1 | /* |
2 | * Copyright 2012-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #include <folly/Fingerprint.h> |
18 | |
19 | #include <glog/logging.h> |
20 | |
21 | #include <folly/Benchmark.h> |
22 | #include <folly/detail/SlowFingerprint.h> |
23 | #include <folly/portability/GTest.h> |
24 | |
25 | using namespace folly; |
26 | using namespace folly::detail; |
27 | |
28 | TEST(Fingerprint, BroderOptimization) { |
29 | // Test that the Broder optimization produces the same result as |
30 | // the default (slow) implementation that processes one bit at a time. |
31 | uint64_t val_a = 0xfaceb00cdeadbeefUL; |
32 | uint64_t val_b = 0x1234567890abcdefUL; |
33 | |
34 | uint64_t slow[2]; |
35 | uint64_t fast[2]; |
36 | |
37 | SlowFingerprint<64>().update64(val_a).update64(val_b).write(slow); |
38 | Fingerprint<64>().update64(val_a).update64(val_b).write(fast); |
39 | EXPECT_EQ(slow[0], fast[0]); |
40 | |
41 | SlowFingerprint<96>().update64(val_a).update64(val_b).write(slow); |
42 | Fingerprint<96>().update64(val_a).update64(val_b).write(fast); |
43 | EXPECT_EQ(slow[0], fast[0]); |
44 | EXPECT_EQ(slow[1], fast[1]); |
45 | |
46 | SlowFingerprint<128>().update64(val_a).update64(val_b).write(slow); |
47 | Fingerprint<128>().update64(val_a).update64(val_b).write(fast); |
48 | EXPECT_EQ(slow[0], fast[0]); |
49 | EXPECT_EQ(slow[1], fast[1]); |
50 | } |
51 | |
52 | TEST(Fingerprint, MultiByteUpdate) { |
53 | // Test that the multi-byte update functions (update32, update64, |
54 | // update(StringPiece)) produce the same result as calling update8 |
55 | // repeatedly. |
56 | uint64_t val_a = 0xfaceb00cdeadbeefUL; |
57 | uint64_t val_b = 0x1234567890abcdefUL; |
58 | uint8_t bytes[16]; |
59 | for (int i = 0; i < 8; i++) { |
60 | bytes[i] = (val_a >> (8 * (7 - i))) & 0xff; |
61 | } |
62 | for (int i = 0; i < 8; i++) { |
63 | bytes[i + 8] = (val_b >> (8 * (7 - i))) & 0xff; |
64 | } |
65 | StringPiece sp((const char*)bytes, 16); |
66 | |
67 | uint64_t u8[2]; // updating 8 bits at a time |
68 | uint64_t u32[2]; // updating 32 bits at a time |
69 | uint64_t u64[2]; // updating 64 bits at a time |
70 | uint64_t usp[2]; // update(StringPiece) |
71 | uint64_t uconv[2]; // convenience function (fingerprint*(StringPiece)) |
72 | |
73 | { |
74 | Fingerprint<64> fp; |
75 | for (int i = 0; i < 16; i++) { |
76 | fp.update8(bytes[i]); |
77 | } |
78 | fp.write(u8); |
79 | } |
80 | Fingerprint<64>() |
81 | .update32(val_a >> 32) |
82 | .update32(val_a & 0xffffffff) |
83 | .update32(val_b >> 32) |
84 | .update32(val_b & 0xffffffff) |
85 | .write(u32); |
86 | Fingerprint<64>().update64(val_a).update64(val_b).write(u64); |
87 | Fingerprint<64>().update(sp).write(usp); |
88 | uconv[0] = fingerprint64(sp); |
89 | |
90 | EXPECT_EQ(u8[0], u32[0]); |
91 | EXPECT_EQ(u8[0], u64[0]); |
92 | EXPECT_EQ(u8[0], usp[0]); |
93 | EXPECT_EQ(u8[0], uconv[0]); |
94 | |
95 | { |
96 | Fingerprint<96> fp; |
97 | for (int i = 0; i < 16; i++) { |
98 | fp.update8(bytes[i]); |
99 | } |
100 | fp.write(u8); |
101 | } |
102 | Fingerprint<96>() |
103 | .update32(val_a >> 32) |
104 | .update32(val_a & 0xffffffff) |
105 | .update32(val_b >> 32) |
106 | .update32(val_b & 0xffffffff) |
107 | .write(u32); |
108 | Fingerprint<96>().update64(val_a).update64(val_b).write(u64); |
109 | Fingerprint<96>().update(sp).write(usp); |
110 | uint32_t uconv_lsb; |
111 | fingerprint96(sp, &(uconv[0]), &uconv_lsb); |
112 | uconv[1] = (uint64_t)uconv_lsb << 32; |
113 | |
114 | EXPECT_EQ(u8[0], u32[0]); |
115 | EXPECT_EQ(u8[1], u32[1]); |
116 | EXPECT_EQ(u8[0], u64[0]); |
117 | EXPECT_EQ(u8[1], u64[1]); |
118 | EXPECT_EQ(u8[0], usp[0]); |
119 | EXPECT_EQ(u8[1], usp[1]); |
120 | EXPECT_EQ(u8[0], uconv[0]); |
121 | EXPECT_EQ(u8[1], uconv[1]); |
122 | |
123 | { |
124 | Fingerprint<128> fp; |
125 | for (int i = 0; i < 16; i++) { |
126 | fp.update8(bytes[i]); |
127 | } |
128 | fp.write(u8); |
129 | } |
130 | Fingerprint<128>() |
131 | .update32(val_a >> 32) |
132 | .update32(val_a & 0xffffffff) |
133 | .update32(val_b >> 32) |
134 | .update32(val_b & 0xffffffff) |
135 | .write(u32); |
136 | Fingerprint<128>().update64(val_a).update64(val_b).write(u64); |
137 | Fingerprint<128>().update(sp).write(usp); |
138 | fingerprint128(sp, &(uconv[0]), &(uconv[1])); |
139 | |
140 | EXPECT_EQ(u8[0], u32[0]); |
141 | EXPECT_EQ(u8[1], u32[1]); |
142 | EXPECT_EQ(u8[0], u64[0]); |
143 | EXPECT_EQ(u8[1], u64[1]); |
144 | EXPECT_EQ(u8[0], usp[0]); |
145 | EXPECT_EQ(u8[1], usp[1]); |
146 | EXPECT_EQ(u8[0], uconv[0]); |
147 | EXPECT_EQ(u8[1], uconv[1]); |
148 | } |
149 | |
150 | TEST(Fingerprint, Alignment) { |
151 | // Test that update() gives the same result regardless of string alignment |
152 | const char test_str[] = "hello world 12345" ; |
153 | int len = sizeof(test_str) - 1; |
154 | std::unique_ptr<char[]> str(new char[len + 8]); |
155 | uint64_t ref_fp; |
156 | SlowFingerprint<64>().update(StringPiece(test_str, len)).write(&ref_fp); |
157 | for (int i = 0; i < 8; i++) { |
158 | char* p = str.get(); |
159 | char* q; |
160 | // Fill the string as !!hello?????? |
161 | for (int j = 0; j < i; j++) { |
162 | *p++ = '!'; |
163 | } |
164 | q = p; |
165 | for (int j = 0; j < len; j++) { |
166 | *p++ = test_str[j]; |
167 | } |
168 | for (int j = i; j < 8; j++) { |
169 | *p++ = '?'; |
170 | } |
171 | |
172 | uint64_t fp; |
173 | Fingerprint<64>().update(StringPiece(q, len)).write(&fp); |
174 | EXPECT_EQ(ref_fp, fp); |
175 | } |
176 | } |
177 | |
178 | int main(int argc, char* argv[]) { |
179 | testing::InitGoogleTest(&argc, argv); |
180 | gflags::ParseCommandLineFlags(&argc, &argv, true); |
181 | auto ret = RUN_ALL_TESTS(); |
182 | if (!ret) { |
183 | folly::runBenchmarksOnFlag(); |
184 | } |
185 | return ret; |
186 | } |
187 | |