1// Protocol Buffers - Google's data interchange format 2// Copyright 2008 Google Inc. All rights reserved. 3// https://developers.google.com/protocol-buffers/ 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 599inline bool safe_parse_sign(string* text /*inout*/, 600 bool* negative_ptr /*output*/) { 601 const char* start = text->data(); 602 const char* end = start + text->size(); 603 604 // Consume whitespace. 605 while (start < end && (start[0] == ' ')) { 606 ++start; 607 } 608 while (start < end && (end[-1] == ' ')) { 609 --end; 610 } 611 if (start >= end) { 612 return false; 613 } 614 615 // Consume sign. 616 *negative_ptr = (start[0] == '-'); 617 if (*negative_ptr || start[0] == '+') { 618 ++start; 619 if (start >= end) { 620 return false; 621 } 622 } 623 *text = text->substr(start - text->data(), end - start); 624 return true; 625} 626 627inline bool safe_parse_positive_int( 628 string text, int32* value_p) { 629 int base = 10; 630 int32 value = 0; 631 const int32 vmax = std::numeric_limits<int32>::max(); 632 assert(vmax > 0); 633 assert(vmax >= base); 634 const int32 vmax_over_base = vmax / base; 635 const char* start = text.data(); 636 const char* end = start + text.size(); 637 // loop over digits 638 for (; start < end; ++start) { 639 unsigned char c = static_cast<unsigned char>(start[0]); 640 int digit = c - '0'; 641 if (digit >= base || digit < 0) { 642 *value_p = value; 643 return false; 644 } 645 if (value > vmax_over_base) { 646 *value_p = vmax; 647 return false; 648 } 649 value *= base; 650 if (value > vmax - digit) { 651 *value_p = vmax; 652 return false; 653 } 654 value += digit; 655 } 656 *value_p = value; 657 return true; 658} 659 660inline bool safe_parse_negative_int( 661 string text, int32* value_p) { 662 int base = 10; 663 int32 value = 0; 664 const int32 vmin = std::numeric_limits<int32>::min(); 665 assert(vmin < 0); 666 assert(vmin <= 0 - base); 667 int32 vmin_over_base = vmin / base; 668 // 2003 c++ standard [expr.mul] 669 // "... the sign of the remainder is implementation-defined." 670 // Although (vmin/base)*base + vmin%base is always vmin. 671 // 2011 c++ standard tightens the spec but we cannot rely on it. 672 if (vmin % base > 0) { 673 vmin_over_base += 1; 674 } 675 const char* start = text.data(); 676 const char* end = start + text.size(); 677 // loop over digits 678 for (; start < end; ++start) { 679 unsigned char c = static_cast<unsigned char>(start[0]); 680 int digit = c - '0'; 681 if (digit >= base || digit < 0) { 682 *value_p = value; 683 return false; 684 } 685 if (value < vmin_over_base) { 686 *value_p = vmin; 687 return false; 688 } 689 value *= base; 690 if (value < vmin + digit) { 691 *value_p = vmin; 692 return false; 693 } 694 value -= digit; 695 } 696 *value_p = value; 697 return true; 698} 699 700bool safe_int(string text, int32* value_p) { 701 *value_p = 0; 702 bool negative; 703 if (!safe_parse_sign(&text, &negative)) { 704 return false; 705 } 706 if (!negative) { 707 return safe_parse_positive_int(text, value_p); 708 } else { 709 return safe_parse_negative_int(text, value_p); 710 } 711} 712 713// ---------------------------------------------------------------------- 714// FastIntToBuffer() 715// FastInt64ToBuffer() 716// FastHexToBuffer() 717// FastHex64ToBuffer() 718// FastHex32ToBuffer() 719// ---------------------------------------------------------------------- 720 721// Offset into buffer where FastInt64ToBuffer places the end of string 722// null character. Also used by FastInt64ToBufferLeft. 723static const int kFastInt64ToBufferOffset = 21; 724 725char *FastInt64ToBuffer(int64 i, char* buffer) { 726 // We could collapse the positive and negative sections, but that 727 // would be slightly slower for positive numbers... 728 // 22 bytes is enough to store -2**64, -18446744073709551616. 729 char* p = buffer + kFastInt64ToBufferOffset; 730 *p-- = '\0'; 731 if (i >= 0) { 732 do { 733 *p-- = '0' + i % 10; 734 i /= 10; 735 } while (i > 0); 736 return p + 1; 737 } else { 738 // On different platforms, % and / have different behaviors for 739 // negative numbers, so we need to jump through hoops to make sure 740 // we don't divide negative numbers. 741 if (i > -10) { 742 i = -i; 743 *p-- = '0' + i; 744 *p = '-'; 745 return p; 746 } else { 747 // Make sure we aren't at MIN_INT, in which case we can't say i = -i 748 i = i + 10; 749 i = -i; 750 *p-- = '0' + i % 10; 751 // Undo what we did a moment ago 752 i = i / 10 + 1; 753 do { 754 *p-- = '0' + i % 10; 755 i /= 10; 756 } while (i > 0); 757 *p = '-'; 758 return p; 759 } 760 } 761} 762 763// Offset into buffer where FastInt32ToBuffer places the end of string 764// null character. Also used by FastInt32ToBufferLeft 765static const int kFastInt32ToBufferOffset = 11; 766 767// Yes, this is a duplicate of FastInt64ToBuffer. But, we need this for the 768// compiler to generate 32 bit arithmetic instructions. It's much faster, at 769// least with 32 bit binaries. 770char *FastInt32ToBuffer(int32 i, char* buffer) { 771 // We could collapse the positive and negative sections, but that 772 // would be slightly slower for positive numbers... 773 // 12 bytes is enough to store -2**32, -4294967296. 774 char* p = buffer + kFastInt32ToBufferOffset; 775 *p-- = '\0'; 776 if (i >= 0) { 777 do { 778 *p-- = '0' + i % 10; 779 i /= 10; 780 } while (i > 0); 781 return p + 1; 782 } else { 783 // On different platforms, % and / have different behaviors for 784 // negative numbers, so we need to jump through hoops to make sure 785 // we don't divide negative numbers. 786 if (i > -10) { 787 i = -i; 788 *p-- = '0' + i; 789 *p = '-'; 790 return p; 791 } else { 792 // Make sure we aren't at MIN_INT, in which case we can't say i = -i 793 i = i + 10; 794 i = -i; 795 *p-- = '0' + i % 10; 796 // Undo what we did a moment ago 797 i = i / 10 + 1; 798 do { 799 *p-- = '0' + i % 10; 800 i /= 10; 801 } while (i > 0); 802 *p = '-'; 803 return p; 804 } 805 } 806} 807 808char *FastHexToBuffer(int i, char* buffer) { 809 GOOGLE_CHECK(i >= 0) << "FastHexToBuffer() wants non-negative integers, not " << i; 810 811 static const char *hexdigits = "0123456789abcdef"; 812 char *p = buffer + 21; 813 *p-- = '\0'; 814 do { 815 *p-- = hexdigits[i & 15]; // mod by 16 816 i >>= 4; // divide by 16 817 } while (i > 0); 818 return p + 1; 819} 820 821char *InternalFastHexToBuffer(uint64 value, char* buffer, int num_byte) { 822 static const char *hexdigits = "0123456789abcdef"; 823 buffer[num_byte] = '\0'; 824 for (int i = num_byte - 1; i >= 0; i--) { 825#ifdef _M_X64 826 // MSVC x64 platform has a bug optimizing the uint32(value) in the #else 827 // block. Given that the uint32 cast was to improve performance on 32-bit 828 // platforms, we use 64-bit '&' directly. 829 buffer[i] = hexdigits[value & 0xf]; 830#else 831 buffer[i] = hexdigits[uint32(value) & 0xf]; 832#endif 833 value >>= 4; 834 } 835 return buffer; 836} 837 838char *FastHex64ToBuffer(uint64 value, char* buffer) { 839 return InternalFastHexToBuffer(value, buffer, 16); 840} 841 842char *FastHex32ToBuffer(uint32 value, char* buffer) { 843 return InternalFastHexToBuffer(value, buffer, 8); 844} 845 846static inline char* PlaceNum(char* p, int num, char prev_sep) { 847 *p-- = '0' + num % 10; 848 *p-- = '0' + num / 10; 849 *p-- = prev_sep; 850 return p; 851} 852 853// ---------------------------------------------------------------------- 854// FastInt32ToBufferLeft() 855// FastUInt32ToBufferLeft() 856// FastInt64ToBufferLeft() 857// FastUInt64ToBufferLeft() 858// 859// Like the Fast*ToBuffer() functions above, these are intended for speed. 860// Unlike the Fast*ToBuffer() functions, however, these functions write 861// their output to the beginning of the buffer (hence the name, as the 862// output is left-aligned). The caller is responsible for ensuring that 863// the buffer has enough space to hold the output. 864// 865// Returns a pointer to the end of the string (i.e. the null character 866// terminating the string). 867// ---------------------------------------------------------------------- 868 869static const char two_ASCII_digits[100][2] = { 870 {'0','0'}, {'0','1'}, {'0','2'}, {'0','3'}, {'0','4'}, 871 {'0','5'}, {'0','6'}, {'0','7'}, {'0','8'}, {'0','9'}, 872 {'1','0'}, {'1','1'}, {'1','2'}, {'1','3'}, {'1','4'}, 873 {'1','5'}, {'1','6'}, {'1','7'}, {'1','8'}, {'1','9'}, 874 {'2','0'}, {'2','1'}, {'2','2'}, {'2','3'}, {'2','4'}, 875 {'2','5'}, {'2','6'}, {'2','7'}, {'2','8'}, {'2','9'}, 876 {'3','0'}, {'3','1'}, {'3','2'}, {'3','3'}, {'3','4'}, 877 {'3','5'}, {'3','6'}, {'3','7'}, {'3','8'}, {'3','9'}, 878 {'4','0'}, {'4','1'}, {'4','2'}, {'4','3'}, {'4','4'}, 879 {'4','5'}, {'4','6'}, {'4','7'}, {'4','8'}, {'4','9'}, 880 {'5','0'}, {'5','1'}, {'5','2'}, {'5','3'}, {'5','4'}, 881 {'5','5'}, {'5','6'}, {'5','7'}, {'5','8'}, {'5','9'}, 882 {'6','0'}, {'6','1'}, {'6','2'}, {'6','3'}, {'6','4'}, 883 {'6','5'}, {'6','6'}, {'6','7'}, {'6','8'}, {'6','9'}, 884 {'7','0'}, {'7','1'}, {'7','2'}, {'7','3'}, {'7','4'}, 885 {'7','5'}, {'7','6'}, {'7','7'}, {'7','8'}, {'7','9'}, 886 {'8','0'}, {'8','1'}, {'8','2'}, {'8','3'}, {'8','4'}, 887 {'8','5'}, {'8','6'}, {'8','7'}, {'8','8'}, {'8','9'}, 888 {'9','0'}, {'9','1'}, {'9','2'}, {'9','3'}, {'9','4'}, 889 {'9','5'}, {'9','6'}, {'9','7'}, {'9','8'}, {'9','9'} 890}; 891 892char* FastUInt32ToBufferLeft(uint32 u, char* buffer) { 893 int digits; 894 const char *ASCII_digits = NULL; 895 // The idea of this implementation is to trim the number of divides to as few 896 // as possible by using multiplication and subtraction rather than mod (%), 897 // and by outputting two digits at a time rather than one. 898 // The huge-number case is first, in the hopes that the compiler will output 899 // that case in one branch-free block of code, and only output conditional 900 // branches into it from below. 901 if (u >= 1000000000) { // >= 1,000,000,000 902 digits = u / 100000000; // 100,000,000 903 ASCII_digits = two_ASCII_digits[digits]; 904 buffer[0] = ASCII_digits[0]; 905 buffer[1] = ASCII_digits[1]; 906 buffer += 2; 907sublt100_000_000: 908 u -= digits * 100000000; // 100,000,000 909lt100_000_000: 910 digits = u / 1000000; // 1,000,000 911 ASCII_digits = two_ASCII_digits[digits]; 912 buffer[0] = ASCII_digits[0]; 913 buffer[1] = ASCII_digits[1]; 914 buffer += 2; 915sublt1_000_000: 916 u -= digits * 1000000; // 1,000,000 917lt1_000_000: 918 digits = u / 10000; // 10,000 919 ASCII_digits = two_ASCII_digits[digits]; 920 buffer[0] = ASCII_digits[0]; 921 buffer[1] = ASCII_digits[1]; 922 buffer += 2; 923sublt10_000: 924 u -= digits * 10000; // 10,000 925lt10_000: 926 digits = u / 100; 927 ASCII_digits = two_ASCII_digits[digits]; 928 buffer[0] = ASCII_digits[0]; 929 buffer[1] = ASCII_digits[1]; 930 buffer += 2; 931sublt100: 932 u -= digits * 100; 933lt100: 934 digits = u; 935 ASCII_digits = two_ASCII_digits[digits]; 936 buffer[0] = ASCII_digits[0]; 937 buffer[1] = ASCII_digits[1]; 938 buffer += 2; 939done: 940 *buffer = 0; 941 return buffer; 942 } 943 944 if (u < 100) { 945 digits = u; 946 if (u >= 10) goto lt100; 947 *buffer++ = '0' + digits; 948 goto done; 949 } 950 if (u < 10000) { // 10,000 951 if (u >= 1000) goto lt10_000; 952 digits = u / 100; 953 *buffer++ = '0' + digits; 954 goto sublt100; 955 } 956 if (u < 1000000) { // 1,000,000 957 if (u >= 100000) goto lt1_000_000; 958 digits = u / 10000; // 10,000 959 *buffer++ = '0' + digits; 960 goto sublt10_000; 961 } 962 if (u < 100000000) { // 100,000,000 963 if (u >= 10000000) goto lt100_000_000; 964 digits = u / 1000000; // 1,000,000 965 *buffer++ = '0' + digits; 966 goto sublt1_000_000; 967 } 968 // we already know that u < 1,000,000,000 969 digits = u / 100000000; // 100,000,000 970 *buffer++ = '0' + digits; 971 goto sublt100_000_000; 972} 973 974char* FastInt32ToBufferLeft(int32 i, char* buffer) { 975 uint32 u = i; 976 if (i < 0) { 977 *buffer++ = '-'; 978 u = -i; 979 } 980 return FastUInt32ToBufferLeft(u, buffer); 981} 982 983char* FastUInt64ToBufferLeft(uint64 u64, char* buffer) { 984 int digits; 985 const char *ASCII_digits = NULL; 986 987 uint32 u = static_cast<uint32>(u64); 988 if (u == u64) return FastUInt32ToBufferLeft(u, buffer); 989 990 uint64 top_11_digits = u64 / 1000000000; 991 buffer = FastUInt64ToBufferLeft(top_11_digits, buffer); 992 u = u64 - (top_11_digits * 1000000000); 993 994 digits = u / 10000000; // 10,000,000 995 GOOGLE_DCHECK_LT(digits, 100); 996 ASCII_digits = two_ASCII_digits[digits]; 997 buffer[0] = ASCII_digits[0]; 998 buffer[1] = ASCII_digits[1]; 999 buffer += 2; 1000 u -= digits * 10000000; // 10,000,000 1001 digits = u / 100000; // 100,000 1002 ASCII_digits = two_ASCII_digits[digits]; 1003 buffer[0] = ASCII_digits[0]; 1004 buffer[1] = ASCII_digits[1]; 1005 buffer += 2; 1006 u -= digits * 100000; // 100,000 1007 digits = u / 1000; // 1,000 1008 ASCII_digits = two_ASCII_digits[digits]; 1009 buffer[0] = ASCII_digits[0]; 1010 buffer[1] = ASCII_digits[1]; 1011 buffer += 2; 1012 u -= digits * 1000; // 1,000 1013 digits = u / 10; 1014 ASCII_digits = two_ASCII_digits[digits]; 1015 buffer[0] = ASCII_digits[0]; 1016 buffer[1] = ASCII_digits[1]; 1017 buffer += 2; 1018 u -= digits * 10; 1019 digits = u; 1020 *buffer++ = '0' + digits; 1021 *buffer = 0; 1022 return buffer; 1023} 1024 1025char* FastInt64ToBufferLeft(int64 i, char* buffer) { 1026 uint64 u = i; 1027 if (i < 0) { 1028 *buffer++ = '-'; 1029 u = -i; 1030 } 1031 return FastUInt64ToBufferLeft(u, buffer); 1032} 1033 1034// ---------------------------------------------------------------------- 1035// SimpleItoa() 1036// Description: converts an integer to a string. 1037// 1038// Return value: string 1039// ---------------------------------------------------------------------- 1040 1041string SimpleItoa(int i) { 1042 char buffer[kFastToBufferSize]; 1043 return (sizeof(i) == 4) ? 1044 FastInt32ToBuffer(i, buffer) : 1045 FastInt64ToBuffer(i, buffer); 1046} 1047 1048string SimpleItoa(unsigned int i) { 1049 char buffer[kFastToBufferSize]; 1050 return string(buffer, (sizeof(i) == 4) ? 1051 FastUInt32ToBufferLeft(i, buffer) : 1052 FastUInt64ToBufferLeft(i, buffer)); 1053} 1054 1055string SimpleItoa(long i) { 1056 char buffer[kFastToBufferSize]; 1057 return (sizeof(i) == 4) ? 1058 FastInt32ToBuffer(i, buffer) : 1059 FastInt64ToBuffer(i, buffer); 1060} 1061 1062string SimpleItoa(unsigned long i) { 1063 char buffer[kFastToBufferSize]; 1064 return string(buffer, (sizeof(i) == 4) ? 1065 FastUInt32ToBufferLeft(i, buffer) : 1066 FastUInt64ToBufferLeft(i, buffer)); 1067} 1068 1069string SimpleItoa(long long i) { 1070 char buffer[kFastToBufferSize]; 1071 return (sizeof(i) == 4) ? 1072 FastInt32ToBuffer(i, buffer) : 1073 FastInt64ToBuffer(i, buffer); 1074} 1075 1076string SimpleItoa(unsigned long long i) { 1077 char buffer[kFastToBufferSize]; 1078 return string(buffer, (sizeof(i) == 4) ? 1079 FastUInt32ToBufferLeft(i, buffer) : 1080 FastUInt64ToBufferLeft(i, buffer)); 1081} 1082 1083// ---------------------------------------------------------------------- 1084// SimpleDtoa() 1085// SimpleFtoa() 1086// DoubleToBuffer() 1087// FloatToBuffer() 1088// We want to print the value without losing precision, but we also do 1089// not want to print more digits than necessary. This turns out to be 1090// trickier than it sounds. Numbers like 0.2 cannot be represented 1091// exactly in binary. If we print 0.2 with a very large precision, 1092// e.g. "%.50g", we get "0.2000000000000000111022302462515654042363167". 1093// On the other hand, if we set the precision too low, we lose 1094// significant digits when printing numbers that actually need them. 1095// It turns out there is no precision value that does the right thing 1096// for all numbers. 1097// 1098// Our strategy is to first try printing with a precision that is never 1099// over-precise, then parse the result with strtod() to see if it 1100// matches. If not, we print again with a precision that will always 1101// give a precise result, but may use more digits than necessary. 1102// 1103// An arguably better strategy would be to use the algorithm described 1104// in "How to Print Floating-Point Numbers Accurately" by Steele & 1105// White, e.g. as implemented by David M. Gay's dtoa(). It turns out, 1106// however, that the following implementation is about as fast as 1107// DMG's code. Furthermore, DMG's code locks mutexes, which means it 1108// will not scale well on multi-core machines. DMG's code is slightly 1109// more accurate (in that it will never use more digits than 1110// necessary), but this is probably irrelevant for most users. 1111// 1112// Rob Pike and Ken Thompson also have an implementation of dtoa() in 1113// third_party/fmt/fltfmt.cc. Their implementation is similar to this 1114// one in that it makes guesses and then uses strtod() to check them. 1115// Their implementation is faster because they use their own code to 1116// generate the digits in the first place rather than use snprintf(), 1117// thus avoiding format string parsing overhead. However, this makes 1118// it considerably more complicated than the following implementation, 1119// and it is embedded in a larger library. If speed turns out to be 1120// an issue, we could re-implement this in terms of their 1121// implementation. 1122// ---------------------------------------------------------------------- 1123 1124string SimpleDtoa(double value) { 1125 char buffer[kDoubleToBufferSize]; 1126 return DoubleToBuffer(value, buffer); 1127} 1128 1129string SimpleFtoa(float value) { 1130 char buffer[kFloatToBufferSize]; 1131 return FloatToBuffer(value, buffer); 1132} 1133 1134static inline bool IsValidFloatChar(char c) { 1135 return ('0' <= c && c <= '9') || 1136 c == 'e' || c == 'E' || 1137 c == '+' || c == '-'; 1138} 1139 1140void DelocalizeRadix(char* buffer) { 1141 // Fast check: if the buffer has a normal decimal point, assume no 1142 // translation is needed. 1143 if (strchr(buffer, '.') != NULL) return; 1144 1145 // Find the first unknown character. 1146 while (IsValidFloatChar(*buffer)) ++buffer; 1147 1148 if (*buffer == '\0') { 1149 // No radix character found. 1150 return; 1151 } 1152 1153 // We are now pointing at the locale-specific radix character. Replace it 1154 // with '.'. 1155 *buffer = '.'; 1156 ++buffer; 1157 1158 if (!IsValidFloatChar(*buffer) && *buffer != '\0') { 1159 // It appears the radix was a multi-byte character. We need to remove the 1160 // extra bytes. 1161 char* target = buffer; 1162 do { ++buffer; } while (!IsValidFloatChar(*buffer) && *buffer != '\0'); 1163 memmove(target, buffer, strlen(buffer) + 1); 1164 } 1165} 1166 1167char* DoubleToBuffer(double value, char* buffer) { 1168 // DBL_DIG is 15 for IEEE-754 doubles, which are used on almost all 1169 // platforms these days. Just in case some system exists where DBL_DIG 1170 // is significantly larger -- and risks overflowing our buffer -- we have 1171 // this assert. 1172 GOOGLE_COMPILE_ASSERT(DBL_DIG < 20, DBL_DIG_is_too_big); 1173 1174 if (value == numeric_limits<double>::infinity()) { 1175 strcpy(buffer, "inf"); 1176 return buffer; 1177 } else if (value == -numeric_limits<double>::infinity()) { 1178 strcpy(buffer, "-inf"); 1179 return buffer; 1180 } else if (IsNaN(value)) { 1181 strcpy(buffer, "nan"); 1182 return buffer; 1183 } 1184 1185 int snprintf_result = 1186 snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG, value); 1187 1188 // The snprintf should never overflow because the buffer is significantly 1189 // larger than the precision we asked for. 1190 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize); 1191 1192 // We need to make parsed_value volatile in order to force the compiler to 1193 // write it out to the stack. Otherwise, it may keep the value in a 1194 // register, and if it does that, it may keep it as a long double instead 1195 // of a double. This long double may have extra bits that make it compare 1196 // unequal to "value" even though it would be exactly equal if it were 1197 // truncated to a double. 1198 volatile double parsed_value = strtod(buffer, NULL); 1199 if (parsed_value != value) { 1200 int snprintf_result = 1201 snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG+2, value); 1202 1203 // Should never overflow; see above. 1204 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize); 1205 } 1206 1207 DelocalizeRadix(buffer); 1208 return buffer; 1209} 1210 1211bool safe_strtof(const char* str, float* value) { 1212 char* endptr; 1213 errno = 0; // errno only gets set on errors 1214#if defined(_WIN32) || defined (__hpux) // has no strtof() 1215 *value = strtod(str, &endptr); 1216#else 1217 *value = strtof(str, &endptr); 1218#endif 1219 return *str != 0 && *endptr == 0 && errno == 0; 1220} 1221 1222char* FloatToBuffer(float value, char* buffer) { 1223 // FLT_DIG is 6 for IEEE-754 floats, which are used on almost all 1224 // platforms these days. Just in case some system exists where FLT_DIG 1225 // is significantly larger -- and risks overflowing our buffer -- we have 1226 // this assert. 1227 GOOGLE_COMPILE_ASSERT(FLT_DIG < 10, FLT_DIG_is_too_big); 1228 1229 if (value == numeric_limits<double>::infinity()) { 1230 strcpy(buffer, "inf"); 1231 return buffer; 1232 } else if (value == -numeric_limits<double>::infinity()) { 1233 strcpy(buffer, "-inf"); 1234 return buffer; 1235 } else if (IsNaN(value)) { 1236 strcpy(buffer, "nan"); 1237 return buffer; 1238 } 1239 1240 int snprintf_result = 1241 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG, value); 1242 1243 // The snprintf should never overflow because the buffer is significantly 1244 // larger than the precision we asked for. 1245 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kFloatToBufferSize); 1246 1247 float parsed_value; 1248 if (!safe_strtof(buffer, &parsed_value) || parsed_value != value) { 1249 int snprintf_result = 1250 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG+2, value); 1251 1252 // Should never overflow; see above. 1253 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kFloatToBufferSize); 1254 } 1255 1256 DelocalizeRadix(buffer); 1257 return buffer; 1258} 1259 1260string ToHex(uint64 num) { 1261 if (num == 0) { 1262 return string("0"); 1263 } 1264 1265 // Compute hex bytes in reverse order, writing to the back of the 1266 // buffer. 1267 char buf[16]; // No more than 16 hex digits needed. 1268 char* bufptr = buf + 16; 1269 static const char kHexChars[] = "0123456789abcdef"; 1270 while (num != 0) { 1271 *--bufptr = kHexChars[num & 0xf]; 1272 num >>= 4; 1273 } 1274 1275 return string(bufptr, buf + 16 - bufptr); 1276} 1277 1278} // namespace protobuf 1279} // namespace google 1280