BUGFIX-66

Bug 17: Botched Bitwise Arithmetic Decoder

This is a state-of-the-art entropy decoder. It consumes a sequence of bytes from the encoder.
Each bit is decoded using the same probability that the encoder used: How likely is this bit to be 1?
0 <= probability1 <= 65535 (0 denotes a probability near 0 and 65535 denotes a probability near 1)
For each bit, this code splits a numeric range (from lo to hi, inclusive) according to probability1.
The bytes received from the encoder indicate which side of that split to select.
The selected side becomes the new numeric range: lo or hi is updated, just like in the encoder.
Both sides of the split always contain at least one number. If lo becomes equal to hi, that is ok.
Side selection also yields an output bit. This code returns true to indicate a 1-bit.
When the most-significant byte of lo matches the most-significant byte of hi, both bytes are discarded.
As lo/hi bytes are discarded, additional bytes from the encoder are consumed.

Fix The Tiny Bug In This Go Code:

type Decoder struct { fr []byte at uint32 lo uint32 hi uint32 } func NewDecoder(from []byte) *Decoder { var ( at1 = uint32(from[0]) << 24 at2 = uint32(from[1]) << 16 at3 = uint32(from[2]) << 8 at4 = uint32(from[3]) ) return &Decoder{ fr: from[4:], at: at1 + at2 + at3 + at4, hi: ^uint32(0), } } func (d *Decoder) ReadBit(probability1 uint16) bool { var ( diff = uint64(d.hi - d.lo) prob = uint64(probability1) add = diff * prob >> 16 mid = d.lo + uint32(add) is1 = d.at <= mid ) if is1 { d.hi = mid } else { d.lo = mid + 1 } for d.lo^d.hi <= 0x_ff_ff_ff { d.lo <<= 8 d.hi <<= 8 d.hi += 0xff d.at <<= 8 d.at += uint32(d.fr[0]) } return is1 }

To receive a hint, submit unfixed code.