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