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   char buffer[20];
 327   if (value < 0) {
 328     result->push_back('-');
 329     result->append(buffer, uint64ToBufferUnsafe(-uint64_t(value), buffer));
 330   } else {
 331     result->append(buffer, uint64ToBufferUnsafe(value, buffer));
 332   }
 333 }
 334
 335 /**
 336  * As above, but for uint32_t and uint64_t.
 337  */
 338 template <class Tgt, class Src>
 339 typename std::enable_if<
 340   std::is_integral<Src>::value && !std::is_signed<Src>::value
 341   && detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 342 toAppend(Src value, Tgt * result) {
 343   char buffer[20];
 344   result->append(buffer, buffer + uint64ToBufferUnsafe(value, buffer));
 345 }
 346
 347 /**
 348  * All small signed and unsigned integers to string go through 32-bit
 349  * types int32_t and uint32_t, respectively.
 350  */
 351 template <class Tgt, class Src>
 352 typename std::enable_if<
 353   std::is_integral<Src>::value
 354   && detail::IsSomeString<Tgt>::value && sizeof(Src) < 4>::type
 355 toAppend(Src value, Tgt * result) {
 356   typedef typename
 357     std::conditional<std::is_signed<Src>::value, int64_t, uint64_t>::type
 358     Intermediate;
 359   toAppend<Tgt>(static_cast<Intermediate>(value), result);
 360 }
 361
 362 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
 363 // std::underlying_type became available by gcc 4.7.0
 364
 365 /**
 366  * Enumerated values get appended as integers.
 367  */
 368 template <class Tgt, class Src>
 369 typename std::enable_if<
 370   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 371 toAppend(Src value, Tgt * result) {
 372   toAppend(
 373       static_cast<typename std::underlying_type<Src>::type>(value), result);
 374 }
 375
 376 #else
 377
 378 /**
 379  * Enumerated values get appended as integers.
 380  */
 381 template <class Tgt, class Src>
 382 typename std::enable_if<
 383   std::is_enum<Src>::value && detail::IsSomeString<Tgt>::value>::type
 384 toAppend(Src value, Tgt * result) {
 385   /* static */ if (Src(-1) < 0) {
 386     /* static */ if (sizeof(Src) <= sizeof(int)) {
 387       toAppend(static_cast<int>(value), result);
 388     } else {
 389       toAppend(static_cast<long>(value), result);
 390     }
 391   } else {
 392     /* static */ if (sizeof(Src) <= sizeof(int)) {
 393       toAppend(static_cast<unsigned int>(value), result);
 394     } else {
 395       toAppend(static_cast<unsigned long>(value), result);
 396     }
 397   }
 398 }
 399
 400 #endif // gcc 4.7 onwards
 401
 402 /*******************************************************************************
 403  * Conversions from floating-point types to string types.
 404  ******************************************************************************/
 405
 406 /** Wrapper around DoubleToStringConverter **/
 407 template <class Tgt, class Src>
 408 typename std::enable_if<
 409   std::is_floating_point<Src>::value
 410   && detail::IsSomeString<Tgt>::value>::type
 411 toAppend(
 412   Src value,
 413   Tgt * result,
 414   double_conversion::DoubleToStringConverter::DtoaMode mode,
 415   unsigned int numDigits) {
 416   using namespace double_conversion;
 417   DoubleToStringConverter
 418     conv(DoubleToStringConverter::NO_FLAGS,
 419          "infinity", "NaN", 'E',
 420          -6,  // decimal in shortest low
 421          21,  // decimal in shortest high
 422          6,   // max leading padding zeros
 423          1);  // max trailing padding zeros
 424   char buffer[256];
 425   StringBuilder builder(buffer, sizeof(buffer));
 426   switch (mode) {
 427     case DoubleToStringConverter::SHORTEST:
 428       conv.ToShortest(value, &builder);
 429       break;
 430     case DoubleToStringConverter::FIXED:
 431       conv.ToFixed(value, numDigits, &builder);
 432       break;
 433     default:
 434       CHECK(mode == DoubleToStringConverter::PRECISION);
 435       conv.ToPrecision(value, numDigits, &builder);
 436       break;
 437   }
 438   const size_t length = builder.position();
 439   builder.Finalize();
 440   result->append(buffer, length);
 441 }
 442
 443 /**
 444  * As above, but for floating point
 445  */
 446 template <class Tgt, class Src>
 447 typename std::enable_if<
 448   std::is_floating_point<Src>::value
 449   && detail::IsSomeString<Tgt>::value>::type
 450 toAppend(Src value, Tgt * result) {
 451   toAppend(
 452     value, result, double_conversion::DoubleToStringConverter::SHORTEST, 0);
 453 }
 454
 455 /**
 456  * Variadic conversion to string. Appends each element in turn.
 457  */
 458 template <class T, class... Ts>
 459 typename std::enable_if<sizeof...(Ts) >= 2
 460   && detail::IsSomeString<
 461   typename std::remove_pointer<
 462     typename std::tuple_element<
 463       sizeof...(Ts) - 1, std::tuple<Ts...>
 464       >::type>::type>::value>::type
 465 toAppend(const T& v, const Ts&... vs) {
 466   toAppend(v, detail::getLastElement(vs...));
 467   toAppend(vs...);
 468 }
 469
 470 /**
 471  * Variadic base case: do nothing.
 472  */
 473 template <class Tgt>
 474 typename std::enable_if<detail::IsSomeString<Tgt>::value>::type
 475 toAppend(Tgt* result) {
 476 }
 477
 478 /**
 479  * Variadic base case: do nothing.
 480  */
 481 template <class Delimiter, class Tgt>
 482 typename std::enable_if<detail::IsSomeString<Tgt>::value>::type
 483 toAppendDelim(const Delimiter& delim, Tgt* result) {
 484 }
 485
 486 /**
 487  * 1 element: same as toAppend.
 488  */
 489 template <class Delimiter, class T, class Tgt>
 490 typename std::enable_if<detail::IsSomeString<Tgt>::value>::type
 491 toAppendDelim(const Delimiter& delim, const T& v, Tgt* tgt) {
 492   toAppend(v, tgt);
 493 }
 494
 495 /**
 496  * Append to string with a delimiter in between elements.
 497  */
 498 template <class Delimiter, class T, class... Ts>
 499 typename std::enable_if<sizeof...(Ts) >= 2
 500   && detail::IsSomeString<
 501   typename std::remove_pointer<
 502     typename std::tuple_element<
 503       sizeof...(Ts) - 1, std::tuple<Ts...>
 504       >::type>::type>::value>::type
 505 toAppendDelim(const Delimiter& delim, const T& v, const Ts&... vs) {
 506   toAppend(v, delim, detail::getLastElement(vs...));
 507   toAppendDelim(delim, vs...);
 508 }
 509
 510 /**
 511  * to<SomeString>(v1, v2, ...) uses toAppend() (see below) as back-end
 512  * for all types.
 513  */
 514 template <class Tgt, class... Ts>
 515 typename std::enable_if<detail::IsSomeString<Tgt>::value, Tgt>::type
 516 to(const Ts&... vs) {
 517   Tgt result;
 518   toAppend(vs..., &result);
 519   return result;
 520 }
 521
 522 /**
 523  * toDelim<SomeString>(delim, v1, v2, ...) uses toAppendDelim() as
 524  * back-end for all types.
 525  */
 526 template <class Tgt, class Delim, class... Ts>
 527 typename std::enable_if<detail::IsSomeString<Tgt>::value, Tgt>::type
 528 toDelim(const Delim& delim, const Ts&... vs) {
 529   Tgt result;
 530   toAppendDelim(delim, vs..., &result);
 531   return result;
 532 }
 533
 534 /*******************************************************************************
 535  * Conversions from string types to integral types.
 536  ******************************************************************************/
 537
 538 namespace detail {
 539
 540 /**
 541  * Finds the first non-digit in a string. The number of digits
 542  * searched depends on the precision of the Tgt integral. Assumes the
 543  * string starts with NO whitespace and NO sign.
 544  *
 545  * The semantics of the routine is:
 546  *   for (;; ++b) {
 547  *     if (b >= e || !isdigit(*b)) return b;
 548  *   }
 549  *
 550  *  Complete unrolling marks bottom-line (i.e. entire conversion)
 551  *  improvements of 20%.
 552  */
 553   template <class Tgt>
 554   const char* findFirstNonDigit(const char* b, const char* e) {
 555     for (; b < e; ++b) {
 556       auto const c = static_cast<unsigned>(*b) - '0';
 557       if (c >= 10) break;
 558     }
 559     return b;
 560   }
 561
 562   // Maximum value of number when represented as a string
 563   template <class T> struct MaxString {
 564     static const char*const value;
 565   };
 566
 567
 568 /*
 569  * Lookup tables that converts from a decimal character value to an integral
 570  * binary value, shifted by a decimal "shift" multiplier.
 571  * For all character values in the range '0'..'9', the table at those
 572  * index locations returns the actual decimal value shifted by the multiplier.
 573  * For all other values, the lookup table returns an invalid OOR value.
 574  */
 575 // Out-of-range flag value, larger than the largest value that can fit in
 576 // four decimal bytes (9999), but four of these added up together should
 577 // still not overflow uint16_t.
 578 constexpr int32_t OOR = 10000;
 579
 580 __attribute__((aligned(16))) constexpr uint16_t shift1[] = {
 581   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 582   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 583   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 584   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 585   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 586   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
 587   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 588   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 589   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 590   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 591   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 592   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 593   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 594   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 595   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 596   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 597   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 598   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 599   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 600   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 601   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 602   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 603   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 604   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 605   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 606   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 607 };
 608
 609 __attribute__((aligned(16))) constexpr uint16_t shift10[] = {
 610   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 611   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 612   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 613   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 614   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 615   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 616   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 617   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 618   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 619   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 620   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 621   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 622   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 623   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 624   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 625   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 626   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 627   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 628   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 629   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 630   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 631   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 632   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 633   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 634   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 635   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 636 };
 637
 638 __attribute__((aligned(16))) constexpr uint16_t shift100[] = {
 639   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 640   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 641   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 642   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 643   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 644   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 645   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 646   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 647   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 648   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 649   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 650   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 651   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 652   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 653   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 654   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 655   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 656   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 657   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 658   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 659   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 660   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 661   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 662   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 663   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 664   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 665 };
 666
 667 __attribute__((aligned(16))) constexpr uint16_t shift1000[] = {
 668   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 669   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 670   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 671   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 672   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 673   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 674   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 675   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 676   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 677   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 678   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 679   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 680   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 681   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 682   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 683   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 684   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 685   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 686   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 687   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 688   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 689   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 690   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 691   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 692   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 693   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 694 };
 695
 696 /**
 697  * String represented as a pair of pointers to char to unsigned
 698  * integrals. Assumes NO whitespace before or after, and also that the
 699  * string is composed entirely of digits. Tgt must be unsigned, and no
 700  * sign is allowed in the string (even it's '+'). String may be empty,
 701  * in which case digits_to throws.
 702  */
 703   template <class Tgt>
 704   Tgt digits_to(const char * b, const char * e) {
 705
 706     static_assert(!std::is_signed<Tgt>::value, "Unsigned type expected");
 707     assert(b <= e);
 708
 709     const size_t size = e - b;
 710
 711     /* Although the string is entirely made of digits, we still need to
 712      * check for overflow.
 713      */
 714     if (size >= std::numeric_limits<Tgt>::digits10 + 1) {
 715       // Leading zeros? If so, recurse to keep things simple
 716       if (b < e && *b == '0') {
 717         for (++b;; ++b) {
 718           if (b == e) return 0; // just zeros, e.g. "0000"
 719           if (*b != '0') return digits_to<Tgt>(b, e);
 720         }
 721       }
 722       FOLLY_RANGE_CHECK(size == std::numeric_limits<Tgt>::digits10 + 1 &&
 723                         strncmp(b, detail::MaxString<Tgt>::value, size) <= 0,
 724                         "Numeric overflow upon conversion");
 725     }
 726
 727     // Here we know that the number won't overflow when
 728     // converted. Proceed without checks.
 729
 730     Tgt result = 0;
 731
 732     for (; e - b >= 4; b += 4) {
 733       result *= 10000;
 734       const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 735       const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 736       const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 737       const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 738       const auto sum = r0 + r1 + r2 + r3;
 739       assert(sum < OOR && "Assumption: string only has digits");
 740       result += sum;
 741     }
 742
 743     switch (e - b) {
 744       case 3: {
 745         const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 746         const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 747         const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 748         const auto sum = r0 + r1 + r2;
 749         assert(sum < OOR && "Assumption: string only has digits");
 750         return result * 1000 + sum;
 751       }
 752       case 2: {
 753         const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 754         const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 755         const auto sum = r0 + r1;
 756         assert(sum < OOR && "Assumption: string only has digits");
 757         return result * 100 + sum;
 758       }
 759       case 1: {
 760         const int32_t sum = shift1[static_cast<size_t>(b[0])];
 761         assert(sum < OOR && "Assumption: string only has digits");
 762         return result * 10 + sum;
 763       }
 764     }
 765
 766     assert(b == e);
 767     FOLLY_RANGE_CHECK(size > 0, "Found no digits to convert in input");
 768     return result;
 769   }
 770
 771
 772   bool str_to_bool(StringPiece * src);
 773
 774 }                                 // namespace detail
 775
 776 /**
 777  * String represented as a pair of pointers to char to unsigned
 778  * integrals. Assumes NO whitespace before or after.
 779  */
 780 template <class Tgt>
 781 typename std::enable_if<
 782   std::is_integral<Tgt>::value && !std::is_signed<Tgt>::value
 783   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 784   Tgt>::type
 785 to(const char * b, const char * e) {
 786   return detail::digits_to<Tgt>(b, e);
 787 }
 788
 789 /**
 790  * String represented as a pair of pointers to char to signed
 791  * integrals. Assumes NO whitespace before or after. Allows an
 792  * optional leading sign.
 793  */
 794 template <class Tgt>
 795 typename std::enable_if<
 796   std::is_integral<Tgt>::value && std::is_signed<Tgt>::value,
 797   Tgt>::type
 798 to(const char * b, const char * e) {
 799   FOLLY_RANGE_CHECK(b < e, "Empty input string in conversion to integral");
 800   if (!isdigit(*b)) {
 801     if (*b == '-') {
 802       Tgt result = -to<typename std::make_unsigned<Tgt>::type>(b + 1, e);
 803       FOLLY_RANGE_CHECK(result <= 0, "Negative overflow.");
 804       return result;
 805     }
 806     FOLLY_RANGE_CHECK(*b == '+', "Invalid lead character");
 807     ++b;
 808   }
 809   Tgt result = to<typename std::make_unsigned<Tgt>::type>(b, e);
 810   FOLLY_RANGE_CHECK(result >= 0, "Overflow.");
 811   return result;
 812 }
 813
 814 /**
 815  * Parsing strings to integrals. These routines differ from
 816  * to<integral>(string) in that they take a POINTER TO a StringPiece
 817  * and alter that StringPiece to reflect progress information.
 818  */
 819
 820 /**
 821  * StringPiece to integrals, with progress information. Alters the
 822  * StringPiece parameter to munch the already-parsed characters.
 823  */
 824 template <class Tgt>
 825 typename std::enable_if<
 826   std::is_integral<Tgt>::value
 827   && !std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 828   Tgt>::type
 829 to(StringPiece * src) {
 830
 831   auto b = src->data(), past = src->data() + src->size();
 832   for (;; ++b) {
 833     FOLLY_RANGE_CHECK(b < past, "No digits found in input string");
 834     if (!isspace(*b)) break;
 835   }
 836
 837   auto m = b;
 838
 839   // First digit is customized because we test for sign
 840   bool negative = false;
 841   /* static */ if (std::is_signed<Tgt>::value) {
 842     if (!isdigit(*m)) {
 843       if (*m == '-') {
 844         negative = true;
 845       } else {
 846         FOLLY_RANGE_CHECK(*m == '+', "Invalid leading character in conversion"
 847                           " to integral");
 848       }
 849       ++b;
 850       ++m;
 851     }
 852   }
 853   FOLLY_RANGE_CHECK(m < past, "No digits found in input string");
 854   FOLLY_RANGE_CHECK(isdigit(*m), "Non-digit character found");
 855   m = detail::findFirstNonDigit<Tgt>(m + 1, past);
 856
 857   Tgt result;
 858   /* static */ if (!std::is_signed<Tgt>::value) {
 859     result = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 860   } else {
 861     auto t = detail::digits_to<typename std::make_unsigned<Tgt>::type>(b, m);
 862     if (negative) {
 863       result = -t;
 864       FOLLY_RANGE_CHECK(is_non_positive(result), "Negative overflow");
 865     } else {
 866       result = t;
 867       FOLLY_RANGE_CHECK(is_non_negative(result), "Overflow");
 868     }
 869   }
 870   src->advance(m - src->data());
 871   return result;
 872 }
 873
 874 /**
 875  * StringPiece to bool, with progress information. Alters the
 876  * StringPiece parameter to munch the already-parsed characters.
 877  */
 878 template <class Tgt>
 879 typename std::enable_if<
 880   std::is_same<typename std::remove_cv<Tgt>::type, bool>::value,
 881   Tgt>::type
 882 to(StringPiece * src) {
 883   return detail::str_to_bool(src);
 884 }
 885
 886 namespace detail {
 887
 888 /**
 889  * Enforce that the suffix following a number is made up only of whitespace.
 890  */
 891 inline void enforceWhitespace(const char* b, const char* e) {
 892   for (; b != e; ++b) {
 893     FOLLY_RANGE_CHECK(isspace(*b), to<std::string>("Non-whitespace: ", *b));
 894   }
 895 }
 896
 897 }  // namespace detail
 898
 899 /**
 900  * String or StringPiece to integrals. Accepts leading and trailing
 901  * whitespace, but no non-space trailing characters.
 902  */
 903 template <class Tgt>
 904 typename std::enable_if<
 905   std::is_integral<Tgt>::value,
 906   Tgt>::type
 907 to(StringPiece src) {
 908   Tgt result = to<Tgt>(&src);
 909   detail::enforceWhitespace(src.data(), src.data() + src.size());
 910   return result;
 911 }
 912
 913 /*******************************************************************************
 914  * Conversions from string types to floating-point types.
 915  ******************************************************************************/
 916
 917 /**
 918  * StringPiece to double, with progress information. Alters the
 919  * StringPiece parameter to munch the already-parsed characters.
 920  */
 921 template <class Tgt>
 922 inline typename std::enable_if<
 923   std::is_floating_point<Tgt>::value,
 924   Tgt>::type
 925 to(StringPiece *const src) {
 926   using namespace double_conversion;
 927   static StringToDoubleConverter
 928     conv(StringToDoubleConverter::ALLOW_TRAILING_JUNK
 929          | StringToDoubleConverter::ALLOW_LEADING_SPACES,
 930          0.0,
 931          // return this for junk input string
 932          std::numeric_limits<double>::quiet_NaN(),
 933          nullptr, nullptr);
 934
 935   FOLLY_RANGE_CHECK(!src->empty(), "No digits found in input string");
 936
 937   int length;
 938   auto result = conv.StringToDouble(src->data(), src->size(),
 939                                        &length); // processed char count
 940
 941   if (!std::isnan(result)) {
 942     src->advance(length);
 943     return result;
 944   }
 945
 946   for (;; src->advance(1)) {
 947     if (src->empty()) {
 948       throw std::range_error("Unable to convert an empty string"
 949                              " to a floating point value.");
 950     }
 951     if (!isspace(src->front())) {
 952       break;
 953     }
 954   }
 955
 956   // Was that "inf[inity]"?
 957   if (src->size() >= 3 && toupper((*src)[0]) == 'I'
 958         && toupper((*src)[1]) == 'N' && toupper((*src)[2]) == 'F') {
 959     if (src->size() >= 8 &&
 960         toupper((*src)[3]) == 'I' &&
 961         toupper((*src)[4]) == 'N' &&
 962         toupper((*src)[5]) == 'I' &&
 963         toupper((*src)[6]) == 'T' &&
 964         toupper((*src)[7]) == 'Y') {
 965       src->advance(8);
 966     } else {
 967       src->advance(3);
 968     }
 969     return std::numeric_limits<Tgt>::infinity();
 970   }
 971
 972   // Was that "-inf[inity]"?
 973   if (src->size() >= 4 && toupper((*src)[0]) == '-'
 974       && toupper((*src)[1]) == 'I' && toupper((*src)[2]) == 'N'
 975       && toupper((*src)[3]) == 'F') {
 976     if (src->size() >= 9 &&
 977         toupper((*src)[4]) == 'I' &&
 978         toupper((*src)[5]) == 'N' &&
 979         toupper((*src)[6]) == 'I' &&
 980         toupper((*src)[7]) == 'T' &&
 981         toupper((*src)[8]) == 'Y') {
 982       src->advance(9);
 983     } else {
 984       src->advance(4);
 985     }
 986     return -std::numeric_limits<Tgt>::infinity();
 987   }
 988
 989   // "nan"?
 990   if (src->size() >= 3 && toupper((*src)[0]) == 'N'
 991         && toupper((*src)[1]) == 'A' && toupper((*src)[2]) == 'N') {
 992     src->advance(3);
 993     return std::numeric_limits<Tgt>::quiet_NaN();
 994   }
 995
 996   // "-nan"?
 997   if (src->size() >= 4 &&
 998       toupper((*src)[0]) == '-' &&
 999       toupper((*src)[1]) == 'N' &&
1000       toupper((*src)[2]) == 'A' &&
1001       toupper((*src)[3]) == 'N') {
1002     src->advance(4);
1003     return -std::numeric_limits<Tgt>::quiet_NaN();
1004   }
1005
1006   // All bets are off
1007   throw std::range_error("Unable to convert \"" + src->toString()
1008                          + "\" to a floating point value.");
1009 }
1010
1011 /**
1012  * Any string, const char*, or StringPiece to double.
1013  */
1014 template <class Tgt>
1015 typename std::enable_if<
1016   std::is_floating_point<Tgt>::value,
1017   Tgt>::type
1018 to(StringPiece src) {
1019   Tgt result = to<double>(&src);
1020   detail::enforceWhitespace(src.data(), src.data() + src.size());
1021   return result;
1022 }
1023
1024 /*******************************************************************************
1025  * Integral to floating point and back
1026  ******************************************************************************/
1027
1028 /**
1029  * Checked conversion from integral to flating point and back. The
1030  * result must be convertible back to the source type without loss of
1031  * precision. This seems Draconian but sometimes is what's needed, and
1032  * complements existing routines nicely. For various rounding
1033  * routines, see <math>.
1034  */
1035 template <class Tgt, class Src>
1036 typename std::enable_if<
1037   (std::is_integral<Src>::value && std::is_floating_point<Tgt>::value)
1038   ||
1039   (std::is_floating_point<Src>::value && std::is_integral<Tgt>::value),
1040   Tgt>::type
1041 to(const Src & value) {
1042   Tgt result = value;
1043   auto witness = static_cast<Src>(result);
1044   if (value != witness) {
1045     throw std::range_error(
1046       to<std::string>("to<>: loss of precision when converting ", value,
1047                       " to type ", typeid(Tgt).name()).c_str());
1048   }
1049   return result;
1050 }
1051
1052 /*******************************************************************************
1053  * Enum to anything and back
1054  ******************************************************************************/
1055
1056 #if defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)
1057 // std::underlying_type became available by gcc 4.7.0
1058
1059 template <class Tgt, class Src>
1060 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1061 to(const Src & value) {
1062   return to<Tgt>(static_cast<typename std::underlying_type<Src>::type>(value));
1063 }
1064
1065 template <class Tgt, class Src>
1066 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1067 to(const Src & value) {
1068   return static_cast<Tgt>(to<typename std::underlying_type<Tgt>::type>(value));
1069 }
1070
1071 #else
1072
1073 template <class Tgt, class Src>
1074 typename std::enable_if<std::is_enum<Src>::value, Tgt>::type
1075 to(const Src & value) {
1076   /* static */ if (Src(-1) < 0) {
1077     /* static */ if (sizeof(Src) <= sizeof(int)) {
1078       return to<Tgt>(static_cast<int>(value));
1079     } else {
1080       return to<Tgt>(static_cast<long>(value));
1081     }
1082   } else {
1083     /* static */ if (sizeof(Src) <= sizeof(int)) {
1084       return to<Tgt>(static_cast<unsigned int>(value));
1085     } else {
1086       return to<Tgt>(static_cast<unsigned long>(value));
1087     }
1088   }
1089 }
1090
1091 template <class Tgt, class Src>
1092 typename std::enable_if<std::is_enum<Tgt>::value, Tgt>::type
1093 to(const Src & value) {
1094   /* static */ if (Tgt(-1) < 0) {
1095     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1096       return static_cast<Tgt>(to<int>(value));
1097     } else {
1098       return static_cast<Tgt>(to<long>(value));
1099     }
1100   } else {
1101     /* static */ if (sizeof(Tgt) <= sizeof(int)) {
1102       return static_cast<Tgt>(to<unsigned int>(value));
1103     } else {
1104       return static_cast<Tgt>(to<unsigned long>(value));
1105     }
1106   }
1107 }
1108
1109 #endif // gcc 4.7 onwards
1110
1111 } // namespace folly
1112
1113 // FOLLY_CONV_INTERNAL is defined by Conv.cpp.  Keep the FOLLY_RANGE_CHECK
1114 // macro for use in Conv.cpp, but #undefine it everywhere else we are included,
1115 // to avoid defining this global macro name in other files that include Conv.h.
1116 #ifndef FOLLY_CONV_INTERNAL
1117 #undef FOLLY_RANGE_CHECK
1118 #endif
1119
1120 #endif /* FOLLY_BASE_CONV_H_ */