c8923075@cc.nu.oz (02/26/90)
I'm currently developing a Lempel-Ziv-Welch de/compression prog for a CBM64, and would like to ask anyone who've tried the same in a simular 64K memory limitation situtation for any information that would be of use. The prog is being written in 6502 Assembler (No prizes for guessing why), & I intend it to resemble what you've probabally seen on pirated games (Although this program is not for a Com.Sci assignment or simular, I have more scolarly intentions). You run the load & run the prog, it deARCs itself without accessing any external memory (Those of you familar with a 1541 d/drive would know why). What I specifically would like in the way of advice is how to impliment the LZW table, the deARCed & ARCed files within the same 64k, permitting the maximum table size (to increase compacting efficency). A proposial would be to have the table in $0200-$0800, allowing about 510 table entries; the ARCed file move forward up in memory as far as possible; the decompressed prog reconstructed from $0801 onwards; and the actual decompression code kept in $0010 to $01F0 (Stack use kept to a minimum, for a 6502 uses $0100-$01FF) For anyone interested in compacting data, I've used the following reference: "The Design & Implementation of a Microproessor based data compression system" --- by Demetrios A. Prountzos. UMI Dissertation service 1986. - This includes "C" language listings on not only LZW, but also a rationalised Huffman algorithm. ----------------- Assisting 8-bitter owners is good for the soul. C8923075@cc.nu.oz -----------------
TRL3@psuvm.psu.edu (Tim Larson) (03/03/90)
For those implementing the LZW algorithm: I quote from a letter in Dr. Dobbs Journal, March 1990, page 8. The author is Robert S. Bramson of Unisys, the owner of U.S. Patent 4,558,302 entitled "High Speed Data Compression and Decompression Apparatus and Method." (That is, Unisys is the owner.) "As a concession to the modem industry, Unisys has agreed to license the patent to modem manufacturers for use in modems conforming to the V42.bis data compression standard promulgated by CCITT, for a one-time fee of $20,000. This $20,000 license, however, is not a general license under all applications of our patent but is limited to the specific appication discussed above." "...Unisys is actively looking into the possibility that a large number of software developers may be infringing one or more of our data compression patents." "Unisys is happy to accept inquiries from persons interested in acquiring a license to U.S. Patent 4,558,302. ...contact Mr. Edmund Chung of [Unisys'] licensing office, at 313-972-7114." This is pretty scary stuff. Many PD and shareware data compression schemes (including the GIF image standard) are based wholly or in part on LZW. LZW schemes are aften written about in books and taught in classes on data compression. Futhermore, LZW is simply one of many variations of a specific family of data compression algorithms. What kind of issues do this patent and Unisys' recent interest in it raise? That letter was enough for me to yank LZW algorithms out of our software until I get the scoop from Unisys. Cheers! -Tim Larson trl3@psuvm.bitnet