Personal tools

Dealing with binary data

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
Line 157: Line 157:
   
 
Here an exception was thrown because we ran out of bytes.
 
Here an exception was thrown because we ran out of bytes.
  +
  +
So the <tt>Get</tt> monad consists of a set of operations like
  +
<hask>getWord32be</hask> which walk over the input and return some type of
  +
data. You can see the full list of those functions in the
  +
[http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/Data-Binary-Get.html documentation].
  +
  +
Here's another example; decoding an EOF terminated list of
  +
numbers list just involves recursion:
  +
  +
<haskell>listOfWord16 = do
  +
empty <- isEmpty
  +
if empty
  +
then return []
  +
else do v <- getWord64be
  +
rest <- listOfWord16
  +
return (v : rest)</haskell>
  +
  +
==== Strict <tt>Get</tt> monad ====
  +
  +
If you're parsing small messages then, firstly your input isn't going to be a
  +
lazy bytestring but a string one. That's not reallly a problem because you can
  +
easilly convert between them. However, if you want to handle parse failures you
  +
either have to write your parser very carefully, or you have to deal with the
  +
fact that you can only catch exceptions in the IO monad.
  +
  +
If this is your dilemma, then you need a strict version of the <tt>Get</tt>
  +
monad. It's almost exactly the same, but a parser of type <hask>Get a</hask>
  +
results in <hask>(Either String a, ByteString)</hask> as the result of
  +
<hask>runGet</hash>. That type is a tuple where the first value is ''either'' a
  +
string (an error string from the parse) or the result, and the second value is
  +
the remaining bytestring when the parser finished.
  +
  +
Let's update the first example with this strict version of <tt>Get</tt>. You'll
  +
have to install the
  +
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict-0.2.2 binary-strict]
  +
package for it to work.
  +
  +
<haskell>import qualified Data.ByteString as B
  +
import Data.Binary.Strict.Get
  +
import Data.Word
  +
  +
deserialiseHeader :: Get (Word32, Word32, Word32)
  +
deserialiseHeader = do
  +
alen <- getWord32be
  +
plen <- getWord32be
  +
chksum <- getWord32be
  +
return (alen, plen, chksum)
  +
  +
main :: IO ()
  +
main = do
  +
input <- B.getContents
  +
print $ runGet deserialiseHeader input</haskell>
  +
  +
Note that all we're done is change from lazy bytestrings to strict bytestrings
  +
and change change to importing <tt>Data.Binary.Strict.Get</tt>. Now we'll run
  +
it again:
  +
  +
<pre>% runhaskell /tmp/example.hs << EOF
  +
heredoc> 123412341235
  +
heredoc> EOF
  +
(Right (825373492,825373492,825373493),"\n")</pre>
  +
  +
Now we can see that the parser was successful (we got a <tt>Right</tt>) and we
  +
can see that our shell actually added an extra newline on the input (correctly)
  +
and the parser didn't consume that, so it's also returned to us. Now we try it
  +
with a truncated input:
  +
  +
<pre>% runhaskell /tmp/example.hs << EOF
  +
heredoc> tooshort
  +
heredoc> EOF
  +
(Left "too few bytes","\n")</pre>
  +
  +
This time we didn't get an exception, but a <tt>Left</tt> value, which can be
  +
handled in pure code. The remaining bytestring is the same because our
  +
truncated input is 9 bytes long, parsing the first two <tt>Word32</tt>'s
  +
consumed 8 bytes and parsing the third failed - at which point we had the last
  +
byte still in the input.
  +
  +
In your parser, you can also call <hask>fail</hask>, with an error string,
  +
which will result in a <tt>Left</tt> value.
  +
  +
====Bit twiddling====
  +
  +
Even with all this monadic goodness, sometimes you just need to move some bits
  +
around. That's perfectly possible in Haskell too. Just import
  +
<tt>Data.Bits</tt> and use the following table.

Revision as of 05:52, 29 January 2008

Contents

1 Handling Binary Data with Haskell

Many programming problems call for the use of binary formats for compactness, ease-of-use, compatibility or speed. This page quickly covers some common libraries for handling binary data in Haskell.

1.1 ByteStrings

Everything else in this tutorial will be based on bytestrings. Normal Haskell

String
types are linked lists of 32-bit charactors. This has a

number of useful properties like coverage of the Unicode space and lazyness,

however when it comes to dealing with byte-wise data the
String

involves a space-inflation of about 24x and a large reduction in speed.

Bytestrings are packed arrays of bytes or 8-bit chars. If you have experience in C, their memory representation would be the same as a uint8_t[] - although bytestrings know their length and don't allow overflows etc.

Their are two major flavours of bytestrings, strict and lazy. Strict bytestrings are exactly what you would expect - a linear array of bytes in memory. Lazy bytestrings are a list of strict bytestrings, often this is called a cord in other languages. When reading a lazy bytestring from a file, the data will be read chunk by chunk and the file can be larger than the size of memory. The default chunk size is currently 32K.

Within each flavour of bytestring comes the Word8 and Char8 versions. These are mostly an aid to the type system since they are fundamentally the same size of

element. The Word8 unpacks as a list of
Word8
elements (bytes), the Char8 unpacks as a list of
Char
, which may be useful if you want to convert them to
Strings

You might want to open the documentation for strict bytestrings and lazy bytestrings in another tab so that you can follow along.

1.1.1 Simple file IO

Here's a very simple program which copies a file from standard input to standard output

module Main where
 
import qualified Data.ByteString as B
 
main :: IO ()
main = do
  contents <- B.getContents
  B.putStr contents

Note that we are using strict bytestrings here. (It's quite common to import the ByteString module under the names B or BS.) Since the bytestrings are strict the code will read the whole of stdin into memory and then write it out. If the input was too large this would overflow the availble memory and fail.

Let's see the same program using lazy bytestrings. We are just changing the imported ByteString module to be the lazy one and calling the exact same functions from the new module:

module Main where
 
import qualified Data.ByteString.Lazy as BL
 
main :: IO ()
main = do
  contents <- BL.getContents
  BL.putStr contents

This code, because of the lazy bytestrings, will cope with any sized input and will start producing output before all the input has been read. You can think of the code as setting up a pipeline, rather than executing in-order, as you

might expect. As
putStr
needs more data, it will cause the lazy bytestring
contents
to read more until the end of the input is

found.

You should review the documentation which lists all the functions which operate on ByteStrings. The documentation for the various types (lazy Word8, strict Char8, ...) are all very similar. You generally find the same functions in each, with the same names. Remember to import the modules as qualified and give them different names.

1.1.2 The Guts of ByteStrings

I'll just mention in passing that sometimes you need to do something which would endanger the referential transparency of ByteStrings. Generally you only need to do this when using the FFI to interface with C libraries. Should such a need arise, you can have a look at the internal functions and the unsafe functions. Remember that the last set of functions are called unsafe for a reason - misuse can crash you program!.

1.2 Binary parsing

Once you have your data as a bytestring you'll be wanting to parse something from it. Here you need to install the binary package. Instructions for installing Cabal packages are out of scope for this tutorial, but should be fairly easy to find.

The binary package has three major parts: the Get monad, the Put monad and a general serialisation for Haskell types. The latter is like the pickle module that you may know from Python - it has it's own serialisation format and I won't be covering it any more here. However, if you just need to persist some Haskell data structures, it might be exactly what you want: the documentation is here

1.2.1 The Get monad

The Get monad is a state monad; it keeps some state and each action updates that state. The state in this case is an offset into the bytestring which is getting parsed. Get parses lazy bytestrings, this is how packages like tar can parse files several gigabytes long in constant memory - they are using a pipeline of lazy bytestrings. However, this also has a downside. When parsing a lazy bytestring a parse failure (such as running off the end of the bytestring) is signified by an exception. Exceptions can only be caught in the IO monad and, because of lazyness, might not be thrown exactly where you expect. If this is a problem you probably want a strict version of Get, which is covered below.

Here's an example of using the Get monad:

import qualified Data.ByteString.Lazy as BL
import Data.Binary.Get
import Data.Word
 
deserialiseHeader :: Get (Word32, Word32, Word32)
deserialiseHeader = do
  alen <- getWord32be
  plen <- getWord32be
  chksum <- getWord32be
  return (alen, plen, chksum)
 
main :: IO ()
main = do
  input <- BL.getContents
  print $ runGet deserialiseHeader input

This code takes 3, big-endian, 32-bit unsigned numbers from the input string and returns them as a tuple. Let's try running it:

% runhaskell /tmp/example.hs << EOF
heredoc> 123412341235
heredoc> EOF
(825373492,825373492,825373493)

Makes sense, right? Look what happens if the input is too short:

% runhaskell /tmp/example.hs << EOF
tooshort
EOF
(1953460083,1752134260,example.hs: too few bytes. Failed reading at byte position 12

Here an exception was thrown because we ran out of bytes.

So the Get monad consists of a set of operations like

getWord32be
which walk over the input and return some type of

data. You can see the full list of those functions in the documentation.

Here's another example; decoding an EOF terminated list of numbers list just involves recursion:

listOfWord16 = do
  empty <- isEmpty
  if empty
     then return []
     else do v <- getWord64be
             rest <- listOfWord16
             return (v : rest)

1.2.2 Strict Get monad

If you're parsing small messages then, firstly your input isn't going to be a lazy bytestring but a string one. That's not reallly a problem because you can easilly convert between them. However, if you want to handle parse failures you either have to write your parser very carefully, or you have to deal with the fact that you can only catch exceptions in the IO monad.

If this is your dilemma, then you need a strict version of the Get

monad. It's almost exactly the same, but a parser of type
Get a
results in
(Either String a, ByteString)
as the result of
runGet</hash>. That type is a tuple where the first value is ''either'' a
string (an error string from the parse) or the result, and the second value is
the remaining bytestring when the parser finished.

Let's update the first example with this strict version of <tt>Get</tt>. You'll
have to install the
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict-0.2.2 binary-strict]
package for it to work.

<haskell>import qualified Data.ByteString as B
import Data.Binary.Strict.Get
import Data.Word

deserialiseHeader :: Get (Word32, Word32, Word32)
deserialiseHeader = do
  alen <- getWord32be
  plen <- getWord32be
  chksum <- getWord32be
  return (alen, plen, chksum)

main :: IO ()
main = do
  input <- B.getContents
  print $ runGet deserialiseHeader input</haskell>

Note that all we're done is change from lazy bytestrings to strict bytestrings
and change change to importing <tt>Data.Binary.Strict.Get</tt>. Now we'll run
it again:

<pre>% runhaskell /tmp/example.hs << EOF
heredoc> 123412341235
heredoc> EOF
(Right (825373492,825373492,825373493),"\n")</pre>

Now we can see that the parser was successful (we got a <tt>Right</tt>) and we
can see that our shell actually added an extra newline on the input (correctly)
and the parser didn't consume that, so it's also returned to us. Now we try it
with a truncated input:

<pre>% runhaskell /tmp/example.hs << EOF
heredoc> tooshort
heredoc> EOF
(Left "too few bytes","\n")</pre>

This time we didn't get an exception, but a <tt>Left</tt> value, which can be
handled in pure code. The remaining bytestring is the same because our
truncated input is 9 bytes long, parsing the first two <tt>Word32</tt>'s
consumed 8 bytes and parsing the third failed - at which point we had the last
byte still in the input.

In your parser, you can also call <hask>fail
, with an error string,

which will result in a Left value.

1.2.3 Bit twiddling

Even with all this monadic goodness, sometimes you just need to move some bits around. That's perfectly possible in Haskell too. Just import Data.Bits and use the following table.