Skip to main content

threers_codec/vp9/
encoder.rs

1//! VP9 intra encoder with 4×4 DCT residual coding.
2//!
3//! Recursively `PARTITION_SPLIT`s each 64×64 superblock down to 8×8 (including
4//! partial edge superblocks), picks a DC/V/H mode by SAD, then transform-codes
5//! each 4×4 residual with the matching hybrid TX. Intra prediction is per-TX.
6//! A conformant decoder must reproduce our reconstruction bit-for-bit
7//! (see `tests/webm.rs`).
8//!
9//! Frame width/height must be multiples of 8 (MI size) and at least 8; 4:2:0
10//! also needs even chroma dims, which that implies.
11
12use crate::bitstream::BitWriter;
13use crate::hevc::Yuv420Frame;
14use crate::vp9::bool_coder::BoolEncoder;
15use crate::vp9::intra::{predict, sad};
16use crate::vp9::quant::{ac_quant, dc_quant, quantize};
17use crate::vp9::tables::{
18    bsl_from_px, partition_ctx_index, DC_PRED, DEFAULT_SKIP_PROBS, INTRA_MODE_TREE,
19    KF_PARTITION_PROBS, KF_UV_MODE_PROB, KF_Y_MODE_PROB, PARTITION_CONTEXT_LOOKUP, PARTITION_NONE,
20    PARTITION_SPLIT, PARTITION_TREE, PRED_MODES,
21};
22use crate::vp9::tokens::write_coefs;
23use crate::vp9::transform::{fht4x4, iht4x4_add, tx_type_from_mode, TxType};
24
25const FRAME_SYNC_CODE: u32 = 0x0049_8342;
26const CS_BT_601: u32 = 1;
27const MAX_TILE_WIDTH_SB: u32 = 64;
28/// Must match `base_q_idx` in the uncompressed header.
29const QINDEX: usize = 128;
30
31/// Reconstruction a conformant decoder produces.
32#[derive(Clone, Debug)]
33pub struct Reconstruction {
34    pub width: u32,
35    pub height: u32,
36    pub y: Vec<u8>,
37    pub u: Vec<u8>,
38    pub v: Vec<u8>,
39}
40
41/// Encode one VP9 intra keyframe (4×4 DCT residual). Returns `(bitstream, recon)`.
42///
43/// `frame.width` / `height` must be ≥ 8 and multiples of 8.
44pub fn encode_intra_frame(frame: &Yuv420Frame) -> (Vec<u8>, Reconstruction) {
45    assert!(
46        frame.width >= 8
47            && frame.height >= 8
48            && frame.width.is_multiple_of(8)
49            && frame.height.is_multiple_of(8),
50        "VP9 encoder needs dims that are multiples of 8 (got {}×{})",
51        frame.width,
52        frame.height
53    );
54
55    let mut enc = FrameEnc::new(frame);
56    let compressed = compressed_header();
57    let tile = enc.encode_tile();
58
59    let mut wb = BitWriter::new();
60    write_uncompressed_header(&mut wb, frame.width, frame.height, compressed.len() as u32);
61    let mut out = wb.finish();
62    out.extend_from_slice(&compressed);
63    out.extend_from_slice(&tile);
64
65    let recon = Reconstruction {
66        width: frame.width,
67        height: frame.height,
68        y: enc.recon_y,
69        u: enc.recon_u,
70        v: enc.recon_v,
71    };
72    (crate::vp9::finalize_frame(out), recon)
73}
74
75struct MiInfo {
76    mode: i8,
77    skip: bool,
78}
79
80struct FrameEnc<'a> {
81    src: &'a Yuv420Frame,
82    mi_cols: usize,
83    mi_rows: usize,
84    recon_y: Vec<u8>,
85    recon_u: Vec<u8>,
86    recon_v: Vec<u8>,
87    mi: Vec<MiInfo>,
88    above_ctx: Vec<u8>,
89    left_ctx: [u8; 8],
90    /// Y entropy contexts: 2 per MI column (4×4 TX).
91    above_ent_y: Vec<u8>,
92    left_ent_y: [u8; 16],
93    above_ent_u: Vec<u8>,
94    left_ent_u: [u8; 8],
95    above_ent_v: Vec<u8>,
96    left_ent_v: [u8; 8],
97    bool: BoolEncoder,
98    dc_q: i32,
99    ac_q: i32,
100}
101
102impl<'a> FrameEnc<'a> {
103    fn new(src: &'a Yuv420Frame) -> Self {
104        let (w, h) = (src.width as usize, src.height as usize);
105        // VP9 MI grid is 8×8; dims are required to be multiples of 8 so this
106        // matches `(size + 7) >> 3` without padding.
107        let mi_cols = w / 8;
108        let mi_rows = h / 8;
109        let cw = w / 2;
110        let ch = h / 2;
111        Self {
112            src,
113            mi_cols,
114            mi_rows,
115            recon_y: vec![0; w * h],
116            recon_u: vec![128; cw * ch],
117            recon_v: vec![128; cw * ch],
118            mi: (0..mi_cols * mi_rows)
119                .map(|_| MiInfo {
120                    mode: DC_PRED,
121                    skip: true,
122                })
123                .collect(),
124            above_ctx: vec![0; mi_cols],
125            left_ctx: [0; 8],
126            above_ent_y: vec![0; mi_cols * 2],
127            left_ent_y: [0; 16],
128            above_ent_u: vec![0; mi_cols],
129            left_ent_u: [0; 8],
130            above_ent_v: vec![0; mi_cols],
131            left_ent_v: [0; 8],
132            bool: BoolEncoder::new(),
133            dc_q: dc_quant(QINDEX),
134            ac_q: ac_quant(QINDEX),
135        }
136    }
137
138    fn encode_tile(&mut self) -> Vec<u8> {
139        let mut mi_row = 0;
140        while mi_row < self.mi_rows {
141            self.left_ctx = [0; 8];
142            self.left_ent_y = [0; 16];
143            self.left_ent_u = [0; 8];
144            self.left_ent_v = [0; 8];
145            let mut mi_col = 0;
146            while mi_col < self.mi_cols {
147                self.encode_partition(mi_row, mi_col, 64);
148                mi_col += 8; // next superblock column (may be partial)
149            }
150            mi_row += 8;
151        }
152        std::mem::take(&mut self.bool).finish()
153    }
154
155    fn encode_partition(&mut self, mi_row: usize, mi_col: usize, bsize_px: u32) {
156        if mi_row >= self.mi_rows || mi_col >= self.mi_cols {
157            return;
158        }
159        let mi_half = (bsize_px as usize / 8) / 2;
160        let has_rows = mi_row + mi_half < self.mi_rows;
161        let has_cols = mi_col + mi_half < self.mi_cols;
162
163        // Match libvpx `read_partition`: when neither half fits, SPLIT is forced
164        // with no bits (recursive children no-op out of bounds). Never NONE above
165        // 8×8 — our residual path only emits 8×8 blocks.
166        let partition = if bsize_px == 8 {
167            PARTITION_NONE
168        } else if has_rows && has_cols {
169            PARTITION_SPLIT
170        } else if has_cols || has_rows {
171            PARTITION_SPLIT
172        } else {
173            PARTITION_SPLIT
174        };
175
176        self.write_partition(mi_row, mi_col, bsize_px, has_rows, has_cols, partition);
177
178        if bsize_px == 8 {
179            self.encode_block(mi_row, mi_col, bsize_px);
180            self.update_partition_context(mi_row, mi_col, bsize_px, bsize_px);
181            return;
182        }
183
184        let sub_px = bsize_px / 2;
185        // SPLIT into four (OOB recursive calls return immediately).
186        self.encode_partition(mi_row, mi_col, sub_px);
187        self.encode_partition(mi_row, mi_col + mi_half, sub_px);
188        self.encode_partition(mi_row + mi_half, mi_col, sub_px);
189        self.encode_partition(mi_row + mi_half, mi_col + mi_half, sub_px);
190    }
191
192    fn write_partition(
193        &mut self,
194        mi_row: usize,
195        mi_col: usize,
196        bsize_px: u32,
197        has_rows: bool,
198        has_cols: bool,
199        partition: i8,
200    ) {
201        let ctx = self.partition_context(mi_row, mi_col, bsize_px);
202        let probs = &KF_PARTITION_PROBS[ctx];
203        if has_rows && has_cols {
204            write_tree(&mut self.bool, &PARTITION_TREE, probs, partition);
205        } else if !has_rows && has_cols {
206            // false = VERT, true = SPLIT (libvpx).
207            self.bool.put_bool(probs[1], partition == PARTITION_SPLIT);
208        } else if has_rows && !has_cols {
209            self.bool.put_bool(probs[2], partition == PARTITION_SPLIT);
210        }
211        // else: neither half fits → SPLIT forced, no bits (libvpx).
212    }
213
214    fn partition_context(&self, mi_row: usize, mi_col: usize, bsize_px: u32) -> usize {
215        let bsl = bsl_from_px(bsize_px);
216        let above = (self.above_ctx[mi_col] >> bsl) & 1;
217        let left = (self.left_ctx[mi_row & 7] >> bsl) & 1;
218        bsl * 4 + (left as usize) * 2 + above as usize
219    }
220
221    fn update_partition_context(
222        &mut self,
223        mi_row: usize,
224        mi_col: usize,
225        sub_px: u32,
226        bsize_px: u32,
227    ) {
228        let bs = bsize_px as usize / 8;
229        let (above_v, left_v) = PARTITION_CONTEXT_LOOKUP[partition_ctx_index(sub_px)];
230        for i in 0..bs {
231            if mi_col + i < self.mi_cols {
232                self.above_ctx[mi_col + i] = above_v;
233            }
234            self.left_ctx[(mi_row + i) & 7] = left_v;
235        }
236    }
237
238    fn encode_block(&mut self, mi_row: usize, mi_col: usize, bsize_px: u32) {
239        debug_assert_eq!(bsize_px, 8, "residual path encodes 8×8 blocks only");
240        let (px, py) = (mi_col * 8, mi_row * 8);
241        let w = self.src.width as usize;
242        let h = self.src.height as usize;
243        let (cpx, cpy) = (px / 2, py / 2);
244        let cw = w / 2;
245        let ch = h / 2;
246
247        let mi_above = mi_row > 0;
248        let mi_left = mi_col > 0;
249        let above_mode = if mi_above {
250            self.mi[(mi_row - 1) * self.mi_cols + mi_col].mode
251        } else {
252            DC_PRED
253        };
254        let left_mode = if mi_left {
255            self.mi[mi_row * self.mi_cols + (mi_col - 1)].mode
256        } else {
257            DC_PRED
258        };
259
260        // Mode decision on the 8×8 with outer neighbors (one mode for all TXs).
261        let above_y = gather_above(&self.recon_y, w, px, py, 8, mi_above);
262        let left_y = gather_left(&self.recon_y, w, h, px, py, 8, mi_left);
263        let best_y = pick_mode(
264            8,
265            mi_above,
266            mi_left,
267            &above_y,
268            &left_y,
269            &self.src.y[py * w + px..],
270            w,
271        );
272        let y_tx = tx_type_from_mode(best_y);
273
274        let above_u = gather_above(&self.recon_u, cw, cpx, cpy, 4, mi_above);
275        let left_u = gather_left(&self.recon_u, cw, ch, cpx, cpy, 4, mi_left);
276        let above_v = gather_above(&self.recon_v, cw, cpx, cpy, 4, mi_above);
277        let left_v = gather_left(&self.recon_v, cw, ch, cpx, cpy, 4, mi_left);
278        let best_uv = pick_uv_mode(
279            4,
280            mi_above,
281            mi_left,
282            &above_u,
283            &left_u,
284            &above_v,
285            &left_v,
286            &self.src.u[cpy * cw + cpx..],
287            &self.src.v[cpy * cw + cpx..],
288            cw,
289        );
290        // UV plane always uses DCT_DCT transform/scan (libvpx `get_tx_type`).
291        let uv_tx = TxType::DctDct;
292
293        // Pass 1: per-TX predict → hybrid TX → quant.
294        let mut y_q = [[0i32; 16]; 4];
295        let mut y_dq = [[0i32; 16]; 4];
296        let mut any = false;
297        let mut local_y = [0u8; 64];
298
299        for ty in 0..2 {
300            for tx in 0..2 {
301                let ti = ty * 2 + tx;
302                let (have_a, have_l) = (mi_above || ty > 0, mi_left || tx > 0);
303                let (above, left) =
304                    neighbors_y(&self.recon_y, &local_y, w, px, py, tx, ty, have_a, have_l);
305                let mut pred = [0u8; 16];
306                predict(best_y, 4, have_a, have_l, &above, &left, &mut pred);
307                let residual = residual_packed4(&pred, &self.src.y, w, px + tx * 4, py + ty * 4);
308                let mut coeff = [0i32; 16];
309                fht4x4(&residual, &mut coeff, y_tx);
310                let (q, dq) = quantize(&coeff, QINDEX);
311                any |= q.iter().any(|&c| c != 0);
312                y_q[ti] = q;
313                y_dq[ti] = dq;
314                let mut block = pred;
315                iht4x4_add(&dq, &mut block, 4, y_tx);
316                store_local4(&mut local_y, tx, ty, &block);
317            }
318        }
319
320        let (u_q, u_dq) = {
321            let (have_a, have_l) = (mi_above, mi_left);
322            let above = gather_above(&self.recon_u, cw, cpx, cpy, 4, have_a);
323            let left = gather_left(&self.recon_u, cw, ch, cpx, cpy, 4, have_l);
324            let mut pred = [0u8; 16];
325            predict(best_uv, 4, have_a, have_l, &above, &left, &mut pred);
326            let residual = residual_packed4(&pred, &self.src.u, cw, cpx, cpy);
327            let mut coeff = [0i32; 16];
328            fht4x4(&residual, &mut coeff, uv_tx);
329            let (q, dq) = quantize(&coeff, QINDEX);
330            any |= q.iter().any(|&c| c != 0);
331            (q, dq)
332        };
333        let (v_q, v_dq) = {
334            let (have_a, have_l) = (mi_above, mi_left);
335            let above = gather_above(&self.recon_v, cw, cpx, cpy, 4, have_a);
336            let left = gather_left(&self.recon_v, cw, ch, cpx, cpy, 4, have_l);
337            let mut pred = [0u8; 16];
338            predict(best_uv, 4, have_a, have_l, &above, &left, &mut pred);
339            let residual = residual_packed4(&pred, &self.src.v, cw, cpx, cpy);
340            let mut coeff = [0i32; 16];
341            fht4x4(&residual, &mut coeff, uv_tx);
342            let (q, dq) = quantize(&coeff, QINDEX);
343            any |= q.iter().any(|&c| c != 0);
344            (q, dq)
345        };
346
347        let skip = !any;
348        let skip_ctx = self.skip_context(mi_row, mi_col);
349        self.bool.put_bool(DEFAULT_SKIP_PROBS[skip_ctx], skip);
350        write_tree(
351            &mut self.bool,
352            &INTRA_MODE_TREE,
353            &KF_Y_MODE_PROB[above_mode as usize][left_mode as usize],
354            best_y,
355        );
356        write_tree(
357            &mut self.bool,
358            &INTRA_MODE_TREE,
359            &KF_UV_MODE_PROB[best_y as usize],
360            best_uv,
361        );
362
363        // Pass 2: emit tokens (if any) and rebuild recon.
364        for ty in 0..2 {
365            for tx in 0..2 {
366                let ti = ty * 2 + tx;
367                let x = px + tx * 4;
368                let y = py + ty * 4;
369                let (have_a, have_l) = (mi_above || ty > 0, mi_left || tx > 0);
370                let above = gather_above(&self.recon_y, w, x, y, 4, have_a);
371                let left = gather_left(&self.recon_y, w, h, x, y, 4, have_l);
372                let mut pred = [0u8; 16];
373                predict(best_y, 4, have_a, have_l, &above, &left, &mut pred);
374
375                if !skip {
376                    let a = self.above_ent_y[mi_col * 2 + tx];
377                    let l = self.left_ent_y[(mi_row & 7) * 2 + ty];
378                    let ctx = (a != 0) as usize + (l != 0) as usize;
379                    let eob = write_coefs(
380                        &mut self.bool,
381                        &y_q[ti],
382                        true,
383                        false,
384                        ctx,
385                        y_tx,
386                        self.dc_q,
387                        self.ac_q,
388                    );
389                    let has = (eob > 0) as u8;
390                    self.above_ent_y[mi_col * 2 + tx] = has;
391                    self.left_ent_y[(mi_row & 7) * 2 + ty] = has;
392                    iht4x4_add(&y_dq[ti], &mut pred, 4, y_tx);
393                }
394                store_4x4(&mut self.recon_y, w, x, y, &pred);
395            }
396        }
397
398        {
399            let (have_a, have_l) = (mi_above, mi_left);
400            let above = gather_above(&self.recon_u, cw, cpx, cpy, 4, have_a);
401            let left = gather_left(&self.recon_u, cw, ch, cpx, cpy, 4, have_l);
402            let mut pred = [0u8; 16];
403            predict(best_uv, 4, have_a, have_l, &above, &left, &mut pred);
404            if !skip {
405                let a = self.above_ent_u[mi_col];
406                let l = self.left_ent_u[mi_row & 7];
407                let ctx = (a != 0) as usize + (l != 0) as usize;
408                let eob = write_coefs(
409                    &mut self.bool,
410                    &u_q,
411                    false,
412                    false,
413                    ctx,
414                    uv_tx,
415                    self.dc_q,
416                    self.ac_q,
417                );
418                let has = (eob > 0) as u8;
419                self.above_ent_u[mi_col] = has;
420                self.left_ent_u[mi_row & 7] = has;
421                iht4x4_add(&u_dq, &mut pred, 4, uv_tx);
422            }
423            store_4x4(&mut self.recon_u, cw, cpx, cpy, &pred);
424        }
425        {
426            let (have_a, have_l) = (mi_above, mi_left);
427            let above = gather_above(&self.recon_v, cw, cpx, cpy, 4, have_a);
428            let left = gather_left(&self.recon_v, cw, ch, cpx, cpy, 4, have_l);
429            let mut pred = [0u8; 16];
430            predict(best_uv, 4, have_a, have_l, &above, &left, &mut pred);
431            if !skip {
432                let a = self.above_ent_v[mi_col];
433                let l = self.left_ent_v[mi_row & 7];
434                let ctx = (a != 0) as usize + (l != 0) as usize;
435                let eob = write_coefs(
436                    &mut self.bool,
437                    &v_q,
438                    false,
439                    false,
440                    ctx,
441                    uv_tx,
442                    self.dc_q,
443                    self.ac_q,
444                );
445                let has = (eob > 0) as u8;
446                self.above_ent_v[mi_col] = has;
447                self.left_ent_v[mi_row & 7] = has;
448                iht4x4_add(&v_dq, &mut pred, 4, uv_tx);
449            }
450            store_4x4(&mut self.recon_v, cw, cpx, cpy, &pred);
451        }
452
453        if skip {
454            for t in 0..2 {
455                self.above_ent_y[mi_col * 2 + t] = 0;
456                self.left_ent_y[(mi_row & 7) * 2 + t] = 0;
457            }
458            self.above_ent_u[mi_col] = 0;
459            self.left_ent_u[mi_row & 7] = 0;
460            self.above_ent_v[mi_col] = 0;
461            self.left_ent_v[mi_row & 7] = 0;
462        }
463
464        self.mi[mi_row * self.mi_cols + mi_col] = MiInfo { mode: best_y, skip };
465    }
466
467    fn skip_context(&self, mi_row: usize, mi_col: usize) -> usize {
468        let above = if mi_row > 0 {
469            self.mi[(mi_row - 1) * self.mi_cols + mi_col].skip as usize
470        } else {
471            0
472        };
473        let left = if mi_col > 0 {
474            self.mi[mi_row * self.mi_cols + (mi_col - 1)].skip as usize
475        } else {
476            0
477        };
478        above + left
479    }
480}
481
482fn gather_above(plane: &[u8], stride: usize, x: usize, y: usize, bs: usize, have: bool) -> Vec<u8> {
483    let mut above = vec![127u8; bs];
484    if have && y > 0 {
485        let row = &plane[(y - 1) * stride..];
486        for i in 0..bs {
487            above[i] = row[(x + i).min(stride - 1)];
488        }
489    }
490    above
491}
492
493fn gather_left(
494    plane: &[u8],
495    stride: usize,
496    height: usize,
497    x: usize,
498    y: usize,
499    bs: usize,
500    have: bool,
501) -> Vec<u8> {
502    let mut left = vec![129u8; bs];
503    if have && x > 0 {
504        for i in 0..bs {
505            let yy = (y + i).min(height - 1);
506            left[i] = plane[yy * stride + (x - 1)];
507        }
508    }
509    left
510}
511
512/// Above/left for a Y 4×4 inside an 8×8, reading prior TXs from `local` (8×8).
513fn neighbors_y(
514    recon: &[u8],
515    local: &[u8; 64],
516    stride: usize,
517    px: usize,
518    py: usize,
519    tx: usize,
520    ty: usize,
521    have_a: bool,
522    have_l: bool,
523) -> ([u8; 4], [u8; 4]) {
524    let mut above = [127u8; 4];
525    let mut left = [129u8; 4];
526    if have_a {
527        if ty == 0 {
528            if py > 0 {
529                let row = &recon[(py - 1) * stride..];
530                for i in 0..4 {
531                    above[i] = row[px + tx * 4 + i];
532                }
533            }
534        } else {
535            for i in 0..4 {
536                above[i] = local[(ty * 4 - 1) * 8 + tx * 4 + i];
537            }
538        }
539    }
540    if have_l {
541        if tx == 0 {
542            if px > 0 {
543                for i in 0..4 {
544                    left[i] = recon[(py + ty * 4 + i) * stride + (px - 1)];
545                }
546            }
547        } else {
548            for i in 0..4 {
549                left[i] = local[(ty * 4 + i) * 8 + (tx * 4 - 1)];
550            }
551        }
552    }
553    (above, left)
554}
555
556fn store_local4(local: &mut [u8; 64], tx: usize, ty: usize, block: &[u8; 16]) {
557    for r in 0..4 {
558        local[(ty * 4 + r) * 8 + tx * 4..(ty * 4 + r) * 8 + tx * 4 + 4]
559            .copy_from_slice(&block[r * 4..r * 4 + 4]);
560    }
561}
562
563fn store_4x4(plane: &mut [u8], stride: usize, x: usize, y: usize, block: &[u8; 16]) {
564    for r in 0..4 {
565        plane[(y + r) * stride + x..(y + r) * stride + x + 4]
566            .copy_from_slice(&block[r * 4..r * 4 + 4]);
567    }
568}
569
570fn residual_packed4(
571    pred: &[u8; 16],
572    src: &[u8],
573    src_stride: usize,
574    x: usize,
575    y: usize,
576) -> [i16; 16] {
577    let mut r = [0i16; 16];
578    for row in 0..4 {
579        for col in 0..4 {
580            let s = src[(y + row) * src_stride + x + col] as i16;
581            r[row * 4 + col] = s - pred[row * 4 + col] as i16;
582        }
583    }
584    r
585}
586
587fn pick_mode(
588    bs: usize,
589    have_above: bool,
590    have_left: bool,
591    above: &[u8],
592    left: &[u8],
593    src: &[u8],
594    src_stride: usize,
595) -> i8 {
596    let mut best_mode = DC_PRED;
597    let mut best_sad = u32::MAX;
598    for &mode in &PRED_MODES {
599        let mut pred = vec![0u8; bs * bs];
600        predict(mode, bs, have_above, have_left, above, left, &mut pred);
601        let s = sad(src, src_stride, &pred, bs);
602        if s < best_sad {
603            best_sad = s;
604            best_mode = mode;
605        }
606    }
607    best_mode
608}
609
610fn pick_uv_mode(
611    bs: usize,
612    have_above: bool,
613    have_left: bool,
614    above_u: &[u8],
615    left_u: &[u8],
616    above_v: &[u8],
617    left_v: &[u8],
618    src_u: &[u8],
619    src_v: &[u8],
620    stride: usize,
621) -> i8 {
622    let mut best_mode = DC_PRED;
623    let mut best_sad = u32::MAX;
624    for &mode in &PRED_MODES {
625        let mut pu = vec![0u8; bs * bs];
626        let mut pv = vec![0u8; bs * bs];
627        predict(mode, bs, have_above, have_left, above_u, left_u, &mut pu);
628        predict(mode, bs, have_above, have_left, above_v, left_v, &mut pv);
629        let s = sad(src_u, stride, &pu, bs) + sad(src_v, stride, &pv, bs);
630        if s < best_sad {
631            best_sad = s;
632            best_mode = mode;
633        }
634    }
635    best_mode
636}
637
638fn write_tree(e: &mut BoolEncoder, tree: &[i8], probs: &[u8], token: i8) {
639    let path = tree_path(tree, 0, token).expect("token not in tree");
640    for (node, bit) in path {
641        e.put_bool(probs[node >> 1], bit);
642    }
643}
644
645fn tree_path(tree: &[i8], node: usize, token: i8) -> Option<Vec<(usize, bool)>> {
646    for bit in 0..2 {
647        let child = tree[node + bit];
648        if child <= 0 {
649            if -child == token {
650                return Some(vec![(node, bit == 1)]);
651            }
652        } else if let Some(mut rest) = tree_path(tree, child as usize, token) {
653            rest.insert(0, (node, bit == 1));
654            return Some(rest);
655        }
656    }
657    None
658}
659
660fn compressed_header() -> Vec<u8> {
661    let mut e = BoolEncoder::new();
662    e.put_literal(0, 2); // tx_mode = ONLY_4X4
663    e.put_bit(false); // coef update TX_4X4 = 0
664    for _ in 0..3 {
665        e.put_bool(252, false); // skip probs unchanged
666    }
667    e.finish()
668}
669
670fn write_uncompressed_header(w: &mut BitWriter, width: u32, height: u32, header_size: u32) {
671    w.write_bits(2, 2);
672    w.write_bit(0);
673    w.write_bit(0);
674    w.write_bit(0);
675    w.write_bit(0);
676    w.write_bit(1);
677    w.write_bit(0);
678
679    w.write_bits(FRAME_SYNC_CODE, 24);
680    w.write_bits(CS_BT_601, 3);
681    w.write_bit(0);
682
683    w.write_bits(width - 1, 16);
684    w.write_bits(height - 1, 16);
685    w.write_bit(0);
686
687    w.write_bit(0);
688    w.write_bit(1);
689    w.write_bits(0, 2);
690
691    w.write_bits(0, 6);
692    w.write_bits(0, 3);
693    w.write_bit(0);
694
695    w.write_bits(QINDEX as u32, 8); // base_q_idx
696    w.write_bit(0);
697    w.write_bit(0);
698    w.write_bit(0);
699
700    w.write_bit(0);
701
702    write_tile_info(w, width);
703
704    w.write_bits(header_size, 16);
705}
706
707fn write_tile_info(w: &mut BitWriter, width: u32) {
708    // libvpx `vp9_get_tile_n_bits` / `write_tile_info`.
709    const MIN_TILE_WIDTH_SB: u32 = 4;
710    let mi_cols = width / 8;
711    let sb_cols = mi_cols.div_ceil(8);
712    let mut min_log2 = 0u32;
713    while (MAX_TILE_WIDTH_SB << min_log2) < sb_cols {
714        min_log2 += 1;
715    }
716    let mut max_log2 = 1u32;
717    while (sb_cols >> max_log2) >= MIN_TILE_WIDTH_SB {
718        max_log2 += 1;
719    }
720    max_log2 -= 1;
721    // Always use log2_tile_cols = min_log2 (one tile): no leading ones, then a
722    // terminating 0 only when min < max (room to request more columns).
723    if min_log2 < max_log2 {
724        w.write_bit(0);
725    }
726    w.write_bit(0); // tile_rows_log2 = 0
727}
728
729#[cfg(test)]
730mod tests {
731    use super::*;
732
733    #[test]
734    fn busy_frame_uses_directional_modes() {
735        // A strong horizontal ramp should prefer H_PRED over DC for interior blocks.
736        let mut f = Yuv420Frame::new(64, 64);
737        for j in 0..64u32 {
738            for i in 0..64u32 {
739                f.y[(j * 64 + i) as usize] = (i * 4).min(255) as u8;
740            }
741        }
742        let (_, recon) = encode_intra_frame(&f);
743        // Recon should track the ramp better than flat mid-gray.
744        let mut err = 0u64;
745        for (a, b) in f.y.iter().zip(&recon.y) {
746            err += a.abs_diff(*b) as u64;
747        }
748        let flat: u64 = f.y.iter().map(|&x| x.abs_diff(128) as u64).sum();
749        assert!(err < flat / 3, "H-friendly ramp err={err} flat={flat}");
750    }
751
752    #[test]
753    fn gray_frame_recons_to_mid_gray() {
754        let mut f = Yuv420Frame::new(64, 64);
755        f.y.fill(128);
756        f.u.fill(128);
757        f.v.fill(128);
758        let (bits, recon) = encode_intra_frame(&f);
759        assert!(bits.len() > 12);
760        assert!(recon.y.iter().all(|&x| x == 128));
761        assert!(recon.u.iter().all(|&x| x == 128));
762        assert!(recon.v.iter().all(|&x| x == 128));
763    }
764
765    #[test]
766    fn partial_superblock_sizes_encode() {
767        for &(w, h) in &[(8u32, 8), (16, 8), (80, 48), (96, 72), (128, 64)] {
768            let mut f = Yuv420Frame::new(w, h);
769            for j in 0..h {
770                for i in 0..w {
771                    f.y[(j * w + i) as usize] = ((i + j) & 0xFF) as u8;
772                }
773            }
774            let (bits, recon) = encode_intra_frame(&f);
775            assert!(bits.len() > 8, "{w}x{h} bitstream too small");
776            assert_eq!(recon.y.len(), (w * h) as usize);
777            assert_eq!(recon.u.len(), (w * h / 4) as usize);
778        }
779    }
780
781    #[test]
782    fn busy_frame_residual_beats_mid_gray() {
783        let mut f = Yuv420Frame::new(64, 64);
784        for j in 0..64u32 {
785            for i in 0..64u32 {
786                f.y[(j * 64 + i) as usize] = ((i.wrapping_mul(3) ^ j.wrapping_mul(5)) & 0xFF) as u8;
787            }
788        }
789        let (bits, recon) = encode_intra_frame(&f);
790        assert!(
791            bits.len() > 50,
792            "residual bitstream unexpectedly tiny: {}",
793            bits.len()
794        );
795        let mut err = 0u64;
796        for (a, b) in f.y.iter().zip(&recon.y) {
797            err += a.abs_diff(*b) as u64;
798        }
799        let flat: u64 = f.y.iter().map(|&x| x.abs_diff(128) as u64).sum();
800        assert!(
801            err < flat / 2,
802            "residual recon err={err} should beat flat={flat}"
803        );
804        // Recon should use the full sample range, not just {127,128,129}.
805        let min = *recon.y.iter().min().unwrap();
806        let max = *recon.y.iter().max().unwrap();
807        assert!(max - min > 10, "recon range too narrow: {min}..{max}");
808    }
809}