#[repr(C)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct PackState {
pub at: u32,
pub candidate: u32,
pub len: u32,
pub misses: u32,
}
pub const MIN_MATCH: usize = 4;
pub const MAX_OFFSET: usize = 65_535;
pub const HASH_BITS: u32 = 12;
pub const HASH_BITS_LARGE: u32 = 11;
pub const NARROW_TABLE_ABOVE: usize = 8192;
pub const SKIP_TRIGGER: u32 = 6;
pub const TABLE_SIZE: usize = 1 << HASH_BITS;
pub const EMPTY: u32 = 0x8000_0000;
pub fn new_table() -> Vec<u32> {
vec![EMPTY; TABLE_SIZE]
}
#[cfg(all(lzvolt_asm, target_arch = "aarch64"))]
extern "C" {
fn keva_pack_find(input: *const u8, len: usize, table: *mut u32, state: *mut PackState);
}
#[cfg(all(lzvolt_asm, any(target_arch = "aarch64", target_arch = "x86_64")))]
extern "C" {
fn keva_pack(
src: *const u8,
src_len: usize,
dst: *mut u8,
dst_cap: usize,
table: *mut u32,
) -> u32;
}
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
extern "C" {
fn keva_pack_xeon(
src: *const u8,
src_len: usize,
dst: *mut u8,
dst_cap: usize,
table: *mut u32,
) -> u32;
fn keva_pack_amd(
src: *const u8,
src_len: usize,
dst: *mut u8,
dst_cap: usize,
table: *mut u32,
) -> u32;
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum PartLine {
Baseline,
Xeon,
Amd,
}
impl PartLine {
pub fn all() -> &'static [PartLine] {
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
{
&[PartLine::Baseline, PartLine::Xeon, PartLine::Amd]
}
#[cfg(not(all(lzvolt_asm, target_arch = "x86_64")))]
{
&[PartLine::Baseline]
}
}
}
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
#[inline]
fn detect_line() -> PartLine {
let f = crate::cpu::features();
if f.xeon {
PartLine::Xeon
} else if f.amd {
PartLine::Amd
} else {
PartLine::Baseline
}
}
#[cfg(all(lzvolt_asm, any(target_arch = "aarch64", target_arch = "x86_64")))]
#[inline]
unsafe fn run(
line: PartLine,
src: *const u8,
src_len: usize,
dst: *mut u8,
dst_cap: usize,
table: *mut u32,
) -> u32 {
#[cfg(target_arch = "x86_64")]
#[allow(clippy::needless_return)]
{
return match line {
PartLine::Xeon => keva_pack_xeon(src, src_len, dst, dst_cap, table),
PartLine::Amd => keva_pack_amd(src, src_len, dst, dst_cap, table),
PartLine::Baseline => keva_pack(src, src_len, dst, dst_cap, table),
};
}
#[cfg(not(target_arch = "x86_64"))]
{
let _ = line;
keva_pack(src, src_len, dst, dst_cap, table)
}
}
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
fn room(n: usize) -> usize {
n + n / MIN_MATCH * 3 + n / 128 + 16 + 64 + 10
}
pub fn pack_asm(input: &[u8], out: &mut Vec<u8>, table: &mut [u32]) -> Option<usize> {
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
#[allow(clippy::needless_return)]
{
return pack_asm_on(detect_line(), input, out, table);
}
#[cfg(not(all(lzvolt_asm, target_arch = "x86_64")))]
#[allow(clippy::needless_return)]
{
pack_asm_on(PartLine::Baseline, input, out, table)
}
}
pub fn pack_asm_on(
line: PartLine,
input: &[u8],
out: &mut Vec<u8>,
table: &mut [u32],
) -> Option<usize> {
debug_assert!(table.len() >= TABLE_SIZE);
let _ = line;
#[cfg(not(all(lzvolt_asm, any(target_arch = "aarch64", target_arch = "x86_64"))))]
#[allow(clippy::needless_return)]
{
let _ = (input, out, table);
return None;
}
#[cfg(all(lzvolt_asm, target_arch = "x86_64"))]
#[allow(clippy::needless_return)]
{
out.clear();
let want = room(input.len());
if out.capacity() < want {
out.reserve(want);
}
let cap = out.capacity();
let written = unsafe {
run(
line,
input.as_ptr(),
input.len(),
out.as_mut_ptr(),
cap,
table.as_mut_ptr(),
)
} as usize;
if written == 0 {
return None;
}
assert!(
written <= cap,
"the kernel reported writing past the buffer"
);
unsafe { out.set_len(written) };
return Some(written);
}
#[cfg(all(lzvolt_asm, target_arch = "aarch64"))]
{
out.clear();
out.resize(input.len() + 16, 0);
let cap = out.len();
let written = unsafe {
run(
line,
input.as_ptr(),
input.len(),
out.as_mut_ptr(),
cap,
table.as_mut_ptr(),
)
} as usize;
if written == 0 {
out.clear();
return None;
}
assert!(
written <= cap,
"the kernel reported writing past the buffer"
);
unsafe { out.set_len(written) };
Some(written)
}
}
pub const fn asm_available() -> bool {
cfg!(all(
lzvolt_asm,
any(target_arch = "aarch64", target_arch = "x86_64")
))
}
pub const fn kernel_is_production_packer() -> bool {
cfg!(all(lzvolt_asm, target_arch = "x86_64"))
}
pub fn find(input: &[u8], table: &mut [u32], state: &mut PackState) {
debug_assert!(table.len() >= TABLE_SIZE);
#[cfg(all(lzvolt_asm, target_arch = "aarch64"))]
unsafe {
keva_pack_find(input.as_ptr(), input.len(), table.as_mut_ptr(), state);
}
#[cfg(not(all(lzvolt_asm, target_arch = "aarch64")))]
find_scalar(input, table, state);
}
pub fn find_scalar(input: &[u8], table: &mut [u32], state: &mut PackState) {
let mut at = state.at as usize;
let mut misses = state.misses;
while at + MIN_MATCH <= input.len() {
let word = u32::from_le_bytes(input[at..at + 4].try_into().unwrap());
let slot = (word.wrapping_mul(0x9E37_79B1) >> (32 - HASH_BITS)) as usize;
let stored = table[slot];
table[slot] = at as u32 + 1;
if stored != 0 {
let candidate = stored as usize - 1;
if candidate < at
&& at - candidate <= MAX_OFFSET
&& u32::from_le_bytes(input[candidate..candidate + 4].try_into().unwrap()) == word
{
let mut matched = MIN_MATCH;
let mut a = candidate + MIN_MATCH;
let mut b = at + MIN_MATCH;
while b + 8 <= input.len() {
let left = u64::from_le_bytes(input[a..a + 8].try_into().unwrap());
let right = u64::from_le_bytes(input[b..b + 8].try_into().unwrap());
let diff = left ^ right;
if diff != 0 {
matched += (diff.trailing_zeros() / 8) as usize;
state.at = at as u32;
state.candidate = candidate as u32;
state.len = matched as u32;
state.misses = 1 << SKIP_TRIGGER;
return;
}
a += 8;
b += 8;
matched += 8;
}
while b < input.len() && input[a] == input[b] {
a += 1;
b += 1;
matched += 1;
}
state.at = at as u32;
state.candidate = candidate as u32;
state.len = matched as u32;
state.misses = 1 << SKIP_TRIGGER;
return;
}
}
at += (misses >> SKIP_TRIGGER) as usize;
misses += 1;
}
state.at = at as u32;
state.len = 0;
state.misses = misses;
}
#[cfg(test)]
mod tests {
use super::*;
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 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 {
out.extend_from_slice(format!("{{\"k\":\"{:016x}\"}}", next()).as_bytes());
}
out.truncate(total);
out
}
fn noise(total: usize) -> Vec<u8> {
let mut state = 0x9E37_79B9_7F4A_7C15u64;
(0..total)
.map(|_| {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state as u8
})
.collect()
}
fn agree(input: &[u8]) {
let mut asm_table = vec![0u32; TABLE_SIZE];
let mut ref_table = vec![0u32; TABLE_SIZE];
let mut asm_state = PackState {
misses: 1 << SKIP_TRIGGER,
..Default::default()
};
let mut ref_state = asm_state;
let mut steps = 0usize;
loop {
find(input, &mut asm_table, &mut asm_state);
find_scalar(input, &mut ref_table, &mut ref_state);
assert_eq!(
asm_state,
ref_state,
"step {steps} disagreed on a {}-byte input",
input.len()
);
if asm_state.len == 0 {
break;
}
let next = asm_state.at + asm_state.len;
asm_state.at = next;
ref_state.at = next;
steps += 1;
assert!(steps < input.len() + 8, "search failed to terminate");
}
}
#[test]
fn agrees_with_the_reference_on_real_shapes() {
for size in [0usize, 1, 3, 4, 5, 7, 8, 16, 64, 1000, 4096, 65_536] {
agree(&records(size));
agree(&varied(size));
agree(&noise(size));
}
}
#[test]
fn agrees_on_degenerate_input() {
agree(&vec![b'a'; 4096]);
agree(&vec![0u8; 4096]);
agree(&[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");
agree(&edge);
}
#[test]
fn the_duplicated_constants_still_hold() {
assert_eq!(TABLE_SIZE, 4096);
assert_eq!(32 - HASH_BITS, 20, "the small-value shift in the .S file");
assert_eq!(
32 - HASH_BITS_LARGE,
21,
"the large-value shift in the .S file"
);
assert_eq!(NARROW_TABLE_ABOVE, 8192, "the threshold in the .S file");
assert_eq!(EMPTY, 0x8000_0000, "the sentinel the .S file relies on");
assert_eq!(MIN_MATCH, 4);
assert_eq!(MAX_OFFSET, 65_535);
assert_eq!(1u32 << SKIP_TRIGGER, 64, "the reset value in the .S file");
assert_eq!(std::mem::size_of::<PackState>(), 16);
}
}