decode.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

    min_bits = 2;     /* minimum length black code word   */
    max_bits = 13;    /* maximum length black code word   */
  }
  else  /* WHITE_PIXEL wanted */
  {
    color = WHITE_WANTED;
    min_bits = 4;     /* minimum length white code word   */
    max_bits = 9;     /* maximum length white code word   */
  }

  for ( ; ; )         /* until code word found or error   */
  {
    do
    {
      /* because a do..while loop has the test at the end */
      /* it always executes at least once so on each pass */
      /* the GetNextBit() function will always be called  */
      /* even if the length of the code word under        */
      /* construction is greater than the minimum value   */
      if ((next_bit = GetNextBit(fin)) == T4_EOF)
      {
        return T4_EOF;
      }
      else
      {
        code_word = (code_word << 1) | next_bit;
      }
    } while (++bits < min_bits);

    /*  check for EOL once code word is long enough */
    if (bits >= EOL_LENGTH && code_word == 1)
    {
      return T4_EOL;
    }

    /* if already past maximum bit length and not   */
    /* EOL must be all zero bits on the way to EOL  */
    if (bits > max_bits)
    {
      if (code_word != 0)
      {
        return T4_INVALID;
      }
    }
    else if (NULL != (t4p =
      code_table[bits - 2][color].token))
    /* this condition has to be in an else if clause to the */
    /* one above it because if bits > max_bits the access   */
    /* to the code_table array will be beyond the end of    */
    /* array causing undefined behavior                     */
    {
      t4p = bsearch(&code_word, t4p,
            code_table[bits - 2][color].search_length,
            sizeof *t4p, T4Compare);

      if (NULL != t4p)
      {
        pixel_run = t4p->run_length;
        /* here the packing of make-up codes into unsigned  */
        /* chars is undone and the run length expanded back */
        /* to its full value                                */
        if (pixel_run & 0x80)
        {
          pixel_run &= ~0x80;
          pixel_run <<= 6;
        }
        return pixel_run;
      }
    }
  }
}

/* Function:    DecodePage
 *
 * Remarks:     only referenced from inside this source
 *              file so defined with the static keyword
 *              for internal linkage
 *
 * Inputs:      FILE *fin, pointer to the source file
 *              of the T.4 encoded image beind decoded
 *
 *              FILE *fout, pointer to destination file
 *              for the decoded binary image
 *
 *              unsigned char *buff, pointer to an array of
 *              at least OCTETS_PER_ROW bytes to store a
 *              full scan row of decoded pixels
 *
 * Returns:     int:
 *                0 through MAXIMUM_ROWS indicating the
 *                number of binary pixel scan lines written
 *                to the output file if no errors occurred,
 *                the standard macro EOF if any errors
 *                do occur
 *
 * Description: this function is used to extract T.4 code
 *              representing an encoded page image,
 *              consisting of 1,728 pixels per scan line
 *              and up to MAXIMUM_ROWS scan lines per
 *              page
 */
int
DecodePage(FILE *fin,
           FILE *fout,
           unsigned char * const buff)
{
  PIXEL_WANTED wanted;    /* color currently sought       */
  int pixel_run;          /* length of current color run  */
  int eop_count = 0;      /* use to recognize end of page */
  int fax_lines;          /* count of lines decoded       */
  int pixel_count;        /* total pixels in current line */
  int total_run;          /* total pixels in current run  */
  unsigned char *out_ptr; /* pointer into output buffer   */

  /* first code word in the file must be an EOL */
  pixel_run = GetPixelRun(WHITE_WANTED, fin);
  if (pixel_run != T4_EOL)
  {
    puts("missing initial EOL");
    return EOF;
  }

  /* read, decode, and output encoded scan lines one-by-one */
  for (fax_lines = 0; fax_lines < MAXIMUM_ROWS; )
  {
    wanted = WHITE_WANTED;  /* lines start with white runs  */
    out_ptr = buff;         /* output starts at beginning   */
    pixel_count = 0;        /* have no pixels in new line   */

    do
    {
      pixel_run = GetPixelRun(wanted, fin);
      if (pixel_run >= 0)
      {
        eop_count = 0;      /* pixel runs since last EOL    */
        if ((total_run = pixel_run) > 63)
        {
          /* if the pixel run just decodes is greater than  */
          /* 63, it is a make-up code and they are always   */
          /* followed by a terminating code for the same    */
          /* color, so call GetPixelRun again with the same */
          /* color to get the total run length              */
          pixel_run = GetPixelRun(wanted, fin);
          if (pixel_run >= 0)
          {
            total_run += pixel_run;
          }
          else
          {
            puts("decode: make-up code missing");
            return EOF;
          }
        }

        /* before inserting the new run of pixels into the  */
        /* output buffer, check to make sure that it will   */
        /* not exceed the proper number of pixels per row   */
        /* as this could cause writing past the end of the  */
        /* memory space belonging to the buffer, causing    */
        /* undefined behavior                               */
        if ((pixel_count += total_run) > PIXELS_PER_ROW)
        {
          puts("decode: line too long");
          return EOF;
        }
        else
        {
          /* the new run of pixels will fit in the buffer   */
          /* so insert it                                   */
          out_ptr = OutputPixels(total_run, wanted, out_ptr);
          /* since white and black pixel runs alternate we  */
          /* now want to look for the opposite color of the */
          /* last run                                       */
          if (wanted == WHITE_WANTED)
          {
            wanted = BLACK_WANTED;
          }
          else
          {
            wanted = WHITE_WANTED;
          }
        }
      }
    } while (pixel_run >= 0);

    /* a value which does not represent a pixel run has     */
    /* been returned by GetPixelRun(), decided what to do   */
    /* next based on its exact value                        */
    switch (pixel_run)
    {
      case T4_EOF:
        puts("decode: unexpected end of file");
        return EOF;
      case T4_EOL:
        /* there are two correct circumstances for finding  */
        /* an EOL code word, the first after decoding the   */
        /* code words for exactly the 1728 pixels...        */
        if (PIXELS_PER_ROW == pixel_count)
        {
          ++fax_lines;
          fwrite(buff, 1, OCTETS_PER_ROW, fout);
          ++eop_count;
        }
        /* ...and the second is after decoding 0 pixels     */
        /* after the preceeding EOL code, since six         */
        /* consecutive EOL codes in a row with no pixels at */
        /* all in between signal the end of the page        */
        else if (0 == pixel_count)
        {
          if (++eop_count >= 6)
          {
            return fax_lines;
          }
        }
        /* if an EOL code word is found after some number   */
        /* of pixels less than 1,728 it is an error         */
        else
        {
          puts("decode: invalid line length");
          return EOF;
        }
        break;
      case T4_INVALID:
        /* if GetPixelRun() detected a pattern of bits that */
        /* don't correspond to any T.4 code word...         */
        puts("decode: invalid t.4 code");
        return EOF;
      default:
        /* for safety sake there is a default case...       */
        puts("decode: program error");
        return EOF;
    }
  }

  return fax_lines;
}

/* Function:    main
 *
 * Inputs:      int argc, specifying number of command line
 *              arguments
 *
 *              char **argv, a pointer to an array of
 *              pointers to strings containing the contents
 *              of the command line arguments
 *
 *              argv[1] must represent the name of an
 *              existing file that can be opened by the
 *              program containing a valid T.4 encoding
 *              of a fax page image
 *
 *              argv[2] must represent a name that the
 *              program can create to contain the decoded
 *              binary image pixels of the page
 *
 * Returns:     int:
 *                EXIT_SUCCESS defined in <stdlib.h> if
 *                appropriate command line arguments are
 *                received and a T.4 encoded input file
 *                is successfully translated to a binary
 *                image output file
 *
 *                EXIT_FAILURE defined in <stdlib.h> if
 *                the command line arguments are incorrect,
 *                or if any error occurs
 *
 * Description: this is the main entry point for the decode
 *              program
 *
 *              it verifies the command line arguments,
 *              opens the source and destination files,
 *              and defines an array of unsigned char to
 *              hold the binary output as each line is
 *              row of pixels is being built
 */
int
main(int argc, char **argv)
{
  int line_count;
  FILE *ifile, *ofile;
  unsigned char obuff[OCTETS_PER_ROW];

  /* check command line arguments and open files  */
  if (argc < 3)
  {
    puts("usage: decode t4-input-file, binary-output-file");
    return EXIT_FAILURE;
  }
  else if ((ifile = fopen(argv[1], "rb")) == NULL)
  {
    printf("decode: can't open %s\n", argv[1]);
    return EXIT_FAILURE;
  }
  else if ((ofile = fopen(argv[2], "wb")) == NULL)
  {
    printf("decode: can't make %s\n", argv[2]);
    fclose(ifile);
    return EXIT_FAILURE;
  }

  line_count = DecodePage(ifile, ofile, obuff);

  if (line_count >= 0)
  {
    printf("decode: %d lines converted\n", line_count);
  }

  fclose(ifile);
  fclose(ofile);
  return EXIT_SUCCESS;
}