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 "firm_config.h"
  14
  15 #define HACKDEL_WORDSIZE 32
  16
  17 /**
  18  * Compute the count of set bits in a 32-bit word.
  19  * @param x A 32-bit word.
  20  * @return The number of bits set in x.
  21  */
  22 static INLINE unsigned popcnt(unsigned x) {
  23   x = x - ((x >> 1) & 0x55555555);
  24   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  25   x = (x + (x >> 4)) & 0x0f0f0f0f;
  26   x = x + (x >> 8);
  27   x = x + (x >> 16);
  28   return x & 0x3f;
  29 }
  30
  31 /**
  32  * Compute the number of leading zeroes in a word.
  33  * @param x The word.
  34  * @return The number of leading (from the most significant bit) zeroes.
  35  */
  36 static INLINE unsigned nlz(unsigned x) {
  37   x |= x >> 1;
  38   x |= x >> 2;
  39   x |= x >> 4;
  40   x |= x >> 8;
  41   x |= x >> 16;
  42   return popcnt(~x);
  43 }
  44
  45 /**
  46  * Compute the number of trailing zeroes in a word.
  47  * @param x The word.
  48  * @return The number of trailing zeroes.
  49  */
  50 #define ntz(x) (HACKDEL_WORDSIZE - nlz(~(x) & ((x) - 1)))
  51
  52 /**
  53  * Compute the greatest power of 2 smaller or equal to a value.
  54  * This is also known as the binary logarithm.
  55  * @param x The value.
  56  * @return The power of two.
  57  */
  58 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
  59
  60 /**
  61  * Compute the smallest power of 2 greater or equal to a value.
  62  * This is also known as the binary logarithm.
  63  * @param x The value.
  64  * @return The power of two.
  65  */
  66 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
  67
  68 /**
  69  * Round up to the next multiple of a power of two.
  70  * @param x A value.
  71  * @param pot A power of two.
  72  * @return x rounded up to the next multiple of pot.
  73  */
  74 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))
  75
  76
  77 #endif