1#ifndef BOOST_NUMERIC_CHECKED_INTEGER_HPP
2#define BOOST_NUMERIC_CHECKED_INTEGER_HPP
3
4// Copyright (c) 2012 Robert Ramey
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9
10// contains operations for doing checked aritmetic on NATIVE
11// C++ types.
12
13#include <limits>
14#include <type_traits> // is_integral, make_unsigned, enable_if
15#include <algorithm> // std::max
16
17#include "checked_result.hpp"
18#include "checked_default.hpp"
19#include "safe_compare.hpp"
20#include "utility.hpp"
21#include "exception.hpp"
22
23namespace boost {
24namespace safe_numerics {
25
26// utility
27
28template<bool tf>
29using bool_type = typename std::conditional<tf, std::true_type, std::false_type>::type;
30
31////////////////////////////////////////////////////
32// layer 0 - implement safe operations for intrinsic integers
33// Note presumption of twos complement integer arithmetic
34
35// convert an integral value to some other integral type
36template<
37 typename R,
38 R Min,
39 R Max,
40 typename T,
41 class F
42>
43struct heterogeneous_checked_operation<
44 R,
45 Min,
46 Max,
47 T,
48 F,
49 typename std::enable_if<
50 std::is_integral<R>::value
51 && std::is_integral<T>::value
52 >::type
53>{
54 ////////////////////////////////////////////////////
55 // safe casting on primitive types
56
57 struct cast_impl_detail {
58 constexpr static checked_result<R>
59 cast_impl(
60 const T & t,
61 std::true_type, // R is signed
62 std::true_type // T is signed
63 ){
64 // INT32-C Ensure that operations on signed
65 // integers do not overflow
66 return
67 boost::safe_numerics::safe_compare::greater_than(t, Max) ?
68 F::template invoke<safe_numerics_error::positive_overflow_error>(
69 "converted signed value too large"
70 )
71 : boost::safe_numerics::safe_compare::less_than(t, Min) ?
72 F::template invoke<safe_numerics_error::negative_overflow_error>(
73 "converted signed value too small"
74 )
75 :
76 checked_result<R>(static_cast<R>(t))
77 ;
78 }
79 constexpr static checked_result<R>
80 cast_impl(
81 const T & t,
82 std::true_type, // R is signed
83 std::false_type // T is unsigned
84 ){
85 // INT30-C Ensure that unsigned integer operations
86 // do not wrap
87 return
88 boost::safe_numerics::safe_compare::greater_than(t, Max) ?
89 F::template invoke<safe_numerics_error::positive_overflow_error>(
90 "converted unsigned value too large"
91 )
92 :
93 boost::safe_numerics::safe_compare::less_than(t, Min) ?
94 F::template invoke<safe_numerics_error::positive_overflow_error>(
95 "converted unsigned value too small"
96 )
97 :
98 checked_result<R>(static_cast<R>(t))
99 ;
100 }
101 constexpr static checked_result<R>
102 cast_impl(
103 const T & t,
104 std::false_type, // R is unsigned
105 std::false_type // T is unsigned
106 ){
107 // INT32-C Ensure that operations on unsigned
108 // integers do not overflow
109 return
110 boost::safe_numerics::safe_compare::greater_than(t, Max) ?
111 F::template invoke<safe_numerics_error::positive_overflow_error>(
112 "converted unsigned value too large"
113 )
114 :
115 boost::safe_numerics::safe_compare::less_than(t, Min) ?
116 F::template invoke<safe_numerics_error::positive_overflow_error>(
117 "converted unsigned value too small"
118 )
119 :
120 checked_result<R>(static_cast<R>(t))
121 ;
122 }
123 constexpr static checked_result<R>
124 cast_impl(
125 const T & t,
126 std::false_type, // R is unsigned
127 std::true_type // T is signed
128 ){
129 return
130 boost::safe_numerics::safe_compare::less_than(t, Min) ?
131 F::template invoke<safe_numerics_error::domain_error>(
132 "converted value to low or negative"
133 )
134 :
135 boost::safe_numerics::safe_compare::greater_than(t, Max) ?
136 F::template invoke<safe_numerics_error::positive_overflow_error>(
137 "converted signed value too large"
138 )
139 :
140 checked_result<R>(static_cast<R>(t))
141 ;
142 }
143 }; // cast_impl_detail
144
145 constexpr static checked_result<R>
146 cast(const T & t){
147 return
148 cast_impl_detail::cast_impl(
149 t,
150 std::is_signed<R>(),
151 std::is_signed<T>()
152 );
153 }
154}; // heterogeneous_checked_operation
155
156// converting floating point value to integral type
157template<
158 typename R,
159 R Min,
160 R Max,
161 typename T,
162 class F
163>
164struct heterogeneous_checked_operation<
165 R,
166 Min,
167 Max,
168 T,
169 F,
170 typename std::enable_if<
171 std::is_integral<R>::value
172 && std::is_floating_point<T>::value
173 >::type
174>{
175 constexpr static checked_result<R>
176 cast(const T & t){
177 return static_cast<R>(t);
178 }
179}; // heterogeneous_checked_operation
180
181// converting integral value to floating point type
182
183// INT35-C. Use correct integer precisions
184template<
185 typename R,
186 R Min,
187 R Max,
188 typename T,
189 class F
190>
191struct heterogeneous_checked_operation<
192 R,
193 Min,
194 Max,
195 T,
196 F,
197 typename std::enable_if<
198 std::is_floating_point<R>::value
199 && std::is_integral<T>::value
200 >::type
201 >{
202 constexpr static checked_result<R>
203 cast(const T & t){
204 if(std::numeric_limits<R>::digits < std::numeric_limits<T>::digits){
205 if(utility::significant_bits(t) > std::numeric_limits<R>::digits){
206 return F::invoke(
207 safe_numerics_error::precision_overflow_error,
208 "keep precision"
209 );
210 }
211 }
212 return t;
213 }
214}; // heterogeneous_checked_operation
215
216// binary operations on primitive integer types
217
218template<
219 typename R,
220 class F
221>
222struct checked_operation<R, F,
223 typename std::enable_if<
224 std::is_integral<R>::value
225 >::type
226>{
227 ////////////////////////////////////////////////////
228 // safe addition on primitive types
229
230 struct add_impl_detail {
231 // result unsigned
232 constexpr static checked_result<R> add(
233 const R t,
234 const R u,
235 std::false_type // R unsigned
236 ){
237 return
238 // INT30-C. Ensure that unsigned integer operations do not wrap
239 std::numeric_limits<R>::max() - u < t ?
240 F::template invoke<safe_numerics_error::positive_overflow_error>(
241 "addition result too large"
242 )
243 :
244 checked_result<R>(t + u)
245 ;
246 }
247
248 // result signed
249 constexpr static checked_result<R> add(
250 const R t,
251 const R u,
252 std::true_type // R signed
253 ){
254 // INT32-C. Ensure that operations on signed integers do not result in overflow
255 return
256 // INT32-C. Ensure that operations on signed integers do not result in overflow
257 ((u > 0) && (t > (std::numeric_limits<R>::max() - u))) ?
258 F::template invoke<safe_numerics_error::positive_overflow_error>(
259 "addition result too large"
260 )
261 :
262 ((u < 0) && (t < (std::numeric_limits<R>::min() - u))) ?
263 F::template invoke<safe_numerics_error::negative_overflow_error>(
264 "addition result too low"
265 )
266 :
267 checked_result<R>(t + u)
268 ;
269 }
270 }; // add_impl_detail
271
272 constexpr static checked_result<R>
273 add(const R & t, const R & u){
274 return add_impl_detail::add(t, u, std::is_signed<R>());
275 }
276
277 ////////////////////////////////////////////////////
278 // safe subtraction on primitive types
279 struct subtract_impl_detail {
280
281 // result unsigned
282 constexpr static checked_result<R> subtract(
283 const R t,
284 const R u,
285 std::false_type // R is unsigned
286 ){
287 // INT30-C. Ensure that unsigned integer operations do not wrap
288 return
289 t < u ?
290 F::template invoke<safe_numerics_error::negative_overflow_error>(
291 "subtraction result cannot be negative"
292 )
293 :
294 checked_result<R>(t - u)
295 ;
296 }
297
298 // result signed
299 constexpr static checked_result<R> subtract(
300 const R t,
301 const R u,
302 std::true_type // R is signed
303 ){ // INT32-C
304 return
305 // INT32-C. Ensure that operations on signed integers do not result in overflow
306 ((u > 0) && (t < (std::numeric_limits<R>::min() + u))) ?
307 F::template invoke<safe_numerics_error::negative_overflow_error>(
308 "subtraction result overflows result type"
309 )
310 :
311 ((u < 0) && (t > (std::numeric_limits<R>::max() + u))) ?
312 F::template invoke<safe_numerics_error::positive_overflow_error>(
313 "subtraction result overflows result type"
314 )
315 :
316 checked_result<R>(t - u)
317 ;
318 }
319
320 }; // subtract_impl_detail
321
322 constexpr static checked_result<R> subtract(const R & t, const R & u){
323 return subtract_impl_detail::subtract(t, u, std::is_signed<R>());
324 }
325
326 ////////////////////////////////////////////////////
327 // safe minus on primitive types
328 struct minus_impl_detail {
329
330 // result unsigned
331 constexpr static checked_result<R> minus(
332 const R t,
333 std::false_type // R is unsigned
334 ){
335 return t > 0 ?
336 F::template invoke<safe_numerics_error::negative_overflow_error>(
337 "minus unsigned would be negative"
338 )
339 :
340 // t == 0
341 checked_result<R>(0)
342 ;
343 }
344
345 // result signed
346 constexpr static checked_result<R> minus(
347 const R t,
348 std::true_type // R is signed
349 ){ // INT32-C
350 return t == std::numeric_limits<R>::min() ?
351 F::template invoke<safe_numerics_error::positive_overflow_error>(
352 "subtraction result overflows result type"
353 )
354 :
355 checked_result<R>(-t)
356 ;
357 }
358
359 }; // minus_impl_detail
360
361 constexpr static checked_result<R> minus(const R & t){
362 return minus_impl_detail::minus(t, std::is_signed<R>());
363 }
364
365 ////////////////////////////////////////////////////
366 // safe multiplication on primitive types
367
368 struct multiply_impl_detail {
369
370 // result unsigned
371 constexpr static checked_result<R> multiply(
372 const R t,
373 const R u,
374 std::false_type, // R is unsigned
375 std::false_type // !(sizeochecked_result<R>R) > sizeochecked_result<R>std::uintmax_t) / 2)
376
377 ){
378 // INT30-C
379 // fast method using intermediate result guaranteed not to overflow
380 // todo - replace std::uintmax_t with a size double the size of R
381 using i_type = std::uintmax_t;
382 return
383 static_cast<i_type>(t) * static_cast<i_type>(u)
384 > std::numeric_limits<R>::max() ?
385 F::template invoke<safe_numerics_error::positive_overflow_error>(
386 "multiplication overflow"
387 )
388 :
389 checked_result<R>(t * u)
390 ;
391 }
392 constexpr static checked_result<R> multiply(
393 const R t,
394 const R u,
395 std::false_type, // R is unsigned
396 std::true_type // (sizeochecked_result<R>R) > sizeochecked_result<R>std::uintmax_t) / 2)
397
398 ){
399 // INT30-C
400 return
401 u > 0 && t > std::numeric_limits<R>::max() / u ?
402 F::template invoke<safe_numerics_error::positive_overflow_error>(
403 "multiplication overflow"
404 )
405 :
406 checked_result<R>(t * u)
407 ;
408 }
409
410 // result signed
411 constexpr static checked_result<R> multiply(
412 const R t,
413 const R u,
414 std::true_type, // R is signed
415 std::false_type // ! (sizeochecked_result<R>R) > (sizeochecked_result<R>std::intmax_t) / 2))
416
417 ){
418 // INT30-C
419 // fast method using intermediate result guaranteed not to overflow
420 // todo - replace std::intmax_t with a size double the size of R
421 using i_type = std::intmax_t;
422 return
423 (
424 static_cast<i_type>(t) * static_cast<i_type>(u)
425 > static_cast<i_type>(std::numeric_limits<R>::max())
426 ) ?
427 F::template invoke<safe_numerics_error::positive_overflow_error>(
428 "multiplication overflow"
429 )
430 :
431 (
432 static_cast<i_type>(t) * static_cast<i_type>(u)
433 < static_cast<i_type>(std::numeric_limits<R>::min())
434 ) ?
435 F::template invoke<safe_numerics_error::negative_overflow_error>(
436 "multiplication overflow"
437 )
438 :
439 checked_result<R>(t * u)
440 ;
441 }
442 constexpr static checked_result<R> multiply(
443 const R t,
444 const R u,
445 std::true_type, // R is signed
446 std::true_type // (sizeochecked_result<R>R) > (sizeochecked_result<R>std::intmax_t) / 2))
447 ){ // INT32-C
448 return t > 0 ?
449 u > 0 ?
450 t > std::numeric_limits<R>::max() / u ?
451 F::template invoke<safe_numerics_error::positive_overflow_error>(
452 "multiplication overflow"
453 )
454 :
455 checked_result<R>(t * u)
456 : // u <= 0
457 u < std::numeric_limits<R>::min() / t ?
458 F::template invoke<safe_numerics_error::negative_overflow_error>(
459 "multiplication overflow"
460 )
461 :
462 checked_result<R>(t * u)
463 : // t <= 0
464 u > 0 ?
465 t < std::numeric_limits<R>::min() / u ?
466 F::template invoke<safe_numerics_error::negative_overflow_error>(
467 "multiplication overflow"
468 )
469 :
470 checked_result<R>(t * u)
471 : // u <= 0
472 t != 0 && u < std::numeric_limits<R>::max() / t ?
473 F::template invoke<safe_numerics_error::positive_overflow_error>(
474 "multiplication overflow"
475 )
476 :
477 checked_result<R>(t * u)
478 ;
479 }
480 }; // multiply_impl_detail
481
482 constexpr static checked_result<R> multiply(const R & t, const R & u){
483 return multiply_impl_detail::multiply(
484 t,
485 u,
486 std::is_signed<R>(),
487 std::integral_constant<
488 bool,
489 (sizeof(R) > sizeof(std::uintmax_t) / 2)
490 >()
491 );
492 }
493
494 ////////////////////////////////
495 // safe division on unsafe types
496
497 struct divide_impl_detail {
498 constexpr static checked_result<R> divide(
499 const R & t,
500 const R & u,
501 std::false_type // R is unsigned
502 ){
503 return t / u;
504 }
505
506 constexpr static checked_result<R> divide(
507 const R & t,
508 const R & u,
509 std::true_type // R is signed
510 ){
511 return
512 (u == -1 && t == std::numeric_limits<R>::min()) ?
513 F::template invoke<safe_numerics_error::positive_overflow_error>(
514 "result cannot be represented"
515 )
516 :
517 checked_result<R>(t / u)
518 ;
519 }
520 }; // divide_impl_detail
521
522 // note that we presume that the size of R >= size of T
523 constexpr static checked_result<R> divide(const R & t, const R & u){
524 if(u == 0){
525 return F::template invoke<safe_numerics_error::domain_error>(
526 "divide by zero"
527 );
528 }
529 return divide_impl_detail::divide(t, u, std::is_signed<R>());
530 }
531
532 ////////////////////////////////
533 // safe modulus on unsafe types
534
535 struct modulus_impl_detail {
536 constexpr static checked_result<R> modulus(
537 const R & t,
538 const R & u,
539 std::false_type // R is unsigned
540 ){
541 return t % u;
542 }
543
544 constexpr static checked_result<R> modulus(
545 const R & t,
546 const R & u,
547 std::true_type // R is signed
548 ){
549 if(u >= 0)
550 return t % u;
551 checked_result<R> ux = checked::minus(u);
552 if(ux.exception())
553 return t;
554 return t % static_cast<R>(ux);
555 }
556 }; // modulus_impl_detail
557
558 constexpr static checked_result<R> modulus(const R & t, const R & u){
559 if(0 == u)
560 return F::template invoke<safe_numerics_error::domain_error>(
561 "denominator is zero"
562 );
563
564 // why to we need abs here? the sign of the modulus is the sign of the
565 // dividend. Consider -128 % -1 The result of this operation should be -1
566 // but if I use t % u the x86 hardware uses the divide instruction
567 // capturing the modulus as a side effect. When it does this, it
568 // invokes the operation -128 / -1 -> 128 which overflows a signed type
569 // and provokes a hardware exception. We can fix this using abs()
570 // since -128 % -1 = -128 % 1 = 0
571 return modulus_impl_detail::modulus(t, u, typename std::is_signed<R>::type());
572 }
573
574 ///////////////////////////////////
575 // shift operations
576
577 struct left_shift_integer_detail {
578
579 #if 0
580 // todo - optimize for gcc to exploit builtin
581 /* for gcc compilers
582 int __builtin_clz (unsigned int x)
583 Returns the number of leading 0-bits in x, starting at the
584 most significant bit position. If x is 0, the result is undefined.
585 */
586
587 #ifndef __has_feature // Optional of course.
588 #define __has_feature(x) 0 // Compatibility with non-clang compilers.
589 #endif
590
591 template<typename T>
592 constexpr unsigned int leading_zeros(const T & t){
593 if(0 == t)
594 return 0;
595 #if __has_feature(builtin_clz)
596 return __builtin_clz(t);
597 #else
598 #endif
599 }
600 #endif
601
602 // INT34-C C++
603
604 // standard paragraph 5.8 / 2
605 // The value of E1 << E2 is E1 left-shifted E2 bit positions;
606 // vacated bits are zero-filled.
607 constexpr static checked_result<R> left_shift(
608 const R & t,
609 const R & u,
610 std::false_type // R is unsigned
611 ){
612 // the value of the result is E1 x 2^E2, reduced modulo one more than
613 // the maximum value representable in the result type.
614
615 // see 5.8 & 1
616 // if right operand is
617 // greater than or equal to the length in bits of the promoted left operand.
618 if(
619 safe_compare::greater_than(
620 u,
621 std::numeric_limits<R>::digits - utility::significant_bits(t)
622 )
623 ){
624 // behavior is undefined
625 return F::template invoke<safe_numerics_error::shift_too_large>(
626 "shifting left more bits than available is undefined behavior"
627 );
628 }
629 return t << u;
630 }
631
632 constexpr static checked_result<R> left_shift(
633 const R & t,
634 const R & u,
635 std::true_type // R is signed
636 ){
637 // and [E1] has a non-negative value
638 if(t >= 0){
639 // and E1 x 2^E2 is representable in the corresponding
640 // unsigned type of the result type,
641
642 // see 5.8 & 1
643 // if right operand is
644 // greater than or equal to the length in bits of the promoted left operand.
645 if(
646 safe_compare::greater_than(
647 u,
648 std::numeric_limits<R>::digits - utility::significant_bits(t)
649 )
650 ){
651 // behavior is undefined
652 return F::template invoke<safe_numerics_error::shift_too_large>(
653 "shifting left more bits than available"
654 );
655 }
656 else{
657 return t << u;
658 }
659 }
660 // otherwise, the behavior is undefined.
661 return F::template invoke<safe_numerics_error::negative_shift>(
662 "shifting a negative value"
663 );
664 }
665
666 }; // left_shift_integer_detail
667
668 constexpr static checked_result<R> left_shift(
669 const R & t,
670 const R & u
671 ){
672 // INT34-C - Do not shift an expression by a negative number of bits
673
674 // standard paragraph 5.8 & 1
675 // if the right operand is negative
676 if(u == 0){
677 return t;
678 }
679 if(u < 0){
680 return F::template invoke<safe_numerics_error::negative_shift>(
681 "shifting negative amount"
682 );
683 }
684 if(u > std::numeric_limits<R>::digits){
685 // behavior is undefined
686 return F::template invoke<safe_numerics_error::shift_too_large>(
687 "shifting more bits than available"
688 );
689 }
690 return left_shift_integer_detail::left_shift(t, u, std::is_signed<R>());
691 }
692
693 // right shift
694
695 struct right_shift_integer_detail {
696
697 // INT34-C C++
698
699 // standard paragraph 5.8 / 3
700 // The value of E1 << E2 is E1 left-shifted E2 bit positions;
701 // vacated bits are zero-filled.
702 constexpr static checked_result<R> right_shift(
703 const R & t,
704 const R & u,
705 std::false_type // T is unsigned
706 ){
707 // the value of the result is the integral part of the
708 // quotient of E1/2E2
709 return t >> u;
710 }
711
712 constexpr static checked_result<R> right_shift(
713 const R & t,
714 const R & u,
715 std::true_type // T is signed;
716 ){
717 if(t < 0){
718 // note that the C++ standard considers this case is "implemenation
719 // defined" rather than "undefined".
720 return F::template invoke<safe_numerics_error::negative_value_shift>(
721 "shifting a negative value"
722 );
723 }
724
725 // the value is the integral part of E1 / 2^E2,
726 return t >> u;
727 }
728 }; // right_shift_integer_detail
729
730 constexpr static checked_result<R> right_shift(
731 const R & t,
732 const R & u
733 ){
734 // INT34-C - Do not shift an expression by a negative number of bits
735
736 // standard paragraph 5.8 & 1
737 // if the right operand is negative
738 if(u < 0){
739 return F::template invoke<safe_numerics_error::negative_shift>(
740 "shifting negative amount"
741 );
742 }
743 if(u > std::numeric_limits<R>::digits){
744 // behavior is undefined
745 return F::template invoke<safe_numerics_error::shift_too_large>(
746 "shifting more bits than available"
747 );
748 }
749 return right_shift_integer_detail::right_shift(t, u ,std::is_signed<R>());
750 }
751
752 ///////////////////////////////////
753 // bitwise operations
754
755 // INT13-C Note: We don't enforce recommendation as acually written
756 // as it would break too many programs. Specifically, we permit signed
757 // integer operands.
758
759 constexpr static checked_result<R> bitwise_or(const R & t, const R & u){
760 using namespace boost::safe_numerics::utility;
761 const unsigned int result_size
762 = std::max(significant_bits(t), significant_bits(u));
763
764 if(result_size > bits_type<R>::value){
765 return F::template invoke<safe_numerics_error::positive_overflow_error>(
766 "result type too small to hold bitwise or"
767 );
768 }
769 return t | u;
770 }
771
772 constexpr static checked_result<R> bitwise_xor(const R & t, const R & u){
773 using namespace boost::safe_numerics::utility;
774 const unsigned int result_size
775 = std::max(significant_bits(t), significant_bits(u));
776
777 if(result_size > bits_type<R>::value){
778 return F::template invoke<safe_numerics_error::positive_overflow_error>(
779 "result type too small to hold bitwise or"
780 );
781 }
782 return t ^ u;
783 }
784
785 constexpr static checked_result<R> bitwise_and(const R & t, const R & u){
786 using namespace boost::safe_numerics::utility;
787 const unsigned int result_size
788 = std::min(significant_bits(t), significant_bits(u));
789
790 if(result_size > bits_type<R>::value){
791 return F::template invoke<safe_numerics_error::positive_overflow_error>(
792 "result type too small to hold bitwise and"
793 );
794 }
795 return t & u;
796 }
797
798 constexpr static checked_result<R> bitwise_not(const R & t){
799 using namespace boost::safe_numerics::utility;
800
801 if(significant_bits(t) > bits_type<R>::value){
802 return F::template invoke<safe_numerics_error::positive_overflow_error>(
803 "result type too small to hold bitwise inverse"
804 );
805 }
806 return ~t;
807 }
808
809}; // checked_operation
810} // safe_numerics
811} // boost
812
813#endif // BOOST_NUMERIC_CHECKED_INTEGER_HPP
814

source code of boost/libs/safe_numerics/include/boost/safe_numerics/checked_integer.hpp