Re: Bit swizzling

"davidl...@gmail.com" <davidlovemore@gmail.com>
Sun, 6 Sep 2020 00:31:53 -0700 (PDT)

          From comp.compilers
Related articles
Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-05)
Re: Bit swizzling DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2020-09-05)
Re: Bit Swizzling johnl@taugh.com (John Levine) (2020-09-05)
Re: Bit swizzling 793-849-0957@kylheku.com (Kaz Kylheku) (2020-09-05)
Re: Bit swizzling davidlovemore@gmail.com (davidl...@gmail.com) (2020-09-06)
Re: Bit Swizzling xxx.syseng.yyy@gfsys.co.uk (Chris) (2020-09-06)
Re: Bit swizzling martin@gkc.org.uk (Martin Ward) (2020-09-07)
Re: Bit swizzling rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-07)
Re: Bit swizzling DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2020-09-08)
Re: Bit swizzling tomcrick@gmail.com (Tom Crick) (2020-09-08)
Re: Bit swizzling gah4@u.washington.edu (gah4) (2020-09-10)
[1 later articles]
| List of all articles for this month |
From: "davidl...@gmail.com" <davidlovemore@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 6 Sep 2020 00:31:53 -0700 (PDT)
Organization: Compilers Central
References: 20-09-014
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
In-Reply-To: 20-09-014

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>alculator

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.