title: CRC32 calculation with CRC hash at the beginning of the message in C
body: <p>I need to calculate CRC of the message and put it <strong>at the beginning</strong> of this message, so that the final CRC of the message with 'prepended' patch bytes equals 0. I was able to do this very easily with the help of few articles, but not for my specific parameters. The thing is that I have to use a given CRC32 algorithm which calculates the CRC of the memory block, but I don't have that 'reverse' algorithm that calculates those 4 patch bytes/'kind of CRC'. Parameters of the given CRC32 algorithm are:  </p>
  
  <ul>
  <li>Polynomial: 0x04C11DB7  </li>
  <li>Endianess: big-endian  </li>
  <li>Initial value: 0xFFFFFFFF  </li>
  <li>Reflected: false  </li>
  <li>XOR out with: 0L  </li>
  <li>Test stream: 0x0123, 0x4567, 0x89AB, 0xCDEF results in CRC = 0x612793C3  </li>
  </ul>
  
  <p>The code to calculate the CRC (half-byte, table-driven, I hope data type definitions are self-explanatory):</p>
  
  <pre><code>uint32 crc32tab(uint16* data, uint32 len, uint32 crc)
  {
      uint8 nibble;
      int i;
      while(len--)
      {
          for(i = 3; i &gt;= 0; i--)
          {
              nibble = (*data &gt;&gt; i*4) &amp; 0x0F;
              crc = ((crc &lt;&lt; 4) | nibble) ^ tab[crc &gt;&gt; 28];
          }
          data++;
      }
  
      return crc;
  }
  </code></pre>
  
  <p>The table needed is (I thougth the short [16] table should contain every 16th element from the large [256] table, but this table contains actually <strong>first</strong> 16 elements, but that's how it was provided to me):  </p>
  
  <pre><code>static const uint32 tab[16]=
  {
      0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
      0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
      0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
      0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
  };  
  </code></pre>
  
  <p>I modified the code so it's not so long, but the functionality stays the same. The problem is that this forward CRC calculation looks more like backward/reverse CRC calc.<br>
  I've spent almost a week trying to find out the correct polynomial/algorithm/table combination, but with no luck. If it helps, I came up with bit-wise algorithm that corresponds to table-driven code above, although that was not so hard after all:  </p>
  
  <pre><code>uint32 crc32(uint16* data, uint32 len, uint32 crc)
  {
      uint32 i;
      while(len--)
      {
          for(i = 0; i &lt; 16; i++)
          {
              // #define POLY 0x04C11DB7
              crc = (crc &lt;&lt; 1) ^ (((crc ^ *data) &amp; 0x80000000) ? POLY : 0);
          }
          crc ^= *data++;
      }
  
      return crc;
  }
  </code></pre>
  
  <p>Here are expected results - first 2 16-bit words make the needed unknown CRC and the rest is the known data itself (by feeding these examples to provided algorithm, the result is 0).  </p>
  
  <pre><code>{0x3288, 0xD244, 0xCDEF, 0x89AB, 0x4567, 0x0123}
  {0xC704, 0xDD7B, 0x0000} - append as many zeros as you like, the result is the same
  {0xCEBD, 0x1ADD, 0xFFFF}
  {0x81AB, 0xB932, 0xFFFF, 0xFFFF}
  {0x0857, 0x0465, 0x0000, 0x0123}
  {0x1583, 0xD959, 0x0123}
     ^        ^
     |        |
     unknown bytes that I need to calculate
  </code></pre>
  
  <p>I think testing this on 0xFFFF or 0x0000 words is convenient because the direction of calculation and endianess is not important (I hope :D). So be careful to use other test bytes, because the direction of calculation is quite devious :D. Also you can see that by feeding only zeros to the algorithm (both forward and backward), the result is so-called residue (0xC704DD7B), that may be helpful.  </p>
  
  <p>So...I wrote at least 10 different functions (bite-wise, tables, combination of polynomials etc.) trying to solve this, but with no luck. I give you here the function in which I put my hopes into. It's 'reversed' algorithm of the table-driven one above, with different table of course. The problem is that the only correct CRC I get from that is with all 0s message and that's not so unexpected. Also I have written the reversed implementation of the bit-wise algorithm (reversed shifts, etc.), but that one returns only the first byte correctly.<br>
  Here is the table-driven one, pointer to <em>data</em> should point to the last element of the message and <em>crc</em> input should be the requested crc (0s for the whole message or you can maybe take another approach - that the last 4 bytes of message are the CRC you are looking for: <a href="https://stackoverflow.com/questions/28714815/calculating-crc-initial-value-instead-of-appending-the-crc-to-payload">Calculating CRC initial value instead of appending the CRC to payload</a>) :</p>
  
  <pre><code>uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc)
  {
      uint8 nibble;
      int i;
      while(len--)
      {
          for(i = 0; i &lt; 4; i++)
          {
              nibble = (*data &gt;&gt; i*4) &amp; 0x0F;
              crc = (crc &gt;&gt; 4) ^ revtab[((crc ^ nibble) &amp; 0x0F)];
          }
          data--;
       }
  
       return reverse(crc); //reverse() flips all bits around center (MSB &lt;-&gt; LSB ...) 
  }
  </code></pre>
  
  <p>The table, which I hope is 'the chosen one':</p>
  
  <pre><code>static const uint32 revtab[16]=
  {
      0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
      0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
      0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
      0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C
  };
  </code></pre>
  
  <p>As you can see, this algorithm has some perks which make me run in circles and I think I'm maybe on the right track, but I'm missing something. I hope an extra pair of eyes will see what I can not. I'm sorry for the long post (no potato :D), but I think all of that explanation was neccessary. Thank you in advance for insight or advice.</p>