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

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

57.5 KiB, 128 runs

created by r1870400018:21097, 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	//! Walking a coded picture and building the samples back up as it goes.
2	//!
3	//! This is where the syntax of clause 7.3.5 meets the decoding processes of clause 8. The two are
4	//! interleaved rather than done in turn, and they have to be: every block is predicted from the
5	//! samples around it, so a block cannot be predicted until the ones before it in decoding order
6	//! have been reconstructed, not merely parsed.
7	//!
8	//! The shape of the walk, outermost first:
9	//!
10	//! - A slice at a time. A slice is its own entropy-coded run, beginning at the macroblock its
11	//! header names, and nothing in one slice may be predicted from another. Most pictures in the
12	//! corpus are one slice, but 92 of the 1,658 are not.
13	//! - A macroblock is sixteen by sixteen luma samples and, in 4:2:0, eight by eight of each
14	//! colour difference. Its type says how it is predicted: as sixteen four-by-four blocks, as four
15	//! eight-by-eight ones, as one sixteen-by-sixteen, or as raw samples.
16	//! - A block is predicted from its neighbours, its residual read and transformed back, and the
17	//! two added.
18	//!
19	//! # What this decodes and what it refuses
20	//!
21	//! Intra pictures in 4:2:0 at eight bits, coded in frames, with one slice group, with either entropy
22	//! coder -- which is every film in the library it was written against. Anything else is refused where
23	//! it is read, by name, rather than decoded into a wrong picture: field coding, macroblock-adaptive
24	//! frame/field coding, monochrome and 4:2:2 and 4:4:4, bit depths above eight, slice groups, and any
25	//! slice that is not intra.
26	//!
27	//! # The two things that have to be got right and cannot be seen
28	//!
29	//! Availability. A block predicts from its neighbours only where those have already been
30	//! decoded and belong to the same slice. What is kept here is one slice number per four-by-four
31	//! block, written as that block is reconstructed, which is exactly the question being asked and is
32	//! impossible to get subtly wrong. A decoder careless about it predicts from samples that are still
33	//! nought and produces a picture with a plausible grid of dark blocks.
34	//!
35	//! The neighbour counts CAVLC reads its tables with. Each four-by-four block's `nC` is the mean
36	//! of the number of coefficients in the blocks above and to the left, and it selects which of six
37	//! code tables reads the next token. Get it wrong and the right bits are read with the wrong code,
38	//! which desynchronises everything after it in the slice.
39	//!
40	//! The neighbours CABAC chooses its contexts by. The arithmetic coder asks the same question of
41	//! nearly every syntax element -- what did the macroblock to the left and the macroblock above do?
42	//! -- and answers it differently each time: for `coded_block_pattern` the neighbouring block counts
43	//! when it holds nothing, for `coded_block_flag` an absent neighbour counts as coded, and for
44	//! `mb_qp_delta` the neighbour is the macroblock decoded before this one rather than either of
45	//! those. Getting one of these wrong does not stop the decode; it feeds the right bins to the wrong
46	//! probability, and the picture comes out plausible and wrong.
47	//!
48	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
49	//! Anthropic Claude
50
51	use crate::h264::{
52	cabac::{
53	self,
54	Cat,
55	},
56	cavlc,
57	intra::{
58	self,
59	Edges,
60	Mode,
61	Mode16,
62	ModeC,
63	},
64	nal,
65	split_lengthed,
66	transform::{
67	self,
68	Weights,
69	ZIGZAG_4X4,
70	ZIGZAG_8X8,
71	},
72	Bits,
73	Pps,
74	Scaling,
75	Sps,
76	Unit,
77	};
78
79	use oxedyne_fe2o3_core::prelude::*;
80
81	/// One component's samples.
82	#[derive(Clone, Debug, PartialEq, Eq)]
83	pub struct Plane {
84	pub w: usize, // width in samples
85	pub h: usize, // height in samples
86	pub px: Vec<u8>, // row by row
87	}
88
89	impl Plane {
90
91	fn new(w: usize, h: usize) -> Self {
92	Self { w, h, px: vec![0; w * h] }
93	}
94
95	pub fn at(&self, x: usize, y: usize) -> Option<u8> {
96	if x < self.w && y < self.h {
97	self.px.get(y * self.w + x).copied()
98	} else {
99	None
100	}
101	}
102
103	/// Writes one sample, ignoring a position outside the plane.
104	fn put(&mut self, x: usize, y: usize, v: u8) {
105	if x < self.w && y < self.h {
106	self.px[y * self.w + x] = v;
107	}
108	}
109
110	/// The plane cropped to a window, which is what the sequence parameter set's conformance
111	/// window asks for.
112	fn cropped(&self, w: usize, h: usize) -> Self {
113	let mut out = Self::new(w, h);
114	for y in 0..h.min(self.h) {
115	let from = y * self.w;
116	let to = from + w.min(self.w);
117	let at = y * w;
118	out.px[at..at + (to - from)].copy_from_slice(&self.px[from..to]);
119	}
120	out
121	}
122	}
123
124	/// A decoded picture, before it is turned into anything anybody can look at.
125	#[derive(Clone, Debug, PartialEq, Eq)]
126	pub struct Picture {
127	pub y: Plane, // brightness
128	pub cb: Plane, // colour difference, at half the width and half the height
129	pub cr: Plane, // the other one
130	}
131
132	/// How a macroblock is predicted (§7.4.5, Table 7-11).
133	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
134	enum Kind {
135	I4x4, // sixteen four-by-four blocks, each with its own direction
136	I8x8, // four eight-by-eight blocks, each with its own direction
137	I16x16, // one prediction over the whole macroblock, the sixteen DC terms together
138	Pcm, // raw samples, carried uncompressed
139	Absent, // not decoded, or in another slice
140	}
141
142	// The mapping from coded_block_pattern's code number to its value, for an intra macroblock in a
143	// picture with colour (Table 9-4(a), the Intra_4x4, Intra_8x8 column).
144	const CBP_INTRA: [u8; 48] = [
145	47, 31, 15, 0, 23, 27, 29, 30, 7, 11, 13, 14, 39, 43, 45, 46,
146	16, 3, 5, 10, 12, 19, 21, 26, 28, 35, 37, 42, 44, 1, 2, 4,
147	8, 17, 18, 20, 24, 6, 9, 22, 25, 32, 33, 34, 36, 40, 38, 41,
148	];
149
150	/// Where each four-by-four luma block sits in the macroblock, in blocks (§6.4.3).
151	///
152	/// Not raster order: the blocks are walked a quadrant at a time, and within each quadrant a
153	/// quadrant again. Walking them in raster order instead predicts half the blocks from neighbours
154	/// that have not been decoded yet.
155	const fn blk_xy(i: usize) -> (usize, usize) {
156	let quad = i / 4;
157	let within = i % 4;
158	(((quad % 2) * 2) + (within % 2), ((quad / 2) * 2) + (within / 2))
159	}
160
161	/// Which of a macroblock's transform blocks were coded with anything in them (§9.3.3.1.1.9).
162	///
163	/// The arithmetic coder reads each block's `coded_block_flag` against a context chosen by the flags
164	/// of the blocks above and to the left, so a block's answer has to be kept for its neighbours -- and
165	/// the neighbour may be in another macroblock, which is why this is kept per macroblock rather than
166	/// discarded with the block.
167	#[derive(Clone, Copy, Debug, Default)]
168	struct Cbf {
169	luma_dc: bool, // the DC block a macroblock predicted whole carries
170	luma4: [bool; 16], // the four-by-four luma blocks, in the macroblock's own order
171	luma8: [bool; 4], // the eight-by-eight ones, where that transform is used
172	chroma_dc: [bool; 2], // each colour difference component's DC block
173	chroma_ac: [[bool; 4]; 2], // their four alternating current blocks each
174	}
175
176	/// Everything a picture's decoder carries from one macroblock to the next.
177	struct Frame<'a> {
178	sps: &'a Sps, // the sequence parameter set in force
179	pps: &'a Pps, // the picture parameter set in force
180	pic: Picture,
181	mbs_w: usize, // the picture's width in macroblocks
182	mbs_h: usize, // and its height
183	slice_of: Vec<Option<usize>>, // None where no macroblock has been decoded there
184	kind: Vec<Kind>, // how each macroblock is predicted
185	qp: Vec<i32>, // quantisation parameter, for the filter
186	big: Vec<bool>, // eight-by-eight transform, which sets the filter's edges
187	modes: Vec<[u8; 16]>, // each luma block's intra mode, in block order
188	counts: Vec<[u8; 24]>, // coefficients a block holds, for CAVLC's counts
189	cbp_luma: Vec<u8>, // luma coded block pattern, for CABAC's neighbours
190	cbp_chroma: Vec<u8>, // the same for the colour difference planes
191	chroma_mode: Vec<u8>, // chroma prediction mode, one of CABAC's contexts too
192	qp_moved: Vec<bool>, // did it move? this picks the next delta's context
193	cbf: Vec<Cbf>, // which transform blocks hold a coefficient
194	w_luma: Weights, // the luma weights, already scanned
195	w_cb: Weights,
196	w_cr: Weights,
197	}
198
199	impl<'a> Frame<'a> {
200
201	fn new(sps: &'a Sps, pps: &'a Pps) -> Outcome<Self> {
202	let mbs_w = sps.mbs_w as usize;
203	let mbs_h = sps.map_units_h as usize;
204	let n = mbs_w * mbs_h;
205	let scaling = match &pps.scaling {
206	Some(s) => s.clone(),
207	None => Scaling::flat(),
208	};
209	Ok(Self {
210	sps,
211	pps,
212	pic: Picture {
213	y: Plane::new(mbs_w * 16, mbs_h * 16),
214	cb: Plane::new(mbs_w * 8, mbs_h * 8),
215	cr: Plane::new(mbs_w * 8, mbs_h * 8),
216	},
217	mbs_w,
218	mbs_h,
219	slice_of: vec![None; n],
220	kind: vec![Kind::Absent; n],
221	qp: vec![0; n],
222	big: vec![false; n],
223	modes: vec![[2u8; 16]; n],
224	counts: vec![[0u8; 24]; n],
225	cbp_luma: vec![0; n],
226	cbp_chroma: vec![0; n],
227	chroma_mode: vec![0; n],
228	qp_moved: vec![false; n],
229	cbf: vec![Cbf::default(); n],
230	w_luma: Weights::intra(&scaling, 0),
231	w_cb: Weights::intra(&scaling, 1),
232	w_cr: Weights::intra(&scaling, 2),
233	})
234	}
235
236	/// Has a macroblock been decoded, and does it belong to the given slice?
237	fn available(&self, mb: i64, slice: usize) -> bool {
238	if mb < 0 \|\| mb as usize >= self.slice_of.len() {
239	return false;
240	}
241	self.slice_of[mb as usize] == Some(slice)
242	}
243
244	/// The macroblock to the left, above, above-right and above-left, where each is available.
245	fn around(&self, mb: usize, slice: usize) -> [Option<usize>; 4] {
246	let w = self.mbs_w as i64;
247	let m = mb as i64;
248	let col = m % w;
249	let a = if col > 0 { m - 1 } else { -1 };
250	let b = m - w;
251	let c = if col + 1 < w { m - w + 1 } else { -1 };
252	let d = if col > 0 { m - w - 1 } else { -1 };
253	let mut out = [None; 4];
254	for (i, n) in [a, b, c, d].into_iter().enumerate() {
255	if self.available(n, slice) {
256	out[i] = Some(n as usize);
257	}
258	}
259	out
260	}
261	}
262
263	/// The state one slice's decoder carries between macroblocks.
264	struct SliceRun {
265	index: usize, // which slice this is, from nought within the picture
266	qp: i32, // the running quantisation parameter
267	transform_8x8: bool, // does the picture parameter set allow the big transform?
268	}
269
270	/// Decodes the first coded picture of a film.
271	///
272	/// `config` is the `avcC` decoder configuration record and `sample` is one access unit as the
273	/// container stores it: NAL units each behind a length prefix. Parameter sets carried in the sample
274	/// itself override the record's, which is how an `avc3` stream works and which costs nothing to
275	/// support.
276	pub fn picture(config: &[u8], sample: &[u8]) -> Outcome<Picture> {
277	whole(config, sample, true)
278	}
279
280	/// The same picture, before the deblocking filter has run.
281	///
282	/// Not a picture anybody should look at: it is the reconstruction the filter is meant to smooth,
283	/// and it is here because it is the only way to tell a fault in prediction or in the residual from
284	/// a fault in the filter. FFmpeg will produce the same thing on demand -- `-skip_loop_filter all`
285	/// -- so the two halves of a decode can be held to it separately, and a mismatch says which half.
286	pub fn picture_undeblocked(config: &[u8], sample: &[u8]) -> Outcome<Picture> {
287	whole(config, sample, false)
288	}
289
290	fn whole(config: &[u8], sample: &[u8], deblock: bool) -> Outcome<Picture> {
291	let cfg = res!(crate::h264::config(config));
292	let mut sets = Vec::new();
293	for u in &cfg.sps {
294	sets.push(res!(crate::h264::sps(&u.body)));
295	}
296	let mut pics = Vec::new();
297	for u in &cfg.pps {
298	pics.push(res!(crate::h264::pps(&u.body, &sets)));
299	}
300	let units = res!(split_lengthed(sample, cfg.length_size));
301	decode(&units, &mut sets, &mut pics, deblock)
302	}
303
304	pub fn decode(units: &[Unit], sets: &mut Vec<Sps>, pics: &mut Vec<Pps>, deblock: bool)
305	-> Outcome<Picture>
306	{
307	// Parameter sets carried in the sample itself come first, so that a slice reads the ones it
308	// was coded against.
309	for u in units {
310	match u.kind {
311	nal::SPS => {
312	let s = res!(crate::h264::sps(&u.body));
313	sets.retain(\|o\| o.id != s.id);
314	sets.push(s);
315	},
316	nal::PPS => {
317	let p = res!(crate::h264::pps(&u.body, sets));
318	pics.retain(\|o\| o.id != p.id);
319	pics.push(p);
320	},
321	_ => {},
322	}
323	}
324	let slices: Vec<&Unit> = units.iter()
325	.filter(\|u\| matches!(u.kind, nal::SLICE \| nal::IDR))
326	.collect();
327	let first = match slices.first() {
328	Some(u) => *u,
329	None => return Err(err!(
330	"The access unit carries no coded slice, only NAL units {:?}.",
331	units.iter().map(\|u\| u.kind).collect::<Vec<_>>();
332	Invalid, Input, Missing)),
333	};
334	let head = res!(crate::h264::slice(first, sets, pics));
335	let pps = match pics.iter().find(\|p\| p.id == head.pps_id) {
336	Some(p) => p,
337	None => return Err(err!(
338	"A slice references picture parameter set {}, which the stream does not carry.",
339	head.pps_id; Invalid, Input, Missing)),
340	};
341	let sps = match sets.iter().find(\|s\| s.id == pps.sps_id) {
342	Some(s) => s,
343	None => return Err(err!(
344	"A picture parameter set references sequence parameter set {}, which the stream does \
345	not carry.", pps.sps_id; Invalid, Input, Missing)),
346	};
347	res!(refuse_what_is_not_read(sps, pps));
348	let mut frame = res!(Frame::new(sps, pps));
349	// Each slice carries its own deblocking disposition and its own thresholds, and they are not
350	// a formality: 92 pictures in the corpus have more than one slice, and the two films whose
351	// decode this was found by both turn the filter off across slice boundaries only.
352	let mut filters: Vec<Filter> = Vec::with_capacity(slices.len());
353
354	for (index, u) in slices.iter().enumerate() {
355	let head = res!(crate::h264::slice(u, sets, pics));
356	if head.pps_id != pps.id {
357	return Err(err!(
358	"Two slices of one picture reference picture parameter sets {} and {}. This \
359	decoder reads a picture whose slices agree.", pps.id, head.pps_id;
360	Invalid, Input, Unimplemented));
361	}
362	let mut run = SliceRun {
363	index,
364	qp: head.qp,
365	transform_8x8: pps.transform_8x8,
366	};
367	filters.push(Filter {
368	idc: head.deblocking,
369	alpha: head.alpha_offset,
370	beta: head.beta_offset,
371	});
372	if pps.cabac {
373	res!(slice_data_cabac(&mut frame, &mut run, u, head.first_mb as usize, head.data_bit));
374	} else {
375	res!(slice_data(&mut frame, &mut run, u, head.first_mb as usize, head.data_bit));
376	}
377	}
378	// The slices of a picture tile it: between them they cover every macroblock exactly once. A
379	// macroblock left undecoded means a slice ended before it should have, and for a slice coded with
380	// the arithmetic coder that means the coder lost the bitstream -- which otherwise shows up only
381	// as a picture, since a desynchronised arithmetic decoder goes on answering bins.
382	if let Some(missing) = frame.slice_of.iter().position(\|s\| s.is_none()) {
383	return Err(err!(
384	"Macroblock {} of {} was never decoded: the picture's {} slices did not cover it. \
385	Either a slice ended early or the picture is not whole.",
386	missing, frame.slice_of.len(), slices.len();
387	Invalid, Input, Decode));
388	}
389	if deblock {
390	let mut view = frame_view(&mut frame);
391	view.filters = &filters;
392	res!(crate::h264::filter::deblock(&mut view));
393	}
394	Ok(crop(&frame))
395	}
396
397	fn refuse_what_is_not_read(sps: &Sps, pps: &Pps) -> Outcome<()> {
398	if sps.chroma != 1 {
399	return Err(err!(
400	"The stream is coded at chroma_format_idc {}, and this decoder reads 4:2:0, which is \
401	1. All 1,658 H.264 films in the corpus it was written against are 4:2:0.", sps.chroma;
402	Invalid, Input, Unimplemented));
403	}
404	if sps.luma_bits != 8 \|\| sps.chroma_bits != 8 {
405	return Err(err!(
406	"The stream is coded at {} bits of luma and {} of chroma, and this decoder reads \
407	eight of each.", sps.luma_bits, sps.chroma_bits;
408	Invalid, Input, Unimplemented));
409	}
410	if !sps.frame_mbs_only {
411	return Err(err!(
412	"The stream may code fields as well as frames (frame_mbs_only_flag is 0), and this \
413	decoder reads frames.";
414	Invalid, Input, Unimplemented));
415	}
416	if sps.mbaff {
417	return Err(err!(
418	"The stream uses macroblock-adaptive frame/field coding, and this decoder reads \
419	frame macroblocks.";
420	Invalid, Input, Unimplemented));
421	}
422	if pps.slice_groups > 1 {
423	return Err(err!(
424	"The picture is cut into {} slice groups, and this decoder reads one.",
425	pps.slice_groups;
426	Invalid, Input, Unimplemented));
427	}
428	if pps.constrained_intra {
429	return Err(err!(
430	"constrained_intra_pred_flag is set. For an all-intra picture it changes nothing, but \
431	it is refused rather than ignored, because a picture that sets it and is not all \
432	intra would decode wrongly.";
433	Invalid, Input, Unimplemented));
434	}
435	if sps.qpprime_bypass {
436	return Err(err!(
437	"qpprime_y_zero_transform_bypass_flag is set, so a macroblock at a quantisation \
438	parameter of nought skips the transform. This decoder does not read that.";
439	Invalid, Input, Unimplemented));
440	}
441	Ok(())
442	}
443
444	/// Walks one slice's macroblocks (§7.3.4).
445	fn slice_data(f: &mut Frame, run: &mut SliceRun, u: &Unit, first_mb: usize, at: usize)
446	-> Outcome<()>
447	{
448	let mut b = Bits::at(&u.body, at);
449	let mut mb = first_mb;
450	let total = f.mbs_w * f.mbs_h;
451	loop {
452	if mb >= total {
453	return Err(err!(
454	"A slice ran past macroblock {} of a picture that holds {}.", mb, total;
455	Invalid, Input, Decode));
456	}
457	res!(macroblock(f, run, &mut b, mb));
458	mb += 1;
459	// A slice ends where its payload does. `more_rbsp_data` is the whole of the test for a
460	// slice coded with the length tables; there is no end-of-slice flag.
461	if !b.more_data() {
462	break;
463	}
464	}
465	Ok(())
466	}
467
468	/// Reads and reconstructs one macroblock (§7.3.5).
469	fn macroblock(f: &mut Frame, run: &mut SliceRun, b: &mut Bits, mb: usize) -> Outcome<()> {
470	let mb_type = res!(b.ue());
471	if mb_type == 25 {
472	return pcm(f, run, b, mb);
473	}
474	if mb_type > 25 {
475	return Err(err!(
476	"An mb_type of {} was coded in an intra slice, and 0 to 25 are the only ones defined.",
477	mb_type; Invalid, Input, Decode));
478	}
479	let (kind, mut cbp_luma, mut cbp_chroma, pred16) = if mb_type == 0 {
480	(Kind::I4x4, 0u8, 0u8, Mode16::Dc)
481	} else {
482	// Table 7-11: the twenty-four Intra_16x16 types are the prediction mode, the chroma
483	// pattern and the luma pattern counted off in that order.
484	let k = (mb_type - 1) as usize;
485	let pred = res!(Mode16::of((k % 4) as u32));
486	let chroma = ((k / 4) % 3) as u8;
487	let luma = if k >= 12 { 15u8 } else { 0 };
488	(Kind::I16x16, luma, chroma, pred)
489	};
490	let mut kind = kind;
491	// The eight-by-eight transform is chosen per macroblock, and only where the picture parameter
492	// set allows it at all.
493	if kind == Kind::I4x4 && run.transform_8x8 && res!(b.flag()) {
494	kind = Kind::I8x8;
495	}
496	// The prediction modes.
497	let mut modes = [2u8; 16];
498	if kind == Kind::I4x4 {
499	for i in 0..16 {
500	let predicted = res!(predicted_mode(f, run, mb, i, &modes, kind));
501	modes[i] = res!(read_mode(b, predicted));
502	}
503	} else if kind == Kind::I8x8 {
504	for i in 0..4 {
505	let predicted = res!(predicted_mode(f, run, mb, i * 4, &modes, kind));
506	let m = res!(read_mode(b, predicted));
507	// An eight-by-eight block's mode is recorded against all four of its four-by-four
508	// blocks, because that is where the next macroblock's prediction looks for it.
509	for k in 0..4 {
510	modes[i * 4 + k] = m;
511	}
512	}
513	}
514	let chroma_mode = if matches!(kind, Kind::I4x4 \| Kind::I8x8 \| Kind::I16x16) {
515	res!(ModeC::of(res!(b.ue())))
516	} else {
517	ModeC::Dc
518	};
519	if kind != Kind::I16x16 {
520	let code = res!(b.ue()) as usize;
521	let cbp = match CBP_INTRA.get(code) {
522	Some(v) => *v,
523	None => return Err(err!(
524	"A coded_block_pattern code number of {} was read, and the table holds 48.", code;
525	Invalid, Input, Decode)),
526	};
527	cbp_luma = cbp & 15;
528	cbp_chroma = cbp >> 4;
529	}
530	// Where nothing is coded at all, the quantisation parameter does not move.
531	let mut qp = run.qp;
532	if cbp_luma > 0 \|\| cbp_chroma > 0 \|\| kind == Kind::I16x16 {
533	let delta = res!(b.se());
534	if !(-26..=25).contains(&delta) {
535	return Err(err!(
536	"An mb_qp_delta of {} was coded, and it runs from -26 to 25.", delta;
537	Invalid, Input, Decode));
538	}
539	// The parameter wraps rather than clipping, so that a delta may reach any value from any
540	// other in one step (§7.4.5).
541	qp = (run.qp + delta + 52).rem_euclid(52);
542	run.qp = qp;
543	}
544	// The residual.
545	let mut luma_dc = [0i32; 16];
546	let mut luma = [[0i32; 16]; 16];
547	let mut luma8 = [[0i32; 64]; 4];
548	let mut chroma_dc = [[0i32; 4]; 2];
549	let mut chroma = [[[0i32; 16]; 4]; 2];
550	let mut counts = [0u8; 24];
551
552	if kind == Kind::I16x16 {
553	let nc = res!(luma_nc(f, run, mb, 0, &counts));
554	let block = res!(cavlc::residual(b, nc, 16));
555	for (i, at) in ZIGZAG_4X4.iter().enumerate() {
556	luma_dc[*at] = block.levels[i];
557	}
558	}
559	for i8 in 0..4usize {
560	for i4 in 0..4usize {
561	let blk = i8 * 4 + i4;
562	if cbp_luma & (1 << i8) == 0 {
563	continue;
564	}
565	let nc = res!(luma_nc(f, run, mb, blk, &counts));
566	let (start, max) = if kind == Kind::I16x16 { (1usize, 15usize) } else { (0, 16) };
567	let block = res!(cavlc::residual(b, nc, max));
568	counts[blk] = block.total as u8;
569	// A macroblock coded with the eight-by-eight transform still reads four
570	// variable-length blocks and interleaves them, because CAVLC has no table for
571	// sixty-four coefficients (§7.3.5.3.1).
572	if kind == Kind::I8x8 {
573	for (i, v) in block.levels.iter().enumerate() {
574	luma8[i8][4 * i + i4] = *v;
575	}
576	} else {
577	// Into raster order as they are read, since the scan is the only thing that
578	// says where in the block a coefficient belongs. An `Intra_16x16` block's
579	// alternating-current terms begin at scan position one, because position nought
580	// is the direct current term that was transformed with the other fifteen.
581	for (i, v) in block.levels.iter().enumerate() {
582	luma[blk][ZIGZAG_4X4[start + i]] = *v;
583	}
584	}
585	}
586	}
587	if cbp_chroma & 3 != 0 {
588	for c in 0..2usize {
589	let block = res!(cavlc::residual(b, -1, 4));
590	chroma_dc[c].copy_from_slice(&block.levels[..4]);
591	}
592	}
593	if cbp_chroma & 2 != 0 {
594	for c in 0..2usize {
595	for i in 0..4usize {
596	let nc = res!(chroma_nc(f, run, mb, c, i, &counts));
597	let block = res!(cavlc::residual(b, nc, 15));
598	counts[16 + c * 4 + i] = block.total as u8;
599	for (k, v) in block.levels.iter().enumerate() {
600	chroma[c][i][ZIGZAG_4X4[1 + k]] = *v;
601	}
602	}
603	}
604	}
605
606	// Record what the neighbours will ask about, before reconstruction, since reconstruction of a
607	// later block in this macroblock reads it.
608	f.slice_of[mb] = Some(run.index);
609	f.kind[mb] = kind;
610	f.qp[mb] = qp;
611	f.modes[mb] = modes;
612	f.counts[mb] = counts;
613	f.big[mb] = kind == Kind::I8x8;
614
615	if std::env::var("H264_TRACE").is_ok() && mb < 3 {
616	eprintln!("mb {} type {} kind {:?} cbpL {} cbpC {} qp {} p16 {:?} ch {:?} modes {:?} \
617	counts {:?} dc {:?}",
618	mb, mb_type, kind, cbp_luma, cbp_chroma, qp, pred16, chroma_mode, modes,
619	&counts[..16], &luma_dc[..4]);
620	}
621	res!(reconstruct(f, run, mb, kind, qp, pred16, chroma_mode, &modes, &luma_dc, &luma, &luma8,
622	&chroma_dc, &chroma));
623	Ok(())
624	}
625
626	/// Reads a raw-sample macroblock (§7.3.5).
627	fn pcm(f: &mut Frame, run: &mut SliceRun, b: &mut Bits, mb: usize) -> Outcome<()> {
628	// The samples begin at the next byte boundary.
629	let pad = (8 - (b.consumed() % 8)) % 8;
630	res!(b.skip(pad));
631	let (mx, my) = ((mb % f.mbs_w) * 16, (mb / f.mbs_w) * 16);
632	for y in 0..16 {
633	for x in 0..16 {
634	let v = res!(b.u(8)) as u8;
635	f.pic.y.put(mx + x, my + y, v);
636	}
637	}
638	let (cx, cy) = ((mb % f.mbs_w) * 8, (mb / f.mbs_w) * 8);
639	for c in 0..2 {
640	for y in 0..8 {
641	for x in 0..8 {
642	let v = res!(b.u(8)) as u8;
643	if c == 0 {
644	f.pic.cb.put(cx + x, cy + y, v);
645	} else {
646	f.pic.cr.put(cx + x, cy + y, v);
647	}
648	}
649	}
650	}
651	f.slice_of[mb] = Some(run.index);
652	f.kind[mb] = Kind::Pcm;
653	f.qp[mb] = 0;
654	f.modes[mb] = [2u8; 16];
655	// A raw macroblock counts as sixteen coefficients everywhere, for its neighbours' tables.
656	f.counts[mb] = [16u8; 24];
657	Ok(())
658	}
659
660	// -------------------------------------------------------------- the arithmetically coded walk
661
662	/// The arithmetic coder's state for one slice.
663	struct Entropy<'a> {
664	body: &'a [u8], // from the first bit of the NAL unit's own body
665	base: usize, // where the engine's buffer begins, bytes; moves only for a PCM macroblock
666	c: cabac::Cabac<'a>, // the decoding engine
667	x: cabac::Contexts, // the context variables
668	prev: Option<usize>, // the macroblock decoded before this one in this slice
669	}
670
671	impl<'a> Entropy<'a> {
672
673	/// The coder as a slice's entropy-coded data begins (§7.3.4, §9.3.1).
674	///
675	/// `at` is where the slice header ended, in bits. The data begins at the next byte boundary, and
676	/// the bits between are `cabac_alignment_one_bit`s, which are all ones. They are checked rather
677	/// than skipped: a header read one bit short lands here with a zero among them, and saying so is
678	/// far better than decoding the whole picture from one bit out.
679	fn new(body: &'a [u8], at: usize, qp: i32) -> Outcome<Self> {
680	let mut b = Bits::at(body, at);
681	while b.consumed() % 8 != 0 {
682	if !res!(b.flag()) {
683	return Err(err!(
684	"A slice's cabac_alignment_one_bit at bit {} is nought, so the slice header was \
685	not read to its end.", b.consumed() - 1;
686	Invalid, Input, Decode));
687	}
688	}
689	let base = b.consumed() / 8;
690	Ok(Self {
691	body,
692	base,
693	c: res!(cabac::Cabac::new(&body[base..])),
694	x: cabac::Contexts::start(qp),
695	prev: None,
696	})
697	}
698
699	fn bin(&mut self, ctx_idx: usize) -> Outcome<u32> {
700	self.x.bin(&mut self.c, ctx_idx)
701	}
702
703	/// Where the engine's next unread bit sits, in bytes from the start of the payload, rounded up.
704	fn byte(&self) -> usize {
705	self.base + self.c.consumed_bits().div_ceil(8)
706	}
707
708	/// Starts the engine afresh at a byte of the payload, which is what follows a raw-sample
709	/// macroblock (§9.3.1.2).
710	fn restart(&mut self, at: usize) -> Outcome<()> {
711	let body = self.body;
712	if at >= body.len() {
713	return Err(err!(
714	"An arithmetic decoder was to restart at byte {} of a payload of {}.", at, body.len();
715	Invalid, Input, Decode));
716	}
717	self.base = at;
718	self.c = res!(cabac::Cabac::new(&body[at..]));
719	Ok(())
720	}
721	}
722
723	/// What a macroblock's own neighbour lookups need before it has been recorded against the picture.
724	///
725	/// A block predicts its context from the blocks above and to the left, and half of those are inside
726	/// the macroblock being read. Reading them out of the picture instead would give every one of them
727	/// the answer for "not yet decoded", which decodes the first block of each macroblock correctly and
728	/// the rest wrongly.
729	struct Partial {
730	kind: Kind, // how the macroblock is predicted
731	cbp_luma: u8, // its luma coded block pattern, as far as it has been read
732	cbp_chroma: u8, // its chroma one
733	cbf: Cbf, // which transform blocks have been read, and what they held
734	}
735
736	/// The macroblock to the left and the macroblock above, where each is available (§6.4.11.1).
737	fn ab(f: &Frame, run: &SliceRun, mb: usize) -> [Option<usize>; 2] {
738	let around = f.around(mb, run.index);
739	[around[0], around[1]]
740	}
741
742	/// The macroblock and four-by-four luma block each of a block's two neighbours sits in (§6.4.11.4).
743	fn luma4_ab(f: &Frame, run: &SliceRun, mb: usize, blk: usize) -> [Option<(usize, usize)>; 2] {
744	let (bx, by) = blk_xy(blk);
745	let around = f.around(mb, run.index);
746	[
747	if bx > 0 {
748	Some((mb, blk_index(bx - 1, by)))
749	} else {
750	around[0].map(\|n\| (n, blk_index(3, by)))
751	},
752	if by > 0 {
753	Some((mb, blk_index(bx, by - 1)))
754	} else {
755	around[1].map(\|n\| (n, blk_index(bx, 3)))
756	},
757	]
758	}
759
760	/// The same for an eight-by-eight luma block, which sit in plain raster order (§6.4.11.2).
761	fn luma8_ab(f: &Frame, run: &SliceRun, mb: usize, blk: usize) -> [Option<(usize, usize)>; 2] {
762	let (bx, by) = (blk % 2, blk / 2);
763	let around = f.around(mb, run.index);
764	[
765	if bx > 0 {
766	Some((mb, by * 2 + bx - 1))
767	} else {
768	around[0].map(\|n\| (n, by * 2 + 1))
769	},
770	if by > 0 {
771	Some((mb, (by - 1) * 2 + bx))
772	} else {
773	around[1].map(\|n\| (n, 2 + bx))
774	},
775	]
776	}
777
778	/// And for a four-by-four block of a 4:2:0 colour difference plane (§6.4.11.5).
779	fn chroma4_ab(f: &Frame, run: &SliceRun, mb: usize, blk: usize) -> [Option<(usize, usize)>; 2] {
780	// A 4:2:0 macroblock's chroma is eight by eight, so its four blocks tile it two by two, which
781	// makes the arithmetic the same as an eight-by-eight luma block's.
782	luma8_ab(f, run, mb, blk)
783	}
784
785	/// Adds a neighbour's contribution to a context increment.
786	///
787	/// The left neighbour counts once and the upper one twice, wherever the specification writes
788	/// `condTermFlagA + 2 * condTermFlagB`; where it writes `condTermFlagA + condTermFlagB` the caller
789	/// sums them itself instead.
790	fn weigh(terms: [usize; 2]) -> usize {
791	terms[0] + 2 * terms[1]
792	}
793
794	/// Reads `mb_type` in an intra slice (§9.3.2.5, Table 9-36, §9.3.3.1.1.3).
795	fn read_mb_type(f: &Frame, run: &SliceRun, e: &mut Entropy, mb: usize) -> Outcome<u32> {
796	let base = cabac::offset::MB_TYPE;
797	// A neighbour coded as sixteen four-by-four or four eight-by-eight blocks contributes nothing,
798	// and any other available neighbour contributes one.
799	let mut inc = 0usize;
800	for n in ab(f, run, mb).into_iter().flatten() {
801	if !matches!(f.kind[n], Kind::I4x4 \| Kind::I8x8) {
802	inc += 1;
803	}
804	}
805	if res!(e.bin(base + inc)) == 0 {
806	return Ok(0);
807	}
808	// The second bin is the one that names a raw-sample macroblock, and it is decoded by the
809	// terminating process rather than against a context of its own.
810	if e.c.terminate() == 1 {
811	return Ok(25);
812	}
813	// Whether all sixteen luma blocks are coded or none of them are.
814	let luma = res!(e.bin(base + 3));
815	// Whether the colour difference pattern is anything but nought.
816	let chroma_any = res!(e.bin(base + 4));
817	let first = res!(e.bin(base + if chroma_any != 0 { 5 } else { 6 }));
818	let second = res!(e.bin(base + if chroma_any != 0 { 6 } else { 7 }));
819	let (chroma, pred) = if chroma_any == 0 {
820	(0u32, first * 2 + second)
821	} else {
822	let third = res!(e.bin(base + 7));
823	(first + 1, second * 2 + third)
824	};
825	// Table 7-11 counts the twenty-four Intra_16x16 types off as the prediction mode, then the
826	// chroma pattern, then the luma one.
827	Ok(1 + pred + 4 * chroma + 12 * luma)
828	}
829
830	/// Reads `transform_size_8x8_flag` (§9.3.3.1.1.10).
831	fn read_transform_8x8(f: &Frame, run: &SliceRun, e: &mut Entropy, mb: usize) -> Outcome<bool> {
832	let mut inc = 0usize;
833	for n in ab(f, run, mb).into_iter().flatten() {
834	if f.big[n] {
835	inc += 1;
836	}
837	}
838	Ok(res!(e.bin(cabac::offset::TRANSFORM_8X8 + inc)) == 1)
839	}
840
841	/// Reads one block's intra prediction mode, given the mode predicted for it (§9.3.2.4).
842	fn read_mode_cabac(e: &mut Entropy, predicted: u8) -> Outcome<u8> {
843	if res!(e.bin(cabac::offset::PREV_PRED)) == 1 {
844	return Ok(predicted);
845	}
846	// Three bins at one context, least significant first.
847	let mut rem = 0u8;
848	for i in 0..3 {
849	rem \|= (res!(e.bin(cabac::offset::REM_PRED)) as u8) << i;
850	}
851	Ok(if rem < predicted { rem } else { rem + 1 })
852	}
853
854	/// Reads `intra_chroma_pred_mode` (§9.3.3.1.1.8).
855	fn read_chroma_mode(f: &Frame, run: &SliceRun, e: &mut Entropy, mb: usize) -> Outcome<u32> {
856	let base = cabac::offset::CHROMA_PRED;
857	let mut inc = 0usize;
858	for n in ab(f, run, mb).into_iter().flatten() {
859	// A raw-sample neighbour has no mode, and one that predicted along the direct current mode
860	// contributes nothing.
861	if f.kind[n] != Kind::Pcm && f.chroma_mode[n] != 0 {
862	inc += 1;
863	}
864	}
865	if res!(e.bin(base + inc)) == 0 {
866	return Ok(0);
867	}
868	if res!(e.bin(base + 3)) == 0 {
869	return Ok(1);
870	}
871	if res!(e.bin(base + 3)) == 0 {
872	return Ok(2);
873	}
874	Ok(3)
875	}
876
877	/// Reads `coded_block_pattern`, luma part then chroma (§9.3.2.6, §9.3.3.1.1.4).
878	fn read_cbp(f: &Frame, run: &SliceRun, e: &mut Entropy, mb: usize) -> Outcome<(u8, u8)> {
879	let mut luma = 0u8;
880	for blk in 0..4usize {
881	// `condTermFlagN` is one where the neighbouring eight-by-eight block holds nothing, which
882	// is the way round that reads oddly and is the specification's.
883	let sides = luma8_ab(f, run, mb, blk);
884	let mut terms = [0usize; 2];
885	for (i, side) in sides.into_iter().enumerate() {
886	terms[i] = match side {
887	None => 0,
888	Some((n, k)) => {
889	let empty = if n == mb {
890	luma & (1 << k) == 0
891	} else if f.kind[n] == Kind::Pcm {
892	false
893	} else {
894	f.cbp_luma[n] & (1 << k) == 0
895	};
896	usize::from(empty)
897	},
898	};
899	}
900	// The four bins are the four bits of the pattern, least significant first.
901	if res!(e.bin(cabac::offset::CBP_LUMA + weigh(terms))) == 1 {
902	luma \|= 1 << blk;
903	}
904	}
905	let mut chroma = 0u8;
906	for bin in 0..2usize {
907	let mut terms = [0usize; 2];
908	for (i, side) in ab(f, run, mb).into_iter().enumerate() {
909	terms[i] = match side {
910	None => 0,
911	Some(n) => {
912	let term = if f.kind[n] == Kind::Pcm {
913	true
914	} else if bin == 0 {
915	f.cbp_chroma[n] != 0
916	} else {
917	f.cbp_chroma[n] == 2
918	};
919	usize::from(term)
920	},
921	};
922	}
923	let inc = weigh(terms) + if bin == 1 { 4 } else { 0 };
924	if res!(e.bin(cabac::offset::CBP_CHROMA + inc)) == 0 {
925	break;
926	}
927	chroma = bin as u8 + 1;
928	}
929	Ok((luma, chroma))
930	}
931
932	/// Reads `mb_qp_delta` (§9.3.2.7, Table 9-3, §9.3.3.1.1.5).
933	fn read_qp_delta(f: &Frame, e: &mut Entropy) -> Outcome<i32> {
934	let base = cabac::offset::MB_QP_DELTA;
935	let first = match e.prev {
936	None => 0usize,
937	Some(p) => {
938	if f.kind[p] == Kind::Pcm {
939	0
940	} else if f.kind[p] != Kind::I16x16 && f.cbp_luma[p] == 0 && f.cbp_chroma[p] == 0 {
941	0
942	} else {
943	usize::from(f.qp_moved[p])
944	}
945	},
946	};
947	let mut k = 0u32;
948	if res!(e.bin(base + first)) == 1 {
949	k = 1;
950	if res!(e.bin(base + 2)) == 1 {
951	k = 2;
952	while res!(e.bin(base + 3)) == 1 {
953	k += 1;
954	// The delta runs from −26 to 25 at eight bits, so its mapped value runs to 51. A
955	// longer run is a decoder that has lost the syntax rather than a legal value.
956	if k > 87 {
957	return Err(err!(
958	"An mb_qp_delta was coded as a unary run of more than 87 bins, which no legal \
959	value is.";
960	Invalid, Input, Decode));
961	}
962	}
963	}
964	}
965	// Table 9-3 alternates: nought, then one, then minus one, and so on.
966	Ok(if k % 2 == 1 {
967	((k + 1) / 2) as i32
968	} else {
969	-((k / 2) as i32)
970	})
971	}
972
973	/// One neighbour's contribution to a `coded_block_flag` context increment (§9.3.3.1.1.9).
974	///
975	/// `kind` is how the neighbouring macroblock is predicted, or `None` where there is no such
976	/// macroblock; `flag` is the neighbouring transform block's own flag, or `None` where that block does
977	/// not exist. An absent neighbour counts as coded, because every macroblock this decoder reads is
978	/// intra; for an inter one it would count as nought, and reading that way round gives every
979	/// macroblock along the top and left edges of a picture the wrong context.
980	fn cbf_term(kind: Option<Kind>, flag: Option<bool>) -> usize {
981	match kind {
982	None => 1,
983	// A raw-sample neighbour counts as coded whatever its blocks hold.
984	Some(Kind::Pcm) => 1,
985	Some(_) => usize::from(flag.unwrap_or(false)),
986	}
987	}
988
989	/// The `coded_block_flag` context increment for a macroblock's block of direct current terms.
990	fn cbf_inc_luma_dc(f: &Frame, run: &SliceRun, mb: usize) -> usize {
991	let mut terms = [0usize; 2];
992	for (i, side) in ab(f, run, mb).into_iter().enumerate() {
993	terms[i] = match side {
994	None => cbf_term(None, None),
995	// Only a macroblock predicted whole has a block of direct current terms at all.
996	Some(n) => match f.kind[n] {
997	Kind::I16x16 => cbf_term(Some(Kind::I16x16), Some(f.cbf[n].luma_dc)),
998	other => cbf_term(Some(other), None),
999	},
1000	};
1001	}
1002	weigh(terms)
1003	}
1004
1005	/// The same for one of a macroblock's four-by-four luma blocks.
1006	fn cbf_inc_luma4(f: &Frame, run: &SliceRun, mb: usize, blk: usize, here: &Partial) -> usize {
1007	let mut terms = [0usize; 2];
1008	for (i, side) in luma4_ab(f, run, mb, blk).into_iter().enumerate() {
1009	terms[i] = match side {
1010	None => cbf_term(None, None),
1011	Some((n, k)) => {
1012	let (kind, cbp, cbf) = if n == mb {
1013	(here.kind, here.cbp_luma, &here.cbf)
1014	} else {
1015	(f.kind[n], f.cbp_luma[n], &f.cbf[n])
1016	};
1017	// The block exists only where the pattern says its quadrant carries anything.
1018	let flag = if cbp & (1 << (k >> 2)) == 0 {
1019	None
1020	} else if kind == Kind::I8x8 {
1021	// A neighbour that used the eight-by-eight transform offers that block instead,
1022	// and in 4:2:0 its flag is not coded at all but inferred to be one.
1023	Some(cbf.luma8[k >> 2])
1024	} else {
1025	Some(cbf.luma4[k])
1026	};
1027	cbf_term(Some(kind), flag)
1028	},
1029	};
1030	}
1031	weigh(terms)
1032	}
1033
1034	/// The same for one colour difference component's block of direct current terms.
1035	fn cbf_inc_chroma_dc(f: &Frame, run: &SliceRun, mb: usize, c: usize) -> usize {
1036	let mut terms = [0usize; 2];
1037	for (i, side) in ab(f, run, mb).into_iter().enumerate() {
1038	terms[i] = match side {
1039	None => cbf_term(None, None),
1040	Some(n) => {
1041	let flag = if f.cbp_chroma[n] == 0 {
1042	None
1043	} else {
1044	Some(f.cbf[n].chroma_dc[c])
1045	};
1046	cbf_term(Some(f.kind[n]), flag)
1047	},
1048	};
1049	}
1050	weigh(terms)
1051	}
1052
1053	/// The same for one of its alternating current blocks.
1054	fn cbf_inc_chroma_ac(f: &Frame, run: &SliceRun, mb: usize, c: usize, blk: usize, here: &Partial)
1055	-> usize
1056	{
1057	let mut terms = [0usize; 2];
1058	for (i, side) in chroma4_ab(f, run, mb, blk).into_iter().enumerate() {
1059	terms[i] = match side {
1060	None => cbf_term(None, None),
1061	Some((n, k)) => {
1062	let (kind, cbp, cbf) = if n == mb {
1063	(here.kind, here.cbp_chroma, &here.cbf)
1064	} else {
1065	(f.kind[n], f.cbp_chroma[n], &f.cbf[n])
1066	};
1067	// An alternating current block exists only where the whole chroma pattern is coded.
1068	let flag = if cbp == 2 { Some(cbf.chroma_ac[c][k]) } else { None };
1069	cbf_term(Some(kind), flag)
1070	},
1071	};
1072	}
1073	weigh(terms)
1074	}
1075
1076	/// Walks one arithmetically coded slice's macroblocks (§7.3.4).
1077	///
1078	/// Where a slice coded with the length tables ends at its payload, this one ends where the coder says
1079	/// it does: an `end_of_slice_flag` after every macroblock, decoded by the terminating process. There
1080	/// is no `more_rbsp_data` test to fall back on, because the arithmetic decoder reads a little past
1081	/// the last byte the encoder wrote.
1082	fn slice_data_cabac(f: &mut Frame, run: &mut SliceRun, u: &Unit, first_mb: usize, at: usize)
1083	-> Outcome<()>
1084	{
1085	let mut e = res!(Entropy::new(&u.body, at, run.qp));
1086	let mut mb = first_mb;
1087	let total = f.mbs_w * f.mbs_h;
1088	loop {
1089	if mb >= total {
1090	return Err(err!(
1091	"A slice ran past macroblock {} of a picture that holds {}.", mb, total;
1092	Invalid, Input, Decode));
1093	}
1094	res!(macroblock_cabac(f, run, &mut e, mb));
1095	e.prev = Some(mb);
1096	mb += 1;
1097	if e.c.terminate() == 1 {
1098	break;
1099	}
1100	}
1101	Ok(())
1102	}
1103
1104	/// Reads and reconstructs one macroblock of an arithmetically coded slice (§7.3.5).
1105	fn macroblock_cabac(f: &mut Frame, run: &mut SliceRun, e: &mut Entropy, mb: usize) -> Outcome<()> {
1106	let mb_type = res!(read_mb_type(f, run, e, mb));
1107	if mb_type == 25 {
1108	return pcm_cabac(f, run, e, mb);
1109	}
1110	let (kind, mut cbp_luma, mut cbp_chroma, pred16) = if mb_type == 0 {
1111	(Kind::I4x4, 0u8, 0u8, Mode16::Dc)
1112	} else {
1113	let k = (mb_type - 1) as usize;
1114	let pred = res!(Mode16::of((k % 4) as u32));
1115	let chroma = ((k / 4) % 3) as u8;
1116	let luma = if k >= 12 { 15u8 } else { 0 };
1117	(Kind::I16x16, luma, chroma, pred)
1118	};
1119	let mut kind = kind;
1120	if kind == Kind::I4x4 && run.transform_8x8 && res!(read_transform_8x8(f, run, e, mb)) {
1121	kind = Kind::I8x8;
1122	}
1123	let mut modes = [2u8; 16];
1124	if kind == Kind::I4x4 {
1125	for i in 0..16 {
1126	let predicted = res!(predicted_mode(f, run, mb, i, &modes, kind));
1127	modes[i] = res!(read_mode_cabac(e, predicted));
1128	}
1129	} else if kind == Kind::I8x8 {
1130	for i in 0..4 {
1131	let predicted = res!(predicted_mode(f, run, mb, i * 4, &modes, kind));
1132	let m = res!(read_mode_cabac(e, predicted));
1133	for k in 0..4 {
1134	modes[i * 4 + k] = m;
1135	}
1136	}
1137	}
1138	let chroma_code = res!(read_chroma_mode(f, run, e, mb));
1139	let chroma_mode = res!(ModeC::of(chroma_code));
1140	if kind != Kind::I16x16 {
1141	let (luma, chroma) = res!(read_cbp(f, run, e, mb));
1142	cbp_luma = luma;
1143	cbp_chroma = chroma;
1144	}
1145	let mut qp = run.qp;
1146	let mut moved = false;
1147	if cbp_luma > 0 \|\| cbp_chroma > 0 \|\| kind == Kind::I16x16 {
1148	let delta = res!(read_qp_delta(f, e));
1149	if !(-26..=25).contains(&delta) {
1150	return Err(err!(
1151	"An mb_qp_delta of {} was coded, and it runs from -26 to 25.", delta;
1152	Invalid, Input, Decode));
1153	}
1154	moved = delta != 0;
1155	qp = (run.qp + delta + 52).rem_euclid(52);
1156	run.qp = qp;
1157	}
1158	// The residual, block by block, with each block's flag kept for the next block's context.
1159	let mut luma_dc = [0i32; 16];
1160	let mut luma = [[0i32; 16]; 16];
1161	let mut luma8 = [[0i32; 64]; 4];
1162	let mut chroma_dc = [[0i32; 4]; 2];
1163	let mut chroma = [[[0i32; 16]; 4]; 2];
1164	let mut here = Partial {
1165	kind,
1166	cbp_luma,
1167	cbp_chroma,
1168	cbf: Cbf::default(),
1169	};
1170
1171	if kind == Kind::I16x16 {
1172	let inc = cbf_inc_luma_dc(f, run, mb) as u32;
1173	let mut out = [0i32; 16];
1174	here.cbf.luma_dc = res!(cabac::residual(&mut e.c, &mut e.x, Cat::LumaDc, Some(inc), &mut out));
1175	for (i, at) in ZIGZAG_4X4.iter().enumerate() {
1176	luma_dc[*at] = out[i];
1177	}
1178	}
1179	for i8 in 0..4usize {
1180	if cbp_luma & (1 << i8) == 0 {
1181	continue;
1182	}
1183	if kind == Kind::I8x8 {
1184	// A block of sixty-four coefficients, read whole. CAVLC has no table for that and reads
1185	// four interleaved blocks of sixteen instead; the arithmetic coder has no such limit,
1186	// and it carries no coded_block_flag for the block either (§7.3.5.3.3).
1187	res!(cabac::residual(&mut e.c, &mut e.x, Cat::Luma8x8, None, &mut luma8[i8]));
1188	here.cbf.luma8[i8] = true;
1189	continue;
1190	}
1191	let (cat, start) = if kind == Kind::I16x16 {
1192	(Cat::LumaAc, 1usize)
1193	} else {
1194	(Cat::Luma4x4, 0)
1195	};
1196	for i4 in 0..4usize {
1197	let blk = i8 * 4 + i4;
1198	let inc = cbf_inc_luma4(f, run, mb, blk, &here) as u32;
1199	let mut out = [0i32; 16];
1200	let held = &mut out[..cat.coeffs()];
1201	here.cbf.luma4[blk] =
1202	res!(cabac::residual(&mut e.c, &mut e.x, cat, Some(inc), held));
1203	for i in 0..cat.coeffs() {
1204	luma[blk][ZIGZAG_4X4[start + i]] = out[i];
1205	}
1206	}
1207	}
1208	if cbp_chroma & 3 != 0 {
1209	for c in 0..2usize {
1210	let inc = cbf_inc_chroma_dc(f, run, mb, c) as u32;
1211	here.cbf.chroma_dc[c] = res!(cabac::residual(
1212	&mut e.c, &mut e.x, Cat::ChromaDc, Some(inc), &mut chroma_dc[c]));
1213	}
1214	}
1215	if cbp_chroma & 2 != 0 {
1216	for c in 0..2usize {
1217	for i in 0..4usize {
1218	let inc = cbf_inc_chroma_ac(f, run, mb, c, i, &here) as u32;
1219	let mut out = [0i32; 15];
1220	here.cbf.chroma_ac[c][i] = res!(cabac::residual(
1221	&mut e.c, &mut e.x, Cat::ChromaAc, Some(inc), &mut out));
1222	for (k, v) in out.iter().enumerate() {
1223	chroma[c][i][ZIGZAG_4X4[1 + k]] = *v;
1224	}
1225	}
1226	}
1227	}
1228
1229	if std::env::var("H264_TRACE").is_ok() && mb < 3 {
1230	eprintln!("mb {} type {} kind {:?} cbpL {} cbpC {} qp {} p16 {:?} ch {:?} modes {:?} \
1231	dc {:?} blk0 {:?} big0 {:?}",
1232	mb, mb_type, kind, cbp_luma, cbp_chroma, qp, pred16, chroma_mode, &modes[..4],
1233	&luma_dc[..4], &luma[0][..4], &luma8[0][..4]);
1234	}
1235	f.slice_of[mb] = Some(run.index);
1236	f.kind[mb] = kind;
1237	f.qp[mb] = qp;
1238	f.modes[mb] = modes;
1239	f.big[mb] = kind == Kind::I8x8;
1240	f.cbp_luma[mb] = cbp_luma;
1241	f.cbp_chroma[mb] = cbp_chroma;
1242	f.chroma_mode[mb] = chroma_code as u8;
1243	f.qp_moved[mb] = moved;
1244	f.cbf[mb] = here.cbf;
1245
1246	res!(reconstruct(f, run, mb, kind, qp, pred16, chroma_mode, &modes, &luma_dc, &luma, &luma8,
1247	&chroma_dc, &chroma));
1248	Ok(())
1249	}
1250
1251	/// Reads a raw-sample macroblock out of an arithmetically coded slice (§7.3.5, §9.3.1.2).
1252	///
1253	/// The samples are not entropy coded at all. They begin at the next byte boundary after the
1254	/// terminating bin that named the macroblock, and the arithmetic decoder is started afresh on the
1255	/// byte after them rather than carried across, which is what makes the bitstream position matter
1256	/// here: get it wrong and everything after this macroblock in the slice is noise.
1257	fn pcm_cabac(f: &mut Frame, run: &mut SliceRun, e: &mut Entropy, mb: usize) -> Outcome<()> {
1258	let at = e.byte();
1259	// Two hundred and fifty-six luma samples, then two of sixty-four for a 4:2:0 macroblock.
1260	let need = 256 + 128;
1261	let end = match at.checked_add(need) {
1262	Some(end) if end <= e.body.len() => end,
1263	_ => return Err(err!(
1264	"A raw-sample macroblock needs {} bytes from byte {} of a payload of {}.",
1265	need, at, e.body.len(); Invalid, Input, Decode)),
1266	};
1267	let raw = &e.body[at..end];
1268	let (mx, my) = ((mb % f.mbs_w) * 16, (mb / f.mbs_w) * 16);
1269	for y in 0..16 {
1270	for x in 0..16 {
1271	f.pic.y.put(mx + x, my + y, raw[y * 16 + x]);
1272	}
1273	}
1274	let (cx, cy) = ((mb % f.mbs_w) * 8, (mb / f.mbs_w) * 8);
1275	for c in 0..2usize {
1276	for y in 0..8 {
1277	for x in 0..8 {
1278	let v = raw[256 + c * 64 + y * 8 + x];
1279	if c == 0 {
1280	f.pic.cb.put(cx + x, cy + y, v);
1281	} else {
1282	f.pic.cr.put(cx + x, cy + y, v);
1283	}
1284	}
1285	}
1286	}
1287	res!(e.restart(end));
1288	f.slice_of[mb] = Some(run.index);
1289	f.kind[mb] = Kind::Pcm;
1290	f.qp[mb] = 0;
1291	f.modes[mb] = [2u8; 16];
1292	f.counts[mb] = [16u8; 24];
1293	f.big[mb] = false;
1294	// A raw-sample macroblock is named in every neighbour rule of clause 9.3.3.1.1 in its own right,
1295	// so the patterns and flags recorded here are never read; they are left at nought rather than
1296	// invented.
1297	Ok(())
1298	}
1299
1300	/// The mode a four-by-four or eight-by-eight block is predicted to take (§8.3.1.1).
1301	///
1302	/// The smaller of the modes its left and upper neighbours used -- but **only where both of the
1303	/// macroblocks holding them are available**. If either is missing, the specification sets
1304	/// `dcPredModePredictedFlag` and both modes become the direct current one, not just the missing
1305	/// side's. Taking the minimum of the one available neighbour and a notional 2 instead gives a
1306	/// different answer whenever that neighbour's mode is below 2, which is every vertical and every
1307	/// horizontal block along the top and left edges of a picture.
1308	fn predicted_mode(f: &Frame, run: &SliceRun, mb: usize, blk: usize, here: &[u8; 16],
1309	here_kind: Kind) -> Outcome<u8>
1310	{
1311	let (bx, by) = blk_xy(blk);
1312	let around = f.around(mb, run.index);
1313	// Which macroblock holds each neighbour, and which of its blocks.
1314	let left = if bx > 0 {
1315	Some((mb, blk_index(bx - 1, by)))
1316	} else {
1317	around[0].map(\|a\| (a, blk_index(3, by)))
1318	};
1319	let above = if by > 0 {
1320	Some((mb, blk_index(bx, by - 1)))
1321	} else {
1322	around[1].map(\|a\| (a, blk_index(bx, 3)))
1323	};
1324	let (left, above) = match (left, above) {
1325	(Some(l), Some(a)) => (l, a),
1326	// Either one missing, and the prediction is the direct current mode.
1327	_ => return Ok(2),
1328	};
1329	let of = \|(a, i): (usize, usize)\| -> u8 {
1330	// A neighbour inside this macroblock has been read but not yet recorded against the
1331	// picture, so it is taken from the array being built. Reading it from the picture instead
1332	// gives every one of them the direct current mode, which decodes the first few blocks of a
1333	// macroblock correctly and the rest wrongly.
1334	let kind = if a == mb { here_kind } else { f.kind[a] };
1335	match kind {
1336	Kind::I4x4 \| Kind::I8x8 => if a == mb { here[i] } else { f.modes[a][i] },
1337	// A neighbour predicted whole, or carried raw, offers no direction.
1338	_ => 2,
1339	}
1340	};
1341	Ok(of(left).min(of(above)))
1342	}
1343
1344	/// The four-by-four block at a position within a macroblock, in the order the blocks are walked.
1345	fn blk_index(bx: usize, by: usize) -> usize {
1346	let quad = (by / 2) * 2 + (bx / 2);
1347	let within = (by % 2) * 2 + (bx % 2);
1348	quad * 4 + within
1349	}
1350
1351	/// Reads one block's prediction mode, given the mode predicted for it (§7.3.5.1).
1352	fn read_mode(b: &mut Bits, predicted: u8) -> Outcome<u8> {
1353	if res!(b.flag()) {
1354	return Ok(predicted);
1355	}
1356	let rem = res!(b.u(3)) as u8;
1357	Ok(if rem < predicted { rem } else { rem + 1 })
1358	}
1359
1360	/// The `nC` a luma block's `coeff_token` is read with (§9.2.1).
1361	fn luma_nc(f: &Frame, run: &SliceRun, mb: usize, blk: usize, here: &[u8; 24]) -> Outcome<i32> {
1362	let (bx, by) = blk_xy(blk);
1363	let left = if bx > 0 {
1364	Some(here[blk_index(bx - 1, by)] as usize)
1365	} else {
1366	f.around(mb, run.index)[0].map(\|a\| f.counts[a][blk_index(3, by)] as usize)
1367	};
1368	let above = if by > 0 {
1369	Some(here[blk_index(bx, by - 1)] as usize)
1370	} else {
1371	f.around(mb, run.index)[1].map(\|a\| f.counts[a][blk_index(bx, 3)] as usize)
1372	};
1373	Ok(cavlc::nc(left, above))
1374	}
1375
1376	/// The same for a chroma block, whose four blocks sit in plain raster order (§6.4.7).
1377	fn chroma_nc(f: &Frame, run: &SliceRun, mb: usize, c: usize, blk: usize, here: &[u8; 24])
1378	-> Outcome<i32>
1379	{
1380	let (bx, by) = (blk % 2, blk / 2);
1381	let base = 16 + c * 4;
1382	let left = if bx > 0 {
1383	Some(here[base + by * 2] as usize)
1384	} else {
1385	f.around(mb, run.index)[0].map(\|a\| f.counts[a][base + by * 2 + 1] as usize)
1386	};
1387	let above = if by > 0 {
1388	Some(here[base + bx] as usize)
1389	} else {
1390	f.around(mb, run.index)[1].map(\|a\| f.counts[a][base + 2 + bx] as usize)
1391	};
1392	Ok(cavlc::nc(left, above))
1393	}
1394
1395	/// Builds the edges around a block of the luma plane.
1396	///
1397	/// `n` is how many samples of the row above are wanted -- four for a four-by-four block, eight for
1398	/// an eight-by-eight one and sixteen for a whole macroblock -- and `right` how many more above and
1399	/// to the right. Availability is asked of the four-by-four block grid, which is where the answer
1400	/// actually lives: a block inside this macroblock is available once it has been reconstructed, and
1401	/// one outside it is available once its macroblock has been and that macroblock is in this slice.
1402	fn luma_edges(f: &Frame, run: &SliceRun, mb: usize, x: usize, y: usize, n: usize, right: usize,
1403	done: &[bool; 16]) -> Edges
1404	{
1405	let (mx, my) = ((mb % f.mbs_w) * 16, (mb / f.mbs_w) * 16);
1406	let mut e = Edges::none();
1407	let ok = \|px: i64, py: i64\| -> bool {
1408	if px < 0 \|\| py < 0 {
1409	return false;
1410	}
1411	let (px, py) = (px as usize, py as usize);
1412	let nb = (px / 16) + (py / 16) * f.mbs_w;
1413	if nb == mb {
1414	// Inside this macroblock: available once the block holding it has been written.
1415	done[blk_index((px % 16) / 4, (py % 16) / 4)]
1416	} else {
1417	px < f.pic.y.w && py < f.pic.y.h && f.available(nb as i64, run.index)
1418	}
1419	};
1420	let ax = (mx + x) as i64;
1421	let ay = (my + y) as i64;
1422	e.top_ok = ok(ax, ay - 1);
1423	if e.top_ok {
1424	for i in 0..n {
1425	e.top[i] = f.pic.y.at(mx + x + i, (my + y).wrapping_sub(1)).unwrap_or(0) as i32;
1426	}
1427	}
1428	if right > 0 {
1429	e.right_ok = ok(ax + n as i64, ay - 1);
1430	if e.right_ok {
1431	for i in 0..right {
1432	e.top[n + i] = f.pic.y.at(mx + x + n + i, (my + y).wrapping_sub(1)).unwrap_or(0)
1433	as i32;
1434	}
1435	}
1436	}
1437	e.left_ok = ok(ax - 1, ay);
1438	if e.left_ok {
1439	for i in 0..n {
1440	e.left[i] = f.pic.y.at((mx + x).wrapping_sub(1), my + y + i).unwrap_or(0) as i32;
1441	}
1442	}
1443	e.corner_ok = ok(ax - 1, ay - 1);
1444	if e.corner_ok {
1445	e.corner = f.pic.y.at((mx + x).wrapping_sub(1), (my + y).wrapping_sub(1)).unwrap_or(0)
1446	as i32;
1447	}
1448	if right > 0 && !e.right_ok {
1449	e.pad_right(n, n + right);
1450	}
1451	e
1452	}
1453
1454	/// Builds the edges around a whole chroma block, which is a macroblock's worth.
1455	fn chroma_edges(f: &Frame, run: &SliceRun, mb: usize, c: usize) -> Edges {
1456	let (cx, cy) = ((mb % f.mbs_w) * 8, (mb / f.mbs_w) * 8);
1457	let plane = if c == 0 { &f.pic.cb } else { &f.pic.cr };
1458	let n = f.around(mb, run.index);
1459	let mut e = Edges::none();
1460	e.top_ok = n[1].is_some();
1461	if e.top_ok {
1462	for i in 0..8 {
1463	e.top[i] = plane.at(cx + i, cy.wrapping_sub(1)).unwrap_or(0) as i32;
1464	}
1465	}
1466	e.left_ok = n[0].is_some();
1467	if e.left_ok {
1468	for i in 0..8 {
1469	e.left[i] = plane.at(cx.wrapping_sub(1), cy + i).unwrap_or(0) as i32;
1470	}
1471	}
1472	e.corner_ok = n[3].is_some();
1473	if e.corner_ok {
1474	e.corner = plane.at(cx.wrapping_sub(1), cy.wrapping_sub(1)).unwrap_or(0) as i32;
1475	}
1476	e
1477	}
1478
1479	/// Predicts, transforms and writes one macroblock's samples.
1480	#[allow(clippy::too_many_arguments)]
1481	fn reconstruct(f: &mut Frame, run: &SliceRun, mb: usize, kind: Kind, qp: i32, pred16: Mode16,
1482	chroma_mode: ModeC, modes: &[u8; 16], luma_dc: &[i32; 16], luma: &[[i32; 16]; 16],
1483	luma8: &[[i32; 64]; 4], chroma_dc: &[[i32; 4]; 2], chroma: &[[[i32; 16]; 4]; 2]) -> Outcome<()>
1484	{
1485	let (mx, my) = ((mb % f.mbs_w) * 16, (mb / f.mbs_w) * 16);
1486	let depth = 8u32;
1487	let mut done = [false; 16];
1488	match kind {
1489	Kind::I16x16 => {
1490	let e = luma_edges(f, run, mb, 0, 0, 16, 0, &done);
1491	let pred = intra::pred_16x16(pred16, &e, depth);
1492	let dc = transform::luma_dc(luma_dc, &f.w_luma, qp);
1493	for blk in 0..16 {
1494	let (bx, by) = blk_xy(blk);
1495	let mut c = luma[blk];
1496	c[0] = dc[by * 4 + bx];
1497	let d = transform::scale_4x4(&c, &f.w_luma, qp, true);
1498	let r = transform::inverse_4x4(&d);
1499	for yy in 0..4 {
1500	for xx in 0..4 {
1501	let px = bx * 4 + xx;
1502	let py = by * 4 + yy;
1503	let v = pred[py * 16 + px] + r[yy * 4 + xx];
1504	f.pic.y.put(mx + px, my + py, v.clamp(0, 255) as u8);
1505	}
1506	}
1507	done[blk] = true;
1508	}
1509	},
1510	Kind::I4x4 => {
1511	for blk in 0..16 {
1512	let (bx, by) = blk_xy(blk);
1513	let (x, y) = (bx * 4, by * 4);
1514	let e = luma_edges(f, run, mb, x, y, 4, 4, &done);
1515	let mode = res!(Mode::of(modes[blk] as u32));
1516	let pred = intra::pred_4x4(mode, &e, depth);
1517	let d = transform::scale_4x4(&luma[blk], &f.w_luma, qp, false);
1518	let r = transform::inverse_4x4(&d);
1519	for yy in 0..4 {
1520	for xx in 0..4 {
1521	let v = pred[yy * 4 + xx] + r[yy * 4 + xx];
1522	f.pic.y.put(mx + x + xx, my + y + yy, v.clamp(0, 255) as u8);
1523	}
1524	}
1525	done[blk] = true;
1526	}
1527	},
1528	Kind::I8x8 => {
1529	for i8 in 0..4usize {
1530	let (x, y) = ((i8 % 2) * 8, (i8 / 2) * 8);
1531	let e = luma_edges(f, run, mb, x, y, 8, 8, &done);
1532	let mode = res!(Mode::of(modes[i8 * 4] as u32));
1533	let pred = intra::pred_8x8(mode, &e, depth);
1534	let mut c = [0i32; 64];
1535	for (i, at) in ZIGZAG_8X8.iter().enumerate() {
1536	c[*at] = luma8[i8][i];
1537	}
1538	let d = transform::scale_8x8(&c, &f.w_luma, qp);
1539	let r = transform::inverse_8x8(&d);
1540	for yy in 0..8 {
1541	for xx in 0..8 {
1542	let v = pred[yy * 8 + xx] + r[yy * 8 + xx];
1543	f.pic.y.put(mx + x + xx, my + y + yy, v.clamp(0, 255) as u8);
1544	}
1545	}
1546	for k in 0..4 {
1547	done[i8 * 4 + k] = true;
1548	}
1549	}
1550	},
1551	Kind::Pcm \| Kind::Absent => {},
1552	}
1553	// Chroma, both components the same way.
1554	let (cx, cy) = ((mb % f.mbs_w) * 8, (mb / f.mbs_w) * 8);
1555	for c in 0..2usize {
1556	let e = chroma_edges(f, run, mb, c);
1557	let pred = intra::pred_chroma(chroma_mode, &e, depth);
1558	let offset = if c == 0 { f.pps.cb_qp_offset } else { f.pps.cr_qp_offset };
1559	let cqp = transform::chroma_qp(qp, offset);
1560	let w = if c == 0 { &f.w_cb } else { &f.w_cr };
1561	let dc = transform::chroma_dc(&chroma_dc[c], w, cqp);
1562	for blk in 0..4usize {
1563	let (bx, by) = (blk % 2, blk / 2);
1564	let mut coeffs = chroma[c][blk];
1565	coeffs[0] = dc[by * 2 + bx];
1566	let d = transform::scale_4x4(&coeffs, w, cqp, true);
1567	let r = transform::inverse_4x4(&d);
1568	for yy in 0..4 {
1569	for xx in 0..4 {
1570	let px = bx * 4 + xx;
1571	let py = by * 4 + yy;
1572	let v = pred[py * 8 + px] + r[yy * 4 + xx];
1573	let s = v.clamp(0, 255) as u8;
1574	if c == 0 {
1575	f.pic.cb.put(cx + px, cy + py, s);
1576	} else {
1577	f.pic.cr.put(cx + px, cy + py, s);
1578	}
1579	}
1580	}
1581	}
1582	}
1583	Ok(())
1584	}
1585
1586	/// What one slice asks of the deblocking filter (§7.4.3).
1587	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1588	pub struct Filter {
1589	pub idc: u32, // 0 filters everything, 1 nothing, 2 all but the slice edges
1590	pub alpha: i32, // offset added to the filter's first threshold
1591	pub beta: i32, // and to its second
1592	}
1593
1594	/// A borrow of the frame's fields the deblocking filter needs.
1595	pub struct View<'a> {
1596	pub pic: &'a mut Picture,
1597	pub mbs_w: usize, // the width in macroblocks
1598	pub mbs_h: usize, // and the height
1599	pub qp: &'a [i32], // each macroblock's quantisation parameter
1600	pub slice_of: &'a [Option<usize>], // which slice each macroblock belongs to
1601	pub big: &'a [bool], // is it coded with the eight-by-eight transform?
1602	pub filters: &'a [Filter], // what each slice asks, in the order the slices were decoded
1603	pub cb_qp_offset: i32, // offset applied to the Cb quantisation parameter
1604	pub cr_qp_offset: i32, // and to Cr
1605	}
1606
1607	fn frame_view<'b>(f: &'b mut Frame) -> View<'b> {
1608	View {
1609	mbs_w: f.mbs_w,
1610	mbs_h: f.mbs_h,
1611	qp: &f.qp,
1612	slice_of: &f.slice_of,
1613	big: &f.big,
1614	filters: &[],
1615	cb_qp_offset: f.pps.cb_qp_offset,
1616	cr_qp_offset: f.pps.cr_qp_offset,
1617	pic: &mut f.pic,
1618	}
1619	}
1620
1621	/// Cuts the picture down to the size the sequence parameter set says it is meant to be shown at.
1622	///
1623	/// A picture is coded in whole macroblocks, so a 1080-line film is coded as 1088 lines and the
1624	/// last eight are not part of it. 669 films in the corpus are exactly that shape.
1625	fn crop(f: &Frame) -> Picture {
1626	let (w, h) = (f.sps.width as usize, f.sps.height as usize);
1627	Picture {
1628	y: f.pic.y.cropped(w, h),
1629	cb: f.pic.cb.cropped(w / 2, h / 2),
1630	cr: f.pic.cr.cropped(w / 2, h / 2),
1631	}
1632	}
1633
1634	#[cfg(test)]
1635	mod tests {
1636	use super::*;
1637
1638	#[test]
1639	fn test_the_blocks_are_walked_a_quadrant_at_a_time_01() -> Outcome<()> {
1640	// Not raster order. The sixteen four-by-four blocks of a macroblock are walked as four
1641	// quadrants of four, and each quadrant as four blocks -- so block 1 sits to the right of
1642	// block 0 and block 4 sits eight samples to its right, not four. A decoder that walked them
1643	// in raster order would predict half of them from neighbours it has not decoded.
1644	let want = [
1645	(0, 0), (1, 0), (0, 1), (1, 1),
1646	(2, 0), (3, 0), (2, 1), (3, 1),
1647	(0, 2), (1, 2), (0, 3), (1, 3),
1648	(2, 2), (3, 2), (2, 3), (3, 3),
1649	];
1650	for (i, xy) in want.iter().enumerate() {
1651	req!(blk_xy(i), *xy, "block {} sits somewhere else", i);
1652	// And the inverse agrees, which is what the neighbour lookups rely on.
1653	req!(blk_index(xy.0, xy.1), i);
1654	}
1655	Ok(())
1656	}
1657
1658	#[test]
1659	fn test_the_pattern_table_is_a_permutation_02() -> Outcome<()> {
1660	// Table 9-4's intra column maps 48 code numbers onto the 48 patterns a macroblock with
1661	// colour may have, one for one. A transcription that repeated a value would silently
1662	// decode two different pictures the same way, and one that dropped a value would make a
1663	// legal picture undecodable, so the check is that it is a permutation of 0 to 47.
1664	let mut seen = [false; 48];
1665	for v in CBP_INTRA {
1666	let v = v as usize;
1667	let already = seen.get(v).copied().unwrap_or(true);
1668	req!(already, false, "the pattern {} appears twice in the table", v);
1669	seen[v] = true;
1670	}
1671	req!(seen.iter().all(\|s\| *s), true, "the table does not cover every pattern");
1672	Ok(())
1673	}
1674
1675	#[test]
1676	fn test_the_quantiser_wraps_rather_than_clipping_03() -> Outcome<()> {
1677	// A macroblock's quantisation parameter is the previous one plus a delta, modulo 52. It
1678	// wraps so that any value is reachable from any other in one step, and a decoder that
1679	// clipped instead would quantise a macroblock at 51 where the stream asked for 0 -- a
1680	// block of flat grey in the middle of a detailed picture.
1681	let step = \|prev: i32, delta: i32\| (prev + delta + 52).rem_euclid(52);
1682	req!(step(30, 5), 35);
1683	req!(step(2, -5), 49, "a delta below nought clipped instead of wrapping");
1684	req!(step(50, 5), 3, "a delta past 51 clipped instead of wrapping");
1685	req!(step(0, 0), 0);
1686	Ok(())
1687	}
1688	}