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