lumen/
varint.rs

1//! Protocol-Buffers-style varints ([`spec/11-layer-encoding.md`] section 5.2).
2//!
3//! Seven data bits per byte, least-significant group first, MSB set means more
4//! bytes follow. The shortest form is mandatory: an overlong encoding is
5//! malformed, as is anything longer than 10 bytes or a varint that runs past the
6//! end of its buffer.
7
8use crate::check::Check;
9use crate::error::{Error, Result};
10use crate::io::{Reader, Writer};
11
12/// The longest legal varint: a 64-bit value needs at most 10 bytes.
13pub const MAX_LEN: usize = 10;
14
15/// Decode one varint, advancing the reader past it.
16///
17/// Every failure reports [`Check::ReeVarint`], the corpus name for this rule.
18pub fn decode(reader: &mut Reader<'_>) -> Result<u64> {
19    let start = reader.pos();
20    let mut result: u64 = 0;
21    let mut shift: u32 = 0;
22    let mut count = 0usize;
23    loop {
24        if count == MAX_LEN {
25            return Err(Error::new(
26                Check::ReeVarint,
27                format!("varint at offset {start} is longer than {MAX_LEN} bytes"),
28            ));
29        }
30        let byte = match reader.u8() {
31            Ok(b) => b,
32            Err(_) => {
33                return Err(Error::new(
34                    Check::ReeVarint,
35                    format!("varint at offset {start} runs past the end of its buffer"),
36                ))
37            }
38        };
39        count += 1;
40        if count == MAX_LEN && byte > 0x01 {
41            return Err(Error::new(
42                Check::ReeVarint,
43                format!("varint at offset {start} overflows 64 bits"),
44            ));
45        }
46        result |= u64::from(byte & 0x7F) << shift;
47        if byte & 0x80 == 0 {
48            if count > 1 && byte == 0 {
49                return Err(Error::new(
50                    Check::ReeVarint,
51                    format!("varint at offset {start} is not minimally encoded"),
52                ));
53            }
54            return Ok(result);
55        }
56        shift += 7;
57    }
58}
59
60/// Append `value` in its shortest form.
61pub fn encode(out: &mut Writer, value: u64) {
62    let mut v = value;
63    while v >= 0x80 {
64        out.u8((v as u8) | 0x80);
65        v >>= 7;
66    }
67    out.u8(v as u8);
68}
69
70/// The number of bytes [`encode`] would write.
71pub fn encoded_len(value: u64) -> usize {
72    let mut len = 1;
73    let mut v = value >> 7;
74    while v != 0 {
75        len += 1;
76        v >>= 7;
77    }
78    len
79}
80
81/// Encode to a fresh `Vec`.
82pub fn to_vec(value: u64) -> Vec<u8> {
83    let mut w = Writer::with_capacity(encoded_len(value));
84    encode(&mut w, value);
85    w.into_vec()
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    fn round_trip(value: u64) {
93        let bytes = to_vec(value);
94        assert_eq!(bytes.len(), encoded_len(value));
95        let mut r = Reader::new(&bytes);
96        assert_eq!(r.varint().unwrap(), value);
97        assert!(r.is_empty());
98    }
99
100    #[test]
101    fn spec_examples() {
102        assert_eq!(to_vec(0), vec![0x00]);
103        assert_eq!(to_vec(128), vec![0x80, 0x01]);
104        assert_eq!(to_vec(2_073_600).len(), 3); // 1920 x 1080
105        assert_eq!(to_vec(74_649_600).len(), 4); // 11520 x 6480
106    }
107
108    #[test]
109    fn round_trips_boundaries() {
110        for value in [
111            0,
112            1,
113            127,
114            128,
115            16_383,
116            16_384,
117            2_097_151,
118            2_097_152,
119            268_435_455,
120            268_435_456,
121            u64::MAX,
122        ] {
123            round_trip(value);
124        }
125    }
126
127    #[test]
128    fn overlong_is_rejected() {
129        let mut r = Reader::new(&[0x80, 0x00]);
130        let err = r.varint().unwrap_err();
131        assert_eq!(err.check(), Check::ReeVarint);
132    }
133
134    #[test]
135    fn truncated_is_rejected() {
136        let mut r = Reader::new(&[0x80]);
137        assert_eq!(r.varint().unwrap_err().check(), Check::ReeVarint);
138    }
139
140    #[test]
141    fn overflow_is_rejected() {
142        // Eleven continuation bytes, then a value bit.
143        let mut bytes = vec![0xFFu8; 10];
144        bytes.push(0x01);
145        let mut r = Reader::new(&bytes);
146        assert_eq!(r.varint().unwrap_err().check(), Check::ReeVarint);
147    }
148
149    #[test]
150    fn max_u64_round_trips_in_ten_bytes() {
151        let bytes = to_vec(u64::MAX);
152        assert_eq!(bytes.len(), 10);
153        let mut r = Reader::new(&bytes);
154        assert_eq!(r.varint().unwrap(), u64::MAX);
155    }
156}
lumen/varint.rs

lumen/
varint.rs
