folly/detail/SlowFingerprint.h

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