1 | /* |
2 | * Copyright 2018-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 | #include <folly/Fingerprint.h> |
18 | |
19 | #include <folly/Portability.h> |
20 | #include <folly/Utility.h> |
21 | #include <folly/detail/FingerprintPolynomial.h> |
22 | |
23 | namespace folly { |
24 | namespace detail { |
25 | |
26 | namespace { |
27 | |
28 | // The polynomials below were generated by a separate program that requires the |
29 | // NTL (Number Theory Library) from http://www.shoup.net/ntl/ |
30 | // |
31 | // Briefly: randomly generate a polynomial of degree D, test for |
32 | // irreducibility, repeat until you find an irreducible polynomial |
33 | // (roughly 1/D of all polynomials of degree D are irreducible, so |
34 | // this will succeed in D/2 tries on average; D is small (64..128) so |
35 | // this simple method works well) |
36 | // |
37 | // DO NOT REPLACE THE POLYNOMIALS USED, EVER, as that would change the value |
38 | // of every single fingerprint in existence. |
39 | template <size_t Deg> |
40 | struct FingerprintTablePoly; |
41 | template <> |
42 | struct FingerprintTablePoly<63> { |
43 | static constexpr uint64_t data[1] = {0xbf3736b51869e9b7}; |
44 | }; |
45 | template <> |
46 | struct FingerprintTablePoly<95> { |
47 | static constexpr uint64_t data[2] = {0x51555cb0aa8d39c3, 0xb679ec3700000000}; |
48 | }; |
49 | template <> |
50 | struct FingerprintTablePoly<127> { |
51 | static constexpr uint64_t data[2] = {0xc91bff9b8768b51b, 0x8c5d5853bd77b0d3}; |
52 | }; |
53 | |
54 | template <typename D, size_t S0, size_t... I0> |
55 | constexpr auto copy_table(D const (&table)[S0], index_sequence<I0...>) { |
56 | using array = std::array<D, S0>; |
57 | return array{{table[I0]...}}; |
58 | } |
59 | template <typename D, size_t S0> |
60 | constexpr auto copy_table(D const (&table)[S0]) { |
61 | return copy_table(table, make_index_sequence<S0>{}); |
62 | } |
63 | |
64 | template <typename D, size_t S0, size_t S1, size_t... I0> |
65 | constexpr auto copy_table(D const (&table)[S0][S1], index_sequence<I0...>) { |
66 | using array = std::array<std::array<D, S1>, S0>; |
67 | return array{{copy_table(table[I0])...}}; |
68 | } |
69 | template <typename D, size_t S0, size_t S1> |
70 | constexpr auto copy_table(D const (&table)[S0][S1]) { |
71 | return copy_table(table, make_index_sequence<S0>{}); |
72 | } |
73 | |
74 | template <typename D, size_t S0, size_t S1, size_t S2, size_t... I0> |
75 | constexpr auto copy_table(D const (&table)[S0][S1][S2], index_sequence<I0...>) { |
76 | using array = std::array<std::array<std::array<D, S2>, S1>, S0>; |
77 | return array{{copy_table(table[I0])...}}; |
78 | } |
79 | template <typename D, size_t S0, size_t S1, size_t S2> |
80 | constexpr auto copy_table(D const (&table)[S0][S1][S2]) { |
81 | return copy_table(table, make_index_sequence<S0>{}); |
82 | } |
83 | |
84 | template <size_t Deg> |
85 | constexpr poly_table<Deg> make_poly_table() { |
86 | FingerprintPolynomial<Deg> poly(FingerprintTablePoly<Deg>::data); |
87 | uint64_t table[8][256][poly_size(Deg)] = {}; |
88 | // table[i][q] is Q(X) * X^(k+8*i) mod P(X), |
89 | // where k is the number of bits in the fingerprint (and deg(P)) and |
90 | // Q(X) = q7*X^7 + q6*X^6 + ... + q1*X + q0 is a degree-7 polyonomial |
91 | // whose coefficients are the bits of q. |
92 | for (uint16_t x = 0; x < 256; x++) { |
93 | FingerprintPolynomial<Deg> t; |
94 | t.setHigh8Bits(uint8_t(x)); |
95 | for (int i = 0; i < 8; i++) { |
96 | t.mulXkmod(8, poly); |
97 | for (size_t j = 0; j < poly_size(Deg); ++j) { |
98 | table[i][x][j] = t.get(j); |
99 | } |
100 | } |
101 | } |
102 | return copy_table(table); |
103 | } |
104 | |
105 | // private global variables marked constexpr to enforce that make_poly_table is |
106 | // really invoked at constexpr time, which would not otherwise be guaranteed |
107 | FOLLY_STORAGE_CONSTEXPR auto const poly_table_63 = make_poly_table<63>(); |
108 | FOLLY_STORAGE_CONSTEXPR auto const poly_table_95 = make_poly_table<95>(); |
109 | FOLLY_STORAGE_CONSTEXPR auto const poly_table_127 = make_poly_table<127>(); |
110 | |
111 | } // namespace |
112 | |
113 | template <> |
114 | const uint64_t FingerprintTable<64>::poly[poly_size(64)] = { |
115 | FingerprintTablePoly<63>::data[0]}; |
116 | template <> |
117 | const uint64_t FingerprintTable<96>::poly[poly_size(96)] = { |
118 | FingerprintTablePoly<95>::data[0], |
119 | FingerprintTablePoly<95>::data[1]}; |
120 | template <> |
121 | const uint64_t FingerprintTable<128>::poly[poly_size(128)] = { |
122 | FingerprintTablePoly<127>::data[0], |
123 | FingerprintTablePoly<127>::data[1]}; |
124 | |
125 | template <> |
126 | const poly_table<64> FingerprintTable<64>::table = poly_table_63; |
127 | template <> |
128 | const poly_table<96> FingerprintTable<96>::table = poly_table_95; |
129 | template <> |
130 | const poly_table<128> FingerprintTable<128>::table = poly_table_127; |
131 | |
132 | } // namespace detail |
133 | } // namespace folly |
134 | |