Merged revisions 85921 via svnmerge from
[asterisk/asterisk.git] / main / stdtime / localtime.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2005, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * Most of this code is in the public domain, so clarified as of
9  * June 5, 1996 by Arthur David Olson (arthur_david_olson@nih.gov).
10  *
11  * All modifications to this code to abstract timezones away from
12  * the environment are by Tilghman Lesher, <tlesher@vcch.com>, with
13  * the copyright assigned to Digium.
14  *
15  * See http://www.asterisk.org for more information about
16  * the Asterisk project. Please do not directly contact
17  * any of the maintainers of this project for assistance;
18  * the project provides a web site, mailing lists and IRC
19  * channels for your use.
20  *
21  * This program is free software, distributed under the terms of
22  * the GNU General Public License Version 2. See the LICENSE file
23  * at the top of the source tree.
24  */
25
26 /*! \file
27  *
28  * Multi-timezone Localtime code
29  *
30  * The original source from this file may be obtained from ftp://elsie.nci.nih.gov/pub/
31  */
32
33 /*
34 ** This file is in the public domain, so clarified as of
35 ** 1996-06-05 by Arthur David Olson.
36 */
37
38 /*
39 ** Leap second handling from Bradley White.
40 ** POSIX-style TZ environment variable handling from Guy Harris.
41 */
42
43 /* #define DEBUG */
44
45 /*LINTLIBRARY*/
46
47 #include <sys/types.h>
48 #include <sys/stat.h>
49 #include <fcntl.h>
50 #ifdef DEBUG
51 #include <stdio.h>
52 #endif
53 #include <float.h>
54
55
56 #include "private.h"
57 #include "tzfile.h"
58 #include "asterisk.h"
59
60 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
61
62 #include "asterisk/lock.h"
63 #include "asterisk/localtime.h"
64 #include "asterisk/strings.h"
65 #include "asterisk/linkedlists.h"
66 #include "asterisk/utils.h"
67
68 #ifndef lint
69 #ifndef NOID
70 static char     __attribute__((unused)) elsieid[] = "@(#)localtime.c    8.5";
71 #endif /* !defined NOID */
72 #endif /* !defined lint */
73
74 #ifndef TZ_ABBR_MAX_LEN
75 #define TZ_ABBR_MAX_LEN 16
76 #endif /* !defined TZ_ABBR_MAX_LEN */
77
78 #ifndef TZ_ABBR_CHAR_SET
79 #define TZ_ABBR_CHAR_SET \
80         "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 :+-._"
81 #endif /* !defined TZ_ABBR_CHAR_SET */
82
83 #ifndef TZ_ABBR_ERR_CHAR
84 #define TZ_ABBR_ERR_CHAR        '_'
85 #endif /* !defined TZ_ABBR_ERR_CHAR */
86
87 /*
88 ** SunOS 4.1.1 headers lack O_BINARY.
89 */
90
91 #ifdef O_BINARY
92 #define OPEN_MODE       (O_RDONLY | O_BINARY)
93 #endif /* defined O_BINARY */
94 #ifndef O_BINARY
95 #define OPEN_MODE       O_RDONLY
96 #endif /* !defined O_BINARY */
97
98 static const char       gmt[] = "GMT";
99 static const struct timeval WRONG = { 0, 0 };
100
101 /*! \note
102  * The DST rules to use if TZ has no rules and we can't load TZDEFRULES.
103  * We default to US rules as of 1999-08-17.
104  * POSIX 1003.1 section 8.1.1 says that the default DST rules are
105  * implementation dependent; for historical reasons, US rules are a
106  * common default.
107  */
108 #ifndef TZDEFRULESTRING
109 #define TZDEFRULESTRING ",M4.1.0,M10.5.0"
110 #endif /* !defined TZDEFDST */
111
112 /*!< \brief time type information */
113 struct ttinfo {                         /* time type information */
114         long            tt_gmtoff;      /* UTC offset in seconds */
115         int             tt_isdst;       /* used to set tm_isdst */
116         int             tt_abbrind;     /* abbreviation list index */
117         int             tt_ttisstd;     /* TRUE if transition is std time */
118         int             tt_ttisgmt;     /* TRUE if transition is UTC */
119 };
120
121 /*! \brief leap second information */
122 struct lsinfo {                         /* leap second information */
123         time_t          ls_trans;       /* transition time */
124         long            ls_corr;        /* correction to apply */
125 };
126
127 #define BIGGEST(a, b)   (((a) > (b)) ? (a) : (b))
128
129 #ifdef TZNAME_MAX
130 #define MY_TZNAME_MAX   TZNAME_MAX
131 #endif /* defined TZNAME_MAX */
132 #ifndef TZNAME_MAX
133 #define MY_TZNAME_MAX   255
134 #endif /* !defined TZNAME_MAX */
135 #ifndef TZ_STRLEN_MAX
136 #define TZ_STRLEN_MAX   255
137 #endif /* !defined TZ_STRLEN_MAX */
138
139 struct state {
140         /*! Name of the file that this references */
141         char    name[TZ_STRLEN_MAX + 1];
142         int             leapcnt;
143         int             timecnt;
144         int             typecnt;
145         int             charcnt;
146         int             goback;
147         int             goahead;
148         time_t          ats[TZ_MAX_TIMES];
149         unsigned char   types[TZ_MAX_TIMES];
150         struct ttinfo   ttis[TZ_MAX_TYPES];
151         char            chars[BIGGEST(BIGGEST(TZ_MAX_CHARS + 1, sizeof gmt),
152                                 (2 * (MY_TZNAME_MAX + 1)))];
153         struct lsinfo   lsis[TZ_MAX_LEAPS];
154         AST_LIST_ENTRY(state) list;
155 };
156
157 struct rule {
158         int             r_type;         /* type of rule--see below */
159         int             r_day;          /* day number of rule */
160         int             r_week;         /* week number of rule */
161         int             r_mon;          /* month number of rule */
162         long            r_time;         /* transition time of rule */
163 };
164
165 #define JULIAN_DAY              0       /* Jn - Julian day */
166 #define DAY_OF_YEAR             1       /* n - day of year */
167 #define MONTH_NTH_DAY_OF_WEEK   2       /* Mm.n.d - month, week, day of week */
168
169 /*
170 ** Prototypes for static functions.
171 */
172
173 static long             detzcode P((const char * codep));
174 static time_t           detzcode64 P((const char * codep));
175 static int              differ_by_repeat P((time_t t1, time_t t0));
176 static const char *     getzname P((const char * strp));
177 static const char *     getqzname P((const char * strp, const int delim));
178 static const char *     getnum P((const char * strp, int * nump, int min,
179                                 int max));
180 static const char *     getsecs P((const char * strp, long * secsp));
181 static const char *     getoffset P((const char * strp, long * offsetp));
182 static const char *     getrule P((const char * strp, struct rule * rulep));
183 static int              gmtload P((struct state * sp));
184 static struct ast_tm *  gmtsub P((const struct timeval * timep, long offset,
185                                 struct ast_tm * tmp));
186 static struct ast_tm *  localsub P((const struct timeval * timep, long offset,
187                                 struct ast_tm * tmp, const struct state *sp));
188 static int              increment_overflow P((int * number, int delta));
189 static int              leaps_thru_end_of P((int y));
190 static int              long_increment_overflow P((long * number, int delta));
191 static int              long_normalize_overflow P((long * tensptr,
192                                 int * unitsptr, const int base));
193 static int              normalize_overflow P((int * tensptr, int * unitsptr,
194                                 const int base));
195 static struct timeval   time1 P((struct ast_tm * tmp,
196                                 struct ast_tm * (*funcp) P((const struct timeval *,
197                                 long, struct ast_tm *, const struct state *sp)),
198                                 long offset, const struct state *sp));
199 static struct timeval   time2 P((struct ast_tm *tmp,
200                                 struct ast_tm * (*funcp) P((const struct timeval *,
201                                 long, struct ast_tm*, const struct state *sp)),
202                                 long offset, int * okayp, const struct state *sp));
203 static struct timeval   time2sub P((struct ast_tm *tmp,
204                                 struct ast_tm * (*funcp) (const struct timeval *,
205                                 long, struct ast_tm*, const struct state *sp),
206                                 long offset, int * okayp, int do_norm_secs, const struct state *sp));
207 static struct ast_tm *  timesub P((const struct timeval * timep, long offset,
208                                 const struct state * sp, struct ast_tm * tmp));
209 static int              tmcomp P((const struct ast_tm * atmp,
210                                 const struct ast_tm * btmp));
211 static time_t           transtime P((time_t janfirst, int year,
212                                 const struct rule * rulep, long offset));
213 static int              tzload P((const char * name, struct state * sp,
214                                 int doextend));
215 static int              tzparse P((const char * name, struct state * sp,
216                                 int lastditch));
217
218 static AST_LIST_HEAD_STATIC(zonelist, state);
219
220 #ifndef TZ_STRLEN_MAX
221 #define TZ_STRLEN_MAX 255
222 #endif /* !defined TZ_STRLEN_MAX */
223
224 /*! \note
225 ** Section 4.12.3 of X3.159-1989 requires that
226 **      Except for the strftime function, these functions [asctime,
227 **      ctime, gmtime, localtime] return values in one of two static
228 **      objects: a broken-down time structure and an array of char.
229 ** Thanks to Paul Eggert for noting this.
230 */
231
232 static long detzcode(const char * const codep)
233 {
234         long    result;
235         int     i;
236
237         result = (codep[0] & 0x80) ? ~0L : 0;
238         for (i = 0; i < 4; ++i)
239                 result = (result << 8) | (codep[i] & 0xff);
240         return result;
241 }
242
243 static time_t detzcode64(const char * const codep)
244 {
245         time_t  result;
246         int     i;
247
248         result = (codep[0] & 0x80) ?  (~(int_fast64_t) 0) : 0;
249         for (i = 0; i < 8; ++i)
250                 result = result * 256 + (codep[i] & 0xff);
251         return result;
252 }
253
254 static int differ_by_repeat(const time_t t1, const time_t t0)
255 {
256         const long long at1 = t1, at0 = t0;
257         if (TYPE_INTEGRAL(time_t) &&
258                 TYPE_BIT(time_t) - TYPE_SIGNED(time_t) < SECSPERREPEAT_BITS)
259                         return 0;
260         return at1 - at0 == SECSPERREPEAT;
261 }
262
263 static int tzload(const char *name, struct state * const sp, const int doextend)
264 {
265         const char *            p;
266         int                     i;
267         int                     fid;
268         int                     stored;
269         int                     nread;
270         union {
271                 struct tzhead   tzhead;
272                 char            buf[2 * sizeof(struct tzhead) +
273                                         2 * sizeof *sp +
274                                         4 * TZ_MAX_TIMES];
275         } u;
276
277         if (name == NULL && (name = TZDEFAULT) == NULL)
278                 return -1;
279         {
280                 int     doaccess;
281                 /*
282                 ** Section 4.9.1 of the C standard says that
283                 ** "FILENAME_MAX expands to an integral constant expression
284                 ** that is the size needed for an array of char large enough
285                 ** to hold the longest file name string that the implementation
286                 ** guarantees can be opened."
287                 */
288                 char            fullname[FILENAME_MAX + 1];
289
290                 if (name[0] == ':')
291                         ++name;
292                 doaccess = name[0] == '/';
293                 if (!doaccess) {
294                         if ((p = TZDIR) == NULL)
295                                 return -1;
296                         if ((strlen(p) + strlen(name) + 1) >= sizeof fullname)
297                                 return -1;
298                         (void) strcpy(fullname, p);
299                         (void) strcat(fullname, "/");
300                         (void) strcat(fullname, name);
301                         /*
302                         ** Set doaccess if '.' (as in "../") shows up in name.
303                         */
304                         if (strchr(name, '.') != NULL)
305                                 doaccess = TRUE;
306                         name = fullname;
307                 }
308                 if (doaccess && access(name, R_OK) != 0)
309                         return -1;
310                 if ((fid = open(name, OPEN_MODE)) == -1)
311                         return -1;
312         }
313         nread = read(fid, u.buf, sizeof u.buf);
314         if (close(fid) < 0 || nread <= 0)
315                 return -1;
316         for (stored = 4; stored <= 8; stored *= 2) {
317                 int             ttisstdcnt;
318                 int             ttisgmtcnt;
319
320                 ttisstdcnt = (int) detzcode(u.tzhead.tzh_ttisstdcnt);
321                 ttisgmtcnt = (int) detzcode(u.tzhead.tzh_ttisgmtcnt);
322                 sp->leapcnt = (int) detzcode(u.tzhead.tzh_leapcnt);
323                 sp->timecnt = (int) detzcode(u.tzhead.tzh_timecnt);
324                 sp->typecnt = (int) detzcode(u.tzhead.tzh_typecnt);
325                 sp->charcnt = (int) detzcode(u.tzhead.tzh_charcnt);
326                 p = u.tzhead.tzh_charcnt + sizeof u.tzhead.tzh_charcnt;
327                 if (sp->leapcnt < 0 || sp->leapcnt > TZ_MAX_LEAPS ||
328                         sp->typecnt <= 0 || sp->typecnt > TZ_MAX_TYPES ||
329                         sp->timecnt < 0 || sp->timecnt > TZ_MAX_TIMES ||
330                         sp->charcnt < 0 || sp->charcnt > TZ_MAX_CHARS ||
331                         (ttisstdcnt != sp->typecnt && ttisstdcnt != 0) ||
332                         (ttisgmtcnt != sp->typecnt && ttisgmtcnt != 0))
333                                 return -1;
334                 if (nread - (p - u.buf) <
335                         sp->timecnt * stored +          /* ats */
336                         sp->timecnt +                   /* types */
337                         sp->typecnt * 6 +               /* ttinfos */
338                         sp->charcnt +                   /* chars */
339                         sp->leapcnt * (stored + 4) +    /* lsinfos */
340                         ttisstdcnt +                    /* ttisstds */
341                         ttisgmtcnt)                     /* ttisgmts */
342                                 return -1;
343                 for (i = 0; i < sp->timecnt; ++i) {
344                         sp->ats[i] = (stored == 4) ?
345                                 detzcode(p) : detzcode64(p);
346                         p += stored;
347                 }
348                 for (i = 0; i < sp->timecnt; ++i) {
349                         sp->types[i] = (unsigned char) *p++;
350                         if (sp->types[i] >= sp->typecnt)
351                                 return -1;
352                 }
353                 for (i = 0; i < sp->typecnt; ++i) {
354                         struct ttinfo * ttisp;
355
356                         ttisp = &sp->ttis[i];
357                         ttisp->tt_gmtoff = detzcode(p);
358                         p += 4;
359                         ttisp->tt_isdst = (unsigned char) *p++;
360                         if (ttisp->tt_isdst != 0 && ttisp->tt_isdst != 1)
361                                 return -1;
362                         ttisp->tt_abbrind = (unsigned char) *p++;
363                         if (ttisp->tt_abbrind < 0 ||
364                                 ttisp->tt_abbrind > sp->charcnt)
365                                         return -1;
366                 }
367                 for (i = 0; i < sp->charcnt; ++i)
368                         sp->chars[i] = *p++;
369                 sp->chars[i] = '\0';    /* ensure '\0' at end */
370                 for (i = 0; i < sp->leapcnt; ++i) {
371                         struct lsinfo * lsisp;
372
373                         lsisp = &sp->lsis[i];
374                         lsisp->ls_trans = (stored == 4) ?
375                                 detzcode(p) : detzcode64(p);
376                         p += stored;
377                         lsisp->ls_corr = detzcode(p);
378                         p += 4;
379                 }
380                 for (i = 0; i < sp->typecnt; ++i) {
381                         struct ttinfo * ttisp;
382
383                         ttisp = &sp->ttis[i];
384                         if (ttisstdcnt == 0)
385                                 ttisp->tt_ttisstd = FALSE;
386                         else {
387                                 ttisp->tt_ttisstd = *p++;
388                                 if (ttisp->tt_ttisstd != TRUE &&
389                                         ttisp->tt_ttisstd != FALSE)
390                                                 return -1;
391                         }
392                 }
393                 for (i = 0; i < sp->typecnt; ++i) {
394                         struct ttinfo * ttisp;
395
396                         ttisp = &sp->ttis[i];
397                         if (ttisgmtcnt == 0)
398                                 ttisp->tt_ttisgmt = FALSE;
399                         else {
400                                 ttisp->tt_ttisgmt = *p++;
401                                 if (ttisp->tt_ttisgmt != TRUE &&
402                                         ttisp->tt_ttisgmt != FALSE)
403                                                 return -1;
404                         }
405                 }
406                 /*
407                 ** Out-of-sort ats should mean we're running on a
408                 ** signed time_t system but using a data file with
409                 ** unsigned values (or vice versa).
410                 */
411                 for (i = 0; i < sp->timecnt - 2; ++i)
412                         if (sp->ats[i] > sp->ats[i + 1]) {
413                                 ++i;
414                                 if (TYPE_SIGNED(time_t)) {
415                                         /*
416                                         ** Ignore the end (easy).
417                                         */
418                                         sp->timecnt = i;
419                                 } else {
420                                         /*
421                                         ** Ignore the beginning (harder).
422                                         */
423                                         int     j;
424
425                                         for (j = 0; j + i < sp->timecnt; ++j) {
426                                                 sp->ats[j] = sp->ats[j + i];
427                                                 sp->types[j] = sp->types[j + i];
428                                         }
429                                         sp->timecnt = j;
430                                 }
431                                 break;
432                         }
433                 /*
434                 ** If this is an old file, we're done.
435                 */
436                 if (u.tzhead.tzh_version[0] == '\0')
437                         break;
438                 nread -= p - u.buf;
439                 for (i = 0; i < nread; ++i)
440                         u.buf[i] = p[i];
441                 /*
442                 ** If this is a narrow integer time_t system, we're done.
443                 */
444                 if (stored >= (int) sizeof(time_t) && TYPE_INTEGRAL(time_t))
445                         break;
446         }
447         if (doextend && nread > 2 &&
448                 u.buf[0] == '\n' && u.buf[nread - 1] == '\n' &&
449                 sp->typecnt + 2 <= TZ_MAX_TYPES) {
450                         struct state    ts;
451                         int     result;
452
453                         u.buf[nread - 1] = '\0';
454                         result = tzparse(&u.buf[1], &ts, FALSE);
455                         if (result == 0 && ts.typecnt == 2 &&
456                                 sp->charcnt + ts.charcnt <= TZ_MAX_CHARS) {
457                                         for (i = 0; i < 2; ++i)
458                                                 ts.ttis[i].tt_abbrind +=
459                                                         sp->charcnt;
460                                         for (i = 0; i < ts.charcnt; ++i)
461                                                 sp->chars[sp->charcnt++] =
462                                                         ts.chars[i];
463                                         i = 0;
464                                         while (i < ts.timecnt &&
465                                                 ts.ats[i] <=
466                                                 sp->ats[sp->timecnt - 1])
467                                                         ++i;
468                                         while (i < ts.timecnt &&
469                                             sp->timecnt < TZ_MAX_TIMES) {
470                                                 sp->ats[sp->timecnt] =
471                                                         ts.ats[i];
472                                                 sp->types[sp->timecnt] =
473                                                         sp->typecnt +
474                                                         ts.types[i];
475                                                 ++sp->timecnt;
476                                                 ++i;
477                                         }
478                                         sp->ttis[sp->typecnt++] = ts.ttis[0];
479                                         sp->ttis[sp->typecnt++] = ts.ttis[1];
480                         }
481         }
482         i = 2 * YEARSPERREPEAT;
483         sp->goback = sp->goahead = sp->timecnt > i;
484         sp->goback = sp->goback && sp->types[i] == sp->types[0] &&
485                 differ_by_repeat(sp->ats[i], sp->ats[0]);
486         sp->goahead = sp->goahead &&
487                 sp->types[sp->timecnt - 1] == sp->types[sp->timecnt - 1 - i] &&
488                 differ_by_repeat(sp->ats[sp->timecnt - 1],
489                          sp->ats[sp->timecnt - 1 - i]);
490         return 0;
491 }
492
493 static const int        mon_lengths[2][MONSPERYEAR] = {
494         { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
495         { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
496 };
497
498 static const int        year_lengths[2] = {
499         DAYSPERNYEAR, DAYSPERLYEAR
500 };
501
502 /*! \brief
503 ** Given a pointer into a time zone string, scan until a character that is not
504 ** a valid character in a zone name is found. Return a pointer to that
505 ** character.
506 */
507
508 static const char * getzname(const char *strp)
509 {
510         char    c;
511
512         while ((c = *strp) != '\0' && !is_digit(c) && c != ',' && c != '-' &&
513                 c != '+')
514                         ++strp;
515         return strp;
516 }
517
518 /*! \brief
519 ** Given a pointer into an extended time zone string, scan until the ending
520 ** delimiter of the zone name is located. Return a pointer to the delimiter.
521 **
522 ** As with getzname above, the legal character set is actually quite
523 ** restricted, with other characters producing undefined results.
524 ** We don't do any checking here; checking is done later in common-case code.
525 */
526
527 static const char * getqzname(const char *strp, const int delim)
528 {
529         int     c;
530
531         while ((c = *strp) != '\0' && c != delim)
532                 ++strp;
533         return strp;
534 }
535
536 /*! \brief
537 ** Given a pointer into a time zone string, extract a number from that string.
538 ** Check that the number is within a specified range; if it is not, return
539 ** NULL.
540 ** Otherwise, return a pointer to the first character not part of the number.
541 */
542
543 static const char *getnum(const char *strp, int *nump, const int min, const int max)
544 {
545         char    c;
546         int     num;
547
548         if (strp == NULL || !is_digit(c = *strp))
549                 return NULL;
550         num = 0;
551         do {
552                 num = num * 10 + (c - '0');
553                 if (num > max)
554                         return NULL;    /* illegal value */
555                 c = *++strp;
556         } while (is_digit(c));
557         if (num < min)
558                 return NULL;            /* illegal value */
559         *nump = num;
560         return strp;
561 }
562
563 /*! \brief
564 ** Given a pointer into a time zone string, extract a number of seconds,
565 ** in hh[:mm[:ss]] form, from the string.
566 ** If any error occurs, return NULL.
567 ** Otherwise, return a pointer to the first character not part of the number
568 ** of seconds.
569 */
570
571 static const char *getsecs(const char *strp, long * const secsp)
572 {
573         int     num;
574
575         /*
576         ** `HOURSPERDAY * DAYSPERWEEK - 1' allows quasi-Posix rules like
577         ** "M10.4.6/26", which does not conform to Posix,
578         ** but which specifies the equivalent of
579         ** ``02:00 on the first Sunday on or after 23 Oct''.
580         */
581         strp = getnum(strp, &num, 0, HOURSPERDAY * DAYSPERWEEK - 1);
582         if (strp == NULL)
583                 return NULL;
584         *secsp = num * (long) SECSPERHOUR;
585         if (*strp == ':') {
586                 ++strp;
587                 strp = getnum(strp, &num, 0, MINSPERHOUR - 1);
588                 if (strp == NULL)
589                         return NULL;
590                 *secsp += num * SECSPERMIN;
591                 if (*strp == ':') {
592                         ++strp;
593                         /* `SECSPERMIN' allows for leap seconds. */
594                         strp = getnum(strp, &num, 0, SECSPERMIN);
595                         if (strp == NULL)
596                                 return NULL;
597                         *secsp += num;
598                 }
599         }
600         return strp;
601 }
602
603 /*! \brief
604 ** Given a pointer into a time zone string, extract an offset, in
605 ** [+-]hh[:mm[:ss]] form, from the string.
606 ** If any error occurs, return NULL.
607 ** Otherwise, return a pointer to the first character not part of the time.
608 */
609
610 static const char *getoffset(const char *strp, long *offsetp)
611 {
612         int     neg = 0;
613
614         if (*strp == '-') {
615                 neg = 1;
616                 ++strp;
617         } else if (*strp == '+')
618                 ++strp;
619         strp = getsecs(strp, offsetp);
620         if (strp == NULL)
621                 return NULL;            /* illegal time */
622         if (neg)
623                 *offsetp = -*offsetp;
624         return strp;
625 }
626
627 /*! \brief
628 ** Given a pointer into a time zone string, extract a rule in the form
629 ** date[/time]. See POSIX section 8 for the format of "date" and "time".
630 ** If a valid rule is not found, return NULL.
631 ** Otherwise, return a pointer to the first character not part of the rule.
632 */
633
634 static const char *getrule(const char *strp, struct rule *rulep)
635 {
636         if (*strp == 'J') {
637                 /*
638                 ** Julian day.
639                 */
640                 rulep->r_type = JULIAN_DAY;
641                 ++strp;
642                 strp = getnum(strp, &rulep->r_day, 1, DAYSPERNYEAR);
643         } else if (*strp == 'M') {
644                 /*
645                 ** Month, week, day.
646                 */
647                 rulep->r_type = MONTH_NTH_DAY_OF_WEEK;
648                 ++strp;
649                 strp = getnum(strp, &rulep->r_mon, 1, MONSPERYEAR);
650                 if (strp == NULL)
651                         return NULL;
652                 if (*strp++ != '.')
653                         return NULL;
654                 strp = getnum(strp, &rulep->r_week, 1, 5);
655                 if (strp == NULL)
656                         return NULL;
657                 if (*strp++ != '.')
658                         return NULL;
659                 strp = getnum(strp, &rulep->r_day, 0, DAYSPERWEEK - 1);
660         } else if (is_digit(*strp)) {
661                 /*
662                 ** Day of year.
663                 */
664                 rulep->r_type = DAY_OF_YEAR;
665                 strp = getnum(strp, &rulep->r_day, 0, DAYSPERLYEAR - 1);
666         } else  return NULL;            /* invalid format */
667         if (strp == NULL)
668                 return NULL;
669         if (*strp == '/') {
670                 /*
671                 ** Time specified.
672                 */
673                 ++strp;
674                 strp = getsecs(strp, &rulep->r_time);
675         } else  rulep->r_time = 2 * SECSPERHOUR;        /* default = 2:00:00 */
676         return strp;
677 }
678
679 /*! \brief
680 ** Given the Epoch-relative time of January 1, 00:00:00 UTC, in a year, the
681 ** year, a rule, and the offset from UTC at the time that rule takes effect,
682 ** calculate the Epoch-relative time that rule takes effect.
683 */
684
685 static time_t transtime(const time_t janfirst, const int year, const struct rule *rulep, const long offset)
686 {
687         int     leapyear;
688         time_t  value;
689         int     i;
690         int             d, m1, yy0, yy1, yy2, dow;
691
692         INITIALIZE(value);
693         leapyear = isleap(year);
694         switch (rulep->r_type) {
695
696         case JULIAN_DAY:
697                 /*
698                 ** Jn - Julian day, 1 == January 1, 60 == March 1 even in leap
699                 ** years.
700                 ** In non-leap years, or if the day number is 59 or less, just
701                 ** add SECSPERDAY times the day number-1 to the time of
702                 ** January 1, midnight, to get the day.
703                 */
704                 value = janfirst + (rulep->r_day - 1) * SECSPERDAY;
705                 if (leapyear && rulep->r_day >= 60)
706                         value += SECSPERDAY;
707                 break;
708
709         case DAY_OF_YEAR:
710                 /*
711                 ** n - day of year.
712                 ** Just add SECSPERDAY times the day number to the time of
713                 ** January 1, midnight, to get the day.
714                 */
715                 value = janfirst + rulep->r_day * SECSPERDAY;
716                 break;
717
718         case MONTH_NTH_DAY_OF_WEEK:
719                 /*
720                 ** Mm.n.d - nth "dth day" of month m.
721                 */
722                 value = janfirst;
723                 for (i = 0; i < rulep->r_mon - 1; ++i)
724                         value += mon_lengths[leapyear][i] * SECSPERDAY;
725
726                 /*
727                 ** Use Zeller's Congruence to get day-of-week of first day of
728                 ** month.
729                 */
730                 m1 = (rulep->r_mon + 9) % 12 + 1;
731                 yy0 = (rulep->r_mon <= 2) ? (year - 1) : year;
732                 yy1 = yy0 / 100;
733                 yy2 = yy0 % 100;
734                 dow = ((26 * m1 - 2) / 10 +
735                         1 + yy2 + yy2 / 4 + yy1 / 4 - 2 * yy1) % 7;
736                 if (dow < 0)
737                         dow += DAYSPERWEEK;
738
739                 /*
740                 ** "dow" is the day-of-week of the first day of the month. Get
741                 ** the day-of-month (zero-origin) of the first "dow" day of the
742                 ** month.
743                 */
744                 d = rulep->r_day - dow;
745                 if (d < 0)
746                         d += DAYSPERWEEK;
747                 for (i = 1; i < rulep->r_week; ++i) {
748                         if (d + DAYSPERWEEK >=
749                                 mon_lengths[leapyear][rulep->r_mon - 1])
750                                         break;
751                         d += DAYSPERWEEK;
752                 }
753
754                 /*
755                 ** "d" is the day-of-month (zero-origin) of the day we want.
756                 */
757                 value += d * SECSPERDAY;
758                 break;
759         }
760
761         /*
762         ** "value" is the Epoch-relative time of 00:00:00 UTC on the day in
763         ** question. To get the Epoch-relative time of the specified local
764         ** time on that day, add the transition time and the current offset
765         ** from UTC.
766         */
767         return value + rulep->r_time + offset;
768 }
769
770 /*! \note
771 ** Given a POSIX section 8-style TZ string, fill in the rule tables as
772 ** appropriate.
773 */
774
775 static int tzparse(const char *name, struct state *sp, const int lastditch)
776 {
777         const char *                    stdname;
778         const char *                    dstname;
779         size_t                          stdlen;
780         size_t                          dstlen;
781         long                            stdoffset;
782         long                            dstoffset;
783         time_t *                atp;
784         unsigned char * typep;
785         char *                  cp;
786         int                     load_result;
787
788         INITIALIZE(dstname);
789         stdname = name;
790         if (lastditch) {
791                 stdlen = strlen(name);  /* length of standard zone name */
792                 name += stdlen;
793                 if (stdlen >= sizeof sp->chars)
794                         stdlen = (sizeof sp->chars) - 1;
795                 stdoffset = 0;
796         } else {
797                 if (*name == '<') {
798                         name++;
799                         stdname = name;
800                         name = getqzname(name, '>');
801                         if (*name != '>')
802                                 return -1;
803                         stdlen = name - stdname;
804                         name++;
805                 } else {
806                         name = getzname(name);
807                         stdlen = name - stdname;
808                 }
809                 if (*name == '\0')
810                         return -1;
811                 name = getoffset(name, &stdoffset);
812                 if (name == NULL)
813                         return -1;
814         }
815         load_result = tzload(TZDEFRULES, sp, FALSE);
816         if (load_result != 0)
817                 sp->leapcnt = 0;                /* so, we're off a little */
818         if (*name != '\0') {
819                 if (*name == '<') {
820                         dstname = ++name;
821                         name = getqzname(name, '>');
822                         if (*name != '>')
823                                 return -1;
824                         dstlen = name - dstname;
825                         name++;
826                 } else {
827                         dstname = name;
828                         name = getzname(name);
829                         dstlen = name - dstname; /* length of DST zone name */
830                 }
831                 if (*name != '\0' && *name != ',' && *name != ';') {
832                         name = getoffset(name, &dstoffset);
833                         if (name == NULL)
834                                 return -1;
835                 } else  dstoffset = stdoffset - SECSPERHOUR;
836                 if (*name == '\0' && load_result != 0)
837                         name = TZDEFRULESTRING;
838                 if (*name == ',' || *name == ';') {
839                         struct rule     start;
840                         struct rule     end;
841                         int     year;
842                         time_t  janfirst;
843                         time_t          starttime;
844                         time_t          endtime;
845
846                         ++name;
847                         if ((name = getrule(name, &start)) == NULL)
848                                 return -1;
849                         if (*name++ != ',')
850                                 return -1;
851                         if ((name = getrule(name, &end)) == NULL)
852                                 return -1;
853                         if (*name != '\0')
854                                 return -1;
855                         sp->typecnt = 2;        /* standard time and DST */
856                         /*
857                         ** Two transitions per year, from EPOCH_YEAR forward.
858                         */
859                         sp->ttis[0].tt_gmtoff = -dstoffset;
860                         sp->ttis[0].tt_isdst = 1;
861                         sp->ttis[0].tt_abbrind = stdlen + 1;
862                         sp->ttis[1].tt_gmtoff = -stdoffset;
863                         sp->ttis[1].tt_isdst = 0;
864                         sp->ttis[1].tt_abbrind = 0;
865                         atp = sp->ats;
866                         typep = sp->types;
867                         janfirst = 0;
868                         sp->timecnt = 0;
869                         for (year = EPOCH_YEAR;
870                             sp->timecnt + 2 <= TZ_MAX_TIMES;
871                             ++year) {
872                                 time_t  newfirst;
873
874                                 starttime = transtime(janfirst, year, &start,
875                                         stdoffset);
876                                 endtime = transtime(janfirst, year, &end,
877                                         dstoffset);
878                                 if (starttime > endtime) {
879                                         *atp++ = endtime;
880                                         *typep++ = 1;   /* DST ends */
881                                         *atp++ = starttime;
882                                         *typep++ = 0;   /* DST begins */
883                                 } else {
884                                         *atp++ = starttime;
885                                         *typep++ = 0;   /* DST begins */
886                                         *atp++ = endtime;
887                                         *typep++ = 1;   /* DST ends */
888                                 }
889                                 sp->timecnt += 2;
890                                 newfirst = janfirst;
891                                 newfirst += year_lengths[isleap(year)] *
892                                         SECSPERDAY;
893                                 if (newfirst <= janfirst)
894                                         break;
895                                 janfirst = newfirst;
896                         }
897                 } else {
898                         long    theirstdoffset;
899                         long    theirdstoffset;
900                         long    theiroffset;
901                         int     isdst;
902                         int     i;
903                         int     j;
904
905                         if (*name != '\0')
906                                 return -1;
907                         /*
908                         ** Initial values of theirstdoffset and theirdstoffset.
909                         */
910                         theirstdoffset = 0;
911                         for (i = 0; i < sp->timecnt; ++i) {
912                                 j = sp->types[i];
913                                 if (!sp->ttis[j].tt_isdst) {
914                                         theirstdoffset =
915                                                 -sp->ttis[j].tt_gmtoff;
916                                         break;
917                                 }
918                         }
919                         theirdstoffset = 0;
920                         for (i = 0; i < sp->timecnt; ++i) {
921                                 j = sp->types[i];
922                                 if (sp->ttis[j].tt_isdst) {
923                                         theirdstoffset =
924                                                 -sp->ttis[j].tt_gmtoff;
925                                         break;
926                                 }
927                         }
928                         /*
929                         ** Initially we're assumed to be in standard time.
930                         */
931                         isdst = FALSE;
932                         theiroffset = theirstdoffset;
933                         /*
934                         ** Now juggle transition times and types
935                         ** tracking offsets as you do.
936                         */
937                         for (i = 0; i < sp->timecnt; ++i) {
938                                 j = sp->types[i];
939                                 sp->types[i] = sp->ttis[j].tt_isdst;
940                                 if (sp->ttis[j].tt_ttisgmt) {
941                                         /* No adjustment to transition time */
942                                 } else {
943                                         /*
944                                         ** If summer time is in effect, and the
945                                         ** transition time was not specified as
946                                         ** standard time, add the summer time
947                                         ** offset to the transition time;
948                                         ** otherwise, add the standard time
949                                         ** offset to the transition time.
950                                         */
951                                         /*
952                                         ** Transitions from DST to DDST
953                                         ** will effectively disappear since
954                                         ** POSIX provides for only one DST
955                                         ** offset.
956                                         */
957                                         if (isdst && !sp->ttis[j].tt_ttisstd) {
958                                                 sp->ats[i] += dstoffset -
959                                                         theirdstoffset;
960                                         } else {
961                                                 sp->ats[i] += stdoffset -
962                                                         theirstdoffset;
963                                         }
964                                 }
965                                 theiroffset = -sp->ttis[j].tt_gmtoff;
966                                 if (sp->ttis[j].tt_isdst)
967                                         theirdstoffset = theiroffset;
968                                 else    theirstdoffset = theiroffset;
969                         }
970                         /*
971                         ** Finally, fill in ttis.
972                         ** ttisstd and ttisgmt need not be handled.
973                         */
974                         sp->ttis[0].tt_gmtoff = -stdoffset;
975                         sp->ttis[0].tt_isdst = FALSE;
976                         sp->ttis[0].tt_abbrind = 0;
977                         sp->ttis[1].tt_gmtoff = -dstoffset;
978                         sp->ttis[1].tt_isdst = TRUE;
979                         sp->ttis[1].tt_abbrind = stdlen + 1;
980                         sp->typecnt = 2;
981                 }
982         } else {
983                 dstlen = 0;
984                 sp->typecnt = 1;                /* only standard time */
985                 sp->timecnt = 0;
986                 sp->ttis[0].tt_gmtoff = -stdoffset;
987                 sp->ttis[0].tt_isdst = 0;
988                 sp->ttis[0].tt_abbrind = 0;
989         }
990         sp->charcnt = stdlen + 1;
991         if (dstlen != 0)
992                 sp->charcnt += dstlen + 1;
993         if ((size_t) sp->charcnt > sizeof sp->chars)
994                 return -1;
995         cp = sp->chars;
996         (void) strncpy(cp, stdname, stdlen);
997         cp += stdlen;
998         *cp++ = '\0';
999         if (dstlen != 0) {
1000                 (void) strncpy(cp, dstname, dstlen);
1001                 *(cp + dstlen) = '\0';
1002         }
1003         return 0;
1004 }
1005
1006 static int gmtload(struct state *sp)
1007 {
1008         if (tzload(gmt, sp, TRUE) != 0)
1009                 return tzparse(gmt, sp, TRUE);
1010         else
1011                 return -1;
1012 }
1013
1014 static const struct state *ast_tzset(const char *zone)
1015 {
1016         struct state *sp;
1017
1018         if (ast_strlen_zero(zone))
1019                 zone = "/etc/localtime";
1020
1021         AST_LIST_LOCK(&zonelist);
1022         AST_LIST_TRAVERSE(&zonelist, sp, list) {
1023                 if (!strcmp(sp->name, zone)) {
1024                         AST_LIST_UNLOCK(&zonelist);
1025                         return sp;
1026                 }
1027         }
1028         AST_LIST_UNLOCK(&zonelist);
1029
1030         if (!(sp = ast_calloc(1, sizeof *sp)))
1031                 return NULL;
1032
1033         if (tzload(zone, sp, TRUE) != 0) {
1034                 if (zone[0] == ':' || tzparse(zone, sp, FALSE) != 0)
1035                         (void) gmtload(sp);
1036         }
1037         ast_copy_string(sp->name, zone, sizeof(sp->name));
1038         AST_LIST_LOCK(&zonelist);
1039         AST_LIST_INSERT_TAIL(&zonelist, sp, list);
1040         AST_LIST_UNLOCK(&zonelist);
1041         return sp;
1042 }
1043
1044 /*! \note
1045 ** The easy way to behave "as if no library function calls" localtime
1046 ** is to not call it--so we drop its guts into "localsub", which can be
1047 ** freely called. (And no, the PANS doesn't require the above behavior--
1048 ** but it *is* desirable.)
1049 **
1050 ** The unused offset argument is for the benefit of mktime variants.
1051 */
1052
1053 static struct ast_tm *localsub(const struct timeval *timep, const long offset, struct ast_tm *tmp, const struct state *sp)
1054 {
1055         const struct ttinfo *   ttisp;
1056         int                     i;
1057         struct ast_tm *         result;
1058         struct timeval  t;
1059         memcpy(&t, timep, sizeof(t));
1060
1061         if (sp == NULL)
1062                 return gmtsub(timep, offset, tmp);
1063         if ((sp->goback && t.tv_sec < sp->ats[0]) ||
1064                 (sp->goahead && t.tv_sec > sp->ats[sp->timecnt - 1])) {
1065                         struct timeval  newt = t;
1066                         time_t          seconds;
1067                         time_t          tcycles;
1068                         int_fast64_t    icycles;
1069
1070                         if (t.tv_sec < sp->ats[0])
1071                                 seconds = sp->ats[0] - t.tv_sec;
1072                         else    seconds = t.tv_sec - sp->ats[sp->timecnt - 1];
1073                         --seconds;
1074                         tcycles = seconds / YEARSPERREPEAT / AVGSECSPERYEAR;
1075                         ++tcycles;
1076                         icycles = tcycles;
1077                         if (tcycles - icycles >= 1 || icycles - tcycles >= 1)
1078                                 return NULL;
1079                         seconds = icycles;
1080                         seconds *= YEARSPERREPEAT;
1081                         seconds *= AVGSECSPERYEAR;
1082                         if (t.tv_sec < sp->ats[0])
1083                                 newt.tv_sec += seconds;
1084                         else    newt.tv_sec -= seconds;
1085                         if (newt.tv_sec < sp->ats[0] ||
1086                                 newt.tv_sec > sp->ats[sp->timecnt - 1])
1087                                         return NULL;    /* "cannot happen" */
1088                         result = localsub(&newt, offset, tmp, sp);
1089                         if (result == tmp) {
1090                                 time_t  newy;
1091
1092                                 newy = tmp->tm_year;
1093                                 if (t.tv_sec < sp->ats[0])
1094                                         newy -= icycles * YEARSPERREPEAT;
1095                                 else
1096                                         newy += icycles * YEARSPERREPEAT;
1097                                 tmp->tm_year = newy;
1098                                 if (tmp->tm_year != newy)
1099                                         return NULL;
1100                         }
1101                         return result;
1102         }
1103         if (sp->timecnt == 0 || t.tv_sec < sp->ats[0]) {
1104                 i = 0;
1105                 while (sp->ttis[i].tt_isdst) {
1106                         if (++i >= sp->typecnt) {
1107                                 i = 0;
1108                                 break;
1109                         }
1110                 }
1111         } else {
1112                 int     lo = 1;
1113                 int     hi = sp->timecnt;
1114
1115                 while (lo < hi) {
1116                         int     mid = (lo + hi) >> 1;
1117
1118                         if (t.tv_sec < sp->ats[mid])
1119                                 hi = mid;
1120                         else
1121                                 lo = mid + 1;
1122                 }
1123                 i = (int) sp->types[lo - 1];
1124         }
1125         ttisp = &sp->ttis[i];
1126         /*
1127         ** To get (wrong) behavior that's compatible with System V Release 2.0
1128         ** you'd replace the statement below with
1129         **      t += ttisp->tt_gmtoff;
1130         **      timesub(&t, 0L, sp, tmp);
1131         */
1132         result = timesub(&t, ttisp->tt_gmtoff, sp, tmp);
1133         tmp->tm_isdst = ttisp->tt_isdst;
1134         tmp->tm_gmtoff = ttisp->tt_gmtoff;
1135 #ifdef TM_ZONE
1136         tmp->TM_ZONE = &sp->chars[ttisp->tt_abbrind];
1137 #endif /* defined TM_ZONE */
1138         tmp->tm_usec = timep->tv_usec;
1139         return result;
1140 }
1141
1142 struct ast_tm *ast_localtime(const struct timeval *timep, struct ast_tm *tmp, const char *zone)
1143 {
1144         const struct state *sp = ast_tzset(zone);
1145         memset(tmp, 0, sizeof(*tmp));
1146         return sp ? localsub(timep, 0L, tmp, sp) : NULL;
1147 }
1148
1149 /*
1150 ** gmtsub is to gmtime as localsub is to localtime.
1151 */
1152
1153 static struct ast_tm *gmtsub(const struct timeval *timep, const long offset, struct ast_tm *tmp)
1154 {
1155         struct ast_tm * result;
1156         struct state *sp;
1157
1158         AST_LIST_LOCK(&zonelist);
1159         AST_LIST_TRAVERSE(&zonelist, sp, list) {
1160                 if (!strcmp(sp->name, "UTC"))
1161                         break;
1162         }
1163
1164         if (!sp) {
1165                 if (!(sp = (struct state *) ast_calloc(1, sizeof *sp)))
1166                         return NULL;
1167                 gmtload(sp);
1168                 AST_LIST_INSERT_TAIL(&zonelist, sp, list);
1169         }
1170         AST_LIST_UNLOCK(&zonelist);
1171
1172         result = timesub(timep, offset, sp, tmp);
1173 #ifdef TM_ZONE
1174         /*
1175         ** Could get fancy here and deliver something such as
1176         ** "UTC+xxxx" or "UTC-xxxx" if offset is non-zero,
1177         ** but this is no time for a treasure hunt.
1178         */
1179         if (offset != 0)
1180                 tmp->TM_ZONE = "    ";
1181         else
1182                 tmp->TM_ZONE = sp->chars;
1183 #endif /* defined TM_ZONE */
1184         return result;
1185 }
1186
1187 /*! \brief
1188 ** Return the number of leap years through the end of the given year
1189 ** where, to make the math easy, the answer for year zero is defined as zero.
1190 */
1191
1192 static int leaps_thru_end_of(const int y)
1193 {
1194         return (y >= 0) ? (y / 4 - y / 100 + y / 400) :
1195                 -(leaps_thru_end_of(-(y + 1)) + 1);
1196 }
1197
1198 static struct ast_tm *timesub(const struct timeval *timep, const long offset, const struct state *sp, struct ast_tm *tmp)
1199 {
1200         const struct lsinfo *   lp;
1201         time_t                  tdays;
1202         int                     idays;  /* unsigned would be so 2003 */
1203         long                    rem;
1204         int                             y;
1205         const int *             ip;
1206         long                    corr;
1207         int                     hit;
1208         int                     i;
1209         long    seconds;
1210
1211
1212         corr = 0;
1213         hit = 0;
1214         i = (sp == NULL) ? 0 : sp->leapcnt;
1215         while (--i >= 0) {
1216                 lp = &sp->lsis[i];
1217                 if (timep->tv_sec >= lp->ls_trans) {
1218                         if (timep->tv_sec == lp->ls_trans) {
1219                                 hit = ((i == 0 && lp->ls_corr > 0) ||
1220                                         lp->ls_corr > sp->lsis[i - 1].ls_corr);
1221                                 if (hit)
1222                                         while (i > 0 &&
1223                                                 sp->lsis[i].ls_trans ==
1224                                                 sp->lsis[i - 1].ls_trans + 1 &&
1225                                                 sp->lsis[i].ls_corr ==
1226                                                 sp->lsis[i - 1].ls_corr + 1) {
1227                                                         ++hit;
1228                                                         --i;
1229                                         }
1230                         }
1231                         corr = lp->ls_corr;
1232                         break;
1233                 }
1234         }
1235         y = EPOCH_YEAR;
1236         tdays = timep->tv_sec / SECSPERDAY;
1237         rem = timep->tv_sec - tdays * SECSPERDAY;
1238         while (tdays < 0 || tdays >= year_lengths[isleap(y)]) {
1239                 int             newy;
1240                 time_t  tdelta;
1241                 int     idelta;
1242                 int     leapdays;
1243
1244                 tdelta = tdays / DAYSPERLYEAR;
1245                 idelta = tdelta;
1246                 if (tdelta - idelta >= 1 || idelta - tdelta >= 1)
1247                         return NULL;
1248                 if (idelta == 0)
1249                         idelta = (tdays < 0) ? -1 : 1;
1250                 newy = y;
1251                 if (increment_overflow(&newy, idelta))
1252                         return NULL;
1253                 leapdays = leaps_thru_end_of(newy - 1) -
1254                         leaps_thru_end_of(y - 1);
1255                 tdays -= ((time_t) newy - y) * DAYSPERNYEAR;
1256                 tdays -= leapdays;
1257                 y = newy;
1258         }
1259
1260         seconds = tdays * SECSPERDAY + 0.5;
1261         tdays = seconds / SECSPERDAY;
1262         rem += seconds - tdays * SECSPERDAY;
1263
1264         /*
1265         ** Given the range, we can now fearlessly cast...
1266         */
1267         idays = tdays;
1268         rem += offset - corr;
1269         while (rem < 0) {
1270                 rem += SECSPERDAY;
1271                 --idays;
1272         }
1273         while (rem >= SECSPERDAY) {
1274                 rem -= SECSPERDAY;
1275                 ++idays;
1276         }
1277         while (idays < 0) {
1278                 if (increment_overflow(&y, -1))
1279                         return NULL;
1280                 idays += year_lengths[isleap(y)];
1281         }
1282         while (idays >= year_lengths[isleap(y)]) {
1283                 idays -= year_lengths[isleap(y)];
1284                 if (increment_overflow(&y, 1))
1285                         return NULL;
1286         }
1287         tmp->tm_year = y;
1288         if (increment_overflow(&tmp->tm_year, -TM_YEAR_BASE))
1289                 return NULL;
1290         tmp->tm_yday = idays;
1291         /*
1292         ** The "extra" mods below avoid overflow problems.
1293         */
1294         tmp->tm_wday = EPOCH_WDAY +
1295                 ((y - EPOCH_YEAR) % DAYSPERWEEK) *
1296                 (DAYSPERNYEAR % DAYSPERWEEK) +
1297                 leaps_thru_end_of(y - 1) -
1298                 leaps_thru_end_of(EPOCH_YEAR - 1) +
1299                 idays;
1300         tmp->tm_wday %= DAYSPERWEEK;
1301         if (tmp->tm_wday < 0)
1302                 tmp->tm_wday += DAYSPERWEEK;
1303         tmp->tm_hour = (int) (rem / SECSPERHOUR);
1304         rem %= SECSPERHOUR;
1305         tmp->tm_min = (int) (rem / SECSPERMIN);
1306         /*
1307         ** A positive leap second requires a special
1308         ** representation. This uses "... ??:59:60" et seq.
1309         */
1310         tmp->tm_sec = (int) (rem % SECSPERMIN) + hit;
1311         ip = mon_lengths[isleap(y)];
1312         for (tmp->tm_mon = 0; idays >= ip[tmp->tm_mon]; ++(tmp->tm_mon))
1313                 idays -= ip[tmp->tm_mon];
1314         tmp->tm_mday = (int) (idays + 1);
1315         tmp->tm_isdst = 0;
1316 #ifdef TM_GMTOFF
1317         tmp->TM_GMTOFF = offset;
1318 #endif /* defined TM_GMTOFF */
1319         tmp->tm_usec = timep->tv_usec;
1320         return tmp;
1321 }
1322
1323 /*! \note
1324 ** Adapted from code provided by Robert Elz, who writes:
1325 **      The "best" way to do mktime I think is based on an idea of Bob
1326 **      Kridle's (so its said...) from a long time ago.
1327 **      It does a binary search of the time_t space. Since time_t's are
1328 **      just 32 bits, its a max of 32 iterations (even at 64 bits it
1329 **      would still be very reasonable).
1330 */
1331
1332 /*! \brief
1333 ** Simplified normalize logic courtesy Paul Eggert.
1334 */
1335
1336 static int increment_overflow(int *number, int delta)
1337 {
1338         int     number0;
1339
1340         number0 = *number;
1341         *number += delta;
1342         return (*number < number0) != (delta < 0);
1343 }
1344
1345 static int long_increment_overflow(long *number, int delta)
1346 {
1347         long    number0;
1348
1349         number0 = *number;
1350         *number += delta;
1351         return (*number < number0) != (delta < 0);
1352 }
1353
1354 static int normalize_overflow(int *tensptr, int *unitsptr, const int base)
1355 {
1356         int     tensdelta;
1357
1358         tensdelta = (*unitsptr >= 0) ?
1359                 (*unitsptr / base) :
1360                 (-1 - (-1 - *unitsptr) / base);
1361         *unitsptr -= tensdelta * base;
1362         return increment_overflow(tensptr, tensdelta);
1363 }
1364
1365 static int long_normalize_overflow(long *tensptr, int *unitsptr, const int base)
1366 {
1367         int     tensdelta;
1368
1369         tensdelta = (*unitsptr >= 0) ?
1370                 (*unitsptr / base) :
1371                 (-1 - (-1 - *unitsptr) / base);
1372         *unitsptr -= tensdelta * base;
1373         return long_increment_overflow(tensptr, tensdelta);
1374 }
1375
1376 static int tmcomp(const struct ast_tm *atmp, const struct ast_tm *btmp)
1377 {
1378         int     result;
1379
1380         if ((result = (atmp->tm_year - btmp->tm_year)) == 0 &&
1381                 (result = (atmp->tm_mon - btmp->tm_mon)) == 0 &&
1382                 (result = (atmp->tm_mday - btmp->tm_mday)) == 0 &&
1383                 (result = (atmp->tm_hour - btmp->tm_hour)) == 0 &&
1384                 (result = (atmp->tm_min - btmp->tm_min)) == 0 &&
1385                 (result = (atmp->tm_sec - btmp->tm_sec)) == 0)
1386                         result = atmp->tm_usec - btmp->tm_usec;
1387         return result;
1388 }
1389
1390 static struct timeval time2sub(struct ast_tm *tmp, struct ast_tm * (* const funcp) (const struct timeval *, long, struct ast_tm *, const struct state *), const long offset, int *okayp, const int do_norm_secs, const struct state *sp)
1391 {
1392         int                     dir;
1393         int                     i, j;
1394         int                     saved_seconds;
1395         long                    li;
1396         time_t                  lo;
1397         time_t                  hi;
1398         long                            y;
1399         struct timeval                  newt = { 0, 0 };
1400         struct timeval                  t = { 0, 0 };
1401         struct ast_tm                   yourtm, mytm;
1402
1403         *okayp = FALSE;
1404         yourtm = *tmp;
1405         if (do_norm_secs) {
1406                 if (normalize_overflow(&yourtm.tm_min, &yourtm.tm_sec,
1407                         SECSPERMIN))
1408                                 return WRONG;
1409         }
1410         if (normalize_overflow(&yourtm.tm_hour, &yourtm.tm_min, MINSPERHOUR))
1411                 return WRONG;
1412         if (normalize_overflow(&yourtm.tm_mday, &yourtm.tm_hour, HOURSPERDAY))
1413                 return WRONG;
1414         y = yourtm.tm_year;
1415         if (long_normalize_overflow(&y, &yourtm.tm_mon, MONSPERYEAR))
1416                 return WRONG;
1417         /*
1418         ** Turn y into an actual year number for now.
1419         ** It is converted back to an offset from TM_YEAR_BASE later.
1420         */
1421         if (long_increment_overflow(&y, TM_YEAR_BASE))
1422                 return WRONG;
1423         while (yourtm.tm_mday <= 0) {
1424                 if (long_increment_overflow(&y, -1))
1425                         return WRONG;
1426                 li = y + (1 < yourtm.tm_mon);
1427                 yourtm.tm_mday += year_lengths[isleap(li)];
1428         }
1429         while (yourtm.tm_mday > DAYSPERLYEAR) {
1430                 li = y + (1 < yourtm.tm_mon);
1431                 yourtm.tm_mday -= year_lengths[isleap(li)];
1432                 if (long_increment_overflow(&y, 1))
1433                         return WRONG;
1434         }
1435         for ( ; ; ) {
1436                 i = mon_lengths[isleap(y)][yourtm.tm_mon];
1437                 if (yourtm.tm_mday <= i)
1438                         break;
1439                 yourtm.tm_mday -= i;
1440                 if (++yourtm.tm_mon >= MONSPERYEAR) {
1441                         yourtm.tm_mon = 0;
1442                         if (long_increment_overflow(&y, 1))
1443                                 return WRONG;
1444                 }
1445         }
1446         if (long_increment_overflow(&y, -TM_YEAR_BASE))
1447                 return WRONG;
1448         yourtm.tm_year = y;
1449         if (yourtm.tm_year != y)
1450                 return WRONG;
1451         if (yourtm.tm_sec >= 0 && yourtm.tm_sec < SECSPERMIN)
1452                 saved_seconds = 0;
1453         else if (y + TM_YEAR_BASE < EPOCH_YEAR) {
1454                 /*
1455                 ** We can't set tm_sec to 0, because that might push the
1456                 ** time below the minimum representable time.
1457                 ** Set tm_sec to 59 instead.
1458                 ** This assumes that the minimum representable time is
1459                 ** not in the same minute that a leap second was deleted from,
1460                 ** which is a safer assumption than using 58 would be.
1461                 */
1462                 if (increment_overflow(&yourtm.tm_sec, 1 - SECSPERMIN))
1463                         return WRONG;
1464                 saved_seconds = yourtm.tm_sec;
1465                 yourtm.tm_sec = SECSPERMIN - 1;
1466         } else {
1467                 saved_seconds = yourtm.tm_sec;
1468                 yourtm.tm_sec = 0;
1469         }
1470         /*
1471         ** Do a binary search (this works whatever time_t's type is).
1472         */
1473         if (!TYPE_SIGNED(time_t)) {
1474                 lo = 0;
1475                 hi = lo - 1;
1476         } else if (!TYPE_INTEGRAL(time_t)) {
1477                 if (sizeof(time_t) > sizeof(float))
1478                         hi = (time_t) DBL_MAX;
1479                 else    hi = (time_t) FLT_MAX;
1480                 lo = -hi;
1481         } else {
1482                 lo = 1;
1483                 for (i = 0; i < (int) TYPE_BIT(time_t) - 1; ++i)
1484                         lo *= 2;
1485                 hi = -(lo + 1);
1486         }
1487         for ( ; ; ) {
1488                 t.tv_sec = lo / 2 + hi / 2;
1489                 if (t.tv_sec < lo)
1490                         t.tv_sec = lo;
1491                 else if (t.tv_sec > hi)
1492                         t.tv_sec = hi;
1493                 if ((*funcp)(&t, offset, &mytm, sp) == NULL) {
1494                         /*
1495                         ** Assume that t is too extreme to be represented in
1496                         ** a struct ast_tm; arrange things so that it is less
1497                         ** extreme on the next pass.
1498                         */
1499                         dir = (t.tv_sec > 0) ? 1 : -1;
1500                 } else  dir = tmcomp(&mytm, &yourtm);
1501                 if (dir != 0) {
1502                         if (t.tv_sec == lo) {
1503                                 ++t.tv_sec;
1504                                 if (t.tv_sec <= lo)
1505                                         return WRONG;
1506                                 ++lo;
1507                         } else if (t.tv_sec == hi) {
1508                                 --t.tv_sec;
1509                                 if (t.tv_sec >= hi)
1510                                         return WRONG;
1511                                 --hi;
1512                         }
1513                         if (lo > hi)
1514                                 return WRONG;
1515                         if (dir > 0)
1516                                 hi = t.tv_sec;
1517                         else    lo = t.tv_sec;
1518                         continue;
1519                 }
1520                 if (yourtm.tm_isdst < 0 || mytm.tm_isdst == yourtm.tm_isdst)
1521                         break;
1522                 /*
1523                 ** Right time, wrong type.
1524                 ** Hunt for right time, right type.
1525                 ** It's okay to guess wrong since the guess
1526                 ** gets checked.
1527                 */
1528                 /*
1529                 ** The (void *) casts are the benefit of SunOS 3.3 on Sun 2's.
1530                 */
1531                 for (i = sp->typecnt - 1; i >= 0; --i) {
1532                         if (sp->ttis[i].tt_isdst != yourtm.tm_isdst)
1533                                 continue;
1534                         for (j = sp->typecnt - 1; j >= 0; --j) {
1535                                 if (sp->ttis[j].tt_isdst == yourtm.tm_isdst)
1536                                         continue;
1537                                 newt.tv_sec = t.tv_sec + sp->ttis[j].tt_gmtoff -
1538                                         sp->ttis[i].tt_gmtoff;
1539                                 if ((*funcp)(&newt, offset, &mytm, sp) == NULL)
1540                                         continue;
1541                                 if (tmcomp(&mytm, &yourtm) != 0)
1542                                         continue;
1543                                 if (mytm.tm_isdst != yourtm.tm_isdst)
1544                                         continue;
1545                                 /*
1546                                 ** We have a match.
1547                                 */
1548                                 t = newt;
1549                                 goto label;
1550                         }
1551                 }
1552                 return WRONG;
1553         }
1554 label:
1555         newt.tv_sec = t.tv_sec + saved_seconds;
1556         if ((newt.tv_sec < t.tv_sec) != (saved_seconds < 0))
1557                 return WRONG;
1558         t.tv_sec = newt.tv_sec;
1559         if ((*funcp)(&t, offset, tmp, sp))
1560                 *okayp = TRUE;
1561         return t;
1562 }
1563
1564 static struct timeval time2(struct ast_tm *tmp, struct ast_tm * (* const funcp) (const struct timeval *, long, struct ast_tm*, const struct state *sp), const long offset, int *okayp, const struct state *sp)
1565 {
1566         struct timeval  t;
1567
1568         /*! \note
1569         ** First try without normalization of seconds
1570         ** (in case tm_sec contains a value associated with a leap second).
1571         ** If that fails, try with normalization of seconds.
1572         */
1573         t = time2sub(tmp, funcp, offset, okayp, FALSE, sp);
1574         return *okayp ? t : time2sub(tmp, funcp, offset, okayp, TRUE, sp);
1575 }
1576
1577 static struct timeval time1(struct ast_tm *tmp, struct ast_tm * (* const funcp) (const struct timeval *, long, struct ast_tm *, const struct state *), const long offset, const struct state *sp)
1578 {
1579         struct timeval                  t;
1580         int                     samei, otheri;
1581         int                     sameind, otherind;
1582         int                     i;
1583         int                     nseen;
1584         int                             seen[TZ_MAX_TYPES];
1585         int                             types[TZ_MAX_TYPES];
1586         int                             okay;
1587
1588         if (tmp->tm_isdst > 1)
1589                 tmp->tm_isdst = 1;
1590         t = time2(tmp, funcp, offset, &okay, sp);
1591 #ifdef PCTS
1592         /*
1593         ** PCTS code courtesy Grant Sullivan.
1594         */
1595         if (okay)
1596                 return t;
1597         if (tmp->tm_isdst < 0)
1598                 tmp->tm_isdst = 0;      /* reset to std and try again */
1599 #endif /* defined PCTS */
1600 #ifndef PCTS
1601         if (okay || tmp->tm_isdst < 0)
1602                 return t;
1603 #endif /* !defined PCTS */
1604         /*
1605         ** We're supposed to assume that somebody took a time of one type
1606         ** and did some math on it that yielded a "struct ast_tm" that's bad.
1607         ** We try to divine the type they started from and adjust to the
1608         ** type they need.
1609         */
1610         if (sp == NULL)
1611                 return WRONG;
1612         for (i = 0; i < sp->typecnt; ++i)
1613                 seen[i] = FALSE;
1614         nseen = 0;
1615         for (i = sp->timecnt - 1; i >= 0; --i)
1616                 if (!seen[sp->types[i]]) {
1617                         seen[sp->types[i]] = TRUE;
1618                         types[nseen++] = sp->types[i];
1619                 }
1620         for (sameind = 0; sameind < nseen; ++sameind) {
1621                 samei = types[sameind];
1622                 if (sp->ttis[samei].tt_isdst != tmp->tm_isdst)
1623                         continue;
1624                 for (otherind = 0; otherind < nseen; ++otherind) {
1625                         otheri = types[otherind];
1626                         if (sp->ttis[otheri].tt_isdst == tmp->tm_isdst)
1627                                 continue;
1628                         tmp->tm_sec += sp->ttis[otheri].tt_gmtoff -
1629                                         sp->ttis[samei].tt_gmtoff;
1630                         tmp->tm_isdst = !tmp->tm_isdst;
1631                         t = time2(tmp, funcp, offset, &okay, sp);
1632                         if (okay)
1633                                 return t;
1634                         tmp->tm_sec -= sp->ttis[otheri].tt_gmtoff -
1635                                         sp->ttis[samei].tt_gmtoff;
1636                         tmp->tm_isdst = !tmp->tm_isdst;
1637                 }
1638         }
1639         return WRONG;
1640 }
1641
1642 struct timeval ast_mktime(struct ast_tm *tmp, const char *zone)
1643 {
1644         const struct state *sp;
1645         if (!(sp = ast_tzset(zone)))
1646                 return WRONG;
1647         return time1(tmp, localsub, 0L, sp);
1648 }
1649
1650 int ast_strftime(char *buf, size_t len, const char *tmp, const struct ast_tm *tm)
1651 {
1652         size_t fmtlen = strlen(tmp) + 1;
1653         char *format = ast_calloc(1, fmtlen), *fptr = format, *newfmt;
1654         int decimals = -1, i, res;
1655         long fraction;
1656
1657         if (!format)
1658                 return -1;
1659         for (; *tmp; tmp++) {
1660                 if (*tmp == '%') {
1661                         switch (tmp[1]) {
1662                         case '1':
1663                         case '2':
1664                         case '3':
1665                         case '4':
1666                         case '5':
1667                         case '6':
1668                                 if (tmp[2] != 'q')
1669                                         goto defcase;
1670                                 decimals = tmp[1] - '0';
1671                                 tmp++;
1672                                 /* Fall through */
1673                         case 'q': /* Milliseconds */
1674                                 if (decimals == -1)
1675                                         decimals = 3;
1676
1677                                 /* Juggle some memory to fit the item */
1678                                 newfmt = ast_realloc(format, fmtlen + decimals);
1679                                 if (!newfmt) {
1680                                         ast_free(format);
1681                                         return -1;
1682                                 }
1683                                 fptr = fptr - format + newfmt;
1684                                 format = newfmt;
1685                                 fmtlen += decimals;
1686
1687                                 /* Reduce the fraction of time to the accuracy needed */
1688                                 for (i = 6, fraction = tm->tm_usec; i > decimals; i--)
1689                                         fraction /= 10;
1690                                 fptr += sprintf(fptr, "%0*ld", decimals, fraction);
1691
1692                                 /* Reset, in case more than one 'q' specifier exists */
1693                                 decimals = -1;
1694                                 tmp++;
1695                                 break;
1696                         default:
1697                                 goto defcase;
1698                         }
1699                 } else
1700 defcase:        *fptr++ = *tmp;
1701         }
1702         *fptr = '\0';
1703 #undef strftime
1704         res = (int)strftime(buf, len, format, (struct tm *)tm);
1705         ast_free(format);
1706         return res;
1707 }
1708