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