2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * @brief Functions from hackers delight.
24 * @author Sebastian Hack, Matthias Braun
26 #ifndef FIRM_ADT_BITFIDDLE_H
27 #define FIRM_ADT_BITFIDDLE_H
34 /* some functions here assume ints are 32 bit wide */
35 #define HACKDEL_WORDSIZE 32
36 COMPILETIME_ASSERT(sizeof(unsigned) == 4, unsignedsize)
37 COMPILETIME_ASSERT(UINT_MAX == 4294967295U, uintmax)
43 * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative.
45 * @note See hacker's delight, page 27.
47 static inline int add_saturated(int x, int y)
51 An overflow occurs, if the sign of the both summands is equal
52 and the one of the sum is different from the summand's one.
53 The sign bit is 1, if an overflow occurred, 0 otherwise.
54 int overflow = ~(x ^ y) & (sum ^ x);
56 int overflow = (x ^ sum) & (y ^ sum);
60 Make a mask of the sign bit of x and y (they are the same if an
62 INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes
65 int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
67 return overflow < 0 ? inf : sum;
71 * Compute the count of set bits in a 32-bit word.
72 * @param x A 32-bit word.
73 * @return The number of bits set in x.
75 static inline unsigned popcount(unsigned x)
77 #if defined(__GNUC__) && __GNUC__ >= 4
78 return __builtin_popcount(x);
80 x -= ((x >> 1) & 0x55555555);
81 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
82 x = (x + (x >> 4)) & 0x0f0f0f0f;
90 * Compute the number of leading zeros in a word.
92 * @return The number of leading (from the most significant bit) zeros.
94 static inline unsigned nlz(unsigned x)
96 #if defined(__GNUC__) && __GNUC__ >= 4
99 return __builtin_clz(x);
104 y = x >>16; if (y != 0) { n -= 16; x = y; }
105 y = x >> 8; if (y != 0) { n -= 8; x = y; }
106 y = x >> 4; if (y != 0) { n -= 4; x = y; }
107 y = x >> 2; if (y != 0) { n -= 2; x = y; }
108 y = x >> 1; if (y != 0) return n - 2;
114 * Compute the number of trailing zeros in a word.
116 * @return The number of trailing zeros.
118 static inline unsigned ntz(unsigned x)
120 #if defined(__GNUC__) && __GNUC__ >= 4
123 return __builtin_ctz(x);
125 return HACKDEL_WORDSIZE - nlz(~x & (x - 1));
130 * Compute the greatest power of 2 smaller or equal to a value.
131 * This is also known as the binary logarithm.
132 * @param x The value.
133 * @return The power of two.
135 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
138 * Compute the smallest power of 2 greater or equal to a value.
139 * This is also known as the binary logarithm.
140 * @param x The value.
141 * @return The power of two.
143 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
146 * Round up to the next multiple of a power of two.
148 * @param pot A power of two.
149 * @return x rounded up to the next multiple of pot.
151 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
154 * Returns the biggest power of 2 that is equal or smaller than @p x
155 * (see hackers delight power-of-2 boundaries, page 48)
157 static inline unsigned floor_po2(unsigned x)
159 #if defined(__GNUC__) && __GNUC__ >= 4 // in this case nlz is fast
162 // note that x != 0 here, so nlz(x) < 32!
163 return 0x80000000U >> nlz(x);
175 * Returns the smallest power of 2 that is equal or greater than x
176 * @remark x has to be <= 0x8000000 of course
177 * @note see hackers delight power-of-2 boundaries, page 48
179 static inline unsigned ceil_po2(unsigned x)
183 assert(x < (1U << 31));
185 #if defined(__GNUC__) && __GNUC__ >= 4 // in this case nlz is fast
186 // note that x != 0 here!
187 return 0x80000000U >> (nlz(x-1) - 1);
200 * Tests whether @p x is a power of 2
202 static inline int is_po2(unsigned x)
204 return (x & (x-1)) == 0;