home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / unix_c / cpm / uncrunch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-21  |  12.8 KB  |  541 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 Ziv.                  */
  9. /*----------------------------------------------------------------------------*/
  10. /*  Portability related assumptions:                          */
  11. /*    1. fopen called with "rb" or "wb" is sufficient to make getc/putc xfer  */
  12. /*       bytes in binary, without newline or control-z translation (this is   */
  13. /*       default for UNIX anyway, and the "b" has no effect).                 */
  14. /*    2. size of type "long" is at least 4 bytes (for getbuf to work).        */
  15. /*----------------------------------------------------------------------------*/
  16. #define VERSION "2.31D"
  17. #define DATE "11 June 1987"
  18.  
  19. /*#define DUMBLINKER*/    /*define this if linker makes a huge executable image*/
  20.             /*containing mostly zeros (big tables will instead be*/
  21.             /*allocated at run time)*/
  22.  
  23. #define XLAT_FN_CHARS    {'/','%'} /*FOR UNIX*/
  24.             /*define comma separated pairs of {undesirable char,*/
  25.             /*replacement char} for filenames - no need to include*/
  26.             /*control characters, as these are automatically*/
  27.             /*translated to question marks (?)*/
  28. /*----------------------------------------------------------------------------*/
  29.  
  30. #include "stdio.h"
  31.  
  32. /*Macro definition - ensure letter is lower case*/
  33. #define tolower(c) (((c)>='A' && (c)<='Z')?(c)-('A'-'a'):(c))
  34.  
  35. /*Macro definition - is character a control (non-printing) character?*/
  36. #define iscntrl(c) (c<' ' || c=='\177')
  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.     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.   char *stack;
  68.  
  69. #else
  70.  
  71.   struct entry {
  72.     short predecessor;    /*index to previous entry, if any*/
  73.     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.   char stack[TABLE_SIZE];
  82.  
  83. #endif
  84.  
  85. /*other global variables*/
  86. char    codlen;            /*variable code length in bits (9-12)*/
  87. short    trgmsk;            /*mask for codes of current length*/
  88. 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. char    entflg;         /*inhibit main loop from entering this code*/
  93. 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.     char *p;
  141.     char *index();
  142.     char outfn[80];            /*space to build output file name*/
  143.     int pred;            /*current predecessor (in main loop)*/
  144.     char reflevel;            /*ref rev level from input file*/
  145.     char siglevel;            /*sig rev level from input file*/
  146.     char errdetect;            /*error detection flag from input file*/
  147.     short file_cksum;        /*checksum read from input file*/
  148.  
  149.     /*filename character translation array*/
  150.     static int xlat_fn_chars[][2] = {XLAT_FN_CHARS, {-1,-1}};
  151.  
  152.     /*initialize variables for uncrunching a file*/
  153.     intram();
  154.  
  155.     /*open input file*/
  156.     if ( 0 == (infd = fopen(filename,"rb")) )
  157.         {
  158.         printf("***** can't open %s\n", filename);
  159.         return;
  160.         }
  161.  
  162.     /*verify this is a crunched file*/
  163.     if (getc(infd) != 0x76 || getc(infd) != 0xfe)
  164.         {
  165.         printf("***** %s is not a crunched file\n",filename);
  166.         fclose(infd);
  167.         return;
  168.         }
  169.  
  170.     /*extract and build output file name*/
  171.     printf("%s --> ",filename);
  172.     for(p=outfn; (*p=getc(infd))!='\0'; p++)
  173.         {
  174.         int *q;
  175.  
  176.         /*translate to lower case and strip high order bit*/
  177.         *p=tolower((*p)&0x7f);
  178.  
  179.         /*make any control character into a question mark*/
  180.         if(iscntrl(*p)) *p = '?';
  181.  
  182.         /*translate undesirable characters in file name*/
  183.         for(q = &xlat_fn_chars[0][0]; *q!=(-1); q+=2)
  184.             {
  185.             if(*p == *q)
  186.                 {
  187.                 *p = *(q+1);
  188.                 break;
  189.                 }
  190.             }
  191.         }
  192.     printf("%s\n",outfn);
  193.     *(index(outfn,'.')+4)='\0';    /*truncate non-name portion*/
  194.     if(p=index(outfn,' ')) *p='\0';    /*truncate trailing blanks*/
  195.  
  196.     /*read the four info bytes*/
  197.     reflevel=getc(infd);
  198.     siglevel=getc(infd);
  199.     errdetect=getc(infd);
  200.     getc(infd); /*skip spare*/
  201.  
  202.     /*make sure we can uncrunch this format file*/
  203.     /*note: this program does not support CRUNCH 1.x format*/
  204.     if(siglevel < 0x20 || siglevel > 0x2f)
  205.         {
  206.         printf("***** this version of UNCR cannot process %s!\n",
  207.             filename);
  208.         fclose(infd);
  209.         return;
  210.         }
  211.  
  212.     /*open output file*/
  213.     if ( 0 == (outfd =fopen( outfn,"wb")) )
  214.         {
  215.         printf("***** can't create %s\n",outfn);
  216.         fclose(infd);
  217.         return;
  218.         }
  219.  
  220.     /*set up atomic code definitions*/
  221.     initb2();
  222.  
  223.     /*main decoding loop*/
  224.     pred=NOPRED;
  225.     for(;;)
  226.         {
  227.         /*remember last predecessor*/
  228.         lastpr=pred;
  229.  
  230.         /*read and process one code*/
  231.         if((pred=getcode())==EOFCOD) /*end-of-file code*/
  232.             {
  233.             break; /*all lzw codes read*/
  234.             }
  235.  
  236.         else if(pred==RSTCOD) /*reset code*/
  237.             {
  238.             entry=0;
  239.             fulflg=0;
  240.             codlen=9;
  241.             trgmsk=0x1ff;
  242.             pred=NOPRED;
  243.             entflg=1;
  244.             initb2();
  245.             }
  246.  
  247.         else /*a normal code (nulls already deleted)*/
  248.             {
  249.             /*check for table full*/
  250.             if(fulflg!=2)
  251.                 {
  252.                 /*strategy if table not full*/
  253.                 if(decode(pred)==0)enterx(lastpr,finchar);
  254.                 else entflg=0;
  255.                 }
  256.             else
  257.                 {
  258.                 /*strategy if table is full*/
  259.                 decode(pred);
  260.                 entfil(lastpr,finchar); /*attempt to reassign*/
  261.                 }
  262.             }
  263.         }
  264.  
  265.     /*verify checksum if required*/
  266.     if(errdetect==0)
  267.         {
  268.         file_cksum=getc(infd);
  269.         file_cksum|=getc(infd)<<8;
  270.         if((file_cksum&0xffff)!=(cksum&0xffff))
  271.             {
  272.             printf("***** checksum error detected in ");
  273.             printf("%s!\n",filename);
  274.             }
  275.         }
  276.  
  277.     /*close files*/
  278.     fclose(infd);
  279.     fclose(outfd);
  280.  
  281.     /*all done this file*/
  282.     return;
  283.     }
  284.  
  285.  
  286. /*initialize the lzw and physical translation tables*/
  287. initb2()
  288.     {
  289.     register int i;
  290.     register struct entry *p;
  291.     p=table;
  292.  
  293.     /*first mark all entries of xlatbl as empty*/
  294.     for(i=0;i<XLATBL_SIZE;i++) xlatbl[i]=EMPTY;
  295.  
  296.     /*enter atomic and reserved codes into lzw table*/
  297.     for(i=0;i<0x100;i++) enterx(NOPRED,i);    /*first 256 atomic codes*/
  298.     for(i=0;i<4;i++) enterx(IMPRED,0);    /*reserved codes*/
  299.     }
  300.  
  301.  
  302. /*enter the next code into the lzw table*/
  303. enterx(pred,suff)
  304. int pred;        /*table index of predecessor*/
  305. int suff;        /*suffix byte represented by this entry*/
  306.     {
  307.     register struct entry *ep;
  308.     ep = &table[entry];
  309.  
  310.     /*update xlatbl to point to this entry*/
  311.     figure(pred,suff);
  312.  
  313.     /*make the new entry*/
  314.     ep->predecessor = (short)pred;
  315.     ep->suffix = (char)suff;
  316.     entry++;
  317.  
  318.     /*if only one entry of the current code length remains, update to*/
  319.     /*next code length because main loop is reading one code ahead*/
  320.     if(entry >= trgmsk)
  321.         {
  322.         if(codlen<12)
  323.             {
  324.             /*table not full, just make length one more bit*/
  325.             codlen++;
  326.             trgmsk=(trgmsk<<1)|1;
  327.             }
  328.         else
  329.             {
  330.             /*table almost full (fulflg==0) or full (fulflg==1)*/
  331.             /*just increment fulflg - when it gets to 2 we will*/
  332.             /*never be called again*/
  333.             fulflg++;
  334.             }
  335.         }
  336.     }
  337.  
  338.  
  339. /*find an empty entry in xlatbl which hashes from this predecessor/suffix*/
  340. /*combo, and store the index of the next available lzw table entry in it*/
  341. figure(pred,suff)
  342. int pred;
  343. int suff;
  344.     {
  345.     short *hash();
  346.     auto int disp;
  347.     register short *p;
  348.     p=hash(pred,suff,&disp);
  349.  
  350.     /*follow secondary hash chain as necessary to find an empty slot*/
  351.     while(((*p)&0xffff) != EMPTY)
  352.         {
  353.         p+=disp;
  354.         if(p<xlatbl)p+=XLATBL_SIZE;
  355.         }
  356.  
  357.     /*stuff next available index into this slot*/
  358.     *p=entry;
  359.     }
  360.  
  361.  
  362. /*hash pred/suff into xlatbl pointer*/
  363. /*duplicates the hash algorithm used by CRUNCH 2.3*/
  364. short *hash(pred,suff,disploc)
  365. int pred;
  366. int suff;
  367. int *disploc;
  368.     {
  369.     register int hashval;
  370.     
  371.     hashval=(((pred>>4)^suff) | ((pred&0xf)<<8)) + 1;
  372.     *disploc=hashval-XLATBL_SIZE;
  373.     return (xlatbl + hashval);
  374.     }
  375.     
  376.  
  377. /*initialize variables for each file to be uncrunched*/
  378. intram()
  379.     {
  380.     trgmsk=0x1ff;    /*nine bits*/
  381.     codlen=9;    /*    "    */
  382.     fulflg=0;    /*table empty*/
  383.     entry=0;    /*    "      */
  384.     getbit=0;    /*buffer emtpy*/
  385.     entflg=1;    /*first code always atomic*/
  386.     repeat_flag=0;    /*repeat not active*/
  387.     cksum=0;    /*zero checsum*/
  388.     }
  389.  
  390.  
  391. /*return a code of length "codlen" bits from the input file bit-stream*/
  392. getcode()
  393.     {
  394.     register int hole;
  395.     int code;
  396.  
  397.     /*always get at least a byte*/
  398.     getbuf=(getbuf<<codlen)|(((long)getc(infd))<<(hole=codlen-getbit));
  399.     getbit=8-hole;
  400.  
  401.     /*if is not enough to supply codlen bits, get another byte*/
  402.     if(getbit<0)
  403.         {
  404.         getbuf |= ((long)getc(infd))<<(hole-8);
  405.         getbit+=8;
  406.         }
  407.  
  408.     if(feof(infd))
  409.         {
  410.         printf("***** Unexpected EOF on input file!\n");
  411.         return EOFCOD;
  412.         }
  413.  
  414.     /*skip spare or null codes*/
  415.     if((code=((getbuf>>8) & trgmsk)) == NULCOD || code == SPRCOD)
  416.         {
  417.         return getcode();    /*skip this code, get next*/
  418.         }
  419.  
  420.     return code;
  421.     }
  422.  
  423.  
  424. /*decode this code*/
  425. decode(code)
  426. short code;
  427.     {
  428.     register char *stackp;        /*byte string stack pointer*/
  429.     register struct entry *ep;
  430.     ep = &table[code];
  431.  
  432.     if(code>=entry)
  433.         {
  434.         /*the ugly exception, "WsWsW"*/
  435.         entflg=1;
  436.         enterx(lastpr,finchar);
  437.         }
  438.  
  439.     /*mark corresponding table entry as referenced*/
  440.     ep->predecessor |= REFERENCED;
  441.  
  442.     /*walk back the lzw table starting with this code*/
  443.     stackp=stack;
  444.     while(ep > &table[255]) /*i.e. code not atomic*/
  445.         {
  446.         *stackp++ = ep->suffix;
  447.         ep = &table[(ep->predecessor)&0xfff];
  448.         }
  449.  
  450.     /*then emit all bytes corresponding to this code in forward order*/
  451.     send(finchar=(ep->suffix)&0xff); /*first byte*/
  452.  
  453.     while(stackp > stack)         /*the rest*/
  454.         {
  455.         send((*--stackp)&0xff);
  456.         }
  457.  
  458.     return(entflg);
  459.     }
  460.  
  461.  
  462. /*write a byte to output file*/
  463. /*repeat byte (0x90) expanded here*/
  464. /*checksumming of output stream done here*/
  465. send(c)
  466. register int c;
  467.     {
  468.     static int savec;    /*previous byte put to output*/
  469.  
  470.     /*repeat flag may have been set by previous call*/
  471.     if(repeat_flag)
  472.         {
  473.  
  474.         /*repeat flag was set - emit (c-1) copies of savec*/
  475.         /*or (if c is zero), emit the repeat byte itself*/
  476.         repeat_flag=0;
  477.         if(c)
  478.             {
  479.             cksum+=(savec)*(c-1);
  480.             while(--c) putc(savec,outfd);
  481.             }
  482.         else
  483.             {
  484.             putc(REPEAT_CHARACTER,outfd);
  485.             cksum+=REPEAT_CHARACTER;
  486.             }
  487.         }
  488.     else
  489.         {
  490.         /*normal case - emit c or set repeat flag*/
  491.         if(c==REPEAT_CHARACTER)
  492.             {
  493.             repeat_flag++;
  494.             }
  495.         else
  496.             {
  497.             putc(savec=c,outfd);
  498.             cksum+=(c&0xff);
  499.             }
  500.         }
  501.     }
  502.  
  503.  
  504. /*attempt to reassign an existing code which has*/
  505. /*been defined, but never referenced*/
  506. entfil(pred,suff)
  507. int pred;        /*table index of predecessor*/
  508. int suff;        /*suffix byte represented by this entry*/
  509.     {
  510.     auto int disp;
  511.     register struct entry *ep;
  512.     short *hash();
  513.     short *p;
  514.     p=hash(pred,suff,&disp);
  515.  
  516.     /*search the candidate codes (all those which hash from this new*/
  517.     /*predecessor and suffix) for an unreferenced one*/
  518.     while(*p!=(short)EMPTY)
  519.         {
  520.  
  521.         /*candidate code*/
  522.         ep = &table[*p];
  523.         if(((ep->predecessor)&REFERENCED)==0)
  524.             {
  525.             /*entry reassignable, so do it!*/
  526.             ep->predecessor=pred;
  527.             ep->suffix=suff;
  528.  
  529.             /*discontinue search*/
  530.             break;
  531.             }
  532.  
  533.         /*candidate unsuitable - follow secondary hash chain*/
  534.         /*and keep searching*/
  535.         p+=disp;
  536.         if(p<xlatbl)p+=XLATBL_SIZE;
  537.         }
  538.     }
  539.  
  540. /*end of source file*/
  541.