]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
7c673cae | 9 | #include "util/crc32c.h" |
f67539c2 | 10 | #include "test_util/testharness.h" |
11fdf7f2 | 11 | #include "util/coding.h" |
7c673cae | 12 | |
f67539c2 | 13 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
14 | namespace crc32c { |
15 | ||
16 | class CRC { }; | |
17 | ||
11fdf7f2 TL |
18 | |
19 | // Tests for 3-way crc32c algorithm. We need these tests because it uses | |
20 | // different lookup tables than the original Fast_CRC32 | |
21 | const unsigned int BUFFER_SIZE = 512 * 1024 * sizeof(uint64_t); | |
22 | char buffer[BUFFER_SIZE]; | |
23 | ||
24 | struct ExpectedResult { | |
25 | size_t offset; | |
26 | size_t length; | |
27 | uint32_t crc32c; | |
28 | }; | |
29 | ||
30 | ExpectedResult expectedResults[] = { | |
31 | // Zero-byte input | |
32 | { 0, 0, ~0U }, | |
33 | // Small aligned inputs to test special cases in SIMD implementations | |
34 | { 8, 1, 1543413366 }, | |
35 | { 8, 2, 523493126 }, | |
36 | { 8, 3, 1560427360 }, | |
37 | { 8, 4, 3422504776 }, | |
38 | { 8, 5, 447841138 }, | |
39 | { 8, 6, 3910050499 }, | |
40 | { 8, 7, 3346241981 }, | |
41 | // Small unaligned inputs | |
42 | { 9, 1, 3855826643 }, | |
43 | { 10, 2, 560880875 }, | |
44 | { 11, 3, 1479707779 }, | |
45 | { 12, 4, 2237687071 }, | |
46 | { 13, 5, 4063855784 }, | |
47 | { 14, 6, 2553454047 }, | |
48 | { 15, 7, 1349220140 }, | |
49 | // Larger inputs to test leftover chunks at the end of aligned blocks | |
50 | { 8, 8, 627613930 }, | |
51 | { 8, 9, 2105929409 }, | |
52 | { 8, 10, 2447068514 }, | |
53 | { 8, 11, 863807079 }, | |
54 | { 8, 12, 292050879 }, | |
55 | { 8, 13, 1411837737 }, | |
56 | { 8, 14, 2614515001 }, | |
57 | { 8, 15, 3579076296 }, | |
58 | { 8, 16, 2897079161 }, | |
59 | { 8, 17, 675168386 }, | |
60 | // // Much larger inputs | |
61 | { 0, BUFFER_SIZE, 2096790750 }, | |
62 | { 1, BUFFER_SIZE / 2, 3854797577 }, | |
63 | ||
64 | }; | |
65 | ||
7c673cae | 66 | TEST(CRC, StandardResults) { |
11fdf7f2 TL |
67 | |
68 | // Original Fast_CRC32 tests. | |
7c673cae FG |
69 | // From rfc3720 section B.4. |
70 | char buf[32]; | |
71 | ||
72 | memset(buf, 0, sizeof(buf)); | |
73 | ASSERT_EQ(0x8a9136aaU, Value(buf, sizeof(buf))); | |
74 | ||
75 | memset(buf, 0xff, sizeof(buf)); | |
76 | ASSERT_EQ(0x62a8ab43U, Value(buf, sizeof(buf))); | |
77 | ||
78 | for (int i = 0; i < 32; i++) { | |
11fdf7f2 | 79 | buf[i] = static_cast<char>(i); |
7c673cae FG |
80 | } |
81 | ASSERT_EQ(0x46dd794eU, Value(buf, sizeof(buf))); | |
82 | ||
83 | for (int i = 0; i < 32; i++) { | |
11fdf7f2 | 84 | buf[i] = static_cast<char>(31 - i); |
7c673cae FG |
85 | } |
86 | ASSERT_EQ(0x113fdb5cU, Value(buf, sizeof(buf))); | |
87 | ||
88 | unsigned char data[48] = { | |
89 | 0x01, 0xc0, 0x00, 0x00, | |
90 | 0x00, 0x00, 0x00, 0x00, | |
91 | 0x00, 0x00, 0x00, 0x00, | |
92 | 0x00, 0x00, 0x00, 0x00, | |
93 | 0x14, 0x00, 0x00, 0x00, | |
94 | 0x00, 0x00, 0x04, 0x00, | |
95 | 0x00, 0x00, 0x00, 0x14, | |
96 | 0x00, 0x00, 0x00, 0x18, | |
97 | 0x28, 0x00, 0x00, 0x00, | |
98 | 0x00, 0x00, 0x00, 0x00, | |
99 | 0x02, 0x00, 0x00, 0x00, | |
100 | 0x00, 0x00, 0x00, 0x00, | |
101 | }; | |
102 | ASSERT_EQ(0xd9963a56, Value(reinterpret_cast<char*>(data), sizeof(data))); | |
11fdf7f2 TL |
103 | |
104 | // 3-Way Crc32c tests ported from folly. | |
105 | // Test 1: single computation | |
106 | for (auto expected : expectedResults) { | |
107 | uint32_t result = Value(buffer + expected.offset, expected.length); | |
108 | EXPECT_EQ(~expected.crc32c, result); | |
109 | } | |
110 | ||
111 | // Test 2: stitching two computations | |
112 | for (auto expected : expectedResults) { | |
113 | size_t partialLength = expected.length / 2; | |
114 | uint32_t partialChecksum = Value(buffer + expected.offset, partialLength); | |
115 | uint32_t result = Extend(partialChecksum, | |
116 | buffer + expected.offset + partialLength, | |
117 | expected.length - partialLength); | |
118 | EXPECT_EQ(~expected.crc32c, result); | |
119 | } | |
120 | ||
7c673cae FG |
121 | } |
122 | ||
123 | TEST(CRC, Values) { | |
124 | ASSERT_NE(Value("a", 1), Value("foo", 3)); | |
125 | } | |
126 | ||
127 | TEST(CRC, Extend) { | |
128 | ASSERT_EQ(Value("hello world", 11), | |
129 | Extend(Value("hello ", 6), "world", 5)); | |
130 | } | |
131 | ||
132 | TEST(CRC, Mask) { | |
133 | uint32_t crc = Value("foo", 3); | |
134 | ASSERT_NE(crc, Mask(crc)); | |
135 | ASSERT_NE(crc, Mask(Mask(crc))); | |
136 | ASSERT_EQ(crc, Unmask(Mask(crc))); | |
137 | ASSERT_EQ(crc, Unmask(Unmask(Mask(Mask(crc))))); | |
138 | } | |
139 | ||
140 | } // namespace crc32c | |
f67539c2 | 141 | } // namespace ROCKSDB_NAMESPACE |
7c673cae | 142 | |
11fdf7f2 TL |
143 | // copied from folly |
144 | const uint64_t FNV_64_HASH_START = 14695981039346656037ULL; | |
145 | inline uint64_t fnv64_buf(const void* buf, | |
146 | size_t n, | |
147 | uint64_t hash = FNV_64_HASH_START) { | |
148 | // forcing signed char, since other platforms can use unsigned | |
149 | const signed char* char_buf = reinterpret_cast<const signed char*>(buf); | |
150 | ||
151 | for (size_t i = 0; i < n; ++i) { | |
152 | hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + | |
153 | (hash << 8) + (hash << 40); | |
154 | hash ^= char_buf[i]; | |
155 | } | |
156 | return hash; | |
157 | } | |
158 | ||
7c673cae FG |
159 | int main(int argc, char** argv) { |
160 | ::testing::InitGoogleTest(&argc, argv); | |
11fdf7f2 TL |
161 | |
162 | // Populate a buffer with a deterministic pattern | |
163 | // on which to compute checksums | |
164 | ||
f67539c2 TL |
165 | const uint8_t* src = (uint8_t*)ROCKSDB_NAMESPACE::crc32c::buffer; |
166 | uint64_t* dst = (uint64_t*)ROCKSDB_NAMESPACE::crc32c::buffer; | |
167 | const uint64_t* end = | |
168 | (const uint64_t*)(ROCKSDB_NAMESPACE::crc32c::buffer + | |
169 | ROCKSDB_NAMESPACE::crc32c::BUFFER_SIZE); | |
11fdf7f2 TL |
170 | *dst++ = 0; |
171 | while (dst < end) { | |
f67539c2 TL |
172 | ROCKSDB_NAMESPACE::EncodeFixed64( |
173 | reinterpret_cast<char*>(dst), | |
174 | fnv64_buf((const char*)src, sizeof(uint64_t))); | |
11fdf7f2 TL |
175 | dst++; |
176 | src += sizeof(uint64_t); | |
177 | } | |
178 | ||
7c673cae FG |
179 | return RUN_ALL_TESTS(); |
180 | } |