numeric/detail/numeric_utils.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003     Copyright (c) 2001-2011 Hartmut Kaiser
0004     Copyright (c) 2011 Jan Frederick Eick
0005     Copyright (c) 2011 Christopher Jefferson
0006     Copyright (c) 2006 Stephen Nutt
0007
0008     Distributed under the Boost Software License, Version 1.0. (See accompanying
0009     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0010 =============================================================================*/
0011 #ifndef BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP
0012 #define BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP
0013
0014 #if defined(_MSC_VER)
0015 #pragma once
0016 #endif
0017
0018 #include <boost/spirit/home/support/unused.hpp>
0019 #include <boost/spirit/home/qi/detail/attributes.hpp>
0020 #include <boost/spirit/home/support/char_encoding/ascii.hpp>
0021 #include <boost/spirit/home/support/numeric_traits.hpp>
0022 #include <boost/preprocessor/repetition/repeat.hpp>
0023 #include <boost/preprocessor/iteration/local.hpp>
0024 #include <boost/preprocessor/comparison/less.hpp>
0025 #include <boost/preprocessor/control/if.hpp>
0026 #include <boost/preprocessor/seq/elem.hpp>
0027 #include <boost/utility/enable_if.hpp>
0028 #include <boost/type_traits/is_integral.hpp>
0029 #include <boost/type_traits/is_signed.hpp>
0030 #include <boost/mpl/bool.hpp>
0031 #include <boost/mpl/and.hpp>
0032 #include <boost/limits.hpp>
0033 #include <boost/static_assert.hpp>
0034 #include <iterator> // for std::iterator_traits
0035
0036 #if defined(BOOST_MSVC)
0037 # pragma warning(push)
0038 # pragma warning(disable: 4127) // conditional expression is constant
0039 #endif
0040
0041 #if !defined(SPIRIT_NUMERICS_LOOP_UNROLL)
0042 # define SPIRIT_NUMERICS_LOOP_UNROLL 3
0043 #endif
0044
0045 namespace boost { namespace spirit { namespace qi { namespace detail
0046 {
0047     ///////////////////////////////////////////////////////////////////////////
0048     //
0049     //  The maximum radix digits that can be represented without
0050     //  overflow:
0051     //
0052     //          template<typename T, unsigned Radix>
0053     //          struct digits_traits::value;
0054     //
0055     ///////////////////////////////////////////////////////////////////////////
0056     template <typename T, unsigned Radix>
0057     struct digits_traits;
0058
0059     template <int Digits, unsigned Radix>
0060     struct digits2_to_n;
0061
0062 // lookup table for log2(x) : 2 <= x <= 36
0063 #define BOOST_SPIRIT_LOG2 (#error)(#error)                                    \
0064         (1000000)(1584960)(2000000)(2321920)(2584960)(2807350)                \
0065         (3000000)(3169920)(3321920)(3459430)(3584960)(3700430)                \
0066         (3807350)(3906890)(4000000)(4087460)(4169920)(4247920)                \
0067         (4321920)(4392310)(4459430)(4523560)(4584960)(4643850)                \
0068         (4700430)(4754880)(4807350)(4857980)(4906890)(4954190)                \
0069         (5000000)(5044390)(5087460)(5129280)(5169925)                         \
0070     /***/
0071
0072 #define BOOST_PP_LOCAL_MACRO(Radix)                                           \
0073     template <int Digits> struct digits2_to_n<Digits, Radix>                  \
0074     {                                                                         \
0075         BOOST_STATIC_CONSTANT(int, value = static_cast<int>(                  \
0076             (Digits * 1000000) /                                              \
0077                 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_LOG2)));                \
0078     };                                                                        \
0079     /***/
0080
0081 #define BOOST_PP_LOCAL_LIMITS (2, 36)
0082 #include BOOST_PP_LOCAL_ITERATE()
0083
0084 #undef BOOST_SPIRIT_LOG2
0085
0086     template <typename T, unsigned Radix>
0087     struct digits_traits : digits2_to_n<std::numeric_limits<T>::digits, Radix>
0088     {
0089         BOOST_STATIC_ASSERT(std::numeric_limits<T>::radix == 2);
0090     };
0091
0092     template <typename T>
0093     struct digits_traits<T, 10>
0094     {
0095         static int const value = std::numeric_limits<T>::digits10;
0096     };
0097
0098     ///////////////////////////////////////////////////////////////////////////
0099     //
0100     //  Traits class for radix specific number conversion
0101     //
0102     //      Test the validity of a single character:
0103     //
0104     //          template<typename Char> static bool is_valid(Char ch);
0105     //
0106     //      Convert a digit from character representation to binary
0107     //      representation:
0108     //
0109     //          template<typename Char> static int digit(Char ch);
0110     //
0111     ///////////////////////////////////////////////////////////////////////////
0112     template <unsigned Radix>
0113     struct radix_traits
0114     {
0115         template <typename Char>
0116         inline static bool is_valid(Char ch)
0117         {
0118             return (ch >= '0' && ch <= (Radix > 10 ? '9' : static_cast<Char>('0' + Radix -1)))
0119                 || (Radix > 10 && ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1))
0120                 || (Radix > 10 && ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1));
0121         }
0122
0123         template <typename Char>
0124         inline static unsigned digit(Char ch)
0125         {
0126             if (Radix <= 10 || (ch >= '0' && ch <= '9'))
0127                 return ch - '0';
0128             return spirit::char_encoding::ascii::tolower(ch) - 'a' + 10;
0129         }
0130     };
0131
0132     ///////////////////////////////////////////////////////////////////////////
0133     //  positive_accumulator/negative_accumulator: Accumulator policies for
0134     //  extracting integers. Use positive_accumulator if number is positive.
0135     //  Use negative_accumulator if number is negative.
0136     ///////////////////////////////////////////////////////////////////////////
0137     template <unsigned Radix>
0138     struct positive_accumulator
0139     {
0140         template <typename T, typename Char>
0141         inline static void add(T& n, Char ch, mpl::false_) // unchecked add
0142         {
0143             const int digit = radix_traits<Radix>::digit(ch);
0144             n = n * T(Radix) + T(digit);
0145         }
0146
0147         template <typename T, typename Char>
0148         inline static bool add(T& n, Char ch, mpl::true_) // checked add
0149         {
0150             // Ensure n *= Radix will not overflow
0151             T const max = (std::numeric_limits<T>::max)();
0152             T const val = max / Radix;
0153
0154             if (n > val)
0155                 return false;
0156
0157             T tmp = n * Radix;
0158
0159             // Ensure n += digit will not overflow
0160             const int digit = radix_traits<Radix>::digit(ch);
0161             if (tmp > max - digit)
0162                 return false;
0163
0164             n = tmp + static_cast<T>(digit);
0165             return true;
0166         }
0167     };
0168
0169     template <unsigned Radix>
0170     struct negative_accumulator
0171     {
0172         template <typename T, typename Char>
0173         inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract
0174         {
0175             const int digit = radix_traits<Radix>::digit(ch);
0176             n = n * T(Radix) - T(digit);
0177         }
0178
0179         template <typename T, typename Char>
0180         inline static bool add(T& n, Char ch, mpl::true_) // checked subtract
0181         {
0182             // Ensure n *= Radix will not underflow
0183             T const min = (std::numeric_limits<T>::min)();
0184             T const val = min / T(Radix);
0185
0186             if (n < val)
0187                 return false;
0188
0189             T tmp = n * Radix;
0190
0191             // Ensure n -= digit will not underflow
0192             int const digit = radix_traits<Radix>::digit(ch);
0193             if (tmp < min + digit)
0194                 return false;
0195
0196             n = tmp - static_cast<T>(digit);
0197             return true;
0198         }
0199     };
0200
0201     ///////////////////////////////////////////////////////////////////////////
0202     //  Common code for extract_int::parse specializations
0203     ///////////////////////////////////////////////////////////////////////////
0204     template <unsigned Radix, typename Accumulator, int MaxDigits, bool AlwaysCheckOverflow>
0205     struct int_extractor
0206     {
0207         template <typename Char, typename T>
0208         inline static bool
0209         call(Char ch, std::size_t count, T& n, mpl::true_)
0210         {
0211             std::size_t const overflow_free = digits_traits<T, Radix>::value - 1;
0212
0213             if (!AlwaysCheckOverflow && (count < overflow_free))
0214             {
0215                 Accumulator::add(n, ch, mpl::false_());
0216             }
0217             else
0218             {
0219                 if (!Accumulator::add(n, ch, mpl::true_()))
0220                     return false; //  over/underflow!
0221             }
0222             return true;
0223         }
0224
0225         template <typename Char, typename T>
0226         inline static bool
0227         call(Char ch, std::size_t /*count*/, T& n, mpl::false_)
0228         {
0229             // no need to check for overflow
0230             Accumulator::add(n, ch, mpl::false_());
0231             return true;
0232         }
0233
0234         template <typename Char>
0235         inline static bool
0236         call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)
0237         {
0238             return true;
0239         }
0240
0241         template <typename Char, typename T>
0242         inline static bool
0243         call(Char ch, std::size_t count, T& n)
0244         {
0245             return call(ch, count, n
0246               , mpl::bool_<
0247                     (   (MaxDigits < 0)
0248                     ||  (MaxDigits > digits_traits<T, Radix>::value)
0249                     )
0250                   && traits::check_overflow<T>::value
0251                 >()
0252             );
0253         }
0254     };
0255
0256     ///////////////////////////////////////////////////////////////////////////
0257     //  End of loop checking: check if the number of digits
0258     //  being parsed exceeds MaxDigits. Note: if MaxDigits == -1
0259     //  we don't do any checking.
0260     ///////////////////////////////////////////////////////////////////////////
0261     template <int MaxDigits>
0262     struct check_max_digits
0263     {
0264         inline static bool
0265         call(std::size_t count)
0266         {
0267             return count < MaxDigits; // bounded
0268         }
0269     };
0270
0271     template <>
0272     struct check_max_digits<-1>
0273     {
0274         inline static bool
0275         call(std::size_t /*count*/)
0276         {
0277             return true; // unbounded
0278         }
0279     };
0280
0281     ///////////////////////////////////////////////////////////////////////////
0282     //  extract_int: main code for extracting integers
0283     ///////////////////////////////////////////////////////////////////////////
0284 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
0285         if (!check_max_digits<MaxDigits>::call(count + leading_zeros)         \
0286             || it == last)                                                    \
0287         {                                                                     \
0288             break;                                                            \
0289         }                                                                     \
0290         ch = *it;                                                             \
0291         if (!radix_check::is_valid(ch))                                       \
0292         {                                                                     \
0293             break;                                                            \
0294         }                                                                     \
0295         if (!extractor::call(ch, count, val))                                 \
0296         {                                                                     \
0297             if (IgnoreOverflowDigits)                                         \
0298             {                                                                 \
0299                 first = it;                                                   \
0300             }                                                                 \
0301             traits::assign_to(val, attr);                                     \
0302             return IgnoreOverflowDigits;                                      \
0303         }                                                                     \
0304         ++it;                                                                 \
0305         ++count;                                                              \
0306     /**/
0307
0308     template <
0309         typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
0310       , typename Accumulator = positive_accumulator<Radix>
0311       , bool Accumulate = false
0312       , bool IgnoreOverflowDigits = false
0313     >
0314     struct extract_int
0315     {
0316 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
0317 # pragma warning(push)
0318 # pragma warning(disable: 4127)   // conditional expression is constant
0319 #endif
0320         template <typename Iterator, typename Attribute>
0321         inline static bool
0322         parse_main(
0323             Iterator& first
0324           , Iterator const& last
0325           , Attribute& attr)
0326         {
0327             typedef radix_traits<Radix> radix_check;
0328             typedef int_extractor<Radix, Accumulator, MaxDigits, Accumulate> extractor;
0329             typedef typename std::iterator_traits<Iterator>::value_type char_type;
0330
0331             Iterator it = first;
0332             std::size_t leading_zeros = 0;
0333             if (!Accumulate)
0334             {
0335                 // skip leading zeros
0336                 while (it != last && *it == '0' && (MaxDigits < 0 || leading_zeros < static_cast< std::size_t >(MaxDigits)))
0337                 {
0338                     ++it;
0339                     ++leading_zeros;
0340                 }
0341             }
0342
0343             typedef typename
0344                 traits::attribute_type<Attribute>::type
0345             attribute_type;
0346
0347             attribute_type val = Accumulate ? attr : attribute_type(0);
0348             std::size_t count = 0;
0349             char_type ch;
0350
0351             while (true)
0352             {
0353                 BOOST_PP_REPEAT(
0354                     SPIRIT_NUMERICS_LOOP_UNROLL
0355                   , SPIRIT_NUMERIC_INNER_LOOP, _)
0356             }
0357
0358             if (count + leading_zeros >= MinDigits)
0359             {
0360                 traits::assign_to(val, attr);
0361                 first = it;
0362                 return true;
0363             }
0364             return false;
0365         }
0366 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
0367 # pragma warning(pop)
0368 #endif
0369
0370         template <typename Iterator>
0371         inline static bool
0372         parse(
0373             Iterator& first
0374           , Iterator const& last
0375           , unused_type)
0376         {
0377             T n = 0; // must calculate value to detect over/underflow
0378             return parse_main(first, last, n);
0379         }
0380
0381         template <typename Iterator, typename Attribute>
0382         inline static bool
0383         parse(
0384             Iterator& first
0385           , Iterator const& last
0386           , Attribute& attr)
0387         {
0388             return parse_main(first, last, attr);
0389         }
0390     };
0391 #undef SPIRIT_NUMERIC_INNER_LOOP
0392
0393     ///////////////////////////////////////////////////////////////////////////
0394     //  extract_int: main code for extracting integers
0395     //  common case where MinDigits == 1 and MaxDigits = -1
0396     ///////////////////////////////////////////////////////////////////////////
0397 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
0398         if (it == last)                                                       \
0399         {                                                                     \
0400             break;                                                            \
0401         }                                                                     \
0402         ch = *it;                                                             \
0403         if (!radix_check::is_valid(ch))                                       \
0404         {                                                                     \
0405             break;                                                            \
0406         }                                                                     \
0407         if (!extractor::call(ch, count, val))                                 \
0408         {                                                                     \
0409             traits::assign_to(val, attr);                                     \
0410             return false;                                                     \
0411         }                                                                     \
0412         ++it;                                                                 \
0413         ++count;                                                              \
0414     /**/
0415
0416     template <typename T, unsigned Radix, typename Accumulator, bool Accumulate>
0417     struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate>
0418     {
0419 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
0420 # pragma warning(push)
0421 # pragma warning(disable: 4127)   // conditional expression is constant
0422 #endif
0423         template <typename Iterator, typename Attribute>
0424         inline static bool
0425         parse_main(
0426             Iterator& first
0427           , Iterator const& last
0428           , Attribute& attr)
0429         {
0430             typedef radix_traits<Radix> radix_check;
0431             typedef int_extractor<Radix, Accumulator, -1, Accumulate> extractor;
0432             typedef typename std::iterator_traits<Iterator>::value_type char_type;
0433
0434             Iterator it = first;
0435             std::size_t count = 0;
0436             if (!Accumulate)
0437             {
0438                 // skip leading zeros
0439                 while (it != last && *it == '0')
0440                 {
0441                     ++it;
0442                     ++count;
0443                 }
0444
0445                 if (it == last)
0446                 {
0447                     if (count == 0) // must have at least one digit
0448                         return false;
0449                     traits::assign_to(0, attr);
0450                     first = it;
0451                     return true;
0452                 }
0453             }
0454
0455             typedef typename
0456                 traits::attribute_type<Attribute>::type
0457             attribute_type;
0458
0459             attribute_type val = Accumulate ? attr : attribute_type(0);
0460             char_type ch = *it;
0461
0462             if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val))
0463             {
0464                 if (count == 0) // must have at least one digit
0465                     return false;
0466                 traits::assign_to(val, attr);
0467                 first = it;
0468                 return true;
0469             }
0470
0471             // count = 0; $$$ verify: I think this is wrong $$$
0472             ++it;
0473             while (true)
0474             {
0475                 BOOST_PP_REPEAT(
0476                     SPIRIT_NUMERICS_LOOP_UNROLL
0477                   , SPIRIT_NUMERIC_INNER_LOOP, _)
0478             }
0479
0480             traits::assign_to(val, attr);
0481             first = it;
0482             return true;
0483         }
0484 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
0485 # pragma warning(pop)
0486 #endif
0487
0488         template <typename Iterator>
0489         inline static bool
0490         parse(
0491             Iterator& first
0492           , Iterator const& last
0493           , unused_type)
0494         {
0495             T n = 0; // must calculate value to detect over/underflow
0496             return parse_main(first, last, n);
0497         }
0498
0499         template <typename Iterator, typename Attribute>
0500         inline static bool
0501         parse(
0502             Iterator& first
0503           , Iterator const& last
0504           , Attribute& attr)
0505         {
0506             return parse_main(first, last, attr);
0507         }
0508     };
0509
0510 #undef SPIRIT_NUMERIC_INNER_LOOP
0511 }}}}
0512
0513 #if defined(BOOST_MSVC)
0514 # pragma warning(pop)
0515 #endif
0516
0517 #endif