src/core/bitmath_func.hpp

   1 /* $Id: bitmath_func.hpp 25685 2013-08-05 20:37:29Z michi_cc $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file bitmath_func.hpp Functions related to bit mathematics. */
  11
  12 #ifndef BITMATH_FUNC_HPP
  13 #define BITMATH_FUNC_HPP
  14
  15 /**
  16  * Fetch \a n bits from \a x, started at bit \a s.
  17  *
  18  * This function can be used to fetch \a n bits from the value \a x. The
  19  * \a s value set the start position to read. The start position is
  20  * count from the LSB and starts at \c 0. The result starts at a
  21  * LSB, as this isn't just an and-bitmask but also some
  22  * bit-shifting operations. GB(0xFF, 2, 1) will so
  23  * return 0x01 (0000 0001) instead of
  24  * 0x04 (0000 0100).
  25  *
  26  * @param x The value to read some bits.
  27  * @param s The start position to read some bits.
  28  * @param n The number of bits to read.
  29  * @pre n < sizeof(T) * 8
  30  * @pre s + n <= sizeof(T) * 8
  31  * @return The selected bits, aligned to a LSB.
  32  */
  33 template <typename T>
  34 static inline uint GB(const T x, const uint8 s, const uint8 n)
  35 {
  36         return (x >> s) & (((T)1U << n) - 1);
  37 }
  38
  39 /**
  40  * Set \a n bits in \a x starting at bit \a s to \a d
  41  *
  42  * This function sets \a n bits from \a x which started as bit \a s to the value of
  43  * \a d. The parameters \a x, \a s and \a n works the same as the parameters of
  44  * #GB. The result is saved in \a x again. Unused bits in the window
  45  * provided by n are set to 0 if the value of \a d isn't "big" enough.
  46  * This is not a bug, its a feature.
  47  *
  48  * @note Parameter \a x must be a variable as the result is saved there.
  49  * @note To avoid unexpected results the value of \a d should not use more
  50  *       space as the provided space of \a n bits (log2)
  51  * @param x The variable to change some bits
  52  * @param s The start position for the new bits
  53  * @param n The size/window for the new bits
  54  * @param d The actually new bits to save in the defined position.
  55  * @pre n < sizeof(T) * 8
  56  * @pre s + n <= sizeof(T) * 8
  57  * @return The new value of \a x
  58  */
  59 template <typename T, typename U>
  60 static inline T SB(T &x, const uint8 s, const uint8 n, const U d)
  61 {
  62         x &= (T)(~((((T)1U << n) - 1) << s));
  63         x |= (T)(d << s);
  64         return x;
  65 }
  66
  67 /**
  68  * Add \a i to \a n bits of \a x starting at bit \a s.
  69  *
  70  * This adds the value of \a i on \a n bits of \a x starting at bit \a s. The parameters \a x,
  71  * \a s, \a i are similar to #GB. Besides, \ a x must be a variable as the result are
  72  * saved there. An overflow does not affect the following bits of the given
  73  * bit window and is simply ignored.
  74  *
  75  * @note Parameter x must be a variable as the result is saved there.
  76  * @param x The variable to add some bits at some position
  77  * @param s The start position of the addition
  78  * @param n The size/window for the addition
  79  * @pre n < sizeof(T) * 8
  80  * @pre s + n <= sizeof(T) * 8
  81  * @param i The value to add at the given start position in the given window.
  82  * @return The new value of \a x
  83  */
  84 template <typename T, typename U>
  85 static inline T AB(T &x, const uint8 s, const uint8 n, const U i)
  86 {
  87         const T mask = ((((T)1U << n) - 1) << s);
  88         x = (T)((x & ~mask) | ((x + (i << s)) & mask));
  89         return x;
  90 }
  91
  92 /**
  93  * Checks if a bit in a value is set.
  94  *
  95  * This function checks if a bit inside a value is set or not.
  96  * The \a y value specific the position of the bit, started at the
  97  * LSB and count from \c 0.
  98  *
  99  * @param x The value to check
 100  * @param y The position of the bit to check, started from the LSB
 101  * @pre y < sizeof(T) * 8
 102  * @return True if the bit is set, false else.
 103  */
 104 template <typename T>
 105 static inline bool HasBit(const T x, const uint8 y)
 106 {
 107         return (x & ((T)1U << y)) != 0;
 108 }
 109
 110 /**
 111  * Set a bit in a variable.
 112  *
 113  * This function sets a bit in a variable. The variable is changed
 114  * and the value is also returned. Parameter y defines the bit and
 115  * starts at the LSB with 0.
 116  *
 117  * @param x The variable to set a bit
 118  * @param y The bit position to set
 119  * @pre y < sizeof(T) * 8
 120  * @return The new value of the old value with the bit set
 121  */
 122 template <typename T>
 123 static inline T SetBit(T &x, const uint8 y)
 124 {
 125         return x = (T)(x | ((T)1U << y));
 126 }
 127
 128 /**
 129  * Sets several bits in a variable.
 130  *
 131  * This macro sets several bits in a variable. The bits to set are provided
 132  * by a value. The new value is also returned.
 133  *
 134  * @param x The variable to set some bits
 135  * @param y The value with set bits for setting them in the variable
 136  * @return The new value of x
 137  */
 138 #define SETBITS(x, y) ((x) |= (y))
 139
 140 /**
 141  * Clears a bit in a variable.
 142  *
 143  * This function clears a bit in a variable. The variable is
 144  * changed and the value is also returned. Parameter y defines the bit
 145  * to clear and starts at the LSB with 0.
 146  *
 147  * @param x The variable to clear the bit
 148  * @param y The bit position to clear
 149  * @pre y < sizeof(T) * 8
 150  * @return The new value of the old value with the bit cleared
 151  */
 152 template <typename T>
 153 static inline T ClrBit(T &x, const uint8 y)
 154 {
 155         return x = (T)(x & ~((T)1U << y));
 156 }
 157
 158 /**
 159  * Clears several bits in a variable.
 160  *
 161  * This macro clears several bits in a variable. The bits to clear are
 162  * provided by a value. The new value is also returned.
 163  *
 164  * @param x The variable to clear some bits
 165  * @param y The value with set bits for clearing them in the variable
 166  * @return The new value of x
 167  */
 168 #define CLRBITS(x, y) ((x) &= ~(y))
 169
 170 /**
 171  * Toggles a bit in a variable.
 172  *
 173  * This function toggles a bit in a variable. The variable is
 174  * changed and the value is also returned. Parameter y defines the bit
 175  * to toggle and starts at the LSB with 0.
 176  *
 177  * @param x The variable to toggle the bit
 178  * @param y The bit position to toggle
 179  * @pre y < sizeof(T) * 8
 180  * @return The new value of the old value with the bit toggled
 181  */
 182 template <typename T>
 183 static inline T ToggleBit(T &x, const uint8 y)
 184 {
 185         return x = (T)(x ^ ((T)1U << y));
 186 }
 187
 188
 189 /** Lookup table to check which bit is set in a 6 bit variable */
 190 extern const uint8 _ffb_64[64];
 191
 192 /**
 193  * Returns the first non-zero bit in a 6-bit value (from right).
 194  *
 195  * Returns the position of the first bit that is not zero, counted from the
 196  * LSB. Ie, 110100 returns 2, 000001 returns 0, etc. When x == 0 returns
 197  * 0.
 198  *
 199  * @param x The 6-bit value to check the first zero-bit
 200  * @return The first position of a bit started from the LSB or 0 if x is 0.
 201  */
 202 #define FIND_FIRST_BIT(x) _ffb_64[(x)]
 203
 204 /**
 205  * Finds the position of the first non-zero bit in an integer.
 206  *
 207  * This function returns the position of the first bit set in the
 208  * integer. It does only check the bits of the bitmask
 209  * 0x3F3F (0011111100111111) and checks only the
 210  * bits of the bitmask 0x3F00 if and only if the
 211  * lower part 0x00FF is 0. This results the bits at 0x00C0 must
 212  * be also zero to check the bits at 0x3F00.
 213  *
 214  * @param value The value to check the first bits
 215  * @return The position of the first bit which is set
 216  * @see FIND_FIRST_BIT
 217  */
 218 static inline uint8 FindFirstBit2x64(const int value)
 219 {
 220         if ((value & 0xFF) == 0) {
 221                 return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8;
 222         } else {
 223                 return FIND_FIRST_BIT(value & 0x3F);
 224         }
 225 }
 226
 227 uint8 FindFirstBit(uint32 x);
 228 uint8 FindLastBit(uint64 x);
 229
 230 /**
 231  * Clear the first bit in an integer.
 232  *
 233  * This function returns a value where the first bit (from LSB)
 234  * is cleared.
 235  * So, 110100 returns 110000, 000001 returns 000000, etc.
 236  *
 237  * @param value The value to clear the first bit
 238  * @return The new value with the first bit cleared
 239  */
 240 template <typename T>
 241 static inline T KillFirstBit(T value)
 242 {
 243         return value &= (T)(value - 1);
 244 }
 245
 246 /**
 247  * Counts the number of set bits in a variable.
 248  *
 249  * @param value the value to count the number of bits in.
 250  * @return the number of bits.
 251  */
 252 template <typename T>
 253 static inline uint CountBits(T value)
 254 {
 255         uint num;
 256
 257         /* This loop is only called once for every bit set by clearing the lowest
 258          * bit in each loop. The number of bits is therefore equal to the number of
 259          * times the loop was called. It was found at the following website:
 260          * http://graphics.stanford.edu/~seander/bithacks.html */
 261
 262         for (num = 0; value != 0; num++) {
 263                 value &= (T)(value - 1);
 264         }
 265
 266         return num;
 267 }
 268
 269 /**
 270  * Test whether \a value has exactly 1 bit set
 271  *
 272  * @param value the value to test.
 273  * @return does \a value have exactly 1 bit set?
 274  */
 275 template <typename T>
 276 static inline bool HasExactlyOneBit(T value)
 277 {
 278         return value != 0 && (value & (value - 1)) == 0;
 279 }
 280
 281 /**
 282  * Test whether \a value has at most 1 bit set
 283  *
 284  * @param value the value to test.
 285  * @return does \a value have at most 1 bit set?
 286  */
 287 template <typename T>
 288 static inline bool HasAtMostOneBit(T value)
 289 {
 290         return (value & (value - 1)) == 0;
 291 }
 292
 293 /**
 294  * ROtate \a x Left by \a n
 295  *
 296  * @note Assumes a byte has 8 bits
 297  * @param x The value which we want to rotate
 298  * @param n The number how many we want to rotate
 299  * @pre n < sizeof(T) * 8
 300  * @return A bit rotated number
 301  */
 302 template <typename T>
 303 static inline T ROL(const T x, const uint8 n)
 304 {
 305         return (T)(x << n | x >> (sizeof(x) * 8 - n));
 306 }
 307
 308 /**
 309  * ROtate \a x Right by \a n
 310  *
 311  * @note Assumes a byte has 8 bits
 312  * @param x The value which we want to rotate
 313  * @param n The number how many we want to rotate
 314  * @pre n < sizeof(T) * 8
 315  * @return A bit rotated number
 316  */
 317 template <typename T>
 318 static inline T ROR(const T x, const uint8 n)
 319 {
 320         return (T)(x >> n | x << (sizeof(x) * 8 - n));
 321 }
 322
 323 /**
 324  * Do an operation for each set bit in a value.
 325  *
 326  * This macros is used to do an operation for each set
 327  * bit in a variable. The second parameter is a
 328  * variable that is used as the bit position counter.
 329  * The fourth parameter is an expression of the bits
 330  * we need to iterate over. This expression will be
 331  * evaluated once.
 332  *
 333  * @param Tbitpos_type Type of the position counter variable.
 334  * @param bitpos_var   The position counter variable.
 335  * @param Tbitset_type Type of the bitset value.
 336  * @param bitset_value The bitset value which we check for bits.
 337  *
 338  * @see FOR_EACH_SET_BIT
 339  */
 340 #define FOR_EACH_SET_BIT_EX(Tbitpos_type, bitpos_var, Tbitset_type, bitset_value) \
 341         for (                                                                           \
 342                 Tbitset_type ___FESBE_bits = (bitpos_var = (Tbitpos_type)0, bitset_value);    \
 343                 ___FESBE_bits != (Tbitset_type)0;                                             \
 344                 ___FESBE_bits = (Tbitset_type)(___FESBE_bits >> 1), bitpos_var++              \
 345         )                                                                               \
 346                 if ((___FESBE_bits & 1) != 0)
 347
 348 /**
 349  * Do an operation for each set set bit in a value.
 350  *
 351  * This macros is used to do an operation for each set
 352  * bit in a variable. The first parameter is a variable
 353  * that is used as the bit position counter.
 354  * The second parameter is an expression of the bits
 355  * we need to iterate over. This expression will be
 356  * evaluated once.
 357  *
 358  * @param bitpos_var   The position counter variable.
 359  * @param bitset_value The value which we check for set bits.
 360  */
 361 #define FOR_EACH_SET_BIT(bitpos_var, bitset_value) FOR_EACH_SET_BIT_EX(uint, bitpos_var, uint, bitset_value)
 362
 363 #if defined(__APPLE__)
 364         /* Make endian swapping use Apple's macros to increase speed
 365          * (since it will use hardware swapping if available).
 366          * Even though they should return uint16 and uint32, we get
 367          * warnings if we don't cast those (why?) */
 368         #define BSWAP32(x) ((uint32)CFSwapInt32(x))
 369         #define BSWAP16(x) ((uint16)CFSwapInt16(x))
 370 #elif defined(_MSC_VER)
 371         /* MSVC has intrinsics for swapping, resulting in faster code */
 372         #define BSWAP32(x) (_byteswap_ulong(x))
 373         #define BSWAP16(x) (_byteswap_ushort(x))
 374 #else
 375         /**
 376          * Perform a 32 bits endianness bitswap on x.
 377          * @param x the variable to bitswap
 378          * @return the bitswapped value.
 379          */
 380         static inline uint32 BSWAP32(uint32 x)
 381         {
 382 #if !defined(__ICC) && defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4)  && __GNUC_MINOR__ >= 3))
 383                 /* GCC >= 4.3 provides a builtin, resulting in faster code */
 384                 return (uint32)__builtin_bswap32((int32)x);
 385 #else
 386                 return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);
 387 #endif /* defined(__GNUC__) */
 388         }
 389
 390         /**
 391          * Perform a 16 bits endianness bitswap on x.
 392          * @param x the variable to bitswap
 393          * @return the bitswapped value.
 394          */
 395         static inline uint16 BSWAP16(uint16 x)
 396         {
 397                 return (x >> 8) | (x << 8);
 398         }
 399 #endif /* __APPLE__ */
 400
 401 #endif /* BITMATH_FUNC_HPP */