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