C++: the Internet checksum
Compute the 16-bit ones'-complement checksum used by IP, TCP, and UDP, and use it to detect corruption.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
std::uint16_t checksum(const std::vector<std::uint8_t>& bytes) {
std::uint32_t sum = 0;
for (std::size_t i = 0; i + 1 < bytes.size(); i += 2) {
sum += (bytes[i] << 8) | bytes[i + 1];
}
if (bytes.size() % 2 == 1) {
sum += bytes.back() << 8;
}
while (sum >> 16) {
sum = (sum & 0xFFFF) + (sum >> 16);
}
return static_cast<std::uint16_t>(~sum);
}
void show(const char* label, std::uint16_t value) {
std::cout << label << "0x" << std::hex << std::setw(4) << std::setfill('0') << value << std::dec << "\n";
}
int main() {
std::vector<std::uint8_t> packet = {0x00, 0x01, 0xf2, 0x03, 0xf4, 0xf5, 0xf6, 0xf7};
std::uint16_t c = checksum(packet);
show("checksum: ", c);
packet.push_back(static_cast<std::uint8_t>(c >> 8));
packet.push_back(static_cast<std::uint8_t>(c & 0xFF));
show("intact packet: ", checksum(packet));
packet[2] ^= 0x01;
show("one bit flipped: ", checksum(packet));
}checksum: 0x220d intact packet: 0x0000 one bit flipped: 0xfeff
Explanation
A checksum lets a receiver detect accidental bit errors. The Internet checksum (RFC 1071) adds the data as 16-bit words, folds any carry out of bit 15 back into the low bits, and takes the bitwise complement of the result. A sender stores it in the header.
The receiver adds everything including the checksum field. If nothing was corrupted, the sum folds to 0xFFFF and the complement is 0. The check is cheap but weak: it catches most single errors, and cannot detect some reorderings and compensating changes, which is why link layers add stronger CRCs.
Explore the dry run
#include <cstdint>#include <iomanip>#include <iostream>#include <vector> std::uint16_t checksum(const std::vector<std::uint8_t>& bytes) { std::uint32_t sum = 0; for (std::size_t i = 0; i + 1 < bytes.size(); i += 2) { sum += (bytes[i] << 8) | bytes[i + 1]; } if (bytes.size() % 2 == 1) { sum += bytes.back() << 8; } while (sum >> 16) { sum = (sum & 0xFFFF) + (sum >> 16); } return static_cast<std::uint16_t>(~sum);} void show(const char* label, std::uint16_t value) { std::cout << label << "0x" << std::hex << std::setw(4) << std::setfill('0') << value << std::dec << "\n";} int main() { std::vector<std::uint8_t> packet = {0x00, 0x01, 0xf2, 0x03, 0xf4, 0xf5, 0xf6, 0xf7}; std::uint16_t c = checksum(packet); show("checksum: ", c); packet.push_back(static_cast<std::uint8_t>(c >> 8)); packet.push_back(static_cast<std::uint8_t>(c & 0xFF)); show("intact packet: ", checksum(packet)); packet[2] ^= 0x01; show("one bit flipped: ", checksum(packet));}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Join two bytes into one 16-bit word and add it to a 32-bit accumulator. | sum accumulates 16-bit words | — | |
| End-around carry: add any overflow beyond 16 bits back into the low half. | sum folded to 0xddf2 | — | |
| The complement of 0xddf2 is 0x220d, the value from RFC 1071's example. | sum folded to 0xddf2 | checksum: 0x220d | |
| With the checksum appended, the receiver's calculation gives 0, meaning no error was detected. | sum folded to 0xddf2 | checksum: 0x220d intact packet: 0x0000 | |
| Flipping one bit changes the sum, so the receiver gets a non-zero result and detects the corruption. | sum folded to 0xddf2 | checksum: 0x220d intact packet: 0x0000 one bit flipped: 0xfeff |
Cost and common mistakes
O(n) time and O(1) extra space for n bytes.
- Network byte order is big-endian. The shifts above build each word that way no matter what the CPU's own byte order is.
- A result of 0 means no error was detected, not that the data is certainly correct.
Try it yourself
Why is the checksum field set to zero while the sender computes it?
Reveal answer and reasoning
Because the checksum covers the whole header; including the old field value would change the sum. The sender zeroes it, computes, and then stores the result.