Skip to main content

threers_codec/hevc/
cabac.rs

1//! HEVC CABAC — Context-Adaptive Binary Arithmetic Coding (H.265 §9.3).
2//!
3//! HEVC has no CAVLC fallback: *every* slice-data syntax element is arithmetic
4//! coded, so this engine is mandatory for any conformant stream. It is also the
5//! single trickiest kernel to get right — an off-by-one in renormalization or a
6//! wrong table entry corrupts the whole slice with no local symptom.
7//!
8//! This module implements the encoder ([`CabacEncoder`]) with the three bin
9//! coders the spec defines — regular (context-modeled), bypass (equiprobable),
10//! and terminate — plus the context model and its QP-dependent initialization
11//! (§9.3.2.2). Correctness is pinned by a matching decoder in the tests: random
12//! bin scripts are encoded then decoded and must come back identical.
13//!
14//! Pure arithmetic over `Vec<u8>`; identical on native and `wasm32`.
15
16use super::tables::{RANGE_TAB_LPS, TRANS_IDX_LPS, TRANS_IDX_MPS};
17use crate::bitstream::BitWriter;
18
19/// One CABAC context: an adaptive probability state (`0..=63`) and the current
20/// most-probable-bin value (`0`/`1`).
21#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22pub struct CtxModel {
23    /// `pStateIdx` — probability-state index into the range/transition tables.
24    pub state: u8,
25    /// `valMps` — the value (0 or 1) currently treated as most probable.
26    pub mps: u8,
27}
28
29impl CtxModel {
30    /// Initialize from an 8-bit `init_value` and the slice QP (H.265 §9.3.2.2).
31    ///
32    /// The high/low nibbles of `init_value` give a slope/offset that map the QP
33    /// to a starting probability. This is how every context is seeded at the
34    /// start of a slice from the per-syntax-element init constants.
35    pub fn init(init_value: u8, slice_qp: i32) -> Self {
36        let slope_idx = (init_value >> 4) as i32;
37        let offset_idx = (init_value & 0x0F) as i32;
38        let m = slope_idx * 5 - 45;
39        let n = (offset_idx << 3) - 16;
40        let qp = slice_qp.clamp(0, 51);
41        let pre = ((m * qp) >> 4) + n;
42        let pre = pre.clamp(1, 126);
43        if pre <= 63 {
44            CtxModel {
45                state: (63 - pre) as u8,
46                mps: 0,
47            }
48        } else {
49            CtxModel {
50                state: (pre - 64) as u8,
51                mps: 1,
52            }
53        }
54    }
55
56    /// A context pinned to an explicit `(state, mps)` — for tests and for the
57    /// equiprobable-ish defaults some tools use before real init constants land.
58    pub fn from_state(state: u8, mps: u8) -> Self {
59        debug_assert!(state < 64);
60        CtxModel {
61            state,
62            mps: mps & 1,
63        }
64    }
65}
66
67/// CABAC arithmetic encoder (H.265 §9.3.4.3).
68///
69/// Feed bins via [`encode_bin`](Self::encode_bin) (context-modeled),
70/// [`encode_bypass`](Self::encode_bypass), and [`encode_terminate`](Self::encode_terminate).
71/// The final `encode_terminate(1)` (i.e. `end_of_slice_segment_flag = 1`) flushes
72/// the engine; [`finish`](Self::finish) then returns the byte-aligned slice data.
73///
74/// `Clone` is what makes rate estimation possible: an encoder can copy the live
75/// engine and contexts, code a candidate into the copy, read [`bit_len`](Self::bit_len),
76/// and throw it away without disturbing the real bitstream.
77#[derive(Clone)]
78pub struct CabacEncoder {
79    /// `ivlLow` — low bound of the current interval.
80    low: u32,
81    /// `ivlCurrRange` — width of the current interval (kept in `[256, 510]`
82    /// except transiently inside a bin).
83    range: u32,
84    /// Count of undecided (outstanding) bits awaiting a resolving carry.
85    bits_outstanding: u32,
86    /// The very first output bit is discarded (it carries no information).
87    first_bit: bool,
88    out: BitWriter,
89}
90
91impl Default for CabacEncoder {
92    fn default() -> Self {
93        Self::new()
94    }
95}
96
97impl CabacEncoder {
98    /// A freshly initialized engine (§9.3.2.5): range `510`, low `0`.
99    pub fn new() -> Self {
100        Self {
101            low: 0,
102            range: 510,
103            bits_outstanding: 0,
104            first_bit: true,
105            out: BitWriter::new(),
106        }
107    }
108
109    /// Emit a resolved bit `b`, then flush any outstanding bits as `1 - b`
110    /// (§9.3.4.3.5 `PutBit`). The first ever bit is swallowed.
111    #[inline]
112    fn put_bit(&mut self, b: u32) {
113        if self.first_bit {
114            self.first_bit = false;
115        } else {
116            self.out.write_bit(b);
117        }
118        while self.bits_outstanding > 0 {
119            self.out.write_bit(1 - (b & 1));
120            self.bits_outstanding -= 1;
121        }
122    }
123
124    /// Renormalize so `range` returns to `[256, 510]` (§9.3.4.3.3).
125    #[inline]
126    fn renorm(&mut self) {
127        while self.range < 256 {
128            if self.low < 256 {
129                self.put_bit(0);
130            } else if self.low >= 512 {
131                self.low -= 512;
132                self.put_bit(1);
133            } else {
134                self.low -= 256;
135                self.bits_outstanding += 1;
136            }
137            self.range <<= 1;
138            self.low <<= 1;
139        }
140    }
141
142    /// Encode one context-modeled decision (§9.3.4.3.2), updating `ctx`.
143    pub fn encode_bin(&mut self, ctx: &mut CtxModel, bin: u32) {
144        let q = ((self.range >> 6) & 3) as usize;
145        let lps = RANGE_TAB_LPS[ctx.state as usize][q] as u32;
146        self.range -= lps;
147        if (bin & 1) != ctx.mps as u32 {
148            // Least-probable symbol.
149            self.low += self.range;
150            self.range = lps;
151            if ctx.state == 0 {
152                ctx.mps = 1 - ctx.mps;
153            }
154            ctx.state = TRANS_IDX_LPS[ctx.state as usize];
155        } else {
156            // Most-probable symbol.
157            ctx.state = TRANS_IDX_MPS[ctx.state as usize];
158        }
159        self.renorm();
160    }
161
162    /// Encode one equiprobable bin with no context (§9.3.4.3.4). Faster and used
163    /// for sign bits, high-order coefficient bits, etc.
164    pub fn encode_bypass(&mut self, bin: u32) {
165        self.low <<= 1;
166        if (bin & 1) != 0 {
167            self.low += self.range;
168        }
169        if self.low >= 1024 {
170            self.put_bit(1);
171            self.low -= 1024;
172        } else if self.low < 512 {
173            self.put_bit(0);
174        } else {
175            self.low -= 512;
176            self.bits_outstanding += 1;
177        }
178    }
179
180    /// Encode `n` equiprobable bins from the low bits of `value`, MSB-first.
181    pub fn encode_bypass_bits(&mut self, value: u32, n: u32) {
182        for i in (0..n).rev() {
183            self.encode_bypass((value >> i) & 1);
184        }
185    }
186
187    /// Encode a termination decision (§9.3.4.3.5). `bin = 1` ends the slice and
188    /// flushes the engine; `bin = 0` just renormalizes and coding continues.
189    pub fn encode_terminate(&mut self, bin: u32) {
190        self.range -= 2;
191        if (bin & 1) != 0 {
192            self.low += self.range;
193            self.flush();
194        } else {
195            self.renorm();
196        }
197    }
198
199    /// Encode-flush (§9.3.4.3.6): drain the interval to the bitstream. Called by
200    /// `encode_terminate(1)`.
201    fn flush(&mut self) {
202        self.range = 2;
203        self.renorm();
204        self.put_bit((self.low >> 9) & 1);
205        self.out.write_bits(((self.low >> 7) & 3) | 1, 2);
206    }
207
208    /// The arithmetic state with an empty output buffer.
209    ///
210    /// Rate-distortion decisions need to know what a candidate *would* cost, so
211    /// they encode it into a copy and read [`bit_len`](Self::bit_len). Cloning
212    /// the whole encoder would copy every byte written so far, once per
213    /// candidate per level — quadratic in picture size. The bit count is a
214    /// difference, so the buffer can start empty as long as `low`, `range` and
215    /// the outstanding-bit count carry over.
216    pub fn probe(&self) -> Self {
217        Self {
218            low: self.low,
219            range: self.range,
220            bits_outstanding: self.bits_outstanding,
221            first_bit: self.first_bit,
222            out: BitWriter::new(),
223        }
224    }
225
226    /// Number of bits emitted so far (for rate estimation / debugging).
227    pub fn bit_len(&self) -> usize {
228        self.out.bit_len()
229    }
230
231    /// Direct access to the underlying bit writer. Only valid to use between a
232    /// flush (`encode_terminate(1)`, as `I_PCM` does) and [`reinit`](Self::reinit)
233    /// — e.g. to emit `pcm_alignment_zero_bit`s and raw PCM samples that bypass
234    /// the arithmetic coder (H.265 §7.3.8.5 / §9.3.1).
235    pub fn writer_mut(&mut self) -> &mut BitWriter {
236        &mut self.out
237    }
238
239    /// Re-initialize the arithmetic engine (range `510`, low `0`), keeping the
240    /// already-emitted bytes. The decoder does the same after reading an `I_PCM`
241    /// CU's samples, so the two stay in lockstep across the PCM interruption.
242    pub fn reinit(&mut self) {
243        self.low = 0;
244        self.range = 510;
245        self.bits_outstanding = 0;
246        self.first_bit = true;
247    }
248
249    /// Finish and return the byte-aligned coded bytes. Call after the terminating
250    /// `encode_terminate(1)`.
251    pub fn finish(self) -> Vec<u8> {
252        self.out.finish()
253    }
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259
260    /// Minimal MSB-first bit reader that returns `0` once the buffer is
261    /// exhausted — matching how a real decoder sees an over-read at a NAL's end.
262    struct BitReader<'a> {
263        bytes: &'a [u8],
264        pos: usize,
265    }
266    impl<'a> BitReader<'a> {
267        fn new(bytes: &'a [u8]) -> Self {
268            Self { bytes, pos: 0 }
269        }
270        fn read_bit(&mut self) -> u32 {
271            let byte = self.pos >> 3;
272            let bit = 7 - (self.pos & 7);
273            self.pos += 1;
274            if byte < self.bytes.len() {
275                ((self.bytes[byte] >> bit) & 1) as u32
276            } else {
277                0
278            }
279        }
280        fn read_bits(&mut self, n: u32) -> u32 {
281            let mut v = 0;
282            for _ in 0..n {
283                v = (v << 1) | self.read_bit();
284            }
285            v
286        }
287    }
288
289    /// The decoding counterpart of [`CabacEncoder`] (§9.3.4.3), used only to
290    /// prove the encoder roundtrips.
291    struct CabacDecoder<'a> {
292        range: u32,
293        offset: u32,
294        r: BitReader<'a>,
295    }
296    impl<'a> CabacDecoder<'a> {
297        fn new(bytes: &'a [u8]) -> Self {
298            let mut r = BitReader::new(bytes);
299            let offset = r.read_bits(9);
300            Self {
301                range: 510,
302                offset,
303                r,
304            }
305        }
306        fn renorm(&mut self) {
307            while self.range < 256 {
308                self.range <<= 1;
309                self.offset = (self.offset << 1) | self.r.read_bit();
310            }
311        }
312        fn decode_bin(&mut self, ctx: &mut CtxModel) -> u32 {
313            let q = ((self.range >> 6) & 3) as usize;
314            let lps = RANGE_TAB_LPS[ctx.state as usize][q] as u32;
315            self.range -= lps;
316            let bin;
317            if self.offset >= self.range {
318                bin = 1 - ctx.mps as u32;
319                self.offset -= self.range;
320                self.range = lps;
321                if ctx.state == 0 {
322                    ctx.mps = 1 - ctx.mps;
323                }
324                ctx.state = TRANS_IDX_LPS[ctx.state as usize];
325            } else {
326                bin = ctx.mps as u32;
327                ctx.state = TRANS_IDX_MPS[ctx.state as usize];
328            }
329            self.renorm();
330            bin
331        }
332        fn decode_bypass(&mut self) -> u32 {
333            self.offset = (self.offset << 1) | self.r.read_bit();
334            if self.offset >= self.range {
335                self.offset -= self.range;
336                1
337            } else {
338                0
339            }
340        }
341        fn decode_terminate(&mut self) -> u32 {
342            self.range -= 2;
343            if self.offset >= self.range {
344                1
345            } else {
346                self.renorm();
347                0
348            }
349        }
350    }
351
352    /// A tiny deterministic PRNG (xorshift32) so the roundtrip is reproducible
353    /// without `rand` or `Math.random` (unavailable in this environment).
354    struct Rng(u32);
355    impl Rng {
356        fn next(&mut self) -> u32 {
357            let mut x = self.0;
358            x ^= x << 13;
359            x ^= x >> 17;
360            x ^= x << 5;
361            self.0 = x;
362            x
363        }
364        fn bit(&mut self) -> u32 {
365            self.next() & 1
366        }
367    }
368
369    #[derive(Clone, Copy, Debug)]
370    enum Op {
371        Regular(usize, u32),
372        Bypass(u32),
373        Terminate(u32),
374    }
375
376    #[test]
377    fn ctx_init_matches_spec_examples() {
378        // Hand-computed from §9.3.2.2 at SliceQpY = 26.
379        // initValue = 154: slope=9,offset=10 → m=0, n=64, pre=64 → state 0, mps 1.
380        assert_eq!(CtxModel::init(154, 26), CtxModel { state: 0, mps: 1 });
381        // initValue = 0: m=-45, n=-16, pre=clip(-90)=1 → state 62, mps 0.
382        assert_eq!(CtxModel::init(0, 26), CtxModel { state: 62, mps: 0 });
383    }
384
385    fn run_roundtrip(ops: &[Op], ctx_seed: &[CtxModel]) {
386        // Encode.
387        let mut enc = CabacEncoder::new();
388        let mut ectx: Vec<CtxModel> = ctx_seed.to_vec();
389        for &op in ops {
390            match op {
391                Op::Regular(c, b) => enc.encode_bin(&mut ectx[c], b),
392                Op::Bypass(b) => enc.encode_bypass(b),
393                Op::Terminate(b) => enc.encode_terminate(b),
394            }
395        }
396        let bytes = enc.finish();
397
398        // Decode with identical initial contexts and op structure.
399        let mut dec = CabacDecoder::new(&bytes);
400        let mut dctx: Vec<CtxModel> = ctx_seed.to_vec();
401        for (i, &op) in ops.iter().enumerate() {
402            match op {
403                Op::Regular(c, b) => {
404                    assert_eq!(dec.decode_bin(&mut dctx[c]), b, "regular bin #{i}");
405                }
406                Op::Bypass(b) => assert_eq!(dec.decode_bypass(), b, "bypass bin #{i}"),
407                Op::Terminate(b) => assert_eq!(dec.decode_terminate(), b, "terminate bin #{i}"),
408            }
409        }
410    }
411
412    #[test]
413    fn roundtrip_simple() {
414        let seed = vec![CtxModel::from_state(0, 0), CtxModel::from_state(31, 1)];
415        let ops = vec![
416            Op::Regular(0, 1),
417            Op::Regular(0, 0),
418            Op::Regular(1, 1),
419            Op::Bypass(1),
420            Op::Bypass(0),
421            Op::Regular(1, 0),
422            Op::Terminate(0),
423            Op::Regular(0, 1),
424            Op::Terminate(1),
425        ];
426        run_roundtrip(&ops, &seed);
427    }
428
429    #[test]
430    fn roundtrip_randomized() {
431        // Many random scripts across seeds — the strong correctness signal for
432        // the arithmetic engine and all three coding tables.
433        for trial in 0..200u32 {
434            let mut rng = Rng(0x9E37_79B9 ^ trial.wrapping_mul(2654435761));
435            let seed = vec![
436                CtxModel::init((rng.next() & 0xFF) as u8, (rng.next() % 52) as i32),
437                CtxModel::init((rng.next() & 0xFF) as u8, (rng.next() % 52) as i32),
438                CtxModel::init((rng.next() & 0xFF) as u8, (rng.next() % 52) as i32),
439                CtxModel::init((rng.next() & 0xFF) as u8, (rng.next() % 52) as i32),
440            ];
441            let len = 20 + (rng.next() % 400) as usize;
442            let mut ops = Vec::with_capacity(len + 1);
443            for _ in 0..len {
444                match rng.next() % 10 {
445                    0..=6 => ops.push(Op::Regular((rng.next() % 4) as usize, rng.bit())),
446                    7..=8 => ops.push(Op::Bypass(rng.bit())),
447                    _ => ops.push(Op::Terminate(0)),
448                }
449            }
450            ops.push(Op::Terminate(1)); // end_of_slice_segment_flag
451            run_roundtrip(&ops, &seed);
452        }
453    }
454
455    #[test]
456    fn roundtrip_all_bypass() {
457        let seed = vec![CtxModel::from_state(0, 0)];
458        let mut rng = Rng(0x1234_5678);
459        let mut ops: Vec<Op> = (0..500).map(|_| Op::Bypass(rng.bit())).collect();
460        ops.push(Op::Terminate(1));
461        run_roundtrip(&ops, &seed);
462    }
463}