Skip to main content

arrow_avro/reader/
vlq.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use crate::errors::AvroError;
6
7/// Decoder for zig-zag encoded variable length (VLW) integers
8///
9/// See also:
10/// <https://avro.apache.org/docs/1.11.1/specification/#primitive-types-1>
11/// <https://protobuf.dev/programming-guides/encoding/#varints>
12#[derive(Debug, Default)]
13pub struct VLQDecoder {
14    /// Scratch space for decoding VLQ integers
15    in_progress: u64,
16    shift: u32,
17}
18
19impl VLQDecoder {
20    /// Decode a signed long from `buf`
21    ///
22    /// Returns `Err` if more than 10 continuation bytes accumulate across calls without a
23    /// terminator, which would otherwise overflow the accumulated `i64`.
24    pub fn long(&mut self, buf: &mut &[u8]) -> Result<Option<i64>, AvroError> {
25        while let Some(byte) = buf.first().copied() {
26            if self.shift == 63 && byte >= 0x02 {
27                self.in_progress = 0;
28                self.shift = 0;
29                return Err(AvroError::ParseError(
30                    "Malformed Avro varint: too many continuation bytes".to_string(),
31                ));
32            }
33            *buf = &buf[1..];
34            self.in_progress |= ((byte & 0x7F) as u64) << self.shift;
35            self.shift += 7;
36            if byte & 0x80 == 0 {
37                let val = self.in_progress;
38                self.in_progress = 0;
39                self.shift = 0;
40                return Ok(Some((val >> 1) as i64 ^ -((val & 1) as i64)));
41            }
42        }
43        Ok(None)
44    }
45}
46
47/// Read a varint from `buf` returning the decoded `u64` and the number of bytes read
48#[inline]
49pub(crate) fn read_varint(buf: &[u8]) -> Option<(u64, usize)> {
50    let first = *buf.first()?;
51    if first < 0x80 {
52        return Some((first as u64, 1));
53    }
54
55    if let Some(array) = buf.get(..10) {
56        return read_varint_array(array.try_into().unwrap());
57    }
58
59    read_varint_slow(buf)
60}
61
62/// Based on
63/// - <https://github.com/tokio-rs/prost/blob/master/prost/src/encoding/varint.rs#L71>
64/// - <https://github.com/google/protobuf/blob/3.3.x/src/google/protobuf/io/coded_stream.cc#L365-L406>
65/// - <https://github.com/protocolbuffers/protobuf-go/blob/v1.27.1/encoding/protowire/wire.go#L358>
66#[inline]
67fn read_varint_array(buf: [u8; 10]) -> Option<(u64, usize)> {
68    let mut in_progress = 0_u64;
69    for (idx, b) in buf.into_iter().take(9).enumerate() {
70        in_progress += (b as u64) << (7 * idx);
71        if b < 0x80 {
72            return Some((in_progress, idx + 1));
73        }
74        in_progress -= 0x80 << (7 * idx);
75    }
76
77    let b = buf[9] as u64;
78    in_progress += b << (7 * 9);
79    (b < 0x02).then_some((in_progress, 10))
80}
81
82#[inline(never)]
83#[cold]
84fn read_varint_slow(buf: &[u8]) -> Option<(u64, usize)> {
85    let mut value = 0;
86    for (count, _byte) in buf.iter().take(10).enumerate() {
87        let byte = buf[count];
88        value |= u64::from(byte & 0x7F) << (count * 7);
89        if byte <= 0x7F {
90            // Check for u64::MAX overflow. See [`ConsumeVarint`][1] for details.
91            // [1]: https://github.com/protocolbuffers/protobuf-go/blob/v1.27.1/encoding/protowire/wire.go#L358
92            return (count != 9 || byte < 2).then_some((value, count + 1));
93        }
94    }
95
96    None
97}
98
99pub(crate) fn skip_varint(buf: &[u8]) -> Option<usize> {
100    if let Some(array) = buf.get(..10) {
101        return skip_varint_array(array.try_into().unwrap());
102    }
103    skip_varint_slow(buf)
104}
105
106fn skip_varint_array(buf: [u8; 10]) -> Option<usize> {
107    // Using buf.into_iter().enumerate() regresses performance by 1% on x86-64
108    #[expect(clippy::needless_range_loop)]
109    for idx in 0..9 {
110        if buf[idx] < 0x80 {
111            return Some(idx + 1);
112        }
113    }
114    (buf[9] < 0x02).then_some(10)
115}
116
117#[cold]
118fn skip_varint_slow(buf: &[u8]) -> Option<usize> {
119    debug_assert!(
120        buf.len() < 10,
121        "should be only called on buffers too short for the fast path"
122    );
123    for (idx, &byte) in buf.iter().enumerate() {
124        if byte < 0x80 {
125            return Some(idx + 1);
126        }
127    }
128    None
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    fn encode_var(mut n: u64, dst: &mut [u8]) -> usize {
136        let mut i = 0;
137
138        while n >= 0x80 {
139            dst[i] = 0x80 | (n as u8);
140            i += 1;
141            n >>= 7;
142        }
143
144        dst[i] = n as u8;
145        i + 1
146    }
147
148    fn varint_test(a: u64) {
149        let mut buf = [0_u8; 10];
150        let len = encode_var(a, &mut buf);
151        assert_eq!(read_varint(&buf[..len]).unwrap(), (a, len));
152        assert_eq!(read_varint(&buf).unwrap(), (a, len));
153    }
154
155    #[test]
156    fn test_varint() {
157        varint_test(0);
158        varint_test(4395932);
159        varint_test(u64::MAX);
160
161        for _ in 0..1000 {
162            varint_test(rand::random());
163        }
164    }
165
166    fn zigzag_encode(n: i64) -> u64 {
167        ((n << 1) ^ (n >> 63)) as u64
168    }
169
170    fn long_test(n: i64) {
171        let mut buf = [0_u8; 10];
172        let len = encode_var(zigzag_encode(n), &mut buf);
173        let mut decoder = VLQDecoder::default();
174        let mut slice = &buf[..len];
175        assert_eq!(decoder.long(&mut slice).unwrap(), Some(n));
176        assert!(slice.is_empty());
177    }
178
179    #[test]
180    fn test_long_roundtrip() {
181        long_test(0);
182        long_test(1);
183        long_test(-1);
184        long_test(4395932);
185        long_test(-4395932);
186        long_test(i64::MAX);
187        long_test(i64::MIN);
188
189        for _ in 0..1000 {
190            long_test(rand::random());
191        }
192    }
193
194    #[test]
195    fn test_long_overlong_varint_returns_error() {
196        // The Avro file magic followed by 13 continuation bytes and a terminator, as
197        // reported against #10290: previously drove `self.shift` past 63 and panicked
198        // with "attempt to shift left with overflow" inside `<< self.shift`.
199        let overlong = [0xFFu8; 13];
200        let mut decoder = VLQDecoder::default();
201        let mut buf = &overlong[..];
202        assert!(decoder.long(&mut buf).is_err());
203
204        // The decoder's state must be reset after a malformed varint, so a subsequent
205        // call decodes a fresh varint cleanly rather than staying stuck mid-decode.
206        let mut fresh = &[0x02u8][..]; // zigzag-encoded 1
207        assert_eq!(decoder.long(&mut fresh).unwrap(), Some(1));
208    }
209}