ordered_varint/
lib.rs

1#![doc= include_str!("../.rustme/docs.md")]
2#![forbid(unsafe_code)]
3#![warn(
4    clippy::cargo,
5    missing_docs,
6    // clippy::missing_docs_in_private_items,
7    clippy::nursery,
8    clippy::pedantic,
9    future_incompatible,
10    rust_2018_idioms,
11)]
12#![cfg_attr(doc, allow(unknown_lints), warn(rustdoc::all))] // https://github.com/rust-lang/rust/pull/106316
13#![allow(
14    clippy::missing_errors_doc, // TODO clippy::missing_errors_doc
15    clippy::option_if_let_else,
16    clippy::module_name_repetitions,
17    clippy::cast_sign_loss,
18    clippy::cast_possible_truncation,
19)]
20
21mod signed;
22mod unsigned;
23
24use std::io::{Read, Write};
25
26pub use self::signed::*;
27pub use self::unsigned::*;
28
29/// Encodes and decodes a type using a variable-length format.
30pub trait Variable: Sized {
31    /// Encodes `self` into `destination`, returning the number of bytes written upon success.
32    fn encode_variable<W: Write>(&self, destination: W) -> std::io::Result<usize>;
33    /// Decodes a variable length value from `source`.
34    fn decode_variable<R: Read>(source: R) -> std::io::Result<Self>;
35
36    /// Encodes `self` into a new `Vec<u8>`.
37    fn to_variable_vec(&self) -> std::io::Result<Vec<u8>> {
38        let mut output = Vec::with_capacity(16);
39        self.encode_variable(&mut output)?;
40        Ok(output)
41    }
42}
43
44macro_rules! impl_primitive_variable {
45    ($ty:ty,  $dest:ty) => {
46        impl Variable for $ty {
47            fn encode_variable<W: Write>(&self, destination: W) -> std::io::Result<usize> {
48                <$dest>::encode_be_bytes(self.to_be_bytes(), destination)
49            }
50
51            fn decode_variable<R: Read>(source: R) -> std::io::Result<Self> {
52                <$dest>::decode_variable_bytes(source).map(<Self>::from_be_bytes)
53            }
54        }
55    };
56}
57
58impl_primitive_variable!(u8, Unsigned);
59impl_primitive_variable!(u16, Unsigned);
60impl_primitive_variable!(u32, Unsigned);
61impl_primitive_variable!(u64, Unsigned);
62impl_primitive_variable!(u128, Unsigned);
63impl_primitive_variable!(usize, Unsigned);
64
65impl_primitive_variable!(i8, Signed);
66impl_primitive_variable!(i16, Signed);
67impl_primitive_variable!(i32, Signed);
68impl_primitive_variable!(i64, Signed);
69impl_primitive_variable!(i128, Signed);
70impl_primitive_variable!(isize, Signed);
71
72#[cfg(test)]
73mod tests {
74    use std::fmt::Debug;
75
76    use super::*;
77
78    trait TestType: Variable {
79        type Variable: From<Self> + TryInto<Self> + Variable + Eq + Debug;
80    }
81
82    macro_rules! impl_test_type {
83        ($name:ident, $kind:ident) => {
84            impl TestType for $name {
85                type Variable = $kind;
86            }
87        };
88    }
89
90    impl_test_type!(u8, Unsigned);
91    impl_test_type!(u16, Unsigned);
92    impl_test_type!(u32, Unsigned);
93    impl_test_type!(u64, Unsigned);
94    impl_test_type!(u128, Unsigned);
95    impl_test_type!(usize, Unsigned);
96
97    impl_test_type!(i8, Signed);
98    impl_test_type!(i16, Signed);
99    impl_test_type!(i32, Signed);
100    impl_test_type!(i64, Signed);
101    impl_test_type!(i128, Signed);
102    impl_test_type!(isize, Signed);
103
104    fn roundtrip<T: TestType + Eq + Debug + Copy>(value: T, expected_bytes: usize) {
105        let mut bytes = Vec::new();
106        let encoded_length = value.encode_variable(&mut bytes).unwrap();
107        println!("Encoded {value:?} to {bytes:02x?}");
108        assert_eq!(
109            encoded_length, expected_bytes,
110            "expected {expected_bytes} encoded bytes, got {encoded_length}"
111        );
112        assert_eq!(
113            encoded_length,
114            bytes.len(),
115            "vec has more bytes than returned value"
116        );
117        let decoded = T::decode_variable(&bytes[..]).unwrap();
118        assert_eq!(
119            decoded, value,
120            "decoded value did not match: {value:?} vs {decoded:?}",
121        );
122
123        // Because we now decode and encode directly, we also need to test using
124        // Signed/Unsigned
125        let variable = <T::Variable as From<T>>::from(value);
126        let mut bytes = Vec::new();
127        let encoded_length = variable.encode_variable(&mut bytes).unwrap();
128        assert_eq!(
129            encoded_length, expected_bytes,
130            "expected {expected_bytes} encoded bytes, got {encoded_length}"
131        );
132        assert_eq!(
133            encoded_length,
134            bytes.len(),
135            "vec has more bytes than returned value"
136        );
137        let decoded = <T::Variable as Variable>::decode_variable(&bytes[..]).unwrap();
138        assert_eq!(
139            decoded, variable,
140            "decoded value did not match: {variable:?} vs {decoded:?}",
141        );
142    }
143
144    #[test]
145    fn roundtrip_u8() {
146        roundtrip(u8::MIN, 1);
147        roundtrip(2_u8.pow(4) - 1, 1);
148        roundtrip(2_u8.pow(4), 2);
149    }
150
151    #[test]
152    fn roundtrip_i8() {
153        roundtrip(0_i8, 1);
154        roundtrip(2_i8.pow(3) - 1, 1);
155        roundtrip(-(2_i8.pow(3)), 1);
156
157        roundtrip(2_i8.pow(3), 2);
158        roundtrip(-(2_i8.pow(3) + 1), 2);
159
160        roundtrip(-1_i8, 1);
161    }
162
163    #[test]
164    fn roundtrip_u16() {
165        roundtrip(u16::from(u8::MAX), 2);
166        roundtrip(2_u16.pow(12) - 1, 2);
167        roundtrip(2_u16.pow(12), 3);
168    }
169
170    #[test]
171    fn roundtrip_i16() {
172        roundtrip(i16::from(i8::MAX), 2);
173        roundtrip(i16::from(i8::MIN), 2);
174        roundtrip(2_i16.pow(11) - 1, 2);
175        roundtrip(-(2_i16.pow(11)), 2);
176
177        roundtrip(2_i16.pow(11), 3);
178        roundtrip(-(2_i16.pow(11) + 1), 3);
179
180        roundtrip(-1_i16, 1);
181    }
182
183    #[test]
184    fn roundtrip_u32() {
185        roundtrip(u32::from(u16::MAX), 3);
186        roundtrip(2_u32.pow(20) - 1, 3);
187        roundtrip(2_u32.pow(20), 4);
188        roundtrip(2_u32.pow(28) - 1, 4);
189        roundtrip(2_u32.pow(28), 5);
190    }
191
192    #[test]
193    fn roundtrip_i32() {
194        roundtrip(i32::from(i16::MAX), 3);
195        roundtrip(i32::from(i16::MIN), 3);
196        roundtrip(2_i32.pow(19) - 1, 3);
197        roundtrip(-(2_i32.pow(19)), 3);
198        roundtrip(2_i32.pow(19), 4);
199        roundtrip(-(2_i32.pow(19) + 1), 4);
200
201        roundtrip(2_i32.pow(27), 5);
202        roundtrip(-(2_i32.pow(27) + 1), 5);
203
204        roundtrip(-1_i32, 1);
205    }
206
207    #[test]
208    fn roundtrip_u64() {
209        roundtrip(u64::from(u32::MAX), 5);
210        roundtrip(2_u64.pow(36) - 1, 5);
211        roundtrip(2_u64.pow(36), 6);
212        roundtrip(2_u64.pow(44) - 1, 6);
213        roundtrip(2_u64.pow(44), 7);
214        roundtrip(2_u64.pow(52) - 1, 7);
215        roundtrip(2_u64.pow(52), 8);
216        roundtrip(2_u64.pow(60) - 1, 8);
217        roundtrip(2_u64.pow(60), 9);
218    }
219
220    #[test]
221    fn roundtrip_i64() {
222        roundtrip(i64::from(i32::MAX), 5);
223        roundtrip(i64::from(i32::MIN), 5);
224        roundtrip(2_i64.pow(35) - 1, 5);
225        roundtrip(-(2_i64.pow(35)), 5);
226        roundtrip(2_i64.pow(35), 6);
227        roundtrip(-(2_i64.pow(35) + 1), 6);
228
229        roundtrip(2_i64.pow(43), 7);
230        roundtrip(-(2_i64.pow(43) + 1), 7);
231
232        roundtrip(2_i64.pow(51), 8);
233        roundtrip(-(2_i64.pow(51) + 1), 8);
234
235        roundtrip(2_i64.pow(59), 9);
236        roundtrip(-(2_i64.pow(59) + 1), 9);
237
238        roundtrip(-1_i64, 1);
239    }
240
241    #[test]
242    fn roundtrip_u128() {
243        roundtrip(u128::from(u64::MAX), 9);
244        roundtrip(2_u128.pow(68) - 1, 9);
245        roundtrip(2_u128.pow(68), 10);
246        roundtrip(2_u128.pow(76) - 1, 10);
247        roundtrip(2_u128.pow(76), 11);
248        roundtrip(2_u128.pow(84) - 1, 11);
249        roundtrip(2_u128.pow(84), 12);
250        roundtrip(2_u128.pow(92) - 1, 12);
251        roundtrip(2_u128.pow(92), 13);
252        roundtrip(2_u128.pow(100) - 1, 13);
253        roundtrip(2_u128.pow(100), 14);
254        roundtrip(2_u128.pow(108) - 1, 14);
255        roundtrip(2_u128.pow(108), 15);
256        roundtrip(2_u128.pow(116) - 1, 15);
257        roundtrip(2_u128.pow(116), 16);
258
259        // Maximum value
260        roundtrip(2_u128.pow(124) - 1, 16);
261
262        // Above maximum value
263        assert!(2_u128.pow(124).encode_variable(&mut Vec::new()).is_err());
264    }
265
266    #[test]
267    fn roundtrip_i128() {
268        roundtrip(i128::from(i64::MAX), 9);
269        roundtrip(i128::from(i64::MIN), 9);
270        roundtrip(2_i128.pow(67) - 1, 9);
271        roundtrip(-(2_i128.pow(67)), 9);
272        roundtrip(2_i128.pow(67), 10);
273        roundtrip(-(2_i128.pow(67) + 1), 10);
274
275        roundtrip(2_i128.pow(75), 11);
276        roundtrip(-(2_i128.pow(75) + 1), 11);
277
278        roundtrip(2_i128.pow(83), 12);
279        roundtrip(-(2_i128.pow(83) + 1), 12);
280
281        roundtrip(2_i128.pow(91), 13);
282        roundtrip(-(2_i128.pow(91) + 1), 13);
283
284        roundtrip(2_i128.pow(99), 14);
285        roundtrip(-(2_i128.pow(99) + 1), 14);
286
287        roundtrip(2_i128.pow(107), 15);
288        roundtrip(-(2_i128.pow(107) + 1), 15);
289
290        roundtrip(2_i128.pow(115), 16);
291        roundtrip(-(2_i128.pow(115) + 1), 16);
292
293        // Maximum value
294        roundtrip(2_i128.pow(123) - 1, 16);
295        // Minimum value
296        roundtrip(-(2_i128.pow(123)), 16);
297
298        // Above maximum
299        assert!(2_i128.pow(123).encode_variable(&mut Vec::new()).is_err());
300        // Below minimum
301        assert!((-(2_i128.pow(123)) - 1)
302            .encode_variable(&mut Vec::new())
303            .is_err());
304    }
305
306    #[test]
307    fn roundtrip_sizes() {
308        // This test is minimal due to *size types being dependent on the
309        // architecture limits.
310        roundtrip(usize::MAX, std::mem::size_of::<usize>() + 1);
311        roundtrip(usize::MIN, 1);
312        roundtrip(isize::MAX, std::mem::size_of::<isize>() + 1);
313        roundtrip(isize::MIN, std::mem::size_of::<isize>() + 1);
314        roundtrip(0_isize, 1);
315    }
316
317    #[test]
318    fn conversions() {
319        assert_eq!(
320            isize::try_from(Signed::from(isize::MAX)).unwrap(),
321            isize::MAX
322        );
323        assert_eq!(
324            usize::try_from(Unsigned::from(usize::MAX)).unwrap(),
325            usize::MAX
326        );
327        assert_eq!(i128::try_from(Signed::from(i128::MAX)).unwrap(), i128::MAX);
328        assert_eq!(
329            u128::try_from(Unsigned::from(u128::MAX)).unwrap(),
330            u128::MAX
331        );
332    }
333
334    #[test]
335    fn test_signed_ordering() {
336        let mut entries = Vec::new();
337        for i in i16::MIN..=i16::MAX {
338            println!("{} => {:02X?}", i, i.to_variable_vec().unwrap());
339            entries.push(i.to_variable_vec().unwrap());
340        }
341        let originals = entries.clone();
342        entries.sort();
343        assert_eq!(originals, entries);
344    }
345
346    #[test]
347    fn test_unsigned_ordering() {
348        let mut entries = Vec::new();
349        for i in u16::MIN..=u16::MAX {
350            println!("{} => {:02X?}", i, i.to_variable_vec().unwrap());
351            entries.push(i.to_variable_vec().unwrap());
352        }
353        let originals = entries.clone();
354        entries.sort();
355        assert_eq!(originals, entries);
356    }
357
358    #[test]
359    fn overflow_decode() {
360        let unsigned_max = u64::MAX.to_variable_vec().unwrap();
361        u32::decode_variable(&unsigned_max[..]).expect_err("u32 should overflow");
362        let signed_min = i64::MIN.to_variable_vec().unwrap();
363        i32::decode_variable(&signed_min[..]).expect_err("i32 should overflow");
364        let signed_max = i64::MAX.to_variable_vec().unwrap();
365        i32::decode_variable(&signed_max[..]).expect_err("i32 should overflow");
366    }
367}
ordered_varint/lib.rs

ordered_varint/
lib.rs
