compress.cpp

dll压缩算法

    /* collect leaf nodes in the first half of the table */
    /* and replace the freq by (freq + 1) / 2. */
    j = 0;
    for (i = 0; i < T; i++) {
        if (son[i] >= T) {
            freq[j] = (freq[i] + 1) / 2;
            son[j] = son[i];
            j++;
        }
    }
    /* begin constructing tree by connecting sons */
    for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
        k = i + 1;
        f = freq[j] = freq[i] + freq[k];
        for (k = j - 1; f < freq[k]; k--);
        k++;
        l = (j - k) * 2;
        memmove(&freq[k + 1], &freq[k], l);
        freq[k] = f;
        memmove(&son[k + 1], &son[k], l);
        son[k] = i;
    }
    /* connect prnt */
    for (i = 0; i < T; i++) {
        if ((k = son[i]) >= T) {
            prnt[k] = i;
        } else {
            prnt[k] = prnt[k + 1] = i;
        }
    }
}


/* increment frequency of given code by one, and update tree */

static void update(int c)
{
    int i, j, k, l;

    if (freq[R] == MAX_FREQ) {
        reconst();
    }
    c = prnt[c + T];
    do {
        k = ++freq[c];

        /* if the order is disturbed, exchange nodes */
        if ((unsigned)k > freq[l = c + 1]) {
            while ((unsigned)k > freq[++l]);
            l--;
            freq[c] = freq[l];
            freq[l] = k;

            i = son[c];
            prnt[i] = l;
            if (i < T) prnt[i + 1] = l;

            j = son[l];
            son[l] = i;

            prnt[j] = c;
            if (j < T) prnt[j + 1] = c;
            son[c] = j;

            c = l;
        }
    } while ((c = prnt[c]) != 0); /* repeat up to root */
}

unsigned code, len;

static void EncodeChar(unsigned c)
{
    unsigned i;
    int j, k;

    i = 0;
    j = 0;
    k = prnt[c + T];

    /* travel from leaf to root */
    do {
        i >>= 1;

        /* if node's address is odd-numbered, choose bigger brother node */
        if (k & 1) i += 0x8000;

        j++;
    } while ((k = prnt[k]) != R);
    Putcode(j, i);
    code = i;
    len = j;
    update(c);
}

static void EncodePosition(unsigned c)
{
    unsigned i;

    /* output upper 6 bits by table lookup */
    i = c >> 6;
    Putcode(p_len[i], (unsigned)p_code[i] << 8);

    /* output lower 6 bits verbatim */
    Putcode(6, (c & 0x3f) << 10);
}

static void EncodeEnd(void)
{
    if (putlen) {
        if (putc(putbuf >> 8, outfile) == EOF) {
            Error(wterr);
        }
        codesize++;
    }
}

static int DecodeChar(void)
{
    unsigned c;

    c = son[R];

    /* travel from root to leaf, */
    /* choosing the smaller child node (son[]) if the read bit is 0, */
    /* the bigger (son[]+1} if 1 */
    while (c < T) {
        c += GetBit();
        c = son[c];
    }
    c -= T;
    update(c);
    return (int)c;
}

static int DecodePosition(void)
{
    unsigned i, j, c;

    /* recover upper 6 bits from table */
    i = GetByte();
    c = (unsigned)d_code[i] << 6;
    j = d_len[i];

    /* read lower 6 bits verbatim */
    j -= 2;
    while (j--) {
        i = (i << 1) + GetBit();
    }
    return (int)(c | (i & 0x3f));
}

/* compression */

int encode(char *file1,char *file2)  /* compression */
{
    int  i, c, len, r, s, last_match_length,temp;
    char extname[16]="";

    /*将压缩文件名存入字符串file2中，并将文件扩展名存入压缩文件*/
    if ((infile = fopen(file1, "rb")) == NULL)
       return -1;
    for(i=(strlen(file1)-1);i>=0;i--)
        if(file1[i] == '.')
         {
         	temp=i;
         	i=-1;
         };
    for(i=temp+1;i<int(strlen(file1));i++)
       extname[i-temp-1]=file1[i];
    
  //  strncpy(file2,file1,temp);
  //  strcat(file2,".hjh");
    
    if ((outfile = fopen(file2, "wb")) == NULL)
       return -1;
    i=strlen(extname);
    while(i<16)           
    {
    	extname[i]='*';
    	i++;
    }
    fwrite(extname,16,1,outfile);
    
    /*开始文件压缩*/
    fseek(infile, 0L, 2);
    textsize = ftell(infile);
    fputc((int)((textsize & 0xff)),outfile);
    fputc((int)((textsize & 0xff00) >> 8),outfile);
    fputc((int)((textsize & 0xff0000L) >> 16),outfile);
    fputc((int)((textsize & 0xff000000L) >> 24),outfile);
    if (ferror(outfile))
        Error(wterr);   /* output size of text */
    if (textsize == 0)
        return -1;
    rewind(infile);
    textsize = 0;           /* rewind and re-read */
    StartHuff();
    InitTree();
    s = 0;
    r = N - F;
    for (i = s; i < r; i++)
        text_buf[i] = 0x20;
    for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
        text_buf[r + len] = (unsigned char)c;
    textsize = len;
    for (i = 1; i <= F; i++)
        InsertNode(r - i);
    InsertNode(r);
    do {
        if (match_length > len)
            match_length = len;
        if (match_length <= THRESHOLD) {
            match_length = 1;
            EncodeChar(text_buf[r]);
        } else {
            EncodeChar(255 - THRESHOLD + match_length);
            EncodePosition(match_position);
        }
        last_match_length = match_length;
        for (i = 0; i < last_match_length &&
                (c = getc(infile)) != EOF; i++) {
            DeleteNode(s);
            text_buf[s] = (unsigned char)c;
            if (s < F - 1)
                text_buf[s + N] = (unsigned char)c;
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            InsertNode(r);
        }
        if ((textsize += i) > printcount) {
     //       printf("%12ld\r", textsize);
            printcount += 1024;
        }
        while (i++ < last_match_length) {
            DeleteNode(s);
            s = (s + 1) & (N - 1);
            r = (r + 1) & (N - 1);
            if (--len) InsertNode(r);
        }
    } while (len > 0);
    EncodeEnd();
    
    fclose(infile);
    fclose(outfile);
    return 0;
    /*以下为显示加解压结果的代码，实际运用时应删去。*/
   // printf("Input file length : %ld bytes\n", textsize);
    //printf("Output file length : %ld bytes\n", codesize);
   // printf("Out/In(Encode) : %.5f\n", 1.0 * codesize / textsize);
}

int decode(char *file1,char *file2)  /* recover */
{
    int  i, j, k, r, c;
    unsigned long int  count,temp;    
    char tempc[16]="";

    if ((infile = fopen(file1, "rb")) == NULL)
       return -1;
    for(i=0;i<(int(strlen(file1)));i++)
    {
    	if(file1[i] == '.') break;
    	file2[i]=file1[i];
    }

   /*将压缩文件的原扩展名读出来并构造好原文件名*/
	file2[i] = '.';
	i++;
    fread(tempc,16,1,infile);
    for(j=0;j<16;j++,i++)
      if (tempc[j] != '*')
           file2[i]=tempc[j];
	file2[i] = '\0';
    if ((outfile = fopen(file2, "wb")) == NULL)
       return -1;
   
    /*开始解压缩*/
    textsize = (fgetc(infile));
    temp=textsize;
    textsize |= ((unsigned long)fgetc(infile) << 8);
    textsize |= ((unsigned long)fgetc(infile) << 16);
    textsize |= ((unsigned long)fgetc(infile) << 24);
    if (ferror(infile))
        Error("Can't read");  /* read size of text */
    if (textsize == 0)
        return -1;
    StartHuff();
	getlen = 0;
    for (i = 0; i < N - F; i++)
        text_buf[i] = 0x20;
    r = N - F;
    for (count = 0; count < textsize; ) {
        c = DecodeChar();
        if (c < 256) {
            if (putc(c, outfile) == EOF) {
                Error(wterr);
            }
            text_buf[r++] = (unsigned char)c;
            r &= (N - 1);
            count++;
        } else {
            i = (r - DecodePosition() - 1) & (N - 1);
            j = c - 255 + THRESHOLD;
            for (k = 0; k < j; k++) {
                c = text_buf[(i + k) & (N - 1)];
                if (putc(c, outfile) == EOF) {
                    Error(wterr);
                }
                text_buf[r++] = (unsigned char)c;
                r &= (N - 1);
                count++;
            }
        }
        if (count > printcount) {
      //      printf("%12ld\r", count);
            printcount += 1024;
        }
    }
    
    fclose(infile);
    fclose(outfile);
    return 0;
    /*以下为显示加解压结果的代码，实际运用时应删去。*/
   // printf("Output file length :%12ld bytes\n", count);
}