source/core/hash.h

   1 #ifndef MSP_CORE_HASH_H_
   2 #define MSP_CORE_HASH_H_
   3
   4 #include <cstdint>
   5 #include <limits>
   6 #include <string>
   7
   8 namespace Msp {
   9
  10 template<unsigned N, unsigned L = 3+(N>8)+(N>16)+(N>32)+(N>64)>
  11 struct HashTraits;
  12
  13 template<>
  14 struct HashTraits<64, 6>
  15 {
  16         using HashType = uint64_t;
  17         using ResultType = uint64_t;
  18         static constexpr HashType prime = 1099511628211ULL;
  19         static constexpr HashType offset = 14695981039346656037ULL;
  20         static constexpr bool folded = false;
  21 };
  22
  23 template<>
  24 struct HashTraits<32, 5>
  25 {
  26         using HashType = uint32_t;
  27         using ResultType = uint32_t;
  28         static constexpr HashType prime = 16777619;
  29         static constexpr HashType offset = 2166136261U;
  30         static constexpr bool folded = false;
  31 };
  32
  33 template<unsigned N>
  34 struct HashTraits<N, 6>
  35 {
  36         using HashType = uint64_t;
  37         using ResultType = uint64_t;
  38         static constexpr bool folded = true;
  39 };
  40
  41 template<unsigned N>
  42 struct HashTraits<N, 5>
  43 {
  44         using HashType = uint32_t;
  45         using ResultType = uint32_t;
  46         static constexpr bool folded = true;
  47 };
  48
  49 template<unsigned N>
  50 struct HashTraits<N, 4>
  51 {
  52         using HashType = uint32_t;
  53         using ResultType = uint16_t;
  54         static constexpr bool folded = true;
  55 };
  56
  57 template<unsigned N>
  58 struct HashTraits<N, 3>
  59 {
  60         using HashType = uint32_t;
  61         using ResultType = uint8_t;
  62         static constexpr bool folded = true;
  63 };
  64
  65 /**
  66 Computes a single round of a hash, adding one byte of data.  N must be a native
  67 hash size.
  68 */
  69 template<unsigned N>
  70 typename HashTraits<N>::ResultType hash_round(typename HashTraits<N>::HashType result, uint8_t byte)
  71 {
  72         constexpr typename HashTraits<N>::HashType prime = HashTraits<N>::prime;
  73         return (result^byte)*prime;
  74 }
  75
  76 /**
  77 Updates a previously computed hash by adding bytes to it.  N must be a native
  78 hash size.
  79 */
  80 template<unsigned N>
  81 typename HashTraits<N>::ResultType hash_update(typename HashTraits<N>::HashType result, const void *data, std::size_t size)
  82 {
  83         const uint8_t *ptr = static_cast<const uint8_t *>(data);
  84         for(unsigned i=0; i<size; ++i)
  85                 result = hash_round<N>(result, *ptr++);
  86         return result;
  87 }
  88
  89 template<unsigned N>
  90 typename HashTraits<N>::ResultType hash_update(typename HashTraits<N>::HashType result, const std::string &str)
  91 { return hash_update<N>(result, str.data(), str.size()); }
  92
  93 // For some reason this causes an ambiguity error without the enable_if.
  94 template<unsigned N, typename T>
  95 typename std::enable_if<!std::is_same<T, std::string>::value, typename HashTraits<N>::ResultType>::type hash_update(typename HashTraits<N>::HashType result, const T &obj)
  96 { return hash_update<N>(result, &obj, sizeof(obj)); }
  97
  98 /**
  99 Manually folds a hash to a smaller size.
 100 */
 101 template<unsigned N, typename T>
 102 typename std::enable_if<N!=std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
 103 { return (hash>>N ^ hash) & ((T(1)<<N)-1); }
 104
 105 template<unsigned N, typename T>
 106 typename std::enable_if<N==std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
 107 { return hash; }
 108
 109 /**
 110 Computes an N-bit Fowler-Noll-Vo (FNV-1a) hash.  If N is not a native hash
 111 size, the next larger native hash is computed and XOR-folding is applied to
 112 the result.
 113
 114 http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
 115 http://www.isthe.com/chongo/tech/comp/fnv/index.html
 116 */
 117 template<unsigned N>
 118 typename HashTraits<N>::ResultType hash(const void *data, std::size_t size)
 119 {
 120         constexpr unsigned hash_bits = std::numeric_limits<typename HashTraits<N>::HashType>::digits;
 121         typename HashTraits<N>::HashType result = hash_update<hash_bits>(HashTraits<hash_bits>::offset, data, size);
 122         if(HashTraits<N>::folded)
 123                 result = hash_fold<N>(result);
 124         return result;
 125 }
 126
 127 /**
 128 Convenience function to compute an N-bit hash of a string.
 129 */
 130 template<unsigned N>
 131 typename HashTraits<N>::ResultType hash(const std::string &str)
 132 { return hash<N>(str.data(), str.size()); }
 133
 134 /**
 135 Convenience function to compute an N-bit hash of any object.  The entire object
 136 representation is hashed, including any padding bytes.
 137 */
 138 template<unsigned N, typename T>
 139 typename HashTraits<N>::ResultType hash(const T &obj)
 140 { return hash<N>(&obj, sizeof(obj)); }
 141
 142 } // namespace Msp
 143
 144 #endif