1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
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
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.
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.
31 // from google3/strings/strutil.cc
33 #include <google/protobuf/stubs/strutil.h>
35 #include <float.h> // FLT_DIG and DBL_DIG
42 // MSVC has only _snprintf, not snprintf.
44 // MinGW has both snprintf and _snprintf, but they appear to be different
45 // functions. The former is buggy. When invoked like so:
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
58 inline bool IsNaN(double value) {
59 // NaN is never equal to anything, even itself.
60 return value != value;
63 // These are defined as macros on some platforms. #undef them so that we can
68 // The definitions of these in ctype.h change based on locale. Since our
69 // string manipulation is all in relation to the protocol buffer and C++
70 // languages, we always want to use the C locale. So, we re-define these
71 // exactly as we want them.
72 inline bool isxdigit(char c) {
73 return ('0' <= c && c <= '9') ||
74 ('a' <= c && c <= 'f') ||
75 ('A' <= c && c <= 'F');
78 inline bool isprint(char c) {
79 return c >= 0x20 && c <= 0x7E;
82 // ----------------------------------------------------------------------
84 // Replaces any occurrence of the character 'remove' (or the characters
85 // in 'remove') with the character 'replacewith'.
86 // ----------------------------------------------------------------------
87 void StripString(string* s, const char* remove, char replacewith) {
88 const char * str_start = s->c_str();
89 const char * str = str_start;
90 for (str = strpbrk(str, remove);
92 str = strpbrk(str + 1, remove)) {
93 (*s)[str - str_start] = replacewith;
97 // ----------------------------------------------------------------------
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 // ----------------------------------------------------------------------
104 void StringReplace(const string& s, const string& oldsub,
105 const string& newsub, bool replace_all,
107 if (oldsub.empty()) {
108 res->append(s); // if empty, append the given string.
112 string::size_type start_pos = 0;
113 string::size_type pos;
115 pos = s.find(oldsub, start_pos);
116 if (pos == string::npos) {
119 res->append(s, start_pos, pos - start_pos);
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);
126 // ----------------------------------------------------------------------
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
133 // ----------------------------------------------------------------------
135 string StringReplace(const string& s, const string& oldsub,
136 const string& newsub, bool replace_all) {
138 StringReplace(s, oldsub, newsub, replace_all, &ret);
142 // ----------------------------------------------------------------------
143 // SplitStringUsing()
144 // Split a string using a character delimiter. Append the components
147 // Note: For multi-character delimiters, this routine will split on *ANY* of
148 // the characters in the string, not the entire string as a single delimiter.
149 // ----------------------------------------------------------------------
150 template <typename ITR>
152 void SplitStringToIteratorUsing(const string& full,
155 // Optimize the common case where delim is a single character.
156 if (delim[0] != '\0' && delim[1] == '\0') {
158 const char* p = full.data();
159 const char* end = p + full.size();
164 const char* start = p;
165 while (++p != end && *p != c);
166 *result++ = string(start, p - start);
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);
180 *result++ = full.substr(begin_index, (end_index - begin_index));
181 begin_index = full.find_first_not_of(delim, end_index);
185 void SplitStringUsing(const string& full,
187 vector<string>* result) {
188 back_insert_iterator< vector<string> > it(*result);
189 SplitStringToIteratorUsing(full, delim, it);
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.
199 // If "full" is the empty string, yields an empty string as the only value.
201 // If "pieces" is negative for some reason, it returns the whole string
202 // ----------------------------------------------------------------------
203 template <typename StringType, typename ITR>
205 void SplitStringToIteratorAllowEmpty(const StringType& full,
209 string::size_type begin_index, end_index;
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);
218 *result++ = full.substr(begin_index, (end_index - begin_index));
219 begin_index = end_index + 1;
221 *result++ = full.substr(begin_index);
224 void SplitStringAllowEmpty(const string& full, const char* delim,
225 vector<string>* result) {
226 back_insert_iterator<vector<string> > it(*result);
227 SplitStringToIteratorAllowEmpty(full, delim, 0, it);
230 // ----------------------------------------------------------------------
232 // This merges a vector of string components with delim inserted
233 // as separaters between components.
235 // ----------------------------------------------------------------------
236 template <class ITERATOR>
237 static void JoinStringsIterator(const ITERATOR& start,
241 GOOGLE_CHECK(result != NULL);
243 int delim_length = strlen(delim);
245 // Precompute resulting length so we can reserve() memory in one shot.
247 for (ITERATOR iter = start; iter != end; ++iter) {
249 length += delim_length;
251 length += iter->size();
253 result->reserve(length);
255 // Now combine everything.
256 for (ITERATOR iter = start; iter != end; ++iter) {
258 result->append(delim, delim_length);
260 result->append(iter->data(), iter->size());
264 void JoinStrings(const vector<string>& components,
267 JoinStringsIterator(components.begin(), components.end(), delim, result);
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.
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 // ----------------------------------------------------------------------
282 #define IS_OCTAL_DIGIT(c) (((c) >= '0') && ((c) <= '7'))
284 inline int hex_digit_to_int(char c) {
286 assert('0' == 0x30 && 'A' == 0x41 && 'a' == 0x61);
288 int x = static_cast<unsigned char>(c);
295 // Protocol buffers doesn't ever care about errors, but I don't want to remove
297 #define LOG_STRING(LEVEL, VECTOR) GOOGLE_LOG_IF(LEVEL, false)
299 int UnescapeCEscapeSequences(const char* source, char* dest) {
300 return UnescapeCEscapeSequences(source, dest, NULL);
303 int UnescapeCEscapeSequences(const char* source, char* dest,
304 vector<string> *errors) {
305 GOOGLE_DCHECK(errors == NULL) << "Error reporting not implemented.";
308 const char* p = source;
310 // Small optimization for case where source = dest and there's no escaping
311 while ( p == d && *p != '\0' && *p != '\\' )
318 switch ( *++p ) { // skip past the '\\'
320 LOG_STRING(ERROR, errors) << "String cannot end with \\";
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': {
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
344 case 'x': case 'X': {
345 if (!isxdigit(p[1])) {
347 LOG_STRING(ERROR, errors) << "String cannot end with \\x";
349 LOG_STRING(ERROR, errors) <<
350 "\\x cannot be followed by non-hex digit: \\" << *p << p[1];
355 const char *hex_start = p;
356 while (isxdigit(p[1])) // arbitrarily many hex digits
357 ch = (ch << 4) + hex_digit_to_int(*++p);
359 LOG_STRING(ERROR, errors) << "Value of " <<
360 "\\" << string(hex_start, p+1-hex_start) << " exceeds 8 bits";
364 #if 0 // TODO(kenton): Support \u and \U? Requires runetochar().
366 // \uhhhh => convert 4 hex digits to UTF-8
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.
373 LOG_STRING(ERROR, errors)
374 << "\\u must be followed by 4 hex digits: \\"
375 << string(hex_start, p+1-hex_start);
379 d += runetochar(d, &rune);
383 // \Uhhhhhhhh => convert 8 hex digits to UTF-8
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)
394 << string(hex_start, p + 1 - hex_start)
395 << " exceeds Unicode limit (0x10FFFF)";
401 LOG_STRING(ERROR, errors)
402 << "\\U must be followed by 8 hex digits: \\"
403 << string(hex_start, p+1-hex_start);
407 d += runetochar(d, &rune);
412 LOG_STRING(ERROR, errors) << "Unknown escape sequence: \\" << *p;
414 p++; // read past letter we escaped
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
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().
432 // In the first and second calls, the length of dest is returned. In the
433 // the third call, the new string is returned.
434 // ----------------------------------------------------------------------
435 int UnescapeCEscapeString(const string& src, string* dest) {
436 return UnescapeCEscapeString(src, dest, NULL);
439 int UnescapeCEscapeString(const string& src, string* dest,
440 vector<string> *errors) {
441 scoped_array<char> unescaped(new char[src.size() + 1]);
442 int len = UnescapeCEscapeSequences(src.c_str(), unescaped.get(), errors);
444 dest->assign(unescaped.get(), len);
448 string UnescapeCEscapeString(const string& src) {
449 scoped_array<char> unescaped(new char[src.size() + 1]);
450 int len = UnescapeCEscapeSequences(src.c_str(), unescaped.get(), NULL);
451 return string(unescaped.get(), len);
454 // ----------------------------------------------------------------------
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.
464 // Currently only \n, \r, \t, ", ', \ and !isprint() chars are escaped.
465 // ----------------------------------------------------------------------
466 int CEscapeInternal(const char* src, int src_len, char* dest,
467 int dest_len, bool use_hex, bool utf8_safe) {
468 const char* src_end = src + src_len;
470 bool last_hex_escape = false; // true if last output char was \xNN
472 for (; src < src_end; src++) {
473 if (dest_len - used < 2) // Need space for two letter escape
476 bool is_hex_escape = false;
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;
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) &&
490 (last_hex_escape && isxdigit(*src)))) {
491 if (dest_len - used < 4) // need space for 4 letter escape
493 sprintf(dest + used, (use_hex ? "\\x%02x" : "\\%03o"),
494 static_cast<uint8>(*src));
495 is_hex_escape = use_hex;
498 dest[used++] = *src; break;
501 last_hex_escape = is_hex_escape;
504 if (dest_len - used < 1) // make sure that there is room for \0
507 dest[used] = '\0'; // doesn't count towards return value though
511 int CEscapeString(const char* src, int src_len, char* dest, int dest_len) {
512 return CEscapeInternal(src, src_len, dest, dest_len, false, false);
515 // ----------------------------------------------------------------------
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.
523 // Currently only \n, \r, \t, ", ', \ and !isprint() chars are escaped.
524 // ----------------------------------------------------------------------
525 string CEscape(const string& src) {
526 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion
527 scoped_array<char> dest(new char[dest_length]);
528 const int len = CEscapeInternal(src.data(), src.size(),
529 dest.get(), dest_length, false, false);
530 GOOGLE_DCHECK_GE(len, 0);
531 return string(dest.get(), len);
536 string Utf8SafeCEscape(const string& src) {
537 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion
538 scoped_array<char> dest(new char[dest_length]);
539 const int len = CEscapeInternal(src.data(), src.size(),
540 dest.get(), dest_length, false, true);
541 GOOGLE_DCHECK_GE(len, 0);
542 return string(dest.get(), len);
545 string CHexEscape(const string& src) {
546 const int dest_length = src.size() * 4 + 1; // Maximum possible expansion
547 scoped_array<char> dest(new char[dest_length]);
548 const int len = CEscapeInternal(src.data(), src.size(),
549 dest.get(), dest_length, true, false);
550 GOOGLE_DCHECK_GE(len, 0);
551 return string(dest.get(), len);
554 } // namespace strings
556 // ----------------------------------------------------------------------
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 // ----------------------------------------------------------------------
564 int32 strto32_adaptor(const char *nptr, char **endptr, int base) {
565 const int saved_errno = errno;
567 const long result = strtol(nptr, endptr, base);
568 if (errno == ERANGE && result == LONG_MIN) {
570 } else if (errno == ERANGE && result == LONG_MAX) {
572 } else if (errno == 0 && result < kint32min) {
575 } else if (errno == 0 && result > kint32max) {
581 return static_cast<int32>(result);
584 uint32 strtou32_adaptor(const char *nptr, char **endptr, int base) {
585 const int saved_errno = errno;
587 const unsigned long result = strtoul(nptr, endptr, base);
588 if (errno == ERANGE && result == ULONG_MAX) {
590 } else if (errno == 0 && result > kuint32max) {
596 return static_cast<uint32>(result);
599 inline 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();
604 // Consume whitespace.
605 while (start < end && (start[0] == ' ')) {
608 while (start < end && (end[-1] == ' ')) {
616 *negative_ptr = (start[0] == '-');
617 if (*negative_ptr || start[0] == '+') {
623 *text = text->substr(start - text->data(), end - start);
627 inline bool safe_parse_positive_int(
628 string text, int32* value_p) {
631 const int32 vmax = std::numeric_limits<int32>::max();
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();
638 for (; start < end; ++start) {
639 unsigned char c = static_cast<unsigned char>(start[0]);
641 if (digit >= base || digit < 0) {
645 if (value > vmax_over_base) {
650 if (value > vmax - digit) {
660 inline bool safe_parse_negative_int(
661 string text, int32* value_p) {
664 const int32 vmin = std::numeric_limits<int32>::min();
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) {
675 const char* start = text.data();
676 const char* end = start + text.size();
678 for (; start < end; ++start) {
679 unsigned char c = static_cast<unsigned char>(start[0]);
681 if (digit >= base || digit < 0) {
685 if (value < vmin_over_base) {
690 if (value < vmin + digit) {
700 bool safe_int(string text, int32* value_p) {
703 if (!safe_parse_sign(&text, &negative)) {
707 return safe_parse_positive_int(text, value_p);
709 return safe_parse_negative_int(text, value_p);
713 // ----------------------------------------------------------------------
715 // FastInt64ToBuffer()
717 // FastHex64ToBuffer()
718 // FastHex32ToBuffer()
719 // ----------------------------------------------------------------------
721 // Offset into buffer where FastInt64ToBuffer places the end of string
722 // null character. Also used by FastInt64ToBufferLeft.
723 static const int kFastInt64ToBufferOffset = 21;
725 char *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;
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.
747 // Make sure we aren't at MIN_INT, in which case we can't say i = -i
751 // Undo what we did a moment ago
763 // Offset into buffer where FastInt32ToBuffer places the end of string
764 // null character. Also used by FastInt32ToBufferLeft
765 static const int kFastInt32ToBufferOffset = 11;
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.
770 char *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;
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.
792 // Make sure we aren't at MIN_INT, in which case we can't say i = -i
796 // Undo what we did a moment ago
808 char *FastHexToBuffer(int i, char* buffer) {
809 GOOGLE_CHECK(i >= 0) << "FastHexToBuffer() wants non-negative integers, not " << i;
811 static const char *hexdigits = "0123456789abcdef";
812 char *p = buffer + 21;
815 *p-- = hexdigits[i & 15]; // mod by 16
816 i >>= 4; // divide by 16
821 char *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--) {
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];
831 buffer[i] = hexdigits[uint32(value) & 0xf];
838 char *FastHex64ToBuffer(uint64 value, char* buffer) {
839 return InternalFastHexToBuffer(value, buffer, 16);
842 char *FastHex32ToBuffer(uint32 value, char* buffer) {
843 return InternalFastHexToBuffer(value, buffer, 8);
846 static inline char* PlaceNum(char* p, int num, char prev_sep) {
847 *p-- = '0' + num % 10;
848 *p-- = '0' + num / 10;
853 // ----------------------------------------------------------------------
854 // FastInt32ToBufferLeft()
855 // FastUInt32ToBufferLeft()
856 // FastInt64ToBufferLeft()
857 // FastUInt64ToBufferLeft()
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.
865 // Returns a pointer to the end of the string (i.e. the null character
866 // terminating the string).
867 // ----------------------------------------------------------------------
869 static 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'}
892 char* FastUInt32ToBufferLeft(uint32 u, char* buffer) {
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];
908 u -= digits * 100000000; // 100,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];
916 u -= digits * 1000000; // 1,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];
924 u -= digits * 10000; // 10,000
927 ASCII_digits = two_ASCII_digits[digits];
928 buffer[0] = ASCII_digits[0];
929 buffer[1] = ASCII_digits[1];
935 ASCII_digits = two_ASCII_digits[digits];
936 buffer[0] = ASCII_digits[0];
937 buffer[1] = ASCII_digits[1];
946 if (u >= 10) goto lt100;
947 *buffer++ = '0' + digits;
950 if (u < 10000) { // 10,000
951 if (u >= 1000) goto lt10_000;
953 *buffer++ = '0' + digits;
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;
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;
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;
974 char* FastInt32ToBufferLeft(int32 i, char* buffer) {
980 return FastUInt32ToBufferLeft(u, buffer);
983 char* FastUInt64ToBufferLeft(uint64 u64, char* buffer) {
985 const char *ASCII_digits = NULL;
987 uint32 u = static_cast<uint32>(u64);
988 if (u == u64) return FastUInt32ToBufferLeft(u, buffer);
990 uint64 top_11_digits = u64 / 1000000000;
991 buffer = FastUInt64ToBufferLeft(top_11_digits, buffer);
992 u = u64 - (top_11_digits * 1000000000);
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];
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];
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];
1012 u -= digits * 1000; // 1,000
1014 ASCII_digits = two_ASCII_digits[digits];
1015 buffer[0] = ASCII_digits[0];
1016 buffer[1] = ASCII_digits[1];
1020 *buffer++ = '0' + digits;
1025 char* FastInt64ToBufferLeft(int64 i, char* buffer) {
1031 return FastUInt64ToBufferLeft(u, buffer);
1034 // ----------------------------------------------------------------------
1036 // Description: converts an integer to a string.
1038 // Return value: string
1039 // ----------------------------------------------------------------------
1041 string SimpleItoa(int i) {
1042 char buffer[kFastToBufferSize];
1043 return (sizeof(i) == 4) ?
1044 FastInt32ToBuffer(i, buffer) :
1045 FastInt64ToBuffer(i, buffer);
1048 string SimpleItoa(unsigned int i) {
1049 char buffer[kFastToBufferSize];
1050 return string(buffer, (sizeof(i) == 4) ?
1051 FastUInt32ToBufferLeft(i, buffer) :
1052 FastUInt64ToBufferLeft(i, buffer));
1055 string SimpleItoa(long i) {
1056 char buffer[kFastToBufferSize];
1057 return (sizeof(i) == 4) ?
1058 FastInt32ToBuffer(i, buffer) :
1059 FastInt64ToBuffer(i, buffer);
1062 string SimpleItoa(unsigned long i) {
1063 char buffer[kFastToBufferSize];
1064 return string(buffer, (sizeof(i) == 4) ?
1065 FastUInt32ToBufferLeft(i, buffer) :
1066 FastUInt64ToBufferLeft(i, buffer));
1069 string SimpleItoa(long long i) {
1070 char buffer[kFastToBufferSize];
1071 return (sizeof(i) == 4) ?
1072 FastInt32ToBuffer(i, buffer) :
1073 FastInt64ToBuffer(i, buffer);
1076 string SimpleItoa(unsigned long long i) {
1077 char buffer[kFastToBufferSize];
1078 return string(buffer, (sizeof(i) == 4) ?
1079 FastUInt32ToBufferLeft(i, buffer) :
1080 FastUInt64ToBufferLeft(i, buffer));
1083 // ----------------------------------------------------------------------
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
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.
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.
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
1122 // ----------------------------------------------------------------------
1124 string SimpleDtoa(double value) {
1125 char buffer[kDoubleToBufferSize];
1126 return DoubleToBuffer(value, buffer);
1129 string SimpleFtoa(float value) {
1130 char buffer[kFloatToBufferSize];
1131 return FloatToBuffer(value, buffer);
1134 static inline bool IsValidFloatChar(char c) {
1135 return ('0' <= c && c <= '9') ||
1136 c == 'e' || c == 'E' ||
1137 c == '+' || c == '-';
1140 void 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;
1145 // Find the first unknown character.
1146 while (IsValidFloatChar(*buffer)) ++buffer;
1148 if (*buffer == '\0') {
1149 // No radix character found.
1153 // We are now pointing at the locale-specific radix character. Replace it
1158 if (!IsValidFloatChar(*buffer) && *buffer != '\0') {
1159 // It appears the radix was a multi-byte character. We need to remove the
1161 char* target = buffer;
1162 do { ++buffer; } while (!IsValidFloatChar(*buffer) && *buffer != '\0');
1163 memmove(target, buffer, strlen(buffer) + 1);
1167 char* 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
1172 GOOGLE_COMPILE_ASSERT(DBL_DIG < 20, DBL_DIG_is_too_big);
1174 if (value == numeric_limits<double>::infinity()) {
1175 strcpy(buffer, "inf");
1177 } else if (value == -numeric_limits<double>::infinity()) {
1178 strcpy(buffer, "-inf");
1180 } else if (IsNaN(value)) {
1181 strcpy(buffer, "nan");
1185 int snprintf_result =
1186 snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG, value);
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);
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);
1203 // Should never overflow; see above.
1204 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize);
1207 DelocalizeRadix(buffer);
1211 bool safe_strtof(const char* str, float* value) {
1213 errno = 0; // errno only gets set on errors
1214 #if defined(_WIN32) || defined (__hpux) // has no strtof()
1215 *value = strtod(str, &endptr);
1217 *value = strtof(str, &endptr);
1219 return *str != 0 && *endptr == 0 && errno == 0;
1222 char* 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
1227 GOOGLE_COMPILE_ASSERT(FLT_DIG < 10, FLT_DIG_is_too_big);
1229 if (value == numeric_limits<double>::infinity()) {
1230 strcpy(buffer, "inf");
1232 } else if (value == -numeric_limits<double>::infinity()) {
1233 strcpy(buffer, "-inf");
1235 } else if (IsNaN(value)) {
1236 strcpy(buffer, "nan");
1240 int snprintf_result =
1241 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG, value);
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);
1248 if (!safe_strtof(buffer, &parsed_value) || parsed_value != value) {
1249 int snprintf_result =
1250 snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG+2, value);
1252 // Should never overflow; see above.
1253 GOOGLE_DCHECK(snprintf_result > 0 && snprintf_result < kFloatToBufferSize);
1256 DelocalizeRadix(buffer);
1260 string ToHex(uint64 num) {
1265 // Compute hex bytes in reverse order, writing to the back of the
1267 char buf[16]; // No more than 16 hex digits needed.
1268 char* bufptr = buf + 16;
1269 static const char kHexChars[] = "0123456789abcdef";
1271 *--bufptr = kHexChars[num & 0xf];
1275 return string(bufptr, buf + 16 - bufptr);
1278 } // namespace protobuf
1279 } // namespace google