nsz Git - cparser/blob - adt/bitfiddle.h

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