Re: Factor

I needed to calculate the “internet checksum” for a small project I’ve been working on. While Factor includes several checksum algorithms, it didn’t have support (until recently) for the “internet checksum”.

The “internet checksum” is a 16-bit checksum value specified in RFC 1071 and used in many places within standard network protocols (such as the IP header). The RFC includes this description of the algorithm:

Adjacent octets to be checksummed are paired to form 16-bit integers, and the 1’s complement sum of these 16-bit integers is formed.

Some C code is provided in the RFC as an example of the algorithm for performing this computation (including comments):

/* 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;

In Factor, we can use some high-level concepts like grouping to walk through the bytes two at a time. In fact, the entire implementation is only a few lines and pretty readable:

: internet-checksum ( bytes -- value )
    2 <sliced-groups> [ le> ] map-sum
    [ -16 shift ] [ 0xffff bitand ] bi +
    [ -16 shift ] keep + bitnot 2 >le ;

This is available as a checksum instance in checksums.internet.