Mercurial > projects > ldc

comparison druntime/src/common/core/bitop.d @ 1458:e0b2d67cfe7c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added druntime (this should be removed once it works).
author Robert Clipsham <robert@octarineparrot.com>
date Tue, 02 Jun 2009 17:43:06 +0100
parents
children
comparison
equal deleted inserted replaced
1456:7b218ec1044f 1458:e0b2d67cfe7c
1 /**
2 * This module contains a collection of bit-level operations.
3 *
4 * Copyright: Copyright Don Clugston 2005 - 2009.
5 * License: <a href="http://www.boost.org/LICENSE_1_0.txt>Boost License 1.0</a>.
6 * Authors: Don Clugston, Sean Kelly, Walter Bright
7 *
8 * Copyright Don Clugston 2005 - 2009.
9 * Distributed under the Boost Software License, Version 1.0.
10 * (See accompanying file LICENSE_1_0.txt or copy at
11 * http://www.boost.org/LICENSE_1_0.txt)
12 */
13 module core.bitop;
14
15
16 version( D_Ddoc )
17 {
18 /**
19 * Scans the bits in v starting with bit 0, looking
20 * for the first set bit.
21 * Returns:
22 * The bit number of the first bit set.
23 * The return value is undefined if v is zero.
24 */
25 int bsf( uint v );
26
27 /**
28 * Scans the bits in v from the most significant bit
29 * to the least significant bit, looking
30 * for the first set bit.
31 * Returns:
32 * The bit number of the first bit set.
33 * The return value is undefined if v is zero.
34 * Example:
35 * ---
36 * import core.bitop;
37 *
38 * int main()
39 * {
40 * uint v;
41 * int x;
42 *
43 * v = 0x21;
44 * x = bsf(v);
45 * printf("bsf(x%x) = %d\n", v, x);
46 * x = bsr(v);
47 * printf("bsr(x%x) = %d\n", v, x);
48 * return 0;
49 * }
50 * ---
51 * Output:
52 * bsf(x21) = 0<br>
53 * bsr(x21) = 5
54 */
55 int bsr( uint v );
56
57
58 /**
59 * Tests the bit.
60 */
61 int bt( uint* p, uint bitnum );
62
63
64 /**
65 * Tests and complements the bit.
66 */
67 int btc( uint* p, uint bitnum );
68
69
70 /**
71 * Tests and resets (sets to 0) the bit.
72 */
73 int btr( uint* p, uint bitnum );
74
75
76 /**
77 * Tests and sets the bit.
78 * Params:
79 * p = a non-NULL pointer to an array of uints.
80 * index = a bit number, starting with bit 0 of p[0],
81 * and progressing. It addresses bits like the expression:
82 ---
83 p[index / (uint.sizeof*8)] & (1 << (index & ((uint.sizeof*8) - 1)))
84 ---
85 * Returns:
86 * A non-zero value if the bit was set, and a zero
87 * if it was clear.
88 *
89 * Example:
90 * ---
91 import core.bitop;
92
93 int main()
94 {
95 uint array[2];
96
97 array[0] = 2;
98 array[1] = 0x100;
99
100 printf("btc(array, 35) = %d\n", <b>btc</b>(array, 35));
101 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
102
103 printf("btc(array, 35) = %d\n", <b>btc</b>(array, 35));
104 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
105
106 printf("bts(array, 35) = %d\n", <b>bts</b>(array, 35));
107 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
108
109 printf("btr(array, 35) = %d\n", <b>btr</b>(array, 35));
110 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
111
112 printf("bt(array, 1) = %d\n", <b>bt</b>(array, 1));
113 printf("array = [0]:x%x, [1]:x%x\n", array[0], array[1]);
114
115 return 0;
116 }
117 * ---
118 * Output:
119 <pre>
120 btc(array, 35) = 0
121 array = [0]:x2, [1]:x108
122 btc(array, 35) = -1
123 array = [0]:x2, [1]:x100
124 bts(array, 35) = 0
125 array = [0]:x2, [1]:x108
126 btr(array, 35) = -1
127 array = [0]:x2, [1]:x100
128 bt(array, 1) = -1
129 array = [0]:x2, [1]:x100
130 </pre>
131 */
132 int bts( uint* p, uint bitnum );
133
134
135 /**
136 * Swaps bytes in a 4 byte uint end-to-end, i.e. byte 0 becomes
137 * byte 3, byte 1 becomes byte 2, byte 2 becomes byte 1, byte 3
138 * becomes byte 0.
139 */
140 uint bswap( uint v );
141
142
143 /**
144 * Reads I/O port at port_address.
145 */
146 ubyte inp( uint port_address );
147
148
149 /**
150 * ditto
151 */
152 ushort inpw( uint port_address );
153
154
155 /**
156 * ditto
157 */
158 uint inpl( uint port_address );
159
160
161 /**
162 * Writes and returns value to I/O port at port_address.
163 */
164 ubyte outp( uint port_address, ubyte value );
165
166
167 /**
168 * ditto
169 */
170 ushort outpw( uint port_address, ushort value );
171
172
173 /**
174 * ditto
175 */
176 uint outpl( uint port_address, uint value );
177 }
178 else
179 {
180 public import std.intrinsic;
181 }
182
183
184 /**
185 * Calculates the number of set bits in a 32-bit integer.
186 */
187 int popcnt( uint x )
188 {
189 // Avoid branches, and the potential for cache misses which
190 // could be incurred with a table lookup.
191
192 // We need to mask alternate bits to prevent the
193 // sum from overflowing.
194 // add neighbouring bits. Each bit is 0 or 1.
195 x = x - ((x>>1) & 0x5555_5555);
196 // now each two bits of x is a number 00,01 or 10.
197 // now add neighbouring pairs
198 x = ((x&0xCCCC_CCCC)>>2) + (x&0x3333_3333);
199 // now each nibble holds 0000-0100. Adding them won't
200 // overflow any more, so we don't need to mask any more
201
202 // Now add the nibbles, then the bytes, then the words
203 // We still need to mask to prevent double-counting.
204 // Note that if we used a rotate instead of a shift, we
205 // wouldn't need the masks, and could just divide the sum
206 // by 8 to account for the double-counting.
207 // On some CPUs, it may be faster to perform a multiply.
208
209 x += (x>>4);
210 x &= 0x0F0F_0F0F;
211 x += (x>>8);
212 x &= 0x00FF_00FF;
213 x += (x>>16);
214 x &= 0xFFFF;
215 return x;
216 }
217
218
219 debug( UnitTest )
220 {
221 unittest
222 {
223 assert( popcnt( 0 ) == 0 );
224 assert( popcnt( 7 ) == 3 );
225 assert( popcnt( 0xAA )== 4 );
226 assert( popcnt( 0x8421_1248 ) == 8 );
227 assert( popcnt( 0xFFFF_FFFF ) == 32 );
228 assert( popcnt( 0xCCCC_CCCC ) == 16 );
229 assert( popcnt( 0x7777_7777 ) == 24 );
230 }
231 }
232
233
234 /**
235 * Reverses the order of bits in a 32-bit integer.
236 */
237 uint bitswap( uint x )
238 {
239
240 version( D_InlineAsm_X86 )
241 {
242 asm
243 {
244 // Author: Tiago Gasiba.
245 mov EDX, EAX;
246 shr EAX, 1;
247 and EDX, 0x5555_5555;
248 and EAX, 0x5555_5555;
249 shl EDX, 1;
250 or EAX, EDX;
251 mov EDX, EAX;
252 shr EAX, 2;
253 and EDX, 0x3333_3333;
254 and EAX, 0x3333_3333;
255 shl EDX, 2;
256 or EAX, EDX;
257 mov EDX, EAX;
258 shr EAX, 4;
259 and EDX, 0x0f0f_0f0f;
260 and EAX, 0x0f0f_0f0f;
261 shl EDX, 4;
262 or EAX, EDX;
263 bswap EAX;
264 }
265 }
266 else
267 {
268 // swap odd and even bits
269 x = ((x >> 1) & 0x5555_5555) | ((x & 0x5555_5555) << 1);
270 // swap consecutive pairs
271 x = ((x >> 2) & 0x3333_3333) | ((x & 0x3333_3333) << 2);
272 // swap nibbles
273 x = ((x >> 4) & 0x0F0F_0F0F) | ((x & 0x0F0F_0F0F) << 4);
274 // swap bytes
275 x = ((x >> 8) & 0x00FF_00FF) | ((x & 0x00FF_00FF) << 8);
276 // swap 2-byte long pairs
277 x = ( x >> 16 ) | ( x << 16);
278 return x;
279
280 }
281 }
282
283
284 debug( UnitTest )
285 {
286 unittest
287 {
288 assert( bitswap( 0x8000_0100 ) == 0x0080_0001 );
289 }
290 }