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}