---
title: Internet Checksum
date: 2024-12-09
excerpt: Notes from designing an Internet checksum lab, covering parallel summation and incremental checksum updates.
tags:
  - Network
  - Linux
  - C
cover: https://assets.vluv.space/cover/Networks/计网拾遗1.webp
updated: 2026-07-08 21:17:39
lang: en
i18n:
  cn: /Internet_Checksum
  translation: 2
---

<script type="module" src="/js/components/tab.js"></script>

The Internet checksum, also known as the IPv4 header checksum, is widely used by IPv4 and ICMP at the network layer and by TCP and UDP at the transport layer, though the range of data each protocol covers differs.

| Protocol | Checksum coverage                    |
| -------- | ------------------------------------ |
| IPv4     | IP Header                            |
| ICMP     | IP Header + ICMP Data                |
| TCP      | PseudoHeader + TCP Header + TCP Data |
| UDP      | PseudoHeader + UDP Header + UDP Data |

The IPv6 header contains no checksum field, which simplifies the work of routers. Data integrity is left to higher-layer protocols, which is why IPv6 makes the UDP checksum mandatory.

### Internet Checksum Algo

#### Common Solution

First, group the header byte array into pairs of 2 bytes and convert them into a sequence of 16-bit integers, corresponding to `uint16_t` in C's `<stdint.h>`.

The following code shows how to merge two bytes into one 16-bit integer using bitwise operations or multiplication.

```c
uint_8 byte1 = 0x45;
uint_8 byte2 = 0x00;
// Shift byte1 left by 8 bits, then OR it with byte2
uint_16 word = (byte1 << 8) | byte2; // 0x4500
// If the header length is odd (in bytes), pad the last byte with a trailing zero
uint_16 last_word = last_bytes << 8);
```

Next, compute the 1's complement sum. One way to do this: add all the 16-bit integers together and store the result in a 32-bit integer, call it `sum`. If the high 16 bits of `sum` are nonzero, add the high 16 bits to the low 16 bits. Repeat until the high 16 bits are zero.

Finally, take the complement of the sum. That is the checksum.

> 1's complement sum
> On a 2's complement machine, the 1's complement sum must be computed by means of an "end around carry", i.e., any overflows from the most significant bits are added into the least significant bits.
>
> <cite>RFC 1071</cite>

The following example may help in understanding the algorithm above.

```wikitext
An IP4 packet with a 20-byte header, shown in hexadecimal:

   IP4 Header Bytes:
1. 0x45, 0x00, 0x00, 0x14
2. 0x00, 0x00, 0x00, 0x00
3. 0x40, 0x00, 0x00, 0x00
4. 0xA8, 0xE0, 0x17, 0xE7
5. 0x85, 0xE9, 0xE8, 0xBC

sum:
0x4500 + 0x0014 + 0x0000 + 0x0000 + 0x4000 + 0x0000 + 0xA8E0 + 0x17E7 + 0x85E9 + 0xE8BC = 0x0002B480

wraparound:
0x0002 + 0xB480 = 0xB482

checksum = ~(0xB482) = 0x4B7D
```

#### Parallel Summation

When the checksum covers a small range, such as a 20-byte IP4 header, the algorithm above performs acceptably.

For TCP, however, the checksum covers `(pseudo-header、TCP header、TCP data)`, which can be fairly large, so efficiency matters.

RFC-1071 Parallel Summation describes a way to compute the checksum in parallel, which improves efficiency considerably.

```wikitext
0x45, 0x00, 0x00, 0x14  -> uint_32t 0x4500_0014
0x00, 0x00, 0x00, 0x00  -> uint_32t 0x0000_0000
0x40, 0x00, 0x00, 0x00  -> uint_32t 0x4000_0000
0xA8, 0xE0, 0x17, 0xE7  -> uint_32t 0xA8E0_17E7
0x85, 0xE9, 0xE8, 0xBC  -> uint_32t 0x85E9_E8BC

sum: (sum should now be stored as uint_64t)
0x4500_0014 + 0x0000_0000 + 0x4000_0000 + 0xA8E0_17E7 + 0x85E9_E8BC = 0x0000_0001_B3CA_00B7

wraparound:
0x0000_0000_0001_B3CA + 0x00B7 = 0x0000_0000_0001_B481
0x0000_0000_0000_0001 + 0xB481 = 0x0000_0000_0000_B482

The corresponding pseudocode:
while (sum > 0xFFFF) {
    sum = (sum & 0xFFFF) + (sum >> 16);
}

checksum = ~(0xB482) = 0x4B7D
```

<x-tabs>

<x-tab title="common_solution" active>

```c
uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {
    /**
     * Compute the Internet checksum
     *
     * @hex_bytes_array: a hexadecimal byte array, e.g. {0x45, 0x00, 0x00, 0x14,
     * 0x00, 0x00, 0x00, 0x00}
     * @count: length of the byte array; watch out for odd lengths
     * @return the computed 16-bit checksum
     */
    uint32_t sum = 0;  // Store the sum in 32 bits; a 16-bit result risks overflow

    size_t i = 0;
    while (i + 1 < count) {
        uint16_t word = (hex_bytes_array[i] << 8) | hex_bytes_array[i + 1];
        sum += word;
        i += 2;
    }

    if (count % 2 == 1) {
        sum += hex_bytes_array[count - 1] << 8;
    }

    // wraparound
    while (sum > 0xFFFF) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }
    // Return the 1's complement of the sum: checksum = ~sum
    return (uint16_t)~sum;
}
```

</x-tab>

<x-tab title="Parallel_Summation">

```c
uint16_t calculate_checksum(uint8_t* hex_bytes_array, size_t count) {
    uint64_t sum = 0;  // Use uint64_t to prevent overflow
    size_t i = 0;

    // Split the byte array into 32-bit chunks and add them in parallel
    while (i + 3 < count) {
        // Read 4 bytes as one 32-bit integer
        sum +=
            (uint32_t)(hex_bytes_array[i] << 24 | hex_bytes_array[i + 1] << 16 |
                       hex_bytes_array[i + 2] << 8 | hex_bytes_array[i + 3]);
        i += 4;
    }

    if (i < count) {
        uint32_t word = 0;
        // Read the remaining bytes as one 32-bit integer
        for (size_t j = 0; i < count; i++, j++) {
            word |= hex_bytes_array[i] << (24 - j * 8);
        }
        sum += word;
    }

    // wraparound
    while (sum > 0xFFFF) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }
    // Return the 1's complement of the sum: checksum = ~sum
    return (uint16_t)~sum;
}
```

</x-tab>

</x-tabs>

### Incremental Update Checksum

RFC 1071 first sketched the idea of incremental updates, RFC 1141 gave a technical implementation, and RFC 1624 later corrected some errors in RFC 1141.

You can implement incremental checksum updates following RFC 1624. The formula:

```wikitext
HC  - old checksum in header
C   - one's complement sum of old header
HC' - new checksum in header
C'  - one's complement sum of new header
m   - old value of a 16-bit field
m'  - new value of a 16-bit field


HC' = ~(C + (-m) + m')
    = ~(~HC + ~m + m')
```

Below is a sample program. The code itself is simple; the point is to understand how incremental checksum updates work.

```c
#include <stdint.h>
#include <stdio.h>

uint16_t incremental_update_checksum(uint16_t old_checksum, uint16_t old_value,
                                     uint16_t new_value) {
    uint32_t res = ~(~old_checksum + ~old_value + new_value);
    return (uint16_t)(res);
}

int main() {
    printf("Incremental update checksum test\n");
    uint16_t old_checksum = 0xDD2F;
    uint16_t old_value = 0x5555;
    uint16_t new_value = 0x3285;
    uint16_t new_checksum =
    incremental_update_checksum(old_checksum, old_value, new_value);
    printf("Incremental update checksum: 0x%04X\n", new_checksum);
}

Output
Incremental update checksum test
Incremental update checksum: 0x0000
```

## Reference

- [RFC 791 INTERNET PROTOCOL](https://datatracker.ietf.org/doc/html/rfc791) Written by Jon Postel et al. in 1981, it defines the IPv4 specification; the IP4 Datagram format in this post follows this document.
- [RFC 1071 Computing the Internet Checksum](https://datatracker.ietf.org/doc/html/rfc1071): Describes how to compute the Internet checksum and introduces several optimizations.
- [RFC 1141 Incremental Updating of the Internet Checksum](https://datatracker.ietf.org/doc/html/rfc1141): Describes an algorithm for incrementally updating the checksum.
- [RFC 1624 Computation of the Internet Checksum via Incremental Update](https://datatracker.ietf.org/doc/html/rfc1624) RFC 1624 fixes the problems in the incremental update algorithm described in RFC 1141.