src/third_party/android_crazy_linker/src/tests/generate_test_elf_hash_tables.py

#!/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()