Rate this page

Flattr this

Calculate an Internet Protocol checksum in C

Content

Tested on

Debian (Lenny)

Objective

To calculate an Internet Protocol checksum in C

Background

RFC 791 defines the following checksum algorithm for use when constructing the header of an IPv4 datagram:

The checksum field is the 16 bit one's complement of the one's complement sum of all 16 bit words in the header. For purposes of computing the checksum, the value of the checksum field is zero.

The same algorithm is used by a number of other IP-based protocols including TCP, UDP and ICMP. Implementation techniques are discussed in RFC 1071, RFC 1141 and RFC 1624.

Scenario

Suppose that you wish to send an ICMP echo request using a raw socket. Like all ICMP messages this contains a checksum that is calculated using the algorithm described above. Given the message to be sent, you wish to calculate the required checksum.

Method

Overview

The checksum can be calculated using the following algorithm:

  1. Set the checksum field to zero.
  2. Pad the data to an even number of bytes.
  3. Reinterpret the data as a sequence of 16-bit unsigned integers that are in network byte order.
  4. Calculate the sum of the integers, subtracting 0xffff whenever the result reaches 0x10000 or greater.
  5. Calculate the bitwise complement of the sum. This is the required value of the checksum field.

One’s complement notation has two representations for the number zero: normal zero (0x0000 in this case) and negative zero (0xffff). It is not completely clear how these should be handled:

In the interests of consistency, the implementations described here prefer normal zero over negative zero in all cases (even where the data is all zeros). This is achieved by initialising the accumulated sum to negative zero (0xffff), which makes no difference to the final result except in the case where nothing is added to it.

To exactly replicate the behaviour of the example given in RFC 1071, the accumulator should instead be initialised to normal zero (0x0000).

Implementation (optimised for clarity)

Here is a near-literal implementation of the algorithm described above:

uint16_t ip_checksum(void* vdata,size_t length) {
    // Cast the data pointer to one that can be indexed.
    char* data=(char*)vdata;

    // Initialise the accumulator.
    uint32_t acc=0xffff;

    // Handle complete 16-bit blocks.
    for (size_t i=0;i+1<length;i+=2) {
        uint16_t word;
        memcpy(&word,data+i,2);
        acc+=ntohs(word);
        if (acc>0xffff) {
            acc-=0xffff;
        }
    }

    // Handle any partial block at the end of the data.
    if (length&1) {
        uint16_t word=0;
        memcpy(&word,data+length-1,1);
        acc+=ntohs(word);
        if (acc>0xffff) {
            acc-=0xffff;
        }
    }

    // Return the checksum in network byte order.
    return htons(~acc);
}

The data should be passed to the function in network byte order with the checksum field already zeroed. The result is returned in network byte order, so is ready to be written directly into the checksum field.

If there is an odd byte at the end of the data then this is treated as a special case so that padding can be done on the fly. The calls to memcpy are needed to avoid breaking the strict aliasing rules, which prevent an arbitrary type from being safely cast to a uint16_t.

Implementation (optimised for speed)

The following implementation uses two techniques to improve performance:

uint16_t ip_checksum(void* vdata,size_t length) {
    // Cast the data pointer to one that can be indexed.
    char* data=(char*)vdata;

    // Initialise the accumulator.
    uint64_t acc=0xffff;

    // Handle any partial block at the start of the data.
    unsigned int offset=((uintptr_t)data)&3;
    if (offset) {
        size_t count=4-offset;
        if (count>length) count=length;
        uint32_t word=0;
        memcpy(offset+(char*)&word,data,count);
        acc+=ntohl(word);
        data+=count;
        length-=count;
    }

    // Handle any complete 32-bit blocks.
    char* data_end=data+(length&~3);
    while (data!=data_end) {
        uint32_t word;
        memcpy(&word,data,4);
        acc+=ntohl(word);
        data+=4;
    }
    length&=3;

    // Handle any partial block at the end of the data.
    if (length) {
        uint32_t word=0;
        memcpy(&word,data,length);
        acc+=ntohl(word);
    }

    // Handle deferred carries.
    acc=(acc&0xffffffff)+(acc>>32);
    while (acc>>16) {
        acc=(acc&0xffff)+(acc>>16);
    }

    // If the data began at an odd byte address
    // then reverse the byte order to compensate.
    if (offset&1) {
        acc=((acc&0xff00)>>8)|((acc&0x00ff)<<8);
    }

    // Return the checksum in network byte order.
    return htons(~acc);
}

The maximum length of message that can be processed by this function is limited to approximately 16 gigabytes by the number of deferred carries that can be accumulated. In this unlikely event that this is insufficient then the upper half of the accumulator can be folded into the lower half as often as is necessary to prevent an overflow. This is more likely to be required when processing 16-bit blocks using a 32-bit accumulator, in which case only 128 kilobytes can be processed without the risk of overflow.

Testing

Here is an example of how an 8-byte ICMP echo request might be constructed using the icmphdr structure type provided by glibc:

struct icmphdr req;
req.type=8;
req.code=0;
req.checksum=0;
req.un.echo.id=htons(0x1234);
req.un.echo.sequence=htons(1);
req.checksum=ip_checksum(&req,8);

The resulting message, as a hexadecimal byte stream, should be as follows:

08 00 E5 CA 12 34 00 01

Variations

Verifying a checksum

There are two ways in which checksums of the type described here can be verified:

The second method is likely to be simpler, quicker and more convenient in most cases. If you should decide to use the first method then some care is needed with regard to negative and normal zero. RFC 1624 recommends that either be accepted (in accordance with the robustness principle: be conservative in what you send, liberal in what you accept). This can be achieved by normalising the received checksum before performing the comparison.

(No special action is required when using the first method, provided that the checksum algorithm used to perform the verification consistently returns normal zero in preference to negative zero. A minor optimisation would be to omit the final inversion and compare the accumulator with negative zero.)

Avoiding the use of memcpy

If the data were presented to the checksum function as an array of uint16_t then the calls to memcpy could be omitted. There are two ways to achieve this. The safer method is to assemble the message within a union:

union {
    uint16_t words[740];
    struct icmphdr icmp;
} message;

This is allowed by C99, but not by C89 or C++. It has the disadvantage that the union must be constructed by the caller if copying is to be avoided, and this may not always be practicable.

The alternative is to reinterpret the data by means of a type cast. This would not normally be safe in any variant of C or C++, and would be quite likely to fall foul of the aliasing rules that are specified by C99. However in some compilation environments it can be made safe (or at least, less unsafe) by disabling strict application of the aliasing rules. In the case of GCC this is done using the -fno-strict-aliasing option or the may_alias attribute.

It should be noted that the removal of memcpy will not necessarily improve the performance of of the checksum function because the compiler may already be able to achieve the same result without assistance. For example, GCC can do this in some cases when optimisation is enabled. It would be advisable to determine whether there is any benefit to be gained before making non-portable changes to the source code.

Omitting the conversion between network and host byte order

The checksum algorithm described here has the property that it works equally well when the upper and lower halves of each 16-bit block are reversed. For example, applying it to the sequence:

0x4500, 0x001c, 0x03de, 0x0000, 0x4001, 0x0000, 0x7f00, 0x0001, 0x7f00, 0x0001

gives a checksum of 0x7901, whereas applying it to:

0x0045, 0x1c00, 0xde03, 0x0000, 0x0140, 0x0000, 0x007f, 0x0100, 0x007f, 0x0100

gives 0x0179. This due to the carry from the most significant byte of each block being fed back into the least significant byte and vice versa. It might therefore appear that the calls to ntohs and htons made above are redundant. This is almost, but not quite, correct.

The usual behaviour of ntohs is to either do nothing or reverse the byte order. In either of these cases the calls to ntohs and htons cancel out and could be removed. However POSIX states quite clearly that an arbitrary rearrangement of the bit pattern could occur, so if you want to be certain that the algorithm will behave as intended then an explicit conversion to host byte order is necessary.

Further reading

Tags: c