xapian-core/common/overflow.h

   1 /** @file
   2  * @brief Arithmetic operations with overflow checks
   3  *
   4  * The operations are implemented with compiler builtins or equivalent where
   5  * possible, so the overflow check will typically just require a check of the
   6  * processor's overflow or carry flag.
   7  */
   8 /* Copyright (C) 2018,2022 Olly Betts
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  23  */
  24
  25 #ifndef XAPIAN_INCLUDED_OVERFLOW_H
  26 #define XAPIAN_INCLUDED_OVERFLOW_H
  27
  28 #ifndef PACKAGE
  29 # error config.h must be included first in each C++ source file
  30 #endif
  31
  32 #include <type_traits>
  33
  34 #if !HAVE_DECL___BUILTIN_ADD_OVERFLOW || !HAVE_DECL___BUILTIN_SUB_OVERFLOW
  35 # if HAVE_DECL__ADDCARRY_U32 || HAVE_DECL__ADDCARRY_U64 || \
  36      HAVE_DECL__SUBBORROW_U32 || HAVE_DECL__SUBBORROW_U64
  37 #  include <intrin.h>
  38 # endif
  39 #endif
  40
  41 /** Addition with overflow checking.
  42  *
  43  *  Add @a a and @a b in infinite precision, and store the result in
  44  *  @a res.
  45  *
  46  *  Where possible, compiler built-ins or intrinsics are used to try to ensure
  47  *  minimal overhead from the overflow check.
  48  *
  49  *  Currently only supported when types involved are unsigned.
  50  *
  51  *  @return true if the result can be represented exactly in @a res, false
  52  *          otherwise.
  53  */
  54 template<typename T1, typename T2, typename R>
  55 typename std::enable_if<std::is_unsigned<T1>::value &&
  56                         std::is_unsigned<T2>::value &&
  57                         std::is_unsigned<R>::value, bool>::type
  58 add_overflows(T1 a, T2 b, R& res) {
  59 #if HAVE_DECL___BUILTIN_ADD_OVERFLOW
  60     return __builtin_add_overflow(a, b, &res);
  61 #else
  62     // Use a local variable to test for overflow so we can use auto and get
  63     // a type which will at least hold each of the inputs, and so we don't need
  64     // to worry if res could be modified by another thread between us setting
  65     // and testing it.
  66     auto r = a + b;
  67     typedef decltype(r) r_type;
  68     res = R(r);
  69     // Overflow is only possible if the result type is the same width as or
  70     // narrower than at least one of the input types.
  71     //
  72     // We've overflowed if r doesn't fit in type R, or if the result is less
  73     // then an input.
  74     return (sizeof(R) <= sizeof(T1) || sizeof(R) <= sizeof(T2)) &&
  75            (r_type(res) != r || r < r_type(b));
  76 #endif
  77 }
  78
  79 #if !HAVE_DECL___BUILTIN_ADD_OVERFLOW
  80 // Only use the addcarry intrinsics where the builtins aren't available.
  81 // GCC and clang support both, but _addcarry_u64() uses `unsigned long
  82 // long` instead of `unsigned __int64` and the two types aren't compatible.
  83 # if HAVE_DECL__ADDCARRY_U32
  84 template<>
  85 inline bool
  86 add_overflows<unsigned,
  87               unsigned,
  88               unsigned>(unsigned a,
  89                         unsigned b,
  90                         unsigned& res) {
  91     return _addcarry_u32(0, a, b, &res) != 0;
  92 }
  93 # endif
  94
  95 # if HAVE_DECL__ADDCARRY_U64
  96 template<>
  97 inline bool
  98 add_overflows<unsigned __int64,
  99               unsigned __int64,
 100               unsigned __int64>(unsigned __int64 a,
 101                                 unsigned __int64 b,
 102                                 unsigned __int64& res) {
 103     return _addcarry_u64(0, a, b, &res) != 0;
 104 }
 105 # endif
 106 #endif
 107
 108 /** Subtraction with overflow checking.
 109  *
 110  *  Subtract @a b from @a a in infinite precision, and store the result in
 111  *  @a res.
 112  *
 113  *  Where possible, compiler built-ins or intrinsics are used to try to ensure
 114  *  minimal overhead from the overflow check.
 115  *
 116  *  Currently only supported when types involved are unsigned.
 117  *
 118  *  @return true if the result can be represented exactly in @a res, false
 119  *          otherwise.
 120  */
 121 template<typename T1, typename T2, typename R>
 122 typename std::enable_if<std::is_unsigned<T1>::value &&
 123                         std::is_unsigned<T2>::value &&
 124                         std::is_unsigned<R>::value, bool>::type
 125 sub_overflows(T1 a, T2 b, R& res) {
 126 #if HAVE_DECL___BUILTIN_ADD_OVERFLOW
 127     return __builtin_sub_overflow(a, b, &res);
 128 #else
 129     // Use a local variable to test for overflow so we can use auto and get
 130     // a type which will at least hold each of the inputs, and so we don't need
 131     // to worry if res could be modified by another thread between us setting
 132     // and testing it.
 133     auto r = a - b;
 134     typedef decltype(r) r_type;
 135     res = r_type(r);
 136     // We've overflowed if r doesn't fit in type R, or if the subtraction
 137     // wrapped.
 138     return r_type(res) != r || r > r_type(a);
 139 #endif
 140 }
 141
 142 #if !HAVE_DECL___BUILTIN_SUB_OVERFLOW
 143 // Only use the subborrow intrinsics where the builtins aren't available.
 144 // GCC and clang support both, but _subborrow_u64() uses `unsigned long
 145 // long` instead of `unsigned __int64` and the two types aren't compatible.
 146 # if HAVE_DECL__SUBBORROW_U32
 147 template<>
 148 inline bool
 149 sub_overflows<unsigned,
 150               unsigned,
 151               unsigned>(unsigned a,
 152                         unsigned b,
 153                         unsigned& res) {
 154     return _subborrow_u32(0, a, b, &res) != 0;
 155 }
 156 # endif
 157
 158 # if HAVE_DECL__SUBBORROW_U64
 159 template<>
 160 inline bool
 161 sub_overflows<unsigned __int64,
 162               unsigned __int64,
 163               unsigned __int64>(unsigned __int64 a,
 164                                 unsigned __int64 b,
 165                                 unsigned __int64& res) {
 166     return _subborrow_u64(0, a, b, &res) != 0;
 167 }
 168 # endif
 169 #endif
 170
 171 /** Multiplication with overflow checking.
 172  *
 173  *  Multiply @a a and @a b in infinite precision, and store the result in
 174  *  @a res.
 175  *
 176  *  Where possible, compiler built-ins or intrinsics are used to try to ensure
 177  *  minimal overhead from the overflow check.
 178  *
 179  *  Currently only supported when types involved are unsigned.
 180  *
 181  *  @return true if the result can be represented exactly in @a res, false
 182  *          otherwise.
 183  */
 184 template<typename T1, typename T2, typename R>
 185 typename std::enable_if<std::is_unsigned<T1>::value &&
 186                         std::is_unsigned<T2>::value &&
 187                         std::is_unsigned<R>::value, bool>::type
 188 mul_overflows(T1 a, T2 b, R& res) {
 189 #if HAVE_DECL___BUILTIN_MUL_OVERFLOW
 190     return __builtin_mul_overflow(a, b, &res);
 191 #else
 192     // Use a local variable to test for overflow so we can use auto and get
 193     // a type which will at least hold each of the inputs, and so we don't need
 194     // to worry if res could be modified by another thread between us setting
 195     // and testing it.
 196     auto r = a * b;
 197     typedef decltype(r) r_type;
 198     res = r_type(r);
 199     // We've overflowed if r doesn't fit in type R, or if the multiplication
 200     // wrapped.
 201     return r_type(res) != r || (a != 0 && r / r_type(a) != r_type(b));
 202 #endif
 203 }
 204
 205 #endif // XAPIAN_INCLUDED_OVERFLOW_H