[PATCH v3 1/1] offtime: optimized calculation of year from unix timestamp

[Gary Gende]

---
 time/offtime.c | 48 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 34 insertions(+), 14 deletions(-)

diff --git a/time/offtime.c b/time/offtime.c
index c94573e931..1de2fc7530 100644
--- a/time/offtime.c
+++ b/time/offtime.c
@@ -18,9 +18,24 @@
 #include <errno.h>
 #include <time.h>
 
+#ifndef MIN
+# define MIN(a,b) (((a) < (b)) ? (a) : (b))
+#endif
+
 #define	SECS_PER_HOUR	(60 * 60)
 #define	SECS_PER_DAY	(SECS_PER_HOUR * 24)
 
+/* The number of days in 400 years, 100 years, 4 years, and 1 year,
+   when starting at the beginning of a 400 year leap year cycle.  */
+#define DIVISOR_400     (303 * 365 + 97 * 366)
+#define DIVISOR_100     (76 * 365 + 24 * 366)
+#define DIVISOR_4       (3 * 365 + 366)
+#define DIVISOR_1       365
+
+/* The number of of days that must be added to start at year -2147483999
+   instead of year 1970.  */
+#define DAYS_OFFSET     DIVISOR_400 * 5368714LL + (280 * 365 + 89 * 366)
+
 /* Compute the `struct tm' representation of T,
    offset OFFSET seconds east of UTC,
    and store year, yday, mon, mday, wday, hour, min, sec into *TP.
@@ -52,22 +67,27 @@ __offtime (__time64_t t, long int offset, struct tm *tp)
   tp->tm_wday = (4 + days) % 7;
   if (tp->tm_wday < 0)
     tp->tm_wday += 7;
-  y = 1970;
 
-#define DIV(a, b) ((a) / (b) - ((a) % (b) < 0))
-#define LEAPS_THRU_END_OF(y) (DIV (y, 4) - DIV (y, 100) + DIV (y, 400))
+  /* Year calculation must start at the beginning of a 400-yr leap year cycle.
+     -2147483999 is the first such year that exists before the minimum value
+     of tm->tm_year.  */
+  y = -2147483999;
+  days += DAYS_OFFSET;
+
+  y += (days / DIVISOR_400) * 400;
+  days %= DIVISOR_400;
+
+  /* adjust for 4x 100-yr cycles being 1 day shorter than a 400-yr cycle  */
+  y += MIN (3, (days / DIVISOR_100)) * 100;
+  days -= MIN (3, (days / DIVISOR_100)) * DIVISOR_100;
+
+  y += (days / DIVISOR_4) * 4;
+  days %= DIVISOR_4;
+
+  /* adjust for 4x 1-yr cycles being 1 day shorter than a 4-yr cycle  */
+  y += MIN (3, (days / DIVISOR_1));
+  days -= MIN (3, (days / DIVISOR_1)) * DIVISOR_1;
 
-  while (days < 0 || days >= (__isleap (y) ? 366 : 365))
-    {
-      /* Guess a corrected year, assuming 365 days per year.  */
-      __time64_t yg = y + days / 365 - (days % 365 < 0);
-
-      /* Adjust DAYS and Y to match the guessed year.  */
-      days -= ((yg - y) * 365
-	       + LEAPS_THRU_END_OF (yg - 1)
-	       - LEAPS_THRU_END_OF (y - 1));
-      y = yg;
-    }
   tp->tm_year = y - 1900;
   if (tp->tm_year != y - 1900)
     {
-- 
2.43.0