Checksums

Why Checksums Matters

A file arrives with the right length and a plausible header, but one stored bit has changed. Reading it successfully does not reveal whether its bytes still match what was written. A checksum adds a small deterministic value computed from the agreed data; the receiver recomputes it and compares the result with the stored or transmitted value.

This lesson covers three practical constructions: Fletcher-16 uses two byte-sized modular sums; Adler-32 uses two larger sums modulo a prime; and CRC-32 uses polynomial arithmetic over bits. You will trace the updates, implement all three, and verify a framed payload in Python, C++, and Java.

A checksum is extra evidence of consistency. A mismatch proves the checked bytes, tag, or agreed parameters do not match. A match cannot prove that the data are unchanged, because different messages can have the same finite checksum. These algorithms detect many accidental errors; they do not correct errors, compress data, or authenticate who supplied the bytes.

The programs make the distinction concrete. They check known values for 123456789, pack and unpack a small record, reject a sample corruption, and exhibit a pair of different payloads that collide under both Fletcher-16 and Adler-32. The full worked arithmetic uses ABC so every inner CRC bit step can be inspected.

Core Concepts and Terminology

Inputs and outputs. The mathematical input is a sequence of octets $d_1,\ldots,d_n$, each an integer in $[0,255]$. Text must first become bytes using an agreed encoding; these examples use explicit ASCII bytes. The output is a fixed-width integer that an enclosing format serializes into check bytes.

Selected Fletcher-16 variant. Start $A=B=0$. For each byte $d$ update $$ A\leftarrow(A+d)\bmod255,\qquad B\leftarrow(B+A)\bmod255, $$ using the new $A$ in the second update. Return $F=(B\ll8)\mathbin{\mathrm{OR}}A$. This is the direct, zero-initialized, modulo-$255$ variant with $B$ in the high byte. No complement or adjustment to make the whole record sum to zero is applied. Fletcher variants differ in word width, initialization, zero representation, and byte order, so the name alone is insufficient for interoperability.

Adler-32. Start $A=1,B=0$ and use the same recurrence with prime modulus $65521$: $$ A\leftarrow(A+d)\bmod65521,\qquad B\leftarrow(B+A)\bmod65521. $$ Return $\operatorname{Adler}=(B\ll16)\mathbin{\mathrm{OR}}A$. This construction is specified in RFC 1950. The starting one matters: for empty input Adler-32 is 00000001, while this Fletcher variant is 0000.

The first sum depends on byte values; the second also depends on their positions. For three bytes $a,b,c$, Fletcher's second sum is $3a+2b+c$ modulo $255$, while Adler's is $3+3a+2b+c$ modulo $65521$. This position sensitivity catches many rearrangements that a single additive sum misses, but not every change.

CRC-32 parameters. CRC is a family, not one algorithm. The programs implement CRC-32/ISO-HDLC, often called IEEE CRC-32, with width $32$, normal polynomial word 04C11DB7, reflected feedback word EDB88320, initial register FFFFFFFF, reflected input/output convention, and final XOR FFFFFFFF. Its check value for ASCII 123456789 is CBF43926; empty input gives 00000000. RFC 1952 specifies the CRC used by gzip. The custom frame below has its own serialization and is not a gzip record.

Polynomial intuition. Interpret a bit string as coefficients of a polynomial over $\mathrm{GF}(2)$: coefficients are zero or one, addition/subtraction is XOR, and multiplication by $x$ shifts bits. A degree-$w$ generator defines a remainder of fewer than $w$ degrees. CRC's shifts and conditional XORs implement that remainder calculation with the chosen initialization, reflection, and finalization.

For a small unrelated teaching example, data bits 1101 and generator 1011 mean $m(x)=x^3+x^2+1$ and $g(x)=x^3+x+1$. Dividing the zero-extended bits 1101000 by 1011 gives remainder 001, so the systematic codeword 1101001 is divisible by the generator. This miniature width-$3$ example explains polynomial checking; it is not the parameterized CRC-32 implementation.

Coverage and serialization. A checksum must cover precisely defined bytes. Our custom frame contains magic 43 53, version 01, an algorithm ID, a four-byte big-endian payload length, the payload, and a two- or four-byte big-endian tag. The tag covers the header followed by the payload, excluding the tag itself. For the same payload, a payload-only checksum and a frame checksum generally differ. The figure makes that boundary explicit.

How Checksums Works, Step by Step

Fletcher and Adler byte loop. Choose the specified modulus and starting state. For each byte, add it to $A$ and reduce modulo the base; then add that updated $A$ to $B$ and reduce again. After the last byte, concatenate the two fields in the agreed order. Reducing after every byte is easy to audit and prevents accumulator growth. Optimized implementations can defer reductions only after proving safe arithmetic bounds.

For example, after ASCII A, Fletcher is $(A,B)=(65,65)$ and Adler is $(66,66)$. On B, decimal $66$, Fletcher becomes $(131,196)$ while Adler becomes $(132,198)$. Updating $B$ from the old $A$ would compute a different checksum.

Reflected CRC-32 byte loop. Start register $R=\texttt{FFFFFFFF}$. For each byte, XOR that byte into the low eight register bits. Repeat exactly eight times:

1. Inspect the old least-significant bit.
2. Shift the register right by one with zero fill.
3. If that old bit was one, XOR the reflected polynomial word EDB88320 into the shifted register.

After all bytes, XOR the register with FFFFFFFF to return the finalized CRC. In symbols, one inner step is $$ R'\!=\!(R\gg1)\oplus \begin{cases} \texttt{EDB88320},&R\bmod2=1,\\ 0,&R\bmod2=0. \end{cases} $$ The condition uses the pre-shift register. The reflected loop already realizes the reflected input/output convention; do not reverse its final result again. Do not finalize after every byte and feed that finalized value directly into the next byte update.

Verification and the framed round trip. The sender constructs the header, computes the checksum over header plus payload, and appends the integer tag in big-endian order. The receiver first checks byte validity, header length, magic, version, algorithm ID, and declared length. It then recomputes the same protected bytes and compares the stored integer tag. Return the payload only when those checks pass.

This is framing and verification, not recovery of a message from a checksum. The payload is retained in the record. A checksum alone does not contain enough information to reconstruct arbitrary original data.

The flowchart describes the three checksum loops and their final comparison. It assumes the input bytes and algorithm selection have already passed the API's range checks. A packet parser performs its structural validation before entering this calculation.

flowchart TD
    A["Choose exact algorithm and initialize state"] --> B{"Another protected byte?"}
    B -->|"Yes"| C{"Fletcher or Adler?"}
    C -->|"Yes"| D["Update first sum modulo base"]
    D --> E["Update second sum using new first sum"]
    E --> B
    C -->|"CRC"| F["XOR byte into low register bits"]
    F --> G["Perform eight zero-fill shifts and conditional XORs"]
    G --> B
    B -->|"No"| H{"CRC selected?"}
    H -->|"Yes"| I["Apply final XOR"]
    H -->|"No"| J["Pack second and first sum fields"]
    I --> K["Computed checksum value"]
    J --> K
    K --> L{"Matches stored expected value?"}
    L -->|"No"| R["Reject inconsistent record"]
    L -->|"Yes"| Z["Accept checksum check; extract payload"]

Worked Example with a Full Trace

The worked payload is ASCII ABC, bytes 41 42 43, or decimal $65,66,67$. This trace computes payload-only checksums. The framed example later includes the header as additional protected bytes.

All Fletcher-16 updates. Start $A=B=0$.

1. A: $A=(0+65)\bmod255=65$; $B=(0+65)\bmod255=65$.
2. B: $A=(65+66)\bmod255=131$; $B=(65+131)\bmod255=196$.
3. C: $A=(131+67)\bmod255=198$; $B=(196+198)\bmod255=139$.

The final tag is $(139\ll8)\mathbin{\mathrm{OR}}198=\texttt{8BC6}$. Notice the last second-sum addition is $394$ before reduction; replacing modulo $255$ by an eight-bit mask would yield $138$ instead of $139$.

All Adler-32 updates. Start $A=1,B=0$.

1. A: $A=1+65=66$; $B=0+66=66$.
2. B: $A=66+66=132$; $B=66+132=198$.
3. C: $A=132+67=199$; $B=198+199=397$.

These small values need no wrap modulo $65521$. The result is $(397\ll16)\mathbin{\mathrm{OR}}199=\texttt{018D00C7}$.

Every CRC-32 bit step. Start raw register FFFFFFFF. Each list below contains all eight register states after the byte has been XORed in and its bits have been processed. They are unfinalized; only the last overall register receives the final XOR.

• Byte A (41): incoming FFFFFFFF; after byte XOR FFFFFFBE. Steps 1–4: 7FFFFFDF, D2477CCF, 849B3D47, AFF51D83. Steps 5–8: BA420DE1, B09985D0, 584CC2E8, 2C266174.
• Byte B (42): incoming 2C266174; after byte XOR 2C266136. Steps 1–4: 1613309B, E6B11B6D, 9EE00E96, 4F70074B. Steps 5–8: CA008085, 88B8C362, 445C61B1, CF96B3F8.
• Byte C (43): incoming CF96B3F8; after byte XOR CF96B3BB. Steps 1–4: 8A73DAFD, A8816E5E, 5440B72F, C798D8B7. Steps 5–8: 8E74EF7B, AA82F49D, B8F9F96E, 5C7CFCB7.

For the first bit of A, FFFFFFBE has old low bit zero, so a right shift alone gives 7FFFFFDF. Its old low bit is one for the next step: shift to 3FFFFFEF, then XOR EDB88320 to get D2477CCF. Continue as recorded. After C, the raw register is 5C7CFCB7; final XOR with FFFFFFFF gives A3830348.

Known-vector check and complete framing. The standalone programs also checksum ASCII 123456789, obtaining Fletcher 1EDE, Adler 091E01DE, and CRC CBF43926. These values are for those nine bytes alone.

The custom CRC frame for that payload is 43 53 01 03 00 00 00 09 31 32 33 34 35 36 37 38 39 32 D0 4B 2A. Its header is eight bytes, its payload nine, and its trailer four. The trailer 32 D0 4B 2A is the CRC of the seventeen header-plus-payload bytes; it is intentionally different from the payload-only CB F4 39 26. The receiver checks the frame, then extracts the original nine bytes.

An exact collision. Messages $[10,20,30]$ and $[11,18,31]$ have the same total $60$ and the same weighted total: $$ 3\cdot10+2\cdot20+30=3\cdot11+2\cdot18+31=100. $$ Both therefore have Fletcher tag 643C and Adler tag 0067003D. CRC distinguishes this pair, but it also has other collisions. A shared prefix and equal payload length preserve this Fletcher/Adler collision, so adding the same frame header does not repair it.

Implementation in Python, C++, and Java

Each panel is one standalone program. Use Python 3, C++17, or Java 8+; save the Java panel as Main.java. The samples contain imports/includes, explicit bytes, known-vector checks, framing round trips, corruption rejection, and the collision demonstration. No third-party package is needed.

Algorithm IDs are 1 for the specified direct Fletcher-16, 2 for Adler-32, and 3 for CRC-32/ISO-HDLC. checksum(data, kind) returns a nonnegative integer tag. pack(payload, kind) returns a byte-valued frame, and unpack(frame) validates it and returns a copy of the payload. A checksum result is not a compressed or encrypted version of its input.

The sample frame format is: two magic bytes 43 53; version 01; one algorithm byte; four big-endian length bytes; exactly that many payload bytes; and the tag as two big-endian bytes for Fletcher or four for Adler/CRC. Checksum coverage is the entire header followed by payload, excluding the trailer. Concatenated frames require an external parser to delimit them; unpack accepts exactly one complete frame.

Payloads may contain $0$ through $65536$ bytes. The standalone checksum API permits up to $65544$ bytes so it can checksum the largest header-plus-payload region. A frame may occupy at most $65548$ bytes. Every byte element must be an integer in $[0,255]$. Python accepts lists, tuples, bytes, and bytearray, and rejects Boolean and floating-point elements; algorithm IDs must be actual integers. Java rejects null arrays. C++ uses integer vectors through its static types.

C++ uses uint32_t for CRC registers and tags. Java uses nonnegative long values and zero-fill >>> for the register shifts; Python's bounded nonnegative register also shifts right with zero fill. The algorithm keeps registers within the 32-bit range. Modular sums are reduced every byte, so Fletcher additions never exceed $509$ for $A$ or $508$ for $B$, and Adler additions never exceed $65775$ for $A$ or $131040$ for $B$. These small intermediate bounds avoid overflow in the implementations.

Length parsing uses a wider integer in C++/Java before the supported-size check. The parser rejects a declared length above the limit or any mismatch between declared payload length, tag width, and actual frame length. It never uses an unchecked four-byte length to allocate an output buffer.

The exception labels agree across languages: ALGORITHM for unsupported IDs; BYTE for invalid byte input; SIZE for an oversized input container; TRUNCATED for fewer than eight header bytes; MAGIC or VERSION for unsupported framing; LENGTH for an invalid declared/actual record length; and CHECKSUM for a tag mismatch. These checks run in the order shown, so a frame with multiple defects reports the first detected one. An error returns no payload and does not mutate the input.

Arrays or lists of integer byte values are convenient teaching containers; they are not necessarily one-byte-per-element storage. The reported frame sizes count logical wire bytes. Use a packed byte buffer or write each validated value as one octet when persisting a frame. The Python and C++ sample assertions check both known values and round trips; Java uses explicit checks even when Java assertions are disabled.

MAX_PAYLOAD = 65536
NAMES = {1: "FLETCHER16", 2: "ADLER32", 3: "CRC32"}


def width(kind):
    if type(kind) is not int or kind not in (1, 2, 3):
        raise ValueError("ALGORITHM")
    return 2 if kind == 1 else 4


def check_bytes(data, limit):
    if not isinstance(data, (list, tuple, bytes, bytearray)):
        raise ValueError("BYTE")
    if len(data) > limit:
        raise ValueError("SIZE")
    if any(type(b) is not int or not 0 <= b <= 255 for b in data):
        raise ValueError("BYTE")


def checksum(data, kind):
    width(kind)
    check_bytes(data, MAX_PAYLOAD + 8)
    if kind in (1, 2):
        modulus = 255 if kind == 1 else 65521
        a, b = (0 if kind == 1 else 1), 0
        for value in data:
            a = (a + value) % modulus
            b = (b + a) % modulus
        return (b << (8 if kind == 1 else 16)) | a
    crc = 0xFFFFFFFF
    for value in data:
        crc ^= value
        for _ in range(8):
            crc = (crc >> 1) ^ (0xEDB88320 if crc & 1 else 0)
    return crc ^ 0xFFFFFFFF


def pack(payload, kind):
    size = width(kind)
    check_bytes(payload, MAX_PAYLOAD)
    count = len(payload)
    header = [0x43, 0x53, 1, kind]
    header += [(count >> (8 * j)) & 255 for j in range(3, -1, -1)]
    protected = header + list(payload)
    tag = checksum(protected, kind)
    return protected + list(tag.to_bytes(size, "big"))


def unpack(frame):
    check_bytes(frame, MAX_PAYLOAD + 12)
    if len(frame) < 8:
        raise ValueError("TRUNCATED")
    if list(frame[:2]) != [0x43, 0x53]:
        raise ValueError("MAGIC")
    if frame[2] != 1:
        raise ValueError("VERSION")
    kind = frame[3]
    size = width(kind)
    count = 0
    for value in frame[4:8]:
        count = 256 * count + value
    if count > MAX_PAYLOAD or len(frame) != 8 + count + size:
        raise ValueError("LENGTH")
    expected = 0
    for value in frame[-size:]:
        expected = 256 * expected + value
    if checksum(frame[:-size], kind) != expected:
        raise ValueError("CHECKSUM")
    return list(frame[8:8 + count])


if __name__ == "__main__":
    payload = list(b"123456789")
    known = {1: 0x1EDE, 2: 0x091E01DE, 3: 0xCBF43926}
    print("payload=123456789")
    for kind in (1, 2, 3):
        tag = checksum(payload, kind)
        frame = pack(payload, kind)
        assert tag == known[kind]
        assert unpack(frame) == payload
        assert pack(unpack(frame), kind) == frame
        print(f"{NAMES[kind]}={tag:0{2 * width(kind)}X} "
              f"frame_bytes={len(frame)} roundtrip=OK")
    frame = pack(payload, 3)
    print("crc_frame=" + " ".join(f"{b:02X}" for b in frame))
    damaged = frame.copy()
    damaged[8] ^= 1
    try:
        unpack(damaged)
    except ValueError as error:
        print("corrupt=" + str(error))
    else:
        raise AssertionError("sample corruption accepted")
    first, second = [10, 20, 30], [11, 18, 31]
    for kind in (1, 2):
        a, b = checksum(first, kind), checksum(second, kind)
        assert a == b
        print(f"collision_{NAMES[kind]}={a:0{2 * width(kind)}X}/"
              f"{b:0{2 * width(kind)}X}")

#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

constexpr int MAX_PAYLOAD = 65536;
int width(int kind) {
    if (kind < 1 || kind > 3) throw invalid_argument("ALGORITHM");
    return kind == 1 ? 2 : 4;
}
void check_bytes(const vector<int>& data, size_t limit) {
    if (data.size() > limit) throw invalid_argument("SIZE");
    for (int b : data) if (b < 0 || b > 255) throw invalid_argument("BYTE");
}
uint32_t checksum(const vector<int>& data, int kind) {
    width(kind); check_bytes(data, MAX_PAYLOAD + 8);
    if (kind == 1 || kind == 2) {
        uint32_t modulus = kind == 1 ? 255 : 65521;
        uint32_t a = kind == 1 ? 0 : 1, b = 0;
        for (int value : data) {
            a = (a + uint32_t(value)) % modulus;
            b = (b + a) % modulus;
        }
        return (b << (kind == 1 ? 8 : 16)) | a;
    }
    uint32_t crc = 0xFFFFFFFFU;
    for (int value : data) {
        crc ^= uint32_t(value);
        for (int j = 0; j < 8; ++j)
            crc = (crc >> 1) ^ ((crc & 1U) ? 0xEDB88320U : 0U);
    }
    return crc ^ 0xFFFFFFFFU;
}
vector<int> pack(const vector<int>& payload, int kind) {
    int size = width(kind);
    check_bytes(payload, MAX_PAYLOAD);
    uint32_t count = uint32_t(payload.size());
    vector<int> frame = {0x43, 0x53, 1, kind};
    for (int j = 3; j >= 0; --j) frame.push_back(int((count >> (8 * j)) & 255U));
    frame.insert(frame.end(), payload.begin(), payload.end());
    uint32_t tag = checksum(frame, kind);
    for (int j = size - 1; j >= 0; --j) frame.push_back(int((tag >> (8 * j)) & 255U));
    return frame;
}
vector<int> unpack(const vector<int>& frame) {
    check_bytes(frame, MAX_PAYLOAD + 12);
    if (frame.size() < 8) throw invalid_argument("TRUNCATED");
    if (frame[0] != 0x43 || frame[1] != 0x53) throw invalid_argument("MAGIC");
    if (frame[2] != 1) throw invalid_argument("VERSION");
    int kind = frame[3], size = width(kind);
    uint64_t count = 0;
    for (int j = 4; j < 8; ++j) count = 256 * count + uint64_t(frame[j]);
    if (count > MAX_PAYLOAD || frame.size() != 8 + count + size)
        throw invalid_argument("LENGTH");
    uint32_t expected = 0;
    for (size_t j = frame.size() - size; j < frame.size(); ++j)
        expected = 256U * expected + uint32_t(frame[j]);
    vector<int> protected_data(frame.begin(), frame.end() - size);
    if (checksum(protected_data, kind) != expected) throw invalid_argument("CHECKSUM");
    return vector<int>(frame.begin() + 8, frame.begin() + 8 + size_t(count));
}
string hex_value(uint32_t value, int digits) {
    ostringstream s; s << uppercase << hex << setw(digits) << setfill('0') << value;
    return s.str();
}
int main() {
    string text = "123456789";
    vector<int> payload(text.begin(), text.end());
    vector<uint32_t> known = {0, 0x1EDEU, 0x091E01DEU, 0xCBF43926U};
    vector<string> names = {"", "FLETCHER16", "ADLER32", "CRC32"};
    cout << "payload=" << text << '\n';
    for (int kind = 1; kind <= 3; ++kind) {
        uint32_t tag = checksum(payload, kind); auto frame = pack(payload, kind);
        assert(tag == known[kind]);
        assert(unpack(frame) == payload);
        assert(pack(unpack(frame), kind) == frame);
        cout << names[kind] << '=' << hex_value(tag, 2 * width(kind))
             << " frame_bytes=" << frame.size() << " roundtrip=OK\n";
    }
    auto frame = pack(payload, 3);
    cout << "crc_frame=";
    for (size_t i = 0; i < frame.size(); ++i) {
        if (i) cout << ' ';
        cout << hex_value(uint32_t(frame[i]), 2);
    }
    cout << '\n';
    auto damaged = frame; damaged[8] ^= 1;
    try { unpack(damaged); throw logic_error("sample corruption accepted"); }
    catch (const invalid_argument& error) { cout << "corrupt=" << error.what() << '\n'; }
    vector<int> first = {10, 20, 30}, second = {11, 18, 31};
    for (int kind = 1; kind <= 2; ++kind) {
        uint32_t a = checksum(first, kind), b = checksum(second, kind);
        assert(a == b);
        cout << "collision_" << names[kind] << '=' << hex_value(a, 2 * width(kind))
             << '/' << hex_value(b, 2 * width(kind)) << '\n';
    }
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final int MAX_PAYLOAD = 65536;
    static int width(int kind) {
        if (kind < 1 || kind > 3) throw new IllegalArgumentException("ALGORITHM");
        return kind == 1 ? 2 : 4;
    }
    static void check_bytes(int[] data, int limit) {
        if (data == null) throw new IllegalArgumentException("BYTE");
        if (data.length > limit) throw new IllegalArgumentException("SIZE");
        for (int b : data)
            if (b < 0 || b > 255) throw new IllegalArgumentException("BYTE");
    }
    static long checksum(int[] data, int kind) {
        width(kind); check_bytes(data, MAX_PAYLOAD + 8);
        if (kind == 1 || kind == 2) {
            long modulus = kind == 1 ? 255 : 65521;
            long a = kind == 1 ? 0 : 1, b = 0;
            for (int value : data) {
                a = (a + value) % modulus;
                b = (b + a) % modulus;
            }
            return (b << (kind == 1 ? 8 : 16)) | a;
        }
        long crc = 0xFFFFFFFFL;
        for (int value : data) {
            crc ^= value;
            for (int j = 0; j < 8; ++j)
                crc = (crc >>> 1) ^ ((crc & 1L) != 0 ? 0xEDB88320L : 0);
        }
        return crc ^ 0xFFFFFFFFL;
    }
    static int[] integers(List<Integer> values) {
        int[] a = new int[values.size()];
        for (int i = 0; i < a.length; ++i) a[i] = values.get(i);
        return a;
    }
    static int[] pack(int[] payload, int kind) {
        int size = width(kind);
        check_bytes(payload, MAX_PAYLOAD);
        List<Integer> frame = new ArrayList<>();
        frame.add(0x43); frame.add(0x53); frame.add(1); frame.add(kind);
        for (int j = 3; j >= 0; --j) frame.add((payload.length >>> (8 * j)) & 255);
        for (int b : payload) frame.add(b);
        long tag = checksum(integers(frame), kind);
        for (int j = size - 1; j >= 0; --j) frame.add((int)((tag >>> (8 * j)) & 255));
        return integers(frame);
    }
    static int[] unpack(int[] frame) {
        check_bytes(frame, MAX_PAYLOAD + 12);
        if (frame.length < 8) throw new IllegalArgumentException("TRUNCATED");
        if (frame[0] != 0x43 || frame[1] != 0x53) throw new IllegalArgumentException("MAGIC");
        if (frame[2] != 1) throw new IllegalArgumentException("VERSION");
        int kind = frame[3], size = width(kind);
        long count = 0;
        for (int j = 4; j < 8; ++j) count = 256 * count + frame[j];
        if (count > MAX_PAYLOAD || frame.length != 8 + count + size)
            throw new IllegalArgumentException("LENGTH");
        long expected = 0;
        for (int j = frame.length - size; j < frame.length; ++j)
            expected = 256 * expected + frame[j];
        if (checksum(Arrays.copyOf(frame, frame.length - size), kind) != expected)
            throw new IllegalArgumentException("CHECKSUM");
        return Arrays.copyOfRange(frame, 8, 8 + (int)count);
    }
    static String hex_value(long value, int digits) {
        StringBuilder s = new StringBuilder();
        for (int j = digits - 1; j >= 0; --j)
            s.append("0123456789ABCDEF".charAt((int)((value >>> (4 * j)) & 15)));
        return s.toString();
    }
    public static void main(String[] args) {
        String text = "123456789";
        int[] payload = new int[text.length()];
        for (int i = 0; i < text.length(); ++i) payload[i] = text.charAt(i);
        long[] known = {0, 0x1EDE, 0x091E01DE, 0xCBF43926L};
        String[] names = {"", "FLETCHER16", "ADLER32", "CRC32"};
        System.out.println("payload=" + text);
        for (int kind = 1; kind <= 3; ++kind) {
            long tag = checksum(payload, kind); int[] frame = pack(payload, kind);
            if (tag != known[kind] || !Arrays.equals(unpack(frame), payload)
                    || !Arrays.equals(pack(unpack(frame), kind), frame))
                throw new AssertionError("round trip failed");
            System.out.println(names[kind] + "=" + hex_value(tag, 2 * width(kind))
                    + " frame_bytes=" + frame.length + " roundtrip=OK");
        }
        int[] frame = pack(payload, 3);
        StringBuilder hex = new StringBuilder();
        for (int b : frame) {
            if (hex.length() != 0) hex.append(' ');
            hex.append(hex_value(b, 2));
        }
        System.out.println("crc_frame=" + hex);
        int[] damaged = frame.clone(); damaged[8] ^= 1;
        try {
            unpack(damaged);
            throw new AssertionError("sample corruption accepted");
        } catch (IllegalArgumentException error) {
            System.out.println("corrupt=" + error.getMessage());
        }
        int[] first = {10, 20, 30}, second = {11, 18, 31};
        for (int kind = 1; kind <= 2; ++kind) {
            long a = checksum(first, kind), b = checksum(second, kind);
            if (a != b) throw new AssertionError("collision example differs");
            System.out.println("collision_" + names[kind] + "=" + hex_value(a, 2 * width(kind))
                    + "/" + hex_value(b, 2 * width(kind)));
        }
    }
}

Expected standard output, identical in all three languages:

• payload=123456789
• FLETCHER16=1EDE frame_bytes=19 roundtrip=OK
• ADLER32=091E01DE frame_bytes=21 roundtrip=OK
• CRC32=CBF43926 frame_bytes=21 roundtrip=OK
• crc_frame=43 53 01 03 00 00 00 09 31 32 33 34 35 36 37 38 39 32 D0 4B 2A
• corrupt=CHECKSUM
• collision_FLETCHER16=643C/643C
• collision_ADLER32=0067003D/0067003D

Complexity, Correctness, and Invariants

For $n$ protected bytes, Fletcher and Adler each perform constant work per byte. The reference CRC performs eight bit steps per byte. All three therefore take $\Theta(n+1)$ time for a full valid calculation and $O(1)$ working state, excluding the input. Best, average, and worst valid-input work are linear; the byte contents change the conditional CRC XORs but not the number of bit steps. A verifier with a stored final tag ordinarily processes the whole covered message before it can compare.

Packing and unpacking are also linear in frame size. These reference routines copy lists/vectors, retain the frame or returned payload, and may build a protected-region copy. Their actual extra memory is $O(n)$ including these buffers. A streaming implementation can compute the checksum with constant state; returning a fully buffered payload or withholding it until verification still costs space proportional to that payload.

Modular-sum invariants. For modulus $m$ and initial first sum $a_0$, after $k$ bytes, $$ A_k\equiv a_0+\sum_{i=1}^{k}d_i\pmod m,\qquad B_k\equiv ka_0+\sum_{i=1}^{k}(k-i+1)d_i\pmod m. $$ Here $a_0=0,m=255$ for the selected Fletcher variant, and $a_0=1,m=65521$ for Adler. The first update adds the next byte. The second adds the new first sum, increasing every earlier byte's weight by one and giving the new byte weight one. Induction proves both formulas and explains why updating $B$ with the old $A$ is incorrect.

These invariants also explain the collision: changes $[1,-2,1]$ have zero total and weighted total $3-4+1=0$. Both sums remain unchanged even before modular reduction. Increasing the modulus does not eliminate this family of equal-length collisions.

CRC invariant and error detection. In the unreflected polynomial view, after $k$ input bits the raw register represents the remainder produced by the initial register contribution and the processed message polynomial. The reflected implementation stores the corresponding reversed register representation. Each right shift moves the next bit through the division; conditional XOR supplies the reflected generator feedback. The final XOR converts that raw state to the agreed external tag.

For a mathematical systematic CRC with generator $g(x)$, a received codeword with error polynomial $e(x)$ passes the remainder test exactly when $g(x)$ divides $e(x)$. A nonzero error burst spanning at most $w$ bits has form $x^j b(x)$ with $\deg b\lt w$. If the generator has degree $w$ and nonzero constant term, it cannot divide that error: it is coprime to $x^j$ and too large in degree to divide nonzero $b$. This gives the familiar burst-detection property in the polynomial's bit order.

For the implemented CRC, holding the expected tag fixed, a nonzero burst affecting at most $32$ consecutive protected input bits in CRC processing order changes the result. Reflection processes each byte least-significant bit first. Do not extend a bit-order-specific proof to arbitrary trailer serialization without checking how the whole codeword is represented. Larger or differently structured errors can be undetected; a 32-bit tag cannot distinguish all possible messages.

Verification correctness. The frame parser establishes exact byte coverage and tag width; checksum computation deterministically produces the defined tag; comparison establishes equality with the stored tag. A packed supported payload therefore unpacks to the same bytes. This proves the framing round trip and consistency check. It does not prove that every corrupted frame is rejected, as the explicit collision demonstrates.

For a hypothetical uniformly distributed independent $w$-bit tag mismatch, an accidental equality rate would be $2^{-w}$. That is a model assumption, not a universal error bound. Fletcher and Adler outputs are not generally uniform, short messages have special structure, and deliberately chosen modifications need not follow a random model.

Variants, Pitfalls, and Optimizations

Fletcher variants are not interchangeable. Fletcher-16, Fletcher-32, and Fletcher-64 refer to different accumulator/input widths in common usage. Initial values, end-around-carry zero conventions, packing order, and check-byte adjustment rules vary too. RFC 1146 illustrates the two-accumulator Fletcher family with its own protocol field layout. Follow the target format's exact rules; the direct $B$-high tag here is explicitly defined and is not that TCP field layout. Modulo $255$ is not modulo $256$, so replacing it with a byte mask changes this implementation.

Adler's prime does not make it collision-resistant. Adler's first-sum seed is one, and its modulus is $65521$, not $65535$ or $65536$. The larger prime avoids some weaknesses of composite modular bases, but the exact three-byte collision above remains. Short blocks do not spread Adler values uniformly over all 32-bit patterns. RFC 3309 explains short-packet concerns and the historical replacement of Adler-32 by CRC-32C in SCTP. That is not a claim that this lesson's IEEE CRC-32 is CRC-32C.

A CRC name is a parameter set. Width, polynomial, initial register, input/output reflection, final XOR, and serialization must match. CRC-32C uses a different generator from the IEEE variant implemented here. A library or hardware operation named CRC32 must be checked against the required variant and known vectors. The right-shifting reflected loop uses EDB88320; a conventional left-shifting loop uses the normal polynomial orientation. Mixing the two produces a different function.

CRC reflection and byte order are different decisions. Reflection controls bit processing inside the CRC algorithm. The big-endian trailer controls how the completed integer is stored in this custom record. A different format may serialize the same CRC integer in the opposite byte order. Do not reverse bytes or bits merely because the implementation is described as reflected, and do not assume that appending this custom tag makes a recomputation over the whole frame equal zero.

Streaming and combination. Maintain accumulators across chunk boundaries instead of restarting each chunk. For CRC, preserve the raw state or use a library's documented finalized-state update convention. To combine separately computed Fletcher states of blocks $X$ and $Y$, with $Y$ length $m$, use $$ A_{XY}=(A_X+A_Y)\bmod255,\qquad B_{XY}=(B_X+B_Y+mA_X)\bmod255. $$ For Adler's seed-one convention, the corresponding formulas are $$ A_{XY}=(A_X+A_Y-1)\bmod65521,\qquad B_{XY}=(B_X+B_Y+m(A_X-1))\bmod65521. $$ Use wider intermediates or modular multiplication when lengths are large. CRC combination instead needs the polynomial effect of shifting by the suffix length; XORing two finalized CRCs alone is not the general combination rule. These are extensions to the reference routines, which expose whole-input computation.

Optimizations need arithmetic proofs. A CRC table can replace eight individual shifts with one table-based byte update. Slicing, vectorized polynomial operations, and hardware instructions can improve throughput, but preserve the exact parameter set. Fletcher and Adler can delay modular reduction or unroll their loops after deriving overflow-safe batch sizes for the chosen accumulator width. The per-byte reductions here provide a clear baseline.

Use the right trust model. These checksums are useful for accidental transmission, storage, and implementation errors. An attacker able to replace a message can normally replace its public checksum too. A cryptographic hash compared against a trusted expected digest serves a different purpose; message authentication requires an appropriate keyed MAC, signature, or authenticated protocol. Neither a checksum nor a plain digest comparison repairs damaged data.

Practical bugs. Check the correct bytes, not a decoded string with different line endings or character encoding. Interpret Java/C++ signed bytes as octets. Validate length before slicing or allocating, preserve leading zero tag bytes, and include the agreed metadata in coverage. An equality check that never recomputes the checksum provides no detection at all.

Practice Problems and Real-World Use

Begin with empty input, one byte, bytes above $127$, and ASCII 123456789. Compare an implementation with independent known values and a separately written oracle; an encoder and verifier sharing the same bug can still round-trip.

For Fletcher and Adler, evaluate the closed-form weighted sums rather than replaying the update loop. For CRC, use a second representation: reflect each input byte into conventional polynomial order, perform integer-polynomial division by the full generator 104C11DB7, then account for initial/final conventions. Comparing this with a trusted CRC library tests more than copying the same right-shift loop into another language.

The shared suite has $7918$ checksum/pack/unpack operation inputs: $5911$ accepted and $2007$ rejected. It covers small exhaustive payloads, every single-byte value, randomized messages, upper size limits, header and trailer mutations, short records, invalid byte values, and the explicit collision. Adler and CRC results were checked against zlib; $2682$ CRC evaluations were independently checked by polynomial division. A further $2303$ burst patterns spanning up to eight input bits were verified to change CRC-32. Python, C++, and Java matched every complete result and error label, and C++ ran with address and undefined-behavior sanitizers. Additional Python-only checks reject invalid container and element types.

When testing corruption, separate “this modification must be detected under a proved condition” from “this random mutation happened to be detected.” Include undetected examples too. For a system integration, record the exact checksum parameters, covered byte range, encoding, framing, and comparison behavior so another implementation can reproduce the same tag.