| 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 | |
| 62 | namespace LIBC_NAMESPACE_DECL { |
| 63 | namespace math { |
| 64 | namespace double_eval { |
| 65 | |
| 66 | LIBC_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 = 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 | |