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)))