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