md_codec/
varint.rs

1//! LP4-ext varint per spec §4.1.
2//!
3//! Encoding: [L: 4 bits][payload: L bits], with L=15 reserved as a
4//! continuation marker. When L=15: [L_high: 4 bits][payload_low: 14 bits]
5//! [payload_high: L_high bits], total payload bits = L_high + 14.
6
7use crate::bitstream::{BitReader, BitWriter};
8use crate::error::Error;
9
10/// Encode `value` as an LP4-ext varint into `writer`.
11///
12/// Returns `Err(Error::VarintOverflow)` if `value` exceeds the single-extension
13/// payload range (max `2^29 - 1`). Recursive extension is not implemented;
14/// callers must ensure values fit within the supported range.
15pub fn write_varint(writer: &mut BitWriter, value: u32) -> Result<(), Error> {
16    // Determine number of payload bits needed.
17    let bits_needed = if value == 0 {
18        0
19    } else {
20        32 - value.leading_zeros() as usize
21    };
22
23    if bits_needed <= 14 {
24        writer.write_bits(bits_needed as u64, 4);
25        writer.write_bits(value as u64, bits_needed);
26        Ok(())
27    } else {
28        // Extension form: L=15, then [L_high:4][payload_low:14][payload_high:L_high]
29        let l_high = bits_needed - 14;
30        if l_high > 15 {
31            return Err(Error::VarintOverflow { value });
32        }
33        writer.write_bits(15, 4);
34        writer.write_bits(l_high as u64, 4);
35        let low_mask = (1u64 << 14) - 1;
36        let payload_low = (value as u64) & low_mask;
37        let payload_high = (value as u64) >> 14;
38        writer.write_bits(payload_low, 14);
39        writer.write_bits(payload_high, l_high);
40        Ok(())
41    }
42}
43
44/// Decode an LP4-ext varint from `reader`.
45pub fn read_varint(reader: &mut BitReader) -> Result<u32, Error> {
46    let l = reader.read_bits(4)? as usize;
47    if l < 15 {
48        let value = reader.read_bits(l)? as u32;
49        Ok(value)
50    } else {
51        let l_high = reader.read_bits(4)? as usize;
52        let payload_low = reader.read_bits(14)? as u32;
53        let payload_high = reader.read_bits(l_high)? as u32;
54        Ok((payload_high << 14) | payload_low)
55    }
56}
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    fn round_trip(value: u32) {
63        let mut w = BitWriter::new();
64        write_varint(&mut w, value).unwrap();
65        let bytes = w.into_bytes();
66        let mut r = BitReader::new(&bytes);
67        assert_eq!(read_varint(&mut r).unwrap(), value);
68    }
69
70    #[test]
71    fn varint_zero() {
72        round_trip(0);
73    }
74
75    #[test]
76    fn varint_one() {
77        round_trip(1);
78    }
79
80    #[test]
81    fn varint_84() {
82        round_trip(84);
83    }
84
85    #[test]
86    fn varint_1024() {
87        round_trip(1024);
88    }
89
90    #[test]
91    fn varint_16383_no_extension() {
92        // 14-bit boundary; should NOT trigger extension
93        round_trip(16383);
94    }
95
96    #[test]
97    fn varint_16384_uses_extension() {
98        round_trip(16384);
99    }
100
101    #[test]
102    fn varint_max_u31() {
103        // Single-extension range: 14 + L_high (max 15) = 29 payload bits.
104        // Spec snippet labeled this "max_u31" but the wire format (4-bit L_high)
105        // caps single-extension payload at 29 bits.
106        round_trip((1u32 << 29) - 1);
107    }
108
109    #[test]
110    fn varint_zero_costs_4_bits() {
111        let mut w = BitWriter::new();
112        write_varint(&mut w, 0).unwrap();
113        assert_eq!(w.bit_len(), 4);
114    }
115
116    #[test]
117    fn varint_one_costs_5_bits() {
118        let mut w = BitWriter::new();
119        write_varint(&mut w, 1).unwrap();
120        assert_eq!(w.bit_len(), 5);
121    }
122
123    #[test]
124    fn varint_84_costs_11_bits() {
125        let mut w = BitWriter::new();
126        write_varint(&mut w, 84).unwrap();
127        assert_eq!(w.bit_len(), 11);
128    }
129
130    #[test]
131    fn varint_overflow_returns_error_instead_of_panicking() {
132        // 1 << 30 needs 30 payload bits; single-extension caps at 29.
133        let mut w = BitWriter::new();
134        let result = write_varint(&mut w, 1u32 << 30);
135        assert!(matches!(result, Err(Error::VarintOverflow { value }) if value == 1u32 << 30));
136    }
137
138    #[test]
139    fn varint_max_single_extension_succeeds() {
140        // (1 << 29) - 1 needs exactly 29 payload bits = 14 + 15. Should succeed.
141        let mut w = BitWriter::new();
142        write_varint(&mut w, (1u32 << 29) - 1).unwrap();
143    }
144
145    #[test]
146    fn varint_l_zero_decodes_to_zero_directly() {
147        // Hand-craft 4 bits of zero (L=0) directly in a byte stream;
148        // verify read_varint returns 0 without consuming additional bits.
149        let mut w = BitWriter::new();
150        w.write_bits(0b0000, 4); // L=0
151        w.write_bits(0b1010, 4); // arbitrary trailing bits to confirm we don't consume them
152        let bytes = w.into_bytes();
153        let mut r = BitReader::new(&bytes);
154        assert_eq!(read_varint(&mut r).unwrap(), 0);
155        // Verify exactly 4 bits were consumed.
156        assert_eq!(r.read_bits(4).unwrap(), 0b1010);
157    }
158}
md_codec/varint.rs

md_codec/
varint.rs
