]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libxfs/xfs_bit.c
39dea3b693f5af70e1c6cafa3416f3db9fc153db
2 * Copyright (c) 2000 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 * Index of low bit number in byte, -1 for none set, 0..7 otherwise.
42 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 */
78 * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
80 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 */
116 * Count of bits set in byte, 0..8.
118 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 */
154 * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
167 else if (v
& 0x0000ffff)
174 return i
+ xfs_highbit
[(v
>> i
) & 0xff];
178 * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
186 if (v
& 0x00000000ffffffff)
187 if (v
& 0x000000000000ffff)
188 if (v
& 0x00000000000000ff)
193 if (v
& 0x0000000000ff0000)
197 else if (v
& 0xffffffff00000000)
198 if (v
& 0x0000ffff00000000)
199 if (v
& 0x000000ff00000000)
204 if (v
& 0x00ff000000000000)
210 return i
+ xfs_lowbit
[(v
>> i
) & 0xff];
225 return i
+ xfs_lowbit
[(vw
>> i
) & 0xff];
226 } else if ((vw
= v
>> 32)) {
237 return i
+ xfs_lowbit
[(vw
>> (i
- 32)) & 0xff];
244 * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
252 if (v
& 0xffffffff00000000)
253 if (v
& 0xffff000000000000)
254 if (v
& 0xff00000000000000)
259 if (v
& 0x0000ff0000000000)
263 else if (v
& 0x00000000ffffffff)
264 if (v
& 0x00000000ffff0000)
265 if (v
& 0x00000000ff000000)
270 if (v
& 0x000000000000ff00)
276 return i
+ xfs_highbit
[(v
>> i
) & 0xff];
280 if ((vw
= v
>> 32)) {
291 return i
+ xfs_highbit
[(vw
>> (i
- 32)) & 0xff];
292 } else if ((vw
= v
)) {
303 return i
+ xfs_highbit
[(vw
>> i
) & 0xff];