1363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 2363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger/* 3363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * Copyright 2012 Google Inc. 4363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * 5363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * Use of this source code is governed by a BSD-style license that can be 6363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger * found in the LICENSE file. 7363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger */ 8363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#include "Test.h" 9363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 10363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#include "SkChecksum.h" 11363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 12363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// Word size that is large enough to hold results of any checksum type. 13363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenbergertypedef uint64_t checksum_result; 14363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 15363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenbergernamespace skiatest { 16363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger class ChecksumTestClass : public Test { 17363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger public: 18363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger static Test* Factory(void*) {return SkNEW(ChecksumTestClass); } 19363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger protected: 20363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger virtual void onGetName(SkString* name) { name->set("Checksum"); } 21363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger virtual void onRun(Reporter* reporter) { 22363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger this->fReporter = reporter; 23363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger RunTest(); 24363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 25363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger private: 26363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger enum Algorithm { 2758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger kSkChecksum, 2858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger kMurmur3, 29363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger }; 30363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 31363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // Call Compute(data, size) on the appropriate checksum algorithm, 32363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // depending on this->fWhichAlgorithm. 33363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result ComputeChecksum(const char *data, size_t size) { 34363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger switch(fWhichAlgorithm) { 35363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger case kSkChecksum: 36363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT_MESSAGE(fReporter, 37363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger reinterpret_cast<uintptr_t>(data) % 4 == 0, 38363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger "test data pointer is not 32-bit aligned"); 39363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size), 40363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger "test data size is not 32-bit aligned"); 41363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger return SkChecksum::Compute(reinterpret_cast<const uint32_t *>(data), size); 4258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger case kMurmur3: 4358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT_MESSAGE(fReporter, 4458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger reinterpret_cast<uintptr_t>(data) % 4 == 0, 4558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger "test data pointer is not 32-bit aligned"); 4658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size), 4758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger "test data size is not 32-bit aligned"); 4858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return SkChecksum::Murmur3(reinterpret_cast<const uint32_t *>(data), size); 49363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger default: 50363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger SkString message("fWhichAlgorithm has unknown value "); 51363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger message.appendf("%d", fWhichAlgorithm); 52363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger fReporter->reportFailed(message); 53363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 54363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // we never get here 55363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger return 0; 56363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 57363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 58363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // Confirm that the checksum algorithm (specified by fWhichAlgorithm) 59363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // generates the same results if called twice over the same data. 60363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger void TestChecksumSelfConsistency(size_t buf_size) { 61363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger SkAutoMalloc storage(buf_size); 62363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger char* ptr = reinterpret_cast<char *>(storage.get()); 63363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 64363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT(fReporter, 65363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger GetTestDataChecksum(8, 0) == 66363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger GetTestDataChecksum(8, 0)); 67363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT(fReporter, 68363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger GetTestDataChecksum(8, 0) != 69363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger GetTestDataChecksum(8, 1)); 70363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 71363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger sk_bzero(ptr, buf_size); 72363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result prev = 0; 73363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 74363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // assert that as we change values (from 0 to non-zero) in 75363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // our buffer, we get a different value 76363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger for (size_t i = 0; i < buf_size; ++i) { 77363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger ptr[i] = (i & 0x7f) + 1; // need some non-zero value here 78363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 79363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // Try checksums of different-sized chunks, but always 80363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // 32-bit aligned and big enough to contain all the 81363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // nonzero bytes. (Remaining bytes will still be zero 82363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // from the initial sk_bzero() call.) 83363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger size_t checksum_size = (((i/4)+1)*4); 84363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT(fReporter, checksum_size <= buf_size); 85363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 86363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result curr = ComputeChecksum(ptr, checksum_size); 87363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT(fReporter, prev != curr); 88363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result again = ComputeChecksum(ptr, checksum_size); 89363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger REPORTER_ASSERT(fReporter, again == curr); 90363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger prev = curr; 91363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 92363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 93363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 94363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // Return the checksum of a buffer of bytes 'len' long. 95363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // The pattern of values within the buffer will be consistent 96363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger // for every call, based on 'seed'. 97363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result GetTestDataChecksum(size_t len, char seed=0) { 98363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger SkAutoMalloc storage(len); 99363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger char* start = reinterpret_cast<char *>(storage.get()); 100363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger char* ptr = start; 101363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger for (size_t i = 0; i < len; ++i) { 102363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger *ptr++ = ((seed+i) & 0x7f); 103363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 104363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger checksum_result result = ComputeChecksum(start, len); 105363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger return result; 106363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 107363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 108363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger void RunTest() { 10958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const Algorithm algorithms[] = { kSkChecksum, kMurmur3 }; 11058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger for (size_t i = 0; i < SK_ARRAY_COUNT(algorithms); i++) { 11158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fWhichAlgorithm = algorithms[i]; 11258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 11358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Test self-consistency of checksum algorithms. 11458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger TestChecksumSelfConsistency(128); 11558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 11658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Test checksum results that should be consistent across 11758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // versions and platforms. 11858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT(fReporter, ComputeChecksum(NULL, 0) == 0); 11958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 12058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const bool colision1 = GetTestDataChecksum(128) == GetTestDataChecksum(256); 12158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const bool colision2 = GetTestDataChecksum(132) == GetTestDataChecksum(260); 12258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fWhichAlgorithm == kSkChecksum) { 12358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // TODO: note the weakness exposed by these collisions... 12458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // We need to improve the SkChecksum algorithm. 12558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // We would prefer that these asserts FAIL! 12658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Filed as https://code.google.com/p/skia/issues/detail?id=981 12758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // ('SkChecksum algorithm allows for way too many collisions') 12858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT(fReporter, colision1); 12958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT(fReporter, colision2); 13058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else { 13158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT(fReporter, !colision1); 13258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger REPORTER_ASSERT(fReporter, !colision2); 13358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 13458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 135363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger } 136363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 137363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger Reporter* fReporter; 138363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger Algorithm fWhichAlgorithm; 139363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger }; 140363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 141363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger static TestRegistry gReg(ChecksumTestClass::Factory); 142363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger} 143