skidd13@7971: /* $Id$ */
skidd13@7971: 
rubidium@9111: /** @file bitmath_func.hpp Functions related to bit mathematics. */
skidd13@7971: 
skidd13@7971: #ifndef BITMATH_FUNC_HPP
skidd13@7971: #define BITMATH_FUNC_HPP
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Fetch n bits from x, started at bit s.
skidd13@7971:  *
skidd13@7971:  * This function can be used to fetch n bits from the value x. The
skidd13@7971:  * s value set the startposition to read. The startposition is
skidd13@7971:  * count from the LSB and starts at 0. The result starts at a
skidd13@7971:  * LSB, as this isn't just an and-bitmask but also some
skidd13@7971:  * bit-shifting operations. GB(0xFF, 2, 1) will so
skidd13@7971:  * return 0x01 (0000 0001) instead of
skidd13@7971:  * 0x04 (0000 0100).
skidd13@7971:  *
skidd13@7971:  * @param x The value to read some bits.
skidd13@7971:  * @param s The startposition to read some bits.
skidd13@7971:  * @param n The number of bits to read.
skidd13@7971:  * @return The selected bits, aligned to a LSB.
skidd13@7971:  */
skidd13@7971: template<typename T> static inline uint GB(const T x, const uint8 s, const uint8 n)
skidd13@7971: {
skidd13@7971: 	return (x >> s) & ((1U << n) - 1);
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /** Set n bits from x starting at bit s to d
skidd13@7971:  *
skidd13@7971:  * This function sets n bits from x which started as bit s to the value of
skidd13@7971:  * d. The parameters x, s and n works the same as the parameters of
skidd13@7971:  * #GB. The result is saved in x again. Unused bits in the window
skidd13@7971:  * provided by n are set to 0 if the value of b isn't "big" enough.
skidd13@7971:  * This is not a bug, its a feature.
skidd13@7971:  *
skidd13@7971:  * @note Parameter x must be a variable as the result is saved there.
skidd13@7971:  * @note To avoid unexpecting results the value of b should not use more
skidd13@7971:  *       space as the provided space of n bits (log2)
skidd13@7971:  * @param x The variable to change some bits
skidd13@7971:  * @param s The startposition for the new bits
skidd13@7971:  * @param n The size/window for the new bits
skidd13@7971:  * @param d The actually new bits to save in the defined position.
skidd13@7971:  * @return The new value of x
skidd13@7971:  */
skidd13@7971: template<typename T, typename U> static inline T SB(T& x, const uint8 s, const uint8 n, const U d)
skidd13@7971: {
skidd13@7971: 	x &= (T)(~(((1U << n) - 1) << s));
skidd13@7971: 	x |= (T)(d << s);
skidd13@7971: 	return x;
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /** Add i to n bits of x starting at bit s.
skidd13@7971:  *
skidd13@7971:  * This add the value of i on n bits of x starting at bit s. The parameters x,
skidd13@7971:  * s, i are similar to #GB besides x must be a variable as the result are
skidd13@7971:  * saved there. An overflow does not affect the following bits of the given
skidd13@7971:  * bit window and is simply ignored.
skidd13@7971:  *
skidd13@7971:  * @note Parameter x must be a variable as the result is saved there.
skidd13@7971:  * @param x The variable to add some bits at some position
skidd13@7971:  * @param s The startposition of the addition
skidd13@7971:  * @param n The size/window for the addition
skidd13@7971:  * @param i The value to add at the given startposition in the given window.
skidd13@7971:  * @return The new value of x
skidd13@7971:  */
skidd13@7971: template<typename T, typename U> static inline T AB(T& x, const uint8 s, const uint8 n, const U i)
skidd13@7971: {
skidd13@7971: 	const T mask = (T)(((1U << n) - 1) << s);
skidd13@7971: 	x = (T)((x & ~mask) | ((x + (i << s)) & mask));
skidd13@7971: 	return x;
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Checks if a bit in a value is set.
skidd13@7971:  *
skidd13@7971:  * This function checks if a bit inside a value is set or not.
skidd13@7971:  * The y value specific the position of the bit, started at the
skidd13@7971:  * LSB and count from 0.
skidd13@7971:  *
skidd13@7971:  * @param x The value to check
skidd13@7971:  * @param y The position of the bit to check, started from the LSB
skidd13@7971:  * @return True if the bit is set, false else.
skidd13@7971:  */
skidd13@7971: template<typename T> static inline bool HasBit(const T x, const uint8 y)
skidd13@7971: {
skidd13@7971: 	return (x & ((T)1U << y)) != 0;
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Check several bits in a value.
skidd13@7971:  *
skidd13@7971:  * This macro checks if a value contains at least one bit of an other
skidd13@7971:  * value.
skidd13@7971:  *
skidd13@7971:  * @param x The first value
skidd13@7971:  * @param y The second value
skidd13@7971:  * @return True if at least one bit is set in both values, false else.
skidd13@7971:  */
skidd13@7971: #define HASBITS(x, y) ((x) & (y))
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Set a bit in a variable.
skidd13@7971:  *
skidd13@7971:  * This function sets a bit in a variable. The variable is changed
skidd13@7971:  * and the value is also returned. Parameter y defines the bit and
skidd13@7971:  * starts at the LSB with 0.
skidd13@7971:  *
skidd13@7971:  * @param x The variable to set a bit
skidd13@7971:  * @param y The bit position to set
skidd13@7971:  * @return The new value of the old value with the bit set
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T SetBit(T& x, const uint8 y)
skidd13@7971: {
skidd13@7971: 	return x = (T)(x | (T)(1U << y));
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Sets several bits in a variable.
skidd13@7971:  *
skidd13@7971:  * This macro sets several bits in a variable. The bits to set are provided
skidd13@7971:  * by a value. The new value is also returned.
skidd13@7971:  *
skidd13@7971:  * @param x The variable to set some bits
skidd13@7971:  * @param y The value with set bits for setting them in the variable
skidd13@7971:  * @return The new value of x
skidd13@7971:  */
skidd13@7971: #define SETBITS(x, y) ((x) |= (y))
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Clears a bit in a variable.
skidd13@7971:  *
skidd13@7971:  * This function clears a bit in a variable. The variable is
skidd13@7971:  * changed and the value is also returned. Parameter y defines the bit
skidd13@7971:  * to clear and starts at the LSB with 0.
skidd13@7971:  *
skidd13@7971:  * @param x The variable to clear the bit
skidd13@7971:  * @param y The bit position to clear
skidd13@7971:  * @return The new value of the old value with the bit cleared
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T ClrBit(T& x, const uint8 y)
skidd13@7971: {
skidd13@7971: 	return x = (T)(x & ~((T)1U << y));
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Clears several bits in a variable.
skidd13@7971:  *
skidd13@7971:  * This macro clears several bits in a variable. The bits to clear are
skidd13@7971:  * provided by a value. The new value is also returned.
skidd13@7971:  *
skidd13@7971:  * @param x The variable to clear some bits
skidd13@7971:  * @param y The value with set bits for clearing them in the variable
skidd13@7971:  * @return The new value of x
skidd13@7971:  */
skidd13@7971: #define CLRBITS(x, y) ((x) &= ~(y))
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Toggles a bit in a variable.
skidd13@7971:  *
skidd13@7971:  * This function toggles a bit in a variable. The variable is
skidd13@7971:  * changed and the value is also returned. Parameter y defines the bit
skidd13@7971:  * to toggle and starts at the LSB with 0.
skidd13@7971:  *
skidd13@7971:  * @param x The varliable to toggle the bit
skidd13@7971:  * @param y The bit position to toggle
skidd13@7971:  * @return The new value of the old value with the bit toggled
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T ToggleBit(T& x, const uint8 y)
skidd13@7971: {
skidd13@7971: 	return x = (T)(x ^ (T)(1U << y));
skidd13@7971: }
skidd13@7971: 
skidd13@7971: 
skidd13@7971: /** Lookup table to check which bit is set in a 6 bit variable */
skidd13@7971: extern const uint8 _ffb_64[64];
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Returns the first occure of a bit in a 6-bit value (from right).
skidd13@7971:  *
skidd13@7971:  * Returns the position of the first bit that is not zero, counted from the
skidd13@7971:  * LSB. Ie, 110100 returns 2, 000001 returns 0, etc. When x == 0 returns
skidd13@7971:  * 0.
skidd13@7971:  *
skidd13@7971:  * @param x The 6-bit value to check the first zero-bit
skidd13@7971:  * @return The first position of a bit started from the LSB or 0 if x is 0.
skidd13@7971:  */
skidd13@7971: #define FIND_FIRST_BIT(x) _ffb_64[(x)]
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Finds the position of the first bit in an integer.
skidd13@7971:  *
skidd13@7971:  * This function returns the position of the first bit set in the
skidd13@7971:  * integer. It does only check the bits of the bitmask
skidd13@7971:  * 0x3F3F (0011111100111111) and checks only the
skidd13@7971:  * bits of the bitmask 0x3F00 if and only if the
skidd13@7971:  * lower part 0x00FF is 0. This results the bits at 0x00C0 must
skidd13@7971:  * be also zero to check the bits at 0x3F00.
skidd13@7971:  *
skidd13@7971:  * @param value The value to check the first bits
skidd13@7971:  * @return The position of the first bit which is set
skidd13@7971:  * @see FIND_FIRST_BIT
skidd13@7971:  */
skidd13@7971: static inline uint8 FindFirstBit2x64(const int value)
skidd13@7971: {
skidd13@7971: 	if ((value & 0xFF) == 0) {
skidd13@7971: 		return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8;
skidd13@7971: 	} else {
skidd13@7971: 		return FIND_FIRST_BIT(value & 0x3F);
skidd13@7971: 	}
skidd13@7971: }
skidd13@7971: 
skidd13@7971: uint8 FindFirstBit(uint32 x);
rubidium@8055: uint8 FindLastBit(uint64 x);
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Clear the first bit in an integer.
skidd13@7971:  *
skidd13@7971:  * This function returns a value where the first bit (from LSB)
skidd13@7971:  * is cleared.
skidd13@7971:  * So, 110100 returns 110000, 000001 returns 000000, etc.
skidd13@7971:  *
skidd13@7971:  * @param value The value to clear the first bit
skidd13@7971:  * @return The new value with the first bit cleared
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T KillFirstBit(T value)
skidd13@7971: {
skidd13@7971: 	return value &= (T)(value - 1);
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Counts the number of set bits in a variable.
skidd13@7971:  *
skidd13@7971:  * @param value the value to count the number of bits in.
skidd13@7971:  * @return the number of bits.
skidd13@7971:  */
skidd13@7971: template<typename T> static inline uint CountBits(T value)
skidd13@7971: {
skidd13@7971: 	uint num;
skidd13@7971: 
skidd13@7971: 	/* This loop is only called once for every bit set by clearing the lowest
skidd13@7971: 	 * bit in each loop. The number of bits is therefore equal to the number of
skidd13@7971: 	 * times the loop was called. It was found at the following website:
skidd13@7971: 	 * http://graphics.stanford.edu/~seander/bithacks.html */
skidd13@7971: 
skidd13@7971: 	for (num = 0; value != 0; num++) {
skidd13@7971: 		value &= (T)(value - 1);
skidd13@7971: 	}
skidd13@7971: 
skidd13@7971: 	return num;
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * ROtate x Left by n
skidd13@7971:  *
skidd13@7971:  * @note Assumes a byte has 8 bits
skidd13@7971:  * @param x The value which we want to rotate
skidd13@7971:  * @param n The number how many we waht to rotate
skidd13@7971:  * @return A bit rotated number
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T ROL(const T x, const uint8 n)
skidd13@7971: {
skidd13@7971: 	return (T)(x << n | x >> (sizeof(x) * 8 - n));
skidd13@7971: }
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * ROtate x Right by n
skidd13@7971:  *
skidd13@7971:  * @note Assumes a byte has 8 bits
skidd13@7971:  * @param x The value which we want to rotate
skidd13@7971:  * @param n The number how many we waht to rotate
skidd13@7971:  * @return A bit rotated number
skidd13@7971:  */
skidd13@7971: template<typename T> static inline T ROR(const T x, const uint8 n)
skidd13@7971: {
skidd13@7971: 	return (T)(x >> n | x << (sizeof(x) * 8 - n));
skidd13@7971: }
skidd13@7971: 
rubidium@8113: /**
rubidium@8113:  * Do an operation for each set set bit in a value.
rubidium@8113:  *
rubidium@8113:  * This macros is used to do an operation for each set
rubidium@8113:  * bit in a variable. The first variable can be reused
rubidium@8113:  * in the operation due to it's the bit position counter.
rubidium@8113:  * The second variable will be cleared during the usage
rubidium@8113:  *
rubidium@8113:  * @param i The position counter
rubidium@8113:  * @param b The value which we check for set bits
rubidium@8113:  */
rubidium@8113: #define FOR_EACH_SET_BIT(i, b)      \
rubidium@8113: 	for (i = 0; b != 0; i++, b >>= 1) \
rubidium@8113: 		if (b & 1)
rubidium@8113: 
rubidium@8132: 
rubidium@8132: #if defined(__APPLE__)
rubidium@8132: 	/* Make endian swapping use Apple's macros to increase speed
rubidium@8132: 	 * (since it will use hardware swapping if available).
rubidium@8132: 	 * Even though they should return uint16 and uint32, we get
rubidium@8132: 	 * warnings if we don't cast those (why?) */
rubidium@8132: 	#define BSWAP32(x) ((uint32)Endian32_Swap(x))
rubidium@8132: 	#define BSWAP16(x) ((uint16)Endian16_Swap(x))
rubidium@8132: #else
rubidium@8132: 	/**
rubidium@8132: 	 * Perform a 32 bits endianness bitswap on x.
rubidium@8132: 	 * @param x the variable to bitswap
rubidium@8132: 	 * @return the bitswapped value.
rubidium@8132: 	 */
rubidium@8132: 	static inline uint32 BSWAP32(uint32 x)
rubidium@8132: 	{
rubidium@8132: 		return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);
rubidium@8132: 	}
rubidium@8132: 
rubidium@8132: 	/**
rubidium@8132: 	 * Perform a 16 bits endianness bitswap on x.
rubidium@8132: 	 * @param x the variable to bitswap
rubidium@8132: 	 * @return the bitswapped value.
rubidium@8132: 	 */
rubidium@8132: 	static inline uint16 BSWAP16(uint16 x)
rubidium@8132: 	{
rubidium@8132: 		return (x >> 8) | (x << 8);
rubidium@8132: 	}
rubidium@8132: #endif /* __APPLE__ */
rubidium@8132: 
skidd13@7971: #endif /* BITMATH_FUNC_HPP */