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// 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// ---------------------------------------------------------------------- 203template <typename StringType, typename ITR> 204static inline 205void 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 224void 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// ---------------------------------------------------------------------- 236template <class ITERATOR> 237static 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 264void 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 284inline 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 299int UnescapeCEscapeSequences(const char* source, char* dest) { 300 return UnescapeCEscapeSequences(source, dest, NULL); 301} 302 303int 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// ---------------------------------------------------------------------- 435int UnescapeCEscapeString(const string& src, string* dest) { 436 return UnescapeCEscapeString(src, dest, NULL); 437} 438 439int 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 448string 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// ---------------------------------------------------------------------- 466int 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 511int 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// ---------------------------------------------------------------------- 525string 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 534namespace strings { 535 536string 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 545string 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 564int32 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 584uint32 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. 609static const int kFastInt64ToBufferOffset = 21; 610 611char *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 651static 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. 656char *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 694char *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 707char *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 724char *FastHex64ToBuffer(uint64 value, char* buffer) { 725 return InternalFastHexToBuffer(value, buffer, 16); 726} 727 728char *FastHex32ToBuffer(uint32 value, char* buffer) { 729 return InternalFastHexToBuffer(value, buffer, 8); 730} 731 732static 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 755static 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 778char* 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; 793sublt100_000_000: 794 u -= digits * 100000000; // 100,000,000 795lt100_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; 801sublt1_000_000: 802 u -= digits * 1000000; // 1,000,000 803lt1_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; 809sublt10_000: 810 u -= digits * 10000; // 10,000 811lt10_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; 817sublt100: 818 u -= digits * 100; 819lt100: 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; 825done: 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 860char* 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 869char* 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 911char* 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 927string SimpleItoa(int i) { 928 char buffer[kFastToBufferSize]; 929 return (sizeof(i) == 4) ? 930 FastInt32ToBuffer(i, buffer) : 931 FastInt64ToBuffer(i, buffer); 932} 933 934string 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 941string SimpleItoa(long i) { 942 char buffer[kFastToBufferSize]; 943 return (sizeof(i) == 4) ? 944 FastInt32ToBuffer(i, buffer) : 945 FastInt64ToBuffer(i, buffer); 946} 947 948string 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 955string SimpleItoa(long long i) { 956 char buffer[kFastToBufferSize]; 957 return (sizeof(i) == 4) ? 958 FastInt32ToBuffer(i, buffer) : 959 FastInt64ToBuffer(i, buffer); 960} 961 962string 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 1010string SimpleDtoa(double value) { 1011 char buffer[kDoubleToBufferSize]; 1012 return DoubleToBuffer(value, buffer); 1013} 1014 1015string SimpleFtoa(float value) { 1016 char buffer[kFloatToBufferSize]; 1017 return FloatToBuffer(value, buffer); 1018} 1019 1020static inline bool IsValidFloatChar(char c) { 1021 return ('0' <= c && c <= '9') || 1022 c == 'e' || c == 'E' || 1023 c == '+' || c == '-'; 1024} 1025 1026void 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 1053char* 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 1097bool 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 1108char* 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. 1154string 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 1175double 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