ix/
varint.rs

1//! Protobuf-style varint encoding/decoding.
2//!
3//! value < 128:     1 byte  `0xxxxxxx`
4//! value < 16384:   2 bytes `1xxxxxxx 0xxxxxxx`
5//! ... up to 10 bytes for u64
6
7use crate::error::{Error, Result};
8
9/// Encode a u64 as a varint, appending bytes to `buf`.
10#[inline]
11pub fn encode(mut value: u64, buf: &mut Vec<u8>) {
12    while value >= 0x80 {
13        buf.push(u8::try_from(value & 0xFF).unwrap_or(0) | 0x80);
14        value >>= 7;
15    }
16    buf.push(u8::try_from(value & 0xFF).unwrap_or(0));
17}
18
19/// Decode a varint from `data` starting at `pos`. Advances `pos` past the varint.
20///
21/// # Errors
22///
23/// Returns `TruncatedVarint` if the data is too short, or `OverflowVarint` if
24/// the varint is too large (>=70 bits).
25#[inline]
26pub fn decode(data: &[u8], pos: &mut usize) -> Result<u64> {
27    let mut result: u64 = 0;
28    let mut shift: u32 = 0;
29    loop {
30        if *pos >= data.len() {
31            return Err(Error::TruncatedVarint(*pos));
32        }
33        if shift >= 70 {
34            return Err(Error::OverflowVarint);
35        }
36        let byte = *data.get(*pos).ok_or(Error::TruncatedVarint(*pos))?;
37        *pos += 1;
38        result |= u64::from(byte & 0x7F) << shift;
39        if byte & 0x80 == 0 {
40            return Ok(result);
41        }
42        shift += 7;
43    }
44}
45
46/// Return the encoded byte length of a varint without allocating.
47#[inline]
48#[must_use]
49pub fn encoded_len(value: u64) -> usize {
50    if value == 0 {
51        return 1;
52    }
53    let bits = usize::try_from(64 - value.leading_zeros()).unwrap_or(0);
54    bits.div_ceil(7)
55}
56
57#[cfg(test)]
58#[allow(clippy::as_conversions, clippy::unwrap_used, clippy::indexing_slicing)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn roundtrip_small() {
64        for v in 0..300u64 {
65            let mut buf = Vec::new();
66            encode(v, &mut buf);
67            let mut pos = 0;
68            assert_eq!(decode(&buf, &mut pos).unwrap(), v);
69            assert_eq!(pos, buf.len());
70        }
71    }
72
73    #[test]
74    fn roundtrip_large() {
75        let values = [0, 1, 127, 128, 16383, 16384, u64::from(u32::MAX), u64::MAX];
76        for &v in &values {
77            let mut buf = Vec::new();
78            encode(v, &mut buf);
79            let mut pos = 0;
80            assert_eq!(decode(&buf, &mut pos).unwrap(), v);
81        }
82    }
83
84    #[test]
85    fn encoded_lengths() {
86        assert_eq!(encoded_len(0), 1);
87        assert_eq!(encoded_len(127), 1);
88        assert_eq!(encoded_len(128), 2);
89        assert_eq!(encoded_len(16383), 2);
90        assert_eq!(encoded_len(16384), 3);
91    }
92
93    #[test]
94    fn truncated_error() {
95        let mut pos = 0;
96        assert!(decode(&[0x80], &mut pos).is_err());
97    }
98
99    #[test]
100    fn multiple_sequential() {
101        let mut buf = Vec::new();
102        encode(42, &mut buf);
103        encode(1000, &mut buf);
104        encode(0, &mut buf);
105
106        let mut pos = 0;
107        assert_eq!(decode(&buf, &mut pos).unwrap(), 42);
108        assert_eq!(decode(&buf, &mut pos).unwrap(), 1000);
109        assert_eq!(decode(&buf, &mut pos).unwrap(), 0);
110        assert_eq!(pos, buf.len());
111    }
112}
ix/varint.rs

ix/
varint.rs
