180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2012 Google Inc. 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkChecksum_DEFINED 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkChecksum_DEFINED 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkChecksum : SkNoncopyable { 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Our Rotate and Mash helpers are meant to automatically do the right 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * thing depending if sizeof(uintptr_t) is 4 or 8. 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru enum { 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ROTR = 17, 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ROTL = sizeof(uintptr_t) * 8 - ROTR, 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru HALFBITS = sizeof(uintptr_t) * 4 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ((total >> ROTR) | (total << ROTL)) ^ value; 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Compute a 32-bit checksum for a given data block 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 33363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * WARNING: this algorithm is tuned for efficiency, not backward/forward 34363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * compatibility. It may change at any time, so a checksum generated with 35363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * one version of the Skia code may not match a checksum generated with 36363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * a different version of the Skia code. 37363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * @param data Memory address of the data block to be processed. Must be 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 32-bit aligned. 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * @param size Size of the data block in bytes. Must be a multiple of 4. 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * @return checksum result 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static uint32_t Compute(const uint32_t* data, size_t size) { 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(SkIsAlign4(size)); 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * We want to let the compiler use 32bit or 64bit addressing and math 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * so we use uintptr_t as our magic type. This makes the code a little 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * more obscure (we can't hard-code 32 or 64 anywhere, but have to use 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * sizeof()). 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uintptr_t result = 0; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(data); 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * count the number of quad element chunks. This takes into account 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * to compute how much to shift-down the size. 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t n4 = size / (sizeof(uintptr_t) << 2); 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (size_t i = 0; i < n4; ++i) { 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = Mash(result, *ptr++); 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = Mash(result, *ptr++); 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = Mash(result, *ptr++); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = Mash(result, *ptr++); 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size &= ((sizeof(uintptr_t) << 2) - 1); 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru data = reinterpret_cast<const uint32_t*>(ptr); 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const uint32_t* stop = data + (size >> 2); 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (data < stop) { 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = Mash(result, *data++); 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * smash us down to 32bits if we were 64. Note that when uintptr_t is 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 32bits, this code-path should go away, but I still got a warning 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * when I wrote 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * result ^= result >> 32; 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * define. 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (8 == sizeof(result)) { 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result ^= result >> HALFBITS; 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return static_cast<uint32_t>(result); 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 91