Linux-2.6.12-rc2
[linux-2.6.git] / fs / xfs / xfs_bit.c
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
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
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
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
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
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  */
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 }