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