Re: kernel bitreverse function

[David Laight <david%l8s.co.uk@localhost>]

On Sat, Apr 02, 2011 at 11:31:15PM +0200, Joerg Sonnenberger wrote:
> On Sat, Apr 02, 2011 at 11:11:39PM +0200, Frank Wille wrote:
> > is there already a global function to reverse the bits in a byte?
> 
> I don't think so.
> 
> > If not, wouldn't it be useful to put an optimized function (e.g. with
> > a 256-byte lookup-table, or 16-byte for the two nibbles to save space)
> > into the kernel, or into libkern?
> 
> Depending on the platform, one of the approaches from
> http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
> makes sense.

Indeed, either:
  ((b * 0x80200802ull) & 0x0884422110ull) * 0x0101010101ull >> 32
or
  ((b * 0x0802u & 0x22110u) | (b * 0x8020u & 0x88440u)) * 0x10101u >> 16
are probably best - probably the 2nd since it avoids a 64x64 multiply.
(Both the above need the result masking to 8 bits.)

The lookup table versions suffer from being a data cache miss!

It is also worth allowing for cpus that can have a hardware instruction
(and then do it in 1 clock!)

        David

-- 
David Laight: david%l8s.co.uk@localhost