How do I compute an RFC 791 IP header checksum?

Question

I am rolling my own IP packets for a teach-yourself-Ruby project, and need to compute the IP header checksum (as described in RFC 791 p.14). One of the related questions that popped up when I typed my question here pointed me at RFC 1071, so I'm probably most of the way there, but just to add to Stack Overflow, can anyone (possibly Future Josh) provide some Ruby code for computing the checksum, assuming the following bit of Ruby:

    def build_ip_packet(tos, ttl, protocol, dst_addr, data)
        len = (IP_HEADER_LEN * 4) + data.size

        ip_header = %w{ #{IP_VERSION} #{IP_HEADER_LEN} #{tos} #{len} #{IP_IDENTIFICATION} #{IP_FLAGS_BIT_0} #{IP_FLAGS_BIT_1} #{IP_FLAGS_BIT_2} #{IP_FRAG_OFFSET} #{ttl} #{protocol} #{hdr_checksum} #{src_addr} #{dst_addr} }

        [...]
    end

The constants are defined at the top of the file, but they should be self-explanatory if you're looking at RFC791 p.11.

Answer 1

RFC 1071 provides the following sample implementation in C:

in 6
   {
       /* Compute Internet Checksum for "count" bytes
        *         beginning at location "addr".
        */
   register long sum = 0;

    while( count > 1 )  {
       /*  This is the inner loop */
           sum += * (unsigned short) addr++;
           count -= 2;
   }

       /*  Add left-over byte, if any */
   if( count > 0 )
           sum += * (unsigned char *) addr;

       /*  Fold 32-bit sum to 16 bits */
   while (sum>>16)
       sum = (sum & 0xffff) + (sum >> 16);

   checksum = ~sum;

}

I wrote the following C code to unit test it:

#include <stdio.h>
#include <stdlib.h>


unsigned short checksum (int count, unsigned short * addr) {
    unsigned long sum = 0;

    while (count > 1) {
        sum += *addr++;
        count -= 2;
    }

    // Add left-over byte, if any
    if (count > 0)
        sum += * (unsigned char *) addr;

    while (sum >> 16)
        sum = (sum & 0xffff) + (sum >> 16);

    return (unsigned short)sum;
}

void test (const unsigned short expected, const unsigned short got) {
    printf(
        "%s  expected 0x%04x, got 0x%04x\n",
        (expected == got ? "OK" : "NOK"),
        expected,
        got
    );
}

int main(void) {
    unsigned short *buf = calloc(1024, sizeof(unsigned short));

    buf[0] = 0x0000;

    test(
        0x0,
        checksum(2, buf)
    );

    buf[0] = 0x0001;
    buf[1] = 0xf203;
    buf[2] = 0xf4f5;
    buf[3] = 0xf6f7;

    test(
        0xddf2,
        checksum(8, buf)
    );

    return 0;
}

It is slightly disconcerting that my code does not take the bitwise NOT of sum in the last line of the checksum() function like the RFC implementation does, but adding the bitwise NOT broke my unit tests.

Running the code yields:

: jglover@jglover-3; /tmp/rfc-1071-checksum 
OK  expected 0x0000, got 0x0000
OK  expected 0xddf2, got 0xddf2

I ported this to Ruby as follows:

def rfc1071_checksum(header_fields)
    checksum = 0

    header_fields.each{|field| checksum += field}

    while (checksum >> 16) != 0
        checksum = (checksum & 0xffff) + (checksum >> 16)
    end

    return checksum
end

I call the method like this:

def build_ip_packet(tos, ttl, protocol, dst_addr, data)
    len = (IP_HEADER_LEN * 4) + data.size

    # Header checksum is set to 0 for computing the checksum; see RFC 791 p.14
    hdr_checksum = 0

    src_addr = IPAddr.new('127.0.0.1')

    header_fields = [
        ( ((IP_VERSION << 4) + IP_HEADER_LEN) << 8 ) + ( tos      ),
        len,
        IP_IDENTIFICATION,
        ( (IP_FLAGS_BIT_0 << 15) + (IP_FLAGS_BIT_1 << 14) + (IP_FLAGS_BIT_2 << 13) + (IP_FRAG_OFFSET << 12)),
        ( ttl                                 << 8 ) + ( protocol ),
        hdr_checksum,
        src_addr & 0xff00,  # 16 most significant bits
        src_addr & 0x00ff,  # 16 least significant bits
        dst_addr & 0xff00,  # 16 most significant bits
        dst_addr & 0x00ff,  # 16 least significant bits
    ]

    hdr_checksum = rfc1071_checksum(header_fields)

    return nil
end

And here are the unit tests:

require 'test/unit'
require 'lib/traceroute'

class TestTraceroute < MiniTest::Unit::TestCase
    def test_rfc1071_checksum
        [
            [ 0x0000, [ 0x0000 ] ],
            [
                0xddf2,
                [
                    0x0001f203,
                    0xf4f5f6f7,
                ]
            ],
        ].each{|input_record|
            got      = Traceroute.new.rfc1071_checksum(input_record[1])
            expected = input_record[0]

            assert_equal(got, expected, "rfc1071_checksum: #{input_record[1].inspect}")
        }
    end
end