mem_tsvqe_util.c

这是TSVQ的经典实现

  static void PRINT_MARKERS(int *interval_start, int num_RIs, char *fname)
  {
    int i;
    FILE *fp;

    OPEN(fp, fname, w);  

    if (input_pos != num_RIs)
      fprintf(fp, "warning:  (input_pos = %d) != (num_RIs = %d)\n\n",
              input_pos, num_RIs);
    fprintf(fp, "i \t\t interval_start \t\t input_interval_start\n");
    for (i = 0; i <= num_RIs; i++)
      fprintf(fp, "%d \t\t %d \t\t %d \t\t 0\n", i, interval_start[i],
              input_interval_start[i]);

    fprintf(fp, "\n\n\n");

    fprintf(fp, "input_stuffed \t\t\t clean_stuffed\n");
    for (i = 0; i < stuffed_pos; i++)
      fprintf(fp, "%d \t\t\t %d \t\t\t 1\n", input_stuffed[i],
              clean_stuffed[i]);

    CLOSE(fp);
  }

  static void INIT_DEBUG(void)
  {
    input_pos = stuffed_pos = 0;
  }

#else
  #define RECORD_STUFFED(x,y)
  #define RECORD_INPUT_INTERVAL_START(x,y,z)
  #define stuffed_pos x
  #define DISPLAY_BITS(a, b, c, d, e, f, g)
  #define PRINT_MARKERS(a, b, c)
  #define INIT_DEBUG()
#endif

/* This gets rid of the FF already copied to the output. */
static void back_up_8_bits(uchar *clean_input, int *k)
{
  int j;

  for (j = 0; j < 8; j++) {
    (*k)--;
    BITUNSET(clean_input, *k);
  }
}

/* next_marker_num_with_copy(): This copies bits from input[] to
   clean_input[]. It goes until either the next 0x7F byte (inclusive) in
   input[], or the end of the array.

   It then packs the next 8 bits into an int and returns the index of the
   element in markers[] that is equal to it. If the next 8 bits do not
   correspond to an element in markers[], it just returns NUM_MARKERS, and if
   there aren't enough bits left in the data stream to assemble a marker, it
   returns -1. */
static int next_marker_num_with_copy(uchar *input, int *bit, int in_len,
                                     uchar *clean_input, int *k)
{
  int mask, t;
  int have_starting_zero, consecutive_ones;

  have_starting_zero = consecutive_ones = 0;

  /* Find the next marker prefix: */
  while (*bit < in_len && consecutive_ones < 7) {
    if (BITTEST(input, *bit)) {
      BITSET(clean_input, *k);
      if (have_starting_zero) consecutive_ones++;
    } else {
      have_starting_zero = 1;
      consecutive_ones = 0;
    }

    (*bit)++; (*k)++;
  }

  /* If the file ends before the marker number then return: */
  if ((*bit)+8 > in_len)
    return -1;

  /* Otherwise, pull it out: */
  for (t = 0, mask = 0x80;    mask > 0;    mask >>= 1, (*bit)++)
    if (BITTEST(input, *bit))
      t |= mask;

  return marker_search_table[t];
}

/* next_marker_num(): This finds the next marker in "input" and returns its
   number. It ignores stuffed 0 bytes. */
static int next_marker_num(uchar *input, int bit, int in_len)
{
  int mask, t;
  int have_starting_zero, consecutive_ones;

  do {
    have_starting_zero = consecutive_ones = 0;

    /* Find the next marker prefix: */
    while (bit < in_len && consecutive_ones < 7) {
      if (BITTEST(input, bit)) {
        if (have_starting_zero) consecutive_ones++;
      } else {
        have_starting_zero = 1;
        consecutive_ones = 0;
      }

      bit++;
    }

    /* If the file ends before the marker number then quit: */
    if (bit+8 > in_len)
      return -1;

    /* Otherwise pull out the marker number: */
    for (t = 0, mask = 0x80;    mask > 0;    mask >>= 1, bit++)
      if (BITTEST(input, bit))
        t |= mask;

  } while (t == 0);             /* ignore stuffed 0 bytes */

  return marker_search_table[t];
}

/* If the previous marker and the next marker are consistent with each other
   (i.e. the next marker is two larger than the previous marker), then
   CHECK_NEXT() makes parse() ignore the current marker.

   Using CHECK_NEXT() is optional, but parse() will work better with it if
   seldom are two consecutive markers corrupted to create a spurious marker
   sequence. Error rates where this is common would probably be too high for
   parse() anyway.

   Note that (previous_marker%NUM_MARKERS + 1) is the current marker,
   and ((previous_marker + 1)%NUM_MARKERS + 1) is the next marker.
 */
#define CHECK_NEXT()                                                    \
 if ((valid > i)  &&  (next_marker_num(input, bit, in_len) ==           \
                       (previous_marker + 1)%NUM_MARKERS + 1))          \
      valid = i;

#define RECORD_START_AND_MOVE_ON()                                          \
        CHECK_NEXT();                                                       \
        for (; i < valid; i++)               /* Flag all the intervals   */ \
          interval_start[i] = BAD_INTERVAL;  /* after the last good one. */ \
        interval_start[i] = k;                                              \
        RECORD_INPUT_INTERVAL_START(bit, i, num_RIs);                       \
        i++;                                                                \
        previous_marker = t;

/* parse():
   INPUTS:
     input:   All of the input data indices.
     in_len:  The number of valid bits in "input".
     num_RIs: The original number of restart intervals in "input".

   OUTPUTS:
     clean_input (the return value): This contains the data in "input" with
       all of the markers and stuffed zero bytes removed.
     interval_start: This should have been allocated in the calling routine to
       point to (num_RIs + 1) ints. Upon return, interval_start[i] is the
       number of the first bit in the ith restart interval.

   parse() assumes that input[] can be generated by a grammar whose terminal
   symbols are {0,1} and that has the following rules:

       data             -> restart_interval data
       data             -> e

       restart_interval -> indices marker

       indices          -> no_stuffed stuffed indices
       indices          -> e

       ; no_stuffed can expand to any string that doesn't contain 01111111:
       no_stuffed -> I
       I -> 1 I,    I -> e,    I -> 0 Z
       Z -> 0 Z,    Z -> e,
       Z -> 1 N1,   Z -> 11 N2,  ....,  Z -> 111111 N6
       Ni -> 0 Z,   Ni -> e                          for i in {1,2,...,6}

       stuffed          -> 01111111 00000000
       stuffed          -> e

       marker           -> 01111111 u       u in markers[]  (see mem_bits.c)

   (where e is the empty string). */
static uchar *parse(uchar *input, int *interval_start, int num_RIs, int in_len)
{
  int i;                /* the number of the current restart interval  */
  int valid;            /* the next valid restart interval number      */
  int k;                /* the bit position in the "clean input" array */
  int bit;              /* the bit position in the "input" array       */
  uchar *clean_input;   /* the input array with the markers and stuffed
                            bytes removed                              */
  int previous_marker;  /* the number of the last marker segment       */
  int t;                /* the current marker's number (in {0, ...,
                           NUM_MARKERS}). 0 implies a byte stuffed 7F. */


  init_marker_search_table();
  bit = k = 0;
  interval_start[0] = 0;    /* The 0th restart interval always */
  i = 1;                    /* starts at bit position 0.       */
  RECORD_INPUT_INTERVAL_START(16, 0, num_RIs);
  clean_input = pr_alloc(sizeof(uchar) * ceil((double)in_len/CHAR_BIT), 0);
  t = next_marker_num_with_copy(input, &bit, in_len, clean_input, &k);
  previous_marker = 0;

  while (t != -1 && i < num_RIs) {

    /* LOOP INVARIANT: locations 0 to i-1 of interval_start point to the
       beginnings of the first i restart intervals. */

    /* Figure out what to do depending on what it was: */
    if (t < 0) break;      /* the data stream ended too soon */

    else if (t == 0)       /* this was a stuffed 7F byte     */
      RECORD_STUFFED(bit,k);

    else if (t > previous_marker && t < NUM_MARKERS) {
      back_up_8_bits(clean_input, &k);   /* delete the marker prefix */
      valid = min(i+(t-previous_marker-1), num_RIs);
      RECORD_START_AND_MOVE_ON();

    } else if (t <= previous_marker) {
      back_up_8_bits(clean_input, &k);
      valid = min(i + ((NUM_MARKERS-1)-previous_marker) + (t-1), num_RIs);
      RECORD_START_AND_MOVE_ON();

    } else bit -= 8;  /* Assume that a bit error generated a spurious 7F and
                         copy everything to clean_input. */

    /* Move on to the next marker: */
    t = next_marker_num_with_copy(input, &bit, in_len, clean_input, &k);

    assert(k <= in_len);
  }

  for (; i < num_RIs; i++)
    interval_start[i] = BAD_INTERVAL;
  interval_start[num_RIs] = k;

  RECORD_INPUT_INTERVAL_START(bit+16, num_RIs, num_RIs);

  return clean_input;
}

static void mem_decode(TreeNode *node, uchar *input, DATATYPE *output,
                       int *bit, int max_bit)
{
  int j;

  if (*bit == BAD_INTERVAL) {
    for (j = 0; j < dim; j++)
      output[j] = (DATATYPE)0;
    return;
  }

  while ((node->left_child != NULL) && (node->right_child != NULL)
         && (*bit < max_bit)) {
    if (BITTEST(input, *bit))
      node = node->right_child;
    else
      node = node->left_child;
    (*bit)++;
  }

  for (j = 0; j < dim; j++)         /* for double data take out the round */
    output[j] = (DATATYPE) round(node->data[j]);
    /* output[j] = (DATATYPE) node->data[j]; */
}

/* I2P_image_decode(): This translates indices to pixels.
  INPUT:
    root:        codebook tree
    input:       points to a bit array of indices
    num_in:      the number of indices coded-up in "input"
    RI_len:      the length of the restart intervals (expressed in
                     "number of indices")
    in_len:      the length of the input data (expressed in bits)

  OUTPUT:
    image_vectors: Upon return this points to an array, num_in*dim long,
                 of DATATYPEs filled with the decoded vectors.
*/
DATATYPE *I2P_image_decode(TreeNode *root, uchar *input, int num_in,
                           int RI_len, int in_len)
{
  int i, j, k;
  int bit;              /* the current location in the clean_input bit array */
  int num_RIs;          /* the number of RI's in the image                   */
  int current_len;      /* the length of the current restart interval        */
  uchar *clean_input;   /* same as "input", except without restart markers   */
  DATATYPE *image_vectors;  /* will hold the decoded image                   */
  int *interval_start;  /* interval_start[i] will be the location, expressed
                           in bits, of the beginning of the ith restart
                           interval in clean_input[].                        */

  image_vectors = pr_alloc(sizeof(DATATYPE) * dim * num_in, NOF);

  if (RI_len > 0) {
    INIT_DEBUG();
    num_RIs = (int)ceil((double)num_in/RI_len);
    interval_start = pr_alloc(sizeof(int)*(num_RIs+1), NOF);
    clean_input = parse(input, interval_start, num_RIs, in_len);
    PRINT_MARKERS(interval_start, num_RIs, "markers");
    DISPLAY_BITS(input, input_interval_start, input_stuffed, in_len,
                  num_RIs, stuffed_pos, "input_bits");
    DISPLAY_BITS(clean_input, interval_start, clean_stuffed, in_len,
                 num_RIs, stuffed_pos, "clean_bits");

    for (i = 0; i < num_RIs; i++) {
      current_len = min(RI_len, num_in - i*RI_len);
      bit = interval_start[i];        /* first valid bit in this interval */

      k = i + 1;
      while (interval_start[k] == BAD_INTERVAL)  k++;   /* last valid bit */

      for (j = 0; j < current_len; j++)
        mem_decode(root, clean_input, image_vectors + (i*RI_len+j)*dim, &bit,
                   interval_start[k]);
    }

    pr_free(interval_start);
    pr_free(clean_input);

  } else {
    bit = 0;
    for (j = 0; j < num_in; j++)
      mem_decode(root, input, image_vectors + j*dim, &bit, in_len);
  }

  return image_vectors;
}