sp_code.c

常用的无损压缩算法源代码

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */

/*               S + P   I M A G E   C O M P R E S S I O N             */

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */
/*     > > > > >    ANSI C version  2.05  -  05/30/95    < < < < <     */

/*   Amir Said - [e-mail]                            */
/*   Faculty of Electrical Engineering                                 */
/*   University of Campinas (UNICAMP) - Campinas, SP 13081, Brazil     */

/*   William A. Pearlman - [e-mail]                       */
/*   Dept. of Electrical, Computer, and Systems Engineering            */
/*   Rensselaer Polytechnic Institute - Troy, NY 12180, USA            */

/*     Copyright (c) 1995 Amir Said & William A. Pearlman              */

/*
   This program is Copyright (c) by Amir Said and William A. Pearlman.
   It may be freely redistributed in its entirety provided that this
   copyright notice is not removed. It may not be sold for profit or
   incorporated in commercial programs without the written permission
   of the copyright holders. This program is provided as is, without
   any express or implied warranty, without even the warranty of
   fitness for a particular purpose.
*/



/* - - Static variables  - - - - - - - - - - - - - - - - - - - - - - - */

char * r_msg = "cannot read PIC file";

char * w_msg = "cannot write to coded file";

Encoder code_file;


/* - - Function prototypes - - - - - - - - - - - - - - - - - - - - - - */

void Show_Usage(char *);

void Write_Header(Image_Coord, int, int, int, long);

int ** Read_Pic(Image_Coord, int, char *, long *);

void Transform(Image_Coord, int **, int *, int *);

void Code_Image(int, Image_Coord, int **);


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Main function - - - - - - - - - - - - - - - - - - - - - - - - - */

int main(int numb_arg, char ** arg)
{
  Image_Coord dim;
  int bytes, mean, levels, ** image, arg_dis = 0;
  long file_bytes, check_sum;
  double CPU_time;
  FILE * temp_file;

  if (numb_arg < 5) Show_Usage(arg[0]);
  
  if (arg[1][0] == '-') {
    if ((arg[1][1] == 's') || (arg[1][2] == 's')) smooth_image = 1;
    arg_dis = ((arg[1][1] == 'r') || (arg[1][2] == 'r') ? 2 : 1); }

  if (numb_arg != 5 + arg_dis) Show_Usage(arg[0]);
  arg += arg_dis;

  if ((temp_file = fopen(arg[4], "rb")) != NULL) {
    printf("Overwrite file %s? (y = yes, otherwise quit) ", arg[4]);
    fclose(temp_file);  gets(line);
    if (line[0] != 'y') exit(0); }

  CPU_time = (double) clock();
  dim.x = atoi(arg[1]);  bytes = atoi(arg[2]);
  dim.y = (arg_dis == 2 ? atoi(arg[0]) : dim.x);

  image = Read_Pic(dim, bytes, arg[3], &check_sum);

  Transform(dim, image, &levels, &mean);

  Start_Encoder(&code_file, arg[4]);

  Write_Header(dim, mean, levels, bytes, check_sum);

  Construct_Set_Table();

  Code_Image(levels, dim, image);

  file_bytes = Stop_Encoder(&code_file);

  printf("\n  Compressed file size = %ld bytes (%5.2f bpp).\n",
    file_bytes, 8.0 * file_bytes / (float) dim.x / (float) dim.y);
  printf("\n  CPU time = %6.2f s.\n", ((double) clock() - CPU_time) /
    (double) CLOCKS_PER_SEC);

  return 0;
}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* - - Implementations - - - - - - - - - - - - - - - - - - - - - - - - */

void Show_Usage(char * prog_name)
{
  printf("\nCorrect usage:\n\n%s [-option] hor_pels [vert_pels] "
    "bytes/pel PIC_file %s_file\n\n", prog_name, FILE_TYPE);
  puts("The valid options are:\n\n\t-s\t\tsmooth (usually medical) " 
    "image\n\t-r\t\trectangular image (default = square)\n"
    "\t-sr, -rs\tcombination of the options above\n");
  puts("The other parameters are:\n");
  puts("hor_pels:\tnumber of pixels per image line "
    "(images stored by lines)");
  puts("vert_pels:\tnumber of image lines, to be used only "
    "with option -r");
  puts("bytes/pel:\tnumber bytes per pixel, most significant "
    "byte first");
  puts("PIC_file:\tname of the file with pixel values (no header)");
  printf("%s_file:\tname of the file with compressed image\n\n",
    FILE_TYPE);
  exit(0);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Write_Header(Image_Coord d, int m, int l, int b, long c)
{
  int i;
  Write_Bits(&code_file, 8, KEY_1);
  Write_Bits(&code_file, 8, (smooth_image ? KEY_3 : KEY_2));
  Write_Bits(&code_file, 8, (d.x >> 2) & 0xFF);
  Write_Bits(&code_file, 6, d.x >> 10);
  Write_Bits(&code_file, 8, (d.y >>  2) & 0xFF);
  Write_Bits(&code_file, 6, d.y >> 10);
  Write_Bits(&code_file, 8, m & 0xFF);
  Write_Bits(&code_file, 8, m >> 8);
  Write_Bits(&code_file, 4, l);
  Write_Bits(&code_file, 1, b - 1);
  for (i = 0; i <= 2; i++) {
    Write_Bits(&code_file, 8, (int) c & 0xFF);
    c >>= 8; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

int ** Read_Pic(Image_Coord d, int bytes, char * file_name, long * check)
{
  int i, j, p, c, ** pic;
  long chk_sum = 0;
  FILE * pic_file = fopen(file_name, "rb");

  if (pic_file == NULL) Error(r_msg);

  if ((d.x < 16) || (d.y < 16) || (bytes < 1) || (bytes > 2))
    Error("Invalid image parameters");

  if ((d.x & 3) || (d.y & 3))
    Error("image dimensions must be a multiple of 4");

  if ((pic = (int **) malloc(d.x * sizeof(int *))) == NULL)
    Error(m_msg);

  for (i = 0; i < d.x; i++) {
    if ((pic[i] = (int *) malloc(d.y * sizeof(int))) == NULL)
      Error(m_msg);
    for (j = 0; j < d.y; j++) {
      if ((p = getc(pic_file)) == EOF) Error(r_msg);
      if (bytes == 2) {
        if ((c = getc(pic_file)) == EOF) Error(r_msg);
        p = (p << 8) | c; }
      pic[i][j] = p;
      chk_sum += p ^ (p >> 1);  chk_sum &= 0xFFFFFFL; } }

  if (getc(pic_file) != EOF)
    Error("PIC file is larger than specified dimension");

  fclose(pic_file);

  p = 1 + (d.x > d.y ? d.x : d.y);
  for (i = 0; i <= 1; i++)
    if ((buffer[i] = (int *) malloc(p * sizeof(int))) == NULL)
      Error(m_msg);

  *check = chk_sum;  return pic;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

int Max_Levels(int n)
{
  int l1, l2;
  for (l1 = 0; !(n & 1); l1++) n >>= 1;
  for (l2 = l1 - 4; n > 0; l2++) n >>= 1;
  return (l1 < l2 ? l1 : l2);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void SP_Transform(int m, int n, int c[], int l[], int h[])
{
  int i, k, d1, d2, d3, mm = m - 1;

  for (i = k = 0; k < n; i++, k += 2) {
    l[i] = (c[k] + c[k+1]) >> 1;
    h[i] =  c[k] - c[k+1]; }

  h[0] -= (d2 = l[0] - l[1]) >> 2;
  if (smooth_image) {
    d3 = l[1] - l[2];  h[1] -= (((d2 + d3 - h[2]) << 1) + d3 + 3) >> 3;
    for (i = 2; i < mm; i++) {
      d1 = d2;  d2 = d3;  d3 = l[i] - l[i+1];
      h[i] -= ((d3 << 3) + (d2 << 2) - d1 - 6 * h[i+1] + 7) >> 4; }
    h[i] -= d3 >> 2; }
  else {
    for (i = 1; i < mm; i++) {
      d1 = d2;  d2 = l[i] - l[i+1];
      h[i] -= (((d1 + d2 - h[i+1]) << 1) + d2 + 3) >> 3; }
    h[i] -= d2 >> 2; }
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

void Transform(Image_Coord d, int ** cf, int * lvs, int * mean)
{
  int lv, levels, i, j, nx, ny, mx = d.x, my = d.y;
  int * in_line = buffer[0], * out_line = buffer[1];
  long sum;

  i = Max_Levels(d.x);  j = Max_Levels(d.y);
  *lvs = levels = (i < j ? i : j);

  for (lv = 0; lv < levels; lv++) {

    nx = mx;  mx >>= 1;  ny = my;  my >>= 1;

    for (j = 0; j < ny; j++) {
      for (i = 0; i < nx; i++) in_line[i] = cf[i][j];
      SP_Transform(mx, nx, in_line, out_line, out_line + mx);
      for (i = 0; i < nx; i++) cf[i][j] = out_line[i]; }

    for (i = 0; i < nx; i++) {
      memcpy(in_line, cf[i], ny * sizeof(int));
      SP_Transform(my, ny, in_line, cf[i], cf[i] + my); } }

  for (sum = i = 0; i < mx; i++)
    for (j = 0; j < my; j++) sum += cf[i][j];

  *mean = (int) (0.5 + (((float) sum) / mx) / my);

  for (i = 0; i < mx; i++)
    for (j = 0; j < my; j++) cf[i][j] -= *mean;
}

/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */

/* end of file < sp_code.c > */