Re: "ocaml_beginners"::[] what to use for 16bit unsigned integer
Richard Jones
On Sat, Nov 01, 2008 at 03:06:27PM +1100, Sashan Govender wrote:
> On Thu, Oct 30, 2008 at 11:49 PM, Richard Jones <ri...@annexia.org> wrote:
> > On Thu, Oct 30, 2008 at 10:41:46PM +1100, Sashan Govender wrote:
> >> What type should I use to represent a 16 bit unsigned integer?
> >> Bigarray.int16_unsigned perhaps? It seems a bit weird to have to use
> >> the Bigarray module to get at its type. Is there an Int16 module
> >> similar to Int32 except for 16 integers?
> >
> > The sad fact is there isn't a 16 bit integer type in the standard
> > library. The one in Bigarray only works if you're using a (big-)array
> > of them.
> >
> > I'm assuming, if you really need this type, you're doing some sort of
> > bit twiddling operations, such as crypto or read/writing a protocol
> > that has 16 bit fields. In these cases you might want to look at:
> >
> > (1) cryptokit: http://pauillac.inria.fr/~xleroy/software.html
> >
> > (2) bitstring: http://code.google.com/p/bitstring/
> >
>
> Thanks. Yes I am doing some sort of protocol analysis. Just dumping
> libpcap captures at the moment. I had a look at bitstring and it looks
> very advanced and expressive. I noticed a bitstring based libpcap
> expression evaluator in the examples but it failed with this error
> when I tried it on a large (600 MB) file.
> Fatal error: exception Failure("Buffer.add: cannot grow buffer")
> The OCaml it uses is too advanced for me at the moment and I can't fix it.
This is just because the libpcap demo program is pretty stupid. Being
just a demo program it tries to load the entire file into memory
before analyzing it, using the bitstring_of_file function, which in
turn uses a Buffer. This Buffer cannot grow to 600 MB, either because
you're running out of memory or because you're on a 32-bit system with
the usual limitation on string & buffer sizes.
There are two ways you can regard this: either rewrite the libpcap
demo program so that it doesn't need to load the whole file in at
once, or you can see it as an example where we need to use 'bitstring
streams', loaded on demand from some source such as a file. The
latter case is tricky to implement, and much discussed on the
bitstring mailing list.
> Other than that I was wondering if there would be any interest in
> 1) adding support for generic bit stuffing/unstuffing operations (i.e.
> that present in hdlc) and
> 2) mux/demux operations (SONET/SDH use this)
>
> To elaborate further:
> 1) this means having a way of matching a pattern in a given buffer and
> then inserting/removing the bit that follows the pattern. For example,
> in the case of HDLC, packets are framed with a sequence of 0x7e and
> then the data. If the data itself contains 0x7e (i.e. the sequence
> 01111110) then that needs to be stuffed with a 0 bit after the 5th 1
> so it becomes 01111101. The reverse needs to happen when deframing.
It's possible to implement this naively, but it'll be very slow
(bitstrings are stored as simple strings, so inserting bits in the
middle is O(n) with a large constant factor in the non-aligned case).
There is a lot of discussion about changing the implementation of the
bitstring type so that it's not just a simple string (but a stream for
example). However implementing this in the general case is going to
be extremely complicated because the assumption is built into almost
every part of the bitstring library and syntax extension. It's better
to implement a partial solution, but see the discussion of streams on
the bitstring mailing list.
> 2) Here mux (multiplexing) means taking a buffer and inserting it into
> a given point in a stream. Demux is the inverse. In a sense this is a
> generic case of 1).
As above I think.
Rich.
--
Richard Jones
Red Hat