boost/spirit/home/x3/support/numeric_utils/detail/extract_int.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2014 Joel de Guzman
   3     Copyright (c) 2001-2011 Hartmut Kaiser
   4     Copyright (c) 2011 Jan Frederick Eick
   5     Copyright (c) 2011 Christopher Jefferson
   6     Copyright (c) 2006 Stephen Nutt
   7
   8     Distributed under the Boost Software License, Version 1.0. (See accompanying
   9     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  10 =============================================================================*/
  11 #if !defined(BOOST_SPIRIT_X3_DETAIL_EXTRACT_INT_APRIL_17_2006_0816AM)
  12 #define BOOST_SPIRIT_X3_DETAIL_EXTRACT_INT_APRIL_17_2006_0816AM
  13
  14 #include <boost/spirit/home/x3/support/unused.hpp>
  15 #include <boost/spirit/home/x3/support/traits/attribute_type.hpp>
  16 #include <boost/spirit/home/x3/support/traits/move_to.hpp>
  17 #include <boost/spirit/home/x3/support/traits/numeric_traits.hpp>
  18 #include <boost/spirit/home/support/char_encoding/ascii.hpp>
  19
  20 #include <boost/preprocessor/repetition/repeat.hpp>
  21 #include <boost/preprocessor/iteration/local.hpp>
  22 #include <boost/preprocessor/comparison/less.hpp>
  23 #include <boost/preprocessor/control/if.hpp>
  24 #include <boost/preprocessor/seq/elem.hpp>
  25
  26 #include <boost/utility/enable_if.hpp>
  27
  28 #include <boost/type_traits/is_integral.hpp>
  29 #include <boost/type_traits/is_signed.hpp>
  30 #include <boost/type_traits/make_unsigned.hpp>
  31
  32 #include <boost/mpl/bool.hpp>
  33 #include <boost/mpl/and.hpp>
  34 #include <boost/limits.hpp>
  35
  36 #include <iterator> // for std::iterator_traits
  37
  38 #if !defined(SPIRIT_NUMERICS_LOOP_UNROLL)
  39 # define SPIRIT_NUMERICS_LOOP_UNROLL 3
  40 #endif
  41
  42 namespace boost { namespace spirit { namespace x3 { namespace detail
  43 {
  44     ///////////////////////////////////////////////////////////////////////////
  45     //
  46     //  The maximum radix digits that can be represented without
  47     //  overflow:
  48     //
  49     //          template<typename T, unsigned Radix>
  50     //          struct digits_traits::value;
  51     //
  52     ///////////////////////////////////////////////////////////////////////////
  53     template <typename T, unsigned Radix>
  54     struct digits_traits;
  55
  56     template <int Digits, unsigned Radix>
  57     struct digits2_to_n;
  58
  59 // lookup table for log2(x) : 2 <= x <= 36
  60 #define BOOST_SPIRIT_X3_LOG2 (#error)(#error)                                   \
  61         (1000000)(1584960)(2000000)(2321920)(2584960)(2807350)                  \
  62         (3000000)(3169920)(3321920)(3459430)(3584960)(3700430)                  \
  63         (3807350)(3906890)(4000000)(4087460)(4169920)(4247920)                  \
  64         (4321920)(4392310)(4459430)(4523560)(4584960)(4643850)                  \
  65         (4700430)(4754880)(4807350)(4857980)(4906890)(4954190)                  \
  66         (5000000)(5044390)(5087460)(5129280)(5169925)                           \
  67     /***/
  68
  69 #define BOOST_PP_LOCAL_MACRO(Radix)                                             \
  70     template <int Digits> struct digits2_to_n<Digits, Radix>                    \
  71     {                                                                           \
  72         BOOST_STATIC_CONSTANT(int, value = static_cast<int>(                    \
  73             (Digits * 1000000) /                                                \
  74                 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_X3_LOG2)));               \
  75     };                                                                          \
  76     /***/
  77
  78 #define BOOST_PP_LOCAL_LIMITS (2, 36)
  79 #include BOOST_PP_LOCAL_ITERATE()
  80
  81 #undef BOOST_SPIRIT_X3_LOG2
  82
  83     template <typename T, unsigned Radix>
  84     struct digits_traits : digits2_to_n<std::numeric_limits<T>::digits, Radix>
  85     {
  86         static_assert(std::numeric_limits<T>::radix == 2, "");
  87     };
  88
  89     template <typename T>
  90     struct digits_traits<T, 10>
  91     {
  92         static int constexpr value = std::numeric_limits<T>::digits10;
  93     };
  94
  95     ///////////////////////////////////////////////////////////////////////////
  96     //
  97     //  Traits class for radix specific number conversion
  98     //
  99     //      Test the validity of a single character:
 100     //
 101     //          template<typename Char> static bool is_valid(Char ch);
 102     //
 103     //      Convert a digit from character representation to binary
 104     //      representation:
 105     //
 106     //          template<typename Char> static int digit(Char ch);
 107     //
 108     ///////////////////////////////////////////////////////////////////////////
 109     template <unsigned Radix>
 110     struct radix_traits
 111     {
 112         template <typename Char>
 113         inline static bool is_valid(Char ch)
 114         {
 115             return (ch >= '0' && ch <= (Radix > 10 ? '9' : static_cast<Char>('0' + Radix -1)))
 116                 || (Radix > 10 && ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1))
 117                 || (Radix > 10 && ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1));
 118         }
 119
 120         template <typename Char>
 121         inline static unsigned digit(Char ch)
 122         {
 123             return (Radix <= 10 || (ch >= '0' && ch <= '9'))
 124                 ? ch - '0'
 125                 : char_encoding::ascii::tolower(ch) - 'a' + 10;
 126         }
 127     };
 128
 129     ///////////////////////////////////////////////////////////////////////////
 130     //  positive_accumulator/negative_accumulator: Accumulator policies for
 131     //  extracting integers. Use positive_accumulator if number is positive.
 132     //  Use negative_accumulator if number is negative.
 133     ///////////////////////////////////////////////////////////////////////////
 134     template <unsigned Radix>
 135     struct positive_accumulator
 136     {
 137         template <typename T, typename Char>
 138         inline static void add(T& n, Char ch, mpl::false_) // unchecked add
 139         {
 140             const int digit = radix_traits<Radix>::digit(ch);
 141             n = n * T(Radix) + T(digit);
 142         }
 143
 144         template <typename T, typename Char>
 145         inline static bool add(T& n, Char ch, mpl::true_) // checked add
 146         {
 147             // Ensure n *= Radix will not overflow
 148             T const max = (std::numeric_limits<T>::max)();
 149             T const val = max / Radix;
 150             if (n > val)
 151                 return false;
 152
 153             T tmp = n * Radix;
 154
 155             // Ensure n += digit will not overflow
 156             const int digit = radix_traits<Radix>::digit(ch);
 157             if (tmp > max - digit)
 158                 return false;
 159
 160             n = tmp + static_cast<T>(digit);
 161             return true;
 162         }
 163     };
 164
 165     template <unsigned Radix>
 166     struct negative_accumulator
 167     {
 168         template <typename T, typename Char>
 169         inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract
 170         {
 171             const int digit = radix_traits<Radix>::digit(ch);
 172             n = n * T(Radix) - T(digit);
 173         }
 174
 175         template <typename T, typename Char>
 176         inline static bool add(T& n, Char ch, mpl::true_) // checked subtract
 177         {
 178             // Ensure n *= Radix will not underflow
 179             T const min = (std::numeric_limits<T>::min)();
 180             T const val = min / T(Radix);
 181             if (n < val)
 182                 return false;
 183
 184             T tmp = n * Radix;
 185
 186             // Ensure n -= digit will not underflow
 187             int const digit = radix_traits<Radix>::digit(ch);
 188             if (tmp < min + digit)
 189                 return false;
 190
 191             n = tmp - static_cast<T>(digit);
 192             return true;
 193         }
 194     };
 195
 196     ///////////////////////////////////////////////////////////////////////////
 197     //  Common code for extract_int::parse specializations
 198     ///////////////////////////////////////////////////////////////////////////
 199     template <unsigned Radix, typename Accumulator, int MaxDigits>
 200     struct int_extractor
 201     {
 202         template <typename Char, typename T>
 203         inline static bool
 204         call(Char ch, std::size_t count, T& n, mpl::true_)
 205         {
 206             std::size_t constexpr
 207                 overflow_free = digits_traits<T, Radix>::value - 1;
 208
 209             if (count < overflow_free)
 210             {
 211                 Accumulator::add(n, ch, mpl::false_());
 212             }
 213             else
 214             {
 215                 if (!Accumulator::add(n, ch, mpl::true_()))
 216                     return false; //  over/underflow!
 217             }
 218             return true;
 219         }
 220
 221         template <typename Char, typename T>
 222         inline static bool
 223         call(Char ch, std::size_t /*count*/, T& n, mpl::false_)
 224         {
 225             // no need to check for overflow
 226             Accumulator::add(n, ch, mpl::false_());
 227             return true;
 228         }
 229
 230         template <typename Char>
 231         inline static bool
 232         call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)
 233         {
 234             return true;
 235         }
 236
 237         template <typename Char, typename T>
 238         inline static bool
 239         call(Char ch, std::size_t count, T& n)
 240         {
 241             return call(ch, count, n
 242               , mpl::bool_<
 243                     (   (MaxDigits < 0)
 244                     ||  (MaxDigits > digits_traits<T, Radix>::value)
 245                     )
 246                   && traits::check_overflow<T>::value
 247                 >()
 248             );
 249         }
 250     };
 251
 252     ///////////////////////////////////////////////////////////////////////////
 253     //  End of loop checking: check if the number of digits
 254     //  being parsed exceeds MaxDigits. Note: if MaxDigits == -1
 255     //  we don't do any checking.
 256     ///////////////////////////////////////////////////////////////////////////
 257     template <int MaxDigits>
 258     struct check_max_digits
 259     {
 260         inline static bool
 261         call(std::size_t count)
 262         {
 263             return count < MaxDigits; // bounded
 264         }
 265     };
 266
 267     template <>
 268     struct check_max_digits<-1>
 269     {
 270         inline static bool
 271         call(std::size_t /*count*/)
 272         {
 273             return true; // unbounded
 274         }
 275     };
 276
 277     ///////////////////////////////////////////////////////////////////////////
 278     //  extract_int: main code for extracting integers
 279     ///////////////////////////////////////////////////////////////////////////
 280 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                   \
 281         if (!check_max_digits<MaxDigits>::call(count + leading_zeros)           \
 282             || it == last)                                                      \
 283             break;                                                              \
 284         ch = *it;                                                               \
 285         if (!radix_check::is_valid(ch) || !extractor::call(ch, count, val))     \
 286             break;                                                              \
 287         ++it;                                                                   \
 288         ++count;                                                                \
 289     /**/
 290
 291     template <
 292         typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
 293       , typename Accumulator = positive_accumulator<Radix>
 294       , bool Accumulate = false
 295     >
 296     struct extract_int
 297     {
 298 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 299 # pragma warning(push)
 300 # pragma warning(disable: 4127)   // conditional expression is constant
 301 #endif
 302         template <typename Iterator, typename Attribute>
 303         inline static bool
 304         parse_main(
 305             Iterator& first
 306           , Iterator const& last
 307           , Attribute& attr)
 308         {
 309             typedef radix_traits<Radix> radix_check;
 310             typedef int_extractor<Radix, Accumulator, MaxDigits> extractor;
 311             typedef typename
 312                 std::iterator_traits<Iterator>::value_type
 313             char_type;
 314
 315             Iterator it = first;
 316             std::size_t leading_zeros = 0;
 317             if (!Accumulate)
 318             {
 319                 // skip leading zeros
 320                 while (it != last && *it == '0' && leading_zeros < MaxDigits)
 321                 {
 322                     ++it;
 323                     ++leading_zeros;
 324                 }
 325             }
 326
 327             typedef typename
 328                 traits::attribute_type<Attribute>::type
 329             attribute_type;
 330
 331             attribute_type val = Accumulate ? attr : attribute_type(0);
 332             std::size_t count = 0;
 333             char_type ch;
 334
 335             while (true)
 336             {
 337                 BOOST_PP_REPEAT(
 338                     SPIRIT_NUMERICS_LOOP_UNROLL
 339                   , SPIRIT_NUMERIC_INNER_LOOP, _)
 340             }
 341
 342             if (count + leading_zeros >= MinDigits)
 343             {
 344                 traits::move_to(val, attr);
 345                 first = it;
 346                 return true;
 347             }
 348             return false;
 349         }
 350 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 351 # pragma warning(pop)
 352 #endif
 353
 354         template <typename Iterator>
 355         inline static bool
 356         parse(
 357             Iterator& first
 358           , Iterator const& last
 359           , unused_type)
 360         {
 361             T n = 0; // must calculate value to detect over/underflow
 362             return parse_main(first, last, n);
 363         }
 364
 365         template <typename Iterator, typename Attribute>
 366         inline static bool
 367         parse(
 368             Iterator& first
 369           , Iterator const& last
 370           , Attribute& attr)
 371         {
 372             return parse_main(first, last, attr);
 373         }
 374     };
 375 #undef SPIRIT_NUMERIC_INNER_LOOP
 376
 377     ///////////////////////////////////////////////////////////////////////////
 378     //  extract_int: main code for extracting integers
 379     //  common case where MinDigits == 1 and MaxDigits = -1
 380     ///////////////////////////////////////////////////////////////////////////
 381 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                   \
 382         if (it == last)                                                         \
 383             break;                                                              \
 384         ch = *it;                                                               \
 385         if (!radix_check::is_valid(ch))                                         \
 386             break;                                                              \
 387         if (!extractor::call(ch, count, val))                                   \
 388             return false;                                                       \
 389         ++it;                                                                   \
 390         ++count;                                                                \
 391     /**/
 392
 393     template <typename T, unsigned Radix, typename Accumulator, bool Accumulate>
 394     struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate>
 395     {
 396 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 397 # pragma warning(push)
 398 # pragma warning(disable: 4127)   // conditional expression is constant
 399 #endif
 400         template <typename Iterator, typename Attribute>
 401         inline static bool
 402         parse_main(
 403             Iterator& first
 404           , Iterator const& last
 405           , Attribute& attr)
 406         {
 407             typedef radix_traits<Radix> radix_check;
 408             typedef int_extractor<Radix, Accumulator, -1> extractor;
 409             typedef typename
 410                 std::iterator_traits<Iterator>::value_type
 411             char_type;
 412
 413             Iterator it = first;
 414             std::size_t count = 0;
 415             if (!Accumulate)
 416             {
 417                 // skip leading zeros
 418                 while (it != last && *it == '0')
 419                 {
 420                     ++it;
 421                     ++count;
 422                 }
 423
 424                 if (it == last)
 425                 {
 426                     if (count == 0) // must have at least one digit
 427                         return false;
 428                     attr = 0;
 429                     first = it;
 430                     return true;
 431                 }
 432             }
 433
 434             typedef typename
 435                 traits::attribute_type<Attribute>::type
 436             attribute_type;
 437
 438             attribute_type val = Accumulate ? attr : attribute_type(0);
 439             char_type ch = *it;
 440
 441             if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val))
 442             {
 443                 if (count == 0) // must have at least one digit
 444                     return false;
 445                 traits::move_to(val, attr);
 446                 first = it;
 447                 return true;
 448             }
 449
 450             count = 0;
 451             ++it;
 452             while (true)
 453             {
 454                 BOOST_PP_REPEAT(
 455                     SPIRIT_NUMERICS_LOOP_UNROLL
 456                   , SPIRIT_NUMERIC_INNER_LOOP, _)
 457             }
 458
 459             traits::move_to(val, attr);
 460             first = it;
 461             return true;
 462         }
 463 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 464 # pragma warning(pop)
 465 #endif
 466
 467         template <typename Iterator>
 468         inline static bool
 469         parse(
 470             Iterator& first
 471           , Iterator const& last
 472           , unused_type)
 473         {
 474             T n = 0; // must calculate value to detect over/underflow
 475             return parse_main(first, last, n);
 476         }
 477
 478         template <typename Iterator, typename Attribute>
 479         inline static bool
 480         parse(
 481             Iterator& first
 482           , Iterator const& last
 483           , Attribute& attr)
 484         {
 485             return parse_main(first, last, attr);
 486         }
 487     };
 488
 489 #undef SPIRIT_NUMERIC_INNER_LOOP
 490 }}}}
 491
 492 #endif