proposed patch to difftime.c and Makefile for tz code

Here's a proposed patch to difftime.c and Makefile to reflect all the recent back-and-forth between Clive D.W. Feather and myself. The main practical import of this patch is the avoidance of a double-rounding bug on hosts with 64-bit time_t and 64-bit 'long double', but it also fixes some much-bigger errors on unusual hosts that have holes in their integer representations. Thanks, Clive! *** Makefile 2004/08/11 15:59:05 2004.3 --- Makefile 2004/08/11 20:30:07 2004.3.0.1 *************** LDLIBS= *** 87,105 **** # Add the following to the end of the "CFLAGS=" line as needed. # -Dconst= if `const' does not work (SunOS 4.x cc, OSF1 V5.0 cc) # -DHAVE_ADJTIME=0 if `adjtime' does not exist (SVR0?) # -DHAVE_GETTEXT=1 if `gettext' works (GNU, Linux, Solaris); also see LDLIBS # -DHAVE_INCOMPATIBLE_CTIME_R=1 if your system's time.h declares # ctime_r and asctime_r incompatibly with the POSIX standard (Solaris 8). ! # -DHAVE_LONG_DOUBLE=1 if your compiler supports the `long double' type # -DHAVE_SETTIMEOFDAY=0 if settimeofday does not exist (SVR0?) # -DHAVE_SETTIMEOFDAY=1 if settimeofday has just 1 arg (SVR4) # -DHAVE_SETTIMEOFDAY=2 if settimeofday uses 2nd arg (4.3BSD) # -DHAVE_SETTIMEOFDAY=3 if settimeofday ignores 2nd arg (4.4BSD) # -DHAVE_STRERROR=0 if your system lacks the strerror function # -DHAVE_SYMLINK=0 if your system lacks the symlink function # -DHAVE_SYS_STAT_H=0 if your compiler lacks a "sys/stat.h" # -DHAVE_SYS_WAIT_H=0 if your compiler lacks a "sys/wait.h" # -DLOCALE_HOME=\"path\" if locales are in "path", not "/usr/lib/locale" # -DHAVE_UNISTD_H=0 if your compiler lacks a "unistd.h" (Microsoft C++ 7?) # -DHAVE_UTMPX_H=1 if your compiler has a "utmpx.h" --- 87,110 ---- # Add the following to the end of the "CFLAGS=" line as needed. # -Dconst= if `const' does not work (SunOS 4.x cc, OSF1 V5.0 cc) + # -Duintmax='unsigned long long int' if your pre-C99 compiler has such a type # -DHAVE_ADJTIME=0 if `adjtime' does not exist (SVR0?) # -DHAVE_GETTEXT=1 if `gettext' works (GNU, Linux, Solaris); also see LDLIBS # -DHAVE_INCOMPATIBLE_CTIME_R=1 if your system's time.h declares # ctime_r and asctime_r incompatibly with the POSIX standard (Solaris 8). ! # -DHAVE_LONG_DOUBLE=1 if your pre-C89 compiler has the `long double' type # -DHAVE_SETTIMEOFDAY=0 if settimeofday does not exist (SVR0?) # -DHAVE_SETTIMEOFDAY=1 if settimeofday has just 1 arg (SVR4) # -DHAVE_SETTIMEOFDAY=2 if settimeofday uses 2nd arg (4.3BSD) # -DHAVE_SETTIMEOFDAY=3 if settimeofday ignores 2nd arg (4.4BSD) + # -DHAVE_STDINT_H=1 if your pre-C99 compiler has a "stdint.h" # -DHAVE_STRERROR=0 if your system lacks the strerror function # -DHAVE_SYMLINK=0 if your system lacks the symlink function # -DHAVE_SYS_STAT_H=0 if your compiler lacks a "sys/stat.h" # -DHAVE_SYS_WAIT_H=0 if your compiler lacks a "sys/wait.h" + # -DINTMAX_MAX=9223372036854775807 (or to the greatest signed integer, + # whatever it is) if your compiler lacks INTMAX_MAX, and if LLONG_MAX + # (or LONG_MAX, if LLONG_MAX is not defined) is not the greatest # -DLOCALE_HOME=\"path\" if locales are in "path", not "/usr/lib/locale" # -DHAVE_UNISTD_H=0 if your compiler lacks a "unistd.h" (Microsoft C++ 7?) # -DHAVE_UTMPX_H=1 if your compiler has a "utmpx.h" *** difftime.c 2002/01/28 15:36:25 2002.2 --- difftime.c 2004/08/11 20:13:16 2002.2.0.3 *************** static char elsieid[] = "@(#)difftime.c *** 14,83 **** #include "private.h" /* ! ** Algorithm courtesy Paul Eggert (eggert@twinsun.com). */ ! #ifdef HAVE_LONG_DOUBLE ! #define long_double long double ! #endif /* defined HAVE_LONG_DOUBLE */ #ifndef HAVE_LONG_DOUBLE ! #define long_double double #endif /* !defined HAVE_LONG_DOUBLE */ double difftime(time1, time0) ! const time_t time1; ! const time_t time0; { ! time_t delta; ! time_t hibit; - { - time_t tt; - double d; - long_double ld; - - if (sizeof tt < sizeof d) - return (double) time1 - (double) time0; - if (sizeof tt < sizeof ld) - return (long_double) time1 - (long_double) time0; - } - if (time1 < time0) - return -difftime(time0, time1); - /* - ** As much as possible, avoid loss of precision - ** by computing the difference before converting to double. - */ - delta = time1 - time0; - if (delta >= 0) - return delta; /* ! ** Repair delta overflow. */ ! hibit = (~ (time_t) 0) << (TYPE_BIT(time_t) - 1); /* ! ** The following expression rounds twice, which means ! ** the result may not be the closest to the true answer. ! ** For example, suppose time_t is 64-bit signed int, ! ** long_double is IEEE 754 double with default rounding, ! ** time1 = 9223372036854775807 and time0 = -1536. ! ** Then the true difference is 9223372036854777343, ! ** which rounds to 9223372036854777856 ! ** with a total error of 513. ! ** But delta overflows to -9223372036854774273, ! ** which rounds to -9223372036854774784, and correcting ! ** this by subtracting 2 * (long_double) hibit ! ** (i.e. by adding 2**64 = 18446744073709551616) ! ** yields 9223372036854776832, which ! ** rounds to 9223372036854775808 ! ** with a total error of 1535 instead. ! ** This problem occurs only with very large differences. ! ** It's too painful to fix this portably. ! ** We are not alone in this problem; ! ** some C compilers round twice when converting ! ** large unsigned types to small floating types, ! ** so if time_t is unsigned the "return delta" above ! ** has the same double-rounding problem with those compilers. */ ! return delta - 2 * (long_double) hibit; } --- 14,175 ---- #include "private.h" /* ! ** Algorithm courtesy Paul Eggert (eggert@cs.ucla.edu). ! ** ! ** Most other code assumes that time_t is an integer type without ! ** padding bits, and that integer arithmetic is modular two's ! ** complement without overflow traps, but (just for fun) this works ! ** even if time_t is an integer type with padding bits, or a real ! ** floating type, and it works even if signed integer overflow ! ** has undefined behavior. */ ! #include <float.h> ! ! #define TYPE_FLOATING(type) ((type) 0.4 != 0) ! ! #if !defined HAVE_LONG_DOUBLE && defined __STDC__ ! #define HAVE_LONG_DOUBLE 1 ! #endif /* !defined HAVE_LONG_DOUBLE && defined __STDC__ */ #ifndef HAVE_LONG_DOUBLE ! #define HAVE_LONG_DOUBLE 0 #endif /* !defined HAVE_LONG_DOUBLE */ + #if HAVE_LONG_DOUBLE + #define long_double long double + #endif /* HAVE_LONG_DOUBLE */ + #if !HAVE_LONG_DOUBLE + #define long_double double + #endif /* !HAVE_LONG_DOUBLE */ + + #ifndef HAVE_STDINT_H + #define HAVE_STDINT_H (199901L <= __STDC_VERSION__) + #endif /* !defined HAVE_STDINT_H */ + + #if HAVE_STDINT_H + #include <stdint.h> + #define uintmax uintmax_t + #endif /* HAVE_STDINT_H */ + #if !defined uintmax && defined ULLONG_MAX + #define uintmax unsigned long long int + #endif /* !defined uintmax && defined ULLONG_MAX */ + #ifndef uintmax + #define uintmax unsigned long int + #endif /* defined uintmax */ + + #ifndef UINTMAX_MAX + #define UINTMAX_MAX ((uintmax) -1) + #endif /* !defined UINTMAX_MAX */ + + #if !defined INTMAX_MAX && defined LLONG_MAX + #define INTMAX_MAX LLONG_MAX + #endif /* !defined INTMAX_MAX && defined LLONG_MAX */ + #ifndef INTMAX_MAX + #define INTMAX_MAX LONG_MAX + #endif /* !defined INTMAX_MAX */ + double difftime(time1, time0) ! time_t time1; ! time_t time0; { ! int time1_is_smaller; ! double delta; /* ! ** Use floating point if there should be no double-rounding error. ! ** However, avoid long double if it must be wider than needed, ! ** as it's sometimes much more expensive in these cases ! ** (e.g., 64-bit sparc). */ ! if (TYPE_BIT(time_t) <= DBL_MANT_DIG ! || (TYPE_FLOATING(time_t) ! && sizeof(time_t) < sizeof(long_double))) { ! double t1 = time1; ! double t0 = time0; ! return t1 - t0; ! } ! if ((TYPE_BIT(time_t) <= LDBL_MANT_DIG ! && (TYPE_BIT(time_t) == LDBL_MANT_DIG ! || (TYPE_SIGNED(time_t) && UINTMAX_MAX / 2 < INTMAX_MAX))) ! || TYPE_FLOATING(time_t)) { ! long_double t1 = time1; ! long_double t0 = time0; ! return t1 - t0; ! } ! ! time1_is_smaller = time1 < time0; ! if (time1_is_smaller) { ! time_t t = time1; ! time0 = time1; ! time1 = t; ! } ! /* ! ** Now time0 <= time1, and time_t is an integer type. ! ** Optimize the common special cases where time_t is unsigned, ! ** or can be converted to uintmax without losing information. */ ! if (! TYPE_SIGNED(time_t)) ! delta = time1 - time0; ! else { ! uintmax t1 = time1; ! uintmax t0 = time0; ! uintmax dt = t1 - t0; ! delta = dt; ! if (UINTMAX_MAX / 2 < INTMAX_MAX) { ! /* ! ** uintmax has padding bits, and time_t is signed. ! ** Check for overflow: compare dt/2 to (time1/2 - ! ** time0/2). Overflow occurred if they differ by ! ** more than a small slop. ! ** ! ** Thanks to Clive D.W. Feather for detailed technical ! ** advice about hosts with padding bits. ! */ ! uintmax hdt = dt / 2; ! time_t ht1 = time1 / 2; ! time_t ht0 = time0 / 2; ! time_t dht = ht1 - ht0; ! /* ! ** "h" here means half. By range analysis, we have: ! ** -0.5 <= ht1 - time1/2 <= 0.5 ! ** -0.5 <= ht0 - time0/2 <= 0.5 ! ** -1.0 <= dht - (time1 - time0)/2 <= 1.0 ! ** If overflow has not occurred, we also have: ! ** -0.5 <= hdt - (time1 - time0)/2 <= 0 ! ** -1.0 <= dht - hdt <= 1.5 ! ** and since dht - hdt is an integer, we also have: ! ** -1 <= dht - hdt <= 1 ! ** or equivalently: ! ** 0 <= dht - hdt + 1 <= 2 ! ** In the above analysis, all the operators have ! ** their exact mathematical semantics, not C semantics. ! ** However, dht - hdt + 1 is unsigned in C, ! ** so it need not be compared to zero. ! */ ! if (2 < dht - hdt + 1) { ! /* ! ** Repair delta overflow. ! ** ! ** The following expression contains a second ! ** rounding, so the result may not be the ! ** closest to the true answer. This problem ! ** occurs only with very large differences, ! ** It's too painful to fix this portably. ! ** We are not alone in this problem; some C ! ** compilers round twice when converting ! ** large unsigned types to small floating ! ** types, so if time_t is unsigned the ! ** "delta = dt" above has the same ! ** double-rounding problem with those ! ** compilers. ! */ ! long_double hibit = ~(UINTMAX_MAX / 2); ! delta = dt + 2 * hibit; ! } ! } ! } ! ! return time1_is_smaller ? -delta : delta; }
participants (1)
-
Paul Eggert