folly/build/GenerateFingerprintTables.cpp

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