#[path = "lossless_lz77.rs"]
mod lz77;
#[path = "lossless_ma_lookup.rs"]
mod ma_lookup;
#[path = "lossless_palette.rs"]
mod palette;
#[path = "lossless_predictor.rs"]
mod predictor;
#[path = "lossless_rct.rs"]
mod rct;
#[path = "lossless_squeeze.rs"]
mod squeeze;
#[path = "lossless_tokens.rs"]
mod tokens;
use ma_lookup::MaLookup;
use tokens::{RawTokenStreams, RawTokens};
use crate::bit_writer::BitWriter;
use crate::coder_scratch::{CoderScratch, LZ77_MAX_CONTEXTS};
use crate::encode_image::AlphaPlane;
use crate::entropy::{
OwnedEntropyCode, Token, optimize_entropy_code, pack_signed, uint_encode, write_entropy_code,
write_token,
};
use crate::image::Image3Si;
use crate::ma_tree::{
LearnedTree, MA_REF_CHANNELS, MaLearnParams, MaNode, MaSamples, NUM_MA_PREDS, NUM_MA_PROPS,
deepen_ma_tree, learn_ma_tree, learn_ma_tree_in_place, learn_ma_tree_indexed,
};
use crate::patches::{
ModularFrameKind, NUM_PATCH_CONTEXTS, PATCH_REF_ID, PatchReference, find_lossless_patches,
};
use crate::thread_pool::ThreadPool;
use crate::weighted_predictor::{WpNeighbors, WpParams, WpState, write_wp_header};
use crate::xyb::quantize_xyb_channels;
pub(crate) use lz77::LzToken;
use lz77::{
LZ77_MIN_SYMBOL, RunLzWriter, build_lz_pixel_code, build_lz_pixel_code_threads,
estimate_coded_bits, estimate_literal_and_run_bits, estimate_literal_and_run_bits_single,
estimate_streams_bits, lz77_compress_channels_for_speed,
lz77_compress_channels_for_speed_with_depth, lz77_compress_for_speed,
lz77_compress_for_speed_with_depth, lz77_run_count, write_local_tree_lz77, write_lz_section,
write_tree_lz77,
};
use palette::{
PALETTE_COARSE_MARGIN, PALETTE_FINAL_MARGIN, build_global_palette,
try_encode_local_palette_multi_group, try_encode_palette_single_group, write_palette_transform,
};
pub(crate) use predictor::{GradPackInteriorFn, GradientScratch, selected_grad_pack_interior_fn};
use predictor::{
PREDICTOR_GRADIENT, PREDICTOR_WEIGHTED, PredictorNeighbors, channel_to_context,
choose_predictor_for_plane, choose_predictors_with_wp, choose_wp_params, fixed_predictor,
predictor_neighbors, predictor_value, tokenize_all, tokenize_channels_with_wp, tokenize_plane,
tokenize_plane_rows, tokenize_runs_with_wp,
};
pub(crate) use rct::forward_ycocg;
use rct::{rank_rcts, rct_planes as rct_planes_fn, write_rct_transform};
pub(crate) use squeeze::{encode_frame_lossy_modular_squeeze, lm_calibrated_distance};
use squeeze::{encode_squeeze_multigroup, encode_squeeze_single_group};
use std::sync::{Condvar, Mutex, OnceLock};
const TREE_CTX_SPLIT_VAL: u32 = 0;
const TREE_CTX_PROPERTY: u32 = 1;
const TREE_CTX_PREDICTOR: u32 = 2;
const TREE_CTX_OFFSET: u32 = 3;
const TREE_CTX_MULTIPLIER_LOG: u32 = 4;
const TREE_CTX_MULTIPLIER_BITS: u32 = 5;
const NUM_TREE_CONTEXTS: usize = 6;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct GroupLayout {
shift: u32,
}
impl GroupLayout {
pub(crate) const DEFAULT: Self = Self { shift: 1 };
pub(crate) const LARGE: Self = Self { shift: 3 };
pub(crate) const fn dim(self) -> usize {
128 << self.shift
}
pub(crate) const fn lf_dim(self) -> usize {
self.dim() * 8
}
}
const GROUP_DIM: usize = GroupLayout::DEFAULT.dim();
const LF_GROUP_DIM: usize = GroupLayout::DEFAULT.lf_dim();
const SLOW_DEEP_LZ_MAX_THREADS: usize = 8;
const MA_DECISIVE_MIN_SAVINGS: f64 = 0.18;
const MA_ALTERNATIVES_MIN_SAVINGS: f64 = 0.05;
#[inline]
fn learned_tree_is_decisive(estimated_savings: f64) -> bool {
estimated_savings >= MA_DECISIVE_MIN_SAVINGS
}
#[inline]
fn group_lz_threads(speed: crate::Speed, pool: &ThreadPool) -> usize {
if speed == crate::Speed::Slow {
pool.num_threads().min(SLOW_DEEP_LZ_MAX_THREADS)
} else {
pool.num_threads()
}
}
struct DeepLzScratchPool {
available: Mutex<Vec<Vec<u32>>>,
activity: Condvar,
}
impl DeepLzScratchPool {
fn new(slots: usize) -> Self {
Self {
available: Mutex::new((0..slots.max(1)).map(|_| Vec::new()).collect()),
activity: Condvar::new(),
}
}
fn with_depth<T>(&self, f: impl FnOnce(&mut Vec<u32>) -> T) -> T {
let mut guard = self.acquire();
f(guard.depth.as_mut().unwrap())
}
fn acquire(&self) -> DeepLzScratchGuard<'_> {
let depth = {
let mut available = self.available.lock().unwrap();
while available.is_empty() {
available = self.activity.wait(available).unwrap();
}
available.pop().unwrap()
};
DeepLzScratchGuard {
owner: self,
depth: Some(depth),
}
}
}
struct DeepLzScratchGuard<'a> {
owner: &'a DeepLzScratchPool,
depth: Option<Vec<u32>>,
}
impl Drop for DeepLzScratchGuard<'_> {
fn drop(&mut self) {
let depth = self.depth.take().unwrap();
self.owner.available.lock().unwrap().push(depth);
self.owner.activity.notify_one();
}
}
fn zero_alpha_like(alpha: Option<&AlphaPlane>, pixels: usize) -> Option<AlphaPlane> {
match alpha {
Some(AlphaPlane::U8(_)) => Some(AlphaPlane::U8(vec![0; pixels])),
Some(AlphaPlane::U16 { bits, .. }) => Some(AlphaPlane::U16 {
data: vec![0; pixels],
bits: *bits,
}),
Some(AlphaPlane::F32(_)) => Some(AlphaPlane::F32(vec![0; pixels])),
None => None,
}
}
pub(crate) fn write_single_channel_lz77_section(
tokens: &[Token],
scratch: &mut CoderScratch,
w: &mut BitWriter,
) -> bool {
if tokens
.iter()
.any(|t| crate::entropy::uint_encode(t.value).0 >= LZ77_MIN_SYMBOL)
{
return false;
}
let mut runs = RunLzWriter::with_capacity(tokens.len());
for t in tokens {
runs.push(Token::new(0, t.value));
}
let lz = runs.finish();
let code = build_lz_pixel_code(
std::iter::once(lz.as_slice()),
1,
LZ77_MIN_SYMBOL,
true,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
w.write(1, 0);
w.write(1, 1);
w.write(2, 0);
write_local_tree_lz77(
&[PREDICTOR_GRADIENT],
&code,
LZ77_MIN_SYMBOL,
&mut scratch.huffman_pool,
w,
);
write_lz_section(&lz, 1, &code, LZ77_MIN_SYMBOL, w);
true
}
fn write_lz_groups(
groups: &[Vec<LzToken>],
code: &crate::entropy::EntropyCode<'_>,
distance_context: u32,
min_symbol: u32,
wp_params: WpParams,
pool: &ThreadPool,
sections: &mut [BitWriter],
) {
write_lz_groups_with_header(
groups,
code,
distance_context,
min_symbol,
pool,
sections,
|_, section| {
section.write(1, 1);
write_wp_header(wp_params, section);
section.write(2, 0);
},
);
}
fn write_lz_groups_with_header(
groups: &[Vec<LzToken>],
code: &crate::entropy::EntropyCode<'_>,
distance_context: u32,
min_symbol: u32,
pool: &ThreadPool,
sections: &mut [BitWriter],
write_header: impl Fn(usize, &mut BitWriter) + Sync,
) {
debug_assert_eq!(groups.len(), sections.len());
let max_staging = if code.use_prefix_code {
0
} else {
groups
.iter()
.map(|g| g.len().saturating_mul(8))
.max()
.unwrap_or(0)
};
#[allow(clippy::manual_clamp)]
let lanes = (32 * 1024 * 1024 / max_staging.max(1))
.max(1)
.min(SLOW_DEEP_LZ_MAX_THREADS)
.min(pool.num_threads())
.min(sections.len());
let write_group = |i: usize, section: &mut BitWriter| {
write_header(i, section);
write_lz_section(&groups[i], distance_context, code, min_symbol, section);
section.zero_pad_to_byte();
};
if lanes <= 1 {
for (i, section) in sections.iter_mut().enumerate() {
write_group(i, section);
}
return;
}
let mut writer_scratch = CoderScratch::lossless();
pool.steal_for_each_mut_with_threads(&mut writer_scratch, sections, lanes, |i, section, _| {
write_group(i, section);
});
}
fn keep_smaller_writer(best: &mut Option<BitWriter>, candidate: BitWriter) {
if best
.as_ref()
.is_none_or(|current| candidate.bits_written() < current.bits_written())
{
*best = Some(candidate);
}
}
pub(crate) fn encode_frame_lossless(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
patches: bool,
num_color: usize,
speed: crate::Speed,
decoding_speed: crate::DecodingSpeed,
num_threads: usize,
writer: &mut BitWriter,
) {
let pool = ThreadPool::new_lossless(num_threads);
let mut scratch = Box::new(CoderScratch::lossless());
encode_frame_lossless_with_pool(
linear,
alpha,
max_bits,
progressive,
patches,
num_color,
speed,
decoding_speed,
&pool,
&mut scratch,
writer,
);
}
#[allow(clippy::too_many_arguments)]
fn encode_frame_lossless_with_pool(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
patches: bool,
num_color: usize,
speed: crate::Speed,
decoding_speed: crate::DecodingSpeed,
pool: &ThreadPool,
scratch: &mut CoderScratch,
writer: &mut BitWriter,
) {
let glyph_plan = if patches && num_color == 3 {
crate::patches::find_lossless_glyph_patches(linear)
} else {
None
};
let is_glyph_plan = glyph_plan.is_some();
if patches
&& num_color == 3
&& let Some(plan) = glyph_plan.or_else(|| find_lossless_patches(linear, pool, scratch))
{
let mut regular_writer = BitWriter::new();
if !is_glyph_plan {
let decisive_tree = encode_frame_lossless_core(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
ModularFrameKind::Regular,
true,
&mut regular_writer,
);
let covered: usize = plan
.references
.iter()
.map(|r| r.positions.len() * r.width * r.height)
.sum::<usize>();
let coverage = covered as f64 / (linear.xsize() * linear.ysize()) as f64;
if decisive_tree || coverage < PATCH_MIN_COVERAGE {
writer.append(®ular_writer);
return;
}
}
let mut patched_writer = BitWriter::new();
let atlas_alpha =
zero_alpha_like(alpha, plan.atlas.xsize().saturating_mul(plan.atlas.ysize()));
encode_frame_lossless_core(
&plan.atlas,
atlas_alpha.as_ref(),
max_bits,
false,
num_color,
speed,
decoding_speed,
pool,
scratch,
ModularFrameKind::ReferenceOnly {
width: plan.atlas.xsize(),
height: plan.atlas.ysize(),
},
true,
&mut patched_writer,
);
let atlas_bits = patched_writer.bits_written();
encode_frame_lossless_core(
&plan.base,
alpha,
max_bits,
false,
num_color,
speed,
decoding_speed,
pool,
scratch,
ModularFrameKind::Patched(&plan.references),
true,
&mut patched_writer,
);
if is_glyph_plan {
let min_symbol = lossless_min_symbol(max_bits);
let use_wp = decoding_speed.use_weighted_predictor();
let regular_est = coarse_frame_bits(linear, alpha, min_symbol, use_wp, pool, scratch);
let base_est = coarse_frame_bits(&plan.base, alpha, min_symbol, use_wp, pool, scratch);
let competitive = match (regular_est, base_est) {
(Some(regular), Some(base)) => {
let mut dictionary = BitWriter::new();
write_patch_dictionary(
&plan.references,
alpha.is_some(),
scratch,
&mut dictionary,
);
let patched = base + (atlas_bits + dictionary.bits_written()) as f64;
regular <= patched * GLYPH_REGULAR_COARSE_MARGIN
}
_ => true,
};
if competitive {
encode_frame_lossless_core(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
ModularFrameKind::Regular,
false,
&mut regular_writer,
);
}
}
if regular_writer.bits_written() > 0
&& regular_writer.bits_written() < patched_writer.bits_written()
{
writer.append(®ular_writer);
} else {
writer.append(&patched_writer);
}
return;
}
encode_frame_lossless_core(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
ModularFrameKind::Regular,
true,
writer,
);
}
#[allow(clippy::too_many_arguments)]
fn lossless_min_symbol(max_bits: u32) -> u32 {
if max_bits <= 13 {
LZ77_MIN_SYMBOL
} else {
4 * max_bits + 24
}
}
fn coarse_frame_bits(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
min_symbol: u32,
use_wp: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<f64> {
let (xsize, ysize) = (linear.xsize(), linear.ysize());
let source = rgb_ma_source(linear, alpha, xsize, 6);
let stage = rank_coarse(
&source,
xsize,
ysize,
min_symbol,
WpParams::DEFAULT,
use_wp,
pool,
scratch,
)?;
Some(stage.candidate.est_real.min(stage.candidate.flat_real))
}
const GLYPH_REGULAR_COARSE_MARGIN: f64 = 1.10;
fn encode_frame_lossless_core(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
num_color: usize,
speed: crate::Speed,
decoding_speed: crate::DecodingSpeed,
pool: &ThreadPool,
scratch: &mut CoderScratch,
frame_kind: ModularFrameKind<'_>,
local_trees: bool,
writer: &mut BitWriter,
) -> bool {
encode_frame_lossless_core_impl(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
frame_kind,
true,
local_trees,
writer,
)
}
#[allow(clippy::too_many_arguments)]
fn encode_frame_lossless_core_impl(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
num_color: usize,
speed: crate::Speed,
decoding_speed: crate::DecodingSpeed,
pool: &ThreadPool,
scratch: &mut CoderScratch,
frame_kind: ModularFrameKind<'_>,
allow_palette_candidates: bool,
local_trees: bool,
writer: &mut BitWriter,
) -> bool {
let use_wp = decoding_speed.use_weighted_predictor();
let min_symbol = lossless_min_symbol(max_bits);
let xsize = linear.xsize();
let ysize = linear.ysize();
let nb_chans = num_color + if alpha.is_some() { 1 } else { 0 };
let xsize_groups = xsize.div_ceil(GROUP_DIM);
let ysize_groups = ysize.div_ceil(GROUP_DIM);
let num_ac_groups = xsize_groups * ysize_groups;
let xsize_dc_groups = xsize.div_ceil(LF_GROUP_DIM);
let ysize_dc_groups = ysize.div_ceil(LF_GROUP_DIM);
let num_dc_groups = xsize_dc_groups * ysize_dc_groups;
let single_group = num_ac_groups == 1;
let grad_pack_fn = selected_grad_pack_interior_fn();
if allow_palette_candidates && frame_kind.is_regular() && single_group && num_color == 3 {
let mut palette_writer = BitWriter::new();
if try_encode_palette_single_group(
linear,
alpha,
xsize,
ysize,
min_symbol,
grad_pack_fn,
speed,
use_wp,
scratch,
&mut palette_writer,
) {
if speed == crate::Speed::Slow {
let mut normal_writer = BitWriter::new();
let normal_decisive = encode_frame_lossless_core_impl(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
frame_kind,
false,
local_trees,
&mut normal_writer,
);
if normal_writer.bits_written() < palette_writer.bits_written() {
writer.append(&normal_writer);
return normal_decisive;
}
writer.append(&palette_writer);
} else {
writer.append(&palette_writer);
}
return false;
}
}
if allow_palette_candidates && frame_kind.is_regular() && !single_group && num_color == 3 {
let mut palette_writer = BitWriter::new();
if try_encode_local_palette_multi_group(
linear,
alpha,
xsize,
ysize,
xsize_groups,
ysize_groups,
num_dc_groups,
min_symbol,
grad_pack_fn,
speed,
use_wp,
pool,
scratch,
&mut palette_writer,
) {
if speed == crate::Speed::Slow {
let mut normal_writer = BitWriter::new();
let normal_decisive = encode_frame_lossless_core_impl(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
decoding_speed,
pool,
scratch,
frame_kind,
false,
local_trees,
&mut normal_writer,
);
if normal_writer.bits_written() < palette_writer.bits_written() {
writer.append(&normal_writer);
return normal_decisive;
}
writer.append(&palette_writer);
} else {
writer.append(&palette_writer);
}
return false;
}
}
if frame_kind.is_regular() && single_group && num_color == 3 && progressive {
encode_squeeze_single_group(
linear,
alpha,
xsize,
ysize,
min_symbol,
grad_pack_fn,
speed,
use_wp,
pool,
scratch,
writer,
);
return false;
}
if frame_kind.is_regular()
&& !single_group
&& num_color == 3
&& progressive
&& encode_squeeze_multigroup(
linear,
alpha,
xsize,
ysize,
min_symbol,
xsize_groups,
ysize_groups,
xsize_dc_groups,
ysize_dc_groups,
num_dc_groups,
num_ac_groups,
grad_pack_fn,
speed,
use_wp,
pool,
scratch,
writer,
)
{
return false;
}
let adaptive_search = speed == crate::Speed::Slow;
let mut rct_type = 6u32;
let mut rct_planes: Option<Image3Si> = None;
let rct_ranked: Vec<(u32, f32)> =
if frame_kind.allows_learned_tree() && adaptive_search && num_color == 3 {
rank_rcts(linear, xsize, ysize, pool, scratch)
} else {
Vec::new()
};
if let Some(&(t, _)) = rct_ranked.first()
&& t != 6
{
rct_type = t;
rct_planes = Some(rct_planes_fn(linear, xsize, ysize, t));
}
let ycocg = linear;
let linear = rct_planes.as_ref().unwrap_or(linear);
let wp_header_count = if single_group {
1
} else {
2 + num_dc_groups + num_ac_groups
};
let mut wp_params = if adaptive_search && use_wp {
choose_wp_params(linear, alpha, num_color, wp_header_count, pool, scratch)
} else {
WpParams::DEFAULT
};
let compare_tree_candidates = frame_kind.allows_learned_tree()
&& adaptive_search
&& num_color == 3
&& decoding_speed.use_ma_trees();
let mut best_tree_writer: Option<BitWriter> = None;
let (layout, learned_tree_decisive, skip_alternatives) = {
let palette = if compare_tree_candidates {
build_global_palette(ycocg, alpha, xsize, ysize, pool, scratch)
} else {
None
};
let header_bits = |params: WpParams| {
if params == WpParams::DEFAULT {
0.0
} else {
(51 * wp_header_count) as f64
}
};
let mut rank_rgb = compare_tree_candidates;
let rgb_final_est: f64;
let mut best_source_coarse;
let mut rank_pal = compare_tree_candidates && palette.is_some();
let mut final_sampling = (MA_TARGET_SAMPLES, MA_FULL_SAMPLE_LIMIT);
let mut pal_wp = wp_params;
if compare_tree_candidates && matches!(decoding_speed, crate::DecodingSpeed::Slow) {
let rgb_stage = {
let source = rgb_ma_source(linear, alpha, xsize, rct_type);
rank_coarse(
&source, xsize, ysize, min_symbol, wp_params, use_wp, pool, scratch,
)
};
let pal_stage = palette.as_ref().and_then(|p| {
let source = p.source(xsize, ysize);
rank_coarse(
&source, xsize, ysize, min_symbol, wp_params, use_wp, pool, scratch,
)
});
let coarse_of = |stage: &Option<CoarseLearn>| {
stage.as_ref().map_or(f64::INFINITY, |s| {
s.candidate.est_real + header_bits(wp_params)
})
};
let (rgb_coarse, pal_coarse) = (coarse_of(&rgb_stage), coarse_of(&pal_stage));
if rgb_stage.as_ref().is_some_and(|stage| {
stage.candidate.est_real
>= DENSE_FINAL_MIN_BITS_PER_VALUE
* source_values_of(xsize, ysize, nb_chans) as f64
}) {
final_sampling = (MA_FINAL_TARGET_SAMPLES, MA_FINAL_FULL_SAMPLE_LIMIT);
}
rank_rgb = rgb_coarse <= pal_coarse * PALETTE_COARSE_MARGIN;
rank_pal = pal_stage.is_some() && pal_coarse <= rgb_coarse * PALETTE_COARSE_MARGIN;
let rank_more = source_values_of(xsize, ysize, nb_chans) >= RANK_MIN_VALUES;
if rank_rgb && rank_more {
let (mut best_bits, mut best_coarse, params) = {
let source = rgb_ma_source(linear, alpha, xsize, rct_type);
rank_presets(
&source,
xsize,
ysize,
min_symbol,
use_wp,
rgb_stage,
wp_params,
&header_bits,
pool,
scratch,
)
};
wp_params = params;
if let Some(&(runner_up, cost)) = rct_ranked.get(1)
&& cost <= rct_ranked[0].1 * RCT_RANK_MARGIN
{
let planes =
(runner_up != 6).then(|| rct_planes_fn(ycocg, xsize, ysize, runner_up));
let source =
rgb_ma_source(planes.as_ref().unwrap_or(ycocg), alpha, xsize, runner_up);
if let Some(stage) = rank_coarse(
&source, xsize, ysize, min_symbol, wp_params, use_wp, pool, scratch,
) && stage.candidate.est_real + header_bits(wp_params)
<= best_coarse * RANK_COARSE_PRUNE
{
best_coarse =
best_coarse.min(stage.candidate.est_real + header_bits(wp_params));
let bits = rank_bits(&stage) + header_bits(wp_params);
if bits < best_bits {
best_bits = bits;
rct_type = runner_up;
rct_planes = planes;
}
}
}
let _ = (best_bits, best_coarse);
}
if rank_pal
&& rank_more
&& let Some(p) = &palette
{
let source = p.source(xsize, ysize);
let (_, _, params) = rank_presets(
&source,
xsize,
ysize,
min_symbol,
use_wp,
pal_stage,
wp_params,
&header_bits,
pool,
scratch,
);
pal_wp = params;
}
}
let linear = rct_planes.as_ref().unwrap_or(ycocg);
let slow_layouts = compare_tree_candidates
&& matches!(decoding_speed, crate::DecodingSpeed::Slow)
&& (xsize > GroupLayout::DEFAULT.dim() || ysize > GroupLayout::DEFAULT.dim());
let layouts: &[GroupLayout] = if slow_layouts {
&[GroupLayout::LARGE, GroupLayout::DEFAULT]
} else {
&[GroupLayout::DEFAULT]
};
let rgb_layouts: &[GroupLayout] = if slow_layouts
&& source_values_of(xsize, ysize, nb_chans) > RGB_SINGLE_LAYOUT_MIN_VALUES
{
&[GroupLayout::LARGE]
} else {
layouts
};
let (layout, rgb_coarse_est, mut learned_tree_decisive, skip_alternatives) = {
let rgb_source = rgb_ma_source(linear, alpha, xsize, rct_type);
let mut learned_estimated_savings: Option<f64> = None;
let learned = if rank_rgb {
learn_best_layout(
&rgb_source,
xsize,
ysize,
rgb_layouts,
min_symbol,
wp_params,
use_wp,
f64::INFINITY,
f64::INFINITY,
false,
final_sampling,
pool,
scratch,
)
} else {
None
};
let rgb_coarse_est = learned.as_ref().map_or(f64::INFINITY, |(_, _, e)| *e);
best_source_coarse = rgb_coarse_est;
rgb_final_est = learned
.as_ref()
.map_or(f64::INFINITY, |(_, c, _)| c.est_real);
let layout = learned.as_ref().map_or(layouts[0], |(l, _, _)| *l);
if let Some((_, cand, _)) = &learned {
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
&rgb_source,
alpha.is_some(),
frame_kind,
xsize,
ysize,
layout,
min_symbol,
pool,
scratch,
wp_params,
use_wp,
cand,
local_trees,
&mut candidate,
);
learned_estimated_savings = Some(estimated_savings);
keep_smaller_writer(&mut best_tree_writer, candidate);
}
(
layout,
rgb_coarse_est,
learned_estimated_savings.is_some_and(learned_tree_is_decisive),
learned_estimated_savings.is_some_and(|s| s >= MA_ALTERNATIVES_MIN_SAVINGS),
)
};
if learned_tree_decisive {
rct_planes = None;
}
let bytes_before_palette = best_tree_writer.as_ref().map(BitWriter::bits_written);
if rank_pal && let Some(palette) = &palette {
let palette_source = palette.source(xsize, ysize);
let coarse_limit = rgb_coarse_est * PALETTE_COARSE_MARGIN;
if let Some((palette_layout, cand, palette_coarse)) = learn_best_layout(
&palette_source,
xsize,
ysize,
layouts,
min_symbol,
pal_wp,
use_wp,
coarse_limit,
rgb_final_est * PALETTE_FINAL_MARGIN * PALETTE_LAYOUT_MARGIN,
true,
final_sampling,
pool,
scratch,
) {
let palette_can_win = cand.est_real <= rgb_final_est * PALETTE_FINAL_MARGIN;
if palette_can_win {
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
&palette_source,
alpha.is_some(),
frame_kind,
xsize,
ysize,
palette_layout,
min_symbol,
pool,
scratch,
pal_wp,
use_wp,
&cand,
local_trees,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
learned_tree_decisive = true;
rct_planes = None;
}
keep_smaller_writer(&mut best_tree_writer, candidate);
}
best_source_coarse = best_source_coarse.min(palette_coarse);
}
}
let global_palette_won =
best_tree_writer.as_ref().map(BitWriter::bits_written) != bytes_before_palette;
if compare_tree_candidates && num_color == 3 && !global_palette_won {
let gdim = GroupLayout::DEFAULT.dim();
let groups_x = xsize.div_ceil(gdim);
let groups_y = ysize.div_ceil(gdim);
let groups = groups_x * groups_y;
if groups > 1 {
let palettes: Vec<Option<palette::LocalPaletteGroup>> =
pool.steal_map(scratch, groups, |group_index, _scratch| {
let x0 = (group_index % groups_x) * gdim;
let y0 = (group_index / groups_x) * gdim;
palette::build_local_palette_group_limited(
ycocg,
alpha,
xsize,
x0,
y0,
gdim.min(xsize - x0),
gdim.min(ysize - y0),
palette::LOCAL_PALETTE_MAX_COLORS,
)
});
let covered: usize = palettes
.iter()
.flatten()
.map(|palette| palette.w * palette.h)
.sum();
if covered * 2 >= xsize * ysize {
let mixed = mixed_ma_source(ycocg, alpha, xsize, &palettes);
let stage = learn_ma_candidate(
&mixed,
xsize,
ysize,
GroupLayout::DEFAULT,
min_symbol,
wp_params,
use_wp,
MA_MAX_LEAVES,
final_sampling.0,
final_sampling.1,
pool,
scratch,
);
if let Some(stage) = stage
.filter(|s| s.candidate.est_real < best_source_coarse * PER_GROUP_MARGIN)
{
let cand = finish_ma_learn(
stage,
min_symbol,
use_wp,
MA_MAX_LEAVES,
pool,
scratch,
);
let mut candidate = BitWriter::new();
let estimated_savings = write_learned_tree_frame(
&mixed,
alpha.is_some(),
frame_kind,
xsize,
ysize,
GroupLayout::DEFAULT,
min_symbol,
pool,
scratch,
wp_params,
use_wp,
&cand,
local_trees,
&mut candidate,
);
if learned_tree_is_decisive(estimated_savings) {
learned_tree_decisive = true;
rct_planes = None;
}
keep_smaller_writer(&mut best_tree_writer, candidate);
}
}
}
}
(layout, learned_tree_decisive, skip_alternatives)
};
if learned_tree_decisive || skip_alternatives {
writer.append(
best_tree_writer
.as_ref()
.expect("decisive learned-tree candidate"),
);
return learned_tree_decisive;
}
let gdim = layout.dim();
let xsize_groups = xsize.div_ceil(gdim);
let ysize_groups = ysize.div_ceil(gdim);
let num_ac_groups = xsize_groups * ysize_groups;
let num_dc_groups = xsize.div_ceil(layout.lf_dim()) * ysize.div_ceil(layout.lf_dim());
let single_group = num_ac_groups == 1;
let linear = rct_planes.as_ref().unwrap_or(ycocg);
let predictors = if adaptive_search {
choose_predictors_with_wp(
linear, alpha, xsize, ysize, num_color, pool, scratch, wp_params, use_wp,
)
} else {
[fixed_predictor(use_wp); 4]
};
let chan_preds: Vec<u32> = {
let mut v: Vec<u32> = (0..num_color).map(|c| predictors[c]).collect();
if alpha.is_some() {
v.push(predictors[3]);
}
v
};
if compare_tree_candidates && use_wp {
let mut candidate = BitWriter::new();
if single_group {
if try_encode_context_tree_single_group(
linear,
alpha,
xsize,
ysize,
layout,
&predictors,
min_symbol,
rct_type,
pool,
scratch,
wp_params,
&mut candidate,
) {
keep_smaller_writer(&mut best_tree_writer, candidate);
}
} else if try_encode_context_tree_multi_group(
linear,
alpha,
xsize,
ysize,
layout,
&predictors,
xsize_groups,
ysize_groups,
num_dc_groups,
min_symbol,
rct_type,
pool,
scratch,
wp_params,
&mut candidate,
) {
keep_smaller_writer(&mut best_tree_writer, candidate);
}
}
if !chan_preds.contains(&PREDICTOR_WEIGHTED) {
wp_params = WpParams::DEFAULT;
}
let mut flat_writer = BitWriter::new();
{
let writer = if compare_tree_candidates {
&mut flat_writer
} else {
&mut *writer
};
write_frame_header_modular_kind(alpha.is_some(), frame_kind, layout, writer);
if single_group {
let mut section = BitWriter::new();
if let ModularFrameKind::Patched(references) = frame_kind {
write_patch_dictionary(references, alpha.is_some(), scratch, &mut section);
}
section.write(1, 1);
section.write(1, 0);
section.write(1, 0);
write_wp_header(wp_params, &mut section);
write_modular_transforms(nb_chans, rct_type, &mut section);
let channel_tokens = tokenize_channels_with_wp(
linear,
alpha,
xsize,
ysize,
0,
0,
xsize,
ysize,
num_color,
&chan_preds,
grad_pack_fn,
pool,
scratch,
wp_params,
);
let distance_ctx = nb_chans as u32;
let lz_tokens =
lz77_compress_channels_for_speed(channel_tokens, distance_ctx, speed, scratch);
let code = build_lz_pixel_code(
std::iter::once(lz_tokens.as_slice()),
nb_chans,
min_symbol,
speed == crate::Speed::Slow,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
write_local_tree_lz77(
&chan_preds,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut section,
);
write_lz_section(&lz_tokens, distance_ctx, &code, min_symbol, &mut section);
section.zero_pad_to_byte();
writer.write(1, 0); writer.zero_pad_to_byte();
write_toc_entry(section.bits_written() / 8, writer);
writer.zero_pad_to_byte();
writer.append_byte_aligned(std::slice::from_mut(&mut section));
writer.zero_pad_to_byte();
} else {
let num_sections = 1 + num_dc_groups + 1 + num_ac_groups;
let mut sections: Vec<BitWriter> =
(0..num_sections).map(|_| BitWriter::new()).collect();
let distance_ctx = nb_chans as u32;
let group_lz_tokens: Vec<Vec<LzToken>> = {
let deep_lz = (speed == crate::Speed::Slow)
.then(|| DeepLzScratchPool::new(group_lz_threads(speed, pool)));
pool.steal_map_with_threads(
scratch,
num_ac_groups,
group_lz_threads(speed, pool),
|group_index, scratch| {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * gdim;
let y0 = gy * gdim;
let gw = gdim.min(xsize - x0);
let gh = gdim.min(ysize - y0);
if speed == crate::Speed::Slow {
let channel_tokens = tokenize_channels_with_wp(
linear,
alpha,
xsize,
ysize,
x0,
y0,
gw,
gh,
num_color,
&chan_preds,
grad_pack_fn,
pool,
scratch,
wp_params,
);
deep_lz.as_ref().unwrap().with_depth(|depth| {
lz77_compress_channels_for_speed_with_depth(
channel_tokens,
distance_ctx,
speed,
depth,
scratch,
)
})
} else {
tokenize_runs_with_wp(
linear,
alpha,
xsize,
x0,
y0,
gw,
gh,
num_color,
&chan_preds,
grad_pack_fn,
scratch,
wp_params,
)
}
},
)
};
if let ModularFrameKind::Patched(references) = frame_kind {
write_patch_dictionary(references, alpha.is_some(), scratch, &mut sections[0]);
}
let code = build_lz_pixel_code(
group_lz_tokens.iter().map(Vec::as_slice),
nb_chans,
min_symbol,
speed == crate::Speed::Slow,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
sections[0].write(1, 1); sections[0].write(1, 1); write_local_tree_lz77(
&chan_preds,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut sections[0],
);
sections[0].write(1, 1);
write_wp_header(wp_params, &mut sections[0]);
write_modular_transforms(nb_chans, rct_type, &mut sections[0]);
sections[0].zero_pad_to_byte();
for section in &mut sections[1..1 + num_dc_groups] {
section.write(1, 1); write_wp_header(wp_params, section);
section.write(2, 0); section.zero_pad_to_byte();
}
let ac_global_idx = 1 + num_dc_groups;
sections[ac_global_idx].write(1, 1);
write_wp_header(wp_params, &mut sections[ac_global_idx]);
sections[ac_global_idx].zero_pad_to_byte();
write_lz_groups(
&group_lz_tokens,
&code,
distance_ctx,
min_symbol,
wp_params,
pool,
&mut sections[2 + num_dc_groups..],
);
writer.write(1, 0);
writer.zero_pad_to_byte();
for s in §ions {
write_toc_entry(s.bits_written() / 8, writer);
}
writer.zero_pad_to_byte();
writer.append_byte_aligned(&mut sections);
writer.zero_pad_to_byte();
}
}
if compare_tree_candidates {
keep_smaller_writer(&mut best_tree_writer, flat_writer);
writer.append(best_tree_writer.as_ref().expect("flat lossless candidate"));
}
false
}
fn write_u64(value: u64, w: &mut BitWriter) {
match value {
0 => w.write(2, 0),
1..=16 => {
w.write(2, 1);
w.write(4, value - 1);
}
17..=272 => {
w.write(2, 2);
w.write(8, value - 17);
}
_ => unreachable!("lossless frame flags fit the short U64 form"),
}
}
fn write_frame_dimension(value: usize, w: &mut BitWriter) {
let value = value as u64;
if value < 256 {
w.write(2, 0);
w.write(8, value);
} else if value < 2304 {
w.write(2, 1);
w.write(11, value - 256);
} else if value < 18688 {
w.write(2, 2);
w.write(14, value - 2304);
} else {
w.write(2, 3);
w.write(30, value - 18688);
}
}
fn write_frame_header_modular_kind(
has_alpha: bool,
kind: ModularFrameKind<'_>,
layout: GroupLayout,
w: &mut BitWriter,
) {
match kind {
ModularFrameKind::Regular => write_frame_header_modular(has_alpha, layout, w),
ModularFrameKind::Patched(_) => write_frame_header_modular_flags(has_alpha, 2, layout, w),
ModularFrameKind::ReferenceOnly { width, height } => {
w.write(1, 0); w.write(2, 0b10); w.write(1, 1); write_u64(0, w); w.write(1, 0); w.write(2, 0); if has_alpha {
w.write(2, 0); }
w.write(2, layout.shift as u64);
w.write(1, 1); write_frame_dimension(width, w);
write_frame_dimension(height, w);
w.write(2, PATCH_REF_ID as u64); w.write(1, 1); w.write(2, 0); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0); w.write(2, 0); }
}
}
fn write_frame_header_modular_xyb_reference(
width: usize,
height: usize,
has_alpha: bool,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b10); w.write(1, 1); write_u64(0, w); w.write(2, 0); if has_alpha {
w.write(2, 0); }
w.write(2, GroupLayout::DEFAULT.shift as u64);
w.write(1, 1); write_frame_dimension(width, w);
write_frame_dimension(height, w);
w.write(2, crate::patches::MODULAR_PATCH_REF_ID as u64); w.write(1, 1); w.write(2, 0); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0); w.write(2, 0); }
pub(crate) fn encode_modular_xyb_atlas(
atlas: &crate::image::Image3F,
has_alpha: bool,
lattice_scale: u32,
speed: crate::Speed,
use_wp: bool,
scratch: &mut CoderScratch,
writer: &mut BitWriter,
) -> bool {
use std::collections::HashMap;
debug_assert!(lattice_scale.is_power_of_two() && lattice_scale <= 8);
let (xsize, ysize) = (atlas.xsize(), atlas.ysize());
if xsize == 0 || ysize == 0 || xsize > GROUP_DIM || ysize > GROUP_DIM {
return false;
}
let ch = quantize_xyb_channels(atlas, lattice_scale);
let npx = xsize * ysize;
let grad_pack_fn = selected_grad_pack_interior_fn();
let slow = speed == crate::Speed::Slow;
let mut seen: HashMap<[i32; 3], ()> = HashMap::with_capacity(257);
let [y, x, b] = &ch;
let pixel_colors = || y[..npx].iter().zip(&x[..npx]).zip(&b[..npx]);
for ((&y, &x), &b) in pixel_colors() {
seen.entry([y, x, b]).or_insert(());
if seen.len() > 256 {
break;
}
}
let use_palette = !seen.is_empty() && seen.len() <= 256;
write_frame_header_modular_xyb_reference(xsize, ysize, has_alpha, writer);
let mut section = BitWriter::new();
if lattice_scale == 1 {
section.write(1, 1); } else {
use crate::quant_weights::INV_DC_QUANT;
use crate::util::f32_to_f16_bits;
section.write(1, 0);
for c in 0..3 {
let step_x128 = 128.0 / (INV_DC_QUANT[c] * lattice_scale as f32);
section.write(16, f32_to_f16_bits(step_x128) as u64);
}
}
section.write(1, 0); section.write(1, 0); section.write(1, 1);
let num_c = 3 + usize::from(has_alpha);
let mut tokens: Vec<Token> = Vec::new();
let (preds, nb_chans): (Vec<u32>, usize) = if use_palette {
let mut colors: Vec<[i32; 3]> = seen.keys().copied().collect();
colors.sort_unstable();
let nb_colors = colors.len();
let mut idx_of: HashMap<[i32; 3], u32> = HashMap::with_capacity(nb_colors);
for (i, c) in colors.iter().enumerate() {
idx_of.insert(*c, i as u32);
}
let mut palette_ch = vec![0i32; num_c * nb_colors];
for (c, row) in palette_ch[..3 * nb_colors]
.chunks_exact_mut(nb_colors)
.enumerate()
{
for (value, color) in row.iter_mut().zip(&colors) {
*value = color[c];
}
}
let index_img: Vec<i32> = pixel_colors()
.map(|((&y, &x), &b)| idx_of[&[y, x, b]] as i32)
.collect();
write_palette_transform(num_c as u32, nb_colors as u32, &mut section);
let pget = |gx: usize, gy: usize| palette_ch[gy * nb_colors + gx];
let iget = |gx: usize, gy: usize| index_img[gy * xsize + gx];
let preds = if slow {
vec![
choose_predictor_for_plane(pget, nb_colors, num_c, use_wp),
choose_predictor_for_plane(iget, xsize, ysize, use_wp),
]
} else {
vec![fixed_predictor(use_wp); 2]
};
tokenize_plane_rows(
channel_to_context(0, 2),
|y| &palette_ch[y * nb_colors..][..nb_colors],
nb_colors,
num_c,
preds[0],
grad_pack_fn,
&mut scratch.gradient,
&mut tokens,
);
tokenize_plane_rows(
channel_to_context(1, 2),
|y| &index_img[y * xsize..][..xsize],
xsize,
ysize,
preds[1],
grad_pack_fn,
&mut scratch.gradient,
&mut tokens,
);
(preds, 2)
} else {
section.write(2, 0b00); let mut preds = Vec::with_capacity(num_c);
for (c, data) in ch.iter().enumerate() {
let get = |gx: usize, gy: usize| data[gy * xsize + gx];
let pred = if slow {
choose_predictor_for_plane(get, xsize, ysize, use_wp)
} else {
fixed_predictor(use_wp)
};
tokenize_plane_rows(
channel_to_context(c, num_c),
|y| &data[y * xsize..][..xsize],
xsize,
ysize,
pred,
grad_pack_fn,
&mut scratch.gradient,
&mut tokens,
);
preds.push(pred);
}
if has_alpha {
tokenize_plane(
channel_to_context(3, num_c),
|_, _| 0,
xsize,
ysize,
fixed_predictor(use_wp),
grad_pack_fn,
&mut scratch.gradient,
&mut tokens,
);
preds.push(fixed_predictor(use_wp));
}
(preds, num_c)
};
let max_abs = ch
.iter()
.flat_map(|plane| plane.iter())
.map(|v| v.unsigned_abs())
.max()
.unwrap_or(0);
let value_bits = 33 - (2 * max_abs).max(1).leading_zeros();
let min_symbol = if value_bits <= 13 {
LZ77_MIN_SYMBOL
} else {
4 * value_bits + 24
};
let distance_ctx = nb_chans as u32;
let lz_tokens = lz77_compress_for_speed(&tokens, distance_ctx, speed, scratch);
let code = build_lz_pixel_code(
std::iter::once(lz_tokens.as_slice()),
nb_chans,
min_symbol,
slow,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
write_local_tree_lz77(
&preds,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut section,
);
write_lz_section(&lz_tokens, distance_ctx, &code, min_symbol, &mut section);
section.zero_pad_to_byte();
writer.write(1, 0); writer.zero_pad_to_byte();
write_toc_entry(section.bits_written() / 8, writer);
writer.zero_pad_to_byte();
writer.append_byte_aligned(std::slice::from_mut(&mut section));
writer.zero_pad_to_byte();
true
}
fn write_frame_header_modular(has_alpha: bool, layout: GroupLayout, w: &mut BitWriter) {
write_frame_header_modular_flags(has_alpha, 0, layout, w);
}
fn write_frame_header_modular_flags(
has_alpha: bool,
flags: u64,
layout: GroupLayout,
w: &mut BitWriter,
) {
w.write(1, 0); w.write(2, 0b00); w.write(1, 1); write_u64(flags, w);
w.write(1, 0); w.write(2, 0b00); if has_alpha {
w.write(2, 0b00);
}
w.write(2, layout.shift as u64);
w.write(2, 0b00); w.write(1, 0); w.write(2, 0b00); if has_alpha {
w.write(2, 0b00);
}
w.write(1, 1); w.write(2, 0b00); w.write(1, 0); w.write(1, 0); w.write(2, 0); w.write(2, 0b00); w.write(2, 0b00); }
pub(crate) fn write_patch_dictionary(
references: &[PatchReference],
has_alpha: bool,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
const NUM_REF: u32 = 0;
const REFERENCE_FRAME: u32 = 1;
const PATCH_SIZE: u32 = 2;
const REF_POSITION: u32 = 3;
const POSITION: u32 = 4;
const BLEND_MODE: u32 = 5;
const OFFSET: u32 = 6;
const COUNT: u32 = 7;
let mut tokens = Vec::new();
tokens.push(Token::new(NUM_REF, references.len() as u32));
for reference in references {
tokens.push(Token::new(REFERENCE_FRAME, reference.ref_frame));
tokens.push(Token::new(REF_POSITION, reference.atlas_x as u32));
tokens.push(Token::new(REF_POSITION, reference.atlas_y as u32));
tokens.push(Token::new(PATCH_SIZE, (reference.width - 1) as u32));
tokens.push(Token::new(PATCH_SIZE, (reference.height - 1) as u32));
tokens.push(Token::new(COUNT, (reference.positions.len() - 1) as u32));
for (i, &(x, y)) in reference.positions.iter().enumerate() {
if i == 0 {
tokens.push(Token::new(POSITION, x as u32));
tokens.push(Token::new(POSITION, y as u32));
} else {
let (px, py) = reference.positions[i - 1];
tokens.push(Token::new(OFFSET, pack_signed(x as i32 - px as i32)));
tokens.push(Token::new(OFFSET, pack_signed(y as i32 - py as i32)));
}
tokens.push(Token::new(BLEND_MODE, 1)); if has_alpha {
tokens.push(Token::new(BLEND_MODE, 0)); }
}
}
let code = optimize_entropy_code(&tokens, NUM_PATCH_CONTEXTS, &mut scratch.huffman_pool);
let code_ref = code.as_ref();
w.write(1, 0); write_entropy_code(&code_ref, &mut scratch.huffman_pool, w);
for token in tokens {
write_token(token, &code_ref, w);
}
}
fn write_modular_transforms(nb_chans: usize, rct_type: u32, w: &mut BitWriter) {
if nb_chans >= 3 {
w.write(2, 0b01);
write_rct_transform(rct_type, w);
} else {
w.write(2, 0b00); }
}
fn write_toc_entry(byte_len: usize, w: &mut BitWriter) {
static OFFSETS: [usize; 4] = [0, 1024, 17_408, 4_211_712];
static BITS: [usize; 4] = [10, 14, 22, 30];
let mut bucket = 0usize;
while bucket < 3 && byte_len >= OFFSETS[bucket + 1] {
bucket += 1;
}
w.write(2, bucket as u64);
w.write(BITS[bucket], (byte_len - OFFSETS[bucket]) as u64);
}
const PROP_WP: u32 = 15;
enum CtTree {
Split(u32, i32, Box<CtTree>, Box<CtTree>),
Leaf(u32, u32),
}
fn emit_ct_tree(root: &CtTree, out: &mut Vec<Token>) -> std::collections::HashMap<u32, u32> {
use std::collections::{HashMap, VecDeque};
let mut map: HashMap<u32, u32> = HashMap::new();
let mut q: VecDeque<&CtTree> = VecDeque::new();
q.push_back(root);
let mut ctx = 0u32;
while let Some(node) = q.pop_front() {
match node {
CtTree::Split(prop, val, gt, le) => {
push_split(out, *prop, *val);
q.push_back(gt);
q.push_back(le);
}
CtTree::Leaf(pred, tag) => {
push_leaf(out, *pred);
map.insert(*tag, ctx);
ctx += 1;
}
}
}
map
}
#[inline]
fn bucket_of(prop: i64, t: i64) -> u32 {
if prop > t {
2
} else if prop > -t - 1 {
1
} else {
0
}
}
fn act_sub(c: u32, pred: u32, t: i32) -> CtTree {
CtTree::Split(
PROP_WP,
t,
Box::new(CtTree::Leaf(pred, c * 3 + 2)),
Box::new(CtTree::Split(
PROP_WP,
-t - 1,
Box::new(CtTree::Leaf(pred, c * 3 + 1)),
Box::new(CtTree::Leaf(pred, c * 3)),
)),
)
}
fn build_context_tree(nb_chans: usize, preds: &[u32], t: &[i32]) -> CtTree {
let a = |c: usize| act_sub(c as u32, preds[c], t[c]);
match nb_chans {
1 => a(0),
2 => CtTree::Split(0, 0, Box::new(a(1)), Box::new(a(0))),
3 => CtTree::Split(
0,
1,
Box::new(a(2)),
Box::new(CtTree::Split(0, 0, Box::new(a(1)), Box::new(a(0)))),
),
4 => CtTree::Split(
0,
1,
Box::new(CtTree::Split(0, 2, Box::new(a(3)), Box::new(a(2)))),
Box::new(CtTree::Split(0, 0, Box::new(a(1)), Box::new(a(0)))),
),
_ => unreachable!("context tree supports 1..=4 channels"),
}
}
fn order0_entropy(vals: &[u32], cell: &mut Vec<u64>, entropy_of_hist: EntropyOfHistFn) -> f32 {
if vals.is_empty() {
return 0.0;
}
let max = vals.iter().copied().max().unwrap_or(0) as usize;
if cell.len() < max + 1 {
cell.resize(max + 1, 0);
}
let hist = &mut cell[..max + 1];
hist.fill(0);
for &v in vals {
hist[v as usize] += 1;
}
entropy_of_hist(hist, vals.len() as u64)
}
fn collect_channel(
get: impl Fn(usize, usize) -> i32,
gw: usize,
gh: usize,
pred_id: u32,
wp_params: WpParams,
) -> (Vec<u32>, Vec<i64>) {
let mut wp = WpState::with_params(gw, wp_params);
let mut res = vec![0; gw * gh];
let mut prp = vec![0; gw * gh];
let (mut gx, mut gy) = (0, 0);
for (res, prp) in res.iter_mut().zip(&mut prp) {
let v = get(gx, gy) as i64;
let neighbors = predictor_neighbors(&get, gx, gy, gw);
let wp_pred = wp.predict(
gx,
gy,
neighbors.top,
neighbors.left,
neighbors.top_right,
neighbors.top_left,
neighbors.top_top,
);
*prp = wp.wp_prop;
let pred = predictor_value(pred_id, neighbors, wp_pred);
*res = pack_signed((v - pred) as i32);
wp.update(v, gx, gy);
gx += 1;
if gx == gw {
gx = 0;
gy += 1;
}
}
(res, prp)
}
pub(crate) type EntropyOfHistFn = fn(&[u64], u64) -> f32;
fn select_entropy_of_hist_fn() -> EntropyOfHistFn {
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma") {
return |hist, total| unsafe { crate::avx::entropy_of_hist_avx2(hist, total) };
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
{
|hist, total| unsafe { crate::neon::entropy_of_hist_neon(hist, total) }
}
#[cfg(not(all(target_arch = "aarch64", feature = "neon")))]
{
entropy_of_hist_scalar
}
}
pub(crate) fn selected_entropy_of_hist_fn() -> EntropyOfHistFn {
static ENTROPY_OF_HIST: OnceLock<EntropyOfHistFn> = OnceLock::new();
*ENTROPY_OF_HIST.get_or_init(select_entropy_of_hist_fn)
}
#[cfg(any(test, not(all(target_arch = "aarch64", feature = "neon"))))]
fn entropy_of_hist_scalar(hist: &[u64], total: u64) -> f32 {
use crate::adaptive_quant::dirty_log2f;
if total == 0 {
return 0.0;
}
let t = total as f32;
let mut bits = 0.0;
for &c in hist.iter() {
if c != 0 {
let p = c as f32 / t;
bits -= c as f32 * dirty_log2f(p);
}
}
bits
}
#[derive(Default)]
pub(crate) struct PickThresholdScratch {
pub(crate) hist_scratch: Vec<u64>,
}
impl PickThresholdScratch {
fn make_scratches(&mut self, size: usize) -> (&mut [u64], &mut [u64], &mut [u64]) {
let bucket = size + 1;
if self.hist_scratch.len() < bucket * 3 {
self.hist_scratch.resize(bucket * 3, 0);
}
let (b0, r0) = self.hist_scratch.split_at_mut(bucket);
let (b1, b2) = r0.split_at_mut(bucket);
(b0, b1, &mut b2[..bucket])
}
}
fn pick_threshold(res: &[u32], prp: &[i64], scratch: &mut CoderScratch) -> (i32, f32, f32) {
let entropy_of_hist = scratch.entropy_of_hist;
let flat = order0_entropy(res, &mut scratch.order0_entropy, entropy_of_hist);
let max = res.iter().copied().max().unwrap_or(0) as usize;
let (h0, h1, h2) = scratch.threshold.make_scratches(max + 1);
let mut best_t = 0i32;
let mut best_bits = f32::INFINITY;
for &t in &[8i64, 16, 24, 32, 48, 64, 96] {
h0.fill(0);
h1.fill(0);
h2.fill(0);
let (mut n0, mut n1, mut n2) = (0u64, 0u64, 0u64);
for (&r, &p) in res.iter().zip(prp.iter()) {
match bucket_of(p, t) {
0 => {
h0[r as usize] += 1;
n0 += 1;
}
1 => {
h1[r as usize] += 1;
n1 += 1;
}
_ => {
h2[r as usize] += 1;
n2 += 1;
}
}
}
let bits = entropy_of_hist(h0, n0) + entropy_of_hist(h1, n1) + entropy_of_hist(h2, n2);
if bits < best_bits {
best_bits = bits;
best_t = t as i32;
}
}
(best_t, best_bits, flat)
}
fn pick_threshold_grouped(
groups: &[Vec<(Vec<u32>, Vec<i64>)>],
channel: usize,
scratch: &mut CoderScratch,
) -> (i32, f32, f32) {
let entropy_of_hist = scratch.entropy_of_hist;
let total: usize = groups.iter().map(|group| group[channel].0.len()).sum();
if total == 0 {
return (0, 0.0, 0.0);
}
let max = groups
.iter()
.flat_map(|group| group[channel].0.iter().copied())
.max()
.unwrap_or(0) as usize;
if scratch.order0_entropy.len() < max + 1 {
scratch.order0_entropy.resize(max + 1, 0);
}
let flat_hist = &mut scratch.order0_entropy[..max + 1];
flat_hist.fill(0);
for group in groups {
for &residual in &group[channel].0 {
flat_hist[residual as usize] += 1;
}
}
let flat = entropy_of_hist(flat_hist, total as u64);
let (h0, h1, h2) = scratch.threshold.make_scratches(max + 1);
let mut best_t = 0i32;
let mut best_bits = f32::INFINITY;
for &t in &[8i64, 16, 24, 32, 48, 64, 96] {
h0.fill(0);
h1.fill(0);
h2.fill(0);
let (mut n0, mut n1, mut n2) = (0u64, 0u64, 0u64);
for group in groups {
let (residuals, properties) = &group[channel];
for (&residual, &property) in residuals.iter().zip(properties.iter()) {
match bucket_of(property, t) {
0 => {
h0[residual as usize] += 1;
n0 += 1;
}
1 => {
h1[residual as usize] += 1;
n1 += 1;
}
_ => {
h2[residual as usize] += 1;
n2 += 1;
}
}
}
}
let bits = entropy_of_hist(h0, n0) + entropy_of_hist(h1, n1) + entropy_of_hist(h2, n2);
if bits < best_bits {
best_bits = bits;
best_t = t as i32;
}
}
(best_t, best_bits, flat)
}
const MA_TARGET_SAMPLES: usize = 1 << 21;
const MA_FULL_SAMPLE_LIMIT: usize = 1 << 22;
const MA_FINAL_TARGET_SAMPLES: usize = 1 << 23;
const MA_FINAL_FULL_SAMPLE_LIMIT: usize = 1 << 24;
const DENSE_FINAL_MIN_BITS_PER_VALUE: f64 = 1.0;
const MA_COARSE_TARGET_SAMPLES: usize = 1 << 16;
const MA_COARSE_MAX_LEAVES: usize = 32;
const MA_DEEPEN_MIN_SAVINGS: f64 = 0.02;
const MA_SPLIT_COST_BITS: f32 = 100.0;
const MA_FINAL_SPLIT_COST_BITS: f32 = 50.0;
const MA_MAX_LEAVES: usize = LZ77_MAX_CONTEXTS - 1;
const MA_MIN_NODE_SAMPLES: usize = 128;
const MA_SIDE_PREDS: usize = 4;
#[derive(Clone, Copy)]
struct MaRefPlane<'a> {
pixels: &'a [i32],
stride: usize,
x0: usize,
y0: usize,
}
#[inline]
fn ref_props(refs: &[MaRefPlane<'_>], x: usize, y: usize, p: &mut [i32; NUM_MA_PROPS]) {
for (r, props) in refs.iter().zip(p[16..].as_chunks_mut::<4>().0) {
let row = &r.pixels[(r.y0 + y) * r.stride + r.x0..];
let v = row[x] as i64;
let left = if x > 0 { row[x - 1] as i64 } else { 0 };
let (top, top_left) = if y > 0 {
let above = &r.pixels[(r.y0 + y - 1) * r.stride + r.x0..];
(
above[x] as i64,
if x > 0 { above[x - 1] as i64 } else { left },
)
} else {
(left, left)
};
let g = (left + top - top_left).clamp(left.min(top), left.max(top));
let residual = v - g;
*props = [
v.abs() as i32,
v as i32,
residual.abs() as i32,
residual as i32,
];
}
}
fn walk_channel_ma<'a, T: Copy + 'a>(
get_row: impl Fn(usize) -> &'a [T],
gw: usize,
gh: usize,
chan: u32,
stream: i32,
refs: &[MaRefPlane<'a>],
wp_params: WpParams,
use_wp: bool,
mut visit: impl FnMut(usize, usize, i64, &[i32; NUM_MA_PROPS], PredictorNeighbors, i64),
) where
i64: From<T>,
{
let disabled = !use_wp;
let mut wp = WpState::with_params(gw, wp_params);
let mut p = [0i32; NUM_MA_PROPS];
p[0] = chan as i32;
p[1] = stream;
let mut north_row: &[T] = &[];
let mut north_north_row: &[T] = &[];
for y in 0..gh {
let current_row = get_row(y);
assert_eq!(current_row.len(), gw);
if y == 0 {
north_row = current_row;
}
if y < 2 {
north_north_row = north_row;
}
assert_eq!(north_row.len(), gw);
assert_eq!(north_north_row.len(), gw);
let row = wp.row_offsets(y);
p[2] = y as i32;
p[9] = 0; macro_rules! visit_pixel {
($predict:ident, $x:expr, $value:expr, $neighbors:expr) => {{
let x = $x;
let value = $value;
let n = $neighbors;
p[3] = x as i32;
p[4] = n.top.abs() as i32;
p[5] = n.left.abs() as i32;
p[6] = n.top as i32;
p[7] = n.left as i32;
p[8] = (n.left - p[9] as i64) as i32;
p[9] = (n.left + n.top - n.top_left) as i32;
p[10] = (n.left - n.top_left) as i32;
p[11] = (n.top_left - n.top) as i32;
p[12] = (n.top - n.top_right) as i32;
p[13] = (n.top - n.top_top) as i32;
p[14] = (n.left - n.left_left) as i32;
let wp_pred = if disabled {
0
} else {
wp.$predict(
value,
x,
row,
WpNeighbors {
north: n.top,
west: n.left,
north_east: n.top_right,
north_west: n.top_left,
north_north: n.top_top,
},
)
};
p[15] = if disabled { 0 } else { wp.wp_prop as i32 };
ref_props(refs, x, y, &mut p);
visit(x, y, value, &p, n, wp_pred);
}};
}
if y == 0 {
if let Some((&first, tail)) = current_row.split_first() {
let first = i64::from(first);
visit_pixel!(
predict_and_update_flat,
0,
first,
PredictorNeighbors {
left: 0,
top: 0,
top_left: 0,
top_right: 0,
left_left: 0,
top_top: 0,
top_right_right: 0,
}
);
let mut left = first;
let mut left_left = first;
for (x, &value) in tail.iter().enumerate() {
let value = i64::from(value);
visit_pixel!(
predict_and_update_flat,
x + 1,
value,
PredictorNeighbors {
left,
top: left,
top_left: left,
top_right: left,
left_left,
top_top: left,
top_right_right: left,
}
);
left_left = left;
left = value;
}
}
} else {
let edge = |x: usize| {
let top = i64::from(north_row[x]);
let left = if x > 0 {
i64::from(current_row[x - 1])
} else {
top
};
let top_right = north_row.get(x + 1).map_or(top, |&v| i64::from(v));
PredictorNeighbors {
left,
top,
top_left: if x > 0 {
i64::from(north_row[x - 1])
} else {
left
},
top_right,
left_left: if x > 1 {
i64::from(current_row[x - 2])
} else {
left
},
top_top: i64::from(north_north_row[x]),
top_right_right: north_row.get(x + 2).map_or(top_right, |&v| i64::from(v)),
}
};
for (x, &value) in current_row.iter().take(2).enumerate() {
visit_pixel!(predict_and_update_flat, x, i64::from(value), edge(x));
}
if gw > 4 {
let mut left = i64::from(current_row[1]);
let mut left_left = i64::from(current_row[0]);
let pixels = current_row[2..gw - 2]
.iter()
.zip(north_row[1..].array_windows::<4>())
.zip(&north_north_row[2..]);
for (x, ((&value, &[nw, n, ne, nee]), &nn)) in pixels.enumerate() {
let value = i64::from(value);
visit_pixel!(
predict_and_update_flat_inlined,
x + 2,
value,
PredictorNeighbors {
left,
top: i64::from(n),
top_left: i64::from(nw),
top_right: i64::from(ne),
left_left,
top_top: i64::from(nn),
top_right_right: i64::from(nee),
}
);
left_left = left;
left = value;
}
}
for x in gw.saturating_sub(2).max(2)..gw {
visit_pixel!(
predict_and_update_flat,
x,
i64::from(current_row[x]),
edge(x)
);
}
}
north_north_row = north_row;
north_row = current_row;
}
}
fn ma_channel_sample_count(w: usize, h: usize, stride: usize) -> usize {
(h / stride) * w + (h % stride) * (w / stride) + (h % stride).min(w % stride)
}
fn sample_channel_ma<'a, T: Copy + 'a>(
get_row: impl Fn(usize) -> &'a [T],
gw: usize,
gh: usize,
chan: u32,
stream: i32,
refs: &[MaRefPlane<'a>],
wp_params: WpParams,
use_wp: bool,
stride: usize,
mut push: impl FnMut([i32; NUM_MA_PROPS], [u8; NUM_MA_PREDS]),
) where
i64: From<T>,
{
if use_wp {
sample_channel_ma_shared::<T, true>(
&get_row, gw, gh, chan, stream, refs, wp_params, stride, &mut push,
);
} else {
sample_channel_ma_shared::<T, false>(
&get_row, gw, gh, chan, stream, refs, wp_params, stride, &mut push,
);
}
}
fn sample_channel_ma_shared<'a, T: Copy + 'a, const USE_WP: bool>(
get_row: &dyn Fn(usize) -> &'a [T],
gw: usize,
gh: usize,
chan: u32,
stream: i32,
refs: &[MaRefPlane<'a>],
wp_params: WpParams,
stride: usize,
push: &mut dyn FnMut([i32; NUM_MA_PROPS], [u8; NUM_MA_PREDS]),
) where
i64: From<T>,
{
debug_assert!(stride != 0);
let disabled = !USE_WP;
let mut wp = WpState::with_params(gw, wp_params);
let mut north_row: &[T] = &[];
let mut north_north_row: &[T] = &[];
for y in 0..gh {
let current_row = get_row(y);
assert_eq!(current_row.len(), gw);
if y == 0 {
north_row = current_row;
}
if y < 2 {
north_north_row = north_row;
}
assert_eq!(north_row.len(), gw);
assert_eq!(north_north_row.len(), gw);
let row = wp.row_offsets(y);
let mut west = 0i64;
let mut west_west = 0i64;
let mut previous_local_gradient = 0i32;
let mut until_sample = 1 + y % stride;
for x in 0..gw {
let value = i64::from(current_row[x]);
let north = if y > 0 { i64::from(north_row[x]) } else { west };
let left = if x > 0 { west } else { north };
let top_left = if x > 0 && y > 0 {
i64::from(north_row[x - 1])
} else {
left
};
let top_right = if x + 1 < gw && y > 0 {
i64::from(north_row[x + 1])
} else {
north
};
let top_top = if y > 1 {
i64::from(north_north_row[x])
} else {
north
};
let wp_pred = if disabled {
0
} else {
let wp_neighbors = WpNeighbors {
north,
west: left,
north_east: top_right,
north_west: top_left,
north_north: top_top,
};
wp.predict_and_update_flat_inlined(value, x, row, wp_neighbors)
};
let local_gradient = (left + north - top_left) as i32;
until_sample -= 1;
if until_sample == 0 {
until_sample = stride;
let neighbors = PredictorNeighbors {
left,
top: north,
top_left,
top_right,
left_left: if x > 1 { west_west } else { left },
top_top,
top_right_right: if x + 2 < gw && y > 0 {
i64::from(north_row[x + 2])
} else {
top_right
},
};
let mut props = [0i32; NUM_MA_PROPS];
props[0] = chan as i32;
props[1] = stream;
props[2] = y as i32;
props[3] = x as i32;
props[4] = north.abs() as i32;
props[5] = left.abs() as i32;
props[6] = north as i32;
props[7] = left as i32;
props[8] = (left - previous_local_gradient as i64) as i32;
props[9] = local_gradient;
props[10] = (left - top_left) as i32;
props[11] = (top_left - north) as i32;
props[12] = (north - top_right) as i32;
props[13] = (north - top_top) as i32;
props[14] = (left - neighbors.left_left) as i32;
props[15] = if disabled { 0 } else { wp.wp_prop as i32 };
ref_props(refs, x, y, &mut props);
let mut tok = [0u8; NUM_MA_PREDS];
for pred in 0..NUM_MA_PREDS as u32 {
let pv = predictor_value(pred, neighbors, wp_pred);
let (t, _, _) = uint_encode(pack_signed((value - pv) as i32));
tok[pred as usize] = t.min(u8::MAX as u32) as u8;
}
push(props, tok);
}
previous_local_gradient = local_gradient;
west_west = west;
west = value;
}
north_north_row = north_row;
north_row = current_row;
}
}
fn tokenize_channel_ma<'a, T: Copy + 'a>(
get_row: impl Fn(usize) -> &'a [T],
gw: usize,
gh: usize,
chan: u32,
stream: i32,
refs: &[MaRefPlane<'a>],
wp_params: WpParams,
use_wp: bool,
lookup: &MaLookup,
offsets: &[i32],
out: &mut RawTokens,
) where
i64: From<T>,
{
let mut row = Vec::with_capacity(gw);
walk_channel_ma(
get_row,
gw,
gh,
chan,
stream,
refs,
wp_params,
use_wp && lookup.needs_wp(),
|x, _y, v, p, n, wp_pred| {
let (context, pred) = lookup.lookup(p);
let pv = predictor_value(pred, n, wp_pred);
row.push(Token::new(
context,
pack_signed((v - pv) as i32 - offsets[context as usize]),
));
if x + 1 == gw {
out.extend(&row);
row.clear();
}
},
);
}
fn emit_learned_tree(tree: &LearnedTree) -> (Vec<Token>, Vec<u32>, u32) {
use std::collections::VecDeque;
let mut tokens = Vec::new();
let mut leaf_ctx = vec![u32::MAX; tree.nodes.len()];
let mut q: VecDeque<u32> = VecDeque::new();
q.push_back(0);
let mut ctx = 0u32;
while let Some(i) = q.pop_front() {
match tree.nodes[i as usize] {
MaNode::Split { prop, val, gt, le } => {
push_split(&mut tokens, prop as u32, val);
q.push_back(gt);
q.push_back(le);
}
MaNode::Leaf { pred } => {
push_leaf(&mut tokens, pred);
leaf_ctx[i as usize] = ctx;
ctx += 1;
}
}
}
(tokens, leaf_ctx, ctx)
}
const MA_LEAF_OFFSET_LIMIT: i32 = 8;
const MA_LEAF_EXACT_SYMBOLS: u32 = 16;
const MA_LEAF_OFFSET_MIN_SAMPLES: u32 = 16;
const MA_LEAF_OFFSET_MAX_ZERO_FRACTION: f64 = 0.9;
fn unpack_signed(token: u32) -> i32 {
if token & 1 == 1 {
-(((token + 1) >> 1) as i32)
} else {
(token >> 1) as i32
}
}
fn leaf_offsets<'a>(
tree: &LearnedTree,
leaf_ctx: &[u32],
num_ctx: u32,
samples: impl Iterator<Item = (&'a [i32; NUM_MA_PROPS], &'a [u8; NUM_MA_PREDS])>,
) -> Vec<i32> {
const BINS: usize = 2 * MA_LEAF_OFFSET_LIMIT as usize + 1;
let mut hist = vec![[0u32; BINS]; num_ctx as usize];
let mut routed = 0u64;
for (props, tok) in samples {
let (node, pred) = tree.lookup(props);
routed += 1;
let symbol = tok[pred as usize] as u32;
if symbol < MA_LEAF_EXACT_SYMBOLS {
let r = unpack_signed(symbol);
hist[leaf_ctx[node as usize] as usize][(r + MA_LEAF_OFFSET_LIMIT) as usize] += 1;
}
}
let zeros: u64 = hist
.iter()
.map(|h| h[MA_LEAF_OFFSET_LIMIT as usize] as u64)
.sum();
if zeros as f64 > MA_LEAF_OFFSET_MAX_ZERO_FRACTION * routed as f64 {
return vec![0; num_ctx as usize];
}
hist.iter()
.map(|h| {
let total: u32 = h.iter().sum();
if total < MA_LEAF_OFFSET_MIN_SAMPLES {
return 0;
}
let half = total.div_ceil(2);
let mut acc = 0u32;
for (bin, &c) in h.iter().enumerate() {
acc += c;
if acc >= half {
return bin as i32 - MA_LEAF_OFFSET_LIMIT;
}
}
0
})
.collect()
}
fn ma_sample_stride(total_px: usize, target_samples: usize, full_sample_limit: usize) -> usize {
let mut stride = total_px.div_ceil(target_samples).max(1);
if stride == 1 && total_px > full_sample_limit {
stride = 3;
}
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
stride
}
fn gate_ma_tree(
tree: LearnedTree,
sample_scale: f64,
samples: Option<&MaSamples>,
) -> Option<LearnedCandidate> {
let mut cand = finish_ma_candidate(tree, sample_scale);
if cand.est_real.partial_cmp(&cand.flat_real) != Some(std::cmp::Ordering::Less) {
return None;
}
if let Some(samples) = samples {
cand.set_leaf_offsets(samples.props.iter().zip(&samples.tok).step_by(4));
}
Some(cand)
}
fn finish_ma_candidate(tree: LearnedTree, sample_scale: f64) -> LearnedCandidate {
let (tree_tokens, leaf_ctx, num_ctx) = emit_learned_tree(&tree);
let overhead_bits =
tree_tokens.len() as f64 * 10.0 + (num_ctx.min(128) as f64) * 200.0 + num_ctx as f64 * 8.0;
let est_real = tree.est_bits * sample_scale + overhead_bits;
let flat_real = tree.flat_bits * sample_scale;
let leaf_offset = vec![0; num_ctx as usize];
let estimated_savings = 1.0 - tree.est_bits / tree.flat_bits.max(f64::MIN_POSITIVE);
LearnedCandidate {
tree,
tree_tokens,
leaf_ctx,
leaf_offset,
num_ctx,
est_real,
flat_real,
estimated_savings,
}
}
fn ma_learn_params_final(
min_symbol: u32,
max_leaves: usize,
max_candidates: usize,
split_scale: f64,
use_wp: bool,
) -> MaLearnParams {
let mut params = ma_learn_params(min_symbol, max_leaves, max_candidates, split_scale, use_wp);
params.split_cost_bits = MA_FINAL_SPLIT_COST_BITS / split_scale as f32;
params
}
fn ma_learn_params(
min_symbol: u32,
max_leaves: usize,
max_candidates: usize,
split_scale: f64,
use_wp: bool,
) -> MaLearnParams {
MaLearnParams {
alphabet: min_symbol as usize,
max_leaves,
split_cost_bits: MA_SPLIT_COST_BITS / split_scale as f32,
min_node: MA_MIN_NODE_SAMPLES,
allow_wp: use_wp,
allowed_preds: u16::MAX,
side_preds: MA_SIDE_PREDS,
max_candidates,
}
}
struct CoarseLearn {
samples: MaSamples,
stride: usize,
max_candidates: usize,
leaf_offsets: bool,
candidate: LearnedCandidate,
deepen: bool,
}
fn learn_ma_coarse(
samples: MaSamples,
stride: usize,
min_symbol: u32,
use_wp: bool,
max_leaves: usize,
max_candidates: usize,
leaf_offsets: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
if samples.len() < 4 * MA_MIN_NODE_SAMPLES {
return None;
}
if samples.len() <= MA_COARSE_TARGET_SAMPLES {
let tree = learn_ma_tree(
&samples,
ma_learn_params(
min_symbol,
max_leaves,
max_candidates,
stride as f64,
use_wp,
),
pool,
scratch,
);
let candidate = gate_ma_tree(tree, stride as f64, leaf_offsets.then_some(&samples))?;
return Some(CoarseLearn {
samples,
stride,
max_candidates,
leaf_offsets,
candidate,
deepen: false,
});
}
let coarse_indices = samples.evenly_sampled_indices(MA_COARSE_TARGET_SAMPLES);
let coarse_scale = stride as f64 * samples.len() as f64 / coarse_indices.len() as f64;
let coarse_tree = learn_ma_tree_indexed(
&samples,
coarse_indices,
ma_learn_params(
min_symbol,
MA_COARSE_MAX_LEAVES,
max_candidates,
coarse_scale,
use_wp,
),
pool,
scratch,
);
let candidate = gate_ma_tree(coarse_tree, coarse_scale, None)?;
let coarse_leaves = candidate.tree.nodes.len().div_ceil(2);
let coarse_savings = 1.0 - candidate.est_real / candidate.flat_real;
let deepen = coarse_leaves == MA_COARSE_MAX_LEAVES && coarse_savings >= MA_DEEPEN_MIN_SAVINGS;
Some(CoarseLearn {
samples,
stride,
max_candidates,
leaf_offsets,
candidate,
deepen,
})
}
fn finish_ma_learn(
coarse: CoarseLearn,
min_symbol: u32,
use_wp: bool,
max_leaves: usize,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedCandidate {
if !coarse.deepen {
return coarse.candidate;
}
let (deep_tree, samples) = deepen_ma_tree(
coarse.samples,
ma_learn_params_final(
min_symbol,
max_leaves,
coarse.max_candidates,
coarse.stride as f64,
use_wp,
),
coarse.candidate.tree.clone(),
pool,
scratch,
);
gate_ma_tree(
deep_tree,
coarse.stride as f64,
coarse.leaf_offsets.then_some(&samples),
)
.unwrap_or(coarse.candidate)
}
const WP_RANK_MIN_ROW_SHARE: f64 = 0.02;
const WP_RANK_MIN_SPLIT_SHARE: f64 = 0.15;
fn wp_matters(stage: &CoarseLearn) -> bool {
let tree = &stage.candidate.tree;
let (mut splits, mut wp_splits) = (0usize, 0usize);
for node in &tree.nodes {
if let crate::ma_tree::MaNode::Split { prop, .. } = node {
splits += 1;
wp_splits += usize::from(*prop as usize == PROP_WP as usize);
}
}
if wp_splits as f64 >= WP_RANK_MIN_SPLIT_SHARE * splits as f64 && wp_splits > 0 {
return true;
}
let mut rows = 0usize;
let mut wp_rows = 0usize;
for props in stage.samples.props.iter().step_by(16) {
rows += 1;
if tree.lookup(props).1 as usize == crate::ma_tree::PRED_WEIGHTED {
wp_rows += 1;
}
}
wp_rows as f64 >= WP_RANK_MIN_ROW_SHARE * rows as f64
}
#[allow(clippy::too_many_arguments)]
fn rank_presets(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
min_symbol: u32,
use_wp: bool,
first: Option<CoarseLearn>,
first_params: WpParams,
header_bits: &dyn Fn(WpParams) -> f64,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> (f64, f64, WpParams) {
let mut best_bits = f64::INFINITY;
let mut best_coarse = f64::INFINITY;
let mut best_params = first_params;
let mut order: Vec<WpParams> = vec![first_params];
if use_wp && first.as_ref().is_none_or(wp_matters) {
for &preset in [1usize, 2, 3, 0].iter().map(|&i| &WpParams::PRESETS[i]) {
if preset != first_params {
order.push(preset);
}
}
}
let mut first = first;
for preset in order {
let stage = match first.take() {
Some(stage) => Some(stage),
None => rank_coarse(
source, xsize, ysize, min_symbol, preset, use_wp, pool, scratch,
),
};
let Some(stage) = stage else {
continue;
};
let coarse = stage.candidate.est_real + header_bits(preset);
if coarse > best_coarse * RANK_COARSE_PRUNE {
continue;
}
best_coarse = best_coarse.min(coarse);
let bits = rank_bits(&stage) + header_bits(preset);
if bits < best_bits {
best_bits = bits;
best_params = preset;
}
}
(best_bits, best_coarse, best_params)
}
struct LearnedCandidate {
tree: LearnedTree,
tree_tokens: Vec<Token>,
leaf_ctx: Vec<u32>,
leaf_offset: Vec<i32>,
num_ctx: u32,
est_real: f64,
flat_real: f64,
estimated_savings: f64,
}
impl LearnedCandidate {
fn set_leaf_offsets<'a>(
&mut self,
samples: impl Iterator<Item = (&'a [i32; NUM_MA_PROPS], &'a [u8; NUM_MA_PREDS])>,
) {
self.leaf_offset = leaf_offsets(&self.tree, &self.leaf_ctx, self.num_ctx, samples);
for (token, &offset) in self
.tree_tokens
.iter_mut()
.filter(|token| token.context == TREE_CTX_OFFSET)
.zip(&self.leaf_offset)
{
token.value = pack_signed(offset);
}
}
}
struct MaChannel<'a> {
w: usize,
h: usize,
meta: bool,
pixels: MaPixels<'a>,
}
enum MaPixels<'a> {
U8(&'a [u8]),
U16(&'a [u16]),
I32(&'a [i32]),
}
macro_rules! with_ma_pixels {
($channel:expr, |$pixels:ident| $body:expr) => {
match &$channel.pixels {
MaPixels::U8($pixels) => $body,
MaPixels::U16($pixels) => $body,
MaPixels::I32($pixels) => $body,
}
};
}
pub(super) const MA_PHOTO_CANDIDATES: usize = 32;
pub(super) const MA_PALETTE_CANDIDATES: usize = 16;
#[derive(Clone, Copy)]
enum MaTransform {
Rct(u32),
Palette { num_c: u32, nb_colors: u32 },
}
struct MaSource<'a> {
channels: Vec<MaChannel<'a>>,
transform: MaTransform,
group_channels: Vec<Option<MaGroupChannels<'a>>>,
}
struct MaGroupChannels<'a> {
channels: Vec<MaChannel<'a>>,
nb_colors: u32,
num_c: u32,
}
const MODULAR_NUM_QUANT_TABLES: usize = 17;
fn ac_stream_id(num_dc_groups: usize, group_index: usize) -> i32 {
(1 + 3 * num_dc_groups + MODULAR_NUM_QUANT_TABLES + group_index) as i32
}
struct MaPlacement {
channel: usize,
chan_id: u32,
global: bool,
}
impl MaSource<'_> {
fn max_candidates(&self) -> usize {
match self.transform {
MaTransform::Palette { .. } => MA_PALETTE_CANDIDATES,
MaTransform::Rct(_) => MA_PHOTO_CANDIDATES,
}
}
fn deep_lz_max_ratio(&self) -> f64 {
match self.transform {
MaTransform::Rct(_) if self.group_channels.iter().all(Option::is_none) => {
LZ_DEEP_MATCHER_MAX_RATIO_RCT
}
_ => LZ_DEEP_MATCHER_MAX_RATIO_PALETTE,
}
}
fn write_transforms(&self, w: &mut BitWriter) {
match self.transform {
MaTransform::Rct(rct_type) => {
write_modular_transforms(self.channels.len(), rct_type, w)
}
MaTransform::Palette { num_c, nb_colors } => {
write_palette_transform(num_c, nb_colors, w)
}
}
}
fn placement(&self, layout: GroupLayout, single_group: bool) -> Vec<MaPlacement> {
let gdim = layout.dim();
let mut global_id = 0u32;
let mut group_id = 0u32;
self.channels
.iter()
.enumerate()
.map(|(channel, ch)| {
let global = single_group || ch.meta || (ch.w <= gdim && ch.h <= gdim);
let chan_id = if single_group {
channel as u32
} else if global {
let id = global_id;
global_id += 1;
id
} else {
let id = group_id;
group_id += 1;
id
};
MaPlacement {
channel,
chan_id,
global,
}
})
.collect()
}
fn total_values(&self) -> usize {
self.channels.iter().map(|c| c.w * c.h).sum()
}
fn group_override(&self, group_index: usize) -> Option<&MaGroupChannels<'_>> {
self.group_channels
.get(group_index)
.and_then(Option::as_ref)
}
fn channel_at(&self, group_override: Option<usize>, channel: usize) -> &MaChannel<'_> {
match group_override {
Some(group_index) => {
&self
.group_override(group_index)
.expect("override group")
.channels[channel]
}
None => &self.channels[channel],
}
}
fn ref_planes(
&self,
placement: &[MaPlacement],
p: &MaPlacement,
x0: usize,
y0: usize,
) -> Vec<MaRefPlane<'_>> {
let ch = &self.channels[p.channel];
placement[..p.channel]
.iter()
.rev()
.filter(|q| q.global == p.global)
.filter_map(|q| {
let other = &self.channels[q.channel];
match other.pixels {
MaPixels::I32(pixels) if other.w == ch.w && other.h == ch.h => {
Some(MaRefPlane {
pixels,
stride: other.w,
x0,
y0,
})
}
_ => None,
}
})
.take(MA_REF_CHANNELS)
.collect()
}
}
fn mixed_ma_source<'a>(
ycocg: &'a Image3Si,
alpha: Option<&'a AlphaPlane>,
xsize: usize,
palettes: &'a [Option<palette::LocalPaletteGroup>],
) -> MaSource<'a> {
let mut source = rgb_ma_source(ycocg, alpha, xsize, 6);
source.group_channels = palettes
.iter()
.map(|palette| {
let palette = palette.as_ref()?;
let num_c = palette.palette.len() / palette.nb_colors;
Some(MaGroupChannels {
channels: vec![
MaChannel {
w: palette.nb_colors,
h: num_c,
meta: true,
pixels: MaPixels::I32(&palette.palette),
},
MaChannel {
w: palette.w,
h: palette.h,
meta: false,
pixels: MaPixels::U16(&palette.indices),
},
],
nb_colors: palette.nb_colors as u32,
num_c: num_c as u32,
})
})
.collect();
source
}
fn rgb_ma_source<'a>(
linear: &'a Image3Si,
alpha: Option<&'a AlphaPlane>,
xsize: usize,
rct_type: u32,
) -> MaSource<'a> {
let ysize = linear.ysize();
let mut channels: Vec<MaChannel<'a>> = (0..3)
.map(|c| {
let pd = linear.plane_data(c);
MaChannel {
w: xsize,
h: ysize,
meta: false,
pixels: MaPixels::I32(pd),
}
})
.collect();
if let Some(a) = alpha {
channels.push(MaChannel {
w: xsize,
h: ysize,
meta: false,
pixels: match a {
AlphaPlane::U8(pixels) => MaPixels::U8(pixels),
AlphaPlane::U16 { data, .. } => MaPixels::U16(data),
AlphaPlane::F32(pixels) => MaPixels::I32(pixels),
},
});
}
MaSource {
channels,
transform: MaTransform::Rct(rct_type),
group_channels: Vec::new(),
}
}
const PATCH_MIN_COVERAGE: f64 = 0.05;
const PALETTE_LAYOUT_MARGIN: f64 = 1.04;
const RANK_MIN_VALUES: usize = 1 << 19;
const RGB_SINGLE_LAYOUT_MIN_VALUES: usize = 1 << 20;
fn source_values_of(xsize: usize, ysize: usize, nb_chans: usize) -> usize {
xsize * ysize * nb_chans
}
const PER_GROUP_MARGIN: f64 = 1.0;
#[allow(clippy::too_many_arguments)]
fn learn_ma_candidate(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
layout: GroupLayout,
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
max_leaves: usize,
target_samples: usize,
full_sample_limit: usize,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
let gdim = layout.dim();
let xsize_groups = xsize.div_ceil(gdim);
let num_groups = xsize_groups * ysize.div_ceil(gdim);
let placement = source.placement(layout, num_groups == 1);
let max_candidates = source.max_candidates();
let stride = ma_sample_stride(source.total_values(), target_samples, full_sample_limit);
struct Job<'a> {
channel: usize,
chan_id: u32,
stream: i32,
refs: Vec<MaRefPlane<'a>>,
group_override: Option<usize>,
x0: usize,
y0: usize,
w: usize,
h: usize,
}
let num_dc_groups = xsize.div_ceil(layout.lf_dim()) * ysize.div_ceil(layout.lf_dim());
let mut jobs: Vec<Job> = Vec::new();
for p in placement.iter().filter(|p| p.global) {
let ch = &source.channels[p.channel];
jobs.push(Job {
channel: p.channel,
chan_id: p.chan_id,
stream: 0,
refs: source.ref_planes(&placement, p, 0, 0),
group_override: None,
x0: 0,
y0: 0,
w: ch.w,
h: ch.h,
});
}
if num_groups > 1 {
for group_index in 0..num_groups {
let x0 = (group_index % xsize_groups) * gdim;
let y0 = (group_index / xsize_groups) * gdim;
if let Some(over) = source.group_override(group_index) {
for (channel, ch) in over.channels.iter().enumerate() {
jobs.push(Job {
channel,
chan_id: channel as u32,
stream: ac_stream_id(num_dc_groups, group_index),
refs: Vec::new(),
group_override: Some(group_index),
x0: 0,
y0: 0,
w: ch.w,
h: ch.h,
});
}
continue;
}
for p in placement.iter().filter(|p| !p.global) {
let ch = &source.channels[p.channel];
jobs.push(Job {
channel: p.channel,
chan_id: p.chan_id,
stream: ac_stream_id(num_dc_groups, group_index),
refs: source.ref_planes(&placement, p, x0, y0),
group_override: None,
x0,
y0,
w: gdim.min(ch.w - x0),
h: gdim.min(ch.h - y0),
});
}
}
}
let counts: Vec<usize> = jobs
.iter()
.map(|job| ma_channel_sample_count(job.w, job.h, stride))
.collect();
let total_samples = counts.iter().sum();
let mut samples = MaSamples {
props: vec![[0; NUM_MA_PROPS]; total_samples],
tok: vec![[0; NUM_MA_PREDS]; total_samples],
};
let mut props = samples.props.as_mut_slice();
let mut tok = samples.tok.as_mut_slice();
let mut ranges = Vec::with_capacity(jobs.len());
for count in counts {
let (p, rest_p) = props.split_at_mut(count);
let (t, rest_t) = tok.split_at_mut(count);
ranges.push((p, t));
(props, tok) = (rest_p, rest_t);
}
pool.steal_for_each_mut(scratch, &mut ranges, |i, range, _scratch| {
let job = &jobs[i];
let ch = source.channel_at(job.group_override, job.channel);
let mut rows = range.0.iter_mut().zip(range.1.iter_mut());
with_ma_pixels!(ch, |pixels| sample_channel_ma(
|y| &pixels[(job.y0 + y) * ch.w + job.x0..][..job.w],
job.w,
job.h,
job.chan_id,
job.stream,
&job.refs,
wp_params,
use_wp,
stride,
|p, t| {
let (props, tok) = rows.next().expect("sample count");
*props = p;
*tok = t;
},
));
debug_assert!(rows.next().is_none());
});
learn_ma_coarse(
samples,
stride,
min_symbol,
use_wp,
max_leaves,
max_candidates,
matches!(source.transform, MaTransform::Rct(_)),
pool,
scratch,
)
}
const MA_RANK_LEAVES: usize = MA_COARSE_MAX_LEAVES;
const RCT_RANK_MARGIN: f32 = 1.02;
const MA_RANK_SAMPLE_LIMIT: usize = MA_FULL_SAMPLE_LIMIT;
const RANK_COARSE_PRUNE: f64 = 1.005;
#[allow(clippy::too_many_arguments)]
fn rank_coarse(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<CoarseLearn> {
learn_ma_candidate(
source,
xsize,
ysize,
GroupLayout::LARGE,
min_symbol,
wp_params,
use_wp,
MA_RANK_LEAVES,
MA_TARGET_SAMPLES,
MA_RANK_SAMPLE_LIMIT,
pool,
scratch,
)
}
fn rank_bits(stage: &CoarseLearn) -> f64 {
stage.candidate.est_real.min(stage.candidate.flat_real)
}
#[allow(clippy::too_many_arguments)]
fn learn_best_layout(
source: &MaSource<'_>,
xsize: usize,
ysize: usize,
layouts: &[GroupLayout],
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
coarse_limit: f64,
final_limit: f64,
deepen_all: bool,
sampling: (usize, usize),
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<(GroupLayout, LearnedCandidate, f64)> {
let mut best_coarse_est = f64::INFINITY;
let mut learned: Option<(GroupLayout, LearnedCandidate)> = None;
for (index, &layout) in layouts.iter().enumerate() {
if index > 0
&& let Some((_, best)) = &learned
&& best.est_real > final_limit
{
break;
}
let Some(stage) = learn_ma_candidate(
source,
xsize,
ysize,
layout,
min_symbol,
wp_params,
use_wp,
MA_MAX_LEAVES,
sampling.0,
sampling.1,
pool,
scratch,
) else {
continue;
};
let coarse_est = stage.candidate.est_real;
let layout_pruned = index > 0 && !deepen_all && coarse_est > best_coarse_est;
if coarse_est > coarse_limit || layout_pruned {
best_coarse_est = best_coarse_est.min(coarse_est);
continue;
}
best_coarse_est = best_coarse_est.min(coarse_est);
let cand = finish_ma_learn(stage, min_symbol, use_wp, MA_MAX_LEAVES, pool, scratch);
if learned
.as_ref()
.is_none_or(|(_, best)| cand.est_real < best.est_real)
{
learned = Some((layout, cand));
}
}
learned.map(|(layout, cand)| (layout, cand, best_coarse_est))
}
macro_rules! with_raw_streams {
($raw:expr, |$streams:ident| $body:block) => {
match RawTokenStreams::new($raw) {
RawTokenStreams::Compact($streams) => $body,
RawTokenStreams::Wide($streams) => $body,
}
};
}
#[allow(clippy::too_many_arguments)]
fn write_learned_tree_frame(
source: &MaSource<'_>,
has_alpha: bool,
frame_kind: ModularFrameKind<'_>,
xsize: usize,
ysize: usize,
layout: GroupLayout,
min_symbol: u32,
pool: &ThreadPool,
scratch: &mut CoderScratch,
wp_params: WpParams,
use_wp: bool,
cand: &LearnedCandidate,
local_trees: bool,
writer: &mut BitWriter,
) -> f64 {
let gdim = layout.dim();
let xsize_groups = xsize.div_ceil(gdim);
let ysize_groups = ysize.div_ceil(gdim);
let num_ac_groups = xsize_groups * ysize_groups;
let num_dc_groups = xsize.div_ceil(layout.lf_dim()) * ysize.div_ceil(layout.lf_dim());
let single_group = num_ac_groups == 1;
let placement = source.placement(layout, single_group);
let num_ctx = cand.num_ctx;
let distance_ctx = num_ctx;
let tokenize = |p: &MaPlacement,
stream: i32,
x0: usize,
y0: usize,
w: usize,
h: usize,
out: &mut RawTokens| {
tokenize_ma_rect(
source, &placement, p, stream, x0, y0, w, h, cand, wp_params, use_wp, out,
);
};
write_frame_header_modular_kind(has_alpha, frame_kind, layout, writer);
let dictionary: Option<BitWriter> = match frame_kind {
ModularFrameKind::Patched(references) => {
let mut w = BitWriter::new();
write_patch_dictionary(references, has_alpha, scratch, &mut w);
Some(w)
}
_ => None,
};
let dictionary = dictionary.as_ref();
if single_group {
let channel_tokens = pool.steal_map(scratch, placement.len(), |i, _scratch| {
let p = &placement[i];
let ch = &source.channels[p.channel];
let mut tokens = RawTokens::with_capacity(ch.w * ch.h);
tokenize(p, 0, 0, 0, ch.w, ch.h, &mut tokens);
tokens
});
let mut section = with_raw_streams!(channel_tokens, |channel_tokens| {
let mut tokens = Vec::with_capacity(source.total_values());
for channel in channel_tokens {
tokens.extend(channel);
}
let variants = choose_tree_streams(
vec![tokens],
distance_ctx,
num_ctx as usize + 1,
min_symbol,
source.deep_lz_max_ratio(),
pool,
scratch,
);
let mut best: Option<BitWriter> = None;
let mut best_estimate = f64::INFINITY;
for variant in variants {
match variant {
TreeStreams::Literals(streams) => {
let stream = streams.into_iter().next().expect("one stream");
write_learned_single_variant(
&stream,
source,
cand,
min_symbol,
wp_params,
dictionary,
pool,
scratch,
&mut best,
&mut best_estimate,
);
}
TreeStreams::Lz(streams) => {
let stream = streams.into_iter().next().expect("one stream");
write_learned_single_variant(
&stream,
source,
cand,
min_symbol,
wp_params,
dictionary,
pool,
scratch,
&mut best,
&mut best_estimate,
);
}
}
}
best.expect("learned-tree section")
});
writer.write(1, 0);
writer.zero_pad_to_byte();
write_toc_entry(section.bits_written() / 8, writer);
writer.zero_pad_to_byte();
writer.append_byte_aligned(std::slice::from_mut(&mut section));
writer.zero_pad_to_byte();
return cand.estimated_savings;
}
let mut global_tokens = RawTokens::with_capacity(0);
for p in placement.iter().filter(|p| p.global) {
let ch = &source.channels[p.channel];
tokenize(p, 0, 0, 0, ch.w, ch.h, &mut global_tokens);
}
let has_global_stream = !global_tokens.is_empty();
let group_placement: Vec<&MaPlacement> = placement.iter().filter(|p| !p.global).collect();
let group_tokens: Vec<RawTokens> = pool.steal_map_with_threads(
scratch,
num_ac_groups,
group_lz_threads(crate::Speed::Slow, pool),
|group_index, _scratch| {
let x0 = (group_index % xsize_groups) * gdim;
let y0 = (group_index / xsize_groups) * gdim;
if let Some(over) = source.group_override(group_index) {
let num_values = over.channels.iter().map(|ch| ch.w * ch.h).sum();
let mut toks = RawTokens::with_capacity(num_values);
for (chan_id, ch) in over.channels.iter().enumerate() {
tokenize_ma_group_channel(
ch,
chan_id as u32,
ac_stream_id(num_dc_groups, group_index),
cand,
wp_params,
use_wp,
&mut toks,
);
}
return toks;
}
let num_values = group_placement
.iter()
.map(|p| {
let ch = &source.channels[p.channel];
gdim.min(ch.w - x0) * gdim.min(ch.h - y0)
})
.sum();
let mut toks = RawTokens::with_capacity(num_values);
for p in &group_placement {
let ch = &source.channels[p.channel];
let gw = gdim.min(ch.w - x0);
let gh = gdim.min(ch.h - y0);
tokenize(
p,
ac_stream_id(num_dc_groups, group_index),
x0,
y0,
gw,
gh,
&mut toks,
);
}
toks
},
);
let mut all_tokens: Vec<RawTokens> = Vec::with_capacity(1 + num_ac_groups);
all_tokens.push(global_tokens);
all_tokens.extend(group_tokens);
let mut sections = with_raw_streams!(all_tokens, |all_tokens| {
let variants = choose_tree_streams(
all_tokens,
distance_ctx,
num_ctx as usize + 1,
min_symbol,
source.deep_lz_max_ratio(),
pool,
scratch,
);
let mut best: Option<Vec<BitWriter>> = None;
let mut best_bits = usize::MAX;
let mut best_estimate = f64::INFINITY;
for variant in variants {
match variant {
TreeStreams::Literals(streams) => {
write_learned_grouped_variant(
&streams,
source,
cand,
min_symbol,
wp_params,
pool,
scratch,
num_ac_groups,
num_dc_groups,
has_global_stream,
dictionary,
&mut best,
&mut best_bits,
&mut best_estimate,
);
}
TreeStreams::Lz(streams) => {
write_learned_grouped_variant(
&streams,
source,
cand,
min_symbol,
wp_params,
pool,
scratch,
num_ac_groups,
num_dc_groups,
has_global_stream,
dictionary,
&mut best,
&mut best_bits,
&mut best_estimate,
);
}
}
}
best.expect("learned-tree sections")
});
let local_gate = local_trees
&& cand.num_ctx as usize >= LOCAL_TREE_MIN_GLOBAL_LEAVES
&& cand.est_real <= LOCAL_TREE_MAX_BITS_PER_VALUE * source.total_values() as f64;
if !has_global_stream
&& local_gate
&& let Some(local) = write_local_tree_sections(
source,
&placement,
xsize,
ysize,
layout,
num_dc_groups,
min_symbol,
wp_params,
use_wp,
dictionary,
pool,
scratch,
)
{
let global_bits: usize = sections.iter().map(BitWriter::bits_written).sum();
let local_bits: usize = local.iter().map(BitWriter::bits_written).sum();
if local_bits < global_bits {
sections = local;
}
}
writer.write(1, 0);
writer.zero_pad_to_byte();
for s in §ions {
write_toc_entry(s.bits_written() / 8, writer);
}
writer.zero_pad_to_byte();
writer.append_byte_aligned(&mut sections);
writer.zero_pad_to_byte();
cand.estimated_savings
}
#[allow(clippy::too_many_arguments)]
fn tokenize_ma_group_channel(
ch: &MaChannel<'_>,
chan_id: u32,
stream: i32,
cand: &LearnedCandidate,
wp_params: WpParams,
use_wp: bool,
out: &mut RawTokens,
) {
let lookup = MaLookup::new(&cand.tree, &cand.leaf_ctx, chan_id, stream);
with_ma_pixels!(ch, |pixels| tokenize_channel_ma(
|y| &pixels[y * ch.w..][..ch.w],
ch.w,
ch.h,
chan_id,
stream,
&[],
wp_params,
use_wp,
&lookup,
&cand.leaf_offset,
out,
));
}
fn tokenize_ma_rect(
source: &MaSource<'_>,
placement: &[MaPlacement],
p: &MaPlacement,
stream: i32,
x0: usize,
y0: usize,
w: usize,
h: usize,
cand: &LearnedCandidate,
wp_params: WpParams,
use_wp: bool,
out: &mut RawTokens,
) {
let ch = &source.channels[p.channel];
let lookup = MaLookup::new(&cand.tree, &cand.leaf_ctx, p.chan_id, stream);
let refs = source.ref_planes(placement, p, x0, y0);
with_ma_pixels!(ch, |pixels| tokenize_channel_ma(
|y| &pixels[(y0 + y) * ch.w + x0..][..w],
w,
h,
p.chan_id,
stream,
&refs,
wp_params,
use_wp,
&lookup,
&cand.leaf_offset,
out,
));
}
const LOCAL_TREE_TARGET_SAMPLES: usize = 1 << 20;
const LOCAL_TREE_LEARN_LANES: usize = 4;
const LOCAL_TREE_MIN_GLOBAL_LEAVES: usize = MA_MAX_LEAVES / 2;
const LOCAL_TREE_MAX_BITS_PER_VALUE: f64 = 0.5;
#[allow(clippy::too_many_arguments)]
fn write_local_tree_sections(
source: &MaSource<'_>,
placement: &[MaPlacement],
xsize: usize,
ysize: usize,
layout: GroupLayout,
num_dc_groups: usize,
min_symbol: u32,
wp_params: WpParams,
use_wp: bool,
dictionary: Option<&BitWriter>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<Vec<BitWriter>> {
let gdim = layout.dim();
let xsize_groups = xsize.div_ceil(gdim);
let ysize_groups = ysize.div_ceil(gdim);
let num_ac_groups = xsize_groups * ysize_groups;
if num_ac_groups < 2 || placement.iter().any(|p| p.global) {
return None;
}
let target = LOCAL_TREE_TARGET_SAMPLES;
let max_candidates = source.max_candidates();
let leaf_offsets = matches!(source.transform, MaTransform::Rct(_));
let group_rect = |group_index: usize| {
let x0 = (group_index % xsize_groups) * gdim;
let y0 = (group_index / xsize_groups) * gdim;
(x0, y0)
};
let cands: Vec<LearnedCandidate> = pool.steal_map_with_threads(
scratch,
num_ac_groups,
LOCAL_TREE_LEARN_LANES,
|group_index, scratch| {
let (x0, y0) = group_rect(group_index);
let stream = ac_stream_id(num_dc_groups, group_index);
let group_values: usize = placement
.iter()
.map(|p| {
let ch = &source.channels[p.channel];
gdim.min(ch.w - x0) * gdim.min(ch.h - y0)
})
.sum();
let mut stride = group_values.div_ceil(target).max(1);
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
let capacity = placement
.iter()
.map(|p| {
let ch = &source.channels[p.channel];
ma_channel_sample_count(gdim.min(ch.w - x0), gdim.min(ch.h - y0), stride)
})
.sum();
let mut samples = MaSamples::with_capacity(capacity);
for p in placement {
let ch = &source.channels[p.channel];
let gw = gdim.min(ch.w - x0);
let gh = gdim.min(ch.h - y0);
let refs = source.ref_planes(placement, p, x0, y0);
with_ma_pixels!(ch, |pixels| sample_channel_ma(
|y| &pixels[(y0 + y) * ch.w + x0..][..gw],
gw,
gh,
p.chan_id,
stream,
&refs,
wp_params,
use_wp,
stride,
|props, tok| {
samples.props.push(props);
samples.tok.push(tok);
},
));
}
let max_leaves = if samples.len() < 4 * MA_MIN_NODE_SAMPLES {
1
} else {
MA_MAX_LEAVES
};
let offsets = (leaf_offsets && max_leaves > 1).then(|| MaSamples {
props: samples.props.iter().step_by(4).copied().collect(),
tok: samples.tok.iter().step_by(4).copied().collect(),
});
let tree = learn_ma_tree_in_place(
&mut samples,
ma_learn_params(
min_symbol,
max_leaves,
max_candidates,
stride as f64,
use_wp,
),
pool,
scratch,
);
drop(samples);
let mut cand = finish_ma_candidate(tree, stride as f64);
if let Some(offsets) = offsets {
cand.set_leaf_offsets(offsets.props.iter().zip(&offsets.tok));
}
cand
},
);
let cands_ref = &cands;
let deep_lz_max_ratio = source.deep_lz_max_ratio();
let deep_lz = DeepLzScratchPool::new(group_lz_threads(crate::Speed::Slow, pool));
let group_sections: Vec<BitWriter> = pool.steal_map_with_threads(
scratch,
num_ac_groups,
group_lz_threads(crate::Speed::Slow, pool),
|group_index, scratch| {
let (x0, y0) = group_rect(group_index);
let num_values = placement
.iter()
.map(|p| {
let ch = &source.channels[p.channel];
gdim.min(ch.w - x0) * gdim.min(ch.h - y0)
})
.sum();
let mut toks = RawTokens::with_capacity(num_values);
for p in placement {
let ch = &source.channels[p.channel];
tokenize_ma_rect(
source,
placement,
p,
ac_stream_id(num_dc_groups, group_index),
x0,
y0,
gdim.min(ch.w - x0),
gdim.min(ch.h - y0),
&cands_ref[group_index],
wp_params,
use_wp,
&mut toks,
);
}
let cand = &cands_ref[group_index];
match &toks {
RawTokens::Compact(tokens) => write_local_tree_group(
tokens,
cand,
min_symbol,
wp_params,
deep_lz_max_ratio,
&deep_lz,
scratch,
),
RawTokens::Wide(tokens) => write_local_tree_group(
tokens,
cand,
min_symbol,
wp_params,
deep_lz_max_ratio,
&deep_lz,
scratch,
),
}
},
);
let num_sections = 1 + num_dc_groups + 1 + num_ac_groups;
let mut sections: Vec<BitWriter> = (0..num_sections).map(|_| BitWriter::new()).collect();
if let Some(dictionary) = dictionary {
sections[0].append(dictionary);
}
sections[0].write(1, 1); sections[0].write(1, 0); sections[0].write(1, 0); write_wp_header(wp_params, &mut sections[0]);
source.write_transforms(&mut sections[0]);
sections[0].zero_pad_to_byte();
for section in sections[1..num_dc_groups + 2].iter_mut() {
section.write(1, 0); write_wp_header(wp_params, section);
section.write(2, 0); section.zero_pad_to_byte();
}
for (group_index, section) in group_sections.into_iter().enumerate() {
sections[2 + num_dc_groups + group_index] = section;
}
Some(sections)
}
fn write_local_tree_group<T: lz77::LiteralToken>(
tokens: &[T],
cand: &LearnedCandidate,
min_symbol: u32,
wp_params: WpParams,
deep_lz_max_ratio: f64,
deep_lz: &DeepLzScratchPool,
scratch: &mut CoderScratch,
) -> BitWriter {
let num_ctx = cand.num_ctx;
let distance_ctx = num_ctx;
let run_count = lz77_run_count(tokens);
let mut best: Option<BitWriter> = None;
let mut best_estimate = f64::INFINITY;
let deep = |scratch: &mut CoderScratch| -> Vec<LzToken> {
deep_lz.with_depth(|depth| {
lz77_compress_for_speed_with_depth(
tokens,
distance_ctx,
crate::Speed::Slow,
depth,
Some(run_count),
scratch,
)
})
};
if (run_count as f64) >= LZ_LITERAL_ALTERNATIVE_MAX_RATIO * tokens.len() as f64 {
let lz = deep(scratch);
write_local_tree_variant(
&lz,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
} else {
let (e_lit, e_run) =
estimate_literal_and_run_bits_single(tokens, num_ctx as usize + 1, min_symbol);
if e_run > e_lit * deep_lz_max_ratio {
write_local_tree_variant(
tokens,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
} else if e_run < e_lit {
let lz = deep(scratch);
write_local_tree_variant(
&lz,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
write_local_tree_variant(
tokens,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
} else {
write_local_tree_variant(
tokens,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
let lz = deep(scratch);
write_local_tree_variant(
&lz,
cand,
min_symbol,
wp_params,
scratch,
&mut best,
&mut best_estimate,
);
}
}
best.expect("local-tree group section")
}
fn write_local_tree_variant<T: lz77::LzTokenSource>(
stream: &[T],
cand: &LearnedCandidate,
min_symbol: u32,
wp_params: WpParams,
scratch: &mut CoderScratch,
best: &mut Option<BitWriter>,
best_estimate: &mut f64,
) {
let num_ctx = cand.num_ctx;
let distance_ctx = num_ctx;
let code = build_lz_pixel_code_threads(
std::iter::once(stream),
num_ctx as usize,
min_symbol,
true,
true,
None,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
let estimate = estimate_coded_bits(&[stream], distance_ctx, &code, min_symbol, 1);
if estimate >= *best_estimate * VARIANT_WRITE_TOLERANCE {
return;
}
*best_estimate = best_estimate.min(estimate);
let mut section = BitWriter::new();
section.write(1, 0); write_wp_header(wp_params, &mut section);
section.write(2, 0); write_tree_lz77(
&cand.tree_tokens,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut section,
);
write_lz_section(stream, distance_ctx, &code, min_symbol, &mut section);
section.zero_pad_to_byte();
keep_smaller_writer(best, section);
}
#[allow(clippy::too_many_arguments)]
fn write_learned_single_variant<T: lz77::LzTokenSource>(
stream: &[T],
source: &MaSource<'_>,
cand: &LearnedCandidate,
min_symbol: u32,
wp_params: WpParams,
dictionary: Option<&BitWriter>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
best: &mut Option<BitWriter>,
best_estimate: &mut f64,
) {
let num_ctx = cand.num_ctx;
let distance_ctx = num_ctx;
let code = build_lz_pixel_code_threads(
std::iter::once(stream),
num_ctx as usize,
min_symbol,
true,
true,
Some(pool),
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
let estimate = estimate_coded_bits(
&[stream],
distance_ctx,
&code,
min_symbol,
pool.num_threads(),
);
if estimate >= *best_estimate * VARIANT_WRITE_TOLERANCE {
return;
}
*best_estimate = (*best_estimate).min(estimate);
let mut body = BitWriter::new();
if let Some(dictionary) = dictionary {
body.append(dictionary);
}
body.write(1, 1); body.write(1, 0); body.write(1, 0); write_wp_header(wp_params, &mut body);
source.write_transforms(&mut body);
write_tree_lz77(
&cand.tree_tokens,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut body,
);
write_lz_section(stream, distance_ctx, &code, min_symbol, &mut body);
body.zero_pad_to_byte();
keep_smaller_writer(best, body);
}
#[allow(clippy::too_many_arguments)]
fn write_learned_grouped_variant<T: lz77::LzTokenSource>(
streams: &[Vec<T>],
source: &MaSource<'_>,
cand: &LearnedCandidate,
min_symbol: u32,
wp_params: WpParams,
pool: &ThreadPool,
scratch: &mut CoderScratch,
num_ac_groups: usize,
num_dc_groups: usize,
has_global_stream: bool,
dictionary: Option<&BitWriter>,
best: &mut Option<Vec<BitWriter>>,
best_bits: &mut usize,
best_estimate: &mut f64,
) {
let num_ctx = cand.num_ctx;
let distance_ctx = num_ctx;
let num_sections = 1 + num_dc_groups + 1 + num_ac_groups;
let code = build_lz_pixel_code_threads(
streams.iter().map(Vec::as_slice),
num_ctx as usize,
min_symbol,
true,
true,
Some(pool),
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
let estimate = {
let slices: Vec<&[T]> = streams.iter().map(Vec::as_slice).collect();
estimate_coded_bits(&slices, distance_ctx, &code, min_symbol, pool.num_threads())
};
if estimate >= *best_estimate * VARIANT_WRITE_TOLERANCE {
return;
}
*best_estimate = (*best_estimate).min(estimate);
let mut sections: Vec<BitWriter> = (0..num_sections).map(|_| BitWriter::new()).collect();
if let Some(dictionary) = dictionary {
sections[0].append(dictionary);
}
sections[0].write(1, 1); sections[0].write(1, 1); write_tree_lz77(
&cand.tree_tokens,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut sections[0],
);
sections[0].write(1, 1); write_wp_header(wp_params, &mut sections[0]);
source.write_transforms(&mut sections[0]);
if has_global_stream {
write_lz_section(
&streams[0],
distance_ctx,
&code,
min_symbol,
&mut sections[0],
);
}
sections[0].zero_pad_to_byte();
for section in sections[1..num_dc_groups + 1].iter_mut() {
section.write(1, 1);
write_wp_header(wp_params, section);
section.write(2, 0);
section.zero_pad_to_byte();
}
let ac_global_idx = 1 + num_dc_groups;
sections[ac_global_idx].write(1, 1);
write_wp_header(wp_params, &mut sections[ac_global_idx]);
sections[ac_global_idx].zero_pad_to_byte();
let code_ref = &code;
let group_streams = &streams[1..];
let threads = pool.num_threads().clamp(1, num_ac_groups.max(1));
let chunk = num_ac_groups.div_ceil(threads).max(1);
let group_sections: Vec<BitWriter> = std::thread::scope(|scope| {
let handles: Vec<_> = group_streams
.chunks(chunk)
.enumerate()
.map(|(part_index, part)| {
let first = part_index * chunk;
scope.spawn(move || {
part.iter()
.enumerate()
.map(|(offset, stream)| {
let mut section = BitWriter::new();
section.write(1, 1);
write_wp_header(wp_params, &mut section);
match source.group_override(first + offset) {
Some(over) => {
write_palette_transform(
over.num_c,
over.nb_colors,
&mut section,
);
}
None => section.write(2, 0),
}
write_lz_section(
stream,
distance_ctx,
code_ref,
min_symbol,
&mut section,
);
section.zero_pad_to_byte();
section
})
.collect::<Vec<_>>()
})
})
.collect();
handles
.into_iter()
.flat_map(|h| h.join().expect("group section writer"))
.collect()
});
for (group_index, section) in group_sections.into_iter().enumerate() {
sections[2 + num_dc_groups + group_index] = section;
}
let bits: usize = sections.iter().map(BitWriter::bits_written).sum();
if bits < *best_bits {
*best_bits = bits;
*best = Some(sections);
}
}
enum TreeStreams<T> {
Literals(Vec<Vec<T>>),
Lz(Vec<Vec<LzToken>>),
}
const LZ_LITERAL_ALTERNATIVE_MAX_RATIO: f64 = 0.98;
const LZ_DEEP_MATCHER_MAX_RATIO_PALETTE: f64 = 1.6;
const LZ_DEEP_MATCHER_MAX_RATIO_RCT: f64 = 1.01;
const VARIANT_WRITE_TOLERANCE: f64 = 1.005;
fn choose_tree_streams<T: lz77::LiteralToken>(
tokens: Vec<Vec<T>>,
distance_ctx: u32,
num_contexts: usize,
min_symbol: u32,
deep_lz_max_ratio: f64,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Vec<TreeStreams<T>> {
let raw: usize = tokens.iter().map(Vec::len).sum();
let run_counts = pool.steal_map(scratch, tokens.len(), |k, _scratch| {
lz77_run_count(&tokens[k])
});
let run_len: usize = run_counts.iter().sum();
let deep = |scratch: &mut CoderScratch| -> Vec<Vec<LzToken>> {
let deep_lz = DeepLzScratchPool::new(group_lz_threads(crate::Speed::Slow, pool));
pool.steal_map_with_threads(
scratch,
tokens.len(),
group_lz_threads(crate::Speed::Slow, pool),
|k, scratch| {
deep_lz.with_depth(|depth| {
lz77_compress_for_speed_with_depth(
&tokens[k],
distance_ctx,
crate::Speed::Slow,
depth,
Some(run_counts[k]),
scratch,
)
})
},
)
};
if (run_len as f64) >= LZ_LITERAL_ALTERNATIVE_MAX_RATIO * raw as f64 {
return vec![TreeStreams::Lz(deep(scratch))];
}
let raw_slices: Vec<&[T]> = tokens.iter().map(Vec::as_slice).collect();
let (e_lit, e_run) =
estimate_literal_and_run_bits(&raw_slices, num_contexts, min_symbol, pool, scratch);
if e_run > e_lit * deep_lz_max_ratio {
return vec![TreeStreams::Literals(tokens)];
}
let lz = deep(scratch);
let slices: Vec<&[LzToken]> = lz.iter().map(Vec::as_slice).collect();
let e_lz = estimate_streams_bits(&slices, num_contexts, min_symbol, pool, scratch);
if e_lz < e_lit {
vec![TreeStreams::Lz(lz), TreeStreams::Literals(tokens)]
} else {
vec![TreeStreams::Literals(tokens), TreeStreams::Lz(lz)]
}
}
fn try_encode_context_tree_single_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
layout: GroupLayout,
predictors: &[u32],
min_symbol: u32,
rct_type: u32,
pool: &ThreadPool,
scratch: &mut CoderScratch,
wp_params: WpParams,
writer: &mut BitWriter,
) -> bool {
let nb_chans = 3 + if alpha.is_some() { 1 } else { 0 };
let collected = pool.steal_map(scratch, nb_chans, |chan, _scratch| {
if chan < 3 {
let pd = linear.plane_data(chan);
collect_channel(
|x, y| pd[y * xsize + x],
xsize,
ysize,
predictors[chan],
wp_params,
)
} else {
let a = alpha.expect("alpha channel must exist");
collect_channel(
|x, y| a.get_i32(y * xsize + x),
xsize,
ysize,
predictors[chan],
wp_params,
)
}
});
let (chan_res, chan_prp): (Vec<Vec<u32>>, Vec<Vec<i64>>) = collected.into_iter().unzip();
let mut ts = [0i32; 4];
let mut ctx_bits = 0.0;
let mut flat_bits = 0.0;
let threshold_costs = pool.steal_map(scratch, nb_chans, |chan, scratch| {
pick_threshold(&chan_res[chan], &chan_prp[chan], scratch)
});
for (chan, (t, cb, fb)) in threshold_costs.into_iter().enumerate() {
ts[chan] = t;
ctx_bits += cb;
flat_bits += fb;
}
let overhead_bits = (2 * nb_chans) as f32 * 64.0 * 8.0;
if ctx_bits + overhead_bits >= flat_bits {
return false;
}
let tree = build_context_tree(nb_chans, predictors, &ts);
let mut tree_tokens: Vec<Token> = Vec::new();
let ctx_map = emit_ct_tree(&tree, &mut tree_tokens);
let ctx_lut: Vec<u32> = (0..(nb_chans as u32) * 3).map(|k| ctx_map[&k]).collect();
let num_pixel_ctx = nb_chans * 3;
let channel_tokens = pool.steal_map(scratch, nb_chans, |chan, _scratch| {
let mut tokens = Vec::with_capacity(xsize * ysize);
let res = &chan_res[chan];
let prp = &chan_prp[chan];
let t = ts[chan] as i64;
for (&prp, &res) in prp[..res.len()].iter().zip(res.iter()) {
let bucket = bucket_of(prp, t);
let ctx = ctx_lut[chan * 3 + bucket as usize];
tokens.push(Token::new(ctx, res));
}
tokens
});
let mut tokens: Vec<Token> = Vec::with_capacity(xsize * ysize * nb_chans);
for channel in channel_tokens {
tokens.extend(channel);
}
write_frame_header_modular(alpha.is_some(), layout, writer);
let mut section = BitWriter::new();
section.write(1, 1); section.write(1, 0); section.write(1, 0); write_wp_header(wp_params, &mut section);
write_modular_transforms(nb_chans, rct_type, &mut section);
let distance_ctx = num_pixel_ctx as u32;
let lz_tokens = lz77_compress_for_speed(&tokens, distance_ctx, crate::Speed::Slow, scratch);
let code = build_lz_pixel_code(
std::iter::once(lz_tokens.as_slice()),
num_pixel_ctx,
min_symbol,
true,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
write_tree_lz77(
&tree_tokens,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut section,
);
write_lz_section(&lz_tokens, distance_ctx, &code, min_symbol, &mut section);
section.zero_pad_to_byte();
writer.write(1, 0);
writer.zero_pad_to_byte();
write_toc_entry(section.bits_written() / 8, writer);
writer.zero_pad_to_byte();
writer.append_byte_aligned(std::slice::from_mut(&mut section));
writer.zero_pad_to_byte();
true
}
fn try_encode_context_tree_multi_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
layout: GroupLayout,
predictors: &[u32],
xsize_groups: usize,
ysize_groups: usize,
num_dc_groups: usize,
min_symbol: u32,
rct_type: u32,
pool: &ThreadPool,
scratch: &mut CoderScratch,
wp_params: WpParams,
writer: &mut BitWriter,
) -> bool {
let nb_chans = 3 + if alpha.is_some() { 1 } else { 0 };
let num_ac_groups = xsize_groups * ysize_groups;
let groups: Vec<Vec<(Vec<u32>, Vec<i64>)>> =
pool.steal_map(scratch, num_ac_groups, |group_index, _scratch| {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * layout.dim();
let y0 = gy * layout.dim();
let gw = layout.dim().min(xsize - x0);
let gh = layout.dim().min(ysize - y0);
let mut chans: Vec<(Vec<u32>, Vec<i64>)> = Vec::with_capacity(nb_chans);
for chan in 0..3usize {
let pd = linear.plane_data(chan);
let get = |lx: usize, ly: usize| pd[(y0 + ly) * xsize + (x0 + lx)];
chans.push(collect_channel(get, gw, gh, predictors[chan], wp_params));
}
if let Some(a) = alpha {
let get = |lx: usize, ly: usize| a.get_i32((y0 + ly) * xsize + (x0 + lx));
chans.push(collect_channel(get, gw, gh, predictors[3], wp_params));
}
chans
});
let mut ts = [0i32; 4];
let mut ctx_bits = 0.0;
let mut flat_bits = 0.0;
let threshold_costs = pool.steal_map(scratch, nb_chans, |chan, scratch| {
pick_threshold_grouped(&groups, chan, scratch)
});
for (chan, (t, cb, fb)) in threshold_costs.into_iter().enumerate() {
ts[chan] = t;
ctx_bits += cb;
flat_bits += fb;
}
let overhead_bits = (2 * nb_chans) as f32 * 64.0 * 8.0;
if ctx_bits + overhead_bits >= flat_bits {
return false;
}
let tree = build_context_tree(nb_chans, predictors, &ts);
let mut tree_tokens: Vec<Token> = Vec::new();
let ctx_map = emit_ct_tree(&tree, &mut tree_tokens);
let ctx_lut: Vec<u32> = (0..(nb_chans as u32) * 3).map(|k| ctx_map[&k]).collect();
let num_pixel_ctx = nb_chans * 3;
let distance_ctx = num_pixel_ctx as u32;
let group_lz_tokens: Vec<Vec<LzToken>> = {
let deep_lz = DeepLzScratchPool::new(group_lz_threads(crate::Speed::Slow, pool));
pool.steal_map_with_threads(
scratch,
num_ac_groups,
group_lz_threads(crate::Speed::Slow, pool),
|group_index, scratch| {
let g = &groups[group_index];
let token_count = g.iter().map(|(res, _)| res.len()).sum();
let mut toks: Vec<Token> = Vec::with_capacity(token_count);
for (((res, prp), &threshold), contexts) in g[..nb_chans]
.iter()
.zip(&ts[..nb_chans])
.zip(ctx_lut.as_chunks::<3>().0)
{
let t = threshold as i64;
for (&prp, &res) in prp[..res.len()].iter().zip(res.iter()) {
let bucket = bucket_of(prp, t);
let ctx = contexts[bucket as usize];
toks.push(Token::new(ctx, res));
}
}
deep_lz.with_depth(|depth| {
lz77_compress_for_speed_with_depth(
&toks,
distance_ctx,
crate::Speed::Slow,
depth,
None,
scratch,
)
})
},
)
};
let code = build_lz_pixel_code(
group_lz_tokens.iter().map(Vec::as_slice),
num_pixel_ctx,
min_symbol,
true,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
write_frame_header_modular(alpha.is_some(), layout, writer);
let num_sections = 1 + num_dc_groups + 1 + num_ac_groups;
let mut sections: Vec<BitWriter> = (0..num_sections).map(|_| BitWriter::new()).collect();
sections[0].write(1, 1); sections[0].write(1, 1); write_tree_lz77(
&tree_tokens,
&code,
min_symbol,
&mut scratch.huffman_pool,
&mut sections[0],
);
sections[0].write(1, 1); write_wp_header(wp_params, &mut sections[0]);
write_modular_transforms(nb_chans, rct_type, &mut sections[0]);
sections[0].zero_pad_to_byte();
for section in sections[1..num_dc_groups + 1].iter_mut() {
section.write(1, 1);
write_wp_header(wp_params, section);
section.write(2, 0);
section.zero_pad_to_byte();
}
let ac_global_idx = 1 + num_dc_groups;
sections[ac_global_idx].write(1, 1);
write_wp_header(wp_params, &mut sections[ac_global_idx]);
sections[ac_global_idx].zero_pad_to_byte();
write_lz_groups(
&group_lz_tokens,
&code,
distance_ctx,
min_symbol,
wp_params,
pool,
&mut sections[2 + num_dc_groups..],
);
writer.write(1, 0);
writer.zero_pad_to_byte();
for s in §ions {
write_toc_entry(s.bits_written() / 8, writer);
}
writer.zero_pad_to_byte();
writer.append_byte_aligned(&mut sections);
writer.zero_pad_to_byte();
true
}
fn push_split(out: &mut Vec<Token>, property: u32, split_val: i32) {
out.push(Token::new(TREE_CTX_PROPERTY, property + 1));
out.push(Token::new(TREE_CTX_SPLIT_VAL, pack_signed(split_val)));
}
fn push_leaf(out: &mut Vec<Token>, predictor: u32) {
push_leaf_mul(out, predictor, 1);
}
fn push_leaf_mul(out: &mut Vec<Token>, predictor: u32, multiplier: u32) {
debug_assert!(multiplier >= 1);
let mul_log = multiplier.trailing_zeros();
let mul_bits = (multiplier >> mul_log) - 1;
out.push(Token::new(TREE_CTX_PROPERTY, 0));
out.push(Token::new(TREE_CTX_PREDICTOR, predictor));
out.push(Token::new(TREE_CTX_OFFSET, pack_signed(0)));
out.push(Token::new(TREE_CTX_MULTIPLIER_LOG, mul_log));
out.push(Token::new(TREE_CTX_MULTIPLIER_BITS, mul_bits));
}
fn build_balanced_tree_tokens_mul(leaves: &[(u32, u32)]) -> Vec<Token> {
let n_leaves = leaves.len();
let mut t = Vec::new();
match n_leaves {
1 => push_leaf_mul(&mut t, leaves[0].0, leaves[0].1),
2 => {
push_split(&mut t, 0, 0);
push_leaf_mul(&mut t, leaves[1].0, leaves[1].1);
push_leaf_mul(&mut t, leaves[0].0, leaves[0].1);
}
_ => {
for k in (1..=(n_leaves - 2)).rev() {
push_split(&mut t, 0, k as i32);
push_leaf_mul(&mut t, leaves[k + 1].0, leaves[k + 1].1);
}
push_split(&mut t, 0, 0);
push_leaf_mul(&mut t, leaves[1].0, leaves[1].1);
push_leaf_mul(&mut t, leaves[0].0, leaves[0].1);
}
}
t
}
fn build_balanced_tree_tokens(predictors: &[u32]) -> Vec<Token> {
let n_leaves = predictors.len();
let mut t = Vec::new();
match n_leaves {
1 => push_leaf(&mut t, predictors[0]),
2 => {
push_split(&mut t, 0, 0);
push_leaf(&mut t, predictors[1]); push_leaf(&mut t, predictors[0]); }
3 => {
push_split(&mut t, 0, 1);
push_leaf(&mut t, predictors[2]); push_split(&mut t, 0, 0);
push_leaf(&mut t, predictors[1]); push_leaf(&mut t, predictors[0]); }
4 => {
push_split(&mut t, 0, 1);
push_split(&mut t, 0, 2);
push_split(&mut t, 0, 0);
push_leaf(&mut t, predictors[3]); push_leaf(&mut t, predictors[2]); push_leaf(&mut t, predictors[1]); push_leaf(&mut t, predictors[0]); }
_ => {
for k in (1..=(n_leaves - 2)).rev() {
push_split(&mut t, 0, k as i32);
push_leaf(&mut t, predictors[k + 1]);
}
push_split(&mut t, 0, 0);
push_leaf(&mut t, predictors[1]);
push_leaf(&mut t, predictors[0]);
}
}
t
}
fn write_tree_and_pixel_code_nolz(
tree_tokens: &[Token],
pixel_code: &OwnedEntropyCode,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
let tree_code =
optimize_entropy_code(tree_tokens, NUM_TREE_CONTEXTS, &mut scratch.huffman_pool);
let tree_code_ref = tree_code.as_ref();
w.write(1, 0); write_entropy_code(&tree_code_ref, &mut scratch.huffman_pool, w);
for tok in tree_tokens {
write_token(*tok, &tree_code_ref, w);
}
w.write(1, 0);
write_entropy_code(&pixel_code.as_ref(), &mut scratch.huffman_pool, w);
}
pub(crate) fn encode_frame_lossless_float(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
num_threads: usize,
writer: &mut BitWriter,
) {
let pool = ThreadPool::new_lossless(num_threads);
let mut scratch = Box::new(CoderScratch::lossless());
encode_frame_lossless_float_with_pool(linear, alpha, &pool, &mut scratch, writer);
}
fn encode_frame_lossless_float_with_pool(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
writer: &mut BitWriter,
) {
let xsize = linear.xsize();
let ysize = linear.ysize();
let nb_chans = 3usize + if alpha.is_some() { 1 } else { 0 };
let xsize_groups = xsize.div_ceil(GROUP_DIM);
let ysize_groups = ysize.div_ceil(GROUP_DIM);
let num_ac_groups = xsize_groups * ysize_groups;
let xsize_dc_groups = xsize.div_ceil(LF_GROUP_DIM);
let ysize_dc_groups = ysize.div_ceil(LF_GROUP_DIM);
let num_dc_groups = xsize_dc_groups * ysize_dc_groups;
let single_group = num_ac_groups == 1;
let grad_pack_fn = selected_grad_pack_interior_fn();
const GRADIENT_PRED: u32 = 5;
let predictors = [GRADIENT_PRED; 4];
let tree_tokens = build_balanced_tree_tokens(&predictors[..nb_chans]);
write_frame_header_modular(alpha.is_some(), GroupLayout::DEFAULT, writer);
if single_group {
let mut section = BitWriter::new();
section.write(1, 1); section.write(1, 0); section.write(1, 0); section.write(1, 1); section.write(2, 0b00);
let tokens = tokenize_all(
linear,
alpha,
xsize,
ysize,
0,
0,
xsize,
ysize,
3,
&predictors,
grad_pack_fn,
pool,
scratch,
);
let code = optimize_entropy_code(&tokens, nb_chans, &mut scratch.huffman_pool);
write_tree_and_pixel_code_nolz(&tree_tokens, &code, scratch, &mut section);
for t in &tokens {
write_token(*t, &code.as_ref(), &mut section);
}
section.zero_pad_to_byte();
writer.write(1, 0);
writer.zero_pad_to_byte();
write_toc_entry(section.bits_written() / 8, writer);
writer.zero_pad_to_byte();
writer.append_byte_aligned(std::slice::from_mut(&mut section));
writer.zero_pad_to_byte();
} else {
let num_sections = 1 + num_dc_groups + 1 + num_ac_groups;
let mut sections: Vec<BitWriter> = (0..num_sections).map(|_| BitWriter::new()).collect();
let group_tokens: Vec<Vec<Token>> =
pool.steal_map(scratch, num_ac_groups, |group_index, scratch| {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * GROUP_DIM;
let y0 = gy * GROUP_DIM;
let gw = GROUP_DIM.min(xsize - x0);
let gh = GROUP_DIM.min(ysize - y0);
tokenize_all(
linear,
alpha,
xsize,
ysize,
x0,
y0,
gw,
gh,
3,
&predictors,
grad_pack_fn,
pool,
scratch,
)
});
let mut all_tokens: Vec<Token> = Vec::new();
for tokens in &group_tokens {
all_tokens.extend_from_slice(tokens);
}
let code = optimize_entropy_code(&all_tokens, nb_chans, &mut scratch.huffman_pool);
sections[0].write(1, 1); sections[0].write(1, 1); write_tree_and_pixel_code_nolz(&tree_tokens, &code, scratch, &mut sections[0]);
sections[0].write(1, 1); sections[0].write(1, 1); sections[0].write(2, 0b00); sections[0].zero_pad_to_byte();
for section in &mut sections[1..1 + num_dc_groups] {
section.write(1, 1);
section.write(1, 1);
section.write(2, 0);
section.zero_pad_to_byte();
}
let ac_global_idx = 1 + num_dc_groups;
sections[ac_global_idx].write(1, 1);
sections[ac_global_idx].write(1, 1);
sections[ac_global_idx].zero_pad_to_byte();
for (section, tokens) in sections[2 + num_dc_groups..][..num_ac_groups]
.iter_mut()
.zip(&group_tokens[..num_ac_groups])
{
section.write(1, 1);
section.write(1, 1);
section.write(2, 0);
for t in tokens {
write_token(*t, &code.as_ref(), section);
}
section.zero_pad_to_byte();
}
writer.write(1, 0);
writer.zero_pad_to_byte();
for s in §ions {
write_toc_entry(s.bits_written() / 8, writer);
}
writer.zero_pad_to_byte();
writer.append_byte_aligned(&mut sections);
writer.zero_pad_to_byte();
}
}
#[cfg(test)]
mod rate_selection_tests {
use super::palette::local_palette_coverage_is_sufficient;
use super::*;
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
fn hist_entropy_fma_reference(hist: &[u64], total: u64) -> f32 {
if total == 0 {
return 0.0;
}
let mut bits = 0.0;
for &count in hist.iter().filter(|&&c| c != 0) {
let p = count as f32 / total as f32;
let ix = p.to_bits().wrapping_add(0x3f80_0000 - 0x3f35_04f3);
let exponent = (ix >> 23) as i32 - 127;
let a = f32::from_bits((ix & 0x007f_ffff) + 0x3f35_04f3);
let x = (a - 1.0) / (a + 1.0);
let x2 = x * x;
let u = 0.412_198_57f32
.mul_add(x2, 0.577_078_04)
.mul_add(x2, 0.961_796_7);
let log = (x2 * x).mul_add(u, x.mul_add(2.885_390_1, exponent as f32));
bits -= count as f32 * log;
}
bits
}
#[test]
fn selected_hist_entropy_matches_scalar_model_exactly() {
let entropy_of_hist = selected_entropy_of_hist_fn();
#[allow(unused_mut)]
let mut reference: EntropyOfHistFn = entropy_of_hist_scalar;
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma") {
reference = hist_entropy_fma_reference;
}
let check = |hist: &[u64]| {
let total = hist.iter().sum();
assert_eq!(
entropy_of_hist(hist, total).to_bits(),
reference(hist, total).to_bits(),
"histogram length {}, total {total}",
hist.len(),
);
};
check(&[]);
check(&[0; 65]);
check(&[u64::MAX]);
check(&[u64::MAX - 6, 1, 2, 3]);
assert_eq!(entropy_of_hist(&[1, 2, 3], 0), 0.0);
assert_eq!(entropy_of_hist(&[1, 1], 2), 2.0);
for exponent in 24..64 {
let midpoint = (1u64 << exponent) + (1u64 << (exponent - 24));
for value in [midpoint - 1, midpoint, midpoint + 1] {
check(&[value, 1, 3, 7, 0]);
check(&[value, 1, 3, 7, 0, 11, 13, 17, 19]);
}
}
for len in 0..129 {
for stride in [1, 2, 3, 5, 16, 64] {
for range in [1, 100, 1 << 24, 1 << 32, 1 << 54] {
let mut state = (len + stride) as u64;
let hist: Vec<_> = (0..len)
.map(|i| {
state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
if i % stride == 0 {
1 + (state >> 10) % range
} else {
0
}
})
.collect();
check(&hist);
}
}
}
}
#[test]
fn shortlist_thresholds_keep_ambiguous_candidates() {
assert!(!local_palette_coverage_is_sufficient(24, 100));
assert!(local_palette_coverage_is_sufficient(25, 100));
assert!(!learned_tree_is_decisive(
MA_DECISIVE_MIN_SAVINGS - f64::EPSILON
));
assert!(learned_tree_is_decisive(MA_DECISIVE_MIN_SAVINGS));
}
fn image_from_rgb(
width: usize,
height: usize,
mut rgb: impl FnMut(usize, usize) -> [i32; 3],
) -> Image3Si {
let mut image = Image3Si::new(width, height);
for y in 0..height {
let [p0, p1, p2] = image.all_plane_rows_mut(y);
for x in 0..width {
let [r, g, b] = rgb(x, y);
let (yc, co, cg) = forward_ycocg(r, g, b);
p0[x] = yc;
p1[x] = co;
p2[x] = cg;
}
}
image
}
fn encode_core(image: &Image3Si, allow_palettes: bool) -> BitWriter {
let pool = ThreadPool::new_lossless(1);
let mut scratch = CoderScratch::lossless();
let mut writer = BitWriter::new();
encode_frame_lossless_core_impl(
image,
None,
8,
false,
3,
crate::Speed::Slow,
crate::DecodingSpeed::Slow,
&pool,
&mut scratch,
ModularFrameKind::Regular,
allow_palettes,
true,
&mut writer,
);
writer
}
#[test]
fn slow_single_group_palette_is_rate_safe() {
let image = image_from_rgb(64, 64, |x, y| {
let c = ((x / 8 + y / 8) & 3) as i32;
[c * 61, c * 37, c * 19]
});
let selected = encode_core(&image, true);
let normal = encode_core(&image, false);
assert!(selected.bits_written() <= normal.bits_written());
}
#[test]
fn slow_local_palette_is_rate_safe_for_mixed_content() {
let image = image_from_rgb(257, 257, |x, y| {
if x < 256 && y < 128 {
let c = ((x / 16 + y / 16) & 7) as i32;
[c * 31, c * 17, c * 7]
} else {
let v = x
.wrapping_mul(1_664_525)
.wrapping_add(y.wrapping_mul(1_013_904_223));
[
((v >> 8) & 255) as i32,
((v >> 16) & 255) as i32,
((v >> 24) & 255) as i32,
]
}
});
let selected = encode_core(&image, true);
let normal = encode_core(&image, false);
assert!(selected.bits_written() <= normal.bits_written());
}
}
#[cfg(test)]
mod ma_sampling_tests {
use super::*;
#[test]
fn row_walk_matches_point_fetched_properties_and_predictions() {
for width in [0usize, 1, 2, 3, 4, 5, 17, 257] {
for height in [0usize, 1, 2, 7] {
for flat in [false, true] {
let plane: Vec<i32> = (0..width * height)
.map(|i| {
if flat {
8192
} else {
[i32::MIN, i32::MAX, -65536, 65535, -8192, 0, 8192]
[(i * 17 + i / width) % 7]
}
})
.collect();
let get = |x: usize, y: usize| plane[y * width + x];
for ¶ms in &WpParams::PRESETS {
for use_wp in [false, true] {
let mut wp = WpState::with_params(width, params);
let mut previous_gradient = 0i32;
let mut count = 0;
walk_channel_ma(
|y| &plane[y * width..][..width],
width,
height,
2,
0,
&[],
params,
use_wp,
|x, y, value, props, neighbors, weighted| {
assert_eq!(count, y * width + x);
assert_eq!(value, get(x, y) as i64);
count += 1;
if x == 0 {
previous_gradient = 0;
}
let n = predictor_neighbors(&get, x, y, width);
let expected_wp = if use_wp {
wp.predict(
x,
y,
n.top,
n.left,
n.top_right,
n.top_left,
n.top_top,
)
} else {
0
};
let gradient = (n.left + n.top - n.top_left) as i32;
assert!(props[16..].iter().all(|&v| v == 0));
assert_eq!(
props[..16],
[
2,
0,
y as i32,
x as i32,
n.top.abs() as i32,
n.left.abs() as i32,
n.top as i32,
n.left as i32,
(n.left - previous_gradient as i64) as i32,
gradient,
(n.left - n.top_left) as i32,
(n.top_left - n.top) as i32,
(n.top - n.top_right) as i32,
(n.top - n.top_top) as i32,
(n.left - n.left_left) as i32,
if use_wp { wp.wp_prop as i32 } else { 0 },
]
);
assert_eq!(weighted, expected_wp);
for pred in 0..NUM_MA_PREDS as u32 {
assert_eq!(
predictor_value(pred, neighbors, weighted),
predictor_value(pred, n, expected_wp),
);
}
previous_gradient = gradient;
if use_wp {
wp.update(value, x, y);
}
},
);
assert_eq!(count, width * height);
}
}
}
}
}
}
fn reference_samples(
plane: &[i32],
width: usize,
height: usize,
stride: usize,
params: WpParams,
) -> MaSamples {
let mut samples = MaSamples::new();
walk_channel_ma(
|y| &plane[y * width..][..width],
width,
height,
2,
0,
&[],
params,
true,
|x, y, value, p, n, wp_pred| {
if x % stride != y % stride {
return;
}
let mut tok = [0u8; NUM_MA_PREDS];
for pred in 0..NUM_MA_PREDS as u32 {
let prediction = predictor_value(pred, n, wp_pred);
let (token, _, _) = uint_encode(pack_signed((value - prediction) as i32));
tok[pred as usize] = token.min(u8::MAX as u32) as u8;
}
samples.push(*p, tok);
},
);
samples
}
#[test]
fn stride_aware_sampling_matches_full_property_walk() {
for &(width, height) in &[(0, 3), (1, 1), (1, 7), (2, 5), (9, 7), (17, 4)] {
let plane: Vec<i32> = (0..width * height)
.map(|i| {
let x = i % width.max(1);
let y = i / width.max(1);
(((x * 977 + y * 619) ^ (x * y * 37)) as i32 & 0xffff) - 0x7fff
})
.collect();
let get_row = |y: usize| &plane[y * width..][..width];
for &stride in &[1, 2, 3, 5, 11, width * height + 1] {
for ¶ms in &WpParams::PRESETS {
let expected = reference_samples(&plane, width, height, stride, params);
let mut actual = MaSamples::new();
sample_channel_ma(
get_row,
width,
height,
2,
0,
&[],
params,
true,
stride,
|p, t| actual.push(p, t),
);
assert_eq!(actual.len(), ma_channel_sample_count(width, height, stride));
assert_eq!(
actual.props, expected.props,
"properties: {width}x{height}, stride={stride}, params={params:?}"
);
assert_eq!(
actual.tok, expected.tok,
"tokens: {width}x{height}, stride={stride}, params={params:?}"
);
}
}
}
}
}
#[cfg(test)]
mod lz_reach_probe {
use super::quantize_xyb_channels;
use crate::image::Image3F;
use crate::quant_weights::INV_DC_QUANT;
#[test]
fn slow_lossless_encode_of_repetitive_image() {
let (w, h) = (512usize, 512usize);
let mut rgb = vec![0u8; w * h * 3];
for y in 0..h {
for x in 0..w {
let v = (((x / 8) + (y / 8)) % 2) as u8 * 255;
let i = (y * w + x) * 3;
rgb[i] = v;
rgb[i + 1] = v;
rgb[i + 2] = v;
}
}
let cfg = crate::EncodeConfig::default()
.with_lossless(true)
.with_speed(crate::Speed::Slow)
.with_num_threads(1);
let out = crate::encode_image(&rgb, w, h, &cfg).expect("encode failed");
eprintln!("PROBE encoded {} bytes", out.len());
assert!(!out.is_empty());
}
#[test]
fn packed_quantization_matches_the_channel_formula() {
let mut atlas = Image3F::new(5, 3);
for i in 0..15 {
atlas.plane_row_mut(0, i / 5)[i % 5] = (i as f32 - 7.0) / 41.0;
atlas.plane_row_mut(1, i / 5)[i % 5] = i as f32 / 29.0;
atlas.plane_row_mut(2, i / 5)[i % 5] = (15 - i) as f32 / 31.0;
}
for lattice_scale in [1, 2, 8] {
let got = quantize_xyb_channels(&atlas, lattice_scale);
let m = lattice_scale as f32;
for i in 0..15 {
let yq = (atlas.plane_data(1)[i] * INV_DC_QUANT[1] * m).round() as i32;
assert_eq!(got[0][i], yq);
assert_eq!(
got[1][i],
(atlas.plane_data(0)[i] * INV_DC_QUANT[0] * m).round() as i32
);
assert_eq!(
got[2][i],
(atlas.plane_data(2)[i] * INV_DC_QUANT[2] * m).round() as i32 - yq
);
}
}
}
}
#[cfg(test)]
mod context_tree_tests {
use super::*;
#[test]
fn gated_tree_keeps_bfs_tokens_with_leaf_offsets() {
let tree = LearnedTree {
nodes: vec![
MaNode::Split {
prop: 0,
val: 0,
gt: 1,
le: 2,
},
MaNode::Leaf { pred: 1 },
MaNode::Split {
prop: 3,
val: 3,
gt: 3,
le: 4,
},
MaNode::Leaf { pred: 6 },
MaNode::Leaf { pred: 0 },
],
est_bits: 100.,
flat_bits: 10000.,
};
let mut samples = MaSamples::new();
for (channel, x, residual) in [(1, 0, -3), (0, 4, 5), (0, 3, 0)] {
let mut props = [0; NUM_MA_PROPS];
props[0] = channel;
props[3] = x;
for _ in 0..64 {
samples.push(props, [pack_signed(residual) as u8; NUM_MA_PREDS]);
}
}
for with_offsets in [false, true] {
let candidate =
gate_ma_tree(tree.clone(), 1., with_offsets.then_some(&samples)).unwrap();
let offsets = if with_offsets { [-3, 5, 0] } else { [0; 3] };
assert_eq!(candidate.leaf_offset, offsets);
assert_eq!(candidate.leaf_ctx, [u32::MAX, 0, u32::MAX, 1, 2]);
assert_eq!(candidate.num_ctx, 3);
let leaf = |pred, offset| {
[
(TREE_CTX_PROPERTY, 0),
(TREE_CTX_PREDICTOR, pred),
(TREE_CTX_OFFSET, pack_signed(offset)),
(TREE_CTX_MULTIPLIER_LOG, 0),
(TREE_CTX_MULTIPLIER_BITS, 0),
]
};
let mut expected = vec![(TREE_CTX_PROPERTY, 1), (TREE_CTX_SPLIT_VAL, 0)];
expected.extend(leaf(1, offsets[0]));
expected.extend([(TREE_CTX_PROPERTY, 4), (TREE_CTX_SPLIT_VAL, 6)]);
expected.extend(leaf(6, offsets[1]));
expected.extend(leaf(0, offsets[2]));
let actual: Vec<_> = candidate
.tree_tokens
.iter()
.map(|token| (token.context, token.value))
.collect();
assert_eq!(actual, expected);
assert_eq!(candidate.est_real, 914.);
}
let retained = MaSamples {
props: samples.props.iter().step_by(4).copied().collect(),
tok: samples.tok.iter().step_by(4).copied().collect(),
};
samples.props.reverse();
samples.tok.reverse();
let mut retained_candidate = finish_ma_candidate(tree.clone(), 1.);
retained_candidate.set_leaf_offsets(retained.props.iter().zip(&retained.tok));
assert_eq!(retained_candidate.leaf_offset, [-3, 5, 0]);
for est_bits in [10000., f64::NAN] {
assert!(
gate_ma_tree(
LearnedTree {
est_bits,
..tree.clone()
},
1.,
Some(&samples)
)
.is_none()
);
}
}
#[test]
fn grouped_threshold_scoring_matches_concatenated_reference() {
let groups = vec![
vec![(vec![0, 3, 7, 3], vec![-20, -4, 12, 80])],
vec![(vec![7, 1, 1, 9, 2], vec![-100, -9, 0, 17, 110])],
];
let residuals: Vec<u32> = groups
.iter()
.flat_map(|group| group[0].0.iter().copied())
.collect();
let properties: Vec<i64> = groups
.iter()
.flat_map(|group| group[0].1.iter().copied())
.collect();
let expected = pick_threshold(&residuals, &properties, &mut CoderScratch::default());
let actual = pick_threshold_grouped(&groups, 0, &mut CoderScratch::default());
assert_eq!(actual, expected);
}
#[test]
fn compiled_ma_tokenization_matches_full_tree_with_and_without_wp() {
let tree = LearnedTree {
nodes: vec![
MaNode::Split {
prop: 0,
val: 0,
gt: 1,
le: 4,
},
MaNode::Split {
prop: 15,
val: 0,
gt: 2,
le: 3,
},
MaNode::Leaf { pred: 6 },
MaNode::Leaf { pred: 1 },
MaNode::Split {
prop: 3,
val: 3,
gt: 5,
le: 6,
},
MaNode::Leaf { pred: 5 },
MaNode::Leaf { pred: 1 },
],
est_bits: 0.,
flat_bits: 0.,
};
let (_, contexts, _) = emit_learned_tree(&tree);
for channel in [0, 1, 7, u32::MAX] {
let lookup = MaLookup::new(&tree, &contexts, channel, 0);
assert_eq!(lookup.needs_wp(), (channel as i32) > 0);
for width in [0, 1, 2, 3, 4, 5, 9, 257] {
for height in [0, 1, 2, 3, 17] {
let values: Vec<i32> = (0..width * height)
.map(|i| ((i * 7919 ^ (i / 7 * 1237)) % 65536) as i32 - 32768)
.collect();
let get_row = |y| &values[y * width..][..width];
for use_wp in [false, true] {
let mut expected = Vec::new();
walk_channel_ma(
get_row,
width,
height,
channel,
0,
&[],
WpParams::DEFAULT,
use_wp,
|_x, _y, value, props, n, wp| {
let (node, pred) = tree.lookup(props);
expected.push((
contexts[node as usize],
pack_signed((value - predictor_value(pred, n, wp)) as i32),
));
},
);
let mut actual = RawTokens::with_capacity(values.len());
tokenize_channel_ma(
get_row,
width,
height,
channel,
0,
&[],
WpParams::DEFAULT,
use_wp,
&lookup,
&vec![0; contexts.len()],
&mut actual,
);
let actual: Vec<_> = match RawTokenStreams::new(vec![actual]) {
RawTokenStreams::Compact(streams) => streams
.into_iter()
.flatten()
.map(|t| {
let t = t.unpack();
(t.context, t.value)
})
.collect(),
RawTokenStreams::Wide(streams) => streams
.into_iter()
.flatten()
.map(|t| (t.context, t.value))
.collect(),
};
assert_eq!(
actual, expected,
"channel={channel}, width={width}, height={height}, wp={use_wp}"
);
}
}
}
}
}
}