Home | History | Annotate | Download | only in src 
      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 
     35 namespace v8 {
     36 namespace internal {
     37 
     38 
     39 static const int kDays4Years[] = {0, 365, 2 * 365, 3 * 365 + 1};
     40 static const int kDaysIn4Years = 4 * 365 + 1;
     41 static const int kDaysIn100Years = 25 * kDaysIn4Years - 1;
     42 static const int kDaysIn400Years = 4 * kDaysIn100Years + 1;
     43 static const int kDays1970to2000 = 30 * 365 + 7;
     44 static const int kDaysOffset = 1000 * kDaysIn400Years + 5 * kDaysIn400Years -
     45                                kDays1970to2000;
     46 static const int kYearsOffset = 400000;
     47 static const char kDaysInMonths[] =
     48     {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
     49 
     50 
     51 void 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 
     69 void 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 
     77 void 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 
    158 int 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 
    202 void 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 
    222 int 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 
    332 void 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 
    372 DateCache::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