1 // Copyright 2006-2008 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 #ifndef V8_UTILS_H_ 29 #define V8_UTILS_H_ 30 31 #include <stdlib.h> 32 33 namespace v8 { 34 namespace internal { 35 36 // ---------------------------------------------------------------------------- 37 // General helper functions 38 39 // Returns true iff x is a power of 2 (or zero). Cannot be used with the 40 // maximally negative value of the type T (the -1 overflows). 41 template <typename T> 42 static inline bool IsPowerOf2(T x) { 43 return (x & (x - 1)) == 0; 44 } 45 46 47 // The C++ standard leaves the semantics of '>>' undefined for 48 // negative signed operands. Most implementations do the right thing, 49 // though. 50 static inline int ArithmeticShiftRight(int x, int s) { 51 return x >> s; 52 } 53 54 55 // Compute the 0-relative offset of some absolute value x of type T. 56 // This allows conversion of Addresses and integral types into 57 // 0-relative int offsets. 58 template <typename T> 59 static inline intptr_t OffsetFrom(T x) { 60 return x - static_cast<T>(0); 61 } 62 63 64 // Compute the absolute value of type T for some 0-relative offset x. 65 // This allows conversion of 0-relative int offsets into Addresses and 66 // integral types. 67 template <typename T> 68 static inline T AddressFrom(intptr_t x) { 69 return static_cast<T>(static_cast<T>(0) + x); 70 } 71 72 73 // Return the largest multiple of m which is <= x. 74 template <typename T> 75 static inline T RoundDown(T x, int m) { 76 ASSERT(IsPowerOf2(m)); 77 return AddressFrom<T>(OffsetFrom(x) & -m); 78 } 79 80 81 // Return the smallest multiple of m which is >= x. 82 template <typename T> 83 static inline T RoundUp(T x, int m) { 84 return RoundDown(x + m - 1, m); 85 } 86 87 88 template <typename T> 89 static int Compare(const T& a, const T& b) { 90 if (a == b) 91 return 0; 92 else if (a < b) 93 return -1; 94 else 95 return 1; 96 } 97 98 99 template <typename T> 100 static int PointerValueCompare(const T* a, const T* b) { 101 return Compare<T>(*a, *b); 102 } 103 104 105 // Returns the smallest power of two which is >= x. If you pass in a 106 // number that is already a power of two, it is returned as is. 107 uint32_t RoundUpToPowerOf2(uint32_t x); 108 109 110 template <typename T> 111 static inline bool IsAligned(T value, T alignment) { 112 ASSERT(IsPowerOf2(alignment)); 113 return (value & (alignment - 1)) == 0; 114 } 115 116 117 // Returns true if (addr + offset) is aligned. 118 static inline bool IsAddressAligned(Address addr, 119 intptr_t alignment, 120 int offset) { 121 intptr_t offs = OffsetFrom(addr + offset); 122 return IsAligned(offs, alignment); 123 } 124 125 126 // Returns the maximum of the two parameters. 127 template <typename T> 128 static T Max(T a, T b) { 129 return a < b ? b : a; 130 } 131 132 133 // Returns the minimum of the two parameters. 134 template <typename T> 135 static T Min(T a, T b) { 136 return a < b ? a : b; 137 } 138 139 140 inline int StrLength(const char* string) { 141 size_t length = strlen(string); 142 ASSERT(length == static_cast<size_t>(static_cast<int>(length))); 143 return static_cast<int>(length); 144 } 145 146 147 // ---------------------------------------------------------------------------- 148 // BitField is a help template for encoding and decode bitfield with 149 // unsigned content. 150 template<class T, int shift, int size> 151 class BitField { 152 public: 153 // Tells whether the provided value fits into the bit field. 154 static bool is_valid(T value) { 155 return (static_cast<uint32_t>(value) & ~((1U << (size)) - 1)) == 0; 156 } 157 158 // Returns a uint32_t mask of bit field. 159 static uint32_t mask() { 160 // To use all bits of a uint32 in a bitfield without compiler warnings we 161 // have to compute 2^32 without using a shift count of 32. 162 return ((1U << shift) << size) - (1U << shift); 163 } 164 165 // Returns a uint32_t with the bit field value encoded. 166 static uint32_t encode(T value) { 167 ASSERT(is_valid(value)); 168 return static_cast<uint32_t>(value) << shift; 169 } 170 171 // Extracts the bit field from the value. 172 static T decode(uint32_t value) { 173 return static_cast<T>((value & mask()) >> shift); 174 } 175 }; 176 177 178 // ---------------------------------------------------------------------------- 179 // Hash function. 180 181 uint32_t ComputeIntegerHash(uint32_t key); 182 183 184 // ---------------------------------------------------------------------------- 185 // I/O support. 186 187 // Our version of printf(). Avoids compilation errors that we get 188 // with standard printf when attempting to print pointers, etc. 189 // (the errors are due to the extra compilation flags, which we 190 // want elsewhere). 191 void PrintF(const char* format, ...); 192 193 // Our version of fflush. 194 void Flush(); 195 196 197 // Read a line of characters after printing the prompt to stdout. The resulting 198 // char* needs to be disposed off with DeleteArray by the caller. 199 char* ReadLine(const char* prompt); 200 201 202 // Read and return the raw bytes in a file. the size of the buffer is returned 203 // in size. 204 // The returned buffer must be freed by the caller. 205 byte* ReadBytes(const char* filename, int* size, bool verbose = true); 206 207 208 // Write size chars from str to the file given by filename. 209 // The file is overwritten. Returns the number of chars written. 210 int WriteChars(const char* filename, 211 const char* str, 212 int size, 213 bool verbose = true); 214 215 216 // Write size bytes to the file given by filename. 217 // The file is overwritten. Returns the number of bytes written. 218 int WriteBytes(const char* filename, 219 const byte* bytes, 220 int size, 221 bool verbose = true); 222 223 224 // Write the C code 225 // const char* <varname> = "<str>"; 226 // const int <varname>_len = <len>; 227 // to the file given by filename. Only the first len chars are written. 228 int WriteAsCFile(const char* filename, const char* varname, 229 const char* str, int size, bool verbose = true); 230 231 232 // ---------------------------------------------------------------------------- 233 // Miscellaneous 234 235 // A static resource holds a static instance that can be reserved in 236 // a local scope using an instance of Access. Attempts to re-reserve 237 // the instance will cause an error. 238 template <typename T> 239 class StaticResource { 240 public: 241 StaticResource() : is_reserved_(false) {} 242 243 private: 244 template <typename S> friend class Access; 245 T instance_; 246 bool is_reserved_; 247 }; 248 249 250 // Locally scoped access to a static resource. 251 template <typename T> 252 class Access { 253 public: 254 explicit Access(StaticResource<T>* resource) 255 : resource_(resource) 256 , instance_(&resource->instance_) { 257 ASSERT(!resource->is_reserved_); 258 resource->is_reserved_ = true; 259 } 260 261 ~Access() { 262 resource_->is_reserved_ = false; 263 resource_ = NULL; 264 instance_ = NULL; 265 } 266 267 T* value() { return instance_; } 268 T* operator -> () { return instance_; } 269 270 private: 271 StaticResource<T>* resource_; 272 T* instance_; 273 }; 274 275 276 template <typename T> 277 class Vector { 278 public: 279 Vector() : start_(NULL), length_(0) {} 280 Vector(T* data, int length) : start_(data), length_(length) { 281 ASSERT(length == 0 || (length > 0 && data != NULL)); 282 } 283 284 static Vector<T> New(int length) { 285 return Vector<T>(NewArray<T>(length), length); 286 } 287 288 // Returns a vector using the same backing storage as this one, 289 // spanning from and including 'from', to but not including 'to'. 290 Vector<T> SubVector(int from, int to) { 291 ASSERT(from < length_); 292 ASSERT(to <= length_); 293 ASSERT(from < to); 294 return Vector<T>(start() + from, to - from); 295 } 296 297 // Returns the length of the vector. 298 int length() const { return length_; } 299 300 // Returns whether or not the vector is empty. 301 bool is_empty() const { return length_ == 0; } 302 303 // Returns the pointer to the start of the data in the vector. 304 T* start() const { return start_; } 305 306 // Access individual vector elements - checks bounds in debug mode. 307 T& operator[](int index) const { 308 ASSERT(0 <= index && index < length_); 309 return start_[index]; 310 } 311 312 T& first() { return start_[0]; } 313 314 T& last() { return start_[length_ - 1]; } 315 316 // Returns a clone of this vector with a new backing store. 317 Vector<T> Clone() const { 318 T* result = NewArray<T>(length_); 319 for (int i = 0; i < length_; i++) result[i] = start_[i]; 320 return Vector<T>(result, length_); 321 } 322 323 void Sort(int (*cmp)(const T*, const T*)) { 324 typedef int (*RawComparer)(const void*, const void*); 325 qsort(start(), 326 length(), 327 sizeof(T), 328 reinterpret_cast<RawComparer>(cmp)); 329 } 330 331 void Sort() { 332 Sort(PointerValueCompare<T>); 333 } 334 335 void Truncate(int length) { 336 ASSERT(length <= length_); 337 length_ = length; 338 } 339 340 // Releases the array underlying this vector. Once disposed the 341 // vector is empty. 342 void Dispose() { 343 if (is_empty()) return; 344 DeleteArray(start_); 345 start_ = NULL; 346 length_ = 0; 347 } 348 349 inline Vector<T> operator+(int offset) { 350 ASSERT(offset < length_); 351 return Vector<T>(start_ + offset, length_ - offset); 352 } 353 354 // Factory method for creating empty vectors. 355 static Vector<T> empty() { return Vector<T>(NULL, 0); } 356 357 protected: 358 void set_start(T* start) { start_ = start; } 359 360 private: 361 T* start_; 362 int length_; 363 }; 364 365 366 // A temporary assignment sets a (non-local) variable to a value on 367 // construction and resets it the value on destruction. 368 template <typename T> 369 class TempAssign { 370 public: 371 TempAssign(T* var, T value): var_(var), old_value_(*var) { 372 *var = value; 373 } 374 375 ~TempAssign() { *var_ = old_value_; } 376 377 private: 378 T* var_; 379 T old_value_; 380 }; 381 382 383 template <typename T, int kSize> 384 class EmbeddedVector : public Vector<T> { 385 public: 386 EmbeddedVector() : Vector<T>(buffer_, kSize) { } 387 388 // When copying, make underlying Vector to reference our buffer. 389 EmbeddedVector(const EmbeddedVector& rhs) 390 : Vector<T>(rhs) { 391 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 392 set_start(buffer_); 393 } 394 395 EmbeddedVector& operator=(const EmbeddedVector& rhs) { 396 if (this == &rhs) return *this; 397 Vector<T>::operator=(rhs); 398 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 399 set_start(buffer_); 400 return *this; 401 } 402 403 private: 404 T buffer_[kSize]; 405 }; 406 407 408 template <typename T> 409 class ScopedVector : public Vector<T> { 410 public: 411 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 412 ~ScopedVector() { 413 DeleteArray(this->start()); 414 } 415 }; 416 417 418 inline Vector<const char> CStrVector(const char* data) { 419 return Vector<const char>(data, StrLength(data)); 420 } 421 422 inline Vector<char> MutableCStrVector(char* data) { 423 return Vector<char>(data, StrLength(data)); 424 } 425 426 inline Vector<char> MutableCStrVector(char* data, int max) { 427 int length = StrLength(data); 428 return Vector<char>(data, (length < max) ? length : max); 429 } 430 431 template <typename T> 432 inline Vector< Handle<Object> > HandleVector(v8::internal::Handle<T>* elms, 433 int length) { 434 return Vector< Handle<Object> >( 435 reinterpret_cast<v8::internal::Handle<Object>*>(elms), length); 436 } 437 438 439 // Simple support to read a file into a 0-terminated C-string. 440 // The returned buffer must be freed by the caller. 441 // On return, *exits tells whether the file existed. 442 Vector<const char> ReadFile(const char* filename, 443 bool* exists, 444 bool verbose = true); 445 446 447 // Simple wrapper that allows an ExternalString to refer to a 448 // Vector<const char>. Doesn't assume ownership of the data. 449 class AsciiStringAdapter: public v8::String::ExternalAsciiStringResource { 450 public: 451 explicit AsciiStringAdapter(Vector<const char> data) : data_(data) {} 452 453 virtual const char* data() const { return data_.start(); } 454 455 virtual size_t length() const { return data_.length(); } 456 457 private: 458 Vector<const char> data_; 459 }; 460 461 462 // Helper class for building result strings in a character buffer. The 463 // purpose of the class is to use safe operations that checks the 464 // buffer bounds on all operations in debug mode. 465 class StringBuilder { 466 public: 467 // Create a string builder with a buffer of the given size. The 468 // buffer is allocated through NewArray<char> and must be 469 // deallocated by the caller of Finalize(). 470 explicit StringBuilder(int size); 471 472 StringBuilder(char* buffer, int size) 473 : buffer_(buffer, size), position_(0) { } 474 475 ~StringBuilder() { if (!is_finalized()) Finalize(); } 476 477 int size() const { return buffer_.length(); } 478 479 // Get the current position in the builder. 480 int position() const { 481 ASSERT(!is_finalized()); 482 return position_; 483 } 484 485 // Reset the position. 486 void Reset() { position_ = 0; } 487 488 // Add a single character to the builder. It is not allowed to add 489 // 0-characters; use the Finalize() method to terminate the string 490 // instead. 491 void AddCharacter(char c) { 492 ASSERT(c != '\0'); 493 ASSERT(!is_finalized() && position_ < buffer_.length()); 494 buffer_[position_++] = c; 495 } 496 497 // Add an entire string to the builder. Uses strlen() internally to 498 // compute the length of the input string. 499 void AddString(const char* s); 500 501 // Add the first 'n' characters of the given string 's' to the 502 // builder. The input string must have enough characters. 503 void AddSubstring(const char* s, int n); 504 505 // Add formatted contents to the builder just like printf(). 506 void AddFormatted(const char* format, ...); 507 508 // Add character padding to the builder. If count is non-positive, 509 // nothing is added to the builder. 510 void AddPadding(char c, int count); 511 512 // Finalize the string by 0-terminating it and returning the buffer. 513 char* Finalize(); 514 515 private: 516 Vector<char> buffer_; 517 int position_; 518 519 bool is_finalized() const { return position_ < 0; } 520 521 DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder); 522 }; 523 524 525 // Copy from ASCII/16bit chars to ASCII/16bit chars. 526 template <typename sourcechar, typename sinkchar> 527 static inline void CopyChars(sinkchar* dest, const sourcechar* src, int chars) { 528 sinkchar* limit = dest + chars; 529 #ifdef V8_HOST_CAN_READ_UNALIGNED 530 if (sizeof(*dest) == sizeof(*src)) { 531 // Number of characters in a uint32_t. 532 static const int kStepSize = sizeof(uint32_t) / sizeof(*dest); // NOLINT 533 while (dest <= limit - kStepSize) { 534 *reinterpret_cast<uint32_t*>(dest) = 535 *reinterpret_cast<const uint32_t*>(src); 536 dest += kStepSize; 537 src += kStepSize; 538 } 539 } 540 #endif 541 while (dest < limit) { 542 *dest++ = static_cast<sinkchar>(*src++); 543 } 544 } 545 546 547 // Calculate 10^exponent. 548 int TenToThe(int exponent); 549 550 } } // namespace v8::internal 551 552 #endif // V8_UTILS_H_ 553