gmtime_r: Use faster algorithm by Howard Hinnant

        * libc/time/gmtime_r.c (gmtime_r): use faster algorithm from
	civil_from_days() by Howard Hinnant

Signed-off-by: Corinna Vinschen <corinna@vinschen.de>

2 files changed, 40 insertions, 71 deletions

diff --git a/newlib/ChangeLog b/newlib/ChangeLog
index 28d571edb..7cfec6f6f 100644
--- a/newlib/ChangeLog
+++ b/newlib/ChangeLog
@@ -1,3 +1,8 @@
+2015-06-15  Freddie Chopin  <freddie_chopin@op.pl>
+
+	* libc/time/gmtime_r.c (gmtime_r): use faster algorithm from
+	civil_from_days() by Howard Hinnant
+
 2015-06-01  Hale Wang  <hale.wang@arm.com>
 
 	* libc/machine/arm/aeabi_memmove-arm.S (__aeabi_memmove): Update the
diff --git a/newlib/libc/time/gmtime_r.c b/newlib/libc/time/gmtime_r.c
index f50c199b9..81c7c94b1 100644
--- a/newlib/libc/time/gmtime_r.c
+++ b/newlib/libc/time/gmtime_r.c
@@ -9,6 +9,8 @@
  * - Fixed bug in calculations for dates after year 2069 or before year 1901. Ideas for
  *   solution taken from musl's __secs_to_tm() - 07/12/2014, Freddie Chopin
  *   <freddie_chopin@op.pl>
+ * - Use faster algorithm from civil_from_days() by Howard Hinnant - 12/06/2014,
+ * Freddie Chopin <freddie_chopin@op.pl>
  *
  * Converts the calendar time pointed to by tim_p into a broken-down time
  * expressed as local time. Returns a pointer to a structure containing the
@@ -17,20 +19,21 @@
 
 #include "local.h"
 
-/* move epoch from 01.01.1970 to 01.03.2000 - this is the first day of new
- * 400-year long cycle, right after additional day of leap year. This adjustment
- * is required only for date calculation, so instead of modifying time_t value
- * (which would require 64-bit operations to work correctly) it's enough to
- * adjust the calculated number of days since epoch. */
-#define EPOCH_ADJUSTMENT_DAYS	11017
+/* Move epoch from 01.01.1970 to 01.03.0000 (yes, Year 0) - this is the first
+ * day of a 400-year long "era", right after additional day of leap year.
+ * This adjustment is required only for date calculation, so instead of
+ * modifying time_t value (which would require 64-bit operations to work
+ * correctly) it's enough to adjust the calculated number of days since epoch.
+ */
+#define EPOCH_ADJUSTMENT_DAYS	719468L
 /* year to which the adjustment was made */
-#define ADJUSTED_EPOCH_YEAR	2000
-/* 1st March of 2000 is Wednesday */
+#define ADJUSTED_EPOCH_YEAR	0
+/* 1st March of year 0 is Wednesday */
 #define ADJUSTED_EPOCH_WDAY	3
 /* there are 97 leap years in 400-year periods. ((400 - 97) * 365 + 97 * 366) */
-#define DAYS_PER_400_YEARS	146097L
+#define DAYS_PER_ERA		146097L
 /* there are 24 leap years in 100-year periods. ((100 - 24) * 365 + 24 * 366) */
-#define DAYS_PER_100_YEARS	36524L
+#define DAYS_PER_CENTURY	36524L
 /* there is one leap year every 4 years */
 #define DAYS_PER_4_YEARS	(3 * 365 + 366)
 /* number of days in a non-leap year */
@@ -39,6 +42,8 @@
 #define DAYS_IN_JANUARY		31
 /* number of days in non-leap February */
 #define DAYS_IN_FEBRUARY	28
+/* number of years per era */
+#define YEARS_PER_ERA		400
 
 struct tm *
 _DEFUN (gmtime_r, (tim_p, res),
@@ -47,12 +52,11 @@ _DEFUN (gmtime_r, (tim_p, res),
 {
   long days, rem;
   _CONST time_t lcltime = *tim_p;
-  int year, month, yearday, weekday;
-  int years400, years100, years4, remainingyears;
-  int yearleap;
-  _CONST int *ip;
+  int era, weekday, year;
+  unsigned erayear, yearday, month, day;
+  unsigned long eraday;
 
-  days = ((long)lcltime) / SECSPERDAY - EPOCH_ADJUSTMENT_DAYS;
+  days = ((long)lcltime) / SECSPERDAY + EPOCH_ADJUSTMENT_DAYS;
   rem = ((long)lcltime) % SECSPERDAY;
   if (rem < 0)
     {
@@ -71,65 +75,25 @@ _DEFUN (gmtime_r, (tim_p, res),
     weekday += DAYSPERWEEK;
   res->tm_wday = weekday;
 
-  /* compute year & day of year */
-  years400 = days / DAYS_PER_400_YEARS;
-  days -= years400 * DAYS_PER_400_YEARS;
-  /* simplify by making the values positive */
-  if (days < 0)
-    {
-      days += DAYS_PER_400_YEARS;
-      --years400;
-    }
-
-  years100 = days / DAYS_PER_100_YEARS;
-  if (years100 == 4) /* required for proper day of year calculation */
-    --years100;
-  days -= years100 * DAYS_PER_100_YEARS;
-  years4 = days / DAYS_PER_4_YEARS;
-  days -= years4 * DAYS_PER_4_YEARS;
-  remainingyears = days / DAYS_PER_YEAR;
-  if (remainingyears == 4) /* required for proper day of year calculation */
-    --remainingyears;
-  days -= remainingyears * DAYS_PER_YEAR;
-
-  year = ADJUSTED_EPOCH_YEAR + years400 * 400 + years100 * 100 + years4 * 4 +
-      remainingyears;
-
-  /* If remainingyears is zero, it means that the years were completely
-   * "consumed" by modulo calculations by 400, 100 and 4, so the year is:
-   * 1. a multiple of 4, but not a multiple of 100 or 400 - it's a leap year,
-   * 2. a multiple of 4 and 100, but not a multiple of 400 - it's not a leap
-   * year,
-   * 3. a multiple of 4, 100 and 400 - it's a leap year.
-   * If years4 is non-zero, it means that the year is not a multiple of 100 or
-   * 400 (case 1), so it's a leap year. If years100 is zero (and years4 is zero
-   * - due to short-circuiting), it means that the year is a multiple of 400
-   * (case 3), so it's also a leap year. */
-  yearleap = remainingyears == 0 && (years4 != 0 || years100 == 0);
+  /* compute year, month, day & day of year */
+  /* for description of this algorithm see
+   * http://howardhinnant.github.io/date_algorithms.html#civil_from_days */
+  era = (days >= 0 ? days : days - (DAYS_PER_ERA - 1)) / DAYS_PER_ERA;
+  eraday = days - era * DAYS_PER_ERA;	/* [0, 146096] */
+  erayear = (eraday - eraday / (DAYS_PER_4_YEARS - 1) + eraday / DAYS_PER_CENTURY -
+      eraday / (DAYS_PER_ERA - 1)) / 365;	/* [0, 399] */
+  yearday = eraday - (DAYS_PER_YEAR * erayear + erayear / 4 - erayear / 100);	/* [0, 365] */
+  month = (5 * yearday + 2) / 153;	/* [0, 11] */
+  day = yearday - (153 * month + 2) / 5 + 1;	/* [1, 31] */
+  month += month < 10 ? 2 : -10;
+  year = ADJUSTED_EPOCH_YEAR + erayear + era * YEARS_PER_ERA + (month <= 1);
 
-  /* adjust back to 1st January */
-  yearday = days + DAYS_IN_JANUARY + DAYS_IN_FEBRUARY + yearleap;
-  if (yearday >= DAYS_PER_YEAR + yearleap)
-    {
-      yearday -= DAYS_PER_YEAR + yearleap;
-      ++year;
-    }
-  res->tm_yday = yearday;
+  res->tm_yday = yearday >= DAYS_PER_YEAR - DAYS_IN_JANUARY - DAYS_IN_FEBRUARY ?
+      yearday - (DAYS_PER_YEAR - DAYS_IN_JANUARY - DAYS_IN_FEBRUARY) :
+      yearday + DAYS_IN_JANUARY + DAYS_IN_FEBRUARY + isleap(erayear);
   res->tm_year = year - YEAR_BASE;
-
-  /* Because "days" is the number of days since 1st March, the additional leap
-   * day (29th of February) is the last possible day, so it doesn't matter much
-   * whether the year is actually leap or not. */
-  ip = __month_lengths[1];
-  month = 2;
-  while (days >= ip[month])
-    {
-      days -= ip[month];
-      if (++month >= MONSPERYEAR)
-        month = 0;
-    }
   res->tm_mon = month;
-  res->tm_mday = days + 1;
+  res->tm_mday = day;
 
   res->tm_isdst = 0;