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 "SkString.h" 12 #include "SkTLogic.h" 13 #include "SkTypes.h" 14 15 class SkChecksum : SkNoncopyable { 16 public: 17 /** 18 * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you 19 * suspect its low bits aren't well mixed. 20 * 21 * This is the Murmur3 finalizer. 22 */ 23 static uint32_t Mix(uint32_t hash) { 24 hash ^= hash >> 16; 25 hash *= 0x85ebca6b; 26 hash ^= hash >> 13; 27 hash *= 0xc2b2ae35; 28 hash ^= hash >> 16; 29 return hash; 30 } 31 32 /** 33 * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you 34 * suspect its low bits aren't well mixed. 35 * 36 * This version is 2-lines cheaper than Mix, but seems to be sufficient for the font cache. 37 */ 38 static uint32_t CheapMix(uint32_t hash) { 39 hash ^= hash >> 16; 40 hash *= 0x85ebca6b; 41 hash ^= hash >> 16; 42 return hash; 43 } 44 45 /** 46 * Calculate 32-bit Murmur hash (murmur3). 47 * See en.wikipedia.org/wiki/MurmurHash. 48 * 49 * @param data Memory address of the data block to be processed. 50 * @param size Size of the data block in bytes. 51 * @param seed Initial hash seed. (optional) 52 * @return hash result 53 */ 54 static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0); 55 }; 56 57 // SkGoodHash should usually be your first choice in hashing data. 58 // It should be both reasonably fast and high quality. 59 struct SkGoodHash { 60 template <typename K> 61 SK_WHEN(sizeof(K) == 4, uint32_t) operator()(const K& k) const { 62 return SkChecksum::Mix(*(const uint32_t*)&k); 63 } 64 65 template <typename K> 66 SK_WHEN(sizeof(K) != 4, uint32_t) operator()(const K& k) const { 67 return SkChecksum::Murmur3(&k, sizeof(K)); 68 } 69 70 uint32_t operator()(const SkString& k) const { 71 return SkChecksum::Murmur3(k.c_str(), k.size()); 72 } 73 }; 74 75 #endif 76
