decode.c

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

 *
 * since the range of white code word lengths is only
 * 4 through 9 inclusive, the entries corresponding
 * to white code word lengths 2 and 3, and 10 through
 * 13, contain a null pointer and a search_length
 * parameter of 0
 */

static const CODE_TABLE code_table[12][2] =
{
  {
    { t4_black_02, sizeof t4_black_02/sizeof *t4_black_02 },
    { NULL       , 0                                      }
  },

  {
    { t4_black_03, sizeof t4_black_03/sizeof *t4_black_03 },
    { NULL       , 0                                      }
  },

  {
    { t4_black_04, sizeof t4_black_03/sizeof *t4_black_03 },
    { t4_white_04, sizeof t4_white_04/sizeof *t4_white_04 }
  },

  {
    { t4_black_05, sizeof t4_black_05/sizeof *t4_black_05 },
    { t4_white_05, sizeof t4_white_05/sizeof *t4_white_05 }
  },

  {
    { t4_black_06, sizeof t4_black_06/sizeof *t4_black_06 },
    { t4_white_06, sizeof t4_white_06/sizeof *t4_white_06 }
  },

  {
    { t4_black_07, sizeof t4_black_07/sizeof *t4_black_07 },
    { t4_white_07, sizeof t4_white_07/sizeof *t4_white_07 }
  },

  {
    { t4_black_08, sizeof t4_black_08/sizeof *t4_black_08 },
    { t4_white_08, sizeof t4_white_08/sizeof *t4_white_08 }
  },

  {
    { t4_black_09, sizeof t4_black_09/sizeof *t4_black_09 },
    { t4_white_09, sizeof t4_white_09/sizeof *t4_white_09 }
  },

  {
    { t4_black_10, sizeof t4_black_10/sizeof *t4_black_10 },
    { NULL       , 0                                      }
  },

  {
    { t4_black_11, sizeof t4_black_11/sizeof *t4_black_11 },
    { NULL       , 0                                      }
  },

  {
    { t4_black_12, sizeof t4_black_12/sizeof *t4_black_12 },
    { NULL       , 0                                      }
  },

  {
    { t4_black_13, sizeof t4_black_13/sizeof *t4_black_13 },
    { NULL       , 0                                      }
  }
};

/* the PIXEL_WANTED enumeration is passed to the code
 * word search and pixel output routines to specify the
 * current pixel color
 */
typedef enum
{
  BLACK_WANTED,
  WHITE_WANTED
} PIXEL_WANTED;

/* the T4_RESULTS enumeration is used to define special
 * return codes for the GetPixelRun() function
 *
 * all special return values are negative numbers, as 0
 * and positive values returned from this function represent
 * pixel runs
 */
typedef enum
{
  T4_EOF          = -1, /* end of input file encountered  */
  T4_EOL          = -2, /* end of line code word found    */
  T4_INVALID      = -3  /* invalid T.4 valid code word    */
} T4_RESULTS;

/* Function:    T4Compare
 *
 * Remarks:     only referenced from inside this source
 *              file so defined with the static keyword
 *              for internal linkage
 *
 * Inputs:      const void *x, an alias for a pointer
 *              to an unsigned int containing the numeric
 *              value of the code word under construction
 *
 *              const void *y, an alias for a pointer to
 *              a T4_DECODE structure
 *
 * Returns:     1 if the code word is greater numerically
 *              than the bit_pattern member of the
 *              T4_DECODE structure, -1 if the code word
 *              is less numerically, and 0 if the code word
 *              and the bit_pattern member of the T4_DECODE
 *              structure are numerically equal
 *
 * Description: this function is designed to be passed as
 *              the comparison function pointer argument to
 *              the standard library function bsearch
 *              prototyped in <stdlib.h>
 *
 * Note:        since both the int and the bit_pattern
 *              structure member are unsigned types, they
 *              are cast to signed ints prior to the
 *              subtraction that generates the return
 *              value
 *
 *              this cast is safe even if the value of
 *              UCHAR_MAX is greater than that of INT_MAX
 *              on an implementation because we know that
 *              the maximum values ever held in the unsigned
 *              types will never be greater than 255, well
 *              within the range of INT_MAX
 *
 *              if this cast were not possible at least two
 *              comparisons between the unsigned values
 *              would need to be made to determine the
 *              functions return value because subtraction
 *              of two unsigned integral types can never
 *              yield a negative result
 */
static int T4Compare(const void *x, const void *y)
{
  return *(int *)x - (int)((T4_DECODE *)y)->bit_pattern;
}

/* Function:    OutputPixels
 *
 * Remarks:     only referenced from inside this source
 *              file so defined with the static keyword
 *              for internal linkage
 *
 * Inputs:      int length, the number of pixels to insert
 *              into the output buffer
 *
 *              PIXEL_WANTED specifying the color of pixels
 *              to be inserted
 *
 *              unsigned char *out_ptr, where octets
 *              containing the generated image bits are
 *              to be stored
 *
 * Returns:     pointer to unsigned char where the next
 *              octet to be generated will be stored
 *
 * Description: this function is used to build the binary
 *              output image of arbitrary length sequences
 *              of white and black pixels
 *
 * Note:        this function does absolutely nothing, and
 *              returns the out_ptr value unchanged, if
 *              called with a length of 0 for either color
 *              pixel so no special test for terminating
 *              code words of 0 length is required by the
 *              caller
 */
static unsigned char
*OutputPixels(int length,
              PIXEL_WANTED wanted,
              unsigned char *out_ptr)
{
  unsigned int mask;
  static int outbits_left = PIXELS_PER_OCTET;
  static unsigned int pixel_out = 0;

  if (BLACK_WANTED == wanted)
  {
    mask = 0;
  }
  else
  {
    mask = 0xff;
  }

  while (length >= outbits_left)
  {
    pixel_out <<= outbits_left;
    *out_ptr++ = (unsigned char)(pixel_out
      | (mask >> (PIXELS_PER_OCTET - outbits_left)));
    pixel_out = 0;
    length -= outbits_left;
    outbits_left = PIXELS_PER_OCTET;
  }

  if (length)
  {
    pixel_out <<= length;
    pixel_out |=
      mask >> (PIXELS_PER_OCTET - length);
    outbits_left -= length;
  }

  return out_ptr;
}

/* Function:    GetNextBit
 *
 * 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
 *
 * Returns:     int:
 *                0 if the next bit from the source file
 *                is 0, 1 if the next bit is 1, EOF if
 *                end of file or error is encountered
 *                reading from fin
 *
 * Description: this function is used to extract bits one
 *              time from the input file
 *
 * Note:        the required left-to-right reversal is
 *              performed by this function
 */
static int
GetNextBit(FILE *fin)
{
  static int bits_used = PIXELS_PER_OCTET;
  static unsigned int t4_in;
  int input;

  /* see if there are bits remaining in the current octet */
  if (bits_used >= PIXELS_PER_OCTET)
  {
    /* none left, get a new octet from the source file    */
    if ((input = fgetc(fin)) == EOF)
    {
      return T4_EOF;
    }
    else
    {
      /* have new octet, mask to 8 least significant bits */
      t4_in = input & OCTET_MASK;
      /* haven't use any bits from this octet yet         */
      bits_used = 0;
    }
  }
  else
  {
    /* more bits in current octet, shift the last one     */
    /* off the right end and bring the next one to bit 0  */
    t4_in >>= 1;
  }

  ++bits_used;                  /* using a bit, count it  */
  return t4_in & 1;             /* return bit 0 of octet  */
}

/* Function:    GetPixelRun
 *
 * Remarks:     only referenced from inside this source
 *              file so defined with the static keyword
 *              for internal linkage
 *
 * Inputs:      PIXEL_WANTED wanted to specify the color,
 *              black or white, to be searched for
 *
 *              FILE *fin, pointer to the source file
 *              of the T.4 encoded image beind decoded
 *
 * Returns:     int:
 *                0 through 1728 representing the length
 *                of the run of pixels of the specified
 *                color, if found, or one of the special
 *                codes from the T4_RESULTS enumeration:
 *
 *                T4_EOF if GetNextPixel encounters an
 *                error or the end of the input file
 *
 *                T4_EOL if the end of line code word is
 *                found instead of a code word for a pixel
 *                run of the specified color
 *
 *                T4_INVALID if the sequence of bits
 *                retrieved from the input file does not
 *                represent a valid T.4 code word
 *
 * Description: this function is used to extract T.4 code
 *              representing pixel runs, or the EOL code
 *              word
 */
static int
GetPixelRun(PIXEL_WANTED color, FILE *fin)
{
  unsigned int code_word = 0;
  int bits = 0;
  int pixel_run, next_bit, min_bits, max_bits;
  const T4_DECODE *t4p;

  /* treat wanted as a Boolean, BLACK_WANTED indicates    */
  /* black, any other value indicates white               */
  if (BLACK_WANTED == color)
  {