src/v8/src/date.cc

   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 "date.h"
   6
   7 #include "v8.h"
   8
   9 #include "objects.h"
  10 #include "objects-inl.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14
  15
  16 static const int kDaysIn4Years = 4 * 365 + 1;
  17 static const int kDaysIn100Years = 25 * kDaysIn4Years - 1;
  18 static const int kDaysIn400Years = 4 * kDaysIn100Years + 1;
  19 static const int kDays1970to2000 = 30 * 365 + 7;
  20 static const int kDaysOffset = 1000 * kDaysIn400Years + 5 * kDaysIn400Years -
  21                                kDays1970to2000;
  22 static const int kYearsOffset = 400000;
  23 static const char kDaysInMonths[] =
  24     {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  25
  26
  27 void 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   ASSERT(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   OS::ClearTimezoneCache(tz_cache_);
  44 }
  45
  46
  47 void 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
  55 void 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   ASSERT(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   ASSERT(days >= -1);
  97   ASSERT(is_leap || (days >= 0));
  98   ASSERT((days < 365) || (is_leap && (days < 366)));
  99   ASSERT(is_leap == ((*year % 4 == 0) && (*year % 100 || (*year % 400 == 0))));
 100   ASSERT(is_leap || ((DaysFromYearMonth(*year, 0) + days) == save_days));
 101   ASSERT(!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   ASSERT(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
 136 int 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   ASSERT(month >= 0);
 150   ASSERT(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
 180 void 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
 200 int 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   ASSERT(InvalidSegment(before_) || before_->start_sec <= time_sec);
 226   ASSERT(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     ASSERT(!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       ASSERT(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
 310 void DateCache::ProbeDST(int time_sec) {
 311   DST* before = NULL;
 312   DST* after = NULL;
 313   ASSERT(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   ASSERT(before != NULL);
 338   ASSERT(after != NULL);
 339   ASSERT(before != after);
 340   ASSERT(InvalidSegment(before) || before->start_sec <= time_sec);
 341   ASSERT(InvalidSegment(after) || time_sec < after->start_sec);
 342   ASSERT(InvalidSegment(before) || InvalidSegment(after) ||
 343          before->end_sec < after->start_sec);
 344
 345   before_ = before;
 346   after_ = after;
 347 }
 348
 349
 350 DateCache::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