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             :  * SPDX-License-Identifier: MIT
      12             :  ****************************************************************************/
      13             : 
      14             : #ifndef CPL_SAFEMATHS_INCLUDED
      15             : #define CPL_SAFEMATHS_INCLUDED
      16             : 
      17             : #include <exception>
      18             : #include <limits>
      19             : 
      20             : #include <cstdint>
      21             : 
      22             : #ifndef __has_builtin
      23             : #define __has_builtin(x) 0
      24             : #endif
      25             : 
      26             : #if (__GNUC__ >= 5 && !defined(__INTEL_COMPILER)) ||                           \
      27             :     __has_builtin(__builtin_sadd_overflow)
      28             : #define BUILTIN_OVERFLOW_CHECK_AVAILABLE
      29             : 
      30             : #elif defined(_MSC_VER)
      31             : 
      32             : #include "safeint.h"
      33             : 
      34             : #endif
      35             : 
      36             : template <typename T> struct CPLSafeInt
      37             : {
      38             :     const T val;
      39             : 
      40       88400 :     inline explicit CPLSafeInt(T valIn) : val(valIn)
      41             :     {
      42       88400 :     }
      43             : 
      44       88365 :     inline T v() const
      45             :     {
      46       88365 :         return val;
      47             :     }
      48             : };
      49             : 
      50             : class CPLSafeIntOverflow : public std::exception
      51             : {
      52             :   public:
      53          36 :     inline CPLSafeIntOverflow()
      54          36 :     {
      55          36 :     }
      56             : };
      57             : 
      58             : class CPLSafeIntOverflowDivisionByZero : public CPLSafeIntOverflow
      59             : {
      60             :   public:
      61           2 :     inline CPLSafeIntOverflowDivisionByZero()
      62           2 :     {
      63           2 :     }
      64             : };
      65             : 
      66             : /** Convenience functions to build a CPLSafeInt */
      67        1253 : inline CPLSafeInt<int> CPLSM(int x)
      68             : {
      69        1253 :     return CPLSafeInt<int>(x);
      70             : }
      71             : 
      72          43 : inline CPLSafeInt<unsigned> CPLSM(unsigned x)
      73             : {
      74          43 :     return CPLSafeInt<unsigned>(x);
      75             : }
      76             : 
      77           2 : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(int x)
      78             : {
      79           2 :     if (x < 0)
      80           1 :         throw CPLSafeIntOverflow();
      81           1 :     return CPLSafeInt<unsigned>(static_cast<unsigned>(x));
      82             : }
      83             : 
      84         611 : inline CPLSafeInt<int64_t> CPLSM(int64_t x)
      85             : {
      86         611 :     return CPLSafeInt<int64_t>(x);
      87             : }
      88             : 
      89       86492 : inline CPLSafeInt<uint64_t> CPLSM(uint64_t x)
      90             : {
      91       86492 :     return CPLSafeInt<uint64_t>(x);
      92             : }
      93             : 
      94             : // Unimplemented for now
      95             : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(unsigned x);
      96             : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(int64_t x);
      97             : inline CPLSafeInt<unsigned> CPLSM_TO_UNSIGNED(uint64_t x);
      98             : 
      99             : #if !defined(BUILTIN_OVERFLOW_CHECK_AVAILABLE) && defined(_MSC_VER)
     100             : class CPLMSVCSafeIntException : public msl::utilities::SafeIntException
     101             : {
     102             :   public:
     103             :     static void SafeIntOnOverflow()
     104             :     {
     105             :         throw CPLSafeIntOverflow();
     106             :     }
     107             : 
     108             :     static void SafeIntOnDivZero()
     109             :     {
     110             :         throw CPLSafeIntOverflowDivisionByZero();
     111             :     }
     112             : };
     113             : #endif
     114             : 
     115             : template <class T>
     116             : inline CPLSafeInt<T> SafeAddSigned(const CPLSafeInt<T> &A,
     117             :                                    const CPLSafeInt<T> &B)
     118             : {
     119             :     const auto a = A.v();
     120             :     const auto b = B.v();
     121             :     if (a > 0 && b > 0 && a > std::numeric_limits<T>::max() - b)
     122             :         throw CPLSafeIntOverflow();
     123             :     if (a < 0 && b < 0 && a < std::numeric_limits<T>::min() - b)
     124             :         throw CPLSafeIntOverflow();
     125             :     return CPLSM(a + b);
     126             : }
     127             : 
     128          50 : inline CPLSafeInt<int> operator+(const CPLSafeInt<int> &A,
     129             :                                  const CPLSafeInt<int> &B)
     130             : {
     131             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     132             :     int res;
     133          50 :     if (__builtin_sadd_overflow(A.v(), B.v(), &res))
     134           4 :         throw CPLSafeIntOverflow();
     135          92 :     return CPLSM(res);
     136             : #elif defined(_MSC_VER)
     137             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
     138             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
     139             :     return CPLSM(static_cast<int>(A2 + B2));
     140             : #else
     141             :     const int a = A.v();
     142             :     const int b = B.v();
     143             :     const int64_t res = static_cast<int64_t>(a) + b;
     144             :     if (res < std::numeric_limits<int>::min() ||
     145             :         res > std::numeric_limits<int>::max())
     146             :     {
     147             :         throw CPLSafeIntOverflow();
     148             :     }
     149             :     return CPLSM(static_cast<int>(res));
     150             : #endif
     151             : }
     152             : 
     153             : #if defined(GDAL_COMPILATION)
     154         103 : inline CPLSafeInt<int64_t> operator+(const CPLSafeInt<int64_t> &A,
     155             :                                      const CPLSafeInt<int64_t> &B)
     156             : {
     157             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     158             :     long long res;
     159         103 :     if (__builtin_saddll_overflow(A.v(), B.v(), &res))
     160           2 :         throw CPLSafeIntOverflow();
     161         202 :     return CPLSM(static_cast<int64_t>(res));
     162             : #elif defined(_MSC_VER)
     163             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> A2(A.v());
     164             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> B2(B.v());
     165             :     return CPLSM(static_cast<int64_t>(A2 + B2));
     166             : #else
     167             :     return SafeAddSigned(A, B);
     168             : #endif
     169             : }
     170             : #endif  // GDAL_COMPILATION
     171             : 
     172           3 : inline CPLSafeInt<unsigned> operator+(const CPLSafeInt<unsigned> &A,
     173             :                                       const CPLSafeInt<unsigned> &B)
     174             : {
     175             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     176             :     unsigned res;
     177           3 :     if (__builtin_uadd_overflow(A.v(), B.v(), &res))
     178           1 :         throw CPLSafeIntOverflow();
     179           4 :     return CPLSM(res);
     180             : #elif defined(_MSC_VER)
     181             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
     182             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
     183             :     return CPLSM(static_cast<unsigned>(A2 + B2));
     184             : #else
     185             :     const unsigned a = A.v();
     186             :     const unsigned b = B.v();
     187             :     if (a > std::numeric_limits<unsigned>::max() - b)
     188             :         throw CPLSafeIntOverflow();
     189             :     return CPLSM(a + b);
     190             : #endif
     191             : }
     192             : 
     193             : #if defined(GDAL_COMPILATION)
     194       13516 : inline CPLSafeInt<uint64_t> operator+(const CPLSafeInt<uint64_t> &A,
     195             :                                       const CPLSafeInt<uint64_t> &B)
     196             : {
     197             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     198             :     unsigned long long res;
     199       13516 :     if (__builtin_uaddll_overflow(A.v(), B.v(), &res))
     200           1 :         throw CPLSafeIntOverflow();
     201       27030 :     return CPLSM(static_cast<uint64_t>(res));
     202             : #elif defined(_MSC_VER)
     203             :     msl::utilities::SafeInt<uint64_t, CPLMSVCSafeIntException> A2(A.v());
     204             :     msl::utilities::SafeInt<uint64_t, CPLMSVCSafeIntException> B2(B.v());
     205             :     return CPLSM(static_cast<uint64_t>(A2 + B2));
     206             : #else
     207             :     const uint64_t a = A.v();
     208             :     const uint64_t b = B.v();
     209             :     if (a > std::numeric_limits<uint64_t>::max() - b)
     210             :         throw CPLSafeIntOverflow();
     211             :     return CPLSM(a + b);
     212             : #endif
     213             : }
     214             : #endif  // GDAL_COMPILATION
     215             : 
     216             : template <class T>
     217             : inline CPLSafeInt<T> SafeSubSigned(const CPLSafeInt<T> &A,
     218             :                                    const CPLSafeInt<T> &B)
     219             : {
     220             :     const auto a = A.v();
     221             :     const auto b = B.v();
     222             :     /* caution we must catch a == 0 && b = INT_MIN */
     223             :     if (a >= 0 && b < 0 && a > std::numeric_limits<T>::max() + b)
     224             :         throw CPLSafeIntOverflow();
     225             :     if (a < 0 && b > 0 && a < std::numeric_limits<T>::min() + b)
     226             :         throw CPLSafeIntOverflow();
     227             :     return CPLSM(a - b);
     228             : }
     229             : 
     230          17 : inline CPLSafeInt<int> operator-(const CPLSafeInt<int> &A,
     231             :                                  const CPLSafeInt<int> &B)
     232             : {
     233             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     234             :     int res;
     235          17 :     if (__builtin_ssub_overflow(A.v(), B.v(), &res))
     236           3 :         throw CPLSafeIntOverflow();
     237          28 :     return CPLSM(res);
     238             : #elif defined(_MSC_VER)
     239             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
     240             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
     241             :     return CPLSM(static_cast<int>(A2 - B2));
     242             : #else
     243             :     const int a = A.v();
     244             :     const int b = B.v();
     245             :     const int64_t res = static_cast<int64_t>(a) - b;
     246             :     if (res < std::numeric_limits<int>::min() ||
     247             :         res > std::numeric_limits<int>::max())
     248             :     {
     249             :         throw CPLSafeIntOverflow();
     250             :     }
     251             :     return CPLSM(static_cast<int>(res));
     252             : #endif
     253             : }
     254             : 
     255          17 : inline CPLSafeInt<int64_t> operator-(const CPLSafeInt<int64_t> &A,
     256             :                                      const CPLSafeInt<int64_t> &B)
     257             : {
     258             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     259             :     long long res;
     260          17 :     if (__builtin_ssubll_overflow(A.v(), B.v(), &res))
     261           2 :         throw CPLSafeIntOverflow();
     262          30 :     return CPLSM(static_cast<int64_t>(res));
     263             : #elif defined(_MSC_VER)
     264             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> A2(A.v());
     265             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> B2(B.v());
     266             :     return CPLSM(static_cast<int64_t>(A2 - B2));
     267             : #else
     268             :     return SafeSubSigned(A, B);
     269             : #endif
     270             : }
     271             : 
     272           4 : inline CPLSafeInt<unsigned> operator-(const CPLSafeInt<unsigned> &A,
     273             :                                       const CPLSafeInt<unsigned> &B)
     274             : {
     275             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     276             :     unsigned res;
     277           4 :     if (__builtin_usub_overflow(A.v(), B.v(), &res))
     278           1 :         throw CPLSafeIntOverflow();
     279           6 :     return CPLSM(res);
     280             : #elif defined(_MSC_VER)
     281             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
     282             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
     283             :     return CPLSM(static_cast<unsigned>(A2 - B2));
     284             : #else
     285             :     const unsigned a = A.v();
     286             :     const unsigned b = B.v();
     287             :     if (a < b)
     288             :         throw CPLSafeIntOverflow();
     289             :     return CPLSM(a - b);
     290             : #endif
     291             : }
     292             : 
     293             : template <class T>
     294             : inline CPLSafeInt<T> SafeMulSigned(const CPLSafeInt<T> &A,
     295             :                                    const CPLSafeInt<T> &B)
     296             : {
     297             :     const auto a = A.v();
     298             :     const auto b = B.v();
     299             :     if (a > 0 && b > 0 && a > std::numeric_limits<T>::max() / b)
     300             :         throw CPLSafeIntOverflow();
     301             :     if (a > 0 && b < 0 && b < std::numeric_limits<T>::min() / a)
     302             :         throw CPLSafeIntOverflow();
     303             :     if (a < 0 && b > 0 && a < std::numeric_limits<T>::min() / b)
     304             :         throw CPLSafeIntOverflow();
     305             :     else if (a == std::numeric_limits<T>::min())
     306             :     {
     307             :         if (b != 0 && b != 1)
     308             :             throw CPLSafeIntOverflow();
     309             :     }
     310             :     else if (b == std::numeric_limits<T>::min())
     311             :     {
     312             :         if (a != 0 && a != 1)
     313             :             throw CPLSafeIntOverflow();
     314             :     }
     315             :     else if (a < 0 && b < 0 && -a > std::numeric_limits<T>::max() / (-b))
     316             :         throw CPLSafeIntOverflow();
     317             : 
     318             :     return CPLSM(a * b);
     319             : }
     320             : 
     321         378 : inline CPLSafeInt<int> operator*(const CPLSafeInt<int> &A,
     322             :                                  const CPLSafeInt<int> &B)
     323             : {
     324             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     325             :     int res;
     326         378 :     if (__builtin_smul_overflow(A.v(), B.v(), &res))
     327           6 :         throw CPLSafeIntOverflow();
     328         744 :     return CPLSM(res);
     329             : #elif defined(_MSC_VER)
     330             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> A2(A.v());
     331             :     msl::utilities::SafeInt<int, CPLMSVCSafeIntException> B2(B.v());
     332             :     return CPLSM(static_cast<int>(A2 * B2));
     333             : #else
     334             :     const int a = A.v();
     335             :     const int b = B.v();
     336             :     const int64_t res = static_cast<int64_t>(a) * b;
     337             :     if (res < std::numeric_limits<int>::min() ||
     338             :         res > std::numeric_limits<int>::max())
     339             :     {
     340             :         throw CPLSafeIntOverflow();
     341             :     }
     342             :     return CPLSM(static_cast<int>(res));
     343             : #endif
     344             : }
     345             : 
     346         118 : inline CPLSafeInt<int64_t> operator*(const CPLSafeInt<int64_t> &A,
     347             :                                      const CPLSafeInt<int64_t> &B)
     348             : {
     349             : #if defined(BUILTIN_OVERFLOW_CHECK_AVAILABLE) && defined(__x86_64__)
     350             :     long long res;
     351         118 :     if (__builtin_smulll_overflow(A.v(), B.v(), &res))
     352           7 :         throw CPLSafeIntOverflow();
     353         222 :     return CPLSM(static_cast<int64_t>(res));
     354             : #elif defined(_MSC_VER)
     355             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> A2(A.v());
     356             :     msl::utilities::SafeInt<int64_t, CPLMSVCSafeIntException> B2(B.v());
     357             :     return CPLSM(static_cast<int64_t>(A2 * B2));
     358             : #else
     359             :     return SafeMulSigned(A, B);
     360             : #endif
     361             : }
     362             : 
     363           6 : inline CPLSafeInt<unsigned> operator*(const CPLSafeInt<unsigned> &A,
     364             :                                       const CPLSafeInt<unsigned> &B)
     365             : {
     366             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     367             :     unsigned res;
     368           6 :     if (__builtin_umul_overflow(A.v(), B.v(), &res))
     369           2 :         throw CPLSafeIntOverflow();
     370           8 :     return CPLSM(res);
     371             : #elif defined(_MSC_VER)
     372             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> A2(A.v());
     373             :     msl::utilities::SafeInt<unsigned, CPLMSVCSafeIntException> B2(B.v());
     374             :     return CPLSM(static_cast<unsigned>(A2 * B2));
     375             : #else
     376             :     const unsigned a = A.v();
     377             :     const unsigned b = B.v();
     378             :     const uint64_t res = static_cast<uint64_t>(a) * b;
     379             :     if (res > std::numeric_limits<unsigned>::max())
     380             :     {
     381             :         throw CPLSafeIntOverflow();
     382             :     }
     383             :     return CPLSM(static_cast<unsigned>(res));
     384             : #endif
     385             : }
     386             : 
     387       21553 : inline CPLSafeInt<uint64_t> operator*(const CPLSafeInt<uint64_t> &A,
     388             :                                       const CPLSafeInt<uint64_t> &B)
     389             : {
     390             : #ifdef BUILTIN_OVERFLOW_CHECK_AVAILABLE
     391             :     unsigned long long res;
     392       21553 :     if (__builtin_umulll_overflow(A.v(), B.v(), &res))
     393           2 :         throw CPLSafeIntOverflow();
     394       43102 :     return CPLSM(static_cast<uint64_t>(res));
     395             : #elif defined(_MSC_VER)
     396             :     msl::utilities::SafeInt<uint64_t, CPLMSVCSafeIntException> A2(A.v());
     397             :     msl::utilities::SafeInt<uint64_t, CPLMSVCSafeIntException> B2(B.v());
     398             :     return CPLSM(static_cast<uint64_t>(A2 * B2));
     399             : #else
     400             :     const uint64_t a = A.v();
     401             :     const uint64_t b = B.v();
     402             :     if (b > 0 && a > std::numeric_limits<uint64_t>::max() / b)
     403             :         throw CPLSafeIntOverflow();
     404             :     return CPLSM(a * b);
     405             : #endif
     406             : }
     407             : 
     408             : template <class T>
     409          23 : inline CPLSafeInt<T> SafeDivSigned(const CPLSafeInt<T> &A,
     410             :                                    const CPLSafeInt<T> &B)
     411             : {
     412          23 :     const auto a = A.v();
     413          23 :     const auto b = B.v();
     414          23 :     if (b == 0)
     415           1 :         throw CPLSafeIntOverflowDivisionByZero();
     416          22 :     if (a == std::numeric_limits<T>::min() && b == -1)
     417           2 :         throw CPLSafeIntOverflow();
     418          20 :     return CPLSM(a / b);
     419             : }
     420             : 
     421          12 : inline CPLSafeInt<int> operator/(const CPLSafeInt<int> &A,
     422             :                                  const CPLSafeInt<int> &B)
     423             : {
     424          12 :     return SafeDivSigned(A, B);
     425             : }
     426             : 
     427          11 : inline CPLSafeInt<int64_t> operator/(const CPLSafeInt<int64_t> &A,
     428             :                                      const CPLSafeInt<int64_t> &B)
     429             : {
     430          11 :     return SafeDivSigned(A, B);
     431             : }
     432             : 
     433           3 : inline CPLSafeInt<unsigned> operator/(const CPLSafeInt<unsigned> &A,
     434             :                                       const CPLSafeInt<unsigned> &B)
     435             : {
     436           3 :     const unsigned a = A.v();
     437           3 :     const unsigned b = B.v();
     438           3 :     if (b == 0)
     439           1 :         throw CPLSafeIntOverflowDivisionByZero();
     440           2 :     return CPLSM(a / b);
     441             : }
     442             : 
     443             : #endif  // CPL_SAFEMATHS_INCLUDED