Page MenuHomePhabricator

[avalanche] Use black magic for popcount.
ClosedPublic

Authored by deadalnix on Nov 29 2018, 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
Branch
avapopcount
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 4168
Build 6402: Bitcoin ABC Buildbot (legacy)
Build 6401: arc lint + arc unit

Event Timeline

jasonbcox requested changes to this revision.Nov 29 2018, 20:10
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/avalanche.cpp
17

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

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

This revision now requires changes to proceed.Nov 29 2018, 20:10
deadalnix marked 2 inline comments as done.
deadalnix added inline comments.
src/avalanche.cpp
17

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

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.

magic

src/avalanche.cpp
17

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.Nov 30 2018, 18:56
Fabien requested changes to this revision.Dec 1 2018, 13:58

There is a build warning in the popcount algo

src/avalanche.cpp
23

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.Dec 1 2018, 13:58
Mengerian requested changes to this revision.Dec 2 2018, 18:49
Mengerian added a subscriber: Mengerian.
Mengerian added inline comments.
src/avalanche.cpp
17

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.

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

One nit in the new comment

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

theses -> these

Mengerian added inline comments.
src/avalanche.cpp
25 ↗(On Diff #6235)

fund -> found

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

bit -> bits
use -> uses

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