C Board  

Go Back   C Board > General Programming Boards > C Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 02-06-2010, 11:56 PM   #1
Eager young mind
 
Join Date: Jun 2006
Posts: 342
CRC stuff

Hi All,
I have been trying to work with CRC. I have searched the boards for some of the CRC-related discussion and I have also gone over this link. http://www.ross.net/crc/download/crc_v3.txt. I found a piece of code that implements CRC at http://www.google.com/url?sa=t&sourc...kTe77z5o8R6z2A and I am trying to adapt it.

So, this is what I know so far :
1. Grab a buffer, generate its CRC
2. Append the CRC to the buffer to generate a new string
3. Generate the CRC on this new string and it should be zero.

I have made very minor changes to that piece of code so far and this is what I have now :

Code:
//----- Include files ---------------------------------------------------------
#include <stdio.h>                  // Needed for printf()
#include <stdlib.h>                 // Needed for rand()
#include <string.h>

//----- Type defines ----------------------------------------------------------
typedef unsigned char      byte;    // Byte is a char
typedef unsigned short int word16;  // 16-bit word is a short int
typedef unsigned int       word32;  // 32-bit word is an int

//----- Defines ---------------------------------------------------------------
#define POLYNOMIAL 0x04c11db7L      // Standard CRC-32 ppolynomial
#define BUFFER_LEN       4096      // Length of buffer

//----- Gloabl variables ------------------------------------------------------
static word32 crc_table[256];       // Table of 8-bit remainders

//----- Prototypes ------------------------------------------------------------
void gen_crc_table(void);
word32 update_crc(word32 crc_accum, byte *data_blk_ptr, word32 data_blk_size);


//===== Main program ==========================================================
int main()
{
  byte        *buff; // Buffer of packet bytes
  word32      crc32;            // 32-bit CRC value
  word16      i;                // Loop counter (16 bit)
  word32      j;                // Loop counter (32 bit)
  char        *crc_hex_string, *crc_bin_string;

  crc_hex_string = malloc(sizeof(char)*1024);
 buff = malloc(sizeof(char)*BUFFER_LEN);

  // Initialize the CRC table
  gen_crc_table();

  // Load buffer with BUFFER_LEN random bytes
  for (i=0; i<BUFFER_LEN; i++)
    buff[i] = (byte) rand();

  // Compute and output CRC
  printf("size of orig buffer = %d \n",strlen(buff));
  crc32 = update_crc(-1, buff, BUFFER_LEN);
  sprintf(crc_hex_string,"%08X",crc32);
  printf("CRC = %08X string = %s\n", crc32,crc_hex_string);

  strcat(buff, crc_hex_string);

  printf("size of new buffer = %d, size of crc buffer =%d \n",strlen(buff),sizeof(crc_hex_string));

  crc32 = update_crc(-1, buff, BUFFER_LEN + strlen(crc_hex_string));
  printf("CRC = %08X \n", crc32);

  return 0;
}

//=============================================================================
//=  CRC32 table initialization                                               =
//=============================================================================
void gen_crc_table(void)
{
  register word16 i, j;
  register word32 crc_accum;

  for (i=0;  i<256;  i++)
  {
    crc_accum = ( (word32) i << 24 );
    for ( j = 0;  j < 8;  j++ )
    {
      if ( crc_accum & 0x80000000L )
        crc_accum = (crc_accum << 1) ^ POLYNOMIAL;
    else
        crc_accum = (crc_accum << 1);
    }
    crc_table[i] = crc_accum;
  }
}

//=============================================================================
//=  CRC32 generation                                                         =
//=============================================================================
word32 update_crc(word32 crc_accum, byte *data_blk_ptr, word32 data_blk_size)
{
   register word32 i, j;

   for (j=0; j<data_blk_size; j++)
   {
     i = ((int) (crc_accum >> 24) ^ *data_blk_ptr++) & 0xFF;
     crc_accum = (crc_accum << 8) ^ crc_table[i];
   }
   crc_accum = ~crc_accum;

   return crc_accum;
}
So, I am trying to print out the CRC value for the original string and the appended string. But, the CRC generated for the second string is not 0. I am planning on digging deeper into the CRC code to see what could be going wrong. But, I just thought of posting this code here to see if someone can offer any insights.

Thanks!
__________________
In the middle of difficulty, lies opportunity
kris.c is offline   Reply With Quote
Old 02-07-2010, 12:37 AM   #2
and the hat of Destiny
 
Salem's Avatar
 
Join Date: Aug 2001
Location: The edge of the known universe
Posts: 22,495
> 3. Generate the CRC on this new string and it should be zero.
Where did you get this idea from?

> printf("size of orig buffer = %d \n",strlen(buff));
And if your rand() produces a zero, then strlen will give you the wrong answer.

> strcat(buff, crc_hex_string);
And this is a buffer overrun, or random scribble in the middle of the buffer.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

Salem is offline   Reply With Quote
Old 02-07-2010, 12:53 AM   #3
Eager young mind
 
Join Date: Jun 2006
Posts: 342
Salem,
>> 3. Generate the CRC on this new string and it should be zero.
>Where did you get this idea from?

I think Section 6 in this link http://www.ross.net/crc/download/crc_v3.txt seems to say something along these lines :

Code:
the checksum is then appended to the message and the result
transmitted. In this case the transmission would be: 11010110111110.

At the other end, the receiver can do one of two things:

   a. Separate the message and checksum. Calculate the checksum for
      the message (after appending W zeros) and compare the two
      checksums.

   b. Checksum the whole lot (without appending zeros) and see if it
      comes out as zero!
Right now, I am just working with one process that reads some data and generates the checksum. Before I go into dealing with 2 processes and a buggy network, I just wanted to compute the CRC on (message + checksum) on the first process itself. Please correct me if I am wrong.

Also, thanks for pointing out the other two possible errors.
__________________
In the middle of difficulty, lies opportunity
kris.c is offline   Reply With Quote
Old 02-07-2010, 03:27 AM   #4
and the hat of Destiny
 
Salem's Avatar
 
Join Date: Aug 2001
Location: The edge of the known universe
Posts: 22,495
Well yes, for a simple checksum, that is true.

But these are CRC's.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

Salem is offline   Reply With Quote
Old 02-07-2010, 10:46 AM   #5
Eager young mind
 
Join Date: Jun 2006
Posts: 342
Ok. So, I will let the other process create the CRC just on the data buffer and compare the two CRC's. But, going back to the "strcat" issue that you indicated. strcat(s,t) is supposed to concatenate string t at the end of string s, right? As long as there is enough space left in s, we shouldn't be running into problems. Can you please elaborate on that?
__________________
In the middle of difficulty, lies opportunity
kris.c is offline   Reply With Quote
Old 02-07-2010, 11:12 AM   #6
and the hat of Destiny
 
Salem's Avatar
 
Join Date: Aug 2001
Location: The edge of the known universe
Posts: 22,495
For one thing, you're dealing with a lot of binary data, so you should be using mem... functions for the most part.

2. buff = malloc(sizeof(char)*BUFFER_LEN);
You don't allocate enough space to append anything.

3. As mentioned before, your rand() filling of a block of memory MAY result in a surprise \0 in an unexpected place.
Since you never allocate space for strcat to work with, nor store a \0 in the correct place, that whole idea is broken.

4. stringifying everything, then recalculating the CRC doesn't add anything.

Typically, one would
- allocate n+sizeof(word32) bytes
- copy n bytes of data to the buffer
- calculate the CRC on n bytes
- memcpy( buff[n], &crc, sizeof(crc)) to append the crc
- send n+sizeof(crc) to whoever wants to receive CRC checked data.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

Salem is offline   Reply With Quote
Old 02-07-2010, 11:19 AM   #7
Eager young mind
 
Join Date: Jun 2006
Posts: 342
Thanks.
__________________
In the middle of difficulty, lies opportunity
kris.c is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Random CRC works "kinda" RedRover C++ Programming 16 08-26-2009 05:43 AM
CRC Check silentkarma C++ Programming 8 03-01-2008 04:20 AM
Tab key stuff. C+WinAPI is killing me. Please help. Templario Windows Programming 5 11-21-2002 03:35 PM
arguments, directories and stuff... Unregistered C Programming 3 06-26-2002 05:46 PM
Your stuff smog890 C Programming 6 06-13-2002 11:50 PM


All times are GMT -6. The time now is 12:10 AM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22