codrle4.c

著名压缩算法的实现

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

#include <stdio.h>
/* For routines printf,fputc,fread and fwrite */
#include <memory.h>
/* For routine 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 65

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

unsigned int index=0,
             buffer_read_size=0;
unsigned char buffer_read[8224+2*65];

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 load_block()  { buffer_read_size=fread(buffer_read,1,sizeof(buffer_read),source_file); index=0; }
#define move_index(i)  (index=(i))
#define size_remaining_to_read()  (buffer_read_size-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_word(x)  { write_byte((x) >> 8); write_byte((x) & 0xFF); }
#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 rle4look_for_occurr(basic_index,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 from 'basic_index' position
   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
*/
unsigned int basic_index,*frame_nb,*frame_size;
int *repetition_ok;
{ int array_equality;
  t_tab array1,array2;

  *frame_size=1;
  *repetition_ok=FALSE;
  move_index(basic_index);
  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<16449)&&(*frame_size==1))||((*frame_nb<257)&&(*frame_size>1)))
                      &&(array_equality))
                     { if ((*frame_size>2)||(*frame_nb>2))
                          { if (*repetition_ok)
                               move_index(*frame_size);
                            else { *repetition_ok=TRUE;
                                   if (basic_index)
                                      return;
                                   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_size>2)||(*frame_nb>2))
                  { if (basic_index)
                       { *repetition_ok=TRUE;
                         return;
                       }
                    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)--;
                  }
                             /* Specifies to the caller there was a repetition */
             }
          (*frame_size)++;
          move_index(basic_index);
        }
}

void rle4encoding()
/* Returned parameters: None
   Action: Compresses with RLE type 4 method all bytes read by the function read_byte
   Errors: An input/output error could disturb the running of the program
*/
{ t_tab frame;
  unsigned int frame_nb1,frame_size1,frame_nb2,frame_size2;
  int repetition_valid;

  load_block();
  while (size_remaining_to_read())
        { rle4look_for_occurr(0,&frame_nb1,&frame_size1,&repetition_valid);
          if (repetition_valid)
                             /* Was there a repetition? */
             { if (frame_size1==1)
                             /* Frame of 1 byte? */
                  { if (frame_nb1<66)
                             /* Frame with a byte but less than 66 times? */
                       write_byte(frame_nb1-2);
                    else write_word(frame_nb1+16318);
                  }
               else {        /* Frame with several bytes */
                      write_byte(frame_size1+126);
                      write_byte(frame_nb1-2);
                    }
             }
          else { frame_size1=0;
                 do {        /* Tests until where there's no repetition */
                      frame_size1++;
                      rle4look_for_occurr(frame_size1,&frame_nb2,&frame_size2,&repetition_valid);
                    }
                 while ((size_remaining_to_read())&&(frame_size1<8224)&&(!repetition_valid));
                 if (frame_size1<33)
                             /* Non repetition of a frame with less than 33 Bytes */
                    write_byte(frame_size1+191);
                 else write_word(frame_size1+57311);
               }
          move_index(0);
          read_array(frame,frame_size1);
          write_array(frame);
          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 4 method\n");
  printf("as given in 'La Video et Les Imprimantes sur PC'\n");
  printf("\nUse: codrle4 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: Returns 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 { rle4encoding();
                   fclose(source_file);
                   fclose(dest_file);
                 }
  printf("Execution of codrle4 completed.\n");
  return (NO_ERROR);
}