Improve code for gmtime_r()

Unlike the current code, it does no looping to count days or do
table lookups, which means running time doesn't increase with year
or month. A good thing if it's call a lot, especially if the
algorithm were asked to compute dates centuries or more from the
epoch start.

As a bonus, handles negative time values.

Change-Id: I198a23daf621e40623e6b44dacf2387078b4db9c

1 files changed, 86 insertions, 68 deletions

diff --git a/firmware/libc/gmtime.c b/firmware/libc/gmtime.c
index c5deb593cd..b01050904d 100644
--- a/firmware/libc/gmtime.c
+++ b/firmware/libc/gmtime.c
@@ -7,6 +7,8 @@
  *                     \/            \/     \/    \/            \/
  * $Id$
  *
+ * Copyright (C) 2017 by Michael Sevakis
+ *
  * Copyright (C) 2012 by Bertrik Sikken
  *
  * Based on code from: rtc_as3514.c
@@ -21,96 +23,112 @@
  * KIND, either express or implied.
  *
  ****************************************************************************/
-#include <stdbool.h>
-#include <stdint.h>
 #include "time.h"
 
-#define MINUTE_SECONDS      60
-#define HOUR_SECONDS        3600
-#define DAY_SECONDS         86400
-#define WEEK_SECONDS        604800
-#define YEAR_SECONDS        31536000
-#define LEAP_YEAR_SECONDS   31622400
+/* Constants that mark Thursday, 1 January 1970 */
+#define UNIX_EPOCH_DAY_NUM  134774
+#define UNIX_EPOCH_YEAR     (1601 - 1900)
 
-/* Days in each month */
-static uint8_t days_in_month[] =
-    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
+/* Last day number it can do */
+#define MAX_DAY_NUM         551879
 
-static inline bool is_leapyear(int year)
+/* d is days since epoch start, Monday, 1 January 1601 (d = 0)
+ *
+ * That date is the beginning of a full 400 year cycle and so simplifies the
+ * calculations a bit, not requiring offsets before divisions to shift the
+ * leap year cycle.
+ *
+ * It can handle dates up through Sunday, 31 December 3111 (d = 551879).
+ *
+ * time_t can't get near the limits anyway for now but algorithm can be
+ * altered slightly to increase range if even needed.
+ */
+static void get_tmdate(unsigned int d, struct tm *tm)
 {
-    return (((year%4)==0) && (((year%100)!=0) || ((year%400)==0)));
-}
+    static const unsigned short mon_yday[13] =
+    {
+        /* year day of 1st of month (non-leap)
+      +31  +28  +31  +30  +31  +30  +31  +31  +30  +31  +30  +31  +31 */
+        0,  31,  59,  90, 120, 151, 181, 212, 243, 273, 304, 334, 365
+    };
 
-struct tm *gmtime(const time_t *timep)
-{
-    static struct tm time;
-    return gmtime_r(timep, &time);
-}
+    unsigned int x0, x1, x2, x3; /* scratch variables */
 
-struct tm *gmtime_r(const time_t *timep, struct tm *tm)
-{
-    time_t seconds = *timep;
-    int year, i, mday, hour, min;
+    /* calculate year from day number */
+    x0 = d / 1460;
+    x1 = x0 / 25;
+    x2 = x1 / 4;
 
-    /* weekday */
-    tm->tm_wday = (seconds / DAY_SECONDS + 4) % 7;
+    unsigned int y = (d - x0 + x1 - x2) / 365;
 
-    /* Year */
-    year = 1970;
-    while (seconds >= LEAP_YEAR_SECONDS)
-    {
-        if (is_leapyear(year)){
-            seconds -= LEAP_YEAR_SECONDS;
-        } else {
-            seconds -= YEAR_SECONDS;
-        }
+    tm->tm_year = y + UNIX_EPOCH_YEAR;          /* year - 1900 */
 
-        year++;
-    }
+    /* calculate year day from year number and day number */
+    x0 = y / 4;
+    x1 = x0 / 25;
+    x2 = x1 / 4;
+
+    unsigned int yday = d - x0 + x1 - x2 - y * 365;
 
-    if (is_leapyear(year)) {
-        days_in_month[1] = 29;
-    } else {
-        days_in_month[1] = 28;
-        if(seconds>YEAR_SECONDS){
-            year++;
-            seconds -= YEAR_SECONDS;
+    tm->tm_yday = x3 = yday;                    /* 0..364/365 */
+
+    /* check if leap year; adjust February->March transition if so rather
+       than keeping a leap year version of mon_yday[] */
+    if (y - x0 * 4 == 3 && (x0 - x1 * 25 != 24 || x1 - x2 * 4 == 3)) {
+        /* retard month lookup to make year day 59 into 29 Feb, both to make
+           year day 60 into 01 March, lagging one day for remainder of year */
+        if (x3 >= mon_yday[2] && --x3 >= mon_yday[2]) {
+            yday--;
         }
     }
-    tm->tm_year = year - 1900;
 
-    /* Month */
-    for (i = 0; i < 12; i++)
-    {
-        if (seconds < days_in_month[i]*DAY_SECONDS){
-            tm->tm_mon = i;
-            break;
-        }
+    /* stab approximately at current month based on year day; advance if
+       it fell short (never initially more than 1 short). */
+    x0 = x3 / 32;
+    if (mon_yday[x0 + 1] <= x3) {
+        x0++;
+    }
+
+    tm->tm_mon  = x0;                           /* 0..11 */
+    tm->tm_mday = yday - mon_yday[x0] + 1;      /* 1..31 */
+    tm->tm_wday = (d + 1) % 7;                  /* 0..6 */
+}
+
+struct tm * gmtime_r(const time_t *timep, struct tm *tm)
+{
+    time_t t = *timep;
+
+    int d = t / 86400;             /* day number (-24856..24855) */
+    int s = t - (time_t)d * 86400; /* second # of day (0..86399) */
 
-        seconds -= days_in_month[i]*DAY_SECONDS;
+    if (s < 0) {
+        /* round towards 0 -> floored division */
+        d--;
+        s += 86400;
     }
 
-    /* Month Day */
-    mday = seconds/DAY_SECONDS;
-    seconds -= mday*DAY_SECONDS;
-    tm->tm_mday = mday + 1; /* 1 ... 31 */
+    unsigned int x;
 
-    /* Hour */
-    hour = seconds/HOUR_SECONDS;
-    seconds -= hour*HOUR_SECONDS;
-    tm->tm_hour = hour;
+    x = s / 3600;
+    tm->tm_hour = x;    /* 0..23 */
 
-    /* Minute */
-    min = seconds/MINUTE_SECONDS;
-    seconds -= min*MINUTE_SECONDS;
-    tm->tm_min = min;
+    s -= x * 3600;
+    x = s / 60;
+    tm->tm_min = x;     /* 0..59 */
 
-    /* Second */
-    tm->tm_sec = seconds;
+    s -= x * 60;
+    tm->tm_sec = s;     /* 0..59 */
 
-    tm->tm_yday = 0; /* Not implemented for now */
-    tm->tm_isdst = -1; /* Not implemented for now */
+    /* not implemented right now */
+    tm->tm_isdst = -1;
+
+    get_tmdate(d + UNIX_EPOCH_DAY_NUM, tm);
 
     return tm;
 }
 
+struct tm * gmtime(const time_t *timep)
+{
+    static struct tm time;
+    return gmtime_r(timep, &time);
+}