Re: Bit swizzling

Path	csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	"davidl...@gmail.com" <davidlovemore@gmail.com>
Newsgroups	comp.compilers
Subject	Re: Bit swizzling
Date	Sun, 6 Sep 2020 00:31:53 -0700 (PDT)
Organization	Compilers Central
Lines	32
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<20-09-018@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="58182"; mail-complaints-to="abuse@iecc.com"
Keywords	optimize
Posted-Date	06 Sep 2020 11:43:12 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:2589

Show key headers only | View raw

On Saturday, September 5, 2020 at 5:45:43 PM UTC+1, 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?

There's some good resources on bit permutations including this online calculator here:

http://programming.sirrida.de/calcperm.php

For:
> Input: 07 06 05 04 03 02 01 00
> Output: 05 04 07 02 01 03 00 06

It gives:

x = bit_permute_step_simple(x, 0x55555555, 1);  // Bit index complement 0
x = bit_permute_step_simple(x, 0x33333333, 2);  // Bit index complement 1
x = bit_permute_step_simple(x, 0x0f0f0f0f, 4);  // Bit index complement 2

where

t_bits bit_permute_step_simple(t_bits x, t_bits m, t_uint shift) {
    return ((x & m) << shift) | ((x >> shift) & m);
    }

Approx 12 cycles on superscalar processor.

Source code for a more sophisticated permutation code generator is also available linked from the page.

Some notes here on the online generator:

http://programming.sirrida.de/bit_perm.html#calculator

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