CRC Emulation

[img_assist|nid=28|title=|desc=|link=node|align=right|width=83|height=100]I coded this assignment to perform CRC calculations against arbitrary data strings using standard polynomials and r values as can be seen in this screenshot. One may also select the Custom option to enter other calculation values. The textbox allows the user to enter strings to run the CRC against. For fun, I setup displays in binary, decimal, and hex for the polynomial and result values. In the documentation that follows, I explain the code that performs the calculations, but the full source code may be downloaded via the link at the top of the page.

CRC.h

There's nothing too exciting going on in CRC.h. It contains the normal function declaration as well as a struct to hold a register (shown below) as well as two declorations of that struct (polyBin and shftReg).

private:
     struct sReg
     {
          char reg[64];
          nt regLen;
     };

     sReg polyBin;
     sReg shftReg;

CRC_Check

The CRC_Check function is the work-horse function in this project. It is called upon by the main form to execute the calculation and return the checksum value. The function performs the CRC check on the given string of given length with using the given poly.

Syntax:

  • str: pointer to the data line to perform the CRC calculation against
  • len: pointer to the integer length of the str value
  • poly: the poly to use in the CRC calculation
  • r: the r value to use in the CRC calculation

Returns:

  • Integer value as the CRC calculation result.

Assumes:

  • That str has any necessary zeros appended (to accommodate the full CRC check).

Code:

#include "stdafx.h"
#include "CRC.h"


int CRCWork::CRC_Check(string * str, int * len, int * poly, int * r)

{
     int retVal;
     char nextBit;

     // Place the polly into the pollyBin register in binary value


     procStr = str;
     procLen = *len;
     procStrOffset = 0;
     procBitPos = 8;
     procBitEndPos = 0;


     //initialize the registers
     for (int j = 0; j < 64; j++)
     {
          polyBin.reg[j] = 0;
          shftReg.reg[j] = 0;

     }

     //convert the poly bin from decimal to text and store it
     polyBin.regLen = *r;
     Int2BinaryCRC(poly, &polyBin);


     // Insert a leading zero into the shift register (for the sake of easy program flow)

     shftReg.reg[0] = '0';

     // populate the shift register up to the first potential XOR event.
     for (int i = 0; i < polyBin.regLen; i++) 

     {
          // Get the next value from the bit string and append it to the shift register

          shftReg.reg[i+1] = getNextBit();

     }

    // set the length of the shift register to be the same as the poly register

     shftReg.regLen = polyBin.regLen;

     // process the rest of the bit stream, performing and XOR every time a 1 moves into the

     // left-most position of the shift register.
     nextBit = getNextBit();

     while (nextBit != 0)
     {
          // shiftInFromRight returns true of the left-most character is a 1
          if(shiftInFromRight(&shftReg, nextBit))

          {
               // XOR_op performs a bitwise XOR to each corresponding element the registers.
               XOR_op(&polyBin, &shftReg);
          }

          nextBit = getNextBit();
     }
     
     //create an integer version of the resulting CRC value useing shift operations

     retVal = 0;
     for (int i = 0; i <= shftReg.regLen; i++)
     {
          retVal <<= 1;
          if (shftReg.reg[i] == '1') retVal += 1;

     }
     return retVal;
};

getNextBit

Retrieves the next input character from str, supplying zeros if necessary to fill in the end of the CRC check.

Returns:

  • next character from str to process

Assumes:

  • that the various variables used by the program properly updated before the function call

Code:

char CRCWork::getNextBit()

{
     int asciiCharVal;
     string test;
     char buffer[32];

     if (procStrOffset == procLen && procBitPos == 8)      // add the following 0's to complete CRC

     {
          if (procBitEndPos++ < polyBin.regLen)
          {
               return '0';
          } else {
               return 0;  // end condition
          }
     }

     if (procBitPos == 8)                                  // get the next letter from string
     {

          asciiCharVal = (int) *procStr->substr(procStrOffset++,1).c_str();

          itoa(asciiCharVal, buffer, 2);
          procBitBuffer.assign(buffer);
          procBitBuffer.insert(0, 8-procBitBuffer.length(), '0');
          procBitPos = 0;
     }

     return *procBitBuffer.substr(procBitPos++,1).c_str();
}

shiftInFromRight

Shifts a char into the sReg from the right hand side, dropping the left most bit. In essence, this is simulating a portion of the CRC logic gate.

Syntax:

  • shftReg: the sReg to have its value shifted
  • shftIn: the char to shift into the sReg

Returns:

  • true if the left most argument in the resulting sReg is a 1, otherwise returns false

Assumes:

  • that the various variables used by the program properly updated before the function call

Code:

bool CRCWork::shiftInFromRight(sReg * shftReg, char shftIn)
{
     for (int i = 0; i < shftReg->regLen; i++)

     {
          shftReg->reg[i] = shftReg->reg[i+1];
     }

     shftReg->reg[shftReg->regLen] = shftIn;

     if (shftReg->reg[0] == '1') return true;

    return false;
}

shiftInFromLeft

Shifts a char into the sReg from the left hand side, dropping the right most bit.

Syntax:

  • shftReg: the sReg to have its value shifted
  • shftIn: the char to shift into the sReg

Assumes:

  • that the various variables used by the program properly updated before the function call

Code:

void CRCWork::shiftInFromLeft(sReg * sr, char shftIn)
{
     for (int i = 63; i > 0; i--)

     {
          sr->reg[i] = sr->reg[i-1];
     }

     sr->reg[0] = shftIn;
}

XOR_op

Performs an XOR operation between a given polly and register.

Syntax:

  • poly: an sReg as the poly to be XORed
  • reg: an sReg as the reg to be XORed

Returns:

  • second argument is altered and returned after a bitwise XOR is performed between each corresponding element

Assumes:

  • that both sReg are the same size

Code:

void CRCWork::XOR_op(sReg * poly, sReg * reg)
{
     for (int i = 0; i <= reg->regLen; i++)                // for each element in the sReg arrays...

     {
          if(poly->reg[i]==reg->reg[i])                    // if the values are equal, XOR to 0
          {
               reg->reg[i] = '0';

          } else {                                         // if the values are NOT equal, XOR to 1
               reg->reg[i] = '1';

          }
     }     
}

hex2int

These are public accessors of the _httoi function for converting a hex string into an integer value.

Syntax:

  • strPoly: value to convert from hex to int

Returns:

  • an int as the conversion from the hex value to the poly

Assumes:

  • that a valid hex value is being passed in by strPoly

Code:

int CRCWork::hex2int(string strPoly)
{
     return hex2int(&strPoly);
};
 
int CRCWork::hex2int(string * strPoly)
{
     int poly = _httoi(strPoly->c_str());
     return poly;
};

RandomBits

Generates a string of 0 and 1 bits of a random length between 50 and 1050 for use in code testing.

Returns:

  • random length string of 1s and 0s

Code:

string CRCWork::RandomBits()
{
     string rndCRC;
     char buffer[1];


     int ofLen = (int)(rand()%1000)+50;                    // select a random length between 50 and 1050


     for (int i = 0; i < ofLen; i++)                       // loop to create random length string of 'data'

     {
          itoa((int)rand()%2, buffer, 10);                 // create a 1 or 0 and stick it into char array ...

          rndCRC.append(buffer);                           // ... and add it to the data string.
     }

     return rndCRC;
}

RandomString

Generates a string of alphanumeric characters of a random length between 50 and 1005 for use in code testing.

Returns:

  • random length string of alphanumeric characters

Code:

string CRCWork::RandomString()
{
     string rndCRC;
     char buffer[1];
     int charVal;


     int ofLen = (int)(rand()%1000)+5;                     // select a random length between 50 and 1005


     for (int i = 0; i < ofLen; i++)                       // loop to create random length string of 'data'

     {
          // generate an ASCII character in the visible range (from 30 to 126)
          charVal = (int)(rand()%95) + 32;

          buffer[0] = charVal;
          rndCRC.append(buffer,1);                         // ... and add it to the data string.
     }

     return rndCRC;

}
 

_httoi

Code from www.thecodeproject.com/string/hexstrtoint.asp.
Converts a hex string (with or without UNICODE defined) into an integer.

Syntax:

  • value: a TCHAR of the string to convert

Returns:

  • an int as the conversion from the hex value

Assumes:

  • that a valid hex value is being passed in by strPoly

Code:

int CRCWork::_httoi(const TCHAR *value)
{
     struct CHexMap
     {
          TCHAR chr;
          int value;

     };
     const int HexMapL = 16;
     CHexMap HexMap[HexMapL] =
     {
          {'0', 0}, {'1', 1},
          {'2', 2}, {'3', 3},

          {'4', 4}, {'5', 5},
          {'6', 6}, {'7', 7},
          {'8', 8}, {'9', 9},
          {'A', 10}, {'B', 11},
          {'C', 12}, {'D', 13},

          {'E', 14}, {'F', 15}
     };

     TCHAR *mstr = _tcsupr(_tcsdup(value));
     TCHAR *s = mstr;
     int result = 0;


     if (*s == '0' && *(s + 1) == 'X') s += 2;
     bool firsttime = true;


     while (*s != '\0')
     {
          bool found = false;
          for (int i = 0; i < HexMapL; i++)

          {
               if (*s == HexMap[i].chr)
               {
                    if (!firsttime) result <<= 4;
                    result |= HexMap[i].value;
                    found = true;

                    break;
               }
          }
          if (!found) break;
          s++;
          firsttime = false;
     }

     free(mstr);
     return result;
}

MarshalString

Code from www.winterdom.com/mcppfaq/archives/000111.html. (with minor modifications)
Converts a System string into a std string.

Syntax:

  • s: the System string to take contents from
  • os: the std string to be replaced with the contents from s

Code:

void CRCWork::MarshalString ( System::String* s, std::string& os )
{
     using namespace System::Runtime::InteropServices;

     const char* chars =
          (const char*)(Marshal::StringToHGlobalAnsi(s)).ToPointer();
     os = chars;
     Marshal::FreeHGlobal(System::IntPtr((void*)chars));
}
void CRCWork::MarshalString ( System::String* s, std::wstring& os )

{
     using namespace System::Runtime::InteropServices;
     const wchar_t* chars =
          (const wchar_t*)(Marshal::StringToHGlobalUni(s)).ToPointer();
     os = chars;
     Marshal::FreeHGlobal(System::IntPtr((void*)chars));
}

Int2BinaryCRC

Converts an integer into a binary string of 1s and 0s. The first version accepts a integer to convert and the expected return length. This function calls the second version, which accepts a value to convert and a sReg to store it in.

Syntax:

  • CRCval: value to be converted into a binary string
  • len: length of the expected return string

Returns:

  • binary string of 1s and 0s

Code:

string CRCWork::Int2BinaryCRC(int * CRCval, int * len)
{
     sReg CRCreg;
     string retStr;
     for (int j = 0; j < 64; j++) CRCreg.reg[j] = 0;

     CRCreg.regLen = *len;
     Int2BinaryCRC(CRCval, &CRCreg);
     retStr.assign(CRCreg.reg);
     return retStr;
}

Int2BinaryCRC

Accepts a value to convert into a binary string of 1s and 0s and a sReg to store it in.

Syntax:

  • CRCval: integer to be converted
  • CRCreg: sReg to hold the converted value

Code:

void CRCWork::Int2BinaryCRC(int *CRCval, sReg *CRCreg)
{
     itoa(*CRCval,CRCreg->reg,2);

     while (CRCreg->reg[CRCreg->regLen-1]==0)
     {
          shiftInFromLeft(CRCreg,'0');
     }
     shiftInFromLeft(CRCreg,'1');
}