#[derive(Clone)]
pub(super) struct Plane {
pub(super) width: usize,
pub(super) pixels: Vec<u8>,
}
impl Plane {
pub(super) fn new(width: usize, height: usize) -> Self {
Self {
width,
pixels: vec![0; width * height],
}
}
fn top(&self, x: usize, y: usize) -> u8 {
if y == 0 {
127
} else {
self.pixels[(y - 1) * self.width + x.min(self.width - 1)]
}
}
fn left(&self, x: usize, y: usize) -> u8 {
if x == 0 {
129
} else {
self.pixels[y * self.width + x - 1]
}
}
fn top_left(&self, x: usize, y: usize) -> u8 {
if y == 0 {
127
} else if x == 0 {
129
} else {
self.pixels[(y - 1) * self.width + x - 1]
}
}
pub(super) fn predict_large(&mut self, x: usize, y: usize, size: usize, mode: u8) {
let mut above = [0u8; 16];
let mut left = [0u8; 16];
for i in 0..size {
above[i] = self.top(x + i, y);
left[i] = self.left(x, y + i);
}
let dc = if x == 0 && y == 0 {
128
} else if y == 0 {
(left[..size].iter().map(|&p| u32::from(p)).sum::<u32>() + (size / 2) as u32)
/ size as u32
} else if x == 0 {
(above[..size].iter().map(|&p| u32::from(p)).sum::<u32>() + (size / 2) as u32)
/ size as u32
} else {
(above[..size]
.iter()
.chain(left[..size].iter())
.map(|&p| u32::from(p))
.sum::<u32>()
+ size as u32)
/ (2 * size) as u32
};
let corner = self.top_left(x, y);
match mode {
0 => {
for row in 0..size {
let start = (y + row) * self.width + x;
self.pixels[start..start + size].fill(dc as u8);
}
return;
}
1 => {
for row in 0..size {
let start = (y + row) * self.width + x;
self.pixels[start..start + size].copy_from_slice(&above[..size]);
}
return;
}
2 => {
for row in 0..size {
let start = (y + row) * self.width + x;
self.pixels[start..start + size].fill(left[row]);
}
return;
}
3 => {}
_ => unreachable!("invalid VP8 large intra mode"),
}
for row in 0..size {
for col in 0..size {
let predicted = clamp(i32::from(left[row]) + i32::from(above[col]) - i32::from(corner));
self.pixels[(y + row) * self.width + x + col] = predicted;
}
}
}
pub(super) fn predict_small(
&mut self,
x: usize,
y: usize,
mode: u8,
macroblock_x: usize,
macroblock_y: usize,
) {
let mut above = [0u8; 8];
let mut left = [0u8; 4];
for i in 0..4 {
left[i] = self.left(x, y + i);
}
for i in 0..8 {
above[i] = if x + i >= macroblock_x + 16 {
self.top((x + i).min(self.width - 1), macroblock_y)
} else {
self.top(x + i, y)
};
}
let corner = self.top_left(x, y);
let edge = [
left[3], left[2], left[1], left[0], corner, above[0], above[1], above[2], above[3],
];
let dc = ((above[..4]
.iter()
.chain(left.iter())
.map(|&v| u32::from(v))
.sum::<u32>()
+ 4)
>> 3) as u8;
let mut predicted = [[0u8; 4]; 4];
for row in 0..4 {
for col in 0..4 {
predicted[row][col] = match mode {
0 => dc,
1 => clamp(i32::from(left[row]) + i32::from(above[col]) - i32::from(corner)),
2 => avg3(
if col == 0 { corner } else { above[col - 1] },
above[col],
above[col + 1],
),
3 => avg3(
if row == 0 { corner } else { left[row - 1] },
left[row],
left[(row + 1).min(3)],
),
4 => {
let center = (row + col + 1).min(7);
avg3(above[center - 1], above[center], above[(center + 1).min(7)])
}
5 => {
let center = (4 + col) - row;
avg3(edge[center - 1], edge[center], edge[center + 1])
}
6 => predict_vertical_right(&edge, row, col),
7 => predict_vertical_left(&above, row, col),
8 => predict_horizontal_down(&edge, row, col),
9 => predict_horizontal_up(&left, row, col),
_ => unreachable!("invalid VP8 subblock mode"),
};
}
}
for row in 0..4 {
self.pixels[(y + row) * self.width + x..(y + row) * self.width + x + 4]
.copy_from_slice(&predicted[row]);
}
}
pub(super) fn add_residual(&mut self, x: usize, y: usize, values: &[i32; 16]) {
if values.iter().all(|&value| value == 0) { return; }
for row in 0..4 {
let start = (y + row) * self.width + x;
for (pixel, &value) in self.pixels[start..start + 4].iter_mut()
.zip(&values[row * 4..row * 4 + 4])
{
*pixel = clamp(i32::from(*pixel).saturating_add(value));
}
}
}
}
fn clamp(value: i32) -> u8 {
value.clamp(0, 255) as u8
}
fn avg2(a: u8, b: u8) -> u8 {
((u16::from(a) + u16::from(b) + 1) >> 1) as u8
}
fn avg3(a: u8, b: u8, c: u8) -> u8 {
((u16::from(a) + 2 * u16::from(b) + u16::from(c) + 2) >> 2) as u8
}
fn predict_vertical_right(edge: &[u8; 9], row: usize, col: usize) -> u8 {
let (center, three) = match (row, col) {
(0, c) => (4 + c, false),
(1, c) => (4 + c, true),
(2, 0) => (3, true),
(2, c) => (3 + c, false),
(3, 0) => (2, true),
(3, c) => (3 + c, true),
_ => unreachable!(),
};
if three {
avg3(edge[center - 1], edge[center], edge[center + 1])
} else {
avg2(edge[center], edge[center + 1])
}
}
fn predict_vertical_left(above: &[u8; 8], row: usize, col: usize) -> u8 {
let (center, three) = match (row, col) {
(0, c) => (c, false),
(1, c) => (c + 1, true),
(2, c) if c < 3 => (c + 1, false),
(2, _) => (5, true),
(3, c) if c < 3 => (c + 2, true),
(3, _) => (6, true),
_ => unreachable!(),
};
if three {
avg3(above[center - 1], above[center], above[center + 1])
} else {
avg2(above[center], above[center + 1])
}
}
fn predict_horizontal_down(edge: &[u8; 9], row: usize, col: usize) -> u8 {
let (center, three) = match (row, col) {
(0, 0) => (3, false),
(0, 1) => (4, true),
(0, 2) => (5, true),
(0, 3) => (6, true),
(r, c) if c % 2 == 0 => (3 - r + c / 2, false),
(r, c) => (3 - r + (c + 1) / 2, true),
};
if three {
avg3(edge[center - 1], edge[center], edge[center + 1])
} else {
avg2(edge[center], edge[center + 1])
}
}
fn predict_horizontal_up(left: &[u8; 4], row: usize, col: usize) -> u8 {
let position = 2 * row + col;
if position >= 6 {
return left[3];
}
let center = position / 2;
if position % 2 == 0 {
avg2(left[center], left[center + 1])
} else {
avg3(left[center], left[center + 1], left[(center + 2).min(3)])
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn small_prediction_does_not_read_unreconstructed_macroblocks() {
for mb_y in [0, 16] {
for mb_x in [0, 16] {
for by in 0..4 {
for bx in 0..4 {
let (x, y) = (mb_x + bx * 4, mb_y + by * 4);
for mode in 0..10 {
let mut expected = None;
for future in 0..3 {
let mut plane = Plane::new(48, 48);
for (index, pixel) in plane.pixels.iter_mut().enumerate() {
let (row, col) = (index / 48, index % 48);
let decoded = row < mb_y || (row < mb_y + 16
&& (col < mb_x || (col < mb_x + 16
&& (row < y || (row < y + 4 && col < x)))));
*pixel = if decoded {
((index * 73 + row * 19) % 256) as u8
} else {
match future {
0 => 0, 1 => ((index * 29 + row * 13) % 256) as u8,
_ => 255,
}
};
}
let before = plane.pixels.clone();
plane.predict_small(x, y, mode, mb_x, mb_y);
let output: [u8; 16] = std::array::from_fn(|index| {
plane.pixels[(y + index / 4) * 48 + x + index % 4]
});
if let Some(reference) = expected {
assert_eq!(output, reference,
"mb=({mb_x},{mb_y}) block=({bx},{by}) mode={mode} future={future}");
} else { expected = Some(output); }
for (index, (&actual, &original)) in
plane.pixels.iter().zip(&before).enumerate()
{
let (row, col) = (index / 48, index % 48);
if !(y..y + 4).contains(&row) || !(x..x + 4).contains(&col) {
assert_eq!(actual, original, "write outside predicted block");
}
}
}
}
}
}
}
}
}
fn lazy_large_prediction(plane: &mut Plane, x: usize, y: usize, size: usize, mode: u8) {
match mode {
1 => {
let mut above = [0; 16];
for (col, value) in above[..size].iter_mut().enumerate() {
*value = plane.top(x + col, y);
}
for row in 0..size {
let start = (y + row) * plane.width + x;
plane.pixels[start..start + size].copy_from_slice(&above[..size]);
}
}
2 => {
for row in 0..size {
let value = plane.left(x, y + row);
let start = (y + row) * plane.width + x;
plane.pixels[start..start + size].fill(value);
}
}
_ => plane.predict_large(x, y, size, mode),
}
}
fn scalar_large_prediction(plane: &mut Plane, x: usize, y: usize, size: usize, mode: u8) {
let above: Vec<_> = (0..size).map(|col| plane.top(x + col, y)).collect();
let left: Vec<_> = (0..size).map(|row| plane.left(x, y + row)).collect();
let (sum, count) = match (x == 0, y == 0) {
(true, true) => (128 * size as u32, size),
(false, true) => (left.iter().map(|&v| u32::from(v)).sum(), size),
(true, false) => (above.iter().map(|&v| u32::from(v)).sum(), size),
(false, false) => (above.iter().chain(&left).map(|&v| u32::from(v)).sum(), size * 2),
};
let dc = (sum + (count / 2) as u32) / count as u32;
let corner = plane.top_left(x, y);
for row in 0..size {
for col in 0..size {
let value = match mode {
0 => dc as u8,
1 => above[col],
2 => left[row],
_ => clamp(i32::from(left[row]) + i32::from(above[col]) - i32::from(corner)),
};
plane.pixels[(y + row) * plane.width + x + col] = value;
}
}
}
#[test]
fn bulk_large_predictions_match_scalar_edges_and_clipping() {
for size in [8, 16] {
for x in [0, 8, 16] {
for y in [0, 8, 16] {
for pattern in 0..4 {
let mut original = Plane::new(32, 32);
for (index, pixel) in original.pixels.iter_mut().enumerate() {
*pixel = match pattern {
0 => 0,
1 => 255,
2 => if index % 2 == 0 { 0 } else { 255 },
_ => ((index * 37 + 19) & 255) as u8,
};
}
for mode in 0..4 {
let mut actual = original.clone();
let mut lazy = original.clone();
let mut expected = original.clone();
actual.predict_large(x, y, size, mode);
lazy_large_prediction(&mut lazy, x, y, size, mode);
scalar_large_prediction(&mut expected, x, y, size, mode);
assert_eq!(actual.pixels, expected.pixels,
"size={size} x={x} y={y} mode={mode} pattern={pattern}");
assert_eq!(lazy.pixels, expected.pixels,
"lazy size={size} x={x} y={y} mode={mode} pattern={pattern}");
}
}
}
}
}
}
#[test]
#[ignore = "manual retained/lazy large-predictor ABBA timing"]
fn benchmark_lazy_large_prediction() {
fn run<const LAZY: bool>(size: usize, mode: u8) -> u128 {
let mut plane = Plane::new(32, 32);
for (index, pixel) in plane.pixels.iter_mut().enumerate() {
*pixel = ((index * 37 + 19) & 255) as u8;
}
let start = std::time::Instant::now();
for _ in 0..200_000 {
let mode = std::hint::black_box(mode);
if LAZY { lazy_large_prediction(&mut plane, 8, 8, size, mode); }
else { plane.predict_large(8, 8, size, mode); }
std::hint::black_box(&plane.pixels);
}
start.elapsed().as_nanos()
}
for size in [8, 16] {
for mode in 0..4 {
for pass in 0..2 {
for lazy in [false, true, true, false] {
let ns = if lazy { run::<true>(size, mode) } else { run::<false>(size, mode) };
eprintln!("vp8 large prediction size={size} mode={mode} pass={pass} lazy={lazy} wall_ns={ns}");
}
}
}
}
}
#[test]
fn default_edges_and_dc_modes() {
let mut plane = Plane::new(32, 32);
plane.predict_large(0, 0, 16, 0);
assert!(plane.pixels[..16].iter().all(|&pixel| pixel == 128));
plane.predict_small(0, 0, 0, 0, 0);
assert!(plane.pixels[..4].iter().all(|&pixel| pixel == 128));
}
#[test]
fn bulk_residual_matches_wide_clipped_addition() {
let mut original = Plane::new(13, 9);
for (index, pixel) in original.pixels.iter_mut().enumerate() {
*pixel = (index * 73) as u8;
}
let extremes = [i32::MIN, -32768, -256, -255, -1, 0, 1, 255, 256, 32767, i32::MAX];
for trial in 0..1024 {
let values = std::array::from_fn(|index| {
if trial < extremes.len() { extremes[(trial + index) % extremes.len()] }
else { ((trial * 37 + index * 73) % 1025) as i32 - 512 }
});
let (x, y) = (trial % 10, trial % 6);
let mut actual = original.clone();
let mut expected = original.clone();
actual.add_residual(x, y, &values);
for row in 0..4 {
for col in 0..4 {
let at = (y + row) * expected.width + x + col;
expected.pixels[at] = (i64::from(expected.pixels[at])
+ i64::from(values[row * 4 + col])).clamp(0, 255) as u8;
}
}
assert_eq!(actual.pixels, expected.pixels, "trial={trial}");
}
let mut actual = original.clone();
actual.add_residual(9, 5, &[0; 16]);
assert_eq!(actual.pixels, original.pixels);
}
#[test]
#[ignore = "manual VP8 residual addition kernel timing"]
fn benchmark_residual_addition() {
use std::hint::black_box;
use std::time::Instant;
let mut plane = Plane::new(13, 9);
let values = std::array::from_fn(|index| (index * 7 % 13) as i32 - 6);
for zero_every in [0, 4] {
for trial in 0..5 {
for bulk in if trial % 2 == 0 { [false, true] } else { [true, false] } {
let start = Instant::now();
for iteration in 0..1_000_000 {
let plane = black_box(&mut plane);
let values = black_box(if zero_every != 0 && iteration % zero_every == 0 {
&[0; 16]
} else { &values });
if bulk { plane.add_residual(3, 2, values); }
else {
for row in 0..4 {
for col in 0..4 {
let at = (2 + row) * plane.width + 3 + col;
plane.pixels[at] = clamp(i32::from(plane.pixels[at]) + values[row * 4 + col]);
}
}
}
black_box(&plane.pixels);
}
eprintln!("VP8 residual zero_every={zero_every} trial={trial} bulk={bulk} elapsed={:?}", start.elapsed());
}
}
}
}
}