Re: Bit swizzling

Path	csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	Hans-Peter Diettrich <DrDiettrich1@netscape.net>
Newsgroups	comp.compilers, comp.arch
Subject	Re: Bit swizzling
Date	Sat, 5 Sep 2020 19:38:02 +0200
Organization	Compilers Central
Lines	39
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<20-09-015@comp.compilers> (permalink)
References	<20-09-014@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	8bit
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="1366"; mail-complaints-to="abuse@iecc.com"
Keywords	optimize
Posted-Date	05 Sep 2020 14:51:17 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:2586 comp.arch:61311

Cross-posted to 2 groups.

Show key headers only | View raw

Am 05.09.2020 um 18:05 schrieb Rick C. Hodgin:
> Are there any algorithms which take a known-at-compile-time sequence
> of bitwise operations on an 8-bit to 64-bit quantity, and optimize
> them down to their minimal set of operations?
>
> For example, if I have an 8-bit byte and I want to swizzle the bits
> thusly:
>
>      Input:   07 06 05 04 03 02 01 00
>     Output:   05 04 07 02 01 03 00 06

In your 8-bit case an array of outputs is sufficient, indexed by the input.


> In addition, given the bit operator abilities that exist on various
> CPUs there are potentially other combinations that exist behind an
> operation, such as bitswap, where the order of bits flips or mirrors
> across the center position.

Somebody must build the tables for those operations, distinct for each
CPU, then write code to make use of these tables. I don't think that it
has been done yet, except perhaps for the basic operations (AND, OR...)

> Are there any existing algorithms which examine the operations that
> must be conducted and then create an optimized / minimal sequence of
> mechanical steps to conduct it given a constrained set of features
> (such as those present on a given CPU)?

I often used Quine-McCluskey to minimize my logic circuits.

In most applications a toggled bit in the outputs invalidates all prior
computation optimization attempts, and everything has to be analyzed and
constructed again.

In general a hash code of the inputs could be used to index an array of
outputs. That code is insensitive to changes of output bits, only the
affected array element has to be uptdated then.

DoDi

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 12:05 -0400
  Re: Bit swizzling Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-05 19:38 +0200
  Re: Bit Swizzling "John Levine" <johnl@taugh.com> - 2020-09-05 18:50 +0000
    Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-06 17:48 +0100
  Re: Bit swizzling Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-05 20:15 +0000
  Re: Bit swizzling "davidl...@gmail.com" <davidlovemore@gmail.com> - 2020-09-06 00:31 -0700
  Re: Bit swizzling Martin Ward <martin@gkc.org.uk> - 2020-09-07 12:08 +0100
    Re: Bit swizzling Tom Crick <tomcrick@gmail.com> - 2020-09-08 09:35 +0100
  Re: Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-07 10:55 -0400
    Re: Bit swizzling Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-08 01:45 +0200
  Re: Bit swizzling gah4 <gah4@u.washington.edu> - 2020-09-10 10:34 -0700
    Re: Bit swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-10 17:13 -0400

csiph-web