include/flatbuffers/hash.h

   1 /*
   2  * Copyright 2015 Google Inc. All rights reserved.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FLATBUFFERS_HASH_H_
  18 #define FLATBUFFERS_HASH_H_
  19
  20 #include <cstdint>
  21 #include <cstring>
  22
  23 #include "flatbuffers/flatbuffers.h"
  24
  25 namespace flatbuffers {
  26
  27 template<typename T> struct FnvTraits {
  28   static const T kFnvPrime;
  29   static const T kOffsetBasis;
  30 };
  31
  32 template<> struct FnvTraits<uint32_t> {
  33   static const uint32_t kFnvPrime = 0x01000193;
  34   static const uint32_t kOffsetBasis = 0x811C9DC5;
  35 };
  36
  37 template<> struct FnvTraits<uint64_t> {
  38   static const uint64_t kFnvPrime = 0x00000100000001b3ULL;
  39   static const uint64_t kOffsetBasis = 0xcbf29ce484222645ULL;
  40 };
  41
  42 template<typename T> T HashFnv1(const char *input) {
  43   T hash = FnvTraits<T>::kOffsetBasis;
  44   for (const char *c = input; *c; ++c) {
  45     hash *= FnvTraits<T>::kFnvPrime;
  46     hash ^= static_cast<unsigned char>(*c);
  47   }
  48   return hash;
  49 }
  50
  51 template<typename T> T HashFnv1a(const char *input) {
  52   T hash = FnvTraits<T>::kOffsetBasis;
  53   for (const char *c = input; *c; ++c) {
  54     hash ^= static_cast<unsigned char>(*c);
  55     hash *= FnvTraits<T>::kFnvPrime;
  56   }
  57   return hash;
  58 }
  59
  60 template <> inline uint16_t HashFnv1<uint16_t>(const char *input) {
  61   uint32_t hash = HashFnv1<uint32_t>(input);
  62   return (hash >> 16) ^ (hash & 0xffff);
  63 }
  64
  65 template <> inline uint16_t HashFnv1a<uint16_t>(const char *input) {
  66   uint32_t hash = HashFnv1a<uint32_t>(input);
  67   return (hash >> 16) ^ (hash & 0xffff);
  68 }
  69
  70 template <typename T> struct NamedHashFunction {
  71   const char *name;
  72
  73   typedef T (*HashFunction)(const char *);
  74   HashFunction function;
  75 };
  76
  77 const NamedHashFunction<uint16_t> kHashFunctions16[] = {
  78   { "fnv1_16",  HashFnv1<uint16_t> },
  79   { "fnv1a_16", HashFnv1a<uint16_t> },
  80 };
  81
  82 const NamedHashFunction<uint32_t> kHashFunctions32[] = {
  83   { "fnv1_32", HashFnv1<uint32_t> },
  84   { "fnv1a_32", HashFnv1a<uint32_t> },
  85 };
  86
  87 const NamedHashFunction<uint64_t> kHashFunctions64[] = {
  88   { "fnv1_64", HashFnv1<uint64_t> },
  89   { "fnv1a_64", HashFnv1a<uint64_t> },
  90 };
  91
  92 inline NamedHashFunction<uint16_t>::HashFunction FindHashFunction16(
  93     const char *name) {
  94   std::size_t size = sizeof(kHashFunctions16) / sizeof(kHashFunctions16[0]);
  95   for (std::size_t i = 0; i < size; ++i) {
  96     if (std::strcmp(name, kHashFunctions16[i].name) == 0) {
  97       return kHashFunctions16[i].function;
  98     }
  99   }
 100   return nullptr;
 101 }
 102
 103 inline NamedHashFunction<uint32_t>::HashFunction FindHashFunction32(
 104     const char *name) {
 105   std::size_t size = sizeof(kHashFunctions32) / sizeof(kHashFunctions32[0]);
 106   for (std::size_t i = 0; i < size; ++i) {
 107     if (std::strcmp(name, kHashFunctions32[i].name) == 0) {
 108       return kHashFunctions32[i].function;
 109     }
 110   }
 111   return nullptr;
 112 }
 113
 114 inline NamedHashFunction<uint64_t>::HashFunction FindHashFunction64(
 115     const char *name) {
 116   std::size_t size = sizeof(kHashFunctions64) / sizeof(kHashFunctions64[0]);
 117   for (std::size_t i = 0; i < size; ++i) {
 118     if (std::strcmp(name, kHashFunctions64[i].name) == 0) {
 119       return kHashFunctions64[i].function;
 120     }
 121   }
 122   return nullptr;
 123 }
 124
 125 }  // namespace flatbuffers
 126
 127 #endif  // FLATBUFFERS_HASH_H_