Home | History | Annotate | Download | only in src 
      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 
     10 namespace v8 {
     11 namespace internal {
     12 
     13 
     14 static const int kDaysIn4Years = 4 * 365 + 1;
     15 static const int kDaysIn100Years = 25 * kDaysIn4Years - 1;
     16 static const int kDaysIn400Years = 4 * kDaysIn100Years + 1;
     17 static const int kDays1970to2000 = 30 * 365 + 7;
     18 static const int kDaysOffset = 1000 * kDaysIn400Years + 5 * kDaysIn400Years -
     19                                kDays1970to2000;
     20 static const int kYearsOffset = 400000;
     21 static const char kDaysInMonths[] =
     22     {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
     23 
     24 
     25 void DateCache::ResetDateCache() {
     26   static const int kMaxStamp = Smi::kMaxValue;
     27   if (stamp_->value() >= kMaxStamp) {
     28     stamp_ = Smi::FromInt(0);
     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 
     45 void 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 
     53 void 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 
    134 int 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 
    178 void 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 
    192 void 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 
    212 int 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 
    322 void 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 
    362 DateCache::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