1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkChecksum.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,135 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkChecksum_DEFINED
1.12 +#define SkChecksum_DEFINED
1.13 +
1.14 +#include "SkTypes.h"
1.15 +
1.16 +/**
1.17 + * Computes a 32bit checksum from a blob of 32bit aligned data. This is meant
1.18 + * to be very very fast, as it is used internally by the font cache, in
1.19 + * conjuction with the entire raw key. This algorithm does not generate
1.20 + * unique values as well as others (e.g. MD5) but it performs much faster.
1.21 + * Skia's use cases can survive non-unique values (since the entire key is
1.22 + * always available). Clients should only be used in circumstances where speed
1.23 + * over uniqueness is at a premium.
1.24 + */
1.25 +class SkChecksum : SkNoncopyable {
1.26 +private:
1.27 + /*
1.28 + * Our Rotate and Mash helpers are meant to automatically do the right
1.29 + * thing depending if sizeof(uintptr_t) is 4 or 8.
1.30 + */
1.31 + enum {
1.32 + ROTR = 17,
1.33 + ROTL = sizeof(uintptr_t) * 8 - ROTR,
1.34 + HALFBITS = sizeof(uintptr_t) * 4
1.35 + };
1.36 +
1.37 + static inline uintptr_t Mash(uintptr_t total, uintptr_t value) {
1.38 + return ((total >> ROTR) | (total << ROTL)) ^ value;
1.39 + }
1.40 +
1.41 +public:
1.42 +
1.43 + /**
1.44 + * Calculate 32-bit Murmur hash (murmur3).
1.45 + * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash.
1.46 + * See en.wikipedia.org/wiki/MurmurHash.
1.47 + *
1.48 + * @param data Memory address of the data block to be processed. Must be 32-bit aligned.
1.49 + * @param size Size of the data block in bytes. Must be a multiple of 4.
1.50 + * @param seed Initial hash seed. (optional)
1.51 + * @return hash result
1.52 + */
1.53 + static uint32_t Murmur3(const uint32_t* data, size_t bytes, uint32_t seed=0) {
1.54 + SkASSERT(SkIsAlign4(bytes));
1.55 + const size_t words = bytes/4;
1.56 +
1.57 + uint32_t hash = seed;
1.58 + for (size_t i = 0; i < words; i++) {
1.59 + uint32_t k = data[i];
1.60 + k *= 0xcc9e2d51;
1.61 + k = (k << 15) | (k >> 17);
1.62 + k *= 0x1b873593;
1.63 +
1.64 + hash ^= k;
1.65 + hash = (hash << 13) | (hash >> 19);
1.66 + hash *= 5;
1.67 + hash += 0xe6546b64;
1.68 + }
1.69 + hash ^= bytes;
1.70 + hash ^= hash >> 16;
1.71 + hash *= 0x85ebca6b;
1.72 + hash ^= hash >> 13;
1.73 + hash *= 0xc2b2ae35;
1.74 + hash ^= hash >> 16;
1.75 + return hash;
1.76 + }
1.77 +
1.78 + /**
1.79 + * Compute a 32-bit checksum for a given data block
1.80 + *
1.81 + * WARNING: this algorithm is tuned for efficiency, not backward/forward
1.82 + * compatibility. It may change at any time, so a checksum generated with
1.83 + * one version of the Skia code may not match a checksum generated with
1.84 + * a different version of the Skia code.
1.85 + *
1.86 + * @param data Memory address of the data block to be processed. Must be
1.87 + * 32-bit aligned.
1.88 + * @param size Size of the data block in bytes. Must be a multiple of 4.
1.89 + * @return checksum result
1.90 + */
1.91 + static uint32_t Compute(const uint32_t* data, size_t size) {
1.92 + SkASSERT(SkIsAlign4(size));
1.93 +
1.94 + /*
1.95 + * We want to let the compiler use 32bit or 64bit addressing and math
1.96 + * so we use uintptr_t as our magic type. This makes the code a little
1.97 + * more obscure (we can't hard-code 32 or 64 anywhere, but have to use
1.98 + * sizeof()).
1.99 + */
1.100 + uintptr_t result = 0;
1.101 + const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data);
1.102 +
1.103 + /*
1.104 + * count the number of quad element chunks. This takes into account
1.105 + * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t)
1.106 + * to compute how much to shift-down the size.
1.107 + */
1.108 + size_t n4 = size / (sizeof(uintptr_t) << 2);
1.109 + for (size_t i = 0; i < n4; ++i) {
1.110 + result = Mash(result, *ptr++);
1.111 + result = Mash(result, *ptr++);
1.112 + result = Mash(result, *ptr++);
1.113 + result = Mash(result, *ptr++);
1.114 + }
1.115 + size &= ((sizeof(uintptr_t) << 2) - 1);
1.116 +
1.117 + data = reinterpret_cast<const uint32_t*>(ptr);
1.118 + const uint32_t* stop = data + (size >> 2);
1.119 + while (data < stop) {
1.120 + result = Mash(result, *data++);
1.121 + }
1.122 +
1.123 + /*
1.124 + * smash us down to 32bits if we were 64. Note that when uintptr_t is
1.125 + * 32bits, this code-path should go away, but I still got a warning
1.126 + * when I wrote
1.127 + * result ^= result >> 32;
1.128 + * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS
1.129 + * define.
1.130 + */
1.131 + if (8 == sizeof(result)) {
1.132 + result ^= result >> HALFBITS;
1.133 + }
1.134 + return static_cast<uint32_t>(result);
1.135 + }
1.136 +};
1.137 +
1.138 +#endif
