include/linux/bitops.h

   1 #ifndef _LINUX_BITOPS_H
   2 #define _LINUX_BITOPS_H
   3 #include <asm/types.h>
   4
   5 /*
   6  * ffs: find first bit set. This is defined the same way as
   7  * the libc and compiler builtin ffs routines, therefore
   8  * differs in spirit from the above ffz (man ffs).
   9  */
  10
  11 static inline int generic_ffs(int x)
  12 {
  13         int r = 1;
  14
  15         if (!x)
  16                 return 0;
  17         if (!(x & 0xffff)) {
  18                 x >>= 16;
  19                 r += 16;
  20         }
  21         if (!(x & 0xff)) {
  22                 x >>= 8;
  23                 r += 8;
  24         }
  25         if (!(x & 0xf)) {
  26                 x >>= 4;
  27                 r += 4;
  28         }
  29         if (!(x & 3)) {
  30                 x >>= 2;
  31                 r += 2;
  32         }
  33         if (!(x & 1)) {
  34                 x >>= 1;
  35                 r += 1;
  36         }
  37         return r;
  38 }
  39
  40 /*
  41  * fls: find last bit set.
  42  */
  43
  44 static __inline__ int generic_fls(int x)
  45 {
  46         int r = 32;
  47
  48         if (!x)
  49                 return 0;
  50         if (!(x & 0xffff0000u)) {
  51                 x <<= 16;
  52                 r -= 16;
  53         }
  54         if (!(x & 0xff000000u)) {
  55                 x <<= 8;
  56                 r -= 8;
  57         }
  58         if (!(x & 0xf0000000u)) {
  59                 x <<= 4;
  60                 r -= 4;
  61         }
  62         if (!(x & 0xc0000000u)) {
  63                 x <<= 2;
  64                 r -= 2;
  65         }
  66         if (!(x & 0x80000000u)) {
  67                 x <<= 1;
  68                 r -= 1;
  69         }
  70         return r;
  71 }
  72
  73 /*
  74  * Include this here because some architectures need generic_ffs/fls in
  75  * scope
  76  */
  77 #include <asm/bitops.h>
  78
  79 static __inline__ int get_bitmask_order(unsigned int count)
  80 {
  81         int order;
  82
  83         order = fls(count);
  84         return order;   /* We could be slightly more clever with -1 here... */
  85 }
  86
  87 /*
  88  * hweightN: returns the hamming weight (i.e. the number
  89  * of bits set) of a N-bit word
  90  */
  91
  92 static inline unsigned int generic_hweight32(unsigned int w)
  93 {
  94         unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
  95         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
  96         res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
  97         res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
  98         return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
  99 }
 100
 101 static inline unsigned int generic_hweight16(unsigned int w)
 102 {
 103         unsigned int res = (w & 0x5555) + ((w >> 1) & 0x5555);
 104         res = (res & 0x3333) + ((res >> 2) & 0x3333);
 105         res = (res & 0x0F0F) + ((res >> 4) & 0x0F0F);
 106         return (res & 0x00FF) + ((res >> 8) & 0x00FF);
 107 }
 108
 109 static inline unsigned int generic_hweight8(unsigned int w)
 110 {
 111         unsigned int res = (w & 0x55) + ((w >> 1) & 0x55);
 112         res = (res & 0x33) + ((res >> 2) & 0x33);
 113         return (res & 0x0F) + ((res >> 4) & 0x0F);
 114 }
 115
 116 static inline unsigned long generic_hweight64(__u64 w)
 117 {
 118 #if BITS_PER_LONG < 64
 119         return generic_hweight32((unsigned int)(w >> 32)) +
 120                                 generic_hweight32((unsigned int)w);
 121 #else
 122         u64 res;
 123         res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul);
 124         res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
 125         res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful);
 126         res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul);
 127         res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul);
 128         return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul);
 129 #endif
 130 }
 131
 132 static inline unsigned long hweight_long(unsigned long w)
 133 {
 134         return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
 135 }
 136
 137 /*
 138  * rol32 - rotate a 32-bit value left
 139  *
 140  * @word: value to rotate
 141  * @shift: bits to roll
 142  */
 143 static inline __u32 rol32(__u32 word, unsigned int shift)
 144 {
 145         return (word << shift) | (word >> (32 - shift));
 146 }
 147
 148 /*
 149  * ror32 - rotate a 32-bit value right
 150  *
 151  * @word: value to rotate
 152  * @shift: bits to roll
 153  */
 154 static inline __u32 ror32(__u32 word, unsigned int shift)
 155 {
 156         return (word >> shift) | (word << (32 - shift));
 157 }
 158
 159 #endif