Search code examples
haskellchecksumicmp

why is ICMP checksum shifted 16 bits

I'm struggling to understand why the ICMP checksum total (before being complemented) is the total + shifted right 16 bits total in this line of code: 

checksum bs = let bs' = (if (BL.length bs) `mod` 2 == 0 then bs else BL.snoc bs 0)
                  ws = runGet listOfWord16 bs'
                  total = sum (map fromIntegral ws) :: Word32
              in complement (fromIntegral total + fromIntegral (total `shiftR` 16))

RFC 792 has this to say about calculating the checksum:

Checksum

The checksum is the 16-bit ones's complement of the one's complement sum of the ICMP message starting with the ICMP Type. For computing the checksum , the checksum field should be zero. If the total length is odd, the received data is padded with one octet of zeros for computing the checksum. This checksum may be replaced in the future.

I understand why bs' is calculated, as required by "If the total length is odd, the received data is padded with one octet of zeros for computing the checksum."

I can also understand summing the total of the 16 bit words done in this line of the code total = sum (map fromIntegral ws) :: Word32

I just can't figure out why in this line of code:

complement (fromIntegral total + fromIntegral (total `shiftR` 16))

that + fromIntegral (total `shiftR` 16) should be included at all.

NOTE: I have verified with wireshark that the checksum is only correct if I complement the total + total `shiftR` 16 as done in the linked line of code. So I know it is correct, I just don't understand why.

Solution

  • RFC 1071 describes in detail the checksum definition, including this important part:

    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.

    In your code,

    total = sum (map fromIntegral ws) :: Word32

    is the 32-bit sum, i.e. its low 16 bits is the sum without carries, and the high 16 bits will contain the sum of the carries. By using the fact that fromIntegral :: Word32 -> Word16 does truncation, we have

    low = fromIntegral total :: Word16
high = fromIntegral $ total `shiftR` 16 :: Word16

    and so we can calculate the "end around carry" as

    eac = low + high