DAW JSON Link
daw_murmur3.h
Go to the documentation of this file.
1 // Copyright (c) Darrell Wright
2 //
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
5 //
6 // Official repository: https://github.com/beached/daw_json_link
7 //
8 
9 #pragma once
10 
11 #include <daw/daw_endian.h>
12 #include <daw/daw_string_view.h>
13 #include <daw/daw_uint_buffer.h>
14 
15 #include <ciso646>
16 #include <cstddef>
17 #include <cstdint>
18 
19 namespace daw {
20  namespace murmur3_details {
21  [[nodiscard]] inline constexpr UInt32 murmur3_32_scramble( UInt32 k ) {
22  k *= 0xcc9e'2d51_u32;
23  k = rotate_left<15>( k );
24  k *= 0x1b87'3593_u32;
25  return k;
26  }
27  } // namespace murmur3_details
28 
29  template<typename StringView>
30  [[nodiscard]] DAW_ATTRIBUTE_FLATTEN inline constexpr UInt32
31  fnv1a_32( StringView key ) {
32  std::size_t const len = std::size( key );
33  char const *ptr = std::data( key );
34  UInt32 hash = 0x811c'9dc5_u32;
35  for( std::size_t n = 0; n < len; ++n ) {
36  hash ^= static_cast<unsigned char>( ptr[n] );
37  hash *= 0x0100'0193_u32;
38  }
39  return hash;
40  }
41 
42  template<typename StringView>
43  [[nodiscard]] constexpr UInt32 name_hash( StringView key,
44  std::uint32_t seed = 0 ) {
45  (void)seed;
46  auto const Sz = std::size( key );
47  if( Sz <= sizeof( UInt32 ) ) {
48  auto result = 0_u32;
49  for( std::size_t n = 0; n < Sz; ++n ) {
50  result <<= 8U;
51  result |= static_cast<unsigned char>( key[n] );
52  }
53  return result;
54  }
55  return fnv1a_32( key );
56  }
57 
58  template<typename StringView>
59  [[nodiscard]] DAW_ATTRIBUTE_FLATTEN inline constexpr UInt32
60  murmur3_32( StringView key, std::uint32_t seed = 0 ) {
61  UInt32 h = to_uint32( seed );
62  UInt32 k = 0_u32;
63  char const *first = std::data( key );
64  char const *const last = std::data( key ) + std::size( key );
65  while( ( last - first ) >= 4 ) {
66  // Here is a source of differing results across endiannesses.
67  // A swap here has no effects on hash properties though.
68  k = daw::to_uint32_buffer( first );
69  first += 4;
70  h ^= murmur3_details::murmur3_32_scramble( k );
71  h = rotate_left<13>( h );
72  h = h * 5 + 0xe654'6b64_u32;
73  }
74 
75  // Anything left over
76  k = 0_u32;
77  for( auto i = ( last - first ); i > 0; --i ) {
78  k <<= 8U;
79  k |= static_cast<unsigned char>( first[i - 1] );
80  }
81 
82  h ^= murmur3_details::murmur3_32_scramble( k );
83 
84  h ^= to_uint32( std::size( key ) );
85  h ^= h >> 16U;
86  h *= 0x85eb'ca6b_u32;
87  h ^= h >> 13U;
88  h *= 0xc2b2'ae35_u32;
89  h ^= h >> 16U;
90  return h;
91  }
92 } // namespace daw
daw::fnv1a_32
constexpr DAW_ATTRIBUTE_FLATTEN UInt32 fnv1a_32(StringView key)
Definition: daw_murmur3.h:31
daw::name_hash
constexpr UInt32 name_hash(StringView key, std::uint32_t seed=0)
Definition: daw_murmur3.h:43
daw
Definition: daw_json_event_parser.h:17
daw::murmur3_32
constexpr DAW_ATTRIBUTE_FLATTEN UInt32 murmur3_32(StringView key, std::uint32_t seed=0)
Definition: daw_murmur3.h:60