Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #61309

Re: Bit Swizzling

Show all headers | View raw

On 9/4/20 11:32 PM, Joshua Landau wrote:
> For an 8 bit value there's a quick method.
> 
> Start with abcdefgh
> PDEP to get 0000000a0000000b0000000c0000000d0000000e0000000f0000000g0000000h
> Multiply by an appropriate 64 bit constant to get the values in the high bits; in your example 0x20_01_80_40_04_10_08_02
> Shift down by 56.

That's a good one when parallel ops are available.  Fast, and it doesn't
require much overhead.  I like it.

> If your value is 64 bit, you can instead do
> (x >> 0) & 0x0101010101010101
> (x >> 1) & 0x0101010101010101
> ...
> (x >> 7) & 0x0101010101010101
> to get your strided inputs, perform a multiplication on each to get the wanted ordering of those 8 bits,
> and then PDEP each into place. The overall cost is 15 shifts, 8 ands, 8 muls, 8 PDEPs and 7 ors,
> with a critical path of shift-and-mul-shift-pdep-or-or-or.
> 
> I can think of more optimal sequences for special-cases.

For an optimal software algorithm where only logical bitwise operators
are available on 8-bit, 16-bit, 32-bit, or 64-bit quantities, I'm going
to have to brute-force the logic through using bit identifiers in bytes,
and then do an analysis to see if any sequences exist in the destination
which match the source, and then extract out those components and
iteratively resolve down until the operation is exhausted with other
manual steps.

I was hoping this was a solved problem that is well-known with easy-to-
read C code taught in CS 351 or something where I could garner and
adapt their well-documented code. :-)

-- 
Rick C. Hodgin

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

Thread

Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@nospicedham.gmail.com> - 2020-09-04 20:33 -0400
  Re: Bit Swizzling MitchAlsup <MitchAlsup@aol.com> - 2020-09-04 18:26 -0700
    Re: Bit Swizzling MitchAlsup <MitchAlsup@aol.com> - 2020-09-04 18:27 -0700
  Re: Bit Swizzling Joshua Landau <joshua.landau.ws@gmail.com> - 2020-09-04 20:32 -0700
    Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-05 09:16 -0400
  Re: Bit Swizzling Bart <bc@nospicedham.freeuk.com> - 2020-09-05 12:33 +0100
  Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-05 13:12 +0100
    Re: Bit Swizzling "John Levine" <johnl@taugh.com> - 2020-09-05 18:50 +0000
      Re: Bit Swizzling "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-06 11:01 -0400
      Re: Bit Swizzling Chris <xxx.syseng.yyy@gfsys.co.uk> - 2020-09-06 17:48 +0100
  Re: Bit Swizzling olcott <NoOne@nospicedham.NoWhere.com> - 2020-09-08 11:25 -0500
    Re: Bit Swizzling olcott <NoOne@nospicedham.NoWhere.com> - 2020-09-08 11:50 -0500

csiph-web