time/tzfile.c

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