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, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #include <assert.h>
  20 #include <limits.h>
  21 #include <stdio.h>
  22 #include <stdio_ext.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <time.h>
  26 #include <unistd.h>
  27 #include <sys/stat.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   register FILE *f;
 108   struct tzhead tzhead;
 109   size_t chars;
 110   register 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
 118   if (sizeof (time_t) != 4 && sizeof (time_t) != 8)
 119     abort ();
 120
 121   __use_tzfile = 0;
 122
 123   if (file == NULL)
 124     /* No user specification; use the site-wide default.  */
 125     file = TZDEFAULT;
 126   else if (*file == '\0')
 127     /* User specified the empty string; use UTC with no leap seconds.  */
 128     goto ret_free_transitions;
 129   else
 130     {
 131       /* We must not allow to read an arbitrary file in a setuid
 132          program.  So we fail for any file which is not in the
 133          directory hierachy starting at TZDIR
 134          and which is not the system wide default TZDEFAULT.  */
 135       if (__libc_enable_secure
 136           && ((*file == '/'
 137                && memcmp (file, TZDEFAULT, sizeof TZDEFAULT)
 138                && memcmp (file, default_tzdir, sizeof (default_tzdir) - 1))
 139               || strstr (file, "../") != NULL))
 140         /* This test is certainly a bit too restrictive but it should
 141            catch all critical cases.  */
 142         goto ret_free_transitions;
 143     }
 144
 145   if (*file != '/')
 146     {
 147       const char *tzdir;
 148       unsigned int len, tzdir_len;
 149       char *new, *tmp;
 150
 151       tzdir = getenv ("TZDIR");
 152       if (tzdir == NULL || *tzdir == '\0')
 153         {
 154           tzdir = default_tzdir;
 155           tzdir_len = sizeof (default_tzdir) - 1;
 156         }
 157       else
 158         tzdir_len = strlen (tzdir);
 159       len = strlen (file) + 1;
 160       new = (char *) __alloca (tzdir_len + 1 + len);
 161       tmp = __mempcpy (new, tzdir, tzdir_len);
 162       *tmp++ = '/';
 163       memcpy (tmp, file, len);
 164       file = new;
 165     }
 166
 167   /* If we were already using tzfile, check whether the file changed.  */
 168   struct stat64 st;
 169   if (was_using_tzfile
 170       && stat64 (file, &st) == 0
 171       && tzfile_ino == st.st_ino && tzfile_dev == st.st_dev
 172       && tzfile_mtime == st.st_mtime)
 173     {
 174       /* Nothing to do.  */
 175       __use_tzfile = 1;
 176       return;
 177     }
 178
 179   /* Note the file is opened with cancellation in the I/O functions
 180      disabled and if available FD_CLOEXEC set.  */
 181   f = fopen (file, "rce");
 182   if (f == NULL)
 183     goto ret_free_transitions;
 184
 185   /* Get information about the file we are actually using.  */
 186   if (fstat64 (fileno (f), &st) != 0)
 187     {
 188       fclose (f);
 189       goto ret_free_transitions;
 190     }
 191
 192   free ((void *) transitions);
 193   transitions = NULL;
 194
 195   /* Remember the inode and device number and modification time.  */
 196   tzfile_dev = st.st_dev;
 197   tzfile_ino = st.st_ino;
 198   tzfile_mtime = st.st_mtime;
 199
 200   /* No threads reading this stream.  */
 201   __fsetlocking (f, FSETLOCKING_BYCALLER);
 202
 203  read_again:
 204   if (__builtin_expect (fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 205                                         1, f) != 1, 0)
 206       || memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic)) != 0)
 207     goto lose;
 208
 209   num_transitions = (size_t) decode (tzhead.tzh_timecnt);
 210   num_types = (size_t) decode (tzhead.tzh_typecnt);
 211   chars = (size_t) decode (tzhead.tzh_charcnt);
 212   num_leaps = (size_t) decode (tzhead.tzh_leapcnt);
 213   num_isstd = (size_t) decode (tzhead.tzh_ttisstdcnt);
 214   num_isgmt = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 215
 216   /* For platforms with 64-bit time_t we use the new format if available.  */
 217   if (sizeof (time_t) == 8 && trans_width == 4
 218       && tzhead.tzh_version[0] != '\0')
 219     {
 220       /* We use the 8-byte format.  */
 221       trans_width = 8;
 222
 223       /* Position the stream before the second header.  */
 224       size_t to_skip = (num_transitions * (4 + 1)
 225                         + num_types * 6
 226                         + chars
 227                         + num_leaps * 8
 228                         + num_isstd
 229                         + num_isgmt);
 230       if (fseek (f, to_skip, SEEK_CUR) != 0)
 231         goto lose;
 232
 233       goto read_again;
 234     }
 235
 236   if (__builtin_expect (num_transitions
 237                         > ((SIZE_MAX - (__alignof__ (struct ttinfo) - 1))
 238                            / (sizeof (time_t) + 1)), 0))
 239     goto lose;
 240   total_size = num_transitions * (sizeof (time_t) + 1);
 241   total_size = ((total_size + __alignof__ (struct ttinfo) - 1)
 242                 & ~(__alignof__ (struct ttinfo) - 1));
 243   types_idx = total_size;
 244   if (__builtin_expect (num_types
 245                         > (SIZE_MAX - total_size) / sizeof (struct ttinfo), 0))
 246     goto lose;
 247   total_size += num_types * sizeof (struct ttinfo);
 248   if (__builtin_expect (chars > SIZE_MAX - total_size, 0))
 249     goto lose;
 250   total_size += chars;
 251   if (__builtin_expect (__alignof__ (struct leap) - 1
 252                         > SIZE_MAX - total_size, 0))
 253     goto lose;
 254   total_size = ((total_size + __alignof__ (struct leap) - 1)
 255                 & ~(__alignof__ (struct leap) - 1));
 256   leaps_idx = total_size;
 257   if (__builtin_expect (num_leaps
 258                         > (SIZE_MAX - total_size) / sizeof (struct leap), 0))
 259     goto lose;
 260   total_size += num_leaps * sizeof (struct leap);
 261   tzspec_len = 0;
 262   if (sizeof (time_t) == 8 && trans_width == 8)
 263     {
 264       off_t rem = st.st_size - ftello (f);
 265       if (__builtin_expect (rem < 0
 266                             || (size_t) rem < (num_transitions * (8 + 1)
 267                                                + num_types * 6
 268                                                + chars), 0))
 269         goto lose;
 270       tzspec_len = (size_t) rem - (num_transitions * (8 + 1)
 271                                    + num_types * 6
 272                                    + chars);
 273       if (__builtin_expect (num_leaps > SIZE_MAX / 12
 274                             || tzspec_len < num_leaps * 12, 0))
 275         goto lose;
 276       tzspec_len -= num_leaps * 12;
 277       if (__builtin_expect (tzspec_len < num_isstd, 0))
 278         goto lose;
 279       tzspec_len -= num_isstd;
 280       if (__builtin_expect (tzspec_len == 0 || tzspec_len - 1 < num_isgmt, 0))
 281         goto lose;
 282       tzspec_len -= num_isgmt + 1;
 283       if (__builtin_expect (SIZE_MAX - total_size < tzspec_len, 0))
 284         goto lose;
 285     }
 286   if (__builtin_expect (SIZE_MAX - total_size - tzspec_len < extra, 0))
 287     goto lose;
 288
 289   /* Allocate enough memory including the extra block requested by the
 290      caller.  */
 291   transitions = (time_t *) malloc (total_size + tzspec_len + extra);
 292   if (transitions == NULL)
 293     goto lose;
 294
 295   type_idxs = (unsigned char *) transitions + (num_transitions
 296                                                * sizeof (time_t));
 297   types = (struct ttinfo *) ((char *) transitions + types_idx);
 298   zone_names = (char *) types + num_types * sizeof (struct ttinfo);
 299   leaps = (struct leap *) ((char *) transitions + leaps_idx);
 300   if (sizeof (time_t) == 8 && trans_width == 8)
 301     tzspec = (char *) leaps + num_leaps * sizeof (struct leap) + extra;
 302   else
 303     tzspec = NULL;
 304   if (extra > 0)
 305     *extrap = (char *) &leaps[num_leaps];
 306
 307   if (sizeof (time_t) == 4 || __builtin_expect (trans_width == 8, 1))
 308     {
 309       if (__builtin_expect (fread_unlocked (transitions, trans_width + 1,
 310                                             num_transitions, f)
 311                             != num_transitions, 0))
 312         goto lose;
 313     }
 314   else
 315     {
 316       if (__builtin_expect (fread_unlocked (transitions, 4, num_transitions, f)
 317                             != num_transitions, 0)
 318           || __builtin_expect (fread_unlocked (type_idxs, 1, num_transitions,
 319                                                f) != num_transitions, 0))
 320         goto lose;
 321     }
 322
 323   /* Check for bogus indices in the data file, so we can hereafter
 324      safely use type_idxs[T] as indices into `types' and never crash.  */
 325   for (i = 0; i < num_transitions; ++i)
 326     if (__builtin_expect (type_idxs[i] >= num_types, 0))
 327       goto lose;
 328
 329   if ((BYTE_ORDER != BIG_ENDIAN && (sizeof (time_t) == 4 || trans_width == 4))
 330       || (BYTE_ORDER == BIG_ENDIAN && sizeof (time_t) == 8
 331           && trans_width == 4))
 332     {
 333       /* Decode the transition times, stored as 4-byte integers in
 334          network (big-endian) byte order.  We work from the end of
 335          the array so as not to clobber the next element to be
 336          processed when sizeof (time_t) > 4.  */
 337       i = num_transitions;
 338       while (i-- > 0)
 339         transitions[i] = decode ((char *) transitions + i * 4);
 340     }
 341   else if (BYTE_ORDER != BIG_ENDIAN && sizeof (time_t) == 8)
 342     {
 343       /* Decode the transition times, stored as 8-byte integers in
 344          network (big-endian) byte order.  */
 345       for (i = 0; i < num_transitions; ++i)
 346         transitions[i] = decode64 ((char *) transitions + i * 8);
 347     }
 348
 349   for (i = 0; i < num_types; ++i)
 350     {
 351       unsigned char x[4];
 352       int c;
 353       if (__builtin_expect (fread_unlocked (x, 1, sizeof (x), f) != sizeof (x),
 354                             0))
 355         goto lose;
 356       c = getc_unlocked (f);
 357       if (__builtin_expect ((unsigned int) c > 1u, 0))
 358         goto lose;
 359       types[i].isdst = c;
 360       c = getc_unlocked (f);
 361       if (__builtin_expect ((size_t) c > chars, 0))
 362         /* Bogus index in data file.  */
 363         goto lose;
 364       types[i].idx = c;
 365       types[i].offset = (long int) decode (x);
 366     }
 367
 368   if (__builtin_expect (fread_unlocked (zone_names, 1, chars, f) != chars, 0))
 369     goto lose;
 370
 371   for (i = 0; i < num_leaps; ++i)
 372     {
 373       unsigned char x[8];
 374       if (__builtin_expect (fread_unlocked (x, 1, trans_width, f)
 375                             != trans_width, 0))
 376         goto lose;
 377       if (sizeof (time_t) == 4 || trans_width == 4)
 378         leaps[i].transition = (time_t) decode (x);
 379       else
 380         leaps[i].transition = (time_t) decode64 (x);
 381
 382       if (__builtin_expect (fread_unlocked (x, 1, 4, f) != 4, 0))
 383         goto lose;
 384       leaps[i].change = (long int) decode (x);
 385     }
 386
 387   for (i = 0; i < num_isstd; ++i)
 388     {
 389       int c = getc_unlocked (f);
 390       if (__builtin_expect (c == EOF, 0))
 391         goto lose;
 392       types[i].isstd = c != 0;
 393     }
 394   while (i < num_types)
 395     types[i++].isstd = 0;
 396
 397   for (i = 0; i < num_isgmt; ++i)
 398     {
 399       int c = getc_unlocked (f);
 400       if (__builtin_expect (c == EOF, 0))
 401         goto lose;
 402       types[i].isgmt = c != 0;
 403     }
 404   while (i < num_types)
 405     types[i++].isgmt = 0;
 406
 407   /* Read the POSIX TZ-style information if possible.  */
 408   if (sizeof (time_t) == 8 && tzspec != NULL)
 409     {
 410       /* Skip over the newline first.  */
 411       if (getc_unlocked (f) != '\n'
 412           || (fread_unlocked (tzspec, 1, tzspec_len - 1, f)
 413               != tzspec_len - 1))
 414         tzspec = NULL;
 415       else
 416         tzspec[tzspec_len - 1] = '\0';
 417     }
 418   else if (sizeof (time_t) == 4 && tzhead.tzh_version[0] != '\0')
 419     {
 420       /* Get the TZ string.  */
 421       if (__builtin_expect (fread_unlocked ((void *) &tzhead, sizeof (tzhead),
 422                                             1, f) != 1, 0)
 423           || (memcmp (tzhead.tzh_magic, TZ_MAGIC, sizeof (tzhead.tzh_magic))
 424               != 0))
 425         goto lose;
 426
 427       size_t num_transitions2 = (size_t) decode (tzhead.tzh_timecnt);
 428       size_t num_types2 = (size_t) decode (tzhead.tzh_typecnt);
 429       size_t chars2 = (size_t) decode (tzhead.tzh_charcnt);
 430       size_t num_leaps2 = (size_t) decode (tzhead.tzh_leapcnt);
 431       size_t num_isstd2 = (size_t) decode (tzhead.tzh_ttisstdcnt);
 432       size_t num_isgmt2 = (size_t) decode (tzhead.tzh_ttisgmtcnt);
 433
 434       /* Position the stream before the second header.  */
 435       size_t to_skip = (num_transitions2 * (8 + 1)
 436                         + num_types2 * 6
 437                         + chars2
 438                         + num_leaps2 * 12
 439                         + num_isstd2
 440                         + num_isgmt2);
 441       off_t off;
 442       if (fseek (f, to_skip, SEEK_CUR) != 0
 443           || (off = ftello (f)) < 0
 444           || st.st_size < off + 2)
 445         goto lose;
 446
 447       tzspec_len = st.st_size - off - 1;
 448       char *tzstr = alloca (tzspec_len);
 449       if (getc_unlocked (f) != '\n'
 450           || (fread_unlocked (tzstr, 1, tzspec_len - 1, f) != tzspec_len - 1))
 451         goto lose;
 452       tzstr[tzspec_len - 1] = '\0';
 453       tzspec = __tzstring (tzstr);
 454     }
 455
 456   /* Don't use an empty TZ string.  */
 457   if (tzspec != NULL && tzspec[0] == '\0')
 458     tzspec = NULL;
 459
 460   fclose (f);
 461
 462   /* First "register" all timezone names.  */
 463   for (i = 0; i < num_types; ++i)
 464     (void) __tzstring (&zone_names[types[i].idx]);
 465
 466   /* Find the standard and daylight time offsets used by the rule file.
 467      We choose the offsets in the types of each flavor that are
 468      transitioned to earliest in time.  */
 469   __tzname[0] = NULL;
 470   __tzname[1] = NULL;
 471   for (i = num_transitions; i > 0; )
 472     {
 473       int type = type_idxs[--i];
 474       int dst = types[type].isdst;
 475
 476       if (__tzname[dst] == NULL)
 477         {
 478           int idx = types[type].idx;
 479
 480           __tzname[dst] = __tzstring (&zone_names[idx]);
 481
 482           if (__tzname[1 - dst] != NULL)
 483             break;
 484         }
 485     }
 486   if (__tzname[0] == NULL)
 487     {
 488       /* This should only happen if there are no transition rules.
 489          In this case there should be only one single type.  */
 490       assert (num_types == 1);
 491       __tzname[0] = __tzstring (zone_names);
 492     }
 493   if (__tzname[1] == NULL)
 494     __tzname[1] = __tzname[0];
 495
 496   compute_tzname_max (chars);
 497
 498   if (num_transitions == 0)
 499     /* Use the first rule (which should also be the only one).  */
 500     rule_stdoff = rule_dstoff = types[0].offset;
 501   else
 502     {
 503       int stdoff_set = 0, dstoff_set = 0;
 504       rule_stdoff = rule_dstoff = 0;
 505       i = num_transitions - 1;
 506       do
 507         {
 508           if (!stdoff_set && !types[type_idxs[i]].isdst)
 509             {
 510               stdoff_set = 1;
 511               rule_stdoff = types[type_idxs[i]].offset;
 512             }
 513           else if (!dstoff_set && types[type_idxs[i]].isdst)
 514             {
 515               dstoff_set = 1;
 516               rule_dstoff = types[type_idxs[i]].offset;
 517             }
 518           if (stdoff_set && dstoff_set)
 519             break;
 520         }
 521       while (i-- > 0);
 522
 523       if (!dstoff_set)
 524         rule_dstoff = rule_stdoff;
 525     }
 526
 527   __daylight = rule_stdoff != rule_dstoff;
 528   __timezone = -rule_stdoff;
 529
 530   __use_tzfile = 1;
 531   return;
 532
 533  lose:
 534   fclose (f);
 535  ret_free_transitions:
 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   compute_tzname_max (stdlen + dstlen);
 626 }
 627 \f
 628 void
 629 __tzfile_compute (time_t timer, int use_localtime,
 630                   long int *leap_correct, int *leap_hit,
 631                   struct tm *tp)
 632 {
 633   register size_t i;
 634
 635   if (use_localtime)
 636     {
 637       __tzname[0] = NULL;
 638       __tzname[1] = NULL;
 639
 640       if (__builtin_expect (num_transitions == 0 || timer < transitions[0], 0))
 641         {
 642           /* TIMER is before any transition (or there are no transitions).
 643              Choose the first non-DST type
 644              (or the first if they're all DST types).  */
 645           i = 0;
 646           while (i < num_types && types[i].isdst)
 647             {
 648               if (__tzname[1] == NULL)
 649                 __tzname[1] = __tzstring (&zone_names[types[i].idx]);
 650
 651               ++i;
 652             }
 653
 654           if (i == num_types)
 655             i = 0;
 656           __tzname[0] = __tzstring (&zone_names[types[i].idx]);
 657           if (__tzname[1] == NULL)
 658             {
 659               size_t j = i;
 660               while (j < num_types)
 661                 if (types[j].isdst)
 662                   {
 663                     __tzname[1] = __tzstring (&zone_names[types[j].idx]);
 664                     break;
 665                   }
 666                 else
 667                   ++j;
 668             }
 669         }
 670       else if (__builtin_expect (timer >= transitions[num_transitions - 1], 0))
 671         {
 672           if (__builtin_expect (tzspec == NULL, 0))
 673             {
 674             use_last:
 675               i = num_transitions;
 676               goto found;
 677             }
 678
 679           /* Parse the POSIX TZ-style string.  */
 680           __tzset_parse_tz (tzspec);
 681
 682           /* Convert to broken down structure.  If this fails do not
 683              use the string.  */
 684           if (__builtin_expect (! __offtime (&timer, 0, tp), 0))
 685             goto use_last;
 686
 687           /* Use the rules from the TZ string to compute the change.  */
 688           __tz_compute (timer, tp, 1);
 689
 690           /* If tzspec comes from posixrules loaded by __tzfile_default,
 691              override the STD and DST zone names with the ones user
 692              requested in TZ envvar.  */
 693           if (__builtin_expect (zone_names == (char *) &leaps[num_leaps], 0))
 694             {
 695               assert (num_types == 2);
 696               __tzname[0] = __tzstring (zone_names);
 697               __tzname[1] = __tzstring (&zone_names[strlen (zone_names) + 1]);
 698             }
 699
 700           goto leap;
 701         }
 702       else
 703         {
 704           /* Find the first transition after TIMER, and
 705              then pick the type of the transition before it.  */
 706           size_t lo = 0;
 707           size_t hi = num_transitions - 1;
 708           /* Assume that DST is changing twice a year and guess initial
 709              search spot from it.
 710              Half of a gregorian year has on average 365.2425 * 86400 / 2
 711              = 15778476 seconds.  */
 712           i = (transitions[num_transitions - 1] - timer) / 15778476;
 713           if (i < num_transitions)
 714             {
 715               i = num_transitions - 1 - i;
 716               if (timer < transitions[i])
 717                 {
 718                   if (i < 10 || timer >= transitions[i - 10])
 719                     {
 720                       /* Linear search.  */
 721                       while (timer < transitions[i - 1])
 722                         --i;
 723                       goto found;
 724                     }
 725                   hi = i - 10;
 726                 }
 727               else
 728                 {
 729                   if (i + 10 >= num_transitions || timer < transitions[i + 10])
 730                     {
 731                       /* Linear search.  */
 732                       while (timer >= transitions[i])
 733                         ++i;
 734                       goto found;
 735                     }
 736                   lo = i + 10;
 737                 }
 738             }
 739
 740           /* Binary search.  */
 741           /* assert (timer >= transitions[lo] && timer < transitions[hi]); */
 742           while (lo + 1 < hi)
 743             {
 744               i = (lo + hi) / 2;
 745               if (timer < transitions[i])
 746                 hi = i;
 747               else
 748                 lo = i;
 749             }
 750           i = hi;
 751
 752         found:
 753           /* assert (timer >= transitions[i - 1]
 754              && (i == num_transitions || timer < transitions[i])); */
 755           __tzname[types[type_idxs[i - 1]].isdst]
 756             = __tzstring (&zone_names[types[type_idxs[i - 1]].idx]);
 757           size_t j = i;
 758           while (j < num_transitions)
 759             {
 760               int type = type_idxs[j];
 761               int dst = types[type].isdst;
 762               int idx = types[type].idx;
 763
 764               if (__tzname[dst] == NULL)
 765                 {
 766                   __tzname[dst] = __tzstring (&zone_names[idx]);
 767
 768                   if (__tzname[1 - dst] != NULL)
 769                     break;
 770                 }
 771
 772               ++j;
 773             }
 774
 775           if (__builtin_expect (__tzname[0] == NULL, 0))
 776             __tzname[0] = __tzname[1];
 777
 778           i = type_idxs[i - 1];
 779         }
 780
 781       struct ttinfo *info = &types[i];
 782       __daylight = rule_stdoff != rule_dstoff;
 783       __timezone = -rule_stdoff;
 784
 785       if (__tzname[0] == NULL)
 786         {
 787           /* This should only happen if there are no transition rules.
 788              In this case there should be only one single type.  */
 789           assert (num_types == 1);
 790           __tzname[0] = __tzstring (zone_names);
 791         }
 792       if (__tzname[1] == NULL)
 793         /* There is no daylight saving time.  */
 794         __tzname[1] = __tzname[0];
 795       tp->tm_isdst = info->isdst;
 796       assert (strcmp (&zone_names[info->idx], __tzname[tp->tm_isdst]) == 0);
 797       tp->tm_zone = __tzname[tp->tm_isdst];
 798       tp->tm_gmtoff = info->offset;
 799     }
 800
 801  leap:
 802   *leap_correct = 0L;
 803   *leap_hit = 0;
 804
 805   /* Find the last leap second correction transition time before TIMER.  */
 806   i = num_leaps;
 807   do
 808     if (i-- == 0)
 809       return;
 810   while (timer < leaps[i].transition);
 811
 812   /* Apply its correction.  */
 813   *leap_correct = leaps[i].change;
 814
 815   if (timer == leaps[i].transition && /* Exactly at the transition time.  */
 816       ((i == 0 && leaps[i].change > 0) ||
 817        leaps[i].change > leaps[i - 1].change))
 818     {
 819       *leap_hit = 1;
 820       while (i > 0
 821              && leaps[i].transition == leaps[i - 1].transition + 1
 822              && leaps[i].change == leaps[i - 1].change + 1)
 823         {
 824           ++*leap_hit;
 825           --i;
 826         }
 827     }
 828 }
 829 \f
 830 static void
 831 internal_function
 832 compute_tzname_max (size_t chars)
 833 {
 834   const char *p;
 835
 836   p = zone_names;
 837   do
 838     {
 839       const char *start = p;
 840       while (*p != '\0')
 841         ++p;
 842       if ((size_t) (p - start) > __tzname_cur_max)
 843         __tzname_cur_max = p - start;
 844     }
 845   while (++p < &zone_names[chars]);
 846 }