pub fn decode_u32(src: &[u8], count: usize) -> Option<Vec<i32>> {
if count == 0 {
return Some(Vec::new());
}
let common = i32::from_le_bytes(src.get(0..4)?.try_into().ok()?);
let codes_len = count.div_ceil(4);
let codes = src.get(4..4 + codes_len)?;
let mut at = 4 + codes_len;
let mut out = Vec::with_capacity(count);
let mut previous = 0i32;
for i in 0..count {
let code = (codes[i / 4] >> ((i % 4) * 2)) & 0b11;
let delta = match code {
0 => common,
1 => {
let v = *src.get(at)? as i8 as i32;
at += 1;
v
}
2 => {
let v = i16::from_le_bytes(src.get(at..at + 2)?.try_into().ok()?) as i32;
at += 2;
v
}
_ => {
let v = i32::from_le_bytes(src.get(at..at + 4)?.try_into().ok()?);
at += 4;
v
}
};
previous = previous.wrapping_add(delta);
out.push(previous);
}
Some(out)
}
pub fn decode_u64(src: &[u8], count: usize) -> Option<Vec<i64>> {
if count == 0 {
return Some(Vec::new());
}
let common = i64::from_le_bytes(src.get(0..8)?.try_into().ok()?);
let codes_len = count.div_ceil(4);
let codes = src.get(8..8 + codes_len)?;
let mut at = 8 + codes_len;
let mut out = Vec::with_capacity(count);
let mut previous = 0i64;
for i in 0..count {
let code = (codes[i / 4] >> ((i % 4) * 2)) & 0b11;
let delta = match code {
0 => common,
1 => {
let v = *src.get(at)? as i8 as i64;
at += 1;
v
}
2 => {
let v = i16::from_le_bytes(src.get(at..at + 2)?.try_into().ok()?) as i64;
at += 2;
v
}
_ => {
let v = i32::from_le_bytes(src.get(at..at + 4)?.try_into().ok()?) as i64;
at += 4;
v
}
};
previous = previous.wrapping_add(delta);
out.push(previous);
}
Some(out)
}
pub fn read_u32_array(file: &[u8], at: &mut usize, count: usize) -> Option<Vec<i32>> {
let size = u64::from_le_bytes(file.get(*at..*at + 8)?.try_into().ok()?) as usize;
*at += 8;
let body = file.get(*at..*at + size)?;
*at += size;
let ceiling = count
.checked_mul(4)?
.checked_add(count.div_ceil(4))?
.checked_add(8)?;
let packed = super::lz4::decompress_upto(body, ceiling)?;
decode_u32(&packed, count)
}
pub fn encode_u32(values: &[i32]) -> Vec<u8> {
if values.is_empty() {
return Vec::new();
}
let mut deltas = Vec::with_capacity(values.len());
let mut previous = 0i32;
for v in values {
deltas.push(v.wrapping_sub(previous));
previous = *v;
}
let common = most_common(&deltas);
let mut out = common.to_le_bytes().to_vec();
let codes_at = out.len();
out.resize(codes_at + values.len().div_ceil(4), 0);
for (i, delta) in deltas.iter().enumerate() {
let code = if *delta == common {
0u8
} else if i8::try_from(*delta).is_ok() {
out.push(*delta as i8 as u8);
1
} else if let Ok(narrow) = i16::try_from(*delta) {
out.extend_from_slice(&narrow.to_le_bytes());
2
} else {
out.extend_from_slice(&delta.to_le_bytes());
3
};
out[codes_at + i / 4] |= code << ((i % 4) * 2);
}
out
}
pub fn encode_u64(values: &[i64]) -> Vec<u8> {
if values.is_empty() {
return Vec::new();
}
let mut deltas = Vec::with_capacity(values.len());
let mut previous = 0i64;
for v in values {
deltas.push(v.wrapping_sub(previous));
previous = *v;
}
let common = most_common(&deltas);
let mut out = common.to_le_bytes().to_vec();
let codes_at = out.len();
out.resize(codes_at + values.len().div_ceil(4), 0);
for (i, delta) in deltas.iter().enumerate() {
let code = if *delta == common {
0u8
} else if i8::try_from(*delta).is_ok() {
out.push(*delta as i8 as u8);
1
} else if let Ok(narrow) = i16::try_from(*delta) {
out.extend_from_slice(&narrow.to_le_bytes());
2
} else {
out.extend_from_slice(&(*delta as i32).to_le_bytes());
3
};
out[codes_at + i / 4] |= code << ((i % 4) * 2);
}
out
}
pub fn encodable_u64(values: &[i64]) -> bool {
let mut previous = 0i64;
for v in values {
let delta = v.wrapping_sub(previous);
if i32::try_from(delta).is_err() {
return false;
}
previous = *v;
}
true
}
fn most_common<T: Copy + Eq + std::hash::Hash + Default>(deltas: &[T]) -> T {
let mut counts: std::collections::HashMap<T, usize> = std::collections::HashMap::new();
for d in deltas {
*counts.entry(*d).or_insert(0) += 1;
}
counts
.into_iter()
.max_by_key(|(_, n)| *n)
.map(|(v, _)| v)
.unwrap_or_default()
}
pub fn write_u32_array(out: &mut Vec<u8>, values: &[i32]) {
let body = super::lz4::compress(&encode_u32(values));
out.extend_from_slice(&(body.len() as u64).to_le_bytes());
out.extend_from_slice(&body);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn decodes_the_field_names_of_a_real_crate() {
let file = include_bytes!("testdata/triangle.usdc");
let u64at = |at: usize| u64::from_le_bytes(file[at..at + 8].try_into().unwrap()) as usize;
let info = super::super::usdc::info(file).unwrap();
let section = |name: &str| {
info.sections
.iter()
.find(|(n, _, _)| n == name)
.map(|(_, at, _)| *at as usize)
.unwrap_or_else(|| panic!("no {name} section"))
};
let tokens_at = section("TOKENS");
let token_count = u64at(tokens_at);
let text = super::super::lz4::decompress(
&file[tokens_at + 24..tokens_at + 24 + u64at(tokens_at + 16)],
u64at(tokens_at + 8),
)
.unwrap();
let tokens: Vec<String> = text
.split(|b| *b == 0)
.take(token_count)
.map(|s| String::from_utf8_lossy(s).into_owned())
.collect();
let fields_at = section("FIELDS");
let count = u64at(fields_at);
let mut at = fields_at + 8;
let indices = read_u32_array(file, &mut at, count).expect("field names decode");
assert_eq!(indices.len(), count);
let names: Vec<&str> = indices
.iter()
.map(|i| {
tokens
.get(*i as usize)
.map(String::as_str)
.unwrap_or("<oob>")
})
.collect();
assert!(
!names.contains(&"<oob>"),
"an index pointed outside the token table: {names:?}"
);
for expected in [
"defaultPrim",
"metersPerUnit",
"upAxis",
"specifier",
"typeName",
"properties",
"variability",
"default",
] {
assert!(names.contains(&expected), "missing {expected} in {names:?}");
}
}
#[test]
fn what_is_packed_unpacks() {
let cases: Vec<Vec<i32>> = vec![
vec![],
vec![0],
vec![7],
(0..100).collect(),
vec![0, 1, 2, 3, 4, 5],
vec![5, 5, 5, 5, 5],
vec![0, 1000, -1000, 70000, -70000, 0],
vec![i32::MIN, i32::MAX, 0, i32::MAX],
(0..50).map(|i| i * i).collect(),
];
for case in cases {
let packed = encode_u32(&case);
assert_eq!(
decode_u32(&packed, case.len()).as_deref(),
Some(&case[..]),
"round trip of {case:?}"
);
}
}
#[test]
fn wide_values_round_trip_when_their_steps_are_narrow() {
let case: Vec<i64> = vec![2_000_000_000, 2_000_000_001, 2_000_000_002, 1_999_999_999];
assert!(encodable_u64(&case));
let packed = encode_u64(&case);
assert_eq!(decode_u64(&packed, case.len()).as_deref(), Some(&case[..]));
}
#[test]
fn a_step_too_wide_is_refused_rather_than_truncated() {
assert!(!encodable_u64(&[0, 1 << 40]));
assert!(
!encodable_u64(&[1 << 40, (1 << 40) + 1]),
"the first step counts"
);
assert!(encodable_u64(&[0, 1, 2]));
}
#[test]
fn a_consecutive_run_packs_to_two_bits_each() {
let packed = encode_u32(&(0..1000).collect::<Vec<_>>());
assert_eq!(packed.len(), 4 + 250 + 1);
}
#[test]
fn a_run_of_consecutive_values_costs_two_bits_each() {
let mut packed = 1i32.to_le_bytes().to_vec();
packed.push(0b0000_0000);
assert_eq!(decode_u32(&packed, 4).unwrap(), vec![1, 2, 3, 4]);
}
#[test]
fn mixed_widths_are_read_in_order() {
let mut packed = 10i32.to_le_bytes().to_vec();
packed.push(0b00_11_10_01);
packed.push(5u8); packed.extend_from_slice(&(-3i16).to_le_bytes()); packed.extend_from_slice(&1000i32.to_le_bytes()); assert_eq!(decode_u32(&packed, 4).unwrap(), vec![5, 2, 1002, 1012]);
}
#[test]
fn a_truncated_buffer_is_none() {
let packed = 1i32.to_le_bytes().to_vec();
assert!(decode_u32(&packed, 4).is_none());
assert!(decode_u32(&[], 1).is_none());
assert_eq!(decode_u32(&[], 0).unwrap(), Vec::<i32>::new());
}
}