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];