OpenTTD Source  12.0-beta2
bitmath_func.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef BITMATH_FUNC_HPP
11 #define BITMATH_FUNC_HPP
12 
31 template <typename T>
32 static inline uint GB(const T x, const uint8 s, const uint8 n)
33 {
34  return (x >> s) & (((T)1U << n) - 1);
35 }
36 
57 template <typename T, typename U>
58 static inline T SB(T &x, const uint8 s, const uint8 n, const U d)
59 {
60  x &= (T)(~((((T)1U << n) - 1) << s));
61  x |= (T)(d << s);
62  return x;
63 }
64 
82 template <typename T, typename U>
83 static inline T AB(T &x, const uint8 s, const uint8 n, const U i)
84 {
85  const T mask = ((((T)1U << n) - 1) << s);
86  x = (T)((x & ~mask) | ((x + (i << s)) & mask));
87  return x;
88 }
89 
102 template <typename T>
103 static inline bool HasBit(const T x, const uint8 y)
104 {
105  return (x & ((T)1U << y)) != 0;
106 }
107 
120 template <typename T>
121 static inline T SetBit(T &x, const uint8 y)
122 {
123  return x = (T)(x | ((T)1U << y));
124 }
125 
136 #define SETBITS(x, y) ((x) |= (y))
137 
150 template <typename T>
151 static inline T ClrBit(T &x, const uint8 y)
152 {
153  return x = (T)(x & ~((T)1U << y));
154 }
155 
166 #define CLRBITS(x, y) ((x) &= ~(y))
167 
180 template <typename T>
181 static inline T ToggleBit(T &x, const uint8 y)
182 {
183  return x = (T)(x ^ ((T)1U << y));
184 }
185 
186 
188 extern const uint8 _ffb_64[64];
189 
200 #define FIND_FIRST_BIT(x) _ffb_64[(x)]
201 
216 static inline uint8 FindFirstBit2x64(const int value)
217 {
218  if ((value & 0xFF) == 0) {
219  return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8;
220  } else {
221  return FIND_FIRST_BIT(value & 0x3F);
222  }
223 }
224 
225 uint8 FindFirstBit(uint32 x);
226 uint8 FindLastBit(uint64 x);
227 
238 template <typename T>
239 static inline T KillFirstBit(T value)
240 {
241  return value &= (T)(value - 1);
242 }
243 
250 template <typename T>
251 static inline uint CountBits(T value)
252 {
253  uint num;
254 
255  /* This loop is only called once for every bit set by clearing the lowest
256  * bit in each loop. The number of bits is therefore equal to the number of
257  * times the loop was called. It was found at the following website:
258  * http://graphics.stanford.edu/~seander/bithacks.html */
259 
260  for (num = 0; value != 0; num++) {
261  value &= (T)(value - 1);
262  }
263 
264  return num;
265 }
266 
273 template <typename T>
274 static inline bool HasExactlyOneBit(T value)
275 {
276  return value != 0 && (value & (value - 1)) == 0;
277 }
278 
285 template <typename T>
286 static inline bool HasAtMostOneBit(T value)
287 {
288  return (value & (value - 1)) == 0;
289 }
290 
300 template <typename T>
301 static inline T ROL(const T x, const uint8 n)
302 {
303  if (n == 0) return x;
304  return (T)(x << n | x >> (sizeof(x) * 8 - n));
305 }
306 
316 template <typename T>
317 static inline T ROR(const T x, const uint8 n)
318 {
319  if (n == 0) return x;
320  return (T)(x >> n | x << (sizeof(x) * 8 - n));
321 }
322 
328 template <typename Tbitpos = uint, typename Tbitset = uint>
330  struct Iterator {
331  typedef Tbitpos value_type;
332  typedef value_type *pointer;
333  typedef value_type &reference;
334  typedef size_t difference_type;
335  typedef std::forward_iterator_tag iterator_category;
336 
337  explicit Iterator(Tbitset bitset) : bitset(bitset), bitpos(static_cast<Tbitpos>(0))
338  {
339  this->Validate();
340  }
341 
342  bool operator==(const Iterator &other) const
343  {
344  return this->bitset == other.bitset && (this->bitset == 0 || this->bitpos == other.bitpos);
345  }
346  bool operator!=(const Iterator &other) const { return !(*this == other); }
347  Tbitpos operator*() const { return this->bitpos; }
348  Iterator & operator++() { this->Next(); this->Validate(); return *this; }
349 
350  private:
351  Tbitset bitset;
352  Tbitpos bitpos;
353  void Validate()
354  {
355  while (this->bitset != 0 && (this->bitset & 1) == 0) this->Next();
356  }
357  void Next()
358  {
359  this->bitset = static_cast<Tbitset>(this->bitset >> 1);
360  this->bitpos++;
361  }
362  };
363 
364  SetBitIterator(Tbitset bitset) : bitset(bitset) {}
365  Iterator begin() { return Iterator(this->bitset); }
366  Iterator end() { return Iterator(static_cast<Tbitset>(0)); }
367  bool empty() { return this->begin() == this->end(); }
368 
369 private:
370  Tbitset bitset;
371 };
372 
373 #if defined(__APPLE__)
374  /* Make endian swapping use Apple's macros to increase speed
375  * (since it will use hardware swapping if available).
376  * Even though they should return uint16 and uint32, we get
377  * warnings if we don't cast those (why?) */
378 # define BSWAP32(x) (static_cast<uint32>(CFSwapInt32(x)))
379 # define BSWAP16(x) (static_cast<uint16>(CFSwapInt16(x)))
380 #elif defined(_MSC_VER)
381  /* MSVC has intrinsics for swapping, resulting in faster code */
382 # define BSWAP32(x) (_byteswap_ulong(x))
383 # define BSWAP16(x) (_byteswap_ushort(x))
384 #else
385 
390  static inline uint32 BSWAP32(uint32 x)
391  {
392 #if !defined(__ICC) && defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4) && __GNUC_MINOR__ >= 3))
393  /* GCC >= 4.3 provides a builtin, resulting in faster code */
394  return static_cast<uint32>(__builtin_bswap32(static_cast<int32>(x)));
395 #else
396  return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);
397 #endif /* defined(__GNUC__) */
398  }
399 
405  static inline uint16 BSWAP16(uint16 x)
406  {
407  return (x >> 8) | (x << 8);
408  }
409 #endif /* __APPLE__ */
410 
411 #endif /* BITMATH_FUNC_HPP */
HasAtMostOneBit
static bool HasAtMostOneBit(T value)
Test whether value has at most 1 bit set.
Definition: bitmath_func.hpp:286
GB
static uint GB(const T x, const uint8 s, const uint8 n)
Fetch n bits from x, started at bit s.
Definition: bitmath_func.hpp:32
KillFirstBit
static T KillFirstBit(T value)
Clear the first bit in an integer.
Definition: bitmath_func.hpp:239
HasBit
static bool HasBit(const T x, const uint8 y)
Checks if a bit in a value is set.
Definition: bitmath_func.hpp:103
ClrBit
static T ClrBit(T &x, const uint8 y)
Clears a bit in a variable.
Definition: bitmath_func.hpp:151
AB
static T AB(T &x, const uint8 s, const uint8 n, const U i)
Add i to n bits of x starting at bit s.
Definition: bitmath_func.hpp:83
CountBits
static uint CountBits(T value)
Counts the number of set bits in a variable.
Definition: bitmath_func.hpp:251
BSWAP16
static uint16 BSWAP16(uint16 x)
Perform a 16 bits endianness bitswap on x.
Definition: bitmath_func.hpp:405
SetBitIterator
Iterable ensemble of each set bit in a value.
Definition: bitmath_func.hpp:329
HasExactlyOneBit
static bool HasExactlyOneBit(T value)
Test whether value has exactly 1 bit set.
Definition: bitmath_func.hpp:274
SB
static T SB(T &x, const uint8 s, const uint8 n, const U d)
Set n bits in x starting at bit s to d.
Definition: bitmath_func.hpp:58
FindFirstBit2x64
static uint8 FindFirstBit2x64(const int value)
Finds the position of the first non-zero bit in an integer.
Definition: bitmath_func.hpp:216
FindFirstBit
uint8 FindFirstBit(uint32 x)
Search the first set bit in a 32 bit variable.
Definition: bitmath_func.cpp:37
SetBitIterator::Iterator
Definition: bitmath_func.hpp:330
ROL
static T ROL(const T x, const uint8 n)
ROtate x Left by n.
Definition: bitmath_func.hpp:301
BSWAP32
static uint32 BSWAP32(uint32 x)
Perform a 32 bits endianness bitswap on x.
Definition: bitmath_func.hpp:390
FindLastBit
uint8 FindLastBit(uint64 x)
Search the last set bit in a 64 bit variable.
Definition: bitmath_func.cpp:65
_ffb_64
const uint8 _ffb_64[64]
Lookup table to check which bit is set in a 6 bit variable.
Definition: bitmath_func.cpp:15
ToggleBit
static T ToggleBit(T &x, const uint8 y)
Toggles a bit in a variable.
Definition: bitmath_func.hpp:181
SetBit
static T SetBit(T &x, const uint8 y)
Set a bit in a variable.
Definition: bitmath_func.hpp:121
ROR
static T ROR(const T x, const uint8 n)
ROtate x Right by n.
Definition: bitmath_func.hpp:317
FIND_FIRST_BIT
#define FIND_FIRST_BIT(x)
Returns the first non-zero bit in a 6-bit value (from right).
Definition: bitmath_func.hpp:200