]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - lib/find_bit.c
1 /* bit search implementation
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
6 * Copyright (C) 2008 IBM Corporation
7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
8 * (Inspired by David Howell's find_next_bit implementation)
10 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
11 * size and improve performance, 2015.
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation; either version
16 * 2 of the License, or (at your option) any later version.
19 #include <linux/bitops.h>
20 #include <linux/bitmap.h>
21 #include <linux/export.h>
22 #include <linux/kernel.h>
24 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
27 * This is a common helper function for find_next_bit and
28 * find_next_zero_bit. The difference is the "invert" argument, which
29 * is XORed with each fetched word before searching it for one bits.
31 static unsigned long _find_next_bit(const unsigned long *addr
,
32 unsigned long nbits
, unsigned long start
, unsigned long invert
)
36 if (unlikely(start
>= nbits
))
39 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
41 /* Handle 1st word. */
42 tmp
&= BITMAP_FIRST_WORD_MASK(start
);
43 start
= round_down(start
, BITS_PER_LONG
);
46 start
+= BITS_PER_LONG
;
50 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
53 return min(start
+ __ffs(tmp
), nbits
);
59 * Find the next set bit in a memory region.
61 unsigned long find_next_bit(const unsigned long *addr
, unsigned long size
,
64 return _find_next_bit(addr
, size
, offset
, 0UL);
66 EXPORT_SYMBOL(find_next_bit
);
69 #ifndef find_next_zero_bit
70 unsigned long find_next_zero_bit(const unsigned long *addr
, unsigned long size
,
73 return _find_next_bit(addr
, size
, offset
, ~0UL);
75 EXPORT_SYMBOL(find_next_zero_bit
);
78 #ifndef find_first_bit
80 * Find the first set bit in a memory region.
82 unsigned long find_first_bit(const unsigned long *addr
, unsigned long size
)
86 for (idx
= 0; idx
* BITS_PER_LONG
< size
; idx
++) {
88 return min(idx
* BITS_PER_LONG
+ __ffs(addr
[idx
]), size
);
93 EXPORT_SYMBOL(find_first_bit
);
96 #ifndef find_first_zero_bit
98 * Find the first cleared bit in a memory region.
100 unsigned long find_first_zero_bit(const unsigned long *addr
, unsigned long size
)
104 for (idx
= 0; idx
* BITS_PER_LONG
< size
; idx
++) {
105 if (addr
[idx
] != ~0UL)
106 return min(idx
* BITS_PER_LONG
+ ffz(addr
[idx
]), size
);
111 EXPORT_SYMBOL(find_first_zero_bit
);
114 #ifndef find_last_bit
115 unsigned long find_last_bit(const unsigned long *addr
, unsigned long size
)
118 unsigned long val
= BITMAP_LAST_WORD_MASK(size
);
119 unsigned long idx
= (size
-1) / BITS_PER_LONG
;
124 return idx
* BITS_PER_LONG
+ __fls(val
);
131 EXPORT_SYMBOL(find_last_bit
);
136 /* include/linux/byteorder does not support "unsigned long" type */
137 static inline unsigned long ext2_swab(const unsigned long y
)
139 #if BITS_PER_LONG == 64
140 return (unsigned long) __swab64((u64
) y
);
141 #elif BITS_PER_LONG == 32
142 return (unsigned long) __swab32((u32
) y
);
144 #error BITS_PER_LONG not defined
148 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
149 static unsigned long _find_next_bit_le(const unsigned long *addr
,
150 unsigned long nbits
, unsigned long start
, unsigned long invert
)
154 if (unlikely(start
>= nbits
))
157 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
159 /* Handle 1st word. */
160 tmp
&= ext2_swab(BITMAP_FIRST_WORD_MASK(start
));
161 start
= round_down(start
, BITS_PER_LONG
);
164 start
+= BITS_PER_LONG
;
168 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
171 return min(start
+ __ffs(ext2_swab(tmp
)), nbits
);
175 #ifndef find_next_zero_bit_le
176 unsigned long find_next_zero_bit_le(const void *addr
, unsigned
177 long size
, unsigned long offset
)
179 return _find_next_bit_le(addr
, size
, offset
, ~0UL);
181 EXPORT_SYMBOL(find_next_zero_bit_le
);
184 #ifndef find_next_bit_le
185 unsigned long find_next_bit_le(const void *addr
, unsigned
186 long size
, unsigned long offset
)
188 return _find_next_bit_le(addr
, size
, offset
, 0UL);
190 EXPORT_SYMBOL(find_next_bit_le
);
193 #endif /* __BIG_ENDIAN */