folly/test/FingerprintTest.cpp

   1 /*
   2  * Copyright 2014 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 #include <gtest/gtest.h>
  21
  22 #include <folly/detail/SlowFingerprint.h>
  23 #include <folly/Benchmark.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>().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);
  85
  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]);
  90
  91   {
  92     Fingerprint<96> fp;
  93     for (int i = 0; i < 16; i++) {
  94       fp.update8(bytes[i]);
  95     }
  96     fp.write(u8);
  97   }
  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);
 102   uint32_t uconv_lsb;
 103   fingerprint96(sp, &(uconv[0]), &uconv_lsb);
 104   uconv[1] = (uint64_t)uconv_lsb << 32;
 105
 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]);
 114
 115   {
 116     Fingerprint<128> fp;
 117     for (int i = 0; i < 16; i++) {
 118       fp.update8(bytes[i]);
 119     }
 120     fp.write(u8);
 121   }
 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]));
 127
 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]);
 136 }
 137
 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]);
 143   uint64_t ref_fp;
 144   SlowFingerprint<64>().update(StringPiece(test_str, len)).write(&ref_fp);
 145   for (int i = 0; i < 8; i++) {
 146     char* p = str.get();
 147     char* q;
 148     // Fill the string as !!hello??????
 149     for (int j = 0; j < i; j++) {
 150       *p++ = '!';
 151     }
 152     q = p;
 153     for (int j = 0; j < len; j++) {
 154       *p++ = test_str[j];
 155     }
 156     for (int j = i; j < 8; j++) {
 157       *p++ = '?';
 158     }
 159
 160     uint64_t fp;
 161     Fingerprint<64>().update(StringPiece(q, len)).write(&fp);
 162     EXPECT_EQ(ref_fp, fp);
 163   }
 164 }
 165
 166 int main(int argc, char *argv[]) {
 167   testing::InitGoogleTest(&argc, argv);
 168   gflags::ParseCommandLineFlags(&argc, &argv, true);
 169   auto ret = RUN_ALL_TESTS();
 170   if (!ret) {
 171     folly::runBenchmarksOnFlag();
 172   }
 173   return ret;
 174 }
 175