mem_tsvqe_util.c

这是TSVQ的经典实现

static char license_1[16][70] = {
    "LICENSE NOTICE AND DISCLAIMER",

    "This is a modified version of software provided by Jill",
    "Goldschneider at the University of Washington Data Compression",
    "Lab. The modifications were made by the",

	   "Environmental Research Institute of Michigan",
	   "1975 Green Road",
	   "Ann Arbor, Michigan 48107",
	   "Telephone: [phone]",

    "under U.S. government contract DLA900-88-D-0392.",

    "There is no warranty, either express or implied, for these",
    "modifications and documentation, including, without limitation,",
    "warranty of merchantibility and warranty of fitness for a ",
    "particular purpose.",

     "These modifications may be used for any non-commercial",
     "purpose, such as research, provided this notice is kept",
     "intact."
};

/******************************************************************************

 Name:   mem_tsvqe_util.c
 Date:   Jan. 31, 1996

 Marko Slyz created mem_tsvqe_util.c by modifying a version of tsvqe_util.c,
 which was written by Jill Goldschneider and last revised in February 1994.

 The routines in mem_tsvqe_util have the following features:

 1) The encoder generates an actual compressed bit stream, which consists of
    indices. The decoder uses these indices to construct an approximation to
    the original data. Calling P2I_image_encode() and then feeding the
    resulting output to I2P_image_decode() should give the same result as a
    single call to tsvqe_util.c's image_encode().
 2) They compress and decompress to and from memory instead of disk.
 3) The encoder can insert restart markers in the output bit stream. Then, if
    that bit stream becomes corrupted, the decoder uses these restart markers
    to recover at least some of the original data.


    DESCRIPTION OF THE BASIC TECHNIQUE

    The restart marker scheme is similar to the one in the JPEG standard [1,
    Section 7.4]. Start by picking some natural number RI_len, then take the
    stream of (possibly variable-length) indices and put a marker after every
    RI_len of them. A marker consists of two bytes. The first is always
    7F. The second is a number that cycles through markers[] (which is defined
    in mem_bits.c). The entire first marker is (7F markers[1]), the
    (NUM_MARKERS-1)th is (7F markers[NUM_MARKERS - 1]) and the NUM_MARKERSth
    marker is (7F markers[1]) again.

    At the receiver, parse the data into segments delimited by markers. Each
    segment's marker determines the location in the image to begin placing the
    pixels corresponding to that segment's indices. This will work perfectly
    if the markers never get corrupted.

    One complication is that 7F's, which indicate markers, can also appear
    naturally in the bits composing the indices. This is bypassed by stuffing
    a 00 byte after each natural occurrence of 7F. The receiver will then need
    to remember that 7F 00 needs to be translated to just 7F before the
    decompressor sees it.

    WHAT HAPPENS WHEN SUBSTITUTION AND INSERTION/DELETION ERRORS OCCUR

    Unfortunately, the markers can get corrupted. One coping strategy is to
    remember the index (i.e. the position in markers[]) of the last decoded
    marker. Then look for the next marker whose index is greater. If its index
    isn't exactly one greater then the receiver knows that an error has been
    made, but for simplicity doesn't try to estimate the missing marker's
    location.

    With this strategy, if an error occurs in a marker then the entire segment
    corresponding to that marker is lost. Also, if an error occurs in the
    indices, then at most the rest of the segment is lost.

    COMPARISONS WITH EXISTING TECHNIQUES

    7F is used instead of the FF used in the JPEG scheme because, no matter
    what bits surround 7F, it is always possible to tell where the 7F
    starts. This is not true for FF; consider the bits stream "01" as an
    example. Suppose that an FF marker code was appended at the end of the bit
    stream to produce: "0111111111". The decoder would not be able to tell
    whether the marker begins at bit position 2 or 3, since FF's start at both
    positions.

    The rationale for using markers[] -- as opposed to the numbers from 1 to
    NUM_MARKERS-1 -- arises from choosing the codes in markers[] such that no
    single insertion, deletion or substitution error can create another valid
    entry in markers[]. So any single error in a marker will create an invalid
    codeword. This is useful since it's better to have a codeword that's known
    to be wrong than to have a codeword that's wrong but is thought to be ok;
    the latter can screw-up not just the current interval but the succeeding
    ones as well.

    The restart marker scheme used here is also similar to comma codes, which
    are discussed in, for example, [2, Section 12.5].


    REFERENCES

    [1] Pennebaker, Mitchell, _JPEG_Still_Image_Data_compression_Standard_,
        Van Nostrand Reinhold, New York, 1993.

    [2] J. Stiffler, "Theory of Synchronous Communication", Prentice-Hall,
        Englewood Cliffs, 1971.


*****************************************************************************/
#include <assert.h>
#include <limits.h>
#include "tsvq.h"
#include "protect.h"
#include "mem_bits.h"

#define round(x)        floor((x) + 0.5)

/* -------------------------------------------------- */
/* An external variable that should be put into a header file: */

extern int   dim;

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

/* This encodes the vector pointed to by "vector" using the tree rooted at
   "node" and saves the index in the array pointed to by "(*output_p)". It
   also sets "*tempbits" and "*tempdistortion".

   Note that only if a tree consists of one node is it possible for a zero-bit
   codeword to occur. Moreover, in that case _all_ of the codewords will have
   zero bits since there is never a need to disambiguate two possibilities,
   except for EOF/not-EOF, and that's handled by the initial transmission of
   the number of codewords. */
static void mem_encode(TreeNode *node, DATATYPE *vector, int *tempbits,
                       DISTTYPE *tempdistortion)
{
  DISTTYPE left_dist, right_dist;

  node->avmse += (*tempdistortion = dist(vector, node->data));
  *tempbits = 0;

  while ((node->left_child != NULL) && (node->right_child != NULL)) {
    node->count++;
    left_dist = dist(vector, node->left_child->data);
    right_dist = dist(vector, node->right_child->data);

    /* Go to the next node: */
    if (left_dist < right_dist) {
      (*tempbits) += mem_output_zero();
      node = node->left_child;
      node->avmse += (*tempdistortion = left_dist);
    } else {
      (*tempbits) += mem_output_one();
      node = node->right_child;
      node->avmse += (*tempdistortion = right_dist);
    }
  }

  assert((node->left_child == NULL) && (node->right_child == NULL));
  node->count++;
}

#if 0
static void print_blocked(DATATYPE *data, int num_in)
{
  int i, j;
  FILE *fp;

  OPEN(fp, "mem_data_jjj", a);
  for (i = 0; i < num_in; i++) {
/*    fprintf(fp, "%x: ", i); */
    for (j = 0; j < dim; j++)
      fprintf(fp, "%x ", data[i*dim + j]);
    fprintf(fp, "\n");
  }

  CLOSE(fp);
}

  remove("mem_data_jjj");       /* so that print_blocked() starts fresh */
  print_blocked(input, num_in);
#endif

/* P2I_image_encode(): This translates pixels to indices.
  INPUT:
    root:        codebook tree
    input:       input[i*dim] is the first pixel in the ith input vector
    output_p:    (*output_p) should be a pointer to uchar. Upon return it will
                      point to an array (ceil(*bits/8.0) long) of indices.
    num_in:      the number of input vectors
    rate:        An array of num_in uchars. It'll contain the number of
                      bits per vector.
    RI_len:      The length of a restart interval, i.e. the number of indices
                      to output between restart markers. If this is zero then
                      no restart markers are used.

  OUTPUT:
    bits:        the number of bits used to encode the image
    maxbits:     the longest codeword used
    numpixels:   the number of pixels encoded
*/
DISTTYPE P2I_image_encode(TreeNode *root, long *bits, int *maxbits,
                          long *numpixels, DATATYPE *input, uchar **output_p,
                          int num_in, uchar *rate, int RI_len)
{
  int      i;               /* the index of the current vector */
  int      tempbits;        /* length of codeword to encode current vector */
  DISTTYPE tempdistortion;  /* distortion of current encoded vector */
  DISTTYPE distortion;      /* distortion of encoded image */
  
  distortion = 0.0;
  *maxbits = 0;
  *numpixels = 0;
  init_mem_bits(output_p, RI_len);

  for (i = 0; i < num_in; i++) {
    /* Put a marker after every RI_len indices, and don't have one before the
       zeroth index. */
    if ((RI_len > 0) && (i % RI_len == 0) && (i > 0)) {
      rate[i] = MARKER_LEN;
      insert_marker();
    } else
      rate[i] = 0;

    mem_encode(root, input+i*dim, &tempbits, &tempdistortion);
    
    distortion += tempdistortion;
    rate[i] += tempbits;
    if (tempbits > *maxbits)
      *maxbits = tempbits;
    *numpixels += dim;
  }

  *bits = number_of_bits_output();
  normalize_avmse(root); 
  return distortion;
}

/* -------------------------------------------------- */
/* The decoding routines: */

#define BAD_INTERVAL  -1
static int min(int a, int b)  { if (a < b) return a; else return b; }

/* Some debugging code: */
#ifdef DBITS
  /* Define a place to record the beginnings of input[]'s intervals.  (note
     that interval_start[] records the same thing but for clean_input[]): */
  #define    MAX_INTERVAL_START     250000
  static int input_interval_start[MAX_INTERVAL_START];

  /* Define places to record the locations of the markers that precede stuffed
     zero bytes that occur in "input" and "clean_input": */
  #define    MAX_STUFFED            50000
  static int input_stuffed[MAX_STUFFED];
  static int clean_stuffed[MAX_STUFFED];

  static int stuffed_pos;       /* the current location in input_stuffed[] and
                                   clean_stuffed[] */
  static int input_pos;         /* the current location in
                                   input_interval_start[] */

  /* This is called right after a stuffed byte has been detected. */
  static void RECORD_STUFFED(int bit, int k)
  {
    if (stuffed_pos < MAX_STUFFED) {
      input_stuffed[stuffed_pos] = bit - 16;
      clean_stuffed[stuffed_pos] = k - 8;
    } else
      pr_error("Recompile with a larger value of MAX_STUFFED");

    stuffed_pos++;
  }

  /* This is called right after an interval start marker has been detected. */
  static void RECORD_INPUT_INTERVAL_START(int bit, int i, int num_RIs)
  {
    if (i < MAX_INTERVAL_START) {
      for ( ; input_pos < i ; input_pos++)
        input_interval_start[input_pos] = BAD_INTERVAL;
      input_interval_start[input_pos] = bit - 16;
      if (input_pos < num_RIs) input_pos++;
    } else
      pr_error("Recompile with a larger value of MAX_INTERVAL_START");
  }

  /* INPUTS:
       This prints all the bits in Xinput. While it's doing this, it prints a
       "X#1(#2):" right before each bit position indicated by Xinterval_start,
       and a "Y#1(#2):" right before each bit position indicated by
       Xstuffed. Here #1 is the number of that marker, while #2 is its
       location.

       in_len: The number of bits in Xinput.
       max_Xint, max_Xstuff: The number of valid elements in Xinterval_start
           and Xstuffed respectively.
       fname: The name of the file in which to print the data. */
  static void DISPLAY_BITS(uchar *Xinput, int *Xinterval_start, int *Xstuffed,
                           int in_len,    int max_Xint,         int max_Xstuff,
                           char *fname)
  {
    int i, j, k;
    int bad_count;    /* the number of bad intervals before this one */
    FILE *fp;

    OPEN(fp, fname, w);

    j = k = bad_count = 0;

    for (i = 0; i < in_len; i++) {
      if (j <= max_Xint && Xinterval_start[j] == i) {
        for (; bad_count > 0; bad_count--)
          fprintf(fp, "\n\nX%d: BAD_INTERVAL", j - bad_count);
            /* Note that Xinterval_start[0] is always 0, so the data can't
               start with bad intervals. */
        fprintf(fp, "\n\nX%d(%d): ", j, i);
        j++;
        while (j < max_Xint-1 && Xinterval_start[j] == BAD_INTERVAL)
	  j++, bad_count++;
      }

      if (k < max_Xstuff && Xstuffed[k] == i) {
        fprintf(fp, "\nY%d(%d): ", k, i);
        if (k < max_Xstuff) k++;
      }

      if (BITTEST(Xinput, i))
        fputc('1', fp);
      else
        fputc('0', fp);

      /* Put spaces after printing each group of 8 bits: */
      if (j > 1 && (i - Xinterval_start[j-1-bad_count] - 7) % 8 == 0)
        fputc(' ', fp);
    }

    CLOSE(fp);
  }