Subject: Re: [TICTOC] The Need for Checksum Extension

From: Yaakov Stein <[email-masked]>
Date: Fri, 5 Aug 2011 23:22:02 +0000

Hal

Yes, I know that CRC CAN be updated rather than recomputed,
but it is not as easy as you imply.

The linearity means that if we have computed the CRC on two bit sequences of equal length
and are interested in knowing the result for the xor of those two sequences,
then we don't have to work very hard.

However, that is NOT what is needed for an update, 
as we don't know the CRC of the sequence which contains the header change and all the zeros
for the entire message.

To perform an update efficiency you have to build M = the 32 by 32 bit matrix of the CRC, 
matrix multiply this matrix by itself enough times to move it to the offset where the field changes
(this can be done off-line), matrix*vector multiply with the original and changed fields and xor these together, 
and then xor all of these with the original CRC.

I agree that this is in principle faster than doing the entire CRC.
However, since the offsets of the changes can vary (depending on VLAN tags, etc)
and there are at least two places with changes (the CF and the UDP checksum),
it is cumbersome.

Y(J)S

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Hal Murray
Sent: Friday, July 29, 2011 22:17
To: [email-masked]
Cc: [email-masked]
Subject: Re: [TICTOC] The Need for Checksum Extension

> CRC can not be readily updated, and so needs to iterate over the entire
> payload, but is still calculated on the fly. So the UDP checksum, which CAN
> be readily updated, can certainly be. 

The CRC can be updated rather than recalculating the CRC of the whole message.

I'm rusty on this stuff and it probably doesn't matter since it takes about 
as much hardware/cycles as recomputing the CRC of the whole packet.  It might 
be interesting if you are concerned about corruption while a packet is in 
memory.

The key idea is linearity:
  CRC(A+B) = CRC(A)+CRC(B) where + is XOR.
In this context, A is the original message and B is the XOR of the old and 
new messages.  That's the XOR of the old/new words you are changing padded 
with enough 0s to line up correctly.  You end up computing the CRC of a 
pseudo message rather than the real message.  (Don't forget to include the 
UDP checksum as well as the slot you are changing.)

-- 
These are my opinions, not necessarily my employer's.  I hate spam.

_______________________________________________
TICTOC mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tictoc