home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 2001 January / VPR0101A.BIN / OLS / TAR32053 / tar32053.exe / SRC / COMPAPI.C < prev    next >
C/C++ Source or Header  |  1999-05-23  |  18KB  |  552 lines
  1. #ifndef __DEFCONF_H
  2. #include "defconf.h"
  3. #endif
  4. /*
  5.    This file was hacked for kmtar for WIN32
  6.                                     at 1996-05-06.
  7.                                     by tantan SGL00213@niftyserve.or.jp 
  8. */
  9. /*@H************************ < COMPRESS API    > ****************************
  10. *   $@(#) compapi.c,v 4.3d 90/01/18 03:00:00 don Release ^                  *
  11. *                                                                           *
  12. *   compress : compapi.c  <current version of compress algorithm>           *
  13. *                                                                           *
  14. *   port by  : Donald J. Gloistein                                          *
  15. *                                                                           *
  16. *   Source, Documentation, Object Code:                                     *
  17. *   released to Public Domain.  This code is based on code as documented    *
  18. *   below in release notes.                                                 *
  19. *                                                                           *
  20. *---------------------------  Module Description  --------------------------*
  21. *   Contains source code for modified Lempel-Ziv method (LZW) compression   *
  22. *   and decompression.                                                      *
  23. *                                                                           *
  24. *   This code module can be maintained to keep current on releases on the   *
  25. *   Unix system. The command shell and dos modules can remain the same.     *
  26. *                                                                           *
  27. *--------------------------- Implementation Notes --------------------------*
  28. *                                                                           *
  29. *   compiled with : compress.h compress.fns compress.c                      *
  30. *   linked with   : compress.obj compusi.obj                                *
  31. *                                                                           *
  32. *   problems:                                                               *
  33. *                                                                           *
  34. *                                                                           *
  35. *   CAUTION: Uses a number of defines for access and speed. If you change   *
  36. *            anything, make sure about side effects.                        *
  37. *                                                                           *
  38. * Compression:                                                              *
  39. * Algorithm:  use open addressing double hashing (no chaining) on the       *
  40. * prefix code / next character combination.  We do a variant of Knuth's     *
  41. * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime     *
  42. * secondary probe.  Here, the modular division first probe is gives way     *
  43. * to a faster exclusive-or manipulation.                                    *
  44. * Also block compression with an adaptive reset was used in original code,  *
  45. * whereby the code table is cleared when the compression ration decreases   *
  46. * but after the table fills.  This was removed from this edition. The table *
  47. * is re-sized at this point when it is filled , and a special CLEAR code is *
  48. * generated for the decompressor. This results in some size difference from *
  49. * straight version 4.0 joe Release. But it is fully compatible in both v4.0 *
  50. * and v4.01                                                                 *
  51. *                                                                           *
  52. * Decompression:                                                            *
  53. * This routine adapts to the codes in the file building the "string" table  *
  54. * on-the-fly; requiring no table to be stored in the compressed file.  The  *
  55. * tables used herein are shared with those of the compress() routine.       *
  56. *                                                                           *
  57. *     Initials ---- Name ---------------------------------                  *
  58. *      DjG          Donald J. Gloistein, current port to MsDos 16 bit       *
  59. *                   Plus many others, see rev.hst file for full list        *
  60. *      LvR          Lyle V. Rains, many thanks for improved implementation  *
  61. *                   of the compression and decompression routines.          *
  62. *************************************************************************@H*/
  63.  
  64. #include <stdio.h>
  65. #include <io.h>
  66. #include "compress.h" /* contains the rest of the include file declarations */
  67.  
  68. static int offset;
  69. static long int in_count ;         /* length of input */
  70. static long int bytes_out;         /* length of compressed output */
  71.  
  72. static INTCODE prefxcode, nextfree;
  73. static INTCODE highcode;
  74. static INTCODE maxcode;
  75. static HASH hashsize;
  76. static int  bits;
  77.  
  78. #include    "defs.h"
  79. /*
  80.  * The following two parameter tables are the hash table sizes and
  81.  * maximum code values for various code bit-lengths.  The requirements
  82.  * are that Hashsize[n] must be a prime number and Maxcode[n] must be less
  83.  * than Maxhash[n].  Table occupancy factor is (Maxcode - 256)/Maxhash.
  84.  * Note:  I am using a lower Maxcode for 16-bit codes in order to
  85.  * keep the hash table size less than 64k entries.
  86.  */
  87. CONST HASH hs[] = {
  88.   0x13FF,       /* 12-bit codes, 75% occupancy */
  89.   0x26C3,       /* 13-bit codes, 80% occupancy */
  90.   0x4A1D,       /* 14-bit codes, 85% occupancy */
  91.   0x8D0D,       /* 15-bit codes, 90% occupancy */
  92.   0xFFD9        /* 16-bit codes, 94% occupancy, 6% of code values unused */
  93. };
  94. #define Hashsize(maxb) (hs[(maxb) -MINBITS])
  95.  
  96. CONST INTCODE mc[] = {
  97.   0x0FFF,       /* 12-bit codes */
  98.   0x1FFF,       /* 13-bit codes */
  99.   0x3FFF,       /* 14-bit codes */
  100.   0x7FFF,       /* 15-bit codes */
  101.   0xEFFF        /* 16-bit codes, 6% of code values unused */
  102. };
  103. #define Maxcode(maxb) (mc[(maxb) -MINBITS])
  104.  
  105. #ifdef __STDC__
  106. #ifdef DEBUG
  107. #define allocx(type, ptr, size) \
  108.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  109.     ?   (fprintf(stderr,"%s: "#ptr" -- ", prog_name), NOMEM) : OK \
  110.     )
  111. #else
  112. #define allocx(type,ptr,size) \
  113.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  114.     ? NOMEM : OK \
  115.     )
  116. #endif
  117. #else
  118. #define allocx(type,ptr,size) \
  119.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  120.     ? NOMEM : OK \
  121.     )
  122. #endif
  123.  
  124. #define free_array(type,ptr,offset) \
  125.     if (ptr != NULLPTR(type)) { \
  126.         efree((ALLOCTYPE FAR *)((ptr) + (offset))); \
  127.         (ptr) = NULLPTR(type); \
  128.     }
  129.  
  130.   /*
  131.    * Macro to allocate new memory to a pointer with an offset value.
  132.    */
  133. #define alloc_array(type, ptr, size, offset) \
  134.     ( allocx(type, ptr, (size) - (offset)) != OK \
  135.       ? NOMEM \
  136.       : (((ptr) -= (offset)), OK) \
  137.     )
  138.  
  139. static char FAR *sfx = NULLPTR(char) ;
  140. #define suffix(code)     sfx[code]
  141.  
  142.  
  143. #if (SPLIT_PFX)
  144.   static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
  145. #else
  146.   static CODE FAR *pfx = NULLPTR(CODE);
  147. #endif
  148.  
  149.  
  150. #if (SPLIT_HT)
  151.   static CODE FAR *ht[2] = {NULLPTR(CODE),NULLPTR(CODE)};
  152. #else
  153.   static CODE FAR *ht = NULLPTR(CODE);
  154. #endif
  155.  
  156.  
  157. static INTCODE alloc_tables_oldmaxcode = 0;
  158. static HASH alloc_tables_oldhashsize = 0;
  159.  
  160. int alloc_tables(maxcode, hashsize)
  161.   INTCODE maxcode;
  162.   HASH hashsize;
  163. {
  164.   //static INTCODE oldmaxcode = 0;
  165.   //static HASH oldhashsize = 0;
  166.  
  167.   if (hashsize > alloc_tables_oldhashsize) {
  168. #if (SPLIT_HT)
  169.       free_array(CODE,ht[1], 0);
  170.       free_array(CODE,ht[0], 0);
  171. #else
  172.       free_array(CODE,ht, 0);
  173. #endif
  174.     alloc_tables_oldhashsize = 0;
  175.   }
  176.  
  177.     if (maxcode > alloc_tables_oldmaxcode) {
  178. #if (SPLIT_PFX)
  179.         free_array(CODE,pfx[1], 128);
  180.         free_array(CODE,pfx[0], 128);
  181. #else
  182.         free_array(CODE,pfx, 256);
  183. #endif
  184.         free_array(char,sfx, 256);
  185.  
  186.         if (   alloc_array(char, sfx, maxcode + 1, 256)
  187. #if (SPLIT_PFX)
  188.             || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
  189.             || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
  190. #else
  191.             || alloc_array(CODE, pfx, (maxcode + 1), 256)
  192. #endif
  193.         ) {
  194.             alloc_tables_oldmaxcode = 0;
  195.             exit_stat = NOMEM;
  196.             return(NOMEM);
  197.         }
  198.         alloc_tables_oldmaxcode = maxcode;
  199.     }
  200.     if (hashsize > alloc_tables_oldhashsize) {
  201.         if (
  202. #if (SPLIT_HT)
  203.             alloc_array(CODE, ht[0], (hashsize / 2) + 1, 0)
  204.             || alloc_array(CODE, ht[1], hashsize / 2, 0)
  205. #else
  206.             alloc_array(CODE, ht, hashsize, 0)
  207. #endif
  208.         ) {
  209.             alloc_tables_oldhashsize = 0;
  210.             exit_stat = NOMEM;
  211.             return(NOMEM);
  212.         }
  213.         alloc_tables_oldhashsize = hashsize;
  214.     }
  215.     return (OK);
  216. }
  217.  
  218. # if (SPLIT_PFX)
  219.     /*
  220.      * We have to split pfx[] table in half,
  221.      * because it's potentially larger than 64k bytes.
  222.      */
  223. #   define prefix(code)   (pfx[(code) & 1][(code) >> 1])
  224. # else
  225.     /*
  226.      * Then pfx[] can't be larger than 64k bytes,
  227.      * or we don't care if it is, so we don't split.
  228.      */
  229. #   define prefix(code) (pfx[code])
  230. # endif
  231.  
  232.  
  233. /* The initializing of the tables can be done quicker with memset() */
  234. /* but this way is portable through out the memory models.          */
  235. /* If you use Microsoft halloc() to allocate the arrays, then       */
  236. /* include the pragma #pragma function(memset)  and make sure that  */
  237. /* the length of the memory block is not greater than 64K.          */
  238. /* This also means that you MUST compile in a model that makes the  */
  239. /* default pointers to be far pointers (compact or large models).   */
  240. /* See the file COMPUSI.DOS to modify function emalloc().           */
  241.  
  242. # if (SPLIT_HT)
  243.     /*
  244.      * We have to split ht[] hash table in half,
  245.      * because it's potentially larger than 64k bytes.
  246.      */
  247. #   define probe(hash)    (ht[(hash) & 1][(hash) >> 1])
  248. #   define init_tables() \
  249.     { \
  250.       hash = hashsize >> 1; \
  251.       ht[0][hash] = 0; \
  252.       while (hash--) ht[0][hash] = ht[1][hash] = 0; \
  253.       highcode = ~(~(INTCODE)0 << (bits = INITBITS)); \
  254.       nextfree = (block_compress ? FIRSTFREE : 256); \
  255.     }
  256.  
  257. # else
  258.  
  259.     /*
  260.      * Then ht[] can't be larger than 64k bytes,
  261.      * or we don't care if it is, so we don't split.
  262.      */
  263. #   define probe(hash) (ht[hash])
  264. #   define init_tables() \
  265.     { \
  266.       hash = hashsize; \
  267.       while (hash--) ht[hash] = 0; \
  268.       highcode = ~(~(INTCODE)0 << (bits = INITBITS)); \
  269.       nextfree = (block_compress ? FIRSTFREE : 256); \
  270.     }
  271.  
  272. # endif
  273.  
  274. /* ------------------------------------------*/
  275.   static int prevbits = 0;
  276.   static int no_res_flag=NO;
  277.  
  278. void fatal(char *s,char *mes);
  279.  
  280.  
  281. /* nextcode()の内部変数*/
  282. static int nextcode_size;
  283. static UCHAR nextcode_inbuf[MAXBITS];
  284.  
  285. int nextcode(codeptr)
  286.   INTCODE *codeptr;
  287. /* Get the next code from input and put it in *codeptr.
  288.  * Return (TRUE) on success, or return (FALSE) on end-of-file.
  289.  * Adapted from COMPRESS V4.0.
  290.  */
  291. {
  292.   //static int size;
  293.   //static UCHAR inbuf[MAXBITS];
  294.   register INTCODE code;
  295.   register int shift;
  296.   UCHAR *bp;
  297.  
  298.  
  299.  
  300.   /* If the next entry is a different bit-size than the preceeding one
  301.    * then we must adjust the size and scrap the old buffer.
  302.    */
  303.   if (prevbits != bits) {
  304.     prevbits = bits;
  305.     nextcode_size = 0;
  306.   }
  307.   /* If we can't read another code from the buffer, then refill it.
  308.    */
  309.   if (nextcode_size - (shift = offset) < bits) {
  310.     /* Read more input and convert size from # of bytes to # of bits */
  311.     if ((nextcode_size = v_read(nextcode_inbuf, bits)) <= 0)
  312.         return NO;
  313.     nextcode_size <<= 3;
  314.     offset = shift = 0;
  315.   }
  316.   /* Get to the first byte. */
  317.   bp = nextcode_inbuf + (shift >> 3);
  318.   /* Get first part (low order bits) */
  319.   code = (*bp++ >> (shift &= 7));
  320.   /* high order bits. */
  321.   code |= *bp++ << (shift = 8 - shift);
  322.   if ((shift += 8) < bits) code |= *bp << shift;
  323.   *codeptr = code & highcode;
  324.   offset += bits;
  325.   return (TRUE);
  326. }
  327. /*--------------------- decompress ----------------*/
  328.  
  329.   static INTCODE _code,savecode;
  330.   FLAG fulltable, cleartable;
  331.   static char sufxchar,*token= NULL;   /* String buffer to build token */
  332.   
  333.   static int maxtoklen = MAXTOKLEN;
  334.   static first_chk=0;
  335.  
  336. /*#define    _putc(a)    *Zbuf=(char)(a);Zbuf++;(*len)++*/
  337. /*#define    _putc(a)    putc((a),stdout);(*len)++*/
  338. #    define INBUFSIZE 10000
  339.  
  340. /* _putcの内部変数*/
  341. static char *_putc_p=NULL;
  342. void _putc(int c)
  343. {
  344.   extern void flush_window(void);
  345. #ifdef DYN_ALLOC
  346.     extern unsigned char *window;
  347. #else
  348.     extern unsigned char window[];
  349. #endif
  350.     //static char *p=NULL;
  351.     extern unsigned int outcnt;
  352.  
  353.     if (_putc_p == NULL){
  354. #ifdef    DYN_ALLOC
  355.         if ((window = malloc(INBUFSIZE)) == NULL)
  356.             fatal("compapi","out of memory");
  357. #endif
  358.         _putc_p = window;
  359.         outcnt=0;
  360.     }
  361.     
  362.     if (outcnt < INBUFSIZE)
  363.         _putc_p[outcnt++] = c;
  364.  
  365.     if (outcnt == INBUFSIZE){
  366.         flush_window();
  367.         _putc_p = window;
  368.     }
  369. }    
  370.     
  371.  
  372. int de_comp(void)
  373. {
  374.     static int i;
  375.  
  376. ss:
  377.     if (first_chk){
  378.       if (!nextcode(&savecode))
  379.           return EOF;
  380.     }else
  381.       first_chk=1;
  382.      
  383.     if ((_code = savecode) == CLEAR && cleartable) {
  384.       highcode = ~(~(INTCODE)0 << (bits = INITBITS));
  385.       fulltable = FALSE;
  386.       nextfree = (cleartable = block_compress) == FALSE ? 256 : FIRSTFREE;
  387.       if (!nextcode(&prefxcode))
  388.           return OK;
  389.    /*   putc((sufxchar = (char)prefxcode), write_out);*/
  390.       _putc((sufxchar = (char)prefxcode));
  391.       goto ss;   /* sorry for "goto" */
  392.     }
  393.     i = 0;
  394.     if (_code >= nextfree && !fulltable) {
  395.       if (_code != nextfree){
  396.         exit_stat = CODEBAD;
  397.         return OK;     /* Non-existant code */
  398.       }
  399.       /* Special case for sequence KwKwK (see text of article)         */
  400.       _code = prefxcode;
  401.       token[i++] = sufxchar;
  402.     }
  403.     /* Build the token string in reverse order by chasing down through
  404.      * successive prefix tokens of the current token.  Then output it.
  405.      */
  406.     while (_code >= 256) {
  407. #     ifdef DEBUG
  408.         /* These are checks to ease paranoia. Prefix codes must decrease
  409.          * monotonically, otherwise we must have corrupt tables.  We can
  410.          * also check that we haven't overrun the token buffer.
  411.          */
  412.         if (_code <= (INTCODE)prefix(_code)){
  413.             exit_stat= TABLEBAD;
  414.             return OK;
  415.         }
  416. #     endif
  417.       if (i >= maxtoklen) {
  418.         maxtoklen *= 2;   /* double the size of the token buffer */
  419.         if ((token =realloc(token,(unsigned int)maxtoklen)) == NULLPTR(char)) {
  420.           exit_stat = TOKTOOBIG;
  421.           return OK;
  422.         }
  423.       }
  424.       token[i++] = suffix(_code);
  425.       _code = (INTCODE)prefix(_code);
  426.     }
  427.     _putc(sufxchar = (char)_code);
  428.     while (--i >= 0){
  429.         _putc(token[i]);
  430.     }
  431.     /* If table isn't full, add new token code to the table with
  432.      * codeprefix and codesuffix, and remember current code.
  433.      */
  434.     if (!fulltable) {
  435.       _code = nextfree;
  436.       assert(256 <= _code && _code <= maxcode);
  437.       prefix(_code) = (CODE)prefxcode;
  438.       suffix(_code) = sufxchar;
  439.       prefxcode = savecode;
  440.       if (_code++ == highcode) {
  441.         if (highcode >= maxcode) {
  442.           fulltable = TRUE;
  443.           --_code;
  444.         }
  445.         else {
  446.           ++bits;
  447.           highcode += _code;           /* nextfree == highcode + 1 */
  448.         }
  449.       }
  450.       nextfree = _code;
  451.     }
  452.   return OK;
  453. }
  454.  
  455. void de_comp_init2(void)
  456. {
  457.  
  458.   exit_stat = OK;
  459.  
  460. /* Initialze the token buffer. */
  461.     if (token == NULL && (token = (char *)malloc((unsigned int)maxtoklen)) == NULL) {
  462.             exit_stat = NOMEM;
  463.             return;
  464.     }
  465.  
  466.   if (alloc_tables(maxcode = ~(~(INTCODE)0 << maxbits),0)) /* exit_stat already set */
  467.      return;
  468.  
  469.  
  470.   cleartable = TRUE;
  471.   savecode = CLEAR;
  472.   offset = 0;
  473.   prevbits = 0;
  474.   no_res_flag=NO;
  475.   first_chk=0;
  476. }
  477. #ifdef DLL
  478. void compapi_end(void)
  479. {
  480. #if (SPLIT_HT)
  481.       free_array(CODE,ht[1], 0);
  482.       free_array(CODE,ht[0], 0);
  483. #else
  484.       free_array(CODE,ht, 0);
  485. #endif
  486.     alloc_tables_oldhashsize = 0;
  487. #if (SPLIT_PFX)
  488.         free_array(CODE,pfx[1], 128);
  489.         free_array(CODE,pfx[0], 128);
  490. #else
  491.         free_array(CODE,pfx, 256);
  492. #endif
  493.         free_array(char,sfx, 256);
  494. }
  495. void compapi_static_init(void)
  496. {
  497.     offset=0;
  498.     in_count=0 ;         /* length of input */
  499.     bytes_out=0;         /* length of compressed output */
  500.  
  501.     prefxcode=0, nextfree=0;
  502.     highcode=0;
  503.     maxcode=0;
  504.     hashsize=0;
  505.     bits=0;
  506.  
  507.     sfx = NULLPTR(char) ;
  508. //#define suffix(code)     sfx[code]
  509.  
  510.  
  511. #if (SPLIT_PFX)
  512.   //static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
  513.     pfx[0]=NULLPTR(CODE);
  514.     pfx[1]=NULLPTR(CODE);
  515. #else
  516.   //static CODE FAR *pfx = NULLPTR(CODE);
  517.     pfx=NULLPTR(CODE);
  518. #endif
  519.  
  520.  
  521. #if (SPLIT_HT)
  522.   //static CODE FAR *ht[2] = {NULLPTR(CODE),NULLPTR(CODE)};
  523.     ht[0]=NULLPTR(CODE);
  524.     ht[1]=NULLPTR(CODE);
  525. #else
  526.   //static CODE FAR *ht = NULLPTR(CODE);
  527.     ht=NULLPTR(CODE);
  528. #endif
  529.  
  530.     alloc_tables_oldmaxcode = 0;
  531.     alloc_tables_oldhashsize = 0;
  532.  
  533.     prevbits = 0;
  534.     no_res_flag=NO;
  535.  
  536. /* nextcode()の内部変数*/
  537.     nextcode_size=0;
  538.     memset(nextcode_inbuf,0,sizeof(UCHAR)*MAXBITS);
  539.  
  540.     _code=0,savecode=0;
  541.     fulltable=0, cleartable=0;
  542.     sufxchar=0,token= NULL;   /* String buffer to build token */
  543.   
  544.     maxtoklen = MAXTOKLEN;
  545.     first_chk=0;
  546.  
  547. /* _putcの内部変数*/
  548.     _putc_p=NULL;
  549.  
  550. }
  551. #endif /* DLL */
  552.