src/core/bitmath_func.hpp

   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
   8 /** @file bitmath_func.hpp Functions related to bit mathematics. */
   9
  10 #ifndef BITMATH_FUNC_HPP
  11 #define BITMATH_FUNC_HPP
  12
  13 /**
  14  * Fetch \a n bits from \a x, started at bit \a s.
  15  *
  16  * This function can be used to fetch \a n bits from the value \a x. The
  17  * \a s value set the start position to read. The start position is
  18  * count from the LSB and starts at \c 0. The result starts at a
  19  * LSB, as this isn't just an and-bitmask but also some
  20  * bit-shifting operations. GB(0xFF, 2, 1) will so
  21  * return 0x01 (0000 0001) instead of
  22  * 0x04 (0000 0100).
  23  *
  24  * @param x The value to read some bits.
  25  * @param s The start position to read some bits.
  26  * @param n The number of bits to read.
  27  * @pre n < sizeof(T) * 8
  28  * @pre s + n <= sizeof(T) * 8
  29  * @return The selected bits, aligned to a LSB.
  30  */
  31 template <typename T>
  32 debug_inline constexpr static uint GB(const T x, const uint8_t s, const uint8_t n)
  33 {
  34         return (x >> s) & (((T)1U << n) - 1);
  35 }
  36
  37 /**
  38  * Set \a n bits in \a x starting at bit \a s to \a d
  39  *
  40  * This function sets \a n bits from \a x which started as bit \a s to the value of
  41  * \a d. The parameters \a x, \a s and \a n works the same as the parameters of
  42  * #GB. The result is saved in \a x again. Unused bits in the window
  43  * provided by n are set to 0 if the value of \a d isn't "big" enough.
  44  * This is not a bug, its a feature.
  45  *
  46  * @note Parameter \a x must be a variable as the result is saved there.
  47  * @note To avoid unexpected results the value of \a d should not use more
  48  *       space as the provided space of \a n bits (log2)
  49  * @param x The variable to change some bits
  50  * @param s The start position for the new bits
  51  * @param n The size/window for the new bits
  52  * @param d The actually new bits to save in the defined position.
  53  * @pre n < sizeof(T) * 8
  54  * @pre s + n <= sizeof(T) * 8
  55  * @return The new value of \a x
  56  */
  57 template <typename T, typename U>
  58 constexpr T SB(T &x, const uint8_t s, const uint8_t n, const U d)
  59 {
  60         x &= (T)(~((((T)1U << n) - 1) << s));
  61         x |= (T)(d << s);
  62         return x;
  63 }
  64
  65 /**
  66  * Add \a i to \a n bits of \a x starting at bit \a s.
  67  *
  68  * This adds the value of \a i on \a n bits of \a x starting at bit \a s. The parameters \a x,
  69  * \a s, \a i are similar to #GB. Besides, \ a x must be a variable as the result are
  70  * saved there. An overflow does not affect the following bits of the given
  71  * bit window and is simply ignored.
  72  *
  73  * @note Parameter x must be a variable as the result is saved there.
  74  * @param x The variable to add some bits at some position
  75  * @param s The start position of the addition
  76  * @param n The size/window for the addition
  77  * @pre n < sizeof(T) * 8
  78  * @pre s + n <= sizeof(T) * 8
  79  * @param i The value to add at the given start position in the given window.
  80  * @return The new value of \a x
  81  */
  82 template <typename T, typename U>
  83 constexpr T AB(T &x, const uint8_t s, const uint8_t 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
  90 /**
  91  * Checks if a bit in a value is set.
  92  *
  93  * This function checks if a bit inside a value is set or not.
  94  * The \a y value specific the position of the bit, started at the
  95  * LSB and count from \c 0.
  96  *
  97  * @param x The value to check
  98  * @param y The position of the bit to check, started from the LSB
  99  * @pre y < sizeof(T) * 8
 100  * @return True if the bit is set, false else.
 101  */
 102 template <typename T>
 103 debug_inline constexpr bool HasBit(const T x, const uint8_t y)
 104 {
 105         return (x & ((T)1U << y)) != 0;
 106 }
 107
 108 /**
 109  * Set a bit in a variable.
 110  *
 111  * This function sets a bit in a variable. The variable is changed
 112  * and the value is also returned. Parameter y defines the bit and
 113  * starts at the LSB with 0.
 114  *
 115  * @param x The variable to set a bit
 116  * @param y The bit position to set
 117  * @pre y < sizeof(T) * 8
 118  * @return The new value of the old value with the bit set
 119  */
 120 template <typename T>
 121 constexpr T SetBit(T &x, const uint8_t y)
 122 {
 123         return x = (T)(x | ((T)1U << y));
 124 }
 125
 126 /**
 127  * Sets several bits in a variable.
 128  *
 129  * This macro sets several bits in a variable. The bits to set are provided
 130  * by a value. The new value is also returned.
 131  *
 132  * @param x The variable to set some bits
 133  * @param y The value with set bits for setting them in the variable
 134  * @return The new value of x
 135  */
 136 #define SETBITS(x, y) ((x) |= (y))
 137
 138 /**
 139  * Clears a bit in a variable.
 140  *
 141  * This function clears a bit in a variable. The variable is
 142  * changed and the value is also returned. Parameter y defines the bit
 143  * to clear and starts at the LSB with 0.
 144  *
 145  * @param x The variable to clear the bit
 146  * @param y The bit position to clear
 147  * @pre y < sizeof(T) * 8
 148  * @return The new value of the old value with the bit cleared
 149  */
 150 template <typename T>
 151 constexpr T ClrBit(T &x, const uint8_t y)
 152 {
 153         return x = (T)(x & ~((T)1U << y));
 154 }
 155
 156 /**
 157  * Clears several bits in a variable.
 158  *
 159  * This macro clears several bits in a variable. The bits to clear are
 160  * provided by a value. The new value is also returned.
 161  *
 162  * @param x The variable to clear some bits
 163  * @param y The value with set bits for clearing them in the variable
 164  * @return The new value of x
 165  */
 166 #define CLRBITS(x, y) ((x) &= ~(y))
 167
 168 /**
 169  * Toggles a bit in a variable.
 170  *
 171  * This function toggles a bit in a variable. The variable is
 172  * changed and the value is also returned. Parameter y defines the bit
 173  * to toggle and starts at the LSB with 0.
 174  *
 175  * @param x The variable to toggle the bit
 176  * @param y The bit position to toggle
 177  * @pre y < sizeof(T) * 8
 178  * @return The new value of the old value with the bit toggled
 179  */
 180 template <typename T>
 181 constexpr T ToggleBit(T &x, const uint8_t y)
 182 {
 183         return x = (T)(x ^ ((T)1U << y));
 184 }
 185
 186 /**
 187  * Assigns a bit in a variable.
 188  *
 189  * This function assigns a single bit in a variable. The variable is
 190  * changed and the value is also returned. Parameter y defines the bit
 191  * to assign and starts at the LSB with 0.
 192  *
 193  * @param x The variable to assign the bit
 194  * @param y The bit position to assign
 195  * @param value The new bit value
 196  * @pre y < sizeof(T) * 8
 197  * @return The new value of the old value with the bit assigned
 198  */
 199 template <typename T>
 200 constexpr T AssignBit(T &x, const uint8_t y, bool value)
 201 {
 202         return SB<T>(x, y, 1, value ? 1 : 0);
 203 }
 204
 205 /**
 206  * Search the first set bit in a value.
 207  * When no bit is set, it returns 0.
 208  *
 209  * @param x The value to search.
 210  * @return The position of the first bit set.
 211  */
 212 template <typename T>
 213 constexpr uint8_t FindFirstBit(T x)
 214 {
 215         if (x == 0) return 0;
 216
 217         if constexpr (std::is_enum_v<T>) {
 218                 return std::countr_zero<std::underlying_type_t<T>>(x);
 219         } else {
 220                 return std::countr_zero(x);
 221         }
 222 }
 223
 224 /**
 225  * Search the last set bit in a value.
 226  * When no bit is set, it returns 0.
 227  *
 228  * @param x The value to search.
 229  * @return The position of the last bit set.
 230  */
 231 template <typename T>
 232 constexpr uint8_t FindLastBit(T x)
 233 {
 234         if (x == 0) return 0;
 235
 236         return std::numeric_limits<T>::digits - std::countl_zero(x) - 1;
 237 }
 238
 239 /**
 240  * Clear the first bit in an integer.
 241  *
 242  * This function returns a value where the first bit (from LSB)
 243  * is cleared.
 244  * So, 110100 returns 110000, 000001 returns 000000, etc.
 245  *
 246  * @param value The value to clear the first bit
 247  * @return The new value with the first bit cleared
 248  */
 249 template <typename T>
 250 constexpr T KillFirstBit(T value)
 251 {
 252         return value &= (T)(value - 1);
 253 }
 254
 255 /**
 256  * Counts the number of set bits in a variable.
 257  *
 258  * @param value the value to count the number of bits in.
 259  * @return the number of bits.
 260  */
 261 template <typename T>
 262 constexpr uint CountBits(T value)
 263 {
 264         if constexpr (std::is_enum_v<T>) {
 265                 return std::popcount<std::underlying_type_t<T>>(value);
 266         } else {
 267                 return std::popcount(value);
 268         }
 269 }
 270
 271 /**
 272  * Test whether \a value has exactly 1 bit set
 273  *
 274  * @param value the value to test.
 275  * @return does \a value have exactly 1 bit set?
 276  */
 277 template <typename T>
 278 constexpr bool HasExactlyOneBit(T value)
 279 {
 280         return value != 0 && (value & (value - 1)) == 0;
 281 }
 282
 283 /**
 284  * Test whether \a value has at most 1 bit set
 285  *
 286  * @param value the value to test.
 287  * @return does \a value have at most 1 bit set?
 288  */
 289 template <typename T>
 290 constexpr bool HasAtMostOneBit(T value)
 291 {
 292         return (value & (value - 1)) == 0;
 293 }
 294
 295  /**
 296  * Iterable ensemble of each set bit in a value.
 297  * @tparam Tbitpos Type of the position variable.
 298  * @tparam Tbitset Type of the bitset value.
 299  */
 300 template <typename Tbitpos = uint, typename Tbitset = uint>
 301 struct SetBitIterator {
 302         struct Iterator {
 303                 typedef Tbitpos value_type;
 304                 typedef value_type *pointer;
 305                 typedef value_type &reference;
 306                 typedef size_t difference_type;
 307                 typedef std::forward_iterator_tag iterator_category;
 308
 309                 explicit Iterator(Tbitset bitset) : bitset(bitset), bitpos(static_cast<Tbitpos>(0))
 310                 {
 311                         this->Validate();
 312                 }
 313
 314                 bool operator==(const Iterator &other) const
 315                 {
 316                         return this->bitset == other.bitset;
 317                 }
 318                 bool operator!=(const Iterator &other) const { return !(*this == other); }
 319                 Tbitpos operator*() const { return this->bitpos; }
 320                 Iterator & operator++() { this->Next(); this->Validate(); return *this; }
 321
 322         private:
 323                 Tbitset bitset;
 324                 Tbitpos bitpos;
 325                 void Validate()
 326                 {
 327                         if (this->bitset != 0) {
 328                                 typename std::make_unsigned<Tbitset>::type unsigned_value = this->bitset;
 329                                 this->bitpos = static_cast<Tbitpos>(FindFirstBit(unsigned_value));
 330                         }
 331                 }
 332                 void Next()
 333                 {
 334                         this->bitset = KillFirstBit(this->bitset);
 335                 }
 336         };
 337
 338         SetBitIterator(Tbitset bitset) : bitset(bitset) {}
 339         Iterator begin() { return Iterator(this->bitset); }
 340         Iterator end() { return Iterator(static_cast<Tbitset>(0)); }
 341         bool empty() { return this->begin() == this->end(); }
 342
 343 private:
 344         Tbitset bitset;
 345 };
 346
 347 #if defined(__APPLE__)
 348         /* Make endian swapping use Apple's macros to increase speed
 349          * (since it will use hardware swapping if available).
 350          * Even though they should return uint16_t and uint32_t, we get
 351          * warnings if we don't cast those (why?) */
 352 #       define BSWAP32(x) (static_cast<uint32_t>(CFSwapInt32(x)))
 353 #       define BSWAP16(x) (static_cast<uint16_t>(CFSwapInt16(x)))
 354 #elif defined(_MSC_VER)
 355         /* MSVC has intrinsics for swapping, resulting in faster code */
 356 #       define BSWAP32(x) (_byteswap_ulong(x))
 357 #       define BSWAP16(x) (_byteswap_ushort(x))
 358 #else
 359         /**
 360          * Perform a 32 bits endianness bitswap on x.
 361          * @param x the variable to bitswap
 362          * @return the bitswapped value.
 363          */
 364         static inline uint32_t BSWAP32(uint32_t x)
 365         {
 366 #if !defined(__ICC) && defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4)  && __GNUC_MINOR__ >= 3))
 367                 /* GCC >= 4.3 provides a builtin, resulting in faster code */
 368                 return static_cast<uint32_t>(__builtin_bswap32(static_cast<int32_t>(x)));
 369 #else
 370                 return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);
 371 #endif /* defined(__GNUC__) */
 372         }
 373
 374         /**
 375          * Perform a 16 bits endianness bitswap on x.
 376          * @param x the variable to bitswap
 377          * @return the bitswapped value.
 378          */
 379         static inline uint16_t BSWAP16(uint16_t x)
 380         {
 381                 return (x >> 8) | (x << 8);
 382         }
 383 #endif /* __APPLE__ */
 384
 385 #endif /* BITMATH_FUNC_HPP */