]>
Commit | Line | Data |
---|---|---|
2874c5fd | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
64af4e0d | 2 | /* bit search implementation |
23e1a358 | 3 | * |
64af4e0d | 4 | * Copied from lib/find_bit.c to tools/lib/find_bit.c |
23e1a358 ACM |
5 | * |
6 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
7 | * Written by David Howells (dhowells@redhat.com) | |
8 | * | |
64af4e0d ACM |
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. | |
23e1a358 ACM |
15 | */ |
16 | ||
17 | #include <linux/bitops.h> | |
64af4e0d ACM |
18 | #include <linux/bitmap.h> |
19 | #include <linux/kernel.h> | |
23e1a358 | 20 | |
0ade34c3 CC |
21 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ |
22 | !defined(find_next_and_bit) | |
23e1a358 | 23 | |
23e1a358 | 24 | /* |
0ade34c3 CC |
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. | |
23e1a358 | 30 | */ |
0ade34c3 CC |
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) | |
23e1a358 | 34 | { |
23e1a358 ACM |
35 | unsigned long tmp; |
36 | ||
e4afd2e5 | 37 | if (unlikely(start >= nbits)) |
64af4e0d ACM |
38 | return nbits; |
39 | ||
0ade34c3 CC |
40 | tmp = addr1[start / BITS_PER_LONG]; |
41 | if (addr2) | |
42 | tmp &= addr2[start / BITS_PER_LONG]; | |
43 | tmp ^= invert; | |
64af4e0d ACM |
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 | ||
0ade34c3 CC |
54 | tmp = addr1[start / BITS_PER_LONG]; |
55 | if (addr2) | |
56 | tmp &= addr2[start / BITS_PER_LONG]; | |
57 | tmp ^= invert; | |
23e1a358 | 58 | } |
23e1a358 | 59 | |
64af4e0d ACM |
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 | { | |
0ade34c3 | 71 | return _find_next_bit(addr, NULL, size, offset, 0UL); |
23e1a358 ACM |
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 | { | |
64af4e0d | 81 | unsigned long idx; |
23e1a358 | 82 | |
64af4e0d ACM |
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); | |
23e1a358 | 86 | } |
23e1a358 | 87 | |
64af4e0d | 88 | return size; |
23e1a358 ACM |
89 | } |
90 | #endif | |
02bc11de JO |
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 | { | |
0ade34c3 CC |
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); | |
02bc11de JO |
123 | } |
124 | #endif |