time/tzfile.c

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