2 * This file is part of cparser.
3 * Copyright (C) 2012 Matthias Braun <matze@braunis.de>
9 * @brief Functions from hackers delight.
10 * @author Sebastian Hack, Matthias Braun
12 #ifndef _FIRM_BITFIDDLE_H_
13 #define _FIRM_BITFIDDLE_H_
18 /* some functions here assume ints are 32 bit wide */
19 #define HACKDEL_WORDSIZE 32
20 COMPILETIME_ASSERT(sizeof(unsigned) == 4, unsignedsize)
21 COMPILETIME_ASSERT(UINT_MAX == 4294967295U, uintmax)
27 * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative.
29 * @note See hacker's delight, page 27.
31 static inline __attribute__((const))
32 int add_saturated(int x, int y)
36 An overflow occurs, if the sign of the both summands is equal
37 and the one of the sum is different from the summand's one.
38 The sign bit is 1, if an overflow occurred, 0 otherwise.
39 int overflow = ~(x ^ y) & (sum ^ x);
41 int overflow = (x ^ sum) & (y ^ sum);
45 Make a mask of the sign bit of x and y (they are the same if an
47 INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes
50 int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
52 return overflow < 0 ? inf : sum;
56 * Compute the count of set bits in a 32-bit word.
57 * @param x A 32-bit word.
58 * @return The number of bits set in x.
60 static inline __attribute__((const))
61 unsigned popcnt(unsigned x) {
62 x -= ((x >> 1) & 0x55555555);
63 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
64 x = (x + (x >> 4)) & 0x0f0f0f0f;
71 * Compute the number of leading zeros in a word.
73 * @return The number of leading (from the most significant bit) zeros.
75 static inline __attribute__((const))
76 unsigned nlz(unsigned x) {
77 #ifdef USE_X86_ASSEMBLY
97 * Compute the number of trailing zeros in a word.
99 * @return The number of trailing zeros.
101 static inline __attribute__((const))
102 unsigned ntz(unsigned x) {
103 #ifdef USE_X86_ASSEMBLY
113 return HACKDEL_WORDSIZE - nlz(~x & (x - 1));
118 * Compute the greatest power of 2 smaller or equal to a value.
119 * This is also known as the binary logarithm.
120 * @param x The value.
121 * @return The power of two.
123 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
126 * Compute the smallest power of 2 greater or equal to a value.
127 * This is also known as the binary logarithm.
128 * @param x The value.
129 * @return The power of two.
131 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
134 * Round up to the next multiple of a power of two.
136 * @param pot A power of two.
137 * @return x rounded up to the next multiple of pot.
139 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
142 * Returns the biggest power of 2 that is equal or smaller than @p x
143 * (see hackers delight power-of-2 boundaries, page 48)
145 static inline __attribute__((const))
146 unsigned floor_po2(unsigned x)
148 #ifdef USE_X86_ASSEMBLY // in this case nlz is fast
151 // note that x != 0 here, so nlz(x) < 32!
152 return 0x80000000U >> nlz(x);
164 * Returns the smallest power of 2 that is equal or greater than x
165 * @remark x has to be <= 0x8000000 of course
166 * @note see hackers delight power-of-2 boundaries, page 48
168 static inline __attribute__((const))
169 unsigned ceil_po2(unsigned x)
173 assert(x < (1U << 31));
175 #ifdef USE_X86_ASSEMBLY // in this case nlz is fast
176 // note that x != 0 here!
177 return 0x80000000U >> (nlz(x-1) - 1);
190 * Tests whether @p x is a power of 2
192 static inline __attribute__((const))
193 int is_po2(unsigned x)
195 return (x & (x-1)) == 0;