home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Archiwiz / Tar320 / SOURCES.ZIP / COMPRESS.C < prev    next >
Text File  |  1994-12-31  |  13KB  |  459 lines
  1. /* Compress - data compression program */
  2. /* machine variants which require cc -Dmachine:    pdp11, z8000, pcxt */
  3.  
  4. /* The following code is derived from regular 'compress' program, */
  5. /* revision 4.0 85/07/30 by Joe Orost (decvax!vax135!petsd!joe)   */
  6.  
  7. /*
  8.  * Algorithm from "A Technique for High Performance Data Compression",
  9.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  10.  *
  11.  * Algorithm:
  12.  *    Modified Lempel-Ziv method (LZW).  Basically finds common
  13.  * substrings and replaces them with a variable size code.  This is
  14.  * deterministic, and can be done on the fly.  Thus, the decompression
  15.  * procedure needs no input table, but tracks the way the table was built.
  16.  */
  17. #include "modern.h"
  18. #include "compress.h"
  19. #ifdef USE_COMPRESS
  20. #include "lzwbits.h"
  21.  
  22. #ifndef USG
  23. #    ifdef i386
  24. #        define SYS_V
  25. #    endif
  26. #    ifdef M_XENIX
  27. #        define SYS_V
  28. #    endif
  29. #endif
  30.  
  31. #ifdef SYS_V
  32. #    include <memory.h>
  33. #    ifndef MEMSET
  34. #        define MEMSET
  35. #    endif
  36. #endif
  37.  
  38. #ifdef MSC_VER
  39. #    include <memory.h>
  40. #    ifndef MEMSET
  41. #        define MEMSET
  42. #    endif
  43. #endif
  44.  
  45. #ifdef __TURBOC__
  46. #    include <mem.h>
  47. #    ifndef MEMSET
  48. #        define MEMSET
  49. #    endif
  50. #endif
  51.  
  52. #ifdef XENIX_16
  53. static code_int c_hashsize;
  54. # define c_HSIZE c_hashsize
  55. #else
  56. # define c_HSIZE _HSIZE
  57. #endif
  58.  
  59. #ifdef MSDOS
  60. #    include <stdlib.h>
  61. #    ifndef ODDBYTES
  62. #        define ODDBYTES
  63. #    endif
  64. #else
  65.     char *malloc();
  66.     void free();
  67. #endif
  68. #if BITS > 15
  69. #    ifdef ODDBYTES
  70.         typedef signed char tentry[3];
  71. #        define ENMASK(x) ((x) & 0xffffffL)
  72. #    else
  73.         typedef count_int tentry;
  74. #    endif
  75. #else
  76.     typedef count_int tentry;
  77. #endif
  78. #ifdef ENMASK
  79. #    define EMPTY (count_int)ENMASK(~0L)
  80. #else
  81. #    define EMPTY (count_int)~0L
  82. #endif
  83.  
  84. static int c_n_bits;    /* number of bits/code */
  85. static int c_maxbits = BITS;    /* user settable max # bits/code */
  86. static code_int c_maxcode;    /* maximum code, given n_bits */
  87. /* should NEVER generate this code */
  88. static code_int c_maxmaxcode = (code_int)1 << BITS;
  89.  
  90. #define word_type unsigned short
  91. #define WNIL (word_type)0
  92. #define CNIL (count_int)0
  93.  
  94. #ifdef XENIX_16
  95.   static tentry *htab[MAXPAGES];
  96.   static word_type *codetab[MAXPAGES] = {WNIL};
  97.  
  98. # define codetabof(i)    (codetab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  99. # define htabof(i)    (htab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  100. #else
  101.   static tentry *htab;
  102.   static word_type *codetab = WNIL;
  103. # define codetabof(i)    codetab[i]
  104. # define htabof(i)    htab[i]
  105. #endif
  106. static code_int hsize = _HSIZE; /* for dynamic table sizing */
  107.  
  108. static code_int c_free_ent = 0; /* first unused entry */
  109.  
  110. /* block compression parameters -- after all codes are */
  111. /* used up, and compression rate changes, start over.  */
  112. static int c_block_compress = BLOCK_MASK;
  113. static int c_clear_flg = 0;
  114. static long int ratio = 0;
  115. static count_int c_checkpoint = CHECK_GAP;
  116.  
  117. static void cl_hash __ARGS__((count_int));
  118.  
  119. static void cl_hash(clsize) /* reset code table */
  120. register count_int clsize;
  121. {
  122. #ifdef XENIX_16
  123.    register j, l;
  124. # ifndef MEMSET
  125.    register i;
  126. # endif
  127.  
  128.    for (j=0; j<MAXPAGES && clsize>=0; j++, clsize-=PAGESIZE) {
  129.        l = clsize<PAGESIZE ? (int)clsize : PAGESIZE;
  130. # ifdef MEMSET
  131.        (void)memset((char*)htab[j], (int)EMPTY, l*sizeof(**htab));
  132. # else
  133.        for (i=0; i<l; i++)
  134. #  ifdef ODDBYTES
  135.        {
  136.           register signed char *p = htab[j][i];
  137.           *(unsigned short *)p = (unsigned short)EMPTY;
  138.           p[2] = (signed char)(EMPTY >> 16);
  139.        }
  140. #  else
  141.           htab[j][i] = EMPTY;
  142. #  endif
  143. # endif
  144.    }
  145. #else
  146. # ifdef MEMSET
  147.    (void)memset(htab, (int)EMPTY, clsize*sizeof(*htab));
  148. # else
  149.    register count_int i; for (i=0; i<clsize; i++) htab[i] = EMPTY;
  150. # endif
  151. #endif
  152. }
  153.  
  154. static int  offset;
  155. static long int in_count = 1;    /* length of input */
  156. static long int bytes_out;    /* length of compressed output */
  157.  
  158. /* interface function pointer */
  159. static void (*putbyte) __ARGS__((int));
  160.  
  161. static void putpiece __ARGS__((char *, int));
  162.  
  163. static void putpiece(p, n)
  164. register char *p; register n;
  165. {
  166.    bytes_out += n; while (n-- > 0) (*putbyte)(*p++); offset = 0;
  167. }
  168.  
  169. /* Output the given code.
  170.  * Inputs:
  171.  *    code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  172.  *        that n_bits =< (long)wordsize - 1.
  173.  * Outputs:
  174.  *    Outputs code to the file.
  175.  * Assumptions:
  176.  *    Chars are 8 bits long.
  177.  * Algorithm:
  178.  *    Maintain a BITS character long buffer (so that 8 codes will
  179.  * fit in it exactly).    Use the VAX insv instruction to insert each
  180.  * code in turn.  When the buffer fills up empty it and start over.
  181.  */
  182.  
  183. static char outbuf[BITS];
  184.  
  185. static void output __ARGS__((word_type));
  186.  
  187. static void output(code)
  188. word_type code;
  189. {
  190. #ifndef vax
  191.    static char_type rmask[] = {0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f};
  192. #endif
  193.    /* On the VAX, it is important to have the register declarations */
  194.    /* in exactly the order given, or the asm will break.            */
  195.    register int r_off = offset, bits = c_n_bits;
  196.    register char *bp = outbuf;
  197.  
  198. #ifdef vax
  199.    /* VAX DEPENDENT!! Implementation on other machines is below.
  200.     *
  201.     * Translation: Insert BITS bits from the argument starting at
  202.     * offset bits from the beginning of buf.
  203.     */
  204.    0;    /* Work around for pcc -O bug with asm and if stmt */
  205.    asm( "insv    4(ap),r11,r10,(r9)" );
  206. #else
  207.    /* byte/bit numbering on the VAX is simulated by the following code */
  208.    /* Get to the first byte. */
  209.    bp += (r_off >> 3);
  210.    r_off &= 7;
  211.    /* Since code is always >= 8 bits, only     */
  212.    /* need to mask the first hunk on the left. */
  213.    *bp = (*bp & rmask[r_off]) | (code << r_off);
  214.    bp++;
  215.    code >>= (r_off = 8 - r_off);
  216.    if ((bits -= r_off) >= 8) {
  217.       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  218.       *bp++ = code;
  219.       code >>= 8;
  220.       bits -= 8;
  221.    }
  222.    /* Last bits. */
  223.    if (bits) *bp = code;
  224. #endif
  225.    if ((offset += c_n_bits)==(c_n_bits << 3)) putpiece(outbuf,c_n_bits);
  226.  
  227.    /* If the next entry is going to be too big for  */
  228.    /* the code size, then increase it, if possible. */
  229.    if (c_free_ent > c_maxcode || c_clear_flg > 0) {
  230.       /* Write the whole buffer, because the input side won't  */
  231.       /* discover the size increase until after it has read it */
  232.       if (offset > 0) putpiece(outbuf, c_n_bits);
  233.  
  234.       if (c_clear_flg) {
  235.          c_maxcode = MAXCODE(c_n_bits = INIT_BITS);
  236.          c_clear_flg = 0;
  237.       } else {
  238.          c_maxcode = ++c_n_bits == c_maxbits ?
  239.             c_maxmaxcode : MAXCODE(c_n_bits);
  240.       }
  241.    }
  242. }
  243.  
  244. static void cl_block __ARGS__((void)) /* table clear for block compress */
  245. {
  246.    register long int rat;
  247.  
  248.    c_checkpoint = in_count + CHECK_GAP;
  249.  
  250.    if (in_count > 0x007fffffL) { /* shift will overflow */
  251.       if ((rat = bytes_out >> 8) == 0) {/* Don't divide by zero */
  252.          rat = 0x7fffffffL;
  253.       } else {
  254.          rat = in_count / rat;
  255.       }
  256.    } else {
  257.       rat = (in_count << 8) / bytes_out; /* 8 fractional bits */
  258.    }
  259.    if (rat > ratio) {
  260.       ratio = rat;
  261.    } else {
  262.       ratio = 0;
  263.       cl_hash((count_int)hsize);
  264.       c_free_ent = FIRST;
  265.       c_clear_flg = 1;
  266.       output(CLEAR);
  267.    }
  268. }
  269.  
  270. int z_gettab(bits)
  271. int bits;
  272. {
  273. #ifdef XENIX_16
  274.    register i, j; long l;
  275. #endif
  276.    if      (c_maxbits > bits)      c_maxbits = bits;
  277.    else if (c_maxbits < INIT_BITS) c_maxbits = INIT_BITS;
  278. #ifdef XENIX_16
  279.    if (codetab[0]) return c_maxbits;
  280.    if      (c_maxbits >= 16) c_hashsize = 69001L;
  281.    else if (c_maxbits >= 15) c_hashsize = 35023L;
  282.    else if (c_maxbits >= 14) c_hashsize = 18013L;
  283.    else if (c_maxbits >= 13) c_hashsize = 9001L;
  284.    else                      c_hashsize = 5003L;
  285.    for (l=c_hashsize, i=0; i<MAXPAGES && l > 0; i++) {
  286.       j = l > PAGESIZE ? PAGESIZE : (int)l;
  287.       codetab[i] = (word_type *)malloc(sizeof(word_type)*j);
  288.       if (!codetab[i]) break;
  289.       htab[i] = (tentry*)malloc(sizeof(**htab) * j);
  290.       if (!htab[i]) {
  291.          free((char*)(codetab[i])); codetab[i]=WNIL; break;
  292.       }
  293.       l -= j;
  294.    }
  295.    c_hashsize -= l;
  296.    if      (c_hashsize >= 69001L) { j = 16; c_hashsize = 69001L; }
  297.    else if (c_hashsize >= 35023L) { j = 15; c_hashsize = 35023L; }
  298.    else if (c_hashsize >= 18013)  { j = 14; c_hashsize = 18013;  }
  299.    else if (c_hashsize >= 9001)   { j = 13; c_hashsize = 9001;   }
  300.    else if (c_hashsize >= 5003)   { j = 12; c_hashsize = 5003;   }
  301.    else return -1;
  302.    if (c_maxbits > j) c_maxbits = j;
  303. #else
  304.    if (codetab) return c_maxbits;
  305.    if ((codetab=(word_type *)malloc(sizeof(*codetab)*_HSIZE))==WNIL ||
  306.        (htab   =(count_int *)malloc(sizeof(*htab)   *_HSIZE))==CNIL) {
  307.       return -1;
  308.    }
  309. #endif
  310.    c_maxmaxcode = (code_int)1 << c_maxbits;
  311.    return c_maxbits;
  312. }
  313.  
  314. void z_reltab()
  315. {
  316. #ifdef XENIX_16
  317.    register i;
  318.  
  319.    for (i=0; i<MAXPAGES && codetab[i]!=WNIL; i++) {
  320.       free((char*)(codetab[i])); free((char*)(htab[i]));
  321.    }
  322.    codetab[0] = WNIL;
  323. #else
  324.    if (codetab != WNIL) {
  325.       free((char*)codetab); codetab = WNIL;
  326.       if (htab != CNIL) free((char*)htab);
  327.    }
  328. #endif
  329. }
  330.  
  331. /*
  332.  * Algorithm:  use open addressing double hashing (no chaining) on the
  333.  * prefix code / next character combination.  We do a variant of Knuth's
  334.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  335.  * secondary probe.  Here, the modular division first probe is gives way
  336.  * to a faster exclusive-or manipulation.  Also do block compression with
  337.  * an adaptive reset, whereby the code table is cleared when the compression
  338.  * ratio decreases, but after the table fills.    The variable-length output
  339.  * codes are re-sized at this point, and a special CLEAR code is generated
  340.  * for the decompressor.  Late addition:  construct the table according to
  341.  * file size for noticeable speed improvement on small files.  Please direct
  342.  * questions about this implementation to ames!jaw.
  343.  */
  344.  
  345. static int already = 0;
  346. static int hshift;
  347. static unsigned short ent;
  348.  
  349. int cbegin(wishbits, putb, fsize)
  350. int wishbits;
  351. void (*putb)();
  352. long fsize;
  353. {
  354.    register long fcode;
  355.  
  356.    if (z_gettab(wishbits) < 0) return -1;
  357.    c_block_compress = BLOCK_MASK;
  358.    c_checkpoint = CHECK_GAP;
  359.  
  360.    putbyte = putb;
  361.    hsize = _HSIZE;
  362.    /* tune hash table size for small files -- ad hoc,      */
  363.    /* but the sizes match earlier #defines, which          */
  364.    /* serve as upper bounds on the number of output codes. */
  365.    if      (fsize < (1<<12)) hsize = 5003;
  366.    else if (fsize < (1<<13)) hsize = 9001;
  367.    else if (fsize < (1<<14)) hsize = 18013;
  368.    else if (fsize < (1<<15)) hsize = 35023L;
  369.    else if (fsize < 47000L)  hsize = 50021L;
  370.    if (hsize > c_HSIZE) hsize = c_HSIZE;
  371.  
  372.    offset = 0;
  373.    bytes_out = 3; /* includes 3-byte header mojo */
  374.    c_clear_flg = 0;
  375.    ratio = 0;
  376.    in_count = 1;
  377.    c_checkpoint = CHECK_GAP;
  378.    c_maxcode = MAXCODE(c_n_bits = INIT_BITS);
  379.    c_free_ent = c_block_compress ? FIRST : 256;
  380.  
  381.    hshift = 0;
  382.    for (fcode = (long)hsize; fcode < 65536L; fcode *= 2L) hshift++;
  383.    hshift = 8 - hshift; /* set hash code range bound */
  384.  
  385.    cl_hash((count_int)hsize); /* clear hash table */
  386.  
  387.    already = 0;
  388.  
  389.    return c_maxbits;
  390. }
  391.  
  392. #define GETBYTE() (--len, char_to_byte(*(char_type *)buf++))
  393.  
  394. void cpiece(buf, len)
  395. char *buf;
  396. int len;
  397. {
  398.    register long fcode;
  399.    register code_int i = 0;
  400.    register int c;
  401.    register long tmp;
  402.    register code_int disp;
  403.  
  404.    if (!already) {
  405.       (*putbyte)(LZW_0TH_MAGIC); (*putbyte)(LZW_1ST_MAGIC);
  406.       (*putbyte)((char)(c_maxbits | c_block_compress));
  407.       already = 1; ent = GETBYTE();
  408.    }
  409.    while (len > 0) {
  410.       c = GETBYTE(); in_count++;
  411.  
  412.       fcode = ((long)c << c_maxbits) + ent;
  413.       i = ((code_int)c << hshift) ^ ent; /* xor hashing */
  414.       disp = i ? hsize-i : 1; /* secondary hash (after G. Knott) */
  415.       while ((tmp =
  416. #ifdef ODDBYTES
  417. #  ifdef ENMASK
  418.       ENMASK(*(long*)htabof(i))
  419. #  else
  420.       (((long)*(2+(signed char *)htabof(i))) << 16) |
  421.       *(unsigned short *)htabof(i)
  422. #  endif
  423. #else
  424.       htabof(i)
  425. #endif
  426.       ) != EMPTY) {
  427.          if (tmp == fcode) {
  428.             ent = codetabof(i); goto next;
  429.          }
  430.          if ((i -= disp) < 0) i += hsize;
  431.       }
  432.       output(ent);
  433.       ent = c;
  434.       if (to_compare(c_free_ent) < to_compare(c_maxmaxcode)) {
  435. #ifdef ODDBYTES
  436.          register signed char *p = htabof(i);
  437.          *(unsigned short *)p = (unsigned short)fcode;
  438.          p[2] = (signed char)(fcode >> 16);
  439. #else
  440.          htabof(i) = fcode;
  441. #endif
  442.          codetabof(i) = c_free_ent++; /* code -> hashtable */
  443.       }
  444.       else if ((count_int)in_count >= c_checkpoint && c_block_compress)
  445.          cl_block();
  446. next: ;
  447.    }
  448. }
  449.  
  450. long cflush()
  451. {
  452.    /* Put out the final code. */
  453.    output(ent);
  454.    /* At EOF, write the rest of the buffer. */
  455.    putpiece(outbuf, (offset+7)/8);
  456.    return bytes_out;
  457. }
  458. #endif
  459.