src/tbl/tblIdentity.c

Go to the documentation of this file.

#include "tblInt.h"

static char rcsid[] UNUSED = "$Id: tblIdentity.c,v 1.1 2009/04/11 07:10:15 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


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


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


boolean
Tbl_TableIsIdentity(
  Tbl_Table_t *table
  )
{
  Var_Variable_t *invar = NIL(Var_Variable_t), *outvar = NIL(Var_Variable_t);
  Var_Variable_t *var;
  int colNum, rowNum;
  Tbl_Entry_t *inputEntry, *outputEntry, *defaultEntry, *cumulative;
  boolean result;
#if 0
  Mvf_Function_t *outMvf, *inMvf, *identMvf;
  array_t *mvarValues;
  array_t *inMvfArray;
  Tbl_Table_t *ident;
#endif

  if (Tbl_TableReadNumInputs(table) != 1) return FALSE;
  if (Tbl_TableReadNumOutputs(table) != 1) return FALSE;

  Tbl_TableForEachInputVar(table,colNum,var) {
    invar = var;
  }

  Tbl_TableForEachOutputVar(table,colNum,var) {
    outvar = var;
  }

  if (!Var_VariablesTestHaveSameDomain(invar,outvar)) return FALSE;

  /* We test the following condition.  If a table specifies a value
   * for all inputs and all rows are consistent with the identity,
   * then the table is an identity.  A normal default declaration is
   * treated as a row whose input and output parts equal the default
   * value.  An equality default declaration is treated like a row
   * with equality output entry and don't care input entry.
   * Completeness and nondeterminism are implicitly tested by this
   * criterion.
   */
  defaultEntry = Tbl_TableDefaultReadEntry(table, 0);
  if (defaultEntry == NIL(Tbl_Entry_t)) {
    cumulative = Tbl_EntryAlloc(Tbl_EntryNormal_c);
  } else if (Tbl_EntryIsEqual(defaultEntry)) {
    cumulative = Tbl_EntryAlloc(Tbl_EntryNormal_c);
    Tbl_EntrySetValue(cumulative, 0, Var_VariableReadNumValues(invar) - 1);
  } else {
    if (Tbl_EntryReadNumValues(defaultEntry) != 1) return FALSE;
    cumulative = Tbl_EntryDup(defaultEntry);
  }
  Tbl_TableForEachOutputEntry(table, rowNum, colNum, outputEntry) {
    Tbl_Entry_t *tmpEntry;
    assert(colNum == 0);
    inputEntry = Tbl_TableReadEntry(table, rowNum, 0, 0);
    assert(!Tbl_EntryIsEqual(inputEntry));
    if (!Tbl_EntryIsEqual(outputEntry)) {
      if (Tbl_EntryReadNumValues(outputEntry) != 1 ||
          !Tbl_EntryTestEqualEntry(outputEntry,inputEntry)) {
        Tbl_EntryFree(cumulative);
        return FALSE;
      }
    }
    tmpEntry = Tbl_EntryMerge(cumulative, inputEntry);
    Tbl_EntryFree(cumulative);
    cumulative = tmpEntry;
  }
  result = Tbl_EntryReadNumValues(cumulative) ==
    Var_VariableReadNumValues(invar);
  Tbl_EntryFree(cumulative);
  return result;

#if 0

  /* Use the MVF sledgehammer.  Only proceed if an mdd manager was
   * passed as argument.
   */

  if (mddMgr == NIL(mdd_manager)) return FALSE;

  /* Create MDD variables for the table inputs. */
  mdd_restart(mddMgr);
  mvarValues = array_alloc(int, 1);
  array_insert_last(int, mvarValues, Var_VariableReadNumValues(invar));
  mdd_create_variables(mddMgr, mvarValues, NIL(array_t), NIL(array_t));
  array_free(mvarValues);

  /*
   * Construct an MVF for each table input. The MVF for column i is the MVF
   * for MDD variable i.
   */
  inMvf = Mvf_FunctionCreateFromVariable(mddMgr, 0);
  inMvfArray = array_alloc(Mvf_Function_t *, 1);
  array_insert_last(Mvf_Function_t *, inMvfArray, inMvf);

  outMvf = Tbl_TableBuildMvfFromFanins(table, 0, inMvfArray, mddMgr);

  /* Build a reference identity.  This can be sped up quite a bit, but
     we are practicing using the tbl package. */
  ident = Tbl_TableAlloc();
  colNum = Tbl_TableAddColumn(ident,invar,0);
  assert(colNum == 1);
  colNum = Tbl_TableAddColumn(ident,outvar,1);
  assert(colNum == 1);
  rowNum = Tbl_TableAddRow(ident);
  assert(rowNum == 0);
  inputEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
  Tbl_EntrySetValue(inputEntry, 0, Var_VariableReadNumValues(invar)-1);
  Tbl_TableSetEntry(ident,inputEntry, 0, 0, 0);
  outputEntry = Tbl_EntryAlloc(Tbl_EntryEqual_c);
  Tbl_EntrySetEqual(outputEntry, 0);
  Tbl_TableSetEntry(ident,outputEntry, 0, 0, 1);

  identMvf = Tbl_TableBuildMvfFromFanins(ident, 0, inMvfArray, mddMgr);
  Mvf_FunctionArrayFree(inMvfArray);
  Tbl_TableFree(ident);
  result = Mvf_FunctionTestIsEqualToFunction(outMvf, identMvf);
  Mvf_FunctionFree(outMvf);
  Mvf_FunctionFree(identMvf);
  return result;
#endif

} /* Tbl_TableIsIdentity */


boolean
Tbl_TableIsInverter(
  Tbl_Table_t *table
  )
{
  Var_Variable_t *invar = NIL(Var_Variable_t), *outvar = NIL(Var_Variable_t);
  Var_Variable_t *var;
  int colNum, rowNum;
  Tbl_Entry_t *inputEntry, *outputEntry, *defaultEntry, *cumulative;
  boolean result;

  if (Tbl_TableReadNumInputs(table) != 1) return FALSE;
  if (Tbl_TableReadNumOutputs(table) != 1) return FALSE;

  Tbl_TableForEachInputVar(table,colNum,var) {
    invar = var;
  }
  if (Var_VariableReadNumValues(invar) != 2 ||
      Var_VariableTestIsSymbolic(invar)) return FALSE;

  Tbl_TableForEachOutputVar(table,colNum,var) {
    outvar = var;
  }
  if (Var_VariableReadNumValues(outvar) != 2 ||
      Var_VariableTestIsSymbolic(outvar)) return FALSE;

  defaultEntry = Tbl_TableDefaultReadEntry(table, 0);
  if (defaultEntry == NIL(Tbl_Entry_t)) {
    cumulative = Tbl_EntryAlloc(Tbl_EntryNormal_c);
  } else if (Tbl_EntryIsEqual(defaultEntry)) {
    return FALSE;
  } else {
    if (Tbl_EntryReadNumValues(defaultEntry) != 1)
      return FALSE;
    cumulative = Tbl_EntryDup(defaultEntry);
    Tbl_EntryComplement(cumulative, 0, 1);
  }
  Tbl_TableForEachOutputEntry(table, rowNum, colNum, outputEntry) {
    Tbl_Entry_t *tmpEntry;
    assert(colNum == 0);
    if (Tbl_EntryIsEqual(outputEntry)) {
      Tbl_EntryFree(cumulative);
      return FALSE;
    }

    inputEntry = Tbl_TableReadEntry(table, rowNum, 0, 0);
    assert(!Tbl_EntryIsEqual(inputEntry));
    if (Tbl_EntryReadNumValues(outputEntry) != 1 ||
        Tbl_EntryTestIntersectEntry(outputEntry,inputEntry)) {
      Tbl_EntryFree(cumulative);
      return FALSE;
    }
    tmpEntry = Tbl_EntryMerge(cumulative, inputEntry);
    Tbl_EntryFree(cumulative);
    cumulative = tmpEntry;
  }
  result = Tbl_EntryReadNumValues(cumulative) == 2;
  Tbl_EntryFree(cumulative);
  return result;

} /* Tbl_TableIsInverter */