1 /*
2
3 Copyright (C) 2000,2004 Silicon Graphics, Inc. All Rights Reserved.
4 Portions Copyright 2011 David Anderson. All Rights Reserved.
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of version 2.1 of the GNU Lesser General Public License
8 as published by the Free Software Foundation.
9
10 This program is distributed in the hope that it would be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13
14 Further, this software is distributed without any warranty that it is
15 free of the rightful claim of any third person regarding infringement
16 or the like. Any license provided herein, whether implied or
17 otherwise, applies only to this software file. Patent licenses, if
18 any, provided herein do not apply to combinations of this program with
19 other software, or any other product whatsoever.
20
21 You should have received a copy of the GNU Lesser General Public
22 License along with this program; if not, write the Free Software
23 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston MA 02110-1301,
24 USA.
25
26 */
27
28
29 #include "config.h"
30 #include "dwarf_incl.h"
31 #include <stdio.h>
32 #ifdef TESTING
33 #include "pro_encode_nm.h"
34 #endif
35
36 /* Note that with -DTESTING ('make tests')
37 many of the test items
38 only make sense if Dwarf_Unsigned (and Dwarf_Signed)
39 are 64 bits. The encode/decode logic should
40 be fine whether those types are 64 or 32 bits. */
41
42 /* 10 bytes of leb, 7 bits each part of the number, gives
43 room for a 64bit number.
44 While any number of leading zeroes would be legal, so
45 no max is really truly required here, why would a
46 compiler generate leading zeros? That would
47 be strange.
48 */
49 #define BYTESLEBMAX 10
50 #define BITSPERBYTE 8
51
52
53 /* Decode ULEB
54 Best not to use this, use _dwarf_decode_u_leb128_chk instead. */
55 Dwarf_Unsigned
_dwarf_decode_u_leb128(Dwarf_Small * leb128,Dwarf_Word * leb128_length)56 _dwarf_decode_u_leb128(Dwarf_Small * leb128, Dwarf_Word * leb128_length)
57 {
58 Dwarf_Unsigned byte = 0;
59 Dwarf_Word word_number = 0;
60 Dwarf_Unsigned number = 0;
61 unsigned shift = 0;
62 /* The byte_length value will be a small non-negative integer. */
63 unsigned byte_length = 0;
64
65 /* The following unrolls-the-loop for the first few bytes and
66 unpacks into 32 bits to make this as fast as possible.
67 word_number is assumed big enough that the shift has a defined
68 result. */
69 if ((*leb128 & 0x80) == 0) {
70 if (leb128_length) {
71 *leb128_length = 1;
72 }
73 return (*leb128);
74 } else if ((*(leb128 + 1) & 0x80) == 0) {
75 if (leb128_length) {
76 *leb128_length = 2;
77 }
78 word_number = *leb128 & 0x7f;
79 word_number |= (*(leb128 + 1) & 0x7f) << 7;
80 return (word_number);
81 } else if ((*(leb128 + 2) & 0x80) == 0) {
82 if (leb128_length) {
83 *leb128_length = 3;
84 }
85 word_number = *leb128 & 0x7f;
86 word_number |= (*(leb128 + 1) & 0x7f) << 7;
87 word_number |= (*(leb128 + 2) & 0x7f) << 14;
88 return (word_number);
89 } else if ((*(leb128 + 3) & 0x80) == 0) {
90 if (leb128_length) {
91 *leb128_length = 4;
92 }
93 word_number = *leb128 & 0x7f;
94 word_number |= (*(leb128 + 1) & 0x7f) << 7;
95 word_number |= (*(leb128 + 2) & 0x7f) << 14;
96 word_number |= (*(leb128 + 3) & 0x7f) << 21;
97 return (word_number);
98 }
99
100 /* The rest handles long numbers Because the 'number' may be larger
101 than the default int/unsigned, we must cast the 'byte' before
102 the shift for the shift to have a defined result. */
103 number = 0;
104 shift = 0;
105 byte_length = 1;
106 byte = *leb128;
107 for (;;) {
108 if (shift >= (sizeof(number)*BITSPERBYTE)) {
109 return DW_DLV_ERROR;
110 }
111 number |= (byte & 0x7f) << shift;
112 if ((byte & 0x80) == 0) {
113 if (leb128_length) {
114 *leb128_length = byte_length;
115 }
116 return (number);
117 }
118 shift += 7;
119 byte_length++;
120 if (byte_length > BYTESLEBMAX) {
121 /* Erroneous input. What to do?
122 Abort? Return error? Just stop here?
123 Call _dwarf_decode_u_leb128_chk instead. */
124 if( leb128_length) {
125 *leb128_length = BYTESLEBMAX;
126 }
127 return number;
128 }
129 ++leb128;
130 byte = *leb128;
131 }
132 }
133
134 /* Decode ULEB with checking */
135 int
_dwarf_decode_u_leb128_chk(Dwarf_Small * leb128,Dwarf_Word * leb128_length,Dwarf_Unsigned * outval,Dwarf_Byte_Ptr endptr)136 _dwarf_decode_u_leb128_chk(Dwarf_Small * leb128,
137 Dwarf_Word * leb128_length,
138 Dwarf_Unsigned *outval,
139 Dwarf_Byte_Ptr endptr)
140 {
141 Dwarf_Unsigned byte = 0;
142 Dwarf_Word word_number = 0;
143 Dwarf_Unsigned number = 0;
144 unsigned shift = 0;
145 /* The byte_length value will be a small non-negative integer. */
146 unsigned byte_length = 0;
147
148 if (leb128 >=endptr) {
149 return DW_DLV_ERROR;
150 }
151 /* The following unrolls-the-loop for the first two bytes and
152 unpacks into 32 bits to make this as fast as possible.
153 word_number is assumed big enough that the shift has a defined
154 result. */
155 if ((*leb128 & 0x80) == 0) {
156 if (leb128_length) {
157 *leb128_length = 1;
158 }
159 *outval = *leb128;
160 return DW_DLV_OK;
161 } else {
162 if ((leb128+1) >=endptr) {
163 return DW_DLV_ERROR;
164 }
165 if ((*(leb128 + 1) & 0x80) == 0) {
166 if (leb128_length) {
167 *leb128_length = 2;
168 }
169 word_number = *leb128 & 0x7f;
170 word_number |= (*(leb128 + 1) & 0x7f) << 7;
171 *outval = word_number;
172 return DW_DLV_OK;
173 }
174 /* Gets messy to hand-inline more byte checking. */
175 }
176
177 /* The rest handles long numbers Because the 'number' may be larger
178 than the default int/unsigned, we must cast the 'byte' before
179 the shift for the shift to have a defined result. */
180 number = 0;
181 shift = 0;
182 byte_length = 1;
183 byte = *leb128;
184 for (;;) {
185 if (shift >= (sizeof(number)*BITSPERBYTE)) {
186 return DW_DLV_ERROR;
187 }
188 number |= (byte & 0x7f) << shift;
189 if ((byte & 0x80) == 0) {
190 if (leb128_length) {
191 *leb128_length = byte_length;
192 }
193 *outval = number;
194 return DW_DLV_OK;
195 }
196 shift += 7;
197 byte_length++;
198 if (byte_length > BYTESLEBMAX) {
199 /* Erroneous input. */
200 if( leb128_length) {
201 *leb128_length = BYTESLEBMAX;
202 }
203 break;
204 }
205 ++leb128;
206 if ((leb128) >=endptr) {
207 return DW_DLV_ERROR;
208 }
209 byte = *leb128;
210 }
211 return DW_DLV_ERROR;
212 }
213
214
215 #define BITSINBYTE 8
216
217 /* Decode SLEB.
218 Best not to use this, use _dwarf_decode_s_leb128_chk instead. */
219 Dwarf_Signed
_dwarf_decode_s_leb128(Dwarf_Small * leb128,Dwarf_Word * leb128_length)220 _dwarf_decode_s_leb128(Dwarf_Small * leb128, Dwarf_Word * leb128_length)
221 {
222 Dwarf_Unsigned byte = *leb128;
223 Dwarf_Signed number = 0;
224 Dwarf_Bool sign = 0;
225 Dwarf_Word shift = 0;
226 /* The byte_length value will be a small non-negative integer. */
227 unsigned byte_length = 1;
228
229 /* byte_length being the number of bytes of data absorbed so far in
230 turning the leb into a Dwarf_Signed. */
231 for (;;) {
232 sign = byte & 0x40;
233 if (shift >= (sizeof(number)*BITSPERBYTE)) {
234 return DW_DLV_ERROR;
235 }
236 number |= (byte & 0x7f) << shift;
237 shift += 7;
238
239 if ((byte & 0x80) == 0) {
240 break;
241 }
242 ++leb128;
243 byte = *leb128;
244 byte_length++;
245 if (byte_length > BYTESLEBMAX) {
246 /* Erroneous input, as who would put leading
247 0x80 for leading zeros?
248 call _dwarf_decode_s_leb128_chk instead. */
249 if (leb128_length) {
250 *leb128_length = BYTESLEBMAX;
251 }
252 return number;
253 }
254 }
255
256 if (sign) {
257 /* The following avoids undefined behavior. */
258 unsigned shiftlim = sizeof(Dwarf_Signed) * BITSINBYTE -1;
259 if (shift < shiftlim) {
260 number |= -(Dwarf_Signed)(((Dwarf_Unsigned)1) << shift);
261 } else if (shift == shiftlim) {
262 number |= (((Dwarf_Unsigned)1) << shift);
263 }
264 }
265
266 if (leb128_length) {
267 *leb128_length = byte_length;
268 }
269 return number;
270 }
271
272 int
_dwarf_decode_s_leb128_chk(Dwarf_Small * leb128,Dwarf_Word * leb128_length,Dwarf_Signed * outval,Dwarf_Byte_Ptr endptr)273 _dwarf_decode_s_leb128_chk(Dwarf_Small * leb128, Dwarf_Word * leb128_length,
274 Dwarf_Signed *outval,Dwarf_Byte_Ptr endptr)
275 {
276 Dwarf_Unsigned byte = 0;
277 Dwarf_Signed number = 0;
278 Dwarf_Bool sign = 0;
279 Dwarf_Word shift = 0;
280 /* The byte_length value will be a small non-negative integer. */
281 unsigned byte_length = 1;
282
283 /* byte_length being the number of bytes of data absorbed so far in
284 turning the leb into a Dwarf_Signed. */
285 if (!outval) {
286 return DW_DLV_ERROR;
287 }
288 if (leb128 >= endptr) {
289 return DW_DLV_ERROR;
290 }
291 byte = *leb128;
292 for (;;) {
293 sign = byte & 0x40;
294 if (shift >= (sizeof(number)*BITSPERBYTE)) {
295 return DW_DLV_ERROR;
296 }
297 number |= ((Dwarf_Unsigned) ((byte & 0x7f))) << shift;
298 shift += 7;
299
300 if ((byte & 0x80) == 0) {
301 break;
302 }
303 ++leb128;
304 byte = *leb128;
305 byte_length++;
306 if (leb128 >= endptr) {
307 return DW_DLV_ERROR;
308 }
309 if (byte_length > BYTESLEBMAX) {
310 /* Erroneous input. */
311 if (leb128_length) {
312 *leb128_length = BYTESLEBMAX;
313 }
314 return DW_DLV_ERROR;
315 }
316 }
317
318 if (sign) {
319 /* The following avoids undefined behavior. */
320 unsigned shiftlim = sizeof(Dwarf_Signed) * BITSINBYTE -1;
321 if (shift < shiftlim) {
322 number |= -(Dwarf_Signed)(((Dwarf_Unsigned)1) << shift);
323 } else if (shift == shiftlim) {
324 number |= (((Dwarf_Unsigned)1) << shift);
325 }
326 }
327
328 if (leb128_length) {
329 *leb128_length = byte_length;
330 }
331 *outval = number;
332 return DW_DLV_OK;
333 }
334
335 #ifdef TESTING
336
337 static void
printinteresting(void)338 printinteresting(void)
339 {
340 return;
341 }
342
343 static Dwarf_Signed stest[] = {
344 0,0xff,
345 0x800000000000002f,
346 0x800000000000003f,
347 0x800000000000004f,
348 0x8000000000000070,
349 0x800000000000007f,
350 0x8000000000000080,
351 0x8000000000000000,
352 0x800000ffffffffff,
353 0x80000000ffffffff,
354 0x800000ffffffffff,
355 0x8000ffffffffffff,
356 0xffffffffffffffff,
357 -1703944 /*18446744073707847672 as signed*/,
358 562949951588368,
359 -1,
360 -127,
361 -100000,
362 -2000000000,
363 -4000000000,
364 -8000000000,
365 -800000000000,
366 };
367 static Dwarf_Unsigned utest[] = {
368 0,0xff,0x7f,0x80,
369 0x800000000000002f,
370 0x800000000000003f,
371 0x800000000000004f,
372 0x8000000000000070,
373 0x800000000000007f,
374 0x8000000000000080,
375 0x800000ffffffffff,
376 0x80000000ffffffff,
377 0x800000ffffffffff,
378 0x8000ffffffffffff,
379 9223372036854775808ULL,
380 -1703944 /*18446744073707847672 as signed*/,
381 562949951588368,
382 0xffff,
383 0xffffff,
384 0xffffffff,
385 0xffffffffff,
386 0xffffffffffff,
387 0xffffffffffffff,
388 0xffffffffffffffff
389 };
390
391
392 #if 0 /* FOR DEBUGGING */
393 static void
394 dump_encoded(char *space,int len)
395 {
396 int t;
397
398 printf("encode len %d: ",len);
399 for ( t = 0; t < len; ++t) {
400 printf("%02x",space[t] & 0xff);
401 }
402 printf("\n");
403 }
404 #endif
405
406
407 #define BUFFERLEN 100
408
409
410 static unsigned
signedtest(unsigned len)411 signedtest(unsigned len)
412 {
413 unsigned errcnt = 0;
414 unsigned t = 0;
415 char bufferspace[BUFFERLEN];
416
417 for ( ; t < len; ++t) {
418 int res = 0;
419 int encodelen = 0;
420 Dwarf_Word decodelen = 0;
421 Dwarf_Signed decodeval = 0;
422
423 res = _dwarf_pro_encode_signed_leb128_nm(
424 stest[t],&encodelen,bufferspace,BUFFERLEN);
425 if (res != DW_DLV_OK) {
426 printf("FAIL signed encode index %u val 0x%llx\n",
427 t,stest[t]);
428 ++errcnt;
429 }
430 res = _dwarf_decode_s_leb128_chk(
431 (Dwarf_Small *)bufferspace,
432 &decodelen,
433 &decodeval,
434 (Dwarf_Byte_Ptr)(&bufferspace[BUFFERLEN-1]));
435 if (res != DW_DLV_OK) {
436 printf("FAIL signed decode index %u val 0x%llx\n",
437 t,stest[t]);
438 ++errcnt;
439 }
440 if (stest[t] != decodeval) {
441 printf("FAIL signed decode val index %u val 0x%llx vs 0x%llx\n",
442 t,stest[t],decodeval);
443 ++errcnt;
444 }
445 if ((Dwarf_Word)encodelen != decodelen) {
446 printf("FAIL signed decodelen val index %u val 0x%llx\n",
447 t,stest[t]);
448 ++errcnt;
449 }
450 }
451 return errcnt;
452 }
453
454 static unsigned
unsignedtest(unsigned len)455 unsignedtest(unsigned len)
456 {
457 unsigned errcnt = 0;
458 unsigned t = 0;
459 char bufferspace[BUFFERLEN];
460
461 for ( ; t < len; ++t) {
462 int res = 0;
463 int encodelen = 0;
464 Dwarf_Word decodelen = 0;
465 Dwarf_Unsigned decodeval = 0;
466
467 res = _dwarf_pro_encode_leb128_nm(
468 utest[t],&encodelen,bufferspace,BUFFERLEN);
469 if (res != DW_DLV_OK) {
470 printf("FAIL signed encode index %u val 0x%llx",
471 t,utest[t]);
472 ++errcnt;
473 }
474 res = _dwarf_decode_u_leb128_chk(
475 (Dwarf_Small *)bufferspace,
476 &decodelen,
477 &decodeval,
478 (Dwarf_Byte_Ptr)(&bufferspace[BUFFERLEN-1]));
479 if (res != DW_DLV_OK) {
480 printf("FAIL signed decode index %u val 0x%llx\n",
481 t,utest[t]);
482 ++errcnt;
483 }
484 if (utest[t] != decodeval) {
485 printf("FAIL signed decode val index %u val 0x%llx vs 0x%llx\n",
486 t,utest[t],decodeval);
487 ++errcnt;
488 }
489 if ((Dwarf_Word)encodelen != decodelen) {
490 printf("FAIL signed decodelen val index %u val 0x%llx\n",
491 t,utest[t]);
492 ++errcnt;
493 }
494 }
495 return errcnt;
496 }
497 static unsigned char v1[] = {
498 0x90, 0x90, 0x90,
499 0x90, 0x90, 0x90,
500 0x90, 0x90, 0x90,
501 0x90, 0x90, 0x90,
502 0x90 };
503
504 static unsigned char v2[] = {
505 0xf4,0xff,
506 0xff,
507 0xff,
508 0x0f,
509 0x4c,
510 0x00,
511 0x00,
512 0x00};
513
514 /* 9223372036854775808 == -9223372036854775808 */
515 static unsigned char v3[] = {
516 0x80, 0x80, 0x80,
517 0x80, 0x80, 0x80,
518 0x80, 0x80, 0x80,
519 0x41 };
520
521
522 /* This warning with --enable-sanitize is fixed
523 as of November 11, 2016 when decoding test v4.
524 dwarf_leb.c: runtime error: negation of -9223372036854775808 cannot be
525 represented in type 'Dwarf_Signed' (aka 'long long');
526 cast to an unsigned type to negate this value to itself.
527 The actual value here is -4611686018427387904 0xc000000000000000 */
528 static unsigned char v4[] = {
529 0x80, 0x80, 0x80,
530 0x80, 0x80, 0x80,
531 0x80, 0x80, 0x40 };
532
533
534 static unsigned
specialtests(void)535 specialtests(void)
536 {
537 unsigned errcnt = 0;
538 unsigned vlen = 0;
539 Dwarf_Word decodelen = 0;
540 Dwarf_Signed decodeval = 0;
541 Dwarf_Unsigned udecodeval = 0;
542 int res;
543
544 vlen = sizeof(v1)/sizeof(char);
545 res = _dwarf_decode_s_leb128_chk(
546 (Dwarf_Small *)v1,
547 &decodelen,
548 &decodeval,
549 (Dwarf_Byte_Ptr)(&v1[vlen]));
550 if (res != DW_DLV_ERROR) {
551 printf("FAIL unsigned decode special v1 \n");
552 ++errcnt;
553 }
554 res = _dwarf_decode_u_leb128_chk(
555 (Dwarf_Small *)v1,
556 &decodelen,
557 &udecodeval,
558 (Dwarf_Byte_Ptr)(&v1[vlen]));
559 if (res != DW_DLV_ERROR) {
560 printf("FAIL unsigned decode special v1 \n");
561 ++errcnt;
562 }
563
564 vlen = sizeof(v2)/sizeof(char);
565 res = _dwarf_decode_s_leb128_chk(
566 (Dwarf_Small *)v2,
567 &decodelen,
568 &decodeval,
569 (Dwarf_Byte_Ptr)(&v2[vlen]));
570 if (res != DW_DLV_OK) {
571 printf("FAIL signed decode special v2 \n");
572 ++errcnt;
573 }
574 /* If you just do (byte & 0x7f) << shift
575 and byte is (or is promoted to) a signed type
576 on the following decode you get the wrong value.
577 Undefined effect in C leads to error. */
578 res = _dwarf_decode_u_leb128_chk(
579 (Dwarf_Small *)v2,
580 &decodelen,
581 &udecodeval,
582 (Dwarf_Byte_Ptr)(&v2[vlen]));
583 if (res != DW_DLV_OK) {
584 printf("FAIL unsigned decode special v2 \n");
585 ++errcnt;
586 }
587
588 vlen = sizeof(v3)/sizeof(char);
589 res = _dwarf_decode_s_leb128_chk(
590 (Dwarf_Small *)v3,
591 &decodelen,
592 &decodeval,
593 (Dwarf_Byte_Ptr)(&v3[vlen]));
594 if (res != DW_DLV_OK) {
595 printf("FAIL signed decode special v3 \n");
596 ++errcnt;
597 }
598 if (decodeval != 0x8000000000000000) {
599 printf("FAIL signed decode special v3 value check %lld vs %lld \n",
600 decodeval,(Dwarf_Signed)0x8000000000000000);
601 ++errcnt;
602 }
603
604 vlen = sizeof(v4)/sizeof(char);
605 res = _dwarf_decode_s_leb128_chk(
606 (Dwarf_Small *)v4,
607 &decodelen,
608 &decodeval,
609 (Dwarf_Byte_Ptr)(&v4[vlen]));
610 if (res != DW_DLV_OK) {
611 printf("FAIL signed decode special v4 \n");
612 ++errcnt;
613 }
614 if (decodeval != -4611686018427387904) {
615 printf("FAIL signed decode special v4 value check %lld vs %lld \n",
616 decodeval,-4611686018427387904LL);
617 printf("FAIL signed decode special v4 value check 0x%llx vs 0x%llx \n",
618 decodeval,-4611686018427387904LL);
619 ++errcnt;
620 }
621
622 return errcnt;
623
624 return errcnt;
625 }
626
main(void)627 int main(void)
628 {
629 unsigned slen = sizeof(stest)/sizeof(Dwarf_Signed);
630 unsigned ulen = sizeof(utest)/sizeof(Dwarf_Unsigned);
631 int errs = 0;
632
633 printinteresting();
634 errs += signedtest(slen);
635
636 errs += unsignedtest(ulen);
637
638 errs += specialtests();
639
640 if (errs) {
641 printf("FAIL. leb encode/decode errors\n");
642 return 1;
643 }
644 printf("PASS leb tests\n");
645 return 0;
646 }
647 #endif /* TESTING */
648
649