LZSS kernel compression

I was in a conversation at work yesterday and mentioned seeing something recently about LZSS, which I thought was interesting. No there knew anything about it and I couldn't think of where I'd come across it.

I've been spending a lot of time wandering around Amit Singh's site because of something Bill Bumgartner had written (pre-explosion) which led me to What is Mac OS X? A quick search found that Amit had mentioned that the kernel was compressed with LZSS.

I don't know why that initially surprised me, but it did. I guess it's mostly because LZSS was largely considered a very good and fast text compressor when first described in Data Compression Via Textual Substitution. My own experience should have kept me more aware of the possibilities. When Kenjirou Okubo uploaded the original compression source to GEnie (where I found it), he included this note:

This article by H.Okumura explains various algorithms of Data Compression. The article, originally uploaded in his workshop, is posted here with his permission. Also includes three C programs illustrating lzari, lzss and lzhuf methods uploaded with permission of their authors. These are the compression schemes currently being investigated by Japanese hobbiest programmers.

Haruhiko Okumura had released a pretty good version of LZSS using Bells ideas about b-trees in the spring of 1988 (Michael Dipperstein has a very accessible description of LZSS). It had a small code and memory footprint and a very efficient decompression engine. It worked really well for textual data but was pretty iffy with binary. I tinkered a bit and moved on.

In late 1990, I was in desperate need of a way to compress a Davidson 'Blaster product to a single disk. The images were my single worst problem, so I focused there. I tried out a number of things, but the solution that worked the best was to use LZSS on PICT images.

Several things were in my favor. We were using 8 bit images. We used a lot of white around the edges because many images were used to create their own masks on the fly. PICT 2 encoding was mostly straight forward (scan line RLE with a few QuickDraw specific wrinkles as I recall).

My first pass on the raw image data was less than impressive. When I later tried compressing the already compressed PICT things changed a bit. I was getting nearly 50% compression for most of the images. I got better compression with other algorithms but was never able to achieve the same kind of performance.

After deciding that LZSS would work quite well, I shoved the original and compressed sizes at the front of the new compressed PICT resources as a simple verification method and a way of preallocating the result buffer during a decode. I also moved away from the stdlib calls to pure array access since I had to deal with handles (a pointer to a pointer, floating memory access mechanism used by the classic MacOS) anyway. Preallocation and direct data access helped improve performance even more. The application was IO bound by the floppy speed so LZSS decoding was almost unnoticeable there and only added about 15% overhead when running off a hard disk on an '030 class system.

Despite a bit of poking around, I can't find a reason for Apple (or anyone else) to pick LZSS as the mechanism for compressing the kernel. Perhaps it was just a timing thing (NeXT was doing a lot of kernel work around the time when people were tinkering with LZSS)?