oak_source_map/
vlq.rs

1//! VLQ Base64 encoding and decoding for Source Maps.
2//!
3//! VLQ (Variable Length Quantity) encoding is used in Source Map v3
4//! to compactly represent integers in the mappings string.
5
6use crate::{Result, SourceMapError};
7
8const BASE64_CHARS: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
9
10const BASE64_DECODE: [i8; 256] = {
11    let mut table = [-1i8; 256];
12    let mut i = 0;
13    while i < 64 {
14        table[BASE64_CHARS[i] as usize] = i as i8;
15        i += 1;
16    }
17    table
18};
19
20const VLQ_CONTINUATION_BIT: u8 = 0b100000;
21const VLQ_BASE_MASK: u8 = 0b011111;
22
23/// Encodes a signed integer to VLQ Base64 string.
24///
25/// # Example
26///
27/// ```
28/// use oak_source_map::vlq_encode;
29///
30/// assert_eq!(vlq_encode(0), "A");
31/// assert_eq!(vlq_encode(1), "C");
32/// assert_eq!(vlq_encode(-1), "D");
33/// assert_eq!(vlq_encode(16), "gB");
34/// assert_eq!(vlq_encode(12345), "uBtC");
35/// ```
36pub fn vlq_encode(value: i32) -> String {
37    let mut result = String::new();
38    let mut value = if value < 0 { ((-value) << 1) + 1 } else { value << 1 };
39
40    loop {
41        let mut digit = (value & VLQ_BASE_MASK as i32) as u8;
42        value >>= 5;
43
44        if value > 0 {
45            digit |= VLQ_CONTINUATION_BIT;
46        }
47
48        result.push(BASE64_CHARS[digit as usize] as char);
49
50        if value == 0 {
51            break;
52        }
53    }
54
55    result
56}
57
58/// Decodes a VLQ Base64 string to a signed integer.
59///
60/// # Example
61///
62/// ```
63/// use oak_source_map::vlq_decode;
64///
65/// assert_eq!(vlq_decode("A"), Ok((0, 1)));
66/// assert_eq!(vlq_decode("C"), Ok((1, 1)));
67/// assert_eq!(vlq_decode("D"), Ok((-1, 1)));
68/// assert_eq!(vlq_decode("gB"), Ok((16, 2)));
69/// ```
70pub fn vlq_decode(s: &str) -> Result<(i32, usize)> {
71    vlq_decode_from_slice(s.as_bytes())
72}
73
74/// Decodes VLQ from a byte slice.
75pub fn vlq_decode_from_slice(bytes: &[u8]) -> Result<(i32, usize)> {
76    let mut result: i32 = 0;
77    let mut shift: u32 = 0;
78    let mut count = 0;
79
80    for &byte in bytes {
81        count += 1;
82
83        let decoded = BASE64_DECODE[byte as usize];
84        if decoded < 0 {
85            return Err(SourceMapError::invalid_vlq(count - 1, format!("Invalid Base64 character: '{}'", byte as char)));
86        }
87
88        let decoded = decoded as u8;
89
90        result |= ((decoded & VLQ_BASE_MASK) as i32) << shift;
91        shift += 5;
92
93        if decoded & VLQ_CONTINUATION_BIT == 0 {
94            break;
95        }
96    }
97
98    let is_negative = result & 1 != 0;
99    result >>= 1;
100
101    if is_negative {
102        result = -result;
103    }
104
105    Ok((result, count))
106}
107
108/// Encodes multiple values into a VLQ string with separators.
109pub fn vlq_encode_many(values: &[i32]) -> String {
110    values.iter().map(|v| vlq_encode(*v)).collect()
111}
112
113/// Decodes multiple VLQ values from a string segment.
114pub fn vlq_decode_many(s: &str) -> Result<Vec<i32>> {
115    let bytes = s.as_bytes();
116    let mut pos = 0;
117    let mut result = Vec::new();
118
119    while pos < bytes.len() {
120        let (value, consumed) = vlq_decode_from_slice(&bytes[pos..])?;
121        result.push(value);
122        pos += consumed;
123    }
124
125    Ok(result)
126}
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    fn test_encode_zero() {
134        assert_eq!(vlq_encode(0), "A");
135    }
136
137    #[test]
138    fn test_encode_positive() {
139        assert_eq!(vlq_encode(1), "C");
140        assert_eq!(vlq_encode(2), "E");
141        assert_eq!(vlq_encode(15), "e");
142        assert_eq!(vlq_encode(16), "gB");
143        assert_eq!(vlq_encode(31), "+B");
144        assert_eq!(vlq_encode(32), "gC");
145    }
146
147    #[test]
148    fn test_encode_negative() {
149        assert_eq!(vlq_encode(-1), "D");
150        assert_eq!(vlq_encode(-2), "F");
151        assert_eq!(vlq_encode(-16), "hB");
152    }
153
154    #[test]
155    fn test_decode_zero() {
156        assert_eq!(vlq_decode("A"), Ok((0, 1)));
157    }
158
159    #[test]
160    fn test_decode_positive() {
161        assert_eq!(vlq_decode("C"), Ok((1, 1)));
162        assert_eq!(vlq_decode("gB"), Ok((16, 2)));
163    }
164
165    #[test]
166    fn test_decode_negative() {
167        assert_eq!(vlq_decode("D"), Ok((-1, 1)));
168        assert_eq!(vlq_decode("hB"), Ok((-16, 2)));
169    }
170
171    #[test]
172    fn test_roundtrip() {
173        for value in [-1000, -100, -10, -1, 0, 1, 10, 100, 1000, 12345] {
174            let encoded = vlq_encode(value);
175            let (decoded, _) = vlq_decode(&encoded).unwrap();
176            assert_eq!(decoded, value, "Failed for value {}", value);
177        }
178    }
179
180    #[test]
181    fn test_decode_many() {
182        let encoded = "AAAA";
183        let decoded = vlq_decode_many(encoded).unwrap();
184        assert_eq!(decoded, vec![0, 0, 0, 0]);
185    }
186
187    #[test]
188    fn test_encode_many() {
189        let values = vec![0, 1, 2, 3];
190        let encoded = vlq_encode_many(&values);
191        assert_eq!(encoded, "ACEG");
192    }
193}
oak_source_map/vlq.rs

oak_source_map/
vlq.rs
