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