jixel 0.5.10

JPEG XL encoder
Documentation
/*
 * // 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.
 */
//! Bit estimate of AC token streams under a built entropy code (the plain
//! per-pass code): the pricing both the AC context-plan arms and the
//! rate-model reconciliation log rely on.

use crate::adaptive_quant::dirty_log2f;
use crate::entropy::{ALPHABET_SIZE, OwnedEntropyCode, TokenSlice};
use crate::thread_pool::ThreadPool;

/// Price of a symbol the code never saw or cannot express: the estimate
/// stays finite and the caller's exact coding decides.
const UNSEEN_ANS_BITS: f32 = crate::entropy::ANS_LOG_TAB_SIZE as f32;
const UNSEEN_PREFIX_BITS: u8 = 15;

pub(crate) fn estimate_ac_plain_bits<'a, I>(streams: I, code: &OwnedEntropyCode) -> u64
where
    I: IntoIterator,
    I::Item: Into<TokenSlice<'a>>,
{
    estimate_ac_plain_bits_shared(&mut streams.into_iter().map(Into::into), code)
}

// Dispatch once per stream; keep the cost table and token loops shared.
fn estimate_ac_plain_bits_shared(
    streams: &mut dyn Iterator<Item = TokenSlice<'_>>,
    code: &OwnedEntropyCode,
) -> u64 {
    if !code.use_prefix_code {
        // rANS approaches the histogram entropy: a symbol with normalized
        // frequency `f` out of `ANS_TAB_SIZE` costs -log2(f / ANS_TAB_SIZE).
        let cost: Vec<Vec<f32>> = code
            .ans_histograms
            .iter()
            .map(|histogram| {
                histogram
                    .freqs
                    .iter()
                    .map(|&f| {
                        if f == 0 {
                            UNSEEN_ANS_BITS
                        } else {
                            crate::entropy::ANS_LOG_TAB_SIZE as f32 - dirty_log2f(f as f32)
                        }
                    })
                    .collect()
            })
            .collect();
        let mut bits = 0.0f64;
        for tokens in streams {
            // Every stream carries its 32-bit state, empty or not.
            bits += 32.0;
            tokens.iter().for_each(|t| {
                let cl = code.context_map[t.context as usize] as usize;
                let (sym, nbits, _) =
                    crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
                // A token priced under another stream's code can need a
                // symbol past its alphabet; it pays the unseen-symbol price.
                let symbol_bits = cost[cl]
                    .get(sym as usize)
                    .copied()
                    .unwrap_or(UNSEEN_ANS_BITS);
                bits += symbol_bits as f64 + nbits as f64;
            });
        }
        return bits as u64;
    }
    let mut bits: u64 = 0;
    for tokens in streams {
        tokens.iter().for_each(|t| {
            let cl = code.context_map[t.context as usize] as usize;
            let (sym, nbits, _) =
                crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
            // A single-symbol code's codeword is empty.
            let prefix = &code.prefix_codes[cl];
            let depth = if prefix.single_symbol {
                0
            } else {
                prefix
                    .depths
                    .get(sym as usize)
                    .copied()
                    .unwrap_or(UNSEEN_PREFIX_BITS)
            };
            bits += depth as u64 + nbits as u64;
        });
    }
    bits
}

/// `estimate_ac_plain_bits` with the streams counted on the pool: a prefix
/// code's bits are integers and sum in any order; the rANS price is the
/// per-cluster symbol counts (integers, merged in stream order) times the
/// cost table, one f64 term per (cluster, symbol) instead of one per token.
/// That reorders the serial token-order sum by about 1e-6 bit, which the
/// truncation to whole bits practically never sees (0 of 60 encodes changed
/// a byte); the result is the same at any thread count.
pub(crate) fn estimate_ac_plain_bits_pooled(
    streams: &[TokenSlice<'_>],
    code: &OwnedEntropyCode,
    pool: Option<&ThreadPool>,
) -> u64 {
    fn map<T: Send>(
        pool: Option<&ThreadPool>,
        len: usize,
        f: impl Fn(usize) -> T + Sync,
    ) -> Vec<T> {
        match pool {
            Some(pool) => pool.map(len, f),
            None => (0..len).map(f).collect(),
        }
    }
    if code.use_prefix_code {
        return map(pool, streams.len(), |i| {
            let mut bits = 0u64;
            streams[i].iter().for_each(|t| {
                let cl = code.context_map[t.context as usize] as usize;
                let (sym, nbits, _) =
                    crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
                let prefix = &code.prefix_codes[cl];
                let depth = if prefix.single_symbol {
                    0
                } else {
                    prefix
                        .depths
                        .get(sym as usize)
                        .copied()
                        .unwrap_or(UNSEEN_PREFIX_BITS)
                };
                bits += depth as u64 + nbits as u64;
            });
            bits
        })
        .into_iter()
        .sum();
    }
    let num_clusters = code.ans_histograms.len();
    let counted = map(pool, streams.len(), |i| {
        let mut counts = vec![0u32; num_clusters * ALPHABET_SIZE];
        let mut raw_bits = 0u64;
        streams[i].iter().for_each(|t| {
            let cl = code.context_map[t.context as usize] as usize;
            let (sym, nbits, _) =
                crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
            if (sym as usize) < ALPHABET_SIZE {
                counts[cl * ALPHABET_SIZE + sym as usize] += 1;
            } else {
                raw_bits += UNSEEN_ANS_BITS as u64;
            }
            raw_bits += u64::from(nbits);
        });
        (counts, raw_bits)
    });
    let mut counts = vec![0u64; num_clusters * ALPHABET_SIZE];
    let mut raw_bits = 0u64;
    for (stream_counts, stream_raw_bits) in counted {
        for (total, count) in counts.iter_mut().zip(stream_counts) {
            *total += u64::from(count);
        }
        raw_bits += stream_raw_bits;
    }
    // Every stream carries its 32-bit state, empty or not.
    let mut bits = 32.0 * streams.len() as f64;
    for (cl, histogram) in code.ans_histograms.iter().enumerate() {
        for (sym, &f) in histogram.freqs.iter().enumerate() {
            let count = counts[cl * ALPHABET_SIZE + sym];
            if count == 0 {
                continue;
            }
            let cost = if f == 0 {
                crate::entropy::ANS_LOG_TAB_SIZE as f32
            } else {
                crate::entropy::ANS_LOG_TAB_SIZE as f32 - dirty_log2f(f as f32)
            };
            bits += count as f64 * cost as f64;
        }
    }
    bits += raw_bits as f64;
    bits as u64
}

#[cfg(test)]
mod tests {
    use super::estimate_ac_plain_bits;
    use crate::ac_context::K_NUM_AC_CONTEXTS;
    use crate::entropy::{Token, optimize_entropy_code_ac};

    /// A skewed AC stream is coded with rANS, which beats the Huffman floor of
    /// 1 bit/symbol. The plain estimate must reflect that, otherwise the LZ77
    /// comparison in `enc_frame` sees an inflated plain cost and switches to a
    /// prefix-coded LZ77 bundle that is actually larger.
    #[test]
    fn plain_estimate_prices_the_ans_path_below_the_huffman_floor() {
        // 99% zeros in one context: entropy is ~0.08 bit/symbol, Huffman 1.0.
        let tokens: Vec<Token> = (0..20_000)
            .map(|i| Token {
                context: 0,
                value: u32::from(i % 100 == 0),
            })
            .collect();
        let mut scratch = crate::coder_scratch::CoderScratch::default();
        let code = optimize_entropy_code_ac(&tokens, K_NUM_AC_CONTEXTS, &mut scratch.huffman_pool);
        assert!(
            !code.use_prefix_code,
            "expected the rANS path for this stream"
        );

        let estimate = estimate_ac_plain_bits(std::iter::once(tokens.as_slice()), &code);
        let huffman_floor = tokens.len() as u64;
        assert!(
            estimate < huffman_floor / 2,
            "ANS estimate {estimate} should be far below the {huffman_floor}-bit Huffman floor"
        );
    }
}