Re: ANNOUNCE: ocaml bitmatch (Erlang-style bitstrings for OCaml)

[Sylvain Le Gall <sylvain@le-gall.net>]

On 01-04-2008, Richard Jones <rich@annexia.org> wrote:
> In the finest tradition of version 0.1 announcements, this is the
> first announcement of a highly experimental camlp4 syntax extension
> which implements Erlang-style bitstrings, matching over bitstrings,
> and construction of bitstrings.
>
>   Source:  http://www.annexia.org/tmp/ocaml-bitmatch-0.1.tar.gz
>   License: LGPLv2+ with OCaml linking exception
>
> Erlang has a "byte-oriented" data type which can be treated as a
> stream of bits, and provides rather elegant features for creating and
> matching over such streams.  This is a key feature of Erlang and was
> developed because of its history in telecommunications.  (More about
> the feature in this paper:
> http://user.it.uu.se/~kostis/Papers/padl07.pdf)
>
> I have written a camlp4 syntax extension which does much the same in
> OCaml.  For example, you can now effortlessly parse IP packets:
>
>   let display pkt =
>     bitmatch pkt with
>     (* IPv4 packet header from RFC 791:
>     0                   1                   2                   3
>     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |Version|  IHL  |Type of Service|          Total Length         |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |         Identification        |Flags|      Fragment Offset    |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |  Time to Live |    Protocol   |         Header Checksum       |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |                       Source Address                          |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |                    Destination Address                        |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |                    Options                    |    Padding    |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>     *)
>     | 4 : 4; hdrlen : 4; tos : 8; length : 16; (* same as above in OCaml *)
>       identification : 16; flags : 3; fragoffset : 13;
>       ttl : 8; protocol : 8; checksum : 16;
>       source : 32;
>       dest : 32;
>       options : (hdrlen-5)*32 : bitstring; (* NB computed length *)
>       payload : -1 : bitstring ->
>   

At the condition this is not a joke ;-)

I have two questions:
* do you think you can get something efficient (part of the paper you
 are linking, talked about performance)
* is there a way to retain part of the data structure... E.g TCP/UDP
 packet has the same IP part (the one you describe) + a TCP/UDP
 header...
 Example
 type ip_header_begin = 
  <<
    version: 4; 
    hdrlen : 4; 
    tos : 8; 
    length : 16;
    identification : 16; 
    flags : 3; 
    fragoffset : 13;
    ttl : 8; 
  >>
  
type ip_header_end =
  <<
    checksum : 16;
    source : 32; 
    dest : 32;
    >>
 ;;

 type udp_header =
  <<
    source_port: 16;
    destination_port: 16;
    length: 16;
    checksum: 16;
    >>
 ;;

 | ip_beg: ip_header_begin; 17: 8; ip_end: ip_header_end; udp: udp_header ->
    Printf.printf "Found an UDP packet (TTL: %d)" ip_beg.ttl
 | ip_beg: ip_header_begin; 6: 8; ip_end: ip_header_end; ->
    print_string "Found a TCP packet"

(N.B.: there is other way to handle this problem... but this is just a
question).

Anyway, i found this interesting and worth looking at.

Regards,
Sylvain Le Gall