baedeker_core/binary/
leb128.rs

1// Copyright (C) 2026 Industrial Algebra
2// SPDX-License-Identifier: Apache-2.0
3
4//! LEB128 (Little Endian Base 128) encoder/decoder.
5//!
6//! WASM uses LEB128 extensively for compact integer encoding in the binary format.
7//! See [Spec §5.2.2](https://webassembly.github.io/spec/core/binary/values.html#integers).
8
9use crate::error::{ByteOffset, DecodeContext, DecodeError, DecodeErrorKind};
10
11/// A cursor over a byte slice, tracking the current read position.
12#[derive(Debug)]
13pub struct Cursor<'a> {
14    data: &'a [u8],
15    pos: usize,
16}
17
18impl<'a> Cursor<'a> {
19    /// Create a new cursor at position 0.
20    pub fn new(data: &'a [u8]) -> Self {
21        Self { data, pos: 0 }
22    }
23
24    /// Current byte offset.
25    pub fn position(&self) -> usize {
26        self.pos
27    }
28
29    /// Remaining bytes.
30    pub fn remaining(&self) -> &'a [u8] {
31        &self.data[self.pos..]
32    }
33
34    /// Pre-allocation capacity for `count` entries yet to be parsed.
35    ///
36    /// Malformed binaries can declare counts in the billions; blindly
37    /// trusting them in `Vec::with_capacity` turns a tiny input into a
38    /// multi-gigabyte allocation. Every entry needs at least one byte in
39    /// the stream, so the remaining input length is a sound upper bound.
40    pub fn capacity_hint(&self, count: u32) -> usize {
41        (count as usize).min(self.remaining().len())
42    }
43
44    /// Original backing slice.
45    pub fn original(&self) -> &'a [u8] {
46        self.data
47    }
48
49    /// Whether we've consumed all input.
50    pub fn is_empty(&self) -> bool {
51        self.pos >= self.data.len()
52    }
53
54    /// Read a single byte, advancing the cursor.
55    pub fn read_byte(&mut self) -> Result<u8, DecodeError> {
56        if self.pos < self.data.len() {
57            let b = self.data[self.pos];
58            self.pos += 1;
59            Ok(b)
60        } else {
61            Err(DecodeError {
62                offset: ByteOffset(self.pos),
63                context: DecodeContext::Leb128,
64                kind: DecodeErrorKind::UnexpectedEof,
65            })
66        }
67    }
68
69    /// Read exactly `n` bytes as a slice, advancing the cursor.
70    pub fn read_bytes(&mut self, n: usize) -> Result<&'a [u8], DecodeError> {
71        if self.pos + n <= self.data.len() {
72            let slice = &self.data[self.pos..self.pos + n];
73            self.pos += n;
74            Ok(slice)
75        } else {
76            Err(DecodeError {
77                offset: ByteOffset(self.pos),
78                context: DecodeContext::Leb128,
79                kind: DecodeErrorKind::UnexpectedEof,
80            })
81        }
82    }
83
84    /// Advance the cursor by `n` bytes.
85    pub fn advance(&mut self, n: usize) -> Result<(), DecodeError> {
86        if self.pos + n <= self.data.len() {
87            self.pos += n;
88            Ok(())
89        } else {
90            Err(DecodeError {
91                offset: ByteOffset(self.pos),
92                context: DecodeContext::Leb128,
93                kind: DecodeErrorKind::UnexpectedEof,
94            })
95        }
96    }
97}
98
99/// Decode an unsigned LEB128-encoded u32.
100///
101/// The encoding uses at most 5 bytes. The final byte's unused high bits
102/// must be zero (no overlong encodings).
103/// See [Spec §5.2.2](https://webassembly.github.io/spec/core/binary/values.html#integers).
104pub fn decode_u32(cursor: &mut Cursor<'_>) -> Result<u32, DecodeError> {
105    let start = cursor.position();
106    let mut result: u32 = 0;
107    let mut shift: u32 = 0;
108
109    for i in 0..5 {
110        let byte = cursor.read_byte().map_err(|mut e| {
111            e.context = DecodeContext::Leb128;
112            e.offset = ByteOffset(start);
113            e
114        })?;
115
116        let low_bits = u32::from(byte & 0x7F);
117
118        // Check for overflow on the 5th byte (shift=28): only 4 low bits are valid.
119        if i == 4 && (byte & 0xF0) != 0 {
120            return Err(DecodeError {
121                offset: ByteOffset(start),
122                context: DecodeContext::Leb128,
123                kind: DecodeErrorKind::Leb128Overflow,
124            });
125        }
126
127        result |= low_bits << shift;
128
129        if byte & 0x80 == 0 {
130            return Ok(result);
131        }
132
133        shift += 7;
134    }
135
136    Err(DecodeError {
137        offset: ByteOffset(start),
138        context: DecodeContext::Leb128,
139        kind: DecodeErrorKind::Leb128TooLong,
140    })
141}
142
143/// Decode an unsigned LEB128-encoded u64.
144///
145/// The encoding uses at most 10 bytes.
146pub fn decode_u64(cursor: &mut Cursor<'_>) -> Result<u64, DecodeError> {
147    let start = cursor.position();
148    let mut result: u64 = 0;
149    let mut shift: u32 = 0;
150
151    for i in 0..10 {
152        let byte = cursor.read_byte().map_err(|mut e| {
153            e.context = DecodeContext::Leb128;
154            e.offset = ByteOffset(start);
155            e
156        })?;
157
158        let low_bits = u64::from(byte & 0x7F);
159
160        // 10th byte (shift=63): only 1 low bit is valid.
161        if i == 9 && (byte & 0xFE) != 0 {
162            return Err(DecodeError {
163                offset: ByteOffset(start),
164                context: DecodeContext::Leb128,
165                kind: DecodeErrorKind::Leb128Overflow,
166            });
167        }
168
169        result |= low_bits << shift;
170
171        if byte & 0x80 == 0 {
172            return Ok(result);
173        }
174
175        shift += 7;
176    }
177
178    Err(DecodeError {
179        offset: ByteOffset(start),
180        context: DecodeContext::Leb128,
181        kind: DecodeErrorKind::Leb128TooLong,
182    })
183}
184
185/// Decode a signed LEB128-encoded i32.
186///
187/// The encoding uses at most 5 bytes. Sign extension is applied based on
188/// the sign bit of the final byte.
189pub fn decode_i32(cursor: &mut Cursor<'_>) -> Result<i32, DecodeError> {
190    let start = cursor.position();
191    let mut result: i32 = 0;
192    let mut shift: u32 = 0;
193
194    for i in 0..5 {
195        let byte = cursor.read_byte().map_err(|mut e| {
196            e.context = DecodeContext::Leb128;
197            e.offset = ByteOffset(start);
198            e
199        })?;
200
201        let low_bits = i32::from(byte & 0x7F);
202        result |= low_bits << shift;
203        shift += 7;
204
205        if byte & 0x80 == 0 {
206            // On the final byte, check that the unused high bits are consistent
207            // with the sign bit (either all 0s or all 1s).
208            if i == 4 {
209                // 5th byte at shift=28: bits 0-3 carry data (bit 3 = the
210                // i32 sign bit); bits 4-6 must sign-extend bit 3 exactly.
211                let sign = byte & 0x08;
212                let extension = byte & 0x70;
213                if (sign == 0 && extension != 0) || (sign != 0 && extension != 0x70) {
214                    return Err(DecodeError {
215                        offset: ByteOffset(start),
216                        context: DecodeContext::Leb128,
217                        kind: DecodeErrorKind::Leb128Overflow,
218                    });
219                }
220            } else if shift < 32 && (byte & 0x40) != 0 {
221                // Sign-extend negative values.
222                result |= !0 << shift;
223            }
224            return Ok(result);
225        }
226    }
227
228    Err(DecodeError {
229        offset: ByteOffset(start),
230        context: DecodeContext::Leb128,
231        kind: DecodeErrorKind::Leb128TooLong,
232    })
233}
234
235/// Decode a signed LEB128-encoded i64.
236///
237/// The encoding uses at most 10 bytes.
238pub fn decode_i64(cursor: &mut Cursor<'_>) -> Result<i64, DecodeError> {
239    let start = cursor.position();
240    let mut result: i64 = 0;
241    let mut shift: u32 = 0;
242
243    for i in 0..10 {
244        let byte = cursor.read_byte().map_err(|mut e| {
245            e.context = DecodeContext::Leb128;
246            e.offset = ByteOffset(start);
247            e
248        })?;
249
250        let low_bits = i64::from(byte & 0x7F);
251        result |= low_bits << shift;
252        shift += 7;
253
254        if byte & 0x80 == 0 {
255            if i == 9 {
256                // 10th byte at shift=63: bit 0 carries data (the i64 sign
257                // bit); bits 1-6 must sign-extend bit 0 exactly.
258                let sign = byte & 0x01;
259                let extension = byte & 0x7E;
260                if (sign == 0 && extension != 0) || (sign != 0 && extension != 0x7E) {
261                    return Err(DecodeError {
262                        offset: ByteOffset(start),
263                        context: DecodeContext::Leb128,
264                        kind: DecodeErrorKind::Leb128Overflow,
265                    });
266                }
267            } else if shift < 64 && (byte & 0x40) != 0 {
268                result |= !0i64 << shift;
269            }
270            return Ok(result);
271        }
272    }
273
274    Err(DecodeError {
275        offset: ByteOffset(start),
276        context: DecodeContext::Leb128,
277        kind: DecodeErrorKind::Leb128TooLong,
278    })
279}
280
281#[cfg(test)]
282mod tests {
283    use super::*;
284
285    // ── decode_u32 ──────────────────────────────────────────
286
287    #[test]
288    fn u32_zero() {
289        let mut c = Cursor::new(&[0x00]);
290        assert_eq!(decode_u32(&mut c).unwrap(), 0);
291    }
292
293    #[test]
294    fn u32_single_byte() {
295        let mut c = Cursor::new(&[0x08]);
296        assert_eq!(decode_u32(&mut c).unwrap(), 8);
297    }
298
299    #[test]
300    fn u32_max_single_byte() {
301        // 127 = 0x7F
302        let mut c = Cursor::new(&[0x7F]);
303        assert_eq!(decode_u32(&mut c).unwrap(), 127);
304    }
305
306    #[test]
307    fn u32_two_bytes() {
308        // 128 = 0x80 0x01
309        let mut c = Cursor::new(&[0x80, 0x01]);
310        assert_eq!(decode_u32(&mut c).unwrap(), 128);
311    }
312
313    #[test]
314    fn u32_624485() {
315        // Classic LEB128 test value: 624485 = 0xE5 0x8E 0x26
316        let mut c = Cursor::new(&[0xE5, 0x8E, 0x26]);
317        assert_eq!(decode_u32(&mut c).unwrap(), 624485);
318    }
319
320    #[test]
321    fn u32_max_value() {
322        // u32::MAX = 4294967295 = 0xFF 0xFF 0xFF 0xFF 0x0F
323        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0x0F]);
324        assert_eq!(decode_u32(&mut c).unwrap(), u32::MAX);
325    }
326
327    #[test]
328    fn u32_overflow_fifth_byte() {
329        // 5th byte has bit 4 set → overflow
330        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0x1F]);
331        let err = decode_u32(&mut c).unwrap_err();
332        assert_eq!(err.kind, DecodeErrorKind::Leb128Overflow);
333    }
334
335    #[test]
336    fn u32_too_long() {
337        // 6 continuation bytes
338        let mut c = Cursor::new(&[0x80, 0x80, 0x80, 0x80, 0x80, 0x00]);
339        let err = decode_u32(&mut c).unwrap_err();
340        assert_eq!(err.kind, DecodeErrorKind::Leb128Overflow);
341    }
342
343    #[test]
344    fn u32_unexpected_eof() {
345        let mut c = Cursor::new(&[0x80]);
346        let err = decode_u32(&mut c).unwrap_err();
347        assert_eq!(err.kind, DecodeErrorKind::UnexpectedEof);
348    }
349
350    // ── decode_i32 ──────────────────────────────────────────
351
352    #[test]
353    fn i32_zero() {
354        let mut c = Cursor::new(&[0x00]);
355        assert_eq!(decode_i32(&mut c).unwrap(), 0);
356    }
357
358    #[test]
359    fn i32_positive() {
360        let mut c = Cursor::new(&[0x08]);
361        assert_eq!(decode_i32(&mut c).unwrap(), 8);
362    }
363
364    #[test]
365    fn i32_negative_one() {
366        // -1 = 0x7F (sign bit set, single byte)
367        let mut c = Cursor::new(&[0x7F]);
368        assert_eq!(decode_i32(&mut c).unwrap(), -1);
369    }
370
371    #[test]
372    fn i32_negative_two() {
373        // -2 = 0x7E
374        let mut c = Cursor::new(&[0x7E]);
375        assert_eq!(decode_i32(&mut c).unwrap(), -2);
376    }
377
378    #[test]
379    fn i32_negative_128() {
380        // -128 = 0x80 0x7F
381        let mut c = Cursor::new(&[0x80, 0x7F]);
382        assert_eq!(decode_i32(&mut c).unwrap(), -128);
383    }
384
385    #[test]
386    fn i32_min_value() {
387        // i32::MIN = -2147483648 = 0x80 0x80 0x80 0x80 0x78
388        let mut c = Cursor::new(&[0x80, 0x80, 0x80, 0x80, 0x78]);
389        assert_eq!(decode_i32(&mut c).unwrap(), i32::MIN);
390    }
391
392    #[test]
393    fn i32_max_value() {
394        // i32::MAX = 2147483647 = 0xFF 0xFF 0xFF 0xFF 0x07
395        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0x07]);
396        assert_eq!(decode_i32(&mut c).unwrap(), i32::MAX);
397    }
398
399    // ── decode_u64 ──────────────────────────────────────────
400
401    #[test]
402    fn u64_zero() {
403        let mut c = Cursor::new(&[0x00]);
404        assert_eq!(decode_u64(&mut c).unwrap(), 0);
405    }
406
407    #[test]
408    fn u64_max_value() {
409        // u64::MAX = 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0x01
410        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01]);
411        assert_eq!(decode_u64(&mut c).unwrap(), u64::MAX);
412    }
413
414    #[test]
415    fn u64_overflow() {
416        // 10th byte has extra bits set
417        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x03]);
418        let err = decode_u64(&mut c).unwrap_err();
419        assert_eq!(err.kind, DecodeErrorKind::Leb128Overflow);
420    }
421
422    // ── decode_i64 ──────────────────────────────────────────
423
424    #[test]
425    fn i64_negative_one() {
426        let mut c = Cursor::new(&[0x7F]);
427        assert_eq!(decode_i64(&mut c).unwrap(), -1i64);
428    }
429
430    #[test]
431    fn i64_min_value() {
432        // i64::MIN encoded as signed LEB128
433        let mut c = Cursor::new(&[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x7F]);
434        assert_eq!(decode_i64(&mut c).unwrap(), i64::MIN);
435    }
436
437    #[test]
438    fn i64_max_value() {
439        // i64::MAX encoded as signed LEB128
440        let mut c = Cursor::new(&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00]);
441        assert_eq!(decode_i64(&mut c).unwrap(), i64::MAX);
442    }
443
444    // ── cursor ──────────────────────────────────────────────
445
446    #[test]
447    fn cursor_tracks_position() {
448        let mut c = Cursor::new(&[0x01, 0x02, 0x03]);
449        assert_eq!(c.position(), 0);
450        c.read_byte().unwrap();
451        assert_eq!(c.position(), 1);
452        c.read_bytes(2).unwrap();
453        assert_eq!(c.position(), 3);
454        assert!(c.is_empty());
455    }
456}
baedeker_core/binary/leb128.rs

baedeker_core/binary/
leb128.rs
