Merge tag '5.7-rc-smb3-fixes-part1' of git://git.samba.org/sfrench/cifs-2.6
[sfrench/cifs-2.6.git] / tools / lib / find_bit.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* bit search implementation
3  *
4  * Copied from lib/find_bit.c to tools/lib/find_bit.c
5  *
6  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
7  * Written by David Howells (dhowells@redhat.com)
8  *
9  * Copyright (C) 2008 IBM Corporation
10  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
11  * (Inspired by David Howell's find_next_bit implementation)
12  *
13  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
14  * size and improve performance, 2015.
15  */
16
17 #include <linux/bitops.h>
18 #include <linux/bitmap.h>
19 #include <linux/kernel.h>
20
21 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
22                 !defined(find_next_and_bit)
23
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  */
31 static inline unsigned long _find_next_bit(const unsigned long *addr1,
32                 const unsigned long *addr2, unsigned long nbits,
33                 unsigned long start, unsigned long invert)
34 {
35         unsigned long tmp;
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         tmp &= BITMAP_FIRST_WORD_MASK(start);
47         start = round_down(start, BITS_PER_LONG);
48
49         while (!tmp) {
50                 start += BITS_PER_LONG;
51                 if (start >= nbits)
52                         return nbits;
53
54                 tmp = addr1[start / BITS_PER_LONG];
55                 if (addr2)
56                         tmp &= addr2[start / BITS_PER_LONG];
57                 tmp ^= invert;
58         }
59
60         return min(start + __ffs(tmp), nbits);
61 }
62 #endif
63
64 #ifndef find_next_bit
65 /*
66  * Find the next set bit in a memory region.
67  */
68 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
69                             unsigned long offset)
70 {
71         return _find_next_bit(addr, NULL, size, offset, 0UL);
72 }
73 #endif
74
75 #ifndef find_first_bit
76 /*
77  * Find the first set bit in a memory region.
78  */
79 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
80 {
81         unsigned long idx;
82
83         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
84                 if (addr[idx])
85                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
86         }
87
88         return size;
89 }
90 #endif
91
92 #ifndef find_first_zero_bit
93 /*
94  * Find the first cleared bit in a memory region.
95  */
96 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
97 {
98         unsigned long idx;
99
100         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
101                 if (addr[idx] != ~0UL)
102                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
103         }
104
105         return size;
106 }
107 #endif
108
109 #ifndef find_next_zero_bit
110 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
111                                  unsigned long offset)
112 {
113         return _find_next_bit(addr, NULL, size, offset, ~0UL);
114 }
115 #endif
116
117 #ifndef find_next_and_bit
118 unsigned long find_next_and_bit(const unsigned long *addr1,
119                 const unsigned long *addr2, unsigned long size,
120                 unsigned long offset)
121 {
122         return _find_next_bit(addr1, addr2, size, offset, 0UL);
123 }
124 #endif