]>
Commit | Line | Data |
---|---|---|
d4ae0811 NS |
1 | /* |
2 | * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved. | |
5000d01d | 3 | * |
d4ae0811 NS |
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. | |
5000d01d | 7 | * |
d4ae0811 NS |
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. | |
5000d01d | 11 | * |
d4ae0811 NS |
12 | * Further, this software is distributed without any warranty that it is |
13 | * free of the rightful claim of any third person regarding infringement | |
5000d01d | 14 | * or the like. Any license provided herein, whether implied or |
d4ae0811 NS |
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. | |
5000d01d | 18 | * |
d4ae0811 NS |
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. | |
5000d01d | 22 | * |
d4ae0811 NS |
23 | * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, |
24 | * Mountain View, CA 94043, or: | |
5000d01d SL |
25 | * |
26 | * http://www.sgi.com | |
27 | * | |
28 | * For further information regarding this notice, see: | |
29 | * | |
d4ae0811 NS |
30 | * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ |
31 | */ | |
32 | ||
33 | /* | |
34 | * XFS bit manipulation routines | |
35 | */ | |
36 | ||
37 | #include <xfs.h> | |
38 | ||
39 | /* | |
40 | * Index of low bit number in byte, -1 for none set, 0..7 otherwise. | |
41 | */ | |
42 | static const char xfs_lowbit[256] = { | |
43 | -1, 0, 1, 0, 2, 0, 1, 0, /* 00 .. 07 */ | |
44 | 3, 0, 1, 0, 2, 0, 1, 0, /* 08 .. 0f */ | |
45 | 4, 0, 1, 0, 2, 0, 1, 0, /* 10 .. 17 */ | |
46 | 3, 0, 1, 0, 2, 0, 1, 0, /* 18 .. 1f */ | |
47 | 5, 0, 1, 0, 2, 0, 1, 0, /* 20 .. 27 */ | |
48 | 3, 0, 1, 0, 2, 0, 1, 0, /* 28 .. 2f */ | |
49 | 4, 0, 1, 0, 2, 0, 1, 0, /* 30 .. 37 */ | |
50 | 3, 0, 1, 0, 2, 0, 1, 0, /* 38 .. 3f */ | |
51 | 6, 0, 1, 0, 2, 0, 1, 0, /* 40 .. 47 */ | |
52 | 3, 0, 1, 0, 2, 0, 1, 0, /* 48 .. 4f */ | |
53 | 4, 0, 1, 0, 2, 0, 1, 0, /* 50 .. 57 */ | |
54 | 3, 0, 1, 0, 2, 0, 1, 0, /* 58 .. 5f */ | |
55 | 5, 0, 1, 0, 2, 0, 1, 0, /* 60 .. 67 */ | |
56 | 3, 0, 1, 0, 2, 0, 1, 0, /* 68 .. 6f */ | |
57 | 4, 0, 1, 0, 2, 0, 1, 0, /* 70 .. 77 */ | |
58 | 3, 0, 1, 0, 2, 0, 1, 0, /* 78 .. 7f */ | |
59 | 7, 0, 1, 0, 2, 0, 1, 0, /* 80 .. 87 */ | |
60 | 3, 0, 1, 0, 2, 0, 1, 0, /* 88 .. 8f */ | |
61 | 4, 0, 1, 0, 2, 0, 1, 0, /* 90 .. 97 */ | |
62 | 3, 0, 1, 0, 2, 0, 1, 0, /* 98 .. 9f */ | |
63 | 5, 0, 1, 0, 2, 0, 1, 0, /* a0 .. a7 */ | |
64 | 3, 0, 1, 0, 2, 0, 1, 0, /* a8 .. af */ | |
65 | 4, 0, 1, 0, 2, 0, 1, 0, /* b0 .. b7 */ | |
66 | 3, 0, 1, 0, 2, 0, 1, 0, /* b8 .. bf */ | |
67 | 6, 0, 1, 0, 2, 0, 1, 0, /* c0 .. c7 */ | |
68 | 3, 0, 1, 0, 2, 0, 1, 0, /* c8 .. cf */ | |
69 | 4, 0, 1, 0, 2, 0, 1, 0, /* d0 .. d7 */ | |
70 | 3, 0, 1, 0, 2, 0, 1, 0, /* d8 .. df */ | |
71 | 5, 0, 1, 0, 2, 0, 1, 0, /* e0 .. e7 */ | |
72 | 3, 0, 1, 0, 2, 0, 1, 0, /* e8 .. ef */ | |
73 | 4, 0, 1, 0, 2, 0, 1, 0, /* f0 .. f7 */ | |
74 | 3, 0, 1, 0, 2, 0, 1, 0, /* f8 .. ff */ | |
75 | }; | |
76 | ||
77 | /* | |
78 | * Index of high bit number in byte, -1 for none set, 0..7 otherwise. | |
79 | */ | |
80 | static const char xfs_highbit[256] = { | |
81 | -1, 0, 1, 1, 2, 2, 2, 2, /* 00 .. 07 */ | |
82 | 3, 3, 3, 3, 3, 3, 3, 3, /* 08 .. 0f */ | |
83 | 4, 4, 4, 4, 4, 4, 4, 4, /* 10 .. 17 */ | |
84 | 4, 4, 4, 4, 4, 4, 4, 4, /* 18 .. 1f */ | |
85 | 5, 5, 5, 5, 5, 5, 5, 5, /* 20 .. 27 */ | |
86 | 5, 5, 5, 5, 5, 5, 5, 5, /* 28 .. 2f */ | |
87 | 5, 5, 5, 5, 5, 5, 5, 5, /* 30 .. 37 */ | |
88 | 5, 5, 5, 5, 5, 5, 5, 5, /* 38 .. 3f */ | |
89 | 6, 6, 6, 6, 6, 6, 6, 6, /* 40 .. 47 */ | |
90 | 6, 6, 6, 6, 6, 6, 6, 6, /* 48 .. 4f */ | |
91 | 6, 6, 6, 6, 6, 6, 6, 6, /* 50 .. 57 */ | |
92 | 6, 6, 6, 6, 6, 6, 6, 6, /* 58 .. 5f */ | |
93 | 6, 6, 6, 6, 6, 6, 6, 6, /* 60 .. 67 */ | |
94 | 6, 6, 6, 6, 6, 6, 6, 6, /* 68 .. 6f */ | |
95 | 6, 6, 6, 6, 6, 6, 6, 6, /* 70 .. 77 */ | |
96 | 6, 6, 6, 6, 6, 6, 6, 6, /* 78 .. 7f */ | |
97 | 7, 7, 7, 7, 7, 7, 7, 7, /* 80 .. 87 */ | |
98 | 7, 7, 7, 7, 7, 7, 7, 7, /* 88 .. 8f */ | |
99 | 7, 7, 7, 7, 7, 7, 7, 7, /* 90 .. 97 */ | |
100 | 7, 7, 7, 7, 7, 7, 7, 7, /* 98 .. 9f */ | |
101 | 7, 7, 7, 7, 7, 7, 7, 7, /* a0 .. a7 */ | |
102 | 7, 7, 7, 7, 7, 7, 7, 7, /* a8 .. af */ | |
103 | 7, 7, 7, 7, 7, 7, 7, 7, /* b0 .. b7 */ | |
104 | 7, 7, 7, 7, 7, 7, 7, 7, /* b8 .. bf */ | |
105 | 7, 7, 7, 7, 7, 7, 7, 7, /* c0 .. c7 */ | |
106 | 7, 7, 7, 7, 7, 7, 7, 7, /* c8 .. cf */ | |
107 | 7, 7, 7, 7, 7, 7, 7, 7, /* d0 .. d7 */ | |
108 | 7, 7, 7, 7, 7, 7, 7, 7, /* d8 .. df */ | |
109 | 7, 7, 7, 7, 7, 7, 7, 7, /* e0 .. e7 */ | |
110 | 7, 7, 7, 7, 7, 7, 7, 7, /* e8 .. ef */ | |
111 | 7, 7, 7, 7, 7, 7, 7, 7, /* f0 .. f7 */ | |
112 | 7, 7, 7, 7, 7, 7, 7, 7, /* f8 .. ff */ | |
113 | }; | |
114 | ||
115 | /* | |
116 | * Count of bits set in byte, 0..8. | |
117 | */ | |
118 | static const char xfs_countbit[256] = { | |
119 | 0, 1, 1, 2, 1, 2, 2, 3, /* 00 .. 07 */ | |
120 | 1, 2, 2, 3, 2, 3, 3, 4, /* 08 .. 0f */ | |
121 | 1, 2, 2, 3, 2, 3, 3, 4, /* 10 .. 17 */ | |
122 | 2, 3, 3, 4, 3, 4, 4, 5, /* 18 .. 1f */ | |
123 | 1, 2, 2, 3, 2, 3, 3, 4, /* 20 .. 27 */ | |
124 | 2, 3, 3, 4, 3, 4, 4, 5, /* 28 .. 2f */ | |
125 | 2, 3, 3, 4, 3, 4, 4, 5, /* 30 .. 37 */ | |
126 | 3, 4, 4, 5, 4, 5, 5, 6, /* 38 .. 3f */ | |
127 | 1, 2, 2, 3, 2, 3, 3, 4, /* 40 .. 47 */ | |
128 | 2, 3, 3, 4, 3, 4, 4, 5, /* 48 .. 4f */ | |
129 | 2, 3, 3, 4, 3, 4, 4, 5, /* 50 .. 57 */ | |
130 | 3, 4, 4, 5, 4, 5, 5, 6, /* 58 .. 5f */ | |
131 | 2, 3, 3, 4, 3, 4, 4, 5, /* 60 .. 67 */ | |
132 | 3, 4, 4, 5, 4, 5, 5, 6, /* 68 .. 6f */ | |
133 | 3, 4, 4, 5, 4, 5, 5, 6, /* 70 .. 77 */ | |
134 | 4, 5, 5, 6, 5, 6, 6, 7, /* 78 .. 7f */ | |
135 | 1, 2, 2, 3, 2, 3, 3, 4, /* 80 .. 87 */ | |
136 | 2, 3, 3, 4, 3, 4, 4, 5, /* 88 .. 8f */ | |
137 | 2, 3, 3, 4, 3, 4, 4, 5, /* 90 .. 97 */ | |
138 | 3, 4, 4, 5, 4, 5, 5, 6, /* 98 .. 9f */ | |
139 | 2, 3, 3, 4, 3, 4, 4, 5, /* a0 .. a7 */ | |
140 | 3, 4, 4, 5, 4, 5, 5, 6, /* a8 .. af */ | |
141 | 3, 4, 4, 5, 4, 5, 5, 6, /* b0 .. b7 */ | |
142 | 4, 5, 5, 6, 5, 6, 6, 7, /* b8 .. bf */ | |
143 | 2, 3, 3, 4, 3, 4, 4, 5, /* c0 .. c7 */ | |
144 | 3, 4, 4, 5, 4, 5, 5, 6, /* c8 .. cf */ | |
145 | 3, 4, 4, 5, 4, 5, 5, 6, /* d0 .. d7 */ | |
146 | 4, 5, 5, 6, 5, 6, 6, 7, /* d8 .. df */ | |
147 | 3, 4, 4, 5, 4, 5, 5, 6, /* e0 .. e7 */ | |
148 | 4, 5, 5, 6, 5, 6, 6, 7, /* e8 .. ef */ | |
149 | 4, 5, 5, 6, 5, 6, 6, 7, /* f0 .. f7 */ | |
150 | 5, 6, 6, 7, 6, 7, 7, 8, /* f8 .. ff */ | |
151 | }; | |
152 | ||
153 | /* | |
154 | * xfs_lowbit32: get low bit set out of 32-bit argument, -1 if none set. | |
155 | */ | |
156 | int | |
157 | xfs_lowbit32( | |
158 | __uint32_t v) | |
159 | { | |
160 | int i; | |
161 | ||
162 | if (v & 0x0000ffff) | |
163 | if (v & 0x000000ff) | |
164 | i = 0; | |
165 | else | |
166 | i = 8; | |
167 | else if (v & 0xffff0000) | |
168 | if (v & 0x00ff0000) | |
169 | i = 16; | |
170 | else | |
171 | i = 24; | |
172 | else | |
173 | return -1; | |
174 | return i + xfs_lowbit[(v >> i) & 0xff]; | |
175 | } | |
176 | ||
177 | /* | |
178 | * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set. | |
179 | */ | |
180 | int | |
181 | xfs_highbit32( | |
182 | __uint32_t v) | |
183 | { | |
184 | int i; | |
185 | ||
186 | if (v & 0xffff0000) | |
187 | if (v & 0xff000000) | |
188 | i = 24; | |
189 | else | |
190 | i = 16; | |
191 | else if (v & 0x0000ffff) | |
192 | if (v & 0x0000ff00) | |
193 | i = 8; | |
194 | else | |
195 | i = 0; | |
196 | else | |
197 | return -1; | |
198 | return i + xfs_highbit[(v >> i) & 0xff]; | |
199 | } | |
200 | ||
201 | /* | |
202 | * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set. | |
203 | */ | |
204 | int | |
205 | xfs_lowbit64( | |
206 | __uint64_t v) | |
207 | { | |
208 | int i; | |
209 | #if XFS_64 | |
210 | if (v & 0x00000000ffffffff) | |
211 | if (v & 0x000000000000ffff) | |
212 | if (v & 0x00000000000000ff) | |
213 | i = 0; | |
214 | else | |
215 | i = 8; | |
216 | else | |
217 | if (v & 0x0000000000ff0000) | |
218 | i = 16; | |
219 | else | |
220 | i = 24; | |
221 | else if (v & 0xffffffff00000000) | |
222 | if (v & 0x0000ffff00000000) | |
223 | if (v & 0x000000ff00000000) | |
224 | i = 32; | |
225 | else | |
226 | i = 40; | |
227 | else | |
228 | if (v & 0x00ff000000000000) | |
229 | i = 48; | |
230 | else | |
231 | i = 56; | |
232 | else | |
233 | return -1; | |
234 | return i + xfs_lowbit[(v >> i) & 0xff]; | |
235 | #else | |
236 | __uint32_t vw; | |
237 | ||
238 | if ((vw = v)) { | |
239 | if (vw & 0x0000ffff) | |
240 | if (vw & 0x000000ff) | |
241 | i = 0; | |
242 | else | |
243 | i = 8; | |
244 | else | |
245 | if (vw & 0x00ff0000) | |
246 | i = 16; | |
247 | else | |
248 | i = 24; | |
249 | return i + xfs_lowbit[(vw >> i) & 0xff]; | |
250 | } else if ((vw = v >> 32)) { | |
251 | if (vw & 0x0000ffff) | |
252 | if (vw & 0x000000ff) | |
253 | i = 32; | |
254 | else | |
255 | i = 40; | |
256 | else | |
257 | if (vw & 0x00ff0000) | |
258 | i = 48; | |
259 | else | |
260 | i = 56; | |
261 | return i + xfs_lowbit[(vw >> (i - 32)) & 0xff]; | |
262 | } else | |
263 | return -1; | |
264 | #endif | |
265 | } | |
266 | ||
267 | /* | |
268 | * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set. | |
269 | */ | |
270 | int | |
271 | xfs_highbit64( | |
272 | __uint64_t v) | |
273 | { | |
274 | int i; | |
275 | #if XFS_64 | |
276 | if (v & 0xffffffff00000000) | |
277 | if (v & 0xffff000000000000) | |
278 | if (v & 0xff00000000000000) | |
279 | i = 56; | |
280 | else | |
281 | i = 48; | |
282 | else | |
283 | if (v & 0x0000ff0000000000) | |
284 | i = 40; | |
285 | else | |
286 | i = 32; | |
287 | else if (v & 0x00000000ffffffff) | |
288 | if (v & 0x00000000ffff0000) | |
289 | if (v & 0x00000000ff000000) | |
290 | i = 24; | |
291 | else | |
292 | i = 16; | |
293 | else | |
294 | if (v & 0x000000000000ff00) | |
295 | i = 8; | |
296 | else | |
297 | i = 0; | |
298 | else | |
299 | return -1; | |
300 | return i + xfs_highbit[(v >> i) & 0xff]; | |
301 | #else | |
302 | __uint32_t vw; | |
303 | ||
304 | if ((vw = v >> 32)) { | |
305 | if (vw & 0xffff0000) | |
306 | if (vw & 0xff000000) | |
307 | i = 56; | |
308 | else | |
309 | i = 48; | |
310 | else | |
311 | if (vw & 0x0000ff00) | |
312 | i = 40; | |
313 | else | |
314 | i = 32; | |
315 | return i + xfs_highbit[(vw >> (i - 32)) & 0xff]; | |
316 | } else if ((vw = v)) { | |
317 | if (vw & 0xffff0000) | |
318 | if (vw & 0xff000000) | |
319 | i = 24; | |
320 | else | |
321 | i = 16; | |
322 | else | |
323 | if (vw & 0x0000ff00) | |
324 | i = 8; | |
325 | else | |
326 | i = 0; | |
327 | return i + xfs_highbit[(vw >> i) & 0xff]; | |
328 | } else | |
329 | return -1; | |
330 | #endif | |
331 | } |