After a short look at the history.dat file of the Mozilla FireFox browser I was convinced: the person who had thought up the file format is insane, and it would take quite some time to program my own parsing solution using the Perl programming language.
Jamie Zawinski's LiveJournal has a nice rant on the file format, and gives some pointers to documentation and, hurray, a Perl program to parse the insane Mork file format.
After I tweaked the mork Perl program written by Jamie a little, it produced the desired output.