I have a problem where as input I have a large byte array (typically >1K length) which has a computed CRC32. I need to replace a small chunk of the array with different values, and recalculate the CRC. Is there an efficient way to do this without looping through the entire original byte array? I suspect it's mathematically possible to take as inputs the original CRC, the bytes to be replaced, the new bytes, and calculate the new CRC with an algorithm whose loop size is just the number of bytes to be replaced, but it's outside my area of expertise, hence, just a suspicion. Thanks,
3
votes
A buffer of size 1KiB is not anywhere near large. Have you implemented a straight forward solution (recomputing the CRC over the entire buffer) and profiled it for bottlenecks? As for your suspicion: CRC calculation relies on state derived from previous input. You cannot just walk in and calculate the CRC based on the replaced bytes, new bytes, and location.
– IInspectable
I have done nothing rigorous to prove this, but it seems in only small instances could you prove that even one bit isn't changed, so the code complexity would *far, far* outweigh any runtime optimization... also that is for a very vanilla CRC, not one that is using a hamming code or similar...
– Grady Player
There is a way if you are always replacing the same exact area of the array (e.g. always index 400 for length 30). Is that the case? Or, do you replace arbitrary parts of the array?
– Craig Estey
In fact, that is the case. I can say that the same starting index and the length are always the same.
– R. Vreeland
This is a question better suited for the Mathematics stack exchange. It is equivalent to: I have calculated the remainder of dividing this large polynomial by this small one. Now I want to change a few coefficients in the large polynomial. Is there a shortcut to calculating the remainder? Oh, by the way all the coefficients are either 0 or 1, and everything is done modulo 2, if that helps.
– Kaz
2 Answers
2
votes
Yes, this can be done. Though at the 1K-byte level it would very likely be faster to just recompute the CRC on the whole thing.
As noted by Dmitry Rubanovich, you can use the fact that a CRC is a linear function where addition is replaced by exclusive-or. You can do better however than just avoiding the recalculation up to the first change. Wherever you have a long string of no changes, which is a long string of zeros in the exclusive-or of the two messages, you can compute the change in the CRC over that string in O(log(n)) time instead of O(n) time.
The way this is done is to generate a series of 32x32 bit matrices, each of which represents the application of a power-of-2 zero bytes to the CRC. E.g. 1, 2, 4, 8, etc. zero bytes. This can be done ahead of time, producing a static table. Then in order to, for example, evolve a CRC by 137 zeros, you multiply the current CRC as a bit vector by the matrices for 128, 8, and 1 zeros. The matrix multiplication is over GF(2), that is, addition is replaced by exclusive-or and multiplication is replaced by the and operation.
You can see an example of how this is done in the zlib function for combining CRC's.
A quick calculation using instruction counts indicates that the logarithmic approach will be faster on average for strings of zeros longer than about 300 bytes.
0
votes
CRC is linear. So CRC(A xor B) = CRC(A) xor CRC(B). If you know exactly which bits you are changing, you can decompose the changing of the bits into an XOR operation. Then you only have to compute CRC starting with the highest significant bit of B. If it's close to the end of the stream, there will be a lot of leading zeros. You don't need to run the CRC over them because CRC of 0 is 0 (crc is a remainder of dividing a polynomial by another polynomial... if the leading polynomial coefficients are 0, you can ignore them).
