Epoch Seconds to Date Conversion on a Limited Embedded Device

Question

I am trying to figure out the best way to convert from epoch seconds (since NTP epoch 1900-01-01 00:00) to a datetime string (MM/DD/YY,hh:mm:ss) without any libraries/modules/external functions, as they are not available on an embedded device.

My first thought was to look at the Python datetime module source code, however that was not very useful to me.

My initial attempt in Python uses a conversion of days since 0001-01-01 to date using getDateFromJulianDay adapted to Python from C++ source, combined with modulo operations to obtain time. It works, but is there a better way?

def getDateFromJulianDay(julianDay):
    # Gregorian calendar starting from October 15, 1582
    # This algorithm is from:
    # Henry F. Fliegel and Thomas C. van Flandern. 1968.
    # Letters to the editor:
    #     a machine algorithm for processing calendar dates.
    # Commun. ACM 11, 10 (October 1968), 657-. DOI=10.1145/364096.364097
    # http://doi.acm.org/10.1145/364096.364097
    ell = julianDay + 68569;
    n = (4 * ell) / 146097;
    ell = ell - (146097 * n + 3) / 4;
    i = (4000 * (ell + 1)) / 1461001;
    ell = ell - (1461 * i) / 4 + 31;
    j = (80 * ell) / 2447;
    d = ell - (2447 * j) / 80;
    ell = j / 11;
    m = j + 2 - (12 * ell);
    y = 100 * (n - 49) + i + ell;
    return y,m,d

# NTP response (integer portion) for Monday, March 25, 2013 at 6:40:43 PM
sec_since_1900 = 3573225643

# 2415021 is the number of days between 0001-01-01 and 1900-01-01,
#     the start of the NTP epoch
(year,month,day) =  getDateFromJulianDay(2415021 + sec_since_1900/60/60/24)

seconds_into_day = sec_since_1900 % 86400
(hour, sec_past_hour) = divmod(seconds_into_day,3600)
(min, sec) = divmod(sec_past_hour,60)
print 'year:',year,'month:',month,'day:',day
print 'hour:',hour,'min:',min,'sec:',sec

Why I'm doing this: I am getting the current time from an NTP server, and taking this time at face value for updating a hardware real time clock (RTC) that only accepts the date, time and time zone: MM/DD/YY,hh:mm:ss,±zz. I plan to implement true NTP capabilities at a later date. A discussion of time synchronization methods is best left elsewhere, such as this question.

Notes:

• My embedded device is a Telit GC-864 cellular modem that runs Python 1.5.2+ and only has limited operators (mostly just C operators), no modules, and some of the expected built-in Python types. The exact capabilities are here, if you're interested. I write Python for this device as if I'm writing C code - not very Pythonic, I know.
• I realize NTP is best used only for a time offset, however with limited options, I'm using NTP as an absolute time source (I could add the check for the NTP rollover in 2036 to enable another 136 years of operation).
• The GC-864-V2 device with up-to-date firmware does have NTP capability, but the GC-864 I need to use is stuck on a previous release of firmware.

Answer 1

The getDateFromJulianDay function originally proposed is too computationally intensive for effective use on an embedded device, containing many multiplication and division operations on large long variables or, as originally written in C++, longlong variables.

I think I hunted down an efficient epoch to date algorithm for an embedded device.

After fruitless Googling, I found myself back on Stack Overflow, and found the question Converting epoch time to “real” date/time, asking about self-written epoch time to date implementation and provides a suitable algorithm. This answer to the question references the gmtime.c source code, and provided the source in C I needed to write a Python conversion algorithm:

/*
 * gmtime - convert the calendar time into broken down time
 */
/* $Header: /opt/proj/minix/cvsroot/src/lib/ansi/gmtime.c,v 1.1.1.1 2005/04/21 14:56:05 beng Exp $ */

#include        <time.h>
#include        <limits.h>
#include        "loc_time.h"

struct tm *
gmtime(register const time_t *timer)
{
        static struct tm br_time;
        register struct tm *timep = &br_time;
        time_t time = *timer;
        register unsigned long dayclock, dayno;
        int year = EPOCH_YR;

        dayclock = (unsigned long)time % SECS_DAY;
        dayno = (unsigned long)time / SECS_DAY;

        timep->tm_sec = dayclock % 60;
        timep->tm_min = (dayclock % 3600) / 60;
        timep->tm_hour = dayclock / 3600;
        timep->tm_wday = (dayno + 4) % 7;       /* day 0 was a thursday */
        while (dayno >= YEARSIZE(year)) {
                dayno -= YEARSIZE(year);
                year++;
        }
        timep->tm_year = year - YEAR0;
        timep->tm_yday = dayno;
        timep->tm_mon = 0;
        while (dayno >= _ytab[LEAPYEAR(year)][timep->tm_mon]) {
                dayno -= _ytab[LEAPYEAR(year)][timep->tm_mon];
                timep->tm_mon++;
        }
        timep->tm_mday = dayno + 1;
        timep->tm_isdst = 0;

        return timep;
}

Additionally, the analysis of the question Why is gmtime implemented this way? helped affirm that the gmtime function is fairly efficient.

Using the raspberryginger.com minix Doxygen documentation site, I was able to find the C macros and constants that were included in gmtime.c from loc_time.h. The relevant code snippet:

#define YEAR0           1900                    /* the first year */
#define EPOCH_YR        1970            /* EPOCH = Jan 1 1970 00:00:00 */
#define SECS_DAY        (24L * 60L * 60L)
#define LEAPYEAR(year)  (!((year) % 4) && (((year) % 100) || !((year) % 400)))
#define YEARSIZE(year)  (LEAPYEAR(year) ? 366 : 365)
#define FIRSTSUNDAY(timp)       (((timp)->tm_yday - (timp)->tm_wday + 420) % 7)
#define FIRSTDAYOF(timp)        (((timp)->tm_wday - (timp)->tm_yday + 420) % 7)
#define TIME_MAX        ULONG_MAX
#define ABB_LEN         3

extern const int _ytab[2][10];

And the extern const int _ytab was defined in misc.c:

const int _ytab[2][12] = {
                { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
                { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
        };

Some other things I found:

• The gmtime.c File Reference was very helpful for finding dependencies.
• The gmtime function starts indexing the Month, Day of Week, and Day of Year at the number zero, (maximal ranges of 0-11, 0-6, 0-365, respectively), whereas the Day of Month starts at the number 1, (1-31), see the IBM gmtime() reference.

---

I re-wrote the gmtime function for Python 1.5.2+:

def is_leap_year(year):
    return ( not ((year) % 4) and ( ((year) % 100) or (not((year) % 400)) ) )

def year_size(year):
    if is_leap_year(year):
        return 366
    else:
        return 365

def ntp_time_to_date(ntp_time):
    year = 1900         # EPOCH_YR for NTP
    ytab =  [ [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31],
              [ 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] ]

    (dayno,dayclock) = divmod(ntp_time, 86400L)
    dayno = int(dayno)

    # Calculate time of day from seconds on the day's clock.
    (hour, sec_past_hour) = divmod(dayclock,3600)
    hour = int(hour)
    (min, sec) = divmod(int(sec_past_hour),60)

    while (dayno >= year_size(year)):
        dayno = dayno - year_size(year)
        year = year + 1
    month = 1                           # NOTE: month range is (1-12)
    while (dayno >= ytab[is_leap_year(year)][month]):
        dayno = dayno - ytab[is_leap_year(year)][month]
        month = month + 1
    day = dayno + 1

    return (year, month, day, hour, min, sec)

Modifications I made re-factoring the C++ gmtime function to my Python function ntp_time_to_date(ntp_time):

• Changed epoch from UNIX epoch of 1970 to NTP epoch of 1900 (the prime epoch for NTP).
• Slightly streamlined time of day calculation.
  • Comparing time of day calculation of gmtime to ntp_time_to_date:
    • Both (dayclock % 3600) / 60 and dayclock / 3600 occur behind the scenes in divmod(dayclock,3600) and divmod(sec_past_hour,60).
    • Only real difference is that divmod(sec_past_hour,60) avoids modulo of dayclock (0-86399) by 60 via dayclock % 60, and instead does modulo of sec_past_hour (0-3599) by 60 within divmod(sec_past_hour,60).
• Removed variables and code I did not need, for example, day of week.
• Changed indexing of Month to start at 1, so Month range is (1-12) instead of (0-11)
• Type cast variables away from long as soon as values were less than 65535 to greatly decrease code execution time.
  • The requires long variables are:
    • ntp_time, seconds since 1900 (0-4294967295)
    • dayclock, seconds into day (0-86399)
  • The largest of the rest of the variables is the calculated year within the date.

---

The Python ntp_time_to_date function (with its dependencies) runs successfully on the Telit GC-864 on an embedded version of Python 1.5.2+, as well as on Python 2.7.3, but of course use the datetime library if you can.

Answer 2

TL;DR

If you are using a Telit GC-864, the Python interpreter seemingly inserts some sort of delay in-between each line of code execution.

For a Telit GC-864, the function in my question getDateFromJulianDay(julianDay) is faster than the function in my answer, ntp_time_to_date(ntp_time).

More Detail

The number of code lines dominates execution time on a GC-864 more than the complexity of the code - weird, I know. The function getDateFromJulianDay(julianDay) in my question has a handful of complex operations, maybe 15 lines of code. The function in my answer ntp_time_to_date(ntp_time) has simpler computation complexity, but the while loops cause 100+ lines of code execution:

• One loop counts from 1900 to the current year
• Another loop counts from month 1 to the current month

Test Results

Timing test results running on an actual GC-864 (note: not a GC-864-V2) using the same NTP time input for each trial (each function outputs "3/25/2013 18:40"). Timing was performed using printf statement debugging, and a serial terminal on a computer would time stamp each line sent by the GC-864.

getDateFromJulianDay(julianDay) Trials:

• 0.3802 seconds
• 0.3370 seconds
• 0.3370 seconds
• Average: 0.3514 seconds

ntp_time_to_date(ntp_time) Trials:

• 0.8899 seconds
• 0.9072 seconds
• 0.8986 seconds
• Average: 0.8986 seconds

The variability partially stems from the GC-864 cell modem servicing cellular network tasks periodically.

For completeness, the optimization of typecasting the long variables to int as quickly as possible in ntp_time_to_date(ntp_time) has a fairly significant effect. Without this optimization:

• 2.3155 seconds
• 1.5034 seconds
• 1.5293 seconds
• 2.0995 seconds
• 2.0909 seconds
• Average: 1.9255 seconds

Doing anything computationally involved on a Telit GC-864 running .pyo files in Python 1.5.2+ is not a great idea. Using the GC-864-V2, which has a built-in NTP capability is a possible solution for someone who comes across this issue. Moreover, newer machine-to-machine (M2M) aka internet of things (IoT) cell phone modems are much more capable.

If you have a similar issue with the GC-864, consider using a newer and more modern cell phone modem.