1//===-- String to float conversion utils ------------------------*- 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// -----------------------------------------------------------------------------
10// **** WARNING ****
11// This file is shared with libc++. You should also be careful when adding
12// dependencies to this file, since it needs to build for all libc++ targets.
13// -----------------------------------------------------------------------------
14
15#ifndef LLVM_LIBC_SRC___SUPPORT_STR_TO_FLOAT_H
16#define LLVM_LIBC_SRC___SUPPORT_STR_TO_FLOAT_H
17
18#include "hdr/errno_macros.h" // For ERANGE
19#include "hdr/stdint_proxy.h"
20#include "src/__support/CPP/bit.h"
21#include "src/__support/CPP/limits.h"
22#include "src/__support/CPP/optional.h"
23#include "src/__support/CPP/string_view.h"
24#include "src/__support/FPUtil/FPBits.h"
25#include "src/__support/FPUtil/float128.h"
26#include "src/__support/FPUtil/rounding_mode.h"
27#include "src/__support/common.h"
28#include "src/__support/ctype_utils.h"
29#include "src/__support/detailed_powers_of_ten.h"
30#include "src/__support/high_precision_decimal.h"
31#include "src/__support/macros/attributes.h"
32#include "src/__support/macros/config.h"
33#include "src/__support/macros/null_check.h"
34#include "src/__support/macros/optimization.h"
35#include "src/__support/macros/properties/types.h"
36#include "src/__support/math_extras.h"
37#include "src/__support/str_to_integer.h"
38#include "src/__support/str_to_num_result.h"
39#include "src/__support/uint128.h"
40#include "src/__support/wctype_utils.h"
41
42namespace LIBC_NAMESPACE_DECL {
43namespace internal {
44
45// -----------------------------------------------------------------------------
46// **** WARNING ****
47// This interface is shared with libc++, if you change this interface you need
48// to update it in both libc and libc++.
49// -----------------------------------------------------------------------------
50template <class T> struct ExpandedFloat {
51 typename fputil::FPBits<T>::StorageType mantissa;
52 int32_t exponent;
53};
54
55// -----------------------------------------------------------------------------
56// **** WARNING ****
57// This interface is shared with libc++, if you change this interface you need
58// to update it in both libc and libc++.
59// -----------------------------------------------------------------------------
60template <class T> struct FloatConvertReturn {
61 ExpandedFloat<T> num = {0, 0};
62 int error = 0;
63};
64
65LIBC_INLINE uint64_t low64(const UInt128 &num) {
66 return static_cast<uint64_t>(num & 0xffffffffffffffff);
67}
68
69LIBC_INLINE uint64_t high64(const UInt128 &num) {
70 return static_cast<uint64_t>(num >> 64);
71}
72
73template <class T> LIBC_INLINE void set_implicit_bit(fputil::FPBits<T> &) {
74 return;
75}
76
77#if defined(LIBC_TYPES_LONG_DOUBLE_IS_X86_FLOAT80)
78template <>
79LIBC_INLINE void
80set_implicit_bit<long double>(fputil::FPBits<long double> &result) {
81 result.set_implicit_bit(result.get_biased_exponent() != 0);
82}
83#endif // LIBC_TYPES_LONG_DOUBLE_IS_X86_FLOAT80
84
85// This Eisel-Lemire implementation is based on the algorithm described in the
86// paper Number Parsing at a Gigabyte per Second, Software: Practice and
87// Experience 51 (8), 2021 (https://arxiv.org/abs/2101.11408), as well as the
88// description by Nigel Tao
89// (https://nigeltao.github.io/blog/2020/eisel-lemire.html) and the golang
90// implementation, also by Nigel Tao
91// (https://github.com/golang/go/blob/release-branch.go1.16/src/strconv/eisel_lemire.go#L25)
92// for some optimizations as well as handling 32 bit floats. This implementation
93// of Eisel-Lemire cannot handle anything longer than a double.
94template <class T, cpp::enable_if_t<sizeof(T) <= 8, int> = 0>
95LIBC_INLINE cpp::optional<ExpandedFloat<T>>
96eisel_lemire_impl(ExpandedFloat<T> init_num,
97 RoundDirection round = RoundDirection::Nearest) {
98 using FPBits = typename fputil::FPBits<T>;
99 using StorageType = typename FPBits::StorageType;
100
101 StorageType mantissa = init_num.mantissa;
102 int32_t exp_10 = init_num.exponent;
103
104 // Exp10 Range
105 if (exp_10 < DETAILED_POWERS_OF_TEN_MIN_EXP_10 ||
106 exp_10 > DETAILED_POWERS_OF_TEN_MAX_EXP_10) {
107 return cpp::nullopt;
108 }
109
110 // Normalization
111 uint32_t clz = static_cast<uint32_t>(cpp::countl_zero<StorageType>(mantissa));
112 mantissa <<= clz;
113
114 int32_t exp_2 = exp10_to_exp2(exp10: exp_10) + FPBits::STORAGE_LEN +
115 FPBits::EXP_BIAS - static_cast<int32_t>(clz);
116
117 // Multiplication
118 const uint64_t *power_of_ten =
119 DETAILED_POWERS_OF_TEN[exp_10 - DETAILED_POWERS_OF_TEN_MIN_EXP_10];
120
121 UInt128 first_approx =
122 static_cast<UInt128>(mantissa) * static_cast<UInt128>(power_of_ten[1]);
123
124 // Wider Approximation
125 UInt128 final_approx;
126 // The halfway constant is used to check if the bits that will be shifted away
127 // initially are all 1. For doubles this is 64 (bitstype size) - 52 (final
128 // mantissa size) - 3 (we shift away the last two bits separately for
129 // accuracy, and the most significant bit is ignored.) = 9 bits. Similarly,
130 // it's 6 bits for floats in this case.
131 const uint64_t halfway_constant =
132 (uint64_t(1) << (FPBits::STORAGE_LEN - (FPBits::FRACTION_LEN + 3))) - 1;
133 if ((high64(num: first_approx) & halfway_constant) == halfway_constant &&
134 low64(num: first_approx) + mantissa < mantissa) {
135 UInt128 low_bits =
136 static_cast<UInt128>(mantissa) * static_cast<UInt128>(power_of_ten[0]);
137 UInt128 second_approx =
138 first_approx + static_cast<UInt128>(high64(num: low_bits));
139
140 if ((high64(num: second_approx) & halfway_constant) == halfway_constant &&
141 low64(num: second_approx) + 1 == 0 &&
142 low64(num: low_bits) + mantissa < mantissa) {
143 return cpp::nullopt;
144 }
145 final_approx = second_approx;
146 } else {
147 final_approx = first_approx;
148 }
149
150 // Shifting to 54 bits for doubles and 25 bits for floats
151 StorageType msb = static_cast<StorageType>(high64(num: final_approx) >>
152 (FPBits::STORAGE_LEN - 1));
153 StorageType final_mantissa = static_cast<StorageType>(
154 high64(num: final_approx) >>
155 (msb + FPBits::STORAGE_LEN - (FPBits::FRACTION_LEN + 3)));
156 exp_2 -= static_cast<uint32_t>(1 ^ msb); // same as !msb
157
158 if (round == RoundDirection::Nearest) {
159 // Half-way ambiguity
160 if (low64(num: final_approx) == 0 &&
161 (high64(num: final_approx) & halfway_constant) == 0 &&
162 (final_mantissa & 3) == 1) {
163 return cpp::nullopt;
164 }
165
166 // Round to even.
167 final_mantissa += final_mantissa & 1;
168
169 } else if (round == RoundDirection::Up) {
170 // If any of the bits being rounded away are non-zero, then round up.
171 if (low64(num: final_approx) > 0 ||
172 (high64(num: final_approx) & halfway_constant) > 0) {
173 // Add two since the last current lowest bit is about to be shifted away.
174 final_mantissa += 2;
175 }
176 }
177 // else round down, which has no effect.
178
179 // From 54 to 53 bits for doubles and 25 to 24 bits for floats
180 final_mantissa >>= 1;
181 if ((final_mantissa >> (FPBits::FRACTION_LEN + 1)) > 0) {
182 final_mantissa >>= 1;
183 ++exp_2;
184 }
185
186 // The if block is equivalent to (but has fewer branches than):
187 // if exp_2 <= 0 || exp_2 >= 0x7FF { etc }
188 if (static_cast<uint32_t>(exp_2) - 1 >= (1 << FPBits::EXP_LEN) - 2) {
189 return cpp::nullopt;
190 }
191
192 ExpandedFloat<T> output;
193 output.mantissa = final_mantissa;
194 output.exponent = exp_2;
195 return output;
196}
197
198template <class T, cpp::enable_if_t<(sizeof(T) > 8), int> = 0>
199LIBC_INLINE cpp::optional<ExpandedFloat<T>>
200eisel_lemire_impl(ExpandedFloat<T> init_num,
201 RoundDirection round = RoundDirection::Nearest) {
202 using FPBits = typename fputil::FPBits<T>;
203 using StorageType = typename FPBits::StorageType;
204 UInt128 mantissa = init_num.mantissa;
205 int32_t exp_10 = init_num.exponent;
206
207 // Exp10 Range
208 // This doesn't reach very far into the range for long doubles, since it's
209 // sized for doubles and their 11 exponent bits, and not for long doubles and
210 // their 15 exponent bits (max exponent of ~300 for double vs ~5000 for long
211 // double). This is a known tradeoff, and was made because a proper long
212 // double table would be approximately 16 times larger. This would have
213 // significant memory and storage costs all the time to speed up a relatively
214 // uncommon path. In addition the exp10_to_exp2 function only approximates
215 // multiplying by log(10)/log(2), and that approximation may not be accurate
216 // out to the full long double range.
217 if (exp_10 < DETAILED_POWERS_OF_TEN_MIN_EXP_10 ||
218 exp_10 > DETAILED_POWERS_OF_TEN_MAX_EXP_10) {
219 return cpp::nullopt;
220 }
221
222 // Normalization
223 int32_t clz = static_cast<int32_t>(cpp::countl_zero(value: mantissa)) -
224 ((sizeof(UInt128) - sizeof(StorageType)) * CHAR_BIT);
225 mantissa <<= clz;
226
227 int32_t exp_2 =
228 exp10_to_exp2(exp10: exp_10) + FPBits::STORAGE_LEN + FPBits::EXP_BIAS - clz;
229
230 // Multiplication
231 const uint64_t *power_of_ten =
232 DETAILED_POWERS_OF_TEN[exp_10 - DETAILED_POWERS_OF_TEN_MIN_EXP_10];
233
234 // Since the input mantissa is more than 64 bits, we have to multiply with the
235 // full 128 bits of the power of ten to get an approximation with the same
236 // number of significant bits. This means that we only get the one
237 // approximation, and that approximation is 256 bits long.
238 UInt128 approx_upper = static_cast<UInt128>(high64(num: mantissa)) *
239 static_cast<UInt128>(power_of_ten[1]);
240
241 UInt128 approx_middle_a = static_cast<UInt128>(high64(num: mantissa)) *
242 static_cast<UInt128>(power_of_ten[0]);
243 UInt128 approx_middle_b = static_cast<UInt128>(low64(num: mantissa)) *
244 static_cast<UInt128>(power_of_ten[1]);
245
246 UInt128 approx_middle = approx_middle_a + approx_middle_b;
247
248 // Handle overflow in the middle
249 approx_upper += (approx_middle < approx_middle_a) ? UInt128(1) << 64 : 0;
250
251 UInt128 approx_lower = static_cast<UInt128>(low64(num: mantissa)) *
252 static_cast<UInt128>(power_of_ten[0]);
253
254 UInt128 final_approx_lower =
255 approx_lower + (static_cast<UInt128>(low64(num: approx_middle)) << 64);
256 UInt128 final_approx_upper = approx_upper + high64(num: approx_middle) +
257 (final_approx_lower < approx_lower ? 1 : 0);
258
259 // The halfway constant is used to check if the bits that will be shifted away
260 // initially are all 1. For 80 bit floats this is 128 (bitstype size) - 64
261 // (final mantissa size) - 3 (we shift away the last two bits separately for
262 // accuracy, and the most significant bit is ignored.) = 61 bits. Similarly,
263 // it's 12 bits for 128 bit floats in this case.
264 constexpr UInt128 HALFWAY_CONSTANT =
265 (UInt128(1) << (FPBits::STORAGE_LEN - (FPBits::FRACTION_LEN + 3))) - 1;
266
267 if ((final_approx_upper & HALFWAY_CONSTANT) == HALFWAY_CONSTANT &&
268 final_approx_lower + mantissa < mantissa) {
269 return cpp::nullopt;
270 }
271
272 // Shifting to 65 bits for 80 bit floats and 113 bits for 128 bit floats
273 uint32_t msb =
274 static_cast<uint32_t>(final_approx_upper >> (FPBits::STORAGE_LEN - 1));
275 UInt128 final_mantissa = final_approx_upper >> (msb + FPBits::STORAGE_LEN -
276 (FPBits::FRACTION_LEN + 3));
277 exp_2 -= static_cast<uint32_t>(1 ^ msb); // same as !msb
278
279 if (round == RoundDirection::Nearest) {
280 // Half-way ambiguity
281 if (final_approx_lower == 0 &&
282 (final_approx_upper & HALFWAY_CONSTANT) == 0 &&
283 (final_mantissa & 3) == 1) {
284 return cpp::nullopt;
285 }
286 // Round to even.
287 final_mantissa += final_mantissa & 1;
288
289 } else if (round == RoundDirection::Up) {
290 // If any of the bits being rounded away are non-zero, then round up.
291 if (final_approx_lower > 0 || (final_approx_upper & HALFWAY_CONSTANT) > 0) {
292 // Add two since the last current lowest bit is about to be shifted away.
293 final_mantissa += 2;
294 }
295 }
296 // else round down, which has no effect.
297
298 // From 65 to 64 bits for 80 bit floats and 113 to 112 bits for 128 bit
299 // floats
300 final_mantissa >>= 1;
301 if ((final_mantissa >> (FPBits::FRACTION_LEN + 1)) > 0) {
302 final_mantissa >>= 1;
303 ++exp_2;
304 }
305
306 // The if block is equivalent to (but has fewer branches than):
307 // if exp_2 <= 0 || exp_2 >= MANTISSA_MAX { etc }
308 if (exp_2 - 1 >= (1 << FPBits::EXP_LEN) - 2) {
309 return cpp::nullopt;
310 }
311
312 ExpandedFloat<T> output;
313 output.mantissa = static_cast<StorageType>(final_mantissa);
314 output.exponent = exp_2;
315 return output;
316}
317
318template <class T>
319LIBC_INLINE cpp::optional<ExpandedFloat<T>>
320eisel_lemire(ExpandedFloat<T> init_num,
321 RoundDirection round = RoundDirection::Nearest) {
322 // TODO: Re-enable eisel-lemire for long double is double double once it's
323 // properly supported.
324#if defined(LIBC_TYPES_LONG_DOUBLE_IS_DOUBLE_DOUBLE)
325 if constexpr (cpp::is_same_v<T, long double>)
326 return cpp::nullopt;
327 else
328#endif // LIBC_TYPES_LONG_DOUBLE_IS_DOUBLE_DOUBLE
329 return eisel_lemire_impl(init_num, round);
330}
331
332// The nth item in POWERS_OF_TWO represents the greatest power of two less than
333// 10^n. This tells us how much we can safely shift without overshooting.
334constexpr uint8_t POWERS_OF_TWO[19] = {
335 0, 3, 6, 9, 13, 16, 19, 23, 26, 29, 33, 36, 39, 43, 46, 49, 53, 56, 59,
336};
337constexpr int32_t NUM_POWERS_OF_TWO =
338 sizeof(POWERS_OF_TWO) / sizeof(POWERS_OF_TWO[0]);
339
340// Takes a mantissa and base 10 exponent and converts it into its closest
341// floating point type T equivalent. This is the fallback algorithm used when
342// the Eisel-Lemire algorithm fails, it's slower but more accurate. It's based
343// on the Simple Decimal Conversion algorithm by Nigel Tao, described at this
344// link: https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html
345template <typename T, typename CharType>
346LIBC_INLINE FloatConvertReturn<T> simple_decimal_conversion(
347 const CharType *__restrict numStart,
348 const size_t num_len = cpp::numeric_limits<size_t>::max(),
349 RoundDirection round = RoundDirection::Nearest) {
350 using FPBits = typename fputil::FPBits<T>;
351 using StorageType = typename FPBits::StorageType;
352
353 int32_t exp_2 = 0;
354 HighPrecisionDecimal hpd = HighPrecisionDecimal(numStart, num_len);
355
356 FloatConvertReturn<T> output;
357
358 if (hpd.get_num_digits() == 0) {
359 output.num = {0, 0};
360 return output;
361 }
362
363 // exp10_to_exp2 is only valid for inputs below 646 456 636, but
364 // HighPrecisionDecimal clamps the decimal point to 1 << 30. Decimal points at
365 // or beyond that limit are far outside the range of any float type, so they
366 // are handled explicitly instead of letting exp10_to_exp2 wrap around.
367 constexpr int32_t EXP10_TO_EXP2_LIMIT = 646456636;
368
369 // If the exponent is too large and can't be represented in this size of
370 // float, return inf.
371 if (hpd.get_decimal_point() > 0 &&
372 (hpd.get_decimal_point() - 1 >= EXP10_TO_EXP2_LIMIT ||
373 exp10_to_exp2(exp10: hpd.get_decimal_point() - 1) > FPBits::EXP_BIAS)) {
374 output.num = {0, fputil::FPBits<T>::MAX_BIASED_EXPONENT};
375 output.error = ERANGE;
376 return output;
377 }
378 // If the exponent is too small even for a subnormal, return 0.
379 if (hpd.get_decimal_point() < 0 &&
380 (-hpd.get_decimal_point() >= EXP10_TO_EXP2_LIMIT ||
381 exp10_to_exp2(exp10: -hpd.get_decimal_point()) >
382 (FPBits::EXP_BIAS + static_cast<int32_t>(FPBits::FRACTION_LEN)))) {
383 output.num = {0, 0};
384 output.error = ERANGE;
385 return output;
386 }
387
388 // Right shift until the number is smaller than 1.
389 while (hpd.get_decimal_point() > 0) {
390 int32_t shift_amount = 0;
391 if (hpd.get_decimal_point() >= NUM_POWERS_OF_TWO) {
392 shift_amount = 60;
393 } else {
394 shift_amount = POWERS_OF_TWO[hpd.get_decimal_point()];
395 }
396 // The bounds checks above keep exp_2 small, but stay well defined if they
397 // are ever loosened.
398 if (LIBC_UNLIKELY(add_overflow(exp_2, shift_amount, exp_2))) {
399 output.num = {0, FPBits::MAX_BIASED_EXPONENT};
400 output.error = ERANGE;
401 return output;
402 }
403 hpd.shift(shift_amount: -shift_amount);
404 }
405
406 // Left shift until the number is between 1/2 and 1
407 while (hpd.get_decimal_point() < 0 ||
408 (hpd.get_decimal_point() == 0 && hpd.get_digits()[0] < 5)) {
409 int32_t shift_amount = 0;
410
411 if (-hpd.get_decimal_point() >= NUM_POWERS_OF_TWO) {
412 shift_amount = 60;
413 } else if (hpd.get_decimal_point() != 0) {
414 shift_amount = POWERS_OF_TWO[-hpd.get_decimal_point()];
415 } else { // This handles the case of the number being between .1 and .5
416 shift_amount = 1;
417 }
418 if (LIBC_UNLIKELY(sub_overflow(exp_2, shift_amount, exp_2))) {
419 output.num = {0, 0};
420 output.error = ERANGE;
421 return output;
422 }
423 hpd.shift(shift_amount);
424 }
425
426 // Left shift once so that the number is between 1 and 2
427 --exp_2;
428 hpd.shift(shift_amount: 1);
429
430 // Get the biased exponent
431 exp_2 += FPBits::EXP_BIAS;
432
433 // Handle the exponent being too large (and return inf).
434 if (exp_2 >= FPBits::MAX_BIASED_EXPONENT) {
435 output.num = {0, FPBits::MAX_BIASED_EXPONENT};
436 output.error = ERANGE;
437 return output;
438 }
439
440 // Shift left to fill the mantissa
441 hpd.shift(shift_amount: FPBits::FRACTION_LEN);
442 StorageType final_mantissa = hpd.round_to_integer_type<StorageType>();
443
444 // Handle subnormals
445 if (exp_2 <= 0) {
446 // Shift right until there is a valid exponent, and once more to compensate
447 // for the left shift to get it between 1 and 2.
448 hpd.shift(shift_amount: exp_2 - 1);
449 exp_2 = 0;
450 final_mantissa = hpd.round_to_integer_type<StorageType>(round);
451
452 // Check if by shifting right we've caused this to round to a normal number.
453 if ((final_mantissa >> FPBits::FRACTION_LEN) != 0) {
454 ++exp_2;
455 }
456 }
457
458 // Check if rounding added a bit, and shift down if that's the case.
459 if (final_mantissa == StorageType(2) << FPBits::FRACTION_LEN) {
460 final_mantissa >>= 1;
461 ++exp_2;
462
463 // Check if this rounding causes exp_2 to go out of range and make the
464 // result INF. If this is the case, then finalMantissa and exp_2 are already
465 // the correct values for an INF result.
466 if (exp_2 >= FPBits::MAX_BIASED_EXPONENT) {
467 output.error = ERANGE;
468 }
469 }
470
471 if (exp_2 == 0) {
472 output.error = ERANGE;
473 }
474
475 output.num = {final_mantissa, exp_2};
476 return output;
477}
478
479// This class is used for templating the constants for Clinger's Fast Path,
480// described as a method of approximation in
481// Clinger WD. How to Read Floating Point Numbers Accurately. SIGPLAN Not 1990
482// Jun;25(6):92–101. https://doi.org/10.1145/93548.93557.
483// As well as the additions by Gay that extend the useful range by the number of
484// exact digits stored by the float type, described in
485// Gay DM, Correctly rounded binary-decimal and decimal-binary conversions;
486// 1990. AT&T Bell Laboratories Numerical Analysis Manuscript 90-10.
487template <typename T> class ClingerConsts;
488
489template <> class ClingerConsts<float> {
490public:
491 static constexpr float POWERS_OF_TEN_ARRAY[] = {1e0, 1e1, 1e2, 1e3, 1e4, 1e5,
492 1e6, 1e7, 1e8, 1e9, 1e10};
493 static constexpr int32_t EXACT_POWERS_OF_TEN = 10;
494 static constexpr int32_t DIGITS_IN_MANTISSA = 7;
495 static constexpr float MAX_EXACT_INT = 16777215.0;
496};
497
498template <> class ClingerConsts<double> {
499public:
500 static constexpr double POWERS_OF_TEN_ARRAY[] = {
501 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11,
502 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
503 static constexpr int32_t EXACT_POWERS_OF_TEN = 22;
504 static constexpr int32_t DIGITS_IN_MANTISSA = 15;
505 static constexpr double MAX_EXACT_INT = 9007199254740991.0;
506};
507
508#if defined(LIBC_TYPES_LONG_DOUBLE_IS_FLOAT64)
509template <> class ClingerConsts<long double> {
510public:
511 static constexpr long double POWERS_OF_TEN_ARRAY[] = {
512 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11,
513 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
514 static constexpr int32_t EXACT_POWERS_OF_TEN =
515 ClingerConsts<double>::EXACT_POWERS_OF_TEN;
516 static constexpr int32_t DIGITS_IN_MANTISSA =
517 ClingerConsts<double>::DIGITS_IN_MANTISSA;
518 static constexpr long double MAX_EXACT_INT =
519 ClingerConsts<double>::MAX_EXACT_INT;
520};
521#elif defined(LIBC_TYPES_LONG_DOUBLE_IS_X86_FLOAT80)
522template <> class ClingerConsts<long double> {
523public:
524 static constexpr long double POWERS_OF_TEN_ARRAY[] = {
525 1e0L, 1e1L, 1e2L, 1e3L, 1e4L, 1e5L, 1e6L, 1e7L, 1e8L, 1e9L,
526 1e10L, 1e11L, 1e12L, 1e13L, 1e14L, 1e15L, 1e16L, 1e17L, 1e18L, 1e19L,
527 1e20L, 1e21L, 1e22L, 1e23L, 1e24L, 1e25L, 1e26L, 1e27L};
528 static constexpr int32_t EXACT_POWERS_OF_TEN = 27;
529 static constexpr int32_t DIGITS_IN_MANTISSA = 21;
530 static constexpr long double MAX_EXACT_INT = 18446744073709551615.0L;
531};
532#elif defined(LIBC_TYPES_LONG_DOUBLE_IS_FLOAT128)
533template <> class ClingerConsts<long double> {
534public:
535 static constexpr long double POWERS_OF_TEN_ARRAY[] = {
536 1e0L, 1e1L, 1e2L, 1e3L, 1e4L, 1e5L, 1e6L, 1e7L, 1e8L, 1e9L,
537 1e10L, 1e11L, 1e12L, 1e13L, 1e14L, 1e15L, 1e16L, 1e17L, 1e18L, 1e19L,
538 1e20L, 1e21L, 1e22L, 1e23L, 1e24L, 1e25L, 1e26L, 1e27L, 1e28L, 1e29L,
539 1e30L, 1e31L, 1e32L, 1e33L, 1e34L, 1e35L, 1e36L, 1e37L, 1e38L, 1e39L,
540 1e40L, 1e41L, 1e42L, 1e43L, 1e44L, 1e45L, 1e46L, 1e47L, 1e48L};
541 static constexpr int32_t EXACT_POWERS_OF_TEN = 48;
542 static constexpr int32_t DIGITS_IN_MANTISSA = 33;
543 static constexpr long double MAX_EXACT_INT =
544 10384593717069655257060992658440191.0L;
545};
546#elif defined(LIBC_TYPES_LONG_DOUBLE_IS_DOUBLE_DOUBLE)
547// TODO: Add proper double double type support here, currently using constants
548// for double since it should be safe.
549template <> class ClingerConsts<long double> {
550public:
551 static constexpr double POWERS_OF_TEN_ARRAY[] = {
552 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11,
553 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
554 static constexpr int32_t EXACT_POWERS_OF_TEN = 22;
555 static constexpr int32_t DIGITS_IN_MANTISSA = 15;
556 static constexpr double MAX_EXACT_INT = 9007199254740991.0;
557};
558#else
559#error "Unknown long double type"
560#endif
561
562template <> class ClingerConsts<fputil::Float128> {
563public:
564 static constexpr fputil::Float128 POWERS_OF_TEN_ARRAY[] = {
565 fputil::Float128::from_bits(bits: UInt128(0x3fff000000000000ULL) << 64), // 1e0
566 fputil::Float128::from_bits(bits: UInt128(0x4002400000000000ULL) << 64), // 1e1
567 fputil::Float128::from_bits(bits: UInt128(0x4005900000000000ULL) << 64), // 1e2
568 fputil::Float128::from_bits(bits: UInt128(0x4008f40000000000ULL) << 64), // 1e3
569 fputil::Float128::from_bits(bits: UInt128(0x400c388000000000ULL) << 64), // 1e4
570 fputil::Float128::from_bits(bits: UInt128(0x400f86a000000000ULL) << 64), // 1e5
571 fputil::Float128::from_bits(bits: UInt128(0x4012e84800000000ULL) << 64), // 1e6
572 fputil::Float128::from_bits(bits: UInt128(0x4016312d00000000ULL) << 64), // 1e7
573 fputil::Float128::from_bits(bits: UInt128(0x40197d7840000000ULL) << 64), // 1e8
574 fputil::Float128::from_bits(bits: UInt128(0x401cdcd650000000ULL) << 64), // 1e9
575 fputil::Float128::from_bits(bits: UInt128(0x40202a05f2000000ULL) << 64), // 1e10
576 fputil::Float128::from_bits(bits: UInt128(0x402374876e800000ULL) << 64), // 1e11
577 fputil::Float128::from_bits(bits: UInt128(0x4026d1a94a200000ULL) << 64), // 1e12
578 fputil::Float128::from_bits(bits: UInt128(0x402a2309ce540000ULL) << 64), // 1e13
579 fputil::Float128::from_bits(bits: UInt128(0x402d6bcc41e90000ULL) << 64), // 1e14
580 fputil::Float128::from_bits(bits: UInt128(0x4030c6bf52634000ULL) << 64), // 1e15
581 fputil::Float128::from_bits(bits: UInt128(0x40341c37937e0800ULL) << 64), // 1e16
582 fputil::Float128::from_bits(bits: UInt128(0x40376345785d8a00ULL) << 64), // 1e17
583 fputil::Float128::from_bits(bits: UInt128(0x403abc16d674ec80ULL) << 64), // 1e18
584 fputil::Float128::from_bits(bits: UInt128(0x403e158e460913d0ULL) << 64), // 1e19
585 fputil::Float128::from_bits(bits: UInt128(0x40415af1d78b58c4ULL) << 64), // 1e20
586 fputil::Float128::from_bits(bits: UInt128(0x4044b1ae4d6e2ef5ULL) << 64), // 1e21
587 fputil::Float128::from_bits(bits: (UInt128(0x40480f0cf064dd59ULL) << 64) |
588 UInt128(0x2000000000000000ULL)), // 1e22
589 fputil::Float128::from_bits(bits: (UInt128(0x404b52d02c7e14afULL) << 64) |
590 UInt128(0x6800000000000000ULL)), // 1e23
591 fputil::Float128::from_bits(bits: (UInt128(0x404ea784379d99dbULL) << 64) |
592 UInt128(0x4200000000000000ULL)), // 1e24
593 fputil::Float128::from_bits(bits: (UInt128(0x405208b2a2c28029ULL) << 64) |
594 UInt128(0x0940000000000000ULL)), // 1e25
595 fputil::Float128::from_bits(bits: (UInt128(0x40554adf4b732033ULL) << 64) |
596 UInt128(0x4b90000000000000ULL)), // 1e26
597 fputil::Float128::from_bits(bits: (UInt128(0x40589d971e4fe840ULL) << 64) |
598 UInt128(0x1e74000000000000ULL)), // 1e27
599 fputil::Float128::from_bits(bits: (UInt128(0x405c027e72f1f128ULL) << 64) |
600 UInt128(0x1308800000000000ULL)), // 1e28
601 fputil::Float128::from_bits(bits: (UInt128(0x405f431e0fae6d72ULL) << 64) |
602 UInt128(0x17caa00000000000ULL)), // 1e29
603 fputil::Float128::from_bits(bits: (UInt128(0x406293e5939a08ceULL) << 64) |
604 UInt128(0x9dbd480000000000ULL)), // 1e30
605 fputil::Float128::from_bits(bits: (UInt128(0x4065f8def8808b02ULL) << 64) |
606 UInt128(0x452c9a0000000000ULL)), // 1e31
607 fputil::Float128::from_bits(bits: (UInt128(0x40693b8b5b5056e1ULL) << 64) |
608 UInt128(0x6b3be04000000000ULL)), // 1e32
609 fputil::Float128::from_bits(bits: (UInt128(0x406c8a6e32246c99ULL) << 64) |
610 UInt128(0xc60ad85000000000ULL)), // 1e33
611 fputil::Float128::from_bits(bits: (UInt128(0x406fed09bead87c0ULL) << 64) |
612 UInt128(0x378d8e6400000000ULL)), // 1e34
613 fputil::Float128::from_bits(bits: (UInt128(0x40733426172c74d8ULL) << 64) |
614 UInt128(0x22b878fe80000000ULL)), // 1e35
615 fputil::Float128::from_bits(bits: (UInt128(0x4076812f9cf7920eULL) << 64) |
616 UInt128(0x2b66973e20000000ULL)), // 1e36
617 fputil::Float128::from_bits(bits: (UInt128(0x4079e17b84357691ULL) << 64) |
618 UInt128(0xb6403d0da8000000ULL)), // 1e37
619 fputil::Float128::from_bits(bits: (UInt128(0x407d2ced32a16a1bULL) << 64) |
620 UInt128(0x11e8262889000000ULL)), // 1e38
621 fputil::Float128::from_bits(bits: (UInt128(0x408078287f49c4a1ULL) << 64) |
622 UInt128(0xd6622fb2ab400000ULL)), // 1e39
623 fputil::Float128::from_bits(bits: (UInt128(0x4083d6329f1c35caULL) << 64) |
624 UInt128(0x4bfabb9f56100000ULL)), // 1e40
625 fputil::Float128::from_bits(bits: (UInt128(0x408725dfa371a19eULL) << 64) |
626 UInt128(0x6f7cb54395ca0000ULL)), // 1e41
627 fputil::Float128::from_bits(bits: (UInt128(0x408a6f578c4e0a06ULL) << 64) |
628 UInt128(0x0b5be2947b3c8000ULL)), // 1e42
629 fputil::Float128::from_bits(bits: (UInt128(0x408dcb2d6f618c87ULL) << 64) |
630 UInt128(0x8e32db399a0ba000ULL)), // 1e43
631 fputil::Float128::from_bits(bits: (UInt128(0x40911efc659cf7d4ULL) << 64) |
632 UInt128(0xb8dfc90400474400ULL)), // 1e44
633 fputil::Float128::from_bits(bits: (UInt128(0x409466bb7f0435c9ULL) << 64) |
634 UInt128(0xe717bb4500591500ULL)), // 1e45
635 fputil::Float128::from_bits(bits: (UInt128(0x4097c06a5ec5433cULL) << 64) |
636 UInt128(0x60ddaa16406f5a40ULL)), // 1e46
637 fputil::Float128::from_bits(bits: (UInt128(0x409b18427b3b4a05ULL) << 64) |
638 UInt128(0xbc8a8a4de8459868ULL)), // 1e47
639 fputil::Float128::from_bits(bits: (UInt128(0x409e5e531a0a1c87ULL) << 64) |
640 UInt128(0x2bad2ce16256fe82ULL))}; // 1e48
641 static constexpr int32_t EXACT_POWERS_OF_TEN = 48;
642 static constexpr int32_t DIGITS_IN_MANTISSA = 33;
643 // 2^113 - 1 = 10384593717069655257060992658440191.0
644 static constexpr fputil::Float128 MAX_EXACT_INT = fputil::Float128::from_bits(
645 bits: (UInt128(0x406fffffffffffffULL) << 64) | UInt128(0xffffffffffffffffULL));
646};
647
648// Take an exact mantissa and exponent and attempt to convert it using only
649// exact floating point arithmetic. This only handles numbers with low
650// exponents, but handles them quickly. This is an implementation of Clinger's
651// Fast Path, as described above.
652template <class T>
653LIBC_INLINE cpp::optional<ExpandedFloat<T>>
654clinger_fast_path(ExpandedFloat<T> init_num,
655 RoundDirection round = RoundDirection::Nearest) {
656 using FPBits = typename fputil::FPBits<T>;
657 using StorageType = typename FPBits::StorageType;
658
659 StorageType mantissa = init_num.mantissa;
660 int32_t exp_10 = init_num.exponent;
661
662 if ((mantissa >> FPBits::FRACTION_LEN) > 0) {
663 return cpp::nullopt;
664 }
665
666 FPBits result;
667 T float_mantissa;
668 if constexpr (is_big_int_v<StorageType> || sizeof(T) > sizeof(uint64_t)) {
669 float_mantissa =
670 (static_cast<T>(uint64_t(mantissa >> 64)) * static_cast<T>(0x1.0p64)) +
671 static_cast<T>(uint64_t(mantissa));
672 } else {
673 float_mantissa = static_cast<T>(mantissa);
674 }
675
676 if (exp_10 == 0) {
677 result = FPBits(float_mantissa);
678 }
679 if (exp_10 > 0) {
680 if (exp_10 > ClingerConsts<T>::EXACT_POWERS_OF_TEN +
681 ClingerConsts<T>::DIGITS_IN_MANTISSA) {
682 return cpp::nullopt;
683 }
684 if (exp_10 > ClingerConsts<T>::EXACT_POWERS_OF_TEN) {
685 float_mantissa = float_mantissa *
686 ClingerConsts<T>::POWERS_OF_TEN_ARRAY
687 [exp_10 - ClingerConsts<T>::EXACT_POWERS_OF_TEN];
688 exp_10 = ClingerConsts<T>::EXACT_POWERS_OF_TEN;
689 }
690 if (float_mantissa > ClingerConsts<T>::MAX_EXACT_INT) {
691 return cpp::nullopt;
692 }
693 result =
694 FPBits(float_mantissa * ClingerConsts<T>::POWERS_OF_TEN_ARRAY[exp_10]);
695 } else if (exp_10 < 0) {
696 if (exp_10 < -ClingerConsts<T>::EXACT_POWERS_OF_TEN) {
697 return cpp::nullopt;
698 }
699 result =
700 FPBits(float_mantissa / ClingerConsts<T>::POWERS_OF_TEN_ARRAY[-exp_10]);
701 }
702
703 // If the rounding mode is not nearest, then the sign of the number may affect
704 // the result. To make sure the rounding mode is respected properly, the
705 // calculation is redone with a negative result, and the rounding mode is used
706 // to select the correct result.
707 if (round != RoundDirection::Nearest) {
708 // I'm 99% sure this will break under fast math optimizations.
709 FPBits negative_result =
710 exp_10 < 0 ? FPBits((-float_mantissa) /
711 ClingerConsts<T>::POWERS_OF_TEN_ARRAY[-exp_10])
712 : FPBits((-float_mantissa) *
713 ClingerConsts<T>::POWERS_OF_TEN_ARRAY[exp_10]);
714
715 // If the results are equal, then we don't need to use the rounding mode.
716 if (result.get_val() != -negative_result.get_val()) {
717 FPBits lower_result;
718 FPBits higher_result;
719
720 if (result.get_val() < -negative_result.get_val()) {
721 lower_result = result;
722 higher_result = negative_result;
723 } else {
724 lower_result = negative_result;
725 higher_result = result;
726 }
727
728 if (round == RoundDirection::Up) {
729 result = higher_result;
730 } else {
731 result = lower_result;
732 }
733 }
734 }
735
736 ExpandedFloat<T> output;
737 output.mantissa = result.get_explicit_mantissa();
738 output.exponent = result.get_biased_exponent();
739 return output;
740}
741
742// The upper bound is the highest base-10 exponent that could possibly give a
743// non-inf result for this size of float. The value is
744// log10(2^(exponent bias)).
745// The generic approximation uses the fact that log10(2^x) ~= x/3
746template <typename T> LIBC_INLINE constexpr int32_t get_upper_bound() {
747 return fputil::FPBits<T>::EXP_BIAS / 3;
748}
749
750template <> LIBC_INLINE constexpr int32_t get_upper_bound<float>() {
751 return 39;
752}
753
754template <> LIBC_INLINE constexpr int32_t get_upper_bound<double>() {
755 return 309;
756}
757
758// The lower bound is the largest negative base-10 exponent that could possibly
759// give a non-zero result for this size of float. The value is
760// log10(2^(exponent bias + final mantissa width + intermediate mantissa width))
761// The intermediate mantissa is the integer that's been parsed from the string,
762// and the final mantissa is the fractional part of the output number. A very
763// low base 10 exponent with a very high intermediate mantissa can cancel each
764// other out, and subnormal numbers allow for the result to be at the very low
765// end of the final mantissa.
766template <typename T> LIBC_INLINE constexpr int32_t get_lower_bound() {
767 using FPBits = typename fputil::FPBits<T>;
768 return -((FPBits::EXP_BIAS +
769 static_cast<int32_t>(FPBits::FRACTION_LEN + FPBits::STORAGE_LEN)) /
770 3);
771}
772
773template <> LIBC_INLINE constexpr int32_t get_lower_bound<float>() {
774 return -(39 + 6 + 10);
775}
776
777template <> LIBC_INLINE constexpr int32_t get_lower_bound<double>() {
778 return -(309 + 15 + 20);
779}
780
781// -----------------------------------------------------------------------------
782// **** WARNING ****
783// This interface is shared with libc++, if you change this interface you need
784// to update it in both libc and libc++.
785// -----------------------------------------------------------------------------
786// Takes a mantissa and base 10 exponent and converts it into its closest
787// floating point type T equivalient. First we try the Eisel-Lemire algorithm,
788// then if that fails then we fall back to a more accurate algorithm for
789// accuracy.
790template <typename T, typename CharType>
791LIBC_INLINE FloatConvertReturn<T> decimal_exp_to_float(
792 ExpandedFloat<T> init_num, [[maybe_unused]] bool truncated,
793 RoundDirection round, const CharType *__restrict numStart,
794 const size_t num_len = cpp::numeric_limits<size_t>::max()) {
795 using FPBits = typename fputil::FPBits<T>;
796
797 int32_t exp_10 = init_num.exponent;
798
799 FloatConvertReturn<T> output;
800 [[maybe_unused]] cpp::optional<ExpandedFloat<T>> opt_output;
801
802 // If the exponent is too large and can't be represented in this size of
803 // float, return inf. These bounds are relatively loose, but are mostly
804 // serving as a first pass. Some close numbers getting through is okay.
805 if (exp_10 > get_upper_bound<T>()) {
806 output.num = {0, FPBits::MAX_BIASED_EXPONENT};
807 output.error = ERANGE;
808 return output;
809 }
810 // If the exponent is too small even for a subnormal, return 0.
811 if (exp_10 < get_lower_bound<T>()) {
812 output.num = {0, 0};
813 output.error = ERANGE;
814 return output;
815 }
816
817 // Clinger's Fast Path and Eisel-Lemire can't set errno, but they can fail.
818 // For this reason the "error" field in their return values is used to
819 // represent whether they've failed as opposed to the errno value. Any
820 // non-zero value represents a failure.
821
822#ifndef LIBC_COPT_STRTOFLOAT_DISABLE_CLINGER_FAST_PATH
823 if (!truncated) {
824 opt_output = clinger_fast_path<T>(init_num, round);
825 // If the algorithm succeeded the error will be 0, else it will be a
826 // non-zero number.
827 if (opt_output.has_value()) {
828 return {opt_output.value(), 0};
829 }
830 }
831#endif // LIBC_COPT_STRTOFLOAT_DISABLE_CLINGER_FAST_PATH
832
833#ifndef LIBC_COPT_STRTOFLOAT_DISABLE_EISEL_LEMIRE
834 // Try Eisel-Lemire
835 using StorageType = typename FPBits::StorageType;
836 StorageType mantissa = init_num.mantissa;
837 opt_output = eisel_lemire<T>(init_num, round);
838 if (opt_output.has_value()) {
839 if (!truncated) {
840 return {opt_output.value(), 0};
841 }
842 // If the mantissa is truncated, then the result may be off by the LSB, so
843 // check if rounding the mantissa up changes the result. If not, then it's
844 // safe, else use the fallback.
845 auto second_output = eisel_lemire<T>({mantissa + 1, exp_10}, round);
846 if (second_output.has_value()) {
847 if (opt_output->mantissa == second_output->mantissa &&
848 opt_output->exponent == second_output->exponent) {
849 return {opt_output.value(), 0};
850 }
851 }
852 }
853#endif // LIBC_COPT_STRTOFLOAT_DISABLE_EISEL_LEMIRE
854
855#ifndef LIBC_COPT_STRTOFLOAT_DISABLE_SIMPLE_DECIMAL_CONVERSION
856 output = simple_decimal_conversion<T>(numStart, num_len, round);
857#else
858#warning "Simple decimal conversion is disabled, result may not be correct."
859#endif // LIBC_COPT_STRTOFLOAT_DISABLE_SIMPLE_DECIMAL_CONVERSION
860
861 return output;
862}
863
864// -----------------------------------------------------------------------------
865// **** WARNING ****
866// This interface is shared with libc++, if you change this interface you need
867// to update it in both libc and libc++.
868// -----------------------------------------------------------------------------
869// Takes a mantissa and base 2 exponent and converts it into its closest
870// floating point type T equivalient. Since the exponent is already in the right
871// form, this is mostly just shifting and rounding. This is used for hexadecimal
872// numbers since a base 16 exponent multiplied by 4 is the base 2 exponent.
873template <class T>
874LIBC_INLINE FloatConvertReturn<T> binary_exp_to_float(ExpandedFloat<T> init_num,
875 bool truncated,
876 RoundDirection round) {
877 using FPBits = typename fputil::FPBits<T>;
878 using StorageType = typename FPBits::StorageType;
879
880 StorageType mantissa = init_num.mantissa;
881 int32_t exp_2 = init_num.exponent;
882
883 FloatConvertReturn<T> output;
884
885 // This is the number of leading zeroes a properly normalized float of type T
886 // should have.
887 constexpr int32_t INF_EXP = (1 << FPBits::EXP_LEN) - 1;
888
889 // Normalization step 1: Bring the leading bit to the highest bit of
890 // StorageType.
891 uint32_t amount_to_shift_left = cpp::countl_zero<StorageType>(mantissa);
892 mantissa <<= amount_to_shift_left;
893
894 // Keep exp_2 representing the exponent of the lowest bit of StorageType.
895 exp_2 -= amount_to_shift_left;
896
897 // biased_exponent represents the biased exponent of the most significant bit.
898 int32_t biased_exponent = exp_2 + FPBits::STORAGE_LEN + FPBits::EXP_BIAS - 1;
899
900 // Handle numbers that're too large and get squashed to inf
901 if (biased_exponent >= INF_EXP) {
902 // This indicates an overflow, so we make the result INF and set errno.
903 output.num = {0, (1 << FPBits::EXP_LEN) - 1};
904 output.error = ERANGE;
905 return output;
906 }
907
908 uint32_t amount_to_shift_right =
909 FPBits::STORAGE_LEN - FPBits::FRACTION_LEN - 1;
910
911 // Handle subnormals.
912 if (biased_exponent <= 0) {
913 amount_to_shift_right += static_cast<uint32_t>(1 - biased_exponent);
914 biased_exponent = 0;
915
916 if (amount_to_shift_right > FPBits::STORAGE_LEN) {
917 // Return 0 if the exponent is too small.
918 output.num = {0, 0};
919 output.error = ERANGE;
920 return output;
921 }
922 }
923
924 StorageType round_bit_mask = StorageType(1) << (amount_to_shift_right - 1);
925 StorageType sticky_mask = round_bit_mask - 1;
926 bool round_bit = static_cast<bool>(mantissa & round_bit_mask);
927 bool sticky_bit = static_cast<bool>(mantissa & sticky_mask) || truncated;
928
929 if (amount_to_shift_right < FPBits::STORAGE_LEN) {
930 // Shift the mantissa and clear the implicit bit.
931 mantissa >>= amount_to_shift_right;
932 mantissa &= FPBits::FRACTION_MASK;
933 } else {
934 mantissa = 0;
935 }
936 bool least_significant_bit = static_cast<bool>(mantissa & StorageType(1));
937
938 // TODO: check that this rounding behavior is correct.
939
940 if (round == RoundDirection::Nearest) {
941 // Perform rounding-to-nearest, tie-to-even.
942 if (round_bit && (least_significant_bit || sticky_bit)) {
943 ++mantissa;
944 }
945 } else if (round == RoundDirection::Up) {
946 if (round_bit || sticky_bit) {
947 ++mantissa;
948 }
949 } else /* (round == RoundDirection::Down)*/ {
950 if (round_bit && sticky_bit) {
951 ++mantissa;
952 }
953 }
954
955 if (mantissa > FPBits::FRACTION_MASK) {
956 // Rounding causes the exponent to increase.
957 ++biased_exponent;
958
959 if (biased_exponent == INF_EXP) {
960 output.error = ERANGE;
961 }
962 }
963
964 if (biased_exponent == 0) {
965 output.error = ERANGE;
966 }
967
968 output.num = {mantissa & FPBits::FRACTION_MASK, biased_exponent};
969 return output;
970}
971
972// Checks if the first characters of the string pointer are the start of a
973// hexadecimal floating point number. Does not advance the string pointer.
974template <typename CharType>
975LIBC_INLINE static bool is_float_hex_start(const CharType *__restrict src) {
976 if (!is_char_or_wchar(src[0], '0', L'0') ||
977 !is_char_or_wchar(tolower(src[1]), 'x', L'x')) {
978 return false;
979 }
980 size_t first_digit = 2;
981 if (src[2] == constants<CharType>::DECIMAL_POINT) {
982 ++first_digit;
983 }
984 return isalnum(src[first_digit]) && b36_char_to_int(src[first_digit]) < 16;
985}
986
987// Verifies that first prefix_len characters of str, when lowercased, match the
988// specified prefix.
989template <typename CharType>
990LIBC_INLINE static bool tolower_starts_with(const CharType *str,
991 size_t prefix_len,
992 const CharType *prefix) {
993 for (size_t i = 0; i < prefix_len; ++i) {
994 if (tolower(str[i]) != prefix[i])
995 return false;
996 }
997 return true;
998}
999
1000// Attempts parsing a decimal floating point number at the start of the string.
1001template <typename T, typename CharType>
1002LIBC_INLINE static StrToNumResult<ExpandedFloat<T>>
1003decimal_string_to_float(const CharType *__restrict src, RoundDirection round) {
1004 using FPBits = typename fputil::FPBits<T>;
1005 using StorageType = typename FPBits::StorageType;
1006
1007 constexpr uint32_t BASE = 10;
1008 bool truncated = false;
1009 bool seen_digit = false;
1010 bool after_decimal = false;
1011 StorageType mantissa = 0;
1012 int32_t exponent = 0;
1013
1014 size_t index = 0;
1015
1016 StrToNumResult<ExpandedFloat<T>> output({0, 0});
1017
1018 // The goal for the first step of parsing is to convert the number in src to
1019 // the format mantissa * (base ^ exponent)
1020
1021 // The loop fills the mantissa with as many digits as it can hold
1022 const StorageType bitstype_max_div_by_base =
1023 cpp::numeric_limits<StorageType>::max() / BASE;
1024 while (true) {
1025 if (isdigit(src[index])) {
1026 uint32_t digit = static_cast<uint32_t>(b36_char_to_int(src[index]));
1027 seen_digit = true;
1028
1029 if (mantissa < bitstype_max_div_by_base) {
1030 mantissa = (mantissa * BASE) + digit;
1031 if (after_decimal) {
1032 --exponent;
1033 }
1034 } else {
1035 if (digit > 0)
1036 truncated = true;
1037 if (!after_decimal)
1038 ++exponent;
1039 }
1040
1041 ++index;
1042 continue;
1043 }
1044 if (src[index] == constants<CharType>::DECIMAL_POINT) {
1045 if (after_decimal) {
1046 break; // this means that src[index] points to a second decimal point,
1047 // ending the number.
1048 }
1049 after_decimal = true;
1050 ++index;
1051 continue;
1052 }
1053 // The character is neither a digit nor a decimal point.
1054 break;
1055 }
1056
1057 if (!seen_digit)
1058 return output;
1059
1060 // TODO: When adding max length argument, handle the case of a trailing
1061 // exponent marker, see scanf for more details.
1062 if (tolower(src[index]) == constants<CharType>::DECIMAL_EXPONENT_MARKER) {
1063 int sign = get_sign(src + index + 1);
1064 if (isdigit(src[index + 1 + static_cast<size_t>(sign != 0)])) {
1065 ++index;
1066 auto result = strtointeger<int32_t>(src + index, 10);
1067 if (result.has_error())
1068 output.error = result.error;
1069 int32_t add_to_exponent = result.value;
1070 index += static_cast<size_t>(result.parsed_len);
1071
1072 // Here we do this operation as int64 to avoid overflow.
1073 int64_t temp_exponent = static_cast<int64_t>(exponent) +
1074 static_cast<int64_t>(add_to_exponent);
1075
1076 // If the result is in the valid range, then we use it. The valid range is
1077 // also within the int32 range, so this prevents overflow issues.
1078 if (temp_exponent > FPBits::MAX_BIASED_EXPONENT) {
1079 exponent = FPBits::MAX_BIASED_EXPONENT;
1080 } else if (temp_exponent < -FPBits::MAX_BIASED_EXPONENT) {
1081 exponent = -FPBits::MAX_BIASED_EXPONENT;
1082 } else {
1083 exponent = static_cast<int32_t>(temp_exponent);
1084 }
1085 }
1086 }
1087
1088 output.parsed_len = index;
1089 if (mantissa == 0) { // if we have a 0, then also 0 the exponent.
1090 output.value = {0, 0};
1091 } else {
1092 auto temp =
1093 decimal_exp_to_float<T>({mantissa, exponent}, truncated, round, src);
1094 output.value = temp.num;
1095 output.error = temp.error;
1096 }
1097 return output;
1098}
1099
1100// Attempts parsing a hexadecimal floating point number at the start of the
1101// string.
1102template <typename T, typename CharType>
1103LIBC_INLINE static StrToNumResult<ExpandedFloat<T>>
1104hexadecimal_string_to_float(const CharType *__restrict src,
1105 RoundDirection round) {
1106 using FPBits = typename fputil::FPBits<T>;
1107 using StorageType = typename FPBits::StorageType;
1108
1109 constexpr uint32_t BASE = 16;
1110 bool truncated = false;
1111 bool seen_digit = false;
1112 bool after_decimal = false;
1113 StorageType mantissa = 0;
1114 int32_t exponent = 0;
1115
1116 size_t index = 0;
1117
1118 StrToNumResult<ExpandedFloat<T>> output({0, 0});
1119
1120 // The goal for the first step of parsing is to convert the number in src to
1121 // the format mantissa * (base ^ exponent)
1122
1123 // The loop fills the mantissa with as many digits as it can hold
1124 const StorageType bitstype_max_div_by_base =
1125 cpp::numeric_limits<StorageType>::max() / BASE;
1126 while (true) {
1127 if (isalnum(src[index])) {
1128 uint32_t digit = static_cast<uint32_t>(b36_char_to_int(src[index]));
1129 if (digit < BASE)
1130 seen_digit = true;
1131 else
1132 break;
1133
1134 if (mantissa < bitstype_max_div_by_base) {
1135 mantissa = (mantissa * BASE) + digit;
1136 if (after_decimal)
1137 --exponent;
1138 } else {
1139 if (digit > 0)
1140 truncated = true;
1141 if (!after_decimal)
1142 ++exponent;
1143 }
1144 ++index;
1145 continue;
1146 }
1147 if (src[index] == constants<CharType>::DECIMAL_POINT) {
1148 if (after_decimal) {
1149 break; // this means that src[index] points to a second decimal point,
1150 // ending the number.
1151 }
1152 after_decimal = true;
1153 ++index;
1154 continue;
1155 }
1156 // The character is neither a hexadecimal digit nor a decimal point.
1157 break;
1158 }
1159
1160 if (!seen_digit)
1161 return output;
1162
1163 // Convert the exponent from having a base of 16 to having a base of 2.
1164 exponent *= 4;
1165
1166 if (tolower(src[index]) == constants<CharType>::HEX_EXPONENT_MARKER) {
1167 int sign = get_sign(src + index + 1);
1168 if (isdigit(src[index + 1 + static_cast<size_t>(sign != 0)])) {
1169 ++index;
1170 auto result = strtointeger<int32_t>(src + index, 10);
1171 if (result.has_error())
1172 output.error = result.error;
1173
1174 int32_t add_to_exponent = result.value;
1175 index += static_cast<size_t>(result.parsed_len);
1176
1177 // Here we do this operation as int64 to avoid overflow.
1178 int64_t temp_exponent = static_cast<int64_t>(exponent) +
1179 static_cast<int64_t>(add_to_exponent);
1180
1181 // If the result is in the valid range, then we use it. The valid range is
1182 // also within the int32 range, so this prevents overflow issues.
1183 if (temp_exponent > FPBits::MAX_BIASED_EXPONENT) {
1184 exponent = FPBits::MAX_BIASED_EXPONENT;
1185 } else if (temp_exponent < -FPBits::MAX_BIASED_EXPONENT) {
1186 exponent = -FPBits::MAX_BIASED_EXPONENT;
1187 } else {
1188 exponent = static_cast<int32_t>(temp_exponent);
1189 }
1190 }
1191 }
1192 output.parsed_len = index;
1193 if (mantissa == 0) { // if we have a 0, then also 0 the exponent.
1194 output.value.exponent = 0;
1195 output.value.mantissa = 0;
1196 } else {
1197 auto temp = binary_exp_to_float<T>({mantissa, exponent}, truncated, round);
1198 output.error = temp.error;
1199 output.value = temp.num;
1200 }
1201 return output;
1202}
1203
1204template <typename T, typename CharType>
1205LIBC_INLINE constexpr typename fputil::FPBits<T>::StorageType
1206nan_mantissa_from_ncharseq(const CharType *str, size_t len) {
1207 using FPBits = typename fputil::FPBits<T>;
1208 using StorageType = typename FPBits::StorageType;
1209
1210 StorageType nan_mantissa = 0;
1211
1212 if (len > 0 && isdigit(str[0])) {
1213 StrToNumResult<StorageType> strtoint_result =
1214 strtointeger<StorageType>(str, 0, len);
1215 if (!strtoint_result.has_error())
1216 nan_mantissa = strtoint_result.value;
1217
1218 if (strtoint_result.parsed_len != static_cast<ptrdiff_t>(len))
1219 nan_mantissa = 0;
1220 }
1221
1222 return nan_mantissa;
1223}
1224
1225// Takes a pointer to a string and a pointer to a string pointer. This function
1226// is used as the backend for all of the string to float functions.
1227// TODO: Add src_len member to match strtointeger.
1228// TODO: Next, move from char* and length to string_view
1229template <typename T, typename CharType>
1230LIBC_INLINE StrToNumResult<T>
1231strtofloatingpoint(const CharType *__restrict src) {
1232 using FPBits = typename fputil::FPBits<T>;
1233 using StorageType = typename FPBits::StorageType;
1234
1235 FPBits result = FPBits();
1236 bool seen_digit = false;
1237 int error = 0;
1238
1239 size_t index = first_non_whitespace(src);
1240 int sign = get_sign(src + index);
1241#ifndef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
1242 bool is_positive = (sign >= 0);
1243#endif
1244 index += (sign != 0);
1245
1246 if (sign < 0) {
1247 result.set_sign(Sign::NEG);
1248 }
1249
1250 if (isdigit(src[index]) ||
1251 src[index] == constants<CharType>::DECIMAL_POINT) { // regular number
1252 int base = 10;
1253 if (is_float_hex_start(src + index)) {
1254 base = 16;
1255 index += 2;
1256 seen_digit = true;
1257 }
1258
1259 RoundDirection round_direction = RoundDirection::Nearest;
1260#ifndef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
1261 switch (fputil::quick_get_round()) {
1262 case FE_TONEAREST:
1263 round_direction = RoundDirection::Nearest;
1264 break;
1265 case FE_UPWARD:
1266 round_direction = is_positive ? RoundDirection::Up : RoundDirection::Down;
1267 break;
1268 case FE_DOWNWARD:
1269 round_direction = is_positive ? RoundDirection::Down : RoundDirection::Up;
1270 break;
1271 case FE_TOWARDZERO:
1272 round_direction = RoundDirection::Down;
1273 break;
1274 }
1275#endif // LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
1276
1277 StrToNumResult<ExpandedFloat<T>> parse_result({0, 0});
1278 if (base == 16) {
1279 parse_result =
1280 hexadecimal_string_to_float<T>(src + index, round_direction);
1281 } else { // base is 10
1282 parse_result = decimal_string_to_float<T>(src + index, round_direction);
1283 }
1284 seen_digit = parse_result.parsed_len != 0;
1285 result.set_mantissa(parse_result.value.mantissa);
1286 result.set_biased_exponent(parse_result.value.exponent);
1287 index += parse_result.parsed_len;
1288 error = parse_result.error;
1289 } else if (tolower_starts_with(src + index, 3,
1290 constants<CharType>::NAN_STRING)) {
1291 // NAN
1292 seen_digit = true;
1293 index += 3;
1294 StorageType nan_mantissa = 0;
1295 // this handles the case of `NaN(n-character-sequence)`, where the
1296 // n-character-sequence is made of 0 or more letters, numbers, or
1297 // underscore characters in any order.
1298 if (is_char_or_wchar(src[index], '(', L'(')) {
1299 size_t left_paren = index;
1300 ++index;
1301 while (isalnum(src[index]) || is_char_or_wchar(src[index], '_', L'_'))
1302 ++index;
1303 if (is_char_or_wchar(src[index], ')', L')')) {
1304 ++index;
1305 nan_mantissa = nan_mantissa_from_ncharseq<T>(src + (left_paren + 1),
1306 index - left_paren - 2);
1307 } else {
1308 index = left_paren;
1309 }
1310 }
1311 result = FPBits(result.quiet_nan(result.sign(), nan_mantissa));
1312 } else if (tolower_starts_with(src + index, 8,
1313 constants<CharType>::INF_STRING)) {
1314 // INFINITY
1315 seen_digit = true;
1316 result = FPBits(result.inf(result.sign()));
1317 index += 8;
1318 } else if (tolower_starts_with(src + index, 3,
1319 constants<CharType>::INF_STRING)) {
1320 // INF
1321 seen_digit = true;
1322 result = FPBits(result.inf(result.sign()));
1323 index += 3;
1324 }
1325
1326 if (!seen_digit) { // If there is nothing to actually parse, then return 0.
1327 return {T(0), 0, error};
1328 }
1329
1330 // This function only does something if T is long double and the platform uses
1331 // special 80 bit long doubles. Otherwise it should be inlined out.
1332 set_implicit_bit<T>(result);
1333
1334 return {result.get_val(), static_cast<ptrdiff_t>(index), error};
1335}
1336
1337template <class T>
1338LIBC_INLINE constexpr StrToNumResult<T> strtonan(const char *arg) {
1339 using FPBits = typename fputil::FPBits<T>;
1340 using StorageType = typename FPBits::StorageType;
1341
1342 LIBC_CRASH_ON_NULLPTR(arg);
1343
1344 FPBits result;
1345 int error = 0;
1346 StorageType nan_mantissa = 0;
1347
1348 ptrdiff_t index = 0;
1349 while (isalnum(ch: arg[index]) || arg[index] == '_')
1350 ++index;
1351
1352 if (arg[index] == '\0')
1353 nan_mantissa = nan_mantissa_from_ncharseq<T>(arg, index);
1354
1355 result = FPBits::quiet_nan(Sign::POS, nan_mantissa);
1356 return {result.get_val(), 0, error};
1357}
1358
1359} // namespace internal
1360} // namespace LIBC_NAMESPACE_DECL
1361
1362#endif // LLVM_LIBC_SRC___SUPPORT_STR_TO_FLOAT_H
1363