1 // Copyright 2023 Google LLC
2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
3
4 #include "modules/bentleyottmann/include/Int96.h"
5
6 #include <cstdint>
7 #include <tuple>
8
9 namespace bentleyottmann {
10
Make(int32_t a)11 Int96 Int96::Make(int32_t a) {
12 return {a >= 0 ? 0 : -1, (uint32_t)a};
13 }
14
Make(int64_t a)15 Int96 Int96::Make(int64_t a) {
16 return {a >> 32, (uint32_t)(a & 0xFFFFFFFF)};
17 }
18
operator ==(const Int96 & a,const Int96 & b)19 bool operator== (const Int96& a, const Int96& b) {
20 return std::tie(a.hi, a.lo) == std::tie(b.hi, b.lo);
21 }
22
operator <(const Int96 & a,const Int96 & b)23 bool operator< (const Int96& a, const Int96& b) {
24 return std::tie(a.hi, a.lo) < std::tie(b.hi, b.lo);
25 }
26
operator +(const Int96 & a,const Int96 & b)27 Int96 operator+ (const Int96& a, const Int96& b) {
28 uint32_t lo = a.lo + b.lo;
29 int64_t carry = lo < a.lo;
30 int64_t hi = a.hi + b.hi + carry;
31 return {hi, lo};
32 }
33
34
35 // Multiply a 64-bit int and a 32-bit int producing a 96-bit int.
36 // This proceeds in two multiplies.
37 // 1 - unsigned multiply of the low 32-bits of a and the 32-bits of b. Using an unsigned
38 // multiply for the lower 32-bits requires a compensation if b is actually negative. The lower
39 // bits of a are subtracted from the upper 64-bits of the result.
40 // 2 - signed multiply of the upper 32-bits of a and the 32-bits of b.
multiply(int64_t a,int32_t b)41 Int96 multiply(int64_t a, int32_t b) {
42 // Multiply the low 32-bits generating a 64-bit lower part.
43 uint64_t loA = a & 0xFFFFFFFF;
44 uint64_t loB = (uint32_t)b;
45 uint64_t newLo = loA * loB;
46
47 // Multiply the upper bits 32-bits of a and b resulting in the hi 64-bits of the Int96.
48 int64_t newHi = (a >> 32) * (int64_t)b;
49
50 // Calculate the overflow into the upper 32-bits.
51 // Remember that newLo is unsigned so will be zero filled by the shift.
52 int64_t lowOverflow = newLo >> 32;
53
54 // Add overflow from the low multiply into hi.
55 newHi += lowOverflow;
56
57 // Compensate for the negative b in the calculation of newLo by subtracting out 2^32 * a.
58 if (b < 0) {
59 newHi -= loA;
60 }
61
62 return {newHi, (uint32_t)newLo};
63 }
64
multiply(int32_t a,int64_t b)65 Int96 multiply(int32_t a, int64_t b) {
66 return multiply(b, a);
67 }
68
69 } // namespace bentleyottmann
70