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: u64 = 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}
653