[ntp:questions] Re: Question about synchronizing client and server clock
Terje Mathisen
terje.mathisen at hda.hydro.com
Tue Jan 6 09:36:23 UTC 2004
John Howells wrote:
> Terje Mathisen wrote:
>
>>NT's _ftime counts 100 ns intervals, starting from 1600 (?),
>
> 1st January 1601. Although I do not believe it is stated anywhere, this
Thanks.
> is presumably chosen so that all leap year "multiples" (every 4 years,
> every 100 years, and every 400 years) are the last modulo the multiple,
> which makes conversion between a date and an FTIME easier than any other
> origin (assuming all dates use the Gregorian calendar). I.e. assuming
> normal integer division you can do:
>
> int Years = Target_Year - 1601;
> int Days_To_Start_Of_Year = Years * 365 +
> ( Years / 4 ) -
> ( Years / 100 ) +
> ( Years / 400 );
>
> which is not so simple with any other origin.
I'd bet that the "real" origin is 10 months earlier, i.e. after
splitting the tick count into day number and seconds+fraction, they
start by adding (365 - 31 - 28 =) 306 days to the day_number variable.
(This can never overflow, btw.)
In my own (fast) conversion code I use 1600-03-01 00:00 as the origin,
because that makes the leap year handling even easier:
All leap days will then be the last day of the current year, and your
example code above starts to work: You must start with logical year
number zero!
I.e. the following portable code generates very fast machine code on all
the cpus I've tested:
unsigned centuries = years / 100;
unsigned days_to_star_of_year =
years * 365 +
(years >> 2) -
centuries +
(centuries >> 2);
Anyway, this operation (Y-M-D to daynr) is quite trivial with such a
March 1st origin, the opposite direction is much harder.
In fact, by far the fastest way to get from day_number to year is to
guess the year, calculate the corresponding day number, and then
possibly adjust the initial guess! :-)
(See code snippet below!)
Terje
/* Start by subtracting any full 400-year cycles: */
y400 = days / 146097; /* Reciprocal multiplication! */
days -= y400 * 146097;
/* Useful and faster approximation to the number of years, will be wrong
* (too high) 910 times
* in a 400-year cycle, i.e. in 0.62% of all calls.
*
* Requires unsigned values with up to 29 significant bits!
*/
y = (days * 2871 + 1983) >> 20;
/* Calculate # of centuries:
* Since y will be in the 0 to 400 range, the following
* approximation can be used instead of a division by 100:
* y / 100; -> (y * 41) >> 12;
*/
y100 = (y * 41) >> 12;
/* # of days in those full years */
gd = y * 365 /* Normal years */
+ (y >> 2) /* + leap years every 4 years */
- y100 /* - missing century leap years */
+ (y100 >> 2); /* + every 400 years */
/* test for the small chance of a wrong year: */
if (gd > days) {
y--; /* y will be in the [0-399] range! */
y100 = (y * 41) >> 12;
/* The 400-year correction can be skipped! */
gd = y * 365 + (y >> 2) - y100 /* + (y100 >> 2) */;
}
/* Calculate the offset into the current year: */
days -= gd;
--
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
More information about the questions
mailing list