163d2df00STue Ly //===-- Single-precision log2(x) function ---------------------------------===// 263d2df00STue Ly // 363d2df00STue Ly // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 463d2df00STue Ly // See https://llvm.org/LICENSE.txt for license information. 563d2df00STue Ly // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 663d2df00STue Ly // 763d2df00STue Ly //===----------------------------------------------------------------------===// 863d2df00STue Ly 963d2df00STue Ly #include "src/math/log2f.h" 1063d2df00STue Ly #include "common_constants.h" // Lookup table for (1/f) 1176ec69a9STue Ly #include "src/__support/FPUtil/FEnvImpl.h" 1263d2df00STue Ly #include "src/__support/FPUtil/FPBits.h" 1363d2df00STue Ly #include "src/__support/FPUtil/PolyEval.h" 14ae2d8b49STue Ly #include "src/__support/FPUtil/except_value_utils.h" 15ae2d8b49STue Ly #include "src/__support/FPUtil/multiply_add.h" 1663d2df00STue Ly #include "src/__support/common.h" 175ff3ff33SPetr Hosek #include "src/__support/macros/config.h" 184663d784STue Ly #include "src/__support/macros/optimization.h" // LIBC_UNLIKELY 1963d2df00STue Ly 2063d2df00STue Ly // This is a correctly-rounded algorithm for log2(x) in single precision with 2163d2df00STue Ly // round-to-nearest, tie-to-even mode from the RLIBM project at: 2263d2df00STue Ly // https://people.cs.rutgers.edu/~sn349/rlibm 2363d2df00STue Ly 2463d2df00STue Ly // Step 1 - Range reduction: 2563d2df00STue Ly // For x = 2^m * 1.mant, log2(x) = m + log2(1.m) 2663d2df00STue Ly // If x is denormal, we normalize it by multiplying x by 2^23 and subtracting 2763d2df00STue Ly // m by 23. 2863d2df00STue Ly 2963d2df00STue Ly // Step 2 - Another range reduction: 3063d2df00STue Ly // To compute log(1.mant), let f be the highest 8 bits including the hidden 3163d2df00STue Ly // bit, and d be the difference (1.mant - f), i.e. the remaining 16 bits of the 3263d2df00STue Ly // mantissa. Then we have the following approximation formula: 3363d2df00STue Ly // log2(1.mant) = log2(f) + log2(1.mant / f) 3463d2df00STue Ly // = log2(f) + log2(1 + d/f) 3563d2df00STue Ly // ~ log2(f) + P(d/f) 3663d2df00STue Ly // since d/f is sufficiently small. 3763d2df00STue Ly // log2(f) and 1/f are then stored in two 2^7 = 128 entries look-up tables. 3863d2df00STue Ly 3963d2df00STue Ly // Step 3 - Polynomial approximation: 4063d2df00STue Ly // To compute P(d/f), we use a single degree-5 polynomial in double precision 4163d2df00STue Ly // which provides correct rounding for all but few exception values. 4263d2df00STue Ly // For more detail about how this polynomial is obtained, please refer to the 4363d2df00STue Ly // papers: 4463d2df00STue Ly // Lim, J. and Nagarakatte, S., "One Polynomial Approximation to Produce 4563d2df00STue Ly // Correctly Rounded Results of an Elementary Function for Multiple 4663d2df00STue Ly // Representations and Rounding Modes", Proceedings of the 49th ACM SIGPLAN 4763d2df00STue Ly // Symposium on Principles of Programming Languages (POPL-2022), Philadelphia, 4863d2df00STue Ly // USA, Jan. 16-22, 2022. 4963d2df00STue Ly // https://people.cs.rutgers.edu/~sn349/papers/rlibmall-popl-2022.pdf 5063d2df00STue Ly // Aanjaneya, M., Lim, J., and Nagarakatte, S., "RLibm-Prog: Progressive 5163d2df00STue Ly // Polynomial Approximations for Fast Correctly Rounded Math Libraries", 5263d2df00STue Ly // Dept. of Comp. Sci., Rutgets U., Technical Report DCS-TR-758, Nov. 2021. 5363d2df00STue Ly // https://arxiv.org/pdf/2111.12852.pdf. 5463d2df00STue Ly 555ff3ff33SPetr Hosek namespace LIBC_NAMESPACE_DECL { 5663d2df00STue Ly 5763d2df00STue Ly LLVM_LIBC_FUNCTION(float, log2f, (float x)) { 5863d2df00STue Ly using FPBits = typename fputil::FPBits<float>; 592137894aSGuillaume Chatelet 6063d2df00STue Ly FPBits xbits(x); 61ae2d8b49STue Ly uint32_t x_u = xbits.uintval(); 6263d2df00STue Ly 6363d2df00STue Ly // Hard to round value(s). 64ae2d8b49STue Ly using fputil::round_result_slightly_up; 65ae2d8b49STue Ly 663546f4daSGuillaume Chatelet int m = -FPBits::EXP_BIAS; 67ae2d8b49STue Ly 6892bc7f54STue Ly // log2(1.0f) = 0.0f. 6992bc7f54STue Ly if (LIBC_UNLIKELY(x_u == 0x3f80'0000U)) 7092bc7f54STue Ly return 0.0f; 7192bc7f54STue Ly 7263d2df00STue Ly // Exceptional inputs. 736b02d2f8SGuillaume Chatelet if (LIBC_UNLIKELY(x_u < FPBits::min_normal().uintval() || 746b02d2f8SGuillaume Chatelet x_u > FPBits::max_normal().uintval())) { 75*0f4b3c40Slntue if (x == 0.0f) { 7631c39439STue Ly fputil::set_errno_if_required(ERANGE); 7731c39439STue Ly fputil::raise_except_if_required(FE_DIVBYZERO); 786b02d2f8SGuillaume Chatelet return FPBits::inf(Sign::NEG).get_val(); 7963d2df00STue Ly } 8011ec512fSGuillaume Chatelet if (xbits.is_neg() && !xbits.is_nan()) { 8131c39439STue Ly fputil::set_errno_if_required(EDOM); 82ae2d8b49STue Ly fputil::raise_except(FE_INVALID); 83ace383dfSGuillaume Chatelet return FPBits::quiet_nan().get_val(); 8463d2df00STue Ly } 8563d2df00STue Ly if (xbits.is_inf_or_nan()) { 8663d2df00STue Ly return x; 8763d2df00STue Ly } 8863d2df00STue Ly // Normalize denormal inputs. 89d02471edSGuillaume Chatelet xbits = FPBits(xbits.get_val() * 0x1.0p23f); 90ae2d8b49STue Ly m -= 23; 9163d2df00STue Ly } 9263d2df00STue Ly 937b387d27SGuillaume Chatelet m += xbits.get_biased_exponent(); 9492bc7f54STue Ly int index = xbits.get_mantissa() >> 16; 9563d2df00STue Ly // Set bits to 1.m 967b387d27SGuillaume Chatelet xbits.set_biased_exponent(0x7F); 9763d2df00STue Ly 982856db0dSGuillaume Chatelet float u = xbits.get_val(); 9992bc7f54STue Ly double v; 10092bc7f54STue Ly #ifdef LIBC_TARGET_CPU_HAS_FMA 10192bc7f54STue Ly v = static_cast<double>(fputil::multiply_add(u, R[index], -1.0f)); // Exact. 10292bc7f54STue Ly #else 10392bc7f54STue Ly v = fputil::multiply_add(static_cast<double>(u), RD[index], -1.0); // Exact 10492bc7f54STue Ly #endif // LIBC_TARGET_CPU_HAS_FMA 10563d2df00STue Ly 10692bc7f54STue Ly double extra_factor = static_cast<double>(m) + LOG2_R[index]; 10763d2df00STue Ly 10892bc7f54STue Ly // Degree-5 polynomial approximation of log2 generated by Sollya with: 10992bc7f54STue Ly // > P = fpminimax(log2(1 + x)/x, 4, [|1, D...|], [-2^-8, 2^-7]); 11092bc7f54STue Ly constexpr double COEFFS[5] = {0x1.71547652b8133p0, -0x1.71547652d1e33p-1, 11192bc7f54STue Ly 0x1.ec70a098473dep-2, -0x1.7154c5ccdf121p-2, 11292bc7f54STue Ly 0x1.2514fd90a130ap-2}; 113ae2d8b49STue Ly 11492bc7f54STue Ly double vsq = v * v; // Exact 11592bc7f54STue Ly double c0 = fputil::multiply_add(v, COEFFS[0], extra_factor); 11692bc7f54STue Ly double c1 = fputil::multiply_add(v, COEFFS[2], COEFFS[1]); 11792bc7f54STue Ly double c2 = fputil::multiply_add(v, COEFFS[4], COEFFS[3]); 118ae2d8b49STue Ly 11992bc7f54STue Ly double r = fputil::polyeval(vsq, c0, c1, c2); 12063d2df00STue Ly 12163d2df00STue Ly return static_cast<float>(r); 12263d2df00STue Ly } 12363d2df00STue Ly 1245ff3ff33SPetr Hosek } // namespace LIBC_NAMESPACE_DECL 125