codrle3.c

著名压缩算法的实现

/* File: codrle3.c
   Author: David Bourgin
   Creation date: 1/2/94
   Last update: 24/7/95
   Purpose: Example of RLE type 3 encoding with a file source to compress.
*/

#include <stdio.h>
/* For routines printf,fputc,fread,fwrite and rewind */
#include <memory.h>
/* For routines memset,memcpy */
#include <stdlib.h>
/* For routine exit */

/* Error codes sent to the caller */
#define NO_ERROR      0
#define BAD_FILE_NAME 1
#define BAD_ARGUMENT  2

/* Useful constants */
#define FALSE 0
#define TRUE  1

#define MAX_FRAME_SIZE  256

/* Global variables */
FILE *source_file,*dest_file;

unsigned int index=0,
             buffer_read_size=0;
unsigned char buffer_read[3*256];

typedef struct { unsigned int array_size;
                 unsigned char *array_val;
               } t_tab;
#define ARRAY_SIZE(array)  ((array).array_size)
#define ARRAY_VAL(array)  ((array).array_val)
#define ARE_EQUAL(array1,array2)  ((ARRAY_SIZE(array1)==ARRAY_SIZE(array2))&&(!memcmp(ARRAY_VAL(array1),ARRAY_VAL(array2),ARRAY_SIZE(array1))))

/* Pseudo procedures */
#define size_remaining_to_read() (buffer_read_size-index)

#define read_block()  { if (!size_remaining_to_read())\
                           { buffer_read_size=fread(buffer_read,1,sizeof(buffer_read),source_file);\
                             index=0;\
                           }\
                      }
#define move_index(i)  (index=(i))
#define beginning_of_data()  { (void)rewind(source_file); buffer_read_size=0; index=0; }
#define end_of_data()  (size_remaining_to_read()?FALSE:(index=0,!(buffer_read_size=fread(buffer_read,1,sizeof(buffer_read),source_file))))
#define read_byte()  ((unsigned char)(end_of_data()?EOF:buffer_read[index++]))
#define read_array(array,nb_to_read)  { ARRAY_SIZE(array)=(nb_to_read);\
                                        ARRAY_VAL(array)= &(buffer_read[index]);\
                                        index += (nb_to_read);\
                                      }
#define write_byte(x)  ((void)fputc((unsigned char)(x),dest_file))
#define write_array(array)  ((void)fwrite(ARRAY_VAL(array),1,ARRAY_SIZE(array),dest_file))
#define fill_block()  { (void)memcpy(buffer_read,&(buffer_read[index]),size_remaining_to_read());\
                        buffer_read_size=fread(&(buffer_read[size_remaining_to_read()]),1,sizeof(buffer_read)-size_remaining_to_read(),source_file)+size_remaining_to_read();\
                        index=0;\
                      }

void rle3look_for_occurr(frame_nb,frame_size,
                         repetition_ok)
/* Returned parameters: 'frame_nb', 'frame_size' and 'repetition_ok' are modified
   Action: Looks in the byte buffer if there's a frame repetition
   where size and repetition are respectively in 'frame_size' and 'frame_nb'.
   Whenever a repetition is met, 'repetition_ok' returns 'TRUE' otherwise 'repetition_ok' returns 'FALSE'
   Errors: Whenever there are no multiple frames then 'frame_nb' won't be modified
   If there is a repetition such as (frame_nb-1)*frame_size>3 the buffer is
   completed so that it contains only one occurrence of the frame a its beginning.
   (The repetitions have been flushed by caliing 'fill_block').
*/
unsigned int *frame_nb,*frame_size;
int *repetition_ok;
{ int array_equality;
  t_tab array1,array2;

  *frame_size=1;
  *repetition_ok=FALSE;
  while ((*frame_size<=MAX_FRAME_SIZE)&&(size_remaining_to_read()>=(*frame_size << 1))&&(!*repetition_ok))
        { read_array(array1,*frame_size);
          read_array(array2,*frame_size);
          if (array_equality=ARE_EQUAL(array1,array2))
             { *frame_nb=2;
               while ((size_remaining_to_read()>=*frame_size)&&(*frame_nb<=255)&&(array_equality))
                     { if ((*frame_nb-1)*(*frame_size)>3)
                          { if (*repetition_ok)
                               move_index(*frame_size);
                            else { *repetition_ok=TRUE;
                                   move_index((*frame_nb-1)*(*frame_size));
                                 }
                            fill_block();
                            move_index(*frame_size);
                          }
                       read_array(array2,*frame_size);
                       if (array_equality=ARE_EQUAL(array1,array2))
                          (*frame_nb)++;
                     }
               if ((*frame_nb-1)*(*frame_size)>3)
                  { if (*repetition_ok)
                       { if (array_equality)
                            { move_index(*frame_size);
                              fill_block();
                            }
                       }
                    else { *repetition_ok=TRUE;
                           move_index((*frame_nb-1)*(*frame_size));
                           fill_block();
                         }
                    (*frame_size)--;
                  }
                             /* Specify to the caller there was a repetition */
             }
          (*frame_size)++;
          move_index(0);
        }
}

void rle3write_non_rep(header_byte,non_repeated_byte)
/* Returned parameters: None
   Action: Writes in the output compression stream the byte 'non_repeated_byte'
   'header_byte' is used as marker as defined in RLE 3 method
   Errors: An input/output error could disturb the running of the program
*/
unsigned char header_byte,non_repeated_byte;
{ if (non_repeated_byte==header_byte)
     { write_byte(header_byte);
       write_byte(0);
       write_byte(0);
     }
  else write_byte(non_repeated_byte);
}

void rle3write_rep(header_byte,frame,repetition)
/* Returned parameters: None
   Action: Writes in the output compression stream 'repetition' times 'frame' which size is given by 'frame_size'
   'header_byte' is used as marker as defined in RLE 3 method
   Errors: An input/output error could disturb the running of the program
*/
unsigned char header_byte;
t_tab frame;
unsigned int repetition;
{ write_byte(header_byte);
  write_byte(repetition-1);
  write_byte(ARRAY_SIZE(frame)-1);
  write_array(frame);
}

void rle3encoding()
/* Returned parameters: None
   Action: Compresses with RLE type 3 method all bytes read by the function 'read_byte'
   Errors: An input/output error could disturb the running of the program
*/
{ register unsigned int i;
  unsigned long int occurrence_table[256];
  unsigned char header_byte;
  t_tab frame;
  unsigned int frame_nb,frame_size;
  int repetition_valid;

  if (!end_of_data())        /* Is there at least a byte to analyze? */
     {                       /* Sets up the occurrence numbers of all bytes to 0 */
       (void)memset((char *)occurrence_table,0,sizeof(occurrence_table));
                             /* This is the same to fill 'occurrence_table' to 0.
                                It's fastest than to loop 256 times */
       while (!end_of_data())/* Valids the occurrences in 'occurrence_table' in regard to the data to compress */

             { header_byte=read_byte();
               occurrence_table[header_byte]++;
             }
       header_byte=0;
       for (i=1;i<=255;i++)
           if (occurrence_table[i]<occurrence_table[header_byte])
              header_byte=i;
       write_byte(header_byte);
       beginning_of_data();
       read_block();
       while (size_remaining_to_read())
             { rle3look_for_occurr(&frame_nb,&frame_size,&repetition_valid);
               if (repetition_valid)
                             /* Was there a repetition? */
                  { read_array(frame,frame_size);
                    rle3write_rep(header_byte,frame,frame_nb);
                  }
               else          /* No pattern repetition */
                    rle3write_non_rep(header_byte,read_byte());
               fill_block(); /* All new analysis must start at 0 in the buffer */
             }
     }
}

void help()
/* Returned parameters: None
   Action: Displays the help of the program and then stops its running
   Errors: None
*/
{ printf("This utility enables you to compress a file by using RLE type 3 method\n");
  printf("as given in 'La Video et Les Imprimantes sur PC'\n");
  printf("\nUse: codrle3 source target\n");
  printf("source: Name of the file to compress\n");
  printf("target: Name of the compressed file\n");
}

int main(argc,argv)
/* Returned parameters: Return an error code (0=None)
   Action: Main procedure
   Errors: Detected, handled and an error code is returned, if any
*/
int argc;
char *argv[];
{ if (argc!=3)
     { help();
       exit(BAD_ARGUMENT);
     }
  else if ((source_file=fopen(argv[1],"rb"))==NULL)
          { help();
            exit(BAD_FILE_NAME);
          }
       else if ((dest_file=fopen(argv[2],"wb"))==NULL)
               { help();
                 exit(BAD_FILE_NAME);
               }
            else { rle3encoding();
                   fclose(source_file);
                   fclose(dest_file);
                 }
  printf("Execution of codrle3 completed.\n");
  return (NO_ERROR);
}