Oregami
Repositories/oxedyne/fe2o3

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

28.1 KiB, 31 runs

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

download · who wrote it · its history

1//! The arithmetic decoder, and the context variables it codes against.
2//!
3//! HEVC entropy coding is CABAC: every syntax element is a string of binary decisions, and each
4//! decision is coded against a probability that adapts as the picture is read. Three kinds of
5//! decision exist -- one against a context variable, which is the usual one; one *bypassed* at even
6//! odds, for the parts of a value that carry no useful correlation; and one *terminating*, which is
7//! how the end of a slice or of a row of blocks is found.
8//!
9//! What is in here is the decoder itself (§9.3.4.3), the probability state a context is in
10//! (§9.3.2.2), the eighteen sets of context variables an intra still picture draws on, and the rule
11//! that carries them from one row of coding tree blocks to the next under wavefront coding.
12//!
13//! The two properties this can be held to before any picture exists are asserted in `mod.rs`'s
14//! tests: every context starts in a state the probability tables actually have, and the coding
15//! interval stays between 256 and 510 after every bin, whatever is fed in.
16//!
17//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
18//! Anthropic Claude
19
20use oxedyne_fe2o3_core::prelude::*;
21
22/// The probability state a context variable is in: an index 0 to 62, and the more probable symbol.
23///
24/// One byte rather than two fields, because there are hundreds of these and they are copied whole
25/// at the start of every row of blocks under wavefront coding.
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub struct Ctx(u8);
28
29impl Ctx {
30
31 /// The state a context starts in, from its initialisation value and the slice's quantisation
32 /// parameter (§9.3.2.2).
33 ///
34 /// The arithmetic is the specification's, and the clamp on the quantisation parameter is
35 /// load-bearing rather than defensive: a slice may legally start at a negative one on a
36 /// high-bit-depth picture, and the table this indexes has no entries there.
37 pub fn start(init: u8, qp: i32) -> Self {
38 let q = qp.clamp(0, 51);
39 let slope = ((init >> 4) as i32) * 5 - 45;
40 let offset = (((init & 15) as i32) << 3) - 16;
41 let pre = ((slope * q) >> 4) + offset;
42 let pre = pre.clamp(1, 126);
43 if pre <= 63 {
44 Self((((63 - pre) as u8) << 1) & 0x7e)
45 } else {
46 Self(((((pre - 64) as u8) << 1) | 1) & 0x7f)
47 }
48 }
49
50 /// The probability state index, 0 to 62.
51 fn state(self) -> usize {
52 (self.0 >> 1) as usize
53 }
54
55 /// The more probable symbol, 0 or 1.
56 fn mps(self) -> u32 {
57 (self.0 & 1) as u32
58 }
59}
60
61// How the range is narrowed for the less probable symbol, indexed by state and by the two bits
62// the current range contributes (§9.3.4.3.2.1, Table 9-46).
63const LPS: [[u8; 4]; 64] = [
64 [128, 176, 208, 240], [128, 167, 197, 227], [128, 158, 187, 216], [123, 150, 178, 205],
65 [116, 142, 169, 195], [111, 135, 160, 185], [105, 128, 152, 175], [100, 122, 144, 166],
66 [95, 116, 137, 158], [90, 110, 130, 150], [85, 104, 123, 142], [81, 99, 117, 135],
67 [77, 94, 111, 128], [73, 89, 105, 122], [69, 85, 100, 116], [66, 80, 95, 110],
68 [62, 76, 90, 104], [59, 72, 86, 99], [56, 69, 81, 94], [53, 65, 77, 89],
69 [51, 62, 73, 85], [48, 59, 69, 80], [46, 56, 66, 76], [43, 53, 63, 72],
70 [41, 50, 59, 69], [39, 48, 56, 65], [37, 45, 54, 62], [35, 43, 51, 59],
71 [33, 41, 48, 56], [32, 39, 46, 53], [30, 37, 43, 50], [29, 35, 41, 48],
72 [27, 33, 39, 45], [26, 31, 37, 43], [24, 30, 35, 41], [23, 28, 33, 39],
73 [22, 27, 32, 37], [21, 26, 30, 35], [20, 24, 29, 33], [19, 23, 27, 31],
74 [18, 22, 26, 30], [17, 21, 25, 28], [16, 20, 23, 27], [15, 19, 22, 25],
75 [14, 18, 21, 24], [14, 17, 20, 23], [13, 16, 19, 22], [12, 15, 18, 21],
76 [12, 14, 17, 20], [11, 14, 16, 19], [11, 13, 15, 18], [10, 12, 15, 17],
77 [10, 12, 14, 16], [9, 11, 13, 15], [9, 11, 12, 14], [8, 10, 12, 14],
78 [8, 9, 11, 13], [7, 9, 11, 12], [7, 9, 10, 12], [7, 8, 10, 11],
79 [6, 8, 9, 11], [6, 7, 9, 10], [6, 7, 8, 9], [2, 2, 2, 2],
80];
81
82// The state to move to after coding the more probable symbol (Table 9-47).
83const NEXT_MPS: [u8; 64] = [
84 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
85 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
86 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
87 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 62, 63,
88];
89
90// The state to move to after coding the less probable symbol (Table 9-47).
91const NEXT_LPS: [u8; 64] = [
92 0, 0, 1, 2, 2, 4, 4, 5, 6, 7, 8, 9, 9, 11, 11, 12,
93 13, 13, 15, 15, 16, 16, 18, 18, 19, 19, 21, 21, 22, 22, 23, 24,
94 24, 25, 26, 26, 27, 27, 28, 29, 29, 30, 30, 30, 31, 32, 32, 33,
95 33, 33, 34, 34, 35, 35, 35, 36, 36, 36, 37, 37, 37, 38, 38, 63,
96];
97
98/// The arithmetic decoder itself (§9.3.4.3).
99///
100/// It reads bits and answers questions of the form "was the next symbol a one?", where the odds are
101/// carried by whichever context variable the syntax says applies. There are three ways to ask: with
102/// a context, which is the usual one and adapts as it goes; **bypassed**, at even odds, for the
103/// parts of a value that carry no useful correlation; and **terminating**, which is how the end of
104/// a slice or a piece of one is found.
105pub struct Cabac<'a> {
106 buf: &'a [u8],
107 at: usize, // the next byte to be taken into the window
108 range: u32, // the current interval's width
109 offset: u32, // where in the interval the coded value sits
110 bits: i32, // bits of the window used so far
111}
112
113impl<'a> Cabac<'a> {
114
115 /// Starts the decoder at the beginning of a piece of entropy-coded data (§9.3.2.5).
116 pub fn new(buf: &'a [u8]) -> Outcome<Self> {
117 if buf.len() < 2 {
118 return Err(err!(
119 "An arithmetic decoder was started on {} bytes, and it reads two before it \
120 answers anything.", buf.len();
121 Invalid, Input, Decode));
122 }
123 Ok(Self {
124 buf,
125 at: 2,
126 range: 510,
127 // The specification reads nine bits into `ivlOffset` and compares it against the
128 // interval directly, reading one more bit at every renormalisation. This decoder keeps
129 // those bits **pre-read** instead -- `offset` holds `ivlOffset` shifted up by `bits`,
130 // with `bits` more of the stream already in the low end -- so a renormalisation is a
131 // subtraction from `bits` rather than a read. That is what makes it a byte-at-a-time
132 // decoder rather than a bit-at-a-time one, and it means the two bytes go in whole:
133 // `ivlOffset` is the top nine bits of them and the other seven are the window.
134 //
135 // Putting the unshifted nine-bit value here instead leaves every comparison against
136 // `range << bits` too small by a factor of 128, so the first hundred or so bins all
137 // come back as the more probable symbol and the picture is plausible and wrong.
138 offset: ((buf[0] as u32) << 8) | (buf[1] as u32),
139 bits: 7,
140 })
141 }
142
143 /// The next byte, or zeroes past the end.
144 ///
145 /// A decoder is allowed to read a little past the last byte of a slice -- the final bins are
146 /// coded against bits the encoder never had to write -- so running out is not a fault. What
147 /// would be a fault is reading far past it, and that is caught by the terminating bin, which
148 /// says where the data ends.
149 fn byte(&mut self) -> u32 {
150 let b = self.buf.get(self.at).copied().unwrap_or(0) as u32;
151 self.at += 1;
152 b
153 }
154
155 /// One bin against a context, which is then moved on (§9.3.4.3.2).
156 pub fn bin(&mut self, ctx: &mut Ctx) -> u32 {
157 let state = ctx.state();
158 let lps = LPS[state][((self.range >> 6) & 3) as usize] as u32;
159 self.range -= lps;
160 let value;
161 if self.offset >= (self.range << self.bits) {
162 // The less probable symbol.
163 self.offset -= self.range << self.bits;
164 value = 1 - ctx.mps();
165 self.range = lps;
166 if state == 0 {
167 // State zero is where the two symbols are equally likely, so being wrong there
168 // exchanges which one is called the more probable.
169 ctx.0 ^= 1;
170 }
171 ctx.0 = (NEXT_LPS[state] << 1) | (ctx.0 & 1);
172 } else {
173 value = ctx.mps();
174 ctx.0 = (NEXT_MPS[state] << 1) | (ctx.0 & 1);
175 }
176 // Renormalise: the interval is kept at nine bits or more.
177 while self.range < 256 {
178 self.range <<= 1;
179 self.bits -= 1;
180 if self.bits < 0 {
181 self.offset = (self.offset << 8) | self.byte();
182 self.bits += 8;
183 }
184 }
185 value
186 }
187
188 /// One bin at even odds, with no context to move on (§9.3.4.3.4).
189 pub fn bypass(&mut self) -> u32 {
190 self.bits -= 1;
191 if self.bits < 0 {
192 self.offset = (self.offset << 8) | self.byte();
193 self.bits += 8;
194 }
195 let scaled = self.range << self.bits;
196 if self.offset >= scaled {
197 self.offset -= scaled;
198 1
199 } else {
200 0
201 }
202 }
203
204 /// `n` bins at even odds, most significant first.
205 pub fn bypass_bits(&mut self, n: usize) -> u32 {
206 let mut v = 0u32;
207 for _ in 0..n.min(32) {
208 v = (v << 1) | self.bypass();
209 }
210 v
211 }
212
213 /// The bin that says whether this is the end (§9.3.4.3.5).
214 ///
215 /// One at the end of a slice, and at the end of each piece of one under wavefront coding.
216 pub fn terminate(&mut self) -> u32 {
217 self.range -= 2;
218 if self.offset >= (self.range << self.bits) {
219 1
220 } else {
221 while self.range < 256 {
222 self.range <<= 1;
223 self.bits -= 1;
224 if self.bits < 0 {
225 self.offset = (self.offset << 8) | self.byte();
226 self.bits += 8;
227 }
228 }
229 0
230 }
231 }
232
233 /// How many bytes have been taken out of the buffer.
234 ///
235 /// After a terminating bin says the piece has ended, this is where the next piece begins --
236 /// which is how the entry point offsets in the slice header are checked against the data.
237 pub fn consumed(&self) -> usize {
238 self.at
239 }
240}
241
242// ------------------------------------------------------- the context variables themselves
243
244/// A set of context variables belonging to one syntax element (§9.3.2.2, Table 9-4).
245///
246/// **Only the sets an intra still picture uses, and only their intra initialisation values.** The
247/// specification gives three initialisation types -- one for I slices and two for P and B -- and a
248/// picture out of a HEIC file is one intra slice, so the other two are as much use here as the
249/// motion vector syntax they mostly belong to. Where a table's intra column is a subset of its rows
250/// (`sig_coeff_flag` uses 0 to 41 and then 126 and 127, and nothing between), that is what is kept,
251/// and the gap is recorded in [`Set::runs`] so the whole lot can be checked back against the
252/// published table.
253#[derive(Clone, Copy, Debug, PartialEq, Eq)]
254pub enum Set {
255 SaoMerge, // reuse the left or upper block's sample adaptive offset?
256 SaoType, // which kind of sample adaptive offset a block has
257 SplitCu, // does a block of the coding quadtree split into four?
258 TransquantBypass, // a coding unit skipping the transform and quantiser entirely
259 PartMode, // how a coding unit is divided into prediction units
260 PrevIntraLumaPred, // is the intra mode one of the three its neighbours suggest?
261 IntraChromaPredMode, // which intra mode the chroma blocks take
262 SplitTransform, // does a block of the transform tree split into four?
263 CbfLuma, // has a luma transform block any coefficient at all?
264 CbfChroma, // the same for the two chroma blocks
265 CuQpDeltaAbs, // how far the block's quantisation parameter is from its prediction
266 TransformSkip, // a transform block coded without its transform
267 LastSigX, // where the last coefficient of a block sits, across
268 LastSigY, // and down
269 CodedSubBlock, // does a four-by-four group hold anything?
270 SigCoeff, // is one coefficient not zero?
271 Greater1, // is a coefficient's magnitude more than one?
272 Greater2, // and more than two?
273}
274
275impl Set {
276
277 // Every set, in the order their context variables are laid out.
278 pub const ALL: [Self; 18] = [
279 Self::SaoMerge,
280 Self::SaoType,
281 Self::SplitCu,
282 Self::TransquantBypass,
283 Self::PartMode,
284 Self::PrevIntraLumaPred,
285 Self::IntraChromaPredMode,
286 Self::SplitTransform,
287 Self::CbfLuma,
288 Self::CbfChroma,
289 Self::CuQpDeltaAbs,
290 Self::TransformSkip,
291 Self::LastSigX,
292 Self::LastSigY,
293 Self::CodedSubBlock,
294 Self::SigCoeff,
295 Self::Greater1,
296 Self::Greater2,
297 ];
298
299 /// The initialisation values of this set's context variables, for an intra slice.
300 pub const fn init(self) -> &'static [u8] {
301 match self {
302 Self::SaoMerge => &[153],
303 Self::SaoType => &[200],
304 Self::SplitCu => &[139, 141, 157],
305 Self::TransquantBypass => &[154],
306 Self::PartMode => &[184],
307 Self::PrevIntraLumaPred => &[184],
308 Self::IntraChromaPredMode => &[63],
309 Self::SplitTransform => &[153, 138, 138],
310 Self::CbfLuma => &[111, 141],
311 // Four by depth in the transform tree, and a fifth for the second chroma block of a
312 // 4:2:2 picture, which this decoder will not meet but which sits in the same table.
313 Self::CbfChroma => &[94, 138, 182, 154, 154],
314 Self::CuQpDeltaAbs => &[154, 154],
315 // One for luma and one for chroma; the specification numbers them 0 and 3.
316 Self::TransformSkip => &[139, 139],
317 Self::LastSigX => &[
318 110, 110, 124, 125, 140, 153, 125, 127, 140,
319 109, 111, 143, 127, 111, 79, 108, 123, 63,
320 ],
321 Self::LastSigY => &[
322 110, 110, 124, 125, 140, 153, 125, 127, 140,
323 109, 111, 143, 127, 111, 79, 108, 123, 63,
324 ],
325 Self::CodedSubBlock => &[91, 171, 134, 141],
326 Self::SigCoeff => &[
327 111, 111, 125, 110, 110, 94, 124, 108,
328 124, 107, 125, 141, 179, 153, 125, 107,
329 125, 141, 179, 153, 125, 107, 125, 141,
330 179, 153, 125, 140, 139, 182, 182, 152,
331 136, 152, 136, 153, 136, 139, 111, 136,
332 139, 111,
333 // The two the specification puts at 126 and 127, for a block coded without its
334 // transform.
335 141, 111,
336 ],
337 Self::Greater1 => &[
338 140, 92, 137, 138, 140, 152, 138, 139,
339 153, 74, 149, 92, 139, 107, 122, 152,
340 140, 179, 166, 182, 140, 227, 122, 197,
341 ],
342 Self::Greater2 => &[138, 153, 136, 167, 152, 152],
343 }
344 }
345
346 pub const fn len(self) -> usize {
347 self.init().len()
348 }
349
350 pub const fn is_empty(self) -> bool {
351 self.len() == 0
352 }
353
354 /// Where the set's variables begin in the flat array [`Contexts`] holds.
355 pub const fn base(self) -> usize {
356 let mut at = 0;
357 let mut i = 0;
358 while i < Self::ALL.len() {
359 if Self::ALL[i] as u8 == self as u8 {
360 return at;
361 }
362 at += Self::ALL[i].len();
363 i += 1;
364 }
365 at
366 }
367
368 /// Which published table the values in [`Set::init`] were taken from, as its number within
369 /// clause 9 -- `5` for Table 9-5.
370 ///
371 /// Kept so that the transcription can be checked against the document rather than against
372 /// itself; `tests` does exactly that where a copy of the specification is to hand.
373 pub const fn table(self) -> usize {
374 match self {
375 Self::SaoMerge => 5,
376 Self::SaoType => 6,
377 Self::SplitCu => 7,
378 Self::TransquantBypass => 8,
379 Self::PartMode => 11,
380 Self::PrevIntraLumaPred => 12,
381 Self::IntraChromaPredMode => 13,
382 Self::SplitTransform => 20,
383 Self::CbfLuma => 21,
384 Self::CbfChroma => 22,
385 Self::CuQpDeltaAbs => 24,
386 Self::TransformSkip => 25,
387 Self::LastSigX => 26,
388 Self::LastSigY => 27,
389 Self::CodedSubBlock => 28,
390 Self::SigCoeff => 29,
391 Self::Greater1 => 30,
392 Self::Greater2 => 31,
393 }
394 }
395
396 /// Which of that table's entries an intra slice takes, as runs of `(first, how many)`.
397 ///
398 /// Table 9-4 gives these as ranges against the initialisation type, and for an intra slice they
399 /// are the first ones -- except where a table serves two syntax elements at once, or where the
400 /// entries a still picture wants are not next to each other.
401 pub const fn runs(self) -> &'static [(usize, usize)] {
402 match self {
403 // Four by depth at 0..3, and the odd one out at 12.
404 Self::CbfChroma => &[(0, 4), (12, 1)],
405 // Luma at 0 and chroma at 3.
406 Self::TransformSkip => &[(0, 1), (3, 1)],
407 // Nought to forty-one, and then two a long way further on.
408 Self::SigCoeff => &[(0, 42), (126, 2)],
409 // Everything else is a run from the start of its table.
410 other => match other.len() {
411 // One run, as long as the set is. Written this way because a `const fn` cannot
412 // hold a reference to a temporary, so each length that occurs gets its own.
413 1 => &[(0, 1)],
414 2 => &[(0, 2)],
415 3 => &[(0, 3)],
416 4 => &[(0, 4)],
417 6 => &[(0, 6)],
418 18 => &[(0, 18)],
419 24 => &[(0, 24)],
420 _ => &[],
421 },
422 }
423 }
424}
425
426// How many context variables a picture's decoder carries altogether.
427pub const CONTEXTS: usize = {
428 let mut at = 0;
429 let mut i = 0;
430 while i < Set::ALL.len() {
431 at += Set::ALL[i].len();
432 i += 1;
433 }
434 at
435};
436
437/// Every context variable a still picture's decoder needs, in one array.
438///
439/// One flat array with a base per set, rather than a struct of named arrays, because the whole lot
440/// is **copied** at the start of every row of blocks under wavefront coding -- which every
441/// photograph in the corpus this was written against uses -- and a copy of one fixed-size array is
442/// as cheap as copying gets.
443#[derive(Clone, Copy, Debug)]
444pub struct Contexts {
445 v: [Ctx; CONTEXTS],
446}
447
448impl Contexts {
449
450 /// The state every context starts a slice in, given that slice's quantisation parameter.
451 pub fn start(qp: i32) -> Self {
452 let mut v = [Ctx::start(154, 26); CONTEXTS];
453 for set in Set::ALL {
454 let base = set.base();
455 let init = set.init();
456 let mut i = 0;
457 while i < init.len() {
458 v[base + i] = Ctx::start(init[i], qp);
459 i += 1;
460 }
461 }
462 Self { v }
463 }
464
465 /// One context variable: which set, and which of that set's variables the syntax says applies.
466 ///
467 /// An index past the end of its set is a fault in whoever worked out the increment, not a thing
468 /// to be clamped quietly into range: a decoder that reads the wrong context produces a picture
469 /// rather than an error, and a picture that is subtly wrong is the hardest kind of fault to
470 /// find. So it is refused, and the message says which set and which index.
471 pub fn at(&mut self, set: Set, i: usize) -> Outcome<&mut Ctx> {
472 if i >= set.len() {
473 return Err(err!(
474 "Context {} of {:?} was asked for, and that set holds {}.", i, set, set.len();
475 Invalid, Input, Decode));
476 }
477 Ok(&mut self.v[set.base() + i])
478 }
479}
480
481/// The context state carried from one row of blocks to the next, under wavefront coding.
482///
483/// Every photograph in the corpus is coded in wavefronts (`entropy_coding_sync_enabled_flag`),
484/// which is the surprise that shapes this decoder: the arithmetic coder is **restarted at every row
485/// of coding tree blocks**, and the contexts it restarts with are not fresh ones but the ones saved
486/// after the *second* block of the row above. That is what lets an encoder code the rows in
487/// parallel while still learning from what came before, and it means a decoder that treats a row
488/// boundary as a fresh start decodes plausible rubbish from the second row onward.
489///
490/// This holds the one-slice, one-tile case, which is every picture in the corpus and every picture a
491/// still image is likely to be. A second tile would need one of these each, since a tile boundary
492/// breaks the dependency; the widening is a field, not a redesign, and is left until a picture
493/// wants it.
494#[derive(Clone, Copy, Debug)]
495pub struct Rows {
496 qp: i32, // what a slice starts from, the first row having nothing above
497 saved: Option<Contexts>, // what was saved after the second block of the row above
498}
499
500impl Rows {
501
502 /// A picture whose first row has nothing to inherit.
503 pub fn new(qp: i32) -> Self {
504 Self { qp, saved: None }
505 }
506
507 /// The contexts a row of blocks begins with.
508 ///
509 /// The row above's second block where there was one, and a fresh set where there was not --
510 /// which is the first row, and only the first row.
511 pub fn begin(&self) -> Contexts {
512 match self.saved {
513 Some(ctxs) => ctxs,
514 None => Contexts::start(self.qp),
515 }
516 }
517
518 /// Keeps the state as it stands, which the caller does once the **second** block of a row has
519 /// been decoded (§9.3.2.3).
520 ///
521 /// Not the first: the row above has to be two blocks ahead before the row below may start, or
522 /// the two would be coding the same neighbourhood at once.
523 pub fn after_second(&mut self, ctxs: &Contexts) {
524 self.saved = Some(*ctxs);
525 }
526}
527
528#[cfg(test)]
529mod tests {
530 use super::*;
531
532 #[test]
533 fn test_every_context_starts_in_a_state_that_exists_03() -> Outcome<()> {
534 // Two hundred and fifty-six initialisation values against every quantisation parameter a
535 // slice may carry, including the negative ones a high-bit-depth picture allows. The state
536 // this yields indexes a table of sixty-four rows, and the arithmetic that produces it is
537 // the specification's own -- so an index outside it is a transcription error, and the only
538 // way to find one before the whole decoder exists is to try them all.
539 for init in 0..=255u8 {
540 for qp in -12..=51i32 {
541 let ctx = Ctx::start(init, qp);
542 let state = ctx.state();
543 if state > 62 {
544 return Err(err!(
545 "An initialisation value of {} at a quantisation parameter of {} starts in \
546 state {}, and 62 is the highest.", init, qp, state;
547 Test, Invalid));
548 }
549 }
550 }
551 Ok(())
552 }
553
554 #[test]
555 fn test_the_interval_is_renormalised_after_every_bin_04() -> Outcome<()> {
556 // The invariant the whole arithmetic decoder rests on: the interval is at least 256 and at
557 // most 510 whenever a bin has been answered. A renormalisation that stops one shift short
558 // decodes plausible rubbish rather than failing, which is exactly the sort of fault that
559 // survives until a picture comes out wrong, so it is asserted directly.
560 //
561 // The data is a run of bytes from a small linear congruential sequence: it is not a coded
562 // picture and does not have to be, since the invariant holds over any input at all.
563 let mut seed = 0x2545_f491_4f6c_dd1du64;
564 let mut data = Vec::with_capacity(4096);
565 for _ in 0..4096 {
566 seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
567 data.push((seed >> 33) as u8);
568 }
569 let mut cabac = res!(Cabac::new(&data));
570 let mut ctxs: Vec<Ctx> = (0..16).map(|i| Ctx::start(i * 17, 26)).collect();
571 let mut ones = 0usize;
572 let total = 20_000usize;
573 for i in 0..total {
574 match i % 8 {
575 7 => {
576 // A terminating bin, which is asked once a block. Where it says the data has
577 // ended, the decoder stops -- and on random bytes it will, eventually.
578 if cabac.terminate() == 1 {
579 break;
580 }
581 },
582 6 => {
583 ones += cabac.bypass() as usize;
584 },
585 k => {
586 ones += cabac.bin(&mut ctxs[k * 2]) as usize;
587 },
588 }
589 if cabac.range < 256 || cabac.range > 510 {
590 return Err(err!(
591 "After {} bins the interval is {}, outside 256 to 510.", i + 1, cabac.range;
592 Test, Invalid));
593 }
594 }
595 // A decoder that answered every bin the same way would satisfy the invariant above and be
596 // useless, so the answers are required to be mixed.
597 if ones == 0 {
598 return Err(err!("Not one bin came back as a one."; Test, Invalid));
599 }
600 Ok(())
601 }
602
603 #[test]
604 fn test_the_context_tables_are_the_published_ones_06() -> Outcome<()> {
605 // Two hundred and thirty numbers copied out of a document by hand, every one of which
606 // silently ruins a picture if it is wrong. Checking them against the decoder that uses them
607 // proves nothing at all -- the only thing worth checking them against is the specification
608 // they came from, so this reads it.
609 //
610 // pdftotext -layout T-REC-H.265-202108.pdf h265.txt
611 // HEVC_SPEC_TEXT=~/.cache/specs/h265.txt cargo test -p oxedyne_fe2o3_graphics hevc
612 //
613 // Absent, it says so rather than passing quietly: a check that skipped in silence would be
614 // a check nobody ran.
615 let path = match std::env::var("HEVC_SPEC_TEXT") {
616 Ok(p) => p,
617 Err(_) => {
618 println!(" skipped: set HEVC_SPEC_TEXT to a text rendering of Rec. ITU-T H.265");
619 return Ok(());
620 },
621 };
622 let text = match std::fs::read_to_string(&path) {
623 Ok(t) => t,
624 Err(e) => {
625 println!(" skipped: {} would not read ({})", path, e);
626 return Ok(());
627 },
628 };
629 let lines: Vec<&str> = text.lines().collect();
630
631 for set in Set::ALL {
632 // The table's own numbers, in ctxIdx order: every "initValue" row under the heading,
633 // until the next table begins. The document lays a wide table out as alternating rows
634 // of indices and values, so the values arrive in several pieces and in order.
635 let heading = fmt!("Table 9-{} – Values of initValue", set.table());
636 // The heading occurs twice: once in the table of contents, trailing dot leaders and a
637 // page number, and once over the table itself. Taking whichever one has values under it
638 // needs no rule about which is which.
639 let mut published: Vec<u8> = Vec::new();
640 for (start, _) in lines.iter().enumerate().filter(|(_, l)| l.contains(&heading)) {
641 let mut found: Vec<u8> = Vec::new();
642 for line in lines.iter().skip(start + 1) {
643 let trimmed = line.trim_start();
644 if trimmed.starts_with("Table 9-") {
645 break;
646 }
647 if !trimmed.starts_with("initValue") {
648 continue;
649 }
650 for word in trimmed.trim_start_matches("initValue").split_whitespace() {
651 match word.parse::<u16>() {
652 // Every initValue is a byte. A page number caught in the same row
653 // would not be, and shows up here rather than as a wrong picture.
654 Ok(n) if n <= 255 => found.push(n as u8),
655 _ => return Err(err!(
656 "Table 9-{} holds {:?}, which is not an initialisation value.",
657 set.table(), word; Test, Invalid)),
658 }
659 }
660 }
661 if !found.is_empty() {
662 published = found;
663 break;
664 }
665 }
666 if published.is_empty() {
667 return Err(err!(
668 "Table 9-{} is not in {}, or holds no values.", set.table(), path;
669 Test, Missing));
670 }
671 // What an intra slice takes out of it, per Table 9-4.
672 let mut wanted: Vec<u8> = Vec::new();
673 for (first, count) in set.runs() {
674 let end = first + count;
675 if end > published.len() {
676 return Err(err!(
677 "{:?} wants entries {}..{} of Table 9-{}, which holds {}.",
678 set, first, end, set.table(), published.len(); Test, Invalid));
679 }
680 wanted.extend_from_slice(&published[*first..end]);
681 }
682 let held: Vec<u8> = set.init().to_vec();
683 if held != wanted {
684 return Err(err!(
685 "{:?} is initialised from {:?}, and Table 9-{} entries {:?} are {:?}.",
686 set, held, set.table(), set.runs(), wanted; Test, Mismatch));
687 }
688 }
689 Ok(())
690 }
691
692 #[test]
693 fn test_a_row_of_blocks_inherits_the_row_above_it_07() -> Outcome<()> {
694 // The wavefront rule, which is the one every photograph in the corpus depends on: a row of
695 // blocks starts from the contexts saved after the *second* block of the row above, not from
696 // fresh ones. A decoder that starts each row afresh decodes rubbish from the second row on,
697 // and this is the smallest statement of the difference.
698 let mut rows = Rows::new(26);
699 let fresh = rows.begin();
700 let mut moved = fresh;
701 // Something the first row learned, which the second must not lose.
702 let ctx = res!(moved.at(Set::SigCoeff, 0));
703 let before = *ctx;
704 *ctx = Ctx::start(200, 51);
705 let learned = *res!(moved.at(Set::SigCoeff, 0));
706 let changed = learned != before;
707 req!(changed, true, "the fixture did not change anything, so it proves nothing");
708
709 rows.after_second(&moved);
710 let next = rows.begin();
711 let carried = next.v[Set::SigCoeff.base()];
712 req!(carried, learned, "a row began afresh instead of from the row above it");
713
714 // And a picture whose first row has nothing above it starts from the table.
715 let first = Rows::new(26).begin();
716 req!(first.v[Set::SigCoeff.base()], before);
717 Ok(())
718 }
719
720 #[test]
721 fn test_the_context_sets_do_not_overlap_or_leave_gaps_08() -> Outcome<()> {
722 // The bases are worked out by summing the lengths in front of each set, so a set added in
723 // the middle of the list moves every one after it. That is the intended behaviour and it is
724 // also exactly how one set would come to share variables with another, so it is asserted.
725 let mut at = 0usize;
726 for set in Set::ALL {
727 req!(set.base(), at, "{:?} does not begin where the set before it ends", set);
728 at += set.len();
729 let empty = set.is_empty();
730 req!(empty, false, "{:?} holds no context variables at all", set);
731 }
732 req!(at, CONTEXTS);
733 // And the last one is reachable, while one past it is refused rather than read.
734 let mut ctxs = Contexts::start(26);
735 let last = Set::Greater2.len() - 1;
736 req!(ctxs.at(Set::Greater2, last).is_ok(), true);
737 req!(ctxs.at(Set::Greater2, last + 1).is_err(), true,
738 "a context past the end of its set was handed out");
739 Ok(())
740 }
741
742 #[test]
743 fn test_a_decoder_needs_two_bytes_to_begin_05() -> Outcome<()> {
744 req!(Cabac::new(&[0x40]).is_err(), true,
745 "A decoder started on one byte, and it reads two before answering anything.");
746 Ok(())
747 }
748}