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 #ifdef __cplusplus
20
21 #include <string_view>
22
23 #include "pw_preprocessor/compiler.h"
24 #include "pw_preprocessor/util.h"
25 #include "pw_tokenizer/config.h"
26
27 namespace pw::tokenizer {
28
29 // The constant to use when generating the hash. Changing this changes the value
30 // of all hashes, so do not change it randomly.
31 inline constexpr uint32_t k65599HashConstant = 65599u;
32
33 // Calculates the hash of a string. This function calculates hashes at either
34 // runtime or compile time in C++ code.
35 //
36 // Unlike the C hashing macro, this hash supports strings of any length. Strings
37 // longer than the maximum C hashing macro's length will hash different values
38 // in C and C++. If the same very long string is used in C and C++, the string
39 // will appear with both tokens in the resulting database.
40 //
41 // This hash is calculated with the following equation, where s is the string
42 // and k is the maximum hash length:
43 //
44 // H(s, k) = len(s) + 65599 * s[0] + 65599^2 * s[1] + ... + 65599^k * s[k-1]
45 //
46 // The hash algorithm is a modified version of the x65599 hash used by the SDBM
47 // open source project. The modifications were made to support hashing in C
48 // macros. These are the differences from x65599:
49 //
50 // - Characters are hashed in reverse order.
51 // - The string length is hashed as the first character in the string.
52 //
Hash(std::string_view string)53 constexpr uint32_t Hash(std::string_view string)
54 PW_NO_SANITIZE("unsigned-integer-overflow") {
55 // The length is hashed as if it were the first character.
56 uint32_t hash = string.size();
57 uint32_t coefficient = k65599HashConstant;
58
59 // Hash all of the characters in the string as unsigned ints.
60 // The coefficient calculation is done modulo 0x100000000, so the unsigned
61 // integer overflows are intentional.
62 for (uint8_t ch : string) {
63 hash += coefficient * ch;
64 coefficient *= k65599HashConstant;
65 }
66
67 return hash;
68 }
69
70 // Take the string as an array to support either literals or character arrays,
71 // but not const char*.
72 template <size_t kSize>
Hash(const char (& string)[kSize])73 constexpr uint32_t Hash(const char (&string)[kSize]) {
74 static_assert(kSize > 0);
75 return Hash(std::string_view(string, kSize - 1));
76 }
77
78 // This hash function is equivalent to the C hashing macros. It hashses a string
79 // up to a maximum length.
80 constexpr uint32_t PwTokenizer65599FixedLengthHash(
81 std::string_view string,
82 size_t hash_length = PW_TOKENIZER_CFG_C_HASH_LENGTH)
83 PW_NO_SANITIZE("unsigned-integer-overflow") {
84 uint32_t hash = string.size();
85 uint32_t coefficient = k65599HashConstant;
86
87 for (uint8_t ch : string.substr(0, hash_length)) {
88 hash += coefficient * ch;
89 coefficient *= k65599HashConstant;
90 }
91
92 return hash;
93 }
94
95 // Character array version of PwTokenizer65599FixedLengthHash.
96 template <size_t kSize>
97 constexpr uint32_t PwTokenizer65599FixedLengthHash(
98 const char (&string)[kSize],
99 size_t hash_length = PW_TOKENIZER_CFG_C_HASH_LENGTH) {
100 static_assert(kSize > 0);
101 return PwTokenizer65599FixedLengthHash(std::string_view(string, kSize - 1),
102 hash_length);
103 }
104
105 } // namespace pw::tokenizer
106
107 #endif // __cplusplus
108
109 // C version of the fixed-length hash. Can be used to calculate hashes
110 // equivalent to the hashing macros at runtime in C.
111 PW_EXTERN_C uint32_t pw_tokenizer_65599FixedLengthHash(const char* string,
112 size_t string_length,
113 size_t hash_length);
114