vlq_rust/
lib.rs

1//! ## Algorithm
2//!
3//! Value-length quantity encoding is an implementation of variable-length integers.
4//!
5//! Each byte is encoded into 7 bits, with the highest bit of the byte used to indicate
6//! if there are any further bytes to read. Reading will continue until the highest bit
7//! is `1`, or will result in an error if the number is too large to fit in the desired
8//! type.
9//!
10//! For example, the number `60000` (or `0xEA60` in hexadecimal):
11//!
12//! ```markdown
13//!          11101010 01100000  [as u16]
14//!       11  1010100  1100000  [as separated into 7-bit groups]
15//!  1100000  1010100       11  [re-organized so least significant byte first]
16//! 11100000 11010100 00000011  [as VLQ-encoded variable-length integer]
17//! ```
18//!
19//! ## Usage
20//!
21//! Add this to your `Cargo.toml`:
22//!
23//! ```toml
24//! [dependencies]
25//! vlq = { package = "vlq-rust", version = "0.2" }
26//! ```
27//!
28//! Use `ReadVlqExt` and `WriteVlqExt` to get the `read_vlq` and `write_vlq` functions
29//! on every `std::io::Read` and `std::io::Write` implementation.
30//!
31//! ## Example
32//!
33//! ```
34//! # use vlq_rust as vlq;
35//! use vlq::{ReadVlqExt, WriteVlqExt};
36//!
37//! let mut data = std::io::Cursor::new(vec![]);
38//! data.write_vlq(std::u64::MAX).unwrap();
39//! data.set_position(0);
40//!
41//! let x: u64 = data.read_vlq().unwrap();
42//! assert_eq!(x, std::u64::MAX);
43//!
44//! let mut data = std::io::Cursor::new(vec![]);
45//! data.write_vlq(std::i64::MIN).unwrap();
46//! data.set_position(0);
47//!
48//! let x: i64 = data.read_vlq().unwrap();
49//! assert_eq!(x, std::i64::MIN);
50//! ```
51
52/// Trait applied to all types that can be encoded as VLQ's.
53pub trait Vlq: Sized {
54    /// Read a variable-length quantity from a reader.
55    fn from_reader<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self>;
56
57    /// Write this variable-length quantity to a writer.
58    fn to_writer<W: std::io::Write>(self, writer: &mut W) -> std::io::Result<()>;
59}
60
61pub trait ReadVlqExt<T> {
62    /// Read a variable-length quantity.
63    fn read_vlq(&mut self) -> std::io::Result<T>;
64}
65
66pub trait WriteVlqExt<T> {
67    /// Write a variable-length quantity.
68    fn write_vlq(&mut self, n: T) -> std::io::Result<()>;
69}
70
71impl<T: Vlq, R: ::std::io::Read> ReadVlqExt<T> for R {
72    fn read_vlq(&mut self) -> std::io::Result<T> {
73        T::from_reader(self)
74    }
75}
76
77impl<T: Vlq, W: ::std::io::Write> WriteVlqExt<T> for W {
78    fn write_vlq(&mut self, n: T) -> std::io::Result<()> {
79        n.to_writer(self)
80    }
81}
82
83/// Helper macro to implement the `Vlq` trait for a primitive type.
84macro_rules! impl_primitive {
85    ($ty:ty) => {
86        impl_primitive!($ty, $ty);
87    };
88    ($ty:ty, $uty:ty) => {
89        impl $crate::Vlq for $ty {
90            fn from_reader<R: ::std::io::Read>(reader: &mut R) -> ::std::io::Result<Self> {
91                let mut buf = [0; 1];
92                let mut value: $uty = 0;
93                let mut shift = 1 as $uty;
94
95                loop {
96                    reader.read_exact(&mut buf)?;
97
98                    value = ((buf[0] & 0b0111_1111) as $uty)
99                        .checked_mul(shift)
100                        .and_then(|add| value.checked_add(add))
101                        .ok_or_else(|| {
102                            std::io::Error::new(
103                                std::io::ErrorKind::Other,
104                                concat!("provided VLQ data too long to fit into ", stringify!($ty)),
105                            )
106                        })?;
107
108                    if (buf[0] & 0b1000_0000) != 0 {
109                        break;
110                    }
111
112                    shift <<= 7;
113                }
114
115                Ok(value as $ty)
116            }
117
118            fn to_writer<W: ::std::io::Write>(self, writer: &mut W) -> ::std::io::Result<()> {
119                let mut n = self as $uty;
120                let mut vlq_buf = [0u8; std::mem::size_of::<$ty>() * 8 / 7 + 1];
121                let mut index = 0;
122
123                while n >= 0x80 {
124                    vlq_buf[index] = (n & 0b0111_1111) as u8;
125                    index += 1;
126                    n >>= 7;
127                }
128
129                vlq_buf[index] = 0b1000_0000 | n as u8;
130                index += 1;
131                writer.write_all(&vlq_buf[..index])?;
132                Ok(())
133            }
134        }
135    };
136}
137
138impl_primitive!(i8, u8);
139impl_primitive!(i16, u16);
140impl_primitive!(i32, u32);
141impl_primitive!(i64, u64);
142impl_primitive!(i128, u128);
143impl_primitive!(isize, usize);
144impl_primitive!(u8);
145impl_primitive!(u16);
146impl_primitive!(u32);
147impl_primitive!(u64);
148impl_primitive!(u128);
149impl_primitive!(usize);
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154    use std::io::Cursor;
155
156    fn roundtrip<T: Vlq>(value: T) -> T {
157        let mut buf = vec![];
158        buf.write_vlq(value).expect("successful write");
159        Cursor::new(buf).read_vlq().expect("successful read")
160    }
161
162    #[test]
163    fn test_smoke() {
164        assert_eq!(std::u8::MAX, roundtrip(std::u8::MAX));
165        assert_eq!(std::u8::MIN, roundtrip(std::u8::MIN));
166        assert_eq!(0u8, roundtrip(0u8));
167
168        assert_eq!(std::i8::MAX, roundtrip(std::i8::MAX));
169        assert_eq!(std::i8::MIN, roundtrip(std::i8::MIN));
170        assert_eq!(0i8, roundtrip(0i8));
171        assert_eq!(-1i8, roundtrip(-1i8));
172
173        assert_eq!(std::u16::MAX, roundtrip(std::u16::MAX));
174        assert_eq!(std::u16::MIN, roundtrip(std::u16::MIN));
175        assert_eq!(0u16, roundtrip(0u16));
176
177        assert_eq!(std::i16::MAX, roundtrip(std::i16::MAX));
178        assert_eq!(std::i16::MIN, roundtrip(std::i16::MIN));
179        assert_eq!(0i16, roundtrip(0i16));
180        assert_eq!(-1i16, roundtrip(-1i16));
181
182        assert_eq!(std::u32::MAX, roundtrip(std::u32::MAX));
183        assert_eq!(std::u32::MIN, roundtrip(std::u32::MIN));
184        assert_eq!(0u32, roundtrip(0u32));
185
186        assert_eq!(std::i32::MAX, roundtrip(std::i32::MAX));
187        assert_eq!(std::i32::MIN, roundtrip(std::i32::MIN));
188        assert_eq!(0i32, roundtrip(0i32));
189        assert_eq!(-1i32, roundtrip(-1i32));
190
191        assert_eq!(std::u64::MAX, roundtrip(std::u64::MAX));
192        assert_eq!(std::u64::MIN, roundtrip(std::u64::MIN));
193        assert_eq!(0u64, roundtrip(0u64));
194
195        assert_eq!(std::i64::MAX, roundtrip(std::i64::MAX));
196        assert_eq!(std::i64::MIN, roundtrip(std::i64::MIN));
197        assert_eq!(0i64, roundtrip(0i64));
198        assert_eq!(-1i64, roundtrip(-1i64));
199
200        assert_eq!(std::u128::MAX, roundtrip(std::u128::MAX));
201        assert_eq!(std::u128::MIN, roundtrip(std::u128::MIN));
202        assert_eq!(0u128, roundtrip(0u128));
203
204        assert_eq!(std::i128::MAX, roundtrip(std::i128::MAX));
205        assert_eq!(std::i128::MIN, roundtrip(std::i128::MIN));
206        assert_eq!(0i128, roundtrip(0i128));
207        assert_eq!(-1i128, roundtrip(-1i128));
208    }
209
210    #[test]
211    fn read_write() {
212        let mut data = std::io::Cursor::new(vec![]);
213        data.write_vlq(std::u64::MAX).unwrap();
214        data.set_position(0);
215
216        let x: u64 = data.read_vlq().unwrap();
217        assert_eq!(x, std::u64::MAX);
218
219        let mut data = std::io::Cursor::new(vec![]);
220        data.write_vlq(std::i64::MIN).unwrap();
221        data.set_position(0);
222
223        let x: i64 = data.read_vlq().unwrap();
224        assert_eq!(x, std::i64::MIN);
225    }
226}
vlq_rust/lib.rs

vlq_rust/
lib.rs
