Parsing Binary data in Erlang and Haskell

The Bittorrent Wire protocol is a protocol used for communication between peers in a bittorrent cloud. The protocol is explicitly defined to balance between conserving bandwidth and being easy to parse. Hence, it is a binary protocol, but it is fairly easy to parse.

When I wrote etorrent as an experiment, I was faced with the problem of parsing this protocol. In Erlang the task is not hard however, since the language can pattern match on bit-patterns. I began by defining a set of constant values, each corresponding to a message type:

%% Packet types
-define(CHOKE, 0:8).
-define(UNCHOKE, 1:8).
-define(INTERESTED, 2:8).
-define(NOT_INTERESTED, 3:8).
-define(HAVE, 4:8).
-define(BITFIELD, 5:8).
-define(REQUEST, 6:8).
-define(PIECE, 7:8).
-define(CANCEL, 8:8).
-define(PORT, 9:8).

The designation 1:8 means that we need to represent the integer value of 1 in 8 bits of information (i.e., in a byte). With these values down, defining a decoder in Erlang is pretty straightforward:

%%--------------------------------------------------------------------
%% Function: recv_message(Message) -> keep_alive | choke | unchoke |
%%   interested | not_interested | {have, integer()} | ...
%% Description: Receive a message from a peer and decode it
%%--------------------------------------------------------------------
recv_message(Rate, Message) ->
    MSize = size(Message),
    Decoded =
    case Message of
        <<>> ->
            keep_alive;
        <<?CHOKE>> ->
            choke;
        <<?UNCHOKE>> ->
            unchoke;
        <<?INTERESTED>> ->
            interested;
        <<?NOT_INTERESTED>> ->
            not_interested;
        <<?HAVE, PieceNum:32/big>> ->
            {have, PieceNum};
        <<?BITFIELD, BitField/binary>> ->
            {bitfield, BitField};
        <<?REQUEST, Index:32/big, Begin:32/big, Len:32/big>> ->
            {request, Index, Begin, Len};
        <<?PIECE, Index:32/big, Begin:32/big, Data/binary>> ->
            {piece, Index, Begin, Data};
        <<?CANCEL, Index:32/big, Begin:32/big, Len:32/big>> ->
            {cancel, Index, Begin, Len};
        <<?PORT, Port:16/big>> ->
            {port, Port};
    end,
{Decoded, etorrent_rate:update(Rate, MSize), MSize}.

This is pretty straightforward idiomatic Erlang as one would write

it. We convert the numbers into tuples or atoms. The idea is that the atom or the first element of the tuple identifies the type of the message that was sent. Note that in idiomatic Erlang code, the process will crash if the pattern match fails. In that case, we have to handle that problem in another janitorial process.

I toyed with the idea of doing the same parsing in Haskell. Initially, my thought was that it would be rather hard to beat the Erlang code in size. Looking at the above code, it is almost the specification of the protocol and we can't get rid of the specification.

In Haskell, I started with the default construction of an algebraic datatype. It simply reflects the tuple/atom construction of Erlang:

type BitField = B.ByteString
type PieceNum = Integer
type PieceOffset = Integer
type PieceLength = Integer
data Message = KeepAlive
        | Choke
        | Unchoke
        | Interested
        | NotInterested
        | Have PieceNum
        | BitField BitField
        | Request PieceNum PieceOffset PieceLength
        | Piece PieceNum PieceOffset B.ByteString
        | Cancel PieceNum PieceOffset PieceLength
        | Port Integer
deriving (Eq, Show)

If it seems more verbose than the initial Erlang counterpart, then it fools you. In the above, we also encode the types of the messages - but this is the only place where we would have to designate the types in the whole program. Type reconstruction by inference will figure out the details for us.

I expect my data to be presented to me via lazy bytestrings (see Data.ByteString.Lazy). It also turns out that George Giorgidze built the HCodecs package. This package provides decoders for MIDI, Wave and SoundFont2 files. But the real gem of the package is the development of binary parsers for ByteStrings. This turns out to be exactly what we would like to process.

The parser is a monad. So we can use do-notation to decode the messages. Here is an example of decoding the PIECE-message:

7 -> do pn <- fromIntegral <$> getWord32be
   os <- fromIntegral <$> getWord32be
   c <- getRemainingLazyByteString         return $ Piece pn p c 

This looks nice, but the <$> from Control.Applicative hints somewhat at where this will go. Note that we are not using the full power of the monad. In particular, we don't use earlier results from the monad to decide what to do next. Since there is no dependency chain, it means we can just utilize that every monad is also an applicative functor. In particular we can define

7 -> Piece    <$> gw32 <*> gw32 <*> gw32 <*> getRemainingLazyByteString
...
where gw32 = fromIntegral <$> getWord32be

using the applicative functor to solve the game. With this down, the rest of the parser is easy:

decodeMsg :: Parser Message
decodeMsg =
do m <- getWord8        case m of          0 -> return Choke
    1 -> return Unchoke
    2 -> return Interested
    3 -> return NotInterested
    4 -> Have     <$> gw32
    5 -> BitField <$> getRemainingLazyByteString
    6 -> Request  <$> gw32 <*> gw32 <*> gw32
    7 -> Piece    <$> gw32 <*> gw32 <*> getRemainingLazyByteString
    8 -> Cancel   <$> gw32 <*> gw32 <*> gw32
    9 -> Port     <$> (fromIntegral <$> getWord16be)
    _ -> fail "Incorrect message parse"
where gw32 = fromIntegral <$> getWord32be

And there you have it: A Haskell version which is more succinct than the Erlang version while being type safe in the process. The reason it works is due to the clever type class hierachy in Haskell: The parser is a monad and all monads are applicative functors. This lets us combine parsers cleverly into an effective decoder for wire protocol messages.

I do hope it is fairly efficient. Protocol decoding is probably going to be a hot place in the program.

Data.ByteString.Lazy

HCodecs

Erlang code

Haskell code