base/string_number_conversions.cc

   1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/string_number_conversions.h"
   6
   7 #include <ctype.h>
   8 #include <errno.h>
   9 #include <stdlib.h>
  10 #include <wctype.h>
  11
  12 #include <limits>
  13
  14 #include "base/logging.h"
  15 #include "base/third_party/dmg_fp/dmg_fp.h"
  16 #include "base/utf_string_conversions.h"
  17
  18 namespace base {
  19
  20 namespace {
  21
  22 template <typename STR, typename INT, typename UINT, bool NEG>
  23 struct IntToStringT {
  24   // This is to avoid a compiler warning about unary minus on unsigned type.
  25   // For example, say you had the following code:
  26   //   template <typename INT>
  27   //   INT abs(INT value) { return value < 0 ? -value : value; }
  28   // Even though if INT is unsigned, it's impossible for value < 0, so the
  29   // unary minus will never be taken, the compiler will still generate a
  30   // warning.  We do a little specialization dance...
  31   template <typename INT2, typename UINT2, bool NEG2>
  32   struct ToUnsignedT {};
  33
  34   template <typename INT2, typename UINT2>
  35   struct ToUnsignedT<INT2, UINT2, false> {
  36     static UINT2 ToUnsigned(INT2 value) {
  37       return static_cast<UINT2>(value);
  38     }
  39   };
  40
  41   template <typename INT2, typename UINT2>
  42   struct ToUnsignedT<INT2, UINT2, true> {
  43     static UINT2 ToUnsigned(INT2 value) {
  44       return static_cast<UINT2>(value < 0 ? -value : value);
  45     }
  46   };
  47
  48   // This set of templates is very similar to the above templates, but
  49   // for testing whether an integer is negative.
  50   template <typename INT2, bool NEG2>
  51   struct TestNegT {};
  52   template <typename INT2>
  53   struct TestNegT<INT2, false> {
  54     static bool TestNeg(INT2 value) {
  55       // value is unsigned, and can never be negative.
  56       return false;
  57     }
  58   };
  59   template <typename INT2>
  60   struct TestNegT<INT2, true> {
  61     static bool TestNeg(INT2 value) {
  62       return value < 0;
  63     }
  64   };
  65
  66   static STR IntToString(INT value) {
  67     // log10(2) ~= 0.3 bytes needed per bit or per byte log10(2**8) ~= 2.4.
  68     // So round up to allocate 3 output characters per byte, plus 1 for '-'.
  69     const int kOutputBufSize = 3 * sizeof(INT) + 1;
  70
  71     // Allocate the whole string right away, we will right back to front, and
  72     // then return the substr of what we ended up using.
  73     STR outbuf(kOutputBufSize, 0);
  74
  75     bool is_neg = TestNegT<INT, NEG>::TestNeg(value);
  76     // Even though is_neg will never be true when INT is parameterized as
  77     // unsigned, even the presence of the unary operation causes a warning.
  78     UINT res = ToUnsignedT<INT, UINT, NEG>::ToUnsigned(value);
  79
  80     for (typename STR::iterator it = outbuf.end();;) {
  81       --it;
  82       DCHECK(it != outbuf.begin());
  83       *it = static_cast<typename STR::value_type>((res % 10) + '0');
  84       res /= 10;
  85
  86       // We're done..
  87       if (res == 0) {
  88         if (is_neg) {
  89           --it;
  90           DCHECK(it != outbuf.begin());
  91           *it = static_cast<typename STR::value_type>('-');
  92         }
  93         return STR(it, outbuf.end());
  94       }
  95     }
  96     NOTREACHED();
  97     return STR();
  98   }
  99 };
 100
 101 // Utility to convert a character to a digit in a given base
 102 template<typename CHAR, int BASE, bool BASE_LTE_10> class BaseCharToDigit {
 103 };
 104
 105 // Faster specialization for bases <= 10
 106 template<typename CHAR, int BASE> class BaseCharToDigit<CHAR, BASE, true> {
 107  public:
 108   static bool Convert(CHAR c, uint8* digit) {
 109     if (c >= '0' && c < '0' + BASE) {
 110       *digit = c - '0';
 111       return true;
 112     }
 113     return false;
 114   }
 115 };
 116
 117 // Specialization for bases where 10 < base <= 36
 118 template<typename CHAR, int BASE> class BaseCharToDigit<CHAR, BASE, false> {
 119  public:
 120   static bool Convert(CHAR c, uint8* digit) {
 121     if (c >= '0' && c <= '9') {
 122       *digit = c - '0';
 123     } else if (c >= 'a' && c < 'a' + BASE - 10) {
 124       *digit = c - 'a' + 10;
 125     } else if (c >= 'A' && c < 'A' + BASE - 10) {
 126       *digit = c - 'A' + 10;
 127     } else {
 128       return false;
 129     }
 130     return true;
 131   }
 132 };
 133
 134 template<int BASE, typename CHAR> bool CharToDigit(CHAR c, uint8* digit) {
 135   return BaseCharToDigit<CHAR, BASE, BASE <= 10>::Convert(c, digit);
 136 }
 137
 138 // There is an IsWhitespace for wchars defined in string_util.h, but it is
 139 // locale independent, whereas the functions we are replacing were
 140 // locale-dependent. TBD what is desired, but for the moment let's not introduce
 141 // a change in behaviour.
 142 template<typename CHAR> class WhitespaceHelper {
 143 };
 144
 145 template<> class WhitespaceHelper<char> {
 146  public:
 147   static bool Invoke(char c) {
 148     return 0 != isspace(static_cast<unsigned char>(c));
 149   }
 150 };
 151
 152 template<> class WhitespaceHelper<char16> {
 153  public:
 154   static bool Invoke(char16 c) {
 155     return 0 != iswspace(c);
 156   }
 157 };
 158
 159 template<typename CHAR> bool LocalIsWhitespace(CHAR c) {
 160   return WhitespaceHelper<CHAR>::Invoke(c);
 161 }
 162
 163 // IteratorRangeToNumberTraits should provide:
 164 //  - a typedef for iterator_type, the iterator type used as input.
 165 //  - a typedef for value_type, the target numeric type.
 166 //  - static functions min, max (returning the minimum and maximum permitted
 167 //    values)
 168 //  - constant kBase, the base in which to interpret the input
 169 template<typename IteratorRangeToNumberTraits>
 170 class IteratorRangeToNumber {
 171  public:
 172   typedef IteratorRangeToNumberTraits traits;
 173   typedef typename traits::iterator_type const_iterator;
 174   typedef typename traits::value_type value_type;
 175
 176   // Generalized iterator-range-to-number conversion.
 177   //
 178   static bool Invoke(const_iterator begin,
 179                      const_iterator end,
 180                      value_type* output) {
 181     bool valid = true;
 182
 183     while (begin != end && LocalIsWhitespace(*begin)) {
 184       valid = false;
 185       ++begin;
 186     }
 187
 188     if (begin != end && *begin == '-') {
 189       if (!Negative::Invoke(begin + 1, end, output)) {
 190         valid = false;
 191       }
 192     } else {
 193       if (begin != end && *begin == '+') {
 194         ++begin;
 195       }
 196       if (!Positive::Invoke(begin, end, output)) {
 197         valid = false;
 198       }
 199     }
 200
 201     return valid;
 202   }
 203
 204  private:
 205   // Sign provides:
 206   //  - a static function, CheckBounds, that determines whether the next digit
 207   //    causes an overflow/underflow
 208   //  - a static function, Increment, that appends the next digit appropriately
 209   //    according to the sign of the number being parsed.
 210   template<typename Sign>
 211   class Base {
 212    public:
 213     static bool Invoke(const_iterator begin, const_iterator end,
 214                        typename traits::value_type* output) {
 215       *output = 0;
 216
 217       if (begin == end) {
 218         return false;
 219       }
 220
 221       // Note: no performance difference was found when using template
 222       // specialization to remove this check in bases other than 16
 223       if (traits::kBase == 16 && end - begin > 2 && *begin == '0' &&
 224           (*(begin + 1) == 'x' || *(begin + 1) == 'X')) {
 225         begin += 2;
 226       }
 227
 228       for (const_iterator current = begin; current != end; ++current) {
 229         uint8 new_digit = 0;
 230
 231         if (!CharToDigit<traits::kBase>(*current, &new_digit)) {
 232           return false;
 233         }
 234
 235         if (current != begin) {
 236           if (!Sign::CheckBounds(output, new_digit)) {
 237             return false;
 238           }
 239           *output *= traits::kBase;
 240         }
 241
 242         Sign::Increment(new_digit, output);
 243       }
 244       return true;
 245     }
 246   };
 247
 248   class Positive : public Base<Positive> {
 249    public:
 250     static bool CheckBounds(value_type* output, uint8 new_digit) {
 251       if (*output > static_cast<value_type>(traits::max() / traits::kBase) ||
 252           (*output == static_cast<value_type>(traits::max() / traits::kBase) &&
 253            new_digit > traits::max() % traits::kBase)) {
 254         *output = traits::max();
 255         return false;
 256       }
 257       return true;
 258     }
 259     static void Increment(uint8 increment, value_type* output) {
 260       *output += increment;
 261     }
 262   };
 263
 264   class Negative : public Base<Negative> {
 265    public:
 266     static bool CheckBounds(value_type* output, uint8 new_digit) {
 267       if (*output < traits::min() / traits::kBase ||
 268           (*output == traits::min() / traits::kBase &&
 269            new_digit > 0 - traits::min() % traits::kBase)) {
 270         *output = traits::min();
 271         return false;
 272       }
 273       return true;
 274     }
 275     static void Increment(uint8 increment, value_type* output) {
 276       *output -= increment;
 277     }
 278   };
 279 };
 280
 281 template<typename ITERATOR, typename VALUE, int BASE>
 282 class BaseIteratorRangeToNumberTraits {
 283  public:
 284   typedef ITERATOR iterator_type;
 285   typedef VALUE value_type;
 286   static value_type min() {
 287     return std::numeric_limits<value_type>::min();
 288   }
 289   static value_type max() {
 290     return std::numeric_limits<value_type>::max();
 291   }
 292   static const int kBase = BASE;
 293 };
 294
 295 typedef BaseIteratorRangeToNumberTraits<std::string::const_iterator, int, 10>
 296     IteratorRangeToIntTraits;
 297 typedef BaseIteratorRangeToNumberTraits<string16::const_iterator, int, 10>
 298     WideIteratorRangeToIntTraits;
 299 typedef BaseIteratorRangeToNumberTraits<std::string::const_iterator, int64, 10>
 300     IteratorRangeToInt64Traits;
 301 typedef BaseIteratorRangeToNumberTraits<string16::const_iterator, int64, 10>
 302     WideIteratorRangeToInt64Traits;
 303
 304 typedef BaseIteratorRangeToNumberTraits<const char*, int, 10>
 305     CharBufferToIntTraits;
 306 typedef BaseIteratorRangeToNumberTraits<const char16*, int, 10>
 307     WideCharBufferToIntTraits;
 308 typedef BaseIteratorRangeToNumberTraits<const char*, int64, 10>
 309     CharBufferToInt64Traits;
 310 typedef BaseIteratorRangeToNumberTraits<const char16*, int64, 10>
 311     WideCharBufferToInt64Traits;
 312
 313 template<typename ITERATOR>
 314 class BaseHexIteratorRangeToIntTraits
 315     : public BaseIteratorRangeToNumberTraits<ITERATOR, int, 16> {
 316  public:
 317   // Allow parsing of 0xFFFFFFFF, which is technically an overflow
 318   static unsigned int max() {
 319     return std::numeric_limits<unsigned int>::max();
 320   }
 321 };
 322
 323 typedef BaseHexIteratorRangeToIntTraits<std::string::const_iterator>
 324     HexIteratorRangeToIntTraits;
 325 typedef BaseHexIteratorRangeToIntTraits<const char*>
 326     HexCharBufferToIntTraits;
 327
 328 template<typename STR>
 329 bool HexStringToBytesT(const STR& input, std::vector<uint8>* output) {
 330   DCHECK_EQ(output->size(), 0u);
 331   size_t count = input.size();
 332   if (count == 0 || (count % 2) != 0)
 333     return false;
 334   for (uintptr_t i = 0; i < count / 2; ++i) {
 335     uint8 msb = 0;  // most significant 4 bits
 336     uint8 lsb = 0;  // least significant 4 bits
 337     if (!CharToDigit<16>(input[i * 2], &msb) ||
 338         !CharToDigit<16>(input[i * 2 + 1], &lsb))
 339       return false;
 340     output->push_back((msb << 4) | lsb);
 341   }
 342   return true;
 343 }
 344
 345 }  // namespace
 346
 347 std::string IntToString(int value) {
 348   return IntToStringT<std::string, int, unsigned int, true>::
 349       IntToString(value);
 350 }
 351
 352 string16 IntToString16(int value) {
 353   return IntToStringT<string16, int, unsigned int, true>::
 354       IntToString(value);
 355 }
 356
 357 std::string UintToString(unsigned int value) {
 358   return IntToStringT<std::string, unsigned int, unsigned int, false>::
 359       IntToString(value);
 360 }
 361
 362 string16 UintToString16(unsigned int value) {
 363   return IntToStringT<string16, unsigned int, unsigned int, false>::
 364       IntToString(value);
 365 }
 366
 367 std::string Int64ToString(int64 value) {
 368   return IntToStringT<std::string, int64, uint64, true>::
 369       IntToString(value);
 370 }
 371
 372 string16 Int64ToString16(int64 value) {
 373   return IntToStringT<string16, int64, uint64, true>::IntToString(value);
 374 }
 375
 376 std::string Uint64ToString(uint64 value) {
 377   return IntToStringT<std::string, uint64, uint64, false>::
 378       IntToString(value);
 379 }
 380
 381 string16 Uint64ToString16(uint64 value) {
 382   return IntToStringT<string16, uint64, uint64, false>::
 383       IntToString(value);
 384 }
 385
 386 std::string DoubleToString(double value) {
 387   // According to g_fmt.cc, it is sufficient to declare a buffer of size 32.
 388   char buffer[32];
 389   dmg_fp::g_fmt(buffer, value);
 390   return std::string(buffer);
 391 }
 392
 393 bool StringToInt(const std::string& input, int* output) {
 394   return IteratorRangeToNumber<IteratorRangeToIntTraits>::Invoke(input.begin(),
 395                                                                  input.end(),
 396                                                                  output);
 397 }
 398
 399 bool StringToInt(std::string::const_iterator begin,
 400                  std::string::const_iterator end,
 401                  int* output) {
 402   return IteratorRangeToNumber<IteratorRangeToIntTraits>::Invoke(begin,
 403                                                                  end,
 404                                                                  output);
 405 }
 406
 407 #if !defined(STD_STRING_ITERATOR_IS_CHAR_POINTER)
 408 bool StringToInt(const char* begin, const char* end, int* output) {
 409   return IteratorRangeToNumber<CharBufferToIntTraits>::Invoke(begin,
 410                                                               end,
 411                                                               output);
 412 }
 413 #endif
 414
 415 bool StringToInt(const string16& input, int* output) {
 416   return IteratorRangeToNumber<WideIteratorRangeToIntTraits>::Invoke(
 417     input.begin(), input.end(), output);
 418 }
 419
 420 bool StringToInt(string16::const_iterator begin,
 421                  string16::const_iterator end,
 422                  int* output) {
 423   return IteratorRangeToNumber<WideIteratorRangeToIntTraits>::Invoke(begin,
 424                                                                      end,
 425                                                                      output);
 426 }
 427
 428 #if !defined(BASE_STRING16_ITERATOR_IS_CHAR16_POINTER)
 429 bool StringToInt(const char16* begin, const char16* end, int* output) {
 430   return IteratorRangeToNumber<WideCharBufferToIntTraits>::Invoke(begin,
 431                                                                   end,
 432                                                                   output);
 433 }
 434 #endif
 435
 436 bool StringToInt64(const std::string& input, int64* output) {
 437   return IteratorRangeToNumber<IteratorRangeToInt64Traits>::Invoke(
 438     input.begin(), input.end(), output);
 439 }
 440
 441 bool StringToInt64(std::string::const_iterator begin,
 442                  std::string::const_iterator end,
 443                  int64* output) {
 444   return IteratorRangeToNumber<IteratorRangeToInt64Traits>::Invoke(begin,
 445                                                                  end,
 446                                                                  output);
 447 }
 448
 449 #if !defined(STD_STRING_ITERATOR_IS_CHAR_POINTER)
 450 bool StringToInt64(const char* begin, const char* end, int64* output) {
 451   return IteratorRangeToNumber<CharBufferToInt64Traits>::Invoke(begin,
 452                                                               end,
 453                                                               output);
 454 }
 455 #endif
 456
 457 bool StringToInt64(const string16& input, int64* output) {
 458   return IteratorRangeToNumber<WideIteratorRangeToInt64Traits>::Invoke(
 459     input.begin(), input.end(), output);
 460 }
 461
 462 bool StringToInt64(string16::const_iterator begin,
 463                  string16::const_iterator end,
 464                  int64* output) {
 465   return IteratorRangeToNumber<WideIteratorRangeToInt64Traits>::Invoke(begin,
 466                                                                      end,
 467                                                                      output);
 468 }
 469
 470 #if !defined(BASE_STRING16_ITERATOR_IS_CHAR16_POINTER)
 471 bool StringToInt64(const char16* begin, const char16* end, int64* output) {
 472   return IteratorRangeToNumber<WideCharBufferToInt64Traits>::Invoke(begin,
 473                                                                   end,
 474                                                                   output);
 475 }
 476 #endif
 477
 478 bool StringToDouble(const std::string& input, double* output) {
 479   errno = 0;  // Thread-safe?  It is on at least Mac, Linux, and Windows.
 480   char* endptr = NULL;
 481   *output = dmg_fp::strtod(input.c_str(), &endptr);
 482
 483   // Cases to return false:
 484   //  - If errno is ERANGE, there was an overflow or underflow.
 485   //  - If the input string is empty, there was nothing to parse.
 486   //  - If endptr does not point to the end of the string, there are either
 487   //    characters remaining in the string after a parsed number, or the string
 488   //    does not begin with a parseable number.  endptr is compared to the
 489   //    expected end given the string's stated length to correctly catch cases
 490   //    where the string contains embedded NUL characters.
 491   //  - If the first character is a space, there was leading whitespace
 492   return errno == 0 &&
 493          !input.empty() &&
 494          input.c_str() + input.length() == endptr &&
 495          !isspace(input[0]);
 496 }
 497
 498 // Note: if you need to add String16ToDouble, first ask yourself if it's
 499 // really necessary. If it is, probably the best implementation here is to
 500 // convert to 8-bit and then use the 8-bit version.
 501
 502 // Note: if you need to add an iterator range version of StringToDouble, first
 503 // ask yourself if it's really necessary. If it is, probably the best
 504 // implementation here is to instantiate a string and use the string version.
 505
 506 std::string HexEncode(const void* bytes, size_t size) {
 507   static const char kHexChars[] = "0123456789ABCDEF";
 508
 509   // Each input byte creates two output hex characters.
 510   std::string ret(size * 2, '\0');
 511
 512   for (size_t i = 0; i < size; ++i) {
 513     char b = reinterpret_cast<const char*>(bytes)[i];
 514     ret[(i * 2)] = kHexChars[(b >> 4) & 0xf];
 515     ret[(i * 2) + 1] = kHexChars[b & 0xf];
 516   }
 517   return ret;
 518 }
 519
 520 bool HexStringToInt(const std::string& input, int* output) {
 521   return IteratorRangeToNumber<HexIteratorRangeToIntTraits>::Invoke(
 522     input.begin(), input.end(), output);
 523 }
 524
 525 bool HexStringToInt(std::string::const_iterator begin,
 526                     std::string::const_iterator end,
 527                     int* output) {
 528   return IteratorRangeToNumber<HexIteratorRangeToIntTraits>::Invoke(begin,
 529                                                                     end,
 530                                                                     output);
 531 }
 532
 533 #if !defined(STD_STRING_ITERATOR_IS_CHAR_POINTER)
 534 bool HexStringToInt(const char* begin, const char* end, int* output) {
 535   return IteratorRangeToNumber<HexCharBufferToIntTraits>::Invoke(begin,
 536                                                                     end,
 537                                                                     output);
 538 }
 539 #endif
 540
 541 bool HexStringToBytes(const std::string& input, std::vector<uint8>* output) {
 542   return HexStringToBytesT(input, output);
 543 }
 544
 545 }  // namespace base