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/detail/iterator.hpp> 19 #include <boost/spirit/home/support/unused.hpp> 20 #include <boost/spirit/home/qi/detail/attributes.hpp> 21 #include <boost/spirit/home/support/char_encoding/ascii.hpp> 22 #include <boost/spirit/home/support/numeric_traits.hpp> 23 #include <boost/preprocessor/repetition/repeat.hpp> 24 #include <boost/preprocessor/iteration/local.hpp> 25 #include <boost/preprocessor/comparison/less.hpp> 26 #include <boost/preprocessor/control/if.hpp> 27 #include <boost/preprocessor/seq/elem.hpp> 28 #include <boost/utility/enable_if.hpp> 29 #include <boost/type_traits/is_integral.hpp> 30 #include <boost/type_traits/is_signed.hpp> 31 #include <boost/mpl/bool.hpp> 32 #include <boost/mpl/and.hpp> 33 #include <boost/limits.hpp> 34 #include <boost/integer_traits.hpp> 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 // lookup table for log2(x) : 2 <= x <= 36 60 #define BOOST_SPIRIT_LOG2 (#error)(#error) \ 61 (1000000)(1584960)(2000000)(2321920)(2584960)(2807350) \ 62 (3000000)(3169920)(3321920)(3459430)(3584960)(3700430) \ 63 (3807350)(3906890)(4000000)(4087460)(4169920)(4247920) \ 64 (4321920)(4392310)(4459430)(4523560)(4584960)(4643850) \ 65 (4700430)(4754880)(4807350)(4857980)(4906890)(4954190) \ 66 (5000000)(5044390)(5087460)(5129280)(5169925) \ 67 /***/ 68 69 #define BOOST_PP_LOCAL_MACRO(Radix) \ 70 template <typename T> struct digits_traits<T, Radix> \ 71 { \ 72 typedef std::numeric_limits<T> numeric_limits_type; \ 73 BOOST_STATIC_CONSTANT(int, value = static_cast<int>( \ 74 (numeric_limits_type::digits * 1000000) / \ 75 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_LOG2))); \ 76 }; \ 77 /***/ 78 79 #define BOOST_PP_LOCAL_LIMITS (2, 36) 80 #include BOOST_PP_LOCAL_ITERATE() 81 82 #undef BOOST_SPIRIT_LOG2 83 84 /////////////////////////////////////////////////////////////////////////// 85 // 86 // Traits class for radix specific number conversion 87 // 88 // Test the validity of a single character: 89 // 90 // template<typename Char> static bool is_valid(Char ch); 91 // 92 // Convert a digit from character representation to binary 93 // representation: 94 // 95 // template<typename Char> static int digit(Char ch); 96 // 97 /////////////////////////////////////////////////////////////////////////// 98 template <unsigned Radix> 99 struct radix_traits 100 { 101 template <typename Char> is_validboost::spirit::qi::detail::radix_traits102 inline static bool is_valid(Char ch) 103 { 104 if (Radix <= 10) 105 return (ch >= '0' && ch <= static_cast<Char>('0' + Radix -1)); 106 return (ch >= '0' && ch <= '9') 107 || (ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1)) 108 || (ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1)); 109 } 110 111 template <typename Char> digitboost::spirit::qi::detail::radix_traits112 inline static unsigned digit(Char ch) 113 { 114 if (Radix <= 10 || (ch >= '0' && ch <= '9')) 115 return ch - '0'; 116 return spirit::char_encoding::ascii::tolower(ch) - 'a' + 10; 117 } 118 }; 119 120 template <typename T, T Val> 121 struct constexpr_int 122 { 123 BOOST_STATIC_CONSTEXPR T value = Val; 124 }; 125 126 /////////////////////////////////////////////////////////////////////////// 127 // positive_accumulator/negative_accumulator: Accumulator policies for 128 // extracting integers. Use positive_accumulator if number is positive. 129 // Use negative_accumulator if number is negative. 130 /////////////////////////////////////////////////////////////////////////// 131 template <unsigned Radix> 132 struct positive_accumulator 133 { 134 template <typename T, typename Char> addboost::spirit::qi::detail::positive_accumulator135 inline static void add(T& n, Char ch, mpl::false_) // unchecked add 136 { 137 const int digit = radix_traits<Radix>::digit(ch); 138 n = n * T(Radix) + T(digit); 139 } 140 141 template <typename T, typename Char> addboost::spirit::qi::detail::positive_accumulator142 inline static bool add(T& n, Char ch, mpl::true_) // checked add 143 { 144 // Ensure n *= Radix will not overflow 145 typedef constexpr_int<T, boost::integer_traits<T>::const_max> max; 146 typedef constexpr_int<T, max::value / Radix> val; 147 148 if (n > val::value) 149 return false; 150 151 n *= Radix; 152 153 // Ensure n += digit will not overflow 154 const int digit = radix_traits<Radix>::digit(ch); 155 if (n > max::value - digit) 156 return false; 157 158 n += static_cast<T>(digit); 159 return true; 160 } 161 }; 162 163 template <unsigned Radix> 164 struct negative_accumulator 165 { 166 template <typename T, typename Char> addboost::spirit::qi::detail::negative_accumulator167 inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract 168 { 169 const int digit = radix_traits<Radix>::digit(ch); 170 n = n * T(Radix) - T(digit); 171 } 172 173 template <typename T, typename Char> addboost::spirit::qi::detail::negative_accumulator174 inline static bool add(T& n, Char ch, mpl::true_) // checked subtract 175 { 176 // Ensure n *= Radix will not underflow 177 typedef constexpr_int<T, boost::integer_traits<T>::const_min> min; 178 typedef constexpr_int<T, (min::value + 1) / T(Radix)> val; 179 180 if (n < val::value) 181 return false; 182 183 n *= Radix; 184 185 // Ensure n -= digit will not underflow 186 int const digit = radix_traits<Radix>::digit(ch); 187 if (n < min::value + digit) 188 return false; 189 190 n -= static_cast<T>(digit); 191 return true; 192 } 193 }; 194 195 /////////////////////////////////////////////////////////////////////////// 196 // Common code for extract_int::parse specializations 197 /////////////////////////////////////////////////////////////////////////// 198 template <unsigned Radix, typename Accumulator, int MaxDigits, bool AlwaysCheckOverflow> 199 struct int_extractor 200 { 201 template <typename Char, typename T> 202 inline static bool callboost::spirit::qi::detail::int_extractor203 call(Char ch, std::size_t count, T& n, mpl::true_) 204 { 205 typedef constexpr_int<std::size_t, digits_traits<T, Radix>::value - 1> overflow_free; 206 207 if (!AlwaysCheckOverflow && (count < overflow_free::value)) 208 { 209 Accumulator::add(n, ch, mpl::false_()); 210 } 211 else 212 { 213 if (!Accumulator::add(n, ch, mpl::true_())) 214 return false; // over/underflow! 215 } 216 return true; 217 } 218 219 template <typename Char, typename T> 220 inline static bool callboost::spirit::qi::detail::int_extractor221 call(Char ch, std::size_t /*count*/, T& n, mpl::false_) 222 { 223 // no need to check for overflow 224 Accumulator::add(n, ch, mpl::false_()); 225 return true; 226 } 227 228 template <typename Char> 229 inline static bool callboost::spirit::qi::detail::int_extractor230 call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_) 231 { 232 return true; 233 } 234 235 template <typename Char, typename T> 236 inline static bool callboost::spirit::qi::detail::int_extractor237 call(Char ch, std::size_t count, T& n) 238 { 239 return call(ch, count, n 240 , mpl::bool_< 241 ( (MaxDigits < 0) 242 || (MaxDigits > digits_traits<T, Radix>::value) 243 ) 244 && traits::check_overflow<T>::value 245 >() 246 ); 247 } 248 }; 249 250 /////////////////////////////////////////////////////////////////////////// 251 // End of loop checking: check if the number of digits 252 // being parsed exceeds MaxDigits. Note: if MaxDigits == -1 253 // we don't do any checking. 254 /////////////////////////////////////////////////////////////////////////// 255 template <int MaxDigits> 256 struct check_max_digits 257 { 258 inline static bool callboost::spirit::qi::detail::check_max_digits259 call(std::size_t count) 260 { 261 return count < MaxDigits; // bounded 262 } 263 }; 264 265 template <> 266 struct check_max_digits<-1> 267 { 268 inline static bool callboost::spirit::qi::detail::check_max_digits269 call(std::size_t /*count*/) 270 { 271 return true; // unbounded 272 } 273 }; 274 275 /////////////////////////////////////////////////////////////////////////// 276 // extract_int: main code for extracting integers 277 /////////////////////////////////////////////////////////////////////////// 278 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \ 279 if (!check_max_digits<MaxDigits>::call(count + leading_zeros) \ 280 || it == last) \ 281 { \ 282 break; \ 283 } \ 284 ch = *it; \ 285 if (!radix_check::is_valid(ch)) \ 286 { \ 287 break; \ 288 } \ 289 if (!extractor::call(ch, count, val)) \ 290 { \ 291 if (IgnoreOverflowDigits) \ 292 { \ 293 first = it; \ 294 } \ 295 traits::assign_to(val, attr); \ 296 return IgnoreOverflowDigits; \ 297 } \ 298 ++it; \ 299 ++count; \ 300 /**/ 301 302 template < 303 typename T, unsigned Radix, unsigned MinDigits, int MaxDigits 304 , typename Accumulator = positive_accumulator<Radix> 305 , bool Accumulate = false 306 , bool IgnoreOverflowDigits = false 307 > 308 struct extract_int 309 { 310 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 311 # pragma warning(push) 312 # pragma warning(disable: 4127) // conditional expression is constant 313 #endif 314 template <typename Iterator, typename Attribute> 315 inline static bool parse_mainboost::spirit::qi::detail::extract_int316 parse_main( 317 Iterator& first 318 , Iterator const& last 319 , Attribute& attr) 320 { 321 typedef radix_traits<Radix> radix_check; 322 typedef int_extractor<Radix, Accumulator, MaxDigits, Accumulate> extractor; 323 typedef typename 324 boost::detail::iterator_traits<Iterator>::value_type 325 char_type; 326 327 Iterator it = first; 328 std::size_t leading_zeros = 0; 329 if (!Accumulate) 330 { 331 // skip leading zeros 332 while (it != last && *it == '0' && (MaxDigits < 0 || leading_zeros < static_cast< std::size_t >(MaxDigits))) 333 { 334 ++it; 335 ++leading_zeros; 336 } 337 } 338 339 typedef typename 340 traits::attribute_type<Attribute>::type 341 attribute_type; 342 343 attribute_type val = Accumulate ? attr : attribute_type(0); 344 std::size_t count = 0; 345 char_type ch; 346 347 while (true) 348 { 349 BOOST_PP_REPEAT( 350 SPIRIT_NUMERICS_LOOP_UNROLL 351 , SPIRIT_NUMERIC_INNER_LOOP, _) 352 } 353 354 if (count + leading_zeros >= MinDigits) 355 { 356 traits::assign_to(val, attr); 357 first = it; 358 return true; 359 } 360 return false; 361 } 362 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 363 # pragma warning(pop) 364 #endif 365 366 template <typename Iterator> 367 inline static bool parseboost::spirit::qi::detail::extract_int368 parse( 369 Iterator& first 370 , Iterator const& last 371 , unused_type) 372 { 373 T n = 0; // must calculate value to detect over/underflow 374 return parse_main(first, last, n); 375 } 376 377 template <typename Iterator, typename Attribute> 378 inline static bool parseboost::spirit::qi::detail::extract_int379 parse( 380 Iterator& first 381 , Iterator const& last 382 , Attribute& attr) 383 { 384 return parse_main(first, last, attr); 385 } 386 }; 387 #undef SPIRIT_NUMERIC_INNER_LOOP 388 389 /////////////////////////////////////////////////////////////////////////// 390 // extract_int: main code for extracting integers 391 // common case where MinDigits == 1 and MaxDigits = -1 392 /////////////////////////////////////////////////////////////////////////// 393 #define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \ 394 if (it == last) \ 395 { \ 396 break; \ 397 } \ 398 ch = *it; \ 399 if (!radix_check::is_valid(ch)) \ 400 { \ 401 break; \ 402 } \ 403 if (!extractor::call(ch, count, val)) \ 404 { \ 405 traits::assign_to(val, attr); \ 406 return false; \ 407 } \ 408 ++it; \ 409 ++count; \ 410 /**/ 411 412 template <typename T, unsigned Radix, typename Accumulator, bool Accumulate> 413 struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate> 414 { 415 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 416 # pragma warning(push) 417 # pragma warning(disable: 4127) // conditional expression is constant 418 #endif 419 template <typename Iterator, typename Attribute> 420 inline static bool parse_mainboost::spirit::qi::detail::extract_int421 parse_main( 422 Iterator& first 423 , Iterator const& last 424 , Attribute& attr) 425 { 426 typedef radix_traits<Radix> radix_check; 427 typedef int_extractor<Radix, Accumulator, -1, Accumulate> extractor; 428 typedef typename 429 boost::detail::iterator_traits<Iterator>::value_type 430 char_type; 431 432 Iterator it = first; 433 std::size_t count = 0; 434 if (!Accumulate) 435 { 436 // skip leading zeros 437 while (it != last && *it == '0') 438 { 439 ++it; 440 ++count; 441 } 442 443 if (it == last) 444 { 445 if (count == 0) // must have at least one digit 446 return false; 447 traits::assign_to(0, attr); 448 first = it; 449 return true; 450 } 451 } 452 453 typedef typename 454 traits::attribute_type<Attribute>::type 455 attribute_type; 456 457 attribute_type val = Accumulate ? attr : attribute_type(0); 458 char_type ch = *it; 459 460 if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val)) 461 { 462 if (count == 0) // must have at least one digit 463 return false; 464 traits::assign_to(val, attr); 465 first = it; 466 return true; 467 } 468 469 // count = 0; $$$ verify: I think this is wrong $$$ 470 ++it; 471 while (true) 472 { 473 BOOST_PP_REPEAT( 474 SPIRIT_NUMERICS_LOOP_UNROLL 475 , SPIRIT_NUMERIC_INNER_LOOP, _) 476 } 477 478 traits::assign_to(val, attr); 479 first = it; 480 return true; 481 } 482 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) 483 # pragma warning(pop) 484 #endif 485 486 template <typename Iterator> 487 inline static bool parseboost::spirit::qi::detail::extract_int488 parse( 489 Iterator& first 490 , Iterator const& last 491 , unused_type) 492 { 493 T n = 0; // must calculate value to detect over/underflow 494 return parse_main(first, last, n); 495 } 496 497 template <typename Iterator, typename Attribute> 498 inline static bool parseboost::spirit::qi::detail::extract_int499 parse( 500 Iterator& first 501 , Iterator const& last 502 , Attribute& attr) 503 { 504 return parse_main(first, last, attr); 505 } 506 }; 507 508 #undef SPIRIT_NUMERIC_INNER_LOOP 509 510 /////////////////////////////////////////////////////////////////////////// 511 // Cast an signed integer to an unsigned integer 512 /////////////////////////////////////////////////////////////////////////// 513 template <typename T, 514 bool force_unsigned 515 = mpl::and_<is_integral<T>, is_signed<T> >::value> 516 struct cast_unsigned; 517 518 template <typename T> 519 struct cast_unsigned<T, true> 520 { 521 typedef typename make_unsigned<T>::type unsigned_type; 522 typedef typename make_unsigned<T>::type& unsigned_type_ref; 523 callboost::spirit::qi::detail::cast_unsigned524 inline static unsigned_type_ref call(T& n) 525 { 526 return unsigned_type_ref(n); 527 } 528 }; 529 530 template <typename T> 531 struct cast_unsigned<T, false> 532 { callboost::spirit::qi::detail::cast_unsigned533 inline static T& call(T& n) 534 { 535 return n; 536 } 537 }; 538 }}}} 539 540 #if defined(BOOST_MSVC) 541 # pragma warning(pop) 542 #endif 543 544 #endif 545