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 | |
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 | 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 | |