From:	CSBVAX::MRGATE!A.Harper@OAK.CC.KCL.AC.UK@SMTP 10-SEP-1988 03:11
To:	ARISIA::EVERHART
Subj:	arc mods pt 5


Received: from UKACRL.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.1) with BSMTP id 3683; Fri, 09 Sep 88 07:15:11 EDT
Received: from RL.IB by UKACRL.BITNET (Mailer X1.25) with BSMTP id 0254; Fri,
 09 Sep 88 12:12:01 BST
Received: from RL.IB by UK.AC.RL.IB (Mailer X1.25) with BSMTP id 0113; Fri, 09
          Sep 88 12:11:59 BS
Via:      UK.AC.KCL.CC.OAK;  9 SEP 88 12:08:08 BST
Date:     9-SEP-1988 12:08:53 GMT
From:     UDAA055%OAK.CC.KCL.AC.UK@CUNYVM.CUNY.EDU
To:       everhart%arisia.decnet@GE-CRD.ARPA
Subject:  arc mods pt 5
Sender:   Andy Harper, Kings College London <A.Harper%OAK.CC.KCL.AC.UK@CUNYVM.CUNY.EDU>

Here are the ARC mods pt 5, as requested.

Regards,

Andy Harper
Kings College london Uk

From:    OAK::UDAA055      "Andy, Systems Manager"  1-SEP-1988 13:58
To:    EARN%"info-vax@com.sri.kl",UDAA055
Subj:    ARC mods 5/7

+-+-+-+ Beginning of part 5 +-+-+-+
X         ‡
X
X         /*
X          * If the next entry is going to be too big for the code size,
X          * then increase it, if possible.
X          */
X         if(free_ent>maxcode || clear_flg>0)
X         ¤    /*
X               * Write the whole buffer, because the input side won't
X               * discover the size increase until after it has read it.
X               */
X              if(offset > 0)
X              ¤    bp = buf;           /* reset pointer for writing */
X                   bytes_out += n = n_bits;
X                   while(n--)
X                        putc_pak(*bp++,t);
X              ‡
X              offset = 0;
X
X              if(clear_flg)            /* reset if clearing */
X              ¤    maxcode = MAXCODE(n_bits = INIT_BITS);
X                   clear_flg = 0;
X              ‡
X              else                     /* else use more bits */
X              ¤    n_bits++;
X                   if(n_bits == BITS)
X                        maxcode = maxcodemax;
X                   else
X                        maxcode = MAXCODE(n_bits);
X              ‡
X         ‡
X    ‡
X
X    else                               /* dump the buffer on EOF */
X    ¤    bytes_out += n = (offset+7) / 8;
X
X         if(offset > 0)
X              while(n--)
X                   putc_pak(*bp++,t);
X         offset = 0;
X    ‡
X‡
X
X/*****************************************************************
X *
X * Read one code from the standard input.  If EOF, return -1.
X * Inputs:
X *      cmpin
X * Outputs:
X *      code or -1 is returned.
X */
X
Xstatic INT getcode(f)                  /* get a code */
XFILE *f;                               /* file to get from */
X¤
X INT code;
X    static INT offset = 0, size = 0;
X INT r_off, bits;
X    unsigned char *bp = buf;
X
X    if(clear_flg > 0 || offset >= size || free_ent > maxcode)
X    ¤    /*
X          * If the next entry will be too big for the current code
X          * size, then we must increase the size.  This implies reading
X          * a new buffer full, too.
X          */
X         if(free_ent > maxcode)
X         ¤    n_bits++;
X              if(n_bits == BITS)
X                   maxcode = maxcodemax;    /* won't get any bigger now */
X              else maxcode = MAXCODE(n_bits);
X         ‡
X         if(clear_flg > 0)
X         ¤    maxcode = MAXCODE(n_bits = INIT_BITS);
X              clear_flg = 0;
X         ‡
X
X         for(size=0; size<n_bits; size++)
X         ¤    if((code=getc_unp(f))==EOF)
X                   break;
X              else buf[size] = code;
X         ‡
X         if(size <= 0)
X              return -1;               /* end of file */
X
X         offset = 0;
X         /* Round size down to integral number of codes */
X         size = (size << 3)-(n_bits - 1);
X    ‡
X    r_off = offset;
X    bits = n_bits;
X
X    /*
X     * Get to the first byte.
X     */
X    bp +=(r_off >> 3);
X    r_off &= 7;
X
X    /* Get first part (low order bits) */
X    code = (*bp++ >> r_off);
X    bits -= 8 - r_off;
X    r_off = 8 - r_off;                 /* now, offset into code word */
X
X    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
X    if(bits >= 8)
X    ¤    code |= *bp++ << r_off;
X         r_off += 8;
X         bits -= 8;
X    ‡
X    /* high order bits. */
X    code |= (*bp & rmask[bits]) << r_off;
X    offset += n_bits;
X
X    return code;
X‡
X
X/*
X * compress a file
X *
X * Algorithm:  use open addressing double hashing (no chaining) on the
X * prefix code / next character combination.  We do a variant of Knuth's
X * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
X * secondary probe.  Here, the modular division first probe is gives way
X * to a faster exclusive-or manipulation.  Also do block compression with
X * an adaptive reset, where the code table is cleared when the compression
X * ratio decreases, but after the table fills.  The variable-length output
X * codes are re-sized at this point, and a special CLEAR code is generated
X * for the decompressor.
X */
X
XINT init_cm(f,t)                           /* initialize for compression */
XFILE *f;                               /* file we will be compressing */
XFILE *t;                               /* where we will put it */
X¤
X    offset = 0;
X    bytes_out = 1;
X    clear_flg = 0;
X    ratio = 0;
X    in_count = 1;
X    checkpoint = CHECK_GAP;
X    maxcode = MAXCODE(n_bits = INIT_BITS);
X    free_ent = FIRST;
X    setmem(htab,HSIZE*sizeof(long),0xff);
X    n_bits = INIT_BITS;                /* set starting code size */
X
X    putc_pak(BITS,t);                  /* note our max code length */
X
X    firstcmp = 1;                      /* next byte will be first */
X‡
X
XINT putc_cm(c,t)                           /* compress a character */
Xunsigned char c;                       /* character to compress */
XFILE *t;                               /* where to put it */
X¤
X    static long fcode;
X    static INT hshift;
X register INT i;
X register INT disp;
X
X    if(firstcmp)                       /* special case for first byte */
X    ¤    ent = c;                      /* remember first byte */
X
X         hshift = 0;
X         for(fcode=(long)HSIZE;  fcode<65536L; fcode*=2L)
X              hshift++;
X         hshift = 8 - hshift;          /* set hash code range bund */
X
X         firstcmp = 0;                 /* no longer first */
X         return;
X    ‡
X
X    in_count++;
X    fcode =(long)(((long)c << BITS)+ent);
X    i = (c<<hshift)ˆent;               /* xor hashing */
X
X    if(htab[i]==fcode)
X    ¤    ent = codetab[i];
X         return;
X    ‡
X    else if(htab[i]<0)                 /* empty slot */
X         goto nomatch;
X    disp = HSIZE - i;                  /* secondary hash (after G.Knott) */
X    if(i == 0)
X         disp = 1;
X
Xprobe:
X    if((i -= disp) < 0)
X         i += HSIZE;
X
X    if(htab[i] == fcode)
X    ¤    ent = codetab[i];
X         return;
X    ‡
X    if(htab[i] > 0)
X         goto probe;
X
Xnomatch:
X    putcode(ent,t);
X    ent = c;
X    if(free_ent < maxcodemax)
X    ¤    codetab[i] = free_ent++;      /* code -> hashtable */
X         htab[i] = fcode;
X    ‡
X    else if((long)in_count >= checkpoint)
X         cl_block(t);
X‡
X
Xlong pred_cm(t)                        /* finish compressing a file */
XFILE *t;                               /* where to put it */
X¤
X    putcode(ent,t);                    /* put out the final code */
X    putcode(-1,t);                     /* tell output we are done */
X
X    return bytes_out;                  /* say how big it got */
X‡
X
X/*
X * Decompress a file.  This routine adapts to the codes in the file
X * building the string table on-the-fly; requiring no table to be stored
X * in the compressed file.  The tables used herein are shared with those of
X * the compress() routine.  See the definitions above.
X */
X
XINT decomp(f,t)                            /* decompress a file */
XFILE *f;                               /* file to read codes from */
XFILE *t;                               /* file to write text to */
X¤
X    unsigned char *stackp;
X INT finchar;
X INT code, oldcode, incode;
X
X    if((code=getc_unp(f))!=BITS)
X         abort("File packed with %d bits, I can only handle %d",code,BITS);
X
X    n_bits = INIT_BITS;                /* set starting code size */
X    clear_flg = 0;
X
X    /*
X     * As above, initialize the first 256 entries in the table.
X     */
X    maxcode = MAXCODE(n_bits=INIT_BITS);
X    for(code = 255; code >= 0; code--)
X    ¤    prefix[code] = 0;
X         suffix[code] = (unsigned char)code;
X    ‡
X    free_ent = FIRST;
X
X    finchar = oldcode = getcode(f);
X    if(oldcode == -1)                  /* EOF already? */
X         return;                       /* Get out of here */
X    putc_ncr((char)finchar,t);         /* first code must be 8 bits=char */
X    stackp = stack;
X
X    while((code = getcode(f))> -1)
X    ¤    if(code==CLEAR)
X         ¤    for(code = 255; code >= 0; code--)
X                   prefix[code] = 0;
X              clear_flg = 1;
X              free_ent = FIRST - 1;
X              if((code=getcode(f))==-1)/* O, untimely death! */
X                   break;
X         ‡
X         incode = code;
X         /*
X          * Special case for KwKwK string.
X          */
X         if(code >= free_ent)
X         ¤    *stackp++ = finchar;
X              code = oldcode;
X         ‡
X
X         /*
X          * Generate output characters in reverse order
X          */
X         while(code >= 256)
X         ¤    *stackp++ = suffix[code];
X              code = prefix[code];
X         ‡
X         *stackp++ = finchar = suffix[code];
X
X         /*
X          * And put them out in forward order
X          */
X         do
X              putc_ncr(*--stackp,t);
X         while(stackp > stack);
X
X         /*
X          * Generate the new entry.
X          */
X         if((code=free_ent) < maxcodemax)
X         ¤    prefix[code] = (unsigned short)oldcode;
X              suffix[code] = finchar;
X              free_ent = code+1;
X         ‡
X         /*
X          * Remember previous code.
X          */
X         oldcode = incode;
X    ‡
X‡
X
X
X/*************************************************************************
X * Please note how much trouble it can be to maintain upwards            *
X * compatibility.  All that follows is for the sole purpose of unpacking *
X * files which were packed using an older method.                        *
X *************************************************************************/
X
X
X/*  The h() pointer points to the routine to use for calculating a hash
X    value.  It is set in the init routines to point to either of oldh()
X    or newh().
X
X    oldh() calculates a hash value by taking the middle twelve bits
X    of the square of the key.
X
X    newh() works somewhat differently, and was tried because it makes
X    ARC about 23% faster.  This approach was abandoned because dynamic
X    Lempel-Zev (above) works as well, and packs smaller also.  However,
X    inadvertent release of a developmental copy forces us to leave this in.
X*/
X
Xstatic unsigned INT (*h)();                /* pointer to hash function */
X
Xstatic unsigned INT oldh(pred,foll)        /* old hash function */
Xunsigned INT pred;                     /* code for preceeding string */
Xunsigned char foll;                    /* value of following char */
X¤
X    long local;                        /* local hash value */
X
X    local = ((pred + foll) | 0x0800) & 0xffff;    /* create the hash key */
X    /*local = (pred + foll) | 0x0800;    /* create the hash key */
X    local *= local;                    /* square it */
X    return (local >> 6) & 0x0FFF;      /* return the middle 12 bits */
X‡
X
Xstatic unsigned INT newh(pred,foll)        /* new hash function */
Xunsigned INT pred;                     /* code for preceeding string */
Xunsigned char foll;                    /* value of following char */
X¤
X    return (((pred+foll)&0xffff)*15073)&0xFFF;  /* faster hash */
X    /*return ((pred+foll)*15073)&0xFFF;  /* faster hash */
X‡
X
X/*  The eolist() function is used to trace down a list of entries with
X    duplicate keys until the last duplicate is found.
X*/
X
Xstatic unsigned INT eolist(index)          /* find last duplicate */
Xunsigned INT index;
X¤
X INT temp;
X
X    while(temp=string_tab[index].next) /* while more duplicates */
X         index = temp;
X
X    return index;
X‡
X
X/*  The hash() routine is used to find a spot in the hash table for a new
X    entry.  It performs a "hash and linear probe" lookup, using h() to
X    calculate the starting hash value and eolist() to perform the linear
X    probe.  This routine DOES NOT detect a table full condition.  That
X    MUST be checked for elsewhere.
X*/
X
Xstatic unsigned INT hash(pred,foll)        /* find spot in the string table */
Xunsigned INT pred;                     /* code for preceeding string */
Xunsigned char foll;                    /* char following string */
X¤
X    unsigned INT local, tempnext;      /* scratch storage */
X    struct entry *ep;                  /* allows faster table handling */
X
X    local = (*h)(pred,foll);           /* get initial hash value */
X
X    if(!string_tab[local].used)        /* if that spot is free */
X         return local;                 /* then that's all we need */
X
X    else                               /* else a collision has occured */
X    ¤    local = eolist(local);        /* move to last duplicate */
X
X         /*   We must find an empty spot. We start looking 101 places
X              down the table from the last duplicate.
X         */
X
X         tempnext = (local+101) & 0x0FFF;
X         ep = &string_tab[tempnext];   /* initialize pointer */
X
X         while(ep->used)               /* while empty spot not found */
X         ¤    if(++tempnext==TABSIZE)  /* if we are at the end */
X              ¤    tempnext = 0;       /* wrap to beginning of table*/
X                   ep = string_tab;
X              ‡
X              else ++ep;               /* point to next element in table */
X         ‡
X
X         /*   local still has the pointer to the last duplicate, while
X              tempnext has the pointer to the spot we found.  We use
X              this to maintain the chain of pointers to duplicates.
X         */
X
X         string_tab[local].next = tempnext;
X
X         return tempnext;
X    ‡
X‡
X
X/*  The unhash() function is used to search the hash table for a given key.
X    Like hash(), it performs a hash and linear probe search.  It returns
X    either the number of the entry (if found) or NOT_FND (if not found).
X*/
X
Xstatic unsigned INT unhash(pred,foll)      /* search string table for a key */
Xunsigned INT pred;                     /* code of preceeding string */
Xunsigned char foll;                    /* character following string */
X¤
X    unsigned INT local, offset;        /* scratch storage */
X    struct entry *ep;                  /* this speeds up access */
X
X    local = (*h)(pred,foll);           /* initial hash */
X
X    while(1)
X    ¤    ep = &string_tab[local];      /* speed up table access */
X
X         if((ep->predecessor==pred) && (ep->follower==foll))
X              return local;            /* we have a match */
X
X         if(!ep->next)                 /* if no more duplicates */
X              return NOT_FND;          /* then key is not listed */
X
X         local = ep->next;             /* move on to next duplicate */
X    ‡
X‡
X
X/*  The init_tab() routine is used to initialize our hash table.
X    You realize, of course, that "initialize" is a complete misnomer.
X*/
X
Xstatic INT init_tab()                      /* set ground state in hash table */
X¤
X    unsigned INT i;                    /* table index */
X    INT upd_tab();
X
X    setmem((char *)string_tab,sizeof(string_tab),0);
X
X    for(i=0; i<256; i++)               /* list all single byte strings */
X         upd_tab(NO_PRED,i);
X
-+-+-+-+-+ End of part 5 +-+-+-+-+-
