1// Copyright 2004 Google Inc.
2// All Rights Reserved.
3//
4
5#ifndef BASE_INT128_H_
6#define BASE_INT128_H_
7
8#include <iostream>
9using std::ostream;
10using std::cout;
11using std::endl;
12
13#include "base/integral_types.h"
14#include "base/logging.h"
15
16// An unsigned 128-bit integer type. Thread-compatible.
17class uint128 {
18public:
19 uint128(); // Sets to 0, but don't trust on this behavior.
20 uint128(uint64 top, uint64 bottom);
21#ifndef SWIG
22 uint128(int bottom);
23 uint128(uint32 bottom); // Top 96 bits = 0
24#endif
25 uint128(uint64 bottom); // hi_ = 0
26 uint128(const uint128 &val);
27
28 void Initialize(uint64 top, uint64 bottom);
29
30 bool operator==(const uint128& b) const;
31 bool operator!=(const uint128& b) const;
32 uint128& operator=(const uint128& b);
33
34 bool operator<(const uint128& b) const;
35 bool operator>(const uint128& b) const;
36 bool operator<=(const uint128& b) const;
37 bool operator>=(const uint128& b) const;
38
39 // Logical operators.
40 uint128 operator~() const;
41 uint128 operator|(const uint128& b) const;
42 uint128 operator&(const uint128& b) const;
43 uint128 operator^(const uint128& b) const;
44
45 // Shift operators.
46 uint128 operator<<(int amount) const;
47 uint128 operator>>(int amount) const;
48
49 // Arithmetic operators.
50 // TODO: multiplication, division, etc.
51 uint128 operator+(const uint128& b) const;
52 uint128 operator-(const uint128& b) const;
53 uint128 operator+=(const uint128& b);
54 uint128 operator-=(const uint128& b);
55 uint128 operator++(int);
56 uint128 operator--(int);
57 uint128 operator++();
58 uint128 operator--();
59
60 friend uint64 Uint128Low64(const uint128& v);
61 friend uint64 Uint128High64(const uint128& v);
62
63 friend ostream& operator<<(ostream& o, const uint128& b);
64
65private:
66 // Little-endian memory order optimizations can benefit from
67 // having lo_ first, hi_ last.
68 // See util/endian/endian.h and Load128/Store128 for storing a uint128.
69 uint64 lo_;
70 uint64 hi_;
71
72 // Not implemented, just declared for catching automatic type conversions.
73 uint128(uint8);
74 uint128(uint16);
75 uint128(float v);
76 uint128(double v);
77};
78
79extern const uint128 kuint128max;
80
81// allow uint128 to be logged
82extern ostream& operator<<(ostream& o, const uint128& b);
83
84// Methods to access low and high pieces of 128-bit value.
85// Defined externally from uint128 to facilitate conversion
86// to native 128-bit types when compilers support them.
87inline uint64 Uint128Low64(const uint128& v) { return v.lo_; }
88inline uint64 Uint128High64(const uint128& v) { return v.hi_; }
89
90// TODO: perhaps it would be nice to have int128, a signed 128-bit type?
91
92// --------------------------------------------------------------------------
93// Implementation details follow
94// --------------------------------------------------------------------------
95inline bool uint128::operator==(const uint128& b) const {
96 return (lo_ == b.lo_) && (hi_ == b.hi_);
97}
98inline bool uint128::operator!=(const uint128& b) const {
99 return !(*this == b);
100}
101inline uint128& uint128::operator=(const uint128& b) {
102 lo_ = b.lo_;
103 hi_ = b.hi_;
104 return *this;
105}
106
107inline uint128::uint128(): lo_(0), hi_(0) { }
108inline uint128::uint128(uint64 top, uint64 bottom) : lo_(bottom), hi_(top) { }
109inline uint128::uint128(const uint128 &v) : lo_(v.lo_), hi_(v.hi_) { }
110inline uint128::uint128(uint64 bottom) : lo_(bottom), hi_(0) { }
111#ifndef SWIG
112inline uint128::uint128(uint32 bottom) : lo_(bottom), hi_(0) { }
113inline uint128::uint128(int bottom) : lo_(bottom), hi_(0) {
114 if (bottom < 0) {
115 --hi_;
116 }
117}
118#endif
119inline void uint128::Initialize(uint64 top, uint64 bottom) {
120 hi_ = top;
121 lo_ = bottom;
122}
123
124// Comparison operators.
125
126#define CMP128(op) \
127inline bool uint128::operator op(const uint128& b) const { \
128 return (hi_ == b.hi_) ? (lo_ op b.lo_) : (hi_ op b.hi_); \
129}
130
131CMP128(<)
132CMP128(>)
133CMP128(>=)
134CMP128(<=)
135
136#undef CMP128
137
138// Logical operators.
139
140inline uint128 uint128::operator~() const {
141 return uint128(~hi_, ~lo_);
142}
143
144#define LOGIC128(op) \
145inline uint128 uint128::operator op(const uint128& b) const { \
146 return uint128(hi_ op b.hi_, lo_ op b.lo_); \
147}
148
149LOGIC128(|)
150LOGIC128(&)
151LOGIC128(^)
152
153#undef LOGIC128
154
155// Shift operators.
156
157inline uint128 uint128::operator<<(int amount) const {
158 DCHECK_GE(amount, 0);
159
160 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
161 if (amount < 64) {
162 if (amount == 0) {
163 return *this;
164 }
165 uint64 new_hi = (hi_ << amount) | (lo_ >> (64 - amount));
166 uint64 new_lo = lo_ << amount;
167 return uint128(new_hi, new_lo);
168 } else if (amount < 128) {
169 return uint128(lo_ << (amount - 64), 0);
170 } else {
171 return uint128(0, 0);
172 }
173}
174
175inline uint128 uint128::operator>>(int amount) const {
176 DCHECK_GE(amount, 0);
177
178 // uint64 shifts of >= 64 are undefined, so we will need some special-casing.
179 if (amount < 64) {
180 if (amount == 0) {
181 return *this;
182 }
183 uint64 new_hi = hi_ >> amount;
184 uint64 new_lo = (lo_ >> amount) | (hi_ << (64 - amount));
185 return uint128(new_hi, new_lo);
186 } else if (amount < 128) {
187 return uint128(0, hi_ >> (amount - 64));
188 } else {
189 return uint128(0, 0);
190 }
191}
192
193inline uint128 uint128::operator+(const uint128& b) const {
194 return uint128(*this) += b;
195}
196
197inline uint128 uint128::operator-(const uint128& b) const {
198 return uint128(*this) -= b;
199}
200
201inline uint128 uint128::operator+=(const uint128& b) {
202 hi_ += b.hi_;
203 lo_ += b.lo_;
204 if (lo_ < b.lo_)
205 ++hi_;
206 return *this;
207}
208
209inline uint128 uint128::operator-=(const uint128& b) {
210 hi_ -= b.hi_;
211 if (b.lo_ > lo_)
212 --hi_;
213 lo_ -= b.lo_;
214 return *this;
215}
216
217inline uint128 uint128::operator++(int) {
218 uint128 tmp(*this);
219 *this += 1;
220 return tmp;
221}
222
223inline uint128 uint128::operator--(int) {
224 uint128 tmp(*this);
225 *this -= 1;
226 return tmp;
227}
228
229inline uint128 uint128::operator++() {
230 *this += 1;
231 return *this;
232}
233
234inline uint128 uint128::operator--() {
235 *this -= 1;
236 return *this;
237}
238
239#endif // BASE_INT128_H_
240