use super::super::GroupLayout;
use super::super::entropy::EntropyOfHistFn;
use super::super::ma_learning::{rank_bits, rank_coarse};
use super::super::ma_source::MA_LITE_SAMPLING;
use super::super::ma_source::{MaChannel, MaPixels, MaSource, MaTransform};
use super::super::rct::selected_rct_row_fn;
use super::{visit_gray_colors, visit_palette_colors};
use crate::coder_scratch::CoderScratch;
use crate::encode_image::AlphaPlane;
use crate::entropy::{pack_signed, uint_encode};
use crate::image::Image3Si;
use crate::thread_pool::ThreadPool;
use crate::weighted_predictor::WpParams;
const GLOBAL_PALETTE_MAX_COLORS: usize = 4096;
const _: () = assert!(GLOBAL_PALETTE_MAX_COLORS <= u16::MAX as usize + 1);
pub(in crate::lossless) const PALETTE_COARSE_MARGIN: f64 = 1.10;
pub(in crate::lossless) const PALETTE_FINAL_MARGIN: f64 = 1.03;
pub(in crate::lossless) struct GlobalPalette {
pub(super) palette: Vec<i32>,
pub(super) indices: Vec<u16>,
pub(super) nb_colors: usize,
pub(super) num_c: usize,
}
impl GlobalPalette {
pub(in crate::lossless) fn source(&self, xsize: usize, ysize: usize) -> MaSource<'_> {
let nb_colors = self.nb_colors;
MaSource {
channels: vec![
MaChannel {
w: nb_colors,
h: self.num_c,
meta: true,
pixels: MaPixels::I32(&self.palette),
constant: None,
},
MaChannel {
w: xsize,
h: ysize,
meta: false,
pixels: MaPixels::U16(&self.indices),
constant: None,
},
],
transform: MaTransform::Palette {
num_c: self.num_c as u32,
nb_colors: nb_colors as u32,
},
group_channels: Vec::new(),
}
}
}
fn luma_key(c: &[i32; 4]) -> i64 {
299 * c[0] as i64 + 587 * c[1] as i64 + 114 * c[2] as i64
}
fn palette_order_candidates(
colors: &[[i32; 4]],
cooc: &[u32],
chroma_orders: bool,
) -> (Vec<Vec<i32>>, usize) {
let mut orders = estimated_order_candidates(colors, cooc);
let estimated = orders.len();
if chroma_orders && colors.len() >= 3 {
let ycc: Vec<[i32; 3]> = colors
.iter()
.map(|c| {
let co = c[0] - c[2];
let t = c[2] + (co >> 1);
let cg = c[1] - t;
[t + (cg >> 1), co, cg]
})
.collect();
for key in [[1, 2, 0], [0, 1, 2]] {
let mut path: Vec<usize> = (0..colors.len()).collect();
path.sort_by_key(|&i| (colors[i][3], key.map(|k| ycc[i][k]), i));
orders.push(order_of_path(&path));
}
}
(orders, estimated)
}
fn estimated_order_candidates(colors: &[[i32; 4]], cooc: &[u32]) -> Vec<Vec<i32>> {
let n = colors.len();
let identity: Vec<i32> = (0..n as i32).collect();
let mut orders = vec![identity];
if n < 3 {
return orders;
}
let chain = cooccurrence_chain_path(n, cooc);
let tour = improve_chain_tour(n, cooc, chain.clone());
orders.push(order_of_path(&chain));
if tour != chain {
orders.push(order_of_path(&tour));
}
let comp = |c: &[i32; 4]| [c[0] as f32, c[1] as f32, c[2] as f32, c[3] as f32];
let mean = colors.iter().fold([0.0f32; 4], |mut m, c| {
for (m, v) in m.iter_mut().zip(comp(c)) {
*m += v / n as f32;
}
m
});
let mut cov = [[0.0f32; 4]; 4];
for c in colors {
let d: [f32; 4] = std::array::from_fn(|i| comp(c)[i] - mean[i]);
for (i, row) in cov.iter_mut().enumerate() {
for (j, cell) in row.iter_mut().enumerate() {
*cell += d[i] * d[j];
}
}
}
let mut axis = [0.5f32, 0.5, 0.5, 0.1];
for _ in 0..32 {
let mut next = [0.0f32; 4];
for (i, row) in cov.iter().enumerate() {
next[i] = row.iter().zip(axis).map(|(c, a)| c * a).sum();
}
let norm = next.iter().map(|v| v * v).sum::<f32>().sqrt();
if norm < 1e-9 {
break;
}
axis = next.map(|v| v / norm);
}
let projection: Vec<f32> = colors
.iter()
.map(|c| comp(c).iter().zip(axis).map(|(v, x)| v * x).sum())
.collect();
let mut by_axis: Vec<usize> = (0..n).collect();
by_axis.sort_by(|&a, &b| projection[a].total_cmp(&projection[b]).then(a.cmp(&b)));
let mut pca = vec![0i32; n];
for (index, &canonical) in by_axis.iter().enumerate() {
pca[canonical] = index as i32;
}
orders.push(pca);
let mut used = vec![false; n];
let mut chain = vec![0i32; n];
let mut current = 0usize; used[0] = true;
for index in 1..n {
let cur = colors[current];
let mut best = usize::MAX;
let mut best_d = i64::MAX;
for (k, (&u, color)) in used.iter().zip(colors).enumerate() {
if u {
continue;
}
let d: i64 = color
.iter()
.zip(cur)
.map(|(&v, c)| {
let d = (v - c) as i64;
d * d
})
.sum();
if d < best_d {
best_d = d;
best = k;
}
}
used[best] = true;
chain[best] = index as i32;
current = best;
}
orders.push(chain);
orders
}
pub(super) fn index_cooccurrence(
indices: &[u16],
xsize: usize,
ysize: usize,
n: usize,
) -> Vec<u32> {
let mut cooc = vec![0u32; n * n];
let mut bump = |a: u16, b: u16| {
if a != b {
cooc[a as usize * n + b as usize] += 1;
cooc[b as usize * n + a as usize] += 1;
}
};
for y in 0..ysize {
let row = &indices[y * xsize..(y + 1) * xsize];
for pair in row.array_windows::<2>() {
bump(pair[0], pair[1]);
}
if y > 0 {
let above = &indices[(y - 1) * xsize..y * xsize];
for (&a, &b) in above.iter().zip(row) {
bump(a, b);
}
}
}
cooc
}
pub(super) fn order_of_path(path: &[usize]) -> Vec<i32> {
let mut order = vec![0i32; path.len()];
for (index, &canonical) in path.iter().enumerate() {
order[canonical] = index as i32;
}
order
}
#[cfg(test)]
pub(super) fn cooccurrence_chain(n: usize, cooc: &[u32]) -> Vec<i32> {
order_of_path(&cooccurrence_chain_path(n, cooc))
}
pub(super) fn cooccurrence_chain_path(n: usize, cooc: &[u32]) -> Vec<usize> {
let total: Vec<u64> = (0..n)
.map(|i| cooc[i * n..(i + 1) * n].iter().map(|&v| v as u64).sum())
.collect();
let most_connected = |used: &[bool]| {
(0..n)
.filter(|&i| !used[i])
.max_by_key(|&i| (total[i], std::cmp::Reverse(i)))
.expect("an unused color remains")
};
let mut used = vec![false; n];
let start = most_connected(&used);
used[start] = true;
let mut chain = std::collections::VecDeque::with_capacity(n);
chain.push_back(start);
let (mut left, mut right) = (start, start);
let best_from = |end: usize, used: &[bool]| {
let row = &cooc[end * n..(end + 1) * n];
(0..n)
.filter(|&i| !used[i])
.map(|i| (row[i], i))
.max_by_key(|&(v, i)| (v, std::cmp::Reverse(i)))
.unwrap_or((0, usize::MAX))
};
for _ in 1..n {
let (lv, li) = best_from(left, &used);
let (rv, ri) = best_from(right, &used);
if lv >= rv && lv > 0 {
chain.push_front(li);
used[li] = true;
left = li;
} else if rv > 0 {
chain.push_back(ri);
used[ri] = true;
right = ri;
} else {
let next = most_connected(&used);
chain.push_back(next);
used[next] = true;
right = next;
}
}
chain.into()
}
#[cfg(test)]
pub(super) fn path_cooccurrence(n: usize, cooc: &[u32], path: &[usize]) -> u64 {
path.array_windows::<2>()
.map(|&[a, b]| cooc[a * n + b] as u64)
.sum()
}
pub(super) fn improve_chain_tour(n: usize, cooc: &[u32], mut path: Vec<usize>) -> Vec<usize> {
const TOUR_OR_OPT_SEGMENT: usize = 8;
const TOUR_MAX_ROUNDS: usize = 16;
if n < 3 {
return path;
}
let mut offsets = vec![0usize; n + 1];
let mut neighbors = Vec::new();
for a in 0..n {
neighbors.extend((0..n).filter(|&b| cooc[a * n + b] != 0));
offsets[a + 1] = neighbors.len();
}
let neighbors = |c: usize| &neighbors[offsets[c]..offsets[c + 1]];
let w = |a: usize, b: usize| cooc[a * n + b] as i64;
let mut pos = vec![0usize; n];
for (k, &c) in path.iter().enumerate() {
pos[c] = k;
}
let link = |path: &[usize], a: Option<usize>, b: Option<usize>| match (a, b) {
(Some(a), Some(b)) if a < n && b < n => w(path[a], path[b]),
_ => 0,
};
let mut candidates: Vec<usize> = Vec::new();
for _ in 0..TOUR_MAX_ROUNDS {
let mut improved = false;
for i in 0..n {
candidates.clear();
if i > 0 {
candidates.extend(
neighbors(path[i - 1])
.iter()
.map(|&c| pos[c])
.filter(|&j| j > i),
);
}
candidates.extend(
neighbors(path[i])
.iter()
.map(|&c| pos[c])
.filter(|&k| k > i + 1)
.map(|k| k - 1),
);
let mut best = (0i64, 0usize);
for &j in &candidates {
let before =
link(&path, i.checked_sub(1), Some(i)) + link(&path, Some(j), Some(j + 1));
let after =
link(&path, i.checked_sub(1), Some(j)) + link(&path, Some(i), Some(j + 1));
if after - before > best.0 {
best = (after - before, j);
}
}
if best.0 > 0 {
let j = best.1;
path[i..=j].reverse();
for (k, &c) in path.iter().enumerate().take(j + 1).skip(i) {
pos[c] = k;
}
improved = true;
}
}
for len in 1..=TOUR_OR_OPT_SEGMENT.min(n - 2) {
for i in 0..=n - len {
let end = i + len;
let (first, last) = (path[i], path[end - 1]);
let removed = link(&path, i.checked_sub(1), Some(i))
+ link(&path, Some(end - 1), Some(end))
- link(&path, i.checked_sub(1), Some(end));
let reduced = |k: usize| if k < i { k } else { k - len };
let left_of = |k: usize| -> Option<usize> {
let k = if k == 0 { n } else { k };
let k = if k == end { i } else { k };
k.checked_sub(1).map(|k| path[k])
};
let right_of = |k: usize| -> Option<usize> {
let k = if k == n { 0 } else { k + 1 };
let k = if k == i { end } else { k };
(k < n).then(|| path[k])
};
let value = |a: Option<usize>, b: Option<usize>| match (a, b) {
(Some(a), Some(b)) => w(a, b),
_ => 0,
};
let mut best = (0i64, 0usize, false);
let mut consider = |left: Option<usize>, right: Option<usize>, at: usize| {
for reversed in [false, true] {
let (head, tail) = if reversed {
(last, first)
} else {
(first, last)
};
let gain = value(left, Some(head)) + value(Some(tail), right)
- value(left, right)
- removed;
if gain > best.0 {
best = (gain, at, reversed);
}
}
};
consider(None, right_of(n), 0);
consider(left_of(0), None, n - len);
for &c in neighbors(first).iter().chain(neighbors(last)) {
let k = pos[c];
if (i..end).contains(&k) {
continue;
}
consider(Some(c), right_of(k), reduced(k) + 1);
consider(left_of(k), Some(c), reduced(k));
}
if best.0 > 0 {
let (_, at, reversed) = best;
let mut segment: Vec<usize> = path.drain(i..end).collect();
if reversed {
segment.reverse();
}
path.splice(at..at, segment);
for (k, &c) in path.iter().enumerate() {
pos[c] = k;
}
improved = true;
}
}
}
if !improved {
break;
}
}
path
}
const INDEX_COST_CONTEXTS: usize = 81;
const INDEX_COST_ALPHABET: usize = 64;
const INDEX_COST_PREDS: usize = 3;
pub(super) struct IndexCostHist {
pub(super) tokens: Vec<u64>,
pub(super) raw_bits: Vec<u64>,
pub(super) values: Vec<u64>,
pub(super) nb_colors: usize,
}
impl IndexCostHist {
pub(super) fn new(nb_colors: usize) -> Self {
Self {
tokens: vec![0; INDEX_COST_CONTEXTS * INDEX_COST_PREDS * INDEX_COST_ALPHABET],
raw_bits: vec![0; INDEX_COST_CONTEXTS * INDEX_COST_PREDS],
values: vec![0; INDEX_COST_CONTEXTS * nb_colors],
nb_colors,
}
}
pub(super) fn add(&mut self, other: &Self) {
for (a, b) in self.tokens.iter_mut().zip(&other.tokens) {
*a += b;
}
for (a, b) in self.raw_bits.iter_mut().zip(&other.raw_bits) {
*a += b;
}
for (a, b) in self.values.iter_mut().zip(&other.values) {
*a += b;
}
}
pub(super) fn cost(&self, entropy_of_hist: EntropyOfHistFn) -> f32 {
let mut cost = 0.0f32;
for ctx in 0..INDEX_COST_CONTEXTS {
let values = &self.values[ctx * self.nb_colors..][..self.nb_colors];
let mut best = entropy_of_hist(values, values.iter().sum());
for pred in 0..INDEX_COST_PREDS {
let slot = ctx * INDEX_COST_PREDS + pred;
let tokens = &self.tokens[slot * INDEX_COST_ALPHABET..][..INDEX_COST_ALPHABET];
let bits =
entropy_of_hist(tokens, tokens.iter().sum()) + self.raw_bits[slot] as f32;
best = best.min(bits);
}
cost += best;
}
cost
}
}
pub(super) fn estimate_index_plane_cost(
indices: &[u16],
xsize: usize,
ysize: usize,
order: &[i32],
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> f32 {
let entropy_of_hist = scratch.entropy_of_hist;
let nb_colors = order.len();
let threads = pool.num_threads().min(ysize.max(1));
let rows_per = ysize.div_ceil(threads).max(1);
let parts = pool.steal_map(scratch, ysize.div_ceil(rows_per), |part, _scratch| {
let y0 = part * rows_per;
index_cost_rows(
indices,
xsize,
y0,
(y0 + rows_per).min(ysize),
order,
nb_colors,
)
});
let mut hist = IndexCostHist::new(nb_colors);
for part in &parts {
hist.add(part);
}
hist.cost(entropy_of_hist)
}
pub(super) fn index_cost_rows(
indices: &[u16],
xsize: usize,
y_begin: usize,
y_end: usize,
order: &[i32],
nb_colors: usize,
) -> IndexCostHist {
let mut hist = IndexCostHist::new(nb_colors);
let remap = |y: usize, row: &mut [i32]| {
for (dst, &index) in row[2..2 + xsize]
.iter_mut()
.zip(&indices[y * xsize..][..xsize])
{
*dst = order[index as usize];
}
};
let mut above = vec![0i32; xsize + 3];
let mut row = vec![0i32; xsize + 3];
let mut samples = vec![[0; 4]; xsize];
let price_row = super::selected_palette_row_fn();
if y_begin > 0 {
remap(y_begin - 1, &mut above);
}
for y in y_begin..y_end {
remap(y, &mut row);
price_row(&above, &row, &mut samples);
for (&[ctx, left, top, gradient], &v) in samples.iter().zip(&row[2..2 + xsize]) {
let ctx = ctx as usize;
for (pred, residual) in [left, top, gradient].into_iter().enumerate() {
let slot = ctx * INDEX_COST_PREDS + pred;
let (tok, nb, _) = uint_encode(pack_signed(residual));
hist.tokens
[slot * INDEX_COST_ALPHABET + (tok as usize).min(INDEX_COST_ALPHABET - 1)] += 1;
hist.raw_bits[slot] += nb as u64;
}
hist.values[ctx * nb_colors + v as usize] += 1;
}
std::mem::swap(&mut above, &mut row);
}
hist
}
#[derive(Default)]
pub(super) struct ColorHasher(u64);
impl std::hash::Hasher for ColorHasher {
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
let bytes: &[u8; 16] = bytes.first_chunk::<16>().unwrap();
let chunks = bytes.as_chunks::<8>().0;
assert_eq!(chunks.len(), 2);
let a = u64::from_le_bytes(chunks[0]);
let b = u64::from_le_bytes(chunks[1]);
const MUL: u64 = 0x9E37_79B9_7F4A_7C15;
self.0 = (a.wrapping_mul(MUL).rotate_left(29) ^ b)
.wrapping_mul(MUL)
.rotate_left(29);
}
fn write_usize(&mut self, length: usize) {
debug_assert_eq!(length, 4);
}
}
pub(super) type ColorMap<V> =
std::collections::HashMap<[i32; 4], V, std::hash::BuildHasherDefault<ColorHasher>>;
#[cfg(test)]
pub(in crate::lossless) fn build_global_palette(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
num_color: usize,
xsize: usize,
ysize: usize,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<GlobalPalette> {
build_global_palettes(linear, alpha, num_color, xsize, ysize, None, pool, scratch)
.map(|(palette, _)| palette)
}
const ORDER_RACE_COARSE_LEAD: f64 = 0.995;
#[derive(Clone, Copy)]
pub(in crate::lossless) struct OrderRace {
pub(in crate::lossless) min_symbol: u32,
pub(in crate::lossless) use_wp: bool,
}
#[allow(clippy::too_many_arguments)]
pub(in crate::lossless) fn build_global_palettes(
linear: &Image3Si,
alpha: Option<&AlphaPlane>,
num_color: usize,
xsize: usize,
ysize: usize,
race: Option<OrderRace>,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<(GlobalPalette, Option<GlobalPalette>)> {
let gray = num_color == 1;
let num_c = num_color + usize::from(alpha.is_some());
let npx = xsize * ysize;
let (colors, canonical_of_id, mut indices) = {
let (first_seen, indices) = {
let mut seen: ColorMap<i32> = ColorMap::default();
seen.reserve(GLOBAL_PALETTE_MAX_COLORS + 1);
let mut first_seen: Vec<[i32; 4]> = Vec::with_capacity(GLOBAL_PALETTE_MAX_COLORS + 1);
let mut indices: Vec<u16> = Vec::with_capacity(npx);
let mut previous = ([0; 4], -1);
let visit = |color: [i32; 4]| {
if previous.1 < 0 || previous.0 != color {
let next = first_seen.len() as i32;
let id = *seen.entry(color).or_insert_with(|| {
first_seen.push(color);
next
});
if first_seen.len() > GLOBAL_PALETTE_MAX_COLORS {
return false;
}
previous = (color, id);
}
indices.push(previous.1 as u16);
true
};
let complete = if gray {
visit_gray_colors(linear, alpha, xsize, ysize, visit)
} else {
visit_palette_colors::<false>(linear, alpha, xsize, 0, 0, xsize, ysize, visit)
};
if !complete {
return None;
}
let nb_colors = first_seen.len();
if nb_colors == 0 {
return None;
}
let narrower = if num_c == 1 {
let (lo, hi) = first_seen.iter().fold((i32::MAX, i32::MIN), |(lo, hi), c| {
(lo.min(c[0]), hi.max(c[0]))
});
2 * nb_colors as i64 <= i64::from(hi) - i64::from(lo) + 1
} else {
npx + num_c * nb_colors < num_c * npx
};
if !narrower {
return None;
}
if !gray {
let inverse = selected_rct_row_fn();
const BLOCK: usize = 64;
let mut src = [[0; BLOCK]; 3];
let mut rgb = [[0; BLOCK]; 3];
for colors in first_seen.chunks_mut(BLOCK) {
let len = colors.len();
let [y, co, cg] = &mut src;
for (i, &[a, b, c, _]) in colors.iter().enumerate() {
(y[i], co[i], cg[i]) = (a, b, c);
}
inverse(
src.each_ref().map(|p| &p[..len]),
0,
rgb.each_mut().map(|p| &mut p[..len]),
);
let [r, g, b] = &rgb;
for (i, color) in colors.iter_mut().enumerate() {
color[..3].copy_from_slice(&[r[i], g[i], b[i]]);
}
}
}
(first_seen, indices)
};
let nb_colors = first_seen.len();
let mut canonical_ids: Vec<usize> = (0..nb_colors).collect();
canonical_ids.sort_unstable_by_key(|&id| {
let c = &first_seen[id];
(c[3], luma_key(c), c[0], c[1], c[2])
});
let colors: Vec<[i32; 4]> = canonical_ids.iter().map(|&id| first_seen[id]).collect();
let mut canonical_of_id = vec![0i32; nb_colors];
for (index, &id) in canonical_ids.iter().enumerate() {
canonical_of_id[id] = index as i32;
}
(colors, canonical_of_id, indices)
};
for v in indices.iter_mut() {
*v = canonical_of_id[*v as usize] as u16;
}
let nb_colors = colors.len();
let (orders, estimated) = {
let cooc = index_cooccurrence(&indices, xsize, ysize, nb_colors);
palette_order_candidates(&colors, &cooc, race.is_some() && !gray)
};
let mut best_order = 0usize;
let mut best_cost = f32::INFINITY;
for (k, order) in orders.iter().enumerate().take(estimated) {
if orders[..k].contains(order) {
continue;
}
let cost = estimate_index_plane_cost(&indices, xsize, ysize, order, pool, scratch);
if cost < best_cost {
best_cost = cost;
best_order = k;
}
}
let under = |order: &[i32]| {
let mut palette = vec![0i32; num_c * nb_colors];
for (canonical, color) in colors.iter().enumerate() {
let index = order[canonical] as usize;
for c in 0..num_c {
let component = if gray && c == 1 { 3 } else { c };
palette[c * nb_colors + index] = color[component];
}
}
GlobalPalette {
palette,
indices: indices.iter().map(|&v| order[v as usize] as u16).collect(),
nb_colors,
num_c,
}
};
let first = under(&orders[best_order]);
let Some(race) = race else {
return Some((first, None));
};
let mut coarse = |palette: &GlobalPalette| {
rank_coarse(
&palette.source(xsize, ysize),
xsize,
ysize,
race.min_symbol,
WpParams::DEFAULT,
race.use_wp,
GroupLayout::LARGE,
MA_LITE_SAMPLING,
pool,
scratch,
)
.map_or(f64::INFINITY, |stage| rank_bits(&stage))
};
let first_bits = coarse(&first);
let mut second: Option<(f64, GlobalPalette)> = None;
for (k, order) in orders.iter().enumerate() {
if k == best_order || orders[..k].contains(order) {
continue;
}
let palette = under(order);
let bits = coarse(&palette);
let to_beat = second
.as_ref()
.map_or(first_bits * ORDER_RACE_COARSE_LEAD, |(best, _)| *best);
if bits < to_beat {
second = Some((bits, palette));
}
}
Some((first, second.map(|(_, palette)| palette)))
}