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