Re: Bit swizzling

Path	csiph.com!xmission!news.alt.net!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	gah4 <gah4@u.washington.edu>
Newsgroups	comp.compilers
Subject	Re: Bit swizzling
Date	Thu, 10 Sep 2020 10:34:18 -0700 (PDT)
Organization	Compilers Central
Lines	28
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<20-09-026@comp.compilers> (permalink)
References	<20-09-014@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="67222"; mail-complaints-to="abuse@iecc.com"
Keywords	optimize, hardware
Posted-Date	10 Sep 2020 13:55:01 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
In-Reply-To	<20-09-014@comp.compilers>
Xref	csiph.com comp.compilers:2597

Show key headers only | View raw

On Saturday, September 5, 2020 at 9:45:43 AM UTC-7, Rick C. Hodgin wrote:
> 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

There is a lot of work, and many algorithms, for logic optimization,
or minimization, that, for example, will find the optimal combination
of NAND and NOR gates to evaluate some logical operation.

This is used to compile Verilog or VHDL into either FPGA bit files
or ASIC masks.   On the other hand, logic minimization tends to
believe that you can wire anything to anything else.  That is, bit
swizzle is just wiring.  The question you ask doesn't come up.
(Later on, routing has to get all the wires to the appropriate
place, but that is true in general, not just for this case.)

Note that it isn't just adjacent bits, but bits with the same spacing
in the input and output, such that you can mask with AND, shift,
and combine with OR.  I suspect that with the operations usually
available: AND, OR, XOR, and shift, it wouldn't be hard to find an
algorithm for the optimal case.  If you add more operations,
maybe allow also add and multiply, it gets interesting.

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