|
132
|
1 /**
|
|
|
2 * This module contains a collection of bit-level operations.
|
|
|
3 *
|
|
|
4 * Copyright: Public Domain
|
|
|
5 * License: Public Domain
|
|
|
6 * Authors: Sean Kelly
|
|
|
7 */
|
|
|
8 module tango.core.BitManip;
|
|
|
9
|
|
|
10
|
|
|
11 version( DDoc )
|
|
|
12 {
|
|
|
13 /**
|
|
|
14 * Scans the bits in v starting with bit 0, looking
|
|
|
15 * for the first set bit.
|
|
|
16 * Returns:
|
|
|
17 * The bit number of the first bit set.
|
|
|
18 * The return value is undefined if v is zero.
|
|
|
19 */
|
|
|
20 int bsf( uint v );
|
|
|
21
|
|
|
22
|
|
|
23 /**
|
|
|
24 * Scans the bits in v from the most significant bit
|
|
|
25 * to the least significant bit, looking
|
|
|
26 * for the first set bit.
|
|
|
27 * Returns:
|
|
|
28 * The bit number of the first bit set.
|
|
|
29 * The return value is undefined if v is zero.
|
|
|
30 * Example:
|
|
|
31 * ---
|
|
|
32 * import std.intrinsic;
|
|
|
33 *
|
|
|
34 * int main()
|
|
|
35 * {
|
|
|
36 * uint v;
|
|
|
37 * int x;
|
|
|
38 *
|
|
|
39 * v = 0x21;
|
|
|
40 * x = bsf(v);
|
|
|
41 * printf("bsf(x%x) = %d\n", v, x);
|
|
|
42 * x = bsr(v);
|
|
|
43 * printf("bsr(x%x) = %d\n", v, x);
|
|
|
44 * return 0;
|
|
|
45 * }
|
|
|
46 * ---
|
|
|
47 * Output:
|
|
|
48 * bsf(x21) = 0<br>
|
|
|
49 * bsr(x21) = 5
|
|
|
50 */
|
|
|
51 int bsr( uint v );
|
|
|
52
|
|
|
53
|
|
|
54 /**
|
|
|
55 * Tests the bit.
|
|
|
56 */
|
|
|
57 int bt( uint* p, uint bitnum );
|
|
|
58
|
|
|
59
|
|
|
60 /**
|
|
|
61 * Tests and complements the bit.
|
|
|
62 */
|
|
|
63 int btc( uint* p, uint bitnum );
|
|
|
64
|
|
|
65
|
|
|
66 /**
|
|
|
67 * Tests and resets (sets to 0) the bit.
|
|
|
68 */
|
|
|
69 int btr( uint* p, uint bitnum );
|
|
|
70
|
|
|
71
|
|
|
72 /**
|
|
|
73 * Tests and sets the bit.
|
|
|
74 * Params:
|
|
|
75 * p = a non-NULL pointer to an array of uints.
|
|
|
76 * index = a bit number, starting with bit 0 of p[0],
|
|
|
77 * and progressing. It addresses bits like the expression:
|
|
|
78 ---
|
|
|
79 p[index / (uint.sizeof*8)] & (1 << (index & ((uint.sizeof*8) - 1)))
|
|
|
80 ---
|
|
|
81 * Returns:
|
|
|
82 * A non-zero value if the bit was set, and a zero
|
|
|
83 * if it was clear.
|
|
|
84 *
|
|
|
85 * Example:
|
|
|
86 * ---
|
|
|
87 import std.intrinsic;
|
|
|
88
|
|
|
89 int main()
|
|
|
90 {
|
|
|
91 uint array[2];
|
|
|
92
|
|
|
93 array[0] = 2;
|
|
|
94 array[1] = 0x100;
|
|
|
95
|
|
|
96 printf("btc(array, 35) = %d\n", <b>btc</b>(array, 35));
|
|
|
97 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
|
|
|
98
|
|
|
99 printf("btc(array, 35) = %d\n", <b>btc</b>(array, 35));
|
|
|
100 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
|
|
|
101
|
|
|
102 printf("bts(array, 35) = %d\n", <b>bts</b>(array, 35));
|
|
|
103 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
|
|
|
104
|
|
|
105 printf("btr(array, 35) = %d\n", <b>btr</b>(array, 35));
|
|
|
106 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
|
|
|
107
|
|
|
108 printf("bt(array, 1) = %d\n", <b>bt</b>(array, 1));
|
|
|
109 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
|
|
|
110
|
|
|
111 return 0;
|
|
|
112 }
|
|
|
113 * ---
|
|
|
114 * Output:
|
|
|
115 <pre>
|
|
|
116 btc(array, 35) = 0
|
|
|
117 array = [0]:x2, [1]:x108
|
|
|
118 btc(array, 35) = -1
|
|
|
119 array = [0]:x2, [1]:x100
|
|
|
120 bts(array, 35) = 0
|
|
|
121 array = [0]:x2, [1]:x108
|
|
|
122 btr(array, 35) = -1
|
|
|
123 array = [0]:x2, [1]:x100
|
|
|
124 bt(array, 1) = -1
|
|
|
125 array = [0]:x2, [1]:x100
|
|
|
126 </pre>
|
|
|
127 */
|
|
|
128 int bts( uint* p, uint bitnum );
|
|
|
129
|
|
|
130
|
|
|
131 /**
|
|
|
132 * Swaps bytes in a 4 byte uint end-to-end, i.e. byte 0 becomes
|
|
|
133 * byte 3, byte 1 becomes byte 2, byte 2 becomes byte 1, byte 3
|
|
|
134 * becomes byte 0.
|
|
|
135 */
|
|
|
136 uint bswap( uint v );
|
|
|
137
|
|
|
138
|
|
|
139 /**
|
|
|
140 * Reads I/O port at port_address.
|
|
|
141 */
|
|
|
142 ubyte inp( uint port_address );
|
|
|
143
|
|
|
144
|
|
|
145 /**
|
|
|
146 * ditto
|
|
|
147 */
|
|
|
148 ushort inpw( uint port_address );
|
|
|
149
|
|
|
150
|
|
|
151 /**
|
|
|
152 * ditto
|
|
|
153 */
|
|
|
154 uint inpl( uint port_address );
|
|
|
155
|
|
|
156
|
|
|
157 /**
|
|
|
158 * Writes and returns value to I/O port at port_address.
|
|
|
159 */
|
|
|
160 ubyte outp( uint port_address, ubyte value );
|
|
|
161
|
|
|
162
|
|
|
163 /**
|
|
|
164 * ditto
|
|
|
165 */
|
|
|
166 ushort outpw( uint port_address, ushort value );
|
|
|
167
|
|
|
168
|
|
|
169 /**
|
|
|
170 * ditto
|
|
|
171 */
|
|
|
172 uint outpl( uint port_address, uint value );
|
|
|
173 }
|
|
184
|
174 else version( LLVMDC )
|
|
|
175 {
|
|
|
176 // From GDC ... public domain!
|
|
|
177
|
|
|
178 int bsf(uint v)
|
|
|
179 {
|
|
|
180 uint m = 1;
|
|
|
181 uint i;
|
|
|
182 for (i = 0; i < 32; i++,m<<=1) {
|
|
|
183 if (v&m)
|
|
|
184 return i;
|
|
|
185 }
|
|
|
186 return i; // supposed to be undefined
|
|
|
187 }
|
|
|
188
|
|
|
189 int bsr(uint v)
|
|
|
190 {
|
|
|
191 uint m = 0x80000000;
|
|
|
192 uint i;
|
|
|
193 for (i = 32; i ; i--,m>>>=1) {
|
|
|
194 if (v&m)
|
|
|
195 return i-1;
|
|
|
196 }
|
|
|
197 return i; // supposed to be undefined
|
|
|
198 }
|
|
|
199
|
|
|
200 int bt(uint *p, uint bitnum)
|
|
|
201 {
|
|
|
202 return (p[bitnum / (uint.sizeof*8)] & (1<<(bitnum & ((uint.sizeof*8)-1)))) ? -1 : 0 ;
|
|
|
203 }
|
|
|
204
|
|
|
205 int btc(uint *p, uint bitnum)
|
|
|
206 {
|
|
|
207 uint * q = p + (bitnum / (uint.sizeof*8));
|
|
|
208 uint mask = 1 << (bitnum & ((uint.sizeof*8) - 1));
|
|
|
209 int result = *q & mask;
|
|
|
210 *q ^= mask;
|
|
|
211 return result ? -1 : 0;
|
|
|
212 }
|
|
|
213
|
|
|
214 int btr(uint *p, uint bitnum)
|
|
|
215 {
|
|
|
216 uint * q = p + (bitnum / (uint.sizeof*8));
|
|
|
217 uint mask = 1 << (bitnum & ((uint.sizeof*8) - 1));
|
|
|
218 int result = *q & mask;
|
|
|
219 *q &= ~mask;
|
|
|
220 return result ? -1 : 0;
|
|
|
221 }
|
|
|
222
|
|
|
223 int bts(uint *p, uint bitnum)
|
|
|
224 {
|
|
|
225 uint * q = p + (bitnum / (uint.sizeof*8));
|
|
|
226 uint mask = 1 << (bitnum & ((uint.sizeof*8) - 1));
|
|
|
227 int result = *q & mask;
|
|
|
228 *q |= mask;
|
|
|
229 return result ? -1 : 0;
|
|
|
230 }
|
|
|
231
|
|
|
232 pragma(LLVM_internal, "intrinsic", "llvm.bswap.i32")
|
|
|
233 uint bswap(uint val);
|
|
|
234
|
|
|
235 ubyte inp(uint p) { return 0; }
|
|
|
236 ushort inpw(uint p) { return 0; }
|
|
|
237 uint inpl(uint p) { return 0; }
|
|
|
238
|
|
|
239 ubyte outp(uint p, ubyte v) { return v; }
|
|
|
240 ushort outpw(uint p, ushort v) { return v; }
|
|
|
241 uint outpl(uint p, uint v) { return v; }
|
|
|
242 }
|
|
132
|
243 else
|
|
|
244 {
|
|
|
245 public import std.intrinsic;
|
|
|
246 }
|
|
|
247
|
|
|
248
|
|
|
249 /**
|
|
|
250 * Calculates the number of set bits in a 32-bit integer.
|
|
|
251 */
|
|
|
252 int popcnt( uint x )
|
|
|
253 {
|
|
|
254 // Avoid branches, and the potential for cache misses which
|
|
|
255 // could be incurred with a table lookup.
|
|
|
256
|
|
|
257 // We need to mask alternate bits to prevent the
|
|
|
258 // sum from overflowing.
|
|
|
259 // add neighbouring bits. Each bit is 0 or 1.
|
|
|
260 x = x - ((x>>1) & 0x5555_5555);
|
|
|
261 // now each two bits of x is a number 00,01 or 10.
|
|
|
262 // now add neighbouring pairs
|
|
|
263 x = ((x&0xCCCC_CCCC)>>2) + (x&0x3333_3333);
|
|
|
264 // now each nibble holds 0000-0100. Adding them won't
|
|
|
265 // overflow any more, so we don't need to mask any more
|
|
|
266
|
|
|
267 // Now add the nibbles, then the bytes, then the words
|
|
|
268 // We still need to mask to prevent double-counting.
|
|
|
269 // Note that if we used a rotate instead of a shift, we
|
|
|
270 // wouldn't need the masks, and could just divide the sum
|
|
|
271 // by 8 to account for the double-counting.
|
|
|
272 // On some CPUs, it may be faster to perform a multiply.
|
|
|
273
|
|
|
274 x += (x>>4);
|
|
|
275 x &= 0x0F0F_0F0F;
|
|
|
276 x += (x>>8);
|
|
|
277 x &= 0x00FF_00FF;
|
|
|
278 x += (x>>16);
|
|
|
279 x &= 0xFFFF;
|
|
|
280 return x;
|
|
|
281 }
|
|
|
282
|
|
|
283
|
|
|
284 debug( UnitTest )
|
|
|
285 {
|
|
|
286 unittest
|
|
|
287 {
|
|
|
288 assert( popcnt( 0 ) == 0 );
|
|
|
289 assert( popcnt( 7 ) == 3 );
|
|
|
290 assert( popcnt( 0xAA )== 4 );
|
|
|
291 assert( popcnt( 0x8421_1248 ) == 8 );
|
|
|
292 assert( popcnt( 0xFFFF_FFFF ) == 32 );
|
|
|
293 assert( popcnt( 0xCCCC_CCCC ) == 16 );
|
|
|
294 assert( popcnt( 0x7777_7777 ) == 24 );
|
|
|
295 }
|
|
|
296 }
|
|
|
297
|
|
|
298
|
|
|
299 /**
|
|
|
300 * Reverses the order of bits in a 32-bit integer.
|
|
|
301 */
|
|
|
302 uint bitswap( uint x )
|
|
|
303 {
|
|
|
304
|
|
|
305 version( D_InlineAsm_X86 )
|
|
|
306 {
|
|
|
307 asm
|
|
|
308 {
|
|
|
309 // Author: Tiago Gasiba.
|
|
|
310 mov EDX, EAX;
|
|
|
311 shr EAX, 1;
|
|
|
312 and EDX, 0x5555_5555;
|
|
|
313 and EAX, 0x5555_5555;
|
|
|
314 shl EDX, 1;
|
|
|
315 or EAX, EDX;
|
|
|
316 mov EDX, EAX;
|
|
|
317 shr EAX, 2;
|
|
|
318 and EDX, 0x3333_3333;
|
|
|
319 and EAX, 0x3333_3333;
|
|
|
320 shl EDX, 2;
|
|
|
321 or EAX, EDX;
|
|
|
322 mov EDX, EAX;
|
|
|
323 shr EAX, 4;
|
|
|
324 and EDX, 0x0f0f_0f0f;
|
|
|
325 and EAX, 0x0f0f_0f0f;
|
|
|
326 shl EDX, 4;
|
|
|
327 or EAX, EDX;
|
|
|
328 bswap EAX;
|
|
|
329 }
|
|
|
330 }
|
|
|
331 else
|
|
|
332 {
|
|
|
333 // swap odd and even bits
|
|
|
334 x = ((x >> 1) & 0x5555_5555) | ((x & 0x5555_5555) << 1);
|
|
|
335 // swap consecutive pairs
|
|
|
336 x = ((x >> 2) & 0x3333_3333) | ((x & 0x3333_3333) << 2);
|
|
|
337 // swap nibbles
|
|
|
338 x = ((x >> 4) & 0x0F0F_0F0F) | ((x & 0x0F0F_0F0F) << 4);
|
|
|
339 // swap bytes
|
|
|
340 x = ((x >> 8) & 0x00FF_00FF) | ((x & 0x00FF_00FF) << 8);
|
|
|
341 // swap 2-byte long pairs
|
|
|
342 x = ( x >> 16 ) | ( x << 16);
|
|
|
343 return x;
|
|
|
344
|
|
|
345 }
|
|
|
346 }
|
|
|
347
|
|
|
348
|
|
|
349 debug( UnitTest )
|
|
|
350 {
|
|
|
351 unittest
|
|
|
352 {
|
|
|
353 assert( bitswap( 0x8000_0100 ) == 0x0080_0001 );
|
|
|
354 }
|
|
|
355 }
|
