numeric_utils.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

/*=============================================================================
    Copyright (c) 2001-2007 Joel de Guzman
    Copyright (c) 2001-2008 Hartmut Kaiser
    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)
=============================================================================*/
#if !defined(SPIRIT_NUMERIC_UTILS_APR_17_2006_0816AM)
#define SPIRIT_NUMERIC_UTILS_APR_17_2006_0816AM

#include <boost/detail/iterator.hpp>
#include <boost/spirit/home/support/unused.hpp>
#include <boost/spirit/home/support/char_class/ascii.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/mpl/bool.hpp>

#include <limits>
#include <boost/limits.hpp>

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

namespace boost { namespace spirit { namespace qi { namespace detail
{
    ///////////////////////////////////////////////////////////////////////////
    //
    //  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);
    //
    //      The maximum radix digits that can be represented without
    //      overflow:
    //
    //          template<typename T> struct digits::value;
    //
    ///////////////////////////////////////////////////////////////////////////
    template <unsigned Radix>
    struct radix_traits;

    // Binary
    template <>
    struct radix_traits<2>
    {
        template<typename Char>
        static bool is_valid(Char ch)
        {
            return ('0' == ch || '1' == ch);
        }

        template<typename Char>
        static unsigned digit(Char ch)
        {
            return ch - '0';
        }

        template<typename T>
        struct digits
        {
            typedef std::numeric_limits<T> numeric_limits_;
            BOOST_STATIC_CONSTANT(int, value = numeric_limits_::digits);
        };
    };

    // Octal
    template <>
    struct radix_traits<8>
    {
        template<typename Char>
        static bool is_valid(Char ch)
        {
            return ch >= '0' && ch <= '7';
        }

        template<typename Char>
        static unsigned digit(Char ch)
        {
            return ch - '0';
        }

        template<typename T>
        struct digits
        {
            typedef std::numeric_limits<T> numeric_limits_;
            BOOST_STATIC_CONSTANT(int, value = numeric_limits_::digits / 3);
        };
    };

    // Decimal
    template <>
    struct radix_traits<10>
    {
        template<typename Char>
        static bool is_valid(Char ch)
        {
            return ch >= '0' && ch <= '9';
        }

        template<typename Char>
        static unsigned digit(Char ch)
        {
            return ch - '0';
        }

        template<typename T>
        struct digits
        {
            typedef std::numeric_limits<T> numeric_limits_;
            BOOST_STATIC_CONSTANT(int, value = numeric_limits_::digits10);
        };
    };

    // Hexadecimal
    template <>
    struct radix_traits<16>
    {
        template<typename Char>
        static bool is_valid(Char ch)
        {
            return (ch >= '0' && ch <= '9')
            || (ch >= 'a' && ch <= 'f')
            || (ch >= 'A' && ch <= 'F');
        }

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

        template<typename T>
        struct digits
        {
            typedef std::numeric_limits<T> numeric_limits_;
            BOOST_STATIC_CONSTANT(int, value = numeric_limits_::digits / 4);
        };
    };

    ///////////////////////////////////////////////////////////////////////////
    //  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>
        static void add(T& n, Char ch, mpl::false_) // unchecked add
        {
            const int digit = radix_traits<Radix>::digit(ch);
            n = n * Radix + digit;
        }

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

            n *= Radix;

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

            n += digit;
            return true;
        }
    };

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

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

            n *= Radix;

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

            n -= digit;
            return true;
        }
    };

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

            if (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>
        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>
        static bool
        call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)