1

/* $Id$ */

     2

     3

/** @file bitmath_func.hpp Functions related to bit mathematics. */

     4

     5

#ifndef BITMATH_FUNC_HPP

     6

#define BITMATH_FUNC_HPP

     7

     8

/**

     9

 * Fetch n bits from x, started at bit s.

    10

 *

    11

 * This function can be used to fetch n bits from the value x. The

    12

 * s value set the startposition to read. The startposition is

    13

 * count from the LSB and starts at 0. The result starts at a

    14

 * LSB, as this isn't just an and-bitmask but also some

    15

 * bit-shifting operations. GB(0xFF, 2, 1) will so

    16

 * return 0x01 (0000 0001) instead of

    17

 * 0x04 (0000 0100).

    18

 *

    19

 * @param x The value to read some bits.

    20

 * @param s The startposition to read some bits.

    21

 * @param n The number of bits to read.

    22

 * @return The selected bits, aligned to a LSB.

    23

 */

    24

template <typename T>

    25

static FORCEINLINE uint GB(const T x, const uint8 s, const uint8 n)

    26

{

    27

	return (x >> s) & ((1U << n) - 1);

    28

}

    29

    30

/** Set \a n bits in \a x starting at bit \a s to \a d

    31

 *

    32

 * This function sets \a n bits from \a x which started as bit \a s to the value of

    33

 * \a d. The parameters \a x, \a s and \a n works the same as the parameters of

    34

 * #GB. The result is saved in \a x again. Unused bits in the window

    35

 * provided by n are set to 0 if the value of \a d isn't "big" enough.

    36

 * This is not a bug, its a feature.

    37

 *

    38

 * @note Parameter \a x must be a variable as the result is saved there.

    39

 * @note To avoid unexpecting results the value of \a d should not use more

    40

 *       space as the provided space of \a n bits (log2)

    41

 * @param x The variable to change some bits

    42

 * @param s The startposition for the new bits

    43

 * @param n The size/window for the new bits

    44

 * @param d The actually new bits to save in the defined position.

    45

 * @return The new value of \a x

    46

 */

    47

template <typename T, typename U>

    48

static FORCEINLINE T SB(T &x, const uint8 s, const uint8 n, const U d)

    49

{

    50

	x &= (T)(~(((1U << n) - 1) << s));

    51

	x |= (T)(d << s);

    52

	return x;

    53

}

    54

    55

/** Add i to n bits of x starting at bit s.

    56

 *

    57

 * This add the value of i on n bits of x starting at bit s. The parameters x,

    58

 * s, i are similar to #GB besides x must be a variable as the result are

    59

 * saved there. An overflow does not affect the following bits of the given

    60

 * bit window and is simply ignored.

    61

 *

    62

 * @note Parameter x must be a variable as the result is saved there.

    63

 * @param x The variable to add some bits at some position

    64

 * @param s The startposition of the addition

    65

 * @param n The size/window for the addition

    66

 * @param i The value to add at the given startposition in the given window.

    67

 * @return The new value of x

    68

 */

    69

template <typename T, typename U>

    70

static FORCEINLINE T AB(T &x, const uint8 s, const uint8 n, const U i)

    71

{

    72

	const T mask = (T)(((1U << n) - 1) << s);

    73

	x = (T)((x & ~mask) | ((x + (i << s)) & mask));

    74

	return x;

    75

}

    76

    77

/**

    78

 * Checks if a bit in a value is set.

    79

 *

    80

 * This function checks if a bit inside a value is set or not.

    81

 * The y value specific the position of the bit, started at the

    82

 * LSB and count from 0.

    83

 *

    84

 * @param x The value to check

    85

 * @param y The position of the bit to check, started from the LSB

    86

 * @return True if the bit is set, false else.

    87

 */

    88

template <typename T>

    89

static FORCEINLINE bool HasBit(const T x, const uint8 y)

    90

{

    91

	return (x & ((T)1U << y)) != 0;

    92

}

    93

    94

/**

    95

 * Check several bits in a value.

    96

 *

    97

 * This macro checks if a value contains at least one bit of an other

    98

 * value.

    99

 *

   100

 * @param x The first value

   101

 * @param y The second value

   102

 * @return True if at least one bit is set in both values, false else.

   103

 */

   104

#define HASBITS(x, y) (((x) & (y)) != 0)

   105

   106

/**

   107

 * Set a bit in a variable.

   108

 *

   109

 * This function sets a bit in a variable. The variable is changed

   110

 * and the value is also returned. Parameter y defines the bit and

   111

 * starts at the LSB with 0.

   112

 *

   113

 * @param x The variable to set a bit

   114

 * @param y The bit position to set

   115

 * @return The new value of the old value with the bit set

   116

 */

   117

template <typename T>

   118

static FORCEINLINE T SetBit(T &x, const uint8 y)

   119

{

   120

	return x = (T)(x | (T)(1U << y));

   121

}

   122

   123

/**

   124

 * Sets several bits in a variable.

   125

 *

   126

 * This macro sets several bits in a variable. The bits to set are provided

   127

 * by a value. The new value is also returned.

   128

 *

   129

 * @param x The variable to set some bits

   130

 * @param y The value with set bits for setting them in the variable

   131

 * @return The new value of x

   132

 */

   133

#define SETBITS(x, y) ((x) |= (y))

   134

   135

/**

   136

 * Clears a bit in a variable.

   137

 *

   138

 * This function clears a bit in a variable. The variable is

   139

 * changed and the value is also returned. Parameter y defines the bit

   140

 * to clear and starts at the LSB with 0.

   141

 *

   142

 * @param x The variable to clear the bit

   143

 * @param y The bit position to clear

   144

 * @return The new value of the old value with the bit cleared

   145

 */

   146

template <typename T>

   147

static FORCEINLINE T ClrBit(T &x, const uint8 y)

   148

{

   149

	return x = (T)(x & ~((T)1U << y));

   150

}

   151

   152

/**

   153

 * Clears several bits in a variable.

   154

 *

   155

 * This macro clears several bits in a variable. The bits to clear are

   156

 * provided by a value. The new value is also returned.

   157

 *

   158

 * @param x The variable to clear some bits

   159

 * @param y The value with set bits for clearing them in the variable

   160

 * @return The new value of x

   161

 */

   162

#define CLRBITS(x, y) ((x) &= ~(y))

   163

   164

/**

   165

 * Toggles a bit in a variable.

   166

 *

   167

 * This function toggles a bit in a variable. The variable is

   168

 * changed and the value is also returned. Parameter y defines the bit

   169

 * to toggle and starts at the LSB with 0.

   170

 *

   171

 * @param x The varliable to toggle the bit

   172

 * @param y The bit position to toggle

   173

 * @return The new value of the old value with the bit toggled

   174

 */

   175

template <typename T>

   176

static FORCEINLINE T ToggleBit(T &x, const uint8 y)

   177

{

   178

	return x = (T)(x ^ (T)(1U << y));

   179

}

   180

   181

   182

/** Lookup table to check which bit is set in a 6 bit variable */

   183

extern const uint8 _ffb_64[64];

   184

   185

/**

   186

 * Returns the first occure of a bit in a 6-bit value (from right).

   187

 *

   188

 * Returns the position of the first bit that is not zero, counted from the

   189

 * LSB. Ie, 110100 returns 2, 000001 returns 0, etc. When x == 0 returns

   190

 * 0.

   191

 *

   192

 * @param x The 6-bit value to check the first zero-bit

   193

 * @return The first position of a bit started from the LSB or 0 if x is 0.

   194

 */

   195

#define FIND_FIRST_BIT(x) _ffb_64[(x)]

   196

   197

/**

   198

 * Finds the position of the first bit in an integer.

   199

 *

   200

 * This function returns the position of the first bit set in the

   201

 * integer. It does only check the bits of the bitmask

   202

 * 0x3F3F (0011111100111111) and checks only the

   203

 * bits of the bitmask 0x3F00 if and only if the

   204

 * lower part 0x00FF is 0. This results the bits at 0x00C0 must

   205

 * be also zero to check the bits at 0x3F00.

   206

 *

   207

 * @param value The value to check the first bits

   208

 * @return The position of the first bit which is set

   209

 * @see FIND_FIRST_BIT

   210

 */

   211

static FORCEINLINE uint8 FindFirstBit2x64(const int value)

   212

{

   213

	if ((value & 0xFF) == 0) {

   214

		return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8;

   215

	} else {

   216

		return FIND_FIRST_BIT(value & 0x3F);

   217

	}

   218

}

   219

   220

uint8 FindFirstBit(uint32 x);

   221

uint8 FindLastBit(uint64 x);

   222

   223

/**

   224

 * Clear the first bit in an integer.

   225

 *

   226

 * This function returns a value where the first bit (from LSB)

   227

 * is cleared.

   228

 * So, 110100 returns 110000, 000001 returns 000000, etc.

   229

 *

   230

 * @param value The value to clear the first bit

   231

 * @return The new value with the first bit cleared

   232

 */

   233

template <typename T>

   234

static FORCEINLINE T KillFirstBit(T value)

   235

{

   236

	return value &= (T)(value - 1);

   237

}

   238

   239

/**

   240

 * Counts the number of set bits in a variable.

   241

 *

   242

 * @param value the value to count the number of bits in.

   243

 * @return the number of bits.

   244

 */

   245

template <typename T>

   246

static inline uint CountBits(T value)

   247

{

   248

	uint num;

   249

   250

	/* This loop is only called once for every bit set by clearing the lowest

   251

	 * bit in each loop. The number of bits is therefore equal to the number of

   252

	 * times the loop was called. It was found at the following website:

   253

	 * http://graphics.stanford.edu/~seander/bithacks.html */

   254

   255

	for (num = 0; value != 0; num++) {

   256

		value &= (T)(value - 1);

   257

	}

   258

   259

	return num;

   260

}

   261

   262

/**

   263

 * ROtate x Left by n

   264

 *

   265

 * @note Assumes a byte has 8 bits

   266

 * @param x The value which we want to rotate

   267

 * @param n The number how many we waht to rotate

   268

 * @return A bit rotated number

   269

 */

   270

template <typename T>

   271

static FORCEINLINE T ROL(const T x, const uint8 n)

   272

{

   273

	return (T)(x << n | x >> (sizeof(x) * 8 - n));

   274

}

   275

   276

/**

   277

 * ROtate x Right by n

   278

 *

   279

 * @note Assumes a byte has 8 bits

   280

 * @param x The value which we want to rotate

   281

 * @param n The number how many we waht to rotate

   282

 * @return A bit rotated number

   283

 */

   284

template <typename T>

   285

static FORCEINLINE T ROR(const T x, const uint8 n)

   286

{

   287

	return (T)(x >> n | x << (sizeof(x) * 8 - n));

   288

}

   289

   290

/**

   291

 * Do an operation for each set set bit in a value.

   292

 *

   293

 * This macros is used to do an operation for each set

   294

 * bit in a variable. The first variable can be reused

   295

 * in the operation due to it's the bit position counter.

   296

 * The second variable will be cleared during the usage

   297

 *

   298

 * @param i The position counter

   299

 * @param b The value which we check for set bits

   300

 */

   301

#define FOR_EACH_SET_BIT(i, b)      \

   302

	for (i = 0; b != 0; i++, b >>= 1) \

   303

		if (b & 1)

   304

   305

   306

#if defined(__APPLE__)

   307

	/* Make endian swapping use Apple's macros to increase speed

   308

	 * (since it will use hardware swapping if available).

   309

	 * Even though they should return uint16 and uint32, we get

   310

	 * warnings if we don't cast those (why?) */

   311

	#define BSWAP32(x) ((uint32)Endian32_Swap(x))

   312

	#define BSWAP16(x) ((uint16)Endian16_Swap(x))

   313

#else

   314

	/**

   315

	 * Perform a 32 bits endianness bitswap on x.

   316

	 * @param x the variable to bitswap

   317

	 * @return the bitswapped value.

   318

	 */

   319

	static FORCEINLINE uint32 BSWAP32(uint32 x)

   320

	{

   321

#if defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4)  && __GNUC_MINOR__ >= 3))

   322

		/* GCC >= 4.3 provides a builtin, resulting in faster code */

   323

		return (uint32)__builtin_bswap32((int32)x);

   324

#else

   325

		return ((x >> 24) & 0xFF) | ((x >> 8) & 0xFF00) | ((x << 8) & 0xFF0000) | ((x << 24) & 0xFF000000);

   326

#endif /* defined(__GNUC__) */

   327

	}

   328

   329

	/**

   330

	 * Perform a 16 bits endianness bitswap on x.

   331

	 * @param x the variable to bitswap

   332

	 * @return the bitswapped value.

   333

	 */

   334

	static FORCEINLINE uint16 BSWAP16(uint16 x)

   335

	{

   336

		return (x >> 8) | (x << 8);

   337

	}

   338

#endif /* __APPLE__ */

   339

   340

#endif /* BITMATH_FUNC_HPP */