rx.h

ac3的解码程序

					struct rexp_node * a);
RX_DECL struct rexp_node * rx_mk_r_star (struct rx * rx,
					 struct rexp_node * a);
RX_DECL struct rexp_node * rx_mk_r_2phase_star (struct rx * rx,
						struct rexp_node * a,
						struct rexp_node * b);
RX_DECL struct rexp_node * rx_mk_r_side_effect (struct rx * rx,
						rx_side_effect a);
RX_DECL struct rexp_node * rx_mk_r_data  (struct rx * rx,
					  void * a);
RX_DECL void rx_free_rexp (struct rx * rx, struct rexp_node * node);
RX_DECL struct rexp_node * rx_copy_rexp (struct rx *rx,
					 struct rexp_node *node);
RX_DECL struct rx_nfa_state * rx_nfa_state (struct rx *rx);
RX_DECL void rx_free_nfa_state (struct rx_nfa_state * n);
RX_DECL struct rx_nfa_state * rx_id_to_nfa_state (struct rx * rx,
						  int id);
RX_DECL struct rx_nfa_edge * rx_nfa_edge (struct rx *rx,
					  enum rx_nfa_etype type,
					  struct rx_nfa_state *start,
					  struct rx_nfa_state *dest);
RX_DECL void rx_free_nfa_edge (struct rx_nfa_edge * e);
RX_DECL void rx_free_nfa (struct rx *rx);
RX_DECL int rx_build_nfa (struct rx *rx,
			  struct rexp_node *rexp,
			  struct rx_nfa_state **start,
			  struct rx_nfa_state **end);
RX_DECL void rx_name_nfa_states (struct rx *rx);
RX_DECL int rx_eclose_nfa (struct rx *rx);
RX_DECL void rx_delete_epsilon_transitions (struct rx *rx);
RX_DECL int rx_compactify_nfa (struct rx *rx,
			       void **mem, unsigned long *size);
RX_DECL void rx_release_superset (struct rx *rx,
				  struct rx_superset *set);
RX_DECL struct rx_superset * rx_superset_cons (struct rx * rx,
					       struct rx_nfa_state *car, struct rx_superset *cdr);
RX_DECL struct rx_superset * rx_superstate_eclosure_union
  (struct rx * rx, struct rx_superset *set, struct rx_nfa_state_set *ecl);
RX_DECL struct rx_superstate * rx_superstate (struct rx *rx,
					      struct rx_superset *set);
RX_DECL struct rx_inx * rx_handle_cache_miss
  (struct rx *rx, struct rx_superstate *super, unsigned char chr, void *data);
RX_DECL reg_errcode_t rx_compile (__const__ char *pattern, int size,
				  reg_syntax_t syntax,
				  struct re_pattern_buffer * rxb);
RX_DECL void rx_blow_up_fastmap (struct re_pattern_buffer * rxb);
#else /* STDC */
RX_DECL int rx_bitset_is_equal ();
RX_DECL int rx_bitset_is_subset ();
RX_DECL int rx_bitset_empty ();
RX_DECL void rx_bitset_null ();
RX_DECL void rx_bitset_universe ();
RX_DECL void rx_bitset_complement ();
RX_DECL void rx_bitset_assign ();
RX_DECL void rx_bitset_union ();
RX_DECL void rx_bitset_intersection ();
RX_DECL void rx_bitset_difference ();
RX_DECL void rx_bitset_revdifference ();
RX_DECL void rx_bitset_xor ();
RX_DECL unsigned long rx_bitset_hash ();
RX_DECL struct rx_hash_item * rx_hash_find ();
RX_DECL struct rx_hash_item * rx_hash_store ();
RX_DECL void rx_hash_free ();
RX_DECL void rx_free_hash_table ();
RX_DECL rx_Bitset rx_cset ();
RX_DECL rx_Bitset rx_copy_cset ();
RX_DECL void rx_free_cset ();
RX_DECL struct rexp_node * rexp_node ();
RX_DECL struct rexp_node * rx_mk_r_cset ();
RX_DECL struct rexp_node * rx_mk_r_concat ();
RX_DECL struct rexp_node * rx_mk_r_alternate ();
RX_DECL struct rexp_node * rx_mk_r_opt ();
RX_DECL struct rexp_node * rx_mk_r_star ();
RX_DECL struct rexp_node * rx_mk_r_2phase_star ();
RX_DECL struct rexp_node * rx_mk_r_side_effect ();
RX_DECL struct rexp_node * rx_mk_r_data  ();
RX_DECL void rx_free_rexp ();
RX_DECL struct rexp_node * rx_copy_rexp ();
RX_DECL struct rx_nfa_state * rx_nfa_state ();
RX_DECL void rx_free_nfa_state ();
RX_DECL struct rx_nfa_state * rx_id_to_nfa_state ();
RX_DECL struct rx_nfa_edge * rx_nfa_edge ();
RX_DECL void rx_free_nfa_edge ();
RX_DECL void rx_free_nfa ();
RX_DECL int rx_build_nfa ();
RX_DECL void rx_name_nfa_states ();
RX_DECL int rx_eclose_nfa ();
RX_DECL void rx_delete_epsilon_transitions ();
RX_DECL int rx_compactify_nfa ();
RX_DECL void rx_release_superset ();
RX_DECL struct rx_superset * rx_superset_cons ();
RX_DECL struct rx_superset * rx_superstate_eclosure_union ();
RX_DECL struct rx_superstate * rx_superstate ();
RX_DECL struct rx_inx * rx_handle_cache_miss ();
RX_DECL reg_errcode_t rx_compile ();
RX_DECL void rx_blow_up_fastmap ();
#endif /* STDC */


#endif /* RX_WANT_RX_DEFS */



#ifdef __STDC__
extern int re_search_2 (struct re_pattern_buffer *rxb,
			__const__ char * string1, int size1,
			__const__ char * string2, int size2,
			int startpos, int range,
			struct re_registers *regs,
			int stop);
extern int re_search (struct re_pattern_buffer * rxb, __const__ char *string,
		      int size, int startpos, int range,
		      struct re_registers *regs);
extern int re_match_2 (struct re_pattern_buffer * rxb,
		       __const__ char * string1, int size1,
		       __const__ char * string2, int size2,
		       int pos, struct re_registers *regs, int stop);
extern int re_match (struct re_pattern_buffer * rxb,
		     __const__ char * string,
		     int size, int pos,
		     struct re_registers *regs);
extern reg_syntax_t re_set_syntax (reg_syntax_t syntax);
extern void re_set_registers (struct re_pattern_buffer *bufp,
			      struct re_registers *regs,
			      unsigned num_regs,
			      regoff_t * starts, regoff_t * ends);
extern __const__ char * re_compile_pattern (__const__ char *pattern,
					int length,
					struct re_pattern_buffer * rxb);
extern int re_compile_fastmap (struct re_pattern_buffer * rxb);
extern char * re_comp (__const__ char *s);
extern int re_exec (__const__ char *s);
extern int regcomp (regex_t * preg, __const__ char * pattern, int cflags);
extern int regexec (__const__ regex_t *preg, __const__ char *string,
		    size_t nmatch, regmatch_t pmatch[],
		    int eflags);
extern size_t regerror (int errcode, __const__ regex_t *preg,
			char *errbuf, size_t errbuf_size);
extern void regfree (regex_t *preg);

#else /* STDC */
extern int re_search_2 ();
extern int re_search ();
extern int re_match_2 ();
extern int re_match ();
extern reg_syntax_t re_set_syntax ();
extern void re_set_registers ();
extern __const__ char * re_compile_pattern ();
extern int re_compile_fastmap ();
extern char * re_comp ();
extern int re_exec ();
extern int regcomp ();
extern int regexec ();
extern size_t regerror ();
extern void regfree ();

#endif /* STDC */



#ifdef RX_WANT_RX_DEFS

struct rx_counter_frame
{
  int tag;
  int val;
  struct rx_counter_frame * inherited_from; /* If this is a copy. */
  struct rx_counter_frame * cdr;
};

struct rx_backtrack_frame
{
  char * counter_stack_sp;

  /* A frame is used to save the matchers state when it crosses a 
   * backtracking point.  The `stk_' fields correspond to variables
   * in re_search_2 (just strip off thes `stk_').  They are documented
   * tere.
   */
  struct rx_superstate * stk_super;
  unsigned int stk_c;
  struct rx_string_position stk_test_pos;
  int stk_last_l;
  int stk_last_r;
  int stk_test_ret;

  /* This is the list of options left to explore at the backtrack
   * point for which this frame was created. 
   */
  struct rx_distinct_future * df;
  struct rx_distinct_future * first_df;

#ifdef RX_DEBUG
   int stk_line_no;
#endif
};

struct rx_stack_chunk
{
  struct rx_stack_chunk * next_chunk;
  int bytes_left;
  char * sp;
};

enum rx_outer_entry
{
  rx_outer_start,
  rx_outer_fastmap,
  rx_outer_test,
  rx_outer_restore_pos
};

enum rx_fastmap_return
{
  rx_fastmap_continuation,
  rx_fastmap_error,
  rx_fastmap_ok,
  rx_fastmap_fail
};

enum rx_fastmap_entry
{
  rx_fastmap_start,
  rx_fastmap_string_break
};

enum rx_test_return
{
  rx_test_continuation,
  rx_test_error,
  rx_test_fail,
  rx_test_ok
};

enum rx_test_internal_return
{
  rx_test_internal_error,
  rx_test_found_first,
  rx_test_line_finished
};

enum rx_test_match_entry
{
  rx_test_start,
  rx_test_cache_hit_loop,
  rx_test_backreference_check,
  rx_test_backtrack_return
};

struct rx_search_state
{
  /* Two groups of registers are kept.  The group with the register state
   * of the current test match, and the group that holds the state at the end
   * of the best known match, if any.
   *
   * For some patterns, there may also be registers saved on the stack.
   */
  unsigned num_regs;		/* Includes an element for register zero. */
  regoff_t * lparen;		/* scratch space for register returns */
  regoff_t * rparen;
  regoff_t * best_lpspace;	/* in case the user doesn't want these */
  regoff_t * best_rpspace;	/* values, we still need space to store
				 * them.  Normally, this memoryis unused
				 * and the space pointed to by REGS is 
				 * used instead.
				 */
  
  int last_l;			/* Highest index of a valid lparen. */
  int last_r;			/* It's dual. */
  
  int * best_lparen;		/* This contains the best known register */
  int * best_rparen;		/* assignments. 
				 * This may point to the same mem as
				 * best_lpspace, or it might point to memory
				 * passed by the caller.
				 */
  int best_last_l;		/* best_last_l:best_lparen::last_l:lparen */
  int best_last_r;


  unsigned char * translate;  

  struct rx_string_position outer_pos;

  struct rx_superstate * start_super;
  int nfa_choice;
  int first_found;		/* If true, return after finding any match. */
  int ret_val;

  /* For continuations... */
  enum rx_outer_entry outer_search_resume_pt;
  struct re_pattern_buffer * saved_rxb;
  int saved_startpos;
  int saved_range;
  int saved_stop;
  int saved_total_size;
  rx_get_burst_fn saved_get_burst;
  rx_back_check_fn saved_back_check;
  struct re_registers * saved_regs;
  
  /**
   ** state for fastmap
   **/
  char * fastmap;
  int fastmap_chr;
  int fastmap_val;

  /* for continuations in the fastmap procedure: */
  enum rx_fastmap_entry fastmap_resume_pt;

  /**
   ** state for test_match 
   **/

  /* The current superNFA position of the matcher. */
  struct rx_superstate * super;
  
  /* The matcher interprets a series of instruction frames.
   * This is the `instruction counter' for the interpretation.
   */
  struct rx_inx * ifr;
  
  /* We insert a ghost character in the string to prime
   * the nfa.  test_pos.pos, test_pos.str_half, and test_pos.end_half
   * keep track of the test-match position and string-half.
   */
  unsigned char c;
  
  /* Position within the string. */
  struct rx_string_position test_pos;

  struct rx_stack_chunk * counter_stack;
  struct rx_stack_chunk * backtrack_stack;
  int backtrack_frame_bytes;
  int chunk_bytes;
  struct rx_stack_chunk * free_chunks;

  /* To return from this function, set test_ret and 
   * `goto test_do_return'.
   *
   * Possible return values are:
   *     1   --- end of string while the superNFA is still going
   *     0   --- internal error (out of memory)
   *	-1   --- search completed by reaching the superNFA fail state
   *    -2   --- a match was found, maybe not the longest.
   *
   * When the search is complete (-1), best_last_r indicates whether
   * a match was found.
   *
   * -2 is return only if search_state.first_found is non-zero.
   *
   * if search_state.first_found is non-zero, a return of -1 indicates no match,
   * otherwise, best_last_r has to be checked.
   */
  int test_ret;

  int could_have_continued;
  
#ifdef RX_DEBUG
  int backtrack_depth;
  /* There is a search tree with every node as set of deterministic
   * transitions in the super nfa.  For every branch of a 
   * backtrack point is an edge in the tree.
   * This counts up a pre-order of nodes in that tree.
   * It's saved on the search stack and printed when debugging. 
   */
  int line_no;
  int lines_found;
#endif


  /* For continuations within the match tester */
  enum rx_test_match_entry test_match_resume_pt;
  struct rx_inx * saved_next_tr_table;
  struct rx_inx * saved_this_tr_table;
  int saved_reg;
  struct rx_backtrack_frame * saved_bf;
  
};


extern char rx_slowmap[];
extern unsigned char rx_id_translation[];

static __inline__ void
init_fastmap (rxb, search_state)
     struct re_pattern_buffer * rxb;
     struct rx_search_state * search_state;
{
  search_state->fastmap = (rxb->fastmap
			   ? (char *)rxb->fastmap
			   : (char *)rx_slowmap);
  /* Update the fastmap now if not correct already. 
   * When the regexp was compiled, the fastmap was computed
   * and stored in a bitset.  This expands the bitset