Joe is an OCaml programmer suffering from chronic Not-Invented-Here syndrome, trying to re-implement everything in a memory-safe language with a high abstraction level in the attempt to build a better world.

At night he works at Robur ( ), a software cooperative working with OCaml and MirageOS. He daylights as a computer security buff.

URLs for Joe

No URLs found.

Workshop Implementing the LZO decompression algorithm

Bring your beer, leave with a working implementation of the LZO decompression algorithm.

Perhaps you want to use it on your BornHack badge to cram more stuff into its tiny flash, showcase the superiority of your ( favoritest || fastest || dependently-typed-est) programming language, or merely go to Mars on your own terms.

In any case it's a fun little exercise with a somewhat usable end result.

I recently had to implement it in order to read packets sent to Robur's OpenVPN reimplementation from servers that insist on using it.

What is LZO

LZO is a sliding-window compression algorithm based on - well, Markus Oberhumer's take on Lempel-Ziv '77.

If that sounds a tad academical to you, have no fear - the algorithm is simple; it consists of two instructions:

There are eight ways to encode these single-byte instructions, some of them requiring additional operands to be read from the input string. Everything can be implemented with addition, subtraction, multiplication, bit shifts, and bit masks. No fancy math required.

Unfortunately it is pretty hard to find a description of how that works in practice, and most people end up using either the official C implementation or a directly translated, unreadable port, leading to gems like this (source):

There is no version of LZO in pure Java. The obvious solution is to take the C source code, 
and feed it to the Java compiler, modifying the Java compiler as necessary to make it compile.

We can do better, and we can do so in an afternoon.

What should you bring:

What will be provided:

Will we be implementing a compression algorithm too?

If we have time! It is very easy to write a compressor that can compress repeated strings of a single character, so that we can definitely do; more advanced strategies will be left to the imagination of the participants. While the decompression algorithm is set in stone, compression depends on a strategy for achieving compression using chains of the aforementioned instructions and operands, so there are many ways to go about it.

Scheduled Instances of "Implementing the LZO decompression algorithm"