Lines Matching +full:use +full:- +full:internal +full:- +full:divider
2 * ntp_calendar.c - calendar and helper functions
7 * --------------------------------------------------------------------
17 * constant-divider case.
44 * an internal overflow, and these are coded in a way that avoids
45 * it. All other functions do not suffer from internal overflow and
61 * macros are not defined, check a few well-known compiler/architecture
63 * integers is unknown and shift-arithmetic-right is not available.
92 *---------------------------------------------------------------------
94 *---------------------------------------------------------------------
124 *---------------------------------------------------------------------
126 *---------------------------------------------------------------------
137 * true, though -- On 8bit CPUs or machines without barrel
148 return UINT32_C(0) - (uint32_t)(v < 0);
174 v = -(int32_t)(~vu) - 1;
184 *---------------------------------------------------------------------
186 *---------------------------------------------------------------------
202 res.D_s.lo = (uint32_t)-tt;
214 * shifting negative signed quantities is compiler-dependent, so
219 tt = -tt;
243 res = (time_t)tv->D_s.lo;
247 res = (time_t)tv->q_s;
251 res = ((time_t)tv->d_s.hi << 32) | tv->D_s.lo;
259 *---------------------------------------------------------------------
261 *---------------------------------------------------------------------
276 * implementation-defined valid date shall be supplied.
282 * implementation-defined valid time shall be supplied.
286 * statement about this. As a result, we may be +/-12hrs off
302 * so using 'uint16_t' is contra-indicated!
310 jd->year = 1970;
311 jd->month = 1;
312 jd->monthday = 1;
329 jd->year = year;
330 jd->month = (uint8_t)((cp - mlist) / 3 + 1);
331 jd->monthday = (uint8_t)day;
332 jd->hour = (uint8_t)hour;
333 jd->minute = (uint8_t)minute;
334 jd->second = (uint8_t)second;
345 *---------------------------------------------------------------------
347 *---------------------------------------------------------------------
353 * We use the proleptic Gregorian calendar, which is the Gregorian
362 * 1970-01-01/03:04:05 means 'IN the 1970st. year, IN the first month,
367 * and full days before a date: 1970-01-01 would be (1969, 0, 0) in
371 * normal range are acceptable: 2001-03-00 will be treated as the day
372 * before 2001-03-01, 2000-13-32 will give the same result as
373 * 2001-02-01 and so on.
376 * (day number). This is the number of days elapsed since 0000-12-31
378 * (0001-01-01) is RD(1).
390 *---------------------------------------------------------------------
392 *---------------------------------------------------------------------
406 * this one is ARM-friendly because of a mask that fits into 16
413 * M <- ceil(ldexp(8/7, 29))
423 /* We add (2**32 - 2**32 % 7), which is (2**32 - 4), to negative
424 * numbers to map them into the postive range. Only the term '-4'
428 return u32mod7((x < 0) ? (ux - 4u) : ux);
438 uint32_t sf = UINT32_C(0) - (x < 0);
444 *---------------------------------------------------------------------
458 * divider and modulus to have the same sign for a non-zero modulus.
462 * + let Y be a calendar year and V a truncated 2-digit year: then
463 * periodic_extend(Y-50, V, 100)
465 * the full year, that is a 4-digit year with a difference of less
468 * + let T be a UN*X time stamp and V be seconds-of-day: then
469 * perodic_extend(T-43200, V, 86400)
470 * is a time stamp that has the same seconds-of-day as the input
474 * + Wherever you have a truncated periodic value and a non-truncated
477 * Basically, the function delivers 'pivot + (value - pivot) % cycle',
478 * but the implementation takes some pains to avoid internal signed
479 * integer overflows in the '(value - pivot) % cycle' part and adheres
488 *---------------------------------------------------------------------
497 /* Implement a 4-quadrant modulus calculation by 2 2-quadrant
505 * that is, we don't actually divide for cycles of -1,0,1 and
515 sf = UINT32_C(0) - (value < pivot);
517 uv = sf ^ (uv - up);
521 else if (cycle < -1)
524 sf = UINT32_C(0) - (value > pivot);
526 uv = sf ^ (up - uv);
528 pivot -= (uc & sf) + (sf ^ uv);
533 /*---------------------------------------------------------------------
539 * res.Q_s -= 0x80000000;
549 * http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
561 *---------------------------------------------------------------------
565 * timestamps before 1970-01-01, so be aware of possible trouble on
571 *---------------------------------------------------------------------
586 res.Q_s -= 0x80000000u; /* unshift of half range */
587 ntp -= (uint32_t)JAN_1970; /* warp into UN*X domain */
588 ntp -= res.D_s.lo; /* cycle difference */
600 ntp -= (uint32_t)JAN_1970; /* warp into UN*X domain */
601 ntp -= res.D_s.lo; /* cycle difference */
610 *---------------------------------------------------------------------
620 *---------------------------------------------------------------------
635 res.Q_s -= 0x80000000u; /* unshift of half range */
637 ntp -= res.D_s.lo; /* cycle difference */
650 ntp -= res.D_s.lo; /* cycle difference */
668 *---------------------------------------------------------------------
673 *---------------------------------------------------------------------
688 uint64_t sf64 = (uint64_t)-(ts->q_s < 0);
689 Q = (uint32_t)(sf64 ^ ((sf64 ^ ts->Q_s) / SECSPERDAY));
690 R = (uint32_t)(ts->Q_s - Q * SECSPERDAY);
696 * for ARM CPUs, the sum-by-digit code in the next section is
698 * the 64bit-by-32bit division will never outperform the exact
701 if (ts->q_s < 0)
702 Q = ~(uint32_t)(~ts->Q_s / SECSPERDAY);
704 Q = (uint32_t)( ts->Q_s / SECSPERDAY);
705 R = ts->D_s.lo - Q * SECSPERDAY;
711 * Here we use a mean trick to get away with just one explicit
714 * Remember: 86400 <--> 128 * 675
721 * Then we use a digit-wise pseudo-reduction, where a 'digit' is
722 * actually a 16-bit group. This is followed by a full reduction
737 * number that is divisible by 675. But since we use the
741 uint32_t al = ts->D_s.lo;
742 uint32_t ah = ts->D_s.hi;
748 R = (ts->d_s.hi < 0) ? 239 : 0;/* sign bit value */
754 Q = (al - R) * 0x2D21C10Bu; /* modinv(675, 2**32) */
755 R = (R << 7) | (ts->d_s.lo & 0x07F);
766 *---------------------------------------------------------------------
771 *---------------------------------------------------------------------
787 uint64_t sf64 = (uint64_t)-(ts->q_s < 0);
788 Q = (uint32_t)(sf64 ^ ((sf64 ^ ts->Q_s) / SECSPERWEEK));
789 R = (uint32_t)(ts->Q_s - Q * SECSPERWEEK);
793 if (ts->q_s < 0)
794 Q = ~(uint32_t)(~ts->Q_s / SECSPERWEEK);
796 Q = (uint32_t)( ts->Q_s / SECSPERWEEK);
797 R = ts->D_s.lo - Q * SECSPERWEEK;
801 /* Remember: 7*86400 <--> 604800 <--> 128 * 4725 */
802 uint32_t al = ts->D_s.lo;
803 uint32_t ah = ts->D_s.hi;
808 R = (ts->d_s.hi < 0) ? 2264 : 0;/* sign bit value */
814 Q = (al - R) * 0x98BBADDDu; /* modinv(4725, 2**32) */
815 R = (R << 7) | (ts->d_s.lo & 0x07F);
826 *---------------------------------------------------------------------
830 *---------------------------------------------------------------------
855 split[0] = (int32_t)(uh - ud * HRSPERDAY );
856 split[1] = (int32_t)(um - uh * MINSPERHR );
857 split[2] = (int32_t)(us - um * SECSPERMIN);
863 *---------------------------------------------------------------------
869 * regular years and a non-zero value for leap years.
870 *---------------------------------------------------------------------
878 /* Use the fast cycle split algorithm here, to calculate the
881 * susceptible to internal range overflow. We take some extra
900 sf64 = (uint64_t)-(days < 0);
902 uday = (uint32_t)(ud64 - Q * GREGORIAN_CYCLE_DAYS);
918 * (-2^33) % 146097 --> 130717 : the sign bit value
919 * ( 2^20) % 146097 --> 25897 : the upper digit value
920 * modinv(146097, 2^32) --> 660721233 : the inverse
927 Q = (ux - uday) * 660721233u; /* exact div */
932 /* Split off years in century -- days >= 0 here, and we're far
936 uday -= n001 * GREGORIAN_NORMAL_LEAP_CYCLE_DAYS;
953 *---------------------------------------------------------------------
958 * This function will fail and return {-1,-1} if the number of elapsed
960 *---------------------------------------------------------------------
968 /* Use the unshifted-year, February-with-30-days approach here.
970 * the smallest power-of-two divider to avoid any true division.
972 ntpcal_split res = {-1, -1};
977 if (eyd >= 61 - isleap)
982 res.lo = eyd - ((489 * res.hi + 8) >> 4);
989 *---------------------------------------------------------------------
991 *---------------------------------------------------------------------
1003 /* Get day-of-week first. It's simply the RD (mod 7)... */
1004 jd->weekday = i32mod7(rd);
1006 split = ntpcal_split_eradays(rd - 1, &leapy);
1007 /* Get year and day-of-year, with overflow check. If any of the
1008 * upper 16 bits is set after shifting to unity-based years, we
1014 ymask = 0u - ((split.hi >> 16) == 0);
1015 jd->year = (uint16_t)(split.hi & ymask);
1016 jd->yearday = (uint16_t)split.lo + 1;
1020 jd->month = (uint8_t)split.hi + 1;
1021 jd->monthday = (uint8_t)split.lo + 1;
1023 return ymask ? leapy : -1;
1027 *---------------------------------------------------------------------
1029 *---------------------------------------------------------------------
1040 /* get day-of-week first */
1041 utm->tm_wday = i32mod7(rd);
1043 /* get year and day-of-year */
1044 split = ntpcal_split_eradays(rd - 1, &leapy);
1045 utm->tm_year = split.hi - 1899;
1046 utm->tm_yday = split.lo; /* 0-based */
1050 utm->tm_mon = split.hi; /* 0-based */
1051 utm->tm_mday = split.lo + 1; /* 1-based */
1057 *---------------------------------------------------------------------
1060 *---------------------------------------------------------------------
1072 jd->hour = (uint8_t)ts[0];
1073 jd->minute = (uint8_t)ts[1];
1074 jd->second = (uint8_t)ts[2];
1080 *---------------------------------------------------------------------
1083 *---------------------------------------------------------------------
1095 utm->tm_hour = ts[0];
1096 utm->tm_min = ts[1];
1097 utm->tm_sec = ts[2];
1103 *---------------------------------------------------------------------
1104 * take a split representation for day/second-of-day and day offset
1110 *---------------------------------------------------------------------
1119 dof += ntpcal_daysec_to_date(jd, ds->lo);
1120 return ntpcal_rd_to_date(jd, ds->hi + dof);
1124 *---------------------------------------------------------------------
1125 * take a split representation for day/second-of-day and day offset
1131 *---------------------------------------------------------------------
1140 dof += ntpcal_daysec_to_tm(utm, ds->lo);
1142 return ntpcal_rd_to_tm(utm, ds->hi + dof);
1146 *---------------------------------------------------------------------
1148 *---------------------------------------------------------------------
1193 sf = (uint32_t)-(hi < 0);
1196 /* assemble major units: res <- |hi| * mul */
1204 /* mul by 128, using shift: res <-- res << 7 */
1208 /* fix up sign: res <-- (res + [sf|sf]) ^ [sf|sf] */
1213 /* properly add seconds: res <-- res + [sx(lo)|lo] */
1214 p2 = (uint32_t)-(lo < 0);
1222 *---------------------------------------------------------------------
1225 *---------------------------------------------------------------------
1251 *---------------------------------------------------------------------
1254 *---------------------------------------------------------------------
1280 *---------------------------------------------------------------------
1282 *---------------------------------------------------------------------
1289 /* We use the in-out-in algorithm here, using the one's
1301 sum = (uyear /= 4u); /* 4yr rule --> IN */
1302 sum -= (uyear /= 25u); /* 100yr rule --> OUT */
1303 sum += (uyear /= 4u); /* 400yr rule --> IN */
1315 *---------------------------------------------------------------------
1317 *---------------------------------------------------------------------
1328 *---------------------------------------------------------------------
1336 * This code uses the shifted-month-approach to convert month to days,
1341 *---------------------------------------------------------------------
1355 res.lo = m - 2;
1368 res.lo = mu - Q * 12u;
1371 /* Get cummulated days in year with unshift. Use the fractional
1373 * divider.
1375 res.lo = ((res.lo * 979 + 16) >> 5) - 306;
1381 *---------------------------------------------------------------------
1385 * If you want to convert years and days-of-year, just give a month of
1387 *---------------------------------------------------------------------
1410 *---------------------------------------------------------------------
1415 * year, even if months & days are off-scale.
1416 *---------------------------------------------------------------------
1429 mdays -= 2 - is_leapyear(years+1);
1435 - ntpcal_days_in_years(years);
1442 *---------------------------------------------------------------------
1449 *---------------------------------------------------------------------
1466 *---------------------------------------------------------------------
1468 * day-of-month) into the RD of that day.
1469 *---------------------------------------------------------------------
1476 return ntpcal_edate_to_eradays(utm->tm_year + 1899,
1477 utm->tm_mon,
1478 utm->tm_mday - 1) + 1;
1482 *---------------------------------------------------------------------
1484 * day-of-month) into the RD of that day.
1485 *---------------------------------------------------------------------
1492 return ntpcal_edate_to_eradays((int32_t)jd->year - 1,
1493 (int32_t)jd->month - 1,
1494 (int32_t)jd->monthday - 1) + 1;
1498 *---------------------------------------------------------------------
1500 *---------------------------------------------------------------------
1507 return ntpcal_days_in_years(year - 1) + 1;
1511 *---------------------------------------------------------------------
1514 *---------------------------------------------------------------------
1526 return rd - ntpcal_split_eradays(rd - 1, NULL).lo;
1530 *---------------------------------------------------------------------
1532 *---------------------------------------------------------------------
1542 split = ntpcal_split_eradays(rd - 1, &leaps);
1545 return rd - split.lo;
1549 *---------------------------------------------------------------------
1550 * take a 'struct calendar' and get the seconds-of-day from it.
1551 *---------------------------------------------------------------------
1558 return ntpcal_etime_to_seconds(jd->hour, jd->minute,
1559 jd->second);
1563 *---------------------------------------------------------------------
1564 * take a 'struct tm' and get the seconds-of-day from it.
1565 *---------------------------------------------------------------------
1572 return ntpcal_etime_to_seconds(utm->tm_hour, utm->tm_min,
1573 utm->tm_sec);
1577 *---------------------------------------------------------------------
1579 *---------------------------------------------------------------------
1589 days = ntpcal_date_to_rd(jd) - DAY_UNIX_STARTS;
1643 * Convert date to NTP. Ignore yearday, use d/m/y only.
1645 return ntpcal_dayjoin(ntpcal_date_to_rd(jd) - DAY_NTP_STARTS,
1666 * day-of-week calculations
1671 * Given a RataDie and a day-of-week, calculate a RDN that is reater-than,
1672 * greater-or equal, closest, less-or-equal or less-than the given RDN
1673 * and denotes the given day-of-week
1699 return ntpcal_periodic_extend(rdn-3, dow, 7);
1708 return ntpcal_periodic_extend(rdn, dow, -7);
1717 return ntpcal_periodic_extend(rdn-1, dow, -7);
1723 * ISO week-calendar conversions
1739 * possible to interpolate over every single century of the 400-year
1752 * of the century in a 400-year period.
1769 * Given a number of elapsed (ISO-)years since the begin of the
1779 * use: w = (y * 53431 + b[c]) / 1024 as interpolation
1791 yu -= cc * 100u;
1806 /* Get weeks in century. Can use plain division here as all ops
1827 * use: y = (w * 157 + b[c]) / 8192 as interpolation
1836 /* Use two fast cycle-split divisions again. Herew e want to
1840 * This is of course (again) susceptible to internal overflow if
1841 * coded directly in 32bit. And again we use 64bit division on
1843 * remainder first on a 32bit target. With the smaller divider,
1850 sf64 = (uint64_t)-(weeks < 0);
1853 sw = (uint32_t)(sw64 - Q * GREGORIAN_CYCLE_WEEKS);
1859 * (-2^33) % 20871 --> 5491 : the sign bit value
1860 * ( 2^20) % 20871 --> 5026 : the upper digit value
1861 * modinv(20871, 2^32) --> 330081335 : the inverse
1868 Q = (ux - sw) * 330081335u; /* exact div */
1914 id->hour = (uint8_t)ts[0];
1915 id->minute = (uint8_t)ts[1];
1916 id->second = (uint8_t)ts[2];
1919 ds.hi += DAY_NTP_STARTS - 1; /* shift from NTP to RDN */
1923 ud -= uw * DAYSPERWEEK;
1928 id->weekday = (uint8_t)ds.lo + 1; /* weekday result */
1932 id->year = (uint16_t)ds.hi + 1; /* shift to current */
1933 id->week = (uint8_t )ds.lo + 1;
1966 weeks = isocal_weeks_in_years((int32_t)id->year - 1)
1967 + (int32_t)id->week - 1;
1968 days = weeks * 7 + (int32_t)id->weekday;
1970 secs = ntpcal_etime_to_seconds(id->hour, id->minute, id->second);
1972 return ntpcal_dayjoin(days - DAY_NTP_STARTS, secs);
2007 * before the UNIX epoch (1970-01-01). It's probably not possible
2011 jd.monthday -= 1;
2012 ed = ntpcal_date_to_rd(&jd) - DAY_NTP_STARTS;
2027 rc = sscanf(str, "%4hu-%2hu-%2hu%n", &y, &m, &d, &nc);
2030 return ntpcal_edate_to_eradays(y-1, m-1, d)
2031 - DAY_NTP_STARTS;
2073 msyslog(LOG_INFO, "basedate set to %04hu-%02hu-%02hu",
2078 - DAY_NTP_STARTS;
2081 s_gpsweek = (day - NTP_TO_GPS_DAYS) / DAYSPERWEEK;
2083 msyslog(LOG_INFO, "gps base set to %04hu-%02hu-%02hu (week %d)",
2093 retv = (time_t)(s_baseday - NTP_TO_UNIX_DAYS);
2103 retv = (time_t)(s_baseday - NTP_TO_UNIX_DAYS);
2125 # error GPSWEEKS defined wrong -- should be 1024!
2129 diff = ((uint32_t)weekno - s_gpsweek) & (GPSWEEKS - 1);
2139 /* --------------------------------------------------------------------
2140 * reconstruct the centrury from a truncated date and a day-of-week
2142 * Given a date with truncated year (2-digit, 0..99) and a day-of-week
2173 * If this yields a result of 4/5/6, the given date/day-of-week
2184 if ((y >= 100u) || (--m >= 12u) || (--d >= 31u))
2188 m -= 12u;
2189 else if (--y >= 100u)
2194 /* get (wd - d), shifted to positive value, and multiply with
2198 * '--d' above, so we add just 251 here!
2200 c = u32mod7(3 * (251u + wd - d));
2205 y -= 100u;
2225 len = snprintf(buf, len, "%04u-%02u-%02uT%02u:%02u:%02u",
2226 cdp->year, cdp->month, cdp->monthday,
2227 cdp->hour, cdp->minute, cdp->second);
2234 /* -*-EOF-*- */