vasnprintf: optimize

[Bruno Haible]

The code in lib/integer_length.c can be used to optimize part of the
division routine in lib/vasnprintf.c.


2011-10-15  Bruno Haible  <address@hidden>

        vasnprintf: Optimize bit search operation.
        * lib/vasnprintf.c (divide): Use optimizations from integer_length.c.
        * m4/vasnprintf.m4 (gl_PREREQ_VASNPRINTF): Require
        gl_DOUBLE_EXPONENT_LOCATION.
        * modules/vasnprintf (Files): Add m4/exponentd.m4.
        * modules/unistdio/u8-vasnprintf (Files): Likewise.
        * modules/unistdio/u8-u8-vasnprintf (Files): Likewise.
        * modules/unistdio/u16-vasnprintf (Files): Likewise.
        * modules/unistdio/u16-u16-vasnprintf (Files): Likewise.
        * modules/unistdio/u32-vasnprintf (Files): Likewise.
        * modules/unistdio/u32-u32-vasnprintf (Files): Likewise.
        * modules/unistdio/ulc-vasnprintf (Files): Likewise.
        * m4/isnand.m4 (gl_PREREQ_ISNAND): Use AC_REQUIRE.

--- lib/vasnprintf.c.orig       Sat Oct 15 12:48:21 2011
+++ lib/vasnprintf.c    Sat Oct 15 12:37:53 2011
@@ -553,32 +553,61 @@
       size_t s;
       {
         mp_limb_t msd = b_ptr[b_len - 1]; /* = b[n-1], > 0 */
-        s = 31;
-        if (msd >= 0x10000)
+        /* Determine s = GMP_LIMB_BITS - integer_length (msd).
+           Code copied from gnulib's integer_length.c.  */
+# if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+        s = __builtin_clz (msd);
+# else
+#  if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT
+        if (GMP_LIMB_BITS <= DBL_MANT_BIT)
           {
-            msd = msd >> 16;
-            s -= 16;
+            /* Use 'double' operations.
+               Assumes an IEEE 754 'double' implementation.  */
+#   define DBL_EXP_MASK ((DBL_MAX_EXP - DBL_MIN_EXP) | 7)
+#   define DBL_EXP_BIAS (DBL_EXP_MASK / 2 - 1)
+#   define NWORDS \
+     ((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int))
+            union { double value; unsigned int word[NWORDS]; } m;
+
+            /* Use a single integer to floating-point conversion.  */
+            m.value = msd;
+
+            s = GMP_LIMB_BITS
+                - (((m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & 
DBL_EXP_MASK)
+                   - DBL_EXP_BIAS);
           }
-        if (msd >= 0x100)
+        else
+#   undef NWORDS
+#  endif
           {
-            msd = msd >> 8;
-            s -= 8;
-          }
-        if (msd >= 0x10)
-          {
-            msd = msd >> 4;
-            s -= 4;
-          }
-        if (msd >= 0x4)
-          {
-            msd = msd >> 2;
-            s -= 2;
-          }
-        if (msd >= 0x2)
-          {
-            msd = msd >> 1;
-            s -= 1;
+            s = 31;
+            if (msd >= 0x10000)
+              {
+                msd = msd >> 16;
+                s -= 16;
+              }
+            if (msd >= 0x100)
+              {
+                msd = msd >> 8;
+                s -= 8;
+              }
+            if (msd >= 0x10)
+              {
+                msd = msd >> 4;
+                s -= 4;
+              }
+            if (msd >= 0x4)
+              {
+                msd = msd >> 2;
+                s -= 2;
+              }
+            if (msd >= 0x2)
+              {
+                msd = msd >> 1;
+                s -= 1;
+              }
           }
+# endif
       }
       /* 0 <= s < GMP_LIMB_BITS.
          Copy b, shifting it left by s bits.  */
--- m4/isnand.m4.orig   Sat Oct 15 12:48:22 2011
+++ m4/isnand.m4        Sat Oct 15 12:45:33 2011
@@ -1,4 +1,4 @@
-# isnand.m4 serial 10
+# isnand.m4 serial 11
 dnl Copyright (C) 2007-2011 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
@@ -43,7 +43,7 @@
 dnl Prerequisites of replacement isnand definition. It does not need -lm.
 AC_DEFUN([gl_PREREQ_ISNAND],
 [
-  gl_DOUBLE_EXPONENT_LOCATION
+  AC_REQUIRE([gl_DOUBLE_EXPONENT_LOCATION])
 ])
 
 dnl Test whether isnand() can be used with libm.
--- m4/vasnprintf.m4.orig       Sat Oct 15 12:48:22 2011
+++ m4/vasnprintf.m4    Sat Oct 15 12:26:19 2011
@@ -1,4 +1,4 @@
-# vasnprintf.m4 serial 33
+# vasnprintf.m4 serial 34
 dnl Copyright (C) 2002-2004, 2006-2011 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
@@ -64,6 +64,9 @@
   dnl Use the _snprintf function only if it is declared (because on NetBSD it
   dnl is defined as a weak alias of snprintf; we prefer to use the latter).
   AC_CHECK_DECLS([_snprintf], , , [[#include <stdio.h>]])
+  dnl Knowing DBL_EXPBIT0_WORD and DBL_EXPBIT0_BIT enables an optimization
+  dnl in the code for NEED_PRINTF_LONG_DOUBLE || NEED_PRINTF_DOUBLE.
+  AC_REQUIRE([gl_DOUBLE_EXPONENT_LOCATION])
   dnl We can avoid a lot of code by assuming that snprintf's return value
   dnl conforms to ISO C99. So check that.
   AC_REQUIRE([gl_SNPRINTF_RETVAL_C99])
--- modules/unistdio/u16-u16-vasnprintf.orig    Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u16-u16-vasnprintf Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/u16-vasnprintf.orig        Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u16-vasnprintf     Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/u32-u32-vasnprintf.orig    Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u32-u32-vasnprintf Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/u32-vasnprintf.orig        Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u32-vasnprintf     Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/u8-u8-vasnprintf.orig      Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u8-u8-vasnprintf   Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/u8-vasnprintf.orig Sat Oct 15 12:48:22 2011
+++ modules/unistdio/u8-vasnprintf      Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/unistdio/ulc-vasnprintf.orig        Sat Oct 15 12:48:22 2011
+++ modules/unistdio/ulc-vasnprintf     Sat Oct 15 12:20:54 2011
@@ -13,6 +13,7 @@
 m4/intmax_t.m4
 m4/stdint_h.m4
 m4/inttypes_h.m4
+m4/exponentd.m4
 
 Depends-on:
 unistdio/base
--- modules/vasnprintf.orig     Sat Oct 15 12:48:22 2011
+++ modules/vasnprintf  Sat Oct 15 12:20:53 2011
@@ -19,6 +19,7 @@
 m4/vasnprintf.m4
 m4/printf.m4
 m4/math_h.m4
+m4/exponentd.m4
 
 Depends-on:
 alloca-opt

-- 
In memoriam Thomas Sankara <http://en.wikipedia.org/wiki/Thomas_Sankara>