mem_bits.c

这是TSVQ的经典实现

static char license3[14][70] = {
    "LICENSE NOTICE AND DISCLAIMER",

    "This module was created by the",

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

    "under U.S. gov't contract DLA900-88-D-0392.",

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

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

/* mem_bits.c: This includes routines and data structures that implement the
   bit buffer necessary for mem_tsvqe_util.c. */

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include "protect.h"
#include "mem_bits.h"

typedef unsigned char uchar;

#define MEM_BLK_SZ 25000     /* the size of the chunks in which memory is
				allocated */

static int   g_bits;         /* The number of bits that have been output
                                up to the current time. */
static uchar **g_output_p;   /* a local copy of output_p */
static int   g_out_room;     /* the number of bits left free in (*output_p) */
static int   g_RI_len;	     /* a local copy of RI_len */
static int   g_have_starting_zero; /* 1 if a zero has occurred after the last
				      7F <marker> pair; otherwise 0. */
static int   g_consecutive_ones; /* the number of consecutive ones that've
				    been output */
static int   g_marker_num;   /* the index of the current marker */

int markers[NUM_MARKERS] = {0x00, 0x0F, 0x30, 0x3F, 0xF0, 0xFF, 0xC0, 0xCF};

/* After init_marker_search_table() is called, marker_search_table[i] contains
   NUM_MARKERS if i is not in markers[], and otherwise the index of i in
   markers[]. extract_marker() uses this as a fast way of telling whether a
   byte is a valid marker codeword, and if so, which one. */
int marker_search_table[256];

void init_marker_search_table(void)
{
  int i;

  for (i = 0; i < 256; i++)
    marker_search_table[i] = NUM_MARKERS;

  for (i = 0; i < NUM_MARKERS; i++)
    marker_search_table[markers[i]] = i;
}

void init_mem_bits(uchar **output_p, int RI_len)
{
  g_bits = 0;
  g_output_p = output_p;
  *g_output_p = 0;              /* so that the first realloc works */
  g_out_room = 0;

  g_RI_len = RI_len;
  g_consecutive_ones = 0;
  g_have_starting_zero = 0;
  g_marker_num = 1;
}

/* This ensures enough memory to store the next bit coming in. */
static void make_sure_output_has_room(void)
{
  if (g_out_room < 1) {
    assert(g_out_room >= 0);
    assert((g_bits/8)*8 == g_bits); /* This should be true since memory is
				       always allocated as a block of bytes.*/
    g_out_room = MEM_BLK_SZ*8;
    *g_output_p = pr_realloc(*g_output_p, g_bits/8 + MEM_BLK_SZ);
    PR_MEMSET(*g_output_p + g_bits/8, 0, MEM_BLK_SZ); /* zero the new memory */
  }
}

int mem_output_zero(void)
{
  make_sure_output_has_room();
  g_bits++;
  g_out_room--;
  g_have_starting_zero = 1;  g_consecutive_ones = 0;

  return 1;
}

#define MEM_OUTPUT_ONE()	do {		\
  make_sure_output_has_room();			\
  BITSET((*g_output_p), g_bits);		\
  g_bits++;					\
  g_out_room--;					\
 } while(0)

int mem_output_one(void)
{
  int j;

  MEM_OUTPUT_ONE();

  if (g_have_starting_zero)   g_consecutive_ones++;
  if (g_RI_len != 0 && g_consecutive_ones == 7) {
    for (j = 0; j < 8; j++) 	/* stuff a 00 after each 7F */
      mem_output_zero();
    g_have_starting_zero = 0;
    return 9;
  }

  return 1;
}

int number_of_bits_output(void)
{
  return g_bits;
}

void insert_marker(void)
{
  int j, mask;

  assert(g_marker_num < NUM_MARKERS && g_marker_num >= 1);

  /* Output a 7F: */
  mem_output_zero();
  for (j = 0; j < 7; j++)
    MEM_OUTPUT_ONE();

  for (mask = 0x80;  mask > 0;  mask >>= 1)  /* output markers[g_marker_num] */
    if ((markers[g_marker_num] & mask) != 0)
      MEM_OUTPUT_ONE();
    else
      mem_output_zero();

  g_consecutive_ones = 0;	/* reset the state variables */
  g_have_starting_zero = 0;
  if (++g_marker_num >= NUM_MARKERS)
    g_marker_num = 1;
}