
/*
 * Copyright 1989 Samuel H. Smith;  All rights reserved
 *
 * Do not distribute modified versions without my permission.
 * Do not remove or alter this notice or any other copyright notice.
 * If you use this in your own program you must distribute source code.
 * Do not use any of this in a commercial product.
 *
 */

/*
 * ST Modifications courtesy of William K. Day
 *
 * I removed a large part of the portability definitions to allow
 * a quick port to the ST.  Sorry.  The original C code from the
 * original archive is present in this archive by the filename
 * unzip.org.
 *
 */

/*
 * UnZip - A simple zipfile extract utility
 */

#define VERSION  \
	"UnZip:  Zipfile Extract v2.0.2 of 11-25-90;  (C) 1990 William K. Day"

typedef unsigned char byte;	/* code assumes UNSIGNED bytes */
typedef long longint;		/* sizeof must be 4 bytes */
typedef unsigned short word;	/* sizeof must be 2 bytes */
typedef char boolean;

#define STRSIZ 256
#define	VOIDARG	void		/* function definitions support (void) */
#define O_BINARY 0

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <ext.h>
#include <string.h>
#include <time.h>
#include <tos.h>

int	total_files;
longint	total_compressed;
longint	total_uncompressed;

/*
 * SEE HOST OPERATING SYSTEM SPECIFICS SECTION STARTING NEAR LINE 180
 *
 */

/* ----------------------------------------------------------- */
/*
 * Zipfile layout declarations
 *
 */

typedef longint signature_type;

#define LOCAL_FILE_HEADER_SIGNATURE  0x04034b50L

typedef struct local_file_header {
	word version_needed_to_extract;
        word general_purpose_bit_flag;
	word compression_method;
	word last_mod_file_time;
	word last_mod_file_date;
	longint crc32;
	longint compressed_size;
        longint uncompressed_size;
	word filename_length;
	word extra_field_length;
} local_file_header;

#define CENTRAL_FILE_HEADER_SIGNATURE  0x02014b50L

typedef struct central_directory_file_header {
	word version_made_by;
	word version_needed_to_extract;
	word general_purpose_bit_flag;
	word compression_method;
	word last_mod_file_time;
	word last_mod_file_date;
	longint crc32;
	longint compressed_size;
	longint uncompressed_size;
	word filename_length;
	word extra_field_length;
	word file_comment_length;
	word disk_number_start;
	word internal_file_attributes;
	longint external_file_attributes;
	longint relative_offset_local_header;
} central_directory_file_header;

#define END_CENTRAL_DIR_SIGNATURE  0x06054b50L

typedef struct end_central_dir_record {
	word number_this_disk;
	word number_disk_with_start_central_directory;
	word total_entries_central_dir_on_this_disk;
	word total_entries_central_dir;
	longint size_central_directory;
	longint offset_start_central_directory;
	word zipfile_comment_length;
} end_central_dir_record;

/* ----------------------------------------------------------- */
/*
 * input file variables
 *
 */

#define INBUFSIZ 0x2000
byte *inbuf;			/* input file buffer - any size is legal */
byte *inptr;

int incnt;
unsigned bitbuf;
int bits_left;
boolean zipeof;

int zipfd;
char zipfn[STRSIZ];
char zipdir[STRSIZ];
local_file_header lrec;

int w0, w1;			/* word translation indices */
int li0, li1, li2, li3;		/* long int translation indices */

/* ----------------------------------------------------------- */
/*
 * output stream variables
 *
 */

#define OUTBUFSIZ 0x2000        /* must be 0x2000 or larger for unImplode */
byte *outbuf;                   /* buffer for rle look-back */
byte *outptr;

longint outpos;			/* absolute position in outfile */
int outcnt;			/* current position in outbuf */

int outfd;
char filename[STRSIZ];
char outfilename[STRSIZ];
char extra[STRSIZ];

#define DLE 144

/* ----------------------------------------------------------- */
/*
 * shrink/reduce working storage
 *
 */

int factor;
byte followers[256][64];
byte Slen[256];

#define max_bits 13
#define init_bits 9
#define hsize 8192
#define first_ent 257
#define clear 256

typedef int hsize_array_integer[hsize+1];
typedef byte hsize_array_byte[hsize+1];

hsize_array_integer prefix_of;
hsize_array_byte suffix_of;
hsize_array_byte stack;

int codesize;
int maxcode;
int free_ent;
int maxcodemax;
int offset;
int sizex;

/* ============================================================= */
/*
 * Host operating system details
 *
 */

void set_file_time(VOIDARG)
 /*
  * set the output file date/time stamp according to information from the
  * zipfile directory record for this file 
  */
{
	union {
                struct ftime ft;        /* system file time record */
		struct {
                        word ztime;     /* date and time words */
                        word zdate;     /* .. same format as in .ZIP file */
		} zt;
	} td;

	/*
	 * set output file date and time - this is optional and can be
	 * deleted if your compiler does not easily support setftime() 
	 */
	td.zt.ztime = lrec.last_mod_file_time;
	td.zt.zdate = lrec.last_mod_file_date;

	setftime (outfd, &td.ft);
}


int create_output_file(VOIDARG)
 /* return non-0 if creat failed */
{
	/* create the output file with READ and WRITE permissions */
	outfd = creat(outfilename, S_IWRITE | S_IREAD | (S_IREAD >> 3)
			| (S_IREAD >> 6));
	if (outfd < 1) {
		printf("Can't create output: %s\n", outfilename);
		return 1;
	}

	/*
	 * close the newly created file and reopen it in BINARY mode to
	 * disable all CR/LF translations 
	 */
	close(outfd);
	outfd = open(outfilename, O_RDWR | O_BINARY);

	/* write a single byte at EOF to pre-allocate the file */
        lseek(outfd, lrec.uncompressed_size - 1L, SEEK_SET);
	write(outfd, "?", 1);
	lseek(outfd, 0L, SEEK_SET);
	return 0;
}


int open_input_file(VOIDARG)
 /* return non-0 if open failed */
{
	/*
	 * open the zipfile for reading and in BINARY mode to prevent cr/lf
	 * translation, which would corrupt the bitstreams 
	 */

	zipfd = open(zipfn, O_RDONLY | O_BINARY);

	if (zipfd < 1)
	{
		printf("Can't open input file: %s\n", zipfn);
		return (1);
	}

	return 0;
}


void swap_bytes(word *wordp)
 /* convert intel style 'short int' variable to host format */
{
	char *charp = (char *) wordp;
	char temp[2];

	temp[0] = charp[w0];
	temp[1] = charp[w1];
	charp[0] = temp[0];
	charp[1] = temp[1];
}

void swap_lbytes(longint *longp)
 /* convert intel style 'long' variable to host format */
{
	char *charp = (char *) longp;
	char temp[4];

	temp[0] = charp[li0];
	temp[1] = charp[li1];
	temp[2] = charp[li2];
	temp[3] = charp[li3];
	charp[0] = temp[0];
	charp[1] = temp[1];
	charp[2] = temp[2];
	charp[3] = temp[3];
}

/* ============================================================= */

int FillBuffer(VOIDARG)
 /* fill input buffer if possible */
{
	int readsize;

        if (lrec.compressed_size <= 0)
		return incnt = 0;

        if (lrec.compressed_size > INBUFSIZ)
		readsize = INBUFSIZ;
	else
                readsize = (int) lrec.compressed_size;
	incnt = (int) read(zipfd, inbuf, readsize);

        lrec.compressed_size -= incnt;
	inptr = inbuf;
	return incnt--;
}

int ReadByte(unsigned *x)
 /* read a byte; return 8 if byte available, 0 if not */
{
	if (incnt-- == 0)
		if (FillBuffer() == 0)
			return 0;

	*x = *inptr++;
	return 8;
}

/* ------------------------------------------------------------- */
static unsigned mask_bits[] =
        {0,     0x0001, 0x0003, 0x0007, 0x000f,
                0x001f, 0x003f, 0x007f, 0x00ff,
                0x01ff, 0x03ff, 0x07ff, 0x0fff,
                0x1fff, 0x3fff, 0x7fff, 0xffff
        };


int FillBitBuffer(register int bits)
 /* read a byte; return 8 if byte available, 0 if not */
{
	/* get the bits that are left and read the next word */
	unsigned temp;
        register int result = bitbuf;
	int sbits = bits_left;
	bits -= bits_left;

	/* read next word of input */
	bits_left = ReadByte(&bitbuf);
	bits_left += ReadByte(&temp);
	bitbuf |= (temp << 8);
	if (bits_left == 0)
		zipeof = 1;

	/* get the remaining bits */
        result = result | (int) ((bitbuf & mask_bits[bits]) << sbits);
        bitbuf >>= bits;
        bits_left -= bits;
        return result;
}

#define READBIT(nbits,zdest,ztype) \
	{ if (nbits <= bits_left) \
		{ zdest = ztype(bitbuf & mask_bits[nbits]); \
		bitbuf >>= nbits; bits_left -= nbits; } \
	else zdest = ztype(FillBitBuffer(nbits));}

/*
 * macro READBIT(nbits,zdest,ztype)
 *  {
 *      if (nbits <= bits_left) {
 *          zdest = ztype(bitbuf & mask_bits[nbits]);
 *          bitbuf >>= nbits;
 *          bits_left -= nbits;
 *      } else
 *          zdest = ztype(FillBitBuffer(nbits));
 *  }
 *
 */

/* ------------------------------------------------------------- */

#include "crc32.h"

/* ------------------------------------------------------------- */

void FlushOutput(VOIDARG)
 /* flush contents of output buffer */
{
	UpdateCRC(outbuf, outcnt);
	write(outfd, outbuf, outcnt);
	outpos += outcnt;
	outcnt = 0;
	outptr = outbuf;
}

#define OUTB(intc) { *outptr++=intc; if (++outcnt==OUTBUFSIZ) FlushOutput(); }

/*
 *  macro OUTB(intc)
 *  {
 *      *outptr++=intc;
 *      if (++outcnt==OUTBUFSIZ)
 *          FlushOutput();
 *  }
 *
 */

/* ----------------------------------------------------------- */

void LoadFollowers(VOIDARG)
{
        register int x;
        register int i;

	for (x = 255; x >= 0; x--) {
                READBIT(6,Slen[x],(byte));
		for (i = 0; i < Slen[x]; i++) {
                        READBIT(8,followers[x][i],(byte));
		}
	}
}

/* ----------------------------------------------------------- */
/*
 * The Reducing algorithm is actually a combination of two
 * distinct algorithms.  The first algorithm compresses repeated
 * byte sequences, and the second algorithm takes the compressed
 * stream from the first algorithm and applies a probabilistic
 * compression method.
 */

int L_table[] = {0, 0x7f, 0x3f, 0x1f, 0x0f};

int D_shift[] = {0, 0x07, 0x06, 0x05, 0x04};
int D_mask[]  = {0, 0x01, 0x03, 0x07, 0x0f};

int B_table[] = {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
		 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
		 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
		 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
		 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		 8, 8, 8, 8};

/* ----------------------------------------------------------- */

void unReduce(VOIDARG)
 /* expand probablisticly reduced data */
{
        register int lchar;
        int nchar;
        int ExState;
        int V;
        int Len;

        factor = lrec.compression_method - 1;
	ExState = 0;
	lchar = 0;
	LoadFollowers();

        while (((outpos+outcnt) < lrec.uncompressed_size) && (!zipeof)) {
		if (Slen[lchar] == 0)
                        READBIT(8,nchar,(int))      /* ; */
                else
		{
                        READBIT(1,nchar,(int));
                        if (nchar != 0)
                                READBIT(8,nchar,(int))      /* ; */
                        else
			{
                                int follower;
                                int bitsneeded = B_table[Slen[lchar]];
                                READBIT(bitsneeded,follower,(int));
                                nchar = followers[lchar][follower];
			}
		}

		/* expand the resulting byte */
		switch (ExState) {

		case 0:
                        if (nchar != DLE)
                                OUTB((byte) nchar) /*;*/
			else
				ExState = 1;
			break;

		case 1:
                        if (nchar != 0) {
                                V = nchar;
				Len = V & L_table[factor];
				if (Len == L_table[factor])
					ExState = 2;
				else
					ExState = 3;
			}
			else {
                                OUTB(DLE);
				ExState = 0;
			}
			break;

                case 2: {
                                Len += nchar;
				ExState = 3;
			}
			break;

                case 3: {
				register int i = Len + 3;
				int offset = (((V >> D_shift[factor]) &
                                          D_mask[factor]) << 8) + nchar + 1;
                                longint op = (outpos+outcnt) - offset;

				/* special case- before start of file */
				while ((op < 0L) && (i > 0)) {
					OUTB(0);
					op++;
					i--;
				}

				/* normal copy of data from output buffer */
				{
					register int ix = (int) (op % OUTBUFSIZ);

                                        /* do a block memory copy if possible */
                                        if ( ((ix    +i) < OUTBUFSIZ) &&
                                             ((outcnt+i) < OUTBUFSIZ) ) {
                                                memcpy(outptr,&outbuf[ix],i);
                                                outptr += i;
                                                outcnt += i;
                                        }

                                        /* otherwise copy byte by byte */
                                        else while (i--) {
                                                OUTB(outbuf[ix]);
                                                if (++ix >= OUTBUFSIZ)
                                                        ix = 0;
                                        }
                                }

				ExState = 0;
			}
			break;
		}

                /* store character for next iteration */
                lchar = nchar;
        }
}

/* ------------------------------------------------------------- */
/*
 * Shrinking is a Dynamic Ziv-Lempel-Welch compression algorithm
 * with partial clearing.
 *
 */

void partial_clear(VOIDARG)
{
        register int pr;
        register int cd;

	/* mark all nodes as potentially unused */
	for (cd = first_ent; cd < free_ent; cd++)
		prefix_of[cd] |= 0x8000;

	/* unmark those that are used by other nodes */
	for (cd = first_ent; cd < free_ent; cd++) {
		pr = prefix_of[cd] & 0x7fff;	/* reference to another node? */
                if (pr >= first_ent)            /* flag node as referenced */
			prefix_of[pr] &= 0x7fff;
	}

	/* clear the ones that are still marked */
	for (cd = first_ent; cd < free_ent; cd++)
		if ((prefix_of[cd] & 0x8000) != 0)
			prefix_of[cd] = -1;

	/* find first cleared node as next free_ent */
        cd = first_ent;
        while ((cd < maxcodemax) && (prefix_of[cd] != -1))
                cd++;
        free_ent = cd;
}

/* ------------------------------------------------------------- */

void unShrink(VOIDARG)
{
#define  GetCode(dest) READBIT(codesize,dest,(int))

	register int code;
	register int stackp;
	int finchar;
	int oldcode;
	int incode;

	/* decompress the file */
	maxcodemax = 1 << max_bits;
	codesize = init_bits;
	maxcode = (1 << codesize) - 1;
	free_ent = first_ent;
	offset = 0;
	sizex = 0;

	for (code = maxcodemax; code > 255; code--)
		prefix_of[code] = -1;

	for (code = 255; code >= 0; code--) {
		prefix_of[code] = 0;
		suffix_of[code] = (byte) code;
	}

	GetCode(oldcode);
	if (zipeof)
		return;
	finchar = oldcode;

        OUTB((byte) finchar);

        stackp = hsize;

	while (!zipeof) {
		GetCode(code);
		if (zipeof)
			return;

		while (code == clear) {
			GetCode(code);
			switch (code) {

			case 1:{
					codesize++;
					if (codesize == max_bits)
						maxcode = maxcodemax;
					else
						maxcode = (1 << codesize) - 1;
				}
				break;

			case 2:
				partial_clear();
				break;
			}

			GetCode(code);
			if (zipeof)
				return;
		}


		/* special case for KwKwK string */
		incode = code;
		if (prefix_of[code] == -1) {
                        stack[--stackp] = (byte) finchar;
			code = oldcode;
		}


		/* generate output characters in reverse order */
		while (code >= first_ent) {
                        stack[--stackp] = suffix_of[code];
			code = prefix_of[code];
		}

		finchar = suffix_of[code];
                stack[--stackp] = (byte) finchar;


                /* and put them out in forward order, block copy */
                if ((hsize-stackp+outcnt) < OUTBUFSIZ) {
                        memcpy(outptr,&stack[stackp],hsize-stackp);
                        outptr += hsize-stackp;
                        outcnt += hsize-stackp;
                        stackp = hsize;
                }

                /* output byte by byte if we can't go by blocks */
                else while (stackp < hsize)
                        OUTB(stack[stackp++]);


		/* generate new entry */
		code = free_ent;
		if (code < maxcodemax) {
			prefix_of[code] = oldcode;
			suffix_of[code] = (byte) finchar;

			do
				code++;
			while ((code < maxcodemax) && (prefix_of[code] != -1));

			free_ent = code;
		}

		/* remember previous code */
		oldcode = incode;
	}

}

/* ------------------------------------------------------------- */ 
/*
 * Imploding
 * ---------
 *
 * The Imploding algorithm is actually a combination of two distinct
 * algorithms.  The first algorithm compresses repeated byte sequences
 * using a sliding dictionary.  The second algorithm is used to compress
 * the encoding of the sliding dictionary ouput, using multiple
 * Shannon-Fano trees.
 *
 */ 

#define maxSF 256

   typedef struct sf_entry { 
                 word         Code; 
                 byte         Value; 
                 byte         BitLength; 
              } sf_entry; 

   typedef struct sf_tree {   /* a shannon-fano tree */ 
      sf_entry     entry[maxSF];
      int          entries;
      int          MaxLength;
   } sf_tree; 

   typedef sf_tree      *sf_treep; 

   sf_tree      lit_tree; 
   sf_tree      length_tree; 
   sf_tree      distance_tree; 
   boolean      lit_tree_present; 
   boolean      eightK_dictionary; 
   int          minimum_match_length;
   int          dict_bits;


void SortLengths(sf_tree *tree)
  /* Sort the Bit Lengths in ascending order, while retaining the order
    of the original lengths stored in the file */ 
{ 
   int          x;
   int          gap;
   sf_entry     t; 
   boolean      noswaps;
   int          a, b;

   gap = tree->entries / 2; 

   do { 
      do { 
         noswaps = 1;
         for (x = 0; x <= (tree->entries - 1) - gap; x++) 
         { 
            a = tree->entry[x].BitLength; 
            b = tree->entry[x + gap].BitLength; 
            if ((a > b) || ((a == b) && (tree->entry[x].Value > tree->entry[x + gap].Value))) 
            { 
               t = tree->entry[x]; 
               tree->entry[x] = tree->entry[x + gap]; 
               tree->entry[x + gap] = t; 
               noswaps = 0;
            } 
         } 
      }  while (!noswaps);

      gap = gap / 2; 
   }  while (gap > 0);
} 


/* ----------------------------------------------------------- */ 

void ReadLengths(sf_tree *tree)
{ 
   int          treeBytes;
   int          i;
   int          num, len;

  /* get number of bytes in compressed tree */
   READBIT(8,treeBytes,(int));
   treeBytes++; 
   i = 0; 

   tree->MaxLength = 0;

 /* High 4 bits: Number of values at this bit length + 1. (1 - 16)
    Low  4 bits: Bit Length needed to represent value + 1. (1 - 16) */
   while (treeBytes > 0)
   {
      READBIT(4,len,(int)); len++;
      READBIT(4,num,(int)); num++;

      while (num > 0)
      {
         if (len > tree->MaxLength)
            tree->MaxLength = len;
         tree->entry[i].BitLength = (byte) len;
         tree->entry[i].Value = (byte) i;
         i++;
         num--;
      }

      treeBytes--;
   } 
} 

/* ----------------------------------------------------------- */ 

void GenerateTrees(sf_tree *tree)
     /* Generate the Shannon-Fano trees */ 
{ 
   word         Code;
   int          CodeIncrement;
   int          LastBitLength;
   int          i;


   Code = 0;
   CodeIncrement = 0; 
   LastBitLength = 0; 

   i = tree->entries - 1;   /* either 255 or 63 */ 
   while (i >= 0) 
   { 
      Code += CodeIncrement; 
      if (tree->entry[i].BitLength != (byte) LastBitLength) 
      { 
         LastBitLength = tree->entry[i].BitLength; 
         CodeIncrement = 1 << (16 - LastBitLength); 
      } 

      tree->entry[i].Code = Code; 
      i--; 
   } 
} 

/* ----------------------------------------------------------- */ 

void ReverseBits(sf_tree *tree)
 /* Reverse the order of all the bits in the above ShannonCode[]
    vector, so that the most significant bit becomes the least
    significant bit. For example, the value 0x1234 (hex) would become
    0x2C48 (hex). */ 
{ 
   int          i;
   word         mask;
   word         revb;
   word         v;
   word         o;
   int          b;


   for (i = 0; i <= tree->entries - 1; i++) 
   { 
        /* get original code */ 
      o = tree->entry[i].Code; 

        /* reverse each bit */ 
      mask = 0x0001;
      revb = 0x8000;
      v = 0;
      for (b = 0; b <= 15; b++) 
      { 
           /* if bit set in mask, then substitute reversed bit */ 
         if ((o & mask) != 0) 
            v = v | revb; 

           /* advance to next bit */ 
         revb = (revb >> 1);
         mask = (mask << 1);
      } 

        /* store reversed bits */ 
      tree->entry[i].Code = v; 
   } 
} 

/* ----------------------------------------------------------- */ 

void LoadTree(sf_tree *tree, int treesize)
     /* allocate and load a shannon-fano tree from the compressed file */ 
{ 
   tree->entries = treesize; 
   ReadLengths(tree); 
   SortLengths(tree); 
   GenerateTrees(tree); 
   ReverseBits(tree); 
} 

/* ----------------------------------------------------------- */ 

void LoadTrees(void)
{ 
   /* bit 1... */
   eightK_dictionary = (boolean) ((lrec.general_purpose_bit_flag & 0x02) != 0);
   /* bit 2... */
   lit_tree_present = (boolean) ((lrec.general_purpose_bit_flag & 0x04) != 0);

   if (eightK_dictionary) 
      dict_bits = 7;
   else 
      dict_bits = 6; 

   if (lit_tree_present) 
   { 
      minimum_match_length = 3; 
      LoadTree(&lit_tree,256); 
   } 
   else 
      minimum_match_length = 2; 

   LoadTree(&length_tree,64); 
   LoadTree(&distance_tree,64); 
} 

/* ----------------------------------------------------------- */ 

void ReadTree(sf_tree *tree, int *dest)
     /* read next byte using a shannon-fano tree */ 
{ 
   int          bits = 0;
   word         cv = 0;
   int          cur = 0;
   int          b;

   *dest = -1;   /* in case of error */ 

   for (;;)
   { 
      READBIT(1,b,(int));
      cv = cv | (b << bits);
      bits++; 

      /* this is a very poor way of decoding shannon-fano.  two quicker
         methods come to mind:
            a) arrange the tree as a huffman-style binary tree with
               a "leaf" indicator at each node,
         and
            b) take advantage of the fact that s-f codes are at most 8
               bits long and alias unused codes for all bits following
               the "leaf" bit.
      */

      while (tree->entry[cur].BitLength < (byte) bits) 
      { 
         cur++; 
         if (cur >= tree->entries) 
            return; /* data error */
      } 

      while (tree->entry[cur].BitLength == (byte) bits) 
      { 
         if (tree->entry[cur].Code == cv) 
         { 
            *dest = tree->entry[cur].Value; 
            return; 
         } 

         cur++; 
         if (cur >= tree->entries) 
            return; /* data error */
      } 
   } 
} 

/* ----------------------------------------------------------- */ 

void unImplode(void)
     /* expand imploded data */ 
{ 
   int          lout;
   longint      op;
   int          Length;
   int          Distance;

   LoadTrees(); 

   while ((!zipeof) && ((outpos+outcnt) < lrec.uncompressed_size))
   { 
      READBIT(1,lout,(int));

      if (lout != 0)   /* encoded data is literal data */ 
      { 
         if (lit_tree_present)  /* use Literal Shannon-Fano tree */
            ReadTree(&lit_tree,&lout);
         else 
            READBIT(8,lout,(int));

         OUTB((byte) lout);
      } 
      else             /* encoded data is sliding dictionary match */
      {                
         READBIT(dict_bits,lout,(int));
         Distance = lout; 

         ReadTree(&distance_tree,&lout); 
         Distance |= (lout << dict_bits);
         /* using the Distance Shannon-Fano tree, read and decode the
            upper 6 bits of the Distance value */ 

         ReadTree(&length_tree,&Length); 
         /* using the Length Shannon-Fano tree, read and decode the
            Length value */

         Length += minimum_match_length; 
         if (Length == (63 + minimum_match_length)) 
         { 
            READBIT(8,lout,(int));
            Length += lout; 
         } 

        /* move backwards Distance+1 bytes in the output stream, and copy
          Length characters from this position to the output stream.
          (if this position is before the start of the output stream,
          then assume that all the data before the start of the output
          stream is filled with zeros) */ 

         op = (outpos+outcnt) - Distance - 1L;

          /* special case- before start of file */
          while ((op < 0L) && (Length > 0)) {
                  OUTB(0);
                  op++;
                  Length--;
          }

          /* normal copy of data from output buffer */
          {
                  register int ix = (int) (op % OUTBUFSIZ);

		  while (Length--) {
                          OUTB(outbuf[ix]);
                          if (++ix >= OUTBUFSIZ)
                                  ix = 0;
                  }
         }
      } 
   } 
} 

/* ---------------------------------------------------------- */

void extract_member(VOIDARG)
{
        unsigned b;

	bits_left = 0;
	bitbuf = 0;
	incnt = 0;
	outpos = 0L;
	outcnt = 0;
	outptr = outbuf;
	zipeof = 0;
	crc32val = 0xFFFFFFFFL;


	/* create the output file with READ and WRITE permissions */
	if (create_output_file())
	{
		free (inbuf); free (outbuf);
		exit(1);
	}

        switch (lrec.compression_method) {

	case 0:		/* stored */
		{
			printf(" Extracting: %-12s ", filename);
			while (ReadByte(&b))
				OUTB((byte) b);
		}
		break;

        case 1: {
			printf("UnShrinking: %-12s ", filename);
			unShrink();
		}
		break;

	case 2:
	case 3:
	case 4:
        case 5: {
			printf("  Expanding: %-12s ", filename);
			unReduce();
		}
		break;

        case 6: {
                        printf("  Exploding: %-12s ", filename);
                        unImplode();
		}
		break;

        default:
		printf("Unknown compression method.");
	}


	/* write the last partial buffer, if any */
	if (outcnt > 0) {
		UpdateCRC(outbuf, outcnt);
		write(outfd, outbuf, outcnt);
	}

	/* set output file date and time */
	set_file_time();

	close(outfd);

	crc32val = -1 - crc32val;
        if (crc32val != lrec.crc32)
                printf(" Bad CRC %08lx  (should be %08lx)", lrec.crc32, crc32val);

	printf("\n");
}

/* ---------------------------------------------------------- */

void get_string(int len, char *s)
{
	read(zipfd, s, len);
	s[len] = 0;
}

/* ---------------------------------------------------------- */

void process_local_file_header(VOIDARG)
{
	if ((long) &lrec.crc32 ==
			(long) &lrec.last_mod_file_date
			+ sizeof(lrec.last_mod_file_date))
		read(zipfd, (char *) &lrec, sizeof(lrec));
	else {
		read(zipfd, (char *) &lrec, (unsigned)
			((long) &lrec.last_mod_file_date
			+ sizeof(lrec.last_mod_file_date)
			- (long) &lrec));
		read(zipfd, (char *) &lrec.crc32, (unsigned)
			((long) &lrec.extra_field_length
			+ sizeof(lrec.extra_field_length)
			- (long) &lrec.crc32));
	}

	swap_bytes(&lrec.version_needed_to_extract);
	swap_bytes(&lrec.general_purpose_bit_flag);
	swap_bytes(&lrec.compression_method);
	swap_bytes(&lrec.last_mod_file_time);
	swap_bytes(&lrec.last_mod_file_date);
	swap_lbytes(&lrec.crc32);
	swap_lbytes(&lrec.compressed_size);
	swap_lbytes(&lrec.uncompressed_size);
	swap_bytes(&lrec.filename_length);
	swap_bytes(&lrec.extra_field_length);

	get_string(lrec.filename_length, filename);
	get_string(lrec.extra_field_length, extra);

	strcpy (outfilename, zipdir);
	strcat (outfilename, filename);
}

/* ---------------------------------------------------------- */

void process_central_file_header(VOIDARG)
{
	central_directory_file_header rec;
	char filename[STRSIZ];
	char extra[STRSIZ];
	char *comment_p;

	if ((long) &rec.external_file_attributes ==
			(long) &rec.internal_file_attributes
			+ sizeof(rec.internal_file_attributes))
		read(zipfd, (char *) &rec, sizeof(rec));
	else {
		read(zipfd, (char *) &rec, (unsigned)
			((long) &rec.internal_file_attributes
			+ sizeof(rec.internal_file_attributes)
			- (long) &rec));
		read(zipfd, (char *) &rec.external_file_attributes, (unsigned)
			((long) &rec.relative_offset_local_header
			+ sizeof(rec.relative_offset_local_header)
			- (long) &rec.external_file_attributes));
	}

	swap_bytes(&rec.version_made_by);
	swap_bytes(&rec.version_needed_to_extract);
	swap_bytes(&rec.general_purpose_bit_flag);
	swap_bytes(&rec.compression_method);
	swap_bytes(&rec.last_mod_file_time);
	swap_bytes(&rec.last_mod_file_date);
	swap_lbytes(&rec.crc32);
	swap_lbytes(&rec.compressed_size);
	swap_lbytes(&rec.uncompressed_size);
	swap_bytes(&rec.filename_length);
	swap_bytes(&rec.extra_field_length);
	swap_bytes(&rec.file_comment_length);
	swap_bytes(&rec.disk_number_start);
	swap_bytes(&rec.internal_file_attributes);
	swap_lbytes(&rec.external_file_attributes);
	swap_lbytes(&rec.relative_offset_local_header);

        get_string(rec.filename_length, filename);
	get_string(rec.extra_field_length, extra);

	if (rec.file_comment_length > 0)
	{
		comment_p = (char *) (malloc (rec.file_comment_length));

		if (comment_p == NULL)
		{
			printf ("Can't allocate zipfile comment buffer!\n");
			free (comment_p); free (inbuf); free (outbuf);
			exit(1);
		}

		get_string (rec.file_comment_length, comment_p);
		printf ("%s\n", comment_p);
		free (comment_p);
	}
}

/* ---------------------------------------------------------- */

void process_end_central_dir(VOIDARG)
{
	end_central_dir_record rec;
	char *comment_p;

	read(zipfd, (char *) &rec, sizeof(rec));

	swap_bytes(&rec.number_this_disk);
	swap_bytes(&rec.number_disk_with_start_central_directory);
	swap_bytes(&rec.total_entries_central_dir_on_this_disk);
	swap_bytes(&rec.total_entries_central_dir);
	swap_lbytes(&rec.size_central_directory);
	swap_lbytes(&rec.offset_start_central_directory);
	swap_bytes(&rec.zipfile_comment_length);

	if (rec.zipfile_comment_length > 0)
	{
		comment_p = (char *) (malloc (rec.zipfile_comment_length));

		if (comment_p == NULL)
		{
			printf ("Can't allocate zipfile comment buffer!\n");
			free (comment_p); free (inbuf); free (outbuf);
			exit(1);
		}

		get_string (rec.zipfile_comment_length, comment_p);
		printf ("%s\n", comment_p);
		free (comment_p);
	}
}

/* ---------------------------------------------------------- */

void process_headers(VOIDARG)
{
	longint sig;

	while (1) {
		if (read(zipfd, (char *) &sig, sizeof(sig)) != sizeof(sig))
			return;

		swap_lbytes(&sig);

                if (sig == LOCAL_FILE_HEADER_SIGNATURE)
		{
			process_local_file_header();
			extract_member ();
		}
                else if (sig == CENTRAL_FILE_HEADER_SIGNATURE)
			process_central_file_header();
                else if (sig == END_CENTRAL_DIR_SIGNATURE) {
			process_end_central_dir();
			return;
		}
                else {
			printf("Invalid Zipfile Header (0x%.8lx)\n", sig);
			return;
		}
	}

}

/* ---------------------------------------------------------- */

char months [12][4] = { "Jan", "Feb", "Mar", "Apr", "May", "Jun",
			"Jul", "Aug", "Sep", "Oct", "Nov", "Dec" };

void verbose_member (VOIDARG)
{
	double comp_fact;
	char stowage [9];
	union {
                struct ftime ft;        /* system file time record */
		struct {
                        word ztime;     /* date and time words */
                        word zdate;     /* .. same format as in .ZIP file */
		} zt;
	} td;

	td.zt.ztime = lrec.last_mod_file_time;
	td.zt.zdate = lrec.last_mod_file_date;

	comp_fact = 100.0
		- ((lrec.compressed_size * 100.0) / lrec.uncompressed_size);

        switch (lrec.compression_method)
	{
		case 0:
			strcpy (stowage, "Stored  ");
			break;

	        case 1:
			strcpy (stowage, "Shrunk  ");
			break;

		case 2: case 3: case 4: case 5:
			strcpy (stowage, "Reduced ");
			break;

		case 6:
			strcpy (stowage, "Imploded");
			break;

		default:
			strcpy (stowage, "Unknown ");
			break;
	}

	printf ("%-12s  %8ld  %-8s   %2.0f%%  %8ld  %02d %3s %2d  %02d:%02d   %08lX\n",
		filename, lrec.uncompressed_size, stowage,
		comp_fact, lrec.compressed_size,
		td.ft.ft_day, months [td.ft.ft_month - 1], td.ft.ft_year + 80,
		td.ft.ft_hour, td.ft.ft_min, lrec.crc32);

	total_files ++;
	total_compressed += lrec.compressed_size;
	total_uncompressed += lrec.uncompressed_size;

	lseek (zipfd, lrec.compressed_size, SEEK_CUR);
}

/* ---------------------------------------------------------- */

void verbose_process_headers (VOIDARG)
{
	longint sig;

	while (1) {
		if (read (zipfd, (char *) &sig, sizeof(sig)) != sizeof(sig))
			return;

		swap_lbytes (&sig);

                if (sig == LOCAL_FILE_HEADER_SIGNATURE)
		{
			process_local_file_header();
			verbose_member ();
		}
                else if (sig == CENTRAL_FILE_HEADER_SIGNATURE)
			process_central_file_header();
                else if (sig == END_CENTRAL_DIR_SIGNATURE) {
			process_end_central_dir();
			return;
		}
                else {
			printf("Invalid Zipfile Header (0x%.8lx)\n", sig);
			return;
		}
	}

}

/* ---------------------------------------------------------- */

void extract_zipfile(VOIDARG)
{
	/*
	 * open the zipfile for reading and in BINARY mode to prevent cr/lf
	 * translation, which would corrupt the bitstreams 
	 */

	if (open_input_file())
	{
		free (inbuf); free (outbuf);
		exit(1);
	}
	{
		word w_sig;
		longint li_sig;
		char *bp, *bp0 = (char *)&li_sig, *bp3 = ((char *)&li_sig)+3;

		if (read(zipfd, (char *) &w_sig, 2) == 2)
			if (w_sig == (LOCAL_FILE_HEADER_SIGNATURE & 0xffff)) {
				w0 = 0;
				w1 = 1;
			} else {
				w0 = 1;
				w1 = 0;
			}
		lseek(zipfd, 0L, SEEK_SET);
		if (read(zipfd, (char *) &li_sig, 4) == 4)
			if (li_sig == LOCAL_FILE_HEADER_SIGNATURE) {
				li0 = 0;
				li1 = 1;
				li2 = 2;
				li3 = 3;
			} else {
				li0 = li1 = li2 = li3 = 0;
				for (bp = bp0; bp < bp3; ++bp, ++li0)
					if (*bp < 0x4b && !(*bp & 0x01))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li1)
					if (*bp < 0x4b && (*bp & 0x01))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li2)
					if (*bp == ((LOCAL_FILE_HEADER_SIGNATURE
							>> 8) & 0xffL))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li3)
					if (*bp == (LOCAL_FILE_HEADER_SIGNATURE
							& 0xffL))
						break;
			}
		lseek(zipfd, 0L, SEEK_SET);
	}

	process_headers();

	close(zipfd);
}

/* ---------------------------------------------------------- */

void verbose_zipfile (VOIDARG)
{
	double total_comp_fact;

	/*
	 * open the zipfile for reading and in BINARY mode to prevent cr/lf
	 * translation, which would corrupt the bitstreams 
	 */

	if (open_input_file())
	{
		free (inbuf); free (outbuf);
		exit(1);
	}
	{
		word w_sig;
		longint li_sig;
		char *bp;
		char *bp0 = (char *) &li_sig;
		char *bp3 = ((char *) &li_sig) + 3;

		if (read (zipfd, (char *) &w_sig, 2) == 2)
			if (w_sig == (LOCAL_FILE_HEADER_SIGNATURE & 0xffff))
			{
				w0 = 0;
				w1 = 1;
			}
			else
			{
				w0 = 1;
				w1 = 0;
			}

		lseek (zipfd, 0L, SEEK_SET);

		if (read (zipfd, (char *) &li_sig, 4) == 4)
			if (li_sig == LOCAL_FILE_HEADER_SIGNATURE)
			{
				li0 = 0;
				li1 = 1;
				li2 = 2;
				li3 = 3;
			}
			else
			{
				li0 = li1 = li2 = li3 = 0;
				for (bp = bp0; bp < bp3; ++bp, ++li0)
					if (*bp < 0x4b && !(*bp & 0x01))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li1)
					if (*bp < 0x4b && (*bp & 0x01))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li2)
					if (*bp == ((LOCAL_FILE_HEADER_SIGNATURE
							>> 8) & 0xffL))
						break;
				for (bp = bp0; bp < bp3; ++bp, ++li3)
					if (*bp == (LOCAL_FILE_HEADER_SIGNATURE
							& 0xffL))
						break;
			}

		lseek (zipfd, 0L, SEEK_SET);
	}

	printf ("\n");
	printf ("Name           Length   Stowage    SF   Size Now    Date      Time     CRC\n");
	printf ("============  ========  ========  ====  ========  =========  ======  ========\n");

	total_files = 0;
	total_uncompressed = 0;
	total_compressed = 0;

	verbose_process_headers ();

	total_comp_fact = 100.0
		- ((total_compressed * 100.0) / total_uncompressed);

	printf ("============  ========  ========  ====  ========  =========  ======  ========\n");
	printf ("Totals:%5d  %8ld             %2.0f%%  %8ld\n\n",
		total_files, total_uncompressed, total_comp_fact,
		total_compressed);

	close (zipfd);
}

void print_disclaimer (void)
{
	printf("\n%s\nCourtesy of:  S.H.Smith  and  The Tool Shop BBS,  (602) 279-2673.\n\n",VERSION);
	printf("You may copy and distribute this program freely, provided that:\n");
	printf("    1)   No fee is charged for such copying and distribution, and\n");
	printf("    2)   It is distributed ONLY in its original, unmodified state.\n\n");
	printf("If you wish to distribute a modified version of this program, you MUST\n");
	printf("include the source code.\n\n");
	printf("If you modify this program, I would appreciate a copy of the  new source\n");
	printf("code.   I am holding the copyright on the source code, so please don't\n");
	printf("delete my name from the program files or from the documentation.\n\n");
	printf("IN NO EVENT WILL I BE LIABLE TO YOU FOR ANY DAMAGES, INCLUDING ANY LOST\n");
	printf("PROFITS, LOST SAVINGS OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES\n");
	printf("ARISING OUT OF YOUR USE OR INABILITY TO USE THE PROGRAM, OR FOR ANY\n");
	printf("CLAIM BY ANY OTHER PARTY.\n\n");
	printf("ST Version 2.0.2 courtesy of William K. Day\n");
	printf("FNET Node 398     (708) 695-8617\n\n");
	printf("Usage: unzip.ttp [v | x] zipfile[.zip] [extractdir\\]\n\n");
	free (inbuf); free (outbuf);
	exit(1);
}

/* ---------------------------------------------------------- */

/*
 * main program
 *
 */

void main(int argc, char **argv)
{
	boolean	extract_flag;
	boolean	verbose_flag;
	char *tmp_ptr;

	if (argc < 3)
		print_disclaimer ();

	if (strcmp ("V", strupr (argv [1])) == 0)
	{
		verbose_flag = 1;
	}
	else
	if (strcmp ("X", strupr (argv [1])) == 0)
	{
		extract_flag = 1;
	}
	else
		print_disclaimer ();

	/* .ZIP default if none provided by user */
	strcpy (zipfn, argv [2]);

	if (strchr (zipfn, '.') == NULL)
		strcat (zipfn, ".zip");

	/* Check for presence of an extract directory */
	if ((argc == 4) && (extract_flag))
	{
		strcpy (zipdir, argv [3]);

		tmp_ptr = strrchr (zipdir, '\\') + 1;
		*tmp_ptr = '\0';
	}

        /* allocate i/o buffers */
	inbuf = (byte *) (malloc(INBUFSIZ));
	outbuf = (byte *) (malloc(OUTBUFSIZ));

	if ((inbuf == NULL) || (outbuf == NULL))
	{
		printf("Can't allocate buffers!\n");
		free (inbuf); free (outbuf);
		exit(1);
	}

        /* do the job... */
	if (extract_flag)
	        extract_zipfile ();
	else
	if (verbose_flag)
		verbose_zipfile ();

	free (inbuf); free (outbuf);
	exit (0);
}

