[Stu] 2007-11-01 Created page.

The '''Internet Checksum''' is a checksum used in (nearly?) every [IP] packet crossing the [Internet] or any [IP]-based network, therefore the speed of of the calculation is very important; oftentimes it is performed in hardware.

Many RFC's described it thusly:
!!!!!!
The checksum field is the 16 bit one's complement of the one's
complement sum of all 16 bit words in the header.
!!!!!!

The description of the checksum and how to calculate it are found in RFC 1071 [http://www.ietf.org/rfc/rfc1071.txt] ''Computing the Internet Checksum'', with additional notes in RFC 1141 [http://www.ietf.org/rfc/rfc1141.txt] ''Incremental Updating of the Internet Checksum'', and RFC 1624 [http://www.ietf.org/rfc/rfc1624.txt] ''Computation of the Internet Checksum via Incremental Update''.

I've written a few Tcl procs to calculate the Internet Checksum using 8,16,32 or 64 bit quantities/operations.
These procs assume that the input data is [binary] and in ''network byte order'' aka ''big-endian'', which is the usual representation of an [IP] packet.

======
# inet_cksum8 --
#
#       Compute Internet Checksum
#       using 8 bit quantities/operations
#
# Arguments:
#       data    binary data to be checksummed
#
# Results:
#       cksum   16 bit Internet Checksum
#
proc inet_cksum8 {data} { 
        set sum 0
        set x {}
        set shift 8
        binary scan $data c* x
        foreach v $x {
                set sum [expr {$sum + (($v & 0xff) << $shift)}]
                if {$shift == 8} { set shift 0 } else { set shift 8 }
        }
        return [Inet_cksum_fold_and_complement $sum]
}
###
======
======
# inet_cksum16 --
#
#       Compute Internet Checksum
#       using 16 bit quantities/operations
#
# Arguments:
#       data    binary data to be checksummed
#
# Results:
#       cksum   16 bit Internet Checksum
#
proc inet_cksum16 {data} {
        set sum 0
        set x {}
        append data [binary format c 0]
        binary scan $data S* x
        foreach v $x {
                set sum [expr {$sum + ($v & 0xffff)}]
        }
        return [Inet_cksum_fold_and_complement $sum]
}
###
======
======
# inet_cksum32 --
#
#       Compute Internet Checksum
#       using 32 bit quantities/operations
#
# Arguments:
#       data    binary data to be checksummed
#
# Results:
#       cksum   16 bit Internet Checksum
#
proc inet_cksum32 {data} {
        set sum 0
        set x {}
        set c [set b [set a 0]]

        set n [binary scan $data I*ccc x a b c]

        set a [expr {$a & 0xff}]
        set b [expr {$b & 0xff}]
        set c [expr {$c & 0xff}]

        if {$n > 1} { set a [expr {$a << 8}] }
        if {$n > 3} { set c [expr {$c << 8}] }

        lappend x $a $b $c

        foreach v $x {
                set sum [expr {$sum + ($v & 0xffffffff)}]
        }

        return [Inet_cksum_fold_and_complement $sum]
}
###
======
======
# inet_cksum64 --
#
# Does not work with tcl 8.4.16, works with tcl 8.5
#
#       Compute Internet Checksum
#       using 64 bit quantities/operations
#
# Arguments:
#       data    binary data to be checksummed
#
# Results:
#       cksum   16 bit Internet Checksum
#
proc inet_cksum64 {data} {
        set sum 0
        set x {}
        set g [set f [set e [set d [set c [set b [set a 0]]]]]]

        set n [binary scan $data W*ccccccc x a b c d e f g]
 
        set a [expr {$a & 0xff}]
        set b [expr {$b & 0xff}]
        set c [expr {$c & 0xff}] 
        set d [expr {$d & 0xff}]
        set e [expr {$e & 0xff}]
        set f [expr {$f & 0xff}]
        set g [expr {$g & 0xff}]
 
        if {$n > 1} { set a [expr {$a << 8}] }
        if {$n > 3} { set c [expr {$c << 8}] }
        if {$n > 5} { set e [expr {$e << 8}] }
        if {$n > 7} { set g [expr {$g << 8}] }

        lappend x $a $b $c $d $e $f $g

        foreach v $x {
                set sum [expr {$sum + ($v & 0xffffffffffffffff)}]
        }
        
        return [Inet_cksum_fold_and_complement $sum]
}
###
======
This performs the last 2 steps in the calculation and is called by all the other procs.
======
# Inet_cksum_fold_and_complement --
#
#       Fold back checksum (apply carry) into 16 bits and complement
#
# Arguments:
#       sum     Summed data, may be more than 16 bits wide
#
# Results:
#       cksum   16 bit Internet Checksum
#
proc Inet_cksum_fold_and_complement {sum} {
        while {$sum > 0xffff} {
                set sum [expr {($sum & 0xffff) + ($sum >> 16)}]
        }
        return [expr {~$sum & 0xffff}]
}
###
======
Hideous test code, the result of the last column is the checksum of (checksum+data) which should always be 0.
======
proc go {} {
        set msg [string repeat [binary format H* 0102030405060708090a0b0c0d0e0f] 99]
        set times 1000
        puts Tcl:\ [info patch]
        puts "Which         Time     Checksum  0"
        puts inet_cksum8\ :\ [format %-10s [lindex [time {inet_cksum8 $msg} $times] 0]]\ ([format %04x [inet_cksum8 $msg]])\ ([format %x [inet_cksum8 [binary format S [inet_cksum8 $msg]]$msg]])
        puts inet_cksum16:\ [format %-10s [lindex [time {inet_cksum16 $msg} $times] 0]]\ ([format %04x [inet_cksum16 $msg]])\ ([format %x [inet_cksum16 [binary format S [inet_cksum16 $msg]]$msg]])
        puts inet_cksum32:\ [format %-10s [lindex [time {inet_cksum32 $msg} $times] 0]]\ ([format %04x [inet_cksum32 $msg]])\ ([format %x [inet_cksum32 [binary format S [inet_cksum32 $msg]]$msg]])
        puts inet_cksum64:\ [format %-10s [lindex [time {inet_cksum64 $msg} $times] 0]]\ ([format %04x [inet_cksum64 $msg]])\ ([format %x [inet_cksum64 [binary format S [inet_cksum64 $msg]]$msg]])
}
======
Testing. The 64 bit proc gives an incorrect result in Tcl 8.4.? which is too bad since it's the fastest. Tcl8.5b2 is slower on the whole with the 64 bit proc being really slow. The 32 bit proc is the overall winner.
======
Tcl: 8.4.7
Which         Time     Checksum  0
inet_cksum8 : 1889       (b0b8) (0)
inet_cksum16: 649        (b0b8) (0)
inet_cksum32: 341        (b0b8) (0)
inet_cksum64: 191        (0b27) (fd09)
======
======
Tcl: 8.5b2
Which         Time     Checksum  0
inet_cksum8 : 2414.965   (b0b8) (0)
inet_cksum16: 838.68     (b0b8) (0)
inet_cksum32: 448.847    (b0b8) (0)
inet_cksum64: 3125.231   (b0b8) (0)
======