Merge branch 'for-5.17-fixes' of git://git.kernel.org/pub/scm/linux/kernel/git/tj...
[platform/kernel/linux-starfive.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 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         (void) le;
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
49         /*
50          * Due to the lack of swab() in tools, and the fact that it doesn't
51          * need little-endian support, just comment it out
52          */
53 #if (0)
54         if (le)
55                 mask = swab(mask);
56 #endif
57
58         tmp &= mask;
59
60         start = round_down(start, BITS_PER_LONG);
61
62         while (!tmp) {
63                 start += BITS_PER_LONG;
64                 if (start >= nbits)
65                         return nbits;
66
67                 tmp = addr1[start / BITS_PER_LONG];
68                 if (addr2)
69                         tmp &= addr2[start / BITS_PER_LONG];
70                 tmp ^= invert;
71         }
72
73 #if (0)
74         if (le)
75                 tmp = swab(tmp);
76 #endif
77
78         return min(start + __ffs(tmp), nbits);
79 }
80 #endif
81
82 #ifndef find_first_bit
83 /*
84  * Find the first set bit in a memory region.
85  */
86 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
87 {
88         unsigned long idx;
89
90         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
91                 if (addr[idx])
92                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
93         }
94
95         return size;
96 }
97 #endif
98
99 #ifndef find_first_and_bit
100 /*
101  * Find the first set bit in two memory regions.
102  */
103 unsigned long _find_first_and_bit(const unsigned long *addr1,
104                                   const unsigned long *addr2,
105                                   unsigned long size)
106 {
107         unsigned long idx, val;
108
109         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
110                 val = addr1[idx] & addr2[idx];
111                 if (val)
112                         return min(idx * BITS_PER_LONG + __ffs(val), size);
113         }
114
115         return size;
116 }
117 #endif
118
119 #ifndef find_first_zero_bit
120 /*
121  * Find the first cleared bit in a memory region.
122  */
123 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
124 {
125         unsigned long idx;
126
127         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
128                 if (addr[idx] != ~0UL)
129                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
130         }
131
132         return size;
133 }
134 #endif