folly/build/generate_varint_tables.py

   1 #!/usr/bin/env python
   2 #
   3 # Generate tables for GroupVarint32
   4 # Copyright 2011 Facebook
   5 #
   6 # @author Tudor Bosman (tudorb@fb.com)
   7 #
   8 # Reference: http://www.stepanovpapers.com/CIKM_2011.pdf
   9 #
  10 # From 17 encoded bytes, we may use between 5 and 17 bytes to encode 4
  11 # integers.  The first byte is a key that indicates how many bytes each of
  12 # the 4 integers takes:
  13 #
  14 # bit 0..1: length-1 of first integer
  15 # bit 2..3: length-1 of second integer
  16 # bit 4..5: length-1 of third integer
  17 # bit 6..7: length-1 of fourth integer
  18 #
  19 # The value of the first byte is used as the index in a table which returns
  20 # a mask value for the SSSE3 PSHUFB instruction, which takes an XMM register
  21 # (16 bytes) and shuffles bytes from it into a destination XMM register
  22 # (optionally setting some of them to 0)
  23 #
  24 # For example, if the key has value 4, that means that the first integer
  25 # uses 1 byte, the second uses 2 bytes, the third and fourth use 1 byte each,
  26 # so we set the mask value so that
  27 #
  28 # r[0] = a[0]
  29 # r[1] = 0
  30 # r[2] = 0
  31 # r[3] = 0
  32 #
  33 # r[4] = a[1]
  34 # r[5] = a[2]
  35 # r[6] = 0
  36 # r[7] = 0
  37 #
  38 # r[8] = a[3]
  39 # r[9] = 0
  40 # r[10] = 0
  41 # r[11] = 0
  42 #
  43 # r[12] = a[4]
  44 # r[13] = 0
  45 # r[14] = 0
  46 # r[15] = 0
  47
  48 import os
  49 from optparse import OptionParser
  50
  51 OUTPUT_FILE = "GroupVarintTables.cpp"
  52
  53 def generate(f):
  54     f.write("""
  55 #include <folly/Portability.h>
  56
  57 #include <stdint.h>
  58
  59 #if (FOLLY_X64 || defined(__i386__)) && (FOLLY_SSE >= 2)
  60 #include <x86intrin.h>
  61 #endif
  62
  63 namespace folly {
  64 namespace detail {
  65
  66 #if (FOLLY_X64 || defined(__i386__)) && (FOLLY_SSE >= 2)
  67 extern const __m128i groupVarintSSEMasks[] = {
  68 """)
  69
  70     # Compute SSE masks
  71     for i in range(0, 256):
  72         offset = 0
  73         vals = [0, 0, 0, 0]
  74         for j in range(0, 4):
  75             d = 1 + ((i >> (2 * j)) & 3)
  76             # the j'th integer uses d bytes, consume them
  77             for k in range(0, d):
  78                 vals[j] |= offset << (8 * k)
  79                 offset += 1
  80             # set remaining bytes in result to 0
  81             # 0xff: set corresponding byte in result to 0
  82             for k in range(d, 4):
  83                 vals[j] |= 0xff << (8 * k)
  84         f.write("  {{static_cast<int64_t>(0x{1:08x}{0:08x}), "
  85             "static_cast<int64_t>(0x{3:08x}{2:08x})}},\n".format(*vals))
  86
  87     f.write("};\n"
  88         "#endif /*#if (FOLLY_X64 || defined(__i386__)) && (FOLLY_SSE >= 2)*/\n"
  89         "\n"
  90         "extern const uint8_t groupVarintLengths[] = {\n")
  91
  92     # Also compute total encoded lengths, including key byte
  93     for i in range(0, 256):
  94         offset = 1  # include key byte
  95         for j in range(0, 4):
  96             d = 1 + ((i >> (2 * j)) & 3)
  97             offset += d
  98         f.write("  {0},\n".format(offset))
  99
 100     f.write("""
 101 };
 102
 103 }  // namespace detail
 104 }  // namespace folly
 105 """)
 106
 107 def main():
 108     parser = OptionParser()
 109     parser.add_option("--install_dir", dest="install_dir", default=".",
 110                       help="write output to DIR", metavar="DIR")
 111     parser.add_option("--fbcode_dir")
 112     (options, args) = parser.parse_args()
 113     f = open(os.path.join(options.install_dir, OUTPUT_FILE), "w")
 114     generate(f)
 115     f.close()
 116
 117 if __name__ == "__main__":
 118     main()