Simple and practical single chip microcomputer CRC fast algorithm

1 Introduction

CRC (Cyclic Redundancy Code) verification technology is widely used in the field of measurement, control and communication. In many cases, CRC calculation is implemented by dedicated hardware, but for small and low-cost single-chip microcomputer systems, if CRC verification is to be implemented without the support of these hardware, the first thing to be solved is how to complete the CRC calculation efficiently and quickly through software, that is, the problem of CRC algorithm.

Two slightly different algorithms are provided here. One is suitable for 51 series microcontrollers with larger program space, and the other is suitable for PIC microcontrollers with very demanding program space. These algorithms calculate byte by byte, using only table lookup and simple XOR operations, so the calculation process is quite simple and the calculation speed is very fast.

The following briefly describes the CRC principle, and then uses the CRC-CCITT standard generating polynomial as an example to illustrate the algorithm, and gives a 51 series microcontroller subroutine and a PIC microcontroller subroutine.

2CRC Principle

The CRC check principle is actually to add an r-bit binary check code (sequence) after a p-bit binary data sequence, thus forming a binary sequence with a total length of n=p+r bits. For example, the p-bit binary data sequence D=[dp-1dp-2......d1d0], the r-bit binary check code R=[rr-1rr-2....r1r0], the resulting n-bit binary sequence is M=[dp-1dp-2......d1d0rr-1rr-2....r1r0]; there is a certain specific relationship between the check code attached to the data sequence and the content of the data sequence. If one or some bits in the data sequence are wrong due to interference or other reasons, this specific relationship will be destroyed. Therefore, by checking this relationship, the correctness of the data can be verified.

The check code R is obtained by performing a binary division remainder operation on the data sequence D. It is divided by a (r+1)-bit binary sequence G=[grgr-1....g1g0] called a generating polynomial, which can be expressed in polynomial form as

（1）

Here, xrD(x) means shifting the data sequence D to the left by r bits (i.e. adding r 0 bits to the end of D), Q(x) represents the quotient obtained by this division, and R(x) is the required remainder. This operation relationship can also be expressed as formula (2):

（2）

Among them, Re[] means to perform a remainder operation on the expression in the brackets.

The coding calculation of the check code is as described above, and the check process is to directly perform a division remainder operation on the M sequence, that is,

（3）

Or expressed as

（4）

If the obtained remainder R(x) is zero, it means that the data is correct, otherwise it is considered that an error has occurred.

3 Basic ideas of fast algorithm

Here we only take the CRC-CCITT standard generator polynomial as an example. CRC-CCITT is a 17-bit generator polynomial G = [10001000000100001], which is expressed in polynomial form as G(x) = x16 + x12 + x5 + 1. The binary number of the check code R generated by it is 16 bits (2 bytes).

The operation of the microcontroller is performed in the form of bytes, so the algorithm should be operated in bytes. Here, the binary sequence composed of bytes is called a "byte sequence". Obviously, the data sequence, check code and the sequence M composed of the two of the microcontroller are all byte sequences, or "multi-byte sequences".

In fact, the problem that this algorithm is to solve is how to perform division remainder operations on multi-byte sequences.

3.1 Multi-byte sequence operation rules

First, suppose there is an 8×i-bit binary sequence consisting of i bytes m1, m2, ..., mi-1, mi, and express it in byte form as Mi = [m1m2......mi-1mi], then take the first (i-1) bytes of Mi to form a Mi-1 sequence, Mi-1 = [m1m2......mi-1]. The relationship between these two sequences can be expressed by a polynomial as Mi(x) = x8Mi-1(x) + mi(x), where mi(x) is the binary polynomial representation of the byte mi, and x8Mi-1(x) means shifting the Mi-1 sequence left by one byte.

For sequence Mi-1,

(5)

Among them, the two-byte sequence remainder Ri-1=［hi-1li-1］.

For the Mi sequence, we can get

(6)

The first term of this result is an integer, so it is independent of the remainder. Thus, the remainder can only appear in the second term. Therefore, the remainder operation on x8Ri-1(x)+mi(x) is equivalent to the remainder operation on Mi(x), which can be expressed in the form of formula (4):

(7)

x8Ri-1(x)+mi(x) represents a three-byte sequence [hi-1li-1mi] composed of Ri-1 and mi, and the remainder operation on this three-byte sequence is equal to the remainder operation on the Mi sequence, and the result is the remainder of the Mi sequence Ri＝[hili]. Similarly, for a Mi+1 sequence (which has one more byte mi+1 than the Mi sequence), the operation on the three-byte sequence [hilimi+1] is equivalent to the operation on the Mi+1 sequence, and the result is the remainder of the Mi+1 sequence Ri+1＝[hi+1li+1].

Obviously, this reflects a law of recursive operation as shown in Figure 1. It can be seen that each recursive operation is a calculation of a three-byte sequence, so how to calculate the three-byte sequence simply and quickly is another key to this algorithm.

3.2 Three-byte sequence calculation

When it comes to simplicity and speed, people naturally think of using a table lookup method, such as calculating all the remainders of the three-byte sequence in advance and placing them in a table called a "remainder table" for easy access at any time. However, such a table is too large and requires 224 units, which means it takes up 225 bytes of storage space, which is absolutely unacceptable for a single-chip microcomputer. Therefore, it is necessary to find a way to reduce the storage space occupied.

Figure 1 Recursive calculation steps

Suppose there is a three-byte sequence Tabc = [abc], a Ta00 = [a00] and a two-byte sequence Tbc = [bc]. The relationship between them can be expressed in polynomial form as Tabc (x) = Ta00 (x) + Tbc (x). Therefore, for Ta00,

（8）

For Tabc,

Among them, Qa00 is an integer and has nothing to do with the remainder; while Ra00 and Tbc are both two-byte sequences, so their sum (modulo 2 addition, that is, XOR operation) is still a two-byte sequence (16 bits in binary, less than the 17 bits of the generating polynomial), so it is the remainder Rabc of Tabc, that is

（9）

This shows that the operation of the three-byte sequence Tabc=[abc] can be decomposed into two steps, as shown in FIG2 .

1. By looking up the remainder table (Table 1), read the remainder Ra00 = [ha00la00] of Ta00 = [a00];

2. Perform an XOR operation on Ra00 and [bc] to obtain the remainder of [abc] Rabc＝[habclabc], that is, habc＝ha00Åb, labc＝la00Åc.

Since only one byte in [a00] is not zero, the remainder table for [a00] only requires 256 cells, which occupies 512 bytes.

Figure 2 Calculation method of the three-byte sequence [abc]

4 Algorithms applicable to 51 series microcontrollers

The method described above can be directly applied to 51 series microcontrollers, because the 512-byte remainder table is not a problem at all for their program storage capacity.

The calculation is directly performed through the above recursive process. Each recursion is a calculation of a three-byte sequence: the first is [m1m2m3], the result is [h3l3]; the second is [h3l3m4], the result is [h4l4]; ..., the i-th time is [hi+1li+1mi+2], the result is [hi+2li+2]; ...; the last is [hk+1lk+1mk+2], the final result is [hl]. If there are k data bytes, recurse k times. The following is a three-byte sequence calculation subroutine for each recursive operation. Note that before the first call, m1, m2 and m3 are stored in R0, R1 and R2 respectively (when the subroutine returns, the calculation results will be stored in R0 and R1). Starting from the second call, each time before calling, you only need to store the bytes involved in this operation in R2 (the second time is m4, the third time is m5, ..., the i-th time is mi+2, ...). When the last call returns, R0 and R1 store the final results h and l respectively.

This subroutine has only 12 instructions, so it is very simple and only takes up 16 machine cycles. In other words, it only takes 16 machine cycles to calculate each byte, which is more than ten times faster than traditional software algorithms.

Although the remainder table shown in Table 1 only occupies 512 bytes of program storage space, it is still too large for the PIC chip and needs to be compressed. The idea is this:

Decompose Ta00 = [a00] into Te00 = [e00] and Tf00 = [f00], and make the upper half byte of byte e the same as the upper half byte of a but the lower half byte is zero, and make the lower half byte of byte f the same as the lower half byte of a but the upper half byte is zero, and then use Te00 and Tf00 to generate a remainder table to replace the Ta00 remainder table. Since only half of the bytes in Te00 and Tf00 are not zero, each remainder table only needs 16 units (32 bytes), and the two remainder tables only occupy 64 bytes in total, which can meet the requirements of the PIC microcontroller.

From the above ideas, we can know that e＝a∧0F0H, f＝a∧0FH, so we can get Ta00＝Te00ÅTf00. At the same time, we can also prove that the relationship between their remainders is Ra00＝Re00ÅRf00, that is, if we set Ra00＝[ha00la00], Re00＝[he00le00] and Rf00＝[hf00lf00], then ha00＝he00Åhf00, la00＝le00Ålf00. In this way, the calculation of the three-byte sequence [a00] can be carried out by the method shown in Figure 3, where the remainders of [e00] and [f00] are shown in Tables 2 and 3.

Obviously, for PIC microcontrollers, the calculation of the three-byte sequence [abc] needs to be carried out by combining the two methods shown in Figures 2 and 3. The following is a PIC subroutine. Its use is basically the same as the 51 series microcontroller subroutine described above, that is, before the first call, m1, m2 and m3 are stored in the general registers BYTEa, BYTEb and BYTEc respectively; starting from the second call, each time before the call, it is only necessary to store the bytes involved in this operation in BYTEc (the second time is m4, the third time is m5,..., the i-th time is mi+2,...). Each time the subroutine returns, the calculation result will be stored in BYTEa and BYTEb. After the last call returns, BYTEa and BYTEb will store the final results h and l respectively. In the subroutine, in addition to BYTEa, BYTEb and BYTEc, ADDR, RESULTh and RESULTl are also general registers.