RDCN An implementation of Ross Data Compression for the Amiga Featuring Fast compression and decompression The fastest overall xpk-library Some copyright 1992, Niklas Sjöberg, but totally PD LEGAL STUFF ~~~~~~~~~~~ This library (xpkRDCN.library) may be freely disributed with any kind of software, as long as no profit is made of the other software. Also, ALL files, source, docs and binary, must be in the same package. If RDCN is put in the xpkdev-/xpkusr-archives, source and binary may be splitted. The author takes NO RESPONSABILITY for any damage of lost data caused by this library. The actual algorithm is 100% OK but bugs may have sneaked into the code. RDCN have been tested on more than 100Mb of data and have been compared to the original files. No differences where found. However crunched data is always more dangerous to use than uncrunched data. It just takes 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. WHY? and 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 me, since I lacked a both-way fast xpk-packer. The assembly code has been very much optimized and I think that higher CPS-rates won't be possible if the RDC method is used. For all you that are interested in compression-stuff: 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 | Byte 1 | Byte 2 | Byte 3 | -------------------------------------------------------------- |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 cource code into the public domain!! Improving compression a bit wouldn't be that hard. Even though RDCN compress fairly well, we really could use BLZW instead (even though it unpacks slow!). Compression rate isn't the most important thing here, we want speed! :) USAGE: ~~~~~~ Most of you probably skipped to this section directly :) RDCN packs fairly well, about 32 % on AmigaVision executable, about 45-50% on textfiles. On really simple textfiles, like a 'list dh0: ALL' RDCN may manage to pack upto a CF of 70-80%. On _really_ redundant data, like a a file full of zeroes RDCN should packs as good as any RLE-packer. 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 copy file, wait until it is closed and the packs it, but rather pack chunks) you may want to wait with the most speed demanding devices. Since I don't have 'xBench' I've timed BLZW and NUKE a couple of times and compared them to RDCN (timed using the built-in function in Csh). Method Packing Unpacking Packing Unpacking Compression Memory Memory Speed Speed Ratio ------ ------- --------- ------- --------- ----------- RDCN 16K 0K 150 K/s 600 K/s 33.0% ; binary RDCN 16K 0K 150 K/s 600 K/s 45.0% ; text When packing all the programs/files in the SAS/C 6.1 package RDCN reduced size by 42%. A more interesting benchmark: FILE: Fish contents 1-650 (some disk missing :-() + AmigaVision executable FILESIZE: 1725 Kb (ie. around 1766400 bytes) LOCATION: RAM: MACHINE: A3000/25 w SCRAM METHOD PACKTIME DEPACKTIME RATIO NUKE 44.36 secs 4.92 secs 54 % BLZW.60 13.34 secs 6.70 secs 46 % RDCN 11.24 secs 4.34 secs 41 % Since NUKE depacks 630 Kb/sec this would indicate that RDCN manages speeds above 700 Kb/sec. (if NUKE packspeed was compared to RDCN 140 Kb/sec). If we compare to BLZW, RDCN unpacks 560 Kb/sec. Packing compared to BLZW is 165 Kb/sec. Well, as I said, I don't have access to xBench, but several other tests shows that RDCN unpacks more than 600 Kb/sec and generally packs more than 150 Kb/sec. CREDITS ~~~~~~~ Ed Ross of Application Software for the actual algorithm. Simple, clear and fast! Thanks Ed! CONTACT ~~~~~~~ Suggestions to "Niklas Sjoberg" 2:203/415.3@Fidonet