// 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.

#include "crazy_linker_gnu_hash_table.h"

#include <string.h>

namespace crazy {

// Compute the GNU hash of a given symbol.
static uint32_t GnuHash(const char* name) {
  uint32_t h = 5381;
  const uint8_t* ptr = reinterpret_cast<const uint8_t*>(name);
  while (*ptr) {
    h = h * 33 + *ptr++;
  }
  return h;
}

void GnuHashTable::Init(uintptr_t dt_gnu_hash) {
  sym_count_ = 0;

  const uint32_t* data = reinterpret_cast<const uint32_t*>(dt_gnu_hash);
  num_buckets_ = data[0];
  sym_offset_ = data[1];

  if (!num_buckets_)
    return;

  const uint32_t bloom_size = data[2];
  if ((bloom_size & (bloom_size - 1U)) != 0)  // must be a power of 2
    return;

  bloom_word_mask_ = bloom_size - 1U;
  bloom_shift_ = data[3];
  bloom_filter_ = reinterpret_cast<const ELF::Addr*>(data + 4);
  buckets_ = reinterpret_cast<const uint32_t*>(bloom_filter_ + bloom_size);
  chain_ = buckets_ + num_buckets_;

  // Compute number of dynamic symbols by parsing the table.
  if (num_buckets_ > 0) {
    // First find the maximum index in the buckets table.
    uint32_t max_index = buckets_[0];
    for (size_t n = 1; n < num_buckets_; ++n) {
      uint32_t sym_index = buckets_[n];
      if (sym_index > max_index)
        max_index = sym_index;
    }
    // Now start to look at the chain_ table from (max_index - sym_offset_)
    // until there is a value with LSB set to 1, indicating the end of the
    // last chain.
    while ((chain_[max_index - sym_offset_] & 1) == 0)
      max_index++;

    sym_count_ = (max_index - sym_offset_) + 1;
  }
}

bool GnuHashTable::IsValid() const {
  return sym_count_ > 0;
}

const ELF::Sym* GnuHashTable::LookupByName(const char* symbol_name,
                                           const ELF::Sym* symbol_table,
                                           const char* string_table) const {
  uint32_t hash = GnuHash(symbol_name);

  // First, bloom filter test.
  const unsigned kElfBits = ELF::kElfBits;
  ELF::Addr word = bloom_filter_[(hash / kElfBits) & bloom_word_mask_];
  ELF::Addr mask = (ELF::Addr(1) << (hash % kElfBits)) |
                   (ELF::Addr(1) << ((hash >> bloom_shift_) % kElfBits));

  if ((word & mask) != mask)
    return nullptr;

  uint32_t sym_index = buckets_[hash % num_buckets_];
  if (sym_index < sym_offset_)
    return nullptr;

  while (true) {
    const ELF::Sym* sym = symbol_table + sym_index;
    const uint32_t sym_hash = chain_[sym_index - sym_offset_];
    const char* sym_name = string_table + sym->st_name;

    if ((sym_hash | 1) == (hash | 1) && !strcmp(sym_name, symbol_name)) {
      return sym;
    }

    if (sym_hash & 1)
      break;

    sym_index++;
  }

  return nullptr;
}

}  // namespace crazy