xref: /llvm-project/libc/src/math/generic/log2f.cpp (revision 0f4b3c409fbd756d826c89d5539d9ea22bcc56aa)
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