README
¶
boolcoder
Pure-Go (CGO=0) boolean arithmetic decoder — the entropy coder VP8 and VP9 both read their compressed partitions with.
d := boolcoder.NewDecoder(partition)
flag := d.Bool(128) // probability out of 256
v := d.Literal(4) // four bits, each at probability 128
s := d.Signed(6) // magnitude then sign
if err := d.Err(); err != nil {
// the partition ended inside a value
}
What is in it
NewDecoder |
a decoder over one compressed partition |
Bool(probability) |
one boolean at the given probability out of 256 |
Literal(n) |
n bits, each at probability 128, most significant first |
Signed(n) |
an n-bit magnitude followed by a sign bit |
Err |
ErrExhausted once a read has gone past the end |
The error is checked at the end, not at each read. Bool returns a bit, not
a bit and an error, because the format reads thousands of them per block and a
decoder that branched on an error after each one would be unreadable. Once the
partition is exhausted the reads return zeroes and Err reports it, so the
caller finds out at the boundary it cares about instead of at every bit.
⛔ A probability here is out of 256, not a fraction and not out of 255:
Bool(128) is an even chance, Bool(255) is nearly certain to be false. The
probability is the chance of zero, which is the way round the formats state
it and the opposite of what reads naturally.
Consumers
go-avkit/vp8 and
go-avkit/vp9 read the plain bit fields of
their headers; everything behind those is arithmetic-coded, and this is what
reads it.
Windows, macOS, Linux; six 64-bit architectures. 100% statement coverage, gated in CI.
A width the result cannot hold
Literal returns a uint32, so n is 0 to 32 and it panics outside that.
⛔ It used to shift the first bits out of the uint32 in silence and return a
value that was not the field asked for — the same shape as
bitstream's Bits, fixed the
same evening.
A panic is right here and an error is not: every width in VP8 and VP9 is a
constant of the syntax, so one outside the range is a mistake in the caller's
code, not something a stream can state. That was measured rather than assumed —
across go-avkit, every call to Literal and Signed passes a constant, and
the only variable one is Signed's own call to Literal.
Licence
BSD-3-Clause.
Documentation
¶
Overview ¶
Package boolcoder decodes the boolean arithmetic coding that VP8 and VP9 carry everything but their frame headers in, in pure Go.
It is to the VPx family what a bit reader is to the H.26x family: the one mechanism every part above it goes through, shared so that neither codec has to own it and neither depends on the other.
⛔ One engine serves both, and that is measured rather than assumed. The two specifications state the split point differently --
VP8: 1 + (((range-1) * probability) >> 8) VP9: (range * probability + (256 - probability)) >> 8
-- and they are the same expression: adding 256 before a shift of eight is adding one after it, so the two agree for every one of the 32768 pairs of range and probability that can occur. A test asserts that over all of them, because a shared engine resting on an unchecked equivalence would be a shared defect.
AV1 is NOT served by this. Its coder carries probabilities on fifteen bits and normalises differently; it belongs beside this rather than inside it.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrExhausted = errors.New("boolcoder: read past the end of the partition")
ErrExhausted means the decoder read past the end of its data.
It is reported rather than hidden because a bitstream that ends early is a bitstream that was cut, and a decoder handed zeros past the end would go on producing plausible symbols from nothing.
Functions ¶
This section is empty.
Types ¶
type Decoder ¶
type Decoder struct {
// contains filtered or unexported fields
}
Decoder reads symbols from one arithmetic-coded partition.
func NewDecoder ¶
NewDecoder starts reading data.
The state it begins in is what the format states: a range of the whole byte, an empty window, and a count that makes the first read fill it.
func (*Decoder) Bool ¶
Bool reads one bit whose chance of being zero is probability out of 256.
The probability is what the model above this supplies; a probability of 128 is an even chance and makes this read a raw bit.
func (*Decoder) Err ¶
Err reports whether any symbol read so far came from past the end of the data.
It is asked at the END of a partition rather than after each symbol: the arithmetic cannot stop mid-symbol, so the question is whether the partition was long enough for everything that was read from it, and that is only answerable once the reading is done.
func (*Decoder) Literal ¶
Literal reads n raw bits, most significant first: n even chances in a row.
n is 0 to 32, which is what the result holds. ⛔ It PANICS outside that, rather than shifting the first bits out of the uint32 and returning a value that is not the field asked for -- which is what it used to do, silently.
A panic is right here and an error is not: every width in VP8 and VP9 is a CONSTANT of the syntax, so one outside the range is a mistake in the caller's code, not something a stream can state. Measured across go-avkit: every call to Literal and Signed passes a constant, and the only variable one is Signed's own call below.
Source Files