Commit | Line | Data |
---|---|---|
64af4e0d | 1 | /* bit search implementation |
23e1a358 | 2 | * |
64af4e0d | 3 | * Copied from lib/find_bit.c to tools/lib/find_bit.c |
23e1a358 ACM |
4 | * |
5 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
6 | * Written by David Howells (dhowells@redhat.com) | |
7 | * | |
64af4e0d ACM |
8 | * Copyright (C) 2008 IBM Corporation |
9 | * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> | |
10 | * (Inspired by David Howell's find_next_bit implementation) | |
11 | * | |
12 | * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease | |
13 | * size and improve performance, 2015. | |
14 | * | |
23e1a358 ACM |
15 | * This program is free software; you can redistribute it and/or |
16 | * modify it under the terms of the GNU General Public License | |
17 | * as published by the Free Software Foundation; either version | |
18 | * 2 of the License, or (at your option) any later version. | |
19 | */ | |
20 | ||
21 | #include <linux/bitops.h> | |
64af4e0d ACM |
22 | #include <linux/bitmap.h> |
23 | #include <linux/kernel.h> | |
23e1a358 | 24 | |
64af4e0d | 25 | #if !defined(find_next_bit) |
23e1a358 | 26 | |
23e1a358 | 27 | /* |
64af4e0d ACM |
28 | * This is a common helper function for find_next_bit and |
29 | * find_next_zero_bit. The difference is the "invert" argument, which | |
30 | * is XORed with each fetched word before searching it for one bits. | |
23e1a358 | 31 | */ |
64af4e0d ACM |
32 | static unsigned long _find_next_bit(const unsigned long *addr, |
33 | unsigned long nbits, unsigned long start, unsigned long invert) | |
23e1a358 | 34 | { |
23e1a358 ACM |
35 | unsigned long tmp; |
36 | ||
64af4e0d ACM |
37 | if (!nbits || start >= nbits) |
38 | return nbits; | |
39 | ||
40 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
41 | ||
42 | /* Handle 1st word. */ | |
43 | tmp &= BITMAP_FIRST_WORD_MASK(start); | |
44 | start = round_down(start, BITS_PER_LONG); | |
45 | ||
46 | while (!tmp) { | |
47 | start += BITS_PER_LONG; | |
48 | if (start >= nbits) | |
49 | return nbits; | |
50 | ||
51 | tmp = addr[start / BITS_PER_LONG] ^ invert; | |
23e1a358 | 52 | } |
23e1a358 | 53 | |
64af4e0d ACM |
54 | return min(start + __ffs(tmp), nbits); |
55 | } | |
56 | #endif | |
57 | ||
58 | #ifndef find_next_bit | |
59 | /* | |
60 | * Find the next set bit in a memory region. | |
61 | */ | |
62 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, | |
63 | unsigned long offset) | |
64 | { | |
65 | return _find_next_bit(addr, size, offset, 0UL); | |
23e1a358 ACM |
66 | } |
67 | #endif | |
68 | ||
69 | #ifndef find_first_bit | |
70 | /* | |
71 | * Find the first set bit in a memory region. | |
72 | */ | |
73 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) | |
74 | { | |
64af4e0d | 75 | unsigned long idx; |
23e1a358 | 76 | |
64af4e0d ACM |
77 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
78 | if (addr[idx]) | |
79 | return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); | |
23e1a358 | 80 | } |
23e1a358 | 81 | |
64af4e0d | 82 | return size; |
23e1a358 ACM |
83 | } |
84 | #endif |