1 /*
2 * Copyright 2017 Content Management AG
3 * All rights reserved.
4 *
5 * author: Max Kellermann <mk@cm4all.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * - Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * - Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the
17 * distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 * FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
25 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
28 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
30 * OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 /*
34 * Implementation of the Fowler-Noll-Vo hash function.
35 */
36
37 #ifndef FNV_HASH_HXX
38 #define FNV_HASH_HXX
39
40 #include "Compiler.h"
41
42 #include <stddef.h>
43 #include <stdint.h>
44
45 template<typename T>
46 struct FNVTraits {};
47
48 template<>
49 struct FNVTraits<uint32_t> {
50 typedef uint32_t value_type;
51 typedef uint_fast32_t fast_type;
52
53 static constexpr value_type OFFSET_BASIS = 2166136261u;
54 static constexpr value_type PRIME = 16777619u;
55 };
56
57 template<>
58 struct FNVTraits<uint64_t> {
59 typedef uint64_t value_type;
60 typedef uint_fast64_t fast_type;
61
62 static constexpr value_type OFFSET_BASIS = 14695981039346656037u;
63 static constexpr value_type PRIME = 1099511628211u;
64 };
65
66 template<typename Traits>
67 struct FNV1aAlgorithm {
68 typedef typename Traits::value_type value_type;
69 typedef typename Traits::fast_type fast_type;
70
71 gcc_hot
UpdateFNV1aAlgorithm72 static constexpr fast_type Update(fast_type hash, uint8_t b) noexcept {
73 return (hash ^ b) * Traits::PRIME;
74 }
75
76 gcc_pure gcc_hot
StringHashFNV1aAlgorithm77 static value_type StringHash(const char *s) noexcept {
78 using Algorithm = FNV1aAlgorithm<Traits>;
79
80 fast_type hash = Traits::OFFSET_BASIS;
81 while (*s)
82 hash = Algorithm::Update(hash, *s++);
83
84 return hash;
85 }
86 };
87
88 gcc_pure gcc_hot
89 inline uint32_t
FNV1aHash32(const char * s)90 FNV1aHash32(const char *s) noexcept
91 {
92 using Traits = FNVTraits<uint32_t>;
93 using Algorithm = FNV1aAlgorithm<Traits>;
94 return Algorithm::StringHash(s);
95 }
96
97 gcc_pure gcc_hot
98 inline uint64_t
FNV1aHash64(const char * s)99 FNV1aHash64(const char *s) noexcept
100 {
101 using Traits = FNVTraits<uint64_t>;
102 using Algorithm = FNV1aAlgorithm<Traits>;
103 return Algorithm::StringHash(s);
104 }
105
106 gcc_pure gcc_hot
107 inline uint32_t
FNV1aHashFold32(const char * s)108 FNV1aHashFold32(const char *s) noexcept
109 {
110 const uint64_t h64 = FNV1aHash64(s);
111
112 /* XOR folding */
113 const uint_fast32_t lo(h64);
114 const uint_fast32_t hi(h64 >> 32);
115 return lo ^ hi;
116 }
117
118 #endif
119