X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitfiddle.h;h=ebf76c10fa5484fdb242b11549e3c0a665a47896;hb=3da5ed2598245b896255bc444aaa1768f6098cfe;hp=d51b40552800b6851a712bba833690503a0b33dc;hpb=ed68ef335c85f51d542de75a52111527269860ea;p=libfirm diff --git a/ir/adt/bitfiddle.h b/ir/adt/bitfiddle.h index d51b40552..ebf76c10f 100644 --- a/ir/adt/bitfiddle.h +++ b/ir/adt/bitfiddle.h @@ -1,53 +1,131 @@ -/** - * @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. * - * Attention! These functions silently assume, that an int is 32 bit wide. - * $Id$ + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * 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 "compiler.h" -#include "firm_config.h" +#include +#include +/* 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. + * @param x Summand 1. + * @param y Summand 2. + * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative. + * + * @note See hacker's delight, page 27. + */ +static inline int add_saturated(int x, int y) +{ + int sum = x + y; + /* + An overflow occurs, if the sign of the both summands is equal + and the one of the sum is different from the summand's one. + The sign bit is 1, if an overflow occurred, 0 otherwise. + int overflow = ~(x ^ y) & (sum ^ x); + */ + int overflow = (x ^ sum) & (y ^ sum); + + /* + 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. + */ + int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX; + + return overflow < 0 ? inf : sum; +} /** * Compute the count of set bits in a 32-bit word. * @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 popcount(unsigned x) +{ +#if defined(__GNUC__) && __GNUC__ >= 4 + return __builtin_popcount(x); +#else + x -= ((x >> 1) & 0x55555555); + x = (x & 0x33333333) + ((x >> 2) & 0x33333333); + x = (x + (x >> 4)) & 0x0f0f0f0f; + x += x >> 8; + x += x >> 16; + return x & 0x3f; +#endif } /** - * 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) +{ +#if defined(__GNUC__) && __GNUC__ >= 4 + if(x == 0) + return 32; + return __builtin_clz(x); +#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) +{ +#if defined(__GNUC__) && __GNUC__ >= 4 + if(x == 0) + return 32; + return __builtin_ctz(x); +#else + return HACKDEL_WORDSIZE - nlz(~x & (x - 1)); +#endif +} /** * Compute the greatest power of 2 smaller or equal to a value. @@ -73,5 +151,58 @@ static INLINE unsigned nlz(unsigned x) { */ #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) +{ +#if defined(__GNUC__) && __GNUC__ >= 4 // 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)); + +#if defined(__GNUC__) && __GNUC__ >= 4 // 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