use crate::build::{self, ImageKind};
pub const MAX_CODE_LENGTH: usize = 15;
pub const NUM_CODE_LENGTH_CODES: usize = 19;
pub const CODE_LENGTH_CODE_ORDER: [usize; NUM_CODE_LENGTH_CODES] = [
17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
];
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EncodeError {
PixelBufferMismatch {
got: usize,
expected: usize,
},
InvalidDimensions {
width: u32,
height: u32,
},
Build(build::BuildError),
}
impl From<build::BuildError> for EncodeError {
fn from(e: build::BuildError) -> Self {
Self::Build(e)
}
}
impl core::fmt::Display for EncodeError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Self::PixelBufferMismatch { got, expected } => write!(
f,
"VP8L encode: pixel buffer is {got} bytes, expected {expected} (width*height*4)"
),
Self::InvalidDimensions { width, height } => write!(
f,
"VP8L encode: invalid dimensions {width}x{height} (must be 1..=16384)"
),
Self::Build(e) => write!(f, "VP8L encode: RIFF/WEBP framing: {e}"),
}
}
}
impl std::error::Error for EncodeError {}
const MAX_DIMENSION: u32 = 1 << 14;
#[derive(Debug, Default, Clone)]
pub struct BitWriter {
bytes: Vec<u8>,
bit_pos: usize,
}
impl BitWriter {
pub fn new() -> Self {
Self::default()
}
pub fn bit_position(&self) -> usize {
self.bit_pos
}
pub fn write_bits(&mut self, value: u32, n: usize) {
debug_assert!(n <= 32, "write_bits supports up to 32 bits");
let mut value = value;
for _ in 0..n {
let byte_idx = self.bit_pos >> 3;
if byte_idx >= self.bytes.len() {
self.bytes.push(0);
}
let bit = (value & 1) as u8;
self.bytes[byte_idx] |= bit << (self.bit_pos & 7);
self.bit_pos += 1;
value >>= 1;
}
}
pub fn write_bit(&mut self, bit: bool) {
self.write_bits(bit as u32, 1);
}
pub fn into_bytes(self) -> Vec<u8> {
self.bytes
}
}
pub fn build_code_lengths(freqs: &[u32]) -> Vec<u8> {
let n = freqs.len();
let mut lengths = vec![0u8; n];
let used: Vec<usize> = (0..n).filter(|&s| freqs[s] > 0).collect();
match used.len() {
0 => return lengths, 1 => {
lengths[used[0]] = 1;
return lengths;
}
_ => {}
}
#[derive(Clone, Copy)]
struct HeapItem {
freq: u64,
node: usize,
order: u64,
}
let mut parent: Vec<isize> = vec![-1; n];
let mut node_freq: Vec<u64> = (0..n).map(|s| freqs[s] as u64).collect();
let mut heap: Vec<HeapItem> = Vec::with_capacity(used.len());
let mut order_counter: u64 = 0;
for &s in &used {
heap.push(HeapItem {
freq: freqs[s] as u64,
node: s,
order: order_counter,
});
order_counter += 1;
}
fn heap_less(a: &HeapItem, b: &HeapItem) -> bool {
(a.freq, a.order) < (b.freq, b.order)
}
fn sift_up(heap: &mut [HeapItem], mut i: usize) {
while i > 0 {
let p = (i - 1) / 2;
if heap_less(&heap[i], &heap[p]) {
heap.swap(i, p);
i = p;
} else {
break;
}
}
}
fn sift_down(heap: &mut [HeapItem], mut i: usize) {
let len = heap.len();
loop {
let l = 2 * i + 1;
let r = 2 * i + 2;
let mut smallest = i;
if l < len && heap_less(&heap[l], &heap[smallest]) {
smallest = l;
}
if r < len && heap_less(&heap[r], &heap[smallest]) {
smallest = r;
}
if smallest == i {
break;
}
heap.swap(i, smallest);
i = smallest;
}
}
fn heap_push(heap: &mut Vec<HeapItem>, item: HeapItem) {
heap.push(item);
let last = heap.len() - 1;
sift_up(heap, last);
}
fn heap_pop(heap: &mut Vec<HeapItem>) -> HeapItem {
let top = heap[0];
let last = heap.pop().unwrap();
if !heap.is_empty() {
heap[0] = last;
sift_down(heap, 0);
}
top
}
for i in (0..heap.len() / 2).rev() {
sift_down(&mut heap, i);
}
while heap.len() > 1 {
let a = heap_pop(&mut heap);
let b = heap_pop(&mut heap);
let new_node = node_freq.len();
node_freq.push(a.freq + b.freq);
parent.push(-1);
parent[a.node] = new_node as isize;
parent[b.node] = new_node as isize;
heap_push(
&mut heap,
HeapItem {
freq: a.freq + b.freq,
node: new_node,
order: order_counter,
},
);
order_counter += 1;
}
let mut max_len = 0usize;
for &s in &used {
let mut depth = 0usize;
let mut cur = s as isize;
while parent[cur as usize] != -1 {
cur = parent[cur as usize];
depth += 1;
}
lengths[s] = depth as u8;
max_len = max_len.max(depth);
}
if max_len > MAX_CODE_LENGTH {
limit_code_lengths(&mut lengths, &used);
}
lengths
}
fn limit_code_lengths(lengths: &mut [u8], used: &[usize]) {
for &s in used {
if lengths[s] as usize > MAX_CODE_LENGTH {
lengths[s] = MAX_CODE_LENGTH as u8;
}
}
let full: i64 = 1i64 << MAX_CODE_LENGTH;
let kraft = |lengths: &[u8]| -> i64 {
let mut k = 0i64;
for &s in used {
let l = lengths[s] as usize;
if l > 0 {
k += 1i64 << (MAX_CODE_LENGTH - l);
}
}
k
};
let mut k = kraft(lengths);
while k > full {
let mut target: Option<usize> = None;
let mut best_len = 0u8;
for &s in used {
let l = lengths[s];
if (l as usize) < MAX_CODE_LENGTH && l >= best_len {
best_len = l;
target = Some(s);
}
}
match target {
Some(s) => {
lengths[s] += 1;
k = kraft(lengths);
}
None => break,
}
}
while k < full {
let mut target: Option<usize> = None;
let mut best_len = 0u8;
for &s in used {
let l = lengths[s];
if l > 1 && l >= best_len {
best_len = l;
target = Some(s);
}
}
match target {
Some(s) => {
lengths[s] -= 1;
k = kraft(lengths);
}
None => break,
}
}
}
pub fn canonical_codes(lengths: &[u8]) -> Vec<u32> {
let mut bl_count = [0u32; MAX_CODE_LENGTH + 1];
for &l in lengths {
if l > 0 {
bl_count[l as usize] += 1;
}
}
let mut next_code = [0u32; MAX_CODE_LENGTH + 2];
let mut code = 0u32;
for len in 1..=MAX_CODE_LENGTH {
code = (code + bl_count[len - 1]) << 1;
next_code[len] = code;
}
let mut codes = vec![0u32; lengths.len()];
let mut assign = next_code;
#[allow(clippy::needless_range_loop)]
for len in 1..=MAX_CODE_LENGTH {
for (sym, &l) in lengths.iter().enumerate() {
if l as usize == len {
codes[sym] = assign[len];
assign[len] += 1;
}
}
}
codes
}
pub fn value_to_prefix(value: u32) -> (u32, u32, u32) {
debug_assert!(value >= 1, "LZ77 length/distance values are 1-based");
if value <= 4 {
return (value - 1, 0, 0);
}
let v0 = value - 1; let msb = 31 - v0.leading_zeros();
let extra_bits = msb - 1;
let parity = (v0 >> (msb - 1)) & 1;
let prefix_code = 2 * extra_bits + 2 + parity;
let offset = (2 + parity) << extra_bits;
let extra_value = value - offset - 1;
debug_assert!(extra_value < (1u32 << extra_bits));
(prefix_code, extra_bits, extra_value)
}
#[derive(Debug, Clone)]
struct WriteCode {
lengths: Vec<u8>,
codes: Vec<u32>,
single: Option<usize>,
}
impl WriteCode {
fn from_freqs(freqs: &[u32]) -> Self {
let used: Vec<usize> = (0..freqs.len()).filter(|&s| freqs[s] > 0).collect();
let single = if used.len() == 1 { Some(used[0]) } else { None };
let lengths = build_code_lengths(freqs);
let codes = canonical_codes(&lengths);
Self {
lengths,
codes,
single,
}
}
fn empty(alphabet_size: usize) -> Self {
let mut freqs = vec![0u32; alphabet_size];
freqs[0] = 1;
Self::from_freqs(&freqs)
}
fn write_symbol(&self, w: &mut BitWriter, symbol: usize) {
if self.single.is_some() {
return; }
let len = self.lengths[symbol] as usize;
let code = self.codes[symbol];
for i in 0..len {
let bit = (code >> (len - 1 - i)) & 1;
w.write_bits(bit, 1);
}
}
fn write_code_lengths(&self, w: &mut BitWriter) {
if let Some(simple) = self.as_simple_form() {
let simple_bits = simple_form_bits(&simple);
let normal_bits = normal_form_bits(&self.lengths);
if simple_bits <= normal_bits {
write_simple_code_lengths(w, &simple);
return;
}
}
write_normal_code_lengths(w, &self.lengths);
}
fn as_simple_form(&self) -> Option<Vec<usize>> {
let used: Vec<(usize, u8)> = self
.lengths
.iter()
.enumerate()
.filter_map(|(s, &l)| if l != 0 { Some((s, l)) } else { None })
.collect();
if used.is_empty() || used.len() > 2 {
return None;
}
if used.iter().any(|&(_, l)| l != 1) {
return None;
}
if used.iter().any(|&(s, _)| s > 255) {
return None;
}
Some(used.iter().map(|&(s, _)| s).collect())
}
}
fn simple_form_bits(symbols: &[usize]) -> usize {
debug_assert!(symbols.len() == 1 || symbols.len() == 2);
let is_first_8bits = symbols[0] > 1;
let s0_width = if is_first_8bits { 8 } else { 1 };
let s1_width = if symbols.len() == 2 { 8 } else { 0 };
3 + s0_width + s1_width
}
fn normal_form_bits(lengths: &[u8]) -> usize {
let mut clc_freq = [0u32; NUM_CODE_LENGTH_CODES];
for &l in lengths {
clc_freq[l as usize] += 1;
}
let clc_lengths = build_code_lengths(&clc_freq);
let mut max_order_used = 0usize;
for (order_idx, &pos) in CODE_LENGTH_CODE_ORDER.iter().enumerate() {
if clc_lengths[pos] != 0 {
max_order_used = order_idx;
}
}
let num_code_lengths = (max_order_used + 1).max(4);
let mut bits = 1 + 4 + 3 * num_code_lengths + 1;
let used_clc: Vec<usize> = (0..NUM_CODE_LENGTH_CODES)
.filter(|&s| clc_freq[s] > 0)
.collect();
if used_clc.len() > 1 {
for &l in lengths {
bits += clc_lengths[l as usize] as usize;
}
}
bits
}
fn write_simple_code_lengths(w: &mut BitWriter, symbols: &[usize]) {
debug_assert!(symbols.len() == 1 || symbols.len() == 2);
debug_assert!(symbols.iter().all(|&s| s <= 255));
w.write_bit(true);
w.write_bits((symbols.len() as u32) - 1, 1);
let is_first_8bits = symbols[0] > 1;
w.write_bits(if is_first_8bits { 1 } else { 0 }, 1);
let s0_width = if is_first_8bits { 8 } else { 1 };
w.write_bits(symbols[0] as u32, s0_width);
if symbols.len() == 2 {
w.write_bits(symbols[1] as u32, 8);
}
}
fn write_normal_code_lengths(w: &mut BitWriter, lengths: &[u8]) {
let mut clc_freq = [0u32; NUM_CODE_LENGTH_CODES];
for &l in lengths {
clc_freq[l as usize] += 1;
}
let clc_lengths = build_code_lengths(&clc_freq);
let clc_codes = canonical_codes(&clc_lengths);
let mut max_order_used = 0usize;
for (order_idx, &pos) in CODE_LENGTH_CODE_ORDER.iter().enumerate() {
if clc_lengths[pos] != 0 {
max_order_used = order_idx;
}
}
let num_code_lengths = (max_order_used + 1).max(4);
w.write_bit(false);
w.write_bits((num_code_lengths - 4) as u32, 4);
for &pos in CODE_LENGTH_CODE_ORDER.iter().take(num_code_lengths) {
w.write_bits(clc_lengths[pos] as u32, 3);
}
w.write_bit(false);
let clc_single = {
let used: Vec<usize> = (0..NUM_CODE_LENGTH_CODES)
.filter(|&s| clc_freq[s] > 0)
.collect();
if used.len() == 1 {
Some(used[0])
} else {
None
}
};
for &l in lengths {
let sym = l as usize;
if clc_single.is_some() {
continue; }
let code = clc_codes[sym];
let len = clc_lengths[sym] as usize;
for i in 0..len {
let bit = (code >> (len - 1 - i)) & 1;
w.write_bits(bit, 1);
}
}
}
pub const MIN_MATCH: usize = 3;
pub const MAX_MATCH: usize = 4096;
const HASH_BITS: usize = 14;
const MAX_CHAIN: usize = 64;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Token {
Literal(u32),
CacheRef {
index: u32,
},
Copy {
length: usize,
distance: usize,
},
}
struct Lz77Matcher<'a> {
pixels: &'a [u32],
head: Vec<i32>,
prev: Vec<i32>,
}
impl<'a> Lz77Matcher<'a> {
fn new(pixels: &'a [u32]) -> Self {
Self {
pixels,
head: vec![-1; 1 << HASH_BITS],
prev: vec![-1; pixels.len()],
}
}
fn hash(&self, pos: usize) -> usize {
let p = self.pixels;
let mut h = 0u32;
for k in 0..4 {
h = h.wrapping_mul(0x9e37_79b1).wrapping_add(p[pos + k]);
}
(h >> (32 - HASH_BITS)) as usize
}
fn insert(&mut self, pos: usize) {
if pos + 4 > self.pixels.len() {
return;
}
let h = self.hash(pos);
self.prev[pos] = self.head[h];
self.head[h] = pos as i32;
}
fn find(&self, pos: usize) -> Option<(usize, usize)> {
let p = self.pixels;
let n = p.len();
if pos + 4 > n {
return None;
}
let max_len = (n - pos).min(MAX_MATCH);
let h = self.hash(pos);
let mut cand = self.head[h];
let mut best_len = 0usize;
let mut best_dist = 0usize;
let mut steps = 0usize;
while cand >= 0 && steps < MAX_CHAIN {
let c = cand as usize;
let mut len = 0usize;
while len < max_len && p[c + len] == p[pos + len] {
len += 1;
}
if len > best_len {
best_len = len;
best_dist = pos - c;
if len >= max_len {
break;
}
}
cand = self.prev[c];
steps += 1;
}
if best_len >= MIN_MATCH {
Some((best_len, best_dist))
} else {
None
}
}
}
fn tokenize_lz77(pixels: &[u32]) -> Vec<Token> {
tokenize_lz77_inner(pixels, LAZY_DEPTH_DEFAULT)
}
const LAZY_DEPTH_DEFAULT: u32 = 4;
const DEPTH4_GUARD_THRESHOLD: u32 = 6;
fn tokenize_lz77_inner(pixels: &[u32], lazy_depth: u32) -> Vec<Token> {
let n = pixels.len();
let mut matcher = Lz77Matcher::new(pixels);
let mut tokens = Vec::new();
let mut pos = 0usize;
let depth = lazy_depth.min(4);
while pos < n {
if let Some((len_a, dist_a)) = matcher.find(pos) {
let mut best_len = len_a;
let mut best_dist = dist_a;
let mut best_start = pos; let inserted_pos = depth >= 1 && len_a < MAX_MATCH && pos + 1 < n;
if inserted_pos {
matcher.insert(pos);
if let Some((len_b, dist_b)) = matcher.find(pos + 1) {
if len_b > best_len {
best_len = len_b;
best_dist = dist_b;
best_start = pos + 1;
}
}
}
let inserted_pos1 = depth >= 2 && best_len < MAX_MATCH && pos + 2 < n;
if inserted_pos1 {
matcher.insert(pos + 1);
if let Some((len_c, dist_c)) = matcher.find(pos + 2) {
if len_c > best_len {
best_len = len_c;
best_dist = dist_c;
best_start = pos + 2;
}
}
}
let inserted_pos2 = depth >= 3 && best_len < MAX_MATCH && pos + 3 < n;
if inserted_pos2 {
matcher.insert(pos + 2);
if let Some((len_d, dist_d)) = matcher.find(pos + 3) {
if len_d > best_len {
best_len = len_d;
best_dist = dist_d;
best_start = pos + 3;
}
}
}
let inserted_pos3 = depth >= 4
&& best_len > MIN_MATCH
&& best_len < MAX_MATCH
&& (best_len as u32) < DEPTH4_GUARD_THRESHOLD
&& pos + 4 < n;
if inserted_pos3 {
matcher.insert(pos + 3);
if let Some((len_e, dist_e)) = matcher.find(pos + 4) {
if len_e > best_len {
best_len = len_e;
best_dist = dist_e;
best_start = pos + 4;
}
}
}
for &skipped in &pixels[pos..best_start] {
tokens.push(Token::Literal(skipped));
}
tokens.push(Token::Copy {
length: best_len,
distance: best_dist,
});
let end = best_start + best_len;
let mut q = pos;
while q < end {
let already_in = (q == pos && inserted_pos)
|| (q == pos + 1 && inserted_pos1)
|| (q == pos + 2 && inserted_pos2)
|| (q == pos + 3 && inserted_pos3);
if q >= best_start && !already_in {
matcher.insert(q);
}
q += 1;
}
pos = end;
} else {
tokens.push(Token::Literal(pixels[pos]));
matcher.insert(pos);
pos += 1;
}
}
tokens
}
pub const COLOR_CACHE_BITS_MIN: u32 = 1;
pub const COLOR_CACHE_BITS_MAX: u32 = 11;
pub const DEFAULT_COLOR_CACHE_BITS: u32 = 8;
#[derive(Debug, Clone)]
struct EncoderColorCache {
code_bits: u32,
entries: Vec<u32>,
}
impl EncoderColorCache {
fn new(code_bits: u32) -> Self {
debug_assert!((COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).contains(&code_bits));
Self {
code_bits,
entries: vec![0u32; 1usize << code_bits],
}
}
#[cfg(test)]
fn size(&self) -> usize {
self.entries.len()
}
fn hash(&self, argb: u32) -> usize {
(crate::vp8l_decode::COLOR_CACHE_HASH_MULTIPLIER.wrapping_mul(argb)
>> (32 - self.code_bits)) as usize
}
fn contains(&self, argb: u32) -> Option<usize> {
let idx = self.hash(argb);
if self.entries[idx] == argb {
Some(idx)
} else {
None
}
}
fn insert(&mut self, argb: u32) {
let idx = self.hash(argb);
self.entries[idx] = argb;
}
}
fn cacheify_tokens(tokens: &[Token], pixels: &[u32], code_bits: u32) -> Vec<Token> {
let mut cache = EncoderColorCache::new(code_bits);
let mut out = Vec::with_capacity(tokens.len());
let mut pos = 0usize;
for &tok in tokens {
match tok {
Token::Literal(argb) => {
if let Some(idx) = cache.contains(argb) {
out.push(Token::CacheRef { index: idx as u32 });
} else {
out.push(Token::Literal(argb));
}
cache.insert(argb);
pos += 1;
}
Token::CacheRef { .. } => {
out.push(tok);
pos += 1;
}
Token::Copy { length, distance } => {
out.push(tok);
let src_start = pos - distance;
for i in 0..length {
let argb = pixels[src_start + i];
cache.insert(argb);
}
pos += length;
}
}
}
debug_assert_eq!(
pos,
pixels.len(),
"cacheify_tokens: token stream covered {pos} of {} pixels",
pixels.len()
);
out
}
struct Frequencies {
green: Vec<u32>,
red: Vec<u32>,
blue: Vec<u32>,
alpha: Vec<u32>,
distance: Vec<u32>,
}
#[cfg(test)]
fn distance_to_code(distance: usize) -> u32 {
distance as u32 + crate::vp8l_decode::NUM_DISTANCE_MAP_CODES as u32
}
pub fn pixel_distance_to_distance_code(distance: usize, image_width: u32) -> u32 {
debug_assert!(distance >= 1, "§5.2.2 distance must be >= 1");
let scan_line_code = distance as u32 + crate::vp8l_decode::NUM_DISTANCE_MAP_CODES as u32;
let mut best = scan_line_code;
let width_i32 = image_width as i32;
for (idx, &(xi, yi)) in crate::vp8l_decode::DISTANCE_MAP.iter().enumerate() {
let raw = xi + yi * width_i32;
let mapped = if raw < 1 { 1 } else { raw as usize };
if mapped == distance {
let candidate = (idx + 1) as u32;
if candidate < best {
best = candidate;
}
}
}
best
}
fn count_frequencies(tokens: &[Token], color_cache_size: usize, image_width: u32) -> Frequencies {
let green_alphabet = 256 + crate::vp8l_decode::NUM_LENGTH_PREFIX_CODES + color_cache_size;
let mut freqs = Frequencies {
green: vec![0u32; green_alphabet],
red: vec![0u32; 256],
blue: vec![0u32; 256],
alpha: vec![0u32; 256],
distance: vec![0u32; 40],
};
for &tok in tokens {
match tok {
Token::Literal(p) => {
let a = ((p >> 24) & 0xff) as usize;
let r = ((p >> 16) & 0xff) as usize;
let g = ((p >> 8) & 0xff) as usize;
let b = (p & 0xff) as usize;
freqs.green[g] += 1;
freqs.red[r] += 1;
freqs.blue[b] += 1;
freqs.alpha[a] += 1;
}
Token::CacheRef { index } => {
let sym = 256 + crate::vp8l_decode::NUM_LENGTH_PREFIX_CODES + index as usize;
debug_assert!(sym < green_alphabet);
freqs.green[sym] += 1;
}
Token::Copy { length, distance } => {
let (len_prefix, _, _) = value_to_prefix(length as u32);
freqs.green[256 + len_prefix as usize] += 1;
let raw_code = pixel_distance_to_distance_code(distance, image_width);
let (dist_prefix, _, _) = value_to_prefix(raw_code);
freqs.distance[dist_prefix as usize] += 1;
}
}
}
freqs
}
fn write_lz77_value(w: &mut BitWriter, code: &WriteCode, symbol_base: usize, value: u32) {
let (prefix, extra_bits, extra_value) = value_to_prefix(value);
code.write_symbol(w, symbol_base + prefix as usize);
if extra_bits > 0 {
w.write_bits(extra_value, extra_bits as usize);
}
}
pub fn apply_subtract_green(pixels: &mut [u32]) {
for px in pixels.iter_mut() {
let a = (*px >> 24) & 0xff;
let r = (*px >> 16) & 0xff;
let g = (*px >> 8) & 0xff;
let b = *px & 0xff;
let r_new = r.wrapping_sub(g) & 0xff;
let b_new = b.wrapping_sub(g) & 0xff;
*px = (a << 24) | (r_new << 16) | (g << 8) | b_new;
}
}
#[inline]
fn predictor_div_round_up(num: u32, den: u32) -> u32 {
num.div_ceil(den)
}
#[inline]
fn predictor_average2(a: u32, b: u32) -> u32 {
let f = |sh: u32| -> u32 {
let ca = (a >> sh) & 0xff;
let cb = (b >> sh) & 0xff;
(ca + cb) / 2
};
(f(24) << 24) | (f(16) << 16) | (f(8) << 8) | f(0)
}
#[inline]
fn predictor_clamp(a: i32) -> i32 {
a.clamp(0, 255)
}
#[inline]
fn predictor_clamp_add_subtract_full(a: u32, b: u32, c: u32) -> u32 {
let f = |sh: u32| -> u32 {
let ca = ((a >> sh) & 0xff) as i32;
let cb = ((b >> sh) & 0xff) as i32;
let cc = ((c >> sh) & 0xff) as i32;
predictor_clamp(ca + cb - cc) as u32
};
(f(24) << 24) | (f(16) << 16) | (f(8) << 8) | f(0)
}
#[inline]
fn predictor_clamp_add_subtract_half(a: u32, b: u32) -> u32 {
let f = |sh: u32| -> u32 {
let ca = ((a >> sh) & 0xff) as i32;
let cb = ((b >> sh) & 0xff) as i32;
predictor_clamp(ca + (ca - cb) / 2) as u32
};
(f(24) << 24) | (f(16) << 16) | (f(8) << 8) | f(0)
}
#[inline]
fn predictor_select(l: u32, t: u32, tl: u32) -> u32 {
let ach = |x: u32| ((x >> 24) & 0xff) as i32;
let rch = |x: u32| ((x >> 16) & 0xff) as i32;
let gch = |x: u32| ((x >> 8) & 0xff) as i32;
let bch = |x: u32| (x & 0xff) as i32;
let p_a = ach(l) + ach(t) - ach(tl);
let p_r = rch(l) + rch(t) - rch(tl);
let p_g = gch(l) + gch(t) - gch(tl);
let p_b = bch(l) + bch(t) - bch(tl);
let p_l =
(p_a - ach(l)).abs() + (p_r - rch(l)).abs() + (p_g - gch(l)).abs() + (p_b - bch(l)).abs();
let p_t =
(p_a - ach(t)).abs() + (p_r - rch(t)).abs() + (p_g - gch(t)).abs() + (p_b - bch(t)).abs();
if p_l < p_t {
l
} else {
t
}
}
fn predictor_predict(mode: u8, l: u32, t: u32, tr: u32, tl: u32) -> u32 {
match mode {
0 => 0xff00_0000,
1 => l,
2 => t,
3 => tr,
4 => tl,
5 => predictor_average2(predictor_average2(l, tr), t),
6 => predictor_average2(l, tl),
7 => predictor_average2(l, t),
8 => predictor_average2(tl, t),
9 => predictor_average2(t, tr),
10 => predictor_average2(predictor_average2(l, tl), predictor_average2(t, tr)),
11 => predictor_select(l, t, tl),
12 => predictor_clamp_add_subtract_full(l, t, tl),
13 => predictor_clamp_add_subtract_half(predictor_average2(l, t), tl),
_ => 0xff00_0000,
}
}
#[inline]
fn predictor_subtract(original: u32, pred: u32) -> u32 {
let a = ((original >> 24) & 0xff).wrapping_sub((pred >> 24) & 0xff) & 0xff;
let r = ((original >> 16) & 0xff).wrapping_sub((pred >> 16) & 0xff) & 0xff;
let g = ((original >> 8) & 0xff).wrapping_sub((pred >> 8) & 0xff) & 0xff;
let b = (original & 0xff).wrapping_sub(pred & 0xff) & 0xff;
(a << 24) | (r << 16) | (g << 8) | b
}
#[inline]
fn residual_magnitude(residual: u32) -> u32 {
let fold = |v: u32| -> u32 {
let v = v & 0xff;
if v <= 128 {
v
} else {
256 - v
}
};
fold(residual >> 24) + fold(residual >> 16) + fold(residual >> 8) + fold(residual)
}
fn predictor_at(pixels: &[u32], width: usize, x: usize, y: usize, mode: u8) -> u32 {
if x == 0 && y == 0 {
return 0xff00_0000;
}
let idx = y * width + x;
if y == 0 {
return pixels[idx - 1];
}
if x == 0 {
return pixels[idx - width];
}
let l = pixels[idx - 1];
let t = pixels[idx - width];
let tl = pixels[idx - width - 1];
let tr = if x == width - 1 {
pixels[idx - width - (width - 1)]
} else {
pixels[idx - width + 1]
};
predictor_predict(mode, l, t, tr, tl)
}
#[cfg(test)]
fn pick_block_mode(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
) -> u8 {
pick_block_mode_with_hint(pixels, width, height, x0, y0, bw, bh, None)
}
#[allow(clippy::too_many_arguments)]
fn block_mode_cost(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
mode: u8,
) -> u64 {
let mut cost: u64 = 0;
for dy in 0..bh {
let y = y0 + dy;
if y >= height {
break;
}
for dx in 0..bw {
let x = x0 + dx;
if x >= width {
break;
}
let pred = predictor_at(pixels, width, x, y, mode);
let original = pixels[y * width + x];
let residual = predictor_subtract(original, pred);
cost += residual_magnitude(residual) as u64;
}
}
cost
}
#[allow(clippy::too_many_arguments)]
fn pick_block_mode_with_hint(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
prefer_mode: Option<u8>,
) -> u8 {
let mut best_mode: u8 = 0;
let mut best_cost = u64::MAX;
for mode in 0u8..=13 {
let mut cost: u64 = 0;
for dy in 0..bh {
let y = y0 + dy;
if y >= height {
break;
}
for dx in 0..bw {
let x = x0 + dx;
if x >= width {
break;
}
let pred = predictor_at(pixels, width, x, y, mode);
let original = pixels[y * width + x];
let residual = predictor_subtract(original, pred);
cost += residual_magnitude(residual) as u64;
if cost >= best_cost {
break;
}
}
if cost >= best_cost {
break;
}
}
if cost < best_cost {
best_cost = cost;
best_mode = mode;
}
}
if let Some(m) = prefer_mode {
if m != best_mode {
let cost = block_mode_cost(pixels, width, height, x0, y0, bw, bh, m);
if cost == best_cost {
best_mode = m;
}
}
}
best_mode
}
#[allow(clippy::too_many_arguments)]
fn pick_block_mode_with_hint_slack(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
prefer_mode: Option<u8>,
slack: u64,
) -> u8 {
let mut best_mode: u8 = 0;
let mut best_cost = u64::MAX;
for mode in 0u8..=13 {
let mut cost: u64 = 0;
for dy in 0..bh {
let y = y0 + dy;
if y >= height {
break;
}
for dx in 0..bw {
let x = x0 + dx;
if x >= width {
break;
}
let pred = predictor_at(pixels, width, x, y, mode);
let original = pixels[y * width + x];
let residual = predictor_subtract(original, pred);
cost += residual_magnitude(residual) as u64;
if cost >= best_cost {
break;
}
}
if cost >= best_cost {
break;
}
}
if cost < best_cost {
best_cost = cost;
best_mode = mode;
}
}
if let Some(m) = prefer_mode {
if m != best_mode {
let cost = block_mode_cost(pixels, width, height, x0, y0, bw, bh, m);
if cost <= best_cost.saturating_add(slack) {
best_mode = m;
}
}
}
best_mode
}
fn build_predictor_image(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
let mut prev_row: Vec<Option<u8>> = vec![None; tw as usize];
for by in 0..th as usize {
let mut left_mode: Option<u8> = None;
for (bx, top_slot) in prev_row.iter_mut().enumerate() {
let x0 = bx * bsz;
let y0 = by * bsz;
let prefer = left_mode.or(*top_slot);
let mode = pick_block_mode_with_hint(pixels, w, h, x0, y0, bsz, bsz, prefer);
img.push(0xff00_0000 | ((mode as u32) << 8));
left_mode = Some(mode);
*top_slot = Some(mode);
}
}
(img, tw, th)
}
fn build_predictor_image_with_slack(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
slack: u64,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
let mut prev_row: Vec<Option<u8>> = vec![None; tw as usize];
for by in 0..th as usize {
let mut left_mode: Option<u8> = None;
for (bx, top_slot) in prev_row.iter_mut().enumerate() {
let x0 = bx * bsz;
let y0 = by * bsz;
let prefer = left_mode.or(*top_slot);
let mode =
pick_block_mode_with_hint_slack(pixels, w, h, x0, y0, bsz, bsz, prefer, slack);
img.push(0xff00_0000 | ((mode as u32) << 8));
left_mode = Some(mode);
*top_slot = Some(mode);
}
}
(img, tw, th)
}
#[allow(clippy::too_many_arguments)]
fn block_mode_entropy_cost(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
mode: u8,
) -> u64 {
let mut hist: [[u32; 256]; 4] = [[0u32; 256]; 4];
let mut n: u32 = 0;
for dy in 0..bh {
let y = y0 + dy;
if y >= height {
break;
}
for dx in 0..bw {
let x = x0 + dx;
if x >= width {
break;
}
let pred = predictor_at(pixels, width, x, y, mode);
let original = pixels[y * width + x];
let residual = predictor_subtract(original, pred);
hist[0][((residual >> 24) & 0xff) as usize] += 1;
hist[1][((residual >> 16) & 0xff) as usize] += 1;
hist[2][((residual >> 8) & 0xff) as usize] += 1;
hist[3][(residual & 0xff) as usize] += 1;
n += 1;
}
}
if n == 0 {
return 0;
}
let n_f = n as f64;
let log2_n = n_f.log2();
let mut milli_bits: f64 = 0.0;
for channel_hist in &hist {
for &count in channel_hist.iter() {
if count == 0 {
continue;
}
let c_f = count as f64;
milli_bits += c_f * (log2_n - c_f.log2());
}
}
(milli_bits * 1000.0 + 0.5) as u64
}
#[allow(clippy::too_many_arguments)]
fn pick_block_mode_with_hint_entropy(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
prefer_mode: Option<u8>,
) -> u8 {
let mut best_mode: u8 = 0;
let mut best_cost = u64::MAX;
for mode in 0u8..=13 {
let cost = block_mode_entropy_cost(pixels, width, height, x0, y0, bw, bh, mode);
if cost < best_cost {
best_cost = cost;
best_mode = mode;
}
}
if let Some(m) = prefer_mode {
if m != best_mode {
let cost = block_mode_entropy_cost(pixels, width, height, x0, y0, bw, bh, m);
if cost == best_cost {
best_mode = m;
}
}
}
best_mode
}
fn build_predictor_image_entropy(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
let mut prev_row: Vec<Option<u8>> = vec![None; tw as usize];
for by in 0..th as usize {
let mut left_mode: Option<u8> = None;
for (bx, top_slot) in prev_row.iter_mut().enumerate() {
let x0 = bx * bsz;
let y0 = by * bsz;
let prefer = left_mode.or(*top_slot);
let mode = pick_block_mode_with_hint_entropy(pixels, w, h, x0, y0, bsz, bsz, prefer);
img.push(0xff00_0000 | ((mode as u32) << 8));
left_mode = Some(mode);
*top_slot = Some(mode);
}
}
(img, tw, th)
}
fn sub_image_mode_cost_delta_milli(hist: &[u32; 14], total: u32, mode: u8) -> u64 {
debug_assert!(mode < 14);
let n_old = total as f64;
let n_new = (total + 1) as f64;
let log2_n_old = if total > 0 { n_old.log2() } else { 0.0 };
let log2_n_new = n_new.log2();
let mut mass_old: f64 = 0.0;
let mut mass_new: f64 = 0.0;
for (m, &c) in hist.iter().enumerate() {
let c_after = if m == mode as usize { c + 1 } else { c };
if c > 0 {
let c_f = c as f64;
mass_old += c_f * (log2_n_old - c_f.log2());
}
if c_after > 0 {
let c_f = c_after as f64;
mass_new += c_f * (log2_n_new - c_f.log2());
}
}
let delta = (mass_new - mass_old).max(0.0);
(delta * 1000.0 + 0.5) as u64
}
#[allow(clippy::too_many_arguments)]
fn pick_block_mode_with_hint_entropy_subaware(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
prefer_mode: Option<u8>,
sub_image_hist: &[u32; 14],
sub_image_total: u32,
lambda_milli: u64,
) -> u8 {
let mut best_mode: u8 = 0;
let mut best_cost = u64::MAX;
for mode in 0u8..=13 {
let residual_cost = block_mode_entropy_cost(pixels, width, height, x0, y0, bw, bh, mode);
let sub_delta = sub_image_mode_cost_delta_milli(sub_image_hist, sub_image_total, mode);
let weighted_sub = sub_delta.saturating_mul(lambda_milli) / 1000;
let cost = residual_cost.saturating_add(weighted_sub);
if cost < best_cost {
best_cost = cost;
best_mode = mode;
}
}
if let Some(m) = prefer_mode {
if m != best_mode {
let residual_cost = block_mode_entropy_cost(pixels, width, height, x0, y0, bw, bh, m);
let sub_delta = sub_image_mode_cost_delta_milli(sub_image_hist, sub_image_total, m);
let weighted_sub = sub_delta.saturating_mul(lambda_milli) / 1000;
let cost = residual_cost.saturating_add(weighted_sub);
if cost == best_cost {
best_mode = m;
}
}
}
best_mode
}
fn build_predictor_image_entropy_subaware(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
lambda_milli: u64,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
let mut prev_row: Vec<Option<u8>> = vec![None; tw as usize];
let mut hist = [0u32; 14];
let mut total: u32 = 0;
for by in 0..th as usize {
let mut left_mode: Option<u8> = None;
for (bx, top_slot) in prev_row.iter_mut().enumerate() {
let x0 = bx * bsz;
let y0 = by * bsz;
let prefer = left_mode.or(*top_slot);
let mode = pick_block_mode_with_hint_entropy_subaware(
pixels,
w,
h,
x0,
y0,
bsz,
bsz,
prefer,
&hist,
total,
lambda_milli,
);
img.push(0xff00_0000 | ((mode as u32) << 8));
left_mode = Some(mode);
*top_slot = Some(mode);
hist[mode as usize] += 1;
total += 1;
}
}
(img, tw, th)
}
fn apply_forward_predictor(
src: &[u32],
dst: &mut [u32],
width: u32,
height: u32,
predictor_image: &[u32],
transform_width: u32,
size_bits: u8,
) {
if width == 0 || height == 0 {
return;
}
let w = width as usize;
let h = height as usize;
for y in 0..h {
for x in 0..w {
let idx = y * w + x;
let mode = if x == 0 || y == 0 {
0
} else {
let bx = (x as u32) >> size_bits;
let by = (y as u32) >> size_bits;
let block_index = (by * transform_width + bx) as usize;
((predictor_image[block_index] >> 8) & 0xff) as u8
};
let pred = predictor_at(src, w, x, y, mode);
dst[idx] = predictor_subtract(src[idx], pred);
}
}
}
const DEFAULT_PREDICTOR_SIZE_BITS: u8 = 4;
fn encode_with_predictor(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Predictor as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (predictor_image, tw, _th) = build_predictor_image(pixels, width, height, size_bits);
write_entropy_coded_image_literals(&mut w, &predictor_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(
pixels,
&mut residuals,
width,
height,
&predictor_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
fn encode_with_predictor_slack(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
slack: u64,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Predictor as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (predictor_image, tw, _th) =
build_predictor_image_with_slack(pixels, width, height, size_bits, slack);
write_entropy_coded_image_literals(&mut w, &predictor_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(
pixels,
&mut residuals,
width,
height,
&predictor_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
fn encode_with_predictor_entropy(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Predictor as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (predictor_image, tw, _th) =
build_predictor_image_entropy(pixels, width, height, size_bits);
write_entropy_coded_image_literals(&mut w, &predictor_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(
pixels,
&mut residuals,
width,
height,
&predictor_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
fn encode_with_predictor_entropy_subaware(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
lambda_milli: u64,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Predictor as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (predictor_image, tw, _th) =
build_predictor_image_entropy_subaware(pixels, width, height, size_bits, lambda_milli);
write_entropy_coded_image_literals(&mut w, &predictor_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(
pixels,
&mut residuals,
width,
height,
&predictor_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
#[inline]
fn color_xfrm_delta(t: u8, c: u8) -> i32 {
let ts = t as i8 as i32;
let cs = c as i8 as i32;
(ts * cs) >> 5
}
#[inline]
fn forward_color_pixel(
r: u8,
g: u8,
b: u8,
green_to_red: u8,
green_to_blue: u8,
red_to_blue: u8,
) -> (u8, u8) {
let mut tmp_red = r as i32;
let mut tmp_blue = b as i32;
tmp_red -= color_xfrm_delta(green_to_red, g);
tmp_blue -= color_xfrm_delta(green_to_blue, g);
tmp_blue -= color_xfrm_delta(red_to_blue, r);
((tmp_red & 0xff) as u8, (tmp_blue & 0xff) as u8)
}
const CTE_AXIS_CANDIDATES: [u8; 25] = [
0xa0, 0xb0, 0xc0, 0xd0, 0xe0, 0xe8, 0xec, 0xf0, 0xf4, 0xf8, 0xfc, 0xfe, 0x00, 0x02, 0x04, 0x08, 0x0c, 0x10, 0x14, 0x18, 0x20, 0x30, 0x40, 0x50, 0x60, ];
#[inline]
fn channel_magnitude(v: u32) -> u32 {
let v = v & 0xff;
if v <= 128 {
v
} else {
256 - v
}
}
fn pick_block_cte(
pixels: &[u32],
width: usize,
height: usize,
x0: usize,
y0: usize,
bw: usize,
bh: usize,
) -> (u8, u8, u8) {
let mut samples: Vec<(u8, u8, u8)> = Vec::with_capacity(bw * bh);
for dy in 0..bh {
let y = y0 + dy;
if y >= height {
break;
}
for dx in 0..bw {
let x = x0 + dx;
if x >= width {
break;
}
let px = pixels[y * width + x];
let r = ((px >> 16) & 0xff) as u8;
let g = ((px >> 8) & 0xff) as u8;
let b = (px & 0xff) as u8;
samples.push((r, g, b));
}
}
if samples.is_empty() {
return (0, 0, 0);
}
let mut best_gtr: u8 = 0;
let mut best_red_cost = u64::MAX;
for >r in &CTE_AXIS_CANDIDATES {
let mut cost = 0u64;
for &(r, g, _b) in &samples {
let residual = (r as i32 - color_xfrm_delta(gtr, g)) as u32;
cost += channel_magnitude(residual) as u64;
if cost >= best_red_cost {
break;
}
}
if cost < best_red_cost {
best_red_cost = cost;
best_gtr = gtr;
}
}
let mut best_gtb: u8 = 0;
let mut best_blue_pre_cost = u64::MAX;
for >b in &CTE_AXIS_CANDIDATES {
let mut cost = 0u64;
for &(_r, g, b) in &samples {
let residual = (b as i32 - color_xfrm_delta(gtb, g)) as u32;
cost += channel_magnitude(residual) as u64;
if cost >= best_blue_pre_cost {
break;
}
}
if cost < best_blue_pre_cost {
best_blue_pre_cost = cost;
best_gtb = gtb;
}
}
let mut best_rtb: u8 = 0;
let mut best_blue_cost = u64::MAX;
for &rtb in &CTE_AXIS_CANDIDATES {
let mut cost = 0u64;
for &(r, g, b) in &samples {
let inter = b as i32 - color_xfrm_delta(best_gtb, g);
let residual = (inter - color_xfrm_delta(rtb, r)) as u32;
cost += channel_magnitude(residual) as u64;
if cost >= best_blue_cost {
break;
}
}
if cost < best_blue_cost {
best_blue_cost = cost;
best_rtb = rtb;
}
}
(best_gtr, best_gtb, best_rtb)
}
fn build_color_image(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
for by in 0..th as usize {
for bx in 0..tw as usize {
let x0 = bx * bsz;
let y0 = by * bsz;
let (gtr, gtb, rtb) = pick_block_cte(pixels, w, h, x0, y0, bsz, bsz);
let argb = 0xff00_0000 | ((rtb as u32) << 16) | ((gtb as u32) << 8) | (gtr as u32);
img.push(argb);
}
}
(img, tw, th)
}
fn apply_forward_color(
src: &[u32],
dst: &mut [u32],
width: u32,
height: u32,
color_image: &[u32],
transform_width: u32,
size_bits: u8,
) {
if width == 0 || height == 0 {
return;
}
let w = width as usize;
let h = height as usize;
for y in 0..h {
for x in 0..w {
let idx = y * w + x;
let bx = (x as u32) >> size_bits;
let by = (y as u32) >> size_bits;
let block_index = (by * transform_width + bx) as usize;
let cte = color_image[block_index];
let red_to_blue = ((cte >> 16) & 0xff) as u8;
let green_to_blue = ((cte >> 8) & 0xff) as u8;
let green_to_red = (cte & 0xff) as u8;
let px = src[idx];
let a = ((px >> 24) & 0xff) as u8;
let r = ((px >> 16) & 0xff) as u8;
let g = ((px >> 8) & 0xff) as u8;
let b = (px & 0xff) as u8;
let (new_r, new_b) =
forward_color_pixel(r, g, b, green_to_red, green_to_blue, red_to_blue);
dst[idx] =
((a as u32) << 24) | ((new_r as u32) << 16) | ((g as u32) << 8) | (new_b as u32);
}
}
}
const DEFAULT_COLOR_TRANSFORM_SIZE_BITS: u8 = 4;
fn encode_with_color_transform(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Color as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (color_image, tw, _th) = build_color_image(pixels, width, height, size_bits);
write_entropy_coded_image_literals(&mut w, &color_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_color(
pixels,
&mut residuals,
width,
height,
&color_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
const MAX_PALETTE_SIZE: usize = 256;
fn encoder_color_indexing_width_bits(color_table_size: usize) -> u8 {
if color_table_size <= 2 {
3
} else if color_table_size <= 4 {
2
} else if color_table_size <= 16 {
1
} else {
0
}
}
fn collect_palette(pixels: &[u32]) -> Option<(Vec<u32>, std::collections::HashMap<u32, u32>)> {
use std::collections::HashSet;
let mut set: HashSet<u32> = HashSet::new();
for &p in pixels {
set.insert(p);
if set.len() > MAX_PALETTE_SIZE {
return None;
}
}
let mut palette: Vec<u32> = set.into_iter().collect();
palette.sort_unstable();
let mut map: std::collections::HashMap<u32, u32> =
std::collections::HashMap::with_capacity(palette.len());
for (i, &c) in palette.iter().enumerate() {
map.insert(c, i as u32);
}
Some((palette, map))
}
fn forward_color_table(color_table: &mut [u32]) {
if color_table.len() < 2 {
return;
}
for i in (1..color_table.len()).rev() {
let cur = color_table[i];
let prev = color_table[i - 1];
let a = ((cur >> 24) & 0xff).wrapping_sub((prev >> 24) & 0xff) & 0xff;
let r = ((cur >> 16) & 0xff).wrapping_sub((prev >> 16) & 0xff) & 0xff;
let g = ((cur >> 8) & 0xff).wrapping_sub((prev >> 8) & 0xff) & 0xff;
let b = (cur & 0xff).wrapping_sub(prev & 0xff) & 0xff;
color_table[i] = (a << 24) | (r << 16) | (g << 8) | b;
}
}
fn pack_indices_into_bundled_image(
pixels: &[u32],
index_of: &std::collections::HashMap<u32, u32>,
width: u32,
height: u32,
width_bits: u8,
) -> (Vec<u32>, u32) {
let count = 1u32 << width_bits;
let bits_per_index = if width_bits == 0 { 8 } else { 8 / count };
let packed_width = width.div_ceil(count);
let pw = packed_width as usize;
let w = width as usize;
let h = height as usize;
let mut out = vec![0u32; pw * h];
for y in 0..h {
for x in 0..w {
let idx = *index_of
.get(&pixels[y * w + x])
.expect("collect_palette covered every pixel");
let packed_x = x / count as usize;
let sub = x % count as usize;
let shift = sub * bits_per_index as usize;
let bits = (idx & ((1u32 << bits_per_index) - 1)) << shift;
out[y * pw + packed_x] |= bits << 8; }
}
(out, packed_width)
}
fn encode_with_color_indexing(
pixels: &[u32],
width: u32,
height: u32,
cache_code_bits: Option<u32>,
) -> Option<Vec<u8>> {
let (palette, index_of) = collect_palette(pixels)?;
if palette.is_empty() {
return None;
}
let width_bits = encoder_color_indexing_width_bits(palette.len());
let (packed_image, packed_width) =
pack_indices_into_bundled_image(pixels, &index_of, width, height, width_bits);
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::ColorIndexing as u32, 2);
debug_assert!((1..=MAX_PALETTE_SIZE).contains(&palette.len()));
w.write_bits((palette.len() - 1) as u32, 8);
let mut subtraction_encoded = palette.clone();
forward_color_table(&mut subtraction_encoded);
write_entropy_coded_image_literals(&mut w, &subtraction_encoded);
w.write_bit(false);
let mut tokens = tokenize_lz77(&packed_image);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &packed_image, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, packed_width);
Some(w.into_bytes())
}
const META_PREFIX_BITS_SWEEP: [u8; 4] = [4, 5, 6, 7];
const MAX_META_GROUPS: u32 = 4;
const CLUSTER_BIN_SHIFT: u32 = 4;
const CLUSTER_BINS_PER_CHANNEL: usize = 256 >> CLUSTER_BIN_SHIFT;
const CLUSTER_NUM_CHANNELS: usize = 3;
const CLUSTER_FEATURE_DIM: usize = CLUSTER_BINS_PER_CHANNEL * CLUSTER_NUM_CHANNELS;
const CLUSTER_MAX_ITERATIONS: u32 = 8;
fn histogram_block_features(
pixels: &[u32],
width: u32,
height: u32,
prefix_bits: u8,
) -> (Vec<u32>, usize) {
let block_side = 1u32 << prefix_bits;
let blocks_wide = width.div_ceil(block_side) as usize;
let blocks_high = height.div_ceil(block_side) as usize;
let block_count = blocks_wide * blocks_high;
let mut features = vec![0u32; block_count * CLUSTER_FEATURE_DIM];
let row_stride = width as usize;
let bs = block_side as usize;
for y in 0..height as usize {
let block_row = y / bs;
for x in 0..width as usize {
let block_col = x / bs;
let block_index = block_row * blocks_wide + block_col;
let pixel = pixels[y * row_stride + x];
let r_bin = (((pixel >> 16) & 0xff) >> CLUSTER_BIN_SHIFT) as usize;
let g_bin = (((pixel >> 8) & 0xff) >> CLUSTER_BIN_SHIFT) as usize;
let b_bin = ((pixel & 0xff) >> CLUSTER_BIN_SHIFT) as usize;
let base = block_index * CLUSTER_FEATURE_DIM;
features[base + r_bin] += 1;
features[base + CLUSTER_BINS_PER_CHANNEL + g_bin] += 1;
features[base + 2 * CLUSTER_BINS_PER_CHANNEL + b_bin] += 1;
}
}
(features, block_count)
}
fn histogram_l1(a: &[u32], b: &[u32]) -> u64 {
debug_assert_eq!(a.len(), CLUSTER_FEATURE_DIM);
debug_assert_eq!(b.len(), CLUSTER_FEATURE_DIM);
let mut sum: u64 = 0;
for i in 0..CLUSTER_FEATURE_DIM {
let ai = a[i];
let bi = b[i];
sum += ai.abs_diff(bi) as u64;
}
sum
}
fn seed_cluster_centroids(features: &[u32], block_count: usize, num_groups: u32) -> Vec<usize> {
let target = num_groups as usize;
debug_assert!(target >= 1 && target <= block_count);
let mut picks: Vec<usize> = Vec::with_capacity(target);
picks.push(0);
while picks.len() < target {
let mut champion_block = 0usize;
let mut champion_min_dist: u64 = 0;
for cand in 0..block_count {
if picks.contains(&cand) {
continue;
}
let cand_vec = &features[cand * CLUSTER_FEATURE_DIM..(cand + 1) * CLUSTER_FEATURE_DIM];
let mut nearest: u64 = u64::MAX;
for &p in &picks {
let pick_vec = &features[p * CLUSTER_FEATURE_DIM..(p + 1) * CLUSTER_FEATURE_DIM];
let d = histogram_l1(cand_vec, pick_vec);
if d < nearest {
nearest = d;
}
}
if nearest > champion_min_dist {
champion_min_dist = nearest;
champion_block = cand;
}
}
if champion_min_dist == 0 {
break;
}
picks.push(champion_block);
}
picks
}
fn cluster_blocks_by_histogram_distance(
pixels: &[u32],
width: u32,
height: u32,
prefix_bits: u8,
num_groups: u32,
) -> Vec<u16> {
debug_assert!(num_groups >= 1);
let (features, block_count) = histogram_block_features(pixels, width, height, prefix_bits);
if num_groups == 1 || block_count <= 1 {
return vec![0u16; block_count];
}
let seeds = seed_cluster_centroids(&features, block_count, num_groups);
if seeds.len() < 2 {
return vec![0u16; block_count];
}
let cluster_k = seeds.len();
let mut centroid_sums: Vec<u64> = vec![0u64; cluster_k * CLUSTER_FEATURE_DIM];
let mut centroid_counts: Vec<u64> = vec![1u64; cluster_k];
for (slot, &block_idx) in seeds.iter().enumerate() {
let src = &features[block_idx * CLUSTER_FEATURE_DIM..(block_idx + 1) * CLUSTER_FEATURE_DIM];
for (i, &v) in src.iter().enumerate() {
centroid_sums[slot * CLUSTER_FEATURE_DIM + i] = v as u64;
}
}
let mut assignment: Vec<u16> = vec![0u16; block_count];
let mut centroid_view: Vec<u32> = vec![0u32; CLUSTER_FEATURE_DIM];
for _pass in 0..CLUSTER_MAX_ITERATIONS {
let mut any_change = false;
for b in 0..block_count {
let block_vec = &features[b * CLUSTER_FEATURE_DIM..(b + 1) * CLUSTER_FEATURE_DIM];
let mut best_group: u16 = 0;
let mut best_dist: u64 = u64::MAX;
for ci in 0..cluster_k {
let divisor = centroid_counts[ci].max(1);
for i in 0..CLUSTER_FEATURE_DIM {
let raw = centroid_sums[ci * CLUSTER_FEATURE_DIM + i];
centroid_view[i] = (raw / divisor) as u32;
}
let d = histogram_l1(block_vec, ¢roid_view);
if d < best_dist {
best_dist = d;
best_group = ci as u16;
}
}
if assignment[b] != best_group {
assignment[b] = best_group;
any_change = true;
}
}
if !any_change {
break;
}
for slot in centroid_sums.iter_mut() {
*slot = 0;
}
for slot in centroid_counts.iter_mut() {
*slot = 0;
}
for b in 0..block_count {
let ci = assignment[b] as usize;
let block_vec = &features[b * CLUSTER_FEATURE_DIM..(b + 1) * CLUSTER_FEATURE_DIM];
let base = ci * CLUSTER_FEATURE_DIM;
for (i, &v) in block_vec.iter().enumerate() {
centroid_sums[base + i] += v as u64;
}
centroid_counts[ci] += 1;
}
}
let mut remap: Vec<i32> = vec![-1; cluster_k];
let mut next_id: u16 = 0;
for slot in assignment.iter_mut() {
let group = *slot as usize;
if remap[group] < 0 {
remap[group] = next_id as i32;
next_id += 1;
}
*slot = remap[group] as u16;
}
if next_id < 2 {
return vec![0u16; block_count];
}
assignment
}
struct EncoderMetaIndex {
prefix_bits: u8,
block_width: u32,
codes: Vec<u16>,
}
impl EncoderMetaIndex {
fn group_for(&self, x: u32, y: u32) -> u16 {
let bx = x >> self.prefix_bits;
let by = y >> self.prefix_bits;
self.codes[(by * self.block_width + bx) as usize]
}
fn num_groups(&self) -> u32 {
self.codes
.iter()
.copied()
.max()
.map(|c| c as u32 + 1)
.unwrap_or(1)
}
fn entropy_image_argb(&self) -> Vec<u32> {
self.codes
.iter()
.map(|&c| {
let lo = (c & 0xff) as u32; let hi = ((c >> 8) & 0xff) as u32; (hi << 16) | (lo << 8)
})
.collect()
}
}
fn split_tokens_by_group(
tokens: &[Token],
index: &EncoderMetaIndex,
width: u32,
num_groups: u32,
) -> Vec<Vec<Token>> {
let mut buckets: Vec<Vec<Token>> = vec![Vec::new(); num_groups as usize];
let mut pos = 0usize;
let w = width as usize;
for &tok in tokens {
let x = (pos % w) as u32;
let y = (pos / w) as u32;
let g = index.group_for(x, y) as usize;
debug_assert!(g < buckets.len());
buckets[g].push(tok);
let consumed = match tok {
Token::Literal(_) | Token::CacheRef { .. } => 1usize,
Token::Copy { length, .. } => length,
};
pos += consumed;
}
buckets
}
fn build_group_codes(
buckets: &[Vec<Token>],
color_cache_size: usize,
image_width: u32,
) -> Vec<[WriteCode; 5]> {
let green_alphabet = 256 + crate::vp8l_decode::NUM_LENGTH_PREFIX_CODES + color_cache_size;
buckets
.iter()
.map(|bucket| {
let freqs = count_frequencies(bucket, color_cache_size, image_width);
let green = if freqs.green.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.green)
} else {
WriteCode::empty(green_alphabet)
};
let red = if freqs.red.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.red)
} else {
WriteCode::empty(256)
};
let blue = if freqs.blue.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.blue)
} else {
WriteCode::empty(256)
};
let alpha = if freqs.alpha.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.alpha)
} else {
WriteCode::empty(256)
};
let dist = if freqs.distance.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.distance)
} else {
WriteCode::empty(40)
};
[green, red, blue, alpha, dist]
})
.collect()
}
fn encode_with_meta_prefix(
pixels: &[u32],
width: u32,
height: u32,
prefix_bits: u8,
num_groups: u32,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Option<Vec<u8>> {
debug_assert!((2..=9).contains(&prefix_bits));
debug_assert!((1..=MAX_META_GROUPS).contains(&num_groups));
let block_side = 1u32 << prefix_bits;
let pw = width.div_ceil(block_side);
let ph = height.div_ceil(block_side);
if (pw * ph) < num_groups {
return None;
}
let codes =
cluster_blocks_by_histogram_distance(pixels, width, height, prefix_bits, num_groups);
let index = EncoderMetaIndex {
prefix_bits,
block_width: pw,
codes,
};
let actual_groups = index.num_groups();
if actual_groups < 2 {
return None;
}
let mut tokens = tokenize_lz77(pixels);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, pixels, bits);
}
let buckets = split_tokens_by_group(&tokens, &index, width, actual_groups);
let cache_size = cache_code_bits.map(|b| 1usize << b).unwrap_or(0);
let group_codes = build_group_codes(&buckets, cache_size, image_width);
let mut w = BitWriter::new();
w.write_bit(false);
if let Some(bits) = cache_code_bits {
debug_assert!((COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).contains(&bits));
w.write_bit(true);
w.write_bits(bits, 4);
} else {
w.write_bit(false);
}
w.write_bit(true);
w.write_bits((prefix_bits - 2) as u32, 3);
let entropy_image = index.entropy_image_argb();
write_entropy_coded_image_literals(&mut w, &entropy_image);
for group in &group_codes {
for code in group.iter() {
code.write_code_lengths(&mut w);
}
}
let mut pos = 0usize;
let w_pixels = width as usize;
for &tok in &tokens {
let x = (pos % w_pixels) as u32;
let y = (pos / w_pixels) as u32;
let g = index.group_for(x, y) as usize;
let codes = &group_codes[g];
let green_code = &codes[0];
let red_code = &codes[1];
let blue_code = &codes[2];
let alpha_code = &codes[3];
let dist_code = &codes[4];
match tok {
Token::Literal(p) => {
let a = ((p >> 24) & 0xff) as usize;
let r = ((p >> 16) & 0xff) as usize;
let g_ch = ((p >> 8) & 0xff) as usize;
let b = (p & 0xff) as usize;
green_code.write_symbol(&mut w, g_ch);
red_code.write_symbol(&mut w, r);
blue_code.write_symbol(&mut w, b);
alpha_code.write_symbol(&mut w, a);
pos += 1;
}
Token::CacheRef { index: ix } => {
debug_assert!(cache_size > 0, "CacheRef requires an enabled cache");
let sym = 256 + crate::vp8l_decode::NUM_LENGTH_PREFIX_CODES + ix as usize;
green_code.write_symbol(&mut w, sym);
pos += 1;
}
Token::Copy { length, distance } => {
write_lz77_value(&mut w, green_code, 256, length as u32);
let raw_code = pixel_distance_to_distance_code(distance, image_width);
write_lz77_value(&mut w, dist_code, 0, raw_code);
pos += length;
}
}
}
Some(w.into_bytes())
}
pub fn encode_argb_literals(pixels: &[u32]) -> Vec<u8> {
encode_argb_literals_with_width(pixels, 1)
}
pub fn encode_argb_literals_with_width(pixels: &[u32], image_width: u32) -> Vec<u8> {
debug_assert!(image_width >= 1);
let mut best = select_best_cache_bits(|cache_bits| {
encode_literals_with_options(pixels, false, cache_bits, image_width)
});
let sg_best = select_best_cache_bits(|cache_bits| {
encode_literals_with_options(pixels, true, cache_bits, image_width)
});
if sg_best.len() < best.len() {
best = sg_best;
}
best
}
fn select_best_cache_bits<F>(mut build_with_cache: F) -> Vec<u8>
where
F: FnMut(Option<u32>) -> Vec<u8>,
{
let mut best = build_with_cache(None);
for bits in COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX {
let cand = build_with_cache(Some(bits));
if cand.len() < best.len() {
best = cand;
}
}
best
}
fn encode_literals_with_options(
pixels: &[u32],
subtract_green: bool,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut working = pixels.to_vec();
if subtract_green {
apply_subtract_green(&mut working);
}
let mut tokens = tokenize_lz77(&working);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &working, bits);
}
encode_tokens(&tokens, subtract_green, cache_code_bits, image_width)
}
pub fn encode_argb_literals_only(pixels: &[u32]) -> Vec<u8> {
let tokens: Vec<Token> = pixels.iter().map(|&p| Token::Literal(p)).collect();
encode_tokens(&tokens, false, None, 1)
}
pub fn encode_argb_literals_subtract_green(pixels: &[u32]) -> Vec<u8> {
let mut sg_pixels = pixels.to_vec();
apply_subtract_green(&mut sg_pixels);
let tokens = tokenize_lz77(&sg_pixels);
encode_tokens(&tokens, true, None, 1)
}
pub fn encode_argb_literals_color_cache(pixels: &[u32], cache_code_bits: u32) -> Vec<u8> {
debug_assert!((COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).contains(&cache_code_bits));
encode_literals_with_options(pixels, false, Some(cache_code_bits), 1)
}
fn encode_tokens(
tokens: &[Token],
subtract_green: bool,
color_cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut w = BitWriter::new();
if subtract_green {
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::SubtractGreen as u32, 2);
}
w.write_bit(false);
write_spatially_coded_image(&mut w, tokens, color_cache_code_bits, image_width);
w.into_bytes()
}
fn write_spatially_coded_image(
w: &mut BitWriter,
tokens: &[Token],
color_cache_code_bits: Option<u32>,
image_width: u32,
) {
let color_cache_size = match color_cache_code_bits {
Some(bits) => {
debug_assert!((COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).contains(&bits));
w.write_bit(true);
w.write_bits(bits, 4);
1usize << bits
}
None => {
w.write_bit(false);
0
}
};
w.write_bit(false);
write_prefix_codes_and_tokens(w, tokens, color_cache_size, image_width);
}
fn write_entropy_coded_image_literals(w: &mut BitWriter, pixels: &[u32]) {
w.write_bit(false);
let tokens: Vec<Token> = pixels.iter().map(|&p| Token::Literal(p)).collect();
write_prefix_codes_and_tokens(w, &tokens, 0, 1);
}
fn write_prefix_codes_and_tokens(
w: &mut BitWriter,
tokens: &[Token],
color_cache_size: usize,
image_width: u32,
) {
let freqs = count_frequencies(tokens, color_cache_size, image_width);
let green_code = WriteCode::from_freqs(&freqs.green);
let red_code = WriteCode::from_freqs(&freqs.red);
let blue_code = WriteCode::from_freqs(&freqs.blue);
let alpha_code = WriteCode::from_freqs(&freqs.alpha);
let dist_code = if freqs.distance.iter().any(|&f| f > 0) {
WriteCode::from_freqs(&freqs.distance)
} else {
WriteCode::empty(40)
};
green_code.write_code_lengths(w);
red_code.write_code_lengths(w);
blue_code.write_code_lengths(w);
alpha_code.write_code_lengths(w);
dist_code.write_code_lengths(w);
for &tok in tokens {
match tok {
Token::Literal(p) => {
let a = ((p >> 24) & 0xff) as usize;
let r = ((p >> 16) & 0xff) as usize;
let g = ((p >> 8) & 0xff) as usize;
let b = (p & 0xff) as usize;
green_code.write_symbol(w, g);
red_code.write_symbol(w, r);
blue_code.write_symbol(w, b);
alpha_code.write_symbol(w, a);
}
Token::CacheRef { index } => {
debug_assert!(color_cache_size > 0, "CacheRef requires an enabled cache");
let sym = 256 + crate::vp8l_decode::NUM_LENGTH_PREFIX_CODES + index as usize;
green_code.write_symbol(w, sym);
}
Token::Copy { length, distance } => {
write_lz77_value(w, &green_code, 256, length as u32);
let raw_code = pixel_distance_to_distance_code(distance, image_width);
write_lz77_value(w, &dist_code, 0, raw_code);
}
}
}
}
fn build_image_header(width: u32, height: u32, alpha_is_used: bool) -> [u8; 5] {
let packed: u32 =
((width - 1) & 0x3FFF) | (((height - 1) & 0x3FFF) << 14) | ((alpha_is_used as u32) << 28);
[
crate::vp8l_chunk::VP8L_SIGNATURE,
(packed & 0xFF) as u8,
((packed >> 8) & 0xFF) as u8,
((packed >> 16) & 0xFF) as u8,
((packed >> 24) & 0xFF) as u8,
]
}
pub fn encode_webp_lossless(rgba: &[u8], width: u32, height: u32) -> Result<Vec<u8>, EncodeError> {
if width == 0 || height == 0 || width > MAX_DIMENSION || height > MAX_DIMENSION {
return Err(EncodeError::InvalidDimensions { width, height });
}
let expected = (width as usize) * (height as usize) * 4;
if rgba.len() != expected {
return Err(EncodeError::PixelBufferMismatch {
got: rgba.len(),
expected,
});
}
let mut pixels = Vec::with_capacity(rgba.len() / 4);
let mut alpha_is_used = false;
for px in rgba.chunks_exact(4) {
let (r, g, b, a) = (px[0] as u32, px[1] as u32, px[2] as u32, px[3] as u32);
if a != 0xff {
alpha_is_used = true;
}
pixels.push((a << 24) | (r << 16) | (g << 8) | b);
}
let payload = encode_vp8l_payload(&pixels, width, height, alpha_is_used);
let file = build::build_webp_file(&payload, ImageKind::Lossless, width, height)?;
Ok(file)
}
fn validate_argb(pixels: &[u32], width: u32, height: u32) -> Result<(), EncodeError> {
if width == 0 || height == 0 || width > MAX_DIMENSION || height > MAX_DIMENSION {
return Err(EncodeError::InvalidDimensions { width, height });
}
let expected = (width as usize) * (height as usize);
if pixels.len() != expected {
return Err(EncodeError::PixelBufferMismatch {
got: pixels.len() * 4,
expected: expected * 4,
});
}
Ok(())
}
fn encode_vp8l_payload(pixels: &[u32], width: u32, height: u32, alpha_is_used: bool) -> Vec<u8> {
let stream = encode_argb_with_predictor_chooser(pixels, width, height);
let header = build_image_header(width, height, alpha_is_used);
let mut payload = Vec::with_capacity(header.len() + stream.len());
payload.extend_from_slice(&header);
payload.extend_from_slice(&stream);
payload
}
fn encode_argb_with_predictor_chooser(pixels: &[u32], width: u32, height: u32) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let mut pred_single_block_size_bits: u8 = pred_size_bits;
while pred_single_block_size_bits < 9
&& ((1u32 << pred_single_block_size_bits) < width
|| (1u32 << pred_single_block_size_bits) < height)
{
pred_single_block_size_bits += 1;
}
let try_pred_single_block = pred_single_block_size_bits != pred_size_bits;
let mut pred_candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_predictor(pixels, width, height, pred_size_bits, cache_bits, width)
})];
let pred_block_pixels: u64 = (1u64 << pred_size_bits) * (1u64 << pred_size_bits);
for slack in [
pred_block_pixels,
2 * pred_block_pixels,
4 * pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
slack,
)
}));
}
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_entropy(pixels, width, height, pred_size_bits, cache_bits, width)
}));
for lambda_milli in [4_000u64, 16_000u64, 64_000u64, 256_000u64] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_entropy_subaware(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
lambda_milli,
)
}));
}
if try_pred_single_block {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
let single_pred_block_pixels: u64 =
(1u64 << pred_single_block_size_bits) * (1u64 << pred_single_block_size_bits);
for slack in [
single_pred_block_pixels,
2 * single_pred_block_pixels,
4 * single_pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
slack,
)
}));
}
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_entropy(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in pred_candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
fn sweep_meta_prefix_candidate(pixels: &[u32], width: u32, height: u32) -> Option<Vec<u8>> {
let mut best: Option<Vec<u8>> = None;
for &prefix_bits in META_PREFIX_BITS_SWEEP.iter() {
for num_groups in 2..=MAX_META_GROUPS {
let mut shape_best: Option<Vec<u8>> = None;
for cache_opt in
std::iter::once(None).chain((COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).map(Some))
{
if let Some(cand) = encode_with_meta_prefix(
pixels,
width,
height,
prefix_bits,
num_groups,
cache_opt,
width,
) {
match &shape_best {
Some(s) if s.len() <= cand.len() => {}
_ => shape_best = Some(cand),
}
}
}
if let Some(cand) = shape_best {
match &best {
Some(b) if b.len() <= cand.len() => {}
_ => best = Some(cand),
}
}
}
}
best
}
pub fn encode_vp8l_argb(pixels: &[u32], width: u32, height: u32) -> Result<Vec<u8>, EncodeError> {
let alpha_is_used = pixels.iter().any(|&p| (p >> 24) & 0xff != 0xff);
encode_vp8l_argb_with(pixels, width, height, alpha_is_used)
}
pub fn encode_vp8l_argb_with(
pixels: &[u32],
width: u32,
height: u32,
alpha_is_used: bool,
) -> Result<Vec<u8>, EncodeError> {
validate_argb(pixels, width, height)?;
Ok(encode_vp8l_payload(pixels, width, height, alpha_is_used))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::vp8l_prefix::PrefixCode;
use crate::vp8l_stream::BitReader;
#[test]
fn bit_writer_round_trips_through_bit_reader() {
let mut w = BitWriter::new();
w.write_bits(0b101, 3);
w.write_bits(0xABCD, 16);
w.write_bit(true);
let bytes = w.into_bytes();
let mut r = BitReader::new(&bytes);
assert_eq!(r.read_bits(3).unwrap(), 0b101);
assert_eq!(r.read_bits(16).unwrap(), 0xABCD);
assert!(r.read_bit().unwrap());
}
#[test]
fn code_lengths_single_symbol_is_length_one() {
let mut freq = vec![0u32; 8];
freq[3] = 10;
let lengths = build_code_lengths(&freq);
assert_eq!(lengths[3], 1);
assert_eq!(lengths.iter().filter(|&&l| l != 0).count(), 1);
}
#[test]
fn code_lengths_two_symbols_length_one_each() {
let mut freq = vec![0u32; 4];
freq[1] = 5;
freq[2] = 5;
let lengths = build_code_lengths(&freq);
assert_eq!(lengths[1], 1);
assert_eq!(lengths[2], 1);
}
#[test]
fn code_lengths_kraft_sum_is_one() {
let freq = vec![100u32, 1, 1, 1, 50, 25, 4, 2];
let lengths = build_code_lengths(&freq);
let mut k = 0f64;
for &l in &lengths {
if l > 0 {
k += 2f64.powi(-(l as i32));
}
}
assert!((k - 1.0).abs() < 1e-9, "Kraft sum {k} != 1");
}
#[test]
fn built_code_decodes_through_prefix_reader() {
let freq = vec![40u32, 10, 5, 5, 1, 0, 0, 0];
let code = WriteCode::from_freqs(&freq);
let mut w = BitWriter::new();
code.write_code_lengths(&mut w);
let seq = [0usize, 1, 2, 3, 4, 0, 0, 1];
for &s in &seq {
code.write_symbol(&mut w, s);
}
let bytes = w.into_bytes();
let mut r = BitReader::new(&bytes);
let decoded = PrefixCode::read(&mut r, freq.len()).unwrap();
for &s in &seq {
assert_eq!(decoded.read_symbol(&mut r).unwrap() as usize, s);
}
}
#[test]
fn empty_distance_code_is_single_symbol_zero() {
let code = WriteCode::empty(40);
let mut w = BitWriter::new();
code.write_code_lengths(&mut w);
let bytes = w.into_bytes();
let mut r = BitReader::new(&bytes);
let decoded = PrefixCode::read(&mut r, 40).unwrap();
assert_eq!(decoded.single_symbol(), Some(0));
}
#[test]
fn simple_form_rejects_tables_outside_3_7_2_1_1_constraints() {
let mut freq = vec![0u32; 8];
freq[0] = 1;
freq[1] = 1;
freq[2] = 1;
let three_sym = WriteCode::from_freqs(&freq);
assert!(three_sym.as_simple_form().is_none());
let lengths_empty = vec![0u8; 16];
let codes_empty = canonical_codes(&lengths_empty);
let empty_code = WriteCode {
lengths: lengths_empty,
codes: codes_empty,
single: None,
};
assert!(empty_code.as_simple_form().is_none());
let mut freq_big = vec![0u32; 300];
freq_big[280] = 1;
let beyond_255 = WriteCode::from_freqs(&freq_big);
assert!(beyond_255.as_simple_form().is_none());
let mixed_lengths = vec![0u8, 2, 2, 1];
let mixed_codes = canonical_codes(&mixed_lengths);
let mixed = WriteCode {
lengths: mixed_lengths,
codes: mixed_codes,
single: None,
};
assert!(mixed.as_simple_form().is_none());
}
#[test]
fn simple_form_accepts_one_or_two_length_one_symbols() {
let mut freq1 = vec![0u32; 16];
freq1[7] = 1;
let one = WriteCode::from_freqs(&freq1);
assert_eq!(one.as_simple_form(), Some(vec![7]));
let mut freq2 = vec![0u32; 16];
freq2[3] = 4;
freq2[12] = 4;
let two = WriteCode::from_freqs(&freq2);
assert_eq!(two.as_simple_form(), Some(vec![3, 12]));
}
#[test]
fn simple_form_bits_matches_written_layout() {
assert_eq!(simple_form_bits(&[1]), 4);
assert_eq!(simple_form_bits(&[7]), 11);
assert_eq!(simple_form_bits(&[0, 50]), 12);
assert_eq!(simple_form_bits(&[200, 100]), 19);
let mut w = BitWriter::new();
write_simple_code_lengths(&mut w, &[200, 100]);
let pos_bits = w.bit_position();
assert_eq!(pos_bits, 19);
}
#[test]
fn chooser_prefers_simple_form_for_empty_distance_code() {
let code = WriteCode::empty(40);
let normal_bits = normal_form_bits(&code.lengths);
let simple = code.as_simple_form().expect("empty(40) is simple-form");
let simple_bits = simple_form_bits(&simple);
assert!(
simple_bits < normal_bits,
"expected simple form (= {simple_bits} bits) to beat normal form (= {normal_bits} bits) for empty distance code"
);
let mut w = BitWriter::new();
code.write_code_lengths(&mut w);
let bytes = w.into_bytes();
let mut r = BitReader::new(&bytes);
assert!(
r.read_bit().expect("flag bit"),
"chooser must select simple form (flag bit = 1) for the empty distance code"
);
}
#[test]
fn chooser_round_trips_through_decoder_on_both_branches() {
let mut freq = vec![0u32; 16];
freq[9] = 7;
let code1 = WriteCode::from_freqs(&freq);
let mut w1 = BitWriter::new();
code1.write_code_lengths(&mut w1);
let bytes1 = w1.into_bytes();
let mut r1 = BitReader::new(&bytes1);
let decoded1 = PrefixCode::read(&mut r1, 16).expect("decode simple form");
assert_eq!(
decoded1.single_symbol(),
Some(9),
"decoder must recover the single-leaf symbol from the simple form"
);
let freq4 = vec![10u32, 4, 2, 1, 0, 0, 0, 0];
let code4 = WriteCode::from_freqs(&freq4);
let mut w4 = BitWriter::new();
code4.write_code_lengths(&mut w4);
let seq = [0usize, 1, 2, 3, 0, 0, 1, 2];
for &s in &seq {
code4.write_symbol(&mut w4, s);
}
let bytes4 = w4.into_bytes();
let mut r4 = BitReader::new(&bytes4);
let decoded4 = PrefixCode::read(&mut r4, 8).expect("decode normal form");
for &s in &seq {
assert_eq!(
decoded4.read_symbol(&mut r4).expect("symbol") as usize,
s,
"round-trip mismatch on normal-form code"
);
}
}
#[test]
fn round_149_simple_form_shrinks_1x1_lossless_baseline() {
let rgba = [0x12, 0x34, 0x56, 0xff];
let file = encode_webp_lossless(&rgba, 1, 1).unwrap();
eprintln!("round-149 1x1 lossless byte count: {}", file.len());
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
assert!(
file.len() <= 48,
"expected round-149 simple-form chooser to bring the 1×1 baseline well under the round-148 174-byte size; got {}",
file.len()
);
}
#[test]
fn round_149_simple_form_shrinks_synthetic_fixtures() {
let mut solid = Vec::new();
for _ in 0..1024 {
solid.extend_from_slice(&[0x80, 0x80, 0x80, 0xff]);
}
let file_solid = encode_webp_lossless(&solid, 32, 32).unwrap();
eprintln!("round-149 32×32 solid: {}", file_solid.len());
assert!(
file_solid.len() <= 100,
"round-149 32×32 solid should land far below the round-148 174-byte size; got {}",
file_solid.len()
);
let mut alpha = Vec::new();
for y in 0..8u32 {
for x in 0..8u32 {
let a = if (x + y) % 2 == 0 { 0xff } else { 0x80 };
alpha.extend_from_slice(&[0x44, 0x88, 0xcc, a]);
}
}
let file_alpha = encode_webp_lossless(&alpha, 8, 8).unwrap();
eprintln!("round-149 8×8 alpha: {}", file_alpha.len());
assert!(
file_alpha.len() <= 110,
"round-149 8×8 alpha should land below the round-148 178-byte size; got {}",
file_alpha.len()
);
let decoded_solid = crate::decode_webp(&file_solid).unwrap();
assert_eq!(decoded_solid.frames[0].rgba, solid);
let decoded_alpha = crate::decode_webp(&file_alpha).unwrap();
assert_eq!(decoded_alpha.frames[0].rgba, alpha);
}
#[test]
fn round_149_two_symbol_simple_form_round_trips() {
let mut freq = vec![0u32; 16];
freq[2] = 5;
freq[11] = 5;
let code = WriteCode::from_freqs(&freq);
assert_eq!(code.as_simple_form(), Some(vec![2, 11]));
let normal_bits = normal_form_bits(&code.lengths);
let simple_bits = simple_form_bits(&[2, 11]);
eprintln!(
"2-symbol code: simple={} bits, normal={} bits",
simple_bits, normal_bits
);
let mut w = BitWriter::new();
code.write_code_lengths(&mut w);
for _ in 0..3 {
code.write_symbol(&mut w, 2);
code.write_symbol(&mut w, 11);
}
let bytes = w.into_bytes();
let mut r = BitReader::new(&bytes);
let decoded = PrefixCode::read(&mut r, 16).expect("decode chooser output");
for _ in 0..3 {
assert_eq!(decoded.read_symbol(&mut r).unwrap() as usize, 2);
assert_eq!(decoded.read_symbol(&mut r).unwrap() as usize, 11);
}
}
#[test]
fn image_header_round_trips_through_chunk_peek() {
use crate::vp8l_chunk::WebpLosslessChunk;
let header = build_image_header(7, 5, true);
let mut payload = header.to_vec();
payload.push(0);
let h = WebpLosslessChunk::from_payload(&payload).unwrap();
assert_eq!(h.width(), 7);
assert_eq!(h.height(), 5);
assert!(h.alpha_is_used());
assert_eq!(h.version(), 0);
}
#[test]
fn round_trip_1x1_opaque() {
let rgba = [0x12, 0x34, 0x56, 0xff];
let file = encode_webp_lossless(&rgba, 1, 1).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn round_trip_1x1_with_alpha() {
let rgba = [0xaa, 0xbb, 0xcc, 0x40];
let file = encode_webp_lossless(&rgba, 1, 1).unwrap();
let img = crate::decode_webp_image(&file).unwrap();
assert_eq!(img.width, 1);
assert_eq!(img.height, 1);
assert_eq!(img.rgba, rgba);
}
#[test]
fn round_trip_small_gradient() {
let w = 4u32;
let h = 3u32;
let mut rgba = Vec::new();
for y in 0..h {
for x in 0..w {
rgba.push((x * 60) as u8);
rgba.push((y * 80) as u8);
rgba.push(((x + y) * 30) as u8);
rgba.push(0xff);
}
}
let file = encode_webp_lossless(&rgba, w, h).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn round_trip_solid_color_uses_single_leaf_codes() {
let w = 8u32;
let h = 8u32;
let mut rgba = Vec::new();
for _ in 0..(w * h) {
rgba.extend_from_slice(&[0x20, 0x40, 0x60, 0xff]);
}
let file = encode_webp_lossless(&rgba, w, h).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn round_trip_larger_random_like() {
let w = 16u32;
let h = 16u32;
let mut rgba = Vec::new();
let mut state = 0x1234_5678u32;
for _ in 0..(w * h) {
for _ in 0..4 {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
rgba.push((state & 0xff) as u8);
}
}
let file = encode_webp_lossless(&rgba, w, h).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn encoded_file_walks_as_simple_lossless_container() {
let rgba = [0x12, 0x34, 0x56, 0xff];
let file = encode_webp_lossless(&rgba, 1, 1).unwrap();
let c = crate::parse_container(&file).unwrap();
assert!(c
.first_chunk_with_fourcc(crate::container::fourcc::VP8L)
.is_some());
}
#[test]
fn rejects_dimension_mismatch() {
let rgba = [0u8; 4]; match encode_webp_lossless(&rgba, 2, 2) {
Err(EncodeError::PixelBufferMismatch { got, expected }) => {
assert_eq!(got, 4);
assert_eq!(expected, 16);
}
other => panic!("expected PixelBufferMismatch, got {other:?}"),
}
}
#[test]
fn rejects_zero_dimensions() {
match encode_webp_lossless(&[], 0, 0) {
Err(EncodeError::InvalidDimensions { width, height }) => {
assert_eq!(width, 0);
assert_eq!(height, 0);
}
other => panic!("expected InvalidDimensions, got {other:?}"),
}
}
#[test]
fn bare_bitstream_wrapped_equals_framed_file() {
let pixels: [u32; 6] = [
0xff10_2030,
0xff40_5060,
0x8070_8090,
0xffa0_b0c0,
0xffd0_e0f0,
0xff00_1122,
];
let bare = encode_vp8l_argb(&pixels, 3, 2).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, 3, 2).unwrap();
let mut rgba = Vec::new();
for &p in &pixels {
rgba.push((p >> 16) as u8);
rgba.push((p >> 8) as u8);
rgba.push(p as u8);
rgba.push((p >> 24) as u8);
}
let via_rgba = encode_webp_lossless(&rgba, 3, 2).unwrap();
assert_eq!(framed, via_rgba);
}
#[test]
fn bare_bitstream_has_no_riff_wrapper() {
let pixels = [0xff12_3456u32];
let bare = encode_vp8l_argb(&pixels, 1, 1).unwrap();
assert_ne!(&bare[0..4], b"RIFF");
assert_eq!(bare[0], crate::vp8l_chunk::VP8L_SIGNATURE);
}
#[test]
fn bare_bitstream_auto_detects_alpha() {
let opaque = [0xff11_2233u32, 0xff44_5566];
let bare = encode_vp8l_argb(&opaque, 2, 1).unwrap();
let h = crate::vp8l_chunk::WebpLosslessChunk::from_payload(&bare).unwrap();
assert!(!h.alpha_is_used());
let translucent = [0x8011_2233u32, 0xff44_5566];
let bare = encode_vp8l_argb(&translucent, 2, 1).unwrap();
let h = crate::vp8l_chunk::WebpLosslessChunk::from_payload(&bare).unwrap();
assert!(h.alpha_is_used());
}
#[test]
fn bare_bitstream_with_forces_alpha_bit() {
let opaque = [0xff11_2233u32];
let bare = encode_vp8l_argb_with(&opaque, 1, 1, true).unwrap();
let h = crate::vp8l_chunk::WebpLosslessChunk::from_payload(&bare).unwrap();
assert!(h.alpha_is_used());
}
#[test]
fn bare_bitstream_round_trips() {
let pixels: [u32; 4] = [0x80aa_bbcc, 0xff00_1122, 0xc033_4455, 0xff66_7788];
let bare = encode_vp8l_argb(&pixels, 2, 2).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, 2, 2).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), &pixels);
}
#[test]
fn bare_bitstream_rejects_dimension_mismatch() {
let pixels = [0xff00_0000u32]; match encode_vp8l_argb(&pixels, 2, 2) {
Err(EncodeError::PixelBufferMismatch { got, expected }) => {
assert_eq!(got, 4);
assert_eq!(expected, 16);
}
other => panic!("expected PixelBufferMismatch, got {other:?}"),
}
}
#[test]
fn value_to_prefix_small_values_have_no_extra_bits() {
for v in 1u32..=4 {
let (p, e, x) = value_to_prefix(v);
assert_eq!(p, v - 1);
assert_eq!(e, 0);
assert_eq!(x, 0);
}
}
#[test]
fn value_to_prefix_round_trips_length_range() {
for v in 1u32..=MAX_MATCH as u32 {
let (p, e, x) = value_to_prefix(v);
let recovered = if p < 4 {
p + 1
} else {
let extra_bits = (p - 2) >> 1;
let offset = (2 + (p & 1)) << extra_bits;
assert_eq!(extra_bits, e);
offset + x + 1
};
assert_eq!(recovered, v, "value_to_prefix lost value {v}");
}
}
#[test]
fn value_to_prefix_round_trips_through_decoder() {
use crate::vp8l_decode::read_lz77_value;
use crate::vp8l_stream::BitReader;
let samples = [
1u32, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 16, 17, 24, 25, 32, 100, 1000, 4096,
];
for &v in &samples {
let (p, e, x) = value_to_prefix(v);
let mut w = BitWriter::new();
if e > 0 {
w.write_bits(x, e as usize);
}
let data = w.into_bytes();
let mut r = BitReader::new(&data);
let got = read_lz77_value(&mut r, p).unwrap();
assert_eq!(
got, v,
"value {v} → prefix {p}, extra ({e}b: {x:b}) decoded as {got}"
);
}
}
#[test]
fn round_trip_solid_color_uses_lz77_copy() {
let w = 32u32;
let h = 32u32;
let pixels = vec![0xff20_4060u32; (w * h) as usize];
let tokens = tokenize_lz77(&pixels);
let copies = tokens
.iter()
.filter(|t| matches!(t, Token::Copy { .. }))
.count();
assert!(
copies >= 1,
"solid-color image should emit at least one copy"
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_trip_periodic_pattern_uses_overlapping_copy() {
let pattern = [0xff10_2030u32, 0xff40_5060, 0xff70_8090, 0xffa0_b0c0];
let w = 16u32;
let h = 4u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
for i in 0..(w * h) {
pixels.push(pattern[(i % 4) as usize]);
}
let tokens = tokenize_lz77(&pixels);
let copies: Vec<_> = tokens
.iter()
.filter_map(|t| match t {
Token::Copy { length, distance } => Some((*length, *distance)),
_ => None,
})
.collect();
assert!(!copies.is_empty(), "periodic pattern should emit a copy");
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn lz77_beats_literal_only_on_repetitive_image() {
let w = 64u32;
let h = 64u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let palette = [
0xff10_2030u32,
0xff40_5060,
0xff70_8090,
0xffa0_b0c0,
0xffd0_e0f0,
0xff00_1122,
0xff33_4455,
0xff66_7788,
];
for x in 0..w {
pixels.push(palette[(x as usize) % palette.len()]);
}
for _ in 1..h {
for x in 0..w {
pixels.push(palette[(x as usize) % palette.len()]);
}
}
let lz77 = encode_argb_literals(&pixels);
let lit_only = encode_argb_literals_only(&pixels);
assert!(
lz77.len() < lit_only.len(),
"LZ77 stream ({} B) not smaller than literal-only ({} B)",
lz77.len(),
lit_only.len(),
);
assert!(
lz77.len() * 2 < lit_only.len(),
"LZ77 stream ({} B) failed to halve literal-only ({} B)",
lz77.len(),
lit_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn lz77_round_trips_incompressible_pixels() {
let w = 17u32;
let h = 19u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xdead_beefu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(state);
}
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn apply_subtract_green_is_inverse_of_inverse_subtract_green() {
let mut pixels = [
0xff00_0000u32, 0xff7f_ff00, 0xffff_ffff, 0x8012_3456, 0x0001_0203, ];
let original = pixels;
apply_subtract_green(&mut pixels);
crate::vp8l_transform::inverse_subtract_green(&mut pixels);
assert_eq!(pixels, original);
}
#[test]
fn apply_subtract_green_only_touches_red_and_blue() {
let mut pixels = [0x80_70_60_50u32]; apply_subtract_green(&mut pixels);
assert_eq!((pixels[0] >> 24) & 0xff, 0x80);
assert_eq!((pixels[0] >> 16) & 0xff, 0x10);
assert_eq!((pixels[0] >> 8) & 0xff, 0x60);
assert_eq!(pixels[0] & 0xff, 0xf0); }
#[test]
fn subtract_green_beats_no_transform_on_green_correlated_image() {
let w = 32u32;
let h = 32u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xC0FFEE12u32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
let g = state & 0xff;
let r = g.wrapping_add(((state >> 8) & 0x0f).wrapping_sub(7) & 0xff) & 0xff;
let b = g.wrapping_add(((state >> 16) & 0x0f).wrapping_sub(7) & 0xff) & 0xff;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
let no_tx = {
let tokens = tokenize_lz77(&pixels);
encode_tokens(&tokens, false, None, 1)
};
let sg = encode_argb_literals_subtract_green(&pixels);
eprintln!(
"[round-120] 32x32 green-correlated: no-tx={} B, subtract-green={} B ({:.1}% reduction)",
no_tx.len(),
sg.len(),
100.0 * (no_tx.len() as f64 - sg.len() as f64) / no_tx.len() as f64,
);
assert!(
sg.len() < no_tx.len(),
"subtract-green ({} B) did not beat no-transform ({} B)",
sg.len(),
no_tx.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn encode_argb_literals_chooses_smaller_path() {
let w = 32u32;
let h = 32u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0x12345678u32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
let g = 0x80u32;
let r = g.wrapping_add((state & 0x0f).wrapping_sub(7) & 0xff) & 0xff;
let b = g.wrapping_add(((state >> 4) & 0x0f).wrapping_sub(7) & 0xff) & 0xff;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
let chosen = encode_argb_literals(&pixels);
let no_tx = encode_literals_with_options(&pixels, false, None, 1);
let sg = encode_literals_with_options(&pixels, true, None, 1);
let cc = encode_literals_with_options(&pixels, false, Some(DEFAULT_COLOR_CACHE_BITS), 1);
let sg_cc = encode_literals_with_options(&pixels, true, Some(DEFAULT_COLOR_CACHE_BITS), 1);
let best = no_tx.len().min(sg.len()).min(cc.len()).min(sg_cc.len());
assert_eq!(chosen.len(), best);
}
#[test]
fn subtract_green_path_round_trips_via_public_entry_points() {
let w = 8u32;
let h = 8u32;
let pixels: Vec<u32> = (0..(w * h))
.map(|i| {
let g = (i * 4) & 0xff;
let r = g.wrapping_add(3) & 0xff;
let b = g.wrapping_sub(2) & 0xff;
0xff00_0000 | (r << 16) | (g << 8) | b
})
.collect();
let stream = encode_argb_literals_subtract_green(&pixels);
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn encode_argb_literals_does_not_regress_on_uncorrelated_noise() {
let w = 16u32;
let h = 16u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xDEAD_BEEFu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(state | 0xff00_0000);
}
let chosen = encode_argb_literals(&pixels);
let no_tx = {
let tokens = tokenize_lz77(&pixels);
encode_tokens(&tokens, false, None, 1)
};
assert!(
chosen.len() <= no_tx.len(),
"chooser regressed: {} B with chooser vs {} B no-transform",
chosen.len(),
no_tx.len(),
);
}
#[test]
fn round_trip_splits_match_at_max_length() {
let total = MAX_MATCH + 100;
let pixels = vec![0xff80_8080u32; total];
let tokens = tokenize_lz77(&pixels);
for tok in &tokens {
if let Token::Copy { length, .. } = tok {
assert!(
*length <= MAX_MATCH,
"copy length {length} exceeded MAX_MATCH"
);
}
}
let w = total as u32;
let h = 1u32;
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn encoder_color_cache_hash_matches_decoder_hash() {
use crate::vp8l_decode::ColorCache;
for bits in COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX {
let enc = EncoderColorCache::new(bits);
let dec = ColorCache::new(bits);
for argb in [
0x0000_0000u32,
0xffff_ffff,
0x0102_0304,
0xffff_0000,
0x8000_ff80,
0x1234_5678,
] {
assert_eq!(
enc.hash(argb),
dec.hash(argb),
"hash mismatch at code_bits={bits} for argb=0x{argb:08x}"
);
}
assert_eq!(enc.size(), 1 << bits);
}
}
#[test]
fn encoder_color_cache_starts_zero_initialized() {
let cache = EncoderColorCache::new(4);
let zero_idx = cache.hash(0);
assert_eq!(cache.entries[zero_idx], 0);
assert_eq!(cache.contains(0), Some(zero_idx));
}
#[test]
fn encoder_color_cache_insert_then_contains_round_trips() {
let mut cache = EncoderColorCache::new(8);
let argb = 0xff12_3456u32;
assert!(cache.contains(argb).is_none() || cache.entries[cache.hash(argb)] != argb);
cache.insert(argb);
assert_eq!(cache.contains(argb), Some(cache.hash(argb)));
}
#[test]
fn cacheify_tokens_collapses_repeat_literal_into_cache_ref() {
let argb = 0xff20_4060u32;
let pixels = vec![argb, argb];
let raw = vec![Token::Literal(argb), Token::Literal(argb)];
let out = cacheify_tokens(&raw, &pixels, 8);
assert!(matches!(out[0], Token::Literal(p) if p == argb));
let cache = EncoderColorCache::new(8);
let idx = cache.hash(argb) as u32;
assert_eq!(out[1], Token::CacheRef { index: idx });
}
#[test]
fn cacheify_tokens_copy_updates_cache_for_subsequent_literal() {
let argb = 0xff80_4010u32;
let pixels = vec![argb, argb, argb, argb, argb];
let raw = vec![
Token::Literal(argb),
Token::Copy {
length: 3,
distance: 1,
},
Token::Literal(argb),
];
let out = cacheify_tokens(&raw, &pixels, 8);
assert!(matches!(out[0], Token::Literal(p) if p == argb));
assert!(matches!(
out[1],
Token::Copy {
length: 3,
distance: 1,
}
));
let cache = EncoderColorCache::new(8);
let idx = cache.hash(argb) as u32;
assert_eq!(out[2], Token::CacheRef { index: idx });
}
#[test]
fn color_cache_path_round_trips_via_public_entry_points() {
let w = 8u32;
let h = 8u32;
let palette: [u32; 16] = [
0xff00_0000,
0xff00_00ff,
0xff00_ff00,
0xff00_ffff,
0xffff_0000,
0xffff_00ff,
0xffff_ff00,
0xffff_ffff,
0xff80_8080,
0xff20_4060,
0xff60_4020,
0xff10_2030,
0xff30_2010,
0xffa0_b0c0,
0xffc0_b0a0,
0xff55_aa55,
];
let pixels: Vec<u32> = (0..(w * h))
.map(|i| palette[(i as usize) % palette.len()])
.collect();
let stream = encode_argb_literals_color_cache(&pixels, DEFAULT_COLOR_CACHE_BITS);
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn color_cache_beats_no_cache_on_small_palette_image() {
let w = 32u32;
let h = 32u32;
let palette: [u32; 8] = [
0xff10_2030,
0xff40_5060,
0xff70_8090,
0xffa0_b0c0,
0xffd0_e0f0,
0xff00_1122,
0xff33_4455,
0xff66_7788,
];
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0x1357_9bdfu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(palette[(state as usize) % palette.len()]);
}
let no_cache = encode_literals_with_options(&pixels, false, None, 1);
let cache = encode_literals_with_options(&pixels, false, Some(DEFAULT_COLOR_CACHE_BITS), 1);
eprintln!(
"[round-121] 32x32 small-palette pseudo-random: no-cache={} B, color-cache={} B ({:.1}% reduction)",
no_cache.len(),
cache.len(),
100.0 * (no_cache.len() as f64 - cache.len() as f64) / no_cache.len() as f64,
);
assert!(
cache.len() < no_cache.len(),
"color-cache stream ({} B) did not beat no-cache LZ77 ({} B)",
cache.len(),
no_cache.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn color_cache_chooser_does_not_regress_on_uncorrelated_noise() {
let w = 16u32;
let h = 16u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xfeed_b00bu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(state | 0xff00_0000);
}
let chosen = encode_argb_literals(&pixels);
let no_cache_no_tx = encode_literals_with_options(&pixels, false, None, 1);
assert!(
chosen.len() <= no_cache_no_tx.len(),
"chooser regressed on noise: {} B chosen vs {} B no-cache no-tx",
chosen.len(),
no_cache_no_tx.len(),
);
}
#[test]
fn color_cache_header_round_trips_through_meta_prefix_reader() {
use crate::meta_prefix::{ImageRole, MetaPrefixHeader};
use crate::vp8l_stream::BitReader;
let w = 4u32;
let h = 4u32;
let palette = [0xff10_2030u32, 0xff40_5060, 0xff70_8090, 0xffa0_b0c0];
let pixels: Vec<u32> = (0..(w * h))
.map(|i| palette[(i as usize) % palette.len()])
.collect();
let stream = encode_argb_literals_color_cache(&pixels, DEFAULT_COLOR_CACHE_BITS);
let mut r = BitReader::new(&stream);
assert!(!r.read_bit().unwrap());
let header = MetaPrefixHeader::read(&mut r, ImageRole::Argb, w, h).unwrap();
assert!(header.color_cache.is_enabled());
assert_eq!(header.color_cache.code_bits, DEFAULT_COLOR_CACHE_BITS);
assert_eq!(header.color_cache.size(), 1 << DEFAULT_COLOR_CACHE_BITS);
}
#[test]
fn distance_chooser_reconstructs_each_distance_map_entry() {
use crate::vp8l_decode::{distance_code_to_pixel_distance, DISTANCE_MAP};
let width = 256u32;
for &(xi, yi) in DISTANCE_MAP.iter() {
let raw = xi + yi * width as i32;
let d = if raw < 1 { 1 } else { raw as usize };
let code = pixel_distance_to_distance_code(d, width);
assert_eq!(
distance_code_to_pixel_distance(code, width),
d,
"chooser code {code} for d={d} (xi={xi},yi={yi}) does not round-trip",
);
}
}
#[test]
fn distance_chooser_picks_map_code_for_row_distance() {
let width = 256u32;
let code = pixel_distance_to_distance_code(width as usize, width);
assert_eq!(code, 1, "row distance must collapse to map code 1");
assert_eq!(distance_to_code(width as usize), width + 120);
}
#[test]
fn distance_chooser_falls_back_to_scan_line_when_no_map_match() {
let width = 256u32;
let code = pixel_distance_to_distance_code(1000, width);
assert_eq!(code, 1000 + 120);
}
#[test]
fn distance_chooser_width_one_uses_scan_line_for_large_distances() {
for d in [16usize, 32, 64, 100, 500] {
assert_eq!(
pixel_distance_to_distance_code(d, 1),
(d as u32) + 120,
"width=1 distance {d} should not collapse",
);
}
}
#[test]
fn width_aware_distance_beats_scan_line_only_on_row_correlated_image() {
let w = 128u32;
let h = 128u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xC0DE_FACEu32;
for _ in 0..w {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push((state & 0x00ff_ffff) | 0xff00_0000);
}
for y in 1..h {
for x in 0..w {
pixels.push(pixels[(x + (y - 1) * w) as usize]);
}
}
let width_aware = encode_argb_literals_with_width(&pixels, w);
let scan_line_only = encode_argb_literals(&pixels);
eprintln!(
"[round-130] 128x128 row-correlated: scan-line-only={} B, width-aware={} B ({:.1}% reduction)",
scan_line_only.len(),
width_aware.len(),
100.0 * (scan_line_only.len() as f64 - width_aware.len() as f64)
/ scan_line_only.len() as f64,
);
assert!(
width_aware.len() < scan_line_only.len(),
"width-aware stream ({} B) not smaller than scan-line-only ({} B)",
width_aware.len(),
scan_line_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn width_aware_distance_beats_scan_line_only_on_photo_like_image() {
let w = 64u32;
let h = 64u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0x1234_5678u32;
for y in 0..h {
let luma = (y * 4) as u8;
for _x in 0..w {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
let n = (state & 0x07) as i32 - 3; let g = (luma as i32 + n).clamp(0, 255) as u32;
let r = g;
let b = g;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let width_aware = encode_argb_literals_with_width(&pixels, w);
let scan_line_only = encode_argb_literals(&pixels);
eprintln!(
"[round-130] 64x64 photo-like: scan-line-only={} B, width-aware={} B ({:.1}% reduction)",
scan_line_only.len(),
width_aware.len(),
100.0 * (scan_line_only.len() as f64 - width_aware.len() as f64)
/ scan_line_only.len() as f64,
);
assert!(
width_aware.len() <= scan_line_only.len(),
"width-aware regressed: {} B vs scan-line-only {} B",
width_aware.len(),
scan_line_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn width_aware_round_trip_across_assorted_widths() {
for &(w, h) in &[
(1u32, 16u32),
(3u32, 16u32),
(16u32, 16u32),
(97u32, 13u32),
(200u32, 3u32),
(256u32, 8u32),
] {
let mut pixels = Vec::with_capacity((w * h) as usize);
for y in 0..h {
for x in 0..w {
let v = (x.wrapping_mul(31).wrapping_add(y)) & 0xff;
pixels.push(0xff00_0000 | (v << 16) | (v << 8) | v);
}
}
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round trip mismatch at {w}x{h}",
);
}
}
#[test]
fn width_aware_distance_compounds_on_many_short_row_offset_matches() {
let w = 64u32;
let h = 64u32;
let mut row0 = Vec::with_capacity(w as usize);
let mut state = 0x1357_2468u32;
for _ in 0..w {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
row0.push((state & 0x00ff_ffff) | 0xff00_0000);
}
let mut pixels = Vec::with_capacity((w * h) as usize);
pixels.extend_from_slice(&row0);
for y in 1..h {
let shift = (y as usize) & 0x3;
for x in 0..(w as usize) {
pixels.push(row0[(x + shift) % (w as usize)]);
}
}
let width_aware = encode_argb_literals_with_width(&pixels, w);
let scan_line_only = encode_argb_literals(&pixels);
eprintln!(
"[round-130] 64x64 row-shifted: scan-line-only={} B, width-aware={} B ({:.1}% reduction)",
scan_line_only.len(),
width_aware.len(),
100.0 * (scan_line_only.len() as f64 - width_aware.len() as f64)
/ scan_line_only.len() as f64,
);
assert!(
width_aware.len() < scan_line_only.len(),
"width-aware ({} B) not smaller than scan-line-only ({} B)",
width_aware.len(),
scan_line_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn width_aware_distance_headline_256x256_row_repeating() {
let w = 256u32;
let h = 256u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xABCD_1234u32;
for _ in 0..w {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push((state & 0x00ff_ffff) | 0xff00_0000);
}
for y in 1..h {
for x in 0..w {
pixels.push(pixels[(x + (y - 1) * w) as usize]);
}
}
let width_aware = encode_argb_literals_with_width(&pixels, w);
let scan_line_only = encode_argb_literals(&pixels);
eprintln!(
"[round-130] 256x256 row-repeating: scan-line-only={} B, width-aware={} B ({:.1}% reduction)",
scan_line_only.len(),
width_aware.len(),
100.0 * (scan_line_only.len() as f64 - width_aware.len() as f64)
/ scan_line_only.len() as f64,
);
assert!(
width_aware.len() < scan_line_only.len(),
"width-aware stream ({} B) not smaller than scan-line-only ({} B)",
width_aware.len(),
scan_line_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn width_aware_re_encode_of_real_fixture_is_smaller() {
let bytes: &[u8] = include_bytes!("../tests/data/lossless-32x32-rgba.webp");
let decoded = crate::decode_lossless_image(bytes).unwrap().unwrap();
let w = decoded.width();
let h = decoded.height();
let pixels = decoded.pixels().to_vec();
let width_aware = encode_argb_literals_with_width(&pixels, w);
let scan_line_only = encode_argb_literals(&pixels);
eprintln!(
"[round-130] {}x{} re-encoded fixture: scan-line-only={} B, width-aware={} B ({:.1}% reduction)",
w,
h,
scan_line_only.len(),
width_aware.len(),
100.0 * (scan_line_only.len() as f64 - width_aware.len() as f64)
/ scan_line_only.len() as f64,
);
assert!(
width_aware.len() <= scan_line_only.len(),
"width-aware regressed: {} B vs scan-line-only {} B",
width_aware.len(),
scan_line_only.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn chooser_never_picks_larger_prefix_than_scan_line() {
let width = 320u32;
for d in 1..=(width as usize * 4) {
let chooser_code = pixel_distance_to_distance_code(d, width);
let scan_code = distance_to_code(d);
let (chooser_prefix, _, _) = value_to_prefix(chooser_code);
let (scan_prefix, _, _) = value_to_prefix(scan_code);
assert!(
chooser_prefix <= scan_prefix,
"d={d}: chooser code {chooser_code} (prefix {chooser_prefix}) > scan-line {scan_code} (prefix {scan_prefix})",
);
}
}
#[test]
fn predictor_subtract_is_inverse_of_add() {
let cases = [
(0xff00_0000u32, 0xff00_0000u32),
(0x1234_5678u32, 0x0000_0000u32),
(0xff80_4020u32, 0x8040_2010u32),
(0x0000_ff00u32, 0xff00_ff00u32),
];
for (orig, pred) in cases {
let residual = predictor_subtract(orig, pred);
let a = ((residual >> 24) & 0xff).wrapping_add((pred >> 24) & 0xff) & 0xff;
let r = ((residual >> 16) & 0xff).wrapping_add((pred >> 16) & 0xff) & 0xff;
let g = ((residual >> 8) & 0xff).wrapping_add((pred >> 8) & 0xff) & 0xff;
let b = (residual & 0xff).wrapping_add(pred & 0xff) & 0xff;
let rebuilt = (a << 24) | (r << 16) | (g << 8) | b;
assert_eq!(
rebuilt, orig,
"subtract+add did not round-trip for orig=0x{orig:08x} pred=0x{pred:08x}"
);
}
}
#[test]
fn pick_block_mode_zero_cost_on_solid_block() {
let w = 8usize;
let h = 8usize;
let pixels = vec![0xff50_6070u32; w * h];
let mode = pick_block_mode(&pixels, w, h, 0, 0, w, h);
assert!(mode <= 13, "mode out of range: {mode}");
let mode_cost = |m: u8| -> u64 {
let mut c = 0u64;
for y in 0..h {
for x in 0..w {
let pred = predictor_at(&pixels, w, x, y, m);
let r = predictor_subtract(pixels[y * w + x], pred);
c += residual_magnitude(r) as u64;
}
}
c
};
let picked_cost = mode_cost(mode);
let mode0_cost = mode_cost(0);
assert!(
picked_cost < mode0_cost,
"expected picked-mode cost ({picked_cost}) < mode-0 cost ({mode0_cost})"
);
}
#[test]
fn forward_predictor_round_trips_through_decoder_inverse() {
use crate::vp8l_transform::inverse_predictor;
let w = 16u32;
let h = 16u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
for y in 0..h {
for x in 0..w {
let r = x * 16;
let g = y * 16;
let b = (x + y) * 8;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let size_bits = 4u8; let (pred_img, tw, _th) = build_predictor_image(&pixels, w, h, size_bits);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(&pixels, &mut residuals, w, h, &pred_img, tw, size_bits);
inverse_predictor(&mut residuals, w, h, &pred_img, tw, size_bits);
assert_eq!(residuals, pixels);
}
#[test]
fn round_trip_smooth_gradient_with_predictor_candidate() {
let w = 32u32;
let h = 32u32;
let mut rgba = Vec::with_capacity((w * h * 4) as usize);
for y in 0..h {
for x in 0..w {
rgba.push((x * 8) as u8); rgba.push((y * 8) as u8); rgba.push(((x + y) * 4) as u8); rgba.push(0xff); }
}
let file = encode_webp_lossless(&rgba, w, h).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn predictor_path_shrinks_smooth_gradient() {
let w = 64u32;
let h = 64u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
for y in 0..h {
for x in 0..w {
let r = (x * 4) & 0xff;
let g = (y * 4) & 0xff;
let b = ((x + y) * 2) & 0xff;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let baseline = encode_literals_with_options(&pixels, false, None, w);
let chosen = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-146] {}x{} smooth gradient: no-tx baseline={} B, chooser={} B ({:.1}% reduction)",
w,
h,
baseline.len(),
chosen.len(),
100.0 * (baseline.len() as f64 - chosen.len() as f64) / baseline.len() as f64,
);
assert!(
chosen.len() <= baseline.len(),
"chooser regressed on smooth gradient: {} B vs no-tx baseline {} B",
chosen.len(),
baseline.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn predictor_chooser_does_not_regress_on_noise() {
let w = 32u32;
let h = 32u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xc0ff_eeeeu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(state | 0xff00_0000);
}
let no_predictor = encode_argb_literals_with_width(&pixels, w);
let chosen = encode_argb_with_predictor_chooser(&pixels, w, h);
assert!(
chosen.len() <= no_predictor.len(),
"predictor chooser regressed on noise: {} B vs {} B",
chosen.len(),
no_predictor.len(),
);
}
#[test]
fn natural_fixture_round_trips_through_predictor_aware_encoder() {
let bytes: &[u8] = include_bytes!("../tests/data/lossless-128x128-natural.webp");
let decoded = crate::decode_lossless_image(bytes).unwrap().unwrap();
let w = decoded.width();
let h = decoded.height();
let pixels = decoded.pixels().to_vec();
let pre_predictor = encode_argb_literals_with_width(&pixels, w);
let with_predictor = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-146] {}x{} natural fixture re-encoded: pre-predictor chooser={} B, predictor chooser={} B ({:.1}% reduction)",
w,
h,
pre_predictor.len(),
with_predictor.len(),
100.0 * (pre_predictor.len() as f64 - with_predictor.len() as f64)
/ pre_predictor.len() as f64,
);
assert!(
with_predictor.len() <= pre_predictor.len(),
"predictor chooser regressed on natural fixture: {} B vs {} B",
with_predictor.len(),
pre_predictor.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn color_xfrm_delta_matches_spec_examples() {
assert_eq!(color_xfrm_delta(0xff, 0x40), -2);
assert_eq!(color_xfrm_delta(2, 0x40), 4);
assert_eq!(color_xfrm_delta(0, 0x7f), 0);
assert_eq!(color_xfrm_delta(0, 0xff), 0);
}
#[test]
fn forward_color_pixel_round_trips_through_decoder_inverse() {
use crate::vp8l_transform;
let cases: &[(u8, u8, u8, u8, u8, u8)] = &[
(120, 80, 200, 0x12, 0xf0, 0x05),
(255, 0, 0, 0x20, 0x00, 0x00),
(0, 255, 0, 0x00, 0x20, 0x00),
(0, 0, 255, 0x00, 0x00, 0x20),
(200, 100, 50, 0xe0, 0xd0, 0x10),
];
for &(r, g, b, gtr, gtb, rtb) in cases {
let (enc_r, enc_b) = forward_color_pixel(r, g, b, gtr, gtb, rtb);
let mut argb = vec![
((0xffu32) << 24) | ((enc_r as u32) << 16) | ((g as u32) << 8) | (enc_b as u32),
];
let cte = ((0xffu32) << 24) | ((rtb as u32) << 16) | ((gtb as u32) << 8) | (gtr as u32);
let color_img = vec![cte];
vp8l_transform::inverse_color(&mut argb, 1, 1, &color_img, 1, 9);
assert_eq!(
(argb[0] >> 16) & 0xff,
r as u32,
"red mismatch for r={r} g={g} b={b} gtr=0x{gtr:02x} gtb=0x{gtb:02x} rtb=0x{rtb:02x}",
);
assert_eq!(argb[0] & 0xff, b as u32, "blue mismatch");
assert_eq!((argb[0] >> 8) & 0xff, g as u32, "green altered");
}
}
#[test]
fn pick_block_cte_is_minimum_on_solid_block() {
let w = 8usize;
let h = 8usize;
let pixels = vec![0xff50_6070u32; w * h];
let block_cost = |gtr: u8, gtb: u8, rtb: u8| -> u64 {
let mut c = 0u64;
for &px in &pixels {
let r = ((px >> 16) & 0xff) as u8;
let g = ((px >> 8) & 0xff) as u8;
let b = (px & 0xff) as u8;
let red_residual = (r as i32 - color_xfrm_delta(gtr, g)) as u32;
let inter_blue = b as i32 - color_xfrm_delta(gtb, g);
let blue_residual = (inter_blue - color_xfrm_delta(rtb, r)) as u32;
c += channel_magnitude(red_residual) as u64;
c += channel_magnitude(blue_residual) as u64;
}
c
};
let (gtr, gtb, rtb) = pick_block_cte(&pixels, w, h, 0, 0, w, h);
let picked_cost = block_cost(gtr, gtb, rtb);
let zero_cost = block_cost(0, 0, 0);
assert!(
picked_cost <= zero_cost,
"picked CTE (0x{gtr:02x}, 0x{gtb:02x}, 0x{rtb:02x}) cost {picked_cost} > all-zero cost {zero_cost}",
);
}
#[test]
fn pick_block_cte_recovers_known_slope() {
let w = 16usize;
let h = 16usize;
let mut pixels = Vec::with_capacity(w * h);
for y in 0..h {
for x in 0..w {
let g = ((x + y) * 4) as u32 & 0xff;
let r = (g / 2) & 0xff;
let b = 0x80u32;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let (gtr, _gtb, _rtb) = pick_block_cte(&pixels, w, h, 0, 0, w, h);
let gtr_signed = gtr as i8 as i32;
assert!(
(0..=32).contains(>r_signed),
"expected gtr ≈ +16 for red≈green/2 correlation, got {gtr_signed} (raw 0x{gtr:02x})",
);
}
#[test]
fn forward_color_round_trips_through_decoder_inverse() {
use crate::vp8l_transform::inverse_color;
let w = 32u32;
let h = 32u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
for y in 0..h {
for x in 0..w {
let r = (x * 7) & 0xff;
let g = (y * 5) & 0xff;
let b = ((x + y) * 3) & 0xff;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let size_bits = 4u8;
let (color_img, tw, _th) = build_color_image(&pixels, w, h, size_bits);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_color(&pixels, &mut residuals, w, h, &color_img, tw, size_bits);
inverse_color(&mut residuals, w, h, &color_img, tw, size_bits);
assert_eq!(residuals, pixels);
}
#[test]
fn round_trip_chroma_correlated_image_with_color_transform_candidate() {
let w = 32u32;
let h = 32u32;
let mut rgba = Vec::with_capacity((w * h * 4) as usize);
for y in 0..h {
for x in 0..w {
let g = ((x + y) * 4) as u8;
let r = g.wrapping_div(2);
let b = g.wrapping_div(3);
rgba.push(r);
rgba.push(g);
rgba.push(b);
rgba.push(0xff);
}
}
let file = encode_webp_lossless(&rgba, w, h).unwrap();
let decoded = crate::decode_webp(&file).unwrap();
assert_eq!(decoded.frames[0].rgba, rgba);
}
#[test]
fn color_transform_chooser_never_regresses() {
let w = 64u32;
let h = 64u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
for y in 0..h {
for x in 0..w {
let g = ((x + y) * 4) & 0xff;
let r = (g / 2) & 0xff;
let b = (g / 3) & 0xff;
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
let pre_color = pre_round_147_chooser(&pixels, w, h);
let with_color = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-147] {}x{} chroma-correlated synth: pre-color chooser={} B, color chooser={} B ({:.1}% reduction)",
w,
h,
pre_color.len(),
with_color.len(),
100.0 * (pre_color.len() as f64 - with_color.len() as f64) / pre_color.len() as f64,
);
assert!(
with_color.len() <= pre_color.len(),
"color-transform chooser regressed: {} B vs pre-color {} B",
with_color.len(),
pre_color.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
fn make_channel_correlated_noise(w: u32, h: u32) -> Vec<u32> {
let mut pixels = vec![0u32; (w * h) as usize];
let slopes: [(u32, u32); 4] = [(1, 1), (2, 2), (1, 2), (2, 1)];
let block = 16u32;
let bw = w.div_ceil(block);
let mut state = 0x1234_5678u32;
for by in 0..h.div_ceil(block) {
for bx in 0..bw {
let (sr, sb) = slopes[((by * bw + bx) % 4) as usize];
for dy in 0..block {
let y = by * block + dy;
if y >= h {
break;
}
for dx in 0..block {
let x = bx * block + dx;
if x >= w {
break;
}
state = state.wrapping_mul(1664525).wrapping_add(1013904223);
let g = (state >> 8) & 0xff;
let jitter_r = state & 0x3f;
let jitter_b = (state >> 16) & 0x3f;
let r = (g.wrapping_mul(sr)).wrapping_add(jitter_r) & 0xff;
let b = (g.wrapping_mul(sb)).wrapping_add(jitter_b) & 0xff;
pixels[(y * w + x) as usize] = 0xff00_0000 | (r << 16) | (g << 8) | b;
}
}
}
}
pixels
}
#[test]
fn color_transform_path_beats_predictor_on_channel_correlated_noise() {
let w = 128u32;
let h = 128u32;
let pixels = make_channel_correlated_noise(w, h);
let pre_color = pre_round_147_chooser(&pixels, w, h);
let with_color = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-147] {}x{} channel-correlated noise: pre-color chooser={} B, color chooser={} B ({:.1}% reduction)",
w,
h,
pre_color.len(),
with_color.len(),
100.0 * (pre_color.len() as f64 - with_color.len() as f64) / pre_color.len() as f64,
);
assert!(
with_color.len() < pre_color.len(),
"color-transform path failed to beat the round-146 chooser on a channel-correlated-noise fixture: {} B vs {} B",
with_color.len(),
pre_color.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn color_transform_chooser_does_not_regress_on_noise() {
let w = 32u32;
let h = 32u32;
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xbadd_caf3u32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(state | 0xff00_0000);
}
let pre_color = pre_round_147_chooser(&pixels, w, h);
let with_color = encode_argb_with_predictor_chooser(&pixels, w, h);
assert!(
with_color.len() <= pre_color.len(),
"color-transform chooser regressed on noise: {} B vs {} B",
with_color.len(),
pre_color.len(),
);
}
#[test]
fn natural_fixture_round_trips_through_color_transform_aware_encoder() {
let bytes: &[u8] = include_bytes!("../tests/data/lossless-128x128-natural.webp");
let decoded = crate::decode_lossless_image(bytes).unwrap().unwrap();
let w = decoded.width();
let h = decoded.height();
let pixels = decoded.pixels().to_vec();
let pre_color = pre_round_147_chooser(&pixels, w, h);
let with_color = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-147] {}x{} natural fixture re-encoded: pre-color chooser={} B, color chooser={} B ({:.1}% reduction)",
w,
h,
pre_color.len(),
with_color.len(),
100.0 * (pre_color.len() as f64 - with_color.len() as f64)
/ pre_color.len() as f64,
);
assert!(
with_color.len() <= pre_color.len(),
"color-transform chooser regressed on natural fixture: {} B vs {} B",
with_color.len(),
pre_color.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
fn pre_round_147_chooser(pixels: &[u32], width: u32, height: u32) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let block = 1u32 << size_bits;
if width >= block && height >= block {
let candidates = [
encode_with_predictor(pixels, width, height, size_bits, None, width),
encode_with_predictor(
pixels,
width,
height,
size_bits,
Some(DEFAULT_COLOR_CACHE_BITS),
width,
),
];
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
best
}
fn pre_round_148_literals_chooser(pixels: &[u32], image_width: u32) -> Vec<u8> {
debug_assert!(image_width >= 1);
let mut best = encode_literals_with_options(pixels, false, None, image_width);
let candidates = [
encode_literals_with_options(pixels, true, None, image_width),
encode_literals_with_options(
pixels,
false,
Some(DEFAULT_COLOR_CACHE_BITS),
image_width,
),
encode_literals_with_options(pixels, true, Some(DEFAULT_COLOR_CACHE_BITS), image_width),
];
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
best
}
#[test]
fn select_best_cache_bits_explores_full_spec_range() {
let mut calls: Vec<Option<u32>> = Vec::new();
let _ = select_best_cache_bits(|bits| {
calls.push(bits);
let len = match bits {
None => 100,
Some(b) => 200 - (b as usize) * 10 + (7 - b as i32).unsigned_abs() as usize,
};
vec![0u8; len]
});
assert_eq!(calls.len(), 12, "expected 12 candidates");
assert_eq!(calls[0], None);
for (i, bits) in (COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX).enumerate() {
assert_eq!(calls[i + 1], Some(bits));
}
}
#[test]
fn select_best_cache_bits_returns_minimum() {
let chosen = select_best_cache_bits(|bits| match bits {
None => vec![0u8; 200],
Some(5) => vec![0u8; 50],
Some(b) => vec![0u8; 200 - (b as usize)],
});
assert_eq!(chosen.len(), 50);
}
#[test]
fn round_148_sweep_never_regresses_versus_hardcoded_8() {
let palette4: Vec<u32> = {
let palette = [0xff10_2030u32, 0xff40_5060, 0xff70_8090, 0xffa0_b0c0];
let mut state = 0x1357_9bdfu32;
(0..(8 * 8))
.map(|_| {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
palette[(state as usize) % palette.len()]
})
.collect()
};
let mut wide_palette: Vec<u32> = Vec::with_capacity(32 * 32);
let mut wstate = 0xabad_1deau32;
for _ in 0..(32 * 32) {
wstate ^= wstate << 13;
wstate ^= wstate >> 17;
wstate ^= wstate << 5;
wide_palette.push(0xff00_0000 | (wstate & 0x3fff_3fff));
}
let noise: Vec<u32> = {
let mut state = 0xc0de_d00du32;
(0..(16 * 16))
.map(|_| {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
state | 0xff00_0000
})
.collect()
};
for (label, pixels, width) in [
("small-palette 8x8", palette4, 8u32),
("wide-palette 32x32", wide_palette, 32u32),
("noise 16x16", noise, 16u32),
] {
let pre = pre_round_148_literals_chooser(&pixels, width);
let post = encode_argb_literals_with_width(&pixels, width);
eprintln!(
"[round-148] {label}: pre={} B, post-sweep={} B",
pre.len(),
post.len(),
);
assert!(
post.len() <= pre.len(),
"round-148 sweep regressed on {label}: post {} B vs pre {} B",
post.len(),
pre.len(),
);
}
}
#[test]
fn round_148_sweep_beats_hardcoded_8_on_small_palette() {
let w = 32u32;
let h = 32u32;
let palette: Vec<u32> = (0..16u32)
.map(|i| 0xff00_0000 | (i * 0x0011_2233))
.collect();
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xfeed_face_u32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(palette[(state as usize) % palette.len()]);
}
let pre = pre_round_148_literals_chooser(&pixels, w);
let post = encode_argb_literals_with_width(&pixels, w);
eprintln!(
"[round-148] small-palette 32x32: hardcoded-8={} B, sweep={} B ({:.1}% reduction)",
pre.len(),
post.len(),
100.0 * (pre.len() as f64 - post.len() as f64) / pre.len() as f64,
);
assert!(
post.len() < pre.len(),
"expected sweep to beat hardcoded-8 on 16-color palette: post {} B vs pre {} B",
post.len(),
pre.len(),
);
let bare = encode_vp8l_argb(&pixels, w, h).unwrap();
let framed = build::build_webp_file(&bare, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_148_sweep_picks_non_default_cache_bits_on_some_payload() {
use crate::meta_prefix::{ImageRole, MetaPrefixHeader};
use crate::vp8l_stream::BitReader;
let mut payloads: Vec<(u32, u32, Vec<u32>)> = Vec::new();
{
let w = 32u32;
let h = 32u32;
let palette = [0xff10_2030u32, 0xff40_5060, 0xff70_8090, 0xffa0_b0c0];
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0x1357_9bdfu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(palette[(state as usize) % palette.len()]);
}
payloads.push((w, h, pixels));
}
{
let w = 64u32;
let h = 64u32;
let palette: Vec<u32> = (0..32u32)
.map(|i| 0xff00_0000 | (i * 0x0008_4210))
.collect();
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xdead_beefu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(palette[(state as usize) % palette.len()]);
}
payloads.push((w, h, pixels));
}
{
let w = 64u32;
let h = 64u32;
let palette: Vec<u32> = (0..256u32)
.map(|i| 0xff00_0000 | (i * 0x0001_0101))
.collect();
let mut pixels = Vec::with_capacity((w * h) as usize);
let mut state = 0xc0ff_eeefu32;
for _ in 0..(w * h) {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
pixels.push(palette[(state as usize) % palette.len()]);
}
payloads.push((w, h, pixels));
}
let mut saw_non_default_enabled = false;
for (w, h, pixels) in &payloads {
let chosen = select_best_cache_bits(|cache_bits| {
encode_literals_with_options(pixels, false, cache_bits, *w)
});
let mut r = BitReader::new(&chosen);
assert!(!r.read_bit().unwrap());
let header = MetaPrefixHeader::read(&mut r, ImageRole::Argb, *w, *h).unwrap();
if header.color_cache.is_enabled() {
assert!(
(COLOR_CACHE_BITS_MIN..=COLOR_CACHE_BITS_MAX)
.contains(&header.color_cache.code_bits),
"chosen code_bits {} outside §5.2.3 [{COLOR_CACHE_BITS_MIN}..{COLOR_CACHE_BITS_MAX}]",
header.color_cache.code_bits,
);
eprintln!(
"[round-148] {}x{} palette payload: sweep enabled cache with code_bits={}",
w, h, header.color_cache.code_bits
);
if header.color_cache.code_bits != DEFAULT_COLOR_CACHE_BITS {
saw_non_default_enabled = true;
}
} else {
eprintln!(
"[round-148] {}x{} palette payload: sweep disabled cache",
w, h
);
}
}
assert!(
saw_non_default_enabled,
"expected the round-148 sweep to pick a non-default code_bits on at least one payload"
);
}
#[test]
fn encoder_color_indexing_width_bits_matches_spec_table() {
assert_eq!(encoder_color_indexing_width_bits(1), 3);
assert_eq!(encoder_color_indexing_width_bits(2), 3);
assert_eq!(encoder_color_indexing_width_bits(3), 2);
assert_eq!(encoder_color_indexing_width_bits(4), 2);
assert_eq!(encoder_color_indexing_width_bits(5), 1);
assert_eq!(encoder_color_indexing_width_bits(16), 1);
assert_eq!(encoder_color_indexing_width_bits(17), 0);
assert_eq!(encoder_color_indexing_width_bits(256), 0);
}
#[test]
fn forward_color_table_round_trips_with_decoder_inverse() {
let original: Vec<u32> = vec![
0xff00_0000,
0xff01_0203,
0xff80_4020,
0x7f12_3456,
0x0000_00ff,
];
let mut encoded = original.clone();
forward_color_table(&mut encoded);
crate::vp8l_transform::inverse_color_table(&mut encoded);
assert_eq!(encoded, original);
}
#[test]
fn collect_palette_early_exits_above_256_unique_colors() {
let small = vec![0xff10_2030, 0xff40_5060, 0xff10_2030, 0xff70_8090];
let (p, m) = collect_palette(&small).expect("4-color palette fits");
assert_eq!(p.len(), 3); assert!(p.windows(2).all(|w| w[0] < w[1]));
for px in &small {
let idx = m[px] as usize;
assert_eq!(p[idx], *px);
}
let big: Vec<u32> = (0..257u32).map(|i| 0xff00_0000 | i).collect();
assert!(collect_palette(&big).is_none());
}
#[test]
fn color_indexing_round_trip_across_all_width_bits_regimes() {
let palette_64: Vec<u32> = (0..64u32)
.map(|i| 0xff00_0000 | (i << 18) | (i << 10) | (i << 2))
.collect();
let scenarios: [(u32, u32, &[u32]); 4] = [
(32, 4, &[0xff00_0000, 0xffff_ffff]),
(16, 4, &[0xff10_2030, 0xff40_5060, 0xff70_8090, 0xffa0_b0c0]),
(
16,
4,
&[
0xff00_0000,
0xff10_2030,
0xff20_4060,
0xff30_6090,
0xff40_80c0,
0xff50_a0e0,
0xff60_c0ff,
0xff70_ff00,
0xff80_8080,
0xff90_9090,
0xffa0_a0a0,
0xffb0_b0b0,
0xffc0_c0c0,
0xffd0_d0d0,
0xffe0_e0e0,
0xfff0_f0f0,
],
),
(16, 4, palette_64.as_slice()),
];
for (w, h, palette) in scenarios {
let mut pixels: Vec<u32> = Vec::with_capacity((w * h) as usize);
let mut state: u32 = 0xC0FF_EE12;
for _ in 0..(w * h) {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
pixels.push(palette[(state as usize) % palette.len()]);
}
let stream = encode_with_color_indexing(&pixels, w, h, None)
.expect("palette fits below 256 unique");
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.expect("decode color-indexing round trip");
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip mismatch on {}-color palette ({}x{} image)",
palette.len(),
w,
h
);
}
}
#[test]
fn round_150_color_indexing_beats_other_candidates_on_palette_image() {
let palette: [u32; 2] = [0xff00_0000, 0xffff_ffff];
let w = 64u32;
let h = 32u32;
let mut pixels: Vec<u32> = Vec::with_capacity((w * h) as usize);
let mut row_pattern: u64 = 0xa5a5_a5a5_a5a5_a5a5;
for _y in 0..h {
for x in 0..w {
let bit = (row_pattern >> (x % 64)) & 1;
pixels.push(palette[bit as usize]);
}
row_pattern = row_pattern.rotate_left(1);
}
let chosen = encode_argb_with_predictor_chooser(&pixels, w, h);
let no_tx_baseline =
select_best_cache_bits(|bits| encode_literals_with_options(&pixels, false, bits, w));
let sg_baseline =
select_best_cache_bits(|bits| encode_literals_with_options(&pixels, true, bits, w));
let pred_baseline = select_best_cache_bits(|bits| {
encode_with_predictor(&pixels, w, h, DEFAULT_PREDICTOR_SIZE_BITS, bits, w)
});
let ctx_baseline = select_best_cache_bits(|bits| {
encode_with_color_transform(&pixels, w, h, DEFAULT_COLOR_TRANSFORM_SIZE_BITS, bits, w)
});
let baseline = no_tx_baseline
.len()
.min(sg_baseline.len())
.min(pred_baseline.len())
.min(ctx_baseline.len());
let ci_only = select_best_cache_bits(|bits| {
encode_with_color_indexing(&pixels, w, h, bits).expect("palette fits")
});
eprintln!(
"[round-150] 64x32 binary row-rotation: chosen={} B, baseline (no §4.4)={} B, ci_only={} B ({:.1}% reduction vs baseline)",
chosen.len(),
baseline,
ci_only.len(),
(1.0 - chosen.len() as f64 / baseline as f64) * 100.0
);
assert!(
chosen.len() < baseline,
"round-150 color-indexing must beat the round-149 baseline on a palette image: \
chosen={} B vs baseline={} B (ci_only={} B)",
chosen.len(),
baseline,
ci_only.len(),
);
let rgba: Vec<u8> = pixels
.iter()
.flat_map(|&p| {
let a = ((p >> 24) & 0xff) as u8;
let r = ((p >> 16) & 0xff) as u8;
let g = ((p >> 8) & 0xff) as u8;
let b = (p & 0xff) as u8;
[r, g, b, a]
})
.collect();
let webp_bytes = encode_webp_lossless(&rgba, w, h).expect("encode round-150 webp");
let decoded = crate::decode_webp(&webp_bytes).expect("decode round-150 webp");
assert_eq!(decoded.frames.len(), 1);
assert_eq!(decoded.frames[0].rgba.as_slice(), rgba.as_slice());
}
#[test]
fn color_indexing_chooser_skips_photo_like_content() {
let w = 64u32;
let h = 64u32;
let mut pixels: Vec<u32> = Vec::with_capacity((w * h) as usize);
let mut state: u32 = 0xFEED_FACE;
for _ in 0..(w * h) {
state = state.wrapping_mul(1_103_515_245).wrapping_add(12345);
pixels.push(0xff00_0000 | (state & 0x00ff_ffff));
}
assert!(collect_palette(&pixels).is_none());
let stream = encode_argb_with_predictor_chooser(&pixels, w, h);
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.expect("decode photo-like content");
assert_eq!(decoded.pixels(), pixels.as_slice());
}
fn two_region_bimodal_image(width: u32, height: u32) -> Vec<u32> {
let w = width as usize;
let h = height as usize;
let mut pixels = Vec::with_capacity(w * h);
for y in 0..h {
for x in 0..w {
let (r, g, b) = if y < h / 2 {
let g = 32u32.wrapping_add(((x as u32) & 0x1f) * 2);
let r = 64u32.wrapping_add((y as u32) & 0x0f);
(r, g, 16u32)
} else {
let g = 200u32.wrapping_add((x as u32) & 0x1f);
let b = 96u32.wrapping_add((y as u32) & 0x0f);
(16u32, g, b)
};
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
pixels
}
fn two_region_noisy_image(width: u32, height: u32) -> Vec<u32> {
let w = width as usize;
let h = height as usize;
let mut pixels = Vec::with_capacity(w * h);
let mut s_top: u32 = 0xC0FF_EE00;
let mut s_bot: u32 = 0xBADC_AFE5;
for y in 0..h {
for x in 0..w {
let argb = if y < h / 2 {
s_top = s_top.wrapping_mul(1_103_515_245).wrapping_add(12345);
let r = s_top & 0x3f; let g = ((s_top >> 8) & 0x3f).wrapping_add(192); let b = (s_top >> 16) & 0x1f; (0xffu32 << 24) | (r << 16) | (g << 8) | b
} else {
s_bot = s_bot.wrapping_mul(1_103_515_245).wrapping_add(12345);
let r = ((s_bot >> 8) & 0x3f).wrapping_add(192); let g = s_bot & 0x3f; let b = ((s_bot >> 16) & 0x1f).wrapping_add(192); (0xffu32 << 24) | (r << 16) | (g << 8) | b
};
let _ = x;
pixels.push(argb);
}
}
pixels
}
#[test]
fn meta_prefix_clusterer_splits_two_region_bimodal_fixture() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_bimodal_image(w, h);
let codes = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 2);
assert_eq!(codes.len(), 16);
let top = codes[0];
let bot = codes[12];
assert_ne!(
top, bot,
"top half group must differ from bottom half group"
);
for c in &codes[0..8] {
assert_eq!(*c, top, "top-half blocks must share a group");
}
for c in &codes[8..16] {
assert_eq!(*c, bot, "bottom-half blocks must share a group");
}
}
#[test]
fn histogram_clusterer_separates_blocks_sharing_a_mean() {
let w = 32u32;
let h = 32u32;
let w_us = w as usize;
let h_us = h as usize;
let mut pixels: Vec<u32> = Vec::with_capacity(w_us * h_us);
for y in 0..h_us {
for x in 0..w_us {
let g = if y < h_us / 2 {
if (x ^ y) & 1 == 0 {
16u32
} else {
240u32
}
} else {
128u32
};
pixels.push(0xff00_0000 | (g << 8));
}
}
let codes = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 2);
assert_eq!(codes.len(), 4);
let top_left = codes[0];
let bot_left = codes[2];
assert_ne!(
top_left, bot_left,
"bimodal-vs-flat green regions must split into distinct groups",
);
}
#[test]
fn histogram_clusterer_is_deterministic() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_noisy_image(w, h);
let first = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 3);
let second = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 3);
assert_eq!(first, second);
}
#[test]
fn histogram_clusterer_collapses_on_uniform_image() {
let w = 64u32;
let h = 64u32;
let pixels = vec![0xff80_8080u32; (w * h) as usize];
let codes = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 4);
assert_eq!(codes.len(), 16);
for c in &codes {
assert_eq!(*c, 0, "uniform image must collapse to one group");
}
}
#[test]
fn histogram_clusterer_num_groups_one_returns_all_zeros() {
let w = 32u32;
let h = 32u32;
let pixels = two_region_noisy_image(w, h);
let codes = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 1);
assert!(codes.iter().all(|&c| c == 0));
}
#[test]
fn histogram_clusterer_returns_compact_group_ids() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_noisy_image(w, h);
let codes = cluster_blocks_by_histogram_distance(&pixels, w, h, 4, 4);
let max_code = codes.iter().copied().max().unwrap_or(0) as usize;
let mut seen = vec![false; max_code + 1];
for &c in &codes {
seen[c as usize] = true;
}
for (i, &s) in seen.iter().enumerate() {
assert!(s, "gap at group id {i} — compaction failed");
}
}
#[test]
fn meta_prefix_two_group_round_trips_through_decoder() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_bimodal_image(w, h);
let stream = encode_with_meta_prefix(&pixels, w, h, 4, 2, None, w)
.expect("two-region image admits a 2-group split");
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.expect("decode meta-prefix stream");
assert_eq!(decoded.pixels(), pixels.as_slice());
}
#[test]
fn meta_prefix_two_group_with_cache_round_trips_through_decoder() {
let w = 32u32;
let h = 32u32;
let pixels = two_region_bimodal_image(w, h);
let stream = encode_with_meta_prefix(&pixels, w, h, 4, 2, Some(8), w)
.expect("two-region image admits a 2-group split with cache");
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.expect("decode meta-prefix-with-cache stream");
assert_eq!(decoded.pixels(), pixels.as_slice());
}
#[test]
fn meta_prefix_three_and_four_groups_round_trip_through_decoder() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_noisy_image(w, h);
for num_groups in [3u32, 4u32] {
let stream = encode_with_meta_prefix(&pixels, w, h, 4, num_groups, None, w)
.unwrap_or_else(|| panic!("noisy image admits {num_groups} groups"));
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.unwrap_or_else(|e| panic!("decode {num_groups}-group stream: {e}"));
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip failed for num_groups={num_groups}"
);
}
}
#[test]
fn meta_prefix_all_sweep_prefix_bits_round_trip_through_decoder() {
let w = 256u32;
let h = 256u32;
let pixels = two_region_noisy_image(w, h);
for &pb in META_PREFIX_BITS_SWEEP.iter() {
let stream =
encode_with_meta_prefix(&pixels, w, h, pb, 2, None, w).unwrap_or_else(|| {
panic!("256x256 noisy image admits 2-group at prefix_bits={pb}")
});
let header = build_image_header(w, h, false);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let decoded = crate::vp8l_transform::decode_lossless(&payload, w, h)
.unwrap_or_else(|e| panic!("decode prefix_bits={pb} stream: {e}"));
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip failed for prefix_bits={pb}"
);
}
}
#[test]
fn meta_prefix_returns_none_when_too_small_for_a_split() {
let pixels = vec![0xff10_2030u32];
for &pb in META_PREFIX_BITS_SWEEP.iter() {
for num_groups in 2..=MAX_META_GROUPS {
assert!(
encode_with_meta_prefix(&pixels, 1, 1, pb, num_groups, None, 1).is_none(),
"1x1 image must not produce a multi-group stream (prefix_bits={pb}, num_groups={num_groups})"
);
}
}
}
#[test]
fn meta_prefix_returns_none_on_uniform_image() {
let w = 64u32;
let h = 64u32;
let pixels = vec![0xff80_8080u32; (w * h) as usize];
assert!(encode_with_meta_prefix(&pixels, w, h, 4, 2, None, w).is_none());
}
#[test]
fn round_151_chooser_round_trips_on_two_region_image() {
let w = 64u32;
let h = 64u32;
let pixels = two_region_bimodal_image(w, h);
let rgba: Vec<u8> = pixels
.iter()
.flat_map(|&p| {
let a = ((p >> 24) & 0xff) as u8;
let r = ((p >> 16) & 0xff) as u8;
let g = ((p >> 8) & 0xff) as u8;
let b = (p & 0xff) as u8;
[r, g, b, a]
})
.collect();
let webp_bytes = encode_webp_lossless(&rgba, w, h).expect("encode round-151 webp");
let decoded = crate::decode_webp(&webp_bytes).expect("decode round-151 webp");
assert_eq!(decoded.frames.len(), 1);
assert_eq!(decoded.frames[0].rgba.as_slice(), rgba.as_slice());
}
#[test]
fn round_151_diagnostic_sweep_records_per_shape_costs() {
let shapes = [
(
"64x64 noisy 2-region",
two_region_noisy_image(64, 64),
64u32,
64u32,
),
(
"128x128 noisy 2-region",
two_region_noisy_image(128, 128),
128u32,
128u32,
),
(
"64x128 noisy 2-region",
two_region_noisy_image(64, 128),
64u32,
128u32,
),
(
"256x256 noisy 2-region",
two_region_noisy_image(256, 256),
256u32,
256u32,
),
];
for (name, pixels, w, h) in &shapes {
let baseline = encode_argb_with_predictor_chooser(pixels, *w, *h);
let mp_opt = sweep_meta_prefix_candidate(pixels, *w, *h);
let mp_len = mp_opt.as_ref().map(|v| v.len()).unwrap_or(usize::MAX);
eprintln!(
"[round-151 diag] {name}: baseline={} B, mp_only={} B, mp_wins={}",
baseline.len(),
mp_len,
mp_len < baseline.len()
);
}
}
#[test]
fn round_151_multi_meta_prefix_beats_single_group_on_noisy_image() {
let w = 128u32;
let h = 128u32;
let pixels = two_region_noisy_image(w, h);
let mut baseline = encode_argb_literals_with_width(&pixels, w);
let pred_block = 1u32 << DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_block = 1u32 << DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
if w >= pred_block && h >= pred_block {
let pred = select_best_cache_bits(|cache_bits| {
encode_with_predictor(&pixels, w, h, DEFAULT_PREDICTOR_SIZE_BITS, cache_bits, w)
});
if pred.len() < baseline.len() {
baseline = pred;
}
}
if w >= ctx_block && h >= ctx_block {
let ctx = select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
&pixels,
w,
h,
DEFAULT_COLOR_TRANSFORM_SIZE_BITS,
cache_bits,
w,
)
});
if ctx.len() < baseline.len() {
baseline = ctx;
}
}
if collect_palette(&pixels).is_some() {
let ci = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(&pixels, w, h, cache_bits).expect("palette fits")
});
if ci.len() < baseline.len() {
baseline = ci;
}
}
let mp = sweep_meta_prefix_candidate(&pixels, w, h)
.expect("two-region 128x128 image admits a multi-group split");
let chosen = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-151] 128x128 two-region noisy: chosen={} B, baseline (no §6.2.2)={} B, mp_only={} B ({:.1}% reduction vs baseline)",
chosen.len(),
baseline.len(),
mp.len(),
(1.0 - chosen.len() as f64 / baseline.len() as f64) * 100.0
);
assert!(
chosen.len() <= baseline.len(),
"round-151 chooser must never regress on the round-150 baseline: \
chosen={} B vs baseline={} B (mp_only={} B)",
chosen.len(),
baseline.len(),
mp.len(),
);
}
fn cluster_blocks_by_mean_green_for_bench(
pixels: &[u32],
width: u32,
height: u32,
prefix_bits: u8,
num_groups: u32,
) -> Vec<u16> {
let block_side = 1u32 << prefix_bits;
let pw = width.div_ceil(block_side);
let ph = height.div_ceil(block_side);
let num_blocks = (pw * ph) as usize;
let mut block_mean: Vec<f64> = vec![0.0; num_blocks];
let mut block_count: Vec<u32> = vec![0; num_blocks];
let row = width as usize;
let pw_u = pw as usize;
for y in 0..height as usize {
let by = y / block_side as usize;
for x in 0..width as usize {
let bx = x / block_side as usize;
let b = by * pw_u + bx;
let g = ((pixels[y * row + x] >> 8) & 0xff) as f64;
block_mean[b] += g;
block_count[b] += 1;
}
}
for b in 0..num_blocks {
if block_count[b] > 0 {
block_mean[b] /= block_count[b] as f64;
}
}
if num_groups == 1 {
return vec![0u16; num_blocks];
}
let mut lo = f64::INFINITY;
let mut hi = f64::NEG_INFINITY;
for &m in &block_mean {
if m < lo {
lo = m;
}
if m > hi {
hi = m;
}
}
if hi <= lo {
return vec![0u16; num_blocks];
}
let span = hi - lo;
let step = span / num_groups as f64;
let mut codes = Vec::with_capacity(num_blocks);
for &m in &block_mean {
let bucket = (((m - lo) / step).floor() as i64).clamp(0, num_groups as i64 - 1);
codes.push(bucket as u16);
}
codes
}
fn measure_mp_bytes_at(
pixels: &[u32],
w: u32,
h: u32,
prefix_bits: u8,
num_groups: u32,
use_histogram: bool,
) -> Option<usize> {
let block_side = 1u32 << prefix_bits;
let pw = w.div_ceil(block_side);
let ph = h.div_ceil(block_side);
if (pw * ph) < num_groups {
return None;
}
let codes = if use_histogram {
cluster_blocks_by_histogram_distance(pixels, w, h, prefix_bits, num_groups)
} else {
cluster_blocks_by_mean_green_for_bench(pixels, w, h, prefix_bits, num_groups)
};
if use_histogram {
return encode_with_meta_prefix(pixels, w, h, prefix_bits, num_groups, None, w)
.map(|v| v.len());
}
let index = EncoderMetaIndex {
prefix_bits,
block_width: pw,
codes,
};
let actual_groups = index.num_groups();
if actual_groups < 2 {
return None;
}
let tokens = tokenize_lz77(pixels);
let buckets = split_tokens_by_group(&tokens, &index, w, actual_groups);
let group_codes = build_group_codes(&buckets, 0, w);
let mut bw = BitWriter::new();
bw.write_bit(false);
bw.write_bit(false);
bw.write_bit(true);
bw.write_bits((prefix_bits - 2) as u32, 3);
let entropy_image = index.entropy_image_argb();
write_entropy_coded_image_literals(&mut bw, &entropy_image);
for group in &group_codes {
for code in group.iter() {
code.write_code_lengths(&mut bw);
}
}
let mut pos = 0usize;
let w_pixels = w as usize;
for &tok in &tokens {
let x = (pos % w_pixels) as u32;
let y = (pos / w_pixels) as u32;
let g = index.group_for(x, y) as usize;
let codes = &group_codes[g];
let green_code = &codes[0];
let red_code = &codes[1];
let blue_code = &codes[2];
let alpha_code = &codes[3];
let dist_code = &codes[4];
match tok {
Token::Literal(p) => {
let a = ((p >> 24) & 0xff) as usize;
let r = ((p >> 16) & 0xff) as usize;
let g_ch = ((p >> 8) & 0xff) as usize;
let b = (p & 0xff) as usize;
green_code.write_symbol(&mut bw, g_ch);
red_code.write_symbol(&mut bw, r);
blue_code.write_symbol(&mut bw, b);
alpha_code.write_symbol(&mut bw, a);
pos += 1;
}
Token::CacheRef { .. } => unreachable!("no cache in measurement"),
Token::Copy { length, distance } => {
write_lz77_value(&mut bw, green_code, 256, length as u32);
let raw_code = pixel_distance_to_distance_code(distance, w);
write_lz77_value(&mut bw, dist_code, 0, raw_code);
pos += length;
}
}
}
Some(bw.into_bytes().len())
}
fn four_region_mean_collision_image(width: u32, height: u32) -> Vec<u32> {
let w = width as usize;
let h = height as usize;
let mut pixels = Vec::with_capacity(w * h);
let mut s: u32 = 0x12345678;
for y in 0..h {
for x in 0..w {
s = s.wrapping_mul(1_103_515_245).wrapping_add(12345);
let top = y < h / 2;
let left = x < w / 2;
let (g, r, b) = match (top, left) {
(true, true) => {
let gv = if (s & 1) == 0 { 16 } else { 240 };
let rv = (s >> 8) & 0x3f;
let bv = (s >> 16) & 0x3f;
(gv, rv, bv)
}
(true, false) => {
let gv = 128u32;
let rv = ((s >> 8) & 0x3f).wrapping_add(192);
let bv = (s >> 16) & 0x3f;
(gv, rv, bv)
}
(false, true) => {
let gv = if (s & 1) == 0 { 64 } else { 192 };
let rv = (s >> 8) & 0x3f;
let bv = ((s >> 16) & 0x3f).wrapping_add(192);
(gv, rv, bv)
}
(false, false) => {
let gv = 128u32;
let rv = ((s >> 8) & 0x3f).wrapping_add(192);
let bv = ((s >> 16) & 0x3f).wrapping_add(192);
(gv, rv, bv)
}
};
pixels.push(0xff00_0000 | (r << 16) | (g << 8) | b);
}
}
pixels
}
fn best_mp_bytes_over_sweep(
pixels: &[u32],
w: u32,
h: u32,
use_histogram: bool,
) -> Option<usize> {
let mut best: Option<usize> = None;
for &prefix_bits in META_PREFIX_BITS_SWEEP.iter() {
for num_groups in 2u32..=MAX_META_GROUPS {
if let Some(bytes) =
measure_mp_bytes_at(pixels, w, h, prefix_bits, num_groups, use_histogram)
{
best = Some(match best {
Some(b) => b.min(bytes),
None => bytes,
});
}
}
}
best
}
#[test]
fn histogram_clusterer_reduces_mp_bytes_on_two_region_sweep() {
let shapes: &[(u32, u32)] = &[(64, 64), (128, 128), (64, 128), (256, 256)];
for &(w, h) in shapes {
let pixels = two_region_noisy_image(w, h);
let mg = best_mp_bytes_over_sweep(&pixels, w, h, false)
.expect("mean-green path must produce a candidate");
let hi = best_mp_bytes_over_sweep(&pixels, w, h, true)
.expect("histogram path must produce a candidate");
assert!(
hi <= mg,
"{w}x{h}: histogram path produced {hi} B, mean-green produced {mg} B \
— histogram path must not regress on the two-region sweep",
);
println!(
"r152 measurement {w}x{h}: mean-green={mg} B histogram={hi} B \
delta={} B ({:.2}%)",
mg as i64 - hi as i64,
100.0 * (mg as f64 - hi as f64) / mg as f64,
);
}
}
#[test]
fn histogram_clusterer_reduces_mp_bytes_on_mean_collision_sweep() {
let shapes: &[(u32, u32)] = &[(64, 64), (128, 128), (64, 128), (256, 256)];
for &(w, h) in shapes {
let pixels = four_region_mean_collision_image(w, h);
let mg_opt = best_mp_bytes_over_sweep(&pixels, w, h, false);
let hi = best_mp_bytes_over_sweep(&pixels, w, h, true)
.expect("histogram path must produce a candidate");
match mg_opt {
Some(mg) => {
assert!(
hi < mg,
"{w}x{h}: histogram path produced {hi} B, mean-green produced {mg} B \
— histogram path must strictly improve on mean-collision fixture",
);
println!(
"r152 mean-collision {w}x{h}: mean-green={mg} B histogram={hi} B \
delta={} B ({:.2}%)",
mg as i64 - hi as i64,
100.0 * (mg as f64 - hi as f64) / mg as f64,
);
}
None => {
println!(
"r152 mean-collision {w}x{h}: mean-green collapsed (no candidate); \
histogram={hi} B",
);
}
}
}
}
fn pre_round_155_predictor_chooser(pixels: &[u32], width: u32, height: u32) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let pred_best = select_best_cache_bits(|cache_bits| {
encode_with_predictor(pixels, width, height, pred_size_bits, cache_bits, width)
});
if pred_best.len() < best.len() {
best = pred_best;
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
#[test]
fn round_155_predictor_size_bits_sweep_never_regresses() {
let shapes: &[(u32, u32)] = &[
(16, 16),
(20, 20),
(24, 24),
(32, 32),
(48, 48),
(16, 32),
(64, 16),
(40, 24),
];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0xFF;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let mut seed = 0xC0FFEE_u32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("noise", &noise),
("stripes", &stripes),
] {
let pre = pre_round_155_predictor_chooser(pixels, w, h);
let post = encode_argb_with_predictor_chooser(pixels, w, h);
assert!(
post.len() <= pre.len(),
"round-155 chooser regression on {name} {w}x{h}: pre={} B post={} B",
pre.len(),
post.len(),
);
}
}
}
#[test]
fn round_155_predictor_size_bits_sweep_strictly_beats_default_on_some_fixture() {
let w = 20u32;
let h = 20u32;
let mut seed = 0xDEADBEEF_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let pre = pre_round_155_predictor_chooser(&pixels, w, h);
let post = encode_argb_with_predictor_chooser(&pixels, w, h);
eprintln!(
"[round-155] {w}x{h} dense-residual: pre={} B post={} B delta={} B ({:.2}%)",
pre.len(),
post.len(),
pre.len() as i64 - post.len() as i64,
(pre.len() as f64 - post.len() as f64) / pre.len() as f64 * 100.0,
);
assert!(
post.len() < pre.len(),
"round-155 maximal-single-block predictor must strictly shrink the chosen \
stream on the 20x20 dense-residual fixture: pre={} B post={} B",
pre.len(),
post.len(),
);
}
#[test]
fn round_155_predictor_single_block_round_trips_through_decoder() {
let w = 64u32;
let h = 16u32;
let mut seed = 0xA5A5_F00D_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stream_chooser = encode_argb_with_predictor_chooser(&pixels, w, h);
let header_chooser = build_image_header(w, h, true);
let mut payload_chooser = header_chooser.to_vec();
payload_chooser.extend_from_slice(&stream_chooser);
let framed_chooser =
build::build_webp_file(&payload_chooser, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed_chooser)
.unwrap()
.unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
let mut single_block_size_bits: u8 = DEFAULT_PREDICTOR_SIZE_BITS;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < w || (1u32 << single_block_size_bits) < h)
{
single_block_size_bits += 1;
}
assert_eq!(single_block_size_bits, 6);
let stream = encode_with_predictor(&pixels, w, h, single_block_size_bits, None, w);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img2 = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img2.pixels(), pixels.as_slice());
}
#[test]
fn round_156_lazy_match_round_trips_through_decoder() {
let w = 64u32;
let h = 16u32;
let mut seed = 0xF00D_BABE_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stream = encode_argb_with_predictor_chooser(&pixels, w, h);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
let stream_direct = encode_argb_literals_with_width(&pixels, w);
let header_direct = build_image_header(w, h, true);
let mut payload_direct = header_direct.to_vec();
payload_direct.extend_from_slice(&stream_direct);
let framed_direct =
build::build_webp_file(&payload_direct, ImageKind::Lossless, w, h).unwrap();
let img_direct = crate::decode_lossless_image(&framed_direct)
.unwrap()
.unwrap();
assert_eq!(img_direct.pixels(), pixels.as_slice());
}
#[test]
fn round_156_lazy_match_strictly_beats_greedy_on_trap_fixture() {
let a = 0xFF11_2233_u32;
let b = 0xFF22_3344_u32;
let c = 0xFF33_4455_u32;
let d = 0xFF44_5566_u32;
let e = 0xFF55_6677_u32;
let f = 0xFF66_7788_u32;
let g = 0xFF77_8899_u32;
let h = 0xFF88_99AA_u32;
let z = 0xFF00_0000_u32;
let mut pixels: Vec<u32> = vec![
a, b, c, d, z, z, z, b, c, d, e, f, g, h, z, z, z, a, b, c, d, e, f, g, h, ];
while pixels.len() < 64 {
pixels.push(z);
}
let greedy = tokenize_lz77_inner(&pixels, 0);
let lazy = tokenize_lz77_inner(&pixels, 1);
let greedy_copies = greedy
.iter()
.filter(|t| matches!(t, Token::Copy { .. }))
.count();
let lazy_copies = lazy
.iter()
.filter(|t| matches!(t, Token::Copy { .. }))
.count();
let coverage = |toks: &[Token]| -> usize {
toks.iter()
.map(|t| match *t {
Token::Literal(_) => 1,
Token::CacheRef { .. } => 1,
Token::Copy { length, .. } => length,
})
.sum()
};
assert_eq!(coverage(&greedy), pixels.len());
assert_eq!(coverage(&lazy), pixels.len());
eprintln!(
"[round-156] trap fixture: greedy tokens={} (copies={}), \
lazy tokens={} (copies={}), copy delta={}",
greedy.len(),
greedy_copies,
lazy.len(),
lazy_copies,
greedy_copies as i64 - lazy_copies as i64,
);
assert!(
lazy_copies < greedy_copies,
"round-156 lazy matcher must emit strictly fewer Copy tokens on the trap \
fixture: greedy copies={} lazy copies={}\ngreedy partition: {:?}\n\
lazy partition: {:?}",
greedy_copies,
lazy_copies,
greedy,
lazy,
);
let stream = encode_argb_literals_with_width(&pixels, pixels.len() as u32);
let w = pixels.len() as u32;
let h = 1u32;
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_156_lazy_never_increases_token_count() {
let shapes: &[(u32, u32)] = &[
(16, 16),
(20, 20),
(24, 24),
(32, 32),
(48, 48),
(16, 32),
(64, 16),
(40, 24),
];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0xFF;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let mut seed = 0xC0FFEE_u32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("noise", &noise),
("stripes", &stripes),
] {
let greedy = tokenize_lz77_inner(pixels, 0);
let lazy = tokenize_lz77_inner(pixels, 1);
assert!(
lazy.len() <= greedy.len(),
"round-156 lazy regression on {name} {w}x{h}: greedy={} tokens, \
lazy={} tokens",
greedy.len(),
lazy.len(),
);
}
}
}
#[test]
fn round_157_depth2_lazy_match_round_trips_through_decoder() {
let w = 80u32;
let h = 16u32;
let mut seed = 0xCAFE_F00D_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stream = encode_argb_with_predictor_chooser(&pixels, w, h);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
let stream_direct = encode_argb_literals_with_width(&pixels, w);
let header_direct = build_image_header(w, h, true);
let mut payload_direct = header_direct.to_vec();
payload_direct.extend_from_slice(&stream_direct);
let framed_direct =
build::build_webp_file(&payload_direct, ImageKind::Lossless, w, h).unwrap();
let img_direct = crate::decode_lossless_image(&framed_direct)
.unwrap()
.unwrap();
assert_eq!(img_direct.pixels(), pixels.as_slice());
}
#[test]
fn round_157_depth2_lazy_match_strictly_beats_depth1_on_trap_fixture() {
let p_ = 0xFF11_2200_u32;
let q_ = 0xFF22_3300_u32;
let r_ = 0xFF33_4400_u32;
let s_ = 0xFF44_5500_u32;
let t_ = 0xFF55_6600_u32;
let u_ = 0xFF66_7700_u32;
let v_ = 0xFF77_8800_u32;
let w_ = 0xFF88_9900_u32;
let x_ = 0xFF99_AA00_u32;
let y_ = 0xFFAA_BB00_u32;
let z1 = 0xFFCC_DD01_u32;
let z2 = 0xFFCC_DD02_u32;
let z3 = 0xFFCC_DD03_u32;
let z4 = 0xFFCC_DD04_u32;
let z5 = 0xFFCC_DD05_u32;
let z6 = 0xFFCC_DD06_u32;
let z7 = 0xFFCC_DD07_u32;
let z8 = 0xFFCC_DD08_u32;
let z9 = 0xFFCC_DD09_u32;
let mut pixels: Vec<u32> = vec![
p_, q_, r_, s_, z1, z2, z3, q_, r_, s_, t_, z4, z5, z6, r_, s_, t_, u_, v_, w_, x_, y_, z7, z8, z9, p_, q_, r_, s_, t_, u_, v_, w_, x_, ];
let mut filler = 0xFFE0_0000_u32;
while pixels.len() < 80 {
filler = filler.wrapping_add(1);
pixels.push(filler);
}
let greedy = tokenize_lz77_inner(&pixels, 0);
let lazy1 = tokenize_lz77_inner(&pixels, 1);
let lazy2 = tokenize_lz77_inner(&pixels, 2);
let copies = |toks: &[Token]| -> usize {
toks.iter()
.filter(|t| matches!(t, Token::Copy { .. }))
.count()
};
let coverage = |toks: &[Token]| -> usize {
toks.iter()
.map(|t| match *t {
Token::Literal(_) => 1,
Token::CacheRef { .. } => 1,
Token::Copy { length, .. } => length,
})
.sum()
};
assert_eq!(coverage(&greedy), pixels.len());
assert_eq!(coverage(&lazy1), pixels.len());
assert_eq!(coverage(&lazy2), pixels.len());
let g_c = copies(&greedy);
let l1_c = copies(&lazy1);
let l2_c = copies(&lazy2);
eprintln!(
"[round-157] depth-2 trap fixture: greedy tokens={} (copies={}), \
depth-1 tokens={} (copies={}), depth-2 tokens={} (copies={}), \
copy delta vs depth-1={}",
greedy.len(),
g_c,
lazy1.len(),
l1_c,
lazy2.len(),
l2_c,
l1_c as i64 - l2_c as i64,
);
assert_eq!(
g_c, l1_c,
"round-157 fixture: depth-1 must agree with greedy here \
(no depth-1 swap fires) — greedy={g_c}, depth-1={l1_c}"
);
assert!(
l2_c < l1_c,
"round-157 depth-2 matcher must emit strictly fewer Copy \
tokens than the depth-1 matcher on the depth-2 trap \
fixture: depth-1 copies={l1_c} depth-2 copies={l2_c}\n\
depth-1 partition: {lazy1:?}\n\
depth-2 partition: {lazy2:?}"
);
let stream = encode_argb_literals_with_width(&pixels, pixels.len() as u32);
let w = pixels.len() as u32;
let h = 1u32;
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_157_depth2_never_increases_token_count_over_depth1() {
let shapes: &[(u32, u32)] = &[
(16, 16),
(20, 20),
(24, 24),
(32, 32),
(48, 48),
(16, 32),
(64, 16),
(40, 24),
];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0xFF;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let mut seed = 0xC0FFEE_u32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("noise", &noise),
("stripes", &stripes),
] {
let lazy1 = tokenize_lz77_inner(pixels, 1);
let lazy2 = tokenize_lz77_inner(pixels, 2);
assert!(
lazy2.len() <= lazy1.len(),
"round-157 depth-2 regression on {name} {w}x{h}: \
depth-1={} tokens, depth-2={} tokens",
lazy1.len(),
lazy2.len(),
);
let stream = encode_argb_literals_with_width(pixels, w);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-157 depth-2 round-trip mismatch on {name} {w}x{h}"
);
}
}
}
#[test]
fn round_158_depth3_lazy_match_round_trips_through_decoder() {
let w = 96u32;
let h = 16u32;
let mut seed = 0xDEAD_BEEF_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stream = encode_argb_with_predictor_chooser(&pixels, w, h);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
let stream_direct = encode_argb_literals_with_width(&pixels, w);
let header_direct = build_image_header(w, h, true);
let mut payload_direct = header_direct.to_vec();
payload_direct.extend_from_slice(&stream_direct);
let framed_direct =
build::build_webp_file(&payload_direct, ImageKind::Lossless, w, h).unwrap();
let img_direct = crate::decode_lossless_image(&framed_direct)
.unwrap()
.unwrap();
assert_eq!(img_direct.pixels(), pixels.as_slice());
}
#[test]
fn round_158_depth3_lazy_match_strictly_beats_depth2_on_trap_fixture() {
let p_ = 0xFF11_2200_u32;
let q_ = 0xFF22_3300_u32;
let r_ = 0xFF33_4400_u32;
let s_ = 0xFF44_5500_u32;
let t_ = 0xFF55_6600_u32;
let u_ = 0xFF66_7700_u32;
let v_ = 0xFF77_8800_u32;
let w_ = 0xFF88_9900_u32;
let x_ = 0xFF99_AA00_u32;
let y_ = 0xFFAA_BB00_u32;
let a_ = 0xFFBB_CC00_u32;
let b_ = 0xFFCC_DD00_u32;
let z01 = 0xFFEE_0001_u32;
let z02 = 0xFFEE_0002_u32;
let z03 = 0xFFEE_0003_u32;
let z04 = 0xFFEE_0004_u32;
let z05 = 0xFFEE_0005_u32;
let z06 = 0xFFEE_0006_u32;
let z07 = 0xFFEE_0007_u32;
let z08 = 0xFFEE_0008_u32;
let z09 = 0xFFEE_0009_u32;
let z10 = 0xFFEE_000A_u32;
let z11 = 0xFFEE_000B_u32;
let z12 = 0xFFEE_000C_u32;
let mut pixels: Vec<u32> = vec![
p_, q_, r_, s_, z01, z02, z03, q_, r_, s_, t_, z04, z05, z06, r_, s_, t_, u_, z07, z08, z09, s_, t_, u_, v_, w_, x_, y_, a_, b_, z10, z11, z12, p_, q_, r_, s_, t_, u_, v_, w_, x_, y_, a_, b_, ];
let mut filler = 0xFFF0_0000_u32;
while pixels.len() < 96 {
filler = filler.wrapping_add(1);
pixels.push(filler);
}
let greedy = tokenize_lz77_inner(&pixels, 0);
let lazy1 = tokenize_lz77_inner(&pixels, 1);
let lazy2 = tokenize_lz77_inner(&pixels, 2);
let lazy3 = tokenize_lz77_inner(&pixels, 3);
let copies = |toks: &[Token]| -> usize {
toks.iter()
.filter(|t| matches!(t, Token::Copy { .. }))
.count()
};
let coverage = |toks: &[Token]| -> usize {
toks.iter()
.map(|t| match *t {
Token::Literal(_) => 1,
Token::CacheRef { .. } => 1,
Token::Copy { length, .. } => length,
})
.sum()
};
assert_eq!(coverage(&greedy), pixels.len());
assert_eq!(coverage(&lazy1), pixels.len());
assert_eq!(coverage(&lazy2), pixels.len());
assert_eq!(coverage(&lazy3), pixels.len());
let g_c = copies(&greedy);
let l1_c = copies(&lazy1);
let l2_c = copies(&lazy2);
let l3_c = copies(&lazy3);
eprintln!(
"[round-158] depth-3 trap fixture: greedy tokens={} (copies={}), \
depth-1 tokens={} (copies={}), depth-2 tokens={} (copies={}), \
depth-3 tokens={} (copies={}), copy delta vs depth-2={}",
greedy.len(),
g_c,
lazy1.len(),
l1_c,
lazy2.len(),
l2_c,
lazy3.len(),
l3_c,
l2_c as i64 - l3_c as i64,
);
assert_eq!(
g_c, l1_c,
"round-158 fixture: depth-1 must agree with greedy here \
(no depth-1 swap fires) — greedy={g_c}, depth-1={l1_c}"
);
assert_eq!(
g_c, l2_c,
"round-158 fixture: depth-2 must agree with greedy here \
(no depth-2 swap fires) — greedy={g_c}, depth-2={l2_c}"
);
assert!(
l3_c < l2_c,
"round-158 depth-3 matcher must emit strictly fewer Copy \
tokens than the depth-2 matcher on the depth-3 trap \
fixture: depth-2 copies={l2_c} depth-3 copies={l3_c}\n\
depth-2 partition: {lazy2:?}\n\
depth-3 partition: {lazy3:?}"
);
let stream = encode_argb_literals_with_width(&pixels, pixels.len() as u32);
let w = pixels.len() as u32;
let h = 1u32;
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_158_depth3_never_increases_token_count_over_depth2() {
let shapes: &[(u32, u32)] = &[
(16, 16),
(20, 20),
(24, 24),
(32, 32),
(48, 48),
(16, 32),
(64, 16),
(40, 24),
];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0xFF;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let mut seed = 0xC0FFEE_u32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("noise", &noise),
("stripes", &stripes),
] {
let lazy2 = tokenize_lz77_inner(pixels, 2);
let lazy3 = tokenize_lz77_inner(pixels, 3);
assert!(
lazy3.len() <= lazy2.len(),
"round-158 depth-3 regression on {name} {w}x{h}: \
depth-2={} tokens, depth-3={} tokens",
lazy2.len(),
lazy3.len(),
);
let stream = encode_argb_literals_with_width(pixels, w);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-158 depth-3 round-trip mismatch on {name} {w}x{h}"
);
}
}
}
#[test]
fn round_163_depth4_lazy_match_round_trips_through_decoder() {
let w = 96u32;
let h = 16u32;
let mut seed = 0xFEED_FACE_u32;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stream = encode_argb_with_predictor_chooser(&pixels, w, h);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
let stream_direct = encode_argb_literals_with_width(&pixels, w);
let header_direct = build_image_header(w, h, true);
let mut payload_direct = header_direct.to_vec();
payload_direct.extend_from_slice(&stream_direct);
let framed_direct =
build::build_webp_file(&payload_direct, ImageKind::Lossless, w, h).unwrap();
let img_direct = crate::decode_lossless_image(&framed_direct)
.unwrap()
.unwrap();
assert_eq!(img_direct.pixels(), pixels.as_slice());
}
#[test]
fn round_163_depth4_guard_suppresses_long_run_swap() {
let a_ = 0xFF10_2030_u32;
let b_ = 0xFF40_5060_u32;
let c_ = 0xFF70_8090_u32;
let d_ = 0xFFA0_B0C0_u32;
let motif = [a_, b_, c_, d_];
let mut pixels: Vec<u32> = Vec::with_capacity(512);
for i in 0..512 {
pixels.push(motif[i & 3]);
}
let lazy3 = tokenize_lz77_inner(&pixels, 3);
let lazy4 = tokenize_lz77_inner(&pixels, 4);
assert_eq!(
lazy3,
lazy4,
"round-163 depth-4 guard should suppress the depth-4 probe \
on a long-run fixture (every depth-3 best `>= DEPTH4_GUARD_THRESHOLD == {}`), \
producing the identical depth-3 partition; depth-3={} tokens, \
depth-4={} tokens",
DEPTH4_GUARD_THRESHOLD,
lazy3.len(),
lazy4.len(),
);
let coverage = |toks: &[Token]| -> usize {
toks.iter()
.map(|t| match *t {
Token::Literal(_) => 1,
Token::CacheRef { .. } => 1,
Token::Copy { length, .. } => length,
})
.sum()
};
assert_eq!(coverage(&lazy3), pixels.len());
assert_eq!(coverage(&lazy4), pixels.len());
let w = pixels.len() as u32;
let h = 1u32;
let stream = encode_argb_literals_with_width(&pixels, w);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(img.pixels(), pixels.as_slice());
}
#[test]
fn round_163_depth4_never_increases_token_count_over_depth3() {
let shapes: &[(u32, u32)] = &[
(16, 16),
(20, 20),
(24, 24),
(32, 32),
(48, 48),
(16, 32),
(64, 16),
(40, 24),
];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0xFF;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let mut seed = 0xBADD_CAFE_u32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x00FF_FFFF)
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("noise", &noise),
("stripes", &stripes),
] {
let lazy3 = tokenize_lz77_inner(pixels, 3);
let lazy4 = tokenize_lz77_inner(pixels, 4);
assert!(
lazy4.len() <= lazy3.len(),
"round-163 depth-4 regression on {name} {w}x{h}: \
depth-3={} tokens, depth-4={} tokens",
lazy3.len(),
lazy4.len(),
);
let stream = encode_argb_literals_with_width(pixels, w);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-163 depth-4 round-trip mismatch on {name} {w}x{h}"
);
}
}
}
#[test]
fn round_159_pick_block_mode_with_hint_swaps_on_tie() {
let w = 8usize;
let h = 8usize;
let pixels = vec![0xff50_6070u32; w * h];
let baseline = pick_block_mode_with_hint(&pixels, w, h, 0, 0, w, h, None);
let baseline_cost = block_mode_cost(&pixels, w, h, 0, 0, w, h, baseline);
let mut tied_other: Option<u8> = None;
for m in 0u8..=13 {
if m == baseline {
continue;
}
let c = block_mode_cost(&pixels, w, h, 0, 0, w, h, m);
if c == baseline_cost {
tied_other = Some(m);
break;
}
}
let other = tied_other
.expect("a solid-fill block has at least two modes tied at minimal residual cost");
let with_hint = pick_block_mode_with_hint(&pixels, w, h, 0, 0, w, h, Some(other));
assert_eq!(
with_hint, other,
"round-159 tie-break did not adopt the preferred mode: \
baseline={baseline}, other={other}, returned={with_hint}"
);
}
#[test]
fn round_159_pick_block_mode_with_hint_keeps_best_when_hint_worse() {
let w = 16usize;
let h = 16usize;
let pixels: Vec<u32> = (0..(w * h))
.map(|i| {
let x = (i % w) as u32;
let y = (i / w) as u32;
let v = (x + 2 * y) & 0xff;
0xff00_0000 | (v << 16) | (v << 8) | v
})
.collect();
let baseline = pick_block_mode_with_hint(&pixels, w, h, 0, 0, w, h, None);
let baseline_cost = block_mode_cost(&pixels, w, h, 0, 0, w, h, baseline);
let mut worse: Option<u8> = None;
for m in 0u8..=13 {
let c = block_mode_cost(&pixels, w, h, 0, 0, w, h, m);
if c > baseline_cost {
worse = Some(m);
break;
}
}
let worse = worse
.expect("test premise: the 2-D ramp should produce at least one strictly-worse mode");
let with_hint = pick_block_mode_with_hint(&pixels, w, h, 0, 0, w, h, Some(worse));
assert_eq!(
with_hint, baseline,
"round-159 tie-break must not adopt a strictly-worse hint \
(baseline={baseline}, worse-hint={worse})"
);
}
fn pre_round_159_build_predictor_image(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
) -> (Vec<u32>, u32, u32) {
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(width, block);
let th = predictor_div_round_up(height, block);
let mut img = Vec::with_capacity((tw * th) as usize);
let w = width as usize;
let h = height as usize;
let bsz = block as usize;
for by in 0..th as usize {
for bx in 0..tw as usize {
let x0 = bx * bsz;
let y0 = by * bsz;
let mode = pick_block_mode_with_hint(pixels, w, h, x0, y0, bsz, bsz, None);
img.push(0xff00_0000 | ((mode as u32) << 8));
}
}
(img, tw, th)
}
#[test]
fn round_159_predictor_image_tie_break_is_cost_neutral() {
let shapes: &[(u32, u32, u8)] = &[
(32, 32, 4),
(48, 48, 4),
(64, 32, 4),
(32, 64, 4),
(24, 24, 3),
];
for &(w, h, size_bits) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0x0F;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [("gradient", &gradient), ("stripes", &stripes)] {
let (pre_img, _, _) = pre_round_159_build_predictor_image(pixels, w, h, size_bits);
let (post_img, _, _) = build_predictor_image(pixels, w, h, size_bits);
assert_eq!(
pre_img.len(),
post_img.len(),
"pre/post mode-image length differs on {name} {w}x{h} size_bits={size_bits}"
);
let block = 1u32 << size_bits;
let tw = predictor_div_round_up(w, block) as usize;
let bsz = block as usize;
let wu = w as usize;
let hu = h as usize;
for (idx, (pre_px, post_px)) in pre_img.iter().zip(post_img.iter()).enumerate() {
let bx = idx % tw;
let by = idx / tw;
let x0 = bx * bsz;
let y0 = by * bsz;
let pre_mode = ((pre_px >> 8) & 0xff) as u8;
let post_mode = ((post_px >> 8) & 0xff) as u8;
let pre_cost = block_mode_cost(pixels, wu, hu, x0, y0, bsz, bsz, pre_mode);
let post_cost = block_mode_cost(pixels, wu, hu, x0, y0, bsz, bsz, post_mode);
assert_eq!(
pre_cost, post_cost,
"round-159 tie-break changed residual cost on {name} {w}x{h} \
block=({bx},{by}): pre mode {pre_mode} cost {pre_cost}, \
post mode {post_mode} cost {post_cost}"
);
}
}
}
}
#[test]
fn round_159_predictor_chooser_never_regresses() {
let shapes: &[(u32, u32)] = &[(16, 16), (24, 24), (32, 32), (48, 48), (32, 16), (24, 40)];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0x0F;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
let mut seed = 0xDEAD_BEEFu32;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
0xFF00_0000 | (seed & 0x000F_0F0F)
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("stripes", &stripes),
("low-noise", &noise),
] {
let post = encode_argb_with_predictor_chooser(pixels, w, h);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&post);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-159 round-trip mismatch on {name} {w}x{h}"
);
let pre = encode_argb_with_predictor_chooser_no_r159_hint(pixels, w, h);
assert!(
post.len() <= pre.len(),
"round-159 chooser regressed on {name} {w}x{h}: \
pre={} B post={} B",
pre.len(),
post.len(),
);
}
}
}
#[test]
fn round_159_predictor_candidate_strictly_beats_no_hint_on_some_fixture() {
let w = 48u32;
let h = 48u32;
let size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let mut found_strict_image = false;
let mut found_strict_bytes = false;
let mut best_savings: i64 = 0;
let mut seed_winner: u32 = 0;
for seed_init in [
0xCAFE_BABEu32,
0xC0FFEE00,
0xDEAD_BEEF,
0xFACE_F00D,
0xFEED_F00D,
0x1234_5678,
0xABCD_1234,
0x90AB_CDEF,
0x5A5A_5A5A,
0xA5A5_A5A5,
0xBA5E_BA11,
0xB16B_00B5,
] {
let solid = 0xff60_8050u32;
let mut pixels = vec![solid; (w * h) as usize];
let mut s = seed_init;
for y in 0..8u32 {
for x in 0..8u32 {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
let v = (s & 0x0007_0707) | 0xFF00_0000;
pixels[(y * w + x) as usize] = v;
}
}
let (pre_img, _, _) = pre_round_159_build_predictor_image(&pixels, w, h, size_bits);
let (post_img, _, _) = build_predictor_image(&pixels, w, h, size_bits);
let pre_modes: Vec<u8> = pre_img.iter().map(|p| ((p >> 8) & 0xff) as u8).collect();
let post_modes: Vec<u8> = post_img.iter().map(|p| ((p >> 8) & 0xff) as u8).collect();
let pre_distinct: std::collections::BTreeSet<u8> = pre_modes.iter().copied().collect();
let post_distinct: std::collections::BTreeSet<u8> =
post_modes.iter().copied().collect();
if post_distinct.len() < pre_distinct.len() {
found_strict_image = true;
let post = encode_with_predictor(&pixels, w, h, size_bits, None, w);
let pre = encode_with_predictor_no_r159_hint(&pixels, w, h, size_bits, None, w);
let saved = pre.len() as i64 - post.len() as i64;
if saved > best_savings {
best_savings = saved;
seed_winner = seed_init;
}
if post.len() < pre.len() {
found_strict_bytes = true;
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&post);
let framed =
build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-159 strict-beat predictor candidate round-trip mismatch on \
seed=0x{seed_init:08x}"
);
eprintln!(
"[round-159] strict-beat predictor candidate: seed=0x{seed_init:08x}, \
pre modes={pre_modes:?} post modes={post_modes:?} (distinct \
pre={} post={}), pre={} B post={} B, saved={saved} B",
pre_distinct.len(),
post_distinct.len(),
pre.len(),
post.len(),
);
}
assert!(
post.len() <= pre.len(),
"round-159 tie-break regressed on seed=0x{seed_init:08x}: \
pre={} B post={} B",
pre.len(),
post.len(),
);
}
}
assert!(
found_strict_image,
"round-159 sweep did not produce a single strictly-more-uniform mode image \
— the hint propagation never fired across the fixture set"
);
assert!(
found_strict_bytes,
"round-159 sweep found a strict mode-image reduction but never a strict byte \
reduction; entropy savings stayed within the LSB packing slack \
(best_savings={best_savings} on seed=0x{seed_winner:08x})"
);
}
fn encode_argb_with_predictor_chooser_no_r159_hint(
pixels: &[u32],
width: u32,
height: u32,
) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let mut pred_single_block_size_bits: u8 = pred_size_bits;
while pred_single_block_size_bits < 9
&& ((1u32 << pred_single_block_size_bits) < width
|| (1u32 << pred_single_block_size_bits) < height)
{
pred_single_block_size_bits += 1;
}
let try_pred_single_block = pred_single_block_size_bits != pred_size_bits;
let mut pred_candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_predictor_no_r159_hint(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
)
})];
if try_pred_single_block {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_no_r159_hint(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in pred_candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
fn encode_with_predictor_no_r159_hint(
pixels: &[u32],
width: u32,
height: u32,
size_bits: u8,
cache_code_bits: Option<u32>,
image_width: u32,
) -> Vec<u8> {
let mut w = BitWriter::new();
w.write_bit(true);
w.write_bits(crate::vp8l_stream::TransformType::Predictor as u32, 2);
debug_assert!((2..=9).contains(&size_bits));
w.write_bits((size_bits - 2) as u32, 3);
let (predictor_image, tw, _th) =
pre_round_159_build_predictor_image(pixels, width, height, size_bits);
write_entropy_coded_image_literals(&mut w, &predictor_image);
w.write_bit(false);
let mut residuals = vec![0u32; pixels.len()];
apply_forward_predictor(
pixels,
&mut residuals,
width,
height,
&predictor_image,
tw,
size_bits,
);
let mut tokens = tokenize_lz77(&residuals);
if let Some(bits) = cache_code_bits {
tokens = cacheify_tokens(&tokens, &residuals, bits);
}
write_spatially_coded_image(&mut w, &tokens, cache_code_bits, image_width);
w.into_bytes()
}
#[test]
fn round_160_pick_block_mode_with_hint_slack_swaps_within_budget() {
let solid = 0xff60_8050u32;
let pixels: Vec<u32> = vec![solid; 16];
let strict = pick_block_mode_with_hint(&pixels, 4, 4, 0, 0, 4, 4, Some(7));
let slack0 = pick_block_mode_with_hint_slack(&pixels, 4, 4, 0, 0, 4, 4, Some(7), 0);
assert_eq!(
strict, slack0,
"slack=0 must be byte-identical to the round-159 strict tie-break"
);
assert_eq!(
slack0, 7,
"preferred tied mode must win on slack=0 when cost is equal"
);
let mut big = vec![0xff00_0000u32; 64];
for y in 4..8u32 {
for x in 0..8u32 {
big[(y * 8 + x) as usize] = 0xff01_0101;
}
}
let best_default = pick_block_mode_with_hint(&big, 8, 8, 0, 4, 4, 4, None);
let best_cost = block_mode_cost(&big, 8, 8, 0, 4, 4, 4, best_default);
let mut preferred: u8 = u8::MAX;
let mut pref_cost: u64 = u64::MAX;
for m in 0u8..=13 {
if m == best_default {
continue;
}
let c = block_mode_cost(&big, 8, 8, 0, 4, 4, 4, m);
if c > best_cost && c < pref_cost {
preferred = m;
pref_cost = c;
}
}
if preferred != u8::MAX {
let extra = pref_cost - best_cost;
let strict = pick_block_mode_with_hint(&big, 8, 8, 0, 4, 4, 4, Some(preferred));
assert_eq!(
strict, best_default,
"strict round-159 tie-break must NOT swap when costs differ"
);
if extra > 0 {
let slack_too_small = pick_block_mode_with_hint_slack(
&big,
8,
8,
0,
4,
4,
4,
Some(preferred),
extra - 1,
);
assert_eq!(
slack_too_small, best_default,
"slack < (pref_cost - best_cost) must NOT swap"
);
}
let slack_exact =
pick_block_mode_with_hint_slack(&big, 8, 8, 0, 4, 4, 4, Some(preferred), extra);
assert_eq!(
slack_exact, preferred,
"slack >= (pref_cost - best_cost) must accept the preferred mode swap"
);
}
}
#[test]
fn round_160_slack_zero_matches_round_159_baseline() {
let shapes: &[(u32, u32, u8)] = &[
(32, 32, 4),
(48, 48, 4),
(64, 32, 4),
(32, 64, 4),
(24, 24, 3),
];
for &(w, h, size_bits) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0x0F;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
for (name, pixels) in [("gradient", &gradient), ("stripes", &stripes)] {
let (r159_img, _, _) = build_predictor_image(pixels, w, h, size_bits);
let (r160_img, _, _) = build_predictor_image_with_slack(pixels, w, h, size_bits, 0);
assert_eq!(
r159_img, r160_img,
"slack=0 sub-image must equal r159 baseline on {name} {w}x{h} \
size_bits={size_bits}"
);
let r159_bytes = encode_with_predictor(pixels, w, h, size_bits, None, w);
let r160_bytes = encode_with_predictor_slack(pixels, w, h, size_bits, None, w, 0);
assert_eq!(
r159_bytes, r160_bytes,
"slack=0 encoded bytes must equal r159 baseline on {name} {w}x{h} \
size_bits={size_bits}"
);
}
}
}
#[test]
fn round_160_slack_predictor_round_trips_through_decoder() {
let w = 32u32;
let h = 32u32;
let size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let pixels: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let r = (x * 7) & 0xff;
let g = (y * 11) & 0xff;
let b = ((x ^ y) * 3) & 0xff;
0xFF00_0000 | (r << 16) | (g << 8) | b
})
.collect();
let block_pixels: u64 = (1u64 << size_bits) * (1u64 << size_bits);
for slack in [0, block_pixels, 2 * block_pixels, 8 * block_pixels] {
let stream = encode_with_predictor_slack(&pixels, w, h, size_bits, None, w, slack);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&stream);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-160 slack={slack} predictor candidate failed end-to-end round-trip"
);
}
}
#[test]
fn round_160_chooser_never_regresses_vs_round_159() {
let shapes: &[(u32, u32)] = &[(32, 32), (48, 48), (32, 64), (64, 32), (24, 24)];
for &(w, h) in shapes {
let gradient: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
let y = (i as u32) / w;
let g = (x + y) & 0x0F;
0xFF00_0000 | (g << 16) | (g << 8) | g
})
.collect();
let stripes: Vec<u32> = (0..(w * h) as usize)
.map(|i| {
let x = (i as u32) % w;
match x % 4 {
0 => 0xFFAA_5500,
1 => 0xFF55_AA00,
2 => 0xFF00_55AA,
_ => 0xFF55_00AA,
}
})
.collect();
let mut s: u32 = 0xCAFE_BABE;
let noise: Vec<u32> = (0..(w * h) as usize)
.map(|_| {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
0xFF00_0000 | (s & 0x00FF_FFFF)
})
.collect();
for (name, pixels) in [
("gradient", &gradient),
("stripes", &stripes),
("noise", &noise),
] {
let r159 = encode_argb_with_predictor_chooser_no_r160_slack(pixels, w, h);
let r160 = encode_argb_with_predictor_chooser(pixels, w, h);
assert!(
r160.len() <= r159.len(),
"round-160 chooser regressed on {name} {w}x{h}: r159={} B r160={} B",
r159.len(),
r160.len()
);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&r160);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-160 chooser output failed end-to-end round-trip on \
{name} {w}x{h}"
);
}
}
}
#[test]
fn round_160_slack_candidate_strictly_beats_strict_on_some_fixture() {
let w = 128u32;
let h = 128u32;
let size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let mut found = false;
let mut best_savings: i64 = 0;
let mut seed_winner: u32 = 0;
let mut slack_winner: u64 = 0;
let block_pixels: u64 = (1u64 << size_bits) * (1u64 << size_bits);
let slack_candidates: &[u64] = &[
1,
4,
16,
64,
block_pixels,
2 * block_pixels,
4 * block_pixels,
];
for seed_init in [
0xCAFE_BABEu32,
0xC0FFEE00,
0xDEAD_BEEF,
0xFACE_F00D,
0xFEED_F00D,
0x1234_5678,
0xABCD_1234,
0x90AB_CDEF,
0x5A5A_5A5A,
0xA5A5_A5A5,
0xBA5E_BA11,
0xB16B_00B5,
0x00DD_BA11,
0xC1AB_AB00,
0xDEAF_BABE,
0xCABB_A6E0,
0x1337_C0DE,
0xABAD_CAFE,
0xBADF_00D0,
0x8BAD_F00D,
] {
let solid = 0xff60_8050u32;
let mut pixels = vec![solid; (w * h) as usize];
let mut s = seed_init;
for y in 0..6u32 {
for x in 0..6u32 {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
pixels[(y * w + x) as usize] = (s & 0x0003_0303) | 0xFF60_8050;
}
}
for y in 20..30u32 {
for x in 20..30u32 {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
pixels[(y * w + x) as usize] = (s & 0x0007_0707) | 0xFF60_8050;
}
}
for _ in 0..32u32 {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
let px = (s >> 8) % w;
let py = (s >> 16) % h;
pixels[(py * w + px) as usize] = (s & 0x0001_0101) | 0xFF60_8050;
}
let strict_bytes = encode_with_predictor(&pixels, w, h, size_bits, None, w);
let mut best_slack_bytes = strict_bytes.clone();
let mut best_slack_value: u64 = 0;
for &slack in slack_candidates {
let bytes = encode_with_predictor_slack(&pixels, w, h, size_bits, None, w, slack);
if bytes.len() < best_slack_bytes.len() {
best_slack_bytes = bytes;
best_slack_value = slack;
}
}
if best_slack_bytes.len() < strict_bytes.len() {
let saved = strict_bytes.len() as i64 - best_slack_bytes.len() as i64;
if saved > best_savings {
best_savings = saved;
seed_winner = seed_init;
slack_winner = best_slack_value;
}
if !found {
found = true;
}
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&best_slack_bytes);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-160 strict-beat predictor candidate round-trip mismatch on \
seed=0x{seed_init:08x} slack={best_slack_value}"
);
eprintln!(
"[round-160] slack-cost strict-beat: seed=0x{seed_init:08x}, \
slack={best_slack_value}, strict={} B slack={} B saved={saved} B",
strict_bytes.len(),
best_slack_bytes.len(),
);
}
let r159 = encode_argb_with_predictor_chooser_no_r160_slack(&pixels, w, h);
let r160 = encode_argb_with_predictor_chooser(&pixels, w, h);
assert!(
r160.len() <= r159.len(),
"round-160 chooser regressed on seed 0x{seed_init:08x}: \
r159={} B r160={} B",
r159.len(),
r160.len()
);
}
assert!(
found,
"round-160 slack-cost sweep did not produce a single strict byte reduction \
across the seeded fixture set; the new slack candidates never won \
(best_savings={best_savings} on seed=0x{seed_winner:08x} slack={slack_winner})"
);
}
fn encode_argb_with_predictor_chooser_no_r160_slack(
pixels: &[u32],
width: u32,
height: u32,
) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let mut pred_single_block_size_bits: u8 = pred_size_bits;
while pred_single_block_size_bits < 9
&& ((1u32 << pred_single_block_size_bits) < width
|| (1u32 << pred_single_block_size_bits) < height)
{
pred_single_block_size_bits += 1;
}
let try_pred_single_block = pred_single_block_size_bits != pred_size_bits;
let mut pred_candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_predictor(pixels, width, height, pred_size_bits, cache_bits, width)
})];
if try_pred_single_block {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in pred_candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
fn encode_argb_with_predictor_chooser_no_r161_entropy(
pixels: &[u32],
width: u32,
height: u32,
) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let mut pred_single_block_size_bits: u8 = pred_size_bits;
while pred_single_block_size_bits < 9
&& ((1u32 << pred_single_block_size_bits) < width
|| (1u32 << pred_single_block_size_bits) < height)
{
pred_single_block_size_bits += 1;
}
let try_pred_single_block = pred_single_block_size_bits != pred_size_bits;
let mut pred_candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_predictor(pixels, width, height, pred_size_bits, cache_bits, width)
})];
let pred_block_pixels: u64 = (1u64 << pred_size_bits) * (1u64 << pred_size_bits);
for slack in [
pred_block_pixels,
2 * pred_block_pixels,
4 * pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
slack,
)
}));
}
if try_pred_single_block {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
let single_pred_block_pixels: u64 =
(1u64 << pred_single_block_size_bits) * (1u64 << pred_single_block_size_bits);
for slack in [
single_pred_block_pixels,
2 * single_pred_block_pixels,
4 * single_pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
slack,
)
}));
}
}
for cand in pred_candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
#[test]
fn round_161_block_mode_entropy_cost_zero_on_zero_residual_block() {
let pixels = vec![0xff_00_00_00u32; 1];
for mode in 0u8..=13 {
let cost = block_mode_entropy_cost(&pixels, 1, 1, 0, 0, 1, 1, mode);
assert_eq!(
cost, 0,
"1×1 zero-residual block should produce zero-entropy cost under mode {mode}, got {cost}"
);
}
}
#[test]
fn round_161_block_mode_entropy_cost_zero_on_constant_residual_block() {
let w = 8usize;
let h = 8usize;
let pixels = vec![0xff_60_80_50u32; w * h];
for mode in 0u8..=13 {
let cost = block_mode_entropy_cost(&pixels, w, h, 4, 4, 4, 4, mode);
assert_eq!(
cost, 0,
"constant-residual mode {mode} on interior solid block should have zero entropy cost, got {cost}"
);
}
}
#[test]
fn round_161_entropy_cost_distinguishes_concentrated_from_scattered() {
let w = 16usize;
let h = 16usize;
let grey = 0xff_60_80_50u32;
let other = 0xff_70_90_60u32;
let mut pixels = vec![grey; w * h];
for y in 8..12 {
for x in 8..12 {
if x % 2 == 0 {
pixels[y * w + x] = other;
}
}
}
let concentrated = block_mode_entropy_cost(&pixels, w, h, 4, 4, 4, 4, 1);
let scattered = block_mode_entropy_cost(&pixels, w, h, 8, 8, 4, 4, 1);
assert!(
scattered > concentrated,
"scattered block should have higher entropy cost than concentrated: \
scattered={scattered}, concentrated={concentrated}"
);
assert_eq!(
concentrated, 0,
"concentrated (interior solid) block under mode 1 should have zero-entropy cost, \
got {concentrated}"
);
assert!(
scattered > 0,
"scattered block should have strictly positive entropy cost, got {scattered}"
);
}
#[test]
fn round_161_pick_block_mode_with_hint_entropy_honours_tie() {
let w = 8usize;
let h = 8usize;
let pixels = vec![0xff_60_80_50u32; w * h];
let no_hint = pick_block_mode_with_hint_entropy(&pixels, w, h, 4, 4, 4, 4, None);
assert_eq!(no_hint, 0);
let with_hint = pick_block_mode_with_hint_entropy(&pixels, w, h, 4, 4, 4, 4, Some(11));
assert_eq!(with_hint, 11);
let with_hint5 = pick_block_mode_with_hint_entropy(&pixels, w, h, 4, 4, 4, 4, Some(5));
assert_eq!(with_hint5, 5);
}
#[test]
fn round_161_entropy_predictor_round_trips_through_decoder() {
let w = 32u32;
let h = 32u32;
let mut pixels = vec![0xff_60_80_50u32; (w * h) as usize];
let mut s: u32 = 0xCAFE_BABE;
for y in 2..8u32 {
for x in 4..10u32 {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
pixels[(y * w + x) as usize] = (s & 0x0007_0707) | 0xff60_8050;
}
}
for cache_bits in [None, Some(2u32), Some(8u32)] {
let bytes = encode_with_predictor_entropy(
&pixels,
w,
h,
DEFAULT_PREDICTOR_SIZE_BITS,
cache_bits,
w,
);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&bytes);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"entropy predictor round-trip mismatch at cache_bits={cache_bits:?}"
);
}
}
#[test]
fn round_161_chooser_never_regresses_vs_round_160() {
let shapes: &[(u32, u32)] = &[(16, 16), (32, 32), (48, 48), (64, 32), (32, 64)];
for &(w, h) in shapes {
let solid = vec![0xff_60_80_50u32; (w * h) as usize];
let mut gradient = vec![0u32; (w * h) as usize];
for y in 0..h {
for x in 0..w {
let r = (x * 255 / w.max(1)) as u8;
let g = (y * 255 / h.max(1)) as u8;
gradient[(y * w + x) as usize] =
0xff00_0000 | ((r as u32) << 16) | ((g as u32) << 8) | 0x40;
}
}
let mut sparse = vec![0xff_70_70_70u32; (w * h) as usize];
let mut s: u32 = 0xDEAD_BEEF ^ (w * h);
for _ in 0..(w * h / 16) {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
let idx = ((s as usize) % sparse.len()) as usize;
sparse[idx] = (s & 0x0003_0303) | 0xff70_7070;
}
for (name, pixels) in &[
("solid", &solid),
("gradient", &gradient),
("sparse", &sparse),
] {
let r160 = encode_argb_with_predictor_chooser_no_r161_entropy(pixels, w, h);
let r161 = encode_argb_with_predictor_chooser(pixels, w, h);
assert!(
r161.len() <= r160.len(),
"round-161 chooser regressed on {name} {w}x{h}: \
r160={} B r161={} B",
r160.len(),
r161.len()
);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&r161);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-161 chooser output failed decode round-trip on {name} {w}x{h}"
);
}
}
}
#[test]
fn round_161_entropy_candidate_strictly_beats_l1_on_some_fixture() {
let w = 64u32;
let h = 64u32;
let size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let block_pixels: u64 = (1u64 << size_bits) * (1u64 << size_bits);
let mut found = false;
let mut best_savings: i64 = 0;
let mut seed_winner: u32 = 0;
let mut family_winner: &'static str = "";
for seed_init in [
0xCAFE_BABEu32,
0xC0FFEE00,
0xDEAD_BEEF,
0xFACE_F00D,
0xFEED_F00D,
0x1234_5678,
0xABCD_1234,
0x90AB_CDEF,
0x5A5A_5A5A,
0xA5A5_A5A5,
0xBA5E_BA11,
0xB16B_00B5,
0x00DD_BA11,
0xC1AB_AB00,
0xDEAF_BABE,
0xCABB_A6E0,
0x1337_C0DE,
0xABAD_CAFE,
0xBADF_00D0,
0x8BAD_F00D,
0xFEE1_DEAD,
0xDEFE_C8ED,
0xD15E_A5E0,
0x600D_F00D,
0xDEAD_C0DE,
0xBADC_0DED,
0xCAFE_F00D,
0xC0DE_F00D,
0xDEED_BEEF,
0xBEAD_F00D,
0x8008_5318,
0xD0DE_C0DE,
] {
let mut pixels = vec![0xff_60_80_50u32; (w * h) as usize];
let mut s = seed_init;
for y in 0..(h / 2) {
for x in 0..(w / 2) {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
let r = 0x40 + (x as u8 & 0x1f);
let g = 0x60 + ((y as u8) & 0x1f) + ((s & 1) as u8);
let b = 0x30 + ((x as u8 ^ y as u8) & 0x0f);
pixels[(y * w + x) as usize] =
0xff00_0000 | ((r as u32) << 16) | ((g as u32) << 8) | (b as u32);
}
}
for y in (h / 2)..h {
for x in (w / 2)..w {
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
if (s & 0x1f) == 0 {
let perturb = (s & 0x0f0f_0f0f) | 0xff60_8050;
pixels[(y * w + x) as usize] = perturb;
}
}
}
let strict_bytes = encode_with_predictor(&pixels, w, h, size_bits, None, w);
let mut best_l1_bytes = strict_bytes.clone();
for slack in [block_pixels, 2 * block_pixels, 4 * block_pixels] {
let bytes = encode_with_predictor_slack(&pixels, w, h, size_bits, None, w, slack);
if bytes.len() < best_l1_bytes.len() {
best_l1_bytes = bytes;
}
}
let entropy_bytes = encode_with_predictor_entropy(&pixels, w, h, size_bits, None, w);
if entropy_bytes.len() < best_l1_bytes.len() {
let saved = best_l1_bytes.len() as i64 - entropy_bytes.len() as i64;
if saved > best_savings {
best_savings = saved;
seed_winner = seed_init;
family_winner = "two-quadrant";
}
if !found {
found = true;
}
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&entropy_bytes);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels.as_slice(),
"round-161 entropy strict-beat predictor candidate round-trip mismatch on \
seed=0x{seed_init:08x}"
);
eprintln!(
"[round-161] entropy strict-beat: seed=0x{seed_init:08x}, \
best_l1={} B entropy={} B saved={saved} B",
best_l1_bytes.len(),
entropy_bytes.len(),
);
}
}
if !found {
let w2 = 16u32;
let h2 = 16u32;
let pixels2 = vec![0xff_80_80_80u32; (w2 * h2) as usize];
let l1_bytes = encode_with_predictor(&pixels2, w2, h2, size_bits, None, w2);
let entropy_bytes =
encode_with_predictor_entropy(&pixels2, w2, h2, size_bits, None, w2);
if entropy_bytes.len() < l1_bytes.len() {
let saved = l1_bytes.len() as i64 - entropy_bytes.len() as i64;
best_savings = saved;
family_winner = "solid-grey-16x16";
found = true;
let header = build_image_header(w2, h2, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&entropy_bytes);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w2, h2).unwrap();
let img = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
img.pixels(),
pixels2.as_slice(),
"round-161 entropy strict-beat solid-grey round-trip mismatch"
);
eprintln!(
"[round-161] entropy strict-beat (solid-grey 16x16): \
l1={} B entropy={} B saved={saved} B",
l1_bytes.len(),
entropy_bytes.len(),
);
}
}
assert!(
found,
"round-161 entropy candidate did not produce a single strict byte reduction \
across the seeded fixture set; the entropy cost never won \
(best_savings={best_savings} on seed=0x{seed_winner:08x} family={family_winner})"
);
}
fn encode_argb_with_predictor_chooser_no_r162_subaware(
pixels: &[u32],
width: u32,
height: u32,
) -> Vec<u8> {
let mut best = encode_argb_literals_with_width(pixels, width);
let pred_size_bits = DEFAULT_PREDICTOR_SIZE_BITS;
let ctx_size_bits = DEFAULT_COLOR_TRANSFORM_SIZE_BITS;
let pred_block = 1u32 << pred_size_bits;
let ctx_block = 1u32 << ctx_size_bits;
if width >= pred_block && height >= pred_block {
let mut pred_single_block_size_bits: u8 = pred_size_bits;
while pred_single_block_size_bits < 9
&& ((1u32 << pred_single_block_size_bits) < width
|| (1u32 << pred_single_block_size_bits) < height)
{
pred_single_block_size_bits += 1;
}
let try_pred_single_block = pred_single_block_size_bits != pred_size_bits;
let mut pred_candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_predictor(pixels, width, height, pred_size_bits, cache_bits, width)
})];
let pred_block_pixels: u64 = (1u64 << pred_size_bits) * (1u64 << pred_size_bits);
for slack in [
pred_block_pixels,
2 * pred_block_pixels,
4 * pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
slack,
)
}));
}
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_entropy(
pixels,
width,
height,
pred_size_bits,
cache_bits,
width,
)
}));
if try_pred_single_block {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
let single_pred_block_pixels: u64 =
(1u64 << pred_single_block_size_bits) * (1u64 << pred_single_block_size_bits);
for slack in [
single_pred_block_pixels,
2 * single_pred_block_pixels,
4 * single_pred_block_pixels,
] {
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_slack(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
slack,
)
}));
}
pred_candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_predictor_entropy(
pixels,
width,
height,
pred_single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in pred_candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if width >= ctx_block && height >= ctx_block {
let mut single_block_size_bits: u8 = ctx_size_bits;
while single_block_size_bits < 9
&& ((1u32 << single_block_size_bits) < width
|| (1u32 << single_block_size_bits) < height)
{
single_block_size_bits += 1;
}
let try_single_block = single_block_size_bits != ctx_size_bits;
let mut candidates: Vec<Vec<u8>> = vec![select_best_cache_bits(|cache_bits| {
encode_with_color_transform(pixels, width, height, ctx_size_bits, cache_bits, width)
})];
if try_single_block {
candidates.push(select_best_cache_bits(|cache_bits| {
encode_with_color_transform(
pixels,
width,
height,
single_block_size_bits,
cache_bits,
width,
)
}));
}
for cand in candidates {
if cand.len() < best.len() {
best = cand;
}
}
}
if collect_palette(pixels).is_some() {
let ci_best = select_best_cache_bits(|cache_bits| {
encode_with_color_indexing(pixels, width, height, cache_bits)
.expect("palette feasibility already confirmed")
});
if ci_best.len() < best.len() {
best = ci_best;
}
}
if let Some(mp_best) = sweep_meta_prefix_candidate(pixels, width, height) {
if mp_best.len() < best.len() {
best = mp_best;
}
}
best
}
#[test]
fn round_162_sub_image_mode_cost_delta_zero_on_first_add() {
let hist = [0u32; 14];
for mode in 0u8..=13 {
let delta = sub_image_mode_cost_delta_milli(&hist, 0, mode);
assert_eq!(
delta, 0,
"first symbol add must produce zero Shannon delta; mode={mode} delta={delta}"
);
}
}
#[test]
fn round_162_sub_image_mode_cost_delta_grows_on_new_symbol() {
let mut hist = [0u32; 14];
hist[3] = 5;
let total = 5u32;
let same = sub_image_mode_cost_delta_milli(&hist, total, 3);
assert_eq!(
same, 0,
"adding same symbol to a single-mode histogram must not grow Shannon mass"
);
let different = sub_image_mode_cost_delta_milli(&hist, total, 7);
assert!(
different > 0,
"adding a new symbol to a single-mode histogram must grow Shannon mass; got 0"
);
assert!(
(3500..=4300).contains(&different),
"expected delta near 3900 milli-bits; got {different}"
);
}
#[test]
fn round_162_lambda_zero_byte_identical_to_round_161() {
let w = 32u32;
let h = 32u32;
let mut pixels = vec![0u32; (w * h) as usize];
for y in 0..h as usize {
for x in 0..w as usize {
let r = (x as u8).wrapping_mul(7);
let g = (y as u8).wrapping_mul(11);
let b = ((x + y) as u8).wrapping_mul(13);
pixels[y * w as usize + x] =
0xff00_0000 | ((r as u32) << 16) | ((g as u32) << 8) | (b as u32);
}
}
let r161 = encode_with_predictor_entropy(&pixels, w, h, 4, None, w);
let r162_lambda0 = encode_with_predictor_entropy_subaware(&pixels, w, h, 4, None, w, 0);
assert_eq!(
r161, r162_lambda0,
"lambda_milli == 0 must produce a byte-identical stream to round-161 entropy"
);
let r161_cached = encode_with_predictor_entropy(&pixels, w, h, 4, Some(6), w);
let r162_cached_lambda0 =
encode_with_predictor_entropy_subaware(&pixels, w, h, 4, Some(6), w, 0);
assert_eq!(
r161_cached, r162_cached_lambda0,
"lambda_milli == 0 must be byte-identical with cache_bits = Some(6)"
);
}
#[test]
fn round_162_pick_block_mode_subaware_honours_tie() {
let pixels = vec![0xff_00_00_00u32; 1];
let hist = [0u32; 14];
let chosen_no_hint = pick_block_mode_with_hint_entropy_subaware(
&pixels, 1, 1, 0, 0, 1, 1, None, &hist, 0, 4_000,
);
assert_eq!(
chosen_no_hint, 0,
"no-hint pick should fall back to lowest-tied mode (= 0)"
);
for hint in 0u8..=13 {
let chosen = pick_block_mode_with_hint_entropy_subaware(
&pixels,
1,
1,
0,
0,
1,
1,
Some(hint),
&hist,
0,
4_000,
);
assert_eq!(
chosen, hint,
"hint {hint} should win on a fully-tied block; got {chosen}"
);
}
}
#[test]
fn round_162_subaware_round_trips_through_decoder() {
let w = 32u32;
let h = 32u32;
let mut pixels = vec![0u32; (w * h) as usize];
for y in 0..h as usize {
for x in 0..w as usize {
let v = match (x < 16, y < 16) {
(true, true) => 0xff_00_00_00 | (((x + y) as u32 * 8) << 8),
(false, true) => {
let seed = (x.wrapping_mul(97) ^ y.wrapping_mul(53)) as u32;
0xff_00_00_00 | ((seed & 0xff) << 16) | (seed & 0xff00)
}
(true, false) => 0xff_80_80_80,
(false, false) => {
if x % 2 == 0 {
0xff_ff_ff_ff
} else {
0xff_00_00_00
}
}
};
pixels[y * w as usize + x] = v;
}
}
for lambda_milli in [1_000u64, 4_000u64, 16_000u64] {
for cache_bits in [None, Some(4u32), Some(8u32)] {
let payload = encode_with_predictor_entropy_subaware(
&pixels,
w,
h,
4,
cache_bits,
w,
lambda_milli,
);
let header = build_image_header(w, h, true);
let mut bytes = header.to_vec();
bytes.extend_from_slice(&payload);
let framed = build::build_webp_file(&bytes, ImageKind::Lossless, w, h).unwrap();
let decoded = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip mismatch lambda_milli={lambda_milli} cache_bits={cache_bits:?}"
);
}
}
}
#[test]
fn round_162_chooser_never_regresses_vs_round_161() {
let shapes: &[(u32, u32)] = &[(16, 16), (24, 32), (32, 24), (48, 48), (64, 32)];
for &(w, h) in shapes {
for fixture_kind in 0..3u32 {
let mut pixels = vec![0u32; (w * h) as usize];
for y in 0..h as usize {
for x in 0..w as usize {
let v = match fixture_kind {
0 => 0xff_00_00_00 | (((x ^ y) as u32 * 3) & 0xff),
1 => {
let seed =
(x.wrapping_mul(2654435761).wrapping_add(y) & 0xff) as u32;
0xff_00_00_00 | (seed << 16) | seed
}
_ => {
if (x + y) % 5 < 2 {
0xff_a0_a0_a0
} else {
0xff_60_60_60
}
}
};
pixels[y * w as usize + x] = v;
}
}
let baseline = encode_argb_with_predictor_chooser_no_r162_subaware(&pixels, w, h);
let r162 = encode_argb_with_predictor_chooser(&pixels, w, h);
assert!(
r162.len() <= baseline.len(),
"round-162 chooser regressed at shape={w}×{h} fixture={fixture_kind}: \
baseline={} B r162={} B",
baseline.len(),
r162.len()
);
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&r162);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let decoded = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip mismatch at shape={w}×{h} fixture={fixture_kind}"
);
}
}
}
#[test]
fn round_162_subaware_isolated_strictly_beats_round_161_on_some_fixture() {
let shapes: &[(u32, u32)] = &[(64, 64), (128, 128), (256, 128), (96, 96), (160, 80)];
let lambda_to_test: u64 = 64_000;
let mut wins = 0u32;
let mut max_savings: i64 = 0;
let mut max_savings_shape: (u32, u32) = (0, 0);
for &(w, h) in shapes {
let mut pixels = vec![0u32; (w * h) as usize];
for y in 0..h {
for x in 0..w {
let r = (x * 255 / w.max(1)) as u8;
let g = (y * 255 / h.max(1)) as u8;
pixels[(y * w + x) as usize] =
0xff00_0000 | ((r as u32) << 16) | ((g as u32) << 8) | 0x40;
}
}
let r161 = encode_with_predictor_entropy(&pixels, w, h, 4, None, w);
let r162 =
encode_with_predictor_entropy_subaware(&pixels, w, h, 4, None, w, lambda_to_test);
assert!(
r162.len() <= r161.len(),
"round-162 isolated candidate REGRESSED on gradient {w}x{h}: \
r161={} B r162={} B",
r161.len(),
r162.len()
);
let saved = r161.len() as i64 - r162.len() as i64;
if r162.len() < r161.len() {
wins += 1;
if saved > max_savings {
max_savings = saved;
max_savings_shape = (w, h);
}
let header = build_image_header(w, h, true);
let mut payload = header.to_vec();
payload.extend_from_slice(&r162);
let framed = build::build_webp_file(&payload, ImageKind::Lossless, w, h).unwrap();
let decoded = crate::decode_lossless_image(&framed).unwrap().unwrap();
assert_eq!(
decoded.pixels(),
pixels.as_slice(),
"round-trip mismatch on gradient strict-beat {w}x{h}"
);
eprintln!(
"[round-162] isolated strict-beat (gradient {w}x{h}, lambda={lambda_to_test}): \
r161={} B r162={} B saved={saved} B ({:.1}% reduction)",
r161.len(),
r162.len(),
100.0 * saved as f64 / r161.len() as f64
);
} else {
eprintln!(
"[round-162] tie (gradient {w}x{h}, lambda={lambda_to_test}): \
r161={} B r162={} B (no regression)",
r161.len(),
r162.len()
);
}
}
assert!(
wins >= 3,
"round-162 isolated candidate strictly beat round-161 on only {wins}/{} gradient \
fixtures; expected at least 3 strict wins to demonstrate the sub-image cost is \
doing real work",
shapes.len()
);
eprintln!(
"[round-162] isolated sub-image-aware: {wins}/{} gradient fixtures strict-won; \
headline savings = {max_savings} B on {}x{}",
shapes.len(),
max_savings_shape.0,
max_savings_shape.1
);
}
}