• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
Uint128Low64(const uint128 & v)128 inline uint64 Uint128Low64(const uint128& v) { return v.lo_; }
Uint128High64(const uint128 & v)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   return (Uint128Low64(lhs) == Uint128Low64(rhs) &&
138           Uint128High64(lhs) == Uint128High64(rhs));
139 }
140 inline bool operator!=(const uint128& lhs, const uint128& rhs) {
141   return !(lhs == rhs);
142 }
143 
uint128()144 inline UINT128_CONSTEXPR uint128::uint128() : lo_(0), hi_(0) {}
uint128(uint64 top,uint64 bottom)145 inline UINT128_CONSTEXPR uint128::uint128(uint64 top, uint64 bottom)
146     : lo_(bottom), hi_(top) {}
uint128(const uint128_pod & v)147 inline UINT128_CONSTEXPR uint128::uint128(const uint128_pod& v)
148     : lo_(v.lo), hi_(v.hi) {}
uint128(uint64 bottom)149 inline UINT128_CONSTEXPR uint128::uint128(uint64 bottom)
150     : lo_(bottom), hi_(0) {}
151 #ifndef SWIG
uint128(uint32 bottom)152 inline UINT128_CONSTEXPR uint128::uint128(uint32 bottom)
153     : lo_(bottom), hi_(0) {}
uint128(int bottom)154 inline UINT128_CONSTEXPR uint128::uint128(int bottom)
155     : lo_(bottom), hi_(static_cast<int64>((bottom < 0) ? -1 : 0)) {}
156 #endif
157 
158 #undef UINT128_CONSTEXPR
159 
Initialize(uint64 top,uint64 bottom)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 CMP128(>)
176 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 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 inline uint128& uint128::operator<<=(int amount) {
265   // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
266   if (amount < 64) {
267     if (amount != 0) {
268       hi_ = (hi_ << amount) | (lo_ >> (64 - amount));
269       lo_ = lo_ << amount;
270     }
271   } else if (amount < 128) {
272     hi_ = lo_ << (amount - 64);
273     lo_ = 0;
274   } else {
275     hi_ = 0;
276     lo_ = 0;
277   }
278   return *this;
279 }
280 
281 inline uint128& uint128::operator>>=(int amount) {
282   // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
283   if (amount < 64) {
284     if (amount != 0) {
285       lo_ = (lo_ >> amount) | (hi_ << (64 - amount));
286       hi_ = hi_ >> amount;
287     }
288   } else if (amount < 128) {
289     lo_ = hi_ >> (amount - 64);
290     hi_ = 0;
291   } else {
292     lo_ = 0;
293     hi_ = 0;
294   }
295   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   hi_ -= b.hi_;
329   if (b.lo_ > lo_)
330     --hi_;
331   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_
384