libc/utils/mathtools/ryu_tablegen.py

   1 """
   2 //===-- Table Generator for Ryu Printf ------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10
  11 This file is used to generate the tables of values in
  12 src/__support/ryu_constants.h and ryu_long_double constants.h. To use it, set
  13 the constants at the top of the file to the values you want to use for the Ryu
  14 algorithm, then run this file. It will output the appropriate tables to stdout,
  15 so it's recommended to pipe stdout to a file. The following is a brief
  16 explenation of each of the constants.
  17
  18 BLOCK_SIZE:
  19     Default: 9
  20     The number of digits that will be calculated together in a block.
  21     Don't touch this unless you really know what you're doing.
  22
  23 CONSTANT:
  24     Default: 120
  25     Also known as c_0 and c_1 in the Ryu Printf paper and SHIFT_CONST in
  26     float_to_string.h.
  27     The table value is shifted left by this amount, and the final value is
  28     shifted right by this amount. It effectively makes the table value a fixed
  29     point number with the decimal point at the bit that is CONSTANT bits from
  30     the right.
  31     Higher values increase accuracy, but also require higher MID_INT_WIDTH
  32     values to fit the result.
  33
  34 IDX_SIZE:
  35     Default: 16
  36     By increasing the MOD_SIZE slightly we can significantly decrease the number
  37     of table entries we need.
  38     We can divide the number of table entries by IDX_SIZE, and multiply MOD_SIZE
  39     by 2^IDX_SIZE, and the math still works out.
  40     This optimization isn't mentioned in the original Ryu Printf paper but it
  41     saves a lot of space.
  42
  43 MID_INT_WIDTH:
  44     Default: 192
  45     This is the size of integer that the tables use. It's called mid int because
  46     it's the integer used in the middle of the calculation. There are large ints
  47     used to calculate the mid int table values, then those are used to calculate
  48     the small int final values.
  49     This must be divisible by 64 since each table entry is an array of 64 bit
  50     integers.
  51     If this is too small, then the results will get cut off. It should be at
  52     least CONSTANT + IDX_SIZE + log_2(10^9) to be able to fit the table values.
  53
  54 MANT_WIDTH:
  55     The width of the widest float mantissa that this table will work for.
  56     This has a small effect on table size.
  57
  58 EXP_WIDTH:
  59     The width of the widest float exponent that this table will work for.
  60     This has a large effect on table size.
  61         Specifically, table size is proportional to the square of this number.
  62 """
  63
  64 BLOCK_SIZE = 9
  65
  66
  67 # Values for double
  68 # CONSTANT = 120
  69 # IDX_SIZE = 16
  70 # MANT_WIDTH = 52
  71 # EXP_WIDTH = 11
  72 # MID_INT_SIZE = 192
  73
  74 # Values for 128 bit float
  75 CONSTANT = 120
  76 IDX_SIZE = 128
  77 MANT_WIDTH = 112
  78 EXP_WIDTH = 15
  79 MID_INT_SIZE = 256 + 64
  80
  81 MAX_EXP = 2 ** (EXP_WIDTH - 1)
  82 POSITIVE_ARR_SIZE = MAX_EXP // IDX_SIZE
  83 NEGATIVE_ARR_SIZE = (MAX_EXP // IDX_SIZE) + ((MANT_WIDTH + (IDX_SIZE - 1)) // IDX_SIZE)
  84 MOD_SIZE = (10**BLOCK_SIZE) << (CONSTANT + (IDX_SIZE if IDX_SIZE > 1 else 0))
  85
  86
  87 # floor(5^(-9i) * 2^(e + c_1 - 9i) + 1) % (10^9 * 2^c_1)
  88 def get_table_positive(exponent, i):
  89     pow_of_two = 1 << (exponent + CONSTANT - (BLOCK_SIZE * i))
  90     pow_of_five = 5 ** (BLOCK_SIZE * i)
  91     result = (pow_of_two // pow_of_five) + 1
  92     return result % MOD_SIZE
  93
  94
  95 # floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
  96 def get_table_negative(exponent, i):
  97     result = 1
  98     pow_of_ten = 10 ** (BLOCK_SIZE * i)
  99     shift_amount = CONSTANT - exponent
 100     if shift_amount < 0:
 101         result = pow_of_ten >> (-shift_amount)
 102     else:
 103         result = pow_of_ten << (shift_amount)
 104     return result % MOD_SIZE
 105
 106
 107 # Returns floor(log_10(2^e)); requires 0 <= e <= 42039.
 108 def ceil_log10_pow2(e):
 109     return ((e * 0x13441350FBD) >> 42) + 1
 110
 111
 112 def length_for_num(idx, index_size=IDX_SIZE):
 113     return (
 114         ceil_log10_pow2(idx * index_size) + ceil_log10_pow2(MANT_WIDTH) + BLOCK_SIZE - 1
 115     ) // BLOCK_SIZE
 116
 117
 118 def get_64bit_window(num, index):
 119     return (num >> (index * 64)) % (2**64)
 120
 121
 122 def mid_int_to_str(num):
 123     outstr = "    {"
 124     outstr += str(get_64bit_window(num, 0)) + "u"
 125     for i in range(1, MID_INT_SIZE // 64):
 126         outstr += ", " + str(get_64bit_window(num, i)) + "u"
 127     outstr += "},"
 128     return outstr
 129
 130
 131 def print_positive_table_for_idx(idx):
 132     positive_blocks = length_for_num(idx)
 133     for i in range(positive_blocks):
 134         table_val = get_table_positive(idx * IDX_SIZE, i)
 135         # print(hex(table_val))
 136         print(mid_int_to_str(table_val))
 137     return positive_blocks
 138
 139
 140 def print_negative_table_for_idx(idx):
 141     i = 0
 142     min_block = -1
 143     table_val = 0
 144     MIN_USEFUL_VAL = 2 ** (CONSTANT - (MANT_WIDTH + 2))
 145     # Iterate through the zero blocks
 146     while table_val < MIN_USEFUL_VAL:
 147         i += 1
 148         table_val = get_table_negative((idx) * IDX_SIZE, i)
 149     else:
 150         i -= 1
 151
 152     min_block = i
 153
 154     # Iterate until another zero block is found
 155     while table_val >= MIN_USEFUL_VAL:
 156         table_val = get_table_negative((idx) * IDX_SIZE, i + 1)
 157         if table_val >= MIN_USEFUL_VAL:
 158             print(mid_int_to_str(table_val))
 159             i += 1
 160     return i - min_block, min_block
 161
 162
 163 positive_size_arr = [0] * (POSITIVE_ARR_SIZE + 1)
 164
 165 negative_size_arr = [0] * (NEGATIVE_ARR_SIZE + 1)
 166 min_block_arr = [0] * (NEGATIVE_ARR_SIZE + 1)
 167 acc = 0
 168
 169 if MOD_SIZE > (2**MID_INT_SIZE):
 170     print(
 171         "Mod size is too big for current MID_INT_SIZE by a factor of",
 172         MOD_SIZE // (2**MID_INT_SIZE),
 173     )
 174 else:
 175     print("static const uint64_t POW10_SPLIT[][" + str(MID_INT_SIZE // 64) + "] = {")
 176     for idx in range(0, POSITIVE_ARR_SIZE + 1):
 177         num_size = print_positive_table_for_idx(idx)
 178         positive_size_arr[idx] = acc
 179         acc += num_size
 180     print("};")
 181
 182     print(
 183         "static const uint32_t POW10_OFFSET_2[" + str(len(positive_size_arr)) + "] = {",
 184         str(positive_size_arr)[1:-2],
 185         "};",
 186     )
 187
 188     print("static const uint64_t POW10_SPLIT_2[][" + str(MID_INT_SIZE // 64) + "] = {")
 189     for idx in range(0, NEGATIVE_ARR_SIZE):
 190         num_size, min_block = print_negative_table_for_idx(idx)
 191         acc += num_size
 192         negative_size_arr[idx + 1] = acc
 193         min_block_arr[idx] = min_block
 194     print("};")
 195     print(
 196         "static const uint32_t POW10_OFFSET_2[" + str(len(negative_size_arr)) + "] = {",
 197         str(negative_size_arr)[1:-2],
 198         "};",
 199     )
 200     print(
 201         "static const uint16_t MIN_BLOCK_2[" + str(len(min_block_arr)) + "] = {",
 202         str(min_block_arr)[1:-2],
 203         "};",
 204     )