[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