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)]
46 pub const CONTINUATION_BIT: u8 = 1 << 7;
47 #[doc(hidden)]
48 pub const SIGN_BIT: u8 = 1 << 6;
49
50 #[doc(hidden)]
51 #[inline]
low_bits_of_byte(byte: u8) -> u852 pub fn low_bits_of_byte(byte: u8) -> u8 {
53 byte & !CONTINUATION_BIT
54 }
55
56 #[doc(hidden)]
57 #[inline]
low_bits_of_u64(val: u64) -> u858 pub 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 signed and unsigned integers that have been LEB128
64 /// encoded.
65 pub mod read {
66 use super::{low_bits_of_byte, CONTINUATION_BIT, SIGN_BIT};
67 use std::fmt;
68 use std::io;
69
70 /// An enumeration of the possible errors that can occur when reading a
71 /// number encoded with LEB128.
72 #[derive(Debug)]
73 pub enum Error {
74 /// There was an underlying IO error.
75 IoError(io::Error),
76 /// The number being read is larger than can be represented.
77 Overflow,
78 }
79
80 impl From<io::Error> for Error {
from(e: io::Error) -> Self81 fn from(e: io::Error) -> Self {
82 Error::IoError(e)
83 }
84 }
85
86 impl fmt::Display for Error {
fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error>87 fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
88 write!(
89 f,
90 "leb128::read::Error: {}",
91 ::std::error::Error::description(self)
92 )
93 }
94 }
95
96 impl ::std::error::Error for Error {
description(&self) -> &str97 fn description(&self) -> &str {
98 match *self {
99 Error::IoError(ref e) => e.description(),
100 Error::Overflow => "The number being read is larger than can be represented",
101 }
102 }
103
cause(&self) -> Option<&::std::error::Error>104 fn cause(&self) -> Option<&::std::error::Error> {
105 match *self {
106 Error::IoError(ref e) => Some(e),
107 Error::Overflow => None,
108 }
109 }
110 }
111
112 /// Read an unsigned LEB128 number from the given `std::io::Read`able and
113 /// return it or an error if reading failed.
unsigned<R>(r: &mut R) -> Result<u64, Error> where R: io::Read,114 pub fn unsigned<R>(r: &mut R) -> Result<u64, Error>
115 where
116 R: io::Read,
117 {
118 let mut result = 0;
119 let mut shift = 0;
120
121 loop {
122 let mut buf = [0];
123 try!(r.read_exact(&mut buf));
124
125 if shift == 63 && buf[0] != 0x00 && buf[0] != 0x01 {
126 return Err(Error::Overflow);
127 }
128
129 let low_bits = low_bits_of_byte(buf[0]) as u64;
130 result |= low_bits << shift;
131
132 if buf[0] & CONTINUATION_BIT == 0 {
133 return Ok(result);
134 }
135
136 shift += 7;
137 }
138 }
139
140 /// Read a signed LEB128 number from the given `std::io::Read`able and
141 /// return it or an error if reading failed.
signed<R>(r: &mut R) -> Result<i64, Error> where R: io::Read,142 pub fn signed<R>(r: &mut R) -> Result<i64, Error>
143 where
144 R: io::Read,
145 {
146 let mut result = 0;
147 let mut shift = 0;
148 let size = 64;
149 let mut byte;
150
151 loop {
152 let mut buf = [0];
153 try!(r.read_exact(&mut buf));
154
155 byte = buf[0];
156 if shift == 63 && byte != 0x00 && byte != 0x7f {
157 return Err(Error::Overflow);
158 }
159
160 let low_bits = low_bits_of_byte(byte) as i64;
161 result |= low_bits << shift;
162 shift += 7;
163
164 if byte & CONTINUATION_BIT == 0 {
165 break;
166 }
167 }
168
169 if shift < size && (SIGN_BIT & byte) == SIGN_BIT {
170 // Sign extend the result.
171 result |= !0 << shift;
172 }
173
174 Ok(result)
175 }
176 }
177
178 /// A module for writing integers encoded as LEB128.
179 pub mod write {
180 use super::{low_bits_of_u64, CONTINUATION_BIT};
181 use std::io;
182
183 /// Write the given unsigned number using the LEB128 encoding to the given
184 /// `std::io::Write`able. Returns the number of bytes written to `w`, or an
185 /// error if writing failed.
unsigned<W>(w: &mut W, mut val: u64) -> Result<usize, io::Error> where W: ?Sized + io::Write,186 pub fn unsigned<W>(w: &mut W, mut val: u64) -> Result<usize, io::Error>
187 where
188 W: ?Sized + io::Write,
189 {
190 let mut bytes_written = 0;
191 loop {
192 let mut byte = low_bits_of_u64(val);
193 val >>= 7;
194 if val != 0 {
195 // More bytes to come, so set the continuation bit.
196 byte |= CONTINUATION_BIT;
197 }
198
199 let buf = [byte];
200 try!(w.write_all(&buf));
201 bytes_written += 1;
202
203 if val == 0 {
204 return Ok(bytes_written);
205 }
206 }
207 }
208
209 /// Write the given signed number using the LEB128 encoding to the given
210 /// `std::io::Write`able. Returns the number of bytes written to `w`, or an
211 /// error if writing failed.
signed<W>(w: &mut W, mut val: i64) -> Result<usize, io::Error> where W: ?Sized + io::Write,212 pub fn signed<W>(w: &mut W, mut val: i64) -> Result<usize, io::Error>
213 where
214 W: ?Sized + io::Write,
215 {
216 let mut bytes_written = 0;
217 loop {
218 let mut byte = val as u8;
219 // Keep the sign bit for testing
220 val >>= 6;
221 let done = val == 0 || val == -1;
222 if done {
223 byte &= !CONTINUATION_BIT;
224 } else {
225 // Remove the sign bit
226 val >>= 1;
227 // More bytes to come, so set the continuation bit.
228 byte |= CONTINUATION_BIT;
229 }
230
231 let buf = [byte];
232 try!(w.write_all(&buf));
233 bytes_written += 1;
234
235 if done {
236 return Ok(bytes_written);
237 }
238 }
239 }
240 }
241
242 #[cfg(test)]
243 mod tests {
244 use super::*;
245 use std;
246 use std::io;
247
248 #[test]
test_low_bits_of_byte()249 fn test_low_bits_of_byte() {
250 for i in 0..127 {
251 assert_eq!(i, low_bits_of_byte(i));
252 assert_eq!(i, low_bits_of_byte(i | CONTINUATION_BIT));
253 }
254 }
255
256 #[test]
test_low_bits_of_u64()257 fn test_low_bits_of_u64() {
258 for i in 0u64..127 {
259 assert_eq!(i as u8, low_bits_of_u64(1 << 16 | i));
260 assert_eq!(
261 i as u8,
262 low_bits_of_u64(i << 16 | i | (CONTINUATION_BIT as u64))
263 );
264 }
265 }
266
267 // Examples from the DWARF 4 standard, section 7.6, figure 22.
268 #[test]
test_read_unsigned()269 fn test_read_unsigned() {
270 let buf = [2u8];
271 let mut readable = &buf[..];
272 assert_eq!(
273 2,
274 read::unsigned(&mut readable).expect("Should read number")
275 );
276
277 let buf = [127u8];
278 let mut readable = &buf[..];
279 assert_eq!(
280 127,
281 read::unsigned(&mut readable).expect("Should read number")
282 );
283
284 let buf = [CONTINUATION_BIT, 1];
285 let mut readable = &buf[..];
286 assert_eq!(
287 128,
288 read::unsigned(&mut readable).expect("Should read number")
289 );
290
291 let buf = [1u8 | CONTINUATION_BIT, 1];
292 let mut readable = &buf[..];
293 assert_eq!(
294 129,
295 read::unsigned(&mut readable).expect("Should read number")
296 );
297
298 let buf = [2u8 | CONTINUATION_BIT, 1];
299 let mut readable = &buf[..];
300 assert_eq!(
301 130,
302 read::unsigned(&mut readable).expect("Should read number")
303 );
304
305 let buf = [57u8 | CONTINUATION_BIT, 100];
306 let mut readable = &buf[..];
307 assert_eq!(
308 12857,
309 read::unsigned(&mut readable).expect("Should read number")
310 );
311 }
312
313 // Examples from the DWARF 4 standard, section 7.6, figure 23.
314 #[test]
test_read_signed()315 fn test_read_signed() {
316 let buf = [2u8];
317 let mut readable = &buf[..];
318 assert_eq!(2, read::signed(&mut readable).expect("Should read number"));
319
320 let buf = [0x7eu8];
321 let mut readable = &buf[..];
322 assert_eq!(-2, read::signed(&mut readable).expect("Should read number"));
323
324 let buf = [127u8 | CONTINUATION_BIT, 0];
325 let mut readable = &buf[..];
326 assert_eq!(
327 127,
328 read::signed(&mut readable).expect("Should read number")
329 );
330
331 let buf = [1u8 | CONTINUATION_BIT, 0x7f];
332 let mut readable = &buf[..];
333 assert_eq!(
334 -127,
335 read::signed(&mut readable).expect("Should read number")
336 );
337
338 let buf = [CONTINUATION_BIT, 1];
339 let mut readable = &buf[..];
340 assert_eq!(
341 128,
342 read::signed(&mut readable).expect("Should read number")
343 );
344
345 let buf = [CONTINUATION_BIT, 0x7f];
346 let mut readable = &buf[..];
347 assert_eq!(
348 -128,
349 read::signed(&mut readable).expect("Should read number")
350 );
351
352 let buf = [1u8 | CONTINUATION_BIT, 1];
353 let mut readable = &buf[..];
354 assert_eq!(
355 129,
356 read::signed(&mut readable).expect("Should read number")
357 );
358
359 let buf = [0x7fu8 | CONTINUATION_BIT, 0x7e];
360 let mut readable = &buf[..];
361 assert_eq!(
362 -129,
363 read::signed(&mut readable).expect("Should read number")
364 );
365 }
366
367 #[test]
test_read_signed_63_bits()368 fn test_read_signed_63_bits() {
369 let buf = [
370 CONTINUATION_BIT,
371 CONTINUATION_BIT,
372 CONTINUATION_BIT,
373 CONTINUATION_BIT,
374 CONTINUATION_BIT,
375 CONTINUATION_BIT,
376 CONTINUATION_BIT,
377 CONTINUATION_BIT,
378 0x40,
379 ];
380 let mut readable = &buf[..];
381 assert_eq!(
382 -0x4000000000000000,
383 read::signed(&mut readable).expect("Should read number")
384 );
385 }
386
387 #[test]
test_read_unsigned_not_enough_data()388 fn test_read_unsigned_not_enough_data() {
389 let buf = [CONTINUATION_BIT];
390 let mut readable = &buf[..];
391 match read::unsigned(&mut readable) {
392 Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
393 otherwise => panic!("Unexpected: {:?}", otherwise),
394 }
395 }
396
397 #[test]
test_read_signed_not_enough_data()398 fn test_read_signed_not_enough_data() {
399 let buf = [CONTINUATION_BIT];
400 let mut readable = &buf[..];
401 match read::signed(&mut readable) {
402 Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
403 otherwise => panic!("Unexpected: {:?}", otherwise),
404 }
405 }
406
407 #[test]
test_write_unsigned_not_enough_space()408 fn test_write_unsigned_not_enough_space() {
409 let mut buf = [0; 1];
410 let mut writable = &mut buf[..];
411 match write::unsigned(&mut writable, 128) {
412 Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
413 otherwise => panic!("Unexpected: {:?}", otherwise),
414 }
415 }
416
417 #[test]
test_write_signed_not_enough_space()418 fn test_write_signed_not_enough_space() {
419 let mut buf = [0; 1];
420 let mut writable = &mut buf[..];
421 match write::signed(&mut writable, 128) {
422 Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
423 otherwise => panic!("Unexpected: {:?}", otherwise),
424 }
425 }
426
427 #[test]
dogfood_signed()428 fn dogfood_signed() {
429 fn inner(i: i64) {
430 let mut buf = [0u8; 1024];
431
432 {
433 let mut writable = &mut buf[..];
434 write::signed(&mut writable, i).expect("Should write signed number");
435 }
436
437 let mut readable = &buf[..];
438 let result = read::signed(&mut readable).expect("Should be able to read it back again");
439 assert_eq!(i, result);
440 }
441 for i in -513..513 {
442 inner(i);
443 }
444 inner(std::i64::MIN);
445 }
446
447 #[test]
dogfood_unsigned()448 fn dogfood_unsigned() {
449 for i in 0..1025 {
450 let mut buf = [0u8; 1024];
451
452 {
453 let mut writable = &mut buf[..];
454 write::unsigned(&mut writable, i).expect("Should write signed number");
455 }
456
457 let mut readable = &buf[..];
458 let result =
459 read::unsigned(&mut readable).expect("Should be able to read it back again");
460 assert_eq!(i, result);
461 }
462 }
463
464 #[test]
test_read_unsigned_overflow()465 fn test_read_unsigned_overflow() {
466 let buf = [
467 2u8 | CONTINUATION_BIT,
468 2 | CONTINUATION_BIT,
469 2 | CONTINUATION_BIT,
470 2 | CONTINUATION_BIT,
471 2 | CONTINUATION_BIT,
472 2 | CONTINUATION_BIT,
473 2 | CONTINUATION_BIT,
474 2 | CONTINUATION_BIT,
475 2 | CONTINUATION_BIT,
476 2 | CONTINUATION_BIT,
477 2 | CONTINUATION_BIT,
478 2 | CONTINUATION_BIT,
479 2 | CONTINUATION_BIT,
480 2 | CONTINUATION_BIT,
481 2 | CONTINUATION_BIT,
482 2 | CONTINUATION_BIT,
483 2 | CONTINUATION_BIT,
484 2 | CONTINUATION_BIT,
485 2 | CONTINUATION_BIT,
486 2 | CONTINUATION_BIT,
487 2 | CONTINUATION_BIT,
488 2 | CONTINUATION_BIT,
489 2 | CONTINUATION_BIT,
490 2 | CONTINUATION_BIT,
491 2 | CONTINUATION_BIT,
492 2 | CONTINUATION_BIT,
493 2 | CONTINUATION_BIT,
494 2 | CONTINUATION_BIT,
495 2 | CONTINUATION_BIT,
496 2 | CONTINUATION_BIT,
497 1,
498 ];
499 let mut readable = &buf[..];
500 assert!(read::unsigned(&mut readable).is_err());
501 }
502
503 #[test]
test_read_signed_overflow()504 fn test_read_signed_overflow() {
505 let buf = [
506 2u8 | 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 2 | CONTINUATION_BIT,
522 2 | CONTINUATION_BIT,
523 2 | CONTINUATION_BIT,
524 2 | CONTINUATION_BIT,
525 2 | CONTINUATION_BIT,
526 2 | CONTINUATION_BIT,
527 2 | CONTINUATION_BIT,
528 2 | CONTINUATION_BIT,
529 2 | CONTINUATION_BIT,
530 2 | CONTINUATION_BIT,
531 2 | CONTINUATION_BIT,
532 2 | CONTINUATION_BIT,
533 2 | CONTINUATION_BIT,
534 2 | CONTINUATION_BIT,
535 2 | CONTINUATION_BIT,
536 1,
537 ];
538 let mut readable = &buf[..];
539 assert!(read::signed(&mut readable).is_err());
540 }
541
542 #[test]
test_read_multiple()543 fn test_read_multiple() {
544 let buf = [2u8 | CONTINUATION_BIT, 1u8, 1u8];
545
546 let mut readable = &buf[..];
547 assert_eq!(
548 read::unsigned(&mut readable).expect("Should read first number"),
549 130u64
550 );
551 assert_eq!(
552 read::unsigned(&mut readable).expect("Should read first number"),
553 1u64
554 );
555 }
556 }
557