Implementation of CRC-CCITT (CRC-16 variant) in Objective Caml. Uses a bit vector implementation but is not table driven.
open Bitv open List open Printf (* convenience functions *) let bits initf = Bitv.init 16 initf let zeros = Bitv.create 16 false let ones = Bitv.create 16 true let from_str s = function n -> (String.get s n) == '1' (* CC-ITT CRC polynomials: big endian and little endian *) let poly8048 = from_str "1000010000001000" let poly1021 = from_str "0001000000100001" (* bit twiddling functions. I hate that OCaml doesn't have a bit vector type *) (* and unsigned ints are 30 bits, and signed ints are 31 bits if that isn't wierd enough *) (* and no, there is no 16 bit type that can be used as an integer. Sigh. *) let bit n bits = Bitv.get bits n let shl n bitv = Bitv.shiftl bitv n let bxor bitv1 bitv2 = Bitv.bw_xor bitv1 bitv2 let byte_bits c = Bitv.sub (Bitv.of_int_us(int_of_char c)) 0 8 let pad n bits = Bitv.append bits (Bitv.create n false) (* calculate the CRC for a given byte value. can use this to create a table *) (* lookup version that should be faster, should you find yourself in a big hurry *) let chksum poly remainder byte = let rem = bxor (shl 8 (pad 8 byte)) remainder in let sum remnant = let shifted = shl 1 remnant in if bit 15 remnant then bxor shifted poly else shifted in let rec bits at max remnant byte = if at < max then bits (at + 1) max (sum remnant) byte else remnant in bits 0 8 rem byte (* fold the list, collecting and applying the checksum to each byte *) let crc init bytes = List.fold_left (chksum (bits poly8048)) init bytes (* test to see if we get the proper output corresponding to a correct implementation *) (* should be 0x29B1, ocaml ints have 30 bits, accounting for strange pad value used *) let result = let bits = List.map byte_bits ['1';'2';'3';'4';'5';'6';'7';'8';'9';] in printf "0x%X\n" (Bitv.to_int_us(pad 14 (crc ones bits)))