const MIN_MATCH: usize = 4;
const MAX_OFFSET: usize = 65_535;
const HASH_BITS: usize = 12;
const HASH_BITS_LARGE: usize = 11;
const NARROW_TABLE_ABOVE: usize = 8192;
const HASH_SIZE: usize = 1 << HASH_BITS;
const EMPTY: u32 = 0x8000_0000;
trait Slot: Copy {
const EMPTY: Self;
const LIMIT: usize;
fn position(self) -> usize;
fn of(at: usize) -> Self;
}
impl Slot for u32 {
const EMPTY: u32 = EMPTY;
const LIMIT: usize = usize::MAX;
#[inline(always)]
fn position(self) -> usize {
self as usize
}
#[inline(always)]
fn of(at: usize) -> u32 {
at as u32
}
}
impl Slot for u16 {
const EMPTY: u16 = 0xFFFF;
const LIMIT: usize = 0x1_0000;
#[inline(always)]
fn position(self) -> usize {
self as usize
}
#[inline(always)]
fn of(at: usize) -> u16 {
at as u16
}
}
#[derive(Debug)]
pub struct Packer {
table: Box<[u32; HASH_SIZE]>,
}
impl Default for Packer {
fn default() -> Self {
Packer {
table: Box::new([EMPTY; HASH_SIZE]),
}
}
}
impl Packer {
pub fn new() -> Packer {
Packer::default()
}
pub fn pack(&mut self, input: &[u8], out: &mut Vec<u8>) -> bool {
pack_dispatch(input, out, &mut self.table)
}
}
#[inline]
fn pack_dispatch(input: &[u8], out: &mut Vec<u8>, table: &mut [u32; HASH_SIZE]) -> bool {
if crate::kernel::encode::kernel_is_production_packer() {
return crate::kernel::encode::pack_asm(input, out, table.as_mut_slice()).is_some();
}
pack_with(input, out, table)
}
#[derive(Debug)]
pub struct PortablePacker {
table: Box<[u32; HASH_SIZE]>,
}
impl Default for PortablePacker {
fn default() -> Self {
PortablePacker {
table: Box::new([EMPTY; HASH_SIZE]),
}
}
}
impl PortablePacker {
pub fn new() -> PortablePacker {
PortablePacker::default()
}
pub fn pack(&mut self, input: &[u8], out: &mut Vec<u8>) -> bool {
pack_with(input, out, &mut self.table)
}
}
#[derive(Debug)]
pub struct NarrowPacker {
table: Box<[u16; HASH_SIZE]>,
}
impl Default for NarrowPacker {
fn default() -> Self {
NarrowPacker {
table: Box::new([<u16 as Slot>::EMPTY; HASH_SIZE]),
}
}
}
impl NarrowPacker {
pub fn new() -> NarrowPacker {
NarrowPacker::default()
}
pub const LIMIT: usize = <u16 as Slot>::LIMIT;
pub fn pack(&mut self, input: &[u8], out: &mut Vec<u8>) -> bool {
out.clear();
if input.len() < HASH_WORD || input.len() > Self::LIMIT {
return false;
}
if !worth_packing(input) {
return false;
}
if input.len() > NARROW_TABLE_ABOVE {
pack_pass::<{ (64 - HASH_BITS_LARGE) as u32 }, u16>(
input,
out,
&mut self.table,
EVEN,
LAZY,
ADAPTIVE,
);
} else {
pack_pass::<{ (64 - HASH_BITS) as u32 }, u16>(
input,
out,
&mut self.table,
EVEN,
LAZY,
ADAPTIVE,
);
}
worth_storing(out.len(), input.len())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PackError {
Truncated,
BadOffset,
LengthMismatch,
TooLarge,
OutputTooSmall,
NonCanonicalHeader,
}
impl std::fmt::Display for PackError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(match self {
PackError::Truncated => "packed value ends mid-field",
PackError::BadOffset => "backward reference points before the output",
PackError::LengthMismatch => "packed value does not produce its declared length",
PackError::TooLarge => "packed value declares an implausible length",
PackError::NonCanonicalHeader => {
"packed value's header is longer than its length needs"
}
PackError::OutputTooSmall => "output buffer is smaller than the declared length",
})
}
}
impl std::error::Error for PackError {}
const MAX_UNPACKED: usize = 512 * 1024 * 1024;
#[inline]
fn hash4(word: u32, shift: u32) -> usize {
(word.wrapping_mul(0x9E37_79B1) >> shift) as usize
}
#[inline]
fn hash_shift(len: usize) -> u32 {
if len > NARROW_TABLE_ABOVE {
(64 - HASH_BITS_LARGE) as u32
} else {
(64 - HASH_BITS) as u32
}
}
const HASH_WORD: usize = 8;
#[inline]
fn hash5(seq: u64, shift: u32) -> usize {
((seq << 24).wrapping_mul(889_523_592_379u64) >> shift) as usize
}
#[inline]
unsafe fn word8(input: &[u8], at: usize) -> u64 {
u64::from_le(input.as_ptr().add(at).cast::<u64>().read_unaligned())
}
#[inline]
unsafe fn word4(input: &[u8], at: usize) -> u32 {
u32::from_le(input.as_ptr().add(at).cast::<u32>().read_unaligned())
}
const SKIP_TRIGGER: usize = 5;
const LAZY_UNTIL: usize = 16;
#[inline]
unsafe fn put_extended(mut remaining: usize, out: &mut Cursor) {
while remaining >= 255 {
out.byte(255);
remaining -= 255;
}
out.byte(remaining as u8);
}
fn get_extended(input: &[u8], at: &mut usize) -> Result<usize, PackError> {
let mut total = 0usize;
loop {
let byte = *input.get(*at).ok_or(PackError::Truncated)?;
*at += 1;
total = total
.checked_add(byte as usize)
.ok_or(PackError::TooLarge)?;
if byte != 255 {
return Ok(total);
}
if total > MAX_UNPACKED {
return Err(PackError::TooLarge);
}
}
}
pub fn pack(input: &[u8], out: &mut Vec<u8>) -> bool {
let mut table = Box::new([EMPTY; HASH_SIZE]);
pack_dispatch(input, out, &mut table)
}
const PROBE: usize = 1024;
const PROBE_BITS: u32 = 8;
const PROBE_WINDOWS: usize = 4;
const PROBE_ABOVE: usize = 2048;
#[inline]
fn worth_storing(packed: usize, original: usize) -> bool {
let saved = match original.checked_sub(packed) {
Some(n) => n,
None => return false,
};
saved >= 8 && saved * 8 >= original
}
#[inline(never)]
fn worth_packing(input: &[u8]) -> bool {
if input.len() <= PROBE_ABOVE {
return true;
}
let mut seen = [0u32; 1 << PROBE_BITS];
let wide = PROBE / PROBE_WINDOWS;
let step = input.len() / PROBE_WINDOWS;
for i in 0..PROBE_WINDOWS {
let start = i * step;
let last = (start + wide).min(input.len() - MIN_MATCH);
let mut at = start;
let mut misses = 1usize << SKIP_TRIGGER;
while at <= last {
let here = unsafe { word4(input, at) };
let slot = hash4(here, 32 - PROBE_BITS);
let stored = seen[slot];
seen[slot] = at as u32 + 1;
if stored != 0 && unsafe { word4(input, stored as usize - 1) } == here {
return true;
}
at += misses >> SKIP_TRIGGER;
misses += 1;
}
}
false
}
fn pack_with(input: &[u8], out: &mut Vec<u8>, table: &mut [u32; HASH_SIZE]) -> bool {
out.clear();
if input.len() < HASH_WORD {
return false;
}
if !worth_packing(input) {
return false;
}
if input.len() > NARROW_TABLE_ABOVE {
pack_pass::<{ (64 - HASH_BITS_LARGE) as u32 }, u32>(
input, out, table, EVEN, LAZY, ADAPTIVE,
);
} else {
pack_pass::<{ (64 - HASH_BITS) as u32 }, u32>(input, out, table, EVEN, LAZY, ADAPTIVE);
}
worth_storing(out.len(), input.len())
}
const LAZY_REACH: usize = 1;
const SPLIT_WINDOW: usize = 16;
const ADAPTIVE: bool = true;
#[cfg(test)]
const FIXED: bool = false;
const LAZY: bool = true;
#[cfg(test)]
const EAGER: bool = false;
#[cfg(test)]
fn pack_with_eager(input: &[u8], out: &mut Vec<u8>, table: &mut [u32; HASH_SIZE]) -> bool {
out.clear();
if input.len() < HASH_WORD {
return false;
}
if input.len() > NARROW_TABLE_ABOVE {
pack_pass::<{ (64 - HASH_BITS_LARGE) as u32 }, u32>(input, out, table, EVEN, EAGER, FIXED);
} else {
pack_pass::<{ (64 - HASH_BITS) as u32 }, u32>(input, out, table, EVEN, EAGER, FIXED);
}
worth_storing(out.len(), input.len())
}
fn pack_pass<const SHIFT: u32, S: Slot>(
input: &[u8],
out: &mut Vec<u8>,
table: &mut [S; HASH_SIZE],
start_split: Split,
lazy: bool,
adaptive: bool,
) {
debug_assert_eq!(start_split, EVEN, "nothing starts in the wide split");
put_header(input.len(), false, out);
let header_len = out.len();
let want = Cursor::room(input.len());
if out.capacity() - out.len() < want {
out.reserve(want);
}
let mut cur = unsafe { Cursor::new(out) };
let mut split = start_split;
let mut switch: Option<(usize, usize)> = None;
let mut recent: u32 = 0;
let mut seen = 0usize;
let mut last_offset = usize::MAX;
let mut blocks = 0usize;
let mut saturated = 0usize;
let mut at = 0usize;
let mut literal_start = 0usize;
let mut misses = 1usize << SKIP_TRIGGER;
let mut next_at = at;
debug_assert_eq!(SHIFT, hash_shift(input.len()));
let last = input.len() - HASH_WORD;
loop {
at = next_at;
next_at = at + (misses >> SKIP_TRIGGER);
if at > last {
break;
}
let word = unsafe { word8(input, at) };
let here = word as u32;
let slot = hash5(word, SHIFT);
let stored = table[slot];
table[slot] = S::of(at);
let candidate = stored.position();
let matched = if candidate < at
&& at - candidate <= MAX_OFFSET
&& unsafe { word4(input, candidate) } == here
{
MIN_MATCH + unsafe { common_prefix(input, candidate + MIN_MATCH, at + MIN_MATCH) }
} else {
0
};
if matched < MIN_MATCH {
misses += 1;
continue;
}
misses = 1 << SKIP_TRIGGER;
let mut candidate = candidate;
let mut matched = matched;
if lazy && matched < LAZY_UNTIL {
'lazy: loop {
for step in 1..=LAZY_REACH {
let next = at + step;
if next > last {
break 'lazy;
}
let ahead = unsafe { word4(input, next) };
let slot = hash5(unsafe { word8(input, next) }, SHIFT);
let stored = table[slot];
table[slot] = S::of(next);
let other = stored.position();
if other < next
&& next - other <= MAX_OFFSET
&& unsafe { word4(input, other) } == ahead
{
let len = MIN_MATCH
+ unsafe { common_prefix(input, other + MIN_MATCH, next + MIN_MATCH) };
if len > matched + step - 1 {
matched = len;
candidate = other;
at = next;
continue 'lazy;
}
}
}
break;
}
}
let mut back = 0usize;
while candidate > back
&& at - back > literal_start
&& input[candidate - back - 1] == input[at - back - 1]
{
back += 1;
}
blocks += 1;
let overflowed = matched + back - MIN_MATCH >= split.mat_max();
if overflowed {
saturated += 1;
}
if adaptive && switch.is_none() && split == EVEN {
recent = (recent << 1) | overflowed as u32;
seen += 1;
let mask = (1u32 << SPLIT_WINDOW) - 1;
let fits = |v: usize| v < 1 << (8 * switch_width(input.len()));
if seen >= SPLIT_WINDOW
&& (recent & mask).count_ones() as usize * 2 > SPLIT_WINDOW
&& fits(cur.len() - header_len)
&& fits(literal_start)
{
switch = Some((cur.len() - header_len, literal_start));
split = LONG_MATCH;
last_offset = usize::MAX;
}
}
let literals = &input[literal_start..at - back];
let wide = wide_literals_fit(literals, at - back, input.len())
.then(|| &input[literal_start..literal_start + WIDE_LITERAL]);
let offset = at - candidate;
let repeat = split.rep_bits == 1 && offset == last_offset;
last_offset = offset;
emit_block(
literals,
offset,
matched + back,
&mut cur,
split,
wide,
repeat,
);
at += matched;
next_at = at;
literal_start = at;
}
emit_literals_only(&input[literal_start..], &mut cur, split);
unsafe { out.set_len(cur.len()) };
if let Some((in_at, out_at)) = switch {
let w = switch_width(input.len());
put_switch(in_at, w, out);
put_switch(out_at, w, out);
debug_assert!(out[0] >> 6 != 0, "a switching value is never one byte");
out[0] |= HYBRID_BIT;
}
let _ = (blocks, saturated);
}
const HEADER_MASK: [u8; 4] = [0x3F, 0x1F, 0x1F, 0x1F];
const HEADER_SHIFT: [u32; 4] = [24, 16, 8, 0];
const HYBRID_BIT: u8 = 0x20;
#[inline]
fn header_len(declared: usize) -> usize {
match declared {
0..=63 => 1,
64..=8191 => 2,
8192..=2_097_151 => 3,
_ => 4,
}
}
#[inline]
fn put_header(declared: usize, hybrid: bool, out: &mut Vec<u8>) {
let n = header_len(declared);
let class = (n - 1) as u8;
let payload = declared as u32;
let top = (payload >> (8 * (n - 1))) as u8;
debug_assert!(top & !HEADER_MASK[class as usize] == 0);
let mut first = (class << 6) | top;
if hybrid && n > 1 {
first |= HYBRID_BIT;
}
out.push(first);
for i in (0..n - 1).rev() {
out.push((payload >> (8 * i)) as u8);
}
}
#[inline]
fn get_header(input: &[u8]) -> Option<(usize, bool, usize)> {
let head: [u8; 4] = match input.get(..4) {
Some(b) => b.try_into().unwrap(),
None => {
let mut b = [0u8; 4];
b[..input.len()].copy_from_slice(input);
b
}
};
let class = (head[0] >> 6) as usize;
let declared = u32::from_be_bytes([head[0] & HEADER_MASK[class], head[1], head[2], head[3]])
>> HEADER_SHIFT[class];
let hybrid = class != 0 && head[0] & HYBRID_BIT != 0;
let n = class + 1;
if input.len() < n {
return None;
}
Some((declared as usize, hybrid, n))
}
#[inline]
fn switch_width(declared: usize) -> usize {
if declared <= 0x1_0000 {
2
} else {
4
}
}
#[inline]
fn put_switch(value: usize, width: usize, out: &mut Vec<u8>) {
match width {
2 => out.extend_from_slice(&(value as u16).to_le_bytes()),
_ => out.extend_from_slice(&(value as u32).to_le_bytes()),
}
}
#[inline]
fn get_switch(bytes: &[u8]) -> usize {
match bytes.len() {
2 => u16::from_le_bytes(bytes.try_into().unwrap()) as usize,
_ => u32::from_le_bytes(bytes.try_into().unwrap()) as usize,
}
}
unsafe fn common_prefix(input: &[u8], a: usize, b: usize) -> usize {
let limit = input.len() - b;
let base = input.as_ptr();
let mut i = 0;
while i + 8 <= limit {
let left = u64::from_le(base.add(a + i).cast::<u64>().read_unaligned());
let right = u64::from_le(base.add(b + i).cast::<u64>().read_unaligned());
let diff = left ^ right;
if diff != 0 {
return i + (diff.trailing_zeros() / 8) as usize;
}
i += 8;
}
while i < limit && *base.add(a + i) == *base.add(b + i) {
i += 1;
}
i
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Split {
lit_bits: u32,
rep_bits: u32,
}
const EVEN: Split = Split {
lit_bits: 4,
rep_bits: 0,
};
const LONG_MATCH: Split = Split {
lit_bits: 2,
rep_bits: 1,
};
impl Split {
#[inline]
fn lit_max(self) -> usize {
(1 << self.lit_bits) - 1
}
#[inline]
fn mat_max(self) -> usize {
(1 << (8 - self.lit_bits - self.rep_bits)) - 1
}
#[inline]
fn mat_shift(self) -> u32 {
self.rep_bits
}
#[inline]
fn shift(self) -> u32 {
8 - self.lit_bits
}
#[inline]
fn other(self) -> Split {
if self == EVEN {
LONG_MATCH
} else {
EVEN
}
}
#[inline]
fn kernel(self) -> crate::kernel::decode::Split {
if self == LONG_MATCH {
crate::kernel::decode::Split::WideMatch
} else {
crate::kernel::decode::Split::Even
}
}
}
const WIDE_LITERAL: usize = 16;
#[inline]
fn wide_literals_fit(literals: &[u8], end: usize, input_len: usize) -> bool {
literals.len() <= WIDE_LITERAL && end + WIDE_LITERAL <= input_len
}
struct Cursor {
p: *mut u8,
base: *mut u8,
#[cfg(debug_assertions)]
limit: *mut u8,
}
impl Cursor {
#[inline]
fn room(n: usize) -> usize {
n + n / MIN_MATCH * 3 + n / 128 + WIDE_LITERAL + 64
}
unsafe fn new(out: &mut Vec<u8>) -> Cursor {
let base = out.as_mut_ptr();
Cursor {
p: base.add(out.len()),
base,
#[cfg(debug_assertions)]
limit: base.add(out.capacity()),
}
}
#[inline]
fn guard(&self, _n: usize) {
#[cfg(debug_assertions)]
debug_assert!(
unsafe { self.p.add(_n) } <= self.limit,
"the packer wrote past its reserve"
);
}
#[inline]
unsafe fn byte(&mut self, b: u8) {
self.guard(1);
*self.p = b;
self.p = self.p.add(1);
}
#[inline]
unsafe fn offset(&mut self, v: u16) {
self.guard(2);
self.p.cast::<u16>().write_unaligned(v.to_le());
self.p = self.p.add(2);
}
#[inline]
unsafe fn literals_wide(&mut self, src: &[u8], n: usize) {
debug_assert!(src.len() >= WIDE_LITERAL, "the wide source is short");
debug_assert!(n <= WIDE_LITERAL, "the run is wider than the move");
self.guard(WIDE_LITERAL);
std::ptr::copy_nonoverlapping(src.as_ptr(), self.p, WIDE_LITERAL);
self.p = self.p.add(n);
}
#[inline]
unsafe fn literals(&mut self, src: &[u8]) {
self.guard(src.len());
std::ptr::copy_nonoverlapping(src.as_ptr(), self.p, src.len());
self.p = self.p.add(src.len());
}
#[inline]
fn len(&self) -> usize {
unsafe { self.p.offset_from(self.base) as usize }
}
}
fn emit_block(
literals: &[u8],
offset: usize,
matched: usize,
out: &mut Cursor,
split: Split,
wide: Option<&[u8]>,
repeat: bool,
) {
let match_extra = matched - MIN_MATCH;
let lit_field = literals.len().min(split.lit_max());
let mat_field = match_extra.min(split.mat_max());
unsafe {
out.byte(
((lit_field as u8) << split.shift())
| ((mat_field as u8) << split.mat_shift())
| (repeat as u8 & split.rep_bits as u8),
);
if literals.len() >= split.lit_max() {
put_extended(literals.len() - split.lit_max(), out);
}
match wide {
Some(src) => out.literals_wide(src, literals.len()),
None => out.literals(literals),
}
if !repeat {
out.offset(offset as u16);
}
if match_extra >= split.mat_max() {
put_extended(match_extra - split.mat_max(), out);
}
}
}
fn emit_literals_only(literals: &[u8], out: &mut Cursor, split: Split) {
let lit_field = literals.len().min(split.lit_max());
unsafe {
out.byte((lit_field as u8) << split.shift());
if literals.len() >= split.lit_max() {
put_extended(literals.len() - split.lit_max(), out);
}
out.literals(literals);
}
}
#[inline]
unsafe fn overlapping_copy(dst: *mut u8, src: *const u8, offset: usize, len: usize) {
let mut written = 0usize;
let mut chunk = offset;
while written < len {
let take = chunk.min(len - written);
std::ptr::copy_nonoverlapping(src, dst.add(written), take);
written += take;
chunk *= 2;
}
}
const OVERRUN: usize = 32;
const FAST_INPUT_SLACK: usize = if FAST_LITERAL > OVERRUN {
FAST_LITERAL
} else {
OVERRUN
};
const FAST_LITERAL: usize = 16;
#[inline]
unsafe fn wildcopy(mut dst: *mut u8, mut src: *const u8, len: usize) {
let mut copied = 0usize;
loop {
std::ptr::copy_nonoverlapping(src, dst, OVERRUN);
copied += OVERRUN;
if copied >= len {
return;
}
src = src.add(OVERRUN);
dst = dst.add(OVERRUN);
}
}
pub fn unpack(input: &[u8], out: &mut Vec<u8>) -> Result<(), PackError> {
if crate::kernel::decode::asm_available() {
if let Ok(f) = frame(input) {
let ok = match f.switch {
None => {
crate::kernel::decode::unpack_asm(f.body, out, f.declared, f.split.kernel())
}
Some(switch) => crate::kernel::decode::unpack_asm_hybrid(
f.body,
out,
f.declared,
switch,
f.split.kernel(),
f.split.other().kernel(),
),
};
if ok {
return Ok(());
}
}
}
unpack_portable(input, out)
}
pub fn unpack_into_slice(input: &[u8], out: &mut [u8]) -> Result<usize, PackError> {
let f = frame(input)?;
if out.len() < f.declared {
return Err(PackError::OutputTooSmall);
}
if crate::kernel::decode::asm_available() {
let ok = match f.switch {
None => {
crate::kernel::decode::unpack_into_slice(f.body, out, f.declared, f.split.kernel())
}
Some(switch) => crate::kernel::decode::unpack_hybrid_into_slice(
f.body,
out,
f.declared,
switch,
f.split.kernel(),
f.split.other().kernel(),
),
};
if ok {
return Ok(f.declared);
}
}
unsafe { unpack_framed(f, out.as_mut_ptr(), out.len()) }
}
pub fn declared_len(input: &[u8]) -> Result<usize, PackError> {
Ok(frame(input)?.declared)
}
pub const fn decompressed_bound(declared: usize) -> usize {
declared + crate::kernel::decode::UNPACK_SLACK
}
pub fn unpack_into(block: &[u8], out: &mut Vec<u8>, declared: usize) -> Result<(), PackError> {
if declared > MAX_UNPACKED {
return Err(PackError::TooLarge);
}
if crate::kernel::decode::asm_available()
&& crate::kernel::decode::unpack_lz4_asm(block, out, declared)
{
return Ok(());
}
let mut framed = Vec::with_capacity(block.len() + 10);
put_header(declared, false, &mut framed);
framed.extend_from_slice(block);
unpack_portable(&framed, out)
}
struct Frame<'a> {
declared: usize,
body: &'a [u8],
split: Split,
switch: Option<(usize, usize)>,
}
fn frame(input: &[u8]) -> Result<Frame<'_>, PackError> {
let (declared, hybrid, header) = get_header(input).ok_or(PackError::Truncated)?;
const CLASS_MIN: [usize; 4] = [0, 64, 8192, 2_097_152];
if declared < CLASS_MIN[(header - 1) & 3] {
return Err(PackError::NonCanonicalHeader);
}
let split = EVEN;
let rest = input.get(header..).ok_or(PackError::Truncated)?;
if !hybrid {
return Ok(Frame {
declared,
body: rest,
split,
switch: None,
});
}
let w = switch_width(declared);
let cut = rest.len().checked_sub(2 * w).ok_or(PackError::Truncated)?;
let (body, tail) = rest.split_at(cut);
let in_at = get_switch(&tail[..w]);
let out_at = get_switch(&tail[w..]);
if in_at > body.len() || out_at == 0 || out_at >= declared {
return Err(PackError::Truncated);
}
Ok(Frame {
declared,
body,
split,
switch: Some((in_at, out_at)),
})
}
fn unpack_portable(input: &[u8], out: &mut Vec<u8>) -> Result<(), PackError> {
out.clear();
let f = frame(input)?;
let declared = f.declared;
out.reserve(declared + OVERRUN);
let produced = unsafe { unpack_framed(f, out.as_mut_ptr(), out.capacity())? };
debug_assert_eq!(produced, declared);
unsafe { out.set_len(produced) };
Ok(())
}
unsafe fn unpack_framed(f: Frame<'_>, base: *mut u8, capacity: usize) -> Result<usize, PackError> {
let (declared, body) = (f.declared, f.body);
let mut split = f.split;
let switch_at = f.switch.map(|(_, out_at)| out_at);
let mut produced = 0usize;
let mut at = 0usize;
let mut last_offset = 0usize;
let input = body;
while produced < declared {
if switch_at == Some(produced) {
split = split.other();
last_offset = 0;
}
let token = *input.get(at).ok_or(PackError::Truncated)?;
let short_literal = (token >> split.shift()) as usize;
let short_match = ((token >> split.mat_shift()) & split.mat_max() as u8) as usize;
let repeat = split.rep_bits == 1 && token & 1 == 1;
if short_literal != split.lit_max()
&& short_match != split.mat_max()
&& short_match + MIN_MATCH <= OVERRUN
&& at + 1 + short_literal + 2 + FAST_INPUT_SLACK <= input.len()
&& produced + 64 <= capacity
{
let literal_at = at + 1;
let offset_at = literal_at + short_literal;
let offset = if repeat {
last_offset
} else {
u16::from_le_bytes(input[offset_at..offset_at + 2].try_into().unwrap()) as usize
};
last_offset = offset;
let match_len = short_match + MIN_MATCH;
let after_literals = produced + short_literal;
if offset == 0 || offset > after_literals {
return Err(PackError::BadOffset);
}
if after_literals + match_len > declared {
return Err(PackError::LengthMismatch);
}
unsafe {
std::ptr::copy_nonoverlapping(
input.as_ptr().add(literal_at),
base.add(produced),
FAST_LITERAL,
);
let src = base.add(after_literals - offset);
let dst = base.add(after_literals);
if offset >= OVERRUN {
std::ptr::copy_nonoverlapping(src, dst, OVERRUN);
} else {
overlapping_copy(dst, src, offset, match_len);
}
}
produced = after_literals + match_len;
at = offset_at + if repeat { 0 } else { 2 };
continue;
}
at += 1;
let mut literal_len = (token >> split.shift()) as usize;
if literal_len == split.lit_max() {
literal_len += get_extended(input, &mut at)?;
}
let end = at.checked_add(literal_len).ok_or(PackError::TooLarge)?;
if end > input.len() {
return Err(PackError::Truncated);
}
if produced + literal_len > declared {
return Err(PackError::LengthMismatch);
}
if literal_len > 0 {
let blocked = literal_len.next_multiple_of(OVERRUN);
unsafe {
if end + OVERRUN <= input.len() && produced + blocked <= capacity {
wildcopy(base.add(produced), input.as_ptr().add(at), literal_len);
} else {
std::ptr::copy_nonoverlapping(
input.as_ptr().add(at),
base.add(produced),
literal_len,
);
}
}
produced += literal_len;
}
at = end;
if produced == declared {
break;
}
let offset = if repeat {
last_offset
} else {
let b = input.get(at..at + 2).ok_or(PackError::Truncated)?;
at += 2;
u16::from_le_bytes([b[0], b[1]]) as usize
};
last_offset = offset;
let mut match_len = ((token >> split.mat_shift()) & split.mat_max() as u8) as usize;
if match_len == split.mat_max() {
match_len += get_extended(input, &mut at)?;
}
let match_len = match_len + MIN_MATCH;
if offset == 0 || offset > produced {
return Err(PackError::BadOffset);
}
if produced + match_len > declared {
return Err(PackError::LengthMismatch);
}
unsafe {
let src = base.add(produced - offset);
let dst = base.add(produced);
if offset >= OVERRUN && produced + match_len.next_multiple_of(OVERRUN) <= capacity {
wildcopy(dst, src, match_len);
} else {
overlapping_copy(dst, src, offset, match_len);
}
}
produced += match_len;
}
if produced != declared {
return Err(PackError::LengthMismatch);
}
Ok(produced)
}
#[cfg(test)]
mod tests {
use super::*;
fn bulk(native: usize) -> usize {
if cfg!(miri) {
(native / 50).max(1)
} else {
native
}
}
fn biggest(native: usize) -> usize {
if cfg!(miri) {
native.min(4096)
} else {
native
}
}
fn records(total: usize) -> Vec<u8> {
let mut out = Vec::with_capacity(total);
let mut i = 0u64;
while out.len() < total {
out.extend_from_slice(
format!("{{\"id\":{i},\"tenant\":\"t42\",\"active\":true}}").as_bytes(),
);
i += 1;
}
out.truncate(total);
out
}
fn roundtrip(input: &[u8]) {
let mut packed = Vec::new();
let mut unpacked = Vec::new();
if pack(input, &mut packed) {
unpack(&packed, &mut unpacked).expect("must unpack what it packed");
assert_eq!(unpacked, input, "round trip changed the bytes");
}
}
#[test]
fn a_saving_has_to_be_worth_the_decode() {
assert!(!worth_storing(31, 32));
assert!(!worth_storing(9, 16));
assert!(worth_storing(8, 16));
assert!(worth_storing(896, 1024));
assert!(!worth_storing(897, 1024));
assert!(worth_storing(195, 512));
assert!(worth_storing(487, 4096));
assert!(worth_storing(5524, 65536));
assert!(!worth_storing(600, 512));
assert!(!worth_storing(512, 512));
}
#[test]
fn round_trips_repetitive_data() {
let input = vec![b'x'; 4096];
let mut packed = Vec::new();
assert!(pack(&input, &mut packed));
assert!(
packed.len() < input.len() / 20,
"4096 identical bytes packed to {} bytes",
packed.len()
);
let mut out = Vec::new();
unpack(&packed, &mut out).unwrap();
assert_eq!(out, input);
}
#[test]
fn round_trips_structured_data() {
let mut input = Vec::new();
for i in 0..500 {
input.extend_from_slice(format!("{{\"user\":{i},\"active\":true}}").as_bytes());
}
let mut packed = Vec::new();
assert!(pack(&input, &mut packed), "JSON-ish data must compress");
let mut out = Vec::new();
unpack(&packed, &mut out).unwrap();
assert_eq!(out, input);
}
#[test]
fn refuses_when_it_would_not_help() {
let mut incompressible = Vec::new();
let mut state = 0x2545_F491_4F6C_DD1Du64;
for _ in 0..4096 {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
incompressible.push(state as u8);
}
let mut packed = Vec::new();
assert!(
!pack(&incompressible, &mut packed),
"random bytes must not claim to compress"
);
}
#[test]
fn handles_the_edges() {
for input in [
b"".as_slice(),
b"a",
b"ab",
b"abc",
b"abcd",
b"abcde",
&[0u8; 15],
&[0u8; 16],
&[0u8; 17],
&[0xFFu8; 300],
] {
roundtrip(input);
}
}
#[test]
fn overlapping_matches_round_trip() {
let mut input = b"ab".to_vec();
input.extend(std::iter::repeat(b'c').take(1000));
input.extend_from_slice(b"ab");
roundtrip(&input);
let alternating: Vec<u8> = (0..2000)
.map(|i| if i % 2 == 0 { b'a' } else { b'b' })
.collect();
roundtrip(&alternating);
}
#[test]
fn corrupt_input_is_refused_rather_than_trusted() {
let input = vec![b'q'; bulk(2000)];
let mut packed = Vec::new();
assert!(pack(&input, &mut packed));
let mut out = Vec::new();
for cut in 0..packed.len() {
let _ = unpack(&packed[..cut], &mut out);
}
for i in 0..packed.len() {
for bit in 0..8 {
let mut broken = packed.clone();
broken[i] ^= 1 << bit;
let _ = unpack(&broken, &mut out);
}
}
let mut absurd = Vec::new();
put_header(0x1FFF_FFFF, false, &mut absurd);
absurd.push(0);
assert_eq!(unpack(&absurd, &mut out), Err(PackError::Truncated));
}
#[test]
fn hostile_input_stays_within_bounds() {
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state
};
let source = records(bulk(3000));
let mut packed = Vec::new();
assert!(pack(&source, &mut packed));
let mut out = Vec::new();
for _ in 0..bulk(4000) {
let mut broken = packed.clone();
let hits = 1 + (next() % 6) as usize;
for _ in 0..hits {
let at = (next() as usize) % broken.len();
broken[at] = next() as u8;
}
let _ = unpack(&broken, &mut out);
}
for len in [0usize, 1, 63, 64, 8191, 8192, 1 << 20, 2_097_151, 2_097_152] {
for hybrid in [false, true] {
for _ in 0..bulk(200) {
let mut stream = Vec::new();
put_header(len, hybrid, &mut stream);
for _ in 0..(next() % 200) {
stream.push(next() as u8);
}
let _ = unpack(&stream, &mut out);
}
}
}
for _ in 0..bulk(2000) {
let n = (next() % 300) as usize;
let stream: Vec<u8> = (0..n).map(|_| next() as u8).collect();
let _ = unpack(&stream, &mut out);
}
}
#[test]
fn both_match_copy_paths_agree() {
for offset in [1usize, 2, 3, 7, 8, 15, 16, 31, 32, 33, 64, 200] {
let mut input = Vec::new();
let pattern: Vec<u8> = (0..offset).map(|i| b'a' + (i % 26) as u8).collect();
while input.len() < 4000 {
input.extend_from_slice(&pattern);
}
input.truncate(4000);
roundtrip(&input);
}
}
#[cfg(feature = "liblz4")]
#[test]
fn our_decoder_reads_what_liblz4_wrote() {
#[link(name = "lz4")]
extern "C" {
fn LZ4_compress_default(src: *const u8, dst: *mut u8, n: i32, cap: i32) -> i32;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [1usize, 4, 15, 16, 17, 63, 64, 65, 1000, 4096, 65_536] {
cases.push(records(size));
cases.push(vec![b'a'; size]);
cases.push((0..size).map(|_| noise_byte()).collect());
}
cases.push(b"ab".repeat(3000));
cases.push(b"abcdefg".repeat(900));
let mut out = Vec::new();
for data in &cases {
let mut block = vec![0u8; data.len() + 1024];
let n = unsafe {
LZ4_compress_default(
data.as_ptr(),
block.as_mut_ptr(),
data.len() as i32,
block.len() as i32,
)
};
assert!(n > 0, "liblz4 refused {} bytes", data.len());
block.truncate(n as usize);
unpack_into(&block, &mut out, data.len())
.unwrap_or_else(|e| panic!("{} bytes from liblz4: {e}", data.len()));
assert_eq!(&out[..], &data[..], "differs on {} bytes", data.len());
}
}
#[test]
fn a_narrow_table_packs_the_same_bytes() {
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [
8usize, 64, 512, 2048, 2049, 4096, 8192, 8193, 40_000, 65_536,
] {
cases.push(records(size));
cases.push(vec![b'a'; size]);
cases.push((0..size).map(|_| next() as u8).collect());
}
let mut wide_out = Vec::new();
let mut narrow_out = Vec::new();
let mut wide = PortablePacker::new();
let mut narrow = NarrowPacker::new();
let mut compared = 0usize;
for input in &cases {
if input.len() > NarrowPacker::LIMIT {
continue;
}
let a = wide.pack(input, &mut wide_out);
let b = narrow.pack(input, &mut narrow_out);
assert_eq!(
a,
b,
"the two widths disagreed on whether packing helped for {} bytes",
input.len()
);
if a {
assert_eq!(
wide_out,
narrow_out,
"a {}-byte value packs differently at sixteen bits",
input.len()
);
compared += 1;
}
}
assert!(compared > 10, "only {compared} cases actually packed");
}
#[test]
fn the_kernel_reads_a_block_that_is_all_literals() {
if !crate::kernel::decode::asm_available() {
return;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut refused = Vec::new();
for n in [
1usize, 4, 14, 15, 16, 17, 24, 30, 31, 32, 33, 40, 47, 48, 49, 56, 63, 64, 65, 96, 127,
128, 129, 269, 270, 512, 1000, 4096, 65_536,
] {
let data: Vec<u8> = (0..n).map(|_| noise_byte()).collect();
let mut block = Vec::new();
block.push((n.min(15) as u8) << 4);
if n >= 15 {
let mut rest = n - 15;
while rest >= 255 {
block.push(255);
rest -= 255;
}
block.push(rest as u8);
}
block.extend_from_slice(&data);
for &body in crate::kernel::decode::Lz4Body::all() {
let mut out = vec![0u8; n + crate::kernel::decode::UNPACK_SLACK];
if !crate::kernel::decode::unpack_lz4_into_slice_on(body, &block, &mut out, n) {
refused.push(n);
continue;
}
assert_eq!(
&out[..n],
&data[..],
"the {body:?} LZ4 body produced wrong bytes for a {n}-byte run"
);
assert_eq!(
out.len(),
n + crate::kernel::decode::UNPACK_SLACK,
"the buffer moved"
);
}
}
assert!(
refused.is_empty(),
"the kernel refused an all-literal block at these lengths: {refused:?}"
);
}
#[test]
fn the_kernel_reads_blocks_with_no_literals() {
if !crate::kernel::decode::asm_available() {
return;
}
let mut failed = Vec::new();
let (mut decided, mut refused) = (0usize, 0usize);
for offset in [1usize, 2, 7, 15, 16, 17, 31, 32, 33, 64, 255, 256, 1000] {
for mat in [
4usize, 5, 14, 18, 19, 20, 31, 32, 33, 66, 200, 268, 269, 270, 271, 600,
] {
let seed: Vec<u8> = (0..offset.max(16) + 8)
.map(|i| (i as u8).wrapping_mul(31).wrapping_add(11))
.collect();
let tail: Vec<u8> = (0..12u8).map(|i| i ^ 0x3C).collect();
let mut block = Vec::new();
let mut want = Vec::new();
push_token(&mut block, seed.len(), 0);
block.extend_from_slice(&seed);
block.extend_from_slice(&(offset as u16).to_le_bytes());
want.extend_from_slice(&seed);
for _ in 0..4 {
want.push(want[want.len() - offset]);
}
for _ in 0..3 {
push_token(&mut block, 0, mat - 4);
block.extend_from_slice(&(offset as u16).to_le_bytes());
push_extension(&mut block, mat - 4);
for _ in 0..mat {
want.push(want[want.len() - offset]);
}
}
push_token(&mut block, tail.len(), 0);
block.extend_from_slice(&tail);
want.extend_from_slice(&tail);
let n = want.len();
for &body in crate::kernel::decode::Lz4Body::all() {
let mut out = vec![0u8; n + crate::kernel::decode::UNPACK_SLACK];
if !crate::kernel::decode::unpack_lz4_into_slice_on(body, &block, &mut out, n) {
refused += 1;
continue; }
decided += 1;
if out[..n] != want[..] {
let at = (0..n).find(|&i| out[i] != want[i]).unwrap();
failed.push((body, offset, mat, at));
}
}
}
}
assert!(
failed.is_empty(),
"a block with no literals decoded wrong: {failed:?}"
);
assert_eq!(
refused,
0,
"the kernel refused {refused} of {} well-formed blocks",
decided + refused
);
}
fn push_token(block: &mut Vec<u8>, lit: usize, mat_nibble: usize) {
block.push(((lit.min(15) as u8) << 4) | mat_nibble.min(15) as u8);
push_extension(block, lit);
}
fn push_extension(block: &mut Vec<u8>, n: usize) {
if n >= 15 {
let mut rest = n - 15;
while rest >= 255 {
block.push(255);
rest -= 255;
}
block.push(rest as u8);
}
}
#[test]
fn the_kernel_reads_a_match_that_overlaps_itself() {
let mut failed = Vec::new();
for offset in 1usize..=40 {
for extra in [0usize, 1, 7, 13, 60, 200, 300] {
let run = offset + extra + 4;
let lit = offset;
let (lit_tok, mat) = (lit.min(15), run - 4);
let mut block = vec![((lit_tok as u8) << 4) | (mat.min(15) as u8)];
if lit_tok == 15 {
let mut rest = lit - 15;
while rest >= 255 {
block.push(255);
rest -= 255;
}
block.push(rest as u8);
}
let seed: Vec<u8> = (0..lit).map(|i| (i as u8).wrapping_add(7)).collect();
block.extend_from_slice(&seed);
block.extend_from_slice(&(offset as u16).to_le_bytes());
if mat >= 15 {
let mut rest = mat - 15;
while rest >= 255 {
block.push(255);
rest -= 255;
}
block.push(rest as u8);
}
let tail: Vec<u8> = (0..12u8).map(|i| i ^ 0x5A).collect();
block.push((tail.len() as u8) << 4);
block.extend_from_slice(&tail);
let mut want = seed.clone();
for _ in 0..run {
want.push(want[want.len() - offset]);
}
want.extend_from_slice(&tail);
let n = want.len();
for &body in crate::kernel::decode::Lz4Body::all() {
let mut out = vec![0u8; n + crate::kernel::decode::UNPACK_SLACK];
if !crate::kernel::decode::unpack_lz4_into_slice_on(body, &block, &mut out, n) {
continue; }
if out[..n] != want[..] {
failed.push((body, offset, run));
}
}
}
}
assert!(
failed.is_empty(),
"an overlapping match decoded wrong: {failed:?}"
);
}
#[cfg(feature = "liblz4")]
#[test]
fn the_kernel_itself_reads_what_liblz4_wrote() {
if !crate::kernel::decode::asm_available() {
return;
}
#[link(name = "lz4")]
extern "C" {
fn LZ4_compress_default(src: *const u8, dst: *mut u8, n: i32, cap: i32) -> i32;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut cases: Vec<(String, Vec<u8>)> = Vec::new();
for size in [16usize, 64, 512, 1000, 4096, 65_536] {
cases.push((format!("records_{size}"), records(size)));
cases.push((format!("runs_{size}"), vec![b'a'; size]));
cases.push((
format!("noise_{size}"),
(0..size).map(|_| noise_byte()).collect(),
));
}
let mut refused = Vec::new();
for (label, data) in &cases {
let mut block = vec![0u8; data.len() + 1024];
let n = unsafe {
LZ4_compress_default(
data.as_ptr(),
block.as_mut_ptr(),
data.len() as i32,
block.len() as i32,
)
};
assert!(n > 0, "liblz4 refused {label}");
block.truncate(n as usize);
let bodies = crate::kernel::decode::Lz4Body::all();
let want = if cfg!(target_arch = "x86_64") {
if crate::cpu::features().avx2 {
4
} else {
2
}
} else if cfg!(target_arch = "aarch64") {
2
} else {
1
};
assert_eq!(
bodies.len(),
want,
"a body was added or removed without this test noticing"
);
for &body in bodies {
let mut out = vec![0u8; data.len() + crate::kernel::decode::UNPACK_SLACK];
let ok = crate::kernel::decode::unpack_lz4_into_slice_on(
body,
&block,
&mut out,
data.len(),
);
if !ok {
refused.push(format!("{label} on {body:?} ({} block bytes)", block.len()));
continue;
}
assert_eq!(
&out[..data.len()],
&data[..],
"the {body:?} LZ4 body decoded {label} to the wrong bytes"
);
}
}
assert!(
refused.is_empty(),
"the assembly decoder refused {} of {} liblz4 blocks: {}",
refused.len(),
cases.len(),
refused.join(", ")
);
}
#[cfg(feature = "liblz4")]
#[test]
fn an_lz4_store_migrates_one_value_at_a_time() {
#[link(name = "lz4")]
extern "C" {
fn LZ4_compress_default(src: *const u8, dst: *mut u8, n: i32, cap: i32) -> i32;
}
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [512usize, 1024, 4096, 65_536] {
cases.push(records(size));
}
let (mut was, mut now, mut migrated) = (0usize, 0usize, 0usize);
let mut value = Vec::new();
let mut repacked = Vec::new();
let mut check = Vec::new();
for original in &cases {
let mut legacy = vec![0u8; original.len() + 1024];
let n = unsafe {
LZ4_compress_default(
original.as_ptr(),
legacy.as_mut_ptr(),
original.len() as i32,
legacy.len() as i32,
)
};
assert!(n > 0, "liblz4 refused {} bytes", original.len());
legacy.truncate(n as usize);
unpack_into(&legacy, &mut value, original.len())
.unwrap_or_else(|e| panic!("legacy entry of {} bytes: {e}", original.len()));
assert_eq!(&value[..], &original[..], "the old value came back wrong");
assert!(
pack(&value, &mut repacked),
"{} bytes did not pack",
value.len()
);
unpack(&repacked, &mut check).expect("what we just wrote");
assert_eq!(
&check[..],
&original[..],
"the migrated value came back wrong"
);
was += legacy.len();
now += repacked.len();
migrated += 1;
}
eprintln!(
" migrated {migrated} values: {was} bytes of LZ4 -> {now} of ours, {:.1}% smaller",
100.0 * (1.0 - now as f64 / was as f64)
);
assert!(now < was, "the rewrite must not cost space: {was} -> {now}");
}
#[cfg(feature = "liblz4")]
#[test]
fn liblz4_refuses_what_we_wrote() {
#[link(name = "lz4")]
extern "C" {
fn LZ4_decompress_safe(src: *const u8, dst: *mut u8, n: i32, cap: i32) -> i32;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [16usize, 17, 63, 64, 65, 1000, 4096, 65_536] {
cases.push(records(size));
cases.push(vec![b'a'; size]);
cases.push((0..size).map(|_| noise_byte()).collect());
}
cases.push(b"ab".repeat(3000));
cases.push(b"abcdefg".repeat(900));
let mut packed = Vec::new();
let (mut even, mut wide, mut refused) = (0, 0, 0);
for data in &cases {
if !pack(data, &mut packed) {
continue;
}
let (_, hybrid, header) = get_header(&packed).expect("a header");
if hybrid {
wide += 1;
continue;
}
even += 1;
let body = &packed[header..];
let mut out = vec![0u8; data.len()];
let n = unsafe {
LZ4_decompress_safe(
body.as_ptr(),
out.as_mut_ptr(),
body.len() as i32,
out.len() as i32,
)
};
if n != data.len() as i32 {
refused += 1;
continue;
}
assert_eq!(
&out[..],
&data[..],
"liblz4 read {} bytes wrong",
data.len()
);
}
eprintln!(" even {even}, wide {wide}, refused by liblz4 {refused}");
assert!(
even > 0,
"no case chose the even split, so nothing was tested"
);
assert_eq!(
refused, even,
"liblz4 accepted one of our blocks -- see the note above"
);
}
#[test]
fn a_value_that_compresses_anywhere_is_not_written_off() {
let noise = |n: usize| {
let mut st = 0x2545_F491_4F6C_DD1Du64;
(0..n)
.map(|_| {
st ^= st << 13;
st ^= st >> 7;
st ^= st << 17;
st as u8
})
.collect::<Vec<u8>>()
};
let mut tail = noise(40 * 1024);
tail.resize(64 * 1024, 0);
let mut middle = noise(64 * 1024);
middle[1024..31_000].fill(0);
for (what, data) in [("tail", tail), ("middle", middle)] {
let mut out = Vec::new();
assert!(pack(&data, &mut out), "{what}: refused outright");
assert!(
out.len() * 3 < data.len() * 2,
"{what}: {} of {} bytes, so the compressible part was never searched",
out.len(),
data.len()
);
}
}
#[test]
fn a_random_head_does_not_write_off_the_body() {
let mut st = 0x2545_F491_4F6C_DD1Du64;
let mut input: Vec<u8> = (0..4096)
.map(|_| {
st ^= st << 13;
st ^= st >> 7;
st ^= st << 17;
st as u8
})
.collect();
while input.len() < 64 * 1024 {
input.extend_from_slice(b"the body of this value repeats itself, ");
}
let mut out = Vec::new();
assert!(pack(&input, &mut out), "refused a value that compresses");
assert!(
out.len() * 4 < input.len(),
"{} of {} bytes: the body was not searched",
out.len(),
input.len()
);
}
#[test]
fn the_kernel_accepts_every_stream_the_packer_writes() {
if !crate::kernel::decode::asm_available() {
return;
}
let mut packed = Vec::new();
let mut out = Vec::new();
let mut sizes: Vec<usize> = vec![256, 512, 1000, 1024, 4096, 16_384, 65_536];
sizes.extend([5usize, 17, 64, 100]);
for size in sizes {
for input in [records(size), vec![b'a'; size]] {
if !pack(&input, &mut packed) {
continue;
}
let f = frame(&packed).expect("the packer wrote a header");
let took = match f.switch {
None => crate::kernel::decode::unpack_asm(
f.body,
&mut out,
f.declared,
f.split.kernel(),
),
Some(switch) => crate::kernel::decode::unpack_asm_hybrid(
f.body,
&mut out,
f.declared,
switch,
f.split.kernel(),
f.split.other().kernel(),
),
};
assert!(
took,
"the kernel declined {} bytes ({})",
input.len(),
if f.switch.is_some() {
"two sections"
} else {
"one section"
}
);
assert_eq!(&out[..], &input[..], "and then lost bytes");
}
}
}
#[test]
fn the_assembly_decoder_agrees_with_the_portable_one() {
if !crate::kernel::decode::asm_available() {
return;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [
1usize, 2, 3, 4, 5, 7, 8, 15, 16, 17, 31, 32, 33, 47, 48, 49, 64, 1000, 4096, 8192,
65_536,
] {
cases.push(records(size));
cases.push(vec![b'a'; size]);
cases.push((0..size).map(|_| noise_byte()).collect());
}
cases.push(b"ab".repeat(3000));
cases.push(b"abc".repeat(2000));
cases.push(b"abcdefg".repeat(900));
cases.push([b"xy".repeat(500), vec![0u8; 4000], b"xy".repeat(500)].concat());
for period in [4usize, 5, 7, 8, 11, 12, 14, 16, 24, 31] {
let mut v = Vec::new();
let mut n = 0u8;
while v.len() < 4096 {
let chunk: Vec<u8> = (0..period)
.map(|_| {
n = n.wrapping_add(37);
n
})
.collect();
v.extend_from_slice(&chunk);
v.extend_from_slice(&chunk);
}
cases.push(v);
}
let mut packed = Vec::new();
let mut asm_out = Vec::new();
let mut ref_out = Vec::new();
for input in &cases {
if !pack(input, &mut packed) {
continue;
}
let f = frame(&packed).expect("the packer wrote a header");
let took = match f.switch {
None => crate::kernel::decode::unpack_asm(
f.body,
&mut asm_out,
f.declared,
f.split.kernel(),
),
Some(switch) => crate::kernel::decode::unpack_asm_hybrid(
f.body,
&mut asm_out,
f.declared,
switch,
f.split.kernel(),
f.split.other().kernel(),
),
};
assert!(
took,
"the kernel declined a stream the packer produced, {} bytes ({})",
input.len(),
if f.switch.is_some() {
"two sections"
} else {
"one section"
}
);
unpack_portable(&packed, &mut ref_out).expect("the portable decoder accepts it");
assert_eq!(
asm_out,
ref_out,
"decoders disagree on {} bytes",
input.len()
);
assert_eq!(
&asm_out[..],
&input[..],
"round trip lost {} bytes",
input.len()
);
}
}
#[test]
fn the_assembly_decoder_never_accepts_more_than_the_portable_one() {
if !crate::kernel::decode::asm_available() {
return;
}
let mut packed = Vec::new();
assert!(pack(&records(4096), &mut packed));
let mut broken: Vec<Vec<u8>> = Vec::new();
for cut in [0usize, 1, 2, 3, 5, 9, 17, 33, 64, 128] {
if cut < packed.len() {
broken.push(packed[..packed.len() - cut].to_vec());
}
}
for at in [0usize, 1, 2, 3, 4, 8, 16, 32, 64, 100] {
for xor in [0x01u8, 0x0F, 0xF0, 0xFF] {
if at < packed.len() {
let mut c = packed.clone();
c[at] ^= xor;
broken.push(c);
}
}
}
let mut asm_out = Vec::new();
let mut ref_out = Vec::new();
for case in &broken {
let Ok(f) = frame(case) else {
continue;
};
let took = match f.switch {
None => crate::kernel::decode::unpack_asm(
f.body,
&mut asm_out,
f.declared,
f.split.kernel(),
),
Some(switch) => crate::kernel::decode::unpack_asm_hybrid(
f.body,
&mut asm_out,
f.declared,
switch,
f.split.kernel(),
f.split.other().kernel(),
),
};
if !took {
continue; }
let reference = unpack_portable(case, &mut ref_out);
assert!(
reference.is_ok(),
"the kernel accepted a stream the portable decoder rejects"
);
assert_eq!(asm_out, ref_out, "decoders disagree on a corrupt stream");
}
}
#[test]
fn the_assembly_packer_agrees_byte_for_byte() {
if !crate::kernel::encode::asm_available() {
return;
}
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut noise_byte = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for size in [0usize, 1, 3, 4, 5, 7, 8, 15, 16, 17, 64, 1000, 4096, 65_536] {
cases.push(records(size));
cases.push(vec![b'a'; size]);
cases.push((0..size).map(|_| noise_byte()).collect());
}
cases.push([b'a', b'b'].repeat(2048));
let mut edge = b"prefix".to_vec();
edge.extend(std::iter::repeat(b'z').take(3000));
edge.extend_from_slice(b"suffix");
cases.push(edge);
for size in [1000usize, 4096, 65_536] {
let mut mixed = Vec::with_capacity(size);
let mut i = 0u64;
while mixed.len() < size {
mixed.extend_from_slice(
format!(
"{{\"k\":\"{:08x}\",\"role\":\"member\",\"n\":{}}}",
i.wrapping_mul(2654435761),
i % 97
)
.as_bytes(),
);
i += 1;
}
mixed.truncate(size);
cases.push(mixed);
}
let mut rust_out = Vec::new();
let mut asm_out = Vec::new();
let mut round_trip = Vec::new();
let production = crate::kernel::encode::kernel_is_production_packer();
#[cfg(target_arch = "x86_64")]
assert_eq!(
crate::kernel::encode::PartLine::all().len(),
3,
"x86-64 has three assembled bodies and the test must drive all of them"
);
for &line in crate::kernel::encode::PartLine::all() {
let mut rust_table = Box::new([EMPTY; HASH_SIZE]);
let mut asm_table = crate::kernel::encode::new_table();
for input in &cases {
let rust_kept = if production {
pack_with(input, &mut rust_out, &mut rust_table)
} else {
pack_with_eager(input, &mut rust_out, &mut rust_table)
};
let asm_kept =
crate::kernel::encode::pack_asm_on(line, input, &mut asm_out, &mut asm_table)
.is_some();
if rust_kept && !production {
let (_, hybrid, _) = get_header(&rust_out).expect("a header");
if hybrid {
rust_table.fill(EMPTY);
asm_table.fill(EMPTY);
continue;
}
}
assert_eq!(
rust_kept,
asm_kept,
"{line:?} disagreed on whether packing helped for {} bytes",
input.len()
);
if rust_kept {
assert_eq!(
rust_out,
asm_out,
"{line:?} produced a different encoding for the same {} byte input",
input.len()
);
unpack(&asm_out, &mut round_trip).expect("assembly output must unpack");
assert_eq!(&round_trip, input, "assembly output lost bytes");
}
}
}
}
#[test]
fn every_assembled_body_is_reached_and_agrees() {
if !crate::kernel::encode::asm_available()
|| !crate::kernel::encode::kernel_is_production_packer()
{
return;
}
let mut state = 0x9E37_79B9_7F4A_7C15u64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state
};
let mut cases: Vec<Vec<u8>> = Vec::new();
for &size in &[512usize, 2049, 4096, 8192, 8193, 20_000, 65_536] {
let mut runs = Vec::with_capacity(size);
while runs.len() < size {
let n = 20 + (next() % 200) as usize;
let b = (next() % 7) as u8 + b'a';
runs.extend(std::iter::repeat(b).take(n));
}
runs.truncate(size);
cases.push(runs);
let mut mixed = Vec::with_capacity(size);
let mut i = 0u64;
while mixed.len() < size {
mixed.extend_from_slice(
format!("{{\"id\":{},\"v\":\"{:x}\"}}", i % 32, next() & 0xFFFF).as_bytes(),
);
i += 1;
}
mixed.truncate(size);
cases.push(mixed);
let mut long_lit: Vec<u8> = (0..size.min(600)).map(|_| next() as u8).collect();
long_lit.extend_from_slice(&long_lit.clone());
cases.push(long_lit);
}
let mut seen_even = 0usize;
let mut seen_hybrid = 0usize;
let mut seen_narrow = 0usize;
let mut seen_wide_table = 0usize;
let mut rust_out = Vec::new();
let mut asm_out = Vec::new();
let mut rust_table = Box::new([EMPTY; HASH_SIZE]);
let mut asm_table = crate::kernel::encode::new_table();
let mut round_trip = Vec::new();
for input in &cases {
let rust_kept = pack_with(input, &mut rust_out, &mut rust_table);
let asm_kept =
crate::kernel::encode::pack_asm(input, &mut asm_out, &mut asm_table).is_some();
assert_eq!(
rust_kept,
asm_kept,
"disagreed on whether packing helped for {} bytes",
input.len()
);
if !rust_kept {
continue;
}
assert_eq!(
rust_out,
asm_out,
"different encodings for the same {} byte input",
input.len()
);
unpack(&asm_out, &mut round_trip).expect("assembly output must unpack");
assert_eq!(&round_trip, input, "assembly output lost bytes");
let (_, hybrid, _) = get_header(&asm_out).expect("a header");
if hybrid {
seen_hybrid += 1;
} else {
seen_even += 1;
}
if input.len() > NARROW_TABLE_ABOVE {
seen_narrow += 1;
} else {
seen_wide_table += 1;
}
}
assert!(seen_even > 0, "no case stayed in the even split");
assert!(
seen_hybrid > 0,
"no case changed split, so the wide bodies and the trailer went untested"
);
assert!(seen_wide_table > 0, "no case used the twelve-bit table");
assert!(seen_narrow > 0, "no case used the eleven-bit table");
}
#[test]
fn an_offset_before_the_start_is_refused() {
let mut stream = Vec::new();
put_header(8, false, &mut stream);
stream.push(1 << 4); stream.push(b'a');
stream.extend_from_slice(&99u16.to_le_bytes());
let mut out = Vec::new();
assert_eq!(unpack(&stream, &mut out), Err(PackError::BadOffset));
}
#[test]
fn decoding_into_a_slice_agrees_with_decoding_into_a_vec() {
let mut seen_hybrid = 0usize;
let mut seen_plain = 0usize;
let varied = |total: usize| -> Vec<u8> {
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state
};
let mut out = Vec::with_capacity(total);
while out.len() < total {
let r = next();
out.extend_from_slice(
format!(
"{{\"id\":\"{:016x}\",\"tenant\":\"{:08x}\",\"score\":{}}}",
r,
next() as u32,
next() % 100_000
)
.as_bytes(),
);
}
out.truncate(total);
out
};
for len in [8usize, 64, 517, 4096, 9000, 65_536].map(biggest) {
for (which, data) in [("records", records(len)), ("varied", varied(len))] {
let mut packed = Vec::new();
if !pack(&data, &mut packed) {
continue;
}
if get_header(&packed).unwrap().1 {
seen_hybrid += 1;
} else {
seen_plain += 1;
}
let mut want = Vec::new();
unpack(&packed, &mut want).expect("the vec path decodes");
assert_eq!(want, data, "{which}_{len}");
let mut roomy = vec![0u8; decompressed_bound(data.len())];
let n = unpack_into_slice(&packed, &mut roomy).expect("roomy");
assert_eq!(n, data.len(), "{which}_{len} roomy length");
assert_eq!(&roomy[..n], &data[..], "{which}_{len} roomy bytes");
let mut tight = vec![0u8; data.len()];
let n = unpack_into_slice(&packed, &mut tight).expect("tight");
assert_eq!(n, data.len(), "{which}_{len} tight length");
assert_eq!(tight, data, "{which}_{len} tight bytes");
if !data.is_empty() {
let mut short = vec![0xAAu8; data.len() - 1];
assert_eq!(
unpack_into_slice(&packed, &mut short),
Err(PackError::OutputTooSmall),
"{which}_{len} short"
);
assert!(short.iter().all(|&b| b == 0xAA), "short buffer was written");
}
}
}
assert!(seen_plain > 0, "no single-section case");
assert!(
seen_hybrid > 0,
"no hybrid case -- the two-kernel path is untested"
);
}
#[test]
fn the_published_vectors_hold() {
let text = include_str!("../docs/vectors.txt");
let mut fields: Vec<(String, String)> = Vec::new();
let mut checked = 0usize;
let mut skipped = 0usize;
fn unhex(text: &str) -> Vec<u8> {
text.split_whitespace()
.map(|b| u8::from_str_radix(b, 16).expect("not a hex byte"))
.collect()
}
fn finish(fields: &mut Vec<(String, String)>, checked: &mut usize, skipped: &mut usize) {
if fields.is_empty() {
return;
}
let get = |key: &str| -> Option<String> {
fields
.iter()
.find(|(k, _)| k == key)
.map(|(_, v)| v.clone())
};
let name = get("name").expect("a record with no name");
let stream = unhex(&get("stream").unwrap_or_else(|| panic!("{name}: no stream")));
let mut out = Vec::new();
let got = unpack(&stream, &mut out);
if let Some(want) = get("output") {
assert_eq!(got, Ok(()), "{name}: refused");
assert_eq!(out, unhex(&want), "{name}");
} else if let Some(spec) = get("output-repeat") {
let (unit, count) = spec
.split_once('*')
.unwrap_or_else(|| panic!("{name}: no '*'"));
let unit = unhex(unit);
let count: usize = count.trim().parse().expect("a count");
if cfg!(miri) && unit.len() * count > 4096 {
*skipped += 1;
fields.clear();
return;
}
assert_eq!(got, Ok(()), "{name}: refused");
assert_eq!(out.len(), unit.len() * count, "{name}: length");
assert!(
out.chunks_exact(unit.len()).all(|c| c == unit),
"{name}: not the repeated unit"
);
} else if let Some(want) = get("reject") {
let err = got.expect_err(&format!("{name}: accepted"));
assert_eq!(format!("{err:?}"), want, "{name}");
} else {
panic!("{name}: no output, output-repeat or reject");
}
*checked += 1;
fields.clear();
}
for line in text.lines() {
if line.starts_with('#') {
continue;
}
if line.trim().is_empty() {
finish(&mut fields, &mut checked, &mut skipped);
continue;
}
if line.starts_with(char::is_whitespace) {
let last = fields.last_mut().expect("a continuation with no field");
last.1.push(' ');
last.1.push_str(line.trim());
continue;
}
let (key, value) = line.split_once(':').expect("a line that is not a field");
fields.push((key.trim().to_owned(), value.trim().to_owned()));
}
finish(&mut fields, &mut checked, &mut skipped);
assert_eq!(
checked + skipped,
16,
"wrong number of vectors seen ({checked} checked, {skipped} skipped)"
);
if cfg!(miri) {
assert_eq!(skipped, 2, "the set of oversized vectors changed");
} else {
assert_eq!(skipped, 0, "a vector was skipped in a native run");
}
}
#[test]
fn a_header_wider_than_its_length_needs_is_refused() {
for declared in [0usize, 1, 63, 64, 8191, 8192, 2_097_151, 2_097_152] {
let mut literals = Vec::new();
let mut body = Vec::new();
let n = declared.min(8);
body.push((n as u8) << 4);
for i in 0..n {
literals.push(b'a' + (i % 26) as u8);
}
body.extend_from_slice(&literals);
let shortest = header_len(declared);
#[allow(clippy::needless_range_loop)]
for class in 0..4usize {
let mut stream = Vec::new();
let payload = declared as u32;
let top = (payload >> (8 * class)) as u8;
if class == 0 && declared > 63 {
continue; }
if class > 0 && top & !HEADER_MASK[class] != 0 {
continue; }
stream.push(((class as u8) << 6) | top);
for i in (0..class).rev() {
stream.push((payload >> (8 * i)) as u8);
}
stream.extend_from_slice(&body);
let mut out = Vec::new();
let got = unpack(&stream, &mut out);
if class + 1 == shortest {
assert_ne!(
got,
Err(PackError::NonCanonicalHeader),
"declared {declared} refused in its own class"
);
if declared <= 8 {
assert_eq!(got, Ok(()), "declared {declared}");
assert_eq!(out, literals, "declared {declared}");
}
} else {
assert_eq!(
got,
Err(PackError::NonCanonicalHeader),
"declared {declared} accepted in class {class}"
);
}
}
}
}
#[test]
fn a_length_the_encoder_would_never_emit_still_decodes() {
for declared in 0usize..=63 {
let mut stream = Vec::new();
put_header(declared, false, &mut stream);
let lit_max = EVEN.lit_max();
if declared < lit_max {
stream.push((declared as u8) << 4);
} else {
stream.push((lit_max as u8) << 4);
let mut rest = declared - lit_max;
while rest >= 255 {
stream.push(255);
rest -= 255;
}
stream.push(rest as u8);
}
let literals: Vec<u8> = (0..declared).map(|i| b'a' + (i % 26) as u8).collect();
stream.extend_from_slice(&literals);
let mut out = Vec::new();
assert_eq!(
unpack(&stream, &mut out),
Ok(()),
"declared {declared} was refused"
);
assert_eq!(out, literals, "declared {declared}");
}
}
}