CRC table generator.

[William Gaatjes]

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 ?

// 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]

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."

 

[William Gaatjes]

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.

 

[William Gaatjes]

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.

 

[Venix]

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.

 

[William Gaatjes]

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]

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.

 

[William Gaatjes]

I do not know how i do it. I just managed to crash the linker :
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:

 

[Markbnj]

Access violation in the linker. Excellent! Good work. Never seen that one before .

 

[Cogman]

Access violation in the linker. Excellent! Good work. Never seen that one before .

Yep. Perhaps one of his object files became corrupted. Either way, pretty unique.

 

[William Gaatjes]

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.