jixel 0.5.13

JPEG XL encoder
Documentation
/*
 * // Copyright (c) Radzivon Bartoshyk 11/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.
 */

//! The merged MA forest: per-tag subtrees under the stream/channel routing
//! skeleton, every leaf stamped with its tag's step as the residual
//! multiplier, and the learning budgets of those subtrees.

use crate::entropy::Token;
use crate::lossless::kit::emit_forest_bfs;
use crate::ma_tree::{LearnedTree, MaNode};

/// Per-tag MA sample budget; more samples plateaued (<=0.6%) in the 2026-09
/// knob sweeps, as did larger leaf budgets and split-candidate counts.
pub(crate) const SAMPLE_TARGET: usize = 1 << 16;

/// Learned-subtree leaf budget: pixels/div, clamped.
pub(crate) const BUDGET_DIV: usize = 1024;

pub(crate) const BUDGET_CAP: usize = 256;

/// Merge the per-tag learned subtrees under the stream/channel routing
/// skeleton and BFS-emit the whole forest, stamping every leaf with its tag's
/// residual multiplier. The skeleton splits on the static stream-id property:
/// 0 = LfGlobal stream, [1+ndc, 2ndc] = DC-group streams, and AC-group
/// streams above both; each side hangs a channel / slot chain. Tags are
/// ordered [global channels][DC slots][AC slots]. Returns the tree tokens,
/// the arena-indexed leaf context table, each tag's arena base, and the
/// context count.
pub(crate) fn emit_forest(
    trees: &[LearnedTree],
    tag_mults: &[u32],
    split: usize,
    n_dc_slots: usize,
    num_dc_groups: usize,
) -> (Vec<Token>, Vec<u32>, Vec<u32>, u32) {
    let n_tags = trees.len();
    let n_ac_slots = n_tags - split - n_dc_slots;
    debug_assert!(split > 0 && (n_ac_slots > 0 || n_dc_slots == 0));
    let mut nodes: Vec<MaNode> = Vec::new();
    let mut mult_of: Vec<u32> = Vec::new();
    let mut tag_base = vec![0u32; n_tags];

    let append_tree = |nodes: &mut Vec<MaNode>, mult_of: &mut Vec<u32>, t: usize| -> u32 {
        let base = nodes.len() as u32;
        for n in &trees[t].nodes {
            nodes.push(match *n {
                MaNode::Split { prop, val, gt, le } => MaNode::Split {
                    prop,
                    val,
                    gt: gt + base,
                    le: le + base,
                },
                leaf @ MaNode::Leaf { .. } => leaf,
            });
            mult_of.push(tag_mults[t]);
        }
        base
    };
    // Per-side chains over property 0 (the decoder-visible channel value:
    // channel index in the global stream, within-group slot in group streams).
    let build_chain = |nodes: &mut Vec<MaNode>,
                       mult_of: &mut Vec<u32>,
                       tag_base: &mut [u32],
                       lo: usize,
                       n: usize|
     -> u32 {
        let base0 = append_tree(nodes, mult_of, lo);
        tag_base[lo] = base0;
        let mut acc = base0;
        for k in 1..n {
            let sub = append_tree(nodes, mult_of, lo + k);
            tag_base[lo + k] = sub;
            nodes.push(MaNode::Split {
                prop: 0,
                val: (k - 1) as i32,
                gt: sub,
                le: acc,
            });
            mult_of.push(1);
            acc = (nodes.len() - 1) as u32;
        }
        acc
    };
    let global_root = build_chain(&mut nodes, &mut mult_of, &mut tag_base, 0, split);
    if n_ac_slots == 0 {
        // Single-group frame: everything lives in the global stream.
        return emit_forest_bfs(&nodes, &mult_of, global_root, tag_base);
    }
    let ac_root = build_chain(
        &mut nodes,
        &mut mult_of,
        &mut tag_base,
        split + n_dc_slots,
        n_ac_slots,
    );
    let low_root = if n_dc_slots > 0 {
        // DC streams exist: separate them from the global stream below the
        // AC threshold.
        let dc_root = build_chain(&mut nodes, &mut mult_of, &mut tag_base, split, n_dc_slots);
        nodes.push(MaNode::Split {
            prop: 1,
            val: 0,
            gt: dc_root,
            le: global_root,
        });
        mult_of.push(1);
        (nodes.len() - 1) as u32
    } else {
        global_root
    };
    // AC stream ids start at 1 + 3*ndc + kNumQuantTables, always above
    // 2*ndc; global (0) and DC ([1+ndc, 2ndc]) stay at or below it.
    nodes.push(MaNode::Split {
        prop: 1,
        val: (2 * num_dc_groups) as i32,
        gt: ac_root,
        le: low_root,
    });
    mult_of.push(1);
    let root = (nodes.len() - 1) as u32;
    emit_forest_bfs(&nodes, &mult_of, root, tag_base)
}