folly/Conv.h

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * Converts anything to anything, with an emphasis on performance and
  19  * safety.
  20  *
  21  * @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  22  */
  23
  24 #ifndef FOLLY_BASE_CONV_H_
  25 #define FOLLY_BASE_CONV_H_
  26
  27 #include "folly/FBString.h"
  28 #include "folly/Likely.h"
  29 #include "folly/Preprocessor.h"
  30 #include "folly/Range.h"
  31
  32 #include <boost/implicit_cast.hpp>
  33 #include <type_traits>
  34 #include <limits>
  35 #include <string>
  36 #include <tuple>
  37 #include <stdexcept>
  38 #include <typeinfo>
  39
  40 #include <limits.h>
  41
  42 #include "double-conversion.h"   // V8 JavaScript implementation
  43
  44 #define FOLLY_RANGE_CHECK(condition, message)                           \
  45   ((condition) ? (void)0 : throw std::range_error(                      \
  46     (__FILE__ "(" + std::to_string((long long int) __LINE__) + "): "    \
  47      + (message)).c_str()))
  48
  49 namespace folly {
  50
  51 /*******************************************************************************
  52  * Integral to integral
  53  ******************************************************************************/
  54
  55 /**
  56  * Checked conversion from integral to integral. The checks are only
  57  * performed when meaningful, e.g. conversion from int to long goes
  58  * unchecked.
  59  */
  60 template <class Tgt, class Src>
  61 typename std::enable_if<
  62   std::is_integral<Src>::value && std::is_integral<Tgt>::value,
  63   Tgt>::type
  64 to(const Src & value) {
  65   /* static */ if (std::numeric_limits<Tgt>::max()
  66                    < std::numeric_limits<Src>::max()) {
  67     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
  68                       "Overflow");
  69   }
  70   /* static */ if (std::is_signed<Src>::value &&
  71                    (!std::is_signed<Tgt>::value || sizeof(Src) > sizeof(Tgt))) {
  72     FOLLY_RANGE_CHECK(value >= std::numeric_limits<Tgt>::min(),
  73                       "Negative overflow");
  74   }
  75   return static_cast<Tgt>(value);
  76 }
  77
  78 /*******************************************************************************
  79  * Floating point to floating point
  80  ******************************************************************************/
  81
  82 template <class Tgt, class Src>
  83 typename std::enable_if<
  84   std::is_floating_point<Tgt>::value && std::is_floating_point<Src>::value,
  85   Tgt>::type
  86 to(const Src & value) {
  87   /* static */ if (std::numeric_limits<Tgt>::max() <
  88                    std::numeric_limits<Src>::max()) {
  89     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
  90                       "Overflow");
  91     FOLLY_RANGE_CHECK(value >= -std::numeric_limits<Tgt>::max(),
  92                       "Negative overflow");
  93   }
  94   return boost::implicit_cast<Tgt>(value);
  95 }
  96
  97 /*******************************************************************************
  98  * Anything to string
  99  ******************************************************************************/
 100
 101 namespace detail {
 102
 103 template <class T> struct IsSomeString {
 104   enum { value = std::is_same<T, std::string>::value
 105          || std::is_same<T, fbstring>::value };
 106 };
 107
 108 template <class T>
 109 const T& getLastElement(const T & v) {
 110   return v;
 111 }
 112
 113 template <class T, class... Ts>
 114 typename std::tuple_element<
 115   sizeof...(Ts),
 116   std::tuple<T, Ts...> >::type const&
 117   getLastElement(const T& v, const Ts&... vs) {
 118   return getLastElement(vs...);
 119 }
 120
 121 } // namespace detail
 122
 123 /*******************************************************************************
 124  * Conversions from integral types to string types.
 125  ******************************************************************************/
 126
 127 #if FOLLY_HAVE_INT128_T
 128 namespace detail {
 129
 130 template <typename IntegerType>
 131 constexpr unsigned int
 132 digitsEnough() {
 133   return ceil((double(sizeof(IntegerType) * CHAR_BIT) * M_LN2) / M_LN10);
 134 }
 135
 136 inline unsigned int
 137 unsafeTelescope128(char * buffer, unsigned int room, unsigned __int128 x) {
 138   typedef unsigned __int128 Usrc;
 139   unsigned int p = room - 1;
 140
 141   while (x >= (Usrc(1) << 64)) { // Using 128-bit division while needed
 142     const auto y = x / 10;
 143     const auto digit = x % 10;
 144
 145     buffer[p--] = '0' + digit;
 146     x = y;
 147   }
 148
 149   uint64_t xx = x; // Moving to faster 64-bit division thereafter
 150
 151   while (xx >= 10) {
 152     const auto y = xx / 10ULL;
 153     const auto digit = xx % 10ULL;
 154
 155     buffer[p--] = '0' + digit;
 156     xx = y;
 157   }
 158
 159   buffer[p] = '0' + xx;
 160
 161   return p;
 162 }
 163
 164 }
 165 #endif
 166
 167 /**
 168  * Returns the number of digits in the base 10 representation of an
 169  * uint64_t. Useful for preallocating buffers and such. It's also used
 170  * internally, see below. Measurements suggest that defining a
 171  * separate overload for 32-bit integers is not worthwhile.
 172  */
 173
 174 inline uint32_t digits10(uint64_t v) {
 175   uint32_t result = 1;
 176   for (;;) {
 177     if (LIKELY(v < 10)) return result;
 178     if (LIKELY(v < 100)) return result + 1;
 179     if (LIKELY(v < 1000)) return result + 2;
 180     if (LIKELY(v < 10000)) return result + 3;
 181     // Skip ahead by 4 orders of magnitude
 182     v /= 10000U;
 183     result += 4;
 184   }
 185 }
 186
 187 /**
 188  * Copies the ASCII base 10 representation of v into buffer and
 189  * returns the number of bytes written. Does NOT append a \0. Assumes
 190  * the buffer points to digits10(v) bytes of valid memory. Note that
 191  * uint64 needs at most 20 bytes, uint32_t needs at most 10 bytes,
 192  * uint16_t needs at most 5 bytes, and so on. Measurements suggest
 193  * that defining a separate overload for 32-bit integers is not
 194  * worthwhile.
 195  *
 196  * This primitive is unsafe because it makes the size assumption and
 197  * because it does not add a terminating \0.
 198  */
 199
 200 inline uint32_t uint64ToBufferUnsafe(uint64_t v, char *const buffer) {
 201   auto const result = digits10(v);
 202   // WARNING: using size_t or pointer arithmetic for pos slows down
 203   // the loop below 20x. This is because several 32-bit ops can be
 204   // done in parallel, but only fewer 64-bit ones.
 205   uint32_t pos = result - 1;
 206   while (v >= 10) {
 207     // Keep these together so a peephole optimization "sees" them and
 208     // computes them in one shot.
 209     auto const q = v / 10;
 210     auto const r = static_cast<uint32_t>(v % 10);
 211     buffer[pos--] = '0' + r;
 212     v = q;
 213   }
 214   // Last digit is trivial to handle
 215   buffer[pos] = static_cast<uint32_t>(v) + '0';
 216   return result;
 217 }
 218
 219 /**
 220  * A single char gets appended.
 221  */
 222 template <class Tgt>
 223 void toAppend(char value, Tgt * result) {
 224   *result += value;
 225 }
 226
 227 /**
 228  * Everything implicitly convertible to const char* gets appended.
 229  */
 230 template <class Tgt, class Src>
 231 typename std::enable_if<
 232   std::is_convertible<Src, const char*>::value
 233   && detail::IsSomeString<Tgt>::value>::type
 234 toAppend(Src value, Tgt * result) {
 235   // Treat null pointers like an empty string, as in:
 236   // operator<<(std::ostream&, const char*).
 237   const char* c = value;
 238   if (c) {
 239     result->append(value);
 240   }
 241 }
 242
 243 /**
 244  * Strings get appended, too.
 245  */
 246 template <class Tgt, class Src>
 247 typename std::enable_if<
 248   detail::IsSomeString<Src>::value && detail::IsSomeString<Tgt>::value>::type
 249 toAppend(const Src& value, Tgt * result) {
 250   result->append(value);
 251 }
 252
 253 /**
 254  * and StringPiece objects too
 255  */
 256 template <class Tgt>
 257 typename std::enable_if<
 258    detail::IsSomeString<Tgt>::value>::type
 259 toAppend(StringPiece value, Tgt * result) {
 260   result->append(value.data(), value.size());
 261 }
 262
 263 /**
 264  * There's no implicit conversion from fbstring to other string types,
 265  * so make a specialization.
 266  */
 267 template <class Tgt>
 268 typename std::enable_if<
 269    detail::IsSomeString<Tgt>::value>::type
 270 toAppend(const fbstring& value, Tgt * result) {
 271   result->append(value.data(), value.size());
 272 }
 273
 274 #if FOLLY_HAVE_INT128_T
 275 /**
 276  * Special handling for 128 bit integers.
 277  */
 278
 279 template <class Tgt>
 280 void
 281 toAppend(__int128 value, Tgt * result) {
 282   typedef unsigned __int128 Usrc;
 283   char buffer[detail::digitsEnough<unsigned __int128>() + 1];
 284   unsigned int p;
 285
 286   if (value < 0) {
 287     p = detail::unsafeTelescope128(buffer, sizeof(buffer), Usrc(-value));
 288     buffer[--p] = '-';
 289   } else {
 290     p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
 291   }
 292
 293   result->append(buffer + p, buffer + sizeof(buffer));
 294 }
 295
 296 template <class Tgt>
 297 void
 298 toAppend(unsigned __int128 value, Tgt * result) {
 299   char buffer[detail::digitsEnough<unsigned __int128>()];
 300   unsigned int p;
 301
 302   p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
 303
 304   result->append(buffer + p, buffer + sizeof(buffer));
 305 }
 306
 307 #endif
 308
 309 /**
 310  * int32_t and int64_t to string (by appending) go through here. The
 311  * result is APPENDED to a preexisting string passed as the second
 312  * parameter. This should be efficient with fbstring because fbstring
 313  * incurs no dynamic allocation below 23 bytes and no number has more
 314  * than 22 bytes in its textual representation (20 for digits, one for
 315  * sign, one for the terminating 0).
 316  */
 317 template <class Tgt, class Src>
 318 typename std::enable_if<
 319   std::is_integral<Src>::value && std::is_signed<Src>::value &&
 320   detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 321 toAppend(Src value, Tgt * result) {
 322   typedef typename std::make_unsigned<Src>::type Usrc;
 323   char buffer[20];
 324   if (value < 0) {
 325     result->push_back('-');
 326     result->append(buffer, uint64ToBufferUnsafe(-uint64_t(value), buffer));
 327   } else {
 328     result->append(buffer, uint64ToBufferUnsafe(value, buffer));
 329   }
 330 }
 331
 332 /**
 333  * As above, but for uint32_t and uint64_t.
 334  */
 335 template <class Tgt, class Src>
 336 typename std::enable_if<
 337   std::is_integral<Src>::value && !std::is_signed<Src>::value
 338   && detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 339 toAppend(Src value, Tgt * result) {
 340   char buffer[20];
 341   result->append(buffer, buffer + uint64ToBufferUnsafe(value, buffer));
 342 }
 343
 344 /**
 345  * All small signed and unsigned integers to string go through 32-bit
 346  * types int32_t and uint32_t, respectively.
 347  */
 348 template <class Tgt, class Src>
 349 typename std::enable_if<
 350   std::is_integral<Src>::value
 351   && detail::IsSomeString<Tgt>::value && sizeof(Src) < 4>::type
 352 toAppend(Src value, Tgt * result) {
 353   typedef typename
 354     std::conditional<std::is_signed<Src>::value, int64_t, uint64_t>::type
 355     Intermediate;
 356   toAppend<Tgt>(static_cast<Intermediate>(value), result);
 357 }
 358
 359 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
 360 // std::underlying_type became available by gcc 4.7.0
 361
 362 /**
 363  * Enumerated values get appended as integers.
 364  */
 365 template <class Tgt, class Src>
 366 typename std::enable_if<
 367   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 368 toAppend(Src value, Tgt * result) {
 369   toAppend(
 370       static_cast<typename std::underlying_type<Src>::type>(value), result);
 371 }
 372
 373 #else
 374
 375 /**
 376  * Enumerated values get appended as integers.
 377  */
 378 template <class Tgt, class Src>
 379 typename std::enable_if<
 380   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 381 toAppend(Src value, Tgt * result) {
 382   /* static */ if (Src(-1) < 0) {
 383     /* static */ if (sizeof(Src) <= sizeof(int)) {
 384       toAppend(static_cast<int>(value), result);
 385     } else {
 386       toAppend(static_cast<long>(value), result);
 387     }
 388   } else {
 389     /* static */ if (sizeof(Src) <= sizeof(int)) {
 390       toAppend(static_cast<unsigned int>(value), result);
 391     } else {
 392       toAppend(static_cast<unsigned long>(value), result);
 393     }
 394   }
 395 }
 396
 397 #endif // gcc 4.7 onwards
 398
 399 /*******************************************************************************
 400  * Conversions from floating-point types to string types.
 401  ******************************************************************************/
 402
 403 /** Wrapper around DoubleToStringConverter **/
 404 template <class Tgt, class Src>
 405 typename std::enable_if<
 406   std::is_floating_point<Src>::value
 407   && detail::IsSomeString<Tgt>::value>::type
 408 toAppend(
 409   Src value,
 410   Tgt * result,
 411   double_conversion::DoubleToStringConverter::DtoaMode mode,
 412   unsigned int numDigits) {
 413   using namespace double_conversion;
 414   DoubleToStringConverter
 415     conv(DoubleToStringConverter::NO_FLAGS,
 416          "infinity", "NaN", 'E',
 417          -6,  // decimal in shortest low
 418          21,  // decimal in shortest high
 419          6,   // max leading padding zeros
 420          1);  // max trailing padding zeros
 421   char buffer[256];
 422   StringBuilder builder(buffer, sizeof(buffer));
 423   switch (mode) {
 424     case DoubleToStringConverter::SHORTEST:
 425       conv.ToShortest(value, &builder);
 426       break;
 427     case DoubleToStringConverter::FIXED:
 428       conv.ToFixed(value, numDigits, &builder);
 429       break;
 430     default:
 431       CHECK(mode == DoubleToStringConverter::PRECISION);
 432       conv.ToPrecision(value, numDigits, &builder);
 433       break;
 434   }
 435   const size_t length = builder.position();
 436   builder.Finalize();
 437   result->append(buffer, length);
 438 }
 439
 440 /**
 441  * As above, but for floating point
 442  */
 443 template <class Tgt, class Src>
 444 typename std::enable_if<
 445   std::is_floating_point<Src>::value
 446   && detail::IsSomeString<Tgt>::value>::type
 447 toAppend(Src value, Tgt * result) {
 448   toAppend(
 449     value, result, double_conversion::DoubleToStringConverter::SHORTEST, 0);
 450 }
 451
 452 /**
 453  * Variadic conversion to string. Appends each element in turn.
 454  */
 455 template <class T, class... Ts>
 456 typename std::enable_if<sizeof...(Ts) >= 2
 457   && detail::IsSomeString<
 458   typename std::remove_pointer<
 459     typename std::tuple_element<
 460       sizeof...(Ts) - 1, std::tuple<Ts...>
 461       >::type>::type>::value>::type
 462 toAppend(const T& v, const Ts&... vs) {
 463   toAppend(v, detail::getLastElement(vs...));
 464   toAppend(vs...);
 465 }
 466
 467 /**
 468  * Variadic base case: do nothing.
 469  */
 470 template <class Tgt>
 471 typename std::enable_if<detail::IsSomeString<Tgt>::value>::type
 472 toAppend(Tgt* result) {
 473 }
 474
 475 /**
 476  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 477  * for all types.
 478  */
 479 template <class Tgt, class... Ts>
 480 typename std::enable_if<detail::IsSomeString<Tgt>::value, Tgt>::type
 481 to(const Ts&... vs) {
 482   Tgt result;
 483   toAppend(vs..., &result);
 484   return result;
 485 }
 486
 487 /*******************************************************************************
 488  * Conversions from string types to integral types.
 489  ******************************************************************************/
 490
 491 namespace detail {
 492
 493 /**
 494  * Finds the first non-digit in a string. The number of digits
 495  * searched depends on the precision of the Tgt integral. Assumes the
 496  * string starts with NO whitespace and NO sign.
 497  *
 498  * The semantics of the routine is:
 499  *   for (;; ++b) {
 500  *     if (b >= e || !isdigit(*b)) return b;
 501  *   }
 502  *
 503  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 504  *  improvements of 20%.
 505  */
 506   template <class Tgt>
 507   const char* findFirstNonDigit(const char* b, const char* e) {
 508     for (; b < e; ++b) {
 509       auto const c = static_cast<unsigned>(*b) - '0';
 510       if (c >= 10) break;
 511     }
 512     return b;
 513   }
 514
 515   // Maximum value of number when represented as a string
 516   template <class T> struct MaxString {
 517     static const char*const value;
 518   };
 519
 520
 521 /*
 522  * Lookup tables that converts from a decimal character value to an integral
 523  * binary value, shifted by a decimal "shift" multiplier.
 524  * For all character values in the range '0'..'9', the table at those
 525  * index locations returns the actual decimal value shifted by the multiplier.
 526  * For all other values, the lookup table returns an invalid OOR value.
 527  */
 528 // Out-of-range flag value, larger than the largest value that can fit in
 529 // four decimal bytes (9999), but four of these added up together should
 530 // still not overflow uint16_t.
 531 constexpr int32_t OOR = 10000;
 532
 533 __attribute__((aligned(16))) constexpr uint16_t shift1[] = {
 534   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 535   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 536   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 537   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 538   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 539   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
 540   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 541   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 542   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 543   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 544   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 545   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 546   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 547   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 548   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 549   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 550   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 551   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 552   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 553   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 554   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 555   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 556   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 557   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 558   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 559   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 560 };
 561
 562 __attribute__((aligned(16))) constexpr uint16_t shift10[] = {
 563   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 564   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 565   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 566   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 567   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 568   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 569   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 570   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 571   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 572   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 573   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 574   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 575   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 576   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 577   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 578   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 579   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 580   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 581   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 582   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 583   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 584   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 585   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 586   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 587   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 588   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 589 };
 590
 591 __attribute__((aligned(16))) constexpr uint16_t shift100[] = {
 592   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 593   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 594   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 595   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 596   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 597   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 598   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 599   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 600   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 601   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 602   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 603   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 604   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 605   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 606   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 607   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 608   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 609   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 610   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 611   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 612   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 613   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 614   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 615   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 616   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 617   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 618 };
 619
 620 __attribute__((aligned(16))) constexpr uint16_t shift1000[] = {
 621   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 622   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 623   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 624   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 625   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 626   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 627   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 628   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 629   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 630   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 631   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 632   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 633   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 634   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 635   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 636   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 637   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 638   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 639   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 640   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 641   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 642   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 643   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 644   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 645   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 646   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 647 };
 648
 649 /**
 650  * String represented as a pair of pointers to char to unsigned
 651  * integrals. Assumes NO whitespace before or after, and also that the
 652  * string is composed entirely of digits. Tgt must be unsigned, and no
 653  * sign is allowed in the string (even it's '+'). String may be empty,
 654  * in which case digits_to throws.
 655  */
 656   template <class Tgt>
 657   Tgt digits_to(const char * b, const char * e) {
 658
 659     static_assert(!std::is_signed<Tgt>::value, "Unsigned type expected");
 660     assert(b <= e);
 661
 662     const size_t size = e - b;
 663
 664     /* Although the string is entirely made of digits, we still need to
 665      * check for overflow.
 666      */
 667     if (size >= std::numeric_limits<Tgt>::digits10 + 1) {
 668       // Leading zeros? If so, recurse to keep things simple
 669       if (b < e && *b == '0') {
 670         for (++b;; ++b) {
 671           if (b == e) return 0; // just zeros, e.g. "0000"
 672           if (*b != '0') return digits_to<Tgt>(b, e);
 673         }
 674       }
 675       FOLLY_RANGE_CHECK(size == std::numeric_limits<Tgt>::digits10 + 1 &&
 676                         strncmp(b, detail::MaxString<Tgt>::value, size) <= 0,
 677                         "Numeric overflow upon conversion");
 678     }
 679
 680     // Here we know that the number won't overflow when
 681     // converted. Proceed without checks.
 682
 683     Tgt result = 0;
 684
 685     for (; e - b >= 4; b += 4) {
 686       result *= 10000;
 687       const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 688       const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 689       const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 690       const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 691       const auto sum = r0 + r1 + r2 + r3;
 692       assert(sum < OOR && "Assumption: string only has digits");
 693       result += sum;
 694     }
 695
 696     switch (e - b) {
 697       case 3: {
 698         const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 699         const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 700         const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 701         const auto sum = r0 + r1 + r2;
 702         assert(sum < OOR && "Assumption: string only has digits");
 703         return result * 1000 + sum;
 704       }
 705       case 2: {
 706         const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 707         const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 708         const auto sum = r0 + r1;
 709         assert(sum < OOR && "Assumption: string only has digits");
 710         return result * 100 + sum;
 711       }
 712       case 1: {
 713         const int32_t sum = shift1[static_cast<size_t>(b[0])];
 714         assert(sum < OOR && "Assumption: string only has digits");
 715         return result * 10 + sum;
 716       }
 717     }
 718
 719     assert(b == e);
 720     FOLLY_RANGE_CHECK(size > 0, "Found no digits to convert in input");
 721     return result;
 722   }
 723
 724
 725   bool str_to_bool(StringPiece * src);
 726
 727 }                                 // namespace detail
 728
 729 /**
 730  * String represented as a pair of pointers to char to unsigned
 731  * integrals. Assumes NO whitespace before or after.
 732  */
 733 template <class Tgt>
 734 typename std::enable_if<
 735   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 736   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 737   Tgt>::type
 738 to(const char * b, const char * e) {
 739   return detail::digits_to<Tgt>(b, e);
 740 }
 741
 742 /**
 743  * String represented as a pair of pointers to char to signed
 744  * integrals. Assumes NO whitespace before or after. Allows an
 745  * optional leading sign.
 746  */
 747 template <class Tgt>
 748 typename std::enable_if<
 749   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
 750   Tgt>::type
 751 to(const char * b, const char * e) {
 752   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral");
 753   if (!isdigit(*b)) {
 754     if (*b == '-') {
 755       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
 756       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow.");
 757       return result;
 758     }
 759     FOLLY_RANGE_CHECK(*b == '+', "Invalid lead character");
 760     ++b;
 761   }
 762   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
 763   FOLLY_RANGE_CHECK(result >= 0, "Overflow.");
 764   return result;
 765 }
 766
 767 /**
 768  * Parsing strings to integrals. These routines differ from
 769  * to<integral>(string) in that they take a POINTER TO a StringPiece
 770  * and alter that StringPiece to reflect progress information.
 771  */
 772
 773 /**
 774  * StringPiece to integrals, with progress information. Alters the
 775  * StringPiece parameter to munch the already-parsed characters.
 776  */
 777 template <class Tgt>
 778 typename std::enable_if<
 779   std::is_integral<Tgt>::value
 780   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 781   Tgt>::type
 782 to(StringPiece * src) {
 783
 784   auto b = src->data(), past = src->data() + src->size();
 785   for (;; ++b) {
 786     FOLLY_RANGE_CHECK(b < past, "No digits found in input string");
 787     if (!isspace(*b)) break;
 788   }
 789
 790   auto m = b;
 791
 792   // First digit is customized because we test for sign
 793   bool negative = false;
 794   /* static */ if (std::is_signed<Tgt>::value) {
 795     if (!isdigit(*m)) {
 796       if (*m == '-') {
 797         negative = true;
 798       } else {
 799         FOLLY_RANGE_CHECK(*m == '+', "Invalid leading character in conversion"
 800                           " to integral");
 801       }
 802       ++b;
 803       ++m;
 804     }
 805   }
 806   FOLLY_RANGE_CHECK(m < past, "No digits found in input string");
 807   FOLLY_RANGE_CHECK(isdigit(*m), "Non-digit character found");
 808   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
 809
 810   Tgt result;
 811   /* static */ if (!std::is_signed<Tgt>::value) {
 812     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 813   } else {
 814     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 815     if (negative) {
 816       result = -t;
 817       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow");
 818     } else {
 819       result = t;
 820       FOLLY_RANGE_CHECK(result >= 0, "Overflow");
 821     }
 822   }
 823   src->advance(m - src->data());
 824   return result;
 825 }
 826
 827 /**
 828  * StringPiece to bool, with progress information. Alters the
 829  * StringPiece parameter to munch the already-parsed characters.
 830  */
 831 template <class Tgt>
 832 typename std::enable_if<
 833   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 834   Tgt>::type
 835 to(StringPiece * src) {
 836   return detail::str_to_bool(src);
 837 }
 838
 839 namespace detail {
 840
 841 /**
 842  * Enforce that the suffix following a number is made up only of whitespace.
 843  */
 844 inline void enforceWhitespace(const char* b, const char* e) {
 845   for (; b != e; ++b) {
 846     FOLLY_RANGE_CHECK(isspace(*b), to<std::string>("Non-whitespace: ", *b));
 847   }
 848 }
 849
 850 }  // namespace detail
 851
 852 /**
 853  * String or StringPiece to integrals. Accepts leading and trailing
 854  * whitespace, but no non-space trailing characters.
 855  */
 856 template <class Tgt>
 857 typename std::enable_if<
 858   std::is_integral<Tgt>::value,
 859   Tgt>::type
 860 to(StringPiece src) {
 861   Tgt result = to<Tgt>(&src);
 862   detail::enforceWhitespace(src.data(), src.data() + src.size());
 863   return result;
 864 }
 865
 866 /*******************************************************************************
 867  * Conversions from string types to floating-point types.
 868  ******************************************************************************/
 869
 870 /**
 871  * StringPiece to double, with progress information. Alters the
 872  * StringPiece parameter to munch the already-parsed characters.
 873  */
 874 template <class Tgt>
 875 inline typename std::enable_if<
 876   std::is_floating_point<Tgt>::value,
 877   Tgt>::type
 878 to(StringPiece *const src) {
 879   using namespace double_conversion;
 880   static StringToDoubleConverter
 881     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
 882          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
 883          0.0,
 884          // return this for junk input string
 885          std::numeric_limits<double>::quiet_NaN(),
 886          nullptr, nullptr);
 887
 888   FOLLY_RANGE_CHECK(!src->empty(), "No digits found in input string");
 889
 890   int length;
 891   auto result = conv.StringToDouble(src->data(), src->size(),
 892                                        &length); // processed char count
 893
 894   if (!std::isnan(result)) {
 895     src->advance(length);
 896     return result;
 897   }
 898
 899   for (;; src->advance(1)) {
 900     if (src->empty()) {
 901       throw std::range_error("Unable to convert an empty string"
 902                              " to a floating point value.");
 903     }
 904     if (!isspace(src->front())) {
 905       break;
 906     }
 907   }
 908
 909   // Was that "inf[inity]"?
 910   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
 911         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
 912     if (src->size() >= 8 &&
 913         toupper((*src)[3]) == 'I' &&
 914         toupper((*src)[4]) == 'N' &&
 915         toupper((*src)[5]) == 'I' &&
 916         toupper((*src)[6]) == 'T' &&
 917         toupper((*src)[7]) == 'Y') {
 918       src->advance(8);
 919     } else {
 920       src->advance(3);
 921     }
 922     return std::numeric_limits<Tgt>::infinity();
 923   }
 924
 925   // Was that "-inf[inity]"?
 926   if (src->size() >= 4 && toupper((*src)[0]) == '-'
 927       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
 928       && toupper((*src)[3]) == 'F') {
 929     if (src->size() >= 9 &&
 930         toupper((*src)[4]) == 'I' &&
 931         toupper((*src)[5]) == 'N' &&
 932         toupper((*src)[6]) == 'I' &&
 933         toupper((*src)[7]) == 'T' &&
 934         toupper((*src)[8]) == 'Y') {
 935       src->advance(9);
 936     } else {
 937       src->advance(4);
 938     }
 939     return -std::numeric_limits<Tgt>::infinity();
 940   }
 941
 942   // "nan"?
 943   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
 944         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
 945     src->advance(3);
 946     return std::numeric_limits<Tgt>::quiet_NaN();
 947   }
 948
 949   // "-nan"?
 950   if (src->size() >= 4 &&
 951       toupper((*src)[0]) == '-' &&
 952       toupper((*src)[1]) == 'N' &&
 953       toupper((*src)[2]) == 'A' &&
 954       toupper((*src)[3]) == 'N') {
 955     src->advance(4);
 956     return -std::numeric_limits<Tgt>::quiet_NaN();
 957   }
 958
 959   // All bets are off
 960   throw std::range_error("Unable to convert \"" + src->toString()
 961                          + "\" to a floating point value.");
 962 }
 963
 964 /**
 965  * Any string, const char*, or StringPiece to double.
 966  */
 967 template <class Tgt>
 968 typename std::enable_if<
 969   std::is_floating_point<Tgt>::value,
 970   Tgt>::type
 971 to(StringPiece src) {
 972   Tgt result = to<double>(&src);
 973   detail::enforceWhitespace(src.data(), src.data() + src.size());
 974   return result;
 975 }
 976
 977 /*******************************************************************************
 978  * Integral to floating point and back
 979  ******************************************************************************/
 980
 981 /**
 982  * Checked conversion from integral to flating point and back. The
 983  * result must be convertible back to the source type without loss of
 984  * precision. This seems Draconian but sometimes is what's needed, and
 985  * complements existing routines nicely. For various rounding
 986  * routines, see <math>.
 987  */
 988 template <class Tgt, class Src>
 989 typename std::enable_if<
 990   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
 991   ||
 992   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
 993   Tgt>::type
 994 to(const Src & value) {
 995   Tgt result = value;
 996   auto witness = static_cast<Src>(result);
 997   if (value != witness) {
 998     throw std::range_error(
 999       to<std::string>("to<>: loss of precision when converting ", value,
1000                       " to type ", typeid(Tgt).name()).c_str());
1001   }
1002   return result;
1003 }
1004
1005 /*******************************************************************************
1006  * Enum to anything and back
1007  ******************************************************************************/
1008
1009 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
1010 // std::underlying_type became available by gcc 4.7.0
1011
1012 template <class Tgt, class Src>
1013 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1014 to(const Src & value) {
1015   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
1016 }
1017
1018 template <class Tgt, class Src>
1019 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1020 to(const Src & value) {
1021   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
1022 }
1023
1024 #else
1025
1026 template <class Tgt, class Src>
1027 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1028 to(const Src & value) {
1029   /* static */ if (Src(-1) < 0) {
1030     /* static */ if (sizeof(Src) <= sizeof(int)) {
1031       return to<Tgt>(static_cast<int>(value));
1032     } else {
1033       return to<Tgt>(static_cast<long>(value));
1034     }
1035   } else {
1036     /* static */ if (sizeof(Src) <= sizeof(int)) {
1037       return to<Tgt>(static_cast<unsigned int>(value));
1038     } else {
1039       return to<Tgt>(static_cast<unsigned long>(value));
1040     }
1041   }
1042 }
1043
1044 template <class Tgt, class Src>
1045 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1046 to(const Src & value) {
1047   /* static */ if (Tgt(-1) < 0) {
1048     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1049       return static_cast<Tgt>(to<int>(value));
1050     } else {
1051       return static_cast<Tgt>(to<long>(value));
1052     }
1053   } else {
1054     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1055       return static_cast<Tgt>(to<unsigned int>(value));
1056     } else {
1057       return static_cast<Tgt>(to<unsigned long>(value));
1058     }
1059   }
1060 }
1061
1062 #endif // gcc 4.7 onwards
1063
1064 } // namespace folly
1065
1066 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
1067 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
1068 // to avoid defining this global macro name in other files that include Conv.h.
1069 #ifndef FOLLY_CONV_INTERNAL
1070 #undef FOLLY_RANGE_CHECK
1071 #endif
1072
1073 #endif /* FOLLY_BASE_CONV_H_ */