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