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 "SkTypes.h"
12
13class SkChecksum : SkNoncopyable {
14private:
15    /*
16     *  Our Rotate and Mash helpers are meant to automatically do the right
17     *  thing depending if sizeof(uintptr_t) is 4 or 8.
18     */
19    enum {
20        ROTR = 17,
21        ROTL = sizeof(uintptr_t) * 8 - ROTR,
22        HALFBITS = sizeof(uintptr_t) * 4
23    };
24
25    static inline uintptr_t Mash(uintptr_t total, uintptr_t value) {
26        return ((total >> ROTR) | (total << ROTL)) ^ value;
27    }
28
29public:
30    /**
31     *  Compute a 32-bit checksum for a given data block
32     *
33     *  WARNING: this algorithm is tuned for efficiency, not backward/forward
34     *  compatibility.  It may change at any time, so a checksum generated with
35     *  one version of the Skia code may not match a checksum generated with
36     *  a different version of the Skia code.
37     *
38     *  @param data Memory address of the data block to be processed. Must be
39     *              32-bit aligned.
40     *  @param size Size of the data block in bytes. Must be a multiple of 4.
41     *  @return checksum result
42     */
43    static uint32_t Compute(const uint32_t* data, size_t size) {
44        SkASSERT(SkIsAlign4(size));
45
46        /*
47         *  We want to let the compiler use 32bit or 64bit addressing and math
48         *  so we use uintptr_t as our magic type. This makes the code a little
49         *  more obscure (we can't hard-code 32 or 64 anywhere, but have to use
50         *  sizeof()).
51         */
52        uintptr_t result = 0;
53        const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data);
54
55        /*
56         *  count the number of quad element chunks. This takes into account
57         *  if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t)
58         *  to compute how much to shift-down the size.
59         */
60        size_t n4 = size / (sizeof(uintptr_t) << 2);
61        for (size_t i = 0; i < n4; ++i) {
62            result = Mash(result, *ptr++);
63            result = Mash(result, *ptr++);
64            result = Mash(result, *ptr++);
65            result = Mash(result, *ptr++);
66        }
67        size &= ((sizeof(uintptr_t) << 2) - 1);
68
69        data = reinterpret_cast<const uint32_t*>(ptr);
70        const uint32_t* stop = data + (size >> 2);
71        while (data < stop) {
72            result = Mash(result, *data++);
73        }
74
75        /*
76         *  smash us down to 32bits if we were 64. Note that when uintptr_t is
77         *  32bits, this code-path should go away, but I still got a warning
78         *  when I wrote
79         *      result ^= result >> 32;
80         *  since >>32 is undefined for 32bit ints, hence the wacky HALFBITS
81         *  define.
82         */
83        if (8 == sizeof(result)) {
84            result ^= result >> HALFBITS;
85        }
86        return static_cast<uint32_t>(result);
87    }
88};
89
90#endif
91