Oregami
Repositories/oxedyne/fe2o3

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

5.5 KiB, 18 runs

created by r1870400018:20519, 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 three orders coefficients are read in (§6.5.3 to §6.5.5).
2//!
3//! A transform block is read as a grid of four-by-four sub-blocks, and both the sub-blocks and the
4//! coefficients within one are visited in the same order: up the diagonals, along the rows, or down
5//! the columns. Which of the three a block uses is settled by its intra prediction mode -- a block
6//! predicted nearly horizontally has its energy in the vertical direction, so it is read down the
7//! columns, and the other way about.
8//!
9//! Every scan runs **backwards** in the bitstream: the coefficient furthest from the corner is coded
10//! first and the direct one last, which is why the syntax begins by saying where the last one is.
11//!
12//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
13//! Anthropic Claude
14
15/// Which way a block is read.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum Order {
18 Diagonal, // up from the top left, which all but the smallest blocks use
19 Horizontal, // along the rows, for a block predicted from nearly vertical
20 Vertical, // down the columns, for one predicted from nearly horizontal
21}
22
23impl Order {
24
25 /// Which order a block of this size and prediction mode is read in (§7.4.9.11).
26 ///
27 /// Only the two smallest luma sizes, and the smallest chroma one, choose by mode at all;
28 /// everything larger is read up the diagonals whatever it was predicted from.
29 pub fn of(log2_size: u32, chroma: bool, mode: u8) -> Self {
30 let chooses = log2_size == 2 || (log2_size == 3 && !chroma);
31 if !chooses {
32 return Self::Diagonal;
33 }
34 match mode {
35 6..=14 => Self::Vertical,
36 22..=30 => Self::Horizontal,
37 _ => Self::Diagonal,
38 }
39 }
40}
41
42/// Position `i` of the result is where the `i`th coefficient in coding order sits, as `(x, y)`.
43/// Sizes are 1, 2, 4 and 8 for the sub-block grid and always 4 for the coefficients within one.
44pub fn positions(size: usize, order: Order) -> Vec<(u8, u8)> {
45 let mut out = Vec::with_capacity(size * size);
46 match order {
47 Order::Horizontal => for y in 0..size {
48 for x in 0..size {
49 out.push((x as u8, y as u8));
50 }
51 },
52 Order::Vertical => for x in 0..size {
53 for y in 0..size {
54 out.push((x as u8, y as u8));
55 }
56 },
57 // Up and to the right, starting each diagonal at the bottom left of it: the loop in the
58 // specification walks x up and y down, then restarts one row lower.
59 Order::Diagonal => {
60 let (mut x, mut y) = (0usize, 0usize);
61 loop {
62 loop {
63 if x < size && y < size {
64 out.push((x as u8, y as u8));
65 }
66 if y == 0 {
67 break;
68 }
69 y -= 1;
70 x += 1;
71 }
72 y = x + 1;
73 x = 0;
74 if out.len() >= size * size {
75 break;
76 }
77 }
78 },
79 }
80 out
81}
82
83/// Every scan a picture needs, worked out once.
84///
85/// Four sizes of sub-block grid -- a four-sample block is one sub-block, a thirty-two-sample block
86/// is eight by eight of them -- in three orders each.
87#[derive(Clone, Debug)]
88pub struct Scans {
89 grids: [[Vec<(u8, u8)>; 3]; 4], // by base-two logarithm of the grid's side, then by order
90}
91
92impl Scans {
93
94 pub fn new() -> Self {
95 let orders = [Order::Diagonal, Order::Horizontal, Order::Vertical];
96 let grids = std::array::from_fn(|log2| {
97 std::array::from_fn(|o| positions(1 << log2, orders[o]))
98 });
99 Self { grids }
100 }
101
102 /// The scan of a square whose side is `1 << log2`, in `order`.
103 pub fn of(&self, log2: u32, order: Order) -> &[(u8, u8)] {
104 let o = match order {
105 Order::Diagonal => 0,
106 Order::Horizontal => 1,
107 Order::Vertical => 2,
108 };
109 &self.grids[(log2 as usize).min(3)][o]
110 }
111}
112
113impl Default for Scans {
114 fn default() -> Self {
115 Self::new()
116 }
117}
118
119#[cfg(test)]
120mod tests {
121 use super::*;
122 use oxedyne_fe2o3_core::prelude::*;
123
124 #[test]
125 fn test_every_scan_visits_every_position_once_00() -> Outcome<()> {
126 for size in [1usize, 2, 4, 8] {
127 for order in [Order::Diagonal, Order::Horizontal, Order::Vertical] {
128 let scan = positions(size, order);
129 req!(scan.len(), size * size, "{:?} at {} is the wrong length", order, size);
130 let mut seen = vec![false; size * size];
131 for (x, y) in &scan {
132 let at = *y as usize * size + *x as usize;
133 req!(seen[at], false, "{:?} at {} visits ({}, {}) twice", order, size, x, y);
134 seen[at] = true;
135 }
136 }
137 }
138 Ok(())
139 }
140
141 #[test]
142 fn test_the_diagonal_goes_up_and_to_the_right_01() -> Outcome<()> {
143 // The order a four-by-four block of coefficients is read in, written out. Getting this
144 // backwards -- down and to the left, which is the other reasonable guess -- puts every
145 // coefficient of every block in the wrong place.
146 let scan = positions(4, Order::Diagonal);
147 req!(scan[0], (0u8, 0u8));
148 req!(scan[1], (0u8, 1u8));
149 req!(scan[2], (1u8, 0u8));
150 req!(scan[3], (0u8, 2u8));
151 req!(scan[4], (1u8, 1u8));
152 req!(scan[5], (2u8, 0u8));
153 req!(scan[15], (3u8, 3u8));
154 Ok(())
155 }
156
157 #[test]
158 fn test_the_scan_order_follows_the_prediction_02() -> Outcome<()> {
159 // A block predicted from nearly horizontal is read down its columns, and one predicted
160 // from nearly vertical along its rows -- the opposite of the direction, because that is
161 // where the residual's energy lies.
162 req!(Order::of(2, false, 10), Order::Vertical, "horizontal prediction");
163 req!(Order::of(2, false, 26), Order::Horizontal, "vertical prediction");
164 req!(Order::of(2, false, 0), Order::Diagonal, "planar");
165 // Only the smallest blocks choose. Eight-sample luma does, eight-sample chroma does not.
166 req!(Order::of(3, false, 10), Order::Vertical);
167 req!(Order::of(3, true, 10), Order::Diagonal);
168 req!(Order::of(4, false, 10), Order::Diagonal);
169 Ok(())
170 }
171}