home *** CD-ROM | disk | FTP | other *** search
/ World of A1200 / World_Of_A1200.iso / programs / compress / misc / xpk / docs / huff.doc < prev    next >
Text File  |  1995-02-27  |  10KB  |  222 lines
  1.  
  2.  
  3.                                     HUFF
  4.                    A dynamic huffman cruncher/decruncher
  5.                                 Version 0.62
  6.                        Copyright 1992 by M.Zimmermann
  7.  
  8.  
  9.  
  10.                              License/Disclaimer
  11.                              ------------------
  12.  
  13.    This  library may be freely distributed with the XPK compression package,
  14. as  long  as  it is kept in its original, complete, and unmodified form.  It
  15. may  not  be  distributed  by  itself or in a commercial package of any kind
  16. without my permission.
  17.  
  18.    This  program  is  distributed  in  the  hope that it will be useful, but
  19. WITHOUT  ANY  WARRANTY; without even the implied warranty of MERCHANTABILITY
  20. or FITNESS FOR A PARTICULAR PURPOSE.
  21.  
  22.  
  23.  
  24.                                About Huffmans
  25.                                --------------
  26.  
  27. The  idea  of  a  huffman  crunch is as follows:  often used bytes (ie 8 bit
  28. codes) get a shorter code than 8 bits, fi 5 bits.  So everytime one of these
  29. bytes  occurs in the source file I save (in this example) 3 bits in the dest
  30. file.  To find out the optimum codes for each byte there is a simple method:
  31. A  tree  is  to  be  constructed so that the path from the root to each leaf
  32. reflects  the  optimum (ie huffman) code.  Unfortunately most computers (the
  33. Amiga,  too)  are  byte-oriented,  which  means a rather complex handling of
  34. codes  that  are  not  a  multiple  of  8 bits.  This results in pretty slow
  35. compression  &  decompression.   So  this  means  that  the  xpkHUFF.library
  36. probably  won't be used for normal circumstances, but, as Dominik stated, it
  37. may serve well as an example library.
  38.  
  39. There are three different huffman crunch algorithms known:
  40.  
  41. · static   compression/decompression
  42. · dynamic  compression/decompression
  43. · adaptive compression/decompression
  44.  
  45.  
  46. What are the differences?
  47.  
  48. The  static  huffman  uses a fix table to represent each byte of the source.
  49. This,  of  course,  makes  sense  only,  if  the structure of the data to be
  50. crunched  is known.  In this case (for instance crunching an english text) a
  51. fix  table of codes is embedded in the code.  Crunching other data than what
  52. the  table  was  generated  for will probably result in worse compression or
  53. even expansion.
  54.  
  55.    This  is  what  a  dynamic  huffman  is  avoiding:   it  first  creates a
  56. statistics  table  reflecting  the  frequency  every  byte  occurs  with and
  57. generates  a special tree/table for this case, so the dynamic huffman does a
  58. good compression for this special data.
  59.  
  60.    But there is something that can be improved, anyway:  imagine, there is a
  61. data  block which contains many 'a's in it's first part and many 'z's in the
  62. last  part....   The  dynamic huffman would represent the 'a's and 'z's with
  63. short  codes,  of  course.   But  it  probably  would  be even better if the
  64. crunch/decrunch  tree  would  reflect  the  *current*  data beeing processed
  65. instead of the whole block, thus in resulting shorter codes for 'a' and 'z',
  66. depending  of  the  position  in  the  data block.  This is what an adaptive
  67. huffman  deals with:  it creates the tree while crunching, without doing any
  68. statistics  or  tree creation before crunching.  It permanently updates it's
  69. internal huffman tree.  Therefore it doesn't have to include the information
  70. about the decrunch tree in the crunched data.
  71.  
  72.  
  73.  
  74.                        Final words about huffmans ...
  75.                        ------------------------------
  76.  
  77.    A  stand-alone huffman will never achieve crunch results as fine as those
  78. reached with most other crunchers, for these will not only regard the number
  79. of  occurances  for  each  byte (as huffman does), but sequels of byte, too.
  80. This  means:   If  you  create  all permutations of a datablock, the huffman
  81. crunched  will  always  have  the  same  length.   Others won't, as they are
  82. depending on the order of the crunched data, too.
  83.  
  84.  
  85.  
  86.                                 Description
  87.                                 -----------
  88.  
  89.    The   library  'xpkHUFF.library'  implements  a  dynamic  huffman  crunch
  90. algorithm,  even  though the adaptive might result in slightly better crunch
  91. results.  However, this is more complex to implement and I'm using a maximum
  92. buffer  size  of  64K,  so this is a little bit like an adaptive huffman for
  93. large files.
  94.  
  95.    If I should have lots of spare time I will probably implement an adaptive
  96. huffman crunch algorithm.  This new library will be called xpkHUFF, too, and
  97. new  xpkHUFF.libraries  will  always  handle  output  generated  by  earlier
  98. versions.
  99.  
  100.    The  xpkHUFF.library  supports  a totally unsafe (but a little bit better
  101. than  simple  eor  :-)  encryption.  Please note that crunch/decrunch speeds
  102. decrease when encryption is used.
  103.  
  104.  
  105.  
  106.                                The source ...
  107.                                --------------
  108.  
  109.   The  source  is  provided,  so you might have a look at different decrunch
  110. codes.   Please  note:  The only code I tested intensively is the byte/cache
  111. decrunch  code,  which  was  used  to  create  the  library included in this
  112. package.   For  it's the fasted code, you probably won't want to use another
  113. one.  However, this might help you to understand what huffmans are about.
  114.  
  115.    If you have never written a huffman, have a look at it, a huffman code is
  116. a  pretty good idea.  If you *have* written a huffman code and it's *faster*
  117. than mine, please let me know, I will then update xpkHUFF.library.
  118.  
  119.  
  120.  
  121.                                Implementation
  122.                                --------------
  123.  
  124.    If  you  should  see an errormessage saying output buffer too small while
  125. crunching  *and*  encrypting,  this  means you tried to crunch and encrypt a
  126. file  that  would  crunched  and encrypted be larger than the original file.
  127. This should occur only with very small files (for I have a minimum file size
  128. due  to  tables) or with files that have been crunched already and therefore
  129. would expand during crunch.
  130.  
  131.    A technical note:  this could also happen, if the last chunk of a file to
  132. be crunched/encrypted would be dimensioned too small by xpkmaster.library.
  133.  
  134.    However,  in this case you cannot encrypt the file.  I know this could be
  135. annoying  and  will  think  about a solution for this problem, but remember:
  136. this  encryption  would  not  be  safe,  better if you used FEAL or IDEA for
  137. secure encryption.
  138.  
  139.  
  140.  
  141.                                  Statistics
  142.                                  ----------
  143.  
  144.    Following is a table briefly listing some comparative statistics for HUFF
  145. without  encryption.   These  were  generated  by xBench on the standard XPK
  146. benchmark  system  (A3000/25 with SCRAM, using the AmigaVision executable as
  147. data).  Note that memory needs don't include xpkmaster.library's buffers.
  148.  
  149. Method   Packing   Unpacking   Packing   Unpacking   Compression
  150.          Memory     Memory      Speed      Speed        Ratio
  151. ------   -------   ---------   -------   ---------   -----------
  152.  HUFF      30K         71K      88 K/s     138 K/s       24.1%  
  153.  
  154.  
  155. Where  unpack  speed  varies depending on decrunch code (refer to source for
  156. that).
  157.  
  158.  
  159.                                Last words ...
  160.                                --------------
  161.  
  162.    I  tried  hard  to  debug  this library with range checking while writing
  163. bytes  on  crunching,  and  so  on, but as in every code larger than, say 10
  164. lines  :-),  there will be bugs.  I don't know any bugs in this version, but
  165. if  you  should meet one, please let me know via email (refer to end of this
  166. document  for  my  email adr).  As usually, reproducable bugs are preferred.
  167. Please  add  your  configuration,  programs running (best if you try without
  168. startup-sequence!),  and,  most  important of all, add the file you tried to
  169. crunch!  Thank you.
  170.  
  171.  
  172.  
  173.                               Version History
  174.                               ---------------
  175.  
  176. ;    V 0.1  - 12-Jul-1992 :    first version
  177. ;    V x.yy - 18-Jul-1992 :    first OK version
  178. ;    V x.yy - 19-Jul-1992 :    sped up decrunching
  179. ;    V x.yy - 21-Jul-1992 :    bug fixed in word/long decrunching: min pack
  180. ;                               chunk size now 3/5
  181. ;    V x.yy - 21-Jul-1992 :    replaced many subq/bxx with dbf (ie sped up
  182. ;                               crunching a little bit), bug fixed: there was
  183. ;                               a dbf counter wrong (one of my favorite 0/1
  184. ;                               problem bugs)
  185. ;    V 0.50 - 29-Jul-1992 :    added 68030+ cache optimized decrunch code
  186. ;    V 0.51 - 01-Aug-1992 :    byte decrunch improved, first code added,
  187. ;                indicator byte for crunchmethod used added,
  188. ;                68030+ chache optimized code does not make
  189. ;                sense any more, since byte decrunch fits to
  190. ;                cache completely, now
  191. ;    V 0.52 - 01-Aug-1992 :    unsafe encryption supported
  192. ;    V 0.53 - 03-Aug-1992 :    slight improvements made to crunch code
  193. ;                (+ 6K/s)
  194. ;    V 0.54 - 03-Aug-1992 :    inconsistence in expansion handling fixed
  195. ;    V 0.55 - 03-Aug-1992 :    bug fixed: expansion handling now considers
  196. ;                table creation, too
  197. ;    V 0.56 - 03-Aug-1992 :    bug fixed: HUFF now can crunch files
  198. ;                consisting of always the same byte (shame
  199. ;                on me, termination criterium was wrong)
  200. ;    V 0.57 - 03-Aug-1992 :    Tree creation code partially rewritten
  201. ;    V 0.58 - 05-Aug-1992 :    bug fixed: wrong termination criterium for
  202. ;                expansion check (my favorite 0/1 problem)
  203. ;    V 0.59 - 06-Aug-1992 :    now decrypting in a special buffer, not using
  204. ;                InBuf (this is read only, I was told) any more
  205. ;    V 0.60 - 07-Aug-1992 :    added extra memory required during
  206. ;                packing/unpacking
  207. ;    V 0.61 - 08-Aug-1992 :    expansion check changed, renamed from
  208. ;                xpkDHUF.library to xpkHUFF.library thus
  209. ;                corresponding to the possibility of handling
  210. ;                adaptive huffman codes later without having
  211. ;                an inconsistence in the name
  212. ;    V 0.62 - 10-Aug-1992 :    Flag XPKIF_MODES removed (I don't have modes
  213. ;                yet (but I have a mapping code :-=))
  214.  
  215.  
  216.  
  217.                               Contact Address
  218.                               ---------------
  219.  
  220.    zimmerma@helios.ibr.cs.tu-bs.de (M. Zimmermann)
  221.  
  222.