compapi.c

和Unix的compress/uncompress兼容的压缩/解压算法16位程序

 /*
   * Check the input stream for previously seen strings.  We keep
   * adding characters to the previously seen prefix string until we
   * get a character which forms a new (unseen) string.  We then send
   * the code for the previously seen prefix string, and add the new
   * string to our tables.  The check for previous strings is done by
   * hashing.  If the code for the hash value is unused, then we have
   * a new string.  If the code is used, we check to see if the prefix
   * and suffix values match the current input; if so, we have found
   * a previously seen string.  Otherwise, we have a hash collision,
   * and we try secondary hash probes until we either find the current
   * string, or we find an unused entry (which indicates a new string).
   */
    if (!nomagic) {
        putchar(magic_header[0]); putchar(magic_header[1]);
        putchar((char)(maxbits | block_compress));
        if(ferror(stdout)){  /* check it on entry */
            exit_stat = WRITEERR;
            return;
        }
        bytes_out = 3L;     /* includes 3-byte header mojo */
    }
    else
        bytes_out = 0L;      /* no 3-byte header mojo */
    in_count = 1L;
    offset = 0;

    if ((c = getchar()) == EOF) {
        exit_stat = ferror(stdin) ? READERR : OK;
        return;
    }
    prefxcode = (INTCODE)c;

    while ((c = getchar()) != EOF) {
        in_count++;
        hash = prefxcode ^ hashf[c];
        /* I need to check that my hash value is within range
        * because my 16-bit hash table is smaller than 64k.
        */
        if (hash >= hashsize)
            hash -= hashsize;
        if ((code = (INTCODE)probe(hash)) != UNUSED) {
            if (suffix(code) != (char)c || (INTCODE)prefix(code) != prefxcode) {
            /* hashdelta is subtracted from hash on each iteration of
            * the following hash table search loop.  I compute it once
            * here to remove it from the loop.
            */
                HASH hashdelta = (0x120 - c) << (adjbits);
                do  {
                    /* rehash and keep looking */
                    assert(code >= FIRSTFREE && code <= maxcode);
                    if (hash >= hashdelta) hash -= hashdelta;
                        else hash += (hashsize - hashdelta);
                    assert(hash < hashsize);
                    if ((code = (INTCODE)probe(hash)) == UNUSED)
                        goto newcode;
                } while (suffix(code) != (char)c || (INTCODE)prefix(code) != prefxcode);
            }
            prefxcode = code;
        }
        else {
            newcode: {
                putcode(prefxcode, bits);
                code = nextfree;
                assert(hash < hashsize);
                assert(code >= FIRSTFREE);
                assert(code <= maxcode + 1);
                if (code <= maxcode) {
                    probe(hash) = (CODE)code;
                    prefix(code) = (CODE)prefxcode;
                    suffix(code) = (char)c;
                    if (code > highcode) {
                        highcode += code;
                        ++bits;
                    }
                    nextfree = code + 1;
                }
#ifdef COMP40
                else if (in_count >= checkpoint && block_compress ) {
                    if (cl_block()){
#else
                else if (block_compress){
#endif
                        putcode((INTCODE)c, bits);
                        putcode(CLEAR, bits);
                        init_tables();
                        if ((c = getchar()) == EOF)
                            break;
                        in_count++;
#ifdef COMP40
                    }
#endif
                }
                prefxcode = (INTCODE)c;
            }
        }
    }
    putcode(prefxcode, bits);
    putcode(CLEAR, 0);
    if (ferror(stdout)){ /* check it on exit */
        exit_stat = WRITEERR;
        return;
    }
    /*
     * Print out stats on stderr
     */
    if(zcat_flg == 0 && !quiet) {
#ifdef DEBUG
        fprintf( stderr,
            "%ld chars in, (%ld bytes) out, compression factor: ",
            in_count, bytes_out );
        prratio( stderr, in_count, bytes_out );
        fprintf( stderr, "\n");
        fprintf( stderr, "\tCompression as in compact: " );
        prratio( stderr, in_count-bytes_out, in_count );
        fprintf( stderr, "\n");
        fprintf( stderr, "\tLargest code (of last block) was %d (%d bits)\n",
            prefxcode - 1, bits );
#else
        fprintf( stderr, "Compression: " );
        prratio( stderr, in_count-bytes_out, in_count );
#endif /* DEBUG */
    }
    if(bytes_out > in_count)      /*  if no savings */
        exit_stat = NOSAVING;
    return ;
}

CONST UCHAR rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

void putcode(code,bits)
  INTCODE code;
  register int bits;
{
  static int oldbits = 0;
  static UCHAR outbuf[MAXBITS];
  register UCHAR *buf;
  register int shift;

  if (bits != oldbits) {
    if (bits == 0) {
      /* bits == 0 means EOF, write the rest of the buffer. */
      if (offset > 0) {
          fwrite(outbuf,1,(offset +7) >> 3, stdout);
          bytes_out += ((offset +7) >> 3);
      }
      offset = 0;
      oldbits = 0;
      fflush(stdout);
      return;
    }
    else {
      /* Change the code size.  We must write the whole buffer,
       * because the expand side won't discover the size change
       * until after it has read a buffer full.
       */
      if (offset > 0) {
        fwrite(outbuf, 1, oldbits, stdout);
        bytes_out += oldbits;
        offset = 0;
      }
      oldbits = bits;
#ifdef DEBUG
      if ( debug )
        fprintf( stderr, "\nChange to %d bits\n", bits );
#endif /* DEBUG */
    }
  }
  /*  Get to the first byte. */
  buf = outbuf + ((shift = offset) >> 3);
  if ((shift &= 7) != 0) {
    *(buf) |= (*buf & rmask[shift]) | (UCHAR)(code << shift);
    *(++buf) = (UCHAR)(code >> (8 - shift));
    if (bits + shift > 16)
        *(++buf) = (UCHAR)(code >> (16 - shift));
  }
  else {
    /* Special case for fast execution */
    *(buf) = (UCHAR)code;
    *(++buf) = (UCHAR)(code >> 8);
  }
  if ((offset += bits) == (bits << 3)) {
    bytes_out += bits;
    fwrite(outbuf,1,bits,stdout);
    offset = 0;
  }
  return;
}

int nextcode(codeptr)
  INTCODE *codeptr;
/* Get the next code from input and put it in *codeptr.
 * Return (TRUE) on success, or return (FALSE) on end-of-file.
 * Adapted from COMPRESS V4.0.
 */
{
  static int prevbits = 0;
  register INTCODE code;
  static int size;
  static UCHAR inbuf[MAXBITS];
  register int shift;
  UCHAR *bp;

  /* If the next entry is a different bit-size than the preceeding one
   * then we must adjust the size and scrap the old buffer.
   */
  if (prevbits != bits) {
    prevbits = bits;
    size = 0;
  }
  /* If we can't read another code from the buffer, then refill it.
   */
  if (size - (shift = offset) < bits) {
    /* Read more input and convert size from # of bytes to # of bits */
    if ((size = fread(inbuf, 1, bits, stdin) << 3) <= 0 || ferror(stdin))
      return(NO);
    offset = shift = 0;
  }
  /* Get to the first byte. */
  bp = inbuf + (shift >> 3);
  /* Get first part (low order bits) */
  code = (*bp++ >> (shift &= 7));
  /* high order bits. */
  code |= *bp++ << (shift = 8 - shift);
  if ((shift += 8) < bits) code |= *bp << shift;
  *codeptr = code & highcode;
  offset += bits;
  return (TRUE);
}

void decompress()
{
  register int i;
  register INTCODE code;
  char sufxchar;
  INTCODE savecode;
  FLAG fulltable, cleartable;
  static char *token= NULL;         /* String buffer to build token */
  static int maxtoklen = MAXTOKLEN;

  exit_stat = OK;

  /* Initialze the token buffer. */
    if (token == NULL && (token = (char*)malloc(maxtoklen)) == NULL) {
    	    exit_stat = NOMEM;
    	    return;
	}

  if (alloc_tables(maxcode = ~(~(INTCODE)0 << maxbits),0)) /* exit_stat already set */
     return;

    /* if not zcat or filter */
    if(is_list && !zcat_flg) {  /* Open output file */
        if (freopen(ofname, WRITE_FILE_TYPE, stdout) == NULL) {
            exit_stat = NOTOPENED;
            return;
        }
        if (!quiet)
            fprintf(stderr, "%s: ",ifname);
        setvbuf(stdout,xbuf,_IOFBF,XBUFSIZE);
    }
  cleartable = TRUE;
  savecode = CLEAR;
  offset = 0;
  do {
    if ((code = savecode) == CLEAR && cleartable) {
      highcode = ~(~(INTCODE)0 << (bits = INITBITS));
      fulltable = FALSE;
      nextfree = (cleartable = block_compress) == FALSE ? 256 : FIRSTFREE;
      if (!nextcode(&prefxcode))
        break;
      putc((sufxchar = (char)prefxcode), stdout);
      continue;
    }
    i = 0;
    if (code >= nextfree && !fulltable) {
      if (code != nextfree){
        exit_stat = CODEBAD;
        return ;     /* Non-existant code */
    }
      /* Special case for sequence KwKwK (see text of article)         */
      code = prefxcode;
      token[i++] = sufxchar;
    }
    /* Build the token string in reverse order by chasing down through
     * successive prefix tokens of the current token.  Then output it.
     */
    while (code >= 256) {
#     ifdef DEBUG
        /* These are checks to ease paranoia. Prefix codes must decrease
         * monotonically, otherwise we must have corrupt tables.  We can
         * also check that we haven't overrun the token buffer.
         */
        if (code <= (INTCODE)prefix(code)){
            exit_stat= TABLEBAD;
            return;
        }
#     endif
      if (i >= maxtoklen) {
        maxtoklen *= 2;   /* double the size of the token buffer */
        if ((token = realloc(token, maxtoklen)) == NULL) {
          exit_stat = TOKTOOBIG;
          return;
        }
      }
      token[i++] = suffix(code);
      code = (INTCODE)prefix(code);
    }
    putc(sufxchar = (char)code, stdout);
    while (--i >= 0)
        putc(token[i], stdout);
    if (ferror(stdout)) {
        exit_stat = WRITEERR;
        return;
    }
    /* If table isn't full, add new token code to the table with
     * codeprefix and codesuffix, and remember current code.
     */
    if (!fulltable) {
      code = nextfree;
      assert(256 <= code && code <= maxcode);
      prefix(code) = (CODE)prefxcode;
      suffix(code) = sufxchar;
      prefxcode = savecode;
      if (code++ == highcode) {
        if (highcode >= maxcode) {
          fulltable = TRUE;
          --code;
        }
        else {
          ++bits;
          highcode += code;           /* nextfree == highcode + 1 */
        }
      }
      nextfree = code;
    }
  } while (nextcode(&savecode));
  exit_stat = (ferror(stdin))? READERR : OK;
  return ;
}