import/core/bitmanip.di

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