2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/Fingerprint.h>
19 #include <glog/logging.h>
20 #include <gtest/gtest.h>
22 #include <folly/detail/SlowFingerprint.h>
23 #include <folly/Benchmark.h>
25 using namespace folly;
26 using namespace folly::detail;
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;
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]);
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]);
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]);
52 TEST(Fingerprint, MultiByteUpdate) {
53 // Test that the multi-byte update functions (update32, update64,
54 // update(StringPiece)) produce the same result as calling update8
56 uint64_t val_a = 0xfaceb00cdeadbeefUL;
57 uint64_t val_b = 0x1234567890abcdefUL;
59 for (int i = 0; i < 8; i++) {
60 bytes[i] = (val_a >> (8*(7-i))) & 0xff;
62 for (int i = 0; i < 8; i++) {
63 bytes[i+8] = (val_b >> (8*(7-i))) & 0xff;
65 StringPiece sp((const char*)bytes, 16);
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))
75 for (int i = 0; i < 16; i++) {
80 Fingerprint<64>().update32(val_a >> 32).update32(val_a & 0xffffffff).
81 update32(val_b >> 32).update32(val_b & 0xffffffff).write(u32);
82 Fingerprint<64>().update64(val_a).update64(val_b).write(u64);
83 Fingerprint<64>().update(sp).write(usp);
84 uconv[0] = fingerprint64(sp);
86 EXPECT_EQ(u8[0], u32[0]);
87 EXPECT_EQ(u8[0], u64[0]);
88 EXPECT_EQ(u8[0], usp[0]);
89 EXPECT_EQ(u8[0], uconv[0]);
93 for (int i = 0; i < 16; i++) {
98 Fingerprint<96>().update32(val_a >> 32).update32(val_a & 0xffffffff).
99 update32(val_b >> 32).update32(val_b & 0xffffffff).write(u32);
100 Fingerprint<96>().update64(val_a).update64(val_b).write(u64);
101 Fingerprint<96>().update(sp).write(usp);
103 fingerprint96(sp, &(uconv[0]), &uconv_lsb);
104 uconv[1] = (uint64_t)uconv_lsb << 32;
106 EXPECT_EQ(u8[0], u32[0]);
107 EXPECT_EQ(u8[1], u32[1]);
108 EXPECT_EQ(u8[0], u64[0]);
109 EXPECT_EQ(u8[1], u64[1]);
110 EXPECT_EQ(u8[0], usp[0]);
111 EXPECT_EQ(u8[1], usp[1]);
112 EXPECT_EQ(u8[0], uconv[0]);
113 EXPECT_EQ(u8[1], uconv[1]);
117 for (int i = 0; i < 16; i++) {
118 fp.update8(bytes[i]);
122 Fingerprint<128>().update32(val_a >> 32).update32(val_a & 0xffffffff).
123 update32(val_b >> 32).update32(val_b & 0xffffffff).write(u32);
124 Fingerprint<128>().update64(val_a).update64(val_b).write(u64);
125 Fingerprint<128>().update(sp).write(usp);
126 fingerprint128(sp, &(uconv[0]), &(uconv[1]));
128 EXPECT_EQ(u8[0], u32[0]);
129 EXPECT_EQ(u8[1], u32[1]);
130 EXPECT_EQ(u8[0], u64[0]);
131 EXPECT_EQ(u8[1], u64[1]);
132 EXPECT_EQ(u8[0], usp[0]);
133 EXPECT_EQ(u8[1], usp[1]);
134 EXPECT_EQ(u8[0], uconv[0]);
135 EXPECT_EQ(u8[1], uconv[1]);
138 TEST(Fingerprint, Alignment) {
139 // Test that update() gives the same result regardless of string alignment
140 const char test_str[] = "hello world 12345";
141 int len = sizeof(test_str)-1;
142 std::unique_ptr<char[]> str(new char[len+8]);
144 SlowFingerprint<64>().update(StringPiece(test_str, len)).write(&ref_fp);
145 for (int i = 0; i < 8; i++) {
148 // Fill the string as !!hello??????
149 for (int j = 0; j < i; j++) {
153 for (int j = 0; j < len; j++) {
156 for (int j = i; j < 8; j++) {
161 Fingerprint<64>().update(StringPiece(q, len)).write(&fp);
162 EXPECT_EQ(ref_fp, fp);
166 int main(int argc, char *argv[]) {
167 testing::InitGoogleTest(&argc, argv);
168 gflags::ParseCommandLineFlags(&argc, &argv, true);
169 auto ret = RUN_ALL_TESTS();
171 folly::runBenchmarksOnFlag();