The SIMPLE algorithm above is a good starting point because it corresponds directly to the theory presented so far, and because it is so SIMPLE. However, because it operates at the bit level, it is rather awkward to code (even in C), and inefficient to execute (it has to loop once for each bit). To speed it up, we need to find a way to enable the algorithm to process the message in units larger than one bit. Candidate quantities are nibbles (4 bits), bytes (8 bits), words (16 bits) and longwords (32 bits) and higher if we can achieve it. Of these, 4 bits is best avoided because it does not correspond to a byte boundary. At the very least, any speedup should allow us to operate at byte boundaries, and in fact most of the table driven algorithms operate a byte at a time. For the purposes of discussion, let us switch from a 4-bit poly to a 32-bit one. Our register looks much the same, except the boxes represent bytes instead of bits, and the Poly is 33 bits (one implicit 1 bit at the top and 32 "active" bits) (W=32). 3 2 1 0 Bytes
+----+----+----+----+
Pop! <-- | | | | | <----- Augmented message
+----+----+----+----+ 1<------32 bits------>The SIMPLE algorithm is still applicable. Let us examine what it does. Imagine that the SIMPLE algorithm is in full swing and consider the top 8 bits of the 32-bit register (byte 3) to have the values: t7 t6 t5 t4 t3 t2 t1 t0In the next iteration of SIMPLE, t7 will determine whether the Poly will be XORed into the entire register. If t7=1, this will happen, otherwise it will not. Suppose that the top 8 bits of the poly are g7 g6.. g0, then after the next iteration, the top byte will be: t6 t5 t4 t3 t2 t1 t0 ??
+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Reminder: + is XOR]The NEW top bit (that will control what happens in the next iteration) now has the value t6 + t7*g7. The important thing to notice here is that from an informational point of view, all the information required to calculate the NEW top bit was present in the top TWO bits of the original top byte. Similarly, the NEXT top bit can be calculated in advance SOLELY from the top THREE bits t7, t6, and t5. In fact, in general, the value of the top bit in the register in k iterations can be calculated from the top k bits of the register. Let us take this for granted for a moment. Consider for a moment that we use the top 8 bits of the register to calculate the value of the top bit of the register during the next 8 iterations. Suppose that we drive the next 8 iterations using the calculated values (which we could perhaps store in a single byte register and shift out to pick off each bit). Then we note three things:
The top byte of the register now doesn't matter. No matter how many times and at what offset the poly is XORed to the top 8 bits, they will all be shifted out the right hand side during the next 8 iterations anyway.
The remaining bits will be shifted left one position and the rightmost byte of the register will be shifted in the next byte
AND
While all this is going on, the register will be subjected to a series of XOR's in accordance with the bits of the pre-calculated control byte.
Now consider the effect of XORing in a constant value at various offsets to a register. For example: 0100010 Register
...0110 XOR this
..0110. XOR this
0110... XOR this
-------
0011000
-------The point of this is that you can XOR constant values into a register to your heart's delight, and in the end, there will exist a value which when XORed in with the original register will have the same effect as all the other XORs. Perhaps you can see the solution now. Putting all the pieces together we have an algorithm that goes like this: While (augmented message is not exhausted)
Begin
Examine the top byte of the register
Calculate the control byte from the top byte of the register
Sum all the Polys at various offsets that are to be XORed into
the register in accordance with the control byte
Shift the register left by one byte, reading a new message byte
into the rightmost byte of the register
XOR the summed polys to the register
EndAs it stands this is not much better than the SIMPLE algorithm. However, it turns out that most of the calculation can be precomputed and assembled into a table. As a result, the above algorithm can be reduced to: While (augmented message is not exhaused)
Begin
Top = top_byte(Register);
Register = (Register << 24) | next_augmessage_byte;
Register = Register XOR precomputed_table[Top];
EndThere! If you understand this, you've grasped the main idea of table-driven CRC algorithms. The above is a very efficient algorithm requiring just a shift, and OR, an XOR, and a table lookup per byte. Graphically, it looks like this: 3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Augmented message
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+
v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+Algorithm
Shift the register left by one byte, reading in a new message byte.
Use the top byte just rotated out of the register to index the table of 256 32-bit values.
XOR the table value into the register.
Goto 1 iff more augmented message bytes.
In C, the algorithm main loop looks like this: r=0;
while (len--)
{
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *++;
r^=table[t];
}where len is the length of the augmented message in bytes, p points to the augmented message, r is the register, t is a temporary, and table is the computed table. This code can be made even more unreadable as follows: r=0;
while (len--)
r = ((r << 8) | *++) ^ t[(r >> 24) & 0xFF];This is a very clean, efficient loop, although not a very obvious one to the casual observer not versed in CRC theory. We will call this the TABLE algorithm.
+----+----+----+----+
Pop! <-- | | | | | <----- Augmented message
+----+----+----+----+ 1<------32 bits------>The SIMPLE algorithm is still applicable. Let us examine what it does. Imagine that the SIMPLE algorithm is in full swing and consider the top 8 bits of the 32-bit register (byte 3) to have the values: t7 t6 t5 t4 t3 t2 t1 t0In the next iteration of SIMPLE, t7 will determine whether the Poly will be XORed into the entire register. If t7=1, this will happen, otherwise it will not. Suppose that the top 8 bits of the poly are g7 g6.. g0, then after the next iteration, the top byte will be: t6 t5 t4 t3 t2 t1 t0 ??
+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Reminder: + is XOR]The NEW top bit (that will control what happens in the next iteration) now has the value t6 + t7*g7. The important thing to notice here is that from an informational point of view, all the information required to calculate the NEW top bit was present in the top TWO bits of the original top byte. Similarly, the NEXT top bit can be calculated in advance SOLELY from the top THREE bits t7, t6, and t5. In fact, in general, the value of the top bit in the register in k iterations can be calculated from the top k bits of the register. Let us take this for granted for a moment. Consider for a moment that we use the top 8 bits of the register to calculate the value of the top bit of the register during the next 8 iterations. Suppose that we drive the next 8 iterations using the calculated values (which we could perhaps store in a single byte register and shift out to pick off each bit). Then we note three things:
The top byte of the register now doesn't matter. No matter how many times and at what offset the poly is XORed to the top 8 bits, they will all be shifted out the right hand side during the next 8 iterations anyway.
The remaining bits will be shifted left one position and the rightmost byte of the register will be shifted in the next byte
AND
While all this is going on, the register will be subjected to a series of XOR's in accordance with the bits of the pre-calculated control byte.
Now consider the effect of XORing in a constant value at various offsets to a register. For example: 0100010 Register
...0110 XOR this
..0110. XOR this
0110... XOR this
-------
0011000
-------The point of this is that you can XOR constant values into a register to your heart's delight, and in the end, there will exist a value which when XORed in with the original register will have the same effect as all the other XORs. Perhaps you can see the solution now. Putting all the pieces together we have an algorithm that goes like this: While (augmented message is not exhausted)
Begin
Examine the top byte of the register
Calculate the control byte from the top byte of the register
Sum all the Polys at various offsets that are to be XORed into
the register in accordance with the control byte
Shift the register left by one byte, reading a new message byte
into the rightmost byte of the register
XOR the summed polys to the register
EndAs it stands this is not much better than the SIMPLE algorithm. However, it turns out that most of the calculation can be precomputed and assembled into a table. As a result, the above algorithm can be reduced to: While (augmented message is not exhaused)
Begin
Top = top_byte(Register);
Register = (Register << 24) | next_augmessage_byte;
Register = Register XOR precomputed_table[Top];
EndThere! If you understand this, you've grasped the main idea of table-driven CRC algorithms. The above is a very efficient algorithm requiring just a shift, and OR, an XOR, and a table lookup per byte. Graphically, it looks like this: 3 2 1 0 Bytes
+----+----+----+----+
+-----<| | | | | <----- Augmented message
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+
v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+Algorithm
Shift the register left by one byte, reading in a new message byte.
Use the top byte just rotated out of the register to index the table of 256 32-bit values.
XOR the table value into the register.
Goto 1 iff more augmented message bytes.
In C, the algorithm main loop looks like this: r=0;
while (len--)
{
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *++;
r^=table[t];
}where len is the length of the augmented message in bytes, p points to the augmented message, r is the register, t is a temporary, and table is the computed table. This code can be made even more unreadable as follows: r=0;
while (len--)
r = ((r << 8) | *++) ^ t[(r >> 24) & 0xFF];This is a very clean, efficient loop, although not a very obvious one to the casual observer not versed in CRC theory. We will call this the TABLE algorithm.
解决方案 »
免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货