rx.c

ac3的解码程序

/*	Copyright (C) 1992, 1993 Free Software Foundation, Inc.

This file is part of the librx library.

Librx is free software; you can redistribute it and/or modify it under
the terms of the GNU Library General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

Librx 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 Library General Public
License along with this software; see the file COPYING.LIB.  If not,
write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA
02139, USA.  */

/* NOTE!!!  AIX is so losing it requires this to be the first thing in the 
 * file. 
 * Do not put ANYTHING before it!  
 */
#if !defined (__GNUC__) && defined (_AIX)
 #pragma alloca
#endif

char rx_version_string[] = "GNU Rx version 0.06";

			/* ``Too hard!''
			 *	    -- anon.
			 */


#include <stdio.h>
#include <ctype.h>
#ifndef isgraph
#define isgraph(c) (isprint (c) && !isspace (c))
#endif
#ifndef isblank
#define isblank(c) ((c) == ' ' || (c) == '\t')
#endif

#include <sys/types.h>

#undef MAX
#undef MIN
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef char boolean;
#define false 0
#define true 1

#ifndef RX_DECL
#define RX_DECL static
#endif

#ifndef __GCC__
#undef __inline__
#define __inline__
#endif

/* Emacs already defines alloca, sometimes.  */
#ifndef alloca

/* Make alloca work the best possible way.  */
#ifdef __GNUC__
#define alloca __builtin_alloca
#else /* not __GNUC__ */
#if HAVE_ALLOCA_H
#include <alloca.h>
#else /* not __GNUC__ or HAVE_ALLOCA_H */
#ifndef _AIX /* Already did AIX, up at the top.  */
char *alloca ();
#endif /* not _AIX */
#endif /* not HAVE_ALLOCA_H */ 
#endif /* not __GNUC__ */

#endif /* not alloca */

/* Memory management and stuff for emacs. */

#define CHARBITS 8
#define remalloc(M, S) (M ? realloc (M, S) : malloc (S))


/* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 * use `alloca' instead of `malloc' for the backtracking stack.
 *
 * Emacs will die miserably if we don't do this.
 */

#ifdef REGEX_MALLOC
#define REGEX_ALLOCATE malloc
#else /* not REGEX_MALLOC  */
#define REGEX_ALLOCATE alloca
#endif /* not REGEX_MALLOC */

#ifdef RX_WANT_RX_DEFS
#define RX_DECL extern
#define RX_DEF_QUAL 
#else
#define RX_WANT_RX_DEFS
#define RX_DECL static
#define RX_DEF_QUAL static
#endif
#include "rx.h"
#undef RX_DECL
#define RX_DECL RX_DEF_QUAL


#ifndef emacs

#ifdef SYNTAX_TABLE
extern char *re_syntax_table;
#else /* not SYNTAX_TABLE */

/* RX_DECL char re_syntax_table[CHAR_SET_SIZE]; */

#ifdef __STDC__
static void
init_syntax_once (void)
#else
static void
init_syntax_once ()
#endif
{
   register int c;
   static int done = 0;

   if (done)
     return;

   bzero (re_syntax_table, sizeof re_syntax_table);

   for (c = 'a'; c <= 'z'; c++)
     re_syntax_table[c] = Sword;

   for (c = 'A'; c <= 'Z'; c++)
     re_syntax_table[c] = Sword;

   for (c = '0'; c <= '9'; c++)
     re_syntax_table[c] = Sword;

   re_syntax_table['_'] = Sword;

   done = 1;
}
#endif /* not SYNTAX_TABLE */
#endif /* not emacs */

/* Compile with `-DRX_DEBUG' and use the following flags.
 *
 * Debugging flags:
 *   	rx_debug - print information as a regexp is compiled
 * 	rx_debug_trace - print information as a regexp is executed
 */

#ifdef RX_DEBUG

int rx_debug_compile = 0;
int rx_debug_trace = 0;
static struct re_pattern_buffer * dbug_rxb = 0;

#ifdef __STDC__
typedef void (*side_effect_printer) (struct rx *, void *, FILE *);
#else
typedef void (*side_effect_printer) ();
#endif

#ifdef __STDC__
static void print_cset (struct rx *rx, rx_Bitset cset, FILE * fp);
#else
static void print_cset ();
#endif

#ifdef __STDC__
static void
print_rexp (struct rx *rx,
	    struct rexp_node *node, int depth,
	    side_effect_printer seprint, FILE * fp)
#else
static void
print_rexp (rx, node, depth, seprint, fp)
     struct rx *rx;
     struct rexp_node *node;
     int depth;
     side_effect_printer seprint;
     FILE * fp;
#endif
{
  if (!node)
    return;
  else
    {
      switch (node->type)
	{
	case r_cset:
	  {
	    fprintf (fp, "%*s", depth, "");
	    print_cset (rx, node->params.cset, fp);
	    fputc ('\n', fp);
	    break;
	  }

 	case r_opt:
	case r_star:
	  fprintf (fp, "%*s%s\n", depth, "",
		   node->type == r_opt ? "opt" : "star");
	  print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
	  break;

	case r_2phase_star:
	  fprintf (fp, "%*s2phase star\n", depth, "");
	  print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp);
	  print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
	  break;


	case r_alternate:
	case r_concat:
	  fprintf (fp, "%*s%s\n", depth, "",
		   node->type == r_alternate ? "alt" : "concat");
	  print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
	  print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp);
	  break;
	case r_side_effect:
	  fprintf (fp, "%*sSide effect: ", depth, "");
	  seprint (rx, node->params.side_effect, fp);
	  fputc ('\n', fp);
	}
    }
}

#ifdef __STDC__
static void
print_nfa (struct rx * rx,
	   struct rx_nfa_state * n,
	   side_effect_printer seprint, FILE * fp)
#else
static void
print_nfa (rx, n, seprint, fp)
     struct rx * rx;
     struct rx_nfa_state * n;
     side_effect_printer seprint;
     FILE * fp;
#endif
{
  while (n)
    {
      struct rx_nfa_edge *e = n->edges;
      struct rx_possible_future *ec = n->futures;
      fprintf (fp, "node %d %s\n", n->id,
	       n->is_final ? "final" : (n->is_start ? "start" : ""));
      while (e)
	{
	  fprintf (fp, "   edge to %d, ", e->dest->id);
	  switch (e->type)
	    {
	    case ne_epsilon:
	      fprintf (fp, "epsilon\n");
	      break;
	    case ne_side_effect:
	      fprintf (fp, "side effect ");
	      seprint (rx, e->params.side_effect, fp);
	      fputc ('\n', fp);
	      break;
	    case ne_cset:
	      fprintf (fp, "cset ");
	      print_cset (rx, e->params.cset, fp);
	      fputc ('\n', fp);
	      break;
	    }
	  e = e->next;
	}

      while (ec)
	{
	  int x;
	  struct rx_nfa_state_set * s;
	  struct rx_se_list * l;
	  fprintf (fp, "   eclosure to {");
	  for (s = ec->destset; s; s = s->cdr)
	    fprintf (fp, "%d ", s->car->id);
	  fprintf (fp, "} (");
	  for (l = ec->effects; l; l = l->cdr)
	    {
	      seprint (rx, l->car, fp);
	      fputc (' ', fp);
	    }
	  fprintf (fp, ")\n");
	  ec = ec->next;
	}
      n = n->next;
    }
}

static char * efnames [] =
{
  "bogon",
  "re_se_try",
  "re_se_pushback",
  "re_se_push0",
  "re_se_pushpos",
  "re_se_chkpos",
  "re_se_poppos",
  "re_se_at_dot",
  "re_se_syntax",
  "re_se_not_syntax",
  "re_se_begbuf",
  "re_se_hat",
  "re_se_wordbeg",
  "re_se_wordbound",
  "re_se_notwordbound",
  "re_se_wordend",
  "re_se_endbuf",
  "re_se_dollar",
  "re_se_fail",
};

static char * efnames2[] =
{
  "re_se_win",
  "re_se_lparen",
  "re_se_rparen",
  "re_se_backref",
  "re_se_iter",
  "re_se_end_iter",
  "re_se_tv"
};

static char * inx_names[] = 
{
  "rx_backtrack_point",
  "rx_do_side_effects",
  "rx_cache_miss",
  "rx_next_char",
  "rx_backtrack",
  "rx_error_inx",
  "rx_num_instructions"
};


#ifdef __STDC__
static void
re_seprint (struct rx * rx, void * effect, FILE * fp)
#else
static void
re_seprint (rx, effect, fp)
     struct rx * rx;
     void * effect;
     FILE * fp;
#endif
{
  if ((int)effect < 0)
    fputs (efnames[-(int)effect], fp);
  else if (dbug_rxb)
    {
      struct re_se_params * p = &dbug_rxb->se_params[(int)effect];
      fprintf (fp, "%s(%d,%d)", efnames2[p->se], p->op1, p->op2);
    }
  else
    fprintf (fp, "[complex op # %d]", (int)effect);
}


/* These are so the regex.c regression tests will compile. */
void
print_compiled_pattern (rxb)
     struct re_pattern_buffer * rxb;
{
}

void
print_fastmap (fm)
     char * fm;
{
}

#endif /* RX_DEBUG */



/* This page: Bitsets.  Completely unintersting. */

#ifdef __STDC__
RX_DECL int
rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL int
rx_bitset_is_equal (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  RX_subset s = b[0];
  b[0] = ~a[0];

  for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
    ;

  b[0] = s;
  return !x && s == a[0];
}

#ifdef __STDC__
RX_DECL int
rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL int
rx_bitset_is_subset (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets(size) - 1;
  while (x-- && (a[x] & b[x]) == a[x]);
  return x == -1;
}


#ifdef __STDC__
RX_DECL int
rx_bitset_empty (int size, rx_Bitset set)
#else
RX_DECL int
rx_bitset_empty (size, set)
     int size;
     rx_Bitset set;
#endif
{
  int x;
  RX_subset s = set[0];
  set[0] = 1;
  for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
    ;
  set[0] = s;
  return !s;
}

#ifdef __STDC__
RX_DECL void
rx_bitset_null (int size, rx_Bitset b)
#else
RX_DECL void
rx_bitset_null (size, b)
     int size;
     rx_Bitset b;
#endif
{
  bzero (b, rx_sizeof_bitset(size));
}


#ifdef __STDC__
RX_DECL void
rx_bitset_universe (int size, rx_Bitset b)
#else
RX_DECL void
rx_bitset_universe (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    *b++ = ~(RX_subset)0;
}


#ifdef __STDC__
RX_DECL void
rx_bitset_complement (int size, rx_Bitset b)
#else
RX_DECL void
rx_bitset_complement (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    {
      *b = ~*b;
      ++b;
    }
}


#ifdef __STDC__
RX_DECL void
rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_assign (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = b[x];
}


#ifdef __STDC__
RX_DECL void
rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_union (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] |= b[x];
}


#ifdef __STDC__
RX_DECL void
rx_bitset_intersection (int size,
			rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_intersection (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &= b[x];
}


#ifdef __STDC__
RX_DECL void
rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_difference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &=  ~ b[x];
}


#ifdef __STDC__
RX_DECL void
rx_bitset_revdifference (int size,
			 rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_revdifference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = ~a[x] & b[x];
}

#ifdef __STDC__
RX_DECL void
rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
#else
RX_DECL void
rx_bitset_xor (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] ^= b[x];
}


#ifdef __STDC__
RX_DECL unsigned long
rx_bitset_hash (int size, rx_Bitset b)
#else
RX_DECL unsigned long
rx_bitset_hash (size, b)
     int size;
     rx_Bitset b;