OR-Tools  8.2
saturated_arithmetic.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_UTIL_SATURATED_ARITHMETIC_H_
15 #define OR_TOOLS_UTIL_SATURATED_ARITHMETIC_H_
16 
17 #include "absl/base/casts.h"
19 #include "ortools/util/bitset.h"
20 
21 namespace operations_research {
22 // ---------- Overflow utility functions ----------
23 
24 // Implement two's complement addition and subtraction on int64s.
25 //
26 // The C and C++ standards specify that the overflow of signed integers is
27 // undefined. This is because of the different possible representations that may
28 // be used for signed integers (one's complement, two's complement, sign and
29 // magnitude). Such overflows are detected by Address Sanitizer with
30 // -fsanitize=signed-integer-overflow.
31 //
32 // Simple, portable overflow detection on current machines relies on
33 // these two functions. For example, if the sign of the sum of two positive
34 // integers is negative, there has been an overflow.
35 //
36 // Note that the static assert will break if the code is compiled on machines
37 // which do not use two's complement.
39  static_assert(static_cast<uint64>(-1LL) == ~0ULL,
40  "The target architecture does not use two's complement.");
41  return absl::bit_cast<int64>(static_cast<uint64>(x) + static_cast<uint64>(y));
42 }
43 
45  static_assert(static_cast<uint64>(-1LL) == ~0ULL,
46  "The target architecture does not use two's complement.");
47  return absl::bit_cast<int64>(static_cast<uint64>(x) - static_cast<uint64>(y));
48 }
49 
50 // Helper function that returns true if an overflow has occured in computing
51 // sum = x + y. sum is expected to be computed elsewhere.
52 inline bool AddHadOverflow(int64 x, int64 y, int64 sum) {
53  // Overflow cannot occur if operands have different signs.
54  // It can only occur if sign(x) == sign(y) and sign(sum) != sign(x),
55  // which is equivalent to: sign(x) != sign(sum) && sign(y) != sign(sum).
56  // This is captured when the expression below is negative.
58  return ((x ^ sum) & (y ^ sum)) < 0;
59 }
60 
61 inline bool SubHadOverflow(int64 x, int64 y, int64 diff) {
62  // This is the same reasoning as for AddHadOverflow. We have x = diff + y.
63  // The formula is the same, with 'x' and diff exchanged.
65  return AddHadOverflow(diff, y, x);
66 }
67 
68 // A note on overflow treatment.
69 // kint64min and kint64max are treated as infinity.
70 // Thus if the computation overflows, the result is always kint64m(ax/in).
71 //
72 // Note(user): this is actually wrong: when computing A-B, if A is kint64max
73 // and B is finite, then A-B won't be kint64max: overflows aren't sticky.
74 // TODO(user): consider making some operations overflow-sticky, some others
75 // not, but make an explicit choice throughout.
76 inline bool AddOverflows(int64 x, int64 y) {
77  return AddHadOverflow(x, y, TwosComplementAddition(x, y));
78 }
79 
80 inline int64 SubOverflows(int64 x, int64 y) {
81  return SubHadOverflow(x, y, TwosComplementSubtraction(x, y));
82 }
83 
84 // Performs *b += a and returns false iff the addition overflow or underflow.
85 // This function only works for typed integer type (IntType<>).
86 template <typename IntegerType>
87 bool SafeAddInto(IntegerType a, IntegerType* b) {
88  const int64 x = a.value();
89  const int64 y = b->value();
90  const int64 sum = TwosComplementAddition(x, y);
91  if (AddHadOverflow(x, y, sum)) return false;
92  *b = sum;
93  return true;
94 }
95 
96 // Returns kint64max if x >= 0 and kint64min if x < 0.
98  // return kint64max if x >= 0 or kint64max + 1 (== kint64min) if x < 0.
99  return TwosComplementAddition(kint64max, static_cast<int64>(x < 0));
100 }
101 
103  const int64 result = TwosComplementAddition(x, y);
104  return AddHadOverflow(x, y, result) ? CapWithSignOf(x) : result;
105 }
106 
107 #if defined(__GNUC__) && defined(__x86_64__)
108 // TODO(user): port this to other architectures.
109 inline int64 CapAddFast(int64 x, int64 y) {
110  const int64 cap = CapWithSignOf(x);
111  int64 result = x;
112  // clang-format off
113  asm volatile( // 'volatile': ask compiler optimizer "keep as is".
114  "\t" "addq %[y],%[result]"
115  "\n\t" "cmovoq %[cap],%[result]" // Conditional move if overflow.
116  : [result] "=r"(result) // Output
117  : "[result]" (result), [y] "r"(y), [cap] "r"(cap) // Input.
118  : "cc" /* Clobbered registers */ );
119  // clang-format on
120  return result;
121 }
122 #endif
123 
124 inline int64 CapAdd(int64 x, int64 y) {
125 #if defined(__GNUC__) && defined(__x86_64__)
126  return CapAddFast(x, y);
127 #else
128  return CapAddGeneric(x, y);
129 #endif
130 }
131 
133  const int64 result = TwosComplementSubtraction(x, y);
134  return SubHadOverflow(x, y, result) ? CapWithSignOf(x) : result;
135 }
136 
137 #if defined(__GNUC__) && defined(__x86_64__)
138 // TODO(user): port this to other architectures.
139 inline int64 CapSubFast(int64 x, int64 y) {
140  const int64 cap = CapWithSignOf(x);
141  int64 result = x;
142  // clang-format off
143  asm volatile( // 'volatile': ask compiler optimizer "keep as is".
144  "\t" "subq %[y],%[result]"
145  "\n\t" "cmovoq %[cap],%[result]" // Conditional move if overflow.
146  : [result] "=r"(result) // Output
147  : "[result]" (result), [y] "r"(y), [cap] "r"(cap) // Input.
148  : "cc" /* Clobbered registers */ );
149  // clang-format on
150  return result;
151 }
152 #endif
153 
154 inline int64 CapSub(int64 x, int64 y) {
155 #if defined(__GNUC__) && defined(__x86_64__)
156  return CapSubFast(x, y);
157 #else
158  return CapSubGeneric(x, y);
159 #endif
160 }
161 
162 // Note(user): -kint64min != kint64max, but kint64max == ~kint64min.
163 inline int64 CapOpp(int64 v) { return v == kint64min ? ~v : -v; }
164 
165 namespace cap_prod_util {
166 // Returns an unsigned int equal to the absolute value of n, in a way that
167 // will not produce overflows.
168 inline uint64 uint_abs(int64 n) {
169  return n < 0 ? ~static_cast<uint64>(n) + 1 : static_cast<uint64>(n);
170 }
171 } // namespace cap_prod_util
172 
173 // The generic algorithm computes a bound on the number of bits necessary to
174 // store the result. For this it uses the position of the most significant bits
175 // of each of the arguments.
176 // If the result needs at least 64 bits, then return a capped value.
177 // If the result needs at most 63 bits, then return the product.
178 // Otherwise, the result may use 63 or 64 bits: compute the product
179 // as a uint64, and cap it if necessary.
181  const uint64 a = cap_prod_util::uint_abs(x);
182  const uint64 b = cap_prod_util::uint_abs(y);
183  // Let MSB(x) denote the most significant bit of x. We have:
184  // MSB(x) + MSB(y) <= MSB(x * y) <= MSB(x) + MSB(y) + 1
185  const int msb_sum =
187  const int kMaxBitIndexInInt64 = 63;
188  if (msb_sum <= kMaxBitIndexInInt64 - 2) return x * y;
189  // Catch a == 0 or b == 0 now, as MostSignificantBitPosition64(0) == 0.
190  // TODO(user): avoid this by writing function Log2(a) with Log2(0) == -1.
191  if (a == 0 || b == 0) return 0;
192  const int64 cap = CapWithSignOf(x ^ y);
193  if (msb_sum >= kMaxBitIndexInInt64) return cap;
194  // The corner case is when msb_sum == 62, i.e. at least 63 bits will be
195  // needed to store the product. The following product will never overflow
196  // on uint64, since msb_sum == 62.
197  const uint64 u_prod = a * b;
198  // The overflow cases are captured by one of the following conditions:
199  // (cap >= 0 && u_prod >= static_cast<uint64>(kint64max) or
200  // (cap < 0 && u_prod >= static_cast<uint64>(kint64min)).
201  // These can be optimized as follows (and if the condition is false, it is
202  // safe to compute x * y.
203  if (u_prod >= static_cast<uint64>(cap)) return cap;
204  const int64 abs_result = absl::bit_cast<int64>(u_prod);
205  return cap < 0 ? -abs_result : abs_result;
206 }
207 
208 #if defined(__GNUC__) && defined(__x86_64__)
209 // TODO(user): port this to other architectures.
210 inline int64 CapProdFast(int64 x, int64 y) {
211  // cap = kint64max if x and y have the same sign, cap = kint64min
212  // otherwise.
213  const int64 cap = CapWithSignOf(x ^ y);
214  int64 result = x;
215  // Here, we use the fact that imul of two signed 64-integers returns a 128-bit
216  // result -- we care about the lower 64 bits. More importantly, imul also sets
217  // the carry flag if 64 bits were not enough.
218  // We therefore use cmovc to return cap if the carry was set.
219  // clang-format off
220  asm volatile( // 'volatile': ask compiler optimizer "keep as is".
221  "\n\t" "imulq %[y],%[result]"
222  "\n\t" "cmovcq %[cap],%[result]" // Conditional move if carry.
223  : [result] "=r"(result) // Output
224  : "[result]" (result), [y] "r"(y), [cap] "r"(cap) // Input.
225  : "cc" /* Clobbered registers */);
226  // clang-format on
227  return result;
228 }
229 #endif
230 
231 inline int64 CapProd(int64 x, int64 y) {
232 #if defined(__GNUC__) && defined(__x86_64__)
233  return CapProdFast(x, y);
234 #else
235  return CapProdGeneric(x, y);
236 #endif
237 }
238 } // namespace operations_research
239 
240 #endif // OR_TOOLS_UTIL_SATURATED_ARITHMETIC_H_
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
static const int64 kint64max
int64_t int64
uint64_t uint64
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapProdGeneric(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
int64 TwosComplementSubtraction(int64 x, int64 y)
int64 CapWithSignOf(int64 x)
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
int64 CapSubGeneric(int64 x, int64 y)
int64 SubOverflows(int64 x, int64 y)
bool SubHadOverflow(int64 x, int64 y, int64 diff)
int64 TwosComplementAddition(int64 x, int64 y)
int64 CapAddGeneric(int64 x, int64 y)
int64 CapAdd(int64 x, int64 y)
bool AddHadOverflow(int64 x, int64 y, int64 sum)
int64 CapProd(int64 x, int64 y)
bool SafeAddInto(IntegerType a, IntegerType *b)
bool AddOverflows(int64 x, int64 y)