// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SRC_LIB_ELFLDLTL_INCLUDE_LIB_ELFLDLTL_COMPAT_HASH_H_
#define SRC_LIB_ELFLDLTL_INCLUDE_LIB_ELFLDLTL_COMPAT_HASH_H_

#include <lib/stdcompat/bit.h>
#include <lib/stdcompat/span.h>

#include <cstdint>
#include <string_view>

namespace elfldltl {

// This handles the DT_HASH format, which is mostly obsolete but is the
// official ELF standard format.  This interface matches GnuHash (gnu-hash.h).
// See SymbolInfo (symbol.h) for details.

inline constexpr uint32_t CompatHashString(std::string_view name) {
  uint_fast32_t hash = 0;
  for (char c : name) {
    hash = (hash << 4) + cpp20::bit_cast<unsigned char>(c);
    hash ^= (hash >> 24) & 0xf0;
  }
  return hash & 0x0fffffff;
}

constexpr uint32_t kCompatNoHash = ~uint32_t{};

// In DT_HASH format, there is a table mapping hash buckets to indices of the
// first symbol table entry in the bucket.  A second "chain" table maps the
// symbol table index of each symbol to the next symbol in the same bucket.
// Empty buckets and the end of a chain are identified by index 0 (STN_UNDEF),
// which is always a null entry.  The first two words of the DT_HASH data are
// the number of buckets and the number of chain entries (i.e. the number of
// symbol table entries).  Then the bucket words follow, then the chain words.

template <typename Word>
class CompatHash {
 public:
  class BucketIterator;

  constexpr explicit CompatHash(cpp20::span<const Word> table)
      : buckets_(table.subspan(2, table[0])), chain_(table.subspan(2 + table[0], table[1])) {}

  static constexpr bool Valid(cpp20::span<const Word> table) {
    if (table.size() < 2) {
      return false;
    }
    const uint32_t nbucket = table[0], nchain = table[1];
    return table.size() - 2 > nbucket && table.size() - 2 - nbucket >= nchain;
  }

  constexpr uint32_t size() const { return static_cast<uint32_t>(chain_.size()); }

  constexpr uint32_t Bucket(uint32_t hash) const {
    if (buckets_.empty()) [[unlikely]] {
      return 0;
    }
    return buckets_[hash % buckets_.size()];
  }

 private:
  cpp20::span<const Word> buckets_, chain_;
};

template <typename Word>
class CompatHash<Word>::BucketIterator {
 public:
  constexpr BucketIterator() = default;
  constexpr BucketIterator(const BucketIterator&) = default;
  constexpr BucketIterator& operator=(const BucketIterator&) = default;

  // This creates a begin() iterator for the bucket and hash value.
  constexpr explicit BucketIterator(const CompatHash& table, uint32_t bucket, uint32_t hash)
      : chain_(table.chain_), i_(BucketIndex(bucket)) {}

  // This creates an end() iterator.
  constexpr explicit BucketIterator(const CompatHash& table) : chain_(table.chain_) {}

  constexpr bool operator==(const BucketIterator& other) const { return i_ == other.i_; }

  constexpr bool operator!=(const BucketIterator& other) const { return !(*this == other); }

  constexpr BucketIterator& operator++() {  // prefix
    // The chain table might encode an infinite loop here.  So cut short
    // iteration when the total number of entries has been enumerated.  In
    // corrupt data, this may not have covered all the entries because it hit a
    // loop.  In valid data, the natural end will always be reached first.
    if (++count_ > chain_.size()) [[unlikely]] {
      i_ = 0;
    } else {
      i_ = BucketIndex(chain_[i_]);
    }
    return *this;
  }

  constexpr BucketIterator& operator++(int) {  // postfix
    auto old = *this;
    ++*this;
    return old;
  }

  constexpr uint32_t operator*() const { return i_; }

 private:
  // If a bogus index came out of the table, reset to end() state.
  constexpr uint32_t BucketIndex(uint32_t symndx) {
    if (symndx < chain_.size()) [[likely]] {
      return symndx;
    }
    return 0;
  }

  cpp20::span<const Word> chain_;
  uint32_t i_ = 0;
  uint32_t count_ = 0;
};

}  // namespace elfldltl

#endif  // SRC_LIB_ELFLDLTL_INCLUDE_LIB_ELFLDLTL_COMPAT_HASH_H_