4 * @brief Functions from hackers delight.
6 * Attention! These functions silently assume, that an int is 32 bit wide.
10 #ifndef __FIRM_HACKDEL_H
11 #define __FIRM_HACKDEL_H
15 #include "firm_config.h"
17 #define HACKDEL_WORDSIZE 32
23 * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative.
25 * @note See hacker's delight, page 27.
27 static INLINE int add_saturated(int x, int y)
31 An overflow occurs, if the sign of the both summands is equal
32 and the one of the sum is different from the summand's one.
33 The sign bit is 1, if an overflow occurred, 0 otherwise.
34 int overflow = ~(x ^ y) & (sum ^ x);
36 int overflow = (x ^ sum) & (y ^ sum);
40 Make a mask of the sign bit of x and y (they are the same if an overflow occurred).
41 INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes INT_MIN.
43 int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
45 return overflow < 0 ? inf : sum;
49 * Compute the count of set bits in a 32-bit word.
50 * @param x A 32-bit word.
51 * @return The number of bits set in x.
53 static INLINE unsigned popcnt(unsigned x) {
54 x = x - ((x >> 1) & 0x55555555);
55 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
56 x = (x + (x >> 4)) & 0x0f0f0f0f;
63 * Compute the number of leading zeros in a word.
65 * @return The number of leading (from the most significant bit) zeros.
67 static INLINE unsigned nlz(unsigned x) {
77 * Compute the number of trailing zeros in a word.
79 * @return The number of trailing zeros.
81 #define ntz(x) (HACKDEL_WORDSIZE - nlz(~(x) & ((x) - 1)))
84 * Compute the greatest power of 2 smaller or equal to a value.
85 * This is also known as the binary logarithm.
87 * @return The power of two.
89 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
92 * Compute the smallest power of 2 greater or equal to a value.
93 * This is also known as the binary logarithm.
95 * @return The power of two.
97 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
100 * Round up to the next multiple of a power of two.
102 * @param pot A power of two.
103 * @return x rounded up to the next multiple of pot.
105 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))