boost/spirit/home/qi/numeric/detail/numeric_utils.hpp
/*=============================================================================
Copyright (c) 2001-2009 Joel de Guzman
Copyright (c) 2001-2009 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_APRIL_17_2006_0816AM)
#define SPIRIT_NUMERIC_UTILS_APRIL_17_2006_0816AM
#if defined(_MSC_VER)
#pragma once
#endif
#include <boost/detail/iterator.hpp>
#include <boost/spirit/home/support/unused.hpp>
#include <boost/spirit/home/support/attributes.hpp>
#include <boost/spirit/home/support/char_encoding/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_encoding::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 * T(Radix) + T(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 += static_cast<T>(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 * T(Radix) - T(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 -= static_cast<T>(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_)
{
return true;
}
template <typename Char, typename T>
static bool
call(Char ch, std::size_t count, T& n)
{
return call(ch, count, n
, mpl::bool_<
( (MaxDigits < 0)
|| (MaxDigits > radix_traits<Radix>::template digits<T>::value)
)
&& std::numeric_limits<T>::is_modulo
>()
);
}
};
///////////////////////////////////////////////////////////////////////////
// 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
{
static bool
call(std::size_t count)
{
return count < MaxDigits; // bounded
}
};
template <>
struct check_max_digits<-1>
{
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) || !extractor::call(ch, count, val)) \
break; \
++it; \
++count; \
/**/
template <
typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
, typename Accumulator = positive_accumulator<Radix>
, bool Accumulate = 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>
static bool
parse_main(
Iterator& first
, Iterator const& last
, Attribute& attr)
{
typedef radix_traits<Radix> radix_check;
typedef int_extractor<Radix, Accumulator, MaxDigits> extractor;
typedef typename
boost::detail::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' && leading_zeros < MaxDigits)
{
++it;
++leading_zeros;
}
}
Attribute val = Accumulate ? attr : Attribute(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>
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>
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) || !extractor::call(ch, count, val)) \
break; \
++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>
static bool
parse_main(
Iterator& first
, Iterator const& last
, Attribute& attr)
{
typedef radix_traits<Radix> radix_check;
typedef int_extractor<Radix, Accumulator, -1> extractor;
typedef typename
boost::detail::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;
}
}
Attribute val = Accumulate ? attr : Attribute(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;
++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>
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>
static bool
parse(
Iterator& first
, Iterator const& last
, Attribute& attr)
{
return parse_main(first, last, attr);
}
};
#undef SPIRIT_NUMERIC_INNER_LOOP
}}}}
#endif
