time/tzfile.c

   1 /* Copyright (C) 1991-2013 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, see
  16    <http://www.gnu.org/licenses/>.  */
  17
  18 #include <assert.h>
  19 #include <limits.h>
  20 #include <stdio.h>
  21 #include <stdio_ext.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <time.h>
  25 #include <unistd.h>
  26 #include <sys/stat.h>
  27
  28 #define NOID
  29 #include <timezone/tzfile.h>
  30
  31 int __use_tzfile;
  32 static dev_t tzfile_dev;
  33 static ino64_t tzfile_ino;
  34 static time_t tzfile_mtime;
  35
  36 struct ttinfo
  37   {
  38     long int offset;            /* Seconds east of GMT.  */
  39     unsigned char isdst;        /* Used to set tm_isdst.  */
  40     unsigned char idx;          /* Index into `zone_names'.  */
  41     unsigned char isstd;        /* Transition times are in standard time.  */
  42     unsigned char isgmt;        /* Transition times are in GMT.  */
  43   };
  44
  45 struct leap
  46   {
  47     time_t transition;          /* Time the transition takes effect.  */
  48     long int change;            /* Seconds of correction to apply.  */
  49   };
  50
  51 static void compute_tzname_max (size_t) internal_function;
  52
  53 static size_t num_transitions;
  54 libc_freeres_ptr (static time_t *transitions);
  55 static unsigned char *type_idxs;
  56 static size_t num_types;
  57 static struct ttinfo *types;
  58 static char *zone_names;
  59 static long int rule_stdoff;
  60 static long int rule_dstoff;
  61 static size_t num_leaps;
  62 static struct leap *leaps;
  63 static char *tzspec;
  64
  65 #include <endian.h>
  66 #include <byteswap.h>
  67
  68 /* Decode the four bytes at PTR as a signed integer in network byte order.  */
  69 static inline int
  70 __attribute ((always_inline))
  71 decode (const void *ptr)
  72 {
  73   if (BYTE_ORDER == BIG_ENDIAN && sizeof (int) == 4)
  74     return *(const int *) ptr;
  75   if (sizeof (int) == 4)
  76     return bswap_32 (*(const int *) ptr);
  77
  78   const unsigned char *p = ptr;
  79   int result = *p & (1 << (CHAR_BIT - 1)) ? ~0 : 0;
  80
  81   result = (result << 8) | *p++;
  82   result = (result << 8) | *p++;
  83   result = (result << 8) | *p++;
  84   result = (result << 8) | *p++;
  85
  86   return result;
  87 }
  88
  89
  90 static inline int64_t
  91 __attribute ((always_inline))
  92 decode64 (const void *ptr)
  93 {
  94   if ((BYTE_ORDER == BIG_ENDIAN))
  95     return *(const int64_t *) ptr;
  96
  97   return bswap_64 (*(const int64_t *) ptr);
  98 }
  99
 100
 101 void
 102 __tzfile_read (const char *file, size_t extra, char **extrap)
 103 {
 104   static const char default_tzdir[] = TZDIR;
 105   size_t num_isstd, num_isgmt;
 106   register FILE *f;
 107   struct tzhead tzhead;
 108   size_t chars;
 109   register size_t i;
 110   size_t total_size;
 111   size_t types_idx;
 112   size_t leaps_idx;
 113   int was_using_tzfile = __use_tzfile;
 114   int trans_width = 4;
 115   size_t tzspec_len;
 116
 117   if (sizeof (time_t) != 4 && sizeof (time_t) != 8)
 118     abort ();
 119
 120   __use_tzfile = 0;
 121
 122   if (file == NULL)
 123     /* No user specification; use the site-wide default.  */
 124     file = TZDEFAULT;
 125   else if (*file == '\0')
 126     /* User specified the empty string; use UTC with no leap seconds.  */
 127     goto ret_free_transitions;
 128   else
 129     {
 130       /* We must not allow to read an arbitrary file in a setuid
 131          program.  So we fail for any file which is not in the
 132          directory hierachy starting at TZDIR
 133          and which is not the system wide default TZDEFAULT.  */
 134       if (__libc_enable_secure
 135           && ((*file == '/'
 136                && memcmp (file, TZDEFAULT, sizeof TZDEFAULT)
 137                && memcmp (file, default_tzdir, sizeof (default_tzdir) - 1))
 138               || strstr (file, "../") != NULL))
 139         /* This test is certainly a bit too restrictive but it should
 140            catch all critical cases.  */
 141         goto ret_free_transitions;
 142     }
 143
 144   if (*file != '/')
 145     {
 146       const char *tzdir;
 147       unsigned int len, tzdir_len;
 148       char *new, *tmp;
 149
 150       tzdir = getenv ("TZDIR");
 151       if (tzdir == NULL || *tzdir == '\0')
 152         {
 153           tzdir = default_tzdir;
 154           tzdir_len = sizeof (default_tzdir) - 1;
 155         }
 156       else
 157         tzdir_len = strlen (tzdir);
 158       len = strlen (file) + 1;
 159       new = (char *) __alloca (tzdir_len + 1 + len);
 160       tmp = __mempcpy (new, tzdir, tzdir_len);
 161       *tmp++ = '/';
 162       memcpy (tmp, file, len);
 163       file = new;
 164     }
 165
 166   /* If we were already using tzfile, check whether the file changed.  */
 167   struct stat64 st;
 168   if (was_using_tzfile
 169       && stat64 (file, &st) == 0
 170       && tzfile_ino == st.st_ino && tzfile_dev == st.st_dev
 171       && tzfile_mtime == st.st_mtime)
 172     {
 173       /* Nothing to do.  */
 174       __use_tzfile = 1;
 175       return;
 176     }
 177
 178   /* Note the file is opened with cancellation in the I/O functions
 179      disabled and if available FD_CLOEXEC set.  */
 180   f = fopen (file, "rce");
 181   if (f == NULL)
 182     goto ret_free_transitions;
 183
 184   /* Get information about the file we are actually using.  */
 185   if (fstat64 (fileno (f), &st) != 0)
 186     {
 187       fclose (f);
 188       goto ret_free_transitions;
 189     }
 190
 191   free ((void *) transitions);
 192   transitions = NULL;
 193
 194   /* Remember the inode and device number and modification time.  */
 195   tzfile_dev = st.st_dev;
 196   tzfile_ino = st.st_ino;
 197   tzfile_mtime = st.st_mtime;
 198
 199   /* No threads reading this stream.  */
 200   __fsetlocking (f, FSETLOCKING_BYCALLER);
 201
 202  read_again:
 203   if (__builtin_expect (fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 204                                         1, f) != 1, 0)
 205       || memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic)) != 0)
 206     goto lose;
 207
 208   num_transitions = (size_t) decode (tzhead.tzh_timecnt);
 209   num_types = (size_t) decode (tzhead.tzh_typecnt);
 210   chars = (size_t) decode (tzhead.tzh_charcnt);
 211   num_leaps = (size_t) decode (tzhead.tzh_leapcnt);
 212   num_isstd = (size_t) decode (tzhead.tzh_ttisstdcnt);
 213   num_isgmt = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 214
 215   /* For platforms with 64-bit time_t we use the new format if available.  */
 216   if (sizeof (time_t) == 8 && trans_width == 4
 217       && tzhead.tzh_version[0] != '\0')
 218     {
 219       /* We use the 8-byte format.  */
 220       trans_width = 8;
 221
 222       /* Position the stream before the second header.  */
 223       size_t to_skip = (num_transitions * (4 + 1)
 224                         + num_types * 6
 225                         + chars
 226                         + num_leaps * 8
 227                         + num_isstd
 228                         + num_isgmt);
 229       if (fseek (f, to_skip, SEEK_CUR) != 0)
 230         goto lose;
 231
 232       goto read_again;
 233     }
 234
 235   if (__builtin_expect (num_transitions
 236                         > ((SIZE_MAX - (__alignof__ (struct ttinfo) - 1))
 237                            / (sizeof (time_t) + 1)), 0))
 238     goto lose;
 239   total_size = num_transitions * (sizeof (time_t) + 1);
 240   total_size = ((total_size + __alignof__ (struct ttinfo) - 1)
 241                 & ~(__alignof__ (struct ttinfo) - 1));
 242   types_idx = total_size;
 243   if (__builtin_expect (num_types
 244                         > (SIZE_MAX - total_size) / sizeof (struct ttinfo), 0))
 245     goto lose;
 246   total_size += num_types * sizeof (struct ttinfo);
 247   if (__builtin_expect (chars > SIZE_MAX - total_size, 0))
 248     goto lose;
 249   total_size += chars;
 250   if (__builtin_expect (__alignof__ (struct leap) - 1
 251                         > SIZE_MAX - total_size, 0))
 252     goto lose;
 253   total_size = ((total_size + __alignof__ (struct leap) - 1)
 254                 & ~(__alignof__ (struct leap) - 1));
 255   leaps_idx = total_size;
 256   if (__builtin_expect (num_leaps
 257                         > (SIZE_MAX - total_size) / sizeof (struct leap), 0))
 258     goto lose;
 259   total_size += num_leaps * sizeof (struct leap);
 260   tzspec_len = 0;
 261   if (sizeof (time_t) == 8 && trans_width == 8)
 262     {
 263       off_t rem = st.st_size - ftello (f);
 264       if (__builtin_expect (rem < 0
 265                             || (size_t) rem < (num_transitions * (8 + 1)
 266                                                + num_types * 6
 267                                                + chars), 0))
 268         goto lose;
 269       tzspec_len = (size_t) rem - (num_transitions * (8 + 1)
 270                                    + num_types * 6
 271                                    + chars);
 272       if (__builtin_expect (num_leaps > SIZE_MAX / 12
 273                             || tzspec_len < num_leaps * 12, 0))
 274         goto lose;
 275       tzspec_len -= num_leaps * 12;
 276       if (__builtin_expect (tzspec_len < num_isstd, 0))
 277         goto lose;
 278       tzspec_len -= num_isstd;
 279       if (__builtin_expect (tzspec_len == 0 || tzspec_len - 1 < num_isgmt, 0))
 280         goto lose;
 281       tzspec_len -= num_isgmt + 1;
 282       if (__builtin_expect (SIZE_MAX - total_size < tzspec_len, 0))
 283         goto lose;
 284     }
 285   if (__builtin_expect (SIZE_MAX - total_size - tzspec_len < extra, 0))
 286     goto lose;
 287
 288   /* Allocate enough memory including the extra block requested by the
 289      caller.  */
 290   transitions = (time_t *) malloc (total_size + tzspec_len + extra);
 291   if (transitions == NULL)
 292     goto lose;
 293
 294   type_idxs = (unsigned char *) transitions + (num_transitions
 295                                                * sizeof (time_t));
 296   types = (struct ttinfo *) ((char *) transitions + types_idx);
 297   zone_names = (char *) types + num_types * sizeof (struct ttinfo);
 298   leaps = (struct leap *) ((char *) transitions + leaps_idx);
 299   if (sizeof (time_t) == 8 && trans_width == 8)
 300     tzspec = (char *) leaps + num_leaps * sizeof (struct leap) + extra;
 301   else
 302     tzspec = NULL;
 303   if (extra > 0)
 304     *extrap = (char *) &leaps[num_leaps];
 305
 306   if (sizeof (time_t) == 4 || __builtin_expect (trans_width == 8, 1))
 307     {
 308       if (__builtin_expect (fread_unlocked (transitions, trans_width + 1,
 309                                             num_transitions, f)
 310                             != num_transitions, 0))
 311         goto lose;
 312     }
 313   else
 314     {
 315       if (__builtin_expect (fread_unlocked (transitions, 4, num_transitions, f)
 316                             != num_transitions, 0)
 317           || __builtin_expect (fread_unlocked (type_idxs, 1, num_transitions,
 318                                                f) != num_transitions, 0))
 319         goto lose;
 320     }
 321
 322   /* Check for bogus indices in the data file, so we can hereafter
 323      safely use type_idxs[T] as indices into `types' and never crash.  */
 324   for (i = 0; i < num_transitions; ++i)
 325     if (__builtin_expect (type_idxs[i] >= num_types, 0))
 326       goto lose;
 327
 328   if ((BYTE_ORDER != BIG_ENDIAN && (sizeof (time_t) == 4 || trans_width == 4))
 329       || (BYTE_ORDER == BIG_ENDIAN && sizeof (time_t) == 8
 330           && trans_width == 4))
 331     {
 332       /* Decode the transition times, stored as 4-byte integers in
 333          network (big-endian) byte order.  We work from the end of
 334          the array so as not to clobber the next element to be
 335          processed when sizeof (time_t) > 4.  */
 336       i = num_transitions;
 337       while (i-- > 0)
 338         transitions[i] = decode ((char *) transitions + i * 4);
 339     }
 340   else if (BYTE_ORDER != BIG_ENDIAN && sizeof (time_t) == 8)
 341     {
 342       /* Decode the transition times, stored as 8-byte integers in
 343          network (big-endian) byte order.  */
 344       for (i = 0; i < num_transitions; ++i)
 345         transitions[i] = decode64 ((char *) transitions + i * 8);
 346     }
 347
 348   for (i = 0; i < num_types; ++i)
 349     {
 350       unsigned char x[4];
 351       int c;
 352       if (__builtin_expect (fread_unlocked (x, 1, sizeof (x), f) != sizeof (x),
 353                             0))
 354         goto lose;
 355       c = getc_unlocked (f);
 356       if (__builtin_expect ((unsigned int) c > 1u, 0))
 357         goto lose;
 358       types[i].isdst = c;
 359       c = getc_unlocked (f);
 360       if (__builtin_expect ((size_t) c > chars, 0))
 361         /* Bogus index in data file.  */
 362         goto lose;
 363       types[i].idx = c;
 364       types[i].offset = (long int) decode (x);
 365     }
 366
 367   if (__builtin_expect (fread_unlocked (zone_names, 1, chars, f) != chars, 0))
 368     goto lose;
 369
 370   for (i = 0; i < num_leaps; ++i)
 371     {
 372       unsigned char x[8];
 373       if (__builtin_expect (fread_unlocked (x, 1, trans_width, f)
 374                             != trans_width, 0))
 375         goto lose;
 376       if (sizeof (time_t) == 4 || trans_width == 4)
 377         leaps[i].transition = (time_t) decode (x);
 378       else
 379         leaps[i].transition = (time_t) decode64 (x);
 380
 381       if (__builtin_expect (fread_unlocked (x, 1, 4, f) != 4, 0))
 382         goto lose;
 383       leaps[i].change = (long int) decode (x);
 384     }
 385
 386   for (i = 0; i < num_isstd; ++i)
 387     {
 388       int c = getc_unlocked (f);
 389       if (__builtin_expect (c == EOF, 0))
 390         goto lose;
 391       types[i].isstd = c != 0;
 392     }
 393   while (i < num_types)
 394     types[i++].isstd = 0;
 395
 396   for (i = 0; i < num_isgmt; ++i)
 397     {
 398       int c = getc_unlocked (f);
 399       if (__builtin_expect (c == EOF, 0))
 400         goto lose;
 401       types[i].isgmt = c != 0;
 402     }
 403   while (i < num_types)
 404     types[i++].isgmt = 0;
 405
 406   /* Read the POSIX TZ-style information if possible.  */
 407   if (sizeof (time_t) == 8 && tzspec != NULL)
 408     {
 409       /* Skip over the newline first.  */
 410       if (getc_unlocked (f) != '\n'
 411           || (fread_unlocked (tzspec, 1, tzspec_len - 1, f)
 412               != tzspec_len - 1))
 413         tzspec = NULL;
 414       else
 415         tzspec[tzspec_len - 1] = '\0';
 416     }
 417   else if (sizeof (time_t) == 4 && tzhead.tzh_version[0] != '\0')
 418     {
 419       /* Get the TZ string.  */
 420       if (__builtin_expect (fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 421                                             1, f) != 1, 0)
 422           || (memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic))
 423               != 0))
 424         goto lose;
 425
 426       size_t num_transitions2 = (size_t) decode (tzhead.tzh_timecnt);
 427       size_t num_types2 = (size_t) decode (tzhead.tzh_typecnt);
 428       size_t chars2 = (size_t) decode (tzhead.tzh_charcnt);
 429       size_t num_leaps2 = (size_t) decode (tzhead.tzh_leapcnt);
 430       size_t num_isstd2 = (size_t) decode (tzhead.tzh_ttisstdcnt);
 431       size_t num_isgmt2 = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 432
 433       /* Position the stream before the second header.  */
 434       size_t to_skip = (num_transitions2 * (8 + 1)
 435                         + num_types2 * 6
 436                         + chars2
 437                         + num_leaps2 * 12
 438                         + num_isstd2
 439                         + num_isgmt2);
 440       off_t off;
 441       if (fseek (f, to_skip, SEEK_CUR) != 0
 442           || (off = ftello (f)) < 0
 443           || st.st_size < off + 2)
 444         goto lose;
 445
 446       tzspec_len = st.st_size - off - 1;
 447       char *tzstr = alloca (tzspec_len);
 448       if (getc_unlocked (f) != '\n'
 449           || (fread_unlocked (tzstr, 1, tzspec_len - 1, f) != tzspec_len - 1))
 450         goto lose;
 451       tzstr[tzspec_len - 1] = '\0';
 452       tzspec = __tzstring (tzstr);
 453     }
 454
 455   /* Don't use an empty TZ string.  */
 456   if (tzspec != NULL && tzspec[0] == '\0')
 457     tzspec = NULL;
 458
 459   fclose (f);
 460
 461   /* First "register" all timezone names.  */
 462   for (i = 0; i < num_types; ++i)
 463     (void) __tzstring (&zone_names[types[i].idx]);
 464
 465   /* Find the standard and daylight time offsets used by the rule file.
 466      We choose the offsets in the types of each flavor that are
 467      transitioned to earliest in time.  */
 468   __tzname[0] = NULL;
 469   __tzname[1] = NULL;
 470   for (i = num_transitions; i > 0; )
 471     {
 472       int type = type_idxs[--i];
 473       int dst = types[type].isdst;
 474
 475       if (__tzname[dst] == NULL)
 476         {
 477           int idx = types[type].idx;
 478
 479           __tzname[dst] = __tzstring (&zone_names[idx]);
 480
 481           if (__tzname[1 - dst] != NULL)
 482             break;
 483         }
 484     }
 485   if (__tzname[0] == NULL)
 486     {
 487       /* This should only happen if there are no transition rules.
 488          In this case there should be only one single type.  */
 489       assert (num_types == 1);
 490       __tzname[0] = __tzstring (zone_names);
 491     }
 492   if (__tzname[1] == NULL)
 493     __tzname[1] = __tzname[0];
 494
 495   compute_tzname_max (chars);
 496
 497   if (num_transitions == 0)
 498     /* Use the first rule (which should also be the only one).  */
 499     rule_stdoff = rule_dstoff = types[0].offset;
 500   else
 501     {
 502       int stdoff_set = 0, dstoff_set = 0;
 503       rule_stdoff = rule_dstoff = 0;
 504       i = num_transitions - 1;
 505       do
 506         {
 507           if (!stdoff_set && !types[type_idxs[i]].isdst)
 508             {
 509               stdoff_set = 1;
 510               rule_stdoff = types[type_idxs[i]].offset;
 511             }
 512           else if (!dstoff_set && types[type_idxs[i]].isdst)
 513             {
 514               dstoff_set = 1;
 515               rule_dstoff = types[type_idxs[i]].offset;
 516             }
 517           if (stdoff_set && dstoff_set)
 518             break;
 519         }
 520       while (i-- > 0);
 521
 522       if (!dstoff_set)
 523         rule_dstoff = rule_stdoff;
 524     }
 525
 526   __daylight = rule_stdoff != rule_dstoff;
 527   __timezone = -rule_stdoff;
 528
 529   __use_tzfile = 1;
 530   return;
 531
 532  lose:
 533   fclose (f);
 534  ret_free_transitions:
 535   free ((void *) transitions);
 536   transitions = NULL;
 537 }
 538 \f
 539 /* The user specified a hand-made timezone, but not its DST rules.
 540    We will use the names and offsets from the user, and the rules
 541    from the TZDEFRULES file.  */
 542
 543 void
 544 __tzfile_default (const char *std, const char *dst,
 545                   long int stdoff, long int dstoff)
 546 {
 547   size_t stdlen = strlen (std) + 1;
 548   size_t dstlen = strlen (dst) + 1;
 549   size_t i;
 550   int isdst;
 551   char *cp;
 552
 553   __tzfile_read (TZDEFRULES, stdlen + dstlen, &cp);
 554   if (!__use_tzfile)
 555     return;
 556
 557   if (num_types < 2)
 558     {
 559       __use_tzfile = 0;
 560       return;
 561     }
 562
 563   /* Ignore the zone names read from the file and use the given ones
 564      instead.  */
 565   __mempcpy (__mempcpy (cp, std, stdlen), dst, dstlen);
 566   zone_names = cp;
 567
 568   /* Now there are only two zones, regardless of what the file contained.  */
 569   num_types = 2;
 570
 571   /* Now correct the transition times for the user-specified standard and
 572      daylight offsets from GMT.  */
 573   isdst = 0;
 574   for (i = 0; i < num_transitions; ++i)
 575     {
 576       struct ttinfo *trans_type = &types[type_idxs[i]];
 577
 578       /* We will use only types 0 (standard) and 1 (daylight).
 579          Fix up this transition to point to whichever matches
 580          the flavor of its original type.  */
 581       type_idxs[i] = trans_type->isdst;
 582
 583       if (trans_type->isgmt)
 584         /* The transition time is in GMT.  No correction to apply.  */ ;
 585       else if (isdst && !trans_type->isstd)
 586         /* The type says this transition is in "local wall clock time", and
 587            wall clock time as of the previous transition was DST.  Correct
 588            for the difference between the rule's DST offset and the user's
 589            DST offset.  */
 590         transitions[i] += dstoff - rule_dstoff;
 591       else
 592         /* This transition is in "local wall clock time", and wall clock
 593            time as of this iteration is non-DST.  Correct for the
 594            difference between the rule's standard offset and the user's
 595            standard offset.  */
 596         transitions[i] += stdoff - rule_stdoff;
 597
 598       /* The DST state of "local wall clock time" for the next iteration is
 599          as specified by this transition.  */
 600       isdst = trans_type->isdst;
 601     }
 602
 603   /* Now that we adjusted the transitions to the requested offsets,
 604      reset the rule_stdoff and rule_dstoff values appropriately.  They
 605      are used elsewhere.  */
 606   rule_stdoff = stdoff;
 607   rule_dstoff = dstoff;
 608
 609   /* Reset types 0 and 1 to describe the user's settings.  */
 610   types[0].idx = 0;
 611   types[0].offset = stdoff;
 612   types[0].isdst = 0;
 613   types[1].idx = stdlen;
 614   types[1].offset = dstoff;
 615   types[1].isdst = 1;
 616
 617   /* Reset the zone names to point to the user's names.  */
 618   __tzname[0] = (char *) std;
 619   __tzname[1] = (char *) dst;
 620
 621   /* Set the timezone.  */
 622   __timezone = -types[0].offset;
 623
 624   compute_tzname_max (stdlen + dstlen);
 625 }
 626 \f
 627 void
 628 __tzfile_compute (time_t timer, int use_localtime,
 629                   long int *leap_correct, int *leap_hit,
 630                   struct tm *tp)
 631 {
 632   register size_t i;
 633
 634   if (use_localtime)
 635     {
 636       __tzname[0] = NULL;
 637       __tzname[1] = NULL;
 638
 639       if (__builtin_expect (num_transitions == 0 || timer < transitions[0], 0))
 640         {
 641           /* TIMER is before any transition (or there are no transitions).
 642              Choose the first non-DST type
 643              (or the first if they're all DST types).  */
 644           i = 0;
 645           while (i < num_types && types[i].isdst)
 646             {
 647               if (__tzname[1] == NULL)
 648                 __tzname[1] = __tzstring (&zone_names[types[i].idx]);
 649
 650               ++i;
 651             }
 652
 653           if (i == num_types)
 654             i = 0;
 655           __tzname[0] = __tzstring (&zone_names[types[i].idx]);
 656           if (__tzname[1] == NULL)
 657             {
 658               size_t j = i;
 659               while (j < num_types)
 660                 if (types[j].isdst)
 661                   {
 662                     __tzname[1] = __tzstring (&zone_names[types[j].idx]);
 663                     break;
 664                   }
 665                 else
 666                   ++j;
 667             }
 668         }
 669       else if (__builtin_expect (timer >= transitions[num_transitions - 1], 0))
 670         {
 671           if (__builtin_expect (tzspec == NULL, 0))
 672             {
 673             use_last:
 674               i = num_transitions;
 675               goto found;
 676             }
 677
 678           /* Parse the POSIX TZ-style string.  */
 679           __tzset_parse_tz (tzspec);
 680
 681           /* Convert to broken down structure.  If this fails do not
 682              use the string.  */
 683           if (__builtin_expect (! __offtime (&timer, 0, tp), 0))
 684             goto use_last;
 685
 686           /* Use the rules from the TZ string to compute the change.  */
 687           __tz_compute (timer, tp, 1);
 688
 689           /* If tzspec comes from posixrules loaded by __tzfile_default,
 690              override the STD and DST zone names with the ones user
 691              requested in TZ envvar.  */
 692           if (__builtin_expect (zone_names == (char *) &leaps[num_leaps], 0))
 693             {
 694               assert (num_types == 2);
 695               __tzname[0] = __tzstring (zone_names);
 696               __tzname[1] = __tzstring (&zone_names[strlen (zone_names) + 1]);
 697             }
 698
 699           goto leap;
 700         }
 701       else
 702         {
 703           /* Find the first transition after TIMER, and
 704              then pick the type of the transition before it.  */
 705           size_t lo = 0;
 706           size_t hi = num_transitions - 1;
 707           /* Assume that DST is changing twice a year and guess initial
 708              search spot from it.
 709              Half of a gregorian year has on average 365.2425 * 86400 / 2
 710              = 15778476 seconds.  */
 711           i = (transitions[num_transitions - 1] - timer) / 15778476;
 712           if (i < num_transitions)
 713             {
 714               i = num_transitions - 1 - i;
 715               if (timer < transitions[i])
 716                 {
 717                   if (i < 10 || timer >= transitions[i - 10])
 718                     {
 719                       /* Linear search.  */
 720                       while (timer < transitions[i - 1])
 721                         --i;
 722                       goto found;
 723                     }
 724                   hi = i - 10;
 725                 }
 726               else
 727                 {
 728                   if (i + 10 >= num_transitions || timer < transitions[i + 10])
 729                     {
 730                       /* Linear search.  */
 731                       while (timer >= transitions[i])
 732                         ++i;
 733                       goto found;
 734                     }
 735                   lo = i + 10;
 736                 }
 737             }
 738
 739           /* Binary search.  */
 740           /* assert (timer >= transitions[lo] && timer < transitions[hi]); */
 741           while (lo + 1 < hi)
 742             {
 743               i = (lo + hi) / 2;
 744               if (timer < transitions[i])
 745                 hi = i;
 746               else
 747                 lo = i;
 748             }
 749           i = hi;
 750
 751         found:
 752           /* assert (timer >= transitions[i - 1]
 753              && (i == num_transitions || timer < transitions[i])); */
 754           __tzname[types[type_idxs[i - 1]].isdst]
 755             = __tzstring (&zone_names[types[type_idxs[i - 1]].idx]);
 756           size_t j = i;
 757           while (j < num_transitions)
 758             {
 759               int type = type_idxs[j];
 760               int dst = types[type].isdst;
 761               int idx = types[type].idx;
 762
 763               if (__tzname[dst] == NULL)
 764                 {
 765                   __tzname[dst] = __tzstring (&zone_names[idx]);
 766
 767                   if (__tzname[1 - dst] != NULL)
 768                     break;
 769                 }
 770
 771               ++j;
 772             }
 773
 774           if (__builtin_expect (__tzname[0] == NULL, 0))
 775             __tzname[0] = __tzname[1];
 776
 777           i = type_idxs[i - 1];
 778         }
 779
 780       struct ttinfo *info = &types[i];
 781       __daylight = rule_stdoff != rule_dstoff;
 782       __timezone = -rule_stdoff;
 783
 784       if (__tzname[0] == NULL)
 785         {
 786           /* This should only happen if there are no transition rules.
 787              In this case there should be only one single type.  */
 788           assert (num_types == 1);
 789           __tzname[0] = __tzstring (zone_names);
 790         }
 791       if (__tzname[1] == NULL)
 792         /* There is no daylight saving time.  */
 793         __tzname[1] = __tzname[0];
 794       tp->tm_isdst = info->isdst;
 795       assert (strcmp (&zone_names[info->idx], __tzname[tp->tm_isdst]) == 0);
 796       tp->tm_zone = __tzname[tp->tm_isdst];
 797       tp->tm_gmtoff = info->offset;
 798     }
 799
 800  leap:
 801   *leap_correct = 0L;
 802   *leap_hit = 0;
 803
 804   /* Find the last leap second correction transition time before TIMER.  */
 805   i = num_leaps;
 806   do
 807     if (i-- == 0)
 808       return;
 809   while (timer < leaps[i].transition);
 810
 811   /* Apply its correction.  */
 812   *leap_correct = leaps[i].change;
 813
 814   if (timer == leaps[i].transition && /* Exactly at the transition time.  */
 815       ((i == 0 && leaps[i].change > 0) ||
 816        leaps[i].change > leaps[i - 1].change))
 817     {
 818       *leap_hit = 1;
 819       while (i > 0
 820              && leaps[i].transition == leaps[i - 1].transition + 1
 821              && leaps[i].change == leaps[i - 1].change + 1)
 822         {
 823           ++*leap_hit;
 824           --i;
 825         }
 826     }
 827 }
 828 \f
 829 static void
 830 internal_function
 831 compute_tzname_max (size_t chars)
 832 {
 833   const char *p;
 834
 835   p = zone_names;
 836   do
 837     {
 838       const char *start = p;
 839       while (*p != '\0')
 840         ++p;
 841       if ((size_t) (p - start) > __tzname_cur_max)
 842         __tzname_cur_max = p - start;
 843     }
 844   while (++p < &zone_names[chars]);
 845 }