title: CRC bit-order confusion
body: <p>I'm calculating a CCITT CRC-16 bit by bit. I do this that way because it's a prototype that later should be ported to VHDL and end up in hardware to check a serial bit-stream.</p>
  
  <p>On the net I found a single bit CRC-16 update step code. Wrote a test-program and it works. Except for one strange thing: I have to feed the bits of a byte from lowest to highest bit. If I do it this way, I get correct results.</p>
  
  <p>In the CCITT definition of CRC-16 the bits should be feed highest bit to lowest bit though. The data-stream that I want to calculate the CRC from comes in this format as well, so my current code is kind of useless for me.</p>
  
  <p>I'm confused. I would have not expected that feeding the bits the wrong way around could work at all.</p>
  
  <p><strong>Question: Why is it possible that a CRC can be written to take the data in two different bit-orders, and how do I transform my single bit update code that it accepts the data MSB first?</strong></p>
  
  <p>For reference, here is the relevant code. Initialization and the final check have been removed to keep the example short:</p>
  
  <pre><code>typedef unsigned char bit;
  
  void update_crc_single_bit (bit * crc, bit data)
  {
    // update CRC for a single bit:
    bit temp[16];
    int i;
  
    temp[0] = data ^ crc[15]; 
    temp[1] = crc[0]; 
    temp[2] = crc[1]; 
    temp[3] = crc[2]; 
    temp[4] = crc[3]; 
    temp[5] = data ^ crc[4] ^ crc[15]; 
    temp[6] = crc[5]; 
    temp[7] = crc[6]; 
    temp[8] = crc[7]; 
    temp[9] = crc[8]; 
    temp[10] = crc[9]; 
    temp[11] = crc[10]; 
    temp[12] = data ^ crc[11] ^ crc[15]; 
    temp[13] = crc[12]; 
    temp[14] = crc[13]; 
    temp[15] = crc[14];
  
    for (i=0; i&lt;16; i++)
      crc[i] = temp[i];
  }
  
  void update_crc_byte (bit * crc, unsigned char data)
  {
    int j;
    // calculate CRC lowest bit first
    for (j=0; j&lt;8; j++)
    {
      bit b = (data&gt;&gt;j)&amp;1;
      update_crc_single_bit(crc, b);
    }
  }
  </code></pre>
  
  <p>Edit: Since there is some confusion here: I have to compute the CRC bit by bit, and for each byte MSB first. I can't simply store the bits because the code shown above is a prototype for something that will end up in hardware (without memory).</p>
  
  <p>The code shown above generates the correct result if I feed in a bit-stream in the following order (shown is the index of the received bit. Each byte gets transmitted MSB first):</p>
  
  <pre><code>|- first byte -|-   second byte     -|-  third byte 
  7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8,....
  </code></pre>
  
  <p>I need the single update loop to be transformed that it generates the same CRC using natural order (e.g. as received):</p>
  
  <pre><code>|- first byte -|-   second byte     -|-  third byte 
  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,.... 
  </code></pre>