Wed, 01 Jul 2009

Three More for the Debian New Queue.

Over the last couple of weeks I've managed to get three new packages into the Debian NEW queue :

Thanks to Simon Horman for sponsoring/uploading the first two of and Matt Palmer for sponsoring/uploading haskell-json.

Posted at: 18:32 | Category: CodeHacking/Debian | Permalink

Mon, 15 Jun 2009

Two More for the Debian New Queue.

I've got two new packages in the Debian NEW queue :

These two libraries are obviously useful in their own right, but I was particularly interested in packaging these because they are build dependencies for hoogle which I'm currently working on packaging.

Thanks to Simon Horman for sponsoring these uploads and the previous ones.

Posted at: 22:31 | Category: CodeHacking/Debian | Permalink

Tue, 09 Jun 2009

Debian Maintainer.

With the closing of Debian bug #531811 I am now officially a Debian Maintainer.

Although I've been using Debian and related distributions for nearly a decade, for most of that time I've been pretty happy just being an upstream developer and a downstream user.

That changed when I started learning and using Haskell some 6 months ago. After using Ocaml on Debian for about four years I had grown spoilt by the work of the Ocaml Debian Maintainers who do a stellar job in keeping the everything Ocaml related in Debian up to date. Any time I needed a new Ocaml library, it was nearly always just an apt-get install away.

Unfortunately Haskell on Debian is in a poor state in comparison to Ocaml. My main aim in becoming a Debian Maintainer is to improve Haskell on Debian. First of all, I will be packaging Haskell libraries. So far I have make Debian packages of the following three Hackage packages :

I have also joined the Debian Haskell Mailing List and hope to help out on packaging and improving the compiler version transition process.

Posted at: 19:52 | Category: CodeHacking/Debian | Permalink

Fri, 05 Jun 2009

Jim Henson Co.

I received an email this morning: 


  From: David XXX <xxx@creatureshop.com>
  To: <erikd@xxx.com>
  Subject: libsndfile usage
  Date: Thu, 4 Jun 2009 10:52:02 -0700
  User-Agent: Mozilla-Thunderbird 2.0.0.19 (X11/20090103)

  Erik, just thought I would mention we have been using libsndfile
  internally at the Jim Henson Co. for a while, we recently got approval
  to open source some of our utilities which mostly use libsndfile to read
  in wav files for encoding into a quicktime file, using libquicktime. We
  released them as usage examples and extras for libquicktime.

  http://libquicktime.cvs.sourceforge.net/viewvc/libquicktime/lqt_utils/

  --
  David XXX
  Pipeline Tools Programmer
  Jim Henson Creature Shop
  xxx@creatureshop.com

This is so cool.

Of course Jim Henson and Company are probably best known for the Muppets and Sesame Street but a couple of years ago my then four year old daughter absolutely loved watching Bear in the Big Blue House.

In a subsequent email David explained that the Bear program was before his time, and that libsndfile was being used as part of the render process in the production of Sid the Science Kid which I don't think has reached this country yet.

Posted at: 21:06 | Category: CodeHacking/libsndfile | Permalink

Thu, 14 May 2009

libsndfile 1.0.20.

There's a new release of libsndfile available in the usual place. This is a security bug fix release which fixes a potential heap overflow in VOC files found and reported by Tobias Klein ( http://www.trapkit.de/ ) and another in the AIFF file parser found by me.

I am also making available patches for older versions of libsndfile:

Hopefully the next release will contain new features instead of just bug fixes.

Posted at: 20:53 | Category: CodeHacking/libsndfile | Permalink

Tue, 03 Mar 2009

libsndfile 1.0.19.

There's a new release of libsndfile available in the usual place. There is also a back story about this release.

At about the same time as my blog post entitled "Security Hyperventilating" I released version 1.0.18 of libsndfile. A couple of days later I received an email from Alin Rad Pop of Secunia Research (the company who got it right last time) informing me of a real, potentially exploitable bug in my newly released code. I've been told that this security vulnerability will be made public over the next couple of days as CVE-2009-0186.

While I certainly didn't believe my code was bug free I have worked very hard to reduce the bugs as much as possible. I have a full and rather comprehensive test suite, I run valgrind over the code regularly, I have learnt from past mistakes and I when I find one bug I nearly always take the time to search for other instances of the same class of bug in the code.

I even wrote a program to do automated Fuzz Testing. This program takes an existing sound file, modifies it, writes it to disk and then runs it through libsndfile. If libsndfile segfaults or does anything else wildly wrong, the problem file is saved for later review. That review usually results in a bug fix.

In spite of all this testing, there was still a security vulnerability. Thats mainly because libsndfile is one of those projects that needs to parse untrusted binary data. Remember all those exploitable bugs against libjpeg and libgif in the late 1990s? Well both of those projects only parse one file type; libsndfile parses more than a dozen. The only other project I can think of with large numbers of different things to parse is the Samba Project which needs to parse dozens of different kinds of messages in the CIFS protocol.

Of course there are other tools to for finding bugs; static analysis tools. In this field there are FOSS products like Sparse and Splint. The first is rather new and developed specifically to find bugs in Linux kernel source code and the second is basically unmaintained. Both are rather intrusive in that they require special annotations to help them ignore valid code and find buggy code.

Neither of these FOSS programs compare well against commercial offerings like Coverity's Prevent but Coverity is widely regarded as being rather expensive. However, for FOSS projects, Coverity does have a program where it scans FOSS projects and feeds the scan results back to the projects so they can fix bugs.

libsndfile was added to Coverity scan of FOSS projects well over a year ago. I fixed all of the issues (mostly minor) pretty much immediately and then asked to go on to the next rung of the ladder. Unfortunately, I was told that I had to wait for all the projects that were currently on rung 0 to fix their issues before that could happen. Eventually, that did happen, but I don't remember anyone contacting me about it. This slow progress was frustrating.

However, on hearing that there was a CVE about to be published against libsndfile I was fortunate enough to have someone offer to run libsndfile through one of the commercial static analysis tools. The result of that was a report containing 68 warnings, split into four roughly equally sized groups:

The interesting thing about the above test was that the bug that resulted in the CVE was still present in the code analysed by static analysis tool, but was not found. So while this tool did find a bunch of errors it is still not able to find every error. Obviously there is room for improvement here, both in my code and in the static analysis tool.

Posted at: 19:53 | Category: CodeHacking/libsndfile | Permalink

Tue, 24 Feb 2009

Calling from C into Ocaml.

I've got a project where it would be nice to be able to call Ocaml code from a C program. Although interfacing Ocaml and C is covered in the official manual and the O'Reilly Ocaml book, neither of these sources have a complete example.

As a firm believer in the idea that a 100 lines of working code is worth a thousand lines of explanatory text in a book or on the web, I thought I'd put together a small but complete example. First off, here is the Ocaml code (download ocaml-called-from-c.ml): 


  let ocaml_puts name =
      Printf.printf "Program name is '%s'.\n" name ;
      (* Must flush stdout before returning to C. *)
      flush stdout

  let ocaml_string_join join arr =
      (* Create and return a string. *)
      String.concat join (Array.to_list arr)

  (* On program initialisation, register functions to be called from C. *)
  let () =
      Callback.register "ocaml_puts" ocaml_puts ;
      Callback.register "ocaml_string_join" ocaml_string_join

There are two functions that will be called from C, ocaml_puts and ocaml_string_join and both functions must be registered as callbacks with the Ocaml runtime using Callback.register. To find the function signatures of these functions we can use the ocamlc program: 


  prompt > ocamlc -i ocaml-called-from-c.ml
  val ocaml_puts : string -> unit
  val ocaml_string_join : string -> string array -> string

The first function has a single string parameter and returns nothing, while the second takes two parameters, a string and an array of strings and returns a string.

The C program which calls these two functions looks like this (download c-main-calls-ocaml.c): 


  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  #include <caml/alloc.h>
  #include <caml/mlvalues.h>
  #include <caml/memory.h>
  #include <caml/callback.h>
  
  
  static void
  call_ocaml_void (const char * name)
  {   CAMLparam0 () ;
      CAMLlocal1 (ostr) ;
  
      ostr = caml_copy_string (name);
  
      value * func = caml_named_value ("ocaml_puts") ;
  
      if (func == NULL)
          puts ("caml_named_value failed!") ;
      else
          caml_callback (*func, ostr) ;
  
      CAMLreturn0 ;
  } /* call_ocaml_void */
  
  
  static void
  call_ocaml_string (char * join, char const ** argv)
  {   CAMLparam0 () ;
      CAMLlocal3 (ojoin, oargv, ores) ;
  
      ojoin = caml_copy_string (join);
      oargv = caml_alloc_array (caml_copy_string, argv) ;
  
      value * func = caml_named_value ("ocaml_string_join") ;
  
      if (func == NULL)
          puts ("caml_named_value failed!") ;
      else
          ores = caml_callback2 (*func, ojoin, oargv) ;
  
      printf ("Ocaml returned : '%s'\n", String_val (ores)) ;
  
      CAMLreturn0 ;
  } /* call_ocaml_string */
  
  
  int
  main (int argc, char ** argv)
  {   const char * progname ;
      int k, count ;
      
      progname = argv [0] ;
      if (strstr (progname, "./") == progname)
          progname += 2 ;
  
      if (argc < 2)
      {   puts ("Need at least 1 command line argument.") ;
          exit (1) ;
          } ;
  
      count = argc >= 2 ? atoi (argv [1]) : 1 ;
      count = count < 1 ? 1 : count ;
      printf ("Count : %d\n", count) ;

      /* Must call this before calling any Ocaml code. */
      caml_startup (argv) ;
  
      for (k = 0 ; k < count ; k++)
          call_ocaml_void (progname) ;
  
      for (k = 0 ; k < count ; k++)
          call_ocaml_string (" ", (char const **) (argv + 1)) ;
  
      return 0 ;
  } /* main */

The main function is mostly self explanatory; the only thing to note is that if we want to call any Ocaml code from C, we must call caml_startup first. Looking at the functions that call into Ocaml, note that these functions begin with a call to CAMLparam0 and ends with a call to CAMLreturn0. These are both macros, the first of which sets up the Ocaml specific stack requirements and the second of which cleans up after the first. The '0' at the end of their names indicates that there are zero Ocaml managed data objects passed into and returned from the C function respectively.

For values to be passed to Ocaml, we use local Ocaml managed variables set up with CAMLlocal1 if we only have one, or CAMLlocal3 if we have 3. Data can be copied into these local Ocaml variables using the caml_copy_* and caml_alloc_* families of functions.

The Ocaml functions we want to call can be looked up by name using caml_named_value and the function actually called using caml_callback if we only have one parameter to pass or caml_callback2 for two parameters.

For the call to ocaml_string_join which returns a string, we can extract the return value from the Ocaml wrapper using String_val. There are also other functions to retrieve other data types, the only real caveat being that if the type isn't atomic (eg int or double) and you want to return it from the C function it will be necessary allocate memory for it and copy it because the memory area returned from Ocaml will be invalid after the call to CAMLreturn0.

Finally, building this simple example can be done as follows (using version 3.10.2 of the Ocaml compiler): 


  ocamlopt -c ocaml-called-from-c.ml -o ocaml-called-from-c.cmx
  ocamlopt -output-obj -o camlcode.o ocaml-called-from-c.cmx 
  gcc -g -Wall -Wextra  -c c-main-calls-ocaml.c -o c-main-calls-ocaml.o
  gcc camlcode.o c-main-calls-ocaml.o -ldl -lm -L /usr/lib/ocaml/3.10.2 \
         -lasmrun -o c-main-calls-ocaml

The first line compiles to Ocaml file into an Ocaml object (*.cmx) using the native code compiler, the second takes the Ocaml object and all the other Ocaml objects needed and generates a object file (camlcode.o) that can be linked to C code. The last two lines compile the C code into an object file and then links all the C objects and required libraries into an executable. 


  prompt > ./c-main-calls-ocaml 4 abc wxyz
  Count : 4
  Program name is 'c-main-calls-ocaml'.
  Program name is 'c-main-calls-ocaml'.
  Program name is 'c-main-calls-ocaml'.
  Program name is 'c-main-calls-ocaml'.
  Ocaml returned : '4 abc wxyz'
  Ocaml returned : '4 abc wxyz'
  Ocaml returned : '4 abc wxyz'
  Ocaml returned : '4 abc wxyz'

At this point its probably a good idea to run the program under valgrind and vary the first parameter to prove to oneself that un-freed memory when the program terminates is a constant (due to the Ocaml runtime) and does not vary in proportion to the number of times the Ocaml code is called (which would indicate a memory leak in the interface code).

Posted at: 22:31 | Category: CodeHacking/Ocaml | Permalink

Sun, 15 Feb 2009

Ten Years of libsndfile.

Today, February 15th 2009, is the ten year anniversary of the first release of libsndfile.

Like most FOSS projects, libsndfile started off as an urge to scratch an itch. I was interested in Digital Signal Processing (DSP) and wanted an easy way to get digital audio into and out of software I was writing to try out various DSP algorithms. Secondly, I wanted to a sound file editor and one important part of such an editor is an ability to read and write various sound file formats. I did however look at a couple of existing sound file editors and found that most of them available at the time had buggy and incorrect WAV file handling. So I started out getting that part fixed. Nowadays, most sound file editors on Linux and many on other platforms use libsndfile for file I/O.

In its 10 years of existence, libsndfile has grown from some 5000 lines of code to over 45000 lines of code (not counting the test suite and the example programs). The earliest versions could read WAV, AIFF and AU file formats while the latest version supports 25 formats and is still growing.

It was originally written to run on Linux and other UNIX-like systems but soon ended up running on windows and Mac OS9 (the old non-Unix Apple Macintosh) operating system. Fortunately Mac OS9 has been assigned to the dustbin of history leaving windows as the only operating system that was difficult or painful to support. Recently, the windows development has moved to a system where the only way I support building of libsndfile for that OS is to cross compile from Linux, with the test suite being run under Wine. This has made my life significantly easier since I also release pre-compiled windows binaries.

One surprise for me was that a Wikipedia entry as added in 2006. The page says:

"libsndfile is a widely-used [citation needed] C library"

and I think that the ten year anniversary of the first release may be a good time to look at where libsndfile is actually being used. With a little research and some help from the libsndfile mailing lists, this is what I found (in no particular order):

On top of that there are language bindings for Fortran 77, Free Pascal, Haskell, Perl, Python ( PySndfile, AudioLab, libsndfile-python and possibly others ), Ruby and probably many others.

Overall its been a fun ten years. I've learnt a lot about writing reliable and portable cross platform code and become a much better coder for it. Having libsndfile as a hobby project has definitely helped my employment prospects and my career as a professional software engineer.

The next ten years of libsndfile will mainly be maintenance, but new file formats (I'm currently working on Ogg/Speex) and features will be added as needed.

Posted at: 11:31 | Category: CodeHacking/libsndfile | Permalink

Sat, 14 Feb 2009

Security Hyperventilating.

Just today, David Cournapeau and Lev Givon found a bug in all versions of libsamplerate up to and including 0.1.6. The bug causes a segfault and is basically the same as a bug I thought I fixed last year that resulted in the following entry in the ChangeLog: 


  2008-07-02  Erik de Castro Lopo  <erikd AT mega-nerd DOT com>

     * src/src_sinc.c
     Fix buffer overrrun bug at extreme low conversion ratios. Thanks to Russell
     O'Connor for the report.

That bug fix went into version 0.1.4 of libsamplerate which was released on July 2nd, 2008. As a result, I was contacted by computer security firm Secunia Research on July 3rd and asked the following questions:

I replied with a reasonably full explanation and stated that while this bug, if triggered, would crash the program, it was not, in my opinion, exploitable. Secunia Research was happy with my explanation and analysis and I thought that was that.

However, in November of 2008 there was a flurry of security advisories which quoted the above ChangeLog entry but got the security implications completely wrong. The curious thing was that no-one, not a single person contacted me or the project mailing list to ask about the severity of the problem.

The earliest of these advisories I can find was dated November 3rd and appeared on the Openwall OSS-Security mailing list. However, by December 2nd, the Gentoo security team was saying:

"A remote attacker could entice a user or automated system to process a specially crafted audio file possibly leading to the execution of arbitrary code with the privileges of the user running the application."

I on the other hand, remain convinced that this bug is not exploitable under anything other than purely theoretical circumstances.

Since I have now found another variant of the same bug I decided I should document the problem more fully than last time. The problem occurs deep in a rather complicated piece of code that looks like this: 


  static void
  prepare_data (SINC_FILTER *filter, SRC_DATA *data, int half_filter_chan_len)
  {   int len = 0 ;
  
      /* Calculation of value of len elided. */
  
      len = MIN (filter->in_count - filter->in_used, len) ;
      len -= (len % filter->channels) ;
  
      memcpy (filter->buffer + filter->b_end, data->data_in + filter->in_used,
                          len * sizeof (float)) ;

The problem is that under conversion ratios near the lower bound of allowed values, the variable len can end up as a small negative value (I saw values in the range [-20, -1]). That small negative number then gets multiplied by 4 (sizeof float) and then passed as the third parameter to memcpy.

However, the third parameter to memcpy is of type size_t which is an unsigned value the same size as sizeof (void*). In the C programming language, when a small signed value is converted to an unsigned value, it gets converted into a very large positive value very near the maximum representable positive unsigned value, ie 4Gig on 32 bit systems or 2 to the power of 64 on 64 bit systems.

Due to the conversion, the memcpy tries to write to a huge chunk of memory (nearly 4 Gig on 32 bit systems, and a hell of a lot more on 64 bit systems). Under a protected memory system (Linux, Windows NT or later and Mac OSX), the only way this bug could possibly exploitable would be if the memcpy returns.

However, since the memcpy is trying to overwrite the vast majority of the CPU's memory space, the chances of the memcpy returning are essentially zero for any sane operating system. Instead, the process containing the call into libsamplerate will attempt to write outside its allocated memory space and will therefore be terminated by the operating system with a segmentation fault.

I have now fixed the function containing the memcpy so that it checks the value of len and returns from the function if it is outside a sane range.

Now I do think that security researchers and security specialists at Linux distributions do a very important and rather thankless job. I also think that in this case some of them fell down rather badly. Secunia Research did the right thing and asked me about the implications of the bug. The others, extrapolated incorrectly, from very little information and got it wrong, without ever contacting me. I'm hoping that the ChangeLog entry (below) 


  2009-02-14  Erik de Castro Lopo  <erikd AT mega-nerd DOT com>

      * src/src_sinc.c
      Fix a segfault which occurs when memcpy is passed a bad length parameter.
      This bug has zero security implications beyond the ability to cause a
      program hitting this bug to exit immediately with a segfault.
      See : http://www.mega-nerd.com/erikd/Blog/2009/Feb/14/index.html
      Thanks to David Cournapeau.

will prevent the kind of security hyperventilating I saw last time. The new version of libsamplerate, version 0.1.7, has just been released.

Update : 2009-02-15 11:19

David Cournapeau informs me that Lev Givon, as a user of David's libsamplerate Python bindings, reported this bug to him and that it was actually Lev that found the bug.

Posted at: 22:58 | Category: CodeHacking/SecretRabbitCode | Permalink

Sat, 07 Feb 2009

libsndfile 1.0.18.

Over two years since the last one I've finally managed to do a new release of libsndfile. The changes are:

The Win32 installer and binaries have been tested under both Wine and Windows XP. The Win64 installer and binaries have received much less testing and should be considered alpha quality.

For those compiling from source, it should be noted that the configure script requires libvorbis version 1.2.1 or greater which is currently only available from Xiph SVN.

Posted at: 17:01 | Category: CodeHacking/libsndfile | Permalink

Sun, 11 Jan 2009

libsamplerate 0.1.5.

There is a new release of libsamplerate available here. This release contains some improvements to the optimisations that were mentioned in this blog post.

After announcing the previous optimisation work on the Secret Rabbit Code mailing list someone asked for a special case optimisation of 6 channels for doing the 5.1 surround sound format. Then there was also a request for an 8 channel special case for doing 7.1 surround.

I added the 6 channel special case immediately and then found another optimisation for the multi-channel case which uses a horrible hack called Duff's Device in the inner most loop. The results for these optimisations can be seen on the following throughput graphs:


[Throughput graphs]

Obviously, the special cases for 1, 2, 4, and 6 channels have significant improvements, especially for 4 and 6 channels. The general multi channel code path is used for 3, 5, 7 and more channels. Interestingly, if one draws a line through the 1, 2, 4 and 6 channel through-puts for and then a line through the general multi channel through-puts, they intersect at about 8 channels, suggesting that there is very little to be gained by adding a special case code path for 8 channels.

The only downside of this new release is that it uses a C construct that is part of the 1999 ISO C Standard which the Microsoft C compiler does not support. Windows users that want to compile libsamplerate should either use GNU GCC or the Intel compiler with the -c99 command line option.

Posted at: 20:47 | Category: CodeHacking/SecretRabbitCode | Permalink

Wed, 31 Dec 2008

Parsec and Expression Parsing.

Haskell's Parsec parsing library (distributed with the GHC compiler since at least version 6.8.2) contains a very powerful expression parsing module Text.ParserCombinators.Parsec.Expr. This module makes it easy to correctly parse arithmetic expressions like the following according to the usual programming language precedence rules. 


  2 + a * 4 - b

Once parsed, the abstract syntax tree for that expression should look like this:


hackfest living room

The original Parsec paper by Daan Leijen even gives a small example of using the expression parser. As can be seen below, the operators are defined in a table (ie a list of lists) where the outer list is a set precedence levels (from highest precedence to lowest) and each inner list specifies all the operators for that precedence level. 


  module Parser
  where
  
  import Text.ParserCombinators.Parsec
  import Text.ParserCombinators.Parsec.Expr
  
  expr :: Parser Integer
  expr = buildExpressionParser table factor <?> "expression"

  table :: [[ Operator Char st Integer ]]
  table = [
      [ op "*" (*) AssocLeft, op "/" div AssocLeft ],
      [ op "+" (+) AssocLeft, op "-" (-) AssocLeft ]
      ]
    where
      op s f assoc = Infix (do { string s ; return f }) assoc
  
  factor = do { char '(' ; x <- expr ; char ')' ; return x }
     <|> number
     <?> "simple expression"
  
  number :: Parser Integer
  number = do { ds <- many1 digit; return (read ds) } <?> "number"

The above simple example works fine but there is a potential for a rather subtle problem if the expression parser is used in conjunction with the Text.ParserCombinators.Parsec.Token module.

The problem arises when trying to parse expressions in C-like languages which have bitwise OR (|) as well as logical OR (||) and where the bitwise operation has higher precedence than the logical. The symptom was that code containing the logical OR would fail because the expression parser was finding two bitwise ORs. After banging my head against this problem for a considerable time, I posted a problem description with a request for clues to the Haskell Cafe mailing list with the following code snippet: 


  import qualified Text.ParserCombinators.Parsec.Expr as E

  opTable :: [[ E.Operator Char st Expression ]]
  opTable = [
      -- Operators listed from highest precedence to lowest precedence.

      {- snip, snip -}

      [    binaryOp "&" BinOpBinAnd E.AssocLeft ],
      [    binaryOp "^"  BinOpBinXor E.AssocLeft ],
      [    binaryOp "|"  BinOpBinOr E.AssocLeft ],

      [    binaryOp "&&" BinOpLogAnd E.AssocLeft ],
      [    binaryOp "||" BinOpLogOr E.AssocLeft ]
      ]

  binaryOp :: String -> (SourcePos -> a -> a -> a)
                     -> E.Assoc -> E.Operator Char st a
  binaryOp name con assoc =
      E.Infix (reservedOp name >>
          getPosition >>=
          return . con) assoc

Unfortunately, no real answer was forthcoming and while I still held out hope that an answer might eventuate, I continued to work on the problem.

Eventually, after reasoning about the problem and looking at the source code to the Token module I realised that the problem was with the behaviour of the reservedOp combinator. This combinator was simply matching the given string at the first precedence level it found so that even if the code contained a logical OR (||) the higher precedence bitwise OR would match leaving the second vertical bar character un-parsed.

My first attempt at a solution to this problem was to define my own combinator reservedOpNf using Parsec's notFollowedBy combinator and use that in place of the problematic reservedOp. 


  opChar :: String
  opChar = "+-/%*=!<>|&^~"

  reservedOpNf :: String -> CharParser st ()
  reservedOpNf name = try (reservedOp name >> notFollowedBy (oneOf opChar))

This solved the immediate problem of distinguishing between bitwise and logical OR, but I soon ran into another problem parsing expressions like this: 


  if (whatever == -1)
     .....

which were failing at the unary minus.

A bit of experimenting suggested that again, the problem was with the behaviour of the reservedOp combinator. In this case it seemed the combinator was matching the given string, consuming any trailing whitespace and then the notFollowedBy was failing on the unary minus.

Once the problem was understood, the solution was easy, replace the reservedOp combinator with the string combinator (which matches the string exactly and doesn't consume trailing whitespace), followed by the notFollowedBy and then finally use the whiteSpace combinator to chew up trailing white space. 


    reservedOpNf :: String -> CharParser st ()
    reservedOpNf name =
        try (string name >> notFollowedBy (oneOf opChar) >> whiteSpace)

Despite minor problems like the one above, I am still incredibly impressed with the ease of use and power of Parsec. Over the years I have written numerous parsers, in multiple host languages, using a number of parser generators and I have never before used anything that comes close to matching Haskell and Parsec.

Posted at: 07:28 | Category: CodeHacking/Haskell | Permalink

Mon, 29 Dec 2008

learnHaskell :: Problem -> IO Solution

Over the last week or so I've been learning Haskell. Unlike a previous attempt to learn Erlang I think this one will actually end up bearing fruit. The main thing that slowed down my attempt to learning Erlang was that I didn't have a task to apply it to that exploited the strengths of the language.

For Haskell I have a task that is ideally suited to the language and plays to its strengths; writing a parser for an Javascript-like language. Just like when I learned Ocaml I am jumping in at the deep end with a difficult problem and learning the language on the way (ie as a side-effect of tackling the task itself).

Normally my tool of choice for this task would be Ocaml and I did in fact start out writing a parser in Ocaml using the Menhir parser generator. Menhir creates a parser from an LR(1) grammar specification where the LR(1) means that the grammar is left recursive and must need no more than one token look-ahead to resolve ambiguities. Over two days of intense hacking I made quite a lot of progress on the grammar and then hit a wall; numerous rather incomprehensible shift/reduce and reduce/reduce warnings plus a part of the grammar (raw XML embedded directly into the source code) which was not context free and for which I could not see any possible way of parsing with only one token look-ahead.

Since I already knew Ocaml, I looked around at some of the other parser generators for Ocaml like Aurochs and PCL. Aurochs uses Parsing Expression Grammar (or Packrat parsing) and seemed interesting, but was rejected because it seemed to gave very little control over the Abstract Syntax Tree it generated. PCL on the other hand was a monadic parser combinator library which is basically a port of Haskell's Parsec library to Ocaml. The main problem I saw with PCL was that it used Monads and lazy evaluation, neither of which are very common in standard Ocaml code. PCL was also rather new and I wasn't sure if it was stable and mature enough for quite an advanced parsing task.

Of course I had been hearing good things about Haskell's Parsec library for a couple of years and decided that this was a good time to give it a try. The interesting thing about Parsec is that it uses lazy evaluation to provide what is effectively infinite token look-ahead. Obviously, a Parsec grammar should be written so that it only uses more than one look-ahead when that is absolutely necessary.

With a bit of googling I found a bunch of examples using Parsec for simple things and that was enough code to get me started. A week later, after an IRC question answered by Don Stewart, a bit of help from Conrad Parker and a question answered on the Haskell Cafe mailing list, I am almost as far along as I got with the Ocaml version of the parser.

My impressions of Haskell and Parsec so far are as follows:

All in all, I'm really enjoying my foray into the world of Haskell.

Posted at: 09:53 | Category: CodeHacking/Haskell | Permalink

Sun, 14 Dec 2008

Rabbit Optimisation.

For some time I have known that the sinc based converters in my sample rate conversion library Secret Rabbit Code might benefit from a particular optimisation which reuses the filter coefficients where possible, rather than recalculating them. The good news is that I finally managed to get around to performing this optimisation work and the results are reasonably impressive.

The old converter used what was basically a single channel converter on each channel in turn. Since part of this single channel operation involved calculating the filter coefficients on the fly it was pretty obvious that if more than one channel was being processed, it would be possible to calculate the coefficients for the first channel and reuse them for all the rest. Once that was done, the inner loop can be special cased for commonly used channel counts like 1, 2 and 4 while having other channel counts handled by a generic function that can handle any number of channels. These special cases contain straight line code where the generic function contains a loop.

As can bee seen in the throughput graph for the SRC_SINC_BEST_QUALITY converter, this optimisation resulted in modest throughput improvements for 1 channel, a big improvement for 2 channels and an outrageous more than doubling of throughput for the 4 channel case. Even the generic multi-channel case, represented here by 3 and 5 channels showed a modest improvement. It should be noted that the filter coefficients are the same for the old and new versions so the only changes in performance are due to the optimisation.


[Throughput graphs for old and new Best Sinc converter]

These results were obtained on a 3 plus year old 1.1 GHz Pentium M laptop. More recent machines should show much better absolute results but similar proportional improvements. The other sinc-based converters will also show similar proportional improvements.

A new version of Secret Rabbit Code containing this optimisation should probably be released some time during the next couple of days.

Posted at: 08:16 | Category: CodeHacking/SecretRabbitCode | Permalink

Tue, 02 Dec 2008

Ocaml : Null Cursor in lablgtk.

I need to be able to hide the cursor in an Ocaml/lablgtk/Cairo program I'm writing (a touchscreen calibration utility to go with the Zytouch driver). Usually this is done by creating a small 1x1 pixel cursor that is transparent, but I couldn't find any existing Ocaml/lablgtk code to do it. With a little help from Jacques Garrigue on the lablgtk mailing list I came up with the following function to create a cursor: 


  let create_null_cursor win =
      let w, h = 1, 1 in
      let mask = Gdk.Bitmap.create ~window:win ~width:w ~height:h () in
      let pixmap = Gdk.Pixmap.create ~window:win ~width:w ~height:h ~depth:1 () in
      let color = Gdk.Color.alloc (Gdk.Color.get_system_colormap ()) (`RGB (0, 0, 0)) in
      Gdk.Cursor.create_from_pixmap pixmap mask color color w h

which I use as follows: 


  let win = GWindow.window ~resizable:true () in
  ignore (win#connect#destroy GMain.quit) ;

  (* More code here. *)

  win#show () ;

  (* Must set the cursor after win#show () or we get a Gpointer.NULL exception. *)
  let cursor = create_null_cursor win#misc#window in
  Gdk.Window.set_cursor win#misc#window cursor ;

  GMain.main ()

Problem solved.

Posted at: 21:36 | Category: CodeHacking/Ocaml | Permalink

Tue, 28 Oct 2008

Zytouch Driver.

At bCODE, we're using some projected capacitive touchscreens by a UK company called Zytronic for our Ubuntu Dapper based embedded devices.

When was first looking for touchscreens back in 2006, we chose the ones form Zytronic because they connected via USB and they had Linux drivers. Unfortunately, these drivers turned out to be binary only and were compiled for Redhat 9. Of course the big difference between Redhat 9 and Dapper was the Redhat used Xfree86 and Dapper was using Xorg. In spite of that, the binary drivers did sort of work, but were flaky and at times chewed up way too much CPU for no apparent reason.

In order to get something working quickly, I snooped the USB bus of a touchscreen connected to a windows machine to get a basic idea of the USB communication. It turned out that under normal conditions, all data traffic was from the touchscreen to the host using USB bulk transfers. The odd thing was that the amount of data transferred per unit time was much more than one would expect from something like a touchscreen.

In order to explore the data more fully, I then used libusb to whip together a Linux program that could find the device (Product:Vendor identifier of 14c8:0002) on the USB bus and then sit in a loop reading the USB data and printing it to the screen in hexadecimal.

Watching the hex data scroll by, it quickly became obvious that the data was the raw X/Y capacitive sensor readings for the screen. One complete read from the screen would consist of 32 bytes, one for each of 16 x-direction columns and one for each of 16 y-direction rows. Getting good mouse pointer performance out of this data was a little difficult due to a number of factors:

Fortunately I had quite a bit of Digital Signal Processing knowledge and already had all the conceptual tools I needed to deal with this raw data. In the end I came up with a solution [Note 1] that consisted of:

Once we had the X/Y position data we needed to get it into the Xserver. The easiest and quickest way to do this was using the XTest extensions.

bCODE has now been using this touchscreen driver for two years, even updating it to use a later model from Zytronic (Product:Vendor identifier of 14c8:0003) which did its own filtering and spat out high quality X/Y values.

The reason I am blogging all this now is that bCODE has decided to release the code for this driver under the terms of the GNU GPL V3. The code is copyright bCODE Pty Ltd and I am listed as the author and maintainer and the code with live on my web site. Most of the nitty gritty details are in the Readme.txt file. The driver source code also includes a calibration utility written in Ocaml using the Ocaml Cairo bindings.

Note 1: It should be noted that I did most of the reverse engineering work during a period when I was insanely busy. After that week, I had a very rough proof of concept driver that still needed quite a bit of work. In the following three weeks, my manager Sean, in his spare time, hacked on the code, fixed bugs and even improved X/Y positioning algorithm.

Posted at: 22:03 | Category: CodeHacking | Permalink

Sat, 18 Oct 2008

Foobar 2000 and the Rabbit.

Foobar 2000 (see also the Wikipedia entry) is a media player for a legacy operating system commonly known as Microsoft Windows. Secret Rabbit Code is an audio sample rate converter that I wrote, and released under the terms of the GNU GPL 2002.

As the sole author and copyright owner of Secret Rabbit Code I have also made it available under a commercial use license (PDF) that is currently earning me a small income. However, developing Secret Rabbit Code was difficult, took a huge amount of research and the development of many prototypes which were thrown away. Now, after 6 years, that income is coming close to covering the cost of developing that initial version. It still has some way to go to cover the cost of the subsequent maintenance and the improvements I have made.

In 2005 I became aware that someone had released a binary only plugin for Foobar 2000 that used Secret Rabbit Code to do sample rate conversion. The fact that this was a binary only release was not the only problem. There was also the problem of Foobar being under a license that was not GPL compatible.

First off, I emailed the ISP in France where the binary was being hosted and asked for the download to be taken down. I also tried to track down the author of the plugin since authorship was not obvious from the download. Within a day or two I was able to track him down via the Hydrogen Audio forums.

The final result of the discussion on that forum was that I decided I would write and release a Secret Rabbit Code based plugin for Foobar. This of course involved development for windows on windows a platform I rarely if ever use and which I actually prefer not to work on. However after some 10 or 12 hours work I had a working plugin that I posted on my website. I also added a Paypal donation button on the page hoping to get paid for the time and effort I put into creating the plugin.

Unfortunately, the donations have been few and far between. Since 2005 when the plugin was released I have only had about 10 people pay the measly US$10 I am asking for. That is despite the fact that I have proven interest in this plugin. The page has had over 30000 hits since 2005, and I get an email every couple of weeks asking if there is a more recent version using later versions of Secret Rabbit Code or a version for other versions of Foobar 2000.

So here's how it stands:

Since most users of this plugin don't think I should be paid for my work creating it for use with Foobar on Windows, I currently have no intention of releasing a new version of this plugin. When and if I get a decent stream of payments for the work I have put in so far I will roll out a new version and maybe even an updated plugin for other versions of Foobar.

I will answer Foobar related emails from people who have donated or work for companies that paid for a commercial use license. The vast majority of other emails regarding the Foobar plugin will be directed to this blog post.

Posted at: 09:21 | Category: CodeHacking/SecretRabbitCode | Permalink

Wed, 20 Aug 2008

Just Drawing Stuff on the Screen.

Richard Jones laments that drawing stuff on the screen is harder than it should be. I haven't seen his code, but it looks like he might be trying to do it with Ocaml and GTK which probably is more difficult than it should be. GTK isn't really meant for that sort of stuff.

Fortunately, there is a really well designed and thoroughly thought out library for doing graphics called Cairo, which even has a really great set of Ocaml bindings. On Debian/Ubuntu, the Cairo bindings can be installed using: 


   sudo apt-get install libcairo-ocaml-dev

I messed about with Ocaml and Cairo about a year ago and came up with this little demo. 


  (*
  **    http://www.e-dsp.com/what-are-fourier-coefficients-and-how-to-calculate-them/
  **
  **    http://en.wikipedia.org/wiki/Fourier_series#Definition
  *)

  type fourier_series_t =
  {   a0 : float ;
      an : float array ;
      bn : float array ;
      }


  let initial_size = 200

  let two_pi = 8.0 *. atan 1.0

  let sum_float_array ary =
      Array.fold_left (fun x y -> x +. y) 0.0 ary


  let calc_series max_n ary =
      (*
      **    This uses a rough numerical approximation to integration.
      **    As long as the array is long enough (say 1000 or more elements), the
      **    results should be reasonable.
      *)
      let len = float_of_int (Array.length ary) in
      let calc_Xn trig_func n =
          let n = n + 1 in
          let ary = Array.mapi (
		  		fun i x -> x *.
                trig_func ((float_of_int (n * i)) *. two_pi /. (len -. 1.0))
				) ary
          in
          2.0 *. (sum_float_array ary) /. len
      in
      let a0 = (sum_float_array ary) /. len in
      let an = Array.init max_n (calc_Xn cos) in
      let bn = Array.init max_n (calc_Xn sin) in
      { a0 = a0 ; an = an ; bn = bn }


  let waveform_of_series outlen series =
      (*
      **  Given a fourier series, calculate a single cycle waveform of the
      **  specified length.
      *)
      let calc_point i =
          let x = two_pi *. (float_of_int i) /. (float_of_int (outlen - 1)) in
          let asum = sum_float_array (Array.mapi (
                    fun i an -> an *. (cos (float_of_int (i + 1) *. x))) series.an
                    )
          in
          let bsum = sum_float_array (Array.mapi (
                    fun i bn -> bn *. (sin (float_of_int (i + 1) *. x))) series.bn
                    )
          in
          series.a0 +. asum +. bsum
      in
      Array.init outlen calc_point


  let fold_over_clipped_sine gain len =
      let point i =
          let x = gain *. sin (two_pi *. (float_of_int i) /. (float_of_int len)) in
          if x > 1.0 then x -. 2.0
          else if x < -1.0 then x +. 2.0
          else x
      in
      Array.init len point


  let redraw w series _ =
      let cr = Cairo_lablgtk.create w#misc#window in
      let { Gtk.width = width ; Gtk.height = height } = w#misc#allocation in
      Cairo.save cr ;
      (   Cairo.identity_matrix cr ;
          let border = 20.0 in
          Cairo.move_to cr border border ;
          Cairo.line_to cr border (float_of_int height -. border) ;
          Cairo.stroke cr ;

          let wave_width = width - 100 - (int_of_float border) in
          let middle = float_of_int height /. 2.0 in
          let wave_height = 0.7 *. (middle -. border) in

          Cairo.move_to cr border middle ;
          Cairo.line_to cr (border +. float_of_int wave_width) middle ;
          Cairo.stroke cr ;

          Cairo.move_to cr (border +. float_of_int wave_width) border ;
          Cairo.line_to cr (border +. float_of_int wave_width)
                                      (float_of_int height -. border) ;
          Cairo.stroke cr ;

          Cairo.set_source_rgb cr 1.0 0.0 0.0 ;
          let wave_data = waveform_of_series wave_width series in
          Cairo.move_to cr border (float_of_int height /. 2.0) ;
          Array.iteri (fun i x ->
                        Cairo.line_to cr (border +. float i)
						      (middle -. wave_height *. x))
                        wave_data ;
          Cairo.stroke cr ;
          ) ;
      Cairo.restore cr ;
      true


  let () =
      if Array.length Sys.argv != 2 then
      (   Printf.printf "Usage : %s <series length>\n\n" Sys.argv.(0) ;
          exit 0 ;
          ) ;

      let series_len = int_of_string (Sys.argv.(1)) in

      let w = GWindow.window ~title:"Fourier Series Demo" ~width:600 ~height:400 () in
      ignore (w#connect#destroy GMain.quit) ;

      let b = GPack.vbox ~spacing:6 ~border_width:12  ~packing:w#add () in
      let f = GBin.frame ~shadow_type:`IN ~packing:(b#pack ~expand:true ~fill:true) () in
      let area = GMisc.drawing_area ~width:initial_size ~height:initial_size
                    ~packing:f#add ()
      in
      let array_len = 1000 in
      let wave = fold_over_clipped_sine 1.2 array_len in
      let series = calc_series series_len wave in

      ignore (area#event#connect#expose (redraw area series)) ;

      w#show () ;
      GMain.main ()

The above code can be compiled using: 


    ocamlopt -I +cairo -I +lablgtk2 cairo.cmxa lablgtk.cmxa cairo_lablgtk.cmxa \
	    gtkInit.cmx fsdemo.ml -o fsdemo

and the output looks like this:


Fourier Series Demo screen shot

So while I agree that the 140 of lines of code here is about 30 times as much as Richard's code from his ZX80 days, I also think the results are at least 30 times as good.

Posted at: 22:29 | Category: CodeHacking/Ocaml | Permalink

Mon, 18 Aug 2008

Nemiver : A GUI debugger for GNOME.

The many years, Linux has lacked a good GUI debugger for C and C++ programs. Yes, everyone knows about GNU GDB, but that is a command line debugger and really not very useful for stepping through a program. There was also the Data Display Debugger (DDD) which uses the Motif widget set, usually supplied by the Lesstif Project. Unfortunately, Lesstif development has basically been abandoned and OpenMotif is not really an option because its license fails to meet term 8 of the Open Software Definition.

This means that for many years, developers on Linux have tended to avoid the "stepping through code with a debugger" approach to debugging. While I think that single stepping is not the most applicable to every debugging problem, there are times when single stepping is useful and possibly also the fastest way to track down a problem.

However, I was recently made aware of a new GUI debugger for the GNOME (ie really the Linux) desktop, Nemiver.


nemiver screen shot

The only problem with nemiver is that the version in Ubuntu Hardy is a little old and was giving me a few troubles. However, after building and installing a version 2.2.0-2 package of libgtksourceviewmm-2.0 from source I was able to build nemiver from SVN and so far its working way better than DDD ever did.

So, here it is, a good looking, stable and capable GUI debugger for Linux.

Posted at: 19:39 | Category: CodeHacking | Permalink

Sat, 19 Jul 2008

Ocaml and Unix.select.

At the June meeting of FP-Syd, Tim Docker gave a presentation about his Tuple Space Server written in Haskell. This presentation rather intrigued me because I have had a long term interest in numerical analysis and numerical optimisation problems which lend themselves very well to parallel and distributed computing. I decided I should write a Tuple Space Server myself, in Ocaml.

Tim's Tuple Space server used threads and Software Transactional Memory (STM) to handle the connection of multiple masters and workers to the server itself. Although the Ocaml CoThreads library does have an STM module I thought there was probably an easier way.

In my day job I'm working on some C++ code that handles multiple network sockets and open file descriptors using the POSIX select system call. On Linux at least, there is a select tutorial man page which gives a example of using select written in C.

The beauty of select is that it allows a single process to multiplex multiple sockets and/or file descriptors without resorting to threads. However, the C example in the tutorial clearly demonstrates that this system call is a bit of a pain to use directly. Fortunately, for the project at work, I had some really great C++ base classes written by my colleague Peter to build on top of. These base classes hide all the nastiness of dealing with the system call itself by wrapping the select call into a daemon class and providing a simple base class which clients of the select call can inherit from.

For Ocaml there is a thin wrapper around the C library function in the Unix module and it has the following signature: 


  val select :
    file_descr list -> file_descr list -> file_descr list -> float ->
      file_descr list * file_descr list * file_descr list

It takes three lists of file descriptors (one descriptor list for each of read, write and exceptions), a float value for a timeout and returns a tuple of three lists; one each for the file descriptors ready for reading, writing and exception handling.

Whereas the C++ solution had a daemon class, the Ocaml version instead has a daemon function. The daemon function operates on a set of tasks, with one file descriptor per task. Each file descriptor was embedded in a struct which I named task_t: 


  type task_t =
  {   fd : Unix.file_descr ;
  
      mutable wake_time : float option ;
  
      mutable select_on : bool ;

      mutable process_read : task_t -> bool * task_t list ;
  
      mutable process_wake : task_t -> bool * task_t list ;
  
      finalize : task_t -> unit ;
      }

The fields of the struct are as follows:

The first thing to note in the above is the careful use of an immutable field for the file descriptor and mutable fields for process_read, process_wake and wake_time. The file descriptor is immutable so that any client code does not change its value behind the back of the daemon.

The others fields of the struct are purposely made to be mutable so that they can be changed on the fly. The functions process_read and process_wake both return their results in the same manner, a tuple containing two items:

The actual daemon run loop keeps the tasks in a hash table where the key is the file descriptor. Once the initial set of tasks is in the hash table, the loop basically does the following:

  1. Find the file descriptors of all the tasks in the hash table which their select_on field set to true (uses Hashtbl.fold).
  2. Find the minimum wake_time timeout of all the tasks (this is actually done on the same pass over all items in the hash tables as step 1.).
  3. Pass the file descriptors from step 1. to the select with the timeout value found in 2. (The lists for writable and exception file descriptors are empty.)
  4. When select returns a list or file descriptors ready to be read, map the file descriptor to a task using the hash table and then run the process_read function of each readable task.
  5. For each task whose wake_time is exceeded, run its process_wake function.
  6. For steps 4. and 5., if a task's process function returns false as the first element of the tuple it returns, remove the task from the hash table and run the task's finalize function. Also if the second element in the tuple is a non-empty list, then add the tasks to the hash table.

The above code was placed in a module named Daemon. Using this module, I've whipped up a simple demo program, an echo server the source code of which is available here. The tarball contains four files:


Makefile The project's Makefile.
daemon.ml The Daemon module.
echo-server.ml The Echo server.
tcp.ml A module of TCP/IP helper functions.

To compile this you will need the Ocaml native compiler which can be installed on Debian or Ubuntu using: 


  sudo apt-get install ocaml-nox

The server can be built using make and when run, you can connect to the server using: 


  telnet localhost 9301

All lines sent to the server will be immediately echoed back to you.

Posted at: 21:10 | Category: CodeHacking/Ocaml | Permalink

Sat, 24 May 2008

Objects vs Modules.

Although I've been using Ocaml for a several years now, I've not yet been in a situation where I've needed to write an Ocaml class to define a C++/Java/Python/Smalltalk/OO style object. I've found that most of the problems I encountered could be easily solved using functional code and that Ocaml's objects didn't provide an obviously better solution. Until now (or so I thought).

The problem was one of moving around the filesystem keeping track of the old directories so they were easy to return to. The obvious model for this was the pushd and popd built-ins in command shells like GNU Bash. This functionality can be easily wrapped up in an Ocaml object as in the following example and demo code (which needs to be linked to the Unix module): 


  class dirstack = object
      val mutable stack = []

      method push dirname =
          (* Find the current working directory. *)
          let cwd = Unix.getcwd () in
          (* Change to the new directory. *)
          Unix.chdir dirname ;
          (* If successful, push old cwd onto the stack. *)
          stack <- cwd :: stack

      method pop () =
          match stack with
          |    [] -> failwith "Directory stack is empty."
          |    head :: tail ->
                  Unix.chdir head

  	end

  let () =
      print_endline (Unix.getcwd ()) ;
      let dstack = new dirstack in
      dstack#push "/tmp" ;
      print_endline (Unix.getcwd ()) ;
      dstack#push "/bin" ;
      print_endline (Unix.getcwd ()) ;
      dstack#pop () ;
      print_endline (Unix.getcwd ()) ;
      dstack#pop () ;
      print_endline (Unix.getcwd ())

However, there are some problems with the above code. Firstly, if the push and pop methods need to be used throughout the program, the dstack object needs to be made more widely accessible using one of the following three methods:

  1. Being placed in the global scope.
  2. Being made into a Singleton objecct.
  3. Being passed around as a parameter to whatever function may need it.

Yuck! Yuck! Double yuck! Suddenly, this object oriented solution didn't look like such a great idea.

Then it struck me. This object can be easily transformed into an Ocaml module like this: 


  module Dirstack = struct
      let stack = ref []

      let push dirname =
          (* Find the current working directory. *)
          let cwd = Unix.getcwd () in
          (* Change to the new directory. *)
          Unix.chdir dirname ;
          (* If successful, push old cwd onto the stack. *)
          stack := cwd :: !stack

      let pop () =
          match !stack with
          |    [] -> failwith "Directory stack is empty."
          |    head :: tail ->
                  stack := tail ;
                  Unix.chdir head

     end

  let () =
      print_endline (Unix.getcwd ()) ;
      Dirstack.push "/tmp" ;
      print_endline (Unix.getcwd ()) ;
      Dirstack.push "/bin" ;
      print_endline (Unix.getcwd ()) ;
      Dirstack.pop () ;
      print_endline (Unix.getcwd ()) ;
      Dirstack.pop () ;
      print_endline (Unix.getcwd ())

This solution using a module is much better than the one using an object. The Dirstack module itself is globally accessible and is already a singleton while the stack used to hold past directories is implemented as a list whose scope is limited to the module itself. (Furthermore, if Dirstack is implemented in its own file instead of using a module defined within a larger file, then the stack variable can be hidden completely by not listing it in the Dirstack interface file.)

So while I'm pleased with this solution, it does mean that I'll have to continue my hunt for a problem where an object provides a better solution than any other feature of the Ocaml language. This is particularly ironic because when choosing between two strict statically typed languages, Haskell and Ocaml, I chose Ocaml because I thought I needed objects. However, I stuck with Ocaml because of its pragmatism.

Posted at: 07:45 | Category: CodeHacking/Ocaml | Permalink

Sun, 20 Apr 2008

Cross Compiling for Legacy Win32 Systems (Part 2).

Cross compiling from Linux to Windows requires the installation of a couple of packages. On a Debian or Ubuntu system this can be done using: 


  sudo apt-get install build-essential
  sudo apt-get install mingw32 mingw32-binutils mingw32-runtime wine

I'm running Ubuntu's Hardy Heron pre-release and the following is known to work with these versions: 


  mingw32               4.2.1.dfsg-1ubuntu1
  mingw32-binutils      2.17.50-20070129.1-1
  mingw32-runtime       3.13-1
  wine                  0.9.59-0ubuntu5

For an example of a project which can be successfully cross-compiled, I have chosen libogg which is one of the two libraries required to encode and decode Ogg/Vorbis files. I also happen to know that the current libogg sources in the Xiph Foundation's SVN repository cross-compile from Linux to Windows correctly because I committed the patch to make it possible.

However, we need to look ahead a little. After we have cross compiled libogg we will also want to cross compile the associated libvorbis library which relies on libogg. We therefore need to configure libogg so that when we install it, it can be found by the libvorbis configure script.

For me that meant creating a MinGW32 directory in my home directory: 


  mkdir $HOME/MinGW32

The next step to to grab the libogg source code from the Xiph SVN server. This can be achieved using the command: 


  svn co http://svn.xiph.org/trunk/ogg libogg

Changing into the libogg directory, we are now ready to configure, test and install the library. That can be done using: 


  ./autogen.sh
  ./configure --host=i586-mingw32msvc --target=i586-mingw32msvc \
      --build=i586-linux --prefix=$HOME/MinGW32
  make
  make check
  make install

The first command above, runs the auto tools to generate that configure script. The second command, configure is broken across two lines. It sets up the generated Makefiles to compile Windows binaries from a Linux host, with the install directory we set up before. The third line builds the windows version of libogg, the fourth line runs the test suite, with the windows executables being run under WINE and the final line installs everything in the MinGW32 directory created earlier.

All of the above commands should pass without errors. If they don't, check your versions of of the mingw cross compiler tools and/or WINE.

Posted at: 20:51 | Category: CodeHacking/MinGWCross | Permalink

Wed, 16 Apr 2008

Cross Compiling for Legacy Win32 Systems (Part 1).

My main two FOSS projects, libsndfile and libsamplerate have significant numbers of users that are tied to that particularly odious legacy system, Microsoft Windows. Since I don't normally use Windows myself, maintaining support for that OS has always been a huge pain in the neck.

Originally I shipped Microsoft project files for libsndfile, but that became unworkable because the different versions of the Microsoft tools (Visual C++ 5, Visual C++ 6, Visual Studio 2003, Visual Studio 2005 etc) used different and incompatible project file formats. I solved this by shipping a simple Makefile that used Microsoft's nmake and the command line compilers to build libsndfile. However, by about 2004, the Microsoft compiler's complete lack of support for the 1999 ISO C Standard made maintaining support too much trouble, so it was dropped.

Instead, I started using Cygwin and MinGW to compile libsndfile on Windows. Both of these tool-sets use a version of the GNU GCC compiler just like Linux and building libsndfile using these two tool-sets was trivial: 


  ./configure
  make
  make check

Of course there were howls of protest from Windows users, but since they (with a small number of exceptions) had contributed so little, I didn't fell like I owed them anything. I also started releasing pre-compiled Windows binaries at the same time as the source code tarballs were released.

However, while the MinGW compiler was a huge improvement over the Microsoft one it was still a huge pain in the neck. I had to keep a Windows machine and keep it updated and patched against vulnerabilities. Furthermore, installing and updating MinGW was a painful manual process. Oh how I longed for a Debian/Ubuntu style apt-get command to look for and install updates. Finally, copying source code back and forth between Linux and Windows while debugging Windows issues was another pain point because version control systems like GNU Arch and bzr simply didn't work very well on Windows.

In about 2004, I tried the MinGW Linux to Windows cross compiler, a compiler that runs on Linux but generates binaries for Windows. This compiler worked, but left one rather large problem; how do I run libsndfile's rather large and comprehensive test suite? Compiling libsndfile without running the test suite is a waste of time. I did try to run the tests under WINE (the Windows emulator), but at the time tests were failing under WINE that didn't fail on Windows.

From that time on, I would try running the cross-compiled test suite under WINE once or twice a year. Then, some time in the last year or so, the number of problems with the test suite dropped to one, which was only a FIXME message. A little hacking on the WINE sources resulted in a patch that was sent to the WINE mailing list and has since been applied to the main WINE source tree.

With that bug fixed, I can now cross compile from Linux to Windows and run the full libsndfile test suite under WINE. That means that Windows has just become that little bit less relevant that it was before.

A future post will explain how to set up the cross compiler and WINE and walk through compiling and testing of a standard FOSS project.

Posted at: 23:12 | Category: CodeHacking/MinGWCross | Permalink

Fri, 11 Apr 2008

You Stupid Git!

As far as I can tell, the absolute, canonical, got-to-first documentation for the git distributed version control system (DVCS) can be found here:

http://www.kernel.org/pub/software/scm/git/docs/user-manual.html

This documentation seems comprehensive and well laid out. It explains commits, manipulating-branches, merging, collaborative development and the pretty damn interesting rebase and bisect commands. This documentation is called a user manual but it contains sufficient examples to make it a pretty damn fine tutorial.

Normally something like "here's a link to the documentation" would not be worthy of a blog post. However, failure to find the canonical user manual could lead a person (ie me) to post messages to mailing lists saying things like:

"I'm sure git is very clever and all, but its UI and documentation is probably the most user hateful thing I have seen [since] sendmail's cf files."

or, on finding a one hour long video screen-cast tutorial (apparently aimed at all those Ruby on Rails writing Mac OSX users):

"This makes me wonder, how fscked up does a DVCS have to be that you need tens of megabytes of video to show how it works when Bzr and many others can do it with less than ten kilobytes of html text?"

So while I was wrong about the documentation I still have huge reservations about git's user interface and stand by this statement:

"I am currently trying to learn git and I can see very clearly that git is designed by kernel programmers whose normal approach to a user interface is something like a Unix system call."

I'm sure git is a powerful tool and the rebase feature is something I've been wishing for in other systems for some time, but git's UI is already starting to grate.

Posted at: 20:02 | Category: CodeHacking | Permalink

Sun, 06 Apr 2008

Ocaml : Exception Back Traces in Native Code.

Some time ago I wrote a blog post about exception back traces which at the time of that post only existed for the Ocaml byte code compiler.

However, version 3.10 of the Ocaml compiler which was released about a year ago, included exception back traces for native code as well as byte code. With the imminent release of Ubuntu's Hardy Heron, version 3.10 of the compiler is about to become much more widely available .

Enabling exception back traces is as simple as adding the "-g" option to the ocamlopt command line and then setting a single environment variable as follows. 


  export OCAMLRUNPARAM="b1"

Posted at: 12:48 | Category: CodeHacking/Ocaml | Permalink