gimli/
leb128.rs

1//! Read and write DWARF's "Little Endian Base 128" (LEB128) variable length
2//! integer encoding.
3//!
4//! Read and write signed integers:
5//!
6//! ```
7//! # #[cfg(all(feature = "read", feature = "write", feature = "std"))] {
8//! use gimli::{EndianSlice, NativeEndian, leb128};
9//!
10//! let mut buf = [0; 1024];
11//!
12//! // Write to anything that implements `std::io::Write`.
13//! {
14//!     let mut writable = &mut buf[..];
15//!     leb128::write::signed(&mut writable, -12345).expect("Should write number");
16//! }
17//!
18//! // Read from anything that implements `gimli::Reader`.
19//! let mut readable = EndianSlice::new(&buf[..], NativeEndian);
20//! let val = leb128::read::signed(&mut readable).expect("Should read number");
21//! assert_eq!(val, -12345);
22//! # }
23//! ```
24//!
25//! Or read and write unsigned integers:
26//!
27//! ```
28//! # #[cfg(all(feature = "read", feature = "write", feature = "std"))] {
29//! use gimli::{EndianSlice, NativeEndian, leb128};
30//!
31//! let mut buf = [0; 1024];
32//!
33//! {
34//!     let mut writable = &mut buf[..];
35//!     leb128::write::unsigned(&mut writable, 98765).expect("Should write number");
36//! }
37//!
38//! let mut readable = EndianSlice::new(&buf[..], NativeEndian);
39//! let val = leb128::read::unsigned(&mut readable).expect("Should read number");
40//! assert_eq!(val, 98765);
41//! # }
42//! ```
43
44const CONTINUATION_BIT: u8 = 1 << 7;
45#[cfg(feature = "read-core")]
46const SIGN_BIT: u8 = 1 << 6;
47
48#[inline]
49fn low_bits_of_byte(byte: u8) -> u8 {
50    byte & !CONTINUATION_BIT
51}
52
53#[inline]
54#[allow(dead_code)]
55fn low_bits_of_u64(val: u64) -> u8 {
56    let byte = val & u64::from(u8::MAX);
57    low_bits_of_byte(byte as u8)
58}
59
60/// A module for reading signed and unsigned integers that have been LEB128
61/// encoded.
62#[cfg(feature = "read-core")]
63pub mod read {
64    use super::{CONTINUATION_BIT, SIGN_BIT, low_bits_of_byte};
65    use crate::read::{Error, Reader, Result};
66
67    /// Read bytes until the LEB128 continuation bit is not set.
68    pub fn skip<R: Reader>(r: &mut R) -> Result<()> {
69        loop {
70            let byte = r.read_u8()?;
71            if byte & CONTINUATION_BIT == 0 {
72                return Ok(());
73            }
74        }
75    }
76
77    /// Read an unsigned LEB128 number from the given `Reader` and
78    /// return it or an error if reading failed.
79    pub fn unsigned<R: Reader>(r: &mut R) -> Result<u64> {
80        // The first iteration of this loop is unpeeled for better code
81        // gen for the statistically likely case of single byte values.
82        let byte = r.read_u8()?;
83        if byte & CONTINUATION_BIT == 0 {
84            return Ok(u64::from(byte));
85        }
86        let mut result = u64::from(low_bits_of_byte(byte));
87        let mut shift = 7;
88
89        loop {
90            let byte = r.read_u8()?;
91            if shift == 63 && byte != 0x00 && byte != 0x01 {
92                return Err(Error::BadUnsignedLeb128);
93            }
94
95            let low_bits = u64::from(low_bits_of_byte(byte));
96            result |= low_bits << shift;
97
98            if byte & CONTINUATION_BIT == 0 {
99                return Ok(result);
100            }
101
102            shift += 7;
103        }
104    }
105
106    /// Read an LEB128 u16 from the given `Reader` and
107    /// return it or an error if reading failed.
108    pub fn u16<R: Reader>(r: &mut R) -> Result<u16> {
109        let byte = r.read_u8()?;
110        if byte & CONTINUATION_BIT == 0 {
111            return Ok(u16::from(byte));
112        }
113
114        let mut result = u16::from(low_bits_of_byte(byte));
115        let byte = r.read_u8()?;
116        result |= u16::from(low_bits_of_byte(byte)) << 7;
117        if byte & CONTINUATION_BIT == 0 {
118            return Ok(result);
119        }
120
121        let byte = r.read_u8()?;
122        if byte > 0x03 {
123            return Err(Error::BadUnsignedLeb128);
124        }
125        result += u16::from(byte) << 14;
126        Ok(result)
127    }
128
129    /// Read a signed LEB128 number from the given `Reader` and
130    /// return it or an error if reading failed.
131    pub fn signed<R: Reader>(r: &mut R) -> Result<i64> {
132        let mut result = 0;
133        let mut shift = 0;
134        let size = 64;
135        let mut byte;
136
137        loop {
138            byte = r.read_u8()?;
139            if shift == 63 && byte != 0x00 && byte != 0x7f {
140                return Err(Error::BadSignedLeb128);
141            }
142
143            let low_bits = i64::from(low_bits_of_byte(byte));
144            result |= low_bits << shift;
145            shift += 7;
146
147            if byte & CONTINUATION_BIT == 0 {
148                break;
149            }
150        }
151
152        if shift < size && (SIGN_BIT & byte) == SIGN_BIT {
153            // Sign extend the result.
154            result |= !0 << shift;
155        }
156
157        Ok(result)
158    }
159}
160
161/// A module for writing integers encoded as LEB128.
162pub mod write {
163    use super::{CONTINUATION_BIT, low_bits_of_u64};
164
165    /// An encoded LEB128 value.
166    ///
167    /// May be signed or unsigned.
168    #[derive(Debug, Clone, Copy)]
169    pub struct Leb128 {
170        bytes: [u8; 10],
171        len: u8,
172    }
173
174    impl Leb128 {
175        /// Return the bytes for the encoded value.
176        pub fn bytes(&self) -> &[u8] {
177            &self.bytes[..self.len as usize]
178        }
179
180        /// Return the length of the encoded bytes.
181        #[allow(clippy::len_without_is_empty)]
182        pub fn len(&self) -> usize {
183            self.len as usize
184        }
185
186        /// Generate the LEB128 encoding for the given unsigned number.
187        pub fn unsigned(mut val: u64) -> Self {
188            let mut bytes = [0; 10];
189            let mut len = 0;
190            loop {
191                let mut byte = low_bits_of_u64(val);
192                val >>= 7;
193                if val != 0 {
194                    // More bytes to come, so set the continuation bit.
195                    byte |= CONTINUATION_BIT;
196                }
197
198                bytes[len] = byte;
199                len += 1;
200
201                if val == 0 {
202                    return Leb128 {
203                        bytes,
204                        len: len as u8,
205                    };
206                }
207            }
208        }
209
210        /// Generate the LEB128 encoding for the given signed number.
211        pub fn signed(mut val: i64) -> Self {
212            let mut bytes = [0; 10];
213            let mut len = 0;
214            loop {
215                let mut byte = val as u8;
216                // Keep the sign bit for testing
217                val >>= 6;
218                let done = val == 0 || val == -1;
219                if done {
220                    byte &= !CONTINUATION_BIT;
221                } else {
222                    // Remove the sign bit
223                    val >>= 1;
224                    // More bytes to come, so set the continuation bit.
225                    byte |= CONTINUATION_BIT;
226                }
227
228                bytes[len] = byte;
229                len += 1;
230
231                if done {
232                    return Leb128 {
233                        bytes,
234                        len: len as u8,
235                    };
236                }
237            }
238        }
239
240        /// Write the bytes.
241        ///
242        /// Returns the written length.
243        #[cfg(feature = "std")]
244        pub fn write<W: std::io::Write>(&self, w: &mut W) -> std::io::Result<usize> {
245            w.write_all(self.bytes())?;
246            Ok(self.len())
247        }
248    }
249
250    /// Write the given unsigned number using the LEB128 encoding to the given
251    /// `std::io::Write`able. Returns the number of bytes written to `w`, or an
252    /// error if writing failed.
253    #[cfg(feature = "std")]
254    pub fn unsigned<W>(w: &mut W, val: u64) -> Result<usize, std::io::Error>
255    where
256        W: std::io::Write,
257    {
258        Leb128::unsigned(val).write(w)
259    }
260
261    /// Return the size of the LEB128 encoding of the given unsigned number.
262    pub fn uleb128_size(mut val: u64) -> usize {
263        let mut size = 0;
264        loop {
265            val >>= 7;
266            size += 1;
267            if val == 0 {
268                return size;
269            }
270        }
271    }
272
273    /// Write the given signed number using the LEB128 encoding to the given
274    /// `std::io::Write`able. Returns the number of bytes written to `w`, or an
275    /// error if writing failed.
276    #[cfg(feature = "std")]
277    pub fn signed<W>(w: &mut W, val: i64) -> Result<usize, std::io::Error>
278    where
279        W: std::io::Write,
280    {
281        Leb128::signed(val).write(w)
282    }
283
284    /// Return the size of the LEB128 encoding of the given signed number.
285    pub fn sleb128_size(mut val: i64) -> usize {
286        let mut size = 0;
287        loop {
288            val >>= 6;
289            let done = val == 0 || val == -1;
290            val >>= 1;
291            size += 1;
292            if done {
293                return size;
294            }
295        }
296    }
297}
298
299#[cfg(test)]
300#[cfg(all(feature = "read", feature = "write"))]
301mod tests {
302    use super::{CONTINUATION_BIT, low_bits_of_byte, low_bits_of_u64, read, write};
303    use crate::endianity::NativeEndian;
304    use crate::read::{EndianSlice, Error, ReaderOffsetId};
305    use alloc::vec::Vec;
306
307    trait ResultExt {
308        fn map_eof(self, input: &[u8]) -> Self;
309    }
310
311    impl<T> ResultExt for Result<T, Error> {
312        fn map_eof(self, input: &[u8]) -> Self {
313            match self {
314                Err(Error::UnexpectedEof(id)) => {
315                    let id = ReaderOffsetId(id.0 - input.as_ptr() as u64);
316                    Err(Error::UnexpectedEof(id))
317                }
318                r => r,
319            }
320        }
321    }
322
323    #[test]
324    fn test_low_bits_of_byte() {
325        for i in 0..127 {
326            assert_eq!(i, low_bits_of_byte(i));
327            assert_eq!(i, low_bits_of_byte(i | CONTINUATION_BIT));
328        }
329    }
330
331    #[test]
332    fn test_low_bits_of_u64() {
333        for i in 0u64..127 {
334            assert_eq!(i as u8, low_bits_of_u64(1 << 16 | i));
335            assert_eq!(
336                i as u8,
337                low_bits_of_u64(i << 16 | i | (u64::from(CONTINUATION_BIT)))
338            );
339        }
340    }
341
342    // Examples from the DWARF 4 standard, section 7.6, figure 22.
343    #[test]
344    fn test_read_unsigned() {
345        let buf = [2u8];
346        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
347        assert_eq!(
348            2,
349            read::unsigned(&mut readable).expect("Should read number")
350        );
351
352        let buf = [127u8];
353        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
354        assert_eq!(
355            127,
356            read::unsigned(&mut readable).expect("Should read number")
357        );
358
359        let buf = [CONTINUATION_BIT, 1];
360        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
361        assert_eq!(
362            128,
363            read::unsigned(&mut readable).expect("Should read number")
364        );
365
366        let buf = [1u8 | CONTINUATION_BIT, 1];
367        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
368        assert_eq!(
369            129,
370            read::unsigned(&mut readable).expect("Should read number")
371        );
372
373        let buf = [2u8 | CONTINUATION_BIT, 1];
374        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
375        assert_eq!(
376            130,
377            read::unsigned(&mut readable).expect("Should read number")
378        );
379
380        let buf = [57u8 | CONTINUATION_BIT, 100];
381        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
382        assert_eq!(
383            12857,
384            read::unsigned(&mut readable).expect("Should read number")
385        );
386    }
387
388    #[test]
389    fn test_read_unsigned_invalid() {
390        let buf = &[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 2][..];
391        let mut readable = EndianSlice::new(buf, NativeEndian);
392        let err = read::unsigned(&mut readable).unwrap_err();
393        assert!(matches!(err, Error::BadUnsignedLeb128), "{}", err);
394    }
395
396    // Examples from the DWARF 4 standard, section 7.6, figure 23.
397    #[test]
398    fn test_read_signed() {
399        let buf = [2u8];
400        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
401        assert_eq!(2, read::signed(&mut readable).expect("Should read number"));
402
403        let buf = [0x7eu8];
404        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
405        assert_eq!(-2, read::signed(&mut readable).expect("Should read number"));
406
407        let buf = [127u8 | CONTINUATION_BIT, 0];
408        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
409        assert_eq!(
410            127,
411            read::signed(&mut readable).expect("Should read number")
412        );
413
414        let buf = [1u8 | CONTINUATION_BIT, 0x7f];
415        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
416        assert_eq!(
417            -127,
418            read::signed(&mut readable).expect("Should read number")
419        );
420
421        let buf = [CONTINUATION_BIT, 1];
422        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
423        assert_eq!(
424            128,
425            read::signed(&mut readable).expect("Should read number")
426        );
427
428        let buf = [CONTINUATION_BIT, 0x7f];
429        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
430        assert_eq!(
431            -128,
432            read::signed(&mut readable).expect("Should read number")
433        );
434
435        let buf = [1u8 | CONTINUATION_BIT, 1];
436        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
437        assert_eq!(
438            129,
439            read::signed(&mut readable).expect("Should read number")
440        );
441
442        let buf = [0x7fu8 | CONTINUATION_BIT, 0x7e];
443        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
444        assert_eq!(
445            -129,
446            read::signed(&mut readable).expect("Should read number")
447        );
448    }
449
450    #[test]
451    fn test_read_signed_63_bits() {
452        let buf = [
453            CONTINUATION_BIT,
454            CONTINUATION_BIT,
455            CONTINUATION_BIT,
456            CONTINUATION_BIT,
457            CONTINUATION_BIT,
458            CONTINUATION_BIT,
459            CONTINUATION_BIT,
460            CONTINUATION_BIT,
461            0x40,
462        ];
463        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
464        assert_eq!(
465            -0x4000_0000_0000_0000,
466            read::signed(&mut readable).expect("Should read number")
467        );
468    }
469
470    #[test]
471    fn test_read_unsigned_not_enough_data() {
472        let buf = [CONTINUATION_BIT];
473        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
474        assert_eq!(
475            read::unsigned(&mut readable).map_eof(&buf),
476            Err(Error::UnexpectedEof(ReaderOffsetId(1)))
477        );
478    }
479
480    #[test]
481    fn test_read_signed_not_enough_data() {
482        let buf = [CONTINUATION_BIT];
483        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
484        assert_eq!(
485            read::signed(&mut readable).map_eof(&buf),
486            Err(Error::UnexpectedEof(ReaderOffsetId(1)))
487        );
488    }
489
490    #[test]
491    #[cfg(feature = "std")]
492    fn test_write_unsigned_not_enough_space() {
493        let mut buf = [0; 1];
494        let mut writable = &mut buf[..];
495        match write::unsigned(&mut writable, 128) {
496            Err(e) => assert_eq!(e.kind(), std::io::ErrorKind::WriteZero),
497            otherwise => panic!("Unexpected: {:?}", otherwise),
498        }
499    }
500
501    #[test]
502    #[cfg(feature = "std")]
503    fn test_write_signed_not_enough_space() {
504        let mut buf = [0; 1];
505        let mut writable = &mut buf[..];
506        match write::signed(&mut writable, 128) {
507            Err(e) => assert_eq!(e.kind(), std::io::ErrorKind::WriteZero),
508            otherwise => panic!("Unexpected: {:?}", otherwise),
509        }
510    }
511
512    #[test]
513    fn dogfood_signed() {
514        fn inner(i: i64) {
515            let mut buf = Vec::new();
516            buf.extend(write::Leb128::signed(i).bytes());
517            buf.resize(1024, 0u8);
518
519            let mut readable = EndianSlice::new(&buf[..], NativeEndian);
520            let result = read::signed(&mut readable).expect("Should be able to read it back again");
521            assert_eq!(i, result);
522        }
523        for i in -513..513 {
524            inner(i);
525        }
526        inner(i64::MIN);
527    }
528
529    #[test]
530    fn dogfood_unsigned() {
531        for i in 0..1025 {
532            let mut buf = Vec::new();
533            buf.extend(write::Leb128::unsigned(i).bytes());
534            buf.resize(1024, 0u8);
535
536            let mut readable = EndianSlice::new(&buf[..], NativeEndian);
537            let result =
538                read::unsigned(&mut readable).expect("Should be able to read it back again");
539            assert_eq!(i, result);
540        }
541    }
542
543    #[test]
544    fn test_read_unsigned_overflow() {
545        let buf = [
546            2u8 | CONTINUATION_BIT,
547            2 | CONTINUATION_BIT,
548            2 | CONTINUATION_BIT,
549            2 | CONTINUATION_BIT,
550            2 | CONTINUATION_BIT,
551            2 | CONTINUATION_BIT,
552            2 | CONTINUATION_BIT,
553            2 | CONTINUATION_BIT,
554            2 | CONTINUATION_BIT,
555            2 | CONTINUATION_BIT,
556            2 | CONTINUATION_BIT,
557            2 | CONTINUATION_BIT,
558            2 | CONTINUATION_BIT,
559            2 | CONTINUATION_BIT,
560            2 | CONTINUATION_BIT,
561            2 | CONTINUATION_BIT,
562            2 | CONTINUATION_BIT,
563            2 | CONTINUATION_BIT,
564            2 | CONTINUATION_BIT,
565            2 | CONTINUATION_BIT,
566            2 | CONTINUATION_BIT,
567            2 | CONTINUATION_BIT,
568            2 | CONTINUATION_BIT,
569            2 | CONTINUATION_BIT,
570            2 | CONTINUATION_BIT,
571            2 | CONTINUATION_BIT,
572            2 | CONTINUATION_BIT,
573            2 | CONTINUATION_BIT,
574            2 | CONTINUATION_BIT,
575            2 | CONTINUATION_BIT,
576            1,
577        ];
578        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
579        assert!(read::unsigned(&mut readable).is_err());
580    }
581
582    #[test]
583    fn test_read_signed_overflow() {
584        let buf = [
585            2u8 | CONTINUATION_BIT,
586            2 | CONTINUATION_BIT,
587            2 | CONTINUATION_BIT,
588            2 | CONTINUATION_BIT,
589            2 | CONTINUATION_BIT,
590            2 | CONTINUATION_BIT,
591            2 | CONTINUATION_BIT,
592            2 | CONTINUATION_BIT,
593            2 | CONTINUATION_BIT,
594            2 | CONTINUATION_BIT,
595            2 | CONTINUATION_BIT,
596            2 | CONTINUATION_BIT,
597            2 | CONTINUATION_BIT,
598            2 | CONTINUATION_BIT,
599            2 | CONTINUATION_BIT,
600            2 | CONTINUATION_BIT,
601            2 | CONTINUATION_BIT,
602            2 | CONTINUATION_BIT,
603            2 | CONTINUATION_BIT,
604            2 | CONTINUATION_BIT,
605            2 | CONTINUATION_BIT,
606            2 | CONTINUATION_BIT,
607            2 | CONTINUATION_BIT,
608            2 | CONTINUATION_BIT,
609            2 | CONTINUATION_BIT,
610            2 | CONTINUATION_BIT,
611            2 | CONTINUATION_BIT,
612            2 | CONTINUATION_BIT,
613            2 | CONTINUATION_BIT,
614            2 | CONTINUATION_BIT,
615            1,
616        ];
617        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
618        assert!(read::signed(&mut readable).is_err());
619    }
620
621    #[test]
622    fn test_read_multiple() {
623        let buf = [2u8 | CONTINUATION_BIT, 1u8, 1u8];
624
625        let mut readable = EndianSlice::new(&buf[..], NativeEndian);
626        assert_eq!(
627            read::unsigned(&mut readable).expect("Should read first number"),
628            130u64
629        );
630        assert_eq!(
631            read::unsigned(&mut readable).expect("Should read first number"),
632            1u64
633        );
634    }
635
636    #[test]
637    fn test_read_u16() {
638        for (buf, val) in [
639            (&[2][..], 2),
640            (&[0x7f][..], 0x7f),
641            (&[0x80, 1][..], 0x80),
642            (&[0x81, 1][..], 0x81),
643            (&[0x82, 1][..], 0x82),
644            (&[0xff, 0x7f][..], 0x3fff),
645            (&[0x80, 0x80, 1][..], 0x4000),
646            (&[0xff, 0xff, 1][..], 0x7fff),
647            (&[0xff, 0xff, 3][..], 0xffff),
648        ]
649        .iter()
650        {
651            let mut readable = EndianSlice::new(buf, NativeEndian);
652            assert_eq!(*val, read::u16(&mut readable).expect("Should read number"));
653        }
654
655        for buf in [
656            &[0x80][..],
657            &[0x80, 0x80][..],
658            &[0x80, 0x80, 4][..],
659            &[0x80, 0x80, 0x80, 3][..],
660        ]
661        .iter()
662        {
663            let mut readable = EndianSlice::new(buf, NativeEndian);
664            assert!(read::u16(&mut readable).is_err(), "{:?}", buf);
665        }
666    }
667}
gimli/leb128.rs

gimli/
leb128.rs
