hash.h File Reference

#include "future_compat.h"
#include <sys/types.h>
#include <cstdint>

Go to the source code of this file.

Namespaces
	MURMUR_HASH_3

Functions
constexpr uint32_t	rotl32 (uint32_t x, int8_t r) noexcept
static VW_STD14_CONSTEXPR uint32_t	MURMUR_HASH_3::fmix (uint32_t h) noexcept
static constexpr uint32_t	MURMUR_HASH_3::getblock (const uint32_t *p, int i) noexcept
VW_STD14_CONSTEXPR uint64_t	uniform_hash (const void *key, size_t len, uint64_t seed)

Function Documentation

rotl32()

constexpr uint32_t rotl32 ( uint32_t  x, int8_t  r  )

inlinenoexcept

Definition at line 38 of file hash.h.

Referenced by uniform_hash().

{
  return (x << r) | (x >> (32 - r));
}

uniform_hash()

VW_STD14_CONSTEXPR uint64_t uniform_hash ( const void *  key, size_t  len, uint64_t  seed  )

inline

Definition at line 67 of file hash.h.

References MURMUR_HASH_3::fmix(), MURMUR_HASH_3::getblock(), and rotl32().

Referenced by io_buf::bin_read_fixed(), io_buf::bin_write_fixed(), Search::cached_action_store_or_find(), cbify_setup(), cbifyldf_setup(), namedlabels::get(), hashall(), hashstring(), VW::cb_sample_data::learn_or_predict(), TC_parser< audit >::maybeFeature(), namedlabels::namedlabels(), TC_parser< audit >::nameSpace(), parse_dictionary_argument(), vw_slim::model_parser::read(), vw_slim::model_parser::read_string(), exploration::sample_after_normalizing(), save_load_header(), vw_slim::model_parser::skip(), MultiState< audit >::StartArray(), and warm_cb_setup().

{
  const uint8_t* data = (const uint8_t*)key;
  const int nblocks = (int)len / 4;

  uint32_t h1 = (uint32_t)seed;

  const uint32_t c1 = 0xcc9e2d51;
  const uint32_t c2 = 0x1b873593;

  // --- body
  const uint32_t* blocks = (const uint32_t *)(data + nblocks * 4);

  for (int i = -nblocks; i; i++)
  {
    uint32_t k1 = MURMUR_HASH_3::getblock(blocks, i);

    k1 *= c1;
    k1 = rotl32(k1, 15);
    k1 *= c2;

    h1 ^= k1;
    h1 = rotl32(h1, 13);
    h1 = h1 * 5 + 0xe6546b64;
  }

  // --- tail
  const uint8_t * tail = (const uint8_t*)(data + nblocks * 4);

  uint32_t k1 = 0;

  // The 'fall through' comments below silence the implicit-fallthrough warning introduced in GCC 7.
  // Once we move to C++17 these should be replaced with the [[fallthrough]] attribute.
  switch (len & 3u)
  {
  case 3:
    k1 ^= tail[2] << 16;
    // fall through
  case 2:
    k1 ^= tail[1] << 8;
    // fall through
  case 1: k1 ^= tail[0];
    k1 *= c1;
    k1 = rotl32(k1, 15);
    k1 *= c2; h1 ^= k1;
  default:
    break;
  }

  // --- finalization
  h1 ^= len;

  return MURMUR_HASH_3::fmix(h1);
}