Merge tag 'regulator-fix-v5.17-rc5' of git://git.kernel.org/pub/scm/linux/kernel...
[linux-2.6-microblaze.git] / lib / find_bit.c
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/math.h>
19 #include <linux/minmax.h>
20 #include <linux/swab.h>
21
22 #if !defined(find_next_bit) || !defined(find_next_zero_bit) ||                  \
23         !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) ||        \
24         !defined(find_next_and_bit)
25 /*
26  * This is a common helper function for find_next_bit, find_next_zero_bit, and
27  * find_next_and_bit. The differences are:
28  *  - The "invert" argument, which is XORed with each fetched word before
29  *    searching it for one bits.
30  *  - The optional "addr2", which is anded with "addr1" if present.
31  */
32 unsigned long _find_next_bit(const unsigned long *addr1,
33                 const unsigned long *addr2, unsigned long nbits,
34                 unsigned long start, unsigned long invert, unsigned long le)
35 {
36         unsigned long tmp, mask;
37
38         if (unlikely(start >= nbits))
39                 return nbits;
40
41         tmp = addr1[start / BITS_PER_LONG];
42         if (addr2)
43                 tmp &= addr2[start / BITS_PER_LONG];
44         tmp ^= invert;
45
46         /* Handle 1st word. */
47         mask = BITMAP_FIRST_WORD_MASK(start);
48         if (le)
49                 mask = swab(mask);
50
51         tmp &= mask;
52
53         start = round_down(start, BITS_PER_LONG);
54
55         while (!tmp) {
56                 start += BITS_PER_LONG;
57                 if (start >= nbits)
58                         return nbits;
59
60                 tmp = addr1[start / BITS_PER_LONG];
61                 if (addr2)
62                         tmp &= addr2[start / BITS_PER_LONG];
63                 tmp ^= invert;
64         }
65
66         if (le)
67                 tmp = swab(tmp);
68
69         return min(start + __ffs(tmp), nbits);
70 }
71 EXPORT_SYMBOL(_find_next_bit);
72 #endif
73
74 #ifndef find_first_bit
75 /*
76  * Find the first set bit in a memory region.
77  */
78 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
79 {
80         unsigned long idx;
81
82         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
83                 if (addr[idx])
84                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
85         }
86
87         return size;
88 }
89 EXPORT_SYMBOL(_find_first_bit);
90 #endif
91
92 #ifndef find_first_and_bit
93 /*
94  * Find the first set bit in two memory regions.
95  */
96 unsigned long _find_first_and_bit(const unsigned long *addr1,
97                                   const unsigned long *addr2,
98                                   unsigned long size)
99 {
100         unsigned long idx, val;
101
102         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
103                 val = addr1[idx] & addr2[idx];
104                 if (val)
105                         return min(idx * BITS_PER_LONG + __ffs(val), size);
106         }
107
108         return size;
109 }
110 EXPORT_SYMBOL(_find_first_and_bit);
111 #endif
112
113 #ifndef find_first_zero_bit
114 /*
115  * Find the first cleared bit in a memory region.
116  */
117 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
118 {
119         unsigned long idx;
120
121         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
122                 if (addr[idx] != ~0UL)
123                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
124         }
125
126         return size;
127 }
128 EXPORT_SYMBOL(_find_first_zero_bit);
129 #endif
130
131 #ifndef find_last_bit
132 unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
133 {
134         if (size) {
135                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
136                 unsigned long idx = (size-1) / BITS_PER_LONG;
137
138                 do {
139                         val &= addr[idx];
140                         if (val)
141                                 return idx * BITS_PER_LONG + __fls(val);
142
143                         val = ~0ul;
144                 } while (idx--);
145         }
146         return size;
147 }
148 EXPORT_SYMBOL(_find_last_bit);
149 #endif
150
151 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
152                                unsigned long size, unsigned long offset)
153 {
154         offset = find_next_bit(addr, size, offset);
155         if (offset == size)
156                 return size;
157
158         offset = round_down(offset, 8);
159         *clump = bitmap_get_value8(addr, offset);
160
161         return offset;
162 }
163 EXPORT_SYMBOL(find_next_clump8);