1//===-- A class to store high precision floating point numbers --*- 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___SUPPORT_FPUTIL_DYADIC_FLOAT_H
10#define LLVM_LIBC_SRC___SUPPORT_FPUTIL_DYADIC_FLOAT_H
11
12#include "hdr/errno_macros.h"
13#include "hdr/fenv_macros.h"
14#include "src/__support/CPP/type_traits.h"
15#include "src/__support/FPUtil/FEnvImpl.h"
16#include "src/__support/FPUtil/FPBits.h"
17#include "src/__support/FPUtil/multiply_add.h"
18#include "src/__support/FPUtil/rounding_mode.h"
19#include "src/__support/big_int.h"
20#include "src/__support/macros/attributes.h"
21#include "src/__support/macros/config.h"
22#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
23#include "src/__support/macros/properties/types.h"
24
25#include <stddef.h>
26
27namespace LIBC_NAMESPACE_DECL {
28namespace fputil {
29
30// Decide whether to round a UInt up, down or not at all at a given bit
31// position, based on the current rounding mode. The assumption is that the
32// caller is going to make the integer `value >> rshift`, and then might need
33// to round it up by 1 depending on the value of the bits shifted off the
34// bottom.
35//
36// `logical_sign` causes the behavior of FE_DOWNWARD and FE_UPWARD to
37// be reversed, which is what you'd want if this is the mantissa of a
38// negative floating-point number.
39//
40// Return value is +1 if the value should be rounded up; -1 if it should be
41// rounded down; 0 if it's exact and needs no rounding.
42template <size_t Bits>
43LIBC_INLINE LIBC_CONSTEXPR_DEFAULT int
44rounding_direction(const LIBC_NAMESPACE::UInt<Bits> &value, size_t rshift,
45 [[maybe_unused]] Sign logical_sign) {
46 // logical_sign only affects FE_DOWNWARD and FE_UPWARD rounding modes. In the
47 // case of LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY being enabled, this option
48 // is no-op
49
50 if (rshift == 0 || (rshift < Bits && (value << (Bits - rshift)) == 0) ||
51 (rshift >= Bits && value == 0))
52 return 0; // exact
53
54#ifdef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
55 if (rshift > 0 && rshift <= Bits && value.get_bit(rshift - 1)) {
56 // We round up, unless the value is an exact halfway case and
57 // the bit that will end up in the units place is 0, in which
58 // case tie-break-to-even says round down.
59 bool round_bit = rshift < Bits ? value.get_bit(rshift) : 0;
60 return round_bit != 0 || (value << (Bits - rshift + 1)) != 0 ? +1 : -1;
61 } else {
62 return -1;
63 }
64#else // !LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
65 switch (quick_get_round()) {
66 case FE_TONEAREST:
67 if (rshift > 0 && rshift <= Bits && value.get_bit(rshift - 1)) {
68 // We round up, unless the value is an exact halfway case and
69 // the bit that will end up in the units place is 0, in which
70 // case tie-break-to-even says round down.
71 bool round_bit = rshift < Bits ? value.get_bit(rshift) : 0;
72 return round_bit != 0 || (value << (Bits - rshift + 1)) != 0 ? +1 : -1;
73 } else {
74 return -1;
75 }
76 case FE_TOWARDZERO:
77 return -1;
78 case FE_DOWNWARD:
79 return logical_sign.is_neg() &&
80 (rshift < Bits && (value << (Bits - rshift)) != 0)
81 ? +1
82 : -1;
83 case FE_UPWARD:
84 return logical_sign.is_pos() &&
85 (rshift < Bits && (value << (Bits - rshift)) != 0)
86 ? +1
87 : -1;
88 default:
89 __builtin_unreachable();
90 }
91#endif // LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
92}
93
94// A generic class to perform computations of high precision floating points.
95// We store the value in dyadic format, including 3 fields:
96// sign : boolean value - false means positive, true means negative
97// exponent: the exponent value of the least significant bit of the mantissa.
98// mantissa: unsigned integer of length `Bits`.
99// So the real value that is stored is:
100// real value = (-1)^sign * 2^exponent * (mantissa as unsigned integer)
101// The stored data is normal if for non-zero mantissa, the leading bit is 1.
102// The outputs of the constructors and most functions will be normalized.
103// To simplify and improve the efficiency, many functions will assume that the
104// inputs are normal.
105template <size_t Bits> struct DyadicFloat {
106 using MantissaType = LIBC_NAMESPACE::UInt<Bits>;
107
108 Sign sign = Sign::POS;
109 int exponent = 0;
110 MantissaType mantissa = MantissaType(0);
111
112 LIBC_INLINE constexpr DyadicFloat() = default;
113
114 template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
115 LIBC_INLINE LIBC_BIT_CAST_CONSTEXPR DyadicFloat(T x) {
116 static_assert(FPBits<T>::FRACTION_LEN < Bits);
117 FPBits<T> x_bits(x);
118 sign = x_bits.sign();
119 exponent = x_bits.get_explicit_exponent() - FPBits<T>::FRACTION_LEN;
120 mantissa = MantissaType(x_bits.get_explicit_mantissa());
121 normalize();
122 }
123
124 LIBC_INLINE constexpr DyadicFloat(Sign s, int e, const MantissaType &m)
125 : sign(s), exponent(e), mantissa(m) {
126 normalize();
127 }
128
129 // Normalizing the mantissa, bringing the leading 1 bit to the most
130 // significant bit.
131 LIBC_INLINE constexpr DyadicFloat &normalize() {
132 if (!mantissa.is_zero()) {
133 int shift_length = cpp::countl_zero(mantissa);
134 exponent -= shift_length;
135 mantissa <<= static_cast<size_t>(shift_length);
136 }
137 return *this;
138 }
139
140 // Used for aligning exponents. Output might not be normalized.
141 LIBC_INLINE constexpr DyadicFloat &shift_left(unsigned shift_length) {
142 exponent -= static_cast<int>(shift_length);
143 if (shift_length < Bits)
144 mantissa <<= shift_length;
145 else
146 mantissa = MantissaType(0);
147 return *this;
148 }
149
150 // Used for aligning exponents. Output might not be normalized.
151 LIBC_INLINE constexpr DyadicFloat &shift_right(unsigned shift_length) {
152 exponent += static_cast<int>(shift_length);
153 if (shift_length < Bits)
154 mantissa >>= shift_length;
155 else
156 mantissa = MantissaType(0);
157 return *this;
158 }
159
160 // Assume that it is already normalized. Output the unbiased exponent.
161 LIBC_INLINE constexpr int get_unbiased_exponent() const {
162 return exponent + (Bits - 1);
163 }
164
165 // Produce a correctly rounded DyadicFloat from a too-large mantissa,
166 // by shifting it down and rounding if necessary.
167 template <size_t MantissaBits>
168 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT static DyadicFloat<Bits>
169 round(Sign result_sign, int result_exponent,
170 const LIBC_NAMESPACE::UInt<MantissaBits> &input_mantissa,
171 size_t rshift) {
172 MantissaType result_mantissa(input_mantissa >> rshift);
173 if (rounding_direction(input_mantissa, rshift, result_sign) > 0) {
174 ++result_mantissa;
175 if (result_mantissa == 0) {
176 // Rounding up made the mantissa integer wrap round to 0,
177 // carrying a bit off the top. So we've rounded up to the next
178 // exponent.
179 result_mantissa.set_bit(Bits - 1);
180 ++result_exponent;
181 }
182 }
183 return DyadicFloat(result_sign, result_exponent, result_mantissa);
184 }
185
186 // The integer core of generic_as(). The destination is named by FPType, so
187 // it also covers formats with no usable native type (float16 without
188 // _Float16).
189 template <FPType DstType, bool ShouldSignalExceptions>
190 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT typename FPRep<DstType>::StorageType
191 generic_as_bits() const {
192 using DstRep = FPRep<DstType>;
193 using StorageType = typename DstRep::StorageType;
194 // Native type used to pick the exception-raising specialization; formats
195 // without one fall back to the generic version.
196 using ExceptT = cpp::conditional_t<
197 DstType == FPType::IEEE754_Binary32, float,
198 cpp::conditional_t<DstType == FPType::IEEE754_Binary64, double, void>>;
199 static_assert(DstRep::FRACTION_LEN < Bits);
200
201 constexpr int EXTRA_FRACTION_LEN = Bits - 1 - DstRep::FRACTION_LEN;
202
203 if (mantissa == 0)
204 return DstRep::zero(sign).uintval();
205
206 int unbiased_exp = get_unbiased_exponent();
207
208 if (unbiased_exp + DstRep::EXP_BIAS >= DstRep::MAX_BIASED_EXPONENT) {
209 if (!cpp::is_constant_evaluated()) {
210#if !(defined(LIBC_MATH_HAS_NO_EXCEPT) && \
211 defined(LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY))
212 if constexpr (ShouldSignalExceptions && internal::HAS_HW_FPU<ExceptT>) {
213 set_errno_if_required(ERANGE);
214 ExceptT r = internal::OVERFLOW_FACTOR<ExceptT> *
215 internal::OVERFLOW_VAL<ExceptT>[sign.is_neg()];
216 return FPBits<ExceptT>(r).uintval();
217 }
218#endif
219 }
220 if constexpr (ShouldSignalExceptions) {
221 set_errno_if_required(ERANGE);
222 raise_overflow_except_if_required<ExceptT>();
223 }
224
225#ifdef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
226 return DstRep::inf(sign).uintval();
227#else // !LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
228 switch (quick_get_round()) {
229 case FE_TONEAREST:
230 return DstRep::inf(sign).uintval();
231 case FE_TOWARDZERO:
232 return DstRep::max_normal(sign).uintval();
233 case FE_DOWNWARD:
234 if (sign.is_pos())
235 return DstRep::max_normal(Sign::POS).uintval();
236 return DstRep::inf(Sign::NEG).uintval();
237 case FE_UPWARD:
238 if (sign.is_neg())
239 return DstRep::max_normal(Sign::NEG).uintval();
240 return DstRep::inf(Sign::POS).uintval();
241 default:
242 __builtin_unreachable();
243 }
244#endif // LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
245 }
246
247 StorageType out_biased_exp = 0;
248 StorageType out_mantissa = 0;
249 bool round = false;
250 bool sticky = false;
251 bool underflow = false;
252
253 if (unbiased_exp < -DstRep::EXP_BIAS - DstRep::FRACTION_LEN) {
254 sticky = true;
255 underflow = true;
256 } else if (unbiased_exp == -DstRep::EXP_BIAS - DstRep::FRACTION_LEN) {
257 round = true;
258 // underflow is detected pre-rounding FE_UNDERFLOW may be raised
259 // even if rounding produces a non-underflow result
260 underflow = true;
261 MantissaType sticky_mask = (MantissaType(1) << (Bits - 1)) - 1;
262 sticky = (mantissa & sticky_mask) != 0;
263 } else {
264 int extra_fraction_len = EXTRA_FRACTION_LEN;
265
266 if (unbiased_exp < 1 - DstRep::EXP_BIAS) {
267 underflow = true;
268 extra_fraction_len += 1 - DstRep::EXP_BIAS - unbiased_exp;
269 } else {
270 out_biased_exp =
271 static_cast<StorageType>(unbiased_exp + DstRep::EXP_BIAS);
272 }
273
274 if (extra_fraction_len > 0) {
275 MantissaType round_mask = MantissaType(1) << (extra_fraction_len - 1);
276 round = (mantissa & round_mask) != 0;
277 MantissaType sticky_mask = round_mask - 1;
278 sticky = (mantissa & sticky_mask) != 0;
279 }
280
281 out_mantissa = static_cast<StorageType>(mantissa >> extra_fraction_len);
282 }
283
284 bool lsb = (out_mantissa & 1) != 0;
285
286 StorageType result =
287 DstRep::create_value(sign, out_biased_exp, out_mantissa).uintval();
288
289#ifdef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
290 if (round && (lsb || sticky))
291 ++result;
292#else
293 switch (quick_get_round()) {
294 case FE_TONEAREST:
295 if (round && (lsb || sticky))
296 ++result;
297 break;
298 case FE_DOWNWARD:
299 if (sign.is_neg() && (round || sticky))
300 ++result;
301 break;
302 case FE_UPWARD:
303 if (sign.is_pos() && (round || sticky))
304 ++result;
305 break;
306 default:
307 break;
308 }
309#endif // LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
310
311 if (ShouldSignalExceptions && (round || sticky)) {
312 if (DstRep(result).is_inf()) {
313 set_errno_if_required(ERANGE);
314 raise_overflow_except_if_required<ExceptT>();
315 } else if (underflow) {
316 set_errno_if_required(ERANGE);
317 raise_underflow_except_if_required<ExceptT>();
318 } else {
319 raise_except_if_required(FE_INEXACT);
320 }
321 }
322
323 return result;
324 }
325
326 template <typename T, bool ShouldSignalExceptions>
327 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT cpp::enable_if_t<
328 cpp::is_floating_point_v<T> && (FPBits<T>::FRACTION_LEN < Bits), T>
329 generic_as() const {
330 return FPBits<T>(
331 generic_as_bits<get_fp_type<T>(), ShouldSignalExceptions>())
332 .get_val();
333 }
334
335 template <typename T, bool ShouldSignalExceptions = true,
336 typename = cpp::enable_if_t<cpp::is_floating_point_v<T> &&
337 (FPBits<T>::FRACTION_LEN < Bits),
338 void>>
339 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT T fast_as() const {
340 if (LIBC_UNLIKELY(mantissa.is_zero()))
341 return FPBits<T>::zero(sign).get_val();
342
343 // Assume that it is normalized, and output is also normal.
344 constexpr uint32_t PRECISION = FPBits<T>::FRACTION_LEN + 1;
345 using output_bits_t = typename FPBits<T>::StorageType;
346 constexpr output_bits_t IMPLICIT_MASK =
347 FPBits<T>::SIG_MASK - FPBits<T>::FRACTION_MASK;
348
349 int exp_hi = exponent + static_cast<int>((Bits - 1) + FPBits<T>::EXP_BIAS);
350
351 if (LIBC_UNLIKELY(exp_hi > 2 * FPBits<T>::EXP_BIAS)) {
352 // Results overflow.
353 if (cpp::is_constant_evaluated())
354 return FPBits<T>::inf(sign).get_val();
355
356 if constexpr (ShouldSignalExceptions)
357 set_errno_if_required(ERANGE);
358
359#if defined(LIBC_MATH_HAS_NO_EXCEPT) && \
360 defined(LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY)
361 return FPBits<T>::inf(sign).get_val();
362#else
363 if constexpr (ShouldSignalExceptions && internal::HAS_HW_FPU<T>) {
364 return internal::OVERFLOW_FACTOR<T> *
365 internal::OVERFLOW_VAL<T>[sign.is_neg()];
366 } else {
367 if constexpr (ShouldSignalExceptions)
368 raise_overflow_except_if_required<T>();
369#ifndef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
370 int rounding = quick_get_round();
371 if (rounding == FE_TOWARDZERO ||
372 (rounding == FE_DOWNWARD && sign.is_pos()) ||
373 (rounding == FE_UPWARD && sign.is_neg()))
374 return FPBits<T>::max_normal(sign).get_val();
375#endif // !LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
376 return FPBits<T>::inf(sign).get_val();
377 }
378#endif
379 }
380
381 bool denorm = false;
382 uint32_t shift = Bits - PRECISION;
383 if (LIBC_UNLIKELY(exp_hi <= 0)) {
384 // Output is denormal.
385 denorm = true;
386 shift = (Bits - PRECISION) + static_cast<uint32_t>(1 - exp_hi);
387
388 exp_hi = FPBits<T>::EXP_BIAS;
389 }
390
391 int exp_lo = exp_hi - static_cast<int>(PRECISION) - 1;
392
393 MantissaType m_hi =
394 shift >= MantissaType::BITS ? MantissaType(0) : mantissa >> shift;
395
396 T d_hi = FPBits<T>::create_value(
397 sign, static_cast<output_bits_t>(exp_hi),
398 (static_cast<output_bits_t>(m_hi) & FPBits<T>::SIG_MASK) |
399 IMPLICIT_MASK)
400 .get_val();
401
402 MantissaType round_mask =
403 shift - 1 >= MantissaType::BITS ? 0 : MantissaType(1) << (shift - 1);
404 MantissaType sticky_mask = round_mask - MantissaType(1);
405
406 bool round_bit = !(mantissa & round_mask).is_zero();
407 bool sticky_bit = !(mantissa & sticky_mask).is_zero();
408 int round_and_sticky = int(round_bit) * 2 + int(sticky_bit);
409
410 T d_lo;
411
412 if (LIBC_UNLIKELY(exp_lo <= 0)) {
413 // d_lo is denormal, but the output is normal.
414 int scale_up_exponent = 1 - exp_lo;
415 T scale_up_factor =
416 FPBits<T>::create_value(Sign::POS,
417 static_cast<output_bits_t>(
418 FPBits<T>::EXP_BIAS + scale_up_exponent),
419 IMPLICIT_MASK)
420 .get_val();
421 T scale_down_factor =
422 FPBits<T>::create_value(Sign::POS,
423 static_cast<output_bits_t>(
424 FPBits<T>::EXP_BIAS - scale_up_exponent),
425 IMPLICIT_MASK)
426 .get_val();
427
428 d_lo = FPBits<T>::create_value(
429 sign, static_cast<output_bits_t>(exp_lo + scale_up_exponent),
430 IMPLICIT_MASK)
431 .get_val();
432
433 return multiply_add(d_lo, T(round_and_sticky), d_hi * scale_up_factor) *
434 scale_down_factor;
435 }
436
437 d_lo = FPBits<T>::create_value(sign, static_cast<output_bits_t>(exp_lo),
438 IMPLICIT_MASK)
439 .get_val();
440
441 // Still correct without FMA instructions if `d_lo` is not underflow.
442 T r = multiply_add(d_lo, T(round_and_sticky), d_hi);
443
444 if (LIBC_UNLIKELY(denorm)) {
445 // Exponent before rounding is in denormal range, simply clear the
446 // exponent field.
447 output_bits_t clear_exp = static_cast<output_bits_t>(
448 output_bits_t(exp_hi) << FPBits<T>::SIG_LEN);
449 output_bits_t r_bits = FPBits<T>(r).uintval() - clear_exp;
450
451 if (!(r_bits & FPBits<T>::EXP_MASK)) {
452 // Output is denormal after rounding, clear the implicit bit for
453 // 80-bit long double.
454 r_bits -= IMPLICIT_MASK;
455 }
456
457 // Underflow exception and ERANGE are signaled when an unrounded result
458 // in the denormal range is inexact, even if destination rounding rounds
459 // it up to min_normal.
460 if (ShouldSignalExceptions && round_and_sticky) {
461 set_errno_if_required(ERANGE);
462 raise_underflow_except_if_required<T>();
463 }
464
465 return FPBits<T>(r_bits).get_val();
466 }
467
468 return r;
469 }
470
471 // Assume that it is already normalized.
472 // Output is rounded correctly with respect to the current rounding mode.
473 template <typename T, bool ShouldSignalExceptions = true,
474 typename = cpp::enable_if_t<cpp::is_floating_point_v<T> &&
475 (FPBits<T>::FRACTION_LEN < Bits),
476 void>>
477 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT T as() const {
478 if constexpr (cpp::is_same_v<T, bfloat16> || cpp::is_same_v<T, Float128> ||
479 cpp::is_same_v<T, Float80>
480#if defined(LIBC_TYPES_HAS_FLOAT16) && !defined(__LIBC_USE_FLOAT16_CONVERSION)
481 || cpp::is_same_v<T, float16>
482#endif
483#if defined(LIBC_TYPES_HAS_NATIVE_FLOAT128)
484 || cpp::is_same_v<T, float128>
485#endif
486 )
487 return generic_as<T, ShouldSignalExceptions>();
488 else
489 return fast_as<T, ShouldSignalExceptions>();
490 }
491
492 template <typename T,
493 typename = cpp::enable_if_t<cpp::is_floating_point_v<T> &&
494 (FPBits<T>::FRACTION_LEN < Bits),
495 void>>
496 LIBC_INLINE explicit constexpr operator T() const {
497 return as<T, /*ShouldSignalExceptions=*/true>();
498 }
499
500 LIBC_INLINE constexpr MantissaType as_mantissa_type() const {
501 if (mantissa.is_zero())
502 return 0;
503
504 MantissaType new_mant = mantissa;
505 if (exponent > 0) {
506 new_mant <<= exponent;
507 } else {
508 // Cast the exponent to size_t before negating it, rather than after,
509 // to avoid undefined behavior negating INT_MIN as an integer (although
510 // exponents coming in to this function _shouldn't_ be that large). The
511 // result should always end up as a positive size_t.
512 size_t shift = -static_cast<size_t>(exponent);
513 size_t limit = cpp::numeric_limits<MantissaType>::digits;
514 if (shift >= limit)
515 new_mant = 0;
516 else
517 new_mant >>= shift;
518 }
519
520 if (sign.is_neg()) {
521 new_mant = (~new_mant) + 1;
522 }
523
524 return new_mant;
525 }
526
527 LIBC_INLINE LIBC_CONSTEXPR_DEFAULT MantissaType
528 as_mantissa_type_rounded(int *round_dir_out = nullptr) const {
529 int round_dir = 0;
530 MantissaType new_mant;
531 if (mantissa.is_zero()) {
532 new_mant = 0;
533 } else {
534 new_mant = mantissa;
535 if (exponent > 0) {
536 new_mant <<= exponent;
537 } else if (exponent < 0) {
538 // Cast the exponent to size_t before negating it, rather than after,
539 // to avoid undefined behavior negating INT_MIN as an integer
540 // (although exponents coming in to this function _shouldn't_ be that
541 // large). The result should always end up as a positive size_t.
542 size_t shift = -static_cast<size_t>(exponent);
543 if (shift >= Bits)
544 new_mant = 0;
545 else
546 new_mant >>= shift;
547 round_dir = rounding_direction(mantissa, shift, sign);
548 if (round_dir > 0)
549 ++new_mant;
550 }
551
552 if (sign.is_neg()) {
553 new_mant = (~new_mant) + 1;
554 }
555 }
556
557 if (round_dir_out)
558 *round_dir_out = round_dir;
559
560 return new_mant;
561 }
562
563 LIBC_INLINE constexpr DyadicFloat operator-() const {
564 return DyadicFloat(sign.negate(), exponent, mantissa);
565 }
566};
567
568// Quick add - Add 2 dyadic floats with rounding toward 0 and then normalize
569// the output:
570// - Align the exponents so that:
571// new a.exponent = new b.exponent = max(a.exponent, b.exponent)
572// - Add or subtract the mantissas depending on the signs.
573// - Normalize the result.
574// The absolute errors compared to the mathematical sum is bounded by:
575// | quick_add(a, b) - (a + b) | < MSB(a + b) * 2^(-Bits + 2),
576// i.e., errors are up to 2 ULPs.
577// Assume inputs are normalized (by constructors or other functions) so that
578// we don't need to normalize the inputs again in this function. If the
579// inputs are not normalized, the results might lose precision significantly.
580template <size_t Bits>
581LIBC_INLINE constexpr DyadicFloat<Bits> quick_add(DyadicFloat<Bits> a,
582 DyadicFloat<Bits> b) {
583 if (LIBC_UNLIKELY(a.mantissa.is_zero()))
584 return b;
585 if (LIBC_UNLIKELY(b.mantissa.is_zero()))
586 return a;
587
588 // Align exponents
589 if (a.exponent > b.exponent)
590 b.shift_right(static_cast<unsigned>(a.exponent - b.exponent));
591 else if (b.exponent > a.exponent)
592 a.shift_right(static_cast<unsigned>(b.exponent - a.exponent));
593
594 DyadicFloat<Bits> result;
595
596 if (a.sign == b.sign) {
597 // Addition
598 result.sign = a.sign;
599 result.exponent = a.exponent;
600 result.mantissa = a.mantissa;
601 if (result.mantissa.add_overflow(b.mantissa)) {
602 // Mantissa addition overflow.
603 result.shift_right(1);
604 result.mantissa.val[DyadicFloat<Bits>::MantissaType::WORD_COUNT - 1] |=
605 (uint64_t(1) << 63);
606 }
607 // Result is already normalized.
608 return result;
609 }
610
611 // Subtraction
612 if (a.mantissa >= b.mantissa) {
613 result.sign = a.sign;
614 result.exponent = a.exponent;
615 result.mantissa = a.mantissa - b.mantissa;
616 } else {
617 result.sign = b.sign;
618 result.exponent = b.exponent;
619 result.mantissa = b.mantissa - a.mantissa;
620 }
621
622 return result.normalize();
623}
624
625template <size_t Bits>
626LIBC_INLINE constexpr DyadicFloat<Bits> quick_sub(DyadicFloat<Bits> a,
627 DyadicFloat<Bits> b) {
628 return quick_add(a, -b);
629}
630
631// Quick Mul - Slightly less accurate but efficient multiplication of 2 dyadic
632// floats with rounding toward 0 and then normalize the output:
633// result.exponent = a.exponent + b.exponent + Bits,
634// result.mantissa = quick_mul_hi(a.mantissa + b.mantissa)
635// ~ (full product a.mantissa * b.mantissa) >> Bits.
636// The errors compared to the mathematical product is bounded by:
637// 2 * errors of quick_mul_hi = 2 * (UInt<Bits>::WORD_COUNT - 1) in ULPs.
638// Assume inputs are normalized (by constructors or other functions) so that
639// we don't need to normalize the inputs again in this function. If the
640// inputs are not normalized, the results might lose precision significantly.
641template <size_t Bits>
642LIBC_INLINE constexpr DyadicFloat<Bits> quick_mul(const DyadicFloat<Bits> &a,
643 const DyadicFloat<Bits> &b) {
644 DyadicFloat<Bits> result;
645 result.sign = (a.sign != b.sign) ? Sign::NEG : Sign::POS;
646 result.exponent = a.exponent + b.exponent + static_cast<int>(Bits);
647
648 if (!(a.mantissa.is_zero() || b.mantissa.is_zero())) {
649 result.mantissa = a.mantissa.quick_mul_hi(b.mantissa);
650 // Check the leading bit directly, should be faster than using clz in
651 // normalize().
652 if (result.mantissa.val[DyadicFloat<Bits>::MantissaType::WORD_COUNT - 1] >>
653 (DyadicFloat<Bits>::MantissaType::WORD_SIZE - 1) ==
654 0)
655 result.shift_left(1);
656 } else {
657 result.mantissa = (typename DyadicFloat<Bits>::MantissaType)(0);
658 }
659 return result;
660}
661
662// Correctly rounded multiplication of 2 dyadic floats, assuming the
663// exponent remains within range.
664template <size_t Bits>
665LIBC_INLINE constexpr DyadicFloat<Bits>
666rounded_mul(const DyadicFloat<Bits> &a, const DyadicFloat<Bits> &b) {
667 using DblMant = LIBC_NAMESPACE::UInt<(2 * Bits)>;
668 Sign result_sign = (a.sign != b.sign) ? Sign::NEG : Sign::POS;
669 int result_exponent = a.exponent + b.exponent + static_cast<int>(Bits);
670 auto product = DblMant(a.mantissa) * DblMant(b.mantissa);
671 // As in quick_mul(), renormalize by 1 bit manually rather than countl_zero
672 if (product.get_bit(2 * Bits - 1) == 0) {
673 product <<= 1;
674 result_exponent -= 1;
675 }
676
677 return DyadicFloat<Bits>::round(result_sign, result_exponent, product, Bits);
678}
679
680// Approximate reciprocal - given a nonzero a, make a good approximation to
681// 1/a. The method is Newton-Raphson iteration, based on quick_mul.
682template <size_t Bits, typename = cpp::enable_if_t<(Bits >= 32)>>
683LIBC_INLINE constexpr DyadicFloat<Bits>
684approx_reciprocal(const DyadicFloat<Bits> &a) {
685 // Given an approximation x to 1/a, a better one is x' = x(2-ax).
686 //
687 // You can derive this by using the Newton-Raphson formula with the function
688 // f(x) = 1/x - a. But another way to see that it works is to say: suppose
689 // that ax = 1-e for some small error e. Then ax' = ax(2-ax) = (1-e)(1+e) =
690 // 1-e^2. So the error in x' is the square of the error in x, i.e. the
691 // number of correct bits in x' is double the number in x.
692
693 // An initial approximation to the reciprocal
694 DyadicFloat<Bits> x(Sign::POS, -32 - a.exponent - int(Bits),
695 uint64_t(0xFFFFFFFFFFFFFFFF) /
696 static_cast<uint64_t>(a.mantissa >> (Bits - 32)));
697
698 // The constant 2, which we'll need in every iteration
699 DyadicFloat<Bits> two(Sign::POS, 1, 1);
700
701 // We expect at least 31 correct bits from our 32-bit starting approximation
702 size_t ok_bits = 31;
703
704 // The number of good bits doubles in each iteration, except that rounding
705 // errors introduce a little extra each time. Subtract a bit from our
706 // accuracy assessment to account for that.
707 while (ok_bits < Bits) {
708 x = quick_mul(x, quick_sub(two, quick_mul(a, x)));
709 ok_bits = 2 * ok_bits - 1;
710 }
711
712 return x;
713}
714
715// Correctly rounded division of 2 dyadic floats, assuming the
716// exponent remains within range.
717template <size_t Bits>
718LIBC_INLINE constexpr DyadicFloat<Bits>
719rounded_div(const DyadicFloat<Bits> &af, const DyadicFloat<Bits> &bf) {
720 using DblMant = LIBC_NAMESPACE::UInt<(Bits * 2 + 64)>;
721
722 // Make an approximation to the quotient as a * (1/b). Both the
723 // multiplication and the reciprocal are a bit sloppy, which doesn't
724 // matter, because we're going to correct for that below.
725 auto qf = fputil::quick_mul(af, fputil::approx_reciprocal(bf));
726
727 // Switch to BigInt and stop using quick_add and quick_mul: now
728 // we're working in exact integers so as to get the true remainder.
729 DblMant a = af.mantissa, b = bf.mantissa, q = qf.mantissa;
730 q <<= 2; // leave room for a round bit, even if exponent decreases
731 a <<= af.exponent - bf.exponent - qf.exponent + 2;
732 DblMant qb = q * b;
733 if (qb < a) {
734 DblMant too_small = a - b;
735 while (qb <= too_small) {
736 qb += b;
737 ++q;
738 }
739 } else {
740 while (qb > a) {
741 qb -= b;
742 --q;
743 }
744 }
745
746 DyadicFloat<(Bits * 2)> qbig(qf.sign, qf.exponent - 2, q);
747 return DyadicFloat<Bits>::round(qbig.sign, qbig.exponent + Bits,
748 qbig.mantissa, Bits);
749}
750
751// Simple polynomial approximation.
752template <size_t Bits>
753LIBC_INLINE constexpr DyadicFloat<Bits>
754multiply_add(const DyadicFloat<Bits> &a, const DyadicFloat<Bits> &b,
755 const DyadicFloat<Bits> &c) {
756 return quick_add(c, quick_mul(a, b));
757}
758
759template <size_t Bits>
760LIBC_INLINE constexpr DyadicFloat<Bits>
761multiply_sub(const DyadicFloat<Bits> &a, const DyadicFloat<Bits> &b,
762 const DyadicFloat<Bits> &c) {
763 return quick_sub(quick_mul(a, b), c);
764}
765
766template <size_t Bits>
767LIBC_INLINE constexpr DyadicFloat<Bits>
768sub_multiply(const DyadicFloat<Bits> &a, const DyadicFloat<Bits> &b,
769 const DyadicFloat<Bits> &c) {
770 return quick_sub(a, quick_mul(b, c));
771}
772
773// Simple exponentiation implementation for printf. Only handles positive
774// exponents, since division isn't implemented.
775template <size_t Bits>
776LIBC_INLINE constexpr DyadicFloat<Bits> pow_n(const DyadicFloat<Bits> &a,
777 uint32_t power) {
778 DyadicFloat<Bits> result = 1.0;
779 DyadicFloat<Bits> cur_power = a;
780
781 while (power > 0) {
782 if ((power % 2) > 0) {
783 result = quick_mul(result, cur_power);
784 }
785 power = power >> 1;
786 cur_power = quick_mul(cur_power, cur_power);
787 }
788 return result;
789}
790
791template <size_t Bits>
792LIBC_INLINE constexpr DyadicFloat<Bits> mul_pow_2(const DyadicFloat<Bits> &a,
793 int32_t pow_2) {
794 DyadicFloat<Bits> result = a;
795 result.exponent += pow_2;
796 return result;
797}
798
799} // namespace fputil
800} // namespace LIBC_NAMESPACE_DECL
801
802#endif // LLVM_LIBC_SRC___SUPPORT_FPUTIL_DYADIC_FLOAT_H
803