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 170