compress.cc

This is a resource based on j2me embedded,if you dont understand,you can connection with me .

/*
 * @(#)compress.cc	1.10 06/10/10
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program is free software; you can redistribute it and/or  
 * modify it under the terms of the GNU General Public License version  
 * 2 only, as published by the Free Software Foundation.   
 *   
 * This program 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 version 2 for more details (a copy is  
 * included at /legal/license.txt).   
 *   
 * You should have received a copy of the GNU General Public License  
 * version 2 along with this work; if not, write to the Free Software  
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
 * 02110-1301 USA   
 *   
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
 * Clara, CA 95054 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "compress.h"
#include "rule.h"
#include "state.h"
#include "symbol.h"
#include "transition.h"
#include "debug.h"
#include "globals.h"

/*
 * @(#)compress.cc	1.9	93/10/25
 * This file defines no classes
 * This file defines routines for massaging
 * statemap and transition tables,
 * for the purpose of producing more compact output.
 *
 * Towards this end, we iteratively remove redundant
 * rows & columns in transition tables, and redundant
 * states.
 * For our purposes, two states are the same ( and thus one
 * of them is redundant ) if they have all the same transitions.
 * This can be true even if they represent different itemsets and
 * thus different partial matches.
 */

extern int uncompress;

extern void delete_inversion_info();
/*
 * Squeeze redundance out of a unary transition table.
 * Simply look for identical row entries, and delete them,
 * while remapping the states.
 * Pretty brute-force sort of algorithm used here.
 *
 * We are provided with temp vectors allocated for our use,
 * since the same can be used for each transition table being
 * compressed, we save a little allocation time.
 */
int
compress_unary_transition(
	unary_symbol *usp,
	char *  delvector )
{
	statemap * 	   map = & usp->lhs_map;
	unary_transition * ut  = usp->transitions;
	stateno *	   row = ut->state;
	int		   n_redundant = 0;
	stateno		   n, m, t, new_n, new_m;
	stateno		   max_transition = ut->max_stateno();

	// first, find redundant entries. List them.
	memset( delvector, 0, (max_transition+1)*sizeof(char) );
	new_n = 0;
	for ( n = 0 ; n < max_transition ; n++ ){
		if ( delvector[n] )
			continue; // already detected as redundant!!
		t = row[n];
		new_m = new_n+1;
		for ( m = n+1; m <= max_transition ; m ++ ){
			if ( delvector[m] )
				continue;
			if (row[m] == t ){
				// the same
				delvector[m] = 1; // mark as redundant
				map->remap( new_m, new_n ); // change mapping.
				n_redundant ++;
			} else {
				new_m += 1; // not the same
			}
		}
		new_n += 1;
	}
	// get rid of those redundant entries
	ut->delete_transitions( delvector );

	return n_redundant;
}

/*
 * See if this is a degenerate unary_symbol: i.e. one with only one
 * non-error transition state. If so, mark it as functionally terminal
 * and give it a terminal_transition table.
 */
void
error_compress_unary_transition(
	unary_symbol *usp )
{
	statemap * 	   map = & usp->lhs_map;
	unary_transition * ut  = usp->transitions;
	stateno *	   row = ut->state;
	int		   found_non_error_state = 0;
	stateno		   n, t, non_error_state = 0; 
	stateno		   max_transition = ut->max_stateno();
	leaf_transition *  lt;

	for ( n = 0 ; n <= max_transition ; n++ ){
	    t = row[n];
	    if ( t == NULL_STATE )
		continue;
	    if ( found_non_error_state ){
		if ( t != non_error_state ){
		    return; // non-degenerate map. Cannot compress
		}
	    } else {
		found_non_error_state = 1;
		non_error_state = t;
	    }
	}
	// made it through the loop finding (at most) one non-error state.
	// this is a degenerate symbol. Mark it so and give it a terminal_transition.
	usp->set_functional_type( symbol::terminal );
	ut->free();
	lt = leaf_transition::newtransition( (terminal_symbol*) usp );
	lt->state = non_error_state;
	usp->transitions = (unary_transition*)lt;
	if (DEBUG(COMPRESS) && n != 0 ){
	    printf("Error compression reduced unary %s to functionally terminal\n",
		usp->name() );
	}

}

/*
 * Squeeze redundance out of a binary transition table.
 * Simply look for identical row or columns, and delete them,
 * while remapping the states.
 * Pretty brute-force sort of algorithm used here.
 *
 * We are provided with temp vectors allocated for our use,
 * since the same can be used for each transition table being
 * compressed, we save a little allocation time.
 */

static int
compress_binary_transition_row(
	binary_symbol *bsp,
	char *  delvector )
{
	statemap * 	   map = & bsp->lhs_map;
	binary_transition * bt  = bsp->transitions;
	binary_transition_row *	   rows = bt->state;
	int		   n_redundant = 0;
	stateno		   n, m, new_n, new_m;
	stateno *	   t;
	stateno		   max_transition = bt->row_max_stateno();
	int		   row_size;

	row_size = (bt->col_max_stateno()+1)*sizeof(stateno);
	// first, find redundant entries. List them.
	memset( delvector, 0, (max_transition+1)*sizeof(char) );
	new_n = 0;
	for ( n = 0 ; n < max_transition ; n++ ){
		if ( delvector[n] != 0 )
			continue; // already detected as redundant!!
		t = rows[n].state;
		new_m = new_n + 1;
		for ( m = n+1; m <= max_transition ; m ++ ){
			if ( delvector[m] )
				continue; // already dead
			if (
			    memcmp( rows[m].state, t, row_size ) == 0
			){
				delvector[m] = 1; // mark as redundant
				// change mapping.
				// (map has already renumbered to
				// compensate for previously removed
				// rows, so we must compensate, too.)
				map->remap( new_m, new_n );
				n_redundant ++;
			} else {
				new_m += 1;
			}
		}
		new_n += 1;
	}
	// get rid of those redundant entries
	bt->delete_transition_rows( delvector );

	return n_redundant;
}

static int
compress_binary_transition_col(
	binary_symbol *bsp,
	char *  delvector )
{
	statemap * 	   map = & bsp->rhs_map;
	binary_transition * bt  = bsp->transitions;
	binary_transition_row *	   rows = bt->state;
	int		   n_redundant = 0;
	stateno		   n, m, new_n, new_m;
	stateno		   max_transition = bt->col_max_stateno();
	register int	   col_size = bt->row_max_stateno();
	int		   col_same;
	register int 	   c;

	// first, find redundant entries. List them.
	memset( delvector, 0, (max_transition+1)*sizeof(char) );
	new_n = 0;
	for ( n = 0 ; n < max_transition ; n++ ){
		if ( delvector[n] != 0 )
			continue; // already detected as redundant!!
		new_m = new_n +1;
		for ( m = n+1; m <= max_transition ; m ++ ){
			if ( delvector[m] )
				continue; // already dead
			col_same = 1;
			for ( c = 0 ; c <= col_size; c++ ){
				// compare the difficult way.
				// NOTE: We might want optimization here.
				if ( rows[c].state[m] != rows[c].state[n] ){
					col_same = 0;
					break;
				}
			}
			if ( col_same ){
				delvector[m] = 1; // mark as redundant
				// change mapping.
				// (map has already renumbered to
				// compensate for previously removed
				// cols, so we must compensate, too.)
				map->remap( new_m, new_n );
				n_redundant ++;
			} else {
				new_m += 1;
			}
		}
		new_n += 1;
	}
	// get rid of those redundant entries
	bt->delete_transition_cols( delvector );

	return n_redundant;
}

static int
map_is_degenerate( statemap *    map )
{
	stateno max_mapped = map->max_ordinate();
	stateno m, t, non_error_value = 0;
	int	found_non_error_value = 0;
	for ( m = 0; m < max_mapped; m++ ){
		t = (*map)[m];
		if ( t == NULL_STATE )
		    continue;
		if ( found_non_error_value ){
		    if ( t != non_error_value )
			return 0; // more than one non-error mapping here.
		} else {
		    found_non_error_value = true;
		    non_error_value = t;
		}
	}
	return 1;
}

static void
error_compress_binary_transition(
	binary_symbol *bsp )
{
	binary_transition * bt  = bsp->transitions;
	binary_transition_row *	   rows = bt->state;
	int		   found_non_error_state = 0;
	stateno		   n, m, t, non_error_state =0;
	stateno		   max_transition = bt->col_max_stateno();
	register int	   col_size = bt->row_max_stateno();
	leaf_transition *  lt;
	statemap * 	   map;
	unary_transition * ut;
	stateno		   maxmapped;

	for ( n = 0 ; n <= max_transition ; n++ ){
		for ( m = 0; m <= col_size ; m ++ ){
			t = rows[m].state[n];
			if ( t == NULL_STATE )
			    continue;
			if ( found_non_error_state ){
			    if ( t != non_error_state ){
				goto try_unary; // transitions not totally degenerate.
			    }
			} else {
			    found_non_error_state = 1;
			    non_error_state = t;
			}
		}
	}
	// made it through the loop finding (at most) one non-error state.
	// this degenerates to a terminal.
	bsp->set_functional_type( symbol::terminal );
	bt->free();
	lt = leaf_transition::newtransition( (terminal_symbol*) bsp );
	lt->state = non_error_state;
	bsp->transitions = (binary_transition*)lt;
	if (DEBUG(COMPRESS) && n != 0 ){
	    printf("Error compression reduced binary %s to functionally terminal\n",
		bsp->name() );
	}
	return;
try_unary:
#if 0
	/*
	 * This is not debugged: in fact I think I've confused rows and
	 * columns. In any case, there are few instances where it helps.
	 */
	/*
	 * Here, we know that this is not a totally trivial transition.
	 * It may degenerate to unary though. Look at the mapping vectors, and
	 * if either of them is degenerate, then this symbol is unary in the 'other'
	 * dimension.
	 */
	/* first the RHS map */
	if ( map_is_degenerate( & bsp->rhs_map )){
	    stateno *nsp;
	    stateno  m, mmax;
	    /* all columns are the same. (or error) choose one
	     * to make into a one-row unary transition. use the lhs_map as is.
	     */
	    bsp->set_functional_type( symbol::unaryop );
	    ut = unary_transition::newtransition( (unary_symbol*) bsp );
	    ut->grow( mmax = bsp->lhs_map.max_mapping() );
	    nsp = ut->state;
	    for ( m = 0; m <= mmax; m++ ){
		nsp[m] = bt->state[m].state[1];
	    }
	    bsp->transitions = (binary_transition*)ut;
	    bt->free();
	    bsp->rhs_map.destruct();
	    if (DEBUG(COMPRESS) && n != 0 ){
		printf("Error compression reduced binary %s to functionally left-unary\n",
		    bsp->name() );
	    }
	    return;
	} else if ( map_is_degenerate( & bsp->lhs_map )){
	    stateno *nsp;
	    stateno  m, mmax;
	    /* all rows are the same. (or error) choose one
	     * to make into a one-row unary transition. replace lhs_map with rhs_map;
	     */
	    bsp->set_functional_type( symbol::rightunaryop );
	    ut = unary_transition::newtransition( (unary_symbol*) bsp );
	    ut->grow( mmax = bsp->rhs_map.max_mapping() );
	    nsp = ut->state;
	    for ( m = 0; m <= mmax; m++ ){
		nsp[m] = bt->state[1].state[m];
	    }
	    bsp->transitions = (binary_transition*)ut;
	    bt->free();
	    bsp->lhs_map.destruct();
	    bsp->lhs_map = bsp->rhs_map;
	    if (DEBUG(COMPRESS) && n != 0 ){
		printf("Error compression reduced binary %s to functionally right-unary\n",
		    bsp->name() );
	    }
	    return;
	}
#else
	(void)0;
#endif
}

static int
compress_transitions()
{

	char * bool_temp;
	symbollist_iterator  sl_i;
	symbol * sp;
	int maxstate = allstates.n() -1;
	int n;
	int n_sum;

	// allocate up temporary for use by all callees.
	// can never need more that total number of states.
	bool_temp = (char *)malloc( allstates.n() );
	assert( bool_temp != 0 );

	n_sum = 0;
	sl_i = all_symbols;