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
  80 static inline int generic_fls64(__u64 x)
  81 {
  82         __u32 h = x >> 32;
  83         if (h)
  84                 return fls(h) + 32;
  85         return fls(x);
  86 }
  87
  88 static __inline__ int get_bitmask_order(unsigned int count)
  89 {
  90         int order;
  91
  92         order = fls(count);
  93         return order;   /* We could be slightly more clever with -1 here... */
  94 }
  95
  96 static __inline__ int get_count_order(unsigned int count)
  97 {
  98         int order;
  99
 100         order = fls(count) - 1;
 101         if (count & (count - 1))
 102                 order++;
 103         return order;
 104 }
 105
 106 /*
 107  * hweightN: returns the hamming weight (i.e. the number
 108  * of bits set) of a N-bit word
 109  */
 110
 111 static inline unsigned int generic_hweight32(unsigned int w)
 112 {
 113         unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
 114         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
 115         res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
 116         res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
 117         return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
 118 }
 119
 120 static inline unsigned int generic_hweight16(unsigned int w)
 121 {
 122         unsigned int res = (w & 0x5555) + ((w >> 1) & 0x5555);
 123         res = (res & 0x3333) + ((res >> 2) & 0x3333);
 124         res = (res & 0x0F0F) + ((res >> 4) & 0x0F0F);
 125         return (res & 0x00FF) + ((res >> 8) & 0x00FF);
 126 }
 127
 128 static inline unsigned int generic_hweight8(unsigned int w)
 129 {
 130         unsigned int res = (w & 0x55) + ((w >> 1) & 0x55);
 131         res = (res & 0x33) + ((res >> 2) & 0x33);
 132         return (res & 0x0F) + ((res >> 4) & 0x0F);
 133 }
 134
 135 static inline unsigned long generic_hweight64(__u64 w)
 136 {
 137 #if BITS_PER_LONG < 64
 138         return generic_hweight32((unsigned int)(w >> 32)) +
 139                                 generic_hweight32((unsigned int)w);
 140 #else
 141         u64 res;
 142         res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul);
 143         res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
 144         res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful);
 145         res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul);
 146         res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul);
 147         return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul);
 148 #endif
 149 }
 150
 151 static inline unsigned long hweight_long(unsigned long w)
 152 {
 153         return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
 154 }
 155
 156 /*
 157  * rol32 - rotate a 32-bit value left
 158  *
 159  * @word: value to rotate
 160  * @shift: bits to roll
 161  */
 162 static inline __u32 rol32(__u32 word, unsigned int shift)
 163 {
 164         return (word << shift) | (word >> (32 - shift));
 165 }
 166
 167 /*
 168  * ror32 - rotate a 32-bit value right
 169  *
 170  * @word: value to rotate
 171  * @shift: bits to roll
 172  */
 173 static inline __u32 ror32(__u32 word, unsigned int shift)
 174 {
 175         return (word >> shift) | (word << (32 - shift));
 176 }
 177
 178 static inline unsigned fls_long(unsigned long l)
 179 {
 180         if (sizeof(l) == 4)
 181                 return fls(l);
 182         return fls64(l);
 183 }
 184
 185 #endif