[flac-dev] PATCH: bugfixes for bitmath.h

[lvqcl]

Erik de Castro Lopo <mle+la at mega-nerd.com> wrote:

>> However _BitScanReverse64() is called with a pointer to FLAC__uint64
>> (8-byte int). IMHO it's a bug
>
> I would not call that a bug, just a result of trying to write cross
> platform code and relying on functions that are not specified by
> any standard.

Well, the calls of _BitScanReverse/_BitScanReverse64 are inside #ifdef _MSC_VER,
so it's MS-specific code, not cross-platform. _BitScanReverse64 writes 4 least
significant bytes of idx, the 4 most significant bytes are not initialized
and contain some garbage.
FLAC__bitmath_ilog2_wide() returns unsigned. If sizeof(unsigned)==4 then these
4 most significant bytes are discarded and the result is correct. But if
sizeof(unsigned)==8 then FLAC__bitmath_ilog2_wide() will usually return
incorrect value. But as I said it is MS-only code, so sizeof(unsigned) is always 4.


>> 4. Am I right that FLAC__bitmath_ilog2_wide() and FLAC__bitmath_ilog2()
>> return the same value if their argument is less than 2^32? Then
>> FLAC__bitmath_ilog2_wide() works correctly only when compiled with GCC:
>> it should return idx, not idx^63U. Also the result of de Bruijn sequences
>> is off by 1.
>
> This also needs more investigation. Your patch changes the output
> of this function for any given input.

There is a comment "An example of what FLAC__bitmath_ilog2() computes".
One can see that FLAC__bitmath_ilog2() == BitScanReverse() == 31 - CountLeadingZeroes().
And it seems that FLAC__bitmath_ilog2_wide() == BitScanReverse64() ==
== 63 - CountLeadingZeroesLongLong().

About de Bruijn: Ulrich Klauer posted a link to http://ccodearchive.net/info/ilog.html
 From this page: "This can also be thought of as the location of the highest set bit,
with counting starting from one (so that 0 returns 0, 1 returns 1, and 2**31 returns 32)".
For FLAC__bitmath_ilog2()/ilog2_wide() counting starts from zero.


---------------------------------------
And by the way: FLAC__bitmath_ilog2_wide() is for integer-only encoder.
IMHO this encoder is for platforms with very slow or absent FPU, and
the inclusion of MS-specific code to this function looks a bit bizarre.
I measured a speed of various implementations of FLAC__bitmath_ilog2_wide()
on my Core2 CPU before I realized that it's pointless.