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-core" )] |
49 | const SIGN_BIT: u8 = 1 << 6; |
50 | |
51 | #[inline ] |
52 | fn low_bits_of_byte(byte: u8) -> u8 { |
53 | byte & !CONTINUATION_BIT |
54 | } |
55 | |
56 | #[inline ] |
57 | #[allow (dead_code)] |
58 | fn low_bits_of_u64(val: u64) -> u8 { |
59 | let byte: u8 = 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-core" )] |
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 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" )] |
160 | pub 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" ))] |
251 | mod 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(core::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 | |