1 #ifndef BOOST_NUMERIC_AUTOMATIC_HPP
2 #define BOOST_NUMERIC_AUTOMATIC_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 // policy which creates expanded results types designed
11 // to avoid overflows.
12 
13 #include <limits>
14 #include <cstdint>     // (u)intmax_t,
15 #include <type_traits> // conditional
16 #include <boost/integer.hpp>
17 
18 #include "safe_common.hpp"
19 #include "checked_result.hpp"
20 #include "checked_default.hpp"
21 #include "checked_integer.hpp"
22 #include "checked_result_operations.hpp"
23 #include "interval.hpp"
24 #include "utility.hpp"
25 
26 namespace boost {
27 namespace safe_numerics {
28 
29 struct automatic {
30 private:
31     // the following returns the "true" type.  After calculating the new max and min
32     // these return the minimum size type which can hold the expected result.
33     struct defer_stored_signed_lazily {
34         template<std::intmax_t Min, std::intmax_t Max>
35         using type = utility::signed_stored_type<Min, Max>;
36     };
37 
38     struct defer_stored_unsigned_lazily {
39         template<std::uintmax_t Min, std::uintmax_t Max>
40         using type = utility::unsigned_stored_type<Min, Max>;
41     };
42 
43     template<typename T, T Min, T Max>
44     struct result_type {
45         using type = typename std::conditional<
46             std::numeric_limits<T>::is_signed,
47             defer_stored_signed_lazily,
48             defer_stored_unsigned_lazily
49         >::type::template type<Min, Max>;
50     };
51 
52 public:
53     ///////////////////////////////////////////////////////////////////////
54     template<typename T, typename U>
55     struct addition_result {
56         using temp_base_type = typename std::conditional<
57             // if both arguments are unsigned
58             ! std::numeric_limits<T>::is_signed
59             && ! std::numeric_limits<U>::is_signed,
60             // result is unsigned
61             std::uintmax_t,
62             // otherwise result is signed
63             std::intmax_t
64         >::type;
65 
66         using r_type = checked_result<temp_base_type>;
67         using r_interval_type = interval<r_type>;
68 
69         constexpr static const r_interval_type t_interval{
70             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
71             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
72         };
73 
74         constexpr static const r_interval_type u_interval{
75             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
76             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
77         };
78 
79         constexpr static const r_interval_type r_interval = t_interval + u_interval;
80 
81         constexpr static auto rl = r_interval.l;
82         constexpr static auto ru = r_interval.u;
83 
84         using type = typename result_type<
85             temp_base_type,
86             rl.exception()
87                 ? std::numeric_limits<temp_base_type>::min()
88                 : static_cast<temp_base_type>(rl),
89             ru.exception()
90                 ? std::numeric_limits<temp_base_type>::max()
91                 : static_cast<temp_base_type>(ru)
92         >::type;
93     };
94 
95     ///////////////////////////////////////////////////////////////////////
96     template<typename T, typename U>
97     struct subtraction_result {
98         // result of subtraction are always signed.
99         using temp_base_type = intmax_t;
100 
101         using r_type = checked_result<temp_base_type>;
102         using r_interval_type = interval<r_type>;
103 
104         constexpr static const r_interval_type t_interval{
105             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
106             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
107         };
108 
109         constexpr static const r_interval_type u_interval{
110             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
111             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
112         };
113 
114         constexpr static const r_interval_type r_interval = t_interval - u_interval;
115 
116         constexpr static auto rl = r_interval.l;
117         constexpr static auto ru = r_interval.u;
118 
119         using type = typename result_type<
120             temp_base_type,
121             rl.exception()
122                 ? std::numeric_limits<temp_base_type>::min()
123                 : static_cast<temp_base_type>(rl),
124             ru.exception()
125                 ? std::numeric_limits<temp_base_type>::max()
126                 : static_cast<temp_base_type>(ru)
127         >::type;
128     };
129 
130     ///////////////////////////////////////////////////////////////////////
131     template<typename T, typename U>
132     struct multiplication_result {
133         using temp_base_type = typename std::conditional<
134             // if both arguments are unsigned
135             ! std::numeric_limits<T>::is_signed
136             && ! std::numeric_limits<U>::is_signed,
137             // result is unsigned
138             std::uintmax_t,
139             // otherwise result is signed
140             std::intmax_t
141         >::type;
142 
143         using r_type = checked_result<temp_base_type>;
144         using r_interval_type = interval<r_type>;
145 
146         constexpr static const r_interval_type t_interval{
147             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
148             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
149         };
150 
151         constexpr static const r_interval_type u_interval{
152             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
153             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
154         };
155 
156         constexpr static const r_interval_type r_interval = t_interval * u_interval;
157 
158         constexpr static auto rl = r_interval.l;
159         constexpr static auto ru = r_interval.u;
160 
161         using type = typename result_type<
162             temp_base_type,
163             rl.exception()
164                 ? std::numeric_limits<temp_base_type>::min()
165                 : static_cast<temp_base_type>(rl),
166             ru.exception()
167                 ? std::numeric_limits<temp_base_type>::max()
168                 : static_cast<temp_base_type>(ru)
169         >::type;
170     };
171 
172     ///////////////////////////////////////////////////////////////////////
173     template<typename T, typename U>
174     struct division_result {
175         using temp_base_type = typename std::conditional<
176             // if both arguments are unsigned
177             ! std::numeric_limits<T>::is_signed
178             && ! std::numeric_limits<U>::is_signed,
179             // result is unsigned
180             std::uintmax_t,
181             // otherwise result is signed
182             std::intmax_t
183         >::type;
184 
185         using r_type = checked_result<temp_base_type>;
186         using r_interval_type = interval<r_type>;
187 
188         constexpr static const r_interval_type t_interval{
189             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
190             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
191         };
192 
193         constexpr static const r_interval_type u_interval{
194             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
195             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
196         };
197 
rxboost::safe_numerics::automatic::division_result198         constexpr static const r_interval_type rx(){
199             if(u_interval.u < r_type(0)
200             || u_interval.l > r_type(0))
201                 return t_interval / u_interval;
202             return utility::minmax(
203                 std::initializer_list<r_type> {
204                     t_interval.l / u_interval.l,
205                     t_interval.l / r_type(-1),
206                     t_interval.l / r_type(1),
207                     t_interval.l / u_interval.u,
208                     t_interval.u / u_interval.l,
209                     t_interval.u / r_type(-1),
210                     t_interval.u / r_type(1),
211                     t_interval.u / u_interval.u,
212                 }
213             );
214         }
215 
216         constexpr static const r_interval_type r_interval = rx();
217 
218         constexpr static auto rl = r_interval.l;
219         constexpr static auto ru = r_interval.u;
220 
221         using type = typename result_type<
222             temp_base_type,
223             rl.exception()
224                 ? std::numeric_limits<temp_base_type>::min()
225                 : static_cast<temp_base_type>(rl),
226             ru.exception()
227                 ? std::numeric_limits<temp_base_type>::max()
228                 : static_cast<temp_base_type>(ru)
229         >::type;
230     };
231 
232     ///////////////////////////////////////////////////////////////////////
233     template<typename T, typename U>
234     struct modulus_result {
235         using temp_base_type = typename std::conditional<
236             // if both arguments are unsigned
237             ! std::numeric_limits<T>::is_signed
238             && ! std::numeric_limits<U>::is_signed,
239             // result is unsigned
240             std::uintmax_t,
241             // otherwise result is signed
242             std::intmax_t
243         >::type;
244 
245         using r_type = checked_result<temp_base_type>;
246         using r_interval_type = interval<r_type>;
247 
248         constexpr static const r_interval_type t_interval{
249             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
250             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
251         };
252 
253         constexpr static const r_interval_type u_interval{
254             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
255             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
256         };
257 
rxboost::safe_numerics::automatic::modulus_result258         constexpr static const r_interval_type rx(){
259             if(u_interval.u < r_type(0)
260             || u_interval.l > r_type(0))
261                 return t_interval / u_interval;
262             return utility::minmax(
263                 std::initializer_list<r_type> {
264                     t_interval.l % u_interval.l,
265                     t_interval.l % r_type(-1),
266                     t_interval.l % r_type(1),
267                     t_interval.l % u_interval.u,
268                     t_interval.u % u_interval.l,
269                     t_interval.u % r_type(-1),
270                     t_interval.u % r_type(1),
271                     t_interval.u % u_interval.u,
272                 }
273             );
274         }
275 
276         constexpr static const r_interval_type r_interval = rx();
277 
278         constexpr static auto rl = r_interval.l;
279         constexpr static auto ru = r_interval.u;
280 
281         using type = typename result_type<
282             temp_base_type,
283             rl.exception()
284                 ? std::numeric_limits<temp_base_type>::min()
285                 : static_cast<temp_base_type>(rl),
286             ru.exception()
287                 ? std::numeric_limits<temp_base_type>::max()
288                 : static_cast<temp_base_type>(ru)
289         >::type;
290     };
291 
292     ///////////////////////////////////////////////////////////////////////
293     // note: comparison_result (<, >, ...) is special.
294     // The return value is always a bool.  The type returned here is
295     // the intermediate type applied to make the values comparable.
296     template<typename T, typename U>
297     struct comparison_result {
298         using temp_base_type = typename std::conditional<
299             // if both arguments are unsigned
300             ! std::numeric_limits<T>::is_signed
301             && ! std::numeric_limits<U>::is_signed,
302             // result is unsigned
303             std::uintmax_t,
304             // otherwise result is signed
305             std::intmax_t
306         >::type;
307 
308         using r_type = checked_result<temp_base_type>;
309         using r_interval_type = interval<r_type>;
310 
311         constexpr static const r_interval_type t_interval{
312             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
313             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
314         };
315 
316         constexpr static const r_interval_type u_interval{
317             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
318             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
319         };
320 
321         // workaround some microsoft problem
322         #if 0
323         constexpr static r_type min(const r_type & t, const r_type & u){
324             // assert(! u.exception());
325             // assert(! t.exception());
326             return static_cast<bool>(t < u) ? t : u;
327         }
328 
329        constexpr static r_type max(const r_type & t, const r_type & u){
330             // assert(! u.exception());
331             // assert(! t.exception());
332             return static_cast<bool>(t < u) ? u : t;
333         }
334         #endif
335 
336         // union of two intervals
337         // note: we can't use t_interval | u_interval because it
338         // depends on max and min which in turn depend on < which in turn
339         // depends on implicit conversion of tribool to bool
union_intervalboost::safe_numerics::automatic::comparison_result340         constexpr static r_interval_type union_interval(
341             const r_interval_type & t,
342             const r_interval_type & u
343         ){
344             //const r_type & rl = min(t.l, u.l);
345             const r_type & rmin = static_cast<bool>(t.l < u.l) ? t.l : u.l;
346             //const r_type & ru = max(t.u, u.u);
347             const r_type & rmax = static_cast<bool>(t.u < u.u) ? u.u : t.u;
348             return r_interval_type(rmin, rmax);
349         }
350 
351         constexpr static const r_interval_type r_interval =
352             union_interval(t_interval, u_interval);
353 
354         constexpr static auto rl = r_interval.l;
355         constexpr static auto ru = r_interval.u;
356 
357         using type = typename result_type<
358             temp_base_type,
359             rl.exception()
360                 ? std::numeric_limits<temp_base_type>::min()
361                 : static_cast<temp_base_type>(rl),
362             ru.exception()
363                 ? std::numeric_limits<temp_base_type>::max()
364                 : static_cast<temp_base_type>(ru)
365         >::type;
366     };
367 
368     ///////////////////////////////////////////////////////////////////////
369     // shift operations
370     template<typename T, typename U>
371     struct left_shift_result {
372         using temp_base_type = typename std::conditional<
373             std::numeric_limits<T>::is_signed,
374             std::intmax_t,
375             std::uintmax_t
376         >::type;
377 
378         using r_type = checked_result<temp_base_type>;
379         using r_interval_type = interval<r_type>;
380 
381         constexpr static const r_interval_type t_interval{
382             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
383             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
384         };
385 
386         constexpr static const r_interval_type u_interval{
387             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
388             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
389         };
390 
391         constexpr static const r_interval_type r_interval =
392             t_interval << u_interval;
393 
394         constexpr static auto rl = r_interval.l;
395         constexpr static auto ru = r_interval.u;
396 
397         using type = typename result_type<
398             temp_base_type,
399             rl.exception()
400                 ? std::numeric_limits<temp_base_type>::min()
401                 : static_cast<temp_base_type>(rl),
402             ru.exception()
403                 ? std::numeric_limits<temp_base_type>::max()
404                 : static_cast<temp_base_type>(ru)
405         >::type;
406     };
407 
408     ///////////////////////////////////////////////////////////////////////
409     template<typename T, typename U>
410     struct right_shift_result {
411         using temp_base_type = typename std::conditional<
412             std::numeric_limits<T>::is_signed,
413             std::intmax_t,
414             std::uintmax_t
415         >::type;
416 
417         using r_type = checked_result<temp_base_type>;
418         using r_interval_type = interval<r_type>;
419 
420         constexpr static const r_interval_type t_interval{
421             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
422             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
423         };
424 
425         constexpr static const r_type u_min
426             = checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min()));
427 
428         constexpr static const r_interval_type u_interval{
429             u_min.exception()
430             ? r_type(0)
431             : u_min,
432             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
433         };
434 
435         constexpr static const r_interval_type r_interval = t_interval >> u_interval;
436 
437         constexpr static auto rl = r_interval.l;
438         constexpr static auto ru = r_interval.u;
439 
440         using type = typename result_type<
441             temp_base_type,
442             rl.exception()
443                 ? std::numeric_limits<temp_base_type>::min()
444                 : static_cast<temp_base_type>(rl),
445             ru.exception()
446                 ? std::numeric_limits<temp_base_type>::max()
447                 : static_cast<temp_base_type>(ru)
448         >::type;
449 
450     };
451 
452     ///////////////////////////////////////////////////////////////////////
453     template<typename T, typename U>
454     struct bitwise_and_result {
455         using type = decltype(
456             typename base_type<T>::type()
457             & typename base_type<U>::type()
458         );
459     };
460     template<typename T, typename U>
461     struct bitwise_or_result {
462         using type = decltype(
463             typename base_type<T>::type()
464             | typename base_type<U>::type()
465         );
466     };
467     template<typename T, typename U>
468     struct bitwise_xor_result {
469         using type = decltype(
470             typename base_type<T>::type()
471             ^ typename base_type<U>::type()
472         );
473     };
474 };
475 
476 } // safe_numerics
477 } // boost
478 
479 #endif // BOOST_NUMERIC_AUTOMATIC_HPP
480