uint_zigzag/
lib.rs

1//! Uint is a convenience wrapper for zig-zag encoding integers to byte sequences.
2//!
3//! This allows better compression since the majority of numbers are quite small resulting
4//! in 1 or 2 bytes in the most common case vs 4 for 32-bit numbers or 8 for 64-bit numbers.
5//!
6//! This also permits the user to not have to think about which value is the most efficient
7//! to compress.
8#![no_std]
9#![deny(
10    warnings,
11    missing_docs,
12    unused_import_braces,
13    unused_qualifications,
14    trivial_casts,
15    trivial_numeric_casts
16)]
17#![cfg_attr(docsrs, feature(doc_cfg))]
18
19use core::{
20    fmt::{self, Display, Formatter},
21    iter::{Product, Sum},
22    ops::*,
23};
24use core2::io::{Error, ErrorKind, Read, Write};
25
26#[cfg(feature = "serde")]
27use serde::{
28    de::{Error as DError, Visitor},
29    Deserialize, Deserializer, Serialize, Serializer,
30};
31
32#[cfg(all(feature = "alloc", not(feature = "std")))]
33extern crate alloc;
34#[cfg(feature = "std")]
35extern crate std;
36
37#[cfg(all(feature = "alloc", not(feature = "std")))]
38use alloc::{boxed::Box, vec::Vec};
39#[cfg(feature = "std")]
40use std::{boxed::Box, vec::Vec};
41
42/// Uint implements zig-zag encoding to represent integers as binary sequences
43#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Ord, PartialOrd, Hash)]
44pub struct Uint(pub u128);
45
46impl Display for Uint {
47    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
48        write!(f, "{}", self.0)
49    }
50}
51
52macro_rules! impl_from {
53    ($($tt:ty),+) => {
54        $(
55        impl From<$tt> for Uint {
56            fn from(v: $tt) -> Self {
57                Uint(v as u128)
58            }
59        }
60
61        impl From<Uint> for $tt {
62            fn from(v: Uint) -> $tt {
63                v.0 as $tt
64            }
65        }
66        )+
67    };
68}
69
70impl From<u128> for Uint {
71    fn from(v: u128) -> Self {
72        Self(v)
73    }
74}
75
76impl From<Uint> for u128 {
77    fn from(v: Uint) -> Self {
78        v.0
79    }
80}
81
82impl_from!(u8, u16, u32, u64, usize, i8, i16, i32, i64, i128, isize);
83
84impl TryFrom<&[u8]> for Uint {
85    type Error = &'static str;
86
87    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
88        let mut x = 0u128;
89        let mut s = 0;
90        let mut i = 0;
91
92        while i < Self::MAX_BYTES {
93            if i >= value.len() {
94                return Err("invalid byte sequence");
95            }
96
97            if value[i] < 0x80 {
98                let u = x | (value[i] as u128) << s;
99                return Ok(Self(u));
100            }
101            x |= ((value[i] & 0x7f) as u128) << s;
102            s += 7;
103            i += 1;
104        }
105        Err("invalid byte sequence")
106    }
107}
108
109#[cfg_attr(docsrs, doc(cfg(any(feature = "alloc", feature = "std"))))]
110#[cfg(any(feature = "alloc", feature = "std"))]
111impl TryFrom<&Vec<u8>> for Uint {
112    type Error = &'static str;
113
114    fn try_from(value: &Vec<u8>) -> Result<Self, Self::Error> {
115        Self::try_from(value.as_slice())
116    }
117}
118
119#[cfg_attr(docsrs, doc(cfg(any(feature = "alloc", feature = "std"))))]
120#[cfg(any(feature = "alloc", feature = "std"))]
121impl TryFrom<&Box<Vec<u8>>> for Uint {
122    type Error = &'static str;
123
124    fn try_from(value: &Box<Vec<u8>>) -> Result<Self, Self::Error> {
125        Self::try_from(value.as_slice())
126    }
127}
128
129macro_rules! ops_impl {
130    ($tr:ident, $fn:ident, $op:tt, $($tt:ty),+) => {
131        impl<'a, 'b> $tr<&'b Uint> for &'a Uint {
132            type Output = Uint;
133
134            fn $fn(self, rhs: &'b Uint) -> Self::Output {
135                Uint(self.0 $op rhs.0)
136            }
137        }
138
139        impl<'a> $tr<&'a Uint> for Uint {
140            type Output = Uint;
141
142            fn $fn(self, rhs: &'a Uint) -> Self::Output {
143                Uint(self.0 $op rhs.0)
144            }
145        }
146
147        impl<'b> $tr<Uint> for &'b Uint {
148            type Output = Uint;
149
150            fn $fn(self, rhs: Uint) -> Self::Output {
151                Uint(self.0 $op rhs.0)
152            }
153        }
154
155        impl $tr<Uint> for Uint {
156            type Output = Uint;
157
158            fn $fn(self, rhs: Uint) -> Self::Output {
159                Uint(self.0 $op rhs.0)
160            }
161        }
162
163        impl<'a> $tr<u128> for &'a Uint {
164            type Output = Uint;
165
166            fn $fn(self, rhs: u128) -> Self::Output {
167                Uint(self.0 $op rhs)
168            }
169        }
170
171        impl $tr<u128> for Uint {
172            type Output = Uint;
173
174            fn $fn(self, rhs: u128) -> Self::Output {
175                Uint(self.0 $op rhs)
176            }
177        }
178
179        impl<'a> $tr<&'a Uint> for u128 {
180            type Output = u128;
181
182            fn $fn(self, rhs: &'a Uint) -> Self::Output {
183                self $op rhs.0
184            }
185        }
186
187        impl $tr<Uint> for u128 {
188            type Output = u128;
189
190            fn $fn(self, rhs: Uint) -> Self::Output {
191                self $op rhs.0
192            }
193        }
194
195        $(
196        impl<'a> $tr<$tt> for &'a Uint {
197            type Output = Uint;
198
199            fn $fn(self, rhs: $tt) -> Self::Output {
200                Uint(self.0 $op rhs as u128)
201            }
202        }
203
204        impl $tr<$tt> for Uint {
205            type Output = Uint;
206
207            fn $fn(self, rhs: $tt) -> Self::Output {
208                Uint(self.0 $op rhs as u128)
209            }
210        }
211
212        impl<'a> $tr<&'a Uint> for $tt {
213            type Output = $tt;
214
215            fn $fn(self, rhs: &'a Uint) -> Self::Output {
216                self $op rhs.0 as $tt
217            }
218        }
219
220        impl $tr<Uint> for $tt {
221            type Output = $tt;
222
223            fn $fn(self, rhs: Uint) -> Self::Output {
224                self $op rhs.0 as $tt
225            }
226        }
227        )+
228    };
229}
230
231macro_rules! assign_ops_impl {
232    ($tr:ident, $fn:ident, $op:tt, $($tt:ty),+) => {
233        impl $tr<Uint> for Uint {
234            fn $fn(&mut self, rhs: Uint) {
235                self.0 $op rhs.0;
236            }
237        }
238
239        impl $tr<u128> for Uint {
240            fn $fn(&mut self, rhs: u128) {
241                self.0 $op rhs;
242            }
243        }
244
245        $(
246        impl $tr<$tt> for Uint {
247            fn $fn(&mut self, rhs: $tt) {
248                self.0 $op rhs as u128;
249            }
250        }
251        )+
252    };
253}
254
255ops_impl!(Add, add, +, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
256ops_impl!(Sub, sub, -, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
257ops_impl!(Mul, mul, *, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
258ops_impl!(Div, div, /, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
259ops_impl!(Rem, rem, %, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
260ops_impl!(BitAnd, bitand, &, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
261ops_impl!(BitOr, bitor, |, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
262ops_impl!(BitXor, bitxor, ^, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
263ops_impl!(Shl, shl, <<, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
264ops_impl!(Shr, shr, >>, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
265
266assign_ops_impl!(AddAssign, add_assign, +=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
267assign_ops_impl!(SubAssign, sub_assign, -=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
268assign_ops_impl!(MulAssign, mul_assign, *=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
269assign_ops_impl!(DivAssign, div_assign, /=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
270assign_ops_impl!(RemAssign, rem_assign, %=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
271assign_ops_impl!(BitAndAssign, bitand_assign, &=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
272assign_ops_impl!(BitOrAssign, bitor_assign, |=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
273assign_ops_impl!(BitXorAssign, bitxor_assign, ^=, u64, u32, u16, u8, usize, i128, i64, i32, i16, i8, isize);
274assign_ops_impl!(ShlAssign, shl_assign, <<=, u64, u32, u16, u8, usize, i64, i128, i32, i16, i8, isize);
275assign_ops_impl!(ShrAssign, shr_assign, >>=, u64, u32, u16, u8, usize, i64, i128, i32, i16, i8, isize);
276
277macro_rules! iter_impl {
278    ($($tt:ty),+) => {
279        impl Sum for Uint {
280            fn sum<I: Iterator<Item=Self>>(mut iter: I) -> Self {
281                let mut i = 0u128;
282                while let Some(v) = iter.next() {
283                    i += v.0;
284                }
285                Self(i)
286            }
287        }
288
289        impl Sum<u128> for Uint {
290            fn sum<I: Iterator<Item=u128>>(mut iter: I) -> Self {
291                let mut i = 0u128;
292                while let Some(v) = iter.next() {
293                    i += v;
294                }
295                Self(i)
296            }
297        }
298
299        impl Product for Uint {
300            fn product<I: Iterator<Item=Self>>(mut iter: I) -> Self {
301                let mut i = 0u128;
302                while let Some(v) = iter.next() {
303                    i *= v.0;
304                }
305                Self(i)
306            }
307        }
308
309        impl Product<u128> for Uint {
310            fn product<I: Iterator<Item=u128>>(mut iter: I) -> Self {
311                let mut i = 0u128;
312                while let Some(v) = iter.next() {
313                    i *= v;
314                }
315                Self(i)
316            }
317        }
318
319        $(
320        impl Sum<$tt> for Uint {
321            fn sum<I: Iterator<Item=$tt>>(mut iter: I) -> Self {
322                let mut i = 0u128;
323                while let Some(v) = iter.next() {
324                    i += v as u128;
325                }
326                Self(i)
327            }
328        }
329
330        impl Product<$tt> for Uint {
331            fn product<I: Iterator<Item=$tt>>(mut iter: I) -> Self {
332                let mut i = 0u128;
333                while let Some(v) = iter.next() {
334                    i *= v as u128;
335                }
336                Self(i)
337            }
338        }
339        )+
340    };
341}
342
343iter_impl!(u64, u32, u16, u8, usize, i64, i32, i16, i8, isize);
344
345#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
346#[cfg(feature = "serde")]
347impl Serialize for Uint {
348    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
349        let mut buffer = [0u8; Self::MAX_BYTES];
350        let length = self.to_bytes_with_length(&mut buffer);
351        serializer.serialize_bytes(&buffer[..length])
352    }
353}
354
355#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
356#[cfg(feature = "serde")]
357impl<'de> Deserialize<'de> for Uint {
358    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
359        struct UintVisitor;
360
361        impl<'de> Visitor<'de> for UintVisitor {
362            type Value = Uint;
363
364            fn expecting(&self, f: &mut Formatter<'_>) -> fmt::Result {
365                write!(f, "a byte sequence")
366            }
367
368            fn visit_bytes<E: DError>(self, v: &[u8]) -> Result<Self::Value, E> {
369                match Uint::try_from(v) {
370                    Err(_) => Err(DError::invalid_length(v.len(), &self)),
371                    Ok(u) => Ok(u),
372                }
373            }
374        }
375
376        deserializer.deserialize_bytes(UintVisitor)
377    }
378}
379
380impl Uint {
381    /// The maximum number of bytes a uint will consume
382    pub const MAX_BYTES: usize = 19;
383
384    /// Peek returns the number of bytes that would be read
385    /// or None if no Uint cannot be read
386    ///
387    /// ```
388    /// use uint_zigzag::Uint;
389    ///
390    /// let buffer = [0x34u8];
391    ///
392    /// let out = Uint::peek(&buffer);
393    ///
394    /// assert!(out.is_some());
395    ///
396    /// let out = Uint::peek(&[]);
397    ///
398    /// assert!(out.is_none());
399    /// ```
400    pub fn peek(value: &[u8]) -> Option<usize> {
401        let mut i = 0;
402
403        while i < Self::MAX_BYTES {
404            if i >= value.len() {
405                return None;
406            }
407            if value[i] < 0x80 {
408                return Some(i + 1);
409            }
410
411            i += 1;
412        }
413        None
414    }
415
416    /// Zig-zag encoding, any length from 1 to MAX_BYTES into buffer
417    /// buffer must be big enough to hold the result
418    ///
419    /// ```
420    ///  use uint_zigzag::Uint;
421    ///
422    /// let mut buffer = [0u8, 0u8];
423    /// let mut u = Uint::from(127);
424    /// u.to_bytes(&mut buffer);
425    ///
426    /// assert_eq!(buffer, [0x7Fu8, 0u8]);
427    ///
428    /// u = Uint::from(128);
429    /// u.to_bytes(&mut buffer);
430    /// assert_eq!(buffer, [0x80u8, 1u8]);
431    /// ```
432    pub fn to_bytes<M: AsMut<[u8]>>(&self, mut buffer: M) {
433        self.to_bytes_with_length(buffer.as_mut());
434    }
435
436    /// Same as `to_bytes` except it returns how many bytes were actually used
437    pub fn to_bytes_with_length(self, buffer: &mut [u8]) -> usize {
438        let mut i = 0;
439        let mut x = self.0;
440
441        while x >= 0x80 {
442            buffer[i] = (x as u8) | 0x80;
443            x >>= 7;
444            i += 1;
445        }
446
447        buffer[i] = x as u8;
448        i += 1;
449        i
450    }
451
452    /// Zig-zag encoding, any length from 1 to MAX_BYTES
453    ///
454    /// ```
455    /// use uint_zigzag::Uint;
456    ///
457    /// let u = Uint(345678);
458    /// let out = u.to_vec();
459    ///
460    /// assert_eq!(out.as_slice(), &[206, 140, 21]);
461    ///
462    /// let u = Uint(2048);
463    /// let out = u.to_vec();
464    /// assert_eq!(out.as_slice(), &[128, 16]);
465    /// ```
466    #[cfg_attr(docsrs, doc(cfg(any(feature = "alloc", feature = "std"))))]
467    #[cfg(any(feature = "alloc", feature = "std"))]
468    pub fn to_vec(&self) -> Vec<u8> {
469        let mut output = [0u8; Self::MAX_BYTES];
470        let i = self.to_bytes_with_length(&mut output);
471        output[..i].to_vec()
472    }
473
474    /// Write bytes to a stream
475    pub fn to_writer<W: Write>(&self, writer: &mut W) -> Result<usize, Error> {
476        let mut output = [0u8; Self::MAX_BYTES];
477        let length = self.to_bytes_with_length(&mut output);
478        writer.write(&output[..length])
479    }
480
481    /// Read bytes from a stream
482    pub fn from_reader<R: Read>(reader: &mut R) -> Result<Self, Error> {
483        let mut output = [0u8; Self::MAX_BYTES];
484        let mut i = 0;
485        while i < Self::MAX_BYTES {
486            reader.read_exact(&mut output[i..i + 1])?;
487            if Self::peek(&output[..i]).is_some() {
488                break;
489            }
490            i += 1;
491        }
492        if i == Self::MAX_BYTES {
493            Err(Error::new(ErrorKind::InvalidData, "invalid byte sequence"))
494        } else {
495            Self::try_from(&output[..i]).map_err(|m| Error::new(ErrorKind::InvalidData, m))
496        }
497    }
498}
499
500#[cfg(feature = "std")]
501#[test]
502fn max_bytes() {
503    let u = Uint(u128::MAX);
504    let bytes = u.to_vec();
505    assert_eq!(bytes.len(), Uint::MAX_BYTES);
506}
uint_zigzag/lib.rs

uint_zigzag/
lib.rs
