home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 December / simtel1292_SIMTEL_1292_Walnut_Creek.iso / msdos / compress / uncr233.arc / UNCR233.C < prev    next >
Text File  |  1989-05-08  |  14KB  |  540 lines
  1. /*----------------------------------------------------------------------------*/
  2. /*  UNCRunch/C - LZW uncruncher compatible with Z-80 CP/M program CRUNCH 2.3  */
  3. /*            (C) Copyright 1986 - Frank Prindle              */
  4. /*            May be reproduced for non-profit use only              */
  5. /*----------------------------------------------------------------------------*/
  6. /* This program is largely based on the previous works of Steven Greenberg,   */
  7. /* Joe Orost, James Woods, Ken Turkowski, Steve Davies, Jim McKie, Spencer    */
  8. /* Thomas, Terry Welch, and (of course) Lempel and Zev (Ziv?), whoever they   */
  9. /* are.                                          */
  10. /*----------------------------------------------------------------------------*/
  11. /*  Portability related assumptions:                          */
  12. /*    1. fopen called with "rb" or "wb" is sufficient to make getc/putc xfer  */
  13. /*       bytes in binary, without newline or control-z translation (this is   */
  14. /*       default for UNIX anyway, and the "b" has no effect).                 */
  15. /*    2. size of type "long" is at least 4 bytes (for getbuf to work).        */
  16. /*----------------------------------------------------------------------------*/
  17. /* Version 2.32    12/15/86 - Mods for Microsoft 'C' version 3.0 under MS-DOS    */
  18. /*    by Skip Hansen - Modem: (213) 541-2503                      */
  19. /*                                          */
  20. /*        1. Changed several "char" declarations to "unsigned char".    */
  21. /*        2. Added both top and bottom range checking on secondary      */
  22. /*           hash probe to prevent wrap around from fooling comparision.*/
  23. /*        3. Added function cisubstr to replace index function which    */
  24. /*           is not included in Microsoft's library.              */
  25. /*----------------------------------------------------------------------------*/        
  26. #define VERSION "2.32"
  27. #define DATE "25 Dec 1986"
  28.  
  29. /*#define DUMBLINKER*/    /*define this if linker makes a huge executable image*/
  30.             /*containing mostly zeros (big tables will instead be*/
  31.             /*allocated at run time)*/
  32.  
  33. #include <stdio.h>
  34.  
  35. /*Macro definition - ensure letter is lower case*/
  36. #define tolower(c) (((c)>='A' && (c)<='Z')?(c)-('A'-'a'):(c))
  37.  
  38. #define TABLE_SIZE  4096    /*size of main lzw table for 12 bit codes*/
  39. #define XLATBL_SIZE 5003    /*size of physical translation table*/
  40.  
  41. /*special values for predecessor in table*/
  42. #define NOPRED 0x6fff        /*no predecessor in table*/
  43. #define EMPTY  0x8000        /*empty table entry (xlatbl only)*/
  44. #define REFERENCED 0x2000    /*table entry referenced if this bit set*/
  45. #define IMPRED 0x7fff        /*impossible predecessor*/
  46.  
  47. #define EOFCOD 0x100        /*special code for end-of-file*/
  48. #define RSTCOD 0x101        /*special code for adaptive reset*/
  49. #define NULCOD 0x102        /*special filler code*/
  50. #define SPRCOD 0x103        /*spare special code*/
  51.  
  52. #define REPEAT_CHARACTER 0x90    /*following byte is repeat count*/
  53.  
  54. #ifdef    DUMBLINKER
  55.  
  56.   /*main lzw table and it's structure*/
  57.   struct entry {
  58.     short predecessor;    /*index to previous entry, if any*/
  59.     unsigned char suffix;        /*character suffixed to previous entries*/
  60.   } *table;
  61.  
  62.   /*auxilliary physical translation table*/
  63.   /*translates hash to main table index*/
  64.   short *xlatbl;
  65.  
  66.   /*byte string stack used by decode*/
  67.   unsigned char *stack;
  68.  
  69. #else
  70.  
  71.   struct entry {
  72.     short predecessor;    /*index to previous entry, if any*/
  73.     unsigned char suffix;    /*character suffixed to previous entries*/
  74.   } table[TABLE_SIZE];
  75.  
  76.   /*auxilliary physical translation table*/
  77.   /*translates hash to main table index*/
  78.   short xlatbl[XLATBL_SIZE];
  79.  
  80.   /*byte string stack used by decode*/
  81.   unsigned char stack[TABLE_SIZE];
  82.  
  83. #endif
  84.  
  85. /*other global variables*/
  86. unsigned char    codlen;        /*variable code length in bits (9-12)*/
  87. short    trgmsk;            /*mask for codes of current length*/
  88. unsigned char    fulflg;        /*full flag - set once main table is full*/
  89. short    entry;            /*next available main table entry*/
  90. long    getbuf;            /*buffer used by getcode*/
  91. short    getbit;            /*residual bit counter used by getcode*/
  92. unsigned char    entflg;     /*inhibit main loop from entering this code*/
  93. unsigned char    repeat_flag;    /*so send can remember if repeat required*/
  94. int    finchar;        /*first character of last substring output*/
  95. int    lastpr;            /*last predecessor (in main loop)*/
  96. short    cksum;            /*checksum of all bytes written to output file*/
  97.  
  98. FILE     *infd;            /*currently open input file*/
  99. FILE     *outfd;            /*currently open output file*/
  100.  
  101. main(argc,argv)
  102. int argc;
  103. char *argv[];
  104.     {
  105.     /*usage check*/
  106.     if (argc-- < 2)
  107.         {
  108.         printf("Usage : uncr <crunched_file_name> ...\n");
  109.         exit(0);
  110.         }
  111.  
  112.     /*who am i*/
  113.     printf("UNCRunch/C Version %s (%s)\n\n",VERSION,DATE);
  114.  
  115. #ifdef    DUMBLINKER
  116.     /*allocate storage now for the big tables (keeps load short)*/
  117.     table=(struct entry *)malloc(TABLE_SIZE*sizeof(struct entry));
  118.     xlatbl=(short *)malloc(XLATBL_SIZE*sizeof(short));
  119.     stack=(char *)malloc(TABLE_SIZE*sizeof(char));
  120.     if(table==NULL || xlatbl==NULL || stack==NULL)
  121.         {
  122.         printf("***** not enough memory to run this program!\n");
  123.         exit(0);
  124.         }
  125. #endif
  126.  
  127.     /*do all the files specified*/
  128.     while(argc--) uncrunch(*++argv);
  129.  
  130.     /*all done all files*/
  131.     exit(0);
  132.     }
  133.  
  134.  
  135. /*uncrunch a single file*/
  136. uncrunch(filename)
  137. char *filename;
  138.     {
  139.     int c;            
  140.     unsigned char *p;
  141.     char *cisubstr();
  142.     unsigned char outfn[80];    /*space to build output file name*/
  143.     int pred;            /*current predecessor (in main loop)*/
  144.     unsigned char reflevel;        /*ref rev level from input file*/
  145.     unsigned char siglevel;        /*sig rev level from input file*/
  146.     unsigned char errdetect;    /*error detection flag from input file*/
  147.     short file_cksum;        /*checksum read from input file*/
  148.  
  149.     /*initialize variables for uncrunching a file*/
  150.     intram();
  151.  
  152.     /*open input file*/
  153.     if ( 0 == (infd = fopen(filename,"rb")) )
  154.         {
  155.         printf("***** can't open %s\n", filename);
  156.         return;
  157.         }
  158.  
  159.     /*verify this is a crunched file*/
  160.     if (getc(infd) != 0x76 || getc(infd) != 0xfe)
  161.         {
  162.         printf("***** %s is not a crunched file\n",filename);
  163.         return;
  164.         }
  165.  
  166.     /*extract and build output file name*/
  167.     printf("%s --> ",filename);
  168.     for(p=outfn; (*p=getc(infd))!='\0'; p++) *p=tolower(*p);
  169.     printf("%s\n",outfn);
  170.     *(cisubstr(outfn,".")+4)='\0'; /*truncate non-name portion*/
  171.  
  172.     /*open output file*/
  173.     if ( 0 == (outfd =fopen( outfn,"wb")) )
  174.         {
  175.         printf("***** can't create %s\n",outfn);
  176.         return;
  177.         }
  178.  
  179.     /*read the four info bytes*/
  180.     reflevel=getc(infd);
  181.     siglevel=getc(infd);
  182.     errdetect=getc(infd);
  183.     getc(infd); /*skip spare*/
  184.  
  185.     /*make sure we can uncrunch this format file*/
  186.     /*note: this program does not support CRUNCH 1.x format*/
  187.     if(siglevel < 0x20 || siglevel > 0x2f)
  188.         {
  189.         printf("***** this version of UNCR cannot process %s!\n",
  190.             filename);
  191.         return;
  192.         }
  193.  
  194.     /*set up atomic code definitions*/
  195.     initb2();
  196.  
  197.     /*main decoding loop*/
  198.     pred=NOPRED;
  199.     for(;;)
  200.         {
  201.         /*remember last predecessor*/
  202.         lastpr=pred;
  203.  
  204.         /*read and process one code*/
  205.         if((pred=getcode())==EOFCOD) /*end-of-file code*/
  206.             {
  207.             break; /*all lzw codes read*/
  208.             }
  209.  
  210.         else if(pred==RSTCOD) /*reset code*/
  211.             {
  212.             entry=0;
  213.             fulflg=0;
  214.             codlen=9;
  215.             trgmsk=0x1ff;
  216.             pred=NOPRED;
  217.             entflg=1;
  218.             initb2();
  219.             }
  220.  
  221.         else /*a normal code (nulls already deleted)*/
  222.             {
  223.             /*check for table full*/
  224.             if(fulflg!=2)
  225.                 {
  226.                 /*strategy if table not full*/
  227.                 if(decode(pred)==0)enterx(lastpr,finchar);
  228.                 else entflg=0;
  229.                 }
  230.             else
  231.                 {
  232.                 /*strategy if table is full*/
  233.                 decode(pred);
  234.                 entfil(lastpr,finchar); /*attempt to reassign*/
  235.                 }
  236.             }
  237.         }
  238.  
  239.     /*verify checksum if required*/
  240.     if(errdetect==0)
  241.         {
  242.         file_cksum=getc(infd);
  243.         file_cksum|=getc(infd)<<8;
  244.         if(file_cksum!=cksum)
  245.             {
  246.             printf("***** checksum error detected in ");
  247.             printf("%s!\n",filename);
  248.             }
  249.         }
  250.  
  251.     /*close files*/
  252.     fclose(infd);
  253.     fclose(outfd);
  254.  
  255.     /*all done this file*/
  256.     return;
  257.     }
  258.  
  259.  
  260. /*initialize the lzw and physical translation tables*/
  261. initb2()
  262.     {
  263.     register int i;
  264.     register struct entry *p;
  265.     p=table;
  266.  
  267.     /*first mark all entries of xlatbl as empty*/
  268.     for(i=0;i<XLATBL_SIZE;i++) xlatbl[i]=EMPTY;
  269.  
  270.     /*enter atomic and reserved codes into lzw table*/
  271.     for(i=0;i<0x100;i++) enterx(NOPRED,i);    /*first 256 atomic codes*/
  272.     for(i=0;i<4;i++) enterx(IMPRED,0);    /*reserved codes*/
  273.     }
  274.  
  275.  
  276. /*enter the next code into the lzw table*/
  277. enterx(pred,suff)
  278. int pred;        /*table index of predecessor*/
  279. int suff;        /*suffix byte represented by this entry*/
  280.     {
  281.     register struct entry *ep;
  282.     ep = &table[entry];
  283.  
  284.  
  285.     /*update xlatbl to point to this entry*/
  286.     figure(pred,suff);
  287.  
  288.     /*make the new entry*/
  289.     ep->predecessor = (short)pred;
  290.     ep->suffix = (unsigned char)suff;
  291.     entry++;
  292.  
  293.     /*if only one entry of the current code length remains, update to*/
  294.     /*next code length because main loop is reading one code ahead*/
  295.     if(entry >= trgmsk)
  296.         {
  297.         if(codlen<12)
  298.             {
  299.             /*table not full, just make length one more bit*/
  300.             codlen++;
  301.             trgmsk=(trgmsk<<1)|1;
  302.             }
  303.         else
  304.             {
  305.             /*table almost full (fulflg==0) or full (fulflg==1)*/
  306.             /*just increment fulflg - when it gets to 2 we will*/
  307.             /*never be called again*/
  308.             fulflg++;
  309.             }
  310.         }
  311.     }
  312.  
  313.  
  314. /*find an empty entry in xlatbl which hashes from this predecessor/suffix*/
  315. /*combo, and store the index of the next available lzw table entry in it*/
  316. figure(pred,suff)
  317. int pred;
  318. int suff;
  319.     {
  320.     short *hash();
  321.     auto int disp;
  322.     register short *p;
  323.     p=hash(pred,suff,&disp);
  324.  
  325.     /*follow secondary hash chain as necessary to find an empty slot*/
  326.     while(((*p)&0xffff) != EMPTY)
  327.         {
  328.         p+=disp;
  329.         if(p<xlatbl || p > xlatbl+XLATBL_SIZE)
  330.             p+=XLATBL_SIZE;
  331.         }
  332.  
  333.     /*stuff next available index into this slot*/
  334.     *p=entry;
  335.     }
  336.  
  337.  
  338. /*hash pred/suff into xlatbl pointer*/
  339. /*duplicates the hash algorithm used by CRUNCH 2.3*/
  340. short *hash(pred,suff,disploc)
  341. int pred;
  342. int suff;
  343. int *disploc;
  344.     {
  345.     register int hashval;
  346.     
  347.     hashval=((((pred>>4) & 0xff) ^suff) | ((pred&0xf)<<8)) + 1;
  348.     *disploc=hashval-XLATBL_SIZE;
  349.     return (xlatbl + hashval);
  350.     }
  351.     
  352.  
  353. /*initialize variables for each file to be uncrunched*/
  354. intram()
  355.     {
  356.     trgmsk=0x1ff;    /*nine bits*/
  357.     codlen=9;    /*    "    */
  358.     fulflg=0;    /*table empty*/
  359.     entry=0;    /*    "      */
  360.     getbit=0;    /*buffer emtpy*/
  361.     entflg=1;    /*first code always atomic*/
  362.     repeat_flag=0;    /*repeat not active*/
  363.     cksum=0;    /*zero checsum*/
  364.     }
  365.  
  366.  
  367. /*return a code of length "codlen" bits from the input file bit-stream*/
  368. getcode()
  369.     {
  370.     register int hole;
  371.     int code;
  372.  
  373.     /*always get at least a byte*/
  374.     getbuf=(getbuf<<codlen)|(((long)getc(infd))<<(hole=codlen-getbit));
  375.     getbit=8-hole;
  376.  
  377.     /*if is not enough to supply codlen bits, get another byte*/
  378.     if(getbit<0)
  379.         {
  380.         getbuf |= ((long)getc(infd))<<(hole-8);
  381.         getbit+=8;
  382.         }
  383.  
  384.     if(feof(infd))
  385.         {
  386.         printf("***** Unexpected EOF on input file!\n");
  387.         return EOFCOD;
  388.         }
  389.  
  390.     /*skip spare or null codes*/
  391.     if((code=((getbuf>>8) & trgmsk)) == NULCOD || code == SPRCOD)
  392.         {
  393.         return getcode();    /*skip this code, get next*/
  394.         }
  395.  
  396.     return code;
  397.     }
  398.  
  399.  
  400. /*decode this code*/
  401. decode(code)
  402. short code;
  403.     {
  404.     register unsigned char *stackp;        /*byte string stack pointer*/
  405.     register struct entry *ep;
  406.     ep = &table[code];
  407.  
  408.     if(code>=entry)
  409.         {
  410.         /*the ugly exception, "WsWsW"*/
  411.         entflg=1;
  412.         enterx(lastpr,finchar);
  413.         }
  414.  
  415.     /*mark corresponding table entry as referenced*/
  416.     ep->predecessor |= REFERENCED;
  417.  
  418.     /*walk back the lzw table starting with this code*/
  419.     stackp=stack;
  420.     while(ep > &table[255]) /*i.e. code not atomic*/
  421.         {
  422.         *stackp++ = ep->suffix;
  423.         ep = &table[(ep->predecessor)&0xfff];
  424.         }
  425.  
  426.     /*then emit all bytes corresponding to this code in forward order*/
  427.     send(finchar=(ep->suffix)&0xff); /*first byte*/
  428.  
  429.     while(stackp > stack)         /*the rest*/
  430.         {
  431.         send(*--stackp);
  432.         }
  433.  
  434.     return(entflg);
  435.     }
  436.  
  437.  
  438. /*write a byte to output file*/
  439. /*repeat byte (0x90) expanded here*/
  440. /*checksumming of output stream done here*/
  441. send(c)
  442. register unsigned char c;
  443.     {
  444.     static unsigned char savec;    /*previous byte put to output*/
  445.  
  446.     /*repeat flag may have been set by previous call*/
  447.     if(repeat_flag)
  448.         {
  449.  
  450.         /*repeat flag was set - emit (c-1) copies of savec*/
  451.         /*or (if c is zero), emit the repeat byte itself*/
  452.         repeat_flag=0;
  453.         if(c)
  454.             {
  455.             cksum+=(savec&0xff)*(c-1);
  456.             while(--c){
  457.                 putc(savec,outfd);
  458.             }
  459.             }
  460.         else
  461.             {
  462.             putc(REPEAT_CHARACTER,outfd);
  463.             cksum+=REPEAT_CHARACTER;
  464.             }
  465.         }
  466.     else
  467.         {
  468.         /*normal case - emit c or set repeat flag*/
  469.         if(c==REPEAT_CHARACTER)
  470.             {
  471.             repeat_flag++;
  472.             }
  473.         else
  474.             {
  475.             putc(savec=c,outfd);
  476.             cksum+=(c&0xff);
  477.             }
  478.         }
  479.     }
  480.  
  481.  
  482. /*attempt to reassign an existing code which has*/
  483. /*been defined, but never referenced*/
  484. entfil(pred,suff)
  485. int pred;        /*table index of predecessor*/
  486. int suff;        /*suffix byte represented by this entry*/
  487.     {
  488.     auto int disp;
  489.     register struct entry *ep;
  490.     short *hash();
  491.     short *p;
  492.     p=hash(pred,suff,&disp);
  493.  
  494.     /*search the candidate codes (all those which hash from this new*/
  495.     /*predecessor and suffix) for an unreferenced one*/
  496.     while(*p!=(short)EMPTY){
  497.  
  498.         /*candidate code*/
  499.         ep = &table[*p];
  500.         if(((ep->predecessor)&REFERENCED)==0){
  501.             /*entry reassignable, so do it!*/
  502.             ep->predecessor=pred;
  503.             ep->suffix=suff;
  504.             /*discontinue search*/
  505.             break;
  506.         }
  507.  
  508.         /*candidate unsuitable - follow secondary hash chain*/
  509.         /*and keep searching*/
  510.         p+=disp;
  511.         if(p<xlatbl || p > xlatbl+XLATBL_SIZE)
  512.             p+=XLATBL_SIZE;
  513.     }
  514. }
  515.  
  516. /*
  517.  cisubstr(string, token) searches for lower case token in string s
  518.  returns pointer to token within string if found, NULL otherwise
  519. */
  520.  
  521. char *cisubstr(s, t)
  522. char *s,*t;
  523. {
  524. char *ss,*tt;
  525. /* search for first char of token */
  526. for(ss=s; *s; s++)
  527.     if (*s==*t)
  528.         /* compare token with substring */
  529.         for(ss=s,tt=t; ;){
  530.             if(*tt==0)
  531.                 return s;
  532.             if(*ss++ != *tt++)
  533.                 break;
  534.         }
  535. return NULL;
  536. }
  537.  
  538. /*end of source file*/
  539.  
  540.