leb128/
lib.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//! use leb128;
11//!
12//! let mut buf = [0; 1024];
13//!
14//! // Write to anything that implements `std::io::Write`.
15//! {
16//!     let mut writable = &mut buf[..];
17//!     leb128::write::signed(&mut writable, -12345).expect("Should write number");
18//! }
19//!
20//! // Read from anything that implements `std::io::Read`.
21//! let mut readable = &buf[..];
22//! let val = leb128::read::signed(&mut readable).expect("Should read number");
23//! assert_eq!(val, -12345);
24//! ```
25//!
26//! Or read and write unsigned integers:
27//!
28//! ```
29//! use 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 = &buf[..];
39//! let val = leb128::read::unsigned(&mut readable).expect("Should read number");
40//! assert_eq!(val, 98765);
41//! ```
42
43#![deny(missing_docs)]
44
45#[doc(hidden)]
46pub const CONTINUATION_BIT: u8 = 1 << 7;
47#[doc(hidden)]
48pub const SIGN_BIT: u8 = 1 << 6;
49
50#[doc(hidden)]
51#[inline]
52pub fn low_bits_of_byte(byte: u8) -> u8 {
53    byte & !CONTINUATION_BIT
54}
55
56#[doc(hidden)]
57#[inline]
58pub fn low_bits_of_u64(val: u64) -> u8 {
59    let byte = val & (std::u8::MAX as u64);
60    low_bits_of_byte(byte as u8)
61}
62
63/// A module for reading LEB128-encoded signed and unsigned integers.
64pub mod read {
65    use super::{low_bits_of_byte, CONTINUATION_BIT, SIGN_BIT};
66    use std::fmt;
67    use std::io;
68
69    /// An error type for reading LEB128-encoded values.
70    #[derive(Debug)]
71    pub enum Error {
72        /// There was an underlying IO error.
73        IoError(io::Error),
74        /// The number being read is larger than can be represented.
75        Overflow,
76    }
77
78    impl From<io::Error> for Error {
79        fn from(e: io::Error) -> Self {
80            Error::IoError(e)
81        }
82    }
83
84    impl fmt::Display for Error {
85        fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
86            match *self {
87                Error::IoError(ref e) => e.fmt(f),
88                Error::Overflow => {
89                    write!(f, "The number being read is larger than can be represented")
90                }
91            }
92        }
93    }
94
95    impl std::error::Error for Error {
96        fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
97            match *self {
98                Error::IoError(ref e) => Some(e),
99                Error::Overflow => None,
100            }
101        }
102    }
103
104    /// Read an unsigned LEB128-encoded number from the `std::io::Read` stream
105    /// `r`.
106    ///
107    /// On success, return the number.
108    pub fn unsigned<R>(r: &mut R) -> Result<u64, Error>
109    where
110        R: ?Sized + io::Read,
111    {
112        let mut result = 0;
113        let mut shift = 0;
114
115        loop {
116            let mut buf = [0];
117            r.read_exact(&mut buf)?;
118
119            if shift == 63 && buf[0] != 0x00 && buf[0] != 0x01 {
120                while buf[0] & CONTINUATION_BIT != 0 {
121                    r.read_exact(&mut buf)?;
122                }
123                return Err(Error::Overflow);
124            }
125
126            let low_bits = low_bits_of_byte(buf[0]) as u64;
127            result |= low_bits << shift;
128
129            if buf[0] & CONTINUATION_BIT == 0 {
130                return Ok(result);
131            }
132
133            shift += 7;
134        }
135    }
136
137    /// Read a signed LEB128-encoded number from the `std::io::Read` stream `r`.
138    ///
139    /// On success, return the number.
140    pub fn signed<R>(r: &mut R) -> Result<i64, Error>
141    where
142        R: ?Sized + io::Read,
143    {
144        let mut result = 0;
145        let mut shift = 0;
146        let size = 64;
147        let mut byte;
148
149        loop {
150            let mut buf = [0];
151            r.read_exact(&mut buf)?;
152
153            byte = buf[0];
154            if shift == 63 && byte != 0x00 && byte != 0x7f {
155                while buf[0] & CONTINUATION_BIT != 0 {
156                    r.read_exact(&mut buf)?;
157                }
158                return Err(Error::Overflow);
159            }
160
161            let low_bits = low_bits_of_byte(byte) as i64;
162            result |= low_bits << shift;
163            shift += 7;
164
165            if byte & CONTINUATION_BIT == 0 {
166                break;
167            }
168        }
169
170        if shift < size && (SIGN_BIT & byte) == SIGN_BIT {
171            // Sign extend the result.
172            result |= !0 << shift;
173        }
174
175        Ok(result)
176    }
177}
178
179/// A module for writing LEB128-encoded signed and unsigned integers.
180pub mod write {
181    use super::{low_bits_of_u64, CONTINUATION_BIT};
182    use std::io;
183
184    /// Write `val` to the `std::io::Write` stream `w` as an unsigned LEB128 value.
185    ///
186    /// On success, return the number of bytes written to `w`.
187    pub fn unsigned<W>(w: &mut W, mut val: u64) -> Result<usize, io::Error>
188    where
189        W: ?Sized + io::Write,
190    {
191        let mut bytes_written = 0;
192        loop {
193            let mut byte = low_bits_of_u64(val);
194            val >>= 7;
195            if val != 0 {
196                // More bytes to come, so set the continuation bit.
197                byte |= CONTINUATION_BIT;
198            }
199
200            let buf = [byte];
201            w.write_all(&buf)?;
202            bytes_written += 1;
203
204            if val == 0 {
205                return Ok(bytes_written);
206            }
207        }
208    }
209
210    /// Write `val` to the `std::io::Write` stream `w` as a signed LEB128 value.
211    ///
212    /// On success, return the number of bytes written to `w`.
213    pub fn signed<W>(w: &mut W, mut val: i64) -> Result<usize, io::Error>
214    where
215        W: ?Sized + io::Write,
216    {
217        let mut bytes_written = 0;
218        loop {
219            let mut byte = val as u8;
220            // Keep the sign bit for testing
221            val >>= 6;
222            let done = val == 0 || val == -1;
223            if done {
224                byte &= !CONTINUATION_BIT;
225            } else {
226                // Remove the sign bit
227                val >>= 1;
228                // More bytes to come, so set the continuation bit.
229                byte |= CONTINUATION_BIT;
230            }
231
232            let buf = [byte];
233            w.write_all(&buf)?;
234            bytes_written += 1;
235
236            if done {
237                return Ok(bytes_written);
238            }
239        }
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246    use std;
247    use std::io;
248
249    #[test]
250    fn test_low_bits_of_byte() {
251        for i in 0..127 {
252            assert_eq!(i, low_bits_of_byte(i));
253            assert_eq!(i, low_bits_of_byte(i | CONTINUATION_BIT));
254        }
255    }
256
257    #[test]
258    fn test_low_bits_of_u64() {
259        for i in 0u64..127 {
260            assert_eq!(i as u8, low_bits_of_u64(1 << 16 | i));
261            assert_eq!(
262                i as u8,
263                low_bits_of_u64(i << 16 | i | (CONTINUATION_BIT as u64))
264            );
265        }
266    }
267
268    // Examples from the DWARF 4 standard, section 7.6, figure 22.
269    #[test]
270    fn test_read_unsigned() {
271        let buf = [2u8];
272        let mut readable = &buf[..];
273        assert_eq!(
274            2,
275            read::unsigned(&mut readable).expect("Should read number")
276        );
277
278        let buf = [127u8];
279        let mut readable = &buf[..];
280        assert_eq!(
281            127,
282            read::unsigned(&mut readable).expect("Should read number")
283        );
284
285        let buf = [CONTINUATION_BIT, 1];
286        let mut readable = &buf[..];
287        assert_eq!(
288            128,
289            read::unsigned(&mut readable).expect("Should read number")
290        );
291
292        let buf = [1u8 | CONTINUATION_BIT, 1];
293        let mut readable = &buf[..];
294        assert_eq!(
295            129,
296            read::unsigned(&mut readable).expect("Should read number")
297        );
298
299        let buf = [2u8 | CONTINUATION_BIT, 1];
300        let mut readable = &buf[..];
301        assert_eq!(
302            130,
303            read::unsigned(&mut readable).expect("Should read number")
304        );
305
306        let buf = [57u8 | CONTINUATION_BIT, 100];
307        let mut readable = &buf[..];
308        assert_eq!(
309            12857,
310            read::unsigned(&mut readable).expect("Should read number")
311        );
312    }
313
314    #[test]
315    fn test_read_unsigned_thru_dyn_trait() {
316        fn read(r: &mut dyn io::Read) -> u64 {
317            read::unsigned(r).expect("Should read number")
318        }
319
320        let buf = [0u8];
321
322        let mut readable = &buf[..];
323        assert_eq!(0, read(&mut readable));
324
325        let mut readable = io::Cursor::new(buf);
326        assert_eq!(0, read(&mut readable));
327    }
328
329    // Examples from the DWARF 4 standard, section 7.6, figure 23.
330    #[test]
331    fn test_read_signed() {
332        let buf = [2u8];
333        let mut readable = &buf[..];
334        assert_eq!(2, read::signed(&mut readable).expect("Should read number"));
335
336        let buf = [0x7eu8];
337        let mut readable = &buf[..];
338        assert_eq!(-2, read::signed(&mut readable).expect("Should read number"));
339
340        let buf = [127u8 | CONTINUATION_BIT, 0];
341        let mut readable = &buf[..];
342        assert_eq!(
343            127,
344            read::signed(&mut readable).expect("Should read number")
345        );
346
347        let buf = [1u8 | CONTINUATION_BIT, 0x7f];
348        let mut readable = &buf[..];
349        assert_eq!(
350            -127,
351            read::signed(&mut readable).expect("Should read number")
352        );
353
354        let buf = [CONTINUATION_BIT, 1];
355        let mut readable = &buf[..];
356        assert_eq!(
357            128,
358            read::signed(&mut readable).expect("Should read number")
359        );
360
361        let buf = [CONTINUATION_BIT, 0x7f];
362        let mut readable = &buf[..];
363        assert_eq!(
364            -128,
365            read::signed(&mut readable).expect("Should read number")
366        );
367
368        let buf = [1u8 | CONTINUATION_BIT, 1];
369        let mut readable = &buf[..];
370        assert_eq!(
371            129,
372            read::signed(&mut readable).expect("Should read number")
373        );
374
375        let buf = [0x7fu8 | CONTINUATION_BIT, 0x7e];
376        let mut readable = &buf[..];
377        assert_eq!(
378            -129,
379            read::signed(&mut readable).expect("Should read number")
380        );
381    }
382
383    #[test]
384    fn test_read_signed_thru_dyn_trait() {
385        fn read(r: &mut dyn io::Read) -> i64 {
386            read::signed(r).expect("Should read number")
387        }
388
389        let buf = [0u8];
390
391        let mut readable = &buf[..];
392        assert_eq!(0, read(&mut readable));
393
394        let mut readable = io::Cursor::new(buf);
395        assert_eq!(0, read(&mut readable));
396    }
397
398    #[test]
399    fn test_read_signed_63_bits() {
400        let buf = [
401            CONTINUATION_BIT,
402            CONTINUATION_BIT,
403            CONTINUATION_BIT,
404            CONTINUATION_BIT,
405            CONTINUATION_BIT,
406            CONTINUATION_BIT,
407            CONTINUATION_BIT,
408            CONTINUATION_BIT,
409            0x40,
410        ];
411        let mut readable = &buf[..];
412        assert_eq!(
413            -0x4000000000000000,
414            read::signed(&mut readable).expect("Should read number")
415        );
416    }
417
418    #[test]
419    fn test_read_unsigned_not_enough_data() {
420        let buf = [CONTINUATION_BIT];
421        let mut readable = &buf[..];
422        match read::unsigned(&mut readable) {
423            Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
424            otherwise => panic!("Unexpected: {:?}", otherwise),
425        }
426    }
427
428    #[test]
429    fn test_read_signed_not_enough_data() {
430        let buf = [CONTINUATION_BIT];
431        let mut readable = &buf[..];
432        match read::signed(&mut readable) {
433            Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
434            otherwise => panic!("Unexpected: {:?}", otherwise),
435        }
436    }
437
438    #[test]
439    fn test_write_unsigned_not_enough_space() {
440        let mut buf = [0; 1];
441        let mut writable = &mut buf[..];
442        match write::unsigned(&mut writable, 128) {
443            Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
444            otherwise => panic!("Unexpected: {:?}", otherwise),
445        }
446    }
447
448    #[test]
449    fn test_write_signed_not_enough_space() {
450        let mut buf = [0; 1];
451        let mut writable = &mut buf[..];
452        match write::signed(&mut writable, 128) {
453            Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
454            otherwise => panic!("Unexpected: {:?}", otherwise),
455        }
456    }
457
458    #[test]
459    fn test_write_unsigned_thru_dyn_trait() {
460        fn write(w: &mut dyn io::Write, val: u64) -> usize {
461            write::unsigned(w, val).expect("Should write number")
462        }
463        let mut buf = [0u8; 1];
464
465        let mut writable = &mut buf[..];
466        assert_eq!(write(&mut writable, 0), 1);
467        assert_eq!(buf[0], 0);
468
469        let mut writable = Vec::from(&buf[..]);
470        assert_eq!(write(&mut writable, 0), 1);
471        assert_eq!(buf[0], 0);
472    }
473
474    #[test]
475    fn test_write_signed_thru_dyn_trait() {
476        fn write(w: &mut dyn io::Write, val: i64) -> usize {
477            write::signed(w, val).expect("Should write number")
478        }
479        let mut buf = [0u8; 1];
480
481        let mut writable = &mut buf[..];
482        assert_eq!(write(&mut writable, 0), 1);
483        assert_eq!(buf[0], 0);
484
485        let mut writable = Vec::from(&buf[..]);
486        assert_eq!(write(&mut writable, 0), 1);
487        assert_eq!(buf[0], 0);
488    }
489
490    #[test]
491    fn dogfood_signed() {
492        fn inner(i: i64) {
493            let mut buf = [0u8; 1024];
494
495            {
496                let mut writable = &mut buf[..];
497                write::signed(&mut writable, i).expect("Should write signed number");
498            }
499
500            let mut readable = &buf[..];
501            let result = read::signed(&mut readable).expect("Should be able to read it back again");
502            assert_eq!(i, result);
503        }
504        for i in -513..513 {
505            inner(i);
506        }
507        inner(std::i64::MIN);
508    }
509
510    #[test]
511    fn dogfood_unsigned() {
512        for i in 0..1025 {
513            let mut buf = [0u8; 1024];
514
515            {
516                let mut writable = &mut buf[..];
517                write::unsigned(&mut writable, i).expect("Should write signed number");
518            }
519
520            let mut readable = &buf[..];
521            let result =
522                read::unsigned(&mut readable).expect("Should be able to read it back again");
523            assert_eq!(i, result);
524        }
525    }
526
527    #[test]
528    fn test_read_unsigned_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 = &buf[..];
563        assert!(read::unsigned(&mut readable).is_err());
564    }
565
566    #[test]
567    fn test_read_signed_overflow() {
568        let buf = [
569            2u8 | 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            2 | CONTINUATION_BIT,
577            2 | CONTINUATION_BIT,
578            2 | CONTINUATION_BIT,
579            2 | CONTINUATION_BIT,
580            2 | CONTINUATION_BIT,
581            2 | CONTINUATION_BIT,
582            2 | CONTINUATION_BIT,
583            2 | CONTINUATION_BIT,
584            2 | CONTINUATION_BIT,
585            2 | 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            1,
600        ];
601        let mut readable = &buf[..];
602        assert!(read::signed(&mut readable).is_err());
603    }
604
605    #[test]
606    fn test_read_multiple() {
607        let buf = [2u8 | CONTINUATION_BIT, 1u8, 1u8];
608
609        let mut readable = &buf[..];
610        assert_eq!(
611            read::unsigned(&mut readable).expect("Should read first number"),
612            130u64
613        );
614        assert_eq!(
615            read::unsigned(&mut readable).expect("Should read first number"),
616            1u64
617        );
618    }
619
620    #[test]
621    fn test_read_multiple_with_overflow() {
622        let buf = [
623            0b1111_1111,
624            0b1111_1111,
625            0b1111_1111,
626            0b1111_1111,
627            0b1111_1111,
628            0b1111_1111,
629            0b1111_1111,
630            0b1111_1111,
631            0b1111_1111,
632            0b1111_1111,
633            0b0111_1111, // Overflow!
634            0b1110_0100,
635            0b1110_0000,
636            0b0000_0010, // 45156
637        ];
638        let mut readable = &buf[..];
639
640        assert!(if let read::Error::Overflow =
641            read::unsigned(&mut readable).expect_err("Should fail with Error::Overflow")
642        {
643            true
644        } else {
645            false
646        });
647        assert_eq!(
648            read::unsigned(&mut readable).expect("Should succeed with correct value"),
649            45156
650        );
651    }
652}
leb128/lib.rs

leb128/
lib.rs
