Skip to main content

threers_codec/hevc/
compress.rs

1//! Compressed intra HEVC (transform-coded, not `I_PCM`).
2//!
3//! Stage 1 (this file, verified): each 16×16 CTB is one intra `PART_2Nx2N` CU
4//! with luma mode chosen by SAD and DM chroma; all `cbf = 0`, so the
5//! reconstruction is the intra prediction itself (lossy, but *real* compression —
6//! far smaller than raw, and decodable by any HEVC decoder). This exercises the
7//! whole coding path — CU/transform-tree syntax, MPM mode coding, reference-
8//! sample construction, and the reconstruction loop — with only a handful of
9//! CABAC contexts. Stage 2 adds residual coefficient coding for quality.
10//!
11//! Verified by decoding with ffmpeg and comparing to the reconstruction this
12//! encoder returns (a conformant decoder must reproduce it bit-for-bit).
13
14use crate::bitstream::{emulation_prevention, BitWriter};
15use crate::captions::CaptionTrack;
16use crate::hevc::cabac::{CabacEncoder, CtxModel};
17use crate::hevc::deblock::{deblock, EdgeMap};
18use crate::hevc::encoder::pad_plane;
19use crate::hevc::hvcc::{build_hvcc, HvccArray, HvccProfile};
20use crate::hevc::nal::{nal_unit_base, push_annexb, NalUnitType};
21use crate::hevc::params::{
22    write_pps_cu_qp_delta, write_pps_cu_qp_delta_no_deblock, write_pps_tiled, write_sps, write_vps,
23    HevcConfig,
24};
25use crate::hevc::residual::ResidualCtx;
26use crate::hevc::transform::{forward_into, inverse_into, TransformKind, MAX_N};
27use crate::hevc::{intra, quant, residual, Yuv420Frame};
28use crate::mp4::{mux_hevc, mux_hevc_with_captions, Mp4Params};
29use crate::rate::{Quality, RateControl, Reach, PROBE_QP};
30
31/// A compressed intra HEVC encoder. Transform-codes intra frames to a decodable
32/// Annex-B stream far smaller than raw.
33///
34/// Two modes:
35/// - **prediction-only** (default, `residual(false)`): every `cbf = 0`, so the
36///   reconstruction is the intra prediction (DC/planar/angular with the
37///   boundary-smoothing filters). Lossy, tiny, and **conformant** — ffmpeg
38///   decodes it bit-for-bit (see `tests/hevc_compress.rs`).
39/// - **residual** (`residual(true)`, the default): also codes quantized transform
40///   coefficients ([`crate::hevc::residual`]), which is what makes the
41///   output actually resemble the input. Externally conformant — ffmpeg decodes
42///   it bit-for-bit to the returned reconstruction, on detailed content and at
43///   every QP (`tests/hevc_residual_conformance.rs`).
44///
45/// Prediction-only is kept because it is a useful bisection tool: it exercises
46/// the CU/mode/reference-sample path with no transform or coefficient coding, so
47/// when a stream misdecodes, whether it also misdecodes here says which half to
48/// look in.
49pub struct CompressedEncoder {
50    cfg: HevcConfig,
51    headers_emitted: bool,
52    residual: bool,
53    aq_strength: f32,
54    deblock: bool,
55}
56
57impl CompressedEncoder {
58    /// New encoder for `width × height` at quantization `qp`.
59    pub fn new(width: u32, height: u32, qp: i32) -> Self {
60        let mut cfg = HevcConfig::new(width, height)
61            .with_pcm(false)
62            .with_level(180)
63            // 64x64 coding tree blocks, a quadtree down to 8x8, transforms up
64            // to 32x32. Every level is a rate-distortion choice, so a flat sky
65            // pays one coding unit per 4096 samples while detail still gets an
66            // 8x8 unit with its own prediction mode. The transform tree splits
67            // again beneath that, down to 4x4 — where luma switches to DST-VII.
68            .with_coding_tree(6, 3, 5)
69            .with_transform_depth(3)
70            // Large pictures get tiled so a single frame can use every core.
71            // It engages at 4K and above, where it costs under a quarter of a
72            // percent; below that the grid is 1x1 and nothing changes.
73            .with_auto_tiles();
74        cfg.qp = qp;
75        Self {
76            cfg,
77            headers_emitted: false,
78            residual: true,
79            aq_strength: 0.0,
80            deblock: true,
81        }
82    }
83
84    /// Turn the in-loop deblocking filter on or off. On by default.
85    pub fn deblock(mut self, on: bool) -> Self {
86        self.deblock = on;
87        self
88    }
89
90    /// Set the adaptive-quantization strength, in QP steps per octave of
91    /// coding-tree-block variance. Off by default — measured on photographic
92    /// content it costs perceptual quality at matched size, the same as on the
93    /// H.264 side (see `docs/codec-benchmark.md`). Negative values invert the
94    /// assignment, which is the control that measurement needs.
95    pub fn aq(mut self, strength: f32) -> Self {
96        self.aq_strength = strength;
97        self
98    }
99
100    /// Enable transform-coefficient residual coding. On by default; pass `false`
101    /// for the prediction-only path (see the type docs).
102    pub fn residual(mut self, on: bool) -> Self {
103        self.residual = on;
104        self
105    }
106
107    /// The active configuration.
108    pub fn config(&self) -> &HevcConfig {
109        &self.cfg
110    }
111
112    /// Encode one 4:2:0 frame → Annex-B access unit, plus the reconstruction a
113    /// conformant decoder reproduces. The first call prepends VPS/SPS/PPS.
114    pub fn encode_frame(&mut self, frame: &Yuv420Frame) -> (Vec<u8>, Reconstruction) {
115        assert_eq!(
116            (frame.width, frame.height),
117            (self.cfg.width, self.cfg.height),
118            "frame size"
119        );
120        let (cw, ch) = (self.cfg.coded_width, self.cfg.coded_height);
121        let y = pad_plane(&frame.y, frame.width, frame.height, cw, ch);
122        let u = pad_plane(&frame.u, frame.width / 2, frame.height / 2, cw / 2, ch / 2);
123        let v = pad_plane(&frame.v, frame.width / 2, frame.height / 2, cw / 2, ch / 2);
124
125        let (slice, recon) = compressed_slice_rbsp(
126            &self.cfg,
127            &y,
128            &u,
129            &v,
130            self.residual,
131            self.aq_strength,
132            self.deblock,
133        );
134        let mut au = Vec::new();
135        if !self.headers_emitted {
136            push_annexb(&mut au, &nal_unit_base(NalUnitType::Vps, &write_vps(false)));
137            push_annexb(
138                &mut au,
139                &nal_unit_base(NalUnitType::Sps, &write_sps(&self.cfg)),
140            );
141            push_annexb(
142                &mut au,
143                &nal_unit_base(NalUnitType::Pps, &self.pps_payload()),
144            );
145            self.headers_emitted = true;
146        }
147        push_annexb(&mut au, &nal_unit_base(NalUnitType::IdrNLp, &slice));
148        (au, recon)
149    }
150
151    /// One frame's slice NAL, in Annex-B form, without parameter sets.
152    ///
153    /// Takes `&self`. That is the whole point: an all-intra stream carries
154    /// nothing between frames — `compressed_slice_rbsp` reads the config and the
155    /// pixels and nothing else — so frames can be encoded on separate threads
156    /// and the result is byte-identical to encoding them in order.
157    pub fn encode_slice_au(&self, frame: &Yuv420Frame) -> Vec<u8> {
158        self.encode_slice_au_at(frame, self.cfg.qp)
159    }
160
161    /// [`encode_slice_au`](Self::encode_slice_au) at a quantizer chosen per
162    /// frame, which is what rate control needs.
163    ///
164    /// Only the slice header moves: `init_qp_minus26` stays zero in the PPS and
165    /// the frame's quantizer rides in `slice_qp_delta`, so the parameter sets
166    /// are the same ones for every frame however the rate controller steers.
167    pub fn encode_slice_au_at(&self, frame: &Yuv420Frame, qp: i32) -> Vec<u8> {
168        let mut cfg = self.cfg;
169        cfg.qp = qp.clamp(0, 51);
170        self.encode_with(&cfg, frame)
171    }
172
173    fn encode_with(&self, cfg: &HevcConfig, frame: &Yuv420Frame) -> Vec<u8> {
174        let (cw, ch) = (cfg.coded_width, cfg.coded_height);
175        let y = pad_plane(&frame.y, frame.width, frame.height, cw, ch);
176        let u = pad_plane(&frame.u, frame.width / 2, frame.height / 2, cw / 2, ch / 2);
177        let v = pad_plane(&frame.v, frame.width / 2, frame.height / 2, cw / 2, ch / 2);
178        let (slice, _recon) = compressed_slice_rbsp(
179            cfg,
180            &y,
181            &u,
182            &v,
183            self.residual,
184            self.aq_strength,
185            self.deblock,
186        );
187        let mut au = Vec::new();
188        push_annexb(&mut au, &nal_unit_base(NalUnitType::IdrNLp, &slice));
189        au
190    }
191
192    fn pps_payload(&self) -> Vec<u8> {
193        if self.cfg.tiles() > 1 {
194            write_pps_tiled(self.cfg.tile_grid, self.deblock)
195        } else if self.deblock {
196            write_pps_cu_qp_delta()
197        } else {
198            write_pps_cu_qp_delta_no_deblock()
199        }
200    }
201
202    /// Split the picture into `cols` x `rows` tiles, which can then be encoded
203    /// concurrently. See [`HevcConfig::tile_grid`] for what it costs.
204    pub fn tiles(mut self, cols: u32, rows: u32) -> Self {
205        self.cfg = self.cfg.with_tiles(cols, rows);
206        self
207    }
208
209    /// The parameter sets, as they go into `hvcC`.
210    pub fn parameter_sets(&self) -> (Vec<u8>, Vec<u8>, Vec<u8>) {
211        (
212            nal_unit_base(NalUnitType::Vps, &write_vps(false)),
213            nal_unit_base(NalUnitType::Sps, &write_sps(&self.cfg)),
214            nal_unit_base(NalUnitType::Pps, &self.pps_payload()),
215        )
216    }
217}
218
219/// Encode `frames` as a compressed intra HEVC `.mp4` (`hvc1`) at quantization
220/// `qp`, entirely in-process — no ffmpeg, and it builds for `wasm32`.
221///
222/// This is the compressed counterpart to [`crate::h264::encode_mp4`],
223/// which codes `I_PCM` and so writes raw samples. On a 17-frame 1280x1440 render
224/// this produces about 0.16 MB at `qp = 27` against 47 MB for the `I_PCM` path,
225/// at VMAF 94.9 (`docs/codec-benchmark.md`).
226///
227/// `qp` is the H.265 quantization parameter: lower is better and bigger, the
228/// usable range is roughly 18-40, and 26 is a reasonable default. Every frame is
229/// an IDR, so the result is all-intra — fine for short clips and the only option
230/// where nothing else can run, but several times larger than an encoder with
231/// inter prediction would produce.
232pub fn encode_mp4(width: u32, height: u32, fps: u32, qp: i32, frames: &[Yuv420Frame]) -> Vec<u8> {
233    encode_mp4_with_captions(width, height, fps, qp, frames, None)
234}
235
236/// [`encode_mp4`] with an optional soft-subtitle track.
237pub fn encode_mp4_with_captions(
238    width: u32,
239    height: u32,
240    fps: u32,
241    qp: i32,
242    frames: &[Yuv420Frame],
243    captions: Option<&CaptionTrack>,
244) -> Vec<u8> {
245    encode_mp4_from_iter(width, height, fps, qp, captions, frames.iter().cloned())
246}
247
248/// [`encode_mp4`] over an iterator of frames, so the caller can generate them
249/// lazily and never hold more than one.
250pub fn encode_mp4_from_iter<I>(
251    width: u32,
252    height: u32,
253    fps: u32,
254    qp: i32,
255    captions: Option<&CaptionTrack>,
256    frames: I,
257) -> Vec<u8>
258where
259    I: IntoIterator<Item = Yuv420Frame>,
260{
261    encode_mp4_inner(width, height, fps, qp, captions, &mut frames.into_iter())
262}
263
264/// [`encode_mp4`] pulling one frame at a time instead of taking them all up
265/// front.
266///
267/// At high resolutions the slice-taking form is the wrong shape: a 4:2:0 frame
268/// is `width * height * 1.5` bytes, so ten seconds of 8K at 24fps is about 12 GB
269/// of source frames held live while the encoder walks them. The muxer only needs
270/// the *encoded* samples, which are three orders of magnitude smaller, so
271/// nothing requires the sources to coexist.
272///
273/// `next` is called once per frame index in order.
274///
275/// ```no_run
276/// use threers_codec::hevc::{encode_compressed_mp4_streaming, Yuv420Frame};
277/// # fn render(_i: usize) -> Vec<u8> { vec![0; 1920 * 1080 * 4] }
278/// let bytes = encode_compressed_mp4_streaming(1920, 1080, 30, 26, 300, None, |i| {
279///     Yuv420Frame::from_rgba(1920, 1080, &render(i))
280/// });
281/// ```
282pub fn encode_mp4_streaming<F>(
283    width: u32,
284    height: u32,
285    fps: u32,
286    qp: i32,
287    frame_count: usize,
288    captions: Option<&CaptionTrack>,
289    next: F,
290) -> Vec<u8>
291where
292    F: FnMut(usize) -> Yuv420Frame,
293{
294    encode_mp4_inner(
295        width,
296        height,
297        fps,
298        qp,
299        captions,
300        &mut (0..frame_count).map(next),
301    )
302}
303
304fn encode_mp4_inner(
305    width: u32,
306    height: u32,
307    fps: u32,
308    qp: i32,
309    captions: Option<&CaptionTrack>,
310    frames: &mut dyn Iterator<Item = Yuv420Frame>,
311) -> Vec<u8> {
312    encode_mp4_quality(width, height, fps, Quality::Qp(qp), captions, frames, None)
313}
314
315/// Say what a bitrate target could not do, and why it is the request rather
316/// than the encoder.
317fn report_reach(reach: Reach) {
318    match reach {
319        Reach::TooComplex { times } => eprintln!(
320            "threers: this content will not fit that bitrate — even at the coarsest \
321             quantizer it is about {times:.1}x larger. The file is as small as the \
322             encoder can make it."
323        ),
324        Reach::TooSimple { times } => eprintln!(
325            "threers: this content cannot fill that bitrate — even losslessly quantized \
326             it is about {times:.1}x smaller, so the file is smaller than asked for. \
327             That is the content, not a failure."
328        ),
329    }
330}
331
332/// [`encode_mp4_from_iter`] with a quality target rather than a fixed quantizer.
333#[allow(clippy::too_many_arguments)]
334pub fn encode_mp4_quality(
335    width: u32,
336    height: u32,
337    fps: u32,
338    quality: Quality,
339    captions: Option<&CaptionTrack>,
340    frames: &mut dyn Iterator<Item = Yuv420Frame>,
341    total: Option<u32>,
342) -> Vec<u8> {
343    let enc = CompressedEncoder::new(width, height, PROBE_QP);
344    let level_idc = enc.config().level_idc;
345
346    // Parameter sets are hoisted into `hvcC`; only slice NALs become samples.
347    let (vps_nal, sps_nal, pps_nal) = enc.parameter_sets();
348    let (vps, sps, pps) = (vec![vps_nal], vec![sps_nal], vec![pps_nal]);
349
350    // Frames go out in batches so they can be encoded concurrently. Nothing
351    // carries between them, so the batching is invisible in the output — it
352    // only decides how many cores are busy and how much is held at once.
353    let mut batch = crate::frames_in_flight(width, height);
354    let mut samples: Vec<Vec<u8>> = Vec::new();
355    let mut rc = match quality {
356        Quality::Qp(_) => None,
357        Quality::Bitrate(bps) => Some(RateControl::new(bps, fps.max(1), total)),
358    };
359    if let Some(r) = rc.as_ref() {
360        batch = r.group_size(crate::frames_by_memory(width, height));
361    }
362    let base_qp = match quality {
363        Quality::Qp(q) => q,
364        Quality::Bitrate(_) => PROBE_QP,
365    };
366
367    // One frame at the probe quantizer tells the controller what this content
368    // costs, which is worth more than any prior: content varies by orders of
369    // magnitude and quantizers do not.
370    let mut pending: Vec<Yuv420Frame> = Vec::with_capacity(batch);
371    // `if let (Some(r), Some(f)) = (rc.as_mut(), frames.next())` would pull a
372    // frame whether or not there is a controller to feed it to — the tuple is
373    // built before the pattern is tried — and a fixed-quantizer encode would
374    // silently lose its first frame.
375    if let Some(r) = rc.as_mut()
376        && let Some(first) = frames.next()
377    {
378        let probe = enc.encode_slice_au_at(&first, PROBE_QP);
379        r.seed(PROBE_QP, probe.len());
380        // If the answer looks far from the probe, measure there too: one
381        // extra frame buys a local slope instead of a chord across the
382        // curve's bend.
383        if let Some(q2) = r.probe_again() {
384            let again = enc.encode_slice_au_at(&first, q2);
385            r.seed_pair(q2, again.len());
386        }
387        pending.push(first);
388    }
389
390    loop {
391        while pending.len() < batch {
392            match frames.next() {
393                Some(f) => pending.push(f),
394                None => break,
395            }
396        }
397        if pending.is_empty() {
398            break;
399        }
400        let qp = rc.as_ref().map_or(base_qp, |r| r.next_qp());
401        let aus = crate::map_frames(&pending, |f| enc.encode_slice_au_at(f, qp));
402        pending.clear();
403        for au in aus {
404            if let Some(r) = rc.as_mut() {
405                r.observe(qp, au.len());
406            }
407            let mut sample = Vec::new();
408            for nal in split_annexb(&au) {
409                sample.extend_from_slice(&(nal.len() as u32).to_be_bytes());
410                sample.extend_from_slice(&nal);
411            }
412            samples.push(sample);
413        }
414    }
415    if let Some(reach) = rc.as_ref().and_then(|r| r.outcome()) {
416        report_reach(reach);
417    }
418
419    let hvcc = build_hvcc(
420        &HvccProfile::main_420(level_idc),
421        &[
422            HvccArray {
423                nal_type: 32,
424                complete: true,
425                nals: &vps,
426            },
427            HvccArray {
428                nal_type: 33,
429                complete: true,
430                nals: &sps,
431            },
432            HvccArray {
433                nal_type: 34,
434                complete: true,
435                nals: &pps,
436            },
437        ],
438    );
439
440    let timescale = 600u32;
441    let params = Mp4Params {
442        width,
443        height,
444        timescale,
445        frame_duration: timescale / fps.max(1),
446        hvcc_payload: &hvcc,
447        almo_payload: None,
448        samples: &samples,
449    };
450    match captions {
451        Some(track) => mux_hevc_with_captions(&params, track),
452        None => mux_hevc(&params),
453    }
454}
455
456/// Split an Annex-B byte stream into NAL units. Start-code scanning is not
457/// codec-specific, so this matches the H.264 helper of the same name.
458fn split_annexb(stream: &[u8]) -> Vec<Vec<u8>> {
459    let mut starts = Vec::new();
460    let mut i = 0;
461    while i + 3 <= stream.len() {
462        if stream[i] == 0 && stream[i + 1] == 0 && stream[i + 2] == 1 {
463            starts.push((i, 3));
464            i += 3;
465        } else if i + 4 <= stream.len()
466            && stream[i] == 0
467            && stream[i + 1] == 0
468            && stream[i + 2] == 0
469            && stream[i + 3] == 1
470        {
471            starts.push((i, 4));
472            i += 4;
473        } else {
474            i += 1;
475        }
476    }
477    let mut nals = Vec::new();
478    for (n, &(off, len)) in starts.iter().enumerate() {
479        let end = starts.get(n + 1).map(|&(o, _)| o).unwrap_or(stream.len());
480        nals.push(stream[off + len..end].to_vec());
481    }
482    nals
483}
484
485/// CABAC contexts for the compressed intra path (I-slice init values, §9.3.2.2).
486///
487/// `Copy`, and deliberately so: every rate-distortion comparison duplicates the
488/// whole set, and at quadtree depths that happens thousands of times a picture.
489#[derive(Clone, Copy)]
490struct Ctx {
491    part_mode: CtxModel,
492    prev_intra: CtxModel,
493    chroma_mode: CtxModel,
494    cbf_luma: [CtxModel; 2],
495    cbf_chroma: [CtxModel; 4],
496    /// `split_transform_flag`, indexed by `5 - log2TrafoSize`.
497    split_tu: [CtxModel; 3],
498    /// `split_cu_flag`, indexed by how many neighbours are deeper.
499    split_cu: [CtxModel; 3],
500    /// `cu_qp_delta_abs` prefix: one context for the first bin, one for the rest.
501    cu_qp_delta: [CtxModel; 2],
502    res: ResidualCtx,
503}
504
505impl Ctx {
506    fn new(qp: i32) -> Self {
507        Self {
508            part_mode: CtxModel::init(184, qp),
509            prev_intra: CtxModel::init(184, qp),
510            chroma_mode: CtxModel::init(63, qp),
511            cbf_luma: [CtxModel::init(111, qp), CtxModel::init(141, qp)],
512            cbf_chroma: [
513                CtxModel::init(94, qp),
514                CtxModel::init(138, qp),
515                CtxModel::init(182, qp),
516                CtxModel::init(154, qp),
517            ],
518            split_tu: [
519                CtxModel::init(153, qp),
520                CtxModel::init(138, qp),
521                CtxModel::init(138, qp),
522            ],
523            split_cu: [
524                CtxModel::init(139, qp),
525                CtxModel::init(141, qp),
526                CtxModel::init(157, qp),
527            ],
528            cu_qp_delta: [CtxModel::init(154, qp), CtxModel::init(154, qp)],
529            res: ResidualCtx::new(qp),
530        }
531    }
532}
533
534/// Chroma QP from luma QP (4:2:0, offset 0) — the §8.6.1 mapping. Identity below 30.
535fn chroma_qp(qp_luma: i32) -> i32 {
536    let qpi = qp_luma.clamp(0, 51);
537    if qpi < 30 {
538        qpi
539    } else {
540        const T: [i32; 14] = [29, 30, 31, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37];
541        if qpi <= 43 {
542            T[(qpi - 30) as usize]
543        } else {
544            qpi - 6
545        }
546    }
547}
548
549/// A reconstructed planar picture the decoder must reproduce.
550pub struct Reconstruction {
551    /// Luma, `coded_width * coded_height`.
552    pub y: Vec<u8>,
553    /// Cb, at half the coded size each way.
554    pub u: Vec<u8>,
555    /// Cr, laid out like `u`.
556    pub v: Vec<u8>,
557    /// Width padded up to whole coding blocks.
558    pub coded_width: u32,
559    /// Height padded up to whole coding blocks.
560    pub coded_height: u32,
561}
562
563/// Encode the picture as one compressed IDR I-slice; returns the slice RBSP plus
564/// the reconstruction (for verification / as neighbor source across frames).
565pub fn compressed_slice_rbsp(
566    cfg: &HevcConfig,
567    y: &[u8],
568    u: &[u8],
569    v: &[u8],
570    residual: bool,
571    aq_strength: f32,
572    deblocking: bool,
573) -> (Vec<u8>, Reconstruction) {
574    if cfg.tiles() > 1 {
575        return tiled_slice_rbsp(cfg, y, u, v, residual, aq_strength, deblocking);
576    }
577    let mut rbsp = slice_header(cfg, &[]);
578    let mut coded = encode_ctbs(cfg, y, u, v, residual, aq_strength, true);
579    if deblocking {
580        coded.deblock(cfg);
581    }
582    rbsp.extend_from_slice(&coded.data);
583    (rbsp, coded.recon)
584}
585
586/// The tile grid in coding tree blocks, with uniform spacing (§6.5.1).
587///
588/// Column `i` spans `((i+1)·nx)/cols − (i·nx)/cols` CTBs, which distributes the
589/// remainder over the leading columns rather than dumping it on the last one.
590fn tile_spans(n: u32, parts: u32) -> Vec<(u32, u32)> {
591    (0..parts)
592        .map(|i| {
593            let a = (i * n) / parts;
594            let b = ((i + 1) * n) / parts;
595            (a, b - a)
596        })
597        .collect()
598}
599
600/// Encode the picture as one slice of independently-coded tiles.
601///
602/// Tiles break intra prediction *and* the entropy coder at their edges, which
603/// is exactly what makes them parallel — and it also means a tile is nothing
604/// more than a smaller picture. So each one is encoded by the same
605/// `encode_ctbs` that codes a whole frame, on its own plane region, and the
606/// substreams are concatenated. Nothing in the coding path needs to know tiles
607/// exist.
608///
609/// Two things are picture-level rather than per-tile: the reconstruction is
610/// stitched back together, and the deblocking filter runs over the result, so
611/// tile edges get smoothed like any other block edge. That is what
612/// `loop_filter_across_tiles_enabled_flag` promises the decoder, and it costs
613/// nothing here because the filter was already a separate pass.
614fn tiled_slice_rbsp(
615    cfg: &HevcConfig,
616    y: &[u8],
617    u: &[u8],
618    v: &[u8],
619    residual: bool,
620    aq_strength: f32,
621    deblocking: bool,
622) -> (Vec<u8>, Reconstruction) {
623    let (cw, ch) = (cfg.coded_width, cfg.coded_height);
624    let (cwc, chc) = (cw / 2, ch / 2);
625    let (nx, ny) = cfg.ctbs();
626    let ctb = 1u32 << cfg.ctb_log2;
627    let cols = tile_spans(nx, cfg.tile_grid.0);
628    let rows = tile_spans(ny, cfg.tile_grid.1);
629
630    // Cut the planes into tiles. Tile boundaries fall on CTB boundaries, so
631    // every tile but those at the right and bottom edges is a whole number of
632    // them; the edge tiles are clipped, which the encoder already handles
633    // because a picture is rarely a whole number of CTBs either.
634    let mut jobs = Vec::with_capacity(cols.len() * rows.len());
635    for (ry0, rh) in &rows {
636        for (cx0, cwd) in &cols {
637            let x0 = cx0 * ctb;
638            let y0 = ry0 * ctb;
639            let tw = (cwd * ctb).min(cw - x0);
640            let th = (rh * ctb).min(ch - y0);
641            let mut tcfg = *cfg;
642            tcfg.width = tw;
643            tcfg.height = th;
644            tcfg.coded_width = tw;
645            tcfg.coded_height = th;
646            tcfg.tile_grid = (1, 1);
647            jobs.push((
648                tcfg,
649                (x0, y0, tw, th),
650                crop(y, cw, x0, y0, tw, th),
651                crop(u, cwc, x0 / 2, y0 / 2, tw / 2, th / 2),
652                crop(v, cwc, x0 / 2, y0 / 2, tw / 2, th / 2),
653            ));
654        }
655    }
656
657    let last = jobs.len() - 1;
658    let coded = crate::map_indexed(&jobs, |i, (tcfg, _, ty, tu, tv)| {
659        encode_ctbs(tcfg, ty, tu, tv, residual, aq_strength, i == last)
660    });
661
662    // Stitch the reconstruction back together, then filter the whole thing.
663    let mut recon = Reconstruction {
664        y: vec![0u8; (cw * ch) as usize],
665        u: vec![128u8; (cwc * chc) as usize],
666        v: vec![128u8; (cwc * chc) as usize],
667        coded_width: cw,
668        coded_height: ch,
669    };
670    let mut edges = EdgeMap::new(cw, ch);
671    let mut qp = vec![cfg.qp as i8; ((cw >> cfg.min_cb_log2) * (ch >> cfg.min_cb_log2)) as usize];
672    let gl = cfg.min_cb_log2;
673    let gw = (cw >> gl) as usize;
674    for (job, c) in jobs.iter().zip(&coded) {
675        let (x0, y0, tw, th) = job.1;
676        paste(&mut recon.y, cw, &c.recon.y, tw, x0, y0, tw, th);
677        paste(
678            &mut recon.u,
679            cwc,
680            &c.recon.u,
681            tw / 2,
682            x0 / 2,
683            y0 / 2,
684            tw / 2,
685            th / 2,
686        );
687        paste(
688            &mut recon.v,
689            cwc,
690            &c.recon.v,
691            tw / 2,
692            x0 / 2,
693            y0 / 2,
694            tw / 2,
695            th / 2,
696        );
697        for ty in (0..th).step_by(1 << gl) {
698            for tx in (0..tw).step_by(1 << gl) {
699                let src = (ty >> gl) as usize * (tw >> gl) as usize + (tx >> gl) as usize;
700                let dst = ((y0 + ty) >> gl) as usize * gw + ((x0 + tx) >> gl) as usize;
701                qp[dst] = c.qp[src];
702            }
703        }
704        edges.paste(&c.edges, tw, th, x0, y0);
705    }
706
707    if deblocking {
708        deblock(
709            &mut recon.y,
710            &mut recon.u,
711            &mut recon.v,
712            cw,
713            ch,
714            &edges,
715            |x, y| i32::from(qp[(y >> gl) as usize * gw + (x >> gl) as usize]),
716            chroma_qp,
717        );
718    }
719
720    // The entry points are byte lengths of every substream but the last, counted
721    // *after* emulation prevention — the specification counts those bytes. The
722    // header always ends with the alignment one-bit, so its last byte is never
723    // zero and the escaping of the data cannot depend on it.
724    let mut entry = Vec::new();
725    for c in &coded[..coded.len() - 1] {
726        entry.push(emulation_prevention(&c.data).len());
727    }
728    let mut rbsp = slice_header(cfg, &entry);
729    for c in &coded {
730        rbsp.extend_from_slice(&c.data);
731    }
732    (rbsp, recon)
733}
734
735/// Copy a `w x h` rectangle out of a plane.
736fn crop(plane: &[u8], stride: u32, x: u32, y: u32, w: u32, h: u32) -> Vec<u8> {
737    let mut out = Vec::with_capacity((w * h) as usize);
738    for r in 0..h {
739        let o = ((y + r) * stride + x) as usize;
740        out.extend_from_slice(&plane[o..o + w as usize]);
741    }
742    out
743}
744
745/// Paste a `w x h` rectangle back into a plane.
746#[allow(clippy::too_many_arguments)]
747fn paste(dst: &mut [u8], stride: u32, src: &[u8], src_stride: u32, x: u32, y: u32, w: u32, h: u32) {
748    for r in 0..h {
749        let d = ((y + r) * stride + x) as usize;
750        let s = (r * src_stride) as usize;
751        dst[d..d + w as usize].copy_from_slice(&src[s..s + w as usize]);
752    }
753}
754
755/// One coded picture, or one tile of one: the entropy-coded bytes, the
756/// reconstruction, and the two things the deblocking filter needs that the
757/// reconstruction alone does not carry.
758struct Coded {
759    data: Vec<u8>,
760    recon: Reconstruction,
761    edges: EdgeMap,
762    /// `QpY` per minimum coding block.
763    qp: Vec<i8>,
764}
765
766impl Coded {
767    fn deblock(&mut self, cfg: &HevcConfig) {
768        let (cw, ch) = (cfg.coded_width, cfg.coded_height);
769        let gl = cfg.min_cb_log2;
770        let gw = (cw >> gl) as usize;
771        let qp = &self.qp;
772        deblock(
773            &mut self.recon.y,
774            &mut self.recon.u,
775            &mut self.recon.v,
776            cw,
777            ch,
778            &self.edges,
779            |x, y| i32::from(qp[(y >> gl) as usize * gw + (x >> gl) as usize]),
780            chroma_qp,
781        );
782    }
783}
784
785/// `slice_segment_header()` for the picture's single slice.
786///
787/// `entry_points` are the byte lengths of every substream but the last, which a
788/// decoder needs to find the tiles. Empty when the picture is not tiled.
789fn slice_header(cfg: &HevcConfig, entry_points: &[usize]) -> Vec<u8> {
790    let mut h = BitWriter::new();
791    h.flag(true); // first_slice_segment_in_pic_flag
792    h.flag(false); // no_output_of_prior_pics_flag
793    h.write_ue(0); // slice_pic_parameter_set_id
794    h.write_ue(2); // slice_type = I
795    h.write_se(cfg.qp - 26); // slice_qp_delta (init_qp_minus26 = 0)
796    if cfg.tiles() > 1 {
797        h.write_ue(entry_points.len() as u32);
798        if !entry_points.is_empty() {
799            let bits = entry_points
800                .iter()
801                .map(|&o| 32 - (o as u32).leading_zeros())
802                .max()
803                .unwrap_or(1)
804                .max(1);
805            h.write_ue(bits - 1); // offset_len_minus1
806            for &o in entry_points {
807                // The value is the length minus one, so a one-byte subset codes
808                // as zero.
809                h.write_bits((o - 1) as u32, bits);
810            }
811        }
812    }
813    h.write_bit(1); // byte_alignment: alignment_bit_equal_to_one
814    h.finish()
815}
816
817/// Code every coding tree block of a picture (or of one tile, encoded as a
818/// picture of its own) and return the CABAC substream.
819///
820/// `last_subset` distinguishes the end of the slice from the end of a tile: the
821/// former sends `end_of_slice_segment_flag = 1`, the latter sends a zero
822/// followed by `end_of_subset_one_bit`, and both flush and byte-align.
823fn encode_ctbs(
824    cfg: &HevcConfig,
825    y: &[u8],
826    u: &[u8],
827    v: &[u8],
828    residual: bool,
829    aq_strength: f32,
830    last_subset: bool,
831) -> Coded {
832    let cw = cfg.coded_width;
833    let ch = cfg.coded_height;
834    let (cwc, chc) = (cw / 2, ch / 2);
835
836    // Reconstruction buffers (grown as CTBs are coded, read for neighbors).
837    let mut ry = vec![0u8; (cw * ch) as usize];
838    let mut ru = vec![128u8; (cwc * chc) as usize];
839    let mut rv = vec![128u8; (cwc * chc) as usize];
840
841    let lim = TreeLimits {
842        max_depth: cfg.max_transform_hierarchy_depth_intra,
843        max_tb_log2: cfg.max_tb_log2,
844    };
845    // The usual HEVC intra Lagrangian: cost = SSD + lambda * bits.
846    let lambda = 0.57 * 2f64.powf((cfg.qp - 12) as f64 / 3.0);
847    let mut cabac = CabacEncoder::new();
848    let mut ctx = Ctx::new(cfg.qp);
849    let (nx, ny) = cfg.ctbs();
850    let ctb = 1u32 << cfg.ctb_log2;
851    let g = Geo { cw, ch, ctb, nx };
852    let mut grid = Grid::new(cw, ch, cfg.min_cb_log2);
853    // One set of working buffers for the whole picture; see `Scratch`.
854    let mut scratch = Scratch::default();
855    let total = nx * ny;
856    let mut coded = 0u32;
857    let ctb_qp = adaptive_qp(y, cw, ch, ctb, nx, ny, cfg.qp, aq_strength);
858    // `qPY_PREV` (§8.6.1). With the quantization group equal to the CTB, both
859    // spatial predictors fall outside it and collapse to this.
860    let mut qp_prev = cfg.qp;
861    let mut edges = EdgeMap::new(cw, ch);
862
863    for cby in 0..ny {
864        for cbx in 0..nx {
865            let (px, py) = (cbx * ctb, cby * ctb);
866            let qp_ctb = ctb_qp[(cby * nx + cbx) as usize];
867            let qp_l = qp_ctb;
868            let qp_c = chroma_qp(qp_ctb);
869            let delta = qp_ctb - qp_prev;
870
871            // Two passes over the coding tree, for the same reason the transform
872            // tree needs two: the search has to try candidates and roll them
873            // back, and only the winner may reach the bitstream. The search
874            // encodes into a scratch engine so each candidate sees the context
875            // state its predecessors leave; `emit_cu` then replays the decided
876            // tree into the real one from the same starting grid.
877            let saved = grid.save(px, py, cfg.ctb_log2);
878            let cu = {
879                let mut planes = Planes {
880                    y,
881                    u,
882                    v,
883                    ry: &mut ry,
884                    ru: &mut ru,
885                    rv: &mut rv,
886                    cw,
887                    ch,
888                    cwc,
889                    chc,
890                    nx,
891                    ctb,
892                    scratch: &mut scratch,
893                    qp_l,
894                    qp_c,
895                    residual,
896                };
897                let mut scratch = cabac.probe();
898                let mut sctx = ctx;
899                let mut qd = QpDelta::new(qp_prev, delta);
900                search_cu(
901                    &mut planes,
902                    &mut scratch,
903                    &mut sctx,
904                    &mut grid,
905                    g,
906                    px,
907                    py,
908                    cfg.ctb_log2,
909                    0,
910                    lim,
911                    lambda,
912                    &mut qd,
913                )
914                .0
915            };
916            grid.restore(px, py, cfg.ctb_log2, &saved);
917            let mut qd = QpDelta::new(qp_prev, delta);
918            emit_cu(
919                &mut cabac,
920                &mut ctx,
921                &cu,
922                &mut grid,
923                g,
924                px,
925                py,
926                cfg.ctb_log2,
927                0,
928                lim,
929                &mut qd,
930            );
931            // A coding tree block with nothing to code carries no delta, so the
932            // predictor does not move past it.
933            if qd.sent {
934                qp_prev = qp_ctb;
935            }
936            mark_cu_edges(&cu, &mut edges, g, px, py, cfg.ctb_log2);
937
938            coded += 1;
939            if coded == total && !last_subset {
940                // Not the end of the slice, only of this tile.
941                cabac.encode_terminate(0); // end_of_slice_segment_flag
942                cabac.encode_terminate(1); // end_of_subset_one_bit
943            } else {
944                cabac.encode_terminate((coded == total) as u32);
945            }
946        }
947    }
948
949    Coded {
950        data: cabac.finish(),
951        recon: Reconstruction {
952            y: ry,
953            u: ru,
954            v: rv,
955            coded_width: cw,
956            coded_height: ch,
957        },
958        edges,
959        qp: grid.into_qp(),
960    }
961}
962
963/// The transform-tree shape limits taken from the SPS.
964#[derive(Clone, Copy)]
965struct TreeLimits {
966    /// `max_transform_hierarchy_depth_intra`.
967    max_depth: u32,
968    /// `MaxTbLog2SizeY`. A node above this size splits without signalling it.
969    max_tb_log2: u32,
970}
971
972/// One node of the transform tree: either a split with four children, or a leaf
973/// carrying the quantized levels for its luma block and the two chroma blocks
974/// that cover it.
975struct Tu {
976    log2: u32,
977    split: bool,
978    children: Vec<Tu>,
979    cbf_luma: bool,
980    levels_y: Vec<i32>,
981    /// Chroma cbf *at this node's depth*. On a split node it is the OR of the
982    /// children's, which is what makes the parent flag meaningful.
983    cbf_cb: bool,
984    cbf_cr: bool,
985    levels_cb: Vec<i32>,
986    levels_cr: Vec<i32>,
987}
988
989/// The planes a transform tree reads and writes, bundled to keep the recursion's
990/// argument list survivable.
991struct Planes<'a> {
992    y: &'a [u8],
993    u: &'a [u8],
994    v: &'a [u8],
995    ry: &'a mut [u8],
996    ru: &'a mut [u8],
997    rv: &'a mut [u8],
998    cw: u32,
999    ch: u32,
1000    cwc: u32,
1001    chc: u32,
1002    nx: u32,
1003    /// Coding-tree-block edge, which sets the decoding order neighbours are
1004    /// judged available in.
1005    ctb: u32,
1006    /// Reusable working buffers — see [`Scratch`].
1007    scratch: &'a mut Scratch,
1008    /// Luma QP for the coding tree block being coded. With a quantization group
1009    /// the size of a CTB this is constant across everything below it.
1010    qp_l: i32,
1011    qp_c: i32,
1012    residual: bool,
1013}
1014
1015/// Build the transform tree for the node at `(x, y)`, choosing at each level
1016/// whether to split, and reconstructing as it goes.
1017///
1018/// The reconstruction has to happen during the build, in decoding order, because
1019/// intra prediction reads neighbouring *reconstructed* samples. That is also why
1020/// splitting helps beyond transform efficiency: four 8x8 blocks each predict
1021/// from a boundary 8 samples away instead of one 16x16 predicting from the CU
1022/// edge.
1023///
1024/// The decision is Lagrangian — both shapes are built, the reconstruction rolled
1025/// back between them, and the cheaper `SSD + lambda * bits` kept. Splitting pays
1026/// on detail and costs flags and transform efficiency on flat areas, so which
1027/// wins is a property of the block rather than a constant.
1028#[allow(clippy::too_many_arguments)]
1029fn build_tu(
1030    p: &mut Planes,
1031    cabac: &CabacEncoder,
1032    ctx: &Ctx,
1033    x: u32,
1034    y: u32,
1035    log2: u32,
1036    depth: u32,
1037    lim: TreeLimits,
1038    mode: u8,
1039    cmode: u8,
1040    lambda: f64,
1041    qd: &QpDelta,
1042) -> Tu {
1043    // Above the largest transform size there is no choice: the tree splits and
1044    // the flag is not coded (§7.3.8.8).
1045    if log2 > lim.max_tb_log2 {
1046        return build_split(
1047            p, cabac, ctx, x, y, log2, depth, lim, mode, cmode, lambda, qd,
1048        );
1049    }
1050    if !(depth < lim.max_depth && log2 > 2) {
1051        return build_leaf(p, x, y, log2, mode, cmode);
1052    }
1053
1054    let before = save_rect(p, x, y, log2);
1055    let leaf = build_leaf(p, x, y, log2, mode, cmode);
1056    let leaf_cost = node_cost(
1057        p, x, y, log2, &leaf, cabac, ctx, depth, lim, mode, cmode, lambda, qd,
1058    );
1059    let leaf_recon = save_rect(p, x, y, log2);
1060
1061    restore_rect(p, x, y, log2, &before);
1062    let split = build_split(
1063        p, cabac, ctx, x, y, log2, depth, lim, mode, cmode, lambda, qd,
1064    );
1065    let split_cost = node_cost(
1066        p, x, y, log2, &split, cabac, ctx, depth, lim, mode, cmode, lambda, qd,
1067    );
1068
1069    if leaf_cost <= split_cost {
1070        restore_rect(p, x, y, log2, &leaf_recon);
1071        leaf
1072    } else {
1073        split
1074    }
1075}
1076
1077/// A leaf: one luma block, plus the chroma block covering it when this node is
1078/// large enough to own one.
1079fn build_leaf(p: &mut Planes, x: u32, y: u32, log2: u32, mode: u8, cmode: u8) -> Tu {
1080    let n = 1usize << log2;
1081    let (cbf_luma, levels_y) = code_leaf(
1082        p.y, p.ry, p.cw, p.ch, x, y, n, p.ctb, p.nx, mode, p.qp_l, true, p.residual, p.scratch,
1083    );
1084    let mut tu = Tu {
1085        log2,
1086        split: false,
1087        children: Vec::new(),
1088        cbf_luma,
1089        levels_y,
1090        cbf_cb: false,
1091        cbf_cr: false,
1092        levels_cb: Vec::new(),
1093        levels_cr: Vec::new(),
1094    };
1095    if log2 > 2 {
1096        code_node_chroma(p, &mut tu, x, y, log2, cmode);
1097    }
1098    tu
1099}
1100
1101/// Split into four quadrants in z-order.
1102///
1103/// At `log2 == 3` the split is the 4:2:0 special case: 2x2 chroma does not
1104/// exist, so the four 4x4 luma blocks share this node's single 4x4 chroma block,
1105/// which the bitstream carries in the fourth child's transform unit. The chroma
1106/// is therefore coded *after* the luma children, matching decoding order.
1107#[allow(clippy::too_many_arguments)]
1108fn build_split(
1109    p: &mut Planes,
1110    cabac: &CabacEncoder,
1111    ctx: &Ctx,
1112    x: u32,
1113    y: u32,
1114    log2: u32,
1115    depth: u32,
1116    lim: TreeLimits,
1117    mode: u8,
1118    cmode: u8,
1119    lambda: f64,
1120    qd: &QpDelta,
1121) -> Tu {
1122    let half = 1u32 << (log2 - 1);
1123    let mut children = Vec::with_capacity(4);
1124    for (dx, dy) in [(0, 0), (half, 0), (0, half), (half, half)] {
1125        children.push(build_tu(
1126            p,
1127            cabac,
1128            ctx,
1129            x + dx,
1130            y + dy,
1131            log2 - 1,
1132            depth + 1,
1133            lim,
1134            mode,
1135            cmode,
1136            lambda,
1137            qd,
1138        ));
1139    }
1140    let mut tu = Tu {
1141        log2,
1142        split: true,
1143        children,
1144        cbf_luma: false,
1145        levels_y: Vec::new(),
1146        cbf_cb: false,
1147        cbf_cr: false,
1148        levels_cb: Vec::new(),
1149        levels_cr: Vec::new(),
1150    };
1151    if log2 == 3 {
1152        // Children are 4x4 luma and carry no chroma; this node owns it.
1153        code_node_chroma(p, &mut tu, x, y, log2, cmode);
1154    } else {
1155        tu.cbf_cb = tu.children.iter().any(|c| c.cbf_cb);
1156        tu.cbf_cr = tu.children.iter().any(|c| c.cbf_cr);
1157    }
1158    tu
1159}
1160
1161/// Code the chroma block covering the `2^log2` luma square at `(x, y)`.
1162fn code_node_chroma(p: &mut Planes, tu: &mut Tu, x: u32, y: u32, log2: u32, cmode: u8) {
1163    let cn = 1usize << (log2 - 1);
1164    let (cx, cy) = (x / 2, y / 2);
1165    let (cbf_cb, levels_cb) = code_leaf(
1166        p.u,
1167        p.ru,
1168        p.cwc,
1169        p.chc,
1170        cx,
1171        cy,
1172        cn,
1173        p.ctb / 2,
1174        p.nx,
1175        cmode,
1176        p.qp_c,
1177        false,
1178        p.residual,
1179        p.scratch,
1180    );
1181    let (cbf_cr, levels_cr) = code_leaf(
1182        p.v,
1183        p.rv,
1184        p.cwc,
1185        p.chc,
1186        cx,
1187        cy,
1188        cn,
1189        p.ctb / 2,
1190        p.nx,
1191        cmode,
1192        p.qp_c,
1193        false,
1194        p.residual,
1195        p.scratch,
1196    );
1197    tu.cbf_cb = cbf_cb;
1198    tu.cbf_cr = cbf_cr;
1199    tu.levels_cb = levels_cb;
1200    tu.levels_cr = levels_cr;
1201}
1202
1203/// Working buffers for one block, kept alive across calls.
1204///
1205/// `code_leaf` used to allocate nine `Vec`s every time it ran, and it runs once
1206/// per candidate per level of two nested trees — the profile put a quarter of
1207/// the encoder's time in the allocator. Fixed-size stack arrays would trade that
1208/// for zeroing four kilobytes to use sixteen of them on a 4x4 block, so these
1209/// are `Vec`s that keep their capacity instead: one allocation each for the
1210/// whole picture.
1211struct Scratch {
1212    refs: Vec<i32>,
1213    smooth: Vec<i32>,
1214    above: Vec<i32>,
1215    left: Vec<i32>,
1216    pred: Vec<i32>,
1217    orig: Vec<i32>,
1218    resid: Vec<i32>,
1219    coeff: Vec<i32>,
1220    deq: Vec<i32>,
1221    res: Vec<i32>,
1222}
1223
1224impl Default for Scratch {
1225    /// Sized to the largest block once, and sliced from then on. Resizing per
1226    /// call would zero four kilobytes to use sixteen of them on a 4x4 block,
1227    /// which is how the first attempt at this came out *slower*.
1228    fn default() -> Self {
1229        const N: usize = MAX_N * MAX_N;
1230        const R: usize = 4 * MAX_N + 1;
1231        Self {
1232            refs: vec![0; R],
1233            smooth: vec![0; R],
1234            above: vec![0; 2 * MAX_N + 1],
1235            left: vec![0; 2 * MAX_N + 1],
1236            pred: vec![0; N],
1237            orig: vec![0; N],
1238            resid: vec![0; N],
1239            coeff: vec![0; N],
1240            deq: vec![0; N],
1241            res: vec![0; N],
1242        }
1243    }
1244}
1245
1246/// Predict, transform, quantize and reconstruct one `n x n` block of one plane.
1247/// Returns its `cbf` and quantized levels; the reconstruction is written back so
1248/// the next block in decoding order can predict from it.
1249#[allow(clippy::too_many_arguments)]
1250fn code_leaf(
1251    orig: &[u8],
1252    recon: &mut [u8],
1253    w: u32,
1254    h: u32,
1255    x: u32,
1256    y: u32,
1257    n: usize,
1258    ctb: u32,
1259    nx: u32,
1260    mode: u8,
1261    qp: i32,
1262    luma: bool,
1263    residual: bool,
1264    sc: &mut Scratch,
1265) -> (bool, Vec<i32>) {
1266    let (nn, nr) = (n * n, 4 * n + 1);
1267    refs_generic_into(recon, w, h, x, y, n as u32, ctb, nx, &mut sc.refs[..nr]);
1268    let src: &[i32] = if luma && filter_flag(mode, n) {
1269        smooth_refs_into(&sc.refs[..nr], &mut sc.smooth[..nr]);
1270        &sc.smooth[..nr]
1271    } else {
1272        &sc.refs[..nr]
1273    };
1274    split_refs_into(
1275        src,
1276        n,
1277        &mut sc.above[..2 * n + 1],
1278        &mut sc.left[..2 * n + 1],
1279    );
1280    intra::predict_into(
1281        mode,
1282        n,
1283        &sc.above[..2 * n + 1],
1284        &sc.left[..2 * n + 1],
1285        luma,
1286        &mut sc.pred[..nn],
1287    );
1288    gather_into(orig, w, x, y, n as u32, &mut sc.orig[..nn]);
1289    for i in 0..nn {
1290        sc.resid[i] = sc.orig[i] - sc.pred[i];
1291    }
1292    // 4x4 intra luma is the one place HEVC uses DST-VII instead of the DCT
1293    // (§8.6.4.2) — it fits the residual of a block predicted from one edge.
1294    let kind = if luma && n == 4 {
1295        TransformKind::Dst
1296    } else {
1297        TransformKind::Dct
1298    };
1299    forward_into(&sc.resid[..nn], &mut sc.coeff[..nn], n, kind);
1300    let mut levels = vec![0i32; nn];
1301    quant::quant_into(&sc.coeff[..nn], n, qp, true, &mut levels);
1302    let cbf = residual && levels.iter().any(|&c| c != 0);
1303
1304    if cbf {
1305        quant::dequant_into(&levels, n, qp, &mut sc.deq[..nn]);
1306        inverse_into(&sc.deq[..nn], &mut sc.res[..nn], n, kind);
1307        for i in 0..nn {
1308            sc.pred[i] += sc.res[i];
1309        }
1310    }
1311    store(recon, w, x, y, n as u32, &sc.pred[..nn]);
1312    (cbf, levels)
1313}
1314
1315/// Emit `transform_tree` / `transform_unit` (H.265 §7.3.8.8, §7.3.8.10).
1316///
1317/// Order matters and is not the order the tree was built in: a node's chroma
1318/// cbf is signalled before its children, because a child only codes its own when
1319/// the parent's was set.
1320#[allow(clippy::too_many_arguments)]
1321fn emit_tu(
1322    cabac: &mut CabacEncoder,
1323    ctx: &mut Ctx,
1324    tu: &Tu,
1325    depth: u32,
1326    lim: TreeLimits,
1327    mode: u8,
1328    cmode: u8,
1329    parent_cb: bool,
1330    parent_cr: bool,
1331    // Set on the fourth 4x4 child: the chroma of the 8x8 parent it shares, which
1332    // the bitstream carries here (`blkIdx == 3`) rather than at the parent.
1333    blk3_chroma: Option<&Tu>,
1334    qd: &mut QpDelta,
1335) {
1336    if tu.log2 <= lim.max_tb_log2 && depth < lim.max_depth && tu.log2 > 2 {
1337        // ctxInc = 5 - log2TrafoSize.
1338        cabac.encode_bin(&mut ctx.split_tu[(5 - tu.log2) as usize], tu.split as u32);
1339    }
1340    if tu.log2 > 2 {
1341        if depth == 0 || parent_cb {
1342            cabac.encode_bin(&mut ctx.cbf_chroma[depth as usize], tu.cbf_cb as u32);
1343        }
1344        if depth == 0 || parent_cr {
1345            cabac.encode_bin(&mut ctx.cbf_chroma[depth as usize], tu.cbf_cr as u32);
1346        }
1347    }
1348    if tu.split {
1349        for (i, child) in tu.children.iter().enumerate() {
1350            // 4x4 children share the parent's chroma, delivered at blkIdx 3.
1351            let carry = (tu.log2 == 3 && i == 3).then_some(tu);
1352            emit_tu(
1353                cabac,
1354                ctx,
1355                child,
1356                depth + 1,
1357                lim,
1358                mode,
1359                cmode,
1360                tu.cbf_cb,
1361                tu.cbf_cr,
1362                carry,
1363                qd,
1364            );
1365        }
1366        return;
1367    }
1368
1369    // Leaf. An intra CU always signals cbf_luma; ctxInc is 1 at depth 0, else 0.
1370    cabac.encode_bin(
1371        &mut ctx.cbf_luma[usize::from(depth == 0)],
1372        tu.cbf_luma as u32,
1373    );
1374    // `cu_qp_delta` rides in the first transform unit of the group that codes
1375    // anything, ahead of the residual it applies to (§7.3.8.10).
1376    //
1377    // At 4x4 the chroma flags to test are the *parent's*, and for all four
1378    // children — not only the one that carries the shared chroma residual.
1379    // A child with no luma coefficients still opens a transform unit if the
1380    // 8x8 above it has chroma, and that unit is where the delta belongs.
1381    let cbf_chroma = if tu.log2 > 2 {
1382        tu.cbf_cb || tu.cbf_cr
1383    } else {
1384        parent_cb || parent_cr
1385    };
1386    if tu.cbf_luma || cbf_chroma {
1387        qd.emit(cabac, ctx);
1388    }
1389    let n = 1usize << tu.log2;
1390    if tu.cbf_luma {
1391        residual::encode(
1392            cabac,
1393            &mut ctx.res,
1394            &tu.levels_y,
1395            n,
1396            false,
1397            scan_idx(mode, tu.log2, false),
1398        );
1399    }
1400    if tu.log2 > 2 {
1401        let cscan = scan_idx(cmode, tu.log2 - 1, true);
1402        if tu.cbf_cb {
1403            residual::encode(cabac, &mut ctx.res, &tu.levels_cb, n / 2, true, cscan);
1404        }
1405        if tu.cbf_cr {
1406            residual::encode(cabac, &mut ctx.res, &tu.levels_cr, n / 2, true, cscan);
1407        }
1408    } else if let Some(parent) = blk3_chroma {
1409        // The shared 4x4 chroma of the 8x8 above, gated by *its* cbf.
1410        let cscan = scan_idx(cmode, 2, true);
1411        if parent.cbf_cb {
1412            residual::encode(cabac, &mut ctx.res, &parent.levels_cb, 4, true, cscan);
1413        }
1414        if parent.cbf_cr {
1415            residual::encode(cabac, &mut ctx.res, &parent.levels_cr, 4, true, cscan);
1416        }
1417    }
1418}
1419
1420/// Copy the reconstructed samples covered by a node out of all three planes, so
1421/// a candidate tree shape can be tried and rolled back.
1422fn save_rect(p: &Planes, x: u32, y: u32, log2: u32) -> Vec<u8> {
1423    let n = 1u32 << log2;
1424    let cn = n / 2;
1425    let mut out = Vec::with_capacity((n * n * 3 / 2) as usize);
1426    for r in 0..n {
1427        let o = ((y + r) * p.cw + x) as usize;
1428        out.extend_from_slice(&p.ry[o..o + n as usize]);
1429    }
1430    let (cx, cy) = (x / 2, y / 2);
1431    for plane in [&*p.ru, &*p.rv] {
1432        for r in 0..cn {
1433            let o = ((cy + r) * p.cwc + cx) as usize;
1434            out.extend_from_slice(&plane[o..o + cn as usize]);
1435        }
1436    }
1437    out
1438}
1439
1440fn restore_rect(p: &mut Planes, x: u32, y: u32, log2: u32, saved: &[u8]) {
1441    let n = 1u32 << log2;
1442    let cn = n / 2;
1443    let mut k = 0;
1444    for r in 0..n {
1445        let o = ((y + r) * p.cw + x) as usize;
1446        p.ry[o..o + n as usize].copy_from_slice(&saved[k..k + n as usize]);
1447        k += n as usize;
1448    }
1449    let (cx, cy) = (x / 2, y / 2);
1450    for ci in 0..2 {
1451        let plane: &mut [u8] = if ci == 0 { p.ru } else { p.rv };
1452        for r in 0..cn {
1453            let o = ((cy + r) * p.cwc + cx) as usize;
1454            plane[o..o + cn as usize].copy_from_slice(&saved[k..k + cn as usize]);
1455            k += cn as usize;
1456        }
1457    }
1458}
1459
1460/// Lagrangian cost of a candidate subtree: squared error of the reconstruction
1461/// it left behind, plus `lambda` times the bits it actually costs.
1462///
1463/// The bit count is exact rather than modelled — the CABAC engine and its
1464/// contexts are cloned, the candidate coded into the copy, and the copy dropped.
1465/// That costs an extra encode per candidate per level and is why this encoder is
1466/// slower than its structure suggests, but it removes the usual guesswork about
1467/// what a flag is worth in a given context state.
1468#[allow(clippy::too_many_arguments)]
1469fn node_cost(
1470    p: &Planes,
1471    x: u32,
1472    y: u32,
1473    log2: u32,
1474    tu: &Tu,
1475    cabac: &CabacEncoder,
1476    ctx: &Ctx,
1477    depth: u32,
1478    lim: TreeLimits,
1479    mode: u8,
1480    cmode: u8,
1481    lambda: f64,
1482    qd: &QpDelta,
1483) -> f64 {
1484    let n = 1u32 << log2;
1485    let cn = n / 2;
1486    let mut ssd = 0f64;
1487    for r in 0..n {
1488        let o = ((y + r) * p.cw + x) as usize;
1489        for c in 0..n as usize {
1490            let d = p.ry[o + c] as f64 - p.y[o + c] as f64;
1491            ssd += d * d;
1492        }
1493    }
1494    let (cx, cy) = (x / 2, y / 2);
1495    for (rec, src) in [(&*p.ru, p.u), (&*p.rv, p.v)] {
1496        for r in 0..cn {
1497            let o = ((cy + r) * p.cwc + cx) as usize;
1498            for c in 0..cn as usize {
1499                let d = rec[o + c] as f64 - src[o + c] as f64;
1500                ssd += d * d;
1501            }
1502        }
1503    }
1504
1505    // A probe rather than a clone: the output buffer would otherwise be copied
1506    // once per candidate per level.
1507    let mut trial = cabac.probe();
1508    let mut tctx = *ctx;
1509    let mut tqd = *qd;
1510    let before = trial.bit_len();
1511    emit_tu(
1512        &mut trial, &mut tctx, tu, depth, lim, mode, cmode, true, true, None, &mut tqd,
1513    );
1514    let bits = (trial.bit_len() - before) as f64;
1515
1516    ssd + lambda * bits
1517}
1518
1519/// `cu_qp_delta` state for one quantization group (§7.3.8.10).
1520///
1521/// The delta is written in the first transform unit that has anything to code,
1522/// wherever in the coding tree that turns out to be — so the value travels down
1523/// the recursion and the flag comes back up. A group that codes nothing sends no
1524/// delta at all, and then the decoder's `QpY` is the predictor, not the target.
1525#[derive(Clone, Copy)]
1526struct QpDelta {
1527    /// `qPY_PRED` for this group.
1528    pred: i32,
1529    value: i32,
1530    sent: bool,
1531}
1532
1533impl QpDelta {
1534    fn new(pred: i32, value: i32) -> Self {
1535        Self {
1536            pred,
1537            value,
1538            sent: false,
1539        }
1540    }
1541
1542    /// The `QpY` a coding unit finishing *now* would have.
1543    ///
1544    /// Not constant across a quantization group: `CuQpDeltaVal` is zero until
1545    /// the delta is parsed, so coding units decoded before the first one with
1546    /// anything to code sit at the predictor and the rest sit at the target.
1547    /// The deblocking filter reads this per coding unit, which is how the
1548    /// distinction becomes visible at all.
1549    fn qp_now(&self) -> i32 {
1550        self.pred + if self.sent { self.value } else { 0 }
1551    }
1552
1553    /// Emit `cu_qp_delta_abs` and its sign if this is the first coded block of
1554    /// the group. Prefix is truncated unary with `cMax = 5`, two contexts; the
1555    /// tail beyond that is bypass Exp-Golomb.
1556    fn emit(&mut self, cabac: &mut CabacEncoder, ctx: &mut Ctx) {
1557        if self.sent {
1558            return;
1559        }
1560        self.sent = true;
1561        let abs = self.value.unsigned_abs();
1562        let prefix = abs.min(5);
1563        for k in 0..prefix {
1564            cabac.encode_bin(&mut ctx.cu_qp_delta[usize::from(k > 0)], 1);
1565        }
1566        if prefix < 5 {
1567            cabac.encode_bin(&mut ctx.cu_qp_delta[usize::from(prefix > 0)], 0);
1568        } else {
1569            let mut rest = abs - 5;
1570            let mut k = 0u32;
1571            while rest >= (1 << k) {
1572                cabac.encode_bypass(1);
1573                rest -= 1 << k;
1574                k += 1;
1575            }
1576            cabac.encode_bypass(0);
1577            for b in (0..k).rev() {
1578                cabac.encode_bypass((rest >> b) & 1);
1579            }
1580        }
1581        if abs > 0 {
1582            cabac.encode_bypass(u32::from(self.value < 0));
1583        }
1584    }
1585}
1586
1587/// Per-coding-tree-block quantizer offsets from local variance.
1588///
1589/// See the H.264 counterpart in [`crate::h264::compress`] for the reasoning and
1590/// for what it measured. Off by default in both.
1591#[allow(clippy::too_many_arguments)]
1592fn adaptive_qp(
1593    y: &[u8],
1594    cw: u32,
1595    ch: u32,
1596    ctb: u32,
1597    nx: u32,
1598    ny: u32,
1599    base: i32,
1600    strength: f32,
1601) -> Vec<i32> {
1602    let n = (nx * ny) as usize;
1603    if strength == 0.0 {
1604        return vec![base; n];
1605    }
1606    let mut energy = Vec::with_capacity(n);
1607    for cby in 0..ny {
1608        for cbx in 0..nx {
1609            let (ox, oy) = (cbx * ctb, cby * ctb);
1610            let (w, h) = (ctb.min(cw - ox), ctb.min(ch - oy));
1611            let (mut sum, mut sq) = (0i64, 0i64);
1612            for j in 0..h {
1613                let row = ((oy + j) * cw + ox) as usize;
1614                for &p in &y[row..row + w as usize] {
1615                    sum += i64::from(p);
1616                    sq += i64::from(p) * i64::from(p);
1617                }
1618            }
1619            let count = i64::from(w * h).max(1);
1620            let var = (sq - sum * sum / count).max(0) as f32 / count as f32;
1621            energy.push((var + 1.0).log2());
1622        }
1623    }
1624    let mean = energy.iter().sum::<f32>() / energy.len() as f32;
1625    energy
1626        .iter()
1627        .map(|e| {
1628            let adj = (strength * (e - mean)).round().clamp(-5.0, 5.0) as i32;
1629            (base + adj).clamp(0, 51)
1630        })
1631        .collect()
1632}
1633
1634/// Picture geometry the coding quadtree consults constantly.
1635#[derive(Clone, Copy)]
1636struct Geo {
1637    cw: u32,
1638    ch: u32,
1639    ctb: u32,
1640    nx: u32,
1641}
1642
1643/// Per-minimum-coding-block state that later blocks derive their contexts from.
1644///
1645/// Both fields are read by *neighbours*, so a candidate that loses a
1646/// rate-distortion comparison has to leave no trace: [`Grid::save`] and
1647/// [`Grid::restore`] cover exactly the square a candidate may write.
1648struct Grid {
1649    /// Chosen luma prediction mode; `255` where nothing has been coded yet.
1650    modes: Vec<u8>,
1651    /// `CtDepth` — the quadtree depth of the coding unit covering each block,
1652    /// which is what `split_cu_flag`'s context is derived from.
1653    depth: Vec<u8>,
1654    /// `QpY` of the coding unit covering each block, for the deblocking filter.
1655    qp: Vec<i8>,
1656    log2: u32,
1657    w: usize,
1658    h: usize,
1659}
1660
1661impl Grid {
1662    fn new(cw: u32, ch: u32, log2: u32) -> Self {
1663        let (w, h) = ((cw >> log2) as usize, (ch >> log2) as usize);
1664        Self {
1665            modes: vec![255; w * h],
1666            depth: vec![0; w * h],
1667            qp: vec![0; w * h],
1668            log2,
1669            w,
1670            h,
1671        }
1672    }
1673
1674    fn idx(&self, x: u32, y: u32) -> usize {
1675        (y >> self.log2) as usize * self.w + (x >> self.log2) as usize
1676    }
1677
1678    /// Prediction mode at a sample position, DC where nothing was coded.
1679    fn mode_at(&self, x: u32, y: u32) -> u8 {
1680        match self.modes[self.idx(x, y)] {
1681            255 => intra::DC,
1682            m => m,
1683        }
1684    }
1685
1686    fn depth_at(&self, x: u32, y: u32) -> u32 {
1687        u32::from(self.depth[self.idx(x, y)])
1688    }
1689
1690    fn into_qp(self) -> Vec<i8> {
1691        self.qp
1692    }
1693
1694    #[allow(dead_code)]
1695    fn qp_at(&self, x: u32, y: u32) -> i32 {
1696        i32::from(self.qp[self.idx(x, y)])
1697    }
1698
1699    /// Stamp a coding unit's mode, depth and quantizer across every block it
1700    /// covers.
1701    fn set_cu(&mut self, x: u32, y: u32, log2: u32, mode: u8, depth: u32, qp: i32) {
1702        let n = 1u32 << log2;
1703        for dy in (0..n).step_by(1 << self.log2) {
1704            for dx in (0..n).step_by(1 << self.log2) {
1705                let (gx, gy) = ((x + dx) >> self.log2, (y + dy) >> self.log2);
1706                if (gx as usize) < self.w && (gy as usize) < self.h {
1707                    let i = gy as usize * self.w + gx as usize;
1708                    self.modes[i] = mode;
1709                    self.depth[i] = depth as u8;
1710                    self.qp[i] = qp as i8;
1711                }
1712            }
1713        }
1714    }
1715
1716    fn save(&self, x: u32, y: u32, log2: u32) -> Vec<(u8, u8, i8)> {
1717        let n = 1u32 << log2;
1718        let mut out = Vec::new();
1719        for dy in (0..n).step_by(1 << self.log2) {
1720            for dx in (0..n).step_by(1 << self.log2) {
1721                let (gx, gy) = ((x + dx) >> self.log2, (y + dy) >> self.log2);
1722                if (gx as usize) < self.w && (gy as usize) < self.h {
1723                    let i = gy as usize * self.w + gx as usize;
1724                    out.push((self.modes[i], self.depth[i], self.qp[i]));
1725                }
1726            }
1727        }
1728        out
1729    }
1730
1731    fn restore(&mut self, x: u32, y: u32, log2: u32, saved: &[(u8, u8, i8)]) {
1732        let n = 1u32 << log2;
1733        let mut k = 0;
1734        for dy in (0..n).step_by(1 << self.log2) {
1735            for dx in (0..n).step_by(1 << self.log2) {
1736                let (gx, gy) = ((x + dx) >> self.log2, (y + dy) >> self.log2);
1737                if (gx as usize) < self.w && (gy as usize) < self.h {
1738                    let i = gy as usize * self.w + gx as usize;
1739                    (self.modes[i], self.depth[i], self.qp[i]) = saved[k];
1740                    k += 1;
1741                }
1742            }
1743        }
1744    }
1745}
1746
1747/// One node of the coding quadtree: four children, or a coding unit.
1748enum Cu {
1749    /// Fewer than four children where the block hangs off the picture edge —
1750    /// the ones whose top-left corner is outside are not coded at all.
1751    Split(Vec<Cu>),
1752    Leaf(Box<CuLeaf>),
1753}
1754
1755struct CuLeaf {
1756    mode: u8,
1757    cmode: u8,
1758    tu: Tu,
1759}
1760
1761/// Record every transform-block boundary in a decided coding tree, for the
1762/// deblocking filter.
1763///
1764/// The filter only smooths where a transform actually ends. Walking the decided
1765/// tree afterwards is the cheapest place to learn that: during the search the
1766/// answer changes with every candidate, and after it the winner is fixed.
1767fn mark_cu_edges(cu: &Cu, edges: &mut EdgeMap, g: Geo, x: u32, y: u32, log2: u32) {
1768    match cu {
1769        Cu::Split(kids) => {
1770            let half = 1u32 << (log2 - 1);
1771            let mut k = 0;
1772            for (dx, dy) in [(0, 0), (half, 0), (0, half), (half, half)] {
1773                let (kx, ky) = (x + dx, y + dy);
1774                if kx >= g.cw || ky >= g.ch {
1775                    continue;
1776                }
1777                mark_cu_edges(&kids[k], edges, g, kx, ky, log2 - 1);
1778                k += 1;
1779            }
1780        }
1781        Cu::Leaf(l) => mark_tu_edges(&l.tu, edges, x, y),
1782    }
1783}
1784
1785fn mark_tu_edges(tu: &Tu, edges: &mut EdgeMap, x: u32, y: u32) {
1786    if tu.split {
1787        let half = 1u32 << (tu.log2 - 1);
1788        for (i, (dx, dy)) in [(0, 0), (half, 0), (0, half), (half, half)]
1789            .into_iter()
1790            .enumerate()
1791        {
1792            if let Some(child) = tu.children.get(i) {
1793                mark_tu_edges(child, edges, x + dx, y + dy);
1794            }
1795        }
1796        return;
1797    }
1798    edges.mark(x, y, 1 << tu.log2);
1799}
1800
1801/// `split_cu_flag`'s context: how many of the two neighbours sit *deeper* in the
1802/// quadtree than this node (§9.3.4.2.2). A neighbourhood of small blocks is
1803/// evidence that this one should be small too.
1804fn split_ctx(grid: &Grid, g: Geo, x: u32, y: u32, depth: u32) -> usize {
1805    let (xi, yi) = (x as i32, y as i32);
1806    let left =
1807        available(xi - 1, yi, x, y, g.cw, g.ch, g.ctb, g.nx) && grid.depth_at(x - 1, y) > depth;
1808    let above =
1809        available(xi, yi - 1, x, y, g.cw, g.ch, g.ctb, g.nx) && grid.depth_at(x, y - 1) > depth;
1810    usize::from(left) + usize::from(above)
1811}
1812
1813/// Squared error the current reconstruction leaves over a block, all three planes.
1814fn ssd_rect(p: &Planes, x: u32, y: u32, log2: u32) -> f64 {
1815    let n = (1u32 << log2).min(p.cw - x).min(p.ch - y);
1816    let mut ssd = 0f64;
1817    for r in 0..n {
1818        let o = ((y + r) * p.cw + x) as usize;
1819        for c in 0..n as usize {
1820            let d = p.ry[o + c] as f64 - p.y[o + c] as f64;
1821            ssd += d * d;
1822        }
1823    }
1824    let (cx, cy) = (x / 2, y / 2);
1825    let cn = n / 2;
1826    for (rec, src) in [(&*p.ru, p.u), (&*p.rv, p.v)] {
1827        for r in 0..cn {
1828            let o = ((cy + r) * p.cwc + cx) as usize;
1829            for c in 0..cn as usize {
1830                let d = rec[o + c] as f64 - src[o + c] as f64;
1831                ssd += d * d;
1832            }
1833        }
1834    }
1835    ssd
1836}
1837
1838/// Choose between coding `(x, y)` as one coding unit and splitting it in four,
1839/// and return the winner along with its Lagrangian cost.
1840///
1841/// `cabac` and `ctx` are a scratch pair: the search encodes into them so that
1842/// each candidate sees the context state its predecessors actually leave, and
1843/// the winner's state is what carries forward. The real bitstream is written
1844/// later by [`emit_cu`], which walks the decided tree.
1845#[allow(clippy::too_many_arguments)]
1846fn search_cu(
1847    p: &mut Planes,
1848    cabac: &mut CabacEncoder,
1849    ctx: &mut Ctx,
1850    grid: &mut Grid,
1851    g: Geo,
1852    x: u32,
1853    y: u32,
1854    log2: u32,
1855    depth: u32,
1856    lim: TreeLimits,
1857    lambda: f64,
1858    qd: &mut QpDelta,
1859) -> (Cu, f64) {
1860    let size = 1u32 << log2;
1861    let inside = x + size <= g.cw && y + size <= g.ch;
1862
1863    // A block hanging off the picture edge is split without a flag: the decoder
1864    // knows it cannot be coded whole (§7.3.8.4).
1865    if !inside {
1866        return split_cu(
1867            p, cabac, ctx, grid, g, x, y, log2, depth, lim, lambda, false, qd,
1868        );
1869    }
1870    // At the minimum coding block size there is nothing to decide.
1871    if log2 == grid.log2 {
1872        return leaf_cu(
1873            p, cabac, ctx, grid, g, x, y, log2, depth, lim, lambda, false, qd,
1874        );
1875    }
1876
1877    let before = save_rect(p, x, y, log2);
1878    let gbefore = grid.save(x, y, log2);
1879
1880    let mut cabac_one = cabac.clone();
1881    let mut ctx_one = *ctx;
1882    let mut qd_one = *qd;
1883    let (cu_one, cost_one) = leaf_cu(
1884        p,
1885        &mut cabac_one,
1886        &mut ctx_one,
1887        grid,
1888        g,
1889        x,
1890        y,
1891        log2,
1892        depth,
1893        lim,
1894        lambda,
1895        true,
1896        &mut qd_one,
1897    );
1898    let recon_one = save_rect(p, x, y, log2);
1899    let grid_one = grid.save(x, y, log2);
1900
1901    restore_rect(p, x, y, log2, &before);
1902    grid.restore(x, y, log2, &gbefore);
1903    let mut cabac_four = cabac.clone();
1904    let mut ctx_four = *ctx;
1905    let mut qd_four = *qd;
1906    let (cu_four, cost_four) = split_cu(
1907        p,
1908        &mut cabac_four,
1909        &mut ctx_four,
1910        grid,
1911        g,
1912        x,
1913        y,
1914        log2,
1915        depth,
1916        lim,
1917        lambda,
1918        true,
1919        &mut qd_four,
1920    );
1921
1922    if cost_one <= cost_four {
1923        restore_rect(p, x, y, log2, &recon_one);
1924        grid.restore(x, y, log2, &grid_one);
1925        *cabac = cabac_one;
1926        *ctx = ctx_one;
1927        *qd = qd_one;
1928        (cu_one, cost_one)
1929    } else {
1930        *cabac = cabac_four;
1931        *ctx = ctx_four;
1932        *qd = qd_four;
1933        (cu_four, cost_four)
1934    }
1935}
1936
1937/// Code `(x, y)` as a single intra coding unit.
1938#[allow(clippy::too_many_arguments)]
1939fn leaf_cu(
1940    p: &mut Planes,
1941    cabac: &mut CabacEncoder,
1942    ctx: &mut Ctx,
1943    grid: &mut Grid,
1944    g: Geo,
1945    x: u32,
1946    y: u32,
1947    log2: u32,
1948    depth: u32,
1949    lim: TreeLimits,
1950    lambda: f64,
1951    flag: bool,
1952    qd: &mut QpDelta,
1953) -> (Cu, f64) {
1954    let start = cabac.bit_len();
1955    if flag {
1956        let inc = split_ctx(grid, g, x, y, depth);
1957        cabac.encode_bin(&mut ctx.split_cu[inc], 0);
1958    }
1959
1960    // Pick the mode on the first transform block rather than the whole coding
1961    // unit: for a block bigger than the largest transform, that is the only part
1962    // whose reference samples exist yet, and a mode that suits it badly loses
1963    // the split comparison anyway.
1964    let mn = 1u32 << log2.min(lim.max_tb_log2);
1965    let lvals = refs_luma(p.ry, p.cw, p.ch, x, y, mn, p.nx, p.ctb);
1966    let orig = gather(p.y, p.cw, x, y, mn);
1967    let mode = best_luma_mode(&orig, mn as usize, &lvals);
1968    let cmode = chroma_mode_from_luma(mode);
1969
1970    let tu = build_tu(p, cabac, ctx, x, y, log2, 0, lim, mode, cmode, lambda, qd);
1971
1972    // ---- coding_unit syntax (§7.3.8.5) ----
1973    if log2 == grid.log2 {
1974        // part_mode exists only at the minimum size, where PART_NxN is legal.
1975        cabac.encode_bin(&mut ctx.part_mode, 1); // PART_2Nx2N
1976    }
1977    code_luma_mode(cabac, ctx, mode, grid, g, x, y);
1978    cabac.encode_bin(&mut ctx.chroma_mode, 0); // intra_chroma_pred_mode = DM
1979    emit_tu(cabac, ctx, &tu, 0, lim, mode, cmode, true, true, None, qd);
1980    grid.set_cu(x, y, log2, mode, depth, qd.qp_now());
1981
1982    let bits = (cabac.bit_len() - start) as f64;
1983    let cost = ssd_rect(p, x, y, log2) + lambda * bits;
1984    (Cu::Leaf(Box::new(CuLeaf { mode, cmode, tu })), cost)
1985}
1986
1987/// Split `(x, y)` into four quadrants and code each independently.
1988#[allow(clippy::too_many_arguments)]
1989fn split_cu(
1990    p: &mut Planes,
1991    cabac: &mut CabacEncoder,
1992    ctx: &mut Ctx,
1993    grid: &mut Grid,
1994    g: Geo,
1995    x: u32,
1996    y: u32,
1997    log2: u32,
1998    depth: u32,
1999    lim: TreeLimits,
2000    lambda: f64,
2001    flag: bool,
2002    qd: &mut QpDelta,
2003) -> (Cu, f64) {
2004    let start = cabac.bit_len();
2005    if flag {
2006        let inc = split_ctx(grid, g, x, y, depth);
2007        cabac.encode_bin(&mut ctx.split_cu[inc], 1);
2008    }
2009    let mut cost = lambda * (cabac.bit_len() - start) as f64;
2010
2011    let half = 1u32 << (log2 - 1);
2012    let mut kids = Vec::with_capacity(4);
2013    for (dx, dy) in [(0, 0), (half, 0), (0, half), (half, half)] {
2014        let (kx, ky) = (x + dx, y + dy);
2015        if kx >= g.cw || ky >= g.ch {
2016            continue; // wholly outside the picture: never coded
2017        }
2018        let (kid, kc) = search_cu(
2019            p,
2020            cabac,
2021            ctx,
2022            grid,
2023            g,
2024            kx,
2025            ky,
2026            log2 - 1,
2027            depth + 1,
2028            lim,
2029            lambda,
2030            qd,
2031        );
2032        kids.push(kid);
2033        cost += kc;
2034    }
2035    (Cu::Split(kids), cost)
2036}
2037
2038/// Write the decided quadtree to the real bitstream.
2039///
2040/// Every context this reads — `split_cu_flag`'s neighbour depths, the mode
2041/// prediction list — comes from `grid`, which the caller has rolled back to its
2042/// pre-search state, so the derivations here reproduce the search's exactly.
2043#[allow(clippy::too_many_arguments)]
2044fn emit_cu(
2045    cabac: &mut CabacEncoder,
2046    ctx: &mut Ctx,
2047    cu: &Cu,
2048    grid: &mut Grid,
2049    g: Geo,
2050    x: u32,
2051    y: u32,
2052    log2: u32,
2053    depth: u32,
2054    lim: TreeLimits,
2055    qd: &mut QpDelta,
2056) {
2057    let size = 1u32 << log2;
2058    let codes_flag = x + size <= g.cw && y + size <= g.ch && log2 > grid.log2;
2059    match cu {
2060        Cu::Split(kids) => {
2061            if codes_flag {
2062                let inc = split_ctx(grid, g, x, y, depth);
2063                cabac.encode_bin(&mut ctx.split_cu[inc], 1);
2064            }
2065            let half = 1u32 << (log2 - 1);
2066            let mut k = 0;
2067            for (dx, dy) in [(0, 0), (half, 0), (0, half), (half, half)] {
2068                let (kx, ky) = (x + dx, y + dy);
2069                if kx >= g.cw || ky >= g.ch {
2070                    continue;
2071                }
2072                emit_cu(
2073                    cabac,
2074                    ctx,
2075                    &kids[k],
2076                    grid,
2077                    g,
2078                    kx,
2079                    ky,
2080                    log2 - 1,
2081                    depth + 1,
2082                    lim,
2083                    qd,
2084                );
2085                k += 1;
2086            }
2087        }
2088        Cu::Leaf(l) => {
2089            if codes_flag {
2090                let inc = split_ctx(grid, g, x, y, depth);
2091                cabac.encode_bin(&mut ctx.split_cu[inc], 0);
2092            }
2093            if log2 == grid.log2 {
2094                cabac.encode_bin(&mut ctx.part_mode, 1);
2095            }
2096            code_luma_mode(cabac, ctx, l.mode, grid, g, x, y);
2097            cabac.encode_bin(&mut ctx.chroma_mode, 0);
2098            emit_tu(
2099                cabac, ctx, &l.tu, 0, lim, l.mode, l.cmode, true, true, None, qd,
2100            );
2101            grid.set_cu(x, y, log2, l.mode, depth, qd.qp_now());
2102        }
2103    }
2104}
2105
2106/// Chroma mode for DM_CHROMA in 4:2:0 (identity — no 4:2:2 remap needed).
2107fn chroma_mode_from_luma(luma: u8) -> u8 {
2108    luma
2109}
2110
2111/// Try planar/DC and every angular mode (each with its own smoothing); return the
2112/// one with least SAD against the original.
2113fn best_luma_mode(orig: &[i32], n: usize, vals: &[i32]) -> u8 {
2114    // The reference samples depend on the mode only through `filter_flag`,
2115    // which is a boolean — so across all thirty-five modes there are exactly two
2116    // reference sets, not thirty-five. Building both once turns a hundred and
2117    // five allocations and thirty-five smoothing passes into three and one.
2118    let plain = split_refs(vals, n);
2119    let smooth = split_refs(&smooth_refs(vals), n);
2120    let mut best = (u32::MAX, intra::DC);
2121    let mut pred = vec![0i32; n * n];
2122    for mode in 0..=34u8 {
2123        let (above, left) = if filter_flag(mode, n) {
2124            &smooth
2125        } else {
2126            &plain
2127        };
2128        intra::predict_into(mode, n, above, left, true, &mut pred[..]);
2129        let sad: u32 = orig
2130            .iter()
2131            .zip(&pred)
2132            .map(|(&o, &p)| (o - p).unsigned_abs())
2133            .sum();
2134        if sad < best.0 {
2135            best = (sad, mode);
2136        }
2137    }
2138    best.1
2139}
2140
2141/// Code the chosen luma mode via the MPM list (§8.4.2, §9.3).
2142#[allow(clippy::too_many_arguments)]
2143fn code_luma_mode(
2144    cabac: &mut CabacEncoder,
2145    ctx: &mut Ctx,
2146    mode: u8,
2147    grid: &Grid,
2148    g: Geo,
2149    x: u32,
2150    y: u32,
2151) {
2152    let (xi, yi) = (x as i32, y as i32);
2153    let cand_a = if available(xi - 1, yi, x, y, g.cw, g.ch, g.ctb, g.nx) {
2154        grid.mode_at(x - 1, y)
2155    } else {
2156        intra::DC
2157    };
2158    // The above neighbour only counts inside the current CTB row. Line buffers
2159    // would otherwise have to hold a whole picture-width of modes, so the spec
2160    // substitutes DC across the CTB boundary (§8.4.2).
2161    let ctb_top = ((y >> g.ctb.trailing_zeros()) << g.ctb.trailing_zeros()) as i32;
2162    let same_ctb_row = yi > ctb_top;
2163    let cand_b = if same_ctb_row && available(xi, yi - 1, x, y, g.cw, g.ch, g.ctb, g.nx) {
2164        grid.mode_at(x, y - 1)
2165    } else {
2166        intra::DC
2167    };
2168
2169    let list = mpm_list(cand_a, cand_b);
2170    if let Some(idx) = list.iter().position(|&m| m == mode) {
2171        cabac.encode_bin(&mut ctx.prev_intra, 1);
2172        // mpm_idx: truncated unary, cMax 2, bypass.
2173        match idx {
2174            0 => cabac.encode_bypass(0),
2175            1 => {
2176                cabac.encode_bypass(1);
2177                cabac.encode_bypass(0);
2178            }
2179            _ => {
2180                cabac.encode_bypass(1);
2181                cabac.encode_bypass(1);
2182            }
2183        }
2184    } else {
2185        cabac.encode_bin(&mut ctx.prev_intra, 0);
2186        let mut sorted = list;
2187        sorted.sort_unstable();
2188        let mut rem = mode as i32;
2189        for &c in sorted.iter().rev() {
2190            if rem > c as i32 {
2191                rem -= 1;
2192            }
2193        }
2194        cabac.encode_bypass_bits(rem as u32, 5); // rem_intra_luma_pred_mode, FL(5)
2195    }
2196}
2197
2198/// Build the 3-entry most-probable-mode list (§8.4.2).
2199fn mpm_list(a: u8, b: u8) -> [u8; 3] {
2200    if a == b {
2201        if a < 2 {
2202            [intra::PLANAR, intra::DC, 26]
2203        } else {
2204            [
2205                a,
2206                2 + ((a as i32 + 29) % 32) as u8,
2207                2 + ((a as i32 - 2 + 1) % 32) as u8,
2208            ]
2209        }
2210    } else {
2211        let mut l = [a, b, 0];
2212        l[2] = if a != intra::PLANAR && b != intra::PLANAR {
2213            intra::PLANAR
2214        } else if a != intra::DC && b != intra::DC {
2215            intra::DC
2216        } else {
2217            26
2218        };
2219        l
2220    }
2221}
2222
2223// ---- reference samples ----
2224
2225/// Is luma/chroma sample (px, py) already reconstructed? True iff its CTB precedes
2226/// the current one in raster order and it is inside the coded picture.
2227/// Whether the sample at `(px, py)` has already been reconstructed when coding
2228/// the block whose origin is `(bx, by)`.
2229///
2230/// CTBs are coded in raster order and blocks inside a CTB in z (Morton) order,
2231/// so a lexicographic compare of `(CTB index, Morton code)` *is* decoding order.
2232/// Comparing the neighbour's sample against the current block's origin is exact
2233/// because Morton order is hierarchical: the origin is the smallest code in its
2234/// block, and every sample of an earlier block sorts below all of them.
2235fn available(px: i32, py: i32, bx: u32, by: u32, w: u32, h: u32, ctb: u32, nx: u32) -> bool {
2236    available_at(px, py, decode_order(bx, by, ctb, nx), w, h, ctb, nx)
2237}
2238
2239/// [`available`] with the current block's place in decoding order already known.
2240///
2241/// Every one of a block's `4n+1` reference samples asks the same question about
2242/// the same block, so recomputing that half of the comparison per sample made
2243/// this the hottest thing in the encoder.
2244#[inline]
2245fn available_at(px: i32, py: i32, here: (u32, u32), w: u32, h: u32, ctb: u32, nx: u32) -> bool {
2246    if px < 0 || py < 0 || px >= w as i32 || py >= h as i32 {
2247        return false;
2248    }
2249    decode_order(px as u32, py as u32, ctb, nx) < here
2250}
2251
2252#[inline]
2253fn decode_order(px: u32, py: u32, ctb: u32, nx: u32) -> (u32, u32) {
2254    // `ctb` is a power of two, but nothing in the type says so and the compiler
2255    // was emitting real integer divisions — two divisions and two remainders per
2256    // call, on the encoder's hottest path.
2257    let sh = ctb.trailing_zeros();
2258    let mask = ctb - 1;
2259    ((py >> sh) * nx + (px >> sh), morton(px & mask, py & mask))
2260}
2261
2262/// Interleave the bits of `x` and `y` (y in the odd positions) — the z-order
2263/// curve HEVC scans transform blocks along.
2264#[inline]
2265fn morton(x: u32, y: u32) -> u32 {
2266    spread(x) | (spread(y) << 1)
2267}
2268
2269/// Move each of the low 16 bits of `v` into an even position and zero the odd
2270/// ones: the doubling-and-masking ladder, five steps against the sixteen-round
2271/// loop it replaces.
2272#[inline]
2273fn spread(v: u32) -> u32 {
2274    let mut v = v & 0xFFFF;
2275    v = (v | (v << 8)) & 0x00FF_00FF;
2276    v = (v | (v << 4)) & 0x0F0F_0F0F;
2277    v = (v | (v << 2)) & 0x3333_3333;
2278    v = (v | (v << 1)) & 0x5555_5555;
2279    v
2280}
2281
2282/// `scanIdx` (H.265 §7.4.9.11). 4x4 blocks and 8x8 luma pick their coefficient
2283/// scan from the prediction mode; everything larger scans diagonally.
2284fn scan_idx(mode: u8, log2: u32, chroma: bool) -> u8 {
2285    if !(log2 == 2 || (log2 == 3 && !chroma)) {
2286        return 0;
2287    }
2288    match mode {
2289        6..=14 => 2,  // near-horizontal prediction -> vertical scan
2290        22..=30 => 1, // near-vertical prediction -> horizontal scan
2291        _ => 0,
2292    }
2293}
2294
2295/// Build the substituted reference chain `vals[0..=4n]` in the order
2296/// bottom-left → left → corner → top → top-right (§8.4.4.2.2). Smoothing and
2297/// above/left extraction happen later (they depend on the chosen mode).
2298#[allow(clippy::too_many_arguments)]
2299fn refs_generic(
2300    recon: &[u8],
2301    w: u32,
2302    h: u32,
2303    x: u32,
2304    y: u32,
2305    n: u32,
2306    ctb: u32,
2307    nx: u32,
2308) -> Vec<i32> {
2309    let mut out = vec![0i32; (4 * n + 1) as usize];
2310    refs_generic_into(recon, w, h, x, y, n, ctb, nx, &mut out);
2311    out
2312}
2313
2314fn refs_generic_into(
2315    recon: &[u8],
2316    w: u32,
2317    h: u32,
2318    x: u32,
2319    y: u32,
2320    n: u32,
2321    ctb: u32,
2322    nx: u32,
2323    out: &mut [i32],
2324) {
2325    let ni = n as i32;
2326    let (xi, yi) = (x as i32, y as i32);
2327    let sample = |px: i32, py: i32| recon[(py as u32 * w + px as u32) as usize] as i32;
2328    // Constant for every one of the 4n+1 reference samples below.
2329    let here = decode_order(x, y, ctb, nx);
2330
2331    let vals = out;
2332    vals.fill(0);
2333    let mut avail = vec![false; (4 * n + 1) as usize];
2334    for k in 0..(2 * ni) {
2335        let py = yi + (2 * ni - 1 - k); // left column p[-1][2n-1-k]
2336        if available_at(xi - 1, py, here, w, h, ctb, nx) {
2337            vals[k as usize] = sample(xi - 1, py);
2338            avail[k as usize] = true;
2339        }
2340    }
2341    if available_at(xi - 1, yi - 1, here, w, h, ctb, nx) {
2342        vals[(2 * ni) as usize] = sample(xi - 1, yi - 1); // corner
2343        avail[(2 * ni) as usize] = true;
2344    }
2345    for k in 0..(2 * ni) {
2346        let px = xi + k; // top row p[k][-1]
2347        if available_at(px, yi - 1, here, w, h, ctb, nx) {
2348            vals[(2 * ni + 1 + k) as usize] = sample(px, yi - 1);
2349            avail[(2 * ni + 1 + k) as usize] = true;
2350        }
2351    }
2352
2353    let len = vals.len();
2354    if avail.iter().all(|&a| !a) {
2355        vals.iter_mut().for_each(|v| *v = 128);
2356    } else {
2357        if !avail[0] {
2358            let first = (0..len).find(|&i| avail[i]).unwrap();
2359            vals[0] = vals[first];
2360        }
2361        for i in 1..len {
2362            if !avail[i] {
2363                vals[i] = vals[i - 1];
2364            }
2365        }
2366    }
2367}
2368
2369#[allow(clippy::too_many_arguments)]
2370fn refs_luma(recon: &[u8], w: u32, h: u32, x: u32, y: u32, n: u32, nx: u32, ctb: u32) -> Vec<i32> {
2371    refs_generic(recon, w, h, x, y, n, ctb, nx)
2372}
2373
2374/// Reference-sample smoothing decision (§8.4.4.2.3): the `[1 2 1]` filter applies
2375/// for larger blocks and modes far from horizontal/vertical.
2376fn filter_flag(mode: u8, n: usize) -> bool {
2377    if mode == intra::DC || n == 4 {
2378        return false;
2379    }
2380    let min_dist = (mode as i32 - 26).abs().min((mode as i32 - 10).abs());
2381    let thres = match n {
2382        8 => 7,
2383        16 => 1,
2384        32 => 0,
2385        _ => 8,
2386    };
2387    min_dist > thres
2388}
2389
2390/// Apply mode-dependent smoothing to the reference chain, then split it into the
2391/// `above`/`left` arrays the predictor consumes. Reference-sample smoothing is
2392/// **luma-only** in 4:2:0 (ChromaArrayType != 3, §8.4.4.2.1): chroma reference
2393/// samples are never filtered, so `luma` gates the `[1 2 1]` filter.
2394#[allow(dead_code)]
2395fn extract(vals: &[i32], n: usize, mode: u8, luma: bool) -> (Vec<i32>, Vec<i32>) {
2396    let (mut a, mut l) = (vec![0i32; 2 * n + 1], vec![0i32; 2 * n + 1]);
2397    extract_into(vals, n, mode, luma, &mut a, &mut l);
2398    (a, l)
2399}
2400
2401/// [`extract`] into caller-owned buffers.
2402fn extract_into(vals: &[i32], n: usize, mode: u8, luma: bool, above: &mut [i32], left: &mut [i32]) {
2403    if luma && filter_flag(mode, n) {
2404        split_refs_into(&smooth_refs(vals), n, above, left);
2405    } else {
2406        split_refs_into(vals, n, above, left);
2407    }
2408}
2409
2410/// The `[1 2 1]` smoothing of §8.4.4.2.3, applied to the whole reference chain.
2411fn smooth_refs(vals: &[i32]) -> Vec<i32> {
2412    let mut f = vec![0i32; vals.len()];
2413    smooth_refs_into(vals, &mut f);
2414    f
2415}
2416
2417fn smooth_refs_into(vals: &[i32], out: &mut [i32]) {
2418    let last = vals.len() - 1;
2419    out[0] = vals[0];
2420    out[last] = vals[last];
2421    for i in 1..last {
2422        out[i] = (vals[i - 1] + 2 * vals[i] + vals[i + 1] + 2) >> 2;
2423    }
2424}
2425
2426/// Split the reference chain into the above and left rays, both starting at the
2427/// corner.
2428fn split_refs(src: &[i32], n: usize) -> (Vec<i32>, Vec<i32>) {
2429    let (mut a, mut l) = (vec![0i32; 2 * n + 1], vec![0i32; 2 * n + 1]);
2430    split_refs_into(src, n, &mut a, &mut l);
2431    (a, l)
2432}
2433
2434fn split_refs_into(src: &[i32], n: usize, above: &mut [i32], left: &mut [i32]) {
2435    let corner = 2 * n;
2436    above[0] = src[corner];
2437    left[0] = src[corner];
2438    for k in 1..=2 * n {
2439        above[k] = src[corner + k];
2440        left[k] = src[corner - k];
2441    }
2442}
2443
2444// ---- block helpers ----
2445
2446fn gather_into(plane: &[u8], w: u32, x: u32, y: u32, n: u32, out: &mut [i32]) {
2447    for yy in 0..n {
2448        let row = ((y + yy) * w + x) as usize;
2449        let dst = (yy * n) as usize;
2450        for (o, &v) in out[dst..dst + n as usize]
2451            .iter_mut()
2452            .zip(&plane[row..row + n as usize])
2453        {
2454            *o = i32::from(v);
2455        }
2456    }
2457}
2458
2459fn gather(plane: &[u8], w: u32, x: u32, y: u32, n: u32) -> Vec<i32> {
2460    let mut b = vec![0i32; (n * n) as usize];
2461    for yy in 0..n {
2462        for xx in 0..n {
2463            b[(yy * n + xx) as usize] = plane[((y + yy) * w + (x + xx)) as usize] as i32;
2464        }
2465    }
2466    b
2467}
2468
2469fn store(plane: &mut [u8], w: u32, x: u32, y: u32, n: u32, block: &[i32]) {
2470    for yy in 0..n {
2471        for xx in 0..n {
2472            plane[((y + yy) * w + (x + xx)) as usize] =
2473                block[(yy * n + xx) as usize].clamp(0, 255) as u8;
2474        }
2475    }
2476}
2477
2478#[cfg(test)]
2479mod tests {
2480    use super::*;
2481
2482    #[test]
2483    fn mpm_list_cases() {
2484        // Both neighbors DC → planar/DC/vertical fallback.
2485        assert_eq!(mpm_list(1, 1), [intra::PLANAR, intra::DC, 26]);
2486        // Distinct non-planar/non-DC → third is planar.
2487        assert_eq!(mpm_list(10, 26), [10, 26, intra::PLANAR]);
2488        // Distinct incl. planar → third is DC.
2489        assert_eq!(mpm_list(intra::PLANAR, 26), [0, 26, intra::DC]);
2490        // Equal angular → derived neighbors.
2491        let l = mpm_list(20, 20);
2492        assert_eq!(l[0], 20);
2493        assert!(l[1] >= 2 && l[2] >= 2 && l[1] != l[2]);
2494    }
2495
2496    #[test]
2497    fn filter_flag_rules() {
2498        assert!(!filter_flag(intra::DC, 16)); // DC never filtered
2499        assert!(!filter_flag(10, 4)); // 4x4 never filtered
2500        assert!(!filter_flag(26, 16)); // pure vertical: minDist 0 <= 1
2501        assert!(filter_flag(intra::PLANAR, 16)); // planar minDist 10 > 1
2502        assert!(filter_flag(18, 16)); // diagonal filtered
2503    }
2504
2505    #[test]
2506    fn rem_mode_roundtrips_through_mpm() {
2507        // Encoding a non-MPM mode and decoding rem must recover it.
2508        let list = mpm_list(1, 1);
2509        let mut sorted = list;
2510        sorted.sort_unstable();
2511        for mode in 0..=34u8 {
2512            if list.contains(&mode) {
2513                continue;
2514            }
2515            let mut rem = mode as i32;
2516            for &c in sorted.iter().rev() {
2517                if rem > c as i32 {
2518                    rem -= 1;
2519                }
2520            }
2521            // Decoder inverse.
2522            let mut dec = rem;
2523            for &c in sorted.iter() {
2524                if dec >= c as i32 {
2525                    dec += 1;
2526                }
2527            }
2528            assert_eq!(dec as u8, mode, "rem roundtrip for mode {mode}");
2529        }
2530    }
2531}