third_party/pigweed/repo/pw_tokenizer/public/pw_tokenizer/hash.h

   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 //
  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 size>
  73 constexpr uint32_t Hash(const char (&string)[size]) {
  74   static_assert(size > 0);
  75   return Hash(std::string_view(string, size - 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 size>
  97 constexpr uint32_t PwTokenizer65599FixedLengthHash(
  98     const char (&string)[size],
  99     size_t hash_length = PW_TOKENIZER_CFG_C_HASH_LENGTH) {
 100   static_assert(size > 0);
 101   return PwTokenizer65599FixedLengthHash(std::string_view(string, size - 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);