xref: /llvm-project/libc/utils/mathtools/ryu_tablegen.py (revision 69c0b2febe01108f50db6e8ed21cd8b2e6088caf) 
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
11This file is used to generate the tables of values in
12src/__support/ryu_constants.h and ryu_long_double constants.h. To use it, set
13the constants at the top of the file to the values you want to use for the Ryu
14algorithm, 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 brief
16explenation of each of the constants.
17
18BLOCK_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
23CONSTANT:
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
34IDX_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
43MID_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
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 = 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
75CONSTANT = 120
76IDX_SIZE = 128
77MANT_WIDTH = 112
78EXP_WIDTH = 15
79MID_INT_SIZE = 256 + 64
80
81MAX_EXP = 2 ** (EXP_WIDTH - 1)
82POSITIVE_ARR_SIZE = MAX_EXP // IDX_SIZE
83NEGATIVE_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) + 1
92    return result % MOD_SIZE
93
94
95# floor(10^(9*(-i)) * 2^(c_0 + (-e))) % (10^9 * 2^c_0)
96def 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.
108def ceil_log10_pow2(e):
109    return ((e * 0x13441350FBD) >> 42) + 1
110
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 - 1
115    ) // BLOCK_SIZE
116
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 outstr
129
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_blocks
138
139
140def 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
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 = 0
168
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] = 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    )
205