plugmem_core/index/
varint.rs

1//! LEB128 varint coding for posting lists.
2//!
3//! Posting entries store fact-id *deltas*; lists are sorted by
4//! construction (fact ids are assigned monotonically), so deltas are
5//! small and most entries take 1 byte instead of 4.
6
7/// Maximum encoded size of a `u32` (5 × 7 bits ≥ 32 bits).
8pub const MAX_VARINT: usize = 5;
9
10/// Encodes `v` into `out`, returning the number of bytes written (1..=5).
11pub fn encode_u32(v: u32, out: &mut [u8; MAX_VARINT]) -> usize {
12    let mut v = v;
13    let mut n = 0;
14    loop {
15        let byte = (v & 0x7F) as u8;
16        v >>= 7;
17        if v == 0 {
18            out[n] = byte;
19            return n + 1;
20        }
21        out[n] = byte | 0x80;
22        n += 1;
23    }
24}
25
26/// Decodes one `u32` from the front of `bytes`, returning the value and
27/// the number of bytes consumed. `None` on truncated input or a value
28/// that does not fit 32 bits (a 5th byte with more than 4 payload bits,
29/// or a continuation bit on the 5th byte).
30pub fn decode_u32(bytes: &[u8]) -> Option<(u32, usize)> {
31    let mut v = 0u32;
32    for (i, &byte) in bytes.iter().take(MAX_VARINT).enumerate() {
33        let payload = u32::from(byte & 0x7F);
34        if i == MAX_VARINT - 1 && (byte & 0x80 != 0 || payload > 0x0F) {
35            return None;
36        }
37        v |= payload << (7 * i);
38        if byte & 0x80 == 0 {
39            return Some((v, i + 1));
40        }
41    }
42    None
43}
plugmem_core/index/varint.rs

plugmem_core/index/
varint.rs
