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