ceph/src/boost/boost/spirit/home/qi/numeric/detail/numeric_utils.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2011 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(SPIRIT_NUMERIC_UTILS_APRIL_17_2006_0816AM)
  12 #define SPIRIT_NUMERIC_UTILS_APRIL_17_2006_0816AM
  13
  14 #if defined(_MSC_VER)
  15 #pragma once
  16 #endif
  17
  18 #include <boost/detail/iterator.hpp>
  19 #include <boost/spirit/home/support/unused.hpp>
  20 #include <boost/spirit/home/qi/detail/attributes.hpp>
  21 #include <boost/spirit/home/support/char_encoding/ascii.hpp>
  22 #include <boost/spirit/home/support/numeric_traits.hpp>
  23 #include <boost/preprocessor/repetition/repeat.hpp>
  24 #include <boost/preprocessor/iteration/local.hpp>
  25 #include <boost/preprocessor/comparison/less.hpp>
  26 #include <boost/preprocessor/control/if.hpp>
  27 #include <boost/preprocessor/seq/elem.hpp>
  28 #include <boost/utility/enable_if.hpp>
  29 #include <boost/type_traits/is_integral.hpp>
  30 #include <boost/type_traits/is_signed.hpp>
  31 #include <boost/mpl/bool.hpp>
  32 #include <boost/mpl/and.hpp>
  33 #include <boost/limits.hpp>
  34 #include <boost/integer_traits.hpp>
  35
  36 #if defined(BOOST_MSVC)
  37 # pragma warning(push)
  38 # pragma warning(disable: 4127) // conditional expression is constant
  39 #endif
  40
  41 #if !defined(SPIRIT_NUMERICS_LOOP_UNROLL)
  42 # define SPIRIT_NUMERICS_LOOP_UNROLL 3
  43 #endif
  44
  45 namespace boost { namespace spirit { namespace qi { namespace detail
  46 {
  47     ///////////////////////////////////////////////////////////////////////////
  48     //
  49     //  The maximum radix digits that can be represented without
  50     //  overflow:
  51     //
  52     //          template<typename T, unsigned Radix>
  53     //          struct digits_traits::value;
  54     //
  55     ///////////////////////////////////////////////////////////////////////////
  56     template <typename T, unsigned Radix>
  57     struct digits_traits;
  58
  59 // lookup table for log2(x) : 2 <= x <= 36
  60 #define BOOST_SPIRIT_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 <typename T> struct digits_traits<T, Radix>                      \
  71     {                                                                         \
  72         typedef std::numeric_limits<T> numeric_limits_type;                   \
  73         BOOST_STATIC_CONSTANT(int, value = static_cast<int>(                  \
  74             (numeric_limits_type::digits * 1000000) /                         \
  75                 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_LOG2)));                \
  76     };                                                                        \
  77     /***/
  78
  79 #define BOOST_PP_LOCAL_LIMITS (2, 36)
  80 #include BOOST_PP_LOCAL_ITERATE()
  81
  82 #undef BOOST_SPIRIT_LOG2
  83
  84     ///////////////////////////////////////////////////////////////////////////
  85     //
  86     //  Traits class for radix specific number conversion
  87     //
  88     //      Test the validity of a single character:
  89     //
  90     //          template<typename Char> static bool is_valid(Char ch);
  91     //
  92     //      Convert a digit from character representation to binary
  93     //      representation:
  94     //
  95     //          template<typename Char> static int digit(Char ch);
  96     //
  97     ///////////////////////////////////////////////////////////////////////////
  98     template <unsigned Radix>
  99     struct radix_traits
 100     {
 101         template <typename Char>
 102         inline static bool is_valid(Char ch)
 103         {
 104             if (Radix <= 10)
 105                 return (ch >= '0' && ch <= static_cast<Char>('0' + Radix -1));
 106             return (ch >= '0' && ch <= '9')
 107                 || (ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1))
 108                 || (ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1));
 109         }
 110
 111         template <typename Char>
 112         inline static unsigned digit(Char ch)
 113         {
 114             if (Radix <= 10 || (ch >= '0' && ch <= '9'))
 115                 return ch - '0';
 116             return spirit::char_encoding::ascii::tolower(ch) - 'a' + 10;
 117         }
 118     };
 119
 120     template <typename T, T Val>
 121     struct constexpr_int
 122     {
 123         BOOST_STATIC_CONSTEXPR T value = Val;
 124     };
 125
 126     ///////////////////////////////////////////////////////////////////////////
 127     //  positive_accumulator/negative_accumulator: Accumulator policies for
 128     //  extracting integers. Use positive_accumulator if number is positive.
 129     //  Use negative_accumulator if number is negative.
 130     ///////////////////////////////////////////////////////////////////////////
 131     template <unsigned Radix>
 132     struct positive_accumulator
 133     {
 134         template <typename T, typename Char>
 135         inline static void add(T& n, Char ch, mpl::false_) // unchecked add
 136         {
 137             const int digit = radix_traits<Radix>::digit(ch);
 138             n = n * T(Radix) + T(digit);
 139         }
 140
 141         template <typename T, typename Char>
 142         inline static bool add(T& n, Char ch, mpl::true_) // checked add
 143         {
 144             // Ensure n *= Radix will not overflow
 145             typedef constexpr_int<T, boost::integer_traits<T>::const_max> max;
 146             typedef constexpr_int<T, max::value / Radix> val;
 147
 148             if (n > val::value)
 149                 return false;
 150
 151             n *= Radix;
 152
 153             // Ensure n += digit will not overflow
 154             const int digit = radix_traits<Radix>::digit(ch);
 155             if (n > max::value - digit)
 156                 return false;
 157
 158             n += static_cast<T>(digit);
 159             return true;
 160         }
 161     };
 162
 163     template <unsigned Radix>
 164     struct negative_accumulator
 165     {
 166         template <typename T, typename Char>
 167         inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract
 168         {
 169             const int digit = radix_traits<Radix>::digit(ch);
 170             n = n * T(Radix) - T(digit);
 171         }
 172
 173         template <typename T, typename Char>
 174         inline static bool add(T& n, Char ch, mpl::true_) // checked subtract
 175         {
 176             // Ensure n *= Radix will not underflow
 177             typedef constexpr_int<T, boost::integer_traits<T>::const_min> min;
 178             typedef constexpr_int<T, (min::value + 1) / T(Radix)> val;
 179
 180             if (n < val::value)
 181                 return false;
 182
 183             n *= Radix;
 184
 185             // Ensure n -= digit will not underflow
 186             int const digit = radix_traits<Radix>::digit(ch);
 187             if (n < min::value + digit)
 188                 return false;
 189
 190             n -= static_cast<T>(digit);
 191             return true;
 192         }
 193     };
 194
 195     ///////////////////////////////////////////////////////////////////////////
 196     //  Common code for extract_int::parse specializations
 197     ///////////////////////////////////////////////////////////////////////////
 198     template <unsigned Radix, typename Accumulator, int MaxDigits, bool AlwaysCheckOverflow>
 199     struct int_extractor
 200     {
 201         template <typename Char, typename T>
 202         inline static bool
 203         call(Char ch, std::size_t count, T& n, mpl::true_)
 204         {
 205             typedef constexpr_int<std::size_t, digits_traits<T, Radix>::value - 1> overflow_free;
 206
 207             if (!AlwaysCheckOverflow && (count < overflow_free::value))
 208             {
 209                 Accumulator::add(n, ch, mpl::false_());
 210             }
 211             else
 212             {
 213                 if (!Accumulator::add(n, ch, mpl::true_()))
 214                     return false; //  over/underflow!
 215             }
 216             return true;
 217         }
 218
 219         template <typename Char, typename T>
 220         inline static bool
 221         call(Char ch, std::size_t /*count*/, T& n, mpl::false_)
 222         {
 223             // no need to check for overflow
 224             Accumulator::add(n, ch, mpl::false_());
 225             return true;
 226         }
 227
 228         template <typename Char>
 229         inline static bool
 230         call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)
 231         {
 232             return true;
 233         }
 234
 235         template <typename Char, typename T>
 236         inline static bool
 237         call(Char ch, std::size_t count, T& n)
 238         {
 239             return call(ch, count, n
 240               , mpl::bool_<
 241                     (   (MaxDigits < 0)
 242                     ||  (MaxDigits > digits_traits<T, Radix>::value)
 243                     )
 244                   && traits::check_overflow<T>::value
 245                 >()
 246             );
 247         }
 248     };
 249
 250     ///////////////////////////////////////////////////////////////////////////
 251     //  End of loop checking: check if the number of digits
 252     //  being parsed exceeds MaxDigits. Note: if MaxDigits == -1
 253     //  we don't do any checking.
 254     ///////////////////////////////////////////////////////////////////////////
 255     template <int MaxDigits>
 256     struct check_max_digits
 257     {
 258         inline static bool
 259         call(std::size_t count)
 260         {
 261             return count < MaxDigits; // bounded
 262         }
 263     };
 264
 265     template <>
 266     struct check_max_digits<-1>
 267     {
 268         inline static bool
 269         call(std::size_t /*count*/)
 270         {
 271             return true; // unbounded
 272         }
 273     };
 274
 275     ///////////////////////////////////////////////////////////////////////////
 276     //  extract_int: main code for extracting integers
 277     ///////////////////////////////////////////////////////////////////////////
 278 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
 279         if (!check_max_digits<MaxDigits>::call(count + leading_zeros)         \
 280             || it == last)                                                    \
 281         {                                                                     \
 282             break;                                                            \
 283         }                                                                     \
 284         ch = *it;                                                             \
 285         if (!radix_check::is_valid(ch))                                       \
 286         {                                                                     \
 287             break;                                                            \
 288         }                                                                     \
 289         if (!extractor::call(ch, count, val))                                 \
 290         {                                                                     \
 291             if (IgnoreOverflowDigits)                                         \
 292             {                                                                 \
 293                 first = it;                                                   \
 294             }                                                                 \
 295             traits::assign_to(val, attr);                                     \
 296             return IgnoreOverflowDigits;                                      \
 297         }                                                                     \
 298         ++it;                                                                 \
 299         ++count;                                                              \
 300     /**/
 301
 302     template <
 303         typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
 304       , typename Accumulator = positive_accumulator<Radix>
 305       , bool Accumulate = false
 306       , bool IgnoreOverflowDigits = false
 307     >
 308     struct extract_int
 309     {
 310 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 311 # pragma warning(push)
 312 # pragma warning(disable: 4127)   // conditional expression is constant
 313 #endif
 314         template <typename Iterator, typename Attribute>
 315         inline static bool
 316         parse_main(
 317             Iterator& first
 318           , Iterator const& last
 319           , Attribute& attr)
 320         {
 321             typedef radix_traits<Radix> radix_check;
 322             typedef int_extractor<Radix, Accumulator, MaxDigits, Accumulate> extractor;
 323             typedef typename
 324                 boost::detail::iterator_traits<Iterator>::value_type
 325             char_type;
 326
 327             Iterator it = first;
 328             std::size_t leading_zeros = 0;
 329             if (!Accumulate)
 330             {
 331                 // skip leading zeros
 332                 while (it != last && *it == '0' && (MaxDigits < 0 || leading_zeros < static_cast< std::size_t >(MaxDigits)))
 333                 {
 334                     ++it;
 335                     ++leading_zeros;
 336                 }
 337             }
 338
 339             typedef typename
 340                 traits::attribute_type<Attribute>::type
 341             attribute_type;
 342
 343             attribute_type val = Accumulate ? attr : attribute_type(0);
 344             std::size_t count = 0;
 345             char_type ch;
 346
 347             while (true)
 348             {
 349                 BOOST_PP_REPEAT(
 350                     SPIRIT_NUMERICS_LOOP_UNROLL
 351                   , SPIRIT_NUMERIC_INNER_LOOP, _)
 352             }
 353
 354             if (count + leading_zeros >= MinDigits)
 355             {
 356                 traits::assign_to(val, attr);
 357                 first = it;
 358                 return true;
 359             }
 360             return false;
 361         }
 362 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 363 # pragma warning(pop)
 364 #endif
 365
 366         template <typename Iterator>
 367         inline static bool
 368         parse(
 369             Iterator& first
 370           , Iterator const& last
 371           , unused_type)
 372         {
 373             T n = 0; // must calculate value to detect over/underflow
 374             return parse_main(first, last, n);
 375         }
 376
 377         template <typename Iterator, typename Attribute>
 378         inline static bool
 379         parse(
 380             Iterator& first
 381           , Iterator const& last
 382           , Attribute& attr)
 383         {
 384             return parse_main(first, last, attr);
 385         }
 386     };
 387 #undef SPIRIT_NUMERIC_INNER_LOOP
 388
 389     ///////////////////////////////////////////////////////////////////////////
 390     //  extract_int: main code for extracting integers
 391     //  common case where MinDigits == 1 and MaxDigits = -1
 392     ///////////////////////////////////////////////////////////////////////////
 393 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
 394         if (it == last)                                                       \
 395         {                                                                     \
 396             break;                                                            \
 397         }                                                                     \
 398         ch = *it;                                                             \
 399         if (!radix_check::is_valid(ch))                                       \
 400         {                                                                     \
 401             break;                                                            \
 402         }                                                                     \
 403         if (!extractor::call(ch, count, val))                                 \
 404         {                                                                     \
 405             traits::assign_to(val, attr);                                     \
 406             return false;                                                     \
 407         }                                                                     \
 408         ++it;                                                                 \
 409         ++count;                                                              \
 410     /**/
 411
 412     template <typename T, unsigned Radix, typename Accumulator, bool Accumulate>
 413     struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate>
 414     {
 415 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 416 # pragma warning(push)
 417 # pragma warning(disable: 4127)   // conditional expression is constant
 418 #endif
 419         template <typename Iterator, typename Attribute>
 420         inline static bool
 421         parse_main(
 422             Iterator& first
 423           , Iterator const& last
 424           , Attribute& attr)
 425         {
 426             typedef radix_traits<Radix> radix_check;
 427             typedef int_extractor<Radix, Accumulator, -1, Accumulate> extractor;
 428             typedef typename
 429                 boost::detail::iterator_traits<Iterator>::value_type
 430             char_type;
 431
 432             Iterator it = first;
 433             std::size_t count = 0;
 434             if (!Accumulate)
 435             {
 436                 // skip leading zeros
 437                 while (it != last && *it == '0')
 438                 {
 439                     ++it;
 440                     ++count;
 441                 }
 442
 443                 if (it == last)
 444                 {
 445                     if (count == 0) // must have at least one digit
 446                         return false;
 447                     traits::assign_to(0, attr);
 448                     first = it;
 449                     return true;
 450                 }
 451             }
 452
 453             typedef typename
 454                 traits::attribute_type<Attribute>::type
 455             attribute_type;
 456
 457             attribute_type val = Accumulate ? attr : attribute_type(0);
 458             char_type ch = *it;
 459
 460             if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val))
 461             {
 462                 if (count == 0) // must have at least one digit
 463                     return false;
 464                 traits::assign_to(val, attr);
 465                 first = it;
 466                 return true;
 467             }
 468
 469             // count = 0; $$$ verify: I think this is wrong $$$
 470             ++it;
 471             while (true)
 472             {
 473                 BOOST_PP_REPEAT(
 474                     SPIRIT_NUMERICS_LOOP_UNROLL
 475                   , SPIRIT_NUMERIC_INNER_LOOP, _)
 476             }
 477
 478             traits::assign_to(val, attr);
 479             first = it;
 480             return true;
 481         }
 482 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
 483 # pragma warning(pop)
 484 #endif
 485
 486         template <typename Iterator>
 487         inline static bool
 488         parse(
 489             Iterator& first
 490           , Iterator const& last
 491           , unused_type)
 492         {
 493             T n = 0; // must calculate value to detect over/underflow
 494             return parse_main(first, last, n);
 495         }
 496
 497         template <typename Iterator, typename Attribute>
 498         inline static bool
 499         parse(
 500             Iterator& first
 501           , Iterator const& last
 502           , Attribute& attr)
 503         {
 504             return parse_main(first, last, attr);
 505         }
 506     };
 507
 508 #undef SPIRIT_NUMERIC_INNER_LOOP
 509
 510     ///////////////////////////////////////////////////////////////////////////
 511     // Cast an signed integer to an unsigned integer
 512     ///////////////////////////////////////////////////////////////////////////
 513     template <typename T,
 514         bool force_unsigned
 515             = mpl::and_<is_integral<T>, is_signed<T> >::value>
 516     struct cast_unsigned;
 517
 518     template <typename T>
 519     struct cast_unsigned<T, true>
 520     {
 521         typedef typename make_unsigned<T>::type unsigned_type;
 522         typedef typename make_unsigned<T>::type& unsigned_type_ref;
 523
 524         inline static unsigned_type_ref call(T& n)
 525         {
 526             return unsigned_type_ref(n);
 527         }
 528     };
 529
 530     template <typename T>
 531     struct cast_unsigned<T, false>
 532     {
 533         inline static T& call(T& n)
 534         {
 535             return n;
 536         }
 537     };
 538 }}}}
 539
 540 #if defined(BOOST_MSVC)
 541 # pragma warning(pop)
 542 #endif
 543
 544 #endif