Mercurial > projects > ldc

comparison tango/lib/common/tango/core/BitManip.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children f5ca6bbbf1d7
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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 }
174 else
175 {
176 public import std.intrinsic;
177 }
178
179
180 /**
181 * Calculates the number of set bits in a 32-bit integer.
182 */
183 int popcnt( uint x )
184 {
185 // Avoid branches, and the potential for cache misses which
186 // could be incurred with a table lookup.
187
188 // We need to mask alternate bits to prevent the
189 // sum from overflowing.
190 // add neighbouring bits. Each bit is 0 or 1.
191 x = x - ((x>>1) & 0x5555_5555);
192 // now each two bits of x is a number 00,01 or 10.
193 // now add neighbouring pairs
194 x = ((x&0xCCCC_CCCC)>>2) + (x&0x3333_3333);
195 // now each nibble holds 0000-0100. Adding them won't
196 // overflow any more, so we don't need to mask any more
197
198 // Now add the nibbles, then the bytes, then the words
199 // We still need to mask to prevent double-counting.
200 // Note that if we used a rotate instead of a shift, we
201 // wouldn't need the masks, and could just divide the sum
202 // by 8 to account for the double-counting.
203 // On some CPUs, it may be faster to perform a multiply.
204
205 x += (x>>4);
206 x &= 0x0F0F_0F0F;
207 x += (x>>8);
208 x &= 0x00FF_00FF;
209 x += (x>>16);
210 x &= 0xFFFF;
211 return x;
212 }
213
214
215 debug( UnitTest )
216 {
217 unittest
218 {
219 assert( popcnt( 0 ) == 0 );
220 assert( popcnt( 7 ) == 3 );
221 assert( popcnt( 0xAA )== 4 );
222 assert( popcnt( 0x8421_1248 ) == 8 );
223 assert( popcnt( 0xFFFF_FFFF ) == 32 );
224 assert( popcnt( 0xCCCC_CCCC ) == 16 );
225 assert( popcnt( 0x7777_7777 ) == 24 );
226 }
227 }
228
229
230 /**
231 * Reverses the order of bits in a 32-bit integer.
232 */
233 uint bitswap( uint x )
234 {
235
236 version( D_InlineAsm_X86 )
237 {
238 asm
239 {
240 // Author: Tiago Gasiba.
241 mov EDX, EAX;
242 shr EAX, 1;
243 and EDX, 0x5555_5555;
244 and EAX, 0x5555_5555;
245 shl EDX, 1;
246 or EAX, EDX;
247 mov EDX, EAX;
248 shr EAX, 2;
249 and EDX, 0x3333_3333;
250 and EAX, 0x3333_3333;
251 shl EDX, 2;
252 or EAX, EDX;
253 mov EDX, EAX;
254 shr EAX, 4;
255 and EDX, 0x0f0f_0f0f;
256 and EAX, 0x0f0f_0f0f;
257 shl EDX, 4;
258 or EAX, EDX;
259 bswap EAX;
260 }
261 }
262 else
263 {
264 // swap odd and even bits
265 x = ((x >> 1) & 0x5555_5555) | ((x & 0x5555_5555) << 1);
266 // swap consecutive pairs
267 x = ((x >> 2) & 0x3333_3333) | ((x & 0x3333_3333) << 2);
268 // swap nibbles
269 x = ((x >> 4) & 0x0F0F_0F0F) | ((x & 0x0F0F_0F0F) << 4);
270 // swap bytes
271 x = ((x >> 8) & 0x00FF_00FF) | ((x & 0x00FF_00FF) << 8);
272 // swap 2-byte long pairs
273 x = ( x >> 16 ) | ( x << 16);
274 return x;
275
276 }
277 }
278
279
280 debug( UnitTest )
281 {
282 unittest
283 {
284 assert( bitswap( 0x8000_0100 ) == 0x0080_0001 );
285 }
286 }