sourcemap/
vlq.rs

1//! Implements utilities for dealing with the sourcemap vlq encoding.
2use crate::errors::{Error, Result};
3
4const B64_CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
5const B64: [i8; 256] = [
6    -1,
7    -1,
8    -1,
9    -1,
10    -1,
11    -1,
12    -1,
13    -1,
14    -1,
15    -1,
16    -1,
17    -1,
18    -1,
19    -1,
20    -1,
21    -1,
22    -1,
23    -1,
24    -1,
25    -1,
26    -1,
27    -1,
28    -1,
29    -1,
30    -1,
31    -1,
32    -1,
33    -1,
34    -1,
35    -1,
36    -1,
37    -1,
38    -1,
39    -1,
40    -1,
41    -1,
42    -1,
43    -1,
44    -1,
45    -1,
46    -1,
47    -1,
48    -1,
49    62,
50    -1,
51    -1,
52    -1,
53    63,
54    52,
55    53,
56    54,
57    55,
58    56,
59    57,
60    58,
61    59,
62    60,
63    61,
64    -1,
65    -1,
66    -1,
67    -1,
68    -1,
69    -1,
70    -1,
71    0,
72    1,
73    2,
74    3,
75    4,
76    5,
77    6,
78    7,
79    8,
80    9,
81    10,
82    11,
83    12,
84    13,
85    14,
86    15,
87    16,
88    17,
89    18,
90    19,
91    20,
92    21,
93    22,
94    23,
95    24,
96    25,
97    -1,
98    -1,
99    -1,
100    -1,
101    -1,
102    -1,
103    26,
104    27,
105    28,
106    29,
107    30,
108    31,
109    32,
110    33,
111    34,
112    35,
113    36,
114    37,
115    38,
116    39,
117    40,
118    41,
119    42,
120    43,
121    44,
122    45,
123    46,
124    47,
125    48,
126    49,
127    50,
128    51,
129    -1,
130    -1,
131    -1,
132    -1,
133    -1 - 1,
134    -1,
135    -1,
136    -1,
137    -1,
138    -1,
139    -1,
140    -1,
141    -1,
142    -1,
143    -1,
144    -1,
145    -1,
146    -1,
147    -1,
148    -1,
149    -1,
150    -1,
151    -1,
152    -1,
153    -1,
154    -1,
155    -1,
156    -1,
157    -1,
158    -1,
159    -1,
160    -1,
161    -1,
162    -1,
163    -1,
164    -1,
165    -1,
166    -1,
167    -1,
168    -1,
169    -1,
170    -1,
171    -1,
172    -1,
173    -1,
174    -1,
175    -1,
176    -1,
177    -1,
178    -1,
179    -1,
180    -1,
181    -1,
182    -1,
183    -1,
184    -1,
185    -1,
186    -1,
187    -1,
188    -1,
189    -1,
190    -1,
191    -1,
192    -1,
193    -1,
194    -1,
195    -1,
196    -1,
197    -1,
198    -1,
199    -1,
200    -1,
201    -1,
202    -1,
203    -1,
204    -1,
205    -1,
206    -1,
207    -1,
208    -1,
209    -1,
210    -1,
211    -1,
212    -1,
213    -1,
214    -1,
215    -1,
216    -1,
217    -1,
218    -1,
219    -1,
220    -1,
221    -1,
222    -1,
223    -1,
224    -1,
225    -1,
226    -1,
227    -1,
228    -1,
229    -1,
230    -1,
231    -1,
232    -1,
233    -1,
234    -1,
235    -1,
236    -1,
237    -1,
238    -1,
239    -1,
240    -1,
241    -1,
242    -1,
243    -1,
244    -1,
245    -1,
246    -1,
247    -1,
248    -1,
249    -1,
250    -1,
251    -1,
252    -1,
253    -1,
254    -1,
255    -1,
256    -1,
257    -1,
258    -1,
259    -1,
260    -1,
261    -1,
262];
263
264/// Parses a VLQ segment into a vector.
265pub fn parse_vlq_segment(segment: &str) -> Result<Vec<i64>> {
266    let mut rv = vec![];
267
268    parse_vlq_segment_into(segment, &mut rv)?;
269
270    Ok(rv)
271}
272
273/// Parses a VLQ segment into a pre-allocated `Vec` instead of returning a new allocation.
274pub(crate) fn parse_vlq_segment_into(segment: &str, rv: &mut Vec<i64>) -> Result<()> {
275    let mut cur = 0;
276    let mut shift = 0;
277
278    for c in segment.bytes() {
279        let enc = i64::from(B64[c as usize]);
280        let val = enc & 0b11111;
281        let cont = enc >> 5;
282        cur += val.checked_shl(shift).ok_or(Error::VlqOverflow)?;
283        shift += 5;
284
285        if cont == 0 {
286            let sign = cur & 1;
287            cur >>= 1;
288            if sign != 0 {
289                cur = -cur;
290            }
291            rv.push(cur);
292            cur = 0;
293            shift = 0;
294        }
295    }
296
297    if cur != 0 || shift != 0 {
298        Err(Error::VlqLeftover)
299    } else if rv.is_empty() {
300        Err(Error::VlqNoValues)
301    } else {
302        Ok(())
303    }
304}
305
306/// Encodes a VLQ segment from a slice.
307pub fn generate_vlq_segment(nums: &[i64]) -> Result<String> {
308    let mut rv = String::new();
309    for &num in nums {
310        encode_vlq(&mut rv, num);
311    }
312    Ok(rv)
313}
314
315pub(crate) fn encode_vlq(out: &mut String, num: i64) {
316    let mut num = if num < 0 { ((-num) << 1) + 1 } else { num << 1 };
317
318    loop {
319        let mut digit = num & 0b11111;
320        num >>= 5;
321        if num > 0 {
322            digit |= 1 << 5;
323        }
324        out.push(B64_CHARS[digit as usize] as char);
325        if num == 0 {
326            break;
327        }
328    }
329}
330
331#[cfg(test)]
332mod tests {
333    use super::*;
334
335    #[test]
336    fn test_vlq_decode() {
337        let rv = parse_vlq_segment("AAAA").unwrap();
338        assert_eq!(rv, vec![0, 0, 0, 0]);
339        let rv = parse_vlq_segment("GAAIA").unwrap();
340        assert_eq!(rv, vec![3, 0, 0, 4, 0]);
341    }
342
343    #[test]
344    fn test_vlq_encode() {
345        let rv = generate_vlq_segment(&[0, 0, 0, 0]).unwrap();
346        assert_eq!(rv.as_str(), "AAAA");
347        let rv = generate_vlq_segment(&[3, 0, 0, 4, 0]).unwrap();
348        assert_eq!(rv.as_str(), "GAAIA");
349    }
350
351    #[test]
352    fn test_overflow() {
353        match parse_vlq_segment("00000000000000") {
354            Err(Error::VlqOverflow) => {}
355            e => {
356                panic!("Unexpeted result: {:?}", e);
357            }
358        }
359    }
360}
sourcemap/vlq.rs

sourcemap/
vlq.rs
