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
21namespace 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.
52inline 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
61inline 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.
76inline bool AddOverflows(int64 x, int64 y) {
77 return AddHadOverflow(x, y, TwosComplementAddition(x, y));
78}
79
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<>).
86template <typename IntegerType>
87bool 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.
109inline 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
124inline 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.
139inline 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
154inline 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.
163inline int64 CapOpp(int64 v) { return v == kint64min ? ~v : -v; }
164
165namespace cap_prod_util {
166// Returns an unsigned int equal to the absolute value of n, in a way that
167// will not produce overflows.
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.
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.
210inline 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
231inline 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 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
int64 TwosComplementSubtraction(int64 x, int64 y)
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
bool SubHadOverflow(int64 x, int64 y, int64 diff)
bool AddOverflows(int64 x, int64 y)
bool SafeAddInto(IntegerType a, IntegerType *b)
int64 CapProdGeneric(int64 x, int64 y)
int64 TwosComplementAddition(int64 x, int64 y)
bool AddHadOverflow(int64 x, int64 y, int64 sum)
int64 CapSubGeneric(int64 x, int64 y)
int64 CapAddGeneric(int64 x, int64 y)
int64 SubOverflows(int64 x, int64 y)
int64 CapWithSignOf(int64 x)