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/export.h>
14#include <asm/types.h>
15#include <asm/byteorder.h>
16
17#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
18
19#ifndef 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#endif
63
64#ifndef find_next_zero_bit
65/*
66 * This implementation of find_{first,next}_zero_bit was stolen from
67 * Linus' asm-alpha/bitops.h.
68 */
69unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
70                 unsigned long offset)
71{
72    const unsigned long *p = addr + BITOP_WORD(offset);
73    unsigned long result = offset & ~(BITS_PER_LONG-1);
74    unsigned long tmp;
75
76    if (offset >= size)
77        return size;
78    size -= result;
79    offset %= BITS_PER_LONG;
80    if (offset) {
81        tmp = *(p++);
82        tmp |= ~0UL >> (BITS_PER_LONG - offset);
83        if (size < BITS_PER_LONG)
84            goto found_first;
85        if (~tmp)
86            goto found_middle;
87        size -= BITS_PER_LONG;
88        result += BITS_PER_LONG;
89    }
90    while (size & ~(BITS_PER_LONG-1)) {
91        if (~(tmp = *(p++)))
92            goto found_middle;
93        result += BITS_PER_LONG;
94        size -= BITS_PER_LONG;
95    }
96    if (!size)
97        return result;
98    tmp = *p;
99
100found_first:
101    tmp |= ~0UL << size;
102    if (tmp == ~0UL) /* Are any bits zero? */
103        return result + size; /* Nope. */
104found_middle:
105    return result + ffz(tmp);
106}
107EXPORT_SYMBOL(find_next_zero_bit);
108#endif
109
110#ifndef find_first_bit
111/*
112 * Find the first set bit in a memory region.
113 */
114unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
115{
116    const unsigned long *p = addr;
117    unsigned long result = 0;
118    unsigned long tmp;
119
120    while (size & ~(BITS_PER_LONG-1)) {
121        if ((tmp = *(p++)))
122            goto found;
123        result += BITS_PER_LONG;
124        size -= BITS_PER_LONG;
125    }
126    if (!size)
127        return result;
128
129    tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
130    if (tmp == 0UL) /* Are any bits set? */
131        return result + size; /* Nope. */
132found:
133    return result + __ffs(tmp);
134}
135EXPORT_SYMBOL(find_first_bit);
136#endif
137
138#ifndef find_first_zero_bit
139/*
140 * Find the first cleared bit in a memory region.
141 */
142unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
143{
144    const unsigned long *p = addr;
145    unsigned long result = 0;
146    unsigned long tmp;
147
148    while (size & ~(BITS_PER_LONG-1)) {
149        if (~(tmp = *(p++)))
150            goto found;
151        result += BITS_PER_LONG;
152        size -= BITS_PER_LONG;
153    }
154    if (!size)
155        return result;
156
157    tmp = (*p) | (~0UL << size);
158    if (tmp == ~0UL) /* Are any bits zero? */
159        return result + size; /* Nope. */
160found:
161    return result + ffz(tmp);
162}
163EXPORT_SYMBOL(find_first_zero_bit);
164#endif
165
166#ifdef __BIG_ENDIAN
167
168/* include/linux/byteorder does not support "unsigned long" type */
169static inline unsigned long ext2_swabp(const unsigned long * x)
170{
171#if BITS_PER_LONG == 64
172    return (unsigned long) __swab64p((u64 *) x);
173#elif BITS_PER_LONG == 32
174    return (unsigned long) __swab32p((u32 *) x);
175#else
176#error BITS_PER_LONG not defined
177#endif
178}
179
180/* include/linux/byteorder doesn't support "unsigned long" type */
181static inline unsigned long ext2_swab(const unsigned long y)
182{
183#if BITS_PER_LONG == 64
184    return (unsigned long) __swab64((u64) y);
185#elif BITS_PER_LONG == 32
186    return (unsigned long) __swab32((u32) y);
187#else
188#error BITS_PER_LONG not defined
189#endif
190}
191
192#ifndef find_next_zero_bit_le
193unsigned long find_next_zero_bit_le(const void *addr, unsigned
194        long size, unsigned long offset)
195{
196    const unsigned long *p = addr;
197    unsigned long result = offset & ~(BITS_PER_LONG - 1);
198    unsigned long tmp;
199
200    if (offset >= size)
201        return size;
202    p += BITOP_WORD(offset);
203    size -= result;
204    offset &= (BITS_PER_LONG - 1UL);
205    if (offset) {
206        tmp = ext2_swabp(p++);
207        tmp |= (~0UL >> (BITS_PER_LONG - offset));
208        if (size < BITS_PER_LONG)
209            goto found_first;
210        if (~tmp)
211            goto found_middle;
212        size -= BITS_PER_LONG;
213        result += BITS_PER_LONG;
214    }
215
216    while (size & ~(BITS_PER_LONG - 1)) {
217        if (~(tmp = *(p++)))
218            goto found_middle_swap;
219        result += BITS_PER_LONG;
220        size -= BITS_PER_LONG;
221    }
222    if (!size)
223        return result;
224    tmp = ext2_swabp(p);
225found_first:
226    tmp |= ~0UL << size;
227    if (tmp == ~0UL) /* Are any bits zero? */
228        return result + size; /* Nope. Skip ffz */
229found_middle:
230    return result + ffz(tmp);
231
232found_middle_swap:
233    return result + ffz(ext2_swab(tmp));
234}
235EXPORT_SYMBOL(find_next_zero_bit_le);
236#endif
237
238#ifndef find_next_bit_le
239unsigned long find_next_bit_le(const void *addr, unsigned
240        long size, unsigned long offset)
241{
242    const unsigned long *p = addr;
243    unsigned long result = offset & ~(BITS_PER_LONG - 1);
244    unsigned long tmp;
245
246    if (offset >= size)
247        return size;
248    p += BITOP_WORD(offset);
249    size -= result;
250    offset &= (BITS_PER_LONG - 1UL);
251    if (offset) {
252        tmp = ext2_swabp(p++);
253        tmp &= (~0UL << offset);
254        if (size < BITS_PER_LONG)
255            goto found_first;
256        if (tmp)
257            goto found_middle;
258        size -= BITS_PER_LONG;
259        result += BITS_PER_LONG;
260    }
261
262    while (size & ~(BITS_PER_LONG - 1)) {
263        tmp = *(p++);
264        if (tmp)
265            goto found_middle_swap;
266        result += BITS_PER_LONG;
267        size -= BITS_PER_LONG;
268    }
269    if (!size)
270        return result;
271    tmp = ext2_swabp(p);
272found_first:
273    tmp &= (~0UL >> (BITS_PER_LONG - size));
274    if (tmp == 0UL) /* Are any bits set? */
275        return result + size; /* Nope. */
276found_middle:
277    return result + __ffs(tmp);
278
279found_middle_swap:
280    return result + __ffs(ext2_swab(tmp));
281}
282EXPORT_SYMBOL(find_next_bit_le);
283#endif
284
285#endif /* __BIG_ENDIAN */
286

Archive Download this file



interactive