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
25using namespace folly;
26using namespace folly::detail;
27
28TEST(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
52TEST(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
150TEST(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
178int 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