time/tzfile.c

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