title: Implementing SSE 4.2's CRC32C in software
body: <p>So I have a design which incorporates CRC32C checksums to ensure data hasn't been damaged. I decided to use CRC32C because I can have both a software version and a hardware-accelerated version if the computer the software runs on supports SSE 4.2</p>
  
  <p>I'm going by Intel's developer manual (vol 2A), which seems to provide the algorithm behind the <code>crc32</code> instruction. However, I'm having little luck. Intel's developer guide says the following:</p>
  
  <pre><code>BIT_REFLECT32: DEST[31-0] = SRC[0-31]
  MOD2: Remainder from Polynomial division modulus 2
  
  TEMP1[31-0] &lt;- BIT_REFLECT(SRC[31-0])
  TEMP2[31-0] &lt;- BIT_REFLECT(DEST[31-0])
  TEMP3[63-0] &lt;- TEMP1[31-0] &lt;&lt; 32
  TEMP4[63-0] &lt;- TEMP2[31-0] &lt;&lt; 32
  TEMP5[63-0] &lt;- TEMP3[63-0] XOR TEMP4[63-0]
  TEMP6[31-0] &lt;- TEMP5[63-0] MOD2 0x11EDC6F41
  DEST[31-0]  &lt;- BIT_REFLECT(TEMP6[31-0])
  </code></pre>
  
  <p>Now, as far as I can tell, I've done everything up to the line starting <code>TEMP6</code> correctly, but I think I may be either misunderstanding the polynomial division, or implementing it incorrectly. If my understanding is correct, <code>1 / 1 mod 2 = 1</code>, <code>0 / 1 mod 2 = 0</code>, and both divides-by-zero are undefined.</p>
  
  <p>What I don't understand is how binary division with 64-bit and 33-bit operands will work. If <code>SRC</code> is <code>0x00000000</code>, and <code>DEST</code> is <code>0xFFFFFFFF</code>, <code>TEMP5[63-32]</code> will be all set bits, while <code>TEMP5[31-0]</code> will be all unset bits.</p>
  
  <p>If I was to use the bits from <code>TEMP5</code> as the numerator, there would be 30 divisions by zero as the polynomial <code>11EDC6F41</code> is only 33 bits long (and so converting it to a 64-bit unsigned integer leaves the top 30 bits unset), and so the denominator is unset for 30 bits.</p>
  
  <p>However, if I was to use the polynomial as the numerator, the bottom 32 bits of <code>TEMP5</code> are unset, resulting in divides by zero there, and the top 30 bits of the result would be zero, as the top 30 bits of the numerator would be zero, as <code>0 / 1 mod 2 = 0</code>.</p>
  
  <p>Am I misunderstanding how this works? Just plain missing something? Or has Intel left out some crucial step in their documentation?</p>
  
  <p>The reason I went to Intel's developer guide for what appeared to be the algorithm they used is because they used a 33-bit polynomial, and I wanted to make outputs identical, which didn't happen when I used the 32-bit polynomial <code>1EDC6F41</code> (show below).</p>
  
  <pre><code>uint32_t poly = 0x1EDC6F41, sres, crcTable[256], data = 0x00000000;
  
  for (n = 0; n &lt; 256; n++) {
      sres = n;
      for (k = 0; k &lt; 8; k++)
          sres = (sres &amp; 1) == 1 ? poly ^ (sres &gt;&gt; 1) : (sres &gt;&gt; 1);
      crcTable[n] = sres;
  }
  sres = 0xFFFFFFFF;
  
  for (n = 0; n &lt; 4; n++) {
      sres = crcTable[(sres ^ data) &amp; 0xFF] ^ (sres &gt;&gt; 8);
  }
  </code></pre>
  
  <p>The above code produces <code>4138093821</code> as an output, and the <code>crc32</code> opcode produces <code>2346497208</code> using the input <code>0x00000000</code>.</p>
  
  <p>Sorry if this is badly written or incomprehensible in places, it is rather late for me.</p>