mod choose;
mod tokens;
pub(crate) use choose::{Area, chroma_candidates, luma_candidates};
pub(crate) use tokens::write_map;
use super::cdf::PaletteCdfs;
use super::entropy::SymbolSink;
pub(crate) const MAX_COLORS: usize = 8;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub(crate) struct Colors {
len: u8,
values: [u8; MAX_COLORS],
}
impl Colors {
pub(crate) fn new(values: &[u8]) -> Self {
let mut colors = Self {
len: values.len() as u8,
..Self::default()
};
colors.values[..values.len()].copy_from_slice(values);
colors
}
pub(crate) fn as_slice(&self) -> &[u8] {
&self.values[..usize::from(self.len)]
}
pub(crate) fn is_some(&self) -> bool {
self.len > 0
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Palette {
pub(crate) colors: Vec<Vec<u8>>,
pub(crate) map: Vec<u8>,
pub(crate) side: usize,
pub(crate) onscreen: (usize, usize),
}
impl Palette {
pub(crate) fn len(&self) -> usize {
self.colors[0].len()
}
pub(crate) fn predict(&self, list: usize, (x, y): (usize, usize), size: usize) -> Vec<u8> {
let colors = &self.colors[list];
(y..y + size)
.flat_map(|row| &self.map[row * self.side + x..][..size])
.map(|&index| colors[usize::from(index)])
.collect()
}
}
fn ceil_log2(x: u32) -> u32 {
if x < 2 { 0 } else { (x - 1).ilog2() + 1 }
}
pub(crate) fn cache(above: &[u8], left: &[u8]) -> Vec<u8> {
let mut merged: Vec<u8> = above.iter().chain(left).copied().collect();
merged.sort_unstable();
merged.dedup();
merged
}
fn write_ascending<S: SymbolSink>(sink: &mut S, colors: &[u8], cache: &[u8], offset: u32) {
let mut used = 0;
let mut rest: Vec<u8> = colors.to_vec();
for &entry in cache {
if used == colors.len() {
break;
}
let hit = rest.iter().position(|&c| c == entry);
sink.literal(u32::from(hit.is_some()), 1);
if let Some(at) = hit {
rest.remove(at);
used += 1;
}
}
let Some((&first, others)) = rest.split_first() else {
return;
};
sink.literal(u32::from(first), 8);
if others.is_empty() {
return;
}
let deltas: Vec<u32> = rest
.windows(2)
.map(|pair| u32::from(pair[1] - pair[0]) - offset)
.collect();
let needed = deltas.iter().map(|&d| d.bit_width()).max().unwrap_or(0);
let extra = needed.saturating_sub(5).min(3);
sink.literal(extra, 2);
let mut bits = 5 + extra;
for (&delta, &color) in deltas.iter().zip(&rest[1..]) {
sink.literal(delta, bits);
let range = 256 - u32::from(color) - offset;
bits = bits.min(ceil_log2(range));
}
}
fn v_deltas(v: &[u8]) -> Option<Vec<i32>> {
v.windows(2)
.map(|pair| {
let d = i32::from(pair[1]) - i32::from(pair[0]);
let d = if d > 128 {
d - 256
} else if d < -128 {
d + 256
} else {
d
};
(d.abs() < 128).then_some(d)
})
.collect()
}
fn write_v<S: SymbolSink>(sink: &mut S, v: &[u8]) {
let raw_bits = 8 * v.len() as u32;
let coded = v_deltas(v).map(|deltas| {
let bits = deltas
.iter()
.map(|d| d.unsigned_abs().bit_width())
.max()
.unwrap_or(0)
.max(4);
let signs = deltas.iter().filter(|&&d| d != 0).count() as u32;
let cost = 2 + 8 + bits * deltas.len() as u32 + signs;
(deltas, bits, cost)
});
match coded {
Some((deltas, bits, cost)) if cost < raw_bits => {
sink.literal(1, 1);
sink.literal(bits - 4, 2);
sink.literal(u32::from(v[0]), 8);
for d in deltas {
sink.literal(d.unsigned_abs(), bits);
if d != 0 {
sink.literal(u32::from(d < 0), 1);
}
}
}
_ => {
sink.literal(0, 1);
for &value in v {
sink.literal(u32::from(value), 8);
}
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct PaletteContext<'a> {
pub(crate) size_ctx: usize,
pub(crate) neighbours: (&'a [u8], &'a [u8]),
}
pub(crate) fn write_luma<S: SymbolSink>(
sink: &mut S,
cdfs: &mut PaletteCdfs,
(context, ctx): (&PaletteContext<'_>, usize),
palette: Option<&Palette>,
) {
sink.symbol(
&mut cdfs.y_mode[context.size_ctx][ctx],
usize::from(palette.is_some()),
);
if let Some(palette) = palette {
sink.symbol(&mut cdfs.y_size[context.size_ctx], palette.len() - 2);
let (above, left) = context.neighbours;
write_ascending(sink, &palette.colors[0], &cache(above, left), 1);
}
}
pub(crate) fn write_chroma<S: SymbolSink>(
sink: &mut S,
cdfs: &mut PaletteCdfs,
(context, has_luma): (&PaletteContext<'_>, bool),
palette: Option<&Palette>,
) {
sink.symbol(
&mut cdfs.uv_mode[usize::from(has_luma)],
usize::from(palette.is_some()),
);
if let Some(palette) = palette {
sink.symbol(&mut cdfs.uv_size[context.size_ctx], palette.len() - 2);
let (above, left) = context.neighbours;
write_ascending(sink, &palette.colors[0], &cache(above, left), 0);
write_v(sink, &palette.colors[1]);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::av1::entropy::RateEstimate;
#[derive(Default)]
struct Bits(Vec<(u32, u32)>);
impl SymbolSink for Bits {
fn symbol<const N: usize>(&mut self, _cdf: &mut [u16; N], symbol: usize) {
self.0.push((symbol as u32, 0));
}
fn bool_with(&mut self, bit: bool, _p0: u16) {
self.0.push((u32::from(bit), 1));
}
fn literal(&mut self, value: u32, bits: u32) {
self.0.push((value, bits));
}
}
#[test]
fn caches_merge_without_repeats() {
assert_eq!(cache(&[3, 9, 200], &[1, 9, 250]), [1, 3, 9, 200, 250]);
assert_eq!(cache(&[], &[]), []);
assert_eq!(ceil_log2(1), 0);
assert_eq!(ceil_log2(5), 3);
assert_eq!(ceil_log2(8), 3);
}
#[test]
fn luma_colours_use_the_cache_then_increments() {
let mut bits = Bits::default();
write_ascending(&mut bits, &[9, 20, 40, 200], &[1, 9, 200, 250], 1);
assert_eq!(
bits.0,
[
(0, 1),
(1, 1),
(1, 1),
(0, 1),
(20, 8),
(0, 2),
(19, 5),
]
);
}
#[test]
fn v_colours_take_the_short_way_round() {
assert_eq!(v_deltas(&[250, 4, 0]), Some(vec![10, -4]));
assert_eq!(v_deltas(&[0, 128]), None);
let mut delta = Bits::default();
write_v(&mut delta, &[100, 104, 99, 101]);
assert_eq!(delta.0[..4], [(1, 1), (0, 2), (100, 8), (4, 4)]);
let mut raw = Bits::default();
write_v(&mut raw, &[0, 128]);
assert_eq!(raw.0, [(0, 1), (0, 8), (128, 8)]);
let mut estimate = RateEstimate::default();
write_v(&mut estimate, &[7, 7]);
assert!(estimate.bits <= 17.0);
}
#[test]
fn predictions_read_the_map() {
let palette = Palette {
colors: vec![vec![10, 200], vec![5, 6]],
map: vec![0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0],
side: 4,
onscreen: (4, 4),
};
assert_eq!(palette.len(), 2);
assert_eq!(palette.predict(0, (2, 2), 2), [200, 200, 10, 10]);
assert_eq!(palette.predict(1, (0, 0), 2), [5, 6, 6, 6]);
assert_eq!(Colors::new(&[3, 4]).as_slice(), [3, 4]);
assert!(!Colors::default().is_some());
}
}