home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 2 / CDPD_II_2352.bin / scope / 176-200 / scopedisk192 / unzipv3.1 / unimplod.c < prev    next >
C/C++ Source or Header  |  1992-10-27  |  8KB  |  297 lines
  1. /* ------------------------------------------------------------- */
  2. /*
  3.  * Imploding
  4.  * ---------
  5.  *
  6.  * The Imploding algorithm is actually a combination of two distinct
  7.  * algorithms.  The first algorithm compresses repeated byte sequences
  8.  * using a sliding dictionary.  The second algorithm is used to compress
  9.  * the encoding of the sliding dictionary ouput, using multiple
  10.  * Shannon-Fano trees.
  11.  *
  12.  */
  13.  
  14.  
  15.    sf_tree  lit_tree;
  16.    sf_tree  length_tree;
  17.    sf_tree  distance_tree;
  18.    /* s-f storage is shared with that used by other comp. methods */
  19.    sf_node  *lit_nodes = (sf_node *) followers;     /* 2*LITVALS nodes */
  20.    sf_node  *length_nodes = (sf_node *) suffix_of;  /* 2*LENVALS nodes */
  21.    sf_node  *distance_nodes = (sf_node *) stack;    /* 2*DISTVALS nodes */
  22.    boolean  lit_tree_present;
  23.    boolean  eightK_dictionary;
  24.    int      minimum_match_length;
  25.    int      dict_bits;
  26.  
  27. #ifdef __TURBOC__
  28. /* v2.0b More local prototypes */
  29. void ReadLengths(sf_tree *tree);
  30. void SortLengths(sf_tree *tree);
  31. void GenerateTrees(sf_tree *tree, sf_node *nodes);
  32. void LoadTree(sf_tree *tree, int treesize, sf_node *nodes);
  33. void LoadTrees(void);
  34. void ReadTree(register sf_node *nodes, int *dest);
  35. #endif
  36.  
  37. void         SortLengths(tree)
  38. sf_tree *tree;
  39.   /* Sort the Bit Lengths in ascending order, while retaining the order
  40.     of the original lengths stored in the file */
  41. {
  42.     register sf_entry *ejm1;    /* entry[j - 1] */
  43.     register int j;
  44.     register sf_entry *entry;
  45.     register int i;
  46.     sf_entry tmp;
  47.     int entries;
  48.     unsigned a, b;
  49.  
  50.     entry = &tree->entry[0];
  51.     entries = tree->entries;
  52.  
  53.     for (i = 0; ++i < entries; )  {
  54.         tmp = entry[i];
  55.         b = tmp.BitLength;
  56.         j = i;
  57.         while ((j > 0)
  58.         && ((a = (ejm1 = &entry[j - 1])->BitLength) >= b))  {
  59.             if ((a == b) && (ejm1->Value <= tmp.Value))
  60.                 break;
  61.             *(ejm1 + 1) = *ejm1;    /* entry[j] = entry[j - 1] */
  62.             --j;
  63.         }
  64.         entry[j] = tmp;
  65.     }
  66. }
  67.  
  68.  
  69. /* ----------------------------------------------------------- */
  70.  
  71. void         ReadLengths(tree)
  72. sf_tree *tree;
  73. {
  74.    int    treeBytes;
  75.    int    i;
  76.    int    num, len;
  77.  
  78.   /* get number of bytes in compressed tree */
  79.    READBIT(8,treeBytes);
  80.    treeBytes++;
  81.    i = 0;
  82.  
  83.    tree->MaxLength = 0;
  84.  
  85. /* High 4 bits: Number of values at this bit length + 1. (1 - 16)
  86.  * Low  4 bits: Bit Length needed to represent value + 1. (1 - 16)
  87.  */
  88.    while (treeBytes > 0) {
  89.       READBIT(4,len); len++;
  90.       READBIT(4,num); num++;
  91.  
  92.       while (num > 0) {
  93.          if (len > tree->MaxLength)
  94.             tree->MaxLength = len;
  95.          tree->entry[i].BitLength = len;
  96.          tree->entry[i].Value = i;
  97.          i++;
  98.          num--;
  99.       }
  100.  
  101.       treeBytes--;
  102.    }
  103. }
  104.  
  105.  
  106. /* ----------------------------------------------------------- */
  107.  
  108. void         GenerateTrees(tree, nodes)
  109. sf_tree *tree;
  110. sf_node *nodes;
  111.      /* Generate the Shannon-Fano trees */
  112. {
  113.     int codelen, i, j, lvlstart, next, parents;
  114.  
  115.     i = tree->entries - 1;          /* either 255 or 63 */
  116.     lvlstart = next = 1;
  117.  
  118.     /* believe it or not, there may be a 1-bit code */
  119.  
  120.     for (codelen = tree->MaxLength; codelen >= 1; --codelen)  {
  121.  
  122.         /* create leaf nodes at level <codelen> */
  123.  
  124.         while ((i >= 0) && (tree->entry[i].BitLength == codelen))  {
  125.             nodes[next].left = 0;
  126.             nodes[next].right = tree->entry[i].Value;
  127.             ++next;
  128.             --i;
  129.         }
  130.  
  131.         /* create parent nodes for all nodes at level <codelen>,
  132.            but don't create the root node here */
  133.  
  134.         parents = next;
  135.         if (codelen > 1)  {
  136.             for (j = lvlstart; j <= parents-2; j += 2)  {
  137.                 nodes[next].left = j;
  138.                 nodes[next].right = j + 1;
  139.                 ++next;
  140.             }
  141.         }
  142.         lvlstart = parents;
  143.     }
  144.  
  145.     /* create root node */
  146.  
  147.     nodes[0].left = next - 2;
  148.     nodes[0].right = next - 1;
  149. }
  150.  
  151.  
  152. /* ----------------------------------------------------------- */
  153.  
  154. void         LoadTree(tree, treesize, nodes)
  155. sf_tree *tree;
  156. int treesize;
  157. sf_node *nodes;
  158.      /* allocate and load a shannon-fano tree from the compressed file */
  159. {
  160.    tree->entries = treesize;
  161.    ReadLengths(tree);
  162.    SortLengths(tree);
  163.    GenerateTrees(tree, nodes);
  164. }
  165.  
  166.  
  167. /* ----------------------------------------------------------- */
  168.  
  169. void         LoadTrees()
  170. {
  171.    eightK_dictionary = (lrec.general_purpose_bit_flag & 0x02) != 0; /* bit 1 */
  172.    lit_tree_present = (lrec.general_purpose_bit_flag & 0x04) != 0;  /* bit 2 */
  173.  
  174.    if (eightK_dictionary)
  175.       dict_bits = 7;
  176.    else
  177.       dict_bits = 6;
  178.  
  179.    if (lit_tree_present) {
  180.       minimum_match_length = 3;
  181.       LoadTree(&lit_tree,256,lit_nodes);
  182.    }
  183.    else
  184.       minimum_match_length = 2;
  185.  
  186.    LoadTree(&length_tree,64,length_nodes);
  187.    LoadTree(&distance_tree,64,distance_nodes);
  188. }
  189.  
  190.  
  191. /* ----------------------------------------------------------- */
  192.  
  193. #ifndef ASM
  194.  
  195. void         ReadTree(nodes, dest)
  196. register sf_node *nodes;
  197. int *dest;
  198.      /* read next byte using a shannon-fano tree */
  199. {
  200.     register int cur;
  201.     register int left;
  202.     UWORD b;
  203.  
  204.     for (cur = 0; ; )  {
  205.         if ((left = nodes[cur].left) == 0)  {
  206.             *dest = nodes[cur].right;
  207.             return;
  208.         }
  209.         READBIT(1, b);
  210.         cur = (b ? nodes[cur].right : left);
  211.     }
  212. }
  213.  
  214. #endif
  215.  
  216. /* ----------------------------------------------------------- */
  217.  
  218. void         unImplode()
  219.      /* expand imploded data */
  220. {
  221.    register int srcix;
  222.    register int Length;
  223.    register int limit;
  224.    int          lout;
  225.    int          Distance;
  226.  
  227.    LoadTrees();
  228.  
  229. #ifdef DEBUG
  230.    printf("\n");
  231. #endif
  232.    while ((!zipeof) && ((outpos+outcnt) < ucsize)) {
  233.       READBIT(1,lout);
  234.  
  235.       if (lout != 0) {   /* encoded data is literal data */
  236.          if (lit_tree_present)  /* use Literal Shannon-Fano tree */  {
  237.             ReadTree(lit_nodes,&lout);
  238. #ifdef DEBUG
  239.             printf("lit=%d\n", lout);
  240. #endif
  241.          }
  242.          else
  243.             READBIT(8,lout);
  244.  
  245.          OUTB(lout);
  246.       }
  247.       else {            /* encoded data is sliding dictionary match */
  248.          READBIT(dict_bits,Distance);
  249.  
  250.          ReadTree(distance_nodes,&lout);
  251. #ifdef DEBUG
  252.      printf("d=%5d (%2d,%3d)", (lout << dict_bits) | Distance, lout,
  253.             Distance);
  254. #endif
  255.          Distance |= (lout << dict_bits);
  256.          /* using the Distance Shannon-Fano tree, read and decode the
  257.             upper 6 bits of the Distance value */
  258.  
  259.          ReadTree(length_nodes,&lout);
  260.          Length = lout;
  261. #ifdef DEBUG
  262.      printf("\tl=%3d\n", Length);
  263. #endif
  264.          /* using the Length Shannon-Fano tree, read and decode the
  265.             Length value */
  266.  
  267.          if (Length == 63) {
  268.             READBIT(8,lout);
  269.             Length += lout;
  270.          }
  271.          Length += minimum_match_length;
  272.  
  273.         /* move backwards Distance+1 bytes in the output stream, and copy
  274.           Length characters from this position to the output stream.
  275.           (if this position is before the start of the output stream,
  276.           then assume that all the data before the start of the output
  277.           stream is filled with zeros.  Requires initializing outbuf
  278.           for each file.) */
  279.  
  280.         srcix = (outcnt - (Distance + 1)) & (OUTBUFSIZ-1);
  281.         limit = OUTBUFSIZ - Length;
  282.         if ((srcix <= limit) && (outcnt < limit))  {
  283.             zmemcpy(outptr, &outbuf[srcix], Length);
  284.             outptr += Length;
  285.             outcnt += Length;
  286.         }
  287.         else {
  288.             while (Length--)  {
  289.                 OUTB(outbuf[srcix++]);
  290.                 srcix &= OUTBUFSIZ-1;
  291.             }
  292.         }
  293.       }
  294.    }
  295. }
  296.  
  297.