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