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];
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]; ... ... }
lvqcl wrote:> Found this code: ftp://ftp.samba.org/pub/unpacked/ntdb/lib/ccan/ilog/ilog.cThe canonical location is at CCAN: http://ccodearchive.net/info/ilog.html Note that the code is licensed LGPL. On the other hand, the author is Xiph.org's Timothy Terryberry, so he might be willing to relicense. Ulrich
Timothy B. Terriberry
2013-Sep-06 21:49 UTC
[flac-dev] About de Bruijn sequences in bitmath.h
Ulrich Klauer wrote:> lvqcl wrote: > >> Found this code: ftp://ftp.samba.org/pub/unpacked/ntdb/lib/ccan/ilog/ilog.c > > The canonical location is at CCAN: http://ccodearchive.net/info/ilog.html > Note that the code is licensed LGPL. On the other hand, the author is > Xiph.org's Timothy Terryberry, so he might be willing to relicense.Uh, I thought Rusty and I relicensed that code public domain years ago. I pinged him about updating the page.
Ulrich Klauer <ulrich at chirlu.de> wrote:> The canonical location is at CCAN: http://ccodearchive.net/info/ilog.html > Note that the code is licensed LGPL. On the other hand, the author is > Xiph.org's Timothy Terryberry, so he might be willing to relicense.Thanks for the information. I just thought that for x86 architecture it's faster to simply use 32-bit intrinsic: /* FLAC__bitmath_ilog2(x) == _BitScanReverse(x) == 31 - __builtin_clz(x) */ static inline unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v) { #if _64bit_intrinsic_is_available ... ... ... #else if (v>0xFFFFFFFFU) return 32+FLAC__bitmath_ilog2((FLAC__uint32)(v>>32)); else return FLAC__bitmath_ilog2((FLAC__uint32)v); #endif }