-/**
- * @file bitfiddle.h
- * @date 28.9.2004
- * @brief Functions from hackers delight.
+/*
+ * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
*
- * Attention! These functions silently assume, that an int is 32 bit wide.
- * $Id$
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
*/
-#ifndef __FIRM_HACKDEL_H
-#define __FIRM_HACKDEL_H
+/**
+ * @file
+ * @date 28.9.2004
+ * @brief Functions from hackers delight.
+ * @author Sebastian Hack, Matthias Braun
+ * @version $Id$
+ */
+#ifndef FIRM_ADT_BITFIDDLE_H
+#define FIRM_ADT_BITFIDDLE_H
-#include <limits.h>
+#include "compiler.h"
-#include "firm_config.h"
+#include <limits.h>
+#include <assert.h>
+/* some functions here assume ints are 32 bit wide */
#define HACKDEL_WORDSIZE 32
+COMPILETIME_ASSERT(sizeof(unsigned) == 4, unsignedsize)
+COMPILETIME_ASSERT(UINT_MAX == 4294967295U, uintmax)
/**
* Add saturated.
*
* @note See hacker's delight, page 27.
*/
-static INLINE int add_saturated(int x, int y)
+static inline
+int add_saturated(int x, int y)
{
int sum = x + y;
/*
/*
The infinity to use.
- Make a mask of the sign bit of x and y (they are the same if an overflow occurred).
- INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes INT_MIN.
+ Make a mask of the sign bit of x and y (they are the same if an
+ overflow occurred).
+ INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes
+ INT_MIN.
*/
- int inf = (x >> sizeof(x) * 8 - 1) ^ INT_MAX;
+ int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
return overflow < 0 ? inf : sum;
}
* @param x A 32-bit word.
* @return The number of bits set in x.
*/
-static INLINE unsigned popcnt(unsigned x) {
- x = x - ((x >> 1) & 0x55555555);
- x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
- x = (x + (x >> 4)) & 0x0f0f0f0f;
- x = x + (x >> 8);
- x = x + (x >> 16);
- return x & 0x3f;
+static inline
+unsigned popcnt(unsigned x) {
+ x -= ((x >> 1) & 0x55555555);
+ x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+ x = (x + (x >> 4)) & 0x0f0f0f0f;
+ x += x >> 8;
+ x += x >> 16;
+ return x & 0x3f;
}
/**
- * Compute the number of leading zeroes in a word.
+ * Compute the number of leading zeros in a word.
* @param x The word.
- * @return The number of leading (from the most significant bit) zeroes.
+ * @return The number of leading (from the most significant bit) zeros.
*/
-static INLINE unsigned nlz(unsigned x) {
- x |= x >> 1;
- x |= x >> 2;
- x |= x >> 4;
- x |= x >> 8;
- x |= x >> 16;
- return popcnt(~x);
+static inline
+unsigned nlz(unsigned x) {
+#ifdef USE_X86_ASSEMBLY
+ unsigned res;
+ if(x == 0)
+ return 32;
+
+ __asm__("bsrl %1,%0"
+ : "=r" (res)
+ : "r" (x));
+ return 31 - res;
+#else
+ unsigned y;
+ int n = 32;
+
+ y = x >>16; if (y != 0) { n -= 16; x = y; }
+ y = x >> 8; if (y != 0) { n -= 8; x = y; }
+ y = x >> 4; if (y != 0) { n -= 4; x = y; }
+ y = x >> 2; if (y != 0) { n -= 2; x = y; }
+ y = x >> 1; if (y != 0) return n - 2;
+ return n - x;
+#endif
}
/**
- * Compute the number of trailing zeroes in a word.
+ * Compute the number of trailing zeros in a word.
* @param x The word.
- * @return The number of trailing zeroes.
+ * @return The number of trailing zeros.
*/
-#define ntz(x) (HACKDEL_WORDSIZE - nlz(~(x) & ((x) - 1)))
+static inline
+unsigned ntz(unsigned x) {
+#ifdef USE_X86_ASSEMBLY
+ unsigned res;
+ if(x == 0)
+ return 32;
+
+ __asm__("bsfl %1,%0"
+ : "=r" (res)
+ : "r" (x));
+ return res;
+#else
+ return HACKDEL_WORDSIZE - nlz(~x & (x - 1));
+#endif
+}
/**
* Compute the greatest power of 2 smaller or equal to a value.
*/
#define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
+/**
+ * Returns the biggest power of 2 that is equal or smaller than @p x
+ * (see hackers delight power-of-2 boundaries, page 48)
+ */
+static inline
+unsigned floor_po2(unsigned x)
+{
+#ifdef USE_X86_ASSEMBLY // in this case nlz is fast
+ if(x == 0)
+ return 0;
+ // note that x != 0 here, so nlz(x) < 32!
+ return 0x80000000U >> nlz(x);
+#else
+ x |= x >> 1;
+ x |= x >> 2;
+ x |= x >> 4;
+ x |= x >> 8;
+ x |= x >> 16;
+ return x - (x >> 1);
+#endif
+}
+
+/**
+ * Returns the smallest power of 2 that is equal or greater than x
+ * @remark x has to be <= 0x8000000 of course
+ * @note see hackers delight power-of-2 boundaries, page 48
+ */
+static inline
+unsigned ceil_po2(unsigned x)
+{
+ if(x == 0)
+ return 0;
+ assert(x < (1U << 31));
+
+#ifdef USE_X86_ASSEMBLY // in this case nlz is fast
+ // note that x != 0 here!
+ return 0x80000000U >> (nlz(x-1) - 1);
+#else
+ x = x - 1;
+ x |= x >> 1;
+ x |= x >> 2;
+ x |= x >> 4;
+ x |= x >> 8;
+ x |= x >> 16;
+ return x + 1;
+#endif
+}
+/**
+ * Tests whether @p x is a power of 2
+ */
+static inline
+int is_po2(unsigned x)
+{
+ return (x & (x-1)) == 0;
+}
#endif
projects / libfirm / blobdiff