search

sipa / minisketch

Minisketch: an optimized library for BCH-based set reconciliation
MIT License
310 stars 52 forks source link

Fix MSVC implementation of `CountBits()` function #72

Closed hebasto closed 2 years ago

hebasto commented 2 years ago

The current MSVC-specific implementation of the CountBits() function, which uses _BitScanReverse and _BitScanReverse64 intrinsic functions, returns the wrong value with offset 1.

See: https://learn.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=msvc-170

The second commit makes MSVC ignore a possible /DHAVE_CLZ option (as this compiler is not handled by the current build system), which otherwise causes a compiling error.

A branch, which allows to test this PR easily, is here.

Fixes #67.

hebasto commented 2 years ago

Friendly ping @sipsorcery

sipsorcery commented 2 years ago

@hebasto the cmake build on your branch worked for me as did running the resultant test.exe.

c:\Dev\github\hebasto-minisketch\build\Debug>test.exe
Running libminisketch tests with complexity=4
All tests successful.

I'm not really qualified to ACK this fix though. It doesn't seem to cascade into any critical Bitcoin Core code and is MSVC specific. Still I don't feel like my ACK would be worthwhile.

hebasto commented 2 years ago

@sipsorcery

the cmake build on your branch worked for me as did running the resultant test.exe.

Thank you for testing.

... any critical Bitcoin Core code...

Actually, it is all about implementing a function, which https://github.com/sipa/minisketch/blob/47f0a2d26f6ca0f6ab3ba5e72064a9d28745de77/src/int_utils.h#L129

using a couple of MSVC-specific calls :)

sipsorcery commented 2 years ago

Thank you for testing.

No probs.

Actually, it is all about implementing a function, which...

Yeah, that bit I got but it's the potential side effects and where that function could end up getting used that I'm not sure about.

sipa commented 2 years ago

ACK 0078bedda6078dee91067268ad5fb60b119fd2fb

sipa commented 2 years ago

Thanks, @hebasto for finding and fixing this issue, and thanks @sipsorcery for testing. It's such a simple, extensively-used, function that I have a hard time imagining how it could be wrong without breaking tests.

As an aside, a PR to add MSVC CI would be very welcome.