1/* elf.c -- Get debug data from an ELF file for backtraces.
2 Copyright (C) 2012-2023 Free Software Foundation, Inc.
3 Written by Ian Lance Taylor, Google.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are
7met:
8
9 (1) Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 (2) Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the
15 distribution.
16
17 (3) The name of the author may not be used to
18 endorse or promote products derived from this software without
19 specific prior written permission.
20
21THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31POSSIBILITY OF SUCH DAMAGE. */
32
33#include "config.h"
34
35#include <errno.h>
36#include <stdlib.h>
37#include <string.h>
38#include <sys/types.h>
39#include <sys/stat.h>
40#include <unistd.h>
41
42#ifdef HAVE_DL_ITERATE_PHDR
43 #ifdef HAVE_LINK_H
44 #include <link.h>
45 #endif
46 #ifdef HAVE_SYS_LINK_H
47 #include <sys/link.h>
48 #endif
49#endif
50
51#include "backtrace.h"
52#include "internal.h"
53
54#ifndef S_ISLNK
55 #ifndef S_IFLNK
56 #define S_IFLNK 0120000
57 #endif
58 #ifndef S_IFMT
59 #define S_IFMT 0170000
60 #endif
61 #define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
62#endif
63
64#ifndef __GNUC__
65#define __builtin_prefetch(p, r, l)
66#define unlikely(x) (x)
67#else
68#define unlikely(x) __builtin_expect(!!(x), 0)
69#endif
70
71#if !defined(HAVE_DECL_STRNLEN) || !HAVE_DECL_STRNLEN
72
73/* If strnlen is not declared, provide our own version. */
74
75static size_t
76xstrnlen (const char *s, size_t maxlen)
77{
78 size_t i;
79
80 for (i = 0; i < maxlen; ++i)
81 if (s[i] == '\0')
82 break;
83 return i;
84}
85
86#define strnlen xstrnlen
87
88#endif
89
90#ifndef HAVE_LSTAT
91
92/* Dummy version of lstat for systems that don't have it. */
93
94static int
95xlstat (const char *path ATTRIBUTE_UNUSED, struct stat *st ATTRIBUTE_UNUSED)
96{
97 return -1;
98}
99
100#define lstat xlstat
101
102#endif
103
104#ifndef HAVE_READLINK
105
106/* Dummy version of readlink for systems that don't have it. */
107
108static ssize_t
109xreadlink (const char *path ATTRIBUTE_UNUSED, char *buf ATTRIBUTE_UNUSED,
110 size_t bufsz ATTRIBUTE_UNUSED)
111{
112 return -1;
113}
114
115#define readlink xreadlink
116
117#endif
118
119#ifndef HAVE_DL_ITERATE_PHDR
120
121/* Dummy version of dl_iterate_phdr for systems that don't have it. */
122
123#define dl_phdr_info x_dl_phdr_info
124#define dl_iterate_phdr x_dl_iterate_phdr
125
126struct dl_phdr_info
127{
128 uintptr_t dlpi_addr;
129 const char *dlpi_name;
130};
131
132static int
133dl_iterate_phdr (int (*callback) (struct dl_phdr_info *,
134 size_t, void *) ATTRIBUTE_UNUSED,
135 void *data ATTRIBUTE_UNUSED)
136{
137 return 0;
138}
139
140#endif /* ! defined (HAVE_DL_ITERATE_PHDR) */
141
142/* The configure script must tell us whether we are 32-bit or 64-bit
143 ELF. We could make this code test and support either possibility,
144 but there is no point. This code only works for the currently
145 running executable, which means that we know the ELF mode at
146 configure time. */
147
148#if BACKTRACE_ELF_SIZE != 32 && BACKTRACE_ELF_SIZE != 64
149#error "Unknown BACKTRACE_ELF_SIZE"
150#endif
151
152/* <link.h> might #include <elf.h> which might define our constants
153 with slightly different values. Undefine them to be safe. */
154
155#undef EI_NIDENT
156#undef EI_MAG0
157#undef EI_MAG1
158#undef EI_MAG2
159#undef EI_MAG3
160#undef EI_CLASS
161#undef EI_DATA
162#undef EI_VERSION
163#undef ELF_MAG0
164#undef ELF_MAG1
165#undef ELF_MAG2
166#undef ELF_MAG3
167#undef ELFCLASS32
168#undef ELFCLASS64
169#undef ELFDATA2LSB
170#undef ELFDATA2MSB
171#undef EV_CURRENT
172#undef ET_DYN
173#undef EM_PPC64
174#undef EF_PPC64_ABI
175#undef SHN_LORESERVE
176#undef SHN_XINDEX
177#undef SHN_UNDEF
178#undef SHT_PROGBITS
179#undef SHT_SYMTAB
180#undef SHT_STRTAB
181#undef SHT_DYNSYM
182#undef SHF_COMPRESSED
183#undef STT_OBJECT
184#undef STT_FUNC
185#undef NT_GNU_BUILD_ID
186#undef ELFCOMPRESS_ZLIB
187#undef ELFCOMPRESS_ZSTD
188
189/* Basic types. */
190
191typedef uint16_t b_elf_half; /* Elf_Half. */
192typedef uint32_t b_elf_word; /* Elf_Word. */
193typedef int32_t b_elf_sword; /* Elf_Sword. */
194
195#if BACKTRACE_ELF_SIZE == 32
196
197typedef uint32_t b_elf_addr; /* Elf_Addr. */
198typedef uint32_t b_elf_off; /* Elf_Off. */
199
200typedef uint32_t b_elf_wxword; /* 32-bit Elf_Word, 64-bit ELF_Xword. */
201
202#else
203
204typedef uint64_t b_elf_addr; /* Elf_Addr. */
205typedef uint64_t b_elf_off; /* Elf_Off. */
206typedef uint64_t b_elf_xword; /* Elf_Xword. */
207typedef int64_t b_elf_sxword; /* Elf_Sxword. */
208
209typedef uint64_t b_elf_wxword; /* 32-bit Elf_Word, 64-bit ELF_Xword. */
210
211#endif
212
213/* Data structures and associated constants. */
214
215#define EI_NIDENT 16
216
217typedef struct {
218 unsigned char e_ident[EI_NIDENT]; /* ELF "magic number" */
219 b_elf_half e_type; /* Identifies object file type */
220 b_elf_half e_machine; /* Specifies required architecture */
221 b_elf_word e_version; /* Identifies object file version */
222 b_elf_addr e_entry; /* Entry point virtual address */
223 b_elf_off e_phoff; /* Program header table file offset */
224 b_elf_off e_shoff; /* Section header table file offset */
225 b_elf_word e_flags; /* Processor-specific flags */
226 b_elf_half e_ehsize; /* ELF header size in bytes */
227 b_elf_half e_phentsize; /* Program header table entry size */
228 b_elf_half e_phnum; /* Program header table entry count */
229 b_elf_half e_shentsize; /* Section header table entry size */
230 b_elf_half e_shnum; /* Section header table entry count */
231 b_elf_half e_shstrndx; /* Section header string table index */
232} b_elf_ehdr; /* Elf_Ehdr. */
233
234#define EI_MAG0 0
235#define EI_MAG1 1
236#define EI_MAG2 2
237#define EI_MAG3 3
238#define EI_CLASS 4
239#define EI_DATA 5
240#define EI_VERSION 6
241
242#define ELFMAG0 0x7f
243#define ELFMAG1 'E'
244#define ELFMAG2 'L'
245#define ELFMAG3 'F'
246
247#define ELFCLASS32 1
248#define ELFCLASS64 2
249
250#define ELFDATA2LSB 1
251#define ELFDATA2MSB 2
252
253#define EV_CURRENT 1
254
255#define ET_DYN 3
256
257#define EM_PPC64 21
258#define EF_PPC64_ABI 3
259
260typedef struct {
261 b_elf_word sh_name; /* Section name, index in string tbl */
262 b_elf_word sh_type; /* Type of section */
263 b_elf_wxword sh_flags; /* Miscellaneous section attributes */
264 b_elf_addr sh_addr; /* Section virtual addr at execution */
265 b_elf_off sh_offset; /* Section file offset */
266 b_elf_wxword sh_size; /* Size of section in bytes */
267 b_elf_word sh_link; /* Index of another section */
268 b_elf_word sh_info; /* Additional section information */
269 b_elf_wxword sh_addralign; /* Section alignment */
270 b_elf_wxword sh_entsize; /* Entry size if section holds table */
271} b_elf_shdr; /* Elf_Shdr. */
272
273#define SHN_UNDEF 0x0000 /* Undefined section */
274#define SHN_LORESERVE 0xFF00 /* Begin range of reserved indices */
275#define SHN_XINDEX 0xFFFF /* Section index is held elsewhere */
276
277#define SHT_PROGBITS 1
278#define SHT_SYMTAB 2
279#define SHT_STRTAB 3
280#define SHT_DYNSYM 11
281
282#define SHF_COMPRESSED 0x800
283
284#if BACKTRACE_ELF_SIZE == 32
285
286typedef struct
287{
288 b_elf_word st_name; /* Symbol name, index in string tbl */
289 b_elf_addr st_value; /* Symbol value */
290 b_elf_word st_size; /* Symbol size */
291 unsigned char st_info; /* Symbol binding and type */
292 unsigned char st_other; /* Visibility and other data */
293 b_elf_half st_shndx; /* Symbol section index */
294} b_elf_sym; /* Elf_Sym. */
295
296#else /* BACKTRACE_ELF_SIZE != 32 */
297
298typedef struct
299{
300 b_elf_word st_name; /* Symbol name, index in string tbl */
301 unsigned char st_info; /* Symbol binding and type */
302 unsigned char st_other; /* Visibility and other data */
303 b_elf_half st_shndx; /* Symbol section index */
304 b_elf_addr st_value; /* Symbol value */
305 b_elf_xword st_size; /* Symbol size */
306} b_elf_sym; /* Elf_Sym. */
307
308#endif /* BACKTRACE_ELF_SIZE != 32 */
309
310#define STT_OBJECT 1
311#define STT_FUNC 2
312
313typedef struct
314{
315 uint32_t namesz;
316 uint32_t descsz;
317 uint32_t type;
318 char name[1];
319} b_elf_note;
320
321#define NT_GNU_BUILD_ID 3
322
323#if BACKTRACE_ELF_SIZE == 32
324
325typedef struct
326{
327 b_elf_word ch_type; /* Compresstion algorithm */
328 b_elf_word ch_size; /* Uncompressed size */
329 b_elf_word ch_addralign; /* Alignment for uncompressed data */
330} b_elf_chdr; /* Elf_Chdr */
331
332#else /* BACKTRACE_ELF_SIZE != 32 */
333
334typedef struct
335{
336 b_elf_word ch_type; /* Compression algorithm */
337 b_elf_word ch_reserved; /* Reserved */
338 b_elf_xword ch_size; /* Uncompressed size */
339 b_elf_xword ch_addralign; /* Alignment for uncompressed data */
340} b_elf_chdr; /* Elf_Chdr */
341
342#endif /* BACKTRACE_ELF_SIZE != 32 */
343
344#define ELFCOMPRESS_ZLIB 1
345#define ELFCOMPRESS_ZSTD 2
346
347/* Names of sections, indexed by enum dwarf_section in internal.h. */
348
349static const char * const dwarf_section_names[DEBUG_MAX] =
350{
351 ".debug_info",
352 ".debug_line",
353 ".debug_abbrev",
354 ".debug_ranges",
355 ".debug_str",
356 ".debug_addr",
357 ".debug_str_offsets",
358 ".debug_line_str",
359 ".debug_rnglists"
360};
361
362/* Information we gather for the sections we care about. */
363
364struct debug_section_info
365{
366 /* Section file offset. */
367 off_t offset;
368 /* Section size. */
369 size_t size;
370 /* Section contents, after read from file. */
371 const unsigned char *data;
372 /* Whether the SHF_COMPRESSED flag is set for the section. */
373 int compressed;
374};
375
376/* Information we keep for an ELF symbol. */
377
378struct elf_symbol
379{
380 /* The name of the symbol. */
381 const char *name;
382 /* The address of the symbol. */
383 uintptr_t address;
384 /* The size of the symbol. */
385 size_t size;
386};
387
388/* Information to pass to elf_syminfo. */
389
390struct elf_syminfo_data
391{
392 /* Symbols for the next module. */
393 struct elf_syminfo_data *next;
394 /* The ELF symbols, sorted by address. */
395 struct elf_symbol *symbols;
396 /* The number of symbols. */
397 size_t count;
398};
399
400/* A view that works for either a file or memory. */
401
402struct elf_view
403{
404 struct backtrace_view view;
405 int release; /* If non-zero, must call backtrace_release_view. */
406};
407
408/* Information about PowerPC64 ELFv1 .opd section. */
409
410struct elf_ppc64_opd_data
411{
412 /* Address of the .opd section. */
413 b_elf_addr addr;
414 /* Section data. */
415 const char *data;
416 /* Size of the .opd section. */
417 size_t size;
418 /* Corresponding section view. */
419 struct elf_view view;
420};
421
422/* Create a view of SIZE bytes from DESCRIPTOR/MEMORY at OFFSET. */
423
424static int
425elf_get_view (struct backtrace_state *state, int descriptor,
426 const unsigned char *memory, size_t memory_size, off_t offset,
427 uint64_t size, backtrace_error_callback error_callback,
428 void *data, struct elf_view *view)
429{
430 if (memory == NULL)
431 {
432 view->release = 1;
433 return backtrace_get_view (state, descriptor, offset, size,
434 error_callback, data, view: &view->view);
435 }
436 else
437 {
438 if ((uint64_t) offset + size > (uint64_t) memory_size)
439 {
440 error_callback (data, "out of range for in-memory file", 0);
441 return 0;
442 }
443 view->view.data = (const void *) (memory + offset);
444 view->view.base = NULL;
445 view->view.len = size;
446 view->release = 0;
447 return 1;
448 }
449}
450
451/* Release a view read by elf_get_view. */
452
453static void
454elf_release_view (struct backtrace_state *state, struct elf_view *view,
455 backtrace_error_callback error_callback, void *data)
456{
457 if (view->release)
458 backtrace_release_view (state, view: &view->view, error_callback, data);
459}
460
461/* Compute the CRC-32 of BUF/LEN. This uses the CRC used for
462 .gnu_debuglink files. */
463
464static uint32_t
465elf_crc32 (uint32_t crc, const unsigned char *buf, size_t len)
466{
467 static const uint32_t crc32_table[256] =
468 {
469 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
470 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
471 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
472 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
473 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
474 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
475 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
476 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
477 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
478 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
479 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
480 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
481 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
482 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
483 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
484 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
485 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
486 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
487 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
488 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
489 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
490 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
491 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
492 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
493 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
494 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
495 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
496 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
497 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
498 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
499 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
500 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
501 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
502 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
503 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
504 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
505 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
506 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
507 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
508 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
509 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
510 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
511 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
512 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
513 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
514 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
515 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
516 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
517 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
518 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
519 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
520 0x2d02ef8d
521 };
522 const unsigned char *end;
523
524 crc = ~crc;
525 for (end = buf + len; buf < end; ++ buf)
526 crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8);
527 return ~crc;
528}
529
530/* Return the CRC-32 of the entire file open at DESCRIPTOR. */
531
532static uint32_t
533elf_crc32_file (struct backtrace_state *state, int descriptor,
534 backtrace_error_callback error_callback, void *data)
535{
536 struct stat st;
537 struct backtrace_view file_view;
538 uint32_t ret;
539
540 if (fstat (fd: descriptor, buf: &st) < 0)
541 {
542 error_callback (data, "fstat", errno);
543 return 0;
544 }
545
546 if (!backtrace_get_view (state, descriptor, offset: 0, size: st.st_size, error_callback,
547 data, view: &file_view))
548 return 0;
549
550 ret = elf_crc32 (crc: 0, buf: (const unsigned char *) file_view.data, len: st.st_size);
551
552 backtrace_release_view (state, view: &file_view, error_callback, data);
553
554 return ret;
555}
556
557/* A dummy callback function used when we can't find a symbol
558 table. */
559
560static void
561elf_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
562 uintptr_t addr ATTRIBUTE_UNUSED,
563 backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
564 backtrace_error_callback error_callback, void *data)
565{
566 error_callback (data, "no symbol table in ELF executable", -1);
567}
568
569/* A callback function used when we can't find any debug info. */
570
571static int
572elf_nodebug (struct backtrace_state *state, uintptr_t pc,
573 backtrace_full_callback callback,
574 backtrace_error_callback error_callback, void *data)
575{
576 if (state->syminfo_fn != NULL && state->syminfo_fn != elf_nosyms)
577 {
578 struct backtrace_call_full bdata;
579
580 /* Fetch symbol information so that we can least get the
581 function name. */
582
583 bdata.full_callback = callback;
584 bdata.full_error_callback = error_callback;
585 bdata.full_data = data;
586 bdata.ret = 0;
587 state->syminfo_fn (state, pc, backtrace_syminfo_to_full_callback,
588 backtrace_syminfo_to_full_error_callback, &bdata);
589 return bdata.ret;
590 }
591
592 error_callback (data, "no debug info in ELF executable", -1);
593 return 0;
594}
595
596/* Compare struct elf_symbol for qsort. */
597
598static int
599elf_symbol_compare (const void *v1, const void *v2)
600{
601 const struct elf_symbol *e1 = (const struct elf_symbol *) v1;
602 const struct elf_symbol *e2 = (const struct elf_symbol *) v2;
603
604 if (e1->address < e2->address)
605 return -1;
606 else if (e1->address > e2->address)
607 return 1;
608 else
609 return 0;
610}
611
612/* Compare an ADDR against an elf_symbol for bsearch. We allocate one
613 extra entry in the array so that this can look safely at the next
614 entry. */
615
616static int
617elf_symbol_search (const void *vkey, const void *ventry)
618{
619 const uintptr_t *key = (const uintptr_t *) vkey;
620 const struct elf_symbol *entry = (const struct elf_symbol *) ventry;
621 uintptr_t addr;
622
623 addr = *key;
624 if (addr < entry->address)
625 return -1;
626 else if (addr >= entry->address + entry->size)
627 return 1;
628 else
629 return 0;
630}
631
632/* Initialize the symbol table info for elf_syminfo. */
633
634static int
635elf_initialize_syminfo (struct backtrace_state *state,
636 uintptr_t base_address,
637 const unsigned char *symtab_data, size_t symtab_size,
638 const unsigned char *strtab, size_t strtab_size,
639 backtrace_error_callback error_callback,
640 void *data, struct elf_syminfo_data *sdata,
641 struct elf_ppc64_opd_data *opd)
642{
643 size_t sym_count;
644 const b_elf_sym *sym;
645 size_t elf_symbol_count;
646 size_t elf_symbol_size;
647 struct elf_symbol *elf_symbols;
648 size_t i;
649 unsigned int j;
650
651 sym_count = symtab_size / sizeof (b_elf_sym);
652
653 /* We only care about function symbols. Count them. */
654 sym = (const b_elf_sym *) symtab_data;
655 elf_symbol_count = 0;
656 for (i = 0; i < sym_count; ++i, ++sym)
657 {
658 int info;
659
660 info = sym->st_info & 0xf;
661 if ((info == STT_FUNC || info == STT_OBJECT)
662 && sym->st_shndx != SHN_UNDEF)
663 ++elf_symbol_count;
664 }
665
666 elf_symbol_size = elf_symbol_count * sizeof (struct elf_symbol);
667 elf_symbols = ((struct elf_symbol *)
668 backtrace_alloc (state, size: elf_symbol_size, error_callback,
669 data));
670 if (elf_symbols == NULL)
671 return 0;
672
673 sym = (const b_elf_sym *) symtab_data;
674 j = 0;
675 for (i = 0; i < sym_count; ++i, ++sym)
676 {
677 int info;
678
679 info = sym->st_info & 0xf;
680 if (info != STT_FUNC && info != STT_OBJECT)
681 continue;
682 if (sym->st_shndx == SHN_UNDEF)
683 continue;
684 if (sym->st_name >= strtab_size)
685 {
686 error_callback (data, "symbol string index out of range", 0);
687 backtrace_free (state, mem: elf_symbols, size: elf_symbol_size, error_callback,
688 data);
689 return 0;
690 }
691 elf_symbols[j].name = (const char *) strtab + sym->st_name;
692 /* Special case PowerPC64 ELFv1 symbols in .opd section, if the symbol
693 is a function descriptor, read the actual code address from the
694 descriptor. */
695 if (opd
696 && sym->st_value >= opd->addr
697 && sym->st_value < opd->addr + opd->size)
698 elf_symbols[j].address
699 = *(const b_elf_addr *) (opd->data + (sym->st_value - opd->addr));
700 else
701 elf_symbols[j].address = sym->st_value;
702 elf_symbols[j].address += base_address;
703 elf_symbols[j].size = sym->st_size;
704 ++j;
705 }
706
707 backtrace_qsort (base: elf_symbols, count: elf_symbol_count, size: sizeof (struct elf_symbol),
708 compar: elf_symbol_compare);
709
710 sdata->next = NULL;
711 sdata->symbols = elf_symbols;
712 sdata->count = elf_symbol_count;
713
714 return 1;
715}
716
717/* Add EDATA to the list in STATE. */
718
719static void
720elf_add_syminfo_data (struct backtrace_state *state,
721 struct elf_syminfo_data *edata)
722{
723 if (!state->threaded)
724 {
725 struct elf_syminfo_data **pp;
726
727 for (pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
728 *pp != NULL;
729 pp = &(*pp)->next)
730 ;
731 *pp = edata;
732 }
733 else
734 {
735 while (1)
736 {
737 struct elf_syminfo_data **pp;
738
739 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
740
741 while (1)
742 {
743 struct elf_syminfo_data *p;
744
745 p = backtrace_atomic_load_pointer (pp);
746
747 if (p == NULL)
748 break;
749
750 pp = &p->next;
751 }
752
753 if (__sync_bool_compare_and_swap (pp, NULL, edata))
754 break;
755 }
756 }
757}
758
759/* Return the symbol name and value for an ADDR. */
760
761static void
762elf_syminfo (struct backtrace_state *state, uintptr_t addr,
763 backtrace_syminfo_callback callback,
764 backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
765 void *data)
766{
767 struct elf_syminfo_data *edata;
768 struct elf_symbol *sym = NULL;
769
770 if (!state->threaded)
771 {
772 for (edata = (struct elf_syminfo_data *) state->syminfo_data;
773 edata != NULL;
774 edata = edata->next)
775 {
776 sym = ((struct elf_symbol *)
777 bsearch (key: &addr, base: edata->symbols, nmemb: edata->count,
778 size: sizeof (struct elf_symbol), compar: elf_symbol_search));
779 if (sym != NULL)
780 break;
781 }
782 }
783 else
784 {
785 struct elf_syminfo_data **pp;
786
787 pp = (struct elf_syminfo_data **) (void *) &state->syminfo_data;
788 while (1)
789 {
790 edata = backtrace_atomic_load_pointer (pp);
791 if (edata == NULL)
792 break;
793
794 sym = ((struct elf_symbol *)
795 bsearch (key: &addr, base: edata->symbols, nmemb: edata->count,
796 size: sizeof (struct elf_symbol), compar: elf_symbol_search));
797 if (sym != NULL)
798 break;
799
800 pp = &edata->next;
801 }
802 }
803
804 if (sym == NULL)
805 callback (data, addr, NULL, 0, 0);
806 else
807 callback (data, addr, sym->name, sym->address, sym->size);
808}
809
810/* Return whether FILENAME is a symlink. */
811
812static int
813elf_is_symlink (const char *filename)
814{
815 struct stat st;
816
817 if (lstat (file: filename, buf: &st) < 0)
818 return 0;
819 return S_ISLNK (st.st_mode);
820}
821
822/* Return the results of reading the symlink FILENAME in a buffer
823 allocated by backtrace_alloc. Return the length of the buffer in
824 *LEN. */
825
826static char *
827elf_readlink (struct backtrace_state *state, const char *filename,
828 backtrace_error_callback error_callback, void *data,
829 size_t *plen)
830{
831 size_t len;
832 char *buf;
833
834 len = 128;
835 while (1)
836 {
837 ssize_t rl;
838
839 buf = backtrace_alloc (state, size: len, error_callback, data);
840 if (buf == NULL)
841 return NULL;
842 rl = readlink (path: filename, buf: buf, len: len);
843 if (rl < 0)
844 {
845 backtrace_free (state, mem: buf, size: len, error_callback, data);
846 return NULL;
847 }
848 if ((size_t) rl < len - 1)
849 {
850 buf[rl] = '\0';
851 *plen = len;
852 return buf;
853 }
854 backtrace_free (state, mem: buf, size: len, error_callback, data);
855 len *= 2;
856 }
857}
858
859#define SYSTEM_BUILD_ID_DIR "/usr/lib/debug/.build-id/"
860
861/* Open a separate debug info file, using the build ID to find it.
862 Returns an open file descriptor, or -1.
863
864 The GDB manual says that the only place gdb looks for a debug file
865 when the build ID is known is in /usr/lib/debug/.build-id. */
866
867static int
868elf_open_debugfile_by_buildid (struct backtrace_state *state,
869 const char *buildid_data, size_t buildid_size,
870 backtrace_error_callback error_callback,
871 void *data)
872{
873 const char * const prefix = SYSTEM_BUILD_ID_DIR;
874 const size_t prefix_len = strlen (s: prefix);
875 const char * const suffix = ".debug";
876 const size_t suffix_len = strlen (s: suffix);
877 size_t len;
878 char *bd_filename;
879 char *t;
880 size_t i;
881 int ret;
882 int does_not_exist;
883
884 len = prefix_len + buildid_size * 2 + suffix_len + 2;
885 bd_filename = backtrace_alloc (state, size: len, error_callback, data);
886 if (bd_filename == NULL)
887 return -1;
888
889 t = bd_filename;
890 memcpy (dest: t, src: prefix, n: prefix_len);
891 t += prefix_len;
892 for (i = 0; i < buildid_size; i++)
893 {
894 unsigned char b;
895 unsigned char nib;
896
897 b = (unsigned char) buildid_data[i];
898 nib = (b & 0xf0) >> 4;
899 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
900 nib = b & 0x0f;
901 *t++ = nib < 10 ? '0' + nib : 'a' + nib - 10;
902 if (i == 0)
903 *t++ = '/';
904 }
905 memcpy (dest: t, src: suffix, n: suffix_len);
906 t[suffix_len] = '\0';
907
908 ret = backtrace_open (filename: bd_filename, error_callback, data, does_not_exist: &does_not_exist);
909
910 backtrace_free (state, mem: bd_filename, size: len, error_callback, data);
911
912 /* gdb checks that the debuginfo file has the same build ID note.
913 That seems kind of pointless to me--why would it have the right
914 name but not the right build ID?--so skipping the check. */
915
916 return ret;
917}
918
919/* Try to open a file whose name is PREFIX (length PREFIX_LEN)
920 concatenated with PREFIX2 (length PREFIX2_LEN) concatenated with
921 DEBUGLINK_NAME. Returns an open file descriptor, or -1. */
922
923static int
924elf_try_debugfile (struct backtrace_state *state, const char *prefix,
925 size_t prefix_len, const char *prefix2, size_t prefix2_len,
926 const char *debuglink_name,
927 backtrace_error_callback error_callback, void *data)
928{
929 size_t debuglink_len;
930 size_t try_len;
931 char *try;
932 int does_not_exist;
933 int ret;
934
935 debuglink_len = strlen (s: debuglink_name);
936 try_len = prefix_len + prefix2_len + debuglink_len + 1;
937 try = backtrace_alloc (state, try_len, error_callback, data);
938 if (try == NULL)
939 return -1;
940
941 memcpy (try, prefix, prefix_len);
942 memcpy (try + prefix_len, prefix2, prefix2_len);
943 memcpy (try + prefix_len + prefix2_len, debuglink_name, debuglink_len);
944 try[prefix_len + prefix2_len + debuglink_len] = '\0';
945
946 ret = backtrace_open (try, error_callback, data, &does_not_exist);
947
948 backtrace_free (state, try, try_len, error_callback, data);
949
950 return ret;
951}
952
953/* Find a separate debug info file, using the debuglink section data
954 to find it. Returns an open file descriptor, or -1. */
955
956static int
957elf_find_debugfile_by_debuglink (struct backtrace_state *state,
958 const char *filename,
959 const char *debuglink_name,
960 backtrace_error_callback error_callback,
961 void *data)
962{
963 int ret;
964 char *alc;
965 size_t alc_len;
966 const char *slash;
967 int ddescriptor;
968 const char *prefix;
969 size_t prefix_len;
970
971 /* Resolve symlinks in FILENAME. Since FILENAME is fairly likely to
972 be /proc/self/exe, symlinks are common. We don't try to resolve
973 the whole path name, just the base name. */
974 ret = -1;
975 alc = NULL;
976 alc_len = 0;
977 while (elf_is_symlink (filename))
978 {
979 char *new_buf;
980 size_t new_len;
981
982 new_buf = elf_readlink (state, filename, error_callback, data, plen: &new_len);
983 if (new_buf == NULL)
984 break;
985
986 if (new_buf[0] == '/')
987 filename = new_buf;
988 else
989 {
990 slash = strrchr (s: filename, c: '/');
991 if (slash == NULL)
992 filename = new_buf;
993 else
994 {
995 size_t clen;
996 char *c;
997
998 slash++;
999 clen = slash - filename + strlen (s: new_buf) + 1;
1000 c = backtrace_alloc (state, size: clen, error_callback, data);
1001 if (c == NULL)
1002 goto done;
1003
1004 memcpy (dest: c, src: filename, n: slash - filename);
1005 memcpy (dest: c + (slash - filename), src: new_buf, n: strlen (s: new_buf));
1006 c[slash - filename + strlen (s: new_buf)] = '\0';
1007 backtrace_free (state, mem: new_buf, size: new_len, error_callback, data);
1008 filename = c;
1009 new_buf = c;
1010 new_len = clen;
1011 }
1012 }
1013
1014 if (alc != NULL)
1015 backtrace_free (state, mem: alc, size: alc_len, error_callback, data);
1016 alc = new_buf;
1017 alc_len = new_len;
1018 }
1019
1020 /* Look for DEBUGLINK_NAME in the same directory as FILENAME. */
1021
1022 slash = strrchr (s: filename, c: '/');
1023 if (slash == NULL)
1024 {
1025 prefix = "";
1026 prefix_len = 0;
1027 }
1028 else
1029 {
1030 slash++;
1031 prefix = filename;
1032 prefix_len = slash - filename;
1033 }
1034
1035 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, prefix2: "", prefix2_len: 0,
1036 debuglink_name, error_callback, data);
1037 if (ddescriptor >= 0)
1038 {
1039 ret = ddescriptor;
1040 goto done;
1041 }
1042
1043 /* Look for DEBUGLINK_NAME in a .debug subdirectory of FILENAME. */
1044
1045 ddescriptor = elf_try_debugfile (state, prefix, prefix_len, prefix2: ".debug/",
1046 prefix2_len: strlen (s: ".debug/"), debuglink_name,
1047 error_callback, data);
1048 if (ddescriptor >= 0)
1049 {
1050 ret = ddescriptor;
1051 goto done;
1052 }
1053
1054 /* Look for DEBUGLINK_NAME in /usr/lib/debug. */
1055
1056 ddescriptor = elf_try_debugfile (state, prefix: "/usr/lib/debug/",
1057 prefix_len: strlen (s: "/usr/lib/debug/"), prefix2: prefix,
1058 prefix2_len: prefix_len, debuglink_name,
1059 error_callback, data);
1060 if (ddescriptor >= 0)
1061 ret = ddescriptor;
1062
1063 done:
1064 if (alc != NULL && alc_len > 0)
1065 backtrace_free (state, mem: alc, size: alc_len, error_callback, data);
1066 return ret;
1067}
1068
1069/* Open a separate debug info file, using the debuglink section data
1070 to find it. Returns an open file descriptor, or -1. */
1071
1072static int
1073elf_open_debugfile_by_debuglink (struct backtrace_state *state,
1074 const char *filename,
1075 const char *debuglink_name,
1076 uint32_t debuglink_crc,
1077 backtrace_error_callback error_callback,
1078 void *data)
1079{
1080 int ddescriptor;
1081
1082 ddescriptor = elf_find_debugfile_by_debuglink (state, filename,
1083 debuglink_name,
1084 error_callback, data);
1085 if (ddescriptor < 0)
1086 return -1;
1087
1088 if (debuglink_crc != 0)
1089 {
1090 uint32_t got_crc;
1091
1092 got_crc = elf_crc32_file (state, descriptor: ddescriptor, error_callback, data);
1093 if (got_crc != debuglink_crc)
1094 {
1095 backtrace_close (descriptor: ddescriptor, error_callback, data);
1096 return -1;
1097 }
1098 }
1099
1100 return ddescriptor;
1101}
1102
1103/* A function useful for setting a breakpoint for an inflation failure
1104 when this code is compiled with -g. */
1105
1106static void
1107elf_uncompress_failed(void)
1108{
1109}
1110
1111/* *PVAL is the current value being read from the stream, and *PBITS
1112 is the number of valid bits. Ensure that *PVAL holds at least 15
1113 bits by reading additional bits from *PPIN, up to PINEND, as
1114 needed. Updates *PPIN, *PVAL and *PBITS. Returns 1 on success, 0
1115 on error. */
1116
1117static int
1118elf_fetch_bits (const unsigned char **ppin, const unsigned char *pinend,
1119 uint64_t *pval, unsigned int *pbits)
1120{
1121 unsigned int bits;
1122 const unsigned char *pin;
1123 uint64_t val;
1124 uint32_t next;
1125
1126 bits = *pbits;
1127 if (bits >= 15)
1128 return 1;
1129 pin = *ppin;
1130 val = *pval;
1131
1132 if (unlikely (pinend - pin < 4))
1133 {
1134 elf_uncompress_failed ();
1135 return 0;
1136 }
1137
1138#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1139 && defined(__ORDER_BIG_ENDIAN__) \
1140 && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1141 || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1142 /* We've ensured that PIN is aligned. */
1143 next = *(const uint32_t *)pin;
1144
1145#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1146 next = __builtin_bswap32 (next);
1147#endif
1148#else
1149 next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1150#endif
1151
1152 val |= (uint64_t)next << bits;
1153 bits += 32;
1154 pin += 4;
1155
1156 /* We will need the next four bytes soon. */
1157 __builtin_prefetch (pin, 0, 0);
1158
1159 *ppin = pin;
1160 *pval = val;
1161 *pbits = bits;
1162 return 1;
1163}
1164
1165/* This is like elf_fetch_bits, but it fetchs the bits backward, and ensures at
1166 least 16 bits. This is for zstd. */
1167
1168static int
1169elf_fetch_bits_backward (const unsigned char **ppin,
1170 const unsigned char *pinend,
1171 uint64_t *pval, unsigned int *pbits)
1172{
1173 unsigned int bits;
1174 const unsigned char *pin;
1175 uint64_t val;
1176 uint32_t next;
1177
1178 bits = *pbits;
1179 if (bits >= 16)
1180 return 1;
1181 pin = *ppin;
1182 val = *pval;
1183
1184 if (unlikely (pin <= pinend))
1185 {
1186 if (bits == 0)
1187 {
1188 elf_uncompress_failed ();
1189 return 0;
1190 }
1191 return 1;
1192 }
1193
1194 pin -= 4;
1195
1196#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) \
1197 && defined(__ORDER_BIG_ENDIAN__) \
1198 && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ \
1199 || __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1200 /* We've ensured that PIN is aligned. */
1201 next = *(const uint32_t *)pin;
1202
1203#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
1204 next = __builtin_bswap32 (next);
1205#endif
1206#else
1207 next = pin[0] | (pin[1] << 8) | (pin[2] << 16) | (pin[3] << 24);
1208#endif
1209
1210 val <<= 32;
1211 val |= next;
1212 bits += 32;
1213
1214 if (unlikely (pin < pinend))
1215 {
1216 val >>= (pinend - pin) * 8;
1217 bits -= (pinend - pin) * 8;
1218 }
1219
1220 *ppin = pin;
1221 *pval = val;
1222 *pbits = bits;
1223 return 1;
1224}
1225
1226/* Initialize backward fetching when the bitstream starts with a 1 bit in the
1227 last byte in memory (which is the first one that we read). This is used by
1228 zstd decompression. Returns 1 on success, 0 on error. */
1229
1230static int
1231elf_fetch_backward_init (const unsigned char **ppin,
1232 const unsigned char *pinend,
1233 uint64_t *pval, unsigned int *pbits)
1234{
1235 const unsigned char *pin;
1236 unsigned int stream_start;
1237 uint64_t val;
1238 unsigned int bits;
1239
1240 pin = *ppin;
1241 stream_start = (unsigned int)*pin;
1242 if (unlikely (stream_start == 0))
1243 {
1244 elf_uncompress_failed ();
1245 return 0;
1246 }
1247 val = 0;
1248 bits = 0;
1249
1250 /* Align to a 32-bit boundary. */
1251 while ((((uintptr_t)pin) & 3) != 0)
1252 {
1253 val <<= 8;
1254 val |= (uint64_t)*pin;
1255 bits += 8;
1256 --pin;
1257 }
1258
1259 val <<= 8;
1260 val |= (uint64_t)*pin;
1261 bits += 8;
1262
1263 *ppin = pin;
1264 *pval = val;
1265 *pbits = bits;
1266 if (!elf_fetch_bits_backward (ppin, pinend, pval, pbits))
1267 return 0;
1268
1269 *pbits -= __builtin_clz (stream_start) - (sizeof (unsigned int) - 1) * 8 + 1;
1270
1271 if (!elf_fetch_bits_backward (ppin, pinend, pval, pbits))
1272 return 0;
1273
1274 return 1;
1275}
1276
1277/* Huffman code tables, like the rest of the zlib format, are defined
1278 by RFC 1951. We store a Huffman code table as a series of tables
1279 stored sequentially in memory. Each entry in a table is 16 bits.
1280 The first, main, table has 256 entries. It is followed by a set of
1281 secondary tables of length 2 to 128 entries. The maximum length of
1282 a code sequence in the deflate format is 15 bits, so that is all we
1283 need. Each secondary table has an index, which is the offset of
1284 the table in the overall memory storage.
1285
1286 The deflate format says that all codes of a given bit length are
1287 lexicographically consecutive. Perhaps we could have 130 values
1288 that require a 15-bit code, perhaps requiring three secondary
1289 tables of size 128. I don't know if this is actually possible, but
1290 it suggests that the maximum size required for secondary tables is
1291 3 * 128 + 3 * 64 ... == 768. The zlib enough program reports 660
1292 as the maximum. We permit 768, since in addition to the 256 for
1293 the primary table, with two bytes per entry, and with the two
1294 tables we need, that gives us a page.
1295
1296 A single table entry needs to store a value or (for the main table
1297 only) the index and size of a secondary table. Values range from 0
1298 to 285, inclusive. Secondary table indexes, per above, range from
1299 0 to 510. For a value we need to store the number of bits we need
1300 to determine that value (one value may appear multiple times in the
1301 table), which is 1 to 8. For a secondary table we need to store
1302 the number of bits used to index into the table, which is 1 to 7.
1303 And of course we need 1 bit to decide whether we have a value or a
1304 secondary table index. So each entry needs 9 bits for value/table
1305 index, 3 bits for size, 1 bit what it is. For simplicity we use 16
1306 bits per entry. */
1307
1308/* Number of entries we allocate to for one code table. We get a page
1309 for the two code tables we need. */
1310
1311#define ZLIB_HUFFMAN_TABLE_SIZE (1024)
1312
1313/* Bit masks and shifts for the values in the table. */
1314
1315#define ZLIB_HUFFMAN_VALUE_MASK 0x01ff
1316#define ZLIB_HUFFMAN_BITS_SHIFT 9
1317#define ZLIB_HUFFMAN_BITS_MASK 0x7
1318#define ZLIB_HUFFMAN_SECONDARY_SHIFT 12
1319
1320/* For working memory while inflating we need two code tables, we need
1321 an array of code lengths (max value 15, so we use unsigned char),
1322 and an array of unsigned shorts used while building a table. The
1323 latter two arrays must be large enough to hold the maximum number
1324 of code lengths, which RFC 1951 defines as 286 + 30. */
1325
1326#define ZLIB_TABLE_SIZE \
1327 (2 * ZLIB_HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1328 + (286 + 30) * sizeof (uint16_t) \
1329 + (286 + 30) * sizeof (unsigned char))
1330
1331#define ZLIB_TABLE_CODELEN_OFFSET \
1332 (2 * ZLIB_HUFFMAN_TABLE_SIZE * sizeof (uint16_t) \
1333 + (286 + 30) * sizeof (uint16_t))
1334
1335#define ZLIB_TABLE_WORK_OFFSET \
1336 (2 * ZLIB_HUFFMAN_TABLE_SIZE * sizeof (uint16_t))
1337
1338#ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1339
1340/* Used by the main function that generates the fixed table to learn
1341 the table size. */
1342static size_t final_next_secondary;
1343
1344#endif
1345
1346/* Build a Huffman code table from an array of lengths in CODES of
1347 length CODES_LEN. The table is stored into *TABLE. ZDEBUG_TABLE
1348 is the same as for elf_zlib_inflate, used to find some work space.
1349 Returns 1 on success, 0 on error. */
1350
1351static int
1352elf_zlib_inflate_table (unsigned char *codes, size_t codes_len,
1353 uint16_t *zdebug_table, uint16_t *table)
1354{
1355 uint16_t count[16];
1356 uint16_t start[16];
1357 uint16_t prev[16];
1358 uint16_t firstcode[7];
1359 uint16_t *next;
1360 size_t i;
1361 size_t j;
1362 unsigned int code;
1363 size_t next_secondary;
1364
1365 /* Count the number of code of each length. Set NEXT[val] to be the
1366 next value after VAL with the same bit length. */
1367
1368 next = (uint16_t *) (((unsigned char *) zdebug_table)
1369 + ZLIB_TABLE_WORK_OFFSET);
1370
1371 memset (s: &count[0], c: 0, n: 16 * sizeof (uint16_t));
1372 for (i = 0; i < codes_len; ++i)
1373 {
1374 if (unlikely (codes[i] >= 16))
1375 {
1376 elf_uncompress_failed ();
1377 return 0;
1378 }
1379
1380 if (count[codes[i]] == 0)
1381 {
1382 start[codes[i]] = i;
1383 prev[codes[i]] = i;
1384 }
1385 else
1386 {
1387 next[prev[codes[i]]] = i;
1388 prev[codes[i]] = i;
1389 }
1390
1391 ++count[codes[i]];
1392 }
1393
1394 /* For each length, fill in the table for the codes of that
1395 length. */
1396
1397 memset (s: table, c: 0, ZLIB_HUFFMAN_TABLE_SIZE * sizeof (uint16_t));
1398
1399 /* Handle the values that do not require a secondary table. */
1400
1401 code = 0;
1402 for (j = 1; j <= 8; ++j)
1403 {
1404 unsigned int jcnt;
1405 unsigned int val;
1406
1407 jcnt = count[j];
1408 if (jcnt == 0)
1409 continue;
1410
1411 if (unlikely (jcnt > (1U << j)))
1412 {
1413 elf_uncompress_failed ();
1414 return 0;
1415 }
1416
1417 /* There are JCNT values that have this length, the values
1418 starting from START[j] continuing through NEXT[VAL]. Those
1419 values are assigned consecutive values starting at CODE. */
1420
1421 val = start[j];
1422 for (i = 0; i < jcnt; ++i)
1423 {
1424 uint16_t tval;
1425 size_t ind;
1426 unsigned int incr;
1427
1428 /* In the compressed bit stream, the value VAL is encoded as
1429 J bits with the value C. */
1430
1431 if (unlikely ((val & ~ZLIB_HUFFMAN_VALUE_MASK) != 0))
1432 {
1433 elf_uncompress_failed ();
1434 return 0;
1435 }
1436
1437 tval = val | ((j - 1) << ZLIB_HUFFMAN_BITS_SHIFT);
1438
1439 /* The table lookup uses 8 bits. If J is less than 8, we
1440 don't know what the other bits will be. We need to fill
1441 in all possibilities in the table. Since the Huffman
1442 code is unambiguous, those entries can't be used for any
1443 other code. */
1444
1445 for (ind = code; ind < 0x100; ind += 1 << j)
1446 {
1447 if (unlikely (table[ind] != 0))
1448 {
1449 elf_uncompress_failed ();
1450 return 0;
1451 }
1452 table[ind] = tval;
1453 }
1454
1455 /* Advance to the next value with this length. */
1456 if (i + 1 < jcnt)
1457 val = next[val];
1458
1459 /* The Huffman codes are stored in the bitstream with the
1460 most significant bit first, as is required to make them
1461 unambiguous. The effect is that when we read them from
1462 the bitstream we see the bit sequence in reverse order:
1463 the most significant bit of the Huffman code is the least
1464 significant bit of the value we read from the bitstream.
1465 That means that to make our table lookups work, we need
1466 to reverse the bits of CODE. Since reversing bits is
1467 tedious and in general requires using a table, we instead
1468 increment CODE in reverse order. That is, if the number
1469 of bits we are currently using, here named J, is 3, we
1470 count as 000, 100, 010, 110, 001, 101, 011, 111, which is
1471 to say the numbers from 0 to 7 but with the bits
1472 reversed. Going to more bits, aka incrementing J,
1473 effectively just adds more zero bits as the beginning,
1474 and as such does not change the numeric value of CODE.
1475
1476 To increment CODE of length J in reverse order, find the
1477 most significant zero bit and set it to one while
1478 clearing all higher bits. In other words, add 1 modulo
1479 2^J, only reversed. */
1480
1481 incr = 1U << (j - 1);
1482 while ((code & incr) != 0)
1483 incr >>= 1;
1484 if (incr == 0)
1485 code = 0;
1486 else
1487 {
1488 code &= incr - 1;
1489 code += incr;
1490 }
1491 }
1492 }
1493
1494 /* Handle the values that require a secondary table. */
1495
1496 /* Set FIRSTCODE, the number at which the codes start, for each
1497 length. */
1498
1499 for (j = 9; j < 16; j++)
1500 {
1501 unsigned int jcnt;
1502 unsigned int k;
1503
1504 jcnt = count[j];
1505 if (jcnt == 0)
1506 continue;
1507
1508 /* There are JCNT values that have this length, the values
1509 starting from START[j]. Those values are assigned
1510 consecutive values starting at CODE. */
1511
1512 firstcode[j - 9] = code;
1513
1514 /* Reverse add JCNT to CODE modulo 2^J. */
1515 for (k = 0; k < j; ++k)
1516 {
1517 if ((jcnt & (1U << k)) != 0)
1518 {
1519 unsigned int m;
1520 unsigned int bit;
1521
1522 bit = 1U << (j - k - 1);
1523 for (m = 0; m < j - k; ++m, bit >>= 1)
1524 {
1525 if ((code & bit) == 0)
1526 {
1527 code += bit;
1528 break;
1529 }
1530 code &= ~bit;
1531 }
1532 jcnt &= ~(1U << k);
1533 }
1534 }
1535 if (unlikely (jcnt != 0))
1536 {
1537 elf_uncompress_failed ();
1538 return 0;
1539 }
1540 }
1541
1542 /* For J from 9 to 15, inclusive, we store COUNT[J] consecutive
1543 values starting at START[J] with consecutive codes starting at
1544 FIRSTCODE[J - 9]. In the primary table we need to point to the
1545 secondary table, and the secondary table will be indexed by J - 9
1546 bits. We count down from 15 so that we install the larger
1547 secondary tables first, as the smaller ones may be embedded in
1548 the larger ones. */
1549
1550 next_secondary = 0; /* Index of next secondary table (after primary). */
1551 for (j = 15; j >= 9; j--)
1552 {
1553 unsigned int jcnt;
1554 unsigned int val;
1555 size_t primary; /* Current primary index. */
1556 size_t secondary; /* Offset to current secondary table. */
1557 size_t secondary_bits; /* Bit size of current secondary table. */
1558
1559 jcnt = count[j];
1560 if (jcnt == 0)
1561 continue;
1562
1563 val = start[j];
1564 code = firstcode[j - 9];
1565 primary = 0x100;
1566 secondary = 0;
1567 secondary_bits = 0;
1568 for (i = 0; i < jcnt; ++i)
1569 {
1570 uint16_t tval;
1571 size_t ind;
1572 unsigned int incr;
1573
1574 if ((code & 0xff) != primary)
1575 {
1576 uint16_t tprimary;
1577
1578 /* Fill in a new primary table entry. */
1579
1580 primary = code & 0xff;
1581
1582 tprimary = table[primary];
1583 if (tprimary == 0)
1584 {
1585 /* Start a new secondary table. */
1586
1587 if (unlikely ((next_secondary & ZLIB_HUFFMAN_VALUE_MASK)
1588 != next_secondary))
1589 {
1590 elf_uncompress_failed ();
1591 return 0;
1592 }
1593
1594 secondary = next_secondary;
1595 secondary_bits = j - 8;
1596 next_secondary += 1 << secondary_bits;
1597 table[primary] = (secondary
1598 + ((j - 8) << ZLIB_HUFFMAN_BITS_SHIFT)
1599 + (1U << ZLIB_HUFFMAN_SECONDARY_SHIFT));
1600 }
1601 else
1602 {
1603 /* There is an existing entry. It had better be a
1604 secondary table with enough bits. */
1605 if (unlikely ((tprimary
1606 & (1U << ZLIB_HUFFMAN_SECONDARY_SHIFT))
1607 == 0))
1608 {
1609 elf_uncompress_failed ();
1610 return 0;
1611 }
1612 secondary = tprimary & ZLIB_HUFFMAN_VALUE_MASK;
1613 secondary_bits = ((tprimary >> ZLIB_HUFFMAN_BITS_SHIFT)
1614 & ZLIB_HUFFMAN_BITS_MASK);
1615 if (unlikely (secondary_bits < j - 8))
1616 {
1617 elf_uncompress_failed ();
1618 return 0;
1619 }
1620 }
1621 }
1622
1623 /* Fill in secondary table entries. */
1624
1625 tval = val | ((j - 8) << ZLIB_HUFFMAN_BITS_SHIFT);
1626
1627 for (ind = code >> 8;
1628 ind < (1U << secondary_bits);
1629 ind += 1U << (j - 8))
1630 {
1631 if (unlikely (table[secondary + 0x100 + ind] != 0))
1632 {
1633 elf_uncompress_failed ();
1634 return 0;
1635 }
1636 table[secondary + 0x100 + ind] = tval;
1637 }
1638
1639 if (i + 1 < jcnt)
1640 val = next[val];
1641
1642 incr = 1U << (j - 1);
1643 while ((code & incr) != 0)
1644 incr >>= 1;
1645 if (incr == 0)
1646 code = 0;
1647 else
1648 {
1649 code &= incr - 1;
1650 code += incr;
1651 }
1652 }
1653 }
1654
1655#ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1656 final_next_secondary = next_secondary;
1657#endif
1658
1659 return 1;
1660}
1661
1662#ifdef BACKTRACE_GENERATE_FIXED_HUFFMAN_TABLE
1663
1664/* Used to generate the fixed Huffman table for block type 1. */
1665
1666#include <stdio.h>
1667
1668static uint16_t table[ZLIB_TABLE_SIZE];
1669static unsigned char codes[288];
1670
1671int
1672main ()
1673{
1674 size_t i;
1675
1676 for (i = 0; i <= 143; ++i)
1677 codes[i] = 8;
1678 for (i = 144; i <= 255; ++i)
1679 codes[i] = 9;
1680 for (i = 256; i <= 279; ++i)
1681 codes[i] = 7;
1682 for (i = 280; i <= 287; ++i)
1683 codes[i] = 8;
1684 if (!elf_zlib_inflate_table (&codes[0], 288, &table[0], &table[0]))
1685 {
1686 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1687 exit (EXIT_FAILURE);
1688 }
1689
1690 printf ("static const uint16_t elf_zlib_default_table[%#zx] =\n",
1691 final_next_secondary + 0x100);
1692 printf ("{\n");
1693 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1694 {
1695 size_t j;
1696
1697 printf (" ");
1698 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1699 printf (" %#x,", table[j]);
1700 printf ("\n");
1701 }
1702 printf ("};\n");
1703 printf ("\n");
1704
1705 for (i = 0; i < 32; ++i)
1706 codes[i] = 5;
1707 if (!elf_zlib_inflate_table (&codes[0], 32, &table[0], &table[0]))
1708 {
1709 fprintf (stderr, "elf_zlib_inflate_table failed\n");
1710 exit (EXIT_FAILURE);
1711 }
1712
1713 printf ("static const uint16_t elf_zlib_default_dist_table[%#zx] =\n",
1714 final_next_secondary + 0x100);
1715 printf ("{\n");
1716 for (i = 0; i < final_next_secondary + 0x100; i += 8)
1717 {
1718 size_t j;
1719
1720 printf (" ");
1721 for (j = i; j < final_next_secondary + 0x100 && j < i + 8; ++j)
1722 printf (" %#x,", table[j]);
1723 printf ("\n");
1724 }
1725 printf ("};\n");
1726
1727 return 0;
1728}
1729
1730#endif
1731
1732/* The fixed tables generated by the #ifdef'ed out main function
1733 above. */
1734
1735static const uint16_t elf_zlib_default_table[0x170] =
1736{
1737 0xd00, 0xe50, 0xe10, 0xf18, 0xd10, 0xe70, 0xe30, 0x1230,
1738 0xd08, 0xe60, 0xe20, 0x1210, 0xe00, 0xe80, 0xe40, 0x1250,
1739 0xd04, 0xe58, 0xe18, 0x1200, 0xd14, 0xe78, 0xe38, 0x1240,
1740 0xd0c, 0xe68, 0xe28, 0x1220, 0xe08, 0xe88, 0xe48, 0x1260,
1741 0xd02, 0xe54, 0xe14, 0xf1c, 0xd12, 0xe74, 0xe34, 0x1238,
1742 0xd0a, 0xe64, 0xe24, 0x1218, 0xe04, 0xe84, 0xe44, 0x1258,
1743 0xd06, 0xe5c, 0xe1c, 0x1208, 0xd16, 0xe7c, 0xe3c, 0x1248,
1744 0xd0e, 0xe6c, 0xe2c, 0x1228, 0xe0c, 0xe8c, 0xe4c, 0x1268,
1745 0xd01, 0xe52, 0xe12, 0xf1a, 0xd11, 0xe72, 0xe32, 0x1234,
1746 0xd09, 0xe62, 0xe22, 0x1214, 0xe02, 0xe82, 0xe42, 0x1254,
1747 0xd05, 0xe5a, 0xe1a, 0x1204, 0xd15, 0xe7a, 0xe3a, 0x1244,
1748 0xd0d, 0xe6a, 0xe2a, 0x1224, 0xe0a, 0xe8a, 0xe4a, 0x1264,
1749 0xd03, 0xe56, 0xe16, 0xf1e, 0xd13, 0xe76, 0xe36, 0x123c,
1750 0xd0b, 0xe66, 0xe26, 0x121c, 0xe06, 0xe86, 0xe46, 0x125c,
1751 0xd07, 0xe5e, 0xe1e, 0x120c, 0xd17, 0xe7e, 0xe3e, 0x124c,
1752 0xd0f, 0xe6e, 0xe2e, 0x122c, 0xe0e, 0xe8e, 0xe4e, 0x126c,
1753 0xd00, 0xe51, 0xe11, 0xf19, 0xd10, 0xe71, 0xe31, 0x1232,
1754 0xd08, 0xe61, 0xe21, 0x1212, 0xe01, 0xe81, 0xe41, 0x1252,
1755 0xd04, 0xe59, 0xe19, 0x1202, 0xd14, 0xe79, 0xe39, 0x1242,
1756 0xd0c, 0xe69, 0xe29, 0x1222, 0xe09, 0xe89, 0xe49, 0x1262,
1757 0xd02, 0xe55, 0xe15, 0xf1d, 0xd12, 0xe75, 0xe35, 0x123a,
1758 0xd0a, 0xe65, 0xe25, 0x121a, 0xe05, 0xe85, 0xe45, 0x125a,
1759 0xd06, 0xe5d, 0xe1d, 0x120a, 0xd16, 0xe7d, 0xe3d, 0x124a,
1760 0xd0e, 0xe6d, 0xe2d, 0x122a, 0xe0d, 0xe8d, 0xe4d, 0x126a,
1761 0xd01, 0xe53, 0xe13, 0xf1b, 0xd11, 0xe73, 0xe33, 0x1236,
1762 0xd09, 0xe63, 0xe23, 0x1216, 0xe03, 0xe83, 0xe43, 0x1256,
1763 0xd05, 0xe5b, 0xe1b, 0x1206, 0xd15, 0xe7b, 0xe3b, 0x1246,
1764 0xd0d, 0xe6b, 0xe2b, 0x1226, 0xe0b, 0xe8b, 0xe4b, 0x1266,
1765 0xd03, 0xe57, 0xe17, 0xf1f, 0xd13, 0xe77, 0xe37, 0x123e,
1766 0xd0b, 0xe67, 0xe27, 0x121e, 0xe07, 0xe87, 0xe47, 0x125e,
1767 0xd07, 0xe5f, 0xe1f, 0x120e, 0xd17, 0xe7f, 0xe3f, 0x124e,
1768 0xd0f, 0xe6f, 0xe2f, 0x122e, 0xe0f, 0xe8f, 0xe4f, 0x126e,
1769 0x290, 0x291, 0x292, 0x293, 0x294, 0x295, 0x296, 0x297,
1770 0x298, 0x299, 0x29a, 0x29b, 0x29c, 0x29d, 0x29e, 0x29f,
1771 0x2a0, 0x2a1, 0x2a2, 0x2a3, 0x2a4, 0x2a5, 0x2a6, 0x2a7,
1772 0x2a8, 0x2a9, 0x2aa, 0x2ab, 0x2ac, 0x2ad, 0x2ae, 0x2af,
1773 0x2b0, 0x2b1, 0x2b2, 0x2b3, 0x2b4, 0x2b5, 0x2b6, 0x2b7,
1774 0x2b8, 0x2b9, 0x2ba, 0x2bb, 0x2bc, 0x2bd, 0x2be, 0x2bf,
1775 0x2c0, 0x2c1, 0x2c2, 0x2c3, 0x2c4, 0x2c5, 0x2c6, 0x2c7,
1776 0x2c8, 0x2c9, 0x2ca, 0x2cb, 0x2cc, 0x2cd, 0x2ce, 0x2cf,
1777 0x2d0, 0x2d1, 0x2d2, 0x2d3, 0x2d4, 0x2d5, 0x2d6, 0x2d7,
1778 0x2d8, 0x2d9, 0x2da, 0x2db, 0x2dc, 0x2dd, 0x2de, 0x2df,
1779 0x2e0, 0x2e1, 0x2e2, 0x2e3, 0x2e4, 0x2e5, 0x2e6, 0x2e7,
1780 0x2e8, 0x2e9, 0x2ea, 0x2eb, 0x2ec, 0x2ed, 0x2ee, 0x2ef,
1781 0x2f0, 0x2f1, 0x2f2, 0x2f3, 0x2f4, 0x2f5, 0x2f6, 0x2f7,
1782 0x2f8, 0x2f9, 0x2fa, 0x2fb, 0x2fc, 0x2fd, 0x2fe, 0x2ff,
1783};
1784
1785static const uint16_t elf_zlib_default_dist_table[0x100] =
1786{
1787 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1788 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1789 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1790 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1791 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1792 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1793 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1794 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1795 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1796 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1797 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1798 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1799 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1800 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1801 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1802 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1803 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1804 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1805 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1806 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1807 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1808 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1809 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1810 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1811 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1812 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1813 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1814 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1815 0x800, 0x810, 0x808, 0x818, 0x804, 0x814, 0x80c, 0x81c,
1816 0x802, 0x812, 0x80a, 0x81a, 0x806, 0x816, 0x80e, 0x81e,
1817 0x801, 0x811, 0x809, 0x819, 0x805, 0x815, 0x80d, 0x81d,
1818 0x803, 0x813, 0x80b, 0x81b, 0x807, 0x817, 0x80f, 0x81f,
1819};
1820
1821/* Inflate a zlib stream from PIN/SIN to POUT/SOUT. Return 1 on
1822 success, 0 on some error parsing the stream. */
1823
1824static int
1825elf_zlib_inflate (const unsigned char *pin, size_t sin, uint16_t *zdebug_table,
1826 unsigned char *pout, size_t sout)
1827{
1828 unsigned char *porigout;
1829 const unsigned char *pinend;
1830 unsigned char *poutend;
1831
1832 /* We can apparently see multiple zlib streams concatenated
1833 together, so keep going as long as there is something to read.
1834 The last 4 bytes are the checksum. */
1835 porigout = pout;
1836 pinend = pin + sin;
1837 poutend = pout + sout;
1838 while ((pinend - pin) > 4)
1839 {
1840 uint64_t val;
1841 unsigned int bits;
1842 int last;
1843
1844 /* Read the two byte zlib header. */
1845
1846 if (unlikely ((pin[0] & 0xf) != 8)) /* 8 is zlib encoding. */
1847 {
1848 /* Unknown compression method. */
1849 elf_uncompress_failed ();
1850 return 0;
1851 }
1852 if (unlikely ((pin[0] >> 4) > 7))
1853 {
1854 /* Window size too large. Other than this check, we don't
1855 care about the window size. */
1856 elf_uncompress_failed ();
1857 return 0;
1858 }
1859 if (unlikely ((pin[1] & 0x20) != 0))
1860 {
1861 /* Stream expects a predefined dictionary, but we have no
1862 dictionary. */
1863 elf_uncompress_failed ();
1864 return 0;
1865 }
1866 val = (pin[0] << 8) | pin[1];
1867 if (unlikely (val % 31 != 0))
1868 {
1869 /* Header check failure. */
1870 elf_uncompress_failed ();
1871 return 0;
1872 }
1873 pin += 2;
1874
1875 /* Align PIN to a 32-bit boundary. */
1876
1877 val = 0;
1878 bits = 0;
1879 while ((((uintptr_t) pin) & 3) != 0)
1880 {
1881 val |= (uint64_t)*pin << bits;
1882 bits += 8;
1883 ++pin;
1884 }
1885
1886 /* Read blocks until one is marked last. */
1887
1888 last = 0;
1889
1890 while (!last)
1891 {
1892 unsigned int type;
1893 const uint16_t *tlit;
1894 const uint16_t *tdist;
1895
1896 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
1897 return 0;
1898
1899 last = val & 1;
1900 type = (val >> 1) & 3;
1901 val >>= 3;
1902 bits -= 3;
1903
1904 if (unlikely (type == 3))
1905 {
1906 /* Invalid block type. */
1907 elf_uncompress_failed ();
1908 return 0;
1909 }
1910
1911 if (type == 0)
1912 {
1913 uint16_t len;
1914 uint16_t lenc;
1915
1916 /* An uncompressed block. */
1917
1918 /* If we've read ahead more than a byte, back up. */
1919 while (bits >= 8)
1920 {
1921 --pin;
1922 bits -= 8;
1923 }
1924
1925 val = 0;
1926 bits = 0;
1927 if (unlikely ((pinend - pin) < 4))
1928 {
1929 /* Missing length. */
1930 elf_uncompress_failed ();
1931 return 0;
1932 }
1933 len = pin[0] | (pin[1] << 8);
1934 lenc = pin[2] | (pin[3] << 8);
1935 pin += 4;
1936 lenc = ~lenc;
1937 if (unlikely (len != lenc))
1938 {
1939 /* Corrupt data. */
1940 elf_uncompress_failed ();
1941 return 0;
1942 }
1943 if (unlikely (len > (unsigned int) (pinend - pin)
1944 || len > (unsigned int) (poutend - pout)))
1945 {
1946 /* Not enough space in buffers. */
1947 elf_uncompress_failed ();
1948 return 0;
1949 }
1950 memcpy (dest: pout, src: pin, n: len);
1951 pout += len;
1952 pin += len;
1953
1954 /* Align PIN. */
1955 while ((((uintptr_t) pin) & 3) != 0)
1956 {
1957 val |= (uint64_t)*pin << bits;
1958 bits += 8;
1959 ++pin;
1960 }
1961
1962 /* Go around to read the next block. */
1963 continue;
1964 }
1965
1966 if (type == 1)
1967 {
1968 tlit = elf_zlib_default_table;
1969 tdist = elf_zlib_default_dist_table;
1970 }
1971 else
1972 {
1973 unsigned int nlit;
1974 unsigned int ndist;
1975 unsigned int nclen;
1976 unsigned char codebits[19];
1977 unsigned char *plenbase;
1978 unsigned char *plen;
1979 unsigned char *plenend;
1980
1981 /* Read a Huffman encoding table. The various magic
1982 numbers here are from RFC 1951. */
1983
1984 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
1985 return 0;
1986
1987 nlit = (val & 0x1f) + 257;
1988 val >>= 5;
1989 ndist = (val & 0x1f) + 1;
1990 val >>= 5;
1991 nclen = (val & 0xf) + 4;
1992 val >>= 4;
1993 bits -= 14;
1994 if (unlikely (nlit > 286 || ndist > 30))
1995 {
1996 /* Values out of range. */
1997 elf_uncompress_failed ();
1998 return 0;
1999 }
2000
2001 /* Read and build the table used to compress the
2002 literal, length, and distance codes. */
2003
2004 memset(s: &codebits[0], c: 0, n: 19);
2005
2006 /* There are always at least 4 elements in the
2007 table. */
2008
2009 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2010 return 0;
2011
2012 codebits[16] = val & 7;
2013 codebits[17] = (val >> 3) & 7;
2014 codebits[18] = (val >> 6) & 7;
2015 codebits[0] = (val >> 9) & 7;
2016 val >>= 12;
2017 bits -= 12;
2018
2019 if (nclen == 4)
2020 goto codebitsdone;
2021
2022 codebits[8] = val & 7;
2023 val >>= 3;
2024 bits -= 3;
2025
2026 if (nclen == 5)
2027 goto codebitsdone;
2028
2029 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2030 return 0;
2031
2032 codebits[7] = val & 7;
2033 val >>= 3;
2034 bits -= 3;
2035
2036 if (nclen == 6)
2037 goto codebitsdone;
2038
2039 codebits[9] = val & 7;
2040 val >>= 3;
2041 bits -= 3;
2042
2043 if (nclen == 7)
2044 goto codebitsdone;
2045
2046 codebits[6] = val & 7;
2047 val >>= 3;
2048 bits -= 3;
2049
2050 if (nclen == 8)
2051 goto codebitsdone;
2052
2053 codebits[10] = val & 7;
2054 val >>= 3;
2055 bits -= 3;
2056
2057 if (nclen == 9)
2058 goto codebitsdone;
2059
2060 codebits[5] = val & 7;
2061 val >>= 3;
2062 bits -= 3;
2063
2064 if (nclen == 10)
2065 goto codebitsdone;
2066
2067 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2068 return 0;
2069
2070 codebits[11] = val & 7;
2071 val >>= 3;
2072 bits -= 3;
2073
2074 if (nclen == 11)
2075 goto codebitsdone;
2076
2077 codebits[4] = val & 7;
2078 val >>= 3;
2079 bits -= 3;
2080
2081 if (nclen == 12)
2082 goto codebitsdone;
2083
2084 codebits[12] = val & 7;
2085 val >>= 3;
2086 bits -= 3;
2087
2088 if (nclen == 13)
2089 goto codebitsdone;
2090
2091 codebits[3] = val & 7;
2092 val >>= 3;
2093 bits -= 3;
2094
2095 if (nclen == 14)
2096 goto codebitsdone;
2097
2098 codebits[13] = val & 7;
2099 val >>= 3;
2100 bits -= 3;
2101
2102 if (nclen == 15)
2103 goto codebitsdone;
2104
2105 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2106 return 0;
2107
2108 codebits[2] = val & 7;
2109 val >>= 3;
2110 bits -= 3;
2111
2112 if (nclen == 16)
2113 goto codebitsdone;
2114
2115 codebits[14] = val & 7;
2116 val >>= 3;
2117 bits -= 3;
2118
2119 if (nclen == 17)
2120 goto codebitsdone;
2121
2122 codebits[1] = val & 7;
2123 val >>= 3;
2124 bits -= 3;
2125
2126 if (nclen == 18)
2127 goto codebitsdone;
2128
2129 codebits[15] = val & 7;
2130 val >>= 3;
2131 bits -= 3;
2132
2133 codebitsdone:
2134
2135 if (!elf_zlib_inflate_table (codes: codebits, codes_len: 19, zdebug_table,
2136 table: zdebug_table))
2137 return 0;
2138
2139 /* Read the compressed bit lengths of the literal,
2140 length, and distance codes. We have allocated space
2141 at the end of zdebug_table to hold them. */
2142
2143 plenbase = (((unsigned char *) zdebug_table)
2144 + ZLIB_TABLE_CODELEN_OFFSET);
2145 plen = plenbase;
2146 plenend = plen + nlit + ndist;
2147 while (plen < plenend)
2148 {
2149 uint16_t t;
2150 unsigned int b;
2151 uint16_t v;
2152
2153 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2154 return 0;
2155
2156 t = zdebug_table[val & 0xff];
2157
2158 /* The compression here uses bit lengths up to 7, so
2159 a secondary table is never necessary. */
2160 if (unlikely ((t & (1U << ZLIB_HUFFMAN_SECONDARY_SHIFT))
2161 != 0))
2162 {
2163 elf_uncompress_failed ();
2164 return 0;
2165 }
2166
2167 b = (t >> ZLIB_HUFFMAN_BITS_SHIFT) & ZLIB_HUFFMAN_BITS_MASK;
2168 val >>= b + 1;
2169 bits -= b + 1;
2170
2171 v = t & ZLIB_HUFFMAN_VALUE_MASK;
2172 if (v < 16)
2173 *plen++ = v;
2174 else if (v == 16)
2175 {
2176 unsigned int c;
2177 unsigned int prev;
2178
2179 /* Copy previous entry 3 to 6 times. */
2180
2181 if (unlikely (plen == plenbase))
2182 {
2183 elf_uncompress_failed ();
2184 return 0;
2185 }
2186
2187 /* We used up to 7 bits since the last
2188 elf_fetch_bits, so we have at least 8 bits
2189 available here. */
2190
2191 c = 3 + (val & 0x3);
2192 val >>= 2;
2193 bits -= 2;
2194 if (unlikely ((unsigned int) (plenend - plen) < c))
2195 {
2196 elf_uncompress_failed ();
2197 return 0;
2198 }
2199
2200 prev = plen[-1];
2201 switch (c)
2202 {
2203 case 6:
2204 *plen++ = prev;
2205 ATTRIBUTE_FALLTHROUGH;
2206 case 5:
2207 *plen++ = prev;
2208 ATTRIBUTE_FALLTHROUGH;
2209 case 4:
2210 *plen++ = prev;
2211 }
2212 *plen++ = prev;
2213 *plen++ = prev;
2214 *plen++ = prev;
2215 }
2216 else if (v == 17)
2217 {
2218 unsigned int c;
2219
2220 /* Store zero 3 to 10 times. */
2221
2222 /* We used up to 7 bits since the last
2223 elf_fetch_bits, so we have at least 8 bits
2224 available here. */
2225
2226 c = 3 + (val & 0x7);
2227 val >>= 3;
2228 bits -= 3;
2229 if (unlikely ((unsigned int) (plenend - plen) < c))
2230 {
2231 elf_uncompress_failed ();
2232 return 0;
2233 }
2234
2235 switch (c)
2236 {
2237 case 10:
2238 *plen++ = 0;
2239 ATTRIBUTE_FALLTHROUGH;
2240 case 9:
2241 *plen++ = 0;
2242 ATTRIBUTE_FALLTHROUGH;
2243 case 8:
2244 *plen++ = 0;
2245 ATTRIBUTE_FALLTHROUGH;
2246 case 7:
2247 *plen++ = 0;
2248 ATTRIBUTE_FALLTHROUGH;
2249 case 6:
2250 *plen++ = 0;
2251 ATTRIBUTE_FALLTHROUGH;
2252 case 5:
2253 *plen++ = 0;
2254 ATTRIBUTE_FALLTHROUGH;
2255 case 4:
2256 *plen++ = 0;
2257 }
2258 *plen++ = 0;
2259 *plen++ = 0;
2260 *plen++ = 0;
2261 }
2262 else if (v == 18)
2263 {
2264 unsigned int c;
2265
2266 /* Store zero 11 to 138 times. */
2267
2268 /* We used up to 7 bits since the last
2269 elf_fetch_bits, so we have at least 8 bits
2270 available here. */
2271
2272 c = 11 + (val & 0x7f);
2273 val >>= 7;
2274 bits -= 7;
2275 if (unlikely ((unsigned int) (plenend - plen) < c))
2276 {
2277 elf_uncompress_failed ();
2278 return 0;
2279 }
2280
2281 memset (s: plen, c: 0, n: c);
2282 plen += c;
2283 }
2284 else
2285 {
2286 elf_uncompress_failed ();
2287 return 0;
2288 }
2289 }
2290
2291 /* Make sure that the stop code can appear. */
2292
2293 plen = plenbase;
2294 if (unlikely (plen[256] == 0))
2295 {
2296 elf_uncompress_failed ();
2297 return 0;
2298 }
2299
2300 /* Build the decompression tables. */
2301
2302 if (!elf_zlib_inflate_table (codes: plen, codes_len: nlit, zdebug_table,
2303 table: zdebug_table))
2304 return 0;
2305 if (!elf_zlib_inflate_table (codes: plen + nlit, codes_len: ndist, zdebug_table,
2306 table: (zdebug_table
2307 + ZLIB_HUFFMAN_TABLE_SIZE)))
2308 return 0;
2309 tlit = zdebug_table;
2310 tdist = zdebug_table + ZLIB_HUFFMAN_TABLE_SIZE;
2311 }
2312
2313 /* Inflate values until the end of the block. This is the
2314 main loop of the inflation code. */
2315
2316 while (1)
2317 {
2318 uint16_t t;
2319 unsigned int b;
2320 uint16_t v;
2321 unsigned int lit;
2322
2323 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2324 return 0;
2325
2326 t = tlit[val & 0xff];
2327 b = (t >> ZLIB_HUFFMAN_BITS_SHIFT) & ZLIB_HUFFMAN_BITS_MASK;
2328 v = t & ZLIB_HUFFMAN_VALUE_MASK;
2329
2330 if ((t & (1U << ZLIB_HUFFMAN_SECONDARY_SHIFT)) == 0)
2331 {
2332 lit = v;
2333 val >>= b + 1;
2334 bits -= b + 1;
2335 }
2336 else
2337 {
2338 t = tlit[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2339 b = (t >> ZLIB_HUFFMAN_BITS_SHIFT) & ZLIB_HUFFMAN_BITS_MASK;
2340 lit = t & ZLIB_HUFFMAN_VALUE_MASK;
2341 val >>= b + 8;
2342 bits -= b + 8;
2343 }
2344
2345 if (lit < 256)
2346 {
2347 if (unlikely (pout == poutend))
2348 {
2349 elf_uncompress_failed ();
2350 return 0;
2351 }
2352
2353 *pout++ = lit;
2354
2355 /* We will need to write the next byte soon. We ask
2356 for high temporal locality because we will write
2357 to the whole cache line soon. */
2358 __builtin_prefetch (pout, 1, 3);
2359 }
2360 else if (lit == 256)
2361 {
2362 /* The end of the block. */
2363 break;
2364 }
2365 else
2366 {
2367 unsigned int dist;
2368 unsigned int len;
2369
2370 /* Convert lit into a length. */
2371
2372 if (lit < 265)
2373 len = lit - 257 + 3;
2374 else if (lit == 285)
2375 len = 258;
2376 else if (unlikely (lit > 285))
2377 {
2378 elf_uncompress_failed ();
2379 return 0;
2380 }
2381 else
2382 {
2383 unsigned int extra;
2384
2385 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2386 return 0;
2387
2388 /* This is an expression for the table of length
2389 codes in RFC 1951 3.2.5. */
2390 lit -= 265;
2391 extra = (lit >> 2) + 1;
2392 len = (lit & 3) << extra;
2393 len += 11;
2394 len += ((1U << (extra - 1)) - 1) << 3;
2395 len += val & ((1U << extra) - 1);
2396 val >>= extra;
2397 bits -= extra;
2398 }
2399
2400 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2401 return 0;
2402
2403 t = tdist[val & 0xff];
2404 b = (t >> ZLIB_HUFFMAN_BITS_SHIFT) & ZLIB_HUFFMAN_BITS_MASK;
2405 v = t & ZLIB_HUFFMAN_VALUE_MASK;
2406
2407 if ((t & (1U << ZLIB_HUFFMAN_SECONDARY_SHIFT)) == 0)
2408 {
2409 dist = v;
2410 val >>= b + 1;
2411 bits -= b + 1;
2412 }
2413 else
2414 {
2415 t = tdist[v + 0x100 + ((val >> 8) & ((1U << b) - 1))];
2416 b = ((t >> ZLIB_HUFFMAN_BITS_SHIFT)
2417 & ZLIB_HUFFMAN_BITS_MASK);
2418 dist = t & ZLIB_HUFFMAN_VALUE_MASK;
2419 val >>= b + 8;
2420 bits -= b + 8;
2421 }
2422
2423 /* Convert dist to a distance. */
2424
2425 if (dist == 0)
2426 {
2427 /* A distance of 1. A common case, meaning
2428 repeat the last character LEN times. */
2429
2430 if (unlikely (pout == porigout))
2431 {
2432 elf_uncompress_failed ();
2433 return 0;
2434 }
2435
2436 if (unlikely ((unsigned int) (poutend - pout) < len))
2437 {
2438 elf_uncompress_failed ();
2439 return 0;
2440 }
2441
2442 memset (s: pout, c: pout[-1], n: len);
2443 pout += len;
2444 }
2445 else if (unlikely (dist > 29))
2446 {
2447 elf_uncompress_failed ();
2448 return 0;
2449 }
2450 else
2451 {
2452 if (dist < 4)
2453 dist = dist + 1;
2454 else
2455 {
2456 unsigned int extra;
2457
2458 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2459 return 0;
2460
2461 /* This is an expression for the table of
2462 distance codes in RFC 1951 3.2.5. */
2463 dist -= 4;
2464 extra = (dist >> 1) + 1;
2465 dist = (dist & 1) << extra;
2466 dist += 5;
2467 dist += ((1U << (extra - 1)) - 1) << 2;
2468 dist += val & ((1U << extra) - 1);
2469 val >>= extra;
2470 bits -= extra;
2471 }
2472
2473 /* Go back dist bytes, and copy len bytes from
2474 there. */
2475
2476 if (unlikely ((unsigned int) (pout - porigout) < dist))
2477 {
2478 elf_uncompress_failed ();
2479 return 0;
2480 }
2481
2482 if (unlikely ((unsigned int) (poutend - pout) < len))
2483 {
2484 elf_uncompress_failed ();
2485 return 0;
2486 }
2487
2488 if (dist >= len)
2489 {
2490 memcpy (dest: pout, src: pout - dist, n: len);
2491 pout += len;
2492 }
2493 else
2494 {
2495 while (len > 0)
2496 {
2497 unsigned int copy;
2498
2499 copy = len < dist ? len : dist;
2500 memcpy (dest: pout, src: pout - dist, n: copy);
2501 len -= copy;
2502 pout += copy;
2503 }
2504 }
2505 }
2506 }
2507 }
2508 }
2509 }
2510
2511 /* We should have filled the output buffer. */
2512 if (unlikely (pout != poutend))
2513 {
2514 elf_uncompress_failed ();
2515 return 0;
2516 }
2517
2518 return 1;
2519}
2520
2521/* Verify the zlib checksum. The checksum is in the 4 bytes at
2522 CHECKBYTES, and the uncompressed data is at UNCOMPRESSED /
2523 UNCOMPRESSED_SIZE. Returns 1 on success, 0 on failure. */
2524
2525static int
2526elf_zlib_verify_checksum (const unsigned char *checkbytes,
2527 const unsigned char *uncompressed,
2528 size_t uncompressed_size)
2529{
2530 unsigned int i;
2531 unsigned int cksum;
2532 const unsigned char *p;
2533 uint32_t s1;
2534 uint32_t s2;
2535 size_t hsz;
2536
2537 cksum = 0;
2538 for (i = 0; i < 4; i++)
2539 cksum = (cksum << 8) | checkbytes[i];
2540
2541 s1 = 1;
2542 s2 = 0;
2543
2544 /* Minimize modulo operations. */
2545
2546 p = uncompressed;
2547 hsz = uncompressed_size;
2548 while (hsz >= 5552)
2549 {
2550 for (i = 0; i < 5552; i += 16)
2551 {
2552 /* Manually unroll loop 16 times. */
2553 s1 = s1 + *p++;
2554 s2 = s2 + s1;
2555 s1 = s1 + *p++;
2556 s2 = s2 + s1;
2557 s1 = s1 + *p++;
2558 s2 = s2 + s1;
2559 s1 = s1 + *p++;
2560 s2 = s2 + s1;
2561 s1 = s1 + *p++;
2562 s2 = s2 + s1;
2563 s1 = s1 + *p++;
2564 s2 = s2 + s1;
2565 s1 = s1 + *p++;
2566 s2 = s2 + s1;
2567 s1 = s1 + *p++;
2568 s2 = s2 + s1;
2569 s1 = s1 + *p++;
2570 s2 = s2 + s1;
2571 s1 = s1 + *p++;
2572 s2 = s2 + s1;
2573 s1 = s1 + *p++;
2574 s2 = s2 + s1;
2575 s1 = s1 + *p++;
2576 s2 = s2 + s1;
2577 s1 = s1 + *p++;
2578 s2 = s2 + s1;
2579 s1 = s1 + *p++;
2580 s2 = s2 + s1;
2581 s1 = s1 + *p++;
2582 s2 = s2 + s1;
2583 s1 = s1 + *p++;
2584 s2 = s2 + s1;
2585 }
2586 hsz -= 5552;
2587 s1 %= 65521;
2588 s2 %= 65521;
2589 }
2590
2591 while (hsz >= 16)
2592 {
2593 /* Manually unroll loop 16 times. */
2594 s1 = s1 + *p++;
2595 s2 = s2 + s1;
2596 s1 = s1 + *p++;
2597 s2 = s2 + s1;
2598 s1 = s1 + *p++;
2599 s2 = s2 + s1;
2600 s1 = s1 + *p++;
2601 s2 = s2 + s1;
2602 s1 = s1 + *p++;
2603 s2 = s2 + s1;
2604 s1 = s1 + *p++;
2605 s2 = s2 + s1;
2606 s1 = s1 + *p++;
2607 s2 = s2 + s1;
2608 s1 = s1 + *p++;
2609 s2 = s2 + s1;
2610 s1 = s1 + *p++;
2611 s2 = s2 + s1;
2612 s1 = s1 + *p++;
2613 s2 = s2 + s1;
2614 s1 = s1 + *p++;
2615 s2 = s2 + s1;
2616 s1 = s1 + *p++;
2617 s2 = s2 + s1;
2618 s1 = s1 + *p++;
2619 s2 = s2 + s1;
2620 s1 = s1 + *p++;
2621 s2 = s2 + s1;
2622 s1 = s1 + *p++;
2623 s2 = s2 + s1;
2624 s1 = s1 + *p++;
2625 s2 = s2 + s1;
2626
2627 hsz -= 16;
2628 }
2629
2630 for (i = 0; i < hsz; ++i)
2631 {
2632 s1 = s1 + *p++;
2633 s2 = s2 + s1;
2634 }
2635
2636 s1 %= 65521;
2637 s2 %= 65521;
2638
2639 if (unlikely ((s2 << 16) + s1 != cksum))
2640 {
2641 elf_uncompress_failed ();
2642 return 0;
2643 }
2644
2645 return 1;
2646}
2647
2648/* Inflate a zlib stream from PIN/SIN to POUT/SOUT, and verify the
2649 checksum. Return 1 on success, 0 on error. */
2650
2651static int
2652elf_zlib_inflate_and_verify (const unsigned char *pin, size_t sin,
2653 uint16_t *zdebug_table, unsigned char *pout,
2654 size_t sout)
2655{
2656 if (!elf_zlib_inflate (pin, sin, zdebug_table, pout, sout))
2657 return 0;
2658 if (!elf_zlib_verify_checksum (checkbytes: pin + sin - 4, uncompressed: pout, uncompressed_size: sout))
2659 return 0;
2660 return 1;
2661}
2662
2663/* For working memory during zstd compression, we need
2664 - a literal length FSE table: 512 64-bit values == 4096 bytes
2665 - a match length FSE table: 512 64-bit values == 4096 bytes
2666 - a offset FSE table: 256 64-bit values == 2048 bytes
2667 - a Huffman tree: 2048 uint16_t values == 4096 bytes
2668 - scratch space, one of
2669 - to build an FSE table: 512 uint16_t values == 1024 bytes
2670 - to build a Huffman tree: 512 uint16_t + 256 uint32_t == 2048 bytes
2671*/
2672
2673#define ZSTD_TABLE_SIZE \
2674 (2 * 512 * sizeof (struct elf_zstd_fse_baseline_entry) \
2675 + 256 * sizeof (struct elf_zstd_fse_baseline_entry) \
2676 + 2048 * sizeof (uint16_t) \
2677 + 512 * sizeof (uint16_t) + 256 * sizeof (uint32_t))
2678
2679#define ZSTD_TABLE_LITERAL_FSE_OFFSET (0)
2680
2681#define ZSTD_TABLE_MATCH_FSE_OFFSET \
2682 (512 * sizeof (struct elf_zstd_fse_baseline_entry))
2683
2684#define ZSTD_TABLE_OFFSET_FSE_OFFSET \
2685 (ZSTD_TABLE_MATCH_FSE_OFFSET \
2686 + 512 * sizeof (struct elf_zstd_fse_baseline_entry))
2687
2688#define ZSTD_TABLE_HUFFMAN_OFFSET \
2689 (ZSTD_TABLE_OFFSET_FSE_OFFSET \
2690 + 256 * sizeof (struct elf_zstd_fse_baseline_entry))
2691
2692#define ZSTD_TABLE_WORK_OFFSET \
2693 (ZSTD_TABLE_HUFFMAN_OFFSET + 2048 * sizeof (uint16_t))
2694
2695/* An entry in a zstd FSE table. */
2696
2697struct elf_zstd_fse_entry
2698{
2699 /* The value that this FSE entry represents. */
2700 unsigned char symbol;
2701 /* The number of bits to read to determine the next state. */
2702 unsigned char bits;
2703 /* Add the bits to this base to get the next state. */
2704 uint16_t base;
2705};
2706
2707static int
2708elf_zstd_build_fse (const int16_t *, int, uint16_t *, int,
2709 struct elf_zstd_fse_entry *);
2710
2711/* Read a zstd FSE table and build the decoding table in *TABLE, updating *PPIN
2712 as it reads. ZDEBUG_TABLE is scratch space; it must be enough for 512
2713 uint16_t values (1024 bytes). MAXIDX is the maximum number of symbols
2714 permitted. *TABLE_BITS is the maximum number of bits for symbols in the
2715 table: the size of *TABLE is at least 1 << *TABLE_BITS. This updates
2716 *TABLE_BITS to the actual number of bits. Returns 1 on success, 0 on
2717 error. */
2718
2719static int
2720elf_zstd_read_fse (const unsigned char **ppin, const unsigned char *pinend,
2721 uint16_t *zdebug_table, int maxidx,
2722 struct elf_zstd_fse_entry *table, int *table_bits)
2723{
2724 const unsigned char *pin;
2725 int16_t *norm;
2726 uint16_t *next;
2727 uint64_t val;
2728 unsigned int bits;
2729 int accuracy_log;
2730 uint32_t remaining;
2731 uint32_t threshold;
2732 int bits_needed;
2733 int idx;
2734 int prev0;
2735
2736 pin = *ppin;
2737
2738 norm = (int16_t *) zdebug_table;
2739 next = zdebug_table + 256;
2740
2741 if (unlikely (pin + 3 >= pinend))
2742 {
2743 elf_uncompress_failed ();
2744 return 0;
2745 }
2746
2747 /* Align PIN to a 32-bit boundary. */
2748
2749 val = 0;
2750 bits = 0;
2751 while ((((uintptr_t) pin) & 3) != 0)
2752 {
2753 val |= (uint64_t)*pin << bits;
2754 bits += 8;
2755 ++pin;
2756 }
2757
2758 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2759 return 0;
2760
2761 accuracy_log = (val & 0xf) + 5;
2762 if (accuracy_log > *table_bits)
2763 {
2764 elf_uncompress_failed ();
2765 return 0;
2766 }
2767 *table_bits = accuracy_log;
2768 val >>= 4;
2769 bits -= 4;
2770
2771 /* This code is mostly copied from the reference implementation. */
2772
2773 /* The number of remaining probabilities, plus 1. This sets the number of
2774 bits that need to be read for the next value. */
2775 remaining = (1 << accuracy_log) + 1;
2776
2777 /* The current difference between small and large values, which depends on
2778 the number of remaining values. Small values use one less bit. */
2779 threshold = 1 << accuracy_log;
2780
2781 /* The number of bits used to compute threshold. */
2782 bits_needed = accuracy_log + 1;
2783
2784 /* The next character value. */
2785 idx = 0;
2786
2787 /* Whether the last count was 0. */
2788 prev0 = 0;
2789
2790 while (remaining > 1 && idx <= maxidx)
2791 {
2792 uint32_t max;
2793 int32_t count;
2794
2795 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2796 return 0;
2797
2798 if (prev0)
2799 {
2800 int zidx;
2801
2802 /* Previous count was 0, so there is a 2-bit repeat flag. If the
2803 2-bit flag is 0b11, it adds 3 and then there is another repeat
2804 flag. */
2805 zidx = idx;
2806 while ((val & 0xfff) == 0xfff)
2807 {
2808 zidx += 3 * 6;
2809 val >>= 12;
2810 bits -= 12;
2811 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2812 return 0;
2813 }
2814 while ((val & 3) == 3)
2815 {
2816 zidx += 3;
2817 val >>= 2;
2818 bits -= 2;
2819 if (!elf_fetch_bits (ppin: &pin, pinend, pval: &val, pbits: &bits))
2820 return 0;
2821 }
2822 /* We have at least 13 bits here, don't need to fetch. */
2823 zidx += val & 3;
2824 val >>= 2;
2825 bits -= 2;
2826
2827 if (unlikely (zidx > maxidx))
2828 {
2829 elf_uncompress_failed ();
2830 return 0;
2831 }
2832
2833 for (; idx < zidx; idx++)
2834 norm[idx] = 0;
2835
2836 prev0 = 0;
2837 continue;
2838 }
2839
2840 max = (2 * threshold - 1) - remaining;
2841 if ((val & (threshold - 1)) < max)
2842 {
2843 /* A small value. */
2844 count = (int32_t) ((uint32_t) val & (threshold - 1));
2845 val >>= bits_needed - 1;
2846 bits -= bits_needed - 1;
2847 }
2848 else
2849 {
2850 /* A large value. */
2851 count = (int32_t) ((uint32_t) val & (2 * threshold - 1));
2852 if (count >= (int32_t) threshold)
2853 count -= (int32_t) max;
2854 val >>= bits_needed;
2855 bits -= bits_needed;
2856 }
2857
2858 count--;
2859 if (count >= 0)
2860 remaining -= count;
2861 else
2862 remaining--;
2863 if (unlikely (idx >= 256))
2864 {
2865 elf_uncompress_failed ();
2866 return 0;
2867 }
2868 norm[idx] = (int16_t) count;
2869 ++idx;
2870
2871 prev0 = count == 0;
2872
2873 while (remaining < threshold)
2874 {
2875 bits_needed--;
2876 threshold >>= 1;
2877 }
2878 }
2879
2880 if (unlikely (remaining != 1))
2881 {
2882 elf_uncompress_failed ();
2883 return 0;
2884 }
2885
2886 /* If we've read ahead more than a byte, back up. */
2887 while (bits >= 8)
2888 {
2889 --pin;
2890 bits -= 8;
2891 }
2892
2893 *ppin = pin;
2894
2895 for (; idx <= maxidx; idx++)
2896 norm[idx] = 0;
2897
2898 return elf_zstd_build_fse (norm, idx, next, *table_bits, table);
2899}
2900
2901/* Build the FSE decoding table from a list of probabilities. This reads from
2902 NORM of length IDX, uses NEXT as scratch space, and writes to *TABLE, whose
2903 size is TABLE_BITS. */
2904
2905static int
2906elf_zstd_build_fse (const int16_t *norm, int idx, uint16_t *next,
2907 int table_bits, struct elf_zstd_fse_entry *table)
2908{
2909 int table_size;
2910 int high_threshold;
2911 int i;
2912 int pos;
2913 int step;
2914 int mask;
2915
2916 table_size = 1 << table_bits;
2917 high_threshold = table_size - 1;
2918 for (i = 0; i < idx; i++)
2919 {
2920 int16_t n;
2921
2922 n = norm[i];
2923 if (n >= 0)
2924 next[i] = (uint16_t) n;
2925 else
2926 {
2927 table[high_threshold].symbol = (unsigned char) i;
2928 high_threshold--;
2929 next[i] = 1;
2930 }
2931 }
2932
2933 pos = 0;
2934 step = (table_size >> 1) + (table_size >> 3) + 3;
2935 mask = table_size - 1;
2936 for (i = 0; i < idx; i++)
2937 {
2938 int n;
2939 int j;
2940
2941 n = (int) norm[i];
2942 for (j = 0; j < n; j++)
2943 {
2944 table[pos].symbol = (unsigned char) i;
2945 pos = (pos + step) & mask;
2946 while (unlikely (pos > high_threshold))
2947 pos = (pos + step) & mask;
2948 }
2949 }
2950 if (unlikely (pos != 0))
2951 {
2952 elf_uncompress_failed ();
2953 return 0;
2954 }
2955
2956 for (i = 0; i < table_size; i++)
2957 {
2958 unsigned char sym;
2959 uint16_t next_state;
2960 int high_bit;
2961 int bits;
2962
2963 sym = table[i].symbol;
2964 next_state = next[sym];
2965 ++next[sym];
2966
2967 if (next_state == 0)
2968 {
2969 elf_uncompress_failed ();
2970 return 0;
2971 }
2972 high_bit = 31 - __builtin_clz (next_state);
2973
2974 bits = table_bits - high_bit;
2975 table[i].bits = (unsigned char) bits;
2976 table[i].base = (uint16_t) ((next_state << bits) - table_size);
2977 }
2978
2979 return 1;
2980}
2981
2982/* Encode the baseline and bits into a single 32-bit value. */
2983
2984#define ZSTD_ENCODE_BASELINE_BITS(baseline, basebits) \
2985 ((uint32_t)(baseline) | ((uint32_t)(basebits) << 24))
2986
2987#define ZSTD_DECODE_BASELINE(baseline_basebits) \
2988 ((uint32_t)(baseline_basebits) & 0xffffff)
2989
2990#define ZSTD_DECODE_BASEBITS(baseline_basebits) \
2991 ((uint32_t)(baseline_basebits) >> 24)
2992
2993/* Given a literal length code, we need to read a number of bits and add that
2994 to a baseline. For states 0 to 15 the baseline is the state and the number
2995 of bits is zero. */
2996
2997#define ZSTD_LITERAL_LENGTH_BASELINE_OFFSET (16)
2998
2999static const uint32_t elf_zstd_literal_length_base[] =
3000{
3001 ZSTD_ENCODE_BASELINE_BITS(16, 1),
3002 ZSTD_ENCODE_BASELINE_BITS(18, 1),
3003 ZSTD_ENCODE_BASELINE_BITS(20, 1),
3004 ZSTD_ENCODE_BASELINE_BITS(22, 1),
3005 ZSTD_ENCODE_BASELINE_BITS(24, 2),
3006 ZSTD_ENCODE_BASELINE_BITS(28, 2),
3007 ZSTD_ENCODE_BASELINE_BITS(32, 3),
3008 ZSTD_ENCODE_BASELINE_BITS(40, 3),
3009 ZSTD_ENCODE_BASELINE_BITS(48, 4),
3010 ZSTD_ENCODE_BASELINE_BITS(64, 6),
3011 ZSTD_ENCODE_BASELINE_BITS(128, 7),
3012 ZSTD_ENCODE_BASELINE_BITS(256, 8),
3013 ZSTD_ENCODE_BASELINE_BITS(512, 9),
3014 ZSTD_ENCODE_BASELINE_BITS(1024, 10),
3015 ZSTD_ENCODE_BASELINE_BITS(2048, 11),
3016 ZSTD_ENCODE_BASELINE_BITS(4096, 12),
3017 ZSTD_ENCODE_BASELINE_BITS(8192, 13),
3018 ZSTD_ENCODE_BASELINE_BITS(16384, 14),
3019 ZSTD_ENCODE_BASELINE_BITS(32768, 15),
3020 ZSTD_ENCODE_BASELINE_BITS(65536, 16)
3021};
3022
3023/* The same applies to match length codes. For states 0 to 31 the baseline is
3024 the state + 3 and the number of bits is zero. */
3025
3026#define ZSTD_MATCH_LENGTH_BASELINE_OFFSET (32)
3027
3028static const uint32_t elf_zstd_match_length_base[] =
3029{
3030 ZSTD_ENCODE_BASELINE_BITS(35, 1),
3031 ZSTD_ENCODE_BASELINE_BITS(37, 1),
3032 ZSTD_ENCODE_BASELINE_BITS(39, 1),
3033 ZSTD_ENCODE_BASELINE_BITS(41, 1),
3034 ZSTD_ENCODE_BASELINE_BITS(43, 2),
3035 ZSTD_ENCODE_BASELINE_BITS(47, 2),
3036 ZSTD_ENCODE_BASELINE_BITS(51, 3),
3037 ZSTD_ENCODE_BASELINE_BITS(59, 3),
3038 ZSTD_ENCODE_BASELINE_BITS(67, 4),
3039 ZSTD_ENCODE_BASELINE_BITS(83, 4),
3040 ZSTD_ENCODE_BASELINE_BITS(99, 5),
3041 ZSTD_ENCODE_BASELINE_BITS(131, 7),
3042 ZSTD_ENCODE_BASELINE_BITS(259, 8),
3043 ZSTD_ENCODE_BASELINE_BITS(515, 9),
3044 ZSTD_ENCODE_BASELINE_BITS(1027, 10),
3045 ZSTD_ENCODE_BASELINE_BITS(2051, 11),
3046 ZSTD_ENCODE_BASELINE_BITS(4099, 12),
3047 ZSTD_ENCODE_BASELINE_BITS(8195, 13),
3048 ZSTD_ENCODE_BASELINE_BITS(16387, 14),
3049 ZSTD_ENCODE_BASELINE_BITS(32771, 15),
3050 ZSTD_ENCODE_BASELINE_BITS(65539, 16)
3051};
3052
3053/* An entry in an FSE table used for literal/match/length values. For these we
3054 have to map the symbol to a baseline value, and we have to read zero or more
3055 bits and add that value to the baseline value. Rather than look the values
3056 up in a separate table, we grow the FSE table so that we get better memory
3057 caching. */
3058
3059struct elf_zstd_fse_baseline_entry
3060{
3061 /* The baseline for the value that this FSE entry represents.. */
3062 uint32_t baseline;
3063 /* The number of bits to read to add to the baseline. */
3064 unsigned char basebits;
3065 /* The number of bits to read to determine the next state. */
3066 unsigned char bits;
3067 /* Add the bits to this base to get the next state. */
3068 uint16_t base;
3069};
3070
3071/* Convert the literal length FSE table FSE_TABLE to an FSE baseline table at
3072 BASELINE_TABLE. Note that FSE_TABLE and BASELINE_TABLE will overlap. */
3073
3074static int
3075elf_zstd_make_literal_baseline_fse (
3076 const struct elf_zstd_fse_entry *fse_table,
3077 int table_bits,
3078 struct elf_zstd_fse_baseline_entry *baseline_table)
3079{
3080 size_t count;
3081 const struct elf_zstd_fse_entry *pfse;
3082 struct elf_zstd_fse_baseline_entry *pbaseline;
3083
3084 /* Convert backward to avoid overlap. */
3085
3086 count = 1U << table_bits;
3087 pfse = fse_table + count;
3088 pbaseline = baseline_table + count;
3089 while (pfse > fse_table)
3090 {
3091 unsigned char symbol;
3092 unsigned char bits;
3093 uint16_t base;
3094
3095 --pfse;
3096 --pbaseline;
3097 symbol = pfse->symbol;
3098 bits = pfse->bits;
3099 base = pfse->base;
3100 if (symbol < ZSTD_LITERAL_LENGTH_BASELINE_OFFSET)
3101 {
3102 pbaseline->baseline = (uint32_t)symbol;
3103 pbaseline->basebits = 0;
3104 }
3105 else
3106 {
3107 unsigned int idx;
3108 uint32_t basebits;
3109
3110 if (unlikely (symbol > 35))
3111 {
3112 elf_uncompress_failed ();
3113 return 0;
3114 }
3115 idx = symbol - ZSTD_LITERAL_LENGTH_BASELINE_OFFSET;
3116 basebits = elf_zstd_literal_length_base[idx];
3117 pbaseline->baseline = ZSTD_DECODE_BASELINE(basebits);
3118 pbaseline->basebits = ZSTD_DECODE_BASEBITS(basebits);
3119 }
3120 pbaseline->bits = bits;
3121 pbaseline->base = base;
3122 }
3123
3124 return 1;
3125}
3126
3127/* Convert the offset length FSE table FSE_TABLE to an FSE baseline table at
3128 BASELINE_TABLE. Note that FSE_TABLE and BASELINE_TABLE will overlap. */
3129
3130static int
3131elf_zstd_make_offset_baseline_fse (
3132 const struct elf_zstd_fse_entry *fse_table,
3133 int table_bits,
3134 struct elf_zstd_fse_baseline_entry *baseline_table)
3135{
3136 size_t count;
3137 const struct elf_zstd_fse_entry *pfse;
3138 struct elf_zstd_fse_baseline_entry *pbaseline;
3139
3140 /* Convert backward to avoid overlap. */
3141
3142 count = 1U << table_bits;
3143 pfse = fse_table + count;
3144 pbaseline = baseline_table + count;
3145 while (pfse > fse_table)
3146 {
3147 unsigned char symbol;
3148 unsigned char bits;
3149 uint16_t base;
3150
3151 --pfse;
3152 --pbaseline;
3153 symbol = pfse->symbol;
3154 bits = pfse->bits;
3155 base = pfse->base;
3156 if (unlikely (symbol > 31))
3157 {
3158 elf_uncompress_failed ();
3159 return 0;
3160 }
3161
3162 /* The simple way to write this is
3163
3164 pbaseline->baseline = (uint32_t)1 << symbol;
3165 pbaseline->basebits = symbol;
3166
3167 That will give us an offset value that corresponds to the one
3168 described in the RFC. However, for offset values > 3, we have to
3169 subtract 3. And for offset values 1, 2, 3 we use a repeated offset.
3170 The baseline is always a power of 2, and is never 0, so for these low
3171 values we will see one entry that is baseline 1, basebits 0, and one
3172 entry that is baseline 2, basebits 1. All other entries will have
3173 baseline >= 4 and basebits >= 2.
3174
3175 So we can check for RFC offset <= 3 by checking for basebits <= 1.
3176 And that means that we can subtract 3 here and not worry about doing
3177 it in the hot loop. */
3178
3179 pbaseline->baseline = (uint32_t)1 << symbol;
3180 if (symbol >= 2)
3181 pbaseline->baseline -= 3;
3182 pbaseline->basebits = symbol;
3183 pbaseline->bits = bits;
3184 pbaseline->base = base;
3185 }
3186
3187 return 1;
3188}
3189
3190/* Convert the match length FSE table FSE_TABLE to an FSE baseline table at
3191 BASELINE_TABLE. Note that FSE_TABLE and BASELINE_TABLE will overlap. */
3192
3193static int
3194elf_zstd_make_match_baseline_fse (
3195 const struct elf_zstd_fse_entry *fse_table,
3196 int table_bits,
3197 struct elf_zstd_fse_baseline_entry *baseline_table)
3198{
3199 size_t count;
3200 const struct elf_zstd_fse_entry *pfse;
3201 struct elf_zstd_fse_baseline_entry *pbaseline;
3202
3203 /* Convert backward to avoid overlap. */
3204
3205 count = 1U << table_bits;
3206 pfse = fse_table + count;
3207 pbaseline = baseline_table + count;
3208 while (pfse > fse_table)
3209 {
3210 unsigned char symbol;
3211 unsigned char bits;
3212 uint16_t base;
3213
3214 --pfse;
3215 --pbaseline;
3216 symbol = pfse->symbol;
3217 bits = pfse->bits;
3218 base = pfse->base;
3219 if (symbol < ZSTD_MATCH_LENGTH_BASELINE_OFFSET)
3220 {
3221 pbaseline->baseline = (uint32_t)symbol + 3;
3222 pbaseline->basebits = 0;
3223 }
3224 else
3225 {
3226 unsigned int idx;
3227 uint32_t basebits;
3228
3229 if (unlikely (symbol > 52))
3230 {
3231 elf_uncompress_failed ();
3232 return 0;
3233 }
3234 idx = symbol - ZSTD_MATCH_LENGTH_BASELINE_OFFSET;
3235 basebits = elf_zstd_match_length_base[idx];
3236 pbaseline->baseline = ZSTD_DECODE_BASELINE(basebits);
3237 pbaseline->basebits = ZSTD_DECODE_BASEBITS(basebits);
3238 }
3239 pbaseline->bits = bits;
3240 pbaseline->base = base;
3241 }
3242
3243 return 1;
3244}
3245
3246#ifdef BACKTRACE_GENERATE_ZSTD_FSE_TABLES
3247
3248/* Used to generate the predefined FSE decoding tables for zstd. */
3249
3250#include <stdio.h>
3251
3252/* These values are straight from RFC 8878. */
3253
3254static int16_t lit[36] =
3255{
3256 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
3257 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
3258 -1,-1,-1,-1
3259};
3260
3261static int16_t match[53] =
3262{
3263 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
3264 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
3265 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
3266 -1,-1,-1,-1,-1
3267};
3268
3269static int16_t offset[29] =
3270{
3271 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
3272 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1
3273};
3274
3275static uint16_t next[256];
3276
3277static void
3278print_table (const struct elf_zstd_fse_baseline_entry *table, size_t size)
3279{
3280 size_t i;
3281
3282 printf ("{\n");
3283 for (i = 0; i < size; i += 3)
3284 {
3285 int j;
3286
3287 printf (" ");
3288 for (j = 0; j < 3 && i + j < size; ++j)
3289 printf (" { %u, %d, %d, %d },", table[i + j].baseline,
3290 table[i + j].basebits, table[i + j].bits,
3291 table[i + j].base);
3292 printf ("\n");
3293 }
3294 printf ("};\n");
3295}
3296
3297int
3298main ()
3299{
3300 struct elf_zstd_fse_entry lit_table[64];
3301 struct elf_zstd_fse_baseline_entry lit_baseline[64];
3302 struct elf_zstd_fse_entry match_table[64];
3303 struct elf_zstd_fse_baseline_entry match_baseline[64];
3304 struct elf_zstd_fse_entry offset_table[32];
3305 struct elf_zstd_fse_baseline_entry offset_baseline[32];
3306
3307 if (!elf_zstd_build_fse (lit, sizeof lit / sizeof lit[0], next,
3308 6, lit_table))
3309 {
3310 fprintf (stderr, "elf_zstd_build_fse failed\n");
3311 exit (EXIT_FAILURE);
3312 }
3313
3314 if (!elf_zstd_make_literal_baseline_fse (lit_table, 6, lit_baseline))
3315 {
3316 fprintf (stderr, "elf_zstd_make_literal_baseline_fse failed\n");
3317 exit (EXIT_FAILURE);
3318 }
3319
3320 printf ("static const struct elf_zstd_fse_baseline_entry "
3321 "elf_zstd_lit_table[64] =\n");
3322 print_table (lit_baseline,
3323 sizeof lit_baseline / sizeof lit_baseline[0]);
3324 printf ("\n");
3325
3326 if (!elf_zstd_build_fse (match, sizeof match / sizeof match[0], next,
3327 6, match_table))
3328 {
3329 fprintf (stderr, "elf_zstd_build_fse failed\n");
3330 exit (EXIT_FAILURE);
3331 }
3332
3333 if (!elf_zstd_make_match_baseline_fse (match_table, 6, match_baseline))
3334 {
3335 fprintf (stderr, "elf_zstd_make_match_baseline_fse failed\n");
3336 exit (EXIT_FAILURE);
3337 }
3338
3339 printf ("static const struct elf_zstd_fse_baseline_entry "
3340 "elf_zstd_match_table[64] =\n");
3341 print_table (match_baseline,
3342 sizeof match_baseline / sizeof match_baseline[0]);
3343 printf ("\n");
3344
3345 if (!elf_zstd_build_fse (offset, sizeof offset / sizeof offset[0], next,
3346 5, offset_table))
3347 {
3348 fprintf (stderr, "elf_zstd_build_fse failed\n");
3349 exit (EXIT_FAILURE);
3350 }
3351
3352 if (!elf_zstd_make_offset_baseline_fse (offset_table, 5, offset_baseline))
3353 {
3354 fprintf (stderr, "elf_zstd_make_offset_baseline_fse failed\n");
3355 exit (EXIT_FAILURE);
3356 }
3357
3358 printf ("static const struct elf_zstd_fse_baseline_entry "
3359 "elf_zstd_offset_table[32] =\n");
3360 print_table (offset_baseline,
3361 sizeof offset_baseline / sizeof offset_baseline[0]);
3362 printf ("\n");
3363
3364 return 0;
3365}
3366
3367#endif
3368
3369/* The fixed tables generated by the #ifdef'ed out main function
3370 above. */
3371
3372static const struct elf_zstd_fse_baseline_entry elf_zstd_lit_table[64] =
3373{
3374 { .baseline: 0, .basebits: 0, .bits: 4, .base: 0 }, { .baseline: 0, .basebits: 0, .bits: 4, .base: 16 }, { .baseline: 1, .basebits: 0, .bits: 5, .base: 32 },
3375 { .baseline: 3, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 4, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 6, .basebits: 0, .bits: 5, .base: 0 },
3376 { .baseline: 7, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 9, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 10, .basebits: 0, .bits: 5, .base: 0 },
3377 { .baseline: 12, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 14, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 16, .basebits: 1, .bits: 5, .base: 0 },
3378 { .baseline: 20, .basebits: 1, .bits: 5, .base: 0 }, { .baseline: 22, .basebits: 1, .bits: 5, .base: 0 }, { .baseline: 28, .basebits: 2, .bits: 5, .base: 0 },
3379 { .baseline: 32, .basebits: 3, .bits: 5, .base: 0 }, { .baseline: 48, .basebits: 4, .bits: 5, .base: 0 }, { .baseline: 64, .basebits: 6, .bits: 5, .base: 32 },
3380 { .baseline: 128, .basebits: 7, .bits: 5, .base: 0 }, { .baseline: 256, .basebits: 8, .bits: 6, .base: 0 }, { .baseline: 1024, .basebits: 10, .bits: 6, .base: 0 },
3381 { .baseline: 4096, .basebits: 12, .bits: 6, .base: 0 }, { .baseline: 0, .basebits: 0, .bits: 4, .base: 32 }, { .baseline: 1, .basebits: 0, .bits: 4, .base: 0 },
3382 { .baseline: 2, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 4, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 5, .basebits: 0, .bits: 5, .base: 0 },
3383 { .baseline: 7, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 8, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 10, .basebits: 0, .bits: 5, .base: 32 },
3384 { .baseline: 11, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 13, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 16, .basebits: 1, .bits: 5, .base: 32 },
3385 { .baseline: 18, .basebits: 1, .bits: 5, .base: 0 }, { .baseline: 22, .basebits: 1, .bits: 5, .base: 32 }, { .baseline: 24, .basebits: 2, .bits: 5, .base: 0 },
3386 { .baseline: 32, .basebits: 3, .bits: 5, .base: 32 }, { .baseline: 40, .basebits: 3, .bits: 5, .base: 0 }, { .baseline: 64, .basebits: 6, .bits: 4, .base: 0 },
3387 { .baseline: 64, .basebits: 6, .bits: 4, .base: 16 }, { .baseline: 128, .basebits: 7, .bits: 5, .base: 32 }, { .baseline: 512, .basebits: 9, .bits: 6, .base: 0 },
3388 { .baseline: 2048, .basebits: 11, .bits: 6, .base: 0 }, { .baseline: 0, .basebits: 0, .bits: 4, .base: 48 }, { .baseline: 1, .basebits: 0, .bits: 4, .base: 16 },
3389 { .baseline: 2, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 3, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 5, .basebits: 0, .bits: 5, .base: 32 },
3390 { .baseline: 6, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 8, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 9, .basebits: 0, .bits: 5, .base: 32 },
3391 { .baseline: 11, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 12, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 15, .basebits: 0, .bits: 6, .base: 0 },
3392 { .baseline: 18, .basebits: 1, .bits: 5, .base: 32 }, { .baseline: 20, .basebits: 1, .bits: 5, .base: 32 }, { .baseline: 24, .basebits: 2, .bits: 5, .base: 32 },
3393 { .baseline: 28, .basebits: 2, .bits: 5, .base: 32 }, { .baseline: 40, .basebits: 3, .bits: 5, .base: 32 }, { .baseline: 48, .basebits: 4, .bits: 5, .base: 32 },
3394 { .baseline: 65536, .basebits: 16, .bits: 6, .base: 0 }, { .baseline: 32768, .basebits: 15, .bits: 6, .base: 0 }, { .baseline: 16384, .basebits: 14, .bits: 6, .base: 0 },
3395 { .baseline: 8192, .basebits: 13, .bits: 6, .base: 0 },
3396};
3397
3398static const struct elf_zstd_fse_baseline_entry elf_zstd_match_table[64] =
3399{
3400 { .baseline: 3, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 4, .basebits: 0, .bits: 4, .base: 0 }, { .baseline: 5, .basebits: 0, .bits: 5, .base: 32 },
3401 { .baseline: 6, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 8, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 9, .basebits: 0, .bits: 5, .base: 0 },
3402 { .baseline: 11, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 13, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 16, .basebits: 0, .bits: 6, .base: 0 },
3403 { .baseline: 19, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 22, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 25, .basebits: 0, .bits: 6, .base: 0 },
3404 { .baseline: 28, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 31, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 34, .basebits: 0, .bits: 6, .base: 0 },
3405 { .baseline: 37, .basebits: 1, .bits: 6, .base: 0 }, { .baseline: 41, .basebits: 1, .bits: 6, .base: 0 }, { .baseline: 47, .basebits: 2, .bits: 6, .base: 0 },
3406 { .baseline: 59, .basebits: 3, .bits: 6, .base: 0 }, { .baseline: 83, .basebits: 4, .bits: 6, .base: 0 }, { .baseline: 131, .basebits: 7, .bits: 6, .base: 0 },
3407 { .baseline: 515, .basebits: 9, .bits: 6, .base: 0 }, { .baseline: 4, .basebits: 0, .bits: 4, .base: 16 }, { .baseline: 5, .basebits: 0, .bits: 4, .base: 0 },
3408 { .baseline: 6, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 7, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 9, .basebits: 0, .bits: 5, .base: 32 },
3409 { .baseline: 10, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 12, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 15, .basebits: 0, .bits: 6, .base: 0 },
3410 { .baseline: 18, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 21, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 24, .basebits: 0, .bits: 6, .base: 0 },
3411 { .baseline: 27, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 30, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 33, .basebits: 0, .bits: 6, .base: 0 },
3412 { .baseline: 35, .basebits: 1, .bits: 6, .base: 0 }, { .baseline: 39, .basebits: 1, .bits: 6, .base: 0 }, { .baseline: 43, .basebits: 2, .bits: 6, .base: 0 },
3413 { .baseline: 51, .basebits: 3, .bits: 6, .base: 0 }, { .baseline: 67, .basebits: 4, .bits: 6, .base: 0 }, { .baseline: 99, .basebits: 5, .bits: 6, .base: 0 },
3414 { .baseline: 259, .basebits: 8, .bits: 6, .base: 0 }, { .baseline: 4, .basebits: 0, .bits: 4, .base: 32 }, { .baseline: 4, .basebits: 0, .bits: 4, .base: 48 },
3415 { .baseline: 5, .basebits: 0, .bits: 4, .base: 16 }, { .baseline: 7, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 8, .basebits: 0, .bits: 5, .base: 32 },
3416 { .baseline: 10, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 11, .basebits: 0, .bits: 5, .base: 32 }, { .baseline: 14, .basebits: 0, .bits: 6, .base: 0 },
3417 { .baseline: 17, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 20, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 23, .basebits: 0, .bits: 6, .base: 0 },
3418 { .baseline: 26, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 29, .basebits: 0, .bits: 6, .base: 0 }, { .baseline: 32, .basebits: 0, .bits: 6, .base: 0 },
3419 { .baseline: 65539, .basebits: 16, .bits: 6, .base: 0 }, { .baseline: 32771, .basebits: 15, .bits: 6, .base: 0 }, { .baseline: 16387, .basebits: 14, .bits: 6, .base: 0 },
3420 { .baseline: 8195, .basebits: 13, .bits: 6, .base: 0 }, { .baseline: 4099, .basebits: 12, .bits: 6, .base: 0 }, { .baseline: 2051, .basebits: 11, .bits: 6, .base: 0 },
3421 { .baseline: 1027, .basebits: 10, .bits: 6, .base: 0 },
3422};
3423
3424static const struct elf_zstd_fse_baseline_entry elf_zstd_offset_table[32] =
3425{
3426 { .baseline: 1, .basebits: 0, .bits: 5, .base: 0 }, { .baseline: 61, .basebits: 6, .bits: 4, .base: 0 }, { .baseline: 509, .basebits: 9, .bits: 5, .base: 0 },
3427 { .baseline: 32765, .basebits: 15, .bits: 5, .base: 0 }, { .baseline: 2097149, .basebits: 21, .bits: 5, .base: 0 }, { .baseline: 5, .basebits: 3, .bits: 5, .base: 0 },
3428 { .baseline: 125, .basebits: 7, .bits: 4, .base: 0 }, { .baseline: 4093, .basebits: 12, .bits: 5, .base: 0 }, { .baseline: 262141, .basebits: 18, .bits: 5, .base: 0 },
3429 { .baseline: 8388605, .basebits: 23, .bits: 5, .base: 0 }, { .baseline: 29, .basebits: 5, .bits: 5, .base: 0 }, { .baseline: 253, .basebits: 8, .bits: 4, .base: 0 },
3430 { .baseline: 16381, .basebits: 14, .bits: 5, .base: 0 }, { .baseline: 1048573, .basebits: 20, .bits: 5, .base: 0 }, { .baseline: 1, .basebits: 2, .bits: 5, .base: 0 },
3431 { .baseline: 125, .basebits: 7, .bits: 4, .base: 16 }, { .baseline: 2045, .basebits: 11, .bits: 5, .base: 0 }, { .baseline: 131069, .basebits: 17, .bits: 5, .base: 0 },
3432 { .baseline: 4194301, .basebits: 22, .bits: 5, .base: 0 }, { .baseline: 13, .basebits: 4, .bits: 5, .base: 0 }, { .baseline: 253, .basebits: 8, .bits: 4, .base: 16 },
3433 { .baseline: 8189, .basebits: 13, .bits: 5, .base: 0 }, { .baseline: 524285, .basebits: 19, .bits: 5, .base: 0 }, { .baseline: 2, .basebits: 1, .bits: 5, .base: 0 },
3434 { .baseline: 61, .basebits: 6, .bits: 4, .base: 16 }, { .baseline: 1021, .basebits: 10, .bits: 5, .base: 0 }, { .baseline: 65533, .basebits: 16, .bits: 5, .base: 0 },
3435 { .baseline: 268435453, .basebits: 28, .bits: 5, .base: 0 }, { .baseline: 134217725, .basebits: 27, .bits: 5, .base: 0 }, { .baseline: 67108861, .basebits: 26, .bits: 5, .base: 0 },
3436 { .baseline: 33554429, .basebits: 25, .bits: 5, .base: 0 }, { .baseline: 16777213, .basebits: 24, .bits: 5, .base: 0 },
3437};
3438
3439/* Read a zstd Huffman table and build the decoding table in *TABLE, reading
3440 and updating *PPIN. This sets *PTABLE_BITS to the number of bits of the
3441 table, such that the table length is 1 << *TABLE_BITS. ZDEBUG_TABLE is
3442 scratch space; it must be enough for 512 uint16_t values + 256 32-bit values
3443 (2048 bytes). Returns 1 on success, 0 on error. */
3444
3445static int
3446elf_zstd_read_huff (const unsigned char **ppin, const unsigned char *pinend,
3447 uint16_t *zdebug_table, uint16_t *table, int *ptable_bits)
3448{
3449 const unsigned char *pin;
3450 unsigned char hdr;
3451 unsigned char *weights;
3452 size_t count;
3453 uint32_t *weight_mark;
3454 size_t i;
3455 uint32_t weight_mask;
3456 size_t table_bits;
3457
3458 pin = *ppin;
3459 if (unlikely (pin >= pinend))
3460 {
3461 elf_uncompress_failed ();
3462 return 0;
3463 }
3464 hdr = *pin;
3465 ++pin;
3466
3467 weights = (unsigned char *) zdebug_table;
3468
3469 if (hdr < 128)
3470 {
3471 /* Table is compressed using FSE. */
3472
3473 struct elf_zstd_fse_entry *fse_table;
3474 int fse_table_bits;
3475 uint16_t *scratch;
3476 const unsigned char *pfse;
3477 const unsigned char *pback;
3478 uint64_t val;
3479 unsigned int bits;
3480 unsigned int state1, state2;
3481
3482 /* SCRATCH is used temporarily by elf_zstd_read_fse. It overlaps
3483 WEIGHTS. */
3484 scratch = zdebug_table;
3485 fse_table = (struct elf_zstd_fse_entry *) (scratch + 512);
3486 fse_table_bits = 6;
3487
3488 pfse = pin;
3489 if (!elf_zstd_read_fse (ppin: &pfse, pinend, zdebug_table: scratch, maxidx: 255, table: fse_table,
3490 table_bits: &fse_table_bits))
3491 return 0;
3492
3493 if (unlikely (pin + hdr > pinend))
3494 {
3495 elf_uncompress_failed ();
3496 return 0;
3497 }
3498
3499 /* We no longer need SCRATCH. Start recording weights. We need up to
3500 256 bytes of weights and 64 bytes of rank counts, so it won't overlap
3501 FSE_TABLE. */
3502
3503 pback = pin + hdr - 1;
3504
3505 if (!elf_fetch_backward_init (ppin: &pback, pinend: pfse, pval: &val, pbits: &bits))
3506 return 0;
3507
3508 bits -= fse_table_bits;
3509 state1 = (val >> bits) & ((1U << fse_table_bits) - 1);
3510 bits -= fse_table_bits;
3511 state2 = (val >> bits) & ((1U << fse_table_bits) - 1);
3512
3513 /* There are two independent FSE streams, tracked by STATE1 and STATE2.
3514 We decode them alternately. */
3515
3516 count = 0;
3517 while (1)
3518 {
3519 struct elf_zstd_fse_entry *pt;
3520 uint64_t v;
3521
3522 pt = &fse_table[state1];
3523
3524 if (unlikely (pin < pinend) && bits < pt->bits)
3525 {
3526 if (unlikely (count >= 254))
3527 {
3528 elf_uncompress_failed ();
3529 return 0;
3530 }
3531 weights[count] = (unsigned char) pt->symbol;
3532 weights[count + 1] = (unsigned char) fse_table[state2].symbol;
3533 count += 2;
3534 break;
3535 }
3536
3537 if (unlikely (pt->bits == 0))
3538 v = 0;
3539 else
3540 {
3541 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pfse, pval: &val, pbits: &bits))
3542 return 0;
3543
3544 bits -= pt->bits;
3545 v = (val >> bits) & (((uint64_t)1 << pt->bits) - 1);
3546 }
3547
3548 state1 = pt->base + v;
3549
3550 if (unlikely (count >= 255))
3551 {
3552 elf_uncompress_failed ();
3553 return 0;
3554 }
3555
3556 weights[count] = pt->symbol;
3557 ++count;
3558
3559 pt = &fse_table[state2];
3560
3561 if (unlikely (pin < pinend && bits < pt->bits))
3562 {
3563 if (unlikely (count >= 254))
3564 {
3565 elf_uncompress_failed ();
3566 return 0;
3567 }
3568 weights[count] = (unsigned char) pt->symbol;
3569 weights[count + 1] = (unsigned char) fse_table[state1].symbol;
3570 count += 2;
3571 break;
3572 }
3573
3574 if (unlikely (pt->bits == 0))
3575 v = 0;
3576 else
3577 {
3578 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pfse, pval: &val, pbits: &bits))
3579 return 0;
3580
3581 bits -= pt->bits;
3582 v = (val >> bits) & (((uint64_t)1 << pt->bits) - 1);
3583 }
3584
3585 state2 = pt->base + v;
3586
3587 if (unlikely (count >= 255))
3588 {
3589 elf_uncompress_failed ();
3590 return 0;
3591 }
3592
3593 weights[count] = pt->symbol;
3594 ++count;
3595 }
3596
3597 pin += hdr;
3598 }
3599 else
3600 {
3601 /* Table is not compressed. Each weight is 4 bits. */
3602
3603 count = hdr - 127;
3604 if (unlikely (pin + ((count + 1) / 2) >= pinend))
3605 {
3606 elf_uncompress_failed ();
3607 return 0;
3608 }
3609 for (i = 0; i < count; i += 2)
3610 {
3611 unsigned char b;
3612
3613 b = *pin;
3614 ++pin;
3615 weights[i] = b >> 4;
3616 weights[i + 1] = b & 0xf;
3617 }
3618 }
3619
3620 weight_mark = (uint32_t *) (weights + 256);
3621 memset (s: weight_mark, c: 0, n: 13 * sizeof (uint32_t));
3622 weight_mask = 0;
3623 for (i = 0; i < count; ++i)
3624 {
3625 unsigned char w;
3626
3627 w = weights[i];
3628 if (unlikely (w > 12))
3629 {
3630 elf_uncompress_failed ();
3631 return 0;
3632 }
3633 ++weight_mark[w];
3634 if (w > 0)
3635 weight_mask += 1U << (w - 1);
3636 }
3637 if (unlikely (weight_mask == 0))
3638 {
3639 elf_uncompress_failed ();
3640 return 0;
3641 }
3642
3643 table_bits = 32 - __builtin_clz (weight_mask);
3644 if (unlikely (table_bits > 11))
3645 {
3646 elf_uncompress_failed ();
3647 return 0;
3648 }
3649
3650 /* Work out the last weight value, which is omitted because the weights must
3651 sum to a power of two. */
3652 {
3653 uint32_t left;
3654 uint32_t high_bit;
3655
3656 left = ((uint32_t)1 << table_bits) - weight_mask;
3657 if (left == 0)
3658 {
3659 elf_uncompress_failed ();
3660 return 0;
3661 }
3662 high_bit = 31 - __builtin_clz (left);
3663 if (((uint32_t)1 << high_bit) != left)
3664 {
3665 elf_uncompress_failed ();
3666 return 0;
3667 }
3668
3669 if (unlikely (count >= 256))
3670 {
3671 elf_uncompress_failed ();
3672 return 0;
3673 }
3674
3675 weights[count] = high_bit + 1;
3676 ++count;
3677 ++weight_mark[high_bit + 1];
3678 }
3679
3680 if (weight_mark[1] < 2 || (weight_mark[1] & 1) != 0)
3681 {
3682 elf_uncompress_failed ();
3683 return 0;
3684 }
3685
3686 /* Change WEIGHT_MARK from a count of weights to the index of the first
3687 symbol for that weight. We shift the indexes to also store how many we
3688 have seen so far, below. */
3689 {
3690 uint32_t next;
3691
3692 next = 0;
3693 for (i = 0; i < table_bits; ++i)
3694 {
3695 uint32_t cur;
3696
3697 cur = next;
3698 next += weight_mark[i + 1] << i;
3699 weight_mark[i + 1] = cur;
3700 }
3701 }
3702
3703 for (i = 0; i < count; ++i)
3704 {
3705 unsigned char weight;
3706 uint32_t length;
3707 uint16_t tval;
3708 size_t start;
3709 uint32_t j;
3710
3711 weight = weights[i];
3712 if (weight == 0)
3713 continue;
3714
3715 length = 1U << (weight - 1);
3716 tval = (i << 8) | (table_bits + 1 - weight);
3717 start = weight_mark[weight];
3718 for (j = 0; j < length; ++j)
3719 table[start + j] = tval;
3720 weight_mark[weight] += length;
3721 }
3722
3723 *ppin = pin;
3724 *ptable_bits = (int)table_bits;
3725
3726 return 1;
3727}
3728
3729/* Read and decompress the literals and store them ending at POUTEND. This
3730 works because we are going to use all the literals in the output, so they
3731 must fit into the output buffer. HUFFMAN_TABLE, and PHUFFMAN_TABLE_BITS
3732 store the Huffman table across calls. SCRATCH is used to read a Huffman
3733 table. Store the start of the decompressed literals in *PPLIT. Update
3734 *PPIN. Return 1 on success, 0 on error. */
3735
3736static int
3737elf_zstd_read_literals (const unsigned char **ppin,
3738 const unsigned char *pinend,
3739 unsigned char *pout,
3740 unsigned char *poutend,
3741 uint16_t *scratch,
3742 uint16_t *huffman_table,
3743 int *phuffman_table_bits,
3744 unsigned char **pplit)
3745{
3746 const unsigned char *pin;
3747 unsigned char *plit;
3748 unsigned char hdr;
3749 uint32_t regenerated_size;
3750 uint32_t compressed_size;
3751 int streams;
3752 uint32_t total_streams_size;
3753 unsigned int huffman_table_bits;
3754 uint64_t huffman_mask;
3755
3756 pin = *ppin;
3757 if (unlikely (pin >= pinend))
3758 {
3759 elf_uncompress_failed ();
3760 return 0;
3761 }
3762 hdr = *pin;
3763 ++pin;
3764
3765 if ((hdr & 3) == 0 || (hdr & 3) == 1)
3766 {
3767 int raw;
3768
3769 /* Raw_Literals_Block or RLE_Literals_Block */
3770
3771 raw = (hdr & 3) == 0;
3772
3773 switch ((hdr >> 2) & 3)
3774 {
3775 case 0: case 2:
3776 regenerated_size = hdr >> 3;
3777 break;
3778 case 1:
3779 if (unlikely (pin >= pinend))
3780 {
3781 elf_uncompress_failed ();
3782 return 0;
3783 }
3784 regenerated_size = (hdr >> 4) + ((uint32_t)(*pin) << 4);
3785 ++pin;
3786 break;
3787 case 3:
3788 if (unlikely (pin + 1 >= pinend))
3789 {
3790 elf_uncompress_failed ();
3791 return 0;
3792 }
3793 regenerated_size = ((hdr >> 4)
3794 + ((uint32_t)*pin << 4)
3795 + ((uint32_t)pin[1] << 12));
3796 pin += 2;
3797 break;
3798 default:
3799 elf_uncompress_failed ();
3800 return 0;
3801 }
3802
3803 if (unlikely ((size_t)(poutend - pout) < regenerated_size))
3804 {
3805 elf_uncompress_failed ();
3806 return 0;
3807 }
3808
3809 plit = poutend - regenerated_size;
3810
3811 if (raw)
3812 {
3813 if (unlikely (pin + regenerated_size >= pinend))
3814 {
3815 elf_uncompress_failed ();
3816 return 0;
3817 }
3818 memcpy (dest: plit, src: pin, n: regenerated_size);
3819 pin += regenerated_size;
3820 }
3821 else
3822 {
3823 if (pin >= pinend)
3824 {
3825 elf_uncompress_failed ();
3826 return 0;
3827 }
3828 memset (s: plit, c: *pin, n: regenerated_size);
3829 ++pin;
3830 }
3831
3832 *ppin = pin;
3833 *pplit = plit;
3834
3835 return 1;
3836 }
3837
3838 /* Compressed_Literals_Block or Treeless_Literals_Block */
3839
3840 switch ((hdr >> 2) & 3)
3841 {
3842 case 0: case 1:
3843 if (unlikely (pin + 1 >= pinend))
3844 {
3845 elf_uncompress_failed ();
3846 return 0;
3847 }
3848 regenerated_size = (hdr >> 4) | ((uint32_t)(*pin & 0x3f) << 4);
3849 compressed_size = (uint32_t)*pin >> 6 | ((uint32_t)pin[1] << 2);
3850 pin += 2;
3851 streams = ((hdr >> 2) & 3) == 0 ? 1 : 4;
3852 break;
3853 case 2:
3854 if (unlikely (pin + 2 >= pinend))
3855 {
3856 elf_uncompress_failed ();
3857 return 0;
3858 }
3859 regenerated_size = (((uint32_t)hdr >> 4)
3860 | ((uint32_t)*pin << 4)
3861 | (((uint32_t)pin[1] & 3) << 12));
3862 compressed_size = (((uint32_t)pin[1] >> 2)
3863 | ((uint32_t)pin[2] << 6));
3864 pin += 3;
3865 streams = 4;
3866 break;
3867 case 3:
3868 if (unlikely (pin + 3 >= pinend))
3869 {
3870 elf_uncompress_failed ();
3871 return 0;
3872 }
3873 regenerated_size = (((uint32_t)hdr >> 4)
3874 | ((uint32_t)*pin << 4)
3875 | (((uint32_t)pin[1] & 0x3f) << 12));
3876 compressed_size = (((uint32_t)pin[1] >> 6)
3877 | ((uint32_t)pin[2] << 2)
3878 | ((uint32_t)pin[3] << 10));
3879 pin += 4;
3880 streams = 4;
3881 break;
3882 default:
3883 elf_uncompress_failed ();
3884 return 0;
3885 }
3886
3887 if (unlikely (pin + compressed_size > pinend))
3888 {
3889 elf_uncompress_failed ();
3890 return 0;
3891 }
3892
3893 pinend = pin + compressed_size;
3894 *ppin = pinend;
3895
3896 if (unlikely ((size_t)(poutend - pout) < regenerated_size))
3897 {
3898 elf_uncompress_failed ();
3899 return 0;
3900 }
3901
3902 plit = poutend - regenerated_size;
3903
3904 *pplit = plit;
3905
3906 total_streams_size = compressed_size;
3907 if ((hdr & 3) == 2)
3908 {
3909 const unsigned char *ptable;
3910
3911 /* Compressed_Literals_Block. Read Huffman tree. */
3912
3913 ptable = pin;
3914 if (!elf_zstd_read_huff (ppin: &ptable, pinend, zdebug_table: scratch, table: huffman_table,
3915 ptable_bits: phuffman_table_bits))
3916 return 0;
3917
3918 if (unlikely (total_streams_size < (size_t)(ptable - pin)))
3919 {
3920 elf_uncompress_failed ();
3921 return 0;
3922 }
3923
3924 total_streams_size -= ptable - pin;
3925 pin = ptable;
3926 }
3927 else
3928 {
3929 /* Treeless_Literals_Block. Reuse previous Huffman tree. */
3930 if (unlikely (*phuffman_table_bits == 0))
3931 {
3932 elf_uncompress_failed ();
3933 return 0;
3934 }
3935 }
3936
3937 /* Decompress COMPRESSED_SIZE bytes of data at PIN using the huffman table,
3938 storing REGENERATED_SIZE bytes of decompressed data at PLIT. */
3939
3940 huffman_table_bits = (unsigned int)*phuffman_table_bits;
3941 huffman_mask = ((uint64_t)1 << huffman_table_bits) - 1;
3942
3943 if (streams == 1)
3944 {
3945 const unsigned char *pback;
3946 const unsigned char *pbackend;
3947 uint64_t val;
3948 unsigned int bits;
3949 uint32_t i;
3950
3951 pback = pin + total_streams_size - 1;
3952 pbackend = pin;
3953 if (!elf_fetch_backward_init (ppin: &pback, pinend: pbackend, pval: &val, pbits: &bits))
3954 return 0;
3955
3956 /* This is one of the inner loops of the decompression algorithm, so we
3957 put some effort into optimization. We can't get more than 64 bytes
3958 from a single call to elf_fetch_bits_backward, and we can't subtract
3959 more than 11 bits at a time. */
3960
3961 if (regenerated_size >= 64)
3962 {
3963 unsigned char *plitstart;
3964 unsigned char *plitstop;
3965
3966 plitstart = plit;
3967 plitstop = plit + regenerated_size - 64;
3968 while (plit < plitstop)
3969 {
3970 uint16_t t;
3971
3972 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pbackend, pval: &val, pbits: &bits))
3973 return 0;
3974
3975 if (bits < 16)
3976 break;
3977
3978 while (bits >= 33)
3979 {
3980 t = huffman_table[(val >> (bits - huffman_table_bits))
3981 & huffman_mask];
3982 *plit = t >> 8;
3983 ++plit;
3984 bits -= t & 0xff;
3985
3986 t = huffman_table[(val >> (bits - huffman_table_bits))
3987 & huffman_mask];
3988 *plit = t >> 8;
3989 ++plit;
3990 bits -= t & 0xff;
3991
3992 t = huffman_table[(val >> (bits - huffman_table_bits))
3993 & huffman_mask];
3994 *plit = t >> 8;
3995 ++plit;
3996 bits -= t & 0xff;
3997 }
3998
3999 while (bits > 11)
4000 {
4001 t = huffman_table[(val >> (bits - huffman_table_bits))
4002 & huffman_mask];
4003 *plit = t >> 8;
4004 ++plit;
4005 bits -= t & 0xff;
4006 }
4007 }
4008
4009 regenerated_size -= plit - plitstart;
4010 }
4011
4012 for (i = 0; i < regenerated_size; ++i)
4013 {
4014 uint16_t t;
4015
4016 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pbackend, pval: &val, pbits: &bits))
4017 return 0;
4018
4019 if (unlikely (bits < huffman_table_bits))
4020 {
4021 t = huffman_table[(val << (huffman_table_bits - bits))
4022 & huffman_mask];
4023 if (unlikely (bits < (t & 0xff)))
4024 {
4025 elf_uncompress_failed ();
4026 return 0;
4027 }
4028 }
4029 else
4030 t = huffman_table[(val >> (bits - huffman_table_bits))
4031 & huffman_mask];
4032
4033 *plit = t >> 8;
4034 ++plit;
4035 bits -= t & 0xff;
4036 }
4037
4038 return 1;
4039 }
4040
4041 {
4042 uint32_t stream_size1, stream_size2, stream_size3, stream_size4;
4043 uint32_t tot;
4044 const unsigned char *pback1, *pback2, *pback3, *pback4;
4045 const unsigned char *pbackend1, *pbackend2, *pbackend3, *pbackend4;
4046 uint64_t val1, val2, val3, val4;
4047 unsigned int bits1, bits2, bits3, bits4;
4048 unsigned char *plit1, *plit2, *plit3, *plit4;
4049 uint32_t regenerated_stream_size;
4050 uint32_t regenerated_stream_size4;
4051 uint16_t t1, t2, t3, t4;
4052 uint32_t i;
4053 uint32_t limit;
4054
4055 /* Read jump table. */
4056 if (unlikely (pin + 5 >= pinend))
4057 {
4058 elf_uncompress_failed ();
4059 return 0;
4060 }
4061 stream_size1 = (uint32_t)*pin | ((uint32_t)pin[1] << 8);
4062 pin += 2;
4063 stream_size2 = (uint32_t)*pin | ((uint32_t)pin[1] << 8);
4064 pin += 2;
4065 stream_size3 = (uint32_t)*pin | ((uint32_t)pin[1] << 8);
4066 pin += 2;
4067 tot = stream_size1 + stream_size2 + stream_size3;
4068 if (unlikely (tot > total_streams_size - 6))
4069 {
4070 elf_uncompress_failed ();
4071 return 0;
4072 }
4073 stream_size4 = total_streams_size - 6 - tot;
4074
4075 pback1 = pin + stream_size1 - 1;
4076 pbackend1 = pin;
4077
4078 pback2 = pback1 + stream_size2;
4079 pbackend2 = pback1 + 1;
4080
4081 pback3 = pback2 + stream_size3;
4082 pbackend3 = pback2 + 1;
4083
4084 pback4 = pback3 + stream_size4;
4085 pbackend4 = pback3 + 1;
4086
4087 if (!elf_fetch_backward_init (ppin: &pback1, pinend: pbackend1, pval: &val1, pbits: &bits1))
4088 return 0;
4089 if (!elf_fetch_backward_init (ppin: &pback2, pinend: pbackend2, pval: &val2, pbits: &bits2))
4090 return 0;
4091 if (!elf_fetch_backward_init (ppin: &pback3, pinend: pbackend3, pval: &val3, pbits: &bits3))
4092 return 0;
4093 if (!elf_fetch_backward_init (ppin: &pback4, pinend: pbackend4, pval: &val4, pbits: &bits4))
4094 return 0;
4095
4096 regenerated_stream_size = (regenerated_size + 3) / 4;
4097
4098 plit1 = plit;
4099 plit2 = plit1 + regenerated_stream_size;
4100 plit3 = plit2 + regenerated_stream_size;
4101 plit4 = plit3 + regenerated_stream_size;
4102
4103 regenerated_stream_size4 = regenerated_size - regenerated_stream_size * 3;
4104
4105 /* We can't get more than 64 literal bytes from a single call to
4106 elf_fetch_bits_backward. The fourth stream can be up to 3 bytes less,
4107 so use as the limit. */
4108
4109 limit = regenerated_stream_size4 <= 64 ? 0 : regenerated_stream_size4 - 64;
4110 i = 0;
4111 while (i < limit)
4112 {
4113 if (!elf_fetch_bits_backward (ppin: &pback1, pinend: pbackend1, pval: &val1, pbits: &bits1))
4114 return 0;
4115 if (!elf_fetch_bits_backward (ppin: &pback2, pinend: pbackend2, pval: &val2, pbits: &bits2))
4116 return 0;
4117 if (!elf_fetch_bits_backward (ppin: &pback3, pinend: pbackend3, pval: &val3, pbits: &bits3))
4118 return 0;
4119 if (!elf_fetch_bits_backward (ppin: &pback4, pinend: pbackend4, pval: &val4, pbits: &bits4))
4120 return 0;
4121
4122 /* We can't subtract more than 11 bits at a time. */
4123
4124 do
4125 {
4126 t1 = huffman_table[(val1 >> (bits1 - huffman_table_bits))
4127 & huffman_mask];
4128 t2 = huffman_table[(val2 >> (bits2 - huffman_table_bits))
4129 & huffman_mask];
4130 t3 = huffman_table[(val3 >> (bits3 - huffman_table_bits))
4131 & huffman_mask];
4132 t4 = huffman_table[(val4 >> (bits4 - huffman_table_bits))
4133 & huffman_mask];
4134
4135 *plit1 = t1 >> 8;
4136 ++plit1;
4137 bits1 -= t1 & 0xff;
4138
4139 *plit2 = t2 >> 8;
4140 ++plit2;
4141 bits2 -= t2 & 0xff;
4142
4143 *plit3 = t3 >> 8;
4144 ++plit3;
4145 bits3 -= t3 & 0xff;
4146
4147 *plit4 = t4 >> 8;
4148 ++plit4;
4149 bits4 -= t4 & 0xff;
4150
4151 ++i;
4152 }
4153 while (bits1 > 11 && bits2 > 11 && bits3 > 11 && bits4 > 11);
4154 }
4155
4156 while (i < regenerated_stream_size)
4157 {
4158 int use4;
4159
4160 use4 = i < regenerated_stream_size4;
4161
4162 if (!elf_fetch_bits_backward (ppin: &pback1, pinend: pbackend1, pval: &val1, pbits: &bits1))
4163 return 0;
4164 if (!elf_fetch_bits_backward (ppin: &pback2, pinend: pbackend2, pval: &val2, pbits: &bits2))
4165 return 0;
4166 if (!elf_fetch_bits_backward (ppin: &pback3, pinend: pbackend3, pval: &val3, pbits: &bits3))
4167 return 0;
4168 if (use4)
4169 {
4170 if (!elf_fetch_bits_backward (ppin: &pback4, pinend: pbackend4, pval: &val4, pbits: &bits4))
4171 return 0;
4172 }
4173
4174 if (unlikely (bits1 < huffman_table_bits))
4175 {
4176 t1 = huffman_table[(val1 << (huffman_table_bits - bits1))
4177 & huffman_mask];
4178 if (unlikely (bits1 < (t1 & 0xff)))
4179 {
4180 elf_uncompress_failed ();
4181 return 0;
4182 }
4183 }
4184 else
4185 t1 = huffman_table[(val1 >> (bits1 - huffman_table_bits))
4186 & huffman_mask];
4187
4188 if (unlikely (bits2 < huffman_table_bits))
4189 {
4190 t2 = huffman_table[(val2 << (huffman_table_bits - bits2))
4191 & huffman_mask];
4192 if (unlikely (bits2 < (t2 & 0xff)))
4193 {
4194 elf_uncompress_failed ();
4195 return 0;
4196 }
4197 }
4198 else
4199 t2 = huffman_table[(val2 >> (bits2 - huffman_table_bits))
4200 & huffman_mask];
4201
4202 if (unlikely (bits3 < huffman_table_bits))
4203 {
4204 t3 = huffman_table[(val3 << (huffman_table_bits - bits3))
4205 & huffman_mask];
4206 if (unlikely (bits3 < (t3 & 0xff)))
4207 {
4208 elf_uncompress_failed ();
4209 return 0;
4210 }
4211 }
4212 else
4213 t3 = huffman_table[(val3 >> (bits3 - huffman_table_bits))
4214 & huffman_mask];
4215
4216 if (use4)
4217 {
4218 if (unlikely (bits4 < huffman_table_bits))
4219 {
4220 t4 = huffman_table[(val4 << (huffman_table_bits - bits4))
4221 & huffman_mask];
4222 if (unlikely (bits4 < (t4 & 0xff)))
4223 {
4224 elf_uncompress_failed ();
4225 return 0;
4226 }
4227 }
4228 else
4229 t4 = huffman_table[(val4 >> (bits4 - huffman_table_bits))
4230 & huffman_mask];
4231
4232 *plit4 = t4 >> 8;
4233 ++plit4;
4234 bits4 -= t4 & 0xff;
4235 }
4236
4237 *plit1 = t1 >> 8;
4238 ++plit1;
4239 bits1 -= t1 & 0xff;
4240
4241 *plit2 = t2 >> 8;
4242 ++plit2;
4243 bits2 -= t2 & 0xff;
4244
4245 *plit3 = t3 >> 8;
4246 ++plit3;
4247 bits3 -= t3 & 0xff;
4248
4249 ++i;
4250 }
4251 }
4252
4253 return 1;
4254}
4255
4256/* The information used to decompress a sequence code, which can be a literal
4257 length, an offset, or a match length. */
4258
4259struct elf_zstd_seq_decode
4260{
4261 const struct elf_zstd_fse_baseline_entry *table;
4262 int table_bits;
4263};
4264
4265/* Unpack a sequence code compression mode. */
4266
4267static int
4268elf_zstd_unpack_seq_decode (int mode,
4269 const unsigned char **ppin,
4270 const unsigned char *pinend,
4271 const struct elf_zstd_fse_baseline_entry *predef,
4272 int predef_bits,
4273 uint16_t *scratch,
4274 int maxidx,
4275 struct elf_zstd_fse_baseline_entry *table,
4276 int table_bits,
4277 int (*conv)(const struct elf_zstd_fse_entry *,
4278 int,
4279 struct elf_zstd_fse_baseline_entry *),
4280 struct elf_zstd_seq_decode *decode)
4281{
4282 switch (mode)
4283 {
4284 case 0:
4285 decode->table = predef;
4286 decode->table_bits = predef_bits;
4287 break;
4288
4289 case 1:
4290 {
4291 struct elf_zstd_fse_entry entry;
4292
4293 if (unlikely (*ppin >= pinend))
4294 {
4295 elf_uncompress_failed ();
4296 return 0;
4297 }
4298 entry.symbol = **ppin;
4299 ++*ppin;
4300 entry.bits = 0;
4301 entry.base = 0;
4302 decode->table_bits = 0;
4303 if (!conv (&entry, 0, table))
4304 return 0;
4305 }
4306 break;
4307
4308 case 2:
4309 {
4310 struct elf_zstd_fse_entry *fse_table;
4311
4312 /* We use the same space for the simple FSE table and the baseline
4313 table. */
4314 fse_table = (struct elf_zstd_fse_entry *)table;
4315 decode->table_bits = table_bits;
4316 if (!elf_zstd_read_fse (ppin, pinend, zdebug_table: scratch, maxidx, table: fse_table,
4317 table_bits: &decode->table_bits))
4318 return 0;
4319 if (!conv (fse_table, decode->table_bits, table))
4320 return 0;
4321 decode->table = table;
4322 }
4323 break;
4324
4325 case 3:
4326 if (unlikely (decode->table_bits == -1))
4327 {
4328 elf_uncompress_failed ();
4329 return 0;
4330 }
4331 break;
4332
4333 default:
4334 elf_uncompress_failed ();
4335 return 0;
4336 }
4337
4338 return 1;
4339}
4340
4341/* Decompress a zstd stream from PIN/SIN to POUT/SOUT. Code based on RFC 8878.
4342 Return 1 on success, 0 on error. */
4343
4344static int
4345elf_zstd_decompress (const unsigned char *pin, size_t sin,
4346 unsigned char *zdebug_table, unsigned char *pout,
4347 size_t sout)
4348{
4349 const unsigned char *pinend;
4350 unsigned char *poutstart;
4351 unsigned char *poutend;
4352 struct elf_zstd_seq_decode literal_decode;
4353 struct elf_zstd_fse_baseline_entry *literal_fse_table;
4354 struct elf_zstd_seq_decode match_decode;
4355 struct elf_zstd_fse_baseline_entry *match_fse_table;
4356 struct elf_zstd_seq_decode offset_decode;
4357 struct elf_zstd_fse_baseline_entry *offset_fse_table;
4358 uint16_t *huffman_table;
4359 int huffman_table_bits;
4360 uint32_t repeated_offset1;
4361 uint32_t repeated_offset2;
4362 uint32_t repeated_offset3;
4363 uint16_t *scratch;
4364 unsigned char hdr;
4365 int has_checksum;
4366 uint64_t content_size;
4367 int last_block;
4368
4369 pinend = pin + sin;
4370 poutstart = pout;
4371 poutend = pout + sout;
4372
4373 literal_decode.table = NULL;
4374 literal_decode.table_bits = -1;
4375 literal_fse_table = ((struct elf_zstd_fse_baseline_entry *)
4376 (zdebug_table + ZSTD_TABLE_LITERAL_FSE_OFFSET));
4377
4378 match_decode.table = NULL;
4379 match_decode.table_bits = -1;
4380 match_fse_table = ((struct elf_zstd_fse_baseline_entry *)
4381 (zdebug_table + ZSTD_TABLE_MATCH_FSE_OFFSET));
4382
4383 offset_decode.table = NULL;
4384 offset_decode.table_bits = -1;
4385 offset_fse_table = ((struct elf_zstd_fse_baseline_entry *)
4386 (zdebug_table + ZSTD_TABLE_OFFSET_FSE_OFFSET));
4387 huffman_table = ((uint16_t *)
4388 (zdebug_table + ZSTD_TABLE_HUFFMAN_OFFSET));
4389 huffman_table_bits = 0;
4390 scratch = ((uint16_t *)
4391 (zdebug_table + ZSTD_TABLE_WORK_OFFSET));
4392
4393 repeated_offset1 = 1;
4394 repeated_offset2 = 4;
4395 repeated_offset3 = 8;
4396
4397 if (unlikely (sin < 4))
4398 {
4399 elf_uncompress_failed ();
4400 return 0;
4401 }
4402
4403 /* These values are the zstd magic number. */
4404 if (unlikely (pin[0] != 0x28
4405 || pin[1] != 0xb5
4406 || pin[2] != 0x2f
4407 || pin[3] != 0xfd))
4408 {
4409 elf_uncompress_failed ();
4410 return 0;
4411 }
4412
4413 pin += 4;
4414
4415 if (unlikely (pin >= pinend))
4416 {
4417 elf_uncompress_failed ();
4418 return 0;
4419 }
4420
4421 hdr = *pin++;
4422
4423 /* We expect a single frame. */
4424 if (unlikely ((hdr & (1 << 5)) == 0))
4425 {
4426 elf_uncompress_failed ();
4427 return 0;
4428 }
4429 /* Reserved bit must be zero. */
4430 if (unlikely ((hdr & (1 << 3)) != 0))
4431 {
4432 elf_uncompress_failed ();
4433 return 0;
4434 }
4435 /* We do not expect a dictionary. */
4436 if (unlikely ((hdr & 3) != 0))
4437 {
4438 elf_uncompress_failed ();
4439 return 0;
4440 }
4441 has_checksum = (hdr & (1 << 2)) != 0;
4442 switch (hdr >> 6)
4443 {
4444 case 0:
4445 if (unlikely (pin >= pinend))
4446 {
4447 elf_uncompress_failed ();
4448 return 0;
4449 }
4450 content_size = (uint64_t) *pin++;
4451 break;
4452 case 1:
4453 if (unlikely (pin + 1 >= pinend))
4454 {
4455 elf_uncompress_failed ();
4456 return 0;
4457 }
4458 content_size = (((uint64_t) pin[0]) | (((uint64_t) pin[1]) << 8)) + 256;
4459 pin += 2;
4460 break;
4461 case 2:
4462 if (unlikely (pin + 3 >= pinend))
4463 {
4464 elf_uncompress_failed ();
4465 return 0;
4466 }
4467 content_size = ((uint64_t) pin[0]
4468 | (((uint64_t) pin[1]) << 8)
4469 | (((uint64_t) pin[2]) << 16)
4470 | (((uint64_t) pin[3]) << 24));
4471 pin += 4;
4472 break;
4473 case 3:
4474 if (unlikely (pin + 7 >= pinend))
4475 {
4476 elf_uncompress_failed ();
4477 return 0;
4478 }
4479 content_size = ((uint64_t) pin[0]
4480 | (((uint64_t) pin[1]) << 8)
4481 | (((uint64_t) pin[2]) << 16)
4482 | (((uint64_t) pin[3]) << 24)
4483 | (((uint64_t) pin[4]) << 32)
4484 | (((uint64_t) pin[5]) << 40)
4485 | (((uint64_t) pin[6]) << 48)
4486 | (((uint64_t) pin[7]) << 56));
4487 pin += 8;
4488 break;
4489 default:
4490 elf_uncompress_failed ();
4491 return 0;
4492 }
4493
4494 if (unlikely (content_size != (size_t) content_size
4495 || (size_t) content_size != sout))
4496 {
4497 elf_uncompress_failed ();
4498 return 0;
4499 }
4500
4501 last_block = 0;
4502 while (!last_block)
4503 {
4504 uint32_t block_hdr;
4505 int block_type;
4506 uint32_t block_size;
4507
4508 if (unlikely (pin + 2 >= pinend))
4509 {
4510 elf_uncompress_failed ();
4511 return 0;
4512 }
4513 block_hdr = ((uint32_t) pin[0]
4514 | (((uint32_t) pin[1]) << 8)
4515 | (((uint32_t) pin[2]) << 16));
4516 pin += 3;
4517
4518 last_block = block_hdr & 1;
4519 block_type = (block_hdr >> 1) & 3;
4520 block_size = block_hdr >> 3;
4521
4522 switch (block_type)
4523 {
4524 case 0:
4525 /* Raw_Block */
4526 if (unlikely ((size_t) block_size > (size_t) (pinend - pin)))
4527 {
4528 elf_uncompress_failed ();
4529 return 0;
4530 }
4531 if (unlikely ((size_t) block_size > (size_t) (poutend - pout)))
4532 {
4533 elf_uncompress_failed ();
4534 return 0;
4535 }
4536 memcpy (dest: pout, src: pin, n: block_size);
4537 pout += block_size;
4538 pin += block_size;
4539 break;
4540
4541 case 1:
4542 /* RLE_Block */
4543 if (unlikely (pin >= pinend))
4544 {
4545 elf_uncompress_failed ();
4546 return 0;
4547 }
4548 if (unlikely ((size_t) block_size > (size_t) (poutend - pout)))
4549 {
4550 elf_uncompress_failed ();
4551 return 0;
4552 }
4553 memset (s: pout, c: *pin, n: block_size);
4554 pout += block_size;
4555 pin++;
4556 break;
4557
4558 case 2:
4559 {
4560 const unsigned char *pblockend;
4561 unsigned char *plitstack;
4562 unsigned char *plit;
4563 uint32_t literal_count;
4564 unsigned char seq_hdr;
4565 size_t seq_count;
4566 size_t seq;
4567 const unsigned char *pback;
4568 uint64_t val;
4569 unsigned int bits;
4570 unsigned int literal_state;
4571 unsigned int offset_state;
4572 unsigned int match_state;
4573
4574 /* Compressed_Block */
4575 if (unlikely ((size_t) block_size > (size_t) (pinend - pin)))
4576 {
4577 elf_uncompress_failed ();
4578 return 0;
4579 }
4580
4581 pblockend = pin + block_size;
4582
4583 /* Read the literals into the end of the output space, and leave
4584 PLIT pointing at them. */
4585
4586 if (!elf_zstd_read_literals (ppin: &pin, pinend: pblockend, pout, poutend,
4587 scratch, huffman_table,
4588 phuffman_table_bits: &huffman_table_bits,
4589 pplit: &plitstack))
4590 return 0;
4591 plit = plitstack;
4592 literal_count = poutend - plit;
4593
4594 seq_hdr = *pin;
4595 pin++;
4596 if (seq_hdr < 128)
4597 seq_count = seq_hdr;
4598 else if (seq_hdr < 255)
4599 {
4600 if (unlikely (pin >= pinend))
4601 {
4602 elf_uncompress_failed ();
4603 return 0;
4604 }
4605 seq_count = ((seq_hdr - 128) << 8) + *pin;
4606 pin++;
4607 }
4608 else
4609 {
4610 if (unlikely (pin + 1 >= pinend))
4611 {
4612 elf_uncompress_failed ();
4613 return 0;
4614 }
4615 seq_count = *pin + (pin[1] << 8) + 0x7f00;
4616 pin += 2;
4617 }
4618
4619 if (seq_count > 0)
4620 {
4621 int (*pfn)(const struct elf_zstd_fse_entry *,
4622 int, struct elf_zstd_fse_baseline_entry *);
4623
4624 if (unlikely (pin >= pinend))
4625 {
4626 elf_uncompress_failed ();
4627 return 0;
4628 }
4629 seq_hdr = *pin;
4630 ++pin;
4631
4632 pfn = elf_zstd_make_literal_baseline_fse;
4633 if (!elf_zstd_unpack_seq_decode (mode: (seq_hdr >> 6) & 3,
4634 ppin: &pin, pinend,
4635 predef: &elf_zstd_lit_table[0], predef_bits: 6,
4636 scratch, maxidx: 35,
4637 table: literal_fse_table, table_bits: 9, conv: pfn,
4638 decode: &literal_decode))
4639 return 0;
4640
4641 pfn = elf_zstd_make_offset_baseline_fse;
4642 if (!elf_zstd_unpack_seq_decode (mode: (seq_hdr >> 4) & 3,
4643 ppin: &pin, pinend,
4644 predef: &elf_zstd_offset_table[0], predef_bits: 5,
4645 scratch, maxidx: 31,
4646 table: offset_fse_table, table_bits: 8, conv: pfn,
4647 decode: &offset_decode))
4648 return 0;
4649
4650 pfn = elf_zstd_make_match_baseline_fse;
4651 if (!elf_zstd_unpack_seq_decode (mode: (seq_hdr >> 2) & 3,
4652 ppin: &pin, pinend,
4653 predef: &elf_zstd_match_table[0], predef_bits: 6,
4654 scratch, maxidx: 52,
4655 table: match_fse_table, table_bits: 9, conv: pfn,
4656 decode: &match_decode))
4657 return 0;
4658 }
4659
4660 pback = pblockend - 1;
4661 if (!elf_fetch_backward_init (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4662 return 0;
4663
4664 bits -= literal_decode.table_bits;
4665 literal_state = ((val >> bits)
4666 & ((1U << literal_decode.table_bits) - 1));
4667
4668 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4669 return 0;
4670 bits -= offset_decode.table_bits;
4671 offset_state = ((val >> bits)
4672 & ((1U << offset_decode.table_bits) - 1));
4673
4674 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4675 return 0;
4676 bits -= match_decode.table_bits;
4677 match_state = ((val >> bits)
4678 & ((1U << match_decode.table_bits) - 1));
4679
4680 seq = 0;
4681 while (1)
4682 {
4683 const struct elf_zstd_fse_baseline_entry *pt;
4684 uint32_t offset_basebits;
4685 uint32_t offset_baseline;
4686 uint32_t offset_bits;
4687 uint32_t offset_base;
4688 uint32_t offset;
4689 uint32_t match_baseline;
4690 uint32_t match_bits;
4691 uint32_t match_base;
4692 uint32_t match;
4693 uint32_t literal_baseline;
4694 uint32_t literal_bits;
4695 uint32_t literal_base;
4696 uint32_t literal;
4697 uint32_t need;
4698 uint32_t add;
4699
4700 pt = &offset_decode.table[offset_state];
4701 offset_basebits = pt->basebits;
4702 offset_baseline = pt->baseline;
4703 offset_bits = pt->bits;
4704 offset_base = pt->base;
4705
4706 /* This case can be more than 16 bits, which is all that
4707 elf_fetch_bits_backward promises. */
4708 need = offset_basebits;
4709 add = 0;
4710 if (unlikely (need > 16))
4711 {
4712 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4713 return 0;
4714 bits -= 16;
4715 add = (val >> bits) & ((1U << 16) - 1);
4716 need -= 16;
4717 add <<= need;
4718 }
4719 if (need > 0)
4720 {
4721 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4722 return 0;
4723 bits -= need;
4724 add += (val >> bits) & ((1U << need) - 1);
4725 }
4726
4727 offset = offset_baseline + add;
4728
4729 pt = &match_decode.table[match_state];
4730 need = pt->basebits;
4731 match_baseline = pt->baseline;
4732 match_bits = pt->bits;
4733 match_base = pt->base;
4734
4735 add = 0;
4736 if (need > 0)
4737 {
4738 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4739 return 0;
4740 bits -= need;
4741 add = (val >> bits) & ((1U << need) - 1);
4742 }
4743
4744 match = match_baseline + add;
4745
4746 pt = &literal_decode.table[literal_state];
4747 need = pt->basebits;
4748 literal_baseline = pt->baseline;
4749 literal_bits = pt->bits;
4750 literal_base = pt->base;
4751
4752 add = 0;
4753 if (need > 0)
4754 {
4755 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4756 return 0;
4757 bits -= need;
4758 add = (val >> bits) & ((1U << need) - 1);
4759 }
4760
4761 literal = literal_baseline + add;
4762
4763 /* See the comment in elf_zstd_make_offset_baseline_fse. */
4764 if (offset_basebits > 1)
4765 {
4766 repeated_offset3 = repeated_offset2;
4767 repeated_offset2 = repeated_offset1;
4768 repeated_offset1 = offset;
4769 }
4770 else
4771 {
4772 if (unlikely (literal == 0))
4773 ++offset;
4774 switch (offset)
4775 {
4776 case 1:
4777 offset = repeated_offset1;
4778 break;
4779 case 2:
4780 offset = repeated_offset2;
4781 repeated_offset2 = repeated_offset1;
4782 repeated_offset1 = offset;
4783 break;
4784 case 3:
4785 offset = repeated_offset3;
4786 repeated_offset3 = repeated_offset2;
4787 repeated_offset2 = repeated_offset1;
4788 repeated_offset1 = offset;
4789 break;
4790 case 4:
4791 offset = repeated_offset1 - 1;
4792 repeated_offset3 = repeated_offset2;
4793 repeated_offset2 = repeated_offset1;
4794 repeated_offset1 = offset;
4795 break;
4796 }
4797 }
4798
4799 ++seq;
4800 if (seq < seq_count)
4801 {
4802 uint32_t v;
4803
4804 /* Update the three states. */
4805
4806 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4807 return 0;
4808
4809 need = literal_bits;
4810 bits -= need;
4811 v = (val >> bits) & (((uint32_t)1 << need) - 1);
4812
4813 literal_state = literal_base + v;
4814
4815 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4816 return 0;
4817
4818 need = match_bits;
4819 bits -= need;
4820 v = (val >> bits) & (((uint32_t)1 << need) - 1);
4821
4822 match_state = match_base + v;
4823
4824 if (!elf_fetch_bits_backward (ppin: &pback, pinend: pin, pval: &val, pbits: &bits))
4825 return 0;
4826
4827 need = offset_bits;
4828 bits -= need;
4829 v = (val >> bits) & (((uint32_t)1 << need) - 1);
4830
4831 offset_state = offset_base + v;
4832 }
4833
4834 /* The next sequence is now in LITERAL, OFFSET, MATCH. */
4835
4836 /* Copy LITERAL bytes from the literals. */
4837
4838 if (unlikely ((size_t)(poutend - pout) < literal))
4839 {
4840 elf_uncompress_failed ();
4841 return 0;
4842 }
4843
4844 if (unlikely (literal_count < literal))
4845 {
4846 elf_uncompress_failed ();
4847 return 0;
4848 }
4849
4850 literal_count -= literal;
4851
4852 /* Often LITERAL is small, so handle small cases quickly. */
4853 switch (literal)
4854 {
4855 case 8:
4856 *pout++ = *plit++;
4857 /* FALLTHROUGH */
4858 case 7:
4859 *pout++ = *plit++;
4860 /* FALLTHROUGH */
4861 case 6:
4862 *pout++ = *plit++;
4863 /* FALLTHROUGH */
4864 case 5:
4865 *pout++ = *plit++;
4866 /* FALLTHROUGH */
4867 case 4:
4868 *pout++ = *plit++;
4869 /* FALLTHROUGH */
4870 case 3:
4871 *pout++ = *plit++;
4872 /* FALLTHROUGH */
4873 case 2:
4874 *pout++ = *plit++;
4875 /* FALLTHROUGH */
4876 case 1:
4877 *pout++ = *plit++;
4878 break;
4879
4880 case 0:
4881 break;
4882
4883 default:
4884 if (unlikely ((size_t)(plit - pout) < literal))
4885 {
4886 uint32_t move;
4887
4888 move = plit - pout;
4889 while (literal > move)
4890 {
4891 memcpy (dest: pout, src: plit, n: move);
4892 pout += move;
4893 plit += move;
4894 literal -= move;
4895 }
4896 }
4897
4898 memcpy (dest: pout, src: plit, n: literal);
4899 pout += literal;
4900 plit += literal;
4901 }
4902
4903 if (match > 0)
4904 {
4905 /* Copy MATCH bytes from the decoded output at OFFSET. */
4906
4907 if (unlikely ((size_t)(poutend - pout) < match))
4908 {
4909 elf_uncompress_failed ();
4910 return 0;
4911 }
4912
4913 if (unlikely ((size_t)(pout - poutstart) < offset))
4914 {
4915 elf_uncompress_failed ();
4916 return 0;
4917 }
4918
4919 if (offset >= match)
4920 {
4921 memcpy (dest: pout, src: pout - offset, n: match);
4922 pout += match;
4923 }
4924 else
4925 {
4926 while (match > 0)
4927 {
4928 uint32_t copy;
4929
4930 copy = match < offset ? match : offset;
4931 memcpy (dest: pout, src: pout - offset, n: copy);
4932 match -= copy;
4933 pout += copy;
4934 }
4935 }
4936 }
4937
4938 if (unlikely (seq >= seq_count))
4939 {
4940 /* Copy remaining literals. */
4941 if (literal_count > 0 && plit != pout)
4942 {
4943 if (unlikely ((size_t)(poutend - pout)
4944 < literal_count))
4945 {
4946 elf_uncompress_failed ();
4947 return 0;
4948 }
4949
4950 if ((size_t)(plit - pout) < literal_count)
4951 {
4952 uint32_t move;
4953
4954 move = plit - pout;
4955 while (literal_count > move)
4956 {
4957 memcpy (dest: pout, src: plit, n: move);
4958 pout += move;
4959 plit += move;
4960 literal_count -= move;
4961 }
4962 }
4963
4964 memcpy (dest: pout, src: plit, n: literal_count);
4965 }
4966
4967 pout += literal_count;
4968
4969 break;
4970 }
4971 }
4972
4973 pin = pblockend;
4974 }
4975 break;
4976
4977 case 3:
4978 default:
4979 elf_uncompress_failed ();
4980 return 0;
4981 }
4982 }
4983
4984 if (has_checksum)
4985 {
4986 if (unlikely (pin + 4 > pinend))
4987 {
4988 elf_uncompress_failed ();
4989 return 0;
4990 }
4991
4992 /* We don't currently verify the checksum. Currently running GNU ld with
4993 --compress-debug-sections=zstd does not seem to generate a
4994 checksum. */
4995
4996 pin += 4;
4997 }
4998
4999 if (pin != pinend)
5000 {
5001 elf_uncompress_failed ();
5002 return 0;
5003 }
5004
5005 return 1;
5006}
5007
5008#define ZDEBUG_TABLE_SIZE \
5009 (ZLIB_TABLE_SIZE > ZSTD_TABLE_SIZE ? ZLIB_TABLE_SIZE : ZSTD_TABLE_SIZE)
5010
5011/* Uncompress the old compressed debug format, the one emitted by
5012 --compress-debug-sections=zlib-gnu. The compressed data is in
5013 COMPRESSED / COMPRESSED_SIZE, and the function writes to
5014 *UNCOMPRESSED / *UNCOMPRESSED_SIZE. ZDEBUG_TABLE is work space to
5015 hold Huffman tables. Returns 0 on error, 1 on successful
5016 decompression or if something goes wrong. In general we try to
5017 carry on, by returning 1, even if we can't decompress. */
5018
5019static int
5020elf_uncompress_zdebug (struct backtrace_state *state,
5021 const unsigned char *compressed, size_t compressed_size,
5022 uint16_t *zdebug_table,
5023 backtrace_error_callback error_callback, void *data,
5024 unsigned char **uncompressed, size_t *uncompressed_size)
5025{
5026 size_t sz;
5027 size_t i;
5028 unsigned char *po;
5029
5030 *uncompressed = NULL;
5031 *uncompressed_size = 0;
5032
5033 /* The format starts with the four bytes ZLIB, followed by the 8
5034 byte length of the uncompressed data in big-endian order,
5035 followed by a zlib stream. */
5036
5037 if (compressed_size < 12 || memcmp (s1: compressed, s2: "ZLIB", n: 4) != 0)
5038 return 1;
5039
5040 sz = 0;
5041 for (i = 0; i < 8; i++)
5042 sz = (sz << 8) | compressed[i + 4];
5043
5044 if (*uncompressed != NULL && *uncompressed_size >= sz)
5045 po = *uncompressed;
5046 else
5047 {
5048 po = (unsigned char *) backtrace_alloc (state, size: sz, error_callback, data);
5049 if (po == NULL)
5050 return 0;
5051 }
5052
5053 if (!elf_zlib_inflate_and_verify (pin: compressed + 12, sin: compressed_size - 12,
5054 zdebug_table, pout: po, sout: sz))
5055 return 1;
5056
5057 *uncompressed = po;
5058 *uncompressed_size = sz;
5059
5060 return 1;
5061}
5062
5063/* Uncompress the new compressed debug format, the official standard
5064 ELF approach emitted by --compress-debug-sections=zlib-gabi. The
5065 compressed data is in COMPRESSED / COMPRESSED_SIZE, and the
5066 function writes to *UNCOMPRESSED / *UNCOMPRESSED_SIZE.
5067 ZDEBUG_TABLE is work space as for elf_uncompress_zdebug. Returns 0
5068 on error, 1 on successful decompression or if something goes wrong.
5069 In general we try to carry on, by returning 1, even if we can't
5070 decompress. */
5071
5072static int
5073elf_uncompress_chdr (struct backtrace_state *state,
5074 const unsigned char *compressed, size_t compressed_size,
5075 uint16_t *zdebug_table,
5076 backtrace_error_callback error_callback, void *data,
5077 unsigned char **uncompressed, size_t *uncompressed_size)
5078{
5079 const b_elf_chdr *chdr;
5080 char *alc;
5081 size_t alc_len;
5082 unsigned char *po;
5083
5084 *uncompressed = NULL;
5085 *uncompressed_size = 0;
5086
5087 /* The format starts with an ELF compression header. */
5088 if (compressed_size < sizeof (b_elf_chdr))
5089 return 1;
5090
5091 chdr = (const b_elf_chdr *) compressed;
5092
5093 alc = NULL;
5094 alc_len = 0;
5095 if (*uncompressed != NULL && *uncompressed_size >= chdr->ch_size)
5096 po = *uncompressed;
5097 else
5098 {
5099 alc_len = chdr->ch_size;
5100 alc = backtrace_alloc (state, size: alc_len, error_callback, data);
5101 if (alc == NULL)
5102 return 0;
5103 po = (unsigned char *) alc;
5104 }
5105
5106 switch (chdr->ch_type)
5107 {
5108 case ELFCOMPRESS_ZLIB:
5109 if (!elf_zlib_inflate_and_verify (pin: compressed + sizeof (b_elf_chdr),
5110 sin: compressed_size - sizeof (b_elf_chdr),
5111 zdebug_table, pout: po, sout: chdr->ch_size))
5112 goto skip;
5113 break;
5114
5115 case ELFCOMPRESS_ZSTD:
5116 if (!elf_zstd_decompress (pin: compressed + sizeof (b_elf_chdr),
5117 sin: compressed_size - sizeof (b_elf_chdr),
5118 zdebug_table: (unsigned char *)zdebug_table, pout: po,
5119 sout: chdr->ch_size))
5120 goto skip;
5121 break;
5122
5123 default:
5124 /* Unsupported compression algorithm. */
5125 goto skip;
5126 }
5127
5128 *uncompressed = po;
5129 *uncompressed_size = chdr->ch_size;
5130
5131 return 1;
5132
5133 skip:
5134 if (alc != NULL && alc_len > 0)
5135 backtrace_free (state, mem: alc, size: alc_len, error_callback, data);
5136 return 1;
5137}
5138
5139/* This function is a hook for testing the zlib support. It is only
5140 used by tests. */
5141
5142int
5143backtrace_uncompress_zdebug (struct backtrace_state *state,
5144 const unsigned char *compressed,
5145 size_t compressed_size,
5146 backtrace_error_callback error_callback,
5147 void *data, unsigned char **uncompressed,
5148 size_t *uncompressed_size)
5149{
5150 uint16_t *zdebug_table;
5151 int ret;
5152
5153 zdebug_table = ((uint16_t *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
5154 error_callback, data));
5155 if (zdebug_table == NULL)
5156 return 0;
5157 ret = elf_uncompress_zdebug (state, compressed, compressed_size,
5158 zdebug_table, error_callback, data,
5159 uncompressed, uncompressed_size);
5160 backtrace_free (state, mem: zdebug_table, ZDEBUG_TABLE_SIZE,
5161 error_callback, data);
5162 return ret;
5163}
5164
5165/* This function is a hook for testing the zstd support. It is only used by
5166 tests. */
5167
5168int
5169backtrace_uncompress_zstd (struct backtrace_state *state,
5170 const unsigned char *compressed,
5171 size_t compressed_size,
5172 backtrace_error_callback error_callback,
5173 void *data, unsigned char *uncompressed,
5174 size_t uncompressed_size)
5175{
5176 unsigned char *zdebug_table;
5177 int ret;
5178
5179 zdebug_table = ((unsigned char *) backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
5180 error_callback, data));
5181 if (zdebug_table == NULL)
5182 return 0;
5183 ret = elf_zstd_decompress (pin: compressed, sin: compressed_size,
5184 zdebug_table, pout: uncompressed, sout: uncompressed_size);
5185 backtrace_free (state, mem: zdebug_table, ZDEBUG_TABLE_SIZE,
5186 error_callback, data);
5187 return ret;
5188}
5189
5190/* Number of LZMA states. */
5191#define LZMA_STATES (12)
5192
5193/* Number of LZMA position states. The pb value of the property byte
5194 is the number of bits to include in these states, and the maximum
5195 value of pb is 4. */
5196#define LZMA_POS_STATES (16)
5197
5198/* Number of LZMA distance states. These are used match distances
5199 with a short match length: up to 4 bytes. */
5200#define LZMA_DIST_STATES (4)
5201
5202/* Number of LZMA distance slots. LZMA uses six bits to encode larger
5203 match lengths, so 1 << 6 possible probabilities. */
5204#define LZMA_DIST_SLOTS (64)
5205
5206/* LZMA distances 0 to 3 are encoded directly, larger values use a
5207 probability model. */
5208#define LZMA_DIST_MODEL_START (4)
5209
5210/* The LZMA probability model ends at 14. */
5211#define LZMA_DIST_MODEL_END (14)
5212
5213/* LZMA distance slots for distances less than 127. */
5214#define LZMA_FULL_DISTANCES (128)
5215
5216/* LZMA uses four alignment bits. */
5217#define LZMA_ALIGN_SIZE (16)
5218
5219/* LZMA match length is encoded with 4, 5, or 10 bits, some of which
5220 are already known. */
5221#define LZMA_LEN_LOW_SYMBOLS (8)
5222#define LZMA_LEN_MID_SYMBOLS (8)
5223#define LZMA_LEN_HIGH_SYMBOLS (256)
5224
5225/* LZMA literal encoding. */
5226#define LZMA_LITERAL_CODERS_MAX (16)
5227#define LZMA_LITERAL_CODER_SIZE (0x300)
5228
5229/* LZMA is based on a large set of probabilities, each managed
5230 independently. Each probability is an 11 bit number that we store
5231 in a uint16_t. We use a single large array of probabilities. */
5232
5233/* Lengths of entries in the LZMA probabilities array. The names used
5234 here are copied from the Linux kernel implementation. */
5235
5236#define LZMA_PROB_IS_MATCH_LEN (LZMA_STATES * LZMA_POS_STATES)
5237#define LZMA_PROB_IS_REP_LEN LZMA_STATES
5238#define LZMA_PROB_IS_REP0_LEN LZMA_STATES
5239#define LZMA_PROB_IS_REP1_LEN LZMA_STATES
5240#define LZMA_PROB_IS_REP2_LEN LZMA_STATES
5241#define LZMA_PROB_IS_REP0_LONG_LEN (LZMA_STATES * LZMA_POS_STATES)
5242#define LZMA_PROB_DIST_SLOT_LEN (LZMA_DIST_STATES * LZMA_DIST_SLOTS)
5243#define LZMA_PROB_DIST_SPECIAL_LEN (LZMA_FULL_DISTANCES - LZMA_DIST_MODEL_END)
5244#define LZMA_PROB_DIST_ALIGN_LEN LZMA_ALIGN_SIZE
5245#define LZMA_PROB_MATCH_LEN_CHOICE_LEN 1
5246#define LZMA_PROB_MATCH_LEN_CHOICE2_LEN 1
5247#define LZMA_PROB_MATCH_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
5248#define LZMA_PROB_MATCH_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
5249#define LZMA_PROB_MATCH_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
5250#define LZMA_PROB_REP_LEN_CHOICE_LEN 1
5251#define LZMA_PROB_REP_LEN_CHOICE2_LEN 1
5252#define LZMA_PROB_REP_LEN_LOW_LEN (LZMA_POS_STATES * LZMA_LEN_LOW_SYMBOLS)
5253#define LZMA_PROB_REP_LEN_MID_LEN (LZMA_POS_STATES * LZMA_LEN_MID_SYMBOLS)
5254#define LZMA_PROB_REP_LEN_HIGH_LEN LZMA_LEN_HIGH_SYMBOLS
5255#define LZMA_PROB_LITERAL_LEN \
5256 (LZMA_LITERAL_CODERS_MAX * LZMA_LITERAL_CODER_SIZE)
5257
5258/* Offsets into the LZMA probabilities array. This is mechanically
5259 generated from the above lengths. */
5260
5261#define LZMA_PROB_IS_MATCH_OFFSET 0
5262#define LZMA_PROB_IS_REP_OFFSET \
5263 (LZMA_PROB_IS_MATCH_OFFSET + LZMA_PROB_IS_MATCH_LEN)
5264#define LZMA_PROB_IS_REP0_OFFSET \
5265 (LZMA_PROB_IS_REP_OFFSET + LZMA_PROB_IS_REP_LEN)
5266#define LZMA_PROB_IS_REP1_OFFSET \
5267 (LZMA_PROB_IS_REP0_OFFSET + LZMA_PROB_IS_REP0_LEN)
5268#define LZMA_PROB_IS_REP2_OFFSET \
5269 (LZMA_PROB_IS_REP1_OFFSET + LZMA_PROB_IS_REP1_LEN)
5270#define LZMA_PROB_IS_REP0_LONG_OFFSET \
5271 (LZMA_PROB_IS_REP2_OFFSET + LZMA_PROB_IS_REP2_LEN)
5272#define LZMA_PROB_DIST_SLOT_OFFSET \
5273 (LZMA_PROB_IS_REP0_LONG_OFFSET + LZMA_PROB_IS_REP0_LONG_LEN)
5274#define LZMA_PROB_DIST_SPECIAL_OFFSET \
5275 (LZMA_PROB_DIST_SLOT_OFFSET + LZMA_PROB_DIST_SLOT_LEN)
5276#define LZMA_PROB_DIST_ALIGN_OFFSET \
5277 (LZMA_PROB_DIST_SPECIAL_OFFSET + LZMA_PROB_DIST_SPECIAL_LEN)
5278#define LZMA_PROB_MATCH_LEN_CHOICE_OFFSET \
5279 (LZMA_PROB_DIST_ALIGN_OFFSET + LZMA_PROB_DIST_ALIGN_LEN)
5280#define LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET \
5281 (LZMA_PROB_MATCH_LEN_CHOICE_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE_LEN)
5282#define LZMA_PROB_MATCH_LEN_LOW_OFFSET \
5283 (LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET + LZMA_PROB_MATCH_LEN_CHOICE2_LEN)
5284#define LZMA_PROB_MATCH_LEN_MID_OFFSET \
5285 (LZMA_PROB_MATCH_LEN_LOW_OFFSET + LZMA_PROB_MATCH_LEN_LOW_LEN)
5286#define LZMA_PROB_MATCH_LEN_HIGH_OFFSET \
5287 (LZMA_PROB_MATCH_LEN_MID_OFFSET + LZMA_PROB_MATCH_LEN_MID_LEN)
5288#define LZMA_PROB_REP_LEN_CHOICE_OFFSET \
5289 (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + LZMA_PROB_MATCH_LEN_HIGH_LEN)
5290#define LZMA_PROB_REP_LEN_CHOICE2_OFFSET \
5291 (LZMA_PROB_REP_LEN_CHOICE_OFFSET + LZMA_PROB_REP_LEN_CHOICE_LEN)
5292#define LZMA_PROB_REP_LEN_LOW_OFFSET \
5293 (LZMA_PROB_REP_LEN_CHOICE2_OFFSET + LZMA_PROB_REP_LEN_CHOICE2_LEN)
5294#define LZMA_PROB_REP_LEN_MID_OFFSET \
5295 (LZMA_PROB_REP_LEN_LOW_OFFSET + LZMA_PROB_REP_LEN_LOW_LEN)
5296#define LZMA_PROB_REP_LEN_HIGH_OFFSET \
5297 (LZMA_PROB_REP_LEN_MID_OFFSET + LZMA_PROB_REP_LEN_MID_LEN)
5298#define LZMA_PROB_LITERAL_OFFSET \
5299 (LZMA_PROB_REP_LEN_HIGH_OFFSET + LZMA_PROB_REP_LEN_HIGH_LEN)
5300
5301#define LZMA_PROB_TOTAL_COUNT \
5302 (LZMA_PROB_LITERAL_OFFSET + LZMA_PROB_LITERAL_LEN)
5303
5304/* Check that the number of LZMA probabilities is the same as the
5305 Linux kernel implementation. */
5306
5307#if LZMA_PROB_TOTAL_COUNT != 1846 + (1 << 4) * 0x300
5308 #error Wrong number of LZMA probabilities
5309#endif
5310
5311/* Expressions for the offset in the LZMA probabilities array of a
5312 specific probability. */
5313
5314#define LZMA_IS_MATCH(state, pos) \
5315 (LZMA_PROB_IS_MATCH_OFFSET + (state) * LZMA_POS_STATES + (pos))
5316#define LZMA_IS_REP(state) \
5317 (LZMA_PROB_IS_REP_OFFSET + (state))
5318#define LZMA_IS_REP0(state) \
5319 (LZMA_PROB_IS_REP0_OFFSET + (state))
5320#define LZMA_IS_REP1(state) \
5321 (LZMA_PROB_IS_REP1_OFFSET + (state))
5322#define LZMA_IS_REP2(state) \
5323 (LZMA_PROB_IS_REP2_OFFSET + (state))
5324#define LZMA_IS_REP0_LONG(state, pos) \
5325 (LZMA_PROB_IS_REP0_LONG_OFFSET + (state) * LZMA_POS_STATES + (pos))
5326#define LZMA_DIST_SLOT(dist, slot) \
5327 (LZMA_PROB_DIST_SLOT_OFFSET + (dist) * LZMA_DIST_SLOTS + (slot))
5328#define LZMA_DIST_SPECIAL(dist) \
5329 (LZMA_PROB_DIST_SPECIAL_OFFSET + (dist))
5330#define LZMA_DIST_ALIGN(dist) \
5331 (LZMA_PROB_DIST_ALIGN_OFFSET + (dist))
5332#define LZMA_MATCH_LEN_CHOICE \
5333 LZMA_PROB_MATCH_LEN_CHOICE_OFFSET
5334#define LZMA_MATCH_LEN_CHOICE2 \
5335 LZMA_PROB_MATCH_LEN_CHOICE2_OFFSET
5336#define LZMA_MATCH_LEN_LOW(pos, sym) \
5337 (LZMA_PROB_MATCH_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
5338#define LZMA_MATCH_LEN_MID(pos, sym) \
5339 (LZMA_PROB_MATCH_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
5340#define LZMA_MATCH_LEN_HIGH(sym) \
5341 (LZMA_PROB_MATCH_LEN_HIGH_OFFSET + (sym))
5342#define LZMA_REP_LEN_CHOICE \
5343 LZMA_PROB_REP_LEN_CHOICE_OFFSET
5344#define LZMA_REP_LEN_CHOICE2 \
5345 LZMA_PROB_REP_LEN_CHOICE2_OFFSET
5346#define LZMA_REP_LEN_LOW(pos, sym) \
5347 (LZMA_PROB_REP_LEN_LOW_OFFSET + (pos) * LZMA_LEN_LOW_SYMBOLS + (sym))
5348#define LZMA_REP_LEN_MID(pos, sym) \
5349 (LZMA_PROB_REP_LEN_MID_OFFSET + (pos) * LZMA_LEN_MID_SYMBOLS + (sym))
5350#define LZMA_REP_LEN_HIGH(sym) \
5351 (LZMA_PROB_REP_LEN_HIGH_OFFSET + (sym))
5352#define LZMA_LITERAL(code, size) \
5353 (LZMA_PROB_LITERAL_OFFSET + (code) * LZMA_LITERAL_CODER_SIZE + (size))
5354
5355/* Read an LZMA varint from BUF, reading and updating *POFFSET,
5356 setting *VAL. Returns 0 on error, 1 on success. */
5357
5358static int
5359elf_lzma_varint (const unsigned char *compressed, size_t compressed_size,
5360 size_t *poffset, uint64_t *val)
5361{
5362 size_t off;
5363 int i;
5364 uint64_t v;
5365 unsigned char b;
5366
5367 off = *poffset;
5368 i = 0;
5369 v = 0;
5370 while (1)
5371 {
5372 if (unlikely (off >= compressed_size))
5373 {
5374 elf_uncompress_failed ();
5375 return 0;
5376 }
5377 b = compressed[off];
5378 v |= (b & 0x7f) << (i * 7);
5379 ++off;
5380 if ((b & 0x80) == 0)
5381 {
5382 *poffset = off;
5383 *val = v;
5384 return 1;
5385 }
5386 ++i;
5387 if (unlikely (i >= 9))
5388 {
5389 elf_uncompress_failed ();
5390 return 0;
5391 }
5392 }
5393}
5394
5395/* Normalize the LZMA range decoder, pulling in an extra input byte if
5396 needed. */
5397
5398static void
5399elf_lzma_range_normalize (const unsigned char *compressed,
5400 size_t compressed_size, size_t *poffset,
5401 uint32_t *prange, uint32_t *pcode)
5402{
5403 if (*prange < (1U << 24))
5404 {
5405 if (unlikely (*poffset >= compressed_size))
5406 {
5407 /* We assume this will be caught elsewhere. */
5408 elf_uncompress_failed ();
5409 return;
5410 }
5411 *prange <<= 8;
5412 *pcode <<= 8;
5413 *pcode += compressed[*poffset];
5414 ++*poffset;
5415 }
5416}
5417
5418/* Read and return a single bit from the LZMA stream, reading and
5419 updating *PROB. Each bit comes from the range coder. */
5420
5421static int
5422elf_lzma_bit (const unsigned char *compressed, size_t compressed_size,
5423 uint16_t *prob, size_t *poffset, uint32_t *prange,
5424 uint32_t *pcode)
5425{
5426 uint32_t bound;
5427
5428 elf_lzma_range_normalize (compressed, compressed_size, poffset,
5429 prange, pcode);
5430 bound = (*prange >> 11) * (uint32_t) *prob;
5431 if (*pcode < bound)
5432 {
5433 *prange = bound;
5434 *prob += ((1U << 11) - *prob) >> 5;
5435 return 0;
5436 }
5437 else
5438 {
5439 *prange -= bound;
5440 *pcode -= bound;
5441 *prob -= *prob >> 5;
5442 return 1;
5443 }
5444}
5445
5446/* Read an integer of size BITS from the LZMA stream, most significant
5447 bit first. The bits are predicted using PROBS. */
5448
5449static uint32_t
5450elf_lzma_integer (const unsigned char *compressed, size_t compressed_size,
5451 uint16_t *probs, uint32_t bits, size_t *poffset,
5452 uint32_t *prange, uint32_t *pcode)
5453{
5454 uint32_t sym;
5455 uint32_t i;
5456
5457 sym = 1;
5458 for (i = 0; i < bits; i++)
5459 {
5460 int bit;
5461
5462 bit = elf_lzma_bit (compressed, compressed_size, prob: probs + sym, poffset,
5463 prange, pcode);
5464 sym <<= 1;
5465 sym += bit;
5466 }
5467 return sym - (1 << bits);
5468}
5469
5470/* Read an integer of size BITS from the LZMA stream, least
5471 significant bit first. The bits are predicted using PROBS. */
5472
5473static uint32_t
5474elf_lzma_reverse_integer (const unsigned char *compressed,
5475 size_t compressed_size, uint16_t *probs,
5476 uint32_t bits, size_t *poffset, uint32_t *prange,
5477 uint32_t *pcode)
5478{
5479 uint32_t sym;
5480 uint32_t val;
5481 uint32_t i;
5482
5483 sym = 1;
5484 val = 0;
5485 for (i = 0; i < bits; i++)
5486 {
5487 int bit;
5488
5489 bit = elf_lzma_bit (compressed, compressed_size, prob: probs + sym, poffset,
5490 prange, pcode);
5491 sym <<= 1;
5492 sym += bit;
5493 val += bit << i;
5494 }
5495 return val;
5496}
5497
5498/* Read a length from the LZMA stream. IS_REP picks either LZMA_MATCH
5499 or LZMA_REP probabilities. */
5500
5501static uint32_t
5502elf_lzma_len (const unsigned char *compressed, size_t compressed_size,
5503 uint16_t *probs, int is_rep, unsigned int pos_state,
5504 size_t *poffset, uint32_t *prange, uint32_t *pcode)
5505{
5506 uint16_t *probs_choice;
5507 uint16_t *probs_sym;
5508 uint32_t bits;
5509 uint32_t len;
5510
5511 probs_choice = probs + (is_rep
5512 ? LZMA_REP_LEN_CHOICE
5513 : LZMA_MATCH_LEN_CHOICE);
5514 if (elf_lzma_bit (compressed, compressed_size, prob: probs_choice, poffset,
5515 prange, pcode))
5516 {
5517 probs_choice = probs + (is_rep
5518 ? LZMA_REP_LEN_CHOICE2
5519 : LZMA_MATCH_LEN_CHOICE2);
5520 if (elf_lzma_bit (compressed, compressed_size, prob: probs_choice,
5521 poffset, prange, pcode))
5522 {
5523 probs_sym = probs + (is_rep
5524 ? LZMA_REP_LEN_HIGH (0)
5525 : LZMA_MATCH_LEN_HIGH (0));
5526 bits = 8;
5527 len = 2 + 8 + 8;
5528 }
5529 else
5530 {
5531 probs_sym = probs + (is_rep
5532 ? LZMA_REP_LEN_MID (pos_state, 0)
5533 : LZMA_MATCH_LEN_MID (pos_state, 0));
5534 bits = 3;
5535 len = 2 + 8;
5536 }
5537 }
5538 else
5539 {
5540 probs_sym = probs + (is_rep
5541 ? LZMA_REP_LEN_LOW (pos_state, 0)
5542 : LZMA_MATCH_LEN_LOW (pos_state, 0));
5543 bits = 3;
5544 len = 2;
5545 }
5546
5547 len += elf_lzma_integer (compressed, compressed_size, probs: probs_sym, bits,
5548 poffset, prange, pcode);
5549 return len;
5550}
5551
5552/* Uncompress one LZMA block from a minidebug file. The compressed
5553 data is at COMPRESSED + *POFFSET. Update *POFFSET. Store the data
5554 into the memory at UNCOMPRESSED, size UNCOMPRESSED_SIZE. CHECK is
5555 the stream flag from the xz header. Return 1 on successful
5556 decompression. */
5557
5558static int
5559elf_uncompress_lzma_block (const unsigned char *compressed,
5560 size_t compressed_size, unsigned char check,
5561 uint16_t *probs, unsigned char *uncompressed,
5562 size_t uncompressed_size, size_t *poffset)
5563{
5564 size_t off;
5565 size_t block_header_offset;
5566 size_t block_header_size;
5567 unsigned char block_flags;
5568 uint64_t header_compressed_size;
5569 uint64_t header_uncompressed_size;
5570 unsigned char lzma2_properties;
5571 uint32_t computed_crc;
5572 uint32_t stream_crc;
5573 size_t uncompressed_offset;
5574 size_t dict_start_offset;
5575 unsigned int lc;
5576 unsigned int lp;
5577 unsigned int pb;
5578 uint32_t range;
5579 uint32_t code;
5580 uint32_t lstate;
5581 uint32_t dist[4];
5582
5583 off = *poffset;
5584 block_header_offset = off;
5585
5586 /* Block header size is a single byte. */
5587 if (unlikely (off >= compressed_size))
5588 {
5589 elf_uncompress_failed ();
5590 return 0;
5591 }
5592 block_header_size = (compressed[off] + 1) * 4;
5593 if (unlikely (off + block_header_size > compressed_size))
5594 {
5595 elf_uncompress_failed ();
5596 return 0;
5597 }
5598
5599 /* Block flags. */
5600 block_flags = compressed[off + 1];
5601 if (unlikely ((block_flags & 0x3c) != 0))
5602 {
5603 elf_uncompress_failed ();
5604 return 0;
5605 }
5606
5607 off += 2;
5608
5609 /* Optional compressed size. */
5610 header_compressed_size = 0;
5611 if ((block_flags & 0x40) != 0)
5612 {
5613 *poffset = off;
5614 if (!elf_lzma_varint (compressed, compressed_size, poffset,
5615 val: &header_compressed_size))
5616 return 0;
5617 off = *poffset;
5618 }
5619
5620 /* Optional uncompressed size. */
5621 header_uncompressed_size = 0;
5622 if ((block_flags & 0x80) != 0)
5623 {
5624 *poffset = off;
5625 if (!elf_lzma_varint (compressed, compressed_size, poffset,
5626 val: &header_uncompressed_size))
5627 return 0;
5628 off = *poffset;
5629 }
5630
5631 /* The recipe for creating a minidebug file is to run the xz program
5632 with no arguments, so we expect exactly one filter: lzma2. */
5633
5634 if (unlikely ((block_flags & 0x3) != 0))
5635 {
5636 elf_uncompress_failed ();
5637 return 0;
5638 }
5639
5640 if (unlikely (off + 2 >= block_header_offset + block_header_size))
5641 {
5642 elf_uncompress_failed ();
5643 return 0;
5644 }
5645
5646 /* The filter ID for LZMA2 is 0x21. */
5647 if (unlikely (compressed[off] != 0x21))
5648 {
5649 elf_uncompress_failed ();
5650 return 0;
5651 }
5652 ++off;
5653
5654 /* The size of the filter properties for LZMA2 is 1. */
5655 if (unlikely (compressed[off] != 1))
5656 {
5657 elf_uncompress_failed ();
5658 return 0;
5659 }
5660 ++off;
5661
5662 lzma2_properties = compressed[off];
5663 ++off;
5664
5665 if (unlikely (lzma2_properties > 40))
5666 {
5667 elf_uncompress_failed ();
5668 return 0;
5669 }
5670
5671 /* The properties describe the dictionary size, but we don't care
5672 what that is. */
5673
5674 /* Block header padding. */
5675 if (unlikely (off + 4 > compressed_size))
5676 {
5677 elf_uncompress_failed ();
5678 return 0;
5679 }
5680
5681 off = (off + 3) &~ (size_t) 3;
5682
5683 if (unlikely (off + 4 > compressed_size))
5684 {
5685 elf_uncompress_failed ();
5686 return 0;
5687 }
5688
5689 /* Block header CRC. */
5690 computed_crc = elf_crc32 (crc: 0, buf: compressed + block_header_offset,
5691 len: block_header_size - 4);
5692 stream_crc = ((uint32_t)compressed[off]
5693 | ((uint32_t)compressed[off + 1] << 8)
5694 | ((uint32_t)compressed[off + 2] << 16)
5695 | ((uint32_t)compressed[off + 3] << 24));
5696 if (unlikely (computed_crc != stream_crc))
5697 {
5698 elf_uncompress_failed ();
5699 return 0;
5700 }
5701 off += 4;
5702
5703 /* Read a sequence of LZMA2 packets. */
5704
5705 uncompressed_offset = 0;
5706 dict_start_offset = 0;
5707 lc = 0;
5708 lp = 0;
5709 pb = 0;
5710 lstate = 0;
5711 while (off < compressed_size)
5712 {
5713 unsigned char control;
5714
5715 range = 0xffffffff;
5716 code = 0;
5717
5718 control = compressed[off];
5719 ++off;
5720 if (unlikely (control == 0))
5721 {
5722 /* End of packets. */
5723 break;
5724 }
5725
5726 if (control == 1 || control >= 0xe0)
5727 {
5728 /* Reset dictionary to empty. */
5729 dict_start_offset = uncompressed_offset;
5730 }
5731
5732 if (control < 0x80)
5733 {
5734 size_t chunk_size;
5735
5736 /* The only valid values here are 1 or 2. A 1 means to
5737 reset the dictionary (done above). Then we see an
5738 uncompressed chunk. */
5739
5740 if (unlikely (control > 2))
5741 {
5742 elf_uncompress_failed ();
5743 return 0;
5744 }
5745
5746 /* An uncompressed chunk is a two byte size followed by
5747 data. */
5748
5749 if (unlikely (off + 2 > compressed_size))
5750 {
5751 elf_uncompress_failed ();
5752 return 0;
5753 }
5754
5755 chunk_size = compressed[off] << 8;
5756 chunk_size += compressed[off + 1];
5757 ++chunk_size;
5758
5759 off += 2;
5760
5761 if (unlikely (off + chunk_size > compressed_size))
5762 {
5763 elf_uncompress_failed ();
5764 return 0;
5765 }
5766 if (unlikely (uncompressed_offset + chunk_size > uncompressed_size))
5767 {
5768 elf_uncompress_failed ();
5769 return 0;
5770 }
5771
5772 memcpy (dest: uncompressed + uncompressed_offset, src: compressed + off,
5773 n: chunk_size);
5774 uncompressed_offset += chunk_size;
5775 off += chunk_size;
5776 }
5777 else
5778 {
5779 size_t uncompressed_chunk_start;
5780 size_t uncompressed_chunk_size;
5781 size_t compressed_chunk_size;
5782 size_t limit;
5783
5784 /* An LZMA chunk. This starts with an uncompressed size and
5785 a compressed size. */
5786
5787 if (unlikely (off + 4 >= compressed_size))
5788 {
5789 elf_uncompress_failed ();
5790 return 0;
5791 }
5792
5793 uncompressed_chunk_start = uncompressed_offset;
5794
5795 uncompressed_chunk_size = (control & 0x1f) << 16;
5796 uncompressed_chunk_size += compressed[off] << 8;
5797 uncompressed_chunk_size += compressed[off + 1];
5798 ++uncompressed_chunk_size;
5799
5800 compressed_chunk_size = compressed[off + 2] << 8;
5801 compressed_chunk_size += compressed[off + 3];
5802 ++compressed_chunk_size;
5803
5804 off += 4;
5805
5806 /* Bit 7 (0x80) is set.
5807 Bits 6 and 5 (0x40 and 0x20) are as follows:
5808 0: don't reset anything
5809 1: reset state
5810 2: reset state, read properties
5811 3: reset state, read properties, reset dictionary (done above) */
5812
5813 if (control >= 0xc0)
5814 {
5815 unsigned char props;
5816
5817 /* Bit 6 is set, read properties. */
5818
5819 if (unlikely (off >= compressed_size))
5820 {
5821 elf_uncompress_failed ();
5822 return 0;
5823 }
5824 props = compressed[off];
5825 ++off;
5826 if (unlikely (props > (4 * 5 + 4) * 9 + 8))
5827 {
5828 elf_uncompress_failed ();
5829 return 0;
5830 }
5831 pb = 0;
5832 while (props >= 9 * 5)
5833 {
5834 props -= 9 * 5;
5835 ++pb;
5836 }
5837 lp = 0;
5838 while (props > 9)
5839 {
5840 props -= 9;
5841 ++lp;
5842 }
5843 lc = props;
5844 if (unlikely (lc + lp > 4))
5845 {
5846 elf_uncompress_failed ();
5847 return 0;
5848 }
5849 }
5850
5851 if (control >= 0xa0)
5852 {
5853 size_t i;
5854
5855 /* Bit 5 or 6 is set, reset LZMA state. */
5856
5857 lstate = 0;
5858 memset (s: &dist, c: 0, n: sizeof dist);
5859 for (i = 0; i < LZMA_PROB_TOTAL_COUNT; i++)
5860 probs[i] = 1 << 10;
5861 range = 0xffffffff;
5862 code = 0;
5863 }
5864
5865 /* Read the range code. */
5866
5867 if (unlikely (off + 5 > compressed_size))
5868 {
5869 elf_uncompress_failed ();
5870 return 0;
5871 }
5872
5873 /* The byte at compressed[off] is ignored for some
5874 reason. */
5875
5876 code = ((compressed[off + 1] << 24)
5877 + (compressed[off + 2] << 16)
5878 + (compressed[off + 3] << 8)
5879 + compressed[off + 4]);
5880 off += 5;
5881
5882 /* This is the main LZMA decode loop. */
5883
5884 limit = off + compressed_chunk_size;
5885 *poffset = off;
5886 while (*poffset < limit)
5887 {
5888 unsigned int pos_state;
5889
5890 if (unlikely (uncompressed_offset
5891 == (uncompressed_chunk_start
5892 + uncompressed_chunk_size)))
5893 {
5894 /* We've decompressed all the expected bytes. */
5895 break;
5896 }
5897
5898 pos_state = ((uncompressed_offset - dict_start_offset)
5899 & ((1 << pb) - 1));
5900
5901 if (elf_lzma_bit (compressed, compressed_size,
5902 prob: probs + LZMA_IS_MATCH (lstate, pos_state),
5903 poffset, prange: &range, pcode: &code))
5904 {
5905 uint32_t len;
5906
5907 if (elf_lzma_bit (compressed, compressed_size,
5908 prob: probs + LZMA_IS_REP (lstate),
5909 poffset, prange: &range, pcode: &code))
5910 {
5911 int short_rep;
5912 uint32_t next_dist;
5913
5914 /* Repeated match. */
5915
5916 short_rep = 0;
5917 if (elf_lzma_bit (compressed, compressed_size,
5918 prob: probs + LZMA_IS_REP0 (lstate),
5919 poffset, prange: &range, pcode: &code))
5920 {
5921 if (elf_lzma_bit (compressed, compressed_size,
5922 prob: probs + LZMA_IS_REP1 (lstate),
5923 poffset, prange: &range, pcode: &code))
5924 {
5925 if (elf_lzma_bit (compressed, compressed_size,
5926 prob: probs + LZMA_IS_REP2 (lstate),
5927 poffset, prange: &range, pcode: &code))
5928 {
5929 next_dist = dist[3];
5930 dist[3] = dist[2];
5931 }
5932 else
5933 {
5934 next_dist = dist[2];
5935 }
5936 dist[2] = dist[1];
5937 }
5938 else
5939 {
5940 next_dist = dist[1];
5941 }
5942
5943 dist[1] = dist[0];
5944 dist[0] = next_dist;
5945 }
5946 else
5947 {
5948 if (!elf_lzma_bit (compressed, compressed_size,
5949 prob: (probs
5950 + LZMA_IS_REP0_LONG (lstate,
5951 pos_state)),
5952 poffset, prange: &range, pcode: &code))
5953 short_rep = 1;
5954 }
5955
5956 if (lstate < 7)
5957 lstate = short_rep ? 9 : 8;
5958 else
5959 lstate = 11;
5960
5961 if (short_rep)
5962 len = 1;
5963 else
5964 len = elf_lzma_len (compressed, compressed_size,
5965 probs, is_rep: 1, pos_state, poffset,
5966 prange: &range, pcode: &code);
5967 }
5968 else
5969 {
5970 uint32_t dist_state;
5971 uint32_t dist_slot;
5972 uint16_t *probs_dist;
5973
5974 /* Match. */
5975
5976 if (lstate < 7)
5977 lstate = 7;
5978 else
5979 lstate = 10;
5980 dist[3] = dist[2];
5981 dist[2] = dist[1];
5982 dist[1] = dist[0];
5983 len = elf_lzma_len (compressed, compressed_size,
5984 probs, is_rep: 0, pos_state, poffset,
5985 prange: &range, pcode: &code);
5986
5987 if (len < 4 + 2)
5988 dist_state = len - 2;
5989 else
5990 dist_state = 3;
5991 probs_dist = probs + LZMA_DIST_SLOT (dist_state, 0);
5992 dist_slot = elf_lzma_integer (compressed,
5993 compressed_size,
5994 probs: probs_dist, bits: 6,
5995 poffset, prange: &range,
5996 pcode: &code);
5997 if (dist_slot < LZMA_DIST_MODEL_START)
5998 dist[0] = dist_slot;
5999 else
6000 {
6001 uint32_t limit;
6002
6003 limit = (dist_slot >> 1) - 1;
6004 dist[0] = 2 + (dist_slot & 1);
6005 if (dist_slot < LZMA_DIST_MODEL_END)
6006 {
6007 dist[0] <<= limit;
6008 probs_dist = (probs
6009 + LZMA_DIST_SPECIAL(dist[0]
6010 - dist_slot
6011 - 1));
6012 dist[0] +=
6013 elf_lzma_reverse_integer (compressed,
6014 compressed_size,
6015 probs: probs_dist,
6016 bits: limit, poffset,
6017 prange: &range, pcode: &code);
6018 }
6019 else
6020 {
6021 uint32_t dist0;
6022 uint32_t i;
6023
6024 dist0 = dist[0];
6025 for (i = 0; i < limit - 4; i++)
6026 {
6027 uint32_t mask;
6028
6029 elf_lzma_range_normalize (compressed,
6030 compressed_size,
6031 poffset,
6032 prange: &range, pcode: &code);
6033 range >>= 1;
6034 code -= range;
6035 mask = -(code >> 31);
6036 code += range & mask;
6037 dist0 <<= 1;
6038 dist0 += mask + 1;
6039 }
6040 dist0 <<= 4;
6041 probs_dist = probs + LZMA_DIST_ALIGN (0);
6042 dist0 +=
6043 elf_lzma_reverse_integer (compressed,
6044 compressed_size,
6045 probs: probs_dist, bits: 4,
6046 poffset,
6047 prange: &range, pcode: &code);
6048 dist[0] = dist0;
6049 }
6050 }
6051 }
6052
6053 if (unlikely (uncompressed_offset
6054 - dict_start_offset < dist[0] + 1))
6055 {
6056 elf_uncompress_failed ();
6057 return 0;
6058 }
6059 if (unlikely (uncompressed_offset + len > uncompressed_size))
6060 {
6061 elf_uncompress_failed ();
6062 return 0;
6063 }
6064
6065 if (dist[0] == 0)
6066 {
6067 /* A common case, meaning repeat the last
6068 character LEN times. */
6069 memset (s: uncompressed + uncompressed_offset,
6070 c: uncompressed[uncompressed_offset - 1],
6071 n: len);
6072 uncompressed_offset += len;
6073 }
6074 else if (dist[0] + 1 >= len)
6075 {
6076 memcpy (dest: uncompressed + uncompressed_offset,
6077 src: uncompressed + uncompressed_offset - dist[0] - 1,
6078 n: len);
6079 uncompressed_offset += len;
6080 }
6081 else
6082 {
6083 while (len > 0)
6084 {
6085 uint32_t copy;
6086
6087 copy = len < dist[0] + 1 ? len : dist[0] + 1;
6088 memcpy (dest: uncompressed + uncompressed_offset,
6089 src: (uncompressed + uncompressed_offset
6090 - dist[0] - 1),
6091 n: copy);
6092 len -= copy;
6093 uncompressed_offset += copy;
6094 }
6095 }
6096 }
6097 else
6098 {
6099 unsigned char prev;
6100 unsigned char low;
6101 size_t high;
6102 uint16_t *lit_probs;
6103 unsigned int sym;
6104
6105 /* Literal value. */
6106
6107 if (uncompressed_offset > 0)
6108 prev = uncompressed[uncompressed_offset - 1];
6109 else
6110 prev = 0;
6111 low = prev >> (8 - lc);
6112 high = (((uncompressed_offset - dict_start_offset)
6113 & ((1 << lp) - 1))
6114 << lc);
6115 lit_probs = probs + LZMA_LITERAL (low + high, 0);
6116 if (lstate < 7)
6117 sym = elf_lzma_integer (compressed, compressed_size,
6118 probs: lit_probs, bits: 8, poffset, prange: &range,
6119 pcode: &code);
6120 else
6121 {
6122 unsigned int match;
6123 unsigned int bit;
6124 unsigned int match_bit;
6125 unsigned int idx;
6126
6127 sym = 1;
6128 if (uncompressed_offset >= dist[0] + 1)
6129 match = uncompressed[uncompressed_offset - dist[0] - 1];
6130 else
6131 match = 0;
6132 match <<= 1;
6133 bit = 0x100;
6134 do
6135 {
6136 match_bit = match & bit;
6137 match <<= 1;
6138 idx = bit + match_bit + sym;
6139 sym <<= 1;
6140 if (elf_lzma_bit (compressed, compressed_size,
6141 prob: lit_probs + idx, poffset,
6142 prange: &range, pcode: &code))
6143 {
6144 ++sym;
6145 bit &= match_bit;
6146 }
6147 else
6148 {
6149 bit &= ~ match_bit;
6150 }
6151 }
6152 while (sym < 0x100);
6153 }
6154
6155 if (unlikely (uncompressed_offset >= uncompressed_size))
6156 {
6157 elf_uncompress_failed ();
6158 return 0;
6159 }
6160
6161 uncompressed[uncompressed_offset] = (unsigned char) sym;
6162 ++uncompressed_offset;
6163 if (lstate <= 3)
6164 lstate = 0;
6165 else if (lstate <= 9)
6166 lstate -= 3;
6167 else
6168 lstate -= 6;
6169 }
6170 }
6171
6172 elf_lzma_range_normalize (compressed, compressed_size, poffset,
6173 prange: &range, pcode: &code);
6174
6175 off = *poffset;
6176 }
6177 }
6178
6179 /* We have reached the end of the block. Pad to four byte
6180 boundary. */
6181 off = (off + 3) &~ (size_t) 3;
6182 if (unlikely (off > compressed_size))
6183 {
6184 elf_uncompress_failed ();
6185 return 0;
6186 }
6187
6188 switch (check)
6189 {
6190 case 0:
6191 /* No check. */
6192 break;
6193
6194 case 1:
6195 /* CRC32 */
6196 if (unlikely (off + 4 > compressed_size))
6197 {
6198 elf_uncompress_failed ();
6199 return 0;
6200 }
6201 computed_crc = elf_crc32 (crc: 0, buf: uncompressed, len: uncompressed_offset);
6202 stream_crc = (compressed[off]
6203 | (compressed[off + 1] << 8)
6204 | (compressed[off + 2] << 16)
6205 | (compressed[off + 3] << 24));
6206 if (computed_crc != stream_crc)
6207 {
6208 elf_uncompress_failed ();
6209 return 0;
6210 }
6211 off += 4;
6212 break;
6213
6214 case 4:
6215 /* CRC64. We don't bother computing a CRC64 checksum. */
6216 if (unlikely (off + 8 > compressed_size))
6217 {
6218 elf_uncompress_failed ();
6219 return 0;
6220 }
6221 off += 8;
6222 break;
6223
6224 case 10:
6225 /* SHA. We don't bother computing a SHA checksum. */
6226 if (unlikely (off + 32 > compressed_size))
6227 {
6228 elf_uncompress_failed ();
6229 return 0;
6230 }
6231 off += 32;
6232 break;
6233
6234 default:
6235 elf_uncompress_failed ();
6236 return 0;
6237 }
6238
6239 *poffset = off;
6240
6241 return 1;
6242}
6243
6244/* Uncompress LZMA data found in a minidebug file. The minidebug
6245 format is described at
6246 https://sourceware.org/gdb/current/onlinedocs/gdb/MiniDebugInfo.html.
6247 Returns 0 on error, 1 on successful decompression. For this
6248 function we return 0 on failure to decompress, as the calling code
6249 will carry on in that case. */
6250
6251static int
6252elf_uncompress_lzma (struct backtrace_state *state,
6253 const unsigned char *compressed, size_t compressed_size,
6254 backtrace_error_callback error_callback, void *data,
6255 unsigned char **uncompressed, size_t *uncompressed_size)
6256{
6257 size_t header_size;
6258 size_t footer_size;
6259 unsigned char check;
6260 uint32_t computed_crc;
6261 uint32_t stream_crc;
6262 size_t offset;
6263 size_t index_size;
6264 size_t footer_offset;
6265 size_t index_offset;
6266 uint64_t index_compressed_size;
6267 uint64_t index_uncompressed_size;
6268 unsigned char *mem;
6269 uint16_t *probs;
6270 size_t compressed_block_size;
6271
6272 /* The format starts with a stream header and ends with a stream
6273 footer. */
6274 header_size = 12;
6275 footer_size = 12;
6276 if (unlikely (compressed_size < header_size + footer_size))
6277 {
6278 elf_uncompress_failed ();
6279 return 0;
6280 }
6281
6282 /* The stream header starts with a magic string. */
6283 if (unlikely (memcmp (compressed, "\375" "7zXZ\0", 6) != 0))
6284 {
6285 elf_uncompress_failed ();
6286 return 0;
6287 }
6288
6289 /* Next come stream flags. The first byte is zero, the second byte
6290 is the check. */
6291 if (unlikely (compressed[6] != 0))
6292 {
6293 elf_uncompress_failed ();
6294 return 0;
6295 }
6296 check = compressed[7];
6297 if (unlikely ((check & 0xf8) != 0))
6298 {
6299 elf_uncompress_failed ();
6300 return 0;
6301 }
6302
6303 /* Next comes a CRC of the stream flags. */
6304 computed_crc = elf_crc32 (crc: 0, buf: compressed + 6, len: 2);
6305 stream_crc = ((uint32_t)compressed[8]
6306 | ((uint32_t)compressed[9] << 8)
6307 | ((uint32_t)compressed[10] << 16)
6308 | ((uint32_t)compressed[11] << 24));
6309 if (unlikely (computed_crc != stream_crc))
6310 {
6311 elf_uncompress_failed ();
6312 return 0;
6313 }
6314
6315 /* Now that we've parsed the header, parse the footer, so that we
6316 can get the uncompressed size. */
6317
6318 /* The footer ends with two magic bytes. */
6319
6320 offset = compressed_size;
6321 if (unlikely (memcmp (compressed + offset - 2, "YZ", 2) != 0))
6322 {
6323 elf_uncompress_failed ();
6324 return 0;
6325 }
6326 offset -= 2;
6327
6328 /* Before that are the stream flags, which should be the same as the
6329 flags in the header. */
6330 if (unlikely (compressed[offset - 2] != 0
6331 || compressed[offset - 1] != check))
6332 {
6333 elf_uncompress_failed ();
6334 return 0;
6335 }
6336 offset -= 2;
6337
6338 /* Before that is the size of the index field, which precedes the
6339 footer. */
6340 index_size = (compressed[offset - 4]
6341 | (compressed[offset - 3] << 8)
6342 | (compressed[offset - 2] << 16)
6343 | (compressed[offset - 1] << 24));
6344 index_size = (index_size + 1) * 4;
6345 offset -= 4;
6346
6347 /* Before that is a footer CRC. */
6348 computed_crc = elf_crc32 (crc: 0, buf: compressed + offset, len: 6);
6349 stream_crc = ((uint32_t)compressed[offset - 4]
6350 | ((uint32_t)compressed[offset - 3] << 8)
6351 | ((uint32_t)compressed[offset - 2] << 16)
6352 | ((uint32_t)compressed[offset - 1] << 24));
6353 if (unlikely (computed_crc != stream_crc))
6354 {
6355 elf_uncompress_failed ();
6356 return 0;
6357 }
6358 offset -= 4;
6359
6360 /* The index comes just before the footer. */
6361 if (unlikely (offset < index_size + header_size))
6362 {
6363 elf_uncompress_failed ();
6364 return 0;
6365 }
6366
6367 footer_offset = offset;
6368 offset -= index_size;
6369 index_offset = offset;
6370
6371 /* The index starts with a zero byte. */
6372 if (unlikely (compressed[offset] != 0))
6373 {
6374 elf_uncompress_failed ();
6375 return 0;
6376 }
6377 ++offset;
6378
6379 /* Next is the number of blocks. We expect zero blocks for an empty
6380 stream, and otherwise a single block. */
6381 if (unlikely (compressed[offset] == 0))
6382 {
6383 *uncompressed = NULL;
6384 *uncompressed_size = 0;
6385 return 1;
6386 }
6387 if (unlikely (compressed[offset] != 1))
6388 {
6389 elf_uncompress_failed ();
6390 return 0;
6391 }
6392 ++offset;
6393
6394 /* Next is the compressed size and the uncompressed size. */
6395 if (!elf_lzma_varint (compressed, compressed_size, poffset: &offset,
6396 val: &index_compressed_size))
6397 return 0;
6398 if (!elf_lzma_varint (compressed, compressed_size, poffset: &offset,
6399 val: &index_uncompressed_size))
6400 return 0;
6401
6402 /* Pad to a four byte boundary. */
6403 offset = (offset + 3) &~ (size_t) 3;
6404
6405 /* Next is a CRC of the index. */
6406 computed_crc = elf_crc32 (crc: 0, buf: compressed + index_offset,
6407 len: offset - index_offset);
6408 stream_crc = ((uint32_t)compressed[offset]
6409 | ((uint32_t)compressed[offset + 1] << 8)
6410 | ((uint32_t)compressed[offset + 2] << 16)
6411 | ((uint32_t)compressed[offset + 3] << 24));
6412 if (unlikely (computed_crc != stream_crc))
6413 {
6414 elf_uncompress_failed ();
6415 return 0;
6416 }
6417 offset += 4;
6418
6419 /* We should now be back at the footer. */
6420 if (unlikely (offset != footer_offset))
6421 {
6422 elf_uncompress_failed ();
6423 return 0;
6424 }
6425
6426 /* Allocate space to hold the uncompressed data. If we succeed in
6427 uncompressing the LZMA data, we never free this memory. */
6428 mem = (unsigned char *) backtrace_alloc (state, size: index_uncompressed_size,
6429 error_callback, data);
6430 if (unlikely (mem == NULL))
6431 return 0;
6432 *uncompressed = mem;
6433 *uncompressed_size = index_uncompressed_size;
6434
6435 /* Allocate space for probabilities. */
6436 probs = ((uint16_t *)
6437 backtrace_alloc (state,
6438 LZMA_PROB_TOTAL_COUNT * sizeof (uint16_t),
6439 error_callback, data));
6440 if (unlikely (probs == NULL))
6441 {
6442 backtrace_free (state, mem, size: index_uncompressed_size, error_callback,
6443 data);
6444 return 0;
6445 }
6446
6447 /* Uncompress the block, which follows the header. */
6448 offset = 12;
6449 if (!elf_uncompress_lzma_block (compressed, compressed_size, check, probs,
6450 uncompressed: mem, uncompressed_size: index_uncompressed_size, poffset: &offset))
6451 {
6452 backtrace_free (state, mem, size: index_uncompressed_size, error_callback,
6453 data);
6454 return 0;
6455 }
6456
6457 compressed_block_size = offset - 12;
6458 if (unlikely (compressed_block_size
6459 != ((index_compressed_size + 3) &~ (size_t) 3)))
6460 {
6461 elf_uncompress_failed ();
6462 backtrace_free (state, mem, size: index_uncompressed_size, error_callback,
6463 data);
6464 return 0;
6465 }
6466
6467 offset = (offset + 3) &~ (size_t) 3;
6468 if (unlikely (offset != index_offset))
6469 {
6470 elf_uncompress_failed ();
6471 backtrace_free (state, mem, size: index_uncompressed_size, error_callback,
6472 data);
6473 return 0;
6474 }
6475
6476 return 1;
6477}
6478
6479/* This function is a hook for testing the LZMA support. It is only
6480 used by tests. */
6481
6482int
6483backtrace_uncompress_lzma (struct backtrace_state *state,
6484 const unsigned char *compressed,
6485 size_t compressed_size,
6486 backtrace_error_callback error_callback,
6487 void *data, unsigned char **uncompressed,
6488 size_t *uncompressed_size)
6489{
6490 return elf_uncompress_lzma (state, compressed, compressed_size,
6491 error_callback, data, uncompressed,
6492 uncompressed_size);
6493}
6494
6495/* Add the backtrace data for one ELF file. Returns 1 on success,
6496 0 on failure (in both cases descriptor is closed) or -1 if exe
6497 is non-zero and the ELF file is ET_DYN, which tells the caller that
6498 elf_add will need to be called on the descriptor again after
6499 base_address is determined. */
6500
6501static int
6502elf_add (struct backtrace_state *state, const char *filename, int descriptor,
6503 const unsigned char *memory, size_t memory_size,
6504 uintptr_t base_address, backtrace_error_callback error_callback,
6505 void *data, fileline *fileline_fn, int *found_sym, int *found_dwarf,
6506 struct dwarf_data **fileline_entry, int exe, int debuginfo,
6507 const char *with_buildid_data, uint32_t with_buildid_size)
6508{
6509 struct elf_view ehdr_view;
6510 b_elf_ehdr ehdr;
6511 off_t shoff;
6512 unsigned int shnum;
6513 unsigned int shstrndx;
6514 struct elf_view shdrs_view;
6515 int shdrs_view_valid;
6516 const b_elf_shdr *shdrs;
6517 const b_elf_shdr *shstrhdr;
6518 size_t shstr_size;
6519 off_t shstr_off;
6520 struct elf_view names_view;
6521 int names_view_valid;
6522 const char *names;
6523 unsigned int symtab_shndx;
6524 unsigned int dynsym_shndx;
6525 unsigned int i;
6526 struct debug_section_info sections[DEBUG_MAX];
6527 struct debug_section_info zsections[DEBUG_MAX];
6528 struct elf_view symtab_view;
6529 int symtab_view_valid;
6530 struct elf_view strtab_view;
6531 int strtab_view_valid;
6532 struct elf_view buildid_view;
6533 int buildid_view_valid;
6534 const char *buildid_data;
6535 uint32_t buildid_size;
6536 struct elf_view debuglink_view;
6537 int debuglink_view_valid;
6538 const char *debuglink_name;
6539 uint32_t debuglink_crc;
6540 struct elf_view debugaltlink_view;
6541 int debugaltlink_view_valid;
6542 const char *debugaltlink_name;
6543 const char *debugaltlink_buildid_data;
6544 uint32_t debugaltlink_buildid_size;
6545 struct elf_view gnu_debugdata_view;
6546 int gnu_debugdata_view_valid;
6547 size_t gnu_debugdata_size;
6548 unsigned char *gnu_debugdata_uncompressed;
6549 size_t gnu_debugdata_uncompressed_size;
6550 off_t min_offset;
6551 off_t max_offset;
6552 off_t debug_size;
6553 struct elf_view debug_view;
6554 int debug_view_valid;
6555 unsigned int using_debug_view;
6556 uint16_t *zdebug_table;
6557 struct elf_view split_debug_view[DEBUG_MAX];
6558 unsigned char split_debug_view_valid[DEBUG_MAX];
6559 struct elf_ppc64_opd_data opd_data, *opd;
6560 struct dwarf_sections dwarf_sections;
6561
6562 if (!debuginfo)
6563 {
6564 *found_sym = 0;
6565 *found_dwarf = 0;
6566 }
6567
6568 shdrs_view_valid = 0;
6569 names_view_valid = 0;
6570 symtab_view_valid = 0;
6571 strtab_view_valid = 0;
6572 buildid_view_valid = 0;
6573 buildid_data = NULL;
6574 buildid_size = 0;
6575 debuglink_view_valid = 0;
6576 debuglink_name = NULL;
6577 debuglink_crc = 0;
6578 debugaltlink_view_valid = 0;
6579 debugaltlink_name = NULL;
6580 debugaltlink_buildid_data = NULL;
6581 debugaltlink_buildid_size = 0;
6582 gnu_debugdata_view_valid = 0;
6583 gnu_debugdata_size = 0;
6584 debug_view_valid = 0;
6585 memset (s: &split_debug_view_valid[0], c: 0, n: sizeof split_debug_view_valid);
6586 opd = NULL;
6587
6588 if (!elf_get_view (state, descriptor, memory, memory_size, offset: 0, size: sizeof ehdr,
6589 error_callback, data, view: &ehdr_view))
6590 goto fail;
6591
6592 memcpy (dest: &ehdr, src: ehdr_view.view.data, n: sizeof ehdr);
6593
6594 elf_release_view (state, view: &ehdr_view, error_callback, data);
6595
6596 if (ehdr.e_ident[EI_MAG0] != ELFMAG0
6597 || ehdr.e_ident[EI_MAG1] != ELFMAG1
6598 || ehdr.e_ident[EI_MAG2] != ELFMAG2
6599 || ehdr.e_ident[EI_MAG3] != ELFMAG3)
6600 {
6601 error_callback (data, "executable file is not ELF", 0);
6602 goto fail;
6603 }
6604 if (ehdr.e_ident[EI_VERSION] != EV_CURRENT)
6605 {
6606 error_callback (data, "executable file is unrecognized ELF version", 0);
6607 goto fail;
6608 }
6609
6610#if BACKTRACE_ELF_SIZE == 32
6611#define BACKTRACE_ELFCLASS ELFCLASS32
6612#else
6613#define BACKTRACE_ELFCLASS ELFCLASS64
6614#endif
6615
6616 if (ehdr.e_ident[EI_CLASS] != BACKTRACE_ELFCLASS)
6617 {
6618 error_callback (data, "executable file is unexpected ELF class", 0);
6619 goto fail;
6620 }
6621
6622 if (ehdr.e_ident[EI_DATA] != ELFDATA2LSB
6623 && ehdr.e_ident[EI_DATA] != ELFDATA2MSB)
6624 {
6625 error_callback (data, "executable file has unknown endianness", 0);
6626 goto fail;
6627 }
6628
6629 /* If the executable is ET_DYN, it is either a PIE, or we are running
6630 directly a shared library with .interp. We need to wait for
6631 dl_iterate_phdr in that case to determine the actual base_address. */
6632 if (exe && ehdr.e_type == ET_DYN)
6633 return -1;
6634
6635 shoff = ehdr.e_shoff;
6636 shnum = ehdr.e_shnum;
6637 shstrndx = ehdr.e_shstrndx;
6638
6639 if ((shnum == 0 || shstrndx == SHN_XINDEX)
6640 && shoff != 0)
6641 {
6642 struct elf_view shdr_view;
6643 const b_elf_shdr *shdr;
6644
6645 if (!elf_get_view (state, descriptor, memory, memory_size, offset: shoff,
6646 size: sizeof shdr, error_callback, data, view: &shdr_view))
6647 goto fail;
6648
6649 shdr = (const b_elf_shdr *) shdr_view.view.data;
6650
6651 if (shnum == 0)
6652 shnum = shdr->sh_size;
6653
6654 if (shstrndx == SHN_XINDEX)
6655 {
6656 shstrndx = shdr->sh_link;
6657
6658 /* Versions of the GNU binutils between 2.12 and 2.18 did
6659 not handle objects with more than SHN_LORESERVE sections
6660 correctly. All large section indexes were offset by
6661 0x100. There is more information at
6662 http://sourceware.org/bugzilla/show_bug.cgi?id-5900 .
6663 Fortunately these object files are easy to detect, as the
6664 GNU binutils always put the section header string table
6665 near the end of the list of sections. Thus if the
6666 section header string table index is larger than the
6667 number of sections, then we know we have to subtract
6668 0x100 to get the real section index. */
6669 if (shstrndx >= shnum && shstrndx >= SHN_LORESERVE + 0x100)
6670 shstrndx -= 0x100;
6671 }
6672
6673 elf_release_view (state, view: &shdr_view, error_callback, data);
6674 }
6675
6676 if (shnum == 0 || shstrndx == 0)
6677 goto fail;
6678
6679 /* To translate PC to file/line when using DWARF, we need to find
6680 the .debug_info and .debug_line sections. */
6681
6682 /* Read the section headers, skipping the first one. */
6683
6684 if (!elf_get_view (state, descriptor, memory, memory_size,
6685 offset: shoff + sizeof (b_elf_shdr),
6686 size: (shnum - 1) * sizeof (b_elf_shdr),
6687 error_callback, data, view: &shdrs_view))
6688 goto fail;
6689 shdrs_view_valid = 1;
6690 shdrs = (const b_elf_shdr *) shdrs_view.view.data;
6691
6692 /* Read the section names. */
6693
6694 shstrhdr = &shdrs[shstrndx - 1];
6695 shstr_size = shstrhdr->sh_size;
6696 shstr_off = shstrhdr->sh_offset;
6697
6698 if (!elf_get_view (state, descriptor, memory, memory_size, offset: shstr_off,
6699 size: shstrhdr->sh_size, error_callback, data, view: &names_view))
6700 goto fail;
6701 names_view_valid = 1;
6702 names = (const char *) names_view.view.data;
6703
6704 symtab_shndx = 0;
6705 dynsym_shndx = 0;
6706
6707 memset (s: sections, c: 0, n: sizeof sections);
6708 memset (s: zsections, c: 0, n: sizeof zsections);
6709
6710 /* Look for the symbol table. */
6711 for (i = 1; i < shnum; ++i)
6712 {
6713 const b_elf_shdr *shdr;
6714 unsigned int sh_name;
6715 const char *name;
6716 int j;
6717
6718 shdr = &shdrs[i - 1];
6719
6720 if (shdr->sh_type == SHT_SYMTAB)
6721 symtab_shndx = i;
6722 else if (shdr->sh_type == SHT_DYNSYM)
6723 dynsym_shndx = i;
6724
6725 sh_name = shdr->sh_name;
6726 if (sh_name >= shstr_size)
6727 {
6728 error_callback (data, "ELF section name out of range", 0);
6729 goto fail;
6730 }
6731
6732 name = names + sh_name;
6733
6734 for (j = 0; j < (int) DEBUG_MAX; ++j)
6735 {
6736 if (strcmp (s1: name, s2: dwarf_section_names[j]) == 0)
6737 {
6738 sections[j].offset = shdr->sh_offset;
6739 sections[j].size = shdr->sh_size;
6740 sections[j].compressed = (shdr->sh_flags & SHF_COMPRESSED) != 0;
6741 break;
6742 }
6743 }
6744
6745 if (name[0] == '.' && name[1] == 'z')
6746 {
6747 for (j = 0; j < (int) DEBUG_MAX; ++j)
6748 {
6749 if (strcmp (s1: name + 2, s2: dwarf_section_names[j] + 1) == 0)
6750 {
6751 zsections[j].offset = shdr->sh_offset;
6752 zsections[j].size = shdr->sh_size;
6753 break;
6754 }
6755 }
6756 }
6757
6758 /* Read the build ID if present. This could check for any
6759 SHT_NOTE section with the right note name and type, but gdb
6760 looks for a specific section name. */
6761 if ((!debuginfo || with_buildid_data != NULL)
6762 && !buildid_view_valid
6763 && strcmp (s1: name, s2: ".note.gnu.build-id") == 0)
6764 {
6765 const b_elf_note *note;
6766
6767 if (!elf_get_view (state, descriptor, memory, memory_size,
6768 offset: shdr->sh_offset, size: shdr->sh_size, error_callback,
6769 data, view: &buildid_view))
6770 goto fail;
6771
6772 buildid_view_valid = 1;
6773 note = (const b_elf_note *) buildid_view.view.data;
6774 if (note->type == NT_GNU_BUILD_ID
6775 && note->namesz == 4
6776 && strncmp (s1: note->name, s2: "GNU", n: 4) == 0
6777 && shdr->sh_size <= 12 + ((note->namesz + 3) & ~ 3) + note->descsz)
6778 {
6779 buildid_data = &note->name[0] + ((note->namesz + 3) & ~ 3);
6780 buildid_size = note->descsz;
6781 }
6782
6783 if (with_buildid_size != 0)
6784 {
6785 if (buildid_size != with_buildid_size)
6786 goto fail;
6787
6788 if (memcmp (s1: buildid_data, s2: with_buildid_data, n: buildid_size) != 0)
6789 goto fail;
6790 }
6791 }
6792
6793 /* Read the debuglink file if present. */
6794 if (!debuginfo
6795 && !debuglink_view_valid
6796 && strcmp (s1: name, s2: ".gnu_debuglink") == 0)
6797 {
6798 const char *debuglink_data;
6799 size_t crc_offset;
6800
6801 if (!elf_get_view (state, descriptor, memory, memory_size,
6802 offset: shdr->sh_offset, size: shdr->sh_size, error_callback,
6803 data, view: &debuglink_view))
6804 goto fail;
6805
6806 debuglink_view_valid = 1;
6807 debuglink_data = (const char *) debuglink_view.view.data;
6808 crc_offset = strnlen (string: debuglink_data, maxlen: shdr->sh_size);
6809 crc_offset = (crc_offset + 3) & ~3;
6810 if (crc_offset + 4 <= shdr->sh_size)
6811 {
6812 debuglink_name = debuglink_data;
6813 debuglink_crc = *(const uint32_t*)(debuglink_data + crc_offset);
6814 }
6815 }
6816
6817 if (!debugaltlink_view_valid
6818 && strcmp (s1: name, s2: ".gnu_debugaltlink") == 0)
6819 {
6820 const char *debugaltlink_data;
6821 size_t debugaltlink_name_len;
6822
6823 if (!elf_get_view (state, descriptor, memory, memory_size,
6824 offset: shdr->sh_offset, size: shdr->sh_size, error_callback,
6825 data, view: &debugaltlink_view))
6826 goto fail;
6827
6828 debugaltlink_view_valid = 1;
6829 debugaltlink_data = (const char *) debugaltlink_view.view.data;
6830 debugaltlink_name = debugaltlink_data;
6831 debugaltlink_name_len = strnlen (string: debugaltlink_data, maxlen: shdr->sh_size);
6832 if (debugaltlink_name_len < shdr->sh_size)
6833 {
6834 /* Include terminating zero. */
6835 debugaltlink_name_len += 1;
6836
6837 debugaltlink_buildid_data
6838 = debugaltlink_data + debugaltlink_name_len;
6839 debugaltlink_buildid_size = shdr->sh_size - debugaltlink_name_len;
6840 }
6841 }
6842
6843 if (!gnu_debugdata_view_valid
6844 && strcmp (s1: name, s2: ".gnu_debugdata") == 0)
6845 {
6846 if (!elf_get_view (state, descriptor, memory, memory_size,
6847 offset: shdr->sh_offset, size: shdr->sh_size, error_callback,
6848 data, view: &gnu_debugdata_view))
6849 goto fail;
6850
6851 gnu_debugdata_size = shdr->sh_size;
6852 gnu_debugdata_view_valid = 1;
6853 }
6854
6855 /* Read the .opd section on PowerPC64 ELFv1. */
6856 if (ehdr.e_machine == EM_PPC64
6857 && (ehdr.e_flags & EF_PPC64_ABI) < 2
6858 && shdr->sh_type == SHT_PROGBITS
6859 && strcmp (s1: name, s2: ".opd") == 0)
6860 {
6861 if (!elf_get_view (state, descriptor, memory, memory_size,
6862 offset: shdr->sh_offset, size: shdr->sh_size, error_callback,
6863 data, view: &opd_data.view))
6864 goto fail;
6865
6866 opd = &opd_data;
6867 opd->addr = shdr->sh_addr;
6868 opd->data = (const char *) opd_data.view.view.data;
6869 opd->size = shdr->sh_size;
6870 }
6871 }
6872
6873 if (symtab_shndx == 0)
6874 symtab_shndx = dynsym_shndx;
6875 if (symtab_shndx != 0 && !debuginfo)
6876 {
6877 const b_elf_shdr *symtab_shdr;
6878 unsigned int strtab_shndx;
6879 const b_elf_shdr *strtab_shdr;
6880 struct elf_syminfo_data *sdata;
6881
6882 symtab_shdr = &shdrs[symtab_shndx - 1];
6883 strtab_shndx = symtab_shdr->sh_link;
6884 if (strtab_shndx >= shnum)
6885 {
6886 error_callback (data,
6887 "ELF symbol table strtab link out of range", 0);
6888 goto fail;
6889 }
6890 strtab_shdr = &shdrs[strtab_shndx - 1];
6891
6892 if (!elf_get_view (state, descriptor, memory, memory_size,
6893 offset: symtab_shdr->sh_offset, size: symtab_shdr->sh_size,
6894 error_callback, data, view: &symtab_view))
6895 goto fail;
6896 symtab_view_valid = 1;
6897
6898 if (!elf_get_view (state, descriptor, memory, memory_size,
6899 offset: strtab_shdr->sh_offset, size: strtab_shdr->sh_size,
6900 error_callback, data, view: &strtab_view))
6901 goto fail;
6902 strtab_view_valid = 1;
6903
6904 sdata = ((struct elf_syminfo_data *)
6905 backtrace_alloc (state, size: sizeof *sdata, error_callback, data));
6906 if (sdata == NULL)
6907 goto fail;
6908
6909 if (!elf_initialize_syminfo (state, base_address,
6910 symtab_view.view.data, symtab_shdr->sh_size,
6911 strtab_view.view.data, strtab_shdr->sh_size,
6912 error_callback, data, sdata, opd))
6913 {
6914 backtrace_free (state, mem: sdata, size: sizeof *sdata, error_callback, data);
6915 goto fail;
6916 }
6917
6918 /* We no longer need the symbol table, but we hold on to the
6919 string table permanently. */
6920 elf_release_view (state, view: &symtab_view, error_callback, data);
6921 symtab_view_valid = 0;
6922 strtab_view_valid = 0;
6923
6924 *found_sym = 1;
6925
6926 elf_add_syminfo_data (state, edata: sdata);
6927 }
6928
6929 elf_release_view (state, view: &shdrs_view, error_callback, data);
6930 shdrs_view_valid = 0;
6931 elf_release_view (state, view: &names_view, error_callback, data);
6932 names_view_valid = 0;
6933
6934 /* If the debug info is in a separate file, read that one instead. */
6935
6936 if (buildid_data != NULL)
6937 {
6938 int d;
6939
6940 d = elf_open_debugfile_by_buildid (state, buildid_data, buildid_size,
6941 error_callback, data);
6942 if (d >= 0)
6943 {
6944 int ret;
6945
6946 elf_release_view (state, view: &buildid_view, error_callback, data);
6947 if (debuglink_view_valid)
6948 elf_release_view (state, view: &debuglink_view, error_callback, data);
6949 if (debugaltlink_view_valid)
6950 elf_release_view (state, view: &debugaltlink_view, error_callback, data);
6951 ret = elf_add (state, filename: "", descriptor: d, NULL, memory_size: 0, base_address, error_callback,
6952 data, fileline_fn, found_sym, found_dwarf, NULL, exe: 0,
6953 debuginfo: 1, NULL, with_buildid_size: 0);
6954 if (ret < 0)
6955 backtrace_close (descriptor: d, error_callback, data);
6956 else if (descriptor >= 0)
6957 backtrace_close (descriptor, error_callback, data);
6958 return ret;
6959 }
6960 }
6961
6962 if (buildid_view_valid)
6963 {
6964 elf_release_view (state, view: &buildid_view, error_callback, data);
6965 buildid_view_valid = 0;
6966 }
6967
6968 if (opd)
6969 {
6970 elf_release_view (state, view: &opd->view, error_callback, data);
6971 opd = NULL;
6972 }
6973
6974 if (debuglink_name != NULL)
6975 {
6976 int d;
6977
6978 d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name,
6979 debuglink_crc, error_callback,
6980 data);
6981 if (d >= 0)
6982 {
6983 int ret;
6984
6985 elf_release_view (state, view: &debuglink_view, error_callback, data);
6986 if (debugaltlink_view_valid)
6987 elf_release_view (state, view: &debugaltlink_view, error_callback, data);
6988 ret = elf_add (state, filename: "", descriptor: d, NULL, memory_size: 0, base_address, error_callback,
6989 data, fileline_fn, found_sym, found_dwarf, NULL, exe: 0,
6990 debuginfo: 1, NULL, with_buildid_size: 0);
6991 if (ret < 0)
6992 backtrace_close (descriptor: d, error_callback, data);
6993 else if (descriptor >= 0)
6994 backtrace_close(descriptor, error_callback, data);
6995 return ret;
6996 }
6997 }
6998
6999 if (debuglink_view_valid)
7000 {
7001 elf_release_view (state, view: &debuglink_view, error_callback, data);
7002 debuglink_view_valid = 0;
7003 }
7004
7005 struct dwarf_data *fileline_altlink = NULL;
7006 if (debugaltlink_name != NULL)
7007 {
7008 int d;
7009
7010 d = elf_open_debugfile_by_debuglink (state, filename, debuglink_name: debugaltlink_name,
7011 debuglink_crc: 0, error_callback, data);
7012 if (d >= 0)
7013 {
7014 int ret;
7015
7016 ret = elf_add (state, filename, descriptor: d, NULL, memory_size: 0, base_address,
7017 error_callback, data, fileline_fn, found_sym,
7018 found_dwarf, fileline_entry: &fileline_altlink, exe: 0, debuginfo: 1,
7019 with_buildid_data: debugaltlink_buildid_data, with_buildid_size: debugaltlink_buildid_size);
7020 elf_release_view (state, view: &debugaltlink_view, error_callback, data);
7021 debugaltlink_view_valid = 0;
7022 if (ret < 0)
7023 {
7024 backtrace_close (descriptor: d, error_callback, data);
7025 return ret;
7026 }
7027 }
7028 }
7029
7030 if (debugaltlink_view_valid)
7031 {
7032 elf_release_view (state, view: &debugaltlink_view, error_callback, data);
7033 debugaltlink_view_valid = 0;
7034 }
7035
7036 if (gnu_debugdata_view_valid)
7037 {
7038 int ret;
7039
7040 ret = elf_uncompress_lzma (state,
7041 compressed: ((const unsigned char *)
7042 gnu_debugdata_view.view.data),
7043 compressed_size: gnu_debugdata_size, error_callback, data,
7044 uncompressed: &gnu_debugdata_uncompressed,
7045 uncompressed_size: &gnu_debugdata_uncompressed_size);
7046
7047 elf_release_view (state, view: &gnu_debugdata_view, error_callback, data);
7048 gnu_debugdata_view_valid = 0;
7049
7050 if (ret)
7051 {
7052 ret = elf_add (state, filename, descriptor: -1, memory: gnu_debugdata_uncompressed,
7053 memory_size: gnu_debugdata_uncompressed_size, base_address,
7054 error_callback, data, fileline_fn, found_sym,
7055 found_dwarf, NULL, exe: 0, debuginfo: 0, NULL, with_buildid_size: 0);
7056 if (ret >= 0 && descriptor >= 0)
7057 backtrace_close(descriptor, error_callback, data);
7058 return ret;
7059 }
7060 }
7061
7062 /* Read all the debug sections in a single view, since they are
7063 probably adjacent in the file. If any of sections are
7064 uncompressed, we never release this view. */
7065
7066 min_offset = 0;
7067 max_offset = 0;
7068 debug_size = 0;
7069 for (i = 0; i < (int) DEBUG_MAX; ++i)
7070 {
7071 off_t end;
7072
7073 if (sections[i].size != 0)
7074 {
7075 if (min_offset == 0 || sections[i].offset < min_offset)
7076 min_offset = sections[i].offset;
7077 end = sections[i].offset + sections[i].size;
7078 if (end > max_offset)
7079 max_offset = end;
7080 debug_size += sections[i].size;
7081 }
7082 if (zsections[i].size != 0)
7083 {
7084 if (min_offset == 0 || zsections[i].offset < min_offset)
7085 min_offset = zsections[i].offset;
7086 end = zsections[i].offset + zsections[i].size;
7087 if (end > max_offset)
7088 max_offset = end;
7089 debug_size += zsections[i].size;
7090 }
7091 }
7092 if (min_offset == 0 || max_offset == 0)
7093 {
7094 if (descriptor >= 0)
7095 {
7096 if (!backtrace_close (descriptor, error_callback, data))
7097 goto fail;
7098 }
7099 return 1;
7100 }
7101
7102 /* If the total debug section size is large, assume that there are
7103 gaps between the sections, and read them individually. */
7104
7105 if (max_offset - min_offset < 0x20000000
7106 || max_offset - min_offset < debug_size + 0x10000)
7107 {
7108 if (!elf_get_view (state, descriptor, memory, memory_size, offset: min_offset,
7109 size: max_offset - min_offset, error_callback, data,
7110 view: &debug_view))
7111 goto fail;
7112 debug_view_valid = 1;
7113 }
7114 else
7115 {
7116 memset (s: &split_debug_view[0], c: 0, n: sizeof split_debug_view);
7117 for (i = 0; i < (int) DEBUG_MAX; ++i)
7118 {
7119 struct debug_section_info *dsec;
7120
7121 if (sections[i].size != 0)
7122 dsec = &sections[i];
7123 else if (zsections[i].size != 0)
7124 dsec = &zsections[i];
7125 else
7126 continue;
7127
7128 if (!elf_get_view (state, descriptor, memory, memory_size,
7129 offset: dsec->offset, size: dsec->size, error_callback, data,
7130 view: &split_debug_view[i]))
7131 goto fail;
7132 split_debug_view_valid[i] = 1;
7133
7134 if (sections[i].size != 0)
7135 sections[i].data = ((const unsigned char *)
7136 split_debug_view[i].view.data);
7137 else
7138 zsections[i].data = ((const unsigned char *)
7139 split_debug_view[i].view.data);
7140 }
7141 }
7142
7143 /* We've read all we need from the executable. */
7144 if (descriptor >= 0)
7145 {
7146 if (!backtrace_close (descriptor, error_callback, data))
7147 goto fail;
7148 descriptor = -1;
7149 }
7150
7151 using_debug_view = 0;
7152 if (debug_view_valid)
7153 {
7154 for (i = 0; i < (int) DEBUG_MAX; ++i)
7155 {
7156 if (sections[i].size == 0)
7157 sections[i].data = NULL;
7158 else
7159 {
7160 sections[i].data = ((const unsigned char *) debug_view.view.data
7161 + (sections[i].offset - min_offset));
7162 ++using_debug_view;
7163 }
7164
7165 if (zsections[i].size == 0)
7166 zsections[i].data = NULL;
7167 else
7168 zsections[i].data = ((const unsigned char *) debug_view.view.data
7169 + (zsections[i].offset - min_offset));
7170 }
7171 }
7172
7173 /* Uncompress the old format (--compress-debug-sections=zlib-gnu). */
7174
7175 zdebug_table = NULL;
7176 for (i = 0; i < (int) DEBUG_MAX; ++i)
7177 {
7178 if (sections[i].size == 0 && zsections[i].size > 0)
7179 {
7180 unsigned char *uncompressed_data;
7181 size_t uncompressed_size;
7182
7183 if (zdebug_table == NULL)
7184 {
7185 zdebug_table = ((uint16_t *)
7186 backtrace_alloc (state, ZLIB_TABLE_SIZE,
7187 error_callback, data));
7188 if (zdebug_table == NULL)
7189 goto fail;
7190 }
7191
7192 uncompressed_data = NULL;
7193 uncompressed_size = 0;
7194 if (!elf_uncompress_zdebug (state, compressed: zsections[i].data,
7195 compressed_size: zsections[i].size, zdebug_table,
7196 error_callback, data,
7197 uncompressed: &uncompressed_data, uncompressed_size: &uncompressed_size))
7198 goto fail;
7199 sections[i].data = uncompressed_data;
7200 sections[i].size = uncompressed_size;
7201 sections[i].compressed = 0;
7202
7203 if (split_debug_view_valid[i])
7204 {
7205 elf_release_view (state, view: &split_debug_view[i],
7206 error_callback, data);
7207 split_debug_view_valid[i] = 0;
7208 }
7209 }
7210 }
7211
7212 if (zdebug_table != NULL)
7213 {
7214 backtrace_free (state, mem: zdebug_table, ZLIB_TABLE_SIZE,
7215 error_callback, data);
7216 zdebug_table = NULL;
7217 }
7218
7219 /* Uncompress the official ELF format
7220 (--compress-debug-sections=zlib-gabi, --compress-debug-sections=zstd). */
7221 for (i = 0; i < (int) DEBUG_MAX; ++i)
7222 {
7223 unsigned char *uncompressed_data;
7224 size_t uncompressed_size;
7225
7226 if (sections[i].size == 0 || !sections[i].compressed)
7227 continue;
7228
7229 if (zdebug_table == NULL)
7230 {
7231 zdebug_table = ((uint16_t *)
7232 backtrace_alloc (state, ZDEBUG_TABLE_SIZE,
7233 error_callback, data));
7234 if (zdebug_table == NULL)
7235 goto fail;
7236 }
7237
7238 uncompressed_data = NULL;
7239 uncompressed_size = 0;
7240 if (!elf_uncompress_chdr (state, compressed: sections[i].data, compressed_size: sections[i].size,
7241 zdebug_table, error_callback, data,
7242 uncompressed: &uncompressed_data, uncompressed_size: &uncompressed_size))
7243 goto fail;
7244 sections[i].data = uncompressed_data;
7245 sections[i].size = uncompressed_size;
7246 sections[i].compressed = 0;
7247
7248 if (debug_view_valid)
7249 --using_debug_view;
7250 else if (split_debug_view_valid[i])
7251 {
7252 elf_release_view (state, view: &split_debug_view[i], error_callback, data);
7253 split_debug_view_valid[i] = 0;
7254 }
7255 }
7256
7257 if (zdebug_table != NULL)
7258 backtrace_free (state, mem: zdebug_table, ZDEBUG_TABLE_SIZE,
7259 error_callback, data);
7260
7261 if (debug_view_valid && using_debug_view == 0)
7262 {
7263 elf_release_view (state, view: &debug_view, error_callback, data);
7264 debug_view_valid = 0;
7265 }
7266
7267 for (i = 0; i < (int) DEBUG_MAX; ++i)
7268 {
7269 dwarf_sections.data[i] = sections[i].data;
7270 dwarf_sections.size[i] = sections[i].size;
7271 }
7272
7273 if (!backtrace_dwarf_add (state, base_address, dwarf_sections: &dwarf_sections,
7274 is_bigendian: ehdr.e_ident[EI_DATA] == ELFDATA2MSB,
7275 fileline_altlink,
7276 error_callback, data, fileline_fn,
7277 fileline_entry))
7278 goto fail;
7279
7280 *found_dwarf = 1;
7281
7282 return 1;
7283
7284 fail:
7285 if (shdrs_view_valid)
7286 elf_release_view (state, view: &shdrs_view, error_callback, data);
7287 if (names_view_valid)
7288 elf_release_view (state, view: &names_view, error_callback, data);
7289 if (symtab_view_valid)
7290 elf_release_view (state, view: &symtab_view, error_callback, data);
7291 if (strtab_view_valid)
7292 elf_release_view (state, view: &strtab_view, error_callback, data);
7293 if (debuglink_view_valid)
7294 elf_release_view (state, view: &debuglink_view, error_callback, data);
7295 if (debugaltlink_view_valid)
7296 elf_release_view (state, view: &debugaltlink_view, error_callback, data);
7297 if (gnu_debugdata_view_valid)
7298 elf_release_view (state, view: &gnu_debugdata_view, error_callback, data);
7299 if (buildid_view_valid)
7300 elf_release_view (state, view: &buildid_view, error_callback, data);
7301 if (debug_view_valid)
7302 elf_release_view (state, view: &debug_view, error_callback, data);
7303 for (i = 0; i < (int) DEBUG_MAX; ++i)
7304 {
7305 if (split_debug_view_valid[i])
7306 elf_release_view (state, view: &split_debug_view[i], error_callback, data);
7307 }
7308 if (opd)
7309 elf_release_view (state, view: &opd->view, error_callback, data);
7310 if (descriptor >= 0)
7311 backtrace_close (descriptor, error_callback, data);
7312 return 0;
7313}
7314
7315/* Data passed to phdr_callback. */
7316
7317struct phdr_data
7318{
7319 struct backtrace_state *state;
7320 backtrace_error_callback error_callback;
7321 void *data;
7322 fileline *fileline_fn;
7323 int *found_sym;
7324 int *found_dwarf;
7325 const char *exe_filename;
7326 int exe_descriptor;
7327};
7328
7329/* Callback passed to dl_iterate_phdr. Load debug info from shared
7330 libraries. */
7331
7332static int
7333#ifdef __i386__
7334__attribute__ ((__force_align_arg_pointer__))
7335#endif
7336phdr_callback (struct dl_phdr_info *info, size_t size ATTRIBUTE_UNUSED,
7337 void *pdata)
7338{
7339 struct phdr_data *pd = (struct phdr_data *) pdata;
7340 const char *filename;
7341 int descriptor;
7342 int does_not_exist;
7343 fileline elf_fileline_fn;
7344 int found_dwarf;
7345
7346 /* There is not much we can do if we don't have the module name,
7347 unless executable is ET_DYN, where we expect the very first
7348 phdr_callback to be for the PIE. */
7349 if (info->dlpi_name == NULL || info->dlpi_name[0] == '\0')
7350 {
7351 if (pd->exe_descriptor == -1)
7352 return 0;
7353 filename = pd->exe_filename;
7354 descriptor = pd->exe_descriptor;
7355 pd->exe_descriptor = -1;
7356 }
7357 else
7358 {
7359 if (pd->exe_descriptor != -1)
7360 {
7361 backtrace_close (descriptor: pd->exe_descriptor, error_callback: pd->error_callback, data: pd->data);
7362 pd->exe_descriptor = -1;
7363 }
7364
7365 filename = info->dlpi_name;
7366 descriptor = backtrace_open (filename: info->dlpi_name, error_callback: pd->error_callback,
7367 data: pd->data, does_not_exist: &does_not_exist);
7368 if (descriptor < 0)
7369 return 0;
7370 }
7371
7372 if (elf_add (state: pd->state, filename, descriptor, NULL, memory_size: 0, base_address: info->dlpi_addr,
7373 error_callback: pd->error_callback, data: pd->data, fileline_fn: &elf_fileline_fn, found_sym: pd->found_sym,
7374 found_dwarf: &found_dwarf, NULL, exe: 0, debuginfo: 0, NULL, with_buildid_size: 0))
7375 {
7376 if (found_dwarf)
7377 {
7378 *pd->found_dwarf = 1;
7379 *pd->fileline_fn = elf_fileline_fn;
7380 }
7381 }
7382
7383 return 0;
7384}
7385
7386/* Initialize the backtrace data we need from an ELF executable. At
7387 the ELF level, all we need to do is find the debug info
7388 sections. */
7389
7390int
7391backtrace_initialize (struct backtrace_state *state, const char *filename,
7392 int descriptor, backtrace_error_callback error_callback,
7393 void *data, fileline *fileline_fn)
7394{
7395 int ret;
7396 int found_sym;
7397 int found_dwarf;
7398 fileline elf_fileline_fn = elf_nodebug;
7399 struct phdr_data pd;
7400
7401 ret = elf_add (state, filename, descriptor, NULL, memory_size: 0, base_address: 0, error_callback, data,
7402 fileline_fn: &elf_fileline_fn, found_sym: &found_sym, found_dwarf: &found_dwarf, NULL, exe: 1, debuginfo: 0, NULL,
7403 with_buildid_size: 0);
7404 if (!ret)
7405 return 0;
7406
7407 pd.state = state;
7408 pd.error_callback = error_callback;
7409 pd.data = data;
7410 pd.fileline_fn = &elf_fileline_fn;
7411 pd.found_sym = &found_sym;
7412 pd.found_dwarf = &found_dwarf;
7413 pd.exe_filename = filename;
7414 pd.exe_descriptor = ret < 0 ? descriptor : -1;
7415
7416 dl_iterate_phdr (callback: phdr_callback, data: (void *) &pd);
7417
7418 if (!state->threaded)
7419 {
7420 if (found_sym)
7421 state->syminfo_fn = elf_syminfo;
7422 else if (state->syminfo_fn == NULL)
7423 state->syminfo_fn = elf_nosyms;
7424 }
7425 else
7426 {
7427 if (found_sym)
7428 backtrace_atomic_store_pointer (&state->syminfo_fn, elf_syminfo);
7429 else
7430 (void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
7431 elf_nosyms);
7432 }
7433
7434 if (!state->threaded)
7435 *fileline_fn = state->fileline_fn;
7436 else
7437 *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
7438
7439 if (*fileline_fn == NULL || *fileline_fn == elf_nodebug)
7440 *fileline_fn = elf_fileline_fn;
7441
7442 return 1;
7443}
7444

source code of libbacktrace/elf.c