folly/Conv.h

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