[avalanche] Use black magic for popcount.
ClosedPublic
Actions

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

Details

Reviewers

Group Reviewers

Restricted Project

Commits

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

Repository

rABC Bitcoin ABC

Lint

Lint Not Applicable

Unit

Tests Not Applicable

jasonbcox requested changes to this revision.Nov 29 2018, 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.Nov 29 2018, 20:10

deadalnix requested review of this revision.Nov 29 2018, 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.

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.Nov 30 2018, 18:56

Fabien accepted this revision.Dec 1 2018, 12:30

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.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 ↗	(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.