1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // http://code.google.com/p/protobuf/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 // from google3/strings/strutil.cc 32 33 #include <google/protobuf/stubs/strutil.h> 34 #include <errno.h> 35 #include <float.h> // FLT_DIG and DBL_DIG 36 #include <limits> 37 #include <limits.h> 38 #include <stdio.h> 39 #include <iterator> 40 41 #ifdef _WIN32 42 // MSVC has only _snprintf, not snprintf. 43 // 44 // MinGW has both snprintf and _snprintf, but they appear to be different 45 // functions. The former is buggy. When invoked like so: 46 // char buffer[32]; 47 // snprintf(buffer, 32, "%.*g\n", FLT_DIG, 1.23e10f); 48 // it prints "1.23000e+10". This is plainly wrong: %g should never print 49 // trailing zeros after the decimal point. For some reason this bug only 50 // occurs with some input values, not all. In any case, _snprintf does the 51 // right thing, so we use it. 52 #define snprintf _snprintf 53 #endif 54 55 namespace google { 56 namespace protobuf { 57 58 inline bool IsNaN(double value) { 59 // NaN is never equal to anything, even itself. 60 return value != value; 61 } 62 63 // These are defined as macros on some platforms. #undef them so that we can 64 // redefine them. 65 #undef isxdigit 66 #undef isprint 67 68 // The definitions of these in ctype.h change based on locale. Since our 69 // string manipulation is all in relation to the protocol buffer and C++ 70 // languages, we always want to use the C locale. So, we re-define these 71 // exactly as we want them. 72 inline bool isxdigit(char c) { 73 return ('0' <= c && c <= '9') || 74 ('a' <= c && c <= 'f') || 75 ('A' <= c && c <= 'F'); 76 } 77 78 inline bool isprint(char c) { 79 return c >= 0x20 && c <= 0x7E; 80 } 81 82 // ---------------------------------------------------------------------- 83 // StripString 84 // Replaces any occurrence of the character 'remove' (or the characters 85 // in 'remove') with the character 'replacewith'. 86 // ---------------------------------------------------------------------- 87 void StripString(string* s, const char* remove, char replacewith) { 88 const char * str_start = s->c_str(); 89 const char * str = str_start; 90 for (str = strpbrk(str, remove); 91 str != NULL; 92 str = strpbrk(str + 1, remove)) { 93 (*s)[str - str_start] = replacewith; 94 } 95 } 96 97 // ---------------------------------------------------------------------- 98 // StringReplace() 99 // Replace the "old" pattern with the "new" pattern in a string, 100 // and append the result to "res". If replace_all is false, 101 // it only replaces the first instance of "old." 102 // ---------------------------------------------------------------------- 103 104 void StringReplace(const string& s, const string& oldsub, 105 const string& newsub, bool replace_all, 106 string* res) { 107 if (oldsub.empty()) { 108 res->append(s); // if empty, append the given string. 109 return; 110 } 111 112 string::size_type start_pos = 0; 113 string::size_type pos; 114 do { 115 pos = s.find(oldsub, start_pos); 116 if (pos == string::npos) { 117 break; 118 } 119 res->append(s, start_pos, pos - start_pos); 120 res->append(newsub); 121 start_pos = pos + oldsub.size(); // start searching again after the "old" 122 } while (replace_all); 123 res->append(s, start_pos, s.length() - start_pos); 124 } 125 126 // ---------------------------------------------------------------------- 127 // StringReplace() 128 // Give me a string and two patterns "old" and "new", and I replace 129 // the first instance of "old" in the string with "new", if it 130 // exists. If "global" is true; call this repeatedly until it 131 // fails. RETURN a new string, regardless of whether the replacement 132 // happened or not. 133 // ---------------------------------------------------------------------- 134 135 string StringReplace(const string& s, const string& oldsub, 136 const string& newsub, bool replace_all) { 137 string ret; 138 StringReplace(s, oldsub, newsub, replace_all, &ret); 139 return ret; 140 } 141 142 // ---------------------------------------------------------------------- 143 // SplitStringUsing() 144 // Split a string using a character delimiter. Append the components 145 // to 'result'. 146 // 147 // Note: For multi-character delimiters, this routine will split on *ANY* of 148 // the characters in the string, not the entire string as a single delimiter. 149 // ---------------------------------------------------------------------- 150 template <typename ITR> 151 static inline 152 void SplitStringToIteratorUsing(const string& full, 153 const char* delim, 154 ITR& result) { 155 // Optimize the common case where delim is a single character. 156 if (delim[0] != '\0' && delim[1] == '\0') { 157 char c = delim[0]; 158 const char* p = full.data(); 159 const char* end = p + full.size(); 160 while (p != end) { 161 if (*p == c) { 162 ++p; 163 } else { 164 const char* start = p; 165 while (++p != end && *p != c); 166 *result++ = string(start, p - start); 167 } 168 } 169 return; 170 } 171 172 string::size_type begin_index, end_index; 173 begin_index = full.find_first_not_of(delim); 174 while (begin_index != string::npos) { 175 end_index = full.find_first_of(delim, begin_index); 176 if (end_index == string::npos) { 177 *result++ = full.substr(begin_index); 178 return; 179 } 180 *result++ = full.substr(begin_index, (end_index - begin_index)); 181 begin_index = full.find_first_not_of(delim, end_index); 182 } 183 } 184 185 void SplitStringUsing(const string& full, 186 const char* delim, 187 vector<string>* result) { 188 back_insert_iterator< vector<string> > it(*result); 189 SplitStringToIteratorUsing(full, delim, it); 190 } 191 192 // Split a string using a character delimiter. Append the components 193 // to 'result'. If there are consecutive delimiters, this function 194 // will return corresponding empty strings. The string is split into 195 // at most the specified number of pieces greedily. This means that the 196 // last piece may possibly be split further. To split into as many pieces 197 // as possible, specify 0 as the number of pieces. 198 // 199 // If "full" is the empty string, yields an empty string as the only value. 200 // 201 // If "pieces" is negative for some reason, it returns the whole string 202 // ---------------------------------------------------------------------- 203 template <typename StringType, typename ITR> 204 static inline 205 void SplitStringToIteratorAllowEmpty(const StringType& full, 206 const char* delim, 207 int pieces, 208 ITR& result) { 209 string::size_type begin_index, end_index; 210 begin_index = 0; 211 212 for (int i = 0; (i < pieces-1) || (pieces == 0); i++) { 213 end_index = full.find_first_of(delim, begin_index); 214 if (end_index == string::npos) { 215 *result++ = full.substr(begin_index); 216 return; 217 } 218 *result++ = full.substr(begin_index, (end_index - begin_index)); 219 begin_index = end_index + 1; 220 } 221 *result++ = full.substr(begin_index); 222 } 223 224 void SplitStringAllowEmpty(const string& full, const char* delim, 225 vector<string>* result) { 226 back_insert_iterator<vector<string> > it(*result); 227 SplitStringToIteratorAllowEmpty(full, delim, 0, it); 228 } 229 230 // ---------------------------------------------------------------------- 231 // JoinStrings() 232 // This merges a vector of string components with delim inserted 233 // as separaters between components. 234 // 235 // ---------------------------------------------------------------------- 236 template <class ITERATOR> 237 static void JoinStringsIterator(const ITERATOR& start, 238 const ITERATOR& end, 239 const char* delim, 240 string* result) { 241 GOOGLE_CHECK(result != NULL); 242 result->clear(); 243 int delim_length = strlen(delim); 244 245 // Precompute resulting length so we can reserve() memory in one shot. 246 int length = 0; 247 for (ITERATOR iter = start; iter != end; ++iter) { 248 if (iter != start) { 249 length += delim_length; 250 } 251 length += iter->size(); 252 } 253 result->reserve(length); 254 255 // Now combine everything. 256 for (ITERATOR iter = start; iter != end; ++iter) { 257 if (iter != start) { 258 result->append(delim, delim_length); 259 } 260 result->append(iter->data(), iter->size()); 261 } 262 } 263 264 void JoinStrings(const vector<string>& components, 265 const char* delim, 266 string * result) { 267 JoinStringsIterator(components.begin(), components.end(), delim, result); 268 } 269 270 // ---------------------------------------------------------------------- 271 // UnescapeCEscapeSequences() 272 // This does all the unescaping that C does: \ooo, \r, \n, etc 273 // Returns length of resulting string. 274 // The implementation of \x parses any positive number of hex digits, 275 // but it is an error if the value requires more than 8 bits, and the 276 // result is truncated to 8 bits. 277 // 278 // The second call stores its errors in a supplied string vector. 279 // If the string vector pointer is NULL, it reports the errors with LOG(). 280 // ---------------------------------------------------------------------- 281 282 #define IS_OCTAL_DIGIT(c) (((c) >= '0') && ((c) <= '7')) 283 284 inline int hex_digit_to_int(char c) { 285 /* Assume ASCII. */ 286 assert('0' == 0x30 && 'A' == 0x41 && 'a' == 0x61); 287 assert(isxdigit(c)); 288 int x = static_cast<unsigned char>(c); 289 if (x > '9') { 290 x += 9; 291 } 292 return x & 0xf; 293 } 294 295 // Protocol buffers doesn't ever care about errors, but I don't want to remove 296 // the code. 297 #define LOG_STRING(LEVEL, VECTOR) GOOGLE_LOG_IF(LEVEL, false) 298 299 int UnescapeCEscapeSequences(const char* source, char* dest) { 300 return UnescapeCEscapeSequences(source, dest, NULL); 301 } 302 303 int UnescapeCEscapeSequences(const char* source, char* dest, 304 vector<string> *errors) { 305 GOOGLE_DCHECK(errors == NULL) << "Error reporting not implemented."; 306 307 char* d = dest; 308 const char* p = source; 309 310 // Small optimization for case where source = dest and there's no escaping 311 while ( p == d && *p != '\0' && *p != '\\' ) 312 p++, d++; 313 314 while (*p != '\0') { 315 if (*p != '\\') { 316 *d++ = *p++; 317 } else { 318 switch ( *++p ) { // skip past the '\\' 319 case '\0': 320 LOG_STRING(ERROR, errors) << "String cannot end with \\"; 321 *d = '\0'; 322 return d - dest; // we're done with p 323 case 'a': *d++ = '\a'; break; 324 case 'b': *d++ = '\b'; break; 325 case 'f': *d++ = '\f'; break; 326 case 'n': *d++ = '\n'; break; 327 case 'r': *d++ = '\r'; break; 328 case 't': *d++ = '\t'; break; 329 case 'v': *d++ = '\v'; break; 330 case '\\': *d++ = '\\'; break; 331 case '?': *d++ = '\?'; break; // \? Who knew? 332 case '\'': *d++ = '\''; break; 333 case '"': *d++ = '\"'; break; 334 case '0': case '1': case '2': case '3': // octal digit: 1 to 3 digits 335 case '4': case '5': case '6': case '7': { 336 char ch = *p - '0'; 337 if ( IS_OCTAL_DIGIT(p[1]) ) 338 ch = ch * 8 + *++p - '0'; 339 if ( IS_OCTAL_DIGIT(p[1]) ) // safe (and easy) to do this twice 340 ch = ch * 8 + *++p - '0'; // now points at last digit 341 *d++ = ch; 342 break; 343 } 344 case 'x': case 'X': { 345 if (!isxdigit(p[1])) { 346 if (p[1] == '\0') { 347 LOG_STRING(ERROR, errors) << "String cannot end with \\x"; 348 } else { 349 LOG_STRING(ERROR, errors) << 350 "\\x cannot be followed by non-hex digit: \\" << *p << p[1]; 351 } 352 break; 353 } 354 unsigned int ch = 0; 355 const char *hex_start = p; 356 while (isxdigit(p[1])) // arbitrarily many hex digits 357 ch = (ch << 4) + hex_digit_to_int(*++p); 358 if (ch > 0xFF) 359 LOG_STRING(ERROR, errors) << "Value of " << 360 "\\" << string(hex_start, p+1-hex_start) << " exceeds 8 bits"; 361 *d++ = ch; 362 break; 363 } 364 #if 0 // TODO(kenton): Support \u and \U? Requires runetochar(). 365 case 'u': { 366 // \uhhhh => convert 4 hex digits to UTF-8 367 char32 rune = 0; 368 const char *hex_start = p; 369 for (int i = 0; i < 4; ++i) { 370 if (isxdigit(p[1])) { // Look one char ahead. 371 rune = (rune << 4) + hex_digit_to_int(*++p); // Advance p. 372 } else { 373 LOG_STRING(ERROR, errors) 374 << "\\u must be followed by 4 hex digits: \\" 375 << string(hex_start, p+1-hex_start); 376 break; 377 } 378 } 379 d += runetochar(d, &rune); 380 break; 381 } 382 case 'U': { 383 // \Uhhhhhhhh => convert 8 hex digits to UTF-8 384 char32 rune = 0; 385 const char *hex_start = p; 386 for (int i = 0; i < 8; ++i) { 387 if (isxdigit(p[1])) { // Look one char ahead. 388 // Don't change rune until we're sure this 389 // is within the Unicode limit, but do advance p. 390 char32 newrune = (rune << 4) + hex_digit_to_int(*++p); 391 if (newrune > 0x10FFFF) { 392 LOG_STRING(ERROR, errors) 393 << "Value of \\" 394 << string(hex_start, p + 1 - hex_start) 395 << " exceeds Unicode limit (0x10FFFF)"; 396 break; 397 } else { 398 rune = newrune; 399 } 400 } else { 401 LOG_STRING(ERROR, errors) 402 << "\\U must be followed by 8 hex digits: \\" 403 << string(hex_start, p+1-hex_start); 404 break; 405 } 406 } 407 d += runetochar(d, &rune); 408 break; 409 } 410 #endif 411 default: 412 LOG_STRING(ERROR, errors) << "Unknown escape sequence: \\" << *p; 413 } 414 p++; // read past letter we escaped 415 } 416 } 417 *d = '\0'; 418 return d - dest; 419 } 420 421 // ---------------------------------------------------------------------- 422 // UnescapeCEscapeString() 423 // This does the same thing as UnescapeCEscapeSequences, but creates 424 // a new string. The caller does not need to worry about allocating 425 // a dest buffer. This should be used for non performance critical 426 // tasks such as printing debug messages. It is safe for src and dest 427 // to be the same. 428 // 429 // The second call stores its errors in a supplied string vector. 430 // If the string vector pointer is NULL, it reports the errors with LOG(). 431 // 432 // In the first and second calls, the length of dest is returned. In the 433 // the third call, the new string is returned. 434 // ---------------------------------------------------------------------- 435 int UnescapeCEscapeString(const string& src, string* dest) { 436 return UnescapeCEscapeString(src, dest, NULL); 437 } 438 439 int UnescapeCEscapeString(const string& src, string* dest, 440 vector<string> *errors) { 441 scoped_array<char> unescaped(new char[src.size() + 1]); 442 int len = UnescapeCEscapeSequences(src.c_str(), unescaped.get(), errors); 443 GOOGLE_CHECK(dest); 444 dest->assign(unescaped.get(), len); 445 return len; 446 } 447 448 string UnescapeCEscapeString(const string& src) { 449 scoped_array<char> unescaped(new char[src.size() + 1]); 450 int len = UnescapeCEscapeSequences(src.c_str(), unescaped.get(), NULL); 451 return string(unescaped.get(), len); 452 } 453 454 // ---------------------------------------------------------------------- 455 // CEscapeString() 456 // CHexEscapeString() 457 // Copies 'src' to 'dest', escaping dangerous characters using 458 // C-style escape sequences. This is very useful for preparing query 459 // flags. 'src' and 'dest' should not overlap. The 'Hex' version uses 460 // hexadecimal rather than octal sequences. 461 // Returns the number of bytes written to 'dest' (not including the \0) 462 // or -1 if there was insufficient space. 463 // 464 // Currently only \n, \r, \t, ", ', \ and !isprint() chars are escaped. 465 // ---------------------------------------------------------------------- 466 int CEscapeInternal(const char* src, int src_len, char* dest, 467 int dest_len, bool use_hex, bool utf8_safe) { 468 const char* src_end = src + src_len; 469 int used = 0; 470 bool last_hex_escape = false; // true if last output char was \xNN 471 472 for (; src < src_end; src++) { 473 if (dest_len - used < 2) // Need space for two letter escape 474 return -1; 475 476 bool is_hex_escape = false; 477 switch (*src) { 478 case '\n': dest[used++] = '\\'; dest[used++] = 'n'; break; 479 case '\r': dest[used++] = '\\'; dest[used++] = 'r'; break; 480 case '\t': dest[used++] = '\\'; dest[used++] = 't'; break; 481 case '\"': dest[used++] = '\\'; dest[used++] = '\"'; break; 482 case '\'': dest[used++] = '\\'; dest[used++] = '\''; break; 483 case '\\': dest[used++] = '\\'; dest[used++] = '\\'; break; 484 default: 485 // Note that if we emit \xNN and the src character after that is a hex 486 // digit then that digit must be escaped too to prevent it being 487 // interpreted as part of the character code by C. 488 if ((!utf8_safe || static_cast<uint8>(*src) < 0x80) && 489 (!isprint(*src) || 490 (last_hex_escape && isxdigit(*src)))) { 491 if (dest_len - used < 4) // need space for 4 letter escape 492 return -1; 493 sprintf(dest + used, (use_hex ? "\\x%02x" : "\\%03o"), 494 static_cast<uint8>(*src)); 495 is_hex_escape = use_hex; 496 used += 4; 497 } else { 498 dest[used++] = *src; break; 499 } 500 } 501 last_hex_escape = is_hex_escape; 502 } 503 504 if (dest_len - used < 1) // make sure that there is room for \0 505 return -1; 506 507 dest[used] = '\0'; // doesn't count towards return value though 508 return used; 509 } 510 511 int CEscapeString(const char* src, int src_len, char* dest, int dest_len) { 512 return CEscapeInternal(src, src_len, dest, dest_len, false, false); 513 } 514 515 // ---------------------------------------------------------------------- 516 // CEscape() 517 // CHexEscape() 518 // Copies 'src' to result, escaping dangerous characters using 519 // C-style escape sequences. This is very useful for preparing query 520 // flags. 'src' and 'dest' should not overlap. The 'Hex' version 521 // hexadecimal rather than octal sequences. 522 // 523 // Currently only \n, \r, \t, ", ', \ and !isprint() chars are escaped. 524 // ---------------------------------------------------------------------- 525 string CEscape(const string& src) { 526 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion 527 scoped_array<char> dest(new char[dest_length]); 528 const int len = CEscapeInternal(src.data(), src.size(), 529 dest.get(), dest_length, false, false); 530 GOOGLE_DCHECK_GE(len, 0); 531 return string(dest.get(), len); 532 } 533 534 namespace strings { 535 536 string Utf8SafeCEscape(const string& src) { 537 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion 538 scoped_array<char> dest(new char[dest_length]); 539 const int len = CEscapeInternal(src.data(), src.size(), 540 dest.get(), dest_length, false, true); 541 GOOGLE_DCHECK_GE(len, 0); 542 return string(dest.get(), len); 543 } 544 545 string CHexEscape(const string& src) { 546 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion 547 scoped_array<char> dest(new char[dest_length]); 548 const int len = CEscapeInternal(src.data(), src.size(), 549 dest.get(), dest_length, true, false); 550 GOOGLE_DCHECK_GE(len, 0); 551 return string(dest.get(), len); 552 } 553 554 } // namespace strings 555 556 // ---------------------------------------------------------------------- 557 // strto32_adaptor() 558 // strtou32_adaptor() 559 // Implementation of strto[u]l replacements that have identical 560 // overflow and underflow characteristics for both ILP-32 and LP-64 561 // platforms, including errno preservation in error-free calls. 562 // ---------------------------------------------------------------------- 563 564 int32 strto32_adaptor(const char *nptr, char **endptr, int base) { 565 const int saved_errno = errno; 566 errno = 0; 567 const long result = strtol(nptr, endptr, base); 568 if (errno == ERANGE && result == LONG_MIN) { 569 return kint32min; 570 } else if (errno == ERANGE && result == LONG_MAX) { 571 return kint32max; 572 } else if (errno == 0 && result < kint32min) { 573 errno = ERANGE; 574 return kint32min; 575 } else if (errno == 0 && result > kint32max) { 576 errno = ERANGE; 577 return kint32max; 578 } 579 if (errno == 0) 580 errno = saved_errno; 581 return static_cast<int32>(result); 582 } 583 584 uint32 strtou32_adaptor(const char *nptr, char **endptr, int base) { 585 const int saved_errno = errno; 586 errno = 0; 587 const unsigned long result = strtoul(nptr, endptr, base); 588 if (errno == ERANGE && result == ULONG_MAX) { 589 return kuint32max; 590 } else if (errno == 0 && result > kuint32max) { 591 errno = ERANGE; 592 return kuint32max; 593 } 594 if (errno == 0) 595 errno = saved_errno; 596 return static_cast<uint32>(result); 597 } 598 599 // ---------------------------------------------------------------------- 600 // FastIntToBuffer() 601 // FastInt64ToBuffer() 602 // FastHexToBuffer() 603 // FastHex64ToBuffer() 604 // FastHex32ToBuffer() 605 // ---------------------------------------------------------------------- 606 607 // Offset into buffer where FastInt64ToBuffer places the end of string 608 // null character. Also used by FastInt64ToBufferLeft. 609 static const int kFastInt64ToBufferOffset = 21; 610 611 char *FastInt64ToBuffer(int64 i, char* buffer) { 612 // We could collapse the positive and negative sections, but that 613 // would be slightly slower for positive numbers... 614 // 22 bytes is enough to store -2**64, -18446744073709551616. 615 char* p = buffer + kFastInt64ToBufferOffset; 616 *p-- = '\0'; 617 if (i >= 0) { 618 do { 619 *p-- = '0' + i % 10; 620 i /= 10; 621 } while (i > 0); 622 return p + 1; 623 } else { 624 // On different platforms, % and / have different behaviors for 625 // negative numbers, so we need to jump through hoops to make sure 626 // we don't divide negative numbers. 627 if (i > -10) { 628 i = -i; 629 *p-- = '0' + i; 630 *p = '-'; 631 return p; 632 } else { 633 // Make sure we aren't at MIN_INT, in which case we can't say i = -i 634 i = i + 10; 635 i = -i; 636 *p-- = '0' + i % 10; 637 // Undo what we did a moment ago 638 i = i / 10 + 1; 639 do { 640 *p-- = '0' + i % 10; 641 i /= 10; 642 } while (i > 0); 643 *p = '-'; 644 return p; 645 } 646 } 647 } 648 649 // Offset into buffer where FastInt32ToBuffer places the end of string 650 // null character. Also used by FastInt32ToBufferLeft 651 static const int kFastInt32ToBufferOffset = 11; 652 653 // Yes, this is a duplicate of FastInt64ToBuffer. But, we need this for the 654 // compiler to generate 32 bit arithmetic instructions. It's much faster, at 655 // least with 32 bit binaries. 656 char *FastInt32ToBuffer(int32 i, char* buffer) { 657 // We could collapse the positive and negative sections, but that 658 // would be slightly slower for positive numbers... 659 // 12 bytes is enough to store -2**32, -4294967296. 660 char* p = buffer + kFastInt32ToBufferOffset; 661 *p-- = '\0'; 662 if (i >= 0) { 663 do { 664 *p-- = '0' + i % 10; 665 i /= 10; 666 } while (i > 0); 667 return p + 1; 668 } else { 669 // On different platforms, % and / have different behaviors for 670 // negative numbers, so we need to jump through hoops to make sure 671 // we don't divide negative numbers. 672 if (i > -10) { 673 i = -i; 674 *p-- = '0' + i; 675 *p = '-'; 676 return p; 677 } else { 678 // Make sure we aren't at MIN_INT, in which case we can't say i = -i 679 i = i + 10; 680 i = -i; 681 *p-- = '0' + i % 10; 682 // Undo what we did a moment ago 683 i = i / 10 + 1; 684 do { 685 *p-- = '0' + i % 10; 686 i /= 10; 687 } while (i > 0); 688 *p = '-'; 689 return p; 690 } 691 } 692 } 693 694 char *FastHexToBuffer(int i, char* buffer) { 695 GOOGLE_CHECK(i >= 0) << "FastHexToBuffer() wants non-negative integers, not " << i; 696 697 static const char *hexdigits = "0123456789abcdef"; 698 char *p = buffer + 21; 699 *p-- = '\0'; 700 do { 701 *p-- = hexdigits[i & 15]; // mod by 16 702 i >>= 4; // divide by 16 703 } while (i > 0); 704 return p + 1; 705 } 706 707 char *InternalFastHexToBuffer(uint64 value, char* buffer, int num_byte) { 708 static const char *hexdigits = "0123456789abcdef"; 709 buffer[num_byte] = '\0'; 710 for (int i = num_byte - 1; i >= 0; i--) { 711 #ifdef _M_X64 712 // MSVC x64 platform has a bug optimizing the uint32(value) in the #else 713 // block. Given that the uint32 cast was to improve performance on 32-bit 714 // platforms, we use 64-bit '&' directly. 715 buffer[i] = hexdigits[value & 0xf]; 716 #else 717 buffer[i] = hexdigits[uint32(value) & 0xf]; 718 #endif 719 value >>= 4; 720 } 721 return buffer; 722 } 723 724 char *FastHex64ToBuffer(uint64 value, char* buffer) { 725 return InternalFastHexToBuffer(value, buffer, 16); 726 } 727 728 char *FastHex32ToBuffer(uint32 value, char* buffer) { 729 return InternalFastHexToBuffer(value, buffer, 8); 730 } 731 732 static inline char* PlaceNum(char* p, int num, char prev_sep) { 733 *p-- = '0' + num % 10; 734 *p-- = '0' + num / 10; 735 *p-- = prev_sep; 736 return p; 737 } 738 739 // ---------------------------------------------------------------------- 740 // FastInt32ToBufferLeft() 741 // FastUInt32ToBufferLeft() 742 // FastInt64ToBufferLeft() 743 // FastUInt64ToBufferLeft() 744 // 745 // Like the Fast*ToBuffer() functions above, these are intended for speed. 746 // Unlike the Fast*ToBuffer() functions, however, these functions write 747 // their output to the beginning of the buffer (hence the name, as the 748 // output is left-aligned). The caller is responsible for ensuring that 749 // the buffer has enough space to hold the output. 750 // 751 // Returns a pointer to the end of the string (i.e. the null character 752 // terminating the string). 753 // ---------------------------------------------------------------------- 754 755 static const char two_ASCII_digits[100][2] = { 756 {'0','0'}, {'0','1'}, {'0','2'}, {'0','3'}, {'0','4'}, 757 {'0','5'}, {'0','6'}, {'0','7'}, {'0','8'}, {'0','9'}, 758 {'1','0'}, {'1','1'}, {'1','2'}, {'1','3'}, {'1','4'}, 759 {'1','5'}, {'1','6'}, {'1','7'}, {'1','8'}, {'1','9'}, 760 {'2','0'}, {'2','1'}, {'2','2'}, {'2','3'}, {'2','4'}, 761 {'2','5'}, {'2','6'}, {'2','7'}, {'2','8'}, {'2','9'}, 762 {'3','0'}, {'3','1'}, {'3','2'}, {'3','3'}, {'3','4'}, 763 {'3','5'}, {'3','6'}, {'3','7'}, {'3','8'}, {'3','9'}, 764 {'4','0'}, {'4','1'}, {'4','2'}, {'4','3'}, {'4','4'}, 765 {'4','5'}, {'4','6'}, {'4','7'}, {'4','8'}, {'4','9'}, 766 {'5','0'}, {'5','1'}, {'5','2'}, {'5','3'}, {'5','4'}, 767 {'5','5'}, {'5','6'}, {'5','7'}, {'5','8'}, {'5','9'}, 768 {'6','0'}, {'6','1'}, {'6','2'}, {'6','3'}, {'6','4'}, 769 {'6','5'}, {'6','6'}, {'6','7'}, {'6','8'}, {'6','9'}, 770 {'7','0'}, {'7','1'}, {'7','2'}, {'7','3'}, {'7','4'}, 771 {'7','5'}, {'7','6'}, {'7','7'}, {'7','8'}, {'7','9'}, 772 {'8','0'}, {'8','1'}, {'8','2'}, {'8','3'}, {'8','4'}, 773 {'8','5'}, {'8','6'}, {'8','7'}, {'8','8'}, {'8','9'}, 774 {'9','0'}, {'9','1'}, {'9','2'}, {'9','3'}, {'9','4'}, 775 {'9','5'}, {'9','6'}, {'9','7'}, {'9','8'}, {'9','9'} 776 }; 777 778 char* FastUInt32ToBufferLeft(uint32 u, char* buffer) { 779 int digits; 780 const char *ASCII_digits = NULL; 781 // The idea of this implementation is to trim the number of divides to as few 782 // as possible by using multiplication and subtraction rather than mod (%), 783 // and by outputting two digits at a time rather than one. 784 // The huge-number case is first, in the hopes that the compiler will output 785 // that case in one branch-free block of code, and only output conditional 786 // branches into it from below. 787 if (u >= 1000000000) { // >= 1,000,000,000 788 digits = u / 100000000; // 100,000,000 789 ASCII_digits = two_ASCII_digits[digits]; 790 buffer[0] = ASCII_digits[0]; 791 buffer[1] = ASCII_digits[1]; 792 buffer += 2; 793 sublt100_000_000: 794 u -= digits * 100000000; // 100,000,000 795 lt100_000_000: 796 digits = u / 1000000; // 1,000,000 797 ASCII_digits = two_ASCII_digits[digits]; 798 buffer[0] = ASCII_digits[0]; 799 buffer[1] = ASCII_digits[1]; 800 buffer += 2; 801 sublt1_000_000: 802 u -= digits * 1000000; // 1,000,000 803 lt1_000_000: 804 digits = u / 10000; // 10,000 805 ASCII_digits = two_ASCII_digits[digits]; 806 buffer[0] = ASCII_digits[0]; 807 buffer[1] = ASCII_digits[1]; 808 buffer += 2; 809 sublt10_000: 810 u -= digits * 10000; // 10,000 811 lt10_000: 812 digits = u / 100; 813 ASCII_digits = two_ASCII_digits[digits]; 814 buffer[0] = ASCII_digits[0]; 815 buffer[1] = ASCII_digits[1]; 816 buffer += 2; 817 sublt100: 818 u -= digits * 100; 819 lt100: 820 digits = u; 821 ASCII_digits = two_ASCII_digits[digits]; 822 buffer[0] = ASCII_digits[0]; 823 buffer[1] = ASCII_digits[1]; 824 buffer += 2; 825 done: 826 *buffer = 0; 827 return buffer; 828 } 829 830 if (u < 100) { 831 digits = u; 832 if (u >= 10) goto lt100; 833 *buffer++ = '0' + digits; 834 goto done; 835 } 836 if (u < 10000) { // 10,000 837 if (u >= 1000) goto lt10_000; 838 digits = u / 100; 839 *buffer++ = '0' + digits; 840 goto sublt100; 841 } 842 if (u < 1000000) { // 1,000,000 843 if (u >= 100000) goto lt1_000_000; 844 digits = u / 10000; // 10,000 845 *buffer++ = '0' + digits; 846 goto sublt10_000; 847 } 848 if (u < 100000000) { // 100,000,000 849 if (u >= 10000000) goto lt100_000_000; 850 digits = u / 1000000; // 1,000,000 851 *buffer++ = '0' + digits; 852 goto sublt1_000_000; 853 } 854 // we already know that u < 1,000,000,000 855 digits = u / 100000000; // 100,000,000 856 *buffer++ = '0' + digits; 857 goto sublt100_000_000; 858 } 859 860 char* FastInt32ToBufferLeft(int32 i, char* buffer) { 861 uint32 u = i; 862 if (i < 0) { 863 *buffer++ = '-'; 864 u = -i; 865 } 866 return FastUInt32ToBufferLeft(u, buffer); 867 } 868 869 char* FastUInt64ToBufferLeft(uint64 u64, char* buffer) { 870 int digits; 871 const char *ASCII_digits = NULL; 872 873 uint32 u = static_cast<uint32>(u64); 874 if (u == u64) return FastUInt32ToBufferLeft(u, buffer); 875 876 uint64 top_11_digits = u64 / 1000000000; 877 buffer = FastUInt64ToBufferLeft(top_11_digits, buffer); 878 u = u64 - (top_11_digits * 1000000000); 879 880 digits = u / 10000000; // 10,000,000 881 GOOGLE_DCHECK_LT(digits, 100); 882 ASCII_digits = two_ASCII_digits[digits]; 883 buffer[0] = ASCII_digits[0]; 884 buffer[1] = ASCII_digits[1]; 885 buffer += 2; 886 u -= digits * 10000000; // 10,000,000 887 digits = u / 100000; // 100,000 888 ASCII_digits = two_ASCII_digits[digits]; 889 buffer[0] = ASCII_digits[0]; 890 buffer[1] = ASCII_digits[1]; 891 buffer += 2; 892 u -= digits * 100000; // 100,000 893 digits = u / 1000; // 1,000 894 ASCII_digits = two_ASCII_digits[digits]; 895 buffer[0] = ASCII_digits[0]; 896 buffer[1] = ASCII_digits[1]; 897 buffer += 2; 898 u -= digits * 1000; // 1,000 899 digits = u / 10; 900 ASCII_digits = two_ASCII_digits[digits]; 901 buffer[0] = ASCII_digits[0]; 902 buffer[1] = ASCII_digits[1]; 903 buffer += 2; 904 u -= digits * 10; 905 digits = u; 906 *buffer++ = '0' + digits; 907 *buffer = 0; 908 return buffer; 909 } 910 911 char* FastInt64ToBufferLeft(int64 i, char* buffer) { 912 uint64 u = i; 913 if (i < 0) { 914 *buffer++ = '-'; 915 u = -i; 916 } 917 return FastUInt64ToBufferLeft(u, buffer); 918 } 919 920 // ---------------------------------------------------------------------- 921 // SimpleItoa() 922 // Description: converts an integer to a string. 923 // 924 // Return value: string 925 // ---------------------------------------------------------------------- 926 927 string SimpleItoa(int i) { 928 char buffer[kFastToBufferSize]; 929 return (sizeof(i) == 4) ? 930 FastInt32ToBuffer(i, buffer) : 931 FastInt64ToBuffer(i, buffer); 932 } 933 934 string SimpleItoa(unsigned int i) { 935 char buffer[kFastToBufferSize]; 936 return string(buffer, (sizeof(i) == 4) ? 937 FastUInt32ToBufferLeft(i, buffer) : 938 FastUInt64ToBufferLeft(i, buffer)); 939 } 940 941 string SimpleItoa(long i) { 942 char buffer[kFastToBufferSize]; 943 return (sizeof(i) == 4) ? 944 FastInt32ToBuffer(i, buffer) : 945 FastInt64ToBuffer(i, buffer); 946 } 947 948 string SimpleItoa(unsigned long i) { 949 char buffer[kFastToBufferSize]; 950 return string(buffer, (sizeof(i) == 4) ? 951 FastUInt32ToBufferLeft(i, buffer) : 952 FastUInt64ToBufferLeft(i, buffer)); 953 } 954 955 string SimpleItoa(long long i) { 956 char buffer[kFastToBufferSize]; 957 return (sizeof(i) == 4) ? 958 FastInt32ToBuffer(i, buffer) : 959 FastInt64ToBuffer(i, buffer); 960 } 961 962 string SimpleItoa(unsigned long long i) { 963 char buffer[kFastToBufferSize]; 964 return string(buffer, (sizeof(i) == 4) ? 965 FastUInt32ToBufferLeft(i, buffer) : 966 FastUInt64ToBufferLeft(i, buffer)); 967 } 968 969 // ---------------------------------------------------------------------- 970 // SimpleDtoa() 971 // SimpleFtoa() 972 // DoubleToBuffer() 973 // FloatToBuffer() 974 // We want to print the value without losing precision, but we also do 975 // not want to print more digits than necessary. This turns out to be 976 // trickier than it sounds. Numbers like 0.2 cannot be represented 977 // exactly in binary. If we print 0.2 with a very large precision, 978 // e.g. "%.50g", we get "0.2000000000000000111022302462515654042363167". 979 // On the other hand, if we set the precision too low, we lose 980 // significant digits when printing numbers that actually need them. 981 // It turns out there is no precision value that does the right thing 982 // for all numbers. 983 // 984 // Our strategy is to first try printing with a precision that is never 985 // over-precise, then parse the result with strtod() to see if it 986 // matches. If not, we print again with a precision that will always 987 // give a precise result, but may use more digits than necessary. 988 // 989 // An arguably better strategy would be to use the algorithm described 990 // in "How to Print Floating-Point Numbers Accurately" by Steele & 991 // White, e.g. as implemented by David M. Gay's dtoa(). It turns out, 992 // however, that the following implementation is about as fast as 993 // DMG's code. Furthermore, DMG's code locks mutexes, which means it 994 // will not scale well on multi-core machines. DMG's code is slightly 995 // more accurate (in that it will never use more digits than 996 // necessary), but this is probably irrelevant for most users. 997 // 998 // Rob Pike and Ken Thompson also have an implementation of dtoa() in 999 // third_party/fmt/fltfmt.cc. Their implementation is similar to this 1000 // one in that it makes guesses and then uses strtod() to check them. 1001 // Their implementation is faster because they use their own code to 1002 // generate the digits in the first place rather than use snprintf(), 1003 // thus avoiding format string parsing overhead. However, this makes 1004 // it considerably more complicated than the following implementation, 1005 // and it is embedded in a larger library. If speed turns out to be 1006 // an issue, we could re-implement this in terms of their 1007 // implementation. 1008 // ---------------------------------------------------------------------- 1009 1010 string SimpleDtoa(double value) { 1011 char buffer[kDoubleToBufferSize]; 1012 return DoubleToBuffer(value, buffer); 1013 } 1014 1015 string SimpleFtoa(float value) { 1016 char buffer[kFloatToBufferSize]; 1017 return FloatToBuffer(value, buffer); 1018 } 1019 1020 static inline bool IsValidFloatChar(char c) { 1021 return ('0' <= c && c <= '9') || 1022 c == 'e' || c == 'E' || 1023 c == '+' || c == '-'; 1024 } 1025 1026 void DelocalizeRadix(char* buffer) { 1027 // Fast check: if the buffer has a normal decimal point, assume no 1028 // translation is needed. 1029 if (strchr(buffer, '.') != NULL) return; 1030 1031 // Find the first unknown character. 1032 while (IsValidFloatChar(*buffer)) ++buffer; 1033 1034 if (*buffer == '\0') { 1035 // No radix character found. 1036 return; 1037 } 1038 1039 // We are now pointing at the locale-specific radix character. Replace it 1040 // with '.'. 1041 *buffer = '.'; 1042 ++buffer; 1043 1044 if (!IsValidFloatChar(*buffer) && *buffer != '\0') { 1045 // It appears the radix was a multi-byte character. We need to remove the 1046 // extra bytes. 1047 char* target = buffer; 1048 do { ++buffer; } while (!IsValidFloatChar(*buffer) && *buffer != '\0'); 1049 memmove(target, buffer, strlen(buffer) + 1); 1050 } 1051 } 1052 1053 char* DoubleToBuffer(double value, char* buffer) { 1054 // DBL_DIG is 15 for IEEE-754 doubles, which are used on almost all 1055 // platforms these days. Just in case some system exists where DBL_DIG 1056 // is significantly larger -- and risks overflowing our buffer -- we have 1057 // this assert. 1058 GOOGLE_COMPILE_ASSERT(DBL_DIG < 20, DBL_DIG_is_too_big); 1059 1060 if (value == numeric_limits<double>::infinity()) { 1061 strcpy(buffer, "inf"); 1062 return buffer; 1063 } else if (value == -numeric_limits<double>::infinity()) { 1064 strcpy(buffer, "-inf"); 1065 return buffer; 1066 } else if (IsNaN(value)) { 1067 strcpy(buffer, "nan"); 1068 return buffer; 1069 } 1070 1071 int snprintf_result = 1072 snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG, value); 1073 1074 // The snprintf should never overflow because the buffer is significantly 1075 // larger than the precision we asked for. 1076 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize); 1077 1078 // We need to make parsed_value volatile in order to force the compiler to 1079 // write it out to the stack. Otherwise, it may keep the value in a 1080 // register, and if it does that, it may keep it as a long double instead 1081 // of a double. This long double may have extra bits that make it compare 1082 // unequal to "value" even though it would be exactly equal if it were 1083 // truncated to a double. 1084 volatile double parsed_value = strtod(buffer, NULL); 1085 if (parsed_value != value) { 1086 int snprintf_result = 1087 snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG+2, value); 1088 1089 // Should never overflow; see above. 1090 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize); 1091 } 1092 1093 DelocalizeRadix(buffer); 1094 return buffer; 1095 } 1096 1097 bool safe_strtof(const char* str, float* value) { 1098 char* endptr; 1099 errno = 0; // errno only gets set on errors 1100 #if defined(_WIN32) || defined (__hpux) // has no strtof() 1101 *value = strtod(str, &endptr); 1102 #else 1103 *value = strtof(str, &endptr); 1104 #endif 1105 return *str != 0 && *endptr == 0 && errno == 0; 1106 } 1107 1108 char* FloatToBuffer(float value, char* buffer) { 1109 // FLT_DIG is 6 for IEEE-754 floats, which are used on almost all 1110 // platforms these days. Just in case some system exists where FLT_DIG 1111 // is significantly larger -- and risks overflowing our buffer -- we have 1112 // this assert. 1113 GOOGLE_COMPILE_ASSERT(FLT_DIG < 10, FLT_DIG_is_too_big); 1114 1115 if (value == numeric_limits<double>::infinity()) { 1116 strcpy(buffer, "inf"); 1117 return buffer; 1118 } else if (value == -numeric_limits<double>::infinity()) { 1119 strcpy(buffer, "-inf"); 1120 return buffer; 1121 } else if (IsNaN(value)) { 1122 strcpy(buffer, "nan"); 1123 return buffer; 1124 } 1125 1126 int snprintf_result = 1127 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG, value); 1128 1129 // The snprintf should never overflow because the buffer is significantly 1130 // larger than the precision we asked for. 1131 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kFloatToBufferSize); 1132 1133 float parsed_value; 1134 if (!safe_strtof(buffer, &parsed_value) || parsed_value != value) { 1135 int snprintf_result = 1136 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG+2, value); 1137 1138 // Should never overflow; see above. 1139 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kFloatToBufferSize); 1140 } 1141 1142 DelocalizeRadix(buffer); 1143 return buffer; 1144 } 1145 1146 // ---------------------------------------------------------------------- 1147 // NoLocaleStrtod() 1148 // This code will make you cry. 1149 // ---------------------------------------------------------------------- 1150 1151 // Returns a string identical to *input except that the character pointed to 1152 // by radix_pos (which should be '.') is replaced with the locale-specific 1153 // radix character. 1154 string LocalizeRadix(const char* input, const char* radix_pos) { 1155 // Determine the locale-specific radix character by calling sprintf() to 1156 // print the number 1.5, then stripping off the digits. As far as I can 1157 // tell, this is the only portable, thread-safe way to get the C library 1158 // to divuldge the locale's radix character. No, localeconv() is NOT 1159 // thread-safe. 1160 char temp[16]; 1161 int size = sprintf(temp, "%.1f", 1.5); 1162 GOOGLE_CHECK_EQ(temp[0], '1'); 1163 GOOGLE_CHECK_EQ(temp[size-1], '5'); 1164 GOOGLE_CHECK_LE(size, 6); 1165 1166 // Now replace the '.' in the input with it. 1167 string result; 1168 result.reserve(strlen(input) + size - 3); 1169 result.append(input, radix_pos); 1170 result.append(temp + 1, size - 2); 1171 result.append(radix_pos + 1); 1172 return result; 1173 } 1174 1175 double NoLocaleStrtod(const char* text, char** original_endptr) { 1176 // We cannot simply set the locale to "C" temporarily with setlocale() 1177 // as this is not thread-safe. Instead, we try to parse in the current 1178 // locale first. If parsing stops at a '.' character, then this is a 1179 // pretty good hint that we're actually in some other locale in which 1180 // '.' is not the radix character. 1181 1182 char* temp_endptr; 1183 double result = strtod(text, &temp_endptr); 1184 if (original_endptr != NULL) *original_endptr = temp_endptr; 1185 if (*temp_endptr != '.') return result; 1186 1187 // Parsing halted on a '.'. Perhaps we're in a different locale? Let's 1188 // try to replace the '.' with a locale-specific radix character and 1189 // try again. 1190 string localized = LocalizeRadix(text, temp_endptr); 1191 const char* localized_cstr = localized.c_str(); 1192 char* localized_endptr; 1193 result = strtod(localized_cstr, &localized_endptr); 1194 if ((localized_endptr - localized_cstr) > 1195 (temp_endptr - text)) { 1196 // This attempt got further, so replacing the decimal must have helped. 1197 // Update original_endptr to point at the right location. 1198 if (original_endptr != NULL) { 1199 // size_diff is non-zero if the localized radix has multiple bytes. 1200 int size_diff = localized.size() - strlen(text); 1201 // const_cast is necessary to match the strtod() interface. 1202 *original_endptr = const_cast<char*>( 1203 text + (localized_endptr - localized_cstr - size_diff)); 1204 } 1205 } 1206 1207 return result; 1208 } 1209 1210 } // namespace protobuf 1211 } // namespace google 1212