hash_t.h

Go to the documentation of this file.

 
#if !defined(ULTRA_HASH_T_H)
#define      ULTRA_HASH_T_H
 
#include "utility/assert.h"
 
#include <algorithm>
#include <array>
#include <bit>
#include <concepts>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <span>
 
namespace ultra
{
struct hash_t
{
  explicit hash_t(std::uint64_t a = 0, std::uint64_t b = 0) : data{a, b} {}

  void clear() noexcept { data[0] = data[1] = 0; }

  [[nodiscard]] bool operator==(const hash_t &) const noexcept = default;
 
  [[nodiscard]] bool operator<(const hash_t &rhs) const noexcept
  {
    return data[0] < rhs.data[0]
           || (data[0] == rhs.data[0] && data[1] < rhs.data[1]);
  }

  void combine(hash_t h) noexcept
  {
    // This is the simple algorithm used in `Apache.Commons.HashCodeBuilder`.
    // It uses simple prime number multiplication and is a special case of
    // Bob Jenkins' idea (`m * H(A) + H(B)`).
    data[0] = data[0] * 37 + h.data[0];
    data[1] = data[1] * 37 + h.data[1];
 
    // An alternative from Boost is:
    //   data[0] ^= h.data[0] + 0x9e3779b9 + (data[0] << 6) + (data[0] >> 2);
    //   data[1] ^= h.data[1] + 0x9e3779b9 + (data[1] << 6) + (data[1] >> 2);
    // Under Boost, combining {0, 0} into {0, 0} immediately produces 0x9e3779b9
    // (non-empty).
 
    // In spite of its handy bit-mixing properties, XOR is not a good way to
    // combine hashes due to its commutativity (e.g. see
    // https://stackoverflow.com/q/5889238/3235496).
  }

  [[nodiscard]] bool empty() const noexcept { return !data[0] && !data[1]; }
 
  // Serialization.
  bool load(std::istream &);
  bool save(std::ostream &) const;
 
  // Data members.
  std::uint64_t data[2];
};
 
std::ostream &operator<<(std::ostream &, hash_t);
 
// Implementation details for MurmurHash3 x64 128-bit hashing.
// This namespace contains the low-level primitives shared by both the
// one-shot (`murmurhash3::hash128`) and incremental (`murmurhash3_sink`)
// implementations: block mixing, tail processing, finalisation.
// Keeping these routines in a single place guarantees bitwise equivalence
// between hashing modes and avoids code duplication.
namespace internal
{
 
// For MurmurHash3 x64 128-bit, the block size is 16 bytes, i.e. 128 bits.
inline constexpr std::size_t murmurhash3_block_size {16};
 
static constexpr std::uint64_t c1 {0x87c37b91114253d5};
static constexpr std::uint64_t c2 {0x4cf5ad432745937f};
 
inline std::uint64_t fmix(std::uint64_t k) noexcept
{
  // The constants were generated by a simple simulated-annealing algorithm.
  k ^= k >> 33;
  k *= 0xff51afd7ed558ccd;
  k ^= k >> 33;
  k *= 0xc4ceb9fe1a85ec53;
  k ^= k >> 33;
 
  return k;
}
 
inline std::uint32_t fmix(std::uint32_t k) noexcept
{
  // The constants were generated by a simple simulated-annealing algorithm.
  k ^= k >> 16;
  k *= 0x85ebca6b;
  k ^= k >> 13;
  k *= 0xc2b2ae35;
  k ^= k >> 16;
 
  return k;
}

inline void finalize(hash_t &h, std::size_t total_len) noexcept
{
  h.data[0] ^= total_len;
  h.data[1] ^= total_len;
 
  h.data[0] += h.data[1];
  h.data[1] += h.data[0];
 
  h.data[0] = fmix(h.data[0]);
  h.data[1] = fmix(h.data[1]);
 
  h.data[0] += h.data[1];
  h.data[1] += h.data[0];
}

inline void process_block(hash_t &h, std::uint64_t k1,
                          std::uint64_t k2) noexcept
{
  k1 *= c1;
  k1  = std::rotl(k1, 31);
  k1 *= c2;
  h.data[0] ^= k1;
 
  h.data[0] = std::rotl(h.data[0], 27);
  h.data[0] += h.data[1];
  h.data[0] = h.data[0] * 5 + 0x52dce729;
 
  k2 *= c2;
  k2  = std::rotl(k2, 33);
  k2 *= c1;
  h.data[1] ^= k2;
 
  h.data[1] = std::rotl(h.data[1], 31);
  h.data[1] += h.data[0];
  h.data[1] = h.data[1] * 5 + 0x38495ab5;
}

inline void process_tail(hash_t &h,
                         const std::byte *tail, std::size_t len) noexcept
{
  std::uint64_t k1(0), k2(0);
 
  switch (len)
  {
  case 15: k2 ^= std::uint64_t(tail[14]) << 48;  [[fallthrough]];
  case 14: k2 ^= std::uint64_t(tail[13]) << 40;  [[fallthrough]];
  case 13: k2 ^= std::uint64_t(tail[12]) << 32;  [[fallthrough]];
  case 12: k2 ^= std::uint64_t(tail[11]) << 24;  [[fallthrough]];
  case 11: k2 ^= std::uint64_t(tail[10]) << 16;  [[fallthrough]];
  case 10: k2 ^= std::uint64_t(tail[ 9]) <<  8;  [[fallthrough]];
  case  9: k2 ^= std::uint64_t(tail[ 8]);
           k2 *= c2; k2 = std::rotl(k2, 33); k2 *= c1; h.data[1] ^= k2;
           [[fallthrough]];
  case  8: k1 ^= std::uint64_t(tail[ 7]) << 56;  [[fallthrough]];
  case  7: k1 ^= std::uint64_t(tail[ 6]) << 48;  [[fallthrough]];
  case  6: k1 ^= std::uint64_t(tail[ 5]) << 40;  [[fallthrough]];
  case  5: k1 ^= std::uint64_t(tail[ 4]) << 32;  [[fallthrough]];
  case  4: k1 ^= std::uint64_t(tail[ 3]) << 24;  [[fallthrough]];
  case  3: k1 ^= std::uint64_t(tail[ 2]) << 16;  [[fallthrough]];
  case  2: k1 ^= std::uint64_t(tail[ 1]) <<  8;  [[fallthrough]];
  case  1: k1 ^= std::uint64_t(tail[ 0]);
           k1 *= c1; k1 = std::rotl(k1, 31); k1 *= c2;
           h.data[0] ^= k1;
  }
}
 
template<std::unsigned_integral T>
[[nodiscard]] T load_unaligned(const std::byte *p) noexcept
{
  // Loads using the host byte order. This is well-defined, but hash values are
  // not guaranteed to be identical across endian architectures.
  //
  // Use memcpy() to load potentially unaligned bytes without violating
  // strict-aliasing rules.
 
  T tmp;
  std::memcpy(&tmp, p, sizeof(T));
  return tmp;
}
 
}  // namespace internal

class murmurhash3
{
public:
  [[nodiscard]] static hash_t hash128(const void *const, std::size_t,
                                      std::uint32_t = 1973) noexcept;
};

inline hash_t murmurhash3::hash128(const void *const data, std::size_t len,
                                   std::uint32_t seed) noexcept
{
  Expects(data || len == 0);
 
  const auto n_blocks(len / internal::murmurhash3_block_size);
 
  // Body.
  const auto *bytes(reinterpret_cast<const std::byte *>(data));
 
  hash_t h(seed, seed);
 
  using internal::load_unaligned;
  for (std::size_t i(0); i < n_blocks; ++i)
  {
    const auto offset(i * internal::murmurhash3_block_size);
 
    const auto k1(load_unaligned<std::uint64_t>(bytes + offset));
    const auto k2(load_unaligned<std::uint64_t>(bytes + offset + sizeof(k1)));
 
    internal::process_block(h, k1, k2);
  }
 
  // Tail.
  if (const auto tail_len(len % internal::murmurhash3_block_size); tail_len)
  {
    const auto tail_offset(len - tail_len);
    internal::process_tail(h, bytes + tail_offset, tail_len);
  }
 
  internal::finalize(h, len);
 
  return h;
}

class murmurhash3_sink
{
public:
  explicit murmurhash3_sink(std::uint32_t = 1973) noexcept;
 
  void write(std::span<const std::byte>) noexcept;
  [[nodiscard]] hash_t final() noexcept;
 
private:
  void process_block(const std::byte* data) noexcept;
 
private:
  hash_t h_;
  std::array<std::byte, internal::murmurhash3_block_size> tail_ {};
  std::size_t tail_size_ {0};
  std::size_t total_len_ {0};
};  // class murmurhash3_sink

inline murmurhash3_sink::murmurhash3_sink(std::uint32_t seed) noexcept
  : h_(seed, seed)
{
}

inline void murmurhash3_sink::write(std::span<const std::byte> bytes) noexcept
{
  total_len_ += bytes.size();
 
  // Fill tail if needed.
  if (tail_size_)
  {
    const auto n(std::min<std::size_t>(
                   internal::murmurhash3_block_size - tail_size_,
                   bytes.size()));
 
    std::memcpy(tail_.data() + tail_size_, bytes.data(), n);
    tail_size_ += n;
    bytes = bytes.subspan(n);
 
    if (tail_size_ == internal::murmurhash3_block_size)
    {
      process_block(tail_.data());
      tail_size_ = 0;
    }
  }
 
  // Process full blocks.
  while (bytes.size() >= internal::murmurhash3_block_size)
  {
    process_block(bytes.data());
    bytes = bytes.subspan(internal::murmurhash3_block_size);
  }
 
  // Store remaining bytes as tail.
  if (!bytes.empty())
  {
    std::memcpy(tail_.data(), bytes.data(), bytes.size());
    tail_size_ = bytes.size();
  }
}
 
inline void murmurhash3_sink::process_block(const std::byte *data) noexcept
{
  const auto k1(internal::load_unaligned<std::uint64_t>(data));
  const auto k2(internal::load_unaligned<std::uint64_t>(data + sizeof(k1)));
 
  internal::process_block(h_, k1, k2);
}

inline hash_t murmurhash3_sink::final() noexcept
{
  internal::process_tail(h_, reinterpret_cast<const std::byte *>(tail_.data()),
                         tail_size_);
  internal::finalize(h_, total_len_);
  return h_;
}
 
using hash = murmurhash3;
using hash_sink = murmurhash3_sink;

template <class T>
requires (std::integral<T> || std::floating_point<T>)
[[nodiscard]] std::span<const std::byte, sizeof(T)>
bytes_view(const T &t) noexcept
{
  return std::span<const std::byte, sizeof(T)>{
    reinterpret_cast<const std::byte *>(std::addressof(t)), sizeof(T)};
}
 
[[nodiscard]] std::span<const std::byte>
bytes_view(const std::string &) noexcept;
 
}  // namespace ultra
 
#endif  // include guard