folly/detail/SlowFingerprint.h

   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 #ifndef FOLLY_DETAIL_SLOWFINGERPRINT_H_
  18 #define FOLLY_DETAIL_SLOWFINGERPRINT_H_
  19
  20 #include <folly/Fingerprint.h>
  21 #include <folly/detail/FingerprintPolynomial.h>
  22 #include <folly/Range.h>
  23
  24 namespace folly {
  25 namespace detail {
  26
  27 /**
  28  * Slow, one-bit-at-a-time implementation of the Rabin fingerprint.
  29  *
  30  * This is useful as a reference implementation to test the Broder optimization
  31  * for correctness in the unittest; it's probably too slow for any real use.
  32  */
  33 template <int BITS>
  34 class SlowFingerprint {
  35  public:
  36   SlowFingerprint()
  37     : poly_(FingerprintTable<BITS>::poly) {
  38     // Use the same starting value as Fingerprint, (1 << (BITS-1))
  39     fp_.addXk(BITS-1);
  40   }
  41
  42   SlowFingerprint& update8(uint8_t v) {
  43     updateLSB(v, 8);
  44     return *this;
  45   }
  46
  47   SlowFingerprint& update32(uint32_t v) {
  48     updateLSB(v, 32);
  49     return *this;
  50   }
  51
  52   SlowFingerprint& update64(uint64_t v) {
  53     updateLSB(v, 64);
  54     return *this;
  55   }
  56
  57   SlowFingerprint& update(const folly::StringPiece str) {
  58     const char* p = str.start();
  59     for (int i = str.size(); i != 0; p++, i--) {
  60       update8(static_cast<uint8_t>(*p));
  61     }
  62     return *this;
  63   }
  64
  65   void write(uint64_t* out) const {
  66     fp_.write(out);
  67   }
  68
  69  private:
  70   void updateBit(bool bit) {
  71     fp_.mulXmod(poly_);
  72     if (bit) {
  73       fp_.addXk(0);
  74     }
  75   }
  76
  77   void updateLSB(uint64_t val, int bits) {
  78     val <<= (64-bits);
  79     for (; bits != 0; --bits) {
  80       updateBit(val & (1UL << 63));
  81       val <<= 1;
  82     }
  83   }
  84
  85   const FingerprintPolynomial<BITS-1> poly_;
  86   FingerprintPolynomial<BITS-1> fp_;
  87 };
  88
  89 }  // namespace detail
  90 }  // namespace folly
  91
  92 #endif /* FOLLY_DETAIL_SLOWFINGERPRINT_H_ */