use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::encode_image::AlphaPlane;
use crate::entropy::{
HuffmanNode, OwnedEntropyCode, Token, optimize_entropy_code, pack_signed, write_entropy_code,
write_prefix_codes, write_token,
};
const TREE_CTX_SPLITVAL: u32 = 0;
const TREE_CTX_PROPERTY: u32 = 1;
const TREE_CTX_PREDICTOR: u32 = 2;
const TREE_CTX_OFFSET: u32 = 3;
const TREE_CTX_MULTIPLIER_LOG: u32 = 4;
const TREE_CTX_MULTIPLIER_BITS: u32 = 5;
const NUM_TREE_CONTEXTS: usize = 6;
const PREDICTOR_GRADIENT: u32 = 5;
const GROUP_DIM: usize = 256;
pub(crate) fn write_lfglobal_alpha_section(
alpha: &AlphaPlane,
xsize: usize,
ysize: usize,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
assert_eq!(alpha.len(), xsize * ysize);
if xsize <= GROUP_DIM && ysize <= GROUP_DIM {
write_group_header_local_tree(w);
let tokens = tokenize_channel(alpha, xsize, ysize, 0, 0, xsize, ysize, xsize);
let pixel_code = build_pixel_code(&tokens, scratch);
write_tree_and_pixel_histograms(&pixel_code, scratch, w);
let code_ref = pixel_code.as_ref();
for tok in &tokens {
write_token(*tok, &code_ref, w);
}
} else {
write_group_header_global_tree(w);
}
}
#[inline]
pub(crate) fn write_global_alpha_modular(
alpha: &AlphaPlane,
xsize: usize,
ysize: usize,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
write_lfglobal_alpha_section(alpha, xsize, ysize, scratch, w);
}
pub(crate) fn write_ac_group_alpha(
alpha: &AlphaPlane,
full_xsize: usize,
full_ysize: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
if full_xsize <= GROUP_DIM && full_ysize <= GROUP_DIM {
return;
}
let full_size = full_xsize
.checked_mul(full_ysize)
.expect("alpha dimensions overflow usize");
assert_eq!(alpha.len(), full_size);
assert!(x0 <= full_xsize && gw <= full_xsize - x0);
assert!(y0 <= full_ysize && gh <= full_ysize - y0);
let token_count = gw
.checked_mul(gh)
.expect("alpha group size overflows usize");
scratch.alpha_tokens.resize(token_count, Token::new(0, 0));
if token_count != 0 {
match alpha {
AlphaPlane::U8(data) => {
tokenize_ac_group_alpha(data, full_xsize, x0, y0, gw, gh, &mut scratch.alpha_tokens)
}
AlphaPlane::U16 { data, .. } => {
tokenize_ac_group_alpha(data, full_xsize, x0, y0, gw, gh, &mut scratch.alpha_tokens)
}
AlphaPlane::F32(data) => {
tokenize_ac_group_alpha(data, full_xsize, x0, y0, gw, gh, &mut scratch.alpha_tokens)
}
}
}
const NUM_CTX: usize = 2; let pixel_code = build_pixel_code_n(&scratch.alpha_tokens, NUM_CTX, &mut scratch.huffman_pool);
write_group_header_local_tree(w); write_split_tree(scratch, w); w.write(1, 0); write_entropy_code(&pixel_code.as_ref(), &mut scratch.huffman_pool, w); let code_ref = pixel_code.as_ref();
for tok in &scratch.alpha_tokens {
write_token(*tok, &code_ref, w);
}
}
trait AlphaSample: Copy {
const ZERO: Self;
fn to_i32(self) -> i32;
}
impl AlphaSample for u8 {
const ZERO: Self = 0;
#[inline]
fn to_i32(self) -> i32 {
self as i32
}
}
impl AlphaSample for u16 {
const ZERO: Self = 0;
#[inline]
fn to_i32(self) -> i32 {
self as i32
}
}
impl AlphaSample for i32 {
const ZERO: Self = 0;
#[inline]
fn to_i32(self) -> i32 {
self
}
}
#[inline]
fn alpha_token<T: AlphaSample>(v: T, w: T, n: T, nw: T) -> Token {
let v = v.to_i32();
let w = w.to_i32();
let n = n.to_i32();
let nw = nw.to_i32();
let grad = w + n - nw;
let pred = grad.clamp(w.min(n), w.max(n));
let context = if grad > 0 { 0 } else { 1 };
Token::new(context, pack_signed(v - pred))
}
#[inline]
fn tokenize_ac_group_alpha<T: AlphaSample>(
samples: &[T],
stride: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
dst: &mut [Token],
) {
debug_assert_ne!(gw, 0);
debug_assert_ne!(gh, 0);
debug_assert_eq!(dst.len(), gw * gh);
let mut src_rows = samples.chunks_exact(stride).skip(y0).take(gh);
let mut dst_rows = dst.chunks_exact_mut(gw);
let first = &src_rows.next().unwrap()[x0..x0 + gw];
let first_dst = dst_rows.next().unwrap();
first_dst[0] = alpha_token(first[0], T::ZERO, T::ZERO, T::ZERO);
for ((&v, &w), out) in first[1..]
.iter()
.zip(first[..gw - 1].iter())
.zip(first_dst[1..].iter_mut())
{
*out = alpha_token(v, w, T::ZERO, T::ZERO);
}
let mut north = first;
for (row, out) in src_rows.zip(dst_rows) {
let row = &row[x0..x0 + gw];
out[0] = alpha_token(row[0], T::ZERO, north[0], T::ZERO);
for ((((&v, &w), &n), &nw), out) in row[1..]
.iter()
.zip(row[..gw - 1].iter())
.zip(north[1..].iter())
.zip(north[..gw - 1].iter())
.zip(out[1..].iter_mut())
{
*out = alpha_token(v, w, n, nw);
}
north = row;
}
}
#[allow(dead_code)]
fn lz77_compress_alpha(tokens: &[Token]) -> Vec<crate::lz77_ac::AcLz> {
use crate::lz77_ac::{AcLz, LZ77_MIN_LENGTH};
let mut out: Vec<AcLz> = Vec::with_capacity(tokens.len());
let mut i = 0;
while i < tokens.len() {
let v = tokens[i].value;
out.push(AcLz::Lit {
context: tokens[i].context,
value: v,
});
let mut j = i + 1;
while j < tokens.len() && tokens[j].value == v {
j += 1;
}
let run_extra = (j - i - 1) as u32; if run_extra >= LZ77_MIN_LENGTH {
out.push(AcLz::Copy {
context: tokens[i + 1].context,
length_value: run_extra - LZ77_MIN_LENGTH,
});
i = j;
} else {
i += 1;
}
}
out
}
pub(crate) fn write_group_header_local_tree(w: &mut BitWriter) {
w.write(1, 0); w.write(1, 1); w.write(2, 0); }
fn write_group_header_global_tree(w: &mut BitWriter) {
w.write(1, 1); w.write(1, 1); w.write(2, 0); }
pub(crate) fn write_tree_and_pixel_histograms(
pixel_code: &OwnedEntropyCode,
scratch: &mut CoderScratch,
w: &mut BitWriter,
) {
let tree_tokens = [
Token::new(TREE_CTX_PROPERTY, 0),
Token::new(TREE_CTX_PREDICTOR, PREDICTOR_GRADIENT),
Token::new(TREE_CTX_OFFSET, pack_signed(0)),
Token::new(TREE_CTX_MULTIPLIER_LOG, 0),
Token::new(TREE_CTX_MULTIPLIER_BITS, 0),
];
let tree_code =
optimize_entropy_code(&tree_tokens, NUM_TREE_CONTEXTS, &mut scratch.huffman_pool);
let tree_code_ref = tree_code.as_ref();
w.write(1, 0); write_entropy_code(&tree_code_ref, &mut scratch.huffman_pool, w);
for tok in &tree_tokens {
write_token(*tok, &tree_code_ref, w);
}
w.write(1, 0); write_prefix_codes(
&pixel_code.prefix_codes,
&pixel_code.hybrid_uint_configs,
&mut scratch.huffman_pool,
w,
);
}
#[allow(dead_code)]
fn write_split_tree(scratch: &mut CoderScratch, w: &mut BitWriter) {
const PROP_GRAD: u32 = 9;
let tree_tokens = [
Token::new(TREE_CTX_PROPERTY, PROP_GRAD + 1),
Token::new(TREE_CTX_SPLITVAL, pack_signed(0)),
Token::new(TREE_CTX_PROPERTY, 0),
Token::new(TREE_CTX_PREDICTOR, PREDICTOR_GRADIENT),
Token::new(TREE_CTX_OFFSET, pack_signed(0)),
Token::new(TREE_CTX_MULTIPLIER_LOG, 0),
Token::new(TREE_CTX_MULTIPLIER_BITS, 0),
Token::new(TREE_CTX_PROPERTY, 0),
Token::new(TREE_CTX_PREDICTOR, PREDICTOR_GRADIENT),
Token::new(TREE_CTX_OFFSET, pack_signed(0)),
Token::new(TREE_CTX_MULTIPLIER_LOG, 0),
Token::new(TREE_CTX_MULTIPLIER_BITS, 0),
];
let tree_code =
optimize_entropy_code(&tree_tokens, NUM_TREE_CONTEXTS, &mut scratch.huffman_pool);
let tree_code_ref = tree_code.as_ref();
w.write(1, 0); write_entropy_code(&tree_code_ref, &mut scratch.huffman_pool, w);
for tok in &tree_tokens {
write_token(*tok, &tree_code_ref, w);
}
}
#[allow(dead_code)]
fn estimate_plain_bits(tokens: &[Token], code: &OwnedEntropyCode) -> u64 {
let code_ref = code.as_ref();
let mut bits: u64 = 0;
for t in tokens {
let (sym, nbits, _) = crate::entropy::uint_encode(t.value);
let cl = code_ref.context_map[t.context as usize] as usize;
let pc = &code_ref.prefix_codes[cl];
let d = if pc.single_symbol {
0
} else {
pc.depths[sym as usize] as u64
};
bits += d + nbits as u64;
}
bits
}
pub(crate) fn build_pixel_code(tokens: &[Token], scratch: &mut CoderScratch) -> OwnedEntropyCode {
build_pixel_code_n(tokens, 1, &mut scratch.huffman_pool)
}
fn build_pixel_code_n(
tokens: &[Token],
num_contexts: usize,
huffman_pool: &mut Vec<HuffmanNode>,
) -> OwnedEntropyCode {
let mut code = if num_contexts > 1 {
crate::entropy::build_entropy_code_no_cluster(tokens, num_contexts, huffman_pool)
} else {
optimize_entropy_code(tokens, num_contexts, huffman_pool)
};
for pc in &mut code.prefix_codes {
let mut nonzero = 0;
let mut idx = 0;
for (i, &d) in pc.depths.iter().enumerate() {
if d != 0 {
nonzero += 1;
idx = i;
if nonzero > 1 {
break;
}
}
}
if nonzero == 1 {
if idx == 0 {
pc.depths[idx] = 0;
pc.bits[idx] = 0;
} else {
pc.depths[0] = 1;
pc.bits[0] = 0;
pc.depths[idx] = 1;
pc.bits[idx] = 1;
}
}
pc.update_single_symbol();
}
code
}
#[inline]
pub(crate) fn gradient(w: i32, n: i32, nw: i32) -> i32 {
let lo = w.min(n);
let hi = w.max(n);
(w + n - nw).clamp(lo, hi)
}
fn tokenize_channel(
alpha: &AlphaPlane,
_full_xsize: usize,
_full_ysize: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
stride: usize,
) -> Vec<Token> {
let _ = _full_ysize;
let mut tokens = Vec::with_capacity(gw * gh);
for y in y0..y0 + gh {
for x in x0..x0 + gw {
let v = alpha.get_i32(y * stride + x);
let w_ = if x > 0 {
alpha.get_i32(y * stride + x - 1)
} else {
0
};
let n_ = if y > 0 {
alpha.get_i32((y - 1) * stride + x)
} else {
0
};
let nw_ = if x > 0 && y > 0 {
alpha.get_i32((y - 1) * stride + x - 1)
} else {
0
};
let pred = gradient(w_, n_, nw_);
tokens.push(Token::new(0, pack_signed(v - pred)));
}
}
tokens
}
#[cfg(test)]
mod tests {
use super::*;
use crate::encode_image::AlphaPlane;
fn check_ac_group_tokenization<T: AlphaSample>(
samples: &[T],
stride: usize,
x0: usize,
y0: usize,
gw: usize,
gh: usize,
) {
let mut actual = vec![Token::new(0, 0); gw * gh];
tokenize_ac_group_alpha(samples, stride, x0, y0, gw, gh, &mut actual);
for gy in 0..gh {
for gx in 0..gw {
let at = |x: usize, y: usize| samples[(y0 + y) * stride + x0 + x].to_i32();
let v = at(gx, gy);
let w = if gx == 0 { 0 } else { at(gx - 1, gy) };
let n = if gy == 0 { 0 } else { at(gx, gy - 1) };
let nw = if gx == 0 || gy == 0 {
0
} else {
at(gx - 1, gy - 1)
};
let pred = gradient(w, n, nw);
let expected =
Token::new(if w + n - nw > 0 { 0 } else { 1 }, pack_signed(v - pred));
let actual = &actual[gy * gw + gx];
assert_eq!(actual.context, expected.context);
assert_eq!(actual.value, expected.value);
}
}
}
#[test]
fn gradient_basic() {
assert_eq!(gradient(50, 50, 0), 50);
assert_eq!(gradient(50, 50, 100), 50);
assert_eq!(gradient(10, 20, 5), 20);
assert_eq!(gradient(10, 20, 25), 10);
assert_eq!(gradient(10, 20, 15), 15);
}
#[test]
fn tokenize_constant_zero() {
let chan = vec![0u8; 16 * 16];
let alpha = AlphaPlane::from_u8(chan);
let toks = tokenize_channel(&alpha, 16, 16, 0, 0, 16, 16, 16);
for t in &toks {
assert_eq!(t.value, 0);
}
}
#[test]
fn tokenize_ac_group_matches_scalar_for_all_sample_types() {
let u8_samples: Vec<u8> = (0..64).map(|v| ((v * 37 + 11) % 251) as u8).collect();
check_ac_group_tokenization(&u8_samples, 8, 2, 1, 5, 6);
check_ac_group_tokenization(&u8_samples, 8, 4, 3, 1, 1);
let u16_samples: Vec<u16> = (0..64).map(|v| ((v * 977 + 31) % 4096) as u16).collect();
check_ac_group_tokenization(&u16_samples, 8, 1, 2, 6, 5);
let i32_samples: Vec<i32> = (0..64).map(|v| (v * 43 + 17) % 257 - 128).collect();
check_ac_group_tokenization(&i32_samples, 8, 3, 1, 4, 7);
}
#[test]
fn write_alpha_small_emits_bytes() {
let mut w = BitWriter::new();
let chan = vec![128u8; 8 * 8];
let alpha = AlphaPlane::from_u8(chan);
let mut scratch = CoderScratch::default();
write_global_alpha_modular(&alpha, 8, 8, &mut scratch, &mut w);
let bits = w.bits_written();
w.zero_pad_to_byte();
assert!(w.into_bytes().len() > 0);
assert!(bits > 0);
}
#[test]
fn write_alpha_large_emits_header_only() {
let mut w = BitWriter::new();
let chan = vec![200u8; 512 * 400];
let alpha = AlphaPlane::from_u8(chan);
let mut scratch = CoderScratch::default();
write_lfglobal_alpha_section(&alpha, 512, 400, &mut scratch, &mut w);
assert_eq!(w.bits_written(), 4);
}
}