home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 111_01 / tr2.c < prev    next >
Text File  |  1985-08-21  |  13KB  |  467 lines
  1. /*
  2. HEADER:        ;
  3. TITLE:        Squeezer;
  4. DESCRIPTION:    "Auxiliary file for the SQ.C and USQ.C package.
  5.         See SQUEEZER.DOC.";
  6. SYSTEM:        CP/M-80;
  7. FILENAME:    TR2.C;
  8. SEE-ALSO:    SQUEEZER.DOC;
  9. AUTHORS:    Dick Greenlaw;
  10. COMPILERS:    BDS C;
  11. */
  12. #include <bdscio.h>
  13. #include <dio.h>
  14. #include "sqcom.h"
  15. #include "sq.h"
  16. #define STDERR 4    /* error stream - always console */
  17.  
  18. /******** Second translation - bytes to variable length bit strings *********/
  19.  
  20.  
  21. /* This translation uses the Huffman algorithm to develop a
  22.  * binary tree representing the decoding information for
  23.  * a variable length bit string code for each input value.
  24.  * Each string's length is in inverse proportion to its
  25.  * frequency of appearance in the incoming data stream.
  26.  * The encoding table is derived from the decoding table.
  27.  *
  28.  * The range of valid values into the Huffman algorithm are
  29.  * the values of a byte stored in an integer plus the special
  30.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  31.  *
  32.  * The "node" array of structures contains the nodes of the
  33.  * binary tree. The first NUMVALS nodes are the leaves of the
  34.  * tree and represent the values of the data bytes being
  35.  * encoded and the special endfile, SPEOF.
  36.  * The remaining nodes become the internal nodes of the tree.
  37.  *
  38.  * In the original design it was believed that
  39.  * a Huffman code would fit in the same number of
  40.  * bits that will hold the sum of all the counts.
  41.  * That was disproven by a user's file and was a rare but
  42.  * infamous bug. This version attempts to choose among equally
  43.  * weighted subtrees according to their maximum depths to avoid
  44.  * unnecessarily long codes. In case that is not sufficient
  45.  * to guarantee codes <= 16 bits long, we initially scale
  46.  * the counts so the total fits in an unsigned integer, but
  47.  * if codes longer than 16 bits are generated the counts are
  48.  * rescaled to a lower ceiling and code generation is retried.
  49.  */
  50.  
  51. /* Initialize the Huffman translation. This requires reading
  52.  * the input file through any preceding translation functions
  53.  * to get the frequency distribution of the various values.
  54.  */
  55.  
  56. init_huff(ib)
  57. struct _buf *ib;
  58. {
  59.     int c, i;
  60.     int btlist[NUMVALS];    /* list of intermediate binary trees */
  61.     int listlen;        /* length of btlist */
  62.     unsigned *wp;    /* simplifies weight counting */
  63.     unsigned ceiling;    /* limit for scaling */
  64.  
  65.     /* Initialize tree nodes to no weight, no children */
  66.     init_tree();
  67.  
  68.     /* Build frequency info in tree */
  69.     do {
  70.         c = getcnr(ib);
  71.         if(c == EOF)
  72.             c = SPEOF;
  73.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  74.             ++(*wp);
  75.     } while(c != SPEOF);
  76.  
  77.     pcounts();    /* debugging aid */
  78.  
  79.     ceiling = MAXCOUNT;
  80.  
  81.     do {    /* Keep trying to scale and encode */
  82.         if(ceiling != MAXCOUNT)
  83.             printf("*** rescaling ***, ");
  84.         scale(ceiling);
  85.         ceiling /= 2;    /* in case we rescale */
  86.         pcounts();    /* debugging aid */
  87.  
  88.         /* Build list of single node binary trees having
  89.          * leaves for the input values with non-zero counts
  90.          */
  91.         for(i = listlen = 0; i < NUMVALS; ++i)
  92.             if(node[i].weight != 0) {
  93.                 node[i].tdepth = 0;
  94.                 btlist[listlen++] = i;
  95.             }
  96.  
  97.         /* Arrange list of trees into a heap with the entry
  98.          * indexing the node with the least weight at the top.
  99.          */
  100.         heap(btlist, listlen);
  101.  
  102.         /* Convert the list of trees to a single decoding tree */
  103.         bld_tree(btlist, listlen);
  104.  
  105.         /* Initialize the encoding table */
  106.         init_enc();
  107.  
  108.         /* Try to build encoding table.
  109.          * Fail if any code is > 16 bits long.
  110.          */
  111.     } while(buildenc(0, dctreehd) == ERROR);
  112.     phuff();    /* debugging aid */
  113.  
  114.     /* Initialize encoding variables */
  115.     cbitsrem = 0;    /*force initial read */
  116.     curin = 0;    /*anything but endfile*/
  117. }
  118.  
  119. /* The count of number of occurrances of each input value
  120.  * have already been prevented from exceeding MAXCOUNT.
  121.  * Now we must scale them so that their sum doesn't exceed
  122.  * ceiling and yet no non-zero count can become zero.
  123.  * This scaling prevents errors in the weights of the
  124.  * interior nodes of the Huffman tree and also ensures that
  125.  * the codes will fit in an unsigned integer. Rescaling is
  126.  * used if necessary to limit the code length.
  127.  */
  128.  
  129. scale(ceil)
  130. unsigned ceil;    /* upper limit on total weight */
  131. {
  132.     int c, ovflw, divisor, i;
  133.     unsigned w, sum;
  134.     char increased;        /* flag */
  135.  
  136.     do {
  137.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  138.             if(node[i].weight > (ceil - sum))
  139.                 ++ovflw;
  140.             sum += node[i].weight;
  141.         }
  142.  
  143.         divisor = ovflw + 1;
  144.  
  145.         /* Ensure no non-zero values are lost */
  146.         increased = FALSE;
  147.         for(i = 0; i < NUMVALS; ++i) {
  148.             w = node[i].weight;
  149.             if (w < divisor && w > 0) {
  150.                 /* Don't fail to provide a code if it's used at all */
  151.                 node[i].weight = divisor;
  152.                 increased = TRUE;
  153.             }
  154.         }
  155.     } while(increased);
  156.  
  157.     /* Scaling factor choosen, now scale */
  158.     if(divisor > 1)
  159.         for(i = 0; i < NUMVALS; ++i)
  160.             node[i].weight /= divisor;
  161. }
  162.  
  163. /* heap() and adjust() maintain a list of binary trees as a
  164.  * heap with the top indexing the binary tree on the list
  165.  * which has the least weight or, in case of equal weights,
  166.  * least depth in its longest path. The depth part is not
  167.  * strictly necessary, but tends to avoid long codes which
  168.  * might provoke rescaling.
  169.  */
  170.  
  171. heap(list, length)
  172. int list[], length;
  173. {
  174.     int i;
  175.  
  176.     for(i = (length - 2) / 2; i >= 0; --i)
  177.         adjust(list, i, length - 1);
  178. }
  179.  
  180. /* Make a heap from a heap with a new top */
  181.  
  182. adjust(list, top, bottom)
  183. int list[], top, bottom;
  184. {
  185.     int k, temp;
  186.  
  187.     k = 2 * top + 1;    /* left child of top */
  188.     temp = list[top];    /* remember root node of top tree */
  189.     if( k <= bottom) {
  190.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  191.             ++k;
  192.  
  193.         /* k indexes "smaller" child (in heap of trees) of top */
  194.         /* now make top index "smaller" of old top and smallest child */
  195.         if(cmptrees(temp, list[k])) {
  196.             list[top] = list[k];
  197.             list[k] = temp;
  198.             /* Make the changed list a heap */
  199.             adjust(list, k, bottom); /*recursive*/
  200.         }
  201.     }
  202. }
  203.  
  204. /* Compare two trees, if a > b return true, else return false
  205.  * note comparison rules in previous comments.
  206.  */
  207.  
  208. char    /* Boolean */
  209. cmptrees(a, b)
  210. int a, b;    /* root nodes of trees */
  211. {
  212.     if(node[a].weight > node[b].weight)
  213.         return TRUE;
  214.     if(node[a].weight == node[b].weight)
  215.         if(node[a].tdepth > node[b].tdepth)
  216.             return TRUE;
  217.     return FALSE;
  218. }
  219.  
  220. /* HUFFMAN ALGORITHM: develops the single element trees
  221.  * into a single binary tree by forming subtrees rooted in
  222.  * interior nodes having weights equal to the sum of weights of all
  223.  * their descendents and having depth counts indicating the
  224.  * depth of their longest paths.
  225.  *
  226.  * When all trees have been formed into a single tree satisfying
  227.  * the heap property (on weight, with depth as a tie breaker)
  228.  * then the binary code assigned to a leaf (value to be encoded)
  229.  * is then the series of left (0) and right (1)
  230.  * paths leading from the root to the leaf.
  231.  * Note that trees are removed from the heaped list by
  232.  * moving the last element over the top element and
  233.  * reheaping the shorter list.
  234.  */
  235.  
  236. bld_tree(list, len)
  237. int list[];
  238. int len;
  239. {
  240.     int freenode;        /* next free node in tree */
  241.     int lch, rch;        /* temporaries for left, right children */
  242.     struct nd *frnp;    /* free node pointer */
  243.     int i;
  244.  
  245.     /* Initialize index to next available (non-leaf) node.
  246.      * Lower numbered nodes correspond to leaves (data values).
  247.      */
  248.     freenode = NUMVALS;
  249.  
  250.     while(len > 1) {
  251.         /* Take from list two btrees with least weight
  252.          * and build an interior node pointing to them.
  253.          * This forms a new tree.
  254.          */
  255.         lch = list[0];    /* This one will be left child */
  256.  
  257.         /* delete top (least) tree from the list of trees */
  258.         list[0] = list[--len];
  259.         adjust(list, 0, len - 1);
  260.  
  261.         /* Take new top (least) tree. Reuse list slot later */
  262.         rch = list[0];    /* This one will be right child */
  263.  
  264.         /* Form new tree from the two least trees using
  265.          * a free node as root. Put the new tree in the list.
  266.          */
  267.         frnp = &node[freenode];    /* address of next free node */
  268.         list[0] = freenode++;    /* put at top for now */
  269.         frnp->lchild = lch;
  270.         frnp->rchild = rch;
  271.         frnp->weight = node[lch].weight + node[rch].weight;
  272.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  273.         /* reheap list  to get least tree at top*/
  274.         adjust(list, 0, len - 1);
  275.     }
  276.     dctreehd = list[0];    /*head of final tree */
  277. }
  278.  
  279. char
  280. maxchar(a, b)
  281. char a, b;
  282. {
  283.     return a > b ? a : b;
  284. }
  285. /* Initialize all nodes to single element binary trees
  286.  * with zero weight and depth.
  287.  */
  288.  
  289. init_tree()
  290. {
  291.     int i;
  292.  
  293.     for(i = 0; i < NUMNODES; ++i) {
  294.         node[i].weight = 0;
  295.         node[i].tdepth = 0;
  296.         node[i].lchild = NOCHILD;
  297.         node[i].rchild = NOCHILD;
  298.     }
  299. }
  300.  
  301. init_enc()
  302. {
  303.     int i;
  304.  
  305.     /* Initialize encoding table */
  306.     for(i = 0; i < NUMVALS; ++i) {
  307.         codelen[i] = 0;
  308.     }
  309. }
  310.  
  311. /* Recursive routine to walk the indicated subtree and level
  312.  * and maintain the current path code in bstree. When a leaf
  313.  * is found the entire code string and length are put into
  314.  * the encoding table entry for the leaf's data value.
  315.  *
  316.  * Returns ERROR if codes are too long.
  317.  */
  318.  
  319. int        /* returns ERROR or NULL */
  320. buildenc(level, root)
  321. int level;/* level of tree being examined, from zero */
  322. int root; /* root of subtree is also data value if leaf */
  323. {
  324.     int l, r;
  325.  
  326.     l = node[root].lchild;
  327.     r = node[root].rchild;
  328.  
  329.     if( l == NOCHILD && r == NOCHILD) {
  330.         /* Leaf. Previous path determines bit string
  331.          * code of length level (bits 0 to level - 1).
  332.          * Ensures unused code bits are zero.
  333.          */
  334.         codelen[root] = level;
  335.         code[root] = tcode & ((~0) >> (16 - level));
  336.         return (level > 16) ? ERROR : NULL;
  337.     } else {
  338.         if( l != NOCHILD) {
  339.             /* Clear path bit and continue deeper */
  340.             tcode &= ~(1 << level);
  341.             /* NOTE RECURSION */
  342.             if(buildenc(level + 1, l) == ERROR)
  343.                 return ERROR;
  344.         }
  345.         if(r != NOCHILD) {
  346.             /* Set path bit and continue deeper */
  347.             tcode |= 1 << level;
  348.             /* NOTE RECURSION */
  349.             if(buildenc(level + 1, r) == ERROR)
  350.                 return ERROR;
  351.         }
  352.     }
  353.     return NULL;    /* if we got here we're ok so far */
  354. }
  355.  
  356. /* Write out the header of the compressed file */
  357.  
  358. wrt_head(ob, infile)
  359. struct _buf *ob;
  360. char *infile;    /* input file name (w/ or w/o drive) */
  361. {
  362.     int i, k, l, r;
  363.     int numnodes;        /* nbr of nodes in simplified tree */
  364.  
  365.     putwe(RECOGNIZE, ob);    /* identifies as compressed */
  366.     putwe(crc, ob);        /* unsigned sum of original data */
  367.  
  368.     /* Record the original file name w/o drive */
  369.     if(*(infile + 1) == ':')
  370.         infile += 2;    /* skip drive */
  371.  
  372.     do {
  373.         putce(*infile, ob);
  374.     } while(*(infile++) != '\0');
  375.  
  376.  
  377.     /* Write out a simplified decoding tree. Only the interior
  378.      * nodes are written. When a child is a leaf index
  379.      * (representing a data value) it is recoded as
  380.      * -(index + 1) to distinguish it from interior indexes
  381.      * which are recoded as positive indexes in the new tree.
  382.      * Note that this tree will be empty for an empty file.
  383.      */
  384.  
  385.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  386.     putwe(numnodes, ob);
  387.  
  388.     for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  389.         l = node[i].lchild;
  390.         r = node[i].rchild;
  391.         l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  392.         r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  393.         putwe(l, ob);    /* left child */
  394.         putwe(r, ob);    /* right child */
  395.     }
  396. }
  397.  
  398. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  399.  *
  400.  * There are two unsynchronized bit-byte relationships here.
  401.  * The input stream bytes are converted to bit strings of
  402.  * various lengths via the static variables named c...
  403.  * These bit strings are concatenated without padding to
  404.  * become the stream of encoded result bytes, which this
  405.  * function returns one at a time. The EOF (end of file) is
  406.  * converted to SPEOF for convenience and encoded like any
  407.  * other input value. True EOF is returned after that.
  408.  *
  409.  * The original gethuff() called a seperate function,
  410.  * getbit(), but that more readable version was too slow.
  411.  */
  412.  
  413. int        /*  Returns byte values except for EOF */
  414. gethuff(ib)
  415. struct _buf *ib;
  416. {
  417.     char rbyte;    /* Result byte value */
  418.     char need, take;    /* numbers of bits */
  419.  
  420.     rbyte = 0;
  421.     need = 8;    /* build one byte per call */
  422.  
  423.     /* Loop to build a byte of encoded data
  424.      * Initialization forces read the first time
  425.      */
  426.  
  427. loop:
  428.     if(cbitsrem >= need) {
  429.         /* Current code fullfills our needs */
  430.         if(need == 0)
  431.             return rbyte;
  432.         /* Take what we need */
  433.          rbyte |= ccode << (8 - need);
  434.         /* And leave the rest */
  435.         ccode >>= need;
  436.         cbitsrem -= need;
  437.         return rbyte;
  438.     }
  439.  
  440.     /* We need more than current code */
  441.     if(cbitsrem > 0) {
  442.         /* Take what there is */
  443.         rbyte |= ccode << (8 - need);
  444.         need -= cbitsrem;
  445.     }
  446.     /* No more bits in current code string */
  447.     if(curin == SPEOF) {
  448.         /* The end of file token has been encoded. If
  449.          * result byte has data return it and do EOF next time
  450.          */
  451.         cbitsrem = 0;
  452.  
  453.         /*NOTE: +0 is to fight compiler bug? */
  454.         return (need == 8) ? EOF : rbyte + 0;
  455.     }
  456.  
  457.     /* Get an input byte */
  458.     if((curin = getcnr(ib)) == EOF)
  459.         curin = SPEOF;    /* convenient for encoding */
  460.  
  461.     /* Get the new byte's code */
  462.     ccode = code[curin];
  463.     cbitsrem = codelen[curin];
  464.  
  465.     goto loop;
  466. }
  467.