bitcoin_embed/
varint.rs

1//! # LEB128 Variable-Length Encoding
2
3// Source: ordinals/varint.rs
4
5/// Adds an integer to a byte array with LEB128 encoding
6pub fn encode_to_vec(mut n: u128, v: &mut Vec<u8>) {
7    while n >> 7 > 0 {
8        v.push(n.to_le_bytes()[0] | 0b1000_0000);
9        n >>= 7;
10    }
11    v.push(n.to_le_bytes()[0]);
12}
13
14/// Decodes value from a LEB128-encoded integer
15pub fn decode(buffer: &[u8]) -> Result<(u128, usize), Error> {
16    let mut n = 0u128;
17
18    for (i, &byte) in buffer.iter().enumerate() {
19        if i > 18 {
20            return Err(Error::Overlong);
21        }
22
23        let value = u128::from(byte) & 0b0111_1111;
24
25        if i == 18 && value & 0b0111_1100 != 0 {
26            return Err(Error::Overflow);
27        }
28
29        n |= value << (7 * i);
30
31        if byte & 0b1000_0000 == 0 {
32            return Ok((n, i + 1));
33        }
34    }
35
36    Err(Error::Unterminated)
37}
38
39/// Returns a LEB128-encoded integer
40pub fn encode(n: u128) -> Vec<u8> {
41    let mut v = Vec::new();
42    encode_to_vec(n, &mut v);
43    v
44}
45
46/// VarInt Error
47#[derive(PartialEq, Debug)]
48pub enum Error {
49    /// Too long
50    Overlong,
51    /// Overflow
52    Overflow,
53    /// Unterminated
54    Unterminated,
55}
56
57impl std::fmt::Display for Error {
58    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
59        match self {
60            Self::Overlong => write!(f, "too long"),
61            Self::Overflow => write!(f, "overflow"),
62            Self::Unterminated => write!(f, "unterminated"),
63        }
64    }
65}
66
67impl std::error::Error for Error {}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn zero_round_trips_successfully() {
75        let n = 0;
76        let encoded = encode(n);
77        let (decoded, length) = decode(&encoded).unwrap();
78        assert_eq!(decoded, n);
79        assert_eq!(length, encoded.len());
80    }
81
82    #[test]
83    fn u128_max_round_trips_successfully() {
84        let n = u128::MAX;
85        let encoded = encode(n);
86        let (decoded, length) = decode(&encoded).unwrap();
87        assert_eq!(decoded, n);
88        assert_eq!(length, encoded.len());
89    }
90
91    #[test]
92    fn powers_of_two_round_trip_successfully() {
93        for i in 0..128 {
94            let n = 1 << i;
95            let encoded = encode(n);
96            let (decoded, length) = decode(&encoded).unwrap();
97            assert_eq!(decoded, n);
98            assert_eq!(length, encoded.len());
99        }
100    }
101
102    #[test]
103    fn alternating_bit_strings_round_trip_successfully() {
104        let mut n = 0;
105
106        for i in 0..129 {
107            n = (n << 1) | (i % 2);
108            let encoded = encode(n);
109            let (decoded, length) = decode(&encoded).unwrap();
110            assert_eq!(decoded, n);
111            assert_eq!(length, encoded.len());
112        }
113    }
114
115    #[test]
116    fn varints_may_not_be_longer_than_19_bytes() {
117        const VALID: [u8; 19] = [
118            128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
119            128, 0,
120        ];
121
122        const INVALID: [u8; 20] = [
123            128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
124            128, 128, 0,
125        ];
126
127        assert_eq!(decode(&VALID), Ok((0, 19)));
128        assert_eq!(decode(&INVALID), Err(Error::Overlong));
129    }
130
131    #[test]
132    fn varints_may_not_overflow_u128() {
133        assert_eq!(
134            decode(&[
135                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
136                128, 128, 64,
137            ]),
138            Err(Error::Overflow)
139        );
140        assert_eq!(
141            decode(&[
142                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
143                128, 128, 32,
144            ]),
145            Err(Error::Overflow)
146        );
147        assert_eq!(
148            decode(&[
149                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
150                128, 128, 16,
151            ]),
152            Err(Error::Overflow)
153        );
154        assert_eq!(
155            decode(&[
156                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
157                128, 128, 8,
158            ]),
159            Err(Error::Overflow)
160        );
161        assert_eq!(
162            decode(&[
163                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
164                128, 128, 4,
165            ]),
166            Err(Error::Overflow)
167        );
168        assert_eq!(
169            decode(&[
170                128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
171                128, 128, 2,
172            ]),
173            Ok((2u128.pow(127), 19))
174        );
175    }
176
177    #[test]
178    fn varints_must_be_terminated() {
179        assert_eq!(decode(&[128]), Err(Error::Unterminated));
180    }
181}
bitcoin_embed/varint.rs

bitcoin_embed/
varint.rs
