diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/core/bitmath_func.cpp | 45 | ||||
| -rw-r--r-- | src/core/bitmath_func.hpp | 278 | ||||
| -rw-r--r-- | src/functions.h | 2 | ||||
| -rw-r--r-- | src/macros.h | 269 | ||||
| -rw-r--r-- | src/misc.cpp | 18 | ||||
| -rw-r--r-- | src/pathfind.cpp | 11 |
6 files changed, 324 insertions, 299 deletions
diff --git a/src/core/bitmath_func.cpp b/src/core/bitmath_func.cpp new file mode 100644 index 000000000..9f36ed9a8 --- /dev/null +++ b/src/core/bitmath_func.cpp @@ -0,0 +1,45 @@ +/* $Id$ */ + +/** @file bitmath_func.cpp */ + +#include "../stdafx.h" +#include "bitmath_func.hpp" + +const uint8 _ffb_64[64] = { + 0, 0, 1, 0, 2, 0, 1, 0, + 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, + 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, + 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, + 3, 0, 1, 0, 2, 0, 1, 0, +}; + +/** + * Search the first set bit in a 32 bit variable. + * + * This algorithm is a static implementation of a log + * conguence search algorithm. It checks the first half + * if there is a bit set search there further. And this + * way further. If no bit is set return 0. + * + * @param x The value to search + * @param The position of the first bit set + */ +uint8 FindFirstBit(uint32 x) +{ + if (x == 0) return 0; + /* The macro FIND_FIRST_BIT is better to use when your x is + not more than 128. */ + + uint8 pos = 0; + + if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; } + if ((x & 0x000000ff) == 0) { x >>= 8; pos += 8; } + if ((x & 0x0000000f) == 0) { x >>= 4; pos += 4; } + if ((x & 0x00000003) == 0) { x >>= 2; pos += 2; } + if ((x & 0x00000001) == 0) { pos += 1; } + + return pos; +} diff --git a/src/core/bitmath_func.hpp b/src/core/bitmath_func.hpp new file mode 100644 index 000000000..1877f003e --- /dev/null +++ b/src/core/bitmath_func.hpp @@ -0,0 +1,278 @@ +/* $Id$ */ + +/** @file bitmath_func.hpp */ + +#ifndef BITMATH_FUNC_HPP +#define BITMATH_FUNC_HPP + +/** + * Fetch n bits from x, started at bit s. + * + * This function can be used to fetch n bits from the value x. The + * s value set the startposition to read. The startposition is + * count from the LSB and starts at 0. The result starts at a + * LSB, as this isn't just an and-bitmask but also some + * bit-shifting operations. GB(0xFF, 2, 1) will so + * return 0x01 (0000 0001) instead of + * 0x04 (0000 0100). + * + * @param x The value to read some bits. + * @param s The startposition to read some bits. + * @param n The number of bits to read. + * @return The selected bits, aligned to a LSB. + */ +template<typename T> static inline uint GB(const T x, const uint8 s, const uint8 n) +{ + return (x >> s) & ((1U << n) - 1); +} + +/** Set n bits from x starting at bit s to d + * + * This function sets n bits from x which started as bit s to the value of + * d. The parameters x, s and n works the same as the parameters of + * #GB. The result is saved in x again. Unused bits in the window + * provided by n are set to 0 if the value of b isn't "big" enough. + * This is not a bug, its a feature. + * + * @note Parameter x must be a variable as the result is saved there. + * @note To avoid unexpecting results the value of b should not use more + * space as the provided space of n bits (log2) + * @param x The variable to change some bits + * @param s The startposition for the new bits + * @param n The size/window for the new bits + * @param d The actually new bits to save in the defined position. + * @return The new value of x + */ +template<typename T, typename U> static inline T SB(T& x, const uint8 s, const uint8 n, const U d) +{ + x &= (T)(~(((1U << n) - 1) << s)); + x |= (T)(d << s); + return x; +} + +/** Add i to n bits of x starting at bit s. + * + * This add the value of i on n bits of x starting at bit s. The parameters x, + * s, i are similar to #GB besides x must be a variable as the result are + * saved there. An overflow does not affect the following bits of the given + * bit window and is simply ignored. + * + * @note Parameter x must be a variable as the result is saved there. + * @param x The variable to add some bits at some position + * @param s The startposition of the addition + * @param n The size/window for the addition + * @param i The value to add at the given startposition in the given window. + * @return The new value of x + */ +template<typename T, typename U> static inline T AB(T& x, const uint8 s, const uint8 n, const U i) +{ + const T mask = (T)(((1U << n) - 1) << s); + x = (T)((x & ~mask) | ((x + (i << s)) & mask)); + return x; +} + +/** + * Checks if a bit in a value is set. + * + * This function checks if a bit inside a value is set or not. + * The y value specific the position of the bit, started at the + * LSB and count from 0. + * + * @param x The value to check + * @param y The position of the bit to check, started from the LSB + * @return True if the bit is set, false else. + */ +template<typename T> static inline bool HasBit(const T x, const uint8 y) +{ + return (x & ((T)1U << y)) != 0; +} + +/** + * Check several bits in a value. + * + * This macro checks if a value contains at least one bit of an other + * value. + * + * @param x The first value + * @param y The second value + * @return True if at least one bit is set in both values, false else. + */ +#define HASBITS(x, y) ((x) & (y)) + +/** + * Set a bit in a variable. + * + * This function sets a bit in a variable. The variable is changed + * and the value is also returned. Parameter y defines the bit and + * starts at the LSB with 0. + * + * @param x The variable to set a bit + * @param y The bit position to set + * @return The new value of the old value with the bit set + */ +template<typename T> static inline T SetBit(T& x, const uint8 y) +{ + return x = (T)(x | (T)(1U << y)); +} + +/** + * Sets several bits in a variable. + * + * This macro sets several bits in a variable. The bits to set are provided + * by a value. The new value is also returned. + * + * @param x The variable to set some bits + * @param y The value with set bits for setting them in the variable + * @return The new value of x + */ +#define SETBITS(x, y) ((x) |= (y)) + +/** + * Clears a bit in a variable. + * + * This function clears a bit in a variable. The variable is + * changed and the value is also returned. Parameter y defines the bit + * to clear and starts at the LSB with 0. + * + * @param x The variable to clear the bit + * @param y The bit position to clear + * @return The new value of the old value with the bit cleared + */ +template<typename T> static inline T ClrBit(T& x, const uint8 y) +{ + return x = (T)(x & ~((T)1U << y)); +} + +/** + * Clears several bits in a variable. + * + * This macro clears several bits in a variable. The bits to clear are + * provided by a value. The new value is also returned. + * + * @param x The variable to clear some bits + * @param y The value with set bits for clearing them in the variable + * @return The new value of x + */ +#define CLRBITS(x, y) ((x) &= ~(y)) + +/** + * Toggles a bit in a variable. + * + * This function toggles a bit in a variable. The variable is + * changed and the value is also returned. Parameter y defines the bit + * to toggle and starts at the LSB with 0. + * + * @param x The varliable to toggle the bit + * @param y The bit position to toggle + * @return The new value of the old value with the bit toggled + */ +template<typename T> static inline T ToggleBit(T& x, const uint8 y) +{ + return x = (T)(x ^ (T)(1U << y)); +} + + +/** Lookup table to check which bit is set in a 6 bit variable */ +extern const uint8 _ffb_64[64]; + +/** + * Returns the first occure of a bit in a 6-bit value (from right). + * + * Returns the position of the first bit that is not zero, counted from the + * LSB. Ie, 110100 returns 2, 000001 returns 0, etc. When x == 0 returns + * 0. + * + * @param x The 6-bit value to check the first zero-bit + * @return The first position of a bit started from the LSB or 0 if x is 0. + */ +#define FIND_FIRST_BIT(x) _ffb_64[(x)] + +/** + * Finds the position of the first bit in an integer. + * + * This function returns the position of the first bit set in the + * integer. It does only check the bits of the bitmask + * 0x3F3F (0011111100111111) and checks only the + * bits of the bitmask 0x3F00 if and only if the + * lower part 0x00FF is 0. This results the bits at 0x00C0 must + * be also zero to check the bits at 0x3F00. + * + * @param value The value to check the first bits + * @return The position of the first bit which is set + * @see FIND_FIRST_BIT + */ +static inline uint8 FindFirstBit2x64(const int value) +{ + if ((value & 0xFF) == 0) { + return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8; + } else { + return FIND_FIRST_BIT(value & 0x3F); + } +} + +uint8 FindFirstBit(uint32 x); + +/** + * Clear the first bit in an integer. + * + * This function returns a value where the first bit (from LSB) + * is cleared. + * So, 110100 returns 110000, 000001 returns 000000, etc. + * + * @param value The value to clear the first bit + * @return The new value with the first bit cleared + */ +template<typename T> static inline T KillFirstBit(T value) +{ + return value &= (T)(value - 1); +} + +/** + * Counts the number of set bits in a variable. + * + * @param value the value to count the number of bits in. + * @return the number of bits. + */ +template<typename T> static inline uint CountBits(T value) +{ + uint num; + + /* This loop is only called once for every bit set by clearing the lowest + * bit in each loop. The number of bits is therefore equal to the number of + * times the loop was called. It was found at the following website: + * http://graphics.stanford.edu/~seander/bithacks.html */ + + for (num = 0; value != 0; num++) { + value &= (T)(value - 1); + } + + return num; +} + +/** + * ROtate x Left by n + * + * @note Assumes a byte has 8 bits + * @param x The value which we want to rotate + * @param n The number how many we waht to rotate + * @return A bit rotated number + */ +template<typename T> static inline T ROL(const T x, const uint8 n) +{ + return (T)(x << n | x >> (sizeof(x) * 8 - n)); +} + +/** + * ROtate x Right by n + * + * @note Assumes a byte has 8 bits + * @param x The value which we want to rotate + * @param n The number how many we waht to rotate + * @return A bit rotated number + */ +template<typename T> static inline T ROR(const T x, const uint8 n) +{ + return (T)(x >> n | x << (sizeof(x) * 8 - n)); +} + +#endif /* BITMATH_FUNC_HPP */ diff --git a/src/functions.h b/src/functions.h index 461f89335..e7ee6f26f 100644 --- a/src/functions.h +++ b/src/functions.h @@ -105,8 +105,6 @@ void ChangeTownRating(Town *t, int add, int max); uint GetTownRadiusGroup(const Town* t, TileIndex tile); void ShowHighscoreTable(int difficulty, int8 rank); -int FindFirstBit(uint32 x); - void AfterLoadTown(); void UpdatePatches(); void AskExitGame(); diff --git a/src/macros.h b/src/macros.h index bbe574cf5..51329ab19 100644 --- a/src/macros.h +++ b/src/macros.h @@ -5,176 +5,9 @@ #ifndef MACROS_H #define MACROS_H +#include "core/bitmath_func.hpp" #include "core/math_func.hpp" -/** - * Fetch n bits from x, started at bit s. - * - * This function can be used to fetch n bits from the value x. The - * s value set the startposition to read. The startposition is - * count from the LSB and starts at 0. The result starts at a - * LSB, as this isn't just an and-bitmask but also some - * bit-shifting operations. GB(0xFF, 2, 1) will so - * return 0x01 (0000 0001) instead of - * 0x04 (0000 0100). - * - * @param x The value to read some bits. - * @param s The startposition to read some bits. - * @param n The number of bits to read. - * @return The selected bits, aligned to a LSB. - */ -template<typename T> static inline uint GB(const T x, const uint8 s, const uint8 n) -{ - return (x >> s) & ((1U << n) - 1); -} - -/** Set n bits from x starting at bit s to d - * - * This function sets n bits from x which started as bit s to the value of - * d. The parameters x, s and n works the same as the parameters of - * #GB. The result is saved in x again. Unused bits in the window - * provided by n are set to 0 if the value of b isn't "big" enough. - * This is not a bug, its a feature. - * - * @note Parameter x must be a variable as the result is saved there. - * @note To avoid unexpecting results the value of b should not use more - * space as the provided space of n bits (log2) - * @param x The variable to change some bits - * @param s The startposition for the new bits - * @param n The size/window for the new bits - * @param d The actually new bits to save in the defined position. - * @return The new value of x - */ -template<typename T, typename U> static inline T SB(T& x, const uint8 s, const uint8 n, const U d) -{ - x &= (T)(~(((1U << n) - 1) << s)); - x |= (T)(d << s); - return x; -} - -/** Add i to n bits of x starting at bit s. - * - * This add the value of i on n bits of x starting at bit s. The parameters x, - * s, i are similar to #GB besides x must be a variable as the result are - * saved there. An overflow does not affect the following bits of the given - * bit window and is simply ignored. - * - * @note Parameter x must be a variable as the result is saved there. - * @param x The variable to add some bits at some position - * @param s The startposition of the addition - * @param n The size/window for the addition - * @param i The value to add at the given startposition in the given window. - * @return The new value of x - */ -template<typename T, typename U> static inline T AB(T& x, const uint8 s, const uint8 n, const U i) -{ - const T mask = (T)(((1U << n) - 1) << s); - x = (T)((x & ~mask) | ((x + (i << s)) & mask)); - return x; -} - -/** - * Checks if a bit in a value is set. - * - * This function checks if a bit inside a value is set or not. - * The y value specific the position of the bit, started at the - * LSB and count from 0. - * - * @param x The value to check - * @param y The position of the bit to check, started from the LSB - * @return True if the bit is set, false else. - */ -template<typename T> static inline bool HasBit(const T x, const uint8 y) -{ - return (x & ((T)1U << y)) != 0; -} - -/** - * Set a bit in a variable. - * - * This function sets a bit in a variable. The variable is changed - * and the value is also returned. Parameter y defines the bit and - * starts at the LSB with 0. - * - * @param x The variable to set a bit - * @param y The bit position to set - * @return The new value of the old value with the bit set - */ -template<typename T> static inline T SetBit(T& x, const uint8 y) -{ - return x = (T)(x | (T)(1U << y)); -} - -/** - * Clears a bit in a variable. - * - * This function clears a bit in a variable. The variable is - * changed and the value is also returned. Parameter y defines the bit - * to clear and starts at the LSB with 0. - * - * @param x The variable to clear the bit - * @param y The bit position to clear - * @return The new value of the old value with the bit cleared - */ -template<typename T> static inline T ClrBit(T& x, const uint8 y) -{ - return x = (T)(x & ~((T)1U << y)); -} - -/** - * Toggles a bit in a variable. - * - * This function toggles a bit in a variable. The variable is - * changed and the value is also returned. Parameter y defines the bit - * to toggle and starts at the LSB with 0. - * - * @param x The varliable to toggle the bit - * @param y The bit position to toggle - * @return The new value of the old value with the bit toggled - */ -template<typename T> static inline T ToggleBit(T& x, const uint8 y) -{ - return x = (T)(x ^ (T)(1U << y)); -} - - -/* checking more bits. Maybe unneccessary, but easy to use */ -/** - * Check several bits in a value. - * - * This macro checks if a value contains at least one bit of an other - * value. - * - * @param x The first value - * @param y The second value - * @return True if at least one bit is set in both values, false else. - */ -#define HASBITS(x, y) ((x) & (y)) - -/** - * Sets several bits in a variable. - * - * This macro sets several bits in a variable. The bits to set are provided - * by a value. The new value is also returned. - * - * @param x The variable to set some bits - * @param y The value with set bits for setting them in the variable - * @return The new value of x - */ -#define SETBITS(x, y) ((x) |= (y)) - -/** - * Clears several bits in a variable. - * - * This macro clears several bits in a variable. The bits to clear are - * provided by a value. The new value is also returned. - * - * @param x The variable to clear some bits - * @param y The value with set bits for clearing them in the variable - * @return The new value of x - */ -#define CLRBITS(x, y) ((x) &= ~(y)) - #define GENERAL_SPRITE_COLOR(color) ((color) + PALETTE_RECOLOR_START) #define PLAYER_SPRITE_COLOR(owner) (GENERAL_SPRITE_COLOR(_player_colors[owner])) @@ -187,80 +20,6 @@ template<typename T> static inline T ToggleBit(T& x, const uint8 y) */ #define IS_CUSTOM_SPRITE(sprite) ((sprite) >= SPR_SIGNALS_BASE) -extern const byte _ffb_64[64]; - -/** - * Returns the first occure of a bit in a 6-bit value (from right). - * - * Returns the position of the first bit that is not zero, counted from the - * LSB. Ie, 110100 returns 2, 000001 returns 0, etc. When x == 0 returns - * 0. - * - * @param x The 6-bit value to check the first zero-bit - * @return The first position of a bit started from the LSB or 0 if x is 0. - */ -#define FIND_FIRST_BIT(x) _ffb_64[(x)] - -/** - * Finds the position of the first bit in an integer. - * - * This function returns the position of the first bit set in the - * integer. It does only check the bits of the bitmask - * 0x3F3F (0011111100111111) and checks only the - * bits of the bitmask 0x3F00 if and only if the - * lower part 0x00FF is 0. This results the bits at 0x00C0 must - * be also zero to check the bits at 0x3F00. - * - * @param value The value to check the first bits - * @return The position of the first bit which is set - * @see FIND_FIRST_BIT - */ -static inline int FindFirstBit2x64(int value) -{ - if ((value & 0xFF) == 0) { - return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8; - } else { - return FIND_FIRST_BIT(value & 0x3F); - } -} - -/** - * Clear the first bit in an integer. - * - * This function returns a value where the first bit (from LSB) - * is cleared. - * So, 110100 returns 110000, 000001 returns 000000, etc. - * - * @param value The value to clear the first bit - * @return The new value with the first bit cleared - */ -template<typename T> static inline T KillFirstBit(T value) -{ - return value &= (T)(value - 1); -} - -/** - * Counts the number of set bits in a variable. - * - * @param value the value to count the number of bits in. - * @return the number of bits. - */ -template<typename T> static inline uint CountBits(T value) -{ - uint num; - - /* This loop is only called once for every bit set by clearing the lowest - * bit in each loop. The number of bits is therefore equal to the number of - * times the loop was called. It was found at the following website: - * http://graphics.stanford.edu/~seander/bithacks.html */ - - for (num = 0; value != 0; num++) { - value &= (T)(value - 1); - } - - return num; -} - #define for_each_bit(_i, _b) \ for (_i = 0; _b != 0; _i++, _b >>= 1) \ @@ -282,32 +41,6 @@ static inline uint16 ReadLE16Unaligned(const void* x) } -/** - * ROtate x Left by n - * - * @note Assumes a byte has 8 bits - * @param x The value which we want to rotate - * @param n The number how many we waht to rotate - * @return A bit rotated number - */ -template<typename T> static inline T ROL(const T x, const uint8 n) -{ - return (T)(x << n | x >> (sizeof(x) * 8 - n)); -} - -/** - * ROtate x Right by n - * - * @note Assumes a byte has 8 bits - * @param x The value which we want to rotate - * @param n The number how many we waht to rotate - * @return A bit rotated number - */ -template<typename T> static inline T ROR(const T x, const uint8 n) -{ - return (T)(x >> n | x << (sizeof(x) * 8 - n)); -} - /** return the largest value that can be entered in a variable. */ #define MAX_UVALUE(type) ((type)~(type)0) diff --git a/src/misc.cpp b/src/misc.cpp index 52cd764e8..a74bc1394 100644 --- a/src/misc.cpp +++ b/src/misc.cpp @@ -205,24 +205,6 @@ void InitializeLandscapeVariables(bool only_constants) } - -int FindFirstBit(uint32 value) -{ - /* The macro FIND_FIRST_BIT is better to use when your value is - not more than 128. */ - byte i = 0; - - if (value == 0) return 0; - - if ((value & 0x0000ffff) == 0) { value >>= 16; i += 16; } - if ((value & 0x000000ff) == 0) { value >>= 8; i += 8; } - if ((value & 0x0000000f) == 0) { value >>= 4; i += 4; } - if ((value & 0x00000003) == 0) { value >>= 2; i += 2; } - if ((value & 0x00000001) == 0) { i += 1; } - - return i; -} - static void Save_NAME() { int i; diff --git a/src/pathfind.cpp b/src/pathfind.cpp index d2cf00f13..2588c1c76 100644 --- a/src/pathfind.cpp +++ b/src/pathfind.cpp @@ -230,17 +230,6 @@ static uint SkipToEndOfTunnel(TrackPathFinder* tpf, TileIndex tile, DiagDirectio return flotr.tile; } -const byte _ffb_64[64] = { - 0, 0, 1, 0, 2, 0, 1, 0, - 3, 0, 1, 0, 2, 0, 1, 0, - 4, 0, 1, 0, 2, 0, 1, 0, - 3, 0, 1, 0, 2, 0, 1, 0, - 5, 0, 1, 0, 2, 0, 1, 0, - 3, 0, 1, 0, 2, 0, 1, 0, - 4, 0, 1, 0, 2, 0, 1, 0, - 3, 0, 1, 0, 2, 0, 1, 0, -}; - static void TPFMode1(TrackPathFinder* tpf, TileIndex tile, DiagDirection direction); /** Most code of the "Normal" case of TPF Mode 1; for signals special tricks |