sqlite_varint/
lib.rs

1#![deny(missing_docs)]
2//! # SQLite Varint
3//! Utility functions for dealing with SQLite varints.
4
5/// Reads a slice of bytes from the start assuming it is a varint.
6/// Gives back the varint as i64 and the amount of bytes the varint was big.
7/// # Example
8/// ```
9/// use sqlite_varint::read_varint;
10/// // Small positive integer values take little place
11/// assert_eq!((1, 1), read_varint(&vec![0b00000001]));
12///
13/// // Negative values will always take 9 bytes.
14/// // Note that the vector is 10 bytes long.
15/// assert_eq!((-1, 9), read_varint(&vec![0xff; 10]));
16/// ```
17pub fn read_varint(bytes: &[u8]) -> (i64, usize) {
18    let mut varint: i64 = 0;
19    let mut bytes_read: usize = 0;
20    for (i, byte) in bytes.iter().enumerate().take(9) {
21        bytes_read += 1;
22        if i == 8 {
23            varint = (varint << 8) | *byte as i64;
24            break;
25        } else {
26            varint = (varint << 7) | (*byte & 0b0111_1111) as i64;
27            if *byte < 0b1000_0000 {
28                break;
29            }
30        }
31    }
32    (varint, bytes_read)
33}
34
35/// Read how long the varint would be in amount of bytes.
36/// # Example
37/// ```
38/// use sqlite_varint::read_varint_byte_length;
39/// // Small positive integer values take little place
40/// assert_eq!(1, read_varint_byte_length(&vec![0b00000001]));
41///
42/// // Negative values will always take 9 bytes.
43/// // Note that the vector is 10 bytes long.
44/// assert_eq!(9, read_varint_byte_length(&vec![0xff; 10]));
45///
46/// ```
47pub fn read_varint_byte_length(bytes: &[u8]) -> usize {
48    for (i, byte) in bytes.iter().enumerate().take(9) {
49        if *byte < 0b1000_0000 {
50            return i + 1;
51        }
52    }
53    9
54}
55
56/// Serializes an i64 to a variable length byte representation.
57/// # Example
58/// ```
59/// use sqlite_varint::serialize_to_varint;
60/// assert_eq!(vec![0b00000001], serialize_to_varint(1));
61///
62/// assert_eq!(vec![0xff; 9], serialize_to_varint(-1));
63///
64/// ```
65pub fn serialize_to_varint(input: i64) -> Vec<u8> {
66    use std::collections::VecDeque;
67
68    let mut result: VecDeque<u8> = VecDeque::new();
69    let mut shifted_input = input;
70
71    if input as u64 > 0x00ff_ffff_ffff_ffff {
72        // we first push the entire last byte
73        result.push_front((shifted_input & 0b1111_1111) as u8);
74        shifted_input >>= 8;
75    }
76    for _ in 0..8 {
77        result.push_front((shifted_input & 0b0111_1111) as u8);
78
79        shifted_input >>= 7;
80        if result.len() > 1 {
81            let p = result.front_mut().unwrap();
82            *p |= 0b1000_0000;
83        }
84        if shifted_input == 0 {
85            // we reached the last one in case we don't use all 9 bytes.
86            break;
87        }
88    }
89
90    result.into_iter().collect()
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    #[test]
97    fn read_single_byte_varint() {
98        assert_eq!((1, 1), read_varint(&vec![0b00000001]));
99        assert_eq!((3, 1), read_varint(&vec![0b00000011]));
100        assert_eq!((7, 1), read_varint(&vec![0b00000111]));
101        assert_eq!((15, 1), read_varint(&vec![0b00001111]));
102    }
103
104    #[test]
105    fn read_two_byte_varint() {
106        assert_eq!((128, 2), read_varint(&vec![0b10000001, 0b00000000]));
107        assert_eq!((129, 2), read_varint(&vec![0b10000001, 0b00000001]));
108        assert_eq!((255, 2), read_varint(&vec![0b10000001, 0b01111111]));
109    }
110
111    #[test]
112    fn read_nine_byte_varint() {
113        assert_eq!((-1, 9), read_varint(&vec![0xff; 9]));
114    }
115
116    #[test]
117    fn read_varint_in_longer_bytes() {
118        assert_eq!((1, 1), read_varint(&vec![0x01; 10]));
119        assert_eq!((-1, 9), read_varint(&vec![0xff; 10]));
120    }
121
122    #[test]
123    fn serialize_simple_varints() {
124        assert_eq!(vec![0b00000001], serialize_to_varint(1));
125        assert_eq!(vec![0b00000011], serialize_to_varint(3));
126    }
127
128    #[test]
129    fn serialize_medium_length_varints() {
130        assert_eq!(
131            vec![0b10000010, 0b00000001],
132            serialize_to_varint(0b100000001)
133        )
134    }
135
136    #[test]
137    fn serialize_negative_varints() {
138        assert_eq!(vec![0xff; 9], serialize_to_varint(-1));
139    }
140
141    #[test]
142    fn read_varint_lengths() {
143        let bytes_vec: Vec<Vec<u8>> = vec![
144            vec![0x0f],
145            vec![0xff, 0x0f],
146            vec![0xff, 0xff, 0x0f],
147            vec![0xff, 0xff, 0xff, 0x0f],
148            vec![0xff, 0xff, 0xff, 0xff, 0x0f],
149            vec![0xff, 0xff, 0xff, 0xff, 0xff, 0x0f],
150            vec![0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f],
151            vec![0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f],
152            vec![0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f],
153            // Next ones are exceeding the max length of a varint
154            vec![0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x0f],
155            vec![
156                0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x0f, 0x0f,
157            ],
158        ];
159
160        let expected_lengths = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9];
161
162        for i in 0..bytes_vec.len() {
163            assert_eq!(expected_lengths[i], read_varint_byte_length(&bytes_vec[i]));
164        }
165    }
166
167    #[test]
168    fn test_noop() {
169        // doing serialze and deserialze should give the input back.:
170        let inputs: Vec<i64> = vec![
171            0x01,
172            0x1ff,
173            0x123456,
174            0x11223344,
175            0x1122334455,
176            0x112233445566,
177            0x11223344556677,
178            0x1928374655647382,
179        ];
180        for input in inputs {
181            assert_eq!(input, read_varint(&serialize_to_varint(input)).0);
182        }
183    }
184}
sqlite_varint/lib.rs

sqlite_varint/
lib.rs
