/**CFile***********************************************************************

  FileName    [ ioWriteBlifUtil.c ]

  PackageName [ io ]

  Synopsis    [ This file contains blifmv -> blif write routines, which perform
                miscellaneous lower-level functions ]

  Description [ Routines that perform lower-level tasks in the determinizing, 
                encoding and) writing a blifmv table into a blif description 
                are included in this file]

  SeeAlso     [ ioReadBlifmv.c, ioWriteBlif.c, ioWriteBlifIo.c]

  Author      [ Sunil P. Khatri ]

  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, provided that the above copyright notice and
  the following two paragraphs appear in all copies of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

******************************************************************************/

#include "ioInt.h"

static char rcsid[] UNUSED = "$Id: ioWriteBlifUtil.c,v 1.12 2005/05/14 02:15:22 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void _IoWriteEntryToTable(Tbl_Entry_t *entry, Tbl_Table_t *table, int row, int col, int output);
static void _IoWriteValueToTable(int value, Tbl_Table_t *table, int row, int col, int output);
static Tbl_Table_t *_IoTableRemoveEqualsContruct(Tbl_Table_t *origBlifmvTable, array_t *freeVarArray, int verbosity);
static void _IoVarEncEntryFree(IoVarEncEntry_t *varEnc);
static int _IoNumValues(int colnum, array_t *numValuesArray);
static Tbl_Entry_t *_IoCreateBinRange(array_t *mvEntryBinRanges, Tbl_Entry_t *entry, int numBits, int runLength, int skipLength);
static boolean _IoEntryCheckRange(Tbl_Entry_t *entry, int startValue, int runLength, int skipLength);
static Tbl_Entry_t *_IoAddBinRange(array_t *mvEntryBinRanges, Tbl_Entry_t *entry, int startValue, int runLength, int skipLength);

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


/**Function***********************************************************


  Synopsis	[ Makes a single output table for the outputNum'th output]

  Description	[ Allows for ='s in output entries to refer only to input vars ]

  SideEffects	[ ]

  SeeAlso	[  ]
************************************************************************/
Tbl_Table_t *
IoMakeSingleOutputTable(
  Tbl_Table_t *table,
  int outputNum
  )
{
    Tbl_Table_t * tableDup;
    int i, j, numRows, numCols;
    Tbl_Entry_t *newEntry, *entry, *parentVarEntry;
    Var_Variable_t *var;
    
    tableDup = Tbl_TableAlloc();
    numRows = Tbl_TableReadNumRows(table);
    numCols = Tbl_TableReadNumInputs(table);
    
    Tbl_TableForEachInputVar(table,i,var){
	Tbl_TableAddColumn(tableDup,var,0);
    }
    
    var = Tbl_TableReadIndexVar(table,outputNum,1);
    Tbl_TableAddColumn(tableDup,var,1);
    
    entry = Tbl_TableDefaultReadEntry(table,outputNum);
    if (entry != NIL(Tbl_Entry_t)){
	if(Tbl_EntryReadType(entry) != Tbl_EntryNormal_c){
	    var = Tbl_EntryReadVar(table, entry);
	    j = Tbl_TableReadVarIndex(table, var, 1);
	    parentVarEntry = Tbl_TableDefaultReadEntry(table, j);
	    newEntry = Tbl_EntryDup(parentVarEntry);
	}
	else{
	    newEntry = Tbl_EntryDup(entry);
	}
    }
    else {
	newEntry = NIL(Tbl_Entry_t);
    }
    (void) Tbl_TableDefaultSetEntry(tableDup,newEntry,0);
    
    for(i = 0; i < numRows; i++){
	(void) Tbl_TableAddRow(tableDup);
	for(j = 0; j < numCols; j++){
	    entry = Tbl_TableReadEntry(table, i, j, 0);
	    newEntry = Tbl_EntryDup(entry);
	    Tbl_TableSetEntry(tableDup, newEntry, i, j, 0);
	}
	entry = Tbl_TableReadEntry(table, i, outputNum, 1);
	newEntry = Tbl_EntryDup(entry);
	Tbl_TableSetEntry(tableDup, newEntry, i, 0, 1);
    }
    return tableDup;
}



/**Function***********************************************************

  Synopsis	[ Checks if the number of rows after expansion, due to the 
                  outputs = expansion, is more than a given threshold.]

  Description	[ Allows for ='s in output entries to refer only to input
  vars ]

  SideEffects	[ ]

  SeeAlso	[ ]

************************************************************************/
boolean
IoOutputExpansionRequired(
  Tbl_Table_t *table
  )
{
    int numRows, numOutputs, i, colnum, parentVarIndex;
    Tbl_Entry_t *entry;
    Var_Variable_t *parentVar;

    /* previously used to find out the estimated size of the resulting binary 
       table (in number of entries) and return TRUE if this number was greater
       than 250. Removed this check, and now return TRUE if the table is multi-
       output. This is at the cost of potentially increasing runtime.
    */
    /* if any of the output entries has an =var where var is another output
       variable, then output splitting is not done */

    numRows = Tbl_TableReadNumRows(table);
    numOutputs = Tbl_TableReadNumOutputs(table);

    for(i = 0; i < numRows; i++){
	for(colnum = 0; colnum < numOutputs; colnum++){
	    entry = Tbl_TableReadEntry(table, i, colnum, 1);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		parentVar = Tbl_EntryReadVar(table, entry);
		parentVarIndex = Tbl_TableReadVarIndex(table, parentVar, 0);
		if(parentVarIndex == -1){
		  fprintf(vis_stderr, "Output entry mimics another output with an '=' construct - error\n");
		  assert(parentVarIndex != -1);
		}
	    }
	}
    }
    if(numOutputs > 1){
      return TRUE;
    }
    return FALSE;
}
    
/**Function********************************************************************

  Synopsis    [Initializes IoBlifInfo_t data structure]

  Description [] 

  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoInitBlifInfo(
   IoBlifInfo_t *blifInfo, 
   Tbl_Table_t *origBlifmvTable,
   FILE *fp,
   FILE *encFp,
   int verbosity
   )
{
    blifInfo->varArray = array_alloc(Var_Variable_t *, 0);
    blifInfo->blifmvTable = _IoTableRemoveEqualsContruct(origBlifmvTable, blifInfo->varArray, verbosity);
    blifInfo->binTable = Tbl_TableAlloc();
    blifInfo->inputEncTblArray = array_alloc(IoVarEncEntry_t *, 0);
    blifInfo->outputEncTblArray = array_alloc(IoVarEncEntry_t *, 0);
    blifInfo->dcTblArray = array_alloc(Tbl_Table_t *, 0);
    blifInfo->verbosity = verbosity;
    blifInfo->pseudoinputFlag = FALSE;
    blifInfo->BlifFp = fp;
    blifInfo->EncFp = encFp;
}


/**Function********************************************************************

  Synopsis    [Frees IoBlifInfo_t data structure]

  Description [ ] 

  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoFreeBlifInfo(
   IoBlifInfo_t *blifInfo
   )
{
    int i;

    Tbl_TableFree(blifInfo->blifmvTable);
    Tbl_TableFree(blifInfo->binTable); 

    for(i=0; i < array_n(blifInfo->inputEncTblArray); i++){
	_IoVarEncEntryFree(array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i));
    }
    array_free(blifInfo->inputEncTblArray);

    for(i=0; i < array_n(blifInfo->outputEncTblArray); i++){
	_IoVarEncEntryFree(array_fetch(IoVarEncEntry_t *, blifInfo->outputEncTblArray, i));
    }
    array_free(blifInfo->outputEncTblArray);

    for(i=0; i < array_n(blifInfo->varArray); i++){
	Var_VariableFree(array_fetch(Var_Variable_t *, blifInfo->varArray, i));
    }
    array_free(blifInfo->varArray);

    for(i=0; i < array_n(blifInfo->binTblArray); i++){
	Tbl_TableFree(array_fetch(Tbl_Table_t *, blifInfo->binTblArray, i));
    }
    array_free(blifInfo->binTblArray);

    for(i=0; i < array_n(blifInfo->dcTblArray); i++){
	Tbl_TableFree(array_fetch(Tbl_Table_t *, blifInfo->dcTblArray, i));
    }
    array_free(blifInfo->dcTblArray);
    FREE(blifInfo);
      
}


/**Function********************************************************************

  Synopsis    [Determines if a variable is a PI/PO of an hnode. ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
boolean		
IoVarIsHnodePIO(
  Hrc_Node_t *hnode, 
  Var_Variable_t *var
  )
{
    boolean test;
    
    test = FALSE;
    if(Var_VariableTestIsPO(var) || Var_VariableTestIsPI(var) || Var_VariableTestIsSO(var) || Var_VariableTestIsSI(var)){
	test = TRUE;
    }
    return test;
}


/**Function********************************************************************

  Synopsis    [Encodes individual variable based on its ranges]

  Description [Returns encoding as an entry in the array of encodings' tables]

  SideEffects [Populates a table in the array of tables describing the IO encodings]

  SeeAlso     []

******************************************************************************/
void
IoEncodeVariable(
   IoBlifInfo_t *blifInfo,
   Var_Variable_t *var,
   int varNum,		 
   int output
   )
{
    int range, numEncBits;
    IoVarEncEntry_t *varEncEntry;

    range = Var_VariableReadNumValues(var);
    numEncBits = IoNumEncBits(range);
    
    varEncEntry = ALLOC(IoVarEncEntry_t, 1);
    varEncEntry->variable = Var_VariableDup(var, NIL(Hrc_Node_t));
    varEncEntry->index = varNum;
    varEncEntry->numEncBits = numEncBits;
    if(output == 1){
	array_insert_last(IoVarEncEntry_t *, blifInfo->outputEncTblArray, varEncEntry);
    }
    else{
	array_insert_last(IoVarEncEntry_t *, blifInfo->inputEncTblArray, varEncEntry);
    }

}


/**Function********************************************************************

  Synopsis    [Returns number of bits in encoding]

  Description [Returns n such that 2^n >= range of the variable ]

  SideEffects []

  SeeAlso     []

******************************************************************************/
int
IoNumEncBits(
   int n
   )
{
    int i=0;
    int j=1;

    if (n<2){
	return 1;
    }
    else{
	while (j < n){
	    j = j * 2;
	    i++;
	}
    }
    return i;

}

/**Function********************************************************************

  Synopsis    [Returns the number of digits in the base 10 representation of a number]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
int 
IoNumDigits(
   int n
   )
{
    double j;
    
    j = log10((double) n) + 1;
    return ((int) j);
}

/**Function********************************************************************

  Synopsis    [Returns log-base-2 of a number which is a power of 2]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
int
IoLog(
   int n
   )
{
    int i=0;
    int j=1;

    while (j < n){
	j = j * 2;
	i++;
    }
    return i;
}


/**Function********************************************************************

  Synopsis    [Returns the IoVarEncEntry_t with the smallest encoding length]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
IoVarEncEntry_t *
IoFindSmallestCode( 
   IoBlifInfo_t *blifInfo
   )
{
    int i, smallestCode, index;
    IoVarEncEntry_t *varEnc;

    index = -1;
    smallestCode = VIS_INFINITY;
    for(i = 0; i < array_n(blifInfo->inputEncTblArray); i++){
	varEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i);
	if((Var_VariableReadNumValues(varEnc->variable)) < smallestCode){
	    smallestCode = Var_VariableReadNumValues(varEnc->variable);
	    index = i;
	}
    }
    
    assert(index != -1);
    varEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, index);
    return varEnc;

}

/**Function********************************************************************

  Synopsis    [Increases the code size of a variable]

  Description [Invoked when a output for a row has multiple values. To determinize 
               this scenario, an input has pseudovariables appended to its code. The
	       number of pseudoinputs = log(n) where n is the number of values of the
	       output]

  SideEffects [alters encoding of mv variables]

  SeeAlso     []

******************************************************************************/
void
IoIncreaseCodeSize(
  IoVarEncEntry_t *varEnc, 
  int numValues,
  int verbosity		  
  )
{
    int temp1, temp2, range, numAddedPseudovars, numExpand;

    range = Var_VariableReadNumValues(varEnc->variable);
    numAddedPseudovars = IoNumEncBits(numValues);
    temp1 = ((int) pow((double) 2, (double)numAddedPseudovars)) - 1;
    temp2 = (int) pow((double) 2, (double)varEnc->numEncBits);
    numExpand = (temp1 * temp2) + range;
    if(verbosity > 2){
	(void)fprintf(stdout, "New Number of Values for the variable = %d\n", numExpand);
    }
    Var_VariableExpandRange(varEnc->variable, numExpand);
	

}


/**Function********************************************************************

  Synopsis    [Alters blifmv table to reflect the increase in code size from IoIncreaseCodeSize]

  Description []
               
  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoChangeBlifmvTableRows(
   IoBlifInfo_t *blifInfo,		 
   IoVarEncEntry_t *varEnc, 
   int row1,
   int row2
  )
{
    int numCurrentBits, i, numRows, colnum, tempCol, reqdColnum;
    Tbl_Entry_t *entry;
    char *varname, *dupName;
    Var_Variable_t *newVar;
    IoVarEncEntry_t *tempVarEnc;

    /* add a new column to bin table */
    numCurrentBits = varEnc->numEncBits;
    varname = Var_VariableReadName(varEnc->variable);
    dupName = ALLOC(char, strlen(varname) + IoNumDigits(numCurrentBits) + 2);
    sprintf(dupName, "%s%d", varname, numCurrentBits);
    newVar = Var_VariableAlloc(NIL(Hrc_Node_t), dupName);
    FREE(dupName);
    array_insert_last(Var_Variable_t *, blifInfo->varArray, newVar);
    colnum = Tbl_TableAddColumn(blifInfo->binTable, newVar, 0);
    numRows = Tbl_TableReadNumRows(blifInfo->binTable);
    for(i = 0; i < numRows; i++){
	entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
	if(i == row1){
	    Tbl_EntrySetValue(entry, 0, 0);
	}
	if(i == row2){
	    Tbl_EntrySetValue(entry, 1, 1);
	}
	if((i != row1) && (i != row2)){
	    Tbl_EntrySetValue(entry, 0, 1);
	}
	Tbl_TableSetEntry(blifInfo->binTable, entry, i, colnum - 1, 0);
    }
    tempCol = 0;
    reqdColnum = -1;
    for(i = 0; i < array_n(blifInfo->inputEncTblArray); i++){
	tempVarEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i);
	if(tempVarEnc == varEnc){
	    reqdColnum = tempCol + varEnc->numEncBits;
	}
	tempCol += tempVarEnc->numEncBits;
    }
    colnum--;    
    assert(reqdColnum != -1);
    while(reqdColnum < colnum){
	Tbl_TableSwapColumns(blifInfo->binTable, colnum, colnum - 1, 0);
	colnum--;
    }
}


/**Function********************************************************************

  Synopsis    [Alters table to reflect the increase in code size from IoIncreaseCodeSize]

  Description []
               
  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoChangeBlifmvTableEntries(
   IoBlifInfo_t *blifInfo,
   int rownum,
   int numValues,
   IoVarEncEntry_t *varEnc, 
   array_t *MvOutputArray
  )
{
    int i, j, k, newrownum, colnum, inputColnumToChange, value, offset;
    int numInputs, numOutputs, entryRepetitionCount, numCycles, numNewBits, maxValue, numOldBits;
    Tbl_Entry_t *entry, *dupEntry;
    lsGen gen;
    Tbl_Range_t *range;

    numInputs = Tbl_TableReadNumInputs(blifInfo->blifmvTable);
    numOutputs = Tbl_TableReadNumOutputs(blifInfo->blifmvTable);
    numNewBits = IoNumEncBits(numValues);
    numOldBits = varEnc->numEncBits;
    maxValue = (int) pow((double) 2, (double)(numNewBits + numOldBits));

    inputColnumToChange = varEnc->index;
    for(i = 0; i < Tbl_TableReadNumRows(blifInfo->blifmvTable); i++){
	if (i != rownum){
	    entry = Tbl_TableReadEntry(blifInfo->blifmvTable, i, inputColnumToChange, 0);
	    dupEntry = Tbl_EntryDup(entry);
	    offset = (int) pow((double) 2, (double)varEnc->numEncBits);
	    Tbl_EntryForEachValue(entry, value, gen, range){
		for(j = value ; j < maxValue; j = j + offset){
		    Tbl_EntrySetValue(dupEntry, j, j);
		}
	    }
	    Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, i, inputColnumToChange, 0);
	}
    }
    newrownum = -1;
    for(i = 0; i < numValues; i++){
 
         /* add a row, and duplicate all entries of the original row except for 
            the one that needs a new entry (because of the new code). This entry
            gets code = oldCode + i * (2^numCurrentEncBits)      */

	newrownum = Tbl_TableAddRow(blifInfo->blifmvTable);
	assert(newrownum != -1);
	for(colnum = 0; colnum < numInputs; colnum++){
	    entry = Tbl_TableReadEntry(blifInfo->blifmvTable, rownum, colnum, 0);
	    if(colnum != inputColnumToChange){
		dupEntry = Tbl_EntryDup(entry);
		Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum, colnum, 0);
	    }
	    else{
		dupEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
		offset = i * ((int) pow((double) 2, (double) varEnc->numEncBits));
		Tbl_EntryForEachValue(entry, value, gen, range){
		    Tbl_EntrySetValue(dupEntry, value + offset, value + offset);
		}
		Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum, colnum, 0);
	    }
	}
    }

    /* This section singleton-izes the output entries of the new row. 
       Multiple outputs are accounted for. If more than one output has 
       non-singleton entries, they are all singleton-ized. Finally,
       the original row is deleted...                                       */ 
    
    entryRepetitionCount = numValues;
    numCycles = 1;
    newrownum++;
    
    for(colnum = 0; colnum < numOutputs; colnum++){
	newrownum = newrownum - numValues;
	numCycles *= _IoNumValues(colnum, MvOutputArray);
	entryRepetitionCount /= array_fetch(int, MvOutputArray, colnum);
	entry = Tbl_TableReadEntry(blifInfo->blifmvTable, rownum, colnum, 1);
	for(j = 0; j < numCycles; j++){
	    Tbl_EntryForEachValue(entry, value, gen, range){
		for(k = 0; k < entryRepetitionCount; k++){
		    dupEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);			
		    Tbl_EntrySetValue(dupEntry, value, value);	     
		    Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum++, colnum, 1);
		}
	    }
	}
    }
    blifInfo->blifmvTable = Tbl_TableRowDelete(blifInfo->blifmvTable, rownum, blifInfo->varArray); 
}


/**Function********************************************************************

  Synopsis    [Alters table to reflect the increase in code size from IoIncreaseCodeSize]

  Description []
               
  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoChangeEncTableEntries(
   IoBlifInfo_t *blifInfo,		 
   st_table *blifInputsStTable,
   IoVarEncEntry_t *varEnc, 
   int numValues
  )
{
    int numOrigBits, numAddedBits, i;
    char *varname, *dupName;
    
    numAddedBits = IoNumEncBits(numValues);
    numOrigBits = varEnc->numEncBits;

    varname = Var_VariableReadName(varEnc->variable);
    for(i=0; i<numAddedBits; i++){
	dupName = ALLOC(char, strlen(varname) + IoNumDigits(numAddedBits + numOrigBits)+ 2);
	sprintf(dupName, "%s%d", varname, i + numOrigBits);
	if(!st_is_member(blifInputsStTable, (char *)dupName)){
	    (void)fprintf(blifInfo->BlifFp, ".inputs %s\n", dupName);
	    if(blifInfo->pseudoinputFlag == FALSE){
		(void)fprintf(blifInfo->EncFp, ".table %s\n", dupName);
		(void)fprintf(blifInfo->EncFp, "-\n");
	    }
	    st_insert(blifInputsStTable, (char *)dupName, (char *)1);
	}
	else{
	    FREE(dupName);
	}
    }
    varEnc->numEncBits += numAddedBits;

}




/**Function********************************************************************

  Synopsis    [Inverts a specified binary output of binTable]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
void
IoInvertBinTableOutput(
   IoBlifInfo_t * blifInfo,
   int colnumToInvert
   )
{
    int i;
    char *name, *newname;
    Var_Variable_t *var;
    
    var = Tbl_TableReadIndexVar(blifInfo->binTable, colnumToInvert, 1);
    name = Var_VariableReadName(var);
    newname = ALLOC(char, strlen(name) + 4);
    sprintf(newname, "%s_b", name);
    (void)fprintf(blifInfo->BlifFp, ".names %s %s\n", newname, name);
    (void)fprintf(blifInfo->BlifFp, "0 1\n");
    Var_VariableChangeName(var, newname);
    FREE(newname);
    for(i = 0; i < Tbl_TableReadNumRows(blifInfo->binTable); i++){
	Tbl_TableComplementEntry(blifInfo->binTable, i, colnumToInvert, 1);
    }
}


/**Function********************************************************************

  Synopsis    [Returns array that represents a simple way of compacting a mv 
               entry while representing it in binary.]

  Description [The array contains IoBinRangeEntry_t *'s. Each item of the array represents
               a starting value and a run length and a skip length. The union of all such values contains
               exactly the values of the entry passed]

  SideEffects []

  SeeAlso     []

******************************************************************************/
array_t *
IoMakeBinaryRangesArray(
   Tbl_Entry_t *entry,
   int colnum,
   IoBlifInfo_t *blifInfo		       
   )
{
    array_t *mvEntryBinRanges;
    int i, j, numBits, runLength, skipLength;
    
    mvEntryBinRanges = array_alloc(IoBinRangeEntry_t *, 0);
    numBits = IoNumBinVars(colnum + 1, blifInfo->inputEncTblArray);
    for(i = numBits; i > 0; i--){
	for(j = 0; j < numBits; j++){
	    runLength = (int) pow((double) 2, (double) i);
	    skipLength = (int) pow((double) 2, (double) j);
	    if((runLength * skipLength) <= (int) pow((double) 2, (double) numBits)){
/*		fprintf(stdout, "run %d, skip %d\n", runLength, skipLength); */
		entry = _IoCreateBinRange(mvEntryBinRanges, entry, numBits, runLength, skipLength);
	    }
	}
    }
    entry = _IoCreateBinRange(mvEntryBinRanges, entry, numBits, 1, 1);	    
    assert(Tbl_EntryReadNumValues(entry) == 0);
    Tbl_EntryFree(entry);
    return mvEntryBinRanges;
}


/**Function********************************************************************

  Synopsis    [Returns the number of values in the entrycolnum-1) ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
int
IoNumValuesFromBinRangesArray( 
   int colnum,
   array_t *binRangesArray
   )
{
    array_t *mvEntryBinRanges;

    if(colnum == 0){
	return 1;
    }
    else{
	mvEntryBinRanges = array_fetch(array_t *, binRangesArray, colnum - 1);
	return(array_n(mvEntryBinRanges));
    }
}


/**Function********************************************************************

  Synopsis    [Returns the number of binary vars in the variable index (colnum-1) ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
int
IoNumBinVars( 
   int colnum,
   array_t *encTblArray
   )
{
    IoVarEncEntry_t *varEnc;
    
    if(colnum == 0){
	return 0;
    }
    else{
	varEnc = array_fetch(IoVarEncEntry_t *, encTblArray, colnum-1);
	return(varEnc->numEncBits);
    }
}

    
/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/


/**Function********************************************************************

  Synopsis    [Duplicate an entry and set it  in a table]

  Description [] 

  SideEffects []

  SeeAlso     []

******************************************************************************/
static void
_IoWriteEntryToTable(
   Tbl_Entry_t *entry, 
   Tbl_Table_t *table, 
   int row, 
   int col, 
   int output
)
{
    Tbl_Entry_t *dupEntry;
    
    dupEntry = Tbl_EntryDup(entry);
    Tbl_TableSetEntry(table, dupEntry, row, col, output);
}


/**Function********************************************************************

  Synopsis    [Make an entry from a value, and set it  in a table]

  Description [] 

  SideEffects []

  SeeAlso     []

******************************************************************************/
static void
_IoWriteValueToTable(
   int value, 
   Tbl_Table_t *table, 
   int row, 
   int col, 
   int output
)
{
    Tbl_Entry_t *entry;
    
    entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
    Tbl_EntrySetValue(entry, value, value);
    Tbl_TableSetEntry(table, entry, row, col, output);
}

/**Function********************************************************************

  Synopsis    [Removes "=" constructs in a table]

  Description [] 

  SideEffects []

  SeeAlso     []

******************************************************************************/
static Tbl_Table_t *
_IoTableRemoveEqualsContruct(
   Tbl_Table_t *origBlifmvTable,
   array_t *freeVarArray,
   int verbosity
   )
{
    Tbl_Table_t *resultTable;
    int numRows, numInputs, numOutputs, numRowsAfterExpansion, i, j, k, colnum, rownum, currRow, value;
    int parentVarnumValues, parentVarIndex, rootRow, entryRepetitionCount ;
    st_table *parentsStTable;
    Tbl_Entry_t *entry, *parentVarEntry, *dupEntry;
    Var_Variable_t *parentVar, *var;
    boolean parentVarIsOutput, rowContainsEqualEntries, insertedI;
    st_generator *gen;
    Tbl_Range_t *range;
    lsGen listgen;
    array_t *rowDeleteArray;
    char *dummy;

    resultTable = Tbl_TableHardDup(origBlifmvTable);
    /* remove "="s in original defaults table*/
    for(i = 0; i < Tbl_TableReadNumOutputs(resultTable); i++){
	entry = Tbl_TableDefaultReadEntry(resultTable, i);
	if(entry != NIL(Tbl_Entry_t)){
	    if(Tbl_EntryReadType(entry) != Tbl_EntryNormal_c){
		var = Tbl_EntryReadVar(resultTable, entry);
		j = Tbl_TableReadVarIndex(resultTable, var, 1);
		parentVarEntry = Tbl_TableDefaultReadEntry(resultTable, j);
		dupEntry = Tbl_EntryDup(parentVarEntry);
		Tbl_TableDefaultSetEntry(resultTable, dupEntry, i);
		Tbl_EntryFree(entry);
	    }
	}
    }

    /* first expand all rows with "=" constructs, in the same table */
    numRows = Tbl_TableReadNumRows(resultTable);
    numInputs = Tbl_TableReadNumInputs(resultTable);
    numOutputs = Tbl_TableReadNumOutputs(resultTable);
    rootRow = numRows;

    for(i = 0; i < numRows; i++){
	numRowsAfterExpansion = 1;
	rowContainsEqualEntries = FALSE;	
	parentsStTable = st_init_table(st_ptrcmp, st_ptrhash);

	/* find variables that are parent variables, ie variables 'var' that
           have =var references in that row of the table    */
	for(colnum = 0; colnum < numInputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		rowContainsEqualEntries = TRUE;
		parentVar = Tbl_EntryReadVar(resultTable, entry);
		st_insert(parentsStTable, (char *) parentVar, (char *) 1);
	    }
	}
	for(colnum = 0; colnum < numOutputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		rowContainsEqualEntries = TRUE;
		parentVar = Tbl_EntryReadVar(resultTable, entry);
		st_insert(parentsStTable, (char *) parentVar, (char *) 1);
	    }
	}
	if(rowContainsEqualEntries == FALSE){
	    st_free_table(parentsStTable);
	    continue;
	}
	
	/* find the number of rows after expansion */
	st_foreach_item(parentsStTable, gen, &parentVar, &dummy){
	    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
	    if(parentVarIndex != -1){
		parentVarIsOutput = 0;
	    }
	    else{
		parentVarIsOutput = 1;
		parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);		
	    }
	    parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex, parentVarIsOutput);
	    numRowsAfterExpansion *= Tbl_EntryReadNumValues(parentVarEntry);
	}

	/* write out expanded form of this row */
	for(j = 0; j < numRowsAfterExpansion; j++){
	    Tbl_TableAddRow(resultTable);
	}
	/* expand parent variables first */
	entryRepetitionCount = numRowsAfterExpansion;
	st_foreach_item(parentsStTable, gen, &parentVar, &dummy){
	    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
	    if(parentVarIndex != -1){
		parentVarIsOutput = 0;
	    }
	    else{
		parentVarIsOutput = 1;
		parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);		
	    }
	    parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
						  parentVarIsOutput);
	    parentVarnumValues = Tbl_EntryReadNumValues(parentVarEntry);
	    currRow = rootRow;
	    entryRepetitionCount = entryRepetitionCount / parentVarnumValues;
	    while(currRow < rootRow + numRowsAfterExpansion){
		Tbl_EntryForEachValue(parentVarEntry, value, listgen, range){	    
		    for(k = 0; k < entryRepetitionCount; k++){
			_IoWriteValueToTable(value, resultTable, currRow, parentVarIndex,
					    parentVarIsOutput);
			currRow++;
		    }
		}
	    }
	}

	/* next expand variables that reference parent vars */
	for(colnum = 0; colnum < numInputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		parentVar = Tbl_EntryReadVar(resultTable, entry);
		parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
		if(parentVarIndex != -1){
		    parentVarIsOutput = 0;
		}
		else{
		    parentVarIsOutput = 1;
		    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);		
		}
		parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
						      parentVarIsOutput);
		for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
		    entry = Tbl_TableReadEntry(resultTable, k, parentVarIndex,
					       parentVarIsOutput);	    
		    _IoWriteEntryToTable(entry, resultTable, k, colnum, 0);
		}
	    }
	    else{
		if(!st_is_member(parentsStTable, (char *) Tbl_TableReadIndexVar(resultTable,
										  colnum, 0))){
		    for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
			_IoWriteEntryToTable(entry, resultTable, k, colnum, 0);
		    }
		}
	    }
	}
	for(colnum = 0; colnum < numOutputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		parentVar = Tbl_EntryReadVar(resultTable, entry);
		parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
		if(parentVarIndex != -1){
		    parentVarIsOutput = 0;
		}
		else{
		    parentVarIsOutput = 1;
		    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);		
		}
		parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
						      parentVarIsOutput);
		for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
		    entry = Tbl_TableReadEntry(resultTable, k, parentVarIndex,
					       parentVarIsOutput);	    
		    _IoWriteEntryToTable(entry, resultTable, k, colnum, 1);
		}
	    }
	    else{
		if(!st_is_member(parentsStTable, (char *) Tbl_TableReadIndexVar(resultTable,
										  colnum, 1))){
		    for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
			_IoWriteEntryToTable(entry, resultTable, k, colnum, 1);
		    }
		}
	    }
	}
	rootRow += numRowsAfterExpansion;
	st_free_table(parentsStTable);
    }
    
    
    /* now delete rows with "=" constructs */
    rowDeleteArray = array_alloc(int, 0);
    for(i = 0; i < numRows; i++){
	insertedI = FALSE;
	for(colnum = 0; colnum < numInputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		if(!insertedI){
		    array_insert_last(int, rowDeleteArray, i);
		    insertedI = TRUE;
		}
	    }
	}
	for(colnum = 0; colnum < numOutputs; colnum++){
	    entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
	    if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
		if(!insertedI){
		    array_insert_last(int, rowDeleteArray, i);
		    insertedI = TRUE;
		}
	    }
	}
    }
    /* array of vars that are to be freed. Since these are called with 
      a NIL(Hrc_Node_t), they need to be freed separately, and kept track 
      of
    */
    for(i = 0; i < array_n(rowDeleteArray); i++){
	rownum = array_fetch(int, rowDeleteArray, i) - i;
	resultTable = Tbl_TableRowDelete(resultTable, rownum, freeVarArray); 
    }
    array_free(rowDeleteArray);


    if(verbosity > 1){
	(void)fprintf(stdout, "Blifmv Table after = removal is\n");
	Tbl_TableWriteBlifMvToFile(resultTable, 0, stdout);
    }
    return resultTable;

}
	

/**Function********************************************************************

  Synopsis    [Frees the IoVarEncEntry_t ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
static void
_IoVarEncEntryFree(
  IoVarEncEntry_t *varEnc
  )
{
    Var_VariableFree(varEnc->variable);
    free(varEnc);
}


/**Function********************************************************************

  Synopsis    [Checks if runLength entries from startValue with skipLength increments are contained in entry
              ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
static boolean
_IoEntryCheckRange(
 Tbl_Entry_t *entry,
 int startValue,
 int runLength,
 int skipLength
 )
{
    boolean startFound;
    int value, i;
    lsGen gen;
    Tbl_Range_t *range;

    startFound = FALSE;
    i = 1;
    Tbl_EntryForEachValue(entry, value, gen, range){
	if(value == startValue){
	    startFound = TRUE;
	}
	if((!startFound) && (value > startValue)){
	    lsFinish(gen);
	    return FALSE;
	}
	if(value == startValue + (i * skipLength)){
	    i++;
	}
	if(value > startValue + (i * skipLength)){
	    lsFinish(gen);
	    return FALSE;
	}
	if(i == runLength){
	    lsFinish(gen);
	    return TRUE;
	}
    }
    return FALSE;
}


/**Function********************************************************************

  Synopsis    [Returns a (startValue, runLength) pair such that the runLength
               is the largest number of contiguous values in entry, starting from 
               startValue]

  Description [adds  a IoBinRangeEntry_t * to the mvEntryBinRanges. Also returns the
               value upto which all values of the entry have been entered in the
	       mvEntryBinRanges.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
static Tbl_Entry_t *
_IoCreateBinRange(
   array_t *mvEntryBinRanges,
   Tbl_Entry_t *entry,
   int numBits,		 
   int runLength,	      
   int skipLength
   )		 
{
    int i, j, bitPos, tempI, numDash, end, numStartValues, startValue;
    array_t *freeBitsArray;

    numDash = IoLog(runLength);
    end = IoLog(skipLength);
    freeBitsArray = array_alloc(int, 0);
    for(i = 0; i < numBits; i++){
	if(i < end){
	    array_insert_last(int, freeBitsArray, i);
	}
	if(i >= end + numDash){
	    array_insert_last(int, freeBitsArray, i);
	}
    }
    numStartValues = (int) pow((double) 2, (double) array_n(freeBitsArray));
    for(i = 0; i < numStartValues; i++){
	startValue = 0;
	tempI = i;
	for(j = array_n(freeBitsArray) - 1; j >= 0; j--){
	    if(tempI >= (int) pow((double) 2, (double) j)){
		bitPos = array_fetch(int, freeBitsArray, j);
		startValue += (int) pow((double) 2, (double) bitPos);
		tempI -= (int) pow((double) 2, (double) j);
	    }
	} 
/*	fprintf(stdout, "trying start %d, run %d, skip %d\n", startValue, runLength, skipLength); */
	if(_IoEntryCheckRange(entry, startValue, runLength, skipLength)){
	    entry = _IoAddBinRange(mvEntryBinRanges, entry, startValue, runLength, skipLength);
	}
    }
    array_free(freeBitsArray);
    return entry;
}

/**Function********************************************************************

  Synopsis    [Enters a (startValue, runLength, skipLength) tuple into the mvEntryBinRanges array]

  Description [adds  a IoBinRangeEntry_t * to the mvEntryBinRanges. ]

  SideEffects []

  SeeAlso     []

******************************************************************************/
static Tbl_Entry_t *
_IoAddBinRange(
   array_t *mvEntryBinRanges,
   Tbl_Entry_t *entry,
   int startValue,
   int runLength,	      
   int skipLength
   )
{
    IoBinRangeEntry_t *binRangeEntry;
    int i, value;
    Tbl_Entry_t *newEntry;
    lsGen gen;
    Tbl_Range_t *range;
    
    binRangeEntry = ALLOC(IoBinRangeEntry_t, 1);
    binRangeEntry->startValue = startValue;
    binRangeEntry->runLength = runLength;
    binRangeEntry->skipLength = skipLength;
    array_insert_last(IoBinRangeEntry_t *, mvEntryBinRanges, binRangeEntry);
    newEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
    i = 0;
    Tbl_EntryForEachValue(entry, value, gen, range){
	if((value == startValue + (i * skipLength)) && (i < runLength)){
	    i++;
	}
	else{
	    Tbl_EntrySetValue(newEntry, value, value);
	}
    }
    Tbl_EntryFree(entry);
    return newEntry;
}


/**Function********************************************************************

  Synopsis    [Returns the number of values in the entrycolnum-1) ]

  Description []

  SideEffects []

  SeeAlso     []

******************************************************************************/
static int
_IoNumValues(
  int colnum,
  array_t *numValuesArray
  )
{
    if(colnum == 0){
	return 1;
    }
    else{
	return(array_fetch(int, numValuesArray, colnum - 1));
    }
}