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  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 481  * for all types.
 482  */
 483 template <class Tgt, class... Ts>
 484 typename std::enable_if<detail::IsSomeString<Tgt>::value, Tgt>::type
 485 to(const Ts&... vs) {
 486   Tgt result;
 487   toAppend(vs..., &result);
 488   return result;
 489 }
 490
 491 /*******************************************************************************
 492  * Conversions from string types to integral types.
 493  ******************************************************************************/
 494
 495 namespace detail {
 496
 497 /**
 498  * Finds the first non-digit in a string. The number of digits
 499  * searched depends on the precision of the Tgt integral. Assumes the
 500  * string starts with NO whitespace and NO sign.
 501  *
 502  * The semantics of the routine is:
 503  *   for (;; ++b) {
 504  *     if (b >= e || !isdigit(*b)) return b;
 505  *   }
 506  *
 507  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 508  *  improvements of 20%.
 509  */
 510   template <class Tgt>
 511   const char* findFirstNonDigit(const char* b, const char* e) {
 512     for (; b < e; ++b) {
 513       auto const c = static_cast<unsigned>(*b) - '0';
 514       if (c >= 10) break;
 515     }
 516     return b;
 517   }
 518
 519   // Maximum value of number when represented as a string
 520   template <class T> struct MaxString {
 521     static const char*const value;
 522   };
 523
 524
 525 /*
 526  * Lookup tables that converts from a decimal character value to an integral
 527  * binary value, shifted by a decimal "shift" multiplier.
 528  * For all character values in the range '0'..'9', the table at those
 529  * index locations returns the actual decimal value shifted by the multiplier.
 530  * For all other values, the lookup table returns an invalid OOR value.
 531  */
 532 // Out-of-range flag value, larger than the largest value that can fit in
 533 // four decimal bytes (9999), but four of these added up together should
 534 // still not overflow uint16_t.
 535 constexpr int32_t OOR = 10000;
 536
 537 __attribute__((aligned(16))) constexpr uint16_t shift1[] = {
 538   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 539   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 540   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 541   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 542   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 543   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
 544   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 545   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 546   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 547   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 548   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 549   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 550   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 551   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 552   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 553   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 554   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 555   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 556   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 557   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 558   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 559   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 560   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 561   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 562   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 563   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 564 };
 565
 566 __attribute__((aligned(16))) constexpr uint16_t shift10[] = {
 567   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 568   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 569   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 570   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 571   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 572   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 573   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 574   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 575   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 576   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 577   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 578   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 579   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 580   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 581   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 582   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 583   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 584   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 585   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 586   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 587   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 588   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 589   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 590   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 591   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 592   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 593 };
 594
 595 __attribute__((aligned(16))) constexpr uint16_t shift100[] = {
 596   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 597   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 598   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 599   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 600   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 601   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 602   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 603   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 604   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 605   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 606   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 607   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 608   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 609   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 610   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 611   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 612   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 613   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 614   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 615   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 616   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 617   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 618   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 619   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 620   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 621   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 622 };
 623
 624 __attribute__((aligned(16))) constexpr uint16_t shift1000[] = {
 625   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 626   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 627   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 628   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 629   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 630   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 631   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 632   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 633   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 634   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 635   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 636   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 637   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 638   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 639   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 640   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 641   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 642   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 643   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 644   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 645   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 646   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 647   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 648   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 649   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 650   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 651 };
 652
 653 /**
 654  * String represented as a pair of pointers to char to unsigned
 655  * integrals. Assumes NO whitespace before or after, and also that the
 656  * string is composed entirely of digits. Tgt must be unsigned, and no
 657  * sign is allowed in the string (even it's '+'). String may be empty,
 658  * in which case digits_to throws.
 659  */
 660   template <class Tgt>
 661   Tgt digits_to(const char * b, const char * e) {
 662
 663     static_assert(!std::is_signed<Tgt>::value, "Unsigned type expected");
 664     assert(b <= e);
 665
 666     const size_t size = e - b;
 667
 668     /* Although the string is entirely made of digits, we still need to
 669      * check for overflow.
 670      */
 671     if (size >= std::numeric_limits<Tgt>::digits10 + 1) {
 672       // Leading zeros? If so, recurse to keep things simple
 673       if (b < e && *b == '0') {
 674         for (++b;; ++b) {
 675           if (b == e) return 0; // just zeros, e.g. "0000"
 676           if (*b != '0') return digits_to<Tgt>(b, e);
 677         }
 678       }
 679       FOLLY_RANGE_CHECK(size == std::numeric_limits<Tgt>::digits10 + 1 &&
 680                         strncmp(b, detail::MaxString<Tgt>::value, size) <= 0,
 681                         "Numeric overflow upon conversion");
 682     }
 683
 684     // Here we know that the number won't overflow when
 685     // converted. Proceed without checks.
 686
 687     Tgt result = 0;
 688
 689     for (; e - b >= 4; b += 4) {
 690       result *= 10000;
 691       const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 692       const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 693       const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 694       const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 695       const auto sum = r0 + r1 + r2 + r3;
 696       assert(sum < OOR && "Assumption: string only has digits");
 697       result += sum;
 698     }
 699
 700     switch (e - b) {
 701       case 3: {
 702         const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 703         const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 704         const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 705         const auto sum = r0 + r1 + r2;
 706         assert(sum < OOR && "Assumption: string only has digits");
 707         return result * 1000 + sum;
 708       }
 709       case 2: {
 710         const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 711         const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 712         const auto sum = r0 + r1;
 713         assert(sum < OOR && "Assumption: string only has digits");
 714         return result * 100 + sum;
 715       }
 716       case 1: {
 717         const int32_t sum = shift1[static_cast<size_t>(b[0])];
 718         assert(sum < OOR && "Assumption: string only has digits");
 719         return result * 10 + sum;
 720       }
 721     }
 722
 723     assert(b == e);
 724     FOLLY_RANGE_CHECK(size > 0, "Found no digits to convert in input");
 725     return result;
 726   }
 727
 728
 729   bool str_to_bool(StringPiece * src);
 730
 731 }                                 // namespace detail
 732
 733 /**
 734  * String represented as a pair of pointers to char to unsigned
 735  * integrals. Assumes NO whitespace before or after.
 736  */
 737 template <class Tgt>
 738 typename std::enable_if<
 739   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 740   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 741   Tgt>::type
 742 to(const char * b, const char * e) {
 743   return detail::digits_to<Tgt>(b, e);
 744 }
 745
 746 /**
 747  * String represented as a pair of pointers to char to signed
 748  * integrals. Assumes NO whitespace before or after. Allows an
 749  * optional leading sign.
 750  */
 751 template <class Tgt>
 752 typename std::enable_if<
 753   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
 754   Tgt>::type
 755 to(const char * b, const char * e) {
 756   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral");
 757   if (!isdigit(*b)) {
 758     if (*b == '-') {
 759       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
 760       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow.");
 761       return result;
 762     }
 763     FOLLY_RANGE_CHECK(*b == '+', "Invalid lead character");
 764     ++b;
 765   }
 766   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
 767   FOLLY_RANGE_CHECK(result >= 0, "Overflow.");
 768   return result;
 769 }
 770
 771 /**
 772  * Parsing strings to integrals. These routines differ from
 773  * to<integral>(string) in that they take a POINTER TO a StringPiece
 774  * and alter that StringPiece to reflect progress information.
 775  */
 776
 777 /**
 778  * StringPiece to integrals, with progress information. Alters the
 779  * StringPiece parameter to munch the already-parsed characters.
 780  */
 781 template <class Tgt>
 782 typename std::enable_if<
 783   std::is_integral<Tgt>::value
 784   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 785   Tgt>::type
 786 to(StringPiece * src) {
 787
 788   auto b = src->data(), past = src->data() + src->size();
 789   for (;; ++b) {
 790     FOLLY_RANGE_CHECK(b < past, "No digits found in input string");
 791     if (!isspace(*b)) break;
 792   }
 793
 794   auto m = b;
 795
 796   // First digit is customized because we test for sign
 797   bool negative = false;
 798   /* static */ if (std::is_signed<Tgt>::value) {
 799     if (!isdigit(*m)) {
 800       if (*m == '-') {
 801         negative = true;
 802       } else {
 803         FOLLY_RANGE_CHECK(*m == '+', "Invalid leading character in conversion"
 804                           " to integral");
 805       }
 806       ++b;
 807       ++m;
 808     }
 809   }
 810   FOLLY_RANGE_CHECK(m < past, "No digits found in input string");
 811   FOLLY_RANGE_CHECK(isdigit(*m), "Non-digit character found");
 812   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
 813
 814   Tgt result;
 815   /* static */ if (!std::is_signed<Tgt>::value) {
 816     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 817   } else {
 818     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 819     if (negative) {
 820       result = -t;
 821       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow");
 822     } else {
 823       result = t;
 824       FOLLY_RANGE_CHECK(result >= 0, "Overflow");
 825     }
 826   }
 827   src->advance(m - src->data());
 828   return result;
 829 }
 830
 831 /**
 832  * StringPiece to bool, with progress information. Alters the
 833  * StringPiece parameter to munch the already-parsed characters.
 834  */
 835 template <class Tgt>
 836 typename std::enable_if<
 837   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 838   Tgt>::type
 839 to(StringPiece * src) {
 840   return detail::str_to_bool(src);
 841 }
 842
 843 namespace detail {
 844
 845 /**
 846  * Enforce that the suffix following a number is made up only of whitespace.
 847  */
 848 inline void enforceWhitespace(const char* b, const char* e) {
 849   for (; b != e; ++b) {
 850     FOLLY_RANGE_CHECK(isspace(*b), to<std::string>("Non-whitespace: ", *b));
 851   }
 852 }
 853
 854 }  // namespace detail
 855
 856 /**
 857  * String or StringPiece to integrals. Accepts leading and trailing
 858  * whitespace, but no non-space trailing characters.
 859  */
 860 template <class Tgt>
 861 typename std::enable_if<
 862   std::is_integral<Tgt>::value,
 863   Tgt>::type
 864 to(StringPiece src) {
 865   Tgt result = to<Tgt>(&src);
 866   detail::enforceWhitespace(src.data(), src.data() + src.size());
 867   return result;
 868 }
 869
 870 /*******************************************************************************
 871  * Conversions from string types to floating-point types.
 872  ******************************************************************************/
 873
 874 /**
 875  * StringPiece to double, with progress information. Alters the
 876  * StringPiece parameter to munch the already-parsed characters.
 877  */
 878 template <class Tgt>
 879 inline typename std::enable_if<
 880   std::is_floating_point<Tgt>::value,
 881   Tgt>::type
 882 to(StringPiece *const src) {
 883   using namespace double_conversion;
 884   static StringToDoubleConverter
 885     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
 886          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
 887          0.0,
 888          // return this for junk input string
 889          std::numeric_limits<double>::quiet_NaN(),
 890          nullptr, nullptr);
 891
 892   FOLLY_RANGE_CHECK(!src->empty(), "No digits found in input string");
 893
 894   int length;
 895   auto result = conv.StringToDouble(src->data(), src->size(),
 896                                        &length); // processed char count
 897
 898   if (!std::isnan(result)) {
 899     src->advance(length);
 900     return result;
 901   }
 902
 903   for (;; src->advance(1)) {
 904     if (src->empty()) {
 905       throw std::range_error("Unable to convert an empty string"
 906                              " to a floating point value.");
 907     }
 908     if (!isspace(src->front())) {
 909       break;
 910     }
 911   }
 912
 913   // Was that "inf[inity]"?
 914   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
 915         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
 916     if (src->size() >= 8 &&
 917         toupper((*src)[3]) == 'I' &&
 918         toupper((*src)[4]) == 'N' &&
 919         toupper((*src)[5]) == 'I' &&
 920         toupper((*src)[6]) == 'T' &&
 921         toupper((*src)[7]) == 'Y') {
 922       src->advance(8);
 923     } else {
 924       src->advance(3);
 925     }
 926     return std::numeric_limits<Tgt>::infinity();
 927   }
 928
 929   // Was that "-inf[inity]"?
 930   if (src->size() >= 4 && toupper((*src)[0]) == '-'
 931       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
 932       && toupper((*src)[3]) == 'F') {
 933     if (src->size() >= 9 &&
 934         toupper((*src)[4]) == 'I' &&
 935         toupper((*src)[5]) == 'N' &&
 936         toupper((*src)[6]) == 'I' &&
 937         toupper((*src)[7]) == 'T' &&
 938         toupper((*src)[8]) == 'Y') {
 939       src->advance(9);
 940     } else {
 941       src->advance(4);
 942     }
 943     return -std::numeric_limits<Tgt>::infinity();
 944   }
 945
 946   // "nan"?
 947   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
 948         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
 949     src->advance(3);
 950     return std::numeric_limits<Tgt>::quiet_NaN();
 951   }
 952
 953   // "-nan"?
 954   if (src->size() >= 4 &&
 955       toupper((*src)[0]) == '-' &&
 956       toupper((*src)[1]) == 'N' &&
 957       toupper((*src)[2]) == 'A' &&
 958       toupper((*src)[3]) == 'N') {
 959     src->advance(4);
 960     return -std::numeric_limits<Tgt>::quiet_NaN();
 961   }
 962
 963   // All bets are off
 964   throw std::range_error("Unable to convert \"" + src->toString()
 965                          + "\" to a floating point value.");
 966 }
 967
 968 /**
 969  * Any string, const char*, or StringPiece to double.
 970  */
 971 template <class Tgt>
 972 typename std::enable_if<
 973   std::is_floating_point<Tgt>::value,
 974   Tgt>::type
 975 to(StringPiece src) {
 976   Tgt result = to<double>(&src);
 977   detail::enforceWhitespace(src.data(), src.data() + src.size());
 978   return result;
 979 }
 980
 981 /*******************************************************************************
 982  * Integral to floating point and back
 983  ******************************************************************************/
 984
 985 /**
 986  * Checked conversion from integral to flating point and back. The
 987  * result must be convertible back to the source type without loss of
 988  * precision. This seems Draconian but sometimes is what's needed, and
 989  * complements existing routines nicely. For various rounding
 990  * routines, see <math>.
 991  */
 992 template <class Tgt, class Src>
 993 typename std::enable_if<
 994   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
 995   ||
 996   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
 997   Tgt>::type
 998 to(const Src & value) {
 999   Tgt result = value;
1000   auto witness = static_cast<Src>(result);
1001   if (value != witness) {
1002     throw std::range_error(
1003       to<std::string>("to<>: loss of precision when converting ", value,
1004                       " to type ", typeid(Tgt).name()).c_str());
1005   }
1006   return result;
1007 }
1008
1009 /*******************************************************************************
1010  * Enum to anything and back
1011  ******************************************************************************/
1012
1013 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
1014 // std::underlying_type became available by gcc 4.7.0
1015
1016 template <class Tgt, class Src>
1017 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1018 to(const Src & value) {
1019   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
1020 }
1021
1022 template <class Tgt, class Src>
1023 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1024 to(const Src & value) {
1025   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
1026 }
1027
1028 #else
1029
1030 template <class Tgt, class Src>
1031 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1032 to(const Src & value) {
1033   /* static */ if (Src(-1) < 0) {
1034     /* static */ if (sizeof(Src) <= sizeof(int)) {
1035       return to<Tgt>(static_cast<int>(value));
1036     } else {
1037       return to<Tgt>(static_cast<long>(value));
1038     }
1039   } else {
1040     /* static */ if (sizeof(Src) <= sizeof(int)) {
1041       return to<Tgt>(static_cast<unsigned int>(value));
1042     } else {
1043       return to<Tgt>(static_cast<unsigned long>(value));
1044     }
1045   }
1046 }
1047
1048 template <class Tgt, class Src>
1049 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1050 to(const Src & value) {
1051   /* static */ if (Tgt(-1) < 0) {
1052     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1053       return static_cast<Tgt>(to<int>(value));
1054     } else {
1055       return static_cast<Tgt>(to<long>(value));
1056     }
1057   } else {
1058     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1059       return static_cast<Tgt>(to<unsigned int>(value));
1060     } else {
1061       return static_cast<Tgt>(to<unsigned long>(value));
1062     }
1063   }
1064 }
1065
1066 #endif // gcc 4.7 onwards
1067
1068 } // namespace folly
1069
1070 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
1071 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
1072 // to avoid defining this global macro name in other files that include Conv.h.
1073 #ifndef FOLLY_CONV_INTERNAL
1074 #undef FOLLY_RANGE_CHECK
1075 #endif
1076
1077 #endif /* FOLLY_BASE_CONV_H_ */