1 //===-- Implementation of mktime function ---------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "src/time/mktime.h"
10 #include "src/__support/common.h"
11 #include "src/time/time_utils.h"
12 
13 #include <limits.h>
14 
15 namespace __llvm_libc {
16 
17 using __llvm_libc::time_utils::TimeConstants;
18 
19 // Returns number of years from (1, year).
20 static constexpr int64_t getNumOfLeapYearsBefore(int64_t year) {
21   return (year / 4) - (year / 100) + (year / 400);
22 }
23 
24 // Returns True if year is a leap year.
25 static constexpr bool isLeapYear(const int64_t year) {
26   return (((year) % 4) == 0 && (((year) % 100) != 0 || ((year) % 400) == 0));
27 }
28 
29 static int64_t computeRemainingYears(int64_t daysPerYears,
30                                      int64_t quotientYears,
31                                      int64_t *remainingDays) {
32   int64_t years = *remainingDays / daysPerYears;
33   if (years == quotientYears)
34     years--;
35   *remainingDays -= years * daysPerYears;
36   return years;
37 }
38 
39 // Update the "tm" structure's year, month, etc. members from seconds.
40 // "total_seconds" is the number of seconds since January 1st, 1970.
41 //
42 // First, divide "total_seconds" by the number of seconds in a day to get the
43 // number of days since Jan 1 1970. The remainder will be used to calculate the
44 // number of Hours, Minutes and Seconds.
45 //
46 // Then, adjust that number of days by a constant to be the number of days
47 // since Mar 1 2000. Year 2000 is a multiple of 400, the leap year cycle. This
48 // makes it easier to count how many leap years have passed using division.
49 //
50 // While calculating numbers of years in the days, the following algorithm
51 // subdivides the days into the number of 400 years, the number of 100 years and
52 // the number of 4 years. These numbers of cycle years are used in calculating
53 // leap day. This is similar to the algorithm used in  getNumOfLeapYearsBefore()
54 // and isLeapYear(). Then compute the total number of years in days from these
55 // subdivided units.
56 //
57 // Compute the number of months from the remaining days. Finally, adjust years
58 // to be 1900 and months to be from January.
59 static int64_t updateFromSeconds(int64_t total_seconds, struct tm *tm) {
60   // Days in month starting from March in the year 2000.
61   static const char daysInMonth[] = {31 /* Mar */, 30, 31, 30, 31, 31,
62                                      30,           31, 30, 31, 31, 29};
63 
64   if (sizeof(time_t) == 4) {
65     if (total_seconds < 0x80000000)
66       return time_utils::OutOfRange();
67     if (total_seconds > 0x7FFFFFFF)
68       return time_utils::OutOfRange();
69   } else {
70     if (total_seconds <
71             INT_MIN * static_cast<int64_t>(
72                           TimeConstants::NumberOfSecondsInLeapYear) ||
73         total_seconds > INT_MAX * static_cast<int64_t>(
74                                       TimeConstants::NumberOfSecondsInLeapYear))
75       return time_utils::OutOfRange();
76   }
77 
78   int64_t seconds = total_seconds - TimeConstants::SecondsUntil2000MarchFirst;
79   int64_t days = seconds / TimeConstants::SecondsPerDay;
80   int64_t remainingSeconds = seconds % TimeConstants::SecondsPerDay;
81   if (remainingSeconds < 0) {
82     remainingSeconds += TimeConstants::SecondsPerDay;
83     days--;
84   }
85 
86   int64_t wday = (TimeConstants::WeekDayOf2000MarchFirst + days) %
87                  TimeConstants::DaysPerWeek;
88   if (wday < 0)
89     wday += TimeConstants::DaysPerWeek;
90 
91   // Compute the number of 400 year cycles.
92   int64_t numOfFourHundredYearCycles = days / TimeConstants::DaysPer400Years;
93   int64_t remainingDays = days % TimeConstants::DaysPer400Years;
94   if (remainingDays < 0) {
95     remainingDays += TimeConstants::DaysPer400Years;
96     numOfFourHundredYearCycles--;
97   }
98 
99   // The reminder number of years after computing number of
100   // "four hundred year cycles" will be 4 hundred year cycles or less in 400
101   // years.
102   int64_t numOfHundredYearCycles =
103       computeRemainingYears(TimeConstants::DaysPer100Years, 4, &remainingDays);
104 
105   // The reminder number of years after computing number of
106   // "hundred year cycles" will be 25 four year cycles or less in 100 years.
107   int64_t numOfFourYearCycles =
108       computeRemainingYears(TimeConstants::DaysPer4Years, 25, &remainingDays);
109 
110   // The reminder number of years after computing number of "four year cycles"
111   // will be 4 one year cycles or less in 4 years.
112   int64_t remainingYears = computeRemainingYears(
113       TimeConstants::DaysPerNonLeapYear, 4, &remainingDays);
114 
115   // Calculate number of years from year 2000.
116   int64_t years = remainingYears + 4 * numOfFourYearCycles +
117                   100 * numOfHundredYearCycles +
118                   400LL * numOfFourHundredYearCycles;
119 
120   int leapDay =
121       !remainingYears && (numOfFourYearCycles || !numOfHundredYearCycles);
122 
123   int64_t yday = remainingDays + 31 + 28 + leapDay;
124   if (yday >= TimeConstants::DaysPerNonLeapYear + leapDay)
125     yday -= TimeConstants::DaysPerNonLeapYear + leapDay;
126 
127   int64_t months = 0;
128   while (daysInMonth[months] <= remainingDays) {
129     remainingDays -= daysInMonth[months];
130     months++;
131   }
132 
133   if (months >= TimeConstants::MonthsPerYear - 2) {
134     months -= TimeConstants::MonthsPerYear;
135     years++;
136   }
137 
138   if (years > INT_MAX || years < INT_MIN)
139     return time_utils::OutOfRange();
140 
141   // All the data (years, month and remaining days) was calculated from
142   // March, 2000. Thus adjust the data to be from January, 1900.
143   tm->tm_year = years + 2000 - TimeConstants::TimeYearBase;
144   tm->tm_mon = months + 2;
145   tm->tm_mday = remainingDays + 1;
146   tm->tm_wday = wday;
147   tm->tm_yday = yday;
148 
149   tm->tm_hour = remainingSeconds / TimeConstants::SecondsPerHour;
150   tm->tm_min = remainingSeconds / TimeConstants::SecondsPerMin %
151                TimeConstants::SecondsPerMin;
152   tm->tm_sec = remainingSeconds % TimeConstants::SecondsPerMin;
153 
154   return 0;
155 }
156 
157 LLVM_LIBC_FUNCTION(time_t, mktime, (struct tm * tm_out)) {
158   // Unlike most C Library functions, mktime doesn't just die on bad input.
159   // TODO(rtenneti); Handle leap seconds.
160   int64_t tmYearFromBase = tm_out->tm_year + TimeConstants::TimeYearBase;
161 
162   // 32-bit end-of-the-world is 03:14:07 UTC on 19 January 2038.
163   if (sizeof(time_t) == 4 &&
164       tmYearFromBase >= TimeConstants::EndOf32BitEpochYear) {
165     if (tmYearFromBase > TimeConstants::EndOf32BitEpochYear)
166       return time_utils::OutOfRange();
167     if (tm_out->tm_mon > 0)
168       return time_utils::OutOfRange();
169     if (tm_out->tm_mday > 19)
170       return time_utils::OutOfRange();
171     if (tm_out->tm_hour > 3)
172       return time_utils::OutOfRange();
173     if (tm_out->tm_min > 14)
174       return time_utils::OutOfRange();
175     if (tm_out->tm_sec > 7)
176       return time_utils::OutOfRange();
177   }
178 
179   // Years are ints.  A 32-bit year will fit into a 64-bit time_t.
180   // A 64-bit year will not.
181   static_assert(sizeof(int) == 4,
182                 "ILP64 is unimplemented.  This implementation requires "
183                 "32-bit integers.");
184 
185   // Calculate number of months and years from tm_mon.
186   int64_t month = tm_out->tm_mon;
187   if (month < 0 || month >= TimeConstants::MonthsPerYear - 1) {
188     int64_t years = month / 12;
189     month %= 12;
190     if (month < 0) {
191       years--;
192       month += 12;
193     }
194     tmYearFromBase += years;
195   }
196   bool tmYearIsLeap = isLeapYear(tmYearFromBase);
197 
198   // Calculate total number of days based on the month and the day (tm_mday).
199   int64_t totalDays = tm_out->tm_mday - 1;
200   for (int64_t i = 0; i < month; ++i)
201     totalDays += TimeConstants::NonLeapYearDaysInMonth[i];
202   // Add one day if it is a leap year and the month is after February.
203   if (tmYearIsLeap && month > 1)
204     totalDays++;
205 
206   // Calculate total numbers of days based on the year.
207   totalDays += (tmYearFromBase - TimeConstants::EpochYear) *
208                TimeConstants::DaysPerNonLeapYear;
209   if (tmYearFromBase >= TimeConstants::EpochYear) {
210     totalDays += getNumOfLeapYearsBefore(tmYearFromBase - 1) -
211                  getNumOfLeapYearsBefore(TimeConstants::EpochYear);
212   } else if (tmYearFromBase >= 1) {
213     totalDays -= getNumOfLeapYearsBefore(TimeConstants::EpochYear) -
214                  getNumOfLeapYearsBefore(tmYearFromBase - 1);
215   } else {
216     // Calculate number of leap years until 0th year.
217     totalDays -= getNumOfLeapYearsBefore(TimeConstants::EpochYear) -
218                  getNumOfLeapYearsBefore(0);
219     if (tmYearFromBase <= 0) {
220       totalDays -= 1; // Subtract 1 for 0th year.
221       // Calculate number of leap years until -1 year
222       if (tmYearFromBase < 0) {
223         totalDays -= getNumOfLeapYearsBefore(-tmYearFromBase) -
224                      getNumOfLeapYearsBefore(1);
225       }
226     }
227   }
228 
229   // TODO(rtenneti): Need to handle timezone and update of tm_isdst.
230   int64_t seconds = tm_out->tm_sec +
231                     tm_out->tm_min * TimeConstants::SecondsPerMin +
232                     tm_out->tm_hour * TimeConstants::SecondsPerHour +
233                     totalDays * TimeConstants::SecondsPerDay;
234 
235   // Update the tm structure's year, month, day, etc. from seconds.
236   if (updateFromSeconds(seconds, tm_out) < 0)
237     return time_utils::OutOfRange();
238 
239   return static_cast<time_t>(seconds);
240 }
241 
242 } // namespace __llvm_libc
243