src/core/bitmanip.d

   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 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 }