[boost] bug in spirit numerics parsing

From: Steve Nutt (steve.nutt_at_[hidden])
Date: 2006-11-13 15:39:47

I've encountered a bug in the spirit library's numeric parsing.  Deep in
boost::spirit::impl is a template extract_int_base which uses the two
templates positive_accumulate and negative_accumulate.

 

When a new digit is parsed, it is accumulated to the current value by
multiplying the current value by the radix and adding the new digit.
Overflow is detected at each stage by comparing the new and old values.

 

The overflow logic is flawed.  It assumes that when the number overflows
it becomes a smaller number, which is only true if the radix is a power
of 2.  It also requires that the arithmetic operation does
over/underflow.

 

My proposed fix detects overflow before it happens, fixing the parsing
of large base 10 numbers, and allowing for non overflowing numeric
types.  The changes are only to the three classes mentioned.

 

Steve Nutt

 

Changed file:

include/spirit/core/primitives/impl/numerics.ipp

 

template <int Radix>

struct positive_accumulate

{

//  Use this accumulator if number is positive

 

template <typename T, typename CharT>

static bool add(T& n, CharT ch)

{

// Ensure n *= Radix will not overflow

static const T val = std::numeric_limits<T>::max() / Radix;

if (n > val)

return false;

 

n *= Radix;

 

// Ensure n += digit will not overflow

const int digit = radix_traits<Radix>::digit(ch);

                        if (n > std::numeric_limits<T>::max() - digit)

                                    return false;

 

                        n += digit;

                        return true;

}

};

 

template <int Radix>

struct negative_accumulate

{

//  Use this accumulator if number is negative

 

            template <typename T>

            static T min()

            {

                        if (std::numeric_limits<T>::is_integer)

                                    return
std::numeric_limits<T>::min();

                                                

                        return -std::numeric_limits<T>::max();

            }

                                    

template <typename T, typename CharT>

static bool add(T& n, CharT ch)

            { 

                        // Ensure n *= Radix will not underflow

                        static const T val = min<T>() / Radix;

                        if (n < val)

                                    return false;

 

                        n *= Radix;

 

                        // Ensure n -= digit will not underflow

                        const int digit =
radix_traits<Radix>::digit(ch);

                        if (n < min<T>() + digit)

                                    return false;

 

                        n -= digit;

                        return true;

}

};

 

template <int Radix, typename Accumulate>

struct extract_int_base

{

//  Common code for extract_int specializations

            template <typename ScannerT, typename T>

            static bool

            f(ScannerT& scan, T& n)

            {

                return Accumulate::add(n, *scan);

            }

};