14#ifndef OR_TOOLS_UTIL_SATURATED_ARITHMETIC_H_
15#define OR_TOOLS_UTIL_SATURATED_ARITHMETIC_H_
17#include "absl/base/casts.h"
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));
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));
58 return ((x ^ sum) & (y ^ sum)) < 0;
86template <
typename IntegerType>
89 const int64 y =
b->value();
107#if defined(__GNUC__) && defined(__x86_64__)
114 "\t" "addq %[y],%[result]"
115 "\n\t" "cmovoq %[cap],%[result]"
116 : [result]
"=r"(result)
117 :
"[result]" (result), [y]
"r"(y), [cap]
"r"(cap)
125#if defined(__GNUC__) && defined(__x86_64__)
126 return CapAddFast(x, y);
137#if defined(__GNUC__) && defined(__x86_64__)
144 "\t" "subq %[y],%[result]"
145 "\n\t" "cmovoq %[cap],%[result]"
146 : [result]
"=r"(result)
147 :
"[result]" (result), [y]
"r"(y), [cap]
"r"(cap)
155#if defined(__GNUC__) && defined(__x86_64__)
156 return CapSubFast(x, y);
165namespace cap_prod_util {
169 return n < 0 ? ~static_cast<uint64>(n) + 1 :
static_cast<uint64>(n);
187 const int kMaxBitIndexInInt64 = 63;
188 if (msb_sum <= kMaxBitIndexInInt64 - 2)
return x * y;
191 if (
a == 0 ||
b == 0)
return 0;
193 if (msb_sum >= kMaxBitIndexInInt64)
return cap;
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;
208#if defined(__GNUC__) && defined(__x86_64__)
221 "\n\t" "imulq %[y],%[result]"
222 "\n\t" "cmovcq %[cap],%[result]"
223 : [result]
"=r"(result)
224 :
"[result]" (result), [y]
"r"(y), [cap]
"r"(cap)
232#if defined(__GNUC__) && defined(__x86_64__)
233 return CapProdFast(x, y);
#define DCHECK_EQ(val1, val2)
static const int64 kint64max
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)
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)