pub(crate) const MAX_CHAIN_LEN: u32 = 1024;
#[inline]
pub(crate) fn weak_init(window: &[u8]) -> (u32, u32) {
let mut s1 = 0u32;
let mut s2 = 0u32;
let mut i = 0usize;
while i + 4 <= window.len() {
let b0 = u32::from(window[i]);
let b1 = u32::from(window[i + 1]);
let b2 = u32::from(window[i + 2]);
let b3 = u32::from(window[i + 3]);
s2 = s2.wrapping_add(
(s1.wrapping_add(b0) << 2).wrapping_add(3 * b1 + 2 * b2 + b3),
);
s1 = s1.wrapping_add(b0 + b1 + b2 + b3);
i += 4;
}
while i < window.len() {
s1 = s1.wrapping_add(u32::from(window[i]));
s2 = s2.wrapping_add(s1);
i += 1;
}
(s1, s2)
}
#[must_use]
#[inline]
pub(crate) fn weak_value(s1: u32, s2: u32) -> u32 {
(s1 & 0xffff) | (s2 << 16)
}
#[must_use]
#[inline]
pub(crate) fn bucket_traditional(s1: u32, s2: u32) -> usize {
(s1.wrapping_add(s2) & 0xffff) as usize
}
#[inline]
pub(crate) fn state_pack(s1: u32, s2: u32) -> u64 {
u64::from(s1) | (u64::from(s2) << 32)
}
#[inline]
pub(crate) fn state_value(st: u64) -> u32 {
#[expect(clippy::cast_possible_truncation)]
let v = ((st & 0xffff) | ((st >> 32) << 16)) as u32;
v
}
#[inline]
pub(crate) fn state_bucket(st: u64) -> usize {
(st.wrapping_add(st >> 32) & 0xffff) as usize
}
#[inline]
pub(crate) fn state_roll(st: &mut u64, k: u32, out: u8, inn: u8) {
#[expect(clippy::cast_possible_truncation)]
let lo = *st as u32;
let hi = (*st >> 32) as u32;
let out = u32::from(out);
let inn = u32::from(inn);
let lo2 = lo.wrapping_add(inn).wrapping_sub(out);
let hi2 = hi
.wrapping_add(lo)
.wrapping_add(inn)
.wrapping_sub(k.wrapping_add(1).wrapping_mul(out));
*st = u64::from(lo2) | (u64::from(hi2) << 32);
}
#[must_use]
pub(crate) fn block_size(file_size: u64) -> usize {
#[expect(clippy::cast_possible_truncation)]
let root = isqrt(file_size) as usize;
let rounded = (root / 8) * 8;
rounded.clamp(700, 32 * 1024)
}
fn isqrt(n: u64) -> u64 {
if n < 2 {
return n;
}
let mut x = n;
let mut y = x.div_ceil(2);
while y < x {
x = y;
y = u64::midpoint(x, n / x);
}
x
}
#[cfg(test)]
mod tests {
use super::*;
fn naive(window: &[u8]) -> (u32, u32) {
let mut s1 = 0u32;
let mut s2 = 0u32;
#[expect(clippy::cast_possible_truncation)]
let n = window.len() as u32;
for (i, &b) in window.iter().enumerate() {
s1 = s1.wrapping_add(u32::from(b));
#[expect(clippy::cast_possible_truncation)]
let w = n.wrapping_sub(i as u32);
s2 = s2.wrapping_add(w.wrapping_mul(u32::from(b)));
}
(s1, s2)
}
#[test]
fn weak_init_matches_naive() {
let data: Vec<u8> = (0..100_000u64)
.map(|i| (i.wrapping_mul(0x9E37_79B9).rotate_left(17) & 0xFF) as u8)
.collect();
for len in [0usize, 1, 2, 3, 4, 5, 7, 8, 12, 63, 64, 700, 23168, 32768] {
if len > data.len() {
continue;
}
assert_eq!(
weak_init(&data[..len]),
naive(&data[..len]),
"unrolled init diverges at len {len}"
);
assert_eq!(
weak_value(weak_init(&data[..len]).0, weak_init(&data[..len]).1),
weak_value(naive(&data[..len]).0, naive(&data[..len]).1)
);
}
}
#[test]
fn roll_matches_reinit() {
let data: Vec<u8> = (0..80_000u64)
.map(|i| (i.wrapping_mul(0x85EB_CA6B).rotate_left(13) & 0xFF) as u8)
.collect();
let n = 5792;
let (s1, s2) = weak_init(&data[..n]);
let mut st = state_pack(s1, s2);
for p in 0..data.len() - n {
let (a, b) = weak_init(&data[p..p + n]);
assert_eq!(
state_pack(a, b),
st,
"rolling state diverges at position {p}"
);
#[expect(clippy::cast_possible_truncation)]
let k = n as u32;
state_roll(&mut st, k, data[p], data[p + n]);
}
let (a, b) = weak_init(&data[data.len() - n..]);
assert_eq!(
state_pack(a, b),
st,
"final rolled state diverges"
);
}
#[test]
fn roll_shrink_matches_reinit() {
let data: Vec<u8> = (0..40_000u64)
.map(|i| (i.wrapping_mul(0xC2B2_AE35).rotate_left(29) & 0xFF) as u8)
.collect();
let mut n = 5792usize;
let (mut s1, mut s2) = weak_init(&data[..n]);
for p in 0..data.len() - 1 {
assert_eq!(
(s1, s2),
weak_init(&data[p..p + n]),
"shrink state diverges at position {p} (k={n})"
);
s1 = s1.wrapping_sub(u32::from(data[p]));
#[expect(clippy::cast_possible_truncation)]
let k = n as u32;
s2 = s2.wrapping_sub(k.wrapping_mul(u32::from(data[p])));
if p + n < data.len() {
let inn = data[p + n];
s1 = s1.wrapping_add(u32::from(inn));
s2 = s2.wrapping_add(s1);
} else {
n -= 1; }
}
}
#[test]
fn block_size_matches_rsync() {
assert_eq!(block_size(33_554_432), 5_792); assert_eq!(block_size(268_435_456), 16_384); assert_eq!(block_size(536_870_912), 23_168); assert_eq!(block_size(1_073_741_824), 32_768); assert_eq!(block_size(100_000), 700);
assert_eq!(block_size(u64::MAX), 32 * 1024);
}
#[test]
fn value_changes_when_content_changes() {
let a = b"hello world, this is a window of data!";
let b = b"hello world, this is a wlndow of data!";
assert_eq!(a.len(), b.len());
assert_ne!(weak_value(weak_init(a).0, weak_init(a).1), weak_value(weak_init(b).0, weak_init(b).1));
}
}