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