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_do_n.h>
12#include <daw/daw_endian.h>
13#include <daw/daw_string_view.h>
14#include <daw/daw_uint_buffer.h>
15
16#include <ciso646>
17#include <cstddef>
18#include <cstdint>
19#include <iterator>
20
21namespace daw {
22 namespace murmur3_details {
23 [[nodiscard]] DAW_ATTRIB_FLATTEN inline constexpr UInt32
24 murmur3_32_scramble( UInt32 k ) {
25 using prime1 = daw::constant<0xcc9e'2d51_u32>;
26 using prime2 = daw::constant<0x1b87'3593_u32>;
27 k *= prime1::value;
28 k = rotate_left<15>( k );
29 k *= prime2::value;
30 return k;
31 }
32 } // namespace murmur3_details
33
34 template<std::size_t N, typename CharT>
35 [[nodiscard]] DAW_ATTRIB_INLINE constexpr UInt32
36 fnv1a_32_N( CharT *first, UInt32 hash = 0x811c'9dc5_u32 ) {
37 daw::algorithm::do_n_arg<N>( [&]( std::size_t n ) {
38 hash ^= static_cast<UInt32>( first[n] );
39 hash *= 0x0100'0193_u32;
40 } );
41 return hash;
42 }
43
44 template<bool expect_long_strings, typename StringView>
45 [[nodiscard]] DAW_ATTRIB_FLATTEN constexpr auto fnv1a_32( StringView key )
46 -> std::enable_if_t<daw::traits::is_string_view_like_v<StringView>,
47 UInt32> {
48 std::size_t len = std::size( key );
49 auto *ptr = std::data( key );
50 auto hash = 0x811c'9dc5_u32;
51 if constexpr( expect_long_strings ) {
52 while( len >= 8 ) {
53 hash = fnv1a_32_N<8>( ptr, hash );
54 len -= 8;
55 ptr += 8;
56 }
57 while( len >= 4 ) {
58 hash = fnv1a_32_N<4>( ptr, hash );
59 len -= 4;
60 ptr += 4;
61 }
62 }
63 for( std::size_t n = 0; n < len; ++n ) {
64 hash ^= static_cast<unsigned char>( ptr[n] );
65 hash *= 0x0100'0193_u32;
66 }
67 return hash;
68 }
69
70 template<bool expect_long_strings, typename StringView>
71 [[nodiscard]] DAW_ATTRIB_INLINE inline constexpr auto
72 name_hash( StringView key )
73 -> std::enable_if_t<daw::traits::is_string_view_like_v<StringView>,
74 UInt32> {
75 if( auto const Sz = std::size( key );
76 DAW_LIKELY( Sz <= sizeof( UInt32 ) ) ) {
77 auto result = 0_u32;
78 auto const *ptr = std::data( key );
79 for( std::size_t n = 0; n < Sz; ++n ) {
80 result <<= 8U;
81 result |= static_cast<unsigned char>( ptr[n] );
82 }
83 return result;
84 }
85 return fnv1a_32<expect_long_strings>( key );
86 }
87
88 template<typename StringView>
89 [[nodiscard]] DAW_ATTRIB_FLATINLINE inline constexpr auto
90 murmur3_32( StringView key, std::uint32_t seed = 0 )
91 -> std::enable_if_t<daw::traits::is_string_view_like_v<StringView>,
92 UInt32> {
93 UInt32 h = to_uint32( seed );
94 UInt32 k = 0_u32;
95 char const *first = std::data( key );
96 char const *const last = daw::data_end( key );
97 while( ( last - first ) >= 4 ) {
98 // Here is a source of differing results across endianness.
99 // A swap here has no effects on hash properties though.
100 k = daw::to_uint32_buffer( first );
101 first += 4;
102 h ^= murmur3_details::murmur3_32_scramble( k );
103 h = rotate_left<13>( h );
104 h = h * 5 + 0xe654'6b64_u32;
105 }
106
107 // Anything left over
108 k = 0_u32;
109 for( auto i = ( last - first ); i > 0; --i ) {
110 k <<= 8U;
111 k |= static_cast<unsigned char>( first[i - 1] );
112 }
113
114 h ^= murmur3_details::murmur3_32_scramble( k );
115
116 h ^= to_uint32( std::size( key ) );
117 h ^= h >> 16U;
118 h *= 0x85eb'ca6b_u32;
119 h ^= h >> 13U;
120 h *= 0xc2b2'ae35_u32;
121 h ^= h >> 16U;
122 return h;
123 }
124} // namespace daw
Definition: daw_from_json.h:22
constexpr DAW_ATTRIB_INLINE auto name_hash(StringView key) -> std::enable_if_t< daw::traits::is_string_view_like_v< StringView >, UInt32 >
Definition: daw_murmur3.h:72
constexpr DAW_ATTRIB_INLINE UInt32 fnv1a_32_N(CharT *first, UInt32 hash=0x811c '9dc5_u32)
Definition: daw_murmur3.h:36
constexpr DAW_ATTRIB_FLATINLINE auto murmur3_32(StringView key, std::uint32_t seed=0) -> std::enable_if_t< daw::traits::is_string_view_like_v< StringView >, UInt32 >
Definition: daw_murmur3.h:90
constexpr DAW_ATTRIB_FLATTEN auto fnv1a_32(StringView key) -> std::enable_if_t< daw::traits::is_string_view_like_v< StringView >, UInt32 >
Definition: daw_murmur3.h:45