blob: fab0b6d5a41be3916ac8893a2f82f142cd4443f4 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include "xfs.h"
19#include "xfs_bit.h"
20#include "xfs_log.h"
21#include "xfs_trans.h"
22#include "xfs_buf_item.h"
23
Nathan Scott7b718762005-11-02 14:58:39 +110024/*
25 * XFS bit manipulation routines, used in non-realtime code.
26 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070027
Lachlan McIlroyef8ece52008-02-26 17:00:22 +110028#ifndef HAVE_ARCH_HIGHBIT
29/*
30 * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
31 */
32static const char xfs_highbit[256] = {
33 -1, 0, 1, 1, 2, 2, 2, 2, /* 00 .. 07 */
34 3, 3, 3, 3, 3, 3, 3, 3, /* 08 .. 0f */
35 4, 4, 4, 4, 4, 4, 4, 4, /* 10 .. 17 */
36 4, 4, 4, 4, 4, 4, 4, 4, /* 18 .. 1f */
37 5, 5, 5, 5, 5, 5, 5, 5, /* 20 .. 27 */
38 5, 5, 5, 5, 5, 5, 5, 5, /* 28 .. 2f */
39 5, 5, 5, 5, 5, 5, 5, 5, /* 30 .. 37 */
40 5, 5, 5, 5, 5, 5, 5, 5, /* 38 .. 3f */
41 6, 6, 6, 6, 6, 6, 6, 6, /* 40 .. 47 */
42 6, 6, 6, 6, 6, 6, 6, 6, /* 48 .. 4f */
43 6, 6, 6, 6, 6, 6, 6, 6, /* 50 .. 57 */
44 6, 6, 6, 6, 6, 6, 6, 6, /* 58 .. 5f */
45 6, 6, 6, 6, 6, 6, 6, 6, /* 60 .. 67 */
46 6, 6, 6, 6, 6, 6, 6, 6, /* 68 .. 6f */
47 6, 6, 6, 6, 6, 6, 6, 6, /* 70 .. 77 */
48 6, 6, 6, 6, 6, 6, 6, 6, /* 78 .. 7f */
49 7, 7, 7, 7, 7, 7, 7, 7, /* 80 .. 87 */
50 7, 7, 7, 7, 7, 7, 7, 7, /* 88 .. 8f */
51 7, 7, 7, 7, 7, 7, 7, 7, /* 90 .. 97 */
52 7, 7, 7, 7, 7, 7, 7, 7, /* 98 .. 9f */
53 7, 7, 7, 7, 7, 7, 7, 7, /* a0 .. a7 */
54 7, 7, 7, 7, 7, 7, 7, 7, /* a8 .. af */
55 7, 7, 7, 7, 7, 7, 7, 7, /* b0 .. b7 */
56 7, 7, 7, 7, 7, 7, 7, 7, /* b8 .. bf */
57 7, 7, 7, 7, 7, 7, 7, 7, /* c0 .. c7 */
58 7, 7, 7, 7, 7, 7, 7, 7, /* c8 .. cf */
59 7, 7, 7, 7, 7, 7, 7, 7, /* d0 .. d7 */
60 7, 7, 7, 7, 7, 7, 7, 7, /* d8 .. df */
61 7, 7, 7, 7, 7, 7, 7, 7, /* e0 .. e7 */
62 7, 7, 7, 7, 7, 7, 7, 7, /* e8 .. ef */
63 7, 7, 7, 7, 7, 7, 7, 7, /* f0 .. f7 */
64 7, 7, 7, 7, 7, 7, 7, 7, /* f8 .. ff */
65};
66#endif
67
68/*
69 * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
70 */
71inline int
72xfs_highbit32(
73 __uint32_t v)
74{
75#ifdef HAVE_ARCH_HIGHBIT
76 return highbit32(v);
77#else
78 int i;
79
80 if (v & 0xffff0000)
81 if (v & 0xff000000)
82 i = 24;
83 else
84 i = 16;
85 else if (v & 0x0000ffff)
86 if (v & 0x0000ff00)
87 i = 8;
88 else
89 i = 0;
90 else
91 return -1;
92 return i + xfs_highbit[(v >> i) & 0xff];
93#endif
94}
95
96/*
97 * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
98 */
99int
100xfs_lowbit64(
101 __uint64_t v)
102{
103 __uint32_t w = (__uint32_t)v;
104 int n = 0;
105
106 if (w) { /* lower bits */
107 n = ffs(w);
108 } else { /* upper bits */
109 w = (__uint32_t)(v >> 32);
110 if (w && (n = ffs(w)))
111 n += 32;
112 }
113 return n - 1;
114}
115
116/*
117 * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
118 */
119int
120xfs_highbit64(
121 __uint64_t v)
122{
123 __uint32_t h = (__uint32_t)(v >> 32);
124
125 if (h)
126 return xfs_highbit32(h) + 32;
127 return xfs_highbit32((__uint32_t)v);
128}
129
130
Linus Torvalds1da177e2005-04-16 15:20:36 -0700131/*
Eric Sandeen24ad33f2007-06-28 16:43:30 +1000132 * Return whether bitmap is empty.
133 * Size is number of words in the bitmap, which is padded to word boundary
134 * Returns 1 for empty, 0 for non-empty.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700135 */
136int
Eric Sandeen24ad33f2007-06-28 16:43:30 +1000137xfs_bitmap_empty(uint *map, uint size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138{
Eric Sandeen24ad33f2007-06-28 16:43:30 +1000139 uint i;
140 uint ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
Eric Sandeen24ad33f2007-06-28 16:43:30 +1000142 for (i = 0; i < size; i++) {
143 ret |= map[i];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 }
145
Eric Sandeen24ad33f2007-06-28 16:43:30 +1000146 return (ret == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147}
148
149/*
150 * Count the number of contiguous bits set in the bitmap starting with bit
151 * start_bit. Size is the size of the bitmap in words.
152 */
153int
154xfs_contig_bits(uint *map, uint size, uint start_bit)
155{
156 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
157 uint result = 0;
158 uint tmp;
159
160 size <<= BIT_TO_WORD_SHIFT;
161
162 ASSERT(start_bit < size);
163 size -= start_bit & ~(NBWORD - 1);
164 start_bit &= (NBWORD - 1);
165 if (start_bit) {
166 tmp = *p++;
167 /* set to one first offset bits prior to start */
168 tmp |= (~0U >> (NBWORD-start_bit));
169 if (tmp != ~0U)
170 goto found;
171 result += NBWORD;
172 size -= NBWORD;
173 }
174 while (size) {
175 if ((tmp = *p++) != ~0U)
176 goto found;
177 result += NBWORD;
178 size -= NBWORD;
179 }
180 return result - start_bit;
181found:
182 return result + ffz(tmp) - start_bit;
183}
184
185/*
186 * This takes the bit number to start looking from and
187 * returns the next set bit from there. It returns -1
188 * if there are no more bits set or the start bit is
189 * beyond the end of the bitmap.
190 *
191 * Size is the number of words, not bytes, in the bitmap.
192 */
193int xfs_next_bit(uint *map, uint size, uint start_bit)
194{
195 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
196 uint result = start_bit & ~(NBWORD - 1);
197 uint tmp;
198
199 size <<= BIT_TO_WORD_SHIFT;
200
201 if (start_bit >= size)
202 return -1;
203 size -= result;
204 start_bit &= (NBWORD - 1);
205 if (start_bit) {
206 tmp = *p++;
207 /* set to zero first offset bits prior to start */
208 tmp &= (~0U << start_bit);
209 if (tmp != 0U)
210 goto found;
211 result += NBWORD;
212 size -= NBWORD;
213 }
214 while (size) {
215 if ((tmp = *p++) != 0U)
216 goto found;
217 result += NBWORD;
218 size -= NBWORD;
219 }
220 return -1;
221found:
222 return result + ffs(tmp) - 1;
223}