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/v8.h"
      8 
      9 #include "src/objects.h"
     10 #include "src/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   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 
     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   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 
    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   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 
    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   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 
    310 void 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 
    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
    363