Checksum principle

Checksum is widely used in TCP/IP protocol family, used to verify IP, TCP, UDP data, the principle is relatively simple, the calculation of Checksum steps as follows: 1) in the data sender, first will test and the field itself, will be tested pairs with adjacent bytes into 16 bit integer, matching all together, at the same time to carry to the check and the low byte, we will get the checksum is defined as a, then will check and take the record for the -a, put the -a in the checksum field sent to the network. 2) If no bits have changed during the data transmission, the checksum calculated at the destination should be equal to a+(-a), that is, the binary inverse is -0(all 1s), and its binary inverse is 0(all 0s). So at the destination, an uncorrupted group will always calculate a checksum of 0.

Checksum features

Although the checksum calculation principle is very simple, it contains many mathematical properties in it. Here is a brief introduction:

  1. The checksum has no limit on the length of the data to be checked. That is, the length of the data to be checked does not affect the result of the checksum.
  2. The calculation result of the checksum does not depend on the characteristics of the hardware platform, that is, for the same set of data, the calculation result of the big-end platform and the small-end platform is the same.

For example, the following set of data is the group to be verified:

Memory address 0x00 0x01 0x02 0x03 0x04 Data 0xF1 0xF2 0xF3 0xF4 0xF5Copy the code
Calculate the sum of all data on the small end platform: calculate the sum of all data: 0xF2F1 + 0xF4F3 + 0x00F5 = 0x01E8D9 Add the carry to the low byte: 0xE8D9 + 0x01 = E8DA Negate :0x1725 Position of the sum in memory: Memory address 0x05 0x06 Checksum 0x25 0x17Copy the code
Calculate the sum of all the data on the big-enended platform: calculate the sum of all the data: 0xF1F2 + 0xF3F4 + 0xF500 =0x02DAE6 Add the carry to the low bytes: 0xDAE6 + 0x02 = 0xDAE8 Invert: 0x2517 Position of the checksum in memory: Memory address 0x05 0x06 Checksum 0x25 0x17Copy the code

It can be seen that the checksum calculated on different platforms is the same in memory, that is, the result is the same.

Checksum implementation

C: Checksum C: Checksum C: Checksum

unsigned short checksum(unsigned short * addr, int count) { long sum = 0; While (count > 1) {/* This is the inner loop */ sum += *(unsigned short*)addr++; Count -= 2} /* If the length of the data is odd, add a byte (0) after the byte, and then convert it to a 16-bit integer and add it to the checksum calculated above. */ if( count > 0 ) { char left_over[2] = {0}; left_over[0] = *addr; sum += * (unsigned short*) left_over; } /* Compress 32bit data into 16bit data, that is, increase the carry to the lower bytes of the checksum until there is no carry. */ while (sum>>16) sum = (sum & 0xFFFF) + (sum>>16); /* return sum */ return ~sum; }Copy the code