home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / UNZIPSRC.ZIP / UNZ.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1992-11-18  |  29.9 KB  |  1,267 lines

  1.  
  2. (*
  3.  * Copyright 1987, 1989 Samuel H. Smith;  All rights reserved
  4.  *
  5.  * This is a component of the ProDoor System.
  6.  * Do not distribute modified versions without my permission.
  7.  * Do not remove or alter this notice or any other copyright notice.
  8.  * If you use this in your own program you must distribute source code.
  9.  * Do not use any of this in a commercial product.
  10.  *
  11.  *)
  12.  
  13. (*
  14.  * UnZip - A simple zipfile extract utility
  15.  *
  16.  *)
  17.  
  18. {$I+}    {I/O checking}
  19. {$N-}    {Numeric coprocessor}
  20. {$V-}    {Relaxes string typing}
  21. {$B-}    {Boolean complete evaluation}
  22. {$S-}    {Stack checking}
  23. {$R-}    {Range checking}
  24. {$D+}    {Global debug information}
  25. {$L+}    {Local debug information}
  26.  
  27. {$M 5000,0,0} {minstack,minheap,maxheap}
  28.  
  29. program UnZip;
  30.  
  31. Uses
  32.    Dos, Mdosio;
  33.  
  34. const
  35.    version = 'UnZ:  Zipfile Extract v2.1 (PAS) of 11-19-92;  Copyright 1989 S.H.Smith';
  36.  
  37.  
  38.  
  39. (*
  40.  * Data declarations for the archive text-view functions.
  41.  *
  42.  *)
  43.  
  44. (* ----------------------------------------------------------- *)
  45. (*
  46.  * ZIPfile layout declarations
  47.  *
  48.  *)
  49.  
  50. type
  51.    signature_type = longint;
  52.  
  53. const
  54.    local_file_header_signature = $04034b50;
  55.  
  56. type
  57.    local_file_header = record
  58.       version_needed_to_extract:    word;
  59.       general_purpose_bit_flag:     word;
  60.       compression_method:           word;
  61.       last_mod_file_time:           word;
  62.       last_mod_file_date:           word;
  63.       crc32:                        longint;
  64.       compressed_size:              longint;
  65.       uncompressed_size:            longint;
  66.       filename_length:              word;
  67.       extra_field_length:           word;
  68.    end;
  69.  
  70. const
  71.    central_file_header_signature = $02014b50;
  72.  
  73. type
  74.    central_directory_file_header = record
  75.       version_made_by:                 word;
  76.       version_needed_to_extract:       word;
  77.       general_purpose_bit_flag:        word;
  78.       compression_method:              word;
  79.       last_mod_file_time:              word;
  80.       last_mod_file_date:              word;
  81.       crc32:                           longint;
  82.       compressed_size:                 longint;
  83.       uncompressed_size:               longint;
  84.       filename_length:                 word;
  85.       extra_field_length:              word;
  86.       file_comment_length:             word;
  87.       disk_number_start:               word;
  88.       internal_file_attributes:        word;
  89.       external_file_attributes:        longint;
  90.       relative_offset_local_header:    longint;
  91.    end;
  92.  
  93. const
  94.    end_central_dir_signature = $06054b50;
  95.  
  96. type
  97.    end_central_dir_record = record
  98.       number_this_disk:                         word;
  99.       number_disk_with_start_central_directory: word;
  100.       total_entries_central_dir_on_this_disk:   word;
  101.       total_entries_central_dir:                word;
  102.       size_central_directory:                   longint;
  103.       offset_start_central_directory:           longint;
  104.       zipfile_comment_length:                   word;
  105.    end;
  106.  
  107.  
  108.  
  109. (* ----------------------------------------------------------- *)
  110. (*
  111.  * input file variables
  112.  *
  113.  *)
  114.  
  115. const
  116.    uinbufsize = 512;    {input buffer size}
  117. var
  118.    zipeof:      boolean;
  119.    csize:       longint;
  120.    cusize:      longint;
  121.    cmethod:     integer;
  122.    cflags:      word;
  123.  
  124.    ctime:       word;
  125.    cdate:       word;
  126.    inbuf:       array[1..uinbufsize] of byte;
  127.    inpos:       integer;
  128.    incnt:       integer;
  129.    pc:          byte;
  130.    pcbits:      byte;
  131.    pcbitv:      byte;
  132.    zipfd:       dos_handle;
  133.    zipfn:       dos_filename;
  134.  
  135.  
  136.  
  137. (* ----------------------------------------------------------- *)
  138. (*
  139.  * output stream variables
  140.  *
  141.  *)
  142.  
  143. var
  144.    outbuf:      array[0..8192] of byte; {8192 or more for rle look-back}
  145.    outpos:      longint;                {absolute position in outfile}
  146.    outcnt:      integer;
  147.    outfd:       dos_handle;
  148.    filename:    string;
  149.    extra:       string;
  150.  
  151.  
  152.  
  153. (* ----------------------------------------------------------- *)
  154.  
  155. type
  156.    Sarray = array[0..255] of string[64];
  157.  
  158. var
  159.    factor:     integer;
  160.    followers:  Sarray;
  161.    ExState:    integer;
  162.    C:          integer;
  163.    V:          integer;
  164.    Len:        integer;
  165.  
  166. const
  167.    hsize =     8192;
  168.  
  169. type
  170.    hsize_array_integer = array[0..hsize] of integer;
  171.    hsize_array_byte    = array[0..hsize] of byte;
  172.  
  173. var
  174.    prefix_of:  hsize_array_integer;
  175.    suffix_of:  hsize_array_byte;
  176.    stack:      hsize_array_byte;
  177.    stackp:     integer;
  178.  
  179.  
  180.  
  181.  
  182. (*
  183.  * Zipfile input/output handlers
  184.  *
  185.  *)
  186.  
  187.  
  188. (* ------------------------------------------------------------- *)
  189. procedure skip_csize;
  190. begin
  191.    dos_lseek(zipfd,csize,seek_cur);
  192.    zipeof := true;
  193.    csize := 0;
  194.    incnt := 0;
  195. end;
  196.  
  197.  
  198. (* ------------------------------------------------------------- *)
  199. procedure ReadByte(var x: byte);
  200. begin
  201.    if incnt = 0 then
  202.    begin
  203.       if csize = 0 then
  204.       begin
  205.          zipeof := true;
  206.          exit;
  207.       end;
  208.  
  209.       inpos := sizeof(inbuf);
  210.       if inpos > csize then
  211.          inpos := csize;
  212.       incnt := dos_read(zipfd,inbuf,inpos);
  213.  
  214.       inpos := 1;
  215.       dec(csize,incnt);
  216.    end;
  217.  
  218.    x := inbuf[inpos];
  219.    inc(inpos);
  220.    dec(incnt);
  221. end;
  222.  
  223.  
  224. (*
  225.  * Copyright 1987, 1989 Samuel H. Smith;  All rights reserved
  226.  *
  227.  * This is a component of the ProDoor System.
  228.  * Do not distribute modified versions without my permission.
  229.  * Do not remove or alter this notice or any other copyright notice.
  230.  * If you use this in your own program you must distribute source code.
  231.  * Do not use any of this in a commercial product.
  232.  *
  233.  *)
  234.  
  235. (******************************************************
  236.  *
  237.  * Procedure:  itoh
  238.  *
  239.  * Purpose:    converts an integer into a string of hex digits
  240.  *
  241.  * Example:    s := itoh(i);
  242.  *
  243.  *)
  244.  
  245. function itoh(i: longint): string;   {integer to hex conversion}
  246. var
  247.    h:   string;
  248.    w:   word;
  249.  
  250.    procedure digit(ix: integer; ii: word);
  251.    begin
  252.       ii := ii and 15;
  253.       if ii > 9 then 
  254.          ii := ii + 7 + ord('a') - ord('A');
  255.       h[ix] := chr(ii + ord('0'));
  256.    end;
  257.  
  258. begin
  259.    w := i and $FFFF;
  260.    h[0] := chr(4);
  261.    digit(1,w shr 12);
  262.    digit(2,w shr 8);
  263.    digit(3,w shr 4);
  264.    digit(4,w);
  265.    itoh := h;   
  266. end;
  267.  
  268.  
  269. (* ------------------------------------------------------------- *)
  270. procedure ReadBits(bits: integer; var result: integer);
  271.    {read the specified number of bits}
  272. const
  273.    bit:     integer = 0;
  274.    bitv:    integer = 0;
  275.    x:       integer = 0;
  276. begin
  277.    x := 0;
  278.    bitv := 1;
  279.  
  280.    for bit := 0 to bits-1 do
  281.    begin
  282.  
  283.       if pcbits > 0 then
  284.       begin
  285.          dec(pcbits);
  286.          pcbitv := pcbitv shl 1;
  287.       end
  288.       else
  289.  
  290.       begin
  291.          ReadByte(pc);
  292.          pcbits := 7;
  293.          pcbitv := 1;
  294.       end;
  295.  
  296.       if (pc and pcbitv) <> 0 then
  297.          x := x or bitv;
  298.  
  299.       bitv := bitv shl 1;
  300.    end;
  301.  
  302. (* writeln(bits,'-',itoh(x)); *)
  303.    result := x;
  304. end;
  305.  
  306.  
  307. (* ---------------------------------------------------------- *)
  308. procedure get_string(ln: word; var s: string);
  309. var
  310.    n: word;
  311. begin
  312.    n := ln;
  313.    if ln > 255 then
  314.       n := 255;
  315.    n := dos_read(zipfd,s[1],n);
  316.    s[0] := chr(n);
  317.    if ln > 255 then
  318.       dos_lseek(zipfd,ln-255,seek_cur);
  319. end;
  320.  
  321.  
  322. (* ------------------------------------------------------------- *)
  323. procedure OutByte (c: integer);
  324.    (* output each character from archive to screen *)
  325. begin
  326.    outbuf[outcnt {outpos mod sizeof(outbuf)} ] := c;
  327.    inc(outpos);
  328.    inc(outcnt);
  329.  
  330.    if outcnt = sizeof(outbuf) then
  331.    begin
  332.       dos_write(outfd,outbuf,outcnt);
  333.       outcnt := 0;
  334.       write('.');
  335.    end;
  336. end;
  337.  
  338. (*
  339.  * expand 'reduced' members of a zipfile
  340.  *
  341.  *)
  342.  
  343. (*
  344.  * The Reducing algorithm is actually a combination of two
  345.  * distinct algorithms.  The first algorithm compresses repeated
  346.  * byte sequences, and the second algorithm takes the compressed
  347.  * stream from the first algorithm and applies a probabilistic
  348.  * compression method.
  349.  *
  350.  *)
  351.  
  352. function reduce_L(x: byte): byte;
  353. begin
  354.    case factor of
  355.       1: reduce_L := x and $7f;
  356.       2: reduce_L := x and $3f;
  357.       3: reduce_L := x and $1f;
  358.       4: reduce_L := x and $0f;
  359.    end;
  360. end;
  361.  
  362. function reduce_F(x: byte): byte;
  363. begin
  364.    case factor of
  365.       1: if x = 127 then reduce_F := 2 else reduce_F := 3;
  366.       2: if x = 63  then reduce_F := 2 else reduce_F := 3;
  367.       3: if x = 31  then reduce_F := 2 else reduce_F := 3;
  368.       4: if x = 15  then reduce_F := 2 else reduce_F := 3;
  369.    end;
  370. end;
  371.  
  372. function reduce_D(x,y: byte): word;
  373. begin
  374.    case factor of
  375.       1: reduce_D := ((x shr 7) and $01) * 256 + Y + 1;
  376.       2: reduce_D := ((x shr 6) and $03) * 256 + Y + 1;
  377.       3: reduce_D := ((x shr 5) and $07) * 256 + Y + 1;
  378.       4: reduce_D := ((x shr 4) and $0f) * 256 + Y + 1;
  379.    end;
  380. end;
  381.  
  382. function reduce_B(x: byte): word;
  383.    {number of bits needed to encode the specified number}
  384. begin
  385.    case x-1 of
  386.       0..1:    reduce_B := 1;
  387.       2..3:    reduce_B := 2;
  388.       4..7:    reduce_B := 3;
  389.       8..15:   reduce_B := 4;
  390.      16..31:   reduce_B := 5;
  391.      32..63:   reduce_B := 6;
  392.      64..127:  reduce_B := 7;
  393.    else        reduce_B := 8;
  394.    end;
  395. end;
  396.  
  397. procedure Expand(c: byte);
  398. const
  399.    DLE = 144;
  400. var
  401.    op:   longint;
  402.    i:    integer;
  403.  
  404. begin
  405.  
  406.    case ExState of
  407.         0:  if C <> DLE then
  408.                 outbyte(C)
  409.             else
  410.                 ExState := 1;
  411.  
  412.         1:  if C <> 0 then
  413.             begin
  414.                 V := C;
  415.                 Len := reduce_L(V);
  416.                 ExState := reduce_F(Len);
  417.             end
  418.             else
  419.             begin
  420.                 outbyte(DLE);
  421.                 ExState := 0;
  422.             end;
  423.  
  424.         2:  begin
  425.                Len := Len + C;
  426.                ExState := 3;
  427.             end;
  428.  
  429.         3:  begin
  430.                op := outpos-reduce_D(V,C);
  431.                for i := 0 to Len+2 do
  432.                begin
  433.                   if op < 0 then
  434.                      outbyte(0)
  435.                   else
  436.                      outbyte(outbuf[op mod sizeof(outbuf)]);
  437.                   inc(op);
  438.                end;
  439.  
  440.                ExState := 0;
  441.             end;
  442.    end;
  443. end;
  444.  
  445.  
  446. procedure LoadFollowers;
  447. var
  448.    x: integer;
  449.    i: integer;
  450.    b: integer;
  451. begin
  452.    for x := 255 downto 0 do
  453.    begin
  454.       ReadBits(6,b);
  455.       followers[x][0] := chr(b);
  456.  
  457.       for i := 1 to length(followers[x]) do
  458.       begin
  459.          ReadBits(8,b);
  460.          followers[x][i] := chr(b);
  461.       end;
  462.    end;
  463. end;
  464.  
  465.  
  466. (* ----------------------------------------------------------- *)
  467. procedure unReduce;
  468.    {expand probablisticly reduced data}
  469.  
  470. var
  471.    lchar:   integer;
  472.    lout:    integer;
  473.    I:       integer;
  474.  
  475. begin
  476.    factor := cmethod - 1;
  477.    if (factor < 1) or (factor > 4) then
  478.    begin
  479.       skip_csize;
  480.       exit;
  481.    end;
  482.  
  483.    ExState := 0;
  484.    LoadFollowers;
  485.    lchar := 0;
  486.  
  487.    while (not zipeof) and (outpos < cusize) do
  488.    begin
  489.  
  490.       if followers[lchar] = '' then
  491.          ReadBits( 8,lout )
  492.       else
  493.  
  494.       begin
  495.          ReadBits(1,lout);
  496.          if lout <> 0 then
  497.             ReadBits( 8,lout )
  498.          else
  499.          begin
  500.             ReadBits( reduce_B(length(followers[lchar])), I );
  501.             lout := ord( followers[lchar][I+1] );
  502.          end;
  503.       end;
  504.  
  505.       if zipeof then
  506.          exit;
  507.  
  508.       Expand( lout );
  509.       lchar := lout;
  510.    end;
  511.  
  512. end;
  513.  
  514.  
  515.  
  516. (*
  517.  * expand 'shrunk' members of a zipfile
  518.  *
  519.  *)
  520.  
  521. (*
  522.  * UnShrinking
  523.  * -----------
  524.  *
  525.  * Shrinking is a Dynamic Ziv-Lempel-Welch compression algorithm
  526.  * with partial clearing.  The initial code size is 9 bits, and
  527.  * the maximum code size is 13 bits.  Shrinking differs from
  528.  * conventional Dynamic Ziv-lempel-Welch implementations in several
  529.  * respects:
  530.  *
  531.  * 1)  The code size is controlled by the compressor, and is not
  532.  *     automatically increased when codes larger than the current
  533.  *     code size are created (but not necessarily used).  When
  534.  *     the decompressor encounters the code sequence 256
  535.  *     (decimal) followed by 1, it should increase the code size
  536.  *     read from the input stream to the next bit size.  No
  537.  *     blocking of the codes is performed, so the next code at
  538.  *     the increased size should be read from the input stream
  539.  *     immediately after where the previous code at the smaller
  540.  *     bit size was read.  Again, the decompressor should not
  541.  *     increase the code size used until the sequence 256,1 is
  542.  *     encountered.
  543.  *
  544.  * 2)  When the table becomes full, total clearing is not
  545.  *     performed.  Rather, when the compresser emits the code
  546.  *     sequence 256,2 (decimal), the decompressor should clear
  547.  *     all leaf nodes from the Ziv-Lempel tree, and continue to
  548.  *     use the current code size.  The nodes that are cleared
  549.  *     from the Ziv-Lempel tree are then re-used, with the lowest
  550.  *     code value re-used first, and the highest code value
  551.  *     re-used last.  The compressor can emit the sequence 256,2
  552.  *     at any time.
  553.  *
  554.  *)
  555.  
  556. procedure unShrink;
  557.  
  558. const
  559.    max_bits =  13;
  560.    init_bits = 9;
  561.    first_ent = 257;
  562.    clear =     256;
  563.    
  564. var
  565.    cbits:      integer;
  566.    maxcode:    integer;
  567.    free_ent:   integer;
  568.    maxcodemax: integer;
  569.    offset:     integer;
  570.    sizex:      integer;
  571.    finchar:    integer;
  572.    code:       integer;
  573.    oldcode:    integer;
  574.    incode:     integer;
  575.  
  576.  
  577. (* ------------------------------------------------------------- *)
  578. procedure partial_clear;
  579. var
  580.    pr:   integer;
  581.    cd:   integer;
  582.  
  583. begin
  584.    {mark all nodes as potentially unused}
  585.    for cd := first_ent to free_ent-1 do
  586.       word(prefix_of[cd]) := prefix_of[cd] or $8000;
  587.  
  588.  
  589.    {unmark those that are used by other nodes}
  590.    for cd := first_ent to free_ent-1 do
  591.    begin
  592.       pr := prefix_of[cd] and $7fff;    {reference to another node?}
  593.       if pr >= first_ent then           {flag node as referenced}
  594.          prefix_of[pr] := prefix_of[pr] and $7fff;
  595.    end;
  596.  
  597.  
  598.    {clear the ones that are still marked}
  599.    for cd := first_ent to free_ent-1 do
  600.       if (prefix_of[cd] and $8000) <> 0 then
  601.          prefix_of[cd] := -1;
  602.  
  603.  
  604.    {find first cleared node as next free_ent}
  605.    free_ent := first_ent;
  606.    while (free_ent < maxcodemax) and (prefix_of[free_ent] <> -1) do
  607.       inc(free_ent);
  608. end;
  609.  
  610.  
  611. (* ------------------------------------------------------------- *)
  612. begin
  613.    (* decompress the file *)
  614.    maxcodemax := 1 shl max_bits;
  615.    cbits := init_bits;
  616.    maxcode := (1 shl cbits)- 1;
  617.    free_ent := first_ent;
  618.    offset := 0;
  619.    sizex := 0;
  620.  
  621.    fillchar(prefix_of,sizeof(prefix_of),$FF);
  622.    for code := 255 downto 0 do
  623.    begin
  624.       prefix_of[code] := 0;
  625.       suffix_of[code] := code;
  626.    end;
  627.  
  628.    ReadBits(cbits,oldcode);
  629.    if zipeof then
  630.       exit;
  631.    finchar := oldcode;
  632.  
  633.    OutByte(finchar);
  634.  
  635.    stackp := 0;
  636.  
  637.    while (not zipeof) do
  638.    begin
  639.       ReadBits(cbits,code);
  640.       if zipeof then
  641.          exit;
  642.  
  643.       while (code = clear) do
  644.       begin
  645.          ReadBits(cbits,code);
  646.  
  647.          case code of
  648.             1: begin
  649.                   inc(cbits);
  650.                   if cbits = max_bits then
  651.                      maxcode := maxcodemax
  652.                   else
  653.                      maxcode := (1 shl cbits) - 1;
  654.                end;
  655.  
  656.             2: partial_clear;
  657.          end;
  658.  
  659.          ReadBits(cbits,code);
  660.          if zipeof then
  661.             exit;
  662.       end;
  663.  
  664.  
  665.       {special case for KwKwK string}
  666.       incode := code;
  667.       if prefix_of[code] = -1 then
  668.       begin
  669.          stack[stackp] := finchar;
  670.          inc(stackp);
  671.          code := oldcode;
  672.       end;
  673.  
  674.  
  675.       {generate output characters in reverse order}
  676.       while (code >= first_ent) do
  677.       begin
  678.          stack[stackp] := suffix_of[code];
  679.          inc(stackp);
  680.          code := prefix_of[code];
  681.       end;
  682.  
  683.       finchar := suffix_of[code];
  684.       stack[stackp] := finchar;
  685.       inc(stackp);
  686.  
  687.  
  688.       {and put them out in forward order}
  689.       while (stackp > 0) do
  690.       begin
  691.          dec(stackp);
  692.          OutByte(stack[stackp]);
  693.       end;
  694.  
  695.  
  696.       {generate new entry}
  697.       code := free_ent;
  698.       if code < maxcodemax then
  699.       begin
  700.          prefix_of[code] := oldcode;
  701.          suffix_of[code] := finchar;
  702.          while (free_ent < maxcodemax) and (prefix_of[free_ent] <> -1) do
  703.             inc(free_ent);
  704.       end;
  705.  
  706.  
  707.       {remember previous code}
  708.       oldcode := incode;
  709.    end;
  710.  
  711. end;
  712.  
  713.  
  714.  
  715. (* ------------------------------------------------------------- *)
  716. (*
  717.  * Imploding
  718.  * ---------
  719.  *
  720.  * The Imploding algorithm is actually a combination of two distinct
  721.  * algorithms.  The first algorithm compresses repeated byte sequences
  722.  * using a sliding dictionary.  The second algorithm is used to compress
  723.  * the encoding of the sliding dictionary ouput, using multiple
  724.  * Shannon-Fano trees.
  725.  *
  726.  *)
  727.  
  728. const
  729.    maxSF = 256;
  730.  
  731. type
  732.    sf_entry = record
  733.                  Code:       word;
  734.                  Value:      byte;
  735.                  BitLength:  byte;
  736.               end;
  737.  
  738.    sf_tree = record  {a shannon-fano tree}
  739.       entry:         array[0..maxSF] of sf_entry;
  740.       entries:       integer;
  741.       MaxLength:     integer;
  742.    end;
  743.  
  744.    sf_treep = ^sf_tree;
  745.  
  746. var
  747.    lit_tree:               sf_tree;
  748.    length_tree:            sf_tree;
  749.    distance_tree:          sf_tree;
  750.    lit_tree_present:       boolean;
  751.    eightK_dictionary:      boolean;
  752.    minimum_match_length:   integer;
  753.    dict_bits:              integer;
  754.  
  755.  
  756. procedure SortLengths(var tree: sf_tree);
  757.    {Sort the Bit Lengths in ascending order, while retaining the order
  758.     of the original lengths stored in the file}
  759. var
  760.    x:       integer;
  761.    gap:     integer;
  762.    t:       sf_entry;
  763.    noswaps: boolean;
  764.    a,b:     integer;
  765.  
  766. begin
  767.    gap := tree.entries div 2;
  768.  
  769.    repeat
  770.       repeat
  771.          noswaps := true;
  772.          for x := 0 to (tree.entries-1)-gap do
  773.          begin
  774.             a := tree.entry[x].BitLength;
  775.             b := tree.entry[x+gap].BitLength;
  776.             if (a > b) or
  777.                ((a = b) and (tree.entry[x].Value > tree.entry[x+gap].Value)) then
  778.             begin
  779.                t := tree.entry[x];
  780.                tree.entry[x] := tree.entry[x+gap];
  781.                tree.entry[x+gap] := t;
  782.                noswaps := false;
  783.             end;
  784.          end;
  785.       until noswaps;
  786.  
  787.       gap := gap div 2;
  788.    until gap < 1;
  789. end;
  790.  
  791.  
  792. (* ----------------------------------------------------------- *)
  793. procedure ReadLengths(var tree: sf_tree);
  794. var
  795.    treeBytes:  integer;
  796.    i:          integer;
  797.    num,len:    integer;
  798.  
  799. begin
  800.    {get number of bytes in compressed tree}
  801.    ReadBits(8,treeBytes);
  802.    inc(treeBytes);
  803.    i := 0;
  804.  
  805.    begin
  806.       tree.MaxLength := 0;
  807.  
  808.       {High 4 bits: Number of values at this bit length + 1. (1 - 16)
  809.        Low  4 bits: Bit Length needed to represent value + 1. (1 - 16)}
  810.       while treeBytes > 0 do
  811.       begin
  812.          ReadBits(4,len);  inc(len);
  813.          ReadBits(4,num);  inc(num);
  814.  
  815.          while num > 0 do
  816.          begin
  817.             if len > tree.MaxLength then
  818.                tree.MaxLength := len;
  819.             tree.entry[i].BitLength := len;
  820.             tree.entry[i].Value := i;
  821.             inc(i);
  822.             dec(num);
  823.          end;
  824.  
  825.          dec(treeBytes);
  826.       end;
  827.    end;
  828. end;
  829.  
  830.  
  831. (* ----------------------------------------------------------- *)
  832. procedure GenerateTrees(var tree: sf_tree);
  833.    {Generate the Shannon-Fano trees}
  834. var
  835.    Code:          word;
  836.    CodeIncrement: integer;
  837.    LastBitLength: integer;
  838.    i:             integer;
  839.  
  840. begin
  841.    Code := 0;
  842.    CodeIncrement := 0;
  843.    LastBitLength := 0;
  844.  
  845.    i := tree.entries - 1;   {either 255 or 63}
  846.    while i >= 0 do
  847.    begin
  848.       inc(Code,CodeIncrement);
  849.       if tree.entry[i].BitLength <> LastBitLength then
  850.       begin
  851.          LastBitLength := tree.entry[i].BitLength;
  852.          CodeIncrement := 1 shl (16 - LastBitLength);
  853.       end;
  854.  
  855.       tree.entry[i].Code := Code;
  856.       dec(i);
  857.    end;
  858. end;
  859.  
  860.  
  861. (* ----------------------------------------------------------- *)
  862. procedure ReverseBits(var tree: sf_tree);
  863.    {Reverse the order of all the bits in the above ShannonCode[]
  864.     vector, so that the most significant bit becomes the least
  865.     significant bit. For example, the value 0x1234 (hex) would become
  866.     0x2C48 (hex).}
  867. var
  868.    i:    integer;
  869.    mask: word;
  870.    revb: word;
  871.    v:    word;
  872.    o:    word;
  873.    b:    integer;
  874.  
  875. begin
  876.    for i := 0 to tree.entries-1 do
  877.    begin
  878.       {get original code}
  879.       o := tree.entry[i].Code;
  880.  
  881.       {reverse each bit}
  882.       mask := $0001;
  883.       revb := $8000;
  884.       v := 0;
  885.       for b := 0 to 15 do
  886.       begin
  887.          {if bit set in mask, then substitute reversed bit}
  888.          if (o and mask) <> 0 then
  889.             v := v or revb;
  890.  
  891.          {advance to next bit}
  892.          revb := revb shr 1;
  893.          mask := mask shl 1;
  894.       end;
  895.  
  896.       {store reversed bits}
  897.       tree.entry[i].Code := v;
  898.    end;
  899. end;
  900.  
  901.  
  902. (* ----------------------------------------------------------- *)
  903. procedure LoadTree(var tree: sf_tree;
  904.                    treesize: integer);
  905.    {allocate and load a shannon-fano tree from the compressed file}
  906. begin
  907.    tree.entries := treesize;
  908.    ReadLengths(tree);
  909.    SortLengths(tree);
  910.    GenerateTrees(tree);
  911.    ReverseBits(tree);
  912. end;
  913.  
  914.  
  915. (* ----------------------------------------------------------- *)
  916. procedure LoadTrees;
  917. begin
  918.    eightK_dictionary := (cflags and $02) <> 0; {bit 1}
  919.    lit_tree_present := (cflags and $04) <> 0; {bit 2}
  920.  
  921.    if eightK_dictionary then
  922.       dict_bits := 7
  923.    else
  924.       dict_bits := 6;
  925.  
  926.    if lit_tree_present then
  927.    begin
  928.       minimum_match_length := 3;
  929.       LoadTree(lit_tree,256);
  930.    end
  931.    else
  932.       minimum_match_length := 2;
  933.  
  934.    LoadTree(length_tree,64);
  935.    LoadTree(distance_tree,64);
  936. end;
  937.  
  938.  
  939. (* ----------------------------------------------------------- *)
  940. procedure ReadTree(var tree: sf_tree;
  941.                    var dest: integer);
  942.    {read next byte using a shannon-fano tree}
  943. var
  944.    bits: integer;
  945.    cv:   word;
  946.    b:    integer;
  947.    cur:  integer;
  948.  
  949. begin
  950.    bits := 0;
  951.    cv := 0;
  952.    cur := 0;
  953.    dest := -1; {in case of error}
  954.  
  955.    while true do
  956.    begin
  957.       ReadBits(1,b);
  958.       cv := cv or (b shl bits);
  959.       inc(bits);
  960.  
  961.       (* this is a very poor way of decoding shannon-fano.  two quicker
  962.       methods come to mind:
  963.          a) arrange the tree as a huffman-style binary tree with
  964.             a "leaf" indicator at each node,
  965.       and
  966.          b) take advantage of the fact that s-f codes are at most 8
  967.             bits long and alias unused codes for all bits following
  968.             the "leaf" bit.
  969.       *)
  970.  
  971.       while tree.entry[cur].BitLength < bits do
  972.       begin
  973.          inc(cur);
  974.          if cur >= tree.entries then
  975.             exit;
  976.       end;
  977.  
  978.       while tree.entry[cur].BitLength = bits do
  979.       begin
  980.          if tree.entry[cur].Code = cv then
  981.          begin
  982.             dest := tree.entry[cur].Value;
  983.             exit;
  984.          end;
  985.  
  986.          inc(cur);
  987.          if cur >= tree.entries then
  988.             exit;
  989.       end;
  990.    end;
  991. end;
  992.  
  993.  
  994. (* ----------------------------------------------------------- *)
  995. procedure unImplode;
  996.    {expand imploded data}
  997.  
  998. var
  999.    lout:       integer;
  1000.    op:         longint;
  1001.    Length:     integer;
  1002.    Distance:   integer;
  1003.    i:          integer;
  1004.  
  1005. begin
  1006.    LoadTrees;
  1007.  
  1008.    while (not zipeof) and (outpos < cusize) do
  1009.    begin
  1010.       ReadBits(1,lout);
  1011.  
  1012.       if lout <> 0 then    {encoded data is literal data}
  1013.       begin
  1014.          if lit_tree_present then
  1015.             ReadTree(lit_tree,lout)   {use Literal Shannon-Fano tree}
  1016.          else
  1017.             ReadBits(8,lout);
  1018.  
  1019.          OutByte(lout);
  1020.       end
  1021.       else
  1022.  
  1023.       begin          {encoded data is sliding dictionary match}
  1024.          readBits(dict_bits,lout);
  1025.          Distance := lout;
  1026.  
  1027.          ReadTree(distance_tree,lout);
  1028.          Distance := Distance or (lout shl dict_bits);
  1029.          {using the Distance Shannon-Fano tree, read and decode the
  1030.             upper 6 bits of the Distance value}
  1031.  
  1032.          ReadTree(length_tree,Length);
  1033.          {using the Length Shannon-Fano tree, read and decode the Length value}
  1034.  
  1035.          inc(Length,Minimum_Match_Length);
  1036.          if Length = (63 + Minimum_Match_Length) then
  1037.          begin
  1038.             ReadBits(8,lout);
  1039.             inc(Length,lout);
  1040.          end;
  1041.  
  1042.          {move backwards Distance+1 bytes in the output stream, and copy
  1043.           Length characters from this position to the output stream.
  1044.           (if this position is before the start of the output stream,
  1045.           then assume that all the data before the start of the output
  1046.           stream is filled with zeros)}
  1047.  
  1048.          op := outpos - Distance - 1;
  1049.          for i := 1 to Length do
  1050.          begin
  1051.             if op < 0 then
  1052.                OutByte(0)
  1053.             else
  1054.                OutByte(outbuf[op mod sizeof(outbuf)]);
  1055.             inc(op);
  1056.          end;
  1057.       end;
  1058.    end;
  1059. end;
  1060.  
  1061.  
  1062.  
  1063. (*
  1064.  * This procedure displays the text contents of a specified archive
  1065.  * file.  The filename must be fully specified and verified.
  1066.  *
  1067.  *)
  1068.  
  1069.  
  1070. (* ---------------------------------------------------------- *)
  1071. procedure extract_member;
  1072. var
  1073.    b: byte;
  1074.  
  1075. begin
  1076.    pcbits := 0;
  1077.    incnt := 0;
  1078.    outpos := 0;
  1079.    outcnt := 0;
  1080.    zipeof := false;
  1081.  
  1082.    outfd := dos_create(filename);
  1083.    if outfd = dos_error then
  1084.    begin
  1085.       writeln('Can''t create output: ', filename);
  1086.       halt;
  1087.    end;
  1088.  
  1089.    case cmethod of
  1090.       0:    {stored}
  1091.             begin
  1092.                write(' Extract: ',filename,' ...');
  1093.                while (not zipeof) do
  1094.                begin
  1095.                   ReadByte(b);
  1096.                   OutByte(b);
  1097.                end;
  1098.             end;
  1099.  
  1100.       1:    begin
  1101.                write('UnShrink: ',filename,' ...');
  1102.                UnShrink;
  1103.             end;
  1104.  
  1105.       2..5: begin
  1106.                write('  Expand: ',filename,' ...');
  1107.                UnReduce;
  1108.             end;
  1109.  
  1110.       6:    begin
  1111.                write(' Explode: ',filename,' ...');
  1112.                unImplode;
  1113.             end;
  1114.  
  1115.       else  write('Unknown compression method.');
  1116.    end;
  1117.  
  1118.    if outcnt > 0 then
  1119.       dos_write(outfd,outbuf,outcnt);
  1120.  
  1121.    dos_file_times(outfd,time_set,ctime,cdate);
  1122.    dos_close(outfd);
  1123.  
  1124.    writeln('  done.');
  1125. end;
  1126.  
  1127.  
  1128. (* ---------------------------------------------------------- *)
  1129. procedure process_local_file_header;
  1130. var
  1131.    n:             word;
  1132.    rec:           local_file_header;
  1133.  
  1134. begin
  1135.    n := dos_read(zipfd,rec,sizeof(rec));
  1136.    get_string(rec.filename_length,filename);
  1137.    get_string(rec.extra_field_length,extra);
  1138.    csize := rec.compressed_size;
  1139.    cusize := rec.uncompressed_size;
  1140.    cmethod := rec.compression_method;
  1141.    cflags := rec.general_purpose_bit_flag;
  1142.    ctime := rec.last_mod_file_time;
  1143.    cdate := rec.last_mod_file_date;
  1144.    extract_member;
  1145. end;
  1146.  
  1147.  
  1148. (* ---------------------------------------------------------- *)
  1149. procedure process_central_file_header;
  1150. var
  1151.    n:             word;
  1152.    rec:           central_directory_file_header;
  1153.    filename:      string;
  1154.    extra:         string;
  1155.    comment:       string;
  1156.  
  1157. begin
  1158.    n := dos_read(zipfd,rec,sizeof(rec));
  1159.    get_string(rec.filename_length,filename);
  1160.    get_string(rec.extra_field_length,extra);
  1161.    get_string(rec.file_comment_length,comment);
  1162. end;
  1163.  
  1164.  
  1165. (* ---------------------------------------------------------- *)
  1166. procedure process_end_central_dir;
  1167. var
  1168.    n:             word;
  1169.    rec:           end_central_dir_record;
  1170.    comment:       string;
  1171.  
  1172. begin
  1173.    n := dos_read(zipfd,rec,sizeof(rec));
  1174.    get_string(rec.zipfile_comment_length,comment);
  1175. end;
  1176.  
  1177.  
  1178. (* ---------------------------------------------------------- *)
  1179. procedure process_headers;
  1180. var
  1181.    sig:  longint;
  1182.  
  1183. begin
  1184.    dos_lseek(zipfd,0,seek_start);
  1185.  
  1186.    while true do
  1187.    begin
  1188.       if dos_read(zipfd,sig,sizeof(sig)) <> sizeof(sig) then
  1189.          exit
  1190.       else
  1191.  
  1192.       if sig = local_file_header_signature then
  1193.          process_local_file_header
  1194.       else
  1195.  
  1196.       if sig = central_file_header_signature then
  1197.          process_central_file_header
  1198.       else
  1199.  
  1200.       if sig = end_central_dir_signature then
  1201.       begin
  1202.          process_end_central_dir;
  1203.          exit;
  1204.       end
  1205.  
  1206.       else
  1207.       begin
  1208.          writeln('Invalid Zipfile Header');
  1209.          exit;
  1210.       end;
  1211.    end;
  1212.  
  1213. end;
  1214.  
  1215.  
  1216. (* ---------------------------------------------------------- *)
  1217. procedure extract_zipfile;
  1218. begin
  1219.    zipfd := dos_open(zipfn,open_read);
  1220.    if zipfd = dos_error then
  1221.       exit;
  1222.  
  1223.    process_headers;
  1224.  
  1225.    dos_close(zipfd);
  1226. end;
  1227.  
  1228.  
  1229. (*
  1230.  * main program
  1231.  *
  1232.  *)
  1233.  
  1234. begin
  1235.    if paramcount <> 1 then
  1236.    begin
  1237.       writeln;
  1238.       writeln(version);
  1239.       writeln('Courtesy of:  S.H.Smith  and  The Tool Shop BBS,  (818) 891-6780.');
  1240.       writeln;
  1241.       writeln('You may copy and distribute this program freely, provided that:');
  1242.       writeln('    1)   No fee is charged for such copying and distribution, and');
  1243.       writeln('    2)   It is distributed ONLY in its original, unmodified state.');
  1244.       writeln('If you wish to distribute a modified version of this program, you MUST');
  1245.       writeln('include the source code.');
  1246.       writeln;
  1247.       writeln('If you modify this program, I would appreciate a copy of the  new source');
  1248.       writeln('code.   I am holding the copyright on the source code, so please don''t');
  1249.       writeln('delete my name from the program files or from the documentation.');
  1250.       writeln('IN NO EVENT WILL I BE LIABLE TO YOU FOR ANY DAMAGES, INCLUDING ANY LOST');
  1251.       writeln('PROFITS, LOST SAVINGS OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES');
  1252.       writeln('ARISING OUT OF YOUR USE OR INABILITY TO USE THE PROGRAM, OR FOR ANY');
  1253.       writeln('CLAIM BY ANY OTHER PARTY.');
  1254.       writeln;
  1255.       writeln('Usage:  UnZip FILE[.zip]');
  1256.       halt;
  1257.    end;
  1258.  
  1259.    zipfn := paramstr(1);
  1260.    if pos('.',zipfn) = 0 then
  1261.       zipfn := zipfn + '.ZIP';
  1262.  
  1263.    extract_zipfile;
  1264. end.
  1265.  
  1266.  
  1267.