Path: utzoo!attcan!uunet!lll-winken!lll-lcc!lll-tis!helios.ee.lbl.gov!pasteur!agate!ucbvax!CORNELLC.CCS.CORNELL.EDU.BITNET!ewilts%Ins.MRC.AdhocNet.CA%Stasis.MRC.AdhocNet.CA%UNCAEDU.
From: ewilts%Ins.MRC.AdhocNet.CA%Stasis.MRC.AdhocNet.CA%UNCAEDU.@CORNELLC.CCS.CORNELL.EDU.BITNET (Ed Wilts)
Newsgroups: comp.os.vms
Subject: ARC_C.SHAR13_OF_19
Message-ID: <880624092735.02d@Ins.MRC.AdhocNet.CA>
Date: 24 Jun 88 15:27:33 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 286

X         /* k indexes "smaller" child (in heap of trees) of top */
X         /* now make top index "smaller" of old top and smallest child */
X
X         if(cmptrees(temp,list[k]))
X         {    list[top] = list[k];
X              list[k] = temp;
X
X              /* Make the changed list a heap */
X
X              adjust(list,k,bottom);   /* recursive */
X         }
X    }
X}
X
X/* Compare two trees, if a > b return true, else return false.
X   Note comparison rules in previous comments.
X*/
X
Xstatic INT cmptrees(a,b)
XINT a, b;                              /* root nodes of trees */
X{
X    if(node[a].weight > node[b].weight)
X         return TRUE;
X    if(node[a].weight == node[b].weight)
X         if(node[a].tdepth > node[b].tdepth)
X              return TRUE;
X    return FALSE;
X}
X
X/* HUFFMAN ALGORITHM: develops the single element trees
X   into a single binary tree by forming subtrees rooted in
X   interior nodes having weights equal to the sum of weights of all
X   their descendents and having depth counts indicating the
X   depth of their longest paths.
X
X   When all trees have been formed into a single tree satisfying
X   the heap property (on weight, with depth as a tie breaker)
X   then the binary code assigned to a leaf (value to be encoded)
X   is then the series of left (0) and right (1)
X   paths leading from the root to the leaf.
X   Note that trees are removed from the heaped list by
X   moving the last element over the top element and
X   reheaping the shorter list.
X*/
X
Xstatic INT bld_tree(list,len)
XINT list[];
XINT len;
X{
X    register INT freenode;             /* next free node in tree */
X    register struct nd *frnp;          /* free node pointer */
X INT lch, rch;                      /* temps for left, right children */
X INT i;
X    INT maxchar();
X
X    /* Initialize index to next available (non-leaf) node.
X       Lower numbered nodes correspond to leaves (data values).
X    */
X
X    freenode = NUMVALS;
X
X    while(len>1)
X    {    /* Take from list two btrees with least weight
X            and build an interior node pointing to them.
X            This forms a new tree.
X         */
X
X         lch = list[0];                /* This one will be left child */
X
X         /* delete top (least) tree from the list of trees */
X
X         list[0] = list[--len];
X         adjust(list,0,len-1);
X
X         /* Take new top (least) tree. Reuse list slot later */
X
X         rch = list[0];                /* This one will be right child */
X
X         /* Form new tree from the two least trees using
X            a free node as root. Put the new tree in the list.
X         */
X
X         frnp = &node[freenode];       /* address of next free node */
X         list[0] = freenode++;         /* put at top for now */
X         frnp->lchild = lch;
X         frnp->rchild = rch;
X         frnp->weight = node[lch].weight + node[rch].weight;
X         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
X
X         /* reheap list  to get least tree at top */
X
X         adjust(list,0,len-1);
X    }
X    dctreehd = list[0];                /* head of final tree */
X}
X
Xstatic INT maxchar(a,b)
X{
X    return a>b ? a : b;
X}
X
Xstatic INT init_enc()
X{
X    register INT i;
X
X    /* Initialize encoding table */
X
X    for(i=0; i<NUMVALS; ++i)
X         codelen[i] = 0;
X}
X
X/* Recursive routine to walk the indicated subtree and level
X   and maintain the current path code in bstree. When a leaf
X   is found the entire code string and length are put into
X   the encoding table entry for the leaf's data value .
X
X   Returns ERROR if codes are too long.
X*/
X
Xstatic INT buildenc(level,root)
XINT level;              /* level of tree being examined, from zero */
XINT root;               /* root of subtree is also data value if leaf */
X{
X    register INT l, r;
X
X    l = node[root].lchild;
X    r = node[root].rchild;
X
X    if(l==NOCHILD && r==NOCHILD)
X    {    /* Leaf. Previous path determines bit string
X            code of length level (bits 0 to level - 1).
X            Ensures unused code bits are zero.
X         */
X
X         codelen[root] = level;
X         code[root] = tcode & (((unsigned INT)~0) >> (16-level));
X         return (level>16) ? ERROR : NULL;
X    }
X
X    else
X    {    if(l!=NOCHILD)
X         {    /* Clear path bit and continue deeper */
X
X              tcode &= ~(1 << level);
X              if(buildenc(level+1,l)==ERROR)
X                   return ERROR;       /* pass back bad statuses */
X         }
X         if(r!=NOCHILD)
X         {    /* Set path bit and continue deeper */
X
X              tcode |= 1 << level;
X              if(buildenc(level+1,r)==ERROR)
X                   return ERROR;       /* pass back bad statuses */
X         }
X    }
X    return NULL;                       /* it worked if we reach here */
X}
X
Xstatic INT put_int(n,f)                    /* output an integer */
XINT n;                                 /* integer to output */
XFILE *f;                               /* file to put it to */
X{
X    putc_pak(n&0xff,f);                /* first the low byte */
X    putc_pak(n>>8,f);                  /* then the high byte */
X}
X
X/* Write out the header of the compressed file */
X
Xstatic long wrt_head(ob)
XFILE *ob;
X{
X    register INT l,r;
X INT i, k;
X INT numnodes;                      /* # of nodes in simplified tree */
X
X    /* Write out a simplified decoding tree. Only the interior
X       nodes are written. When a child is a leaf index
X       (representing a data value) it is recoded as
X       -(index + 1) to distinguish it from interior indexes
X       which are recoded as positive indexes in the new tree.
X
X       Note that this tree will be empty for an empty file.
X    */
X
X    numnodes = dctreehd<NUMVALS ? 0 : dctreehd-(NUMVALS-1);
X    put_int(numnodes,ob);
X
X    for(k=0, i=dctreehd; k<numnodes; ++k, --i)
X    {    l = node[i].lchild;
X         r = node[i].rchild;
X         l = l<NUMVALS ? -(l+1) : dctreehd-l;
X         r = r<NUMVALS ? -(r+1) : dctreehd-r;
X         put_int(l,ob);
X         put_int(r,ob);
X    }
X
X    return sizeof(INT) + numnodes*2*sizeof(INT);
X}
X
X/* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
X
X   There are two unsynchronized bit-byte relationships here.
X   The input stream bytes are converted to bit strings of
X   various lengths via the static variables named c...
X   These bit strings are concatenated without padding to
X   become the stream of encoded result bytes, which this
X   function returns one at a time. The EOF (end of file) is
X   converted to SPEOF for convenience and encoded like any
X   other input value. True EOF is returned after that.
X*/
X
Xstatic INT gethuff(ib)                 /* Returns bytes except for EOF */
XFILE *ib;
X{
X INT rbyte;                         /* Result byte value */
X INT need, take;                    /* numbers of bits */
X
X    rbyte = 0;
X    need = 8;                          /* build one byte per call */
X
X    /* Loop to build a byte of encoded data.
X       Initialization forces read the first time.
X    */
X
Xloop:
X    if(cbitsrem>=need)                 /* if current code is big enough */
X    {    if(need==0)
X              return rbyte;
X
X         rbyte |= ccode << (8-need);   /* take what we need */
X         ccode >>= need;               /* and leave the rest */
X         cbitsrem -= need;
X         return rbyte & 0xff;
X    }
X
X    /* We need more than current code */
X
X    if(cbitsrem>0)
X    {    rbyte |= ccode << (8-need);   /* take what there is */
X         need -= cbitsrem;
X    }
X
X    /* No more bits in current code string */
X
X    if(curin==SPEOF)
X    {    /* The end of file token has been encoded. If
X            result byte has data return it and do EOF next time.
X         */
X
X         cbitsrem = 0;
X         return (need==8) ? EOF : rbyte + 0;
X    }
X
X    /* Get an input byte */
X
X    if((curin=getc_ncr(ib)) == EOF)
X         curin = SPEOF;                /* convenient for encoding */
X
X    ccode = code[curin];               /* get the new byte's code */
X    cbitsrem = codelen[curin];
X
X    goto loop;
X}
X
X/*  This routine is used to perform the actual squeeze operation.  It can
X    only be called after the file has been scanned.  It returns the true
X    length of the squeezed entry.
X*/
X
Xlong file_sq(f,t)                      /* squeeze a file into an archive */
XFILE *f;                               /* file to squeeze */
XFILE *t;                               /* archive to receive file */
X{
X INT c;                             /* one byte of squeezed data */
X    long size;                         /* size after squeezing */
X
X    size = wrt_head(t);                /* write out the decode tree */
X
X    while((c=gethuff(f))!=EOF)
X    {    putc_pak(c,t);
X         size++;
X    }
X
X    return size;                       /* report true size */
X}
$ GoSub Convert_File
$ Goto Part15