Skip to main content

threers_codec/av1/
encoder.rs

1//! Key frames: headers, block decisions and the coefficient syntax.
2
3use std::f32::consts::PI;
4
5use super::bitwriter::{obu, BitWriter};
6use super::range::RangeEncoder;
7use crate::decode::av1::cdf::CdfContext;
8use crate::decode::av1::env::{gather_left_partition_prob, gather_top_partition_prob};
9use crate::decode::av1::itx::itxfm_add;
10use crate::decode::av1::levels::*;
11use crate::decode::av1::obu::Layout;
12use crate::decode::av1::recon::{get_dc_sign_ctx, get_lo_ctx, get_skip_ctx};
13use crate::decode::av1::tables::{
14    AL_PART_CTX, BLOCK_SIZES, DQ_TBL, LO_CTX_OFFSETS, PARTITION_TYPE_COUNT, SCANS, TXFM_DIMENSIONS,
15    TX_TYPES_PER_SET,
16};
17
18const OBU_SEQUENCE_HEADER: u8 = 1;
19const OBU_TEMPORAL_DELIMITER: u8 = 2;
20const OBU_FRAME: u8 = 6;
21
22/// An AV1 encoder for 8-bit 4:2:0 pictures whose sides are multiples of 8, so
23/// that every block lies inside the frame. Each picture becomes one temporal
24/// unit, independently decodable; see [the module docs](super).
25///
26/// At `qidx` 0 it is lossless: AV1's lossless mode, the 4×4 Walsh–Hadamard
27/// transform without quantisation, so a decoder returns the planes exactly.
28pub struct Av1Encoder {
29    width: usize,
30    height: usize,
31    qidx: u8,
32    cdf: Box<CdfContext>,
33    /// Orthonormal DCT rows, by log2 of the size.
34    bases: [Vec<f32>; 6],
35    wrote_sequence: bool,
36}
37
38/// One frame's state: the reconstruction, and what later blocks read of
39/// earlier ones.
40struct Frame<'a> {
41    src: [&'a [u8]; 3],
42    /// This frame's probabilities, adapting as symbols are coded (each frame
43    /// starts again from the defaults).
44    cdf: Box<CdfContext>,
45    rec: [Vec<u16>; 3],
46    strides: [usize; 3],
47    enc: RangeEncoder,
48    /// Per 8 luma pixels, across the frame and down the superblock.
49    above_part: Vec<u8>,
50    left_part: [u8; 16],
51    /// Per 4 luma pixels.
52    above_skip: Vec<u8>,
53    left_skip: Vec<u8>,
54    /// Coefficient contexts, luma then the two chromas, per 4 samples.
55    above_coef: [Vec<u8>; 3],
56    left_coef: [Vec<u8>; 3],
57    w4: usize,
58    h4: usize,
59}
60
61impl Av1Encoder {
62    /// An encoder at quantiser `qidx`: 0 is lossless, 1 nearly so, up to 255.
63    pub fn new(width: usize, height: usize, qidx: u8) -> Result<Self, String> {
64        if width == 0 || height == 0 || !width.is_multiple_of(8) || !height.is_multiple_of(8) {
65            return Err(format!(
66                "AV1 encoder needs sides that are multiples of 8, not {width}x{height}"
67            ));
68        }
69        if width > 65536 || height > 65536 {
70            return Err("AV1 frame is too large".into());
71        }
72        let bases = std::array::from_fn(|log2| {
73            let n = 1usize << log2;
74            let mut m = vec![0f32; n * n];
75            for k in 0..n {
76                let scale = if k == 0 {
77                    (1.0 / n as f32).sqrt()
78                } else {
79                    (2.0 / n as f32).sqrt()
80                };
81                for i in 0..n {
82                    m[k * n + i] =
83                        scale * (PI * (2 * i + 1) as f32 * k as f32 / (2 * n) as f32).cos();
84                }
85            }
86            m
87        });
88        Ok(Av1Encoder {
89            width,
90            height,
91            qidx,
92            cdf: CdfContext::default_for(qidx),
93            bases,
94            wrote_sequence: false,
95        })
96    }
97
98    /// One picture as planes with no padding between rows, chroma at half
99    /// size each way. Returns a temporal unit, with the sequence header on
100    /// the first.
101    pub fn encode(&mut self, y: &[u8], u: &[u8], v: &[u8]) -> Result<Vec<u8>, String> {
102        let (w, h) = (self.width, self.height);
103        if y.len() != w * h || u.len() != w * h / 4 || v.len() != w * h / 4 {
104            return Err("AV1 encoder: plane sizes do not match the frame".into());
105        }
106        let mut out = Vec::new();
107        obu(OBU_TEMPORAL_DELIMITER, &[], &mut out);
108        if !self.wrote_sequence {
109            obu(OBU_SEQUENCE_HEADER, &self.sequence_header(), &mut out);
110            self.wrote_sequence = true;
111        }
112        let mut payload = self.frame_header();
113        payload.extend(self.tile(y, u, v));
114        obu(OBU_FRAME, &payload, &mut out);
115        Ok(out)
116    }
117
118    fn sequence_header(&self) -> Vec<u8> {
119        let mut b = BitWriter::default();
120        b.put(0, 3); // seq_profile: Main
121        b.flag(false); // still_picture
122        b.flag(false); // reduced_still_picture_header
123        b.flag(false); // timing_info_present_flag
124        b.flag(false); // initial_display_delay_present_flag
125        b.put(0, 5); // operating_points_cnt_minus_1
126        b.put(0, 12); // operating_point_idc
127        b.put(31, 5); // seq_level_idx: no level claimed
128        b.flag(false); // seq_tier
129        b.put(15, 4); // frame_width_bits_minus_1
130        b.put(15, 4); // frame_height_bits_minus_1
131        b.put(self.width as u32 - 1, 16);
132        b.put(self.height as u32 - 1, 16);
133        b.flag(false); // frame_id_numbers_present_flag
134        b.flag(false); // use_128x128_superblock
135        b.flag(false); // enable_filter_intra
136        b.flag(false); // enable_intra_edge_filter
137        b.flag(false); // enable_interintra_compound
138        b.flag(false); // enable_masked_compound
139        b.flag(false); // enable_warped_motion
140        b.flag(false); // enable_dual_filter
141        b.flag(false); // enable_order_hint
142        b.flag(false); // seq_choose_screen_content_tools
143        b.flag(false); // seq_force_screen_content_tools
144        b.flag(false); // enable_superres
145        b.flag(false); // enable_cdef
146        b.flag(false); // enable_restoration
147        b.flag(false); // high_bitdepth
148        b.flag(false); // mono_chrome
149        b.flag(false); // color_description_present_flag
150        b.flag(false); // color_range: studio
151        b.put(0, 2); // chroma_sample_position
152        b.flag(false); // separate_uv_delta_q
153        b.flag(false); // film_grain_params_present
154        b.trailing()
155    }
156
157    fn frame_header(&self) -> Vec<u8> {
158        let mut b = BitWriter::default();
159        b.flag(false); // show_existing_frame
160        b.put(0, 2); // frame_type: KEY_FRAME
161        b.flag(true); // show_frame
162        b.flag(false); // disable_cdf_update: probabilities adapt
163        b.flag(false); // frame_size_override_flag
164        b.flag(false); // render_and_frame_size_different
165        b.flag(true); // disable_frame_end_update_cdf: each frame stands alone
166                      // tile_info: one tile.
167        b.flag(true); // uniform_tile_spacing_flag
168        let tile_log2 = |n: usize| {
169            let mut k = 0;
170            while (1usize << k) < n {
171                k += 1;
172            }
173            k
174        };
175        if tile_log2(self.width.div_ceil(64).min(64)) > 0 {
176            b.flag(false); // increment_tile_cols_log2
177        }
178        if tile_log2(self.height.div_ceil(64).min(64)) > 0 {
179            b.flag(false); // increment_tile_rows_log2
180        }
181        // quantization_params
182        b.put(self.qidx as u32, 8);
183        b.flag(false); // DeltaQYDc
184        b.flag(false); // DeltaQUDc
185        b.flag(false); // DeltaQUAc
186        b.flag(false); // using_qmatrix
187        b.flag(false); // segmentation_enabled
188        if self.lossless() {
189            // CodedLossless: no delta_q_present (base_q_idx is 0), no loop
190            // filter parameters and no tx mode (4×4 only) are coded.
191        } else {
192            b.flag(false); // delta_q_present
193                           // loop_filter_params: off.
194            b.put(0, 6);
195            b.put(0, 6);
196            b.put(0, 3); // loop_filter_sharpness
197            b.flag(false); // loop_filter_delta_enabled
198            b.flag(false); // tx_mode_select: TX_MODE_LARGEST
199        }
200        b.flag(true); // reduced_tx_set
201        b.aligned()
202    }
203
204    fn tile(&self, y: &[u8], u: &[u8], v: &[u8]) -> Vec<u8> {
205        let (w, h) = (self.width, self.height);
206        let (w4, h4) = (w / 4, h / 4);
207        let mut f = Frame {
208            src: [y, u, v],
209            cdf: Box::new(*self.cdf),
210            rec: [vec![0; w * h], vec![0; w * h / 4], vec![0; w * h / 4]],
211            strides: [w, w / 2, w / 2],
212            enc: RangeEncoder::new(),
213            above_part: vec![0; w4 / 2 + 16],
214            left_part: [0; 16],
215            above_skip: vec![0; w4 + 32],
216            left_skip: vec![0; 32],
217            above_coef: [
218                vec![0x40; w4 + 32],
219                vec![0x40; w4 + 32],
220                vec![0x40; w4 + 32],
221            ],
222            left_coef: [vec![0x40; 32], vec![0x40; 32], vec![0x40; 32]],
223            w4,
224            h4,
225        };
226        for by in (0..h4).step_by(16) {
227            f.left_part = [0; 16];
228            f.left_skip.fill(0);
229            for l in &mut f.left_coef {
230                l.fill(0x40);
231            }
232            for bx in (0..w4).step_by(16) {
233                self.partition(&mut f, BL_64X64, bx, by);
234            }
235        }
236        f.enc.finish()
237    }
238
239    /// `decode_sb`, with blocks of 64 always split and any crossing the frame
240    /// edge split until they do not.
241    fn partition(&self, f: &mut Frame, bl: usize, bx: usize, by: usize) {
242        let hsz = 16usize >> bl;
243        let have_h = f.w4 > bx + hsz;
244        let have_v = f.h4 > by + hsz;
245        if !have_h && !have_v {
246            return self.partition(f, bl + 1, bx, by);
247        }
248        let by8 = (by & 31) >> 1;
249        let shift = 4 - bl;
250        let ctx = ((f.above_part[bx >> 1] >> shift) & 1) as usize
251            + ((((f.left_part[by8] >> shift) & 1) as usize) << 1);
252        let bp;
253        if have_h && have_v {
254            let fits = bx + 2 * hsz <= f.w4 && by + 2 * hsz <= f.h4;
255            // Lossless transforms are 4×4 whatever the block, so large blocks
256            // only save mode symbols.
257            let split = bl < BL_8X8
258                && (bl < BL_32X32 || !fits || (!self.lossless() && self.busy(f, bl, bx, by)));
259            bp = if split {
260                PARTITION_SPLIT
261            } else {
262                PARTITION_NONE
263            };
264            f.enc.symbol_adapt(
265                &mut f.cdf.m.partition[bl][ctx],
266                PARTITION_TYPE_COUNT[bl] as usize,
267                bp,
268            );
269            if split {
270                self.partition(f, bl + 1, bx, by);
271                self.partition(f, bl + 1, bx + hsz, by);
272                self.partition(f, bl + 1, bx, by + hsz);
273                self.partition(f, bl + 1, bx + hsz, by + hsz);
274            } else {
275                self.block(f, bl, bx, by);
276            }
277        } else if have_h {
278            f.enc.bool(
279                gather_top_partition_prob(&f.cdf.m.partition[bl][ctx], bl),
280                true,
281            );
282            bp = PARTITION_SPLIT;
283            self.partition(f, bl + 1, bx, by);
284            self.partition(f, bl + 1, bx + hsz, by);
285        } else {
286            f.enc.bool(
287                gather_left_partition_prob(&f.cdf.m.partition[bl][ctx], bl),
288                true,
289            );
290            bp = PARTITION_SPLIT;
291            self.partition(f, bl + 1, bx, by);
292            self.partition(f, bl + 1, bx, by + hsz);
293        }
294        if bp != PARTITION_SPLIT || bl == BL_8X8 {
295            let n = hsz.min(16);
296            f.above_part[bx >> 1..(bx >> 1) + n].fill(AL_PART_CTX[0][bl][bp]);
297            f.left_part[by8..(by8 + n).min(16)].fill(AL_PART_CTX[1][bl][bp]);
298        }
299    }
300
301    /// Whether a block has more detail than one prediction and transform suit:
302    /// its halves differ, measured as luma variance against the quantiser.
303    fn busy(&self, f: &Frame, bl: usize, bx: usize, by: usize) -> bool {
304        let n = 8usize << (BL_8X8 - bl);
305        let stride = f.strides[0];
306        let (mut sum, mut sq) = (0u64, 0u64);
307        for y in 0..n {
308            let row = &f.src[0][(by * 4 + y) * stride + bx * 4..][..n];
309            for &p in row {
310                sum += p as u64;
311                sq += p as u64 * p as u64;
312            }
313        }
314        let count = (n * n) as u64;
315        let variance = (sq - sum * sum / count) / count;
316        let q = DQ_TBL[0][self.qidx as usize][1] as u64 / 8;
317        variance > (4 * q * q).max(16)
318    }
319
320    /// Whether this encoder is lossless (`qidx` 0).
321    fn lossless(&self) -> bool {
322        self.qidx == 0
323    }
324
325    /// One block: the mode syntax, then each plane's single transform.
326    fn block(&self, f: &mut Frame, bl: usize, bx: usize, by: usize) {
327        if self.lossless() {
328            return self.lossless_block(f, bl, bx, by);
329        }
330        let bs = BLOCK_SIZES[bl][PARTITION_NONE][0] as usize;
331        let log2 = 3 + BL_8X8 - bl;
332        let txs = [log2 - 2, log2 - 3, log2 - 3];
333        let mut coded = Vec::with_capacity(3);
334        for plane in 0..3 {
335            coded.push(self.transform(f, plane, txs[plane], bx, by));
336        }
337        let skip = coded.iter().all(|c| c.is_none());
338
339        let n4 = 1usize << (log2 - 2);
340        let ly = by & 31;
341        let sctx = (f.above_skip[bx] + f.left_skip[ly]) as usize;
342        f.enc.bool_adapt(&mut f.cdf.m.skip[sctx], skip);
343        f.above_skip[bx..bx + n4].fill(skip as u8);
344        f.left_skip[ly..ly + n4].fill(skip as u8);
345        f.enc
346            .symbol_adapt(&mut f.cdf.kfym[0][0], N_INTRA_PRED_MODES - 1, DC_PRED);
347        f.enc.symbol_adapt(
348            &mut f.cdf.m.uv_mode[1][DC_PRED],
349            N_UV_INTRA_PRED_MODES - 1,
350            DC_PRED,
351        );
352
353        if skip {
354            for plane in 0..3 {
355                let (x, y, n) = if plane == 0 {
356                    (bx, ly, n4)
357                } else {
358                    (bx / 2, ly / 2, n4 / 2)
359                };
360                f.above_coef[plane][x..x + n.max(1)].fill(0x40);
361                f.left_coef[plane][y..y + n.max(1)].fill(0x40);
362            }
363            return;
364        }
365        for (plane, levels) in coded.into_iter().enumerate() {
366            self.coefficients(f, plane, txs[plane], bs, bx, by, levels.as_deref());
367        }
368    }
369
370    /// A lossless block: 4×4 Walsh–Hadamard transforms in every plane, each
371    /// predicted from what the ones before reconstructed, in the order the
372    /// decoder reconstructs them: luma in raster order, then each chroma.
373    ///
374    /// The prediction is DC or Paeth, chosen for luma and for chroma by which
375    /// leaves the smaller residuals. A lossless reconstruction is the source, so
376    /// the choice can be measured on the source before anything is coded.
377    ///
378    /// The block is never coded as skipped: a skipped block predicts at the
379    /// block's own transform size, which need not reproduce the source.
380    fn lossless_block(&self, f: &mut Frame, bl: usize, bx: usize, by: usize) {
381        let bs = BLOCK_SIZES[bl][PARTITION_NONE][0] as usize;
382        let log2 = 3 + BL_8X8 - bl;
383        let n4 = 1usize << (log2 - 2);
384        let tiles = |plane: usize| if plane == 0 { n4 } else { (n4 / 2).max(1) };
385        let cost = |f: &Frame, planes: &[usize], mode: usize| -> u32 {
386            let mut sum = 0;
387            for &plane in planes {
388                let m = tiles(plane);
389                for ty in 0..m {
390                    for tx in 0..m {
391                        let (x0, y0) = tile_origin(plane, bx, by, tx, ty);
392                        let stride = f.strides[plane];
393                        let src = f.src[plane];
394                        let pred = predict4(|x, y| src[y * stride + x] as i32, x0, y0, mode);
395                        for (i, p) in pred.iter().enumerate() {
396                            sum +=
397                                (src[(y0 + i / 4) * stride + x0 + i % 4] as i32 - p).unsigned_abs();
398                        }
399                    }
400                }
401            }
402            sum
403        };
404        let pick = |f: &Frame, planes: &[usize]| {
405            if cost(f, planes, PAETH_PRED) < cost(f, planes, DC_PRED) {
406                PAETH_PRED
407            } else {
408                DC_PRED
409            }
410        };
411        let (y_mode, uv_mode) = (pick(f, &[0]), pick(f, &[1, 2]));
412        // (plane, block-relative position in that plane's 4×4 units, levels).
413        let mut coded: Vec<(usize, usize, usize, Option<Vec<i32>>)> = Vec::new();
414        for plane in 0..3 {
415            let mode = if plane == 0 { y_mode } else { uv_mode };
416            for ty in 0..tiles(plane) {
417                for tx in 0..tiles(plane) {
418                    coded.push((
419                        plane,
420                        tx,
421                        ty,
422                        self.lossless_transform(f, plane, bx, by, tx, ty, mode),
423                    ));
424                }
425            }
426        }
427
428        let ly = by & 31;
429        let sctx = (f.above_skip[bx] + f.left_skip[ly]) as usize;
430        f.enc.bool_adapt(&mut f.cdf.m.skip[sctx], false);
431        f.above_skip[bx..bx + n4].fill(0);
432        f.left_skip[ly..ly + n4].fill(0);
433        // DC and Paeth share mode context 0, so neighbours' modes need no tracking.
434        f.enc
435            .symbol_adapt(&mut f.cdf.kfym[0][0], N_INTRA_PRED_MODES - 1, y_mode);
436        // Lossless allows CfL only for a 4×4 chroma block.
437        let cfl_allowed = bl == BL_8X8;
438        f.enc.symbol_adapt(
439            &mut f.cdf.m.uv_mode[cfl_allowed as usize][y_mode],
440            N_UV_INTRA_PRED_MODES - 1 - !cfl_allowed as usize,
441            uv_mode,
442        );
443        for (plane, tx, ty, levels) in coded {
444            // `coefficients` takes positions in luma 4×4 units.
445            let k = if plane == 0 { 1 } else { 2 };
446            self.coefficients(
447                f,
448                plane,
449                TX_4X4,
450                bs,
451                bx + tx * k,
452                by + ty * k,
453                levels.as_deref(),
454            );
455        }
456    }
457
458    /// One lossless 4×4: DC or Paeth prediction from the reconstruction, the forward
459    /// Walsh–Hadamard transform of the residual (libaom's `av1_fwht4x4`, whose
460    /// outputs are the levels: the quantiser at `qidx` 0 is the transform's
461    /// own scale), and the decoder's inverse, which must give the source back.
462    fn lossless_transform(
463        &self,
464        f: &mut Frame,
465        plane: usize,
466        bx: usize,
467        by: usize,
468        tx: usize,
469        ty: usize,
470        mode: usize,
471    ) -> Option<Vec<i32>> {
472        let (x0, y0) = tile_origin(plane, bx, by, tx, ty);
473        let stride = f.strides[plane];
474        let rec = &mut f.rec[plane];
475        let pred = predict4(|x, y| rec[y * stride + x] as i32, x0, y0, mode);
476
477        let src = f.src[plane];
478        let mut residual = [0i32; 16];
479        for y in 0..4 {
480            for x in 0..4 {
481                residual[y * 4 + x] = src[(y0 + y) * stride + x0 + x] as i32 - pred[y * 4 + x];
482            }
483        }
484        let out = fwht4x4(&residual);
485        // The decoder's coefficients are column-major: `rc = x * 4 + y`, with
486        // x the horizontal frequency.
487        let mut levels = vec![0i32; 16];
488        let mut cf = vec![0i32; 16];
489        let mut any = false;
490        let mut last = 0;
491        for r in 0..4 {
492            for c in 0..4 {
493                let level = out[r * 4 + c];
494                let rc = c * 4 + r;
495                levels[rc] = level;
496                // Dequantised at `qidx` 0: × 4, which the inverse undoes.
497                cf[rc] = level * 4;
498                any |= level != 0;
499            }
500        }
501        for (i, &rc) in SCANS[TX_4X4].iter().enumerate() {
502            if levels[rc as usize] != 0 {
503                last = i as i32;
504            }
505        }
506        for y in 0..4 {
507            for x in 0..4 {
508                rec[(y0 + y) * stride + x0 + x] = pred[y * 4 + x] as u16;
509            }
510        }
511        if any {
512            itxfm_add(
513                rec,
514                y0 * stride + x0,
515                stride,
516                &mut cf,
517                last,
518                TX_4X4,
519                WHT_WHT,
520                255,
521            );
522        }
523        for y in 0..4 {
524            for x in 0..4 {
525                assert_eq!(
526                    rec[(y0 + y) * stride + x0 + x],
527                    src[(y0 + y) * stride + x0 + x] as u16,
528                    "AV1 lossless: reconstruction differs from the source"
529                );
530            }
531        }
532        any.then_some(levels)
533    }
534
535    /// Predict a plane of the block and reconstruct it: DC prediction, forward
536    /// DCT, quantisation and the decoder's own inverse. Returns the levels,
537    /// indexed as the decoder's `cf`, or `None` if all are zero.
538    fn transform(
539        &self,
540        f: &mut Frame,
541        plane: usize,
542        tx: usize,
543        bx: usize,
544        by: usize,
545    ) -> Option<Vec<i32>> {
546        let n = 4usize << tx;
547        let shift_c = (plane != 0) as usize;
548        let (x0, y0) = ((bx * 4) >> shift_c, (by * 4) >> shift_c);
549        let stride = f.strides[plane];
550        let rec = &mut f.rec[plane];
551
552        let mut sum = 0u32;
553        if y0 > 0 {
554            sum += rec[(y0 - 1) * stride + x0..][..n]
555                .iter()
556                .map(|&v| v as u32)
557                .sum::<u32>();
558        }
559        if x0 > 0 {
560            sum += (0..n)
561                .map(|i| rec[(y0 + i) * stride + x0 - 1] as u32)
562                .sum::<u32>();
563        }
564        let count = n as u32 * ((y0 > 0) as u32 + (x0 > 0) as u32);
565        let dc = (sum + count / 2).checked_div(count).unwrap_or(128);
566
567        // Rows then columns of the orthonormal DCT.
568        let log2 = tx + 2;
569        let base = &self.bases[log2];
570        let src = f.src[plane];
571        let residual: Vec<f32> = (0..n * n)
572            .map(|i| src[(y0 + i / n) * stride + x0 + i % n] as f32 - dc as f32)
573            .collect();
574        let mut rows = vec![0f32; n * n];
575        for y in 0..n {
576            for k in 0..n {
577                rows[y * n + k] = (0..n).map(|x| residual[y * n + x] * base[k * n + x]).sum();
578            }
579        }
580        let t_dim = TXFM_DIMENSIONS[tx];
581        let dq_shift = (t_dim.ctx as i32 - 2).max(0);
582        let dq = DQ_TBL[0][self.qidx as usize];
583        // What the inverse needs for an orthonormal coefficient of 1.
584        let gain = if tx == TX_32X32 { 4.0 } else { 8.0 };
585        let mut levels = vec![0i32; n * n];
586        let mut cf = vec![0i32; n * n];
587        let mut any = false;
588        let mut last = 0;
589        for x in 0..n {
590            for yf in 0..n {
591                let c: f32 = (0..n).map(|y| rows[y * n + x] * base[yf * n + y]).sum();
592                let q = dq[(x + yf != 0) as usize] as i32;
593                let target = c * gain * (1 << dq_shift) as f32;
594                let level = (target.abs() / q as f32 + 0.4) as i32;
595                if level != 0 {
596                    let rc = x * n + yf;
597                    let value = (q * level) >> dq_shift;
598                    levels[rc] = if c < 0.0 { -level } else { level };
599                    cf[rc] = if c < 0.0 { -value } else { value };
600                    any = true;
601                }
602            }
603        }
604        let scan = SCANS[tx];
605        for (i, &rc) in scan.iter().enumerate() {
606            if levels[rc as usize] != 0 {
607                last = i as i32;
608            }
609        }
610        for y in 0..n {
611            rec[(y0 + y) * stride + x0..][..n].fill(dc as u16);
612        }
613        if !any {
614            return None;
615        }
616        itxfm_add(
617            rec,
618            y0 * stride + x0,
619            stride,
620            &mut cf,
621            last,
622            tx,
623            DCT_DCT,
624            255,
625        );
626        Some(levels)
627    }
628
629    /// `decode_coefs` in reverse. Writes one transform's syntax and leaves its
630    /// context behind.
631    #[allow(clippy::too_many_arguments)]
632    fn coefficients(
633        &self,
634        f: &mut Frame,
635        plane: usize,
636        tx: usize,
637        bs: usize,
638        bx: usize,
639        by: usize,
640        levels: Option<&[i32]>,
641    ) {
642        let chroma = plane != 0;
643        let ci = chroma as usize;
644        let t_dim = TXFM_DIMENSIONS[tx];
645        let tctx = t_dim.ctx as usize;
646        let (ax, ly) = if chroma {
647            (bx / 2, (by & 31) / 2)
648        } else {
649            (bx, by & 31)
650        };
651        let mut ab = [0x40u8; 16];
652        let mut lb = [0x40u8; 16];
653        let w = t_dim.w as usize;
654        let h = t_dim.h as usize;
655        ab[..w].copy_from_slice(&f.above_coef[plane][ax..ax + w]);
656        lb[..h].copy_from_slice(&f.left_coef[plane][ly..ly + h]);
657        let sctx = get_skip_ctx(&t_dim, bs, &ab, &lb, chroma, Layout::I420);
658        let coef = &mut f.cdf.coef;
659        let enc = &mut f.enc;
660        enc.bool_adapt(&mut coef.skip[tctx][sctx], levels.is_none());
661        let Some(levels) = levels else {
662            f.above_coef[plane][ax..ax + w].fill(0x40);
663            f.left_coef[plane][ly..ly + h].fill(0x40);
664            return;
665        };
666
667        // Only luma below 32 pixels says which transform it used.
668        if !self.lossless() && !chroma && (t_dim.max as usize) + 1 < TX_64X64 {
669            let idx = TX_TYPES_PER_SET.iter().position(|&t| t == DCT_DCT).unwrap();
670            enc.symbol_adapt(
671                &mut f.cdf.m.txtp_intra2[t_dim.min as usize][DC_PRED],
672                4,
673                idx,
674            );
675        }
676
677        let slw = (t_dim.lw as usize).min(TX_32X32);
678        let slh = (t_dim.lh as usize).min(TX_32X32);
679        let tx2dszctx = slw + slh;
680        let scan = SCANS[tx];
681        let eob = scan
682            .iter()
683            .rposition(|&rc| levels[rc as usize] != 0)
684            .unwrap() as u32;
685
686        let bin = if eob < 2 {
687            eob
688        } else {
689            32 - eob.leading_zeros()
690        };
691        let ns = 4 + tx2dszctx;
692        let eob_cdf: &mut [u16] = match tx2dszctx {
693            0 => &mut coef.eob_bin_16[ci][0],
694            1 => &mut coef.eob_bin_32[ci][0],
695            2 => &mut coef.eob_bin_64[ci][0],
696            3 => &mut coef.eob_bin_128[ci][0],
697            4 => &mut coef.eob_bin_256[ci][0],
698            5 => &mut coef.eob_bin_512[ci],
699            _ => &mut coef.eob_bin_1024[ci],
700        };
701        enc.symbol_adapt(eob_cdf, ns, bin as usize);
702        if bin > 1 {
703            let hi = (eob >> (bin - 2)) & 1;
704            enc.bool_adapt(&mut coef.eob_hi_bit[tctx][ci][bin as usize], hi != 0);
705            enc.bools(eob & ((1 << (bin - 2)) - 1), bin - 2);
706        }
707
708        let hi_ctx = tctx.min(3);
709        let shift = slh as u32 + 2;
710        let mask = (4u32 << slh) - 1;
711        let stride = 4usize << slh;
712        let offsets = &LO_CTX_OFFSETS[0];
713        let token = |level: i32| (level.unsigned_abs()).min(15);
714        let mut grid = vec![0u8; stride * ((4 << slw) + 2) + 64];
715        let mut mag = 0u32;
716        let at = |i: u32| {
717            let rc = scan[i as usize] as u32;
718            (rc as usize, rc >> shift, rc & mask)
719        };
720        if eob != 0 {
721            let ctx0 = 1 + (eob > 2 << tx2dszctx) as usize + (eob > 4 << tx2dszctx) as usize;
722            let (rc, x, y) = at(eob);
723            let tok = token(levels[rc]);
724            enc.symbol_adapt(
725                &mut coef.eob_base_tok[tctx][ci][ctx0],
726                2,
727                tok.min(3) as usize - 1,
728            );
729            let mut level_tok = tok * 0x41;
730            if tok >= 3 {
731                let c = if (x | y) > 1 { 14 } else { 7 };
732                enc.hi_tok_adapt(&mut coef.br_tok[hi_ctx][ci][c], tok);
733                level_tok = tok + (3 << 6);
734            }
735            grid[x as usize * stride + y as usize] = level_tok as u8;
736            for i in (1..eob).rev() {
737                let (rc, x, mut y) = at(i);
738                let lo = x as usize * stride + y as usize;
739                let ctx = get_lo_ctx(
740                    &grid,
741                    lo,
742                    TX_CLASS_2D,
743                    &mut mag,
744                    Some(offsets),
745                    x,
746                    y,
747                    stride,
748                ) as usize;
749                y |= x;
750                let tok = token(levels[rc]);
751                enc.symbol_adapt(&mut coef.base_tok[tctx][ci][ctx], 3, tok.min(3) as usize);
752                if tok >= 3 {
753                    mag &= 63;
754                    let c = (if y > 1 { 14 } else { 7 })
755                        + if mag > 12 {
756                            6
757                        } else {
758                            ((mag + 1) >> 1) as usize
759                        };
760                    enc.hi_tok_adapt(&mut coef.br_tok[hi_ctx][ci][c], tok);
761                    grid[lo] = (tok + (3 << 6)) as u8;
762                } else {
763                    grid[lo] = (tok * 0x41) as u8;
764                }
765            }
766            let tok = token(levels[0]);
767            enc.symbol_adapt(&mut coef.base_tok[tctx][ci][0], 3, tok.min(3) as usize);
768            if tok >= 3 {
769                let m = (grid[1] as u32 + grid[stride] as u32 + grid[stride + 1] as u32) & 63;
770                let c = if m > 12 { 6 } else { ((m + 1) >> 1) as usize };
771                enc.hi_tok_adapt(&mut coef.br_tok[hi_ctx][ci][c], tok);
772            }
773        } else {
774            let tok = token(levels[0]);
775            enc.symbol_adapt(
776                &mut coef.eob_base_tok[tctx][ci][0],
777                2,
778                tok.min(3) as usize - 1,
779            );
780            if tok >= 3 {
781                enc.hi_tok_adapt(&mut coef.br_tok[hi_ctx][ci][0], tok);
782            }
783        }
784
785        // Signs and what did not fit, DC first, then the rest in scan order.
786        let mut cul = 0u32;
787        let mut sign_level = 1u32 << 6;
788        let dc = levels[0];
789        if dc != 0 {
790            let dsc = get_dc_sign_ctx(&t_dim, &ab, &lb);
791            let negative = dc < 0;
792            enc.bool_adapt(&mut coef.dc_sign[ci][dsc], negative);
793            sign_level = if negative { 0 } else { 2 << 6 };
794            let m = dc.unsigned_abs();
795            if m >= 15 {
796                enc.golomb(m - 15);
797            }
798            cul = m;
799        }
800        for i in 1..=eob {
801            let level = levels[scan[i as usize] as usize];
802            if level != 0 {
803                enc.bool_equi(level < 0);
804                let m = level.unsigned_abs();
805                if m >= 15 {
806                    enc.golomb(m - 15);
807                }
808                cul = cul.saturating_add(m);
809            }
810        }
811        let ctx = (cul.min(63) | sign_level) as u8;
812        f.above_coef[plane][ax..ax + w].fill(ctx);
813        f.left_coef[plane][ly..ly + h].fill(ctx);
814    }
815}
816
817/// Where a block's 4×4 transform `(tx, ty)` starts in `plane`'s samples.
818fn tile_origin(plane: usize, bx: usize, by: usize, tx: usize, ty: usize) -> (usize, usize) {
819    let shift_c = (plane != 0) as usize;
820    (
821        ((bx * 4) >> shift_c) + tx * 4,
822        ((by * 4) >> shift_c) + ty * 4,
823    )
824}
825
826/// A 4×4 intra prediction at `(x0, y0)` from the samples `at(x, y)` above and
827/// to the left, as the decoder makes it (`decode::av1::ipred`): DC averages
828/// the edges there are (128 with none); Paeth picks, per sample, whichever of
829/// left, top and top-left is closest to `left + top - top_left`, becoming a
830/// vertical, horizontal or flat prediction where edges are missing.
831fn predict4(at: impl Fn(usize, usize) -> i32, x0: usize, y0: usize, mode: usize) -> [i32; 16] {
832    let (have_top, have_left) = (y0 > 0, x0 > 0);
833    let top = |x: usize| at(x0 + x, y0 - 1);
834    let left = |y: usize| at(x0 - 1, y0 + y);
835    let mut p = [0i32; 16];
836    match (mode, have_left, have_top) {
837        (PAETH_PRED, true, true) => {
838            let tl = at(x0 - 1, y0 - 1);
839            for y in 0..4 {
840                for x in 0..4 {
841                    let (l, t) = (left(y), top(x));
842                    let base = l + t - tl;
843                    let (ld, td, tld) = ((l - base).abs(), (t - base).abs(), (tl - base).abs());
844                    p[y * 4 + x] = if ld <= td && ld <= tld {
845                        l
846                    } else if td <= tld {
847                        t
848                    } else {
849                        tl
850                    };
851                }
852            }
853        }
854        (PAETH_PRED, false, true) => {
855            for (i, v) in p.iter_mut().enumerate() {
856                *v = top(i % 4);
857            }
858        }
859        (PAETH_PRED, true, false) => {
860            for (i, v) in p.iter_mut().enumerate() {
861                *v = left(i / 4);
862            }
863        }
864        _ => {
865            let mut sum = 0;
866            if have_top {
867                sum += (0..4).map(top).sum::<i32>();
868            }
869            if have_left {
870                sum += (0..4).map(left).sum::<i32>();
871            }
872            let count = 4 * (have_top as i32 + have_left as i32);
873            p = [if count == 0 {
874                128
875            } else {
876                (sum + count / 2) / count
877            }; 16];
878        }
879    }
880    p
881}
882
883/// libaom's `av1_fwht4x4_c` without its final `× UNIT_QUANT_FACTOR`: the
884/// lossless levels. Row-major in and out (`[row * 4 + col]`), rows being the
885/// vertical frequency of the output.
886fn fwht4x4(input: &[i32; 16]) -> [i32; 16] {
887    let mut tmp = [0i32; 16];
888    for i in 0..4 {
889        let (mut a1, mut b1, mut c1, mut d1) =
890            (input[i], input[4 + i], input[8 + i], input[12 + i]);
891        a1 += b1;
892        d1 -= c1;
893        let e1 = (a1 - d1) >> 1;
894        b1 = e1 - b1;
895        c1 = e1 - c1;
896        a1 -= c1;
897        d1 += b1;
898        tmp[i] = a1;
899        tmp[4 + i] = c1;
900        tmp[8 + i] = d1;
901        tmp[12 + i] = b1;
902    }
903    let mut out = [0i32; 16];
904    for i in 0..4 {
905        let (mut a1, mut b1, mut c1, mut d1) =
906            (tmp[4 * i], tmp[4 * i + 1], tmp[4 * i + 2], tmp[4 * i + 3]);
907        a1 += b1;
908        d1 -= c1;
909        let e1 = (a1 - d1) >> 1;
910        b1 = e1 - b1;
911        c1 = e1 - c1;
912        a1 -= c1;
913        d1 += b1;
914        out[4 * i] = a1;
915        out[4 * i + 1] = c1;
916        out[4 * i + 2] = d1;
917        out[4 * i + 3] = b1;
918    }
919    out
920}