lzd.c

一个很好的压缩与解压程序

                                                  != outbufp - out_buf_adr)
         	prterror ('f', "Output error in lzd().\n");
         addbfcrc(out_buf_adr, outbufp - out_buf_adr);
      }
      return (0);
   }

   in_code = cur_code;              /* save original code */
   if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
      cur_code = old_code;             /* previous code becomes current */
                                       /* push first character of old code */
      *--stack_pointer = firstchar(old_code);
      goto unwind;                     /* and go "unwind" the current code */
   }              /* (use general unwind because the stack isn't empty now) */

/* Unwind a code.  The basic idea is to use a sort of loop-unrolling
** approach to really speed up the processing by treating the codes
** which represent short strings (the vast majority of codes) as
** special cases.  Avoid a lot of stack overflow checking safely.
*/

   if (cur_code > 255) {                  /* if cur_code is not atomic */
      *--stack_pointer = tail[cur_code];  /* push its tail code */
      cur_code = head[cur_code];          /* and replace with its head code */
   } else {                        /* else 1-byte string */
      if ( outbufp > outbufguard ) /* if outbuf near end, */
         goto write_stack;         /* write via general routine */
      *outbufp++ = cur_code;       /* we got space, put char out */
      goto add_code;               /* add code to table */
   }

   if (cur_code > 255) {                  /* if cur_code is not atomic */
      *--stack_pointer = tail[cur_code];  /* push its tail code */
      cur_code = head[cur_code];          /* and replace with its head code */
   } else {                        /* else 2-byte string */
      if ( outbufp > outbufguard ) /* if outbuf near end, */
         goto write_stack;         /* write via general routine */
      *outbufp++ = cur_code;       /* we got space, put char out, and */
      goto move_1_char;            /* go move rest of stack to outbuf */
   }
   if (cur_code > 255) {                  /* if cur_code is not atomic */
      *--stack_pointer = tail[cur_code];  /* push its tail code */
      cur_code = head[cur_code];          /* and replace with its head code */
   } else {                        /* else 3-byte string */
      if ( outbufp > outbufguard ) /* if outbuf near end, */
         goto write_stack;         /* write via general routine */
      *outbufp++ = cur_code;       /* we got space, put char out, and */
      goto move_2_char;            /* go move rest of stack to outbuf */
   }

/* we handle codes representing strings of 4 thru 8 bytes similarly */

   if (cur_code > 255) {
      *--stack_pointer = tail[cur_code];
      cur_code = head[cur_code];
   } else {                        /* 4-byte string */
      if ( outbufp > outbufguard )
         goto write_stack;
      *outbufp++ = cur_code;
      goto move_3_char;
   }
   if (cur_code > 255) {
      *--stack_pointer = tail[cur_code];
      cur_code = head[cur_code];
   } else {                        /* 5-byte string */
      if ( outbufp > outbufguard )
         goto write_stack;
      *outbufp++ = cur_code;
      goto move_4_char;
   }
   if (cur_code > 255) {
      *--stack_pointer = tail[cur_code];
      cur_code = head[cur_code];
   } else {                        /* 6-byte string */
      if ( outbufp > outbufguard )
         goto write_stack;
      *outbufp++ = cur_code;
      goto move_5_char;
   }
   if (cur_code > 255) {
      *--stack_pointer = tail[cur_code];
      cur_code = head[cur_code];
   } else {                        /* 7-byte string */
      if ( outbufp > outbufguard )
         goto write_stack;
      *outbufp++ = cur_code;
      goto move_6_char;
   }
   if (cur_code > 255) {
      *--stack_pointer = tail[cur_code];
      cur_code = head[cur_code];
   } else {                        /* 8-byte string */
      if ( outbufp > outbufguard )
         goto write_stack;
      *outbufp++ = cur_code;
      goto move_7_char;
   }

/* Here for KwKwK case and strings longer than 8 bytes */
/* Note we have to check stack here, but not elsewhere */

unwind:
   while (cur_code > 255) {               /* if code, not character */
      *--stack_pointer = tail[cur_code];         /* push suffix char */
      if (stack_pointer < stack+12)
         prterror ('f', "Stack overflow in lzd().\n");
      cur_code = head[cur_code];          /* head of code is new code */
   }

/* General routine to write stack with check for output buffer full */

write_stack:
   assert(nbits >= 9 && nbits <= 13);
   wr_dchar(cur_code);    /* write this code, don't need to stack it first */
   while ( stack_pointer < stack_lim ) {
      wr_dchar(*stack_pointer++);
   }
   goto add_code;                           /* now go add code to table */

/* Here to move strings from stack to output buffer */
/* only if we know we have enough room in output buffer */
/* because (outbufp <= outbufguard) */

move_7_char:
   *outbufp++ = *stack_pointer++;
move_6_char:
   *outbufp++ = *stack_pointer++;
move_5_char:
   *outbufp++ = *stack_pointer++;
move_4_char:
   *outbufp++ = *stack_pointer++;
move_3_char:
   *outbufp++ = *stack_pointer++;
move_2_char:
   *outbufp++ = *stack_pointer++;
move_1_char:
   *outbufp++ = *stack_pointer++;

assert(stack_pointer == stack_lim); /* I haven't tested this! rdg */

/* add_code is now inline to avoid overhead of function call on */
/*   each code processed */

add_code:
   assert(nbits >= 9 && nbits <= 13);
   assert(free_code <= MAXMAX+1);
   tail[free_code] = cur_code;                /* save suffix char */
   head[free_code] = old_code;                /* save prefix code */
   free_code++;
   assert(nbits >= 9 && nbits <= 13);
   if (free_code >= max_code) {
      if (nbits < MAXBITS) {
         debug((printf("lzd: nbits was %d\n", nbits)))
         nbits++;
         assert(nbits >= 9 && nbits <= 13);
         debug((printf("lzd: nbits now %d\n", nbits)))
         max_code = max_code << 1;        /* double max_code */
         debug((printf("lzd: max_code now %d\n", max_code)))
      }
   }
   old_code = in_code;

   assert(nbits >= 9 && nbits <= 13);

   goto loop;
} /* lzd() */

#else /* SLOW_LZD defined, so use following instead */

/*********************************************************************/
/* Original slower lzd().                                            */
/*********************************************************************/

/*
Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
code.  The contents of this file are hereby released to the public domain.
                                 -- Rahul Dhesi 1986/11/14
*/

#define  STACKSIZE   4000

struct tabentry {
   unsigned next;
   char z_ch;
};

void init_dtab PARMS((void));
unsigned rd_dcode PARMS((void));
void wr_dchar PARMS((int));
void ad_dcode PARMS((void));

#ifdef FILTER
/* to send data back to zoofilt */
extern unsigned int filt_lzd_word;
#endif /* FILTER */


static unsigned stack_pointer = 0;
static unsigned *stack;

#define  push(x)  {  \
                     stack[stack_pointer++] = (x);                   \
                     if (stack_pointer >= STACKSIZE)                 \
                        prterror ('f', "Stack overflow in lzd().\n");\
                  }
#define  pop()    (stack[--stack_pointer])

extern char *out_buf_adr;        /* output buffer */
extern char *in_buf_adr;         /* input buffer */

char memflag = 0;                /* memory allocated? flag */
extern struct tabentry *table;   /* hash table from lzc.c */
static unsigned cur_code;
static unsigned old_code;
static unsigned in_code;

static unsigned free_code;
static int nbits;
static unsigned max_code;

static char fin_char;
static char k;
static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
static unsigned bit_offset;
static unsigned output_offset;

#ifdef UNBUF_IO
#define		BLOCKFILE		int
#define		BLOCKREAD		read
#define		BLOCKWRITE		blockwrite
int read PARMS ((int, VOIDPTR, unsigned));
int write PARMS ((int, VOIDPTR, unsigned));
#else
#define		BLOCKFILE		ZOOFILE
#define		BLOCKREAD		zooread
#define		BLOCKWRITE		zoowrite
#endif /* UNBUF_IO */

static BLOCKFILE in_f, out_f; 

int lzd(input_f, output_f)
BLOCKFILE input_f, output_f;          /* input & output file handles */
{
   in_f = input_f;                 /* make it avail to other fns */
   out_f = output_f;               /* ditto */
   nbits = 9;
   max_code = 512;
   free_code = FIRST_FREE;
   stack_pointer = 0;
   bit_offset = 0;
   output_offset = 0;

   if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
      return(IOERR);
   if (memflag == 0) {
     table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
     stack = (unsigned *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
     memflag++;
   }

   init_dtab();             /* initialize table */

loop:
   cur_code = rd_dcode();
goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
   if (cur_code == Z_EOF) {
      debug((printf ("lzd: Z_EOF\n")))
      if (output_offset != 0) {
         if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
            prterror ('f', "Output error in lzd().\n");
         addbfcrc(out_buf_adr, output_offset);
      }
#ifdef FILTER
		/* get next two bytes and put them where zoofilt can find them */
		/* nbits known to be in range 9..13 */
		bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
		filt_lzd_word = rd_dcode();
		filt_lzd_word |= (rd_dcode() << nbits);
		filt_lzd_word &= 0xffff;
#endif
      return (0);
   }

   assert(nbits >= 9 && nbits <= 13);

   if (cur_code == CLEAR) {
      debug((printf ("lzd: CLEAR\n")))
      init_dtab();
      fin_char = k = old_code = cur_code = rd_dcode();
		if (cur_code == Z_EOF)		/* special case for 0-length files */
			goto goteof;
      wr_dchar(k);
      goto loop;
   }

   in_code = cur_code;
   if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
      cur_code = old_code;             /* previous code becomes current */
      push(fin_char);
   }

   while (cur_code > 255) {               /* if code, not character */
      push(table[cur_code].z_ch);         /* push suffix char */
      cur_code = table[cur_code].next;    /* <w> := <w>.code */
   }

   assert(nbits >= 9 && nbits <= 13);

   k = fin_char = cur_code;
   push(k);
   while (stack_pointer != 0) {
      wr_dchar(pop());
   }
   assert(nbits >= 9 && nbits <= 13);
   ad_dcode();
   old_code = in_code;

   assert(nbits >= 9 && nbits <= 13);

   goto loop;
} /* lzd() */

/* rd_dcode() reads a code from the input (compressed) file and returns
its value. */
unsigned rd_dcode()
{
   register char *ptra, *ptrb;    /* miscellaneous pointers */
   unsigned word;                     /* first 16 bits in buffer */
   unsigned byte_offset;
   char nextch;                           /* next 8 bits in buffer */
   unsigned ofs_inbyte;               /* offset within byte */

   ofs_inbyte = bit_offset % 8;
   byte_offset = bit_offset / 8;
   bit_offset = bit_offset + nbits;

   assert(nbits >= 9 && nbits <= 13);

   if (byte_offset >= INBUFSIZ - 5) {
      int space_left;

#ifdef CHECK_BREAK
	check_break();
#endif

      assert(byte_offset >= INBUFSIZ - 5);
      debug((printf ("lzd: byte_offset near end of buffer\n")))

      bit_offset = ofs_inbyte + nbits;
      space_left = INBUFSIZ - byte_offset;
      ptrb = byte_offset + in_buf_adr;          /* point to char */
      ptra = in_buf_adr;
      /* we now move the remaining characters down buffer beginning */
      debug((printf ("rd_dcode: space_left = %d\n", space_left)))
      while (space_left > 0) {
         *ptra++ = *ptrb++;
         space_left--;
      }
      assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
      assert(space_left == 0);
      if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
         prterror ('f', "I/O error in lzd:rd_dcode.\n");
      byte_offset = 0;
   }
   ptra = byte_offset + in_buf_adr;
   /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
   word = (unsigned char) *ptra; ptra++;
   word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;

   nextch = *ptra;
   if (ofs_inbyte != 0) {
      /* shift nextch right by ofs_inbyte bits */
      /* and shift those bits right into word; */
      word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
   }
   return (word & masks[nbits]); 
} /* rd_dcode() */

void init_dtab()
{
   nbits = 9;
   max_code = 512;
   free_code = FIRST_FREE;
}

void wr_dchar (ch)
int ch;
{
   if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
#ifdef CHECK_BREAK
	check_break();
#endif
      if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
         prterror ('f', "Write error in lzd:wr_dchar.\n");
      addbfcrc(out_buf_adr, output_offset);     /* update CRC */
      output_offset = 0;                  /* restore empty buffer */
   }
   assert(output_offset < OUTBUFSIZ);
   out_buf_adr[output_offset++] = ch;        /* store character */
} /* wr_dchar() */

/* adds a code to table */
void ad_dcode()
{
   assert(nbits >= 9 && nbits <= 13);
   assert(free_code <= MAXMAX+1);
   table[free_code].z_ch = k;                /* save suffix char */
   table[free_code].next = old_code;         /* save prefix code */
   free_code++;
   assert(nbits >= 9 && nbits <= 13);
   if (free_code >= max_code) {
      if (nbits < MAXBITS) {
         debug((printf("lzd: nbits was %d\n", nbits)))
         nbits++;
         assert(nbits >= 9 && nbits <= 13);
         debug((printf("lzd: nbits now %d\n", nbits)))
         max_code = max_code << 1;        /* double max_code */
         debug((printf("lzd: max_code now %d\n", max_code)))
      }
   }
}
#endif /* ! SLOW_LZD */