Mercurial > projects > ldc

comparison druntime/import/core/bitmanip.di @ 760:6f33b427bfd1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Seems like hg ignores .di files, so I missed a bunch of stuff. complete druntime should be there now :)
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Wed, 12 Nov 2008 00:19:18 +0100
parents
children
comparison
equal deleted inserted replaced
759:d3eb054172f9 760:6f33b427bfd1
1 /**
2 * This module contains a collection of bit-level operations.
3 *
4 * Copyright: Copyright (c) 2005-2008, The D Runtime Project
5 * License: BSD Style, see LICENSE
6 * Authors: Walter Bright, Don Clugston, Sean Kelly
7 */
8 module 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 bitmanip;
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 bitmanip;
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 /**
216 * Reverses the order of bits in a 32-bit integer.
217 */
218 uint bitswap( uint x )
219 {
220
221 version( D_InlineAsm_X86 )
222 {
223 asm
224 {
225 // Author: Tiago Gasiba.
226 mov EDX, EAX;
227 shr EAX, 1;
228 and EDX, 0x5555_5555;
229 and EAX, 0x5555_5555;
230 shl EDX, 1;
231 or EAX, EDX;
232 mov EDX, EAX;
233 shr EAX, 2;
234 and EDX, 0x3333_3333;
235 and EAX, 0x3333_3333;
236 shl EDX, 2;
237 or EAX, EDX;
238 mov EDX, EAX;
239 shr EAX, 4;
240 and EDX, 0x0f0f_0f0f;
241 and EAX, 0x0f0f_0f0f;
242 shl EDX, 4;
243 or EAX, EDX;
244 bswap EAX;
245 }
246 }
247 else
248 {
249 // swap odd and even bits
250 x = ((x >> 1) & 0x5555_5555) | ((x & 0x5555_5555) << 1);
251 // swap consecutive pairs
252 x = ((x >> 2) & 0x3333_3333) | ((x & 0x3333_3333) << 2);
253 // swap nibbles
254 x = ((x >> 4) & 0x0F0F_0F0F) | ((x & 0x0F0F_0F0F) << 4);
255 // swap bytes
256 x = ((x >> 8) & 0x00FF_00FF) | ((x & 0x00FF_00FF) << 8);
257 // swap 2-byte long pairs
258 x = ( x >> 16 ) | ( x << 16);
259 return x;
260
261 }
262 }