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