| #!/usr/bin/env python |
| |
| # Copyright 2018 The Chromium Authors. All rights reserved. |
| # Use of this source code is governed by a BSD-style license that can be |
| # found in the LICENSE file. |
| |
| """Simple script used to generate the SysV ELF hash table test data""" |
| |
| import collections |
| import os |
| |
| from pylib import source_utils |
| from pylib import elf_utils |
| |
| script_name = os.path.basename(__file__) |
| |
| |
| def ElfHash(name): |
| """Compute the ELF hash of a given input string.""" |
| h = 0 |
| for c in name: |
| h = (h << 4) + ord(c) |
| g = h & 0xf0000000 |
| h ^= g |
| h ^= g >> 24 |
| return h & 0xffffffff |
| |
| |
| class ElfHashTable(object): |
| def __init__(self, num_buckets, symbol_names): |
| """Initialize a new SysV ELF hash table instance. |
| |
| Args: |
| num_buckets: Number of hash buckets, must be > 0. |
| symbol_names: List of symbol names. |
| """ |
| self.num_buckets_ = num_buckets |
| self.num_chain_ = len(symbol_names) + 1 |
| |
| self.symbols_ = symbol_names |
| self.hashes_ = [ElfHash(t) for t in symbol_names] |
| |
| # Build bucket and chain arrays. |
| buckets = [0] * num_buckets |
| chain = [0] * self.num_chain_ |
| |
| for n, symbol in enumerate(self.symbols_): |
| elf_hash = self.hashes_[n] |
| bucket_index = elf_hash % num_buckets |
| idx = buckets[bucket_index] |
| if idx == 0: |
| buckets[bucket_index] = n + 1 |
| else: |
| while chain[idx] != 0: |
| idx = chain[idx] |
| chain[idx] = n + 1 |
| |
| self.buckets_ = buckets |
| self.chain_ = chain |
| |
| # Generate final string table and symbol offsets. |
| self.string_table_, self.symbol_offsets_ = \ |
| elf_utils.GenerateStringTable(self.symbols_) |
| |
| def __str__(self): |
| """Dump human-friendly text description for this table.""" |
| out = 'SysV ELF hash table: num_buckets=%d num_chain=%d\n\n' % ( |
| self.num_buckets_, self.num_chain_) |
| |
| out += 'idx symbol hash bucket chain\n' |
| out += ' 0 <STN_UNDEF>\n' |
| for n, symbol in enumerate(self.symbols_): |
| elf_hash = self.hashes_[n] |
| bucket_index = elf_hash % self.num_buckets_ |
| out += '%3d %-20s %08x %-3d %d\n' % ( |
| n + 1, symbol, elf_hash, bucket_index, self.chain_[n + 1]) |
| |
| out += '\nBuckets: ' |
| comma = '' |
| for b in self.buckets_: |
| out += '%s%d' % (comma, b) |
| comma = ', ' |
| |
| out += '\n' |
| return out |
| |
| def AsCSource(self, variable_prefix, guard_macro_name): |
| """Dump the content of this instance.""" |
| out = source_utils.CSourceBeginAutoGeneratedHeader(script_name, |
| guard_macro_name) |
| out += source_utils.CSourceForComments(str(self)) |
| out += source_utils.CSourceForConstCharArray( |
| self.string_table_, 'k%sStringTable' % variable_prefix) |
| out += '\n' |
| out += elf_utils.CSourceForElfSymbolListMacro(variable_prefix, |
| self.symbols_, |
| self.symbol_offsets_) |
| out += '\n' |
| out += elf_utils.CSourceForElfSymbolTable(variable_prefix, |
| self.symbols_, |
| self.symbol_offsets_) |
| |
| out += '\nstatic const uint32_t k%sHashTable[] = {\n' % variable_prefix |
| out += ' %d, // num_buckets\n' % self.num_buckets_ |
| out += ' %d, // num_chain\n' % self.num_chain_ |
| out += ' // Buckets\n' |
| out += source_utils.CSourceForIntegerHexArray(self.buckets_, 32) |
| out += ' // Chain\n' |
| out += source_utils.CSourceForIntegerHexArray(self.chain_, 32) |
| out += '};\n' |
| out += source_utils.CSourceEndAutoGeneratedHeader(script_name, |
| guard_macro_name) |
| return out |
| |
| def main(): |
| # Same data as the one found on the following web page: |
| # |
| # https://flapenguin.me/2017/04/24/elf-lookup-dt-hash/ |
| # |
| # NOTE: The hash values on that page are incorrect, so results differs!! |
| # |
| table = ElfHashTable(4, [ |
| 'isnan', 'freelocal', 'hcreate_', 'getopt_long_onl', 'endrpcen', |
| 'pthread_mutex_lock', 'isinf', 'setrlimi', 'getspen', 'umoun', |
| 'strsigna', 'listxatt', 'gettyen', 'uselib', 'cfsetispeed']) |
| print table.AsCSource('TestElf', 'CRAZY_LINKER_ELF_HASH_TABLE_TEST_DATA_H') |
| |
| if __name__ == "__main__": |
| main() |