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: da...@l8s.co.uk