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.
