folly/Fingerprint.h

   1 /*
   2  * Copyright 2017 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 /**
  18  * Compute 64-, 96-, and 128-bit Rabin fingerprints, as described in
  19  * Michael O. Rabin (1981)
  20  *   Fingerprinting by Random Polynomials
  21  *   Center for Research in Computing Technology, Harvard University
  22  *   Tech Report TR-CSE-03-01
  23  *
  24  * The implementation follows the optimization described in
  25  * Andrei Z. Broder (1993)
  26  *   Some applications of Rabin's fingerprinting method
  27  *
  28  * extended for fingerprints larger than 64 bits, and modified to use
  29  * 64-bit instead of 32-bit integers for computation.
  30  *
  31  * The precomputed tables are in FingerprintTable.cpp, which is automatically
  32  * generated by ComputeFingerprintTable.cpp.
  33  *
  34  * Benchmarked on 10/13/2009 on a 2.5GHz quad-core Xeon L5420,
  35  * - Fingerprint<64>::update64() takes about 12ns
  36  * - Fingerprint<96>::update64() takes about 30ns
  37  * - Fingerprint<128>::update128() takes about 30ns
  38  * (unsurprisingly, Fingerprint<96> and Fingerprint<128> take the
  39  * same amount of time, as they both use 128-bit operations; the least
  40  * significant 32 bits of Fingerprint<96> will always be 0)
  41  *
  42  * @author Tudor Bosman (tudorb@facebook.com)
  43  */
  44
  45 #pragma once
  46
  47 #include <cstdint>
  48
  49 #include <folly/Range.h>
  50
  51 namespace folly {
  52
  53 namespace detail {
  54
  55 template <int BITS>
  56 struct FingerprintTable {
  57   static const uint64_t poly[1 + (BITS - 1) / 64];
  58   static const uint64_t table[8][256][1 + (BITS - 1) / 64];
  59 };
  60
  61 template <int BITS>
  62 const uint64_t FingerprintTable<BITS>::poly[1 + (BITS - 1) / 64] = {};
  63 template <int BITS>
  64 const uint64_t FingerprintTable<BITS>::table[8][256][1 + (BITS - 1) / 64] = {};
  65
  66 #ifndef _MSC_VER
  67 // MSVC 2015 can't handle these extern specialization declarations,
  68 // but they aren't needed for things to work right, so we just don't
  69 // declare them in the header for MSVC.
  70
  71 #define FOLLY_DECLARE_FINGERPRINT_TABLES(BITS)                      \
  72   template <>                                                       \
  73   const uint64_t FingerprintTable<BITS>::poly[1 + (BITS - 1) / 64]; \
  74   template <>                                                       \
  75   const uint64_t FingerprintTable<BITS>::table[8][256][1 + (BITS - 1) / 64]
  76
  77 FOLLY_DECLARE_FINGERPRINT_TABLES(64);
  78 FOLLY_DECLARE_FINGERPRINT_TABLES(96);
  79 FOLLY_DECLARE_FINGERPRINT_TABLES(128);
  80
  81 #undef FOLLY_DECLARE_FINGERPRINT_TABLES
  82 #endif
  83
  84 } // namespace detail
  85
  86 /**
  87  * Compute the Rabin fingerprint.
  88  *
  89  * TODO(tudorb): Extend this to allow removing values from the computed
  90  * fingerprint (so we can fingerprint a sliding window, as in the Rabin-Karp
  91  * string matching algorithm)
  92  *
  93  * update* methods return *this, so you can chain them together:
  94  * Fingerprint<96>().update8(x).update(str).update64(val).write(output);
  95  */
  96 template <int BITS>
  97 class Fingerprint {
  98  public:
  99   Fingerprint() {
 100     // Use a non-zero starting value. We'll use (1 << (BITS-1))
 101     fp_[0] = 1ULL << 63;
 102     for (int i = 1; i < size(); i++) {
 103       fp_[i] = 0;
 104     }
 105   }
 106
 107   Fingerprint& update8(uint8_t v) {
 108     uint8_t out = shlor8(v);
 109     xortab(detail::FingerprintTable<BITS>::table[0][out]);
 110     return *this;
 111   }
 112
 113   // update32 and update64 are convenience functions to update the fingerprint
 114   // with 4 and 8 bytes at a time.  They are faster than calling update8
 115   // in a loop.  They process the bytes in big-endian order.
 116   Fingerprint& update32(uint32_t v) {
 117     uint32_t out = shlor32(v);
 118     for (int i = 0; i < 4; i++) {
 119       xortab(detail::FingerprintTable<BITS>::table[i][out&0xff]);
 120       out >>= 8;
 121     }
 122     return *this;
 123   }
 124
 125   Fingerprint& update64(uint64_t v) {
 126     uint64_t out = shlor64(v);
 127     for (int i = 0; i < 8; i++) {
 128       xortab(detail::FingerprintTable<BITS>::table[i][out&0xff]);
 129       out >>= 8;
 130     }
 131     return *this;
 132   }
 133
 134   Fingerprint& update(StringPiece str) {
 135     // TODO(tudorb): We could be smart and do update64 or update32 if aligned
 136     for (auto c : str) {
 137       update8(uint8_t(c));
 138     }
 139     return *this;
 140   }
 141
 142   /**
 143    * Return the number of uint64s needed to hold the fingerprint value.
 144    */
 145   static int size() {
 146     return 1 + (BITS-1)/64;
 147   }
 148
 149   /**
 150    * Write the computed fingeprint to an array of size() uint64_t's.
 151    * For Fingerprint<64>,  size()==1; we write 64 bits in out[0]
 152    * For Fingerprint<96>,  size()==2; we write 64 bits in out[0] and
 153    *                                  the most significant 32 bits of out[1]
 154    * For Fingerprint<128>, size()==2; we write 64 bits in out[0] and
 155    *                                  64 bits in out[1].
 156    */
 157   void write(uint64_t* out) const {
 158     for (int i = 0; i < size(); i++) {
 159       out[i] = fp_[i];
 160     }
 161   }
 162
 163  private:
 164   // XOR the fingerprint with a value from one of the tables.
 165   void xortab(const uint64_t* tab) {
 166     for (int i = 0; i < size(); i++) {
 167       fp_[i] ^= tab[i];
 168     }
 169   }
 170
 171   // Helper functions: shift the fingerprint value left by 8/32/64 bits,
 172   // return the "out" value (the bits that were shifted out), and add "v"
 173   // in the bits on the right.
 174   uint8_t  shlor8(uint8_t v);
 175   uint32_t shlor32(uint32_t v);
 176   uint64_t shlor64(uint64_t v);
 177
 178   uint64_t fp_[1 + (BITS-1)/64];
 179 };
 180
 181 // Convenience functions
 182
 183 /**
 184  * Return the 64-bit Rabin fingerprint of a string.
 185  */
 186 inline uint64_t fingerprint64(StringPiece str) {
 187   uint64_t fp;
 188   Fingerprint<64>().update(str).write(&fp);
 189   return fp;
 190 }
 191
 192 /**
 193  * Compute the 96-bit Rabin fingerprint of a string.
 194  * Return the 64 most significant bits in *msb, and the 32 least significant
 195  * bits in *lsb.
 196  */
 197 inline void fingerprint96(StringPiece str,
 198                           uint64_t* msb, uint32_t* lsb) {
 199   uint64_t fp[2];
 200   Fingerprint<96>().update(str).write(fp);
 201   *msb = fp[0];
 202   *lsb = (uint32_t)(fp[1] >> 32);
 203 }
 204
 205 /**
 206  * Compute the 128-bit Rabin fingerprint of a string.
 207  * Return the 64 most significant bits in *msb, and the 64 least significant
 208  * bits in *lsb.
 209  */
 210 inline void fingerprint128(StringPiece str,
 211                            uint64_t* msb, uint64_t* lsb) {
 212   uint64_t fp[2];
 213   Fingerprint<128>().update(str).write(fp);
 214   *msb = fp[0];
 215   *lsb = fp[1];
 216 }
 217
 218
 219 template <>
 220 inline uint8_t Fingerprint<64>::shlor8(uint8_t v) {
 221   uint8_t out = (uint8_t)(fp_[0] >> 56);
 222   fp_[0] = (fp_[0] << 8) | ((uint64_t)v);
 223   return out;
 224 }
 225
 226 template <>
 227 inline uint32_t Fingerprint<64>::shlor32(uint32_t v) {
 228   uint32_t out = (uint32_t)(fp_[0] >> 32);
 229   fp_[0] = (fp_[0] << 32) | ((uint64_t)v);
 230   return out;
 231 }
 232
 233 template <>
 234 inline uint64_t Fingerprint<64>::shlor64(uint64_t v) {
 235   uint64_t out = fp_[0];
 236   fp_[0] = v;
 237   return out;
 238 }
 239
 240 template <>
 241 inline uint8_t Fingerprint<96>::shlor8(uint8_t v) {
 242   uint8_t out = (uint8_t)(fp_[0] >> 56);
 243   fp_[0] = (fp_[0] << 8) | (fp_[1] >> 56);
 244   fp_[1] = (fp_[1] << 8) | ((uint64_t)v << 32);
 245   return out;
 246 }
 247
 248 template <>
 249 inline uint32_t Fingerprint<96>::shlor32(uint32_t v) {
 250   uint32_t out = (uint32_t)(fp_[0] >> 32);
 251   fp_[0] = (fp_[0] << 32) | (fp_[1] >> 32);
 252   fp_[1] = ((uint64_t)v << 32);
 253   return out;
 254 }
 255
 256 template <>
 257 inline uint64_t Fingerprint<96>::shlor64(uint64_t v) {
 258   uint64_t out = fp_[0];
 259   fp_[0] = fp_[1] | (v >> 32);
 260   fp_[1] = v << 32;
 261   return out;
 262 }
 263
 264 template <>
 265 inline uint8_t Fingerprint<128>::shlor8(uint8_t v) {
 266   uint8_t out = (uint8_t)(fp_[0] >> 56);
 267   fp_[0] = (fp_[0] << 8) | (fp_[1] >> 56);
 268   fp_[1] = (fp_[1] << 8) | ((uint64_t)v);
 269   return out;
 270 }
 271
 272 template <>
 273 inline uint32_t Fingerprint<128>::shlor32(uint32_t v) {
 274   uint32_t out = (uint32_t)(fp_[0] >> 32);
 275   fp_[0] = (fp_[0] << 32) | (fp_[1] >> 32);
 276   fp_[1] = (fp_[1] << 32) | ((uint64_t)v);
 277   return out;
 278 }
 279
 280 template <>
 281 inline uint64_t Fingerprint<128>::shlor64(uint64_t v) {
 282   uint64_t out = fp_[0];
 283   fp_[0] = fp_[1];
 284   fp_[1] = v;
 285   return out;
 286 }
 287
 288 } // namespace folly