----------- RDCN v3.0 ----------- An implementation of Ross Data Compression for the Amiga featuring The fastest overall xpk-library !!! LEGAL STUFF ~~~~~~~~~~~ This library (xpkRDCN.library) may be freely distributed, as long as: - No profit is made with it - All parts are copied together (Library, Doc & Source) If RDCN is put in the xpkdev-/xpkusr-archives, source and binary may be splitted. Please foreward this library to the xpk authors, I'd like to see it in the official distribution :) The author takes NO RESPONSABILITY for any damage or data loss caused by this library. The actual algorithm is 100% OK but bugs may have sneaked into the code. RDCN has been tested on more than 100Mb of data and no bugs were found; HOWEVER: Crunching data is always dangerous, it takes just _one_ single bit that is faulty to make a large part, or even the whole file, useless! The actual algorithm (in this version) is (c) Ed Ross, see bottom of file. WHAT IS RDCN? ~~~~~~~~~~~~~ RDCN is based on a very simple, but yet effective AND fast algorithm published in `The C Users Journal` Oct 92. It was transferred to Amiga assembly code by Niklas Sjoberg, the actual version was optimized by myself (Daniel Frey). The main feature is speed... here's a brief benchmark on my system (A2000C, 4MB FAST, 68010@7.14MHz) Test file was the term3.3-Executable Original: 449848 bytes Packed: 293736 bytes (ratio: 35%) Speed (cps): | Pack | Unpack -----+-------+------- v2.2 | 27289 | 80084 v3.0 | 33092 | 82375 HOW DOES IT WORK? ~~~~~~~~~~~~~~~~~ RDCN works with 65K (approx.) inbuffers. It also allocates a hash-table of 4096 entries (that's 16 Kb). Before each 'sequence' RDCN stores a control- word, in order to distinguish compressed bytes from uncompressed ones. A bit which is zero indicates that the next byte is uncompressed. Just to be compatible with the original RDC, RDCN uses bit 15 as byte1-indicator, bit 14 as byte2 indicator etc. etc. Now, how do the data get compressed? o First RDCN checks if the next inbyte equals to the current. If so, get next byte, see if that equals to the next etc. etc. RDCN also makes sure that we don't advance >4113 bytes. o If at least 3 bytes were identical, we can use RLE (Run Length Encoding) o Were there <19 characters repeated? o Yes! This is a short RLE. Since there were at least 3 repeated bytes we subtract 3 from the number of repeated bytes. Gee! Max number of repeated bytes is now 15, 4 bits. The other four bits (in this case zero) tells RDCN which compression method that was used. Next we store first the crunched byte (4 bit code, 4 bit 'count') and next the byte to be repeated. Jump to top. o No! We need to use more than one byte for compression code and 'count'. Subtract 19 from count. Since we made sure that number of repeated chars was less than 4114 we now only need 12 bits for count. Set the 4 bit compression-code to 1, store that 4 bits + 4 bits of count. Store 8 bit count and the byte to repeat. Jump to top. o We found no repeating characters. Use the sliding dictionary instead. Calculate a hash between 0 and 4095. Look in dictionary at offset 'hash'. (The hash is calculated by using the current byte and the two following) Get possible pointer and store the new one (the current position) o See if the old pointer in hash_table[hash] wasn't zero! o No! Sorry, nothing do to. Just copy the current byte to outbuffer. Jump to top. o Yes! First make sure the three byte sequence isn't located > 4098 bytes away. If it is, we can't compress! ('gap' only uses 12 bits) Now, start comparing our current bytes in source to the 'old' bytes which hash_table[hash] pointed to. If >271 bytes equal we stop since we can't handle longer patterns than 271 bytes (max 8 bits in count). o Next, if less than 3 bytes didn't match, we can't compress. Copy current byte to outbuffer and jump to top. o Did at least three bytes match, but no more than 15? o Yes! A short pattern. Combine count (4 bits) with 4 bits from 'gap' (gap is the offset from last pattern to current pattern). Next store 8 more bits from gap (we have subtracted three from gap since at least three bits matched and gap can thus be as large as 4098 bytes). o No! Encode this as a long pattern. This pattern is at least 16 bytes long, so subtract 16 from count. Since we made sure the pattern was no longer than 271 bytes we only need 8 bits for count. Gap still need 12 bits, so combine 4 of them with the four control bits (which are set to 2!), store the next 8 gap-bits and last the 8 bit count. o We're done! Proceed with a jump to top to search for RLE on next source byte. To sum up : Type | 4 Bits | 4 Bits | 8 Bits | 8 Bits | --------------+--------+------------+-------------+-----------+ Short RLE | 0 | Count | Character | Not used | --------------+--------+------------+-------------+-----------+ Long RLE | 1 | Low count | High count | Character | --------------+--------+------------+-------------+-----------+ Long Pattern | 2 | Low offset | High offset | Count | --------------+--------+------------+-------------+-----------+ Short Pattern | 3-15 | Low offset | High offset | Not used | Have a look at the source. If you find a smart way to speed it up PLEASE do it and release both binary and source code into the public domain!! USAGE ~~~~~ Most of you probably skipped to this section directly :) Just copy xpkRDCN.library to LIBS:compressors/ where all xpk-sublibraries are found. If you already had an older version of xpkRDCN, type "avail flush" in a Shell, that's it. You may use your old data compressed with previous versions of RDCN, this release should be 100% compatible. The main intention with this packer is 'to go where no packer ever has gone before' :) Since RDCN is optimized on both packing and depacking it is intended for devices/dirs you _normally_ wouldn't pack. A C-programming device would be a good example. It takes a lot of space, data is fairly simple and you want a decent access speed. However, until a real version of XFH is released (one which doesn't write file, wait until it is closed and than packs it, but rather pack chunks) you may want to wait with the most speed demanding devices. It also very useful for floppy-users, as it speeds up disk-operations by roughly two even on "slow" systems! BUGS ~~~~ None known :) CREDITS ~~~~~~~ Ed Ross of Application Software for the actual algorithm John Harris for the first implementation and versions upto 2.1 Niklas Sjoberg for version 2.2 Jürgen (SYSOP@SPLIT) & Charly (SYSOP@CARRIER) for Betatesting AUTHOR ~~~~~~ If you find bugs or ways of speeding it up, please write a note. If you think it's worth some bucks, please send only cash or register me for your shareware-tools. Snailmail: Phone: Daniel Frey +49-(0)2266-2963 Tulpenweg 13 51789 Lindlar EMail: Germany D.FREY@SPLIT.ZER[.sub.org] FUTURE ~~~~~~ Probably a 68020+ version, but I don't have a book about 680x0-code with cycles for all those access-modes. A somewhat more optimized version for 68020 will follow anyway, but it will only be optimized in what I _guess_ should speed it up (as I don't have a turbo-board). HISTORY ~~~~~~~ V1.0 (Niklas Sjoberg) First working version in C, not public, compiled with SAS/C 6.0 V1.1 Decompression written in assembler, not public V1.2 Compression written in assembler, not public V1.3 Small optimizations, first public release, compiled with SAS/C 6.1 V1.4 Fixed 68000-bug (word fetch at odd address, sorry..), never released due to the fact that I waited for Stefan Boberg's promised optimizations. V2.0 Implemented John Harris's new code. V2.1 Fixed a couple of serious bugs, public release, compiled with SAS/C 6.2 V2.2 (John Harris) Fixed above bugs in ways that didn't slow down the routine. Also fixed more 68000 problems and errors in code translation. Updated the version strings which had still shown '1.0'. V3.0 (Daniel Frey) Translated C-Parts to Assembler, crunching sped up about 20%, decrunching about 3-4%. Released to the public on 4. August 1993. As I rewrote about 80% of the source, most comments have gone. FINAL NOTICE ~~~~~~~~~~~~ The source wasn't supplied for quiche-eaters, it's a bit tricky and has only some very "global" comments. Indeed it is dedicated to Wirth :)