#![forbid(unsafe_code)]
use zrip_core::frame::MAX_BLOCK_SIZE;
const MAX_SPAN: usize = if cfg!(test) {
1 << 20
} else {
u32::MAX as usize
};
#[derive(Clone, Copy, Debug)]
pub(crate) struct PositionBase {
base: usize,
window: usize,
}
impl PositionBase {
pub(crate) fn new(window_log: u32) -> Self {
Self {
base: 0,
window: 1usize << window_log,
}
}
#[inline]
pub(crate) fn advance(&mut self, block_start: usize, block_end: usize) -> Option<u32> {
if block_end - self.base <= MAX_SPAN {
return None;
}
let shift = (block_start - self.base).saturating_sub(self.window);
if shift == 0 {
return None;
}
self.base += shift;
Some(shift as u32)
}
#[inline]
pub(crate) fn base(&self) -> usize {
self.base
}
}
pub(crate) fn reduce_hash_table(table: &mut [u32], shift: u32) {
for entry in table.iter_mut() {
if *entry < shift {
*entry = 0;
} else {
*entry -= shift;
}
}
}
#[inline(always)]
pub(crate) fn debug_assert_fits(block_end: usize, window_log: u32) {
debug_assert!(
block_end <= MAX_SPAN.max((2usize << window_log) + MAX_BLOCK_SIZE),
"block end {block_end} past the table span at window_log {window_log}"
);
}
#[cfg(all(test, feature = "std"))]
mod tests {
use super::*;
use crate::context::CompressContext;
use crate::{compress, compress_with_dict, compress_with_params, strategy};
use zrip_core::dict::Dictionary;
const BLOCK: usize = MAX_BLOCK_SIZE;
const INPUT_LEN: usize = 6 << 20;
const LEVELS: [i32; 10] = [-7, -6, -5, -4, -3, -2, -1, 1, 2, 3];
const RANDOM_SEEDS: u64 = 20;
const RANDOM_MIN_WINDOW_LOG: u32 = 13;
fn pool_slices(len: usize) -> Vec<u8> {
let mut x = 0x9E37_79B9_7F4A_7C15u64;
let mut next = move || {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x
};
let pool: Vec<u8> = (0..64 << 10).map(|_| b'a' + (next() >> 60) as u8).collect();
let mut out = Vec::with_capacity(len);
while out.len() < len {
let at = (next() as usize) % (pool.len() - 4096);
let n = 4096.min(len - out.len());
out.extend_from_slice(&pool[at..at + n]);
}
out
}
fn mixed(seed: u64, len: usize) -> Vec<u8> {
let mut x = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
let mut next = move || {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x
};
let pool: Vec<u8> = (0..16 << 10).map(|_| b'a' + (next() >> 60) as u8).collect();
let mut out = Vec::with_capacity(len);
while out.len() < len {
let n = ((next() as usize) % (256 << 10)).clamp(1, len - out.len());
match next() % 4 {
0 => out.extend((0..n).map(|_| next() as u8)),
1 => out.resize(out.len() + n, next() as u8),
_ => {
let end = out.len() + n;
while out.len() < end {
let at = (next() as usize) % (pool.len() - 1024);
let take = 1024.min(end - out.len());
out.extend_from_slice(&pool[at..at + take]);
}
}
}
}
out
}
fn dict() -> Dictionary {
let fixture = include_bytes!("../../../tests/fixtures/corpus_dict_roundtrip.bin");
let len = u32::from_le_bytes([fixture[0], fixture[1], fixture[2], fixture[3]]) as usize;
Dictionary::from_bytes(&fixture[4..4 + len]).unwrap()
}
#[test]
fn advance_keeps_one_window_behind_the_block() {
let window = 1usize << 19;
let mut positions = PositionBase::new(19);
assert_eq!(positions.advance(0, BLOCK), None);
assert_eq!(positions.base(), 0);
let start = MAX_SPAN - BLOCK / 2;
let end = start + BLOCK;
let shift = positions.advance(start, end).unwrap() as usize;
assert_eq!(shift, start - window);
assert_eq!(start - positions.base(), window);
assert_eq!(positions.advance(end, end + BLOCK), None);
}
#[test]
fn advance_waits_while_the_window_covers_the_span() {
let mut positions = PositionBase::new(27);
assert_eq!(positions.advance(MAX_SPAN, MAX_SPAN + BLOCK), None);
assert_eq!(positions.base(), 0);
}
#[test]
fn reduce_hash_table_moves_entries_and_clears_the_rest() {
let mut table = [0, 99, 100, 101, 500];
reduce_hash_table(&mut table, 100);
assert_eq!(table, [0, 0, 0, 1, 400]);
}
fn assert_rebase_is_transparent(frame: &[u8], plain: &[u8], label: &str) {
assert!(
frame == plain,
"{label}: rebased frame differs, {} vs {} bytes",
frame.len(),
plain.len()
);
}
#[test]
fn one_shot_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
for level in LEVELS {
let frame = compress(&data, level).unwrap();
let plain = zrip::compress(&data, level).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("level {level}"));
assert_eq!(zrip::decompress(&frame).unwrap(), data, "level {level}");
}
}
#[test]
fn custom_window_rebases_at_l4() {
let data = pool_slices(INPUT_LEN);
let params = strategy::level_params(4).unwrap().with_window_log(19);
let frame = compress_with_params(&data, ¶ms).unwrap();
let plain_params = zrip::encode::strategy::level_params(4)
.unwrap()
.with_window_log(19);
let plain = zrip::encode::compress_with_params(&data, &plain_params).unwrap();
assert_rebase_is_transparent(&frame, &plain, "L4 window_log 19");
assert_eq!(zrip::decompress(&frame).unwrap(), data);
}
#[test]
fn random_inputs_and_windows_survive_rebases() {
for seed in 0..RANDOM_SEEDS {
let level = LEVELS[seed as usize % LEVELS.len()];
let window_log =
RANDOM_MIN_WINDOW_LOG + (seed * 7 % (21 - RANDOM_MIN_WINDOW_LOG as u64)) as u32;
let len = (1 << 20) + (seed as usize * 131_071) % (1 << 20);
let data = mixed(seed, len);
let params = strategy::level_params(level)
.unwrap()
.with_window_log(window_log);
let frame = compress_with_params(&data, ¶ms).unwrap();
let plain_params = zrip::encode::strategy::level_params(level)
.unwrap()
.with_window_log(window_log);
let plain = zrip::encode::compress_with_params(&data, &plain_params).unwrap();
let label = format!("seed {seed} level {level} window_log {window_log}");
assert_eq!(zrip::decompress(&frame).unwrap(), data, "{label}");
assert!(
frame.len() <= plain.len() + plain.len() / 100 + 64,
"{label}: frame {} plain {}",
frame.len(),
plain.len()
);
}
}
#[cfg(feature = "ldm")]
#[test]
fn ldm_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
let opts = strategy::Options::default().window_log(19).ldm(true);
let plain_opts = zrip::Options::default().window_log(19).ldm(true);
for level in LEVELS {
let frame = crate::compress_opts(&data, level, &opts).unwrap();
let plain = zrip::compress_opts(&data, level, &plain_opts).unwrap();
assert!(
frame.len() < plain.len() + plain.len() / 10,
"LDM level {level}: frame {} plain {}",
frame.len(),
plain.len()
);
assert_eq!(zrip::decompress(&frame).unwrap(), data, "level {level}");
}
}
#[cfg(feature = "ldm")]
#[test]
#[ignore = "compresses 129 MiB per level, run with --release"]
fn ldm_frames_past_single_segment_are_transparent() {
let data = pool_slices(129 << 20);
let opts = strategy::Options::default().window_log(19).ldm(true);
let plain_opts = zrip::Options::default().window_log(19).ldm(true);
for level in LEVELS {
let frame = crate::compress_opts(&data, level, &opts).unwrap();
let plain = zrip::compress_opts(&data, level, &plain_opts).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("LDM level {level}"));
}
}
#[test]
fn dict_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
let dict = dict();
for level in LEVELS {
let frame = compress_with_dict(&data, level, &dict).unwrap();
let plain = zrip::compress_with_dict(&data, level, &dict).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("dict level {level}"));
let out = zrip::decompress_with_dict(&frame, &dict).unwrap();
assert_eq!(out, data, "level {level}");
}
}
#[test]
fn context_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
for level in LEVELS {
let mut ctx = CompressContext::new(level).unwrap();
let frame = ctx.compress(&data).unwrap();
let mut plain_ctx = zrip::CompressContext::new(level).unwrap();
let plain = plain_ctx.compress(&data).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("context level {level}"));
assert_eq!(zrip::decompress(&frame).unwrap(), data, "level {level}");
}
}
#[test]
fn context_ad_hoc_dict_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
let dict = dict();
for level in LEVELS {
let mut ctx = CompressContext::new(level).unwrap();
let frame = ctx.compress_with_dict(&data, &dict).unwrap();
let mut plain_ctx = zrip::CompressContext::new(level).unwrap();
let plain = plain_ctx.compress_with_dict(&data, &dict).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("ad hoc dict level {level}"));
let out = zrip::decompress_with_dict(&frame, &dict).unwrap();
assert_eq!(out, data, "level {level}");
}
}
#[test]
fn context_prepared_dict_frames_survive_rebases() {
let data = pool_slices(INPUT_LEN);
let dict = dict();
for level in LEVELS {
let mut ctx =
CompressContext::with_dict_for_size(level, dict.clone(), data.len()).unwrap();
let frame = ctx.compress(&data).unwrap();
let mut plain_ctx =
zrip::CompressContext::with_dict_for_size(level, dict.clone(), data.len()).unwrap();
let plain = plain_ctx.compress(&data).unwrap();
assert_rebase_is_transparent(&frame, &plain, &format!("prepared dict level {level}"));
let out = zrip::decompress_with_dict(&frame, &dict).unwrap();
assert_eq!(out, data, "level {level}");
}
}
}