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