projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
s390/bitops: fix find_next_bit_left
[deliverable/linux.git] / arch / s390 / include / asm / bitops.h
1 /*
2 * S390 version
3 * Copyright IBM Corp. 1999
4 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com)
5 *
6 * Derived from "include/asm-i386/bitops.h"
7 * Copyright (C) 1992, Linus Torvalds
8 *
9 */
10
11 #ifndef _S390_BITOPS_H
12 #define _S390_BITOPS_H
13
14 #ifndef _LINUX_BITOPS_H
15 #error only <linux/bitops.h> can be included directly
16 #endif
17
18 #include <linux/compiler.h>
19
20 /*
21 * 32 bit bitops format:
22 * bit 0 is the LSB of *addr; bit 31 is the MSB of *addr;
23 * bit 32 is the LSB of *(addr+4). That combined with the
24 * big endian byte order on S390 give the following bit
25 * order in memory:
26 * 1f 1e 1d 1c 1b 1a 19 18 17 16 15 14 13 12 11 10 \
27 * 0f 0e 0d 0c 0b 0a 09 08 07 06 05 04 03 02 01 00
28 * after that follows the next long with bit numbers
29 * 3f 3e 3d 3c 3b 3a 39 38 37 36 35 34 33 32 31 30
30 * 2f 2e 2d 2c 2b 2a 29 28 27 26 25 24 23 22 21 20
31 * The reason for this bit ordering is the fact that
32 * in the architecture independent code bits operations
33 * of the form "flags |= (1 << bitnr)" are used INTERMIXED
34 * with operation of the form "set_bit(bitnr, flags)".
35 *
36 * 64 bit bitops format:
37 * bit 0 is the LSB of *addr; bit 63 is the MSB of *addr;
38 * bit 64 is the LSB of *(addr+8). That combined with the
39 * big endian byte order on S390 give the following bit
40 * order in memory:
41 * 3f 3e 3d 3c 3b 3a 39 38 37 36 35 34 33 32 31 30
42 * 2f 2e 2d 2c 2b 2a 29 28 27 26 25 24 23 22 21 20
43 * 1f 1e 1d 1c 1b 1a 19 18 17 16 15 14 13 12 11 10
44 * 0f 0e 0d 0c 0b 0a 09 08 07 06 05 04 03 02 01 00
45 * after that follows the next long with bit numbers
46 * 7f 7e 7d 7c 7b 7a 79 78 77 76 75 74 73 72 71 70
47 * 6f 6e 6d 6c 6b 6a 69 68 67 66 65 64 63 62 61 60
48 * 5f 5e 5d 5c 5b 5a 59 58 57 56 55 54 53 52 51 50
49 * 4f 4e 4d 4c 4b 4a 49 48 47 46 45 44 43 42 41 40
50 * The reason for this bit ordering is the fact that
51 * in the architecture independent code bits operations
52 * of the form "flags |= (1 << bitnr)" are used INTERMIXED
53 * with operation of the form "set_bit(bitnr, flags)".
54 */
55
56 /* bitmap tables from arch/s390/kernel/bitmap.c */
57 extern const char _oi_bitmap[];
58 extern const char _ni_bitmap[];
59 extern const char _zb_findmap[];
60 extern const char _sb_findmap[];
61
62 #ifndef CONFIG_64BIT
63
64 #define __BITOPS_OR "or"
65 #define __BITOPS_AND "nr"
66 #define __BITOPS_XOR "xr"
67
68 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \
69 asm volatile( \
70 " l %0,%2\n" \
71 "0: lr %1,%0\n" \
72 __op_string " %1,%3\n" \
73 " cs %0,%1,%2\n" \
74 " jl 0b" \
75 : "=&d" (__old), "=&d" (__new), \
76 "=Q" (*(unsigned long *) __addr) \
77 : "d" (__val), "Q" (*(unsigned long *) __addr) \
78 : "cc");
79
80 #else /* CONFIG_64BIT */
81
82 #define __BITOPS_OR "ogr"
83 #define __BITOPS_AND "ngr"
84 #define __BITOPS_XOR "xgr"
85
86 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \
87 asm volatile( \
88 " lg %0,%2\n" \
89 "0: lgr %1,%0\n" \
90 __op_string " %1,%3\n" \
91 " csg %0,%1,%2\n" \
92 " jl 0b" \
93 : "=&d" (__old), "=&d" (__new), \
94 "=Q" (*(unsigned long *) __addr) \
95 : "d" (__val), "Q" (*(unsigned long *) __addr) \
96 : "cc");
97
98 #endif /* CONFIG_64BIT */
99
100 #define __BITOPS_WORDS(bits) (((bits) + BITS_PER_LONG - 1) / BITS_PER_LONG)
101
102 #ifdef CONFIG_SMP
103 /*
104 * SMP safe set_bit routine based on compare and swap (CS)
105 */
106 static inline void set_bit_cs(unsigned long nr, volatile unsigned long *ptr)
107 {
108 unsigned long addr, old, new, mask;
109
110 addr = (unsigned long) ptr;
111 /* calculate address for CS */
112 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
113 /* make OR mask */
114 mask = 1UL << (nr & (BITS_PER_LONG - 1));
115 /* Do the atomic update. */
116 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_OR);
117 }
118
119 /*
120 * SMP safe clear_bit routine based on compare and swap (CS)
121 */
122 static inline void clear_bit_cs(unsigned long nr, volatile unsigned long *ptr)
123 {
124 unsigned long addr, old, new, mask;
125
126 addr = (unsigned long) ptr;
127 /* calculate address for CS */
128 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
129 /* make AND mask */
130 mask = ~(1UL << (nr & (BITS_PER_LONG - 1)));
131 /* Do the atomic update. */
132 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_AND);
133 }
134
135 /*
136 * SMP safe change_bit routine based on compare and swap (CS)
137 */
138 static inline void change_bit_cs(unsigned long nr, volatile unsigned long *ptr)
139 {
140 unsigned long addr, old, new, mask;
141
142 addr = (unsigned long) ptr;
143 /* calculate address for CS */
144 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
145 /* make XOR mask */
146 mask = 1UL << (nr & (BITS_PER_LONG - 1));
147 /* Do the atomic update. */
148 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_XOR);
149 }
150
151 /*
152 * SMP safe test_and_set_bit routine based on compare and swap (CS)
153 */
154 static inline int
155 test_and_set_bit_cs(unsigned long nr, volatile unsigned long *ptr)
156 {
157 unsigned long addr, old, new, mask;
158
159 addr = (unsigned long) ptr;
160 /* calculate address for CS */
161 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
162 /* make OR/test mask */
163 mask = 1UL << (nr & (BITS_PER_LONG - 1));
164 /* Do the atomic update. */
165 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_OR);
166 barrier();
167 return (old & mask) != 0;
168 }
169
170 /*
171 * SMP safe test_and_clear_bit routine based on compare and swap (CS)
172 */
173 static inline int
174 test_and_clear_bit_cs(unsigned long nr, volatile unsigned long *ptr)
175 {
176 unsigned long addr, old, new, mask;
177
178 addr = (unsigned long) ptr;
179 /* calculate address for CS */
180 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
181 /* make AND/test mask */
182 mask = ~(1UL << (nr & (BITS_PER_LONG - 1)));
183 /* Do the atomic update. */
184 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_AND);
185 barrier();
186 return (old ^ new) != 0;
187 }
188
189 /*
190 * SMP safe test_and_change_bit routine based on compare and swap (CS)
191 */
192 static inline int
193 test_and_change_bit_cs(unsigned long nr, volatile unsigned long *ptr)
194 {
195 unsigned long addr, old, new, mask;
196
197 addr = (unsigned long) ptr;
198 /* calculate address for CS */
199 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3;
200 /* make XOR/test mask */
201 mask = 1UL << (nr & (BITS_PER_LONG - 1));
202 /* Do the atomic update. */
203 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_XOR);
204 barrier();
205 return (old & mask) != 0;
206 }
207 #endif /* CONFIG_SMP */
208
209 /*
210 * fast, non-SMP set_bit routine
211 */
212 static inline void __set_bit(unsigned long nr, volatile unsigned long *ptr)
213 {
214 unsigned long addr;
215
216 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
217 asm volatile(
218 " oc %O0(1,%R0),%1"
219 : "=Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) : "cc" );
220 }
221
222 static inline void
223 __constant_set_bit(const unsigned long nr, volatile unsigned long *ptr)
224 {
225 unsigned long addr;
226
227 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
228 *(unsigned char *) addr |= 1 << (nr & 7);
229 }
230
231 #define set_bit_simple(nr,addr) \
232 (__builtin_constant_p((nr)) ? \
233 __constant_set_bit((nr),(addr)) : \
234 __set_bit((nr),(addr)) )
235
236 /*
237 * fast, non-SMP clear_bit routine
238 */
239 static inline void
240 __clear_bit(unsigned long nr, volatile unsigned long *ptr)
241 {
242 unsigned long addr;
243
244 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
245 asm volatile(
246 " nc %O0(1,%R0),%1"
247 : "=Q" (*(char *) addr) : "Q" (_ni_bitmap[nr & 7]) : "cc" );
248 }
249
250 static inline void
251 __constant_clear_bit(const unsigned long nr, volatile unsigned long *ptr)
252 {
253 unsigned long addr;
254
255 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
256 *(unsigned char *) addr &= ~(1 << (nr & 7));
257 }
258
259 #define clear_bit_simple(nr,addr) \
260 (__builtin_constant_p((nr)) ? \
261 __constant_clear_bit((nr),(addr)) : \
262 __clear_bit((nr),(addr)) )
263
264 /*
265 * fast, non-SMP change_bit routine
266 */
267 static inline void __change_bit(unsigned long nr, volatile unsigned long *ptr)
268 {
269 unsigned long addr;
270
271 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
272 asm volatile(
273 " xc %O0(1,%R0),%1"
274 : "=Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) : "cc" );
275 }
276
277 static inline void
278 __constant_change_bit(const unsigned long nr, volatile unsigned long *ptr)
279 {
280 unsigned long addr;
281
282 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
283 *(unsigned char *) addr ^= 1 << (nr & 7);
284 }
285
286 #define change_bit_simple(nr,addr) \
287 (__builtin_constant_p((nr)) ? \
288 __constant_change_bit((nr),(addr)) : \
289 __change_bit((nr),(addr)) )
290
291 /*
292 * fast, non-SMP test_and_set_bit routine
293 */
294 static inline int
295 test_and_set_bit_simple(unsigned long nr, volatile unsigned long *ptr)
296 {
297 unsigned long addr;
298 unsigned char ch;
299
300 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
301 ch = *(unsigned char *) addr;
302 asm volatile(
303 " oc %O0(1,%R0),%1"
304 : "=Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7])
305 : "cc", "memory");
306 return (ch >> (nr & 7)) & 1;
307 }
308 #define __test_and_set_bit(X,Y) test_and_set_bit_simple(X,Y)
309
310 /*
311 * fast, non-SMP test_and_clear_bit routine
312 */
313 static inline int
314 test_and_clear_bit_simple(unsigned long nr, volatile unsigned long *ptr)
315 {
316 unsigned long addr;
317 unsigned char ch;
318
319 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
320 ch = *(unsigned char *) addr;
321 asm volatile(
322 " nc %O0(1,%R0),%1"
323 : "=Q" (*(char *) addr) : "Q" (_ni_bitmap[nr & 7])
324 : "cc", "memory");
325 return (ch >> (nr & 7)) & 1;
326 }
327 #define __test_and_clear_bit(X,Y) test_and_clear_bit_simple(X,Y)
328
329 /*
330 * fast, non-SMP test_and_change_bit routine
331 */
332 static inline int
333 test_and_change_bit_simple(unsigned long nr, volatile unsigned long *ptr)
334 {
335 unsigned long addr;
336 unsigned char ch;
337
338 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
339 ch = *(unsigned char *) addr;
340 asm volatile(
341 " xc %O0(1,%R0),%1"
342 : "=Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7])
343 : "cc", "memory");
344 return (ch >> (nr & 7)) & 1;
345 }
346 #define __test_and_change_bit(X,Y) test_and_change_bit_simple(X,Y)
347
348 #ifdef CONFIG_SMP
349 #define set_bit set_bit_cs
350 #define clear_bit clear_bit_cs
351 #define change_bit change_bit_cs
352 #define test_and_set_bit test_and_set_bit_cs
353 #define test_and_clear_bit test_and_clear_bit_cs
354 #define test_and_change_bit test_and_change_bit_cs
355 #else
356 #define set_bit set_bit_simple
357 #define clear_bit clear_bit_simple
358 #define change_bit change_bit_simple
359 #define test_and_set_bit test_and_set_bit_simple
360 #define test_and_clear_bit test_and_clear_bit_simple
361 #define test_and_change_bit test_and_change_bit_simple
362 #endif
363
364
365 /*
366 * This routine doesn't need to be atomic.
367 */
368
369 static inline int __test_bit(unsigned long nr, const volatile unsigned long *ptr)
370 {
371 unsigned long addr;
372 unsigned char ch;
373
374 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3);
375 ch = *(volatile unsigned char *) addr;
376 return (ch >> (nr & 7)) & 1;
377 }
378
379 static inline int
380 __constant_test_bit(unsigned long nr, const volatile unsigned long *addr) {
381 return (((volatile char *) addr)
382 [(nr^(BITS_PER_LONG-8))>>3] & (1<<(nr&7))) != 0;
383 }
384
385 #define test_bit(nr,addr) \
386 (__builtin_constant_p((nr)) ? \
387 __constant_test_bit((nr),(addr)) : \
388 __test_bit((nr),(addr)) )
389
390 /*
391 * Optimized find bit helper functions.
392 */
393
394 /**
395 * __ffz_word_loop - find byte offset of first long != -1UL
396 * @addr: pointer to array of unsigned long
397 * @size: size of the array in bits
398 */
399 static inline unsigned long __ffz_word_loop(const unsigned long *addr,
400 unsigned long size)
401 {
402 typedef struct { long _[__BITOPS_WORDS(size)]; } addrtype;
403 unsigned long bytes = 0;
404
405 asm volatile(
406 #ifndef CONFIG_64BIT
407 " ahi %1,-1\n"
408 " sra %1,5\n"
409 " jz 1f\n"
410 "0: c %2,0(%0,%3)\n"
411 " jne 1f\n"
412 " la %0,4(%0)\n"
413 " brct %1,0b\n"
414 "1:\n"
415 #else
416 " aghi %1,-1\n"
417 " srag %1,%1,6\n"
418 " jz 1f\n"
419 "0: cg %2,0(%0,%3)\n"
420 " jne 1f\n"
421 " la %0,8(%0)\n"
422 " brct %1,0b\n"
423 "1:\n"
424 #endif
425 : "+&a" (bytes), "+&d" (size)
426 : "d" (-1UL), "a" (addr), "m" (*(addrtype *) addr)
427 : "cc" );
428 return bytes;
429 }
430
431 /**
432 * __ffs_word_loop - find byte offset of first long != 0UL
433 * @addr: pointer to array of unsigned long
434 * @size: size of the array in bits
435 */
436 static inline unsigned long __ffs_word_loop(const unsigned long *addr,
437 unsigned long size)
438 {
439 typedef struct { long _[__BITOPS_WORDS(size)]; } addrtype;
440 unsigned long bytes = 0;
441
442 asm volatile(
443 #ifndef CONFIG_64BIT
444 " ahi %1,-1\n"
445 " sra %1,5\n"
446 " jz 1f\n"
447 "0: c %2,0(%0,%3)\n"
448 " jne 1f\n"
449 " la %0,4(%0)\n"
450 " brct %1,0b\n"
451 "1:\n"
452 #else
453 " aghi %1,-1\n"
454 " srag %1,%1,6\n"
455 " jz 1f\n"
456 "0: cg %2,0(%0,%3)\n"
457 " jne 1f\n"
458 " la %0,8(%0)\n"
459 " brct %1,0b\n"
460 "1:\n"
461 #endif
462 : "+&a" (bytes), "+&a" (size)
463 : "d" (0UL), "a" (addr), "m" (*(addrtype *) addr)
464 : "cc" );
465 return bytes;
466 }
467
468 /**
469 * __ffz_word - add number of the first unset bit
470 * @nr: base value the bit number is added to
471 * @word: the word that is searched for unset bits
472 */
473 static inline unsigned long __ffz_word(unsigned long nr, unsigned long word)
474 {
475 #ifdef CONFIG_64BIT
476 if ((word & 0xffffffff) == 0xffffffff) {
477 word >>= 32;
478 nr += 32;
479 }
480 #endif
481 if ((word & 0xffff) == 0xffff) {
482 word >>= 16;
483 nr += 16;
484 }
485 if ((word & 0xff) == 0xff) {
486 word >>= 8;
487 nr += 8;
488 }
489 return nr + _zb_findmap[(unsigned char) word];
490 }
491
492 /**
493 * __ffs_word - add number of the first set bit
494 * @nr: base value the bit number is added to
495 * @word: the word that is searched for set bits
496 */
497 static inline unsigned long __ffs_word(unsigned long nr, unsigned long word)
498 {
499 #ifdef CONFIG_64BIT
500 if ((word & 0xffffffff) == 0) {
501 word >>= 32;
502 nr += 32;
503 }
504 #endif
505 if ((word & 0xffff) == 0) {
506 word >>= 16;
507 nr += 16;
508 }
509 if ((word & 0xff) == 0) {
510 word >>= 8;
511 nr += 8;
512 }
513 return nr + _sb_findmap[(unsigned char) word];
514 }
515
516
517 /**
518 * __load_ulong_be - load big endian unsigned long
519 * @p: pointer to array of unsigned long
520 * @offset: byte offset of source value in the array
521 */
522 static inline unsigned long __load_ulong_be(const unsigned long *p,
523 unsigned long offset)
524 {
525 p = (unsigned long *)((unsigned long) p + offset);
526 return *p;
527 }
528
529 /**
530 * __load_ulong_le - load little endian unsigned long
531 * @p: pointer to array of unsigned long
532 * @offset: byte offset of source value in the array
533 */
534 static inline unsigned long __load_ulong_le(const unsigned long *p,
535 unsigned long offset)
536 {
537 unsigned long word;
538
539 p = (unsigned long *)((unsigned long) p + offset);
540 #ifndef CONFIG_64BIT
541 asm volatile(
542 " ic %0,%O1(%R1)\n"
543 " icm %0,2,%O1+1(%R1)\n"
544 " icm %0,4,%O1+2(%R1)\n"
545 " icm %0,8,%O1+3(%R1)"
546 : "=&d" (word) : "Q" (*p) : "cc");
547 #else
548 asm volatile(
549 " lrvg %0,%1"
550 : "=d" (word) : "m" (*p) );
551 #endif
552 return word;
553 }
554
555 /*
556 * The various find bit functions.
557 */
558
559 /*
560 * ffz - find first zero in word.
561 * @word: The word to search
562 *
563 * Undefined if no zero exists, so code should check against ~0UL first.
564 */
565 static inline unsigned long ffz(unsigned long word)
566 {
567 return __ffz_word(0, word);
568 }
569
570 /**
571 * __ffs - find first bit in word.
572 * @word: The word to search
573 *
574 * Undefined if no bit exists, so code should check against 0 first.
575 */
576 static inline unsigned long __ffs (unsigned long word)
577 {
578 return __ffs_word(0, word);
579 }
580
581 /**
582 * ffs - find first bit set
583 * @x: the word to search
584 *
585 * This is defined the same way as
586 * the libc and compiler builtin ffs routines, therefore
587 * differs in spirit from the above ffz (man ffs).
588 */
589 static inline int ffs(int x)
590 {
591 if (!x)
592 return 0;
593 return __ffs_word(1, x);
594 }
595
596 /**
597 * find_first_zero_bit - find the first zero bit in a memory region
598 * @addr: The address to start the search at
599 * @size: The maximum size to search
600 *
601 * Returns the bit-number of the first zero bit, not the number of the byte
602 * containing a bit.
603 */
604 static inline unsigned long find_first_zero_bit(const unsigned long *addr,
605 unsigned long size)
606 {
607 unsigned long bytes, bits;
608
609 if (!size)
610 return 0;
611 bytes = __ffz_word_loop(addr, size);
612 bits = __ffz_word(bytes*8, __load_ulong_be(addr, bytes));
613 return (bits < size) ? bits : size;
614 }
615 #define find_first_zero_bit find_first_zero_bit
616
617 /**
618 * find_first_bit - find the first set bit in a memory region
619 * @addr: The address to start the search at
620 * @size: The maximum size to search
621 *
622 * Returns the bit-number of the first set bit, not the number of the byte
623 * containing a bit.
624 */
625 static inline unsigned long find_first_bit(const unsigned long * addr,
626 unsigned long size)
627 {
628 unsigned long bytes, bits;
629
630 if (!size)
631 return 0;
632 bytes = __ffs_word_loop(addr, size);
633 bits = __ffs_word(bytes*8, __load_ulong_be(addr, bytes));
634 return (bits < size) ? bits : size;
635 }
636 #define find_first_bit find_first_bit
637
638 /*
639 * Big endian variant whichs starts bit counting from left using
640 * the flogr (find leftmost one) instruction.
641 */
642 static inline unsigned long __flo_word(unsigned long nr, unsigned long val)
643 {
644 register unsigned long bit asm("2") = val;
645 register unsigned long out asm("3");
646
647 asm volatile (
648 " .insn rre,0xb9830000,%[bit],%[bit]\n"
649 : [bit] "+d" (bit), [out] "=d" (out) : : "cc");
650 return nr + bit;
651 }
652
653 /*
654 * 64 bit special left bitops format:
655 * order in memory:
656 * 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
657 * 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
658 * 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
659 * 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
660 * after that follows the next long with bit numbers
661 * 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
662 * 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
663 * 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
664 * 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
665 * The reason for this bit ordering is the fact that
666 * the hardware sets bits in a bitmap starting at bit 0
667 * and we don't want to scan the bitmap from the 'wrong
668 * end'.
669 */
670 static inline unsigned long find_first_bit_left(const unsigned long *addr,
671 unsigned long size)
672 {
673 unsigned long bytes, bits;
674
675 if (!size)
676 return 0;
677 bytes = __ffs_word_loop(addr, size);
678 bits = __flo_word(bytes * 8, __load_ulong_be(addr, bytes));
679 return (bits < size) ? bits : size;
680 }
681
682 static inline int find_next_bit_left(const unsigned long *addr,
683 unsigned long size,
684 unsigned long offset)
685 {
686 const unsigned long *p;
687 unsigned long bit, set;
688
689 if (offset >= size)
690 return size;
691 bit = offset & (BITS_PER_LONG - 1);
692 offset -= bit;
693 size -= offset;
694 p = addr + offset / BITS_PER_LONG;
695 if (bit) {
696 set = __flo_word(0, *p & (~0UL >> bit));
697 if (set >= size)
698 return size + offset;
699 if (set < BITS_PER_LONG)
700 return set + offset;
701 offset += BITS_PER_LONG;
702 size -= BITS_PER_LONG;
703 p++;
704 }
705 return offset + find_first_bit_left(p, size);
706 }
707
708 #define for_each_set_bit_left(bit, addr, size) \
709 for ((bit) = find_first_bit_left((addr), (size)); \
710 (bit) < (size); \
711 (bit) = find_next_bit_left((addr), (size), (bit) + 1))
712
713 /* same as for_each_set_bit() but use bit as value to start with */
714 #define for_each_set_bit_left_cont(bit, addr, size) \
715 for ((bit) = find_next_bit_left((addr), (size), (bit)); \
716 (bit) < (size); \
717 (bit) = find_next_bit_left((addr), (size), (bit) + 1))
718
719 /**
720 * find_next_zero_bit - find the first zero bit in a memory region
721 * @addr: The address to base the search on
722 * @offset: The bitnumber to start searching at
723 * @size: The maximum size to search
724 */
725 static inline int find_next_zero_bit (const unsigned long * addr,
726 unsigned long size,
727 unsigned long offset)
728 {
729 const unsigned long *p;
730 unsigned long bit, set;
731
732 if (offset >= size)
733 return size;
734 bit = offset & (BITS_PER_LONG - 1);
735 offset -= bit;
736 size -= offset;
737 p = addr + offset / BITS_PER_LONG;
738 if (bit) {
739 /*
740 * __ffz_word returns BITS_PER_LONG
741 * if no zero bit is present in the word.
742 */
743 set = __ffz_word(bit, *p >> bit);
744 if (set >= size)
745 return size + offset;
746 if (set < BITS_PER_LONG)
747 return set + offset;
748 offset += BITS_PER_LONG;
749 size -= BITS_PER_LONG;
750 p++;
751 }
752 return offset + find_first_zero_bit(p, size);
753 }
754 #define find_next_zero_bit find_next_zero_bit
755
756 /**
757 * find_next_bit - find the first set bit in a memory region
758 * @addr: The address to base the search on
759 * @offset: The bitnumber to start searching at
760 * @size: The maximum size to search
761 */
762 static inline int find_next_bit (const unsigned long * addr,
763 unsigned long size,
764 unsigned long offset)
765 {
766 const unsigned long *p;
767 unsigned long bit, set;
768
769 if (offset >= size)
770 return size;
771 bit = offset & (BITS_PER_LONG - 1);
772 offset -= bit;
773 size -= offset;
774 p = addr + offset / BITS_PER_LONG;
775 if (bit) {
776 /*
777 * __ffs_word returns BITS_PER_LONG
778 * if no one bit is present in the word.
779 */
780 set = __ffs_word(0, *p & (~0UL << bit));
781 if (set >= size)
782 return size + offset;
783 if (set < BITS_PER_LONG)
784 return set + offset;
785 offset += BITS_PER_LONG;
786 size -= BITS_PER_LONG;
787 p++;
788 }
789 return offset + find_first_bit(p, size);
790 }
791 #define find_next_bit find_next_bit
792
793 /*
794 * Every architecture must define this function. It's the fastest
795 * way of searching a 140-bit bitmap where the first 100 bits are
796 * unlikely to be set. It's guaranteed that at least one of the 140
797 * bits is cleared.
798 */
799 static inline int sched_find_first_bit(unsigned long *b)
800 {
801 return find_first_bit(b, 140);
802 }
803
804 #include <asm-generic/bitops/fls.h>
805 #include <asm-generic/bitops/__fls.h>
806 #include <asm-generic/bitops/fls64.h>
807
808 #include <asm-generic/bitops/hweight.h>
809 #include <asm-generic/bitops/lock.h>
810
811 /*
812 * ATTENTION: intel byte ordering convention for ext2 and minix !!
813 * bit 0 is the LSB of addr; bit 31 is the MSB of addr;
814 * bit 32 is the LSB of (addr+4).
815 * That combined with the little endian byte order of Intel gives the
816 * following bit order in memory:
817 * 07 06 05 04 03 02 01 00 15 14 13 12 11 10 09 08 \
818 * 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24
819 */
820
821 static inline int find_first_zero_bit_le(void *vaddr, unsigned int size)
822 {
823 unsigned long bytes, bits;
824
825 if (!size)
826 return 0;
827 bytes = __ffz_word_loop(vaddr, size);
828 bits = __ffz_word(bytes*8, __load_ulong_le(vaddr, bytes));
829 return (bits < size) ? bits : size;
830 }
831 #define find_first_zero_bit_le find_first_zero_bit_le
832
833 static inline int find_next_zero_bit_le(void *vaddr, unsigned long size,
834 unsigned long offset)
835 {
836 unsigned long *addr = vaddr, *p;
837 unsigned long bit, set;
838
839 if (offset >= size)
840 return size;
841 bit = offset & (BITS_PER_LONG - 1);
842 offset -= bit;
843 size -= offset;
844 p = addr + offset / BITS_PER_LONG;
845 if (bit) {
846 /*
847 * s390 version of ffz returns BITS_PER_LONG
848 * if no zero bit is present in the word.
849 */
850 set = __ffz_word(bit, __load_ulong_le(p, 0) >> bit);
851 if (set >= size)
852 return size + offset;
853 if (set < BITS_PER_LONG)
854 return set + offset;
855 offset += BITS_PER_LONG;
856 size -= BITS_PER_LONG;
857 p++;
858 }
859 return offset + find_first_zero_bit_le(p, size);
860 }
861 #define find_next_zero_bit_le find_next_zero_bit_le
862
863 static inline unsigned long find_first_bit_le(void *vaddr, unsigned long size)
864 {
865 unsigned long bytes, bits;
866
867 if (!size)
868 return 0;
869 bytes = __ffs_word_loop(vaddr, size);
870 bits = __ffs_word(bytes*8, __load_ulong_le(vaddr, bytes));
871 return (bits < size) ? bits : size;
872 }
873 #define find_first_bit_le find_first_bit_le
874
875 static inline int find_next_bit_le(void *vaddr, unsigned long size,
876 unsigned long offset)
877 {
878 unsigned long *addr = vaddr, *p;
879 unsigned long bit, set;
880
881 if (offset >= size)
882 return size;
883 bit = offset & (BITS_PER_LONG - 1);
884 offset -= bit;
885 size -= offset;
886 p = addr + offset / BITS_PER_LONG;
887 if (bit) {
888 /*
889 * s390 version of ffz returns BITS_PER_LONG
890 * if no zero bit is present in the word.
891 */
892 set = __ffs_word(0, __load_ulong_le(p, 0) & (~0UL << bit));
893 if (set >= size)
894 return size + offset;
895 if (set < BITS_PER_LONG)
896 return set + offset;
897 offset += BITS_PER_LONG;
898 size -= BITS_PER_LONG;
899 p++;
900 }
901 return offset + find_first_bit_le(p, size);
902 }
903 #define find_next_bit_le find_next_bit_le
904
905 #include <asm-generic/bitops/le.h>
906
907 #include <asm-generic/bitops/ext2-atomic-setbit.h>
908
909 #endif /* _S390_BITOPS_H */
Linux kernel - Deliverables
This page took 0.088663 seconds and 5 git commands to generate.