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 #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   /* For platforms with 64-bit time_t we use the new format if available.  */
 204   if (sizeof (time_t) == 8 && trans_width == 4
 205       && tzhead.tzh_version[0] != '\0')
 206     {
 207       /* We use the 8-byte format.  */
 208       trans_width = 8;
 209
 210       /* Position the stream before the second header.  */
 211       size_t to_skip = (num_transitions * (4 + 1)
 212                         + num_types * 6
 213                         + chars
 214                         + num_leaps * 8
 215                         + num_isstd
 216                         + num_isgmt);
 217       if (fseek (f, to_skip, SEEK_CUR) != 0)
 218         goto lose;
 219
 220       goto read_again;
 221     }
 222
 223   if (__builtin_expect (num_transitions
 224                         > ((SIZE_MAX - (__alignof__ (struct ttinfo) - 1))
 225                            / (sizeof (time_t) + 1)), 0))
 226     goto lose;
 227   total_size = num_transitions * (sizeof (time_t) + 1);
 228   total_size = ((total_size + __alignof__ (struct ttinfo) - 1)
 229                 & ~(__alignof__ (struct ttinfo) - 1));
 230   types_idx = total_size;
 231   if (__builtin_expect (num_types
 232                         > (SIZE_MAX - total_size) / sizeof (struct ttinfo), 0))
 233     goto lose;
 234   total_size += num_types * sizeof (struct ttinfo);
 235   if (__builtin_expect (chars > SIZE_MAX - total_size, 0))
 236     goto lose;
 237   total_size += chars;
 238   if (__builtin_expect (__alignof__ (struct leap) - 1
 239                         > SIZE_MAX - total_size, 0))
 240     goto lose;
 241   total_size = ((total_size + __alignof__ (struct leap) - 1)
 242                 & ~(__alignof__ (struct leap) - 1));
 243   leaps_idx = total_size;
 244   if (__builtin_expect (num_leaps
 245                         > (SIZE_MAX - total_size) / sizeof (struct leap), 0))
 246     goto lose;
 247   total_size += num_leaps * sizeof (struct leap);
 248   tzspec_len = 0;
 249   if (sizeof (time_t) == 8 && trans_width == 8)
 250     {
 251       off_t rem = st.st_size - ftello (f);
 252       if (__builtin_expect (rem < 0
 253                             || (size_t) rem < (num_transitions * (8 + 1)
 254                                                + num_types * 6
 255                                                + chars), 0))
 256         goto lose;
 257       tzspec_len = (size_t) rem - (num_transitions * (8 + 1)
 258                                    + num_types * 6
 259                                    + chars);
 260       if (__builtin_expect (num_leaps > SIZE_MAX / 12
 261                             || tzspec_len < num_leaps * 12, 0))
 262         goto lose;
 263       tzspec_len -= num_leaps * 12;
 264       if (__builtin_expect (tzspec_len < num_isstd, 0))
 265         goto lose;
 266       tzspec_len -= num_isstd;
 267       if (__builtin_expect (tzspec_len == 0 || tzspec_len - 1 < num_isgmt, 0))
 268         goto lose;
 269       tzspec_len -= num_isgmt + 1;
 270       if (__builtin_expect (SIZE_MAX - total_size < tzspec_len, 0))
 271         goto lose;
 272     }
 273   if (__builtin_expect (SIZE_MAX - total_size - tzspec_len < extra, 0))
 274     goto lose;
 275
 276   /* Allocate enough memory including the extra block requested by the
 277      caller.  */
 278   transitions = (time_t *) malloc (total_size + tzspec_len + extra);
 279   if (transitions == NULL)
 280     goto lose;
 281
 282   type_idxs = (unsigned char *) transitions + (num_transitions
 283                                                * sizeof (time_t));
 284   types = (struct ttinfo *) ((char *) transitions + types_idx);
 285   zone_names = (char *) types + num_types * sizeof (struct ttinfo);
 286   leaps = (struct leap *) ((char *) transitions + leaps_idx);
 287   if (sizeof (time_t) == 8 && trans_width == 8)
 288     tzspec = (char *) leaps + num_leaps * sizeof (struct leap) + extra;
 289   else
 290     tzspec = NULL;
 291   if (extra > 0)
 292     *extrap = (char *) &leaps[num_leaps];
 293
 294   if (sizeof (time_t) == 4 || __builtin_expect (trans_width == 8, 1))
 295     {
 296       if (__builtin_expect (fread_unlocked (transitions, trans_width + 1,
 297                                             num_transitions, f)
 298                             != num_transitions, 0))
 299         goto lose;
 300     }
 301   else
 302     {
 303       if (__builtin_expect (fread_unlocked (transitions, 4, num_transitions, f)
 304                             != num_transitions, 0)
 305           || __builtin_expect (fread_unlocked (type_idxs, 1, num_transitions,
 306                                                f) != num_transitions, 0))
 307         goto lose;
 308     }
 309
 310   /* Check for bogus indices in the data file, so we can hereafter
 311      safely use type_idxs[T] as indices into `types' and never crash.  */
 312   for (i = 0; i < num_transitions; ++i)
 313     if (__builtin_expect (type_idxs[i] >= num_types, 0))
 314       goto lose;
 315
 316   if ((BYTE_ORDER != BIG_ENDIAN && (sizeof (time_t) == 4 || trans_width == 4))
 317       || (BYTE_ORDER == BIG_ENDIAN && sizeof (time_t) == 8
 318           && trans_width == 4))
 319     {
 320       /* Decode the transition times, stored as 4-byte integers in
 321          network (big-endian) byte order.  We work from the end of
 322          the array so as not to clobber the next element to be
 323          processed when sizeof (time_t) > 4.  */
 324       i = num_transitions;
 325       while (i-- > 0)
 326         transitions[i] = decode ((char *) transitions + i * 4);
 327     }
 328   else if (BYTE_ORDER != BIG_ENDIAN && sizeof (time_t) == 8)
 329     {
 330       /* Decode the transition times, stored as 8-byte integers in
 331          network (big-endian) byte order.  */
 332       for (i = 0; i < num_transitions; ++i)
 333         transitions[i] = decode64 ((char *) transitions + i * 8);
 334     }
 335
 336   for (i = 0; i < num_types; ++i)
 337     {
 338       unsigned char x[4];
 339       int c;
 340       if (__builtin_expect (fread_unlocked (x, 1, sizeof (x), f) != sizeof (x),
 341                             0))
 342         goto lose;
 343       c = getc_unlocked (f);
 344       if (__builtin_expect ((unsigned int) c > 1u, 0))
 345         goto lose;
 346       types[i].isdst = c;
 347       c = getc_unlocked (f);
 348       if (__builtin_expect ((size_t) c > chars, 0))
 349         /* Bogus index in data file.  */
 350         goto lose;
 351       types[i].idx = c;
 352       types[i].offset = (long int) decode (x);
 353     }
 354
 355   if (__builtin_expect (fread_unlocked (zone_names, 1, chars, f) != chars, 0))
 356     goto lose;
 357
 358   for (i = 0; i < num_leaps; ++i)
 359     {
 360       unsigned char x[8];
 361       if (__builtin_expect (fread_unlocked (x, 1, trans_width, f)
 362                             != trans_width, 0))
 363         goto lose;
 364       if (sizeof (time_t) == 4 || trans_width == 4)
 365         leaps[i].transition = (time_t) decode (x);
 366       else
 367         leaps[i].transition = (time_t) decode64 (x);
 368
 369       if (__builtin_expect (fread_unlocked (x, 1, 4, f) != 4, 0))
 370         goto lose;
 371       leaps[i].change = (long int) decode (x);
 372     }
 373
 374   for (i = 0; i < num_isstd; ++i)
 375     {
 376       int c = getc_unlocked (f);
 377       if (__builtin_expect (c == EOF, 0))
 378         goto lose;
 379       types[i].isstd = c != 0;
 380     }
 381   while (i < num_types)
 382     types[i++].isstd = 0;
 383
 384   for (i = 0; i < num_isgmt; ++i)
 385     {
 386       int c = getc_unlocked (f);
 387       if (__builtin_expect (c == EOF, 0))
 388         goto lose;
 389       types[i].isgmt = c != 0;
 390     }
 391   while (i < num_types)
 392     types[i++].isgmt = 0;
 393
 394   /* Read the POSIX TZ-style information if possible.  */
 395   if (sizeof (time_t) == 8 && tzspec != NULL)
 396     {
 397       /* Skip over the newline first.  */
 398       if (getc_unlocked (f) != '\n'
 399           || (fread_unlocked (tzspec, 1, tzspec_len - 1, f)
 400               != tzspec_len - 1))
 401         tzspec = NULL;
 402       else
 403         tzspec[tzspec_len - 1] = '\0';
 404     }
 405   else if (sizeof (time_t) == 4 && tzhead.tzh_version[0] != '\0')
 406     {
 407       /* Get the TZ string.  */
 408       if (__builtin_expect (fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 409                                             1, f) != 1, 0)
 410           || (memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic))
 411               != 0))
 412         goto lose;
 413
 414       size_t num_transitions2 = (size_t) decode (tzhead.tzh_timecnt);
 415       size_t num_types2 = (size_t) decode (tzhead.tzh_typecnt);
 416       size_t chars2 = (size_t) decode (tzhead.tzh_charcnt);
 417       size_t num_leaps2 = (size_t) decode (tzhead.tzh_leapcnt);
 418       size_t num_isstd2 = (size_t) decode (tzhead.tzh_ttisstdcnt);
 419       size_t num_isgmt2 = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 420
 421       /* Position the stream before the second header.  */
 422       size_t to_skip = (num_transitions2 * (8 + 1)
 423                         + num_types2 * 6
 424                         + chars2
 425                         + num_leaps2 * 12
 426                         + num_isstd2
 427                         + num_isgmt2);
 428       off_t off;
 429       if (fseek (f, to_skip, SEEK_CUR) != 0
 430           || (off = ftello (f)) < 0
 431           || st.st_size < off + 2)
 432         goto lose;
 433
 434       tzspec_len = st.st_size - off - 1;
 435       char *tzstr = alloca (tzspec_len);
 436       if (getc_unlocked (f) != '\n'
 437           || (fread_unlocked (tzstr, 1, tzspec_len - 1, f) != tzspec_len - 1))
 438         goto lose;
 439       tzstr[tzspec_len - 1] = '\0';
 440       tzspec = __tzstring (tzstr);
 441     }
 442
 443   /* Don't use an empty TZ string.  */
 444   if (tzspec != NULL && tzspec[0] == '\0')
 445     tzspec = NULL;
 446
 447   fclose (f);
 448
 449   /* First "register" all timezone names.  */
 450   for (i = 0; i < num_types; ++i)
 451     (void) __tzstring (&zone_names[types[i].idx]);
 452
 453   /* Find the standard and daylight time offsets used by the rule file.
 454      We choose the offsets in the types of each flavor that are
 455      transitioned to earliest in time.  */
 456   __tzname[0] = NULL;
 457   __tzname[1] = NULL;
 458   for (i = num_transitions; i > 0; )
 459     {
 460       int type = type_idxs[--i];
 461       int dst = types[type].isdst;
 462
 463       if (__tzname[dst] == NULL)
 464         {
 465           int idx = types[type].idx;
 466
 467           __tzname[dst] = __tzstring (&zone_names[idx]);
 468
 469           if (__tzname[1 - dst] != NULL)
 470             break;
 471         }
 472     }
 473   if (__tzname[0] == NULL)
 474     {
 475       /* This should only happen if there are no transition rules.
 476          In this case there should be only one single type.  */
 477       assert (num_types == 1);
 478       __tzname[0] = __tzstring (zone_names);
 479     }
 480   if (__tzname[1] == NULL)
 481     __tzname[1] = __tzname[0];
 482
 483   compute_tzname_max (chars);
 484
 485   if (num_transitions == 0)
 486     /* Use the first rule (which should also be the only one).  */
 487     rule_stdoff = rule_dstoff = types[0].offset;
 488   else
 489     {
 490       int stdoff_set = 0, dstoff_set = 0;
 491       rule_stdoff = rule_dstoff = 0;
 492       i = num_transitions - 1;
 493       do
 494         {
 495           if (!stdoff_set && !types[type_idxs[i]].isdst)
 496             {
 497               stdoff_set = 1;
 498               rule_stdoff = types[type_idxs[i]].offset;
 499             }
 500           else if (!dstoff_set && types[type_idxs[i]].isdst)
 501             {
 502               dstoff_set = 1;
 503               rule_dstoff = types[type_idxs[i]].offset;
 504             }
 505           if (stdoff_set && dstoff_set)
 506             break;
 507         }
 508       while (i-- > 0);
 509
 510       if (!dstoff_set)
 511         rule_dstoff = rule_stdoff;
 512     }
 513
 514   __daylight = rule_stdoff != rule_dstoff;
 515   __timezone = -rule_stdoff;
 516
 517  done:
 518   __use_tzfile = 1;
 519   free (new);
 520   return;
 521
 522  lose:
 523   fclose (f);
 524  ret_free_transitions:
 525   free (new);
 526   free ((void *) transitions);
 527   transitions = NULL;
 528 }
 529 \f
 530 /* The user specified a hand-made timezone, but not its DST rules.
 531    We will use the names and offsets from the user, and the rules
 532    from the TZDEFRULES file.  */
 533
 534 void
 535 __tzfile_default (const char *std, const char *dst,
 536                   long int stdoff, long int dstoff)
 537 {
 538   size_t stdlen = strlen (std) + 1;
 539   size_t dstlen = strlen (dst) + 1;
 540   size_t i;
 541   int isdst;
 542   char *cp;
 543
 544   __tzfile_read (TZDEFRULES, stdlen + dstlen, &cp);
 545   if (!__use_tzfile)
 546     return;
 547
 548   if (num_types < 2)
 549     {
 550       __use_tzfile = 0;
 551       return;
 552     }
 553
 554   /* Ignore the zone names read from the file and use the given ones
 555      instead.  */
 556   __mempcpy (__mempcpy (cp, std, stdlen), dst, dstlen);
 557   zone_names = cp;
 558
 559   /* Now there are only two zones, regardless of what the file contained.  */
 560   num_types = 2;
 561
 562   /* Now correct the transition times for the user-specified standard and
 563      daylight offsets from GMT.  */
 564   isdst = 0;
 565   for (i = 0; i < num_transitions; ++i)
 566     {
 567       struct ttinfo *trans_type = &types[type_idxs[i]];
 568
 569       /* We will use only types 0 (standard) and 1 (daylight).
 570          Fix up this transition to point to whichever matches
 571          the flavor of its original type.  */
 572       type_idxs[i] = trans_type->isdst;
 573
 574       if (trans_type->isgmt)
 575         /* The transition time is in GMT.  No correction to apply.  */ ;
 576       else if (isdst && !trans_type->isstd)
 577         /* The type says this transition is in "local wall clock time", and
 578            wall clock time as of the previous transition was DST.  Correct
 579            for the difference between the rule's DST offset and the user's
 580            DST offset.  */
 581         transitions[i] += dstoff - rule_dstoff;
 582       else
 583         /* This transition is in "local wall clock time", and wall clock
 584            time as of this iteration is non-DST.  Correct for the
 585            difference between the rule's standard offset and the user's
 586            standard offset.  */
 587         transitions[i] += stdoff - rule_stdoff;
 588
 589       /* The DST state of "local wall clock time" for the next iteration is
 590          as specified by this transition.  */
 591       isdst = trans_type->isdst;
 592     }
 593
 594   /* Now that we adjusted the transitions to the requested offsets,
 595      reset the rule_stdoff and rule_dstoff values appropriately.  They
 596      are used elsewhere.  */
 597   rule_stdoff = stdoff;
 598   rule_dstoff = dstoff;
 599
 600   /* Reset types 0 and 1 to describe the user's settings.  */
 601   types[0].idx = 0;
 602   types[0].offset = stdoff;
 603   types[0].isdst = 0;
 604   types[1].idx = stdlen;
 605   types[1].offset = dstoff;
 606   types[1].isdst = 1;
 607
 608   /* Reset the zone names to point to the user's names.  */
 609   __tzname[0] = (char *) std;
 610   __tzname[1] = (char *) dst;
 611
 612   /* Set the timezone.  */
 613   __timezone = -types[0].offset;
 614
 615   compute_tzname_max (stdlen + dstlen);
 616 }
 617 \f
 618 void
 619 __tzfile_compute (time_t timer, int use_localtime,
 620                   long int *leap_correct, int *leap_hit,
 621                   struct tm *tp)
 622 {
 623   size_t i;
 624
 625   if (use_localtime)
 626     {
 627       __tzname[0] = NULL;
 628       __tzname[1] = NULL;
 629
 630       if (__builtin_expect (num_transitions == 0 || timer < transitions[0], 0))
 631         {
 632           /* TIMER is before any transition (or there are no transitions).
 633              Choose the first non-DST type
 634              (or the first if they're all DST types).  */
 635           i = 0;
 636           while (i < num_types && types[i].isdst)
 637             {
 638               if (__tzname[1] == NULL)
 639                 __tzname[1] = __tzstring (&zone_names[types[i].idx]);
 640
 641               ++i;
 642             }
 643
 644           if (i == num_types)
 645             i = 0;
 646           __tzname[0] = __tzstring (&zone_names[types[i].idx]);
 647           if (__tzname[1] == NULL)
 648             {
 649               size_t j = i;
 650               while (j < num_types)
 651                 if (types[j].isdst)
 652                   {
 653                     __tzname[1] = __tzstring (&zone_names[types[j].idx]);
 654                     break;
 655                   }
 656                 else
 657                   ++j;
 658             }
 659         }
 660       else if (__builtin_expect (timer >= transitions[num_transitions - 1], 0))
 661         {
 662           if (__builtin_expect (tzspec == NULL, 0))
 663             {
 664             use_last:
 665               i = num_transitions;
 666               goto found;
 667             }
 668
 669           /* Parse the POSIX TZ-style string.  */
 670           __tzset_parse_tz (tzspec);
 671
 672           /* Convert to broken down structure.  If this fails do not
 673              use the string.  */
 674           if (__builtin_expect (! __offtime (&timer, 0, tp), 0))
 675             goto use_last;
 676
 677           /* Use the rules from the TZ string to compute the change.  */
 678           __tz_compute (timer, tp, 1);
 679
 680           /* If tzspec comes from posixrules loaded by __tzfile_default,
 681              override the STD and DST zone names with the ones user
 682              requested in TZ envvar.  */
 683           if (__builtin_expect (zone_names == (char *) &leaps[num_leaps], 0))
 684             {
 685               assert (num_types == 2);
 686               __tzname[0] = __tzstring (zone_names);
 687               __tzname[1] = __tzstring (&zone_names[strlen (zone_names) + 1]);
 688             }
 689
 690           goto leap;
 691         }
 692       else
 693         {
 694           /* Find the first transition after TIMER, and
 695              then pick the type of the transition before it.  */
 696           size_t lo = 0;
 697           size_t hi = num_transitions - 1;
 698           /* Assume that DST is changing twice a year and guess initial
 699              search spot from it.
 700              Half of a gregorian year has on average 365.2425 * 86400 / 2
 701              = 15778476 seconds.  */
 702           i = (transitions[num_transitions - 1] - timer) / 15778476;
 703           if (i < num_transitions)
 704             {
 705               i = num_transitions - 1 - i;
 706               if (timer < transitions[i])
 707                 {
 708                   if (i < 10 || timer >= transitions[i - 10])
 709                     {
 710                       /* Linear search.  */
 711                       while (timer < transitions[i - 1])
 712                         --i;
 713                       goto found;
 714                     }
 715                   hi = i - 10;
 716                 }
 717               else
 718                 {
 719                   if (i + 10 >= num_transitions || timer < transitions[i + 10])
 720                     {
 721                       /* Linear search.  */
 722                       while (timer >= transitions[i])
 723                         ++i;
 724                       goto found;
 725                     }
 726                   lo = i + 10;
 727                 }
 728             }
 729
 730           /* Binary search.  */
 731           /* assert (timer >= transitions[lo] && timer < transitions[hi]); */
 732           while (lo + 1 < hi)
 733             {
 734               i = (lo + hi) / 2;
 735               if (timer < transitions[i])
 736                 hi = i;
 737               else
 738                 lo = i;
 739             }
 740           i = hi;
 741
 742         found:
 743           /* assert (timer >= transitions[i - 1]
 744              && (i == num_transitions || timer < transitions[i])); */
 745           __tzname[types[type_idxs[i - 1]].isdst]
 746             = __tzstring (&zone_names[types[type_idxs[i - 1]].idx]);
 747           size_t j = i;
 748           while (j < num_transitions)
 749             {
 750               int type = type_idxs[j];
 751               int dst = types[type].isdst;
 752               int idx = types[type].idx;
 753
 754               if (__tzname[dst] == NULL)
 755                 {
 756                   __tzname[dst] = __tzstring (&zone_names[idx]);
 757
 758                   if (__tzname[1 - dst] != NULL)
 759                     break;
 760                 }
 761
 762               ++j;
 763             }
 764
 765           if (__builtin_expect (__tzname[0] == NULL, 0))
 766             __tzname[0] = __tzname[1];
 767
 768           i = type_idxs[i - 1];
 769         }
 770
 771       struct ttinfo *info = &types[i];
 772       __daylight = rule_stdoff != rule_dstoff;
 773       __timezone = -rule_stdoff;
 774
 775       if (__tzname[0] == NULL)
 776         {
 777           /* This should only happen if there are no transition rules.
 778              In this case there should be only one single type.  */
 779           assert (num_types == 1);
 780           __tzname[0] = __tzstring (zone_names);
 781         }
 782       if (__tzname[1] == NULL)
 783         /* There is no daylight saving time.  */
 784         __tzname[1] = __tzname[0];
 785       tp->tm_isdst = info->isdst;
 786       assert (strcmp (&zone_names[info->idx], __tzname[tp->tm_isdst]) == 0);
 787       tp->tm_zone = __tzname[tp->tm_isdst];
 788       tp->tm_gmtoff = info->offset;
 789     }
 790
 791  leap:
 792   *leap_correct = 0L;
 793   *leap_hit = 0;
 794
 795   /* Find the last leap second correction transition time before TIMER.  */
 796   i = num_leaps;
 797   do
 798     if (i-- == 0)
 799       return;
 800   while (timer < leaps[i].transition);
 801
 802   /* Apply its correction.  */
 803   *leap_correct = leaps[i].change;
 804
 805   if (timer == leaps[i].transition && /* Exactly at the transition time.  */
 806       ((i == 0 && leaps[i].change > 0) ||
 807        leaps[i].change > leaps[i - 1].change))
 808     {
 809       *leap_hit = 1;
 810       while (i > 0
 811              && leaps[i].transition == leaps[i - 1].transition + 1
 812              && leaps[i].change == leaps[i - 1].change + 1)
 813         {
 814           ++*leap_hit;
 815           --i;
 816         }
 817     }
 818 }
 819 \f
 820 static void
 821 internal_function
 822 compute_tzname_max (size_t chars)
 823 {
 824   const char *p;
 825
 826   p = zone_names;
 827   do
 828     {
 829       const char *start = p;
 830       while (*p != '\0')
 831         ++p;
 832       if ((size_t) (p - start) > __tzname_cur_max)
 833         __tzname_cur_max = p - start;
 834     }
 835   while (++p < &zone_names[chars]);
 836 }