aboutsummaryrefslogtreecommitdiffstats
path: root/include/asm-mips/bitops.h
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /include/asm-mips/bitops.h
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'include/asm-mips/bitops.h')
-rw-r--r--include/asm-mips/bitops.h850
1 files changed, 850 insertions, 0 deletions
diff --git a/include/asm-mips/bitops.h b/include/asm-mips/bitops.h
new file mode 100644
index 000000000000..779d2187a6a4
--- /dev/null
+++ b/include/asm-mips/bitops.h
@@ -0,0 +1,850 @@
1/*
2 * This file is subject to the terms and conditions of the GNU General Public
3 * License. See the file "COPYING" in the main directory of this archive
4 * for more details.
5 *
6 * Copyright (c) 1994 - 1997, 1999, 2000 Ralf Baechle (ralf@gnu.org)
7 * Copyright (c) 1999, 2000 Silicon Graphics, Inc.
8 */
9#ifndef _ASM_BITOPS_H
10#define _ASM_BITOPS_H
11
12#include <linux/config.h>
13#include <linux/compiler.h>
14#include <linux/types.h>
15#include <asm/byteorder.h> /* sigh ... */
16#include <asm/cpu-features.h>
17
18#if (_MIPS_SZLONG == 32)
19#define SZLONG_LOG 5
20#define SZLONG_MASK 31UL
21#define __LL "ll "
22#define __SC "sc "
23#define cpu_to_lelongp(x) cpu_to_le32p((__u32 *) (x))
24#elif (_MIPS_SZLONG == 64)
25#define SZLONG_LOG 6
26#define SZLONG_MASK 63UL
27#define __LL "lld "
28#define __SC "scd "
29#define cpu_to_lelongp(x) cpu_to_le64p((__u64 *) (x))
30#endif
31
32#ifdef __KERNEL__
33
34#include <asm/interrupt.h>
35#include <asm/sgidefs.h>
36#include <asm/war.h>
37
38/*
39 * clear_bit() doesn't provide any barrier for the compiler.
40 */
41#define smp_mb__before_clear_bit() smp_mb()
42#define smp_mb__after_clear_bit() smp_mb()
43
44/*
45 * Only disable interrupt for kernel mode stuff to keep usermode stuff
46 * that dares to use kernel include files alive.
47 */
48
49#define __bi_flags unsigned long flags
50#define __bi_local_irq_save(x) local_irq_save(x)
51#define __bi_local_irq_restore(x) local_irq_restore(x)
52#else
53#define __bi_flags
54#define __bi_local_irq_save(x)
55#define __bi_local_irq_restore(x)
56#endif /* __KERNEL__ */
57
58/*
59 * set_bit - Atomically set a bit in memory
60 * @nr: the bit to set
61 * @addr: the address to start counting from
62 *
63 * This function is atomic and may not be reordered. See __set_bit()
64 * if you do not require the atomic guarantees.
65 * Note that @nr may be almost arbitrarily large; this function is not
66 * restricted to acting on a single-word quantity.
67 */
68static inline void set_bit(unsigned long nr, volatile unsigned long *addr)
69{
70 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
71 unsigned long temp;
72
73 if (cpu_has_llsc && R10000_LLSC_WAR) {
74 __asm__ __volatile__(
75 "1: " __LL "%0, %1 # set_bit \n"
76 " or %0, %2 \n"
77 " "__SC "%0, %1 \n"
78 " beqzl %0, 1b \n"
79 : "=&r" (temp), "=m" (*m)
80 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
81 } else if (cpu_has_llsc) {
82 __asm__ __volatile__(
83 "1: " __LL "%0, %1 # set_bit \n"
84 " or %0, %2 \n"
85 " "__SC "%0, %1 \n"
86 " beqz %0, 1b \n"
87 : "=&r" (temp), "=m" (*m)
88 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
89 } else {
90 volatile unsigned long *a = addr;
91 unsigned long mask;
92 __bi_flags;
93
94 a += nr >> SZLONG_LOG;
95 mask = 1UL << (nr & SZLONG_MASK);
96 __bi_local_irq_save(flags);
97 *a |= mask;
98 __bi_local_irq_restore(flags);
99 }
100}
101
102/*
103 * __set_bit - Set a bit in memory
104 * @nr: the bit to set
105 * @addr: the address to start counting from
106 *
107 * Unlike set_bit(), this function is non-atomic and may be reordered.
108 * If it's called on the same region of memory simultaneously, the effect
109 * may be that only one operation succeeds.
110 */
111static inline void __set_bit(unsigned long nr, volatile unsigned long * addr)
112{
113 unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
114
115 *m |= 1UL << (nr & SZLONG_MASK);
116}
117
118/*
119 * clear_bit - Clears a bit in memory
120 * @nr: Bit to clear
121 * @addr: Address to start counting from
122 *
123 * clear_bit() is atomic and may not be reordered. However, it does
124 * not contain a memory barrier, so if it is used for locking purposes,
125 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
126 * in order to ensure changes are visible on other processors.
127 */
128static inline void clear_bit(unsigned long nr, volatile unsigned long *addr)
129{
130 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
131 unsigned long temp;
132
133 if (cpu_has_llsc && R10000_LLSC_WAR) {
134 __asm__ __volatile__(
135 "1: " __LL "%0, %1 # clear_bit \n"
136 " and %0, %2 \n"
137 " " __SC "%0, %1 \n"
138 " beqzl %0, 1b \n"
139 : "=&r" (temp), "=m" (*m)
140 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
141 } else if (cpu_has_llsc) {
142 __asm__ __volatile__(
143 "1: " __LL "%0, %1 # clear_bit \n"
144 " and %0, %2 \n"
145 " " __SC "%0, %1 \n"
146 " beqz %0, 1b \n"
147 : "=&r" (temp), "=m" (*m)
148 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
149 } else {
150 volatile unsigned long *a = addr;
151 unsigned long mask;
152 __bi_flags;
153
154 a += nr >> SZLONG_LOG;
155 mask = 1UL << (nr & SZLONG_MASK);
156 __bi_local_irq_save(flags);
157 *a &= ~mask;
158 __bi_local_irq_restore(flags);
159 }
160}
161
162/*
163 * __clear_bit - Clears a bit in memory
164 * @nr: Bit to clear
165 * @addr: Address to start counting from
166 *
167 * Unlike clear_bit(), this function is non-atomic and may be reordered.
168 * If it's called on the same region of memory simultaneously, the effect
169 * may be that only one operation succeeds.
170 */
171static inline void __clear_bit(unsigned long nr, volatile unsigned long * addr)
172{
173 unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
174
175 *m &= ~(1UL << (nr & SZLONG_MASK));
176}
177
178/*
179 * change_bit - Toggle a bit in memory
180 * @nr: Bit to change
181 * @addr: Address to start counting from
182 *
183 * change_bit() is atomic and may not be reordered.
184 * Note that @nr may be almost arbitrarily large; this function is not
185 * restricted to acting on a single-word quantity.
186 */
187static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
188{
189 if (cpu_has_llsc && R10000_LLSC_WAR) {
190 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
191 unsigned long temp;
192
193 __asm__ __volatile__(
194 "1: " __LL "%0, %1 # change_bit \n"
195 " xor %0, %2 \n"
196 " "__SC "%0, %1 \n"
197 " beqzl %0, 1b \n"
198 : "=&r" (temp), "=m" (*m)
199 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
200 } else if (cpu_has_llsc) {
201 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
202 unsigned long temp;
203
204 __asm__ __volatile__(
205 "1: " __LL "%0, %1 # change_bit \n"
206 " xor %0, %2 \n"
207 " "__SC "%0, %1 \n"
208 " beqz %0, 1b \n"
209 : "=&r" (temp), "=m" (*m)
210 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
211 } else {
212 volatile unsigned long *a = addr;
213 unsigned long mask;
214 __bi_flags;
215
216 a += nr >> SZLONG_LOG;
217 mask = 1UL << (nr & SZLONG_MASK);
218 __bi_local_irq_save(flags);
219 *a ^= mask;
220 __bi_local_irq_restore(flags);
221 }
222}
223
224/*
225 * __change_bit - Toggle a bit in memory
226 * @nr: the bit to change
227 * @addr: the address to start counting from
228 *
229 * Unlike change_bit(), this function is non-atomic and may be reordered.
230 * If it's called on the same region of memory simultaneously, the effect
231 * may be that only one operation succeeds.
232 */
233static inline void __change_bit(unsigned long nr, volatile unsigned long * addr)
234{
235 unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
236
237 *m ^= 1UL << (nr & SZLONG_MASK);
238}
239
240/*
241 * test_and_set_bit - Set a bit and return its old value
242 * @nr: Bit to set
243 * @addr: Address to count from
244 *
245 * This operation is atomic and cannot be reordered.
246 * It also implies a memory barrier.
247 */
248static inline int test_and_set_bit(unsigned long nr,
249 volatile unsigned long *addr)
250{
251 if (cpu_has_llsc && R10000_LLSC_WAR) {
252 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
253 unsigned long temp, res;
254
255 __asm__ __volatile__(
256 "1: " __LL "%0, %1 # test_and_set_bit \n"
257 " or %2, %0, %3 \n"
258 " " __SC "%2, %1 \n"
259 " beqzl %2, 1b \n"
260 " and %2, %0, %3 \n"
261#ifdef CONFIG_SMP
262 "sync \n"
263#endif
264 : "=&r" (temp), "=m" (*m), "=&r" (res)
265 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
266 : "memory");
267
268 return res != 0;
269 } else if (cpu_has_llsc) {
270 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
271 unsigned long temp, res;
272
273 __asm__ __volatile__(
274 " .set noreorder # test_and_set_bit \n"
275 "1: " __LL "%0, %1 \n"
276 " or %2, %0, %3 \n"
277 " " __SC "%2, %1 \n"
278 " beqz %2, 1b \n"
279 " and %2, %0, %3 \n"
280#ifdef CONFIG_SMP
281 "sync \n"
282#endif
283 ".set\treorder"
284 : "=&r" (temp), "=m" (*m), "=&r" (res)
285 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
286 : "memory");
287
288 return res != 0;
289 } else {
290 volatile unsigned long *a = addr;
291 unsigned long mask;
292 int retval;
293 __bi_flags;
294
295 a += nr >> SZLONG_LOG;
296 mask = 1UL << (nr & SZLONG_MASK);
297 __bi_local_irq_save(flags);
298 retval = (mask & *a) != 0;
299 *a |= mask;
300 __bi_local_irq_restore(flags);
301
302 return retval;
303 }
304}
305
306/*
307 * __test_and_set_bit - Set a bit and return its old value
308 * @nr: Bit to set
309 * @addr: Address to count from
310 *
311 * This operation is non-atomic and can be reordered.
312 * If two examples of this operation race, one can appear to succeed
313 * but actually fail. You must protect multiple accesses with a lock.
314 */
315static inline int __test_and_set_bit(unsigned long nr,
316 volatile unsigned long *addr)
317{
318 volatile unsigned long *a = addr;
319 unsigned long mask;
320 int retval;
321
322 a += nr >> SZLONG_LOG;
323 mask = 1UL << (nr & SZLONG_MASK);
324 retval = (mask & *a) != 0;
325 *a |= mask;
326
327 return retval;
328}
329
330/*
331 * test_and_clear_bit - Clear a bit and return its old value
332 * @nr: Bit to clear
333 * @addr: Address to count from
334 *
335 * This operation is atomic and cannot be reordered.
336 * It also implies a memory barrier.
337 */
338static inline int test_and_clear_bit(unsigned long nr,
339 volatile unsigned long *addr)
340{
341 if (cpu_has_llsc && R10000_LLSC_WAR) {
342 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
343 unsigned long temp, res;
344
345 __asm__ __volatile__(
346 "1: " __LL "%0, %1 # test_and_clear_bit \n"
347 " or %2, %0, %3 \n"
348 " xor %2, %3 \n"
349 __SC "%2, %1 \n"
350 " beqzl %2, 1b \n"
351 " and %2, %0, %3 \n"
352#ifdef CONFIG_SMP
353 " sync \n"
354#endif
355 : "=&r" (temp), "=m" (*m), "=&r" (res)
356 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
357 : "memory");
358
359 return res != 0;
360 } else if (cpu_has_llsc) {
361 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
362 unsigned long temp, res;
363
364 __asm__ __volatile__(
365 " .set noreorder # test_and_clear_bit \n"
366 "1: " __LL "%0, %1 \n"
367 " or %2, %0, %3 \n"
368 " xor %2, %3 \n"
369 __SC "%2, %1 \n"
370 " beqz %2, 1b \n"
371 " and %2, %0, %3 \n"
372#ifdef CONFIG_SMP
373 " sync \n"
374#endif
375 " .set reorder \n"
376 : "=&r" (temp), "=m" (*m), "=&r" (res)
377 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
378 : "memory");
379
380 return res != 0;
381 } else {
382 volatile unsigned long *a = addr;
383 unsigned long mask;
384 int retval;
385 __bi_flags;
386
387 a += nr >> SZLONG_LOG;
388 mask = 1UL << (nr & SZLONG_MASK);
389 __bi_local_irq_save(flags);
390 retval = (mask & *a) != 0;
391 *a &= ~mask;
392 __bi_local_irq_restore(flags);
393
394 return retval;
395 }
396}
397
398/*
399 * __test_and_clear_bit - Clear a bit and return its old value
400 * @nr: Bit to clear
401 * @addr: Address to count from
402 *
403 * This operation is non-atomic and can be reordered.
404 * If two examples of this operation race, one can appear to succeed
405 * but actually fail. You must protect multiple accesses with a lock.
406 */
407static inline int __test_and_clear_bit(unsigned long nr,
408 volatile unsigned long * addr)
409{
410 volatile unsigned long *a = addr;
411 unsigned long mask;
412 int retval;
413
414 a += (nr >> SZLONG_LOG);
415 mask = 1UL << (nr & SZLONG_MASK);
416 retval = ((mask & *a) != 0);
417 *a &= ~mask;
418
419 return retval;
420}
421
422/*
423 * test_and_change_bit - Change a bit and return its old value
424 * @nr: Bit to change
425 * @addr: Address to count from
426 *
427 * This operation is atomic and cannot be reordered.
428 * It also implies a memory barrier.
429 */
430static inline int test_and_change_bit(unsigned long nr,
431 volatile unsigned long *addr)
432{
433 if (cpu_has_llsc && R10000_LLSC_WAR) {
434 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
435 unsigned long temp, res;
436
437 __asm__ __volatile__(
438 "1: " __LL " %0, %1 # test_and_change_bit \n"
439 " xor %2, %0, %3 \n"
440 " "__SC "%2, %1 \n"
441 " beqzl %2, 1b \n"
442 " and %2, %0, %3 \n"
443#ifdef CONFIG_SMP
444 " sync \n"
445#endif
446 : "=&r" (temp), "=m" (*m), "=&r" (res)
447 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
448 : "memory");
449
450 return res != 0;
451 } else if (cpu_has_llsc) {
452 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
453 unsigned long temp, res;
454
455 __asm__ __volatile__(
456 " .set noreorder # test_and_change_bit \n"
457 "1: " __LL " %0, %1 \n"
458 " xor %2, %0, %3 \n"
459 " "__SC "\t%2, %1 \n"
460 " beqz %2, 1b \n"
461 " and %2, %0, %3 \n"
462#ifdef CONFIG_SMP
463 " sync \n"
464#endif
465 " .set reorder \n"
466 : "=&r" (temp), "=m" (*m), "=&r" (res)
467 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
468 : "memory");
469
470 return res != 0;
471 } else {
472 volatile unsigned long *a = addr;
473 unsigned long mask, retval;
474 __bi_flags;
475
476 a += nr >> SZLONG_LOG;
477 mask = 1UL << (nr & SZLONG_MASK);
478 __bi_local_irq_save(flags);
479 retval = (mask & *a) != 0;
480 *a ^= mask;
481 __bi_local_irq_restore(flags);
482
483 return retval;
484 }
485}
486
487/*
488 * __test_and_change_bit - Change a bit and return its old value
489 * @nr: Bit to change
490 * @addr: Address to count from
491 *
492 * This operation is non-atomic and can be reordered.
493 * If two examples of this operation race, one can appear to succeed
494 * but actually fail. You must protect multiple accesses with a lock.
495 */
496static inline int __test_and_change_bit(unsigned long nr,
497 volatile unsigned long *addr)
498{
499 volatile unsigned long *a = addr;
500 unsigned long mask;
501 int retval;
502
503 a += (nr >> SZLONG_LOG);
504 mask = 1UL << (nr & SZLONG_MASK);
505 retval = ((mask & *a) != 0);
506 *a ^= mask;
507
508 return retval;
509}
510
511#undef __bi_flags
512#undef __bi_local_irq_save
513#undef __bi_local_irq_restore
514
515/*
516 * test_bit - Determine whether a bit is set
517 * @nr: bit number to test
518 * @addr: Address to start counting from
519 */
520static inline int test_bit(unsigned long nr, const volatile unsigned long *addr)
521{
522 return 1UL & (addr[nr >> SZLONG_LOG] >> (nr & SZLONG_MASK));
523}
524
525/*
526 * ffz - find first zero in word.
527 * @word: The word to search
528 *
529 * Undefined if no zero exists, so code should check against ~0UL first.
530 */
531static inline unsigned long ffz(unsigned long word)
532{
533 int b = 0, s;
534
535 word = ~word;
536#ifdef CONFIG_MIPS32
537 s = 16; if (word << 16 != 0) s = 0; b += s; word >>= s;
538 s = 8; if (word << 24 != 0) s = 0; b += s; word >>= s;
539 s = 4; if (word << 28 != 0) s = 0; b += s; word >>= s;
540 s = 2; if (word << 30 != 0) s = 0; b += s; word >>= s;
541 s = 1; if (word << 31 != 0) s = 0; b += s;
542#endif
543#ifdef CONFIG_MIPS64
544 s = 32; if (word << 32 != 0) s = 0; b += s; word >>= s;
545 s = 16; if (word << 48 != 0) s = 0; b += s; word >>= s;
546 s = 8; if (word << 56 != 0) s = 0; b += s; word >>= s;
547 s = 4; if (word << 60 != 0) s = 0; b += s; word >>= s;
548 s = 2; if (word << 62 != 0) s = 0; b += s; word >>= s;
549 s = 1; if (word << 63 != 0) s = 0; b += s;
550#endif
551
552 return b;
553}
554
555/*
556 * __ffs - find first bit in word.
557 * @word: The word to search
558 *
559 * Undefined if no bit exists, so code should check against 0 first.
560 */
561static inline unsigned long __ffs(unsigned long word)
562{
563 return ffz(~word);
564}
565
566/*
567 * fls: find last bit set.
568 */
569
570#define fls(x) generic_fls(x)
571
572/*
573 * find_next_zero_bit - find the first zero bit in a memory region
574 * @addr: The address to base the search on
575 * @offset: The bitnumber to start searching at
576 * @size: The maximum size to search
577 */
578static inline unsigned long find_next_zero_bit(const unsigned long *addr,
579 unsigned long size, unsigned long offset)
580{
581 const unsigned long *p = addr + (offset >> SZLONG_LOG);
582 unsigned long result = offset & ~SZLONG_MASK;
583 unsigned long tmp;
584
585 if (offset >= size)
586 return size;
587 size -= result;
588 offset &= SZLONG_MASK;
589 if (offset) {
590 tmp = *(p++);
591 tmp |= ~0UL >> (_MIPS_SZLONG-offset);
592 if (size < _MIPS_SZLONG)
593 goto found_first;
594 if (~tmp)
595 goto found_middle;
596 size -= _MIPS_SZLONG;
597 result += _MIPS_SZLONG;
598 }
599 while (size & ~SZLONG_MASK) {
600 if (~(tmp = *(p++)))
601 goto found_middle;
602 result += _MIPS_SZLONG;
603 size -= _MIPS_SZLONG;
604 }
605 if (!size)
606 return result;
607 tmp = *p;
608
609found_first:
610 tmp |= ~0UL << size;
611 if (tmp == ~0UL) /* Are any bits zero? */
612 return result + size; /* Nope. */
613found_middle:
614 return result + ffz(tmp);
615}
616
617#define find_first_zero_bit(addr, size) \
618 find_next_zero_bit((addr), (size), 0)
619
620/*
621 * find_next_bit - find the next set bit in a memory region
622 * @addr: The address to base the search on
623 * @offset: The bitnumber to start searching at
624 * @size: The maximum size to search
625 */
626static inline unsigned long find_next_bit(const unsigned long *addr,
627 unsigned long size, unsigned long offset)
628{
629 const unsigned long *p = addr + (offset >> SZLONG_LOG);
630 unsigned long result = offset & ~SZLONG_MASK;
631 unsigned long tmp;
632
633 if (offset >= size)
634 return size;
635 size -= result;
636 offset &= SZLONG_MASK;
637 if (offset) {
638 tmp = *(p++);
639 tmp &= ~0UL << offset;
640 if (size < _MIPS_SZLONG)
641 goto found_first;
642 if (tmp)
643 goto found_middle;
644 size -= _MIPS_SZLONG;
645 result += _MIPS_SZLONG;
646 }
647 while (size & ~SZLONG_MASK) {
648 if ((tmp = *(p++)))
649 goto found_middle;
650 result += _MIPS_SZLONG;
651 size -= _MIPS_SZLONG;
652 }
653 if (!size)
654 return result;
655 tmp = *p;
656
657found_first:
658 tmp &= ~0UL >> (_MIPS_SZLONG - size);
659 if (tmp == 0UL) /* Are any bits set? */
660 return result + size; /* Nope. */
661found_middle:
662 return result + __ffs(tmp);
663}
664
665/*
666 * find_first_bit - find the first set bit in a memory region
667 * @addr: The address to start the search at
668 * @size: The maximum size to search
669 *
670 * Returns the bit-number of the first set bit, not the number of the byte
671 * containing a bit.
672 */
673#define find_first_bit(addr, size) \
674 find_next_bit((addr), (size), 0)
675
676#ifdef __KERNEL__
677
678/*
679 * Every architecture must define this function. It's the fastest
680 * way of searching a 140-bit bitmap where the first 100 bits are
681 * unlikely to be set. It's guaranteed that at least one of the 140
682 * bits is cleared.
683 */
684static inline int sched_find_first_bit(const unsigned long *b)
685{
686#ifdef CONFIG_MIPS32
687 if (unlikely(b[0]))
688 return __ffs(b[0]);
689 if (unlikely(b[1]))
690 return __ffs(b[1]) + 32;
691 if (unlikely(b[2]))
692 return __ffs(b[2]) + 64;
693 if (b[3])
694 return __ffs(b[3]) + 96;
695 return __ffs(b[4]) + 128;
696#endif
697#ifdef CONFIG_MIPS64
698 if (unlikely(b[0]))
699 return __ffs(b[0]);
700 if (unlikely(b[1]))
701 return __ffs(b[1]) + 64;
702 return __ffs(b[2]) + 128;
703#endif
704}
705
706/*
707 * ffs - find first bit set
708 * @x: the word to search
709 *
710 * This is defined the same way as
711 * the libc and compiler builtin ffs routines, therefore
712 * differs in spirit from the above ffz (man ffs).
713 */
714
715#define ffs(x) generic_ffs(x)
716
717/*
718 * hweightN - returns the hamming weight of a N-bit word
719 * @x: the word to weigh
720 *
721 * The Hamming Weight of a number is the total number of bits set in it.
722 */
723
724#define hweight64(x) generic_hweight64(x)
725#define hweight32(x) generic_hweight32(x)
726#define hweight16(x) generic_hweight16(x)
727#define hweight8(x) generic_hweight8(x)
728
729static inline int __test_and_set_le_bit(unsigned long nr, unsigned long *addr)
730{
731 unsigned char *ADDR = (unsigned char *) addr;
732 int mask, retval;
733
734 ADDR += nr >> 3;
735 mask = 1 << (nr & 0x07);
736 retval = (mask & *ADDR) != 0;
737 *ADDR |= mask;
738
739 return retval;
740}
741
742static inline int __test_and_clear_le_bit(unsigned long nr, unsigned long *addr)
743{
744 unsigned char *ADDR = (unsigned char *) addr;
745 int mask, retval;
746
747 ADDR += nr >> 3;
748 mask = 1 << (nr & 0x07);
749 retval = (mask & *ADDR) != 0;
750 *ADDR &= ~mask;
751
752 return retval;
753}
754
755static inline int test_le_bit(unsigned long nr, const unsigned long * addr)
756{
757 const unsigned char *ADDR = (const unsigned char *) addr;
758 int mask;
759
760 ADDR += nr >> 3;
761 mask = 1 << (nr & 0x07);
762
763 return ((mask & *ADDR) != 0);
764}
765
766static inline unsigned long find_next_zero_le_bit(unsigned long *addr,
767 unsigned long size, unsigned long offset)
768{
769 unsigned long *p = ((unsigned long *) addr) + (offset >> SZLONG_LOG);
770 unsigned long result = offset & ~SZLONG_MASK;
771 unsigned long tmp;
772
773 if (offset >= size)
774 return size;
775 size -= result;
776 offset &= SZLONG_MASK;
777 if (offset) {
778 tmp = cpu_to_lelongp(p++);
779 tmp |= ~0UL >> (_MIPS_SZLONG-offset); /* bug or feature ? */
780 if (size < _MIPS_SZLONG)
781 goto found_first;
782 if (~tmp)
783 goto found_middle;
784 size -= _MIPS_SZLONG;
785 result += _MIPS_SZLONG;
786 }
787 while (size & ~SZLONG_MASK) {
788 if (~(tmp = cpu_to_lelongp(p++)))
789 goto found_middle;
790 result += _MIPS_SZLONG;
791 size -= _MIPS_SZLONG;
792 }
793 if (!size)
794 return result;
795 tmp = cpu_to_lelongp(p);
796
797found_first:
798 tmp |= ~0UL << size;
799 if (tmp == ~0UL) /* Are any bits zero? */
800 return result + size; /* Nope. */
801
802found_middle:
803 return result + ffz(tmp);
804}
805
806#define find_first_zero_le_bit(addr, size) \
807 find_next_zero_le_bit((addr), (size), 0)
808
809#define ext2_set_bit(nr,addr) \
810 __test_and_set_le_bit((nr),(unsigned long*)addr)
811#define ext2_clear_bit(nr, addr) \
812 __test_and_clear_le_bit((nr),(unsigned long*)addr)
813 #define ext2_set_bit_atomic(lock, nr, addr) \
814({ \
815 int ret; \
816 spin_lock(lock); \
817 ret = ext2_set_bit((nr), (addr)); \
818 spin_unlock(lock); \
819 ret; \
820})
821
822#define ext2_clear_bit_atomic(lock, nr, addr) \
823({ \
824 int ret; \
825 spin_lock(lock); \
826 ret = ext2_clear_bit((nr), (addr)); \
827 spin_unlock(lock); \
828 ret; \
829})
830#define ext2_test_bit(nr, addr) test_le_bit((nr),(unsigned long*)addr)
831#define ext2_find_first_zero_bit(addr, size) \
832 find_first_zero_le_bit((unsigned long*)addr, size)
833#define ext2_find_next_zero_bit(addr, size, off) \
834 find_next_zero_le_bit((unsigned long*)addr, size, off)
835
836/*
837 * Bitmap functions for the minix filesystem.
838 *
839 * FIXME: These assume that Minix uses the native byte/bitorder.
840 * This limits the Minix filesystem's value for data exchange very much.
841 */
842#define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
843#define minix_set_bit(nr,addr) set_bit(nr,addr)
844#define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
845#define minix_test_bit(nr,addr) test_bit(nr,addr)
846#define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
847
848#endif /* __KERNEL__ */
849
850#endif /* _ASM_BITOPS_H */