1 | // Copyright 2004 Google Inc. |
2 | // All Rights Reserved. |
3 | // |
4 | |
5 | #ifndef BASE_INT128_H_ |
6 | #define BASE_INT128_H_ |
7 | |
8 | #include <iostream> |
9 | using std::ostream; |
10 | using std::cout; |
11 | using std::endl; |
12 | |
13 | #include "base/integral_types.h" |
14 | #include "base/logging.h" |
15 | |
16 | // An unsigned 128-bit integer type. Thread-compatible. |
17 | class uint128 { |
18 | public: |
19 | uint128(); // Sets to 0, but don't trust on this behavior. |
20 | uint128(uint64 top, uint64 bottom); |
21 | #ifndef SWIG |
22 | uint128(int bottom); |
23 | uint128(uint32 bottom); // Top 96 bits = 0 |
24 | #endif |
25 | uint128(uint64 bottom); // hi_ = 0 |
26 | uint128(const uint128 &val); |
27 | |
28 | void Initialize(uint64 top, uint64 bottom); |
29 | |
30 | bool operator==(const uint128& b) const; |
31 | bool operator!=(const uint128& b) const; |
32 | uint128& operator=(const uint128& b); |
33 | |
34 | bool operator<(const uint128& b) const; |
35 | bool operator>(const uint128& b) const; |
36 | bool operator<=(const uint128& b) const; |
37 | bool operator>=(const uint128& b) const; |
38 | |
39 | // Logical operators. |
40 | uint128 operator~() const; |
41 | uint128 operator|(const uint128& b) const; |
42 | uint128 operator&(const uint128& b) const; |
43 | uint128 operator^(const uint128& b) const; |
44 | |
45 | // Shift operators. |
46 | uint128 operator<<(int amount) const; |
47 | uint128 operator>>(int amount) const; |
48 | |
49 | // Arithmetic operators. |
50 | // TODO: multiplication, division, etc. |
51 | uint128 operator+(const uint128& b) const; |
52 | uint128 operator-(const uint128& b) const; |
53 | uint128 operator+=(const uint128& b); |
54 | uint128 operator-=(const uint128& b); |
55 | uint128 operator++(int); |
56 | uint128 operator--(int); |
57 | uint128 operator++(); |
58 | uint128 operator--(); |
59 | |
60 | friend uint64 Uint128Low64(const uint128& v); |
61 | friend uint64 Uint128High64(const uint128& v); |
62 | |
63 | friend ostream& operator<<(ostream& o, const uint128& b); |
64 | |
65 | private: |
66 | // Little-endian memory order optimizations can benefit from |
67 | // having lo_ first, hi_ last. |
68 | // See util/endian/endian.h and Load128/Store128 for storing a uint128. |
69 | uint64 lo_; |
70 | uint64 hi_; |
71 | |
72 | // Not implemented, just declared for catching automatic type conversions. |
73 | uint128(uint8); |
74 | uint128(uint16); |
75 | uint128(float v); |
76 | uint128(double v); |
77 | }; |
78 | |
79 | extern const uint128 kuint128max; |
80 | |
81 | // allow uint128 to be logged |
82 | extern ostream& operator<<(ostream& o, const uint128& b); |
83 | |
84 | // Methods to access low and high pieces of 128-bit value. |
85 | // Defined externally from uint128 to facilitate conversion |
86 | // to native 128-bit types when compilers support them. |
87 | inline uint64 Uint128Low64(const uint128& v) { return v.lo_; } |
88 | inline uint64 Uint128High64(const uint128& v) { return v.hi_; } |
89 | |
90 | // TODO: perhaps it would be nice to have int128, a signed 128-bit type? |
91 | |
92 | // -------------------------------------------------------------------------- |
93 | // Implementation details follow |
94 | // -------------------------------------------------------------------------- |
95 | inline bool uint128::operator==(const uint128& b) const { |
96 | return (lo_ == b.lo_) && (hi_ == b.hi_); |
97 | } |
98 | inline bool uint128::operator!=(const uint128& b) const { |
99 | return !(*this == b); |
100 | } |
101 | inline uint128& uint128::operator=(const uint128& b) { |
102 | lo_ = b.lo_; |
103 | hi_ = b.hi_; |
104 | return *this; |
105 | } |
106 | |
107 | inline uint128::uint128(): lo_(0), hi_(0) { } |
108 | inline uint128::uint128(uint64 top, uint64 bottom) : lo_(bottom), hi_(top) { } |
109 | inline uint128::uint128(const uint128 &v) : lo_(v.lo_), hi_(v.hi_) { } |
110 | inline uint128::uint128(uint64 bottom) : lo_(bottom), hi_(0) { } |
111 | #ifndef SWIG |
112 | inline uint128::uint128(uint32 bottom) : lo_(bottom), hi_(0) { } |
113 | inline uint128::uint128(int bottom) : lo_(bottom), hi_(0) { |
114 | if (bottom < 0) { |
115 | --hi_; |
116 | } |
117 | } |
118 | #endif |
119 | inline void uint128::Initialize(uint64 top, uint64 bottom) { |
120 | hi_ = top; |
121 | lo_ = bottom; |
122 | } |
123 | |
124 | // Comparison operators. |
125 | |
126 | #define CMP128(op) \ |
127 | inline bool uint128::operator op(const uint128& b) const { \ |
128 | return (hi_ == b.hi_) ? (lo_ op b.lo_) : (hi_ op b.hi_); \ |
129 | } |
130 | |
131 | CMP128(<) |
132 | CMP128(>) |
133 | CMP128(>=) |
134 | CMP128(<=) |
135 | |
136 | #undef CMP128 |
137 | |
138 | // Logical operators. |
139 | |
140 | inline uint128 uint128::operator~() const { |
141 | return uint128(~hi_, ~lo_); |
142 | } |
143 | |
144 | #define LOGIC128(op) \ |
145 | inline uint128 uint128::operator op(const uint128& b) const { \ |
146 | return uint128(hi_ op b.hi_, lo_ op b.lo_); \ |
147 | } |
148 | |
149 | LOGIC128(|) |
150 | LOGIC128(&) |
151 | LOGIC128(^) |
152 | |
153 | #undef LOGIC128 |
154 | |
155 | // Shift operators. |
156 | |
157 | inline uint128 uint128::operator<<(int amount) const { |
158 | DCHECK_GE(amount, 0); |
159 | |
160 | // uint64 shifts of >= 64 are undefined, so we will need some special-casing. |
161 | if (amount < 64) { |
162 | if (amount == 0) { |
163 | return *this; |
164 | } |
165 | uint64 new_hi = (hi_ << amount) | (lo_ >> (64 - amount)); |
166 | uint64 new_lo = lo_ << amount; |
167 | return uint128(new_hi, new_lo); |
168 | } else if (amount < 128) { |
169 | return uint128(lo_ << (amount - 64), 0); |
170 | } else { |
171 | return uint128(0, 0); |
172 | } |
173 | } |
174 | |
175 | inline uint128 uint128::operator>>(int amount) const { |
176 | DCHECK_GE(amount, 0); |
177 | |
178 | // uint64 shifts of >= 64 are undefined, so we will need some special-casing. |
179 | if (amount < 64) { |
180 | if (amount == 0) { |
181 | return *this; |
182 | } |
183 | uint64 new_hi = hi_ >> amount; |
184 | uint64 new_lo = (lo_ >> amount) | (hi_ << (64 - amount)); |
185 | return uint128(new_hi, new_lo); |
186 | } else if (amount < 128) { |
187 | return uint128(0, hi_ >> (amount - 64)); |
188 | } else { |
189 | return uint128(0, 0); |
190 | } |
191 | } |
192 | |
193 | inline uint128 uint128::operator+(const uint128& b) const { |
194 | return uint128(*this) += b; |
195 | } |
196 | |
197 | inline uint128 uint128::operator-(const uint128& b) const { |
198 | return uint128(*this) -= b; |
199 | } |
200 | |
201 | inline uint128 uint128::operator+=(const uint128& b) { |
202 | hi_ += b.hi_; |
203 | lo_ += b.lo_; |
204 | if (lo_ < b.lo_) |
205 | ++hi_; |
206 | return *this; |
207 | } |
208 | |
209 | inline uint128 uint128::operator-=(const uint128& b) { |
210 | hi_ -= b.hi_; |
211 | if (b.lo_ > lo_) |
212 | --hi_; |
213 | lo_ -= b.lo_; |
214 | return *this; |
215 | } |
216 | |
217 | inline uint128 uint128::operator++(int) { |
218 | uint128 tmp(*this); |
219 | *this += 1; |
220 | return tmp; |
221 | } |
222 | |
223 | inline uint128 uint128::operator--(int) { |
224 | uint128 tmp(*this); |
225 | *this -= 1; |
226 | return tmp; |
227 | } |
228 | |
229 | inline uint128 uint128::operator++() { |
230 | *this += 1; |
231 | return *this; |
232 | } |
233 | |
234 | inline uint128 uint128::operator--() { |
235 | *this -= 1; |
236 | return *this; |
237 | } |
238 | |
239 | #endif // BASE_INT128_H_ |
240 | |