1 //===-- Fixed Point Converter for printf ------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H
10 #define LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H
11
12 #include "include/llvm-libc-macros/stdfix-macros.h"
13 #include "src/__support/CPP/string_view.h"
14 #include "src/__support/fixed_point/fx_bits.h"
15 #include "src/__support/fixed_point/fx_rep.h"
16 #include "src/__support/integer_to_string.h"
17 #include "src/__support/libc_assert.h"
18 #include "src/__support/macros/config.h"
19 #include "src/stdio/printf_core/converter_utils.h"
20 #include "src/stdio/printf_core/core_structs.h"
21 #include "src/stdio/printf_core/writer.h"
22
23 #include <inttypes.h>
24 #include <stddef.h>
25
26 namespace LIBC_NAMESPACE_DECL {
27 namespace printf_core {
28
29 // This is just for assertions. It will be compiled out for release builds.
const_ten_exp(uint32_t exponent)30 LIBC_INLINE constexpr uint32_t const_ten_exp(uint32_t exponent) {
31 uint32_t result = 1;
32 LIBC_ASSERT(exponent < 11);
33 for (uint32_t i = 0; i < exponent; ++i)
34 result *= 10;
35
36 return result;
37 }
38
39 #define READ_FX_BITS(TYPE) \
40 do { \
41 auto fixed_bits = fixed_point::FXBits<TYPE>( \
42 fixed_point::FXRep<TYPE>::StorageType(to_conv.conv_val_raw)); \
43 integral = fixed_bits.get_integral(); \
44 fractional = fixed_bits.get_fraction(); \
45 exponent = fixed_bits.get_exponent(); \
46 is_negative = fixed_bits.get_sign(); \
47 } while (false)
48
49 #define APPLY_FX_LENGTH_MODIFIER(LENGTH_MODIFIER) \
50 do { \
51 if (to_conv.conv_name == 'r') { \
52 READ_FX_BITS(LENGTH_MODIFIER fract); \
53 } else if (to_conv.conv_name == 'R') { \
54 READ_FX_BITS(unsigned LENGTH_MODIFIER fract); \
55 } else if (to_conv.conv_name == 'k') { \
56 READ_FX_BITS(LENGTH_MODIFIER accum); \
57 } else if (to_conv.conv_name == 'K') { \
58 READ_FX_BITS(unsigned LENGTH_MODIFIER accum); \
59 } else { \
60 LIBC_ASSERT(false && "Invalid conversion name passed to convert_fixed"); \
61 return FIXED_POINT_CONVERSION_ERROR; \
62 } \
63 } while (false)
64
convert_fixed(Writer * writer,const FormatSection & to_conv)65 LIBC_INLINE int convert_fixed(Writer *writer, const FormatSection &to_conv) {
66 // Long accum should be the largest type, so we can store all the smaller
67 // numbers in things sized for it.
68 using LARep = fixed_point::FXRep<unsigned long accum>;
69 using StorageType = LARep::StorageType;
70
71 // All of the letters will be defined relative to variable a, which will be
72 // the appropriate case based on the name of the conversion. This converts any
73 // conversion name into the letter 'a' with the appropriate case.
74 const char a = (to_conv.conv_name & 32) | 'A';
75 FormatFlags flags = to_conv.flags;
76
77 bool is_negative;
78 int exponent;
79 StorageType integral;
80 StorageType fractional;
81
82 // r = fract
83 // k = accum
84 // lowercase = signed
85 // uppercase = unsigned
86 // h = short
87 // l = long
88 // any other length modifier has no effect
89
90 if (to_conv.length_modifier == LengthModifier::h) {
91 APPLY_FX_LENGTH_MODIFIER(short);
92 } else if (to_conv.length_modifier == LengthModifier::l) {
93 APPLY_FX_LENGTH_MODIFIER(long);
94 } else {
95 APPLY_FX_LENGTH_MODIFIER();
96 }
97
98 LIBC_ASSERT(static_cast<size_t>(exponent) <=
99 (sizeof(StorageType) - sizeof(uint32_t)) * CHAR_BIT &&
100 "StorageType must be large enough to hold the fractional "
101 "component multiplied by a 32 bit number.");
102
103 // If to_conv doesn't specify a precision, the precision defaults to 6.
104 const size_t precision = to_conv.precision < 0 ? 6 : to_conv.precision;
105 bool has_decimal_point =
106 (precision > 0) || ((flags & FormatFlags::ALTERNATE_FORM) != 0);
107
108 // The number of non-zero digits below the decimal point for a negative power
109 // of 2 in base 10 is equal to the magnitude of the power of 2.
110
111 // A quick proof:
112 // Let p be any positive integer.
113 // Let e = 2^(-p)
114 // Let t be a positive integer such that e * 10^t is an integer.
115 // By definition: The smallest allowed value of t must be equal to the number
116 // of non-zero digits below the decimal point in e.
117 // If we evaluate e * 10^t we get the following:
118 // e * 10^t = 2^(-p) * 10*t = 2^(-p) * 2^t * 5^t = 5^t * 2^(t-p)
119 // For 5^t * 2^(t-p) to be an integer, both exponents must be non-negative,
120 // since 5 and 2 are coprime.
121 // The smallest value of t such that t-p is non-negative is p.
122 // Therefor, the number of non-zero digits below the decimal point for a given
123 // negative power of 2 "p" is equal to the value of p.
124
125 constexpr size_t MAX_FRACTION_DIGITS = LARep::FRACTION_LEN;
126
127 char fraction_digits[MAX_FRACTION_DIGITS];
128
129 size_t valid_fraction_digits = 0;
130
131 // TODO: Factor this part out
132 while (fractional > 0) {
133 uint32_t cur_digits = 0;
134 // 10^9 is used since it's the largest power of 10 that fits in a uint32_t
135 constexpr uint32_t TEN_EXP_NINE = 1000000000;
136 constexpr size_t DIGITS_PER_BLOCK = 9;
137
138 // Multiply by 10^9, then grab the digits above the decimal point, then
139 // clear those digits in fractional.
140 fractional = fractional * TEN_EXP_NINE;
141 cur_digits = static_cast<uint32_t>(fractional >> exponent);
142 fractional = fractional % (StorageType(1) << exponent);
143
144 // we add TEN_EXP_NINE to force leading zeroes to show up, then we skip the
145 // first digit in the loop.
146 const IntegerToString<uint32_t> cur_fractional_digits(cur_digits +
147 TEN_EXP_NINE);
148 for (size_t i = 0;
149 i < DIGITS_PER_BLOCK && valid_fraction_digits < MAX_FRACTION_DIGITS;
150 ++i, ++valid_fraction_digits)
151 fraction_digits[valid_fraction_digits] =
152 cur_fractional_digits.view()[i + 1];
153
154 if (valid_fraction_digits >= MAX_FRACTION_DIGITS) {
155 LIBC_ASSERT(fractional == 0 && "If the fraction digit buffer is full, "
156 "there should be no remaining digits.");
157 /*
158 A visual explanation of what this assert is checking:
159
160 32 digits (max for 32 bit fract)
161 +------------------------------++--+--- must be zero
162 | || |
163 123456789012345678901234567890120000
164 | || || || |
165 +-------++-------++-------++-------+
166 9 digit blocks
167 */
168 LIBC_ASSERT(cur_digits % const_ten_exp(
169 DIGITS_PER_BLOCK -
170 (MAX_FRACTION_DIGITS % DIGITS_PER_BLOCK)) ==
171 0 &&
172 "Digits after the MAX_FRACTION_DIGITS should all be zero.");
173 valid_fraction_digits = MAX_FRACTION_DIGITS;
174 }
175 }
176
177 if (precision < valid_fraction_digits) {
178 // Handle rounding. Just do round to nearest, tie to even since it's
179 // unspecified.
180 RoundDirection round;
181 char first_digit_after = fraction_digits[precision];
182 if (first_digit_after > '5') {
183 round = RoundDirection::Up;
184 } else if (first_digit_after < '5') {
185 round = RoundDirection::Down;
186 } else {
187 // first_digit_after == '5'
188 // need to check the remaining digits, but default to even.
189 round = RoundDirection::Even;
190 for (size_t cur_digit_index = precision + 1;
191 cur_digit_index + 1 < valid_fraction_digits; ++cur_digit_index) {
192 if (fraction_digits[cur_digit_index] != '0') {
193 round = RoundDirection::Up;
194 break;
195 }
196 }
197 }
198
199 // If we need to actually perform rounding, do so.
200 if (round == RoundDirection::Up || round == RoundDirection::Even) {
201 bool keep_rounding = true;
202 int digit_to_round = static_cast<int>(precision) - 1;
203 for (; digit_to_round >= 0 && keep_rounding; --digit_to_round) {
204 keep_rounding = false;
205 char cur_digit = fraction_digits[digit_to_round];
206 // if the digit should not be rounded up
207 if (round == RoundDirection::Even && ((cur_digit - '0') % 2) == 0) {
208 // break out of the loop
209 break;
210 }
211 fraction_digits[digit_to_round] += 1;
212
213 // if the digit was a 9, instead replace with a 0.
214 if (cur_digit == '9') {
215 fraction_digits[digit_to_round] = '0';
216 keep_rounding = true;
217 }
218 }
219
220 // if every digit below the decimal point was rounded up but we need to
221 // keep rounding
222 if (keep_rounding &&
223 (round == RoundDirection::Up ||
224 (round == RoundDirection::Even && ((integral % 2) == 1)))) {
225 // add one to the integral portion to round it up.
226 ++integral;
227 }
228 }
229
230 valid_fraction_digits = precision;
231 }
232
233 const IntegerToString<StorageType> integral_str(integral);
234
235 // these are signed to prevent underflow due to negative values. The
236 // eventual values will always be non-negative.
237 size_t trailing_zeroes = 0;
238 int padding;
239
240 // If the precision is greater than the actual result, pad with 0s
241 if (precision > valid_fraction_digits)
242 trailing_zeroes = precision - (valid_fraction_digits);
243
244 constexpr cpp::string_view DECIMAL_POINT(".");
245
246 char sign_char = 0;
247
248 // Check if the conv name is uppercase
249 if (a == 'A') {
250 // These flags are only for signed conversions, so this removes them if the
251 // conversion is unsigned.
252 flags = FormatFlags(flags &
253 ~(FormatFlags::FORCE_SIGN | FormatFlags::SPACE_PREFIX));
254 }
255
256 if (is_negative)
257 sign_char = '-';
258 else if ((flags & FormatFlags::FORCE_SIGN) == FormatFlags::FORCE_SIGN)
259 sign_char = '+'; // FORCE_SIGN has precedence over SPACE_PREFIX
260 else if ((flags & FormatFlags::SPACE_PREFIX) == FormatFlags::SPACE_PREFIX)
261 sign_char = ' ';
262
263 padding = static_cast<int>(to_conv.min_width - (sign_char > 0 ? 1 : 0) -
264 integral_str.size() -
265 static_cast<int>(has_decimal_point) -
266 valid_fraction_digits - trailing_zeroes);
267 if (padding < 0)
268 padding = 0;
269
270 if ((flags & FormatFlags::LEFT_JUSTIFIED) == FormatFlags::LEFT_JUSTIFIED) {
271 // The pattern is (sign), integral, (.), (fraction), (zeroes), (spaces)
272 if (sign_char > 0)
273 RET_IF_RESULT_NEGATIVE(writer->write(sign_char));
274 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view()));
275 if (has_decimal_point)
276 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT));
277 if (valid_fraction_digits > 0)
278 RET_IF_RESULT_NEGATIVE(
279 writer->write({fraction_digits, valid_fraction_digits}));
280 if (trailing_zeroes > 0)
281 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes));
282 if (padding > 0)
283 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding));
284 } else {
285 // The pattern is (spaces), (sign), (zeroes), integral, (.), (fraction),
286 // (zeroes)
287 if ((padding > 0) &&
288 ((flags & FormatFlags::LEADING_ZEROES) != FormatFlags::LEADING_ZEROES))
289 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding));
290 if (sign_char > 0)
291 RET_IF_RESULT_NEGATIVE(writer->write(sign_char));
292 if ((padding > 0) &&
293 ((flags & FormatFlags::LEADING_ZEROES) == FormatFlags::LEADING_ZEROES))
294 RET_IF_RESULT_NEGATIVE(writer->write('0', padding));
295 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view()));
296 if (has_decimal_point)
297 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT));
298 if (valid_fraction_digits > 0)
299 RET_IF_RESULT_NEGATIVE(
300 writer->write({fraction_digits, valid_fraction_digits}));
301 if (trailing_zeroes > 0)
302 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes));
303 }
304 return WRITE_OK;
305 }
306
307 } // namespace printf_core
308 } // namespace LIBC_NAMESPACE_DECL
309
310 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H
311