#[path = "enc_lossless_lz77.rs"]
mod lz77;
use lz77::{
LZ77_MIN_SYMBOL, LzToken, build_lz_pixel_code, lz77_compress_for_speed, lz77_compress_runs,
write_local_tree_lz77, write_lz_token, write_tree_lz77,
};
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;
const PREDICTOR_LEFT: u32 = 1;
const PREDICTOR_TOP: u32 = 2;
const PREDICTOR_SELECT: u32 = 4;
const PREDICTOR_GRADIENT: u32 = 5;
const PREDICTOR_WEIGHTED: u32 = 6;
const PREDICTOR_AVERAGE4: u32 = 13;
static SLOW_PREDICTORS: [u32; 6] = [
PREDICTOR_WEIGHTED,
PREDICTOR_GRADIENT,
PREDICTOR_AVERAGE4,
PREDICTOR_SELECT,
PREDICTOR_LEFT,
PREDICTOR_TOP,
];
#[derive(Clone, Copy)]
struct PredictorNeighbors {
left: i64,
top: i64,
top_left: i64,
top_right: i64,
left_left: i64,
top_top: i64,
top_right_right: i64,
}
#[inline]
fn predictor_neighbors<F: Fn(usize, usize) -> i32 + ?Sized>(
get: &F,
x: usize,
y: usize,
width: usize,
) -> PredictorNeighbors {
let left = if x > 0 {
get(x - 1, y) as i64
} else if y > 0 {
get(x, y - 1) as i64
} else {
0
};
let top = if y > 0 { get(x, y - 1) as i64 } else { left };
let top_left = if x > 0 && y > 0 {
get(x - 1, y - 1) as i64
} else {
left
};
let top_right = if x + 1 < width && y > 0 {
get(x + 1, y - 1) as i64
} else {
top
};
PredictorNeighbors {
left,
top,
top_left,
top_right,
left_left: if x > 1 { get(x - 2, y) as i64 } else { left },
top_top: if y > 1 { get(x, y - 2) as i64 } else { top },
top_right_right: if x + 2 < width && y > 0 {
get(x + 2, y - 1) as i64
} else {
top_right
},
}
}
#[inline]
fn predictor_value(pred_id: u32, n: PredictorNeighbors, weighted: i64) -> i64 {
match pred_id {
PREDICTOR_LEFT => n.left,
PREDICTOR_TOP => n.top,
PREDICTOR_SELECT => {
let projected = n.left + n.top - n.top_left;
if (projected - n.left).abs() < (projected - n.top).abs() {
n.left
} else {
n.top
}
}
PREDICTOR_GRADIENT => clamped_gradient(n.left, n.top, n.top_left),
PREDICTOR_WEIGHTED => weighted,
PREDICTOR_AVERAGE4 => {
(6 * n.top - 2 * n.top_top
+ 7 * n.left
+ n.left_left
+ n.top_right_right
+ 3 * n.top_right
+ 8)
/ 16
}
_ => unreachable!("unsupported modular predictor {pred_id}"),
}
}
const WP_EXTRA_BITS: i64 = 3;
const WP_PRED_ROUND: i64 = ((1 << WP_EXTRA_BITS) >> 1) - 1; #[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct WpParams {
w: [u32; 4],
p: [i64; 7],
}
impl WpParams {
const PRESETS: [Self; 4] = [
Self {
w: [0xd, 0xc, 0xc, 0xc],
p: [16, 10, 7, 7, 7, 0, 0],
},
Self {
w: [0xd, 0xc, 0xc, 0xb],
p: [8, 8, 4, 0, 3, 23, 2],
},
Self {
w: [0xd, 0xc, 0xd, 0xc],
p: [10, 9, 7, 0, 0, 16, 9],
},
Self {
w: [0xd, 0xd, 0xc, 0xc],
p: [16, 8, 0, 16, 0, 23, 0],
},
];
const DEFAULT: Self = Self::PRESETS[0];
}
fn write_wp_header(params: WpParams, w: &mut BitWriter) {
if params == WpParams::DEFAULT {
w.write(1, 1);
return;
}
w.write(1, 0);
for &p in ¶ms.p {
w.write(5, p as u64);
}
for &weight in ¶ms.w {
w.write(4, weight as u64);
}
}
static WP_DIV: [u32; 64] = [
16777216, 8388608, 5592405, 4194304, 3355443, 2796202, 2396745, 2097152, 1864135, 1677721,
1525201, 1398101, 1290555, 1198372, 1118481, 1048576, 986895, 932067, 883011, 838860, 798915,
762600, 729444, 699050, 671088, 645277, 621378, 599186, 578524, 559240, 541200, 524288, 508400,
493447, 479349, 466033, 453438, 441505, 430185, 419430, 409200, 399457, 390167, 381300, 372827,
364722, 356962, 349525, 342392, 335544, 328965, 322638, 316551, 310689, 305040, 299593, 294337,
289262, 284359, 279620, 275036, 270600, 266305, 262144,
];
pub(crate) struct WpState {
xsize: usize,
pred_errors: [Vec<u32>; 4],
error: Vec<i64>,
prediction: [i64; 4],
pred: i64,
pub(crate) wp_prop: i64,
params: WpParams,
}
impl WpState {
pub(crate) fn new(xsize: usize) -> Self {
Self::with_params(xsize, WpParams::DEFAULT)
}
fn with_params(xsize: usize, params: WpParams) -> Self {
let n = (xsize + 2) * 2;
WpState {
xsize,
pred_errors: [vec![0u32; n], vec![0u32; n], vec![0u32; n], vec![0u32; n]],
error: vec![0i64; n],
prediction: [0; 4],
pred: 0,
wp_prop: 0,
params,
}
}
#[inline]
fn add_bits(x: i64) -> i64 {
x << WP_EXTRA_BITS
}
#[inline]
fn floor_log2(x: u64) -> u32 {
debug_assert!(x >= 1);
63 - x.leading_zeros()
}
#[inline]
fn error_weight(x: u64, maxweight: u32) -> u32 {
let mut shift = Self::floor_log2(x + 1) as i32 - 5;
if shift < 0 {
shift = 0;
}
4 + (((maxweight as u64 * WP_DIV[(x >> shift) as usize] as u64) >> shift) as u32)
}
#[inline]
fn weighted_average(pred: &[i64; 4], w_in: &[u32; 4]) -> i64 {
let mut weight_sum: u32 = w_in.iter().sum();
let log_weight = Self::floor_log2(weight_sum as u64);
let mut w = [0u32; 4];
weight_sum = 0;
for i in 0..4 {
w[i] = w_in[i] >> (log_weight - 4);
weight_sum += w[i];
}
let mut sum: i64 = (weight_sum as i64 >> 1) - 1;
for i in 0..4 {
sum += pred[i] * w[i] as i64;
}
(sum * WP_DIV[(weight_sum - 1) as usize] as i64) >> 24
}
#[inline]
pub(crate) fn predict(
&mut self,
x: usize,
y: usize,
n: i64,
w: i64,
ne: i64,
nw: i64,
nn: i64,
) -> i64 {
let xsize = self.xsize;
let cur_row = if y & 1 == 1 { 0 } else { xsize + 2 };
let prev_row = if y & 1 == 1 { xsize + 2 } else { 0 };
let pos_n = prev_row + x;
let pos_ne = if x < xsize - 1 { pos_n + 1 } else { pos_n };
let pos_nw = if x > 0 { pos_n - 1 } else { pos_n };
let mut weights = [0u32; 4];
for i in 0..4 {
let s = self.pred_errors[i][pos_n] as u64
+ self.pred_errors[i][pos_ne] as u64
+ self.pred_errors[i][pos_nw] as u64;
weights[i] = Self::error_weight(s, self.params.w[i]);
}
let an = Self::add_bits(n);
let aw = Self::add_bits(w);
let ane = Self::add_bits(ne);
let anw = Self::add_bits(nw);
let ann = Self::add_bits(nn);
let te_w = if x == 0 {
0
} else {
self.error[cur_row + x - 1]
};
let te_n = self.error[pos_n];
let te_nw = self.error[pos_nw];
let te_ne = self.error[pos_ne];
let mut wpp = te_w;
if te_n.abs() > wpp.abs() {
wpp = te_n;
}
if te_nw.abs() > wpp.abs() {
wpp = te_nw;
}
if te_ne.abs() > wpp.abs() {
wpp = te_ne;
}
self.wp_prop = wpp;
let s_wn = te_n + te_w;
self.prediction[0] = aw + ane - an;
self.prediction[1] = an - (((s_wn + te_ne) * self.params.p[0]) >> 5);
self.prediction[2] = aw - (((s_wn + te_nw) * self.params.p[1]) >> 5);
self.prediction[3] = an
- ((te_nw * self.params.p[2]
+ te_n * self.params.p[3]
+ te_ne * self.params.p[4]
+ (ann - an) * self.params.p[5]
+ (anw - aw) * self.params.p[6])
>> 5);
let pred = Self::weighted_average(&self.prediction, &weights);
if ((te_n ^ te_w) | (te_n ^ te_nw)) > 0 {
self.pred = pred;
(pred + WP_PRED_ROUND) >> WP_EXTRA_BITS
} else {
let mx = aw.max(ane).max(an);
let mn = aw.min(ane).min(an);
let predc = pred.max(mn).min(mx);
self.pred = predc;
(predc + WP_PRED_ROUND) >> WP_EXTRA_BITS
}
}
#[inline]
pub(crate) fn update(&mut self, val: i64, x: usize, y: usize) {
let xsize = self.xsize;
let cur_row = if y & 1 == 1 { 0 } else { xsize + 2 };
let prev_row = if y & 1 == 1 { xsize + 2 } else { 0 };
let valb = Self::add_bits(val);
self.error[cur_row + x] = self.pred - valb;
for i in 0..4 {
let e = ((self.prediction[i] - valb).abs() + WP_PRED_ROUND) >> WP_EXTRA_BITS;
self.pred_errors[i][cur_row + x] = e as u32;
self.pred_errors[i][prev_row + x + 1] += e as u32;
}
}
}
fn wp_sample_cost(
get: impl Fn(usize, usize) -> i32,
width: usize,
height: usize,
params: WpParams,
) -> (u64, usize) {
let cw = width.min(128);
let ch = height.min(128);
let xs = if width > cw { [0, width - cw] } else { [0, 0] };
let ys = if height > ch {
[0, height - ch]
} else {
[0, 0]
};
let nx = 1 + usize::from(xs[1] != xs[0]);
let ny = 1 + usize::from(ys[1] != ys[0]);
let mut cost = 0u64;
let mut count = 0usize;
for &y0 in &ys[..ny] {
for &x0 in &xs[..nx] {
let local_get = |x: usize, y: usize| get(x0 + x, y0 + y);
let mut wp = WpState::with_params(cw, params);
for y in 0..ch {
for x in 0..cw {
let neighbors = predictor_neighbors(&local_get, x, y, cw);
let value = local_get(x, y);
let prediction = wp.predict(
x,
y,
neighbors.top,
neighbors.left,
neighbors.top_right,
neighbors.top_left,
neighbors.top_top,
);
let packed = pack_signed(value.wrapping_sub(prediction as i32));
let (_, extra_bits, _) = crate::entropy::uint_encode(packed);
let magnitude_bits = packed
.checked_add(1)
.map_or(32, |value| 32 - value.leading_zeros());
cost += extra_bits as u64 + u64::from(magnitude_bits);
count += 1;
wp.update(value as i64, x, y);
}
}
}
}
(cost, count)
}
fn choose_wp_params(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
num_color: usize,
header_count: usize,
num_threads: usize,
) -> WpParams {
let width = linear.xsize();
let height = linear.ysize();
let nb_chans = num_color + usize::from(alpha.is_some());
let total_values = width.saturating_mul(height).saturating_mul(nb_chans);
let scores = crate::thread_pool::steal_map(WpParams::PRESETS.len(), num_threads, |preset| {
let params = WpParams::PRESETS[preset];
let mut sample_cost = 0u64;
let mut samples = 0usize;
for channel in 0..num_color {
let plane = linear.plane_data(channel);
let (cost, count) = wp_sample_cost(|x, y| plane[y * width + x], width, height, params);
sample_cost += cost;
samples += count;
}
if let Some(alpha) = alpha {
let (cost, count) =
wp_sample_cost(|x, y| alpha.get_i32(y * width + x), width, height, params);
sample_cost += cost;
samples += count;
}
let scaled = sample_cost as f64 * total_values as f64 / samples.max(1) as f64;
scaled
+ if preset == 0 {
0.0
} else {
(51 * header_count) as f64
}
});
let best = scores
.iter()
.enumerate()
.min_by(|a, b| a.1.total_cmp(b.1))
.map_or(0, |(index, _)| index);
WpParams::PRESETS[best]
}
const GROUP_DIM: usize = 256;
const LF_GROUP_DIM: usize = 2048;
struct LosslessScratchGuard;
impl Drop for LosslessScratchGuard {
fn drop(&mut self) {
release_lossless_tls_scratches();
}
}
fn release_lossless_tls_scratches() {
GRADIENT_SCRATCH.with_borrow_mut(|scratch| *scratch = GradientScratch::default());
ORDER0_ENTROPY_SCRATCH.with_borrow_mut(|scratch| *scratch = Vec::new());
THRESHOLD_SCRATCH.with_borrow_mut(|scratch| scratch.hist_scratch = Vec::new());
lz77::release_tls_scratch();
crate::entropy::release_huffman_tree_scratch();
}
#[cfg(test)]
fn lossless_tls_scratch_capacity() -> usize {
let gradient = GRADIENT_SCRATCH.with_borrow(|scratch| {
scratch.cur.capacity() + scratch.prev.capacity() + scratch.buf.capacity()
});
let order0 = ORDER0_ENTROPY_SCRATCH.with_borrow(|scratch| scratch.capacity());
let threshold = THRESHOLD_SCRATCH.with_borrow(|scratch| scratch.hist_scratch.capacity());
gradient
+ order0
+ threshold
+ lz77::tls_scratch_capacity()
+ crate::entropy::huffman_tree_scratch_capacity()
}
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 encode_frame_lossless(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
patches: bool,
num_color: usize,
speed: crate::Speed,
num_threads: usize,
writer: &mut BitWriter,
) {
if patches
&& num_color == 3
&& let Some(plan) = find_lossless_patches(linear)
{
let mut regular_writer = BitWriter::new();
encode_frame_lossless_core(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
num_threads,
ModularFrameKind::Regular,
&mut regular_writer,
);
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,
num_threads,
ModularFrameKind::ReferenceOnly {
width: plan.atlas.xsize(),
height: plan.atlas.ysize(),
},
&mut patched_writer,
);
encode_frame_lossless_core(
&plan.base,
alpha,
max_bits,
false,
num_color,
speed,
num_threads,
ModularFrameKind::Patched(&plan.references),
&mut patched_writer,
);
if patched_writer.bits_written() < regular_writer.bits_written() {
writer.append(&patched_writer);
} else {
writer.append(®ular_writer);
}
return;
}
encode_frame_lossless_core(
linear,
alpha,
max_bits,
progressive,
num_color,
speed,
num_threads,
ModularFrameKind::Regular,
writer,
);
}
#[allow(clippy::too_many_arguments)]
fn encode_frame_lossless_core(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
max_bits: u32,
progressive: bool,
num_color: usize,
speed: crate::Speed,
num_threads: usize,
frame_kind: ModularFrameKind<'_>,
writer: &mut BitWriter,
) {
let _scratch_guard = LosslessScratchGuard;
let num_threads = num_threads.max(1);
let min_symbol: u32 = if max_bits <= 13 {
LZ77_MIN_SYMBOL
} else {
4 * max_bits + 24
};
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 frame_kind.is_regular()
&& single_group
&& num_color == 3
&& try_encode_palette_single_group(
linear,
alpha,
xsize,
ysize,
min_symbol,
grad_pack_fn,
speed,
writer,
)
{
return;
}
if frame_kind.is_regular()
&& !single_group
&& num_color == 3
&& try_encode_local_palette_multi_group(
linear,
alpha,
xsize,
ysize,
xsize_groups,
ysize_groups,
num_dc_groups,
min_symbol,
grad_pack_fn,
speed,
num_threads,
writer,
)
{
return;
}
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,
num_threads,
writer,
);
return;
}
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,
num_threads,
writer,
)
{
return;
}
let adaptive_search = speed == crate::Speed::Slow;
let wp_header_count = if single_group {
1
} else {
2 + num_dc_groups + num_ac_groups
};
let mut wp_params = if adaptive_search {
choose_wp_params(linear, alpha, num_color, wp_header_count, num_threads)
} else {
WpParams::DEFAULT
};
let predictors = if adaptive_search {
choose_predictors_with_wp(linear, alpha, xsize, ysize, num_threads, wp_params)
} else {
[PREDICTOR_WEIGHTED; 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 frame_kind.is_regular() && adaptive_search && num_color == 3 {
if single_group {
if try_encode_context_tree_single_group(
linear,
alpha,
xsize,
ysize,
&predictors,
min_symbol,
num_threads,
wp_params,
writer,
) {
return;
}
} else if try_encode_context_tree_multi_group(
linear,
alpha,
xsize,
ysize,
&predictors,
xsize_groups,
ysize_groups,
num_dc_groups,
min_symbol,
num_threads,
wp_params,
writer,
) {
return;
}
}
if !chan_preds.contains(&PREDICTOR_WEIGHTED) {
wp_params = WpParams::DEFAULT;
}
write_frame_header_modular_kind(alpha.is_some(), frame_kind, writer);
if single_group {
let mut section = BitWriter::new();
if let ModularFrameKind::Patched(references) = frame_kind {
write_patch_dictionary(references, alpha.is_some(), &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, &mut section);
let tokens = tokenize_all_with_wp(
linear,
alpha,
xsize,
ysize,
0,
0,
xsize,
ysize,
num_color,
&chan_preds,
grad_pack_fn,
num_threads,
wp_params,
);
let distance_ctx = nb_chans as u32;
let lz_tokens = lz77_compress_for_speed(&tokens, distance_ctx, speed);
let code = build_lz_pixel_code(
&lz_tokens,
nb_chans,
min_symbol,
speed == crate::Speed::Slow,
);
write_local_tree_lz77(&chan_preds, &code, min_symbol, &mut section);
for t in &lz_tokens {
write_lz_token(*t, &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(§ion);
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>> =
crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
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);
let toks = tokenize_all_with_wp(
linear,
alpha,
xsize,
ysize,
x0,
y0,
gw,
gh,
num_color,
&chan_preds,
grad_pack_fn,
1,
wp_params,
);
lz77_compress_for_speed(&toks, distance_ctx, speed)
});
let mut all_lz: Vec<LzToken> = Vec::new();
for lz in &group_lz_tokens {
all_lz.extend_from_slice(lz);
}
let code = build_lz_pixel_code(&all_lz, nb_chans, min_symbol, speed == crate::Speed::Slow);
if let ModularFrameKind::Patched(references) = frame_kind {
write_patch_dictionary(references, alpha.is_some(), &mut sections[0]);
}
sections[0].write(1, 1); sections[0].write(1, 1); write_local_tree_lz77(&chan_preds, &code, min_symbol, &mut sections[0]);
sections[0].write(1, 1);
write_wp_header(wp_params, &mut sections[0]);
write_modular_transforms(nb_chans, &mut sections[0]);
sections[0].zero_pad_to_byte();
for i in 0..num_dc_groups {
sections[1 + i].write(1, 1); write_wp_header(wp_params, &mut sections[1 + i]);
sections[1 + i].write(2, 0); sections[1 + i].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();
for gy in 0..ysize_groups {
for gx in 0..xsize_groups {
let group_index = gy * xsize_groups + gx;
let section_idx = 2 + num_dc_groups + group_index;
sections[section_idx].write(1, 1);
write_wp_header(wp_params, &mut sections[section_idx]);
sections[section_idx].write(2, 0);
for t in &group_lz_tokens[group_index] {
write_lz_token(*t, &code, min_symbol, &mut sections[section_idx]);
}
sections[section_idx].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();
for s in §ions {
writer.append(s);
writer.zero_pad_to_byte();
}
}
}
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<'_>, w: &mut BitWriter) {
match kind {
ModularFrameKind::Regular => write_frame_header_modular(has_alpha, w),
ModularFrameKind::Patched(_) => write_frame_header_modular_flags(has_alpha, 2, 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, 1); 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(has_alpha: bool, w: &mut BitWriter) {
write_frame_header_modular_flags(has_alpha, 0, w);
}
fn write_frame_header_modular_flags(has_alpha: bool, flags: u64, 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, 0b01); 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,
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, PATCH_REF_ID));
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, (PATCH_TILE - 1) as u32));
tokens.push(Token::new(PATCH_SIZE, (PATCH_TILE - 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);
let code_ref = code.as_ref();
w.write(1, 0); write_entropy_code(&code_ref, w);
for token in tokens {
write_token(token, &code_ref, w);
}
}
fn write_modular_transforms(nb_chans: usize, w: &mut BitWriter) {
if nb_chans >= 3 {
w.write(2, 0b01);
w.write(2, 0b00); w.write(2, 0b00); w.write(3, 0); w.write(2, 0b00); } else {
w.write(2, 0b00); }
}
fn write_modular_transforms_rct_squeeze(steps: &[crate::squeeze::SqueezeStep], w: &mut BitWriter) {
w.write(2, 0b10);
w.write(4, 0);
w.write(2, 0b00);
w.write(2, 0b00);
w.write(3, 0);
w.write(2, 0b00);
w.write(2, 0b10); let n = steps.len() as u32;
if n == 0 {
w.write(2, 0b00);
} else if n <= 16 {
w.write(2, 0b01);
w.write(4, (n - 1) as u64);
} else if n <= 72 {
w.write(2, 0b10);
w.write(6, (n - 9) as u64);
} else {
w.write(2, 0b11);
w.write(8, (n - 41) as u64);
}
for s in steps {
w.write(1, if s.horizontal { 1 } else { 0 });
w.write(1, if s.in_place { 1 } else { 0 });
debug_assert!(s.begin_c < 8);
w.write(2, 0b00);
w.write(3, s.begin_c as u64);
match s.num_c {
1 => w.write(2, 0b00),
2 => w.write(2, 0b01),
3 => w.write(2, 0b10),
n => {
w.write(2, 0b11);
w.write(4, (n - 4) as u64);
}
}
}
}
fn encode_squeeze_single_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
min_symbol: u32,
grad_pack_fn: GradPackInteriorFn,
speed: crate::Speed,
num_threads: usize,
writer: &mut BitWriter,
) {
use crate::squeeze::{Channel, apply_step_forward, default_squeeze_steps};
let num_c = if alpha.is_some() { 4 } else { 3 };
let mut channels: Vec<Channel> = Vec::with_capacity(num_c);
for c in 0..3usize {
let mut ch = Channel::new(xsize, ysize);
for y in 0..ysize {
let row = linear.plane_row(c, y);
ch.data[y * xsize..y * xsize + xsize].copy_from_slice(&row[..xsize]);
}
channels.push(ch);
}
if let Some(a) = alpha {
let mut ch = Channel::new(xsize, ysize);
match a {
AlphaPlane::U8(data) => {
for (row, src_row) in ch
.data
.chunks_exact_mut(xsize)
.zip(data.chunks_exact(xsize))
{
for (dst, &src) in row[..xsize].iter_mut().zip(src_row.iter()) {
*dst = src as i32;
}
}
}
AlphaPlane::U16 { data, bits: _ } => {
for (row, src_row) in ch
.data
.chunks_exact_mut(xsize)
.zip(data.chunks_exact(xsize))
{
for (dst, &src) in row[..xsize].iter_mut().zip(src_row.iter()) {
*dst = src as i32;
}
}
}
AlphaPlane::F32(data) => {
for (row, src_row) in ch
.data
.chunks_exact_mut(xsize)
.zip(data.chunks_exact(xsize))
{
for (dst, &src) in row[..xsize].iter_mut().zip(src_row.iter()) {
*dst = src;
}
}
}
}
channels.push(ch);
}
let steps = default_squeeze_steps(xsize, ysize, num_c);
for s in &steps {
apply_step_forward(&mut channels, s);
}
let nb = channels.len();
let predictors: Vec<u32> = if speed == crate::Speed::Slow {
crate::thread_pool::steal_map(channels.len(), num_threads, |c| {
let ch = &channels[c];
let data = &ch.data;
let w = ch.w;
let get = move |gx: usize, gy: usize| data[gy * w + gx];
choose_predictor_for_plane(get, ch.w, ch.h)
})
} else {
vec![PREDICTOR_WEIGHTED; nb]
};
let channel_tokens = crate::thread_pool::steal_map(nb, num_threads, |c| {
let ch = &channels[c];
let mut tokens = Vec::with_capacity(ch.w * ch.h);
tokenize_plane(
channel_to_context(c, nb),
|x, y| ch.data[y * ch.w + x],
ch.w,
ch.h,
predictors[c],
grad_pack_fn,
&mut tokens,
);
tokens
});
let mut tokens: Vec<Token> = Vec::new();
for channel in channel_tokens {
tokens.extend(channel);
}
write_frame_header_modular(alpha.is_some(), writer);
let mut section = BitWriter::new();
section.write(1, 1); section.write(1, 0); section.write(1, 0); section.write(1, 1); write_modular_transforms_rct_squeeze(&steps, &mut section);
let distance_ctx = nb as u32;
let lz_tokens = lz77_compress_for_speed(&tokens, distance_ctx, speed);
let code = build_lz_pixel_code(&lz_tokens, nb, min_symbol, speed == crate::Speed::Slow);
write_local_tree_lz77(&predictors, &code, min_symbol, &mut section);
for t in &lz_tokens {
write_lz_token(*t, &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(§ion);
writer.zero_pad_to_byte();
}
#[derive(Default)]
struct SqueezePredictorCost {
costs: PredictorCosts,
}
impl SqueezePredictorCost {
fn add_crop(&mut self, get: impl Fn(usize, usize) -> i32, w: usize, h: usize) {
if w == 0 || h == 0 {
return;
}
let mut wp = WpState::new(w);
for y in 0..h {
for x in 0..w {
let value = get(x, y) as i64;
let neighbors = predictor_neighbors(&get, x, y, w);
let weighted = wp.predict(
x,
y,
neighbors.top,
neighbors.left,
neighbors.top_right,
neighbors.top_left,
neighbors.top_top,
);
self.costs.add(value, neighbors, weighted);
wp.update(value, x, y);
}
}
}
fn predictor(&self) -> u32 {
self.costs.best_predictor()
}
}
#[allow(clippy::too_many_arguments)]
fn for_each_squeeze_group_crop(
channels: &[crate::squeeze::Channel],
split: usize,
gdim: usize,
gx: usize,
gy: usize,
minsh: i32,
maxsh: i32,
mut visit: impl FnMut(usize, usize, usize, usize, usize, usize),
) {
let mut within = 0usize;
for c in split..channels.len() {
let ch = &channels[c];
let msh = ch.hshift.min(ch.vshift);
if msh < minsh || msh > maxsh {
continue;
}
let hs = ch.hshift as usize;
let vs = ch.vshift as usize;
let rx0 = (gx * gdim) >> hs;
let ry0 = (gy * gdim) >> vs;
if rx0 >= ch.w || ry0 >= ch.h {
continue;
}
let rw = (gdim >> hs).min(ch.w - rx0);
let rh = (gdim >> vs).min(ch.h - ry0);
if rw == 0 || rh == 0 {
continue;
}
visit(within, c, rx0, ry0, rw, rh);
within += 1;
}
}
#[allow(clippy::too_many_arguments)]
fn encode_squeeze_multigroup(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
min_symbol: u32,
xsize_groups: usize,
ysize_groups: usize,
xsize_dc_groups: usize,
ysize_dc_groups: usize,
num_dc_groups: usize,
num_ac_groups: usize,
grad_pack_fn: GradPackInteriorFn,
speed: crate::Speed,
num_threads: usize,
writer: &mut BitWriter,
) -> bool {
use crate::squeeze::{Channel, apply_step_forward, default_squeeze_steps};
let num_c = if alpha.is_some() { 4 } else { 3 };
let mut channels: Vec<Channel> = Vec::with_capacity(num_c);
for c in 0..3usize {
let mut ch = Channel::new(xsize, ysize);
for y in 0..ysize {
let row = linear.plane_row(c, y);
ch.data[y * xsize..y * xsize + xsize].copy_from_slice(&row[..xsize]);
}
channels.push(ch);
}
if let Some(a) = alpha {
let mut ch = Channel::new(xsize, ysize);
for y in 0..ysize {
for x in 0..xsize {
ch.data[y * xsize + x] = a.get_i32(y * xsize + x);
}
}
channels.push(ch);
}
let steps = default_squeeze_steps(xsize, ysize, num_c);
for s in &steps {
apply_step_forward(&mut channels, s);
}
let nb = channels.len();
let split = channels
.iter()
.position(|c| c.w > GROUP_DIM || c.h > GROUP_DIM)
.unwrap_or(nb);
let predictors: Vec<u32> = if speed == crate::Speed::Slow {
let mut costs: Vec<SqueezePredictorCost> =
(0..nb).map(|_| SqueezePredictorCost::default()).collect();
for c in 0..split {
let ch = &channels[c];
costs[c].add_crop(|x, y| ch.data[y * ch.w + x], ch.w, ch.h);
}
for gy in 0..ysize_dc_groups {
for gx in 0..xsize_dc_groups {
for_each_squeeze_group_crop(
&channels,
split,
LF_GROUP_DIM,
gx,
gy,
3,
1000,
|within, c, x0, y0, w, h| {
let ch = &channels[c];
costs[within].add_crop(|x, y| ch.data[(y0 + y) * ch.w + x0 + x], w, h);
},
);
}
}
for gy in 0..ysize_groups {
for gx in 0..xsize_groups {
for_each_squeeze_group_crop(
&channels,
split,
GROUP_DIM,
gx,
gy,
0,
2,
|within, c, x0, y0, w, h| {
let ch = &channels[c];
costs[within].add_crop(|x, y| ch.data[(y0 + y) * ch.w + x0 + x], w, h);
},
);
}
}
costs.iter().map(SqueezePredictorCost::predictor).collect()
} else {
vec![PREDICTOR_WEIGHTED; nb]
};
let distance_ctx = nb as u32;
let global_channel_tokens = crate::thread_pool::steal_map(split, num_threads, |c| {
let ch = &channels[c];
let ctx = channel_to_context(c, nb);
let data = &ch.data;
let w = ch.w;
let get = move |gx: usize, gy: usize| data[gy * w + gx];
let mut tokens = Vec::with_capacity(ch.w * ch.h);
tokenize_plane(
ctx,
get,
ch.w,
ch.h,
predictors[c],
grad_pack_fn,
&mut tokens,
);
tokens
});
let mut global_tokens: Vec<Token> = Vec::new();
for channel in global_channel_tokens {
global_tokens.extend(channel);
}
let global_lz = lz77_compress_for_speed(&global_tokens, distance_ctx, speed);
let mut all_lz: Vec<LzToken> = global_lz.clone();
let crop_group = |gdim: usize, gx: usize, gy: usize, minsh: i32, maxsh: i32| -> Vec<LzToken> {
let mut gtok: Vec<Token> = Vec::new();
for_each_squeeze_group_crop(
&channels,
split,
gdim,
gx,
gy,
minsh,
maxsh,
|within, c, rx0, ry0, rw, rh| {
let ch = &channels[c];
let ctx = channel_to_context(within, nb);
let pred = predictors[within];
let data = &ch.data;
let w = ch.w;
let get = move |lx: usize, ly: usize| data[(ry0 + ly) * w + (rx0 + lx)];
tokenize_plane(ctx, get, rw, rh, pred, grad_pack_fn, &mut gtok);
},
);
lz77_compress_for_speed(>ok, distance_ctx, speed)
};
let dc_group_lz = crate::thread_pool::steal_map(num_dc_groups, num_threads, |group_index| {
let gx = group_index % xsize_dc_groups;
let gy = group_index / xsize_dc_groups;
crop_group(LF_GROUP_DIM, gx, gy, 3, 1000)
});
for glz in &dc_group_lz {
all_lz.extend_from_slice(glz);
}
let ac_group_lz = crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
crop_group(GROUP_DIM, gx, gy, 0, 2)
});
for glz in &ac_group_lz {
all_lz.extend_from_slice(glz);
}
let code = build_lz_pixel_code(&all_lz, nb, min_symbol, speed == crate::Speed::Slow);
write_frame_header_modular(alpha.is_some(), 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_local_tree_lz77(&predictors, &code, min_symbol, &mut sections[0]);
sections[0].write(1, 1); sections[0].write(1, 1); write_modular_transforms_rct_squeeze(&steps, &mut sections[0]);
for t in &global_lz {
write_lz_token(*t, &code, min_symbol, &mut sections[0]);
}
sections[0].zero_pad_to_byte();
for (k, section) in sections[1..num_dc_groups + 1].iter_mut().enumerate() {
let i = k + 1;
section.write(1, 1); section.write(1, 1); section.write(2, 0); for t in &dc_group_lz[i] {
write_lz_token(*t, &code, min_symbol, section);
}
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 g in 0..num_ac_groups {
let idx = 2 + num_dc_groups + g;
sections[idx].write(1, 1); sections[idx].write(1, 1); sections[idx].write(2, 0); for t in &ac_group_lz[g] {
write_lz_token(*t, &code, min_symbol, &mut sections[idx]);
}
sections[idx].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();
for s in §ions {
writer.append(s);
writer.zero_pad_to_byte();
}
true
}
fn write_palette_transform(num_c: u32, nb_colors: u32, w: &mut BitWriter) {
debug_assert!(matches!(num_c, 3 | 4));
w.write(2, 0b01);
w.write(2, 0b01);
w.write(2, 0b00);
w.write(3, 0);
w.write(2, if num_c == 3 { 0b01 } else { 0b10 });
if nb_colors <= 255 {
w.write(2, 0b00); w.write(8, nb_colors as u64);
} else {
w.write(2, 0b01);
w.write(10, (nb_colors - 256) as u64);
}
w.write(2, 0b00);
w.write(4, 0);
}
fn try_encode_palette_single_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
min_symbol: u32,
grad_pack_fn: GradPackInteriorFn,
speed: crate::Speed,
writer: &mut BitWriter,
) -> bool {
use std::collections::HashMap;
let npx = xsize * ysize;
let num_c = 3 + usize::from(alpha.is_some());
let plane0 = linear.plane_data(0);
let plane1 = linear.plane_data(1);
let plane2 = linear.plane_data(2);
let color_at = |gx: usize, gy: usize| {
let (r, g, b) = inverse_ycocg(
plane0[gy * xsize + gx],
plane1[gy * xsize + gx],
plane2[gy * xsize + gx],
);
[r, g, b, alpha.map_or(0, |a| a.get_i32(gy * xsize + gx))]
};
let mut seen: HashMap<[i32; 4], ()> = HashMap::with_capacity(257);
for gy in 0..ysize {
for gx in 0..xsize {
seen.entry(color_at(gx, gy)).or_insert(());
if seen.len() > 256 {
return false;
}
}
}
let nb_colors = seen.len();
if nb_colors == 0 {
return false;
}
let mut colors: Vec<[i32; 4]> = seen.keys().copied().collect();
colors.sort_unstable();
let mut idx_of: HashMap<[i32; 4], 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 (i, color) in colors.iter().enumerate() {
for c in 0..num_c {
palette_ch[c * nb_colors + i] = color[c];
}
}
let mut index_img = Vec::with_capacity(npx);
for gy in 0..ysize {
for gx in 0..xsize {
index_img.push(idx_of[&color_at(gx, gy)] as i32);
}
}
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 speed == crate::Speed::Slow {
[
choose_predictor_for_plane(pget, nb_colors, num_c),
choose_predictor_for_plane(iget, xsize, ysize),
]
} else {
[PREDICTOR_WEIGHTED; 2]
};
write_frame_header_modular(alpha.is_some(), writer);
let nb_chans = 2usize;
let mut section = BitWriter::new();
section.write(1, 1); section.write(1, 0); section.write(1, 0); section.write(1, 1); write_palette_transform(num_c as u32, nb_colors as u32, &mut section);
let mut tokens: Vec<Token> = Vec::with_capacity(num_c * nb_colors + npx);
tokenize_plane(
channel_to_context(0, nb_chans),
pget,
nb_colors,
num_c,
preds[0],
grad_pack_fn,
&mut tokens,
);
tokenize_plane(
channel_to_context(1, nb_chans),
iget,
xsize,
ysize,
preds[1],
grad_pack_fn,
&mut tokens,
);
let distance_ctx = nb_chans as u32;
let lz_tokens = lz77_compress_for_speed(&tokens, distance_ctx, speed);
let code = build_lz_pixel_code(
&lz_tokens,
nb_chans,
min_symbol,
speed == crate::Speed::Slow,
);
write_local_tree_lz77(&preds, &code, min_symbol, &mut section);
for t in &lz_tokens {
write_lz_token(*t, &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(§ion);
writer.zero_pad_to_byte();
true
}
struct LocalPaletteGroup {
palette: Vec<i32>,
indices: Vec<i32>,
nb_colors: usize,
w: usize,
h: usize,
}
fn estimated_local_stream_bits(
tokens: &[Token],
predictors: &[u32],
num_contexts: usize,
min_symbol: u32,
speed: crate::Speed,
) -> usize {
let lz = lz77_compress_runs(tokens, num_contexts as u32);
let code = build_lz_pixel_code(&lz, num_contexts, min_symbol, speed == crate::Speed::Slow);
let mut writer = BitWriter::new();
write_local_tree_lz77(predictors, &code, min_symbol, &mut writer);
for token in &lz {
write_lz_token(*token, &code, min_symbol, &mut writer);
}
writer.bits_written()
}
#[allow(clippy::too_many_arguments)]
fn local_palette_is_better(
palette: &LocalPaletteGroup,
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
x0: usize,
y0: usize,
min_symbol: u32,
grad_pack_fn: GradPackInteriorFn,
speed: crate::Speed,
) -> bool {
let nb_chans = 3 + usize::from(alpha.is_some());
let palette_predictors = if speed == crate::Speed::Slow {
[
choose_predictor_for_plane(
|x, y| palette.palette[y * palette.nb_colors + x],
palette.nb_colors,
nb_chans,
),
choose_predictor_for_plane(
|x, y| palette.indices[y * palette.w + x],
palette.w,
palette.h,
),
]
} else {
[PREDICTOR_WEIGHTED; 2]
};
let mut palette_tokens =
Vec::with_capacity(nb_chans * palette.nb_colors + palette.w * palette.h);
tokenize_plane(
channel_to_context(0, 2),
|x, y| palette.palette[y * palette.nb_colors + x],
palette.nb_colors,
nb_chans,
palette_predictors[0],
grad_pack_fn,
&mut palette_tokens,
);
tokenize_plane(
channel_to_context(1, 2),
|x, y| palette.indices[y * palette.w + x],
palette.w,
palette.h,
palette_predictors[1],
grad_pack_fn,
&mut palette_tokens,
);
let mut palette_transform = BitWriter::new();
write_palette_transform(
nb_chans as u32,
palette.nb_colors as u32,
&mut palette_transform,
);
let palette_bits =
estimated_local_stream_bits(&palette_tokens, &palette_predictors, 2, min_symbol, speed)
+ palette_transform.bits_written();
let plain_predictors: Vec<u32> = if speed == crate::Speed::Slow {
(0..nb_chans)
.map(|chan| {
if chan < 3 {
let plane = linear.plane_data(chan);
choose_predictor_for_plane(
|x, y| plane[(y0 + y) * xsize + x0 + x],
palette.w,
palette.h,
)
} else {
let alpha = alpha.expect("alpha channel must exist");
choose_predictor_for_plane(
|x, y| alpha.get_i32((y0 + y) * xsize + x0 + x),
palette.w,
palette.h,
)
}
})
.collect()
} else {
vec![PREDICTOR_WEIGHTED; nb_chans]
};
let plain_tokens = tokenize_all(
linear,
alpha,
xsize,
linear.ysize(),
x0,
y0,
palette.w,
palette.h,
3,
&plain_predictors,
grad_pack_fn,
1,
);
let plain_bits = estimated_local_stream_bits(
&plain_tokens,
&plain_predictors,
nb_chans,
min_symbol,
speed,
) + 2;
palette_bits < plain_bits
}
fn build_local_palette_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
x0: usize,
y0: usize,
w: usize,
h: usize,
) -> Option<LocalPaletteGroup> {
use std::collections::HashMap;
let num_c = 3 + usize::from(alpha.is_some());
let num_pixels = w * h;
let plane0 = linear.plane_data(0);
let plane1 = linear.plane_data(1);
let plane2 = linear.plane_data(2);
let tuple_at = |gx: usize, gy: usize| {
[
plane0[gy * xsize + gx],
plane1[gy * xsize + gx],
plane2[gy * xsize + gx],
alpha.map_or(0, |a| a.get_i32(gy * xsize + gx)),
]
};
let mut seen = HashMap::<[i32; 4], ()>::with_capacity(257);
for y in 0..h {
for x in 0..w {
let gx = x0 + x;
let gy = y0 + y;
seen.entry(tuple_at(gx, gy)).or_insert(());
if seen.len() > 256 {
return None;
}
}
}
let nb_colors = seen.len();
let palette_samples = num_pixels + num_c * nb_colors + 16;
if nb_colors == 0 || palette_samples >= num_c * num_pixels {
return None;
}
let mut colors: Vec<[i32; 4]> = seen.keys().copied().collect();
colors.sort_unstable();
let mut index_of = HashMap::<[i32; 4], i32>::with_capacity(nb_colors);
let mut palette = vec![0i32; num_c * nb_colors];
for (index, color) in colors.iter().enumerate() {
index_of.insert(*color, index as i32);
for c in 0..num_c {
palette[c * nb_colors + index] = color[c];
}
}
let mut indices = Vec::with_capacity(num_pixels);
for y in 0..h {
for x in 0..w {
indices.push(index_of[&tuple_at(x0 + x, y0 + y)]);
}
}
Some(LocalPaletteGroup {
palette,
indices,
nb_colors,
w,
h,
})
}
#[allow(clippy::too_many_arguments)]
fn try_encode_local_palette_multi_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
xsize_groups: usize,
ysize_groups: usize,
num_dc_groups: usize,
min_symbol: u32,
grad_pack_fn: GradPackInteriorFn,
speed: crate::Speed,
num_threads: usize,
writer: &mut BitWriter,
) -> bool {
let nb_chans = 3 + usize::from(alpha.is_some());
let num_ac_groups = xsize_groups * ysize_groups;
let palettes = crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * GROUP_DIM;
let y0 = gy * GROUP_DIM;
let w = GROUP_DIM.min(xsize - x0);
let h = GROUP_DIM.min(ysize - y0);
let palette = build_local_palette_group(linear, alpha, xsize, x0, y0, w, h)?;
local_palette_is_better(
&palette,
linear,
alpha,
xsize,
x0,
y0,
min_symbol,
grad_pack_fn,
speed,
)
.then_some(palette)
});
if !palettes.iter().any(Option::is_some) {
return false;
}
let predictors: Vec<u32> = if speed == crate::Speed::Slow {
crate::thread_pool::steal_map(nb_chans, num_threads, |slot| {
let mut cost = SqueezePredictorCost::default();
for (group_index, palette) in palettes.iter().enumerate() {
if let Some(palette) = palette {
if slot == 0 {
cost.add_crop(
|x, y| palette.palette[y * palette.nb_colors + x],
palette.nb_colors,
nb_chans,
);
} else if slot == 1 {
cost.add_crop(
|x, y| palette.indices[y * palette.w + x],
palette.w,
palette.h,
);
}
continue;
}
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * GROUP_DIM;
let y0 = gy * GROUP_DIM;
let w = GROUP_DIM.min(xsize - x0);
let h = GROUP_DIM.min(ysize - y0);
if slot < 3 {
let plane = linear.plane_data(slot);
cost.add_crop(|x, y| plane[(y0 + y) * xsize + x0 + x], w, h);
} else {
let alpha = alpha.expect("alpha slot requires alpha channel");
cost.add_crop(|x, y| alpha.get_i32((y0 + y) * xsize + x0 + x), w, h);
}
}
cost.predictor()
})
} else {
vec![PREDICTOR_WEIGHTED; nb_chans]
};
let distance_ctx = nb_chans as u32;
let group_lz_tokens: Vec<Vec<LzToken>> =
crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
let mut tokens = if let Some(palette) = &palettes[group_index] {
Vec::with_capacity(nb_chans * palette.nb_colors + palette.w * palette.h)
} else {
Vec::new()
};
if let Some(palette) = &palettes[group_index] {
tokenize_plane(
channel_to_context(0, nb_chans),
|x, y| palette.palette[y * palette.nb_colors + x],
palette.nb_colors,
nb_chans,
predictors[0],
grad_pack_fn,
&mut tokens,
);
tokenize_plane(
channel_to_context(1, nb_chans),
|x, y| palette.indices[y * palette.w + x],
palette.w,
palette.h,
predictors[1],
grad_pack_fn,
&mut tokens,
);
} else {
let gx = group_index % xsize_groups;
let gy = group_index / xsize_groups;
let x0 = gx * GROUP_DIM;
let y0 = gy * GROUP_DIM;
let w = GROUP_DIM.min(xsize - x0);
let h = GROUP_DIM.min(ysize - y0);
tokens = tokenize_all(
linear,
alpha,
xsize,
ysize,
x0,
y0,
w,
h,
3,
&predictors,
grad_pack_fn,
1,
);
}
lz77_compress_for_speed(&tokens, distance_ctx, speed)
});
let mut all_lz = Vec::with_capacity(group_lz_tokens.iter().map(Vec::len).sum());
for tokens in &group_lz_tokens {
all_lz.extend_from_slice(tokens);
}
let code = build_lz_pixel_code(&all_lz, nb_chans, min_symbol, speed == crate::Speed::Slow);
write_frame_header_modular(alpha.is_some(), 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_local_tree_lz77(&predictors, &code, min_symbol, &mut sections[0]);
sections[0].write(1, 1); sections[0].write(1, 1); write_modular_transforms(nb_chans, &mut sections[0]);
sections[0].zero_pad_to_byte();
for section in sections[1..num_dc_groups + 1].iter_mut() {
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 group_index in 0..num_ac_groups {
let section_idx = 2 + num_dc_groups + group_index;
sections[section_idx].write(1, 1); sections[section_idx].write(1, 1); if let Some(palette) = &palettes[group_index] {
write_palette_transform(
nb_chans as u32,
palette.nb_colors as u32,
&mut sections[section_idx],
);
} else {
sections[section_idx].write(2, 0); }
for token in &group_lz_tokens[group_index] {
write_lz_token(*token, &code, min_symbol, &mut sections[section_idx]);
}
sections[section_idx].zero_pad_to_byte();
}
writer.write(1, 0); writer.zero_pad_to_byte();
for section in §ions {
write_toc_entry(section.bits_written() / 8, writer);
}
writer.zero_pad_to_byte();
for section in §ions {
writer.append(section);
writer.zero_pad_to_byte();
}
true
}
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);
}
#[inline]
pub(crate) fn forward_ycocg(r: i32, g: i32, b: i32) -> (i32, i32, i32) {
let co = r - b;
let tmp = b + (co >> 1);
let cg = g - tmp;
let y = tmp + (cg >> 1);
(y, co, cg)
}
#[inline]
pub(crate) fn inverse_ycocg(y: i32, co: i32, cg: i32) -> (i32, i32, i32) {
let tmp = y - (cg >> 1);
let g = cg + tmp;
let b = tmp - (co >> 1);
let r = b + co;
(r, g, b)
}
#[inline]
fn channel_to_context(chan: usize, nb_chans: usize) -> u32 {
(nb_chans - 1 - chan) as u32
}
fn tokenize_all(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
_ysize: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
num_color: usize,
predictors: &[u32],
grad_pack_fn: GradPackInteriorFn,
num_threads: usize,
) -> Vec<Token> {
tokenize_all_with_wp(
linear,
alpha,
xsize,
_ysize,
x0,
y0,
gw,
gh,
num_color,
predictors,
grad_pack_fn,
num_threads,
WpParams::DEFAULT,
)
}
fn tokenize_all_with_wp(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
_ysize: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
num_color: usize,
predictors: &[u32],
grad_pack_fn: GradPackInteriorFn,
num_threads: usize,
wp_params: WpParams,
) -> Vec<Token> {
let nb_chans = num_color + if alpha.is_some() { 1 } else { 0 };
let channel_tokens = crate::thread_pool::steal_map(nb_chans, num_threads, |chan| {
let mut out = Vec::with_capacity(gw * gh);
let ctx = channel_to_context(chan, nb_chans);
if chan < num_color {
let get = |gx: usize, gy: usize| linear.plane_row(chan, y0 + gy)[x0 + gx];
tokenize_plane_with_wp(
ctx,
get,
gw,
gh,
predictors[chan],
grad_pack_fn,
&mut out,
wp_params,
);
} else {
let a = alpha.expect("alpha channel must exist");
let get = |gx: usize, gy: usize| a.get_i32((y0 + gy) * xsize + (x0 + gx));
tokenize_plane_with_wp(
ctx,
get,
gw,
gh,
predictors[chan],
grad_pack_fn,
&mut out,
wp_params,
);
}
out
});
let mut out = Vec::with_capacity(gw * gh * nb_chans);
for channel in channel_tokens {
out.extend(channel);
}
out
}
#[derive(Default)]
struct GradientScratch {
cur: Vec<i32>,
prev: Vec<i32>,
buf: Vec<u32>,
}
thread_local! {
static GRADIENT_SCRATCH: RefCell<GradientScratch> =
RefCell::new(GradientScratch::default());
}
fn tokenize_plane(
ctx: u32,
get: impl Fn(usize, usize) -> i32,
gw: usize,
gh: usize,
pred_id: u32,
grad_pack_fn: GradPackInteriorFn,
out: &mut Vec<Token>,
) {
tokenize_plane_with_wp(
ctx,
get,
gw,
gh,
pred_id,
grad_pack_fn,
out,
WpParams::DEFAULT,
);
}
fn tokenize_plane_with_wp(
ctx: u32,
get: impl Fn(usize, usize) -> i32,
gw: usize,
gh: usize,
pred_id: u32,
grad_pack_fn: GradPackInteriorFn,
out: &mut Vec<Token>,
wp_params: WpParams,
) {
if pred_id == PREDICTOR_WEIGHTED {
let mut wp = WpState::with_params(gw, wp_params);
for gy in 0..gh {
for gx in 0..gw {
let v = get(gx, gy) as i64;
let w_ = if gx > 0 {
get(gx - 1, gy) as i64
} else if gy > 0 {
get(gx, gy - 1) as i64
} else {
0
};
let n_ = if gy > 0 { get(gx, gy - 1) as i64 } else { w_ };
let nw_ = if gx > 0 && gy > 0 {
get(gx - 1, gy - 1) as i64
} else {
w_
};
let ne_ = if gx + 1 < gw && gy > 0 {
get(gx + 1, gy - 1) as i64
} else {
n_
};
let nn_ = if gy > 1 { get(gx, gy - 2) as i64 } else { n_ };
let p = wp.predict(gx, gy, n_, w_, ne_, nw_, nn_);
wp.update(v, gx, gy);
out.push(Token::new(ctx, pack_signed((v - p) as i32)));
}
}
} else if pred_id == PREDICTOR_GRADIENT {
GRADIENT_SCRATCH.with_borrow_mut(|scratch| {
if scratch.buf.len() < gw {
scratch.buf.resize(gw, 0);
}
if scratch.cur.len() < gw {
scratch.cur.resize(gw, 0);
}
if scratch.prev.len() < gw {
scratch.prev.resize(gw, 0);
}
let mut cur = &mut scratch.cur[..gw];
let mut prev = &mut scratch.prev[..gw];
let buf = &mut scratch.buf[..gw];
for gy in 0..gh {
std::mem::swap(&mut cur, &mut prev); for (gx, c) in cur.iter_mut().enumerate() {
*c = get(gx, gy);
}
if gy == 0 {
buf[0] = pack_signed(cur[0]); for gx in 1..gw {
buf[gx] = pack_signed(cur[gx].wrapping_sub(cur[gx - 1]));
}
} else {
buf[0] = pack_signed(cur[0].wrapping_sub(prev[0])); grad_pack_fn(cur, prev, buf, gw); }
for &b in buf.iter().take(gw) {
out.push(Token::new(ctx, b));
}
}
});
} else {
debug_assert!(matches!(
pred_id,
PREDICTOR_AVERAGE4 | PREDICTOR_SELECT | PREDICTOR_LEFT | PREDICTOR_TOP
));
for gy in 0..gh {
for gx in 0..gw {
let value = get(gx, gy) as i64;
let neighbors = predictor_neighbors(&get, gx, gy, gw);
let pred = predictor_value(pred_id, neighbors, 0);
out.push(Token::new(ctx, pack_signed((value - pred) as i32)));
}
}
}
}
type GradPackInteriorFn = fn(&[i32], &[i32], &mut [u32], usize);
fn select_grad_pack_interior_fn() -> GradPackInteriorFn {
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if is_x86_feature_detected!("avx2") {
return |c, p, o, g| unsafe { crate::avx::grad_pack_interior(c, p, o, g) };
}
#[cfg(all(any(target_arch = "x86_64", target_arch = "x86"), feature = "sse"))]
if is_x86_feature_detected!("sse4.1") {
return |c, p, o, g| unsafe { crate::sse::grad_pack_interior(c, p, o, g) };
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
{
|c, p, o, g| unsafe { crate::neon::grad_pack_interior(c, p, o, g) }
}
#[cfg(all(target_arch = "wasm32", target_feature = "simd128", feature = "wasm"))]
{
crate::wasm::grad_pack_interior
}
#[cfg(not(any(
all(target_arch = "aarch64", feature = "neon"),
all(target_arch = "wasm32", target_feature = "simd128", feature = "wasm")
)))]
{
grad_pack_interior_scalar
}
}
static GRAD_PACK_INTERIOR_FN: OnceLock<GradPackInteriorFn> = OnceLock::new();
#[inline]
fn selected_grad_pack_interior_fn() -> GradPackInteriorFn {
*GRAD_PACK_INTERIOR_FN.get_or_init(select_grad_pack_interior_fn)
}
#[allow(unused)]
fn grad_pack_interior_scalar(cur: &[i32], prev: &[i32], out: &mut [u32], gw: usize) {
for gx in 1..gw {
let w = cur[gx - 1];
let n = prev[gx];
let nw = prev[gx - 1];
let ac = w.wrapping_sub(nw);
let bc = n.wrapping_sub(nw);
let grad = ac.wrapping_add(n);
let clamp = if (w.wrapping_sub(n) ^ bc) < 0 { n } else { w };
let pred = if (ac ^ bc) < 0 { grad } else { clamp };
out[gx] = pack_signed(cur[gx].wrapping_sub(pred));
}
}
#[derive(Default)]
struct PredictorCosts {
histograms: [Vec<u64>; SLOW_PREDICTORS.len()],
total: u64,
}
impl PredictorCosts {
#[inline]
fn add(&mut self, value: i64, neighbors: PredictorNeighbors, weighted: i64) {
for (candidate, &pred_id) in SLOW_PREDICTORS.iter().enumerate() {
let pred = predictor_value(pred_id, neighbors, weighted);
let symbol = pack_signed((value - pred) as i32) as usize;
let hist = &mut self.histograms[candidate];
if hist.len() <= symbol {
hist.resize(symbol + 1, 0);
}
hist[symbol] += 1;
}
self.total += 1;
}
fn best_predictor(&self) -> u32 {
let mut best_id = SLOW_PREDICTORS[0];
let mut best_bits = entropy_of_hist(&self.histograms[0], self.total);
for (candidate, &pred_id) in SLOW_PREDICTORS.iter().enumerate().skip(1) {
let bits = entropy_of_hist(&self.histograms[candidate], self.total);
if bits < best_bits {
best_bits = bits;
best_id = pred_id;
}
}
best_id
}
}
fn choose_predictor_for_plane(get: impl Fn(usize, usize) -> i32, w: usize, h: usize) -> u32 {
choose_predictor_for_plane_with_wp(get, w, h, WpParams::DEFAULT)
}
fn choose_predictor_for_plane_with_wp(
get: impl Fn(usize, usize) -> i32,
w: usize,
h: usize,
wp_params: WpParams,
) -> u32 {
if w == 0 || h == 0 {
return PREDICTOR_WEIGHTED;
}
let mut wp = WpState::with_params(w, wp_params);
let mut costs = PredictorCosts::default();
for gy in 0..h {
for gx in 0..w {
let value = get(gx, gy) as i64;
let neighbors = predictor_neighbors(&get, gx, gy, w);
let weighted = wp.predict(
gx,
gy,
neighbors.top,
neighbors.left,
neighbors.top_right,
neighbors.top_left,
neighbors.top_top,
);
costs.add(value, neighbors, weighted);
wp.update(value, gx, gy);
}
}
costs.best_predictor()
}
fn choose_predictors_with_wp(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
num_threads: usize,
wp_params: WpParams,
) -> [u32; 4] {
let mut preds = [PREDICTOR_WEIGHTED; 4];
let num_channels = 3 + usize::from(alpha.is_some());
let selected = crate::thread_pool::steal_map(num_channels, num_threads, |chan| {
if chan < 3 {
let pd = linear.plane_data(chan);
choose_predictor_for_plane_with_wp(|x, y| pd[y * xsize + x], xsize, ysize, wp_params)
} else {
let a = alpha.expect("alpha channel must exist");
choose_predictor_for_plane_with_wp(
|x, y| a.get_i32(y * xsize + x),
xsize,
ysize,
wp_params,
)
}
});
preds[..num_channels].copy_from_slice(&selected);
if alpha.is_none() {
preds[3] = PREDICTOR_WEIGHTED;
}
preds
}
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"),
}
}
#[inline]
fn clamped_gradient(w: i64, n: i64, nw: i64) -> i64 {
let lo = w.min(n);
let hi = w.max(n);
(w + n - nw).clamp(lo, hi)
}
thread_local! {
static ORDER0_ENTROPY_SCRATCH: RefCell<Vec<u64>> = const { RefCell::new(vec![]) };
}
fn order0_entropy(vals: &[u32]) -> f32 {
if vals.is_empty() {
return 0.0;
}
ORDER0_ENTROPY_SCRATCH.with_borrow_mut(|cell| {
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;
}
let total = vals.len() as f32;
let mut bits = 0.0;
for &c in hist.iter() {
if c != 0 {
let p = c as f32 / total;
bits -= c as f32 * dirty_log2f(p);
}
}
bits
})
}
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<u32> = Vec::with_capacity(gw * gh);
let mut prp = Vec::with_capacity(gw * gh);
for gy in 0..gh {
for gx in 0..gw {
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.push(wp.wp_prop);
let pred = predictor_value(pred_id, neighbors, wp_pred);
res.push(pack_signed((v - pred) as i32));
wp.update(v, gx, gy);
}
}
(res, prp)
}
fn entropy_of_hist(hist: &[u64], total: u64) -> f32 {
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 * p.log2();
}
}
bits
}
struct PickThresholdScratch {
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])
}
}
thread_local! {
static THRESHOLD_SCRATCH: RefCell<PickThresholdScratch> = const { RefCell::new(PickThresholdScratch {
hist_scratch: Vec::new(),
}) }
}
fn pick_threshold(res: &[u32], prp: &[i64]) -> (i32, f32, f32) {
THRESHOLD_SCRATCH.with_borrow_mut(|cell| {
let flat = order0_entropy(res);
let max = res.iter().copied().max().unwrap_or(0) as usize;
let (h0, h1, h2) = cell.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 try_encode_context_tree_single_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
predictors: &[u32],
min_symbol: u32,
num_threads: usize,
wp_params: WpParams,
writer: &mut BitWriter,
) -> bool {
let nb_chans = 3 + if alpha.is_some() { 1 } else { 0 };
let collected = crate::thread_pool::steal_map(nb_chans, num_threads, |chan| {
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 = crate::thread_pool::steal_map(nb_chans, num_threads, |chan| {
pick_threshold(&chan_res[chan], &chan_prp[chan])
});
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 = crate::thread_pool::steal_map(nb_chans, num_threads, |chan| {
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(), 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, &mut section);
let distance_ctx = num_pixel_ctx as u32;
let lz_tokens = lz77_compress_runs(&tokens, distance_ctx);
let code = build_lz_pixel_code(&lz_tokens, num_pixel_ctx, min_symbol, true);
write_tree_lz77(&tree_tokens, &code, min_symbol, &mut section);
for t in &lz_tokens {
write_lz_token(*t, &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(§ion);
writer.zero_pad_to_byte();
true
}
fn try_encode_context_tree_multi_group(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
predictors: &[u32],
xsize_groups: usize,
ysize_groups: usize,
num_dc_groups: usize,
min_symbol: u32,
num_threads: usize,
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>)>> =
crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
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);
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 = crate::thread_pool::steal_map(nb_chans, num_threads, |chan| {
let mut res: Vec<u32> = Vec::new();
let mut prp: Vec<i64> = Vec::new();
for g in &groups {
res.extend_from_slice(&g[chan].0);
prp.extend_from_slice(&g[chan].1);
}
pick_threshold(&res, &prp)
});
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>> =
crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
let g = &groups[group_index];
let mut toks: Vec<Token> = Vec::new();
for chan in 0..nb_chans {
let (res, prp) = &g[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];
toks.push(Token::new(ctx, res));
}
}
lz77_compress_runs(&toks, distance_ctx)
});
let mut all_lz: Vec<LzToken> = Vec::new();
for lz in &group_lz_tokens {
all_lz.extend_from_slice(lz);
}
let code = build_lz_pixel_code(&all_lz, num_pixel_ctx, min_symbol, true);
write_frame_header_modular(alpha.is_some(), 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 sections[0]);
sections[0].write(1, 1); write_wp_header(wp_params, &mut sections[0]);
write_modular_transforms(nb_chans, &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();
for group_index in 0..num_ac_groups {
let section_idx = 2 + num_dc_groups + group_index;
sections[section_idx].write(1, 1);
write_wp_header(wp_params, &mut sections[section_idx]);
sections[section_idx].write(2, 0);
for t in &group_lz_tokens[group_index] {
write_lz_token(*t, &code, min_symbol, &mut sections[section_idx]);
}
sections[section_idx].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();
for s in §ions {
writer.append(s);
writer.zero_pad_to_byte();
}
true
}
use crate::adaptive_quant::dirty_log2f;
use crate::bit_writer::BitWriter;
use crate::encode_image::AlphaPlane;
use crate::entropy::{
OwnedEntropyCode, Token, optimize_entropy_code, pack_signed, write_entropy_code, write_token,
};
use crate::image::Image3Si;
use crate::patches::{
ModularFrameKind, NUM_PATCH_CONTEXTS, PATCH_REF_ID, PATCH_TILE, PatchReference,
find_lossless_patches,
};
use std::cell::RefCell;
use std::sync::OnceLock;
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) {
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, 0));
out.push(Token::new(TREE_CTX_MULTIPLIER_BITS, 0));
}
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,
w: &mut BitWriter,
) {
let tree_code = optimize_entropy_code(tree_tokens, NUM_TREE_CONTEXTS);
let tree_code_ref = tree_code.as_ref();
w.write(1, 0); write_entropy_code(&tree_code_ref, w);
for tok in tree_tokens {
write_token(*tok, &tree_code_ref, w);
}
w.write(1, 0);
write_entropy_code(&pixel_code.as_ref(), w);
}
pub(crate) fn encode_frame_lossless_float(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
num_threads: usize,
writer: &mut BitWriter,
) {
let _scratch_guard = LosslessScratchGuard;
let num_threads = num_threads.max(1);
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(), 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,
num_threads,
);
let code = optimize_entropy_code(&tokens, nb_chans);
write_tree_and_pixel_code_nolz(&tree_tokens, &code, &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(§ion);
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>> =
crate::thread_pool::steal_map(num_ac_groups, num_threads, |group_index| {
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,
1,
)
});
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);
sections[0].write(1, 1); sections[0].write(1, 1); write_tree_and_pixel_code_nolz(&tree_tokens, &code, &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 i in 0..num_dc_groups {
sections[1 + i].write(1, 1);
sections[1 + i].write(1, 1);
sections[1 + i].write(2, 0);
sections[1 + i].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 group_index in 0..num_ac_groups {
let section_idx = 2 + num_dc_groups + group_index;
sections[section_idx].write(1, 1);
sections[section_idx].write(1, 1);
sections[section_idx].write(2, 0);
for t in &group_tokens[group_index] {
write_token(*t, &code.as_ref(), &mut sections[section_idx]);
}
sections[section_idx].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();
for s in §ions {
writer.append(s);
writer.zero_pad_to_byte();
}
}
}
#[cfg(test)]
mod predictor_tests {
use super::*;
#[test]
fn added_predictors_match_jxl_formulas() {
let n = PredictorNeighbors {
left: 11,
top: 7,
top_left: 5,
top_right: 13,
left_left: 3,
top_top: 2,
top_right_right: 17,
};
assert_eq!(predictor_value(PREDICTOR_LEFT, n, 99), 11);
assert_eq!(predictor_value(PREDICTOR_TOP, n, 99), 7);
assert_eq!(predictor_value(PREDICTOR_SELECT, n, 99), 11);
assert_eq!(predictor_value(PREDICTOR_AVERAGE4, n, 99), 11);
let tie = PredictorNeighbors {
left: 9,
top: 3,
top_left: 6,
..n
};
assert_eq!(predictor_value(PREDICTOR_SELECT, tie, 99), 3);
}
#[test]
fn slow_search_selects_directional_predictors() {
const W: usize = 64;
const H: usize = 64;
let mut horizontal = vec![0i32; W * H];
for y in 0..H {
horizontal[y * W] = ((y * 73) & 255) as i32;
for x in 1..W {
let delta = (((x * 17 + y * 31) ^ (x * y * 3)) % 7) as i32 - 3;
horizontal[y * W + x] = horizontal[y * W + x - 1] + delta;
}
}
let mut vertical = vec![0i32; W * H];
for x in 0..W {
vertical[x] = ((x * 73) & 255) as i32;
for y in 1..H {
let delta = (((y * 17 + x * 31) ^ (x * y * 3)) % 7) as i32 - 3;
vertical[y * W + x] = vertical[(y - 1) * W + x] + delta;
}
}
assert_eq!(
choose_predictor_for_plane(|x, y| horizontal[y * W + x], W, H),
PREDICTOR_SELECT
);
assert_eq!(
choose_predictor_for_plane(|x, y| vertical[y * W + x], W, H),
PREDICTOR_SELECT
);
}
#[test]
fn slow_search_selects_average4_for_its_recurrence() {
const W: usize = 64;
const H: usize = 64;
let mut plane = vec![0i32; W * H];
for y in 0..H {
for x in 0..W {
let i = y * W + x;
if y < 2 || x < 2 {
plane[i] = (((x * 97 + y * 53) ^ (x * y * 11)) & 1023) as i32 - 512;
continue;
}
let top_right = if x + 1 < W {
plane[(y - 1) * W + x + 1]
} else {
plane[(y - 1) * W + x]
};
let top_right_right = if x + 2 < W {
plane[(y - 1) * W + x + 2]
} else {
top_right
};
plane[i] = (6 * plane[(y - 1) * W + x] - 2 * plane[(y - 2) * W + x]
+ 7 * plane[i - 1]
+ plane[i - 2]
+ top_right_right
+ 3 * top_right
+ 8)
/ 16;
}
}
assert_eq!(
choose_predictor_for_plane(|x, y| plane[y * W + x], W, H),
PREDICTOR_AVERAGE4
);
}
#[test]
fn wp_headers_have_expected_sizes() {
let mut default = BitWriter::new();
write_wp_header(WpParams::DEFAULT, &mut default);
assert_eq!(default.bits_written(), 1);
for ¶ms in &WpParams::PRESETS[1..] {
let mut custom = BitWriter::new();
write_wp_header(params, &mut custom);
assert_eq!(custom.bits_written(), 52);
}
}
#[test]
fn directional_wp_presets_are_distinct() {
const W: usize = 128;
const H: usize = 128;
let mut west = vec![0i32; W * H];
let mut north = vec![0i32; W * H];
for y in 0..H {
west[y * W] = ((y * 977) & 65535) as i32;
for x in 1..W {
west[y * W + x] = west[y * W + x - 1] + ((x * 13 + y * 7) % 5) as i32 - 2;
}
}
for x in 0..W {
north[x] = ((x * 977) & 65535) as i32;
for y in 1..H {
north[y * W + x] = north[(y - 1) * W + x] + ((y * 13 + x * 7) % 5) as i32 - 2;
}
}
let west_costs: Vec<_> = WpParams::PRESETS
.iter()
.map(|¶ms| wp_sample_cost(|x, y| west[y * W + x], W, H, params).0)
.collect();
let north_costs: Vec<_> = WpParams::PRESETS
.iter()
.map(|¶ms| wp_sample_cost(|x, y| north[y * W + x], W, H, params).0)
.collect();
assert_ne!(west_costs[2], west_costs[3]);
assert_ne!(north_costs[2], north_costs[3]);
}
}
#[cfg(test)]
mod lz_reach_probe {
#[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_eq!(
super::lossless_tls_scratch_capacity(),
0,
"lossless TLS allocations must be released after encoding"
);
}
}