1
1
/* ELF strtab with GC and suffix merging support.
2
Copyright 2001, 2002 Free Software Foundation, Inc.
2
Copyright 2001, 2002, 2003 Free Software Foundation, Inc.
3
3
Written by Jakub Jelinek <jakub@redhat.com>.
5
5
This file is part of BFD, the Binary File Descriptor library.
30
30
struct elf_strtab_hash_entry
32
32
struct bfd_hash_entry root;
33
/* Length of this entry. */
33
/* Length of this entry. This includes the zero terminator. */
35
35
unsigned int refcount;
37
37
/* Index within the merged section. */
38
38
bfd_size_type index;
39
/* Entry this is a suffix of (if len is 0). */
39
/* Entry this is a suffix of (if len < 0). */
40
40
struct elf_strtab_hash_entry *suffix;
41
struct elf_strtab_hash_entry *next;
235
236
for (i = 1; i < tab->size; ++i)
237
238
register const char *str;
239
register unsigned int len;
240
str = tab->array[i]->root.string;
241
BFD_ASSERT (tab->array[i]->refcount == 0);
241
242
len = tab->array[i]->len;
242
BFD_ASSERT (tab->array[i]->refcount == 0);
246
str = tab->array[i]->root.string;
246
247
if (bfd_bwrite (str, len, abfd) != len)
256
/* Compare two elf_strtab_hash_entry structures. This is called via qsort. */
257
/* Compare two elf_strtab_hash_entry structures. Called via qsort. */
259
cmplengthentry (const void *a, const void *b)
260
strrevcmp (const void *a, const void *b)
261
262
struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
262
263
struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
266
else if (A->len > B->len)
269
return memcmp (A->root.string, B->root.string, A->len);
264
unsigned int lenA = A->len;
265
unsigned int lenB = B->len;
266
const unsigned char *s = A->root.string + lenA - 1;
267
const unsigned char *t = B->root.string + lenB - 1;
268
int l = lenA < lenB ? lenA : lenB;
273
return (int) *s - (int) *t;
273
last4_eq (const void *a, const void *b)
282
is_suffix (const struct elf_strtab_hash_entry *A,
283
const struct elf_strtab_hash_entry *B)
275
const struct elf_strtab_hash_entry *A = a;
276
const struct elf_strtab_hash_entry *B = b;
278
if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
280
/* This was a hashtable collision. */
283
285
if (A->len <= B->len)
284
286
/* B cannot be a suffix of A unless A is equal to B, which is guaranteed
285
287
not to be equal by the hash table. */
288
290
return memcmp (A->root.string + (A->len - B->len),
289
B->root.string, B->len - 5) == 0;
291
B->root.string, B->len - 1) == 0;
292
294
/* This function assigns final string table offsets for used strings,
296
298
_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
298
struct elf_strtab_hash_entry **array, **a, **end, *e;
299
htab_t last4tab = NULL;
300
struct elf_strtab_hash_entry **array, **a, *e;
300
301
bfd_size_type size, amt;
301
struct elf_strtab_hash_entry *last[256], **last_ptr[256];
303
303
/* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
304
304
a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
309
/* Now sort the strings by length, longest first. */
309
/* Sort the strings by suffix and length. */
311
310
amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
312
311
array = bfd_malloc (amt);
313
312
if (array == NULL)
314
313
goto alloc_failure;
316
memset (last, 0, sizeof (last));
317
for (i = 0; i < 256; ++i)
318
last_ptr[i] = &last[i];
319
315
for (i = 1, a = array; i < tab->size; ++i)
320
if (tab->array[i]->refcount)
321
*a++ = tab->array[i];
323
tab->array[i]->len = 0;
321
/* Adjust the length to not include the zero terminator. */
325
328
size = a - array;
327
qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
329
last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
330
if (last4tab == NULL)
333
/* Now insert the strings into hash tables (strings with last 4 characters
334
and strings with last character equal), look for longer strings which
336
for (a = array, end = array + size; a < end; a++)
338
register hashval_t hash;
341
const unsigned char *s;
331
qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
333
/* Loop over the sorted array and merge suffixes. Start from the
334
end because we want eg.
346
ie. we don't want s1 pointing into the old s2. */
347
s = e->root.string + e->len - 1;
349
for (j = 0; j < 4; j++)
352
hash += c + (c << 17);
355
p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
360
struct elf_strtab_hash_entry *ent;
351
struct elf_strtab_hash_entry *cmp = *a;
354
if (is_suffix (e, cmp))
357
cmp->len = -cmp->len;
372
struct elf_strtab_hash_entry *tem;
374
c = e->root.string[e->len - 2] & 0xff;
376
for (tem = last[c]; tem; tem = tem->u.next)
377
if (tem->len > e->len
378
&& memcmp (tem->root.string + (tem->len - e->len),
379
e->root.string, e->len - 1) == 0)
389
c = e->root.string[e->len - 2] & 0xff;
390
/* Put longest strings first. */
392
last_ptr[c] = &e->u.next;
400
htab_delete (last4tab);
402
/* Now assign positions to the strings we want to keep. */
368
/* Assign positions to the strings we want to keep. */
404
370
for (i = 1; i < tab->size; ++i)
406
372
e = tab->array[i];
407
if (e->refcount && e->len)
373
if (e->refcount && e->len > 0)
409
375
e->u.index = size;
414
380
tab->sec_size = size;
416
/* And now adjust the rest. */
382
/* Adjust the rest. */
417
383
for (i = 1; i < tab->size; ++i)
419
385
e = tab->array[i];
420
if (e->refcount && ! e->len)
421
e->u.index = e->u.suffix->u.index
422
+ (e->u.suffix->len - strlen (e->root.string) - 1);
386
if (e->refcount && e->len < 0)
387
e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);