1//===-- Implementation of hypotf function ---------------------------------===//
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_HYPOT_H
10#define LLVM_LIBC_SRC___SUPPORT_FPUTIL_HYPOT_H
11
12#include "hdr/fenv_macros.h"
13#include "hdr/stdint_proxy.h"
14#include "src/__support/CPP/bit.h"
15#include "src/__support/CPP/type_traits.h"
16#include "src/__support/FPUtil/FEnvImpl.h"
17#include "src/__support/FPUtil/FPBits.h"
18#include "src/__support/FPUtil/cast.h"
19#include "src/__support/FPUtil/except_value_utils.h"
20#include "src/__support/FPUtil/rounding_mode.h"
21#include "src/__support/macros/attributes.h"
22#include "src/__support/macros/config.h"
23#include "src/__support/macros/optimization.h"
24#include "src/__support/macros/properties/types.h"
25#include "src/__support/uint128.h"
26
27namespace LIBC_NAMESPACE_DECL {
28namespace fputil {
29
30namespace internal {
31
32template <typename T>
33LIBC_INLINE T find_leading_one(T mant, int &shift_length) {
34 shift_length = 0;
35 if (mant > 0) {
36 shift_length = (sizeof(mant) * 8) - 1 - cpp::countl_zero(mant);
37 }
38 return static_cast<T>((T(1) << shift_length));
39}
40
41} // namespace internal
42
43template <typename T> struct DoubleLength;
44
45template <> struct DoubleLength<uint16_t> {
46 using Type = uint32_t;
47};
48
49template <> struct DoubleLength<uint32_t> {
50 using Type = uint64_t;
51};
52
53template <> struct DoubleLength<uint64_t> {
54 using Type = UInt128;
55};
56
57// Correctly rounded IEEE 754 HYPOT(x, y) with round to nearest, ties to even.
58//
59// Algorithm:
60// - Let a = max(|x|, |y|), b = min(|x|, |y|), then we have that:
61// a <= sqrt(a^2 + b^2) <= min(a + b, a*sqrt(2))
62// 1. So if b < eps(a)/2, then HYPOT(x, y) = a.
63//
64// - Moreover, the exponent part of HYPOT(x, y) is either the same or 1 more
65// than the exponent part of a.
66//
67// 2. For the remaining cases, we will use the digit-by-digit (shift-and-add)
68// algorithm to compute SQRT(Z):
69//
70// - For Y = y0.y1...yn... = SQRT(Z),
71// let Y(n) = y0.y1...yn be the first n fractional digits of Y.
72//
73// - The nth scaled residual R(n) is defined to be:
74// R(n) = 2^n * (Z - Y(n)^2)
75//
76// - Since Y(n) = Y(n - 1) + yn * 2^(-n), the scaled residual
77// satisfies the following recurrence formula:
78// R(n) = 2*R(n - 1) - yn*(2*Y(n - 1) + 2^(-n)),
79// with the initial conditions:
80// Y(0) = y0, and R(0) = Z - y0.
81//
82// - So the nth fractional digit of Y = SQRT(Z) can be decided by:
83// yn = 1 if 2*R(n - 1) >= 2*Y(n - 1) + 2^(-n),
84// 0 otherwise.
85//
86// 3. Precision analysis:
87//
88// - Notice that in the decision function:
89// 2*R(n - 1) >= 2*Y(n - 1) + 2^(-n),
90// the right hand side only uses up to the 2^(-n)-bit, and both sides are
91// non-negative, so R(n - 1) can be truncated at the 2^(-(n + 1))-bit, so
92// that 2*R(n - 1) is corrected up to the 2^(-n)-bit.
93//
94// - Thus, in order to round SQRT(a^2 + b^2) correctly up to n-fractional
95// bits, we need to perform the summation (a^2 + b^2) correctly up to (2n +
96// 2)-fractional bits, and the remaining bits are sticky bits (i.e. we only
97// care if they are 0 or > 0), and the comparisons, additions/subtractions
98// can be done in n-fractional bits precision.
99//
100// - For single precision (float), we can use uint64_t to store the sum a^2 +
101// b^2 exact up to (2n + 2)-fractional bits.
102//
103// - Then we can feed this sum into the digit-by-digit algorithm for SQRT(Z)
104// described above.
105//
106//
107// Special cases:
108// - HYPOT(x, y) is +Inf if x or y is +Inf or -Inf; else
109// - HYPOT(x, y) is NaN if x or y is NaN.
110//
111template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T>, int> = 0>
112LIBC_INLINE T hypot(T x, T y) {
113 using FPBits_t = FPBits<T>;
114 using StorageType = typename FPBits<T>::StorageType;
115 using DStorageType = typename DoubleLength<StorageType>::Type;
116
117 FPBits_t x_abs = FPBits_t(x).abs();
118 FPBits_t y_abs = FPBits_t(y).abs();
119
120 bool x_abs_larger = x_abs.uintval() >= y_abs.uintval();
121
122 FPBits_t a_bits = x_abs_larger ? x_abs : y_abs;
123 FPBits_t b_bits = x_abs_larger ? y_abs : x_abs;
124
125 if (LIBC_UNLIKELY(a_bits.is_inf_or_nan())) {
126 if (x_abs.is_signaling_nan() || y_abs.is_signaling_nan()) {
127 fputil::raise_except_if_required(FE_INVALID);
128 return FPBits_t::quiet_nan().get_val();
129 }
130 if (x_abs.is_inf() || y_abs.is_inf())
131 return FPBits_t::inf().get_val();
132 if (x_abs.is_nan())
133 return x;
134 // y is nan
135 return y;
136 }
137
138 uint16_t a_exp = a_bits.get_biased_exponent();
139 uint16_t b_exp = b_bits.get_biased_exponent();
140
141 if ((a_exp - b_exp >= FPBits_t::FRACTION_LEN + 2) || (x == 0) || (y == 0)) {
142#ifdef LIBC_TYPES_HAS_FLOAT16
143 if constexpr (cpp::is_same_v<T, float16>) {
144 // Compiler runtime for basic operations of float16 might not be correctly
145 // rounded for all rounding modes.
146 float af = fputil::cast<float>(x_abs.get_val());
147 float bf = fputil::cast<float>(y_abs.get_val());
148 return fputil::cast<float16>(x: af + bf);
149 } else
150#endif // LIBC_TYPES_HAS_FLOAT16
151 return x_abs.get_val() + y_abs.get_val();
152 }
153
154 uint64_t out_exp = a_exp;
155 StorageType a_mant = a_bits.get_mantissa();
156 StorageType b_mant = b_bits.get_mantissa();
157 DStorageType a_mant_sq, b_mant_sq;
158 bool sticky_bits;
159
160 // Add an extra bit to simplify the final rounding bit computation.
161 constexpr StorageType ONE = StorageType(1) << (FPBits_t::FRACTION_LEN + 1);
162
163 a_mant <<= 1;
164 b_mant <<= 1;
165
166 StorageType leading_one;
167 int y_mant_width;
168 if (a_exp != 0) {
169 leading_one = ONE;
170 a_mant |= ONE;
171 y_mant_width = FPBits_t::FRACTION_LEN + 1;
172 } else {
173 leading_one = internal::find_leading_one(a_mant, y_mant_width);
174 a_exp = 1;
175 }
176
177 if (b_exp != 0)
178 b_mant |= ONE;
179 else
180 b_exp = 1;
181
182 a_mant_sq = static_cast<DStorageType>(a_mant) * a_mant;
183 b_mant_sq = static_cast<DStorageType>(b_mant) * b_mant;
184
185 // At this point, a_exp >= b_exp > a_exp - 25, so in order to line up aSqMant
186 // and bSqMant, we need to shift bSqMant to the right by (a_exp - b_exp) bits.
187 // But before that, remember to store the losing bits to sticky.
188 // The shift length is for a^2 and b^2, so it's double of the exponent
189 // difference between a and b.
190 uint16_t shift_length = static_cast<uint16_t>(2 * (a_exp - b_exp));
191 sticky_bits =
192 ((b_mant_sq & ((DStorageType(1) << shift_length) - DStorageType(1))) !=
193 DStorageType(0));
194 b_mant_sq >>= shift_length;
195
196 DStorageType sum = a_mant_sq + b_mant_sq;
197 if (sum >= (DStorageType(1) << (2 * y_mant_width + 2))) {
198 // a^2 + b^2 >= 4* leading_one^2, so we will need an extra bit to the left.
199 if (leading_one == ONE) {
200 // For normal result, we discard the last 2 bits of the sum and increase
201 // the exponent.
202 sticky_bits = sticky_bits || ((sum & 0x3U) != 0);
203 sum >>= 2;
204 ++out_exp;
205 if (out_exp >= FPBits_t::MAX_BIASED_EXPONENT)
206 return set_overflow<T>();
207 } else {
208 // For denormal result, we simply move the leading bit of the result to
209 // the left by 1.
210 leading_one <<= 1;
211 ++y_mant_width;
212 }
213 }
214
215 StorageType y_new = leading_one;
216 StorageType r = static_cast<StorageType>(sum >> y_mant_width) - leading_one;
217 StorageType tail_bits = static_cast<StorageType>(sum) & (leading_one - 1);
218
219 for (StorageType current_bit = leading_one >> 1; current_bit;
220 current_bit >>= 1) {
221 r = static_cast<StorageType>((r << 1) +
222 ((tail_bits & current_bit) ? 1 : 0));
223 StorageType tmp = static_cast<StorageType>((y_new << 1)) +
224 current_bit; // 2*y_new(n - 1) + 2^(-n)
225 if (r >= tmp) {
226 r -= tmp;
227 y_new += current_bit;
228 }
229 }
230
231 bool round_bit = y_new & StorageType(1);
232 bool lsb = y_new & StorageType(2);
233
234 if ((out_exp == 0) && (round_bit || sticky_bits || (r != 0)))
235 raise_underflow_except_if_required<T>();
236
237 if (y_new >= ONE) {
238 y_new -= ONE;
239
240 if (out_exp == 0) {
241 out_exp = 1;
242 }
243 }
244
245 y_new >>= 1;
246
247#ifdef LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
248 // Round to the nearest, tie to even.
249 if (round_bit && (lsb || sticky_bits || (r != 0)))
250 ++y_new;
251#else
252 // Round to the nearest, tie to even.
253 int round_mode = quick_get_round();
254 switch (round_mode) {
255 case FE_TONEAREST:
256 // Round to nearest, ties to even
257 if (round_bit && (lsb || sticky_bits || (r != 0)))
258 ++y_new;
259 break;
260 case FE_UPWARD:
261 if (round_bit || sticky_bits || (r != 0))
262 ++y_new;
263 break;
264 }
265#endif // LIBC_MATH_HAS_ASSUME_ROUND_NEAREST_ONLY
266
267 if (y_new >= (ONE >> 1)) {
268 y_new -= ONE >> 1;
269 ++out_exp;
270 if (out_exp >= FPBits_t::MAX_BIASED_EXPONENT)
271 return set_overflow<T>();
272 }
273
274 y_new |= static_cast<StorageType>(out_exp) << FPBits_t::FRACTION_LEN;
275
276 // TODO: We should only clear FE_INEXACT except if it's not set at the
277 // start of the function.
278 // if (!(round_bit || sticky_bits || (r != 0)))
279 // fputil::clear_except_if_required(FE_INEXACT);
280
281 return cpp::bit_cast<T>(y_new);
282}
283
284} // namespace fputil
285} // namespace LIBC_NAMESPACE_DECL
286
287#endif // LLVM_LIBC_SRC___SUPPORT_FPUTIL_HYPOT_H
288