home *** CD-ROM | disk | FTP | other *** search
-
- 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
-
-
- History at bottom of file
-
-
- 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 180 K/s 800 K/s 33.0% ; binary
- RDCN 16K 0K 180 K/s 800 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 % (old 1.3 version)
- RDCN 09.12 secs 3.48 secs 41 % (new 2.1 version)
-
- Since NUKE depacks 630 Kb/sec this would indicate that RDCN manages speeds
- above 890 Kb/sec. (if NUKE packspeed was compared to RDCN 175 Kb/sec). If
- we compare to BLZW, RDCN unpacks 700 Kb/sec. Packing compared to BLZW is
- 200 Kb/sec.
-
- Well, as I said, I don't have access to xBench, but several other tests shows
- that RDCN unpacks more than 800 Kb/sec and generally packs more than 190
- Kb/sec.
-
-
- BUGS
- ~~~~
- SAS/C LibVersion and LibRevision are bugged or my c:version stopped working!
- version libs:compressors/xpkRDCN.library -> "version 1.0"
- version dh0:libs/compressors/xpkRDCN.library -> "2.1"
-
- Any suggestions? (have I missed a keyword in SAS/C or something?)
-
- CREDITS
- ~~~~~~~
- Ed Ross of Application Software for the actual algorithm. Simple, clear and
- fast! Thanks Ed!
-
- John Harris (jharris@cup.portal.com) did all the optimizing between V1.3 and
- V2.1.
-
-
- CONTACT
- ~~~~~~~
- Suggestions to "Niklas Sjoberg" 2:203/415.3@Fidonet
-
- If you find a gate between Internet and Fidonet (many did :):
- Niklas.Sjoberg@p3.f415.n203.z2.fidonet.org
-
-
- HISTORY CHANGES AND UPDATES
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
- V1.0 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 (By 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'.
-