1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkChecksum_DEFINED 9 #define SkChecksum_DEFINED 10 11 #include "include/core/SkString.h" 12 #include "include/private/base/SkAPI.h" 13 14 #include <cstddef> 15 #include <cstdint> 16 #include <string> 17 #include <string_view> 18 #include <type_traits> 19 20 /** 21 * Our hash functions are exposed as SK_SPI (e.g. SkParagraph) 22 */ 23 namespace SkChecksum { 24 /** 25 * uint32_t -> uint32_t hash, useful for when you're about to truncate this hash but you 26 * suspect its low bits aren't well mixed. 27 * 28 * This is the Murmur3 finalizer. 29 */ Mix(uint32_t hash)30 static inline uint32_t Mix(uint32_t hash) { 31 hash ^= hash >> 16; 32 hash *= 0x85ebca6b; 33 hash ^= hash >> 13; 34 hash *= 0xc2b2ae35; 35 hash ^= hash >> 16; 36 return hash; 37 } 38 39 /** 40 * uint32_t -> uint32_t hash, useful for when you're about to truncate this hash but you 41 * suspect its low bits aren't well mixed. 42 * 43 * This version is 2-lines cheaper than Mix, but seems to be sufficient for the font cache. 44 */ CheapMix(uint32_t hash)45 static inline uint32_t CheapMix(uint32_t hash) { 46 hash ^= hash >> 16; 47 hash *= 0x85ebca6b; 48 hash ^= hash >> 16; 49 return hash; 50 } 51 52 /** 53 * This is a fast, high-quality 32-bit hash. We make no guarantees about this remaining stable 54 * over time, or being consistent across devices. 55 * 56 * For now, this is a 64-bit wyhash, truncated to 32-bits. 57 * See: https://github.com/wangyi-fudan/wyhash 58 */ 59 uint32_t SK_SPI Hash32(const void* data, size_t bytes, uint32_t seed = 0); 60 61 /** 62 * This is a fast, high-quality 64-bit hash. We make no guarantees about this remaining stable 63 * over time, or being consistent across devices. 64 * 65 * For now, this is a 64-bit wyhash. 66 * See: https://github.com/wangyi-fudan/wyhash 67 */ 68 uint64_t SK_SPI Hash64(const void* data, size_t bytes, uint64_t seed = 0); 69 70 } // namespace SkChecksum 71 72 // SkGoodHash should usually be your first choice in hashing data. 73 // It should be both reasonably fast and high quality. 74 struct SkGoodHash { 75 template <typename K> 76 std::enable_if_t<std::has_unique_object_representations<K>::value && sizeof(K) == 4, uint32_t> operatorSkGoodHash77 operator()(const K& k) const { 78 return SkChecksum::Mix(*(const uint32_t*)&k); 79 } 80 81 template <typename K> 82 std::enable_if_t<std::has_unique_object_representations<K>::value && sizeof(K) != 4, uint32_t> operatorSkGoodHash83 operator()(const K& k) const { 84 return SkChecksum::Hash32(&k, sizeof(K)); 85 } 86 operatorSkGoodHash87 uint32_t operator()(const SkString& k) const { 88 return SkChecksum::Hash32(k.c_str(), k.size()); 89 } 90 operatorSkGoodHash91 uint32_t operator()(const std::string& k) const { 92 return SkChecksum::Hash32(k.c_str(), k.size()); 93 } 94 operatorSkGoodHash95 uint32_t operator()(std::string_view k) const { 96 return SkChecksum::Hash32(k.data(), k.size()); 97 } 98 }; 99 100 // The default hashing behavior in SkGoodHash requires the type to have a unique object 101 // representation (i.e. all bits in contribute to its identity so can be hashed directly). This is 102 // false when a struct has padding for alignment (which can be avoided by using 103 // SK_BEGIN|END_REQUIRE_DENSE) or if the struct has floating point members since there are multiple 104 // bit representations for NaN. 105 // 106 // Often Skia code has externally removed the possibility of NaN so the bit representation of a 107 // non-NaN float will still hash correctly. SkForceDirectHash<K> produces the same as SkGoodHash 108 // for K's that do not satisfy std::has_unique_object_representation. It should be used sparingly 109 // and it's use may highlight design issues with the key's data that might warrant an explicitly 110 // implemented hash function. 111 template <typename K> 112 struct SkForceDirectHash { operatorSkForceDirectHash113 uint32_t operator()(const K& k) const { 114 return SkChecksum::Hash32(&k, sizeof(K)); 115 } 116 }; 117 118 #endif 119