Line data Source code
1 : /**********************************************************************
2 : *
3 : * Name: cpl_safemaths.hpp
4 : * Project: CPL - Common Portability Library
5 : * Purpose: Arithmetic overflow checking
6 : * Author: Even Rouault <even.rouault at spatialys.com>
7 : *
8 : **********************************************************************
9 : * Copyright (c) 2017, Even Rouault <even.rouault at spatialys.com>
10 : *
11 : * Permission is hereby granted, free of charge, to any person obtaining a
12 : * copy of this software and associated documentation files (the "Software"),
13 : * to deal in the Software without restriction, including without limitation
14 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 : * and/or sell copies of the Software, and to permit persons to whom the
16 : * Software is furnished to do so, subject to the following conditions:
17 : *
18 : * The above copyright notice and this permission notice shall be included
19 : * in all copies or substantial portions of the Software.
20 : *
21 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 : * DEALINGS IN THE SOFTWARE.
28 : ****************************************************************************/
29 :
30 : #ifndef CPL_SAFEMATHS_INCLUDED
31 : #define CPL_SAFEMATHS_INCLUDED
32 :
33 : #include <exception>
34 : #include <limits>
35 :
36 : #ifndef __has_builtin
37 : #define __has_builtin(x) 0
38 : #endif
39 :
40 : #if (__GNUC__ >= 5 && !defined(__INTEL_COMPILER)) || \
41 : __has_builtin(__builtin_sadd_overflow)
42 : #define BUILTIN_OVERFLOW_CHECK_AVAILABLE
43 :
44 : #elif defined(_MSC_VER)
45 :
46 : #include "safeint.h"
47 :
48 : #elif defined(GDAL_COMPILATION)
49 : #include "cpl_port.h"
50 :
51 : #elif !defined(DISABLE_GINT64) && !defined(CPL_HAS_GINT64)
52 : #if defined(WIN32) && defined(_MSC_VER)
53 : typedef _int64 GInt64;
54 : typedef unsigned _int64 GUInt64;
55 : #else
56 : typedef long long GInt64;
57 : typedef unsigned long long GUInt64;
58 : #endif
59 : #define CPL_HAS_GINT64
60 : #endif
61 :
62 : template <typename T> struct CPLSafeInt
63 : {
64 : T val;
65 :
66 85568 : inline explicit CPLSafeInt(T valIn) : val(valIn)
67 : {
68 85568 : }
69 :
70 85533 : inline T v() const
71 : {
72 85533 : return val;
73 : }
74 : };
75 :
76 : class CPLSafeIntOverflow : public std::exception
77 : {
78 : public:
79 36 : inline CPLSafeIntOverflow()
80 36 : {
81 36 : }
82 : };
83 :
84 : class CPLSafeIntOverflowDivisionByZero : public CPLSafeIntOverflow
85 : {
86 : public:
87 2 : inline CPLSafeIntOverflowDivisionByZero()
88 2 : {
89 2 : }
90 : };
91 :
92 : /** Convenience functions to build a CPLSafeInt */
93 1253 : inline CPLSafeInt<int> CPLSM(int x)
94 : {
95 1253 : return CPLSafeInt<int>(x);
96 : }
97 :
98 43 : inline CPLSafeInt<unsigned> CPLSM(unsigned x)
99 : {
100 43 : return CPLSafeInt<unsigned>(x);
101 : }
102 :
103 2 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(int x)
104 : {
105 2 : if (x < 0)
106 1 : throw CPLSafeIntOverflow();
107 1 : return CPLSafeInt<unsigned>(static_cast<unsigned>(x));
108 : }
109 :
110 : // Unimplemented for now
111 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(unsigned x);
112 : inline CPLSafeInt<int> CPLSM(long x);
113 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(long x);
114 : inline CPLSafeInt<int> CPLSM(unsigned long x);
115 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(unsigned long x);
116 : #if defined(GDAL_COMPILATION)
117 608 : inline CPLSafeInt<GInt64> CPLSM(GInt64 x)
118 : {
119 608 : return CPLSafeInt<GInt64>(x);
120 : }
121 :
122 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(GInt64 x);
123 :
124 83663 : inline CPLSafeInt<GUInt64> CPLSM(GUInt64 x)
125 : {
126 83663 : return CPLSafeInt<GUInt64>(x);
127 : }
128 :
129 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(GUInt64 x);
130 : #endif
131 :
132 : #if !defined(BUILTIN_OVERFLOW_CHECK_AVAILABLE) && defined(_MSC_VER)
133 : class CPLMSVCSafeIntException : public msl::utilities::SafeIntException
134 : {
135 : public:
136 : static void SafeIntOnOverflow()
137 : {
138 : throw CPLSafeIntOverflow();
139 : }
140 :
141 : static void SafeIntOnDivZero()
142 : {
143 : throw CPLSafeIntOverflowDivisionByZero();
144 : }
145 : };
146 : #endif
147 :
148 : template <class T>
149 : inline CPLSafeInt<T> SafeAddSigned(const CPLSafeInt<T> &A,
150 : const CPLSafeInt<T> &B)
151 : {
152 : const auto a = A.v();
153 : const auto b = B.v();
154 : if (a > 0 && b > 0 && a > std::numeric_limits<T>::max() - b)
155 : throw CPLSafeIntOverflow();
156 : if (a < 0 && b < 0 && a < std::numeric_limits<T>::min() - b)
157 : throw CPLSafeIntOverflow();
158 : return CPLSM(a + b);
159 : }
160 :
161 50 : inline CPLSafeInt<int> operator+(const CPLSafeInt<int> &A,
162 : const CPLSafeInt<int> &B)
163 : {
164 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
165 : int res;
166 50 : if (__builtin_sadd_overflow(A.v(), B.v(), &res))
167 4 : throw CPLSafeIntOverflow();
168 92 : return CPLSM(res);
169 : #elif defined(_MSC_VER)
170 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
171 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
172 : return CPLSM(static_cast<int>(A2 + B2));
173 : #elif defined(CPL_HAS_GINT64)
174 : const int a = A.v();
175 : const int b = B.v();
176 : const GInt64 res = static_cast<GInt64>(a) + b;
177 : if (res < std::numeric_limits<int>::min() ||
178 : res > std::numeric_limits<int>::max())
179 : {
180 : throw CPLSafeIntOverflow();
181 : }
182 : return CPLSM(static_cast<int>(res));
183 : #else
184 : return SafeAddSigned(A, B);
185 : #endif
186 : }
187 :
188 : #if defined(GDAL_COMPILATION)
189 102 : inline CPLSafeInt<GInt64> operator+(const CPLSafeInt<GInt64> &A,
190 : const CPLSafeInt<GInt64> &B)
191 : {
192 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
193 : GInt64 res;
194 102 : if (__builtin_saddll_overflow(A.v(), B.v(), &res))
195 2 : throw CPLSafeIntOverflow();
196 200 : return CPLSM(res);
197 : #elif defined(_MSC_VER)
198 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> A2(A.v());
199 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> B2(B.v());
200 : return CPLSM(static_cast<GInt64>(A2 + B2));
201 : #else
202 : return SafeAddSigned(A, B);
203 : #endif
204 : }
205 : #endif // GDAL_COMPILATION
206 :
207 3 : inline CPLSafeInt<unsigned> operator+(const CPLSafeInt<unsigned> &A,
208 : const CPLSafeInt<unsigned> &B)
209 : {
210 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
211 : unsigned res;
212 3 : if (__builtin_uadd_overflow(A.v(), B.v(), &res))
213 1 : throw CPLSafeIntOverflow();
214 4 : return CPLSM(res);
215 : #elif defined(_MSC_VER)
216 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
217 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
218 : return CPLSM(static_cast<unsigned>(A2 + B2));
219 : #else
220 : const unsigned a = A.v();
221 : const unsigned b = B.v();
222 : if (a > std::numeric_limits<unsigned>::max() - b)
223 : throw CPLSafeIntOverflow();
224 : return CPLSM(a + b);
225 : #endif
226 : }
227 :
228 : #if defined(GDAL_COMPILATION)
229 13093 : inline CPLSafeInt<GUInt64> operator+(const CPLSafeInt<GUInt64> &A,
230 : const CPLSafeInt<GUInt64> &B)
231 : {
232 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
233 : GUInt64 res;
234 13093 : if (__builtin_uaddll_overflow(A.v(), B.v(), &res))
235 1 : throw CPLSafeIntOverflow();
236 26184 : return CPLSM(res);
237 : #elif defined(_MSC_VER)
238 : msl::utilities::SafeInt<GUInt64, CPLMSVCSafeIntException> A2(A.v());
239 : msl::utilities::SafeInt<GUInt64, CPLMSVCSafeIntException> B2(B.v());
240 : return CPLSM(static_cast<GUInt64>(A2 + B2));
241 : #else
242 : const GUInt64 a = A.v();
243 : const GUInt64 b = B.v();
244 : if (a > std::numeric_limits<GUInt64>::max() - b)
245 : throw CPLSafeIntOverflow();
246 : return CPLSM(a + b);
247 : #endif
248 : }
249 : #endif // GDAL_COMPILATION
250 :
251 : template <class T>
252 : inline CPLSafeInt<T> SafeSubSigned(const CPLSafeInt<T> &A,
253 : const CPLSafeInt<T> &B)
254 : {
255 : const auto a = A.v();
256 : const auto b = B.v();
257 : /* caution we must catch a == 0 && b = INT_MIN */
258 : if (a >= 0 && b < 0 && a > std::numeric_limits<T>::max() + b)
259 : throw CPLSafeIntOverflow();
260 : if (a < 0 && b > 0 && a < std::numeric_limits<T>::min() + b)
261 : throw CPLSafeIntOverflow();
262 : return CPLSM(a - b);
263 : }
264 :
265 17 : inline CPLSafeInt<int> operator-(const CPLSafeInt<int> &A,
266 : const CPLSafeInt<int> &B)
267 : {
268 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
269 : int res;
270 17 : if (__builtin_ssub_overflow(A.v(), B.v(), &res))
271 3 : throw CPLSafeIntOverflow();
272 28 : return CPLSM(res);
273 : #elif defined(_MSC_VER)
274 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
275 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
276 : return CPLSM(static_cast<int>(A2 - B2));
277 : #elif defined(CPL_HAS_GINT64)
278 : const int a = A.v();
279 : const int b = B.v();
280 : const GInt64 res = static_cast<GInt64>(a) - b;
281 : if (res < std::numeric_limits<int>::min() ||
282 : res > std::numeric_limits<int>::max())
283 : {
284 : throw CPLSafeIntOverflow();
285 : }
286 : return CPLSM(static_cast<int>(res));
287 : #else
288 : return SafeSubSigned(A, B);
289 : #endif
290 : }
291 :
292 : #if defined(GDAL_COMPILATION)
293 17 : inline CPLSafeInt<GInt64> operator-(const CPLSafeInt<GInt64> &A,
294 : const CPLSafeInt<GInt64> &B)
295 : {
296 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
297 : GInt64 res;
298 17 : if (__builtin_ssubll_overflow(A.v(), B.v(), &res))
299 2 : throw CPLSafeIntOverflow();
300 30 : return CPLSM(res);
301 : #elif defined(_MSC_VER)
302 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> A2(A.v());
303 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> B2(B.v());
304 : return CPLSM(static_cast<GInt64>(A2 - B2));
305 : #else
306 : return SafeSubSigned(A, B);
307 : #endif
308 : }
309 : #endif // GDAL_COMPILATION
310 :
311 4 : inline CPLSafeInt<unsigned> operator-(const CPLSafeInt<unsigned> &A,
312 : const CPLSafeInt<unsigned> &B)
313 : {
314 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
315 : unsigned res;
316 4 : if (__builtin_usub_overflow(A.v(), B.v(), &res))
317 1 : throw CPLSafeIntOverflow();
318 6 : return CPLSM(res);
319 : #elif defined(_MSC_VER)
320 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
321 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
322 : return CPLSM(static_cast<unsigned>(A2 - B2));
323 : #else
324 : const unsigned a = A.v();
325 : const unsigned b = B.v();
326 : if (a < b)
327 : throw CPLSafeIntOverflow();
328 : return CPLSM(a - b);
329 : #endif
330 : }
331 :
332 : template <class T>
333 : inline CPLSafeInt<T> SafeMulSigned(const CPLSafeInt<T> &A,
334 : const CPLSafeInt<T> &B)
335 : {
336 : const auto a = A.v();
337 : const auto b = B.v();
338 : if (a > 0 && b > 0 && a > std::numeric_limits<T>::max() / b)
339 : throw CPLSafeIntOverflow();
340 : if (a > 0 && b < 0 && b < std::numeric_limits<T>::min() / a)
341 : throw CPLSafeIntOverflow();
342 : if (a < 0 && b > 0 && a < std::numeric_limits<T>::min() / b)
343 : throw CPLSafeIntOverflow();
344 : else if (a == std::numeric_limits<T>::min())
345 : {
346 : if (b != 0 && b != 1)
347 : throw CPLSafeIntOverflow();
348 : }
349 : else if (b == std::numeric_limits<T>::min())
350 : {
351 : if (a != 0 && a != 1)
352 : throw CPLSafeIntOverflow();
353 : }
354 : else if (a < 0 && b < 0 && -a > std::numeric_limits<T>::max() / (-b))
355 : throw CPLSafeIntOverflow();
356 :
357 : return CPLSM(a * b);
358 : }
359 :
360 378 : inline CPLSafeInt<int> operator*(const CPLSafeInt<int> &A,
361 : const CPLSafeInt<int> &B)
362 : {
363 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
364 : int res;
365 378 : if (__builtin_smul_overflow(A.v(), B.v(), &res))
366 6 : throw CPLSafeIntOverflow();
367 744 : return CPLSM(res);
368 : #elif defined(_MSC_VER)
369 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
370 : msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
371 : return CPLSM(static_cast<int>(A2 * B2));
372 : #elif defined(CPL_HAS_GINT64)
373 : const int a = A.v();
374 : const int b = B.v();
375 : const GInt64 res = static_cast<GInt64>(a) * b;
376 : if (res < std::numeric_limits<int>::min() ||
377 : res > std::numeric_limits<int>::max())
378 : {
379 : throw CPLSafeIntOverflow();
380 : }
381 : return CPLSM(static_cast<int>(res));
382 : #else
383 : return SafeMulSigned(A, B);
384 : #endif
385 : }
386 :
387 : #if defined(GDAL_COMPILATION)
388 118 : inline CPLSafeInt<GInt64> operator*(const CPLSafeInt<GInt64> &A,
389 : const CPLSafeInt<GInt64> &B)
390 : {
391 : #if defined(BUILTIN_OVERFLOW_CHECK_AVAILABLE) && defined(__x86_64__)
392 : GInt64 res;
393 118 : if (__builtin_smulll_overflow(A.v(), B.v(), &res))
394 7 : throw CPLSafeIntOverflow();
395 222 : return CPLSM(res);
396 : #elif defined(_MSC_VER)
397 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> A2(A.v());
398 : msl::utilities::SafeInt<GInt64, CPLMSVCSafeIntException> B2(B.v());
399 : return CPLSM(static_cast<GInt64>(A2 * B2));
400 : #else
401 : return SafeMulSigned(A, B);
402 : #endif
403 : }
404 : #endif // GDAL_COMPILATION
405 :
406 6 : inline CPLSafeInt<unsigned> operator*(const CPLSafeInt<unsigned> &A,
407 : const CPLSafeInt<unsigned> &B)
408 : {
409 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
410 : unsigned res;
411 6 : if (__builtin_umul_overflow(A.v(), B.v(), &res))
412 2 : throw CPLSafeIntOverflow();
413 8 : return CPLSM(res);
414 : #elif defined(_MSC_VER)
415 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
416 : msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
417 : return CPLSM(static_cast<unsigned>(A2 * B2));
418 : #elif defined(CPL_HAS_GINT64)
419 : const unsigned a = A.v();
420 : const unsigned b = B.v();
421 : const GUInt64 res = static_cast<GUInt64>(a) * b;
422 : if (res > std::numeric_limits<unsigned>::max())
423 : {
424 : throw CPLSafeIntOverflow();
425 : }
426 : return CPLSM(static_cast<unsigned>(res));
427 : #else
428 : const unsigned a = A.v();
429 : const unsigned b = B.v();
430 : if (b > 0 && a > std::numeric_limits<unsigned>::max() / b)
431 : throw CPLSafeIntOverflow();
432 : return CPLSM(a * b);
433 : #endif
434 : }
435 :
436 : #if defined(GDAL_COMPILATION)
437 20856 : inline CPLSafeInt<GUInt64> operator*(const CPLSafeInt<GUInt64> &A,
438 : const CPLSafeInt<GUInt64> &B)
439 : {
440 : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
441 : GUInt64 res;
442 20856 : if (__builtin_umulll_overflow(A.v(), B.v(), &res))
443 2 : throw CPLSafeIntOverflow();
444 41708 : return CPLSM(res);
445 : #elif defined(_MSC_VER)
446 : msl::utilities::SafeInt<GUInt64, CPLMSVCSafeIntException> A2(A.v());
447 : msl::utilities::SafeInt<GUInt64, CPLMSVCSafeIntException> B2(B.v());
448 : return CPLSM(static_cast<GUInt64>(A2 * B2));
449 : #else
450 : const GUInt64 a = A.v();
451 : const GUInt64 b = B.v();
452 : if (b > 0 && a > std::numeric_limits<GUInt64>::max() / b)
453 : throw CPLSafeIntOverflow();
454 : return CPLSM(a * b);
455 : #endif
456 : }
457 : #endif // GDAL_COMPILATION
458 :
459 : template <class T>
460 23 : inline CPLSafeInt<T> SafeDivSigned(const CPLSafeInt<T> &A,
461 : const CPLSafeInt<T> &B)
462 : {
463 23 : const auto a = A.v();
464 23 : const auto b = B.v();
465 23 : if (b == 0)
466 1 : throw CPLSafeIntOverflowDivisionByZero();
467 22 : if (a == std::numeric_limits<T>::min() && b == -1)
468 2 : throw CPLSafeIntOverflow();
469 20 : return CPLSM(a / b);
470 : }
471 :
472 12 : inline CPLSafeInt<int> operator/(const CPLSafeInt<int> &A,
473 : const CPLSafeInt<int> &B)
474 : {
475 12 : return SafeDivSigned(A, B);
476 : }
477 :
478 : #if defined(GDAL_COMPILATION)
479 11 : inline CPLSafeInt<GInt64> operator/(const CPLSafeInt<GInt64> &A,
480 : const CPLSafeInt<GInt64> &B)
481 : {
482 11 : return SafeDivSigned(A, B);
483 : }
484 : #endif // GDAL_COMPILATION
485 :
486 3 : inline CPLSafeInt<unsigned> operator/(const CPLSafeInt<unsigned> &A,
487 : const CPLSafeInt<unsigned> &B)
488 : {
489 3 : const unsigned a = A.v();
490 3 : const unsigned b = B.v();
491 3 : if (b == 0)
492 1 : throw CPLSafeIntOverflowDivisionByZero();
493 2 : return CPLSM(a / b);
494 : }
495 :
496 : #endif // CPL_SAFEMATHS_INCLUDED
|