use

In the process of data transmission, no matter how well designed the transmission system is, there will always be errors, such errors may cause one or more frames transmitted over the link to be corrupted (a bit error, 0 to 1, or 1 to 0), so that the receiver receives the wrong data. In order to improve the accuracy rate of receiving data as much as possible, it is necessary to conduct error detection on the data before receiving the data, and only when the detection result is correct, the data is really accepted by the receiver. There are many detection methods, such as parity check, Internet check and cyclic redundancy check. Cyclic redundancy check is a calculation method used to verify the accuracy of digital transmission on a communication link

CRC is everywhere: The famous communication protocol X.25 FCS(Frame error detection sequence) uses CRC-CCITT, WinRAR, NERO, ARJ, LHA and other compression tools software uses CRC32, disk drive read and write uses CRC16, common image storage formats such as GIF and TIFF also use CRC as a means of error detection

The principle of

Let’s say A wants to transmit A data from 0 to B, and the signal may change to 1 because of external interference and B can’t tell whether the message is transmitted correctly or not.

The simplest way to describe detection is to send three zeros in A row if A wants to pass A zero. When B receives data, if the signal is disturbed, for example, the message B receives is 010, then B can find that the data transmitted is inconsistent. It indicates that there is interference in the signal, and there is A high probability that the message A wants to transmit is 0

However, there is also a possibility that B receives 111, so error checking is not 100% guarantee that the data is correct, but through some mathematical model to reduce the probability to a minimum

CRC cyclic redundancy check is the same as other error detection methods. It adds (n-k) redundant bits after k bits of data D to be transmitted

The first of the above three 000 is the information bit followed by the two 00 check bits

The mathematical model of CRC is very complex (you can look it up yourself if you are interested). It is based on a polynomial to calculate a set of check codes, which are used to check whether data is changed or transmitted incorrectly during transmission

Generally speaking, CRC calculation involves the following concepts

  • Parametric models —- Models in the standard
  • Polynomial value —- short for the generated item, expressed in hexadecimal
  • Initial value —- This is the initial preset value of the register (CRC) at the start of the algorithm, expressed in hexadecimal
  • Result xOR value —- Computations result xor with this parameter to get the final CRC value

Calculation example

Assume that the original data is 10110011

Parameter model: CRC-4

  1. Polynomial :x^4+x^3+1 the corresponding 2-base code 2^4+2^3+1=25 ->11001
  2. Because the check code is 4 bits, we need to add 4 zeros after 10110011 to get 101100110000. The result can be obtained by “modular 2 division” (logic or ^)

  1. CRC^101100110000 gets 101100110100 and sends it to the receiver.
  2. After receiving 101100110100, the receiver divided by 11001(removed by “modulo 2 division”), and the remainder is 0, there is no error

Generally speaking, CRC has a variety of implementation methods, direct generation method and lookup table method.

Direct generation method Power smaller format suitable for CRC time, when the CRC power increased gradually, because of its complex Xor logical operation will drag on the system operation speed, no longer recommend the use of direct generation method, replaced by the look-up table method, will be part of the data block M operation ahead of schedule, and will result in the array, the system began to perform operation, In effect, the previous operation is omitted and the calculation starts directly from the similar middle position, so the efficiency will be improved.

In CRC calculation, you can use Normal or Reversed check. The two methods will affect the final check code in a mirror image relationship. But this has no effect on the success rate of CRC itself, just whether it is a forward or a mirror walk.

Table establishment method:

If the first place of the register is 1, move the register one bit to the right (move the remaining MSB of Mx^r to the MSB of the register (high octet)), and then xor to the last R bit of G(x), otherwise just move the register one bit to the right (move the remaining LSB of Mx^r (low octet) to the LSB of the register)

The method of computing CRC check Code (look-up table method)

  1. Performs XOR operations between the previous CRC and the new byte to be checked;
  2. The calculated value is indexed in the pre-generated code table to obtain the corresponding value (known as the remainder);
  3. XOR operation is performed with the obtained value and the CRC right-shifted value;
  4. If the data to be checked has already been processed, the result of step (4) is the final CRC check code. If there is more data to process, go to step (1) again

Background knowledge

Before we discuss the implementation of CRC, we need to know the knowledge about binary data in Javacript. The first thing we need to know is ArrayBuffer, which is defined in Mdn as follows

The ArrayBuffer object is used to represent a generic, fixed-length buffer of raw binary data.

To put it more informally, an ArrayBuffer is an object that allocates a contiguous area of memory for storing data

new ArrayBuffer(256)
Copy the code

You can’t manipulate the contents of an ArrayBuffer directly, but rather through a type array object or DataView object

The so-called array objects of type refer to things like 👇

Int8Array(a);Uint8Array(a);Uint8ClampedArray(a);Int16Array(a);Uint16Array(a);Int32Array(a);Uint32Array(a);Float32Array(a);Float64Array(a);Copy the code

Javascript code CRC-32-IEEE 802.3 standard

For example, the polynomial used by CRC-32-IEEE 802.3

0xEDB88320 Reverse verification 🐴

The initial value of 0 XFF

// table lookup preconstructs a table
// In CRC-16 and 32, the data to be measured is 8 bits at a time, i.e. one byte at a time.
// The table has 2^8 = 256 table values. A byte has eight bits of binary, and each bit has two choices.
let table: Uint32Array = new Uint32Array(256);
for (var i = 0; i < 256; i++) {
    var c = i;
    for (var k = 0; k < 8; k++) { 
        c = 
            (c & 1)?/ / the LSM is 1
            (c >>> 1) ^ 0xEDB88320   // Take reverse verification
            : c >>> 1; // Move the register 1 bit to the right
    }
    table[i] = c;
}

function crc32(bytes:Uint8Array, start: number, length: number) {
    start = start || 0;
    length = length || (bytes.length - start);
    // The top is used to select the position to be checked
    var crc = -1; 
    for (var i = start, l = start + length; i < l; i++) {
        crc = (crc >>> 8) ^ table[(crc ^ bytes[i]) & 0xFF]; }return crc ^ (-1);

}
Copy the code

Refer to the article

www.cnblogs.com/masonzhang/… Bbs.pediy.com/thread-1719…