home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga Shareware Floppies / ma54.dms / ma54.adf / xpkHFMN_136 / HFMN.doc next >
Text File  |  1995-06-13  |  6KB  |  139 lines
  1.  
  2.                                       HFMN
  3.                    A fast packing & unpacking dynamic huffman
  4.                                   Version 1.36
  5.                       Copyright © 1993/94/95 Martin Hauner
  6.  
  7.  
  8.  
  9.                                License/Disclaimer
  10.                                ------------------
  11.  
  12. This library may be freely distributed with the XPK compression package, as long
  13. as  it  is  kept  in its original, complete, and unmodified form.  It may not be
  14. distributed  by  itself  or  in  a  commercial  package  of  any kind without my
  15. permission.
  16.  
  17. This  program is distributed in the hope that it will be useful, but WITHOUT ANY
  18. WARRANTY;  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  19. PARTICULAR PURPOSE.
  20.  
  21.  
  22.                                   Description
  23.                                   -----------
  24.  
  25. This  XPK  sub-library  basically  uses  the  same algorithm (dynamic huffman or
  26. classic huffman) as found in the xpkHUFF.library.  For more detailed information
  27. about  the huffman algorithm, take a look into HUFF.doc from M.Zimmermann -- and
  28. skip  the  part  that  huffman  compression  & decompression is pretty slow!  In
  29. difference to HUFF, HFMN is FAST on compression and decompression and produces a
  30. slightly  better  output.   Although  the  basic  algorithm  is  the same, it is
  31. entirely different implemented, therefore HFMN will not depack HUFF and HUFF not
  32. HFMN !
  33.  
  34.  
  35.      HFMN needs for private buffers (no xpkmaster.library buffers) 
  36.  
  37.                ·  7.5 Kbyte packing memory
  38.                ·  5   KByte unpacking memory
  39.  
  40.  
  41. Following  is  a  table  briefly  listing  some comparative statistics for HFMN.
  42. These  were  generated  by xBench on the standard XPK benchmark system (A3000/25
  43. with  SCRAM, using the AmigaVision executeable as data) and on A4000/40 (Booting
  44. without  Startup-Sequence, with Setpatch).  Note that memory needs don't include
  45. xpkmaster.library's buffers.
  46.  
  47.  
  48.         Method    Packing   Unpacking   Packing   Unpacking   Compression
  49.                   Memory     Memory      Speed      Speed        Ratio
  50.        ---------  -------   ---------   -------   ---------   -----------
  51.        HFMN.000+    7.5 K      5 K      223 K/s    209 K/s        24.7
  52.        HFMN.020+    7.5 K      5 K      259 K/s    209 K/s        24.7 
  53.  
  54.                          and now the same with A4000/40
  55.  
  56.         Method    Packing   Unpacking   Packing   Unpacking   Compression
  57.                   Memory     Memory      Speed      Speed        Ratio
  58.        ---------  -------   ---------   -------   ---------   -----------
  59.        HFMN.000+    7.5 K      5 K      537 K/s    569 K/s        24.7
  60.        HFMN.020+    7.5 K      5 K      592 K/s    569 K/s        24.7
  61.  
  62.  
  63.  
  64. How does it work?
  65.  
  66.  ·  First,  i use heapsort to create the huffman tree, which is most responsible
  67.     for  packing speed.
  68.     (heapsort is the second-best sort algorithm and is based upon binary trees)
  69.  
  70.  ·  Second,  (for decompression) i generate an (almost) optimal unpack code from
  71.     the huffman tree.
  72.  
  73.  ·  Third, i save the huffman tree recursivly.  That's why i need max.  320 byte
  74.     to save a complete huffman tree.
  75.  
  76.  
  77.  
  78.                                   020+ Version
  79.                                   ------------
  80.  
  81. I  have  experimented  with  020+  code  and rewrote the most used routines.  My
  82. huffman-code-translation-routine  :)  is  reduced  from  50  to 16 instructions,
  83. and achieves a noticable speedup. (hmm, i like bitfield instructions.:-)
  84.  
  85. .next        move.b    (a0)+,d2        ;incoming characters ( $00-$ff )
  86.         move.l    (a2,d2.w*4),d3        ;huffman code
  87.         move.b    3(a3,d2.w*4),d4        ;huffman codesize
  88.         bfins    d3,(a1){d5:d4}        ;store huffman code
  89.         add.l    d4,d5            ;bitoffset + last codesize
  90.         dbra    d7,.next
  91.  
  92. For decompression, the 020+ code produces no improvements.  But there were still
  93. some small optimizations possible, so decompression speed is improved too.
  94.  
  95.  
  96.  
  97.  
  98.                                 Version History
  99.                                 ---------------
  100.  
  101.           V 1.16 - first public version.
  102.           V 1.18 - 2 ways of decompression.
  103.           V 1.19 - bugfix: uncompressable data returns now XPKERR_EXPANSION
  104.                    instead of XPKERR_SMALLOUTBUF.
  105.  V 1.20 - V 1.27 - some experimental versions with 020+ code.
  106.           V 1.28 - extra library with 020+ code for compression.
  107.                  - improved 000+ decompression code.
  108.  V 1.29 - V 1.33 - some experimental version for the 1.34 bugfix.
  109.  
  110.           V 1.34 - fixed a bug that i had added somewhere before 1.16.
  111.                    it should have caused problems only under bad circumstances,
  112.                    when the byte statistic was fibonacci like.
  113.                    (in fact, the decompression routine couldn't handle huffman
  114.                     codes longer than 16 bits, ups...)
  115.                    Thanks to Nicolas Pomarede for his superdetailed bugreport.
  116.                    (He analysed the code and told me exactly when and where it
  117.                     goes wrong :-) )
  118.  
  119.           V 1.35 - fixed a bug in the 020+ compression routine.
  120.                    (16 Bit overflow for number of bytes written to xsp_OutBuf
  121.                     wasn't handled correctly)
  122.                    Thanks to David Balazic for reporting this one.
  123.           V 1.36 - 1.35 bugfix wasn't 100% ok.
  124.  
  125.  
  126.                                 Contact Address
  127.                                 ---------------
  128.  
  129.     any comments ?
  130.     email:
  131.     drizzt@trashcan.mcnet.de
  132.  
  133.     snail-mail:
  134.     Martin Hauner
  135.     Max-Born-Straße 5
  136.     38116 Braunschweig
  137.     Germany
  138.  
  139.