Root/lib/find_next_bit.c

1/* find_next_bit.c: fallback find next bit implementation
2 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 */
11
12#include <linux/bitops.h>
13#include <linux/module.h>
14#include <asm/types.h>
15#include <asm/byteorder.h>
16
17#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
18
19#ifdef CONFIG_GENERIC_FIND_NEXT_BIT
20/*
21 * Find the next set bit in a memory region.
22 */
23unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24                unsigned long offset)
25{
26    const unsigned long *p = addr + BITOP_WORD(offset);
27    unsigned long result = offset & ~(BITS_PER_LONG-1);
28    unsigned long tmp;
29
30    if (offset >= size)
31        return size;
32    size -= result;
33    offset %= BITS_PER_LONG;
34    if (offset) {
35        tmp = *(p++);
36        tmp &= (~0UL << offset);
37        if (size < BITS_PER_LONG)
38            goto found_first;
39        if (tmp)
40            goto found_middle;
41        size -= BITS_PER_LONG;
42        result += BITS_PER_LONG;
43    }
44    while (size & ~(BITS_PER_LONG-1)) {
45        if ((tmp = *(p++)))
46            goto found_middle;
47        result += BITS_PER_LONG;
48        size -= BITS_PER_LONG;
49    }
50    if (!size)
51        return result;
52    tmp = *p;
53
54found_first:
55    tmp &= (~0UL >> (BITS_PER_LONG - size));
56    if (tmp == 0UL) /* Are any bits set? */
57        return result + size; /* Nope. */
58found_middle:
59    return result + __ffs(tmp);
60}
61EXPORT_SYMBOL(find_next_bit);
62
63/*
64 * This implementation of find_{first,next}_zero_bit was stolen from
65 * Linus' asm-alpha/bitops.h.
66 */
67unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
68                 unsigned long offset)
69{
70    const unsigned long *p = addr + BITOP_WORD(offset);
71    unsigned long result = offset & ~(BITS_PER_LONG-1);
72    unsigned long tmp;
73
74    if (offset >= size)
75        return size;
76    size -= result;
77    offset %= BITS_PER_LONG;
78    if (offset) {
79        tmp = *(p++);
80        tmp |= ~0UL >> (BITS_PER_LONG - offset);
81        if (size < BITS_PER_LONG)
82            goto found_first;
83        if (~tmp)
84            goto found_middle;
85        size -= BITS_PER_LONG;
86        result += BITS_PER_LONG;
87    }
88    while (size & ~(BITS_PER_LONG-1)) {
89        if (~(tmp = *(p++)))
90            goto found_middle;
91        result += BITS_PER_LONG;
92        size -= BITS_PER_LONG;
93    }
94    if (!size)
95        return result;
96    tmp = *p;
97
98found_first:
99    tmp |= ~0UL << size;
100    if (tmp == ~0UL) /* Are any bits zero? */
101        return result + size; /* Nope. */
102found_middle:
103    return result + ffz(tmp);
104}
105EXPORT_SYMBOL(find_next_zero_bit);
106#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
107
108#ifdef CONFIG_GENERIC_FIND_FIRST_BIT
109/*
110 * Find the first set bit in a memory region.
111 */
112unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
113{
114    const unsigned long *p = addr;
115    unsigned long result = 0;
116    unsigned long tmp;
117
118    while (size & ~(BITS_PER_LONG-1)) {
119        if ((tmp = *(p++)))
120            goto found;
121        result += BITS_PER_LONG;
122        size -= BITS_PER_LONG;
123    }
124    if (!size)
125        return result;
126
127    tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
128    if (tmp == 0UL) /* Are any bits set? */
129        return result + size; /* Nope. */
130found:
131    return result + __ffs(tmp);
132}
133EXPORT_SYMBOL(find_first_bit);
134
135/*
136 * Find the first cleared bit in a memory region.
137 */
138unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
139{
140    const unsigned long *p = addr;
141    unsigned long result = 0;
142    unsigned long tmp;
143
144    while (size & ~(BITS_PER_LONG-1)) {
145        if (~(tmp = *(p++)))
146            goto found;
147        result += BITS_PER_LONG;
148        size -= BITS_PER_LONG;
149    }
150    if (!size)
151        return result;
152
153    tmp = (*p) | (~0UL << size);
154    if (tmp == ~0UL) /* Are any bits zero? */
155        return result + size; /* Nope. */
156found:
157    return result + ffz(tmp);
158}
159EXPORT_SYMBOL(find_first_zero_bit);
160#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
161
162#ifdef __BIG_ENDIAN
163
164/* include/linux/byteorder does not support "unsigned long" type */
165static inline unsigned long ext2_swabp(const unsigned long * x)
166{
167#if BITS_PER_LONG == 64
168    return (unsigned long) __swab64p((u64 *) x);
169#elif BITS_PER_LONG == 32
170    return (unsigned long) __swab32p((u32 *) x);
171#else
172#error BITS_PER_LONG not defined
173#endif
174}
175
176/* include/linux/byteorder doesn't support "unsigned long" type */
177static inline unsigned long ext2_swab(const unsigned long y)
178{
179#if BITS_PER_LONG == 64
180    return (unsigned long) __swab64((u64) y);
181#elif BITS_PER_LONG == 32
182    return (unsigned long) __swab32((u32) y);
183#else
184#error BITS_PER_LONG not defined
185#endif
186}
187
188unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
189        long size, unsigned long offset)
190{
191    const unsigned long *p = addr + BITOP_WORD(offset);
192    unsigned long result = offset & ~(BITS_PER_LONG - 1);
193    unsigned long tmp;
194
195    if (offset >= size)
196        return size;
197    size -= result;
198    offset &= (BITS_PER_LONG - 1UL);
199    if (offset) {
200        tmp = ext2_swabp(p++);
201        tmp |= (~0UL >> (BITS_PER_LONG - offset));
202        if (size < BITS_PER_LONG)
203            goto found_first;
204        if (~tmp)
205            goto found_middle;
206        size -= BITS_PER_LONG;
207        result += BITS_PER_LONG;
208    }
209
210    while (size & ~(BITS_PER_LONG - 1)) {
211        if (~(tmp = *(p++)))
212            goto found_middle_swap;
213        result += BITS_PER_LONG;
214        size -= BITS_PER_LONG;
215    }
216    if (!size)
217        return result;
218    tmp = ext2_swabp(p);
219found_first:
220    tmp |= ~0UL << size;
221    if (tmp == ~0UL) /* Are any bits zero? */
222        return result + size; /* Nope. Skip ffz */
223found_middle:
224    return result + ffz(tmp);
225
226found_middle_swap:
227    return result + ffz(ext2_swab(tmp));
228}
229
230EXPORT_SYMBOL(generic_find_next_zero_le_bit);
231
232unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
233        long size, unsigned long offset)
234{
235    const unsigned long *p = addr + BITOP_WORD(offset);
236    unsigned long result = offset & ~(BITS_PER_LONG - 1);
237    unsigned long tmp;
238
239    if (offset >= size)
240        return size;
241    size -= result;
242    offset &= (BITS_PER_LONG - 1UL);
243    if (offset) {
244        tmp = ext2_swabp(p++);
245        tmp &= (~0UL << offset);
246        if (size < BITS_PER_LONG)
247            goto found_first;
248        if (tmp)
249            goto found_middle;
250        size -= BITS_PER_LONG;
251        result += BITS_PER_LONG;
252    }
253
254    while (size & ~(BITS_PER_LONG - 1)) {
255        tmp = *(p++);
256        if (tmp)
257            goto found_middle_swap;
258        result += BITS_PER_LONG;
259        size -= BITS_PER_LONG;
260    }
261    if (!size)
262        return result;
263    tmp = ext2_swabp(p);
264found_first:
265    tmp &= (~0UL >> (BITS_PER_LONG - size));
266    if (tmp == 0UL) /* Are any bits set? */
267        return result + size; /* Nope. */
268found_middle:
269    return result + __ffs(tmp);
270
271found_middle_swap:
272    return result + __ffs(ext2_swab(tmp));
273}
274EXPORT_SYMBOL(generic_find_next_le_bit);
275#endif /* __BIG_ENDIAN */
276

Archive Download this file



interactive