© 2001 by Alain Brobecker (aka baah/Arm's Tech)

LouZy77 & LouZy77D are compression algorithms, a bit slow and giving average compression ratios (better than Huffman though), but the coders and decoder are very simple, have small memory needs (except for LouZy77D coder) and the decoder is very small & fast.

Download LouZy77.zip with sources (C+Archimedes packer, ARM, 6502, 68000 depacker).

0. Introduction

While working on a simple Run Length Encoding pre-compressor, where ABCCCC is coded NoRept(2;AB)+Rept(4;C), i devised another way of coding the repetition of bytes: NoPk(3;ABC)+Copy(3;-1) with Copy(3;-1) meaning copy 3 bytes from current position-1 to current position.

In this example, and in all pure RLE cases, this new method will require more bytes to code the stream, but the depacker will remain as simple and fast as for RLE, and the method allows references to previously depacked strings as in dictionnary based compression (LZ77).

This method is almost original, meaning i had already heard about dictionnary compression before, but i had only seen LZ78 algorithms which are far different and i made the first tries before looking in the litterature for exact references. I was pleased to learn it is in fact a LZ77 variation.

1. LouZy77 compressor & decompressor

No compression at all: dest must contain SrcLen+INT(SrcLen/MaxNbNoPk)+1 bytes.File format:

       0 : End
  1..127 : NbNoPk followed with NbNoPk bytes
128..256 : NbCopy+128-Min followed by Offset-1

2. Optimality problem: Dijkstra algorithm

The greedy parsing technique used above is not always optimal.

3. Results