folly/build/GenerateFingerprintTables.cpp

   1 /*
   2  * Copyright 2015 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   gflags::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 }