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