Skip to main content

threers_codec/vp9/
bool_coder.rs

1//! The VP8/VP9 boolean entropy coder — a binary range coder.
2//!
3//! Every compressed VP9 syntax element is coded as a series of boolean decisions,
4//! each with an 8-bit probability (the chance the bit is 0). This is VP9's analog
5//! of HEVC's CABAC engine, and like it, it is the one kernel that must be
6//! bit-exact: a single wrong renormalization corrupts the whole partition.
7//!
8//! The arithmetic matches RFC 6386 §7, but the start/stop convention follows
9//! libvpx's `vpx_writer` (a leading equiprobable `0` on start, thirty-two
10//! equiprobable `0`s on stop) so the bitstream is accepted by ffmpeg, browsers,
11//! and every other libvpx-derived decoder. Pure arithmetic over `Vec<u8>` —
12//! identical on native and `wasm32`.
13//!
14//! [`BoolEncoder`] is the encode side. Correctness is pinned by a matching
15//! decoder in the tests: random `(prob, bit)` scripts are encoded then decoded
16//! and must come back identical.
17
18/// VP8/VP9 boolean-range encoder (libvpx `vpx_writer` / RFC 6386 §7.3).
19pub struct BoolEncoder {
20    out: Vec<u8>,
21    /// `range` — width of the current interval, kept in `[128, 255]`.
22    range: u32,
23    /// `bottom` — low end of the current interval (with pending output bits).
24    bottom: u32,
25    /// Shifts remaining before the next output byte is complete.
26    bit_count: i32,
27}
28
29impl Default for BoolEncoder {
30    fn default() -> Self {
31        Self::new()
32    }
33}
34
35impl BoolEncoder {
36    /// A fresh encoder primed like libvpx `vpx_start_encode`: `range = 255`,
37    /// `bottom = 0`, and one leading equiprobable `0` so the first emitted byte
38    /// lines up with a libvpx/ffmpeg bool decoder.
39    pub fn new() -> Self {
40        let mut e = Self {
41            out: Vec::new(),
42            range: 255,
43            bottom: 0,
44            bit_count: 24,
45        };
46        e.put_bit(false); // libvpx primes with vpx_write(0, 128)
47        e
48    }
49
50    /// Propagate a carry (`+1`) backward through already-emitted bytes
51    /// (RFC 6386 `add_one_to_output`). The final `insert` is a defensive
52    /// backstop for a whole-number carry; the priming above makes it unreachable
53    /// in normal operation.
54    fn carry(&mut self) {
55        let mut i = self.out.len();
56        while i > 0 {
57            i -= 1;
58            if self.out[i] == 0xff {
59                self.out[i] = 0;
60            } else {
61                self.out[i] += 1;
62                return;
63            }
64        }
65        self.out.insert(0, 1);
66    }
67
68    /// One renormalization shift: emit a bit of `bottom`, completing a byte every
69    /// eight shifts.
70    #[inline]
71    fn shift(&mut self) {
72        if self.bottom & 0x8000_0000 != 0 {
73            self.carry();
74        }
75        self.bottom <<= 1;
76        self.bit_count -= 1;
77        if self.bit_count == 0 {
78            self.out.push((self.bottom >> 24) as u8);
79            self.bottom &= (1 << 24) - 1;
80            self.bit_count = 8;
81        }
82    }
83
84    /// Encode one boolean `bit` whose probability of being `0` is `prob/256`
85    /// (RFC 6386 `write_bool`).
86    pub fn put_bool(&mut self, prob: u8, bit: bool) {
87        let split = 1 + (((self.range - 1) * prob as u32) >> 8);
88        if bit {
89            self.bottom += split;
90            self.range -= split;
91        } else {
92            self.range = split;
93        }
94        while self.range < 128 {
95            self.range <<= 1;
96            self.shift();
97        }
98    }
99
100    /// Encode one equiprobable bit (probability 128, i.e. a literal bit).
101    pub fn put_bit(&mut self, bit: bool) {
102        self.put_bool(128, bit);
103    }
104
105    /// Encode the `n` low bits of `value`, MSB first, as literals.
106    pub fn put_literal(&mut self, value: u32, n: u32) {
107        for i in (0..n).rev() {
108            self.put_bit((value >> i) & 1 != 0);
109        }
110    }
111
112    /// Flush like libvpx `vpx_stop_encode`: thirty-two equiprobable `0`s so the
113    /// pending interval is fully emitted, then return the coded bytes.
114    pub fn finish(mut self) -> Vec<u8> {
115        for _ in 0..32 {
116            self.put_bit(false);
117        }
118        self.out
119    }
120
121    /// Bytes emitted so far (renormalized; excludes the pending interval).
122    pub fn len(&self) -> usize {
123        self.out.len()
124    }
125
126    pub fn is_empty(&self) -> bool {
127        self.out.is_empty()
128    }
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    /// The decode counterpart (RFC 6386 §7.3), used only to prove the encoder
136    /// round-trips.
137    struct BoolDecoder<'a> {
138        input: &'a [u8],
139        pos: usize,
140        range: u32,
141        value: u32,
142        bit_count: i32,
143    }
144    impl<'a> BoolDecoder<'a> {
145        fn new(input: &'a [u8]) -> Self {
146            let b0 = input.first().copied().unwrap_or(0) as u32;
147            let b1 = input.get(1).copied().unwrap_or(0) as u32;
148            let mut d = Self {
149                input,
150                pos: 2,
151                range: 255,
152                value: (b0 << 8) | b1,
153                bit_count: 0,
154            };
155            // libvpx `vpx_reader_init` consumes the encoder's priming 0 bit.
156            assert!(!d.get_bool(128), "bool coder marker bit must be 0");
157            d
158        }
159        fn get_bool(&mut self, prob: u8) -> bool {
160            let split = 1 + (((self.range - 1) * prob as u32) >> 8);
161            let big_split = split << 8;
162            let ret = if self.value >= big_split {
163                self.range -= split;
164                self.value -= big_split;
165                true
166            } else {
167                self.range = split;
168                false
169            };
170            while self.range < 128 {
171                self.value <<= 1;
172                self.range <<= 1;
173                self.bit_count += 1;
174                if self.bit_count == 8 {
175                    self.bit_count = 0;
176                    let byte = self.input.get(self.pos).copied().unwrap_or(0) as u32;
177                    self.pos += 1;
178                    self.value |= byte;
179                }
180            }
181            ret
182        }
183        fn get_literal(&mut self, n: u32) -> u32 {
184            let mut v = 0;
185            for _ in 0..n {
186                v = (v << 1) | self.get_bool(128) as u32;
187            }
188            v
189        }
190    }
191
192    /// A tiny deterministic xorshift PRNG (no `rand` / `Math.random`).
193    struct Rng(u32);
194    impl Rng {
195        fn next(&mut self) -> u32 {
196            let mut x = self.0;
197            x ^= x << 13;
198            x ^= x >> 17;
199            x ^= x << 5;
200            self.0 = x;
201            x
202        }
203    }
204
205    #[test]
206    fn roundtrip_simple() {
207        let script: &[(u8, bool)] = &[
208            (128, true),
209            (128, false),
210            (10, true),
211            (250, false),
212            (200, true),
213            (5, false),
214        ];
215        let mut enc = BoolEncoder::new();
216        for &(p, b) in script {
217            enc.put_bool(p, b);
218        }
219        let bytes = enc.finish();
220        let mut dec = BoolDecoder::new(&bytes);
221        for &(p, b) in script {
222            assert_eq!(dec.get_bool(p), b);
223        }
224    }
225
226    #[test]
227    fn roundtrip_randomized() {
228        // Many random scripts, mixing modeled bools and literals — the strong
229        // correctness signal for the range coder and its carry propagation.
230        for trial in 0..300u32 {
231            let mut rng = Rng(0x9E37_79B9 ^ trial.wrapping_mul(2654435761));
232            let len = 20 + (rng.next() % 500) as usize;
233            let ops: Vec<(u8, bool)> = (0..len)
234                .map(|_| {
235                    // Bias probabilities toward the extremes to stress renorm.
236                    let p = match rng.next() % 4 {
237                        0 => 1,
238                        1 => 255,
239                        _ => (rng.next() % 256) as u8,
240                    };
241                    (p.max(1), rng.next() & 1 != 0)
242                })
243                .collect();
244
245            let mut enc = BoolEncoder::new();
246            for &(p, b) in &ops {
247                enc.put_bool(p, b);
248            }
249            let bytes = enc.finish();
250
251            let mut dec = BoolDecoder::new(&bytes);
252            for (i, &(p, b)) in ops.iter().enumerate() {
253                assert_eq!(dec.get_bool(p), b, "trial {trial} bin {i} (prob {p})");
254            }
255        }
256    }
257
258    #[test]
259    fn roundtrip_literals() {
260        let mut rng = Rng(0x1234_5678);
261        let vals: Vec<(u32, u32)> = (0..200)
262            .map(|_| {
263                let n = 1 + rng.next() % 16;
264                (rng.next() & ((1 << n) - 1), n)
265            })
266            .collect();
267        let mut enc = BoolEncoder::new();
268        for &(v, n) in &vals {
269            enc.put_literal(v, n);
270        }
271        let bytes = enc.finish();
272        let mut dec = BoolDecoder::new(&bytes);
273        for &(v, n) in &vals {
274            assert_eq!(dec.get_literal(n), v, "literal {v} ({n} bits)");
275        }
276    }
277
278    #[test]
279    fn roundtrip_all_ones_carry_stress() {
280        // Long runs of the least-probable symbol force maximal carry propagation.
281        let mut enc = BoolEncoder::new();
282        let ops: Vec<(u8, bool)> = (0..2000).map(|i| (1u8, i % 7 != 0)).collect();
283        for &(p, b) in &ops {
284            enc.put_bool(p, b);
285        }
286        let bytes = enc.finish();
287        let mut dec = BoolDecoder::new(&bytes);
288        for &(p, b) in &ops {
289            assert_eq!(dec.get_bool(p), b);
290        }
291    }
292}