1*4882a593Smuzhiyun // SPDX-License-Identifier: GPL-2.0-or-later
2*4882a593Smuzhiyun /* bit search implementation
3*4882a593Smuzhiyun *
4*4882a593Smuzhiyun * Copied from lib/find_bit.c to tools/lib/find_bit.c
5*4882a593Smuzhiyun *
6*4882a593Smuzhiyun * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
7*4882a593Smuzhiyun * Written by David Howells (dhowells@redhat.com)
8*4882a593Smuzhiyun *
9*4882a593Smuzhiyun * Copyright (C) 2008 IBM Corporation
10*4882a593Smuzhiyun * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
11*4882a593Smuzhiyun * (Inspired by David Howell's find_next_bit implementation)
12*4882a593Smuzhiyun *
13*4882a593Smuzhiyun * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
14*4882a593Smuzhiyun * size and improve performance, 2015.
15*4882a593Smuzhiyun */
16*4882a593Smuzhiyun
17*4882a593Smuzhiyun #include <linux/bitops.h>
18*4882a593Smuzhiyun #include <linux/bitmap.h>
19*4882a593Smuzhiyun #include <linux/kernel.h>
20*4882a593Smuzhiyun
21*4882a593Smuzhiyun #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
22*4882a593Smuzhiyun !defined(find_next_and_bit)
23*4882a593Smuzhiyun
24*4882a593Smuzhiyun /*
25*4882a593Smuzhiyun * This is a common helper function for find_next_bit, find_next_zero_bit, and
26*4882a593Smuzhiyun * find_next_and_bit. The differences are:
27*4882a593Smuzhiyun * - The "invert" argument, which is XORed with each fetched word before
28*4882a593Smuzhiyun * searching it for one bits.
29*4882a593Smuzhiyun * - The optional "addr2", which is anded with "addr1" if present.
30*4882a593Smuzhiyun */
_find_next_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start,unsigned long invert)31*4882a593Smuzhiyun static inline unsigned long _find_next_bit(const unsigned long *addr1,
32*4882a593Smuzhiyun const unsigned long *addr2, unsigned long nbits,
33*4882a593Smuzhiyun unsigned long start, unsigned long invert)
34*4882a593Smuzhiyun {
35*4882a593Smuzhiyun unsigned long tmp;
36*4882a593Smuzhiyun
37*4882a593Smuzhiyun if (unlikely(start >= nbits))
38*4882a593Smuzhiyun return nbits;
39*4882a593Smuzhiyun
40*4882a593Smuzhiyun tmp = addr1[start / BITS_PER_LONG];
41*4882a593Smuzhiyun if (addr2)
42*4882a593Smuzhiyun tmp &= addr2[start / BITS_PER_LONG];
43*4882a593Smuzhiyun tmp ^= invert;
44*4882a593Smuzhiyun
45*4882a593Smuzhiyun /* Handle 1st word. */
46*4882a593Smuzhiyun tmp &= BITMAP_FIRST_WORD_MASK(start);
47*4882a593Smuzhiyun start = round_down(start, BITS_PER_LONG);
48*4882a593Smuzhiyun
49*4882a593Smuzhiyun while (!tmp) {
50*4882a593Smuzhiyun start += BITS_PER_LONG;
51*4882a593Smuzhiyun if (start >= nbits)
52*4882a593Smuzhiyun return nbits;
53*4882a593Smuzhiyun
54*4882a593Smuzhiyun tmp = addr1[start / BITS_PER_LONG];
55*4882a593Smuzhiyun if (addr2)
56*4882a593Smuzhiyun tmp &= addr2[start / BITS_PER_LONG];
57*4882a593Smuzhiyun tmp ^= invert;
58*4882a593Smuzhiyun }
59*4882a593Smuzhiyun
60*4882a593Smuzhiyun return min(start + __ffs(tmp), nbits);
61*4882a593Smuzhiyun }
62*4882a593Smuzhiyun #endif
63*4882a593Smuzhiyun
64*4882a593Smuzhiyun #ifndef find_next_bit
65*4882a593Smuzhiyun /*
66*4882a593Smuzhiyun * Find the next set bit in a memory region.
67*4882a593Smuzhiyun */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)68*4882a593Smuzhiyun unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
69*4882a593Smuzhiyun unsigned long offset)
70*4882a593Smuzhiyun {
71*4882a593Smuzhiyun return _find_next_bit(addr, NULL, size, offset, 0UL);
72*4882a593Smuzhiyun }
73*4882a593Smuzhiyun #endif
74*4882a593Smuzhiyun
75*4882a593Smuzhiyun #ifndef find_first_bit
76*4882a593Smuzhiyun /*
77*4882a593Smuzhiyun * Find the first set bit in a memory region.
78*4882a593Smuzhiyun */
find_first_bit(const unsigned long * addr,unsigned long size)79*4882a593Smuzhiyun unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
80*4882a593Smuzhiyun {
81*4882a593Smuzhiyun unsigned long idx;
82*4882a593Smuzhiyun
83*4882a593Smuzhiyun for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
84*4882a593Smuzhiyun if (addr[idx])
85*4882a593Smuzhiyun return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
86*4882a593Smuzhiyun }
87*4882a593Smuzhiyun
88*4882a593Smuzhiyun return size;
89*4882a593Smuzhiyun }
90*4882a593Smuzhiyun #endif
91*4882a593Smuzhiyun
92*4882a593Smuzhiyun #ifndef find_first_zero_bit
93*4882a593Smuzhiyun /*
94*4882a593Smuzhiyun * Find the first cleared bit in a memory region.
95*4882a593Smuzhiyun */
find_first_zero_bit(const unsigned long * addr,unsigned long size)96*4882a593Smuzhiyun unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
97*4882a593Smuzhiyun {
98*4882a593Smuzhiyun unsigned long idx;
99*4882a593Smuzhiyun
100*4882a593Smuzhiyun for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
101*4882a593Smuzhiyun if (addr[idx] != ~0UL)
102*4882a593Smuzhiyun return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
103*4882a593Smuzhiyun }
104*4882a593Smuzhiyun
105*4882a593Smuzhiyun return size;
106*4882a593Smuzhiyun }
107*4882a593Smuzhiyun #endif
108*4882a593Smuzhiyun
109*4882a593Smuzhiyun #ifndef find_next_zero_bit
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)110*4882a593Smuzhiyun unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
111*4882a593Smuzhiyun unsigned long offset)
112*4882a593Smuzhiyun {
113*4882a593Smuzhiyun return _find_next_bit(addr, NULL, size, offset, ~0UL);
114*4882a593Smuzhiyun }
115*4882a593Smuzhiyun #endif
116*4882a593Smuzhiyun
117*4882a593Smuzhiyun #ifndef find_next_and_bit
find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long offset)118*4882a593Smuzhiyun unsigned long find_next_and_bit(const unsigned long *addr1,
119*4882a593Smuzhiyun const unsigned long *addr2, unsigned long size,
120*4882a593Smuzhiyun unsigned long offset)
121*4882a593Smuzhiyun {
122*4882a593Smuzhiyun return _find_next_bit(addr1, addr2, size, offset, 0UL);
123*4882a593Smuzhiyun }
124*4882a593Smuzhiyun #endif
125