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

   1 /**
   2  * @file bitfiddle.h
   3  * @date 28.9.2004
   4  * @brief Functions from hackers delight.
   5  *
   6  * Attention! These functions silently assume, that an int is 32 bit wide.
   7  * $Id$
   8  */
   9
  10 #ifndef __FIRM_HACKDEL_H
  11 #define __FIRM_HACKDEL_H
  12
  13 #include <limits.h>
  14
  15 #include "firm_config.h"
  16
  17 #define HACKDEL_WORDSIZE 32
  18
  19 /**
  20  * Add saturated.
  21  * @param x Summand 1.
  22  * @param y Summand 2.
  23  * @return x + y or INT_MAX/INT_MIN if an overflow occurred and x,y was positive/negative.
  24  *
  25  * @note See hacker's delight, page 27.
  26  */
  27 static INLINE int add_saturated(int x, int y)
  28 {
  29         int sum      = x + y;
  30         /*
  31                 An overflow occurs, if the sign of the both summands is equal
  32                 and the one of the sum is different from the summand's one.
  33                 The sign bit is 1, if an overflow occurred, 0 otherwise.
  34                 int overflow = ~(x ^ y) & (sum ^ x);
  35         */
  36         int overflow = (x ^ sum) & (y ^ sum);
  37
  38         /*
  39                 The infinity to use.
  40                 Make a mask of the sign bit of x and y (they are the same if an overflow occurred).
  41                 INT_MIN == ~INT_MAX, so if the sign was negative, INT_MAX becomes INT_MIN.
  42         */
  43         int inf      = (x >> (sizeof(x) * 8 - 1)) ^ INT_MAX;
  44
  45         return overflow < 0 ? inf : sum;
  46 }
  47
  48 /**
  49  * Compute the count of set bits in a 32-bit word.
  50  * @param x A 32-bit word.
  51  * @return The number of bits set in x.
  52  */
  53 static INLINE unsigned popcnt(unsigned x) {
  54   x = x - ((x >> 1) & 0x55555555);
  55   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  56   x = (x + (x >> 4)) & 0x0f0f0f0f;
  57   x = x + (x >> 8);
  58   x = x + (x >> 16);
  59   return x & 0x3f;
  60 }
  61
  62 /**
  63  * Compute the number of leading zeros in a word.
  64  * @param x The word.
  65  * @return The number of leading (from the most significant bit) zeros.
  66  */
  67 static INLINE unsigned nlz(unsigned x) {
  68   x |= x >> 1;
  69   x |= x >> 2;
  70   x |= x >> 4;
  71   x |= x >> 8;
  72   x |= x >> 16;
  73   return popcnt(~x);
  74 }
  75
  76 /**
  77  * Compute the number of trailing zeros in a word.
  78  * @param x The word.
  79  * @return The number of trailing zeros.
  80  */
  81 #define ntz(x) (HACKDEL_WORDSIZE - nlz(~(x) & ((x) - 1)))
  82
  83 /**
  84  * Compute the greatest power of 2 smaller or equal to a value.
  85  * This is also known as the binary logarithm.
  86  * @param x The value.
  87  * @return The power of two.
  88  */
  89 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
  90
  91 /**
  92  * Compute the smallest power of 2 greater or equal to a value.
  93  * This is also known as the binary logarithm.
  94  * @param x The value.
  95  * @return The power of two.
  96  */
  97 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
  98
  99 /**
 100  * Round up to the next multiple of a power of two.
 101  * @param x A value.
 102  * @param pot A power of two.
 103  * @return x rounded up to the next multiple of pot.
 104  */
 105 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
 106
 107
 108
 109 #endif