Google OR-Tools: ortools/util/saturated

Google OR-Tools: ortools/util/saturated_arithmetic.h Source File

14#ifndef ORTOOLS_UTIL_SATURATED_ARITHMETIC_H_

15#define ORTOOLS_UTIL_SATURATED_ARITHMETIC_H_

17#include <cstdint>

18#include <limits>

19#include <type_traits>

21#include "absl/base/casts.h"

22#include "absl/log/check.h"

54 return x == std::numeric_limits<int64_t>::min() ||

55 x == std::numeric_limits<int64_t>::max();

56}

59inline int64_t CapOpp(int64_t v) { return v == kint64min ? ~v : -v; }

61inline int64_t CapAbs(int64_t v) {

62 return v == kint64min ? std::numeric_limits<int64_t>::max()

63 : (v < 0 ? -v : v);

64}

83 static_assert(static_cast<uint64_t>(-1LL) == ~0ULL,

84 "The target architecture does not use two's complement.");

85 return absl::bit_cast<int64_t>(static_cast<uint64_t>(x) +

86 static_cast<uint64_t>(y));

87}

90 static_assert(static_cast<uint64_t>(-1LL) == ~0ULL,

91 "The target architecture does not use two's complement.");

92 return absl::bit_cast<int64_t>(static_cast<uint64_t>(x) -

93 static_cast<uint64_t>(y));

94}

98inline bool AddHadOverflow(int64_t x, int64_t y, int64_t sum) {

100

101

102

104 return ((x ^ sum) & (y ^ sum)) < 0;

105}

106

113

114

115

116

117

118

119

120

121

125

129

130

131

132template <typename IntegerType>

134 const int64_t x = a.value();

135 const int64_t y = b->value();

138 *b = sum;

139 return true;

140}

141

142

147

148

149

150

151

152#if defined(__GNUC__) && !defined(__clang_) && defined(__x86_64__)

153inline int64_t CapAddAsm(int64_t x, int64_t y) {

155 int64_t result = x;

156

157 asm volatile(

158 "\t" "addq %[y],%[result]"

159 "\n\t" "cmovoq %[cap],%[result]"

160 : [result] "=r"(result)

161 : "[result]" (result), [y] "r"(y), [cap] "r"(cap)

162 : "cc" );

163

164 return result;

165}

166

167inline int64_t CapSubAsm(int64_t x, int64_t y) {

169 int64_t result = x;

170

171 asm volatile(

172 "\t" "subq %[y],%[result]"

173 "\n\t" "cmovoq %[cap],%[result]"

174 : [result] "=r"(result)

175 : "[result]" (result), [y] "r"(y), [cap] "r"(cap)

176 : "cc" );

177

178 return result;

179}

180

181

182

183inline int64_t CapProdAsm(int64_t x, int64_t y) {

184

185

187 int64_t result = x;

188

189

190

191

192

193 asm volatile(

194 "\n\t" "imulq %[y],%[result]"

195 "\n\t" "cmovcq %[cap],%[result]"

196 : [result] "=r"(result)

197 : "[result]" (result), [y] "r"(y), [cap] "r"(cap)

198 : "cc" );

199

200 return result;

201}

202#endif

203

204

205

206

207#if defined(__clang__)

208inline int64_t CapAddBuiltIn(int64_t x, int64_t y) {

210 int64_t result;

211 const bool overflowed = __builtin_add_overflow(x, y, &result);

212 return overflowed ? cap : result;

213}

214

215inline int64_t CapSubBuiltIn(int64_t x, int64_t y) {

217 int64_t result;

218 const bool overflowed = __builtin_sub_overflow(x, y, &result);

219 return overflowed ? cap : result;

220}

221

222

223inline int64_t CapProdBuiltIn(int64_t x, int64_t y) {

225 int64_t result;

226 const bool overflowed = __builtin_mul_overflow(x, y, &result);

227 return overflowed ? cap : result;

228}

229#endif

230

231

232

237

242

244

245

247 return n < 0 ? ~static_cast<uint64_t>(n) + 1 : static_cast<uint64_t>(n);

248}

249}

250

251

252

253

254

255

256

257

261

262

263 const int msb_sum =

265 const int kMaxBitIndexInInt64 = 63;

266 if (msb_sum <= kMaxBitIndexInInt64 - 2) return x * y;

267

268

269 if (a == 0 || b == 0) return 0;

271 if (msb_sum >= kMaxBitIndexInInt64) return cap;

272

273

274

275 const uint64_t u_prod = a * b;

276

277

278

279

280

281 if (u_prod >= static_cast<uint64_t>(cap)) return cap;

282 const int64_t abs_result = absl::bit_cast<int64_t>(u_prod);

283 return cap < 0 ? -abs_result : abs_result;

284}

285

286

287

288

289template <typename T>

291

292inline int64_t CapAdd(int64_t x, int64_t y) {

293#if defined(__GNUC__) && !defined(__clang__) && defined(__x86_64__)

294 return CapAddAsm(x, y);

295#elif defined(__clang__)

296 return CapAddBuiltIn(x, y);

297#else

299#endif

300}

301

302

303

305#if defined(__clang__)

306 return __builtin_add_overflow(x, *y, y);

307#else

310 *y = result;

311 return false;

312#endif

313}

314

315inline void CapAddTo(int64_t x, int64_t* y) { *y = CapAdd(*y, x); }

316

317inline int64_t CapSub(int64_t x, int64_t y) {

318#if defined(__GNUC__) && !defined(__clang__) && defined(__x86_64__)

319 return CapSubAsm(x, y);

320#elif defined(__clang__)

321 return CapSubBuiltIn(x, y);

322#else

324#endif

325}

326

327

328inline void CapSubFrom(int64_t amount, int64_t* target) {

329 *target = CapSub(*target, amount);

330}

331

332inline int64_t CapProd(int64_t x, int64_t y) {

333#if defined(__GNUC__) && defined(__x86_64__)

334

335

336

337

338 return CapProdAsm(x, y);

339#elif defined(__clang__)

340 return CapProdBuiltIn(x, y);

341#else

343#endif

344}

345

346template <typename T>

348 static_assert(std::is_floating_point_v<T> || std::is_integral_v<T>);

349 if constexpr (std::is_integral_v<T>) {

350 if constexpr (std::is_same_v<T, int64_t>) {

352 } else {

353 static_assert(

354 std::is_same_v<T, int32_t>,

355 "CapOrFloatAdd() on integers only works for int and int64_t");

356 const int64_t sum = int64_t{x} + y;

358 }

359 } else {

360 return x + y;

361 }

362}

363

364}

365

366#endif

uint64_t uint_abs(int64_t n)

Definition saturated_arithmetic.h:246

int64_t SubOverflows(int64_t x, int64_t y)

Definition saturated_arithmetic.h:126

bool AtMinOrMaxInt64(int64_t x)

Definition saturated_arithmetic.h:53

bool AddHadOverflow(int64_t x, int64_t y, int64_t sum)

Definition saturated_arithmetic.h:98

int64_t CapAdd(int64_t x, int64_t y)

Definition saturated_arithmetic.h:292

void CapAddTo(int64_t x, int64_t *y)

Definition saturated_arithmetic.h:315

int64_t CapWithSignOf(int64_t x)

Definition saturated_arithmetic.h:143

int64_t TwosComplementAddition(int64_t x, int64_t y)

Definition saturated_arithmetic.h:82

int64_t CapSub(int64_t x, int64_t y)

Definition saturated_arithmetic.h:317

void CapSubFrom(int64_t amount, int64_t *target)

Definition saturated_arithmetic.h:328

bool AddIntoOverflow(int64_t x, int64_t *y)

Definition saturated_arithmetic.h:304

int64_t CapAddGeneric(int64_t x, int64_t y)

Definition saturated_arithmetic.h:233

T CapOrFloatAdd(T x, T y)

Definition saturated_arithmetic.h:347

bool AddOverflows(int64_t x, int64_t y)

Definition saturated_arithmetic.h:122

int64_t CapProd(int64_t x, int64_t y)

Definition saturated_arithmetic.h:332

bool SubHadOverflow(int64_t x, int64_t y, int64_t diff)

Definition saturated_arithmetic.h:107

int64_t TwosComplementSubtraction(int64_t x, int64_t y)

Definition saturated_arithmetic.h:89

int64_t CapAbs(int64_t v)

Definition saturated_arithmetic.h:61

int64_t CapProdGeneric(int64_t x, int64_t y)

Definition saturated_arithmetic.h:258

bool SafeAddInto(IntegerType a, IntegerType *b)

Definition saturated_arithmetic.h:133

int64_t CapSubGeneric(int64_t x, int64_t y)

Definition saturated_arithmetic.h:238

int64_t CapOpp(int64_t v)

Definition saturated_arithmetic.h:59

int MostSignificantBitPosition64(uint64_t n)

static const int32_t kint32min

static const int64_t kint64max

static const int32_t kint32max

static const int64_t kint64min