folly/build/GenerateFingerprintTables.cpp

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