Matt Mahoney, Feb. 14, 2008.

The contents of this archiver are released to the public domain.

This archive contains implementations of lzrw1, lzrw1-a, lzrw2,
lzrw3, lzrw3-a and lzrw5 compression algorithms from 
http://www.ross.net/compression/index.html by Dr. Ross Williams in 1991.
They were written as memory-to-memory compressors, not as complete programs.
I wrote drivers to implement file compressors.  Each program takes 3
arguments as follows:

To compress:    c input output
To decompress:  d input output

where 'input' and 'output' are file names.

Each of the programs was compiled for Windows using MinGW g++ 3.4.2
and packed with UPX 3.00w.  For all programs except lzrw1, the programs are
compiled as follows:

  gcc -O2 -s -fomit-frame-pointer -march=pentiumpro %1.c main.c -o %1
  upx -qqq %1.exe

where %1 is lzrw1-a, lzrw2, lzrw3, lzrw3-a or lzrw5.  lzrw1 is compiled
without the driver main.c:

  gcc -O2 -s -fomit-frame-pointer -march=pentiumpro lzrw1.c -o lzrw1
  upx -qqq lzrw1.exe

For lzrw5 only, the following line in main.c should be changed from

  #define BUFSIZE 0x100000
to
  #define BUFSIZE 0x10000

Since the programs are memory to memory compressor, the driver divides
the input into blocks of size BUFSIZE which are compressed independently.
Using larger blocks generally improves compression.  However, lzrw5
is only guaranteed to work for BUFSIZE up to 0x10000 (64K).  I tested
on enwik8 and enwik9 from http://cs.fit.edu/~mmahoney/compression/text.html
with 0x30000 and it did compress better, but decompression failed at 0x40000.

Memory usage is 2 * BUFSIZE plus a small amount for the algorithm itself.
lzrw5 uses 384K, lzrw2 uses 24K, and the other algorithms use 16K.

Source code is from http://www.ross.net/compression/index.html
but modified as follows:

main.c was not part of the original code.  It parses the command line,
opens input and output files, queries the algorithm for the amount of
working memory, allocates it, then compresses by dividing the input
into blocks of size BUFSIZE, compressing to a second buffer of the
same size, then outputing the compresssed size (as a 4 byte number,
MSB first) and the compressed data.  No other file headers are used.
Working memory is zeroed, so all algorithms that use it are deterministic.

lzrw1.c does not use the same interface as the other algorithms, so
I added a driver to this file similar to main.c.  I also made the
following changes:
- Commented out initial comments.
- defined TRUE as 1.
- changed definitions of UWORD and ULONG assuming 32 bit ints.
- made the algorithm deterministic by initializing hash[] to {0}.

lzrw1-a.c - commented out header text (no code changes).

lzrw2.c, lzrw3.c, lzrw3-a.c - no changes needed.

lzrw5.c - commented out 68000 assembler code.  Removed uncommented
header text.  Changed  'UCARD execute_c_code = FALSE;' to TRUE.

fast_copy.h - no changes.  main.c implements fast_copy() using memcpy().

compress.h - no changes (extracted from old_lzrw_headers.h)

port.h - (from old_lzrw_headers.h) added machine-dependent type
definitions that should work on any machine where type int is 32 bits.

Algorithm summary:

lzrw1 is byte-aligned LZ77 with a 12 bit offset and 4 bit length field
allowing lengths 3-16.  Each group of 16 phrases (pointers or literals)
is preceded by 2 flag bytes to distinguish pointers from literals.  
Matches are found using a 4K hash table without confirmation which is 
updated after each phrase.

lzrw1-a the length field represents values 3-18.

lzrw2 replaces the offset with a 12 bit index into a rotating table
of offsets, allowing the last 4K phrases (rather than 4K bytes) to
be reached.  The decompressor must reconstruct the phrase table
(but not the hash table).

lzrw3 replaces the 12 bit length field with a 12 bit index into the
hash table.  The decompressor must reconstruct the hash table.

lzrw3-a uses a deep hash table (8 offsets per hash) with LRU replacement.

lzrw5 uses LZW.  The dictionary is implemented as a tree.

Note: lzrw4 was never fully implemented.

Update Feb. 17, 2008
Recompiled with -s option to make *.exe files smaller.
