ironwork_rt/module/
leb.rs

1//! Unsigned LEB128 and zigzag (load-module.md §4.1), with only the canonical form accepted.
2
3#[derive(Clone, Copy, Debug, PartialEq, Eq)]
4pub enum LebError {
5    /// The bytes end before the last group.
6    End,
7    /// A zero final group after a continuation, as `80 00`.
8    OverLong,
9    /// More than 64 bits.
10    Overflow,
11}
12
13pub fn write(out: &mut Vec<u8>, mut value: u64) {
14    loop {
15        let group = (value & 0x7F) as u8;
16        value >>= 7;
17        if value == 0 {
18            out.push(group);
19            return;
20        }
21        out.push(group | 0x80);
22    }
23}
24
25/// The value at the front of `bytes`, and how many bytes it takes.
26pub fn read(bytes: &[u8]) -> Result<(u64, usize), LebError> {
27    let mut value = 0u64;
28    for (i, &byte) in bytes.iter().enumerate() {
29        if i == 9 && byte > 1 {
30            return Err(LebError::Overflow);
31        }
32        value |= u64::from(byte & 0x7F) << (7 * i);
33        if byte & 0x80 == 0 {
34            return if byte == 0 && i > 0 { Err(LebError::OverLong) } else { Ok((value, i + 1)) };
35        }
36    }
37    Err(LebError::End)
38}
39
40pub const fn zigzag(n: i64) -> u64 {
41    ((n << 1) ^ (n >> 63)) as u64
42}
43
44pub const fn unzigzag(z: u64) -> i64 {
45    (z >> 1) as i64 ^ -((z & 1) as i64)
46}
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    fn bytes(value: u64) -> Vec<u8> {
53        let mut out = Vec::new();
54        write(&mut out, value);
55        out
56    }
57
58    #[test]
59    fn seven_bits_per_byte_low_group_first() {
60        assert_eq!(bytes(0), [0x00]);
61        assert_eq!(bytes(127), [0x7F]);
62        assert_eq!(bytes(128), [0x80, 0x01]);
63        assert_eq!(bytes(1140), [0xF4, 0x08]);
64        assert_eq!(bytes(16_384), [0x80, 0x80, 0x01]);
65        assert_eq!(bytes(u64::MAX), [0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01]);
66    }
67
68    #[test]
69    fn every_width_reads_back_and_reports_its_length() {
70        for shift in 0..64 {
71            for value in [1u64 << shift, (1u64 << shift) - 1, (1u64 << shift) + 1] {
72                let encoded = bytes(value);
73                assert_eq!(read(&encoded), Ok((value, encoded.len())), "{value}");
74            }
75        }
76        assert_eq!(read(&[0x05, 0xFF]), Ok((5, 1)));
77    }
78
79    #[test]
80    fn only_the_canonical_form_is_read() {
81        assert_eq!(read(&[0x80, 0x00]), Err(LebError::OverLong));
82        assert_eq!(read(&[0xFF, 0x80, 0x00]), Err(LebError::OverLong));
83        assert_eq!(read(&[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00]), Err(LebError::OverLong));
84        assert_eq!(read(&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x02]), Err(LebError::Overflow));
85        assert_eq!(read(&[0x80; 11]), Err(LebError::Overflow));
86        assert_eq!(read(&[]), Err(LebError::End));
87        assert_eq!(read(&[0x80]), Err(LebError::End));
88        assert_eq!(read(&[0xFF, 0xFF]), Err(LebError::End));
89    }
90
91    #[test]
92    fn zigzag_interleaves_the_signs() {
93        let pairs = [(0, 0), (-1, 1), (1, 2), (-2, 3), (2, 4), (i64::MAX, u64::MAX - 1), (i64::MIN, u64::MAX)];
94        for (n, z) in pairs {
95            assert_eq!(zigzag(n), z, "{n}");
96            assert_eq!(unzigzag(z), n, "{z}");
97        }
98        assert_eq!(zigzag(i64::from(i32::MIN)), u64::from(u32::MAX));
99    }
100}
ironwork_rt/module/leb.rs

ironwork_rt/module/
leb.rs
