205 lines · python
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-exception7//8//===----------------------------------------------------------------------===//9 10 11This file is used to generate the tables of values in12src/__support/ryu_constants.h and ryu_long_double constants.h. To use it, set13the constants at the top of the file to the values you want to use for the Ryu14algorithm, then run this file. It will output the appropriate tables to stdout,15so it's recommended to pipe stdout to a file. The following is a brief16explenation of each of the constants.17 18BLOCK_SIZE:19 Default: 920 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 23CONSTANT:24 Default: 12025 Also known as c_0 and c_1 in the Ryu Printf paper and SHIFT_CONST in26 float_to_string.h.27 The table value is shifted left by this amount, and the final value is28 shifted right by this amount. It effectively makes the table value a fixed29 point number with the decimal point at the bit that is CONSTANT bits from30 the right.31 Higher values increase accuracy, but also require higher MID_INT_WIDTH32 values to fit the result.33 34IDX_SIZE:35 Default: 1636 By increasing the MOD_SIZE slightly we can significantly decrease the number37 of table entries we need.38 We can divide the number of table entries by IDX_SIZE, and multiply MOD_SIZE39 by 2^IDX_SIZE, and the math still works out.40 This optimization isn't mentioned in the original Ryu Printf paper but it41 saves a lot of space.42 43MID_INT_WIDTH:44 Default: 19245 This is the size of integer that the tables use. It's called mid int because46 it's the integer used in the middle of the calculation. There are large ints47 used to calculate the mid int table values, then those are used to calculate48 the small int final values.49 This must be divisible by 64 since each table entry is an array of 64 bit50 integers.51 If this is too small, then the results will get cut off. It should be at52 least CONSTANT + IDX_SIZE + log_2(10^9) to be able to fit the table values.53 54MANT_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 58EXP_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 64BLOCK_SIZE = 965 66 67# Values for double68# CONSTANT = 12069# IDX_SIZE = 1670# MANT_WIDTH = 5271# EXP_WIDTH = 1172# MID_INT_SIZE = 19273 74# Values for 128 bit float75CONSTANT = 12076IDX_SIZE = 12877MANT_WIDTH = 11278EXP_WIDTH = 1579MID_INT_SIZE = 256 + 6480 81MAX_EXP = 2 ** (EXP_WIDTH - 1)82POSITIVE_ARR_SIZE = MAX_EXP // IDX_SIZE83NEGATIVE_ARR_SIZE = (MAX_EXP // IDX_SIZE) + ((MANT_WIDTH + (IDX_SIZE - 1)) // IDX_SIZE)84MOD_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)88def 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) + 192 return result % MOD_SIZE93 94 95# floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)96def get_table_negative(exponent, i):97 result = 198 pow_of_ten = 10 ** (BLOCK_SIZE * i)99 shift_amount = CONSTANT - exponent100 if shift_amount < 0:101 result = pow_of_ten >> (-shift_amount)102 else:103 result = pow_of_ten << (shift_amount)104 return result % MOD_SIZE105 106 107# Returns floor(log_10(2^e)); requires 0 <= e <= 42039.108def ceil_log10_pow2(e):109 return ((e * 0x13441350FBD) >> 42) + 1110 111 112def length_for_num(idx, index_size=IDX_SIZE):113 return (114 ceil_log10_pow2(idx * index_size) + ceil_log10_pow2(MANT_WIDTH) + BLOCK_SIZE - 1115 ) // BLOCK_SIZE116 117 118def get_64bit_window(num, index):119 return (num >> (index * 64)) % (2**64)120 121 122def 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 outstr129 130 131def 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_blocks138 139 140def print_negative_table_for_idx(idx):141 i = 0142 min_block = -1143 table_val = 0144 MIN_USEFUL_VAL = 2 ** (CONSTANT - (MANT_WIDTH + 2))145 # Iterate through the zero blocks146 while table_val < MIN_USEFUL_VAL:147 i += 1148 table_val = get_table_negative((idx) * IDX_SIZE, i)149 else:150 i -= 1151 152 min_block = i153 154 # Iterate until another zero block is found155 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 += 1160 return i - min_block, min_block161 162 163positive_size_arr = [0] * (POSITIVE_ARR_SIZE + 1)164 165negative_size_arr = [0] * (NEGATIVE_ARR_SIZE + 1)166min_block_arr = [0] * (NEGATIVE_ARR_SIZE + 1)167acc = 0168 169if 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 )174else: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] = acc179 acc += num_size180 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_size192 negative_size_arr[idx + 1] = acc193 min_block_arr[idx] = min_block194 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 )205