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