folly/detail/FingerprintPolynomial.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_BUILD_FINGERPRINTPOLYNOMIAL_H_
  18 #define FOLLY_BUILD_FINGERPRINTPOLYNOMIAL_H_
  19
  20 #include <cstdint>
  21
  22 namespace folly {
  23 namespace detail {
  24
  25 /**
  26  * Representation of a polynomial of degree DEG over GF(2) (that is,
  27  * with binary coefficients).
  28  *
  29  * Probably of no use outside of Fingerprint code; used by
  30  * GenerateFingerprintTables and the unittest.
  31  */
  32 template <int DEG>
  33 class FingerprintPolynomial {
  34  public:
  35   FingerprintPolynomial() {
  36     for (int i = 0; i < size(); i++) {
  37       val_[i] = 0;
  38     }
  39   }
  40
  41   explicit FingerprintPolynomial(const uint64_t* vals) {
  42     for (int i = 0; i < size(); i++) {
  43       val_[i] = vals[i];
  44     }
  45   }
  46
  47   void write(uint64_t* out) const {
  48     for (int i = 0; i < size(); i++) {
  49       out[i] = val_[i];
  50     }
  51   }
  52
  53   void add(const FingerprintPolynomial<DEG>& other) {
  54     for (int i = 0; i < size(); i++) {
  55       val_[i] ^= other.val_[i];
  56     }
  57   }
  58
  59   // Multiply by X.  The actual degree must be < DEG.
  60   void mulX() {
  61     CHECK_EQ(0, val_[0] & (1UL<<63));
  62     uint64_t b = 0;
  63     for (int i = size()-1; i >= 0; i--) {
  64       uint64_t nb = val_[i] >> 63;
  65       val_[i] = (val_[i] << 1) | b;
  66       b = nb;
  67     }
  68   }
  69
  70   // Compute (this * X) mod P(X), where P(X) is a monic polynomial of degree
  71   // DEG+1 (represented as a FingerprintPolynomial<DEG> object, with the
  72   // implicit coefficient of X^(DEG+1)==1)
  73   //
  74   // This is a bit tricky. If k=DEG+1:
  75   // Let P(X) = X^k + p_(k-1) * X^(k-1) + ... + p_1 * X + p_0
  76   // Let this = A(X) = a_(k-1) * X^(k-1) + ... + a_1 * X + a_0
  77   // Then:
  78   //   A(X) * X
  79   // = a_(k-1) * X^k + (a_(k-2) * X^(k-1) + ... + a_1 * X^2 + a_0 * X)
  80   // = a_(k-1) * X^k + (the binary representation of A, left shift by 1)
  81   //
  82   // if a_(k-1) = 0, we can ignore the first term.
  83   // if a_(k-1) = 1, then:
  84   //   X^k mod P(X)
  85   // = X^k - P(X)
  86   // = P(X) - X^k
  87   // = p_(k-1) * X^(k-1) + ... + p_1 * X + p_0
  88   // = exactly the binary representation passed in as an argument to this
  89   //   function!
  90   //
  91   // So A(X) * X mod P(X) is:
  92   //   the binary representation of A, left shift by 1,
  93   //   XOR p if a_(k-1) == 1
  94   void mulXmod(const FingerprintPolynomial<DEG>& p) {
  95     bool needXOR = (val_[0] & (1UL<<63));
  96     val_[0] &= ~(1UL<<63);
  97     mulX();
  98     if (needXOR) {
  99       add(p);
 100     }
 101   }
 102
 103   // Compute (this * X^k) mod P(X) by repeatedly multiplying by X (see above)
 104   void mulXkmod(int k, const FingerprintPolynomial<DEG>& p) {
 105     for (int i = 0; i < k; i++) {
 106       mulXmod(p);
 107     }
 108   }
 109
 110   // add X^k, where k <= DEG
 111   void addXk(int k) {
 112     DCHECK_GE(k, 0);
 113     DCHECK_LE(k, DEG);
 114     int word_offset = (DEG - k) / 64;
 115     int bit_offset = 63 - (DEG - k) % 64;
 116     val_[word_offset] ^= (1UL << bit_offset);
 117   }
 118
 119   // Set the highest 8 bits to val.
 120   // If val is interpreted as polynomial of degree 7, then this sets *this
 121   // to val * X^(DEG-7)
 122   void setHigh8Bits(uint8_t val) {
 123     val_[0] = ((uint64_t)val) << (64-8);
 124     for (int i = 1; i < size(); i++) {
 125       val_[i] = 0;
 126     }
 127   }
 128
 129   static int size() {
 130     return 1 + DEG/64;
 131   }
 132  private:
 133   // Internal representation: big endian
 134   // val_[0] contains the highest order coefficients, with bit 63 as the
 135   // highest order coefficient
 136   //
 137   // If DEG+1 is not a multiple of 64,  val_[size()-1] only uses the highest
 138   // order (DEG+1)%64 bits (the others are always 0)
 139   uint64_t val_[1 + DEG/64];
 140 };
 141
 142 }  // namespace detail
 143 }  // namespace folly
 144
 145 #endif /* FOLLY_BUILD_FINGERPRINTPOLYNOMIAL_H_ */
 146