Bump to 1.14.1
[platform/upstream/augeas.git] / lib / mktime.c
1 /* Convert a 'struct tm' to a time_t value.
2    Copyright (C) 1993-2016 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Paul Eggert <eggert@twinsun.com>.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, see
18    <http://www.gnu.org/licenses/>.  */
19
20 /* Define this to 1 to have a standalone program to test this implementation of
21    mktime.  */
22 #ifndef DEBUG_MKTIME
23 # define DEBUG_MKTIME 0
24 #endif
25
26 #if !defined _LIBC && !DEBUG_MKTIME
27 # include <config.h>
28 #endif
29
30 /* Assume that leap seconds are possible, unless told otherwise.
31    If the host has a 'zic' command with a '-L leapsecondfilename' option,
32    then it supports leap seconds; otherwise it probably doesn't.  */
33 #ifndef LEAP_SECONDS_POSSIBLE
34 # define LEAP_SECONDS_POSSIBLE 1
35 #endif
36
37 #include <time.h>
38
39 #include <limits.h>
40 #include <stdbool.h>
41
42 #include <intprops.h>
43 #include <verify.h>
44
45 #if DEBUG_MKTIME
46 # include <stdio.h>
47 # include <stdlib.h>
48 # include <string.h>
49 /* Make it work even if the system's libc has its own mktime routine.  */
50 # undef mktime
51 # define mktime my_mktime
52 #endif
53
54 /* A signed type that can represent an integer number of years
55    multiplied by three times the number of seconds in a year.  It is
56    needed when converting a tm_year value times the number of seconds
57    in a year.  The factor of three comes because these products need
58    to be subtracted from each other, and sometimes with an offset
59    added to them, without worrying about overflow.
60
61    Much of the code uses long_int to represent time_t values, to
62    lessen the hassle of dealing with platforms where time_t is
63    unsigned, and because long_int should suffice to represent all
64    time_t values that mktime can generate even on platforms where
65    time_t is excessively wide.  */
66
67 #if INT_MAX <= LONG_MAX / 3 / 366 / 24 / 60 / 60
68 typedef long int long_int;
69 #else
70 typedef long long int long_int;
71 #endif
72 verify (INT_MAX <= TYPE_MAXIMUM (long_int) / 3 / 366 / 24 / 60 / 60);
73
74 /* Shift A right by B bits portably, by dividing A by 2**B and
75    truncating towards minus infinity.  B should be in the range 0 <= B
76    <= LONG_INT_BITS - 2, where LONG_INT_BITS is the number of useful
77    bits in a long_int.  LONG_INT_BITS is at least 32.
78
79    ISO C99 says that A >> B is implementation-defined if A < 0.  Some
80    implementations (e.g., UNICOS 9.0 on a Cray Y-MP EL) don't shift
81    right in the usual way when A < 0, so SHR falls back on division if
82    ordinary A >> B doesn't seem to be the usual signed shift.  */
83
84 static long_int
85 shr (long_int a, int b)
86 {
87   long_int one = 1;
88   return (-one >> 1 == -1
89           ? a >> b
90           : a / (one << b) - (a % (one << b) < 0));
91 }
92
93 /* Bounds for the intersection of time_t and long_int.  */
94
95 static long_int const mktime_min
96   = ((TYPE_SIGNED (time_t) && TYPE_MINIMUM (time_t) < TYPE_MINIMUM (long_int))
97      ? TYPE_MINIMUM (long_int) : TYPE_MINIMUM (time_t));
98 static long_int const mktime_max
99   = (TYPE_MAXIMUM (long_int) < TYPE_MAXIMUM (time_t)
100      ? TYPE_MAXIMUM (long_int) : TYPE_MAXIMUM (time_t));
101
102 verify (TYPE_IS_INTEGER (time_t));
103
104 #define EPOCH_YEAR 1970
105 #define TM_YEAR_BASE 1900
106 verify (TM_YEAR_BASE % 100 == 0);
107
108 /* Is YEAR + TM_YEAR_BASE a leap year?  */
109 static bool
110 leapyear (long_int year)
111 {
112   /* Don't add YEAR to TM_YEAR_BASE, as that might overflow.
113      Also, work even if YEAR is negative.  */
114   return
115     ((year & 3) == 0
116      && (year % 100 != 0
117          || ((year / 100) & 3) == (- (TM_YEAR_BASE / 100) & 3)));
118 }
119
120 /* How many days come before each month (0-12).  */
121 #ifndef _LIBC
122 static
123 #endif
124 const unsigned short int __mon_yday[2][13] =
125   {
126     /* Normal years.  */
127     { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 },
128     /* Leap years.  */
129     { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 }
130   };
131
132
133 #ifdef _LIBC
134 typedef time_t mktime_offset_t;
135 #else
136 /* Portable standalone applications should supply a <time.h> that
137    declares a POSIX-compliant localtime_r, for the benefit of older
138    implementations that lack localtime_r or have a nonstandard one.
139    See the gnulib time_r module for one way to implement this.  */
140 # undef __localtime_r
141 # define __localtime_r localtime_r
142 # define __mktime_internal mktime_internal
143 # include "mktime-internal.h"
144 #endif
145
146 /* Do the values A and B differ according to the rules for tm_isdst?
147    A and B differ if one is zero and the other positive.  */
148 static bool
149 isdst_differ (int a, int b)
150 {
151   return (!a != !b) && (0 <= a) && (0 <= b);
152 }
153
154 /* Return an integer value measuring (YEAR1-YDAY1 HOUR1:MIN1:SEC1) -
155    (YEAR0-YDAY0 HOUR0:MIN0:SEC0) in seconds, assuming that the clocks
156    were not adjusted between the time stamps.
157
158    The YEAR values uses the same numbering as TP->tm_year.  Values
159    need not be in the usual range.  However, YEAR1 must not overflow
160    when multiplied by three times the number of seconds in a year, and
161    likewise for YDAY1 and three times the number of seconds in a day.  */
162
163 static long_int
164 ydhms_diff (long_int year1, long_int yday1, int hour1, int min1, int sec1,
165             int year0, int yday0, int hour0, int min0, int sec0)
166 {
167   verify (-1 / 2 == 0);
168
169   /* Compute intervening leap days correctly even if year is negative.
170      Take care to avoid integer overflow here.  */
171   int a4 = shr (year1, 2) + shr (TM_YEAR_BASE, 2) - ! (year1 & 3);
172   int b4 = shr (year0, 2) + shr (TM_YEAR_BASE, 2) - ! (year0 & 3);
173   int a100 = a4 / 25 - (a4 % 25 < 0);
174   int b100 = b4 / 25 - (b4 % 25 < 0);
175   int a400 = shr (a100, 2);
176   int b400 = shr (b100, 2);
177   int intervening_leap_days = (a4 - b4) - (a100 - b100) + (a400 - b400);
178
179   /* Compute the desired time without overflowing.  */
180   long_int years = year1 - year0;
181   long_int days = 365 * years + yday1 - yday0 + intervening_leap_days;
182   long_int hours = 24 * days + hour1 - hour0;
183   long_int minutes = 60 * hours + min1 - min0;
184   long_int seconds = 60 * minutes + sec1 - sec0;
185   return seconds;
186 }
187
188 /* Return the average of A and B, even if A + B would overflow.
189    Round toward positive infinity.  */
190 static long_int
191 long_int_avg (long_int a, long_int b)
192 {
193   return shr (a, 1) + shr (b, 1) + ((a | b) & 1);
194 }
195
196 /* Return a time_t value corresponding to (YEAR-YDAY HOUR:MIN:SEC),
197    assuming that T corresponds to *TP and that no clock adjustments
198    occurred between *TP and the desired time.
199    Although T and the returned value are of type long_int,
200    they represent time_t values and must be in time_t range.
201    If TP is null, return a value not equal to T; this avoids false matches.
202    YEAR and YDAY must not be so large that multiplying them by three times the
203    number of seconds in a year (or day, respectively) would overflow long_int.
204    If the returned value would be out of range, yield the minimal or
205    maximal in-range value, except do not yield a value equal to T.  */
206 static long_int
207 guess_time_tm (long_int year, long_int yday, int hour, int min, int sec,
208                long_int t, const struct tm *tp)
209 {
210   if (tp)
211     {
212       long_int result;
213       long_int d = ydhms_diff (year, yday, hour, min, sec,
214                                tp->tm_year, tp->tm_yday,
215                                tp->tm_hour, tp->tm_min, tp->tm_sec);
216       if (! INT_ADD_WRAPV (t, d, &result))
217         return result;
218     }
219
220   /* Overflow occurred one way or another.  Return the nearest result
221      that is actually in range, except don't report a zero difference
222      if the actual difference is nonzero, as that would cause a false
223      match; and don't oscillate between two values, as that would
224      confuse the spring-forward gap detector.  */
225   return (t < long_int_avg (mktime_min, mktime_max)
226           ? (t <= mktime_min + 1 ? t + 1 : mktime_min)
227           : (mktime_max - 1 <= t ? t - 1 : mktime_max));
228 }
229
230 /* Use CONVERT to convert T to a struct tm value in *TM.  T must be in
231    range for time_t.  Return TM if successful, NULL if T is out of
232    range for CONVERT.  */
233 static struct tm *
234 convert_time (struct tm *(*convert) (const time_t *, struct tm *),
235               long_int t, struct tm *tm)
236 {
237   time_t x = t;
238   return convert (&x, tm);
239 }
240
241 /* Use CONVERT to convert *T to a broken down time in *TP.
242    If *T is out of range for conversion, adjust it so that
243    it is the nearest in-range value and then convert that.
244    A value is in range if it fits in both time_t and long_int.  */
245 static struct tm *
246 ranged_convert (struct tm *(*convert) (const time_t *, struct tm *),
247                 long_int *t, struct tm *tp)
248 {
249   struct tm *r;
250   if (*t < mktime_min)
251     *t = mktime_min;
252   else if (mktime_max < *t)
253     *t = mktime_max;
254   r = convert_time (convert, *t, tp);
255
256   if (!r && *t)
257     {
258       long_int bad = *t;
259       long_int ok = 0;
260
261       /* BAD is a known unconvertible value, and OK is a known good one.
262          Use binary search to narrow the range between BAD and OK until
263          they differ by 1.  */
264       while (true)
265         {
266           long_int mid = long_int_avg (ok, bad);
267           if (mid != ok && mid != bad)
268             break;
269           r = convert_time (convert, mid, tp);
270           if (r)
271             ok = mid;
272           else
273             bad = mid;
274         }
275
276       if (!r && ok)
277         {
278           /* The last conversion attempt failed;
279              revert to the most recent successful attempt.  */
280           r = convert_time (convert, ok, tp);
281         }
282     }
283
284   return r;
285 }
286
287 /* Convert *TP to a time_t value, inverting
288    the monotonic and mostly-unit-linear conversion function CONVERT.
289    Use *OFFSET to keep track of a guess at the offset of the result,
290    compared to what the result would be for UTC without leap seconds.
291    If *OFFSET's guess is correct, only one CONVERT call is needed.
292    This function is external because it is used also by timegm.c.  */
293 time_t
294 __mktime_internal (struct tm *tp,
295                    struct tm *(*convert) (const time_t *, struct tm *),
296                    mktime_offset_t *offset)
297 {
298   long_int t, gt, t0, t1, t2, dt;
299   struct tm tm;
300
301   /* The maximum number of probes (calls to CONVERT) should be enough
302      to handle any combinations of time zone rule changes, solar time,
303      leap seconds, and oscillations around a spring-forward gap.
304      POSIX.1 prohibits leap seconds, but some hosts have them anyway.  */
305   int remaining_probes = 6;
306
307   /* Time requested.  Copy it in case CONVERT modifies *TP; this can
308      occur if TP is localtime's returned value and CONVERT is localtime.  */
309   int sec = tp->tm_sec;
310   int min = tp->tm_min;
311   int hour = tp->tm_hour;
312   int mday = tp->tm_mday;
313   int mon = tp->tm_mon;
314   int year_requested = tp->tm_year;
315   int isdst = tp->tm_isdst;
316
317   /* 1 if the previous probe was DST.  */
318   int dst2;
319
320   /* Ensure that mon is in range, and set year accordingly.  */
321   int mon_remainder = mon % 12;
322   int negative_mon_remainder = mon_remainder < 0;
323   int mon_years = mon / 12 - negative_mon_remainder;
324   long_int lyear_requested = year_requested;
325   long_int year = lyear_requested + mon_years;
326
327   /* The other values need not be in range:
328      the remaining code handles overflows correctly.  */
329
330   /* Calculate day of year from year, month, and day of month.
331      The result need not be in range.  */
332   int mon_yday = ((__mon_yday[leapyear (year)]
333                    [mon_remainder + 12 * negative_mon_remainder])
334                   - 1);
335   long_int lmday = mday;
336   long_int yday = mon_yday + lmday;
337
338   int negative_offset_guess;
339
340   int sec_requested = sec;
341
342   if (LEAP_SECONDS_POSSIBLE)
343     {
344       /* Handle out-of-range seconds specially,
345          since ydhms_tm_diff assumes every minute has 60 seconds.  */
346       if (sec < 0)
347         sec = 0;
348       if (59 < sec)
349         sec = 59;
350     }
351
352   /* Invert CONVERT by probing.  First assume the same offset as last
353      time.  */
354
355   INT_SUBTRACT_WRAPV (0, *offset, &negative_offset_guess);
356   t0 = ydhms_diff (year, yday, hour, min, sec,
357                    EPOCH_YEAR - TM_YEAR_BASE, 0, 0, 0, negative_offset_guess);
358
359   /* Repeatedly use the error to improve the guess.  */
360
361   for (t = t1 = t2 = t0, dst2 = 0;
362        (gt = guess_time_tm (year, yday, hour, min, sec, t,
363                             ranged_convert (convert, &t, &tm)),
364         t != gt);
365        t1 = t2, t2 = t, t = gt, dst2 = tm.tm_isdst != 0)
366     if (t == t1 && t != t2
367         && (tm.tm_isdst < 0
368             || (isdst < 0
369                 ? dst2 <= (tm.tm_isdst != 0)
370                 : (isdst != 0) != (tm.tm_isdst != 0))))
371       /* We can't possibly find a match, as we are oscillating
372          between two values.  The requested time probably falls
373          within a spring-forward gap of size GT - T.  Follow the common
374          practice in this case, which is to return a time that is GT - T
375          away from the requested time, preferring a time whose
376          tm_isdst differs from the requested value.  (If no tm_isdst
377          was requested and only one of the two values has a nonzero
378          tm_isdst, prefer that value.)  In practice, this is more
379          useful than returning -1.  */
380       goto offset_found;
381     else if (--remaining_probes == 0)
382       return -1;
383
384   /* We have a match.  Check whether tm.tm_isdst has the requested
385      value, if any.  */
386   if (isdst_differ (isdst, tm.tm_isdst))
387     {
388       /* tm.tm_isdst has the wrong value.  Look for a neighboring
389          time with the right value, and use its UTC offset.
390
391          Heuristic: probe the adjacent timestamps in both directions,
392          looking for the desired isdst.  This should work for all real
393          time zone histories in the tz database.  */
394
395       /* Distance between probes when looking for a DST boundary.  In
396          tzdata2003a, the shortest period of DST is 601200 seconds
397          (e.g., America/Recife starting 2000-10-08 01:00), and the
398          shortest period of non-DST surrounded by DST is 694800
399          seconds (Africa/Tunis starting 1943-04-17 01:00).  Use the
400          minimum of these two values, so we don't miss these short
401          periods when probing.  */
402       int stride = 601200;
403
404       /* The longest period of DST in tzdata2003a is 536454000 seconds
405          (e.g., America/Jujuy starting 1946-10-01 01:00).  The longest
406          period of non-DST is much longer, but it makes no real sense
407          to search for more than a year of non-DST, so use the DST
408          max.  */
409       int duration_max = 536454000;
410
411       /* Search in both directions, so the maximum distance is half
412          the duration; add the stride to avoid off-by-1 problems.  */
413       int delta_bound = duration_max / 2 + stride;
414
415       int delta, direction;
416
417       for (delta = stride; delta < delta_bound; delta += stride)
418         for (direction = -1; direction <= 1; direction += 2)
419           {
420             long_int ot;
421             if (! INT_ADD_WRAPV (t, delta * direction, &ot))
422               {
423                 struct tm otm;
424                 ranged_convert (convert, &ot, &otm);
425                 if (! isdst_differ (isdst, otm.tm_isdst))
426                   {
427                     /* We found the desired tm_isdst.
428                        Extrapolate back to the desired time.  */
429                     t = guess_time_tm (year, yday, hour, min, sec, ot, &otm);
430                     ranged_convert (convert, &t, &tm);
431                     goto offset_found;
432                   }
433               }
434           }
435     }
436
437  offset_found:
438   /* Set *OFFSET to the low-order bits of T - T0 - NEGATIVE_OFFSET_GUESS.
439      This is just a heuristic to speed up the next mktime call, and
440      correctness is unaffected if integer overflow occurs here.  */
441   INT_SUBTRACT_WRAPV (t, t0, &dt);
442   INT_SUBTRACT_WRAPV (dt, negative_offset_guess, offset);
443
444   if (LEAP_SECONDS_POSSIBLE && sec_requested != tm.tm_sec)
445     {
446       /* Adjust time to reflect the tm_sec requested, not the normalized value.
447          Also, repair any damage from a false match due to a leap second.  */
448       long_int sec_adjustment = sec == 0 && tm.tm_sec == 60;
449       sec_adjustment -= sec;
450       sec_adjustment += sec_requested;
451       if (INT_ADD_WRAPV (t, sec_adjustment, &t)
452           || ! (mktime_min <= t && t <= mktime_max)
453           || ! convert_time (convert, t, &tm))
454         return -1;
455     }
456
457   *tp = tm;
458   return t;
459 }
460
461
462 static mktime_offset_t localtime_offset;
463
464 /* Convert *TP to a time_t value.  */
465 time_t
466 mktime (struct tm *tp)
467 {
468 #ifdef _LIBC
469   /* POSIX.1 8.1.1 requires that whenever mktime() is called, the
470      time zone names contained in the external variable 'tzname' shall
471      be set as if the tzset() function had been called.  */
472   __tzset ();
473 #elif HAVE_TZSET
474   tzset ();
475 #endif
476
477   return __mktime_internal (tp, __localtime_r, &localtime_offset);
478 }
479
480 #ifdef weak_alias
481 weak_alias (mktime, timelocal)
482 #endif
483
484 #ifdef _LIBC
485 libc_hidden_def (mktime)
486 libc_hidden_weak (timelocal)
487 #endif
488 \f
489 #if DEBUG_MKTIME
490
491 static int
492 not_equal_tm (const struct tm *a, const struct tm *b)
493 {
494   return ((a->tm_sec ^ b->tm_sec)
495           | (a->tm_min ^ b->tm_min)
496           | (a->tm_hour ^ b->tm_hour)
497           | (a->tm_mday ^ b->tm_mday)
498           | (a->tm_mon ^ b->tm_mon)
499           | (a->tm_year ^ b->tm_year)
500           | (a->tm_yday ^ b->tm_yday)
501           | isdst_differ (a->tm_isdst, b->tm_isdst));
502 }
503
504 static void
505 print_tm (const struct tm *tp)
506 {
507   if (tp)
508     printf ("%04d-%02d-%02d %02d:%02d:%02d yday %03d wday %d isdst %d",
509             tp->tm_year + TM_YEAR_BASE, tp->tm_mon + 1, tp->tm_mday,
510             tp->tm_hour, tp->tm_min, tp->tm_sec,
511             tp->tm_yday, tp->tm_wday, tp->tm_isdst);
512   else
513     printf ("0");
514 }
515
516 static int
517 check_result (time_t tk, struct tm tmk, time_t tl, const struct tm *lt)
518 {
519   if (tk != tl || !lt || not_equal_tm (&tmk, lt))
520     {
521       printf ("mktime (");
522       print_tm (lt);
523       printf (")\nyields (");
524       print_tm (&tmk);
525       printf (") == %ld, should be %ld\n", (long int) tk, (long int) tl);
526       return 1;
527     }
528
529   return 0;
530 }
531
532 int
533 main (int argc, char **argv)
534 {
535   int status = 0;
536   struct tm tm, tmk, tml;
537   struct tm *lt;
538   time_t tk, tl, tl1;
539   char trailer;
540
541   /* Sanity check, plus call tzset.  */
542   tl = 0;
543   if (! localtime (&tl))
544     {
545       printf ("localtime (0) fails\n");
546       status = 1;
547     }
548
549   if ((argc == 3 || argc == 4)
550       && (sscanf (argv[1], "%d-%d-%d%c",
551                   &tm.tm_year, &tm.tm_mon, &tm.tm_mday, &trailer)
552           == 3)
553       && (sscanf (argv[2], "%d:%d:%d%c",
554                   &tm.tm_hour, &tm.tm_min, &tm.tm_sec, &trailer)
555           == 3))
556     {
557       tm.tm_year -= TM_YEAR_BASE;
558       tm.tm_mon--;
559       tm.tm_isdst = argc == 3 ? -1 : atoi (argv[3]);
560       tmk = tm;
561       tl = mktime (&tmk);
562       lt = localtime_r (&tl, &tml);
563       printf ("mktime returns %ld == ", (long int) tl);
564       print_tm (&tmk);
565       printf ("\n");
566       status = check_result (tl, tmk, tl, lt);
567     }
568   else if (argc == 4 || (argc == 5 && strcmp (argv[4], "-") == 0))
569     {
570       time_t from = atol (argv[1]);
571       time_t by = atol (argv[2]);
572       time_t to = atol (argv[3]);
573
574       if (argc == 4)
575         for (tl = from; by < 0 ? to <= tl : tl <= to; tl = tl1)
576           {
577             lt = localtime_r (&tl, &tml);
578             if (lt)
579               {
580                 tmk = tml;
581                 tk = mktime (&tmk);
582                 status |= check_result (tk, tmk, tl, &tml);
583               }
584             else
585               {
586                 printf ("localtime_r (%ld) yields 0\n", (long int) tl);
587                 status = 1;
588               }
589             tl1 = tl + by;
590             if ((tl1 < tl) != (by < 0))
591               break;
592           }
593       else
594         for (tl = from; by < 0 ? to <= tl : tl <= to; tl = tl1)
595           {
596             /* Null benchmark.  */
597             lt = localtime_r (&tl, &tml);
598             if (lt)
599               {
600                 tmk = tml;
601                 tk = tl;
602                 status |= check_result (tk, tmk, tl, &tml);
603               }
604             else
605               {
606                 printf ("localtime_r (%ld) yields 0\n", (long int) tl);
607                 status = 1;
608               }
609             tl1 = tl + by;
610             if ((tl1 < tl) != (by < 0))
611               break;
612           }
613     }
614   else
615     printf ("Usage:\
616 \t%s YYYY-MM-DD HH:MM:SS [ISDST] # Test given time.\n\
617 \t%s FROM BY TO # Test values FROM, FROM+BY, ..., TO.\n\
618 \t%s FROM BY TO - # Do not test those values (for benchmark).\n",
619             argv[0], argv[0], argv[0]);
620
621   return status;
622 }
623
624 #endif /* DEBUG_MKTIME */
625 \f
626 /*
627 Local Variables:
628 compile-command: "gcc -DDEBUG_MKTIME -I. -Wall -W -O2 -g mktime.c -o mktime"
629 End:
630 */