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 | |
0ade34c3 CC |
25 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ |
26 | !defined(find_next_and_bit) | |
23e1a358 | 27 | |
23e1a358 | 28 | /* |
0ade34c3 CC |
29 | * This is a common helper function for find_next_bit, find_next_zero_bit, and |
30 | * find_next_and_bit. The differences are: | |
31 | * - The "invert" argument, which is XORed with each fetched word before | |
32 | * searching it for one bits. | |
33 | * - The optional "addr2", which is anded with "addr1" if present. | |
23e1a358 | 34 | */ |
0ade34c3 CC |
35 | static inline unsigned long _find_next_bit(const unsigned long *addr1, |
36 | const unsigned long *addr2, unsigned long nbits, | |
37 | unsigned long start, unsigned long invert) | |
23e1a358 | 38 | { |
23e1a358 ACM |
39 | unsigned long tmp; |
40 | ||
e4afd2e5 | 41 | if (unlikely(start >= nbits)) |
64af4e0d ACM |
42 | return nbits; |
43 | ||
0ade34c3 CC |
44 | tmp = addr1[start / BITS_PER_LONG]; |
45 | if (addr2) | |
46 | tmp &= addr2[start / BITS_PER_LONG]; | |
47 | tmp ^= invert; | |
64af4e0d ACM |
48 | |
49 | /* Handle 1st word. */ | |
50 | tmp &= BITMAP_FIRST_WORD_MASK(start); | |
51 | start = round_down(start, BITS_PER_LONG); | |
52 | ||
53 | while (!tmp) { | |
54 | start += BITS_PER_LONG; | |
55 | if (start >= nbits) | |
56 | return nbits; | |
57 | ||
0ade34c3 CC |
58 | tmp = addr1[start / BITS_PER_LONG]; |
59 | if (addr2) | |
60 | tmp &= addr2[start / BITS_PER_LONG]; | |
61 | tmp ^= invert; | |
23e1a358 | 62 | } |
23e1a358 | 63 | |
64af4e0d ACM |
64 | return min(start + __ffs(tmp), nbits); |
65 | } | |
66 | #endif | |
67 | ||
68 | #ifndef find_next_bit | |
69 | /* | |
70 | * Find the next set bit in a memory region. | |
71 | */ | |
72 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, | |
73 | unsigned long offset) | |
74 | { | |
0ade34c3 | 75 | return _find_next_bit(addr, NULL, size, offset, 0UL); |
23e1a358 ACM |
76 | } |
77 | #endif | |
78 | ||
79 | #ifndef find_first_bit | |
80 | /* | |
81 | * Find the first set bit in a memory region. | |
82 | */ | |
83 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) | |
84 | { | |
64af4e0d | 85 | unsigned long idx; |
23e1a358 | 86 | |
64af4e0d ACM |
87 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
88 | if (addr[idx]) | |
89 | return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); | |
23e1a358 | 90 | } |
23e1a358 | 91 | |
64af4e0d | 92 | return size; |
23e1a358 ACM |
93 | } |
94 | #endif | |
02bc11de JO |
95 | |
96 | #ifndef find_first_zero_bit | |
97 | /* | |
98 | * Find the first cleared bit in a memory region. | |
99 | */ | |
100 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) | |
101 | { | |
102 | unsigned long idx; | |
103 | ||
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); | |
107 | } | |
108 | ||
109 | return size; | |
110 | } | |
111 | #endif | |
112 | ||
113 | #ifndef find_next_zero_bit | |
114 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, | |
115 | unsigned long offset) | |
116 | { | |
0ade34c3 CC |
117 | return _find_next_bit(addr, NULL, size, offset, ~0UL); |
118 | } | |
119 | #endif | |
120 | ||
121 | #ifndef find_next_and_bit | |
122 | unsigned long find_next_and_bit(const unsigned long *addr1, | |
123 | const unsigned long *addr2, unsigned long size, | |
124 | unsigned long offset) | |
125 | { | |
126 | return _find_next_bit(addr1, addr2, size, offset, 0UL); | |
02bc11de JO |
127 | } |
128 | #endif |