Page MenuHomePhabricator

[avalanche] Use black magic for popcount.
ClosedPublic

Authored by deadalnix on Thu, Nov 29, 16:25.

Details

Summary

Or compiler intrinsic if these are supported.

The black magic algorithm is from 'Owen Anderson <resistor@mac.com>', as far as I know.

Test Plan
make check

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

deadalnix created this revision.Thu, Nov 29, 16:25
Herald added a reviewer: Restricted Project. · View Herald TranscriptThu, Nov 29, 16:25
Herald added a subscriber: schancel. · View Herald Transcript
jasonbcox requested changes to this revision.Thu, Nov 29, 20:10
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/avalanche.cpp
17 ↗(On Diff #6165)

Needs test(s). Something like a map of 1-byte hex values and their known countBits() results, plus concatenating these hex values together of various lengths, should do the job.

27 ↗(On Diff #6165)

Moving this should be in a separate diff. Seems totally unrelated to the popcount change.

This revision now requires changes to proceed.Thu, Nov 29, 20:10
deadalnix requested review of this revision.Thu, Nov 29, 23:58
deadalnix marked 2 inline comments as done.
deadalnix added inline comments.
src/avalanche.cpp
17 ↗(On Diff #6165)

I would rather keep that function as an internal implementation detail than expose it from the API, unless it is required. The behavior is tested via registerVote's test, and while that is not ideal, adding a unittest specifically for it wouldn't cut it either because it would check for the compiler intrinsic on pretty much all plateforms, which we assume is correct (and if it's not, there isn't much we can do about it).

27 ↗(On Diff #6165)

In fact it is. The goal here was to reduce dependencies. The popcount code is used only here and therefore only accessible here. If popcount becomes something that is generally useful, then we'll move it into some header, but in the meantime, I'd rather have it here and static.

jasonbcox accepted this revision.Fri, Nov 30, 18:56

magic

src/avalanche.cpp
17 ↗(On Diff #6165)

As long as registerVote has sufficient testing, then I suppose we're good. Looking at the existing tests, I think the coverage will be enough. I'll continue to think about any new test cases.

This revision is now accepted and ready to land.Fri, Nov 30, 18:56
Fabien accepted this revision.Sat, Dec 1, 12:30
Fabien requested changes to this revision.Sat, Dec 1, 13:58

There is a build warning in the popcount algo

src/avalanche.cpp
23 ↗(On Diff #6165)

avalanche.cpp:23:16: warning: suggest parentheses around ‘+’ in operand of ‘&’ [-Wparentheses]

return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
This revision now requires changes to proceed.Sat, Dec 1, 13:58
Mengerian requested changes to this revision.Sun, Dec 2, 18:49
Mengerian added a subscriber: Mengerian.
Mengerian added inline comments.
src/avalanche.cpp
17 ↗(On Diff #6165)

Could you keep the comment in?
Maybe something like:

Return the number of bits set, as an integer value.
Use compiler intrinsic if these are supported.
Otherwise use black magic algorithm.

deadalnix updated this revision to Diff 6235.Sun, Dec 2, 22:40

Add explainations and link for the blakc magic.
Add parenthesis to make the compiler happy.

jasonbcox accepted this revision.Sun, Dec 2, 23:16

One nit in the new comment

src/avalanche.cpp
24 ↗(On Diff #6235)

theses -> these

Mengerian accepted this revision.Mon, Dec 3, 00:11
Mengerian added inline comments.
src/avalanche.cpp
25 ↗(On Diff #6235)

fund -> found

Mengerian added inline comments.Mon, Dec 3, 03:41
src/avalanche.cpp
22 ↗(On Diff #6235)

bit -> bits
use -> uses

Fabien accepted this revision.Mon, Dec 3, 14:32
This revision is now accepted and ready to land.Mon, Dec 3, 14:32
This revision was automatically updated to reflect the committed changes.