Oregami
Repositories/oxedyne/fe2o3

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

54.7 KiB, 129 runs

created by r1870400018:20502, 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 clauses 7.3.8.1 to 7.3.8.11 meets the decoding processes of clause 8.
4//! The two are interleaved rather than done in turn, and they have to be: every block is predicted
5//! from the samples around it, so a block cannot be predicted until the ones before it in coding
6//! order have been *reconstructed*, not merely parsed.
7//!
8//! The shape of the walk, outermost first:
9//!
10//! - **A row of coding tree blocks at a time**, because every photograph in the corpus is coded in
11//! wavefronts: each row is its own piece of arithmetic-coded data, beginning at a byte offset the
12//! slice header carries, and starting from the context state saved after the second block of the
13//! row above.
14//! - **A coding tree block** is a quadtree. Each node either splits into four or becomes a coding
15//! unit, and the depth it stops at is what the picture spends its bits on: flat sky stops early,
16//! an eyelash goes all the way down.
17//! - **A coding unit** carries one or four intra prediction modes for luma and one for chroma, and
18//! then a transform tree of its own, which may cut it up again.
19//! - **A transform block** is predicted, its residual read, transformed back and added.
20//!
21//! # What this decodes and what it refuses
22//!
23//! Intra pictures in 4:2:0 at eight bits, which is every HEIC photograph in the library it was
24//! written against. Four things are refused where they are read rather than decoded into a wrong
25//! picture, and a refusal names the tool so a photograph that needs one says which: another chroma
26//! format, another bit depth, raw sample blocks, and a picture cut into tiles.
27//!
28//! Scaling lists are **not** among them. Two in five of the survey corpus carry their own, and the
29//! default lists are not flat, so reading the flag as "no scaling" would quantise every block
30//! wrongly; they are read and applied.
31//!
32//! Palettes, cross-component prediction and residual rotation are enabled by the sequence and
33//! picture parameter set *extensions*, and this reader stops before the extension flags. So a
34//! stream using one is neither refused nor decoded correctly -- it is outside what is read at all,
35//! which is a weaker guarantee than a refusal and is stated here rather than implied.
36//!
37//! # The one thing that has to be got right and cannot be seen
38//!
39//! Sample availability. A block predicts from its neighbours only where those neighbours have
40//! already been decoded, and "already" is in the zig-zag order the quadtree is walked in, not in
41//! raster order. A decoder that is careless about it predicts from samples that are still nought
42//! and produces a picture with a plausible-looking grid of darker blocks. What is kept here is one
43//! flag per four-by-four block, set as that block is written, which is exactly the question being
44//! asked and is impossible to get subtly wrong.
45//!
46//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
47//! Anthropic Claude
48
49use crate::hevc::{
50 filter,
51 cabac::{
52 Cabac,
53 Contexts,
54 Rows,
55 Set,
56 },
57 intra,
58 scan::{
59 Order,
60 Scans,
61 },
62 transform,
63 Pps,
64 Slice,
65 Sps,
66};
67
68use oxedyne_fe2o3_core::prelude::*;
69
70/// One component's samples.
71#[derive(Clone, Debug)]
72pub struct Plane {
73 pub w: usize, // width in samples
74 pub h: usize, // height in samples
75 pub px: Vec<u16>, // row by row
76}
77
78impl Plane {
79
80 fn new(w: usize, h: usize) -> Self {
81 Self { w, h, px: vec![0; w * h] }
82 }
83
84 /// The same, for a caller assembling a grid out of tiles.
85 pub fn empty(w: usize, h: usize) -> Self {
86 Self::new(w, h)
87 }
88
89 pub fn at(&self, x: usize, y: usize) -> Option<u16> {
90 if x < self.w && y < self.h {
91 self.px.get(y * self.w + x).copied()
92 } else {
93 None
94 }
95 }
96
97 /// Writes one sample, ignoring a position outside the plane.
98 fn put(&mut self, x: usize, y: usize, v: u16) {
99 if x < self.w && y < self.h {
100 self.px[y * self.w + x] = v;
101 }
102 }
103
104 /// The plane cropped to a window at its top left.
105 ///
106 /// A coded picture is a whole number of coding tree blocks and a shown one is not, so a
107 /// 1920 by 1080 film is coded 1920 by 1088 and the eight rows the encoder filled to reach the
108 /// block boundary are not part of the picture. This is what takes them off.
109 pub fn cropped(&self, w: usize, h: usize) -> Self {
110 self.window(0, 0, w, h)
111 }
112
113 /// The rectangle of the plane starting at a position, clamped to what is there.
114 pub fn window(&self, x: usize, y: usize, w: usize, h: usize) -> Self {
115 let mut out = Self::new(w, h);
116 for row in 0..h {
117 let sy = y + row;
118 if sy >= self.h || x >= self.w {
119 break;
120 }
121 let take = w.min(self.w - x);
122 let from = sy * self.w + x;
123 let at = row * w;
124 out.px[at..at + take].copy_from_slice(&self.px[from..from + take]);
125 }
126 out
127 }
128}
129
130/// A decoded picture, before it is turned into anything anybody can look at.
131#[derive(Clone, Debug)]
132pub struct Picture {
133 pub y: Plane, // brightness
134 pub cb: Plane, // colour difference, at half the width and half the height
135 pub cr: Plane, // the other one
136 pub depth: u32, // bits a sample
137}
138
139impl Picture {
140
141 /// Copies another picture into this one at a position, for assembling a grid of tiles.
142 ///
143 /// The colour planes are half size both ways, so the position halves with them.
144 pub fn paste(&mut self, from: &Self, x: usize, y: usize) {
145 for (dst, src, at) in [
146 (&mut self.y, &from.y, (x, y)),
147 (&mut self.cb, &from.cb, (x / 2, y / 2)),
148 (&mut self.cr, &from.cr, (x / 2, y / 2)),
149 ] {
150 for row in 0..src.h {
151 let into = at.1 + row;
152 if into >= dst.h {
153 break;
154 }
155 let take = src.w.min(dst.w.saturating_sub(at.0));
156 let (a, b) = (into * dst.w + at.0, row * src.w);
157 dst.px[a..a + take].copy_from_slice(&src.px[b..b + take]);
158 }
159 }
160 }
161
162 /// The picture cropped to the size it is meant to be shown at, from its top left corner.
163 ///
164 /// The colour planes are half size both ways and are rounded **up**, since a picture of an odd
165 /// width still has a colour sample for its last column.
166 pub fn cropped(&self, w: usize, h: usize) -> Self {
167 self.window(0, 0, w, h)
168 }
169
170 /// The rectangle of the picture that is meant to be shown.
171 ///
172 /// A window need not sit at the corner: a stabilised film is coded larger than it shows and
173 /// moves the window about inside it, so taking the corner instead moves the whole picture.
174 pub fn window(&self, x: usize, y: usize, w: usize, h: usize) -> Self {
175 Self {
176 y: self.y.window(x, y, w, h),
177 cb: self.cb.window(x / 2, y / 2, w.div_ceil(2), h.div_ceil(2)),
178 cr: self.cr.window(x / 2, y / 2, w.div_ceil(2), h.div_ceil(2)),
179 depth: self.depth,
180 }
181 }
182}
183
184/// What one coding tree block's sample adaptive offset filter was told to do.
185///
186/// Parsed with the block and applied to the whole picture at the end, because the filter reads
187/// samples the block after this one will write.
188#[derive(Clone, Copy, Debug, Default)]
189pub struct Sao {
190 pub kind: [u8; 3], // per component: 0 nothing, 1 a band offset, 2 an edge offset
191 pub offset: [[i32; 4]; 3], // the four offsets, already signed
192 pub band: [u8; 3], // which band the offsets start at, for a band offset
193 pub class: [u8; 3], // which direction the edge is looked for in
194}
195
196/// The arithmetic decoder and the contexts it reads against, which travel together.
197struct Ent<'a> {
198 cabac: Cabac<'a>, // over this row's piece of the data
199 ctxs: Contexts, // the context variables, which carry over between rows
200}
201
202impl<'a> Ent<'a> {
203
204 fn bin(&mut self, set: Set, inc: usize) -> Outcome<u32> {
205 let ctx = res!(self.ctxs.at(set, inc));
206 Ok(self.cabac.bin(ctx))
207 }
208
209 /// A run of ones ended by a nought, against one context each, up to `most` of them.
210 fn unary(&mut self, set: Set, incs: &[usize], most: usize) -> Outcome<u32> {
211 let mut n = 0u32;
212 while (n as usize) < most {
213 let inc = incs[(n as usize).min(incs.len() - 1)];
214 if res!(self.bin(set, inc)) == 0 {
215 break;
216 }
217 n += 1;
218 }
219 Ok(n)
220 }
221
222 /// The same at even odds, with no context.
223 fn unary_bypass(&mut self, most: usize) -> u32 {
224 let mut n = 0u32;
225 while (n as usize) < most && self.cabac.bypass() == 1 {
226 n += 1;
227 }
228 n
229 }
230}
231
232/// Everything a picture's decoding needs to know about what has been decoded so far.
233struct Frame<'a> {
234 sps: &'a Sps,
235 pps: &'a Pps,
236 slice: &'a Slice, // the slice being read now
237 slice_at: Vec<u16>, // which slice each block is in
238 pic: Picture, // the samples, filled in as the walk goes
239 scans: Scans, // the scan orders, worked out once
240 weights: Option<crate::hevc::Scaling>, // None where the sequence quantises flat
241
242 gw: usize, // the grid the per-block records sit on
243 gh: usize, // and its height
244 ct_depth: Vec<u8>, // quadtree depth of the covering coding unit
245 mode: Vec<u8>, // luma prediction mode of the covering block
246 qp: Vec<i8>, // luma quantisation parameter of the covering unit
247 // Every prediction boundary in an intra picture is a transform boundary too -- a coding unit
248 // split into four prediction blocks has its transform tree forced down to match -- so
249 // recording the transform blocks records both.
250 edge_v: Vec<bool>, // a transform boundary on each block's left?
251 edge_h: Vec<bool>, // and on its top?
252
253 sao: Vec<Sao>, // filter settings, for the pass at the end
254 ctbs_w: usize, // coding tree blocks across the picture
255 ctbs_h: usize, // and down
256
257 qp_prev: i32, // what the next quantisation group predicts from
258 qp_delta: i32, // what the current group's syntax added to it
259 qp_coded: bool, // has the delta been read in this group?
260 qp_now: i32, // in force for the coding unit being decoded
261
262 bypass: bool, // skips the transform and the quantiser?
263 split_intra: bool, // four prediction blocks, forcing the tree one deep
264 pred_y: [u8; 4], // its luma prediction modes, one or four
265 pred_c: u8, // its chroma prediction mode
266 cbf_cb: [bool; 6], // a chroma residual at each transform tree depth?
267 cbf_cr: [bool; 6], // the other component
268 skip_tr: bool, // was this block coded without its transform?
269 cu_x: usize, // where the coding unit starts
270 cu_y: usize, // and down
271 cu_size: usize, // how wide it is
272}
273
274/// Decodes one intra picture out of its single slice.
275///
276/// `data` is the slice segment's entropy-coded bytes **as they arrived**, escaping and all, from
277/// the slice header's end onwards. It has to be the escaped form: the entry point offsets that say
278/// where each row of blocks begins are counted in escaped bytes (§7.4.7.1), so the cut is made here
279/// and each piece unescaped afterwards.
280pub fn picture(sps: &Sps, pps: &Pps, slice: &Slice, data: &[u8]) -> Outcome<Picture> {
281 picture_of(sps, pps, &[(slice, data)])
282}
283
284/// Decodes one intra picture out of the several slices it is cut into.
285///
286/// A photograph is one slice and a film's frame need not be: an encoder that cuts a picture into
287/// four so that four processors may code it writes four slice segments, each with a header of its
288/// own and each beginning at the coding tree block its header names. They arrive here in the order
289/// they were coded, which is the order the picture is walked in.
290///
291/// Two things follow from a picture being cut up, and both are in this function rather than in the
292/// block reader. **A slice predicts from nothing outside itself** -- that is the whole point of
293/// cutting one, since otherwise the pieces could not be coded independently -- so the availability
294/// rule gains a second half beyond decoding order. And the arithmetic decoder starts afresh at each
295/// slice, from contexts initialised at that slice's own quantisation parameter.
296pub fn picture_of(sps: &Sps, pps: &Pps, parts: &[(&Slice, &[u8])]) -> Outcome<Picture> {
297 res!(refuse_what_is_not_built(sps, pps));
298 let slice = match parts.first() {
299 Some((s, _)) => *s,
300 None => return Err(err!("A picture cut into no slices at all."; Invalid, Input, Missing)),
301 };
302 let (w, h) = (sps.coded_w as usize, sps.coded_h as usize);
303 let ctb = sps.ctb_size as usize;
304 let ctbs_w = w.div_ceil(ctb);
305 let ctbs_h = h.div_ceil(ctb);
306 let blocks = ctbs_w * ctbs_h;
307 let (gw, gh) = (w.div_ceil(4), h.div_ceil(4));
308 // Which slice each coding tree block belongs to. The segments tile the picture in raster order,
309 // so a block's slice is settled by where the segments begin -- and a picture whose first
310 // segment does not begin at the first block, or whose segments do not ascend, is one this
311 // decoder would fill in the wrong order rather than one it can draw.
312 let mut slice_at = vec![0u16; blocks];
313 if slice.address != 0 {
314 return Err(err!(
315 "The first slice segment of a picture begins at block {} rather than at its first.",
316 slice.address; Invalid, Input, Decode));
317 }
318 if parts.len() > u16::MAX as usize {
319 return Err(err!(
320 "A picture cut into {} slices, which no encoder writes.", parts.len();
321 Invalid, Input, Excessive));
322 }
323 for (i, (part, _)) in parts.iter().enumerate() {
324 let from = part.address as usize;
325 let to = match parts.get(i + 1) {
326 Some((next, _)) => next.address as usize,
327 None => blocks,
328 };
329 if from >= to || to > blocks {
330 return Err(err!(
331 "Slice segment {} covers blocks {} to {} of a picture of {}. The segments do not \
332 tile it.", i, from, to, blocks; Invalid, Input, Decode));
333 }
334 for a in slice_at.iter_mut().take(to).skip(from) {
335 *a = i as u16;
336 }
337 }
338 let mut frame = Frame {
339 sps,
340 pps,
341 slice,
342 slice_at,
343 pic: Picture {
344 y: Plane::new(w, h),
345 cb: Plane::new(w / 2, h / 2),
346 cr: Plane::new(w / 2, h / 2),
347 depth: sps.luma_bits as u32,
348 },
349 scans: Scans::new(),
350 weights: sps.weights.clone(),
351 gw,
352 gh,
353 ct_depth: vec![0; gw * gh],
354 mode: vec![intra::DC; gw * gh],
355 qp: vec![slice.qp as i8; gw * gh],
356 edge_v: vec![false; gw * gh],
357 edge_h: vec![false; gw * gh],
358 sao: vec![Sao::default(); ctbs_w * ctbs_h],
359 ctbs_w,
360 ctbs_h,
361 qp_prev: slice.qp,
362 qp_delta: 0,
363 qp_coded: false,
364 qp_now: slice.qp,
365 bypass: false,
366 split_intra: false,
367 pred_y: [intra::DC; 4],
368 pred_c: intra::DC,
369 cbf_cb: [false; 6],
370 cbf_cr: [false; 6],
371 skip_tr: false,
372 cu_x: 0,
373 cu_y: 0,
374 cu_size: ctb,
375 };
376
377 // Wavefront coding cuts a slice into one piece a row of blocks, at the offsets its header
378 // names, and starts the arithmetic decoder afresh at each; without it a slice is one piece and
379 // one arithmetic decoder from its first block to its last. Every photograph in the corpus is
380 // coded the first way and a good many films are coded the second, so both are here.
381 for (i, (part, data)) in parts.iter().enumerate() {
382 frame.slice = part;
383 let from = part.address as usize;
384 let to = match parts.get(i + 1) {
385 Some((next, _)) => next.address as usize,
386 None => blocks,
387 };
388 if pps.wavefront {
389 // A slice cut into wavefronts is one piece a row of **its own** blocks, which is the
390 // whole picture where the picture is one slice. A slice that began part way along a
391 // row would have a piece that is neither a row nor a slice, and there is nothing here
392 // that could find its end.
393 if from % ctbs_w != 0 || to % ctbs_w != 0 {
394 return Err(err!(
395 "A slice coded in wavefronts covers blocks {} to {} of a picture {} blocks \
396 wide, so it begins or ends part way along a row.", from, to, ctbs_w;
397 Unimplemented));
398 }
399 let (row0, rows_here) = (from / ctbs_w, (to - from) / ctbs_w);
400 // One piece a row of blocks, each unescaped on its own once the cut has been made in
401 // the escaped bytes.
402 let pieces: Vec<Vec<u8>> = res!(split_rows(data, part, rows_here))
403 .into_iter()
404 .map(crate::hevc::rbsp)
405 .collect();
406 // Each slice starts its rows afresh: the row above the first of them is in another
407 // slice, and a slice inherits nothing from one.
408 let mut rows = Rows::new(part.qp);
409 for (i, piece) in pieces.iter().enumerate() {
410 let ry = row0 + i;
411 let mut ent = Ent {
412 cabac: res!(Cabac::new(piece)),
413 ctxs: rows.begin(),
414 };
415 // Every row of a wavefront-coded picture starts predicting its quantisation
416 // parameter afresh, because the row above may not have been decoded yet where an
417 // encoder ran them in parallel (§8.6.1).
418 frame.qp_prev = part.qp;
419 for rx in 0..ctbs_w {
420 res!(frame.ctu(&mut ent, rx, ry));
421 if rx == 1 {
422 rows.after_second(&ent.ctxs);
423 }
424 // The bin that says whether the slice ends here. It has to be read whether or
425 // not it says so: it moves the arithmetic decoder on.
426 let ended = ent.cabac.terminate();
427 if ended == 1 && !(ry == row0 + rows_here - 1 && rx == ctbs_w - 1) {
428 // A slice that stops early is not a fault in a still picture -- it is a
429 // picture this decoder has misread, and saying so beats returning half of
430 // one.
431 return Err(err!(
432 "The slice ended at block ({}, {}) of {} by {}.",
433 rx, ry, ctbs_w, ctbs_h; Invalid, Input, Decode));
434 }
435 }
436 // A row one block wide never reaches the save above, and the row below it still
437 // has to start from somewhere.
438 if ctbs_w == 1 {
439 rows.after_second(&ent.ctxs);
440 }
441 // The encoder said how long this row's data is; the decoder has just read it. The
442 // two agreeing is the cheapest check there is that the row was read in step, and
443 // it is checkable a row at a time rather than only at the end of the picture --
444 // which is what makes it worth having: it names the row that went wrong.
445 //
446 // A little short is normal. The arithmetic decoder reads ahead into a window it
447 // may not use, and the final bins are coded against bits the encoder never had to
448 // write.
449 let used = ent.cabac.consumed();
450 let have = piece.len();
451 if used > have + 2 || used + 8 < have {
452 return Err(err!(
453 "Row {} of blocks is {} bytes and reading it took {}. The row was read \
454 out of step.", ry, have, used; Invalid, Input, Decode));
455 }
456 }
457 } else {
458 // One arithmetic decoder over the whole slice, and one set of contexts that carries
459 // from each block to the next: there is no row boundary here for anything to be reset
460 // at, which is what wavefront coding adds and this does not have.
461 let piece = crate::hevc::rbsp(data);
462 let mut ent = Ent {
463 cabac: res!(Cabac::new(&piece)),
464 ctxs: Contexts::start(part.qp),
465 };
466 frame.qp_prev = part.qp;
467 for at in from..to {
468 let (rx, ry) = (at % ctbs_w, at / ctbs_w);
469 res!(frame.ctu(&mut ent, rx, ry));
470 let ended = ent.cabac.terminate();
471 if ended == 1 && at != to - 1 {
472 return Err(err!(
473 "A slice covering blocks {} to {} ended at {}.", from, to, at;
474 Invalid, Input, Decode));
475 }
476 }
477 // The same check the rows above are held to, over the whole slice: the encoder said
478 // how long it is and the decoder has just read it.
479 let used = ent.cabac.consumed();
480 let have = piece.len();
481 if used > have + 2 || used + 8 < have {
482 return Err(err!(
483 "A slice of {} bytes took {} to read. It was read out of step.", have, used;
484 Invalid, Input, Decode));
485 }
486 }
487 }
488 // The two in-loop filters, in the order the specification runs them: every block boundary
489 // softened, and then the offsets that put back what quantisation rounded away. The encoder ran
490 // both, so a picture without them is not a rougher picture but a different one.
491 // Whether a filter runs is a slice's own answer, and a picture cut into slices may hold both
492 // answers. Each filter runs over the whole picture where any slice asks for it, which is right
493 // where they agree -- and every picture measured does.
494 let deblocking = parts.iter().any(|(p, _)| p.deblocking);
495 let sao_on = parts.iter().any(|(p, _)| p.sao_luma || p.sao_chroma);
496 // Both filters run over block boundaries wherever they fall, including the ones between
497 // slices. A picture that asks for them to stop at a slice boundary would need the boundaries
498 // carried into the filter, and saying so beats filtering across one that should not be.
499 if parts.len() > 1 && !parts.iter().all(|(p, _)| p.across_slices) && (deblocking || sao_on) {
500 return Err(err!(
501 "A picture cut into {} slices whose loop filters are not to run across the boundaries \
502 between them.", parts.len(); Unimplemented));
503 }
504 if deblocking {
505 let edges = filter::Edges {
506 gw: frame.gw,
507 gh: frame.gh,
508 vertical: &frame.edge_v,
509 horizontal: &frame.edge_h,
510 qp: &frame.qp,
511 chroma_offset: [pps.cb_qp_offset, pps.cr_qp_offset],
512 };
513 filter::deblock(&mut frame.pic, &edges, sps.luma_bits as u32);
514 }
515 if sao_on {
516 filter::sao(&mut frame.pic, &frame.sao, ctbs_w, ctb, sps.luma_bits as u32);
517 }
518 Ok(frame.pic)
519}
520
521fn refuse_what_is_not_built(sps: &Sps, pps: &Pps) -> Outcome<()> {
522 if sps.chroma != 1 {
523 return Err(err!(
524 "This decoder reads 4:2:0 pictures, and this one is chroma format {}.", sps.chroma;
525 Unimplemented));
526 }
527 if sps.luma_bits != 8 || sps.chroma_bits != 8 {
528 return Err(err!(
529 "This decoder reads eight-bit pictures, and this one is {} and {}.",
530 sps.luma_bits, sps.chroma_bits; Unimplemented));
531 }
532 if sps.pcm {
533 return Err(err!(
534 "This picture may carry raw sample blocks, which are not read."; Unimplemented));
535 }
536 if pps.tiles {
537 return Err(err!("This picture is cut into tiles, which are not read."; Unimplemented));
538 }
539 Ok(())
540}
541
542/// Cuts the slice data into one piece a row of blocks, at the entry points the header carries.
543fn split_rows<'a>(data: &'a [u8], slice: &Slice, rows: usize) -> Outcome<Vec<&'a [u8]>> {
544 if slice.entries.is_empty() {
545 if rows != 1 {
546 return Err(err!(
547 "A picture {} rows tall carries no entry points, so only its first row could be \
548 found.", rows; Invalid, Input, Decode));
549 }
550 return Ok(vec![data]);
551 }
552 if slice.entries.len() + 1 != rows {
553 return Err(err!(
554 "The slice header names {} pieces and the picture has {} rows of blocks.",
555 slice.entries.len() + 1, rows; Invalid, Input, Decode));
556 }
557 let mut out = Vec::with_capacity(rows);
558 let mut at = 0usize;
559 for len in &slice.entries {
560 let len = *len as usize;
561 let end = at + len;
562 if end > data.len() {
563 return Err(err!(
564 "A row of blocks is said to end at byte {} of {}.", end, data.len();
565 Invalid, Input, Decode));
566 }
567 out.push(&data[at..end]);
568 at = end;
569 }
570 out.push(&data[at..]);
571 Ok(out)
572}
573
574impl<'a> Frame<'a> {
575
576 /// Where a position sits in the order the picture is decoded in (§6.4.1).
577 ///
578 /// Coding tree blocks in raster order, and within one, four-by-four blocks in **z order** --
579 /// the quadtree's own order, so that the four children of a node are visited before anything to
580 /// their right or below. Interleaving the bits of the two coordinates is exactly that order.
581 fn z_order(&self, x: usize, y: usize) -> u64 {
582 let ctb = self.sps.ctb_size as usize;
583 let block = (y / ctb) * self.ctbs_w + (x / ctb);
584 let (bx, by) = ((x % ctb) / 4, (y % ctb) / 4);
585 let mut z = 0u64;
586 for i in 0..4 {
587 z |= (((bx >> i) & 1) as u64) << (2 * i);
588 z |= (((by >> i) & 1) as u64) << (2 * i + 1);
589 }
590 ((block as u64) << 8) | z
591 }
592
593 /// Whether a neighbouring position may be used by a block at `(cx, cy)`.
594 ///
595 /// Inside the picture, and **earlier in decoding order**. It is decoding order and not "has
596 /// been reconstructed": the four prediction blocks of one coding unit have their modes read
597 /// before any of them is reconstructed, and each of them draws its candidate modes from the one
598 /// before it. A decoder that asks whether the samples exist yet answers "no" there, hands every
599 /// such block the flat mode as its candidate, and picks the wrong mode out of the list -- with
600 /// no change to how many bins were read, so the picture stays in step and comes out wrong.
601 ///
602 /// **And in the same slice.** A slice predicts from nothing outside itself, which is the whole
603 /// point of cutting a picture into slices, so a neighbour on the other side of a slice boundary
604 /// is not available however early it was decoded. One tile, so nothing else can make a
605 /// neighbour unavailable.
606 fn available(&self, cx: usize, cy: usize, nx: i32, ny: i32) -> bool {
607 if nx < 0 || ny < 0 {
608 return false;
609 }
610 let (nx, ny) = (nx as usize, ny as usize);
611 if nx >= self.pic.y.w || ny >= self.pic.y.h {
612 return false;
613 }
614 if self.z_order(nx, ny) >= self.z_order(cx, cy) {
615 return false;
616 }
617 self.slice_of(nx, ny) == self.slice_of(cx, cy)
618 }
619
620 /// Which slice the coding tree block covering a position belongs to.
621 fn slice_of(&self, x: usize, y: usize) -> u16 {
622 let ctb = self.sps.ctb_size as usize;
623 let at = (y / ctb) * self.ctbs_w + (x / ctb);
624 self.slice_at.get(at).copied().unwrap_or(0)
625 }
626
627 /// Records how deep in the quadtree a coding unit sits, against every block it covers.
628 fn record_depth(&mut self, x: usize, y: usize, size: usize, depth: u8) {
629 for gy in (y / 4)..((y + size).div_ceil(4)).min(self.gh) {
630 for gx in (x / 4)..((x + size).div_ceil(4)).min(self.gw) {
631 self.ct_depth[gy * self.gw + gx] = depth;
632 }
633 }
634 }
635
636 /// The same for its quantisation parameter, which is settled later than its depth is.
637 ///
638 /// Kept apart from the depth deliberately: writing the two together meant that a coding unit
639 /// carrying a change of quantisation parameter also wrote a depth of nought over its own, and
640 /// the next block's split flag was then read against the wrong context.
641 fn record_qp(&mut self, x: usize, y: usize, size: usize, qp: i8) {
642 for gy in (y / 4)..((y + size).div_ceil(4)).min(self.gh) {
643 for gx in (x / 4)..((x + size).div_ceil(4)).min(self.gw) {
644 self.qp[gy * self.gw + gx] = qp;
645 }
646 }
647 }
648
649 /// The luma prediction mode recorded against a position.
650 ///
651 /// **Not guarded by availability.** A block's own mode is written down as its syntax is read,
652 /// which is before it has been reconstructed -- so asking whether it is *available* and
653 /// answering "flat" where it is not predicts every block in the picture with the flat mode, and
654 /// produces a picture that is recognisably the right photograph and wrong everywhere. Where
655 /// availability does matter is the candidate list, and [`Frame::mode_candidates`] checks it
656 /// there.
657 fn mode_of(&self, x: usize, y: usize) -> u8 {
658 let (gx, gy) = ((x / 4).min(self.gw - 1), (y / 4).min(self.gh - 1));
659 self.mode[gy * self.gw + gx]
660 }
661
662 /// One coding tree block: its filter settings, then its quadtree.
663 fn ctu(&mut self, ent: &mut Ent, rx: usize, ry: usize) -> Outcome<()> {
664 let ctb = self.sps.ctb_size as usize;
665 let (x, y) = (rx * ctb, ry * ctb);
666 if self.slice.sao_luma || self.slice.sao_chroma {
667 res!(self.sao_params(ent, rx, ry));
668 }
669 // A new coding tree block is a new quantisation group unless the group is larger than one.
670 self.quadtree(ent, x, y, self.sps.ctb_size.trailing_zeros(), 0)
671 }
672
673 /// The sample adaptive offset settings of one block (§7.3.8.3).
674 fn sao_params(&mut self, ent: &mut Ent, rx: usize, ry: usize) -> Outcome<()> {
675 let at = ry * self.ctbs_w + rx;
676 let mut merge_left = false;
677 let mut merge_up = false;
678 if rx > 0 {
679 merge_left = res!(ent.bin(Set::SaoMerge, 0)) == 1;
680 }
681 if ry > 0 && !merge_left {
682 merge_up = res!(ent.bin(Set::SaoMerge, 0)) == 1;
683 }
684 if merge_left {
685 self.sao[at] = self.sao[at - 1];
686 return Ok(());
687 }
688 if merge_up {
689 self.sao[at] = self.sao[at - self.ctbs_w];
690 return Ok(());
691 }
692 let mut sao = Sao::default();
693 for c in 0..3usize {
694 let wanted = if c == 0 { self.slice.sao_luma } else { self.slice.sao_chroma };
695 if !wanted {
696 continue;
697 }
698 // Luma and the first chroma component each carry a type; the second takes the first's.
699 if c < 2 {
700 // Truncated unary of at most two: nothing, a band offset, or an edge offset.
701 let first = res!(ent.bin(Set::SaoType, 0));
702 sao.kind[c] = if first == 0 {
703 0
704 } else if ent.cabac.bypass() == 0 {
705 1
706 } else {
707 2
708 };
709 } else {
710 sao.kind[2] = sao.kind[1];
711 sao.class[2] = sao.class[1];
712 }
713 if sao.kind[c] == 0 {
714 continue;
715 }
716 // The offsets themselves, each a truncated unary at even odds, bounded by what the bit
717 // depth allows: seven at eight bits, and never more than thirty-one (§9.3.3, Table
718 // 9-43). A bound that is too large reads bins that were never coded and every syntax
719 // element after it in the picture is shifted -- which is what this was, at 127.
720 let depth = if c == 0 { self.sps.luma_bits } else { self.sps.chroma_bits };
721 let most = (1usize << (depth.min(10) as usize - 5)) - 1;
722 for i in 0..4 {
723 sao.offset[c][i] = ent.unary_bypass(most) as i32;
724 }
725 if sao.kind[c] == 1 {
726 for i in 0..4 {
727 if sao.offset[c][i] != 0 && ent.cabac.bypass() == 1 {
728 sao.offset[c][i] = -sao.offset[c][i];
729 }
730 }
731 sao.band[c] = ent.cabac.bypass_bits(5) as u8;
732 } else {
733 // An edge offset's four are two positive and two negative by construction, so no
734 // signs are coded.
735 sao.offset[c][2] = -sao.offset[c][2];
736 sao.offset[c][3] = -sao.offset[c][3];
737 if c < 2 {
738 sao.class[c] = ent.cabac.bypass_bits(2) as u8;
739 if c == 1 {
740 sao.class[2] = sao.class[1];
741 }
742 }
743 }
744 }
745 self.sao[at] = sao;
746 Ok(())
747 }
748
749 /// One node of the coding quadtree (§7.3.8.4).
750 fn quadtree(&mut self, ent: &mut Ent, x: usize, y: usize, log2: u32, depth: u8)
751 -> Outcome<()>
752 {
753 let size = 1usize << log2;
754 let (w, h) = (self.pic.y.w, self.pic.y.h);
755 let min_cb = self.sps.min_cb.trailing_zeros();
756 // A node hanging over the edge of the picture is split without being told to, and one at
757 // the smallest coding size cannot split at all. Only in between is a flag coded.
758 let mut split = log2 > min_cb;
759 if x + size <= w && y + size <= h && log2 > min_cb {
760 // The context depends on whether the neighbours went deeper than this node, which is
761 // what makes a picture of small blocks cheap to say so about.
762 let left = if self.available(x, y, x as i32 - 1, y as i32) {
763 (self.ct_depth[(y / 4) * self.gw + (x - 1) / 4] > depth) as usize
764 } else {
765 0
766 };
767 let above = if self.available(x, y, x as i32, y as i32 - 1) {
768 (self.ct_depth[((y - 1) / 4) * self.gw + x / 4] > depth) as usize
769 } else {
770 0
771 };
772 split = res!(ent.bin(Set::SplitCu, left + above)) == 1;
773 }
774 // A quantisation group begins at whatever depth the picture chose.
775 if self.pps.cu_qp_delta && log2 >= self.qp_group_log2() {
776 self.qp_coded = false;
777 self.qp_delta = 0;
778 }
779 if split {
780 let half = size / 2;
781 let next = log2 - 1;
782 res!(self.quadtree(ent, x, y, next, depth + 1));
783 if x + half < w {
784 res!(self.quadtree(ent, x + half, y, next, depth + 1));
785 }
786 if y + half < h {
787 res!(self.quadtree(ent, x, y + half, next, depth + 1));
788 }
789 if x + half < w && y + half < h {
790 res!(self.quadtree(ent, x + half, y + half, next, depth + 1));
791 }
792 return Ok(());
793 }
794 self.coding_unit(ent, x, y, log2, depth)
795 }
796
797 /// The size of a quantisation group, as a base-two logarithm.
798 fn qp_group_log2(&self) -> u32 {
799 self.sps.ctb_size.trailing_zeros() - self.pps.qp_delta_depth as u32
800 }
801
802 /// One coding unit (§7.3.8.5), for the intra case, which is all a still picture has.
803 fn coding_unit(&mut self, ent: &mut Ent, x: usize, y: usize, log2: u32, depth: u8)
804 -> Outcome<()>
805 {
806 let size = 1usize << log2;
807 self.bypass = false;
808 if self.pps.transquant_bypass {
809 self.bypass = res!(ent.bin(Set::TransquantBypass, 0)) == 1;
810 }
811 // Only at the smallest coding size may an intra unit be split into four prediction blocks,
812 // and only then is the partition mode coded at all.
813 let min_cb = self.sps.min_cb.trailing_zeros();
814 self.split_intra = if log2 == min_cb {
815 // One bin: set means the whole unit, clear means four.
816 res!(ent.bin(Set::PartMode, 0)) == 0
817 } else {
818 false
819 };
820 let parts = if self.split_intra { 4 } else { 1 };
821 let step = if self.split_intra { size / 2 } else { size };
822
823 // Whether each prediction block takes one of the three modes its neighbours suggest.
824 let mut from_list = [false; 4];
825 for p in 0..parts {
826 from_list[p] = res!(ent.bin(Set::PrevIntraLumaPred, 0)) == 1;
827 }
828 for p in 0..parts {
829 let (px, py) = (x + (p & 1) * step, y + (p >> 1) * step);
830 let list = self.mode_candidates(px, py);
831 self.pred_y[p] = if from_list[p] {
832 // Two bins at even odds, truncated: 0, 10 or 11.
833 let idx = if ent.cabac.bypass() == 0 {
834 0
835 } else if ent.cabac.bypass() == 0 {
836 1
837 } else {
838 2
839 };
840 list[idx]
841 } else {
842 // Five bits at even odds, naming one of the thirty-two that are not in the list.
843 let mut sorted = list;
844 sorted.sort_unstable();
845 let mut mode = ent.cabac.bypass_bits(5) as u8;
846 for candidate in sorted {
847 if mode >= candidate {
848 mode += 1;
849 }
850 }
851 mode
852 };
853 // Written down as each block's mode is settled, because the next block's candidate
854 // list is drawn from it.
855 self.put_mode(px, py, step, self.pred_y[p]);
856 }
857 // One chroma mode for the whole unit in 4:2:0.
858 let chroma_syntax = if res!(ent.bin(Set::IntraChromaPredMode, 0)) == 0 {
859 4
860 } else {
861 ent.cabac.bypass_bits(2) as usize
862 };
863 self.pred_c = chroma_mode(chroma_syntax, self.pred_y[0]);
864
865 self.cu_x = x;
866 self.cu_y = y;
867 self.cu_size = size;
868 self.cbf_cb = [false; 6];
869 self.cbf_cr = [false; 6];
870 // The parameter this unit will use, unless its own residual carries a change.
871 self.qp_now = self.predict_qp(x, y);
872 self.record_depth(x, y, size, depth);
873 self.record_qp(x, y, size, self.qp_now as i8);
874
875 let max_depth = self.sps.max_depth_intra as u32 + self.split_intra as u32;
876 res!(self.transform_tree(ent, x, y, x, y, log2, 0, 0, max_depth));
877 // What the next quantisation group predicts from is the last unit of this one, and this is
878 // the last unit until another follows it.
879 self.qp_prev = self.qp_now;
880 Ok(())
881 }
882
883 /// Writes a prediction mode against every four-by-four block it covers.
884 fn put_mode(&mut self, x: usize, y: usize, size: usize, mode: u8) {
885 for gy in (y / 4)..((y + size).div_ceil(4)).min(self.gh) {
886 for gx in (x / 4)..((x + size).div_ceil(4)).min(self.gw) {
887 self.mode[gy * self.gw + gx] = mode;
888 }
889 }
890 }
891
892 /// The three modes a block's neighbours suggest (§8.4.2).
893 ///
894 /// A block whose left and upper neighbours agree gets that mode and its two nearest angles; one
895 /// whose neighbours differ gets both of theirs and a third that is not either. The upper
896 /// neighbour is only consulted **within the same row of coding tree blocks**: a decoder running
897 /// the rows in parallel cannot see the row above, so the specification does not let it.
898 fn mode_candidates(&self, x: usize, y: usize) -> [u8; 3] {
899 let ctb = self.sps.ctb_size as usize;
900 let left = if self.available(x, y, x as i32 - 1, y as i32) {
901 self.mode_of(x - 1, y)
902 } else {
903 intra::DC
904 };
905 let above = if y % ctb == 0 || !self.available(x, y, x as i32, y as i32 - 1) {
906 intra::DC
907 } else {
908 self.mode_of(x, y - 1)
909 };
910 if left == above {
911 if left < 2 {
912 return [intra::PLANAR, intra::DC, intra::VERTICAL];
913 }
914 return [
915 left,
916 2 + ((left as u32 + 29) % 32) as u8,
917 2 + ((left as u32 - 2 + 1) % 32) as u8,
918 ];
919 }
920 let third = if left != intra::PLANAR && above != intra::PLANAR {
921 intra::PLANAR
922 } else if left != intra::DC && above != intra::DC {
923 intra::DC
924 } else {
925 intra::VERTICAL
926 };
927 [left, above, third]
928 }
929
930 /// What the quantisation parameter of a coding unit is predicted to be (§8.6.1).
931 fn predict_qp(&self, x: usize, y: usize) -> i32 {
932 if !self.pps.cu_qp_delta {
933 return self.slice.qp;
934 }
935 let group = 1usize << self.qp_group_log2();
936 let (qx, qy) = (x - (x & (group - 1)), y - (y & (group - 1)));
937 let ctb = self.sps.ctb_size as usize;
938 // A neighbour in another coding tree block does not count: the prediction is meant to stay
939 // inside one, so that a row decoded on its own gives the same answer.
940 let same_ctb = |nx: i32, ny: i32| {
941 nx >= 0 && ny >= 0
942 && (nx as usize) / ctb == x / ctb
943 && (ny as usize) / ctb == y / ctb
944 };
945 let left = if same_ctb(qx as i32 - 1, qy as i32)
946 && self.available(x, y, qx as i32 - 1, qy as i32)
947 {
948 self.qp[(qy / 4) * self.gw + (qx - 1) / 4] as i32
949 } else {
950 self.qp_prev
951 };
952 let above = if same_ctb(qx as i32, qy as i32 - 1)
953 && self.available(x, y, qx as i32, qy as i32 - 1)
954 {
955 self.qp[((qy - 1) / 4) * self.gw + qx / 4] as i32
956 } else {
957 self.qp_prev
958 };
959 (left + above + 1) >> 1
960 }
961
962 /// One node of the transform tree (§7.3.8.8).
963 #[allow(clippy::too_many_arguments)]
964 fn transform_tree(
965 &mut self,
966 ent: &mut Ent,
967 x: usize,
968 y: usize,
969 base_x: usize,
970 base_y: usize,
971 log2: u32,
972 depth: u32,
973 blk: usize,
974 max_depth: u32,
975 )
976 -> Outcome<()>
977 {
978 let max_tb = self.sps.max_tb.trailing_zeros();
979 let min_tb = self.sps.min_tb.trailing_zeros();
980 // Forced where the block is too large for one transform, or where a coding unit split
981 // into four prediction blocks makes its transform tree follow it down one level; coded
982 // where neither applies.
983 let coded = log2 <= max_tb && log2 > min_tb && depth < max_depth
984 && !(self.split_intra && depth == 0);
985 let split = if coded {
986 res!(ent.bin(Set::SplitTransform, (5 - log2) as usize)) == 1
987 } else {
988 log2 > max_tb || (self.split_intra && depth == 0 && log2 > min_tb)
989 };
990 // Chroma has a residual flag only where the block is big enough to have chroma of its own.
991 let d = depth as usize;
992 if log2 > 2 {
993 if depth == 0 || self.cbf_cb[d - 1] {
994 self.cbf_cb[d] = res!(ent.bin(Set::CbfChroma, d)) == 1;
995 } else {
996 self.cbf_cb[d] = false;
997 }
998 if depth == 0 || self.cbf_cr[d - 1] {
999 self.cbf_cr[d] = res!(ent.bin(Set::CbfChroma, d)) == 1;
1000 } else {
1001 self.cbf_cr[d] = false;
1002 }
1003 } else if d > 0 {
1004 // A four-sample luma block has no chroma of its own; the quad shares its parent's.
1005 self.cbf_cb[d] = self.cbf_cb[d - 1];
1006 self.cbf_cr[d] = self.cbf_cr[d - 1];
1007 } else {
1008 return Err(err!(
1009 "A four-sample transform block sits at the top of its tree, which cannot happen: the smallest coding block is {} samples.", self.sps.min_cb; Invalid, Input, Decode));
1010 }
1011 if split {
1012 let half = 1usize << (log2 - 1);
1013 for (i, (dx, dy)) in [(0, 0), (half, 0), (0, half), (half, half)].iter().enumerate() {
1014 res!(self.transform_tree(
1015 ent, x + dx, y + dy, x, y, log2 - 1, depth + 1, i, max_depth));
1016 }
1017 return Ok(());
1018 }
1019 // An intra block always has a luma residual flag; there is nothing else it could carry.
1020 let cbf_luma = res!(ent.bin(Set::CbfLuma, (depth == 0) as usize)) == 1;
1021 self.transform_unit(ent, x, y, base_x, base_y, log2, depth, blk, cbf_luma)
1022 }
1023
1024 /// One transform unit: the residuals, and the reconstruction they belong to (§7.3.8.10).
1025 #[allow(clippy::too_many_arguments)]
1026 fn transform_unit(
1027 &mut self,
1028 ent: &mut Ent,
1029 x: usize,
1030 y: usize,
1031 base_x: usize,
1032 base_y: usize,
1033 log2: u32,
1034 depth: u32,
1035 blk: usize,
1036 cbf_luma: bool,
1037 )
1038 -> Outcome<()>
1039 {
1040 let d = depth as usize;
1041 // Where the block is four samples wide the chroma of the whole quad is carried by the last
1042 // of the four, and the flags belong to the parent.
1043 let small = log2 == 2;
1044 let cd = if small { d - 1 } else { d };
1045 // Whether this unit has any chroma residual **at all**, which is a different question from
1046 // whether this is the block that carries it. A four-sample quad's chroma is read at the
1047 // last of the four, but all four of them share the flags -- so the first of them, even
1048 // with no luma residual of its own, is where a change of quantisation parameter is coded.
1049 // Gating this on the last block instead read that change at the wrong point in the stream,
1050 // and everything after it in the picture was decoded from the wrong bins.
1051 let chroma_here = !small || blk == 3;
1052 let has_chroma = self.cbf_cb[cd] || self.cbf_cr[cd];
1053 if cbf_luma || has_chroma {
1054 if self.pps.cu_qp_delta && !self.qp_coded {
1055 self.qp_coded = true;
1056 // A unary run of up to five against contexts, then the rest at even odds.
1057 let mut abs = res!(ent.unary(Set::CuQpDeltaAbs, &[0, 1], 5));
1058 if abs == 5 {
1059 abs += golomb(ent, 0);
1060 }
1061 if abs > 0 && ent.cabac.bypass() == 1 {
1062 self.qp_delta = -(abs as i32);
1063 } else {
1064 self.qp_delta = abs as i32;
1065 }
1066 let offset = 0; // Eight-bit pictures have no quantisation parameter offset.
1067 let span = 52 + offset;
1068 self.qp_now = ((self.predict_qp(self.cu_x, self.cu_y) + self.qp_delta + span
1069 + offset) % span) - offset;
1070 let (cx, cy, cs) = (self.cu_x, self.cu_y, self.cu_size);
1071 self.record_qp(cx, cy, cs, self.qp_now as i8);
1072 self.qp_prev = self.qp_now;
1073 }
1074 }
1075 // Luma first, because the chroma of a small quad is written after all four of them.
1076 let mode_y = self.mode_of(x, y);
1077 res!(self.block(ent, x, y, log2, 0, mode_y, cbf_luma));
1078
1079 if !chroma_here {
1080 return Ok(());
1081 }
1082 // In 4:2:0 the chroma block is half the size, and a four-sample luma quad shares one.
1083 let (cx, cy, clog2) = if small {
1084 (base_x / 2, base_y / 2, log2)
1085 } else {
1086 (x / 2, y / 2, log2 - 1)
1087 };
1088 let mode_c = self.pred_c;
1089 res!(self.block(ent, cx, cy, clog2, 1, mode_c, self.cbf_cb[cd]));
1090 res!(self.block(ent, cx, cy, clog2, 2, mode_c, self.cbf_cr[cd]));
1091 Ok(())
1092 }
1093
1094 /// Predicts one transform block, reads its residual where it has one, and writes the samples.
1095 fn block(
1096 &mut self,
1097 ent: &mut Ent,
1098 x: usize,
1099 y: usize,
1100 log2: u32,
1101 cidx: usize,
1102 mode: u8,
1103 coded: bool,
1104 )
1105 -> Outcome<()>
1106 {
1107 let size = 1usize << log2;
1108 let chroma = cidx > 0;
1109 let mut coeffs = [0i32; 32 * 32];
1110 self.skip_tr = false;
1111 if coded {
1112 res!(self.residual(ent, log2, cidx, mode, &mut coeffs));
1113 }
1114 // The samples around the block, and whether each of them exists.
1115 let mut around = intra::Around::new(size);
1116 let (px, py) = if chroma { (x * 2, y * 2) } else { (x, y) };
1117 let step = if chroma { 2usize } else { 1 };
1118 {
1119 let plane = self.plane(cidx);
1120 if self.available(px, py, px as i32 - step as i32, py as i32 - step as i32) {
1121 if let Some(v) = plane.at(x.wrapping_sub(1), y.wrapping_sub(1)) {
1122 around.set_corner(v as i32);
1123 }
1124 }
1125 for i in 0..size * 2 {
1126 if self.available(px, py, px as i32 - step as i32, (py + i * step) as i32) {
1127 if let Some(v) = plane.at(x.wrapping_sub(1), y + i) {
1128 around.set_left(i, v as i32);
1129 }
1130 }
1131 if self.available(px, py, (px + i * step) as i32, py as i32 - step as i32) {
1132 if let Some(v) = plane.at(x + i, y.wrapping_sub(1)) {
1133 around.set_top(i, v as i32);
1134 }
1135 }
1136 }
1137 }
1138 let depth = self.pic.depth;
1139 around.substitute(depth);
1140 around.smooth(mode, chroma, self.sps.strong_smoothing, depth);
1141 let mut pred = [0i32; 32 * 32];
1142 res!(intra::predict(&around, mode, size, chroma, depth, &mut pred));
1143
1144 if coded {
1145 let qp = self.block_qp(cidx);
1146 if self.bypass {
1147 // Nothing was quantised and nothing transformed: the coefficients are the residual.
1148 } else {
1149 let m = self.weights_for(size, log2, cidx);
1150 transform::scale(&mut coeffs, size, qp, depth, &m);
1151 if self.skip_tr {
1152 transform::skipped(&mut coeffs, size);
1153 } else {
1154 let kind = transform::Kind::of(true, size, chroma);
1155 res!(transform::inverse(&mut coeffs, size, kind));
1156 }
1157 transform::finish(&mut coeffs, size, depth);
1158 }
1159 }
1160 let top = (1i32 << depth) - 1;
1161 for j in 0..size {
1162 for i in 0..size {
1163 let v = (pred[j * size + i] + coeffs[j * size + i]).clamp(0, top);
1164 self.plane_mut(cidx).put(x + i, y + j, v as u16);
1165 }
1166 }
1167 if !chroma {
1168 // Where this block's edges are, for the deblocking filter to find later.
1169 for j in (y / 4)..((y + size).div_ceil(4)).min(self.gh) {
1170 self.edge_v[j * self.gw + x / 4] = true;
1171 }
1172 for i in (x / 4)..((x + size).div_ceil(4)).min(self.gw) {
1173 self.edge_h[(y / 4) * self.gw + i] = true;
1174 }
1175 }
1176 Ok(())
1177 }
1178
1179 /// The scaling matrix one block is quantised against (§7.4.5, equations 7-44 to 7-49).
1180 ///
1181 /// A four-sample block is flat; an eight-sample one takes the matrix as it stands; and the two
1182 /// larger sizes take it with each of its values covering two or four samples each way. All
1183 /// three colour components share one matrix here, because the default lists give the same
1184 /// numbers to all three.
1185 fn weights_for(&self, size: usize, log2: u32, cidx: usize) -> Vec<i32> {
1186 let scaling = match &self.weights {
1187 Some(s) => s,
1188 None => return vec![16; size * size],
1189 };
1190 // An intra picture only ever uses the first three of the six lists: the other three belong
1191 // to blocks predicted from another picture, which a still photograph has none of.
1192 let matrix = cidx;
1193 let raster = scaling.raster(log2, matrix);
1194 let mut out = Vec::with_capacity(size * size);
1195 for y in 0..size {
1196 for x in 0..size {
1197 out.push(scaling.factor(log2, matrix, x, y, &raster));
1198 }
1199 }
1200 out
1201 }
1202
1203 /// The quantisation parameter one component's block is scaled by (§8.6.1).
1204 fn block_qp(&self, cidx: usize) -> i32 {
1205 if cidx == 0 {
1206 return self.qp_now.clamp(0, 51);
1207 }
1208 let offset = if cidx == 1 {
1209 self.pps.cb_qp_offset + self.slice.cb_qp_offset
1210 } else {
1211 self.pps.cr_qp_offset + self.slice.cr_qp_offset
1212 };
1213 chroma_qp((self.qp_now + offset).clamp(0, 57))
1214 }
1215
1216 fn plane(&self, cidx: usize) -> &Plane {
1217 match cidx {
1218 0 => &self.pic.y,
1219 1 => &self.pic.cb,
1220 _ => &self.pic.cr,
1221 }
1222 }
1223
1224 fn plane_mut(&mut self, cidx: usize) -> &mut Plane {
1225 match cidx {
1226 0 => &mut self.pic.y,
1227 1 => &mut self.pic.cb,
1228 _ => &mut self.pic.cr,
1229 }
1230 }
1231
1232 /// The coefficients of one transform block (§7.3.8.11).
1233 #[allow(clippy::too_many_arguments)]
1234 fn residual(
1235 &mut self,
1236 ent: &mut Ent,
1237 log2: u32,
1238 cidx: usize,
1239 mode: u8,
1240 out: &mut [i32],
1241 )
1242 -> Outcome<()>
1243 {
1244 let size = 1usize << log2;
1245 let chroma = cidx > 0;
1246 if self.pps.transform_skip && !self.bypass && log2 == 2 {
1247 self.skip_tr = res!(ent.bin(Set::TransformSkip, (cidx > 0) as usize)) == 1;
1248 }
1249 let order = Order::of(log2, chroma, mode);
1250
1251 // Where the last coefficient in coding order sits. Its prefix is a truncated unary against
1252 // contexts that depend on the block size, and its suffix is plain bits.
1253 let (offset, shift) = if cidx == 0 {
1254 (3 * (log2 as usize - 2) + ((log2 as usize - 1) >> 2), (log2 + 1) >> 2)
1255 } else {
1256 (15usize, log2 - 2)
1257 };
1258 let most = (log2 as usize) * 2 - 1;
1259 let incs: Vec<usize> = (0..most).map(|b| (b >> shift) + offset).collect();
1260 let px = res!(ent.unary(Set::LastSigX, &incs, most));
1261 let py = res!(ent.unary(Set::LastSigY, &incs, most));
1262 let last_x = suffix_of(ent, px);
1263 let last_y = suffix_of(ent, py);
1264 let (last_x, last_y) = if order == Order::Vertical {
1265 (last_y, last_x)
1266 } else {
1267 (last_x, last_y)
1268 };
1269
1270 // Which sub-block that lands in, and where within it.
1271 let sub_log2 = log2 - 2;
1272 let subs = self.scans.of(sub_log2, order).to_vec();
1273 let coeff_scan = self.scans.of(2, order).to_vec();
1274 let mut last_sub = subs.len() - 1;
1275 let mut last_pos = 16usize;
1276 'find: loop {
1277 if last_pos == 0 {
1278 last_pos = 16;
1279 if last_sub == 0 {
1280 break;
1281 }
1282 last_sub -= 1;
1283 }
1284 last_pos -= 1;
1285 let (sx, sy) = subs[last_sub];
1286 let (cx, cy) = coeff_scan[last_pos];
1287 if (sx as usize * 4 + cx as usize) == last_x as usize
1288 && (sy as usize * 4 + cy as usize) == last_y as usize
1289 {
1290 break 'find;
1291 }
1292 if last_sub == 0 && last_pos == 0 {
1293 return Err(err!(
1294 "The last coefficient of a {0} by {0} block is at ({1}, {2}), which its scan \
1295 never reaches.", size, last_x, last_y; Invalid, Input, Decode));
1296 }
1297 }
1298
1299 let mut coded_sub = vec![false; subs.len()];
1300 coded_sub[last_sub] = true;
1301 if !subs.is_empty() {
1302 coded_sub[0] = true;
1303 }
1304 // Carried between sub-blocks: which context set the magnitudes are read against.
1305 let mut prev_greater1_ctx = 1i32;
1306
1307 for i in (0..=last_sub).rev() {
1308 let (sx, sy) = subs[i];
1309 let (sx, sy) = (sx as usize, sy as usize);
1310 let mut infer_dc = false;
1311 if i < last_sub && i > 0 {
1312 let right = if sx < (1 << sub_log2) - 1 {
1313 coded_sub[position_of(&subs, sx + 1, sy)] as usize
1314 } else {
1315 0
1316 };
1317 let below = if sy < (1 << sub_log2) - 1 {
1318 coded_sub[position_of(&subs, sx, sy + 1)] as usize
1319 } else {
1320 0
1321 };
1322 let inc = (right + below).min(1) + if chroma { 2 } else { 0 };
1323 coded_sub[i] = res!(ent.bin(Set::CodedSubBlock, inc)) == 1;
1324 infer_dc = true;
1325 }
1326 if !coded_sub[i] {
1327 continue;
1328 }
1329 // Which coefficients in this sub-block are not nought.
1330 let mut sig = [false; 16];
1331 // The last coefficient is significant by definition -- saying where it was is what
1332 // the block began with -- so the flags start one before it.
1333 let start = if i == last_sub { last_pos as i32 - 1 } else { 15 };
1334 if i == last_sub {
1335 sig[last_pos] = true;
1336 }
1337 for n in (0..=start).rev() {
1338 let n = n as usize;
1339 if n > 0 || !infer_dc {
1340 let (cx, cy) = coeff_scan[n];
1341 let inc = self.sig_ctx(
1342 sx, sy, cx as usize, cy as usize, log2, cidx, order, &coded_sub, &subs);
1343 sig[n] = res!(ent.bin(Set::SigCoeff, inc)) == 1;
1344 if sig[n] {
1345 infer_dc = false;
1346 }
1347 } else {
1348 // The only coefficient left in a sub-block known to hold something.
1349 sig[n] = true;
1350 }
1351 }
1352
1353 // Their magnitudes, in three passes: over one, over two, and the rest.
1354 let mut ctx_set = if i == 0 || chroma { 0usize } else { 2 };
1355 if prev_greater1_ctx == 0 {
1356 ctx_set += 1;
1357 }
1358 let mut greater1_ctx = 1i32;
1359 let mut n_greater1 = 0usize;
1360 let mut last_greater1 = -1i32;
1361 let mut greater1 = [false; 16];
1362 for n in (0..16).rev() {
1363 if !sig[n] {
1364 continue;
1365 }
1366 if n_greater1 < 8 {
1367 let inc = ctx_set * 4 + (greater1_ctx.min(3) as usize)
1368 + if chroma { 16 } else { 0 };
1369 greater1[n] = res!(ent.bin(Set::Greater1, inc)) == 1;
1370 n_greater1 += 1;
1371 if greater1[n] {
1372 greater1_ctx = 0;
1373 if last_greater1 == -1 {
1374 last_greater1 = n as i32;
1375 }
1376 } else if greater1_ctx > 0 {
1377 greater1_ctx += 1;
1378 }
1379 }
1380 }
1381 // Carried to the next sub-block, but only where this one asked the question at all:
1382 // a sub-block whose coefficients are all ones leaves the context where it found it.
1383 if n_greater1 > 0 {
1384 prev_greater1_ctx = greater1_ctx;
1385 }
1386
1387 let mut greater2 = [false; 16];
1388 if last_greater1 >= 0 {
1389 let inc = ctx_set + if chroma { 4 } else { 0 };
1390 greater2[last_greater1 as usize] = res!(ent.bin(Set::Greater2, inc)) == 1;
1391 }
1392
1393 // Where the first and last of them are, which is what decides whether one sign is
1394 // carried by the parity of the sum rather than by a bit of its own.
1395 let mut first_sig = 16i32;
1396 let mut last_sig = -1i32;
1397 for n in (0..16).rev() {
1398 if sig[n] {
1399 if last_sig == -1 {
1400 last_sig = n as i32;
1401 }
1402 first_sig = n as i32;
1403 }
1404 }
1405 let hidden = self.pps.sign_hiding && !self.bypass && last_sig - first_sig > 3;
1406
1407 let mut signs = [false; 16];
1408 for n in (0..16).rev() {
1409 if sig[n] && (!hidden || n as i32 != first_sig) {
1410 signs[n] = ent.cabac.bypass() == 1;
1411 }
1412 }
1413
1414 // And the magnitudes themselves.
1415 let mut rice = 0u32;
1416 let mut n_sig = 0usize;
1417 let mut sum = 0i64;
1418 let mut last_abs = 0i64;
1419 let mut first = true;
1420 for n in (0..16).rev() {
1421 if !sig[n] {
1422 continue;
1423 }
1424 let base = 1 + greater1[n] as i32 + greater2[n] as i32;
1425 let threshold = if n_sig < 8 {
1426 if n as i32 == last_greater1 { 3 } else { 2 }
1427 } else {
1428 1
1429 };
1430 let mut level = base as i64;
1431 if base == threshold {
1432 if first {
1433 rice = 0;
1434 } else {
1435 rice = (rice + (last_abs > (3 << rice) as i64) as u32).min(4);
1436 }
1437 level += remaining(ent, rice) as i64;
1438 first = false;
1439 last_abs = level;
1440 }
1441 let (cx, cy) = coeff_scan[n];
1442 let at = (sy * 4 + cy as usize) * size + sx * 4 + cx as usize;
1443 sum += level;
1444 let negative = signs[n] || (hidden && n as i32 == first_sig && sum % 2 == 1);
1445 out[at] = if negative { -(level as i32) } else { level as i32 };
1446 n_sig += 1;
1447 }
1448 }
1449 Ok(())
1450 }
1451
1452 /// The context one significance flag is read against (§9.3.4.2.5).
1453 #[allow(clippy::too_many_arguments)]
1454 fn sig_ctx(
1455 &self,
1456 sx: usize,
1457 sy: usize,
1458 cx: usize,
1459 cy: usize,
1460 log2: u32,
1461 cidx: usize,
1462 order: Order,
1463 coded: &[bool],
1464 subs: &[(u8, u8)],
1465 )
1466 -> usize
1467 {
1468 let chroma = cidx > 0;
1469 if self.skip_tr || self.bypass {
1470 // A block coded without its transform has no corner to speak of, so it has contexts of
1471 // its own.
1472 return if chroma { 27 + 16 } else { 42 };
1473 }
1474 if log2 == 2 {
1475 // A four-sample block reads its contexts straight off a map of its sixteen positions.
1476 const MAP: [usize; 16] = [0, 1, 4, 5, 2, 3, 4, 5, 6, 6, 8, 8, 7, 7, 8, 8];
1477 let v = MAP[cy * 4 + cx];
1478 return if chroma { 27 + v } else { v };
1479 }
1480 let (x, y) = (sx * 4 + cx, sy * 4 + cy);
1481 if x + y == 0 {
1482 return if chroma { 27 } else { 0 };
1483 }
1484 let side = 1usize << (log2 - 2);
1485 let mut prev = 0usize;
1486 if sx < side - 1 && coded[position_of(subs, sx + 1, sy)] {
1487 prev += 1;
1488 }
1489 if sy < side - 1 && coded[position_of(subs, sx, sy + 1)] {
1490 prev += 2;
1491 }
1492 let (px, py) = (cx, cy);
1493 let mut ctx = match prev {
1494 0 => if px + py == 0 { 2 } else if px + py < 3 { 1 } else { 0 },
1495 1 => if py == 0 { 2 } else if py == 1 { 1 } else { 0 },
1496 2 => if px == 0 { 2 } else if px == 1 { 1 } else { 0 },
1497 _ => 2,
1498 };
1499 if !chroma {
1500 if sx + sy > 0 {
1501 ctx += 3;
1502 }
1503 ctx += if log2 == 3 {
1504 if order == Order::Diagonal { 9 } else { 15 }
1505 } else {
1506 21
1507 };
1508 } else {
1509 ctx += if log2 == 3 { 9 } else { 12 };
1510 }
1511 if chroma {
1512 27 + ctx
1513 } else {
1514 ctx
1515 }
1516 }
1517}
1518
1519/// Where a sub-block sits in the scan.
1520fn position_of(subs: &[(u8, u8)], x: usize, y: usize) -> usize {
1521 subs.iter()
1522 .position(|(sx, sy)| *sx as usize == x && *sy as usize == y)
1523 .unwrap_or(0)
1524}
1525
1526/// The plain-bits half of a last-coefficient position, where the prefix says there is one.
1527fn suffix_of(ent: &mut Ent, prefix: u32) -> u32 {
1528 if prefix <= 3 {
1529 return prefix;
1530 }
1531 let bits = (prefix >> 1) - 1;
1532 let suffix = ent.cabac.bypass_bits(bits as usize);
1533 (1 << bits) * (2 + (prefix & 1)) + suffix
1534}
1535
1536/// An exponential Golomb code at even odds, of the given order (§9.3.3.3).
1537fn golomb(ent: &mut Ent, k: u32) -> u32 {
1538 let mut k = k;
1539 let mut value = 0u32;
1540 while ent.cabac.bypass() == 1 {
1541 value += 1 << k;
1542 k += 1;
1543 if k > 30 {
1544 return value;
1545 }
1546 }
1547 value + ent.cabac.bypass_bits(k as usize)
1548}
1549
1550/// What is left of a coefficient's magnitude past what the flags said (§9.3.3.11).
1551///
1552/// A truncated Rice code whose parameter grows with the magnitudes already seen in this sub-block,
1553/// and past four of those an exponential Golomb code takes over.
1554fn remaining(ent: &mut Ent, rice: u32) -> u32 {
1555 let prefix = ent.unary_bypass(4) as u32;
1556 if prefix < 4 {
1557 return (prefix << rice) + ent.cabac.bypass_bits(rice as usize);
1558 }
1559 (4 << rice) + golomb(ent, rice + 1)
1560}
1561
1562/// The chroma prediction mode a coding unit's syntax names (§8.4.3, Table 8-2).
1563///
1564/// Four of the five choices are fixed directions and the fifth is "the same as luma"; where a fixed
1565/// choice happens to be what luma already uses, the mode moves to 34 so that the two are never
1566/// coded twice.
1567fn chroma_mode(syntax: usize, luma: u8) -> u8 {
1568 if syntax == 4 {
1569 return luma;
1570 }
1571 let fixed = [intra::PLANAR, intra::VERTICAL, intra::HORIZONTAL, intra::DC][syntax];
1572 if fixed == luma {
1573 34
1574 } else {
1575 fixed
1576 }
1577}
1578
1579/// The chroma quantisation parameter for a given luma one (§8.6.1, Table 8-10).
1580///
1581/// Chroma is quantised more gently than luma above a parameter of thirty, because the eye is less
1582/// able to see colour noise than brightness noise -- but only up to a point, past which the two run
1583/// parallel again six steps apart.
1584pub fn chroma_qp(qpi: i32) -> i32 {
1585 match qpi {
1586 i32::MIN..=29 => qpi,
1587 30..=43 => [29, 30, 31, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37][(qpi - 30) as usize],
1588 _ => qpi - 6,
1589 }
1590}