root / bitops.h @ 05175535
History | View | Annotate | Download (6.3 kB)
1 | e0e53b2f | Corentin Chary | /*
|
---|---|---|---|
2 | e0e53b2f | Corentin Chary | * Bitops Module
|
3 | e0e53b2f | Corentin Chary | *
|
4 | e0e53b2f | Corentin Chary | * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
|
5 | e0e53b2f | Corentin Chary | *
|
6 | e0e53b2f | Corentin Chary | * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
|
7 | e0e53b2f | Corentin Chary | *
|
8 | e0e53b2f | Corentin Chary | * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
|
9 | e0e53b2f | Corentin Chary | * See the COPYING.LIB file in the top-level directory.
|
10 | e0e53b2f | Corentin Chary | */
|
11 | e0e53b2f | Corentin Chary | |
12 | e0e53b2f | Corentin Chary | #ifndef BITOPS_H
|
13 | e0e53b2f | Corentin Chary | #define BITOPS_H
|
14 | e0e53b2f | Corentin Chary | |
15 | e0e53b2f | Corentin Chary | #include "qemu-common.h" |
16 | e0e53b2f | Corentin Chary | |
17 | e0e53b2f | Corentin Chary | #define BITS_PER_BYTE CHAR_BIT
|
18 | e0e53b2f | Corentin Chary | #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) |
19 | e0e53b2f | Corentin Chary | |
20 | e0e53b2f | Corentin Chary | #define BIT(nr) (1UL << (nr)) |
21 | e0e53b2f | Corentin Chary | #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) |
22 | e0e53b2f | Corentin Chary | #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
|
23 | e0e53b2f | Corentin Chary | #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) |
24 | e0e53b2f | Corentin Chary | |
25 | e0e53b2f | Corentin Chary | /**
|
26 | e0e53b2f | Corentin Chary | * bitops_ffs - find first bit in word.
|
27 | e0e53b2f | Corentin Chary | * @word: The word to search
|
28 | e0e53b2f | Corentin Chary | *
|
29 | e0e53b2f | Corentin Chary | * Undefined if no bit exists, so code should check against 0 first.
|
30 | e0e53b2f | Corentin Chary | */
|
31 | e0e53b2f | Corentin Chary | static unsigned long bitops_ffsl(unsigned long word) |
32 | e0e53b2f | Corentin Chary | { |
33 | e0e53b2f | Corentin Chary | int num = 0; |
34 | e0e53b2f | Corentin Chary | |
35 | e0e53b2f | Corentin Chary | #if LONG_MAX > 0x7FFFFFFF |
36 | e0e53b2f | Corentin Chary | if ((word & 0xffffffff) == 0) { |
37 | e0e53b2f | Corentin Chary | num += 32;
|
38 | e0e53b2f | Corentin Chary | word >>= 32;
|
39 | e0e53b2f | Corentin Chary | } |
40 | e0e53b2f | Corentin Chary | #endif
|
41 | e0e53b2f | Corentin Chary | if ((word & 0xffff) == 0) { |
42 | e0e53b2f | Corentin Chary | num += 16;
|
43 | e0e53b2f | Corentin Chary | word >>= 16;
|
44 | e0e53b2f | Corentin Chary | } |
45 | e0e53b2f | Corentin Chary | if ((word & 0xff) == 0) { |
46 | e0e53b2f | Corentin Chary | num += 8;
|
47 | e0e53b2f | Corentin Chary | word >>= 8;
|
48 | e0e53b2f | Corentin Chary | } |
49 | e0e53b2f | Corentin Chary | if ((word & 0xf) == 0) { |
50 | e0e53b2f | Corentin Chary | num += 4;
|
51 | e0e53b2f | Corentin Chary | word >>= 4;
|
52 | e0e53b2f | Corentin Chary | } |
53 | e0e53b2f | Corentin Chary | if ((word & 0x3) == 0) { |
54 | e0e53b2f | Corentin Chary | num += 2;
|
55 | e0e53b2f | Corentin Chary | word >>= 2;
|
56 | e0e53b2f | Corentin Chary | } |
57 | e0e53b2f | Corentin Chary | if ((word & 0x1) == 0) { |
58 | e0e53b2f | Corentin Chary | num += 1;
|
59 | e0e53b2f | Corentin Chary | } |
60 | e0e53b2f | Corentin Chary | return num;
|
61 | e0e53b2f | Corentin Chary | } |
62 | e0e53b2f | Corentin Chary | |
63 | e0e53b2f | Corentin Chary | /**
|
64 | e0e53b2f | Corentin Chary | * bitops_fls - find last (most-significant) set bit in a long word
|
65 | e0e53b2f | Corentin Chary | * @word: the word to search
|
66 | e0e53b2f | Corentin Chary | *
|
67 | e0e53b2f | Corentin Chary | * Undefined if no set bit exists, so code should check against 0 first.
|
68 | e0e53b2f | Corentin Chary | */
|
69 | 84803d7a | Blue Swirl | static inline unsigned long bitops_flsl(unsigned long word) |
70 | e0e53b2f | Corentin Chary | { |
71 | e0e53b2f | Corentin Chary | int num = BITS_PER_LONG - 1; |
72 | e0e53b2f | Corentin Chary | |
73 | e0e53b2f | Corentin Chary | #if LONG_MAX > 0x7FFFFFFF |
74 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << 32))) { |
75 | e0e53b2f | Corentin Chary | num -= 32;
|
76 | e0e53b2f | Corentin Chary | word <<= 32;
|
77 | e0e53b2f | Corentin Chary | } |
78 | e0e53b2f | Corentin Chary | #endif
|
79 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << (BITS_PER_LONG-16)))) { |
80 | e0e53b2f | Corentin Chary | num -= 16;
|
81 | e0e53b2f | Corentin Chary | word <<= 16;
|
82 | e0e53b2f | Corentin Chary | } |
83 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << (BITS_PER_LONG-8)))) { |
84 | e0e53b2f | Corentin Chary | num -= 8;
|
85 | e0e53b2f | Corentin Chary | word <<= 8;
|
86 | e0e53b2f | Corentin Chary | } |
87 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << (BITS_PER_LONG-4)))) { |
88 | e0e53b2f | Corentin Chary | num -= 4;
|
89 | e0e53b2f | Corentin Chary | word <<= 4;
|
90 | e0e53b2f | Corentin Chary | } |
91 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << (BITS_PER_LONG-2)))) { |
92 | e0e53b2f | Corentin Chary | num -= 2;
|
93 | e0e53b2f | Corentin Chary | |
94 | e0e53b2f | Corentin Chary | word <<= 2;
|
95 | e0e53b2f | Corentin Chary | } |
96 | e0e53b2f | Corentin Chary | if (!(word & (~0ul << (BITS_PER_LONG-1)))) |
97 | e0e53b2f | Corentin Chary | num -= 1;
|
98 | e0e53b2f | Corentin Chary | return num;
|
99 | e0e53b2f | Corentin Chary | } |
100 | e0e53b2f | Corentin Chary | |
101 | e0e53b2f | Corentin Chary | /**
|
102 | e0e53b2f | Corentin Chary | * ffz - find first zero in word.
|
103 | e0e53b2f | Corentin Chary | * @word: The word to search
|
104 | e0e53b2f | Corentin Chary | *
|
105 | e0e53b2f | Corentin Chary | * Undefined if no zero exists, so code should check against ~0UL first.
|
106 | e0e53b2f | Corentin Chary | */
|
107 | e0e53b2f | Corentin Chary | static inline unsigned long ffz(unsigned long word) |
108 | e0e53b2f | Corentin Chary | { |
109 | e0e53b2f | Corentin Chary | return bitops_ffsl(~word);
|
110 | e0e53b2f | Corentin Chary | } |
111 | e0e53b2f | Corentin Chary | |
112 | e0e53b2f | Corentin Chary | /**
|
113 | e0e53b2f | Corentin Chary | * set_bit - Set a bit in memory
|
114 | e0e53b2f | Corentin Chary | * @nr: the bit to set
|
115 | e0e53b2f | Corentin Chary | * @addr: the address to start counting from
|
116 | e0e53b2f | Corentin Chary | */
|
117 | e0e53b2f | Corentin Chary | static inline void set_bit(int nr, volatile unsigned long *addr) |
118 | e0e53b2f | Corentin Chary | { |
119 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
120 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
121 | e0e53b2f | Corentin Chary | |
122 | e0e53b2f | Corentin Chary | *p |= mask; |
123 | e0e53b2f | Corentin Chary | } |
124 | e0e53b2f | Corentin Chary | |
125 | e0e53b2f | Corentin Chary | /**
|
126 | e0e53b2f | Corentin Chary | * clear_bit - Clears a bit in memory
|
127 | e0e53b2f | Corentin Chary | * @nr: Bit to clear
|
128 | e0e53b2f | Corentin Chary | * @addr: Address to start counting from
|
129 | e0e53b2f | Corentin Chary | */
|
130 | e0e53b2f | Corentin Chary | static inline void clear_bit(int nr, volatile unsigned long *addr) |
131 | e0e53b2f | Corentin Chary | { |
132 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
133 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
134 | e0e53b2f | Corentin Chary | |
135 | e0e53b2f | Corentin Chary | *p &= ~mask; |
136 | e0e53b2f | Corentin Chary | } |
137 | e0e53b2f | Corentin Chary | |
138 | e0e53b2f | Corentin Chary | /**
|
139 | e0e53b2f | Corentin Chary | * change_bit - Toggle a bit in memory
|
140 | e0e53b2f | Corentin Chary | * @nr: Bit to change
|
141 | e0e53b2f | Corentin Chary | * @addr: Address to start counting from
|
142 | e0e53b2f | Corentin Chary | */
|
143 | e0e53b2f | Corentin Chary | static inline void change_bit(int nr, volatile unsigned long *addr) |
144 | e0e53b2f | Corentin Chary | { |
145 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
146 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
147 | e0e53b2f | Corentin Chary | |
148 | e0e53b2f | Corentin Chary | *p ^= mask; |
149 | e0e53b2f | Corentin Chary | } |
150 | e0e53b2f | Corentin Chary | |
151 | e0e53b2f | Corentin Chary | /**
|
152 | e0e53b2f | Corentin Chary | * test_and_set_bit - Set a bit and return its old value
|
153 | e0e53b2f | Corentin Chary | * @nr: Bit to set
|
154 | e0e53b2f | Corentin Chary | * @addr: Address to count from
|
155 | e0e53b2f | Corentin Chary | */
|
156 | e0e53b2f | Corentin Chary | static inline int test_and_set_bit(int nr, volatile unsigned long *addr) |
157 | e0e53b2f | Corentin Chary | { |
158 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
159 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
160 | e0e53b2f | Corentin Chary | unsigned long old = *p; |
161 | e0e53b2f | Corentin Chary | |
162 | e0e53b2f | Corentin Chary | *p = old | mask; |
163 | e0e53b2f | Corentin Chary | return (old & mask) != 0; |
164 | e0e53b2f | Corentin Chary | } |
165 | e0e53b2f | Corentin Chary | |
166 | e0e53b2f | Corentin Chary | /**
|
167 | e0e53b2f | Corentin Chary | * test_and_clear_bit - Clear a bit and return its old value
|
168 | e0e53b2f | Corentin Chary | * @nr: Bit to clear
|
169 | e0e53b2f | Corentin Chary | * @addr: Address to count from
|
170 | e0e53b2f | Corentin Chary | */
|
171 | e0e53b2f | Corentin Chary | static inline int test_and_clear_bit(int nr, volatile unsigned long *addr) |
172 | e0e53b2f | Corentin Chary | { |
173 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
174 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
175 | e0e53b2f | Corentin Chary | unsigned long old = *p; |
176 | e0e53b2f | Corentin Chary | |
177 | e0e53b2f | Corentin Chary | *p = old & ~mask; |
178 | e0e53b2f | Corentin Chary | return (old & mask) != 0; |
179 | e0e53b2f | Corentin Chary | } |
180 | e0e53b2f | Corentin Chary | |
181 | e0e53b2f | Corentin Chary | /**
|
182 | e0e53b2f | Corentin Chary | * test_and_change_bit - Change a bit and return its old value
|
183 | e0e53b2f | Corentin Chary | * @nr: Bit to change
|
184 | e0e53b2f | Corentin Chary | * @addr: Address to count from
|
185 | e0e53b2f | Corentin Chary | */
|
186 | e0e53b2f | Corentin Chary | static inline int test_and_change_bit(int nr, volatile unsigned long *addr) |
187 | e0e53b2f | Corentin Chary | { |
188 | e0e53b2f | Corentin Chary | unsigned long mask = BIT_MASK(nr); |
189 | e0e53b2f | Corentin Chary | unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
190 | 04483e15 | Corentin Chary | unsigned long old = *p; |
191 | e0e53b2f | Corentin Chary | |
192 | e0e53b2f | Corentin Chary | *p = old ^ mask; |
193 | e0e53b2f | Corentin Chary | return (old & mask) != 0; |
194 | e0e53b2f | Corentin Chary | } |
195 | e0e53b2f | Corentin Chary | |
196 | e0e53b2f | Corentin Chary | /**
|
197 | e0e53b2f | Corentin Chary | * test_bit - Determine whether a bit is set
|
198 | e0e53b2f | Corentin Chary | * @nr: bit number to test
|
199 | e0e53b2f | Corentin Chary | * @addr: Address to start counting from
|
200 | e0e53b2f | Corentin Chary | */
|
201 | e0e53b2f | Corentin Chary | static inline int test_bit(int nr, const volatile unsigned long *addr) |
202 | e0e53b2f | Corentin Chary | { |
203 | e0e53b2f | Corentin Chary | return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); |
204 | e0e53b2f | Corentin Chary | } |
205 | e0e53b2f | Corentin Chary | |
206 | e0e53b2f | Corentin Chary | /**
|
207 | e0e53b2f | Corentin Chary | * find_last_bit - find the last set bit in a memory region
|
208 | e0e53b2f | Corentin Chary | * @addr: The address to start the search at
|
209 | e0e53b2f | Corentin Chary | * @size: The maximum size to search
|
210 | e0e53b2f | Corentin Chary | *
|
211 | e0e53b2f | Corentin Chary | * Returns the bit number of the first set bit, or size.
|
212 | e0e53b2f | Corentin Chary | */
|
213 | e0e53b2f | Corentin Chary | unsigned long find_last_bit(const unsigned long *addr, |
214 | e0e53b2f | Corentin Chary | unsigned long size); |
215 | e0e53b2f | Corentin Chary | |
216 | e0e53b2f | Corentin Chary | /**
|
217 | e0e53b2f | Corentin Chary | * find_next_bit - find the next set bit in a memory region
|
218 | e0e53b2f | Corentin Chary | * @addr: The address to base the search on
|
219 | e0e53b2f | Corentin Chary | * @offset: The bitnumber to start searching at
|
220 | e0e53b2f | Corentin Chary | * @size: The bitmap size in bits
|
221 | e0e53b2f | Corentin Chary | */
|
222 | e0e53b2f | Corentin Chary | unsigned long find_next_bit(const unsigned long *addr, |
223 | e0e53b2f | Corentin Chary | unsigned long size, unsigned long offset); |
224 | e0e53b2f | Corentin Chary | |
225 | e0e53b2f | Corentin Chary | /**
|
226 | e0e53b2f | Corentin Chary | * find_next_zero_bit - find the next cleared bit in a memory region
|
227 | e0e53b2f | Corentin Chary | * @addr: The address to base the search on
|
228 | e0e53b2f | Corentin Chary | * @offset: The bitnumber to start searching at
|
229 | e0e53b2f | Corentin Chary | * @size: The bitmap size in bits
|
230 | e0e53b2f | Corentin Chary | */
|
231 | e0e53b2f | Corentin Chary | |
232 | e0e53b2f | Corentin Chary | unsigned long find_next_zero_bit(const unsigned long *addr, |
233 | e0e53b2f | Corentin Chary | unsigned long size, |
234 | e0e53b2f | Corentin Chary | unsigned long offset); |
235 | e0e53b2f | Corentin Chary | |
236 | e0e53b2f | Corentin Chary | /**
|
237 | e0e53b2f | Corentin Chary | * find_first_bit - find the first set bit in a memory region
|
238 | e0e53b2f | Corentin Chary | * @addr: The address to start the search at
|
239 | e0e53b2f | Corentin Chary | * @size: The maximum size to search
|
240 | e0e53b2f | Corentin Chary | *
|
241 | e0e53b2f | Corentin Chary | * Returns the bit number of the first set bit.
|
242 | e0e53b2f | Corentin Chary | */
|
243 | e0e53b2f | Corentin Chary | static inline unsigned long find_first_bit(const unsigned long *addr, |
244 | e0e53b2f | Corentin Chary | unsigned long size) |
245 | e0e53b2f | Corentin Chary | { |
246 | e0e53b2f | Corentin Chary | return find_next_bit(addr, size, 0); |
247 | e0e53b2f | Corentin Chary | } |
248 | e0e53b2f | Corentin Chary | |
249 | e0e53b2f | Corentin Chary | /**
|
250 | e0e53b2f | Corentin Chary | * find_first_zero_bit - find the first cleared bit in a memory region
|
251 | e0e53b2f | Corentin Chary | * @addr: The address to start the search at
|
252 | e0e53b2f | Corentin Chary | * @size: The maximum size to search
|
253 | e0e53b2f | Corentin Chary | *
|
254 | e0e53b2f | Corentin Chary | * Returns the bit number of the first cleared bit.
|
255 | e0e53b2f | Corentin Chary | */
|
256 | e0e53b2f | Corentin Chary | static inline unsigned long find_first_zero_bit(const unsigned long *addr, |
257 | e0e53b2f | Corentin Chary | unsigned long size) |
258 | e0e53b2f | Corentin Chary | { |
259 | e0e53b2f | Corentin Chary | return find_next_zero_bit(addr, size, 0); |
260 | e0e53b2f | Corentin Chary | } |
261 | e0e53b2f | Corentin Chary | |
262 | e0e53b2f | Corentin Chary | static inline unsigned long hweight_long(unsigned long w) |
263 | e0e53b2f | Corentin Chary | { |
264 | e0e53b2f | Corentin Chary | unsigned long count; |
265 | e0e53b2f | Corentin Chary | |
266 | e0e53b2f | Corentin Chary | for (count = 0; w; w >>= 1) { |
267 | e0e53b2f | Corentin Chary | count += w & 1;
|
268 | e0e53b2f | Corentin Chary | } |
269 | e0e53b2f | Corentin Chary | return count;
|
270 | e0e53b2f | Corentin Chary | } |
271 | e0e53b2f | Corentin Chary | |
272 | e0e53b2f | Corentin Chary | #endif |