Electronic – Revising CRC value after data adjustment

crc

I have a 181 bytes data stream with 4 bytes CRC32 value at the end. The entire message length is 185 bytes.

The data stream is stored in the FPGA onchip memory and waiting to put into wire by TCP.

Before sending out the message, there are some 32 bits data in the data stream need to be modified resulting revising CRC value is needed.

The location of the new bit values are from 41st – 63rd bit (starting the 5th byte) from the LSB of the stream.

As the CRC is within the tcp message payload, the tcp header and ip checksum have to be revised as well.

Currently I have to build a pipeline module for re-calculating the CRC like this:

module crc32 (
input rst,
input clk,
input [255:0] in_data,
input crc_en,
output crc_out
);

It works but it need to spend 181 bytes / 256 bits ~= 6 cycles for revising the CRC value of a 181 bytes TCP message.

Although the CRC is located at the end of the business message, the tcp header checksum (which is more significant than the tcp payload) can be revised only when the new CRC value is calculated. That's the reason why it have to wait 6 cycles.

Is there any smart revising CRC algorithm so that I can use less number of cycles to revise the CRC of a modified data stream?

Ideas:

  1. Is there any way to recalculate CRC based on the old CRC value? CRC(new) = revise(CRC(old))?
  2. I learn from this paper that by patching the data stream to maintain the old CRC value.

CH5 : GETTING A CHOSEN CRC BY ALTERING A CHOSEN POSITION

It is interesting but it require to recalculate crc from n bit to m bit

where n = start bit location of modified field

m = start bit location of the patch field

which doesn't look good for saving clock cycles.

Best Answer

1) Yes

2) It's complicated.

The CRC is a linear operation on GF(2) (GF(2) is just the fancy discrete-math way of saying binary, added modulo 2). So each bit of your 32 bits will have the same effect on your two CRCs in the add-modulo 2-sense.

The really bone-headed (but possibly good enough) way to do this is to have a table of 32 32-bit words. For each bit in your field that you flip, XOR the CRC with the corresponding word from the table. That should work just fine. The actual words in that table are the CRCs for the whole data stream with every bit but the bit in question set to zero.

There are alternate ways to do this -- you could have four tables of 256 words each, for instance, with each byte of your 32-bit variable field selecting one word from its corresponding table. That saves you XORs at the cost of keeping the table in memory.

If it works, you probably want to generate your long message with that variable section set to zero, then you won't have to compute which bits have flipped, because you know that whatever bits are set to 1 in your replacement variable field are the flipped bits.

Going from an n-bit CRC backwards to an n-bit field that you can freely set should have the same linearity property; if you can tack some bits on to the packet after your desired message you should be able to decide ahead of time what you want the packet CRC to be, and then set it after the fact. Or you can do the same trick I mention above, with each bit in the message corresponding to a different 32-bit pattern in the free space that you need to toggle.

Related Topic