use core::ptr;
use crate::decode_vec::DecodeVec;
use crate::error::{DecodeError, ErrorKind};
use crate::wire::read_varint_full;
const KERNEL_MIN_SPAN: usize = 256;
mod swar {
pub const MSB: u64 = 0x8080_8080_8080_8080;
pub const LOW7: u64 = 0x7F7F_7F7F_7F7F_7F7F;
#[inline]
pub const fn low_byte_mask(n: usize) -> u64 {
if n >= 8 {
u64::MAX
} else {
(1u64 << (8 * n)) - 1
}
}
#[inline]
pub unsafe fn load64(p: *const u8) -> u64 {
let w = unsafe { core::ptr::read_unaligned(p.cast::<u64>()) };
if cfg!(target_endian = "little") {
w
} else {
w.swap_bytes()
}
}
#[inline]
pub fn compact7(x: u64) -> u64 {
let x = ((x & 0x7F00_7F00_7F00_7F00) >> 1) | (x & 0x007F_007F_007F_007F);
let x = ((x & 0x3FFF_0000_3FFF_0000) >> 2) | (x & 0x0000_3FFF_0000_3FFF);
((x & 0x0FFF_FFFF_0000_0000) >> 4) | (x & 0x0000_0000_0FFF_FFFF)
}
#[inline]
pub fn bytemask8(w: u64) -> u64 {
((w & MSB).wrapping_mul(0x0002_0408_1020_4081)) >> 56
}
#[inline]
pub unsafe fn stopmask64(p: *const u8) -> u64 {
let mut m = 0u64;
for j in 0..8usize {
let w = unsafe { load64(p.add(8 * j)) };
m |= bytemask8(!w) << (8 * j);
}
m
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Kernel {
ByteLoop, Swar, Struct, Bulk1, Bulk2, Fixed, }
unsafe fn classify(p: *const u8, span: usize) -> (Kernel, usize) {
if span < KERNEL_MIN_SPAN {
return (Kernel::ByteLoop, 0);
}
let stop = unsafe { swar::stopmask64(p) };
if stop == 0 {
return (Kernel::ByteLoop, 0);
}
let mut m = stop;
let mut last: i32 = -1;
let mut g0: i32 = -1;
let mut maxw = 0i32;
let mut homo = true;
while m != 0 {
let b = m.trailing_zeros() as i32;
m &= m - 1;
let w = b - last;
last = b;
if w > maxw {
maxw = w;
}
if g0 < 0 {
g0 = w;
} else if w != g0 {
homo = false;
}
}
if !homo {
return if maxw <= 5 {
(Kernel::Struct, 0)
} else {
(Kernel::Swar, 0)
};
}
match g0 {
1 => (Kernel::Bulk1, 0),
2 => (Kernel::Bulk2, 0),
3..=10 => (Kernel::Fixed, g0 as usize),
_ => (Kernel::ByteLoop, 0), }
}
#[inline(always)]
unsafe fn read_one(q: *const u8, end: *const u8) -> Result<(u64, *const u8), ErrorKind> {
let rest = unsafe { core::slice::from_raw_parts(q, end.offset_from(q) as usize) };
let mut raw = 0u64;
let after = read_varint_full(rest, &mut raw)?;
Ok((raw, after.as_ptr()))
}
#[inline(always)]
unsafe fn read_one_swar(q: *const u8, end: *const u8) -> Result<(u64, *const u8), ErrorKind> {
let b = unsafe { *q };
if b < 0x80 {
return Ok((u64::from(b), unsafe { q.add(1) }));
}
let w = unsafe { swar::load64(q) };
let stop = !w & swar::MSB; if stop == 0 {
return unsafe { read_one(q, end) };
}
let len = (stop.trailing_zeros() >> 3) as usize + 1;
let mask = stop ^ (stop - 1);
Ok((swar::compact7(w & mask & swar::LOW7), unsafe { q.add(len) }))
}
#[inline]
unsafe fn put<T, F: FnMut(u64) -> T>(out: *mut T, i: usize, raw: u64, conv: &mut F) {
unsafe { ptr::write(out.add(i), conv(raw)) };
}
unsafe fn fixed_fill<const W: usize, T, F: FnMut(u64) -> T>(
mut q: *const u8,
end: *const u8,
n: &mut usize,
out: *mut T,
conv: &mut F,
) -> *const u8 {
let len_mask = swar::low_byte_mask(W);
let msb_w = swar::MSB & len_mask;
let one_varint = msb_w ^ (0x80u64 << (8 * (W - 1)));
if W <= 4 {
let msb2 = msb_w | (msb_w << (8 * W));
let two_varints = one_varint | (one_varint << (8 * W));
while end.addr().wrapping_sub(q.addr()) >= 8 {
let w = unsafe { swar::load64(q) };
if (w & msb2) == two_varints {
let r0 = swar::compact7(w & len_mask & swar::LOW7);
let r1 = swar::compact7((w >> (8 * W)) & len_mask & swar::LOW7);
unsafe {
put(out, *n, r0, conv);
put(out, *n + 1, r1, conv);
}
*n += 2;
q = unsafe { q.add(2 * W) };
} else if (w & msb_w) == one_varint {
let r = swar::compact7(w & len_mask & swar::LOW7);
unsafe { put(out, *n, r, conv) };
*n += 1;
q = unsafe { q.add(W) };
} else {
break;
}
}
} else {
while end.addr().wrapping_sub(q.addr()) >= 8 {
let w = unsafe { swar::load64(q) };
if (w & msb_w) != one_varint {
break;
}
let r = swar::compact7(w & len_mask & swar::LOW7);
unsafe { put(out, *n, r, conv) };
*n += 1;
q = unsafe { q.add(W) };
}
}
q
}
unsafe fn fixed_fill_wide<const W: usize, T, F: FnMut(u64) -> T>(
mut q: *const u8,
end: *const u8,
n: &mut usize,
out: *mut T,
conv: &mut F,
) -> *const u8 {
debug_assert!(W == 9 || W == 10);
while end.addr().wrapping_sub(q.addr()) >= W {
let w0 = unsafe { swar::load64(q) };
if (w0 & swar::MSB) != swar::MSB {
break; }
let mut value = swar::compact7(w0 & swar::LOW7);
let b8 = unsafe { *q.add(8) };
if W == 9 {
if (b8 & 0x80) != 0 {
break; }
value |= u64::from(b8 & 0x7F) << 56;
} else {
let b9 = unsafe { *q.add(9) };
if (b8 & 0x80) == 0 || (b9 & 0x80) != 0 {
break; }
if b9 > 1 {
break; }
value |= u64::from(b8 & 0x7F) << 56;
value |= u64::from(b9) << 63;
}
unsafe { put(out, *n, value, conv) };
*n += 1;
q = unsafe { q.add(W) };
}
q
}
#[inline(never)]
unsafe fn decode_kernel<T, F: FnMut(u64) -> T>(
span: &[u8],
out: *mut T,
conv: &mut F,
) -> Result<usize, (ErrorKind, usize)> {
let core::ops::Range { start: begin, end } = span.as_ptr_range();
let mut q = begin;
let mut n = 0usize;
let avail = |q: *const u8| end.addr().wrapping_sub(q.addr());
loop {
let q_start = q;
let (kern, width) = unsafe { classify(q, avail(q)) };
match kern {
Kernel::Bulk1 => {
while avail(q) >= 64 {
let mut any = 0u64;
for j in 0..8usize {
any |= unsafe { swar::load64(q.add(8 * j)) } & swar::MSB;
}
if any == 0 {
for i in 0..64usize {
unsafe { put(out, n + i, u64::from(*q.add(i)), conv) };
}
q = unsafe { q.add(64) };
n += 64;
} else {
break;
}
}
}
Kernel::Bulk2 => {
while avail(q) >= 8 {
let w = unsafe { swar::load64(q) };
if (w & swar::MSB) == 0x0080_0080_0080_0080 {
let x = w & swar::LOW7;
let y = (x & 0x007F_007F_007F_007F) | ((x & 0x7F00_7F00_7F00_7F00) >> 1);
unsafe {
put(out, n, u64::from(y as u16), conv);
put(out, n + 1, u64::from((y >> 16) as u16), conv);
put(out, n + 2, u64::from((y >> 32) as u16), conv);
put(out, n + 3, u64::from((y >> 48) as u16), conv);
q = q.add(8);
}
n += 4;
} else {
break;
}
}
}
Kernel::Fixed => {
q = unsafe {
match width {
3 => fixed_fill::<3, _, _>(q, end, &mut n, out, conv),
4 => fixed_fill::<4, _, _>(q, end, &mut n, out, conv),
5 => fixed_fill::<5, _, _>(q, end, &mut n, out, conv),
6 => fixed_fill::<6, _, _>(q, end, &mut n, out, conv),
7 => fixed_fill::<7, _, _>(q, end, &mut n, out, conv),
8 => fixed_fill::<8, _, _>(q, end, &mut n, out, conv),
9 => fixed_fill_wide::<9, _, _>(q, end, &mut n, out, conv),
_ => fixed_fill_wide::<10, _, _>(q, end, &mut n, out, conv),
}
};
}
Kernel::Struct => {
while avail(q) >= 72 {
let mut t = unsafe { swar::stopmask64(q) };
if t == 0 {
break;
}
let mut start = 0i32;
loop {
let b = t.trailing_zeros() as i32;
t &= t - 1;
let len = (b - start + 1) as usize;
if len <= 8 {
let lenmask = swar::low_byte_mask(len);
let w = unsafe { swar::load64(q.add(start as usize)) };
let r = swar::compact7(w & lenmask & swar::LOW7);
unsafe { put(out, n, r, conv) };
n += 1;
} else {
let p = unsafe { q.add(start as usize) };
let (raw, _) = unsafe { read_one(p, end) }
.map_err(|k| (k, p.addr() - begin.addr()))?;
unsafe { put(out, n, raw, conv) };
n += 1;
}
start = b + 1;
if t == 0 {
break;
}
}
q = unsafe { q.add(start as usize) };
}
}
Kernel::Swar => {
while avail(q) >= 8 {
let (raw, next) = unsafe { read_one_swar(q, end) }
.map_err(|k| (k, q.addr() - begin.addr()))?;
q = next;
unsafe { put(out, n, raw, conv) };
n += 1;
}
}
Kernel::ByteLoop => {}
}
if avail(q) < 512 {
break; }
if q.addr().wrapping_sub(q_start.addr()) < 4096 {
break; }
}
let consumed = q.addr() - begin.addr();
let tail = unsafe { decode_scalar(&span[consumed..], out.add(n), conv) }
.map_err(|(k, off)| (k, consumed + off))?;
Ok(n + tail)
}
#[inline(always)]
unsafe fn decode_scalar<T, F: FnMut(u64) -> T>(
span: &[u8],
out: *mut T,
conv: &mut F,
) -> Result<usize, (ErrorKind, usize)> {
let core::ops::Range { start: begin, end } = span.as_ptr_range();
let mut q = begin;
let mut n = 0usize;
while q < end {
let b = unsafe { *q };
let raw = if b < 0x80 {
q = unsafe { q.add(1) };
u64::from(b)
} else {
let (raw, next) =
unsafe { read_one(q, end) }.map_err(|k| (k, q.addr() - begin.addr()))?;
q = next;
raw
};
unsafe { put(out, n, raw, conv) };
n += 1;
}
Ok(n)
}
impl<'a, T> DecodeVec<'a, T> {
#[inline]
pub fn fill_packed_varints<F>(
&mut self,
span: &[u8],
base_off: usize,
mut conv: F,
) -> Result<(), DecodeError>
where
F: FnMut(u64) -> T,
{
if span.is_empty() {
return Ok(());
}
self.reserve(span.len())
.map_err(|_| DecodeError::new(ErrorKind::ArenaExhausted, 0))?;
let tail = self.spare_capacity_ptr();
let written = if span.len() >= KERNEL_MIN_SPAN {
unsafe { decode_kernel(span, tail, &mut conv) }
} else {
unsafe { decode_scalar(span, tail, &mut conv) }
}
.map_err(|(k, off)| DecodeError::new(k, base_off + off))?;
unsafe { self.advance_len(written) };
self.shrink_to_fit();
Ok(())
}
}
#[cfg(all(test, feature = "alloc"))]
mod tests {
use super::*;
use crate::arena::Arena;
fn put_varint(out: &mut alloc::vec::Vec<u8>, mut v: u64) {
loop {
let b = (v & 0x7F) as u8;
v >>= 7;
if v != 0 {
out.push(b | 0x80);
} else {
out.push(b);
break;
}
}
}
fn decode_u64(span: &[u8]) -> alloc::vec::Vec<u64> {
let arena = Arena::new();
let mut v = DecodeVec::<u64>::new(&arena);
v.fill_packed_varints(span, 0, |raw| raw).unwrap();
v.into_slice().to_vec()
}
fn check(values: &[u64]) {
let mut span = alloc::vec::Vec::new();
for &x in values {
put_varint(&mut span, x);
}
assert_eq!(decode_u64(&span), values, "span len {}", span.len());
}
fn runs(n: u64) -> u64 {
if cfg!(miri) {
n / 10
} else {
n
}
}
#[test]
fn empty_span() {
assert_eq!(decode_u64(&[]), alloc::vec::Vec::<u64>::new());
}
#[test]
fn small_span_uses_scalar_loop() {
check(&[0, 1, 127, 128, 300, 16384, u64::MAX]);
}
#[test]
fn homogeneous_1_byte_bulk1() {
let vals: alloc::vec::Vec<u64> = (0..2000u64).map(|i| i % 128).collect();
check(&vals);
}
#[test]
fn homogeneous_2_byte_bulk2() {
let vals: alloc::vec::Vec<u64> = (0..runs(2000)).map(|i| 128 + (i % 16000)).collect();
check(&vals);
}
#[test]
fn homogeneous_fixed_widths_3_through_10() {
let per_width = [
(3usize, 1u64 << 14), (4, 1 << 21),
(5, 1 << 28),
(6, 1 << 35),
(7, 1 << 42),
(8, 1 << 49),
(9, 1 << 56),
(10, 1 << 63),
];
for (w, base) in per_width {
let vals: alloc::vec::Vec<u64> = (0..runs(1500)).map(|i| base + (i & 0x3F)).collect();
check(&vals);
let _ = w;
}
}
#[test]
fn narrow_mixed_struct() {
let vals: alloc::vec::Vec<u64> = (0..runs(3000))
.map(|i| match i % 5 {
0 => i % 100, 1 => 200 + (i % 10000), 2 => 1 << 20, 3 => 1 << 24, _ => 1 << 30, })
.collect();
check(&vals);
}
fn swar_span(values: &[u64]) -> alloc::vec::Vec<u8> {
let mut span = alloc::vec::Vec::new();
for &x in values {
put_varint(&mut span, x);
}
assert!(unsafe { classify(span.as_ptr(), span.len()) }.0 == Kernel::Swar);
span
}
fn swar_prefix_values() -> alloc::vec::Vec<u64> {
(0..100u64)
.map(|i| if i % 3 == 0 { u64::MAX } else { i })
.collect()
}
fn swar_prefix() -> alloc::vec::Vec<u8> {
swar_span(&swar_prefix_values())
}
#[test]
fn wide_mixed_swar() {
let vals: alloc::vec::Vec<u64> = (0..runs(3000))
.map(|i| if i % 7 == 0 { u64::MAX - i } else { i % 50 })
.collect();
swar_span(&vals);
check(&vals);
}
#[test]
fn wide_mixed_swar_every_width() {
let vals: alloc::vec::Vec<u64> = (0..runs(3000))
.map(|i| match i % 10 {
9 => u64::MAX - i,
w => (1u64 << (7 * w)) + i % 7, })
.collect();
let span = swar_span(&vals);
assert_eq!(decode_u64(&span), vals);
}
fn decode_err(span: &[u8]) -> (ErrorKind, usize) {
let arena = Arena::new();
let mut v = DecodeVec::<u64>::new(&arena);
let err = v.fill_packed_varints(span, 0, |raw| raw).unwrap_err();
(err.kind(), err.offset())
}
#[test]
fn swar_overflow_reports_offset() {
let mut span = swar_prefix();
let overflow_at = span.len();
span.resize(span.len() + 9, 0x80);
span.push(0x02);
assert_eq!(decode_err(&span), (ErrorKind::VarintOverflow, overflow_at));
}
#[test]
fn swar_truncation_reports_offset() {
for left in [9usize, 7] {
let mut span = swar_prefix();
let truncated_at = span.len();
span.resize(span.len() + left, 0x80);
assert_eq!(decode_err(&span), (ErrorKind::Truncated, truncated_at));
}
}
#[test]
fn scalar_loop_reports_offset_after_one_byte_values() {
assert_eq!(decode_err(&[1, 2, 0x80]), (ErrorKind::Truncated, 2));
let mut span = alloc::vec![5, 0x7f];
span.resize(span.len() + 9, 0xff);
span.push(0x02);
assert_eq!(decode_err(&span), (ErrorKind::VarintOverflow, 2));
}
#[test]
fn swar_non_canonical_padding() {
let mut span = swar_prefix();
let mut expected = swar_prefix_values();
for _ in 0..50 {
span.extend_from_slice(&[0x81, 0x80, 0x80, 0x00, 0xac, 0x82, 0x00, 0x07]);
expected.extend([1, 300, 7]);
}
assert_eq!(decode_u64(&span), expected);
}
#[test]
fn re_classify_across_regime_change() {
let mut vals: alloc::vec::Vec<u64> = (0..6000u64).map(|_| 1).collect(); vals.extend((0..runs(3000)).map(|i| 128 + (i % 16000))); vals.extend((0..runs(3000)).map(|i| if i % 7 == 0 { u64::MAX } else { i % 50 }));
check(&vals);
}
#[test]
fn conv_is_applied_per_element() {
let arena = Arena::new();
let mut v = DecodeVec::<i32>::new(&arena);
let mut span = alloc::vec::Vec::new();
for i in 0..1000u64 {
put_varint(&mut span, i);
}
v.fill_packed_varints(&span, 0, |raw| raw as i32).unwrap();
let got = v.into_slice();
assert_eq!(got.len(), 1000);
for (i, &x) in got.iter().enumerate() {
assert_eq!(x, i as i32);
}
}
#[test]
fn truncated_varint_errors_without_panic() {
let mut span = alloc::vec::Vec::new();
for _ in 0..500 {
put_varint(&mut span, 300); }
span.push(0x80); let arena = Arena::new();
let mut v = DecodeVec::<u64>::new(&arena);
let err = v.fill_packed_varints(&span, 10, |raw| raw).unwrap_err();
assert_eq!(err.kind(), ErrorKind::Truncated);
assert_eq!(err.offset(), 10 + (span.len() - 1));
}
#[test]
fn spans_around_the_kernel_min_span_boundary() {
for n in [255usize, 256, 257] {
let vals: alloc::vec::Vec<u64> = (0..n as u64).map(|i| i % 128).collect();
check(&vals);
}
}
#[test]
fn ten_byte_overflow_bails_to_tail_and_reports_overflow() {
let mut span = alloc::vec::Vec::new();
for _ in 0..40 {
put_varint(&mut span, 1u64 << 63); }
let overflow_at = span.len();
span.resize(span.len() + 9, 0x80); span.push(0x02); let arena = Arena::new();
let mut v = DecodeVec::<u64>::new(&arena);
let err = v.fill_packed_varints(&span, 0, |raw| raw).unwrap_err();
assert_eq!(err.kind(), ErrorKind::VarintOverflow);
assert_eq!(err.offset(), overflow_at);
}
#[test]
fn two_segments_reserve_into_nonempty() {
let arena = Arena::new();
let mut v = DecodeVec::<u64>::new(&arena);
let seg1: alloc::vec::Vec<u64> = (0..300u64).map(|i| 128 + (i % 16000)).collect(); let seg2: alloc::vec::Vec<u64> = (0..400u64).map(|i| i % 64).collect(); let mut b1 = alloc::vec::Vec::new();
for &x in &seg1 {
put_varint(&mut b1, x);
}
let mut b2 = alloc::vec::Vec::new();
for &x in &seg2 {
put_varint(&mut b2, x);
}
v.fill_packed_varints(&b1, 0, |raw| raw).unwrap();
v.fill_packed_varints(&b2, 0, |raw| raw).unwrap();
let got = v.into_slice();
let mut expected = seg1.clone();
expected.extend(seg2);
assert_eq!(got, &expected[..]);
}
}