1// Copyright 2012 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/date.h"
6
7#include "src/objects.h"
8#include "src/objects-inl.h"
9
10namespace v8 {
11namespace internal {
12
13
14static const int kDaysIn4Years = 4 * 365 + 1;
15static const int kDaysIn100Years = 25 * kDaysIn4Years - 1;
16static const int kDaysIn400Years = 4 * kDaysIn100Years + 1;
17static const int kDays1970to2000 = 30 * 365 + 7;
18static const int kDaysOffset = 1000 * kDaysIn400Years + 5 * kDaysIn400Years -
19                               kDays1970to2000;
20static const int kYearsOffset = 400000;
21static const char kDaysInMonths[] =
22    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
23
24
25void DateCache::ResetDateCache() {
26  static const int kMaxStamp = Smi::kMaxValue;
27  if (stamp_->value() >= kMaxStamp) {
28    stamp_ = Smi::kZero;
29  } else {
30    stamp_ = Smi::FromInt(stamp_->value() + 1);
31  }
32  DCHECK(stamp_ != Smi::FromInt(kInvalidStamp));
33  for (int i = 0; i < kDSTSize; ++i) {
34    ClearSegment(&dst_[i]);
35  }
36  dst_usage_counter_ = 0;
37  before_ = &dst_[0];
38  after_ = &dst_[1];
39  local_offset_ms_ = kInvalidLocalOffsetInMs;
40  ymd_valid_ = false;
41  base::OS::ClearTimezoneCache(tz_cache_);
42}
43
44
45void DateCache::ClearSegment(DST* segment) {
46  segment->start_sec = kMaxEpochTimeInSec;
47  segment->end_sec = -kMaxEpochTimeInSec;
48  segment->offset_ms = 0;
49  segment->last_used = 0;
50}
51
52
53void DateCache::YearMonthDayFromDays(
54    int days, int* year, int* month, int* day) {
55  if (ymd_valid_) {
56    // Check conservatively if the given 'days' has
57    // the same year and month as the cached 'days'.
58    int new_day = ymd_day_ + (days - ymd_days_);
59    if (new_day >= 1 && new_day <= 28) {
60      ymd_day_ = new_day;
61      ymd_days_ = days;
62      *year = ymd_year_;
63      *month = ymd_month_;
64      *day = new_day;
65      return;
66    }
67  }
68  int save_days = days;
69
70  days += kDaysOffset;
71  *year = 400 * (days / kDaysIn400Years) - kYearsOffset;
72  days %= kDaysIn400Years;
73
74  DCHECK_EQ(save_days, DaysFromYearMonth(*year, 0) + days);
75
76  days--;
77  int yd1 = days / kDaysIn100Years;
78  days %= kDaysIn100Years;
79  *year += 100 * yd1;
80
81  days++;
82  int yd2 = days / kDaysIn4Years;
83  days %= kDaysIn4Years;
84  *year += 4 * yd2;
85
86  days--;
87  int yd3 = days / 365;
88  days %= 365;
89  *year += yd3;
90
91
92  bool is_leap = (!yd1 || yd2) && !yd3;
93
94  DCHECK(days >= -1);
95  DCHECK(is_leap || (days >= 0));
96  DCHECK((days < 365) || (is_leap && (days < 366)));
97  DCHECK(is_leap == ((*year % 4 == 0) && (*year % 100 || (*year % 400 == 0))));
98  DCHECK(is_leap || ((DaysFromYearMonth(*year, 0) + days) == save_days));
99  DCHECK(!is_leap || ((DaysFromYearMonth(*year, 0) + days + 1) == save_days));
100
101  days += is_leap;
102
103  // Check if the date is after February.
104  if (days >= 31 + 28 + BoolToInt(is_leap)) {
105    days -= 31 + 28 + BoolToInt(is_leap);
106    // Find the date starting from March.
107    for (int i = 2; i < 12; i++) {
108      if (days < kDaysInMonths[i]) {
109        *month = i;
110        *day = days + 1;
111        break;
112      }
113      days -= kDaysInMonths[i];
114    }
115  } else {
116    // Check January and February.
117    if (days < 31) {
118      *month = 0;
119      *day = days + 1;
120    } else {
121      *month = 1;
122      *day = days - 31 + 1;
123    }
124  }
125  DCHECK(DaysFromYearMonth(*year, *month) + *day - 1 == save_days);
126  ymd_valid_ = true;
127  ymd_year_ = *year;
128  ymd_month_ = *month;
129  ymd_day_ = *day;
130  ymd_days_ = save_days;
131}
132
133
134int DateCache::DaysFromYearMonth(int year, int month) {
135  static const int day_from_month[] = {0, 31, 59, 90, 120, 151,
136                                       181, 212, 243, 273, 304, 334};
137  static const int day_from_month_leap[] = {0, 31, 60, 91, 121, 152,
138                                            182, 213, 244, 274, 305, 335};
139
140  year += month / 12;
141  month %= 12;
142  if (month < 0) {
143    year--;
144    month += 12;
145  }
146
147  DCHECK(month >= 0);
148  DCHECK(month < 12);
149
150  // year_delta is an arbitrary number such that:
151  // a) year_delta = -1 (mod 400)
152  // b) year + year_delta > 0 for years in the range defined by
153  //    ECMA 262 - 15.9.1.1, i.e. upto 100,000,000 days on either side of
154  //    Jan 1 1970. This is required so that we don't run into integer
155  //    division of negative numbers.
156  // c) there shouldn't be an overflow for 32-bit integers in the following
157  //    operations.
158  static const int year_delta = 399999;
159  static const int base_day = 365 * (1970 + year_delta) +
160                              (1970 + year_delta) / 4 -
161                              (1970 + year_delta) / 100 +
162                              (1970 + year_delta) / 400;
163
164  int year1 = year + year_delta;
165  int day_from_year = 365 * year1 +
166                      year1 / 4 -
167                      year1 / 100 +
168                      year1 / 400 -
169                      base_day;
170
171  if ((year % 4 != 0) || (year % 100 == 0 && year % 400 != 0)) {
172    return day_from_year + day_from_month[month];
173  }
174  return day_from_year + day_from_month_leap[month];
175}
176
177
178void DateCache::BreakDownTime(int64_t time_ms, int* year, int* month, int* day,
179                              int* weekday, int* hour, int* min, int* sec,
180                              int* ms) {
181  int const days = DaysFromTime(time_ms);
182  int const time_in_day_ms = TimeInDay(time_ms, days);
183  YearMonthDayFromDays(days, year, month, day);
184  *weekday = Weekday(days);
185  *hour = time_in_day_ms / (60 * 60 * 1000);
186  *min = (time_in_day_ms / (60 * 1000)) % 60;
187  *sec = (time_in_day_ms / 1000) % 60;
188  *ms = time_in_day_ms % 1000;
189}
190
191
192void DateCache::ExtendTheAfterSegment(int time_sec, int offset_ms) {
193  if (after_->offset_ms == offset_ms &&
194      after_->start_sec <= time_sec + kDefaultDSTDeltaInSec &&
195      time_sec <= after_->end_sec) {
196    // Extend the after_ segment.
197    after_->start_sec = time_sec;
198  } else {
199    // The after_ segment is either invalid or starts too late.
200    if (after_->start_sec <= after_->end_sec) {
201      // If the after_ segment is valid, replace it with a new segment.
202      after_ = LeastRecentlyUsedDST(before_);
203    }
204    after_->start_sec = time_sec;
205    after_->end_sec = time_sec;
206    after_->offset_ms = offset_ms;
207    after_->last_used = ++dst_usage_counter_;
208  }
209}
210
211
212int DateCache::DaylightSavingsOffsetInMs(int64_t time_ms) {
213  int time_sec = (time_ms >= 0 && time_ms <= kMaxEpochTimeInMs)
214      ? static_cast<int>(time_ms / 1000)
215      : static_cast<int>(EquivalentTime(time_ms) / 1000);
216
217  // Invalidate cache if the usage counter is close to overflow.
218  // Note that dst_usage_counter is incremented less than ten times
219  // in this function.
220  if (dst_usage_counter_ >= kMaxInt - 10) {
221    dst_usage_counter_ = 0;
222    for (int i = 0; i < kDSTSize; ++i) {
223      ClearSegment(&dst_[i]);
224    }
225  }
226
227  // Optimistic fast check.
228  if (before_->start_sec <= time_sec &&
229      time_sec <= before_->end_sec) {
230    // Cache hit.
231    before_->last_used = ++dst_usage_counter_;
232    return before_->offset_ms;
233  }
234
235  ProbeDST(time_sec);
236
237  DCHECK(InvalidSegment(before_) || before_->start_sec <= time_sec);
238  DCHECK(InvalidSegment(after_) || time_sec < after_->start_sec);
239
240  if (InvalidSegment(before_)) {
241    // Cache miss.
242    before_->start_sec = time_sec;
243    before_->end_sec = time_sec;
244    before_->offset_ms = GetDaylightSavingsOffsetFromOS(time_sec);
245    before_->last_used = ++dst_usage_counter_;
246    return before_->offset_ms;
247  }
248
249  if (time_sec <= before_->end_sec) {
250    // Cache hit.
251    before_->last_used = ++dst_usage_counter_;
252    return before_->offset_ms;
253  }
254
255  if (time_sec > before_->end_sec + kDefaultDSTDeltaInSec) {
256    // If the before_ segment ends too early, then just
257    // query for the offset of the time_sec
258    int offset_ms = GetDaylightSavingsOffsetFromOS(time_sec);
259    ExtendTheAfterSegment(time_sec, offset_ms);
260    // This swap helps the optimistic fast check in subsequent invocations.
261    DST* temp = before_;
262    before_ = after_;
263    after_ = temp;
264    return offset_ms;
265  }
266
267  // Now the time_sec is between
268  // before_->end_sec and before_->end_sec + default DST delta.
269  // Update the usage counter of before_ since it is going to be used.
270  before_->last_used = ++dst_usage_counter_;
271
272  // Check if after_ segment is invalid or starts too late.
273  // Note that start_sec of invalid segments is kMaxEpochTimeInSec.
274  if (before_->end_sec + kDefaultDSTDeltaInSec <= after_->start_sec) {
275    int new_after_start_sec = before_->end_sec + kDefaultDSTDeltaInSec;
276    int new_offset_ms = GetDaylightSavingsOffsetFromOS(new_after_start_sec);
277    ExtendTheAfterSegment(new_after_start_sec, new_offset_ms);
278  } else {
279    DCHECK(!InvalidSegment(after_));
280    // Update the usage counter of after_ since it is going to be used.
281    after_->last_used = ++dst_usage_counter_;
282  }
283
284  // Now the time_sec is between before_->end_sec and after_->start_sec.
285  // Only one daylight savings offset change can occur in this interval.
286
287  if (before_->offset_ms == after_->offset_ms) {
288    // Merge two segments if they have the same offset.
289    before_->end_sec = after_->end_sec;
290    ClearSegment(after_);
291    return before_->offset_ms;
292  }
293
294  // Binary search for daylight savings offset change point,
295  // but give up if we don't find it in four iterations.
296  for (int i = 4; i >= 0; --i) {
297    int delta = after_->start_sec - before_->end_sec;
298    int middle_sec = (i == 0) ? time_sec : before_->end_sec + delta / 2;
299    int offset_ms = GetDaylightSavingsOffsetFromOS(middle_sec);
300    if (before_->offset_ms == offset_ms) {
301      before_->end_sec = middle_sec;
302      if (time_sec <= before_->end_sec) {
303        return offset_ms;
304      }
305    } else {
306      DCHECK(after_->offset_ms == offset_ms);
307      after_->start_sec = middle_sec;
308      if (time_sec >= after_->start_sec) {
309        // This swap helps the optimistic fast check in subsequent invocations.
310        DST* temp = before_;
311        before_ = after_;
312        after_ = temp;
313        return offset_ms;
314      }
315    }
316  }
317  UNREACHABLE();
318  return 0;
319}
320
321
322void DateCache::ProbeDST(int time_sec) {
323  DST* before = NULL;
324  DST* after = NULL;
325  DCHECK(before_ != after_);
326
327  for (int i = 0; i < kDSTSize; ++i) {
328    if (dst_[i].start_sec <= time_sec) {
329      if (before == NULL || before->start_sec < dst_[i].start_sec) {
330        before = &dst_[i];
331      }
332    } else if (time_sec < dst_[i].end_sec) {
333      if (after == NULL || after->end_sec > dst_[i].end_sec) {
334        after = &dst_[i];
335      }
336    }
337  }
338
339  // If before or after segments were not found,
340  // then set them to any invalid segment.
341  if (before == NULL) {
342    before = InvalidSegment(before_) ? before_ : LeastRecentlyUsedDST(after);
343  }
344  if (after == NULL) {
345    after = InvalidSegment(after_) && before != after_
346            ? after_ : LeastRecentlyUsedDST(before);
347  }
348
349  DCHECK(before != NULL);
350  DCHECK(after != NULL);
351  DCHECK(before != after);
352  DCHECK(InvalidSegment(before) || before->start_sec <= time_sec);
353  DCHECK(InvalidSegment(after) || time_sec < after->start_sec);
354  DCHECK(InvalidSegment(before) || InvalidSegment(after) ||
355         before->end_sec < after->start_sec);
356
357  before_ = before;
358  after_ = after;
359}
360
361
362DateCache::DST* DateCache::LeastRecentlyUsedDST(DST* skip) {
363  DST* result = NULL;
364  for (int i = 0; i < kDSTSize; ++i) {
365    if (&dst_[i] == skip) continue;
366    if (result == NULL || result->last_used > dst_[i].last_used) {
367      result = &dst_[i];
368    }
369  }
370  ClearSegment(result);
371  return result;
372}
373
374}  // namespace internal
375}  // namespace v8
376