Re: kernel bitreverse function

[Frank Wille <frank%phoenix.owl.de@localhost>]

David Laight wrote:

> Works for me, I replaced the 2nd multiply by a shift (of the 1st product).

Your're right. I got a compiler bug. It works with gcc.


> I more modern gcc, compiling for a more modern cpu type, might
> generate code that will run faster on a modern cpu.

I guess the function is mostly used in mii or i2c drivers, which are
not so time critical. So I would put a bigger weight on the code size,
which is fine here.


Did somebody already try to implement it? If not, I would suggest the
following code for src/sys/lib/libkern:

New files:

bitrev8.c:
/*      $NetBSD: $     */

#include <lib/libkern/libkern.h>

uint8_t bitrev8(uint8_t b)
{

        return ((b * 0x0802u & 0x22110u) | (b * 0x8020u & 0x88440u))
            * 0x10101u >> 16;
}

bitrev16.c:
/*      $NetBSD: $     */

#include <lib/libkern/libkern.h>

uint16_t bitrev16(uint16_t b)
{

        return (bitrev8(b & 0xff) << 8) | bitrev8(b >> 8);
}

bitrev32.c:
/*      $NetBSD: $     */

#include <lib/libkern/libkern.h>

uint32_t bitrev32(uint32_t b)
{

        return (bitrev16(b & 0xffff) << 16) | bitrev16(b >> 16);
}


Diffs:

Index: Makefile.libkern
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/Makefile.libkern,v
retrieving revision 1.13
diff -u -r1.13 Makefile.libkern
--- Makefile.libkern    24 Mar 2011 17:05:44 -0000      1.13
+++ Makefile.libkern    3 Apr 2011 15:02:50 -0000
@@ -61,6 +61,7 @@
 .if empty(SRCS:Mbyte_swap_8.*)
 SRCS+= bswap64.c
 .endif
+SRCS+= bitrev8.c bitrev16.c bitrev32.c
 SRCS+= md4c.c md5c.c rmd160.c sha1.c sha2.c
 SRCS+= pmatch.c arc4random.c bcd.c mcount.c mertwist.c crc32.c

 Index: libkern.h
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.97
diff -u -r1.97 libkern.h
--- libkern.h   19 Feb 2011 02:02:14 -0000      1.97
+++ libkern.h   3 Apr 2011 15:02:50 -0000
@@ -348,4 +348,7 @@
 unsigned int   popcountll(unsigned long long) __constfunc;
 unsigned int   popcount32(uint32_t) __constfunc;
 unsigned int   popcount64(uint64_t) __constfunc;
+uint8_t         bitrev8(uint8_t);
+uint16_t bitrev16(uint16_t);
+uint32_t bitrev32(uint32_t);
 #endif /* !_LIB_LIBKERN_LIBKERN_H_ */


I'm not sure about the license, though. Is it sufficient to mention
Sean Anderson as the author of the original algorithm, but use the
standard NetBSD header?

Any comments? Then please speak now. :)

-- 
Frank Wille