Assembly Language Programming

June 10, 2011

CRC-16 Calculator

Javascript CRC-16 Calculator

Here is a Javascript CRC-16 calculator I have written to demonstrate the different techniques that can be used to implement the CRC calculation in code.

A CRC is calculated by dividing a generator polynomial into the message. The long division process is done according to the mathemetics of polynomial division mod 2, so the conventional long division process is not used. Instead the various left shifts of the generator polynomial bit pattern are simply XORed into the message bit pattern.

For CRC-16 the generator polynomial is 17 bits in length. The msb (bit 16) and lsb (bit 0) are always 1. Since the msb is always 1, when the polynomial is written in hex form it is the convention just to show the lower 16 bits. For example the IBM polynomial 18005 is usually just written as 8005. My program follows this convention.

Long Division Method

To visualise the long division process, imagine the message written as a binary number (or bit pattern). The leading bits in the message will be the most significant (or leftmost) bits in the bit pattern. The long division process is begun by left shifting the 17 bit polynomial such that the msb of the polynomial is aligned with the msb of the message. The polynomial is XORed into the message only if the msb of the message is 1 and as a result the msb of the message will be cleared. The polynomial is then right shifted by 1 bit and the process repeats. In this way every bit in the message is tested against the polynomial, with the polynomial being XORed into the message if the message bit that is aligned with the msb of the shifted polynomial is 1. Of course the bits in the message will change as the polynomial is XORed into it, and all of the bits to the left of the current shifted polynomial will become 0.

The remainder from this division process is the CRC. To capture the remainder, 16 zero bits are appended to the right of the message bit pattern. When the long division process reaches the point where the msb of the polynomial is aligned with the lsb (the rightmost bit) of the message and the final XOR is done (only if the lsb was 1) these 16 bits will hold the CRC value.

Register Method

If the CRC is being computed on a machine where there is a lot of memory and processing power available, then it is easy to implement the above long division method. First create arrays for each of the message and polynomial. Then shift and XOR the polynomial array into the message array as described above.

However on an embedded system where the memory and processing power is limited, this approach is not feasible. This leads to the register method for computing CRCs.

Even though the polynomial for 16 bit CRC is 17 bits in length, a CRC-16 calculation can be done with a 16 bit register. There are three factors that make this possible. One, when an operation is performed on a register that results in a carry from the msb of the data contained in the register, the CPU will capture and store the carry bit. Two, each iteration of the long division process only effects 17 bits within the message. Three, all bits in the message that are to the left of the shifted polynomial are cleared and will not be a part of the final CRC value.

The carry bit together with the 16 bit register gives 17 bits. This bit pattern can be visualised as aligning with the 17 bit polynomial, with the msb of the polynomial aligning with the processor carry bit. We know that the msb of the polynomial is always 1 and the effect it will have if the carry bit is also 1. Therefore, there is no need to store the msb of the polynomial and the remaining bits of the polynomial can be stored in a 16 bit register.

Therefore, a 16 bit CRC can be calculated by shifting the message bits through a register. Each bit that is shifted out of the register and into the processor carry bit is tested. If it is 1, the lower 16 bits of the polynomial are XORed into the register containing the message bits. Once the bit that has just been shifted out of the register has been tested and acted upon, it is no longer needed and can just be discarded. The process works like this:

- Initialise the CRC register: CRC = the 16 leftmost bits of M.

(1) Left shift CRC: CRC = CRC << 1

    - the processor carry bit now stores the msb: carry = msb(CRC)

(2) Left shift the next bit from M into CRC: CRC = CRC + bit

(3) Test the carry bit and XOR if 1:

    - if(carry == 1) CRC = CRC ^ Poly

(4) Repeat from (1) until the last bit from M has been shifted through the register.

    - The register now contains the CRC.

    - The padding bits are used to push the last message bit completely through the 
      register.

Table Method

The table method allows a processor to process a message byte by byte to calculate the CRC. This is a faster and more efficient way than processing a message bit by bit.

The table method is derived as follows. Visualise the long division process above as applied to any 3 bytes within the message. If each bit in the first (leftmost) byte is tested against the polynomial and an XOR done whenever one of the bits is 1, then a bit pattern can be built up by the combined XOR of the shifted polynomials. This bit pattern will have a length of 24 bits and therefore effect all 3 of the bytes being considered. We already know that when this bit pattern is XORed with the 3 bytes, that the first byte will just becomes zero. So the upper 8 bits of the bit pattern can just be discarded. What is left is the 16 bit pattern that will be XORed with bytes 2 and 3. For any given byte, this 16 bit pattern will always be the same. Therefore a table of these values can be built. The index for this table will be the byte values from 0 to 255. With this table, the long division process can be done byte by byte:

- Let T[byte] = the 16 bit value as described above.

- Let the bytes B(i) B(i+1) B(i+2) B(i+3) be a portion of a message.

- B(i) is used as the table index to get T[B(i)].

- B(i) is set to zero and T[B(i)] is XORed into the message:

  B(i+1)' B(i+2)' B(i+3) ...

- B(i+1)' is used as the table index to get T[B(i+1)'].

- B(i+1)' is set to zero and T[B(i+1)'] is XORed into the message:

  B(i+2)'' B(i+3)' ...

- And so on ...

The register method to calculate a CRC can be significantly enhanced if a table is used:

- Initialise the CRC register: CRC = the 16 leftmost bits of M.

(1) Using the upper byte from the register B(u), get T[B(u)].

(2) Left shift the register by 1 byte. B(u) is shifted out of the register.

(3) Load the next message byte into the lower byte of the register.

(4) XOR T[B(u)] into the register.

(5) Repeat from (1) until the last message byte has travelled 
    through the register.

  - The 2 padding bytes are used to push the last message byte completely through 
    the register.

If the message is a hexadecimal number that potentially contains an odd number of digits, the table method can be adapted to handle this. The message is just processed digit by digit (or nibble by nibble) using a table that is indexed by a 4 bit value. The table values will still be 16 bits however (for CRC-16).

A message could even be processed in blocks of 2 bytes, but the table needed for this would have 65,536 elements, which would require over 130 KB of memory.

Direct Table Method

There is a further refinement to the table method known as the direct table method. It works like this:

- Initialise the CRC register to zero: CRC = 0

- Get the first message byte.

(1) Get the upper byte from the register B(u).

(2) XOR B(u) with the message byte B(M) to get the table index.

(3) Left shift the register by 1 byte. B(u) is shifted out of the register.

    - The lower byte becomes zero.

(4) XOR T[B(u) xor B(M)] into the register.

(5) Repeat from (1) until the last message byte has been used.

    - The padding bits are not needed.

In this method the message bytes don’t travel through the register at all. They are XORed directly with the upper byte of the register to obtain a table index. Most implementations of CRC use this method, since it is the fastest and most efficient out of all the methods.

The relationship between the direct table method and the more clearcut long division and table methods is far from obvious. However, the direct table method can be derived in only a few simple steps by considering the long division process.

To derive the direct table method, we just need to keep in mind that the XOR operation is both associative and commutative:

Commutative: A ^ B = B ^ A

Associative: A ^ (B ^ C) = (A ^ B) ^ C

Consider the portion of the message starting from the byte B(i), where the bytes B(0) to B(i-1) have already been processed:

B(i)  B(i+1)  B(i+2)  B(i+3)  B(i+4) .... B(n)

The message is n bytes long.

We are ready to process the byte B(i), which will involve getting the value T[B(i)] 
and XORing it into the bytes B(i+1) and B(i+2).

But before doing this we define a secong bit string which is all zero, except for the 
byte at position i+2. The byte at i+2 is set to the same value as the byte B(i+2) in 
the message.

Then the message can be defined as:

{ B(i)  B(i+1)  0  B(i+3)  B(i+4) .... B(n) } XOR { 0  0  B(i+2)  0  0 .... 0 }

Next we XOR T[B(i)] into the message:

{ B(i+1)'  X  B(i+3)  B(i+4) .... B(n) } XOR { 0  B(i+2)  0  0 .... 0 }

The value X is just the lower byte of T[B(i)] - it's value doesn't really matter.

Next we XOR T[B(i+1)'] into the message:

{ X'  B(i+3)'  B(i+4) .... B(n) } XOR { B(i+2)  0  0 .... 0 }

We are now ready to process the X' byte, but to process the message properly we also 
have to deal with B(i+2). Unlike the previous terms in the bit string to the right of 
the XOR, B(i+2) is non-zero and will have an effect on the CRC calculation.

So we recombine the 2 bit strings to get:

(X' xor B(i+2))  B(i+3)'  B(i+4)' .... 0 

And it becomes clear that the index for the table T[] is just: { X' xor B(i+2) }

So for every byte B(i) in the message a bit string can be defined that is all zero 
except for the byte at position i which has a value of B(i). Let { B(i) } be any one 
of these bit strings. Then the message can be defined as the xor of all these bit strings:

M = { M' } xor { B(0) } xor { B(1) } xor .... { B(i) } .... xor { B(n) }

- where { M'} is just a zero bit string.

Then by the discussion above, the CRC can be calculated just by processing M' - with 
the bit string { B(i) } only needing to be XORed in when the byte at position i 
within M' is about to be processed.

As applied to the table method above using the register, this means that the bytes do not need to be shifted through the register. Instead they are just directly XORed with the most recent byte to be popped out of the register to generate a table index.

Initial and Final Values

Many CRC-16 implemetations specify an initial value which is XORed into the first 2 bytes of the message. CRC-16 also allows a final value to be XORed into the register once the CRC has been calculated. Both the initial and final values are 16 bit values.

My program supports both these options.

Reflection and Reversed Polynomials

These aspects of CRC-16 are not implemented in my program.

Program Usage

The input message can be entered as a Text String or a Hexadecimal Number. Press the [ Toggle Input Type ] to select one of these types of input. If a hexadecimal number is the input, it can include whitespace for formatting purposes. This whitespace will just be ignored when the number is processed. The [ Clear Input ] button clears the input area.

To compute the CRC for a message just press the [ Calc CRC ] button.

The user can enter values for the generator polynomial, the initial XOR value and the final XOR value. These are all entered as 4 digit hex numbers. The default values for these parameters are those for the IBM CRC-16 implementation: 8005 for the generator polynomial, FFFF for the initial XOR value, and 0000 for the final XOR value.

The program can also display the lookup tables for 4 bit and 8 bit indexes. Just press one of the [ Show Table ] buttons.

HTML/Javascript Source Code:

To grab this code, just select it with the mouse, and copy and paste into a text file.

<html>

<head>

<title>CRC 16</title>

<style type="text/css">

textarea, input, p
{
 font-family: "Lucida Console";

 font-size: 11pt;
}

h2
{
 font-family: "Verdana";
}

</style>

</head>

<script type="text/javascript">

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

var g_InputType = "Text";

var g_Poly = 0x8005; // default polynomial

var g_Init = 0xffff; // default initial register value

var g_Final = 0; // default XOR final value

var g_Message = [];

var g_Byte_Message = [];

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function Init()
{
 // init the text fields:

 var tmpstr="";

 tmpstr = g_Poly.toString(16);

 while(tmpstr.length < 4) tmpstr = "0" + tmpstr;

 document.getElementById("gen_poly").value = tmpstr;

 tmpstr = g_Init.toString(16);

 while(tmpstr.length < 4) tmpstr = "0" + tmpstr;

 document.getElementById("init").value = tmpstr;

 tmpstr = g_Final.toString(16);

 while(tmpstr.length < 4) tmpstr = "0" + tmpstr;

 document.getElementById("final").value = tmpstr;

 document.getElementById("input").value = "";
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function Clear()
{
 document.getElementById("input").value = "";
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function ToggleInputType()
{
 if(g_InputType == "Text")
 {
  g_InputType = "Hex";

  document.getElementById("input_type").innerHTML = "CRC-16: Hex Number Input";
 }
 else
 {
  g_InputType = "Text";

  document.getElementById("input_type").innerHTML = "CRC-16: Text String Input";
 }
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function ShowTable_4()
{
 // print the 4 bit index table (16 elements):

 if(getPoly())
 {
  document.getElementById("input").value = "Error: invalid generator or init value.";

  return;
 }

 // generate the table:

 var Table = calcTable_4();

 var outstr = "";

 var tmpstr = "";

 var i;

 // print the table:

 for(i=0;i<16;i++)
 {
  tmpstr = Table[i].toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += tmpstr + "\r\n";
 }

 document.getElementById("input").value = outstr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function ShowTable_8()
{
 // print the 8 bit index table (16 elements):

 if(getPoly())
 {
  document.getElementById("input").value = "Error: invalid generator or init value.";

  return;
 }

 // generate the table:

 var Table = calcTable_8();

 var outstr = "";

 var tmpstr = "";

 var i,j;

 // print the table:

 for(i=0;i<32;i++)
 {
  for(j=0;j<8;j++)
  {
   tmpstr = Table[i*8+j].toString(16);

   while(tmpstr.length<4) tmpstr = "0" + tmpstr;

   outstr += tmpstr + "  ";
  }

  outstr += "\r\n";
 }

 document.getElementById("input").value = outstr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function getPoly()
{
 // get the polynomial, init and final values:

 var bError = false;

 // polynomial:

 var str = document.getElementById("gen_poly").value;

 g_Poly = parseInt(str,16);

 if(g_Poly > 0xffff) bError = true;

 // Init:

 str = document.getElementById("init").value;

 g_Init = parseInt(str,16);

 if(g_Init > 0xffff) bError = true;

 // Final:

 str = document.getElementById("final").value;

 g_Final = parseInt(str,16);

 if(g_Final > 0xffff) bError = true;

 return bError;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function getMessage(tmpstr)
{
 // load the message into an array:

 // the message is read as a hex number, each array element 
 // contains a single hex digit (nibble):

 g_Message = [];

 g_Byte_Message = [];

 // remove whitespace:

 tmpstr = tmpstr.replace(/\s{0,}/g,"");

 if(tmpstr.length == 0)
 {
  document.getElementById("input").value = "Error - NULL input.";

  return;
 }

 // pad message by 16 bits (add 4 zeroes):

 tmpstr += "0000";

 // load the hex digits:

 var i;

 var index = 0;

 for(i=0;i<tmpstr.length;i++)
 {
  var asc = tmpstr.charCodeAt(i);

  if(asc >= 48 && asc <= 57)
  {
   // 0 - 9:

   g_Message[index++] = asc - 48;
  }
  else if(asc >= 65 && asc <= 70)
  {
   // A - F:

   g_Message[index++] = asc - 55;
  }
  else if(asc >= 97 && asc <= 102)
  {
   // a - f:

   g_Message[index++] = asc - 87;
  }
  else
  {
   document.getElementById("input").value = "Error - invalid character in input.";

   return;
  }
 }
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function getByteMessage()
{
 // convert the message array of hex digits 
 // into an array of bytes:

 var byte_message = [];

 var i,j;

 j=0;

 for(i=0;i<g_Message.length;i+=2)
 {
  byte_message[j] = g_Message[i];

  byte_message[j] <<= 4;

  byte_message[j] |= g_Message[i+1];

  byte_message[j] &= 0xff;

  j++;  
 }

 return byte_message;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function ToHex(tmpstr)
{
 // convert a text string to a hexadecimal number string:

 if(tmpstr.length == 0)
 {
  document.getElementById("input").value = "Error - NULL input.";

  return;
 }

 var outstr = "";

 var i;

 for(i=0;i<tmpstr.length;i++)
 {
  var asc = tmpstr.charCodeAt(i);

  // no need to worry about leading zeros, hex values for 
  // printable characters are >= 0x20:

  outstr += asc.toString(16);
 }

 return outstr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcCRC()
{
 // calc the CRC using each of the different methods:

 var tmpstr = document.getElementById("input").value;

 // get the poly, init  and final values:

 if(getPoly())
 {
  document.getElementById("input").value = "Error: invalid generator or init value.";

  return;
 }

 // convert the input to a hex number string:

 if(g_InputType == "Text")
 {
  tmpstr = ToHex(tmpstr);
 }

 // get the message (padded with 2 zero bytes):

 getMessage(tmpstr);

 if(g_Message.length < 5) return;

 var i;

 var outstr = "Message (padded):\r\n\r\n";

 for(i=0;i<g_Message.length;i++)
 {
  outstr += g_Message[i].toString(16);
 }

 outstr += "\r\n\r\n";

 // XOR the Init value into the first 2 bytes of the message:

 for(i=0;i<4;i++)
 {
  g_Message[i] ^= (g_Init >> (12-4*i)) & 0xf;
 }

 // CRC by long division:

 var CRC = calcByDivision();

 var tmpstr = "";

 for(i=0;i<CRC.length;i++)
 {
  tmpstr += CRC[i].toString(16);
 }

 outstr += "CRC (by division) =\r\n\r\n" + tmpstr + "\r\n\r\n";

 // CRC by pushing the message bits through a 16 bit register:

 CRC = calcByRegister();

 tmpstr = CRC.toString(16);

 while(tmpstr.length<4) tmpstr = "0" + tmpstr;

 outstr += "CRC (by register) = " + tmpstr + "\r\n\r\n";

 // CRC by the table method:

 if(g_Message.length%2 > 0)
 {
  CRC = calcByTable_4();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by table - 4 bit index) = " + tmpstr + "\r\n\r\n";

  // reverse the initial XOR of the Init value into the first 2 message bytes,
  // the direct table functions directly initialise the register with this value 

  for(i=0;i<4;i++)
  {
   g_Message[i] ^= (g_Init >> (12-4*i)) & 0xf;
  }

  CRC = calcByDirectTable_4();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by direct table - 4 bit index) = " + tmpstr + "\r\n\r\n";
 }
 else
 {
  CRC = calcByTable_4();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by table - 4 bit index) = " + tmpstr + "\r\n\r\n";

  CRC = calcByTable_8();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by table - 8 bit index) = " + tmpstr + "\r\n\r\n";

  // reverse the initial XOR of the Init value into the first 2 message bytes,
  // the direct table functions directly initialise the register with this value 

  for(i=0;i<4;i++)
  {
   g_Message[i] ^= (g_Init >> (12-4*i)) & 0xf;
  }

  CRC = calcByDirectTable_4();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by direct table - 4 bit index) = " + tmpstr + "\r\n\r\n";

  CRC = calcByDirectTable_8();

  tmpstr = CRC.toString(16);

  while(tmpstr.length<4) tmpstr = "0" + tmpstr;

  outstr += "CRC (by direct table - 8 bit index) = " + tmpstr + "\r\n\r\n";
 }

 document.getElementById("input").value = outstr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByTable_4()
{
 // use a 4 bit index table to calc the CRC:

 // generate the table:

 var Table = calcTable_4();

 // init the register with the first 2 bytes of the message:

 var register_16 = g_Message[0];

 register_16 <<= 4;

 register_16 |= g_Message[1];

 register_16 <<= 4;

 register_16 |= g_Message[2];

 register_16 <<= 4;

 register_16 |= g_Message[3];

 register_16 &= 0xffff;

 var i;

 // push the remaining message through the register:

 // one hex digit (nibble) at a time: 

 for(i=4;i<g_Message.length;i++)
 {
  // calc the table index (4 bits):

  var index = (register_16 >> 12) & 0xf;

  // shift the register:

  register_16 <<= 4;

  // shift in the next digit:

  register_16 |= g_Message[i];

  // XOR with Table[index]:

  register_16 ^= Table[index];

  register_16 &= 0xffff;
 }

 // XOR in the final value:

 register_16 = XOR_Final(register_16);

 return register_16;

}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByTable_8()
{
 // use an 8 bit index table to calc the CRC:

 // generate the table:

 var Table = calcTable_8();

 // init the register with the first 2 bytes of the message:

 var byte_message = getByteMessage();

 var register_16 = byte_message[0] << 8;

 register_16 |= byte_message[1];

 register_16 &= 0xffff;

 var i;

 // push the remaining message through the register:

 // one byte at a time: 

 for(i=2;i<byte_message.length;i++)
 {
  // calc the table index (8 bits):

  var index = (register_16 >> 8) & 0xff;

  // shift the register:

  register_16 <<= 8;

  // shift in the next byte:

  register_16 |= byte_message[i];

  // XOR with Table[index]:

  register_16 ^= Table[index];

  register_16 &= 0xffff;
 }

 // XOR in the final value:

 register_16 = XOR_Final(register_16);

 return register_16;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByDirectTable_4()
{
 // Direct Table Method:

 // use a 4 bit index table to calc the CRC:

 // generate the table:

 var Table = calcTable_4();

 // init the register with the Init value:

 var register_16 = g_Init;

 var i;

 // process the message:

 // one hex digit (nibble) at a time: 

 // don't include the padding:

 for(i=0;i<g_Message.length-4;i++)
 {
  // calc the table index (4 bits):

  // XOR the current hex digit with the
  // upper 4 bits of the register:

  var index = ((register_16 >> 12) ^ g_Message[i]) & 0xf;

  // shift the register:

  register_16 <<= 4;

  // XOR with Table[index]:

  register_16 ^= Table[index];

  register_16 &= 0xffff;
 }

 // XOR in the final value:

 register_16 = XOR_Final(register_16);

 return register_16;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByDirectTable_8()
{
 // Direct Table Method:

 // use an 8 bit index table to calc the CRC:

 // generate the table:

 var Table = calcTable_8();

 // init the register with the Init value:

 var register_16 = g_Init;

 var byte_message = getByteMessage();

 var i;

 // process the message:

 // one byte at a time: 

 // don't include the padding:

 for(i=0;i<byte_message.length-2;i++)
 {
  // calc the table index (8 bits):

  // XOR the current byte with the
  // upper 8 bits of the register:

  var index = ((register_16 >> 8) ^ byte_message[i]) & 0xff;

  // shift the register:

  register_16 <<= 8;

  // XOR with Table[index]:

  register_16 ^= Table[index];

  register_16 &= 0xffff;
 }

 // XOR in the final value:

 register_16 = XOR_Final(register_16);

 return register_16;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByRegister()
{
 var i,j;

 var register_16 = 0;

 // load the first 2 bytes of the message into the register:

 for(i=0;i<4;i++)
 {
  register_16 <<= 4;

  register_16 |= (g_Message[i] & 0xf);
 }

 register_16 &= 0xffff;

 var carry_bit = 0;

 // feed in the rest of the message, one bit at a time:

 for(i=4;i<g_Message.length;i++)
 {
  var mask = 8;

  for(j=0;j<4;j++)
  {
   if(j==0) mask = 8;

   carry_bit = 0;

   if(register_16 & 0x8000) carry_bit = 1;

   // shift the msb out of the register:

   register_16 <<= 1;

   // shift in the next message bit:

   if(g_Message[i] & mask) register_16 |= 1;  

   // XOR with the polynomial:

   if(carry_bit)
   {
    register_16 ^= g_Poly;
   }

   register_16 &= 0xffff;

   mask >>>= 1;  
  }
 }

 // XOR in the final value:

 register_16 = XOR_Final(register_16);

 return register_16;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcByDivision()
{
 // calc the CRC by long division of the 
 // polynomial into the message:

 // include the bit at X^16:

 var poly_val = (0x10000 + g_Poly) & 0x1ffff;

 // init the poly array:
 // msb is aligned with the first bit of the message:

 var poly = InitPoly(poly_val,g_Message.length);

 var i,j,k;

 var CRC = [];

 for(i=0;i<g_Message.length;i++) CRC[i] = g_Message[i];

 // do the long division:

 for(i=0; i < CRC.length-4; i++)
 {
  var mask=8; 

  for(j=0;j<4;j++)
  {
   if(j==0) mask=8;

   // if the bit in the message that is aligned with the 
   // msb of the poly is 1, XOR the poly into the message:

   if(CRC[i] & mask)
   {
    for(k=0; k < CRC.length; k++)
    {
     CRC[k] = (CRC[k] ^ poly[k]) & 0xf;
    }
   }

   mask >>>= 1;

   poly = shiftRight(poly);
  }  
 }

 // XOR in the final value:

 var fx = g_Final;

 for(i = CRC.length-1; i >= CRC.length-4; i--)
 {
  CRC[i] = (CRC[i] ^ fx) & 0xf;

  fx >>>= 4; 
 }

 return CRC;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcTable_4()
{
 // calc the 4 bit index table:

 var Table = [];

 var i,j;

 for(i=0;i<16;i++)
 {
  var word = (i << 12) & 0xffff;

  for(j=0;j<4;j++)
  {
   var test = word & 0x8000;

   word = (word << 1) & 0xffff;

   if(test)
   {
    word = (word ^ g_Poly) & 0xffff;
   }
  }

  Table[i] = word & 0xffff; 
 }

 return Table;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function calcTable_8()
{
 // calc the 8 bit index table:

 var Table = [];

 var i,j;

 for(i=0;i<256;i++)
 {
  var word = (i << 8) & 0xffff;

  for(j=0;j<8;j++)
  {
   var test = word & 0x8000;

   word = (word << 1) & 0xffff;

   if(test)
   {
    word = (word ^ g_Poly) & 0xffff;
   }
  }

  Table[i] = word & 0xffff; 
 }

 return Table;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function XOR_Final(CRC)
{
 return (CRC ^ g_Final) & 0xffff;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function InitPoly(poly_val,msg_length)
{
 // load the polynomial into an array, 
 // for the long division method:

 var poly = [];

 var i;

 for(i=0;i<msg_length;i++) poly[i]=0;

 poly_val <<= 3;

 poly_val &= 0xfffff;

 poly[4] = poly_val & 0xf;

 poly_val >>>= 4;

 poly[3] = poly_val & 0xf;

 poly_val >>>= 4;

 poly[2] = poly_val & 0xf; 

 poly_val >>>= 4;

 poly[1] = poly_val & 0xf;

 poly_val >>>= 4;

 poly[0] = poly_val & 0xf;

 return poly;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function shiftLeft(arr)
{
 // left shift a hex digit array, by 1:

 var k;

 for(k=0;k<arr.length;k++)
 {
  arr[k] <<= 1;

  if((k<arr.length-1) && (arr[k+1] & 8)) arr[k] |= 1;

  arr[k] &= 0xf;
 }

 return arr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function shiftRight(arr)
{
 // right shift a hex digit array, by 1:

 var k;

 for(k=arr.length-1;k>=0;k--)
 {
  arr[k] >>>= 1;

  if((k>0) && (arr[k-1] % 2)) arr[k] |= 8;

  arr[k] &= 0xf;
 }

 return arr;
}

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

</script>

<body onload="Init()">

<h2 id="input_type">CRC-16: Text String Input</h2>

<input type="button" value="Toggle Input Type" onclick="ToggleInputType()">

<input type="button" value="Clear Input" onclick="Clear()">

<input type="button" value="Calc CRC" onclick="calcCRC()">

<p>
For hexadecimal number input, whitespace is allowed.
</p>

<p>
Generator Polynomial:
<input type="text" id="gen_poly" size="7">
Init:
<input type="text" id="init" size="7">
Final:
<input type="text" id="final" size="7">
</p>

<p>
Enter the message:
</p>

<textarea id="input" cols="60" rows="20" spellcheck="false"></textarea>

<br><br>

<input type="button" value="Show Table: 4 Bit Index" onclick="ShowTable_4()">

<input type="button" value="Show Table: 8 Bit Index" onclick="ShowTable_8()">

</body>

</html>
Advertisements

Create a free website or blog at WordPress.com.

%d bloggers like this: