8 /**

     8 #include "core/bitmath_func.hpp"

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

     9 #include "core/math_func.hpp"

    10  *

    11  * This macro 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 #define GB(x, s, n) (((x) >> (s)) & ((1U << (n)) - 1))

    25 

    26 /** Set n bits from x starting at bit s to d

    27  *

    28  * This macro sets n bits from x which started as bit s to the value of

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

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

    31  * provided by n are set to 0 if the value of b isn't "big" enough.

    32  * This is not a bug, its a feature.

    33  *

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

    35  * @note To avoid unexpecting results the value of b should not use more

    36  *       space as the provided space of n bits (log2)

    37  * @param x The variable to change some bits

    38  * @param s The startposition for the new bits

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

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

    41  * @return The new value of x

    42  */

    43 #define SB(x, s, n, d) ((x) = ((x) & ~(((1U << (n)) - 1) << (s))) | ((d) << (s)))

    44 

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

    46  *

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

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

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

    50  * bit window and is simply ignored.

    51  *

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

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

    54  * @param s The startposition of the addition

    55  * @param n The size/window for the addition

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

    57  * @return The new value of x

    58  */

    59 #define AB(x, s, n, i) ((x) = ((x) & ~(((1U << (n)) - 1) << (s))) | (((x) + ((i) << (s))) & (((1U << (n)) - 1) << (s))))

    60 

    61 #ifdef min

    62 #undef min

    63 #endif

    64 

    65 #ifdef max

    66 #undef max

    67 #endif

    68 

    69 /**

    70  * Returns the maximum of two values.

    71  *

    72  * This function returns the greater value of two given values.

    73  * If they are equal the value of a is returned.

    74  *

    75  * @param a The first value

    76  * @param b The second value

    77  * @return The greater value or a if equals

    78  */

    79 template <typename T>

    80 static inline T max(T a, T b)

    81 {

    82 	return a >= b ? a : b;

    83 }

    84 

    85 /**

    86  * Returns the minimum of two values.

    87  *

    88  * This function returns the smaller value of two given values.

    89  * If they are equal the value of b is returned.

    90  *

    91  * @param a The first value

    92  * @param b The second value

    93  * @return The smaller value or b if equals

    94  */

    95 template <typename T>

    96 static inline T min(T a, T b)

    97 {

    98 	return a < b ? a : b;

    99 }

   100 

   101 /**

   102  * Returns the minimum of two integer.

   103  *

   104  * This function returns the smaller value of two given integers.

   105  *

   106  * @param a The first integer

   107  * @param b The second integer

   108  * @return The smaller value

   109  */

   110 static inline int min(int a, int b) { if (a <= b) return a; return b; }

   111 

   112 /**

   113  * Returns the minimum of two unsigned integers.

   114  *

   115  * This function returns the smaller value of two given unsigned integers.

   116  *

   117  * @param a The first unsigned integer

   118  * @param b The second unsigned integer

   119  * @return The smaller value

   120  */

   121 static inline uint minu(uint a, uint b) { if (a <= b) return a; return b; }

   122 

   123 /**

   124  * Clamp an integer between an interval.

   125  *

   126  * This function returns a value which is between the given interval of

   127  * min and max. If the given value is in this interval the value itself

   128  * is returned otherwise the border of the interval is returned, according

   129  * which side of the interval was 'left'.

   130  *

   131  * @note The min value must be less or equal of max or you get some

   132  *       unexpected results.

   133  * @param a The value to clamp/truncate.

   134  * @param min The minimum of the interval.

   135  * @param max the maximum of the interval.

   136  * @returns A value between min and max which is closest to a.

   137  * @see clampu(uint, uint, uint)

   138  */

   139 static inline int clamp(int a, int min, int max)

   140 {

   141 	if (a <= min) return min;

   142 	if (a >= max) return max;

   143 	return a;

   144 }

   145 

   146 /**

   147  * Clamp an unsigned integer between an interval.

   148  *

   149  * This function returns a value which is between the given interval of

   150  * min and max. If the given value is in this interval the value itself

   151  * is returned otherwise the border of the interval is returned, according

   152  * which side of the interval was 'left'.

   153  *

   154  * @note The min value must be less or equal of max or you get some

   155  *       unexpected results.

   156  * @param a The value to clamp/truncate.

   157  * @param min The minimum of the interval.

   158  * @param max the maximum of the interval.

   159  * @returns A value between min and max which is closest to a.

   160  * @see clamp(int, int, int)

   161  */

   162 static inline uint clampu(uint a, uint min, uint max)

   163 {

   164 	if (a <= min) return min;

   165 	if (a >= max) return max;

   166 	return a;

   167 }

   168 

   169 /**

   170  * Reduce a signed 64-bit int to a signed 32-bit one

   171  *

   172  * This function clamps a 64-bit integer to a 32-bit integer.

   173  * If the 64-bit value is smaller than the smallest 32-bit integer

   174  * value 0x80000000 this value is returned (the left one bit is the sign bit).

   175  * If the 64-bit value is greater than the greatest 32-bit integer value 0x7FFFFFFF

   176  * this value is returned. In all other cases the 64-bit value 'fits' in a

   177  * 32-bits integer field and so the value is casted to int32 and returned.

   178  *

   179  * @param a The 64-bit value to clamps

   180  * @return The 64-bit value reduced to a 32-bit value

   181  * @see clamp(int, int, int)

   182  */

   183 static inline int32 ClampToI32(int64 a)

   184 {

   185 	if (a <= (int32)0x80000000) return 0x80000000;

   186 	if (a >= (int32)0x7FFFFFFF) return 0x7FFFFFFF;

   187 	return (int32)a;

   188 }

   189 

   190 /**

   191  * Multiply two integer values and shift the results to right.

   192  *

   193  * This function multiplies two integer values. The result is

   194  * shifted by the amount of shift to right.

   195  *

   196  * @param a The first integer

   197  * @param b The second integer

   198  * @param shift The amount to shift the value to right.

   199  * @return The shifted result

   200  */

   201 static inline int32 BIGMULSS(int32 a, int32 b, int shift)

   202 {

   203 	return (int32)((int64)a * (int64)b >> shift);

   204 }

   205 

   206 /**

   207  * Multiply two unsigned integers and shift the results to right.

   208  *

   209  * This function multiplies two unsigned integers. The result is

   210  * shifted by the amount of shift to right.

   211  *

   212  * @param a The first unsigned integer

   213  * @param b The second unsigned integer

   214  * @param shift The amount to shift the value to right.

   215  * @return The shifted result

   216  */

   217 static inline uint32 BIGMULUS(uint32 a, uint32 b, int shift)

   218 {

   219 	return (uint32)((uint64)a * (uint64)b >> shift);

   220 }

   221 

   222 

   223 /**

   224  * Checks if a value is between a window started at some base point.

   225  *

   226  * This macro checks if the value x is between the value of base

   227  * and base+size. If x equals base this returns true. If x equals

   228  * base+size this returns false.

   229  *

   230  * @param x The value to check

   231  * @param base The base value of the interval

   232  * @param size The size of the interval

   233  * @return True if the value is in the interval, false else.

   234  */

   235 /* OPT: optimized into an unsigned comparison */

   236 //#define IS_INSIDE_1D(x, base, size) ((x) >= (base) && (x) < (base) + (size))

   237 #define IS_INSIDE_1D(x, base, size) ( (uint)((x) - (base)) < ((uint)(size)) )

   238 

   239 /**

   240  * Checks if a bit in a value is set.

   241  *

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

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

   244  * LSB and count from 0.

   245  *

   246  * @param x The value to check

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

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

   249  */

   250 template<typename T> static inline bool HASBIT(T x, int y)

   251 {

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

   253 }

   254 

   255 /**

   256  * Set a bit in a variable.

   257  *

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

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

   260  * starts at the LSB with 0.

   261  *

   262  * @param x The variable to set a bit

   263  * @param y The bit position to set

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

   265  */

   266 template<typename T> static inline T SETBIT(T& x, int y)

   267 {

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

   269 }

   270 

   271 /**

   272  * Clears a bit in a variable.

   273  *

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

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

   276  * to clear and starts at the LSB with 0.

   277  *

   278  * @param x The variable to clear the bit

   279  * @param y The bit position to clear

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

   281  */

   282 template<typename T> static inline T CLRBIT(T& x, int y)

   283 {

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

   285 }

   286 

   287 /**

   288  * Toggles a bit in a variable.

   289  *

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

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

   292  * to toggle and starts at the LSB with 0.

   293  *

   294  * @param x The varliable to toggle the bit

   295  * @param y The bit position to toggle

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

   297  */

   298 template<typename T> static inline T TOGGLEBIT(T& x, int y)

   299 {

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

   301 }

   302 

   303 

   304 /* checking more bits. Maybe unneccessary, but easy to use */

   305 /**

   306  * Check several bits in a value.

   307  *

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

   309  * value.

   310  *

   311  * @param x The first value

   312  * @param y The second value

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

   314  */

   315 #define HASBITS(x, y) ((x) & (y))

   316 

   317 /**

   318  * Sets several bits in a variable.

   319  *

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

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

   322  *

   323  * @param x The variable to set some bits

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

   325  * @return The new value of x

   326  */

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

   328 

   329 /**

   330  * Clears several bits in a variable.

   331  *

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

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

   334  *

   335  * @param x The variable to clear some bits

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

   337  * @return The new value of x

   338  */

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

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

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

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

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

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

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

   360  * 0.

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

    29  * The second variable will be cleared during the usage

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

    31  * @param i The position counter

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

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

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

    34 #define FOR_EACH_SET_BIT(i, b)            \

   366 

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

   367 /**

    36 		if (b & 1)

   368  * Returns a value with the first occured of a bit set to zero.

   369  *

   370  * Returns x with the first bit from LSB that is not zero set

   371  * to zero. So, 110100 returns 110000, 000001 returns 000000, etc.

   372  *

   373  * @param x The value to returned a new value

   374  * @return The value which the first bit is set to zero

   375  */

   376 #define KILL_FIRST_BIT(x) _ffb_64[(x) + 64]

   377 

   378 /**

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

   380  *

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

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

   383  * 0x3F3F (0011111100111111) and checks only the

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

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

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

   387  *

   388  * @param value The value to check the first bits

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

   390  * @see FIND_FIRST_BIT

   391  */

   392 static inline int FindFirstBit2x64(int value)

   393 {

   394 /*

   395 	int i = 0;

   396 	if ( (byte) value == 0) {

   397 		i += 8;

   398 		value >>= 8;

   399 	}

   400 	return i + FIND_FIRST_BIT(value & 0x3F);

   401 

   402 Faster ( or at least cleaner ) implementation below?

   403 */

   404 	if (GB(value, 0, 8) == 0) {

   405 		return FIND_FIRST_BIT(GB(value, 8, 6)) + 8;

   406 	} else {

   407 		return FIND_FIRST_BIT(GB(value, 0, 6));

   408 	}

   409 }

   410 

   411 /**

   412  * Clear the first bit in an integer.

   413  *

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

   415  * is cleared. This function checks, similar to FindFirstBit2x64,

   416  * the bits at 0x3F3F.

   417  *

   418  * @param value The value to clear the first bit

   419  * @return The new value with the first bit cleared

   420  * @see KILL_FIRST_BIT

   421  * @see FindFirstBit2x64

   422  */

   423 static inline int KillFirstBit2x64(int value)

   424 {

   425 	if (GB(value, 0, 8) == 0) {

   426 		return KILL_FIRST_BIT(GB(value, 8, 6)) << 8;

   427 	} else {

   428 		return value & (KILL_FIRST_BIT(GB(value, 0, 6)) | 0x3F00);

   429 	}

   430 }

   431 

   432 /**

   433  * Counts the number of set bits in a variable.

   434  *

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

   436  * @return the number of bits.

   437  */

   438 template<typename T> static inline uint COUNTBITS(T value)

   439 {

   440 	uint num;

   441 

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

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

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

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

   446 

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

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

   449 	}

   450 

   451 	return num;

   452 }

   453 

   454 /**

   455  * Returns true if value a has only one bit set to 1

   456  *

   457  * This macro returns true if only one bit is set.

   458  *

   459  * @param a The value to check

   460  * @return True if only one bit is set, false else

   461  */

   462 #define HAS_SINGLE_BIT(a) ( ((a) & ((a) - 1)) == 0)

   463 

   464 /**

   465  * Checks if a byte is in an interval.

   466  *

   467  * This macro returns true if a byte value is in the interval of [min, max).

   468  *

   469  * @param a The byte value to check

   470  * @param min The minimum of the interval

   471  * @param max The maximum of the interval

   472  * @see IS_INSIDE_1D

   473  */

   474 #define IS_BYTE_INSIDE(a, min, max) ((byte)((a) - (min)) < (byte)((max) - (min)))

   475 

   476 /**

   477  * Checks if an int is in an interval.

   478  *

   479  * This macro returns true if a integer value is in the interval of [min, max).

   480  *

   481  * @param a The integer value to check

   482  * @param min The minimum of the interval

   483  * @param max The maximum of the interval

   484  * @see IS_INSIDE_1D

   485  */

   486 #define IS_INT_INSIDE(a, min, max) ((uint)((a) - (min)) < (uint)((max) - (min)))

   487 

   488 /**

   489  * Flips a coin with a given probability.

   490  *

   491  * This macro can be used to get true or false randomized according to a

   492  * given probability. The parameter a and b create a percent value with

   493  * (a/b). The macro returns true in (a/b) percent.

   494  *

   495  * @param a The numerator of the fraction

   496  * @param b The denominator of the fraction, must of course not be null

   497  * @return True in (a/b) percent

   498  */

   499 #define CHANCE16(a, b) ((uint16)Random() <= (uint16)((65536 * (a)) / (b)))

   500 

   501 /**

   502  * Flips a coin with a given probability and saves the randomize-number in a variable.

   503  *

   504  * This macro uses the same parameters as the CHANCE16 marco. The third parameter

   505  * must be a variable the randomize-number from Random() is saved in.

   506  *

   507  * @param a The numerator of the fraction, see CHANCE16

   508  * @param b The denominator of the fraction, see CHANCE16

   509  * @param r The variable to save the randomize-number from Random()

   510  * @return True in (a/b) percent

   511  */

   512 #define CHANCE16R(a, b, r) ((uint16)(r = Random()) <= (uint16)((65536 * (a)) / (b)))

   513 

   514 /**

   515  * Checks if a given randomize-number is below a given probability.

   516  *

   517  * This macro is used to check if the given probability by the fraction of (a/b)

   518  * is greater than the given randomize-number v.

   519  *

   520  * @param a The numerator of the fraction, see CHANCE16

   521  * @param b The denominator of the fraction, see CHANCE16

   522  * @param v The given randomize-number

   523  * @return True if v is less or equals (a/b)

   524  */

   525 #define CHANCE16I(a, b, v) ((uint16)(v) <= (uint16)((65536 * (a)) / (b)))

   526 

   527 

   528 #define for_each_bit(_i, _b)            \

   529 	for (_i = 0; _b != 0; _i++, _b >>= 1) \

   530 		if (_b & 1)

   531 

   532 #define abs myabs