tango.core.BitManip source code

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 +/