diff options
Diffstat (limited to 'libntp/ntp_calendar.c')
-rw-r--r-- | libntp/ntp_calendar.c | 1615 |
1 files changed, 1615 insertions, 0 deletions
diff --git a/libntp/ntp_calendar.c b/libntp/ntp_calendar.c new file mode 100644 index 0000000..e557f4e --- /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-*- */ |