1/*=============================================================================
2 Copyright (c) 2001-2014 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(BOOST_SPIRIT_X3_DETAIL_EXTRACT_INT_APRIL_17_2006_0816AM)
12#define BOOST_SPIRIT_X3_DETAIL_EXTRACT_INT_APRIL_17_2006_0816AM
13
14#include <boost/spirit/home/x3/support/unused.hpp>
15#include <boost/spirit/home/x3/support/traits/attribute_type.hpp>
16#include <boost/spirit/home/x3/support/traits/move_to.hpp>
17#include <boost/spirit/home/x3/support/traits/numeric_traits.hpp>
18#include <boost/spirit/home/support/char_encoding/ascii.hpp>
19
20#include <boost/preprocessor/repetition/repeat.hpp>
21#include <boost/preprocessor/iteration/local.hpp>
22#include <boost/preprocessor/comparison/less.hpp>
23#include <boost/preprocessor/control/if.hpp>
24#include <boost/preprocessor/seq/elem.hpp>
25
26#include <boost/utility/enable_if.hpp>
27
28#include <boost/type_traits/is_integral.hpp>
29#include <boost/type_traits/is_signed.hpp>
30#include <boost/type_traits/make_unsigned.hpp>
31
32#include <boost/mpl/bool.hpp>
33#include <boost/mpl/and.hpp>
34#include <boost/limits.hpp>
35
36#include <iterator> // for std::iterator_traits
37
38#if !defined(SPIRIT_NUMERICS_LOOP_UNROLL)
39# define SPIRIT_NUMERICS_LOOP_UNROLL 3
40#endif
41
42namespace boost { namespace spirit { namespace x3 { namespace detail
43{
44 ///////////////////////////////////////////////////////////////////////////
45 //
46 // The maximum radix digits that can be represented without
47 // overflow:
48 //
49 // template<typename T, unsigned Radix>
50 // struct digits_traits::value;
51 //
52 ///////////////////////////////////////////////////////////////////////////
53 template <typename T, unsigned Radix>
54 struct digits_traits;
55
56 template <int Digits, unsigned Radix>
57 struct digits2_to_n;
58
59// lookup table for log2(x) : 2 <= x <= 36
60#define BOOST_SPIRIT_X3_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 <int Digits> struct digits2_to_n<Digits, Radix> \
71 { \
72 BOOST_STATIC_CONSTANT(int, value = static_cast<int>( \
73 (Digits * 1000000) / \
74 BOOST_PP_SEQ_ELEM(Radix, BOOST_SPIRIT_X3_LOG2))); \
75 }; \
76 /***/
77
78#define BOOST_PP_LOCAL_LIMITS (2, 36)
79#include BOOST_PP_LOCAL_ITERATE()
80
81#undef BOOST_SPIRIT_X3_LOG2
82
83 template <typename T, unsigned Radix>
84 struct digits_traits : digits2_to_n<std::numeric_limits<T>::digits, Radix>
85 {
86 static_assert(std::numeric_limits<T>::radix == 2, "");
87 };
88
89 template <typename T>
90 struct digits_traits<T, 10>
91 {
92 static int constexpr value = std::numeric_limits<T>::digits10;
93 };
94
95 ///////////////////////////////////////////////////////////////////////////
96 //
97 // Traits class for radix specific number conversion
98 //
99 // Test the validity of a single character:
100 //
101 // template<typename Char> static bool is_valid(Char ch);
102 //
103 // Convert a digit from character representation to binary
104 // representation:
105 //
106 // template<typename Char> static int digit(Char ch);
107 //
108 ///////////////////////////////////////////////////////////////////////////
109 template <unsigned Radix>
110 struct radix_traits
111 {
112 template <typename Char>
113 inline static bool is_valid(Char ch)
114 {
115 return (ch >= '0' && ch <= (Radix > 10 ? '9' : static_cast<Char>('0' + Radix -1)))
116 || (Radix > 10 && ch >= 'a' && ch <= static_cast<Char>('a' + Radix -10 -1))
117 || (Radix > 10 && ch >= 'A' && ch <= static_cast<Char>('A' + Radix -10 -1));
118 }
119
120 template <typename Char>
121 inline static unsigned digit(Char ch)
122 {
123 return (Radix <= 10 || (ch >= '0' && ch <= '9'))
124 ? ch - '0'
125 : char_encoding::ascii::tolower(ch) - 'a' + 10;
126 }
127 };
128
129 ///////////////////////////////////////////////////////////////////////////
130 // positive_accumulator/negative_accumulator: Accumulator policies for
131 // extracting integers. Use positive_accumulator if number is positive.
132 // Use negative_accumulator if number is negative.
133 ///////////////////////////////////////////////////////////////////////////
134 template <unsigned Radix>
135 struct positive_accumulator
136 {
137 template <typename T, typename Char>
138 inline static void add(T& n, Char ch, mpl::false_) // unchecked add
139 {
140 const int digit = radix_traits<Radix>::digit(ch);
141 n = n * T(Radix) + T(digit);
142 }
143
144 template <typename T, typename Char>
145 inline static bool add(T& n, Char ch, mpl::true_) // checked add
146 {
147 // Ensure n *= Radix will not overflow
148 T const max = (std::numeric_limits<T>::max)();
149 T const val = max / Radix;
150 if (n > val)
151 return false;
152
153 T tmp = n * Radix;
154
155 // Ensure n += digit will not overflow
156 const int digit = radix_traits<Radix>::digit(ch);
157 if (tmp > max - digit)
158 return false;
159
160 n = tmp + static_cast<T>(digit);
161 return true;
162 }
163 };
164
165 template <unsigned Radix>
166 struct negative_accumulator
167 {
168 template <typename T, typename Char>
169 inline static void add(T& n, Char ch, mpl::false_) // unchecked subtract
170 {
171 const int digit = radix_traits<Radix>::digit(ch);
172 n = n * T(Radix) - T(digit);
173 }
174
175 template <typename T, typename Char>
176 inline static bool add(T& n, Char ch, mpl::true_) // checked subtract
177 {
178 // Ensure n *= Radix will not underflow
179 T const min = (std::numeric_limits<T>::min)();
180 T const val = min / T(Radix);
181 if (n < val)
182 return false;
183
184 T tmp = n * Radix;
185
186 // Ensure n -= digit will not underflow
187 int const digit = radix_traits<Radix>::digit(ch);
188 if (tmp < min + digit)
189 return false;
190
191 n = tmp - static_cast<T>(digit);
192 return true;
193 }
194 };
195
196 ///////////////////////////////////////////////////////////////////////////
197 // Common code for extract_int::parse specializations
198 ///////////////////////////////////////////////////////////////////////////
199 template <unsigned Radix, typename Accumulator, int MaxDigits>
200 struct int_extractor
201 {
202 template <typename Char, typename T>
203 inline static bool
204 call(Char ch, std::size_t count, T& n, mpl::true_)
205 {
206 std::size_t constexpr
207 overflow_free = digits_traits<T, Radix>::value - 1;
208
209 if (count < overflow_free)
210 {
211 Accumulator::add(n, ch, mpl::false_());
212 }
213 else
214 {
215 if (!Accumulator::add(n, ch, mpl::true_()))
216 return false; // over/underflow!
217 }
218 return true;
219 }
220
221 template <typename Char, typename T>
222 inline static bool
223 call(Char ch, std::size_t /*count*/, T& n, mpl::false_)
224 {
225 // no need to check for overflow
226 Accumulator::add(n, ch, mpl::false_());
227 return true;
228 }
229
230 template <typename Char>
231 inline static bool
232 call(Char /*ch*/, std::size_t /*count*/, unused_type, mpl::false_)
233 {
234 return true;
235 }
236
237 template <typename Char, typename T>
238 inline static bool
239 call(Char ch, std::size_t count, T& n)
240 {
241 return call(ch, count, n
242 , mpl::bool_<
243 ( (MaxDigits < 0)
244 || (MaxDigits > digits_traits<T, Radix>::value)
245 )
246 && traits::check_overflow<T>::value
247 >()
248 );
249 }
250 };
251
252 ///////////////////////////////////////////////////////////////////////////
253 // End of loop checking: check if the number of digits
254 // being parsed exceeds MaxDigits. Note: if MaxDigits == -1
255 // we don't do any checking.
256 ///////////////////////////////////////////////////////////////////////////
257 template <int MaxDigits>
258 struct check_max_digits
259 {
260 inline static bool
261 call(std::size_t count)
262 {
263 return count < MaxDigits; // bounded
264 }
265 };
266
267 template <>
268 struct check_max_digits<-1>
269 {
270 inline static bool
271 call(std::size_t /*count*/)
272 {
273 return true; // unbounded
274 }
275 };
276
277 ///////////////////////////////////////////////////////////////////////////
278 // extract_int: main code for extracting integers
279 ///////////////////////////////////////////////////////////////////////////
280#define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \
281 if (!check_max_digits<MaxDigits>::call(count + leading_zeros) \
282 || it == last) \
283 break; \
284 ch = *it; \
285 if (!radix_check::is_valid(ch) || !extractor::call(ch, count, val)) \
286 break; \
287 ++it; \
288 ++count; \
289 /**/
290
291 template <
292 typename T, unsigned Radix, unsigned MinDigits, int MaxDigits
293 , typename Accumulator = positive_accumulator<Radix>
294 , bool Accumulate = false
295 >
296 struct extract_int
297 {
298#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
299# pragma warning(push)
300# pragma warning(disable: 4127) // conditional expression is constant
301# pragma warning(disable: 4459) // declaration hides global declaration
302#endif
303 template <typename Iterator, typename Attribute>
304 inline static bool
305 parse_main(
306 Iterator& first
307 , Iterator const& last
308 , Attribute& attr)
309 {
310 typedef radix_traits<Radix> radix_check;
311 typedef int_extractor<Radix, Accumulator, MaxDigits> extractor;
312 typedef typename
313 std::iterator_traits<Iterator>::value_type
314 char_type;
315
316 Iterator it = first;
317 std::size_t leading_zeros = 0;
318 if (!Accumulate)
319 {
320 // skip leading zeros
321 while (it != last && *it == '0' && leading_zeros < MaxDigits)
322 {
323 ++it;
324 ++leading_zeros;
325 }
326 }
327
328 typedef typename
329 traits::attribute_type<Attribute>::type
330 attribute_type;
331
332 attribute_type val = Accumulate ? attr : attribute_type(0);
333 std::size_t count = 0;
334 char_type ch;
335
336 while (true)
337 {
338 BOOST_PP_REPEAT(
339 SPIRIT_NUMERICS_LOOP_UNROLL
340 , SPIRIT_NUMERIC_INNER_LOOP, _)
341 }
342
343 if (count + leading_zeros >= MinDigits)
344 {
345 traits::move_to(val, attr);
346 first = it;
347 return true;
348 }
349 return false;
350 }
351#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
352# pragma warning(pop)
353#endif
354
355 template <typename Iterator>
356 inline static bool
357 parse(
358 Iterator& first
359 , Iterator const& last
360 , unused_type)
361 {
362 T n = 0; // must calculate value to detect over/underflow
363 return parse_main(first, last, n);
364 }
365
366 template <typename Iterator, typename Attribute>
367 inline static bool
368 parse(
369 Iterator& first
370 , Iterator const& last
371 , Attribute& attr)
372 {
373 return parse_main(first, last, attr);
374 }
375 };
376#undef SPIRIT_NUMERIC_INNER_LOOP
377
378 ///////////////////////////////////////////////////////////////////////////
379 // extract_int: main code for extracting integers
380 // common case where MinDigits == 1 and MaxDigits = -1
381 ///////////////////////////////////////////////////////////////////////////
382#define SPIRIT_NUMERIC_INNER_LOOP(z, x, data) \
383 if (it == last) \
384 break; \
385 ch = *it; \
386 if (!radix_check::is_valid(ch)) \
387 break; \
388 if (!extractor::call(ch, count, val)) \
389 return false; \
390 ++it; \
391 ++count; \
392 /**/
393
394 template <typename T, unsigned Radix, typename Accumulator, bool Accumulate>
395 struct extract_int<T, Radix, 1, -1, Accumulator, Accumulate>
396 {
397#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
398# pragma warning(push)
399# pragma warning(disable: 4127) // conditional expression is constant
400# pragma warning(disable: 4459) // declaration hides global declaration
401#endif
402 template <typename Iterator, typename Attribute>
403 inline static bool
404 parse_main(
405 Iterator& first
406 , Iterator const& last
407 , Attribute& attr)
408 {
409 typedef radix_traits<Radix> radix_check;
410 typedef int_extractor<Radix, Accumulator, -1> extractor;
411 typedef typename
412 std::iterator_traits<Iterator>::value_type
413 char_type;
414
415 Iterator it = first;
416 std::size_t count = 0;
417 if (!Accumulate)
418 {
419 // skip leading zeros
420 while (it != last && *it == '0')
421 {
422 ++it;
423 ++count;
424 }
425
426 if (it == last)
427 {
428 if (count == 0) // must have at least one digit
429 return false;
430 attr = 0;
431 first = it;
432 return true;
433 }
434 }
435
436 typedef typename
437 traits::attribute_type<Attribute>::type
438 attribute_type;
439
440 attribute_type val = Accumulate ? attr : attribute_type(0);
441 char_type ch = *it;
442
443 if (!radix_check::is_valid(ch) || !extractor::call(ch, 0, val))
444 {
445 if (count == 0) // must have at least one digit
446 return false;
447 traits::move_to(val, attr);
448 first = it;
449 return true;
450 }
451
452 count = 0;
453 ++it;
454 while (true)
455 {
456 BOOST_PP_REPEAT(
457 SPIRIT_NUMERICS_LOOP_UNROLL
458 , SPIRIT_NUMERIC_INNER_LOOP, _)
459 }
460
461 traits::move_to(val, attr);
462 first = it;
463 return true;
464 }
465#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
466# pragma warning(pop)
467#endif
468
469 template <typename Iterator>
470 inline static bool
471 parse(
472 Iterator& first
473 , Iterator const& last
474 , unused_type)
475 {
476 T n = 0; // must calculate value to detect over/underflow
477 return parse_main(first, last, n);
478 }
479
480 template <typename Iterator, typename Attribute>
481 inline static bool
482 parse(
483 Iterator& first
484 , Iterator const& last
485 , Attribute& attr)
486 {
487 return parse_main(first, last, attr);
488 }
489 };
490
491#undef SPIRIT_NUMERIC_INNER_LOOP
492}}}}
493
494#endif
495

source code of boost/libs/spirit/include/boost/spirit/home/x3/support/numeric_utils/detail/extract_int.hpp