Line data Source code
1 : // Protocol Buffers - Google's data interchange format
2 : // Copyright 2008 Google Inc. All rights reserved.
3 : // https://developers.google.com/protocol-buffers/
4 : //
5 : // Redistribution and use in source and binary forms, with or without
6 : // modification, are permitted provided that the following conditions are
7 : // met:
8 : //
9 : // * Redistributions of source code must retain the above copyright
10 : // notice, this list of conditions and the following disclaimer.
11 : // * Redistributions in binary form must reproduce the above
12 : // copyright notice, this list of conditions and the following disclaimer
13 : // in the documentation and/or other materials provided with the
14 : // distribution.
15 : // * Neither the name of Google Inc. nor the names of its
16 : // contributors may be used to endorse or promote products derived from
17 : // this software without specific prior written permission.
18 : //
19 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 : #ifndef GOOGLE_PROTOBUF_STUBS_INT128_H_
31 : #define GOOGLE_PROTOBUF_STUBS_INT128_H_
32 :
33 : #include <google/protobuf/stubs/common.h>
34 :
35 : #include <iosfwd>
36 :
37 : namespace google {
38 : namespace protobuf {
39 :
40 : struct uint128_pod;
41 :
42 : // TODO(xiaofeng): Define GOOGLE_PROTOBUF_HAS_CONSTEXPR when constexpr is
43 : // available.
44 : #ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR
45 : # define UINT128_CONSTEXPR constexpr
46 : #else
47 : # define UINT128_CONSTEXPR
48 : #endif
49 :
50 : // An unsigned 128-bit integer type. Thread-compatible.
51 : class LIBPROTOBUF_EXPORT uint128 {
52 : public:
53 : UINT128_CONSTEXPR uint128(); // Sets to 0, but don't trust on this behavior.
54 : UINT128_CONSTEXPR uint128(uint64 top, uint64 bottom);
55 : #ifndef SWIG
56 : UINT128_CONSTEXPR uint128(int bottom);
57 : UINT128_CONSTEXPR uint128(uint32 bottom); // Top 96 bits = 0
58 : #endif
59 : UINT128_CONSTEXPR uint128(uint64 bottom); // hi_ = 0
60 : UINT128_CONSTEXPR uint128(const uint128_pod &val);
61 :
62 : // Trivial copy constructor, assignment operator and destructor.
63 :
64 : void Initialize(uint64 top, uint64 bottom);
65 :
66 : // Arithmetic operators.
67 : uint128& operator+=(const uint128& b);
68 : uint128& operator-=(const uint128& b);
69 : uint128& operator*=(const uint128& b);
70 : // Long division/modulo for uint128.
71 : uint128& operator/=(const uint128& b);
72 : uint128& operator%=(const uint128& b);
73 : uint128 operator++(int);
74 : uint128 operator--(int);
75 : uint128& operator<<=(int);
76 : uint128& operator>>=(int);
77 : uint128& operator&=(const uint128& b);
78 : uint128& operator|=(const uint128& b);
79 : uint128& operator^=(const uint128& b);
80 : uint128& operator++();
81 : uint128& operator--();
82 :
83 : friend uint64 Uint128Low64(const uint128& v);
84 : friend uint64 Uint128High64(const uint128& v);
85 :
86 : // We add "std::" to avoid including all of port.h.
87 : LIBPROTOBUF_EXPORT friend std::ostream& operator<<(std::ostream& o,
88 : const uint128& b);
89 :
90 : private:
91 : static void DivModImpl(uint128 dividend, uint128 divisor,
92 : uint128* quotient_ret, uint128* remainder_ret);
93 :
94 : // Little-endian memory order optimizations can benefit from
95 : // having lo_ first, hi_ last.
96 : // See util/endian/endian.h and Load128/Store128 for storing a uint128.
97 : uint64 lo_;
98 : uint64 hi_;
99 :
100 : // Not implemented, just declared for catching automatic type conversions.
101 : uint128(uint8);
102 : uint128(uint16);
103 : uint128(float v);
104 : uint128(double v);
105 : };
106 :
107 : // This is a POD form of uint128 which can be used for static variables which
108 : // need to be operated on as uint128.
109 : struct uint128_pod {
110 : // Note: The ordering of fields is different than 'class uint128' but the
111 : // same as its 2-arg constructor. This enables more obvious initialization
112 : // of static instances, which is the primary reason for this struct in the
113 : // first place. This does not seem to defeat any optimizations wrt
114 : // operations involving this struct.
115 : uint64 hi;
116 : uint64 lo;
117 : };
118 :
119 : LIBPROTOBUF_EXPORT extern const uint128_pod kuint128max;
120 :
121 : // allow uint128 to be logged
122 : LIBPROTOBUF_EXPORT extern std::ostream& operator<<(std::ostream& o,
123 : const uint128& b);
124 :
125 : // Methods to access low and high pieces of 128-bit value.
126 : // Defined externally from uint128 to facilitate conversion
127 : // to native 128-bit types when compilers support them.
128 : inline uint64 Uint128Low64(const uint128& v) { return v.lo_; }
129 : inline uint64 Uint128High64(const uint128& v) { return v.hi_; }
130 :
131 : // TODO: perhaps it would be nice to have int128, a signed 128-bit type?
132 :
133 : // --------------------------------------------------------------------------
134 : // Implementation details follow
135 : // --------------------------------------------------------------------------
136 : inline bool operator==(const uint128& lhs, const uint128& rhs) {
137 0 : return (Uint128Low64(lhs) == Uint128Low64(rhs) &&
138 0 : Uint128High64(lhs) == Uint128High64(rhs));
139 : }
140 : inline bool operator!=(const uint128& lhs, const uint128& rhs) {
141 : return !(lhs == rhs);
142 : }
143 :
144 0 : inline UINT128_CONSTEXPR uint128::uint128() : lo_(0), hi_(0) {}
145 : inline UINT128_CONSTEXPR uint128::uint128(uint64 top, uint64 bottom)
146 : : lo_(bottom), hi_(top) {}
147 : inline UINT128_CONSTEXPR uint128::uint128(const uint128_pod& v)
148 : : lo_(v.lo), hi_(v.hi) {}
149 : inline UINT128_CONSTEXPR uint128::uint128(uint64 bottom)
150 : : lo_(bottom), hi_(0) {}
151 : #ifndef SWIG
152 : inline UINT128_CONSTEXPR uint128::uint128(uint32 bottom)
153 : : lo_(bottom), hi_(0) {}
154 : inline UINT128_CONSTEXPR uint128::uint128(int bottom)
155 0 : : lo_(bottom), hi_(static_cast<int64>((bottom < 0) ? -1 : 0)) {}
156 : #endif
157 :
158 : #undef UINT128_CONSTEXPR
159 :
160 : inline void uint128::Initialize(uint64 top, uint64 bottom) {
161 : hi_ = top;
162 : lo_ = bottom;
163 : }
164 :
165 : // Comparison operators.
166 :
167 : #define CMP128(op) \
168 : inline bool operator op(const uint128& lhs, const uint128& rhs) { \
169 : return (Uint128High64(lhs) == Uint128High64(rhs)) ? \
170 : (Uint128Low64(lhs) op Uint128Low64(rhs)) : \
171 : (Uint128High64(lhs) op Uint128High64(rhs)); \
172 : }
173 :
174 : CMP128(<)
175 0 : CMP128(>)
176 0 : CMP128(>=)
177 : CMP128(<=)
178 :
179 : #undef CMP128
180 :
181 : // Unary operators
182 :
183 : inline uint128 operator-(const uint128& val) {
184 : const uint64 hi_flip = ~Uint128High64(val);
185 : const uint64 lo_flip = ~Uint128Low64(val);
186 : const uint64 lo_add = lo_flip + 1;
187 : if (lo_add < lo_flip) {
188 : return uint128(hi_flip + 1, lo_add);
189 : }
190 : return uint128(hi_flip, lo_add);
191 : }
192 :
193 : inline bool operator!(const uint128& val) {
194 : return !Uint128High64(val) && !Uint128Low64(val);
195 : }
196 :
197 : // Logical operators.
198 :
199 : inline uint128 operator~(const uint128& val) {
200 : return uint128(~Uint128High64(val), ~Uint128Low64(val));
201 : }
202 :
203 : #define LOGIC128(op) \
204 : inline uint128 operator op(const uint128& lhs, const uint128& rhs) { \
205 : return uint128(Uint128High64(lhs) op Uint128High64(rhs), \
206 : Uint128Low64(lhs) op Uint128Low64(rhs)); \
207 : }
208 :
209 : LOGIC128(|)
210 : LOGIC128(&)
211 : LOGIC128(^)
212 :
213 : #undef LOGIC128
214 :
215 : #define LOGICASSIGN128(op) \
216 : inline uint128& uint128::operator op(const uint128& other) { \
217 : hi_ op other.hi_; \
218 : lo_ op other.lo_; \
219 : return *this; \
220 : }
221 :
222 0 : LOGICASSIGN128(|=)
223 : LOGICASSIGN128(&=)
224 : LOGICASSIGN128(^=)
225 :
226 : #undef LOGICASSIGN128
227 :
228 : // Shift operators.
229 :
230 : inline uint128 operator<<(const uint128& val, int amount) {
231 : // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
232 : if (amount < 64) {
233 : if (amount == 0) {
234 : return val;
235 : }
236 : uint64 new_hi = (Uint128High64(val) << amount) |
237 : (Uint128Low64(val) >> (64 - amount));
238 : uint64 new_lo = Uint128Low64(val) << amount;
239 : return uint128(new_hi, new_lo);
240 : } else if (amount < 128) {
241 : return uint128(Uint128Low64(val) << (amount - 64), 0);
242 : } else {
243 : return uint128(0, 0);
244 : }
245 : }
246 :
247 : inline uint128 operator>>(const uint128& val, int amount) {
248 : // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
249 : if (amount < 64) {
250 : if (amount == 0) {
251 : return val;
252 : }
253 : uint64 new_hi = Uint128High64(val) >> amount;
254 : uint64 new_lo = (Uint128Low64(val) >> amount) |
255 : (Uint128High64(val) << (64 - amount));
256 : return uint128(new_hi, new_lo);
257 : } else if (amount < 128) {
258 : return uint128(0, Uint128High64(val) >> (amount - 64));
259 : } else {
260 : return uint128(0, 0);
261 : }
262 : }
263 :
264 0 : inline uint128& uint128::operator<<=(int amount) {
265 : // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
266 0 : if (amount < 64) {
267 0 : if (amount != 0) {
268 0 : hi_ = (hi_ << amount) | (lo_ >> (64 - amount));
269 0 : lo_ = lo_ << amount;
270 : }
271 0 : } else if (amount < 128) {
272 0 : hi_ = lo_ << (amount - 64);
273 0 : lo_ = 0;
274 : } else {
275 0 : hi_ = 0;
276 0 : lo_ = 0;
277 : }
278 0 : return *this;
279 : }
280 :
281 0 : inline uint128& uint128::operator>>=(int amount) {
282 : // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
283 0 : if (amount < 64) {
284 0 : if (amount != 0) {
285 0 : lo_ = (lo_ >> amount) | (hi_ << (64 - amount));
286 0 : hi_ = hi_ >> amount;
287 : }
288 0 : } else if (amount < 128) {
289 0 : lo_ = hi_ >> (amount - 64);
290 0 : hi_ = 0;
291 : } else {
292 0 : lo_ = 0;
293 0 : hi_ = 0;
294 : }
295 0 : return *this;
296 : }
297 :
298 : inline uint128 operator+(const uint128& lhs, const uint128& rhs) {
299 : return uint128(lhs) += rhs;
300 : }
301 :
302 : inline uint128 operator-(const uint128& lhs, const uint128& rhs) {
303 : return uint128(lhs) -= rhs;
304 : }
305 :
306 : inline uint128 operator*(const uint128& lhs, const uint128& rhs) {
307 : return uint128(lhs) *= rhs;
308 : }
309 :
310 : inline uint128 operator/(const uint128& lhs, const uint128& rhs) {
311 : return uint128(lhs) /= rhs;
312 : }
313 :
314 : inline uint128 operator%(const uint128& lhs, const uint128& rhs) {
315 : return uint128(lhs) %= rhs;
316 : }
317 :
318 : inline uint128& uint128::operator+=(const uint128& b) {
319 : hi_ += b.hi_;
320 : uint64 lolo = lo_ + b.lo_;
321 : if (lolo < lo_)
322 : ++hi_;
323 : lo_ = lolo;
324 : return *this;
325 : }
326 :
327 : inline uint128& uint128::operator-=(const uint128& b) {
328 0 : hi_ -= b.hi_;
329 0 : if (b.lo_ > lo_)
330 0 : --hi_;
331 0 : lo_ -= b.lo_;
332 : return *this;
333 : }
334 :
335 : inline uint128& uint128::operator*=(const uint128& b) {
336 : uint64 a96 = hi_ >> 32;
337 : uint64 a64 = hi_ & 0xffffffffu;
338 : uint64 a32 = lo_ >> 32;
339 : uint64 a00 = lo_ & 0xffffffffu;
340 : uint64 b96 = b.hi_ >> 32;
341 : uint64 b64 = b.hi_ & 0xffffffffu;
342 : uint64 b32 = b.lo_ >> 32;
343 : uint64 b00 = b.lo_ & 0xffffffffu;
344 : // multiply [a96 .. a00] x [b96 .. b00]
345 : // terms higher than c96 disappear off the high side
346 : // terms c96 and c64 are safe to ignore carry bit
347 : uint64 c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96;
348 : uint64 c64 = a64 * b00 + a32 * b32 + a00 * b64;
349 : this->hi_ = (c96 << 32) + c64;
350 : this->lo_ = 0;
351 : // add terms after this one at a time to capture carry
352 : *this += uint128(a32 * b00) << 32;
353 : *this += uint128(a00 * b32) << 32;
354 : *this += a00 * b00;
355 : return *this;
356 : }
357 :
358 : inline uint128 uint128::operator++(int) {
359 : uint128 tmp(*this);
360 : *this += 1;
361 : return tmp;
362 : }
363 :
364 : inline uint128 uint128::operator--(int) {
365 : uint128 tmp(*this);
366 : *this -= 1;
367 : return tmp;
368 : }
369 :
370 : inline uint128& uint128::operator++() {
371 : *this += 1;
372 : return *this;
373 : }
374 :
375 : inline uint128& uint128::operator--() {
376 : *this -= 1;
377 : return *this;
378 : }
379 :
380 : } // namespace protobuf
381 : } // namespace google
382 :
383 : #endif // GOOGLE_PROTOBUF_STUBS_INT128_H_
|
