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

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