oxedyne/fe2o3 — fe2o3_graphics/src/h264/cabac.rs

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

44.0 KiB, 106 runs

created by r1870400018:21306, 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 arithmetic entropy coder, and the context variables it codes against.
2	//!
3	//! CABAC is the entropy coder H.264 uses when `entropy_coding_mode_flag` is on, and **947 films in
4	//! the corpus use it** -- every Main and every High one. Nothing about it resembles the code tables
5	//! beside it in [`super::cavlc`]. Every syntax element is a string of binary decisions, and each
6	//! decision is coded against a probability that adapts as the picture is read. Three kinds of
7	//! decision exist: one against a context variable, which is the usual one; one bypassed at even
8	//! odds, for the parts of a value that carry no useful correlation; and one terminating, which is
9	//! how the end of a slice and the raw-sample macroblock type are found.
10	//!
11	//! # What is in here
12	//!
13	//! The decoding engine of §9.3.3.2 and its two published tables, the context variables of §9.3.1.1
14	//! and their initialisation values, and the reading of one block of coefficients (§7.3.5.3.3). The
15	//! binarisation of everything above a block -- macroblock type, coded block pattern, quantisation
16	//! delta, prediction modes -- needs a macroblock's neighbours and so lives in [`super::decode`]
17	//! beside them.
18	//!
19	//! # The initialisation tables, and why they are the dangerous part
20	//!
21	//! A context variable starts from a pair of signed numbers `(m, n)` and the slice's quantisation
22	//! parameter (§9.3.1.1). There are 261 such pairs for an intra 4:2:0 slice, spread over eight
23	//! published tables, and a wrong one produces a picture rather than an error: the decoder stays
24	//! in step with the encoder, reads the same number of bins, and hands back samples that look
25	//! decoded. So they are held to the specification itself rather than to this decoder, entry by
26	//! entry, in this module's tests -- and separately to FFmpeg over the whole library, which is the
27	//! only check that exercises the values rather than merely comparing them.
28	//!
29	//! The engine's own two tables, `rangeTabLPS` (Table 9-44) and the state transitions (Table 9-45),
30	//! are the same numbers HEVC publishes as its Tables 9-46 and 9-47. They are transcribed again here
31	//! rather than borrowed, because the two codecs' entropy layers are independent and a shared table
32	//! would tie one to the other; the tests read both out of the H.264 specification.
33	//!
34	//! # What an intra slice does not need
35	//!
36	//! The specification gives four initialisation columns: one for I and SI slices, and three chosen by
37	//! `cabac_init_idc` for P, SP and B. Only the first is here. So are only the block categories a
38	//! 4:2:0 picture has -- 0 to 5 of Table 9-42 -- which is why Tables 9-14, 9-15, 9-22, 9-23 and
39	//! 9-25 to 9-33 are absent: they serve motion vectors, field coding, and the Cb and Cr blocks of a
40	//! 4:4:4 picture. An 8x8 luma block in 4:2:0 carries no `coded_block_flag` at all (§7.3.5.3.3), so
41	//! Table 9-33 is not needed either.
42	//!
43	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
44	//! Anthropic Claude
45
46	use oxedyne_fe2o3_core::prelude::*;
47
48	/// The probability state a context variable is in: an index 0 to 62, and the more probable symbol.
49	///
50	/// One byte rather than two fields, because a slice carries over a thousand of these and they are
51	/// initialised together at the head of every slice.
52	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
53	pub struct Ctx(u8);
54
55	impl Ctx {
56
57	/// The state a context starts in, from its initialisation pair and the slice's quantisation
58	/// parameter (§9.3.1.1, equations 9-5 and 9-6).
59	///
60	/// The clamp on the quantisation parameter is the specification's own, and the clamp on
61	/// `preCtxState` to 1..126 is what keeps the state index inside the 64 rows the probability
62	/// tables have.
63	pub fn start(m: i8, n: i8, qp: i32) -> Self {
64	let q = qp.clamp(0, 51);
65	let pre = (((m as i32 * q) >> 4) + n as i32).clamp(1, 126);
66	if pre <= 63 {
67	// The less probable symbol is a one.
68	Self(((63 - pre) as u8) << 1)
69	} else {
70	Self((((pre - 64) as u8) << 1) \| 1)
71	}
72	}
73
74	/// The probability state index, 0 to 62.
75	fn state(self) -> usize {
76	(self.0 >> 1) as usize
77	}
78
79	/// The more probable symbol, 0 or 1.
80	fn mps(self) -> u32 {
81	(self.0 & 1) as u32
82	}
83	}
84
85	// How the range is narrowed for the less probable symbol, by state and by the two bits the current
86	// range contributes (§9.3.3.2.1, Table 9-44).
87	const LPS: [[u8; 4]; 64] = [
88	[128, 176, 208, 240], [128, 167, 197, 227], [128, 158, 187, 216], [123, 150, 178, 205],
89	[116, 142, 169, 195], [111, 135, 160, 185], [105, 128, 152, 175], [100, 122, 144, 166],
90	[95, 116, 137, 158], [90, 110, 130, 150], [85, 104, 123, 142], [81, 99, 117, 135],
91	[77, 94, 111, 128], [73, 89, 105, 122], [69, 85, 100, 116], [66, 80, 95, 110],
92	[62, 76, 90, 104], [59, 72, 86, 99], [56, 69, 81, 94], [53, 65, 77, 89],
93	[51, 62, 73, 85], [48, 59, 69, 80], [46, 56, 66, 76], [43, 53, 63, 72],
94	[41, 50, 59, 69], [39, 48, 56, 65], [37, 45, 54, 62], [35, 43, 51, 59],
95	[33, 41, 48, 56], [32, 39, 46, 53], [30, 37, 43, 50], [29, 35, 41, 48],
96	[27, 33, 39, 45], [26, 31, 37, 43], [24, 30, 35, 41], [23, 28, 33, 39],
97	[22, 27, 32, 37], [21, 26, 30, 35], [20, 24, 29, 33], [19, 23, 27, 31],
98	[18, 22, 26, 30], [17, 21, 25, 28], [16, 20, 23, 27], [15, 19, 22, 25],
99	[14, 18, 21, 24], [14, 17, 20, 23], [13, 16, 19, 22], [12, 15, 18, 21],
100	[12, 14, 17, 20], [11, 14, 16, 19], [11, 13, 15, 18], [10, 12, 15, 17],
101	[10, 12, 14, 16], [9, 11, 13, 15], [9, 11, 12, 14], [8, 10, 12, 14],
102	[8, 9, 11, 13], [7, 9, 11, 12], [7, 9, 10, 12], [7, 8, 10, 11],
103	[6, 8, 9, 11], [6, 7, 9, 10], [6, 7, 8, 9], [2, 2, 2, 2],
104	];
105
106	// The state to move to after decoding the more probable symbol (Table 9-45, transIdxMPS).
107	const NEXT_MPS: [u8; 64] = [
108	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
109	17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
110	33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
111	49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 62, 63,
112	];
113
114	// The state to move to after decoding the less probable symbol (Table 9-45, transIdxLPS).
115	const NEXT_LPS: [u8; 64] = [
116	0, 0, 1, 2, 2, 4, 4, 5, 6, 7, 8, 9, 9, 11, 11, 12,
117	13, 13, 15, 15, 16, 16, 18, 18, 19, 19, 21, 21, 22, 22, 23, 24,
118	24, 25, 26, 26, 27, 27, 28, 29, 29, 30, 30, 30, 31, 32, 32, 33,
119	33, 33, 34, 34, 35, 35, 35, 36, 36, 36, 37, 37, 37, 38, 38, 63,
120	];
121
122	/// The arithmetic decoder itself (§9.3.3.2).
123	///
124	/// It reads bits and answers questions of the form "was the next bin a one?", where the odds are
125	/// carried by whichever context variable the syntax says applies.
126	pub struct Cabac<'a> {
127	buf: &'a [u8], // from the first byte of the slice's entropy-coded data
128	at: usize, // the next byte to be taken into the window
129	range: u32, // codIRange, the current interval's width
130	offset: u32, // codIOffset, shifted up by bits
131	bits: i32, // bits of the window pre-read and not yet part of codIOffset
132	}
133
134	impl<'a> Cabac<'a> {
135
136	/// Starts the decoder at the first byte of a slice's entropy-coded data (§9.3.1.2).
137	///
138	/// The specification reads nine bits into `codIOffset` and compares it against the interval
139	/// directly, reading one more bit at every renormalisation. This decoder keeps those bits
140	/// pre-read instead -- `offset` holds `codIOffset` shifted up by `bits`, with `bits` more of
141	/// the stream already in the low end -- so a renormalisation is a subtraction from `bits` rather
142	/// than a read, and the two bytes go in whole.
143	pub fn new(buf: &'a [u8]) -> Outcome<Self> {
144	if buf.len() < 2 {
145	return Err(err!(
146	"An arithmetic decoder was started on {} bytes, and it reads two before it answers \
147	anything.", buf.len();
148	Invalid, Input, Decode));
149	}
150	Ok(Self {
151	buf,
152	at: 2,
153	range: 510,
154	offset: ((buf[0] as u32) << 8) \| (buf[1] as u32),
155	bits: 7,
156	})
157	}
158
159	/// The next byte, or zeroes past the end.
160	///
161	/// A decoder is allowed to read a little past the last byte of a slice -- the final bins are
162	/// coded against bits the encoder never had to write -- so running out is not a fault. Reading
163	/// far past it would be, and that is caught by the terminating bin, which says where the data
164	/// ends.
165	fn byte(&mut self) -> u32 {
166	let b = self.buf.get(self.at).copied().unwrap_or(0) as u32;
167	self.at += 1;
168	b
169	}
170
171	/// Keeps the interval at nine bits or more (§9.3.3.2.2).
172	fn renormalise(&mut self) {
173	while self.range < 256 {
174	self.range <<= 1;
175	self.bits -= 1;
176	if self.bits < 0 {
177	self.offset = (self.offset << 8) \| self.byte();
178	self.bits += 8;
179	}
180	}
181	}
182
183	/// One bin against a context, which is then moved on (§9.3.3.2.1).
184	pub fn bin(&mut self, ctx: &mut Ctx) -> u32 {
185	let state = ctx.state();
186	let lps = LPS[state][((self.range >> 6) & 3) as usize] as u32;
187	self.range -= lps;
188	let value;
189	if self.offset >= (self.range << self.bits) {
190	// The less probable symbol.
191	self.offset -= self.range << self.bits;
192	value = 1 - ctx.mps();
193	self.range = lps;
194	if state == 0 {
195	// State nought is where the two symbols are equally likely, so being wrong there
196	// exchanges which one is called the more probable.
197	ctx.0 ^= 1;
198	}
199	ctx.0 = (NEXT_LPS[state] << 1) \| (ctx.0 & 1);
200	} else {
201	value = ctx.mps();
202	ctx.0 = (NEXT_MPS[state] << 1) \| (ctx.0 & 1);
203	}
204	self.renormalise();
205	value
206	}
207
208	/// One bin at even odds, with no context to move on (§9.3.3.2.3).
209	pub fn bypass(&mut self) -> u32 {
210	self.bits -= 1;
211	if self.bits < 0 {
212	self.offset = (self.offset << 8) \| self.byte();
213	self.bits += 8;
214	}
215	let scaled = self.range << self.bits;
216	if self.offset >= scaled {
217	self.offset -= scaled;
218	1
219	} else {
220	0
221	}
222	}
223
224	/// `n` bins at even odds, most significant first.
225	pub fn bypass_bits(&mut self, n: usize) -> u32 {
226	let mut v = 0u32;
227	for _ in 0..n.min(32) {
228	v = (v << 1) \| self.bypass();
229	}
230	v
231	}
232
233	/// The bin that says whether this is the end (§9.3.3.2.4).
234	///
235	/// One at the end of a slice, and one for the bin of `mb_type` that names the raw-sample
236	/// macroblock. Where it says the end has come, the interval is not renormalised, which is
237	/// what leaves the bitstream pointer where the next syntax begins.
238	pub fn terminate(&mut self) -> u32 {
239	self.range -= 2;
240	if self.offset >= (self.range << self.bits) {
241	1
242	} else {
243	self.renormalise();
244	0
245	}
246	}
247
248	/// How many bits of the buffer the decoder has taken into `codIOffset`.
249	///
250	/// This is where the bitstream pointer sits, which a raw-sample macroblock needs: its samples
251	/// begin at the next byte boundary after the terminating bin that named it.
252	pub fn consumed_bits(&self) -> usize {
253	(self.at * 8).saturating_sub(self.bits.max(0) as usize)
254	}
255
256	/// The interval's current width, for the tests that assert it stays in range.
257	#[cfg(test)]
258	fn width(&self) -> u32 {
259	self.range
260	}
261	}
262
263	// ------------------------------------------------------- the context variables themselves
264
265	pub const CONTEXTS: usize = 1024; // ctxIdx runs 0 to 1023 (§9.3.3.1)
266
267	// The ctxIdx of end_of_slice_flag, and of the mb_type bin that names a raw-sample macroblock. It
268	// carries no context variable at all: both are decoded by the terminating process.
269	pub const TERMINATE: usize = 276;
270
271	/// The `ctxIdxOffset` of each syntax element an intra 4:2:0 slice codes (Table 9-34).
272	pub mod offset {
273	pub const MB_TYPE: usize = 3; // mb_type in an I slice
274	pub const MB_QP_DELTA: usize = 60;
275	pub const CHROMA_PRED: usize = 64; // intra_chroma_pred_mode
276	pub const PREV_PRED: usize = 68; // prev_intra4x4_pred_mode_flag, prev_intra8x8_pred_mode_flag
277	pub const REM_PRED: usize = 69; // rem_intra4x4_pred_mode, rem_intra8x8_pred_mode
278	pub const CBP_LUMA: usize = 73; // the luma part of coded_block_pattern
279	pub const CBP_CHROMA: usize = 77; // its chroma part
280	pub const TRANSFORM_8X8: usize = 399;
281	}
282
283	// The initialisation pairs an intra slice's context variables start from, as runs of
284	// (first ctxIdx, table number within clause 9, [(m, n), ...]).
285	//
286	// The table number is kept so that the transcription can be checked against the document rather
287	// than against itself; this module's tests do exactly that where a text rendering of the
288	// specification is to hand. Each run is the whole of that table's I-slice column, even where an
289	// intra 4:2:0 decoder reads only part of it -- mb_field_decoding_flag at 70 to 72 is never coded
290	// in a frame-only stream, and significant_coeff_flag stops at 151 rather than 165 -- because a
291	// partial run would be a second place to make a mistake.
292	pub const INIT_I: [(usize, usize, &[(i8, i8)]); 8] = [
293	// Table 9-12 gives ctxIdx 0 to 10 and has no cabac_init_idc column at all; 0 to 2 belong to
294	// mb_type in an SI slice, so an I slice starts at 3.
295	(3, 12, &[
296	(20, -15), (2, 54), (3, 74), (-28, 127),
297	(-23, 104), (-6, 53), (-1, 54), (7, 51),
298	]),
299	// Table 9-17: mb_qp_delta at 60 to 63, intra_chroma_pred_mode at 64 to 67, and the two
300	// prediction mode elements at 68 and 69.
301	(60, 17, &[
302	(0, 41), (0, 63), (0, 63), (0, 63), (-9, 83),
303	(4, 86), (0, 97), (-7, 72), (13, 41), (3, 62),
304	]),
305	// Table 9-18: mb_field_decoding_flag, coded_block_pattern and coded_block_flag.
306	(70, 18, &[
307	(0, 11), (1, 55), (0, 69), (-17, 127), (-13, 102),
308	(0, 82), (-7, 74), (-21, 107), (-27, 127), (-31, 127),
309	(-24, 127), (-18, 95), (-27, 127), (-21, 114), (-30, 127),
310	(-17, 123), (-12, 115), (-16, 122), (-11, 115), (-12, 63),
311	(-2, 68), (-15, 84), (-13, 104), (-3, 70), (-8, 93),
312	(-10, 90), (-30, 127), (-1, 74), (-6, 97), (-7, 91),
313	(-20, 127), (-4, 56), (-5, 82), (-7, 76), (-22, 125),
314	]),
315	// Table 9-19: significant_coeff_flag for a frame-coded block of category below five.
316	(105, 19, &[
317	(-7, 93), (-11, 87), (-3, 77), (-5, 71), (-4, 63),
318	(-4, 68), (-12, 84), (-7, 62), (-7, 65), (8, 61),
319	(5, 56), (-2, 66), (1, 64), (0, 61), (-2, 78),
320	(1, 50), (7, 52), (10, 35), (0, 44), (11, 38),
321	(1, 45), (0, 46), (5, 44), (31, 17), (1, 51),
322	(7, 50), (28, 19), (16, 33), (14, 62), (-13, 108),
323	(-15, 100), (-13, 101), (-13, 91), (-12, 94), (-10, 88),
324	(-16, 84), (-10, 86), (-7, 83), (-13, 87), (-19, 94),
325	(1, 70), (0, 72), (-5, 74), (18, 59), (-8, 102),
326	(-15, 100), (0, 95), (-4, 75), (2, 72), (-11, 75),
327	(-3, 71), (15, 46), (-13, 69), (0, 62), (0, 65),
328	(21, 37), (-15, 72), (9, 57), (16, 54), (0, 62),
329	(12, 72),
330	]),
331	// Table 9-20: last_significant_coeff_flag for the same blocks.
332	(166, 20, &[
333	(24, 0), (15, 9), (8, 25), (13, 18), (15, 9),
334	(13, 19), (10, 37), (12, 18), (6, 29), (20, 33),
335	(15, 30), (4, 45), (1, 58), (0, 62), (7, 61),
336	(12, 38), (11, 45), (15, 39), (11, 42), (13, 44),
337	(16, 45), (12, 41), (10, 49), (30, 34), (18, 42),
338	(10, 55), (17, 51), (17, 46), (0, 89), (26, -19),
339	(22, -17), (26, -17), (30, -25), (28, -20), (33, -23),
340	(37, -27), (33, -23), (40, -28), (38, -17), (33, -11),
341	(40, -15), (41, -6), (38, 1), (41, 17), (30, -6),
342	(27, 3), (26, 22), (37, -16), (35, -4), (38, -8),
343	(38, -3), (37, 3), (38, 5), (42, 0), (35, 16),
344	(39, 22), (14, 48), (27, 37), (21, 60), (12, 68),
345	(2, 97),
346	]),
347	// Table 9-21: coeff_abs_level_minus1 for the same blocks.
348	(227, 21, &[
349	(-3, 71), (-6, 42), (-5, 50), (-3, 54), (-2, 62),
350	(0, 58), (1, 63), (-2, 72), (-1, 74), (-9, 91),
351	(-5, 67), (-5, 27), (-3, 39), (-2, 44), (0, 46),
352	(-16, 64), (-8, 68), (-10, 78), (-6, 77), (-10, 86),
353	(-12, 92), (-15, 55), (-10, 60), (-6, 62), (-4, 65),
354	(-12, 73), (-8, 76), (-7, 80), (-9, 88), (-17, 110),
355	(-11, 97), (-20, 84), (-11, 79), (-6, 73), (-4, 74),
356	(-13, 86), (-13, 96), (-11, 97), (-19, 117), (-8, 78),
357	(-5, 33), (-4, 48), (-2, 53), (-3, 62), (-13, 71),
358	(-10, 79), (-12, 86), (-13, 90), (-14, 97),
359	]),
360	// Table 9-16 gives transform_size_8x8_flag its own three, and its I-slice row is the only one
361	// of the four columns that is not "na" for 54 to 59.
362	(399, 16, &[
363	(31, 21), (31, 31), (25, 50),
364	]),
365	// Table 9-24: the residual of an eight-by-eight luma block -- significance at 402 to 416, the
366	// last position at 417 to 425, the levels at 426 to 435. Its column is headed "I slices" rather
367	// than "I and SI slices", since an SI slice has no eight-by-eight transform.
368	(402, 24, &[
369	(-17, 120), (-20, 112), (-18, 114), (-11, 85), (-15, 92),
370	(-14, 89), (-26, 71), (-15, 81), (-14, 80), (0, 68),
371	(-14, 70), (-24, 56), (-23, 68), (-24, 50), (-11, 74),
372	(23, -13), (26, -13), (40, -15), (49, -14), (44, 3),
373	(45, 6), (44, 34), (33, 54), (19, 82), (-3, 75),
374	(-1, 23), (1, 34), (1, 43), (0, 54), (-2, 55),
375	(0, 61), (1, 64), (0, 68), (-9, 92),
376	]),
377	];
378
379	/// Every context variable a slice carries, and which of them the initialisation tables reached.
380	///
381	/// One flat array indexed by `ctxIdx`, because that is how the syntax names them: a context is
382	/// `ctxIdxOffset` plus an increment worked out from the neighbours, and there is nothing to be
383	/// gained by grouping them.
384	#[derive(Clone)]
385	pub struct Contexts {
386	v: Vec<Ctx>,
387	known: Vec<bool>, // do the intra tables carry an initialisation value for it?
388	}
389
390	impl Contexts {
391
392	/// The state every context an intra slice uses starts in, given that slice's quantisation
393	/// parameter (§9.3.1.1).
394	pub fn start(qp: i32) -> Self {
395	let mut v = vec![Ctx(0); CONTEXTS];
396	let mut known = vec![false; CONTEXTS];
397	for (first, _table, values) in INIT_I {
398	for (i, (m, n)) in values.iter().enumerate() {
399	v[first + i] = Ctx::start(m, n, qp);
400	known[first + i] = true;
401	}
402	}
403	Self { v, known }
404	}
405
406	/// One context variable, by the `ctxIdx` the syntax names.
407	///
408	/// A `ctxIdx` the intra tables never initialised is a fault in whoever worked out the increment,
409	/// not a thing to be read quietly: a decoder that codes a bin against an uninitialised context
410	/// produces a picture rather than an error, and a picture that is subtly wrong is the hardest
411	/// kind of fault to find. So it is refused, and the message says which index.
412	pub fn at(&mut self, ctx_idx: usize) -> Outcome<&mut Ctx> {
413	match self.known.get(ctx_idx) {
414	Some(true) => Ok(&mut self.v[ctx_idx]),
415	_ => Err(err!(
416	"A bin was to be coded against context {}, and the intra initialisation tables of \
417	clause 9.3.1.1 do not carry it. Either the context increment is wrong or the stream \
418	codes something this decoder does not read.", ctx_idx;
419	Invalid, Input, Decode)),
420	}
421	}
422
423	pub fn bin(&mut self, c: &mut Cabac, ctx_idx: usize) -> Outcome<u32> {
424	let ctx = res!(self.at(ctx_idx));
425	Ok(c.bin(ctx))
426	}
427	}
428
429	// ------------------------------------------------------------------ a block of coefficients
430
431	/// Which family of block a residual belongs to, which chooses its context variables (Table 9-42).
432	///
433	/// Only the six a 4:2:0 picture has. Categories 6 to 13 are the Cb and Cr blocks of a 4:4:4 picture,
434	/// which this decoder refuses where the chroma format is read.
435	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
436	pub enum Cat {
437	LumaDc, // sixteen direct current terms of a macroblock predicted whole, ctxBlockCat 0
438	LumaAc, // fifteen alternating current terms of one of its blocks (1)
439	Luma4x4, // a whole four-by-four luma block (2)
440	ChromaDc, // four direct current terms of one colour difference component (3)
441	ChromaAc, // fifteen alternating current terms of one of its blocks (4)
442	Luma8x8, // a whole eight-by-eight luma block (5)
443	}
444
445	impl Cat {
446
447	/// The `ctxBlockCat` the specification numbers this category with.
448	pub fn number(self) -> usize {
449	match self {
450	Self::LumaDc => 0,
451	Self::LumaAc => 1,
452	Self::Luma4x4 => 2,
453	Self::ChromaDc => 3,
454	Self::ChromaAc => 4,
455	Self::Luma8x8 => 5,
456	}
457	}
458
459	/// How many coefficients the block holds, `maxNumCoeff` (Table 9-42).
460	///
461	/// For a chroma direct current block this is `4 * NumC8x8`, which in 4:2:0 is four.
462	pub fn coeffs(self) -> usize {
463	match self {
464	Self::LumaDc \| Self::Luma4x4 => 16,
465	Self::LumaAc \| Self::ChromaAc => 15,
466	Self::ChromaDc => 4,
467	Self::Luma8x8 => 64,
468	}
469	}
470
471	/// Where this category's `coded_block_flag` contexts begin, offset included (Tables 9-34, 9-40).
472	pub fn cbf_base(self) -> usize {
473	match self {
474	Self::LumaDc => 85,
475	Self::LumaAc => 89,
476	Self::Luma4x4 => 93,
477	Self::ChromaDc => 97,
478	Self::ChromaAc => 101,
479	// Never read in 4:2:0: an eight-by-eight block's flag is not coded (§7.3.5.3.3).
480	Self::Luma8x8 => 1012,
481	}
482	}
483
484	/// Where its `significant_coeff_flag` contexts begin, for a frame-coded block.
485	pub fn sig_base(self) -> usize {
486	match self {
487	Self::LumaDc => 105,
488	Self::LumaAc => 120,
489	Self::Luma4x4 => 134,
490	Self::ChromaDc => 149,
491	Self::ChromaAc => 152,
492	Self::Luma8x8 => 402,
493	}
494	}
495
496	/// Where its `last_significant_coeff_flag` contexts begin.
497	pub fn last_base(self) -> usize {
498	match self {
499	Self::LumaDc => 166,
500	Self::LumaAc => 181,
501	Self::Luma4x4 => 195,
502	Self::ChromaDc => 210,
503	Self::ChromaAc => 213,
504	Self::Luma8x8 => 417,
505	}
506	}
507
508	/// Where its `coeff_abs_level_minus1` contexts begin.
509	pub fn level_base(self) -> usize {
510	match self {
511	Self::LumaDc => 227,
512	Self::LumaAc => 237,
513	Self::Luma4x4 => 247,
514	Self::ChromaDc => 257,
515	Self::ChromaAc => 266,
516	Self::Luma8x8 => 426,
517	}
518	}
519
520	/// The context increment for the significance of the coefficient at a scan position (§9.3.3.1.3).
521	fn sig_inc(self, at: usize) -> usize {
522	match self {
523	// A chroma direct current block's four positions share three contexts.
524	Self::ChromaDc => at.min(2),
525	Self::Luma8x8 => SIG_8X8[at.min(62)] as usize,
526	_ => at,
527	}
528	}
529
530	/// The same for whether that coefficient is the last one.
531	fn last_inc(self, at: usize) -> usize {
532	match self {
533	Self::ChromaDc => at.min(2),
534	Self::Luma8x8 => LAST_8X8[at.min(62)] as usize,
535	_ => at,
536	}
537	}
538	}
539
540	// The context increment for the significance of each scan position of a frame-coded eight-by-eight
541	// block (Table 9-43, the first of its three columns). Sixty-four positions share fifteen contexts,
542	// and not in scan order: the mapping is a published table because it groups positions by how likely
543	// a coefficient there is, which the scan does not.
544	pub const SIG_8X8: [u8; 63] = [
545	0, 1, 2, 3, 4, 5, 5, 4,
546	4, 3, 3, 4, 4, 4, 5, 5,
547	4, 4, 4, 4, 3, 3, 6, 7,
548	7, 7, 8, 9, 10, 9, 8, 7,
549	7, 6, 11, 12, 13, 11, 6, 7,
550	8, 9, 14, 10, 9, 8, 6, 11,
551	12, 13, 11, 6, 9, 14, 10, 9,
552	11, 12, 13, 11, 14, 10, 12,
553	];
554
555	// The same for whether the coefficient there is the last one (Table 9-43, the third column).
556	pub const LAST_8X8: [u8; 63] = [
557	0, 1, 1, 1, 1, 1, 1, 1,
558	1, 1, 1, 1, 1, 1, 1, 1,
559	2, 2, 2, 2, 2, 2, 2, 2,
560	2, 2, 2, 2, 2, 2, 2, 2,
561	3, 3, 3, 3, 3, 3, 3, 3,
562	4, 4, 4, 4, 4, 4, 4, 4,
563	5, 5, 5, 5, 6, 6, 6, 6,
564	7, 7, 7, 7, 8, 8, 8,
565	];
566
567	// How far the unary prefix of a coefficient's magnitude runs before the Exp-Golomb suffix begins
568	// (Table 9-34, uCoff of the UEG0 binarisation).
569	const LEVEL_PREFIX_MAX: usize = 14;
570
571	/// Reads one block of transform coefficient levels (§7.3.5.3.3).
572	///
573	/// `cbf_inc` is the context increment for `coded_block_flag`, worked out from the neighbouring
574	/// blocks by the caller; `None` says the flag is not coded at all and is inferred to be one, which
575	/// is what an eight-by-eight luma block in 4:2:0 does. `levels` is filled in scan order and must be
576	/// as long as the category says the block is.
577	///
578	/// Whether the block holds anything is what the neighbours of the next block ask about.
579	pub fn residual(c: &mut Cabac, x: &mut Contexts, cat: Cat, cbf_inc: Option<u32>, levels: &mut [i32])
580	-> Outcome<bool>
581	{
582	if levels.len() != cat.coeffs() {
583	return Err(err!(
584	"A {:?} block was read into {} coefficients, and Table 9-42 says it holds {}.",
585	cat, levels.len(), cat.coeffs(); Bug));
586	}
587	for v in levels.iter_mut() {
588	*v = 0;
589	}
590	if let Some(inc) = cbf_inc {
591	if res!(x.bin(c, cat.cbf_base() + inc as usize)) == 0 {
592	return Ok(false);
593	}
594	}
595	// The significance map, forwards from the direct current term. A set last flag says the block
596	// ends there, and the coefficient at that position is significant without a flag of its own.
597	let n = levels.len();
598	let mut sig = vec![false; n];
599	let mut num = n;
600	let mut at = 0usize;
601	while at + 1 < num {
602	if res!(x.bin(c, cat.sig_base() + cat.sig_inc(at))) == 1 {
603	sig[at] = true;
604	if res!(x.bin(c, cat.last_base() + cat.last_inc(at))) == 1 {
605	num = at + 1;
606	}
607	}
608	at += 1;
609	}
610	sig[num - 1] = true;
611	// The magnitudes, backwards from the last significant position. The order matters: the context
612	// a magnitude is coded against counts how many magnitudes of one and how many above one have
613	// already been read in this block, so reading them forwards gives every one the wrong context.
614	let mut ones = 0usize;
615	let mut bigger = 0usize;
616	for k in (0..num).rev() {
617	if !sig[k] {
618	continue;
619	}
620	let magnitude = res!(level(c, x, cat, ones, bigger));
621	if magnitude == 1 {
622	ones += 1;
623	} else {
624	bigger += 1;
625	}
626	levels[k] = if c.bypass() == 1 {
627	-(magnitude as i32)
628	} else {
629	magnitude as i32
630	};
631	}
632	Ok(true)
633	}
634
635	/// Reads one coefficient's magnitude: `coeff_abs_level_minus1` plus one (§9.3.2.3, §9.3.3.1.3).
636	///
637	/// A truncated unary prefix of up to fourteen bins, and past that an Exp-Golomb suffix read at even
638	/// odds. `ones` and `bigger` are how many magnitudes of exactly one and of more than one have been
639	/// read in this block already, which is the whole of what chooses the contexts.
640	fn level(c: &mut Cabac, x: &mut Contexts, cat: Cat, ones: usize, bigger: usize) -> Outcome<u32> {
641	let base = cat.level_base();
642	let first = if bigger != 0 { 0 } else { 4.min(1 + ones) };
643	if res!(x.bin(c, base + first)) == 0 {
644	return Ok(1);
645	}
646	// Every bin after the first shares one context, since maxBinIdxCtx is one.
647	let rest = base + 5 + (4 - usize::from(cat == Cat::ChromaDc)).min(bigger);
648	let mut prefix = 1usize;
649	while prefix < LEVEL_PREFIX_MAX && res!(x.bin(c, rest)) == 1 {
650	prefix += 1;
651	}
652	if prefix < LEVEL_PREFIX_MAX {
653	return Ok(prefix as u32 + 1);
654	}
655	// The suffix: a run of ones says how wide the remainder is, then the remainder itself.
656	let mut k = 0u32;
657	let mut suffix = 0u32;
658	while c.bypass() == 1 {
659	suffix += 1 << k;
660	k += 1;
661	if k > 20 {
662	return Err(err!(
663	"A coefficient's Exp-Golomb suffix ran past 20 bins, so the arithmetic decoder is no \
664	longer reading the syntax where it is.";
665	Invalid, Input, Decode));
666	}
667	}
668	suffix += c.bypass_bits(k as usize);
669	Ok(LEVEL_PREFIX_MAX as u32 + suffix + 1)
670	}
671
672	#[cfg(test)]
673	mod tests {
674	use super::*;
675
676	#[test]
677	fn test_every_context_starts_in_a_state_that_exists_01() -> Outcome<()> {
678	// Two hundred and sixty-one initialisation pairs against every quantisation parameter a
679	// slice may carry. The state they yield indexes a table of sixty-four rows, and the
680	// arithmetic that produces it is the specification's own -- so an index outside it is a
681	// transcription error, and trying them all is the only way to find one before a picture
682	// exists.
683	let mut pairs = 0usize;
684	for (first, _table, values) in INIT_I {
685	for (i, (m, n)) in values.iter().enumerate() {
686	pairs += 1;
687	for qp in 0..=51i32 {
688	let ctx = Ctx::start(m, n, qp);
689	let state = ctx.state();
690	if state > 62 {
691	return Err(err!(
692	"Context {} starts from ({}, {}) and at a quantisation parameter of {} \
693	that is state {}, where 62 is the highest.",
694	first + i, m, n, qp, state; Test, Invalid));
695	}
696	}
697	}
698	}
699	req!(pairs, 261, "the intra initialisation tables hold {} pairs and clause 9 gives 261",
700	pairs);
701	Ok(())
702	}
703
704	#[test]
705	fn test_the_interval_is_renormalised_after_every_bin_02() -> Outcome<()> {
706	// The invariant the whole arithmetic decoder rests on: the interval is at least 256 and at
707	// most 510 whenever a bin has been answered. A renormalisation that stops one shift short
708	// decodes plausible rubbish rather than failing, which is exactly the sort of fault that
709	// survives until a picture comes out wrong, so it is asserted directly.
710	//
711	// The data is a run of bytes from a small linear congruential sequence: it is not a coded
712	// slice and does not have to be, since the invariant holds over any input at all.
713	let mut seed = 0x2545_f491_4f6c_dd1du64;
714	let mut data = Vec::with_capacity(4096);
715	for _ in 0..4096 {
716	seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
717	data.push((seed >> 33) as u8);
718	}
719	let mut c = res!(Cabac::new(&data));
720	let mut x = Contexts::start(26);
721	let mut ones = 0usize;
722	for i in 0..20_000usize {
723	match i % 8 {
724	7 => {
725	// The terminating bin, which a slice asks once a macroblock. On random bytes it
726	// will eventually say the data has ended.
727	if c.terminate() == 1 {
728	break;
729	}
730	},
731	6 => {
732	ones += c.bypass() as usize;
733	},
734	k => {
735	ones += res!(x.bin(&mut c, 105 + k)) as usize;
736	},
737	}
738	let w = c.width();
739	if w < 256 \|\| w > 510 {
740	return Err(err!(
741	"After {} bins the interval is {}, outside 256 to 510.", i + 1, w;
742	Test, Invalid));
743	}
744	}
745	// A decoder that answered every bin the same way would satisfy the invariant above and be
746	// useless, so the answers are required to be mixed.
747	if ones == 0 {
748	return Err(err!("Not one bin came back as a one."; Test, Invalid));
749	}
750	Ok(())
751	}
752
753	#[test]
754	fn test_an_uninitialised_context_is_refused_03() -> Outcome<()> {
755	// The guard against a wrong context increment. Every ctxIdx an intra 4:2:0 slice may name is
756	// initialised; anything else is a fault in the increment, and reading it would produce a
757	// picture rather than an error.
758	let mut x = Contexts::start(26);
759	req!(x.at(3).is_ok(), true, "mb_type's first context is not initialised");
760	req!(x.at(435).is_ok(), true, "the last of Table 9-24 is not initialised");
761	let past = x.at(436).is_err();
762	req!(past, true, "a context the intra tables do not carry was handed out");
763	let motion = x.at(40).is_err();
764	req!(motion, true, "a motion vector context was handed out to an intra slice");
765	let outside = x.at(CONTEXTS).is_err();
766	req!(outside, true, "a context past the 1024 the syntax numbers was handed out");
767	Ok(())
768	}
769
770	#[test]
771	fn test_a_decoder_needs_two_bytes_to_begin_04() -> Outcome<()> {
772	req!(Cabac::new(&[0x40]).is_err(), true,
773	"A decoder started on one byte, and it reads nine bits before answering anything.");
774	Ok(())
775	}
776
777	#[test]
778	fn test_the_scan_position_tables_cover_every_position_05() -> Outcome<()> {
779	// Table 9-43 maps 63 scan positions of an eight-by-eight block onto contexts, and the counts
780	// are what the initialisation tables were sized against: fifteen significance contexts at
781	// 402 to 416 and nine last-position ones at 417 to 425. A mapping that reached further would
782	// read a context belonging to the next syntax element.
783	let sig_top = SIG_8X8.iter().copied().max().unwrap_or(0);
784	req!(sig_top as usize, 14, "significance reaches context {} and Table 9-24 gives 15 of them",
785	sig_top);
786	let last_top = LAST_8X8.iter().copied().max().unwrap_or(0);
787	req!(last_top as usize, 8, "the last position reaches context {} and there are 9", last_top);
788	// Every context in each range is used by some position, which a table with a value missing
789	// would break.
790	for want in 0..=14u8 {
791	let used = SIG_8X8.contains(&want);
792	req!(used, true, "no scan position maps to significance context {}", want);
793	}
794	for want in 0..=8u8 {
795	let used = LAST_8X8.contains(&want);
796	req!(used, true, "no scan position maps to last-position context {}", want);
797	}
798	// The last-position mapping rises without ever falling, which is what makes it a mapping
799	// from frequency band to context; a transposed row would break it.
800	for i in 1..LAST_8X8.len() {
801	let rising = LAST_8X8[i] >= LAST_8X8[i - 1];
802	req!(rising, true, "the last-position mapping falls at scan position {}", i);
803	}
804	Ok(())
805	}
806
807	#[test]
808	fn test_no_two_categories_share_a_context_06() -> Outcome<()> {
809	// Table 9-40's offsets are what keeps six block categories out of each other's context
810	// variables, and an offset one place out is a fault that changes no bin count: the decoder
811	// stays in step and adapts the wrong probabilities. So the ranges are laid out and checked
812	// for overlap.
813	//
814	// The ranges each category actually reaches, given the increments of §9.3.3.1.3.
815	let cats = [Cat::LumaDc, Cat::LumaAc, Cat::Luma4x4, Cat::ChromaDc, Cat::ChromaAc];
816	let mut spans: Vec<(String, usize, usize)> = Vec::new();
817	for cat in cats {
818	let n = cat.coeffs();
819	let sig_top = (0..n - 1).map(\|i\| cat.sig_inc(i)).max().unwrap_or(0);
820	let last_top = (0..n - 1).map(\|i\| cat.last_inc(i)).max().unwrap_or(0);
821	// A magnitude's contexts: nought to four for the first bin, and five upward for the
822	// rest, one fewer for a chroma direct current block.
823	let level_top = 5 + (4 - usize::from(cat == Cat::ChromaDc));
824	spans.push((fmt!("{:?} significance", cat), cat.sig_base(), cat.sig_base() + sig_top));
825	spans.push((fmt!("{:?} last", cat), cat.last_base(), cat.last_base() + last_top));
826	spans.push((fmt!("{:?} levels", cat), cat.level_base(), cat.level_base() + level_top));
827	spans.push((fmt!("{:?} flag", cat), cat.cbf_base(), cat.cbf_base() + 3));
828	}
829	for (i, (an, a0, a1)) in spans.iter().enumerate() {
830	for (bn, b0, b1) in spans.iter().skip(i + 1) {
831	if a0 <= b1 && b0 <= a1 {
832	return Err(err!(
833	"{} uses contexts {} to {} and {} uses {} to {}, so they share.",
834	an, a0, a1, bn, b0, b1; Test, Invalid));
835	}
836	}
837	}
838	// And every context each span reaches is one the tables initialised.
839	let mut x = Contexts::start(26);
840	for (name, a0, a1) in &spans {
841	for i in a0..=a1 {
842	if x.at(i).is_err() {
843	return Err(err!(
844	"{} reaches context {}, which the intra tables do not carry.", name, i;
845	Test, Missing));
846	}
847	}
848	}
849	Ok(())
850	}
851
852	/// A signed integer as the document prints one.
853	///
854	/// The minus sign is U+2212 rather than the hyphen a parser would expect, and a word that is not
855	/// a number at all -- "na" where a column does not apply, or a word of a row heading -- is not
856	/// one.
857	fn number(w: &str) -> Option<i32> {
858	w.replace('\u{2212}', "-").parse::<i32>().ok()
859	}
860
861	/// The lines of one published table, gathered across every page it spans.
862	///
863	/// A heading occurs in the table of contents as well as over the table, trailing dot leaders and
864	/// a page number, so an occurrence carrying those is not the table. A wide table repeats its
865	/// heading on each page it continues onto, which is why the pieces are gathered rather than the
866	/// first one taken.
867	fn region<'a>(lines: &[&'a str], heading: &str) -> Vec<&'a str> {
868	let mut out = Vec::new();
869	for (start, _) in lines.iter().enumerate()
870	.filter(\|(_, l)\| l.contains(heading) && !l.contains("...."))
871	{
872	for line in lines.iter().skip(start + 1) {
873	if line.trim_start().starts_with("Table 9-") {
874	break;
875	}
876	out.push(*line);
877	}
878	}
879	out
880	}
881
882	/// The numbers of one initialisation table, as a flat run in `ctxIdx` order.
883	///
884	/// Two shapes occur, and which a table uses is a fact about the document rather than about the
885	/// values, so the caller states it in `by_row` and the count then proves it.
886	///
887	/// Tables 9-12, 9-16 and 9-17 lay their values out as a row of every `m` followed by a row of
888	/// every `n`, the I-slice row first. The rest give one line per `ctxIdx`: the index, then the
889	/// I-slice column's `m` and `n`, then three pairs for the values of `cabac_init_idc` -- nine
890	/// numbers, and eighteen where the page prints two halves of the table side by side. **Nothing
891	/// but a line of exactly nine or exactly eighteen numbers is read as data**, which is what keeps
892	/// a value out of the row above or below it: a looser rule reads the neighbouring column's `m` as
893	/// this row's `ctxIdx` and then quietly agrees with a wrong transcription.
894	fn published(lines: &[&str], table: usize, first: usize, count: usize, by_row: bool)
895	-> Outcome<Vec<(i32, i32)>>
896	{
897	let heading = fmt!("Table 9-{} – Values of variables m and n for ctxIdx", table);
898	let body = region(lines, &heading);
899	let mut rows: std::collections::BTreeMap<usize, (i32, i32)> =
900	std::collections::BTreeMap::new();
901	let mut ms: Vec<i32> = Vec::new();
902	let mut ns: Vec<i32> = Vec::new();
903	for line in &body {
904	let words: Vec<&str> = line.split_whitespace().collect();
905	if !by_row {
906	// The label sits after the row's own heading words -- "I slices" in Table 9-16 -- so
907	// it is found rather than assumed to be first, and a run of "na" where a column does
908	// not apply starts the values again.
909	let at = match words.iter().position(\|w\| w == "m" \|\| w == "n") {
910	Some(at) => at,
911	None => continue,
912	};
913	let mut got: Vec<i32> = Vec::new();
914	for w in &words[at + 1..] {
915	match number(w) {
916	Some(v) => got.push(v),
917	None => got.clear(),
918	}
919	}
920	if got.len() == count {
921	if words[at] == "m" && ms.is_empty() {
922	ms = got;
923	} else if words[at] == "n" && ns.is_empty() {
924	ns = got;
925	}
926	}
927	continue;
928	}
929	let got: Vec<Option<i32>> = words.iter().map(\|w\| number(w)).collect();
930	if got.is_empty() \|\| got.iter().any(\|v\| v.is_none()) {
931	continue;
932	}
933	let v: Vec<i32> = got.into_iter().flatten().collect();
934	let halves: &[usize] = match v.len() {
935	9 => &[0],
936	18 => &[0, 9],
937	_ => continue,
938	};
939	for at in halves {
940	let idx = v[*at];
941	if idx < first as i32 \|\| idx >= (first + count) as i32 {
942	return Err(err!(
943	"Table 9-{} has a row for ctxIdx {}, and it is meant to cover {} to {}.",
944	table, idx, first, first + count - 1; Test, Invalid));
945	}
946	if rows.insert(idx as usize, (v[at + 1], v[at + 2])).is_some() {
947	return Err(err!(
948	"Table 9-{} gives ctxIdx {} twice.", table, idx; Test, Invalid));
949	}
950	}
951	}
952	if !by_row && ms.len() == count && ns.len() == count {
953	return Ok(ms.into_iter().zip(ns).collect());
954	}
955	if by_row && rows.len() == count {
956	return Ok(rows.into_values().collect());
957	}
958	Err(err!(
959	"Table 9-{} gave up {} rows and {} m and {} n values, and it covers ctxIdx {} to {}.",
960	table, rows.len(), ms.len(), ns.len(), first, first + count - 1;
961	Test, Missing))
962	}
963
964	#[test]
965	fn test_the_context_tables_are_the_published_ones_07() -> Outcome<()> {
966	// Two hundred and sixty-one pairs of numbers copied out of a document by hand, every one of
967	// which silently ruins a picture if it is wrong. Checking them against the decoder that uses
968	// them proves nothing at all -- the only thing worth checking them against is the
969	// specification they came from, so this reads it:
970	//
971	// pdftotext -layout T-REC-H.264-202108.pdf h264.txt
972	// H264_SPEC_TEXT=~/.cache/specs/h264.txt cargo test -p oxedyne_fe2o3_graphics h264
973	//
974	// Absent, it says so rather than passing quietly: a check that skipped in silence would be a
975	// check nobody ran.
976	let path = match std::env::var("H264_SPEC_TEXT") {
977	Ok(p) => p,
978	Err(_) => {
979	println!(" skipped: set H264_SPEC_TEXT to a text rendering of Rec. ITU-T H.264");
980	return Ok(());
981	},
982	};
983	let text = match std::fs::read_to_string(&path) {
984	Ok(t) => t,
985	Err(e) => {
986	println!(" skipped: {} would not read ({})", path, e);
987	return Ok(());
988	},
989	};
990	let lines: Vec<&str> = text.lines().collect();
991	let mut checked = 0usize;
992	for (first, table, values) in INIT_I {
993	// Where the table starts, how many entries it holds, and whether it prints one line per
994	// ctxIdx. Table 9-12 holds more than an I slice reads -- 0 to 2 are an SI slice's -- and
995	// Table 9-24 holds the eight-by-eight residual of the P and B slices too, so the whole
996	// table is read and the run taken out of it.
997	let (from, count, by_row) = match table {
998	12 => (0usize, 11usize, false),
999	16 => (399, 3, false),
1000	17 => (60, 10, false),
1001	18 => (70, 35, true),
1002	19 => (105, 61, true),
1003	20 => (166, 61, true),
1004	21 => (227, 49, true),
1005	24 => (402, 58, true),
1006	other => return Err(err!(
1007	"Table 9-{} is not one this test knows how to read.", other; Test, Bug)),
1008	};
1009	let all = res!(published(&lines, table, from, count, by_row));
1010	for (i, (m, n)) in values.iter().enumerate() {
1011	let at = first + i - from;
1012	let (pm, pn) = match all.get(at) {
1013	Some(v) => *v,
1014	None => return Err(err!(
1015	"Table 9-{} holds {} entries and ctxIdx {} would be the {}th.",
1016	table, all.len(), first + i, at + 1; Test, Missing)),
1017	};
1018	if pm != m as i32 \|\| pn != n as i32 {
1019	return Err(err!(
1020	"Context {} is initialised from ({}, {}) and Table 9-{} publishes ({}, {}).",
1021	first + i, m, n, table, pm, pn; Test, Mismatch));
1022	}
1023	checked += 1;
1024	}
1025	}
1026	req!(checked, 261, "{} of 261 initialisation pairs were held to the document", checked);
1027
1028	// And the engine's own two tables, which are not initialisation values but are transcribed
1029	// by hand just the same. Table 9-44 prints two halves side by side: a state and its four
1030	// values, then a second state and its four.
1031	let mut rows = 0usize;
1032	for line in region(&lines, "Table 9-44 – Specification of rangeTabLPS") {
1033	let got: Vec<Option<u32>> = line.split_whitespace()
1034	.map(\|w\| w.parse::<u32>().ok())
1035	.collect();
1036	if got.is_empty() \|\| got.iter().any(\|v\| v.is_none()) {
1037	continue;
1038	}
1039	let v: Vec<u32> = got.into_iter().flatten().collect();
1040	let halves: &[usize] = match v.len() {
1041	5 => &[0],
1042	10 => &[0, 5],
1043	_ => continue,
1044	};
1045	for at in halves {
1046	let state = v[*at] as usize;
1047	if state >= 64 {
1048	return Err(err!(
1049	"Table 9-44 has a row for state {}, and there are 64.", state; Test, Invalid));
1050	}
1051	let want = [v[at + 1] as u8, v[at + 2] as u8, v[at + 3] as u8, v[at + 4] as u8];
1052	if LPS[state] != want {
1053	return Err(err!(
1054	"rangeTabLPS row {} is {:?} here and {:?} in Table 9-44.",
1055	state, LPS[state], want; Test, Mismatch));
1056	}
1057	rows += 1;
1058	}
1059	}
1060	req!(rows, 64, "{} of 64 rangeTabLPS rows were held to Table 9-44", rows);
1061
1062	// Table 9-45 prints itself as four blocks of a states row, a transIdxLPS row and a
1063	// transIdxMPS row.
1064	let mut moved = 0usize;
1065	let mut states: Vec<usize> = Vec::new();
1066	for line in region(&lines, "Table 9-45 – State transition table") {
1067	let words: Vec<&str> = line.split_whitespace().collect();
1068	if words.is_empty() {
1069	continue;
1070	}
1071	let got: Vec<u8> = words[1..].iter().filter_map(\|w\| w.parse::<u8>().ok()).collect();
1072	match words[0] {
1073	"pStateIdx" => {
1074	states = got.into_iter().map(usize::from).collect();
1075	},
1076	"transIdxLPS" \| "transIdxMPS" if got.len() == states.len() => {
1077	let held = if words[0] == "transIdxLPS" { &NEXT_LPS } else { &NEXT_MPS };
1078	for (s, v) in states.iter().zip(got.iter()) {
1079	if held[s] != v {
1080	return Err(err!(
1081	"{}({}) is {} here and {} in Table 9-45.",
1082	words[0], s, held[*s], v; Test, Mismatch));
1083	}
1084	moved += 1;
1085	}
1086	},
1087	_ => {},
1088	}
1089	}
1090	req!(moved, 128, "{} of 128 state transitions were held to Table 9-45", moved);
1091	Ok(())
1092	}
1093
1094	#[test]
1095	fn test_the_scan_position_table_is_the_published_one_08() -> Outcome<()> {
1096	// Table 9-43, which is laid out as two halves of a wide table: a scan position, three
1097	// context increments, then a second scan position and three more. Only the first and third
1098	// of the three are held here, since this decoder reads frames.
1099	let path = match std::env::var("H264_SPEC_TEXT") {
1100	Ok(p) => p,
1101	Err(_) => {
1102	println!(" skipped: set H264_SPEC_TEXT to a text rendering of Rec. ITU-T H.264");
1103	return Ok(());
1104	},
1105	};
1106	let text = match std::fs::read_to_string(&path) {
1107	Ok(t) => t,
1108	Err(_) => return Ok(()),
1109	};
1110	let lines: Vec<&str> = text.lines().collect();
1111	let mut seen: std::collections::BTreeMap<usize, (u8, u8)> =
1112	std::collections::BTreeMap::new();
1113	for line in region(&lines, "Table 9-43 – Mapping of scanning position to ctxIdxInc") {
1114	let got: Vec<Option<u8>> = line.split_whitespace()
1115	.map(\|w\| w.parse::<u8>().ok())
1116	.collect();
1117	if got.is_empty() \|\| got.iter().any(\|v\| v.is_none()) {
1118	continue;
1119	}
1120	let v: Vec<u8> = got.into_iter().flatten().collect();
1121	// Each half is four numbers: the scan position and the three context increments.
1122	let halves: &[usize] = match v.len() {
1123	4 => &[0],
1124	8 => &[0, 4],
1125	_ => continue,
1126	};
1127	for at in halves {
1128	let pos = v[*at] as usize;
1129	if pos > 62 {
1130	return Err(err!(
1131	"Table 9-43 has a row for scan position {}, and it covers 0 to 62.", pos;
1132	Test, Invalid));
1133	}
1134	if seen.insert(pos, (v[at + 1], v[at + 3])).is_some() {
1135	return Err(err!(
1136	"Table 9-43 gives scan position {} twice.", pos; Test, Invalid));
1137	}
1138	}
1139	}
1140	req!(seen.len(), 63, "Table 9-43 gave up {} of its 63 scan positions", seen.len());
1141	for (pos, (sig, last)) in &seen {
1142	if SIG_8X8[pos] != sig {
1143	return Err(err!(
1144	"Scan position {} maps to significance context {} here and {} in Table 9-43.",
1145	pos, SIG_8X8[*pos], sig; Test, Mismatch));
1146	}
1147	if LAST_8X8[pos] != last {
1148	return Err(err!(
1149	"Scan position {} maps to last-position context {} here and {} in Table 9-43.",
1150	pos, LAST_8X8[*pos], last; Test, Mismatch));
1151	}
1152	}
1153	Ok(())
1154	}
1155	}