buffertk/
varint.rs

1//! This module provides an implementation of the variable integer encoding specified in the
2//! [protobuf encoding documentation](https://developers.google.com/protocol-buffers/docs/encoding).
3//!
4//! By convention the `From<I>` and `Into<I>` traits are implemented for all common integer types
5//! I.  They will silently truncate and it is up to higher level code to unpack to full v64 and
6//! check for overflow when casting.
7#![allow(clippy::len_zero)]
8#![allow(clippy::from_over_into)]
9
10use super::Error;
11use super::Packable;
12use super::Unpackable;
13
14use std::convert::TryInto;
15
16////////////////////////////////////////////// Varint //////////////////////////////////////////////
17
18/// v64 is the type of a variable integer encoding.  It can represent any value of 64-bits or
19/// fewer.  The encoding follows the protocol buffer spec, which means that negative numbers will
20/// always serialize to ten bytes.
21#[allow(non_camel_case_types)]
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub struct v64 {
24    x: u64,
25}
26
27impl From<u8> for v64 {
28    fn from(x: u8) -> v64 {
29        v64 { x: x as u64 }
30    }
31}
32
33impl TryInto<u8> for v64 {
34    type Error = Error;
35
36    fn try_into(self) -> Result<u8, Error> {
37        match self.x.try_into() {
38            Ok(x) => Ok(x),
39            Err(_) => Err(Error::UnsignedOverflow { value: self.x }),
40        }
41    }
42}
43
44impl From<u16> for v64 {
45    fn from(x: u16) -> v64 {
46        v64 { x: x as u64 }
47    }
48}
49
50impl TryInto<u16> for v64 {
51    type Error = Error;
52
53    fn try_into(self) -> Result<u16, Error> {
54        match self.x.try_into() {
55            Ok(x) => Ok(x),
56            Err(_) => Err(Error::UnsignedOverflow { value: self.x }),
57        }
58    }
59}
60
61impl From<u32> for v64 {
62    fn from(x: u32) -> v64 {
63        v64 { x: x as u64 }
64    }
65}
66
67impl TryInto<u32> for v64 {
68    type Error = Error;
69
70    fn try_into(self) -> Result<u32, Error> {
71        match self.x.try_into() {
72            Ok(x) => Ok(x),
73            Err(_) => Err(Error::UnsignedOverflow { value: self.x }),
74        }
75    }
76}
77
78impl From<u64> for v64 {
79    fn from(x: u64) -> v64 {
80        v64 { x }
81    }
82}
83
84impl Into<u64> for v64 {
85    fn into(self) -> u64 {
86        self.x
87    }
88}
89
90impl From<i8> for v64 {
91    fn from(x: i8) -> v64 {
92        v64 { x: x as u64 }
93    }
94}
95
96impl TryInto<i8> for v64 {
97    type Error = Error;
98
99    fn try_into(self) -> Result<i8, Error> {
100        let value: i64 = self.x as i64;
101        match value.try_into() {
102            Ok(x) => Ok(x),
103            Err(_) => Err(Error::SignedOverflow { value }),
104        }
105    }
106}
107
108impl From<i16> for v64 {
109    fn from(x: i16) -> v64 {
110        v64 { x: x as u64 }
111    }
112}
113
114impl TryInto<i16> for v64 {
115    type Error = Error;
116
117    fn try_into(self) -> Result<i16, Error> {
118        let value: i64 = self.x as i64;
119        match value.try_into() {
120            Ok(x) => Ok(x),
121            Err(_) => Err(Error::SignedOverflow { value }),
122        }
123    }
124}
125
126impl From<i32> for v64 {
127    fn from(x: i32) -> v64 {
128        v64 { x: x as u64 }
129    }
130}
131
132impl TryInto<i32> for v64 {
133    type Error = Error;
134
135    fn try_into(self) -> Result<i32, Error> {
136        let value: i64 = self.x as i64;
137        match value.try_into() {
138            Ok(x) => Ok(x),
139            Err(_) => Err(Error::SignedOverflow { value }),
140        }
141    }
142}
143
144impl From<i64> for v64 {
145    fn from(x: i64) -> v64 {
146        v64 { x: x as u64 }
147    }
148}
149
150impl Into<i64> for v64 {
151    fn into(self) -> i64 {
152        self.x as i64
153    }
154}
155
156impl From<usize> for v64 {
157    fn from(x: usize) -> v64 {
158        // unwrap because we assume and test this is safe
159        let x: u64 = x.try_into().unwrap();
160        v64 { x }
161    }
162}
163
164impl Into<usize> for v64 {
165    fn into(self) -> usize {
166        // unwrap because we assume and test this is safe
167        let x: usize = self.x.try_into().unwrap();
168        x
169    }
170}
171
172impl Packable for v64 {
173    fn pack_sz(&self) -> usize {
174        let mut x: u64 = self.x;
175        let mut count: usize = 1;
176        x >>= 7;
177        while x > 0 {
178            x >>= 7;
179            count += 1;
180        }
181        count
182    }
183
184    fn pack(&self, out: &mut [u8]) {
185        let mut x: u64 = self.x;
186        out[0] = (x & 0x7f) as u8;
187        x >>= 7;
188        let mut idx: usize = 1;
189        while x > 0 {
190            out[idx - 1] |= 128;
191            out[idx] = (x & 0x7f) as u8;
192            idx += 1;
193            x >>= 7;
194        }
195    }
196}
197
198impl v64 {
199    fn unpack_slow(buf: &[u8]) -> Result<(Self, &[u8]), Error> {
200        let bytes: usize = if buf.len() < 10 { buf.len() } else { 10 };
201        let mut ret = 0u64;
202        let mut idx = 0;
203        let mut shl = 0;
204        while idx + 1 < bytes && buf[idx] & 128 != 0 {
205            ret |= (buf[idx] as u64 & 127) << shl;
206            idx += 1;
207            shl += 7;
208        }
209        if !buf.is_empty() && buf[idx] & 128 == 0 {
210            ret |= (buf[idx] as u64 & 127) << shl;
211            idx += 1;
212            let ret: v64 = ret.into();
213            Ok((ret, &buf[idx..]))
214        } else {
215            Err(Error::VarintOverflow { bytes })
216        }
217    }
218
219    fn unpack_size<const SZ: usize>(buf: &[u8]) -> Result<(Self, &[u8]), Error> {
220        let mut result = (buf[SZ - 1] as u64) << (7 * (SZ - 1));
221        let mut offset = 0;
222        for b in buf.iter().take(SZ - 1) {
223            result += (*b as u64 - 0x80) << offset;
224            offset += 7;
225        }
226        Ok((v64::from(result), &buf[SZ..]))
227    }
228}
229
230impl<'a> Unpackable<'a> for v64 {
231    type Error = Error;
232
233    #[inline(always)]
234    fn unpack<'b>(buf: &'b [u8]) -> Result<(Self, &'b [u8]), Error>
235    where
236        'b: 'a,
237    {
238        if buf.len() < 10 {
239            return Self::unpack_slow(buf);
240        }
241        if buf[0] < 128 {
242            Self::unpack_size::<1>(buf)
243        } else if buf[1] < 128 {
244            Self::unpack_size::<2>(buf)
245        } else if buf[2] < 128 {
246            Self::unpack_size::<3>(buf)
247        } else if buf[3] < 128 {
248            Self::unpack_size::<4>(buf)
249        } else if buf[4] < 128 {
250            Self::unpack_size::<5>(buf)
251        } else if buf[5] < 128 {
252            Self::unpack_size::<6>(buf)
253        } else if buf[6] < 128 {
254            Self::unpack_size::<7>(buf)
255        } else if buf[7] < 128 {
256            Self::unpack_size::<8>(buf)
257        } else if buf[8] < 128 {
258            Self::unpack_size::<9>(buf)
259        } else if buf[9] < 128 {
260            Self::unpack_size::<10>(buf)
261        } else {
262            Err(Error::VarintOverflow { bytes: buf.len() })
263        }
264    }
265}
266
267///////////////////////////////////////////// mod tests ////////////////////////////////////////////
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272
273    fn from_into_x<X, E>(x: X)
274    where
275        v64: std::convert::From<X> + std::convert::TryInto<X, Error = E>,
276        X: std::fmt::Debug + PartialEq + Copy,
277        E: std::fmt::Debug,
278    {
279        let v: v64 = v64::from(x);
280        let x2: X = v.try_into().unwrap();
281        assert_eq!(x, x2, "value did not survive a .into().into()");
282    }
283
284    #[test]
285    fn from_into_u8() {
286        from_into_x(u8::MIN);
287        from_into_x(u8::MAX);
288        from_into_x(1u8);
289    }
290
291    #[test]
292    fn try_into_u8() {
293        let x: u64 = (u8::MAX as u64) + 1;
294        let v: v64 = v64::from(x);
295        let x2: Result<u8, Error> = v.try_into();
296        assert_eq!(Err(Error::UnsignedOverflow { value: x }), x2);
297    }
298
299    #[test]
300    fn from_into_u16() {
301        from_into_x(u16::MIN);
302        from_into_x(u16::MAX);
303        from_into_x(1u16);
304    }
305
306    #[test]
307    fn try_into_u16() {
308        let x: u64 = (u16::MAX as u64) + 1;
309        let v: v64 = v64::from(x);
310        let x2: Result<u16, Error> = v.try_into();
311        assert_eq!(Err(Error::UnsignedOverflow { value: x }), x2);
312    }
313
314    #[test]
315    fn from_into_u32() {
316        from_into_x(u32::MIN);
317        from_into_x(u32::MAX);
318        from_into_x(1u32);
319    }
320
321    #[test]
322    fn try_into_u32() {
323        let x: u64 = (u32::MAX as u64) + 1;
324        let v: v64 = v64::from(x);
325        let x2: Result<u32, Error> = v.try_into();
326        assert_eq!(Err(Error::UnsignedOverflow { value: x }), x2);
327    }
328
329    #[test]
330    fn from_into_u64() {
331        from_into_x(u64::MIN);
332        from_into_x(u64::MAX);
333        from_into_x(1u64);
334    }
335
336    #[test]
337    fn from_into_i8() {
338        from_into_x(i8::MIN);
339        from_into_x(i8::MAX);
340        from_into_x(-1i8);
341        from_into_x(0i8);
342        from_into_x(1i8);
343    }
344
345    #[test]
346    fn try_into_i8() {
347        let x: i64 = (i8::MAX as i64) + 1;
348        let v: v64 = v64::from(x);
349        let x2: Result<i8, Error> = v.try_into();
350        assert_eq!(Err(Error::SignedOverflow { value: x }), x2);
351    }
352
353    #[test]
354    fn from_into_i16() {
355        from_into_x(i16::MIN);
356        from_into_x(i16::MAX);
357        from_into_x(-1i16);
358        from_into_x(0i16);
359        from_into_x(1i16);
360    }
361
362    #[test]
363    fn try_into_i16() {
364        let x: i64 = (i16::MAX as i64) + 1;
365        let v: v64 = v64::from(x);
366        let x2: Result<i16, Error> = v.try_into();
367        assert_eq!(Err(Error::SignedOverflow { value: x }), x2);
368    }
369
370    #[test]
371    fn from_into_i32() {
372        from_into_x(i32::MIN);
373        from_into_x(i32::MAX);
374        from_into_x(-1i32);
375        from_into_x(0i32);
376        from_into_x(1i32);
377    }
378
379    #[test]
380    fn try_into_i32() {
381        let x: i64 = (i32::MAX as i64) + 1;
382        let v: v64 = v64::from(x);
383        let x2: Result<i32, Error> = v.try_into();
384        assert_eq!(Err(Error::SignedOverflow { value: x }), x2);
385    }
386
387    #[test]
388    fn from_into_i64() {
389        from_into_x(i64::MIN);
390        from_into_x(i64::MAX);
391        from_into_x(-1i64);
392        from_into_x(0i64);
393        from_into_x(1i64);
394    }
395
396    #[test]
397    fn from_into_usize() {
398        from_into_x(usize::MIN);
399        from_into_x(usize::MAX);
400        from_into_x(1usize);
401    }
402
403    #[test]
404    fn assumption_u64_holds_usize() {
405        let min: u64 = usize::MIN.try_into().unwrap();
406        let min: usize = min.try_into().unwrap();
407        assert_eq!(usize::MIN, min, "u64 cannot hold usize::MIN");
408        let max: u64 = usize::MAX.try_into().unwrap();
409        let max: usize = max.try_into().unwrap();
410        assert_eq!(usize::MAX, max, "u64 cannot hold usize::MAX");
411    }
412
413    const TESTS: &[(u64, usize, &[u8])] = &[
414        (0, 1, &[0]),
415        (1, 1, &[1]),
416        ((1 << 7) - 1, 1, &[127]),
417        ((1 << 7), 2, &[128, 1]),
418        ((1 << 14) - 1, 2, &[255, 127]),
419        ((1 << 14), 3, &[128, 128, 1]),
420        ((1 << 21) - 1, 3, &[255, 255, 127]),
421        ((1 << 21), 4, &[128, 128, 128, 1]),
422        ((1 << 28) - 1, 4, &[255, 255, 255, 127]),
423        ((1 << 28), 5, &[128, 128, 128, 128, 1]),
424        ((1 << 35) - 1, 5, &[255, 255, 255, 255, 127]),
425        ((1 << 35), 6, &[128, 128, 128, 128, 128, 1]),
426        ((1 << 42) - 1, 6, &[255, 255, 255, 255, 255, 127]),
427        ((1 << 42), 7, &[128, 128, 128, 128, 128, 128, 1]),
428        ((1 << 49) - 1, 7, &[255, 255, 255, 255, 255, 255, 127]),
429        ((1 << 49), 8, &[128, 128, 128, 128, 128, 128, 128, 1]),
430        ((1 << 56) - 1, 8, &[255, 255, 255, 255, 255, 255, 255, 127]),
431        ((1 << 56), 9, &[128, 128, 128, 128, 128, 128, 128, 128, 1]),
432        (
433            (1 << 63) - 1,
434            9,
435            &[255, 255, 255, 255, 255, 255, 255, 255, 127],
436        ),
437        (
438            (1 << 63),
439            10,
440            &[128, 128, 128, 128, 128, 128, 128, 128, 128, 1],
441        ),
442    ];
443
444    #[test]
445    fn pack_varint() {
446        for (idx, &(num, bytes, enc)) in TESTS.iter().enumerate() {
447            println!("test case={idx} x={num}, |x|={bytes}, s(x)={enc:?}");
448            let mut buf: [u8; 10] = [0; 10];
449            assert_eq!(bytes, enc.len(), "human got test case wrong?");
450            assert!(bytes <= buf.len(), "human made buffer too small?");
451            let num: v64 = num.into();
452            let req = num.pack_sz();
453            assert_eq!(bytes, req, "human got pack_sz wrong?");
454            num.pack(&mut buf[..bytes]);
455            assert_eq!(enc, &buf[..bytes], "human got encoder wrong?");
456        }
457    }
458
459    #[test]
460    fn unpack_varint() {
461        for (idx, &(num, bytes, enc)) in TESTS.iter().enumerate() {
462            println!("test case={idx} x={num}, |x|={bytes}, s(x)={enc:?}");
463            assert_eq!(bytes, enc.len(), "human got test case wrong?");
464            assert!(enc.len() <= 10, "human got test harness wrong?");
465            let mut buf: [u8; 10] = [0xff; 10];
466            buf[..enc.len()].copy_from_slice(enc);
467            let (x, rem): (v64, &[u8]) = Unpackable::unpack(&buf).unwrap();
468            let v: v64 = num.into();
469            assert_eq!(v, x, "human got decode wrong?");
470            assert_eq!(rem, &buf[bytes..], "human got remainder wrong?");
471        }
472    }
473
474    // TODO(rescrv): test unhappy paths
475}
buffertk/varint.rs

buffertk/
varint.rs
