Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
/*
 * // Copyright (c) Radzivon Bartoshyk 5/2026. All rights reserved.
 * //
 * // Redistribution and use in source and binary forms, with or without modification,
 * // are permitted provided that the following conditions are met:
 * //
 * // 1.  Redistributions of source code must retain the above copyright notice, this
 * // list of conditions and the following disclaimer.
 * //
 * // 2.  Redistributions in binary form must reproduce the above copyright notice,
 * // this list of conditions and the following disclaimer in the documentation
 * // and/or other materials provided with the distribution.
 * //
 * // 3.  Neither the name of the copyright holder nor the names of its
 * // contributors may be used to endorse or promote products derived from
 * // this software without specific prior written permission.
 * //
 * // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

//! Lossy modular coding: an image, or one extra channel, as a quantized
//! Squeeze pyramid in modular streams instead of VarDCT.
//!
//! A lossy modular frame runs these stages, one module each:
//!
//! 1. [`calibrate`]: map the caller's distance to this arm's quantizer
//!    distance, so the modular and VarDCT arms land near the same quality.
//! 2. [`pyramid`]: put the source planes on the frame's integer [`layout`]
//!    (the XYB lattice, or the samples themselves through YCoCg), run the
//!    forward Squeeze, and divide every channel by its [`quantize`] step.
//!    At ExtraSlow, `polish` then revisits the XYB frame's luma and chroma residuals
//!    against the exact SSIMULACRA2 and ColorVideoVDP arbiters.
//! 3. [`fold`]: screen folding the pyramid's exact coarse tail back into
//!    full-scale averages: the same decoded image, another entropy
//!    representation.
//! 4. [`race`]: code the pyramid, and the screen's fold when it found one;
//!    keep the smaller frame.
//! 5. [`code`]: code one pyramid as a complete frame. A single-group frame is
//!    one section ([`single`]). Otherwise [`tags`] assigns every channel crop
//!    to a stream slot, [`trees`] learns one MA subtree per tag, [`forest`]
//!    merges them under the global tree, [`tokens`] tokenizes every stream
//!    and [`write`] emits the sections and TOC. [`cache`] carries unchanged
//!    trees and tokens from one race candidate to the next.
//!
//! [`alpha`] codes a lossy extra channel inside a VarDCT frame with the same
//! squeeze, quantizer and forest.

mod alpha;
#[cfg(test)]
mod alpha_tests;
mod cache;
mod calibrate;
mod closed_loop;
mod code;
mod fold;
mod forest;
mod layout;
#[cfg(feature = "extraslow")]
mod polish;
mod pyramid;
#[cfg(test)]
mod pyramid_tests;
mod quantize;
mod race;
mod single;
mod tags;
mod tokens;
mod trees;
mod write;

pub(crate) use alpha::ExtraSqueeze;
pub(crate) use calibrate::{calibrated_distance, plain_distance};
pub(crate) use pyramid::PlainInput;

use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::entropy::f_log2;
use crate::image::Image3F;
use crate::shared_sort::SharedSort;
use crate::thread_pool::ThreadPool;
use pyramid::Pyramid;

/// Lossy modular frame of an XYB codestream. `distance` is the arm's
/// calibrated quantizer distance ([`calibrated_distance`] and the Auto gate)
/// and `screen` whether the image is screen content (its step rows);
/// `patches` are dictionary entries over an atlas frame the caller has
/// already written.
/// Returns the frame size in bits before the fold race, for the Auto gate,
/// or None when the image is too small to squeeze.
#[allow(clippy::too_many_arguments)]
pub(crate) fn encode_xyb_frame(
    xyb: &Image3F,
    distance: f32,
    screen: bool,
    vertical_first: bool,
    patches: &[crate::patches::PatchReference],
    speed: crate::Speed,
    pool: &ThreadPool,
    scratch: &mut CoderScratch,
    writer: &mut BitWriter,
) -> Option<usize> {
    let mut pyramid = Pyramid::xyb(xyb, distance, screen, vertical_first, pool)?;
    pyramid.patches = patches.to_vec();
    pyramid.group_shift = group_shift(speed);
    #[cfg(feature = "extraslow")]
    if speed.effort().lm_residual_polish() {
        polish::polish_frame(
            &mut pyramid,
            xyb,
            distance,
            screen,
            vertical_first,
            pool,
            scratch,
        );
    }
    race::encode(pyramid, speed, pool, scratch, writer)
}

/// Lossy modular crop frame of an XYB codestream: `xyb` is the rectangle at
/// `origin`, coded like [`encode_xyb_frame`] (no patches) and replacing
/// reference slot 0 there. None when the rectangle is too small to squeeze.
#[allow(clippy::too_many_arguments)]
pub(crate) fn encode_xyb_crop_frame(
    xyb: &Image3F,
    distance: f32,
    screen: bool,
    origin: [usize; 2],
    last: bool,
    speed: crate::Speed,
    pool: &ThreadPool,
    scratch: &mut CoderScratch,
    writer: &mut BitWriter,
) -> Option<usize> {
    let mut pyramid = Pyramid::xyb(xyb, distance, screen, false, pool)?;
    pyramid.group_shift = group_shift(speed);
    pyramid.crop = Some((origin, last));
    race::encode(pyramid, speed, pool, scratch, writer)
}

/// Lossy modular frame of a non-XYB codestream: the integer planes in
/// `input` at the plain-layout schedule ([`plain_distance`]). Returns the
/// frame size in bits before the fold race, for the Auto gate, or None when
/// the image is too small to squeeze. `black_plate` says the extra channel is
/// CMYK's K, stored inverted, whose no-ink value a lossy palette must keep.
#[allow(clippy::too_many_arguments)]
pub(crate) fn encode_plain_frame(
    input: &PlainInput,
    xsize: usize,
    ysize: usize,
    distance: f32,
    black_plate: bool,
    speed: crate::Speed,
    pool: &ThreadPool,
    scratch: &mut CoderScratch,
    writer: &mut BitWriter,
) -> Option<usize> {
    // A lossless extra channel (alpha, say) codes the same samples squeezed
    // or not: unsqueezed wins on cutouts and stickers (to -27 %), the squeeze
    // on smooth fades (one vignette +7..+14 % without it). The color pyramid
    // is the same either way, so from Slow the extras alone decide, coded
    // under an all-zero gray plane at Fastest (crops and tile samples break
    // the fades and pick wrong); faster tiers take unsqueezed, -9.7 % over
    // eight RGBA images and quicker to code.
    let unsqueeze = input.extra.last().is_some_and(|&(_, d)| d == 0.0)
        && (speed < crate::Speed::Slow || {
            let probe = PlainInput {
                color: vec![vec![0; xsize * ysize]],
                extra: input.extra.clone(),
                max: input.max,
                coding: input.coding,
            };
            let bits = |unsqueeze: bool, scratch: &mut CoderScratch| {
                let pyramid = Pyramid::plain(&probe, xsize, ysize, distance, unsqueeze, pool)?;
                let mut w = BitWriter::new();
                code::write_frame(&pyramid, crate::Speed::Fastest, pool, scratch, &mut w, None);
                Some(w.bits_written())
            };
            match (bits(false, scratch), bits(true, scratch)) {
                (Some(squeezed), Some(plain)) => plain < squeezed,
                _ => false,
            }
        });
    let mut pyramid = Pyramid::plain(input, xsize, ysize, distance, unsqueeze, pool)?;
    pyramid.group_shift = group_shift(speed);
    // From Slow, a lossy extra channel (alpha) also races as a lossy
    // palette, decided by estimated rates: order-0 context entropy of the
    // squeezed channel and of the palette indices. Calibrated against the
    // full double encode over 32 RGBA images x 5 distances: 8/160 choices
    // differ, all near ties (+0.05 % bytes); probe encodes of the extras
    // cost 1.69x the arm-free frame, the estimate 1.18x.
    let Some(levels) = (speed >= crate::Speed::Slow)
        .then(|| lossy_palette_levels(input, &pyramid, xsize, ysize, black_plate))
        .flatten()
    else {
        return race::encode(pyramid, speed, pool, scratch, writer);
    };
    let palette_bits = palette_index_bits(&levels, xsize, ysize);
    let take =
        palette_bits < PALETTE_RATE_MARGIN * squeezed_extra_bits(&pyramid, input.color.len());
    let tiled = repeated_share(&input.extra[0].0, xsize) > TILED_SHARE;
    if !take && !tiled {
        return race::encode(pyramid, speed, pool, scratch, writer);
    }
    let levels = PlainInput {
        color: input.color.clone(),
        extra: vec![(levels, 0.0)],
        max: input.max,
        coding: input.coding,
    };
    let Some(mut palette) = Pyramid::plain_palette(&levels, xsize, ysize, distance, pool) else {
        return race::encode(pyramid, speed, pool, scratch, writer);
    };
    palette.group_shift = pyramid.group_shift;
    if !tiled {
        return race::encode(palette, speed, pool, scratch, writer);
    }
    let mut squeezed = writer.clone();
    let squeezed_bits = race::encode(pyramid, speed, pool, scratch, &mut squeezed);
    let palette_bits = race::encode(palette, speed, pool, scratch, writer);
    if squeezed.bits_written() < writer.bits_written() {
        *writer = squeezed;
        return squeezed_bits;
    }
    palette_bits
}

/// Tiled alpha races both codings exactly instead: LZ77 copies its repeats,
/// which neither order-0 estimate sees, so either coding can win by 2-4x (a
/// tiled background at 8 to 16 bits, both ways). Over 18 deep and 18 8-bit
/// RGBA images the tile's [`repeated_share`] is 0.79-0.93 and the next 0.71;
/// a race taken in vain only costs time.
const TILED_SHARE: f64 = 0.75;

/// Share of the plane's samples in non-constant 16-sample windows (raster
/// order) that LZ77 could copy from more than two rows back in runs of at
/// least 128. Nearer repeats (a straight edge continuing) and short ones
/// (antialiased edges alike) are the estimates' contexts' to see.
fn repeated_share(plane: &[i32], xsize: usize) -> f64 {
    const WINDOW: usize = 16;
    const MIN_RUN: usize = 128;
    const HASH_BITS: u32 = 18;
    let hash = |w: &[i32]| {
        let h = w.iter().fold(0xcbf2_9ce4_8422_2325u64, |h, &v| {
            (h ^ u64::from(v as u32)).wrapping_mul(0x0100_0000_01b3)
        });
        (h >> (64 - HASH_BITS)) as usize
    };
    let mut last = vec![u32::MAX; 1 << HASH_BITS];
    let (mut varied, mut repeated) = (0usize, 0usize);
    let mut i = 0;
    while i + WINDOW <= plane.len() {
        let w = &plane[i..i + WINDOW];
        if w.iter().all(|&v| v == w[0]) {
            i += 1;
            continue;
        }
        let h = hash(w);
        let j = last[h] as usize;
        last[h] = i as u32;
        if j < i && plane[j..j + WINDOW] == *w {
            let mut run = WINDOW;
            while i + run < plane.len() && plane[j + run] == plane[i + run] {
                run += 1;
            }
            varied += run;
            if run >= MIN_RUN && i - j > 2 * xsize {
                repeated += run;
            }
            i += run;
        } else {
            varied += 1;
            i += 1;
        }
    }
    if varied == 0 {
        0.0
    } else {
        repeated as f64 / varied as f64
    }
}

/// The palette is taken while its estimated index bits stay under this many
/// times the squeezed channel's: the estimate rates the indices about 1.45x
/// their learned-tree coding relative to the squeeze's.
const PALETTE_RATE_MARGIN: f64 = 1.45;

/// Hybrid-uint token and raw bits of a packed residual (split exponent 4,
/// one mantissa bit), as the frame's entropy code splits it.
fn residual_token(e: u32) -> (u32, u32) {
    if e < 16 {
        (e, 0)
    } else {
        let n = 31 - e.leading_zeros();
        (16 + (n - 4) * 2 + ((e >> (n - 1)) & 1), n - 1)
    }
}

/// Order-0 bits of `(context, residual)` samples: per-context token entropy,
/// raw bits and a small table cost per context.
fn context_entropy_bits(samples: impl Iterator<Item = (usize, i32)>, contexts: usize) -> f64 {
    let mut hist = vec![std::collections::HashMap::<u32, u32>::new(); contexts];
    let mut bits = 0f64;
    for (c, v) in samples {
        let (token, raw) = residual_token(crate::entropy::pack_signed(v));
        *hist[c].entry(token).or_default() += 1;
        bits += f64::from(raw);
    }
    for h in &hist {
        let n: u32 = h.values().sum();
        if n == 0 {
            continue;
        }
        bits += 12.0 + 6.0 * h.len() as f64;
        for &k in h.values() {
            bits -= f64::from(k) * f_log2(f64::from(k) / f64::from(n));
        }
    }
    bits
}

/// The decoder's left, top and top-left neighbors of `(x, y)` in a plane.
fn neighbors<T: Copy + Default>(data: &[T], w: usize, x: usize, y: usize) -> (T, T, T) {
    let left = if x > 0 {
        data[y * w + x - 1]
    } else if y > 0 {
        data[(y - 1) * w + x]
    } else {
        T::default()
    };
    let top = if y > 0 { data[(y - 1) * w + x] } else { left };
    let top_left = if x > 0 && y > 0 {
        data[(y - 1) * w + x - 1]
    } else {
        left
    };
    (left, top, top_left)
}

/// Estimated bits of a plain pyramid's one squeezed extra channel (the last
/// squeezed plane): its coarsest channel through the clamped gradient, its
/// residual channels as stored under |W| > 0 / |N| > 0 contexts, like the
/// fixed extra-channel context tree.
fn squeezed_extra_bits(p: &Pyramid, num_color: usize) -> f64 {
    let planes = num_color + 1;
    let n_pre: usize = p
        .steps
        .iter()
        .filter(|s| !s.in_place)
        .map(|s| s.num_c)
        .sum();
    let channels = &p.channels[..p.channels.len() - n_pre];
    let samples = channels
        .iter()
        .enumerate()
        .filter(|&(i, _)| i % planes == num_color)
        .flat_map(|(i, ch)| {
            (0..ch.w * ch.h).map(move |k| {
                let (x, y) = (k % ch.w, k / ch.w);
                let (left, top, top_left) = neighbors(&ch.data, ch.w, x, y);
                let v = ch.data[k];
                if i < planes {
                    let pred = (left + top - top_left).clamp(left.min(top), left.max(top));
                    (4, v - pred)
                } else {
                    (usize::from(left != 0) * 2 + usize::from(top != 0), v)
                }
            })
        });
    context_entropy_bits(samples, 5)
}

/// Estimated bits of the palette indices of `levels`: each index against
/// its left neighbor under W == N / N == NW contexts.
pub(crate) fn palette_index_bits(levels: &[i32], xsize: usize, ysize: usize) -> f64 {
    let mut entries = levels.to_vec();
    entries.shared_sort();
    entries.dedup();
    let indices: Vec<i32> = levels
        .iter()
        .map(|v| entries.binary_search(v).unwrap_or(0) as i32)
        .collect();
    palette_rank_bits(&indices, xsize, ysize, |index| index)
}

/// The same estimate for a byte plane, whose sorted palette ranks fit a LUT.
pub(crate) fn palette_index_bits_u8(levels: &[u8], xsize: usize, ysize: usize) -> f64 {
    let mut seen = [false; 256];
    for &level in levels {
        seen[usize::from(level)] = true;
    }
    let mut ranks = [0u8; 256];
    for (rank, level) in (0..seen.len()).filter(|&level| seen[level]).enumerate() {
        ranks[level] = rank as u8;
    }
    palette_rank_bits(levels, xsize, ysize, |level| {
        i32::from(ranks[usize::from(level)])
    })
}

fn palette_rank_bits<T: Copy + Default>(
    levels: &[T],
    xsize: usize,
    ysize: usize,
    rank: impl Fn(T) -> i32,
) -> f64 {
    let samples = (0..xsize * ysize).map(|k| {
        let (left, top, top_left) = neighbors(levels, xsize, k % xsize, k / xsize);
        let (left, top, top_left) = (rank(left), rank(top), rank(top_left));
        (
            usize::from(left == top) * 2 + usize::from(top == top_left),
            rank(levels[k]) - left,
        )
    });
    context_entropy_bits(samples, 4)
}

/// The lossy palette levels of a plain frame's one lossy extra channel
/// (alpha): the fewest levels within part of the squeezed channel's weighted
/// error ([`crate::frame::extra_levels`]), to code losslessly through a
/// Palette transform. None without such a channel, or when every value is
/// needed. A `black_plate` keeps its no-ink value (the full one) exact.
fn lossy_palette_levels(
    input: &PlainInput,
    squeezed: &Pyramid,
    xsize: usize,
    ysize: usize,
    black_plate: bool,
) -> Option<Vec<i32>> {
    use crate::encode_image::AlphaPlane;
    use crate::frame::extra_levels::{error_weights, fewest_levels, squeeze_budget};
    let [(plane, d)] = input.extra.as_slice() else {
        return None;
    };
    if *d <= 0.0 || plane.iter().any(|&v| !(0..=65535).contains(&v)) {
        return None;
    }
    let source = AlphaPlane::U16 {
        data: plane.iter().map(|&v| v as u16).collect(),
        bits: 16,
    };
    let weights = error_weights(&source, xsize, ysize);
    let budget = squeeze_budget(&source, &squeezed.decoded_extra(0), &weights);
    let AlphaPlane::U16 { data, .. } = fewest_levels(&source, &weights, budget, black_plate)?
    else {
        unreachable!("levels keep the plane's type")
    };
    Some(data.into_iter().map(i32::from).collect())
}

/// The group_size_shift of a regular frame. From Slow, 1024-pixel groups:
/// every group edge costs its first row and column their neighbors, so
/// larger groups code the same pixels in -1.3 % (Slow) / -1.5 % (Fast) over
/// 54 forced encodes, to -4.6 %. They cost 18-24 % encode time at 8
/// threads and the decoder's group parallelism, so faster tiers keep 256.
fn group_shift(speed: crate::Speed) -> u32 {
    if speed >= crate::Speed::Slow {
        crate::lossless::kit::GroupLayout::LARGE.shift
    } else {
        crate::lossless::kit::GroupLayout::DEFAULT.shift
    }
}

/// Progressive DC: the 1:8 DC image of a VarDCT frame as its squeezed DC
/// frame (frame type kDCFrame, dc_level 1), which the VarDCT frame then
/// references instead of coding its own DC. Full-resolution chroma, no loop
/// filters. `levels` keeps that many of the finest squeeze levels (clamped
/// to at least one; `None` squeezes down to the 8x8 preview). Returns false
/// when the image is too small to squeeze.
pub(crate) fn encode_dc_frame(
    dc: &Image3F,
    vardct_steps: [f32; 3],
    levels: Option<u32>,
    speed: crate::Speed,
    pool: &ThreadPool,
    scratch: &mut CoderScratch,
    writer: &mut BitWriter,
) -> bool {
    match Pyramid::dc_frame(dc, vardct_steps, levels, pool) {
        Some(pyramid) => race::encode(pyramid, speed, pool, scratch, writer).is_some(),
        None => false,
    }
}

/// Whether [`encode_dc_frame`] can code a DC image of this size.
pub(crate) fn dc_frame_supported(xsize: usize, ysize: usize) -> bool {
    !crate::squeeze::default_squeeze_steps(xsize, ysize, 3).is_empty()
}