[thirdparty/systemd.git] / src / shared / time-dst.c

/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/

/***
  This file is part of systemd.

  Timezone file reading code from glibc 2.16.

  Copyright (C) 1991-2012 Free Software Foundation, Inc.
  Copyright 2012 Kay Sievers

  systemd is free software; you can redistribute it and/or modify it
  under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation; either version 2.1 of the License, or
  (at your option) any later version.

  systemd is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with systemd; If not, see <http://www.gnu.org/licenses/>.
***/
#include <ctype.h>
#include <errno.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <endian.h>
#include <byteswap.h>
#include <assert.h>
#include <limits.h>
#include <unistd.h>
#include <stdint.h>
#include <stdbool.h>
#include <sys/stat.h>

#include "time-dst.h"
#include "util.h"

/*
 * If tzh_version is '2' or greater, the above is followed by a second instance
 * of tzhead and a second instance of the data in which each coded transition
 * time uses 8 rather than 4 chars, then a POSIX-TZ-environment-variable-style
 * string for use in handling instants after the last transition time stored in
 * the file * (with nothing between the newlines if there is no POSIX
 * representation for such instants).
 */
#define TZ_MAGIC                "TZif"
struct tzhead {
        char tzh_magic[4];      /* TZ_MAGIC */
        char tzh_version[1];    /* '\0' or '2' as of 2005 */
        char tzh_reserved[15];  /* reserved--must be zero */
        char tzh_ttisgmtcnt[4]; /* coded number of trans. time flags */
        char tzh_ttisstdcnt[4]; /* coded number of trans. time flags */
        char tzh_leapcnt[4];    /* coded number of leap seconds */
        char tzh_timecnt[4];    /* coded number of transition times */
        char tzh_typecnt[4];    /* coded number of local time types */
        char tzh_charcnt[4];    /* coded number of abbr. chars */
};

struct ttinfo {
        long int offset;        /* Seconds east of GMT.  */
        unsigned char isdst;    /* Used to set tm_isdst.  */
        unsigned char idx;      /* Index into `zone_names'.  */
        unsigned char isstd;    /* Transition times are in standard time.  */
        unsigned char isgmt;    /* Transition times are in GMT.  */
};

struct leap {
        time_t transition;      /* Time the transition takes effect.  */
        long int change;        /* Seconds of correction to apply.  */
};

static inline int decode(const void *ptr) {
        return be32toh(*(int *)ptr);
}

static inline int64_t decode64(const void *ptr) {
        return be64toh(*(int64_t *)ptr);
}

int time_get_dst(time_t date, const char *tzfile,
                 time_t *switch_cur, char **zone_cur, bool *dst_cur,
                 time_t *switch_next, int *delta_next, char **zone_next, bool *dst_next) {
        unsigned char *type_idxs = 0;
        size_t num_types = 0;
        struct ttinfo *types = NULL;
        char *zone_names = NULL;
        struct stat st;
        size_t num_isstd, num_isgmt;
        struct tzhead tzhead;
        size_t chars;
        size_t i;
        size_t total_size;
        size_t types_idx;
        int trans_width = 4;
        size_t tzspec_len;
        size_t num_leaps;
        size_t lo, hi;
        size_t num_transitions = 0;
        _cleanup_free_ time_t *transitions = NULL;
        _cleanup_fclose_ FILE *f;

        f = fopen(tzfile, "re");
        if (f == NULL)
                return -errno;

        if (fstat(fileno(f), &st) < 0)
                return -errno;

read_again:
        if (fread((void *)&tzhead, sizeof(tzhead), 1, f) != 1 ||
            memcmp(tzhead.tzh_magic, TZ_MAGIC, sizeof(tzhead.tzh_magic)) != 0)
                return -EINVAL;

        num_transitions = (size_t)decode(tzhead.tzh_timecnt);
        num_types = (size_t)decode(tzhead.tzh_typecnt);
        chars = (size_t)decode(tzhead.tzh_charcnt);
        num_leaps = (size_t)decode(tzhead.tzh_leapcnt);
        num_isstd = (size_t)decode(tzhead.tzh_ttisstdcnt);
        num_isgmt = (size_t)decode(tzhead.tzh_ttisgmtcnt);

        /* For platforms with 64-bit time_t we use the new format if available.  */
        if (sizeof(time_t) == 8 && trans_width == 4 && tzhead.tzh_version[0] != '\0') {
                size_t to_skip;

                /* We use the 8-byte format.  */
                trans_width = 8;

                /* Position the stream before the second header.  */
                to_skip = (num_transitions * (4 + 1)
                           + num_types * 6
                           + chars
                           + num_leaps * 8 + num_isstd + num_isgmt);
                if (fseek(f, to_skip, SEEK_CUR) != 0)
                        return -EINVAL;

                goto read_again;
        }

        if (num_transitions > ((SIZE_MAX - (__alignof__(struct ttinfo) - 1)) / (sizeof(time_t) + 1)))
                 return -EINVAL;

        total_size = num_transitions * (sizeof(time_t) + 1);
        total_size = ((total_size + __alignof__(struct ttinfo) - 1) & ~(__alignof__(struct ttinfo) - 1));
        types_idx = total_size;
        if (num_leaps > (SIZE_MAX - total_size) / sizeof(struct ttinfo))
                return -EINVAL;

        total_size += num_types * sizeof(struct ttinfo);
        if (chars > SIZE_MAX - total_size)
                return -EINVAL;

        total_size += chars;
        if (__alignof__(struct leap) - 1 > SIZE_MAX - total_size)
                 return -EINVAL;

        total_size = ((total_size + __alignof__(struct leap) - 1) & ~(__alignof__(struct leap) - 1));
        if (num_leaps > (SIZE_MAX - total_size) / sizeof(struct leap))
                return -EINVAL;

        total_size += num_leaps * sizeof(struct leap);
        tzspec_len = 0;
        if (sizeof(time_t) == 8 && trans_width == 8) {
                off_t rem = st.st_size - ftello(f);

                if (rem < 0 || (size_t) rem < (num_transitions * (8 + 1) + num_types * 6 + chars))
                        return -EINVAL;
                tzspec_len = (size_t) rem - (num_transitions * (8 + 1) + num_types * 6 + chars);
                if (num_leaps > SIZE_MAX / 12 || tzspec_len < num_leaps * 12)
                        return -EINVAL;
                tzspec_len -= num_leaps * 12;
                if (tzspec_len < num_isstd)
                        return -EINVAL;
                tzspec_len -= num_isstd;
                if (tzspec_len == 0 || tzspec_len - 1 < num_isgmt)
                        return -EINVAL;
                tzspec_len -= num_isgmt + 1;
                if (SIZE_MAX - total_size < tzspec_len)
                        return -EINVAL;
        }

        transitions = malloc0(total_size + tzspec_len);
        if (transitions == NULL)
                return -EINVAL;

        type_idxs = (unsigned char *)transitions + (num_transitions
                                                    * sizeof(time_t));
        types = (struct ttinfo *)((char *)transitions + types_idx);
        zone_names = (char *)types + num_types * sizeof(struct ttinfo);

        if (sizeof(time_t) == 4 || trans_width == 8) {
                if (fread(transitions, trans_width + 1, num_transitions, f) != num_transitions)
                        return -EINVAL;
        } else {
                if (fread(transitions, 4, num_transitions, f) != num_transitions ||
                    fread(type_idxs, 1, num_transitions, f) != num_transitions)
                        return -EINVAL;
        }

        /* Check for bogus indices in the data file, so we can hereafter
           safely use type_idxs[T] as indices into `types' and never crash.  */
        for (i = 0; i < num_transitions; ++i)
                if (type_idxs[i] >= num_types)
                        return -EINVAL;

        if (__BYTE_ORDER == __BIG_ENDIAN ? sizeof(time_t) == 8 && trans_width == 4
                                         : sizeof(time_t) == 4 || trans_width == 4) {
                /* Decode the transition times, stored as 4-byte integers in
                   network (big-endian) byte order.  We work from the end of
                   the array so as not to clobber the next element to be
                   processed when sizeof (time_t) > 4.  */
                i = num_transitions;
                while (i-- > 0)
                        transitions[i] = decode((char *)transitions + i * 4);
        } else if (__BYTE_ORDER != __BIG_ENDIAN && sizeof(time_t) == 8) {
                /* Decode the transition times, stored as 8-byte integers in
                   network (big-endian) byte order.  */
                for (i = 0; i < num_transitions; ++i)
                        transitions[i] = decode64((char *)transitions + i * 8);
        }

        for (i = 0; i < num_types; ++i) {
                unsigned char x[4];
                int c;

                if (fread(x, 1, sizeof(x), f) != sizeof(x))
                        return -EINVAL;
                c = getc(f);
                if ((unsigned int)c > 1u)
                        return -EINVAL;
                types[i].isdst = c;
                c = getc(f);
                if ((size_t) c > chars)
                        /* Bogus index in data file.  */
                        return -EINVAL;
                types[i].idx = c;
                types[i].offset = (long int)decode(x);
        }

        if (fread(zone_names, 1, chars, f) != chars)
                return -EINVAL;

        for (i = 0; i < num_isstd; ++i) {
                int c = getc(f);
                if (c == EOF)
                        return -EINVAL;
                types[i].isstd = c != 0;
        }

        while (i < num_types)
                types[i++].isstd = 0;

        for (i = 0; i < num_isgmt; ++i) {
                int c = getc(f);
                if (c == EOF)
                        return -EINVAL;
                types[i].isgmt = c != 0;
        }

        while (i < num_types)
                types[i++].isgmt = 0;

        if (num_transitions == 0)
               return -EINVAL;

        if (date < transitions[0] || date >= transitions[num_transitions - 1])
               return -EINVAL;

        /* Find the first transition after TIMER, and
           then pick the type of the transition before it.  */
        lo = 0;
        hi = num_transitions - 1;

        /* Assume that DST is changing twice a year and guess initial
           search spot from it.
           Half of a gregorian year has on average 365.2425 * 86400 / 2
           = 15778476 seconds.  */
        i = (transitions[num_transitions - 1] - date) / 15778476;
        if (i < num_transitions) {
                i = num_transitions - 1 - i;
                if (date < transitions[i]) {
                        if (i < 10 || date >= transitions[i - 10]) {
                                /* Linear search.  */
                                while (date < transitions[i - 1])
                                        i--;
                                goto found;
                        }
                        hi = i - 10;
                } else {
                        if (i + 10 >= num_transitions || date < transitions[i + 10]) {
                                /* Linear search.  */
                                while (date >= transitions[i])
                                        i++;
                                goto found;
                        }
                        lo = i + 10;
                }
        }

        /* Binary search. */
        while (lo + 1 < hi) {
                i = (lo + hi) / 2;
                if (date < transitions[i])
                        hi = i;
                else
                        lo = i;
        }
        i = hi;

found:
        if (switch_cur)
                *switch_cur = transitions[i-1];
        if (zone_cur)
                *zone_cur = strdup(&zone_names[types[type_idxs[i - 1]].idx]);
        if (dst_cur)
                *dst_cur = types[type_idxs[i-1]].isdst;

        if (switch_next)
                *switch_next = transitions[i];
        if (delta_next)
                *delta_next = (types[type_idxs[i]].offset - types[type_idxs[i-1]].offset) / 60;
        if (zone_next)
                *zone_next = strdup(&zone_names[types[type_idxs[i]].idx]);
        if (dst_next)
                *dst_next = types[type_idxs[i]].isdst;

        return 0;
}
Commit	Line	Data
b7f1542c KS	1	/-- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil --/
	2
	3	/***
	4	This file is part of systemd.
	5
	6	Timezone file reading code from glibc 2.16.
	7
	8	Copyright (C) 1991-2012 Free Software Foundation, Inc.
	9	Copyright 2012 Kay Sievers
	10
	11	systemd is free software; you can redistribute it and/or modify it
	12	under the terms of the GNU Lesser General Public License as published by
	13	the Free Software Foundation; either version 2.1 of the License, or
	14	(at your option) any later version.
	15
	16	systemd is distributed in the hope that it will be useful, but
	17	WITHOUT ANY WARRANTY; without even the implied warranty of
	18	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	19	Lesser General Public License for more details.
	20
	21	You should have received a copy of the GNU Lesser General Public License
	22	along with systemd; If not, see <http://www.gnu.org/licenses/>.
	23	***/
	24	#include <ctype.h>
	25	#include <errno.h>
	26	#include <stddef.h>
	27	#include <stdio.h>
	28	#include <stdlib.h>
	29	#include <string.h>
	30	#include <time.h>
	31	#include <endian.h>
	32	#include <byteswap.h>
	33	#include <assert.h>
	34	#include <limits.h>
	35	#include <unistd.h>
	36	#include <stdint.h>
	37	#include <stdbool.h>
	38	#include <sys/stat.h>
	39
	40	#include "time-dst.h"
11f22867	41	#include "util.h"
b7f1542c KS	42
	43	/*
	44	* If tzh_version is '2' or greater, the above is followed by a second instance
	45	* of tzhead and a second instance of the data in which each coded transition
	46	* time uses 8 rather than 4 chars, then a POSIX-TZ-environment-variable-style
	47	* string for use in handling instants after the last transition time stored in
	48	* the file * (with nothing between the newlines if there is no POSIX
	49	* representation for such instants).
	50	*/
	51	#define TZ_MAGIC "TZif"
	52	struct tzhead {
	53	char tzh_magic[4]; /* TZ_MAGIC */
	54	char tzh_version[1]; /* '\0' or '2' as of 2005 */
	55	char tzh_reserved[15]; /* reserved--must be zero */
	56	char tzh_ttisgmtcnt[4]; /* coded number of trans. time flags */
	57	char tzh_ttisstdcnt[4]; /* coded number of trans. time flags */
	58	char tzh_leapcnt[4]; /* coded number of leap seconds */
	59	char tzh_timecnt[4]; /* coded number of transition times */
	60	char tzh_typecnt[4]; /* coded number of local time types */
	61	char tzh_charcnt[4]; /* coded number of abbr. chars */
	62	};
	63
	64	struct ttinfo {
	65	long int offset; /* Seconds east of GMT. */
	66	unsigned char isdst; /* Used to set tm_isdst. */
	67	unsigned char idx; /* Index into `zone_names'. */
	68	unsigned char isstd; /* Transition times are in standard time. */
	69	unsigned char isgmt; /* Transition times are in GMT. */
	70	};
	71
	72	struct leap {
	73	time_t transition; /* Time the transition takes effect. */
	74	long int change; /* Seconds of correction to apply. */
	75	};
	76
	77	static inline int decode(const void *ptr) {
	78	return be32toh((int )ptr);
	79	}
	80
	81	static inline int64_t decode64(const void *ptr) {
	82	return be64toh((int64_t )ptr);
	83	}
	84
	85	int time_get_dst(time_t date, const char *tzfile,
	86	time_t switch_cur, char zone_cur, bool dst_cur,
2311eb2f	87	time_t switch_next, int delta_next, char *zone_next, bool dst_next) {
b7f1542c KS	88	unsigned char *type_idxs = 0;
	89	size_t num_types = 0;
	90	struct ttinfo *types = NULL;
	91	char *zone_names = NULL;
	92	struct stat st;
	93	size_t num_isstd, num_isgmt;
b7f1542c KS	94	struct tzhead tzhead;
	95	size_t chars;
	96	size_t i;
	97	size_t total_size;
	98	size_t types_idx;
	99	int trans_width = 4;
	100	size_t tzspec_len;
	101	size_t num_leaps;
	102	size_t lo, hi;
11f22867 ZJS	103	size_t num_transitions = 0;
	104	_cleanup_free_ time_t *transitions = NULL;
	105	_cleanup_fclose_ FILE *f;
b7f1542c KS	106
	107	f = fopen(tzfile, "re");
	108	if (f == NULL)
	109	return -errno;
	110
11f22867 ZJS	111	if (fstat(fileno(f), &st) < 0)
11f22867 ZJS	112	return -errno;
b7f1542c KS	113
	114	read_again:
	115	if (fread((void *)&tzhead, sizeof(tzhead), 1, f) != 1 \|\|
	116	memcmp(tzhead.tzh_magic, TZ_MAGIC, sizeof(tzhead.tzh_magic)) != 0)
11f22867	117	return -EINVAL;
b7f1542c KS	118
	119	num_transitions = (size_t)decode(tzhead.tzh_timecnt);
	120	num_types = (size_t)decode(tzhead.tzh_typecnt);
	121	chars = (size_t)decode(tzhead.tzh_charcnt);
	122	num_leaps = (size_t)decode(tzhead.tzh_leapcnt);
	123	num_isstd = (size_t)decode(tzhead.tzh_ttisstdcnt);
	124	num_isgmt = (size_t)decode(tzhead.tzh_ttisgmtcnt);
	125
	126	/* For platforms with 64-bit time_t we use the new format if available. */
	127	if (sizeof(time_t) == 8 && trans_width == 4 && tzhead.tzh_version[0] != '\0') {
	128	size_t to_skip;
	129
	130	/* We use the 8-byte format. */
	131	trans_width = 8;
	132
	133	/* Position the stream before the second header. */
	134	to_skip = (num_transitions * (4 + 1)
	135	+ num_types * 6
	136	+ chars
	137	+ num_leaps * 8 + num_isstd + num_isgmt);
	138	if (fseek(f, to_skip, SEEK_CUR) != 0)
11f22867	139	return -EINVAL;
b7f1542c KS	140
	141	goto read_again;
	142	}
	143
	144	if (num_transitions > ((SIZE_MAX - (__alignof__(struct ttinfo) - 1)) / (sizeof(time_t) + 1)))
11f22867	145	return -EINVAL;
b7f1542c KS	146
	147	total_size = num_transitions * (sizeof(time_t) + 1);
	148	total_size = ((total_size + __alignof__(struct ttinfo) - 1) & ~(__alignof__(struct ttinfo) - 1));
	149	types_idx = total_size;
	150	if (num_leaps > (SIZE_MAX - total_size) / sizeof(struct ttinfo))
11f22867	151	return -EINVAL;
b7f1542c KS	152
	153	total_size += num_types * sizeof(struct ttinfo);
	154	if (chars > SIZE_MAX - total_size)
11f22867	155	return -EINVAL;
b7f1542c KS	156
	157	total_size += chars;
	158	if (__alignof__(struct leap) - 1 > SIZE_MAX - total_size)
11f22867	159	return -EINVAL;
b7f1542c KS	160
	161	total_size = ((total_size + __alignof__(struct leap) - 1) & ~(__alignof__(struct leap) - 1));
	162	if (num_leaps > (SIZE_MAX - total_size) / sizeof(struct leap))
11f22867	163	return -EINVAL;
b7f1542c KS	164
	165	total_size += num_leaps * sizeof(struct leap);
	166	tzspec_len = 0;
	167	if (sizeof(time_t) == 8 && trans_width == 8) {
	168	off_t rem = st.st_size - ftello(f);
	169
	170	if (rem < 0 \|\| (size_t) rem < (num_transitions * (8 + 1) + num_types * 6 + chars))
11f22867	171	return -EINVAL;
b7f1542c KS	172	tzspec_len = (size_t) rem - (num_transitions * (8 + 1) + num_types * 6 + chars);
b7f1542c KS	173	if (num_leaps > SIZE_MAX / 12 \|\| tzspec_len < num_leaps * 12)
11f22867	174	return -EINVAL;
b7f1542c KS	175	tzspec_len -= num_leaps * 12;
b7f1542c KS	176	if (tzspec_len < num_isstd)
11f22867	177	return -EINVAL;
b7f1542c KS	178	tzspec_len -= num_isstd;
b7f1542c KS	179	if (tzspec_len == 0 \|\| tzspec_len - 1 < num_isgmt)
11f22867	180	return -EINVAL;
b7f1542c KS	181	tzspec_len -= num_isgmt + 1;
b7f1542c KS	182	if (SIZE_MAX - total_size < tzspec_len)
11f22867	183	return -EINVAL;
b7f1542c KS	184	}
b7f1542c KS	185
955d98c9	186	transitions = malloc0(total_size + tzspec_len);
b7f1542c	187	if (transitions == NULL)
11f22867	188	return -EINVAL;
b7f1542c KS	189
	190	type_idxs = (unsigned char *)transitions + (num_transitions
	191	* sizeof(time_t));
	192	types = (struct ttinfo )((char )transitions + types_idx);
	193	zone_names = (char )types + num_types sizeof(struct ttinfo);
	194
	195	if (sizeof(time_t) == 4 \|\| trans_width == 8) {
	196	if (fread(transitions, trans_width + 1, num_transitions, f) != num_transitions)
11f22867	197	return -EINVAL;
b7f1542c KS	198	} else {
	199	if (fread(transitions, 4, num_transitions, f) != num_transitions \|\|
	200	fread(type_idxs, 1, num_transitions, f) != num_transitions)
11f22867	201	return -EINVAL;
b7f1542c KS	202	}
	203
	204	/* Check for bogus indices in the data file, so we can hereafter
	205	safely use type_idxs[T] as indices into `types' and never crash. */
	206	for (i = 0; i < num_transitions; ++i)
	207	if (type_idxs[i] >= num_types)
11f22867	208	return -EINVAL;
b7f1542c	209
4f4b92ba LP	210	if (__BYTE_ORDER == __BIG_ENDIAN ? sizeof(time_t) == 8 && trans_width == 4
4f4b92ba LP	211	: sizeof(time_t) == 4 \|\| trans_width == 4) {
b7f1542c KS	212	/* Decode the transition times, stored as 4-byte integers in
	213	network (big-endian) byte order. We work from the end of
	214	the array so as not to clobber the next element to be
	215	processed when sizeof (time_t) > 4. */
	216	i = num_transitions;
	217	while (i-- > 0)
	218	transitions[i] = decode((char )transitions + i 4);
4f4b92ba	219	} else if (__BYTE_ORDER != __BIG_ENDIAN && sizeof(time_t) == 8) {
b7f1542c KS	220	/* Decode the transition times, stored as 8-byte integers in
	221	network (big-endian) byte order. */
	222	for (i = 0; i < num_transitions; ++i)
	223	transitions[i] = decode64((char )transitions + i 8);
	224	}
	225
	226	for (i = 0; i < num_types; ++i) {
	227	unsigned char x[4];
	228	int c;
	229
	230	if (fread(x, 1, sizeof(x), f) != sizeof(x))
11f22867	231	return -EINVAL;
b7f1542c KS	232	c = getc(f);
b7f1542c KS	233	if ((unsigned int)c > 1u)
11f22867	234	return -EINVAL;
b7f1542c KS	235	types[i].isdst = c;
	236	c = getc(f);
	237	if ((size_t) c > chars)
	238	/* Bogus index in data file. */
11f22867	239	return -EINVAL;
b7f1542c KS	240	types[i].idx = c;
	241	types[i].offset = (long int)decode(x);
	242	}
	243
	244	if (fread(zone_names, 1, chars, f) != chars)
11f22867	245	return -EINVAL;
b7f1542c KS	246
	247	for (i = 0; i < num_isstd; ++i) {
	248	int c = getc(f);
	249	if (c == EOF)
11f22867	250	return -EINVAL;
b7f1542c KS	251	types[i].isstd = c != 0;
	252	}
	253
	254	while (i < num_types)
	255	types[i++].isstd = 0;
	256
	257	for (i = 0; i < num_isgmt; ++i) {
	258	int c = getc(f);
	259	if (c == EOF)
11f22867	260	return -EINVAL;
b7f1542c KS	261	types[i].isgmt = c != 0;
	262	}
	263
	264	while (i < num_types)
	265	types[i++].isgmt = 0;
	266
	267	if (num_transitions == 0)
11f22867	268	return -EINVAL;
b7f1542c KS	269
b7f1542c KS	270	if (date < transitions[0] \|\| date >= transitions[num_transitions - 1])
11f22867	271	return -EINVAL;
b7f1542c KS	272
	273	/* Find the first transition after TIMER, and
	274	then pick the type of the transition before it. */
	275	lo = 0;
	276	hi = num_transitions - 1;
	277
	278	/* Assume that DST is changing twice a year and guess initial
	279	search spot from it.
	280	Half of a gregorian year has on average 365.2425 * 86400 / 2
	281	= 15778476 seconds. */
	282	i = (transitions[num_transitions - 1] - date) / 15778476;
	283	if (i < num_transitions) {
	284	i = num_transitions - 1 - i;
	285	if (date < transitions[i]) {
	286	if (i < 10 \|\| date >= transitions[i - 10]) {
	287	/* Linear search. */
	288	while (date < transitions[i - 1])
	289	i--;
	290	goto found;
	291	}
	292	hi = i - 10;
	293	} else {
	294	if (i + 10 >= num_transitions \|\| date < transitions[i + 10]) {
	295	/* Linear search. */
	296	while (date >= transitions[i])
	297	i++;
	298	goto found;
	299	}
	300	lo = i + 10;
	301	}
	302	}
	303
	304	/* Binary search. */
	305	while (lo + 1 < hi) {
	306	i = (lo + hi) / 2;
	307	if (date < transitions[i])
	308	hi = i;
	309	else
	310	lo = i;
	311	}
	312	i = hi;
	313
	314	found:
	315	if (switch_cur)
	316	*switch_cur = transitions[i-1];
	317	if (zone_cur)
	318	*zone_cur = strdup(&zone_names[types[type_idxs[i - 1]].idx]);
	319	if (dst_cur)
	320	*dst_cur = types[type_idxs[i-1]].isdst;
2311eb2f	321
b7f1542c KS	322	if (switch_next)
b7f1542c KS	323	*switch_next = transitions[i];
2311eb2f KS	324	if (delta_next)
2311eb2f KS	325	*delta_next = (types[type_idxs[i]].offset - types[type_idxs[i-1]].offset) / 60;
b7f1542c KS	326	if (zone_next)
	327	*zone_next = strdup(&zone_names[types[type_idxs[i]].idx]);
	328	if (dst_next)
	329	*dst_next = types[type_idxs[i]].isdst;
	330
b7f1542c	331	return 0;
b7f1542c	332	}