Improve performance of sinf/cosf/sincosf

This patch is a complete rewrite of sinf, cosf and sincosf.  The new version
is significantly faster, as well as simple and accurate.
The worst-case ULP is 0.56072, maximum relative error is 0.5303p-23 over all
4 billion inputs.  In non-nearest rounding modes the error is 1ULP.

The algorithm uses 3 main cases: small inputs which don't need argument
reduction, small inputs which need a simple range reduction and large inputs
requiring complex range reduction.  The code uses approximate integer
comparisons to quickly decide between these cases - on some targets this may
be slow, so this can be configured to use floating point comparisons.

The small range reducer uses a single reduction step to handle values up to
120.0.  It is fastest on targets which support inlined round instructions.

The large range reducer uses integer arithmetic for simplicity.  It does a
32x96 bit multiply to compute a 64-bit modulo result.  This is more than
accurate enough to handle the worst-case cancellation for values close to
an integer multiple of PI/4.  It could be further optimized, however it is
already much faster than necessary.

6 files changed, 511 insertions, 0 deletions

diff --git a/math/cosf.c b/math/cosf.c
index 6b5284c..de664ea 100644
--- a/math/cosf.c
+++ b/math/cosf.c
@@ -1 +1,82 @@
+/*
+ * Single-precision cos function.
+ *
+ * Copyright (c) 2018, Arm Limited.
+ * SPDX-License-Identifier: Apache-2.0
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#if WANT_SINGLEPREC
 #include "single/s_cosf.c"
+#else
+
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+#include "sincosf.h"
+
+/* Fast cosf implementation.  Worst-case ULP is 0.56072, maximum relative
+   error is 0.5303p-23.  A single-step signed range reduction is used for
+   small values.  Large inputs have their range reduced using fast integer
+   arithmetic.
+*/
+float
+cosf (float y)
+{
+  double x = y;
+  double s;
+  int n;
+  sincos_t *p = &sincosf_table[0];
+
+  if (abstop12 (y) < abstop12 (pio4))
+    {
+      double x2 = x * x;
+
+      if (unlikely (abstop12 (y) < abstop12 (0x1p-12f)))
+	return 1.0f;
+
+      return sinf_poly (x, x2, p, 1);
+    }
+  else if (likely (abstop12 (y) < abstop12 (120.0f)))
+    {
+      x = reduce_fast (x, p, &n);
+
+      /* Setup the signs for sin and cos.  */
+      s = p->sign[n & 3];
+
+      if (n & 2)
+	p = &sincosf_table[1];
+
+      return sinf_poly (x * s, x * x, p, n ^ 1);
+    }
+  else if (abstop12 (y) < abstop12 (INFINITY))
+    {
+      uint32_t xi = asuint (y);
+      int sign = xi >> 31;
+
+      x = reduce_large (xi, &n);
+
+      /* Setup signs for sin and cos - include original sign.  */
+      s = p->sign[(n + sign) & 3];
+
+      if ((n + sign) & 2)
+	p = &sincosf_table[1];
+
+      return sinf_poly (x * s, x * x, p, n ^ 1);
+    }
+  else
+    return __math_invalidf (y);
+}
+
+#endif
diff --git a/math/include/mathlib.h b/math/include/mathlib.h
index 43962ab..dff4922 100644
--- a/math/include/mathlib.h
+++ b/math/include/mathlib.h
@@ -25,3 +25,6 @@ float exp2f(float);
 float logf(float);
 float log2f(float);
 float powf(float, float);
+float sinf(float);
+float cosf(float);
+void sincosf(float, float*, float*);
diff --git a/math/sincosf.c b/math/sincosf.c
new file mode 100644
index 0000000..4ea2b1d
--- /dev/null
+++ b/math/sincosf.c
@@ -0,0 +1,98 @@
+/*
+ * Single-precision sin/cos function.
+ *
+ * Copyright (c) 2018, Arm Limited.
+ * SPDX-License-Identifier: Apache-2.0
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#if WANT_SINGLEPREC
+#include "single/s_sincosf.c"
+#else
+
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+#include "sincosf.h"
+
+/* Fast sincosf implementation.  Worst-case ULP is 0.56072, maximum relative
+   error is 0.5303p-23.  A single-step signed range reduction is used for
+   small values.  Large inputs have their range reduced using fast integer
+   arithmetic.
+*/
+void
+sincosf (float y, float *sinp, float *cosp)
+{
+  double x = y;
+  double s;
+  int n;
+  sincos_t *p = &sincosf_table[0];
+
+  if (abstop12 (y) < abstop12 (pio4))
+    {
+      double x2 = x * x;
+
+      if (unlikely (abstop12 (y) < abstop12 (0x1p-12f)))
+      {
+	if (unlikely (abstop12 (y) < abstop12 (0x1p-126f)))
+	  /* Force underflow for tiny y.  */
+	  force_eval_float (x2);
+	*sinp = y;
+	*cosp = 1.0f;
+	return;
+      }
+
+      sincosf_poly (x, x2, p, 0, sinp, cosp);
+    }
+  else if (abstop12 (y) < abstop12 (120.0f))
+    {
+      x = reduce_fast (x, p, &n);
+
+      /* Setup the signs for sin and cos.  */
+      s = p->sign[n & 3];
+
+      if (n & 2)
+	p = &sincosf_table[1];
+
+      sincosf_poly (x * s, x * x, p, n, sinp, cosp);
+    }
+  else if (likely (abstop12 (y) < abstop12 (INFINITY)))
+    {
+      uint32_t xi = asuint (y);
+      int sign = xi >> 31;
+
+      x = reduce_large (xi, &n);
+
+      /* Setup signs for sin and cos - include original sign.  */
+      s = p->sign[(n + sign) & 3];
+
+      if ((n + sign) & 2)
+	p = &sincosf_table[1];
+
+      sincosf_poly (x * s, x * x, p, n, sinp, cosp);
+    }
+  else
+    {
+      /* Return NaN if Inf or NaN for both sin and cos.  */
+      *sinp = *cosp = y - y;
+#if WANT_ERRNO
+      /* Needed to set errno for +-Inf, the add is a hack to work
+	 around a gcc register allocation issue: just passing y
+	 affects code generation in the fast path.  */
+      __math_invalidf (y + y);
+#endif
+    }
+}
+
+#endif
diff --git a/math/sincosf.h b/math/sincosf.h
new file mode 100644
index 0000000..afe8b64
--- /dev/null
+++ b/math/sincosf.h
@@ -0,0 +1,165 @@
+/*
+ * Header for sinf, cosf and sincosf.
+ *
+ * Copyright (c) 2018, Arm Limited.
+ * SPDX-License-Identifier: Apache-2.0
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+
+/* PI * 2^-64.  */
+static const double pi64 = 0x1.921FB54442D18p-62;
+/* PI / 4.  */
+static const double pio4 = 0x1.921FB54442D18p-1;
+
+typedef const struct
+{
+  double sign[4];
+  double hpi_inv, hpi, c0, c1, c2, c3, c4, s1, s2, s3;
+} sincos_t;
+
+extern sincos_t sincosf_table[2] HIDDEN;
+
+extern const uint32_t inv_pio4[] HIDDEN;
+
+/* abstop12 assumes floating point reinterpret is fast by default.
+   If floating point comparisons are faster, define PREFER_FLOAT_COMPARISON.  */
+#if PREFER_FLOAT_COMPARISON
+static inline float
+abstop12 (float x)
+{
+  return fabsf (x);
+}
+#else
+static inline uint32_t
+abstop12 (float x)
+{
+  return (asuint (x) >> 20) & 0x7ff;
+}
+#endif
+
+/* Compute the sine and cosine of inputs X and X2 (X squared), using the
+   polynomial P and store the results in SINP and COSP.  N is the quadrant,
+   if odd the cosine and sine polynomials are swapped.  */
+static inline void
+sincosf_poly (double x, double x2, sincos_t *p, int n, float *sinp, float *cosp)
+{
+  double x3, x4, x5, x6, s, c, c1, c2, s1;
+
+  x4 = x2 * x2;
+  x3 = x2 * x;
+  c2 = p->c3 + x2 * p->c4;
+  s1 = p->s2 + x2 * p->s3;
+
+  /* Swap sin/cos result based on quadrant.  */
+  float *tmp = (n & 1 ? cosp : sinp);
+  cosp = (n & 1 ? sinp : cosp);
+  sinp = tmp;
+
+  c1 = p->c0 + x2 * p->c1;
+  x5 = x3 * x2;
+  x6 = x4 * x2;
+
+  s = x + x3 * p->s1;
+  c = c1 + x4 * p->c2;
+
+  *sinp = s + x5 * s1;
+  *cosp = c + x6 * c2;
+}
+
+/* Return the sine of inputs X and X2 (X squared) using the polynomial P.
+   N is the quadrant, and if odd the cosine polynomial is used.  */
+static inline float
+sinf_poly (double x, double x2, sincos_t *p, int n)
+{
+  double x3, x4, x6, x7, s, c, c1, c2, s1;
+
+  if ((n & 1) == 0)
+    {
+      x3 = x * x2;
+      s1 = p->s2 + x2 * p->s3;
+
+      x7 = x3 * x2;
+      s = x + x3 * p->s1;
+
+      return s + x7 * s1;
+    }
+  else
+    {
+      x4 = x2 * x2;
+      c2 = p->c3 + x2 * p->c4;
+      c1 = p->c0 + x2 * p->c1;
+
+      x6 = x4 * x2;
+      c = c1 + x4 * p->c2;
+
+      return c + x6 * c2;
+    }
+}
+
+/* Fast range reduction using single multiply-subtract.  Return the modulo of
+   X as a value between -PI/4 and PI/4 and store the quadrant in NP.
+   The values for PI/2 and 2/PI are accessed via P.  Since PI/2 as a double
+   is accurate to 55 bits and the worst-case cancellation happens at 6 * PI/4,
+   only 2 multiplies are required and the result is accurate for |X| <= 120.0.
+   Use round/lround if inlined, otherwise convert to int.  To avoid inaccuracies
+   introduced by truncating negative values, compute the quadrant * 2^24.  */
+static inline double
+reduce_fast (double x, sincos_t *p, int *np)
+{
+  double r;
+#if TOINT_INTRINSICS
+  r = x * p->hpi_inv;
+  *np = converttoint (r);
+  return x - roundtoint (r) * p->hpi;
+#else
+  r = x * p->hpi_inv;
+  int n = ((int)r + 0x800000) >> 24;
+  *np = n;
+  return x - n * p->hpi;
+#endif
+}
+
+/* Reduce the range of XI to a multiple of PI/4 using fast integer arithmetic.
+   XI is a reinterpreted float and must be >= 2.0f (the sign bit is ignored).
+   Return the modulo between -PI/4 and PI/4 and store the quadrant in NP.
+   Reduction uses a table of 4/PI with 192 bits of precision.  A 32x96->128 bit
+   multiply computes the exact 2.62-bit fixed-point modulo.  Since the result
+   can have at most 29 leading zeros after the binary point, the double
+   precision result is accurate to 33 bits.  */
+static inline double
+reduce_large (uint32_t xi, int *np)
+{
+  const uint32_t *arr = &inv_pio4[(xi >> 26) & 15];
+  int shift = (xi >> 23) & 7;
+  uint64_t n, res0, res1, res2;
+
+  xi = (xi & 0xffffff) | 0x800000;
+  xi <<= shift;
+
+  res0 = xi * arr[0];
+  res1 = (uint64_t)xi * arr[4];
+  res2 = (uint64_t)xi * arr[8];
+  res0 = (res2 >> 32) | (res0 << 32);
+  res0 += res1;
+
+  n = (res0 + (1ULL << 61)) >> 62;
+  res0 -= n << 62;
+  double x = (int64_t)res0;
+  *np = n;
+  return x * pi64;
+}
diff --git a/math/sincosf_data.c b/math/sincosf_data.c
new file mode 100644
index 0000000..ee6aeb9
--- /dev/null
+++ b/math/sincosf_data.c
@@ -0,0 +1,79 @@
+/*
+ * Data definition for sinf, cosf and sincosf.
+ *
+ * Copyright (c) 2018, Arm Limited.
+ * SPDX-License-Identifier: Apache-2.0
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#if !WANT_SINGLEPREC
+
+#include <stdint.h>
+#include <math.h>
+#include "math_config.h"
+#include "sincosf.h"
+
+/* The constants and polynomials for sine and cosine.  The 2nd entry
+   computes -cos (x) rather than cos (x) to get negation for free.  */
+sincos_t sincosf_table[2] =
+{
+  {
+    { 1.0, -1.0, -1.0, 1.0 },
+#if HAVE_FAST_ROUND
+    0x1.45F306DC9C883p-1,
+#else
+    0x1.45F306DC9C883p+23,
+#endif
+    0x1.921FB54442D18p0,
+    0x1p0,
+    -0x1.ffffffd0c621cp-2,
+    0x1.55553e1068f19p-5,
+    -0x1.6c087e89a359dp-10,
+    0x1.99343027bf8c3p-16,
+    -0x1.555545995a603p-3,
+    0x1.1107605230bc4p-7,
+    -0x1.994eb3774cf24p-13
+  },
+  {
+    { 1.0, -1.0, -1.0, 1.0 },
+#if HAVE_FAST_ROUND
+    0x1.45F306DC9C883p-1,
+#else
+    0x1.45F306DC9C883p+23,
+#endif
+    0x1.921FB54442D18p0,
+    -0x1p0,
+    0x1.ffffffd0c621cp-2,
+    -0x1.55553e1068f19p-5,
+    0x1.6c087e89a359dp-10,
+    -0x1.99343027bf8c3p-16,
+    -0x1.555545995a603p-3,
+    0x1.1107605230bc4p-7,
+    -0x1.994eb3774cf24p-13
+  }
+};
+
+/* Table with 4/PI to 192 bit precision.  To avoid unaligned accesses
+   only 8 new bits are added per entry, making the table 4 times larger.  */
+const uint32_t inv_pio4[24] =
+{
+  0xa2,       0xa2f9,	  0xa2f983,   0xa2f9836e,
+  0xf9836e4e, 0x836e4e44, 0x6e4e4415, 0x4e441529,
+  0x441529fc, 0x1529fc27, 0x29fc2757, 0xfc2757d1,
+  0x2757d1f5, 0x57d1f534, 0xd1f534dd, 0xf534ddc0,
+  0x34ddc0db, 0xddc0db62, 0xc0db6295, 0xdb629599,
+  0x6295993c, 0x95993c43, 0x993c4390, 0x3c439041
+};
+
+#endif
diff --git a/math/sinf.c b/math/sinf.c
index 859e9ba..3c7dfe3 100644
--- a/math/sinf.c
+++ b/math/sinf.c
@@ -1 +1,86 @@
+/*
+ * Single-precision sin function.
+ *
+ * Copyright (c) 2018, Arm Limited.
+ * SPDX-License-Identifier: Apache-2.0
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#if WANT_SINGLEPREC
 #include "single/s_sinf.c"
+#else
+
+#include <math.h>
+#include "math_config.h"
+#include "sincosf.h"
+
+/* Fast sinf implementation.  Worst-case ULP is 0.56072, maximum relative
+   error is 0.5303p-23.  A single-step signed range reduction is used for
+   small values.  Large inputs have their range reduced using fast integer
+   arithmetic.
+*/
+float
+sinf (float y)
+{
+  double x = y;
+  double s;
+  int n;
+  sincos_t *p = &sincosf_table[0];
+
+  if (abstop12 (y) < abstop12 (pio4))
+    {
+      s = x * x;
+
+      if (unlikely (abstop12 (y) < abstop12 (0x1p-12f)))
+      {
+	if (unlikely (abstop12 (y) < abstop12 (0x1p-126f)))
+	  /* Force underflow for tiny y.  */
+	  force_eval_float (s);
+	return y;
+      }
+
+      return sinf_poly (x, s, p, 0);
+    }
+  else if (likely (abstop12 (y) < abstop12 (120.0f)))
+    {
+      x = reduce_fast (x, p, &n);
+
+      /* Setup the signs for sin and cos.  */
+      s = p->sign[n & 3];
+
+      if (n & 2)
+	p = &sincosf_table[1];
+
+      return sinf_poly (x * s, x * x, p, n);
+    }
+  else if (abstop12 (y) < abstop12 (INFINITY))
+    {
+      uint32_t xi = asuint (y);
+      int sign = xi >> 31;
+
+      x = reduce_large (xi, &n);
+
+      /* Setup signs for sin and cos - include original sign.  */
+      s = p->sign[(n + sign) & 3];
+
+      if ((n + sign) & 2)
+	p = &sincosf_table[1];
+
+      return sinf_poly (x * s, x * x, p, n);
+    }
+  else
+    return __math_invalidf (y);
+}
+
+#endif