folly/Conv.h

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