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