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