1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * MSB0 numbered special bitops handling.
4  *
5  * The bits are numbered:
6  *   |0..............63|64............127|128...........191|192...........255|
7  *
8  * The reason for this bit numbering is the fact that the hardware sets bits
9  * in a bitmap starting at bit 0 (MSB) and we don't want to scan the bitmap
10  * from the 'wrong end'.
11  */
12 
13 #include <linux/compiler.h>
14 #include <linux/bitops.h>
15 #include <linux/export.h>
16 
find_first_bit_inv(const unsigned long * addr,unsigned long size)17 unsigned long find_first_bit_inv(const unsigned long *addr, unsigned long size)
18 {
19 	const unsigned long *p = addr;
20 	unsigned long result = 0;
21 	unsigned long tmp;
22 
23 	while (size & ~(BITS_PER_LONG - 1)) {
24 		if ((tmp = *(p++)))
25 			goto found;
26 		result += BITS_PER_LONG;
27 		size -= BITS_PER_LONG;
28 	}
29 	if (!size)
30 		return result;
31 	tmp = (*p) & (~0UL << (BITS_PER_LONG - size));
32 	if (!tmp)		/* Are any bits set? */
33 		return result + size;	/* Nope. */
34 found:
35 	return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
36 }
37 EXPORT_SYMBOL(find_first_bit_inv);
38 
find_next_bit_inv(const unsigned long * addr,unsigned long size,unsigned long offset)39 unsigned long find_next_bit_inv(const unsigned long *addr, unsigned long size,
40 				unsigned long offset)
41 {
42 	const unsigned long *p = addr + (offset / BITS_PER_LONG);
43 	unsigned long result = offset & ~(BITS_PER_LONG - 1);
44 	unsigned long tmp;
45 
46 	if (offset >= size)
47 		return size;
48 	size -= result;
49 	offset %= BITS_PER_LONG;
50 	if (offset) {
51 		tmp = *(p++);
52 		tmp &= (~0UL >> offset);
53 		if (size < BITS_PER_LONG)
54 			goto found_first;
55 		if (tmp)
56 			goto found_middle;
57 		size -= BITS_PER_LONG;
58 		result += BITS_PER_LONG;
59 	}
60 	while (size & ~(BITS_PER_LONG-1)) {
61 		if ((tmp = *(p++)))
62 			goto found_middle;
63 		result += BITS_PER_LONG;
64 		size -= BITS_PER_LONG;
65 	}
66 	if (!size)
67 		return result;
68 	tmp = *p;
69 found_first:
70 	tmp &= (~0UL << (BITS_PER_LONG - size));
71 	if (!tmp)		/* Are any bits set? */
72 		return result + size;	/* Nope. */
73 found_middle:
74 	return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
75 }
76 EXPORT_SYMBOL(find_next_bit_inv);
77