CRC table generator.

May 11, 2008
19,442
1,155
126
Hello. Maybe you can help me what quirks i overlooked.

I am trying to make a crc checksum table generator.
My implementation does not seem to work.
It is almost a straight copy of this example.
To make sure the error is with me, i used the example shown below.
But i get the same results.
All i get is a table filled with zeros.
Why is it not working in visual studio ?
What have i overlooked ?

Code:
// Type definitions.
typedef char		 int8_t;	
typedef unsigned char      uint8_t;	
typedef short                 int16_t;
typedef unsigned short	 uint16_t;
typedef long		int32_t;				
typedef unsigned long	uint32_t;


// Constants.
#define POLYNOMIAL            0x8005
#define MSB_BIT                  0x8000 // (1 << 15)
#define INITIAL_REMAINDER   0

// Global variables.
uint16_t      g_crctable[256]; // For a 16 bit crc, we need to store 16 bit values.


void CrcTableGenerator(void)
{
  uint16_t  remainder;
  int	    dividend;
  int	    bit;

  /* Compute the remainder of each possible dividend. */
  for (dividend = 0; dividend < 256; dividend++)
  {
      /* Start with the dividend followed by zeros. */
      remainder = dividend << 8;

    /* Perform modulo-2 division, a bit at a time. */
    for (bit = 8; bit > 0; bit--)
    {
       /* Try to divide the current data bit. */			
       if (remainder & MSB_BIT)
       {
	remainder = (remainder << 1) ^ POLYNOMIAL;
       }
       else
       {
       	remainder = (remainder << 1);
       } 
     }
    /* Store the result into the table. */
    g_crctable[dividend] = remainder;
  }
}
 

Markbnj

Elite Member <br>Moderator Emeritus
Moderator
Sep 16, 2005
15,682
13
81
www.markbetz.net
Quick read... I'll guess that the example was written for a platform with a different byte order than Intel. The values 0-255 are in the first byte of the word-sized variable dividend, and disappear when you shift that byte off to the left.

For more background Google "little-endian vs. big-endian."
 
Last edited:
May 11, 2008
19,442
1,155
126
Thank you for the reply.

I know about the Endian information.

But the code example i got is a general example.
And with how it works, it should not matter about the Endian format.
It is just a table generator computing a fixed result for a fixed input.
y = x / A , 0 <= x <= 255. A is a constant.
This function does not read in the data. That is another function that will make use of the stored results in this table.

When i have it working, i use the table for an embedded system based on an ARM (No CRC unit :( ) where i will write an embedded c function first to get it working and a hand optimized assembly function after that. An assembly routine that makes optimum use of the 32 bit width ARM architecture and ARM machine instructions. I want to make it as efficient as possible. But first i have to understand the basics. At the moment i am at a loss. Back to the drawing board.
 
May 11, 2008
19,442
1,155
126
I am using the debugger, but i think i forgot to cast something.

EDIT:

Not sure if the cast helped. the worst error was the if statement error.
I looked at it with a fresh look and realized that if ((value & MSB_BIT) == 1)
can never work.
It must be :
if ((value & MSB_BIT) == MSB_BIT)
Time to call it a day i think.

if (value & MSB_BIT)
Also does not seem to work under Visual Studio.

if ((value & MSB_BIT) == MSB_BIT)
This works, May table is filled. :)
 
Last edited:

Venix

Golden Member
Aug 22, 2002
1,084
3
81
I compiled it with Visual Studio and it did not generate a table full of zeroes. You must be making a mistake somewhere else.

It should be trivial to determine why it isn't working by stepping through the code with the debugger.
 
May 11, 2008
19,442
1,155
126
I tested just my own example after modification of the if statement.
It works as well. Removing the ==1 did the trick. I think i made a mistake as well. The example i posted here works with me too now. I copied the example into my source file and it worked at once.

Indeed i must have made some mistake. I call it a day. I have improved a lot already yesterday, cleaned up hundreds of lines of code. Next week is going to be a busy week at work. Tomorrow it is relax day and tonight it is movie night.
:thumbsup:
 

Markbnj

Elite Member <br>Moderator Emeritus
Moderator
Sep 16, 2005
15,682
13
81
www.markbetz.net
Thank you for the reply.

I know about the Endian information.

But the code example i got is a general example.
And with how it works, it should not matter about the Endian format.
It is just a table generator computing a fixed result for a fixed input.
y = x / A , 0 <= x <= 255. A is a constant.
This function does not read in the data. That is another function that will make use of the stored results in this table.

When i have it working, i use the table for an embedded system based on an ARM (No CRC unit :( ) where i will write an embedded c function first to get it working and a hand optimized assembly function after that. An assembly routine that makes optimum use of the 32 bit width ARM architecture and ARM machine instructions. I want to make it as efficient as possible. But first i have to understand the basics. At the moment i am at a loss. Back to the drawing board.

Ah yeah, I misread it. The dividend variable is a 32-bit int. I thought it was the uint16_t.
 
May 11, 2008
19,442
1,155
126
I do not know how i do it. I just managed to crash the linker : :oops:
It must be a gift...

Linking...
crc_functions.obj : fatal error LNK1000: Internal error during IncrCalcPtrs
Version 9.00.30729.01
ExceptionCode = C0000005
ExceptionFlags = 00000000
ExceptionAddress = 0045B8C0 (00400000) "C: \Program Files\Microsoft Visual Studio 9.0\VC\bin\link.exe"
NumberParameters = 00000002
ExceptionInformation[ 0] = 00000000
ExceptionInformation[ 1] = 0000001C
CONTEXT:
Eax = 00000000 Esp = 0012F2B0
Ebx = 3FFF0000 Ebp = 0012F2D4
Ecx = 7C91056D Esi = 40091ACC
Edx = 40009494 Edi = 00000000
Eip = 0045B8C0 EFlags = 00010293
SegCs = 0000001B SegDs = 00000023
SegSs = 00000023 SegEs = 00000023
SegFs = 0000003B SegGs = 00000000
Dr0 = 00000000 Dr3 = 00000000
Dr1 = 00000000 Dr6 = 00000000
Dr2 = 00000000 Dr7 = 00000000

But after cleaning and again compiling it was solved.:thumbsup:
 
May 11, 2008
19,442
1,155
126
No , no corrupted files.

I changed a pointer that is passed as a variable of a function in c -source file. After that i called the function from another function in the same file. I did not clean the project first. I just builded immediately and it caused a crash. After cleaning and building, it worked and no crashes of the linker. Normally i always do a clean first and then a compile when i make some major changes. In the past i did not always do this and it caused some strange effects. Anyway, this was only a minor change thus i assumed it would be okay. I guess it was not okay. But i am already on track again. Soon i will be able to hand optimize my crc calculator by writing it in assembly for my ARM system(no crc unit :( ). Then it is table driven and hand optimized for maximum speed. I know, many examples out there to use. But it is a hobby and i like to figure it out on my own as an exercise. Later on , i will be able to use my acquired skills for my work as well. Increasing my value.