OLD | NEW |
1 | |
2 /* | 1 /* |
3 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
4 * | 3 * |
5 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 5 * found in the LICENSE file. |
7 */ | 6 */ |
8 #include "Test.h" | |
9 | 7 |
10 #include "SkChecksum.h" | 8 #include "SkChecksum.h" |
| 9 #include "SkRandom.h" |
| 10 #include "Test.h" |
| 11 #include "TestClassDef.h" |
11 | 12 |
12 // Word size that is large enough to hold results of any checksum type. | |
13 typedef uint64_t checksum_result; | |
14 | 13 |
15 namespace skiatest { | 14 // Murmur3 has an optional third seed argument, so we wrap it to fit a uniform t
ype. |
16 class ChecksumTestClass : public Test { | 15 static uint32_t murmur_noseed(const uint32_t* d, size_t l) { return SkChecksum::
Murmur3(d, l); } |
17 public: | 16 |
18 static Test* Factory(void*) {return SkNEW(ChecksumTestClass); } | 17 #define ASSERT(x) REPORTER_ASSERT(r, x) |
19 protected: | 18 |
20 virtual void onGetName(SkString* name) { name->set("Checksum"); } | 19 DEF_TEST(Checksum, r) { |
21 virtual void onRun(Reporter* reporter) { | 20 // Algorithms to test. They're currently all uint32_t(const uint32_t*, size
_t). |
22 this->fReporter = reporter; | 21 typedef uint32_t(*algorithmProc)(const uint32_t*, size_t); |
23 RunTest(); | 22 const algorithmProc kAlgorithms[] = { &SkChecksum::Compute, &murmur_noseed }
; |
| 23 |
| 24 // Put 128 random bytes into two identical buffers. Any multiple of 4 will
do. |
| 25 const size_t kBytes = SkAlign4(128); |
| 26 SkRandom rand; |
| 27 uint32_t data[kBytes/4], tweaked[kBytes/4]; |
| 28 for (size_t i = 0; i < SK_ARRAY_COUNT(tweaked); ++i) { |
| 29 data[i] = tweaked[i] = rand.nextU(); |
| 30 } |
| 31 |
| 32 // Test each algorithm. |
| 33 for (size_t i = 0; i < SK_ARRAY_COUNT(kAlgorithms); ++i) { |
| 34 const algorithmProc algorithm = kAlgorithms[i]; |
| 35 |
| 36 // Hash of NULL is always 0. |
| 37 ASSERT(algorithm(NULL, 0) == 0); |
| 38 |
| 39 const uint32_t hash = algorithm(data, kBytes); |
| 40 // Should be deterministic. |
| 41 ASSERT(hash == algorithm(data, kBytes)); |
| 42 |
| 43 // Changing any single element should change the hash. |
| 44 for (size_t j = 0; j < SK_ARRAY_COUNT(tweaked); ++j) { |
| 45 const uint32_t saved = tweaked[j]; |
| 46 tweaked[j] = rand.nextU(); |
| 47 const uint32_t tweakedHash = algorithm(tweaked, kBytes); |
| 48 ASSERT(tweakedHash != hash); |
| 49 ASSERT(tweakedHash == algorithm(tweaked, kBytes)); |
| 50 tweaked[j] = saved; |
24 } | 51 } |
25 private: | 52 } |
26 enum Algorithm { | |
27 kSkChecksum, | |
28 kMurmur3, | |
29 }; | |
30 | |
31 // Call Compute(data, size) on the appropriate checksum algorithm, | |
32 // depending on this->fWhichAlgorithm. | |
33 checksum_result ComputeChecksum(const char *data, size_t size) { | |
34 switch(fWhichAlgorithm) { | |
35 case kSkChecksum: | |
36 REPORTER_ASSERT_MESSAGE(fReporter, | |
37 reinterpret_cast<uintptr_t>(data) % 4 ==
0, | |
38 "test data pointer is not 32-bit aligned
"); | |
39 REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size), | |
40 "test data size is not 32-bit aligned"); | |
41 return SkChecksum::Compute(reinterpret_cast<const uint32_t *>(da
ta), size); | |
42 case kMurmur3: | |
43 REPORTER_ASSERT_MESSAGE(fReporter, | |
44 reinterpret_cast<uintptr_t>(data) % 4 ==
0, | |
45 "test data pointer is not 32-bit aligned
"); | |
46 REPORTER_ASSERT_MESSAGE(fReporter, SkIsAlign4(size), | |
47 "test data size is not 32-bit aligned"); | |
48 return SkChecksum::Murmur3(reinterpret_cast<const uint32_t *>(da
ta), size); | |
49 default: | |
50 SkString message("fWhichAlgorithm has unknown value "); | |
51 message.appendf("%d", fWhichAlgorithm); | |
52 fReporter->reportFailed(message); | |
53 } | |
54 // we never get here | |
55 return 0; | |
56 } | |
57 | |
58 // Confirm that the checksum algorithm (specified by fWhichAlgorithm) | |
59 // generates the same results if called twice over the same data. | |
60 void TestChecksumSelfConsistency(size_t buf_size) { | |
61 SkAutoMalloc storage(buf_size); | |
62 char* ptr = reinterpret_cast<char *>(storage.get()); | |
63 | |
64 REPORTER_ASSERT(fReporter, | |
65 GetTestDataChecksum(8, 0) == | |
66 GetTestDataChecksum(8, 0)); | |
67 REPORTER_ASSERT(fReporter, | |
68 GetTestDataChecksum(8, 0) != | |
69 GetTestDataChecksum(8, 1)); | |
70 | |
71 sk_bzero(ptr, buf_size); | |
72 checksum_result prev = 0; | |
73 | |
74 // assert that as we change values (from 0 to non-zero) in | |
75 // our buffer, we get a different value | |
76 for (size_t i = 0; i < buf_size; ++i) { | |
77 ptr[i] = (i & 0x7f) + 1; // need some non-zero value here | |
78 | |
79 // Try checksums of different-sized chunks, but always | |
80 // 32-bit aligned and big enough to contain all the | |
81 // nonzero bytes. (Remaining bytes will still be zero | |
82 // from the initial sk_bzero() call.) | |
83 size_t checksum_size = (((i/4)+1)*4); | |
84 REPORTER_ASSERT(fReporter, checksum_size <= buf_size); | |
85 | |
86 checksum_result curr = ComputeChecksum(ptr, checksum_size); | |
87 REPORTER_ASSERT(fReporter, prev != curr); | |
88 checksum_result again = ComputeChecksum(ptr, checksum_size); | |
89 REPORTER_ASSERT(fReporter, again == curr); | |
90 prev = curr; | |
91 } | |
92 } | |
93 | |
94 // Return the checksum of a buffer of bytes 'len' long. | |
95 // The pattern of values within the buffer will be consistent | |
96 // for every call, based on 'seed'. | |
97 checksum_result GetTestDataChecksum(size_t len, char seed=0) { | |
98 SkAutoMalloc storage(len); | |
99 char* start = reinterpret_cast<char *>(storage.get()); | |
100 char* ptr = start; | |
101 for (size_t i = 0; i < len; ++i) { | |
102 *ptr++ = ((seed+i) & 0x7f); | |
103 } | |
104 checksum_result result = ComputeChecksum(start, len); | |
105 return result; | |
106 } | |
107 | |
108 void RunTest() { | |
109 const Algorithm algorithms[] = { kSkChecksum, kMurmur3 }; | |
110 for (size_t i = 0; i < SK_ARRAY_COUNT(algorithms); i++) { | |
111 fWhichAlgorithm = algorithms[i]; | |
112 | |
113 // Test self-consistency of checksum algorithms. | |
114 TestChecksumSelfConsistency(128); | |
115 | |
116 // Test checksum results that should be consistent across | |
117 // versions and platforms. | |
118 REPORTER_ASSERT(fReporter, ComputeChecksum(NULL, 0) == 0); | |
119 | |
120 const bool colision1 = GetTestDataChecksum(128) == GetTestDataCh
ecksum(256); | |
121 const bool colision2 = GetTestDataChecksum(132) == GetTestDataCh
ecksum(260); | |
122 if (fWhichAlgorithm == kSkChecksum) { | |
123 // TODO: note the weakness exposed by these collisions... | |
124 // We need to improve the SkChecksum algorithm. | |
125 // We would prefer that these asserts FAIL! | |
126 // Filed as https://code.google.com/p/skia/issues/detail?id=
981 | |
127 // ('SkChecksum algorithm allows for way too many collisions
') | |
128 REPORTER_ASSERT(fReporter, colision1); | |
129 REPORTER_ASSERT(fReporter, colision2); | |
130 } else { | |
131 REPORTER_ASSERT(fReporter, !colision1); | |
132 REPORTER_ASSERT(fReporter, !colision2); | |
133 } | |
134 } | |
135 } | |
136 | |
137 Reporter* fReporter; | |
138 Algorithm fWhichAlgorithm; | |
139 }; | |
140 | |
141 static TestRegistry gReg(ChecksumTestClass::Factory); | |
142 } | 53 } |
OLD | NEW |