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