1 // This file is part of CAF, the C++ Actor Framework. See the file LICENSE in 2 // the main distribution directory for license terms and copyright or visit 3 // https://github.com/actor-framework/actor-framework/blob/master/LICENSE. 4 5 #pragma once 6 7 #include <cstdint> 8 #include <type_traits> 9 10 #include "caf/detail/ieee_754.hpp" 11 #include "caf/inspector_access.hpp" 12 #include "caf/save_inspector_base.hpp" 13 #include "caf/span.hpp" 14 #include "caf/string_view.hpp" 15 #include "caf/type_id.hpp" 16 17 namespace caf::hash { 18 19 /// Non-cryptographic hash algorithm (variant 1a) named after Glenn Fowler, 20 /// Landon Curt Noll, and Kiem-Phong Vo. 21 /// 22 /// For more details regarding the public domain algorithm, see: 23 /// - https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function 24 /// - http://www.isthe.com/chongo/tech/comp/fnv/index.html 25 /// 26 /// @tparam T One of `uint32_t`, `uint64_t`, or `size_t`. 27 template <class T> 28 class fnv : public save_inspector_base<fnv<T>> { 29 public: 30 static_assert(sizeof(T) == 4 || sizeof(T) == 8); 31 32 using super = save_inspector_base<fnv<T>>; 33 fnv()34 constexpr fnv() noexcept : result(init()) { 35 // nop 36 } 37 has_human_readable_format()38 static constexpr bool has_human_readable_format() noexcept { 39 return false; 40 } 41 begin_object(type_id_t,string_view)42 constexpr bool begin_object(type_id_t, string_view) { 43 return true; 44 } 45 end_object()46 constexpr bool end_object() { 47 return true; 48 } 49 begin_field(string_view)50 bool begin_field(string_view) { 51 return true; 52 } 53 begin_field(string_view,bool is_present)54 bool begin_field(string_view, bool is_present) { 55 return value(static_cast<uint8_t>(is_present)); 56 } 57 begin_field(string_view,span<const type_id_t>,size_t index)58 bool begin_field(string_view, span<const type_id_t>, size_t index) { 59 return value(index); 60 } 61 begin_field(string_view,bool is_present,span<const type_id_t>,size_t index)62 bool begin_field(string_view, bool is_present, span<const type_id_t>, 63 size_t index) { 64 value(static_cast<uint8_t>(is_present)); 65 if (is_present) 66 value(index); 67 return true; 68 } 69 end_field()70 constexpr bool end_field() { 71 return true; 72 } 73 begin_tuple(size_t)74 constexpr bool begin_tuple(size_t) { 75 return true; 76 } 77 end_tuple()78 constexpr bool end_tuple() { 79 return true; 80 } 81 begin_key_value_pair()82 constexpr bool begin_key_value_pair() { 83 return true; 84 } 85 end_key_value_pair()86 constexpr bool end_key_value_pair() { 87 return true; 88 } 89 begin_sequence(size_t)90 constexpr bool begin_sequence(size_t) { 91 return true; 92 } 93 end_sequence()94 constexpr bool end_sequence() { 95 return true; 96 } 97 begin_associative_array(size_t)98 constexpr bool begin_associative_array(size_t) { 99 return true; 100 } 101 end_associative_array()102 constexpr bool end_associative_array() { 103 return true; 104 } 105 106 template <class Integral> 107 std::enable_if_t<std::is_integral<Integral>::value, bool> value(Integral x)108 value(Integral x) noexcept { 109 auto begin = reinterpret_cast<const uint8_t*>(&x); 110 append(begin, begin + sizeof(Integral)); 111 return true; 112 } 113 value(bool x)114 bool value(bool x) noexcept { 115 auto tmp = static_cast<uint8_t>(x); 116 return value(tmp); 117 } 118 value(float x)119 bool value(float x) noexcept { 120 return value(detail::pack754(x)); 121 } 122 value(double x)123 bool value(double x) noexcept { 124 return value(detail::pack754(x)); 125 } 126 value(string_view x)127 bool value(string_view x) noexcept { 128 auto begin = reinterpret_cast<const uint8_t*>(x.data()); 129 append(begin, begin + x.size()); 130 return true; 131 } 132 value(span<const byte> x)133 bool value(span<const byte> x) noexcept { 134 auto begin = reinterpret_cast<const uint8_t*>(x.data()); 135 append(begin, begin + x.size()); 136 return true; 137 } 138 139 /// Convenience function for computing an FNV1a hash value for given 140 /// arguments in one shot. 141 template <class... Ts> compute(Ts &&...xs)142 static T compute(Ts&&... xs) noexcept { 143 using detail::as_mutable_ref; 144 fnv f; 145 auto unused = (f.apply(xs) && ...); 146 static_cast<void>(unused); // Always true. 147 return f.result; 148 } 149 150 T result; 151 152 private: init()153 static constexpr T init() noexcept { 154 if constexpr (sizeof(T) == 4) 155 return 0x811C9DC5u; 156 else 157 return 0xCBF29CE484222325ull; 158 } 159 append(const uint8_t * begin,const uint8_t * end)160 void append(const uint8_t* begin, const uint8_t* end) noexcept { 161 if constexpr (sizeof(T) == 4) 162 while (begin != end) 163 result = (*begin++ ^ result) * 0x01000193u; 164 else 165 while (begin != end) 166 result = (*begin++ ^ result) * 1099511628211ull; 167 } 168 }; 169 170 } // namespace caf::hash 171