time/tzfile.c

   1 /* Copyright (C) 1991-2018 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 #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 size_t num_transitions;
  52 libc_freeres_ptr (static time_t *transitions);
  53 static unsigned char *type_idxs;
  54 static size_t num_types;
  55 static struct ttinfo *types;
  56 static char *zone_names;
  57 static long int rule_stdoff;
  58 static long int rule_dstoff;
  59 static size_t num_leaps;
  60 static struct leap *leaps;
  61 static char *tzspec;
  62
  63 #include <endian.h>
  64 #include <byteswap.h>
  65
  66 /* Decode the four bytes at PTR as a signed integer in network byte order.  */
  67 static inline int
  68 __attribute ((always_inline))
  69 decode (const void *ptr)
  70 {
  71   if (BYTE_ORDER == BIG_ENDIAN && sizeof (int) == 4)
  72     return *(const int *) ptr;
  73   if (sizeof (int) == 4)
  74     return bswap_32 (*(const int *) ptr);
  75
  76   const unsigned char *p = ptr;
  77   int result = *p & (1 << (CHAR_BIT - 1)) ? ~0 : 0;
  78
  79   result = (result << 8) | *p++;
  80   result = (result << 8) | *p++;
  81   result = (result << 8) | *p++;
  82   result = (result << 8) | *p++;
  83
  84   return result;
  85 }
  86
  87
  88 static inline int64_t
  89 __attribute ((always_inline))
  90 decode64 (const void *ptr)
  91 {
  92   if ((BYTE_ORDER == BIG_ENDIAN))
  93     return *(const int64_t *) ptr;
  94
  95   return bswap_64 (*(const int64_t *) ptr);
  96 }
  97
  98
  99 void
 100 __tzfile_read (const char *file, size_t extra, char **extrap)
 101 {
 102   static const char default_tzdir[] = TZDIR;
 103   size_t num_isstd, num_isgmt;
 104   FILE *f;
 105   struct tzhead tzhead;
 106   size_t chars;
 107   size_t i;
 108   size_t total_size;
 109   size_t types_idx;
 110   size_t leaps_idx;
 111   int was_using_tzfile = __use_tzfile;
 112   int trans_width = 4;
 113   size_t tzspec_len;
 114   char *new = NULL;
 115
 116   if (sizeof (time_t) != 4 && sizeof (time_t) != 8)
 117     abort ();
 118
 119   __use_tzfile = 0;
 120
 121   if (file == NULL)
 122     /* No user specification; use the site-wide default.  */
 123     file = TZDEFAULT;
 124   else if (*file == '\0')
 125     /* User specified the empty string; use UTC with no leap seconds.  */
 126     goto ret_free_transitions;
 127   else
 128     {
 129       /* We must not allow to read an arbitrary file in a setuid
 130          program.  So we fail for any file which is not in the
 131          directory hierachy starting at TZDIR
 132          and which is not the system wide default TZDEFAULT.  */
 133       if (__libc_enable_secure
 134           && ((*file == '/'
 135                && memcmp (file, TZDEFAULT, sizeof TZDEFAULT)
 136                && memcmp (file, default_tzdir, sizeof (default_tzdir) - 1))
 137               || strstr (file, "../") != NULL))
 138         /* This test is certainly a bit too restrictive but it should
 139            catch all critical cases.  */
 140         goto ret_free_transitions;
 141     }
 142
 143   if (*file != '/')
 144     {
 145       const char *tzdir;
 146
 147       tzdir = getenv ("TZDIR");
 148       if (tzdir == NULL || *tzdir == '\0')
 149         tzdir = default_tzdir;
 150       if (__asprintf (&new, "%s/%s", tzdir, file) == -1)
 151         goto ret_free_transitions;
 152       file = new;
 153     }
 154
 155   /* If we were already using tzfile, check whether the file changed.  */
 156   struct stat64 st;
 157   if (was_using_tzfile
 158       && stat64 (file, &st) == 0
 159       && tzfile_ino == st.st_ino && tzfile_dev == st.st_dev
 160       && tzfile_mtime == st.st_mtime)
 161     goto done;  /* Nothing to do.  */
 162
 163   /* Note the file is opened with cancellation in the I/O functions
 164      disabled and if available FD_CLOEXEC set.  */
 165   f = fopen (file, "rce");
 166   if (f == NULL)
 167     goto ret_free_transitions;
 168
 169   /* Get information about the file we are actually using.  */
 170   if (fstat64 (__fileno (f), &st) != 0)
 171     {
 172       fclose (f);
 173       goto ret_free_transitions;
 174     }
 175
 176   free ((void *) transitions);
 177   transitions = NULL;
 178
 179   /* Remember the inode and device number and modification time.  */
 180   tzfile_dev = st.st_dev;
 181   tzfile_ino = st.st_ino;
 182   tzfile_mtime = st.st_mtime;
 183
 184   /* No threads reading this stream.  */
 185   __fsetlocking (f, FSETLOCKING_BYCALLER);
 186
 187  read_again:
 188   if (__builtin_expect (__fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 189                                           1, f) != 1, 0)
 190       || memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic)) != 0)
 191     goto lose;
 192
 193   num_transitions = (size_t) decode (tzhead.tzh_timecnt);
 194   num_types = (size_t) decode (tzhead.tzh_typecnt);
 195   chars = (size_t) decode (tzhead.tzh_charcnt);
 196   num_leaps = (size_t) decode (tzhead.tzh_leapcnt);
 197   num_isstd = (size_t) decode (tzhead.tzh_ttisstdcnt);
 198   num_isgmt = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 199
 200   if (__glibc_unlikely (num_isstd > num_types || num_isgmt > num_types))
 201     goto lose;
 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 (__glibc_unlikely (chars > SIZE_MAX - total_size))
 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 (__glibc_unlikely (tzspec_len < num_isstd))
 265         goto lose;
 266       tzspec_len -= num_isstd;
 267       if (__glibc_unlikely (tzspec_len == 0 || tzspec_len - 1 < num_isgmt))
 268         goto lose;
 269       tzspec_len -= num_isgmt + 1;
 270       if (__glibc_unlikely (tzspec_len == 0
 271                             || SIZE_MAX - total_size < tzspec_len))
 272         goto lose;
 273     }
 274   if (__glibc_unlikely (SIZE_MAX - total_size - tzspec_len < extra))
 275     goto lose;
 276
 277   /* Allocate enough memory including the extra block requested by the
 278      caller.  */
 279   transitions = (time_t *) malloc (total_size + tzspec_len + extra);
 280   if (transitions == NULL)
 281     goto lose;
 282
 283   type_idxs = (unsigned char *) transitions + (num_transitions
 284                                                * sizeof (time_t));
 285   types = (struct ttinfo *) ((char *) transitions + types_idx);
 286   zone_names = (char *) types + num_types * sizeof (struct ttinfo);
 287   leaps = (struct leap *) ((char *) transitions + leaps_idx);
 288   if (sizeof (time_t) == 8 && trans_width == 8)
 289     tzspec = (char *) leaps + num_leaps * sizeof (struct leap) + extra;
 290   else
 291     tzspec = NULL;
 292   if (extra > 0)
 293     *extrap = (char *) &leaps[num_leaps];
 294
 295   if (sizeof (time_t) == 4 || __builtin_expect (trans_width == 8, 1))
 296     {
 297       if (__builtin_expect (__fread_unlocked (transitions, trans_width + 1,
 298                                               num_transitions, f)
 299                             != num_transitions, 0))
 300         goto lose;
 301     }
 302   else
 303     {
 304       if (__builtin_expect (__fread_unlocked (transitions, 4,
 305                                               num_transitions, f)
 306                             != num_transitions, 0)
 307           || __builtin_expect (__fread_unlocked (type_idxs, 1, num_transitions,
 308                                                  f) != num_transitions, 0))
 309         goto lose;
 310     }
 311
 312   /* Check for bogus indices in the data file, so we can hereafter
 313      safely use type_idxs[T] as indices into `types' and never crash.  */
 314   for (i = 0; i < num_transitions; ++i)
 315     if (__glibc_unlikely (type_idxs[i] >= num_types))
 316       goto lose;
 317
 318   if ((BYTE_ORDER != BIG_ENDIAN && (sizeof (time_t) == 4 || trans_width == 4))
 319       || (BYTE_ORDER == BIG_ENDIAN && sizeof (time_t) == 8
 320           && trans_width == 4))
 321     {
 322       /* Decode the transition times, stored as 4-byte integers in
 323          network (big-endian) byte order.  We work from the end of
 324          the array so as not to clobber the next element to be
 325          processed when sizeof (time_t) > 4.  */
 326       i = num_transitions;
 327       while (i-- > 0)
 328         transitions[i] = decode ((char *) transitions + i * 4);
 329     }
 330   else if (BYTE_ORDER != BIG_ENDIAN && sizeof (time_t) == 8)
 331     {
 332       /* Decode the transition times, stored as 8-byte integers in
 333          network (big-endian) byte order.  */
 334       for (i = 0; i < num_transitions; ++i)
 335         transitions[i] = decode64 ((char *) transitions + i * 8);
 336     }
 337
 338   for (i = 0; i < num_types; ++i)
 339     {
 340       unsigned char x[4];
 341       int c;
 342       if (__builtin_expect (__fread_unlocked (x, 1,
 343                                               sizeof (x), f) != sizeof (x),
 344                             0))
 345         goto lose;
 346       c = getc_unlocked (f);
 347       if (__glibc_unlikely ((unsigned int) c > 1u))
 348         goto lose;
 349       types[i].isdst = c;
 350       c = getc_unlocked (f);
 351       if (__glibc_unlikely ((size_t) c > chars))
 352         /* Bogus index in data file.  */
 353         goto lose;
 354       types[i].idx = c;
 355       types[i].offset = (long int) decode (x);
 356     }
 357
 358   if (__glibc_unlikely (__fread_unlocked (zone_names, 1, chars, f) != chars))
 359     goto lose;
 360
 361   for (i = 0; i < num_leaps; ++i)
 362     {
 363       unsigned char x[8];
 364       if (__builtin_expect (__fread_unlocked (x, 1, trans_width, f)
 365                             != trans_width, 0))
 366         goto lose;
 367       if (sizeof (time_t) == 4 || trans_width == 4)
 368         leaps[i].transition = (time_t) decode (x);
 369       else
 370         leaps[i].transition = (time_t) decode64 (x);
 371
 372       if (__glibc_unlikely (__fread_unlocked (x, 1, 4, f) != 4))
 373         goto lose;
 374       leaps[i].change = (long int) decode (x);
 375     }
 376
 377   for (i = 0; i < num_isstd; ++i)
 378     {
 379       int c = getc_unlocked (f);
 380       if (__glibc_unlikely (c == EOF))
 381         goto lose;
 382       types[i].isstd = c != 0;
 383     }
 384   while (i < num_types)
 385     types[i++].isstd = 0;
 386
 387   for (i = 0; i < num_isgmt; ++i)
 388     {
 389       int c = getc_unlocked (f);
 390       if (__glibc_unlikely (c == EOF))
 391         goto lose;
 392       types[i].isgmt = c != 0;
 393     }
 394   while (i < num_types)
 395     types[i++].isgmt = 0;
 396
 397   /* Read the POSIX TZ-style information if possible.  */
 398   if (sizeof (time_t) == 8 && tzspec != NULL)
 399     {
 400       /* Skip over the newline first.  */
 401       if (getc_unlocked (f) != '\n'
 402           || (__fread_unlocked (tzspec, 1, tzspec_len - 1, f)
 403               != tzspec_len - 1))
 404         tzspec = NULL;
 405       else
 406         tzspec[tzspec_len - 1] = '\0';
 407     }
 408   else if (sizeof (time_t) == 4 && tzhead.tzh_version[0] != '\0')
 409     {
 410       /* Get the TZ string.  */
 411       if (__builtin_expect (__fread_unlocked ((void *) &tzhead,
 412                                               sizeof (tzhead), 1, f) != 1, 0)
 413           || (memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic))
 414               != 0))
 415         goto lose;
 416
 417       size_t num_transitions2 = (size_t) decode (tzhead.tzh_timecnt);
 418       size_t num_types2 = (size_t) decode (tzhead.tzh_typecnt);
 419       size_t chars2 = (size_t) decode (tzhead.tzh_charcnt);
 420       size_t num_leaps2 = (size_t) decode (tzhead.tzh_leapcnt);
 421       size_t num_isstd2 = (size_t) decode (tzhead.tzh_ttisstdcnt);
 422       size_t num_isgmt2 = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 423
 424       /* Position the stream before the second header.  */
 425       size_t to_skip = (num_transitions2 * (8 + 1)
 426                         + num_types2 * 6
 427                         + chars2
 428                         + num_leaps2 * 12
 429                         + num_isstd2
 430                         + num_isgmt2);
 431       off_t off;
 432       if (fseek (f, to_skip, SEEK_CUR) != 0
 433           || (off = __ftello (f)) < 0
 434           || st.st_size < off + 2)
 435         goto lose;
 436
 437       tzspec_len = st.st_size - off - 1;
 438       if (tzspec_len == 0)
 439         goto lose;
 440       char *tzstr = malloc (tzspec_len);
 441       if (tzstr == NULL)
 442         goto lose;
 443       if (getc_unlocked (f) != '\n'
 444           || (__fread_unlocked (tzstr, 1, tzspec_len - 1, f)
 445               != tzspec_len - 1))
 446         {
 447           free (tzstr);
 448           goto lose;
 449         }
 450       tzstr[tzspec_len - 1] = '\0';
 451       tzspec = __tzstring (tzstr);
 452       free (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   if (num_transitions == 0)
 496     /* Use the first rule (which should also be the only one).  */
 497     rule_stdoff = rule_dstoff = types[0].offset;
 498   else
 499     {
 500       int stdoff_set = 0, dstoff_set = 0;
 501       rule_stdoff = rule_dstoff = 0;
 502       i = num_transitions - 1;
 503       do
 504         {
 505           if (!stdoff_set && !types[type_idxs[i]].isdst)
 506             {
 507               stdoff_set = 1;
 508               rule_stdoff = types[type_idxs[i]].offset;
 509             }
 510           else if (!dstoff_set && types[type_idxs[i]].isdst)
 511             {
 512               dstoff_set = 1;
 513               rule_dstoff = types[type_idxs[i]].offset;
 514             }
 515           if (stdoff_set && dstoff_set)
 516             break;
 517         }
 518       while (i-- > 0);
 519
 520       if (!dstoff_set)
 521         rule_dstoff = rule_stdoff;
 522     }
 523
 524   __daylight = rule_stdoff != rule_dstoff;
 525   __timezone = -rule_stdoff;
 526
 527  done:
 528   __use_tzfile = 1;
 529   free (new);
 530   return;
 531
 532  lose:
 533   fclose (f);
 534  ret_free_transitions:
 535   free (new);
 536   free ((void *) transitions);
 537   transitions = NULL;
 538 }
 539 \f
 540 /* The user specified a hand-made timezone, but not its DST rules.
 541    We will use the names and offsets from the user, and the rules
 542    from the TZDEFRULES file.  */
 543
 544 void
 545 __tzfile_default (const char *std, const char *dst,
 546                   long int stdoff, long int dstoff)
 547 {
 548   size_t stdlen = strlen (std) + 1;
 549   size_t dstlen = strlen (dst) + 1;
 550   size_t i;
 551   int isdst;
 552   char *cp;
 553
 554   __tzfile_read (TZDEFRULES, stdlen + dstlen, &cp);
 555   if (!__use_tzfile)
 556     return;
 557
 558   if (num_types < 2)
 559     {
 560       __use_tzfile = 0;
 561       return;
 562     }
 563
 564   /* Ignore the zone names read from the file and use the given ones
 565      instead.  */
 566   __mempcpy (__mempcpy (cp, std, stdlen), dst, dstlen);
 567   zone_names = cp;
 568
 569   /* Now there are only two zones, regardless of what the file contained.  */
 570   num_types = 2;
 571
 572   /* Now correct the transition times for the user-specified standard and
 573      daylight offsets from GMT.  */
 574   isdst = 0;
 575   for (i = 0; i < num_transitions; ++i)
 576     {
 577       struct ttinfo *trans_type = &types[type_idxs[i]];
 578
 579       /* We will use only types 0 (standard) and 1 (daylight).
 580          Fix up this transition to point to whichever matches
 581          the flavor of its original type.  */
 582       type_idxs[i] = trans_type->isdst;
 583
 584       if (trans_type->isgmt)
 585         /* The transition time is in GMT.  No correction to apply.  */ ;
 586       else if (isdst && !trans_type->isstd)
 587         /* The type says this transition is in "local wall clock time", and
 588            wall clock time as of the previous transition was DST.  Correct
 589            for the difference between the rule's DST offset and the user's
 590            DST offset.  */
 591         transitions[i] += dstoff - rule_dstoff;
 592       else
 593         /* This transition is in "local wall clock time", and wall clock
 594            time as of this iteration is non-DST.  Correct for the
 595            difference between the rule's standard offset and the user's
 596            standard offset.  */
 597         transitions[i] += stdoff - rule_stdoff;
 598
 599       /* The DST state of "local wall clock time" for the next iteration is
 600          as specified by this transition.  */
 601       isdst = trans_type->isdst;
 602     }
 603
 604   /* Now that we adjusted the transitions to the requested offsets,
 605      reset the rule_stdoff and rule_dstoff values appropriately.  They
 606      are used elsewhere.  */
 607   rule_stdoff = stdoff;
 608   rule_dstoff = dstoff;
 609
 610   /* Reset types 0 and 1 to describe the user's settings.  */
 611   types[0].idx = 0;
 612   types[0].offset = stdoff;
 613   types[0].isdst = 0;
 614   types[1].idx = stdlen;
 615   types[1].offset = dstoff;
 616   types[1].isdst = 1;
 617
 618   /* Reset the zone names to point to the user's names.  */
 619   __tzname[0] = (char *) std;
 620   __tzname[1] = (char *) dst;
 621
 622   /* Set the timezone.  */
 623   __timezone = -types[0].offset;
 624
 625   /* Invalidate the tzfile attribute cache to force rereading
 626      TZDEFRULES the next time it is used.  */
 627   tzfile_dev = 0;
 628   tzfile_ino = 0;
 629   tzfile_mtime = 0;
 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 }