compapi.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 706 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


/*@H************************ < COMPRESS API    > ****************************
*                                                                           *
*   compress : compapi.c  <current version of compress algorithm>           *
*                                                                           *
*   port by  : Donald J. Gloistein                                          *
*                                                                           *
*   Source, Documentation, Object Code:                                     *
*   released to Public Domain.  This code is based on code as documented    *
*   below in release notes.                                                 *
*                                                                           *
*---------------------------  Module Description  --------------------------*
*   Contains source code for modified Lempel-Ziv method (LZW) compression   *
*   and decompression.                                                      *
*                                                                           *
*   This code module can be maintained to keep current on releases on the   *
*   Unix system. The command shell and dos modules can remain the same.     *
*                                                                           *
*--------------------------- Implementation Notes --------------------------*
*                                                                           *
*   compiled with : compress.h compress.fns compress.c                      *
*   linked with   : compress.obj compusi.obj                                *
*                                                                           *
*   problems:                                                               *
*                                                                           *
*                                                                           *
*   CAUTION: Uses a number of defines for access and speed. If you change   *
*            anything, make sure about side effects.                        *
*                                                                           *
* Compression:                                                              *
* Algorithm:  use open addressing double hashing (no chaining) on the       *
* prefix code / next character combination.  We do a variant of Knuth's     *
* algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime     *
* secondary probe.  Here, the modular division first probe is gives way     *
* to a faster exclusive-or manipulation.                                    *
* Also block compression with an adaptive reset was used in original code,  *
* whereby the code table is cleared when the compression ration decreases   *
* but after the table fills.  This was removed from this edition. The table *
* is re-sized at this point when it is filled , and a special CLEAR code is *
* generated for the decompressor. This results in some size difference from *
* straight version 4.0 joe Release. But it is fully compatible in both v4.0 *
* and v4.01                                                                 *
*                                                                           *
* Decompression:                                                            *
* This routine adapts to the codes in the file building the "string" table  *
* on-the-fly; requiring no table to be stored in the compressed file.  The  *
* tables used herein are shared with those of the compress() routine.       *
*                                                                           *
*     Initials ---- Name ---------------------------------                  *
*      DjG          Donald J. Gloistein, current port to MsDos 16 bit       *
*                   Plus many others, see rev.hst file for full list        *
*      LvR          Lyle V. Rains, many thanks for improved implementation  *
*                   of the compression and decompression routines.          *
*************************************************************************@H*/

#include <stdio.h>

#include "compress.h" /* contains the rest of the include file declarations */

static int offset;
static long int in_count ;         /* length of input */
static long int bytes_out;         /* length of compressed output */

static CODE prefxcode, nextfree;
static CODE highcode;
static CODE maxcode;
static HASH hashsize;
static int  bits;


/*
 * The following two parameter tables are the hash table sizes and
 * maximum code values for various code bit-lengths.  The requirements
 * are that Hashsize[n] must be a prime number and Maxcode[n] must be less
 * than Maxhash[n].  Table occupancy factor is (Maxcode - 256)/Maxhash.
 * Note:  I am using a lower Maxcode for 16-bit codes in order to
 * keep the hash table size less than 64k entries.
 */
CONST HASH hs[] = {
  0x13FF,       /* 12-bit codes, 75% occupancy */
  0x26C3,       /* 13-bit codes, 80% occupancy */
  0x4A1D,       /* 14-bit codes, 85% occupancy */
  0x8D0D,       /* 15-bit codes, 90% occupancy */
  0xFFD9        /* 16-bit codes, 94% occupancy, 6% of code values unused */
};
#define Hashsize(maxb) (hs[(maxb) -MINBITS])

CONST CODE mc[] = {
  0x0FFF,       /* 12-bit codes */
  0x1FFF,       /* 13-bit codes */
  0x3FFF,       /* 14-bit codes */
  0x7FFF,       /* 15-bit codes */
  0xEFFF        /* 16-bit codes, 6% of code values unused */
};
#define Maxcode(maxb) (mc[(maxb) -MINBITS])

#ifdef __STDC__
#ifndef NDEBUG
#define allocx(type, ptr, size) \
    (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
    ?   (fprintf(stderr,"%s: "#ptr" -- ", prog_name), NOMEM) : OK \
    )
#else
#define allocx(type,ptr,size) \
    (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
    ? NOMEM : OK \
    )
#endif
#else
#define allocx(type,ptr,size) \
    (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
    ? NOMEM : OK \
    )
#endif

#define free_array(type,ptr,offset) \
    if (ptr != NULLPTR(type)) { \
        efree((ALLOCTYPE FAR *)((ptr) + (offset))); \
        (ptr) = NULLPTR(type); \
    }

  /*
   * Macro to allocate new memory to a pointer with an offset value.
   */
#define alloc_array(type, ptr, size, offset) \
    ( allocx(type, ptr, (size) - (offset)) != OK \
      ? NOMEM \
      : (((ptr) -= (offset)), OK) \
    )

static char FAR *sfx = NULLPTR(char) ;
#define suffix(code)     sfx[code]


#if (SPLIT_PFX)
  static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
#else
  static CODE FAR *pfx = NULLPTR(CODE);
#endif


#if (SPLIT_HT)
  static CODE FAR *ht[2] = {NULLPTR(CODE),NULLPTR(CODE)};
#else
  static CODE FAR *ht = NULLPTR(CODE);
#endif


int alloc_tables(maxcode, hashsize)
  CODE maxcode;
  HASH hashsize;
{
  static CODE oldmaxcode = 0;
  static HASH oldhashsize = 0;

  if (hashsize > oldhashsize) {
#if (SPLIT_HT)
      free_array(CODE,ht[1], 0);
      free_array(CODE,ht[0], 0);
#else
      free_array(CODE,ht, 0);
#endif
    oldhashsize = 0;
  }

    if (maxcode > oldmaxcode) {
#if (SPLIT_PFX)
        free_array(CODE,pfx[1], 128);
        free_array(CODE,pfx[0], 128);
#else
        free_array(CODE,pfx, 256);
#endif
        free_array(char,sfx, 256);

        if (   alloc_array(char, sfx, maxcode + 1, 256)
#if (SPLIT_PFX)
            || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
            || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
#else
            || alloc_array(CODE, pfx, (maxcode + 1), 256)
#endif
        ) {
            oldmaxcode = 0;
            exit_stat = NOMEM;
            return(NOMEM);
        }
        oldmaxcode = maxcode;
    }
    if (hashsize > oldhashsize) {
        if (
#if (SPLIT_HT)
            alloc_array(CODE, ht[0], (hashsize / 2) + 1, 0)
            || alloc_array(CODE, ht[1], hashsize / 2, 0)
#else
            alloc_array(CODE, ht, hashsize, 0)
#endif
        ) {
            oldhashsize = 0;
            exit_stat = NOMEM;
            return(NOMEM);
        }
        oldhashsize = hashsize;
    }
    return (OK);
}

# if (SPLIT_PFX)
    /*
     * We have to split pfx[] table in half,
     * because it's potentially larger than 64k bytes.
     */
#   define prefix(code)   (pfx[(code) & 1][(code) >> 1])
# else
    /*
     * Then pfx[] can't be larger than 64k bytes,
     * or we don't care if it is, so we don't split.
     */
#   define prefix(code) (pfx[code])
# endif


/* The initializing of the tables can be done quicker with memset() */
/* but this way is portable through out the memory models.          */
/* If you use Microsoft halloc() to allocate the arrays, then       */
/* include the pragma #pragma function(memset)  and make sure that  */
/* the length of the memory block is not greater than 64K.          */
/* This also means that you MUST compile in a model that makes the  */
/* default pointers to be far pointers (compact or large models).   */
/* See the file COMPUSI.DOS to modify function emalloc().           */

# if (SPLIT_HT)
    /*
     * We have to split ht[] hash table in half,
     * because it's potentially larger than 64k bytes.
     */
#   define probe(hash)    (ht[(hash) & 1][(hash) >> 1])
#   define init_tables() \
    { \
      hash = hashsize >> 1; \
      ht[0][hash] = 0; \
      while (hash--) ht[0][hash] = ht[1][hash] = 0; \
      highcode = ~(~(CODE)0 << (bits = INITBITS)); \
      nextfree = (block_compress ? FIRSTFREE : 256); \
    }

# else

    /*
     * Then ht[] can't be larger than 64k bytes,
     * or we don't care if it is, so we don't split.
     */
#   define probe(hash) (ht[hash])
#   define init_tables() \
    { \
      hash = hashsize; \
      while (hash--) ht[hash] = 0; \
      highcode = ~(~(CODE)0 << (bits = INITBITS)); \
      nextfree = (block_compress ? FIRSTFREE : 256); \
    }

# endif

#ifdef COMP40
/* table clear for block compress */
/* this is for adaptive reset present in version 4.0 joe release */
/* DjG, sets it up and returns TRUE to compress and FALSE to not compress */
int cl_block ()
{
    register long int rat;

    checkpoint = in_count + CHECK_GAP;
#ifndef NDEBUG
        if ( debug ) {
        fprintf ( stderr, "count: %ld, ratio: ", in_count );
        prratio ( stderr, in_count, bytes_out );
                fprintf ( stderr, "\n");
        }
#endif

    if(in_count > 0x007fffff) { /* shift will overflow */
        rat = bytes_out >> 8;
        if(rat == 0)       /* Don't divide by zero */
            rat = 0x7fffffff;
        else
            rat = in_count / rat;
    }
    else
        rat = (in_count << 8) / bytes_out;  /* 8 fractional bits */

    if ( rat > ratio ){
        ratio = rat;
        return FALSE;
    }
    else {
        ratio = 0;
#ifndef NDEBUG
        if(debug)
                fprintf ( stderr, "clear\n" );
#endif
        return TRUE;    /* clear the table */
    }
    return FALSE; /* don't clear the table */
}
#endif

/*
 * compress stdin to stdout
 *
 */
void compress()
{
    int c,adjbits;
    register HASH hash;
    register CODE code;
    HASH hashf[256];

    maxcode = Maxcode(maxbits);
    hashsize = Hashsize(maxbits);

#ifdef COMP40
/* Only needed for adaptive reset */
    checkpoint = CHECK_GAP;