home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / LZ77CODE.ZIP / PROG2.C < prev    next >
C/C++ Source or Header  |  1994-03-24  |  13KB  |  526 lines
  1. /* PROG2.C                                                       */
  2. /* Simple Hashing LZ77 Sliding Dictionary Compression Program    */
  3. /* By Rich Geldreich, Jr. October, 1993                          */
  4. /* Originally compiled with QuickC v2.5 in the small model.      */
  5. /* This program uses more efficient code to delete strings from  */
  6. /* the sliding dictionary compared to PROG1.C, at the expense of */
  7. /* greater memory requirements. See the HashData and DeleteData  */
  8. /* subroutines.                                                  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <ctype.h>
  14.  
  15. /* set this to 1 for a greedy encoder */
  16. #define GREEDY    0
  17.  
  18. /* ratio vs. speed constant */
  19. /* the larger this constant, the better the compression */
  20. #define MAXCOMPARES 75
  21.  
  22. /* unused entry flag */
  23. #define NIL       0xFFFF
  24.  
  25. /* bits per symbol- normally 8 for general purpose compression */
  26. #define CHARBITS  8
  27.  
  28. /* minimum match length & maximum match length */
  29. #define THRESHOLD 2
  30. #define MATCHBITS 4
  31. #define MAXMATCH  ((1 << MATCHBITS) + THRESHOLD - 1)
  32.  
  33. /* sliding dictionary size and hash table's size */
  34. /* some combinations of HASHBITS and THRESHOLD values will not work
  35.    correctly because of the way this program hashes strings */
  36. #define DICTBITS  13
  37. #define HASHBITS  10
  38. #define DICTSIZE  (1 << DICTBITS)
  39. #define HASHSIZE  (1 << HASHBITS)
  40.  
  41. /* # bits to shift after each XOR hash */
  42. /* this constant must be high enough so that only THRESHOLD + 1
  43.    characters are in the hash accumulator at one time */
  44. #define SHIFTBITS ((HASHBITS + THRESHOLD) / (THRESHOLD + 1))
  45.  
  46. /* sector size constants */
  47. #define SECTORBIT 10
  48. #define SECTORLEN (1 << SECTORBIT)
  49.  
  50. #define HASHFLAG1 0x8000
  51. #define HASHFLAG2 0x7FFF
  52.  
  53. /* dictionary plus MAXMATCH extra chars for string comparisions */
  54. unsigned char
  55.   dict[DICTSIZE + MAXMATCH];
  56.  
  57. /* hashtable & link list tables */
  58. unsigned int
  59.   hash[HASHSIZE],
  60.   nextlink[DICTSIZE],
  61.   lastlink[DICTSIZE];
  62.  
  63. /* misc. global variables */
  64. unsigned int
  65.   matchlength,
  66.   matchpos,
  67.   bitbuf,
  68.   bitsin,
  69.   masks[17] = {0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535};
  70.  
  71. FILE *infile, *outfile;
  72.  
  73. /* writes multiple bit codes to the output stream */
  74. void SendBits(unsigned int bits, unsigned int numbits)
  75. {
  76.  
  77.   bitbuf |= (bits << bitsin);
  78.  
  79.   bitsin += numbits;
  80.  
  81.   if (bitsin > 16)         /* special case when # bits in buffer exceeds 16 */
  82.   {
  83.     if (putc(bitbuf & 0xFF, outfile) == EOF)
  84.     {
  85.       printf("\nerror writing to output file");
  86.       exit(EXIT_FAILURE);
  87.     }
  88.     bitbuf = bits >> (8 - (bitsin - numbits));
  89.     bitsin -= 8;
  90.   }
  91.  
  92.   while (bitsin >= 8)
  93.   {
  94.     if (putc(bitbuf & 0xFF, outfile) == EOF)
  95.     {
  96.       printf("\nerror writing to output file");
  97.       exit(EXIT_FAILURE);
  98.     }
  99.     bitbuf >>= 8;
  100.     bitsin -= 8;
  101.   }
  102.  
  103. }
  104.  
  105. /* reads multiple bit codes from the input stream */
  106. unsigned int ReadBits(unsigned int numbits)
  107. {
  108.  
  109.   register unsigned int i;
  110.  
  111.   i = bitbuf >> (8 - bitsin);
  112.  
  113.   while (numbits > bitsin)
  114.   {
  115.     if ((bitbuf = getc(infile)) == EOF)
  116.     {
  117.       printf("\nerror reading from input file");
  118.       exit(EXIT_FAILURE);
  119.     }
  120.     i |= (bitbuf << bitsin);
  121.     bitsin += 8;
  122.   }
  123.  
  124.   bitsin -= numbits;
  125.  
  126.   return (i & masks[numbits]);
  127.  
  128. }
  129.  
  130. /* sends a match to the output stream */
  131. void SendMatch(unsigned int matchlen, unsigned int matchdistance)
  132. {
  133.   SendBits(1, 1);
  134.  
  135.   SendBits(matchlen - (THRESHOLD + 1), MATCHBITS);
  136.  
  137.   SendBits(matchdistance, DICTBITS);
  138. }
  139.  
  140. /* sends one character (or literal) to the output stream */
  141. void SendChar(unsigned int character)
  142. {
  143.   SendBits(0, 1);
  144.  
  145.   SendBits(character, CHARBITS);
  146. }
  147.  
  148. /* initializes the search structures needed for compression */
  149. void InitEncode(void)
  150. {
  151.   register unsigned int i;
  152.  
  153.   for (i = 0; i < HASHSIZE; i++) hash[i] = NIL;
  154.  
  155.   nextlink[DICTSIZE] = NIL;
  156.  
  157. }
  158.  
  159. /* loads dictionary with characters from the input stream */
  160. unsigned int LoadDict(unsigned int dictpos)
  161. {
  162.   register unsigned int i, j;
  163.  
  164.   if ((i = fread(&dict[dictpos], sizeof (char), SECTORLEN, infile)) == EOF)
  165.   {
  166.     printf("\nerror reading from input file");
  167.     exit(EXIT_FAILURE);
  168.   }
  169.  
  170.   /* since the dictionary is a ring buffer, copy the characters at
  171.      the very start of the dictionary to the end */
  172.   if (dictpos == 0)
  173.   {
  174.     for (j = 0; j < MAXMATCH; j++) dict[j + DICTSIZE] = dict[j];
  175.   }
  176.  
  177.   return i;
  178. }
  179.  
  180. /* deletes data from the dictionary search structures */
  181. /* this is only done when the number of bytes to be   */
  182. /* compressed exceeds the dictionary's size           */
  183. void DeleteData(unsigned int dictpos)
  184. {
  185.  
  186.   register unsigned int i, j, k;
  187.  
  188.   /* delete all references to the sector being deleted */
  189.  
  190.   k = dictpos + SECTORLEN;
  191.  
  192.   for (i = dictpos; i < k; i++)
  193.   {
  194.     if ((j = lastlink[i]) & HASHFLAG1)
  195.       {
  196.         if (j != NIL) hash[j & HASHFLAG2] = NIL;
  197.       }
  198.     else
  199.       nextlink[j] = NIL;
  200.   }
  201.  
  202. }
  203.  
  204. /* hash data just entered into dictionary */
  205. /* XOR hashing is used here, but practically any hash function will work */
  206. void HashData(unsigned int dictpos, unsigned int bytestodo)
  207. {
  208.   register unsigned int i, j, k;
  209.  
  210.   if (bytestodo <= THRESHOLD)   /* not enough bytes in sector for match? */
  211.     for (i = 0; i < bytestodo; i++)
  212.       nextlink[dictpos + i] = lastlink[dictpos + i] = NIL;
  213.   else
  214.   {
  215.     /* matches can't cross sector boundries */
  216.     for (i = bytestodo - THRESHOLD; i < bytestodo; i++)
  217.       nextlink[dictpos + i] = lastlink[dictpos + i] = NIL;
  218.  
  219.     j = (((unsigned int)dict[dictpos]) << SHIFTBITS) ^ dict[dictpos + 1];
  220.  
  221.     k = dictpos + bytestodo - THRESHOLD;  /* calculate end of sector */
  222.  
  223.     for (i = dictpos; i < k; i++)
  224.     {
  225.       lastlink[i] = (j = (((j << SHIFTBITS) & (HASHSIZE - 1)) ^ dict[i + THRESHOLD])) | HASHFLAG1;
  226.       if ((nextlink[i] = hash[j]) != NIL) lastlink[nextlink[i]] = i;
  227.       hash[j] = i;
  228.     }
  229.   }
  230. }
  231.  
  232. /* finds match for string at position dictpos     */
  233. /* this search code finds the longest AND closest */
  234. /* match for the string at dictpos                */
  235. void FindMatch(unsigned int dictpos, unsigned int startlen)
  236. {
  237.   register unsigned int i, j, k;
  238.   unsigned char l;
  239.  
  240.   i = dictpos; matchlength = startlen; k = MAXCOMPARES;
  241.   l = dict[dictpos + matchlength];
  242.  
  243.   do
  244.   {
  245.     if ((i = nextlink[i]) == NIL) return;   /* get next string in list */
  246.  
  247.     if (dict[i + matchlength] == l)        /* possible larger match? */
  248.     {
  249.       for (j = 0; j < MAXMATCH; j++)          /* compare strings */
  250.         if (dict[dictpos + j] != dict[i + j]) break;
  251.  
  252.       if (j > matchlength)  /* found larger match? */
  253.       {
  254.         matchlength = j;
  255.         matchpos = i;
  256.         if (matchlength == MAXMATCH) return;  /* exit if largest possible match */
  257.         l = dict[dictpos + matchlength];
  258.       }
  259.     }
  260.   }
  261.   while (--k);  /* keep on trying until we run out of chances */
  262.  
  263. }
  264.  
  265. /* finds dictionary matches for characters in current sector */
  266. void DictSearch(unsigned int dictpos, unsigned int bytestodo)
  267. {
  268.  
  269.   register unsigned int i, j;
  270.  
  271. #if (GREEDY == 0)
  272.  
  273.   unsigned int matchlen1, matchpos1;
  274.  
  275.   /* non-greedy search loop (slow) */
  276.  
  277.   i = dictpos; j = bytestodo;
  278.  
  279.   while (j) /* loop while there are still characters left to be compressed */
  280.   {
  281.     FindMatch(i, THRESHOLD);
  282.  
  283.     if (matchlength > THRESHOLD)
  284.     {
  285.       matchlen1 = matchlength;
  286.       matchpos1 = matchpos;
  287.  
  288.       for ( ; ; )
  289.       {
  290.         FindMatch(i + 1, matchlen1);
  291.  
  292.         if (matchlength > matchlen1)
  293.         {
  294.           matchlen1 = matchlength;
  295.           matchpos1 = matchpos;
  296.           SendChar(dict[i++]);
  297.           j--;
  298.         }
  299.         else
  300.         {
  301.           if (matchlen1 > j)
  302.           {
  303.             matchlen1 = j;
  304.             if (matchlen1 <= THRESHOLD) { SendChar(dict[i++]); j--; break; }
  305.           }
  306.  
  307.           SendMatch(matchlen1, (i - matchpos1) & (DICTSIZE - 1));
  308.           i += matchlen1;
  309.           j -= matchlen1;
  310.           break;
  311.         }
  312.       }
  313.     }
  314.     else
  315.     {
  316.       SendChar(dict[i++]);
  317.       j--;
  318.     }
  319.   }
  320.  
  321. #else
  322.  
  323.   /* greedy search loop (fast) */
  324.  
  325.   i = dictpos; j = bytestodo;
  326.  
  327.   while (j) /* loop while there are still characters left to be compressed */
  328.   {
  329.     FindMatch(i, THRESHOLD);
  330.  
  331.     if (matchlength > j) matchlength = j;     /* clamp matchlength */
  332.  
  333.     if (matchlength > THRESHOLD)  /* valid match? */
  334.     {
  335.       SendMatch(matchlength, (i - matchpos) & (DICTSIZE - 1));
  336.       i += matchlength;
  337.       j -= matchlength;
  338.     }
  339.     else
  340.     {
  341.       SendChar(dict[i++]);
  342.       j--;
  343.     }
  344.   }
  345.  
  346. #endif
  347.  
  348. }
  349.  
  350. /* main encoder */
  351. void Encode (void)
  352. {
  353.   unsigned int dictpos, deleteflag, sectorlen;
  354.     unsigned long bytescompressed;
  355.  
  356.   InitEncode();
  357.  
  358.   dictpos = deleteflag = 0;
  359.  
  360.   bytescompressed = 0;
  361.  
  362.   while (1)
  363.   {
  364.     /* delete old data from dictionary */
  365.     if (deleteflag) DeleteData(dictpos);
  366.  
  367.     /* grab more data to compress */
  368.     if ((sectorlen = LoadDict(dictpos)) == 0) break;
  369.  
  370.     /* hash the data */
  371.     HashData(dictpos, sectorlen);
  372.  
  373.     /* find dictionary matches */
  374.     DictSearch(dictpos, sectorlen);
  375.  
  376.     bytescompressed += sectorlen;
  377.  
  378.     printf("\r%ld", bytescompressed);
  379.  
  380.     dictpos += SECTORLEN;
  381.  
  382.     /* wrap back to beginning of dictionary when its full */
  383.     if (dictpos == DICTSIZE)
  384.     {
  385.       dictpos = 0;
  386.       deleteflag = 1;   /* ok to delete now */
  387.     }
  388.   }
  389.  
  390.   /* Send EOF flag */
  391.   SendMatch(MAXMATCH + 1, 0);
  392.  
  393.   /* Flush bit buffer */
  394.   if (bitsin) SendBits(0, 8 - bitsin);
  395.  
  396.   return;
  397. }
  398.  
  399. /* main decoder */
  400. void Decode (void)
  401. {
  402.  
  403.   register unsigned int i, j, k;
  404.   unsigned long bytesdecompressed;
  405.  
  406.   i = 0;
  407.   bytesdecompressed = 0;
  408.  
  409.   for ( ; ; )
  410.   {
  411.     if (ReadBits(1) == 0)   /* character or match? */
  412.     {
  413.       dict[i++] = ReadBits(CHARBITS);
  414.       if (i == DICTSIZE)
  415.       {
  416.         if (fwrite(&dict, sizeof (char), DICTSIZE, outfile) == EOF)
  417.         {
  418.           printf("\nerror writing to output file");
  419.           exit(EXIT_FAILURE);
  420.         }
  421.         i = 0;
  422.         bytesdecompressed += DICTSIZE;
  423.         printf("\r%ld", bytesdecompressed);
  424.       }
  425.     }
  426.     else
  427.     {
  428.       /* get match length from input stream */
  429.       k = (THRESHOLD + 1) + ReadBits(MATCHBITS);
  430.  
  431.       if (k == (MAXMATCH + 1))      /* Check for EOF flag */
  432.       {
  433.         if (fwrite(&dict, sizeof (char), i, outfile) == EOF)
  434.         {
  435.           printf("\nerror writing to output file");
  436.           exit(EXIT_FAILURE);
  437.         }
  438.         bytesdecompressed += i;
  439.         printf("\r%ld", bytesdecompressed);
  440.         return;
  441.       }
  442.  
  443.       /* get match position from input stream */
  444.       j = ((i - ReadBits(DICTBITS)) & (DICTSIZE - 1));
  445.  
  446.       if ((i + k) >= DICTSIZE)
  447.       {
  448.         do
  449.         {
  450.           dict[i++] = dict[j++];
  451.           j &= (DICTSIZE - 1);
  452.           if (i == DICTSIZE)
  453.           {
  454.             if (fwrite(&dict, sizeof (char), DICTSIZE, outfile) == EOF)
  455.             {
  456.               printf("\nerror writing to output file");
  457.               exit(EXIT_FAILURE);
  458.             }
  459.             i = 0;
  460.             bytesdecompressed += DICTSIZE;
  461.             printf("\r%ld", bytesdecompressed);
  462.           }
  463.         }
  464.         while (--k);
  465.       }
  466.       else
  467.       {
  468.         if ((j + k) >= DICTSIZE)
  469.         {
  470.           do
  471.           {
  472.             dict[i++] = dict[j++];
  473.             j &= (DICTSIZE - 1);
  474.           }
  475.           while (--k);
  476.         }
  477.         else
  478.         {
  479.           do
  480.           {
  481.             dict[i++] = dict[j++];
  482.           }
  483.           while (--k);
  484.         }
  485.       }
  486.     }
  487.   }
  488. }
  489.  
  490. int main(int argc, char *argv[])
  491. {
  492.   char *s;
  493.  
  494.   if (argc != 4)
  495.   {
  496.     printf("\n'prog2 e file1 file2' encodes file1 into file2.\n"
  497.              "'prog2 d file2 file1' decodes file2 into file1.\n");
  498.     return EXIT_FAILURE;
  499.   }
  500.   if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  501.    || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  502.    || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  503.     printf("??? %s\n", s);  return EXIT_FAILURE;
  504.   }
  505.  
  506.   /* allocate 4k I/O buffers */
  507.   setvbuf( infile, NULL, _IOFBF, 4096);
  508.   setvbuf( outfile, NULL, _IOFBF, 4096);
  509.  
  510.   if (toupper(*argv[1]) == 'E')
  511.   {
  512.     printf("Compressing %s to %s\n", argv[2], argv[3]);
  513.     Encode();
  514.   }
  515.   else
  516.   {
  517.     printf("Decompressing %s to %s\n", argv[2], argv[3]);
  518.     Decode();
  519.   }
  520.  
  521.   fclose(infile);  fclose(outfile);
  522.  
  523.   return EXIT_SUCCESS;
  524. }
  525.  
  526.