use crate::pack::pack;
use crate::scalar::{bits_for_max_value, check_num_bits};
use crate::unpack::unpack;
const CHUNK: usize = 128;
fn delta_step_sorted(prev: u32, v: u32) -> u32 {
assert!(
v >= prev,
"compress_sorted/num_bits_sorted require non-decreasing input: {v} follows {prev}"
);
v - prev
}
fn delta_step_strictly_sorted(prev: u32, v: u32) -> u32 {
assert!(
v > prev,
"compress_strictly_sorted/num_bits_strictly_sorted require strictly increasing \
input: {v} follows {prev}"
);
v - prev - 1
}
fn reconstruct_step_sorted(prev: u32, delta: u32) -> u32 {
prev.wrapping_add(delta)
}
fn reconstruct_step_strictly_sorted(prev: u32, delta: u32) -> u32 {
prev.wrapping_add(delta).wrapping_add(1)
}
fn num_bits_delta_encoded(decompressed: &[u32], delta_step: fn(u32, u32) -> u32) -> u8 {
let mut max_delta = 0u32;
for w in decompressed.windows(2) {
max_delta = max_delta.max(delta_step(w[0], w[1]));
}
bits_for_max_value(max_delta)
}
fn compress_delta_encoded(
decompressed: &[u32],
compressed: &mut [u8],
num_bits: u8,
delta_step: fn(u32, u32) -> u32,
) -> usize {
check_num_bits(num_bits);
let (&first, rest) = match decompressed.split_first() {
Some(pair) => pair,
None => return 0,
};
assert!(
compressed.len() >= 4,
"compressed buffer too small: need at least 4 bytes for the base-value header, got {}",
compressed.len()
);
compressed[0..4].copy_from_slice(&first.to_le_bytes());
let mut buf = [0u32; CHUNK];
let mut prev = first;
let mut out_pos = 4usize;
for chunk in rest.chunks(CHUNK) {
for (slot, &v) in buf.iter_mut().zip(chunk) {
*slot = delta_step(prev, v);
prev = v;
}
out_pos += pack(&buf[..chunk.len()], &mut compressed[out_pos..], num_bits);
}
out_pos
}
fn decompress_delta_encoded(
compressed: &[u8],
decompressed: &mut [u32],
num_bits: u8,
reconstruct_step: fn(u32, u32) -> u32,
) -> usize {
check_num_bits(num_bits);
let (first_slot, rest) = match decompressed.split_first_mut() {
Some(pair) => pair,
None => return 0,
};
assert!(
compressed.len() >= 4,
"compressed buffer too small: need at least 4 bytes for the base-value header, got {}",
compressed.len()
);
let mut header = [0u8; 4];
header.copy_from_slice(&compressed[0..4]);
let first = u32::from_le_bytes(header);
*first_slot = first;
let read = unpack(&compressed[4..], rest, num_bits);
let mut prev = first;
for slot in rest.iter_mut() {
let v = reconstruct_step(prev, *slot);
*slot = v;
prev = v;
}
4 + read
}
pub fn num_bits_sorted(decompressed: &[u32]) -> u8 {
num_bits_delta_encoded(decompressed, delta_step_sorted)
}
pub fn num_bits_strictly_sorted(decompressed: &[u32]) -> u8 {
num_bits_delta_encoded(decompressed, delta_step_strictly_sorted)
}
pub fn compress_sorted(decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize {
compress_delta_encoded(decompressed, compressed, num_bits, delta_step_sorted)
}
pub fn compress_strictly_sorted(
decompressed: &[u32],
compressed: &mut [u8],
num_bits: u8,
) -> usize {
compress_delta_encoded(
decompressed,
compressed,
num_bits,
delta_step_strictly_sorted,
)
}
pub fn decompress_sorted(compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize {
decompress_delta_encoded(compressed, decompressed, num_bits, reconstruct_step_sorted)
}
pub fn decompress_strictly_sorted(
compressed: &[u8],
decompressed: &mut [u32],
num_bits: u8,
) -> usize {
decompress_delta_encoded(
compressed,
decompressed,
num_bits,
reconstruct_step_strictly_sorted,
)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::testing::gen;
use proptest::prelude::*;
#[test]
fn num_bits_sorted_ignores_base_magnitude() {
assert_eq!(
num_bits_sorted(&[1_700_000_000, 1_700_000_003, 1_700_000_007]),
3
);
assert_eq!(num_bits_sorted(&[5]), 0); assert_eq!(num_bits_sorted(&[]), 0);
assert_eq!(num_bits_sorted(&[7, 7, 7]), 0); }
#[test]
fn num_bits_strictly_sorted_saves_one_bit_on_consecutive_runs() {
assert_eq!(num_bits_strictly_sorted(&[10, 11, 12, 13]), 0);
assert_eq!(num_bits_sorted(&[10, 11, 12, 13]), 1); }
#[test]
fn compress_sorted_empty_and_single_element() {
let mut compressed = vec![0u8; 16];
assert_eq!(compress_sorted(&[], &mut compressed, 4), 0);
let written = compress_sorted(&[42], &mut compressed, 4);
assert_eq!(written, 4);
let mut decompressed = vec![0u32; 1];
let read = decompress_sorted(&compressed[..written], &mut decompressed, 4);
assert_eq!(read, written);
assert_eq!(decompressed, vec![42]);
}
#[test]
fn compress_strictly_sorted_empty_and_single_element() {
let mut compressed = vec![0u8; 16];
assert_eq!(compress_strictly_sorted(&[], &mut compressed, 4), 0);
let written = compress_strictly_sorted(&[42], &mut compressed, 4);
assert_eq!(written, 4);
let mut decompressed = vec![0u32; 1];
let read = decompress_strictly_sorted(&compressed[..written], &mut decompressed, 4);
assert_eq!(read, written);
assert_eq!(decompressed, vec![42]);
}
#[test]
fn round_trip_bit_width_boundaries() {
for num_bits in [1u8, 32] {
let values: Vec<u32> = (0..50u32).collect();
let mut compressed = vec![0u8; values.len() * 4 + 8];
let written = compress_sorted(&values, &mut compressed, num_bits);
let mut decompressed = vec![0u32; values.len()];
let read = decompress_sorted(&compressed[..written], &mut decompressed, num_bits);
assert_eq!(read, written, "num_bits={num_bits}");
assert_eq!(decompressed, values, "num_bits={num_bits}");
}
}
#[test]
#[should_panic(expected = "require non-decreasing input")]
fn compress_sorted_panics_on_unsorted_input() {
let mut compressed = vec![0u8; 32];
compress_sorted(&[1, 5, 3], &mut compressed, 4);
}
#[test]
#[should_panic(expected = "require strictly increasing input")]
fn compress_strictly_sorted_panics_on_duplicate() {
let mut compressed = vec![0u8; 32];
compress_strictly_sorted(&[1, 3, 3], &mut compressed, 4);
}
#[test]
#[should_panic(expected = "num_bits must be in 1..=32")]
fn compress_sorted_panics_on_num_bits_zero() {
let mut compressed = vec![0u8; 32];
compress_sorted(&[1, 2, 3], &mut compressed, 0);
}
#[test]
#[should_panic(expected = "num_bits must be in 1..=32")]
fn compress_sorted_panics_on_num_bits_zero_even_for_single_element() {
let mut compressed = vec![0u8; 32];
compress_sorted(&[7], &mut compressed, 0);
}
#[test]
#[should_panic(expected = "need at least 4 bytes for the base-value header")]
fn compress_sorted_panics_on_undersized_header_buffer() {
let mut compressed = vec![0u8; 2];
compress_sorted(&[1, 2, 3], &mut compressed, 4);
}
#[test]
#[should_panic(expected = "compressed buffer too small")]
fn compress_sorted_panics_on_undersized_payload_buffer() {
let mut compressed = vec![0u8; 4];
compress_sorted(&[1, 2, 3], &mut compressed, 32);
}
proptest! {
#![proptest_config(gen::proptest_config(500))]
#[test]
fn prop_round_trip_sorted((num_bits, values) in gen::sorted_num_bits_and_values()) {
let mut compressed = vec![0u8; values.len() * 4 + 8];
let written = compress_sorted(&values, &mut compressed, num_bits);
let mut decompressed = vec![0u32; values.len()];
let read = decompress_sorted(&compressed[..written], &mut decompressed, num_bits);
prop_assert_eq!(read, written);
prop_assert_eq!(decompressed, values);
}
#[test]
fn prop_round_trip_strictly_sorted(
(num_bits, values) in gen::strictly_sorted_num_bits_and_values()
) {
let mut compressed = vec![0u8; values.len() * 4 + 8];
let written = compress_strictly_sorted(&values, &mut compressed, num_bits);
let mut decompressed = vec![0u32; values.len()];
let read =
decompress_strictly_sorted(&compressed[..written], &mut decompressed, num_bits);
prop_assert_eq!(read, written);
prop_assert_eq!(decompressed, values);
}
}
}