1 /*
2 * Copyright (c) 2000-2004 Silicon Graphics, Inc. All Rights Reserved.
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
11 *
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
22 *
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
25 *
26 * http://www.sgi.com
27 *
28 * For further information regarding this notice, see:
29 *
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
31 */
32
33 /*
34 * XFS bit manipulation routines, used in non-realtime code.
35 */
36
37 #include "xfs.h"
38 #include "xfs_bit.h"
39 #include "xfs_log.h"
40 #include "xfs_trans.h"
41 #include "xfs_buf_item.h"
42
43
44 #ifndef HAVE_ARCH_HIGHBIT
45 /*
46 * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
47 */
48 const char xfs_highbit[256] = {
49 -1, 0, 1, 1, 2, 2, 2, 2, /* 00 .. 07 */
50 3, 3, 3, 3, 3, 3, 3, 3, /* 08 .. 0f */
51 4, 4, 4, 4, 4, 4, 4, 4, /* 10 .. 17 */
52 4, 4, 4, 4, 4, 4, 4, 4, /* 18 .. 1f */
53 5, 5, 5, 5, 5, 5, 5, 5, /* 20 .. 27 */
54 5, 5, 5, 5, 5, 5, 5, 5, /* 28 .. 2f */
55 5, 5, 5, 5, 5, 5, 5, 5, /* 30 .. 37 */
56 5, 5, 5, 5, 5, 5, 5, 5, /* 38 .. 3f */
57 6, 6, 6, 6, 6, 6, 6, 6, /* 40 .. 47 */
58 6, 6, 6, 6, 6, 6, 6, 6, /* 48 .. 4f */
59 6, 6, 6, 6, 6, 6, 6, 6, /* 50 .. 57 */
60 6, 6, 6, 6, 6, 6, 6, 6, /* 58 .. 5f */
61 6, 6, 6, 6, 6, 6, 6, 6, /* 60 .. 67 */
62 6, 6, 6, 6, 6, 6, 6, 6, /* 68 .. 6f */
63 6, 6, 6, 6, 6, 6, 6, 6, /* 70 .. 77 */
64 6, 6, 6, 6, 6, 6, 6, 6, /* 78 .. 7f */
65 7, 7, 7, 7, 7, 7, 7, 7, /* 80 .. 87 */
66 7, 7, 7, 7, 7, 7, 7, 7, /* 88 .. 8f */
67 7, 7, 7, 7, 7, 7, 7, 7, /* 90 .. 97 */
68 7, 7, 7, 7, 7, 7, 7, 7, /* 98 .. 9f */
69 7, 7, 7, 7, 7, 7, 7, 7, /* a0 .. a7 */
70 7, 7, 7, 7, 7, 7, 7, 7, /* a8 .. af */
71 7, 7, 7, 7, 7, 7, 7, 7, /* b0 .. b7 */
72 7, 7, 7, 7, 7, 7, 7, 7, /* b8 .. bf */
73 7, 7, 7, 7, 7, 7, 7, 7, /* c0 .. c7 */
74 7, 7, 7, 7, 7, 7, 7, 7, /* c8 .. cf */
75 7, 7, 7, 7, 7, 7, 7, 7, /* d0 .. d7 */
76 7, 7, 7, 7, 7, 7, 7, 7, /* d8 .. df */
77 7, 7, 7, 7, 7, 7, 7, 7, /* e0 .. e7 */
78 7, 7, 7, 7, 7, 7, 7, 7, /* e8 .. ef */
79 7, 7, 7, 7, 7, 7, 7, 7, /* f0 .. f7 */
80 7, 7, 7, 7, 7, 7, 7, 7, /* f8 .. ff */
81 };
82 #endif
83
84 /*
85 * Count of bits set in byte, 0..8.
86 */
87 static const char xfs_countbit[256] = {
88 0, 1, 1, 2, 1, 2, 2, 3, /* 00 .. 07 */
89 1, 2, 2, 3, 2, 3, 3, 4, /* 08 .. 0f */
90 1, 2, 2, 3, 2, 3, 3, 4, /* 10 .. 17 */
91 2, 3, 3, 4, 3, 4, 4, 5, /* 18 .. 1f */
92 1, 2, 2, 3, 2, 3, 3, 4, /* 20 .. 27 */
93 2, 3, 3, 4, 3, 4, 4, 5, /* 28 .. 2f */
94 2, 3, 3, 4, 3, 4, 4, 5, /* 30 .. 37 */
95 3, 4, 4, 5, 4, 5, 5, 6, /* 38 .. 3f */
96 1, 2, 2, 3, 2, 3, 3, 4, /* 40 .. 47 */
97 2, 3, 3, 4, 3, 4, 4, 5, /* 48 .. 4f */
98 2, 3, 3, 4, 3, 4, 4, 5, /* 50 .. 57 */
99 3, 4, 4, 5, 4, 5, 5, 6, /* 58 .. 5f */
100 2, 3, 3, 4, 3, 4, 4, 5, /* 60 .. 67 */
101 3, 4, 4, 5, 4, 5, 5, 6, /* 68 .. 6f */
102 3, 4, 4, 5, 4, 5, 5, 6, /* 70 .. 77 */
103 4, 5, 5, 6, 5, 6, 6, 7, /* 78 .. 7f */
104 1, 2, 2, 3, 2, 3, 3, 4, /* 80 .. 87 */
105 2, 3, 3, 4, 3, 4, 4, 5, /* 88 .. 8f */
106 2, 3, 3, 4, 3, 4, 4, 5, /* 90 .. 97 */
107 3, 4, 4, 5, 4, 5, 5, 6, /* 98 .. 9f */
108 2, 3, 3, 4, 3, 4, 4, 5, /* a0 .. a7 */
109 3, 4, 4, 5, 4, 5, 5, 6, /* a8 .. af */
110 3, 4, 4, 5, 4, 5, 5, 6, /* b0 .. b7 */
111 4, 5, 5, 6, 5, 6, 6, 7, /* b8 .. bf */
112 2, 3, 3, 4, 3, 4, 4, 5, /* c0 .. c7 */
113 3, 4, 4, 5, 4, 5, 5, 6, /* c8 .. cf */
114 3, 4, 4, 5, 4, 5, 5, 6, /* d0 .. d7 */
115 4, 5, 5, 6, 5, 6, 6, 7, /* d8 .. df */
116 3, 4, 4, 5, 4, 5, 5, 6, /* e0 .. e7 */
117 4, 5, 5, 6, 5, 6, 6, 7, /* e8 .. ef */
118 4, 5, 5, 6, 5, 6, 6, 7, /* f0 .. f7 */
119 5, 6, 6, 7, 6, 7, 7, 8, /* f8 .. ff */
120 };
121
122 /*
123 * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
124 */
125 inline int
xfs_highbit32(__uint32_t v)126 xfs_highbit32(
127 __uint32_t v)
128 {
129 #ifdef HAVE_ARCH_HIGHBIT
130 return highbit32(v);
131 #else
132 int i;
133
134 if (v & 0xffff0000)
135 if (v & 0xff000000)
136 i = 24;
137 else
138 i = 16;
139 else if (v & 0x0000ffff)
140 if (v & 0x0000ff00)
141 i = 8;
142 else
143 i = 0;
144 else
145 return -1;
146 return i + xfs_highbit[(v >> i) & 0xff];
147 #endif
148 }
149
150 /*
151 * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
152 */
153 int
xfs_lowbit64(__uint64_t v)154 xfs_lowbit64(
155 __uint64_t v)
156 {
157 __uint32_t w = (__uint32_t)v;
158 int n = 0;
159
160 if (w) { /* lower bits */
161 n = ffs(w);
162 } else { /* upper bits */
163 w = (__uint32_t)(v >> 32);
164 if (w && (n = ffs(w)))
165 n += 32;
166 }
167 return n - 1;
168 }
169
170 /*
171 * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
172 */
173 int
xfs_highbit64(__uint64_t v)174 xfs_highbit64(
175 __uint64_t v)
176 {
177 __uint32_t h = (__uint32_t)(v >> 32);
178
179 if (h)
180 return xfs_highbit32(h) + 32;
181 return xfs_highbit32((__uint32_t)v);
182 }
183
184
185 /*
186 * Count the number of bits set in the bitmap starting with bit
187 * start_bit. Size is the size of the bitmap in words.
188 *
189 * Do the counting by mapping a byte value to the number of set
190 * bits for that value using the xfs_countbit array, i.e.
191 * xfs_countbit[0] == 0, xfs_countbit[1] == 1, xfs_countbit[2] == 1,
192 * xfs_countbit[3] == 2, etc.
193 */
194 int
xfs_count_bits(uint * map,uint size,uint start_bit)195 xfs_count_bits(uint *map, uint size, uint start_bit)
196 {
197 register int bits;
198 register unsigned char *bytep;
199 register unsigned char *end_map;
200 int byte_bit;
201
202 bits = 0;
203 end_map = (char*)(map + size);
204 bytep = (char*)(map + (start_bit & ~0x7));
205 byte_bit = start_bit & 0x7;
206
207 /*
208 * If the caller fell off the end of the map, return 0.
209 */
210 if (bytep >= end_map) {
211 return (0);
212 }
213
214 /*
215 * If start_bit is not byte aligned, then process the
216 * first byte separately.
217 */
218 if (byte_bit != 0) {
219 /*
220 * Shift off the bits we don't want to look at,
221 * before indexing into xfs_countbit.
222 */
223 bits += xfs_countbit[(*bytep >> byte_bit)];
224 bytep++;
225 }
226
227 /*
228 * Count the bits in each byte until the end of the bitmap.
229 */
230 while (bytep < end_map) {
231 bits += xfs_countbit[*bytep];
232 bytep++;
233 }
234
235 return (bits);
236 }
237
238 /*
239 * Count the number of contiguous bits set in the bitmap starting with bit
240 * start_bit. Size is the size of the bitmap in words.
241 */
242 int
xfs_contig_bits(uint * map,uint size,uint start_bit)243 xfs_contig_bits(uint *map, uint size, uint start_bit)
244 {
245 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
246 uint result = 0;
247 uint tmp;
248
249 size <<= BIT_TO_WORD_SHIFT;
250
251 ASSERT(start_bit < size);
252 size -= start_bit & ~(NBWORD - 1);
253 start_bit &= (NBWORD - 1);
254 if (start_bit) {
255 tmp = *p++;
256 /* set to one first offset bits prior to start */
257 tmp |= (~0U >> (NBWORD-start_bit));
258 if (tmp != ~0U)
259 goto found;
260 result += NBWORD;
261 size -= NBWORD;
262 }
263 while (size) {
264 if ((tmp = *p++) != ~0U)
265 goto found;
266 result += NBWORD;
267 size -= NBWORD;
268 }
269 return result - start_bit;
270 found:
271 return result + ffz(tmp) - start_bit;
272 }
273
274 /*
275 * This takes the bit number to start looking from and
276 * returns the next set bit from there. It returns -1
277 * if there are no more bits set or the start bit is
278 * beyond the end of the bitmap.
279 *
280 * Size is the number of words, not bytes, in the bitmap.
281 */
xfs_next_bit(uint * map,uint size,uint start_bit)282 int xfs_next_bit(uint *map, uint size, uint start_bit)
283 {
284 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
285 uint result = start_bit & ~(NBWORD - 1);
286 uint tmp;
287
288 size <<= BIT_TO_WORD_SHIFT;
289
290 if (start_bit >= size)
291 return -1;
292 size -= result;
293 start_bit &= (NBWORD - 1);
294 if (start_bit) {
295 tmp = *p++;
296 /* set to zero first offset bits prior to start */
297 tmp &= (~0U << start_bit);
298 if (tmp != 0U)
299 goto found;
300 result += NBWORD;
301 size -= NBWORD;
302 }
303 while (size) {
304 if ((tmp = *p++) != 0U)
305 goto found;
306 result += NBWORD;
307 size -= NBWORD;
308 }
309 return -1;
310 found:
311 return result + ffs(tmp) - 1;
312 }
313