xapian-core  1.4.22
overflow.h
Go to the documentation of this file.
1 
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 
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 
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 
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
std::enable_if< std::is_unsigned< T1 >::value &&std::is_unsigned< T2 >::value &&std::is_unsigned< R >::value, bool >::type add_overflows(T1 a, T2 b, R &res)
Addition with overflow checking.
Definition: overflow.h:58
std::enable_if< std::is_unsigned< T1 >::value &&std::is_unsigned< T2 >::value &&std::is_unsigned< R >::value, bool >::type sub_overflows(T1 a, T2 b, R &res)
Subtraction with overflow checking.
Definition: overflow.h:125
std::enable_if< std::is_unsigned< T1 >::value &&std::is_unsigned< T2 >::value &&std::is_unsigned< R >::value, bool >::type mul_overflows(T1 a, T2 b, R &res)
Multiplication with overflow checking.
Definition: overflow.h:188