From: jloup@chorus.fr (Jean-loup Gailly)
Newsgroups: comp.compression,misc.legal.computing
Subject: data compression patents (was: LZRW, patents, products)
Date: 29 Sep 92 10:22:25 GMT
Reply-To: jloup@chorus.fr (Jean-loup Gailly)
Followup-To: misc.legal.computing

(followups to misc.legal.computing)

Andy McFadden <fadden@uts.amdahl.com> writes in comp.compression:

> I know that the patent status of LZRW* is still fuzzy because of Gibson &
> Graybill, but I'm not familiar with patent law and was wondering...
> (1) can a commercial product use LZRW without paying tribute to G&G?

Note that different patents apply to different versions of the LZRW series.
The Gibson and Graybill patent 5,049,881 applies only to lzrw1. The
Jung patent 5,140,321 applies to lzrw3-a. (Note that Ross Williams
discovered lzrw3-a before Jung, and that Jung applied for his patent
two months after lzrw3-a was posted on comp.compression.)

The answer to your question (1) is that you can't use LZRW1 unless you
either license the patent from G&G or get the patent invalidated.

> (2) if not, can a program be released into the public domain which uses them?
>   (given that LZRW1-4 are still up for FTP, I'd guess this is a "yes", but
>   I'd prefer an authoritative answer.)

Yes, but the program should explicitly warn that its usage is allowed
only 'for instruction and amusement' (that's the wording of the patent
law). This is what Dan Bernstein is doing in the yabba package, which
includes an implementation of AP coding patented by Storer (4,876,541).

If (s)he does not  include such a warning, the author of the public domain
program can be sued for 'contributory infringement'. The holders
of the RSA patents have threatened to do this for the author of the
free program PGP, which uses RSA public key encryption.

> I'm hoping to avoid having to deal with Unisys (LZW...ouch).

That's yet another patent (4,558,302), but its status is very unclear
currently because IBM has another patent (4,814,746) on exactly the
same algorithm. The IBM patent application was filed three weeks
before that of Unisys, but the US patent office failed to recognize
that they covered the same algorithm. (The IBM patent is more general,
but its claim 7 is exactly LZW.)


Let me take this opportunity to tell you that I just discovered two
patents on run length encoding, by Tsukiyama: 4,586,027 and 4,872,009
granted in 1986 and 1989 respectively. The first one covers run length
encoding in its most primitive form: a length byte followed by the
repeated byte. The second patent covers the 'invention' of limiting
the run length to 16 bytes and thus the encoding of the length on 4
bits.  Here is the start of claim 1 of patent 4,872,009, just for
pleasure:

    1. A method of transforming an input data string comprising a plurality
    of data bytes, said plurality including portions of a plurality of
    consecutive data bytes identical to one another, wherein said data
    bytes may be of a plurality of types, each type representing different
    information, said method comprising the steps of: [...]

These patents on run length encoding are about as absurd as the patents
on the xor cursor (4,197,590), on the idea of include files (4,674,040),
or on standard byte ordering (4,956,809).

Jean-loup Gailly
jloup@chorus.fr