folly/Conv.cpp

   1 /*
   2  * Copyright 2016 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 #define FOLLY_CONV_INTERNAL
  17 #include <folly/Conv.h>
  18
  19 namespace folly {
  20 namespace detail {
  21
  22 extern const char digit1[101] =
  23   "00000000001111111111222222222233333333334444444444"
  24   "55555555556666666666777777777788888888889999999999";
  25 extern const char digit2[101] =
  26   "01234567890123456789012345678901234567890123456789"
  27   "01234567890123456789012345678901234567890123456789";
  28
  29 template <> const char *const MaxString<bool>::value = "true";
  30 template <> const char *const MaxString<uint8_t>::value = "255";
  31 template <> const char *const MaxString<uint16_t>::value = "65535";
  32 template <> const char *const MaxString<uint32_t>::value = "4294967295";
  33 #if __SIZEOF_LONG__ == 4
  34 template <> const char *const MaxString<unsigned long>::value =
  35   "4294967295";
  36 #else
  37 template <> const char *const MaxString<unsigned long>::value =
  38   "18446744073709551615";
  39 #endif
  40 static_assert(sizeof(unsigned long) >= 4,
  41               "Wrong value for MaxString<unsigned long>::value,"
  42               " please update.");
  43 template <> const char *const MaxString<unsigned long long>::value =
  44   "18446744073709551615";
  45 static_assert(sizeof(unsigned long long) >= 8,
  46               "Wrong value for MaxString<unsigned long long>::value"
  47               ", please update.");
  48
  49 #ifdef FOLLY_HAVE_INT128_T
  50 template <> const char *const MaxString<__uint128_t>::value =
  51   "340282366920938463463374607431768211455";
  52 #endif
  53
  54 namespace {
  55 /*
  56  * Lookup tables that converts from a decimal character value to an integral
  57  * binary value, shifted by a decimal "shift" multiplier.
  58  * For all character values in the range '0'..'9', the table at those
  59  * index locations returns the actual decimal value shifted by the multiplier.
  60  * For all other values, the lookup table returns an invalid OOR value.
  61  */
  62 // Out-of-range flag value, larger than the largest value that can fit in
  63 // four decimal bytes (9999), but four of these added up together should
  64 // still not overflow uint16_t.
  65 constexpr int32_t OOR = 10000;
  66
  67 FOLLY_ALIGNED(16) constexpr uint16_t shift1[] = {
  68   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
  69   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
  70   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
  71   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
  72   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
  73   1, 2, 3, 4, 5, 6, 7, 8, 9, OOR, OOR,
  74   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
  75   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
  76   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
  77   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
  78   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
  79   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
  80   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
  81   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
  82   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
  83   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
  84   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
  85   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
  86   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
  87   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
  88   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
  89   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
  90   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
  91   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
  92   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
  93   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
  94 };
  95
  96 FOLLY_ALIGNED(16) constexpr uint16_t shift10[] = {
  97   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
  98   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
  99   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 100   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 101   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 102   10, 20, 30, 40, 50, 60, 70, 80, 90, OOR, OOR,
 103   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 104   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 105   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 106   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 107   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 108   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 109   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 110   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 111   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 112   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 113   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 114   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 115   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 116   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 117   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 118   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 119   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 120   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 121   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 122   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 123 };
 124
 125 FOLLY_ALIGNED(16) constexpr uint16_t shift100[] = {
 126   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 127   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 128   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 129   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 130   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 131   100, 200, 300, 400, 500, 600, 700, 800, 900, OOR, OOR,
 132   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 133   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 134   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 135   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 136   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 137   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 138   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 139   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 140   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 141   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 142   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 143   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 144   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 145   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 146   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 147   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 148   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 149   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 150   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 151   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 152 };
 153
 154 FOLLY_ALIGNED(16) constexpr uint16_t shift1000[] = {
 155   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 0-9
 156   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  10
 157   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  20
 158   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  30
 159   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, 0,         //  40
 160   1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, OOR, OOR,
 161   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  60
 162   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  70
 163   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  80
 164   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  //  90
 165   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 100
 166   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 110
 167   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 120
 168   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 130
 169   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 140
 170   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 150
 171   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 160
 172   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 170
 173   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 180
 174   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 190
 175   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 200
 176   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 210
 177   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 220
 178   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 230
 179   OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR, OOR,  // 240
 180   OOR, OOR, OOR, OOR, OOR, OOR                       // 250
 181 };
 182 }
 183
 184 inline bool bool_str_cmp(const char** b, size_t len, const char* value) {
 185   // Can't use strncasecmp, since we want to ensure that the full value matches
 186   const char* p = *b;
 187   const char* e = *b + len;
 188   const char* v = value;
 189   while (*v != '\0') {
 190     if (p == e || tolower(*p) != *v) { // value is already lowercase
 191       return false;
 192     }
 193     ++p;
 194     ++v;
 195   }
 196
 197   *b = p;
 198   return true;
 199 }
 200
 201 bool str_to_bool(StringPiece* src) {
 202   auto b = src->begin(), e = src->end();
 203   for (;; ++b) {
 204     FOLLY_RANGE_CHECK_STRINGPIECE(
 205       b < e, "No non-whitespace characters found in input string", *src);
 206     if (!isspace(*b)) break;
 207   }
 208
 209   bool result;
 210   size_t len = e - b;
 211   switch (*b) {
 212     case '0':
 213     case '1': {
 214       result = false;
 215       for (; b < e && isdigit(*b); ++b) {
 216         FOLLY_RANGE_CHECK_STRINGPIECE(
 217           !result && (*b == '0' || *b == '1'),
 218           "Integer overflow when parsing bool: must be 0 or 1", *src);
 219         result = (*b == '1');
 220       }
 221       break;
 222     }
 223     case 'y':
 224     case 'Y':
 225       result = true;
 226       if (!bool_str_cmp(&b, len, "yes")) {
 227         ++b;  // accept the single 'y' character
 228       }
 229       break;
 230     case 'n':
 231     case 'N':
 232       result = false;
 233       if (!bool_str_cmp(&b, len, "no")) {
 234         ++b;
 235       }
 236       break;
 237     case 't':
 238     case 'T':
 239       result = true;
 240       if (!bool_str_cmp(&b, len, "true")) {
 241         ++b;
 242       }
 243       break;
 244     case 'f':
 245     case 'F':
 246       result = false;
 247       if (!bool_str_cmp(&b, len, "false")) {
 248         ++b;
 249       }
 250       break;
 251     case 'o':
 252     case 'O':
 253       if (bool_str_cmp(&b, len, "on")) {
 254         result = true;
 255       } else if (bool_str_cmp(&b, len, "off")) {
 256         result = false;
 257       } else {
 258         FOLLY_RANGE_CHECK_STRINGPIECE(false, "Invalid value for bool", *src);
 259       }
 260       break;
 261     default:
 262       FOLLY_RANGE_CHECK_STRINGPIECE(false, "Invalid value for bool", *src);
 263   }
 264
 265   src->assign(b, e);
 266   return result;
 267 }
 268
 269 /**
 270  * String represented as a pair of pointers to char to unsigned
 271  * integrals. Assumes NO whitespace before or after, and also that the
 272  * string is composed entirely of digits. Tgt must be unsigned, and no
 273  * sign is allowed in the string (even it's '+'). String may be empty,
 274  * in which case digits_to throws.
 275  */
 276 template <class Tgt>
 277 Tgt digits_to(const char* b, const char* e) {
 278
 279   static_assert(!std::is_signed<Tgt>::value, "Unsigned type expected");
 280   assert(b <= e);
 281
 282   const size_t size = e - b;
 283
 284   /* Although the string is entirely made of digits, we still need to
 285    * check for overflow.
 286    */
 287   if (size >= std::numeric_limits<Tgt>::digits10 + 1) {
 288     // Leading zeros? If so, recurse to keep things simple
 289     if (b < e && *b == '0') {
 290       for (++b;; ++b) {
 291         if (b == e)
 292           return 0; // just zeros, e.g. "0000"
 293         if (*b != '0')
 294           return digits_to<Tgt>(b, e);
 295       }
 296     }
 297     FOLLY_RANGE_CHECK_BEGIN_END(
 298         size == std::numeric_limits<Tgt>::digits10 + 1 &&
 299             strncmp(b, detail::MaxString<Tgt>::value, size) <= 0,
 300         "Numeric overflow upon conversion",
 301         b,
 302         e);
 303   }
 304
 305   // Here we know that the number won't overflow when
 306   // converted. Proceed without checks.
 307
 308   Tgt result = 0;
 309
 310   for (; e - b >= 4; b += 4) {
 311     result *= 10000;
 312     const int32_t r0 = shift1000[static_cast<size_t>(b[0])];
 313     const int32_t r1 = shift100[static_cast<size_t>(b[1])];
 314     const int32_t r2 = shift10[static_cast<size_t>(b[2])];
 315     const int32_t r3 = shift1[static_cast<size_t>(b[3])];
 316     const auto sum = r0 + r1 + r2 + r3;
 317     assert(sum < OOR && "Assumption: string only has digits");
 318     result += sum;
 319   }
 320
 321   switch (e - b) {
 322   case 3: {
 323     const int32_t r0 = shift100[static_cast<size_t>(b[0])];
 324     const int32_t r1 = shift10[static_cast<size_t>(b[1])];
 325     const int32_t r2 = shift1[static_cast<size_t>(b[2])];
 326     const auto sum = r0 + r1 + r2;
 327     assert(sum < OOR && "Assumption: string only has digits");
 328     return result * 1000 + sum;
 329   }
 330   case 2: {
 331     const int32_t r0 = shift10[static_cast<size_t>(b[0])];
 332     const int32_t r1 = shift1[static_cast<size_t>(b[1])];
 333     const auto sum = r0 + r1;
 334     assert(sum < OOR && "Assumption: string only has digits");
 335     return result * 100 + sum;
 336   }
 337   case 1: {
 338     const int32_t sum = shift1[static_cast<size_t>(b[0])];
 339     assert(sum < OOR && "Assumption: string only has digits");
 340     return result * 10 + sum;
 341   }
 342   }
 343
 344   assert(b == e);
 345   FOLLY_RANGE_CHECK_BEGIN_END(
 346       size > 0, "Found no digits to convert in input", b, e);
 347   return result;
 348 }
 349
 350 template unsigned char digits_to<unsigned char>(const char* b, const char* e);
 351 template unsigned short digits_to<unsigned short>(const char* b, const char* e);
 352 template unsigned int digits_to<unsigned int>(const char* b, const char* e);
 353 template unsigned long digits_to<unsigned long>(const char* b, const char* e);
 354 template unsigned long long digits_to<unsigned long long>(const char* b,
 355                                                           const char* e);
 356 #if FOLLY_HAVE_INT128_T
 357 template unsigned __int128 digits_to<unsigned __int128>(const char* b,
 358                                                         const char* e);
 359 #endif
 360
 361 } // namespace detail
 362 } // namespace folly