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 ] [ HEX: ffff bitand ] bi + [ -16 shift ] keep + bitnot 2 >le ;

This is available as a `checksum`

instance in checksums.internet.

## No comments:

Post a Comment