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