Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* find_next_bit.c: fallback find next bit implementation |
2 | * | |
3 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
4 | * Written by David Howells (dhowells@redhat.com) | |
5 | * | |
2c57a0e2 YN |
6 | * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease |
7 | * size and improve performance, 2015. | |
8 | * | |
1da177e4 LT |
9 | * This program is free software; you can redistribute it and/or |
10 | * modify it under the terms of the GNU General Public License | |
11 | * as published by the Free Software Foundation; either version | |
12 | * 2 of the License, or (at your option) any later version. | |
13 | */ | |
14 | ||
15 | #include <linux/bitops.h> | |
8bc3bcc9 | 16 | #include <linux/export.h> |
2c57a0e2 | 17 | #include <linux/kernel.h> |
1da177e4 | 18 | |
2c57a0e2 | 19 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) |
c7f612cd | 20 | |
64970b68 | 21 | /* |
2c57a0e2 YN |
22 | * This is a common helper function for find_next_bit and |
23 | * find_next_zero_bit. The difference is the "invert" argument, which | |
24 | * is XORed with each fetched word before searching it for one bits. | |
c7f612cd | 25 | */ |
2c57a0e2 YN |
26 | static unsigned long _find_next_bit(const unsigned long *addr, |
27 | unsigned long nbits, unsigned long start, unsigned long invert) | |
1da177e4 | 28 | { |
1da177e4 LT |
29 | unsigned long tmp; |
30 | ||
2c57a0e2 YN |
31 | if (!nbits || start >= nbits) |
32 | return nbits; | |
33 | ||
34 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
35 | ||
36 | /* Handle 1st word. */ | |
37 | tmp &= BITMAP_FIRST_WORD_MASK(start); | |
38 | start = round_down(start, BITS_PER_LONG); | |
39 | ||
40 | while (!tmp) { | |
41 | start += BITS_PER_LONG; | |
42 | if (start >= nbits) | |
43 | return nbits; | |
44 | ||
45 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
1da177e4 LT |
46 | } |
47 | ||
2c57a0e2 | 48 | return min(start + __ffs(tmp), nbits); |
c7f612cd | 49 | } |
19de85ef | 50 | #endif |
1da177e4 | 51 | |
2c57a0e2 | 52 | #ifndef find_next_bit |
c7f612cd | 53 | /* |
2c57a0e2 | 54 | * Find the next set bit in a memory region. |
c7f612cd | 55 | */ |
2c57a0e2 YN |
56 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
57 | unsigned long offset) | |
58 | { | |
59 | return _find_next_bit(addr, size, offset, 0UL); | |
60 | } | |
61 | EXPORT_SYMBOL(find_next_bit); | |
62 | #endif | |
63 | ||
64 | #ifndef find_next_zero_bit | |
fee4b19f TG |
65 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
66 | unsigned long offset) | |
c7f612cd | 67 | { |
2c57a0e2 | 68 | return _find_next_bit(addr, size, offset, ~0UL); |
1da177e4 | 69 | } |
fee4b19f | 70 | EXPORT_SYMBOL(find_next_zero_bit); |
19de85ef | 71 | #endif |
77b9bd9c | 72 | |
19de85ef | 73 | #ifndef find_first_bit |
77b9bd9c AH |
74 | /* |
75 | * Find the first set bit in a memory region. | |
76 | */ | |
fee4b19f | 77 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 78 | { |
2c57a0e2 | 79 | unsigned long idx; |
77b9bd9c | 80 | |
2c57a0e2 YN |
81 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
82 | if (addr[idx]) | |
83 | return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); | |
77b9bd9c | 84 | } |
77b9bd9c | 85 | |
2c57a0e2 | 86 | return size; |
77b9bd9c | 87 | } |
fee4b19f | 88 | EXPORT_SYMBOL(find_first_bit); |
19de85ef | 89 | #endif |
77b9bd9c | 90 | |
19de85ef | 91 | #ifndef find_first_zero_bit |
77b9bd9c AH |
92 | /* |
93 | * Find the first cleared bit in a memory region. | |
94 | */ | |
fee4b19f | 95 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 96 | { |
2c57a0e2 | 97 | unsigned long idx; |
77b9bd9c | 98 | |
2c57a0e2 YN |
99 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
100 | if (addr[idx] != ~0UL) | |
101 | return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); | |
77b9bd9c | 102 | } |
77b9bd9c | 103 | |
2c57a0e2 | 104 | return size; |
77b9bd9c | 105 | } |
fee4b19f | 106 | EXPORT_SYMBOL(find_first_zero_bit); |
19de85ef | 107 | #endif |
930ae745 AM |
108 | |
109 | #ifdef __BIG_ENDIAN | |
110 | ||
111 | /* include/linux/byteorder does not support "unsigned long" type */ | |
930ae745 AM |
112 | static inline unsigned long ext2_swab(const unsigned long y) |
113 | { | |
114 | #if BITS_PER_LONG == 64 | |
115 | return (unsigned long) __swab64((u64) y); | |
116 | #elif BITS_PER_LONG == 32 | |
117 | return (unsigned long) __swab32((u32) y); | |
118 | #else | |
119 | #error BITS_PER_LONG not defined | |
120 | #endif | |
121 | } | |
122 | ||
2c57a0e2 YN |
123 | #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) |
124 | static unsigned long _find_next_bit_le(const unsigned long *addr, | |
125 | unsigned long nbits, unsigned long start, unsigned long invert) | |
930ae745 | 126 | { |
930ae745 AM |
127 | unsigned long tmp; |
128 | ||
2c57a0e2 YN |
129 | if (!nbits || start >= nbits) |
130 | return nbits; | |
131 | ||
132 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
133 | ||
134 | /* Handle 1st word. */ | |
135 | tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start)); | |
136 | start = round_down(start, BITS_PER_LONG); | |
930ae745 | 137 | |
2c57a0e2 YN |
138 | while (!tmp) { |
139 | start += BITS_PER_LONG; | |
140 | if (start >= nbits) | |
141 | return nbits; | |
142 | ||
143 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
930ae745 | 144 | } |
930ae745 | 145 | |
2c57a0e2 YN |
146 | return min(start + __ffs(ext2_swab(tmp)), nbits); |
147 | } | |
148 | #endif | |
149 | ||
150 | #ifndef find_next_zero_bit_le | |
151 | unsigned long find_next_zero_bit_le(const void *addr, unsigned | |
152 | long size, unsigned long offset) | |
153 | { | |
154 | return _find_next_bit_le(addr, size, offset, ~0UL); | |
930ae745 | 155 | } |
c4945b9e | 156 | EXPORT_SYMBOL(find_next_zero_bit_le); |
19de85ef | 157 | #endif |
930ae745 | 158 | |
19de85ef | 159 | #ifndef find_next_bit_le |
a56560b3 | 160 | unsigned long find_next_bit_le(const void *addr, unsigned |
aa02ad67 AK |
161 | long size, unsigned long offset) |
162 | { | |
2c57a0e2 | 163 | return _find_next_bit_le(addr, size, offset, 0UL); |
aa02ad67 | 164 | } |
c4945b9e | 165 | EXPORT_SYMBOL(find_next_bit_le); |
19de85ef | 166 | #endif |
0664996b | 167 | |
930ae745 | 168 | #endif /* __BIG_ENDIAN */ |