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