BUGFIX-66

Bug 16: Botched Bitwise Arithmetic Encoder

This is a state-of-the-art entropy encoder. Bits are compressed to the extent they are predictable.
Each input bit is encoded using a probability: Before the bit was observed, how likely was it 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 observed bit (is1) selects one side of that split to be the new numeric range (updating lo or hi).
If the observed bit is likely, the range narrows less. If it is unlikely, the range narrows more.
Both sides of the split always contain at least one number. If lo becomes equal to hi, that is ok.
When the most-significant byte of lo matches the most-significant byte of hi, that byte is emitted.
Once all the input bits have been encoded, the remaining bytes of lo are emitted.

Fix The Tiny Bug In This Go Code:

type Encoder struct { to []byte lo uint32 hi uint32 } func NewEncoder() *Encoder { return &Encoder{ hi: ^uint32(0), } } func (e *Encoder) WriteBit(probability1 uint16, is1 bool) { var ( diff = uint64(e.hi - e.lo) prob = uint64(probability1) add = diff * prob >> 16 mid = e.lo + uint32(add) ) if is1 { e.lo = mid + 1 } else { e.hi = mid } for e.lo^e.hi <= 0x_ff_ff_ff { b := byte(e.lo >> 24) e.to = append(e.to, b) e.lo <<= 8 e.hi <<= 8 e.hi += 0xff } } func (e *Encoder) Bytes() []byte { var ( b1 = byte(e.lo >> 24) b2 = byte(e.lo >> 16) b3 = byte(e.lo >> 8) b4 = byte(e.lo) ) return append( e.to, b1, b2, b3, b4, ) }

To receive a hint, submit unfixed code.