home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PIBLZW.ZIP / PIBDCOMP.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1988-04-30  |  14.2 KB  |  317 lines
  1. (*$R-,V-,S-,I-*)
  2. PROGRAM PibDComp;
  3.  
  4. (*--------------------------------------------------------------------------*)
  5. (*                                                                          *)
  6. (*       Program:  PibDComp                                                 *)
  7. (*                                                                          *)
  8. (*       Purpose:  Decompresses a file compressed using Lempel-Ziv-Welch    *)
  9. (*                 appraoch by PibCompr.                                    *)
  10. (*                                                                          *)
  11. (*       Use:      PIBDCOMP  inputfile outputfile                           *)
  12. (*                                                                          *)
  13. (*                    inputfile  --- the input file to be decompressed      *)
  14. (*                    outputfile --- the output decompressed file           *)
  15. (*                                                                          *)
  16. (*       Remarks:                                                           *)
  17. (*                                                                          *)
  18. (*          PibDComp uncompresses a file compressed by PibCompr.            *)
  19. (*                                                                          *)
  20. (*       Algorithm:                                                         *)
  21. (*                                                                          *)
  22. (*          The decompression algorithm translates each received            *)
  23. (*          code into a prefix string and extension [suffix] character.     *)
  24. (*          The extension character is stored (in a push-down stack),       *)
  25. (*          and the prefix translated again, until the prefix is a          *)
  26. (*          single character, which completes decompression of this         *)
  27. (*          code.  The entire code is then output by popping the stack.     *)
  28. (*                                                                          *)
  29. (*          "An update to the string table is made for each code received   *)
  30. (*          (except the first one).  When a code has been translated,       *)
  31. (*          its final character is used as the extension character,         *)
  32. (*          combined with the prior string, to add a new string to          *)
  33. (*          the string table.  This new string is assigned a unique         *)
  34. (*          code value, which is the same code that the compressor          *)
  35. (*          assigned to that string.  In this way, the decompressor         *)
  36. (*          incrementally reconstructs the same string table that           *)
  37. (*          the decompressor used.... Unfortunately ... [the algorithm]     *)
  38. (*          does not work for an abnormal case.                             *)
  39. (*                                                                          *)
  40. (*          The abnormal case occurs whenever an input character string     *)
  41. (*          contains the sequence C<w>C<w>C, where C<w> already             *)
  42. (*          appears in the compressor string table."                        *)
  43. (*                                                                          *)
  44. (*          The decompression algorithm, augmented to handle                *)
  45. (*          the abnormal case, is as follows:                               *)
  46. (*                                                                          *)
  47. (*            1. Read first input code;                                     *)
  48. (*               Store in CODE and OLDcode;                                 *)
  49. (*               With CODE = code(C), output(C);  FINchar = C;              *)
  50. (*            2. Read next code to CODE; INcode = CODE;                     *)
  51. (*               If at end of file, exit;                                   *)
  52. (*            3. If CODE not in string table (special case) then            *)
  53. (*                  Output(FINchar);                                        *)
  54. (*                  CODE = OLDcode;                                         *)
  55. (*                  INcode = code(OLDcode, FINchar);                        *)
  56. (*            4. If CODE == code(<w>C) then                                 *)
  57. (*                  Push C onto the stack;                                  *)
  58. (*                  CODE == code(<w>);                                      *)
  59. (*                  Goto 4.                                                 *)
  60. (*            5. If CODE == code(C) then                                    *)
  61. (*                  Output C;                                               *)
  62. (*                  FINchar = C;                                            *)
  63. (*            6. While stack not empty                                      *)
  64. (*                  Output top of stack;                                    *)
  65. (*                  Pop stack;                                              *)
  66. (*            7. Put OLDcode,C into the string table.                       *)
  67. (*               OLDcode = INcode;                                          *)
  68. (*               Goto 2.                                                    *)
  69. (*                                                                          *)
  70. (*       Reference:                                                         *)
  71. (*                                                                          *)
  72. (*          "A Technique for High Performance Data Compression",            *)
  73. (*          Terry A. Welch, IEEE Computer,                                  *)
  74. (*          vol. 17, no. 6 (June 1984), pp. 8-19.                           *)
  75. (*                                                                          *)
  76. (*       Note:  The hashing algorithm used here isn't very good, and        *)
  77. (*              should be replaced by a better one.                         *)
  78. (*                                                                          *)
  79. (*       Usage note:                                                        *)
  80. (*                                                                          *)
  81. (*          You may use this program in any way you see fit without         *)
  82. (*          restriction.  I'd appreciate a citation if you do use this      *)
  83. (*          code in a program you distribute.                               *)
  84. (*                                                                          *)
  85. (*--------------------------------------------------------------------------*)
  86.  
  87. (*$I PIBLZW.DEF *)
  88.  
  89. CONST
  90.    MaxStack = 4096                 (* Decompression stack size  *);
  91.  
  92. VAR
  93.                                    (* Decompression stack       *)
  94.  
  95.    Stack         : ARRAY[1..MaxStack] OF INTEGER;
  96.  
  97.    Stack_Pointer : INTEGER         (* Decompression stack depth *);
  98.  
  99. (*$I PIBLZW.INC *)
  100.  
  101. (*--------------------------------------------------------------------------*)
  102. (*                  Push --- Push character onto stack                      *)
  103. (*--------------------------------------------------------------------------*)
  104.  
  105. PROCEDURE Push( C : INTEGER );
  106.  
  107. BEGIN (* Push *)
  108.  
  109.   INC( Stack_Pointer );
  110.   Stack[ Stack_Pointer ] := C;
  111.  
  112.   IF ( Stack_Pointer >= MaxStack ) THEN
  113.      BEGIN
  114.         WRITELN('Stack overflow!');
  115.         Terminate;
  116.         Halt;
  117.      END;
  118.  
  119. END  (* Push *);
  120.  
  121. (*--------------------------------------------------------------------------*)
  122. (*                  Pop --- Pop character from stack                        *)
  123. (*--------------------------------------------------------------------------*)
  124.  
  125. PROCEDURE Pop( VAR C : INTEGER );
  126.  
  127. BEGIN (* Pop *)
  128.  
  129.    IF ( Stack_Pointer > 0 ) THEN
  130.       BEGIN
  131.          C := Stack[Stack_Pointer];
  132.          DEC( Stack_Pointer );
  133.       END
  134.    ELSE
  135.       C := Empty;
  136.  
  137. END   (* Pop *);
  138.  
  139. (*--------------------------------------------------------------------------*)
  140. (*            Get_Code --- Get compression code from input file             *)
  141. (*--------------------------------------------------------------------------*)
  142.  
  143. PROCEDURE Get_Code( VAR Hash_Code : INTEGER );
  144.  
  145. VAR
  146.    Local_Buf : INTEGER;
  147.  
  148. BEGIN (* Get_Code *)
  149.  
  150.    IF ( Input_Code = Empty ) THEN
  151.       BEGIN
  152.  
  153.          Get_Char( Local_Buf );
  154.  
  155.          IF ( Local_Buf = EOF_Char ) THEN
  156.             BEGIN
  157.                Hash_Code := EOF_Char;
  158.                EXIT;
  159.             END;
  160.  
  161.          Get_Char( Input_Code );
  162.  
  163.          IF ( Input_Code = EOF_Char ) THEN
  164.             BEGIN
  165.                Hash_Code := EOF_Char;
  166.                EXIT;
  167.             END;
  168.  
  169.          Hash_Code  := ( ( Local_Buf SHL 4  ) AND $FF0 ) +
  170.                        ( ( Input_Code SHR 4 ) AND $00F );
  171.  
  172.          Input_Code := Input_Code AND $0F;
  173.  
  174.       END
  175.    ELSE
  176.       BEGIN
  177.  
  178.          Get_Char( Local_Buf );
  179.  
  180.          IF ( Local_Buf = EOF_Char ) THEN
  181.             BEGIN
  182.                Hash_Code := EOF_Char;
  183.                EXIT;
  184.             END;
  185.  
  186.          Hash_Code  := Local_Buf + ( ( Input_Code SHL 8 ) AND $F00 );
  187.          Input_Code := Empty;
  188.  
  189.       END;
  190.  
  191. END   (* Get_Code *);
  192.  
  193. (*--------------------------------------------------------------------------*)
  194. (*            Do_Decompression --- Perform decompression                    *)
  195. (*--------------------------------------------------------------------------*)
  196.  
  197. PROCEDURE Do_Decompression;
  198.  
  199. VAR
  200.    C         : INTEGER             (* Current input character *);
  201.    Code      : INTEGER             (* Current code string     *);
  202.    Old_Code  : INTEGER             (* Previous code string    *);
  203.    Fin_Char  : INTEGER             (* Final input character   *);
  204.    In_Code   : INTEGER             (* Current input code      *);
  205.    Last_Char : INTEGER             (* Previous character      *);
  206.    Unknown   : BOOLEAN             (* TRUE if code not found  *);
  207.    Temp_C    : INTEGER             (* Char popped off stack   *);
  208.  
  209. BEGIN (* Do_Decompression *)
  210.                                    (* Decompression stack is empty *)
  211.   Stack_Pointer := 0;
  212.                                    (* First string is always known *)
  213.   Unknown       := FALSE;
  214.                                    (* Get first string == Step 1   *)
  215.   Get_Code( Old_Code );
  216.  
  217.   Code          := Old_Code;
  218.                                    (* Output corresponding character *)
  219.  
  220.   C    := String_Table[Code].FollChar;
  221.  
  222.   Put_Char( C );
  223.                                    (* Remember this character  -- it    *)
  224.                                    (* is final character of next string *)
  225.   Fin_Char := C;
  226.                                    (* Get next code  == Step 2 *)
  227.   Get_Code( In_Code );
  228.  
  229.   WHILE( In_Code <> EOF_Char ) DO
  230.      BEGIN
  231.                                    (* Set code to this input code *)
  232.         Code := In_Code;
  233.                                    (* If code not in table, do special *)
  234.                                    (* case ==> Step 3                  *)
  235.  
  236.         IF ( NOT String_Table[Code].Used ) THEN
  237.            BEGIN
  238.               Last_Char := Fin_Char;
  239.               Code      := Old_Code;
  240.               Unknown   := TRUE;
  241.            END;
  242.                                    (* Run through code extracting single *)
  243.                                    (* characters from code string until  *)
  244.                                    (* no more characters can be removed. *)
  245.                                    (* Push these onto stack.  They will  *)
  246.                                    (* be entered in reverse order, and   *)
  247.                                    (* will come out in forwards order    *)
  248.                                    (* when popped off.                   *)
  249.                                    (*                                    *)
  250.                                    (* ==> Step 4                         *)
  251.  
  252.         WHILE( String_Table[Code].PrevChar <> No_Prev ) DO
  253.            WITH String_Table[Code] DO
  254.               BEGIN
  255.                  Push( FollChar );
  256.                  Code := PrevChar;
  257.               END;
  258.                                    (* We now have the first character in *)
  259.                                    (* the string.                        *)
  260.  
  261.         Fin_Char := String_Table[Code].FollChar;
  262.  
  263.                                    (* Output first character  ==> Step 5   *)
  264.         Put_Char( Fin_Char );
  265.                                    (* While the stack is not empty, remove *)
  266.                                    (* and output all characters from stack *)
  267.                                    (* which are rest of characters in the  *)
  268.                                    (* string.                              *)
  269.                                    (*                                      *)
  270.                                    (* ==> Step 6                           *)
  271.         Pop( Temp_C );
  272.  
  273.         WHILE( Temp_C <> Empty ) DO
  274.            BEGIN
  275.               Put_Char( Temp_C );
  276.               Pop( Temp_C );
  277.            END;
  278.                                    (* If code isn't known, output the      *)
  279.                                    (* follower character of last character *)
  280.                                    (* of string.                           *)
  281.         IF Unknown THEN
  282.            BEGIN
  283.               Fin_Char := Last_Char;
  284.               Put_Char( Fin_Char );
  285.               Unknown  := FALSE;
  286.            END;
  287.                                    (* Enter code into table ==> Step 7 *)
  288.  
  289.         Make_Table_Entry( Old_Code , Fin_Char );
  290.  
  291.                                    (* Make current code the previous code *)
  292.         Old_Code := In_Code;
  293.  
  294.                                    (* Get next code  == Step 2 *)
  295.         Get_Code( In_Code );
  296.  
  297.      END;
  298.  
  299. END   (* Do_Decompression *);
  300.  
  301. (*--------------------------------------------------------------------------*)
  302. (*                     PibDComp --- Main program                            *)
  303. (*--------------------------------------------------------------------------*)
  304.  
  305. BEGIN (* PibDComp *)
  306.                                    (* Indicate we are doing decompression *)
  307.    If_Compressing := FALSE;
  308.                                    (* Initialize for deceompression       *)
  309.    Initialize;
  310.                                    (* Perform decompression               *)
  311.    Do_Decompression;
  312.                                    (* Clean up and exit                   *)
  313.    Terminate;
  314.  
  315. END   (* PibDComp *).
  316.  
  317.