mod global;
mod local;
pub(crate) type PaletteRowFn = fn(&[i32], &[i32], &mut [[i32; 4]]);
#[allow(unreachable_code)]
pub(crate) fn selected_palette_row_fn() -> PaletteRowFn {
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::arch::is_x86_feature_detected!("avx2") {
return |a, b, c| unsafe { crate::avx::palette_row_avx2(a, b, c) };
}
#[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), feature = "sse"))]
if std::arch::is_x86_feature_detected!("sse4.1") {
return |a, b, c| unsafe { crate::sse::palette_row_sse41(a, b, c) };
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
return |a, b, c| unsafe { crate::neon::palette_row_neon(a, b, c) };
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
return crate::wasm::palette_row_wasm;
palette_row_scalar
}
#[allow(dead_code)]
pub(crate) fn palette_row_scalar(above: &[i32], row: &[i32], out: &mut [[i32; 4]]) {
for (x, out) in out.iter_mut().enumerate() {
let (ll, l, v) = (row[x], row[x + 1], row[x + 2]);
let (tl, t, tr) = (above[x + 1], above[x + 2], above[x + 3]);
let sign = |v: i32| v.signum() + 1;
let ctx = sign(l - tl) * 27 + sign(t - tl) * 9 + sign(t - tr) * 3 + sign(l - ll);
let gradient =
((l as i64 + t as i64 - tl as i64).clamp(l.min(t) as i64, l.max(t) as i64)) as i32;
*out = [ctx, v - l, v - t, v - gradient];
}
}
#[cfg(test)]
mod tests;
pub(super) use global::{
GlobalPalette, OrderRace, PALETTE_COARSE_MARGIN, PALETTE_FINAL_MARGIN, build_global_palettes,
};
#[cfg(test)]
pub(super) use local::local_palette_coverage_is_sufficient;
pub(super) use local::{
LOCAL_PALETTE_MAX_COLORS, LocalPaletteGroup, build_local_palette_group_limited,
ordered_local_palette, try_encode_local_palette_multi_group,
};
use super::GroupLayout;
use super::header::{write_frame_header_modular_kind, write_toc_entry};
use super::lz77::{
RunLzWriter, build_lz_pixel_code, lz77_compress_for_speed, write_local_tree_lz77,
write_lz_section,
};
use super::predictor::{GradPackInteriorFn, choose_predictor_for_rows, fixed_predictor};
use super::rct::selected_rct_row_fn;
use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::encode_image::AlphaPlane;
use crate::image::Image3Si;
use crate::patches::ModularFrameKind;
use crate::shared_sort::SharedSort;
use global::ColorMap;
pub(crate) fn write_palette_transform(num_c: u32, nb_colors: u32, w: &mut BitWriter) {
w.write(2, 0b01);
write_palette_transform_entry(0, num_c, nb_colors, w);
}
pub(crate) fn write_palette_transform_entry(
begin_c: u32,
num_c: u32,
nb_colors: u32,
w: &mut BitWriter,
) {
debug_assert!((1..=4).contains(&num_c));
w.write(2, 0b01);
match begin_c {
0..8 => {
w.write(2, 0b00);
w.write(3, u64::from(begin_c));
}
8..72 => {
w.write(2, 0b01);
w.write(6, u64::from(begin_c - 8));
}
72..1096 => {
w.write(2, 0b10);
w.write(10, u64::from(begin_c - 72));
}
_ => {
w.write(2, 0b11);
w.write(13, u64::from(begin_c - 1096));
}
}
match num_c {
1 => w.write(2, 0b00),
3 => w.write(2, 0b01),
4 => w.write(2, 0b10),
_ => {
w.write(2, 0b11);
w.write(13, u64::from(num_c - 1));
}
}
if nb_colors <= 255 {
w.write(2, 0b00);
w.write(8, nb_colors as u64);
} else if nb_colors <= 256 + 1023 {
w.write(2, 0b01);
w.write(10, (nb_colors - 256) as u64);
} else if nb_colors <= 1280 + 4095 {
w.write(2, 0b10);
w.write(12, (nb_colors - 1280) as u64);
} else {
debug_assert!(nb_colors <= 5376 + 65535);
w.write(2, 0b11);
w.write(16, (nb_colors - 5376) as u64);
}
w.write(2, 0b00);
w.write(4, 0);
}
#[inline]
fn visit_palette_colors<const RGB: bool>(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
stride: usize,
x0: usize,
y0: usize,
w: usize,
h: usize,
mut visit: impl FnMut([i32; 4]) -> bool,
) -> bool {
if w == 0 || h == 0 {
return true;
}
const RGB_BLOCK: usize = 128;
let block = if RGB { RGB_BLOCK } else { w };
let inverse = RGB.then(selected_rct_row_fn);
let mut rgb = [[0; RGB_BLOCK]; 3];
let planes = [0, 1, 2].map(|c| linear.plane_data(c));
for y in y0..y0 + h {
for offset in (0..w).step_by(block) {
let start = y * stride + x0 + offset;
let len = (w - offset).min(block);
let range = start..start + len;
let src = planes.map(|p| &p[range.clone()]);
let [r, g, b] = if let Some(inverse) = inverse {
inverse(src, 0, rgb.each_mut().map(|p| &mut p[..len]));
rgb.each_ref().map(|p| &p[..len])
} else {
src
};
let mut colors = r.iter().zip(g).zip(b).map(|((&r, &g), &b)| [r, g, b, 0]);
let complete = match alpha {
None => colors.all(&mut visit),
Some(AlphaPlane::U8(data)) => colors.zip(&data[range]).all(|(mut c, &a)| {
c[3] = i32::from(a);
visit(c)
}),
Some(AlphaPlane::U16 { data, .. }) => {
colors.zip(&data[range]).all(|(mut c, &a)| {
c[3] = i32::from(a);
visit(c)
})
}
Some(AlphaPlane::F32(data)) => colors.zip(&data[range]).all(|(mut c, &a)| {
c[3] = a;
visit(c)
}),
};
if !complete {
return false;
}
}
}
true
}
fn visit_gray_colors(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
xsize: usize,
ysize: usize,
mut visit: impl FnMut([i32; 4]) -> bool,
) -> bool {
let plane = &linear.plane_data(0)[..xsize * ysize];
match alpha {
None => plane.iter().all(|&v| visit([v, v, v, 0])),
Some(AlphaPlane::U8(data)) => plane
.iter()
.zip(data)
.all(|(&v, &a)| visit([v, v, v, i32::from(a)])),
Some(AlphaPlane::U16 { data, .. }) => plane
.iter()
.zip(data)
.all(|(&v, &a)| visit([v, v, v, i32::from(a)])),
Some(AlphaPlane::F32(data)) => plane.iter().zip(data).all(|(&v, &a)| visit([v, v, v, a])),
}
}
pub(super) 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,
use_wp: bool,
frame_kind: ModularFrameKind<'_>,
layout: GroupLayout,
scratch: &mut CoderScratch,
writer: &mut BitWriter,
) -> bool {
let npx = xsize * ysize;
let num_c = 3 + usize::from(alpha.is_some());
let nb_chans = 2usize;
let distance_ctx = nb_chans as u32;
let (preds, mut section, lz_tokens) = {
let mut seen = ColorMap::<()>::with_capacity_and_hasher(
LOCAL_PALETTE_MAX_COLORS + 1,
Default::default(),
);
let mut previous = None;
if !visit_palette_colors::<true>(linear, alpha, xsize, 0, 0, xsize, ysize, |color| {
if previous != Some(color) {
seen.entry(color).or_insert(());
previous = Some(color);
}
seen.len() <= LOCAL_PALETTE_MAX_COLORS
}) {
return false;
}
let nb_colors = seen.len();
if nb_colors == 0 {
return false;
}
let mut colors: Vec<[i32; 4]> = seen.keys().copied().collect();
colors.shared_sort();
let mut idx_of = ColorMap::<i32>::with_capacity_and_hasher(nb_colors, Default::default());
for (i, c) in colors.iter().enumerate() {
idx_of.insert(*c, i as i32);
}
let mut palette_ch = vec![0i32; num_c * nb_colors];
for (c, row) in palette_ch.chunks_exact_mut(nb_colors).enumerate() {
for (value, color) in row.iter_mut().zip(&colors) {
*value = color[c];
}
}
let mut index_img = Vec::with_capacity(npx);
let mut previous = ([0; 4], -1);
visit_palette_colors::<true>(linear, alpha, xsize, 0, 0, xsize, ysize, |color| {
if previous.1 < 0 || previous.0 != color {
previous = (color, idx_of[&color]);
}
index_img.push(previous.1 as u16);
true
});
let palette = LocalPaletteGroup {
palette: palette_ch,
indices: index_img,
nb_colors,
w: xsize,
h: ysize,
};
let (palette, _, _) = local::race_local_palette_orders(
palette,
num_c,
min_symbol,
grad_pack_fn,
speed,
use_wp,
scratch,
);
let pget = |y: usize| &palette.palette[y * nb_colors..][..nb_colors];
let iget = |y: usize| &palette.indices[y * xsize..][..xsize];
let preds = if speed.effort().predictor_search {
[
choose_predictor_for_rows(pget, nb_colors, num_c, use_wp),
choose_predictor_for_rows(iget, xsize, ysize, use_wp),
]
} else {
[fixed_predictor(use_wp); 2]
};
write_frame_header_modular_kind(alpha.is_some(), frame_kind, layout, writer);
let mut section = BitWriter::new();
super::header::write_dc_quant(frame_kind, &mut section);
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 lz_tokens = if speed.effort().lz_deep {
let mut tokens = Vec::with_capacity(num_c * nb_colors + npx);
palette.tokenize(
nb_chans,
&preds,
grad_pack_fn,
&mut scratch.gradient,
&mut tokens,
);
lz77_compress_for_speed(&tokens, distance_ctx, speed, scratch)
} else {
let mut runs = RunLzWriter::with_capacity((num_c * nb_colors + npx).min(16 * 1024));
palette.tokenize(
nb_chans,
&preds,
grad_pack_fn,
&mut scratch.gradient,
&mut runs,
);
runs.finish()
};
(preds, section, lz_tokens)
};
let code = build_lz_pixel_code(
speed.effort().lz_exhaustive_entropy(),
std::iter::once(lz_tokens.as_slice()),
nb_chans,
min_symbol,
speed.effort().lz_refined_entropy,
&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
}
#[cfg(test)]
mod search_row_tests {
use super::*;
#[derive(Clone, Copy)]
struct Rows {
palette: PaletteRowFn,
}
fn backends() -> Vec<Rows> {
#[allow(unused_mut)]
let mut rows = vec![Rows {
palette: palette_row_scalar,
}];
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::arch::is_x86_feature_detected!("avx2") {
rows.push(Rows {
palette: |a, b, c| unsafe { crate::avx::palette_row_avx2(a, b, c) },
});
}
#[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), feature = "sse"))]
if std::arch::is_x86_feature_detected!("sse4.1") {
rows.push(Rows {
palette: |a, b, c| unsafe { crate::sse::palette_row_sse41(a, b, c) },
});
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
{
rows.push(Rows {
palette: |a, b, c| unsafe { crate::neon::palette_row_neon(a, b, c) },
});
}
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
{
rows.push(Rows {
palette: crate::wasm::palette_row_wasm,
});
}
rows.push(Rows {
palette: selected_palette_row_fn(),
});
rows
}
#[test]
fn palette_contexts_and_residuals_match_scalar() {
for len in 0..133 {
for pattern in 0..6 {
let row: Vec<i32> = (0..len + 3)
.map(|x| ((x * 79 + pattern * 17) % 1024) as i32)
.collect();
let above: Vec<i32> = (0..len + 3)
.map(|x| {
if pattern == 0 {
row[x]
} else {
((x * 13 + pattern * 327) % 1024) as i32
}
})
.collect();
let mut expected = vec![[0; 4]; len];
palette_row_scalar(&above, &row, &mut expected);
for backend in backends() {
let mut actual = vec![[0; 4]; len];
(backend.palette)(&above, &row, &mut actual);
assert_eq!(actual, expected, "len={len}, pattern={pattern}");
}
}
}
}
}