time/tzfile.c

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