Wow   Posted by: Teasy on Tuesday, September 03, 2002

Another great compression algorithm made easy!

Fatal bugs makes the routine unpredictable   Posted by: xxcopy_man on Sunday, April 11, 2004

I just went though some section of the code by hand
and found a few quite serious bugs. Based on the
bugs, this program as is would not produce a predictable
results.

More specifically, in, Compression() function,

1. uword Command = 0; // needs initialization
2. uword Pos = 0; // needs initialization

I'm pretty sure Command need to be initialized to 0.
But, I don't know for sure if 0 is right for the
initial value of Pos (probably it is).

I did not even finish reading/analyzing the whole code
but it is unfortunate that the program was probably
never tested (or, the particular run-time environment
always provided the consistent initial value for
these variables that the author might never caught
the bug). It is even more probable that the initialized
value was non-zero (e.g., 0xcccc as in the case of
Win32 environment --- I believe Microsoft deliberately
chose 0xcccc as the default initial value for non-initialized
local variables for consistent behavior of buggy program
like this). At any rate, if a program has this kind
of bug, it cannot be given a high mark for rating.

On the other hand, the whole program being quite small,
it serves a good starting point for biginners in the
LZ algorithm --- I's a seasoned C programmer but
never had needs to learn the LZ algorithm. I got
a glimpse of it and this source code taught me something.
But, without knowing what the Pos value is at the
beginning, I just lost interest in investing any more
of my time to mentally go through the algorithm :-(

I will go elsewhere to locate similarly written (concise)
source code and learn it there. So, my rating reflect
this (possibly minor in pedagogical point of view) blemish.
Otherwise, the rating would have be even 5-star.

Still, I'm appreciative of the work done by Kurt.

Kan Yabumoto

No fatal bugs at all   Posted on Thursday, September 16, 2004

The previous comment is incorrect. This algorithm is well tested and widely used by different projects. 'Command' does not need be initialised as it is not used before it is initialised, but compilers will issue this as a warning.

Imatix have issued a version of this (in their SFL) with a couple of small efficiency improvements, but have released it under their own license.

Correction (Not rated)   Posted on Thursday, September 16, 2004

Command DOES need setting to 0, Pos doesn't - it is set in GetMatch before it is used.

If you are using this library you will need to make that modification.

No it does not ... please try to grasp the code (Not rated)   Posted by: Kurt Haenen on Wednesday, October 17, 2007

First of all, for the record: LZRW1 is actually an algorithm from Ross Williams. At the moment I created LZRW1/KH I was only aware of the 68000 implementation of Ross, which I had tried to understand out of pure interest in compression. I had a small improvement on that and then ported the result also to C and Pascal, unaware that Ross also had a C implementation. So, although this is probably my most famous code (especially the Pascal version), any praise for the algorithm should go to Ross Williams (and from the patent info it seems some other people before him and independent from him).

Now, to remove any doubt: Command in Compression does NOT need to be initialized to 0. The reason for this is simple:
- Bit is initialized to zero
- Command-bits (0 or 1) are shifted into command one at a time at the lower end until Bit becomes > 15
- At that time the 16 bits are taken from Command and output to the destination.
- If at the end Command doesn't contain exactly 16 bits, (16-Bit) zeroes are shifted in to reach 16 defined bits which are stored in Dest.

In short, it is indeed undefined what the value of the bits in Command is at the beginning, but it doesn't matter, since they are never used.