home *** CD-ROM | disk | FTP | other *** search
/ Programmer Power Tools / Programmer Power Tools.iso / compress / sq_usq.arc / SQ18U.C next >
Encoding:
C/C++ Source or Header  |  1986-05-03  |  22.1 KB  |  829 lines
  1. static char *sccsid = "@(#)sq.c         1.8u (UCF) 83/09/02";
  2. /*
  3.  *   sq.c - CP/M compatible file squeezer utility
  4.  *
  5.  *   compile as follows:
  6.  *   cc [-DVAX] -O sq.c -o sq
  7.  *     (define VAX only if running on VAX)
  8.  */
  9.  
  10. #include <stdio.h>
  11. /* #include <signal.h> */
  12.  
  13. #define TRUE 1
  14. #define FALSE 0
  15. #define ERROR (-1)
  16. #define PATHLEN 312    /* Number of characters allowed in pathname */
  17. #define ALTNAME "sq.out"
  18.  
  19. /* Definitions and external declarations */
  20.  
  21. #define RECOGNIZE 0xFF76    /* unlikely pattern */
  22.  
  23. /* *** Stuff for first translation module *** */
  24.  
  25. #define DLE 0x90
  26.  
  27.  
  28. /* *** Stuff for second translation module *** */
  29.  
  30. #define SPEOF 256    /* special endfile token */
  31. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  32.  
  33.  
  34. #ifdef VAX   /*  we only want 16 bit integers  */
  35.  
  36. typedef short INT;
  37. typedef unsigned short UNSIGNED;
  38.  
  39. #else    /*  PDP-11 and other 16-bit machines  */
  40.  
  41. typedef int INT;
  42. typedef unsigned UNSIGNED;
  43.  
  44. #endif
  45.  
  46.  
  47. /* Definitions and external declarations */
  48.  
  49. INT Usestd;    /* Use stdout for squeezed output */
  50. UNSIGNED crc;    /* error check code */
  51.  
  52. /* *** Stuff for first translation module *** */
  53.  
  54. INT likect;    /*count of consecutive identical chars */
  55. INT lastchar, newchar;
  56. unsigned char state;
  57.  
  58. /* states */
  59.  
  60. #define NOHIST    0    /*don't consider previous input*/
  61. #define SENTCHAR 1    /*lastchar set, no lookahead yet */
  62. #define SENDNEWC 2    /*newchar set, previous sequence done */
  63. #define SENDCNT 3    /*newchar set, DLE sent, send count next */
  64.  
  65. /* *** Stuff for second translation module *** */
  66.  
  67. #define NOCHILD -1    /* indicates end of path through tree */
  68. #define NUMNODES (NUMVALS + NUMVALS - 1)    /* nbr of nodes */
  69.  
  70. #define MAXCOUNT (UNSIGNED) 65535    /* biggest UNSIGNED integer */
  71.  
  72. /* The following array of structures are the nodes of the
  73.  * binary trees. The first NUMVALS nodes becomethe leaves of the
  74.  * final tree and represent the values of the data bytes being
  75.  * encoded and the special endfile, SPEOF.
  76.  * The remaining nodes become the internal nodes of the final tree.
  77.  */
  78.  
  79. struct    nd {
  80.     UNSIGNED weight;    /* number of appearances */
  81.     INT tdepth;        /* length on longest path in tre*/
  82.     INT lchild, rchild;    /* indexes to next level */
  83. } node[NUMNODES];
  84.  
  85. INT dctreehd;    /*index to head node of final tree */
  86.  
  87. /* This is the encoding table:
  88.  * The bit strings have first bit in  low bit.
  89.  * Note that counts were scaled so code fits UNSIGNED integer
  90.  */
  91.  
  92. INT codelen[NUMVALS];        /* number of bits in code */
  93. UNSIGNED code[NUMVALS];     /* code itself, right adjusted */
  94. UNSIGNED tcode;         /* temporary code value */
  95.  
  96.  
  97. /* Variables used by encoding process */
  98.  
  99. INT curin;    /* Value currently being encoded */
  100. INT cbitsrem;    /* Number of code string bits remaining */
  101. UNSIGNED ccode; /* Current code shifted so next code bit is at right */
  102.  
  103. /* This program compresses a file without losing information.
  104.  * The usq.com program is required to unsqueeze the file
  105.  * before it can be used.
  106.  *
  107.  * Typical compression rates are:
  108.  *    .COM    6%    (Don't bother)
  109.  *    .ASM    33%    (using full ASCII set)
  110.  *    .DIC    46%    (using only uppercase and a few others)
  111.  * Squeezing a really big file takes a few minutes.
  112.  *
  113.  * Useage:
  114.  *    sq file ...
  115.  *
  116.  *
  117.  * The squeezed file name is formed by changing the second from last
  118.  * letter of the file type to Q. If there is no file type,
  119.  * the squeezed file type is QQQ. If the name exists it is
  120.  * overwritten!
  121.  *
  122.  * The transformations compress strings of identical bytes and
  123.  * then encode each resulting byte value and EOF as bit strings
  124.  * having lengths in inverse proportion to their frequency of
  125.  * occurrence in the intermediate input stream. The latter uses
  126.  * the Huffman algorithm. Decoding information is included in
  127.  * the squeezed file, so squeezing short files or files with
  128.  * uniformly distributed byte values will actually increase size.
  129.  */
  130.  
  131. /* CHANGE HISTORY:
  132.  * 1.5u *unix version - means output to stdout.
  133.  *  (stdin not allowed becuase sq needs to rewind input, which
  134.  *  won't work with pipes.)
  135.  * Filename generation changed to suit **nix and stdio.
  136.  * 1.6u machine independent output for file compatibility with
  137.  *    original CP/M version SQ, when running on machine with
  138.  *    IBM byte ordering such as Z8000 and 68000.
  139.  * 1.7u machine independence was still lacking for 32-bit machines
  140.  *    like the VAX-11/780, so a typedef was added.  No action
  141.  *    need be taken if running on a 16-bit machine, but if
  142.  *    running on a VAX, define VAX either on the cc line or
  143.  *    in the program preamble.   Ben Goldfarb 12/13/82
  144.  * 1.8u Modified to run under CI-86 compiler for the IBM PC
  145.  *    Robert J. Beilstein 09/02/83
  146.  */
  147.  
  148. #define VERSION "1.8u   12-13-82"
  149.  
  150. INT inbackground = 0;  /* change to 1 to suppress informative messages */
  151.  
  152. INT buildenc(), gethuff(), getc_crc();
  153.  
  154. main(argc, argv)
  155. INT argc;
  156. char *argv[];
  157. {
  158.     register INT i,c;
  159. /*
  160.  
  161.     if (signal(SIGINT, SIG_IGN)==SIG_IGN)
  162.         inbackground++;
  163.     else
  164.         signal(SIGINT, SIG_DFL);
  165.     signal(SIGHUP, SIG_IGN);       */
  166.  
  167.     /* Process the parameters in order */
  168.     for(i = 1; i < argc; ++i) {
  169.         if(strcmp(argv[i], "-")==0)
  170.             Usestd = TRUE;
  171.     }
  172.     for(i = 1; i < argc; ++i) {
  173.         if(strcmp(argv[i], "-")!=0)
  174.             obey(argv[i]);
  175.     }
  176.  
  177.     if(argc < 2) {
  178.         fprintf(stderr,"File squeezer version %s by\n\tRichard Greenlaw\n\t251 Colony Ct.\n\tGahanna, Ohio 43230\n", VERSION);
  179.         fprintf(stderr, "Usage: sq [-] pathname ...\n");
  180.         fprintf(stderr, "\t- squeezed output to stdout\n");
  181.         exit(1);
  182.     }
  183.     exit(0);
  184. }
  185. obey(p)
  186. unsigned char *p;
  187. {
  188.     unsigned char *w,*q;
  189.     unsigned char outfile[PATHLEN+2];     /* output file spec. */
  190.  
  191.     /* First build output file name */
  192.  
  193.     strcpy(outfile, p);
  194.     /* Find and change output file type */
  195.     for(w=q = outfile; *q != '\0'; ++q)     /* skip leading /'s */
  196.         if( *q == '/')
  197.             w = q+1;
  198.     for(q = w; *q != '\0'; ++q)
  199.         if(*q == '.')
  200.             if(*(q + 1) == '\0')
  201.                 *q = '\0';      /* kill trailing dot */
  202.             else
  203.                 switch(*(q+2)) {
  204.                 case 'q':
  205.                 case 'Q':
  206.                     fprintf(stderr, "sq: %s ignored ( already squeezed?)", p);
  207.                     return;
  208.                 case '\0':
  209.                     *(q+3) = '\0';
  210.                     /* fall thru */
  211.                 default:
  212.                     *(q + 2) = 'Q';
  213.                     goto named;
  214.                 }
  215.     /* No file type */
  216.     strcat(outfile, ".QQQ");
  217. named:
  218.     if(strlen(w)>14)
  219.         strcpy(outfile, ALTNAME);    /* check for too long name */
  220.     squeeze(p, outfile);
  221. }
  222.  
  223. squeeze(infile, outfile)
  224. unsigned char *infile, *outfile;
  225. {
  226.     register INT i, c;
  227.     FILE *inbuff, *outbuff; /* file buffers */
  228.  
  229.     if (!inbackground)
  230.         fprintf(stderr, "\n%s -> %s: ", infile, outfile);
  231.  
  232.     if((inbuff=fopen(infile, "rb")) == NULL) {
  233.         fprintf(stderr, "sq: can't open %s\n", infile);
  234.         return;
  235.     }
  236.     if(Usestd)
  237.         outbuff=stdout;
  238.     else if((outbuff=fopen(outfile, "wb")) == NULL) {
  239.         fprintf(stderr, "sq: can't create %s\n", outfile);
  240.         fclose(inbuff);
  241.         return;
  242.     }
  243.  
  244.     /* First pass - get properties of file */
  245.     crc = 0;    /* initialize checksum */
  246.     if (!inbackground)
  247.         fprintf(stderr, "analyzing, ");
  248.     init_ncr();
  249.     init_huff(inbuff);
  250.     /* rewind(inbuff); */ fseek(inbuff,0L,0);
  251.  
  252.     /* Write output file header with decoding info */
  253.     wrt_head(outbuff, infile);
  254.  
  255.     /* Second pass - encode the file */
  256.     if (!inbackground)
  257.         fprintf(stderr, "squeezing, ");
  258.  
  259.     init_ncr();    /* For second pass */
  260.  
  261.     /* Translate the input file into the output file */
  262.     while((c = gethuff(inbuff)) != EOF)
  263.         if(putc(c, outbuff) == ERROR && ferror(outbuff)) {
  264.             fprintf(stderr, "sq: write error\n");
  265.             goto closeall;
  266.         }
  267.     if (!inbackground)
  268.         fprintf(stderr, " done.\n");
  269. closeall:
  270.     fclose(inbuff);
  271. closeout:
  272.     fflush(outbuff);
  273.     fclose(outbuff);
  274. }
  275.  
  276.  
  277. /* First translation - encoding of repeated characters
  278.  * The code is byte for byte pass through except that
  279.  * DLE is encoded as DLE, zero and repeated byte values
  280.  * are encoded as value, DLE, count for count >= 3.
  281.  */
  282.  
  283. init_ncr()    /*initialize getcnr() */
  284. {
  285.     state = NOHIST;
  286. }
  287.  
  288. INT
  289. getcnr(iob)
  290. FILE *iob;
  291. {
  292.     switch(state) {
  293.     case NOHIST:
  294.         /* No relevant history */
  295.         state = SENTCHAR;
  296.         return lastchar = getc_crc(iob);
  297.     case SENTCHAR:
  298.         /* Lastchar is set, need lookahead */
  299.         switch(lastchar) {
  300.         case DLE:
  301.             state = NOHIST;
  302.             return 0;    /* indicates DLE was the data */
  303.         case EOF:
  304.             return EOF;
  305.         default:
  306.             for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
  307.                 ;
  308.             switch(likect) {
  309.             case 1:
  310.                 return lastchar = newchar;
  311.             case 2:
  312.                 /* just pass through */
  313.                 state = SENDNEWC;
  314.                 return lastchar;
  315.             default:
  316.                 state = SENDCNT;
  317.                 return DLE;
  318.             }
  319.         }
  320.     case SENDNEWC:
  321.         /* Previous sequence complete, newchar set */
  322.         state = SENTCHAR;
  323.         return lastchar = newchar;
  324.     case SENDCNT:
  325.         /* Sent DLE for repeat sequence, send count */
  326.         state = SENDNEWC;
  327.         return likect;
  328.     default:
  329.         fprintf(stderr,"sq: Bug - bad state\n");
  330.         exit(1);
  331.         /* NOTREACHED */
  332.     }
  333. }
  334.  
  335.  
  336. /******** Second translation - bytes to variable length bit strings *********/
  337.  
  338.  
  339. /* This translation uses the Huffman algorithm to develop a
  340.  * binary tree representing the decoding information for
  341.  * a variable length bit string code for each input value.
  342.  * Each string's length is in inverse proportion to its
  343.  * frequency of appearance in the incoming data stream.
  344.  * The encoding table is derived from the decoding table.
  345.  *
  346.  * The range of valid values into the Huffman algorithm are
  347.  * the values of a byte stored in an integer plus the special
  348.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  349.  *
  350.  * The "node" array of structures contains the nodes of the
  351.  * binary tree. The first NUMVALS nodes are the leaves of the
  352.  * tree and represent the values of the data bytes being
  353.  * encoded and the special endfile, SPEOF.
  354.  * The remaining nodes become the internal nodes of the tree.
  355.  *
  356.  * In the original design it was believed that
  357.  * a Huffman code would fit in the same number of
  358.  * bits that will hold the sum of all the counts.
  359.  * That was disproven by a user's file and was a rare but
  360.  * infamous bug. This version attempts to choose among equally
  361.  * weighted subtrees according to their maximum depths to avoid
  362.  * unnecessarily long codes. In case that is not sufficient
  363.  * to guarantee codes <= 16 bits long, we initially scale
  364.  * the counts so the total fits in an unsigned integer, but
  365.  * if codes longer than 16 bits are generated the counts are
  366.  * rescaled to a lower ceiling and code generation is retried.
  367.  */
  368.  
  369. /* Initialize the Huffman translation. This requires reading
  370.  * the input file through any preceding translation functions
  371.  * to get the frequency distribution of the various values.
  372.  */
  373.  
  374. init_huff(ib)
  375. FILE *ib;
  376. {
  377.     register INT c, i;
  378.     INT btlist[NUMVALS];    /* list of intermediate binary trees */
  379.     INT listlen;        /* length of btlist */
  380.     UNSIGNED *wp;        /* simplifies weight counting */
  381.     UNSIGNED ceiling;    /* limit for scaling */
  382.  
  383.     /* Initialize tree nodes to no weight, no children */
  384.     init_tree();
  385.  
  386.     /* Build frequency info in tree */
  387.     do {
  388.         c = getcnr(ib);
  389.         if(c == EOF)
  390.             c = SPEOF;
  391.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  392.             ++(*wp);
  393.     }
  394.     while(c != SPEOF);
  395.  
  396.     ceiling = MAXCOUNT;
  397.  
  398.     do {    /* Keep trying to scale and encode */
  399.         if(ceiling != MAXCOUNT)
  400.             fprintf(stderr, "sq: *** rescaling ***, ");
  401.         scale(ceiling);
  402.         ceiling /= 2;    /* in case we rescale */
  403.  
  404.         /* Build list of single node binary trees having
  405.                  * leaves for the input values with non-zero counts
  406.                  */
  407.         for(i = listlen = 0; i < NUMVALS; ++i)
  408.             if(node[i].weight != 0) {
  409.                 node[i].tdepth = 0;
  410.                 btlist[listlen++] = i;
  411.             }
  412.  
  413.         /* Arrange list of trees into a heap with the entry
  414.                  * indexing the node with the least weight at the top.
  415.                  */
  416.         heap(btlist, listlen);
  417.  
  418.         /* Convert the list of trees to a single decoding tree */
  419.         bld_tree(btlist, listlen);
  420.  
  421.         /* Initialize the encoding table */
  422.         init_enc();
  423.  
  424.         /* Try to build encoding table.
  425.                  * Fail if any code is > 16 bits long.
  426.                  */
  427.     }
  428.     while(buildenc(0, dctreehd) == ERROR);
  429.  
  430.     /* Initialize encoding variables */
  431.     cbitsrem = 0;    /*force initial read */
  432.     curin = 0;    /*anything but endfile*/
  433. }
  434.  
  435. /* The count of number of occurrances of each input value
  436.  * have already been prevented from exceeding MAXCOUNT.
  437.  * Now we must scale them so that their sum doesn't exceed
  438.  * ceiling and yet no non-zero count can become zero.
  439.  * This scaling prevents errors in the weights of the
  440.  * interior nodes of the Huffman tree and also ensures that
  441.  * the codes will fit in an unsigned integer. Rescaling is
  442.  * used if necessary to limit the code length.
  443.  */
  444.  
  445. scale(ceil)
  446. UNSIGNED ceil;    /* upper limit on total weight */
  447. {
  448.     register INT i,c;
  449.     INT ovflw, divisor;
  450.     UNSIGNED w, sum;
  451.     unsigned char increased;     /* flag */
  452.  
  453.     do {
  454.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  455.             if(node[i].weight > (ceil - sum))
  456.                 ++ovflw;
  457.             sum += node[i].weight;
  458.         }
  459.  
  460.         divisor = ovflw + 1;
  461.  
  462.         /* Ensure no non-zero values are lost */
  463.         increased = FALSE;
  464.         for(i = 0; i < NUMVALS; ++i) {
  465.             w = node[i].weight;
  466.             if (w < divisor && w != 0) {
  467.                 /* Don't fail to provide a code if it's used at all */
  468.                 node[i].weight = divisor;
  469.                 increased = TRUE;
  470.             }
  471.         }
  472.     }
  473.     while(increased);
  474.  
  475.     /* Scaling factor choosen, now scale */
  476.     if(divisor > 1)
  477.         for(i = 0; i < NUMVALS; ++i)
  478.             node[i].weight /= divisor;
  479. }
  480.  
  481. /* heap() and adjust() maintain a list of binary trees as a
  482.  * heap with the top indexing the binary tree on the list
  483.  * which has the least weight or, in case of equal weights,
  484.  * least depth in its longest path. The depth part is not
  485.  * strictly necessary, but tends to avoid long codes which
  486.  * might provoke rescaling.
  487.  */
  488.  
  489. heap(list, length)
  490. INT list[], length;
  491. {
  492.     register INT i;
  493.  
  494.     for(i = (length - 2) / 2; i >= 0; --i)
  495.         adjust(list, i, length - 1);
  496. }
  497.  
  498. /* Make a heap from a heap with a new top */
  499.  
  500. adjust(list, top, bottom)
  501. INT list[], top, bottom;
  502. {
  503.     register INT k, temp;
  504.  
  505.     k = 2 * top + 1;    /* left child of top */
  506.     temp = list[top];    /* remember root node of top tree */
  507.     if( k <= bottom) {
  508.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  509.             ++k;
  510.  
  511.         /* k indexes "smaller" child (in heap of trees) of top */
  512.         /* now make top index "smaller" of old top and smallest child */
  513.         if(cmptrees(temp, list[k])) {
  514.             list[top] = list[k];
  515.             list[k] = temp;
  516.             /* Make the changed list a heap */
  517.             adjust(list, k, bottom); /*recursive*/
  518.         }
  519.     }
  520. }
  521.  
  522. /* Compare two trees, if a > b return true, else return false
  523.  * note comparison rules in previous comments.
  524.  */
  525.  
  526. cmptrees(a, b)
  527. INT a, b;    /* root nodes of trees */
  528. {
  529.     if(node[a].weight > node[b].weight)
  530.         return TRUE;
  531.     if(node[a].weight == node[b].weight)
  532.         if(node[a].tdepth > node[b].tdepth)
  533.             return TRUE;
  534.     return FALSE;
  535. }
  536.  
  537. /* HUFFMAN ALGORITHM: develops the single element trees
  538.  * into a single binary tree by forming subtrees rooted in
  539.  * interior nodes having weights equal to the sum of weights of all
  540.  * their descendents and having depth counts indicating the
  541.  * depth of their longest paths.
  542.  *
  543.  * When all trees have been formed into a single tree satisfying
  544.  * the heap property (on weight, with depth as a tie breaker)
  545.  * then the binary code assigned to a leaf (value to be encoded)
  546.  * is then the series of left (0) and right (1)
  547.  * paths leading from the root to the leaf.
  548.  * Note that trees are removed from the heaped list by
  549.  * moving the last element over the top element and
  550.  * reheaping the shorter list.
  551.  */
  552.  
  553. bld_tree(list, len)
  554. INT list[];
  555. INT len;
  556. {
  557.     register INT freenode;        /* next free node in tree */
  558.     register struct nd *frnp;    /* free node pointer */
  559.     INT lch, rch;        /* temporaries for left, right children */
  560.     INT i;
  561.  
  562.     /* Initialize index to next available (non-leaf) node.
  563.          * Lower numbered nodes correspond to leaves (data values).
  564.          */
  565.     freenode = NUMVALS;
  566.  
  567.     while(len > 1) {
  568.         /* Take from list two btrees with least weight
  569.                  * and build an interior node pointing to them.
  570.                  * This forms a new tree.
  571.                  */
  572.         lch = list[0];    /* This one will be left child */
  573.  
  574.         /* delete top (least) tree from the list of trees */
  575.         list[0] = list[--len];
  576.         adjust(list, 0, len - 1);
  577.  
  578.         /* Take new top (least) tree. Reuse list slot later */
  579.         rch = list[0];    /* This one will be right child */
  580.  
  581.         /* Form new tree from the two least trees using
  582.                  * a free node as root. Put the new tree in the list.
  583.                  */
  584.         frnp = &node[freenode]; /* address of next free node */
  585.         list[0] = freenode++;    /* put at top for now */
  586.         frnp->lchild = lch;
  587.         frnp->rchild = rch;
  588.         frnp->weight = node[lch].weight + node[rch].weight;
  589.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  590.         /* reheap list    to get least tree at top*/
  591.         adjust(list, 0, len - 1);
  592.     }
  593.     dctreehd = list[0];    /*head of final tree */
  594. }
  595.  
  596. /* ???????????? */
  597. maxchar(a, b)
  598. {
  599.     return a > b ? a : b;
  600. }
  601. /* Initialize all nodes to single element binary trees
  602.  * with zero weight and depth.
  603.  */
  604.  
  605. init_tree()
  606. {
  607.     register INT i;
  608.  
  609.     for(i = 0; i < NUMNODES; ++i) {
  610.         node[i].weight = 0;
  611.         node[i].tdepth = 0;
  612.         node[i].lchild = NOCHILD;
  613.         node[i].rchild = NOCHILD;
  614.     }
  615. }
  616.  
  617. init_enc()
  618. {
  619.     register INT i;
  620.  
  621.     /* Initialize encoding table */
  622.     for(i = 0; i < NUMVALS; ++i) {
  623.         codelen[i] = 0;
  624.     }
  625. }
  626.  
  627. /* Recursive routine to walk the indicated subtree and level
  628.  * and maintain the current path code in bstree. When a leaf
  629.  * is found the entire code string and length are put into
  630.  * the encoding table entry for the leaf's data value .
  631.  *
  632.  * Returns ERROR if codes are too long.
  633.  */
  634.  
  635. INT        /* returns ERROR or NULL */
  636. buildenc(level, root)
  637. INT level;/* level of tree being examined, from zero */
  638. INT root; /* root of subtree is also data value if leaf */
  639. {
  640.     register INT l, r;
  641.  
  642.     l = node[root].lchild;
  643.     r = node[root].rchild;
  644.  
  645.     if( l == NOCHILD && r == NOCHILD) {
  646.         /* Leaf. Previous path determines bit string
  647.                  * code of length level (bits 0 to level - 1).
  648.                  * Ensures unused code bits are zero.
  649.                  */
  650.         codelen[root] = level;
  651.         code[root] = tcode & (((UNSIGNED)~0) >> (16 - level));
  652.         return (level > 16) ? ERROR : NULL;
  653.     }
  654.     else {
  655.         if( l != NOCHILD) {
  656.             /* Clear path bit and continue deeper */
  657.             tcode &= ~(1 << level);
  658.             /* NOTE RECURSION */
  659.             if(buildenc(level + 1, l) == ERROR)
  660.                 return ERROR;
  661.         }
  662.         if(r != NOCHILD) {
  663.             /* Set path bit and continue deeper */
  664.             tcode |= 1 << level;
  665.             /* NOTE RECURSION */
  666.             if(buildenc(level + 1, r) == ERROR)
  667.                 return ERROR;
  668.         }
  669.     }
  670.     return NULL;    /* if we got here we're ok so far */
  671. }
  672.  
  673. /* Write out the header of the compressed file */
  674.  
  675. wrt_head(ob, infile)
  676. FILE *ob;
  677. unsigned char *infile;     /* input file name (w/ or w/o drive) */
  678. {
  679.     register INT l,r;
  680.     INT i, k;
  681.     INT numnodes;        /* nbr of nodes in simplified tree */
  682.  
  683.     putwe(RECOGNIZE, ob);    /* identifies as compressed */
  684.     putwe(crc, ob);     /* unsigned sum of original data */
  685.  
  686.     /* Record the original file name w/o drive */
  687.     if(*(infile + 1) == ':')
  688.         infile += 2;    /* skip drive */
  689.  
  690.     do {
  691.         putce(*infile, ob);
  692.     }
  693.     while(*(infile++) != '\0');
  694.  
  695.  
  696.     /* Write out a simplified decoding tree. Only the interior
  697.          * nodes are written. When a child is a leaf index
  698.          * (representing a data value) it is recoded as
  699.          * -(index + 1) to distinguish it from interior indexes
  700.          * which are recoded as positive indexes in the new tree.
  701.          * Note that this tree will be empty for an empty file.
  702.          */
  703.  
  704.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  705.     putwe(numnodes, ob);
  706.  
  707.     for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  708.         l = node[i].lchild;
  709.         r = node[i].rchild;
  710.         l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  711.         r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  712.         putwe(l, ob);    /* left child */
  713.         putwe(r, ob);    /* right child */
  714.     }
  715. }
  716.  
  717. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  718.  *
  719.  * There are two unsynchronized bit-byte relationships here.
  720.  * The input stream bytes are converted to bit strings of
  721.  * various lengths via the static variables named c...
  722.  * These bit strings are concatenated without padding to
  723.  * become the stream of encoded result bytes, which this
  724.  * function returns one at a time. The EOF (end of file) is
  725.  * converted to SPEOF for convenience and encoded like any
  726.  * other input value. True EOF is returned after that.
  727.  *
  728.  * The original gethuff() called a seperate function,
  729.  * getbit(), but that more readable version was too slow.
  730.  */
  731.  
  732. INT        /*  Returns byte values except for EOF */
  733. gethuff(ib)
  734. FILE *ib;
  735. {
  736.     INT rbyte;    /* Result byte value */
  737.     INT need, take; /* numbers of bits */
  738.  
  739.     rbyte = 0;
  740.     need = 8;    /* build one byte per call */
  741.  
  742.     /* Loop to build a byte of encoded data
  743.          * Initialization forces read the first time
  744.          */
  745.  
  746. loop:
  747.     if(cbitsrem >= need) {
  748.         /* Current code fullfills our needs */
  749.         if(need == 0)
  750.             return rbyte;
  751.         /* Take what we need */
  752.         rbyte |= ccode << (8 - need);
  753.         /* And leave the rest */
  754.         ccode >>= need;
  755.         cbitsrem -= need;
  756.         return rbyte & 0xff;
  757.     }
  758.  
  759.     /* We need more than current code */
  760.     if(cbitsrem > 0) {
  761.         /* Take what there is */
  762.         rbyte |= ccode << (8 - need);
  763.         need -= cbitsrem;
  764.     }
  765.     /* No more bits in current code string */
  766.     if(curin == SPEOF) {
  767.         /* The end of file token has been encoded. If
  768.                  * result byte has data return it and do EOF next time
  769.                  */
  770.         cbitsrem = 0;
  771.  
  772.         /*NOTE: +0 is to fight compiler bug? */
  773.         return (need == 8) ? EOF : rbyte + 0;
  774.     }
  775.  
  776.     /* Get an input byte */
  777.     if((curin = getcnr(ib)) == EOF)
  778.         curin = SPEOF;    /* convenient for encoding */
  779.  
  780.     /* Get the new byte's code */
  781.     ccode = code[curin];
  782.     cbitsrem = codelen[curin];
  783.  
  784.     goto loop;
  785. }
  786.  
  787.  
  788. /* Get next byte from file and update checksum */
  789.  
  790. INT
  791. getc_crc(ib)
  792. FILE *ib;
  793. {
  794.     register INT c;
  795.  
  796.     c = getc(ib);
  797.     if(c != EOF)
  798.         crc += c;    /* checksum */
  799.     return c;
  800. }
  801.  
  802. /* Output functions with error reporting */
  803.  
  804. putce(c, iob)
  805. INT c;
  806. FILE *iob;
  807. {
  808.     if(putc(c, iob) == ERROR && ferror(iob)) {
  809.         fprintf(stderr, "sq: write error\n");
  810.         exit(1);
  811.     }
  812. }
  813.  
  814. /*
  815.  * machine independent put-word that writes low order byte first
  816.  *  (compatible with CP/M original) regardless of host cpu.
  817.  */
  818. putwe(w, iob)
  819. INT w;
  820. FILE *iob;
  821. {
  822.     putc(w, iob);
  823.     putc(w>>8, iob);
  824.     if (ferror(iob)) {
  825.         fprintf(stderr, "sq: write error\n");
  826.         exit(1);
  827.     }
  828. }
  829.