source: vis_dev/vis-2.3/src/io/ioWriteBlifUtil.c @ 40

Last change on this file since 40 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 38.2 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ ioWriteBlifUtil.c ]
4
5  PackageName [ io ]
6
7  Synopsis    [ This file contains blifmv -> blif write routines, which perform
8                miscellaneous lower-level functions ]
9
10  Description [ Routines that perform lower-level tasks in the determinizing,
11                encoding and) writing a blifmv table into a blif description
12                are included in this file]
13
14  SeeAlso     [ ioReadBlifmv.c, ioWriteBlif.c, ioWriteBlifIo.c]
15
16  Author      [ Sunil P. Khatri ]
17
18  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
19  All rights reserved.
20
21  Permission is hereby granted, without written agreement and without license
22  or royalty fees, to use, copy, modify, and distribute this software and its
23  documentation for any purpose, provided that the above copyright notice and
24  the following two paragraphs appear in all copies of this software.
25
26  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
27  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
28  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
29  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
32  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
33  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
34  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
35  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
36
37******************************************************************************/
38
39#include "ioInt.h"
40
41static char rcsid[] UNUSED = "$Id: ioWriteBlifUtil.c,v 1.12 2005/05/14 02:15:22 fabio Exp $";
42
43/*---------------------------------------------------------------------------*/
44/* Macro declarations                                                        */
45/*---------------------------------------------------------------------------*/
46
47
48/**AutomaticStart*************************************************************/
49
50/*---------------------------------------------------------------------------*/
51/* Static function prototypes                                                */
52/*---------------------------------------------------------------------------*/
53
54static void _IoWriteEntryToTable(Tbl_Entry_t *entry, Tbl_Table_t *table, int row, int col, int output);
55static void _IoWriteValueToTable(int value, Tbl_Table_t *table, int row, int col, int output);
56static Tbl_Table_t *_IoTableRemoveEqualsContruct(Tbl_Table_t *origBlifmvTable, array_t *freeVarArray, int verbosity);
57static void _IoVarEncEntryFree(IoVarEncEntry_t *varEnc);
58static int _IoNumValues(int colnum, array_t *numValuesArray);
59static Tbl_Entry_t *_IoCreateBinRange(array_t *mvEntryBinRanges, Tbl_Entry_t *entry, int numBits, int runLength, int skipLength);
60static boolean _IoEntryCheckRange(Tbl_Entry_t *entry, int startValue, int runLength, int skipLength);
61static Tbl_Entry_t *_IoAddBinRange(array_t *mvEntryBinRanges, Tbl_Entry_t *entry, int startValue, int runLength, int skipLength);
62
63/**AutomaticEnd***************************************************************/
64
65
66/*---------------------------------------------------------------------------*/
67/* Definition of exported functions                                          */
68/*---------------------------------------------------------------------------*/
69
70
71/*---------------------------------------------------------------------------*/
72/* Definition of internal functions                                          */
73/*---------------------------------------------------------------------------*/
74
75
76/**Function***********************************************************
77
78
79  Synopsis      [ Makes a single output table for the outputNum'th output]
80
81  Description   [ Allows for ='s in output entries to refer only to input vars ]
82
83  SideEffects   [ ]
84
85  SeeAlso       [  ]
86************************************************************************/
87Tbl_Table_t *
88IoMakeSingleOutputTable(
89  Tbl_Table_t *table,
90  int outputNum
91  )
92{
93    Tbl_Table_t * tableDup;
94    int i, j, numRows, numCols;
95    Tbl_Entry_t *newEntry, *entry, *parentVarEntry;
96    Var_Variable_t *var;
97   
98    tableDup = Tbl_TableAlloc();
99    numRows = Tbl_TableReadNumRows(table);
100    numCols = Tbl_TableReadNumInputs(table);
101   
102    Tbl_TableForEachInputVar(table,i,var){
103        Tbl_TableAddColumn(tableDup,var,0);
104    }
105   
106    var = Tbl_TableReadIndexVar(table,outputNum,1);
107    Tbl_TableAddColumn(tableDup,var,1);
108   
109    entry = Tbl_TableDefaultReadEntry(table,outputNum);
110    if (entry != NIL(Tbl_Entry_t)){
111        if(Tbl_EntryReadType(entry) != Tbl_EntryNormal_c){
112            var = Tbl_EntryReadVar(table, entry);
113            j = Tbl_TableReadVarIndex(table, var, 1);
114            parentVarEntry = Tbl_TableDefaultReadEntry(table, j);
115            newEntry = Tbl_EntryDup(parentVarEntry);
116        }
117        else{
118            newEntry = Tbl_EntryDup(entry);
119        }
120    }
121    else {
122        newEntry = NIL(Tbl_Entry_t);
123    }
124    (void) Tbl_TableDefaultSetEntry(tableDup,newEntry,0);
125   
126    for(i = 0; i < numRows; i++){
127        (void) Tbl_TableAddRow(tableDup);
128        for(j = 0; j < numCols; j++){
129            entry = Tbl_TableReadEntry(table, i, j, 0);
130            newEntry = Tbl_EntryDup(entry);
131            Tbl_TableSetEntry(tableDup, newEntry, i, j, 0);
132        }
133        entry = Tbl_TableReadEntry(table, i, outputNum, 1);
134        newEntry = Tbl_EntryDup(entry);
135        Tbl_TableSetEntry(tableDup, newEntry, i, 0, 1);
136    }
137    return tableDup;
138}
139
140
141
142/**Function***********************************************************
143
144  Synopsis      [ Checks if the number of rows after expansion, due to the
145                  outputs = expansion, is more than a given threshold.]
146
147  Description   [ Allows for ='s in output entries to refer only to input
148  vars ]
149
150  SideEffects   [ ]
151
152  SeeAlso       [ ]
153
154************************************************************************/
155boolean
156IoOutputExpansionRequired(
157  Tbl_Table_t *table
158  )
159{
160    int numRows, numOutputs, i, colnum, parentVarIndex;
161    Tbl_Entry_t *entry;
162    Var_Variable_t *parentVar;
163
164    /* previously used to find out the estimated size of the resulting binary
165       table (in number of entries) and return TRUE if this number was greater
166       than 250. Removed this check, and now return TRUE if the table is multi-
167       output. This is at the cost of potentially increasing runtime.
168    */
169    /* if any of the output entries has an =var where var is another output
170       variable, then output splitting is not done */
171
172    numRows = Tbl_TableReadNumRows(table);
173    numOutputs = Tbl_TableReadNumOutputs(table);
174
175    for(i = 0; i < numRows; i++){
176        for(colnum = 0; colnum < numOutputs; colnum++){
177            entry = Tbl_TableReadEntry(table, i, colnum, 1);
178            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
179                parentVar = Tbl_EntryReadVar(table, entry);
180                parentVarIndex = Tbl_TableReadVarIndex(table, parentVar, 0);
181                if(parentVarIndex == -1){
182                  fprintf(vis_stderr, "Output entry mimics another output with an '=' construct - error\n");
183                  assert(parentVarIndex != -1);
184                }
185            }
186        }
187    }
188    if(numOutputs > 1){
189      return TRUE;
190    }
191    return FALSE;
192}
193   
194/**Function********************************************************************
195
196  Synopsis    [Initializes IoBlifInfo_t data structure]
197
198  Description []
199
200  SideEffects []
201
202  SeeAlso     []
203
204******************************************************************************/
205void
206IoInitBlifInfo(
207   IoBlifInfo_t *blifInfo, 
208   Tbl_Table_t *origBlifmvTable,
209   FILE *fp,
210   FILE *encFp,
211   int verbosity
212   )
213{
214    blifInfo->varArray = array_alloc(Var_Variable_t *, 0);
215    blifInfo->blifmvTable = _IoTableRemoveEqualsContruct(origBlifmvTable, blifInfo->varArray, verbosity);
216    blifInfo->binTable = Tbl_TableAlloc();
217    blifInfo->inputEncTblArray = array_alloc(IoVarEncEntry_t *, 0);
218    blifInfo->outputEncTblArray = array_alloc(IoVarEncEntry_t *, 0);
219    blifInfo->dcTblArray = array_alloc(Tbl_Table_t *, 0);
220    blifInfo->verbosity = verbosity;
221    blifInfo->pseudoinputFlag = FALSE;
222    blifInfo->BlifFp = fp;
223    blifInfo->EncFp = encFp;
224}
225
226
227/**Function********************************************************************
228
229  Synopsis    [Frees IoBlifInfo_t data structure]
230
231  Description [ ]
232
233  SideEffects []
234
235  SeeAlso     []
236
237******************************************************************************/
238void
239IoFreeBlifInfo(
240   IoBlifInfo_t *blifInfo
241   )
242{
243    int i;
244
245    Tbl_TableFree(blifInfo->blifmvTable);
246    Tbl_TableFree(blifInfo->binTable); 
247
248    for(i=0; i < array_n(blifInfo->inputEncTblArray); i++){
249        _IoVarEncEntryFree(array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i));
250    }
251    array_free(blifInfo->inputEncTblArray);
252
253    for(i=0; i < array_n(blifInfo->outputEncTblArray); i++){
254        _IoVarEncEntryFree(array_fetch(IoVarEncEntry_t *, blifInfo->outputEncTblArray, i));
255    }
256    array_free(blifInfo->outputEncTblArray);
257
258    for(i=0; i < array_n(blifInfo->varArray); i++){
259        Var_VariableFree(array_fetch(Var_Variable_t *, blifInfo->varArray, i));
260    }
261    array_free(blifInfo->varArray);
262
263    for(i=0; i < array_n(blifInfo->binTblArray); i++){
264        Tbl_TableFree(array_fetch(Tbl_Table_t *, blifInfo->binTblArray, i));
265    }
266    array_free(blifInfo->binTblArray);
267
268    for(i=0; i < array_n(blifInfo->dcTblArray); i++){
269        Tbl_TableFree(array_fetch(Tbl_Table_t *, blifInfo->dcTblArray, i));
270    }
271    array_free(blifInfo->dcTblArray);
272    FREE(blifInfo);
273     
274}
275
276
277/**Function********************************************************************
278
279  Synopsis    [Determines if a variable is a PI/PO of an hnode. ]
280
281  Description []
282
283  SideEffects []
284
285  SeeAlso     []
286
287******************************************************************************/
288boolean         
289IoVarIsHnodePIO(
290  Hrc_Node_t *hnode, 
291  Var_Variable_t *var
292  )
293{
294    boolean test;
295   
296    test = FALSE;
297    if(Var_VariableTestIsPO(var) || Var_VariableTestIsPI(var) || Var_VariableTestIsSO(var) || Var_VariableTestIsSI(var)){
298        test = TRUE;
299    }
300    return test;
301}
302
303
304/**Function********************************************************************
305
306  Synopsis    [Encodes individual variable based on its ranges]
307
308  Description [Returns encoding as an entry in the array of encodings' tables]
309
310  SideEffects [Populates a table in the array of tables describing the IO encodings]
311
312  SeeAlso     []
313
314******************************************************************************/
315void
316IoEncodeVariable(
317   IoBlifInfo_t *blifInfo,
318   Var_Variable_t *var,
319   int varNum,           
320   int output
321   )
322{
323    int range, numEncBits;
324    IoVarEncEntry_t *varEncEntry;
325
326    range = Var_VariableReadNumValues(var);
327    numEncBits = IoNumEncBits(range);
328   
329    varEncEntry = ALLOC(IoVarEncEntry_t, 1);
330    varEncEntry->variable = Var_VariableDup(var, NIL(Hrc_Node_t));
331    varEncEntry->index = varNum;
332    varEncEntry->numEncBits = numEncBits;
333    if(output == 1){
334        array_insert_last(IoVarEncEntry_t *, blifInfo->outputEncTblArray, varEncEntry);
335    }
336    else{
337        array_insert_last(IoVarEncEntry_t *, blifInfo->inputEncTblArray, varEncEntry);
338    }
339
340}
341
342
343/**Function********************************************************************
344
345  Synopsis    [Returns number of bits in encoding]
346
347  Description [Returns n such that 2^n >= range of the variable ]
348
349  SideEffects []
350
351  SeeAlso     []
352
353******************************************************************************/
354int
355IoNumEncBits(
356   int n
357   )
358{
359    int i=0;
360    int j=1;
361
362    if (n<2){
363        return 1;
364    }
365    else{
366        while (j < n){
367            j = j * 2;
368            i++;
369        }
370    }
371    return i;
372
373}
374
375/**Function********************************************************************
376
377  Synopsis    [Returns the number of digits in the base 10 representation of a number]
378
379  Description []
380
381  SideEffects []
382
383  SeeAlso     []
384
385******************************************************************************/
386int 
387IoNumDigits(
388   int n
389   )
390{
391    double j;
392   
393    j = log10((double) n) + 1;
394    return ((int) j);
395}
396
397/**Function********************************************************************
398
399  Synopsis    [Returns log-base-2 of a number which is a power of 2]
400
401  Description []
402
403  SideEffects []
404
405  SeeAlso     []
406
407******************************************************************************/
408int
409IoLog(
410   int n
411   )
412{
413    int i=0;
414    int j=1;
415
416    while (j < n){
417        j = j * 2;
418        i++;
419    }
420    return i;
421}
422
423
424/**Function********************************************************************
425
426  Synopsis    [Returns the IoVarEncEntry_t with the smallest encoding length]
427
428  Description []
429
430  SideEffects []
431
432  SeeAlso     []
433
434******************************************************************************/
435IoVarEncEntry_t *
436IoFindSmallestCode( 
437   IoBlifInfo_t *blifInfo
438   )
439{
440    int i, smallestCode, index;
441    IoVarEncEntry_t *varEnc;
442
443    index = -1;
444    smallestCode = VIS_INFINITY;
445    for(i = 0; i < array_n(blifInfo->inputEncTblArray); i++){
446        varEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i);
447        if((Var_VariableReadNumValues(varEnc->variable)) < smallestCode){
448            smallestCode = Var_VariableReadNumValues(varEnc->variable);
449            index = i;
450        }
451    }
452   
453    assert(index != -1);
454    varEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, index);
455    return varEnc;
456
457}
458
459/**Function********************************************************************
460
461  Synopsis    [Increases the code size of a variable]
462
463  Description [Invoked when a output for a row has multiple values. To determinize
464               this scenario, an input has pseudovariables appended to its code. The
465               number of pseudoinputs = log(n) where n is the number of values of the
466               output]
467
468  SideEffects [alters encoding of mv variables]
469
470  SeeAlso     []
471
472******************************************************************************/
473void
474IoIncreaseCodeSize(
475  IoVarEncEntry_t *varEnc, 
476  int numValues,
477  int verbosity           
478  )
479{
480    int temp1, temp2, range, numAddedPseudovars, numExpand;
481
482    range = Var_VariableReadNumValues(varEnc->variable);
483    numAddedPseudovars = IoNumEncBits(numValues);
484    temp1 = ((int) pow((double) 2, (double)numAddedPseudovars)) - 1;
485    temp2 = (int) pow((double) 2, (double)varEnc->numEncBits);
486    numExpand = (temp1 * temp2) + range;
487    if(verbosity > 2){
488        (void)fprintf(stdout, "New Number of Values for the variable = %d\n", numExpand);
489    }
490    Var_VariableExpandRange(varEnc->variable, numExpand);
491       
492
493}
494
495
496/**Function********************************************************************
497
498  Synopsis    [Alters blifmv table to reflect the increase in code size from IoIncreaseCodeSize]
499
500  Description []
501               
502  SideEffects []
503
504  SeeAlso     []
505
506******************************************************************************/
507void
508IoChangeBlifmvTableRows(
509   IoBlifInfo_t *blifInfo,               
510   IoVarEncEntry_t *varEnc, 
511   int row1,
512   int row2
513  )
514{
515    int numCurrentBits, i, numRows, colnum, tempCol, reqdColnum;
516    Tbl_Entry_t *entry;
517    char *varname, *dupName;
518    Var_Variable_t *newVar;
519    IoVarEncEntry_t *tempVarEnc;
520
521    /* add a new column to bin table */
522    numCurrentBits = varEnc->numEncBits;
523    varname = Var_VariableReadName(varEnc->variable);
524    dupName = ALLOC(char, strlen(varname) + IoNumDigits(numCurrentBits) + 2);
525    sprintf(dupName, "%s%d", varname, numCurrentBits);
526    newVar = Var_VariableAlloc(NIL(Hrc_Node_t), dupName);
527    FREE(dupName);
528    array_insert_last(Var_Variable_t *, blifInfo->varArray, newVar);
529    colnum = Tbl_TableAddColumn(blifInfo->binTable, newVar, 0);
530    numRows = Tbl_TableReadNumRows(blifInfo->binTable);
531    for(i = 0; i < numRows; i++){
532        entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
533        if(i == row1){
534            Tbl_EntrySetValue(entry, 0, 0);
535        }
536        if(i == row2){
537            Tbl_EntrySetValue(entry, 1, 1);
538        }
539        if((i != row1) && (i != row2)){
540            Tbl_EntrySetValue(entry, 0, 1);
541        }
542        Tbl_TableSetEntry(blifInfo->binTable, entry, i, colnum - 1, 0);
543    }
544    tempCol = 0;
545    reqdColnum = -1;
546    for(i = 0; i < array_n(blifInfo->inputEncTblArray); i++){
547        tempVarEnc = array_fetch(IoVarEncEntry_t *, blifInfo->inputEncTblArray, i);
548        if(tempVarEnc == varEnc){
549            reqdColnum = tempCol + varEnc->numEncBits;
550        }
551        tempCol += tempVarEnc->numEncBits;
552    }
553    colnum--;   
554    assert(reqdColnum != -1);
555    while(reqdColnum < colnum){
556        Tbl_TableSwapColumns(blifInfo->binTable, colnum, colnum - 1, 0);
557        colnum--;
558    }
559}
560
561
562/**Function********************************************************************
563
564  Synopsis    [Alters table to reflect the increase in code size from IoIncreaseCodeSize]
565
566  Description []
567               
568  SideEffects []
569
570  SeeAlso     []
571
572******************************************************************************/
573void
574IoChangeBlifmvTableEntries(
575   IoBlifInfo_t *blifInfo,
576   int rownum,
577   int numValues,
578   IoVarEncEntry_t *varEnc, 
579   array_t *MvOutputArray
580  )
581{
582    int i, j, k, newrownum, colnum, inputColnumToChange, value, offset;
583    int numInputs, numOutputs, entryRepetitionCount, numCycles, numNewBits, maxValue, numOldBits;
584    Tbl_Entry_t *entry, *dupEntry;
585    lsGen gen;
586    Tbl_Range_t *range;
587
588    numInputs = Tbl_TableReadNumInputs(blifInfo->blifmvTable);
589    numOutputs = Tbl_TableReadNumOutputs(blifInfo->blifmvTable);
590    numNewBits = IoNumEncBits(numValues);
591    numOldBits = varEnc->numEncBits;
592    maxValue = (int) pow((double) 2, (double)(numNewBits + numOldBits));
593
594    inputColnumToChange = varEnc->index;
595    for(i = 0; i < Tbl_TableReadNumRows(blifInfo->blifmvTable); i++){
596        if (i != rownum){
597            entry = Tbl_TableReadEntry(blifInfo->blifmvTable, i, inputColnumToChange, 0);
598            dupEntry = Tbl_EntryDup(entry);
599            offset = (int) pow((double) 2, (double)varEnc->numEncBits);
600            Tbl_EntryForEachValue(entry, value, gen, range){
601                for(j = value ; j < maxValue; j = j + offset){
602                    Tbl_EntrySetValue(dupEntry, j, j);
603                }
604            }
605            Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, i, inputColnumToChange, 0);
606        }
607    }
608    newrownum = -1;
609    for(i = 0; i < numValues; i++){
610 
611         /* add a row, and duplicate all entries of the original row except for
612            the one that needs a new entry (because of the new code). This entry
613            gets code = oldCode + i * (2^numCurrentEncBits)      */
614
615        newrownum = Tbl_TableAddRow(blifInfo->blifmvTable);
616        assert(newrownum != -1);
617        for(colnum = 0; colnum < numInputs; colnum++){
618            entry = Tbl_TableReadEntry(blifInfo->blifmvTable, rownum, colnum, 0);
619            if(colnum != inputColnumToChange){
620                dupEntry = Tbl_EntryDup(entry);
621                Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum, colnum, 0);
622            }
623            else{
624                dupEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
625                offset = i * ((int) pow((double) 2, (double) varEnc->numEncBits));
626                Tbl_EntryForEachValue(entry, value, gen, range){
627                    Tbl_EntrySetValue(dupEntry, value + offset, value + offset);
628                }
629                Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum, colnum, 0);
630            }
631        }
632    }
633
634    /* This section singleton-izes the output entries of the new row.
635       Multiple outputs are accounted for. If more than one output has
636       non-singleton entries, they are all singleton-ized. Finally,
637       the original row is deleted...                                       */ 
638   
639    entryRepetitionCount = numValues;
640    numCycles = 1;
641    newrownum++;
642   
643    for(colnum = 0; colnum < numOutputs; colnum++){
644        newrownum = newrownum - numValues;
645        numCycles *= _IoNumValues(colnum, MvOutputArray);
646        entryRepetitionCount /= array_fetch(int, MvOutputArray, colnum);
647        entry = Tbl_TableReadEntry(blifInfo->blifmvTable, rownum, colnum, 1);
648        for(j = 0; j < numCycles; j++){
649            Tbl_EntryForEachValue(entry, value, gen, range){
650                for(k = 0; k < entryRepetitionCount; k++){
651                    dupEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);                       
652                    Tbl_EntrySetValue(dupEntry, value, value);       
653                    Tbl_TableSetEntry(blifInfo->blifmvTable, dupEntry, newrownum++, colnum, 1);
654                }
655            }
656        }
657    }
658    blifInfo->blifmvTable = Tbl_TableRowDelete(blifInfo->blifmvTable, rownum, blifInfo->varArray); 
659}
660
661
662/**Function********************************************************************
663
664  Synopsis    [Alters table to reflect the increase in code size from IoIncreaseCodeSize]
665
666  Description []
667               
668  SideEffects []
669
670  SeeAlso     []
671
672******************************************************************************/
673void
674IoChangeEncTableEntries(
675   IoBlifInfo_t *blifInfo,               
676   st_table *blifInputsStTable,
677   IoVarEncEntry_t *varEnc, 
678   int numValues
679  )
680{
681    int numOrigBits, numAddedBits, i;
682    char *varname, *dupName;
683   
684    numAddedBits = IoNumEncBits(numValues);
685    numOrigBits = varEnc->numEncBits;
686
687    varname = Var_VariableReadName(varEnc->variable);
688    for(i=0; i<numAddedBits; i++){
689        dupName = ALLOC(char, strlen(varname) + IoNumDigits(numAddedBits + numOrigBits)+ 2);
690        sprintf(dupName, "%s%d", varname, i + numOrigBits);
691        if(!st_is_member(blifInputsStTable, (char *)dupName)){
692            (void)fprintf(blifInfo->BlifFp, ".inputs %s\n", dupName);
693            if(blifInfo->pseudoinputFlag == FALSE){
694                (void)fprintf(blifInfo->EncFp, ".table %s\n", dupName);
695                (void)fprintf(blifInfo->EncFp, "-\n");
696            }
697            st_insert(blifInputsStTable, (char *)dupName, (char *)1);
698        }
699        else{
700            FREE(dupName);
701        }
702    }
703    varEnc->numEncBits += numAddedBits;
704
705}
706
707
708
709
710/**Function********************************************************************
711
712  Synopsis    [Inverts a specified binary output of binTable]
713
714  Description []
715
716  SideEffects []
717
718  SeeAlso     []
719
720******************************************************************************/
721void
722IoInvertBinTableOutput(
723   IoBlifInfo_t * blifInfo,
724   int colnumToInvert
725   )
726{
727    int i;
728    char *name, *newname;
729    Var_Variable_t *var;
730   
731    var = Tbl_TableReadIndexVar(blifInfo->binTable, colnumToInvert, 1);
732    name = Var_VariableReadName(var);
733    newname = ALLOC(char, strlen(name) + 4);
734    sprintf(newname, "%s_b", name);
735    (void)fprintf(blifInfo->BlifFp, ".names %s %s\n", newname, name);
736    (void)fprintf(blifInfo->BlifFp, "0 1\n");
737    Var_VariableChangeName(var, newname);
738    FREE(newname);
739    for(i = 0; i < Tbl_TableReadNumRows(blifInfo->binTable); i++){
740        Tbl_TableComplementEntry(blifInfo->binTable, i, colnumToInvert, 1);
741    }
742}
743
744
745/**Function********************************************************************
746
747  Synopsis    [Returns array that represents a simple way of compacting a mv
748               entry while representing it in binary.]
749
750  Description [The array contains IoBinRangeEntry_t *'s. Each item of the array represents
751               a starting value and a run length and a skip length. The union of all such values contains
752               exactly the values of the entry passed]
753
754  SideEffects []
755
756  SeeAlso     []
757
758******************************************************************************/
759array_t *
760IoMakeBinaryRangesArray(
761   Tbl_Entry_t *entry,
762   int colnum,
763   IoBlifInfo_t *blifInfo                     
764   )
765{
766    array_t *mvEntryBinRanges;
767    int i, j, numBits, runLength, skipLength;
768   
769    mvEntryBinRanges = array_alloc(IoBinRangeEntry_t *, 0);
770    numBits = IoNumBinVars(colnum + 1, blifInfo->inputEncTblArray);
771    for(i = numBits; i > 0; i--){
772        for(j = 0; j < numBits; j++){
773            runLength = (int) pow((double) 2, (double) i);
774            skipLength = (int) pow((double) 2, (double) j);
775            if((runLength * skipLength) <= (int) pow((double) 2, (double) numBits)){
776/*              fprintf(stdout, "run %d, skip %d\n", runLength, skipLength); */
777                entry = _IoCreateBinRange(mvEntryBinRanges, entry, numBits, runLength, skipLength);
778            }
779        }
780    }
781    entry = _IoCreateBinRange(mvEntryBinRanges, entry, numBits, 1, 1);     
782    assert(Tbl_EntryReadNumValues(entry) == 0);
783    Tbl_EntryFree(entry);
784    return mvEntryBinRanges;
785}
786
787
788/**Function********************************************************************
789
790  Synopsis    [Returns the number of values in the entrycolnum-1) ]
791
792  Description []
793
794  SideEffects []
795
796  SeeAlso     []
797
798******************************************************************************/
799int
800IoNumValuesFromBinRangesArray( 
801   int colnum,
802   array_t *binRangesArray
803   )
804{
805    array_t *mvEntryBinRanges;
806
807    if(colnum == 0){
808        return 1;
809    }
810    else{
811        mvEntryBinRanges = array_fetch(array_t *, binRangesArray, colnum - 1);
812        return(array_n(mvEntryBinRanges));
813    }
814}
815
816
817/**Function********************************************************************
818
819  Synopsis    [Returns the number of binary vars in the variable index (colnum-1) ]
820
821  Description []
822
823  SideEffects []
824
825  SeeAlso     []
826
827******************************************************************************/
828int
829IoNumBinVars( 
830   int colnum,
831   array_t *encTblArray
832   )
833{
834    IoVarEncEntry_t *varEnc;
835   
836    if(colnum == 0){
837        return 0;
838    }
839    else{
840        varEnc = array_fetch(IoVarEncEntry_t *, encTblArray, colnum-1);
841        return(varEnc->numEncBits);
842    }
843}
844
845   
846/*---------------------------------------------------------------------------*/
847/* Definition of static functions                                            */
848/*---------------------------------------------------------------------------*/
849
850
851/**Function********************************************************************
852
853  Synopsis    [Duplicate an entry and set it  in a table]
854
855  Description []
856
857  SideEffects []
858
859  SeeAlso     []
860
861******************************************************************************/
862static void
863_IoWriteEntryToTable(
864   Tbl_Entry_t *entry, 
865   Tbl_Table_t *table, 
866   int row, 
867   int col, 
868   int output
869)
870{
871    Tbl_Entry_t *dupEntry;
872   
873    dupEntry = Tbl_EntryDup(entry);
874    Tbl_TableSetEntry(table, dupEntry, row, col, output);
875}
876
877
878/**Function********************************************************************
879
880  Synopsis    [Make an entry from a value, and set it  in a table]
881
882  Description []
883
884  SideEffects []
885
886  SeeAlso     []
887
888******************************************************************************/
889static void
890_IoWriteValueToTable(
891   int value, 
892   Tbl_Table_t *table, 
893   int row, 
894   int col, 
895   int output
896)
897{
898    Tbl_Entry_t *entry;
899   
900    entry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
901    Tbl_EntrySetValue(entry, value, value);
902    Tbl_TableSetEntry(table, entry, row, col, output);
903}
904
905/**Function********************************************************************
906
907  Synopsis    [Removes "=" constructs in a table]
908
909  Description []
910
911  SideEffects []
912
913  SeeAlso     []
914
915******************************************************************************/
916static Tbl_Table_t *
917_IoTableRemoveEqualsContruct(
918   Tbl_Table_t *origBlifmvTable,
919   array_t *freeVarArray,
920   int verbosity
921   )
922{
923    Tbl_Table_t *resultTable;
924    int numRows, numInputs, numOutputs, numRowsAfterExpansion, i, j, k, colnum, rownum, currRow, value;
925    int parentVarnumValues, parentVarIndex, rootRow, entryRepetitionCount ;
926    st_table *parentsStTable;
927    Tbl_Entry_t *entry, *parentVarEntry, *dupEntry;
928    Var_Variable_t *parentVar, *var;
929    boolean parentVarIsOutput, rowContainsEqualEntries, insertedI;
930    st_generator *gen;
931    Tbl_Range_t *range;
932    lsGen listgen;
933    array_t *rowDeleteArray;
934    char *dummy;
935
936    resultTable = Tbl_TableHardDup(origBlifmvTable);
937    /* remove "="s in original defaults table*/
938    for(i = 0; i < Tbl_TableReadNumOutputs(resultTable); i++){
939        entry = Tbl_TableDefaultReadEntry(resultTable, i);
940        if(entry != NIL(Tbl_Entry_t)){
941            if(Tbl_EntryReadType(entry) != Tbl_EntryNormal_c){
942                var = Tbl_EntryReadVar(resultTable, entry);
943                j = Tbl_TableReadVarIndex(resultTable, var, 1);
944                parentVarEntry = Tbl_TableDefaultReadEntry(resultTable, j);
945                dupEntry = Tbl_EntryDup(parentVarEntry);
946                Tbl_TableDefaultSetEntry(resultTable, dupEntry, i);
947                Tbl_EntryFree(entry);
948            }
949        }
950    }
951
952    /* first expand all rows with "=" constructs, in the same table */
953    numRows = Tbl_TableReadNumRows(resultTable);
954    numInputs = Tbl_TableReadNumInputs(resultTable);
955    numOutputs = Tbl_TableReadNumOutputs(resultTable);
956    rootRow = numRows;
957
958    for(i = 0; i < numRows; i++){
959        numRowsAfterExpansion = 1;
960        rowContainsEqualEntries = FALSE;       
961        parentsStTable = st_init_table(st_ptrcmp, st_ptrhash);
962
963        /* find variables that are parent variables, ie variables 'var' that
964           have =var references in that row of the table    */
965        for(colnum = 0; colnum < numInputs; colnum++){
966            entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
967            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
968                rowContainsEqualEntries = TRUE;
969                parentVar = Tbl_EntryReadVar(resultTable, entry);
970                st_insert(parentsStTable, (char *) parentVar, (char *) 1);
971            }
972        }
973        for(colnum = 0; colnum < numOutputs; colnum++){
974            entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
975            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
976                rowContainsEqualEntries = TRUE;
977                parentVar = Tbl_EntryReadVar(resultTable, entry);
978                st_insert(parentsStTable, (char *) parentVar, (char *) 1);
979            }
980        }
981        if(rowContainsEqualEntries == FALSE){
982            st_free_table(parentsStTable);
983            continue;
984        }
985       
986        /* find the number of rows after expansion */
987        st_foreach_item(parentsStTable, gen, &parentVar, &dummy){
988            parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
989            if(parentVarIndex != -1){
990                parentVarIsOutput = 0;
991            }
992            else{
993                parentVarIsOutput = 1;
994                parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);             
995            }
996            parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex, parentVarIsOutput);
997            numRowsAfterExpansion *= Tbl_EntryReadNumValues(parentVarEntry);
998        }
999
1000        /* write out expanded form of this row */
1001        for(j = 0; j < numRowsAfterExpansion; j++){
1002            Tbl_TableAddRow(resultTable);
1003        }
1004        /* expand parent variables first */
1005        entryRepetitionCount = numRowsAfterExpansion;
1006        st_foreach_item(parentsStTable, gen, &parentVar, &dummy){
1007            parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
1008            if(parentVarIndex != -1){
1009                parentVarIsOutput = 0;
1010            }
1011            else{
1012                parentVarIsOutput = 1;
1013                parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);             
1014            }
1015            parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
1016                                                  parentVarIsOutput);
1017            parentVarnumValues = Tbl_EntryReadNumValues(parentVarEntry);
1018            currRow = rootRow;
1019            entryRepetitionCount = entryRepetitionCount / parentVarnumValues;
1020            while(currRow < rootRow + numRowsAfterExpansion){
1021                Tbl_EntryForEachValue(parentVarEntry, value, listgen, range){       
1022                    for(k = 0; k < entryRepetitionCount; k++){
1023                        _IoWriteValueToTable(value, resultTable, currRow, parentVarIndex,
1024                                            parentVarIsOutput);
1025                        currRow++;
1026                    }
1027                }
1028            }
1029        }
1030
1031        /* next expand variables that reference parent vars */
1032        for(colnum = 0; colnum < numInputs; colnum++){
1033            entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
1034            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
1035                parentVar = Tbl_EntryReadVar(resultTable, entry);
1036                parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
1037                if(parentVarIndex != -1){
1038                    parentVarIsOutput = 0;
1039                }
1040                else{
1041                    parentVarIsOutput = 1;
1042                    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);         
1043                }
1044                parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
1045                                                      parentVarIsOutput);
1046                for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
1047                    entry = Tbl_TableReadEntry(resultTable, k, parentVarIndex,
1048                                               parentVarIsOutput);         
1049                    _IoWriteEntryToTable(entry, resultTable, k, colnum, 0);
1050                }
1051            }
1052            else{
1053                if(!st_is_member(parentsStTable, (char *) Tbl_TableReadIndexVar(resultTable,
1054                                                                                  colnum, 0))){
1055                    for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
1056                        _IoWriteEntryToTable(entry, resultTable, k, colnum, 0);
1057                    }
1058                }
1059            }
1060        }
1061        for(colnum = 0; colnum < numOutputs; colnum++){
1062            entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
1063            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
1064                parentVar = Tbl_EntryReadVar(resultTable, entry);
1065                parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 0);
1066                if(parentVarIndex != -1){
1067                    parentVarIsOutput = 0;
1068                }
1069                else{
1070                    parentVarIsOutput = 1;
1071                    parentVarIndex = Tbl_TableReadVarIndex(resultTable, parentVar, 1);         
1072                }
1073                parentVarEntry = Tbl_TableReadEntry(resultTable, i, parentVarIndex,
1074                                                      parentVarIsOutput);
1075                for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
1076                    entry = Tbl_TableReadEntry(resultTable, k, parentVarIndex,
1077                                               parentVarIsOutput);         
1078                    _IoWriteEntryToTable(entry, resultTable, k, colnum, 1);
1079                }
1080            }
1081            else{
1082                if(!st_is_member(parentsStTable, (char *) Tbl_TableReadIndexVar(resultTable,
1083                                                                                  colnum, 1))){
1084                    for(k = rootRow; k < rootRow + numRowsAfterExpansion; k++){
1085                        _IoWriteEntryToTable(entry, resultTable, k, colnum, 1);
1086                    }
1087                }
1088            }
1089        }
1090        rootRow += numRowsAfterExpansion;
1091        st_free_table(parentsStTable);
1092    }
1093   
1094   
1095    /* now delete rows with "=" constructs */
1096    rowDeleteArray = array_alloc(int, 0);
1097    for(i = 0; i < numRows; i++){
1098        insertedI = FALSE;
1099        for(colnum = 0; colnum < numInputs; colnum++){
1100            entry = Tbl_TableReadEntry(resultTable, i, colnum, 0);
1101            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
1102                if(!insertedI){
1103                    array_insert_last(int, rowDeleteArray, i);
1104                    insertedI = TRUE;
1105                }
1106            }
1107        }
1108        for(colnum = 0; colnum < numOutputs; colnum++){
1109            entry = Tbl_TableReadEntry(resultTable, i, colnum, 1);
1110            if(Tbl_EntryReadType(entry) == Tbl_EntryEqual_c){
1111                if(!insertedI){
1112                    array_insert_last(int, rowDeleteArray, i);
1113                    insertedI = TRUE;
1114                }
1115            }
1116        }
1117    }
1118    /* array of vars that are to be freed. Since these are called with
1119      a NIL(Hrc_Node_t), they need to be freed separately, and kept track
1120      of
1121    */
1122    for(i = 0; i < array_n(rowDeleteArray); i++){
1123        rownum = array_fetch(int, rowDeleteArray, i) - i;
1124        resultTable = Tbl_TableRowDelete(resultTable, rownum, freeVarArray); 
1125    }
1126    array_free(rowDeleteArray);
1127
1128
1129    if(verbosity > 1){
1130        (void)fprintf(stdout, "Blifmv Table after = removal is\n");
1131        Tbl_TableWriteBlifMvToFile(resultTable, 0, stdout);
1132    }
1133    return resultTable;
1134
1135}
1136       
1137
1138/**Function********************************************************************
1139
1140  Synopsis    [Frees the IoVarEncEntry_t ]
1141
1142  Description []
1143
1144  SideEffects []
1145
1146  SeeAlso     []
1147
1148******************************************************************************/
1149static void
1150_IoVarEncEntryFree(
1151  IoVarEncEntry_t *varEnc
1152  )
1153{
1154    Var_VariableFree(varEnc->variable);
1155    free(varEnc);
1156}
1157
1158
1159/**Function********************************************************************
1160
1161  Synopsis    [Checks if runLength entries from startValue with skipLength increments are contained in entry
1162              ]
1163
1164  Description []
1165
1166  SideEffects []
1167
1168  SeeAlso     []
1169
1170******************************************************************************/
1171static boolean
1172_IoEntryCheckRange(
1173 Tbl_Entry_t *entry,
1174 int startValue,
1175 int runLength,
1176 int skipLength
1177 )
1178{
1179    boolean startFound;
1180    int value, i;
1181    lsGen gen;
1182    Tbl_Range_t *range;
1183
1184    startFound = FALSE;
1185    i = 1;
1186    Tbl_EntryForEachValue(entry, value, gen, range){
1187        if(value == startValue){
1188            startFound = TRUE;
1189        }
1190        if((!startFound) && (value > startValue)){
1191            lsFinish(gen);
1192            return FALSE;
1193        }
1194        if(value == startValue + (i * skipLength)){
1195            i++;
1196        }
1197        if(value > startValue + (i * skipLength)){
1198            lsFinish(gen);
1199            return FALSE;
1200        }
1201        if(i == runLength){
1202            lsFinish(gen);
1203            return TRUE;
1204        }
1205    }
1206    return FALSE;
1207}
1208
1209
1210/**Function********************************************************************
1211
1212  Synopsis    [Returns a (startValue, runLength) pair such that the runLength
1213               is the largest number of contiguous values in entry, starting from
1214               startValue]
1215
1216  Description [adds  a IoBinRangeEntry_t * to the mvEntryBinRanges. Also returns the
1217               value upto which all values of the entry have been entered in the
1218               mvEntryBinRanges.]
1219
1220  SideEffects []
1221
1222  SeeAlso     []
1223
1224******************************************************************************/
1225static Tbl_Entry_t *
1226_IoCreateBinRange(
1227   array_t *mvEntryBinRanges,
1228   Tbl_Entry_t *entry,
1229   int numBits,         
1230   int runLength,             
1231   int skipLength
1232   )             
1233{
1234    int i, j, bitPos, tempI, numDash, end, numStartValues, startValue;
1235    array_t *freeBitsArray;
1236
1237    numDash = IoLog(runLength);
1238    end = IoLog(skipLength);
1239    freeBitsArray = array_alloc(int, 0);
1240    for(i = 0; i < numBits; i++){
1241        if(i < end){
1242            array_insert_last(int, freeBitsArray, i);
1243        }
1244        if(i >= end + numDash){
1245            array_insert_last(int, freeBitsArray, i);
1246        }
1247    }
1248    numStartValues = (int) pow((double) 2, (double) array_n(freeBitsArray));
1249    for(i = 0; i < numStartValues; i++){
1250        startValue = 0;
1251        tempI = i;
1252        for(j = array_n(freeBitsArray) - 1; j >= 0; j--){
1253            if(tempI >= (int) pow((double) 2, (double) j)){
1254                bitPos = array_fetch(int, freeBitsArray, j);
1255                startValue += (int) pow((double) 2, (double) bitPos);
1256                tempI -= (int) pow((double) 2, (double) j);
1257            }
1258        } 
1259/*      fprintf(stdout, "trying start %d, run %d, skip %d\n", startValue, runLength, skipLength); */
1260        if(_IoEntryCheckRange(entry, startValue, runLength, skipLength)){
1261            entry = _IoAddBinRange(mvEntryBinRanges, entry, startValue, runLength, skipLength);
1262        }
1263    }
1264    array_free(freeBitsArray);
1265    return entry;
1266}
1267
1268/**Function********************************************************************
1269
1270  Synopsis    [Enters a (startValue, runLength, skipLength) tuple into the mvEntryBinRanges array]
1271
1272  Description [adds  a IoBinRangeEntry_t * to the mvEntryBinRanges. ]
1273
1274  SideEffects []
1275
1276  SeeAlso     []
1277
1278******************************************************************************/
1279static Tbl_Entry_t *
1280_IoAddBinRange(
1281   array_t *mvEntryBinRanges,
1282   Tbl_Entry_t *entry,
1283   int startValue,
1284   int runLength,             
1285   int skipLength
1286   )
1287{
1288    IoBinRangeEntry_t *binRangeEntry;
1289    int i, value;
1290    Tbl_Entry_t *newEntry;
1291    lsGen gen;
1292    Tbl_Range_t *range;
1293   
1294    binRangeEntry = ALLOC(IoBinRangeEntry_t, 1);
1295    binRangeEntry->startValue = startValue;
1296    binRangeEntry->runLength = runLength;
1297    binRangeEntry->skipLength = skipLength;
1298    array_insert_last(IoBinRangeEntry_t *, mvEntryBinRanges, binRangeEntry);
1299    newEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
1300    i = 0;
1301    Tbl_EntryForEachValue(entry, value, gen, range){
1302        if((value == startValue + (i * skipLength)) && (i < runLength)){
1303            i++;
1304        }
1305        else{
1306            Tbl_EntrySetValue(newEntry, value, value);
1307        }
1308    }
1309    Tbl_EntryFree(entry);
1310    return newEntry;
1311}
1312
1313
1314/**Function********************************************************************
1315
1316  Synopsis    [Returns the number of values in the entrycolnum-1) ]
1317
1318  Description []
1319
1320  SideEffects []
1321
1322  SeeAlso     []
1323
1324******************************************************************************/
1325static int
1326_IoNumValues(
1327  int colnum,
1328  array_t *numValuesArray
1329  )
1330{
1331    if(colnum == 0){
1332        return 1;
1333    }
1334    else{
1335        return(array_fetch(int, numValuesArray, colnum - 1));
1336    }
1337}
1338               
1339
Note: See TracBrowser for help on using the repository browser.