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 protected] [mailto:[email protected]] On Behalf Of Hal Murray Sent: Friday, July 29, 2011 22:17 To: [email protected] Cc: [email protected] 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 protected] https://www.ietf.org/mailman/listinfo/tictoc _______________________________________________ TICTOC mailing list [email protected] https://www.ietf.org/mailman/listinfo/tictoc
