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