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