1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef NET_BASE_INT128_H_
6 #define NET_BASE_INT128_H_
7
8 #include <iosfwd>
9 #include "base/basictypes.h"
10 #include "net/base/net_export.h"
11
12 struct uint128_pod;
13
14 // An unsigned 128-bit integer type. Thread-compatible.
15 class uint128 {
16 public:
17 uint128(); // Sets to 0, but don't trust on this behavior.
18 uint128(uint64 top, uint64 bottom);
19 uint128(int bottom);
20 uint128(uint32 bottom); // Top 96 bits = 0
21 uint128(uint64 bottom); // hi_ = 0
22 uint128(const uint128 &val);
23 uint128(const uint128_pod &val);
24
25 void Initialize(uint64 top, uint64 bottom);
26
27 uint128& operator=(const uint128& b);
28
29 // Arithmetic operators.
30 // TODO: division, etc.
31 uint128& operator+=(const uint128& b);
32 uint128& operator-=(const uint128& b);
33 uint128& operator*=(const uint128& b);
34 uint128 operator++(int);
35 uint128 operator--(int);
36 uint128& operator<<=(int);
37 uint128& operator>>=(int);
38 uint128& operator&=(const uint128& b);
39 uint128& operator|=(const uint128& b);
40 uint128& operator^=(const uint128& b);
41 uint128& operator++();
42 uint128& operator--();
43
44 friend uint64 Uint128Low64(const uint128& v);
45 friend uint64 Uint128High64(const uint128& v);
46
47 // We add "std::" to avoid including all of port.h.
48 friend NET_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& o,
49 const uint128& b);
50
51 private:
52 // Little-endian memory order optimizations can benefit from
53 // having lo_ first, hi_ last.
54 // See util/endian/endian.h and Load128/Store128 for storing a uint128.
55 uint64 lo_;
56 uint64 hi_;
57
58 // Not implemented, just declared for catching automatic type conversions.
59 uint128(uint8);
60 uint128(uint16);
61 uint128(float v);
62 uint128(double v);
63 };
64
65 // This is a POD form of uint128 which can be used for static variables which
66 // need to be operated on as uint128.
67 struct uint128_pod {
68 // Note: The ordering of fields is different than 'class uint128' but the
69 // same as its 2-arg constructor. This enables more obvious initialization
70 // of static instances, which is the primary reason for this struct in the
71 // first place. This does not seem to defeat any optimizations wrt
72 // operations involving this struct.
73 uint64 hi;
74 uint64 lo;
75 };
76
77 NET_EXPORT_PRIVATE extern const uint128_pod kuint128max;
78
79 // allow uint128 to be logged
80 NET_EXPORT_PRIVATE extern std::ostream& operator<<(std::ostream& o,
81 const uint128& b);
82
83 // Methods to access low and high pieces of 128-bit value.
84 // Defined externally from uint128 to facilitate conversion
85 // to native 128-bit types when compilers support them.
Uint128Low64(const uint128 & v)86 inline uint64 Uint128Low64(const uint128& v) { return v.lo_; }
Uint128High64(const uint128 & v)87 inline uint64 Uint128High64(const uint128& v) { return v.hi_; }
88
89 // TODO: perhaps it would be nice to have int128, a signed 128-bit type?
90
91 // --------------------------------------------------------------------------
92 // Implementation details follow
93 // --------------------------------------------------------------------------
94 inline bool operator==(const uint128& lhs, const uint128& rhs) {
95 return (Uint128Low64(lhs) == Uint128Low64(rhs) &&
96 Uint128High64(lhs) == Uint128High64(rhs));
97 }
98 inline bool operator!=(const uint128& lhs, const uint128& rhs) {
99 return !(lhs == rhs);
100 }
101 inline uint128& uint128::operator=(const uint128& b) {
102 lo_ = b.lo_;
103 hi_ = b.hi_;
104 return *this;
105 }
106
uint128()107 inline uint128::uint128(): lo_(0), hi_(0) { }
uint128(uint64 top,uint64 bottom)108 inline uint128::uint128(uint64 top, uint64 bottom) : lo_(bottom), hi_(top) { }
uint128(const uint128 & v)109 inline uint128::uint128(const uint128 &v) : lo_(v.lo_), hi_(v.hi_) { }
uint128(const uint128_pod & v)110 inline uint128::uint128(const uint128_pod &v) : lo_(v.lo), hi_(v.hi) { }
uint128(uint64 bottom)111 inline uint128::uint128(uint64 bottom) : lo_(bottom), hi_(0) { }
uint128(uint32 bottom)112 inline uint128::uint128(uint32 bottom) : lo_(bottom), hi_(0) { }
uint128(int bottom)113 inline uint128::uint128(int bottom) : lo_(bottom), hi_(0) {
114 if (bottom < 0) {
115 --hi_;
116 }
117 }
Initialize(uint64 top,uint64 bottom)118 inline void uint128::Initialize(uint64 top, uint64 bottom) {
119 hi_ = top;
120 lo_ = bottom;
121 }
122
123 // Comparison operators.
124
125 #define CMP128(op) \
126 inline bool operator op(const uint128& lhs, const uint128& rhs) { \
127 return (Uint128High64(lhs) == Uint128High64(rhs)) ? \
128 (Uint128Low64(lhs) op Uint128Low64(rhs)) : \
129 (Uint128High64(lhs) op Uint128High64(rhs)); \
130 }
131
132 CMP128(<)
133 CMP128(>)
134 CMP128(>=)
135 CMP128(<=)
136
137 #undef CMP128
138
139 // Unary operators
140
141 inline uint128 operator-(const uint128& val) {
142 const uint64 hi_flip = ~Uint128High64(val);
143 const uint64 lo_flip = ~Uint128Low64(val);
144 const uint64 lo_add = lo_flip + 1;
145 if (lo_add < lo_flip) {
146 return uint128(hi_flip + 1, lo_add);
147 }
148 return uint128(hi_flip, lo_add);
149 }
150
151 inline bool operator!(const uint128& val) {
152 return !Uint128High64(val) && !Uint128Low64(val);
153 }
154
155 // Logical operators.
156
157 inline uint128 operator~(const uint128& val) {
158 return uint128(~Uint128High64(val), ~Uint128Low64(val));
159 }
160
161 #define LOGIC128(op) \
162 inline uint128 operator op(const uint128& lhs, const uint128& rhs) { \
163 return uint128(Uint128High64(lhs) op Uint128High64(rhs), \
164 Uint128Low64(lhs) op Uint128Low64(rhs)); \
165 }
166
167 LOGIC128(|)
168 LOGIC128(&)
169 LOGIC128(^)
170
171 #undef LOGIC128
172
173 #define LOGICASSIGN128(op) \
174 inline uint128& uint128::operator op(const uint128& other) { \
175 hi_ op other.hi_; \
176 lo_ op other.lo_; \
177 return *this; \
178 }
179
180 LOGICASSIGN128(|=)
181 LOGICASSIGN128(&=)
182 LOGICASSIGN128(^=)
183
184 #undef LOGICASSIGN128
185
186 // Shift operators.
187
188 inline uint128 operator<<(const uint128& val, int amount) {
189 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
190 if (amount < 64) {
191 if (amount == 0) {
192 return val;
193 }
194 uint64 new_hi = (Uint128High64(val) << amount) |
195 (Uint128Low64(val) >> (64 - amount));
196 uint64 new_lo = Uint128Low64(val) << amount;
197 return uint128(new_hi, new_lo);
198 } else if (amount < 128) {
199 return uint128(Uint128Low64(val) << (amount - 64), 0);
200 } else {
201 return uint128(0, 0);
202 }
203 }
204
205 inline uint128 operator>>(const uint128& val, int amount) {
206 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
207 if (amount < 64) {
208 if (amount == 0) {
209 return val;
210 }
211 uint64 new_hi = Uint128High64(val) >> amount;
212 uint64 new_lo = (Uint128Low64(val) >> amount) |
213 (Uint128High64(val) << (64 - amount));
214 return uint128(new_hi, new_lo);
215 } else if (amount < 128) {
216 return uint128(0, Uint128High64(val) >> (amount - 64));
217 } else {
218 return uint128(0, 0);
219 }
220 }
221
222 inline uint128& uint128::operator<<=(int amount) {
223 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
224 if (amount < 64) {
225 if (amount != 0) {
226 hi_ = (hi_ << amount) | (lo_ >> (64 - amount));
227 lo_ = lo_ << amount;
228 }
229 } else if (amount < 128) {
230 hi_ = lo_ << (amount - 64);
231 lo_ = 0;
232 } else {
233 hi_ = 0;
234 lo_ = 0;
235 }
236 return *this;
237 }
238
239 inline uint128& uint128::operator>>=(int amount) {
240 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
241 if (amount < 64) {
242 if (amount != 0) {
243 lo_ = (lo_ >> amount) | (hi_ << (64 - amount));
244 hi_ = hi_ >> amount;
245 }
246 } else if (amount < 128) {
247 hi_ = 0;
248 lo_ = hi_ >> (amount - 64);
249 } else {
250 hi_ = 0;
251 lo_ = 0;
252 }
253 return *this;
254 }
255
256 inline uint128 operator+(const uint128& lhs, const uint128& rhs) {
257 return uint128(lhs) += rhs;
258 }
259
260 inline uint128 operator-(const uint128& lhs, const uint128& rhs) {
261 return uint128(lhs) -= rhs;
262 }
263
264 inline uint128 operator*(const uint128& lhs, const uint128& rhs) {
265 return uint128(lhs) *= rhs;
266 }
267
268 inline uint128& uint128::operator+=(const uint128& b) {
269 hi_ += b.hi_;
270 uint64 lolo = lo_ + b.lo_;
271 if (lolo < lo_)
272 ++hi_;
273 lo_ = lolo;
274 return *this;
275 }
276
277 inline uint128& uint128::operator-=(const uint128& b) {
278 hi_ -= b.hi_;
279 if (b.lo_ > lo_)
280 --hi_;
281 lo_ -= b.lo_;
282 return *this;
283 }
284
285 inline uint128& uint128::operator*=(const uint128& b) {
286 uint64 a96 = hi_ >> 32;
287 uint64 a64 = hi_ & 0xffffffffu;
288 uint64 a32 = lo_ >> 32;
289 uint64 a00 = lo_ & 0xffffffffu;
290 uint64 b96 = b.hi_ >> 32;
291 uint64 b64 = b.hi_ & 0xffffffffu;
292 uint64 b32 = b.lo_ >> 32;
293 uint64 b00 = b.lo_ & 0xffffffffu;
294 // multiply [a96 .. a00] x [b96 .. b00]
295 // terms higher than c96 disappear off the high side
296 // terms c96 and c64 are safe to ignore carry bit
297 uint64 c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96;
298 uint64 c64 = a64 * b00 + a32 * b32 + a00 * b64;
299 this->hi_ = (c96 << 32) + c64;
300 this->lo_ = 0;
301 // add terms after this one at a time to capture carry
302 *this += uint128(a32 * b00) << 32;
303 *this += uint128(a00 * b32) << 32;
304 *this += a00 * b00;
305 return *this;
306 }
307
308 inline uint128 uint128::operator++(int) {
309 uint128 tmp(*this);
310 *this += 1;
311 return tmp;
312 }
313
314 inline uint128 uint128::operator--(int) {
315 uint128 tmp(*this);
316 *this -= 1;
317 return tmp;
318 }
319
320 inline uint128& uint128::operator++() {
321 *this += 1;
322 return *this;
323 }
324
325 inline uint128& uint128::operator--() {
326 *this -= 1;
327 return *this;
328 }
329
330 #endif // NET_BASE_INT128_H_
331