Page MenuHomePhabricator

streams: Implement BitStreamReader/Writer classes.
ClosedPublic

Authored by markblundeberg on Apr 12 2019, 03:16.

Details

Summary

Golomb-Rice coding, as specified in BIP 158, involves operations on
individual bits. These classes will be used to implement the
encoding/decoding operations.

For BIP158; is cherry-picked from two commits (fe943f9 and 9b622dc) from:
https://github.com/bitcoin/bitcoin/pull/12254/commits

Depends on D2797.

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

markblundeberg created this revision.Apr 12 2019, 03:16
Herald added a reviewer: Restricted Project. · View Herald TranscriptApr 12 2019, 03:16
Fabien requested changes to this revision.Apr 12 2019, 10:22
Fabien added a subscriber: Fabien.

There are tests missing for some edge cases: nbits < 0, =0, =64 and > 64

src/streams.h
489 ↗(On Diff #8041)
/**
 * Read the specified ...
490 ↗(On Diff #8041)

signficant => significant

494 ↗(On Diff #8041)

0 being a valid value is questionable.
It likely indicates that the caller is misbehaving, and this can have side effects because the function returns a result which is valid for any number of bits.

532 ↗(On Diff #8041)

Dito.

552 ↗(On Diff #8041)

Dito.

src/test/streams_tests.cpp
137 ↗(On Diff #8041)

Move comment above.

141 ↗(On Diff #8041)

Dito.

This revision now requires changes to proceed.Apr 12 2019, 10:22
markblundeberg added inline comments.Apr 12 2019, 17:44
src/streams.h
490 ↗(On Diff #8041)

Interestingly, Core has a codespell thing that catches these... https://github.com/bitcoin/bitcoin/pull/13954#issuecomment-416261394

494 ↗(On Diff #8041)

Indeed for any value of nbits, the result is valid for any greater number of nbits.

The GCSFilter class constructor defaults to P=0, and would thus by default end up calling Read(0) for every element. This is a degenerate case of golomb filter where each element is encoded in plain unary, not very practical but technically valid. It won't actually get used in the block filters where P=19, but I'd prefer to allow nbits=0 for the simplicity.

(I could also imagine a practical protocol where Read(0) might be used: consider a bitwise varint protocol that encodes the number of bits in an upcoming integer, then followed by the content of the integer itself. The minimal encoding of the content of the integer 0 would be a zero bitlength; the encoder/decoder would then benefit from being able to write/read zero bitlength.)

markblundeberg marked 7 inline comments as done.Apr 12 2019, 19:51

fix comments & typo

deadalnix accepted this revision.Apr 14 2019, 19:38
Fabien accepted this revision.Apr 16 2019, 06:48
This revision is now accepted and ready to land.Apr 16 2019, 06:48
This revision was automatically updated to reflect the committed changes.