gimli/
leb128.rs

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

gimli/
leb128.rs
