title: Which CRC Alogrithim is this? How to improve?
body: <p>I have a telemetry stream that is passed through a hardware CRC generator appending the CRC to the end of each telemetry frame.  Now I am trying to make something to verify the hardware generated CRC.  I have old legacy code (see below) that computes the correct CRC (verified multiple times).  However it is slow since each telemetry frame is 300+ bytes and there can be upwards of 10,000,000+ frames to process.</p>
  
  <p>After some research I found some literature pointing me to a table driven approach.  The legacy method uses a Poly of 0x8005, reverses the bit order of each byte before processing, and initializes the CRC to zero. However, after building tables for that poly with reversed and non-reversed input and just trying to work through even the first byte of data (0x10) I can not get anything to match what the legacy method is generating.</p>
  
  <p>Inside the calcCRC16 function (below) the existing method checks the LSB where others seem to check the MSB ... and the bit shifts are to the right where other examples I have seen are to the left.  I am getting lost in why this is especially since the bit order is swapped before passing it to this function.  I have tried on-line calculators &amp; manually doing the look-ups in tables switching the poly from 8005 to A001(reversed), normal and reversed input bytes, and every combination I can think of but can't get any table approach to match the legacy code which I know to be correct for our hardware implementation.</p>
  
  <p>Can anyone help me out if I am missing something obvious?  How would you go about creating a table based approach to create the same output?  I am a novice at C++ and not really familiar with CRC generation and could be overlooking something fundamental.  Sample code and output which was verified against the hardware CRC follows:</p>
  
  <p><strong>Sample Code:</strong> I just hard coded a few bytes out of a know telemetry stream as an example</p>
  
  <pre><code>/** ********************************************************************************
  * TEST CRC METHOD
  *******************************************************************************/
  #include &lt;iostream&gt;
  
  using namespace std;
  
  unsigned char swapBits(unsigned char d);
  void calcCRC16(unsigned int *CRCVal, unsigned char value);
  
  /** **************************************************************************
  *   @function   main
  *   TEST CRC METHOd
  *******************************************************************************/
  int main(int argc, char* argv[])
  {
      short          dataLength = 5;
      unsigned int   givenCrc;
      unsigned int   calcCrc;    
      unsigned char byte[] = {0x10,0xbb,0x42,0x4d,0xfd};
  
      /* Init CRC. */
      calcCrc = 0;
      cout &lt;&lt; "Inital CRC = " &lt;&lt; hex &lt;&lt; calcCrc &lt;&lt; "\n";
      /* Read frame data. */
      for (int i = 0; i &lt; dataLength; i++)
      {
          cout &lt;&lt; "byte    = " &lt;&lt; hex &lt;&lt; static_cast&lt;int16_t&gt;(byte[i]) &lt;&lt; " ";
          calcCRC16(&amp;calcCrc, swapBits(byte[i]));
          cout &lt;&lt; "calcCRC = " &lt;&lt; hex &lt;&lt; calcCrc &lt;&lt; "\n";
       }
  }
  
  /** ********************************************************************
  *   @function   swapBits
  *   Swaps the bits so they match the order sent to CRC Gen Hardware
  ************************************************************************/
  unsigned char swapBits(unsigned char d)
  {
      unsigned char t = 0;
      int i           = 0;
      int n           = 0x80;
  
      for(i=0x01; i&lt;0x100; i=i&lt;&lt;1)
      {
          if (d &amp; i)
          {
              t|=n;
          }
          n=n&gt;&gt;1;
      }
      return t;
  }
  
  /** ********************************************************************
  *   @function   calcCRC16
  *   WORKING METHOD VERIFIED AGAINST CRC HARDWARE
  ************************************************************************/
  void calcCRC16(unsigned int *CRCVal, unsigned char value)
  {
      unsigned char lsb;
      unsigned char bcnt;
  
      for (bcnt=0 ; bcnt&lt;8 ; bcnt++)
      {
          lsb = (value ^ *CRCVal) &amp; 0x01;
          *CRCVal &gt;&gt;= 1;
          value &gt;&gt;= 1;
          if (lsb != 0)
          {
              *CRCVal ^= 0x8005;
          }
      }
  }
  </code></pre>
  
  <p><strong>Output:</strong><br>
      Inital CRC = 0<br>
      byte    = 10 calcCRC = b804<br>
      byte    = bb calcCRC = 1fb8<br>
      byte    = 42 calcCRC = 461d<br>
      byte    = 4d calcCRC = 3d47<br>
      byte    = fd calcCRC = 683e </p>