164070 - PR_ImplodeTime only works with years 1901-2099

Status: RESOLVED FIXED

(NSPR :: NSPR, defect)

Description

[Wan-Teh Chang]

This bug is similar to the limitation of PR_ExplodeTime
described in bug 350.

It turns out that PR_ImplodeTime is using the same
simplistic logic for determining leap years and hence
is subject to the same limitation.  PR_ImplodeTime
only works if the tm_year field of its argument is
between 1901 and 2099 (inclusive).

Comment 1

[Wan-Teh Chang]

This bug was brought to my attention because a user
hit an assertion failure in w95io.c, _PR_FileTimeToPRTime:

PR_ASSERT((cmp / PR_USEC_PER_MSEC) == (*prtm / PR_USEC_PER_MSEC));

The values of the relevant variables are:

systime
   wYear         2165
   wMonth           8
   wDayOfWeek       0
   wDay             4
   wHour           22
   wMinute         11
   wSecond         14
   wMilliseconds  582


cmp      6172409474582000


*prtm    6172323074582873


*filetime
   dwLowDateTime   1614617984
   dwHighDateTime    41482962


PR_USEC_PER_MSEC   1000

The assertion resolves to
PR_ASSERT ( 6172409474582 == 6172323074582 )

The difference between the two values is exactly one
day (86400000 milliseconds).  This is because the
time in question is in year 2165.  PR_ImplodeTime
incorrectly considers year 2100 a leap year and adds
one more day to it, resulting in 'cmp' being greater
than *prtm (which is correct) by one day.

Comment 2

[Shanmu]

Attachment: Proposed fix

The bug in the existing algorithm is that one day is added for every non-leap
century year. To rectify this, this patch deducts one day for every non-leap
century year after (or before) 1970. For years after 2000 the referene years is
2000, while for the years before 1970 the year 1900 is taken as reference year.
The number of non-century years is calculated and that many days are deducted
from the numDays which have been mistakenly added. 

I have tested the values for upto 9999. The results match the epoch time.

Comment 3

[Wan-Teh Chang]

Comment on attachment 191237 [details] [diff] [review]
Proposed fix

Shanmu:

Thanks a lot for coming up with this patch.  I
have some suggested changes.

Please add a comment that explains how your code adjusts
for the non-leap century years.  Without this comment, one
won't be able to figure out what the "nlc" in "nlcyears"
means.	(I know "nlcyears" means "non-leap century years"
because I read this bug report.)

>+    PRInt32 nlcyears=0;
>+    PRInt32 refYear=2000;

Please follow NSPR's coding style exactly, which adds a
space before and after the '=' sign.

>+    while(refYear < copy.tm_year)
>+        {
>+                if (!(refYear % 400 == 0))
>+                        nlcyears++;
>+                refYear += 100;
>+        }

It is a shame that we didn't come up with a closed-form
formula for nlcyears, but since this is not performance
critical code, this brute-force calculation is fine.

Please write this while loop as:

    while (refYear < copy.tm_year) {
	if (refYear % 400 != 0)
	    nlcyears++;
	refYear += 100;
    }

Note the placement of the curly braces and the use of
white space.  You need to imitate the existing code in
the file you modify.  It's important that our changes
preserve the prevalent coding style in the file.

Also note that I changed
    !(refYear % 400 == 0)
to
    refYear % 400 != 0
because the latter is more direct.

>     fourYears = (copy.tm_year - 1970) / 4;
>     remainder = (copy.tm_year - 1970) % 4;
>     if (remainder < 0) {
>         remainder += 4;
>         fourYears--;
>+        refYear=1900;
>+	
>+        while(refYear >= copy.tm_year)
>+        {
>+                if (!(refYear % 400 == 0))
>+                        nlcyears--;
>+                refYear -=100;
>+	}
>     }

This while loop needs to be moved elsewhere.  The purpose
of this if statement is to handle the platforms where the
remainer of dividing a negative number is negative.

This while loop should be put inside a separate if statement
like this:

    if (copy.tm_year < 1970) {
	refYear = 1900;
	while (refYear >= copy.tm_year) {
	    if (refYear % 400 != 0)
		nlcyears--;
	    refYear -=100;
	}
    }

In fact I think we should put the two while loops together
like this:

    if (copy.tm_year >= 1970) {
	refYear = 2000;
	while (refYear < copy.tm_year) {
	    if (refYear % 400 != 0)
		nlcyears++;
	    refYear += 100;
	}
    } else {
	refYear = 1900;
	while (refYear >= copy.tm_year) {
	    if (refYear % 400 != 0)
		nlcyears--;
	    refYear -=100;
	}
    }

Have you tested the years 1901, 1900, and 1899?

>-    numDays = fourYears * (4 * 365 + 1);
>+    numDays = fourYears * (4 * 365 + 1) - nlcyears;
>     switch (remainder) {
>         case 0:
>             break;

I think it is better to do the subtraction of nlcyears
after the switch statement, which completes the (inaccurate)
calculation of numDays.  I like to see we do the (inaccurate)
calculation of numDays first, and then apply the correction.

Comment 4

[Shanmu]

Attachment: Patch with comments and few changes.

I have included the comments that describe the fix. I have also modified 
the patch with the suggestions given by Wan-Teh.

I have tested the patch for all the years that surround the centrury years 
from 1500 - 3000 and the year in question (2165). The values are compared with 

the values obtained from 
http://esqsoft.com/javascript_examples/date-to-epoch.htm . The result looks
good.

Comment 5

[Wan-Teh Chang]

Comment on attachment 192751 [details] [diff] [review]
Patch with comments and few changes.

Hi Shanmu,

Thanks for the new patch.  It seems correct, but please
generate a new patch using "cvs diff -u" for easier review.

I suggest two changes:

1. The comment should describe the resulting code, not the
change.  Your comment says "This function incorrectly assumes
the non-leap century year...", which describes what the old
code did.  This is confusing for people who only look at the
new code.

Please add "non-leap century years" after the nlcyears variable
declaration.

2. Rewrite the two while loops as for loops.

3. Extra credit: I spent some time last time and figured out
closed-form formulas that can replace the brute-force calculations.
You might want to try too so we can compare notes.  Again,
I don't mind checking in the brute-force calculations first
because for the range of years we care about, the performance
penalty is small

Comment 6

[Shanmu]

Wan-Teh,
I am trying to come up with a whole new algorithm to get the calculations 
right. Let us not check in this brute-force calculations now. 

Comment 7

[Shanmu]

Attachment: A new algorithm that calculates the number of leap years rightly.

This is a new algorithm that calculates the number of days since ( and till) 1970. This  algorithm calculates the number of leap years correctly 

#define COUNT_LEAPS(Y)   ( ((Y)-1)/4 - ((Y)-1)/100 + ((Y)-1)/400 )

I have tested this for all the years possible, and this looks good.  This works for years after 1970 and before 1970 correctly. Let me know if this is alright.

I did a "cvs diff -u" to generate this patch. If there are problems please let me know.

Comment 8

[Wan-Teh Chang]

Comment on attachment 200600 [details] [diff] [review]
A new algorithm that calculates the number of leap years rightly.

r=wtc.  I like this patch.  Good job, Shanmu!

Please submit a new patch with the following improvements.

1. Remove the unused macro COUNT_YEARS.  Or, will this macro
be used in the future (for fixing ComputeGMT in bug 350)?

2. Please add a comment to define or explain these macros.
At least explain why we need to subtract 1 from Y; it wasn't
obvious to me.  I figured out that COUNT_DAYS(Y) is the number
of days from 0000-01-01 00:00:00 to Y-01-01 00:00:00, which is
really the end of Year Y-1.  This is why (Y)-1 instead of Y is
used in the macros, right?

3. I found a block of code in PR_NormalizeTime (for
recomputing wday) that is essentially the same as the code
you rewrote in PR_ImpodeTime and should be rewritten the
same way.

Comment 9

[Shanmu]

Attachment: New patch.

1. I wanted to delete this, but forgot to. Deleted in the new patch.
2. Comments added.
3. PR_NormalizeTime routine updated with this patch.

Comment 10

[Shanmu]

Wan-Teh,
Is this ready to submit? I don't have CVS access to submit. You may have to help me submitting this fix.

Comment 11

[Wan-Teh Chang]

Attachment: New patch v2 (as checked in)

I edited the comments and made a minor improvement to
the patch.

I've checked in the patch on the NSPR trunk (NSPR 4.7)
and the NSPRPUB_PRE_4_2_CLIENT_BRANCH (Mozilla 1.9a).

Comment 12

[Wan-Teh Chang]

Shanmu, thanks a lot for your work on this bug.
Now let's move on to tackle bug 350.

Comment 13

[Wan-Teh Chang]

I wrote the following test program to verify that
the new code gives the same result as the old code
for years 1901-2100.

C:\temp>cat time.c
#include <stdio.h>

#define COUNT_LEAPS(Y)   ( ((Y)-1)/4 - ((Y)-1)/100 + ((Y)-1)/400 )
#define COUNT_DAYS(Y)  ( ((Y)-1)*365 + COUNT_LEAPS(Y) )
#define DAYS_BETWEEN_YEARS(A, B)  (COUNT_DAYS(B) - COUNT_DAYS(A))

int main()
{
    int year;
    int fourYears;
    int remainder;
    int numDays;
    int numDaysNew;

    for (year = 1890; year <=2110; year++) {
        numDaysNew = DAYS_BETWEEN_YEARS(1970, year);

        fourYears = (year - 1970) / 4;
        remainder = (year - 1970) % 4;
        if (remainder < 0) {
            remainder += 4;
            fourYears--;
        }
        numDays = fourYears * (4 * 365 + 1);
        switch (remainder) {
        case 0:
            break;
        case 1:  /* 1970 */
            numDays += 365;
            break;
        case 2:  /* 1970-1 */
            numDays += 365 * 2;
            break;
        case 3:  /* 1970-2 */
            numDays += 365 * 3 + 1;
            break;
        }

        if (numDaysNew != numDays) {
            printf("year %d: numDaysNew=%d numDays=%d\n",
                year, numDaysNew, numDays);
        }
    }
    return 0;
}

C:\temp>cl time.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.

time.c
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:time.exe
time.obj

C:\temp>.\time.exe
year 1890: numDaysNew=-29219 numDays=-29220
year 1891: numDaysNew=-28854 numDays=-28855
year 1892: numDaysNew=-28489 numDays=-28490
year 1893: numDaysNew=-28123 numDays=-28124
year 1894: numDaysNew=-27758 numDays=-27759
year 1895: numDaysNew=-27393 numDays=-27394
year 1896: numDaysNew=-27028 numDays=-27029
year 1897: numDaysNew=-26662 numDays=-26663
year 1898: numDaysNew=-26297 numDays=-26298
year 1899: numDaysNew=-25932 numDays=-25933
year 1900: numDaysNew=-25567 numDays=-25568
year 2101: numDaysNew=47847 numDays=47848
year 2102: numDaysNew=48212 numDays=48213
year 2103: numDaysNew=48577 numDays=48578
year 2104: numDaysNew=48942 numDays=48943
year 2105: numDaysNew=49308 numDays=49309
year 2106: numDaysNew=49673 numDays=49674
year 2107: numDaysNew=50038 numDays=50039
year 2108: numDaysNew=50403 numDays=50404
year 2109: numDaysNew=50769 numDays=50770
year 2110: numDaysNew=51134 numDays=51135