2 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
3 * Written by David Howells (dhowells@redhat.com)
4 * Copyright (C) 2008 IBM Corporation
5 * Written by Rusty Russell <rusty@rustcorp.com.au>
6 * (Inspired by David Howell's find_next_bit implementation)
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
16 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
19 * Find the next set bit in a memory region.
21 unsigned long find_next_bit(const unsigned long *addr
, unsigned long size
,
24 const unsigned long *p
= addr
+ BITOP_WORD(offset
);
25 unsigned long result
= offset
& ~(BITS_PER_LONG
-1);
32 offset
%= BITS_PER_LONG
;
35 tmp
&= (~0UL << offset
);
36 if (size
< BITS_PER_LONG
) {
42 size
-= BITS_PER_LONG
;
43 result
+= BITS_PER_LONG
;
45 while (size
& ~(BITS_PER_LONG
-1)) {
49 result
+= BITS_PER_LONG
;
50 size
-= BITS_PER_LONG
;
58 tmp
&= (~0UL >> (BITS_PER_LONG
- size
));
59 if (tmp
== 0UL) { /* Are any bits set? */
60 return result
+ size
; /* Nope. */
63 return result
+ bitops_ffsl(tmp
);
67 * This implementation of find_{first,next}_zero_bit was stolen from
68 * Linus' asm-alpha/bitops.h.
70 unsigned long find_next_zero_bit(const unsigned long *addr
, unsigned long size
,
73 const unsigned long *p
= addr
+ BITOP_WORD(offset
);
74 unsigned long result
= offset
& ~(BITS_PER_LONG
-1);
81 offset
%= BITS_PER_LONG
;
84 tmp
|= ~0UL >> (BITS_PER_LONG
- offset
);
85 if (size
< BITS_PER_LONG
) {
91 size
-= BITS_PER_LONG
;
92 result
+= BITS_PER_LONG
;
94 while (size
& ~(BITS_PER_LONG
-1)) {
95 if (~(tmp
= *(p
++))) {
98 result
+= BITS_PER_LONG
;
99 size
-= BITS_PER_LONG
;
108 if (tmp
== ~0UL) { /* Are any bits zero? */
109 return result
+ size
; /* Nope. */
112 return result
+ ffz(tmp
);
115 unsigned long find_last_bit(const unsigned long *addr
, unsigned long size
)
120 /* Start at final word. */
121 words
= size
/ BITS_PER_LONG
;
123 /* Partial final word? */
124 if (size
& (BITS_PER_LONG
-1)) {
125 tmp
= (addr
[words
] & (~0UL >> (BITS_PER_LONG
126 - (size
& (BITS_PER_LONG
-1)))));
136 return words
* BITS_PER_LONG
+ bitops_flsl(tmp
);