3ebb99bcd2ae12657b436704ab22f9777c27508a
[folly.git] / folly / build / GenerateFingerprintTables.cpp
1 /*
2  * Copyright 2014 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 #ifndef __STDC_FORMAT_MACROS
18 #define __STDC_FORMAT_MACROS 1
19 #endif
20
21 #include <cstdio>
22 #include <cinttypes>
23
24 #include <string>
25
26 #include <glog/logging.h>
27 #include <gflags/gflags.h>
28
29 #include <folly/Format.h>
30
31 #include <folly/detail/FingerprintPolynomial.h>
32
33 using namespace folly;
34 using namespace folly::detail;
35
36 // The defaults were generated by a separate program that requires the
37 // NTL (Number Theory Library) from http://www.shoup.net/ntl/
38 //
39 // Briefly: randomly generate a polynomial of degree D, test for
40 // irreducibility, repeat until you find an irreducible polynomial
41 // (roughly 1/D of all polynomials of degree D are irreducible, so
42 // this will succeed in D/2 tries on average; D is small (64..128) so
43 // this simple method works well)
44 //
45 // DO NOT REPLACE THE POLYNOMIALS USED, EVER, as that would change the value
46 // of every single fingerprint in existence.
47 DEFINE_int64(poly64, 0xbf3736b51869e9b7,
48              "Generate 64-bit tables using this polynomial");
49 DEFINE_int64(poly96_m, 0x51555cb0aa8d39c3,
50              "Generate 96-bit tables using this polynomial "
51              "(most significant 64 bits)");
52 DEFINE_int32(poly96_l, 0xb679ec37,
53              "Generate 96-bit tables using this polynomial "
54              "(least significant 32 bits)");
55 DEFINE_int64(poly128_m, 0xc91bff9b8768b51b,
56              "Generate 128-bit tables using this polynomial "
57              "(most significant 64 bits)");
58 DEFINE_int64(poly128_l, 0x8c5d5853bd77b0d3,
59              "Generate 128-bit tables using this polynomial "
60              "(least significant 64 bits)");
61 DEFINE_string(install_dir, ".",
62               "Direectory to place output files in");
63 DEFINE_string(fbcode_dir, "", "fbcode directory (ignored)");
64
65 namespace {
66
67 template <int DEG>
68 void computeTables(FILE* file, const FingerprintPolynomial<DEG>& poly) {
69   uint64_t table[8][256][FingerprintPolynomial<DEG>::size()];
70   // table[i][q] is Q(X) * X^(k+8*i) mod P(X),
71   // where k is the number of bits in the fingerprint (and deg(P)) and
72   // Q(X) = q7*X^7 + q6*X^6 + ... + q1*X + q0 is a degree-7 polyonomial
73   // whose coefficients are the bits of q.
74   for (int x = 0; x < 256; x++) {
75     FingerprintPolynomial<DEG> t;
76     t.setHigh8Bits(x);
77     for (int i = 0; i < 8; i++) {
78       t.mulXkmod(8, poly);
79       t.write(&(table[i][x][0]));
80     }
81   }
82
83   // Write the actual polynomial used; this isn't needed during fast
84   // fingerprint calculation, but it's useful for reference and unittesting.
85   uint64_t poly_val[FingerprintPolynomial<DEG>::size()];
86   poly.write(poly_val);
87   CHECK_ERR(fprintf(file,
88       "template <>\n"
89       "const uint64_t FingerprintTable<%d>::poly[%d] = {",
90       DEG+1, FingerprintPolynomial<DEG>::size()));
91   for (int j = 0; j < FingerprintPolynomial<DEG>::size(); j++) {
92     CHECK_ERR(fprintf(file, "%s%" PRIu64 "LU", j ? ", " : "", poly_val[j]));
93   }
94   CHECK_ERR(fprintf(file, "};\n\n"));
95
96   // Write the tables.
97   CHECK_ERR(fprintf(file,
98       "template <>\n"
99       "const uint64_t FingerprintTable<%d>::table[8][256][%d] = {\n",
100       DEG+1, FingerprintPolynomial<DEG>::size()));
101   for (int i = 0; i < 8; i++) {
102     CHECK_ERR(fprintf(file,
103         "  // Table %d"
104         "\n"
105         "  {\n", i));
106     for (int x = 0; x < 256; x++) {
107       CHECK_ERR(fprintf(file, "    {"));
108       for (int j = 0; j < FingerprintPolynomial<DEG>::size(); j++) {
109         CHECK_ERR(fprintf(
110           file, "%s%" PRIu64 "LU", (j ? ", " : ""), table[i][x][j]));
111       }
112       CHECK_ERR(fprintf(file, "},\n"));
113     }
114     CHECK_ERR(fprintf(file, "  },\n"));
115   }
116   CHECK_ERR(fprintf(file, "\n};\n\n"));
117 }
118
119 }  // namespace
120
121 int main(int argc, char *argv[]) {
122   google::ParseCommandLineFlags(&argc, &argv, true);
123   google::InitGoogleLogging(argv[0]);
124
125   std::string name = folly::format("{}/{}", FLAGS_install_dir,
126                                    "FingerprintTables.cpp").str();
127   FILE* file = fopen(name.c_str(), "w");
128   PCHECK(file);
129
130   CHECK_ERR(fprintf(file,
131       "/**\n"
132       " * Fingerprint tables for 64-, 96-, and 128-bit Rabin fingerprints.\n"
133       " *\n"
134       " * AUTOMATICALLY GENERATED.  DO NOT EDIT.\n"
135       " */\n"
136       "\n"
137       "#include <folly/Fingerprint.h>\n"
138       "\n"
139       "namespace folly {\n"
140       "namespace detail {\n"
141       "\n"));
142
143   FingerprintPolynomial<63> poly64((const uint64_t*)&FLAGS_poly64);
144   computeTables(file, poly64);
145
146   uint64_t poly96_val[2];
147   poly96_val[0] = (uint64_t)FLAGS_poly96_m;
148   poly96_val[1] = (uint64_t)FLAGS_poly96_l << 32;
149   FingerprintPolynomial<95> poly96(poly96_val);
150   computeTables(file, poly96);
151
152   uint64_t poly128_val[2];
153   poly128_val[0] = (uint64_t)FLAGS_poly128_m;
154   poly128_val[1] = (uint64_t)FLAGS_poly128_l;
155   FingerprintPolynomial<127> poly128(poly128_val);
156   computeTables(file, poly128);
157
158   CHECK_ERR(fprintf(file,
159       "}  // namespace detail\n"
160       "}  // namespace folly\n"));
161   CHECK_ERR(fclose(file));
162
163   return 0;
164 }