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
17unsigned 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. */
34found:
35	return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
36}
37EXPORT_SYMBOL(find_first_bit_inv);
38
39unsigned 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;
69found_first:
70	tmp &= (~0UL << (BITS_PER_LONG - size));
71	if (!tmp)		/* Are any bits set? */
72		return result + size;	/* Nope. */
73found_middle:
74	return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
75}
76EXPORT_SYMBOL(find_next_bit_inv);

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