Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/h264/cavlc.rs

28.2 KiB, 34 runs

created by r1870400018:21085, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The variable-length code tables, and reading a block of coefficients with them.
2//!
3//! CAVLC is the entropy coder H.264 uses when `entropy_coding_mode_flag` is off, and **711 films in
4//! the corpus use it** -- every Baseline one. It is not a fallback and not a legacy path: it is two
5//! films in every five. Nothing about it resembles the arithmetic coder beside it. Where CABAC
6//! carries a probability that adapts with the picture, CAVLC carries published code tables and
7//! switches between them on what has already been decoded.
8//!
9//! # How a block is read
10//!
11//! A four-by-four block's coefficients are read **backwards**, from the highest frequency down:
12//!
13//! 1. `coeff_token` says how many coefficients are not zero and how many of them, at the end of the
14//! block, are exactly ±1. Which of the six tables reads it depends on `nC`, the mean of the
15//! counts in the blocks above and to the left -- so a block's *table* depends on its
16//! neighbours, and getting that wrong reads the right bits with the wrong code and desynchronises
17//! everything after it.
18//! 2. Each trailing ±1 costs one bit: its sign.
19//! 3. Every other level is a prefix of zeroes, a suffix whose width **grows as the levels do**, and
20//! an escape for the large ones.
21//! 4. `total_zeros` says how many zeroes lie among the coefficients, and `run_before` distributes
22//! them.
23//!
24//! Step 3 is where the coder earns its keep and where a decoder goes wrong quietly: `suffixLength`
25//! starts at nought or one depending on the token, and climbs each time a level exceeds
26//! `3 << (suffixLength − 1)`. A decoder that never climbs it decodes small blocks perfectly and
27//! busy ones as noise.
28//!
29//! # Where the tables came from
30//!
31//! Parsed out of Rec. ITU-T H.264 (08/2021) rather than typed in: Table 9-5 is 372 codewords and a
32//! transcription shifted by one place in one column is a picture that is right until it meets a
33//! busy block. The tests re-read the same tables out of the specification and, separately, assert
34//! that every column is a prefix code -- which a misread codeword almost always breaks.
35//!
36//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
37//! Anthropic Claude
38
39use crate::h264::Bits;
40
41use oxedyne_fe2o3_core::prelude::*;
42
43// coeff_token, as (bits, code) by column of Table 9-5, trailing ones and total.
44// The six columns are the six ranges of nC: below two, below four, below eight, eight
45// and over, and the two chroma direct-current tables at −1 and −2. An entry of no bits is a
46// combination the table does not code.
47pub const COEFF_TOKEN: [[[(u8, u16); 17]; 4]; 6] = [
48 [
49 [(1, 0b1), (6, 0b000101), (8, 0b00000111), (9, 0b000000111), (10, 0b0000000111), (11, 0b00000000111), (13, 0b0000000001111), (13, 0b0000000001011), (13, 0b0000000001000), (14, 0b00000000001111), (14, 0b00000000001011), (15, 0b000000000001111), (15, 0b000000000001011), (16, 0b0000000000001111), (16, 0b0000000000001011), (16, 0b0000000000000111), (16, 0b0000000000000100)],
50 [(0, 0), (2, 0b01), (6, 0b000100), (8, 0b00000110), (9, 0b000000110), (10, 0b0000000110), (11, 0b00000000110), (13, 0b0000000001110), (13, 0b0000000001010), (14, 0b00000000001110), (14, 0b00000000001010), (15, 0b000000000001110), (15, 0b000000000001010), (15, 0b000000000000001), (16, 0b0000000000001110), (16, 0b0000000000001010), (16, 0b0000000000000110)],
51 [(0, 0), (0, 0), (3, 0b001), (7, 0b0000101), (8, 0b00000101), (9, 0b000000101), (10, 0b0000000101), (11, 0b00000000101), (13, 0b0000000001101), (13, 0b0000000001001), (14, 0b00000000001101), (14, 0b00000000001001), (15, 0b000000000001101), (15, 0b000000000001001), (16, 0b0000000000001101), (16, 0b0000000000001001), (16, 0b0000000000000101)],
52 [(0, 0), (0, 0), (0, 0), (5, 0b00011), (6, 0b000011), (7, 0b0000100), (8, 0b00000100), (9, 0b000000100), (10, 0b0000000100), (11, 0b00000000100), (13, 0b0000000001100), (14, 0b00000000001100), (14, 0b00000000001000), (15, 0b000000000001100), (15, 0b000000000001000), (16, 0b0000000000001100), (16, 0b0000000000001000)],
53 ],
54 [
55 [(2, 0b11), (6, 0b001011), (6, 0b000111), (7, 0b0000111), (8, 0b00000111), (8, 0b00000100), (9, 0b000000111), (11, 0b00000001111), (11, 0b00000001011), (12, 0b000000001111), (12, 0b000000001011), (12, 0b000000001000), (13, 0b0000000001111), (13, 0b0000000001011), (13, 0b0000000000111), (14, 0b00000000001001), (14, 0b00000000000111)],
56 [(0, 0), (2, 0b10), (5, 0b00111), (6, 0b001010), (6, 0b000110), (7, 0b0000110), (8, 0b00000110), (9, 0b000000110), (11, 0b00000001110), (11, 0b00000001010), (12, 0b000000001110), (12, 0b000000001010), (13, 0b0000000001110), (13, 0b0000000001010), (14, 0b00000000001011), (14, 0b00000000001000), (14, 0b00000000000110)],
57 [(0, 0), (0, 0), (3, 0b011), (6, 0b001001), (6, 0b000101), (7, 0b0000101), (8, 0b00000101), (9, 0b000000101), (11, 0b00000001101), (11, 0b00000001001), (12, 0b000000001101), (12, 0b000000001001), (13, 0b0000000001101), (13, 0b0000000001001), (13, 0b0000000000110), (14, 0b00000000001010), (14, 0b00000000000101)],
58 [(0, 0), (0, 0), (0, 0), (4, 0b0101), (4, 0b0100), (5, 0b00110), (6, 0b001000), (6, 0b000100), (7, 0b0000100), (9, 0b000000100), (11, 0b00000001100), (11, 0b00000001000), (12, 0b000000001100), (13, 0b0000000001100), (13, 0b0000000001000), (13, 0b0000000000001), (14, 0b00000000000100)],
59 ],
60 [
61 [(4, 0b1111), (6, 0b001111), (6, 0b001011), (6, 0b001000), (7, 0b0001111), (7, 0b0001011), (7, 0b0001001), (7, 0b0001000), (8, 0b00001111), (8, 0b00001011), (9, 0b000001111), (9, 0b000001011), (9, 0b000001000), (10, 0b0000001101), (10, 0b0000001001), (10, 0b0000000101), (10, 0b0000000001)],
62 [(0, 0), (4, 0b1110), (5, 0b01111), (5, 0b01100), (5, 0b01010), (5, 0b01000), (6, 0b001110), (6, 0b001010), (7, 0b0001110), (8, 0b00001110), (8, 0b00001010), (9, 0b000001110), (9, 0b000001010), (9, 0b000000111), (10, 0b0000001100), (10, 0b0000001000), (10, 0b0000000100)],
63 [(0, 0), (0, 0), (4, 0b1101), (5, 0b01110), (5, 0b01011), (5, 0b01001), (6, 0b001101), (6, 0b001001), (7, 0b0001101), (7, 0b0001010), (8, 0b00001101), (8, 0b00001001), (9, 0b000001101), (9, 0b000001001), (10, 0b0000001011), (10, 0b0000000111), (10, 0b0000000011)],
64 [(0, 0), (0, 0), (0, 0), (4, 0b1100), (4, 0b1011), (4, 0b1010), (4, 0b1001), (4, 0b1000), (5, 0b01101), (6, 0b001100), (7, 0b0001100), (8, 0b00001100), (8, 0b00001000), (9, 0b000001100), (10, 0b0000001010), (10, 0b0000000110), (10, 0b0000000010)],
65 ],
66 [
67 [(6, 0b000011), (6, 0b000000), (6, 0b000100), (6, 0b001000), (6, 0b001100), (6, 0b010000), (6, 0b010100), (6, 0b011000), (6, 0b011100), (6, 0b100000), (6, 0b100100), (6, 0b101000), (6, 0b101100), (6, 0b110000), (6, 0b110100), (6, 0b111000), (6, 0b111100)],
68 [(0, 0), (6, 0b000001), (6, 0b000101), (6, 0b001001), (6, 0b001101), (6, 0b010001), (6, 0b010101), (6, 0b011001), (6, 0b011101), (6, 0b100001), (6, 0b100101), (6, 0b101001), (6, 0b101101), (6, 0b110001), (6, 0b110101), (6, 0b111001), (6, 0b111101)],
69 [(0, 0), (0, 0), (6, 0b000110), (6, 0b001010), (6, 0b001110), (6, 0b010010), (6, 0b010110), (6, 0b011010), (6, 0b011110), (6, 0b100010), (6, 0b100110), (6, 0b101010), (6, 0b101110), (6, 0b110010), (6, 0b110110), (6, 0b111010), (6, 0b111110)],
70 [(0, 0), (0, 0), (0, 0), (6, 0b001011), (6, 0b001111), (6, 0b010011), (6, 0b010111), (6, 0b011011), (6, 0b011111), (6, 0b100011), (6, 0b100111), (6, 0b101011), (6, 0b101111), (6, 0b110011), (6, 0b110111), (6, 0b111011), (6, 0b111111)],
71 ],
72 [
73 [(2, 0b01), (6, 0b000111), (6, 0b000100), (6, 0b000011), (6, 0b000010), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
74 [(0, 0), (1, 0b1), (6, 0b000110), (7, 0b0000011), (8, 0b00000011), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
75 [(0, 0), (0, 0), (3, 0b001), (7, 0b0000010), (8, 0b00000010), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
76 [(0, 0), (0, 0), (0, 0), (6, 0b000101), (7, 0b0000000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
77 ],
78 [
79 [(1, 0b1), (7, 0b0001111), (7, 0b0001110), (9, 0b000000111), (9, 0b000000110), (10, 0b0000000111), (11, 0b00000000111), (12, 0b000000000111), (13, 0b0000000000111), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
80 [(0, 0), (2, 0b01), (7, 0b0001101), (7, 0b0001100), (9, 0b000000101), (10, 0b0000000110), (11, 0b00000000110), (12, 0b000000000110), (12, 0b000000000101), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
81 [(0, 0), (0, 0), (3, 0b001), (7, 0b0001011), (7, 0b0001010), (9, 0b000000100), (10, 0b0000000101), (11, 0b00000000101), (12, 0b000000000100), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
82 [(0, 0), (0, 0), (0, 0), (5, 0b00001), (6, 0b000001), (7, 0b0001001), (7, 0b0001000), (10, 0b0000000100), (11, 0b00000000100), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
83 ],
84];
85
86// total_zeros for a block of sixteen coefficients, by tzVlcIndex and by the count
87// (Tables 9-7 and 9-8).
88pub const TOTAL_ZEROS: [[(u8, u16); 16]; 15] = [
89 [(1, 0b1), (3, 0b011), (3, 0b010), (4, 0b0011), (4, 0b0010), (5, 0b00011), (5, 0b00010), (6, 0b000011), (6, 0b000010), (7, 0b0000011), (7, 0b0000010), (8, 0b00000011), (8, 0b00000010), (9, 0b000000011), (9, 0b000000010), (9, 0b000000001)],
90 [(3, 0b111), (3, 0b110), (3, 0b101), (3, 0b100), (3, 0b011), (4, 0b0101), (4, 0b0100), (4, 0b0011), (4, 0b0010), (5, 0b00011), (5, 0b00010), (6, 0b000011), (6, 0b000010), (6, 0b000001), (6, 0b000000), (0, 0)],
91 [(4, 0b0101), (3, 0b111), (3, 0b110), (3, 0b101), (4, 0b0100), (4, 0b0011), (3, 0b100), (3, 0b011), (4, 0b0010), (5, 0b00011), (5, 0b00010), (6, 0b000001), (5, 0b00001), (6, 0b000000), (0, 0), (0, 0)],
92 [(5, 0b00011), (3, 0b111), (4, 0b0101), (4, 0b0100), (3, 0b110), (3, 0b101), (3, 0b100), (4, 0b0011), (3, 0b011), (4, 0b0010), (5, 0b00010), (5, 0b00001), (5, 0b00000), (0, 0), (0, 0), (0, 0)],
93 [(4, 0b0101), (4, 0b0100), (4, 0b0011), (3, 0b111), (3, 0b110), (3, 0b101), (3, 0b100), (3, 0b011), (4, 0b0010), (5, 0b00001), (4, 0b0001), (5, 0b00000), (0, 0), (0, 0), (0, 0), (0, 0)],
94 [(6, 0b000001), (5, 0b00001), (3, 0b111), (3, 0b110), (3, 0b101), (3, 0b100), (3, 0b011), (3, 0b010), (4, 0b0001), (3, 0b001), (6, 0b000000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
95 [(6, 0b000001), (5, 0b00001), (3, 0b101), (3, 0b100), (3, 0b011), (2, 0b11), (3, 0b010), (4, 0b0001), (3, 0b001), (6, 0b000000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
96 [(6, 0b000001), (4, 0b0001), (5, 0b00001), (3, 0b011), (2, 0b11), (2, 0b10), (3, 0b010), (3, 0b001), (6, 0b000000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
97 [(6, 0b000001), (6, 0b000000), (4, 0b0001), (2, 0b11), (2, 0b10), (3, 0b001), (2, 0b01), (5, 0b00001), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
98 [(5, 0b00001), (5, 0b00000), (3, 0b001), (2, 0b11), (2, 0b10), (2, 0b01), (4, 0b0001), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
99 [(4, 0b0000), (4, 0b0001), (3, 0b001), (3, 0b010), (1, 0b1), (3, 0b011), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
100 [(4, 0b0000), (4, 0b0001), (2, 0b01), (1, 0b1), (3, 0b001), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
101 [(3, 0b000), (3, 0b001), (1, 0b1), (2, 0b01), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
102 [(2, 0b00), (2, 0b01), (1, 0b1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
103 [(1, 0b0), (1, 0b1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
104];
105
106// total_zeros for a 4:2:0 chroma direct-current block of four (Table 9-9(a)).
107pub const TOTAL_ZEROS_CHROMA: [[(u8, u16); 4]; 3] = [
108 [(1, 0b1), (2, 0b01), (3, 0b001), (3, 0b000)],
109 [(1, 0b1), (2, 0b01), (2, 0b00), (0, 0)],
110 [(1, 0b1), (1, 0b0), (0, 0), (0, 0)],
111];
112
113// run_before, by how many zeroes are left and by the run (Table 9-10).
114// The seventh row serves every zerosLeft above six, which is why it runs to fourteen
115// where the others stop at their own count.
116pub const RUN_BEFORE: [[(u8, u16); 15]; 7] = [
117 [(1, 0b1), (1, 0b0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
118 [(1, 0b1), (2, 0b01), (2, 0b00), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
119 [(2, 0b11), (2, 0b10), (2, 0b01), (2, 0b00), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
120 [(2, 0b11), (2, 0b10), (2, 0b01), (3, 0b001), (3, 0b000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
121 [(2, 0b11), (2, 0b10), (3, 0b011), (3, 0b010), (3, 0b001), (3, 0b000), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
122 [(2, 0b11), (3, 0b000), (3, 0b001), (3, 0b011), (3, 0b010), (3, 0b101), (3, 0b100), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
123 [(3, 0b111), (3, 0b110), (3, 0b101), (3, 0b100), (3, 0b011), (3, 0b010), (3, 0b001), (4, 0b0001), (5, 0b00001), (6, 0b000001), (7, 0b0000001), (8, 0b00000001), (9, 0b000000001), (10, 0b0000000001), (11, 0b00000000001)],
124];
125
126#[derive(Clone, Debug, PartialEq, Eq)]
127pub struct Block {
128 pub levels: Vec<i32>, // scan order, from the direct current term upward, zeroes and all
129 pub total: usize, // how many are not zero, which the next block's nC is derived from
130}
131
132/// Reads a value out of a code table, given the table's entries as `(bits, code)`.
133///
134/// Every table here is a prefix code, so at most one entry matches whatever comes next, and the
135/// longest entry is sixteen bits. A run of bits matching nothing is a desynchronised decoder and is
136/// refused rather than guessed at: from that point on every later block would be noise, and the
137/// picture that came out would look decoded.
138fn lookup(b: &mut Bits, table: &[(u8, u16)], what: &str) -> Outcome<usize> {
139 let peeked = b.peek(16);
140 for (i, (bits, code)) in table.iter().enumerate() {
141 if *bits == 0 {
142 continue;
143 }
144 if (peeked >> (16 - *bits as u32)) == *code as u32 {
145 res!(b.skip(*bits as usize));
146 return Ok(i);
147 }
148 }
149 Err(err!(
150 "The next bits, {:016b}, are not a {} codeword in this table.", peeked, what;
151 Invalid, Input, Decode))
152}
153
154/// Which column of Table 9-5 a block's `coeff_token` is read from, given `nC` (§9.2.1).
155fn token_column(nc: i32) -> usize {
156 match nc {
157 -1 => 4,
158 n if n <= -2 => 5,
159 n if n < 2 => 0,
160 n if n < 4 => 1,
161 n if n < 8 => 2,
162 _ => 3,
163 }
164}
165
166/// Reads `coeff_token`: how many coefficients are not zero, and how many trailing ±1s (§9.2.1).
167pub fn coeff_token(b: &mut Bits, nc: i32) -> Outcome<(usize, usize)> {
168 let col = token_column(nc);
169 let peeked = b.peek(16);
170 for t1 in 0..4usize {
171 for tc in 0..17usize {
172 let (bits, code) = COEFF_TOKEN[col][t1][tc];
173 if bits == 0 {
174 continue;
175 }
176 if (peeked >> (16 - bits as u32)) == code as u32 {
177 res!(b.skip(bits as usize));
178 return Ok((t1, tc));
179 }
180 }
181 }
182 Err(err!(
183 "The next bits, {:016b}, are not a coeff_token in the table nC of {} selects.", peeked, nc;
184 Invalid, Input, Decode))
185}
186
187/// Reads `level_prefix`: the count of zeroes before the next one bit (§9.2.2.1).
188fn level_prefix(b: &mut Bits) -> Outcome<u32> {
189 let mut zeros = 0u32;
190 while res!(b.u(1)) == 0 {
191 zeros += 1;
192 // A prefix beyond this is not a level, it is a decoder that has lost the bitstream. The
193 // profiles in the corpus cap it at 15, and the widest any profile allows is 11 plus the
194 // bit depth.
195 if zeros > 32 {
196 return Err(err!(
197 "A level_prefix ran past 32 zeroes, so the bitstream is no longer being read \
198 where its syntax is.";
199 Invalid, Input, Decode));
200 }
201 }
202 Ok(zeros)
203}
204
205/// Reads one block of transform coefficient levels (§9.2).
206///
207/// `max_coeffs` is how many the block holds -- sixteen for a whole four-by-four block, fifteen for
208/// the alternating-current part of one whose direct current term is coded elsewhere, and four for a
209/// 4:2:0 chroma direct-current block. `nc` selects the table, and for a chroma direct-current block
210/// it is −1 rather than a count.
211pub fn residual(b: &mut Bits, nc: i32, max_coeffs: usize) -> Outcome<Block> {
212 let (trailing, total) = res!(coeff_token(b, nc));
213 let mut out = Block { levels: vec![0; max_coeffs], total };
214 if total == 0 {
215 return Ok(out);
216 }
217 if total > max_coeffs {
218 return Err(err!(
219 "A block of {} coefficients codes {} of them as non-zero.", max_coeffs, total;
220 Invalid, Input, Decode));
221 }
222 // The levels, highest frequency first.
223 let mut levels = vec![0i32; total];
224 for level in levels.iter_mut().take(trailing) {
225 *level = if res!(b.u(1)) == 1 { -1 } else { 1 };
226 }
227 // The suffix starts one wide in a block busy enough that most levels will need it.
228 let mut suffix_len: u32 = if total > 10 && trailing < 3 { 1 } else { 0 };
229 for i in trailing..total {
230 let prefix = res!(level_prefix(b));
231 let suffix_size = if prefix == 14 && suffix_len == 0 {
232 4
233 } else if prefix >= 15 {
234 prefix - 3
235 } else {
236 suffix_len
237 };
238 let suffix = if suffix_size > 0 {
239 res!(b.u(suffix_size as usize))
240 } else {
241 0
242 };
243 let mut code = ((prefix.min(15) << suffix_len) + suffix) as i64;
244 if prefix >= 15 && suffix_len == 0 {
245 code += 15;
246 }
247 if prefix >= 16 {
248 code += (1i64 << (prefix - 3)) - 4096;
249 }
250 // The first level after the trailing ones cannot be ±1, since a ±1 there would have been
251 // coded as a trailing one, so its magnitude is offset by one.
252 if i == trailing && trailing < 3 {
253 code += 2;
254 }
255 levels[i] = if code % 2 == 0 {
256 ((code + 2) >> 1) as i32
257 } else {
258 ((-code - 1) >> 1) as i32
259 };
260 // The suffix widens as the levels do. A decoder that leaves this out reads a quiet block
261 // perfectly and a busy one as noise.
262 if suffix_len == 0 {
263 suffix_len = 1;
264 }
265 if levels[i].unsigned_abs() > (3u32 << (suffix_len - 1)) && suffix_len < 6 {
266 suffix_len += 1;
267 }
268 }
269 // Where the zeroes are.
270 let mut zeros_left = if total < max_coeffs {
271 let idx = total - 1;
272 if max_coeffs == 4 {
273 res!(lookup(b, &TOTAL_ZEROS_CHROMA[idx], "total_zeros")) as i32
274 } else {
275 res!(lookup(b, &TOTAL_ZEROS[idx], "total_zeros")) as i32
276 }
277 } else {
278 0
279 };
280 let mut runs = vec![0i32; total];
281 for i in 0..total.saturating_sub(1) {
282 runs[i] = if zeros_left > 0 {
283 let row = (zeros_left.min(7) - 1) as usize;
284 res!(lookup(b, &RUN_BEFORE[row], "run_before")) as i32
285 } else {
286 0
287 };
288 zeros_left -= runs[i];
289 if zeros_left < 0 {
290 return Err(err!(
291 "The runs of zeroes in a block add to more than the block holds.";
292 Invalid, Input, Decode));
293 }
294 }
295 if let Some(last) = runs.last_mut() {
296 *last = zeros_left;
297 }
298 // Lay the levels out (§9.2.4). The levels were read from the *highest* frequency down, and the
299 // runs count the zeroes in front of each, so the walk goes backwards through both and forwards
300 // through the block: the last level read is the one nearest the direct current term.
301 let mut at: i32 = -1;
302 for i in (0..total).rev() {
303 at += runs[i] + 1;
304 if at < 0 || at as usize >= max_coeffs {
305 return Err(err!(
306 "A coefficient lands at position {} of a block of {}.", at, max_coeffs;
307 Invalid, Input, Decode));
308 }
309 out.levels[at as usize] = levels[i];
310 }
311 Ok(out)
312}
313
314/// The `nC` a block reads its `coeff_token` with, from the counts in its two neighbours (§9.2.1).
315///
316/// Where both neighbours are available it is their mean rounded up; where one is, it is that one's;
317/// where neither is, it is nought. This is the single most load-bearing number in CAVLC parsing:
318/// the wrong `nC` picks the wrong column of Table 9-5, which reads a different number of bits, and
319/// every block after it in the slice is then read from the wrong place.
320pub fn nc(left: Option<usize>, above: Option<usize>) -> i32 {
321 match (left, above) {
322 (Some(a), Some(b)) => ((a + b + 1) >> 1) as i32,
323 (Some(a), None) => a as i32,
324 (None, Some(b)) => b as i32,
325 (None, None) => 0,
326 }
327}
328
329#[cfg(test)]
330mod tests {
331 use super::*;
332
333 /// Every codeword one table holds, as a bit string.
334 fn codes(table: &[(u8, u16)]) -> Vec<String> {
335 table.iter()
336 .filter(|(bits, _)| *bits > 0)
337 .map(|(bits, code)| fmt!("{:01$b}", code, *bits as usize))
338 .collect()
339 }
340
341 #[test]
342 fn test_every_table_is_a_prefix_code_01() -> Outcome<()> {
343 // The property that makes a variable-length code readable at all: no codeword is the start
344 // of another, so the decoder always knows where one ends. It is also the property a
345 // mistranscribed table almost always breaks -- a codeword one bit short, or one place out
346 // of its column, collides with a neighbour -- so this catches a bad table without needing
347 // a picture to decode.
348 let mut sets: Vec<(String, Vec<String>)> = Vec::new();
349 for col in 0..6 {
350 let mut all = Vec::new();
351 for t1 in 0..4 {
352 all.extend(codes(&COEFF_TOKEN[col][t1]));
353 }
354 sets.push((fmt!("coeff_token column {}", col), all));
355 }
356 for i in 0..15 {
357 sets.push((fmt!("total_zeros {}", i + 1), codes(&TOTAL_ZEROS[i])));
358 }
359 for i in 0..3 {
360 sets.push((fmt!("chroma total_zeros {}", i + 1), codes(&TOTAL_ZEROS_CHROMA[i])));
361 }
362 for i in 0..7 {
363 sets.push((fmt!("run_before {}", i + 1), codes(&RUN_BEFORE[i])));
364 }
365 for (name, all) in &sets {
366 if all.is_empty() {
367 return Err(err!("{} holds no codewords at all.", name; Test, Missing));
368 }
369 for (i, a) in all.iter().enumerate() {
370 for b in all.iter().skip(i + 1) {
371 if a.starts_with(b.as_str()) || b.starts_with(a.as_str()) {
372 return Err(err!(
373 "{}: the codeword {} is a prefix of {}, so neither can be read.",
374 name, a, b; Test, Invalid));
375 }
376 }
377 }
378 }
379 Ok(())
380 }
381
382 #[test]
383 fn test_the_tables_are_the_published_ones_02() -> Outcome<()> {
384 // Five hundred and fifty-odd codewords, held against the document they came from. A
385 // prefix code that is internally consistent and simply *wrong* -- two columns swapped,
386 // say -- passes every other check here and decodes a plausible picture out of the wrong
387 // bits, so the only worthwhile oracle is the specification itself.
388 //
389 // pdftotext -layout T-REC-H.264-202108.pdf h264.txt
390 // H264_SPEC_TEXT=~/.cache/specs/h264.txt cargo test -p oxedyne_fe2o3_graphics h264
391 let path = match std::env::var("H264_SPEC_TEXT") {
392 Ok(p) => p,
393 Err(_) => {
394 println!(" skipped: set H264_SPEC_TEXT to a text rendering of Rec. ITU-T H.264");
395 return Ok(());
396 },
397 };
398 let text = match std::fs::read_to_string(&path) {
399 Ok(t) => t,
400 Err(e) => {
401 println!(" skipped: {} would not read ({})", path, e);
402 return Ok(());
403 },
404 };
405 // A row of one of these tables is a run of fields separated by two or more spaces; a
406 // *single* space inside a field joins the four-bit groups the document prints a codeword
407 // in. That is the whole of the layout, and it is what makes the tables readable at all.
408 let row = |line: &str| -> Vec<String> {
409 let mut out = Vec::new();
410 let mut field = String::new();
411 let mut gap = 0usize;
412 for c in line.trim().chars() {
413 if c == ' ' {
414 gap += 1;
415 continue;
416 }
417 if gap >= 2 && !field.is_empty() {
418 out.push(field.clone());
419 field.clear();
420 }
421 gap = 0;
422 field.push(c);
423 }
424 if !field.is_empty() {
425 out.push(field);
426 }
427 out
428 };
429 let lines: Vec<&str> = text.lines().collect();
430 // Table 9-5, gathered across the pages it spans.
431 let mut found = 0usize;
432 let mut inside = false;
433 for line in &lines {
434 let trimmed = line.trim();
435 if trimmed.starts_with("Table 9-") {
436 inside = trimmed.starts_with("Table 9-5 – coeff_token mapping");
437 continue;
438 }
439 if !inside {
440 continue;
441 }
442 let f = row(line);
443 if f.len() != 8 {
444 continue;
445 }
446 let (t1, tc) = match (f[0].parse::<usize>(), f[1].parse::<usize>()) {
447 (Ok(a), Ok(b)) if a < 4 && b < 17 => (a, b),
448 _ => continue,
449 };
450 for (col, word) in f[2..].iter().enumerate() {
451 let (bits, code) = COEFF_TOKEN[col][t1][tc];
452 if word == "-" {
453 if bits != 0 {
454 return Err(err!(
455 "Table 9-5 column {} has no codeword for {} trailing ones of {}, and \
456 this decoder holds {} bits.", col, t1, tc, bits; Test, Mismatch));
457 }
458 // A dash is an entry too: the table saying this combination is not coded in
459 // this column, which is as much a fact to be checked as a codeword is.
460 found += 1;
461 continue;
462 }
463 let held = fmt!("{:01$b}", code, bits as usize);
464 if bits == 0 || &held != word {
465 return Err(err!(
466 "Table 9-5 column {}, {} trailing ones of {}: the specification codes {} \
467 and this decoder holds {}.", col, t1, tc, word, held; Test, Mismatch));
468 }
469 found += 1;
470 }
471 }
472 // Six columns, and the sixty-two combinations of trailing ones and total that exist.
473 req!(found, 6 * 62, "Table 9-5 gave up {} codewords, and it holds {}", found, 6 * 62);
474 Ok(())
475 }
476
477 #[test]
478 fn test_the_suffix_widens_as_the_levels_grow_03() -> Outcome<()> {
479 // `suffixLength` climbs each time a level exceeds `3 << (suffixLength − 1)`, and a decoder
480 // that never climbs it reads a quiet block perfectly and a busy one as noise. This is the
481 // smallest statement of the rule: the same bits read with and without it.
482 //
483 // A block of five coefficients, no trailing ones, whose levels climb. What is asserted is
484 // that the decode uses more bits than a fixed one-bit suffix would -- which is only true
485 // if the width grew.
486 //
487 // The bits: coeff_token for nC 0, TotalCoeff 5, TrailingOnes 0, then five levels.
488 let (bits, code) = COEFF_TOKEN[0][0][5];
489 let present = bits > 0;
490 req!(present, true, "the fixture's coeff_token is not in the table");
491 let mut stream: Vec<bool> = (0..bits).map(|i| (code >> (bits - 1 - i)) & 1 == 1).collect();
492 // Five levels, each coded as a prefix of zeroes and a one, with a suffix whose width is
493 // whatever the decoder believes it to be. Feeding a long run of level_prefix zeroes makes
494 // each level large, which is exactly what drives the width up.
495 for _ in 0..5 {
496 for _ in 0..6 {
497 stream.push(false);
498 }
499 stream.push(true);
500 for _ in 0..6 {
501 stream.push(false);
502 }
503 }
504 // total_zeros of nought for a five-coefficient block.
505 let (tzb, tzc) = TOTAL_ZEROS[4][0];
506 for i in 0..tzb {
507 stream.push((tzc >> (tzb - 1 - i)) & 1 == 1);
508 }
509 let mut buf = vec![0u8; stream.len().div_ceil(8) + 4];
510 for (i, bit) in stream.iter().enumerate() {
511 if *bit {
512 buf[i / 8] |= 0x80 >> (i % 8);
513 }
514 }
515 let mut b = Bits::new(&buf);
516 let block = res!(residual(&mut b, 0, 16));
517 req!(block.total, 5);
518 let magnitudes: Vec<i32> = block.levels.iter().filter(|v| **v != 0).map(|v| v.abs())
519 .collect();
520 req!(magnitudes.len(), 5);
521 // With the width fixed at one, every level would decode the same way; with it growing,
522 // they do not.
523 let all_same = magnitudes.iter().all(|m| *m == magnitudes[0]);
524 req!(all_same, false,
525 "every level came out the same magnitude {:?}, so the suffix never widened",
526 magnitudes);
527 Ok(())
528 }
529
530 #[test]
531 fn test_the_neighbour_count_picks_the_table_04() -> Outcome<()> {
532 // `nC` is the mean of the counts above and to the left, and it chooses which of six code
533 // tables reads the next token. The four cases are the whole of it, and the rounding is
534 // *up*: `(a + b + 1) >> 1`, not down. Rounding down picks a lower column for half the
535 // blocks in a picture, and a lower column reads a different number of bits.
536 req!(nc(Some(3), Some(4)), 4, "the mean of three and four rounded down");
537 req!(nc(Some(4), Some(3)), 4);
538 req!(nc(Some(2), Some(2)), 2);
539 req!(nc(Some(5), None), 5);
540 req!(nc(None, Some(5)), 5);
541 req!(nc(None, None), 0, "a block with no neighbours did not read the first table");
542 // And the columns each range picks.
543 req!(token_column(0), 0);
544 req!(token_column(1), 0);
545 req!(token_column(2), 1);
546 req!(token_column(3), 1);
547 req!(token_column(4), 2);
548 req!(token_column(7), 2);
549 req!(token_column(8), 3);
550 req!(token_column(64), 3);
551 req!(token_column(-1), 4, "a 4:2:0 chroma direct-current block read a luma table");
552 req!(token_column(-2), 5);
553 Ok(())
554 }
555
556 #[test]
557 fn test_a_block_of_nothing_costs_one_bit_05() -> Outcome<()> {
558 // The commonest block in a picture is the empty one, and in the first table it is coded as
559 // a single set bit. That is worth asserting on its own, because it is the one codeword
560 // whose length a table shifted by one place changes without breaking the prefix property.
561 let buf = [0b1000_0000u8, 0, 0, 0];
562 let mut b = Bits::new(&buf);
563 let block = res!(residual(&mut b, 0, 16));
564 req!(block.total, 0);
565 req!(b.consumed(), 1, "an empty block cost {} bits and it costs one", b.consumed());
566 req!(block.levels, vec![0i32; 16]);
567 Ok(())
568 }
569}