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/// Double-precision implementation of log2f.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_LOG2F_DOUBLE_EVAL_H
15#define LLVM_LIBC_SRC___SUPPORT_MATH_LOG2F_DOUBLE_EVAL_H
16
17#include "src/__support/FPUtil/FEnvImpl.h"
18#include "src/__support/FPUtil/FPBits.h"
19#include "src/__support/FPUtil/multiply_add.h"
20#include "src/__support/FPUtil/polyeval.h"
21#include "src/__support/common.h"
22#include "src/__support/macros/config.h"
23#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
24#include "src/__support/macros/properties/cpu_features.h"
25#include "src/__support/math/common_constants.h" // Lookup table for (1/f)
26
27// This is a correctly-rounded algorithm for log2(x) in single precision with
28// round-to-nearest, tie-to-even mode from the RLIBM project at:
29// https://people.cs.rutgers.edu/~sn349/rlibm
30
31// Step 1 - Range reduction:
32// For x = 2^m * 1.mant, log2(x) = m + log2(1.m)
33// If x is denormal, convert its integer significand to float exactly and
34// account for the 2^-149 subnormal scale in m.
35
36// Step 2 - Another range reduction:
37// To compute log(1.mant), let f be the highest 8 bits including the hidden
38// bit, and d be the difference (1.mant - f), i.e. the remaining 16 bits of the
39// mantissa. Then we have the following approximation formula:
40// log2(1.mant) = log2(f) + log2(1.mant / f)
41// = log2(f) + log2(1 + d/f)
42// ~ log2(f) + P(d/f)
43// since d/f is sufficiently small.
44// log2(f) and 1/f are then stored in two 2^7 = 128 entries look-up tables.
45
46// Step 3 - Polynomial approximation:
47// To compute P(d/f), we use a single degree-5 polynomial in double precision
48// which provides correct rounding for all but few exception values.
49// For more detail about how this polynomial is obtained, please refer to the
50// papers:
51// Lim, J. and Nagarakatte, S., "One Polynomial Approximation to Produce
52// Correctly Rounded Results of an Elementary Function for Multiple
53// Representations and Rounding Modes", Proceedings of the 49th ACM SIGPLAN
54// Symposium on Principles of Programming Languages (POPL-2022), Philadelphia,
55// USA, Jan. 16-22, 2022.
56// https://people.cs.rutgers.edu/~sn349/papers/rlibmall-popl-2022.pdf
57// Aanjaneya, M., Lim, J., and Nagarakatte, S., "RLibm-Prog: Progressive
58// Polynomial Approximations for Fast Correctly Rounded Math Libraries",
59// Dept. of Comp. Sci., Rutgets U., Technical Report DCS-TR-758, Nov. 2021.
60// https://arxiv.org/pdf/2111.12852.pdf.
61
62namespace LIBC_NAMESPACE_DECL {
63namespace math {
64namespace double_eval {
65
66LIBC_INLINE float log2f(float x) {
67 using namespace common_constants_internal;
68 using FPBits = typename fputil::FPBits<float>;
69
70 FPBits xbits(x);
71 uint32_t x_u = xbits.uintval();
72
73 int m = -FPBits::EXP_BIAS;
74
75 // log2(1.0f) = 0.0f.
76 if (LIBC_UNLIKELY(x_u == 0x3f80'0000U))
77 return 0.0f;
78
79 // Exceptional inputs.
80 if (LIBC_UNLIKELY(x_u < FPBits::min_normal().uintval() ||
81 x_u > FPBits::max_normal().uintval())) {
82 if (x == 0.0f) {
83 fputil::set_errno_if_required(ERANGE);
84 fputil::raise_except_if_required(FE_DIVBYZERO);
85 return FPBits::inf(sign: Sign::NEG).get_val();
86 }
87 if (xbits.is_neg() && !xbits.is_nan()) {
88 fputil::set_errno_if_required(EDOM);
89 fputil::raise_except_if_required(FE_INVALID);
90 return FPBits::quiet_nan().get_val();
91 }
92 if (xbits.is_inf_or_nan()) {
93 return x;
94 }
95 // Normalize denormal inputs.
96 xbits = FPBits(static_cast<float>(static_cast<int32_t>(x_u)));
97 m -= 149;
98 }
99
100 m += xbits.get_biased_exponent();
101 int index = xbits.get_mantissa() >> 16;
102 // Set bits to 1.m
103 xbits.set_biased_exponent(0x7F);
104
105 float u = xbits.get_val();
106#ifdef LIBC_TARGET_CPU_HAS_FMA_FLOAT
107 double v =
108 static_cast<double>(fputil::multiply_sub(u, R[index], 1.0f)); // Exact.
109#else
110 double v =
111 fputil::multiply_sub(x: static_cast<double>(u), y: RD[index], z: 1.0); // Exact
112#endif // LIBC_TARGET_CPU_HAS_FMA_FLOAT
113
114 double extra_factor = static_cast<double>(m) + LOG2_R[index];
115
116 // Degree-5 polynomial approximation of log2 generated by Sollya with:
117 // > P = fpminimax(log2(1 + x)/x, 4, [|1, D...|], [-2^-8, 2^-7]);
118 constexpr double COEFFS[5] = {0x1.71547652b8133p0, -0x1.71547652d1e33p-1,
119 0x1.ec70a098473dep-2, -0x1.7154c5ccdf121p-2,
120 0x1.2514fd90a130ap-2};
121
122 double vsq = v * v; // Exact
123 double c0 = fputil::multiply_add(x: v, y: COEFFS[0], z: extra_factor);
124 double c1 = fputil::multiply_add(x: v, y: COEFFS[2], z: COEFFS[1]);
125 double c2 = fputil::multiply_add(x: v, y: COEFFS[4], z: COEFFS[3]);
126
127 double r = fputil::polyeval(x: vsq, a0: c0, a: c1, a: c2);
128
129 return static_cast<float>(r);
130}
131
132} // namespace double_eval
133} // namespace math
134} // namespace LIBC_NAMESPACE_DECL
135
136#endif // LLVM_LIBC_SRC___SUPPORT_MATH_LOG2F_DOUBLE_EVAL_H
137