net/base/int128.h

   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.
  86 inline uint64 Uint128Low64(const uint128& v) { return v.lo_; }
  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
 107 inline uint128::uint128(): lo_(0), hi_(0) { }
 108 inline uint128::uint128(uint64 top, uint64 bottom) : lo_(bottom), hi_(top) { }
 109 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) { }
 111 inline uint128::uint128(uint64 bottom) : lo_(bottom), hi_(0) { }
 112 inline uint128::uint128(uint32 bottom) : lo_(bottom), hi_(0) { }
 113 inline uint128::uint128(int bottom) : lo_(bottom), hi_(0) {
 114   if (bottom < 0) {
 115     --hi_;
 116   }
 117 }
 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_