home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD1.iso / Backup / DIAVOLOBACKUPV2.0.DMS / in.adf / XPK / XPKusr_2,4.lha / Docs / RDCN.doc < prev    next >
Encoding:
Text File  |  1993-09-23  |  8.5 KB  |  191 lines
  1.     
  2.                                 -----------
  3.                                  RDCN v3.1
  4.                                 -----------
  5.  
  6.          An implementation of Ross Data Compression for the Amiga
  7.  
  8.                                  featuring
  9.  
  10.                     The fastest overall xpk-library !!!
  11.  
  12.  
  13. LEGAL STUFF
  14. ~~~~~~~~~~~
  15. This library (xpkRDCN.library) may be freely distributed, as long as:
  16.  
  17. - No profit is made with it
  18. - All files are unchanged
  19. - All files are copied together
  20.  
  21. If RDCN is put in the xpkdev-/xpkusr-archives, source and binary may be
  22. splitted. Please foreward this library to the xpk authors, I'd like to
  23. see it in the official distribution :)
  24.  
  25. The author takes NO RESPONSABILITY for any damage or data loss caused by
  26. this library. The actual algorithm is 100% OK but bugs may have sneaked
  27. into the code. RDCN has been tested on more than 100Mb of data and no
  28. bugs were found; HOWEVER:
  29.  
  30. Crunching data is always dangerous, it takes just _one_ single bit that
  31. is faulty to make a large part, or even the whole file, useless!
  32.  
  33. The algorithm (upto version 3.0) is (c) Ed Ross, see bottom of file.
  34.  
  35. In release 3.1, I removed the restriction on overlaying source/dest with
  36. patterns, as I can't see any reason why this should be an error. It still
  37. works fine with any hardware, is faster, crunches better and is compatible
  38. to old RDCN-libraries.
  39.  
  40.  
  41. HOW DOES IT WORK?
  42. ~~~~~~~~~~~~~~~~~
  43. RDCN works with 64K (approx.) inbuffers. It also allocates a hash-table of
  44. 4096 entries (that's 16K). Before each 'sequence' RDCN stores a control-
  45. word, in order to distinguish compressed bytes from uncompressed ones. A bit
  46. which is zero indicates that the next byte is uncompressed. Just to be
  47. compatible with the original RDC, RDCN uses bit 15 as byte1-indicator, bit
  48. 14 as byte2 indicator etc. etc. Now, how do the data get compressed?
  49.  
  50. o First RDCN checks if the next inbyte equals to the current. If so, get next
  51.   byte, see if that equals to the next etc. etc. RDCN also makes sure that we
  52.   don't advance >4113 bytes.
  53. o If at least 3 bytes were identical, we can use RLE (Run Length Encoding)
  54.   o Were there <19 characters repeated?
  55.     o Yes! This is a short RLE. Since there were at least 3 repeated bytes
  56.       we subtract 3 from the number of repeated bytes. Gee! Max number of
  57.       repeated bytes is now 15, 4 bits. The other four bits (in this case
  58.       zero) tells RDCN which compression method that was used. Next we store
  59.       first the crunched byte (4 bit code, 4 bit 'count') and next the byte
  60.       to be repeated.
  61.       Jump to top.
  62.   o No! We need to use more than one byte for compression code and 'count'.
  63.       Subtract 19 from count. Since we made sure that number of repeated chars
  64.       was less than 4114 we now only need 12 bits for count. Set the 4 bit
  65.       compression-code to 1, store that 4 bits + 4 bits of count. Store 8
  66.       bit count and the byte to repeat.
  67.       Jump to top.
  68. o We found no repeating characters. Use the sliding dictionary instead.
  69.   Calculate a hash between 0 and 4095. Look in dictionary at offset 'hash'.
  70.   (The hash is calculated by using the current byte and the two following)
  71.   Get possible pointer and store the new one (the current position) 
  72. o See if the old pointer in hash_table[hash] wasn't zero!
  73.   o No! Sorry, nothing do to. Just copy the current byte to outbuffer.
  74.     Jump to top.
  75.   o Yes! First make sure the three byte sequence isn't located > 4098 bytes
  76.     away. If it is, we can't compress! ('gap' only uses 12 bits)
  77.     Now, start comparing our current bytes in source to the 'old' bytes which
  78.     hash_table[hash] pointed to. If >271 bytes equal we stop since we can't
  79.     handle longer patterns than 271 bytes (max 8 bits in count).
  80.     o Next, if less than 3 bytes didn't match, we can't compress. Copy current
  81.       byte to outbuffer and jump to top.
  82.     o Did at least three bytes match, but no more than 15?
  83.       o Yes! A short pattern. Combine count (4 bits) with 4 bits from 'gap'
  84.         (gap is the offset from last pattern to current pattern). Next store
  85.         8 more bits from gap (we have subtracted three from gap since at
  86.         least three bits matched and gap can thus be as large as 4098 bytes).
  87.       o No! Encode this as a long pattern. This pattern is at least 16 bytes
  88.         long, so subtract 16 from count. Since we made sure the pattern was no
  89.         longer than 271 bytes we only need 8 bits for count. Gap still need
  90.         12 bits, so combine 4 of them with the four control bits (which are
  91.         set to 2!), store the next 8 gap-bits and last the 8 bit count.
  92. o We're done! Proceed with a jump to top to search for RLE on next source
  93.   byte.
  94.  
  95. To sum up :
  96.  
  97. Type          | 4 Bits |     4 Bits |      8 Bits |    8 Bits |
  98. --------------+--------+------------+-------------+-----------+
  99. Short RLE     |      0 |      Count |   Character |  Not used |
  100. --------------+--------+------------+-------------+-----------+
  101. Long  RLE     |      1 |  Low count |  High count | Character |
  102. --------------+--------+------------+-------------+-----------+
  103. Long  Pattern |      2 | Low offset | High offset |     Count |
  104. --------------+--------+------------+-------------+-----------+
  105. Short Pattern |   3-15 | Low offset | High offset |  Not used |
  106.  
  107. Have a look at the source. If you find a smart way to speed it up PLEASE
  108. do it and release both binary and source code into the public domain!!
  109.  
  110.  
  111. USAGE
  112. ~~~~~
  113. Most of you probably skipped to this section directly :)
  114.  
  115. Just copy xpkRDCN.library to LIBS:compressors/ where all xpk-sublibraries
  116. are found. If you already had an older version of xpkRDCN, type "avail flush"
  117. in a Shell, that's it. You may use your old data compressed with previous
  118. versions of RDCN, this release should be 100% compatible.
  119.  
  120. The main intention with this packer is 'to go where no packer ever has gone
  121. before' :) Since RDCN is optimized on both packing and depacking it is
  122. intended for devices/dirs you _normally_ wouldn't pack. A C-programming device
  123. would be a good example. It takes a lot of space, data is fairly simple and
  124. you want a decent access speed. However, until a real version of XFH is
  125. released (one which doesn't write file, wait until it is closed and than packs
  126. it, but rather pack chunks) you may want to wait with the most speed demanding
  127. devices. It also very useful for floppy-users, as it speeds up disk-operations
  128. by roughly two even on "slow" systems!
  129.  
  130.  
  131. BUGS
  132. ~~~~
  133. None known :)
  134.  
  135.  
  136. CREDITS
  137. ~~~~~~~
  138. Ed Ross of Application Software for the algorithm
  139. John Harris for the first implementation and versions upto 2.1
  140. Niklas Sjoberg for version 2.2
  141. Jürgen (SYSOP@SPLIT) & Charly (SYSOP@CARRIER) for Betatesting
  142.  
  143.  
  144. AUTHOR
  145. ~~~~~~
  146. If you find bugs or ways of speeding it up, please write a note. If you
  147. think it's worth some bucks, please send only cash or register me for your
  148. shareware-tools.
  149.  
  150. Snailmail:           Phone:
  151.   Daniel Frey          +49-(0)2266-2963
  152.   Tulpenweg 13
  153.   51789 Lindlar      EMail:
  154.   Germany              D.FREY@SPLIT.ZER[.sub.org]
  155.  
  156.  
  157. FUTURE
  158. ~~~~~~
  159. Probably a 68020+ version, but I don't have a book about 680x0-code with
  160. cycles for all those access-modes. A somewhat more optimized version for
  161. 68020+ is available, contact me for more information if you like.
  162.  
  163.  
  164. HISTORY
  165. ~~~~~~~
  166. V1.0 (Niklas Sjoberg) First working version in C, not public, compiled with
  167.      SAS/C 6.0
  168. V1.1 Decompression written in assembler, not public
  169. V1.2 Compression written in assembler, not public
  170. V1.3 Small optimizations, first public release, compiled with SAS/C 6.1
  171. V1.4 Fixed 68000-bug (word fetch at odd address, sorry..), never released
  172.      due to the fact that I waited for Stefan Boberg's promised optimizations.
  173. V2.0 Implemented John Harris's new code.
  174. V2.1 Fixed a couple of serious bugs, public release, compiled with SAS/C 6.2
  175. V2.2 (John Harris) Fixed above bugs in ways that didn't slow down the 
  176.      routine.  Also fixed more 68000 problems and errors in code translation.
  177.      Updated the version strings which had still shown '1.0'.
  178. V3.0 (Daniel Frey) Translated C-Parts to Assembler, crunching sped up about
  179.      20%, decrunching about 3-4%. Released to the public on 4. August 1993.
  180.      As I rewrote about 80% of the source, most comments have gone.
  181. V3.1 I removed some stuff not used (Libraries) and made a very interesting
  182.      optimisation to the crunching routine: It is now shorter, faster, packs
  183.      better (just about 0.5%) and is still compatible (old versions of the
  184.      library may decrunch the new format!). Released on 14. August 1993.
  185.  
  186.  
  187. FINAL NOTICE
  188. ~~~~~~~~~~~~
  189. The source wasn't supplied for quiche-eaters, it's a bit tricky and has only
  190. some very "global" comments. Indeed it is dedicated to Wirth :)
  191.