nsz Git - libfirm/blob - include/libfirm/adt/bitfiddle.h

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @date    28.9.2004
  23  * @brief   Functions from hackers delight.
  24  * @author  Sebastian Hack, Matthias Braun
  25  * @version $Id$
  26  */
  27 #ifndef FIRM_ADT_BITFIDDLE_H
  28 #define FIRM_ADT_BITFIDDLE_H
  29
  30 #include <limits.h>
  31 #include <assert.h>
  32 #include "util.h"
  33
  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)
  38
  39 /**
  40  * Add saturated.
  41  * @param x Summand 1.
  42  * @param y Summand 2.
  43  * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative.
  44  *
  45  * @note See hacker's delight, page 27.
  46  */
  47 static INLINE __attribute__((const))
  48 int add_saturated(int x, int y)
  49 {
  50         int sum      = x + y;
  51         /*
  52                 An overflow occurs, if the sign of the both summands is equal
  53                 and the one of the sum is different from the summand's one.
  54                 The sign bit is 1, if an overflow occurred, 0 otherwise.
  55                 int overflow = ~(x ^ y) & (sum ^ x);
  56         */
  57         int overflow = (x ^ sum) & (y ^ sum);
  58
  59         /*
  60                 The infinity to use.
  61                 Make a mask of the sign bit of x and y (they are the same if an
  62                 overflow occurred).
  63                 INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes
  64                 INT_MIN.
  65         */
  66         int inf = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
  67
  68         return overflow < 0 ? inf : sum;
  69 }
  70
  71 /**
  72  * Compute the count of set bits in a 32-bit word.
  73  * @param x A 32-bit word.
  74  * @return The number of bits set in x.
  75  */
  76 static INLINE __attribute__((const))
  77 unsigned popcnt(unsigned x) {
  78         x -= ((x >> 1) & 0x55555555);
  79         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  80         x = (x + (x >> 4)) & 0x0f0f0f0f;
  81         x += x >> 8;
  82         x += x >> 16;
  83         return x & 0x3f;
  84 }
  85
  86 /**
  87  * Compute the number of leading zeros in a word.
  88  * @param x The word.
  89  * @return The number of leading (from the most significant bit) zeros.
  90  */
  91 static INLINE __attribute__((const))
  92 unsigned nlz(unsigned x) {
  93 #ifdef USE_X86_ASSEMBLY
  94         unsigned res;
  95         if(x == 0)
  96                 return 32;
  97
  98         __asm__("bsrl %1,%0"
  99                         : "=r" (res)
 100                         : "r" (x));
 101         return 31 - res;
 102 #else
 103    unsigned y;
 104    int n = 32;
 105
 106    y = x >>16;  if (y != 0) { n -= 16;  x = y; }
 107    y = x >> 8;  if (y != 0) { n -=  8;  x = y; }
 108    y = x >> 4;  if (y != 0) { n -=  4;  x = y; }
 109    y = x >> 2;  if (y != 0) { n -=  2;  x = y; }
 110    y = x >> 1;  if (y != 0) return n - 2;
 111    return n - x;
 112 #endif
 113 }
 114
 115 /**
 116  * Compute the number of trailing zeros in a word.
 117  * @param x The word.
 118  * @return The number of trailing zeros.
 119  */
 120 static INLINE __attribute__((const))
 121 unsigned ntz(unsigned x) {
 122 #ifdef USE_X86_ASSEMBLY
 123         unsigned res;
 124         if(x == 0)
 125                 return 32;
 126
 127         __asm__("bsfl %1,%0"
 128                         : "=r" (res)
 129                         : "r" (x));
 130         return  res;
 131 #else
 132         return HACKDEL_WORDSIZE - nlz(~x & (x - 1));
 133 #endif
 134 }
 135
 136 /**
 137  * Compute the greatest power of 2 smaller or equal to a value.
 138  * This is also known as the binary logarithm.
 139  * @param x The value.
 140  * @return The power of two.
 141  */
 142 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
 143
 144 /**
 145  * Compute the smallest power of 2 greater or equal to a value.
 146  * This is also known as the binary logarithm.
 147  * @param x The value.
 148  * @return The power of two.
 149  */
 150 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
 151
 152 /**
 153  * Round up to the next multiple of a power of two.
 154  * @param x A value.
 155  * @param pot A power of two.
 156  * @return x rounded up to the next multiple of pot.
 157  */
 158 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
 159
 160 /**
 161  * Returns the biggest power of 2 that is equal or smaller than @p x
 162  * (see hackers delight power-of-2 boundaries, page 48)
 163  */
 164 static INLINE __attribute__((const))
 165 unsigned floor_po2(unsigned x)
 166 {
 167 #ifdef USE_X86_ASSEMBLY // in this case nlz is fast
 168         if(x == 0)
 169                 return 0;
 170         // note that x != 0 here, so nlz(x) < 32!
 171         return 0x80000000U >> nlz(x);
 172 #else
 173         x |= x >> 1;
 174         x |= x >> 2;
 175         x |= x >> 4;
 176         x |= x >> 8;
 177         x |= x >> 16;
 178         return x - (x >> 1);
 179 #endif
 180 }
 181
 182 /**
 183  * Returns the smallest power of 2 that is equal or greater than x
 184  * @remark x has to be <= 0x8000000 of course
 185  * @note see hackers delight power-of-2 boundaries, page 48
 186  */
 187 static INLINE __attribute__((const))
 188 unsigned ceil_po2(unsigned x)
 189 {
 190         if(x == 0)
 191                 return 0;
 192         assert(x < (1U << 31));
 193
 194 #ifdef USE_X86_ASSEMBLY // in this case nlz is fast
 195         // note that x != 0 here!
 196         return 0x80000000U >> (nlz(x-1) - 1);
 197 #else
 198         x = x - 1;
 199         x |= x >> 1;
 200         x |= x >> 2;
 201         x |= x >> 4;
 202         x |= x >> 8;
 203         x |= x >> 16;
 204         return x + 1;
 205 #endif
 206 }
 207
 208 /**
 209  * Tests whether @p x is a power of 2
 210  */
 211 static INLINE __attribute__((const))
 212 int is_po2(unsigned x)
 213 {
 214         return (x & (x-1)) == 0;
 215 }
 216
 217 #endif