From patchwork Sun Jan 5 05:57:29 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul Eggert X-Patchwork-Id: 104065 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 643B63857713 for ; Sun, 5 Jan 2025 06:19:59 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail.cs.ucla.edu (mail.cs.ucla.edu [131.179.128.66]) by sourceware.org (Postfix) with ESMTPS id AFE1F3858429 for ; Sun, 5 Jan 2025 06:00:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org AFE1F3858429 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=cs.ucla.edu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=cs.ucla.edu ARC-Filter: OpenARC Filter v1.0.0 sourceware.org AFE1F3858429 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=131.179.128.66 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1736056835; cv=none; b=gEBSRoA5K9UZ4dXPqtS/2GMNgQGJ3n5/bMuHfNmvFamH57IW0plYB9EBy/x+ezZKXwZtfgR8dc6pj1F9+lQRKkADdLortDnQJ3TT7UUkp1lmHcDPAFtCf3IqYL9pB9QHMxZeHmbjBLBoVC7L84rX1t4tTw1UrU/I0fKD2cyXKU0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1736056835; c=relaxed/simple; bh=ineo5JBXl805/O1ggz2r9aS6RtbNIKfML91MIL1ScSI=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=nGGcK+ldB56uUPzprW9vAf6HXGpowun453i80DsI5qLQYAMX93kXifA+GNt8cSmJyLBYz0An/9K0DR0hLuN4SwDJutVMw/uT22wXLRr8kxSSzrxIHM4mndQKRXig1YW3zUeSBT3mUhSxUVaX8ux/fOJZJU36uRxk0bepZf+pzgk= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AFE1F3858429 Authentication-Results: sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=cs.ucla.edu header.i=@cs.ucla.edu header.a=rsa-sha256 header.s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C header.b=Zkqsn3pJ Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id 353CA3C123843 for ; Sat, 4 Jan 2025 22:00:35 -0800 (PST) Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10032) with ESMTP id Cuj-ZR0qR928; Sat, 4 Jan 2025 22:00:34 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by mail.cs.ucla.edu (Postfix) with ESMTP id CA6AC3C082EB9; Sat, 4 Jan 2025 22:00:34 -0800 (PST) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.cs.ucla.edu CA6AC3C082EB9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.ucla.edu; s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C; t=1736056834; bh=9a9joSjfR0byLtNeIREefPsFf80nGV2fcPMZsS3fssY=; h=From:To:Date:Message-ID:MIME-Version; b=Zkqsn3pJhrHUIILY0aMPUjf3G08Z+eBXBbzxnnvWDnJ0B8X0gMk2fKmbGBFCaKAdZ WhVmng2/rKGpvC7rliH+acQeg9Zx7Tn5YEq+mDneofN0VURehisujX4p5KvSnHvkcP ZkqFCflUQ+ZUyxcl8tel0cEC4eRqJ1HCBkNfDyggAqOpQiQ35EJ/zW9NBfHzLcBjQ2 YEmnGpJKPofzLKKmo9w+s1gY6xuTc0K2qKUKIvNXX073mHaLuG4Cs3W3aC3EuuqDdw 4DZxsthJTsR9ZLHQ1x++B5fc4whHeyXMGrkPcHIwOLVad3Ywo+7ziYx1JHQ+yglWOO dFGu8s/zmvFYg== X-Virus-Scanned: amavis at mail.cs.ucla.edu Received: from mail.cs.ucla.edu ([127.0.0.1]) by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10026) with ESMTP id zfO-YS58YiG7; Sat, 4 Jan 2025 22:00:34 -0800 (PST) Received: from wing.home (unknown [47.154.28.214]) by mail.cs.ucla.edu (Postfix) with ESMTPSA id B42843C082EB5; Sat, 4 Jan 2025 22:00:34 -0800 (PST) From: Paul Eggert To: libc-alpha@sourceware.org Cc: Paul Eggert Subject: [PATCH 54/59] Refactor __tzfile_compute to avoid two gotos Date: Sat, 4 Jan 2025 21:57:29 -0800 Message-ID: <20250105055750.1668721-55-eggert@cs.ucla.edu> X-Mailer: git-send-email 2.45.2 In-Reply-To: <01207110-bd60-46ae-9c08-fb39c2011067@cs.ucla.edu> References: <01207110-bd60-46ae-9c08-fb39c2011067@cs.ucla.edu> MIME-Version: 1.0 X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces~patchwork=sourceware.org@sourceware.org * time/tzfile.c (first_transition_after): New function. (__tzfile_compute): Use it to avoid the need for two gotos. --- time/tzfile.c | 129 +++++++++++++++++++++++++++----------------------- 1 file changed, 69 insertions(+), 60 deletions(-) diff --git a/time/tzfile.c b/time/tzfile.c index cde8d74b6f..0ee70fd356 100644 --- a/time/tzfile.c +++ b/time/tzfile.c @@ -574,6 +574,70 @@ __tzfile_read (const char *file) return false; } +/* Find index of first transition after TIMER. + If there are no transitions after TIMER, return the number of transitions. + TIMER must not be less than the first transition (if any). */ + +static tzidx +first_transition_after (__time64_t timer) +{ + if (timecnt == 0 || timer >= transitions[timecnt - 1]) + return timecnt; + + tzidx lo = 0; + tzidx hi = timecnt - 1; + + /* Find the last transition on or before TIMER. + 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. + Although i's value can be wrong if overflow occurs, + this is harmless because it is just a guess. */ + + __time64_t tdiff; + tzidx i; + ckd_sub (&tdiff, transitions[timecnt - 1], timer); + ckd_add (&i, tdiff / 15778476, 0); + if (i < timecnt) + { + i = timecnt - 1 - i; + if (timer < transitions[i]) + { + if (i < 10 || timer >= transitions[i - 10]) + { + /* Linear search. */ + while (timer < transitions[i - 1]) + --i; + return i; + } + hi = i - 10; + } + else + { + if (timecnt - i <= 10 || timer < transitions[i + 10]) + { + /* Linear search. */ + while (timer >= transitions[i]) + ++i; + return i; + } + lo = i + 10; + } + } + + /* Binary search. */ + /* assert (timer >= transitions[lo] && timer < transitions[hi]); */ + while (lo + 1 < hi) + { + i = (lo >> 1) + (hi >> 1) + (lo & hi & 1); + if (timer < transitions[i]) + hi = i; + else + lo = i; + } + return hi; +} + void __tzfile_compute (__time64_t timer, int use_localtime, int *leap_correct, bool *leap_hit, @@ -615,10 +679,12 @@ __tzfile_compute (__time64_t timer, int use_localtime, } else { - if (timecnt == 0 || timer >= transitions[timecnt - 1]) + i = first_transition_after (timer); + if (i == timecnt) { - /* TIMER is after the last transition. Use the TZ string if - it is present and we can convert to the broken down structure. */ + /* TIMER is after the last transition, or there are no transitions + and a TZ string is present. Use the TZ string if it is present + and if we can convert to the broken down structure. */ if (__glibc_likely (tzspec != NULL) && __glibc_likely (__offtime (timer, 0, 0, tp) != NULL)) { @@ -626,64 +692,7 @@ __tzfile_compute (__time64_t timer, int use_localtime, __tz_compute (timer, tp); return; } - - i = timecnt; - } - else - { - /* Find the first transition after TIMER, and - then pick the type of the transition before it. */ - tzidx lo = 0; - tzidx hi = timecnt - 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. - Although i's value can be wrong if overflow occurs, - this is harmless because it is just a guess. */ - __time64_t tdiff; - ckd_sub (&tdiff, transitions[timecnt - 1], timer); - ckd_add (&i, tdiff / 15778476, 0); - if (i < timecnt) - { - i = timecnt - 1 - i; - if (timer < transitions[i]) - { - if (i < 10 || timer >= transitions[i - 10]) - { - /* Linear search. */ - while (timer < transitions[i - 1]) - --i; - goto found; - } - hi = i - 10; - } - else - { - if (timecnt - i <= 10 || timer < transitions[i + 10]) - { - /* Linear search. */ - while (timer >= transitions[i]) - ++i; - goto found; - } - lo = i + 10; - } - } - - /* Binary search. */ - /* assert (timer >= transitions[lo] && timer < transitions[hi]); */ - while (lo + 1 < hi) - { - i = (lo >> 1) + (hi >> 1) + (lo & hi & 1); - if (timer < transitions[i]) - hi = i; - else - lo = i; - } - i = hi; } - - found: ti = type_idxs[i - 1]; }