decode.c

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

/*  decode.c - contains code to decode Group 3 Facsimilie T.4
 *             encoding back to binary pixel image data
 *
 *  Copyright (C) 2000  Jack Klein
 *                      Macmillan Computer Publishing
 *
 *  This program is free software; you can redistribute it
 *  and/or modify it under the terms of the GNU General
 *  Public License as published by the Free Software
 *  Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will
 *  be useful, but WITHOUT ANY WARRANTY; without even the
 *  implied warranty of MERCHANTABILITY or FITNESS FOR A
 *  PARTICULAR PURPOSE.  See the GNU General Public License
 *  for more details.
 *
 *  You should have received a copy of the GNU General
 *  Public License along with this program; if not, write
 *  to the Free Software Foundation, Inc., 675 Mass Ave,
 *  Cambridge, MA 02139, USA.
 *
 *  Jack Klein may be contacted by email at:
 *     [e-mail]
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "fax.h"

/* the T4_DECODE structure is the data type used in the
 * look up tables for matchine T.4 code words from the
 * input bit stream
 */
typedef struct
{
  unsigned char bit_pattern;
  unsigned char run_length;
} T4_DECODE;

static const T4_DECODE t4_white_04[] =
{
  { 0x07, 0x02 }, /*    2 white pixels */
  { 0x08, 0x03 }, /*    3 white pixels */
  { 0x0B, 0x04 }, /*    4 white pixels */
  { 0x0C, 0x05 }, /*    5 white pixels */
  { 0x0E, 0x06 }, /*    6 white pixels */
  { 0x0F, 0x07 }  /*    7 white pixels */
};

static const T4_DECODE t4_white_05[] =
{
  { 0x07, 0x0A }, /*   10 white pixels */
  { 0x08, 0x0B }, /*   11 white pixels */
  { 0x12, 0x82 }, /*  128 white pixels */
  { 0x13, 0x08 }, /*    8 white pixels */
  { 0x14, 0x09 }, /*    9 white pixels */
  { 0x1B, 0x81 }  /*   64 white pixels */
};

static const T4_DECODE t4_white_06[] =
{
  { 0x03, 0x0D }, /*   13 white pixels */
  { 0x07, 0x01 }, /*    1 white pixels */
  { 0x08, 0x0C }, /*   12 white pixels */
  { 0x17, 0x83 }, /*  192 white pixels */
  { 0x18, 0x9A }, /* 1664 white pixels */
  { 0x2A, 0x10 }, /*   16 white pixels */
  { 0x2B, 0x11 }, /*   17 white pixels */
  { 0x34, 0x0E }, /*   14 white pixels */
  { 0x35, 0x0F }  /*   15 white pixels */
};

static const T4_DECODE t4_white_07[] =
{
  { 0x03, 0x16 }, /*   22 white pixels */
  { 0x04, 0x17 }, /*   23 white pixels */
  { 0x08, 0x14 }, /*   20 white pixels */
  { 0x0C, 0x13 }, /*   19 white pixels */
  { 0x13, 0x1A }, /*   26 white pixels */
  { 0x17, 0x15 }, /*   21 white pixels */
  { 0x18, 0x1C }, /*   28 white pixels */
  { 0x24, 0x1B }, /*   27 white pixels */
  { 0x27, 0x12 }, /*   18 white pixels */
  { 0x28, 0x18 }, /*   24 white pixels */
  { 0x2B, 0x19 }, /*   25 white pixels */
  { 0x37, 0x84 }  /*  256 white pixels */
};

static const T4_DECODE t4_white_08[] =
{
  { 0x02, 0x1D }, /*   29 white pixels */
  { 0x03, 0x1E }, /*   30 white pixels */
  { 0x04, 0x2D }, /*   45 white pixels */
  { 0x05, 0x2E }, /*   46 white pixels */
  { 0x0A, 0x2F }, /*   47 white pixels */
  { 0x0B, 0x30 }, /*   48 white pixels */
  { 0x12, 0x21 }, /*   33 white pixels */
  { 0x13, 0x22 }, /*   34 white pixels */
  { 0x14, 0x23 }, /*   35 white pixels */
  { 0x15, 0x24 }, /*   36 white pixels */
  { 0x16, 0x25 }, /*   37 white pixels */
  { 0x17, 0x26 }, /*   38 white pixels */
  { 0x1A, 0x1F }, /*   31 white pixels */
  { 0x1B, 0x20 }, /*   32 white pixels */
  { 0x24, 0x35 }, /*   53 white pixels */
  { 0x25, 0x36 }, /*   54 white pixels */
  { 0x28, 0x27 }, /*   39 white pixels */
  { 0x29, 0x28 }, /*   40 white pixels */
  { 0x2A, 0x29 }, /*   41 white pixels */
  { 0x2B, 0x2A }, /*   42 white pixels */
  { 0x2C, 0x2B }, /*   43 white pixels */
  { 0x2D, 0x2C }, /*   44 white pixels */
  { 0x32, 0x3D }, /*   61 white pixels */
  { 0x33, 0x3E }, /*   62 white pixels */
  { 0x34, 0x3F }, /*   63 white pixels */
  { 0x35, 0x00 }, /*    0 white pixels */
  { 0x36, 0x85 }, /*  320 white pixels */
  { 0x37, 0x86 }, /*  384 white pixels */
  { 0x4A, 0x3B }, /*   59 white pixels */
  { 0x4B, 0x3C }, /*   60 white pixels */
  { 0x52, 0x31 }, /*   49 white pixels */
  { 0x53, 0x32 }, /*   50 white pixels */
  { 0x54, 0x33 }, /*   51 white pixels */
  { 0x55, 0x34 }, /*   52 white pixels */
  { 0x58, 0x37 }, /*   55 white pixels */
  { 0x59, 0x38 }, /*   56 white pixels */
  { 0x5A, 0x39 }, /*   57 white pixels */
  { 0x5B, 0x3A }, /*   58 white pixels */
  { 0x64, 0x87 }, /*  448 white pixels */
  { 0x65, 0x88 }, /*  512 white pixels */
  { 0x67, 0x8A }, /*  640 white pixels */
  { 0x68, 0x89 }  /*  576 white pixels */
};

static const T4_DECODE t4_white_09[] =
{
  { 0x98, 0x97 }, /* 1472 white pixels */
  { 0x99, 0x98 }, /* 1536 white pixels */
  { 0x9A, 0x99 }, /* 1600 white pixels */
  { 0x9B, 0x9B }, /* 1728 white pixels */
  { 0xCC, 0x8B }, /*  704 white pixels */
  { 0xCD, 0x8C }, /*  768 white pixels */
  { 0xD2, 0x8D }, /*  832 white pixels */
  { 0xD3, 0x8E }, /*  896 white pixels */
  { 0xD4, 0x8F }, /*  960 white pixels */
  { 0xD5, 0x90 }, /* 1024 white pixels */
  { 0xD6, 0x91 }, /* 1088 white pixels */
  { 0xD7, 0x92 }, /* 1152 white pixels */
  { 0xD8, 0x93 }, /* 1216 white pixels */
  { 0xD9, 0x94 }, /* 1280 white pixels */
  { 0xDA, 0x95 }, /* 1344 white pixels */
  { 0xDB, 0x96 }  /* 1408 white pixels */
};

static const T4_DECODE t4_black_02[] =
{
  { 0x02, 0x03 }, /*    3 black pixels */
  { 0x03, 0x02 }  /*    2 black pixels */
};

static const T4_DECODE t4_black_03[] =
{
  { 0x02, 0x01 }, /*   1 black pixels */
  { 0x03, 0x04 }  /*   4 black pixels */
};

static const T4_DECODE t4_black_04[] =
{
  { 0x02, 0x06 }, /*    6 black pixels */
  { 0x03, 0x05 }  /*    5 black pixels */
};

static const T4_DECODE t4_black_05[] =
{
  { 0x03, 0x07 }  /*    7 black pixels */
};

static const T4_DECODE t4_black_06[] =
{
  { 0x04, 0x09 }, /*    9 black pixels */
  { 0x05, 0x08 }  /*    8 black pixels */
};

static const T4_DECODE t4_black_07[] =
{
  { 0x04, 0x0A }, /*   10 black pixels */
  { 0x05, 0x0B }, /*   11 black pixels */
  { 0x07, 0x0C }  /*   12 black pixels */
};

static const T4_DECODE t4_black_08[] =
{
  { 0x04, 0x0D }, /*   13 black pixels */
  { 0x07, 0x0E }  /*   14 black pixels */
};

static const T4_DECODE t4_black_09[] =
{
  { 0x18, 0x0F }  /*   15 black pixels */
};

static const T4_DECODE t4_black_10[] =
{
  { 0x08, 0x12 }, /*   18 black pixels */
  { 0x0F, 0x81 }, /*   64 black pixels */
  { 0x17, 0x10 }, /*   16 black pixels */
  { 0x18, 0x11 }, /*   17 black pixels */
  { 0x37, 0x00 }  /*    0 black pixels */
};

static const T4_DECODE  t4_black_11[] =
{
  { 0x17, 0x18 }, /*   24 black pixels */
  { 0x18, 0x19 }, /*   25 black pixels */
  { 0x28, 0x17 }, /*   23 black pixels */
  { 0x37, 0x16 }, /*   22 black pixels */
  { 0x67, 0x13 }, /*   19 black pixels */
  { 0x68, 0x14 }, /*   20 black pixels */
  { 0x6C, 0x15 }  /*   21 black pixels */
};

static const T4_DECODE t4_black_12[] =
{
  { 0x24, 0x34 }, /*   52 black pixels */
  { 0x27, 0x37 }, /*   55 black pixels */
  { 0x28, 0x38 }, /*   56 black pixels */
  { 0x2B, 0x3B }, /*   59 black pixels */
  { 0x2C, 0x3C }, /*   60 black pixels */
  { 0x33, 0x85 }, /*  320 black pixels */
  { 0x34, 0x86 }, /*  384 black pixels */
  { 0x35, 0x87 }, /*  448 black pixels */
  { 0x37, 0x35 }, /*   53 black pixels */
  { 0x38, 0x36 }, /*   54 black pixels */
  { 0x52, 0x32 }, /*   50 black pixels */
  { 0x53, 0x33 }, /*   51 black pixels */
  { 0x54, 0x2C }, /*   44 black pixels */
  { 0x55, 0x2D }, /*   45 black pixels */
  { 0x56, 0x2E }, /*   46 black pixels */
  { 0x57, 0x2F }, /*   47 black pixels */
  { 0x58, 0x39 }, /*   57 black pixels */
  { 0x59, 0x3A }, /*   58 black pixels */
  { 0x5A, 0x3D }, /*   61 black pixels */
  { 0x5B, 0x84 }, /*  256 black pixels */
  { 0x64, 0x30 }, /*   48 black pixels */
  { 0x65, 0x31 }, /*   49 black pixels */
  { 0x66, 0x3E }, /*   62 black pixels */
  { 0x67, 0x3F }, /*   63 black pixels */
  { 0x68, 0x1E }, /*   30 black pixels */
  { 0x69, 0x1F }, /*   31 black pixels */
  { 0x6A, 0x20 }, /*   32 black pixels */
  { 0x6B, 0x21 }, /*   33 black pixels */
  { 0x6C, 0x28 }, /*   40 black pixels */
  { 0x6D, 0x29 }, /*   41 black pixels */
  { 0xC8, 0x82 }, /*  128 black pixels */
  { 0xC9, 0x83 }, /*  192 black pixels */
  { 0xCA, 0x1A }, /*   26 black pixels */
  { 0xCB, 0x1B }, /*   27 black pixels */
  { 0xCC, 0x1C }, /*   28 black pixels */
  { 0xCD, 0x1D }, /*   29 black pixels */
  { 0xD2, 0x22 }, /*   34 black pixels */
  { 0xD3, 0x23 }, /*   35 black pixels */
  { 0xD4, 0x24 }, /*   36 black pixels */
  { 0xD5, 0x25 }, /*   37 black pixels */
  { 0xD6, 0x26 }, /*   38 black pixels */
  { 0xD7, 0x27 }, /*   39 black pixels */
  { 0xDA, 0x2A }, /*   42 black pixels */
  { 0xDB, 0x2B }  /*   43 black pixels */
};

static const T4_DECODE t4_black_13[] =
{
  { 0x4A, 0x8A }, /*  640 black pixels */
  { 0x4B, 0x8B }, /*  704 black pixels */
  { 0x4C, 0x8C }, /*  768 black pixels */
  { 0x4D, 0x8D }, /*  832 black pixels */
  { 0x52, 0x94 }, /* 1280 black pixels */
  { 0x53, 0x95 }, /* 1344 black pixels */
  { 0x54, 0x96 }, /* 1408 black pixels */
  { 0x55, 0x97 }, /* 1472 black pixels */
  { 0x5A, 0x98 }, /* 1536 black pixels */
  { 0x5B, 0x99 }, /* 1600 black pixels */
  { 0x64, 0x9A }, /* 1664 black pixels */
  { 0x65, 0x9B }, /* 1728 black pixels */
  { 0x6C, 0x88 }, /*  512 black pixels */
  { 0x6D, 0x89 }, /*  576 black pixels */
  { 0x72, 0x8E }, /*  896 black pixels */
  { 0x73, 0x8F }, /*  960 black pixels */
  { 0x74, 0x90 }, /* 1024 black pixels */
  { 0x75, 0x91 }, /* 1088 black pixels */
  { 0x76, 0x92 }, /* 1152 black pixels */
  { 0x77, 0x93 }  /* 1216 black pixels */
};

/* the CODE_TABLE structure designates arrays of
 * T4_DECODE structures for each possible combination
 * of pixel color and code word length
 *
 * each structure contains a pointer to an array of
 * T4_DECODE structures and the length of the array
 */
typedef struct
{
  const T4_DECODE *token;
  int search_length;
} CODE_TABLE;

/* the two dimensional array of CODE_TABLE structures
 * is used in the actual decoding process, there are two
 * elements, one for black, the other for white, for each
 * possible code word length, 2 through 13 inclusive,
 * for a total of 12 possible code word lengths