1 /*============================================================================= 2 Copyright (c) 2001-2011 Joel de Guzman 3 Copyright (c) 2001-2011 Hartmut Kaiser 4 Copyright (c) 2011 Jan Frederick Eick 5 Copyright (c) 2011 Christopher Jefferson 6 Copyright (c) 2006 Stephen Nutt 7 8 Distributed under the Boost Software License, Version 1.0. (See accompanying 9 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 10 =============================================================================*/ 11 #if !defined(SPIRIT_NUMERIC_UTILS_APRIL_17_2006_0816AM) 12 #define SPIRIT_NUMERIC_UTILS_APRIL_17_2006_0816AM 13 14 #if defined(_MSC_VER) 15 #pragma once 16 #endif 17 18 #include <boost/spirit/home/support/unused.hpp> 19 #include <boost/spirit/home/qi/detail/attributes.hpp> 20 #include <boost/spirit/home/support/char_encoding/ascii.hpp> 21 #include <boost/spirit/home/support/numeric_traits.hpp> 22 #include <boost/preprocessor/repetition/repeat.hpp> 23 #include <boost/preprocessor/iteration/local.hpp> 24 #include <boost/preprocessor/comparison/less.hpp> 25 #include <boost/preprocessor/control/if.hpp> 26 #include <boost/preprocessor/seq/elem.hpp> 27 #include <boost/utility/enable_if.hpp> 28 #include <boost/type_traits/is_integral.hpp> 29 #include <boost/type_traits/is_signed.hpp> 30 #include <boost/mpl/bool.hpp> 31 #include <boost/mpl/and.hpp> 32 #include <boost/limits.hpp> 33 #include <boost/static_assert.hpp> 34 #include <iterator> // for std::iterator_traits 35 36 #if defined(BOOST_MSVC) 37 # pragma warning(push) 38 # pragma warning(disable: 4127) // conditional expression is constant 39 #endif 40 41 #if !defined(SPIRIT_NUMERICS_LOOP_UNROLL) 42 # define SPIRIT_NUMERICS_LOOP_UNROLL 3 43 #endif 44 45 namespace boost { namespace spirit { namespace qi { namespace detail 46 { 47 /////////////////////////////////////////////////////////////////////////// 48 // 49 // The maximum radix digits that can be represented without 50 // overflow: 51 // 52 // template<typename T, unsigned Radix> 53 // struct digits_traits::value; 54 // 55 /////////////////////////////////////////////////////////////////////////// 56 template <typename T, unsigned Radix> 57 struct digits_traits; 58 59 template <int Digits, unsigned Radix> 60 struct digits2_to_n; 61 62 // lookup table for log2(x) : 2 <= x <= 36 63 #define BOOST_SPIRIT_LOG2 (#error)(#error) \ 64 (1000000)(1584960)(2000000)(2321920)(2584960)(2807350) \ 65 (3000000)(3169920)(3321920)(3459430)(3584960)(3700430) \ 66 (3807350)(3906890)(4000000)(4087460)(4169920)(4247920) \ 67 (4321920)(4392310)(4459430)(4523560)(4584960)(4643850) \ 68 (4700430)(4754880)(4807350)(4857980)(4906890)(4954190) \ 69 (5000000)(5044390)(5087460)(5129280)(5169925) \ 70 /***/ 71 72 #define BOOST_PP_LOCAL_MACRO(Radix) \ 73 template <int Digits> struct digits2_to_n<Digits, Radix> \ 74 { \ 75 BOOST_STATIC_CONSTANT(int, value = static_cast<int>( \ 76 (Digits * 1000000) / \ 77 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_LOG2))); \ 78 }; \ 79 /***/ 80 81 #define BOOST_PP_LOCAL_LIMITS (2, 36) 82 #include BOOST_PP_LOCAL_ITERATE() 83 84 #undef BOOST_SPIRIT_LOG2 85 86 template <typename T, unsigned Radix> 87 struct digits_traits : digits2_to_n<std::numeric_limits<T>::digits, Radix> 88 { 89 BOOST_STATIC_ASSERT(std::numeric_limits<T>::radix == 2); 90 }; 91 92 template <typename T> 93 struct digits_traits<T, 10> 94 { 95 static int const value = std::numeric_limits<T>::digits10; 96 }; 97 98 /////////////////////////////////////////////////////////////////////////// 99 // 100 // Traits class for radix specific number conversion 101 // 102 // Test the validity of a single character: 103 // 104 // template<typename Char> static bool is_valid(Char ch); 105 // 106 // Convert a digit from character representation to binary 107 // representation: 108 // 109 // template<typename Char> static int digit(Char ch); 110 // 111 /////////////////////////////////////////////////////////////////////////// 112 template <unsigned Radix> 113 struct radix_traits 114 { 115 template <typename Char> is_validboost::spirit::qi::detail::radix_traits116 inline static bool is_valid(Char ch) 117 { 118 return (ch >= '0' && ch <= (Radix > 10 ? '9' : static_cast<Char>('0' + Radix -1))) 119 || (Radix > 10 && ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1)) 120 || (Radix > 10 && ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1)); 121 } 122 123 template <typename Char> digitboost::spirit::qi::detail::radix_traits124 inline static unsigned digit(Char ch) 125 { 126 if (Radix <= 10 || (ch >= '0' && ch <= '9')) 127 return ch - '0'; 128 return spirit::char_encoding::ascii::tolower(ch) - 'a' + 10; 129 } 130 }; 131 132 /////////////////////////////////////////////////////////////////////////// 133 // positive_accumulator/negative_accumulator: Accumulator policies for 134 // extracting integers. Use positive_accumulator if number is positive. 135 // Use negative_accumulator if number is negative. 136 /////////////////////////////////////////////////////////////////////////// 137 template <unsigned Radix> 138 struct positive_accumulator 139 { 140 template <typename T, typename Char> addboost::spirit::qi::detail::positive_accumulator141 inline static void add(T& n, Char ch, mpl::false_) // unchecked add 142 { 143 const int digit = radix_traits<Radix>::digit(ch); 144 n = n * T(Radix) + T(digit); 145 } 146 147 template <typename T, typename Char> addboost::spirit::qi::detail::positive_accumulator148 inline static bool add(T& n, Char ch, mpl::true_) // checked add 149 { 150 // Ensure n *= Radix will not overflow 151 T const max = (std::numeric_limits<T>::max)(); 152 T const val = max / Radix; 153 154 if (n > val) 155 return false; 156 157 T tmp = n * Radix; 158 159 // Ensure n += digit will not overflow 160 const int digit = radix_traits<Radix>::digit(ch); 161 if (tmp > max - digit) 162 return false; 163 164 n = tmp + static_cast<T>(digit); 165 return true; 166 } 167 }; 168 169 template <unsigned Radix> 170 struct negative_accumulator 171 { 172 template <typename T, typename Char> addboost::spirit::qi::detail::negative_accumulator173 inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract 174 { 175 const int digit = radix_traits<Radix>::digit(ch); 176 n = n * T(Radix) - T(digit); 177 } 178 179 template <typename T, typename Char> addboost::spirit::qi::detail::negative_accumulator180 inline static bool add(T& n, Char ch, mpl::true_) // checked subtract 181 { 182 // Ensure n *= Radix will not underflow 183 T const min = (std::numeric_limits<T>::min)(); 184 T const val = min / T(Radix); 185 186 if (n < val) 187 return false; 188 189 T tmp = n * Radix; 190 191 // Ensure n -= digit will not underflow 192 int const digit = radix_traits<Radix>::digit(ch); 193 if (tmp < min + digit) 194 return false; 195 196 n = tmp - static_cast<T>(digit); 197 return true; 198 } 199 }; 200 201 /////////////////////////////////////////////////////////////////////////// 202 // Common code for extract_int::parse specializations 203 /////////////////////////////////////////////////////////////////////////// 204 template <unsigned Radix, typename Accumulator, int MaxDigits, bool AlwaysCheckOverflow> 205 struct int_extractor 206 { 207 template <typename Char, typename T> 208 inline static bool callboost::spirit::qi::detail::int_extractor209 call(Char ch, std::size_t count, T& n, mpl::true_) 210 { 211 std::size_t const overflow_free = digits_traits<T, Radix>::value - 1; 212 213 if (!AlwaysCheckOverflow && (count < overflow_free)) 214 { 215 Accumulator::add(n, ch, mpl::false_()); 216 } 217 else 218 { 219 if (!Accumulator::add(n, ch, mpl::true_())) 220 return false; // over/underflow! 221 } 222 return true; 223 } 224 225 template <typename Char, typename T> 226 inline static bool callboost::spirit::qi::detail::int_extractor227 call(Char ch, std::size_t /*count*/, T& n, mpl::false_) 228 { 229 // no need to check for overflow 230 Accumulator::add(n, ch, mpl::false_()); 231 return true; 232 } 233 234 template <typename Char> 235 inline static bool callboost::spirit::qi::detail::int_extractor236 call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_) 237 { 238 return true; 239 } 240 241 template <typename Char, typename T> 242 inline static bool callboost::spirit::qi::detail::int_extractor243 call(Char ch, std::size_t count, T& n) 244 { 245 return call(ch, count, n 246 , mpl::bool_< 247 ( (MaxDigits < 0) 248 || (MaxDigits > digits_traits<T, Radix>::value) 249 ) 250 && traits::check_overflow<T>::value 251 >() 252 ); 253 } 254 }; 255 256 /////////////////////////////////////////////////////////////////////////// 257 // End of loop checking: check if the number of digits 258 // being parsed exceeds MaxDigits. Note: if MaxDigits == -1 259 // we don't do any checking. 260 /////////////////////////////////////////////////////////////////////////// 261 template <int MaxDigits> 262 struct check_max_digits 263 { 264 inline static bool callboost::spirit::qi::detail::check_max_digits265 call(std::size_t count) 266 { 267 return count < MaxDigits; // bounded 268 } 269 }; 270 271 template <> 272 struct check_max_digits<-1> 273 { 274 inline static bool callboost::spirit::qi::detail::check_max_digits275 call(std::size_t /*count*/) 276 { 277 return true; // unbounded 278 } 279 }; 280 281 /////////////////////////////////////////////////////////////////////////// 282 // extract_int: main code for extracting integers 283 /////////////////////////////////////////////////////////////////////////// 284 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \ 285 if (!check_max_digits<MaxDigits>::call(count + leading_zeros) \ 286 || it == last) \ 287 { \ 288 break; \ 289 } \ 290 ch = *it; \ 291 if (!radix_check::is_valid(ch)) \ 292 { \ 293 break; \ 294 } \ 295 if (!extractor::call(ch, count, val)) \ 296 { \ 297 if (IgnoreOverflowDigits) \ 298 { \ 299 first = it; \ 300 } \ 301 traits::assign_to(val, attr); \ 302 return IgnoreOverflowDigits; \ 303 } \ 304 ++it; \ 305 ++count; \ 306 /**/ 307 308 template < 309 typename T, unsigned Radix, unsigned MinDigits, int MaxDigits 310 , typename Accumulator = positive_accumulator<Radix> 311 , bool Accumulate = false 312 , bool IgnoreOverflowDigits = false 313 > 314 struct extract_int 315 { 316 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 317 # pragma warning(push) 318 # pragma warning(disable: 4127) // conditional expression is constant 319 #endif 320 template <typename Iterator, typename Attribute> 321 inline static bool parse_mainboost::spirit::qi::detail::extract_int322 parse_main( 323 Iterator& first 324 , Iterator const& last 325 , Attribute& attr) 326 { 327 typedef radix_traits<Radix> radix_check; 328 typedef int_extractor<Radix, Accumulator, MaxDigits, Accumulate> extractor; 329 typedef typename std::iterator_traits<Iterator>::value_type char_type; 330 331 Iterator it = first; 332 std::size_t leading_zeros = 0; 333 if (!Accumulate) 334 { 335 // skip leading zeros 336 while (it != last && *it == '0' && (MaxDigits < 0 || leading_zeros < static_cast< std::size_t >(MaxDigits))) 337 { 338 ++it; 339 ++leading_zeros; 340 } 341 } 342 343 typedef typename 344 traits::attribute_type<Attribute>::type 345 attribute_type; 346 347 attribute_type val = Accumulate ? attr : attribute_type(0); 348 std::size_t count = 0; 349 char_type ch; 350 351 while (true) 352 { 353 BOOST_PP_REPEAT( 354 SPIRIT_NUMERICS_LOOP_UNROLL 355 , SPIRIT_NUMERIC_INNER_LOOP, _) 356 } 357 358 if (count + leading_zeros >= MinDigits) 359 { 360 traits::assign_to(val, attr); 361 first = it; 362 return true; 363 } 364 return false; 365 } 366 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 367 # pragma warning(pop) 368 #endif 369 370 template <typename Iterator> 371 inline static bool parseboost::spirit::qi::detail::extract_int372 parse( 373 Iterator& first 374 , Iterator const& last 375 , unused_type) 376 { 377 T n = 0; // must calculate value to detect over/underflow 378 return parse_main(first, last, n); 379 } 380 381 template <typename Iterator, typename Attribute> 382 inline static bool parseboost::spirit::qi::detail::extract_int383 parse( 384 Iterator& first 385 , Iterator const& last 386 , Attribute& attr) 387 { 388 return parse_main(first, last, attr); 389 } 390 }; 391 #undef SPIRIT_NUMERIC_INNER_LOOP 392 393 /////////////////////////////////////////////////////////////////////////// 394 // extract_int: main code for extracting integers 395 // common case where MinDigits == 1 and MaxDigits = -1 396 /////////////////////////////////////////////////////////////////////////// 397 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \ 398 if (it == last) \ 399 { \ 400 break; \ 401 } \ 402 ch = *it; \ 403 if (!radix_check::is_valid(ch)) \ 404 { \ 405 break; \ 406 } \ 407 if (!extractor::call(ch, count, val)) \ 408 { \ 409 traits::assign_to(val, attr); \ 410 return false; \ 411 } \ 412 ++it; \ 413 ++count; \ 414 /**/ 415 416 template <typename T, unsigned Radix, typename Accumulator, bool Accumulate> 417 struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate> 418 { 419 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 420 # pragma warning(push) 421 # pragma warning(disable: 4127) // conditional expression is constant 422 #endif 423 template <typename Iterator, typename Attribute> 424 inline static bool parse_mainboost::spirit::qi::detail::extract_int425 parse_main( 426 Iterator& first 427 , Iterator const& last 428 , Attribute& attr) 429 { 430 typedef radix_traits<Radix> radix_check; 431 typedef int_extractor<Radix, Accumulator, -1, Accumulate> extractor; 432 typedef typename std::iterator_traits<Iterator>::value_type char_type; 433 434 Iterator it = first; 435 std::size_t count = 0; 436 if (!Accumulate) 437 { 438 // skip leading zeros 439 while (it != last && *it == '0') 440 { 441 ++it; 442 ++count; 443 } 444 445 if (it == last) 446 { 447 if (count == 0) // must have at least one digit 448 return false; 449 traits::assign_to(0, attr); 450 first = it; 451 return true; 452 } 453 } 454 455 typedef typename 456 traits::attribute_type<Attribute>::type 457 attribute_type; 458 459 attribute_type val = Accumulate ? attr : attribute_type(0); 460 char_type ch = *it; 461 462 if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val)) 463 { 464 if (count == 0) // must have at least one digit 465 return false; 466 traits::assign_to(val, attr); 467 first = it; 468 return true; 469 } 470 471 // count = 0; $$$ verify: I think this is wrong $$$ 472 ++it; 473 while (true) 474 { 475 BOOST_PP_REPEAT( 476 SPIRIT_NUMERICS_LOOP_UNROLL 477 , SPIRIT_NUMERIC_INNER_LOOP, _) 478 } 479 480 traits::assign_to(val, attr); 481 first = it; 482 return true; 483 } 484 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 485 # pragma warning(pop) 486 #endif 487 488 template <typename Iterator> 489 inline static bool parseboost::spirit::qi::detail::extract_int490 parse( 491 Iterator& first 492 , Iterator const& last 493 , unused_type) 494 { 495 T n = 0; // must calculate value to detect over/underflow 496 return parse_main(first, last, n); 497 } 498 499 template <typename Iterator, typename Attribute> 500 inline static bool parseboost::spirit::qi::detail::extract_int501 parse( 502 Iterator& first 503 , Iterator const& last 504 , Attribute& attr) 505 { 506 return parse_main(first, last, attr); 507 } 508 }; 509 510 #undef SPIRIT_NUMERIC_INNER_LOOP 511 }}}} 512 513 #if defined(BOOST_MSVC) 514 # pragma warning(pop) 515 #endif 516 517 #endif 518