use crate::bit_writer::BitWriter;
const WP_EXTRA_BITS: i64 = 3;
const WP_PRED_ROUND: i64 = ((1 << WP_EXTRA_BITS) >> 1) - 1;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct WpParams {
w: [u32; 4],
p: [i64; 7],
}
impl WpParams {
pub(crate) const PRESETS: [Self; 4] = [
Self {
w: [0xd, 0xc, 0xc, 0xc],
p: [16, 10, 7, 7, 7, 0, 0],
},
Self {
w: [0xd, 0xc, 0xc, 0xb],
p: [8, 8, 4, 0, 3, 23, 2],
},
Self {
w: [0xd, 0xc, 0xd, 0xc],
p: [10, 9, 7, 0, 0, 16, 9],
},
Self {
w: [0xd, 0xd, 0xc, 0xc],
p: [16, 8, 0, 16, 0, 23, 0],
},
];
pub(crate) const DEFAULT: Self = Self::PRESETS[0];
}
pub(crate) fn write_wp_header(params: WpParams, writer: &mut BitWriter) {
if params == WpParams::DEFAULT {
writer.write(1, 1);
return;
}
writer.write(1, 0);
for ¶m in ¶ms.p {
writer.write(5, param as u64);
}
for &weight in ¶ms.w {
writer.write(4, weight as u64);
}
}
static WP_DIV: [u32; 64] = [
16777216, 8388608, 5592405, 4194304, 3355443, 2796202, 2396745, 2097152, 1864135, 1677721,
1525201, 1398101, 1290555, 1198372, 1118481, 1048576, 986895, 932067, 883011, 838860, 798915,
762600, 729444, 699050, 671088, 645277, 621378, 599186, 578524, 559240, 541200, 524288, 508400,
493447, 479349, 466033, 453438, 441505, 430185, 419430, 409200, 399457, 390167, 381300, 372827,
364722, 356962, 349525, 342392, 335544, 328965, 322638, 316551, 310689, 305040, 299593, 294337,
289262, 284359, 279620, 275036, 270600, 266305, 262144,
];
pub(crate) struct WpState {
xsize: usize,
pred_errors: [Vec<u32>; 4],
error: Vec<i64>,
prediction: [i64; 4],
pred: i64,
pub(crate) wp_prop: i64,
params: WpParams,
}
#[derive(Clone, Copy)]
pub(crate) struct WpRowOffsets {
current: usize,
previous: usize,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub(crate) struct WpUpdate {
error: i64,
pred_errors: [u32; 4],
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct WpPrediction {
pred: i64,
prediction: [i64; 4],
}
#[derive(Clone, Copy)]
pub(crate) struct WpNeighbors {
pub(crate) north: i64,
pub(crate) west: i64,
pub(crate) north_east: i64,
pub(crate) north_west: i64,
pub(crate) north_north: i64,
}
impl WpState {
pub(crate) fn new(xsize: usize) -> Self {
Self::with_params(xsize, WpParams::DEFAULT)
}
pub(crate) fn with_params(xsize: usize, params: WpParams) -> Self {
let n = (xsize + 2) * 2;
Self {
xsize,
pred_errors: [vec![0u32; n], vec![0u32; n], vec![0u32; n], vec![0u32; n]],
error: vec![0i64; n],
prediction: [0; 4],
pred: 0,
wp_prop: 0,
params,
}
}
pub(crate) fn reset(&mut self, xsize: usize, params: WpParams) {
let n = (xsize + 2) * 2;
for errors in &mut self.pred_errors {
errors.resize(n, 0);
errors.fill(0);
}
self.error.resize(n, 0);
self.error.fill(0);
self.xsize = xsize;
self.params = params;
self.prediction = [0; 4];
self.pred = 0;
self.wp_prop = 0;
}
#[inline]
fn add_bits(x: i64) -> i64 {
x << WP_EXTRA_BITS
}
#[inline]
fn floor_log2(x: u64) -> u32 {
debug_assert!(x >= 1);
63 - x.leading_zeros()
}
#[inline]
fn error_weight(x: u64, maxweight: u32) -> u32 {
let mut shift = Self::floor_log2(x + 1) as i32 - 5;
if shift < 0 {
shift = 0;
}
4 + (((maxweight as u64 * WP_DIV[(x >> shift) as usize & 63] as u64) >> shift) as u32)
}
#[inline]
fn weighted_average(pred: &[i64; 4], w_in: &[u32; 4]) -> i64 {
let mut weight_sum: u32 = w_in.iter().sum();
let log_weight = Self::floor_log2(weight_sum as u64);
let mut w = [0u32; 4];
weight_sum = 0;
for i in 0..4 {
w[i] = w_in[i] >> (log_weight - 4);
weight_sum += w[i];
}
let mut sum: i64 = (weight_sum as i64 >> 1) - 1;
for i in 0..4 {
sum += pred[i] * w[i] as i64;
}
(sum * WP_DIV[(weight_sum - 1) as usize & 63] as i64) >> 24
}
#[inline]
pub(crate) fn row_offsets(&self, y: usize) -> WpRowOffsets {
let second = self.xsize + 2;
if y & 1 == 1 {
WpRowOffsets {
current: 0,
previous: second,
}
} else {
WpRowOffsets {
current: second,
previous: 0,
}
}
}
#[inline(always)]
fn predict_with_row<const FLAT_SHORTCUT: bool>(
&mut self,
x: usize,
row: WpRowOffsets,
n: WpNeighbors,
) -> (i64, bool) {
self.check_slot(x, row);
let error = |i: usize| unsafe { *self.error.get_unchecked(i) };
let pred_error = |p: usize, i: usize| unsafe { *self.pred_errors[p].get_unchecked(i) };
let pos_n = row.previous + x;
let pos_ne = if x < self.xsize - 1 { pos_n + 1 } else { pos_n };
let pos_nw = if x > 0 { pos_n - 1 } else { pos_n };
if FLAT_SHORTCUT
&& n.north == n.west
&& n.north == n.north_east
&& n.north == n.north_west
&& n.north == n.north_north
&& (-8192..=8192).contains(&n.north)
&& (x == 0 || error(row.current + x - 1) == 0)
&& error(pos_n) == 0
&& error(pos_nw) == 0
&& error(pos_ne) == 0
{
let common = Self::add_bits(n.north);
self.prediction = [common; 4];
self.pred = common;
self.wp_prop = 0;
return (n.north, true);
}
let mut weights = [0u32; 4];
for i in 0..4 {
let s = pred_error(i, pos_n) as u64
+ pred_error(i, pos_ne) as u64
+ pred_error(i, pos_nw) as u64;
weights[i] = Self::error_weight(s, self.params.w[i]);
}
let an = Self::add_bits(n.north);
let aw = Self::add_bits(n.west);
let ane = Self::add_bits(n.north_east);
let anw = Self::add_bits(n.north_west);
let ann = Self::add_bits(n.north_north);
let te_w = if x == 0 {
0
} else {
error(row.current + x - 1)
};
let te_n = error(pos_n);
let te_nw = error(pos_nw);
let te_ne = error(pos_ne);
let mut wp_prop = te_w;
if te_n.abs() > wp_prop.abs() {
wp_prop = te_n;
}
if te_nw.abs() > wp_prop.abs() {
wp_prop = te_nw;
}
if te_ne.abs() > wp_prop.abs() {
wp_prop = te_ne;
}
self.wp_prop = wp_prop;
let s_wn = te_n + te_w;
self.prediction[0] = aw + ane - an;
self.prediction[1] = an - (((s_wn + te_ne) * self.params.p[0]) >> 5);
self.prediction[2] = aw - (((s_wn + te_nw) * self.params.p[1]) >> 5);
self.prediction[3] = an
- ((te_nw * self.params.p[2]
+ te_n * self.params.p[3]
+ te_ne * self.params.p[4]
+ (ann - an) * self.params.p[5]
+ (anw - aw) * self.params.p[6])
>> 5);
let pred = Self::weighted_average(&self.prediction, &weights);
if ((te_n ^ te_w) | (te_n ^ te_nw)) > 0 {
self.pred = pred;
((pred + WP_PRED_ROUND) >> WP_EXTRA_BITS, false)
} else {
let mx = aw.max(ane).max(an);
let mn = aw.min(ane).min(an);
let predc = pred.max(mn).min(mx);
self.pred = predc;
((predc + WP_PRED_ROUND) >> WP_EXTRA_BITS, false)
}
}
#[inline(always)]
fn check_slot(&self, x: usize, row: WpRowOffsets) {
assert!(x < self.xsize && row.previous.max(row.current) <= self.xsize + 2);
}
#[inline(always)]
fn update_with_row(&mut self, val: i64, x: usize, row: WpRowOffsets) {
let update = Self::update_for(self.last_prediction(), val);
self.check_slot(x, row);
unsafe {
*self.error.get_unchecked_mut(row.current + x) = update.error;
for (errors, &error) in self.pred_errors.iter_mut().zip(&update.pred_errors) {
*errors.get_unchecked_mut(row.current + x) = error;
let slot = errors.get_unchecked_mut(row.previous + x + 1);
*slot = slot.wrapping_add(error);
}
}
}
#[inline(always)]
pub(crate) fn last_prediction(&self) -> WpPrediction {
WpPrediction {
pred: self.pred,
prediction: self.prediction,
}
}
#[inline(always)]
pub(crate) fn update_for(prediction: WpPrediction, val: i64) -> WpUpdate {
let valb = Self::add_bits(val);
WpUpdate {
error: prediction.pred - valb,
pred_errors: std::array::from_fn(|i| {
(((prediction.prediction[i] - valb).abs() + WP_PRED_ROUND) >> WP_EXTRA_BITS) as u32
}),
}
}
pub(crate) fn save_row_base(&self, y: usize, into: &mut Vec<[u32; 4]>) {
let row = self.row_offsets(y);
into.clear();
into.extend(
(0..self.xsize).map(|x| std::array::from_fn(|i| self.pred_errors[i][row.previous + x])),
);
}
pub(crate) fn restore_row_base(&mut self, y: usize, base: &[[u32; 4]]) {
let row = self.row_offsets(y);
for (x, slots) in base.iter().enumerate() {
for (errors, &slot) in self.pred_errors.iter_mut().zip(slots) {
errors[row.previous + x] = slot;
}
}
}
#[inline]
pub(crate) fn stage_path(
&mut self,
x: usize,
y: usize,
base: &[[u32; 4]],
west: Option<WpUpdate>,
west2: Option<WpUpdate>,
) {
let row = self.row_offsets(y);
if let Some(west) = west {
self.error[row.current + x - 1] = west.error;
for (i, errors) in self.pred_errors.iter_mut().enumerate() {
errors[row.previous + x] = base[x][i].wrapping_add(west.pred_errors[i]);
}
}
if let Some(west2) = west2 {
for (i, errors) in self.pred_errors.iter_mut().enumerate() {
errors[row.previous + x - 1] = base[x - 1][i].wrapping_add(west2.pred_errors[i]);
}
}
}
pub(crate) fn predict_and_update(
&mut self,
val: i64,
x: usize,
row: WpRowOffsets,
neighbors: WpNeighbors,
) -> i64 {
let (prediction, _) = self.predict_with_row::<false>(x, row, neighbors);
self.update_with_row(val, x, row);
prediction
}
pub(crate) fn predict_and_update_flat(
&mut self,
val: i64,
x: usize,
row: WpRowOffsets,
neighbors: WpNeighbors,
) -> i64 {
self.predict_and_update_flat_inlined(val, x, row, neighbors)
}
#[inline(always)]
pub(crate) fn predict_and_update_flat_inlined(
&mut self,
val: i64,
x: usize,
row: WpRowOffsets,
neighbors: WpNeighbors,
) -> i64 {
let (prediction, flat) = self.predict_with_row::<true>(x, row, neighbors);
if flat && prediction == val {
unsafe {
*self.error.get_unchecked_mut(row.current + x) = 0;
for errors in &mut self.pred_errors {
*errors.get_unchecked_mut(row.current + x) = 0;
}
}
} else {
self.update_with_row(val, x, row);
}
prediction
}
pub(crate) fn predict(
&mut self,
x: usize,
y: usize,
north: i64,
west: i64,
north_east: i64,
north_west: i64,
north_north: i64,
) -> i64 {
self.predict_with_row::<false>(
x,
self.row_offsets(y),
WpNeighbors {
north,
west,
north_east,
north_west,
north_north,
},
)
.0
}
#[inline]
pub(crate) fn update(&mut self, val: i64, x: usize, y: usize) {
self.update_with_row(val, x, self.row_offsets(y));
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn equal_predictions_keep_the_exact_fixed_point_average() {
for total in 13i64..=31 {
let reciprocal = WP_DIV[total as usize - 1] as i64;
for prediction in -65_536i64..=65_536 {
let sum = prediction * total + (total >> 1) - 1;
assert_eq!((sum * reciprocal) >> 24, prediction);
}
}
let mut seed = 17u32;
for _ in 0..10_000 {
let weights: [u32; 4] = std::array::from_fn(|_| {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
4 + seed % (15 << 24)
});
let sum: u32 = weights.iter().sum();
let shift = WpState::floor_log2(sum as u64) - 4;
let normalized: u32 = weights.iter().map(|w| w >> shift).sum();
assert!((13..=31).contains(&normalized));
for prediction in [-65_536, -1, 0, 1, 65_536] {
assert_eq!(
WpState::weighted_average(&[prediction; 4], &weights),
prediction
);
}
}
}
#[test]
fn flat_shortcut_preserves_prediction_and_error_state() {
for params in WpParams::PRESETS {
for width in [1, 17] {
for value in [-8193, -8192, -1, 0, 1, 8192, 8193, 65535] {
let mut general = WpState::with_params(width, params);
let mut ma = WpState::with_params(width, params);
for (i, errors) in general.pred_errors.iter_mut().enumerate() {
for (j, error) in errors.iter_mut().enumerate() {
*error = (i * 191 + j * 73) as u32;
}
}
ma.pred_errors.clone_from(&general.pred_errors);
for y in 0..8 {
for x in 0..width {
let delta = if (2..5).contains(&y) {
x as i64 * 31 + y as i64 * 17
} else {
0
};
let neighbors = WpNeighbors {
north: value,
west: value + delta,
north_east: value - delta,
north_west: value + delta * 2,
north_north: value - delta * 3,
};
assert_eq!(
ma.predict_and_update_flat(
value + delta,
x,
ma.row_offsets(y),
neighbors,
),
general.predict_and_update(
value + delta,
x,
general.row_offsets(y),
neighbors,
)
);
assert_eq!(ma.pred, general.pred);
assert_eq!(ma.prediction, general.prediction);
assert_eq!(ma.wp_prop, general.wp_prop);
assert_eq!(ma.error, general.error);
assert_eq!(ma.pred_errors, general.pred_errors);
}
}
}
}
}
}
#[test]
fn reset_matches_fresh_state_after_width_and_parameter_changes() {
let mut reused = WpState::new(0);
for (round, width) in [17, 3, 257, 1, 17].into_iter().enumerate() {
let params = WpParams::PRESETS[round % WpParams::PRESETS.len()];
reused.reset(width, params);
let mut fresh = WpState::with_params(width, params);
for y in 0..5 {
for x in 0..width {
let value = (x * 37 + y * 101 + round * 17) as i64;
let neighbors = WpNeighbors {
north: value - 13,
west: value + 7,
north_east: value - 29,
north_west: value + 3,
north_north: value - 19,
};
assert_eq!(
reused.predict_and_update(value, x, reused.row_offsets(y), neighbors),
fresh.predict_and_update(value, x, fresh.row_offsets(y), neighbors)
);
assert_eq!(reused.wp_prop, fresh.wp_prop);
}
}
}
}
#[test]
fn wp_headers_have_expected_sizes() {
let mut default = BitWriter::new();
write_wp_header(WpParams::DEFAULT, &mut default);
assert_eq!(default.bits_written(), 1);
for ¶ms in &WpParams::PRESETS[1..] {
let mut custom = BitWriter::new();
write_wp_header(params, &mut custom);
assert_eq!(custom.bits_written(), 52);
}
}
}