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