bug introduced in tzcode2005c

[Todd C. Miller]

A change in tzcode 2005c causes the following program on OpenBSD
to loop forever.  I've tracked it down to the change included at
the end of this message.

Previously::

$ ./mktime 
Timestamp is: -1
Date is: Thu Jan  1 00:59:59 1970                                               

With tzcode 2005c and beyond it loops forever.

#include <sys/types.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/*
 * This small programm will consume 100% CPU and loops forever with
 * tzcode 2005c - 2005k.
 */
int
main(int argc, char **argv)
{
        time_t timet;
        struct tm tm;

        tm.tm_sec = 36;
        tm.tm_min = 5;
        tm.tm_hour = 23;
        tm.tm_mday = 31;
        tm.tm_mon = 11;
        tm.tm_year = 138;       /* 2038 - 1900 */
        tm.tm_isdst = 0;

        timet = mktime(&tm);
        printf("Timestamp is: %d\n", timet);
        printf("Date is: %s\n", ctime(&timet));
        exit(0);
}

Here's the change that triggers it.

--- tzcode2005b/localtime.c	Mon Jan 10 07:19:41 2005
+++ tzcode2005c/localtime.c	Mon Jan 17 16:36:15 2005
@@ -1441,10 +1436,11 @@
 {
 	register const struct state *	sp;
 	register int			dir;
-	register int			bits;
 	register int			i, j;
 	register int			saved_seconds;
 	register long			li;
+	register time_t			lo;
+	register time_t			hi;
 	long				y;
 	time_t				newt;
 	time_t				t;
@@ -1518,28 +1514,49 @@
 		yourtm.tm_sec = 0;
 	}
 	/*
-	** Divide the search space in half
-	** (this works whether time_t is signed or unsigned).
+	** Do a binary search (this works whatever time_t's type is).
 	*/
-	bits = TYPE_BIT(time_t) - 1;
-	/*
-	** If time_t is signed, then 0 is just above the median,
-	** assuming two's complement arithmetic.
-	** If time_t is unsigned, then (1 << bits) is just above the median.
-	*/
-	t = TYPE_SIGNED(time_t) ? 0 : (((unsigned long) 1) << bits);
+	if (!TYPE_SIGNED(time_t)) {
+		lo = 0;
+		hi = lo - 1;
+	} else if (!TYPE_INTEGRAL(time_t)) {
+		if (sizeof(time_t) > sizeof(float))
+			hi = (time_t) DBL_MAX;
+		else	hi = (time_t) FLT_MAX;
+		lo = -hi;
+	} else {
+		lo = 1;
+		for (i = 0; i < (int) TYPE_BIT(time_t) - 1; ++i)
+			lo *= 2;
+		hi = -(lo + 1);
+	}
 	for ( ; ; ) {
-		if ((*funcp)(&t, offset, &mytm) == NULL)
-			return WRONG;	/* XXX probably wrong */
-		dir = tmcomp(&mytm, &yourtm);
+		t = lo / 2 + hi / 2;
+		if (t < lo)
+			t = lo;
+		else if (t > hi)
+			t = hi;
+		if ((*funcp)(&t, offset, &mytm) == NULL) {
+			/*
+			** Assume that t is too extreme to be represented in
+			** a struct tm; arrange things so that it is less
+			** extreme on the next pass.
+			*/
+			dir = (t > 0) ? 1 : -1;
+		} else	dir = tmcomp(&mytm, &yourtm);
 		if (dir != 0) {
-			if (bits-- < 0)
+			if (t == lo) {
+				++t;
+				++lo;
+			} else if (t == hi) {
+				--t;
+				--hi;
+			}
+			if (lo > hi)
 				return WRONG;
-			if (bits < 0)
-				--t; /* may be needed if new t is minimal */
-			else if (dir > 0)
-				t -= ((long) 1) << bits;
-			else	t += ((long) 1) << bits;
+			if (dir > 0)
+				hi = t;
+			else	lo = t;
 			continue;
 		}
 		if (yourtm.tm_isdst < 0 || mytm.tm_isdst == yourtm.tm_isdst)