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

lvqcl lvqcl.mail at gmail.com
Fri Sep 6 13:08:27 PDT 2013


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():


     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 v;
     int m;
     m=(_v>0xFFFFFFFFU)<<5;
     v=(FLAC__uint32)(_v>>m);
     v|=v>>1;
     v|=v>>2;
     v|=v>>4;
     v|=v>>8;
     v|=v>>16;
     v=(v>>1)+1;
     return m+DEBRUIJN_IDX32[v*0x77CB531U>>27&0x1F];


More information about the flac-dev mailing list