1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14 #pragma once
15
16 #include <stddef.h>
17 #include <stdint.h>
18
19 #include "pw_polyfill/standard.h"
20 #include "pw_preprocessor/util.h"
21
22 #ifdef __cplusplus
23
24 #include <string_view>
25
26 #include "pw_preprocessor/compiler.h"
27 #include "pw_tokenizer/config.h"
28
29 namespace pw::tokenizer {
30
31 // The constant to use when generating the hash. Changing this changes the value
32 // of all hashes, so do not change it randomly.
33 inline constexpr uint32_t k65599HashConstant = 65599u;
34
35 // Calculates the hash of a string. This function calculates hashes at either
36 // runtime or compile time in C++ code.
37 //
38 // Unlike the C hashing macro, this hash supports strings of any length. Strings
39 // longer than the maximum C hashing macro's length will hash different values
40 // in C and C++. If the same very long string is used in C and C++, the string
41 // will appear with both tokens in the resulting database.
42 //
43 // This hash is calculated with the following equation, where s is the string
44 // and k is the maximum hash length:
45 //
46 // H(s, k) = len(s) + 65599 * s[0] + 65599^2 * s[1] + ... + 65599^k * s[k-1]
47 //
48 // The hash algorithm is a modified version of the x65599 hash used by the SDBM
49 // open source project. The modifications were made to support hashing in C
50 // macros. These are the differences from x65599:
51 //
52 // - Characters are hashed in reverse order.
53 // - The string length is hashed as the first character in the string.
54 //
Hash(std::string_view string)55 constexpr uint32_t Hash(std::string_view string)
56 PW_NO_SANITIZE("unsigned-integer-overflow") {
57 // The length is hashed as if it were the first character.
58 uint32_t hash = static_cast<uint32_t>(string.size());
59 uint32_t coefficient = k65599HashConstant;
60
61 // Hash all of the characters in the string as unsigned ints.
62 // The coefficient calculation is done modulo 0x100000000, so the unsigned
63 // integer overflows are intentional.
64 for (char ch : string) {
65 hash += coefficient * static_cast<uint8_t>(ch);
66 coefficient *= k65599HashConstant;
67 }
68
69 return hash;
70 }
71
72 // Take the string as an array to support either literals or character arrays,
73 // but not const char*.
74 template <size_t kSize>
Hash(const char (& string)[kSize])75 constexpr uint32_t Hash(const char (&string)[kSize]) {
76 static_assert(kSize > 0);
77 return Hash(std::string_view(string, kSize - 1));
78 }
79
80 // This hash function is equivalent to the C hashing macros. It hashses a string
81 // up to a maximum length.
82 constexpr uint32_t PwTokenizer65599FixedLengthHash(
83 std::string_view string,
84 size_t hash_length = PW_TOKENIZER_CFG_C_HASH_LENGTH)
85 PW_NO_SANITIZE("unsigned-integer-overflow") {
86 uint32_t hash = static_cast<uint32_t>(string.size());
87 uint32_t coefficient = k65599HashConstant;
88
89 for (char ch : string.substr(0, hash_length)) {
90 hash += coefficient * static_cast<uint8_t>(ch);
91 coefficient *= k65599HashConstant;
92 }
93
94 return hash;
95 }
96
97 // Character array version of PwTokenizer65599FixedLengthHash.
98 template <size_t kSize>
99 constexpr uint32_t PwTokenizer65599FixedLengthHash(
100 const char (&string)[kSize],
101 size_t hash_length = PW_TOKENIZER_CFG_C_HASH_LENGTH) {
102 static_assert(kSize > 0);
103 return PwTokenizer65599FixedLengthHash(std::string_view(string, kSize - 1),
104 hash_length);
105 }
106
107 } // namespace pw::tokenizer
108
109 #endif // __cplusplus
110
111 // C version of the fixed-length hash. Can be used to calculate hashes
112 // equivalent to the hashing macros at runtime in C.
113 PW_EXTERN_C uint32_t pw_tokenizer_65599FixedLengthHash(const char* string,
114 size_t string_length,
115 size_t hash_length);
116