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
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

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
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.)

This revision is now accepted and ready to land.Apr 16 2019, 06:48