serde_jam/compact/
vlen.rs

1//! Length prefix encoding.
2
3use crate::{Vec, compact::Numeric, vec};
4
5/// The thresholds for the length prefix encoding.
6pub const THRESHOLDS: [(usize, u8, u8, u64, u64); 7] = [
7    // 1 bytes, 0x80 = 2^8 - 2^7, 2^8, 2^14
8    (1, 0x80, 0xc0, 0x100, 0x4000),
9    // 2 bytes, 0xc0 = 2^8 - 2^6, 2^16, 2^21
10    (2, 0xc0, 0xe0, 0x10000, 0x200000),
11    // 3 bytes, 0xe0 = 2^8 - 2^5, 2^24, 2^28
12    (3, 0xe0, 0xf0, 0x1000000, 0x10000000),
13    // 4 bytes, 0xf0 = 2^8 - 2^4, 2^32, 2^35
14    (4, 0xf0, 0xf8, 0x100000000, 0x800000000),
15    // 5 bytes, 0xf8 = 2^8 - 2^3, 2^40, 2^42
16    (5, 0xf8, 0xfc, 0x10000000000, 0x40000000000),
17    // 6 bytes, 0xfc = 2^8 - 2^2, 2^48, 2^49
18    (6, 0xfc, 0xfe, 0x1000000000000, 0x2000000000000),
19    // 7 bytes, 0xfe = 2^8 - 2^1, 2^56, 2^56
20    (7, 0xfe, 0xff, 0x100000000000000, 0x100000000000000),
21];
22
23/// Encode a value into a length prefix.
24pub fn encode(value: u64) -> Vec<u8> {
25    if value < 0x80 {
26        return vec![value as u8];
27    }
28
29    // It's okay to use for loops here because it has the same performance as a match.
30    for (length, base, _, bits, threshold) in THRESHOLDS.into_iter() {
31        if value < threshold {
32            let mut encoded = vec![base + (value / bits) as u8];
33            let remainder = (value % bits).encode();
34            // Always pad to the expected length for this threshold level
35            encoded.extend_from_slice(&remainder);
36            while encoded.len() < length + 1 {
37                encoded.push(0);
38            }
39
40            return encoded;
41        }
42    }
43
44    [vec![255], value.to_le_bytes().to_vec()].concat()
45}
46
47/// Decode a compact encoded number.
48pub fn decode(encoded: &[u8]) -> u64 {
49    self::decode_from(encoded).0
50}
51
52/// Decode a length prefix.
53pub fn decode_from(encoded: &[u8]) -> (u64, usize) {
54    if encoded.is_empty() {
55        return (0, 0);
56    }
57
58    let prefix = encoded[0];
59    if prefix < 0x80 {
60        return (prefix as u64, 1);
61    }
62
63    // loop instead match for returning the length
64    for (length, base, next, bits, _) in THRESHOLDS.into_iter() {
65        if prefix < next {
66            let dlen = length + 1;
67            return (
68                ((prefix - base) as u64) * bits + u64::decode(&encoded[1..dlen]),
69                dlen,
70            );
71        }
72    }
73
74    (u64::decode(&encoded[1..9]), 9)
75}
76
77#[test]
78fn thresholds() {
79    for (length, base, _, bits, threshold) in THRESHOLDS.into_iter() {
80        assert_eq!(bits.trailing_zeros(), 8 * length as u32);
81
82        // check that the base is correct
83        let expected = 2u64.pow(8_u32) - 2u64.pow((8 - length) as u32);
84        assert_eq!(base, expected as u8);
85
86        // check the threshold is correct
87        let expected = 2u64.pow(7 * (length + 1) as u32);
88        assert_eq!(threshold, expected,);
89    }
90}
91
92#[test]
93fn roundtrip() {
94    for (length, _, _, _, threshold) in THRESHOLDS.iter() {
95        let value = threshold - 1;
96        let encoded = encode(value);
97        let (decoded, dlen) = decode_from(&encoded);
98        assert_eq!(dlen, *length + 1);
99        assert_eq!(encoded.len(), dlen);
100        assert_eq!(value, decoded);
101    }
102}
103
104#[test]
105fn vlen_zero() {
106    assert_eq!(encode(0), vec![0]);
107}
serde_jam/compact/vlen.rs

serde_jam/compact/
vlen.rs
