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