pub(super) const BLACK: u32 = 0xFF00_0000;
pub(super) const PREDICTOR_MODES: u32 = 14;
#[derive(Clone, Debug)]
pub(super) enum Transform {
Predictor(TileImage),
CrossColor(TileImage),
SubtractGreen,
ColorIndexing(Palette),
}
#[derive(Clone, Debug)]
pub(super) struct TileImage {
pub(super) width: usize,
pub(super) bits: u32,
pub(super) tiles: Vec<u32>,
}
impl TileImage {
fn at(&self, x: usize, y: usize) -> u32 {
let per_row = subsample(self.width, self.bits);
self.tiles[(y >> self.bits) * per_row + (x >> self.bits)]
}
}
#[derive(Clone, Debug)]
pub(super) struct Palette {
pub(super) width: usize,
pub(super) bits: u32,
pub(super) colors: Vec<u32>,
}
impl Palette {
pub(super) fn from_deltas(width: usize, bits: u32, deltas: &[u32]) -> Self {
let mut colors = Vec::with_capacity(1 << (8 >> bits));
let mut previous = 0;
for &delta in deltas {
previous = add_pixels(previous, delta);
colors.push(previous);
}
colors.resize(1 << (8 >> bits), 0);
Self {
width,
bits,
colors,
}
}
}
pub(super) fn subsample(size: usize, bits: u32) -> usize {
(size + (1 << bits) - 1) >> bits
}
impl Transform {
pub(super) fn invert(&self, mut pixels: Vec<u32>, width: usize) -> (Vec<u32>, usize) {
match self {
Self::Predictor(tiles) => {
unpredict(tiles, &mut pixels);
(pixels, width)
}
Self::CrossColor(tiles) => {
recorrelate(tiles, &mut pixels);
(pixels, width)
}
Self::SubtractGreen => {
for pixel in &mut pixels {
*pixel = add_green(*pixel);
}
(pixels, width)
}
Self::ColorIndexing(palette) => (unpack(palette, &pixels, width), palette.width),
}
}
}
pub(super) fn add_pixels(a: u32, b: u32) -> u32 {
let alpha_green = (a & 0xFF00_FF00).wrapping_add(b & 0xFF00_FF00);
let red_blue = (a & 0x00FF_00FF).wrapping_add(b & 0x00FF_00FF);
(alpha_green & 0xFF00_FF00) | (red_blue & 0x00FF_00FF)
}
fn average2(a: u32, b: u32) -> u32 {
(((a ^ b) & 0xFEFE_FEFE) >> 1) + (a & b)
}
fn channels(pixel: u32) -> [i32; 4] {
pixel.to_be_bytes().map(i32::from)
}
fn from_channels(channels: [i32; 4]) -> u32 {
u32::from_be_bytes(channels.map(|c| c.clamp(0, 255) as u8))
}
fn select(top: u32, left: u32, top_left: u32) -> u32 {
let [t, l, tl] = [top, left, top_left].map(channels);
let distance: i32 = (0..4)
.map(|i| (l[i] - tl[i]).abs() - (t[i] - tl[i]).abs())
.sum();
if distance <= 0 { top } else { left }
}
fn clamped_add_subtract_full(a: u32, b: u32, c: u32) -> u32 {
let [a, b, c] = [a, b, c].map(channels);
from_channels(std::array::from_fn(|i| a[i] + b[i] - c[i]))
}
fn clamped_add_subtract_half(a: u32, b: u32, c: u32) -> u32 {
let [average, c] = [average2(a, b), c].map(channels);
from_channels(std::array::from_fn(|i| {
average[i] + (average[i] - c[i]) / 2
}))
}
pub(super) fn sub_pixels(a: u32, b: u32) -> u32 {
let alpha_green = (a | 0x00FF_00FF).wrapping_sub(b & 0xFF00_FF00);
let red_blue = (a | 0xFF00_FF00).wrapping_sub(b & 0x00FF_00FF);
(alpha_green & 0xFF00_FF00) | (red_blue & 0x00FF_00FF)
}
pub(super) fn predict(mode: u32, pixels: &[u32], index: usize, width: usize) -> u32 {
let left = pixels[index - 1];
let top = pixels[index - width];
let top_left = pixels[index - width - 1];
let top_right = pixels[index - width + 1];
match mode {
1 => left,
2 => top,
3 => top_right,
4 => top_left,
5 => average2(average2(left, top_right), top),
6 => average2(left, top_left),
7 => average2(left, top),
8 => average2(top_left, top),
9 => average2(top, top_right),
10 => average2(average2(left, top_left), average2(top, top_right)),
11 => select(top, left, top_left),
12 => clamped_add_subtract_full(left, top, top_left),
13 => clamped_add_subtract_half(left, top, top_left),
_ => BLACK,
}
}
fn unpredict(tiles: &TileImage, pixels: &mut [u32]) {
let width = tiles.width;
pixels[0] = add_pixels(pixels[0], BLACK);
for x in 1..width {
pixels[x] = add_pixels(pixels[x], pixels[x - 1]);
}
for y in 1..pixels.len() / width {
let row = y * width;
pixels[row] = add_pixels(pixels[row], pixels[row - width]);
for x in 1..width {
let mode = (tiles.at(x, y) >> 8) & 0xF;
let index = row + x;
pixels[index] = add_pixels(pixels[index], predict(mode, pixels, index, width));
}
}
}
fn color_delta(multiplier: u8, channel: u8) -> u8 {
((i32::from(multiplier as i8) * i32::from(channel as i8)) >> 5) as u8
}
fn recorrelate(tiles: &TileImage, pixels: &mut [u32]) {
let width = tiles.width;
for (index, pixel) in pixels.iter_mut().enumerate() {
let [_, red_to_blue, green_to_blue, green_to_red] =
tiles.at(index % width, index / width).to_be_bytes();
let [alpha, red, green, blue] = pixel.to_be_bytes();
let red = red.wrapping_add(color_delta(green_to_red, green));
let blue = blue
.wrapping_add(color_delta(green_to_blue, green))
.wrapping_add(color_delta(red_to_blue, red));
*pixel = u32::from_be_bytes([alpha, red, green, blue]);
}
}
pub(super) fn subtract_green(pixel: u32) -> u32 {
let [alpha, red, green, blue] = pixel.to_be_bytes();
u32::from_be_bytes([
alpha,
red.wrapping_sub(green),
green,
blue.wrapping_sub(green),
])
}
fn add_green(pixel: u32) -> u32 {
let green = (pixel >> 8) & 0xFF;
let red_blue = ((pixel & 0x00FF_00FF) + ((green << 16) | green)) & 0x00FF_00FF;
(pixel & 0xFF00_FF00) | red_blue
}
fn unpack(palette: &Palette, coded: &[u32], coded_width: usize) -> Vec<u32> {
let width = palette.width;
let index_bits = 8 >> palette.bits;
let mask = (1u32 << index_bits) - 1;
let per_coded = 1usize << palette.bits;
let mut pixels = Vec::with_capacity(width * (coded.len() / coded_width));
for row in coded.chunks_exact(coded_width) {
for x in 0..width {
let packed = (row[x / per_coded] >> 8) & 0xFF;
let index = (packed >> ((x % per_coded) as u32 * index_bits)) & mask;
pixels.push(palette.colors[index as usize]);
}
}
pixels
}
#[cfg(test)]
mod tests {
use super::*;
fn argb(a: u8, r: u8, g: u8, b: u8) -> u32 {
u32::from_be_bytes([a, r, g, b])
}
#[test]
fn channel_arithmetic_wraps_and_rounds_down() {
assert_eq!(
add_pixels(argb(200, 1, 2, 255), argb(100, 3, 4, 1)),
argb(44, 4, 6, 0)
);
assert_eq!(
average2(argb(0, 1, 255, 10), argb(255, 2, 254, 11)),
argb(127, 1, 254, 10)
);
assert_eq!(add_green(argb(9, 250, 10, 1)), argb(9, 4, 10, 11));
assert_eq!(subtract_green(argb(9, 4, 10, 11)), argb(9, 250, 10, 1));
assert_eq!(subtract_green(argb(0, 50, 20, 5)), argb(0, 30, 20, 241));
assert_eq!(
add_green(subtract_green(argb(7, 50, 20, 5))),
argb(7, 50, 20, 5)
);
let (a, b) = (argb(3, 200, 0, 7), argb(250, 201, 1, 255));
assert_eq!(add_pixels(sub_pixels(a, b), b), a);
assert_eq!(sub_pixels(a, b), argb(9, 255, 255, 8));
}
#[test]
fn predictors_follow_libwebp() {
let top_left = argb(255, 10, 20, 30);
let top = argb(255, 40, 50, 60);
let top_right = argb(255, 70, 80, 90);
let left = argb(255, 100, 110, 120);
let pixels = [top_left, top, top_right, left, 0, 0];
assert_eq!(predict(0, &pixels, 4, 3), BLACK);
assert_eq!(predict(3, &pixels, 4, 3), top_right);
assert_eq!(
predict(11, &pixels, 4, 3),
left,
"left is nearer the gradient"
);
assert_eq!(
predict(12, &pixels, 4, 3),
argb(255, 130, 140, 150),
"left + top - top-left"
);
assert_eq!(predict(13, &pixels, 4, 3), argb(255, 100, 110, 120));
assert_eq!(
predict(15, &pixels, 4, 3),
BLACK,
"unused modes predict black"
);
let row_end = [1, 2, 3, 4, 5, 6];
assert_eq!(predict(3, &row_end, 5, 3), 4);
}
#[test]
fn half_steps_truncate_towards_zero() {
let pixel = clamped_add_subtract_half(0, 0, argb(5, 5, 5, 5));
assert_eq!(pixel, 0);
let pixel = clamped_add_subtract_half(argb(0, 9, 0, 0), argb(0, 9, 0, 0), argb(0, 4, 0, 0));
assert_eq!(pixel, argb(0, 11, 0, 0), "9 + 5 / 2");
}
#[test]
fn colour_transforms_use_signed_multipliers() {
let tiles = TileImage {
width: 1,
bits: 2,
tiles: vec![u32::from_be_bytes([0, 0, 0, 0xE0])],
};
let mut pixels = vec![argb(255, 0, 0x80, 0)];
recorrelate(&tiles, &mut pixels);
assert_eq!(pixels, [argb(255, 128, 0x80, 0)]);
}
#[test]
fn palettes_unpack_low_bits_first_and_pad_with_transparency() {
let palette = Palette::from_deltas(5, 2, &[argb(255, 1, 1, 1), argb(0, 1, 1, 1)]);
assert_eq!(palette.colors.len(), 4);
assert_eq!(palette.colors[1], argb(255, 2, 2, 2));
assert_eq!(palette.colors[2], 0);
let coded = [0b01_10_00_01 << 8, 1 << 8];
let pixels = unpack(&palette, &coded, 2);
let [one, zero, two] = [1, 0, 2].map(|i| palette.colors[i]);
assert_eq!(pixels, [one, zero, two, one, one]);
}
#[test]
fn prediction_round_trips_a_ramp() {
let tiles = TileImage {
width: 4,
bits: 2,
tiles: vec![1 << 8],
};
let mut pixels = vec![argb(0, 0, 0, 1); 8];
unpredict(&tiles, &mut pixels);
let blue: Vec<u8> = pixels.iter().map(|p| p.to_be_bytes()[3]).collect();
assert_eq!(blue, [1, 2, 3, 4, 2, 3, 4, 5]);
}
}