From:	CSBVAX::MRGATE!RELAY-INFO-VAX@CRVAX.SRI.COM@SMTP  2-SEP-1988 08:55
To:	ARISIA::EVERHART
Subj:	ARC mods 6/7


Received: From KL.SRI.COM by CRVAX.SRI.COM with TCP; Thu,  1 SEP 88 06:28:07 PDT
Received: from CUNYVM.CUNY.EDU by KL.SRI.COM with TCP; Thu, 1 Sep 88 06:03:52 PDT
Received: from UKACRL.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 7778; Thu, 01 Sep 88 09:00:52 EDT
Received: from RL.IB by UKACRL.BITNET (Mailer X1.25) with BSMTP id 3263; Thu,
 01 Sep 88 13:59:02 BST
Received: from RL.IB by UK.AC.RL.IB (Mailer X1.25) with BSMTP id 3259; Thu, 01
          Sep 88 13:59:00 BS
Via:      UK.AC.KCL.CC.OAK;  1 SEP 88 13:58:46 BST
Date:     1-SEP-1988 13:59:30 GMT
From:     UDAA055%OAK.CC.KCL.AC.UK@CUNYVM.CUNY.EDU
To:       info-vax@KL.SRI.COM
Subject:  ARC mods 6/7
Sender:   Andy Harper, Kings College London <A.Harper%OAK.CC.KCL.AC.UK@CUNYVM.CUNY.EDU>

+-+-+-+ Beginning of part 6 +-+-+-+
X    inbuf = EMPTY;                     /* nothing is in our buffer */
X
X
X/*  The upd_tab routine is used to add a new entry to the string table.
X    As previously stated, no checks are made to ensure that the table
X    has any room.  This must be done elsewhere.
X*/
X
XINT upd_tab(pred,foll)                     /* add an entry to the table */
Xunsigned INT pred;                     /* code for preceeding string */
Xunsigned INT foll;                     /* character which follows string */
X$
X    struct entry *ep;                  /* pointer to current entry */
X
X    /* calculate offset just once */
X
X    ep = &string_tab[hash(pred,foll)];
X
X    ep->used = TRUE;                   /* this spot is now in use */
X    ep->next = 0;                      /* no duplicates after this yet */
X    ep->predecessor = pred;            /* note code of preceeding string */
X    ep->follower = foll;               /* note char after string */
X
X
X/*  This algorithm encoded a file into twelve bit strings (three nybbles).
X    The gocode() routine is used to read these strings a byte (or two)
X    at a time.
X*/
X
Xstatic INT gocode(fd)                      /* read in a twelve bit code */
XFILE *fd;                              /* file to get code from */
X$
X    unsigned INT localbuf, returnval;
X
X    if(inbuf==EMPTY)                   /* if on a code boundary */
X    $    if((localbuf=getc_unp(fd))==EOF)   /* get start of next code */
X              return EOF;              /* pass back end of file status */
X         localbuf &= 0xFF;             /* mask down to true byte value */
X         if((inbuf=getc_unp(fd))==EOF) /* get end of code, start of next */
X              return EOF;              /* this should never happen */
X         inbuf &= 0xFF;                /* mask down to true byte value */
X
X         returnval = ((localbuf<<4)&0xFF0) + ((inbuf>>4)&0x00F);
X         inbuf &= 0x000F;              /* leave partial code pending */
X    
X
X    else                               /* buffer contains first nybble */
X    $    if((localbuf=getc_unp(fd))==EOF)
X              return EOF;
X         localbuf &= 0xFF;
X
X         returnval = localbuf + ((inbuf<<8)&0xF00);
X         inbuf = EMPTY;                /* note no hanging nybbles */
X    
X    return returnval;                  /* pass back assembled code */
X
X
Xstatic INT push(c)                         /* push char onto stack */
XINT c;                                 /* character to push */
X$
X    stack[sp] = ((char) c);            /* coerce integer into a char */
X
X    if(++sp >= TABSIZE)
X         abort("Stack overflow\n");
X
X
Xstatic INT pop()                       /* pop character from stack */
X$
X    if(sp>0)
X         return ((INT) stack[--sp]);   /* leave ptr at next empty slot */
X
X    else return EMPTY;
X
X
X/***** LEMPEL-ZEV DECOMPRESSION *****/
X
Xstatic INT code_count;                 /* needed to detect table full */
Xstatic unsigned INT code;                  /* where we are so far */
Xstatic INT firstc;                     /* true only on first character */
X
XINT init_ucr(new)                          /* get set for uncrunching */
XINT new;                               /* true to use new hash function */
X$
X    if(new)                            /* set proper hash function */
X         h = newh;
X    else h = oldh;
X
X    sp = 0;                            /* clear out the stack */
X    init_tab();                        /* set up atomic code definitions */
X    code_count = TABSIZE - 256;        /* note space left in table */
X    firstc = 1;                        /* true only on first code */
X
X
XINT getc_ucr(f)                        /* get next uncrunched byte */
XFILE *f;                               /* file containing crunched data */
X$
X    unsigned INT c;                    /* a character of input */
X INT code, newcode;
X    static INT oldcode, finchar;
X    struct entry *ep;                  /* allows faster table handling */
X
X    if(firstc)                         /* first code is always known */
X    $    firstc = FALSE;               /* but next will not be first */
X         oldcode = gocode(f);
X         return finchar = string_tab[oldcode].follower;
X    
X
X    if(!sp)                            /* if stack is empty */
X    $    if((code=newcode=gocode(f))==EOF)
X              return EOF;
X
X         ep = &string_tab[code];       /* initialize pointer */
X
X         if(!ep->used)                 /* if code isn't known */
X         $    code = oldcode;
X              ep = &string_tab[code];  /* re-initialize pointer */
X              push(finchar);
X         
X
X         while(ep->predecessor!=NO_PRED)
X         $    push(ep->follower);      /* decode string backwards */
X              code = ep->predecessor;
X              ep = &string_tab[code];
X         
X
X         push(finchar=ep->follower);   /* save first character also */
X
X         /*   The above loop will terminate, one way or another,
X              with string_tab[code].follower equal to the first
X              character in the string.
X         */
X
X         if(code_count)                /* if room left in string table */
X         $    upd_tab(oldcode,finchar);
X              --code_count;
X         
X
X         oldcode = newcode;
X    
X
X    return pop();                      /* return saved character */
X
X
$ GOSUB UNPACK_FILE
$ FILE_IS = "ARCPACK.C"
$ CHECKSUM_IS = 1986289896
$ COPY SYS$INPUT VMS_SHARE_DUMMY.DUMMY
Xstatic char *RCSid = "$Header: arcpack.c,v 1.2 86/07/15 07:53:48 turner Exp $";
X
X/*
X * $Log:`009arcpack.c,v $
X * VAXC modifications       31-AUG-1988`009`009Andy Harper, KCL
X * Separated VAXC and BSD dependencies
X *
X * Hack-attack 1.3  86/12/20  01:23:45  wilhite@usceast.uucp
X * `009Bludgeoned into submission for VAX 11/780 BSD4.2
X *`009(ugly code, but fewer core dumps)
X *
X * Revision 1.2  86/07/15  07:53:48  turner
X *
X *
X * Revision 1.1  86/06/26  15:00:37  turner
X * initial version
X *
X *
X */
X
X/*  ARC - Archive utility - ARCPACK
X
X$define(tag,$$segment(@1,$$index(@1,=)+1))#
X$define(version,Version $tag(
XTED_VERSION DB =3.37), created on $tag(
XTED_DATE DB =02/03/86) at $tag(
XTED_TIME DB =22:58:01))#
X$undefine(tag)#
X    $version
X
X(C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
X
X    By:  Thom Henderson
X
X    Description:
X         This file contains the routines used to compress a file
X         when placing it in an archive.
X
X    Language:
X         Computer Innovations Optimizing C86
X*/
X#include <stdio.h>
X#include "arc.h"
X
X/* stuff for non-repeat packing */
X
X#define DLE 0x90                       /* repeat sequence marker */
X
Xstatic unsigned char state;            /* current packing state */
X
X/* non-repeat packing states */
X
X#define NOHIST  0                      /* don't consider previous input*/
X#define SENTCHAR 1                     /* lastchar set, no lookahead yet */
X#define SENDNEWC 2                     /* run over, send new char next */
X#define SENDCNT 3                      /* newchar set, send count next */
X
X/* packing results */
X
Xstatic long stdlen;                    /* length for standard packing */
Xstatic INT crcval;                     /* CRC check value */
X
XINT pack(f,t,hdr)                          /* pack file into an archive */
XFILE *f, *t;                           /* source, destination */
Xstruct heads *hdr;                     /* pointer to header data */
X$
X INT c;                             /* one character of stream */
X    long ncrlen;                       /* length after packing */
X    long huflen;                       /* length after squeezing */
X    long lzwlen;                       /* length after crunching */
X    long pred_sq(), file_sq();         /* stuff for squeezing */
X    long pred_cm(), sqpred_cm();       /* dynamic crunching cleanup */
X    char tnam[STRLEN];                /* temporary name buffer */
X    char *makefnam();                  /* filename fixer upper */
X    FILE *crn = NULL;                  /* temporary crunch file */
X    INT getch();
X    INT getc_ncr();
X    INT putc_pak();
X
X    /* first pass - see which method is best */
X
X    if(!nocomp)                        /* if storage kludge not active */
X    $    if(note)
X            $ printf(" analyzing, "); fflush(stdout);
X
X         if(arctemp)                   /* use temp area if specified */
X              sprintf(tnam,"%s.CRN",arctemp);
X         else makefnam("$ARCTEMP.CRN",arcname,tnam);
X#if MSDOS
X         crn = fopen(tnam,"wrb");
X#endif
X#if VAXC | BSD | ST
X         crn = fopen(tnam,"w+");
X#endif
X         state = NOHIST;               /* initialize ncr packing */
X         stdlen =  ncrlen = 0;         /* reset size counters */
X         crcval = 0;                   /* initialize CRC check value */
X         setcode();                    /* initialize encryption */
X
X`009 if(dosquash)
X         sqinit_cm(f,crn);
X`009 else
X         init_cm(f,crn);               /* initialize for crunching */
X         init_sq();                    /* initialize for squeeze scan */
X
X`009 if(dosquash)
X         while((c=getch(f))!=EOF)   /* for each byte of file */
X         $    ncrlen++;                /* one more packed byte */
X              scan_sq(c);              /* see what squeezing can do */
X              sqputc_cm(c,crn);          /* see what crunching can do */
X         
X         else
X         while((c=getc_ncr(f))!=EOF)   /* for each byte of file */
X         $    ncrlen++;                /* one more packed byte */
X              scan_sq(c);              /* see what squeezing can do */
X              putc_cm(c,crn);          /* see what crunching can do */
X         
X         huflen = pred_sq();           /* finish up after squeezing */
X`009 if(dosquash)
X         lzwlen = sqpred_cm(crn);
X`009 else
X         lzwlen = pred_cm(crn);        /* finish up after crunching */
X    
X    else                               /* else kludge the method */
X    $    stdlen = 0;                   /* make standard look best */
X         ncrlen = huflen = lzwlen = 1;
X    
X
X    /* standard set-ups common to all methods */
X
X    fseek(f,0L,0);                     /* rewind input */
X    hdr->crc = crcval;                 /* note CRC check value */
X    hdr->length = stdlen;              /* set actual file length */
X    state = NOHIST;                    /* reinitialize ncr packing */
X    setcode();                         /* reinitialize encryption */
X
X    /* choose and use the shortest method */
X
X    if(stdlen<=ncrlen && stdlen<=huflen && stdlen<=lzwlen)
X    $    if(kludge)                    /*DEBUG*/
X              printf("(%ld) ",lzwlen-stdlen);
X         if(note)
X          $ printf("storing, "); fflush(stdout);/* store w/out compression */
X         hdrver = 2;                   /* note packing method */
X         stdlen = crcval = 0;          /* recalc these for kludge */
X         while((c=getch(f))!=EOF)      /* store it straight */
X              putc_pak(c,t);
X         hdr->crc = crcval;
X         hdr->length = hdr->size = stdlen;
X    
X
X    else if(ncrlen<huflen && ncrlen<lzwlen)
X    $    if(kludge)                    /*DEBUG*/
X              printf("(%ld) ",lzwlen-ncrlen);
X         if(note)
X              $ printf("packing, ");
X              fflush(stdout); /* pack w/repeat suppression */
X         hdrver = 3;                   /* note packing method */
X         hdr->size = ncrlen;           /* set data length */
X         while((c=getc_ncr(f))!=EOF)
X              putc_pak(c,t);
X    
X
X    else if(huflen<lzwlen)
X    $    if(kludge)                    /*DEBUG*/
X              printf("(%ld) ",lzwlen-huflen);
X         if(note)
X            $ printf("squeezing, "); fflush(stdout);
X         hdrver = 4;                   /* note packing method */
X         hdr->size = file_sq(f,t);     /* note final size */
X    
X
X    else
X    $    if(kludge)                    /*DEBUG*/
X              printf("(%ld) ",huflen-lzwlen);
X         if(note)
V            $ printf(dosquash ? "squashing, " : "crunching, "); fflush(stdout);
X
X         hdrver = dosquash ? 9 : 8;
X         hdr->size = lzwlen;           /* size should not change */
X         if(crn)                       /* if temp was created */
X         $    fseek(crn,0L,0);         /* then copy over crunched temp */
X              while((c=fgetc(crn))!=EOF)
X                   putc_tst(c,t);
X         
X         else                          /* else re-crunch */
X         $    if(dosquash)
X`009`009sqinit_cm(f, t);
X`009      else
X`009`009init_cm(f,t);
X`009   if(dosquash)
X              while((c=getc_ncr(f))!=EOF)
X`009`009`009putc_cm(c,t);
X`009   else
X              while((c=getch(f))!=EOF)
X`009`009`009sqputc_cm(c,t);
X`009      if(dosquash)
X`009`009sqpred_cm(t);
X`009      else
X`009`009pred_cm(t);              /* finish up after crunching */
X         
X    
X
X    /* standard cleanups common to all methods */
X
X    if(crn)                            /* get rid of crunch temporary */
X    $    fclose(crn);
X         if(unlink(tnam) && warn)
X         $    printf("Cannot delete temporary file %s\n",tnam);
X              nerrs++;
X         
X    
X    if(note)
X         printf("done.\n");
X
X
X/*  Non-repeat compression - text is passed through normally, except that
X    a run of more than two is encoded as:
X
X         <char> <DLE> <count>
X
X    Special case: a count of zero indicates that the DLE is really a DLE,
X    not a repeat marker.
X*/
X
XINT getc_ncr(f)                        /* get bytes with collapsed runs */
XFILE *f;                               /* file to get from */
X$
X#if vaxc
X    INT getch();
X#endif
X    static INT lastc;                  /* value returned on last call */
X    static INT repcnt;                 /* repetition counter */
X    static INT c;                      /* latest value seen */
X
X    switch(state)                      /* depends on our state */
X    $
X    case NOHIST:                       /* no relevant history */
X         state = SENTCHAR;
X         return (lastc = getch(f));      /* remember the value next time */
X
X    case SENTCHAR:                     /* char was sent. look ahead */
X         switch(lastc)                 /* action depends on char */
X         $
X         case DLE:                     /* if we sent a real DLE */
X              state = NOHIST;          /* then start over again */
X              return 0;                /* but note that the DLE was real */
X
X         case EOF:                     /* EOF is always a special case */
X              return EOF;
X
X         default:                      /* else test for a repeat */
X              for(repcnt=1; (c=getch(f))==lastc && repcnt<255; repcnt++)
X                   ;                   /* find end of run */
X
X              switch(repcnt)           /* action depends on run size */
X              $
X              case 1:                  /* not a repeat */
X                   return lastc = c;   /* but remember value next time */
X
-+-+-+-+-+ End of part 6 +-+-+-+-+-

