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