OR-Tools  8.1
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_
integral_types.h
operations_research::CapSub
int64 CapSub(int64 x, int64 y)
Definition: saturated_arithmetic.h:154
operations_research::AddHadOverflow
bool AddHadOverflow(int64 x, int64 y, int64 sum)
Definition: saturated_arithmetic.h:52
operations_research::CapProd
int64 CapProd(int64 x, int64 y)
Definition: saturated_arithmetic.h:231
operations_research::CapOpp
int64 CapOpp(int64 v)
Definition: saturated_arithmetic.h:163
operations_research::SafeAddInto
bool SafeAddInto(IntegerType a, IntegerType *b)
Definition: saturated_arithmetic.h:87
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
kint64min
static const int64 kint64min
Definition: integral_types.h:60
operations_research::SubOverflows
int64 SubOverflows(int64 x, int64 y)
Definition: saturated_arithmetic.h:80
int64
int64_t int64
Definition: integral_types.h:34
operations_research::TwosComplementAddition
int64 TwosComplementAddition(int64 x, int64 y)
Definition: saturated_arithmetic.h:38
a
int64 a
Definition: constraint_solver/table.cc:42
operations_research::CapAdd
int64 CapAdd(int64 x, int64 y)
Definition: saturated_arithmetic.h:124
operations_research::CapProdGeneric
int64 CapProdGeneric(int64 x, int64 y)
Definition: saturated_arithmetic.h:180
uint64
uint64_t uint64
Definition: integral_types.h:39
operations_research::MostSignificantBitPosition64
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
operations_research::CapAddGeneric
int64 CapAddGeneric(int64 x, int64 y)
Definition: saturated_arithmetic.h:102
operations_research::CapWithSignOf
int64 CapWithSignOf(int64 x)
Definition: saturated_arithmetic.h:97
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::CapSubGeneric
int64 CapSubGeneric(int64 x, int64 y)
Definition: saturated_arithmetic.h:132
operations_research::TwosComplementSubtraction
int64 TwosComplementSubtraction(int64 x, int64 y)
Definition: saturated_arithmetic.h:44
operations_research::AddOverflows
bool AddOverflows(int64 x, int64 y)
Definition: saturated_arithmetic.h:76
operations_research::cap_prod_util::uint_abs
uint64 uint_abs(int64 n)
Definition: saturated_arithmetic.h:168
operations_research::SubHadOverflow
bool SubHadOverflow(int64 x, int64 y, int64 diff)
Definition: saturated_arithmetic.h:61
bitset.h
kint64max
static const int64 kint64max
Definition: integral_types.h:62