xref: /kernel/linux/linux-5.10/lib/find_bit.c (revision 8c2ecf20) 
1// SPDX-License-Identifier: GPL-2.0-or-later
2/* bit search implementation
3 *
4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
5 * Written by David Howells (dhowells@redhat.com)
6 *
7 * Copyright (C) 2008 IBM Corporation
8 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
9 * (Inspired by David Howell's find_next_bit implementation)
10 *
11 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
12 * size and improve performance, 2015.
13 */
14
15#include <linux/bitops.h>
16#include <linux/bitmap.h>
17#include <linux/export.h>
18#include <linux/kernel.h>
19#include <linux/minmax.h>
20
21#if !defined(find_next_bit) || !defined(find_next_zero_bit) ||			\
22	!defined(find_next_bit_le) || !defined(find_next_zero_bit_le) ||	\
23	!defined(find_next_and_bit)
24/*
25 * This is a common helper function for find_next_bit, find_next_zero_bit, and
26 * find_next_and_bit. The differences are:
27 *  - The "invert" argument, which is XORed with each fetched word before
28 *    searching it for one bits.
29 *  - The optional "addr2", which is anded with "addr1" if present.
30 */
31static unsigned long _find_next_bit(const unsigned long *addr1,
32		const unsigned long *addr2, unsigned long nbits,
33		unsigned long start, unsigned long invert, unsigned long le)
34{
35	unsigned long tmp, mask;
36
37	if (unlikely(start >= nbits))
38		return nbits;
39
40	tmp = addr1[start / BITS_PER_LONG];
41	if (addr2)
42		tmp &= addr2[start / BITS_PER_LONG];
43	tmp ^= invert;
44
45	/* Handle 1st word. */
46	mask = BITMAP_FIRST_WORD_MASK(start);
47	if (le)
48		mask = swab(mask);
49
50	tmp &= mask;
51
52	start = round_down(start, BITS_PER_LONG);
53
54	while (!tmp) {
55		start += BITS_PER_LONG;
56		if (start >= nbits)
57			return nbits;
58
59		tmp = addr1[start / BITS_PER_LONG];
60		if (addr2)
61			tmp &= addr2[start / BITS_PER_LONG];
62		tmp ^= invert;
63	}
64
65	if (le)
66		tmp = swab(tmp);
67
68	return min(start + __ffs(tmp), nbits);
69}
70#endif
71
72#ifndef find_next_bit
73/*
74 * Find the next set bit in a memory region.
75 */
76unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
77			    unsigned long offset)
78{
79	return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
80}
81EXPORT_SYMBOL(find_next_bit);
82#endif
83
84#ifndef find_next_zero_bit
85unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
86				 unsigned long offset)
87{
88	return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
89}
90EXPORT_SYMBOL(find_next_zero_bit);
91#endif
92
93#if !defined(find_next_and_bit)
94unsigned long find_next_and_bit(const unsigned long *addr1,
95		const unsigned long *addr2, unsigned long size,
96		unsigned long offset)
97{
98	return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
99}
100EXPORT_SYMBOL(find_next_and_bit);
101#endif
102
103#ifndef find_first_bit
104/*
105 * Find the first set bit in a memory region.
106 */
107unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
108{
109	unsigned long idx;
110
111	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
112		if (addr[idx])
113			return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
114	}
115
116	return size;
117}
118EXPORT_SYMBOL(find_first_bit);
119#endif
120
121#ifndef find_first_zero_bit
122/*
123 * Find the first cleared bit in a memory region.
124 */
125unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
126{
127	unsigned long idx;
128
129	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
130		if (addr[idx] != ~0UL)
131			return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
132	}
133
134	return size;
135}
136EXPORT_SYMBOL(find_first_zero_bit);
137#endif
138
139#ifndef find_last_bit
140unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
141{
142	if (size) {
143		unsigned long val = BITMAP_LAST_WORD_MASK(size);
144		unsigned long idx = (size-1) / BITS_PER_LONG;
145
146		do {
147			val &= addr[idx];
148			if (val)
149				return idx * BITS_PER_LONG + __fls(val);
150
151			val = ~0ul;
152		} while (idx--);
153	}
154	return size;
155}
156EXPORT_SYMBOL(find_last_bit);
157#endif
158
159#ifdef __BIG_ENDIAN
160
161#ifndef find_next_zero_bit_le
162unsigned long find_next_zero_bit_le(const void *addr, unsigned
163		long size, unsigned long offset)
164{
165	return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
166}
167EXPORT_SYMBOL(find_next_zero_bit_le);
168#endif
169
170#ifndef find_next_bit_le
171unsigned long find_next_bit_le(const void *addr, unsigned
172		long size, unsigned long offset)
173{
174	return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
175}
176EXPORT_SYMBOL(find_next_bit_le);
177#endif
178
179#endif /* __BIG_ENDIAN */
180
181unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
182			       unsigned long size, unsigned long offset)
183{
184	offset = find_next_bit(addr, size, offset);
185	if (offset == size)
186		return size;
187
188	offset = round_down(offset, 8);
189	*clump = bitmap_get_value8(addr, offset);
190
191	return offset;
192}
193EXPORT_SYMBOL(find_next_clump8);
194