2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_BUILD_FINGERPRINTPOLYNOMIAL_H_
18 #define FOLLY_BUILD_FINGERPRINTPOLYNOMIAL_H_
26 * Representation of a polynomial of degree DEG over GF(2) (that is,
27 * with binary coefficients).
29 * Probably of no use outside of Fingerprint code; used by
30 * GenerateFingerprintTables and the unittest.
33 class FingerprintPolynomial {
35 FingerprintPolynomial() {
36 for (int i = 0; i < size(); i++) {
41 explicit FingerprintPolynomial(const uint64_t* vals) {
42 for (int i = 0; i < size(); i++) {
47 void write(uint64_t* out) const {
48 for (int i = 0; i < size(); i++) {
53 void add(const FingerprintPolynomial<DEG>& other) {
54 for (int i = 0; i < size(); i++) {
55 val_[i] ^= other.val_[i];
59 // Multiply by X. The actual degree must be < DEG.
61 CHECK_EQ(0, val_[0] & (1UL<<63));
63 for (int i = size()-1; i >= 0; i--) {
64 uint64_t nb = val_[i] >> 63;
65 val_[i] = (val_[i] << 1) | b;
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)
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
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)
82 // if a_(k-1) = 0, we can ignore the first term.
83 // if a_(k-1) = 1, then:
87 // = p_(k-1) * X^(k-1) + ... + p_1 * X + p_0
88 // = exactly the binary representation passed in as an argument to this
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);
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++) {
110 // add X^k, where k <= DEG
114 int word_offset = (DEG - k) / 64;
115 int bit_offset = 63 - (DEG - k) % 64;
116 val_[word_offset] ^= (1UL << bit_offset);
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++) {
133 // Internal representation: big endian
134 // val_[0] contains the highest order coefficients, with bit 63 as the
135 // highest order coefficient
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];
142 } // namespace detail
145 #endif /* FOLLY_BUILD_FINGERPRINTPOLYNOMIAL_H_ */