robot/include/boost/spirit/home/qi/numeric/detail/numeric_utils.hpp

/*=============================================================================
    Copyright (c) 2001-2011 Joel de Guzman
    Copyright (c) 2001-2011 Hartmut Kaiser
    Copyright (c) 2011 Jan Frederick Eick
    Copyright (c) 2011 Christopher Jefferson
    Copyright (c) 2006 Stephen Nutt

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#ifndef BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP
#define BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/spirit/home/support/unused.hpp>
#include <boost/spirit/home/qi/detail/attributes.hpp>
#include <boost/spirit/home/support/char_encoding/ascii.hpp>
#include <boost/spirit/home/support/numeric_traits.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/iteration/local.hpp>
#include <boost/preprocessor/comparison/less.hpp>
#include <boost/preprocessor/control/if.hpp>
#include <boost/preprocessor/seq/elem.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_signed.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/and.hpp>
#include <boost/limits.hpp>
#include <boost/static_assert.hpp>
#include <iterator> // for std::iterator_traits

#if defined(BOOST_MSVC)
# pragma warning(push)
# pragma warning(disable: 4127) // conditional expression is constant
#endif

#if !defined(SPIRIT_NUMERICS_LOOP_UNROLL)
# define SPIRIT_NUMERICS_LOOP_UNROLL 3
#endif

namespace boost { namespace spirit { namespace qi { namespace detail
{
    ///////////////////////////////////////////////////////////////////////////
    //
    //  The maximum radix digits that can be represented without
    //  overflow:
    //
    //          template<typename T, unsigned Radix>
    //          struct digits_traits::value;
    //
    ///////////////////////////////////////////////////////////////////////////
    template <typename T, unsigned Radix>
    struct digits_traits;

    template <int Digits, unsigned Radix>
    struct digits2_to_n;

// lookup table for log2(x) : 2 <= x <= 36
#define BOOST_SPIRIT_LOG2 (#error)(#error)                                    \
        (1000000)(1584960)(2000000)(2321920)(2584960)(2807350)                \
        (3000000)(3169920)(3321920)(3459430)(3584960)(3700430)                \
        (3807350)(3906890)(4000000)(4087460)(4169920)(4247920)                \
        (4321920)(4392310)(4459430)(4523560)(4584960)(4643850)                \
        (4700430)(4754880)(4807350)(4857980)(4906890)(4954190)                \
        (5000000)(5044390)(5087460)(5129280)(5169925)                         \
    /***/

#define BOOST_PP_LOCAL_MACRO(Radix)                                           \
    template <int Digits> struct digits2_to_n<Digits, Radix>                  \
    {                                                                         \
        BOOST_STATIC_CONSTANT(int, value = static_cast<int>(                  \
            (Digits * 1000000) /                                              \
                BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_LOG2)));                \
    };                                                                        \
    /***/

#define BOOST_PP_LOCAL_LIMITS (2, 36)
#include BOOST_PP_LOCAL_ITERATE()

#undef BOOST_SPIRIT_LOG2

    template <typename T, unsigned Radix>
    struct digits_traits : digits2_to_n<std::numeric_limits<T>::digits, Radix>
    {
        BOOST_STATIC_ASSERT(std::numeric_limits<T>::radix == 2);
    };

    template <typename T>
    struct digits_traits<T, 10>
    {
        static int const value = std::numeric_limits<T>::digits10;
    };

    ///////////////////////////////////////////////////////////////////////////
    //
    //  Traits class for radix specific number conversion
    //
    //      Test the validity of a single character:
    //
    //          template<typename Char> static bool is_valid(Char ch);
    //
    //      Convert a digit from character representation to binary
    //      representation:
    //
    //          template<typename Char> static int digit(Char ch);
    //
    ///////////////////////////////////////////////////////////////////////////
    template <unsigned Radix>
    struct radix_traits
    {
        template <typename Char>
        inline static bool is_valid(Char ch)
        {
            return (ch >= '0' && ch <= (Radix > 10 ? '9' : static_cast<Char>('0' + Radix -1)))
                || (Radix > 10 && ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1))
                || (Radix > 10 && ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1));
        }

        template <typename Char>
        inline static unsigned digit(Char ch)
        {
            if (Radix <= 10 || (ch >= '0' && ch <= '9'))
                return ch - '0';
            return spirit::char_encoding::ascii::tolower(ch) - 'a' + 10;
        }
    };

    ///////////////////////////////////////////////////////////////////////////
    //  positive_accumulator/negative_accumulator: Accumulator policies for
    //  extracting integers. Use positive_accumulator if number is positive.
    //  Use negative_accumulator if number is negative.
    ///////////////////////////////////////////////////////////////////////////
    template <unsigned Radix>
    struct positive_accumulator
    {
        template <typename T, typename Char>
        inline static void add(T& n, Char ch, mpl::false_) // unchecked add
        {
            const int digit = radix_traits<Radix>::digit(ch);
            n = n * T(Radix) + T(digit);
        }

        template <typename T, typename Char>
        inline static bool add(T& n, Char ch, mpl::true_) // checked add
        {
            // Ensure n *= Radix will not overflow
            T const max = (std::numeric_limits<T>::max)();
            T const val = max / Radix;

            if (n > val)
                return false;

            T tmp = n * Radix;

            // Ensure n += digit will not overflow
            const int digit = radix_traits<Radix>::digit(ch);
            if (tmp > max - digit)
                return false;

            n = tmp + static_cast<T>(digit);
            return true;
        }
    };

    template <unsigned Radix>
    struct negative_accumulator
    {
        template <typename T, typename Char>
        inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract
        {
            const int digit = radix_traits<Radix>::digit(ch);
            n = n * T(Radix) - T(digit);
        }

        template <typename T, typename Char>
        inline static bool add(T& n, Char ch, mpl::true_) // checked subtract
        {
            // Ensure n *= Radix will not underflow
            T const min = (std::numeric_limits<T>::min)();
            T const val = min / T(Radix);

            if (n < val)
                return false;

            T tmp = n * Radix;

            // Ensure n -= digit will not underflow
            int const digit = radix_traits<Radix>::digit(ch);
            if (tmp < min + digit)
                return false;

            n = tmp - static_cast<T>(digit);
            return true;
        }
    };

    ///////////////////////////////////////////////////////////////////////////
    //  Common code for extract_int::parse specializations
    ///////////////////////////////////////////////////////////////////////////
    template <unsigned Radix, typename Accumulator, int MaxDigits, bool AlwaysCheckOverflow>
    struct int_extractor
    {
        template <typename Char, typename T>
        inline static bool
        call(Char ch, std::size_t count, T& n, mpl::true_)
        {
            std::size_t const overflow_free = digits_traits<T, Radix>::value - 1;

            if (!AlwaysCheckOverflow && (count < overflow_free))
            {
                Accumulator::add(n, ch, mpl::false_());
            }
            else
            {
                if (!Accumulator::add(n, ch, mpl::true_()))
                    return false; //  over/underflow!
            }
            return true;
        }

        template <typename Char, typename T>
        inline static bool
        call(Char ch, std::size_t /*count*/, T& n, mpl::false_)
        {
            // no need to check for overflow
            Accumulator::add(n, ch, mpl::false_());
            return true;
        }

        template <typename Char>
        inline static bool
        call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)
        {
            return true;
        }

        template <typename Char, typename T>
        inline static bool
        call(Char ch, std::size_t count, T& n)
        {
            return call(ch, count, n
              , mpl::bool_<
                    (   (MaxDigits < 0)
                    ||  (MaxDigits > digits_traits<T, Radix>::value)
                    )
                  && traits::check_overflow<T>::value
                >()
            );
        }
    };

    ///////////////////////////////////////////////////////////////////////////
    //  End of loop checking: check if the number of digits
    //  being parsed exceeds MaxDigits. Note: if MaxDigits == -1
    //  we don't do any checking.
    ///////////////////////////////////////////////////////////////////////////
    template <int MaxDigits>
    struct check_max_digits
    {
        inline static bool
        call(std::size_t count)
        {
            return count < MaxDigits; // bounded
        }
    };

    template <>
    struct check_max_digits<-1>
    {
        inline static bool
        call(std::size_t /*count*/)
        {
            return true; // unbounded
        }
    };

    ///////////////////////////////////////////////////////////////////////////
    //  extract_int: main code for extracting integers
    ///////////////////////////////////////////////////////////////////////////
#define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
        if (!check_max_digits<MaxDigits>::call(count + leading_zeros)         \
            || it == last)                                                    \
        {                                                                     \
            break;                                                            \
        }                                                                     \
        ch = *it;                                                             \
        if (!radix_check::is_valid(ch))                                       \
        {                                                                     \
            break;                                                            \
        }                                                                     \
        if (!extractor::call(ch, count, val))                                 \
        {                                                                     \
            if (IgnoreOverflowDigits)                                         \
            {                                                                 \
                first = it;                                                   \
            }                                                                 \
            traits::assign_to(val, attr);                                     \
            return IgnoreOverflowDigits;                                      \
        }                                                                     \
        ++it;                                                                 \
        ++count;                                                              \
    /**/

    template <
        typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
      , typename Accumulator = positive_accumulator<Radix>
      , bool Accumulate = false
      , bool IgnoreOverflowDigits = false
    >
    struct extract_int
    {
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
# pragma warning(push)
# pragma warning(disable: 4127)   // conditional expression is constant
#endif
        template <typename Iterator, typename Attribute>
        inline static bool
        parse_main(
            Iterator& first
          , Iterator const& last
          , Attribute& attr)
        {
            typedef radix_traits<Radix> radix_check;
            typedef int_extractor<Radix, Accumulator, MaxDigits, Accumulate> extractor;
            typedef typename std::iterator_traits<Iterator>::value_type char_type;

            Iterator it = first;
            std::size_t leading_zeros = 0;
            if (!Accumulate)
            {
                // skip leading zeros
                while (it != last && *it == '0' && (MaxDigits < 0 || leading_zeros < static_cast< std::size_t >(MaxDigits)))
                {
                    ++it;
                    ++leading_zeros;
                }
            }

            typedef typename
                traits::attribute_type<Attribute>::type
            attribute_type;

            attribute_type val = Accumulate ? attr : attribute_type(0);
            std::size_t count = 0;
            char_type ch;

            while (true)
            {
                BOOST_PP_REPEAT(
                    SPIRIT_NUMERICS_LOOP_UNROLL
                  , SPIRIT_NUMERIC_INNER_LOOP, _)
            }

            if (count + leading_zeros >= MinDigits)
            {
                traits::assign_to(val, attr);
                first = it;
                return true;
            }
            return false;
        }
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
# pragma warning(pop)
#endif

        template <typename Iterator>
        inline static bool
        parse(
            Iterator& first
          , Iterator const& last
          , unused_type)
        {
            T n = 0; // must calculate value to detect over/underflow
            return parse_main(first, last, n);
        }

        template <typename Iterator, typename Attribute>
        inline static bool
        parse(
            Iterator& first
          , Iterator const& last
          , Attribute& attr)
        {
            return parse_main(first, last, attr);
        }
    };
#undef SPIRIT_NUMERIC_INNER_LOOP

    ///////////////////////////////////////////////////////////////////////////
    //  extract_int: main code for extracting integers
    //  common case where MinDigits == 1 and MaxDigits = -1
    ///////////////////////////////////////////////////////////////////////////
#define SPIRIT_NUMERIC_INNER_LOOP(z, x, data)                                 \
        if (it == last)                                                       \
        {                                                                     \
            break;                                                            \
        }                                                                     \
        ch = *it;                                                             \
        if (!radix_check::is_valid(ch))                                       \
        {                                                                     \
            break;                                                            \
        }                                                                     \
        if (!extractor::call(ch, count, val))                                 \
        {                                                                     \
            traits::assign_to(val, attr);                                     \
            return false;                                                     \
        }                                                                     \
        ++it;                                                                 \
        ++count;                                                              \
    /**/

    template <typename T, unsigned Radix, typename Accumulator, bool Accumulate>
    struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate>
    {
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
# pragma warning(push)
# pragma warning(disable: 4127)   // conditional expression is constant
#endif
        template <typename Iterator, typename Attribute>
        inline static bool
        parse_main(
            Iterator& first
          , Iterator const& last
          , Attribute& attr)
        {
            typedef radix_traits<Radix> radix_check;
            typedef int_extractor<Radix, Accumulator, -1, Accumulate> extractor;
            typedef typename std::iterator_traits<Iterator>::value_type char_type;

            Iterator it = first;
            std::size_t count = 0;
            if (!Accumulate)
            {
                // skip leading zeros
                while (it != last && *it == '0')
                {
                    ++it;
                    ++count;
                }

                if (it == last)
                {
                    if (count == 0) // must have at least one digit
                        return false;
                    traits::assign_to(0, attr);
                    first = it;
                    return true;
                }
            }

            typedef typename
                traits::attribute_type<Attribute>::type
            attribute_type;

            attribute_type val = Accumulate ? attr : attribute_type(0);
            char_type ch = *it;

            if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val))
            {
                if (count == 0) // must have at least one digit
                    return false;
                traits::assign_to(val, attr);
                first = it;
                return true;
            }

            // count = 0; $$$ verify: I think this is wrong $$$
            ++it;
            while (true)
            {
                BOOST_PP_REPEAT(
                    SPIRIT_NUMERICS_LOOP_UNROLL
                  , SPIRIT_NUMERIC_INNER_LOOP, _)
            }

            traits::assign_to(val, attr);
            first = it;
            return true;
        }
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
# pragma warning(pop)
#endif

        template <typename Iterator>
        inline static bool
        parse(
            Iterator& first
          , Iterator const& last
          , unused_type)
        {
            T n = 0; // must calculate value to detect over/underflow
            return parse_main(first, last, n);
        }

        template <typename Iterator, typename Attribute>
        inline static bool
        parse(
            Iterator& first
          , Iterator const& last
          , Attribute& attr)
        {
            return parse_main(first, last, attr);
        }
    };

#undef SPIRIT_NUMERIC_INNER_LOOP
}}}}

#if defined(BOOST_MSVC)
# pragma warning(pop)
#endif

#endif