use crate::core::errors::{PvError, Result};
pub fn write_uvarint(out: &mut Vec<u8>, mut value: u64) {
loop {
let mut byte = (value & 0x7F) as u8;
value >>= 7;
if value != 0 {
byte |= 0x80;
}
out.push(byte);
if value == 0 {
break;
}
}
}
pub fn read_uvarint(buf: &[u8], pos: &mut usize) -> Result<u64> {
let start = *pos;
let mut result: u64 = 0;
for index in 0..10usize {
let byte = *buf
.get(*pos)
.ok_or_else(|| PvError::Corruption("truncated varint".into()))?;
*pos += 1;
let payload = u64::from(byte & 0x7f);
if index == 9 && payload > 1 {
return Err(PvError::Corruption("varint overflow".into()));
}
result |= payload << (index * 7);
if byte & 0x80 == 0 {
if *pos - start > 1 && payload == 0 {
return Err(PvError::Corruption("non-canonical varint".into()));
}
return Ok(result);
}
}
Err(PvError::Corruption("unterminated varint".into()))
}
#[inline]
pub fn zigzag_encode(v: i64) -> u64 {
((v << 1) ^ (v >> 63)) as u64
}
#[inline]
pub fn zigzag_decode(v: u64) -> i64 {
((v >> 1) as i64) ^ -((v & 1) as i64)
}
pub fn delta_z_encode(values: &[i64]) -> Vec<u8> {
let mut out = Vec::with_capacity(values.len() + 9);
write_uvarint(&mut out, values.len() as u64);
if let Some(&base) = values.first() {
out.extend_from_slice(&base.to_le_bytes());
let mut prev = base;
for &v in &values[1..] {
write_uvarint(&mut out, zigzag_encode(v.wrapping_sub(prev)));
prev = v;
}
}
out
}
pub fn delta_z_decode(buf: &[u8]) -> Result<Vec<i64>> {
let mut pos = 0usize;
let count = usize::try_from(read_uvarint(buf, &mut pos)?)
.map_err(|_| PvError::Corruption("delta-z: row count exceeds this platform".into()))?;
let mut out = Vec::with_capacity(count.min(buf.len()));
if count == 0 {
if pos != buf.len() {
return Err(PvError::Corruption("delta-z: trailing bytes".into()));
}
return Ok(out);
}
let base_bytes = buf
.get(pos..pos + 8)
.ok_or_else(|| PvError::Corruption("delta-z: missing base".into()))?;
let mut prev = i64::from_le_bytes(base_bytes.try_into().unwrap());
pos += 8;
out.push(prev);
for _ in 1..count {
let delta = zigzag_decode(read_uvarint(buf, &mut pos)?);
prev = prev.wrapping_add(delta);
out.push(prev);
}
if pos != buf.len() {
return Err(PvError::Corruption("delta-z: trailing bytes".into()));
}
Ok(out)
}
pub fn bits_for_cardinality(cardinality: usize) -> u8 {
if cardinality <= 1 {
return 1;
}
let bits = (usize::BITS - (cardinality - 1).leading_zeros()) as u8;
bits.clamp(1, 8)
}
pub fn pack_codes(codes: &[u8], bits: u8) -> Vec<u8> {
debug_assert!((1..=8).contains(&bits));
let mut out = Vec::with_capacity((codes.len() * bits as usize).div_ceil(8));
let mut acc: u16 = 0;
let mut filled: u8 = 0;
for &code in codes {
acc |= u16::from(code) << filled;
filled += bits;
while filled >= 8 {
out.push((acc & 0xFF) as u8);
acc >>= 8;
filled -= 8;
}
}
if filled > 0 {
out.push((acc & 0xFF) as u8);
}
out
}
pub fn unpack_codes(packed: &[u8], bits: u8, count: usize) -> Result<Vec<u8>> {
if !(1..=8).contains(&bits) {
return Err(PvError::Corruption(format!(
"bit-pack: invalid bit width {bits} (must be 1..=8)"
)));
}
let total_bits = count
.checked_mul(bits as usize)
.ok_or_else(|| PvError::Corruption("bit-pack: encoded size overflow".into()))?;
let expected_bytes = total_bits.div_ceil(8);
if packed.len() != expected_bytes {
return Err(PvError::Corruption(format!(
"bit-pack: expected {expected_bytes} byte(s), found {}",
packed.len()
)));
}
if let (Some(last), used @ 1..=7) = (packed.last(), total_bits % 8) {
let unused_mask = !((1u8 << used) - 1);
if last & unused_mask != 0 {
return Err(PvError::Corruption("bit-pack: nonzero padding bits".into()));
}
}
let mut out = Vec::with_capacity(count);
let mask = ((1u16 << bits) - 1) as u8;
let mut acc: u16 = 0;
let mut filled: u8 = 0;
let mut byte_iter = packed.iter();
for _ in 0..count {
while filled < bits {
let byte = *byte_iter
.next()
.ok_or_else(|| PvError::Corruption("bit-pack: truncated stream".into()))?;
acc |= u16::from(byte) << filled;
filled += 8;
}
out.push((acc & u16::from(mask)) as u8);
acc >>= bits;
filled -= bits;
}
Ok(out)
}
pub const MAX_DICTIONARY_SYMBOLS: usize = 256;
#[derive(Debug, Clone, PartialEq)]
pub struct DictionaryColumn {
pub symbols: Vec<String>,
pub bits: u8,
pub count: usize,
pub codes: Vec<u8>,
}
impl DictionaryColumn {
pub fn build(values: &[String]) -> Option<Self> {
let mut symbols: Vec<String> = Vec::new();
let mut codes: Vec<u8> = Vec::with_capacity(values.len());
for v in values {
let code = match symbols.iter().position(|s| s == v) {
Some(i) => i,
None => {
if symbols.len() >= MAX_DICTIONARY_SYMBOLS {
return None;
}
symbols.push(v.clone());
symbols.len() - 1
}
};
codes.push(code as u8);
}
let bits = bits_for_cardinality(symbols.len());
Some(Self {
bits,
count: values.len(),
codes: pack_codes(&codes, bits),
symbols,
})
}
pub fn decode(&self) -> Result<Vec<String>> {
let codes = unpack_codes(&self.codes, self.bits, self.count)?;
codes
.into_iter()
.map(|c| {
self.symbols
.get(c as usize)
.cloned()
.ok_or_else(|| PvError::Corruption("dictionary: code out of range".into()))
})
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn uvarint_round_trips() {
for v in [0u64, 1, 127, 128, 300, 16_384, u64::MAX] {
let mut buf = Vec::new();
write_uvarint(&mut buf, v);
let mut pos = 0;
assert_eq!(read_uvarint(&buf, &mut pos).unwrap(), v);
assert_eq!(pos, buf.len());
}
assert_eq!(
{
let mut b = Vec::new();
write_uvarint(&mut b, 127);
b.len()
},
1
);
let mut pos = 0;
assert!(read_uvarint(&[0x80, 0], &mut pos).is_err());
let mut pos = 0;
assert!(read_uvarint(&[0xff; 10], &mut pos).is_err());
let mut overflow = [0xff; 10];
overflow[9] = 2;
let mut pos = 0;
assert!(read_uvarint(&overflow, &mut pos).is_err());
}
#[test]
fn zigzag_round_trips() {
for v in [0i64, -1, 1, -64, 63, i64::MIN, i64::MAX] {
assert_eq!(zigzag_decode(zigzag_encode(v)), v);
}
assert!(zigzag_encode(-1) < 4);
}
#[test]
fn delta_z_round_trips_and_compresses_monotonic() {
let timestamps: Vec<i64> = (1_700_000_000..1_700_000_050).collect();
let encoded = delta_z_encode(×tamps);
assert_eq!(delta_z_decode(&encoded).unwrap(), timestamps);
assert!(encoded.len() < 70, "got {} bytes", encoded.len());
}
#[test]
fn delta_z_handles_empty_and_single() {
assert_eq!(
delta_z_decode(&delta_z_encode(&[])).unwrap(),
Vec::<i64>::new()
);
assert_eq!(delta_z_decode(&delta_z_encode(&[42])).unwrap(), vec![42]);
let mut trailing = delta_z_encode(&[42]);
trailing.push(0);
assert!(delta_z_decode(&trailing).is_err());
}
#[test]
fn bits_for_cardinality_matches_spec_example() {
assert_eq!(bits_for_cardinality(3), 2);
assert_eq!(bits_for_cardinality(1), 1);
assert_eq!(bits_for_cardinality(2), 1);
assert_eq!(bits_for_cardinality(4), 2);
assert_eq!(bits_for_cardinality(5), 3);
assert_eq!(bits_for_cardinality(256), 8);
}
#[test]
fn bit_pack_round_trips() {
let codes = [0u8, 1, 2, 0, 1, 2, 2, 1, 0];
let packed = pack_codes(&codes, 2);
assert_eq!(packed.len(), 3);
assert_eq!(unpack_codes(&packed, 2, codes.len()).unwrap(), codes);
let mut trailing = packed.clone();
trailing.push(0);
assert!(unpack_codes(&trailing, 2, codes.len()).is_err());
let mut nonzero_padding = packed;
*nonzero_padding.last_mut().unwrap() |= 0b1100_0000;
assert!(unpack_codes(&nonzero_padding, 2, codes.len()).is_err());
}
#[test]
fn dictionary_packs_low_cardinality() {
let values: Vec<String> = (0..1000)
.map(|i| {
match i % 3 {
0 => "Pending",
1 => "Active",
_ => "Archived",
}
.to_string()
})
.collect();
let dict = DictionaryColumn::build(&values).unwrap();
assert_eq!(dict.symbols.len(), 3);
assert_eq!(dict.bits, 2);
assert_eq!(dict.codes.len(), 250);
assert_eq!(dict.decode().unwrap(), values);
}
#[test]
fn dictionary_bails_on_high_cardinality() {
let values: Vec<String> = (0..300).map(|i| format!("sym{i}")).collect();
assert!(DictionaryColumn::build(&values).is_none());
}
}