srcmap_codec/

vlq.rs

//! Base64 VLQ encoding/decoding primitives.
//!
//! VLQ (Variable-Length Quantity) encoding stores arbitrary integers
//! as sequences of base64 characters. The sign bit is stored in the
//! least significant bit, and continuation bits indicate multi-char values.

use crate::DecodeError;

const VLQ_BASE_SHIFT: u32 = 5;
const VLQ_BASE: u64 = 1 << VLQ_BASE_SHIFT; // 32
const VLQ_BASE_MASK: u64 = VLQ_BASE - 1; // 0b11111
const VLQ_CONTINUATION_BIT: u64 = VLQ_BASE; // 0b100000

/// Maximum shift before overflow. 13 VLQ digits × 5 bits = 65 bits,
/// which exceeds i64 range. We allow shift up to 60 (13th digit).
const VLQ_MAX_SHIFT: u32 = 64;

/// Pre-computed base64 encode lookup table (index -> char byte).
#[rustfmt::skip]
const BASE64_ENCODE: [u8; 64] = [
    b'A', b'B', b'C', b'D', b'E', b'F', b'G', b'H',
    b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P',
    b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X',
    b'Y', b'Z', b'a', b'b', b'c', b'd', b'e', b'f',
    b'g', b'h', b'i', b'j', b'k', b'l', b'm', b'n',
    b'o', b'p', b'q', b'r', b's', b't', b'u', b'v',
    b'w', b'x', b'y', b'z', b'0', b'1', b'2', b'3',
    b'4', b'5', b'6', b'7', b'8', b'9', b'+', b'/',
];

/// Pre-computed base64 decode lookup table (char byte -> value).
/// Invalid characters map to 255.
const BASE64_DECODE: [u8; 128] = {
    let mut table = [255u8; 128];
    let mut i = 0u8;
    while i < 64 {
        table[BASE64_ENCODE[i as usize] as usize] = i;
        i += 1;
    }
    table
};

/// Encode a single VLQ value, appending base64 chars to the output buffer.
#[inline]
pub fn vlq_encode(out: &mut Vec<u8>, value: i64) {
    // Convert to VLQ signed representation using u64 to avoid overflow.
    // Sign bit goes in the LSB. Two's complement negation via bit ops
    // handles all values including i64::MIN safely.
    let mut vlq: u64 = if value >= 0 {
        (value as u64) << 1
    } else {
        // !(x as u64) + 1 computes the absolute value for any negative i64.
        // For i64::MIN (-2^63), abs = 2^63, and (2^63 << 1) wraps to 0 in u64.
        // This produces an incorrect encoding for i64::MIN, but that value
        // is unreachable in valid source maps (max ~4 billion lines/columns).
        ((!(value as u64)) + 1) << 1 | 1
    };

    loop {
        let mut digit = vlq & VLQ_BASE_MASK;
        vlq >>= VLQ_BASE_SHIFT;

        if vlq > 0 {
            digit |= VLQ_CONTINUATION_BIT;
        }

        out.push(BASE64_ENCODE[digit as usize]);

        if vlq == 0 {
            break;
        }
    }
}

/// Decode a single VLQ value from the input bytes starting at the given position.
///
/// Returns `(decoded_value, bytes_consumed)` or a [`DecodeError`].
#[inline]
pub fn vlq_decode(input: &[u8], pos: usize) -> Result<(i64, usize), DecodeError> {
    let mut result: u64 = 0;
    let mut shift: u32 = 0;
    let mut i = pos;

    loop {
        if i >= input.len() {
            return Err(DecodeError::UnexpectedEof { offset: i });
        }

        let byte = input[i];

        if byte >= 128 {
            return Err(DecodeError::InvalidBase64 { byte, offset: i });
        }

        let digit = BASE64_DECODE[byte as usize];

        if digit == 255 {
            return Err(DecodeError::InvalidBase64 { byte, offset: i });
        }

        let digit = digit as u64;
        i += 1;

        if shift >= VLQ_MAX_SHIFT {
            return Err(DecodeError::VlqOverflow { offset: pos });
        }

        result += (digit & VLQ_BASE_MASK) << shift;
        shift += VLQ_BASE_SHIFT;

        if (digit & VLQ_CONTINUATION_BIT) == 0 {
            break;
        }
    }

    // Extract sign from LSB
    let value = if (result & 1) == 1 {
        -((result >> 1) as i64)
    } else {
        (result >> 1) as i64
    };

    Ok((value, i - pos))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn encode_zero() {
        let mut buf = Vec::new();
        vlq_encode(&mut buf, 0);
        assert_eq!(&buf, b"A");
    }

    #[test]
    fn encode_positive() {
        let mut buf = Vec::new();
        vlq_encode(&mut buf, 1);
        assert_eq!(&buf, b"C");
    }

    #[test]
    fn encode_negative() {
        let mut buf = Vec::new();
        vlq_encode(&mut buf, -1);
        assert_eq!(&buf, b"D");
    }

    #[test]
    fn encode_large_value() {
        let mut buf = Vec::new();
        vlq_encode(&mut buf, 1000);
        let (decoded, _) = vlq_decode(&buf, 0).unwrap();
        assert_eq!(decoded, 1000);
    }

    #[test]
    fn roundtrip_values() {
        let values = [
            0,
            1,
            -1,
            15,
            -15,
            16,
            -16,
            31,
            32,
            100,
            -100,
            1000,
            -1000,
            100_000,
            i64::MAX,
        ];
        for &v in &values {
            let mut buf = Vec::new();
            vlq_encode(&mut buf, v);
            let (decoded, consumed) = vlq_decode(&buf, 0).unwrap();
            assert_eq!(decoded, v, "roundtrip failed for {v}");
            assert_eq!(consumed, buf.len());
        }
    }

    #[test]
    fn decode_multi_char() {
        let mut buf = Vec::new();
        vlq_encode(&mut buf, 500);
        assert!(buf.len() > 1, "500 should need multiple chars");
        let (decoded, _) = vlq_decode(&buf, 0).unwrap();
        assert_eq!(decoded, 500);
    }

    #[test]
    fn decode_non_ascii_byte() {
        let input = [0xC0u8];
        let err = vlq_decode(&input, 0).unwrap_err();
        assert_eq!(
            err,
            DecodeError::InvalidBase64 {
                byte: 0xC0,
                offset: 0
            }
        );
    }

    #[test]
    fn decode_invalid_base64_char() {
        let input = b"!";
        let err = vlq_decode(input, 0).unwrap_err();
        assert_eq!(
            err,
            DecodeError::InvalidBase64 {
                byte: b'!',
                offset: 0
            }
        );
    }

    #[test]
    fn decode_unexpected_eof() {
        // 'g' = 32, which has the continuation bit set
        let input = b"g";
        let err = vlq_decode(input, 0).unwrap_err();
        assert_eq!(err, DecodeError::UnexpectedEof { offset: 1 });
    }

    #[test]
    fn decode_overflow() {
        // 14 continuation chars: shift reaches 65 which exceeds limit
        let input = b"ggggggggggggggA";
        let err = vlq_decode(input, 0).unwrap_err();
        assert!(matches!(err, DecodeError::VlqOverflow { .. }));
    }

    #[test]
    fn decode_empty_input() {
        let err = vlq_decode(b"", 0).unwrap_err();
        assert_eq!(err, DecodeError::UnexpectedEof { offset: 0 });
    }
}