]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | #ifndef _PARISC_BITOPS_H |
2 | #define _PARISC_BITOPS_H | |
3 | ||
4 | #include <linux/compiler.h> | |
5 | #include <asm/system.h> | |
6 | #include <asm/byteorder.h> | |
7 | #include <asm/atomic.h> | |
8 | ||
9 | /* | |
10 | * HP-PARISC specific bit operations | |
11 | * for a detailed description of the functions please refer | |
12 | * to include/asm-i386/bitops.h or kerneldoc | |
13 | */ | |
14 | ||
15 | #ifdef __LP64__ | |
16 | # define SHIFT_PER_LONG 6 | |
17 | #ifndef BITS_PER_LONG | |
18 | # define BITS_PER_LONG 64 | |
19 | #endif | |
20 | #else | |
21 | # define SHIFT_PER_LONG 5 | |
22 | #ifndef BITS_PER_LONG | |
23 | # define BITS_PER_LONG 32 | |
24 | #endif | |
25 | #endif | |
26 | ||
27 | #define CHOP_SHIFTCOUNT(x) ((x) & (BITS_PER_LONG - 1)) | |
28 | ||
29 | ||
30 | #define smp_mb__before_clear_bit() smp_mb() | |
31 | #define smp_mb__after_clear_bit() smp_mb() | |
32 | ||
33 | static __inline__ void set_bit(int nr, volatile unsigned long * address) | |
34 | { | |
35 | unsigned long mask; | |
36 | unsigned long *addr = (unsigned long *) address; | |
37 | unsigned long flags; | |
38 | ||
39 | addr += (nr >> SHIFT_PER_LONG); | |
40 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
41 | _atomic_spin_lock_irqsave(addr, flags); | |
42 | *addr |= mask; | |
43 | _atomic_spin_unlock_irqrestore(addr, flags); | |
44 | } | |
45 | ||
46 | static __inline__ void __set_bit(int nr, volatile unsigned long * address) | |
47 | { | |
48 | unsigned long mask; | |
49 | unsigned long *addr = (unsigned long *) address; | |
50 | ||
51 | addr += (nr >> SHIFT_PER_LONG); | |
52 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
53 | *addr |= mask; | |
54 | } | |
55 | ||
56 | static __inline__ void clear_bit(int nr, volatile unsigned long * address) | |
57 | { | |
58 | unsigned long mask; | |
59 | unsigned long *addr = (unsigned long *) address; | |
60 | unsigned long flags; | |
61 | ||
62 | addr += (nr >> SHIFT_PER_LONG); | |
63 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
64 | _atomic_spin_lock_irqsave(addr, flags); | |
65 | *addr &= ~mask; | |
66 | _atomic_spin_unlock_irqrestore(addr, flags); | |
67 | } | |
68 | ||
69 | static __inline__ void __clear_bit(unsigned long nr, volatile unsigned long * address) | |
70 | { | |
71 | unsigned long mask; | |
72 | unsigned long *addr = (unsigned long *) address; | |
73 | ||
74 | addr += (nr >> SHIFT_PER_LONG); | |
75 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
76 | *addr &= ~mask; | |
77 | } | |
78 | ||
79 | static __inline__ void change_bit(int nr, volatile unsigned long * address) | |
80 | { | |
81 | unsigned long mask; | |
82 | unsigned long *addr = (unsigned long *) address; | |
83 | unsigned long flags; | |
84 | ||
85 | addr += (nr >> SHIFT_PER_LONG); | |
86 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
87 | _atomic_spin_lock_irqsave(addr, flags); | |
88 | *addr ^= mask; | |
89 | _atomic_spin_unlock_irqrestore(addr, flags); | |
90 | } | |
91 | ||
92 | static __inline__ void __change_bit(int nr, volatile unsigned long * address) | |
93 | { | |
94 | unsigned long mask; | |
95 | unsigned long *addr = (unsigned long *) address; | |
96 | ||
97 | addr += (nr >> SHIFT_PER_LONG); | |
98 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
99 | *addr ^= mask; | |
100 | } | |
101 | ||
102 | static __inline__ int test_and_set_bit(int nr, volatile unsigned long * address) | |
103 | { | |
104 | unsigned long mask; | |
105 | unsigned long *addr = (unsigned long *) address; | |
106 | int oldbit; | |
107 | unsigned long flags; | |
108 | ||
109 | addr += (nr >> SHIFT_PER_LONG); | |
110 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
111 | _atomic_spin_lock_irqsave(addr, flags); | |
112 | oldbit = (*addr & mask) ? 1 : 0; | |
113 | *addr |= mask; | |
114 | _atomic_spin_unlock_irqrestore(addr, flags); | |
115 | ||
116 | return oldbit; | |
117 | } | |
118 | ||
119 | static __inline__ int __test_and_set_bit(int nr, volatile unsigned long * address) | |
120 | { | |
121 | unsigned long mask; | |
122 | unsigned long *addr = (unsigned long *) address; | |
123 | int oldbit; | |
124 | ||
125 | addr += (nr >> SHIFT_PER_LONG); | |
126 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
127 | oldbit = (*addr & mask) ? 1 : 0; | |
128 | *addr |= mask; | |
129 | ||
130 | return oldbit; | |
131 | } | |
132 | ||
133 | static __inline__ int test_and_clear_bit(int nr, volatile unsigned long * address) | |
134 | { | |
135 | unsigned long mask; | |
136 | unsigned long *addr = (unsigned long *) address; | |
137 | int oldbit; | |
138 | unsigned long flags; | |
139 | ||
140 | addr += (nr >> SHIFT_PER_LONG); | |
141 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
142 | _atomic_spin_lock_irqsave(addr, flags); | |
143 | oldbit = (*addr & mask) ? 1 : 0; | |
144 | *addr &= ~mask; | |
145 | _atomic_spin_unlock_irqrestore(addr, flags); | |
146 | ||
147 | return oldbit; | |
148 | } | |
149 | ||
150 | static __inline__ int __test_and_clear_bit(int nr, volatile unsigned long * address) | |
151 | { | |
152 | unsigned long mask; | |
153 | unsigned long *addr = (unsigned long *) address; | |
154 | int oldbit; | |
155 | ||
156 | addr += (nr >> SHIFT_PER_LONG); | |
157 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
158 | oldbit = (*addr & mask) ? 1 : 0; | |
159 | *addr &= ~mask; | |
160 | ||
161 | return oldbit; | |
162 | } | |
163 | ||
164 | static __inline__ int test_and_change_bit(int nr, volatile unsigned long * address) | |
165 | { | |
166 | unsigned long mask; | |
167 | unsigned long *addr = (unsigned long *) address; | |
168 | int oldbit; | |
169 | unsigned long flags; | |
170 | ||
171 | addr += (nr >> SHIFT_PER_LONG); | |
172 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
173 | _atomic_spin_lock_irqsave(addr, flags); | |
174 | oldbit = (*addr & mask) ? 1 : 0; | |
175 | *addr ^= mask; | |
176 | _atomic_spin_unlock_irqrestore(addr, flags); | |
177 | ||
178 | return oldbit; | |
179 | } | |
180 | ||
181 | static __inline__ int __test_and_change_bit(int nr, volatile unsigned long * address) | |
182 | { | |
183 | unsigned long mask; | |
184 | unsigned long *addr = (unsigned long *) address; | |
185 | int oldbit; | |
186 | ||
187 | addr += (nr >> SHIFT_PER_LONG); | |
188 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
189 | oldbit = (*addr & mask) ? 1 : 0; | |
190 | *addr ^= mask; | |
191 | ||
192 | return oldbit; | |
193 | } | |
194 | ||
195 | static __inline__ int test_bit(int nr, const volatile unsigned long *address) | |
196 | { | |
197 | unsigned long mask; | |
198 | const unsigned long *addr = (const unsigned long *)address; | |
199 | ||
200 | addr += (nr >> SHIFT_PER_LONG); | |
201 | mask = 1L << CHOP_SHIFTCOUNT(nr); | |
202 | ||
203 | return !!(*addr & mask); | |
204 | } | |
205 | ||
206 | #ifdef __KERNEL__ | |
207 | ||
208 | /** | |
209 | * __ffs - find first bit in word. returns 0 to "BITS_PER_LONG-1". | |
210 | * @word: The word to search | |
211 | * | |
212 | * __ffs() return is undefined if no bit is set. | |
213 | * | |
214 | * 32-bit fast __ffs by LaMont Jones "lamont At hp com". | |
215 | * 64-bit enhancement by Grant Grundler "grundler At parisc-linux org". | |
216 | * (with help from willy/jejb to get the semantics right) | |
217 | * | |
218 | * This algorithm avoids branches by making use of nullification. | |
219 | * One side effect of "extr" instructions is it sets PSW[N] bit. | |
220 | * How PSW[N] (nullify next insn) gets set is determined by the | |
221 | * "condition" field (eg "<>" or "TR" below) in the extr* insn. | |
222 | * Only the 1st and one of either the 2cd or 3rd insn will get executed. | |
223 | * Each set of 3 insn will get executed in 2 cycles on PA8x00 vs 16 or so | |
224 | * cycles for each mispredicted branch. | |
225 | */ | |
226 | ||
227 | static __inline__ unsigned long __ffs(unsigned long x) | |
228 | { | |
229 | unsigned long ret; | |
230 | ||
231 | __asm__( | |
232 | #if BITS_PER_LONG > 32 | |
233 | " ldi 63,%1\n" | |
234 | " extrd,u,*<> %0,63,32,%%r0\n" | |
235 | " extrd,u,*TR %0,31,32,%0\n" /* move top 32-bits down */ | |
236 | " addi -32,%1,%1\n" | |
237 | #else | |
238 | " ldi 31,%1\n" | |
239 | #endif | |
240 | " extru,<> %0,31,16,%%r0\n" | |
241 | " extru,TR %0,15,16,%0\n" /* xxxx0000 -> 0000xxxx */ | |
242 | " addi -16,%1,%1\n" | |
243 | " extru,<> %0,31,8,%%r0\n" | |
244 | " extru,TR %0,23,8,%0\n" /* 0000xx00 -> 000000xx */ | |
245 | " addi -8,%1,%1\n" | |
246 | " extru,<> %0,31,4,%%r0\n" | |
247 | " extru,TR %0,27,4,%0\n" /* 000000x0 -> 0000000x */ | |
248 | " addi -4,%1,%1\n" | |
249 | " extru,<> %0,31,2,%%r0\n" | |
250 | " extru,TR %0,29,2,%0\n" /* 0000000y, 1100b -> 0011b */ | |
251 | " addi -2,%1,%1\n" | |
252 | " extru,= %0,31,1,%%r0\n" /* check last bit */ | |
253 | " addi -1,%1,%1\n" | |
254 | : "+r" (x), "=r" (ret) ); | |
255 | return ret; | |
256 | } | |
257 | ||
258 | /* Undefined if no bit is zero. */ | |
259 | #define ffz(x) __ffs(~x) | |
260 | ||
261 | /* | |
262 | * ffs: find first bit set. returns 1 to BITS_PER_LONG or 0 (if none set) | |
263 | * This is defined the same way as the libc and compiler builtin | |
264 | * ffs routines, therefore differs in spirit from the above ffz (man ffs). | |
265 | */ | |
266 | static __inline__ int ffs(int x) | |
267 | { | |
268 | return x ? (__ffs((unsigned long)x) + 1) : 0; | |
269 | } | |
270 | ||
271 | /* | |
272 | * fls: find last (most significant) bit set. | |
273 | * fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. | |
274 | */ | |
275 | ||
276 | static __inline__ int fls(int x) | |
277 | { | |
278 | int ret; | |
279 | if (!x) | |
280 | return 0; | |
281 | ||
282 | __asm__( | |
283 | " ldi 1,%1\n" | |
284 | " extru,<> %0,15,16,%%r0\n" | |
285 | " zdep,TR %0,15,16,%0\n" /* xxxx0000 */ | |
286 | " addi 16,%1,%1\n" | |
287 | " extru,<> %0,7,8,%%r0\n" | |
288 | " zdep,TR %0,23,24,%0\n" /* xx000000 */ | |
289 | " addi 8,%1,%1\n" | |
290 | " extru,<> %0,3,4,%%r0\n" | |
291 | " zdep,TR %0,27,28,%0\n" /* x0000000 */ | |
292 | " addi 4,%1,%1\n" | |
293 | " extru,<> %0,1,2,%%r0\n" | |
294 | " zdep,TR %0,29,30,%0\n" /* y0000000 (y&3 = 0) */ | |
295 | " addi 2,%1,%1\n" | |
296 | " extru,= %0,0,1,%%r0\n" | |
297 | " addi 1,%1,%1\n" /* if y & 8, add 1 */ | |
298 | : "+r" (x), "=r" (ret) ); | |
299 | ||
300 | return ret; | |
301 | } | |
302 | ||
303 | /* | |
304 | * hweightN: returns the hamming weight (i.e. the number | |
305 | * of bits set) of a N-bit word | |
306 | */ | |
307 | #define hweight64(x) \ | |
308 | ({ \ | |
309 | unsigned long __x = (x); \ | |
310 | unsigned int __w; \ | |
311 | __w = generic_hweight32((unsigned int) __x); \ | |
312 | __w += generic_hweight32((unsigned int) (__x>>32)); \ | |
313 | __w; \ | |
314 | }) | |
315 | #define hweight32(x) generic_hweight32(x) | |
316 | #define hweight16(x) generic_hweight16(x) | |
317 | #define hweight8(x) generic_hweight8(x) | |
318 | ||
319 | /* | |
320 | * Every architecture must define this function. It's the fastest | |
321 | * way of searching a 140-bit bitmap where the first 100 bits are | |
322 | * unlikely to be set. It's guaranteed that at least one of the 140 | |
323 | * bits is cleared. | |
324 | */ | |
325 | static inline int sched_find_first_bit(const unsigned long *b) | |
326 | { | |
327 | #ifndef __LP64__ | |
328 | if (unlikely(b[0])) | |
329 | return __ffs(b[0]); | |
330 | if (unlikely(b[1])) | |
331 | return __ffs(b[1]) + 32; | |
332 | if (unlikely(b[2])) | |
333 | return __ffs(b[2]) + 64; | |
334 | if (b[3]) | |
335 | return __ffs(b[3]) + 96; | |
336 | return __ffs(b[4]) + 128; | |
337 | #else | |
338 | if (unlikely(b[0])) | |
339 | return __ffs(b[0]); | |
340 | if (unlikely(((unsigned int)b[1]))) | |
341 | return __ffs(b[1]) + 64; | |
342 | if (b[1] >> 32) | |
343 | return __ffs(b[1] >> 32) + 96; | |
344 | return __ffs(b[2]) + 128; | |
345 | #endif | |
346 | } | |
347 | ||
348 | #endif /* __KERNEL__ */ | |
349 | ||
350 | /* | |
351 | * This implementation of find_{first,next}_zero_bit was stolen from | |
352 | * Linus' asm-alpha/bitops.h. | |
353 | */ | |
354 | #define find_first_zero_bit(addr, size) \ | |
355 | find_next_zero_bit((addr), (size), 0) | |
356 | ||
357 | static __inline__ unsigned long find_next_zero_bit(const void * addr, unsigned long size, unsigned long offset) | |
358 | { | |
359 | const unsigned long * p = ((unsigned long *) addr) + (offset >> SHIFT_PER_LONG); | |
360 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
361 | unsigned long tmp; | |
362 | ||
363 | if (offset >= size) | |
364 | return size; | |
365 | size -= result; | |
366 | offset &= (BITS_PER_LONG-1); | |
367 | if (offset) { | |
368 | tmp = *(p++); | |
369 | tmp |= ~0UL >> (BITS_PER_LONG-offset); | |
370 | if (size < BITS_PER_LONG) | |
371 | goto found_first; | |
372 | if (~tmp) | |
373 | goto found_middle; | |
374 | size -= BITS_PER_LONG; | |
375 | result += BITS_PER_LONG; | |
376 | } | |
377 | while (size & ~(BITS_PER_LONG -1)) { | |
378 | if (~(tmp = *(p++))) | |
379 | goto found_middle; | |
380 | result += BITS_PER_LONG; | |
381 | size -= BITS_PER_LONG; | |
382 | } | |
383 | if (!size) | |
384 | return result; | |
385 | tmp = *p; | |
386 | found_first: | |
387 | tmp |= ~0UL << size; | |
388 | found_middle: | |
389 | return result + ffz(tmp); | |
390 | } | |
391 | ||
392 | static __inline__ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) | |
393 | { | |
394 | const unsigned long *p = addr + (offset >> 6); | |
395 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
396 | unsigned long tmp; | |
397 | ||
398 | if (offset >= size) | |
399 | return size; | |
400 | size -= result; | |
401 | offset &= (BITS_PER_LONG-1); | |
402 | if (offset) { | |
403 | tmp = *(p++); | |
404 | tmp &= (~0UL << offset); | |
405 | if (size < BITS_PER_LONG) | |
406 | goto found_first; | |
407 | if (tmp) | |
408 | goto found_middle; | |
409 | size -= BITS_PER_LONG; | |
410 | result += BITS_PER_LONG; | |
411 | } | |
412 | while (size & ~(BITS_PER_LONG-1)) { | |
413 | if ((tmp = *(p++))) | |
414 | goto found_middle; | |
415 | result += BITS_PER_LONG; | |
416 | size -= BITS_PER_LONG; | |
417 | } | |
418 | if (!size) | |
419 | return result; | |
420 | tmp = *p; | |
421 | ||
422 | found_first: | |
423 | tmp &= (~0UL >> (BITS_PER_LONG - size)); | |
424 | if (tmp == 0UL) /* Are any bits set? */ | |
425 | return result + size; /* Nope. */ | |
426 | found_middle: | |
427 | return result + __ffs(tmp); | |
428 | } | |
429 | ||
430 | /** | |
431 | * find_first_bit - find the first set bit in a memory region | |
432 | * @addr: The address to start the search at | |
433 | * @size: The maximum size to search | |
434 | * | |
435 | * Returns the bit-number of the first set bit, not the number of the byte | |
436 | * containing a bit. | |
437 | */ | |
438 | #define find_first_bit(addr, size) \ | |
439 | find_next_bit((addr), (size), 0) | |
440 | ||
441 | #define _EXT2_HAVE_ASM_BITOPS_ | |
442 | ||
443 | #ifdef __KERNEL__ | |
444 | /* | |
445 | * test_and_{set,clear}_bit guarantee atomicity without | |
446 | * disabling interrupts. | |
447 | */ | |
448 | #ifdef __LP64__ | |
449 | #define ext2_set_bit(nr, addr) __test_and_set_bit((nr) ^ 0x38, (unsigned long *)addr) | |
450 | #define ext2_set_bit_atomic(l,nr,addr) test_and_set_bit((nr) ^ 0x38, (unsigned long *)addr) | |
451 | #define ext2_clear_bit(nr, addr) __test_and_clear_bit((nr) ^ 0x38, (unsigned long *)addr) | |
452 | #define ext2_clear_bit_atomic(l,nr,addr) test_and_clear_bit((nr) ^ 0x38, (unsigned long *)addr) | |
453 | #else | |
454 | #define ext2_set_bit(nr, addr) __test_and_set_bit((nr) ^ 0x18, (unsigned long *)addr) | |
455 | #define ext2_set_bit_atomic(l,nr,addr) test_and_set_bit((nr) ^ 0x18, (unsigned long *)addr) | |
456 | #define ext2_clear_bit(nr, addr) __test_and_clear_bit((nr) ^ 0x18, (unsigned long *)addr) | |
457 | #define ext2_clear_bit_atomic(l,nr,addr) test_and_clear_bit((nr) ^ 0x18, (unsigned long *)addr) | |
458 | #endif | |
459 | ||
460 | #endif /* __KERNEL__ */ | |
461 | ||
462 | static __inline__ int ext2_test_bit(int nr, __const__ void * addr) | |
463 | { | |
464 | __const__ unsigned char *ADDR = (__const__ unsigned char *) addr; | |
465 | ||
466 | return (ADDR[nr >> 3] >> (nr & 7)) & 1; | |
467 | } | |
468 | ||
469 | /* | |
470 | * This implementation of ext2_find_{first,next}_zero_bit was stolen from | |
471 | * Linus' asm-alpha/bitops.h and modified for a big-endian machine. | |
472 | */ | |
473 | ||
474 | #define ext2_find_first_zero_bit(addr, size) \ | |
475 | ext2_find_next_zero_bit((addr), (size), 0) | |
476 | ||
477 | extern __inline__ unsigned long ext2_find_next_zero_bit(void *addr, | |
478 | unsigned long size, unsigned long offset) | |
479 | { | |
480 | unsigned int *p = ((unsigned int *) addr) + (offset >> 5); | |
481 | unsigned int result = offset & ~31UL; | |
482 | unsigned int tmp; | |
483 | ||
484 | if (offset >= size) | |
485 | return size; | |
486 | size -= result; | |
487 | offset &= 31UL; | |
488 | if (offset) { | |
489 | tmp = cpu_to_le32p(p++); | |
490 | tmp |= ~0UL >> (32-offset); | |
491 | if (size < 32) | |
492 | goto found_first; | |
493 | if (tmp != ~0U) | |
494 | goto found_middle; | |
495 | size -= 32; | |
496 | result += 32; | |
497 | } | |
498 | while (size >= 32) { | |
499 | if ((tmp = cpu_to_le32p(p++)) != ~0U) | |
500 | goto found_middle; | |
501 | result += 32; | |
502 | size -= 32; | |
503 | } | |
504 | if (!size) | |
505 | return result; | |
506 | tmp = cpu_to_le32p(p); | |
507 | found_first: | |
508 | tmp |= ~0U << size; | |
509 | found_middle: | |
510 | return result + ffz(tmp); | |
511 | } | |
512 | ||
513 | /* Bitmap functions for the minix filesystem. */ | |
514 | #define minix_test_and_set_bit(nr,addr) ext2_set_bit(nr,addr) | |
515 | #define minix_set_bit(nr,addr) ((void)ext2_set_bit(nr,addr)) | |
516 | #define minix_test_and_clear_bit(nr,addr) ext2_clear_bit(nr,addr) | |
517 | #define minix_test_bit(nr,addr) ext2_test_bit(nr,addr) | |
518 | #define minix_find_first_zero_bit(addr,size) ext2_find_first_zero_bit(addr,size) | |
519 | ||
520 | #endif /* _PARISC_BITOPS_H */ |