]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | #ifndef _ALPHA_BITOPS_H |
2 | #define _ALPHA_BITOPS_H | |
3 | ||
4 | #include <linux/config.h> | |
5 | #include <asm/compiler.h> | |
6 | ||
7 | /* | |
8 | * Copyright 1994, Linus Torvalds. | |
9 | */ | |
10 | ||
11 | /* | |
12 | * These have to be done with inline assembly: that way the bit-setting | |
13 | * is guaranteed to be atomic. All bit operations return 0 if the bit | |
14 | * was cleared before the operation and != 0 if it was not. | |
15 | * | |
16 | * To get proper branch prediction for the main line, we must branch | |
17 | * forward to code at the end of this object's .text section, then | |
18 | * branch back to restart the operation. | |
19 | * | |
20 | * bit 0 is the LSB of addr; bit 64 is the LSB of (addr+1). | |
21 | */ | |
22 | ||
23 | static inline void | |
24 | set_bit(unsigned long nr, volatile void * addr) | |
25 | { | |
26 | unsigned long temp; | |
27 | int *m = ((int *) addr) + (nr >> 5); | |
28 | ||
29 | __asm__ __volatile__( | |
30 | "1: ldl_l %0,%3\n" | |
31 | " bis %0,%2,%0\n" | |
32 | " stl_c %0,%1\n" | |
33 | " beq %0,2f\n" | |
34 | ".subsection 2\n" | |
35 | "2: br 1b\n" | |
36 | ".previous" | |
37 | :"=&r" (temp), "=m" (*m) | |
38 | :"Ir" (1UL << (nr & 31)), "m" (*m)); | |
39 | } | |
40 | ||
41 | /* | |
42 | * WARNING: non atomic version. | |
43 | */ | |
44 | static inline void | |
45 | __set_bit(unsigned long nr, volatile void * addr) | |
46 | { | |
47 | int *m = ((int *) addr) + (nr >> 5); | |
48 | ||
49 | *m |= 1 << (nr & 31); | |
50 | } | |
51 | ||
52 | #define smp_mb__before_clear_bit() smp_mb() | |
53 | #define smp_mb__after_clear_bit() smp_mb() | |
54 | ||
55 | static inline void | |
56 | clear_bit(unsigned long nr, volatile void * addr) | |
57 | { | |
58 | unsigned long temp; | |
59 | int *m = ((int *) addr) + (nr >> 5); | |
60 | ||
61 | __asm__ __volatile__( | |
62 | "1: ldl_l %0,%3\n" | |
63 | " bic %0,%2,%0\n" | |
64 | " stl_c %0,%1\n" | |
65 | " beq %0,2f\n" | |
66 | ".subsection 2\n" | |
67 | "2: br 1b\n" | |
68 | ".previous" | |
69 | :"=&r" (temp), "=m" (*m) | |
70 | :"Ir" (1UL << (nr & 31)), "m" (*m)); | |
71 | } | |
72 | ||
73 | /* | |
74 | * WARNING: non atomic version. | |
75 | */ | |
76 | static __inline__ void | |
77 | __clear_bit(unsigned long nr, volatile void * addr) | |
78 | { | |
79 | int *m = ((int *) addr) + (nr >> 5); | |
80 | ||
81 | *m &= ~(1 << (nr & 31)); | |
82 | } | |
83 | ||
84 | static inline void | |
85 | change_bit(unsigned long nr, volatile void * addr) | |
86 | { | |
87 | unsigned long temp; | |
88 | int *m = ((int *) addr) + (nr >> 5); | |
89 | ||
90 | __asm__ __volatile__( | |
91 | "1: ldl_l %0,%3\n" | |
92 | " xor %0,%2,%0\n" | |
93 | " stl_c %0,%1\n" | |
94 | " beq %0,2f\n" | |
95 | ".subsection 2\n" | |
96 | "2: br 1b\n" | |
97 | ".previous" | |
98 | :"=&r" (temp), "=m" (*m) | |
99 | :"Ir" (1UL << (nr & 31)), "m" (*m)); | |
100 | } | |
101 | ||
102 | /* | |
103 | * WARNING: non atomic version. | |
104 | */ | |
105 | static __inline__ void | |
106 | __change_bit(unsigned long nr, volatile void * addr) | |
107 | { | |
108 | int *m = ((int *) addr) + (nr >> 5); | |
109 | ||
110 | *m ^= 1 << (nr & 31); | |
111 | } | |
112 | ||
113 | static inline int | |
114 | test_and_set_bit(unsigned long nr, volatile void *addr) | |
115 | { | |
116 | unsigned long oldbit; | |
117 | unsigned long temp; | |
118 | int *m = ((int *) addr) + (nr >> 5); | |
119 | ||
120 | __asm__ __volatile__( | |
121 | "1: ldl_l %0,%4\n" | |
122 | " and %0,%3,%2\n" | |
123 | " bne %2,2f\n" | |
124 | " xor %0,%3,%0\n" | |
125 | " stl_c %0,%1\n" | |
126 | " beq %0,3f\n" | |
127 | "2:\n" | |
128 | #ifdef CONFIG_SMP | |
129 | " mb\n" | |
130 | #endif | |
131 | ".subsection 2\n" | |
132 | "3: br 1b\n" | |
133 | ".previous" | |
134 | :"=&r" (temp), "=m" (*m), "=&r" (oldbit) | |
135 | :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory"); | |
136 | ||
137 | return oldbit != 0; | |
138 | } | |
139 | ||
140 | /* | |
141 | * WARNING: non atomic version. | |
142 | */ | |
143 | static inline int | |
144 | __test_and_set_bit(unsigned long nr, volatile void * addr) | |
145 | { | |
146 | unsigned long mask = 1 << (nr & 0x1f); | |
147 | int *m = ((int *) addr) + (nr >> 5); | |
148 | int old = *m; | |
149 | ||
150 | *m = old | mask; | |
151 | return (old & mask) != 0; | |
152 | } | |
153 | ||
154 | static inline int | |
155 | test_and_clear_bit(unsigned long nr, volatile void * addr) | |
156 | { | |
157 | unsigned long oldbit; | |
158 | unsigned long temp; | |
159 | int *m = ((int *) addr) + (nr >> 5); | |
160 | ||
161 | __asm__ __volatile__( | |
162 | "1: ldl_l %0,%4\n" | |
163 | " and %0,%3,%2\n" | |
164 | " beq %2,2f\n" | |
165 | " xor %0,%3,%0\n" | |
166 | " stl_c %0,%1\n" | |
167 | " beq %0,3f\n" | |
168 | "2:\n" | |
169 | #ifdef CONFIG_SMP | |
170 | " mb\n" | |
171 | #endif | |
172 | ".subsection 2\n" | |
173 | "3: br 1b\n" | |
174 | ".previous" | |
175 | :"=&r" (temp), "=m" (*m), "=&r" (oldbit) | |
176 | :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory"); | |
177 | ||
178 | return oldbit != 0; | |
179 | } | |
180 | ||
181 | /* | |
182 | * WARNING: non atomic version. | |
183 | */ | |
184 | static inline int | |
185 | __test_and_clear_bit(unsigned long nr, volatile void * addr) | |
186 | { | |
187 | unsigned long mask = 1 << (nr & 0x1f); | |
188 | int *m = ((int *) addr) + (nr >> 5); | |
189 | int old = *m; | |
190 | ||
191 | *m = old & ~mask; | |
192 | return (old & mask) != 0; | |
193 | } | |
194 | ||
195 | static inline int | |
196 | test_and_change_bit(unsigned long nr, volatile void * addr) | |
197 | { | |
198 | unsigned long oldbit; | |
199 | unsigned long temp; | |
200 | int *m = ((int *) addr) + (nr >> 5); | |
201 | ||
202 | __asm__ __volatile__( | |
203 | "1: ldl_l %0,%4\n" | |
204 | " and %0,%3,%2\n" | |
205 | " xor %0,%3,%0\n" | |
206 | " stl_c %0,%1\n" | |
207 | " beq %0,3f\n" | |
208 | #ifdef CONFIG_SMP | |
209 | " mb\n" | |
210 | #endif | |
211 | ".subsection 2\n" | |
212 | "3: br 1b\n" | |
213 | ".previous" | |
214 | :"=&r" (temp), "=m" (*m), "=&r" (oldbit) | |
215 | :"Ir" (1UL << (nr & 31)), "m" (*m) : "memory"); | |
216 | ||
217 | return oldbit != 0; | |
218 | } | |
219 | ||
220 | /* | |
221 | * WARNING: non atomic version. | |
222 | */ | |
223 | static __inline__ int | |
224 | __test_and_change_bit(unsigned long nr, volatile void * addr) | |
225 | { | |
226 | unsigned long mask = 1 << (nr & 0x1f); | |
227 | int *m = ((int *) addr) + (nr >> 5); | |
228 | int old = *m; | |
229 | ||
230 | *m = old ^ mask; | |
231 | return (old & mask) != 0; | |
232 | } | |
233 | ||
234 | static inline int | |
235 | test_bit(int nr, const volatile void * addr) | |
236 | { | |
237 | return (1UL & (((const int *) addr)[nr >> 5] >> (nr & 31))) != 0UL; | |
238 | } | |
239 | ||
240 | /* | |
241 | * ffz = Find First Zero in word. Undefined if no zero exists, | |
242 | * so code should check against ~0UL first.. | |
243 | * | |
244 | * Do a binary search on the bits. Due to the nature of large | |
245 | * constants on the alpha, it is worthwhile to split the search. | |
246 | */ | |
247 | static inline unsigned long ffz_b(unsigned long x) | |
248 | { | |
249 | unsigned long sum, x1, x2, x4; | |
250 | ||
251 | x = ~x & -~x; /* set first 0 bit, clear others */ | |
252 | x1 = x & 0xAA; | |
253 | x2 = x & 0xCC; | |
254 | x4 = x & 0xF0; | |
255 | sum = x2 ? 2 : 0; | |
256 | sum += (x4 != 0) * 4; | |
257 | sum += (x1 != 0); | |
258 | ||
259 | return sum; | |
260 | } | |
261 | ||
262 | static inline unsigned long ffz(unsigned long word) | |
263 | { | |
264 | #if defined(__alpha_cix__) && defined(__alpha_fix__) | |
265 | /* Whee. EV67 can calculate it directly. */ | |
266 | return __kernel_cttz(~word); | |
267 | #else | |
268 | unsigned long bits, qofs, bofs; | |
269 | ||
270 | bits = __kernel_cmpbge(word, ~0UL); | |
271 | qofs = ffz_b(bits); | |
272 | bits = __kernel_extbl(word, qofs); | |
273 | bofs = ffz_b(bits); | |
274 | ||
275 | return qofs*8 + bofs; | |
276 | #endif | |
277 | } | |
278 | ||
279 | /* | |
280 | * __ffs = Find First set bit in word. Undefined if no set bit exists. | |
281 | */ | |
282 | static inline unsigned long __ffs(unsigned long word) | |
283 | { | |
284 | #if defined(__alpha_cix__) && defined(__alpha_fix__) | |
285 | /* Whee. EV67 can calculate it directly. */ | |
286 | return __kernel_cttz(word); | |
287 | #else | |
288 | unsigned long bits, qofs, bofs; | |
289 | ||
290 | bits = __kernel_cmpbge(0, word); | |
291 | qofs = ffz_b(bits); | |
292 | bits = __kernel_extbl(word, qofs); | |
293 | bofs = ffz_b(~bits); | |
294 | ||
295 | return qofs*8 + bofs; | |
296 | #endif | |
297 | } | |
298 | ||
299 | #ifdef __KERNEL__ | |
300 | ||
301 | /* | |
302 | * ffs: find first bit set. This is defined the same way as | |
303 | * the libc and compiler builtin ffs routines, therefore | |
304 | * differs in spirit from the above __ffs. | |
305 | */ | |
306 | ||
307 | static inline int ffs(int word) | |
308 | { | |
309 | int result = __ffs(word) + 1; | |
310 | return word ? result : 0; | |
311 | } | |
312 | ||
313 | /* | |
314 | * fls: find last bit set. | |
315 | */ | |
316 | #if defined(__alpha_cix__) && defined(__alpha_fix__) | |
317 | static inline int fls(int word) | |
318 | { | |
319 | return 64 - __kernel_ctlz(word & 0xffffffff); | |
320 | } | |
321 | #else | |
322 | #define fls generic_fls | |
323 | #endif | |
3821af2f | 324 | #define fls64 generic_fls64 |
1da177e4 LT |
325 | |
326 | /* Compute powers of two for the given integer. */ | |
327 | static inline long floor_log2(unsigned long word) | |
328 | { | |
329 | #if defined(__alpha_cix__) && defined(__alpha_fix__) | |
330 | return 63 - __kernel_ctlz(word); | |
331 | #else | |
332 | long bit; | |
333 | for (bit = -1; word ; bit++) | |
334 | word >>= 1; | |
335 | return bit; | |
336 | #endif | |
337 | } | |
338 | ||
339 | static inline long ceil_log2(unsigned long word) | |
340 | { | |
341 | long bit = floor_log2(word); | |
342 | return bit + (word > (1UL << bit)); | |
343 | } | |
344 | ||
345 | /* | |
346 | * hweightN: returns the hamming weight (i.e. the number | |
347 | * of bits set) of a N-bit word | |
348 | */ | |
349 | ||
350 | #if defined(__alpha_cix__) && defined(__alpha_fix__) | |
351 | /* Whee. EV67 can calculate it directly. */ | |
352 | static inline unsigned long hweight64(unsigned long w) | |
353 | { | |
354 | return __kernel_ctpop(w); | |
355 | } | |
356 | ||
357 | #define hweight32(x) (unsigned int) hweight64((x) & 0xfffffffful) | |
358 | #define hweight16(x) (unsigned int) hweight64((x) & 0xfffful) | |
359 | #define hweight8(x) (unsigned int) hweight64((x) & 0xfful) | |
360 | #else | |
361 | static inline unsigned long hweight64(unsigned long w) | |
362 | { | |
363 | unsigned long result; | |
364 | for (result = 0; w ; w >>= 1) | |
365 | result += (w & 1); | |
366 | return result; | |
367 | } | |
368 | ||
369 | #define hweight32(x) generic_hweight32(x) | |
370 | #define hweight16(x) generic_hweight16(x) | |
371 | #define hweight8(x) generic_hweight8(x) | |
372 | #endif | |
373 | ||
374 | #endif /* __KERNEL__ */ | |
375 | ||
376 | /* | |
377 | * Find next zero bit in a bitmap reasonably efficiently.. | |
378 | */ | |
379 | static inline unsigned long | |
380 | find_next_zero_bit(const void *addr, unsigned long size, unsigned long offset) | |
381 | { | |
382 | const unsigned long *p = addr; | |
383 | unsigned long result = offset & ~63UL; | |
384 | unsigned long tmp; | |
385 | ||
386 | p += offset >> 6; | |
387 | if (offset >= size) | |
388 | return size; | |
389 | size -= result; | |
390 | offset &= 63UL; | |
391 | if (offset) { | |
392 | tmp = *(p++); | |
393 | tmp |= ~0UL >> (64-offset); | |
394 | if (size < 64) | |
395 | goto found_first; | |
396 | if (~tmp) | |
397 | goto found_middle; | |
398 | size -= 64; | |
399 | result += 64; | |
400 | } | |
401 | while (size & ~63UL) { | |
402 | if (~(tmp = *(p++))) | |
403 | goto found_middle; | |
404 | result += 64; | |
405 | size -= 64; | |
406 | } | |
407 | if (!size) | |
408 | return result; | |
409 | tmp = *p; | |
410 | found_first: | |
411 | tmp |= ~0UL << size; | |
412 | if (tmp == ~0UL) /* Are any bits zero? */ | |
413 | return result + size; /* Nope. */ | |
414 | found_middle: | |
415 | return result + ffz(tmp); | |
416 | } | |
417 | ||
418 | /* | |
419 | * Find next one bit in a bitmap reasonably efficiently. | |
420 | */ | |
421 | static inline unsigned long | |
422 | find_next_bit(const void * addr, unsigned long size, unsigned long offset) | |
423 | { | |
424 | const unsigned long *p = addr; | |
425 | unsigned long result = offset & ~63UL; | |
426 | unsigned long tmp; | |
427 | ||
428 | p += offset >> 6; | |
429 | if (offset >= size) | |
430 | return size; | |
431 | size -= result; | |
432 | offset &= 63UL; | |
433 | if (offset) { | |
434 | tmp = *(p++); | |
435 | tmp &= ~0UL << offset; | |
436 | if (size < 64) | |
437 | goto found_first; | |
438 | if (tmp) | |
439 | goto found_middle; | |
440 | size -= 64; | |
441 | result += 64; | |
442 | } | |
443 | while (size & ~63UL) { | |
444 | if ((tmp = *(p++))) | |
445 | goto found_middle; | |
446 | result += 64; | |
447 | size -= 64; | |
448 | } | |
449 | if (!size) | |
450 | return result; | |
451 | tmp = *p; | |
452 | found_first: | |
453 | tmp &= ~0UL >> (64 - size); | |
454 | if (!tmp) | |
455 | return result + size; | |
456 | found_middle: | |
457 | return result + __ffs(tmp); | |
458 | } | |
459 | ||
460 | /* | |
461 | * The optimizer actually does good code for this case. | |
462 | */ | |
463 | #define find_first_zero_bit(addr, size) \ | |
464 | find_next_zero_bit((addr), (size), 0) | |
465 | #define find_first_bit(addr, size) \ | |
466 | find_next_bit((addr), (size), 0) | |
467 | ||
468 | #ifdef __KERNEL__ | |
469 | ||
470 | /* | |
471 | * Every architecture must define this function. It's the fastest | |
472 | * way of searching a 140-bit bitmap where the first 100 bits are | |
473 | * unlikely to be set. It's guaranteed that at least one of the 140 | |
474 | * bits is set. | |
475 | */ | |
476 | static inline unsigned long | |
477 | sched_find_first_bit(unsigned long b[3]) | |
478 | { | |
479 | unsigned long b0 = b[0], b1 = b[1], b2 = b[2]; | |
480 | unsigned long ofs; | |
481 | ||
482 | ofs = (b1 ? 64 : 128); | |
483 | b1 = (b1 ? b1 : b2); | |
484 | ofs = (b0 ? 0 : ofs); | |
485 | b0 = (b0 ? b0 : b1); | |
486 | ||
487 | return __ffs(b0) + ofs; | |
488 | } | |
489 | ||
490 | ||
491 | #define ext2_set_bit __test_and_set_bit | |
492 | #define ext2_set_bit_atomic(l,n,a) test_and_set_bit(n,a) | |
493 | #define ext2_clear_bit __test_and_clear_bit | |
494 | #define ext2_clear_bit_atomic(l,n,a) test_and_clear_bit(n,a) | |
495 | #define ext2_test_bit test_bit | |
496 | #define ext2_find_first_zero_bit find_first_zero_bit | |
497 | #define ext2_find_next_zero_bit find_next_zero_bit | |
498 | ||
499 | /* Bitmap functions for the minix filesystem. */ | |
500 | #define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,addr) | |
501 | #define minix_set_bit(nr,addr) __set_bit(nr,addr) | |
502 | #define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,addr) | |
503 | #define minix_test_bit(nr,addr) test_bit(nr,addr) | |
504 | #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size) | |
505 | ||
506 | #endif /* __KERNEL__ */ | |
507 | ||
508 | #endif /* _ALPHA_BITOPS_H */ |