2 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
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.
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.
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.
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.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 * XFS bit manipulation routines, used in non-realtime code.
40 #include "xfs_trans.h"
41 #include "xfs_buf_item.h"
44 #ifndef HAVE_ARCH_HIGHBIT
46 * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
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 */
85 * Count of bits set in byte, 0..8.
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 */
123 * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
129 #ifdef HAVE_ARCH_HIGHBIT
139 else if (v & 0x0000ffff)
146 return i + xfs_highbit[(v >> i) & 0xff];
151 * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
158 n = ffs((unsigned)v);
164 return (n <= 0) ? n : n-1;
168 * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
174 __uint32_t h = v >> 32;
176 return xfs_highbit32(h) + 32;
177 return xfs_highbit32((__u32)v);
182 * Count the number of bits set in the bitmap starting with bit
183 * start_bit. Size is the size of the bitmap in words.
185 * Do the counting by mapping a byte value to the number of set
186 * bits for that value using the xfs_countbit array, i.e.
187 * xfs_countbit[0] == 0, xfs_countbit[1] == 1, xfs_countbit[2] == 1,
188 * xfs_countbit[3] == 2, etc.
191 xfs_count_bits(uint *map, uint size, uint start_bit)
194 register unsigned char *bytep;
195 register unsigned char *end_map;
199 end_map = (char*)(map + size);
200 bytep = (char*)(map + (start_bit & ~0x7));
201 byte_bit = start_bit & 0x7;
204 * If the caller fell off the end of the map, return 0.
206 if (bytep >= end_map) {
211 * If start_bit is not byte aligned, then process the
212 * first byte separately.
216 * Shift off the bits we don't want to look at,
217 * before indexing into xfs_countbit.
219 bits += xfs_countbit[(*bytep >> byte_bit)];
224 * Count the bits in each byte until the end of the bitmap.
226 while (bytep < end_map) {
227 bits += xfs_countbit[*bytep];
235 * Count the number of contiguous bits set in the bitmap starting with bit
236 * start_bit. Size is the size of the bitmap in words.
239 xfs_contig_bits(uint *map, uint size, uint start_bit)
241 #if BITS_PER_LONG == 32
242 return find_next_zero_bit((unsigned long *)map,
243 size * sizeof(uint) * 8, start_bit) - start_bit;
246 * The first argument to find_next_zero_bit needs to be aligned,
247 * but this is coming from the xfs_buf_log_format_t on-disk
248 * struct, which can't be padded or otherwise modified w/o breaking
249 * on-disk compatibility... so create a temporary, aligned
250 * variable, copy over the bitmap, and send that to find_next_zero_bit
251 * This only happens in recovery, so it's ugly but not too bad.
255 size_t bitmap_size = size * sizeof(uint);
257 addr = (void *)kmem_alloc(bitmap_size, KM_SLEEP);
258 memcpy(addr, map, size * sizeof(uint));
260 bit = find_next_zero_bit((unsigned long *)addr,
261 size * sizeof(uint) * 8, start_bit) - start_bit;
263 kmem_free(addr, bitmap_size);
270 * This takes the bit number to start looking from and
271 * returns the next set bit from there. It returns -1
272 * if there are no more bits set or the start bit is
273 * beyond the end of the bitmap.
275 * Size is the number of words, not bytes, in the bitmap.
277 int xfs_next_bit(uint *map, uint size, uint start_bit)
279 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
280 uint result = start_bit & ~(NBWORD - 1);
283 size <<= BIT_TO_WORD_SHIFT;
285 if (start_bit >= size)
288 start_bit &= (NBWORD - 1);
291 /* set to zero first offset bits */
292 tmp &= (~0U << start_bit);
300 while (size >= NBWORD) {
301 if ((tmp = *p++) != 0U)
311 return result + ffs(tmp) - 1;