protozero/
encoding.rs

1use crate::Error;
2
3pub(crate) const VARINT_MAX_LEN: usize = 10;
4
5/// Decodes a varint from a slice, returning the remainder of the slice and the value.
6#[allow(clippy::get_first)]
7#[inline]
8pub(crate) fn read_varint(buf: &[u8]) -> Result<(&[u8], u64), Error> {
9    if let Some(&byte) = buf.get(0) {
10        if byte <= 0x7f {
11            return Ok((&buf[1..], byte as u64));
12        }
13    }
14    read_varint_loop(buf)
15}
16
17#[allow(clippy::int_plus_one)]
18fn read_varint_loop(buf: &[u8]) -> Result<(&[u8], u64), Error> {
19    let mut index = 0;
20    let mut value = 0;
21    // Compare `index + 1` in the conditional. This lets the compiler optimize out bounds checks in
22    // the loop body.
23    while index < VARINT_MAX_LEN && index + 1 <= buf.len() {
24        let byte = buf[index];
25        value |= ((byte & 0x7f) as u64) << (index * 7);
26        if byte <= 0x7f {
27            if index + 1 == VARINT_MAX_LEN && byte > 0x01 {
28                break;
29            }
30            return Ok((&buf[index + 1..], value));
31        }
32        index += 1;
33    }
34    Err(Error)
35}
36
37pub(crate) mod zigzag {
38    #[inline]
39    pub(crate) fn decode_32(n: u32) -> i32 {
40        (n >> 1) as i32 ^ -((n & 1) as i32)
41    }
42
43    #[inline]
44    pub(crate) fn decode_64(n: u64) -> i64 {
45        (n >> 1) as i64 ^ -((n & 1) as i64)
46    }
47}
48
49#[cfg(test)]
50mod tests {
51    use super::read_varint;
52    use super::zigzag;
53    use crate::Error;
54    use core::ptr;
55
56    #[test]
57    fn read_varint_ok() {
58        for (input, (expected_value, len)) in [
59            (&b"\x00"[..], (0, 1)),
60            (&b"\x01"[..], (1, 1)),
61            (&b"\x7f"[..], (127, 1)),
62            (&b"\xa2\x74"[..], (14882, 2)),
63            (&b"\xbe\xf7\x92\x84\x0b"[..], (2961488830, 5)),
64            (&b"\xbe\xf7\x92\x84\x1b"[..], (7256456126, 5)),
65            (
66                &b"\x80\xe6\xeb\x9c\xc3\xc9\xa4\x49"[..],
67                (41256202580718336, 8),
68            ),
69            (
70                &b"\x9b\xa8\xf9\xc2\xbb\xd6\x80\x85\xa6\x01"[..],
71                (11964378330978735131, 10),
72            ),
73            (
74                &b"\xff\xff\xff\xff\xff\xff\xff\xff\xff\x01"[..],
75                (0xffffffffffffffff, 10),
76            ),
77        ] {
78            let (buf, value) = read_varint(input).unwrap();
79            assert!(ptr::eq(buf, &input[len..]));
80            assert_eq!(value, expected_value);
81        }
82    }
83
84    #[test]
85    fn read_varint_invalid() {
86        assert_eq!(read_varint(&b""[..]), Err(Error));
87        assert_eq!(read_varint(&b"\xf0\xab"[..]), Err(Error));
88        assert_eq!(read_varint(&b"\xf0\xab\xc9\x9a\xf8\xb2"[..]), Err(Error));
89    }
90
91    #[test]
92    fn read_varint_overflow() {
93        assert_eq!(
94            read_varint(&b"\xff\xff\xff\xff\xff\xff\xff\xff\xff\x02"[..]),
95            Err(Error)
96        );
97    }
98
99    #[test]
100    fn read_varint_too_many_bytes() {
101        assert_eq!(
102            read_varint(&b"\xff\xff\xff\xff\xff\xff\xff\xff\xff\x80\x00"[..]),
103            Err(Error)
104        );
105    }
106
107    #[test]
108    fn zigzag_decode_32() {
109        assert_eq!(zigzag::decode_32(0), 0);
110        assert_eq!(zigzag::decode_32(1), -1);
111        assert_eq!(zigzag::decode_32(2), 1);
112        assert_eq!(zigzag::decode_32(3), -2);
113        assert_eq!(zigzag::decode_32(0x7FFFFFFE), 0x3FFFFFFF_u32 as i32);
114        assert_eq!(zigzag::decode_32(0x7FFFFFFF), 0xC0000000_u32 as i32);
115        assert_eq!(zigzag::decode_32(0xFFFFFFFE), 0x7FFFFFFF_u32 as i32);
116        assert_eq!(zigzag::decode_32(0xFFFFFFFF), 0x80000000_u32 as i32);
117    }
118
119    #[test]
120    fn zigzag_decode_64() {
121        assert_eq!(zigzag::decode_64(0), 0);
122        assert_eq!(zigzag::decode_64(1), -1);
123        assert_eq!(zigzag::decode_64(2), 1);
124        assert_eq!(zigzag::decode_64(3), -2);
125        assert_eq!(
126            zigzag::decode_64(0x000000007FFFFFFE),
127            0x000000003FFFFFFF_u64 as i64
128        );
129        assert_eq!(
130            zigzag::decode_64(0x000000007FFFFFFF),
131            0xFFFFFFFFC0000000_u64 as i64
132        );
133        assert_eq!(
134            zigzag::decode_64(0x00000000FFFFFFFE),
135            0x000000007FFFFFFF_u64 as i64
136        );
137        assert_eq!(
138            zigzag::decode_64(0x00000000FFFFFFFF),
139            0xFFFFFFFF80000000_u64 as i64
140        );
141        assert_eq!(
142            zigzag::decode_64(0xFFFFFFFFFFFFFFFE),
143            0x7FFFFFFFFFFFFFFF_u64 as i64
144        );
145        assert_eq!(
146            zigzag::decode_64(0xFFFFFFFFFFFFFFFF),
147            0x8000000000000000_u64 as i64
148        );
149    }
150}
protozero/encoding.rs

protozero/
encoding.rs
