Function MurmurHashBitmap64

cpp/src/arrow/util/hashing.cc:41–75

\brief A hash function for bitmaps that can handle offsets and lengths in terms of number of bits. The hash only depends on the bits actually hashed. This implementation is based on 64-bit versions of MurmurHash2 by Austin Appleby. It's the caller's responsibility to ensure that bits_offset + num_bits are readable from the bitmap. \param key The pointer to the bitmap. \param seed The seed for t

/// \param bits_offset The offset in bits relative to the start of the bitmap.
/// \param num_bits The number of bits after the offset to be hashed.
uint64_t MurmurHashBitmap64(const uint8_t* key, uint64_t seed, uint64_t bits_offset,
                            uint64_t num_bits) {
  const uint64_t m = 0xc6a4a7935bd1e995LLU;
  const int r = 47;

  uint64_t h = seed ^ (num_bits * m);

  BitmapWordReader<uint64_t> reader(key, bits_offset, num_bits);
  auto nwords = reader.words();
  while (nwords--) {
    auto k = reader.NextWord();
    k *= m;
    k ^= k >> r;
    k *= m;

    h ^= k;
    h *= m;
  }
  int valid_bits;
  auto nbytes = reader.trailing_bytes();
  if (nbytes) {
    uint64_t k = 0;
    do {
      auto byte = reader.NextTrailingByte(valid_bits);
      k = (k << 8) | static_cast<uint64_t>(byte);
    } while (--nbytes);
    h ^= k;
    h *= m;
  }

  h ^= h >> r;
  h *= m;
  h ^= h >> r;
  return h;
}

}  // namespace