1 /* bit search implementation
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
6 * Copyright (C) 2008 IBM Corporation
7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
8 * (Inspired by David Howell's find_next_bit implementation)
10 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
11 * size and improve performance, 2015.
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation; either version
16 * 2 of the License, or (at your option) any later version.
19 #include <linux/bitops.h>
20 #include <linux/bitmap.h>
21 #include <linux/export.h>
22 #include <linux/kernel.h>
24 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
27 * This is a common helper function for find_next_bit and
28 * find_next_zero_bit. The difference is the "invert" argument, which
29 * is XORed with each fetched word before searching it for one bits.
31 static unsigned long _find_next_bit(const unsigned long *addr,
32 unsigned long nbits, unsigned long start, unsigned long invert)
36 if (!nbits || start >= nbits)
39 tmp = addr[start / BITS_PER_LONG] ^ invert;
41 /* Handle 1st word. */
42 tmp &= BITMAP_FIRST_WORD_MASK(start);
43 start = round_down(start, BITS_PER_LONG);
46 start += BITS_PER_LONG;
50 tmp = addr[start / BITS_PER_LONG] ^ invert;
53 return min(start + __ffs(tmp), nbits);
59 * Find the next set bit in a memory region.
61 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
64 return _find_next_bit(addr, size, offset, 0UL);
66 EXPORT_SYMBOL(find_next_bit);
69 #ifndef find_next_zero_bit
70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
73 return _find_next_bit(addr, size, offset, ~0UL);
75 EXPORT_SYMBOL(find_next_zero_bit);
78 #ifndef find_first_bit
80 * Find the first set bit in a memory region.
82 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
86 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
88 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
93 EXPORT_SYMBOL(find_first_bit);
96 #ifndef find_first_zero_bit
98 * Find the first cleared bit in a memory region.
100 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
104 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
105 if (addr[idx] != ~0UL)
106 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
111 EXPORT_SYMBOL(find_first_zero_bit);
114 #ifndef find_last_bit
115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
118 unsigned long val = BITMAP_LAST_WORD_MASK(size);
119 unsigned long idx = (size-1) / BITS_PER_LONG;
124 return idx * BITS_PER_LONG + __fls(val);
131 EXPORT_SYMBOL(find_last_bit);
136 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
137 static unsigned long _find_next_bit_le(const unsigned long *addr,
138 unsigned long nbits, unsigned long start, unsigned long invert)
142 if (!nbits || start >= nbits)
145 tmp = addr[start / BITS_PER_LONG] ^ invert;
147 /* Handle 1st word. */
148 tmp &= swab(BITMAP_FIRST_WORD_MASK(start));
149 start = round_down(start, BITS_PER_LONG);
152 start += BITS_PER_LONG;
156 tmp = addr[start / BITS_PER_LONG] ^ invert;
159 return min(start + __ffs(swab(tmp)), nbits);
163 #ifndef find_next_zero_bit_le
164 unsigned long find_next_zero_bit_le(const void *addr, unsigned
165 long size, unsigned long offset)
167 return _find_next_bit_le(addr, size, offset, ~0UL);
169 EXPORT_SYMBOL(find_next_zero_bit_le);
172 #ifndef find_next_bit_le
173 unsigned long find_next_bit_le(const void *addr, unsigned
174 long size, unsigned long offset)
176 return _find_next_bit_le(addr, size, offset, 0UL);
178 EXPORT_SYMBOL(find_next_bit_le);
181 #endif /* __BIG_ENDIAN */