Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: Fin--fin.c
发信站: 哈工大紫丁香 (Sun Sep  3 16:03:15 2000), 转信


#include <stdio.h>
#include <string.h>

// table with predictions
char pcTable[32768U];

// macro to calculate index in pctable from previous 2 characters
#define INDEX(p1,p2) (((unsigned)(unsigned char)p1<<7)^(unsigned char)p2)

void Compress (FILE *pfIn, FILE *pfOut){
   int c;                // character
   int i;                // loop counter
   char p1=0, p2=0;      // previous 2 characters
   char buf[8];          // keeps characters temporarily
   int ctr=0;            // number of characters in mask
   int bctr=0;           // position in buf
   unsigned char mask=0; // mask to mark successful predictions

   memset (pcTable, 32, 32768U); // space (ASCII 32) is the most used char

   c = fgetc (pfIn);
   while (c!=EOF){
      // try to predict the next character
      if (pcTable[INDEX(p1,p2)]==(char)c){
         // correct prediction, mark bit for correct prediction
         mask = mask ^ (1<<ctr);
      } else {
         // wrong prediction, but next time ...
         pcTable[INDEX(p1,p2)]=(char)c;

         // buf keeps character temporarily in buffer
         buf[bctr++] = (char)c;
      }

      // test if mask is full (8 characters read)
      if (++ctr==8){
         // write mask
         fputc ((char)mask, pfOut);

         // write kept characters
         for (i=0;i<bctr;i++)
            fputc (buf[i], pfOut);

         // reset variables
         ctr=0;
         bctr=0;
         mask=0;
      }

      // shift characters
      p1 = p2; p2 = (char)c;

      c = fgetc (pfIn);
   }

   // EOF, but there might be some left for output
   if (ctr){
      // write mask
      fputc ((char)mask, pfOut);

      // write kept characters
      for (i=0;i<bctr;i++)
         fputc (buf[i], pfOut);
   }
}

void Decompress (FILE *pfin, FILE *pfout){
   int ci,co;            // characters (in and out)
   char p1=0, p2=0;      // previous 2 characters
   int ctr=8;            // number of characters processed for this mask
   unsigned char mask=0; // mask to mark successful predictions

   memset (pcTable, 32, 32768U); // space (ASCII 32) is the most used char

   ci = fgetc (pfin);
   while (ci!=EOF){
      // get mask (for 8 characters)
      mask = (unsigned char)(char)ci;

      // for each bit in the mask
      for (ctr=0; ctr<8; ctr++){
         if (mask & (1<<ctr)){
            // predicted character
            co = pcTable[INDEX(p1,p2)];
         } else {
            // not predicted character
            co = fgetc (pfin);
            if (co==EOF) return; // decompression completed !
     pcTable[INDEX(p1,p2)] = (char)co;
         }
         fputc (co, pfout);
         p1 = p2; p2 = co;
      }
      ci = fgetc (pfin);
   }
}

/* test program by compressing and decompressing a file */
void main (){
   FILE *a = fopen ("in","rb");
   FILE *b = fopen ("out","wb");
   Compress (a,b);
   fclose (a);
   fclose (b);

   a = fopen ("out","rb");
   b = fopen ("rin","wb");
   Decompress (a, b);
   fclose (a);
   fclose (b);
}


--
          ┌─                           ─┐
             Every problem has a solution.
          └─                           ─┘

infosite@263.net
http://infosite.topcool.net
※ 修改:．haojs 于 Sep  3 16:00:47 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
※ 修改:·lofe 於 09月03日16:07:46 修改本文·[FROM: 202.118.226.15]