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#ifndef BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP
12#define BOOST_SPIRIT_QI_NUMERIC_DETAIL_NUMERIC_UTILS_HPP
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
45namespace 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>
116 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>
124 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>
141 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>
148 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>
173 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>
180 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
209 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
227 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
236 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
243 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
265 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
275 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
322 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
372 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
383 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
425 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
490 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
501 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

source code of boost/libs/spirit/include/boost/spirit/home/qi/numeric/detail/numeric_utils.hpp