svenpanne@chromium.org | 4efbdb1 | 2012-03-12 08:18:42 +0000 | [diff] [blame] | 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 |