Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
uint_types.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/common/uint_types.hpp
3  *
4  * Class representing a 40-bit or 48-bit unsigned integer encoded in five or
5  * six bytes.
6  *
7  * Part of Project Thrill - http://project-thrill.org
8  *
9  * Copyright (C) 2013 Timo Bingmann <[email protected]>
10  *
11  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
12  ******************************************************************************/
13 
14 #pragma once
15 #ifndef THRILL_COMMON_UINT_TYPES_HEADER
16 #define THRILL_COMMON_UINT_TYPES_HEADER
17 
20 #include <tlx/define/likely.hpp>
21 
22 #include <cassert>
23 #include <limits>
24 #include <ostream>
25 
26 namespace thrill {
27 namespace common {
28 
29 /*!
30  * Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes.
31  *
32  * The purpose of this class is to provide integers with smaller data storage
33  * footprints when more than 32-bit, but less than 64-bit indexes are
34  * needed. This is commonly the case for storing file offsets and indexes. Here
35  * smaller types currently suffice for files < 1 TiB or < 16 TiB.
36  *
37  * The class combines a 32-bit integer with a HighType (either 8-bit or 16-bit)
38  * to get a larger type. Only unsigned values are supported, which fits the
39  * general application of file offsets.
40  *
41  * Calculation in UIntPair are generally done by transforming everything to
42  * 64-bit data type, so that 64-bit register arithmetic can be used. The
43  * exception here is \b increment and \b decrement, which is done directly on
44  * the lower/higher part. Not all arithmetic operations are supported, patches
45  * welcome if you really need the operations.
46  */
47 #if defined(_MSC_VER)
48 #pragma pack(push, 1)
49 #endif
50 template <typename High_>
51 class UIntPair
52 {
53 public:
54  //! lower part type, always 32-bit
55  using Low = uint32_t;
56  //! higher part type, currently either 8-bit or 16-bit
57  using High = High_;
58 
59 private:
60  //! member containing lower significant integer value
62  //! member containing higher significant integer value
64 
65  //! return highest value storable in lower part, also used as a mask.
66  static unsigned low_max() {
68  }
69 
70  //! number of bits in the lower integer part, used a bit shift value.
71  static constexpr size_t low_bits = 8 * sizeof(Low);
72 
73  //! return highest value storable in higher part, also used as a mask.
74  static unsigned high_max() {
76  }
77 
78  //! number of bits in the higher integer part, used a bit shift value.
79  static constexpr size_t high_bits = 8 * sizeof(High);
80 
81 public:
82  //! number of binary digits (bits) in UIntPair
83  static constexpr size_t digits = low_bits + high_bits;
84 
85  //! number of bytes in UIntPair
86  static constexpr size_t bytes = sizeof(Low) + sizeof(High);
87 
88  // compile-time assertions about size of Low
89  static_assert(8 * sizeof(Low) == 32, "sizeof Low is 32-bit");
90  static_assert(digits / 8 == bytes, "digit and bytes ratio is wrong");
91 
92  //! empty constructor, does not even initialize to zero!
93  UIntPair() = default;
94 
95  //! construct unit pair from lower and higher parts.
96  UIntPair(const Low& l, const High& h)
97  : low_(l), high_(h) { }
98 
99  //! copy constructor
100  UIntPair(const UIntPair&) = default;
101  //! move constructor
102  UIntPair(UIntPair&&) = default;
103 
104  //! const from a simple 32-bit unsigned integer
105  UIntPair(const uint32_t& a) // NOLINT
106  : low_(a), high_(0) { }
107 
108  //! const from a simple 32-bit signed integer
109  UIntPair(const int32_t& a) // NOLINT
110  : low_(a), high_(0) {
111  if (a >= 0)
112  low_ = a;
113  else
114  low_ = a, high_ = (High)high_max();
115  }
116 
117  //! construct from an 64-bit unsigned integer
118  UIntPair(const unsigned long long& a) // NOLINT
119  : low_((Low)(a & low_max())),
120  high_((High)((a >> low_bits) & high_max())) {
121  // check for overflow
122  assert((a >> (low_bits + high_bits)) == 0);
123  }
124 
125  //! construct from an 64-bit signed integer
126  UIntPair(const unsigned long& a) // NOLINT
127  : UIntPair(static_cast<unsigned long long>(a)) { }
128 
129  //! construct from an 64-bit signed integer
130  UIntPair(const int64_t& a) // NOLINT
131  : UIntPair(static_cast<unsigned long long>(a)) { }
132 
133  //! copy assignment operator
134  UIntPair& operator = (const UIntPair&) = default;
135  //! move assignment operator
136  UIntPair& operator = (UIntPair&&) = default;
137 
138  //! return the number as an uint64 (unsigned long long)
139  uint64_t ull() const {
140  return ((uint64_t)high_) << low_bits | (uint64_t)low_;
141  }
142 
143  //! implicit cast to an unsigned long long
144  operator uint64_t () const {
145  return ull();
146  }
147 
148  //! return the number as a uint64_t
149  uint64_t u64() const {
150  return ((uint64_t)high_) << low_bits | (uint64_t)low_;
151  }
152 
153  //! prefix increment operator (directly manipulates the integer parts)
155  if (TLX_UNLIKELY(low_ == low_max()))
156  ++high_, low_ = 0;
157  else
158  ++low_;
159  return *this;
160  }
161 
162  //! prefix decrement operator (directly manipulates the integer parts)
164  if (TLX_UNLIKELY(low_ == 0))
165  --high_, low_ = (Low)low_max();
166  else
167  --low_;
168  return *this;
169  }
170 
171  //! addition operator (uses 64-bit arithmetic)
173  uint64_t add = low_ + uint64_t(b.low_);
174  low_ = (Low)(add & low_max());
175  high_ = (High)(high_ + b.high_ + ((add >> low_bits) & high_max()));
176  return *this;
177  }
178 
179  //! addition operator (uses 64-bit arithmetic)
180  UIntPair operator + (const UIntPair& b) const {
181  uint64_t add = low_ + uint64_t(b.low_);
182  return UIntPair(
183  (Low)(add & low_max()),
184  (High)(high_ + b.high_ + ((add >> low_bits) & high_max())));
185  }
186 
187  //! subtraction operator (uses 64-bit arithmetic)
189  uint64_t sub = low_ - uint64_t(b.low_);
190  low_ = (Low)(sub & low_max());
191  high_ = (High)(high_ - b.high_ + ((sub >> low_bits) & high_max()));
192  return *this;
193  }
194 
195  //! subtraction operator (uses 64-bit arithmetic)
196  UIntPair operator - (const UIntPair& b) const {
197  uint64_t sub = low_ - uint64_t(b.low_);
198  return UIntPair(
199  (Low)(sub & low_max()),
200  (High)(high_ - b.high_ + ((sub >> low_bits) & high_max())));
201  }
202 
203  //! equality checking operator
204  bool operator == (const UIntPair& b) const {
205  return (low_ == b.low_) && (high_ == b.high_);
206  }
207 
208  //! inequality checking operator
209  bool operator != (const UIntPair& b) const {
210  return (low_ != b.low_) || (high_ != b.high_);
211  }
212 
213  //! less-than comparison operator
214  bool operator < (const UIntPair& b) const {
215  return (high_ < b.high_) || (high_ == b.high_ && low_ < b.low_);
216  }
217 
218  //! less-than comparison operator
219  bool operator < (const uint64_t& b) const {
220  return ull() < b;
221  }
222 
223  //! less-or-equal comparison operator
224  bool operator <= (const UIntPair& b) const {
225  return (high_ < b.high_) || (high_ == b.high_ && low_ <= b.low_);
226  }
227 
228  //! greater comparison operator
229  bool operator > (const UIntPair& b) const {
230  return (high_ > b.high_) || (high_ == b.high_ && low_ > b.low_);
231  }
232 
233  //! greater-or-equal comparison operator
234  bool operator >= (const UIntPair& b) const {
235  return (high_ > b.high_) || (high_ == b.high_ && low_ >= b.low_);
236  }
237 
238  //! make a UIntPair outputtable via iostreams, using unsigned long long.
239  friend std ::ostream& operator << (std::ostream& os, const UIntPair& a) {
240  return os << a.ull();
241  }
242 
243  //! return an UIntPair instance containing the smallest value possible
244  static UIntPair min() {
247  }
248 
249  //! return an UIntPair instance containing the largest value possible
250  static UIntPair max() {
253  }
255 #if defined(_MSC_VER)
256 #pragma pack(pop)
257 #endif
258 
259 //! Construct a 40-bit unsigned integer stored in five bytes.
261 
262 //! Construct a 48-bit unsigned integer stored in six bytes.
264 
265 // compile-time assertions about size of our data structure, this tests packing
266 // of structures by the compiler
267 static_assert(sizeof(uint40) == 5, "sizeof uint40 is wrong");
268 static_assert(sizeof(uint48) == 6, "sizeof uint48 is wrong");
269 
270 } // namespace common
271 } // namespace thrill
272 
273 namespace std {
274 
275 //! template class providing some numeric_limits fields for UIntPair types.
276 template <typename HighType>
277 class numeric_limits<thrill::common::UIntPair<HighType> >
278 {
279 public:
281 
282  //! yes we have information about UIntPair
283  static const bool is_specialized = true;
284 
285  //! return an UIntPair instance containing the smallest value possible
286  static UIntPair min()
287  { return UIntPair::min(); }
288 
289  //! return an UIntPair instance containing the largest value possible
290  static UIntPair max()
291  { return UIntPair::max(); }
292 
293  //! return an UIntPair instance containing the smallest value possible
294  static UIntPair lowest()
295  { return min(); }
296 
297  //! unit_pair types are unsigned
298  static const bool is_signed = false;
299 
300  //! UIntPair types are integers
301  static const bool is_integer = true;
302 
303  //! unit_pair types contain exact integers
304  static const bool is_exact = true;
305 
306  //! unit_pair radix is binary
307  static const int radix = 2;
308 
309  //! number of binary digits (bits) in UIntPair
310  static const int digits = UIntPair::digits;
311 
312  //! epsilon is zero
313  static const UIntPair epsilon()
314  { return UIntPair(0, 0); }
315 
316  //! rounding error is zero
317  static const UIntPair round_error()
318  { return UIntPair(0, 0); }
319 
320  //! no exponent
321  static const int min_exponent = 0;
322 
323  //! no exponent
324  static const int min_exponent10 = 0;
325 
326  //! no exponent
327  static const int max_exponent = 0;
328 
329  //! no exponent
330  static const int max_exponent10 = 0;
331 
332  //! no infinity
333  static const bool has_infinity = false;
334 };
335 
336 } // namespace std
337 
338 #endif // !THRILL_COMMON_UINT_TYPES_HEADER
339 
340 /******************************************************************************/
bool operator!=(const UIntPair &b) const
inequality checking operator
Definition: uint_types.hpp:209
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:226
UIntPair & operator=(const UIntPair &)=default
copy assignment operator
UIntPair(const int32_t &a)
const from a simple 32-bit signed integer
Definition: uint_types.hpp:109
UIntPair(const unsigned long long &a)
construct from an 64-bit unsigned integer
Definition: uint_types.hpp:118
static constexpr size_t bytes
number of bytes in UIntPair
Definition: uint_types.hpp:86
static unsigned high_max()
return highest value storable in higher part, also used as a mask.
Definition: uint_types.hpp:74
static UIntPair min()
return an UIntPair instance containing the smallest value possible
Definition: uint_types.hpp:286
bool operator>(const UIntPair &b) const
greater comparison operator
Definition: uint_types.hpp:229
UIntPair operator+(const UIntPair &b) const
addition operator (uses 64-bit arithmetic)
Definition: uint_types.hpp:180
UIntPair & operator-=(const UIntPair &b)
subtraction operator (uses 64-bit arithmetic)
Definition: uint_types.hpp:188
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
UIntPair(const uint32_t &a)
const from a simple 32-bit unsigned integer
Definition: uint_types.hpp:105
static constexpr size_t low_bits
number of bits in the lower integer part, used a bit shift value.
Definition: uint_types.hpp:71
High_ High
higher part type, currently either 8-bit or 16-bit
Definition: uint_types.hpp:57
friend std::ostream & operator<<(std::ostream &os, const UIntPair &a)
make a UIntPair outputtable via iostreams, using unsigned long long.
Definition: uint_types.hpp:239
UIntPair(const int64_t &a)
construct from an 64-bit signed integer
Definition: uint_types.hpp:130
UIntPair()=default
empty constructor, does not even initialize to zero!
uint32_t Low
lower part type, always 32-bit
Definition: uint_types.hpp:55
static UIntPair lowest()
return an UIntPair instance containing the smallest value possible
Definition: uint_types.hpp:294
static UIntPair min()
return an UIntPair instance containing the smallest value possible
Definition: uint_types.hpp:244
UIntPair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.hpp:154
class thrill::common::UIntPair TLX_ATTRIBUTE_PACKED
bool operator==(const UIntPair &b) const
equality checking operator
Definition: uint_types.hpp:204
UIntPair(const unsigned long &a)
construct from an 64-bit signed integer
Definition: uint_types.hpp:126
bool operator>=(const UIntPair &b) const
greater-or-equal comparison operator
Definition: uint_types.hpp:234
static UIntPair max()
return an UIntPair instance containing the largest value possible
Definition: uint_types.hpp:290
static constexpr size_t high_bits
number of bits in the higher integer part, used a bit shift value.
Definition: uint_types.hpp:79
uint64_t ull() const
return the number as an uint64 (unsigned long long)
Definition: uint_types.hpp:139
bool operator<(const UIntPair &b) const
less-than comparison operator
Definition: uint_types.hpp:214
static constexpr size_t digits
number of binary digits (bits) in UIntPair
Definition: uint_types.hpp:83
High high_
member containing higher significant integer value
Definition: uint_types.hpp:63
static const UIntPair round_error()
rounding error is zero
Definition: uint_types.hpp:317
UIntPair operator-(const UIntPair &b) const
subtraction operator (uses 64-bit arithmetic)
Definition: uint_types.hpp:196
UIntPair & operator+=(const UIntPair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.hpp:172
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:217
static unsigned low_max()
return highest value storable in lower part, also used as a mask.
Definition: uint_types.hpp:66
Low low_
member containing lower significant integer value
Definition: uint_types.hpp:61
UIntPair(const Low &l, const High &h)
construct unit pair from lower and higher parts.
Definition: uint_types.hpp:96
uint64_t u64() const
return the number as a uint64_t
Definition: uint_types.hpp:149
static const size_t digits
number of binary digits (bits) in uint_pair
Definition: uint_types.hpp:72
static const UIntPair epsilon()
epsilon is zero
Definition: uint_types.hpp:313
bool operator<=(const UIntPair &b) const
less-or-equal comparison operator
Definition: uint_types.hpp:224
Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes.
Definition: uint_types.hpp:51
UIntPair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.hpp:163
static UIntPair max()
return an UIntPair instance containing the largest value possible
Definition: uint_types.hpp:250