[flac-dev] About de Bruijn sequences in bitmath.h

[lvqcl]

lvqcl <lvqcl.mail at gmail.com> писал(а) в своём письме Sat, 07 Sep 2013 00:08:27 +0400:

> Found this code: ftp://ftp.samba.org/pub/unpacked/ntdb/lib/ccan/ilog/ilog.c
>
> Tests show that it's faster to use the following code in FLAC__bitmath_ilog2_wide():
>

Oops, wrong code was posted. Here's correct version:

static inline unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v)
{
...
...
...
     static const unsigned char DEBRUIJN_IDX32[32]={
          0, 1,28, 2,29,14,24, 3,30,22,20,15,25,17, 4, 8,
         31,27,13,23,21,19,16, 7,26,12,18, 6,11, 5,10, 9
     };
     FLAC__uint32 w;
     int m;
     m=(v>0xFFFFFFFFU)<<5;
     w=(FLAC__uint32)(v>>m);
     w|=w>>1;
     w|=w>>2;
     w|=w>>4;
     w|=w>>8;
     w|=w>>16;
     w=(w>>1)+1;
     return m+DEBRUIJN_IDX32[w*0x77CB531U>>27&0x1F];
...
...
}