ucw/bitops.h

   1 /*
   2  *      UCW Library -- Bit Operations
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  *      (c) 2012 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #ifndef _UCW_BITOPS_H
  12 #define _UCW_BITOPS_H
  13
  14 /* Find highest bit set (i.e., the floor of the binary logarithm) (bit-fls.c) */
  15
  16 int bit_fls(u32 x);             /* bit_fls(0)=-1 */
  17
  18 /* Find lowest bit set, undefined for zero argument (bit-ffs.c) */
  19
  20 extern const byte ffs_table[256];
  21
  22 #ifdef __pentium4               /* On other ia32 machines, the C version is faster */
  23
  24 static inline uns bit_ffs(uns w)
  25 {
  26   asm("bsfl %1,%0" :"=r" (w) :"rm" (w));
  27   return w;
  28 }
  29
  30 #else
  31
  32 static inline uns bit_ffs(uns w)
  33 {
  34   uns b = (w & 0xffff) ? 0 : 16;
  35   b += ((w >> b) & 0xff) ? 0 : 8;
  36   return b + ffs_table[(w >> b) & 0xff];
  37 }
  38
  39 #endif
  40
  41 /* Count the number of bits set */
  42
  43 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  44
  45 static inline uns bit_count(uns w)
  46 {
  47   return __builtin_popcount(w);
  48 }
  49
  50 #else
  51
  52 static inline uns bit_count(uns w)
  53 {
  54   uns n = 0;
  55   while (w)
  56     {
  57       w &= w - 1;
  58       n++;
  59     }
  60   return n;
  61 }
  62
  63 #endif
  64
  65 #endif