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