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