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