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      */
Mix(uint32_t hash)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      */
CheapMix(uint32_t hash)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>
operatorSkGoodHash61     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>
operatorSkGoodHash66     SK_WHEN(sizeof(K) != 4, uint32_t) operator()(const K& k) const {
67         return SkChecksum::Murmur3(&k, sizeof(K));
68     }
69 
operatorSkGoodHash70     uint32_t operator()(const SkString& k) const {
71         return SkChecksum::Murmur3(k.c_str(), k.size());
72     }
73 };
74 
75 #endif
76