home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PIBLZW.ZIP / PIBCOMPR.PAS next >
Encoding:
Pascal/Delphi Source File  |  1988-04-30  |  9.7 KB  |  183 lines
  1. (*$R-,V-,S-,I-*)
  2. PROGRAM PibCompr;
  3.  
  4. (*--------------------------------------------------------------------------*)
  5. (*                                                                          *)
  6. (*       Program:  PibCompr                                                 *)
  7. (*                                                                          *)
  8. (*       Purpose:  Compresses a file using the Lempel-Ziv-Welch approach.   *)
  9. (*                                                                          *)
  10. (*       Author:   Philip R. Burns.   April 30, 1988.                       *)
  11. (*                                                                          *)
  12. (*       Use:      PIBCOMPR  inputfile outputfile                           *)
  13. (*                                                                          *)
  14. (*                    inputfile  --- the input file to be compressed        *)
  15. (*                    outputfile --- the output compressed file             *)
  16. (*                                                                          *)
  17. (*       Remarks:                                                           *)
  18. (*                                                                          *)
  19. (*          PibCompr implements the Lempel-Ziv file compression algorithm.  *)
  20. (*          (Files compressed by PibCommpr are uncompressed by PibDComp.)   *)
  21. (*          It operates by finding common substrings and replaces them      *)
  22. (*          with a fixed-length 12-bit code.  This is deterministic, and    *)
  23. (*          can be done with a single pass over the file.  Thus,            *)
  24. (*          the decompression procedure needs no input table, but           *)
  25. (*          can track the way the table was built.                          *)
  26. (*                                                                          *)
  27. (*       Algorithm:                                                         *)
  28. (*                                                                          *)
  29. (*                                                                          *)
  30. (*          This section is abstracted from Terry Welch's article           *)
  31. (*          referenced below.  The algorithm builds a string                *)
  32. (*          translation table that maps substrings in the input             *)
  33. (*          into fixed-length codes.  The compress algorithm may            *)
  34. (*          be described as follows:                                        *)
  35. (*                                                                          *)
  36. (*            1. Initialize table to contain single-character strings.      *)
  37. (*            2. Read the first character.  Set <w> (the prefix string)     *)
  38. (*               to that character.                                         *)
  39. (*            3. (step): Read next input character, C.                      *)
  40. (*            4. If at end of file, output code(<w>); exit.                 *)
  41. (*            5. If <w>C is in the string table:                            *)
  42. (*                  Set <w> to <w>C; goto step 3.                           *)
  43. (*            6. Else <w>C is not in the string table.                      *)
  44. (*                  Output code(<w>);                                       *)
  45. (*                  Put <w>C into the string table;                         *)
  46. (*                  Set <w> to C; Goto step 3.                              *)
  47. (*                                                                          *)
  48. (*          "At each execution of the basic step an acceptable input        *)
  49. (*          string <w> has been parsed off.  The next character C is        *)
  50. (*          read and the extended string <w>C is tested to see if it        *)
  51. (*          exists in the string table.  If it is there, then the           *)
  52. (*          extended string becomes the parsed string <w> and the           *)
  53. (*          step is repeated.  If <w>C is not in the string table,          *)
  54. (*          then it is entered, the code for the successfully               *)
  55. (*          parsed string <w> is put out as comprssed data, the             *)
  56. (*          character K becomes the beginning of the next string,           *)
  57. (*          and the step is repeated."                                      *)
  58. (*                                                                          *)
  59. (*       Reference:                                                         *)
  60. (*                                                                          *)
  61. (*          "A Technique for High Performance Data Compression",            *)
  62. (*          Terry A. Welch, IEEE Computer,                                  *)
  63. (*          vol. 17, no. 6 (June 1984), pp. 8-19.                           *)
  64. (*                                                                          *)
  65. (*       Note:  The hashing algorithm used here isn't very good, and        *)
  66. (*              should be replaced by a better one.                         *)
  67. (*                                                                          *)
  68. (*       Usage note:                                                        *)
  69. (*                                                                          *)
  70. (*          You may use this program in any way you see fit without         *)
  71. (*          restriction.  I'd appreciate a citation if you do use this      *)
  72. (*          code in a program you distribute.                               *)
  73. (*                                                                          *)
  74. (*--------------------------------------------------------------------------*)
  75.  
  76. (*$I PIBLZW.DEF *)
  77. (*$I PIBLZW.INC *)
  78.  
  79. (*--------------------------------------------------------------------------*)
  80. (*             Put_Code  ---  Write hash code to output file.               *)
  81. (*--------------------------------------------------------------------------*)
  82.  
  83. PROCEDURE Put_Code( Hash_Code : INTEGER );
  84.  
  85. BEGIN (* Put_Code *)
  86.                                    (* Output code word is empty.        *)
  87.                                    (* Put out 1st 8 bits of compression *)
  88.                                    (* code and save last 4 bit for next *)
  89.                                    (* time through.                     *)
  90.  
  91.    IF ( Output_Code = Empty ) THEN
  92.       BEGIN
  93.          Put_Char( ( Hash_Code SHR 4 ) AND $FF );
  94.          Output_Code := Hash_Code AND $0F;
  95.       END
  96.    ELSE
  97.                                    (* Output code word not empty.         *)
  98.                                    (* Put out last 4 bits of previous     *)
  99.                                    (* code appended to 1st 4 bits of this *)
  100.                                    (* code.  Then put out last 8 bits of  *)
  101.                                    (* this code.                          *)
  102.       BEGIN
  103.          Put_Char( ( ( Output_Code SHL 4 ) AND $FF0 ) +
  104.                    ( ( Hash_Code SHR 8 ) AND $00F ) ) ;
  105.          Put_Char( Hash_Code AND $FF );
  106.          Output_Code := Empty;
  107.       END;
  108.  
  109. END   (* Put_Code *);
  110.  
  111. (*--------------------------------------------------------------------------*)
  112. (*             Do_Compression --- Perform Lempel-Ziv-Welch compression      *)
  113. (*--------------------------------------------------------------------------*)
  114.  
  115. PROCEDURE Do_Compression;
  116.  
  117. VAR
  118.    C  : INTEGER             (* Current input character = C *);
  119.    WC : INTEGER             (* Hash code value for <w>C    *);
  120.    W  : INTEGER             (* Hash code value for <w>     *);
  121.  
  122. BEGIN (* Do_Compression *)
  123.                                    (* Read first character ==> Step 2 *)
  124.    Get_Char( C );
  125.                                    (* Initial hash code -- first character *)
  126.                                    (* has no previous string (<w> is null) *)
  127.  
  128.    W := Lookup_String( No_Prev , C );
  129.  
  130.                                    (* Get next character ==> Step 3    *)
  131.    Get_Char( C );
  132.                                    (* Loop over input characters until *)
  133.                                    (* end of file reached ==> Step 4.  *)
  134.    WHILE( C <> EOF_Char ) DO
  135.       BEGIN
  136.                                    (* See if <w>C is in table. *)
  137.  
  138.          WC := Lookup_String( W , C );
  139.  
  140.                                    (* If <w>C is not in the table, *)
  141.                                    (* enter it into the table and  *)
  142.                                    (* output <w>.  Reset <w> to    *)
  143.                                    (* be the code for C ==> Step 6 *)
  144.  
  145.          IF ( WC = End_List ) THEN
  146.             BEGIN
  147.  
  148.                Make_Table_Entry( W , C );
  149.                Put_Code( W );
  150.                W := Lookup_String( No_Prev , C );
  151.  
  152.             END
  153.          ELSE                      (* If <w>C is in table, keep looking *)
  154.                                    (* for longer strings == Step 5      *)
  155.  
  156.             W := WC;
  157.  
  158.                                    (* Get next input character ==> Step 3 *)
  159.          Get_Char( C );
  160.  
  161.       END;
  162.                                    (* Make sure last code is       *)
  163.                                    (* written out ==> Step 4.      *)
  164.    Put_Code( W );
  165.  
  166. END   (* Do_Compression *);
  167.  
  168. (*--------------------------------------------------------------------------*)
  169. (*                     PibCompr --- Main program                            *)
  170. (*--------------------------------------------------------------------------*)
  171.  
  172. BEGIN (* PibCompr *)
  173.                                    (* We are doing compression *)
  174.    If_Compressing := TRUE;
  175.                                    (* Initialize compression   *)
  176.    Initialize;
  177.                                    (* Perform compression      *)
  178.    Do_Compression;
  179.                                    (* Clean up and exit        *)
  180.    Terminate;
  181.  
  182. END   (* PibCompr *).
  183.