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  * foxxll/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 FOXXLL. See http://foxxll.org
8  *
9  * Copyright (C) 2013 Timo Bingmann <[email protected]>
10  *
11  * Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at
13  * http://www.boost.org/LICENSE_1_0.txt)
14  **************************************************************************/
15 
16 #ifndef FOXXLL_COMMON_UINT_TYPES_HEADER
17 #define FOXXLL_COMMON_UINT_TYPES_HEADER
18 
19 #include <cassert>
20 #include <limits>
21 #include <ostream>
22 
23 #include <foxxll/common/types.hpp>
24 #include <foxxll/common/utils.hpp>
25 #include <foxxll/config.hpp>
26 
27 namespace foxxll {
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 uint_pair 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 FOXXLL_MSVC
48 #pragma pack(push, 1)
49 #endif
50 template <typename HighType>
51 class uint_pair
52 {
53 public:
54  //! lower part type, always 32-bit
55  using low_type = uint32_t;
56  //! higher part type, currently either 8-bit or 16-bit
57  using high_type = HighType;
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 low_type low_max()
67  {
69  }
70 
71  //! number of bits in the lower integer part, used a bit shift value.
72  static const size_t low_bits = 8 * sizeof(low_type);
73 
74  //! return highest value storable in higher part, also used as a mask.
76  {
78  }
79 
80  //! number of bits in the higher integer part, used a bit shift value.
81  static const size_t high_bits = 8 * sizeof(high_type);
82 
83 public:
84  //! number of binary digits (bits) in uint_pair
85  static const size_t digits = low_bits + high_bits;
86 
87  //! number of bytes in uint_pair
88  static const size_t bytes = sizeof(low_type) + sizeof(high_type);
89 
90  //! empty constructor, does not even initialize to zero!
92  {
93  // compile-time assertions about size of low_type
94  static_assert(
95  8 * sizeof(low_type) == 32,
96  "8 * sizeof(low_type) == 32"
97  );
98  // compile-time assertions about size of our data structure, this tests
99  // packing of structures by the compiler
100  static_assert(
101  sizeof(uint_pair) == bytes,
102  "sizeof(uint_pair) == bytes"
103  );
104  static_assert(
105  sizeof(uint_pair) == digits / 8,
106  "sizeof(uint_pair) == digits / 8"
107  );
108  static_assert(digits / 8 == bytes, "digits / 8 == bytes");
109  }
110 
111  //! construct unit pair from lower and higher parts.
112  uint_pair(const low_type& l, const high_type& h)
113  : low(l), high(h)
114  { }
115 
116  //! implicit conversion from a simple 32-bit unsigned integer
117  uint_pair(const uint32_t& a) // NOLINT
118  : low(a), high(0)
119  { }
120 
121  //! implicit conversion from a simple 32-bit signed integer
122  uint_pair(const int32_t& a) // NOLINT
123  : low(a), high(0)
124  {
125  if (a >= 0)
126  low = a;
127  else
128  low = a, high = high_max();
129  }
130 
131  //! implicit conversion from an uint64_t (unsigned long long)
132  uint_pair(const uint64_t& a) // NOLINT
133  : low(static_cast<low_type>(a & low_max())),
134  high(static_cast<high_type>((a >> low_bits) & high_max()))
135  {
136  // check for overflow
137  assert((a >> (low_bits + high_bits)) == 0);
138  }
139 
140  //! return the number as an uint64_t (unsigned long long)
141  uint64_t ull() const
142  {
143  return static_cast<uint64_t>(high) << low_bits | static_cast<uint64_t>(low);
144  }
145 
146  //! implicit cast to an unsigned long long
147  operator uint64_t () const
148  {
149  return ull();
150  }
151 
152  //! return the number as a uint64_t
153  uint64_t u64() const
154  {
155  return static_cast<uint64_t>(high) << low_bits | static_cast<uint64_t>(low);
156  }
157 
158  //! prefix increment operator (directly manipulates the integer parts)
160  {
161  if (UNLIKELY(low == low_max()))
162  ++high, low = 0;
163  else
164  ++low;
165  return *this;
166  }
167 
168  //! prefix decrement operator (directly manipulates the integer parts)
170  {
171  if (UNLIKELY(low == 0))
172  --high, low = low_max();
173  else
174  --low;
175  return *this;
176  }
177 
178  //! addition operator (uses 64-bit arithmetic)
180  {
181  uint64_t add = static_cast<uint64_t>(low) + b.low;
182  low = static_cast<low_type>(add & low_max());
183  high = static_cast<high_type>(high + b.high + ((add >> low_bits) & high_max()));
184  return *this;
185  }
186 
187  //! equality checking operator
188  bool operator == (const uint_pair& b) const
189  {
190  return (low == b.low) && (high == b.high);
191  }
192 
193  //! inequality checking operator
194  bool operator != (const uint_pair& b) const
195  {
196  return (low != b.low) || (high != b.high);
197  }
198 
199  //! less-than comparison operator
200  bool operator < (const uint_pair& b) const
201  {
202  return (high < b.high) || (high == b.high && low < b.low);
203  }
204 
205  //! less-or-equal comparison operator
206  bool operator <= (const uint_pair& b) const
207  {
208  return (high < b.high) || (high == b.high && low <= b.low);
209  }
210 
211  //! greater comparison operator
212  bool operator > (const uint_pair& b) const
213  {
214  return (high > b.high) || (high == b.high && low > b.low);
215  }
216 
217  //! greater-or-equal comparison operator
218  bool operator >= (const uint_pair& b) const
219  {
220  return (high > b.high) || (high == b.high && low >= b.low);
221  }
222 
223  //! make a uint_pair outputtable via iostreams, using unsigned long long.
224  friend std::ostream& operator << (std::ostream& os, const uint_pair& a)
225  {
226  return os << a.ull();
227  }
228 
229  //! return an uint_pair instance containing the smallest value possible
230  static uint_pair min()
231  {
232  return uint_pair(
235  );
236  }
237 
238  //! return an uint_pair instance containing the largest value possible
239  static uint_pair max()
240  {
241  return uint_pair(
244  );
245  }
246 }
247 #if FOXXLL_MSVC
248 ; // NOLINT
249 #pragma pack(pop)
250 #else
251 __attribute__ ((packed)); // NOLINT
252 #endif
253 
254 //! \addtogroup foxxll_support
255 //! \{
256 
257 //! Construct a 40-bit unsigned integer stored in five bytes.
259 
260 //! Construct a 48-bit unsigned integer stored in six bytes.
262 
263 //! \}
264 
265 } // namespace foxxll
266 
267 namespace std {
268 
269 //! template class providing some numeric_limits fields for uint_pair types.
270 template <typename HighType>
271 class numeric_limits<foxxll::uint_pair<HighType> >
272 {
273 public:
274  //! yes we have information about uint_pair
275  static const bool is_specialized = true;
276 
277  //! return an uint_pair instance containing the smallest value possible
280 
281  //! return an uint_pair instance containing the largest value possible
284 
285  //! return an uint_pair instance containing the smallest value possible
287  { return min(); }
288 
289  //! unit_pair types are unsigned
290  static const bool is_signed = false;
291 
292  //! uint_pair types are integers
293  static const bool is_integer = true;
294 
295  //! unit_pair types contain exact integers
296  static const bool is_exact = true;
297 
298  //! unit_pair radix is binary
299  static const int radix = 2;
300 
301  //! number of binary digits (bits) in uint_pair
303 
304  //! epsilon is zero
306  { return foxxll::uint_pair<HighType>(0, 0); }
307 
308  //! rounding error is zero
310  { return foxxll::uint_pair<HighType>(0, 0); }
311 
312  //! no exponent
313  static const int min_exponent = 0;
314 
315  //! no exponent
316  static const int min_exponent10 = 0;
317 
318  //! no exponent
319  static const int max_exponent = 0;
320 
321  //! no exponent
322  static const int max_exponent10 = 0;
323 
324  //! no infinity
325  static const bool has_infinity = false;
326 };
327 
328 } // namespace std
329 
330 #endif // !FOXXLL_COMMON_UINT_TYPES_HEADER
331 
332 /**************************************************************************/
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:226
HighType high_type
higher part type, currently either 8-bit or 16-bit
Definition: uint_types.hpp:44
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.hpp:188
uint_pair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.hpp:169
static foxxll::uint_pair< HighType > min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:278
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:239
static low_type low_max()
return highest value storable in lower part, also used as a mask.
Definition: uint_types.hpp:66
Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes.
Definition: uint_types.hpp:51
uint_pair(const uint64_t &a)
implicit conversion from an uint64_t (unsigned long long)
Definition: uint_types.hpp:132
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:230
uint64_t ull() const
return the number as an uint64_t (unsigned long long)
Definition: uint_types.hpp:141
uint_pair & operator+=(const uint_pair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.hpp:179
static const foxxll::uint_pair< HighType > round_error()
rounding error is zero
Definition: uint_types.hpp:309
bool operator>(const uint_pair &b) const
greater comparison operator
Definition: uint_types.hpp:212
high_type high
member containing higher significant integer value
Definition: uint_types.hpp:63
static foxxll::uint_pair< HighType > lowest()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:286
static const foxxll::uint_pair< HighType > epsilon()
epsilon is zero
Definition: uint_types.hpp:305
uint_pair(const int32_t &a)
implicit conversion from a simple 32-bit signed integer
Definition: uint_types.hpp:122
uint_pair(const low_type &l, const high_type &h)
construct unit pair from lower and higher parts.
Definition: uint_types.hpp:112
static const size_t low_bits
number of bits in the lower integer part, used a bit shift value.
Definition: uint_types.hpp:72
class foxxll::uint_pair __attribute__((packed))
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.hpp:159
HighType high_type
higher part type, currently either 8-bit or 16-bit
Definition: uint_types.hpp:57
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.hpp:194
#define UNLIKELY(c)
Definition: utils.hpp:88
friend std::ostream & operator<<(std::ostream &os, const uint_pair &a)
make a uint_pair outputtable via iostreams, using unsigned long long.
Definition: uint_types.hpp:224
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:217
static const size_t bytes
number of bytes in uint_pair
Definition: uint_types.hpp:88
uint32_t low_type
lower part type, always 32-bit
Definition: uint_types.hpp:55
low_type low
member containing lower significant integer value
Definition: uint_types.hpp:61
static const size_t digits
number of binary digits (bits) in uint_pair
Definition: uint_types.hpp:85
bool operator>=(const uint_pair &b) const
greater-or-equal comparison operator
Definition: uint_types.hpp:218
static foxxll::uint_pair< HighType > max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:282
static high_type high_max()
return highest value storable in higher part, also used as a mask.
Definition: uint_types.hpp:75
uint64_t u64() const
return the number as a uint64_t
Definition: uint_types.hpp:153
static const size_t high_bits
number of bits in the higher integer part, used a bit shift value.
Definition: uint_types.hpp:81
uint_pair()
empty constructor, does not even initialize to zero!
Definition: uint_types.hpp:91
static const size_t digits
number of binary digits (bits) in uint_pair
Definition: uint_types.hpp:72
bool operator<=(const uint_pair &b) const
less-or-equal comparison operator
Definition: uint_types.hpp:206
bool operator<(const uint_pair &b) const
less-than comparison operator
Definition: uint_types.hpp:200
uint_pair()
empty constructor, does not even initialize to zero!
Definition: uint_types.hpp:78
uint_pair(const uint32_t &a)
implicit conversion from a simple 32-bit unsigned integer
Definition: uint_types.hpp:117