Calculation of CRC in the main static data stream

Background:

I have a memory section, 1024 bytes. The last 1020 bytes will always be the same. The first 4 bytes will change (product serial number). I need to calculate CRC-16 CCITT (start 0xFFFF, mask 0x1021) for the entire memory partition, CRC_WHOLE .

Question:

Is it possible to calculate CRC only for the first 4 bytes, CRC_A , and then use a function like the one below to calculate the full CRC? We can assume that the checksum for the last 1020 bytes, CRC_B , is already known.

 CRC_WHOLE = XOR(CRC_A, CRC_B) 

I know this formula does not work (tried), but I hope something like this exists.

+10
source share
1 answer

Yes. You can see how in zlib crc32_combine() . If you have two sequences A and B, then pure CRC AB is exceptional or CRC from A0 and CRC 0B, where 0 is a sequence of zero bytes with the length of the corresponding sequence, that is, B and A, respectively.

For your application, you can pre-compute one statement that very quickly applies 1020 zeros to the CRC of your first four bytes. You can then use the exclusive or pre-computed CRC of 1020 bytes.

Update:

Here is my post from 2008 with a detailed explanation of what @ArtemB discovered (which I forgot about):

crc32_combine() in zlib is based on two key tricks. For the future, we put off the fact that the standard 32-bit CRC is a preliminary and post-air conditioner. We will deal with this later. Suppose now that the CRC, which does not have such conditioning, and therefore begins with a register filled with zeros.

Trick # 1: CRC are linear. Therefore, if you have stream X and stream Y the same length and exclusive or two streams are beaten to get Z, i.e. Z = X ^ Y (using the notation C for exceptional or), then CRC (Z) = CRC (X) ^ CRC (Y). For the problem under consideration, we have two streams A and B of different lengths, which we want to combine into stream Z. What do we have CRC (A) and CRC (B). What we want is a quick way to calculate CRC (Z). The trick is to build X = A combined with the length (B) of the zero bits and Y = the length (A) of the zero bits concatenated with B. Therefore, if we represent concatenation simply by matching the characters, X = A0, Y = 0B, then X ^ Y = Z = AB. Then we have CRC (Z) = CRC (A0) ^ CRC (0B).

Now we need to know CRC (A0) and CRC (0B). CRC (0B) is simple. If we feed a bunch of zeros for the CRC machine, starting from zero, the register is still filled with zeros. As if we did nothing. Therefore, CRC (0B) = CRC (B).

CRC (A0) requires more work. Taking non-zero CRC and feeding zeros on the CRC machine do not leave her alone. Each change to zero is the contents of the register. So, to get CRC (A0), we need to set the register to CRC (A), and then pass the length (B) of zeros through it. Then we can exception or result from this with CRC (B) = CRC (0B), and we get what we want CRC (Z) = CRC (AB). Voila!

Well, voila is actually premature. I was not at all happy with this answer. I did not want the calculations to take time in proportion to the length of B. This would not save a time comparable to simply setting the register in CRC (A) and starting thread B through. I decided that there should be a faster way to calculate the effect of feeding n zeros to the CRC machine (where n = length (B)). So that leads us to:

Trick # 2: The CRC machine is a linear state machine. If we know that the linear transformation that occurs when we feed zero to the machine, then we can more efficiently perform operations on this transformation to find the transformation that results from feeding n zeros to the machine.

Converting the feed of one zero bit to a CRC machine is fully represented by a 32x32 binary matrix. To apply, we multiply the matrix by register, taking register as a 32-bit column vector. For matrix multiplication into binary (that is, above the Galois field 2), the role of multiplication is played and played, and the role of addition is played exclusively by or'ing.

There are several different ways of constructing a magic matrix, which is a conversion caused by giving a CRC a single zero bit. One way is to notice that each column of the matrix is ​​what you get when your register starts with one in It. So, the first column is what you get when the register is 100 ... and then file zero, the second column starts at 0100 ... etc. (Those called basic vectors.) You can see this simply by matrix multiplication with these vectors. Matrix multiplication selects a matrix column corresponding to the location of a single.

Now for the trick. When we have the magic matrix, we can defer the contents of the original register for a while, and instead use the conversion for one zero to calculate the conversion for n zeros. We could just multiply n copies of the matrix together to get a matrix for n zeros. But this is even worse than just starting n zeros through the machine. However, there is an easy way to avoid most of these matrix multiplications in order to get the same answer. Suppose we want to know the conversion to run eight zero bits or one byte through. Let me name the magic matrix, which is the running zero through: M. We could do seven matrix multiplications to get R = MxMxMxMxMxMxMxM. Instead, let's start with MxM and call it P. Then PxP - MxMxMxM. Let us call Q. Then QxQ is equal to R. So now we have reduced seven multiplications to three. P = MxM, Q = PxP and R = QxQ.

Now I'm sure that you get the idea for an arbitrary n number of zeros. We can very quickly generate transformation matrices M k , where M k is the transformation for a 2 k run. (In the paragraph above, M 3 is equal to R.) We can make M 1 through M k only with k matrix multiplications, starting with M 0 = M. k, should be like the number of bits in the binary representation n. We can then select those matrices in which there are binary representations of n and multiply them together to get the conversion of running n zeros through the CRC machine. Therefore, if n = 13, calculate M 0 x M 2 x M 3 .

If j is the unit number in the binary representation of n, then we simply j - 1 more than matrix multiplications. So, we have the total number k + j - 1 matrix multiplications, where j <= k = floor (logbase2 (n)).

Now we take our quickly constructed matrix for n zeros and multiply that CRC (A) gets CRC (A0). We can calculate CRC (A0) in O (log (n)) time, not O (n). We are exclusive with either CRC (B) and Voila! (indeed, this time), we have CRC (Z).

What zlib does crc32_combine() .

I will leave this as an exercise for the reader on how to deal with the pre-and post-conditioning of the CRC register. You just need to apply the linearity observations above. Hint: You do not need to know the Length (A). In fact, crc32_combine() accepts only three arguments: CRC (A), CRC (B), and length (B) (in bytes).

+30
source

All Articles