[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: kernel bitreverse function
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
> makes sense.
((b * 0x80200802ull) & 0x0884422110ull) * 0x0101010101ull >> 32
((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 Laight: david%l8s.co.uk@localhost
Main Index |
Thread Index |