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 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 144 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 : 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 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
