streams: Implement BitStreamReader/Writer classes.
ClosedPublic
Actions

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

Details

Reviewers

deadalnix
Fabien

Group Reviewers

Restricted Project

Maniphest Tasks

T589: BIP157 & BIP158 backports

Commits

rSTAGING0925cf776a90: streams: Implement BitStreamReader/Writer classes.
rABC0925cf776a90: streams: Implement BitStreamReader/Writer classes.

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

markblundeberg created this revision.Apr 12 2019, 03:16

Herald added a reviewer: Restricted Project. · View Herald TranscriptApr 12 2019, 03:16

Herald added a reviewer: deadalnix. · View Herald Transcript

markblundeberg added a task: T589: BIP157 & BIP158 backports.Apr 12 2019, 03:17

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B5442: Diff 8041.Apr 12 2019, 03:32

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