/****************************************************************** * ex:se ts=4 sw=4 ai: * * Data compression program. * * Author: Gene H. Olson * Smartware Consulting * * This is FREE software in the PUBLIC DOMAIN. * * This program may be used only for research into data * compression techniques. See WARNING in compact(1) * manual page for further discussion. * * "Everything FREE contains no guarantee." ********************************************************************/ #define VERSION "compact version 1.0 PL0" #ifndef lint static char sccs[] = "@(#)compact.c 1.25 10/28/90" ; #endif #include #include #include #include #include #include #if MARK # include #else # define MARK(x) #endif extern void exit() ; extern char *memset() ; extern char *memcpy() ; extern char *share_create() ; extern char *share_open() ; #ifndef DEBUG # ifdef lint # define DEBUG 99 # else # define DEBUG 0 # endif #endif #ifndef CHECK # if DEBUG >= 2 # define CHECK 100 # else # define CHECK 0 # endif #endif /* * Pet typedefs. */ #define SWAP(x) (((ushort)(x) >> 8) | ((ushort)(x) << 8)) #define uchar unsigned char #define ushort unsigned short #define ulong unsigned long #if lint #define malloc(x) 0 #define realloc(x,y) 0 #endif /* * Fundamental constants. */ #define MAGIC 0xc5a3 /* Magic number */ #define ODDMAGIC 0xc3a4 /* EOF magic for odd files */ #define EVENMAGIC 0xc3a5 /* EOF magic for even files */ #define MAXCHAR ((1 << 16) + 1) /* Size of character set */ /* * Tuning parameter defaults. */ #define MEMORY 0x40000000 /* Default bytes memory */ #define INRUN 10000000 /* Default bytes input run */ #ifndef HASHRATIO #define HASHRATIO 1.2 /* Ratio of hash entries to items */ #endif /* * Compression item table definition. */ #define HASHFUN(prefix, suffix) \ ((((((prefix) << 3) + (suffix)) << 4) - (prefix) + (suffix)) & (hashmask)) typedef struct h_struct ITEM ; struct h_struct { ITEM* h_next ; /* Next item on hash list */ ITEM** h_last ; /* Link ptr to this item */ ulong h_code ; /* Previous code */ ushort h_char ; /* Current input character */ ushort h_ref ; /* Reference flag */ } ; int hashsize ; /* Hash table size (power 2) */ int maxitem ; /* Maximum item number */ /* * Decompression item table definition. */ typedef struct d_struct DEC ; struct d_struct { ulong d_code ; /* Decompression code */ ushort d_char ; /* Decompression character */ ushort d_ref ; /* Reference flag */ } ; /* * Caught signal list. */ int sig[] = { SIGHUP, SIGINT, SIGQUIT, SIGPIPE, SIGTERM, 0 } ; /* * Debugging stuff. */ #if DEBUG >= 1 int debug ; /* Debug level */ #endif /* * Efficiency checks. */ #if DEBUG >= 1 long collision ; #endif /* * User parameters. */ int action ; /* c==compact or e==expand */ char *infname ; /* Input file name */ char *outfname ; /* Output file name */ int infd ; /* Input file descriptor */ int outfd ; /* Output file descriptor */ long inrun ; /* Maximum input run length */ long memory ; /* Memory to use */ long maxwidth ; /* Max width of output code */ int quiet ; /* Quiet mode */ int inbs ; /* Input block size */ int outbs ; /* Output block size */ int phys ; /* Output physical record size */ int insize ; /* Input volume size (records) */ int outsize ; /* Output volume size (records) */ ulong inrec ; /* Input record number */ ulong outrec ; /* Output record number */ int incopy ; /* Read input to non-shared buffer */ int outcopy ; /* Write output from non-shared buffer */ int inswap ; /* Swap input bytes */ int outswap ; /* Swap output bytes */ int memlock ; /* Lock process into memory */ int intank ; /* Number of input buffers */ int outtank ; /* Number of output buffers */ int inpid ; /* Input tank process PID */ int outpid ; /* Output tank process PID */ int (*getin)() ; /* Get input routine */ int (*putout)() ; /* Put output routine */ char *acommand ; /* Medium setup command */ char *zcommand ; /* Medium teardown command */ char *rsh ; /* Read share structure (opaque) */ char *wsh ; /* Write share structure (opaque) */ /* * Miscellaneous declarations. */ int invol ; /* Input volume number */ int outvol ; /* Output volume number */ ushort *inbuf ; /* Input buffer */ ushort *outbuf ; /* Output buffer */ ushort *lastbuf ; /* Last buffer read by inprocess */ int lastcount ; /* Corresponding buffer count */ ulong intotal ; /* Input character count */ ulong outtotal ; /* Output character count */ ushort eofmagic ; /* EOF magic number */ /************************************************************** * quit - Exit gracefully. **************************************************************/ void quit(s) int s ; { register int i ; register int pid ; int rs ; for (i = 0 ; sig[i] ; i++) (void) signal(sig[i], SIG_IGN) ; /* * Close shared memory. */ if (rsh) share_close(rsh) ; if (wsh) share_close(wsh) ; /* * Wait for inprocess and outprocess to complete. */ while (inpid | outpid) { pid = wait(&rs) ; if (pid == -1) break ; if (inpid == pid) { inpid = 0 ; if (s == 0) s = rs ; } if (outpid == pid) { outpid = 0 ; if (s > 0) s = rs ; } } /* * Destroy allocated shared memory. */ if (rsh) share_destroy(rsh) ; if (wsh) share_destroy(wsh) ; /* * Execute final teardown command. * * Note that if we were in compress mode with * multi-volume input, the zcommand has already * been done by the input() routine when prompting * for the last volume of the set. */ if (s == 0 && zcommand && !(action == 'c' && insize)) (void) system(zcommand) ; exit(s) ; } /*********************************************************** * getval - Get value ***********************************************************/ long getval(cp, units) register char *cp ; int units ; { register int val ; units = 0 ; if (!isdigit(*cp)) return(-1) ; val = 0 ; do { val *= 10 ; val += *cp++ - '0' ; } while (isdigit(*cp)) ; if (*cp) units = *cp++ ; switch (units) { case 'B': case 'b': val *= 512 ; break ; case 'K': case 'k': val *= 1024 ; break ; case 'M': case 'm': val *= 1000 * 1024 ; break ; case 0: break ; default: return(-1) ; } return (*cp==0 ? val : -1) ; } /************************************************************ * confirm - Wait for volume load confirmation. ************************************************************/ confirm() { register int n ; char ch ; int answer ; static int ttyfd = -1 ; /* * Get a file descriptor to reference the * users tty terminal. */ if (ttyfd < 0) { if (isatty(0)) ttyfd = 0 ; else if ((ttyfd = open("/dev/tty", O_RDWR)) == -1) { (void) fprintf(stderr, "Cannot open ") ; perror("/dev/tty") ; quit(1) ; } } /* * Read the tty for the user's answer. */ answer = 0 ; for (;;) { n = read(ttyfd, &ch, 1) ; if (n == 1) { if (ch == '\r' || ch == '\n') break ; if (answer == 0) answer = ch ; } if (n < 0) { perror("TTY") ; quit(1) ; } } return(answer) ; } /************************************************************ * input - Get an input block. ************************************************************/ input() { register int n ; register int i ; register ushort *wp ; int ch ; static int eoi ; if (eoi) return(0) ; /* * Loop to read in a full input record. */ for (n = 0 ;;) { /* * Handle multi-volume input. */ if (infname && inrec == 0) { /* * If not the first volume of an n-volume set, * ask for confirmation before opening the file. * * If he responds with (q), assume the last * volume has been read, and return end-of-file. */ if (++invol > 1) { if (zcommand) (void) system(zcommand) ; for (;;) { (void) fprintf(stderr, "Mount input volume #%d, hit (or 'q' to quit)? ", invol) ; ch = confirm() ; if (ch == 0) break ; if (ch == 'q') { eoi = 1 ; goto done ; } } if (acommand) (void) system(acommand) ; } /* * Open the file. */ if ((infd = open(infname, O_RDONLY)) == -1) { (void) fprintf(stderr, "Cannot open ") ; perror(infname) ; quit(1) ; } } /* * Read in records until we get a full record, an * end-of-file, or an error. */ for (;;) { i = read(infd, (char*)inbuf + n, inbs - n) ; /* * Handle EOF. If we are not doing multi-volume input * consider this the EOI. If we are doing multi-volume * input, go back for the next volume. */ if (i == 0) { (void) close(infd) ; if (insize) { inrec = 0 ; break ; } eoi = 1 ; goto done ; } /* * Handle a file I/O error. */ if (i == -1) { n = -1 ; perror("Input read error") ; (void) close(infd) ; return(-1) ; } /* * A good read. Add the bytes read this time to * the running total. When we get a full record, * increment the volume record count. When the * full volume size is reached, reset the record * position so we go back for another volume next * time. */ n += i ; if (n == inbs) { if (++inrec == insize) { (void) close(infd) ; inrec = 0 ; } goto done ; } } } /* * If byte swapping is in effect, swap all the * bytes in the current input buffer. */ done: if (inswap) { wp = inbuf ; i = (n + 1) / 2 ; while (--i >= 0) { *wp = SWAP(*wp) ; wp++ ; } } return(n) ; } /****************************************************************** * fileinput - File input. ******************************************************************/ fileinput() { register int n ; n = input() ; if (n > 0) { intotal += n ; if (n & 1) eofmagic = ODDMAGIC ; } return((n + 1) / 2 - 1) ; } /****************************************************************** * inprocess - Input process * * This procedure forks, then runs as a process reading from * the input device or pipe. ******************************************************************/ inprocess() { register char *sh ; int rc ; ushort *buf ; ushort *ibuf ; ushort *wp ; int pfd[2] ; int cfd[2] ; rsh = share_create(pfd, cfd, inbs, intank) ; if (rsh == 0) { (void) fprintf(stderr, "Shared memory allocated failed\n") ; quit(1) ; } /* * Create the task. Setup file descriptors so the * inprocess will die on SIGPIPE if the primary process * exits, but no SIGPIPE occurs to the promary process * when inprocess exits. */ while ((inpid = fork()) == -1) sleep(1) ; if (inpid == 0) { (void) close(1) ; (void) close(cfd[0]) ; (void) close(cfd[1]) ; /* * If input is done to a non-shared buffer, * allocate the buffer here. */ if (incopy) { buf = (ushort *)malloc(inbs) ; if (buf == 0) { (void) fprintf(stderr, "Not enough memory\n") ; exit(1) ; } } else buf = 0 ; /* * Loop reading input blocks until done. */ sh = share_open(pfd) ; assert(sh) ; for (;;) { /* * Get a block, read data into it, then pass it * to the data compression process. */ if (share_get(sh, (char**)&inbuf, &rc) <= 0) break ; if (buf) { ibuf = inbuf ; inbuf = buf ; } if ((rc = input()) <= 0) break ; if (buf) { inbuf = ibuf ; (void) memcpy((char *)inbuf, (char *)buf, rc) ; } if (share_put(sh, (char*)inbuf, rc) <= 0) break ; /* * In data compression mode with multi-volume * input, detect EOI here so as to avoid prompting * the user unnecessarily for another volume. */ if (action == 'e' && insize) { wp = inbuf + rc / sizeof(ushort) ; while (wp > inbuf && *--wp == 0) ; if ( wp >= inbuf && (*wp == ODDMAGIC || *wp == EVENMAGIC) && (wp == inbuf || *--wp == 0) && (wp == inbuf || *--wp == 0) && (wp == inbuf || *--wp == 0) ) break ; } } #if DEBUG >= 2 if (debug >= 2) { (void) fprintf(stderr, "Input child terminating normally\n") ; } #endif /* * Exit the child when complete. */ share_close(sh) ; exit(0) ; } /* * Initialize the shared memory interface in the * parent process. */ (void) close(pfd[1]) ; rsh = share_open(cfd) ; } /************************************************************ * shareinput - Do input from shared memory. ************************************************************/ shareinput() { int n ; if (inbuf) (void) share_put(rsh, (char*)inbuf, 0) ; if (share_get(rsh, (char**)&inbuf, &n) <= 0) return(-1) ; if (n > 0) { intotal += n ; if (n & 1) eofmagic = ODDMAGIC ; } return((n + 1) / 2 - 1) ; } /*********************************************************** * output - Output a block of data. ***********************************************************/ output(nbyte) int nbyte ; /* Number of bytes to write */ { register ushort *wp ; register int n ; register int bsize ; /* * Open the output file if necessary. */ if (outfname && outrec == 0) { if (++outvol > 1) { if (zcommand) (void) system(zcommand) ; (void) fprintf(stderr, "Please mount output volume #%d, hit ", outvol) ; (void) confirm() ; if (acommand) (void) system(acommand) ; } if ((outfd = open(outfname, O_WRONLY)) == -1) { (void) fprintf(stderr, "Cannot open ") ; perror(outfname) ; quit(1) ; } } /* * Swap output bytes if that option is selected. */ if (outswap) { n = nbyte / 2 + 1 ; wp = outbuf ; while (--n >= 0) { *wp = SWAP(*wp) ; wp++ ; } } /* * Pad to a multiple of the given physical size if * that option is selected. */ if (nbyte < outbs && phys) { wp = &outbuf[nbyte/2] ; bsize = (nbyte + phys - 1) / phys * phys ; while (nbyte < bsize) { *wp++ = 0 ; nbyte += 2 ; } } /* * Write the data and check for errors. */ n = write(outfd, (char*) outbuf, (int) nbyte) ; if (n < 0) { perror("Write error") ; return(0) ; } if (n != nbyte) { (void) fprintf(stderr, "Write of %d bytes returned %d\n", nbyte, n) ; } if (++outrec == outsize) { outrec = 0 ; (void) close(outfd) ; } return(outbs) ; } /***************************************************************** * fileoutput - File oriented output routine. *****************************************************************/ fileoutput(n) { if (n < outbs && phys) outtotal += (n + phys - 1) / phys * phys ; else outtotal += n ; return(output(n) / 2) ; } /****************************************************************** * outprocess - Output process * * This procedure forks, then runs as a process writing to * the output device or pipe. ******************************************************************/ outprocess() { int pfd[2] ; int cfd[2] ; int wcount ; int n ; char *sh ; ushort *obuf ; ushort *buf ; wsh = share_create(pfd, cfd, outbs, outtank) ; if (wsh == 0) { (void) fprintf(stderr, "Shared memory allocated failed\n") ; quit(1) ; } /* * Create the task. Setup file descriptors so the * primary process will die on SIGPIPE if outprocess * exits, but no SIGPIPE occurs to outprocess when * the primary process exits. */ while ((outpid = fork()) == -1) sleep(1) ; if (outpid == 0) { (void) close(0) ; (void) close(pfd[1]) ; sh = share_open(cfd) ; assert(sh) ; if (outcopy) { buf = (ushort *)malloc(outbs) ; if (buf == 0) { (void) fprintf(stderr, "Not enough memory!\n") ; exit(1) ; } } else buf = 0 ; for (;;) { if (share_get(sh, (char**)&outbuf, &wcount) <= 0) break ; if (buf) { (void) memcpy((char *)buf, (char *)outbuf, wcount) ; obuf = outbuf ; outbuf = buf ; } if (output(wcount) <= 0) break ; if (buf) outbuf = obuf ; if (share_put(sh, (char*) outbuf, 0) <= 0) break ; } share_close(sh) ; exit(0) ; } (void) close(cfd[0]) ; (void) close(cfd[1]) ; wsh = share_open(pfd) ; (void) share_get(wsh, (char**)&outbuf, &n) ; } /******************************************************** * shareoutput - Shared memory output routine. ********************************************************/ shareoutput(n) int n ; { if (n < outbs && phys) outtotal += (n + phys - 1) / phys * phys ; else outtotal += n ; if (share_put(wsh, (char*) outbuf, n) <= 0) return(0) ; if (share_get(wsh, (char**)&outbuf, &n) <= 0) return(0) ; return(outbs/2) ; } /************************************************************* * check - keep track of the progress of the algorithm. *************************************************************/ #if CHECK check(incount, outptr) int incount ; ushort *outptr ; { ulong in ; ulong out ; float avg ; float ratio ; static ulong lastin ; static ulong lastout ; in = intotal - incount * sizeof(ushort) ; out = outtotal + (long) outptr - (long) outbuf ; avg = 100.0 * (float) out / (float) in ; ratio = 100.0 * (float) (out - lastout) / (float) (in - lastin) ; lastin = in ; lastout = out ; #if DEBUG >= 1 if (debug >= 1) (void) fprintf(stderr, "Read: %-8ld Wrote: %-8ld Col: %-8ld Ratio: %6.2f%% %6.2f%%\n", in, out, collision, ratio, avg ) ; #endif } #endif /************************************************************** * compact - Compression algorithm. **************************************************************/ compact() { register ITEM *hp ; register ITEM *sp ; register ITEM **hpp ; register ushort *inptr ; register ushort *outptr ; register ulong ch ; register ulong code ; register ulong out ; register int obit ; register int osize ; register int incount ; register int outcount ; register ulong nitem ; register ulong mitem ; register ulong hashmask ; ITEM *itemtable ; ITEM **hashtable ; ITEM *ep ; long bitcount ; long blockcount ; long i ; ushort header[10] ; #if CHECK long chkcount = CHECK ; #endif /* * If max output width is given, set maxitem accordingly. */ maxitem = (1 << maxwidth) - MAXCHAR ; /* * Reduce maxitem if necessary to fit into the requested * maximum memory. */ i = memory / (sizeof(ITEM) + sizeof(ITEM *)) ; if (maxitem > i) maxitem = i ; /* * Set the hashtable to have the same approximate number * of entries as in maxitem, rounded to the closest * power of 2. */ hashsize = HASHRATIO * maxitem ; while (i = hashsize & (hashsize - 1)) hashsize = i ; hashmask = hashsize - 1 ; #if DEBUG >= 2 if (debug >= 2) { (void) fprintf(stderr, "hashsize = %ld (%ldK), maxitem = %ld (%ldK)\n", hashsize, sizeof(ITEM *) * hashsize / 1024, maxitem, sizeof(ITEM) * maxitem / 1024) ; } #endif /* * Allocate hash table and item table. */ itemtable = (ITEM *)malloc(maxitem * sizeof(ITEM)) ; hashtable = (ITEM **)malloc(hashsize * sizeof(ITEM *)) ; if (itemtable == 0 || hashtable == 0) { (void) fprintf(stderr, "Cannot allocate enough memory!\n") ; exit(2) ; } /* * Initialize output. */ outcount = outbs / 2 + 1 ; outptr = outbuf ; eofmagic = EVENMAGIC ; /* * Each pass through the loop, compress one block * of data. */ for (;;) { #if DEBUG >= 1 if (debug >= 1) (void) fprintf(stderr, "\n") ; #endif /* * Initialize for a new scan. */ (void) memset((char*)hashtable, 0, (int)(hashsize * sizeof(ITEM *))) ; nitem = 0 ; sp = &itemtable[0] ; ep = &itemtable[maxitem] ; out = 0 ; obit = 0 ; code = 0 ; osize = 17 ; bitcount = (1 << 16) ; blockcount = inrun / inbs + .5 ; /* * Prepare the Magic number, and the maximum number * of output codes for transmission. */ mitem = maxitem ; header[0] = MAGIC ; header[1] = 17 ; header[2] = maxitem & 0xffff ; header[3] = maxitem >> 16 ; for (i = 0 ; i < 4 ; i++) { if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = header[i] ; } /* * Read in the first input character of the run. */ if ((incount = (*getin)()) < 0) goto endrun ; inptr = inbuf ; ch = *inptr++ ; /* * Each pass through the loop, compress 1 or * more input characters to output 1 compression * code. */ for (;;) { MARK(cmatch) ; code = ch + 1 ; #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "\nMatching char: %04x\n", ch) ; #endif /* * Each time through the loop, match the next * input character if possible and continue. * Exit when the match fails. */ for (;;) { /* * Read in the next input character. */ if (--incount < 0) { if (--blockcount == 0) { incount = 0 ; goto endrun ; } #if CHECK if (--chkcount <= 0) { check(0, outptr) ; chkcount = CHECK ; } #endif if ((incount = (*getin)()) < 0) goto endrun ; inptr = inbuf ; } ch = *inptr++ ; #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "Read input char: %04x", ch) ; #endif /* * Search the hash table for the required * last code and current character. */ hpp = &hashtable[HASHFUN(code, ch)] ; for (;;) { if ((hp = *hpp) == 0) goto miss ; if (hp->h_code == code && hp->h_char == ch) break ; hpp = &hp->h_next ; #if DEBUG >= 1 collision++ ; #endif } code = hp - itemtable + MAXCHAR ; #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "\tMatched code: %lx\n", (ulong) code) ; #endif } /* * Output the next code. */ miss: MARK(cout) ; out |= code << obit ; obit += osize ; if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = out ; out >>= 16 ; obit -= 16 ; if (obit >= 16) { if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = out ; if (obit > 16) out |= code >> (osize - obit) ; out >>= 16 ; obit -= 16 ; } #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "\nOutput code: %lx\n", (ulong) code) ; #endif MARK(cbuild) ; sp->h_next = 0 ; sp->h_last = hpp ; *hpp = sp ; sp->h_code = code ; sp->h_char = ch ; sp->h_ref = 0 ; sp++ ; if (code >= MAXCHAR) itemtable[code - MAXCHAR].h_ref = 1 ; #if DEBUG >= 3 if (debug >= 3) { (void) fprintf(stderr, "Created compression code: %05lx ( %05lx %04x )\n", sp - itemtable + MAXCHAR - 1, code, ch) ; } #endif /* * If we added a new entry to the table, expand * the output bitsize if necessary. */ if (nitem < mitem) { MARK(calloc) ; if (--bitcount == 0) { bitcount = 1 << osize ; osize++ ; #if DEBUG >= 2 if (debug >= 2) (void) fprintf(stderr, "nitem = %d, osize = %d, bitcount = %d\n", nitem, osize, bitcount) ; #endif } if (++nitem != mitem) continue ; } /* * When the compress item table has become full, * find the least-recently-used leaf node and * reallocate it. */ MARK(cscan) ; for (;;) { if (sp == ep) sp = itemtable ; if (sp->h_ref == 0) break ; if (sp->h_code >= MAXCHAR) { itemtable[sp->h_code - MAXCHAR].h_ref = 1 ; } sp->h_ref = 0 ; sp++ ; } *sp->h_last = sp->h_next ; if (sp->h_next) sp->h_next->h_last = sp->h_last ; } /* * Flush the output buffer, and add a few bytes * of zero to guarantee synchronization. */ endrun: MARK(cend) ; #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "\nOutput final code: %lx\n", (ulong) code) ; #endif for (i = 0 ; i < 6 ; i++) { if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } out |= code << obit ; *outptr++ = out ; out >>= 16 ; code >>= 16 ; } if (incount < 0) break ; #if CHECK check(incount, outptr) ; chkcount = CHECK ; #endif } /* * Add the EOF code at the end. */ if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = eofmagic ; if ( outptr != outbuf && (*putout)((int) ((long)outptr-(long)outbuf)) == 0 ) return(1) ; #if DEBUG >= 1 if (debug >= 1) check(0, outbuf) ; #endif if (!quiet && intotal != 0) { (void) fprintf(stderr, "Read %ld, Wrote %ld, Compression %6.2f%%\n", intotal, outtotal, 100.0 * (long)(intotal - outtotal) / intotal ) ; } #if DEBUG >= 1 if (!quiet && intotal > 1) { (void) fprintf(stderr, "Collisions: %ld, %6.2f %%\n", collision, (100.0 * 17.0 / 16.0 * collision) / (intotal-1) ) ; } #endif return(0) ; } /*********************************************************** * expand - Expand previously compressed data. ***********************************************************/ expand() { register DEC *sp ; register DEC *dp ; register ushort *bp ; register ushort *outptr ; register ushort *inptr ; register int ibit ; register ulong in ; register ulong ch ; register ulong code ; register ulong lastcode ; register int incount ; register int outcount ; int bitcount ; ulong maxcode ; DEC *dectable ; DEC *ep ; int isize ; ulong imask ; ushort *ip ; ushort *buffer ; int ic ; int i ; ulong skip ; ulong zskip ; int state ; ulong ncode ; int err ; int magic ; int nbyte ; ushort header[4] ; /* * Initialize I/O buffers. */ err = 0 ; incount = 0 ; magic = 0 ; outptr = outbuf ; outcount = outbs / 2 + 1 ; maxcode = 0 ; dectable = 0 ; buffer = 0 ; /* * Each time through the loop, process a complete * block of data. */ state = 4 ; for (;;) { /* * Synchronize to the beginning of a new block of data. * * The file begins immediately with a magic number. * * Thereafter, blocks of decompression data are delimited * by at least two bytes of zero, followed by the two * byte magic number. */ MARK(esync) ; skip = 0 ; zskip = 0 ; for (;;) { if (--incount < 0) { if ((incount = (*getin)()) < 0) break ; inptr = inbuf ; } in = *inptr++ ; if (in == 0) { if (state <= 4) state++ ; else zskip += sizeof(ushort) ; } else { if (state >= 2) { if (in == MAGIC) { magic = 1 ; break ; } if (in == (SWAP(MAGIC) & 0xffff)) { if (!quiet) (void) fprintf(stderr, "Automatically reversing byte order!\n") ; inswap = !inswap ; outswap = !outswap ; ip = inptr ; ic = incount ; while (--ic >= 0) { *ip = SWAP(*ip) ; ip++ ; } magic = 1 ; break ; } if ((in == ODDMAGIC || in == EVENMAGIC) && magic) { eofmagic = in ; magic = 2 ; incount = -1 ; break ; } } skip += sizeof(ushort) ; state = 0 ; } } /* * Mention that data was skipped. */ if (skip != 0 || zskip != 0 && incount >= 0) { (void) fprintf(stderr, "Warning: %d bytes of unintelligible data skipped!\n", skip + zskip) ; } if (incount < 0) { if (magic == 0) (void) fprintf(stderr, "Warning: Magic number not found!\n") ; if (magic == 1) (void) fprintf(stderr, "Warning: Old style EOF encountered!\n") ; goto eof ; } /* * Get the maximum code present in the data. */ for (i = 1 ; i < 4 ; i++) { if (--incount < 0) { if ((incount = (*getin)()) < 0) { (void) fprintf(stderr, "EOF in header!\n") ; err = 1 ; goto eof ; } inptr = inbuf ; } header[i] = *inptr++ ; } code = header[3] ; code <<= 16 ; code |= header[2] ; #if DEBUG >= 2 if (debug >= 2) (void) fprintf(stderr, "Read header, nbits=%d, maxitem=%d\n", header[1], code) ; #endif /* * Allocate the required memory. */ if (maxcode != code) { dectable = dectable ? (DEC *) realloc((char*) dectable, code * sizeof(DEC)) : (DEC *) malloc(code * sizeof(DEC)) ; buffer = buffer ? (ushort *) realloc((char*)buffer, code * sizeof(ushort)) : (ushort *) malloc(code * sizeof(ushort)) ; if (dectable == 0 || buffer == 0) { (void) fprintf(stderr, "Cannot get enough memory to decode %d items\n", code) ; exit(1) ; } maxcode = code ; } sp = &dectable[0] ; ep = &dectable[maxcode] ; /* * Initialize to decompress this block of data. */ in = 0 ; ibit = 0 ; ncode = 0 ; bp = buffer ; isize = 17 ; bitcount = (1 << 16) ; imask = 0x1ffff ; /* * Read in the first item, which must be a * single character. */ do { if (--incount < 0) { if ((incount = (*getin)()) < 0) { (void) fprintf(stderr, "Premature eof!\n") ; err = 1 ; goto eof ; } inptr = inbuf ; } in |= *inptr++ << ibit ; ibit += 16 ; } while (ibit < 17) ; code = in & imask ; if (code == 0) { state = 0 ; continue ; } in >>= 17 ; ibit -= 17 ; if (code == 0) { (void) fprintf(stderr, "Null compression block!\n") ; break ; } ch = code - 1 ; #if DEBUG >= 3 if (debug >= 3) (void) fprintf(stderr, "First input code: %05lx output as < %04x >\n", code, ch) ; #endif if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = ch ; /* * Each time through the loop, read and process one * compressed item code. */ MARK(eloop) ; for (;;) { lastcode = code ; /* * Expand the input bitsize if necessary. */ if (ncode < maxcode) { MARK(ealloc) ; if (--bitcount == 0) { bitcount = 1 << isize ; isize++ ; imask += imask + 1 ; #if DEBUG >= 2 if (debug >= 2) (void) fprintf(stderr, "ncode = %d, isize = %d, bitcount = %d\n", ncode, isize, bitcount) ; #endif } ncode++ ; } /* * If the table is full, find the oldest leaf node * and reallocate it. */ else { MARK(escan) ; for (;;) { if (sp == ep) sp = dectable ; if (sp->d_ref == 0) break ; if (sp->d_code >= MAXCHAR) { dectable[sp->d_code - MAXCHAR].d_ref = 1 ; } sp->d_ref = 0 ; sp++ ; } } /* * Read in the next compression code. */ MARK(eread) ; if (--incount < 0) { if ((incount = (*getin)()) < 0) { (void) fprintf(stderr, "Premature eof\n") ; err = 1 ; goto eof ; } inptr = inbuf ; } in |= *inptr++ << ibit ; ibit += 16 ; if (ibit >= isize) { code = in & imask ; in >>= isize ; ibit -= isize ; } else { if (--incount < 0) { if ((incount = (*getin)()) < 0) { (void) fprintf(stderr, "Premature eof\n") ; err = 1 ; goto eof ; } inptr = inbuf ; } if (ibit <= 16) { in |= (ulong) *inptr++ << ibit ; code = in & imask ; in >>= isize ; ibit -= isize - 16 ; } else { in |= (ulong) *inptr << ibit ; code = in & imask ; in >>= isize ; in |= (ulong) *inptr++ >> (isize - ibit) ; ibit -= isize - 16 ; } } #if DEBUG >= 4 if (debug >= 4) (void) fprintf(stderr, "Read input code: %05lx\n", code) ; #endif /* * If a zero code is detected, start a new * decompression pass. * * If a character code is detected, output it. */ MARK(eexpand) ; if (code < MAXCHAR) { if (code == 0) break ; ch = code ; } /* * Expand a compression code. * * If the code is the next one to be allocated, * then it was allocated by the compression program * already to be the lastcode + the first character * of the last code. * * Also check for an out-of-range decompression * code. Signal an error in this case. */ else { if (code - MAXCHAR >= ncode) { (void) fprintf(stderr, "Decompress error - attempting resync\n") ; break ; } dp = &dectable[code - MAXCHAR] ; if (dp == sp) { if (sp - dectable == lastcode - MAXCHAR) { (void) fprintf(stderr, "Nasty decompress error - attempting resync\n") ; break ; } *bp++ = ch ; ch = lastcode ; if (ch >= MAXCHAR) { dp = &dectable[ch - MAXCHAR] ; for (;;) { *bp++ = dp->d_char ; ch = dp->d_code ; if (ch < MAXCHAR) break ; dp = &dectable[ch - MAXCHAR] ; } } } else { for (;;) { *bp++ = dp->d_char ; ch = dp->d_code ; if (ch < MAXCHAR) break ; dp = &dectable[ch - MAXCHAR] ; } } } ch -= 1 ; /* * Output the compression code data. */ MARK(eout) ; #if DEBUG >= 3 if (debug >= 3) { ushort *wp ; (void) fprintf(stderr, "Expanded code %05lx to <", code) ; wp = bp ; *wp++ = ch ; do { (void) fprintf(stderr, " %04x", *--wp) ; } while (wp != buffer) ; (void) fprintf(stderr, " >\n") ; } #endif if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = ch ; while (bp != buffer) { if (--outcount <= 0) { if ((outcount = (*putout)(outbs)) == 0) return(1) ; outptr = outbuf ; } *outptr++ = *--bp ; } /* * Create a new code from the input data. */ MARK(ebuild) ; sp->d_code = lastcode ; sp->d_char = ch ; sp->d_ref = 0 ; sp++ ; if (lastcode >= MAXCHAR) dectable[lastcode - MAXCHAR].d_ref = 1 ; #if DEBUG >= 3 if (debug >= 3) { (void) fprintf(stderr, "Created compression code: %05lx ( %05lx %04x )\n", sp - dectable + MAXCHAR - 1, lastcode, ch) ; } #endif } state = 0 ; } eof: nbyte = (long)outptr - (long)outbuf ; if (eofmagic == ODDMAGIC) nbyte-- ; if (nbyte && (*putout)(nbyte) == 0) return(1) ; if (!quiet && intotal != 0) { (void) fprintf(stderr, "Read %ld, Wrote %ld, Expansion %6.2f%%\n", intotal, outtotal, 100.0 * (long)(outtotal - intotal) / intotal) ; } return(err) ; } /************************************************************** * main - main program. **************************************************************/ main(argc, argv) int argc ; char **argv ; { register int i ; register int c ; register int err ; register int rs ; register char *p ; extern char *optarg ; extern int optind ; /* * Set default parameters. */ infd = 0 ; outfd = 1 ; inbs = BUFSIZ ; outbs = BUFSIZ ; memory = MEMORY ; maxwidth = 17 ; inrun = INRUN ; /* * If command begins with 'e' or 'u', expand the * input file. Otherwise compress it. */ p = argv[0] ; action = *p ; while (*p) if (*p++ == '/') action = *p ; if (action == 'u') action = 'e' ; else if (action != 'e') action = 'c' ; #if DEBUG >= 1 debug = DEBUG ; #endif /* * Unpack parameters. */ err = 0 ; for (;;) { c = getopt(argc, argv, "a:b:B:cd:ef:F:lm:n:N:p:qr:R:sSt:T:uvw:xXz:") ; if (c == EOF) break ; switch (c) { /* * Media setup command to be performed before * first open. */ case 'a': acommand = optarg ; break ; /* * Input/output block size. */ case 'b': inbs = getval(optarg, 'k') ; if (inbs <= 2 || (inbs & 1)) err++ ; break ; case 'B': outbs = getval(optarg, 'k') ; if (outbs <= 2 || (outbs & 1)) err++ ; break ; /* * Compress or expand action. */ case 'c': case 'e': action = c ; break ; /* * Debug level. */ #if DEBUG >= 1 case 'd': debug = atoi(optarg) ; if (debug > DEBUG) err++ ; break ; #endif /* * Input/Output file name. */ case 'f': infname = optarg ; break ; case 'F': outfname = optarg ; break ; /* * Lock process into memory. */ case 'l': memlock = 1 ; break ; /* * Amount of memory to use. */ case 'm': memory = getval(optarg, 'k') ; if (memory < 1) err++ ; break ; /* * Physical record size. Causes the last output * record to be padded with zeros to the next * multiple of this size if necessary. */ case 'p': phys = getval(optarg, 'k') ; if (phys <= 2 || (phys & 1)) err++ ; break ; /* * Quiet mode. */ case 'q': quiet = 1 ; break ; /* * Number of input/output records in volume. */ case 'n': insize = getval(optarg, 'k') ; if (insize < 1) err++ ; break ; case 'N': outsize = getval(optarg, 'k') ; if (outsize < 1) err++ ; break ; /* * Maximum run length. */ case 'r': inrun = getval(optarg, 0) ; if (inrun < 5) err++ ; break ; /* * Swap input or output bytes. */ case 's': inswap++ ; break ; case 'S': outswap++ ; break ; /* * Tank size. */ case 't': intank = getval(optarg, 0) ; if (intank < 2 || intank > 500) err++ ; break ; case 'T': outtank = getval(optarg, 0) ; if (outtank < 2 || outtank > 500) err++ ; break ; /* * Uncompress. */ case 'u': action = 'e' ; break ; /* * Version. */ case 'v': #if DEBUG >= 1 (void) fprintf(stderr, "%s (debug %d)\n", VERSION, DEBUG) ; #else (void) fprintf(stderr, "%s\n", VERSION) ; #endif return(0) ; /* * Maximum output bit width. */ case 'w': maxwidth = getval(optarg, 0) ; if (maxwidth < 17 || maxwidth > 24) err++ ; break ; /* * Read/Write data to/from non-shared memory buffers * to avoid driver problems. */ case 'x': incopy = 1 ; break ; case 'X': outcopy = 1 ; break ; /* * Command to be performed after last close. */ case 'z': zcommand = optarg ; break ; default: err++ ; } } /* * Check parameter consistency. */ if (insize && !infname) { (void) fprintf(stderr, "-n requires -f\n") ; err++ ; } if (outsize && !outfname) { (void) fprintf(stderr, "-N requires -F\n") ; err++ ; } /* * Print the USAGE message. */ if (optind != argc || err) { (void) fprintf(stderr, "Usage: %s %s%s%s", argv[0], "[-celqsSvxX] [-a cmd] [-b cbs] [-B ebs] [-f cfile] [-F efile]\n", "\t[-m memory] [-n cblks] [-N eblks] [-p outpad] [-r runsize]\n", "\t[-t cbuf] [-T ebuf] [-w width] [-z cmd]\n") ; exit(2) ; } /* * Adjust compression parameters. */ if (action == 'c') { long i ; char *p ; /* * Switch parameters around if necessary so the lower * case options refer to the compressed file, and the * upper case letters refer to the expanded file. */ if (phys == 0) phys = 512 ; i = insize ; insize = outsize ; outsize = i ; i = inbs ; inbs = outbs ; outbs = i ; i = intank ; intank = outtank ; outtank = i ; i = inswap ; inswap = outswap ; outswap = i ; i = incopy ; incopy = outcopy ; outcopy = i ; p = infname ; infname = outfname ; outfname = p ; } /* * Adjust output block size to correspond with * the requested output padding. */ if (phys) { if (outbs < phys) outbs = phys ; else outbs = (outbs + phys - 1) / phys * phys ; } /* * Execute setup command. */ if (acommand) (void) system(acommand) ; /* * Setup input operation through shared memory. */ if (intank) { inprocess() ; getin = shareinput ; } else { inbuf = (ushort *) malloc((unsigned) inbs+1) ; getin = fileinput ; } /* * Setup output operation through shared memory. */ if (outtank) { outprocess() ; putout = shareoutput ; } else { outbuf = (ushort *) malloc((unsigned) outbs) ; putout = fileoutput ; } /* * Lock process into memory. */ if (memlock && plock(PROCLOCK) == -1) { (void) perror("Cannot lock process in memory") ; return(2) ; } /* * Setup to gracefully exit. */ for (i = 0 ; sig[i] ; i++) { if (signal(sig[i], SIG_IGN) != SIG_IGN) (void) signal(sig[i], quit) ; } /* * Compress or expand input data. */ rs = action == 'c' ? compact() : expand() ; quit(rs) ; return(0) ; }