• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #ifndef _PERF_LINUX_BITOPS_H_
2 #define _PERF_LINUX_BITOPS_H_
3 
4 #include <linux/kernel.h>
5 #include <linux/compiler.h>
6 #include <asm/hweight.h>
7 
8 #ifdef __APPLE__
9 #define __SIZEOF_LONG__ 4
10 #endif
11 
12 #ifndef __WORDSIZE
13 #define __WORDSIZE (__SIZEOF_LONG__ * 8)
14 #endif
15 
16 #define BITS_PER_LONG __WORDSIZE
17 #define BITS_PER_BYTE           8
18 #define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
19 #define BITS_TO_U64(nr)         DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64))
20 #define BITS_TO_U32(nr)         DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32))
21 #define BITS_TO_BYTES(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE)
22 
23 #define for_each_set_bit(bit, addr, size) \
24 	for ((bit) = find_first_bit((addr), (size));		\
25 	     (bit) < (size);					\
26 	     (bit) = find_next_bit((addr), (size), (bit) + 1))
27 
28 /* same as for_each_set_bit() but use bit as value to start with */
29 #define for_each_set_bit_from(bit, addr, size) \
30 	for ((bit) = find_next_bit((addr), (size), (bit));	\
31 	     (bit) < (size);					\
32 	     (bit) = find_next_bit((addr), (size), (bit) + 1))
33 
set_bit(int nr,unsigned long * addr)34 static inline void set_bit(int nr, unsigned long *addr)
35 {
36 	addr[nr / BITS_PER_LONG] |= 1UL << (nr % BITS_PER_LONG);
37 }
38 
clear_bit(int nr,unsigned long * addr)39 static inline void clear_bit(int nr, unsigned long *addr)
40 {
41 	addr[nr / BITS_PER_LONG] &= ~(1UL << (nr % BITS_PER_LONG));
42 }
43 
test_bit(unsigned int nr,const unsigned long * addr)44 static __always_inline int test_bit(unsigned int nr, const unsigned long *addr)
45 {
46 	return ((1UL << (nr % BITS_PER_LONG)) &
47 		(((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0;
48 }
49 
hweight_long(unsigned long w)50 static inline unsigned long hweight_long(unsigned long w)
51 {
52 	return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
53 }
54 
55 #define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
56 
57 /**
58  * __ffs - find first bit in word.
59  * @word: The word to search
60  *
61  * Undefined if no bit exists, so code should check against 0 first.
62  */
__ffs(unsigned long word)63 static __always_inline unsigned long __ffs(unsigned long word)
64 {
65 	int num = 0;
66 
67 #if BITS_PER_LONG == 64
68 	if ((word & 0xffffffff) == 0) {
69 		num += 32;
70 		word >>= 32;
71 	}
72 #endif
73 	if ((word & 0xffff) == 0) {
74 		num += 16;
75 		word >>= 16;
76 	}
77 	if ((word & 0xff) == 0) {
78 		num += 8;
79 		word >>= 8;
80 	}
81 	if ((word & 0xf) == 0) {
82 		num += 4;
83 		word >>= 4;
84 	}
85 	if ((word & 0x3) == 0) {
86 		num += 2;
87 		word >>= 2;
88 	}
89 	if ((word & 0x1) == 0)
90 		num += 1;
91 	return num;
92 }
93 
94 /*
95  * Find the first set bit in a memory region.
96  */
97 static inline unsigned long
find_first_bit(const unsigned long * addr,unsigned long size)98 find_first_bit(const unsigned long *addr, unsigned long size)
99 {
100 	const unsigned long *p = addr;
101 	unsigned long result = 0;
102 	unsigned long tmp;
103 
104 	while (size & ~(BITS_PER_LONG-1)) {
105 		if ((tmp = *(p++)))
106 			goto found;
107 		result += BITS_PER_LONG;
108 		size -= BITS_PER_LONG;
109 	}
110 	if (!size)
111 		return result;
112 
113 	tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
114 	if (tmp == 0UL)		/* Are any bits set? */
115 		return result + size;	/* Nope. */
116 found:
117 	return result + __ffs(tmp);
118 }
119 
120 /*
121  * Find the next set bit in a memory region.
122  */
123 static inline unsigned long
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)124 find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset)
125 {
126 	const unsigned long *p = addr + BITOP_WORD(offset);
127 	unsigned long result = offset & ~(BITS_PER_LONG-1);
128 	unsigned long tmp;
129 
130 	if (offset >= size)
131 		return size;
132 	size -= result;
133 	offset %= BITS_PER_LONG;
134 	if (offset) {
135 		tmp = *(p++);
136 		tmp &= (~0UL << offset);
137 		if (size < BITS_PER_LONG)
138 			goto found_first;
139 		if (tmp)
140 			goto found_middle;
141 		size -= BITS_PER_LONG;
142 		result += BITS_PER_LONG;
143 	}
144 	while (size & ~(BITS_PER_LONG-1)) {
145 		if ((tmp = *(p++)))
146 			goto found_middle;
147 		result += BITS_PER_LONG;
148 		size -= BITS_PER_LONG;
149 	}
150 	if (!size)
151 		return result;
152 	tmp = *p;
153 
154 found_first:
155 	tmp &= (~0UL >> (BITS_PER_LONG - size));
156 	if (tmp == 0UL)		/* Are any bits set? */
157 		return result + size;	/* Nope. */
158 found_middle:
159 	return result + __ffs(tmp);
160 }
161 
162 #endif
163