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 #include <iterator>
19 
20 namespace daw {
21  namespace murmur3_details {
22  [[nodiscard]] DAW_ATTRIB_FLATTEN inline constexpr UInt32
23  murmur3_32_scramble( UInt32 k ) {
24  k *= 0xcc9e'2d51_u32;
25  k = rotate_left<15>( k );
26  k *= 0x1b87'3593_u32;
27  return k;
28  }
29  } // namespace murmur3_details
30 
31  template<typename StringView>
32  [[nodiscard]] DAW_ATTRIB_FLATTEN constexpr UInt32
33  fnv1a_32( StringView &&key ) {
34  std::size_t const len = std::size( key );
35  char const *ptr = std::data( key );
36  UInt32 hash = 0x811c'9dc5_u32;
37  for( std::size_t n = 0; n < len; ++n ) {
38  hash ^= static_cast<unsigned char>( ptr[n] );
39  hash *= 0x0100'0193_u32;
40  }
41  return hash;
42  }
43 
44  template<typename StringView>
45  [[nodiscard]] constexpr UInt32 name_hash( StringView const &key,
46  std::uint32_t seed = 0 ) {
47  (void)seed;
48  auto const Sz = std::size( key );
49  if( Sz <= sizeof( UInt32 ) ) {
50  auto result = 0_u32;
51  for( std::size_t n = 0; n < Sz; ++n ) {
52  result <<= 8U;
53  result |= static_cast<unsigned char>( key[n] );
54  }
55  return result;
56  }
57  return fnv1a_32( key );
58  }
59 
60  template<typename StringView>
61  [[nodiscard]] DAW_ATTRIB_FLATINLINE inline constexpr UInt32
62  murmur3_32( StringView &&key, std::uint32_t seed = 0 ) {
63  UInt32 h = to_uint32( seed );
64  UInt32 k = 0_u32;
65  char const *first = std::data( key );
66  char const *const last = daw::data_end( key );
67  while( ( last - first ) >= 4 ) {
68  // Here is a source of differing results across endianness.
69  // A swap here has no effects on hash properties though.
70  k = daw::to_uint32_buffer( first );
71  first += 4;
72  h ^= murmur3_details::murmur3_32_scramble( k );
73  h = rotate_left<13>( h );
74  h = h * 5 + 0xe654'6b64_u32;
75  }
76 
77  // Anything left over
78  k = 0_u32;
79  for( auto i = ( last - first ); i > 0; --i ) {
80  k <<= 8U;
81  k |= static_cast<unsigned char>( first[i - 1] );
82  }
83 
84  h ^= murmur3_details::murmur3_32_scramble( k );
85 
86  h ^= to_uint32( std::size( key ) );
87  h ^= h >> 16U;
88  h *= 0x85eb'ca6b_u32;
89  h ^= h >> 13U;
90  h *= 0xc2b2'ae35_u32;
91  h ^= h >> 16U;
92  return h;
93  }
94 } // namespace daw
Definition: daw_from_json.h:22
constexpr DAW_ATTRIB_FLATTEN UInt32 fnv1a_32(StringView &&key)
Definition: daw_murmur3.h:33
constexpr DAW_ATTRIB_FLATINLINE UInt32 murmur3_32(StringView &&key, std::uint32_t seed=0)
Definition: daw_murmur3.h:62
constexpr UInt32 name_hash(StringView const &key, std::uint32_t seed=0)
Definition: daw_murmur3.h:45