CNL  2.0.2 (development)
Compositional Numeric Library
is_overflow.h
1 
2 // Copyright John McFarlane 2019.
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file ../LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 
7 #if !defined(CNL_IMPL_OVERFLOW_IS_OVERFLOW_H)
8 #define CNL_IMPL_OVERFLOW_IS_OVERFLOW_H
9 
10 #include "../../numeric.h"
11 #include "../custom_operator/op.h"
12 #include "../num_traits/digits.h"
13 #include "../numbers/signedness.h"
14 #include "../polarity.h"
15 
16 #include <algorithm>
17 #include <limits>
18 #include <type_traits>
19 
21 namespace cnl {
22  namespace _impl {
24  // cnl::_impl::overflow_digits
25 
26  template<class T, polarity>
27  struct overflow_digits;
28 
29  template<class T>
30  struct overflow_digits<T, polarity::positive>
31  : public std::integral_constant<int, std::numeric_limits<T>::digits> {
32  };
33 
34  template<class T>
35  struct overflow_digits<T, polarity::negative>
36  : public std::integral_constant<int, cnl::numbers::signedness_v<T> ? digits_v<T> : 0> {
37  };
38 
40  // cnl::_impl::has_most_negative_number
41 
42  // implementation assumes one of three things:
43  // 1. type is unsigned
44  // 2. type is symmetrical around zero (e.g. elastic_integer)
45  // 3. type has most negative number
46  template<typename Operand, bool IsSigned = numbers::signedness_v<Operand>>
47  struct has_most_negative_number : std::false_type {
48  };
49 
50  template<typename Operand>
51  struct has_most_negative_number<Operand, true>
52  : std::integral_constant<
53  bool, std::numeric_limits<Operand>::lowest() < -std::numeric_limits<Operand>::max()> {
54  };
55 
57  // cnl::_impl::is_overflow_convert
58 
59  template<polarity Polarity, bool DestinationIsFloat, bool SourceIsFloat>
60  struct is_overflow_convert;
61 
62  template<>
63  struct is_overflow_convert<polarity::positive, false, false> {
64  template<typename Destination, typename Source>
65  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
66  {
67  return overflow_digits<Destination, polarity::positive>::value
68  < overflow_digits<Source, polarity::positive>::value
69  && rhs > static_cast<Source>(std::numeric_limits<Destination>::max());
70  }
71  };
72 
73  template<>
74  struct is_overflow_convert<polarity::positive, false, true> {
75  template<typename Destination, typename Source>
76  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
77  {
78  return rhs > static_cast<Source>(std::numeric_limits<Destination>::max());
79  }
80  };
81 
82  template<>
83  struct is_overflow_convert<polarity::positive, true, false> {
84  template<typename Destination, typename Source>
85  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
86  {
87  return static_cast<Destination>(rhs) > std::numeric_limits<Destination>::max();
88  }
89  };
90 
91  template<>
92  struct is_overflow_convert<polarity::positive, true, true> {
93  template<typename Destination, typename Source>
94  [[nodiscard]] constexpr auto operator()(Source const&) const
95  {
96  return false;
97  }
98  };
99 
100  template<>
101  struct is_overflow_convert<polarity::negative, false, false> {
102  template<typename Destination, typename Source>
103  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
104  {
105  return overflow_digits<Destination, polarity::negative>::value
106  < overflow_digits<Source, polarity::negative>::value
107  && rhs < static_cast<Source>(std::numeric_limits<Destination>::lowest());
108  }
109  };
110 
111  template<>
112  struct is_overflow_convert<polarity::negative, false, true> {
113  template<typename Destination, typename Source>
114  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
115  {
116  return rhs < static_cast<Source>(std::numeric_limits<Destination>::lowest());
117  }
118  };
119 
120  template<>
121  struct is_overflow_convert<polarity::negative, true, false> {
122  template<typename Destination, typename Source>
123  [[nodiscard]] constexpr auto operator()(Source const& rhs) const
124  {
125  return static_cast<Destination>(rhs) < std::numeric_limits<Destination>::lowest();
126  }
127  };
128 
129  template<>
130  struct is_overflow_convert<polarity::negative, true, true> {
131  template<typename Destination, typename Source>
132  [[nodiscard]] constexpr auto operator()(Source const&) const
133  {
134  return false;
135  }
136  };
137 
139  // cnl::_impl::operator_overflow_traits
140 
141  template<op Operator, typename... Operands>
142  struct operator_overflow_traits {
143  using result = op_result<Operator, Operands...>;
144 
145  static constexpr int positive_digits =
146  _impl::overflow_digits<result, polarity::positive>::value;
147  static constexpr int negative_digits =
148  _impl::overflow_digits<result, polarity::negative>::value;
149 
150  [[nodiscard]] static constexpr auto lowest()
151  {
152  return std::numeric_limits<result>::lowest();
153  }
154 
155  [[nodiscard]] static constexpr auto max()
156  {
157  return std::numeric_limits<result>::max();
158  }
159 
160  template<typename Operand>
161  [[nodiscard]] static constexpr auto leading_bits(Operand const& operand)
162  {
163  return cnl::leading_bits(static_cast<result>(operand));
164  }
165  };
166 
168  // cnl::_impl::is_overflow
169 
170  template<typename Operator, polarity Polarity>
171  struct is_overflow {
172  template<typename... Operands>
173  [[nodiscard]] constexpr auto operator()(Operands const&...) const
174  {
175  return false;
176  }
177  };
178 
179  template<polarity Polarity>
180  struct is_overflow<convert_op, Polarity> {
181  template<typename Destination, typename Source>
182  [[nodiscard]] constexpr auto operator()(Source const& from) const
183  {
184  using is_overflow_convert = cnl::_impl::is_overflow_convert<
185  Polarity, std::is_floating_point<Destination>::value,
186  std::is_floating_point<Source>::value>;
187  return is_overflow_convert{}.template operator()<Destination>(from);
188  }
189  };
190 
191 #if defined(_MSC_VER)
192 #pragma warning(push)
193 #pragma warning(disable : 4146)
194 #endif
195  template<>
196  struct is_overflow<minus_op, polarity::positive> {
197  template<typename Rhs>
198  [[nodiscard]] constexpr auto operator()(Rhs const& rhs) const
199  {
200  return has_most_negative_number<Rhs>::value && rhs < -std::numeric_limits<Rhs>::max();
201  }
202  };
203 
204  template<>
205  struct is_overflow<minus_op, polarity::negative> {
206  template<typename Rhs>
207  [[nodiscard]] constexpr auto operator()(Rhs const& rhs) const
208  {
209  return !numbers::signedness_v<Rhs> && rhs;
210  }
211  };
212 #if defined(_MSC_VER)
213 #pragma warning(pop)
214 #endif
215 
216  template<>
217  struct is_overflow<add_op, polarity::positive> {
218  template<typename Lhs, typename Rhs>
219  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
220  {
221  using traits = operator_overflow_traits<add_op, Lhs, Rhs>;
222  return (std::max(overflow_digits<Lhs, polarity::positive>::value, overflow_digits<Rhs, polarity::positive>::value)
223  + 1
224  > traits::positive_digits)
225  && lhs > Lhs{0} && rhs > Rhs{0} &&
226  typename traits::result(lhs) > traits::max() - rhs;
227  }
228  };
229 
230  template<>
231  struct is_overflow<add_op, polarity::negative> {
232  template<typename Lhs, typename Rhs>
233  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
234  {
235  using traits = operator_overflow_traits<add_op, Lhs, Rhs>;
236  return (std::max(overflow_digits<Lhs, polarity::positive>::value, overflow_digits<Rhs, polarity::positive>::value)
237  + 1
238  > traits::positive_digits)
239  && lhs < Lhs{0} && rhs < Rhs{0} &&
240  typename traits::result(lhs) < traits::lowest() - rhs;
241  }
242  };
243 
244 #if defined(__GNUC__)
245 #pragma GCC diagnostic push
246 #pragma GCC diagnostic ignored "-Wstrict-overflow"
247 #endif
248  template<>
249  struct is_overflow<subtract_op, polarity::positive> {
250  template<typename Lhs, typename Rhs>
251  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
252  {
253  using traits = operator_overflow_traits<subtract_op, Lhs, Rhs>;
254  return (std::max(overflow_digits<Lhs, polarity::positive>::value, overflow_digits<Rhs, polarity::negative>::value)
255  + 1
256  > traits::positive_digits)
257  && rhs < Rhs{0} // NOLINTNEXTLINE(bugprone-misplaced-widening-cast)
258  && lhs > static_cast<typename traits::result>(std::numeric_limits<Rhs>::max() + rhs);
259  }
260  };
261 
262  template<>
263  struct is_overflow<subtract_op, polarity::negative> {
264  template<typename Lhs, typename Rhs>
265  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
266  {
267  using traits = operator_overflow_traits<subtract_op, Lhs, Rhs>;
268  return (std::max(overflow_digits<Lhs, polarity::positive>::value, overflow_digits<Rhs, polarity::positive>::value)
269  + 1
270  > traits::positive_digits)
271  && (rhs >= 0) && lhs < traits::lowest() + rhs;
272  }
273  };
274 #if defined(__GNUC__)
275 #pragma GCC diagnostic pop
276 #endif
277 
278 #if defined(__GNUC__)
279 #pragma GCC diagnostic push
280 #pragma GCC diagnostic ignored "-Wsign-compare"
281 #endif
282  template<>
283  struct is_overflow<multiply_op, polarity::positive> {
284  template<typename Lhs, typename Rhs>
285  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
286  {
287  using traits = operator_overflow_traits<multiply_op, Lhs, Rhs>;
288  return (overflow_digits<Lhs, polarity::positive>::value
289  + overflow_digits<Rhs, polarity::positive>::value
290  > traits::positive_digits)
291  && ((lhs > Lhs{0}) ? (rhs > Rhs{0}) && (traits::max() / rhs) < lhs
292  : (rhs < Rhs{0}) && (traits::max() / rhs) > lhs);
293  }
294  };
295 
296  template<>
297  struct is_overflow<multiply_op, polarity::negative> {
298  template<typename Lhs, typename Rhs>
299  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
300  {
301  using traits = operator_overflow_traits<multiply_op, Lhs, Rhs>;
302  return (overflow_digits<Lhs, polarity::positive>::value
303  + overflow_digits<Rhs, polarity::positive>::value
304  > traits::positive_digits)
305  && ((lhs < Lhs{0}) ? (rhs > Rhs{0}) && (traits::lowest() / rhs) > lhs
306  : (rhs < Rhs{0}) && (traits::lowest() / rhs) < lhs);
307  }
308  };
309 #if defined(__GNUC__)
310 #pragma GCC diagnostic pop
311 #endif
312 
313  template<>
314  struct is_overflow<divide_op, polarity::positive> {
315  template<typename Lhs, typename Rhs>
316  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
317  {
318  using traits = operator_overflow_traits<divide_op, Lhs, Rhs>;
319  return (has_most_negative_number<Lhs>::value) ? rhs == -1 && lhs == traits::lowest()
320  : false;
321  }
322  };
323 
324  template<>
325  struct is_overflow<shift_left_op, polarity::negative> {
326  template<typename Lhs, typename Rhs>
327  requires numbers::signedness_v<Lhs>
328  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
329  {
330  using traits = operator_overflow_traits<shift_left_op, Lhs, Rhs>;
331  return lhs < 0 ? rhs > 0 ? rhs < traits::positive_digits
332  ? (lhs >> (traits::positive_digits - rhs)) != -1
333  : true
334  : false
335  : false;
336  }
337 
338  template<typename Lhs, typename Rhs>
339  requires(!numbers::signedness_v<Lhs>)
340  [[nodiscard]] constexpr auto
341  operator()(Lhs const&, Rhs const&) const
342  {
343  return false;
344  }
345  };
346 
347  template<>
348  struct is_overflow<shift_left_op, polarity::positive> {
349  template<typename Lhs, typename Rhs>
350  [[nodiscard]] constexpr auto operator()(Lhs const& lhs, Rhs const& rhs) const
351  {
352  using traits = operator_overflow_traits<shift_left_op, Lhs, Rhs>;
353  return lhs > 0 ? rhs > 0 ? rhs < traits::positive_digits
354  ? (lhs >> (traits::positive_digits - rhs)) != 0
355  : true
356  : false
357  : false;
358  }
359  };
360  }
361 }
362 
363 #endif // CNL_IMPL_OVERFLOW_IS_OVERFLOW_H
std::integral_constant
std::numeric_limits::lowest
T lowest(T... args)
cnl
compositional numeric library
Definition: abort.h:15
std::is_floating_point
std::max
T max(T... args)
std::numeric_limits