aboutsummaryrefslogtreecommitdiff
path: root/libntp/ntp_calendar.c
diff options
context:
space:
mode:
Diffstat (limited to 'libntp/ntp_calendar.c')
-rw-r--r--libntp/ntp_calendar.c1615
1 files changed, 1615 insertions, 0 deletions
diff --git a/libntp/ntp_calendar.c b/libntp/ntp_calendar.c
new file mode 100644
index 000000000000..e557f4ec682e
--- /dev/null
+++ b/libntp/ntp_calendar.c
@@ -0,0 +1,1615 @@
+/*
+ * ntp_calendar.c - calendar and helper functions
+ *
+ * Written by Juergen Perlinger (perlinger@ntp.org) for the NTP project.
+ * The contents of 'html/copyright.html' apply.
+ */
+#include <config.h>
+#include <sys/types.h>
+
+#include "ntp_types.h"
+#include "ntp_calendar.h"
+#include "ntp_stdlib.h"
+#include "ntp_fp.h"
+#include "ntp_unixtime.h"
+
+/*
+ *---------------------------------------------------------------------
+ * replacing the 'time()' function
+ * --------------------------------------------------------------------
+ */
+
+static systime_func_ptr systime_func = &time;
+static inline time_t now(void);
+
+
+systime_func_ptr
+ntpcal_set_timefunc(
+ systime_func_ptr nfunc
+ )
+{
+ systime_func_ptr res;
+
+ res = systime_func;
+ if (NULL == nfunc)
+ nfunc = &time;
+ systime_func = nfunc;
+
+ return res;
+}
+
+
+static inline time_t
+now(void)
+{
+ return (*systime_func)(NULL);
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert between 'time_t' and 'vint64'
+ *---------------------------------------------------------------------
+ */
+vint64
+time_to_vint64(
+ const time_t * ptt
+ )
+{
+ vint64 res;
+ time_t tt;
+
+ tt = *ptt;
+
+#if SIZEOF_TIME_T <= 4
+
+ res.D_s.hi = 0;
+ if (tt < 0) {
+ res.D_s.lo = (uint32_t)-tt;
+ M_NEG(res.D_s.hi, res.D_s.lo);
+ } else {
+ res.D_s.lo = (uint32_t)tt;
+ }
+
+#elif defined(HAVE_INT64)
+
+ res.q_s = tt;
+
+#else
+ /*
+ * shifting negative signed quantities is compiler-dependent, so
+ * we better avoid it and do it all manually. And shifting more
+ * than the width of a quantity is undefined. Also a don't do!
+ */
+ if (tt < 0) {
+ tt = -tt;
+ res.D_s.lo = (uint32_t)tt;
+ res.D_s.hi = (uint32_t)(tt >> 32);
+ M_NEG(res.D_s.hi, res.D_s.lo);
+ } else {
+ res.D_s.lo = (uint32_t)tt;
+ res.D_s.hi = (uint32_t)(tt >> 32);
+ }
+
+#endif
+
+ return res;
+}
+
+
+time_t
+vint64_to_time(
+ const vint64 *tv
+ )
+{
+ time_t res;
+
+#if SIZEOF_TIME_T <= 4
+
+ res = (time_t)tv->D_s.lo;
+
+#elif defined(HAVE_INT64)
+
+ res = (time_t)tv->q_s;
+
+#else
+
+ res = ((time_t)tv->d_s.hi << 32) | tv->D_s.lo;
+
+#endif
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Get the build date & time
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_get_build_date(
+ struct calendar * jd
+ )
+{
+ /* The C standard tells us the format of '__DATE__':
+ *
+ * __DATE__ The date of translation of the preprocessing
+ * translation unit: a character string literal of the form "Mmm
+ * dd yyyy", where the names of the months are the same as those
+ * generated by the asctime function, and the first character of
+ * dd is a space character if the value is less than 10. If the
+ * date of translation is not available, an
+ * implementation-defined valid date shall be supplied.
+ *
+ * __TIME__ The time of translation of the preprocessing
+ * translation unit: a character string literal of the form
+ * "hh:mm:ss" as in the time generated by the asctime
+ * function. If the time of translation is not available, an
+ * implementation-defined valid time shall be supplied.
+ *
+ * Note that MSVC declares DATE and TIME to be in the local time
+ * zone, while neither the C standard nor the GCC docs make any
+ * statement about this. As a result, we may be +/-12hrs off
+ * UTC. But for practical purposes, this should not be a
+ * problem.
+ *
+ */
+ static const char build[] = __TIME__ "/" __DATE__;
+ static const char mlist[] = "JanFebMarAprMayJunJulAugSepOctNovDec";
+
+ char monstr[4];
+ const char * cp;
+ unsigned short hour, minute, second, day, year;
+ /* Note: The above quantities are used for sscanf 'hu' format,
+ * so using 'uint16_t' is contra-indicated!
+ */
+
+#ifdef DEBUG
+ static int ignore = 0;
+#endif
+
+ ZERO(*jd);
+ jd->year = 1970;
+ jd->month = 1;
+ jd->monthday = 1;
+
+#ifdef DEBUG
+ /* check environment if build date should be ignored */
+ if (0 == ignore) {
+ const char * envstr;
+ envstr = getenv("NTPD_IGNORE_BUILD_DATE");
+ ignore = 1 + (envstr && (!*envstr || !strcasecmp(envstr, "yes")));
+ }
+ if (ignore > 1)
+ return FALSE;
+#endif
+
+ if (6 == sscanf(build, "%hu:%hu:%hu/%3s %hu %hu",
+ &hour, &minute, &second, monstr, &day, &year)) {
+ cp = strstr(mlist, monstr);
+ if (NULL != cp) {
+ jd->year = year;
+ jd->month = (uint8_t)((cp - mlist) / 3 + 1);
+ jd->monthday = (uint8_t)day;
+ jd->hour = (uint8_t)hour;
+ jd->minute = (uint8_t)minute;
+ jd->second = (uint8_t)second;
+
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+
+/*
+ *---------------------------------------------------------------------
+ * basic calendar stuff
+ * --------------------------------------------------------------------
+ */
+
+/* month table for a year starting with March,1st */
+static const uint16_t shift_month_table[13] = {
+ 0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337, 366
+};
+
+/* month tables for years starting with January,1st; regular & leap */
+static const uint16_t real_month_table[2][13] = {
+ /* -*- table for regular years -*- */
+ { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 },
+ /* -*- table for leap years -*- */
+ { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 }
+};
+
+/*
+ * Some notes on the terminology:
+ *
+ * We use the proleptic Gregorian calendar, which is the Gregorian
+ * calendar extended in both directions ad infinitum. This totally
+ * disregards the fact that this calendar was invented in 1582, and
+ * was adopted at various dates over the world; sometimes even after
+ * the start of the NTP epoch.
+ *
+ * Normally date parts are given as current cycles, while time parts
+ * are given as elapsed cycles:
+ *
+ * 1970-01-01/03:04:05 means 'IN the 1970st. year, IN the first month,
+ * ON the first day, with 3hrs, 4minutes and 5 seconds elapsed.
+ *
+ * The basic calculations for this calendar implementation deal with
+ * ELAPSED date units, which is the number of full years, full months
+ * and full days before a date: 1970-01-01 would be (1969, 0, 0) in
+ * that notation.
+ *
+ * To ease the numeric computations, month and day values outside the
+ * normal range are acceptable: 2001-03-00 will be treated as the day
+ * before 2001-03-01, 2000-13-32 will give the same result as
+ * 2001-02-01 and so on.
+ *
+ * 'rd' or 'RD' is used as an abbreviation for the latin 'rata die'
+ * (day number). This is the number of days elapsed since 0000-12-31
+ * in the proleptic Gregorian calendar. The begin of the Christian Era
+ * (0001-01-01) is RD(1).
+ *
+ *
+ * Some notes on the implementation:
+ *
+ * Calendar algorithms thrive on the division operation, which is one of
+ * the slowest numerical operations in any CPU. What saves us here from
+ * abysmal performance is the fact that all divisions are divisions by
+ * constant numbers, and most compilers can do this by a multiplication
+ * operation. But this might not work when using the div/ldiv/lldiv
+ * function family, because many compilers are not able to do inline
+ * expansion of the code with following optimisation for the
+ * constant-divider case.
+ *
+ * Also div/ldiv/lldiv are defined in terms of int/long/longlong, which
+ * are inherently target dependent. Nothing that could not be cured with
+ * autoconf, but still a mess...
+ *
+ * Furthermore, we need floor division while C demands truncation to
+ * zero, so additional steps are required to make sure the algorithms
+ * work.
+ *
+ * For all this, all divisions by constant are coded manually, even when
+ * there is a joined div/mod operation: The optimiser should sort that
+ * out, if possible.
+ *
+ * Finally, the functions do not check for overflow conditions. This
+ * is a sacrifice made for execution speed; since a 32-bit day counter
+ * covers +/- 5,879,610 years, this should not pose a problem here.
+ */
+
+
+/*
+ * ==================================================================
+ *
+ * General algorithmic stuff
+ *
+ * ==================================================================
+ */
+
+/*
+ *---------------------------------------------------------------------
+ * Do a periodic extension of 'value' around 'pivot' with a period of
+ * 'cycle'.
+ *
+ * The result 'res' is a number that holds to the following properties:
+ *
+ * 1) res MOD cycle == value MOD cycle
+ * 2) pivot <= res < pivot + cycle
+ * (replace </<= with >/>= for negative cycles)
+ *
+ * where 'MOD' denotes the modulo operator for FLOOR DIVISION, which
+ * is not the same as the '%' operator in C: C requires division to be
+ * a truncated division, where remainder and dividend have the same
+ * sign if the remainder is not zero, whereas floor division requires
+ * divider and modulus to have the same sign for a non-zero modulus.
+ *
+ * This function has some useful applications:
+ *
+ * + let Y be a calendar year and V a truncated 2-digit year: then
+ * periodic_extend(Y-50, V, 100)
+ * is the closest expansion of the truncated year with respect to
+ * the full year, that is a 4-digit year with a difference of less
+ * than 50 years to the year Y. ("century unfolding")
+ *
+ * + let T be a UN*X time stamp and V be seconds-of-day: then
+ * perodic_extend(T-43200, V, 86400)
+ * is a time stamp that has the same seconds-of-day as the input
+ * value, with an absolute difference to T of <= 12hrs. ("day
+ * unfolding")
+ *
+ * + Wherever you have a truncated periodic value and a non-truncated
+ * base value and you want to match them somehow...
+ *
+ * Basically, the function delivers 'pivot + (value - pivot) % cycle',
+ * but the implementation takes some pains to avoid internal signed
+ * integer overflows in the '(value - pivot) % cycle' part and adheres
+ * to the floor division convention.
+ *
+ * If 64bit scalars where available on all intended platforms, writing a
+ * version that uses 64 bit ops would be easy; writing a general
+ * division routine for 64bit ops on a platform that can only do
+ * 32/16bit divisions and is still performant is a bit more
+ * difficult. Since most usecases can be coded in a way that does only
+ * require the 32-bit version a 64bit version is NOT provided here.
+ * ---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_periodic_extend(
+ int32_t pivot,
+ int32_t value,
+ int32_t cycle
+ )
+{
+ uint32_t diff;
+ char cpl = 0; /* modulo complement flag */
+ char neg = 0; /* sign change flag */
+
+ /* make the cycle positive and adjust the flags */
+ if (cycle < 0) {
+ cycle = - cycle;
+ neg ^= 1;
+ cpl ^= 1;
+ }
+ /* guard against div by zero or one */
+ if (cycle > 1) {
+ /*
+ * Get absolute difference as unsigned quantity and
+ * the complement flag. This is done by always
+ * subtracting the smaller value from the bigger
+ * one. This implementation works only on a two's
+ * complement machine!
+ */
+ if (value >= pivot) {
+ diff = (uint32_t)value - (uint32_t)pivot;
+ } else {
+ diff = (uint32_t)pivot - (uint32_t)value;
+ cpl ^= 1;
+ }
+ diff %= (uint32_t)cycle;
+ if (diff) {
+ if (cpl)
+ diff = cycle - diff;
+ if (neg)
+ diff = ~diff + 1;
+ pivot += diff;
+ }
+ }
+ return pivot;
+}
+
+/*
+ *-------------------------------------------------------------------
+ * Convert a timestamp in NTP scale to a 64bit seconds value in the UN*X
+ * scale with proper epoch unfolding around a given pivot or the current
+ * system time. This function happily accepts negative pivot values as
+ * timestamps befor 1970-01-01, so be aware of possible trouble on
+ * platforms with 32bit 'time_t'!
+ *
+ * This is also a periodic extension, but since the cycle is 2^32 and
+ * the shift is 2^31, we can do some *very* fast math without explicit
+ * divisions.
+ *-------------------------------------------------------------------
+ */
+vint64
+ntpcal_ntp_to_time(
+ uint32_t ntp,
+ const time_t * pivot
+ )
+{
+ vint64 res;
+
+#ifdef HAVE_INT64
+
+ res.q_s = (pivot != NULL)
+ ? *pivot
+ : now();
+ res.Q_s -= 0x80000000; /* unshift of half range */
+ ntp -= (uint32_t)JAN_1970; /* warp into UN*X domain */
+ ntp -= res.D_s.lo; /* cycle difference */
+ res.Q_s += (uint64_t)ntp; /* get expanded time */
+
+#else /* no 64bit scalars */
+
+ time_t tmp;
+
+ tmp = (pivot != NULL)
+ ? *pivot
+ : now();
+ res = time_to_vint64(&tmp);
+ M_SUB(res.D_s.hi, res.D_s.lo, 0, 0x80000000);
+ ntp -= (uint32_t)JAN_1970; /* warp into UN*X domain */
+ ntp -= res.D_s.lo; /* cycle difference */
+ M_ADD(res.D_s.hi, res.D_s.lo, 0, ntp);
+
+#endif /* no 64bit scalars */
+
+ return res;
+}
+
+/*
+ *-------------------------------------------------------------------
+ * Convert a timestamp in NTP scale to a 64bit seconds value in the NTP
+ * scale with proper epoch unfolding around a given pivot or the current
+ * system time.
+ *
+ * Note: The pivot must be given in the UN*X time domain!
+ *
+ * This is also a periodic extension, but since the cycle is 2^32 and
+ * the shift is 2^31, we can do some *very* fast math without explicit
+ * divisions.
+ *-------------------------------------------------------------------
+ */
+vint64
+ntpcal_ntp_to_ntp(
+ uint32_t ntp,
+ const time_t *pivot
+ )
+{
+ vint64 res;
+
+#ifdef HAVE_INT64
+
+ res.q_s = (pivot)
+ ? *pivot
+ : now();
+ res.Q_s -= 0x80000000; /* unshift of half range */
+ res.Q_s += (uint32_t)JAN_1970; /* warp into NTP domain */
+ ntp -= res.D_s.lo; /* cycle difference */
+ res.Q_s += (uint64_t)ntp; /* get expanded time */
+
+#else /* no 64bit scalars */
+
+ time_t tmp;
+
+ tmp = (pivot)
+ ? *pivot
+ : now();
+ res = time_to_vint64(&tmp);
+ M_SUB(res.D_s.hi, res.D_s.lo, 0, 0x80000000u);
+ M_ADD(res.D_s.hi, res.D_s.lo, 0, (uint32_t)JAN_1970);/*into NTP */
+ ntp -= res.D_s.lo; /* cycle difference */
+ M_ADD(res.D_s.hi, res.D_s.lo, 0, ntp);
+
+#endif /* no 64bit scalars */
+
+ return res;
+}
+
+
+/*
+ * ==================================================================
+ *
+ * Splitting values to composite entities
+ *
+ * ==================================================================
+ */
+
+/*
+ *-------------------------------------------------------------------
+ * Split a 64bit seconds value into elapsed days in 'res.hi' and
+ * elapsed seconds since midnight in 'res.lo' using explicit floor
+ * division. This function happily accepts negative time values as
+ * timestamps before the respective epoch start.
+ * -------------------------------------------------------------------
+ */
+ntpcal_split
+ntpcal_daysplit(
+ const vint64 *ts
+ )
+{
+ ntpcal_split res;
+
+#ifdef HAVE_INT64
+
+ /* manual floor division by SECSPERDAY */
+ res.hi = (int32_t)(ts->q_s / SECSPERDAY);
+ res.lo = (int32_t)(ts->q_s % SECSPERDAY);
+ if (res.lo < 0) {
+ res.hi -= 1;
+ res.lo += SECSPERDAY;
+ }
+
+#else
+
+ /*
+ * since we do not have 64bit ops, we have to this by hand.
+ * Luckily SECSPERDAY is 86400 is 675*128, so we do the division
+ * using chained 32/16 bit divisions and shifts.
+ */
+ vint64 op;
+ uint32_t q, r, a;
+ int isneg;
+
+ memcpy(&op, ts, sizeof(op));
+ /* fix sign */
+ isneg = M_ISNEG(op.D_s.hi);
+ if (isneg)
+ M_NEG(op.D_s.hi, op.D_s.lo);
+
+ /* save remainder of DIV 128, shift for divide */
+ r = op.D_s.lo & 127; /* save remainder bits */
+ op.D_s.lo = (op.D_s.lo >> 7) | (op.D_s.hi << 25);
+ op.D_s.hi = (op.D_s.hi >> 7);
+
+ /* now do a mnual division, trying to remove as many ops as
+ * possible -- division is always slow! An since we do not have
+ * the advantage of a specific 64/32 bit or even a specific 32/16
+ * bit division op, but must use the general 32/32bit division
+ * even if we *know* the divider fits into unsigned 16 bits, the
+ * exra code pathes should pay off.
+ */
+ a = op.D_s.hi;
+ if (a > 675u)
+ a = a % 675u;
+ if (a) {
+ a = (a << 16) | op.W_s.lh;
+ q = a / 675u;
+ a = a % 675u;
+
+ a = (a << 16) | op.W_s.ll;
+ q = (q << 16) | (a / 675u);
+ } else {
+ a = op.D_s.lo;
+ q = a / 675u;
+ }
+ a = a % 675u;
+
+ /* assemble remainder */
+ r |= a << 7;
+
+ /* fix sign of result */
+ if (isneg) {
+ if (r) {
+ r = SECSPERDAY - r;
+ q = ~q;
+ } else
+ q = ~q + 1;
+ }
+
+ res.hi = q;
+ res.lo = r;
+
+#endif
+ return res;
+}
+
+/*
+ *-------------------------------------------------------------------
+ * Split a 32bit seconds value into h/m/s and excessive days. This
+ * function happily accepts negative time values as timestamps before
+ * midnight.
+ * -------------------------------------------------------------------
+ */
+static int32_t
+priv_timesplit(
+ int32_t split[3],
+ int32_t ts
+ )
+{
+ int32_t days = 0;
+
+ /* make sure we have a positive offset into a day */
+ if (ts < 0 || ts >= SECSPERDAY) {
+ days = ts / SECSPERDAY;
+ ts = ts % SECSPERDAY;
+ if (ts < 0) {
+ days -= 1;
+ ts += SECSPERDAY;
+ }
+ }
+
+ /* get secs, mins, hours */
+ split[2] = (uint8_t)(ts % SECSPERMIN);
+ ts /= SECSPERMIN;
+ split[1] = (uint8_t)(ts % MINSPERHR);
+ split[0] = (uint8_t)(ts / MINSPERHR);
+
+ return days;
+}
+
+/*
+ * ---------------------------------------------------------------------
+ * Given the number of elapsed days in the calendar era, split this
+ * number into the number of elapsed years in 'res.hi' and the number
+ * of elapsed days of that year in 'res.lo'.
+ *
+ * if 'isleapyear' is not NULL, it will receive an integer that is 0 for
+ * regular years and a non-zero value for leap years.
+ *---------------------------------------------------------------------
+ */
+ntpcal_split
+ntpcal_split_eradays(
+ int32_t days,
+ int *isleapyear
+ )
+{
+ ntpcal_split res;
+ int32_t n400, n100, n004, n001, yday; /* calendar year cycles */
+
+ /*
+ * Split off calendar cycles, using floor division in the first
+ * step. After that first step, simple division does it because
+ * all operands are positive; alas, we have to be aware of the
+ * possibe cycle overflows for 100 years and 1 year, caused by
+ * the additional leap day.
+ */
+ n400 = days / GREGORIAN_CYCLE_DAYS;
+ yday = days % GREGORIAN_CYCLE_DAYS;
+ if (yday < 0) {
+ n400 -= 1;
+ yday += GREGORIAN_CYCLE_DAYS;
+ }
+ n100 = yday / GREGORIAN_NORMAL_CENTURY_DAYS;
+ yday = yday % GREGORIAN_NORMAL_CENTURY_DAYS;
+ n004 = yday / GREGORIAN_NORMAL_LEAP_CYCLE_DAYS;
+ yday = yday % GREGORIAN_NORMAL_LEAP_CYCLE_DAYS;
+ n001 = yday / DAYSPERYEAR;
+ yday = yday % DAYSPERYEAR;
+
+ /*
+ * check for leap cycle overflows and calculate the leap flag
+ * if needed
+ */
+ if ((n001 | n100) > 3) {
+ /* hit last day of leap year */
+ n001 -= 1;
+ yday += DAYSPERYEAR;
+ if (isleapyear)
+ *isleapyear = 1;
+ } else if (isleapyear)
+ *isleapyear = (n001 == 3) && ((n004 != 24) || (n100 == 3));
+
+ /* now merge the cycles to elapsed years, using horner scheme */
+ res.hi = ((4*n400 + n100)*25 + n004)*4 + n001;
+ res.lo = yday;
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Given a number of elapsed days in a year and a leap year indicator,
+ * split the number of elapsed days into the number of elapsed months in
+ * 'res.hi' and the number of elapsed days of that month in 'res.lo'.
+ *
+ * This function will fail and return {-1,-1} if the number of elapsed
+ * days is not in the valid range!
+ *---------------------------------------------------------------------
+ */
+ntpcal_split
+ntpcal_split_yeardays(
+ int32_t eyd,
+ int isleapyear
+ )
+{
+ ntpcal_split res;
+ const uint16_t *lt; /* month length table */
+
+ /* check leap year flag and select proper table */
+ lt = real_month_table[(isleapyear != 0)];
+ if (0 <= eyd && eyd < lt[12]) {
+ /* get zero-based month by approximation & correction step */
+ res.hi = eyd >> 5; /* approx month; might be 1 too low */
+ if (lt[res.hi + 1] <= eyd) /* fixup approximative month value */
+ res.hi += 1;
+ res.lo = eyd - lt[res.hi];
+ } else {
+ res.lo = res.hi = -1;
+ }
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert a RD into the date part of a 'struct calendar'.
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_rd_to_date(
+ struct calendar *jd,
+ int32_t rd
+ )
+{
+ ntpcal_split split;
+ int leaps;
+ int retv;
+
+ leaps = 0;
+ retv = 0;
+ /* get day-of-week first */
+ jd->weekday = rd % 7;
+ if (jd->weekday >= 7) /* unsigned! */
+ jd->weekday += 7;
+
+ split = ntpcal_split_eradays(rd - 1, &leaps);
+ retv = leaps;
+ /* get year and day-of-year */
+ jd->year = (uint16_t)split.hi + 1;
+ if (jd->year != split.hi + 1) {
+ jd->year = 0;
+ retv = -1; /* bletch. overflow trouble. */
+ }
+ jd->yearday = (uint16_t)split.lo + 1;
+
+ /* convert to month and mday */
+ split = ntpcal_split_yeardays(split.lo, leaps);
+ jd->month = (uint8_t)split.hi + 1;
+ jd->monthday = (uint8_t)split.lo + 1;
+
+ return retv ? retv : leaps;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert a RD into the date part of a 'struct tm'.
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_rd_to_tm(
+ struct tm *utm,
+ int32_t rd
+ )
+{
+ ntpcal_split split;
+ int leaps;
+
+ leaps = 0;
+ /* get day-of-week first */
+ utm->tm_wday = rd % 7;
+ if (utm->tm_wday < 0)
+ utm->tm_wday += 7;
+
+ /* get year and day-of-year */
+ split = ntpcal_split_eradays(rd - 1, &leaps);
+ utm->tm_year = split.hi - 1899;
+ utm->tm_yday = split.lo; /* 0-based */
+
+ /* convert to month and mday */
+ split = ntpcal_split_yeardays(split.lo, leaps);
+ utm->tm_mon = split.hi; /* 0-based */
+ utm->tm_mday = split.lo + 1; /* 1-based */
+
+ return leaps;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Take a value of seconds since midnight and split it into hhmmss in a
+ * 'struct calendar'.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_daysec_to_date(
+ struct calendar *jd,
+ int32_t sec
+ )
+{
+ int32_t days;
+ int ts[3];
+
+ days = priv_timesplit(ts, sec);
+ jd->hour = (uint8_t)ts[0];
+ jd->minute = (uint8_t)ts[1];
+ jd->second = (uint8_t)ts[2];
+
+ return days;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Take a value of seconds since midnight and split it into hhmmss in a
+ * 'struct tm'.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_daysec_to_tm(
+ struct tm *utm,
+ int32_t sec
+ )
+{
+ int32_t days;
+ int32_t ts[3];
+
+ days = priv_timesplit(ts, sec);
+ utm->tm_hour = ts[0];
+ utm->tm_min = ts[1];
+ utm->tm_sec = ts[2];
+
+ return days;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * take a split representation for day/second-of-day and day offset
+ * and convert it to a 'struct calendar'. The seconds will be normalised
+ * into the range of a day, and the day will be adjusted accordingly.
+ *
+ * returns >0 if the result is in a leap year, 0 if in a regular
+ * year and <0 if the result did not fit into the calendar struct.
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_daysplit_to_date(
+ struct calendar *jd,
+ const ntpcal_split *ds,
+ int32_t dof
+ )
+{
+ dof += ntpcal_daysec_to_date(jd, ds->lo);
+ return ntpcal_rd_to_date(jd, ds->hi + dof);
+}
+
+/*
+ *---------------------------------------------------------------------
+ * take a split representation for day/second-of-day and day offset
+ * and convert it to a 'struct tm'. The seconds will be normalised
+ * into the range of a day, and the day will be adjusted accordingly.
+ *
+ * returns 1 if the result is in a leap year and zero if in a regular
+ * year.
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_daysplit_to_tm(
+ struct tm *utm,
+ const ntpcal_split *ds ,
+ int32_t dof
+ )
+{
+ dof += ntpcal_daysec_to_tm(utm, ds->lo);
+
+ return ntpcal_rd_to_tm(utm, ds->hi + dof);
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Take a UN*X time and convert to a calendar structure.
+ *---------------------------------------------------------------------
+ */
+int
+ntpcal_time_to_date(
+ struct calendar *jd,
+ const vint64 *ts
+ )
+{
+ ntpcal_split ds;
+
+ ds = ntpcal_daysplit(ts);
+ ds.hi += ntpcal_daysec_to_date(jd, ds.lo);
+ ds.hi += DAY_UNIX_STARTS;
+
+ return ntpcal_rd_to_date(jd, ds.hi);
+}
+
+
+/*
+ * ==================================================================
+ *
+ * merging composite entities
+ *
+ * ==================================================================
+ */
+
+/*
+ *---------------------------------------------------------------------
+ * Merge a number of days and a number of seconds into seconds,
+ * expressed in 64 bits to avoid overflow.
+ *---------------------------------------------------------------------
+ */
+vint64
+ntpcal_dayjoin(
+ int32_t days,
+ int32_t secs
+ )
+{
+ vint64 res;
+
+#ifdef HAVE_INT64
+
+ res.q_s = days;
+ res.q_s *= SECSPERDAY;
+ res.q_s += secs;
+
+#else
+
+ uint32_t p1, p2;
+ int isneg;
+
+ /*
+ * res = days *86400 + secs, using manual 16/32 bit
+ * multiplications and shifts.
+ */
+ isneg = (days < 0);
+ if (isneg)
+ days = -days;
+
+ /* assemble days * 675 */
+ res.D_s.lo = (days & 0xFFFF) * 675u;
+ res.D_s.hi = 0;
+ p1 = (days >> 16) * 675u;
+ p2 = p1 >> 16;
+ p1 = p1 << 16;
+ M_ADD(res.D_s.hi, res.D_s.lo, p2, p1);
+
+ /* mul by 128, using shift */
+ res.D_s.hi = (res.D_s.hi << 7) | (res.D_s.lo >> 25);
+ res.D_s.lo = (res.D_s.lo << 7);
+
+ /* fix sign */
+ if (isneg)
+ M_NEG(res.D_s.hi, res.D_s.lo);
+
+ /* properly add seconds */
+ p2 = 0;
+ if (secs < 0) {
+ p1 = (uint32_t)-secs;
+ M_NEG(p2, p1);
+ } else {
+ p1 = (uint32_t)secs;
+ }
+ M_ADD(res.D_s.hi, res.D_s.lo, p2, p1);
+
+#endif
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert elapsed years in Era into elapsed days in Era.
+ *
+ * To accomodate for negative values of years, floor division would be
+ * required for all division operations. This can be eased by first
+ * splitting the years into full 400-year cycles and years in the
+ * cycle. Only this operation must be coded as a full floor division; as
+ * the years in the cycle is a non-negative number, all other divisions
+ * can be regular truncated divisions.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_days_in_years(
+ int32_t years
+ )
+{
+ int32_t cycle; /* full gregorian cycle */
+
+ /* split off full calendar cycles, using floor division */
+ cycle = years / 400;
+ years = years % 400;
+ if (years < 0) {
+ cycle -= 1;
+ years += 400;
+ }
+
+ /*
+ * Calculate days in cycle. years now is a non-negative number,
+ * holding the number of years in the 400-year cycle.
+ */
+ return cycle * GREGORIAN_CYCLE_DAYS
+ + years * DAYSPERYEAR /* days inregular years */
+ + years / 4 /* 4 year leap rule */
+ - years / 100; /* 100 year leap rule */
+ /* the 400-year rule does not apply due to full-cycle split-off */
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert a number of elapsed month in a year into elapsed days in year.
+ *
+ * The month will be normalized, and 'res.hi' will contain the
+ * excessive years that must be considered when converting the years,
+ * while 'res.lo' will contain the number of elapsed days since start
+ * of the year.
+ *
+ * This code uses the shifted-month-approach to convert month to days,
+ * because then there is no need to have explicit leap year
+ * information. The slight disadvantage is that for most month values
+ * the result is a negative value, and the year excess is one; the
+ * conversion is then simply based on the start of the following year.
+ *---------------------------------------------------------------------
+ */
+ntpcal_split
+ntpcal_days_in_months(
+ int32_t m
+ )
+{
+ ntpcal_split res;
+
+ /* normalize month into range */
+ res.hi = 0;
+ res.lo = m;
+ if (res.lo < 0 || res.lo >= 12) {
+ res.hi = res.lo / 12;
+ res.lo = res.lo % 12;
+ if (res.lo < 0) {
+ res.hi -= 1;
+ res.lo += 12;
+ }
+ }
+
+ /* add 10 month for year starting with march */
+ if (res.lo < 2)
+ res.lo += 10;
+ else {
+ res.hi += 1;
+ res.lo -= 2;
+ }
+
+ /* get cummulated days in year with unshift */
+ res.lo = shift_month_table[res.lo] - 306;
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert ELAPSED years/months/days of gregorian calendar to elapsed
+ * days in Gregorian epoch.
+ *
+ * If you want to convert years and days-of-year, just give a month of
+ * zero.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_edate_to_eradays(
+ int32_t years,
+ int32_t mons,
+ int32_t mdays
+ )
+{
+ ntpcal_split tmp;
+ int32_t res;
+
+ if (mons) {
+ tmp = ntpcal_days_in_months(mons);
+ res = ntpcal_days_in_years(years + tmp.hi) + tmp.lo;
+ } else
+ res = ntpcal_days_in_years(years);
+ res += mdays;
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert ELAPSED years/months/days of gregorian calendar to elapsed
+ * days in year.
+ *
+ * Note: This will give the true difference to the start of the given year,
+ * even if months & days are off-scale.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_edate_to_yeardays(
+ int32_t years,
+ int32_t mons,
+ int32_t mdays
+ )
+{
+ ntpcal_split tmp;
+
+ if (0 <= mons && mons < 12) {
+ years += 1;
+ mdays += real_month_table[is_leapyear(years)][mons];
+ } else {
+ tmp = ntpcal_days_in_months(mons);
+ mdays += tmp.lo
+ + ntpcal_days_in_years(years + tmp.hi)
+ - ntpcal_days_in_years(years);
+ }
+
+ return mdays;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert elapsed days and the hour/minute/second information into
+ * total seconds.
+ *
+ * If 'isvalid' is not NULL, do a range check on the time specification
+ * and tell if the time input is in the normal range, permitting for a
+ * single leapsecond.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_etime_to_seconds(
+ int32_t hours,
+ int32_t minutes,
+ int32_t seconds
+ )
+{
+ int32_t res;
+
+ res = (hours * MINSPERHR + minutes) * SECSPERMIN + seconds;
+
+ return res;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert the date part of a 'struct tm' (that is, year, month,
+ * day-of-month) into the RD of that day.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_tm_to_rd(
+ const struct tm *utm
+ )
+{
+ return ntpcal_edate_to_eradays(utm->tm_year + 1899,
+ utm->tm_mon,
+ utm->tm_mday - 1) + 1;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * Convert the date part of a 'struct calendar' (that is, year, month,
+ * day-of-month) into the RD of that day.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_date_to_rd(
+ const struct calendar *jd
+ )
+{
+ return ntpcal_edate_to_eradays((int32_t)jd->year - 1,
+ (int32_t)jd->month - 1,
+ (int32_t)jd->monthday - 1) + 1;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * convert a year number to rata die of year start
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_year_to_ystart(
+ int32_t year
+ )
+{
+ return ntpcal_days_in_years(year - 1) + 1;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * For a given RD, get the RD of the associated year start,
+ * that is, the RD of the last January,1st on or before that day.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_rd_to_ystart(
+ int32_t rd
+ )
+{
+ /*
+ * Rather simple exercise: split the day number into elapsed
+ * years and elapsed days, then remove the elapsed days from the
+ * input value. Nice'n sweet...
+ */
+ return rd - ntpcal_split_eradays(rd - 1, NULL).lo;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * For a given RD, get the RD of the associated month start.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_rd_to_mstart(
+ int32_t rd
+ )
+{
+ ntpcal_split split;
+ int leaps;
+
+ split = ntpcal_split_eradays(rd - 1, &leaps);
+ split = ntpcal_split_yeardays(split.lo, leaps);
+
+ return rd - split.lo;
+}
+
+/*
+ *---------------------------------------------------------------------
+ * take a 'struct calendar' and get the seconds-of-day from it.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_date_to_daysec(
+ const struct calendar *jd
+ )
+{
+ return ntpcal_etime_to_seconds(jd->hour, jd->minute,
+ jd->second);
+}
+
+/*
+ *---------------------------------------------------------------------
+ * take a 'struct tm' and get the seconds-of-day from it.
+ *---------------------------------------------------------------------
+ */
+int32_t
+ntpcal_tm_to_daysec(
+ const struct tm *utm
+ )
+{
+ return ntpcal_etime_to_seconds(utm->tm_hour, utm->tm_min,
+ utm->tm_sec);
+}
+
+/*
+ *---------------------------------------------------------------------
+ * take a 'struct calendar' and convert it to a 'time_t'
+ *---------------------------------------------------------------------
+ */
+time_t
+ntpcal_date_to_time(
+ const struct calendar *jd
+ )
+{
+ vint64 join;
+ int32_t days, secs;
+
+ days = ntpcal_date_to_rd(jd) - DAY_UNIX_STARTS;
+ secs = ntpcal_date_to_daysec(jd);
+ join = ntpcal_dayjoin(days, secs);
+
+ return vint64_to_time(&join);
+}
+
+
+/*
+ * ==================================================================
+ *
+ * extended and unchecked variants of caljulian/caltontp
+ *
+ * ==================================================================
+ */
+int
+ntpcal_ntp64_to_date(
+ struct calendar *jd,
+ const vint64 *ntp
+ )
+{
+ ntpcal_split ds;
+
+ ds = ntpcal_daysplit(ntp);
+ ds.hi += ntpcal_daysec_to_date(jd, ds.lo);
+
+ return ntpcal_rd_to_date(jd, ds.hi + DAY_NTP_STARTS);
+}
+
+int
+ntpcal_ntp_to_date(
+ struct calendar *jd,
+ uint32_t ntp,
+ const time_t *piv
+ )
+{
+ vint64 ntp64;
+
+ /*
+ * Unfold ntp time around current time into NTP domain. Split
+ * into days and seconds, shift days into CE domain and
+ * process the parts.
+ */
+ ntp64 = ntpcal_ntp_to_ntp(ntp, piv);
+ return ntpcal_ntp64_to_date(jd, &ntp64);
+}
+
+
+vint64
+ntpcal_date_to_ntp64(
+ const struct calendar *jd
+ )
+{
+ /*
+ * Convert date to NTP. Ignore yearday, use d/m/y only.
+ */
+ return ntpcal_dayjoin(ntpcal_date_to_rd(jd) - DAY_NTP_STARTS,
+ ntpcal_date_to_daysec(jd));
+}
+
+
+uint32_t
+ntpcal_date_to_ntp(
+ const struct calendar *jd
+ )
+{
+ /*
+ * Get lower half of 64-bit NTP timestamp from date/time.
+ */
+ return ntpcal_date_to_ntp64(jd).d_s.lo;
+}
+
+
+
+/*
+ * ==================================================================
+ *
+ * day-of-week calculations
+ *
+ * ==================================================================
+ */
+/*
+ * Given a RataDie and a day-of-week, calculate a RDN that is reater-than,
+ * greater-or equal, closest, less-or-equal or less-than the given RDN
+ * and denotes the given day-of-week
+ */
+int32_t
+ntpcal_weekday_gt(
+ int32_t rdn,
+ int32_t dow
+ )
+{
+ return ntpcal_periodic_extend(rdn+1, dow, 7);
+}
+
+int32_t
+ntpcal_weekday_ge(
+ int32_t rdn,
+ int32_t dow
+ )
+{
+ return ntpcal_periodic_extend(rdn, dow, 7);
+}
+
+int32_t
+ntpcal_weekday_close(
+ int32_t rdn,
+ int32_t dow
+ )
+{
+ return ntpcal_periodic_extend(rdn-3, dow, 7);
+}
+
+int32_t
+ntpcal_weekday_le(
+ int32_t rdn,
+ int32_t dow
+ )
+{
+ return ntpcal_periodic_extend(rdn, dow, -7);
+}
+
+int32_t
+ntpcal_weekday_lt(
+ int32_t rdn,
+ int32_t dow
+ )
+{
+ return ntpcal_periodic_extend(rdn-1, dow, -7);
+}
+
+/*
+ * ==================================================================
+ *
+ * ISO week-calendar conversions
+ *
+ * The ISO8601 calendar defines a calendar of years, weeks and weekdays.
+ * It is related to the Gregorian calendar, and a ISO year starts at the
+ * Monday closest to Jan,1st of the corresponding Gregorian year. A ISO
+ * calendar year has always 52 or 53 weeks, and like the Grogrian
+ * calendar the ISO8601 calendar repeats itself every 400 years, or
+ * 146097 days, or 20871 weeks.
+ *
+ * While it is possible to write ISO calendar functions based on the
+ * Gregorian calendar functions, the following implementation takes a
+ * different approach, based directly on years and weeks.
+ *
+ * Analysis of the tabulated data shows that it is not possible to
+ * interpolate from years to weeks over a full 400 year range; cyclic
+ * shifts over 400 years do not provide a solution here. But it *is*
+ * possible to interpolate over every single century of the 400-year
+ * cycle. (The centennial leap year rule seems to be the culprit here.)
+ *
+ * It can be shown that a conversion from years to weeks can be done
+ * using a linear transformation of the form
+ *
+ * w = floor( y * a + b )
+ *
+ * where the slope a must hold to
+ *
+ * 52.1780821918 <= a < 52.1791044776
+ *
+ * and b must be chosen according to the selected slope and the number
+ * of the century in a 400-year period.
+ *
+ * The inverse calculation can also be done in this way. Careful scaling
+ * provides an unlimited set of integer coefficients a,k,b that enable
+ * us to write the calulation in the form
+ *
+ * w = (y * a + b ) / k
+ * y = (w * a' + b') / k'
+ *
+ * In this implementation the values of k and k' are chosen to be
+ * smallest possible powers of two, so the division can be implemented
+ * as shifts if the optimiser chooses to do so.
+ *
+ * ==================================================================
+ */
+
+/*
+ * Given a number of elapsed (ISO-)years since the begin of the
+ * christian era, return the number of elapsed weeks corresponding to
+ * the number of years.
+ */
+int32_t
+isocal_weeks_in_years(
+ int32_t years
+ )
+{
+ /*
+ * use: w = (y * 53431 + b[c]) / 1024 as interpolation
+ */
+ static const int32_t bctab[4] = { 449, 157, 889, 597 };
+ int32_t cycle; /* full gregorian cycle */
+ int32_t cents; /* full centuries */
+ int32_t weeks; /* accumulated weeks */
+
+ /* split off full calendar cycles, using floor division */
+ cycle = years / 400;
+ years = years % 400;
+ if (years < 0) {
+ cycle -= 1;
+ years += 400;
+ }
+
+ /* split off full centuries */
+ cents = years / 100;
+ years = years % 100;
+
+ /*
+ * calculate elapsed weeks, taking into account that the
+ * first, third and fourth century have 5218 weeks but the
+ * second century falls short by one week.
+ */
+ weeks = (years * 53431 + bctab[cents]) / 1024;
+
+ return cycle * GREGORIAN_CYCLE_WEEKS
+ + cents * 5218 - (cents > 1)
+ + weeks;
+}
+
+/*
+ * Given a number of elapsed weeks since the begin of the christian
+ * era, split this number into the number of elapsed years in res.hi
+ * and the excessive number of weeks in res.lo. (That is, res.lo is
+ * the number of elapsed weeks in the remaining partial year.)
+ */
+ntpcal_split
+isocal_split_eraweeks(
+ int32_t weeks
+ )
+{
+ /*
+ * use: y = (w * 157 + b[c]) / 8192 as interpolation
+ */
+ static const int32_t bctab[4] = { 85, 131, 17, 62 };
+ ntpcal_split res;
+ int32_t cents;
+
+ /*
+ * split off 400-year cycles, using the fact that a 400-year
+ * cycle has 146097 days, which is exactly 20871 weeks.
+ */
+ res.hi = weeks / GREGORIAN_CYCLE_WEEKS;
+ res.lo = weeks % GREGORIAN_CYCLE_WEEKS;
+ if (res.lo < 0) {
+ res.hi -= 1;
+ res.lo += GREGORIAN_CYCLE_WEEKS;
+ }
+ res.hi *= 400;
+
+ /*
+ * split off centuries, taking into account that the first,
+ * third and fourth century have 5218 weeks but that the
+ * second century falls short by one week.
+ */
+ res.lo += (res.lo >= 10435);
+ cents = res.lo / 5218;
+ res.lo %= 5218; /* res.lo is weeks in century now */
+
+ /* convert elapsed weeks in century to elapsed years and weeks */
+ res.lo = res.lo * 157 + bctab[cents];
+ res.hi += cents * 100 + res.lo / 8192;
+ res.lo = (res.lo % 8192) / 157;
+
+ return res;
+}
+
+/*
+ * Given a second in the NTP time scale and a pivot, expand the NTP
+ * time stamp around the pivot and convert into an ISO calendar time
+ * stamp.
+ */
+int
+isocal_ntp64_to_date(
+ struct isodate *id,
+ const vint64 *ntp
+ )
+{
+ ntpcal_split ds;
+ int32_t ts[3];
+
+ /*
+ * Split NTP time into days and seconds, shift days into CE
+ * domain and process the parts.
+ */
+ ds = ntpcal_daysplit(ntp);
+
+ /* split time part */
+ ds.hi += priv_timesplit(ts, ds.lo);
+ id->hour = (uint8_t)ts[0];
+ id->minute = (uint8_t)ts[1];
+ id->second = (uint8_t)ts[2];
+
+ /* split date part */
+ ds.lo = ds.hi + DAY_NTP_STARTS - 1; /* elapsed era days */
+ ds.hi = ds.lo / 7; /* elapsed era weeks */
+ ds.lo = ds.lo % 7; /* elapsed week days */
+ if (ds.lo < 0) { /* floor division! */
+ ds.hi -= 1;
+ ds.lo += 7;
+ }
+ id->weekday = (uint8_t)ds.lo + 1; /* weekday result */
+
+ ds = isocal_split_eraweeks(ds.hi); /* elapsed years&week*/
+ id->year = (uint16_t)ds.hi + 1; /* shift to current */
+ id->week = (uint8_t )ds.lo + 1;
+
+ return (ds.hi >= 0 && ds.hi < 0xFFFFU);
+}
+
+int
+isocal_ntp_to_date(
+ struct isodate *id,
+ uint32_t ntp,
+ const time_t *piv
+ )
+{
+ vint64 ntp64;
+
+ /*
+ * Unfold ntp time around current time into NTP domain, then
+ * convert the full time stamp.
+ */
+ ntp64 = ntpcal_ntp_to_ntp(ntp, piv);
+ return isocal_ntp64_to_date(id, &ntp64);
+}
+
+/*
+ * Convert a ISO date spec into a second in the NTP time scale,
+ * properly truncated to 32 bit.
+ */
+vint64
+isocal_date_to_ntp64(
+ const struct isodate *id
+ )
+{
+ int32_t weeks, days, secs;
+
+ weeks = isocal_weeks_in_years((int32_t)id->year - 1)
+ + (int32_t)id->week - 1;
+ days = weeks * 7 + (int32_t)id->weekday;
+ /* days is RDN of ISO date now */
+ secs = ntpcal_etime_to_seconds(id->hour, id->minute, id->second);
+
+ return ntpcal_dayjoin(days - DAY_NTP_STARTS, secs);
+}
+
+uint32_t
+isocal_date_to_ntp(
+ const struct isodate *id
+ )
+{
+ /*
+ * Get lower half of 64-bit NTP timestamp from date/time.
+ */
+ return isocal_date_to_ntp64(id).d_s.lo;
+}
+
+/* -*-EOF-*- */
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-16 07:32:33 +0000