summaryrefslogtreecommitdiff
path: root/src/math/fma.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/fma.c')
-rw-r--r--src/math/fma.c585
1 files changed, 154 insertions, 431 deletions
diff --git a/src/math/fma.c b/src/math/fma.c
index 741ccd75..0c6f90c9 100644
--- a/src/math/fma.c
+++ b/src/math/fma.c
@@ -1,460 +1,183 @@
-#include <fenv.h>
-#include "libm.h"
+#include <stdint.h>
+#include <float.h>
+#include <math.h>
+#include "atomic.h"
-#if LDBL_MANT_DIG==64 && LDBL_MAX_EXP==16384
-/* exact add, assumes exponent_x >= exponent_y */
-static void add(long double *hi, long double *lo, long double x, long double y)
-{
- long double r;
-
- r = x + y;
- *hi = r;
- r -= x;
- *lo = y - r;
-}
-
-/* exact mul, assumes no over/underflow */
-static void mul(long double *hi, long double *lo, long double x, long double y)
-{
- static const long double c = 1.0 + 0x1p32L;
- long double cx, xh, xl, cy, yh, yl;
+#define ASUINT64(x) ((union {double f; uint64_t i;}){x}).i
+#define ZEROINFNAN (0x7ff-0x3ff-52-1)
- cx = c*x;
- xh = (x - cx) + cx;
- xl = x - xh;
- cy = c*y;
- yh = (y - cy) + cy;
- yl = y - yh;
- *hi = x*y;
- *lo = (xh*yh - *hi) + xh*yl + xl*yh + xl*yl;
-}
+struct num { uint64_t m; int e; int sign; };
-/*
-assume (long double)(hi+lo) == hi
-return an adjusted hi so that rounding it to double (or less) precision is correct
-*/
-static long double adjust(long double hi, long double lo)
+static struct num normalize(double x)
{
- union ldshape uhi, ulo;
-
- if (lo == 0)
- return hi;
- uhi.f = hi;
- if (uhi.i.m & 0x3ff)
- return hi;
- ulo.f = lo;
- if ((uhi.i.se & 0x8000) == (ulo.i.se & 0x8000))
- uhi.i.m++;
- else {
- /* handle underflow and take care of ld80 implicit msb */
- if (uhi.i.m << 1 == 0) {
- uhi.i.m = 0;
- uhi.i.se--;
- }
- uhi.i.m--;
+ uint64_t ix = ASUINT64(x);
+ int e = ix>>52;
+ int sign = e & 0x800;
+ e &= 0x7ff;
+ if (!e) {
+ ix = ASUINT64(x*0x1p63);
+ e = ix>>52 & 0x7ff;
+ e = e ? e-63 : 0x800;
}
- return uhi.f;
+ ix &= (1ull<<52)-1;
+ ix |= 1ull<<52;
+ ix <<= 1;
+ e -= 0x3ff + 52 + 1;
+ return (struct num){ix,e,sign};
}
-/* adjusted add so the result is correct when rounded to double (or less) precision */
-static long double dadd(long double x, long double y)
+static void mul(uint64_t *hi, uint64_t *lo, uint64_t x, uint64_t y)
{
- add(&x, &y, x, y);
- return adjust(x, y);
-}
-
-/* adjusted mul so the result is correct when rounded to double (or less) precision */
-static long double dmul(long double x, long double y)
-{
- mul(&x, &y, x, y);
- return adjust(x, y);
-}
-
-static int getexp(long double x)
-{
- union ldshape u;
- u.f = x;
- return u.i.se & 0x7fff;
+ uint64_t t1,t2,t3;
+ uint64_t xlo = (uint32_t)x, xhi = x>>32;
+ uint64_t ylo = (uint32_t)y, yhi = y>>32;
+
+ t1 = xlo*ylo;
+ t2 = xlo*yhi + xhi*ylo;
+ t3 = xhi*yhi;
+ *lo = t1 + (t2<<32);
+ *hi = t3 + (t2>>32) + (t1 > *lo);
}
double fma(double x, double y, double z)
{
#pragma STDC FENV_ACCESS ON
- long double hi, lo1, lo2, xy;
- int round, ez, exy;
- /* handle +-inf,nan */
- if (!isfinite(x) || !isfinite(y))
+ /* normalize so top 10bits and last bit are 0 */
+ struct num nx, ny, nz;
+ nx = normalize(x);
+ ny = normalize(y);
+ nz = normalize(z);
+
+ if (nx.e >= ZEROINFNAN || ny.e >= ZEROINFNAN)
return x*y + z;
- if (!isfinite(z))
+ if (nz.e >= ZEROINFNAN) {
+ if (nz.e > ZEROINFNAN) /* z==0 */
+ return x*y + z;
return z;
- /* handle +-0 */
- if (x == 0.0 || y == 0.0)
- return x*y + z;
- round = fegetround();
- if (z == 0.0) {
- if (round == FE_TONEAREST)
- return dmul(x, y);
- return x*y;
}
- /* exact mul and add require nearest rounding */
- /* spurious inexact exceptions may be raised */
- fesetround(FE_TONEAREST);
- mul(&xy, &lo1, x, y);
- exy = getexp(xy);
- ez = getexp(z);
- if (ez > exy) {
- add(&hi, &lo2, z, xy);
- } else if (ez > exy - 12) {
- add(&hi, &lo2, xy, z);
- if (hi == 0) {
- /*
- xy + z is 0, but it should be calculated with the
- original rounding mode so the sign is correct, if the
- compiler does not support FENV_ACCESS ON it does not
- know about the changed rounding mode and eliminates
- the xy + z below without the volatile memory access
- */
- volatile double z_;
- fesetround(round);
- z_ = z;
- return (xy + z_) + lo1;
+ /* mul: r = x*y */
+ uint64_t rhi, rlo, zhi, zlo;
+ mul(&rhi, &rlo, nx.m, ny.m);
+ /* either top 20 or 21 bits of rhi and last 2 bits of rlo are 0 */
+
+ /* align exponents */
+ int e = nx.e + ny.e;
+ int d = nz.e - e;
+ /* shift bits z<<=kz, r>>=kr, so kz+kr == d, set e = e+kr (== ez-kz) */
+ if (d > 0) {
+ if (d < 64) {
+ zlo = nz.m<<d;
+ zhi = nz.m>>64-d;
+ } else {
+ zlo = 0;
+ zhi = nz.m;
+ e = nz.e - 64;
+ d -= 64;
+ if (d == 0) {
+ } else if (d < 64) {
+ rlo = rhi<<64-d | rlo>>d | !!(rlo<<64-d);
+ rhi = rhi>>d;
+ } else {
+ rlo = 1;
+ rhi = 0;
+ }
}
} else {
- /*
- ez <= exy - 12
- the 12 extra bits (1guard, 11round+sticky) are needed so with
- lo = dadd(lo1, lo2)
- elo <= ehi - 11, and we use the last 10 bits in adjust so
- dadd(hi, lo)
- gives correct result when rounded to double
- */
- hi = xy;
- lo2 = z;
- }
- /*
- the result is stored before return for correct precision and exceptions
-
- one corner case is when the underflow flag should be raised because
- the precise result is an inexact subnormal double, but the calculated
- long double result is an exact subnormal double
- (so rounding to double does not raise exceptions)
-
- in nearest rounding mode dadd takes care of this: the last bit of the
- result is adjusted so rounding sees an inexact value when it should
-
- in non-nearest rounding mode fenv is used for the workaround
- */
- fesetround(round);
- if (round == FE_TONEAREST)
- z = dadd(hi, dadd(lo1, lo2));
- else {
-#if defined(FE_INEXACT) && defined(FE_UNDERFLOW)
- int e = fetestexcept(FE_INEXACT);
- feclearexcept(FE_INEXACT);
-#endif
- z = hi + (lo1 + lo2);
-#if defined(FE_INEXACT) && defined(FE_UNDERFLOW)
- if (getexp(z) < 0x3fff-1022 && fetestexcept(FE_INEXACT))
- feraiseexcept(FE_UNDERFLOW);
- else if (e)
- feraiseexcept(FE_INEXACT);
-#endif
- }
- return z;
-}
-#else
-/* origin: FreeBSD /usr/src/lib/msun/src/s_fma.c */
-/*-
- * Copyright (c) 2005-2011 David Schultz <das@FreeBSD.ORG>
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-/*
- * A struct dd represents a floating-point number with twice the precision
- * of a double. We maintain the invariant that "hi" stores the 53 high-order
- * bits of the result.
- */
-struct dd {
- double hi;
- double lo;
-};
-
-/*
- * Compute a+b exactly, returning the exact result in a struct dd. We assume
- * that both a and b are finite, but make no assumptions about their relative
- * magnitudes.
- */
-static inline struct dd dd_add(double a, double b)
-{
- struct dd ret;
- double s;
-
- ret.hi = a + b;
- s = ret.hi - a;
- ret.lo = (a - (ret.hi - s)) + (b - s);
- return (ret);
-}
-
-/*
- * Compute a+b, with a small tweak: The least significant bit of the
- * result is adjusted into a sticky bit summarizing all the bits that
- * were lost to rounding. This adjustment negates the effects of double
- * rounding when the result is added to another number with a higher
- * exponent. For an explanation of round and sticky bits, see any reference
- * on FPU design, e.g.,
- *
- * J. Coonen. An Implementation Guide to a Proposed Standard for
- * Floating-Point Arithmetic. Computer, vol. 13, no. 1, Jan 1980.
- */
-static inline double add_adjusted(double a, double b)
-{
- struct dd sum;
- union {double f; uint64_t i;} uhi, ulo;
-
- sum = dd_add(a, b);
- if (sum.lo != 0) {
- uhi.f = sum.hi;
- if ((uhi.i & 1) == 0) {
- /* hibits += (int)copysign(1.0, sum.hi * sum.lo) */
- ulo.f = sum.lo;
- uhi.i += 1 - ((uhi.i ^ ulo.i) >> 62);
- sum.hi = uhi.f;
+ zhi = 0;
+ d = -d;
+ if (d == 0) {
+ zlo = nz.m;
+ } else if (d < 64) {
+ zlo = nz.m>>d | !!(nz.m<<64-d);
+ } else {
+ zlo = 1;
}
}
- return (sum.hi);
-}
-
-/*
- * Compute ldexp(a+b, scale) with a single rounding error. It is assumed
- * that the result will be subnormal, and care is taken to ensure that
- * double rounding does not occur.
- */
-static inline double add_and_denormalize(double a, double b, int scale)
-{
- struct dd sum;
- union {double f; uint64_t i;} uhi, ulo;
- int bits_lost;
-
- sum = dd_add(a, b);
-
- /*
- * If we are losing at least two bits of accuracy to denormalization,
- * then the first lost bit becomes a round bit, and we adjust the
- * lowest bit of sum.hi to make it a sticky bit summarizing all the
- * bits in sum.lo. With the sticky bit adjusted, the hardware will
- * break any ties in the correct direction.
- *
- * If we are losing only one bit to denormalization, however, we must
- * break the ties manually.
- */
- if (sum.lo != 0) {
- uhi.f = sum.hi;
- bits_lost = -((int)(uhi.i >> 52) & 0x7ff) - scale + 1;
- if ((bits_lost != 1) ^ (int)(uhi.i & 1)) {
- /* hibits += (int)copysign(1.0, sum.hi * sum.lo) */
- ulo.f = sum.lo;
- uhi.i += 1 - (((uhi.i ^ ulo.i) >> 62) & 2);
- sum.hi = uhi.f;
- }
- }
- return scalbn(sum.hi, scale);
-}
-
-/*
- * Compute a*b exactly, returning the exact result in a struct dd. We assume
- * that both a and b are normalized, so no underflow or overflow will occur.
- * The current rounding mode must be round-to-nearest.
- */
-static inline struct dd dd_mul(double a, double b)
-{
- static const double split = 0x1p27 + 1.0;
- struct dd ret;
- double ha, hb, la, lb, p, q;
-
- p = a * split;
- ha = a - p;
- ha += p;
- la = a - ha;
-
- p = b * split;
- hb = b - p;
- hb += p;
- lb = b - hb;
-
- p = ha * hb;
- q = ha * lb + la * hb;
-
- ret.hi = p + q;
- ret.lo = p - ret.hi + q + la * lb;
- return (ret);
-}
-/*
- * Fused multiply-add: Compute x * y + z with a single rounding error.
- *
- * We use scaling to avoid overflow/underflow, along with the
- * canonical precision-doubling technique adapted from:
- *
- * Dekker, T. A Floating-Point Technique for Extending the
- * Available Precision. Numer. Math. 18, 224-242 (1971).
- *
- * This algorithm is sensitive to the rounding precision. FPUs such
- * as the i387 must be set in double-precision mode if variables are
- * to be stored in FP registers in order to avoid incorrect results.
- * This is the default on FreeBSD, but not on many other systems.
- *
- * Hardware instructions should be used on architectures that support it,
- * since this implementation will likely be several times slower.
- */
-double fma(double x, double y, double z)
-{
- #pragma STDC FENV_ACCESS ON
- double xs, ys, zs, adj;
- struct dd xy, r;
- int oround;
- int ex, ey, ez;
- int spread;
-
- /*
- * Handle special cases. The order of operations and the particular
- * return values here are crucial in handling special cases involving
- * infinities, NaNs, overflows, and signed zeroes correctly.
- */
- if (!isfinite(x) || !isfinite(y))
- return (x * y + z);
- if (!isfinite(z))
- return (z);
- if (x == 0.0 || y == 0.0)
- return (x * y + z);
- if (z == 0.0)
- return (x * y);
-
- xs = frexp(x, &ex);
- ys = frexp(y, &ey);
- zs = frexp(z, &ez);
- oround = fegetround();
- spread = ex + ey - ez;
-
- /*
- * If x * y and z are many orders of magnitude apart, the scaling
- * will overflow, so we handle these cases specially. Rounding
- * modes other than FE_TONEAREST are painful.
- */
- if (spread < -DBL_MANT_DIG) {
-#ifdef FE_INEXACT
- feraiseexcept(FE_INEXACT);
-#endif
-#ifdef FE_UNDERFLOW
- if (!isnormal(z))
- feraiseexcept(FE_UNDERFLOW);
-#endif
- switch (oround) {
- default: /* FE_TONEAREST */
- return (z);
-#ifdef FE_TOWARDZERO
- case FE_TOWARDZERO:
- if (x > 0.0 ^ y < 0.0 ^ z < 0.0)
- return (z);
- else
- return (nextafter(z, 0));
-#endif
-#ifdef FE_DOWNWARD
- case FE_DOWNWARD:
- if (x > 0.0 ^ y < 0.0)
- return (z);
- else
- return (nextafter(z, -INFINITY));
-#endif
-#ifdef FE_UPWARD
- case FE_UPWARD:
- if (x > 0.0 ^ y < 0.0)
- return (nextafter(z, INFINITY));
- else
- return (z);
-#endif
+ /* add */
+ int sign = nx.sign^ny.sign;
+ int samesign = !(sign^nz.sign);
+ int nonzero = 1;
+ if (samesign) {
+ /* r += z */
+ rlo += zlo;
+ rhi += zhi + (rlo < zlo);
+ } else {
+ /* r -= z */
+ uint64_t t = rlo;
+ rlo -= zlo;
+ rhi = rhi - zhi - (t < rlo);
+ if (rhi>>63) {
+ rlo = -rlo;
+ rhi = -rhi-!!rlo;
+ sign = !sign;
}
+ nonzero = !!rhi;
}
- if (spread <= DBL_MANT_DIG * 2)
- zs = scalbn(zs, -spread);
- else
- zs = copysign(DBL_MIN, zs);
-
- fesetround(FE_TONEAREST);
- /*
- * Basic approach for round-to-nearest:
- *
- * (xy.hi, xy.lo) = x * y (exact)
- * (r.hi, r.lo) = xy.hi + z (exact)
- * adj = xy.lo + r.lo (inexact; low bit is sticky)
- * result = r.hi + adj (correctly rounded)
- */
- xy = dd_mul(xs, ys);
- r = dd_add(xy.hi, zs);
-
- spread = ex + ey;
-
- if (r.hi == 0.0) {
- /*
- * When the addends cancel to 0, ensure that the result has
- * the correct sign.
- */
- fesetround(oround);
- volatile double vzs = zs; /* XXX gcc CSE bug workaround */
- return xy.hi + vzs + scalbn(xy.lo, spread);
+ /* set rhi to top 63bit of the result (last bit is sticky) */
+ if (nonzero) {
+ e += 64;
+ d = a_clz_64(rhi)-1;
+ /* note: d > 0 */
+ rhi = rhi<<d | rlo>>64-d | !!(rlo<<d);
+ } else if (rlo) {
+ d = a_clz_64(rlo)-1;
+ if (d < 0)
+ rhi = rlo>>1 | (rlo&1);
+ else
+ rhi = rlo<<d;
+ } else {
+ /* exact +-0 */
+ return x*y + z;
}
-
- if (oround != FE_TONEAREST) {
- /*
- * There is no need to worry about double rounding in directed
- * rounding modes.
- * But underflow may not be raised properly, example in downward rounding:
- * fma(0x1.000000001p-1000, 0x1.000000001p-30, -0x1p-1066)
- */
- double ret;
-#if defined(FE_INEXACT) && defined(FE_UNDERFLOW)
- int e = fetestexcept(FE_INEXACT);
- feclearexcept(FE_INEXACT);
-#endif
- fesetround(oround);
- adj = r.lo + xy.lo;
- ret = scalbn(r.hi + adj, spread);
-#if defined(FE_INEXACT) && defined(FE_UNDERFLOW)
- if (ilogb(ret) < -1022 && fetestexcept(FE_INEXACT))
- feraiseexcept(FE_UNDERFLOW);
- else if (e)
- feraiseexcept(FE_INEXACT);
-#endif
- return ret;
+ e -= d;
+
+ /* convert to double */
+ int64_t i = rhi; /* i is in [1<<62,(1<<63)-1] */
+ if (sign)
+ i = -i;
+ double r = i; /* |r| is in [0x1p62,0x1p63] */
+
+ if (e < -1022-62) {
+ /* result is subnormal before rounding */
+ if (e == -1022-63) {
+ double c = 0x1p63;
+ if (sign)
+ c = -c;
+ if (r == c) {
+ /* min normal after rounding, underflow depends
+ on arch behaviour which can be imitated by
+ a double to float conversion */
+ float fltmin = 0x0.ffffff8p-63*FLT_MIN * r;
+ return DBL_MIN/FLT_MIN * fltmin;
+ }
+ /* one bit is lost when scaled, add another top bit to
+ only round once at conversion if it is inexact */
+ if (rhi << 53) {
+ i = rhi>>1 | (rhi&1) | 1ull<<62;
+ if (sign)
+ i = -i;
+ r = i;
+ r = 2*r - c; /* remove top bit */
+
+ /* raise underflow portably, such that it
+ cannot be optimized away */
+ {
+ double_t tiny = DBL_MIN/FLT_MIN * r;
+ r += (double)(tiny*tiny) * (r-r);
+ }
+ }
+ } else {
+ /* only round once when scaled */
+ d = 10;
+ i = ( rhi>>d | !!(rhi<<64-d) ) << d;
+ if (sign)
+ i = -i;
+ r = i;
+ }
}
-
- adj = add_adjusted(r.lo, xy.lo);
- if (spread + ilogb(r.hi) > -1023)
- return scalbn(r.hi + adj, spread);
- else
- return add_and_denormalize(r.hi, adj, spread);
+ return scalbn(r, e);
}
-#endif