1//===----------------------------------------------------------------------===//
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/// \file
10/// Common header for polynomial evaluation implementations.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_FPUTIL_POLYEVAL_H
15#define LLVM_LIBC_SRC___SUPPORT_FPUTIL_POLYEVAL_H
16
17#include "hdr/types/size_t.h"
18#include "src/__support/CPP/type_traits.h"
19#include "src/__support/FPUtil/multiply_add.h"
20#include "src/__support/common.h"
21#include "src/__support/macros/config.h"
22#include "src/__support/macros/optimization.h"
23
24namespace LIBC_NAMESPACE_DECL {
25namespace fputil {
26
27// Evaluate polynomial using Horner's scheme:
28// polyeval(x, a_0, a_1, ..., a_n) = a_0 + x * (a_1 + ... + x * a_n).
29template <typename T, typename... Ts>
30LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
31polyeval([[maybe_unused]] T x, T a0, Ts... a) {
32 static_assert((cpp::is_same_v<T, Ts> && ...),
33 "All coefficients must have the same type T.");
34 if constexpr (sizeof...(Ts) == 0) {
35 return a0;
36 } else {
37 T r = polyeval(x, a...);
38 return multiply_add(x, r, a0);
39 }
40}
41
42template <typename T, typename... Ts>
43LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
44polyeval([[maybe_unused]] const T &x, const T &a0, const Ts &...a) {
45 static_assert((cpp::is_same_v<T, Ts> && ...),
46 "All coefficients must have the same type T.");
47 if constexpr (sizeof...(Ts) == 0) {
48 return a0;
49 } else {
50 T r = polyeval(x, a...);
51 return multiply_add(x, r, a0);
52 }
53}
54
55template <size_t OFFSET = 0, typename T, size_t N>
56LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
57polyeval([[maybe_unused]] T x, const T (&a)[N]) {
58 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
59 if constexpr (OFFSET + 1 == N) {
60 return a[OFFSET];
61 } else {
62 T r = polyeval<OFFSET + 1>(x, a);
63 return multiply_add(x, r, a[OFFSET]);
64 }
65}
66
67template <size_t OFFSET = 0, typename T, size_t N>
68LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
69polyeval([[maybe_unused]] const T &x, const T (&a)[N]) {
70 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
71 if constexpr (OFFSET + 1 == N) {
72 return a[OFFSET];
73 } else {
74 T r = polyeval<OFFSET + 1>(x, a);
75 return multiply_add(x, r, a[OFFSET]);
76 }
77}
78
79// Evaluate alternating polynomial:
80// altpolyeval(x, a_0, a_1, ..., a_n) = a_0 - x * a_1 + x^2 * a_2 - ...
81// + (-1)^n * x^n * a_n.
82template <typename T, typename... Ts>
83LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
84altpolyeval([[maybe_unused]] T x, T a0, Ts... a) {
85 static_assert((cpp::is_same_v<T, Ts> && ...),
86 "All coefficients must have the same type T.");
87 if constexpr (sizeof...(Ts) == 0) {
88 return a0;
89 } else {
90 T r = altpolyeval(x, a...);
91 return sub_multiply(a0, x, r);
92 }
93}
94
95template <typename T, typename... Ts>
96LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
97altpolyeval([[maybe_unused]] const T &x, const T &a0, const Ts &...a) {
98 static_assert((cpp::is_same_v<T, Ts> && ...),
99 "All coefficients must have the same type T.");
100 if constexpr (sizeof...(Ts) == 0) {
101 return a0;
102 } else {
103 T r = altpolyeval(x, a...);
104 return sub_multiply(a0, x, r);
105 }
106}
107
108template <size_t OFFSET = 0, typename T, size_t N>
109LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
110altpolyeval([[maybe_unused]] T x, const T (&a)[N]) {
111 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
112 if constexpr (OFFSET + 1 == N) {
113 return a[OFFSET];
114 } else {
115 T r = altpolyeval<OFFSET + 1>(x, a);
116 return sub_multiply(a[OFFSET], x, r);
117 }
118}
119
120template <size_t OFFSET = 0, typename T, size_t N>
121LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
122altpolyeval([[maybe_unused]] const T &x, const T (&a)[N]) {
123 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
124 if constexpr (OFFSET + 1 == N) {
125 return a[OFFSET];
126 } else {
127 T r = altpolyeval<OFFSET + 1>(x, a);
128 return sub_multiply(a[OFFSET], x, r);
129 }
130}
131
132// Evaluate polynomial using a non-unrolled Horner loop:
133// loop_polyeval<OFFSET>(x, a) = a[OFFSET] + x * (a[OFFSET + 1] + ...
134// + x * a[N - 1]).
135template <size_t OFFSET = 0, typename T, size_t N>
136LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
137loop_polyeval([[maybe_unused]] T x, const T (&a)[N]) {
138 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
139 T r = a[N - 1];
140 if constexpr (OFFSET + 1 < N) {
141 LIBC_LOOP_NOUNROLL
142 for (size_t i = N - 1; i > OFFSET; --i)
143 r = multiply_add(x, r, a[i - 1]);
144 }
145 return r;
146}
147
148template <size_t OFFSET = 0, typename T, size_t N>
149LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
150loop_polyeval([[maybe_unused]] const T &x, const T (&a)[N]) {
151 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
152 T r = a[N - 1];
153 if constexpr (OFFSET + 1 < N) {
154 LIBC_LOOP_NOUNROLL
155 for (size_t i = N - 1; i > OFFSET; --i)
156 r = multiply_add(x, r, a[i - 1]);
157 }
158 return r;
159}
160
161// Evaluate alternating polynomial using a non-unrolled Horner loop:
162// loop_altpolyeval<OFFSET>(x, a) = a[OFFSET] - x * a[OFFSET + 1] + ...
163// + (-1)^(N - 1 - OFFSET) * x^(N - 1 - OFFSET) * a[N - 1].
164template <size_t OFFSET = 0, typename T, size_t N>
165LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
166loop_altpolyeval([[maybe_unused]] T x, const T (&a)[N]) {
167 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
168 T r = a[N - 1];
169 if constexpr (OFFSET + 1 < N) {
170 LIBC_LOOP_NOUNROLL
171 for (size_t i = N - 1; i > OFFSET; --i)
172 r = sub_multiply(a[i - 1], x, r);
173 }
174 return r;
175}
176
177template <size_t OFFSET = 0, typename T, size_t N>
178LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
179loop_altpolyeval([[maybe_unused]] const T &x, const T (&a)[N]) {
180 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
181 T r = a[N - 1];
182 if constexpr (OFFSET + 1 < N) {
183 LIBC_LOOP_NOUNROLL
184 for (size_t i = N - 1; i > OFFSET; --i)
185 r = sub_multiply(a[i - 1], x, r);
186 }
187 return r;
188}
189
190namespace internal {
191
192template <typename T>
193using ValOrConstRef =
194 cpp::conditional_t<(sizeof(T) > sizeof(double)), const T &, T>;
195
196// For len >= 2, let 2^h < len <= 2^(h + 1), so tree depth is h + 1 and each
197// subtree has capacity at most 2^h. Return the smallest k such that
198// 2^k >= len - 2^h, giving a right-heavy split:
199// LOW = 2^k <= 2^h, 1 <= HI = len - 2^k <= 2^h.
200// Examples:
201// len = 2, 3 -> k = 0 (1 + 1, 1 + 2)
202// len = 4 -> k = 1 (2 + 2)
203// len = 5 -> k = 0 (1 + 4)
204// len = 6 -> k = 1 (2 + 4)
205// len = 7, 8 -> k = 2 (4 + 3, 4 + 4)
206// len = 9 -> k = 0 (1 + 8)
207// len = 10 -> k = 1 (2 + 8)
208// len = 11, 12 -> k = 2 (4 + 7, 4 + 8)
209LIBC_INLINE constexpr size_t estrin_split_log2(size_t len) {
210 size_t h = 0;
211 while ((size_t(1) << (h + 1)) < len)
212 ++h;
213 size_t rem = len - (size_t(1) << h);
214 size_t k = 0;
215 while ((size_t(1) << k) < rem)
216 ++k;
217 return k;
218}
219
220// Return the largest dyadic power index K needed across the entire right-heavy
221// Estrin tree of length len (for len >= 2). Powers up to x^(2^K) can form a
222// full high subtree of length 2^(K + 1) plus a low subtree of length 2^K,
223// covering len <= 3 * 2^K:
224// len = 2, 3 -> K = 0 (x)
225// len = 4..6 -> K = 1 (x, x^2)
226// len = 7..12 -> K = 2 (x, x^2, x^4)
227// len = 13..24 -> K = 3 (x, x^2, x^4, x^8)
228LIBC_INLINE constexpr size_t estrin_max_power_log2(size_t len) {
229 size_t k = 0;
230 while ((size_t(3) << k) < len)
231 ++k;
232 return k;
233}
234
235// Precompute dyadic powers x^(2^0), x^(2^1), ..., x^(2^K) once by repeated
236// squaring so that all subtrees share x^2, x^4, ..., x^(2^K). Members are
237// initialized in declaration order (`prev` before `x_pow`), computing:
238// EstrinPows<T, 0>: x_pow = x
239// EstrinPows<T, K>: prev = EstrinPows<T, K - 1>(x),
240// x_pow = prev.x_pow * prev.x_pow = x^(2^K)
241// pows.get<I>() returns x^(2^I) for 0 <= I <= K.
242template <typename T, size_t K> struct EstrinPows {
243 EstrinPows<T, K - 1> prev;
244 T x_pow;
245
246 LIBC_ALWAYS_INLINE constexpr explicit EstrinPows(ValOrConstRef<T> x)
247 : prev(x), x_pow(prev.x_pow * prev.x_pow) {}
248
249 template <size_t I>
250 LIBC_ALWAYS_INLINE constexpr ValOrConstRef<T> get() const {
251 if constexpr (I == K)
252 return x_pow;
253 else
254 return prev.template get<I>();
255 }
256};
257
258template <typename T> struct EstrinPows<T, 0> {
259 T x_pow;
260
261 LIBC_ALWAYS_INLINE constexpr explicit EstrinPows(ValOrConstRef<T> x)
262 : x_pow(x) {}
263
264 template <size_t I>
265 LIBC_ALWAYS_INLINE constexpr ValOrConstRef<T> get() const {
266 static_assert(I == 0, "Invalid Estrin power index.");
267 return x_pow;
268 }
269};
270
271// Recursively evaluate P(x) = sum_{i = 0}^{LEN - 1} a[OFFSET + i] * x^i using
272// a right-heavy Estrin binary tree of minimum depth ceil(log2(LEN)):
273// - LEN == 1: a[OFFSET]
274// - LEN == 2: multiply_add(x, a[OFFSET + 1], a[OFFSET])
275// = a[OFFSET] + x * a[OFFSET + 1]
276// - LEN >= 3: let K = estrin_split_log2(LEN) and LOW = 2^K. Split into:
277// lo = estrin_eval_tree<OFFSET, LOW>(pows, a)
278// = sum_{i = 0}^{LOW - 1} a[OFFSET + i] * x^i
279// hi = estrin_eval_tree<OFFSET + LOW, LEN - LOW>(pows, a)
280// = sum_{i = 0}^{LEN - LOW - 1} a[OFFSET + LOW + i] * x^i
281// and combine via multiply_add(x^(2^K), hi, lo) = lo + x^(2^K) * hi.
282//
283// Placing the larger subtree in `hi` minimizes both the highest required power
284// of x and the number of roundings on a[OFFSET] when |x| << 1, while keeping
285// tree depth ceil(log2(LEN)). With x2 = x^2 and x4 = x^4, each (u + p * v)
286// below is evaluated as multiply_add(p, v, u):
287// LEN = 3: a0 + x * (a1 + x * a2)
288// LEN = 4: (a0 + x * a1) + x2 * (a2 + x * a3)
289// LEN = 5: a0 + x * ((a1 + x * a2) + x2 * (a3 + x * a4))
290// LEN = 6: (a0 + x * a1) + x2 * ((a2 + x * a3) + x2 * (a4 + x * a5))
291// LEN = 7: ((a0 + x * a1) + x2 * (a2 + x * a3))
292// + x4 * (a4 + x * (a5 + x * a6))
293// LEN = 8: ((a0 + x * a1) + x2 * (a2 + x * a3))
294// + x4 * ((a4 + x * a5) + x2 * (a6 + x * a7))
295template <size_t OFFSET, size_t LEN, typename T, size_t N, size_t MAX_K>
296LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
297estrin_eval_tree(const EstrinPows<T, MAX_K> &pows, const T (&a)[N]) {
298 if constexpr (LEN == 1) {
299 return a[OFFSET];
300 } else if constexpr (LEN == 2) {
301 return multiply_add(pows.template get<0>(), a[OFFSET + 1], a[OFFSET]);
302 } else {
303 constexpr size_t K = estrin_split_log2(len: LEN);
304 constexpr size_t LOW = size_t(1) << K;
305 if constexpr (LOW == 1) {
306 T hi = estrin_eval_tree<OFFSET + 1, LEN - 1>(pows, a);
307 return multiply_add(pows.template get<0>(), hi, a[OFFSET]);
308 } else {
309 T lo = estrin_eval_tree<OFFSET, LOW>(pows, a);
310 T hi = estrin_eval_tree<OFFSET + LOW, LEN - LOW>(pows, a);
311 return multiply_add(pows.template get<K>(), hi, lo);
312 }
313 }
314}
315
316template <size_t OFFSET, size_t LEN, typename T, size_t N, size_t MAX_K>
317LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
318estrin_eval_tree(const EstrinPows<T, MAX_K> &pows, const T (&a)[N]) {
319 if constexpr (LEN == 1) {
320 return a[OFFSET];
321 } else if constexpr (LEN == 2) {
322 return multiply_add(pows.template get<0>(), a[OFFSET + 1], a[OFFSET]);
323 } else {
324 constexpr size_t K = estrin_split_log2(len: LEN);
325 constexpr size_t LOW = size_t(1) << K;
326 if constexpr (LOW == 1) {
327 T hi = estrin_eval_tree<OFFSET + 1, LEN - 1>(pows, a);
328 return multiply_add(pows.template get<0>(), hi, a[OFFSET]);
329 } else {
330 T lo = estrin_eval_tree<OFFSET, LOW>(pows, a);
331 T hi = estrin_eval_tree<OFFSET + LOW, LEN - LOW>(pows, a);
332 return multiply_add(pows.template get<K>(), hi, lo);
333 }
334 }
335}
336
337} // namespace internal
338
339// Evaluate polynomial using Estrin's scheme:
340// estrin_polyeval(x, a_0, a_1, ..., a_n) = a_0 + a_1 * x + ... + a_n * x^n.
341template <size_t OFFSET = 0, typename T, size_t N>
342LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
343estrin_polyeval([[maybe_unused]] T x, const T (&a)[N]) {
344 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
345 constexpr size_t LEN = N - OFFSET;
346 if constexpr (LEN == 1) {
347 return a[OFFSET];
348 } else {
349 constexpr size_t MAX_K = internal::estrin_max_power_log2(len: LEN);
350 internal::EstrinPows<T, MAX_K> pows(x);
351 return internal::estrin_eval_tree<OFFSET, LEN>(pows, a);
352 }
353}
354
355template <size_t OFFSET = 0, typename T, size_t N>
356LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
357estrin_polyeval([[maybe_unused]] const T &x, const T (&a)[N]) {
358 static_assert(OFFSET < N, "OFFSET must be less than array size N.");
359 constexpr size_t LEN = N - OFFSET;
360 if constexpr (LEN == 1) {
361 return a[OFFSET];
362 } else {
363 constexpr size_t MAX_K = internal::estrin_max_power_log2(len: LEN);
364 internal::EstrinPows<T, MAX_K> pows(x);
365 return internal::estrin_eval_tree<OFFSET, LEN>(pows, a);
366 }
367}
368
369template <typename T, typename... Ts>
370LIBC_ALWAYS_INLINE constexpr cpp::enable_if_t<(sizeof(T) <= sizeof(double)), T>
371estrin_polyeval([[maybe_unused]] T x, T a0, Ts... a) {
372 static_assert((cpp::is_same_v<T, Ts> && ...),
373 "All coefficients must have the same type T.");
374 if constexpr (sizeof...(Ts) == 0) {
375 return a0;
376 } else {
377 const T coeffs[] = {a0, a...};
378 return estrin_polyeval(x, coeffs);
379 }
380}
381
382template <typename T, typename... Ts>
383LIBC_INLINE constexpr cpp::enable_if_t<(sizeof(T) > sizeof(double)), T>
384estrin_polyeval([[maybe_unused]] const T &x, const T &a0, const Ts &...a) {
385 static_assert((cpp::is_same_v<T, Ts> && ...),
386 "All coefficients must have the same type T.");
387 if constexpr (sizeof...(Ts) == 0) {
388 return a0;
389 } else {
390 const T coeffs[] = {a0, a...};
391 return estrin_polyeval(x, coeffs);
392 }
393}
394
395} // namespace fputil
396} // namespace LIBC_NAMESPACE_DECL
397
398#endif // LLVM_LIBC_SRC___SUPPORT_FPUTIL_POLYEVAL_H
399