home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / OS2ARC_S.ZIP / ARCSQ.C < prev    next >
C/C++ Source or Header  |  1987-10-14  |  17KB  |  535 lines
  1. /*  ARC - Archive utility - ARCSQ
  2.  
  3. $define(tag,$$segment(@1,$$index(@1,=)+1))#
  4. $define(version,Version $tag(
  5. TED_VERSION DB =3.10), created on $tag(
  6. TED_DATE DB =01/30/86) at $tag(
  7. TED_TIME DB =20:10:46))#
  8. $undefine(tag)#
  9.     $version
  10.  
  11. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  12.  
  13.     By:  Thom Henderson
  14.  
  15.     Description:
  16.          This file contains the routines used to squeeze a file
  17.          when placing it in an archive.
  18.  
  19.     Language:
  20.          Computer Innovations Optimizing C86
  21.  
  22.     Programming notes:
  23.          Most of the routines used for the Huffman squeezing algorithm
  24.          were lifted from the SQ program by Dick Greenlaw, as adapted
  25.          to CI-C86 by Robert J. Beilstein.
  26. */
  27. #include <stdio.h>
  28.  
  29. /* stuff for Huffman squeezing */
  30.  
  31. #define TRUE 1
  32. #define FALSE 0
  33. #define ERROR (-1)
  34. #define SPEOF 256                      /* special endfile token */
  35. #define NOCHILD -1                     /* marks end of path through tree */
  36. #define NUMVALS 257                    /* 256 data values plus SPEOF*/
  37. #define NUMNODES (NUMVALS+NUMVALS-1)   /* number of nodes */
  38. #define MAXCOUNT (unsigned) 65535      /* biggest unsigned integer */
  39.  
  40. /* The following array of structures are the nodes of the
  41.    binary trees. The first NUMVALS nodes become the leaves of the
  42.    final tree and represent the values of the data bytes being
  43.    encoded and the special endfile, SPEOF.
  44.    The remaining nodes become the internal nodes of the final tree.
  45. */
  46.  
  47. struct nd                              /* shared by unsqueezer */
  48. {   unsigned weight;                   /* number of appearances */
  49.     int tdepth;                        /* length on longest path in tree */
  50.     int lchild, rchild;                /* indices to next level */
  51. }   node[NUMNODES];                    /* use large buffer */
  52.  
  53. static int dctreehd;                   /* index to head of final tree */
  54.  
  55. /* This is the encoding table:
  56.    The bit strings have first bit in low bit.
  57.    Note that counts were scaled so code fits unsigned integer.
  58. */
  59.  
  60. static int codelen[NUMVALS];           /* number of bits in code */
  61. static unsigned code[NUMVALS];         /* code itself, right adjusted */
  62. static unsigned tcode;                 /* temporary code value */
  63. static long valcount[NUMVALS];         /* actual count of times seen */
  64.  
  65. /* Variables used by encoding process */
  66.  
  67. static int curin;                      /* value currently being encoded */
  68. static int cbitsrem;                   /* # of code string bits left */
  69. static unsigned ccode;                 /* current code right justified */
  70.  
  71. init_sq()                              /* prepare for scanning pass */
  72. {
  73.     int i;                             /* node index */
  74.  
  75.     /* Initialize all nodes to single element binary trees
  76.        with zero weight and depth.
  77.     */
  78.  
  79.     for(i=0; i<NUMNODES; ++i)
  80.     {    node[i].weight = 0;
  81.          node[i].tdepth = 0;
  82.          node[i].lchild = NOCHILD;
  83.          node[i].rchild = NOCHILD;
  84.     }
  85.  
  86.     for(i=0; i<NUMVALS; i++)
  87.          valcount[i] = 0;
  88. }
  89.  
  90. scan_sq(c)                             /* add a byte to the tables */
  91. int c;                                 /* byte to add */
  92. {
  93.     unsigned *wp;                      /* speeds up weight counting */
  94.  
  95.     /* Build frequency info in tree */
  96.  
  97.     if(c == EOF)                       /* it's traditional */
  98.          c = SPEOF;                    /* dumb, but traditional */
  99.  
  100.     if(*(wp = &node[c].weight) !=  MAXCOUNT)
  101.          ++(*wp);                      /* bump weight counter */
  102.  
  103.     valcount[c]++;                     /* bump byte counter */
  104. }
  105.  
  106. long pred_sq()                         /* predict size of squeezed file */
  107. {
  108.     int i;
  109.     int btlist[NUMVALS];               /* list of intermediate b-trees */
  110.     int listlen;                       /* length of btlist */
  111.     unsigned ceiling;                  /* limit for scaling */
  112.     long size = 0;                     /* predicted size */
  113.     int numnodes;                      /* # of nodes in simplified tree */
  114.  
  115.     scan_sq(EOF);                      /* signal end of input */
  116.  
  117.     ceiling = MAXCOUNT;
  118.  
  119.     /* Keep trying to scale and encode */
  120.  
  121.     do
  122.     {    scale(ceiling);
  123.          ceiling /= 2;                 /* in case we rescale */
  124.  
  125.          /* Build list of single node binary trees having
  126.             leaves for the input values with non-zero counts
  127.          */
  128.  
  129.          for(i=listlen=0; i<NUMVALS; ++i)
  130.          {    if(node[i].weight != 0)
  131.               {    node[i].tdepth = 0;
  132.                    btlist[listlen++] = i;
  133.               }
  134.          }
  135.  
  136.          /* Arrange list of trees into a heap with the entry
  137.             indexing the node with the least weight at the top.
  138.          */
  139.  
  140.          heap(btlist,listlen);
  141.  
  142.          /* Convert the list of trees to a single decoding tree */
  143.  
  144.          bld_tree(btlist,listlen);
  145.  
  146.          /* Initialize the encoding table */
  147.  
  148.          init_enc();
  149.  
  150.          /* Try to build encoding table.
  151.             Fail if any code is > 16 bits long.
  152.          */
  153.     }    while(buildenc(0,dctreehd) == ERROR);
  154.  
  155.     /* Initialize encoding variables */
  156.  
  157.     cbitsrem = 0;                      /* force initial read */
  158.     curin = 0;                         /* anything but endfile */
  159.  
  160.     for(i=0; i<NUMVALS; i++)           /* add bits for each code */
  161.          size += valcount[i] * codelen[i];
  162.  
  163.     size = (size+7)/8;                 /* reduce to number of bytes */
  164.  
  165.     numnodes = dctreehd<NUMVALS ? 0 : dctreehd-(NUMVALS-1);
  166.  
  167.     size += sizeof(int) + 2*numnodes*sizeof(int);
  168.  
  169.     return size;
  170. }
  171.  
  172. /* The count of number of occurrances of each input value
  173.    have already been prevented from exceeding MAXCOUNT.
  174.    Now we must scale them so that their sum doesn't exceed
  175.    ceiling and yet no non-zero count can become zero.
  176.    This scaling prevents errors in the weights of the
  177.    interior nodes of the Huffman tree and also ensures that
  178.    the codes will fit in an unsigned integer. Rescaling is
  179.    used if necessary to limit the code length.
  180. */
  181.  
  182. static scale(ceil)
  183. unsigned ceil;                         /* upper limit on total weight */
  184. {
  185.     register int i,c;
  186.     int ovflw, divisor;
  187.     unsigned w, sum;
  188.     unsigned char increased;           /* flag */
  189.  
  190.     do
  191.     {    for(i=sum=ovflw=0; i<NUMVALS; ++i)
  192.          {    if(node[i].weight > (ceil-sum))
  193.                    ++ovflw;
  194.               sum += node[i].weight;
  195.          }
  196.  
  197.          divisor = ovflw + 1;
  198.  
  199.          /* Ensure no non-zero values are lost */
  200.  
  201.          increased = FALSE;
  202.          for(i=0; i<NUMVALS; ++i)
  203.          {    w = node[i].weight;
  204.               if(w<divisor && w!=0)
  205.               {    /* Don't fail to provide a code if it's used at all */
  206.  
  207.                    node[i].weight = divisor;
  208.                    increased = TRUE;
  209.               }
  210.          }
  211.     }    while(increased);
  212.  
  213.     /* Scaling factor choosen, now scale */
  214.  
  215.     if(divisor>1)
  216.          for(i=0; i<NUMVALS; ++i)
  217.               node[i].weight /= divisor;
  218. }
  219.  
  220. /* heap() and adjust() maintain a list of binary trees as a
  221.    heap with the top indexing the binary tree on the list
  222.    which has the least weight or, in case of equal weights,
  223.    least depth in its longest path. The depth part is not
  224.    strictly necessary, but tends to avoid long codes which
  225.    might provoke rescaling.
  226. */
  227.  
  228. static heap(list,length)
  229. int list[], length;
  230. {
  231.     register int i;
  232.  
  233.     for(i=(length-2)/2; i>=0; --i)
  234.          adjust(list,i,length-1);
  235. }
  236.  
  237. /* Make a heap from a heap with a new top */
  238.  
  239. static adjust(list,top,bottom)
  240. int list[], top, bottom;
  241. {
  242.     register int k, temp;
  243.  
  244.     k = 2 * top + 1;                   /* left child of top */
  245.     temp = list[top];                  /* remember root node of top tree */
  246.  
  247.     if(k<=bottom)
  248.     {    if(k<bottom && cmptrees(list[k],list[k+1]))
  249.               ++k;
  250.  
  251.          /* k indexes "smaller" child (in heap of trees) of top */
  252.          /* now make top index "smaller" of old top and smallest child */
  253.  
  254.          if(cmptrees(temp,list[k]))
  255.          {    list[top] = list[k];
  256.               list[k] = temp;
  257.  
  258.               /* Make the changed list a heap */
  259.  
  260.               adjust(list,k,bottom);   /* recursive */
  261.          }
  262.     }
  263. }
  264.  
  265. /* Compare two trees, if a > b return true, else return false.
  266.    Note comparison rules in previous comments.
  267. */
  268.  
  269. static cmptrees(a,b)
  270. int a, b;                              /* root nodes of trees */
  271. {
  272.     if(node[a].weight > node[b].weight)
  273.          return TRUE;
  274.     if(node[a].weight == node[b].weight)
  275.          if(node[a].tdepth > node[b].tdepth)
  276.               return TRUE;
  277.     return FALSE;
  278. }
  279.  
  280. /* HUFFMAN ALGORITHM: develops the single element trees
  281.    into a single binary tree by forming subtrees rooted in
  282.    interior nodes having weights equal to the sum of weights of all
  283.    their descendents and having depth counts indicating the
  284.    depth of their longest paths.
  285.  
  286.    When all trees have been formed into a single tree satisfying
  287.    the heap property (on weight, with depth as a tie breaker)
  288.    then the binary code assigned to a leaf (value to be encoded)
  289.    is then the series of left (0) and right (1)
  290.    paths leading from the root to the leaf.
  291.    Note that trees are removed from the heaped list by
  292.    moving the last element over the top element and
  293.    reheaping the shorter list.
  294. */
  295.  
  296. static bld_tree(list,len)
  297. int list[];
  298. int len;
  299. {
  300.     register int freenode;             /* next free node in tree */
  301.     register struct nd *frnp;          /* free node pointer */
  302.     int lch, rch;                      /* temps for left, right children */
  303.     int i;
  304.  
  305.     /* Initialize index to next available (non-leaf) node.
  306.        Lower numbered nodes correspond to leaves (data values).
  307.     */
  308.  
  309.     freenode = NUMVALS;
  310.  
  311.     while(len>1)
  312.     {    /* Take from list two btrees with least weight
  313.             and build an interior node pointing to them.
  314.             This forms a new tree.
  315.          */
  316.  
  317.          lch = list[0];                /* This one will be left child */
  318.  
  319.          /* delete top (least) tree from the list of trees */
  320.  
  321.          list[0] = list[--len];
  322.          adjust(list,0,len-1);
  323.  
  324.          /* Take new top (least) tree. Reuse list slot later */
  325.  
  326.          rch = list[0];                /* This one will be right child */
  327.  
  328.          /* Form new tree from the two least trees using
  329.             a free node as root. Put the new tree in the list.
  330.          */
  331.  
  332.          frnp = &node[freenode];       /* address of next free node */
  333.          list[0] = freenode++;         /* put at top for now */
  334.          frnp->lchild = lch;
  335.          frnp->rchild = rch;
  336.          frnp->weight = node[lch].weight + node[rch].weight;
  337.          frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  338.  
  339.          /* reheap list  to get least tree at top */
  340.  
  341.          adjust(list,0,len-1);
  342.     }
  343.     dctreehd = list[0];                /* head of final tree */
  344. }
  345.  
  346. static maxchar(a,b)
  347. {
  348.     return a>b ? a : b;
  349. }
  350.  
  351. static init_enc()
  352. {
  353.     register int i;
  354.  
  355.     /* Initialize encoding table */
  356.  
  357.     for(i=0; i<NUMVALS; ++i)
  358.          codelen[i] = 0;
  359. }
  360.  
  361. /* Recursive routine to walk the indicated subtree and level
  362.    and maintain the current path code in bstree. When a leaf
  363.    is found the entire code string and length are put into
  364.    the encoding table entry for the leaf's data value .
  365.  
  366.    Returns ERROR if codes are too long.
  367. */
  368.  
  369. static int buildenc(level,root)
  370. int level;              /* level of tree being examined, from zero */
  371. int root;               /* root of subtree is also data value if leaf */
  372. {
  373.     register int l, r;
  374.  
  375.     l = node[root].lchild;
  376.     r = node[root].rchild;
  377.  
  378.     if(l==NOCHILD && r==NOCHILD)
  379.     {    /* Leaf. Previous path determines bit string
  380.             code of length level (bits 0 to level - 1).
  381.             Ensures unused code bits are zero.
  382.          */
  383.  
  384.          codelen[root] = level;
  385.          code[root] = tcode & (((unsigned)~0) >> (16-level));
  386.          return (level>16) ? ERROR : NULL;
  387.     }
  388.  
  389.     else
  390.     {    if(l!=NOCHILD)
  391.          {    /* Clear path bit and continue deeper */
  392.  
  393.               tcode &= ~(1 << level);
  394.               if(buildenc(level+1,l)==ERROR)
  395.                    return ERROR;       /* pass back bad statuses */
  396.          }
  397.          if(r!=NOCHILD)
  398.          {    /* Set path bit and continue deeper */
  399.  
  400.               tcode |= 1 << level;
  401.               if(buildenc(level+1,r)==ERROR)
  402.                    return ERROR;       /* pass back bad statuses */
  403.          }
  404.     }
  405.     return NULL;                       /* it worked if we reach here */
  406. }
  407.  
  408. static put_int(n,f)                    /* output an integer */
  409. int n;                                 /* integer to output */
  410. FILE *f;                               /* file to put it to */
  411. {
  412.     putc_pak(n&0xff,f);                /* first the low byte */
  413.     putc_pak(n>>8,f);                  /* then the high byte */
  414. }
  415.  
  416. /* Write out the header of the compressed file */
  417.  
  418. static long wrt_head(ob)
  419. FILE *ob;
  420. {
  421.     register int l,r;
  422.     int i, k;
  423.     int numnodes;                      /* # of nodes in simplified tree */
  424.  
  425.     /* Write out a simplified decoding tree. Only the interior
  426.        nodes are written. When a child is a leaf index
  427.        (representing a data value) it is recoded as
  428.        -(index + 1) to distinguish it from interior indexes
  429.        which are recoded as positive indexes in the new tree.
  430.  
  431.        Note that this tree will be empty for an empty file.
  432.     */
  433.  
  434.     numnodes = dctreehd<NUMVALS ? 0 : dctreehd-(NUMVALS-1);
  435.     put_int(numnodes,ob);
  436.  
  437.     for(k=0, i=dctreehd; k<numnodes; ++k, --i)
  438.     {    l = node[i].lchild;
  439.          r = node[i].rchild;
  440.          l = l<NUMVALS ? -(l+1) : dctreehd-l;
  441.          r = r<NUMVALS ? -(r+1) : dctreehd-r;
  442.          put_int(l,ob);
  443.          put_int(r,ob);
  444.     }
  445.  
  446.     return sizeof(int) + numnodes*2*sizeof(int);
  447. }
  448.  
  449. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  450.  
  451.    There are two unsynchronized bit-byte relationships here.
  452.    The input stream bytes are converted to bit strings of
  453.    various lengths via the static variables named c...
  454.    These bit strings are concatenated without padding to
  455.    become the stream of encoded result bytes, which this
  456.    function returns one at a time. The EOF (end of file) is
  457.    converted to SPEOF for convenience and encoded like any
  458.    other input value. True EOF is returned after that.
  459. */
  460.  
  461. static int gethuff(ib)                 /* Returns bytes except for EOF */
  462. FILE *ib;
  463. {
  464.     int rbyte;                         /* Result byte value */
  465.     int need, take;                    /* numbers of bits */
  466.  
  467.     rbyte = 0;
  468.     need = 8;                          /* build one byte per call */
  469.  
  470.     /* Loop to build a byte of encoded data.
  471.        Initialization forces read the first time.
  472.     */
  473.  
  474. loop:
  475.     if(cbitsrem>=need)                 /* if current code is big enough */
  476.     {    if(need==0)
  477.               return rbyte;
  478.  
  479.          rbyte |= ccode << (8-need);   /* take what we need */
  480.          ccode >>= need;               /* and leave the rest */
  481.          cbitsrem -= need;
  482.          return rbyte & 0xff;
  483.     }
  484.  
  485.     /* We need more than current code */
  486.  
  487.     if(cbitsrem>0)
  488.     {    rbyte |= ccode << (8-need);   /* take what there is */
  489.          need -= cbitsrem;
  490.     }
  491.  
  492.     /* No more bits in current code string */
  493.  
  494.     if(curin==SPEOF)
  495.     {    /* The end of file token has been encoded. If
  496.             result byte has data return it and do EOF next time.
  497.          */
  498.  
  499.          cbitsrem = 0;
  500.          return (need==8) ? EOF : rbyte + 0;
  501.     }
  502.  
  503.     /* Get an input byte */
  504.  
  505.     if((curin=getc_ncr(ib)) == EOF)
  506.          curin = SPEOF;                /* convenient for encoding */
  507.  
  508.     ccode = code[curin];               /* get the new byte's code */
  509.     cbitsrem = codelen[curin];
  510.  
  511.     goto loop;
  512. }
  513.  
  514. /*  This routine is used to perform the actual squeeze operation.  It can
  515.     only be called after the file has been scanned.  It returns the true
  516.     length of the squeezed entry.
  517. */
  518.  
  519. long file_sq(f,t)                      /* squeeze a file into an archive */
  520. FILE *f;                               /* file to squeeze */
  521. FILE *t;                               /* archive to receive file */
  522. {
  523.     int c;                             /* one byte of squeezed data */
  524.     long size;                         /* size after squeezing */
  525.  
  526.     size = wrt_head(t);                /* write out the decode tree */
  527.  
  528.     while((c=gethuff(f))!=EOF)
  529.     {    putc_pak(c,t);
  530.          size++;
  531.     }
  532.  
  533.     return size;                       /* report true size */
  534. }
  535.