diff options
| author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-19 08:01:00 -0700 |
|---|---|---|
| committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-19 08:01:00 -0700 |
| commit | 0e4de190ff4e25f5904a571b79a225363d5fc369 (patch) | |
| tree | a89075fbb01848568534265967c59289c77713a0 | |
| parent | dffcc93b8e8779f443762c71098796b01ea7d409 (diff) | |
| download | abc-0e4de190ff4e25f5904a571b79a225363d5fc369.tar.gz abc-0e4de190ff4e25f5904a571b79a225363d5fc369.tar.bz2 abc-0e4de190ff4e25f5904a571b79a225363d5fc369.zip | |
Version abc50819
39 files changed, 1970 insertions, 2116 deletions
@@ -1125,6 +1125,10 @@ SOURCE=.\src\opt\rwr\rwrMan.c # End Source File # Begin Source File +SOURCE=.\src\opt\rwr\rwrPrint.c +# End Source File +# Begin Source File + SOURCE=.\src\opt\rwr\rwrUtil.c # End Source File # End Group Binary files differ@@ -6,274 +6,14 @@ --------------------Configuration: abc - Win32 Release-------------------- </h3> <h3>Command Lines</h3> -Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C4.tmp" with contents +Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1976.tmp" with contents [ /nologo /ML /W3 /GX /O2 /I "src\base\abc" /I "src\base\cmd" /I "src\base\io" /I "src\base\main" /I "src\bdd\cudd" /I "src\bdd\epd" /I "src\bdd\mtr" /I "src\bdd\parse" /I "src\bdd\dsd" /I "src\bdd\reo" /I "src\sop\mvc" /I "src\sop\ft" /I "src\sat\asat" /I "src\sat\msat" /I "src\sat\fraig" /I "src\opt\fxa" /I "src\opt\fxu" /I "src\opt\rwr" /I "src\map\fpga" /I "src\map\mapper" /I "src\map\mio" /I "src\map\super" /I "src\misc\extra" /I "src\misc\st" /I "src\misc\util" /I "src\misc\vec" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /D "__STDC__" /D "HAVE_ASSERT_H" /FR"Release/" /Fp"Release/abc.pch" /YX /Fo"Release/" /Fd"Release/" /FD /c -"C:\_projects\abc\src\base\abc\abc.c" -"C:\_projects\abc\src\base\abc\abcAig.c" -"C:\_projects\abc\src\base\abc\abcAttach.c" -"C:\_projects\abc\src\base\abc\abcCheck.c" -"C:\_projects\abc\src\base\abc\abcCollapse.c" -"C:\_projects\abc\src\base\abc\abcCreate.c" -"C:\_projects\abc\src\base\abc\abcDfs.c" -"C:\_projects\abc\src\base\abc\abcDsd.c" -"C:\_projects\abc\src\base\abc\abcFanio.c" -"C:\_projects\abc\src\base\abc\abcFpga.c" -"C:\_projects\abc\src\base\abc\abcFraig.c" -"C:\_projects\abc\src\base\abc\abcFunc.c" -"C:\_projects\abc\src\base\abc\abcFxu.c" -"C:\_projects\abc\src\base\abc\abcLatch.c" -"C:\_projects\abc\src\base\abc\abcMap.c" -"C:\_projects\abc\src\base\abc\abcMinBase.c" -"C:\_projects\abc\src\base\abc\abcMiter.c" -"C:\_projects\abc\src\base\abc\abcNames.c" -"C:\_projects\abc\src\base\abc\abcNetlist.c" -"C:\_projects\abc\src\base\abc\abcPrint.c" -"C:\_projects\abc\src\base\abc\abcReconv.c" -"C:\_projects\abc\src\base\abc\abcRefs.c" -"C:\_projects\abc\src\base\abc\abcRenode.c" -"C:\_projects\abc\src\base\abc\abcSat.c" -"C:\_projects\abc\src\base\abc\abcSeq.c" -"C:\_projects\abc\src\base\abc\abcSeqRetime.c" -"C:\_projects\abc\src\base\abc\abcShow.c" -"C:\_projects\abc\src\base\abc\abcSop.c" -"C:\_projects\abc\src\base\abc\abcStrash.c" -"C:\_projects\abc\src\base\abc\abcSweep.c" -"C:\_projects\abc\src\base\abc\abcTiming.c" -"C:\_projects\abc\src\base\abc\abcUnreach.c" -"C:\_projects\abc\src\base\abc\abcUtil.c" -"C:\_projects\abc\src\base\abc\abcVerify.c" -"C:\_projects\abc\src\base\cmd\cmd.c" -"C:\_projects\abc\src\base\cmd\cmdAlias.c" -"C:\_projects\abc\src\base\cmd\cmdApi.c" -"C:\_projects\abc\src\base\cmd\cmdFlag.c" -"C:\_projects\abc\src\base\cmd\cmdHist.c" -"C:\_projects\abc\src\base\cmd\cmdUtils.c" -"C:\_projects\abc\src\base\io\io.c" -"C:\_projects\abc\src\base\io\ioRead.c" -"C:\_projects\abc\src\base\io\ioReadBench.c" -"C:\_projects\abc\src\base\io\ioReadBlif.c" -"C:\_projects\abc\src\base\io\ioReadEdif.c" -"C:\_projects\abc\src\base\io\ioReadPla.c" -"C:\_projects\abc\src\base\io\ioReadVerilog.c" -"C:\_projects\abc\src\base\io\ioUtil.c" -"C:\_projects\abc\src\base\io\ioWriteBench.c" -"C:\_projects\abc\src\base\io\ioWriteBlif.c" -"C:\_projects\abc\src\base\io\ioWriteCnf.c" -"C:\_projects\abc\src\base\io\ioWritePla.c" -"C:\_projects\abc\src\base\main\main.c" -"C:\_projects\abc\src\base\main\mainFrame.c" -"C:\_projects\abc\src\base\main\mainInit.c" -"C:\_projects\abc\src\base\main\mainUtils.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddAbs.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddApply.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddFind.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddInv.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddIte.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddNeg.c" -"C:\_projects\abc\src\bdd\cudd\cuddAddWalsh.c" -"C:\_projects\abc\src\bdd\cudd\cuddAndAbs.c" -"C:\_projects\abc\src\bdd\cudd\cuddAnneal.c" -"C:\_projects\abc\src\bdd\cudd\cuddApa.c" -"C:\_projects\abc\src\bdd\cudd\cuddAPI.c" -"C:\_projects\abc\src\bdd\cudd\cuddApprox.c" -"C:\_projects\abc\src\bdd\cudd\cuddBddAbs.c" -"C:\_projects\abc\src\bdd\cudd\cuddBddCorr.c" -"C:\_projects\abc\src\bdd\cudd\cuddBddIte.c" -"C:\_projects\abc\src\bdd\cudd\cuddBridge.c" -"C:\_projects\abc\src\bdd\cudd\cuddCache.c" -"C:\_projects\abc\src\bdd\cudd\cuddCheck.c" -"C:\_projects\abc\src\bdd\cudd\cuddClip.c" -"C:\_projects\abc\src\bdd\cudd\cuddCof.c" -"C:\_projects\abc\src\bdd\cudd\cuddCompose.c" -"C:\_projects\abc\src\bdd\cudd\cuddDecomp.c" -"C:\_projects\abc\src\bdd\cudd\cuddEssent.c" -"C:\_projects\abc\src\bdd\cudd\cuddExact.c" -"C:\_projects\abc\src\bdd\cudd\cuddExport.c" -"C:\_projects\abc\src\bdd\cudd\cuddGenCof.c" -"C:\_projects\abc\src\bdd\cudd\cuddGenetic.c" -"C:\_projects\abc\src\bdd\cudd\cuddGroup.c" -"C:\_projects\abc\src\bdd\cudd\cuddHarwell.c" -"C:\_projects\abc\src\bdd\cudd\cuddInit.c" -"C:\_projects\abc\src\bdd\cudd\cuddInteract.c" -"C:\_projects\abc\src\bdd\cudd\cuddLCache.c" -"C:\_projects\abc\src\bdd\cudd\cuddLevelQ.c" -"C:\_projects\abc\src\bdd\cudd\cuddLinear.c" -"C:\_projects\abc\src\bdd\cudd\cuddLiteral.c" -"C:\_projects\abc\src\bdd\cudd\cuddMatMult.c" -"C:\_projects\abc\src\bdd\cudd\cuddPriority.c" -"C:\_projects\abc\src\bdd\cudd\cuddRead.c" -"C:\_projects\abc\src\bdd\cudd\cuddRef.c" -"C:\_projects\abc\src\bdd\cudd\cuddReorder.c" -"C:\_projects\abc\src\bdd\cudd\cuddSat.c" -"C:\_projects\abc\src\bdd\cudd\cuddSign.c" -"C:\_projects\abc\src\bdd\cudd\cuddSolve.c" -"C:\_projects\abc\src\bdd\cudd\cuddSplit.c" -"C:\_projects\abc\src\bdd\cudd\cuddSubsetHB.c" -"C:\_projects\abc\src\bdd\cudd\cuddSubsetSP.c" -"C:\_projects\abc\src\bdd\cudd\cuddSymmetry.c" -"C:\_projects\abc\src\bdd\cudd\cuddTable.c" -"C:\_projects\abc\src\bdd\cudd\cuddUtil.c" -"C:\_projects\abc\src\bdd\cudd\cuddWindow.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddCount.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddFuncs.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddGroup.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddIsop.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddLin.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddMisc.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddPort.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddReord.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddSetop.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddSymm.c" -"C:\_projects\abc\src\bdd\cudd\cuddZddUtil.c" -"C:\_projects\abc\src\bdd\epd\epd.c" -"C:\_projects\abc\src\bdd\mtr\mtrBasic.c" -"C:\_projects\abc\src\bdd\mtr\mtrGroup.c" -"C:\_projects\abc\src\bdd\parse\parseCore.c" -"C:\_projects\abc\src\bdd\parse\parseStack.c" -"C:\_projects\abc\src\bdd\dsd\dsdApi.c" -"C:\_projects\abc\src\bdd\dsd\dsdCheck.c" -"C:\_projects\abc\src\bdd\dsd\dsdLocal.c" -"C:\_projects\abc\src\bdd\dsd\dsdMan.c" -"C:\_projects\abc\src\bdd\dsd\dsdProc.c" -"C:\_projects\abc\src\bdd\dsd\dsdTree.c" -"C:\_projects\abc\src\bdd\reo\reoApi.c" -"C:\_projects\abc\src\bdd\reo\reoCore.c" -"C:\_projects\abc\src\bdd\reo\reoProfile.c" -"C:\_projects\abc\src\bdd\reo\reoSift.c" -"C:\_projects\abc\src\bdd\reo\reoSwap.c" -"C:\_projects\abc\src\bdd\reo\reoTest.c" -"C:\_projects\abc\src\bdd\reo\reoTransfer.c" -"C:\_projects\abc\src\bdd\reo\reoUnits.c" -"C:\_projects\abc\src\sop\mvc\mvc.c" -"C:\_projects\abc\src\sop\mvc\mvcApi.c" -"C:\_projects\abc\src\sop\mvc\mvcCompare.c" -"C:\_projects\abc\src\sop\mvc\mvcContain.c" -"C:\_projects\abc\src\sop\mvc\mvcCover.c" -"C:\_projects\abc\src\sop\mvc\mvcCube.c" -"C:\_projects\abc\src\sop\mvc\mvcDivide.c" -"C:\_projects\abc\src\sop\mvc\mvcDivisor.c" -"C:\_projects\abc\src\sop\mvc\mvcList.c" -"C:\_projects\abc\src\sop\mvc\mvcLits.c" -"C:\_projects\abc\src\sop\mvc\mvcMan.c" -"C:\_projects\abc\src\sop\mvc\mvcOpAlg.c" -"C:\_projects\abc\src\sop\mvc\mvcOpBool.c" -"C:\_projects\abc\src\sop\mvc\mvcPrint.c" -"C:\_projects\abc\src\sop\mvc\mvcSort.c" -"C:\_projects\abc\src\sop\mvc\mvcUtils.c" -"C:\_projects\abc\src\sop\ft\ftFactor.c" -"C:\_projects\abc\src\sop\ft\ftPrint.c" -"C:\_projects\abc\src\sat\asat\added.c" -"C:\_projects\abc\src\sat\asat\solver.c" -"C:\_projects\abc\src\sat\msat\msatActivity.c" -"C:\_projects\abc\src\sat\msat\msatClause.c" -"C:\_projects\abc\src\sat\msat\msatClauseVec.c" -"C:\_projects\abc\src\sat\msat\msatMem.c" -"C:\_projects\abc\src\sat\msat\msatOrderJ.c" -"C:\_projects\abc\src\sat\msat\msatQueue.c" -"C:\_projects\abc\src\sat\msat\msatRead.c" -"C:\_projects\abc\src\sat\msat\msatSolverApi.c" -"C:\_projects\abc\src\sat\msat\msatSolverCore.c" -"C:\_projects\abc\src\sat\msat\msatSolverIo.c" -"C:\_projects\abc\src\sat\msat\msatSolverSearch.c" -"C:\_projects\abc\src\sat\msat\msatSort.c" -"C:\_projects\abc\src\sat\msat\msatVec.c" -"C:\_projects\abc\src\sat\fraig\fraigApi.c" -"C:\_projects\abc\src\sat\fraig\fraigCanon.c" -"C:\_projects\abc\src\sat\fraig\fraigFanout.c" -"C:\_projects\abc\src\sat\fraig\fraigFeed.c" -"C:\_projects\abc\src\sat\fraig\fraigMan.c" -"C:\_projects\abc\src\sat\fraig\fraigMem.c" -"C:\_projects\abc\src\sat\fraig\fraigNode.c" -"C:\_projects\abc\src\sat\fraig\fraigPrime.c" -"C:\_projects\abc\src\sat\fraig\fraigSat.c" -"C:\_projects\abc\src\sat\fraig\fraigTable.c" -"C:\_projects\abc\src\sat\fraig\fraigUtil.c" -"C:\_projects\abc\src\sat\fraig\fraigVec.c" -"C:\_projects\abc\src\sat\sim\simMan.c" -"C:\_projects\abc\src\sat\sim\simSat.c" -"C:\_projects\abc\src\sat\sim\simSupp.c" -"C:\_projects\abc\src\sat\sim\simSym.c" -"C:\_projects\abc\src\sat\sim\simUnate.c" -"C:\_projects\abc\src\sat\sim\simUtils.c" -"C:\_projects\abc\src\opt\fxu\fxu.c" -"C:\_projects\abc\src\opt\fxu\fxuCreate.c" -"C:\_projects\abc\src\opt\fxu\fxuHeapD.c" -"C:\_projects\abc\src\opt\fxu\fxuHeapS.c" -"C:\_projects\abc\src\opt\fxu\fxuList.c" -"C:\_projects\abc\src\opt\fxu\fxuMatrix.c" -"C:\_projects\abc\src\opt\fxu\fxuPair.c" -"C:\_projects\abc\src\opt\fxu\fxuPrint.c" -"C:\_projects\abc\src\opt\fxu\fxuReduce.c" -"C:\_projects\abc\src\opt\fxu\fxuSelect.c" -"C:\_projects\abc\src\opt\fxu\fxuSingle.c" -"C:\_projects\abc\src\opt\fxu\fxuUpdate.c" -"C:\_projects\abc\src\opt\rwr\rwrCut.c" -"C:\_projects\abc\src\opt\rwr\rwrEva.c" -"C:\_projects\abc\src\opt\rwr\rwrExp.c" -"C:\_projects\abc\src\opt\rwr\rwrLib.c" -"C:\_projects\abc\src\opt\rwr\rwrMan.c" -"C:\_projects\abc\src\opt\rwr\rwrUtil.c" -"C:\_projects\abc\src\map\fpga\fpga.c" -"C:\_projects\abc\src\map\fpga\fpgaCore.c" -"C:\_projects\abc\src\map\fpga\fpgaCreate.c" -"C:\_projects\abc\src\map\fpga\fpgaCut.c" -"C:\_projects\abc\src\map\fpga\fpgaCutUtils.c" -"C:\_projects\abc\src\map\fpga\fpgaFanout.c" -"C:\_projects\abc\src\map\fpga\fpgaLib.c" -"C:\_projects\abc\src\map\fpga\fpgaMatch.c" -"C:\_projects\abc\src\map\fpga\fpgaTime.c" -"C:\_projects\abc\src\map\fpga\fpgaTruth.c" -"C:\_projects\abc\src\map\fpga\fpgaUtils.c" -"C:\_projects\abc\src\map\fpga\fpgaVec.c" -"C:\_projects\abc\src\map\mapper\mapper.c" -"C:\_projects\abc\src\map\mapper\mapperCanon.c" "C:\_projects\abc\src\map\mapper\mapperCore.c" -"C:\_projects\abc\src\map\mapper\mapperCreate.c" "C:\_projects\abc\src\map\mapper\mapperCut.c" -"C:\_projects\abc\src\map\mapper\mapperCutUtils.c" -"C:\_projects\abc\src\map\mapper\mapperFanout.c" -"C:\_projects\abc\src\map\mapper\mapperLib.c" -"C:\_projects\abc\src\map\mapper\mapperMatch.c" -"C:\_projects\abc\src\map\mapper\mapperRefs.c" -"C:\_projects\abc\src\map\mapper\mapperSuper.c" -"C:\_projects\abc\src\map\mapper\mapperTable.c" -"C:\_projects\abc\src\map\mapper\mapperTime.c" -"C:\_projects\abc\src\map\mapper\mapperTree.c" -"C:\_projects\abc\src\map\mapper\mapperTruth.c" -"C:\_projects\abc\src\map\mapper\mapperUtils.c" -"C:\_projects\abc\src\map\mapper\mapperVec.c" -"C:\_projects\abc\src\map\mio\mio.c" -"C:\_projects\abc\src\map\mio\mioApi.c" -"C:\_projects\abc\src\map\mio\mioFunc.c" -"C:\_projects\abc\src\map\mio\mioRead.c" -"C:\_projects\abc\src\map\mio\mioUtils.c" -"C:\_projects\abc\src\map\super\super.c" -"C:\_projects\abc\src\map\super\superAnd.c" -"C:\_projects\abc\src\map\super\superGate.c" -"C:\_projects\abc\src\map\super\superWrite.c" -"C:\_projects\abc\src\misc\extra\extraUtilBdd.c" -"C:\_projects\abc\src\misc\extra\extraUtilBitMatrix.c" -"C:\_projects\abc\src\misc\extra\extraUtilFile.c" -"C:\_projects\abc\src\misc\extra\extraUtilMemory.c" -"C:\_projects\abc\src\misc\extra\extraUtilMisc.c" -"C:\_projects\abc\src\misc\extra\extraUtilProgress.c" -"C:\_projects\abc\src\misc\extra\extraUtilReader.c" -"C:\_projects\abc\src\misc\st\st.c" -"C:\_projects\abc\src\misc\st\stmm.c" -"C:\_projects\abc\src\misc\util\cpu_stats.c" -"C:\_projects\abc\src\misc\util\cpu_time.c" -"C:\_projects\abc\src\misc\util\datalimit.c" -"C:\_projects\abc\src\misc\util\getopt.c" -"C:\_projects\abc\src\misc\util\pathsearch.c" -"C:\_projects\abc\src\misc\util\safe_mem.c" -"C:\_projects\abc\src\misc\util\strsav.c" -"C:\_projects\abc\src\misc\util\texpand.c" -"C:\_projects\abc\src\base\abc\abcRefactor.c" -"C:\_projects\abc\src\base\abc\abcRewrite.c" ] -Creating command line "cl.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C4.tmp" -Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C5.tmp" with contents +Creating command line "cl.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1976.tmp" +Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1977.tmp" with contents [ kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /incremental:no /pdb:"Release/abc.pdb" /machine:I386 /out:"_TEST/abc.exe" .\Release\abc.obj @@ -297,8 +37,10 @@ kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32 .\Release\abcNetlist.obj .\Release\abcPrint.obj .\Release\abcReconv.obj +.\Release\abcRefactor.obj .\Release\abcRefs.obj .\Release\abcRenode.obj +.\Release\abcRewrite.obj .\Release\abcSat.obj .\Release\abcSeq.obj .\Release\abcSeqRetime.obj @@ -536,291 +278,15 @@ kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32 .\Release\safe_mem.obj .\Release\strsav.obj .\Release\texpand.obj -.\Release\abcRefactor.obj -.\Release\abcRewrite.obj +.\Release\rwrPrint.obj ] -Creating command line "link.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C5.tmp" +Creating command line "link.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1977.tmp" <h3>Output Window</h3> Compiling... -abc.c -abcAig.c -abcAttach.c -abcCheck.c -abcCollapse.c -abcCreate.c -abcDfs.c -abcDsd.c -abcFanio.c -abcFpga.c -abcFraig.c -abcFunc.c -abcFxu.c -abcLatch.c -abcMap.c -abcMinBase.c -abcMiter.c -abcNames.c -abcNetlist.c -abcPrint.c -abcReconv.c -abcRefs.c -abcRenode.c -abcSat.c -abcSeq.c -abcSeqRetime.c -abcShow.c -abcSop.c -abcStrash.c -abcSweep.c -abcTiming.c -abcUnreach.c -abcUtil.c -abcVerify.c -cmd.c -cmdAlias.c -cmdApi.c -cmdFlag.c -cmdHist.c -cmdUtils.c -io.c -ioRead.c -ioReadBench.c -ioReadBlif.c -ioReadEdif.c -ioReadPla.c -ioReadVerilog.c -ioUtil.c -ioWriteBench.c -ioWriteBlif.c -ioWriteCnf.c -ioWritePla.c -main.c -mainFrame.c -mainInit.c -mainUtils.c -cuddAddAbs.c -cuddAddApply.c -cuddAddFind.c -cuddAddInv.c -cuddAddIte.c -cuddAddNeg.c -cuddAddWalsh.c -cuddAndAbs.c -cuddAnneal.c -cuddApa.c -C:\_projects\abc\src\bdd\cudd\cuddApa.c(181) : warning C4244: 'return' : conversion from 'unsigned long ' to 'unsigned short ', possible loss of data -C:\_projects\abc\src\bdd\cudd\cuddApa.c(213) : warning C4244: 'return' : conversion from 'unsigned long ' to 'unsigned short ', possible loss of data -C:\_projects\abc\src\bdd\cudd\cuddApa.c(530) : warning C4244: '=' : conversion from 'unsigned short ' to 'unsigned char ', possible loss of data -C:\_projects\abc\src\bdd\cudd\cuddApa.c(588) : warning C4244: '=' : conversion from 'unsigned short ' to 'unsigned char ', possible loss of data -cuddAPI.c -cuddApprox.c -cuddBddAbs.c -cuddBddCorr.c -cuddBddIte.c -cuddBridge.c -cuddCache.c -C:\_projects\abc\src\bdd\cudd\cuddCache.c(902) : warning C4146: unary minus operator applied to unsigned type, result still unsigned -cuddCheck.c -cuddClip.c -cuddCof.c -cuddCompose.c -cuddDecomp.c -cuddEssent.c -cuddExact.c -cuddExport.c -cuddGenCof.c -cuddGenetic.c -cuddGroup.c -C:\_projects\abc\src\bdd\cudd\cuddGroup.c(2062) : warning C4018: '<=' : signed/unsigned mismatch -cuddHarwell.c -cuddInit.c -cuddInteract.c -cuddLCache.c -C:\_projects\abc\src\bdd\cudd\cuddLCache.c(1387) : warning C4146: unary minus operator applied to unsigned type, result still unsigned -cuddLevelQ.c -cuddLinear.c -cuddLiteral.c -cuddMatMult.c -cuddPriority.c -cuddRead.c -cuddRef.c -cuddReorder.c -C:\_projects\abc\src\bdd\cudd\cuddReorder.c(395) : warning C4146: unary minus operator applied to unsigned type, result still unsigned -cuddSat.c -C:\_projects\abc\src\bdd\cudd\cuddReorder.c(2016) : warning C4700: local variable 'minLevel' used without having been initialized -C:\_projects\abc\src\bdd\cudd\cuddReorder.c(2020) : warning C4700: local variable 'maxLevel' used without having been initialized -cuddSign.c -cuddSolve.c -cuddSplit.c -cuddSubsetHB.c -cuddSubsetSP.c -cuddSymmetry.c -cuddTable.c -C:\_projects\abc\src\bdd\cudd\cuddTable.c(1822) : warning C4018: '<' : signed/unsigned mismatch -C:\_projects\abc\src\bdd\cudd\cuddTable.c(1927) : warning C4018: '<' : signed/unsigned mismatch -C:\_projects\abc\src\bdd\cudd\cuddTable.c(2235) : warning C4018: '<' : signed/unsigned mismatch -C:\_projects\abc\src\bdd\cudd\cuddTable.c(2303) : warning C4018: '<' : signed/unsigned mismatch -C:\_projects\abc\src\bdd\cudd\cuddTable.c(2358) : warning C4146: unary minus operator applied to unsigned type, result still unsigned -cuddUtil.c -cuddWindow.c -cuddZddCount.c -cuddZddFuncs.c -cuddZddGroup.c -cuddZddIsop.c -cuddZddLin.c -cuddZddMisc.c -cuddZddPort.c -cuddZddReord.c -cuddZddSetop.c -cuddZddSymm.c -cuddZddUtil.c -epd.c -mtrBasic.c -mtrGroup.c -parseCore.c -parseStack.c -dsdApi.c -dsdCheck.c -dsdLocal.c -dsdMan.c -dsdProc.c -dsdTree.c -reoApi.c -reoCore.c -reoProfile.c -reoSift.c -reoSwap.c -reoTest.c -reoTransfer.c -reoUnits.c -mvc.c -mvcApi.c -mvcCompare.c -mvcContain.c -mvcCover.c -mvcCube.c -mvcDivide.c -mvcDivisor.c -mvcList.c -mvcLits.c -mvcMan.c -mvcOpAlg.c -mvcOpBool.c -mvcPrint.c -mvcSort.c -mvcUtils.c -ftFactor.c -ftPrint.c -added.c -solver.c -msatActivity.c -msatClause.c -msatClauseVec.c -msatMem.c -msatOrderJ.c -msatQueue.c -msatRead.c -msatSolverApi.c -msatSolverCore.c -msatSolverIo.c -msatSolverSearch.c -msatSort.c -msatVec.c -fraigApi.c -fraigCanon.c -fraigFanout.c -fraigFeed.c -fraigMan.c -fraigMem.c -fraigNode.c -fraigPrime.c -fraigSat.c -fraigTable.c -fraigUtil.c -fraigVec.c -simMan.c -simSat.c -simSupp.c -simSym.c -simUnate.c -simUtils.c -fxu.c -fxuCreate.c -fxuHeapD.c -fxuHeapS.c -fxuList.c -fxuMatrix.c -fxuPair.c -fxuPrint.c -fxuReduce.c -fxuSelect.c -fxuSingle.c -fxuUpdate.c -rwrCut.c -rwrEva.c -rwrExp.c -rwrLib.c -rwrMan.c -rwrUtil.c -fpga.c -fpgaCore.c -fpgaCreate.c -fpgaCut.c -fpgaCutUtils.c -fpgaFanout.c -fpgaLib.c -fpgaMatch.c -fpgaTime.c -fpgaTruth.c -fpgaUtils.c -fpgaVec.c -mapper.c -mapperCanon.c mapperCore.c -mapperCreate.c mapperCut.c -mapperCutUtils.c -mapperFanout.c -mapperLib.c -mapperMatch.c -mapperRefs.c -mapperSuper.c -mapperTable.c -mapperTime.c -mapperTree.c -mapperTruth.c -mapperUtils.c -mapperVec.c -mio.c -mioApi.c -mioFunc.c -mioRead.c -mioUtils.c -super.c -superAnd.c -superGate.c -superWrite.c -extraUtilBdd.c -extraUtilBitMatrix.c -extraUtilFile.c -extraUtilMemory.c -extraUtilMisc.c -extraUtilProgress.c -extraUtilReader.c -st.c -stmm.c -cpu_stats.c -cpu_time.c -datalimit.c -getopt.c -pathsearch.c -safe_mem.c -strsav.c -texpand.c -abcRefactor.c -abcRewrite.c Linking... -Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C7.tmp" with contents +Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1979.tmp" with contents [ /nologo /o"Release/abc.bsc" .\Release\abc.sbr @@ -844,8 +310,10 @@ Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C7.tmp" with cont .\Release\abcNetlist.sbr .\Release\abcPrint.sbr .\Release\abcReconv.sbr +.\Release\abcRefactor.sbr .\Release\abcRefs.sbr .\Release\abcRenode.sbr +.\Release\abcRewrite.sbr .\Release\abcSat.sbr .\Release\abcSeq.sbr .\Release\abcSeqRetime.sbr @@ -1083,16 +551,15 @@ Creating temporary file "C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C7.tmp" with cont .\Release\safe_mem.sbr .\Release\strsav.sbr .\Release\texpand.sbr -.\Release\abcRefactor.sbr -.\Release\abcRewrite.sbr] -Creating command line "bscmake.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP15C7.tmp" +.\Release\rwrPrint.sbr] +Creating command line "bscmake.exe @C:\DOCUME~1\alanmi\LOCALS~1\Temp\RSP1979.tmp" Creating browse info file... <h3>Output Window</h3> <h3>Results</h3> -abc.exe - 0 error(s), 15 warning(s) +abc.exe - 0 error(s), 0 warning(s) </pre> </body> </html> diff --git a/src/base/abc/abc.c b/src/base/abc/abc.c index be813996..dfe2f4d4 100644 --- a/src/base/abc/abc.c +++ b/src/base/abc/abc.c @@ -1323,34 +1323,26 @@ int Abc_CommandRewrite( Abc_Frame_t * pAbc, int argc, char ** argv ) Abc_Ntk_t * pNtk; int c; bool fVerbose; + bool fPrecompute; // external functions - extern void * Abc_NtkManRwrStart( char * pFileName ); - extern void Abc_NtkManRwrStop( void * p ); + extern void Rwr_Precompute(); extern int Abc_NtkRewrite( Abc_Ntk_t * pNtk ); -/* - { - void * p; - int fFlag = 0; - if ( fFlag ) - p = Abc_NtkManRwrStart( NULL ); - else - p = Abc_NtkManRwrStart( "data.aaa" ); - Abc_NtkManRwrStop( p ); - return 0; - } -*/ pNtk = Abc_FrameReadNet(pAbc); pOut = Abc_FrameReadOut(pAbc); pErr = Abc_FrameReadErr(pAbc); // set defaults - fVerbose = 0; + fVerbose = 0; + fPrecompute = 0; util_getopt_reset(); - while ( ( c = util_getopt( argc, argv, "vh" ) ) != EOF ) + while ( ( c = util_getopt( argc, argv, "zvh" ) ) != EOF ) { switch ( c ) { + case 'z': + fPrecompute ^= 1; + break; case 'v': fVerbose ^= 1; break; @@ -1361,6 +1353,12 @@ int Abc_CommandRewrite( Abc_Frame_t * pAbc, int argc, char ** argv ) } } + if ( fPrecompute ) + { + Rwr_Precompute(); + return 0; + } + if ( pNtk == NULL ) { fprintf( pErr, "Empty network.\n" ); diff --git a/src/base/abc/abcAttach.c b/src/base/abc/abcAttach.c index 950ecc1d..47e911c9 100644 --- a/src/base/abc/abcAttach.c +++ b/src/base/abc/abcAttach.c @@ -144,7 +144,7 @@ int Abc_NtkAttach( Abc_Ntk_t * pNtk ) pNode->pData = pNode->pCopy, pNode->pCopy = NULL; pNtk->Type = ABC_NTK_LOGIC_MAP; Extra_MmFlexStop( pNtk->pManFunc, 0 ); - pNtk->pManFunc = NULL; + pNtk->pManFunc = pGenlib; printf( "Library gates are successfully attached to the nodes.\n" ); diff --git a/src/base/abc/abcRefs.c b/src/base/abc/abcRefs.c index 764dc165..c3561028 100644 --- a/src/base/abc/abcRefs.c +++ b/src/base/abc/abcRefs.c @@ -46,6 +46,8 @@ int Abc_NodeMffcSize( Abc_Obj_t * pNode ) int nConeSize1, nConeSize2; assert( !Abc_ObjIsComplement( pNode ) ); assert( Abc_ObjIsNode( pNode ) ); + if ( Abc_ObjFaninNum(pNode) == 0 ) + return 0; nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference assert( nConeSize1 == nConeSize2 ); @@ -69,6 +71,8 @@ int Abc_NodeMffcLabel( Abc_Obj_t * pNode ) int nConeSize1, nConeSize2; assert( !Abc_ObjIsComplement( pNode ) ); assert( Abc_ObjIsNode( pNode ) ); + if ( Abc_ObjFaninNum(pNode) == 0 ) + return 0; nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference nConeSize2 = Abc_NodeRefDeref( pNode, 1, 1 ); // reference assert( nConeSize1 == nConeSize2 ); diff --git a/src/base/abc/abcRewrite.c b/src/base/abc/abcRewrite.c index 437448de..2c4c8c55 100644 --- a/src/base/abc/abcRewrite.c +++ b/src/base/abc/abcRewrite.c @@ -50,7 +50,9 @@ int Abc_NtkRewrite( Abc_Ntk_t * pNtk ) assert( Abc_NtkIsAig(pNtk) ); // start the rewriting manager - p = Rwr_ManStart( "data.aaa" ); + p = Rwr_ManStart( 0 ); + if ( p == NULL ) + return 0; Rwr_ManPrepareNetwork( p, pNtk ); // resynthesize each node once diff --git a/src/map/fpga/fpga.h b/src/map/fpga/fpga.h index 62a93a75..9dad1670 100644 --- a/src/map/fpga/fpga.h +++ b/src/map/fpga/fpga.h @@ -80,10 +80,7 @@ extern void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ); extern void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ); extern void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ); extern void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ); -extern void Fpga_ManSetTree( Fpga_Man_t * p, int fTree ); -extern void Fpga_ManSetPower( Fpga_Man_t * p, int fPower ); extern void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ); -extern void Fpga_ManSetResyn( Fpga_Man_t * p, int fResynthesis ); extern void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ); extern void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ); extern void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ); @@ -95,7 +92,6 @@ extern void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNode extern void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ); extern void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ); extern void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ); -extern void Fpga_ManSetSequential( Fpga_Man_t * p, int fSequential ); extern void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ); extern int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ); diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c index 457c2384..b181e997 100644 --- a/src/map/fpga/fpgaCore.c +++ b/src/map/fpga/fpgaCore.c @@ -17,18 +17,12 @@ ***********************************************************************/ #include "fpgaInt.h" -//#include "res.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static int Fpga_MappingPostProcess( Fpga_Man_t * p ); - -extern void Fpga_Experiment( Fpga_Man_t * p ); -extern void Fpga_MappingCutsSeq( Fpga_Man_t * p ); -extern void Fpga_MappingLValues( Fpga_Man_t * pMan, int fVerbose ); - +static int Fpga_MappingPostProcess( Fpga_Man_t * p ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -51,35 +45,18 @@ extern void Fpga_MappingLValues( Fpga_Man_t * pMan, int fVerbose ); ***********************************************************************/ int Fpga_Mapping( Fpga_Man_t * p ) { - int clk; + int clk, clkTotal = clock(); // collect the nodes reachable from POs in the DFS order (including the choices) p->vAnds = Fpga_MappingDfs( p, 1 ); Fpga_ManReportChoices( p ); // recomputes levels Fpga_MappingSetChoiceLevels( p ); - if ( p->fSequential ) - { -// Fpga_MappingCutsSeq( p ); - Fpga_MappingCuts( p ); -//clk = clock(); -// Fpga_MappingLValues( p, p->fVerbose ); -//PRT( "Time", clock() - clk ); - return 0; - } - // compute the cuts of nodes in the DFS order clk = clock(); Fpga_MappingCuts( p ); p->timeCuts = clock() - clk; -// Fpga_MappingSortByLevel( p, p->vAnds, 1 ); - - // derive the truth tables - clk = clock(); -// Fpga_MappingTruths( p ); - p->timeTruth = clock() - clk; - // match the truth tables to the supergates clk = clock(); if ( !Fpga_MappingMatches( p, 1 ) ) @@ -94,10 +71,7 @@ int Fpga_Mapping( Fpga_Man_t * p ) return 0; p->timeRecover = clock() - clk; } - - // perform resynthesis -// if ( p->fResynthesis ) -// Res_Resynthesize( p, p->DelayLimit, p->AreaLimit, p->TimeLimit, 1 ); +PRT( "Total mapping time", clock() - clkTotal ); // print the AI-graph used for mapping //Fpga_ManShow( p, "test" ); @@ -124,128 +98,59 @@ int Fpga_Mapping( Fpga_Man_t * p ) int Fpga_MappingPostProcess( Fpga_Man_t * p ) { float aAreaTotalPrev, aAreaTotalCur, aAreaTotalCur2; - float aSwitchTotalPrev, aSwitchTotalCur; int Iter, clk; - + // compute area, set references, and collect nodes used in the mapping + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); if ( p->fVerbose ) { -printf( "Iteration %dD : Area = %11.1f ", 0, Fpga_MappingArea( p ) ); +printf( "Iteration %dD : Area = %11.1f ", 0, aAreaTotalCur ); PRT( "Time", p->timeMatch ); } - -// Fpga_MappingExplore( p ); -// p->fAreaGlo = Fpga_MappingArea( p ); -// return; - - -// aAreaTotalCur = FPGA_FLOAT_LARGE; - aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); - Iter = 1; do { clk = clock(); // save the previous area flow aAreaTotalPrev = aAreaTotalCur; - // compute the required times and the fanouts Fpga_TimeComputeRequiredGlobal( p ); // remap topologically Fpga_MappingMatches( p, 0 ); // get the resulting area - aAreaTotalCur = Fpga_MappingArea( p ); +// aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); + aAreaTotalCur = Fpga_MappingAreaTrav( p ); + // note that here we do not update the reference counter + // for some reason, this works better on benchmarks if ( p->fVerbose ) { printf( "Iteration %dF : Area = %11.1f ", Iter++, aAreaTotalCur ); PRT( "Time", clock() - clk ); } - if ( p->fPower ) - aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); // quit if this iteration reduced area flow by less than 1% } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); - -// Fpga_MappingExplore( p ); -// p->fAreaGlo = Fpga_MappingArea( p ); -// return; - - -/* - // compute the area of each cut - aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); - // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p ); - // perform experiment - Fpga_Experiment( p ); -*/ - - - // compute the area of each cut - aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); - aAreaTotalCur2 = Fpga_MappingComputeCutAreas( p ); + // update reference counters + aAreaTotalCur2 = Fpga_MappingSetRefsAndArea( p ); assert( aAreaTotalCur == aAreaTotalCur2 ); - -// aAreaTotalCur = FPGA_FLOAT_LARGE; -// Iter = 1; do { clk = clock(); // save the previous area flow aAreaTotalPrev = aAreaTotalCur; - // compute the required times and the fanouts Fpga_TimeComputeRequiredGlobal( p ); // remap topologically Fpga_MappingMatchesArea( p ); // get the resulting area - aAreaTotalCur = Fpga_MappingArea( p ); + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); if ( p->fVerbose ) { printf( "Iteration %dA : Area = %11.1f ", Iter++, aAreaTotalCur ); PRT( "Time", clock() - clk ); } - if ( p->fPower ) - { - aSwitchTotalPrev = aSwitchTotalCur; - aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); - } // quit if this iteration reduced area flow by less than 1% } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); - - - if ( p->fPower ) - { - do { -clk = clock(); - // save the previous area flow - aAreaTotalPrev = aAreaTotalCur; - - // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p ); - // remap topologically - Fpga_MappingMatchesSwitch( p ); - // get the resulting area - aAreaTotalCur = Fpga_MappingArea( p ); -if ( p->fVerbose ) -{ -printf( "Iteration %dS : Area = %11.1f ", Iter++, aAreaTotalCur ); -PRT( "Time", clock() - clk ); -} - aSwitchTotalPrev = aSwitchTotalCur; - aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); - // quit if this iteration reduced area flow by less than 1% - } while ( aSwitchTotalPrev > 1.01 * aSwitchTotalCur ); - } - -/* - // compute the area of each cut - aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); - // compute the required times and the fanouts - Fpga_TimeComputeRequiredGlobal( p ); - // perform experiment - Fpga_Experiment( p ); -*/ p->fAreaGlo = aAreaTotalCur; return 1; } diff --git a/src/map/fpga/fpgaCreate.c b/src/map/fpga/fpgaCreate.c index 1e654ded..f3abbedb 100644 --- a/src/map/fpga/fpgaCreate.c +++ b/src/map/fpga/fpgaCreate.c @@ -58,10 +58,7 @@ void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ) { p->t void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ) { p->timeTotal = Time; } void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ) { p->ppOutputNames = ppNames; } void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ) { p->pInputArrivals = pArrivals; } -void Fpga_ManSetTree( Fpga_Man_t * p, int fTree ) { p->fTree = fTree; } -void Fpga_ManSetPower( Fpga_Man_t * p, int fPower ) { p->fPower = fPower; } void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ) { p->fAreaRecovery = fAreaRecovery;} -void Fpga_ManSetResyn( Fpga_Man_t * p, int fResynthesis ) { p->fResynthesis = fResynthesis; } void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ) { p->DelayLimit = DelayLimit; } void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ) { p->AreaLimit = AreaLimit; } void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ) { p->TimeLimit = TimeLimit; } @@ -69,7 +66,6 @@ void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ) { p void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ) { p->nChoices = nChoices; } void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ) { p->fVerbose = fVerbose; } void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ) { p->nLatches = nLatches; } -void Fpga_ManSetSequential( Fpga_Man_t * p, int fSequential ) { p->fSequential = fSequential; } void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ) { p->pFileName = pFileName; } /**Function************************************************************* @@ -170,8 +166,6 @@ Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) p->nVarsMax = p->pLutLib->LutMax; p->fVerbose = fVerbose; p->fAreaRecovery = 1; - p->fTree = 0; - p->fRefCount = 1; p->fEpsilon = (float)0.001; Fpga_TableCreate( p ); @@ -181,13 +175,14 @@ Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) p->mmCuts = Extra_MmFixedStart( sizeof(Fpga_Cut_t) ); assert( p->nVarsMax > 0 ); - Fpga_MappingSetupTruthTables( p->uTruths ); +// Fpga_MappingSetupTruthTables( p->uTruths ); // make sure the constant node will get index -1 p->nNodes = -1; // create the constant node p->pConst1 = Fpga_NodeCreate( p, NULL, NULL ); - p->vNodesAll = Fpga_NodeVecAlloc( 100 ); + p->vNodesAll = Fpga_NodeVecAlloc( 1000 ); + p->vMapping = Fpga_NodeVecAlloc( 1000 ); // create the PI nodes p->nInputs = nInputs; @@ -216,27 +211,23 @@ Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) void Fpga_ManFree( Fpga_Man_t * p ) { // Fpga_ManStats( p ); - // int i; // for ( i = 0; i < p->vNodesAll->nSize; i++ ) // Fpga_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts ); // Fpga_NodeVecFree( p->pConst1->vFanouts ); + if ( p->vMapping ) + Fpga_NodeVecFree( p->vMapping ); if ( p->vAnds ) Fpga_NodeVecFree( p->vAnds ); if ( p->vNodesAll ) Fpga_NodeVecFree( p->vNodesAll ); Extra_MmFixedStop( p->mmNodes, 0 ); Extra_MmFixedStop( p->mmCuts, 0 ); + FREE( p->ppOutputNames ); FREE( p->pInputArrivals ); FREE( p->pInputs ); FREE( p->pOutputs ); FREE( p->pBins ); - FREE( p->ppOutputNames ); - if ( p->pSimInfo ) - { - FREE( p->pSimInfo[0] ); - FREE( p->pSimInfo ); - } FREE( p ); } @@ -316,19 +307,18 @@ Fpga_Node_t * Fpga_NodeCreate( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p // set the level of this node if ( p1 ) { +#ifdef FPGA_ALLOCATE_FANOUT // create the fanout info Fpga_NodeAddFaninFanout( Fpga_Regular(p1), pNode ); Fpga_NodeAddFaninFanout( Fpga_Regular(p2), pNode ); +#endif // compute the level pNode->Level = 1 + FPGA_MAX(Fpga_Regular(p1)->Level, Fpga_Regular(p2)->Level); pNode->fInv = Fpga_NodeIsSimComplement(p1) & Fpga_NodeIsSimComplement(p2); } - // reference the inputs (will be used to compute the number of fanouts) - if ( p->fRefCount ) - { - if ( p1 ) Fpga_NodeRef(p1); - if ( p2 ) Fpga_NodeRef(p2); - } + // reference the inputs + if ( p1 ) Fpga_NodeRef(p1); + if ( p2 ) Fpga_NodeRef(p2); return pNode; } diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c index 27079953..5b5fbe69 100644 --- a/src/map/fpga/fpgaCut.c +++ b/src/map/fpga/fpgaCut.c @@ -206,8 +206,9 @@ Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Nod Fpga_Node_t * pTemp; Fpga_Cut_t * pList, * pList1, * pList2; Fpga_Cut_t * pCut; - int fPivot1 = p->fTree && (Fpga_NodeReadRef(pNode->p1)>2); - int fPivot2 = p->fTree && (Fpga_NodeReadRef(pNode->p2)>2); + int fTree = 0; + int fPivot1 = fTree && (Fpga_NodeReadRef(pNode->p1)>2); + int fPivot2 = fTree && (Fpga_NodeReadRef(pNode->p2)>2); // if the cuts are computed return them if ( pNode->pCuts ) diff --git a/src/map/fpga/fpgaFanout.c b/src/map/fpga/fpgaFanout.c index 50809f65..0a34ff43 100644 --- a/src/map/fpga/fpgaFanout.c +++ b/src/map/fpga/fpgaFanout.c @@ -18,6 +18,8 @@ #include "fpgaInt.h" +#ifdef MAP_ALLOCATE_FANOUT + //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// @@ -26,7 +28,6 @@ /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// - /**Function************************************************************* Synopsis [Add the fanout to the node.] @@ -136,4 +137,5 @@ int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ) /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/map/fpga/fpgaInt.h b/src/map/fpga/fpgaInt.h index 63308d53..95203378 100644 --- a/src/map/fpga/fpgaInt.h +++ b/src/map/fpga/fpgaInt.h @@ -35,6 +35,9 @@ /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// +// uncomment to have fanouts represented in the mapping graph +//#define FPGA_ALLOCATE_FANOUT 1 + //////////////////////////////////////////////////////////////////////// /// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// @@ -104,10 +107,11 @@ struct Fpga_ManStruct_t_ Fpga_Node_t ** pOutputs; // the array of outputs int nOutputs; // the number of outputs int nNodes; // the total number of nodes - Fpga_Node_t * pConst1; // the constant 1 node - Fpga_NodeVec_t * vAnds; // the array of pointer to nodes by number - Fpga_NodeVec_t * vNodesAll; // the array of pointer to nodes by number int nLatches; // the number of latches in the circuit + Fpga_Node_t * pConst1; // the constant 1 node + Fpga_NodeVec_t * vNodesAll; // the nodes by number + Fpga_NodeVec_t * vAnds; // the nodes reachable from COs + Fpga_NodeVec_t * vMapping; // the nodes used in the current mapping // info about the original circuit char * pFileName; // the file name @@ -116,12 +120,12 @@ struct Fpga_ManStruct_t_ // mapping parameters int nVarsMax; // the max number of variables - int fTree; // the flag to enable tree mapping - int fPower; // the flag to enable power optimization +// int fTree; // the flag to enable tree mapping +// int fPower; // the flag to enable power optimization int fAreaRecovery; // the flag to use area flow as the first parameter int fVerbose; // the verbosiness flag - int fRefCount; // enables reference counting - int fSequential; // use sequential mapping +// int fRefCount; // enables reference counting +// int fSequential; // use sequential mapping int nTravIds; // support of choice nodes @@ -133,16 +137,12 @@ struct Fpga_ManStruct_t_ // the supergate library Fpga_LutLib_t * pLutLib; // the current LUT library - unsigned uTruths[6][2]; // the elementary truth tables +// unsigned uTruths[6][2]; // the elementary truth tables // the memory managers Extra_MmFixed_t * mmNodes; // the memory manager for nodes Extra_MmFixed_t * mmCuts; // the memory manager for cuts - // simulation info from the FRAIG manager - int nSimRounds; // the number of words in the simulation info - unsigned ** pSimInfo; // the simulation info for each PI - // resynthesis parameters int fResynthesis; // the resynthesis flag float fRequiredGlo; // the global required times @@ -203,12 +203,14 @@ struct Fpga_NodeStruct_t_ Fpga_Node_t * p2; // the second child Fpga_Node_t * pNextE; // the next functionally equivalent node Fpga_Node_t * pRepr; // the representative of the functionally equivalent class -// Fpga_NodeVec_t * vFanouts; // the array of fanouts of the node +#ifdef FPGA_ALLOCATE_FANOUT // representation of node's fanouts Fpga_Node_t * pFanPivot; // the first fanout of this node Fpga_Node_t * pFanFanin1; // the next fanout of p1 Fpga_Node_t * pFanFanin2; // the next fanout of p2 +// Fpga_NodeVec_t * vFanouts; // the array of fanouts of the gate +#endif // the delay information float tRequired; // the best area flow @@ -335,8 +337,6 @@ extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ); extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ); extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); extern void Fpga_TimePropagateArrival( Fpga_Man_t * p ); -/*=== fpgaTruth.c ===============================================================*/ -extern void Fpga_MappingTruths( Fpga_Man_t * pMan ); /*=== fpgaVec.c =============================================================*/ extern Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ); extern void Fpga_NodeVecFree( Fpga_NodeVec_t * p ); @@ -359,23 +359,11 @@ extern void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ); /*=== fpgaUtils.c ===============================================================*/ extern Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ); extern Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ); -extern Fpga_NodeVec_t * Fpga_MappingDfsCutsNode( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); -//extern Sat_IntVec_t * Fpga_MappingDfsNodesSat( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes ); -extern Fpga_NodeVec_t * Fpga_MappingDfsCuts( Fpga_Man_t * pMan ); extern int Fpga_CountLevels( Fpga_Man_t * pMan ); -extern int Fpga_CountLevelsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots ); -extern void Fpga_MappingMarkUsed( Fpga_Man_t * pMan ); extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ); extern float Fpga_MappingArea( Fpga_Man_t * pMan ); -extern float Fpga_MappingComputeCutAreas( Fpga_Man_t * pMan ); +extern float Fpga_MappingAreaTrav( Fpga_Man_t * pMan ); extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ); -extern Fpga_NodeVec_t * Fpga_MappingCollectRefed( Fpga_Man_t * pMan ); -extern int Fpga_MappingCountLevels( Fpga_Man_t * pMan ); -extern void Fpga_MappingUnmark( Fpga_Man_t * pMan ); -extern void Fpga_MappingUnmark_rec( Fpga_Node_t * pNode ); -extern void Fpga_MappingMark_rec( Fpga_Node_t * pNode ); -extern void Fpga_MappedMark_rec( Fpga_Node_t * pNode ); -extern void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ); extern void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ); extern void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ); extern void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ); @@ -383,7 +371,7 @@ extern void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVe extern Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ); extern Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ); extern float Fpga_MappingPrintSwitching( Fpga_Man_t * pMan ); -extern int Fpga_GetMaxLevel( Fpga_Man_t * pMan ); +extern int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ); extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c index 599662f7..63ee682d 100644 --- a/src/map/fpga/fpgaMatch.c +++ b/src/map/fpga/fpgaMatch.c @@ -777,59 +777,6 @@ float Fpga_FindBestNode( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes, Fpga_Node_t ** return Gain; } -/**function************************************************************* - - synopsis [Performs area minimization using a heuristic algorithm.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -void Fpga_MappingExplore( Fpga_Man_t * p ) -{ - Fpga_Cut_t * pCutBest; - Fpga_Node_t * pNodeBest; - Fpga_NodeVec_t * vNodes; - float Area, Gain, CutArea1, CutArea2; - int i; - - // compute the arrival times - Fpga_TimePropagateArrival( p ); - p->fRequiredGlo = Fpga_TimeComputeArrivalMax( p ); - Fpga_TimeComputeRequired( p, p->fRequiredGlo ); - - // assign the refs - Area = Fpga_MappingSetRefsAndArea( p ); - // collect the nodes - vNodes = Fpga_MappingCollectRefed( p ); - // find the best node to update - for ( i = 0; Gain = Fpga_FindBestNode(p, vNodes, &pNodeBest, &pCutBest); i++ ) - { - // update the node - assert( pNodeBest->pCutBest != pCutBest ); - // deref the current cut - CutArea1 = Fpga_CutDeref( p, pNodeBest, pNodeBest->pCutBest, 0 ); - // ref the new cut - CutArea2 = Fpga_CutRef( p, pNodeBest, pCutBest, 0 ); - assert( CutArea1 - CutArea2 == Gain ); - printf( "Iteration %2d: Gain = %5.2f.\n", i, Gain ); - // update the node - pNodeBest->pCutBest = pCutBest; - // collect new nodes - Fpga_NodeVecFree( vNodes ); - vNodes = Fpga_MappingCollectRefed( p ); - // compute the arrival and required times - Fpga_TimePropagateArrival( p ); - Fpga_TimeComputeRequired( p, p->fRequiredGlo ); - } - - -} - - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/fpga/fpgaTime.c b/src/map/fpga/fpgaTime.c index 066ae215..6cbe16f9 100644 --- a/src/map/fpga/fpgaTime.c +++ b/src/map/fpga/fpgaTime.c @@ -128,21 +128,15 @@ void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ) ***********************************************************************/ void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ) { - Fpga_NodeVec_t * vNodes; int i; - // clean the required times and the fanout counts for all nodes for ( i = 0; i < p->vAnds->nSize; i++ ) p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE; - // set the required times for the POs for ( i = 0; i < p->nOutputs; i++ ) Fpga_Regular(p->pOutputs[i])->tRequired = fRequired; - // collect nodes reachable from POs in the DFS order through the best cuts - vNodes = Fpga_MappingDfsCuts( p ); - Fpga_TimePropagateRequired( p, vNodes ); - Fpga_NodeVecFree( vNodes ); + Fpga_TimePropagateRequired( p, p->vMapping ); } /**Function************************************************************* @@ -163,7 +157,9 @@ void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) int i, k; // sorts the nodes in the decreasing order of levels - Fpga_MappingSortByLevel( p, vNodes, 0 ); +// Fpga_MappingSortByLevel( p, vNodes, 0 ); + // the nodes area already sorted in Fpga_MappingSetRefsAndArea() + // go through the nodes in the reverse topological order for ( k = 0; k < vNodes->nSize; k++ ) { diff --git a/src/map/fpga/fpgaUtils.c b/src/map/fpga/fpgaUtils.c index fc67d52b..bf334afa 100644 --- a/src/map/fpga/fpgaUtils.c +++ b/src/map/fpga/fpgaUtils.c @@ -24,15 +24,10 @@ static void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ); static void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); -static float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); -static int Fpga_MappingCountLevels_rec( Fpga_Node_t * pNode ); -static void Fpga_MappingMarkUsed_rec( Fpga_Node_t * pNode ); static int Fpga_MappingCompareOutputDelay( int * pOut1, int * pOut2 ); -static float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); -static Fpga_Man_t * s_pMan = NULL; - static void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ); -static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ); +static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ); +static Fpga_Man_t * s_pMan = NULL; //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -131,184 +126,6 @@ Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes return vNodes; } - -/**Function************************************************************* - - Synopsis [Computes the number of logic levels not counting PIs/POs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CountLevels( Fpga_Man_t * pMan ) -{ - int i, LevelsMax, LevelsCur; - // perform the traversal - LevelsMax = -1; - for ( i = 0; i < pMan->nOutputs; i++ ) - { - LevelsCur = Fpga_Regular(pMan->pOutputs[i])->Level; - if ( LevelsMax < LevelsCur ) - LevelsMax = LevelsCur; - } - return LevelsMax; -} - -/**Function************************************************************* - - Synopsis [Computes the number of logic levels not counting PIs/POs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_CountLevelsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots ) -{ - int i, LevelsMax, LevelsCur; - // perform the traversal - LevelsMax = -1; - for ( i = 0; i < nRoots; i++ ) - { - LevelsCur = Fpga_Regular(ppRoots[i])->Level; - if ( LevelsMax < LevelsCur ) - LevelsMax = LevelsCur; - } - return LevelsMax; -} - -/**Function************************************************************* - - Synopsis [Computes the DFS ordering of the nodes visible in current mapping.] - - Description [The node is visible if it appears as a root of one of the best - cuts (that is cuts selected for the current mapping).] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingDfsCuts( Fpga_Man_t * pMan ) -{ - Fpga_NodeVec_t * vNodes; - int i; - // perform the traversal - vNodes = Fpga_NodeVecAlloc( 100 ); - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingDfsCuts_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes ); - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - return vNodes; -} - -/**Function************************************************************* - - Synopsis [Computes the DFS ordering of the nodes visible in current mapping.] - - Description [The node is visible if it appears as a root of one of the best - cuts (that is cuts selected for the current mapping).] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingDfsCutsNode( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) -{ - Fpga_NodeVec_t * vNodes; - int i; - // perform the traversal - vNodes = Fpga_NodeVecAlloc( 100 ); - Fpga_MappingDfsCuts_rec( pNode, vNodes ); - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - return vNodes; -} - -/**Function************************************************************* - - Synopsis [Recursively computes the DFS ordering of the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ) -{ - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( !Fpga_NodeIsAnd(pNode) ) - return; - if ( pNode->fMark0 ) - return; - assert( pNode->pCutBest != NULL ); - // visit the transitive fanin of the selected cut - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - Fpga_MappingDfsCuts_rec( pNode->pCutBest->ppLeaves[i], vNodes ); - // make sure the node is not visited through the fanin nodes - assert( pNode->fMark0 == 0 ); - // mark the node as visited - pNode->fMark0 = 1; - // add the node to the list - Fpga_NodeVecPush( vNodes, pNode ); -} - - -/**Function************************************************************* - - Synopsis [Marks the nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingMarkUsed( Fpga_Man_t * pMan ) -{ - int i; - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingMarkUsed_rec( Fpga_Regular(pMan->pOutputs[i]) ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingMarkUsed_rec( Fpga_Node_t * pNode ) -{ - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fUsed ) - return; - pNode->fUsed = 1; - if ( !Fpga_NodeIsAnd(pNode) ) - return; - assert( pNode->pCutBest != NULL ); - // visit the transitive fanin of the selected cut - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - Fpga_MappingMarkUsed_rec( pNode->pCutBest->ppLeaves[i] ); -} - - - /**Function************************************************************* Synopsis [] @@ -346,22 +163,16 @@ float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ) ***********************************************************************/ float Fpga_MappingArea( Fpga_Man_t * pMan ) { - Fpga_NodeVec_t * vNodes; + Fpga_Node_t * pNode; float aTotal; int i; // perform the traversal aTotal = 0; - vNodes = Fpga_NodeVecAlloc( 100 ); - for ( i = 0; i < pMan->nOutputs; i++ ) + for ( i = 0; i < pMan->vMapping->nSize; i++ ) { - aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes ); - // add the area for single-input nodes (if any) at the POs -// if ( Fpga_NodeIsVar(pMan->pOutputs[i]) || Fpga_IsComplement(pMan->pOutputs[i]) ) -// aTotal += pMan->pLutLib->pLutAreas[1]; + pNode = pMan->vMapping->pArray[i]; + aTotal += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; } - for ( i = 0; i < vNodes->nSize; i++ ) - vNodes->pArray[i]->fMark0 = 0; - Fpga_NodeVecFree( vNodes ); return aTotal; } @@ -401,10 +212,9 @@ float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec return aArea; } - /**Function************************************************************* - Synopsis [Sets the correct reference counts for the mapping.] + Synopsis [Computes the area of the current mapping.] Description [] @@ -413,55 +223,22 @@ float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec SeeAlso [] ***********************************************************************/ -float Fpga_MappingComputeCutAreas( Fpga_Man_t * pMan ) +float Fpga_MappingAreaTrav( Fpga_Man_t * pMan ) { Fpga_NodeVec_t * vNodes; - Fpga_Node_t * pNode; - float Area = 0; + float aTotal; int i; - // collect nodes reachable from POs in the DFS order through the best cuts - vNodes = Fpga_MappingDfsCuts( pMan ); + // perform the traversal + aTotal = 0; + vNodes = Fpga_NodeVecAlloc( 100 ); + for ( i = 0; i < pMan->nOutputs; i++ ) + aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes ); for ( i = 0; i < vNodes->nSize; i++ ) - { - pNode = vNodes->pArray[i]; - pNode->pCutBest->aFlow = Fpga_CutGetAreaRefed( pMan, pNode->pCutBest ); - Area += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; - } + vNodes->pArray[i]->fMark0 = 0; Fpga_NodeVecFree( vNodes ); - return Area; + return aTotal; } -/**Function************************************************************* - - Synopsis [Sets the correct reference counts for the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) -{ - Fpga_Node_t * pNode; - float aArea; - int i; - // clean all references - for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) - pMan->vNodesAll->pArray[i]->nRefs = 0; - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - for ( i = 0; i < pMan->nOutputs; i++ ) - { - pNode = Fpga_Regular(pMan->pOutputs[i]); - if ( pNode == pMan->pConst1 ) - continue; - aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode ); - pNode->nRefs++; - } - return aArea; -} /**Function************************************************************* @@ -474,7 +251,7 @@ float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) SeeAlso [] ***********************************************************************/ -float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) +float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Node_t ** ppStore ) { float aArea; int i; @@ -484,217 +261,63 @@ float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) if ( !Fpga_NodeIsAnd(pNode) ) return 0; assert( pNode->pCutBest != NULL ); + // store the node in the structure by level + pNode->pData0 = (char *)ppStore[pNode->Level]; + ppStore[pNode->Level] = pNode; // visit the transitive fanin of the selected cut aArea = pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i] ); + aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i], ppStore ); return aArea; } /**Function************************************************************* - Synopsis [Collect the referenced nodes.] + Synopsis [Sets the correct reference counts for the mapping.] - Description [] + Description [Collects the nodes in reverse topological order + and places in them in array pMan->vMapping.] SideEffects [] SeeAlso [] ***********************************************************************/ -Fpga_NodeVec_t * Fpga_MappingCollectRefed( Fpga_Man_t * pMan ) +float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) { - Fpga_NodeVec_t * vNodes; - int i; - vNodes = Fpga_NodeVecAlloc( 100 ); - for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) - { - if ( Fpga_NodeIsVar(pMan->vNodesAll->pArray[i]) ) - continue; - if ( pMan->vNodesAll->pArray[i]->nRefs ) - Fpga_NodeVecPush( vNodes, pMan->vNodesAll->pArray[i] ); - } - return vNodes; -} - -/**Function************************************************************* - - Synopsis [Computes the number of logic levels not counting PIs/POs.] + Fpga_Node_t * pNode, ** ppStore; + float aArea; + int i, LevelMax; - Description [] - - SideEffects [Note that this procedure will reassign the levels assigned - originally by NodeCreate() because it counts the number of levels with - choices differently!] + // clean all references + for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) + pMan->vNodesAll->pArray[i]->nRefs = 0; - SeeAlso [] + // allocate place to store the nodes + LevelMax = Fpga_MappingMaxLevel( pMan ); + ppStore = ALLOC( Fpga_Node_t *, LevelMax + 1 ); + memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) ); -***********************************************************************/ -int Fpga_MappingCountLevels( Fpga_Man_t * pMan ) -{ - int i, LevelsMax, LevelsCur; - // perform the traversal - LevelsMax = -1; - for ( i = 0; i < pMan->nOutputs; i++ ) - { - LevelsCur = Fpga_MappingCountLevels_rec( Fpga_Regular(pMan->pOutputs[i]) ); - if ( LevelsMax < LevelsCur ) - LevelsMax = LevelsCur; - } + // collect nodes reachable from POs in the DFS order through the best cuts + aArea = 0; for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); - return LevelsMax; -} - -/**Function************************************************************* - - Synopsis [Recursively computes the number of logic levels.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Fpga_MappingCountLevels_rec( Fpga_Node_t * pNode ) -{ - int Level1, Level2; - assert( !Fpga_IsComplement(pNode) ); - if ( !Fpga_NodeIsAnd(pNode) ) { - pNode->Level = 0; - return 0; + pNode = Fpga_Regular(pMan->pOutputs[i]); + if ( pNode == pMan->pConst1 ) + continue; + aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore ); + pNode->nRefs++; } - if ( pNode->fMark0 ) - return pNode->Level; - pNode->fMark0 = 1; - // visit the transitive fanin - Level1 = Fpga_MappingCountLevels_rec( Fpga_Regular(pNode->p1) ); - Level2 = Fpga_MappingCountLevels_rec( Fpga_Regular(pNode->p2) ); - // set the number of levels - pNode->Level = 1 + ((Level1>Level2)? Level1: Level2); - return pNode->Level; -} - -/**Function************************************************************* - - Synopsis [Unmarks the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingUnmark( Fpga_Man_t * pMan ) -{ - int i; - for ( i = 0; i < pMan->nOutputs; i++ ) - Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); -} - -/**Function************************************************************* - - Synopsis [Recursively unmarks the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingUnmark_rec( Fpga_Node_t * pNode ) -{ - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 == 0 ) - return; - pNode->fMark0 = 0; - if ( !Fpga_NodeIsAnd(pNode) ) - return; - Fpga_MappingUnmark_rec( Fpga_Regular(pNode->p1) ); - Fpga_MappingUnmark_rec( Fpga_Regular(pNode->p2) ); - // visit the equivalent nodes - if ( pNode->pNextE ) - Fpga_MappingUnmark_rec( pNode->pNextE ); -} - -/**Function************************************************************* - - Synopsis [Recursively unmarks the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappingMark_rec( Fpga_Node_t * pNode ) -{ - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 == 1 ) - return; - pNode->fMark0 = 1; - if ( !Fpga_NodeIsAnd(pNode) ) - return; - Fpga_MappingMark_rec( Fpga_Regular(pNode->p1) ); - Fpga_MappingMark_rec( Fpga_Regular(pNode->p2) ); -} - -/**Function************************************************************* - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappedMark_rec( Fpga_Node_t * pNode ) -{ - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 == 1 ) - return; - pNode->fMark0 = 1; - if ( !Fpga_NodeIsAnd(pNode) ) - return; - assert( pNode->pCutBest != NULL ); - // visit the transitive fanin of the selected cut - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - Fpga_MappedMark_rec( pNode->pCutBest->ppLeaves[i] ); + // reconnect the nodes in reverse topological order + pMan->vMapping->nSize = 0; + for ( i = LevelMax; i > 0; i-- ) + for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 ) + Fpga_NodeVecPush( pMan->vMapping, pNode ); + free( ppStore ); + return aArea; } -/**Function************************************************************* - - Synopsis [Recursively unmarks the nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ) -{ - int i; - assert( !Fpga_IsComplement(pNode) ); - if ( pNode->fMark0 == 0 ) - return; - pNode->fMark0 = 0; - if ( !Fpga_NodeIsAnd(pNode) ) - return; - assert( pNode->pCutBest != NULL ); - // visit the transitive fanin of the selected cut - for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) - Fpga_MappedUnmark_rec( pNode->pCutBest->ppLeaves[i] ); -} /**Function************************************************************* @@ -710,7 +333,7 @@ void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ) void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) { Fpga_Node_t * pNode; - int fCompl, Limit, i; + int fCompl, Limit, MaxNameSize, i; int * pSorted; // sort outputs by arrival time @@ -723,15 +346,21 @@ void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) assert( Fpga_MappingCompareOutputDelay( pSorted, pSorted + p->nOutputs - 1 ) <= 0 ); s_pMan = NULL; - // print the latest outputs + // determine max size of the node's name + MaxNameSize = 0; Limit = (p->nOutputs > 5)? 5 : p->nOutputs; for ( i = 0; i < Limit; i++ ) + if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) ) + MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]); + + // print the latest outputs + for ( i = 0; i < Limit; i++ ) { // get the i-th latest output pNode = Fpga_Regular(p->pOutputs[pSorted[i]]); fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]); // print out the best arrival time - printf( "Output %20s : ", p->ppOutputNames[pSorted[i]] ); + printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] ); printf( "Delay = %8.2f ", (double)pNode->pCutBest->tArrival ); if ( fCompl ) printf( "NEG" ); @@ -1169,7 +798,7 @@ float Fpga_MappingPrintSwitching( Fpga_Man_t * p ) SeeAlso [] ***********************************************************************/ -int Fpga_GetMaxLevel( Fpga_Man_t * pMan ) +int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ) { int nLevelMax, i; nLevelMax = 0; @@ -1269,11 +898,11 @@ void Fpga_ManReportChoices( Fpga_Man_t * pMan ) int i, LevelMax1, LevelMax2; // report the number of levels - LevelMax1 = Fpga_GetMaxLevel( pMan ); + LevelMax1 = Fpga_MappingMaxLevel( pMan ); pMan->nTravIds++; for ( i = 0; i < pMan->nOutputs; i++ ) Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 ); - LevelMax2 = Fpga_GetMaxLevel( pMan ); + LevelMax2 = Fpga_MappingMaxLevel( pMan ); // report statistics about choices nChoiceNodes = nChoices = 0; diff --git a/src/map/mapper/mapper.h b/src/map/mapper/mapper.h index 9ef8ee17..1322cdfa 100644 --- a/src/map/mapper/mapper.h +++ b/src/map/mapper/mapper.h @@ -152,8 +152,8 @@ extern void Map_NodeSetChoice( Map_Man_t * pMan, Map_Node_t * pNodeOl /*=== resmCanon.c =============================================================*/ extern int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] ); +extern int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] ); /*=== mapperCut.c =============================================================*/ -extern void Map_MappingCreatePiCuts( Map_Man_t * p ); extern Map_Cut_t * Map_CutAlloc( Map_Man_t * p ); /*=== mapperCutUtils.c =============================================================*/ extern void Map_CutCreateFromNode( Map_Man_t * p, Map_Super_t * pSuper, int iRoot, unsigned uPhaseRoot, diff --git a/src/map/mapper/mapperCanon.c b/src/map/mapper/mapperCanon.c index c5186c7e..4937fd0e 100644 --- a/src/map/mapper/mapperCanon.c +++ b/src/map/mapper/mapperCanon.c @@ -154,6 +154,95 @@ void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[] } } +/**Function************************************************************* + + Synopsis [Computes the N-canonical form of the Boolean function.] + + Description [The N-canonical form is defined as the truth table with + the minimum integer value. This function exhaustively enumerates + through the complete set of 2^N phase assignments.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] ) +{ + unsigned uTruth0, uTruth1; + unsigned uCanon0, uCanon1, uCanonBest; + int i, Limit; + + if ( nVarsMax != 5 || nVarsReal < 5 ) + return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes ); + + assert( nVarsMax == 5 ); + uTruth0 = uTruth[0] & 0xFFFF; + uTruth1 = (uTruth[0] >> 16); + if ( uTruth1 == 0 ) + { + uTruthRes[0] = p->uCanons[uTruth0]; + uTruthRes[1] = uTruthRes[0]; + Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0]; + for ( i = 0; i < Limit; i++ ) + puPhases[i] = p->uPhases[uTruth0][i]; + return Limit; + } + else if ( uTruth0 == 0 ) + { + uTruthRes[0] = p->uCanons[uTruth1]; + uTruthRes[1] = uTruthRes[0]; + Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1]; + for ( i = 0; i < Limit; i++ ) + { + puPhases[i] = p->uPhases[uTruth1][i]; + puPhases[i] |= (1 << 4); + } + return Limit; + } + uCanon0 = p->uCanons[uTruth0]; + uCanon1 = p->uCanons[uTruth1]; + if ( uCanon0 && uCanon1 && uCanon0 > uCanon1 ) // using nCanon1 as the main one + { + assert( p->pCounters[uTruth1] > 0 ); + uCanonBest = 0xFFFF; + for ( i = 0; i < p->pCounters[uTruth1]; i++ ) + { + uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 ); + if ( uCanonBest > uCanon0 ) + uCanonBest = uCanon0; + } + uTruthRes[0] = (uCanon1 << 16) | uCanonBest; + uTruthRes[1] = uTruthRes[0]; + Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1]; + for ( i = 0; i < Limit; i++ ) + puPhases[i] = p->uPhases[uTruth1][i]; + return Limit; + } + else if ( uCanon0 && uCanon1 && uCanon0 < uCanon1 ) + { + assert( p->pCounters[uTruth0] > 0 ); + uCanonBest = 0xFFFF; + for ( i = 0; i < p->pCounters[uTruth0]; i++ ) + { + uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 ); + if ( uCanonBest > uCanon1 ) + uCanonBest = uCanon1; + } + uTruthRes[0] = (uCanon0 << 16) | uCanonBest; + uTruthRes[1] = uTruthRes[0]; + Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0]; + for ( i = 0; i < Limit; i++ ) + { + puPhases[i] = p->uPhases[uTruth0][i]; + puPhases[i] |= (1 << 4); + } + return Limit; + } + else + return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/mapper/mapperCore.c b/src/map/mapper/mapperCore.c index 0014d48f..16cbfd5c 100644 --- a/src/map/mapper/mapperCore.c +++ b/src/map/mapper/mapperCore.c @@ -69,6 +69,7 @@ int Map_Mapping( Map_Man_t * p ) Map_MappingTruths( p ); p->timeTruth = clock() - clk; ////////////////////////////////////////////////////////////////////// +//PRT( "Truths", clock() - clk ); ////////////////////////////////////////////////////////////////////// // compute the minimum-delay mapping diff --git a/src/map/mapper/mapperCreate.c b/src/map/mapper/mapperCreate.c index eb938847..dc056f34 100644 --- a/src/map/mapper/mapperCreate.c +++ b/src/map/mapper/mapperCreate.c @@ -196,6 +196,9 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) p->fEpsilon = (float)0.001; assert( p->nVarsMax > 0 ); + if ( p->nVarsMax == 5 ) + Extra_Truth4VarN( &p->uCanons, &p->uPhases, &p->pCounters, 16 ); + // start various data structures Map_TableCreate( p ); Map_MappingSetupTruthTables( p->uTruths ); @@ -211,8 +214,6 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) p->vNodesAll = Map_NodeVecAlloc( 100 ); p->vNodesTemp = Map_NodeVecAlloc( 100 ); p->vMapping = Map_NodeVecAlloc( 100 ); - p->vInside = Map_NodeVecAlloc( 100 ); - p->vFanins = Map_NodeVecAlloc( 100 ); p->vVisited = Map_NodeVecAlloc( 100 ); // create the PI nodes @@ -245,10 +246,6 @@ void Map_ManFree( Map_Man_t * p ) // for ( i = 0; i < p->vNodesAll->nSize; i++ ) // Map_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts ); // Map_NodeVecFree( p->pConst1->vFanouts ); - if ( p->vInside ) - Map_NodeVecFree( p->vInside ); - if ( p->vFanins ) - Map_NodeVecFree( p->vFanins ); if ( p->vAnds ) Map_NodeVecFree( p->vAnds ); if ( p->vNodesAll ) @@ -259,6 +256,9 @@ void Map_ManFree( Map_Man_t * p ) Map_NodeVecFree( p->vMapping ); if ( p->vVisited ) Map_NodeVecFree( p->vVisited ); + if ( p->uCanons ) free( p->uCanons ); + if ( p->uPhases ) free( p->uPhases ); + if ( p->pCounters ) free( p->pCounters ); Extra_MmFixedStop( p->mmNodes, 0 ); Extra_MmFixedStop( p->mmCuts, 0 ); FREE( p->pInputArrivals ); @@ -266,8 +266,6 @@ void Map_ManFree( Map_Man_t * p ) FREE( p->pOutputs ); FREE( p->pBins ); FREE( p->ppOutputNames ); - if ( p->pSimInfo ) FREE( p->pSimInfo[0] ); - FREE( p->pSimInfo ); FREE( p ); } @@ -357,9 +355,11 @@ Map_Node_t * Map_NodeCreate( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ) // set the level of this node if ( p1 ) { +#ifdef MAP_ALLOCATE_FANOUT // create the fanout info Map_NodeAddFaninFanout( Map_Regular(p1), pNode ); Map_NodeAddFaninFanout( Map_Regular(p2), pNode ); +#endif pNode->Level = 1 + MAP_MAX(Map_Regular(pNode->p1)->Level, Map_Regular(pNode->p2)->Level); pNode->fInv = Map_NodeIsSimComplement(p1) & Map_NodeIsSimComplement(p2); } diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c index 1f3c8074..0c3a0910 100644 --- a/src/map/mapper/mapperCut.c +++ b/src/map/mapper/mapperCut.c @@ -65,6 +65,7 @@ static Map_Cut_t * Map_CutSortCuts( Map_Man_t * pMan, Map_CutTable_t * p, M static int Map_CutList2Array( Map_Cut_t ** pArray, Map_Cut_t * pList ); static Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ); +static unsigned Map_CutComputeTruth( Map_Man_t * p, Map_Cut_t * pCut, Map_Cut_t * pTemp0, Map_Cut_t * pTemp1, int fComp0, int fComp1 ); // iterator through all the cuts of the list #define Map_ListForEachCut( pList, pCut ) \ @@ -78,7 +79,6 @@ static Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ); pCut = pCut2, \ pCut2 = pCut? pCut->pNext: NULL ) - //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// @@ -114,6 +114,7 @@ void Map_MappingCuts( Map_Man_t * p ) Map_Node_t * pNode; Map_Cut_t * pCut; int nCuts, nNodes, i; + int clk = clock(); // set the elementary cuts for the PI variables assert( p->nVarsMax > 1 && p->nVarsMax < 7 ); for ( i = 0; i < p->nInputs; i++ ) @@ -121,10 +122,10 @@ void Map_MappingCuts( Map_Man_t * p ) pCut = Map_CutAlloc( p ); pCut->nLeaves = 1; pCut->ppLeaves[0] = p->pInputs[i]; -// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; p->pInputs[i]->pCuts = pCut; p->pInputs[i]->pCutBest[0] = NULL; // negative polarity is not mapped p->pInputs[i]->pCutBest[1] = pCut; // positive polarity is a trivial cut + pCut->uTruth = 0xAAAAAAAA; // the first variable "10101010" pCut->M[0].AreaFlow = 0.0; pCut->M[1].AreaFlow = 0.0; } @@ -148,8 +149,9 @@ void Map_MappingCuts( Map_Man_t * p ) if ( p->fVerbose ) { nCuts = Map_MappingCountAllCuts(p); - printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n", + printf( "Nodes = %6d. Total %d-feasible cuts = %d. Per node = %.1f. ", p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + PRT( "Time", clock() - clk ); } // print the cuts for the first primary output @@ -158,48 +160,6 @@ void Map_MappingCuts( Map_Man_t * p ) /**Function************************************************************* - Synopsis [Performs technology mapping for variable-size-LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Map_MappingCreatePiCuts( Map_Man_t * p ) -{ - Map_Cut_t * pCut; - int i; - - // set the elementary cuts for the PI variables - for ( i = 0; i < p->nInputs; i++ ) - { - pCut = Map_CutAlloc( p ); - pCut->nLeaves = 1; - pCut->ppLeaves[0] = p->pInputs[i]; -// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; - p->pInputs[i]->pCuts = pCut; - p->pInputs[i]->pCutBest[1] = pCut; - p->pInputs[i]->pCutBest[0] = pCut; - // set the input arrival times -// p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i]; - - // set the input arrival times - pCut = p->pInputs[i]->pCutBest[1]; - pCut->M[1].tArrive = p->pInputArrivals[i]; - pCut->M[1].tArrive.Worst = MAP_MAX( pCut->M[1].tArrive.Rise, pCut->M[1].tArrive.Fall ); - // set the arrival times of the negative phases of the PI nodes - pCut = p->pInputs[i]->pCutBest[0]; - pCut->M[0].tArrive.Rise = p->pInputArrivals[i].Fall + p->pSuperLib->tDelayInv.Rise; - pCut->M[0].tArrive.Fall = p->pInputArrivals[i].Rise + p->pSuperLib->tDelayInv.Fall; - pCut->M[0].tArrive.Worst = MAP_MAX( pCut->M[0].tArrive.Rise, pCut->M[0].tArrive.Fall ); - - } -} - -/**Function************************************************************* - Synopsis [Computes the cuts for one node.] Description [] @@ -242,7 +202,7 @@ Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t * pCut = Map_CutAlloc( p ); pCut->nLeaves = 1; pCut->ppLeaves[0] = pNode; -// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + pCut->uTruth = 0xAAAAAAAA; // append (it is important that the elementary cut is appended first) pCut->pNext = pList; // set at the node @@ -392,6 +352,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable, // add data to the cut pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); +// if ( p->nVarsMax == 5 ) +// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 ); // add it to the corresponding list pCut->pNext = pLists[pCut->nLeaves]; pLists[pCut->nLeaves] = pCut; @@ -424,6 +386,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable, // add data to the cut pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); +// if ( p->nVarsMax == 5 ) +// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 ); // add it to the corresponding list pCut->pNext = pLists[pCut->nLeaves]; pLists[pCut->nLeaves] = pCut; @@ -459,6 +423,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable, // add data to the cut pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); +// if ( p->nVarsMax == 5 ) +// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 ); // add it to the corresponding list pCut->pNext = pLists[pCut->nLeaves]; pLists[pCut->nLeaves] = pCut; @@ -725,12 +691,26 @@ int Map_MappingCountAllCuts( Map_Man_t * pMan ) Map_Node_t * pNode; Map_Cut_t * pCut; int i, nCuts; +// int nCuts55 = 0, nCuts5x = 0, nCuts4x = 0, nCuts3x = 0; nCuts = 0; for ( i = 0; i < pMan->nBins; i++ ) for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) if ( pCut->nLeaves > 1 ) // skip the elementary cuts + { nCuts++; +/* + if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 && Map_CutRegular(pCut->pTwo)->nLeaves == 5 ) + nCuts55++; + if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 || Map_CutRegular(pCut->pTwo)->nLeaves == 5 ) + nCuts5x++; + else if ( Map_CutRegular(pCut->pOne)->nLeaves == 4 || Map_CutRegular(pCut->pTwo)->nLeaves == 4 ) + nCuts4x++; + else if ( Map_CutRegular(pCut->pOne)->nLeaves == 3 || Map_CutRegular(pCut->pTwo)->nLeaves == 3 ) + nCuts3x++; +*/ + } +// printf( "Total cuts = %6d. 55 = %6d. 5x = %6d. 4x = %6d. 3x = %6d.\n", nCuts, nCuts55, nCuts5x, nCuts4x, nCuts3x ); return nCuts; } @@ -926,7 +906,6 @@ Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node Map_Cut_t * pCut; int Place, i; // int clk; - // check the cut Place = Map_CutTableLookup( p, ppNodes, nNodes ); if ( Place == -1 ) @@ -937,13 +916,8 @@ Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node pCut = Map_CutAlloc( pMan ); //pMan->time1 += clock() - clk; pCut->nLeaves = nNodes; -// pCut->fLevel = 0; for ( i = 0; i < nNodes; i++ ) - { pCut->ppLeaves[i] = ppNodes[i]; -// pCut->fLevel += ppNodes[i]->Level; - } -// pCut->fLevel /= nNodes; // add the cut to the table assert( p->pBins[Place] == NULL ); p->pBins[Place] = pCut; @@ -994,12 +968,6 @@ int Map_CutSortCutsCompare( Map_Cut_t ** pC1, Map_Cut_t ** pC2 ) return -1; if ( (*pC1)->nLeaves > (*pC2)->nLeaves ) return 1; -/* - if ( (*pC1)->fLevel < (*pC2)->fLevel ) - return -1; - if ( (*pC1)->fLevel > (*pC2)->fLevel ) - return 1; -*/ return 0; } @@ -1081,7 +1049,6 @@ Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ) // connect these lists *ppListNew = pArray[i]; ppListNew = &pArray[i]->pNext; -//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel ); } //printf( "\n" ); @@ -1090,6 +1057,103 @@ Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ) } +/**Function************************************************************* + + Synopsis [Computes the truth table of the 5-input cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_CutComputeTruth( Map_Man_t * p, Map_Cut_t * pCut, Map_Cut_t * pTemp0, Map_Cut_t * pTemp1, int fComp0, int fComp1 ) +{ + static unsigned ** pPerms53 = NULL; + static unsigned ** pPerms54 = NULL; + + unsigned uPhase, uTruth, uTruth0, uTruth1; + int i, k; + + if ( pPerms53 == NULL ) + { + pPerms53 = (unsigned **)Extra_TruthPerm53(); + pPerms54 = (unsigned **)Extra_TruthPerm54(); + } + + // find the mapping from the old nodes to the new + if ( pTemp0->nLeaves == pCut->nLeaves ) + uTruth0 = pTemp0->uTruth; + else + { + assert( pTemp0->nLeaves < pCut->nLeaves ); + uPhase = 0; + for ( i = 0; i < (int)pTemp0->nLeaves; i++ ) + { + for ( k = 0; k < pCut->nLeaves; k++ ) + if ( pTemp0->ppLeaves[i] == pCut->ppLeaves[k] ) + break; + uPhase |= (1 << k); + } + assert( uPhase < 32 ); + if ( pTemp0->nLeaves == 4 ) + { + if ( uPhase == 31-16 ) // 01111 + uTruth0 = pTemp0->uTruth; + else if ( uPhase == 31-8 ) // 10111 + uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][0]; + else if ( uPhase == 31-4 ) // 11011 + uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][1]; + else if ( uPhase == 31-2 ) // 11101 + uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][2]; + else if ( uPhase == 31-1 ) // 11110 + uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][3]; + else + assert( 0 ); + } + else + uTruth0 = pPerms53[pTemp0->uTruth & 0xFF][uPhase]; + } + uTruth0 = fComp0? ~uTruth0: uTruth0; + + // find the mapping from the old nodes to the new + if ( pTemp1->nLeaves == pCut->nLeaves ) + uTruth1 = pTemp1->uTruth; + else + { + assert( pTemp1->nLeaves < pCut->nLeaves ); + uPhase = 0; + for ( i = 0; i < (int)pTemp1->nLeaves; i++ ) + { + for ( k = 0; k < pCut->nLeaves; k++ ) + if ( pTemp1->ppLeaves[i] == pCut->ppLeaves[k] ) + break; + uPhase |= (1 << k); + } + assert( uPhase < 32 ); + if ( pTemp1->nLeaves == 4 ) + { + if ( uPhase == 31-16 ) // 01111 + uTruth1 = pTemp1->uTruth; + else if ( uPhase == 31-8 ) // 10111 + uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][0]; + else if ( uPhase == 31-4 ) // 11011 + uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][1]; + else if ( uPhase == 31-2 ) // 11101 + uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][2]; + else if ( uPhase == 31-1 ) // 11110 + uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][3]; + else + assert( 0 ); + } + else + uTruth1 = pPerms53[pTemp1->uTruth & 0xFF][uPhase]; + } + uTruth1 = fComp1? ~uTruth1: uTruth1; + uTruth = uTruth0 & uTruth1; + return uTruth; +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/map/mapper/mapperFanout.c b/src/map/mapper/mapperFanout.c index 7bd92ed9..aca29918 100644 --- a/src/map/mapper/mapperFanout.c +++ b/src/map/mapper/mapperFanout.c @@ -18,6 +18,8 @@ #include "mapperInt.h" +#ifdef MAP_ALLOCATE_FANOUT + //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// @@ -26,7 +28,6 @@ /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// - /**Function************************************************************* Synopsis [Add the fanout to the node.] @@ -136,4 +137,5 @@ int Map_NodeGetFanoutNum( Map_Node_t * pNode ) /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/map/mapper/mapperInt.h b/src/map/mapper/mapperInt.h index d4262abb..7d63a804 100644 --- a/src/map/mapper/mapperInt.h +++ b/src/map/mapper/mapperInt.h @@ -36,7 +36,10 @@ //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// - + +// uncomment to have fanouts represented in the mapping graph +//#define MAP_ALLOCATE_FANOUT 1 + //////////////////////////////////////////////////////////////////////// /// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// @@ -123,18 +126,15 @@ struct Map_ManStruct_t_ int nCountsBest[32];// the counter of minterms Map_NodeVec_t * vVisited; // the visited cuts during cut computation - // simulation info from the FRAIG manager - int nSimRounds; // the number of words in the simulation info - unsigned ** pSimInfo; // the simulation info for each PI - - // don't-care computation - Map_NodeVec_t * vInside; // the array of nodes for SDC computation - Map_NodeVec_t * vFanins; // the array of nodes for SDC computation - // the memory managers Extra_MmFixed_t * mmNodes; // the memory manager for nodes Extra_MmFixed_t * mmCuts; // the memory manager for cuts + // precomputed N-canonical forms + unsigned short * uCanons; // N-canonical forms + char ** uPhases; // N-canonical phases + char * pCounters; // counters of phases + // various statistical variables int nChoiceNodes; // the number of choice nodes int nChoices; // the number of all choices @@ -211,27 +211,25 @@ struct Map_NodeStruct_t_ int nRefAct[3]; // estimated fanout for current covering phase, neg and pos and sum float nRefEst[3]; // actual fanout for previous covering phase, neg and pos and sum - // the successors of this node + // connectivity Map_Node_t * p1; // the first child Map_Node_t * p2; // the second child Map_Node_t * pNextE; // the next functionally equivalent node Map_Node_t * pRepr; // the representative of the functionally equivalent class -// Map_NodeVec_t * vFanouts; // the array of fanouts of the node +#ifdef MAP_ALLOCATE_FANOUT // representation of node's fanouts Map_Node_t * pFanPivot; // the first fanout of this node Map_Node_t * pFanFanin1; // the next fanout of p1 Map_Node_t * pFanFanin2; // the next fanout of p2 - - unsigned * pSims; // the simulation info - float SwitchProb; // the switching probability +// Map_NodeVec_t * vFanouts; // the array of fanouts of the gate +#endif // the delay information Map_Time_t tArrival[2]; // the best arrival time of the neg (0) and pos (1) phases Map_Time_t tRequired[2]; // the required time of the neg (0) and pos (1) phases // misc information - Map_Cut_t * pCutOld[2]; // the old mapping for neg and pos phase Map_Cut_t * pCutBest[2]; // the best mapping for neg and pos phase Map_Cut_t * pCuts; // mapping choices for the node (elementary comes first) char * pData0; // temporary storage for the corresponding network node @@ -259,6 +257,7 @@ struct Map_CutStruct_t_ Map_Cut_t * pOne; // the father of this cut Map_Cut_t * pTwo; // the mother of this cut Map_Node_t * ppLeaves[6]; // the leaves of this cut + unsigned uTruth; // truth table for five-input cuts char nLeaves; // the number of leaves char nVolume; // the volume of this cut char fMark; // the mark to denote visited cut diff --git a/src/map/mapper/mapperRefs.c b/src/map/mapper/mapperRefs.c index 334e98c7..e74bab9a 100644 --- a/src/map/mapper/mapperRefs.c +++ b/src/map/mapper/mapperRefs.c @@ -25,7 +25,7 @@ static int Map_NodeIncRefPhaseAct( Map_Node_t * pNode, int fPhase ); static int Map_NodeDecRefPhaseAct( Map_Node_t * pNode, int fPhase ); static float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ); -static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ); +static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_Node_t ** ppStore ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -401,8 +401,9 @@ float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ) Synopsis [Computes actual reference counters.] - Description [Stores all the nodes used in the mapping in the array pMan->vMapping. - The nodes are stored in the random order.] + Description [Collects the nodes used in the mapping in array pMan->vMapping. + Nodes are collected in reverse topological order to facilitate the + computation of required times.] SideEffects [] @@ -411,8 +412,9 @@ float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ) ***********************************************************************/ void Map_MappingSetRefs( Map_Man_t * pMan ) { - Map_Node_t * pNode; - int i, fPhase; + Map_Node_t * pNode, ** ppStore; + int i, fPhase, LevelMax; + // clean all references for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) { @@ -421,18 +423,32 @@ void Map_MappingSetRefs( Map_Man_t * pMan ) pNode->nRefAct[1] = 0; pNode->nRefAct[2] = 0; } + + // find the largest level of a node + LevelMax = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + if ( LevelMax < (int)Map_Regular(pMan->pOutputs[i])->Level ) + LevelMax = Map_Regular(pMan->pOutputs[i])->Level; + + // allocate place to store the nodes + ppStore = ALLOC( Map_Node_t *, LevelMax + 1 ); + memset( ppStore, 0, sizeof(Map_Node_t *) * (LevelMax + 1) ); + // visit nodes reachable from POs in the DFS order through the best cuts - pMan->vMapping->nSize = 0; for ( i = 0; i < pMan->nOutputs; i++ ) { pNode = pMan->pOutputs[i]; fPhase = !Map_IsComplement(pNode); if ( !Map_NodeIsConst(pNode) ) - Map_MappingSetRefs_rec( pMan, pNode ); - // reference count the PO node -// Map_Regular(pNode)->nRefAct[fPhase]++; -// Map_Regular(pNode)->nRefAct[2]++; + Map_MappingSetRefs_rec( pMan, pNode, ppStore ); } + + // reconnect the nodes in reverse topological order + pMan->vMapping->nSize = 0; + for ( i = LevelMax; i >= 0; i-- ) + for ( pNode = ppStore[i]; pNode; pNode = (Map_Node_t *)pNode->pData0 ) + Map_NodeVecPush( pMan->vMapping, pNode ); + free( ppStore ); } /**Function************************************************************* @@ -446,7 +462,7 @@ void Map_MappingSetRefs( Map_Man_t * pMan ) SeeAlso [] ***********************************************************************/ -void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ) +void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_Node_t ** ppStore ) { Map_Cut_t * pCut; Map_Node_t * pNodeR; @@ -459,7 +475,8 @@ void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ) // add the node to the list of all visited nodes if ( pNodeR->nRefAct[2]++ == 0 ) - Map_NodeVecPush( pMan->vMapping, pNodeR ); +// Map_NodeVecPush( pMan->vMapping, pNodeR ); + pNodeR->pData0 = (char *)ppStore[pNodeR->Level], ppStore[pNodeR->Level] = pNodeR; // quit if the node was already visited in this phase if ( pNodeR->nRefAct[fPhase]++ ) @@ -482,7 +499,7 @@ void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ) for ( i = 0; i < pCut->nLeaves; i++ ) { fInvPin = ((uPhase & (1 << i)) > 0); - Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin) ); + Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin), ppStore ); } } diff --git a/src/map/mapper/mapperTime.c b/src/map/mapper/mapperTime.c index 0ff88b0e..f1cafae7 100644 --- a/src/map/mapper/mapperTime.c +++ b/src/map/mapper/mapperTime.c @@ -252,7 +252,9 @@ void Map_TimeComputeRequired( Map_Man_t * p, float fRequired ) // sorts the nodes in the decreasing order of levels // this puts the nodes in reverse topological order - Map_MappingSortByLevel( p, p->vMapping ); +// Map_MappingSortByLevel( p, p->vMapping ); + // the array is already sorted by construction in Map_MappingSetRefs() + Map_TimePropagateRequired( p, p->vMapping ); } diff --git a/src/map/mapper/mapperTruth.c b/src/map/mapper/mapperTruth.c index 97e64920..54fc0391 100644 --- a/src/map/mapper/mapperTruth.c +++ b/src/map/mapper/mapperTruth.c @@ -23,7 +23,7 @@ //////////////////////////////////////////////////////////////////////// static void Map_TruthsCut( Map_Man_t * pMan, Map_Cut_t * pCut ); -static void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] ); +extern void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] ); static void Map_CutsCollect_rec( Map_Cut_t * pCut, Map_NodeVec_t * vVisited ); //////////////////////////////////////////////////////////////////////// @@ -90,18 +90,30 @@ void Map_MappingTruths( Map_Man_t * pMan ) ***********************************************************************/ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) { - unsigned uTruth[2], uCanon[2]; // unsigned uCanon1, uCanon2; + unsigned uTruth[2], uCanon[2]; unsigned char uPhases[16]; + int fUseFast = 1; // generally speaking, 1-input cut can be matched into a wire! if ( pCut->nLeaves == 1 ) return; +/* + if ( p->nVarsMax == 5 ) + { + uTruth[0] = pCut->uTruth; + uTruth[1] = pCut->uTruth; + } + else +*/ Map_TruthsCutOne( p, pCut, uTruth ); // compute the canonical form for the positive phase - Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + if ( fUseFast ) + Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + else + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); pCut->M[1].uPhase = uPhases[0]; p->nCanons++; @@ -111,13 +123,15 @@ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) // compute the canonical form for the negative phase uTruth[0] = ~uTruth[0]; uTruth[1] = ~uTruth[1]; - Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + if ( fUseFast ) + Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + else + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); pCut->M[0].uPhase = uPhases[0]; p->nCanons++; //uCanon2 = uCanon[0] & 0xFFFF; - //assert( p->nVarsMax == 4 ); //Rwt_Man4ExploreCount( uCanon1 < uCanon2 ? uCanon1 : uCanon2 ); diff --git a/src/map/mapper/mapperUtils.c b/src/map/mapper/mapperUtils.c index f8fd1a4c..78885729 100644 --- a/src/map/mapper/mapperUtils.c +++ b/src/map/mapper/mapperUtils.c @@ -405,7 +405,7 @@ void Map_MappingPrintOutputArrivals( Map_Man_t * p ) Map_Time_t * pTimes; Map_Node_t * pNode; int fPhase, Limit, i; - int nOutputs; + int nOutputs, MaxNameSize; int * pSorted; // sort outputs by arrival time @@ -423,16 +423,22 @@ void Map_MappingPrintOutputArrivals( Map_Man_t * p ) assert( Map_MappingCompareOutputDelay( pSorted, pSorted + nOutputs - 1 ) <= 0 ); s_pMan = NULL; - // print the latest outputs + // determine max size of the node's name + MaxNameSize = 0; Limit = (nOutputs > 5)? 5 : nOutputs; for ( i = 0; i < Limit; i++ ) + if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) ) + MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]); + + // print the latest outputs + for ( i = 0; i < Limit; i++ ) { // get the i-th latest output pNode = Map_Regular(p->pOutputs[pSorted[i]]); fPhase =!Map_IsComplement(p->pOutputs[pSorted[i]]); pTimes = pNode->tArrival + fPhase; // print out the best arrival time - printf( "Out %20s : ", p->ppOutputNames[pSorted[i]] ); + printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] ); printf( "Delay = (%5.2f, %5.2f) ", (double)pTimes->Rise, (double)pTimes->Fall ); printf( "%s", fPhase? "POS" : "NEG" ); printf( "\n" ); @@ -1013,136 +1019,6 @@ void Map_MappingReportChoices( Map_Man_t * pMan ) printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); } -/* -void Map_MappingReportChoices( Map_Man_t * pMan ) -{ - Map_Node_t * pNode, * pTemp; - int nChoiceNodes, nChoices; - int i, LevelMax1, LevelMax2; - int DiffMaxTotal, DiffMinTotal, Min, Max; - int CounterByMin[300]={0}, CounterByMax[300]={0}; - - // report the number of levels - LevelMax1 = Map_MappingGetMaxLevel( pMan ); - pMan->nTravIds++; - for ( i = 0; i < pMan->nOutputs; i++ ) -// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 ); - Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); - LevelMax2 = Map_MappingGetMaxLevel( pMan ); - - // report statistics about choices - nChoiceNodes = nChoices = 0; - DiffMaxTotal = DiffMinTotal = 0; - for ( i = 0; i < pMan->vAnds->nSize; i++ ) - { - pNode = pMan->vAnds->pArray[i]; - if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) - { // this is a choice node = the primary node that has equivalent nodes - nChoiceNodes++; - for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) - nChoices++; - // call to compare the levels - Map_MappingGetChoiceLevels( pMan, pNode, pNode->pNextE, &Min, &Max ); - assert( Min < (int)pNode->Level ); - assert( Max < (int)pNode->Level ); - DiffMinTotal += pNode->Level - Max; - DiffMaxTotal += pNode->Level - Min; - - CounterByMin[pNode->Level - Max]++; - CounterByMax[pNode->Level - Min]++; - - } - } - printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); - printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); - printf( "Choice depth: Minimum = %4.2f. Maximum = %4.2f.\n", - ((float)DiffMinTotal)/nChoiceNodes, ((float)DiffMaxTotal)/nChoiceNodes ); - - { - FILE * pTable; - pTable = fopen( "statsc.txt", "a+" ); - fprintf( pTable, "%6d ", pMan->vAnds->nSize ); - fprintf( pTable, "%5d ", LevelMax2 ); - fprintf( pTable, "%5d ", nChoiceNodes ); - fprintf( pTable, "%5d ", nChoices ); - fprintf( pTable, "%5.2f ", ((float)DiffMinTotal)/nChoiceNodes ); - fprintf( pTable, "%5.2f ", ((float)DiffMaxTotal)/nChoiceNodes ); -// fprintf( pTable, "%4.2f\n", (float)(Time)/(float)(CLOCKS_PER_SEC) ); - fprintf( pTable, "\n" ); - fclose( pTable ); - } - - - printf( "Distribution by min/max levels:\n" ); - for ( i = 0; i < LevelMax2; i++ ) - printf( "%3d : %5d %5d\n", i, CounterByMin[i], CounterByMax[i] ); - printf( "\n" ); -} -*/ - -/* -void Map_MappingReportChoices( Map_Man_t * pMan ) -{ - Map_Node_t * pNode, * pTemp; - int nChoiceNodes, nChoices; - int i, LevelMax1, LevelMax2; - int CounterByVol[1000]={0}; - float VolumeAve, Volume; - - // report the number of levels - LevelMax1 = Map_MappingGetMaxLevel( pMan ); - pMan->nTravIds++; - for ( i = 0; i < pMan->nOutputs; i++ ) - Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 ); -// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); - LevelMax2 = Map_MappingGetMaxLevel( pMan ); - - // report statistics about choices - nChoiceNodes = nChoices = 0; - VolumeAve = 0.0; - for ( i = 0; i < pMan->vAnds->nSize; i++ ) - { - pNode = pMan->vAnds->pArray[i]; - if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) - { // this is a choice node = the primary node that has equivalent nodes - nChoiceNodes++; - for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) - nChoices++; - Volume = Map_MappingGetChoiceVolumes( pMan, pNode, pNode->pNextE ); - VolumeAve += Volume; - assert( Volume < 1000 ); - CounterByVol[(int)Volume]++; - } - } - printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); - printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); - printf( "Average volume = %5.4f.\n", VolumeAve/nChoiceNodes ); -*/ -/* - { - FILE * pTable; - pTable = fopen( "statsv.txt", "a+" ); - fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,1) ); - fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,0) ); - fprintf( pTable, "%5d ", LevelMax1 ); - fprintf( pTable, " " ); - fprintf( pTable, "%5d ", nChoiceNodes ); - fprintf( pTable, "%5d ", nChoices ); - fprintf( pTable, " " ); - fprintf( pTable, "%5.4f ", VolumeAve/nChoiceNodes ); - fprintf( pTable, "\n" ); - fclose( pTable ); - } - printf( "Distribution by volume:\n" ); - for ( i = 0; i < 1000; i++ ) - if ( CounterByVol[i] > 0 ) - printf( "%3d : %5d\n", i, CounterByVol[i] ); - printf( "\n" ); -*/ -/* -} -*/ - /**Function************************************************************* Synopsis [Computes the maximum and minimum levels of the choice nodes.] diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h index 7f4ec8d8..92e631ad 100644 --- a/src/misc/extra/extra.h +++ b/src/misc/extra/extra.h @@ -89,6 +89,10 @@ (((((((unsigned)(a) + (unsigned)(b)) * DD_P1 + (unsigned)(c)) * DD_P2 + \ (unsigned)(d)) * DD_P3 + (unsigned)(e)) * DD_P1) % TSIZE) +#ifndef PRT +#define PRT(a,t) printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC)) +#endif + /*===========================================================================*/ /* Various Utilities */ /*===========================================================================*/ @@ -209,7 +213,13 @@ extern unsigned Extra_TruthCanonP( unsigned uTruth, int nVars ); extern unsigned Extra_TruthCanonNP( unsigned uTruth, int nVars ); extern unsigned Extra_TruthCanonNPN( unsigned uTruth, int nVars ); /* canonical forms of 4-variable functions */ -extern void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms ); +extern void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms, unsigned char ** puMap ); +extern void Extra_Truth4VarN( unsigned short ** puCanons, char *** puPhases, char ** ppCounters, int nPhasesMax ); +/* permutation mapping */ +extern void ** Extra_ArrayAlloc( int nCols, int nRows, int Size ); +extern unsigned short ** Extra_TruthPerm43(); +extern unsigned ** Extra_TruthPerm53(); +extern unsigned ** Extra_TruthPerm54(); /* for independence from CUDD */ extern unsigned int Cudd_PrimeCopy( unsigned int p ); diff --git a/src/misc/extra/extraUtilMisc.c b/src/misc/extra/extraUtilMisc.c index ccd871e4..2767498b 100644 --- a/src/misc/extra/extraUtilMisc.c +++ b/src/misc/extra/extraUtilMisc.c @@ -246,15 +246,10 @@ char ** Extra_Permutations( int n ) { char Array[50]; char ** pRes; - char * pBuffer; int nFact, i; - // allocate all memory at once - nFact = Extra_Factorial( n ); - pBuffer = ALLOC( char, nFact * sizeof(char *) + nFact * n * sizeof(char) ); - // split the chunk - pRes = (char **)pBuffer; - for ( i = 0; i < nFact; i++ ) - pRes[i] = pBuffer + nFact * sizeof(char *) + i * n * sizeof(char); + // allocate memory + nFact = Extra_Factorial( n ); + pRes = (char **)Extra_ArrayAlloc( nFact, n, sizeof(char) ); // fill in the permutations for ( i = 0; i < n; i++ ) Array[i] = i; @@ -290,7 +285,7 @@ void Extra_Permutations_rec( char ** pRes, int nFact, int n, char Array[] ) { char ** pNext; int nFactNext; - int iTemp, iCur, iLast, p; + int iTemp, iCur, iLast, k; if ( n == 1 ) { @@ -314,8 +309,8 @@ void Extra_Permutations_rec( char ** pRes, int nFact, int n, char Array[] ) pNext = pRes + (n - 1 - iCur) * nFactNext; // set the last entry - for ( p = 0; p < nFactNext; p++ ) - pNext[p][iLast] = Array[iLast]; + for ( k = 0; k < nFactNext; k++ ) + pNext[k][iLast] = Array[iLast]; // call recursively for this part Extra_Permutations_rec( pNext, nFactNext, n - 1, Array ); @@ -453,12 +448,12 @@ unsigned Extra_TruthPolarize( unsigned uTruth, int Polarity, int nVars ) unsigned Extra_TruthCanonN( unsigned uTruth, int nVars ) { unsigned uTruthMin, uPhase; - int nMints, p; + int nMints, i; nMints = (1 << nVars); uTruthMin = 0xFFFFFFFF; - for ( p = 0; p < nMints; p++ ) + for ( i = 0; i < nMints; i++ ) { - uPhase = Extra_TruthPolarize( uTruth, p, nVars ); + uPhase = Extra_TruthPolarize( uTruth, i, nVars ); if ( uTruthMin > uPhase ) uTruthMin = uPhase; } @@ -479,16 +474,16 @@ unsigned Extra_TruthCanonN( unsigned uTruth, int nVars ) unsigned Extra_TruthCanonNN( unsigned uTruth, int nVars ) { unsigned uTruthMin, uTruthC, uPhase; - int nMints, p; + int nMints, i; nMints = (1 << nVars); uTruthC = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) ); uTruthMin = 0xFFFFFFFF; - for ( p = 0; p < nMints; p++ ) + for ( i = 0; i < nMints; i++ ) { - uPhase = Extra_TruthPolarize( uTruth, p, nVars ); + uPhase = Extra_TruthPolarize( uTruth, i, nVars ); if ( uTruthMin > uPhase ) uTruthMin = uPhase; - uPhase = Extra_TruthPolarize( uTruthC, p, nVars ); + uPhase = Extra_TruthPolarize( uTruthC, i, nVars ); if ( uTruthMin > uPhase ) uTruthMin = uPhase; } @@ -555,7 +550,7 @@ unsigned Extra_TruthCanonNP( unsigned uTruth, int nVars ) static char ** pPerms = NULL; unsigned uTruthMin, uPhase, uPerm; - int nMints, k, p; + int nMints, k, i; if ( pPerms == NULL ) { @@ -573,9 +568,9 @@ unsigned Extra_TruthCanonNP( unsigned uTruth, int nVars ) nMints = (1 << nVars); uTruthMin = 0xFFFFFFFF; - for ( p = 0; p < nMints; p++ ) + for ( i = 0; i < nMints; i++ ) { - uPhase = Extra_TruthPolarize( uTruth, p, nVars ); + uPhase = Extra_TruthPolarize( uTruth, i, nVars ); for ( k = 0; k < nPerms; k++ ) { uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 ); @@ -603,7 +598,7 @@ unsigned Extra_TruthCanonNPN( unsigned uTruth, int nVars ) static char ** pPerms = NULL; unsigned uTruthMin, uTruthC, uPhase, uPerm; - int nMints, k, p; + int nMints, k, i; if ( pPerms == NULL ) { @@ -622,16 +617,16 @@ unsigned Extra_TruthCanonNPN( unsigned uTruth, int nVars ) nMints = (1 << nVars); uTruthC = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) ); uTruthMin = 0xFFFFFFFF; - for ( p = 0; p < nMints; p++ ) + for ( i = 0; i < nMints; i++ ) { - uPhase = Extra_TruthPolarize( uTruth, p, nVars ); + uPhase = Extra_TruthPolarize( uTruth, i, nVars ); for ( k = 0; k < nPerms; k++ ) { uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 ); if ( uTruthMin > uPerm ) uTruthMin = uPerm; } - uPhase = Extra_TruthPolarize( uTruthC, p, nVars ); + uPhase = Extra_TruthPolarize( uTruthC, i, nVars ); for ( k = 0; k < nPerms; k++ ) { uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 ); @@ -653,21 +648,24 @@ unsigned Extra_TruthCanonNPN( unsigned uTruth, int nVars ) SeeAlso [] ***********************************************************************/ -void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms ) +void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms, unsigned char ** puMap ) { unsigned short * uCanons; + unsigned char * uMap; unsigned uTruth, uPhase, uPerm; char ** pPerms4, * uPhases, * uPerms; int nFuncs, nClasses; - int p, k; + int i, k; nFuncs = (1 << 16); uCanons = ALLOC( unsigned short, nFuncs ); uPhases = ALLOC( char, nFuncs ); uPerms = ALLOC( char, nFuncs ); + uMap = ALLOC( unsigned char, nFuncs ); memset( uCanons, 0, sizeof(unsigned short) * nFuncs ); memset( uPhases, 0, sizeof(char) * nFuncs ); memset( uPerms, 0, sizeof(char) * nFuncs ); + memset( uMap, 0, sizeof(unsigned char) * nFuncs ); pPerms4 = Extra_Permutations( 4 ); nClasses = 1; @@ -676,41 +674,45 @@ void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** p { // skip already assigned if ( uCanons[uTruth] ) + { + assert( uTruth > uCanons[uTruth] ); + uMap[uTruth] = uMap[uCanons[uTruth]]; continue; - nClasses++; - for ( p = 0; p < 16; p++ ) + } + uMap[uTruth] = nClasses++; + for ( i = 0; i < 16; i++ ) { - uPhase = Extra_TruthPolarize( uTruth, p, 4 ); + uPhase = Extra_TruthPolarize( uTruth, i, 4 ); for ( k = 0; k < 24; k++ ) { uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 ); if ( uCanons[uPerm] == 0 ) { uCanons[uPerm] = uTruth; - uPhases[uPerm] = p; + uPhases[uPerm] = i; uPerms[uPerm] = k; uPerm = ~uPerm & 0xFFFF; uCanons[uPerm] = uTruth; - uPhases[uPerm] = p | 16; + uPhases[uPerm] = i | 16; uPerms[uPerm] = k; } else assert( uCanons[uPerm] == uTruth ); } - uPhase = Extra_TruthPolarize( ~uTruth & 0xFFFF, p, 4 ); + uPhase = Extra_TruthPolarize( ~uTruth & 0xFFFF, i, 4 ); for ( k = 0; k < 24; k++ ) { uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 ); if ( uCanons[uPerm] == 0 ) { uCanons[uPerm] = uTruth; - uPhases[uPerm] = p; + uPhases[uPerm] = i; uPerms[uPerm] = k; uPerm = ~uPerm & 0xFFFF; uCanons[uPerm] = uTruth; - uPhases[uPerm] = p | 16; + uPhases[uPerm] = i | 16; uPerms[uPerm] = k; } else @@ -733,6 +735,352 @@ void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** p *puPerms = uPerms; else free( uPerms ); + if ( puMap ) + *puMap = uMap; + else + free( uMap ); +} + +/**Function************************************************************* + + Synopsis [Computes NPN canonical forms for 4-variable functions.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Extra_Truth4VarN( unsigned short ** puCanons, char *** puPhases, char ** ppCounters, int nPhasesMax ) +{ + unsigned short * uCanons; + unsigned uTruth, uPhase; + char ** uPhases, * pCounters; + int nFuncs, nClasses, i; + + nFuncs = (1 << 16); + uCanons = ALLOC( unsigned short, nFuncs ); + memset( uCanons, 0, sizeof(unsigned short) * nFuncs ); + pCounters = ALLOC( char, nFuncs ); + memset( pCounters, 0, sizeof(char) * nFuncs ); + uPhases = (char **)Extra_ArrayAlloc( nFuncs, nPhasesMax, sizeof(char) ); + nClasses = 0; + for ( uTruth = 0; uTruth < (unsigned)nFuncs; uTruth++ ) + { + // skip already assigned + if ( uCanons[uTruth] ) + { + assert( uTruth > uCanons[uTruth] ); + continue; + } + nClasses++; + for ( i = 0; i < 16; i++ ) + { + uPhase = Extra_TruthPolarize( uTruth, i, 4 ); + if ( uCanons[uPhase] == 0 ) + { + uCanons[uPhase] = uTruth; + uPhases[uPhase][0] = i; + pCounters[uPhase] = 1; + } + else + { + assert( uCanons[uPhase] == uTruth ); + if ( pCounters[uPhase] < nPhasesMax ) + uPhases[uPhase][ pCounters[uPhase]++ ] = i; + } + } + } + if ( puCanons ) + *puCanons = uCanons; + else + free( uCanons ); + if ( puPhases ) + *puPhases = uPhases; + else + free( uPhases ); + if ( ppCounters ) + *ppCounters = pCounters; + else + free( pCounters ); +} + +/**Function************************************************************* + + Synopsis [Allocated one-memory-chunk array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void ** Extra_ArrayAlloc( int nCols, int nRows, int Size ) +{ + char ** pRes; + char * pBuffer; + int i; + assert( nCols > 0 && nRows > 0 && Size > 0 ); + pBuffer = ALLOC( char, nCols * (sizeof(void *) + nRows * Size) ); + pRes = (char **)pBuffer; + pRes[0] = pBuffer + nCols * sizeof(void *); + for ( i = 1; i < nCols; i++ ) + pRes[i] = pRes[0] + i * nRows * Size; + return pRes; +} + +/**Function************************************************************* + + Synopsis [Computes a phase of the 3-var function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned short Extra_TruthPerm4One( unsigned uTruth, int Phase ) +{ + // cases + static unsigned short Cases[16] = { + 0, // 0000 - skip + 0, // 0001 - skip + 0xCCCC, // 0010 - single var + 0, // 0011 - skip + 0xF0F0, // 0100 - single var + 1, // 0101 + 1, // 0110 + 0, // 0111 - skip + 0xFF00, // 1000 - single var + 1, // 1001 + 1, // 1010 + 1, // 1011 + 1, // 1100 + 1, // 1101 + 1, // 1110 + 0 // 1111 - skip + }; + // permutations + static int Perms[16][4] = { + { 0, 0, 0, 0 }, // 0000 - skip + { 0, 0, 0, 0 }, // 0001 - skip + { 0, 0, 0, 0 }, // 0010 - single var + { 0, 0, 0, 0 }, // 0011 - skip + { 0, 0, 0, 0 }, // 0100 - single var + { 0, 2, 1, 3 }, // 0101 + { 2, 0, 1, 3 }, // 0110 + { 0, 0, 0, 0 }, // 0111 - skip + { 0, 0, 0, 0 }, // 1000 - single var + { 0, 2, 3, 1 }, // 1001 + { 2, 0, 3, 1 }, // 1010 + { 0, 1, 3, 2 }, // 1011 + { 2, 3, 0, 1 }, // 1100 + { 0, 3, 1, 2 }, // 1101 + { 3, 0, 1, 2 }, // 1110 + { 0, 0, 0, 0 } // 1111 - skip + }; + int i, k, iRes; + unsigned uTruthRes; + assert( Phase >= 0 && Phase < 16 ); + if ( Cases[Phase] == 0 ) + return uTruth; + if ( Cases[Phase] > 1 ) + return Cases[Phase]; + uTruthRes = 0; + for ( i = 0; i < 16; i++ ) + if ( uTruth & (1 << i) ) + { + for ( iRes = 0, k = 0; k < 4; k++ ) + if ( i & (1 << Perms[Phase][k]) ) + iRes |= (1 << k); + uTruthRes |= (1 << iRes); + } + return uTruthRes; +} + +/**Function************************************************************* + + Synopsis [Computes a phase of the 3-var function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Extra_TruthPerm5One( unsigned uTruth, int Phase ) +{ + // cases + static unsigned Cases[32] = { + 0, // 00000 - skip + 0, // 00001 - skip + 0xCCCCCCCC, // 00010 - single var + 0, // 00011 - skip + 0xF0F0F0F0, // 00100 - single var + 1, // 00101 + 1, // 00110 + 0, // 00111 - skip + 0xFF00FF00, // 01000 - single var + 1, // 01001 + 1, // 01010 + 1, // 01011 + 1, // 01100 + 1, // 01101 + 1, // 01110 + 0, // 01111 - skip + 0xFFFF0000, // 10000 - skip + 1, // 10001 + 1, // 10010 + 1, // 10011 + 1, // 10100 + 1, // 10101 + 1, // 10110 + 1, // 10111 - four var + 1, // 11000 + 1, // 11001 + 1, // 11010 + 1, // 11011 - four var + 1, // 11100 + 1, // 11101 - four var + 1, // 11110 - four var + 0 // 11111 - skip + }; + // permutations + static int Perms[32][5] = { + { 0, 0, 0, 0, 0 }, // 00000 - skip + { 0, 0, 0, 0, 0 }, // 00001 - skip + { 0, 0, 0, 0, 0 }, // 00010 - single var + { 0, 0, 0, 0, 0 }, // 00011 - skip + { 0, 0, 0, 0, 0 }, // 00100 - single var + { 0, 2, 1, 3, 4 }, // 00101 + { 2, 0, 1, 3, 4 }, // 00110 + { 0, 0, 0, 0, 0 }, // 00111 - skip + { 0, 0, 0, 0, 0 }, // 01000 - single var + { 0, 2, 3, 1, 4 }, // 01001 + { 2, 0, 3, 1, 4 }, // 01010 + { 0, 1, 3, 2, 4 }, // 01011 + { 2, 3, 0, 1, 4 }, // 01100 + { 0, 3, 1, 2, 4 }, // 01101 + { 3, 0, 1, 2, 4 }, // 01110 + { 0, 0, 0, 0, 0 }, // 01111 - skip + { 0, 0, 0, 0, 0 }, // 10000 - single var + { 0, 4, 2, 3, 1 }, // 10001 + { 4, 0, 2, 3, 1 }, // 10010 + { 0, 1, 3, 4, 2 }, // 10011 + { 2, 3, 0, 4, 1 }, // 10100 + { 0, 3, 1, 4, 2 }, // 10101 + { 3, 0, 1, 4, 2 }, // 10110 + { 0, 1, 2, 4, 3 }, // 10111 - four var + { 2, 3, 4, 0, 1 }, // 11000 + { 0, 3, 4, 1, 2 }, // 11001 + { 3, 0, 4, 1, 2 }, // 11010 + { 0, 1, 4, 2, 3 }, // 11011 - four var + { 3, 4, 0, 1, 2 }, // 11100 + { 0, 4, 1, 2, 3 }, // 11101 - four var + { 4, 0, 1, 2, 3 }, // 11110 - four var + { 0, 0, 0, 0, 0 } // 11111 - skip + }; + int i, k, iRes; + unsigned uTruthRes; + assert( Phase >= 0 && Phase < 32 ); + if ( Cases[Phase] == 0 ) + return uTruth; + if ( Cases[Phase] > 1 ) + return Cases[Phase]; + uTruthRes = 0; + for ( i = 0; i < 32; i++ ) + if ( uTruth & (1 << i) ) + { + for ( iRes = 0, k = 0; k < 5; k++ ) + if ( i & (1 << Perms[Phase][k]) ) + iRes |= (1 << k); + uTruthRes |= (1 << iRes); + } + return uTruthRes; +} + +/**Function************************************************************* + + Synopsis [Allocated lookup table for truth table permutation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned short ** Extra_TruthPerm43() +{ + unsigned short ** pTable; + unsigned uTruth; + int i, k; + pTable = (unsigned short **)Extra_ArrayAlloc( 256, 16, 2 ); + for ( i = 0; i < 256; i++ ) + { + uTruth = (i << 8) | i; + for ( k = 0; k < 16; k++ ) + pTable[i][k] = Extra_TruthPerm4One( uTruth, k ); + } + return pTable; +} + +/**Function************************************************************* + + Synopsis [Allocated lookup table for truth table permutation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned ** Extra_TruthPerm53() +{ + unsigned ** pTable; + unsigned uTruth; + int i, k; + pTable = (unsigned **)Extra_ArrayAlloc( 256, 32, 4 ); + for ( i = 0; i < 256; i++ ) + { + uTruth = (i << 24) | (i << 16) | (i << 8) | i; + for ( k = 0; k < 32; k++ ) + pTable[i][k] = Extra_TruthPerm5One( uTruth, k ); + } + return pTable; +} + +/**Function************************************************************* + + Synopsis [Allocated lookup table for truth table permutation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned ** Extra_TruthPerm54() +{ + unsigned ** pTable; + unsigned uTruth; + int i; + pTable = (unsigned **)Extra_ArrayAlloc( 256*256, 4, 4 ); + for ( i = 0; i < 256*256; i++ ) + { + uTruth = (i << 16) | i; + pTable[i][0] = Extra_TruthPerm5One( uTruth, 31-8 ); + pTable[i][1] = Extra_TruthPerm5One( uTruth, 31-4 ); + pTable[i][2] = Extra_TruthPerm5One( uTruth, 31-2 ); + pTable[i][3] = Extra_TruthPerm5One( uTruth, 31-1 ); + } + return pTable; } /**Function************************************************************* diff --git a/src/opt/rwr/rwr.h b/src/opt/rwr/rwr.h index 96810c25..5d190745 100644 --- a/src/opt/rwr/rwr.h +++ b/src/opt/rwr/rwr.h @@ -44,17 +44,19 @@ typedef struct Rwr_Cut_t_ Rwr_Cut_t; struct Rwr_Man_t_ { // internal lookups - int nFuncs; // the number of four var functions + int nFuncs; // number of four var functions unsigned short * puCanons; // canonical forms char * pPhases; // canonical phases char * pPerms; // canonical permutations unsigned char * pMap; // mapping of functions into class numbers - char * pPractical; // practical classes - unsigned short puPerms[256][16]; // permutations for three var functions + char * pPractical; // practical NPN classes + unsigned short ** puPerms43; // four-var permutations for three var functions // node space Vec_Ptr_t * vForest; // all the nodes Rwr_Node_t ** pTable; // the hash table of nodes by their canonical form + Vec_Vec_t * vClasses; // the nodes of the equivalence classes Extra_MmFixed_t * pMmNode; // memory for nodes and cuts + // statistical variables int nTravIds; // the counter of traversal IDs int nConsidered; // the number of nodes considered int nAdded; // the number of nodes added to lists @@ -64,10 +66,8 @@ struct Rwr_Man_t_ Vec_Int_t * vReqTimes; // the required times for each node (used for delay-driven evalution) // the result of resynthesis Vec_Int_t * vForm; // the decomposition tree (temporary) + Vec_Int_t * vLevNums; // the array of levels (temporary) Vec_Ptr_t * vFanins; // the fanins array (temporary) - Vec_Ptr_t * vTfo; // the TFO node array (temporary) - Vec_Ptr_t * vTfoFor; // the TFO node array (temporary) - Vec_Vec_t * vLevels; // the levelized structure (temporary) int nGainMax; // runtime statistics int time1; @@ -82,8 +82,7 @@ struct Rwr_Node_t_ // 24 bytes int TravId; // traversal ID unsigned uTruth : 16; // truth table unsigned Volume : 8; // volume - unsigned Level : 5; // level - unsigned fMark : 1; // mark + unsigned Level : 6; // level unsigned fUsed : 1; // mark unsigned fExor : 1; // mark Rwr_Node_t * p0; // first child @@ -122,22 +121,29 @@ extern void Rwr_NtkStartCuts( Rwr_Man_t * p, Abc_Ntk_t * pNtk ); extern void Rwr_NodeComputeCuts( Rwr_Man_t * p, Abc_Obj_t * pNode ); /*=== rwrEva.c ========================================================*/ extern int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode ); +extern void Rwr_ManPreprocess( Rwr_Man_t * p ); /*=== rwrLib.c ========================================================*/ extern void Rwr_ManPrecompute( Rwr_Man_t * p ); -extern void Rwr_ManWriteToFile( Rwr_Man_t * p, char * pFileName ); -extern void Rwr_ManLoadFromFile( Rwr_Man_t * p, char * pFileName ); -extern void Rwr_ManPrintFirst( Rwr_Man_t * p ); -extern void Rwr_ManPrintNext( Rwr_Man_t * p ); -extern Rwr_Node_t * Rwr_ManAddVar( Rwr_Man_t * p, unsigned uTruth, char * pFileName ); +extern Rwr_Node_t * Rwr_ManAddVar( Rwr_Man_t * p, unsigned uTruth, int fPrecompute ); +extern Rwr_Node_t * Rwr_ManAddNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, int fExor, int Level, int Volume ); +extern int Rwr_ManNodeVolume( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1 ); +extern void Rwr_ManIncTravId( Rwr_Man_t * p ); /*=== rwrMan.c ========================================================*/ -extern Rwr_Man_t * Rwr_ManStart( char * pFileName ); +extern Rwr_Man_t * Rwr_ManStart( bool fPrecompute ); extern void Rwr_ManStop( Rwr_Man_t * p ); extern void Rwr_ManPrepareNetwork( Rwr_Man_t * p, Abc_Ntk_t * pNtk ); extern Vec_Ptr_t * Rwr_ManReadFanins( Rwr_Man_t * p ); extern Vec_Int_t * Rwr_ManReadDecs( Rwr_Man_t * p ); -extern unsigned short Rwr_FunctionPhase( unsigned uTruth, unsigned uPhase ); +/*=== rwrPrint.c ========================================================*/ +extern void Rwr_ManPrint( Rwr_Man_t * p ); /*=== rwrUtil.c ========================================================*/ +extern void Rwr_ManWriteToArray( Rwr_Man_t * p ); +extern void Rwr_ManLoadFromArray( Rwr_Man_t * p ); +extern void Rwr_ManWriteToFile( Rwr_Man_t * p, char * pFileName ); +extern void Rwr_ManLoadFromFile( Rwr_Man_t * p, char * pFileName ); extern Vec_Int_t * Rwt_NtkFanoutCounters( Abc_Ntk_t * pNtk ); +extern void Rwr_ListAddToTail( Rwr_Node_t ** ppList, Rwr_Node_t * pNode ); +extern char * Rwr_ManGetPractical( Rwr_Man_t * p ); //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/rwr/rwrCut.c b/src/opt/rwr/rwrCut.c index c8560114..209d6ee6 100644 --- a/src/opt/rwr/rwrCut.c +++ b/src/opt/rwr/rwrCut.c @@ -174,7 +174,7 @@ Rwr_Cut_t * Rwr_CutsMerge( Rwr_Man_t * p, Rwr_Cut_t * pCut0, Rwr_Cut_t * pCut1, } assert( uPhase < 16 ); assert( pCut0->uTruth < 256 ); - uTruth0 = p->puPerms[pCut0->uTruth][uPhase]; + uTruth0 = p->puPerms43[pCut0->uTruth][uPhase]; } // find the mapping from the old nodes to the new @@ -192,7 +192,7 @@ Rwr_Cut_t * Rwr_CutsMerge( Rwr_Man_t * p, Rwr_Cut_t * pCut0, Rwr_Cut_t * pCut1, } assert( uPhase < 16 ); assert( pCut1->uTruth < 256 ); - uTruth1 = p->puPerms[pCut1->uTruth][uPhase]; + uTruth1 = p->puPerms43[pCut1->uTruth][uPhase]; } // create the cut diff --git a/src/opt/rwr/rwrEva.c b/src/opt/rwr/rwrEva.c index 50e773f8..ddc9d742 100644 --- a/src/opt/rwr/rwrEva.c +++ b/src/opt/rwr/rwrEva.c @@ -19,13 +19,13 @@ ***********************************************************************/ #include "rwr.h" +#include "ft.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut ); -static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut, Vec_Int_t * vForm ); +static Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -51,43 +51,34 @@ static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut ***********************************************************************/ int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode ) { - Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector; - Rwr_Cut_t * pCut, * pCutBest; - int BestGain = -1; - int i, Required = Vec_IntEntry( p->vReqTimes, pNode->Id ); - - // compute the cuts of the node + Vec_Int_t * vForm; + Rwr_Cut_t * pCut; + int Required, nNodesSaved; + int i, BestGain = -1; + // compute the cuts for this node Rwr_NodeComputeCuts( p, pNode ); - + // get the required times + Required = Vec_IntEntry( p->vReqTimes, pNode->Id ); + // label MFFC with current ID + nNodesSaved = Abc_NodeMffcLabel( pNode ); // go through the cuts for ( pCut = (Rwr_Cut_t *)pNode->pCopy, pCut = pCut->pNext; pCut; pCut = pCut->pNext ) { - // collect the TFO - vFanins->nSize = pCut->nLeaves; - vFanins->pArray = pCut->ppLeaves; - Abc_NodeCollectTfoCands( pNode->pNtk, pNode, vFanins, Required, p->vLevels, p->vTfo ); // evaluate the cut - Rwr_CutEvaluate( p, pNode, pCut ); - // check if the cut is the best - if ( pCut->fTime && pCut->fGain ) + vForm = Rwr_CutEvaluate( p, pNode, pCut, nNodesSaved, Required ); + // check if the cut is better than the currently best one + if ( vForm != NULL && BestGain < (int)pCut->Volume ) { - pCutBest = pCut; - BestGain = pCut->Volume; + assert( pCut->Volume >= 0 ); + BestGain = pCut->Volume; + // save this form + p->vForm = vForm; + // collect fanins + Vec_PtrClear( p->vFanins ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + Vec_PtrPush( p->vFanins, pCut->ppLeaves[i] ); } } - if ( BestGain == -1 ) - return -1; - // we found a good cut - - // prepare the fanins - Vec_PtrClear( p->vFanins ); - for ( i = 0; i < (int)pCutBest->nLeaves; i++ ) - Vec_PtrPush( p->vFanins, pCutBest->ppLeaves[i] ); - // collect the TFO again - Abc_NodeCollectTfoCands( pNode->pNtk, pNode, p->vFanins, Required, p->vLevels, p->vTfo ); - // perform the decomposition - Rwr_CutDecompose( p, pNode, pCutBest, p->vForm ); - // the best fanins are in p->vFanins, the result of decomposition is in p->vForm return BestGain; } @@ -102,46 +93,113 @@ int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode ) SeeAlso [] ***********************************************************************/ -void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut ) +Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax ) { - Abc_Obj_t * pNode, * pFanin0, * pFanin1; - Rwr_Node_t * pNodeFor; - int i; - // mark forest PIs corresponding to cut leaves - Vec_PtrClear( p->vTfoFor ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) + Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector; + Vec_Ptr_t * vSubgraphs; + Vec_Int_t * vFormBest; + Rwr_Node_t * pNode; + int GainCur, GainBest = -1, i; + // find the matching class of subgraphs + vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[pCut->uTruth] ); + // determine the best subgraph + Vec_PtrForEachEntry( vSubgraphs, pNode, i ) { - pNodeFor = p->vForest->pArray[i]; - Vec_PtrPush( p->vTfoFor, pNodeFor ); - pCut->ppLeaves[i]->pData = pNodeFor; - pNodeFor->fMark = 1; + // create the fanin array + vFanins->nSize = pCut->nLeaves; + vFanins->pArray = pCut->ppLeaves; + // detect how many unlabeled nodes will be reused + GainCur = Abc_NodeStrashDecCount( pRoot->pNtk->pManFunc, vFanins, (Vec_Int_t *)pNode->pNext, + p->vLevNums, NodeMax, LevelMax ); + if ( GainBest < GainCur ) + { + GainBest = GainCur; + vFormBest = (Vec_Int_t *)pNode->pNext; + } } - // detect forest nodes corresponding to TFO - Vec_PtrForEachEntry( p->vTfo, pNode, i ) - { - pFanin0 = Abc_ObjFanin0(pNode); - if ( pFanin0->pData == NULL ) - continue; - pFanin1 = Abc_ObjFanin1(pNode); - if ( pFanin1->pData == NULL ) - continue; + if ( GainBest == -1 ) + return NULL; + pCut->Volume = GainBest; + return vFormBest; +} - } - // find the best implementation of the root +/**Function************************************************************* + + Synopsis [Adds one node.] - // assign costs + Description [] + + SideEffects [] + + SeeAlso [] - // clean the nodes - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - pCut->ppLeaves[i]->pData = NULL; - Vec_PtrForEachEntry( p->vTfo, pNode, i ) - pNode->pData = NULL; +***********************************************************************/ +int Rwr_TravCollect_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, Vec_Int_t * vForm ) +{ + Ft_Node_t Node, NodeA, NodeB; + int Node0, Node1; + // elementary variable + if ( pNode->fUsed ) + return ((pNode->Id - 1) << 1); + // previously visited node + if ( pNode->TravId == p->nTravIds ) + return pNode->Volume; + pNode->TravId = p->nTravIds; + // solve for children + Node0 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p0), vForm ); + Node1 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p1), vForm ); + // create the decomposition node(s) + if ( pNode->fExor ) + { + assert( !Rwr_IsComplement(pNode->p0) ); + assert( !Rwr_IsComplement(pNode->p1) ); + NodeA.fIntern = 1; + NodeA.fConst = 0; + NodeA.fCompl = 0; + NodeA.fCompl0 = !(Node0 & 1); + NodeA.fCompl1 = (Node1 & 1); + NodeA.iFanin0 = (Node0 >> 1); + NodeA.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(NodeA) ); + + NodeB.fIntern = 1; + NodeB.fConst = 0; + NodeB.fCompl = 0; + NodeB.fCompl0 = (Node0 & 1); + NodeB.fCompl1 = !(Node1 & 1); + NodeB.iFanin0 = (Node0 >> 1); + NodeB.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(NodeB) ); + + Node.fIntern = 1; + Node.fConst = 0; + Node.fCompl = 0; + Node.fCompl0 = 1; + Node.fCompl1 = 1; + Node.iFanin0 = vForm->nSize - 2; + Node.iFanin1 = vForm->nSize - 1; + Vec_IntPush( vForm, Ft_Node2Int(Node) ); + } + else + { + Node.fIntern = 1; + Node.fConst = 0; + Node.fCompl = 0; + Node.fCompl0 = Rwr_IsComplement(pNode->p0) ^ (Node0 & 1); + Node.fCompl1 = Rwr_IsComplement(pNode->p1) ^ (Node1 & 1); + Node.iFanin0 = (Node0 >> 1); + Node.iFanin1 = (Node1 >> 1); + Vec_IntPush( vForm, Ft_Node2Int(Node) ); + } + // save the number of this node + pNode->Volume = ((vForm->nSize - 1) << 1) | pNode->fExor; + return pNode->Volume; } /**Function************************************************************* - Synopsis [Decomposes the cut.] + Synopsis [Preprocesses subgraphs rooted at this node.] Description [] @@ -150,11 +208,45 @@ void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, Vec_Int_t * vForm ) +void Rwr_NodePreprocess( Rwr_Man_t * p, Rwr_Node_t * pNode ) { - + Vec_Int_t * vForm; + int i, Root; + vForm = Vec_IntAlloc( 10 ); + for ( i = 0; i < 5; i++ ) + Vec_IntPush( vForm, 0 ); + // collect the nodes + Rwr_ManIncTravId( p ); + Root = Rwr_TravCollect_rec( p, pNode, vForm ); + if ( Root & 1 ) + Ft_FactorComplement( vForm ); + pNode->pNext = (Rwr_Node_t *)vForm; } +/**Function************************************************************* + + Synopsis [Preprocesses computed library of subgraphs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManPreprocess( Rwr_Man_t * p ) +{ + Rwr_Node_t * pNode; + int i, k; + // put the nodes into the structure + p->vClasses = Vec_VecAlloc( 222 ); + for ( i = 0; i < p->nFuncs; i++ ) + for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) + Vec_VecPush( p->vClasses, p->pMap[pNode->uTruth], pNode ); + // compute decomposition forms for each node + Vec_VecForEachEntry( p->vClasses, pNode, i, k ) + Rwr_NodePreprocess( p, pNode ); +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/rwr/rwrExp.c b/src/opt/rwr/rwrExp.c index a5c355a9..e93a2611 100644 --- a/src/opt/rwr/rwrExp.c +++ b/src/opt/rwr/rwrExp.c @@ -69,7 +69,7 @@ void Rwt_Man4ExploreStart() // canonical forms p->nFuncs = (1<<16); // canonical forms, phases, perms - Extra_Truth4VarNPN( &p->puCanons, NULL, NULL ); + Extra_Truth4VarNPN( &p->puCanons, NULL, NULL, NULL ); // counters p->pnCounts = ALLOC( int, p->nFuncs ); memset( p->pnCounts, 0, sizeof(int) * p->nFuncs ); diff --git a/src/opt/rwr/rwrLib.c b/src/opt/rwr/rwrLib.c index a283e38f..fbcb8916 100644 --- a/src/opt/rwr/rwrLib.c +++ b/src/opt/rwr/rwrLib.c @@ -25,14 +25,7 @@ //////////////////////////////////////////////////////////////////////// static Rwr_Node_t * Rwr_ManTryNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, int fExor, int Level, int Volume ); -static Rwr_Node_t * Rwr_ManAddNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, int fExor, int Level, int Volume ); -static int Rwr_ManNodeVolume( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1 ); - -static void Rwr_ManIncTravId_int( Rwr_Man_t * p ); -static inline void Rwr_ManIncTravId( Rwr_Man_t * p ) { if ( p->nTravIds++ == 0x8FFFFFFF ) Rwr_ManIncTravId_int( p ); } - static void Rwr_MarkUsed_rec( Rwr_Man_t * p, Rwr_Node_t * pNode ); -static void Rwr_ListAddToTail( Rwr_Node_t ** ppList, Rwr_Node_t * pNode ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// @@ -119,8 +112,7 @@ save : if ( p0->fUsed ) { p->vForest->pArray[k] = p0; - p0->Id = k; - k++; + p0->Id = k++; } p->vForest->nSize = k; printf( "Total canonical = %4d. Total used = %5d.\n", nNodes, p->vForest->nSize ); @@ -128,202 +120,6 @@ save : /**Function************************************************************* - Synopsis [Writes to file.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ManWriteToFile( Rwr_Man_t * p, char * pFileName ) -{ - FILE * pFile; - Rwr_Node_t * pNode; - unsigned * pBuffer; - int i, nEntries, clk = clock(); - // prepare the buffer - nEntries = p->vForest->nSize - 5; - pBuffer = ALLOC( unsigned, nEntries * 2 ); - for ( i = 0; i < nEntries; i++ ) - { - pNode = p->vForest->pArray[i+5]; - pBuffer[2*i + 0] = (Rwr_Regular(pNode->p0)->Id << 1) | Rwr_IsComplement(pNode->p0); - pBuffer[2*i + 1] = (Rwr_Regular(pNode->p1)->Id << 1) | Rwr_IsComplement(pNode->p1); - // save EXOR flag - pBuffer[2*i + 0] = (pBuffer[2*i + 0] << 1) | pNode->fExor; - - } - pFile = fopen( pFileName, "wb" ); - fwrite( &nEntries, sizeof(int), 1, pFile ); - fwrite( pBuffer, sizeof(unsigned), nEntries * 2, pFile ); - free( pBuffer ); - fclose( pFile ); - printf( "The number of nodes saved = %d. ", nEntries ); PRT( "Saving", clock() - clk ); -} - -/**Function************************************************************* - - Synopsis [Loads data from file.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ManLoadFromFile( Rwr_Man_t * p, char * pFileName ) -{ - FILE * pFile; - Rwr_Node_t * p0, * p1; - unsigned * pBuffer; - int Level, Volume, nEntries, fExor; - int i, clk = clock(); - - // load the data - pFile = fopen( pFileName, "rb" ); - if ( pFile == NULL ) - { - printf( "Rwr_ManLoadFromFile: Cannot open file \"%s\".\n", pFileName ); - return; - } - fread( &nEntries, sizeof(int), 1, pFile ); - pBuffer = ALLOC( unsigned, nEntries * 2 ); - fread( pBuffer, sizeof(unsigned), nEntries * 2, pFile ); - fclose( pFile ); - // reconstruct the forest - for ( i = 0; i < nEntries; i++ ) - { - // get EXOR flag - fExor = (pBuffer[2*i + 0] & 1); - pBuffer[2*i + 0] = (pBuffer[2*i + 0] >> 1); - // get the nodes - p0 = p->vForest->pArray[pBuffer[2*i + 0] >> 1]; - p1 = p->vForest->pArray[pBuffer[2*i + 1] >> 1]; - // compute the level and volume of the new nodes - Level = 1 + ABC_MAX( p0->Level, p1->Level ); - Volume = 1 + Rwr_ManNodeVolume( p, p0, p1 ); - // set the complemented attributes - p0 = Rwr_NotCond( p0, (pBuffer[2*i + 0] & 1) ); - p1 = Rwr_NotCond( p1, (pBuffer[2*i + 1] & 1) ); - // add the node -// Rwr_ManTryNode( p, p0, p1, Level, Volume ); - Rwr_ManAddNode( p, p0, p1, fExor, Level, Volume + fExor ); - } - free( pBuffer ); - printf( "The number of classes = %d. Canonical nodes = %d.\n", p->nClasses, p->nAdded ); - printf( "The number of nodes loaded = %d. ", nEntries ); PRT( "Loading", clock() - clk ); -} - -/**Function************************************************************* - - Synopsis [Adds one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ManIncTravId_int( Rwr_Man_t * p ) -{ - Rwr_Node_t * pNode; - int i; - Vec_PtrForEachEntry( p->vForest, pNode, i ) - pNode->TravId = 0; - p->nTravIds = 1; -} - -/**Function************************************************************* - - Synopsis [Adds one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_MarkUsed_rec( Rwr_Man_t * p, Rwr_Node_t * pNode ) -{ - if ( pNode->fUsed || pNode->TravId == p->nTravIds ) - return; - pNode->TravId = p->nTravIds; - pNode->fUsed = 1; - Rwr_MarkUsed_rec( p, Rwr_Regular(pNode->p0) ); - Rwr_MarkUsed_rec( p, Rwr_Regular(pNode->p1) ); -} - -/**Function************************************************************* - - Synopsis [Adds one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_Trav_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, int * pVolume ) -{ - if ( pNode->fMark || pNode->TravId == p->nTravIds ) - return; - pNode->TravId = p->nTravIds; - (*pVolume)++; - if ( pNode->fExor ) - (*pVolume)++; - Rwr_Trav_rec( p, Rwr_Regular(pNode->p0), pVolume ); - Rwr_Trav_rec( p, Rwr_Regular(pNode->p1), pVolume ); -} - -/**Function************************************************************* - - Synopsis [Adds one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_Trav2_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, int * pVolume ) -{ - if ( pNode->fMark || pNode->TravId == p->nTravIds ) - return; - pNode->TravId = p->nTravIds; - (*pVolume)++; - Rwr_Trav2_rec( p, Rwr_Regular(pNode->p0), pVolume ); - Rwr_Trav2_rec( p, Rwr_Regular(pNode->p1), pVolume ); -} - -/**Function************************************************************* - - Synopsis [Adds one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Rwr_ManNodeVolume( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1 ) -{ - int Volume = 0; - Rwr_ManIncTravId( p ); - Rwr_Trav_rec( p, p0, &Volume ); - Rwr_Trav_rec( p, p1, &Volume ); - return Volume; -} - -/**Function************************************************************* - Synopsis [Adds one node.] Description [] @@ -361,6 +157,7 @@ Rwr_Node_t * Rwr_ManTryNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in // if ( pOld->Level < (unsigned)Level && pOld->Volume == (unsigned)Volume ) // return NULL; } +/* // enumerate through the nodes with the opposite polarity for ( pOld = p->pTable[~uTruth & 0xFFFF]; pOld; pOld = pOld->pNext ) { @@ -371,6 +168,7 @@ Rwr_Node_t * Rwr_ManTryNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in // if ( pOld->Level < (unsigned)Level && pOld->Volume == (unsigned)Volume ) // return NULL; } +*/ // count the classes if ( p->pTable[uTruth] == NULL && p->puCanons[uTruth] == uTruth ) p->nClasses++; @@ -381,7 +179,6 @@ Rwr_Node_t * Rwr_ManTryNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in pNew->uTruth = uTruth; pNew->Level = Level; pNew->Volume = Volume; - pNew->fMark = 0; pNew->fUsed = 0; pNew->fExor = fExor; pNew->p0 = p0; @@ -421,7 +218,6 @@ Rwr_Node_t * Rwr_ManAddNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in pNew->uTruth = uTruth; pNew->Level = Level; pNew->Volume = Volume; - pNew->fMark = 0; pNew->fUsed = 0; pNew->fExor = fExor; pNew->p0 = p0; @@ -434,9 +230,9 @@ Rwr_Node_t * Rwr_ManAddNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in // add to the list p->nAdded++; - if ( p->pTable[p->pMap[uTruth]] == NULL ) + if ( p->pTable[uTruth] == NULL ) p->nClasses++; - Rwr_ListAddToTail( p->pTable + p->pMap[uTruth], pNew ); + Rwr_ListAddToTail( p->pTable + uTruth, pNew ); return pNew; } @@ -451,7 +247,7 @@ Rwr_Node_t * Rwr_ManAddNode( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1, in SeeAlso [] ***********************************************************************/ -Rwr_Node_t * Rwr_ManAddVar( Rwr_Man_t * p, unsigned uTruth, char * pFileName ) +Rwr_Node_t * Rwr_ManAddVar( Rwr_Man_t * p, unsigned uTruth, int fPrecompute ) { Rwr_Node_t * pNew; pNew = (Rwr_Node_t *)Extra_MmFixedEntryFetch( p->pMmNode ); @@ -460,45 +256,22 @@ Rwr_Node_t * Rwr_ManAddVar( Rwr_Man_t * p, unsigned uTruth, char * pFileName ) pNew->uTruth = uTruth; pNew->Level = 0; pNew->Volume = 0; - pNew->fMark = 1; pNew->fUsed = 1; pNew->fExor = 0; pNew->p0 = NULL; pNew->p1 = NULL; pNew->pNext = NULL; Vec_PtrPush( p->vForest, pNew ); - if ( pFileName == NULL ) + if ( fPrecompute ) Rwr_ListAddToTail( p->pTable + uTruth, pNew ); -// else -// Rwr_ListAddToTail( p->pTable + p->pMap[uTruth], pNew ); return pNew; } -/**Function************************************************************* - - Synopsis [Adds the node to the end of the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Rwr_ListAddToTail( Rwr_Node_t ** ppList, Rwr_Node_t * pNode ) -{ - Rwr_Node_t * pTemp; - // find the last one - for ( pTemp = *ppList; pTemp; pTemp = pTemp->pNext ) - ppList = &pTemp->pNext; - // attach at the end - *ppList = pNode; -} /**Function************************************************************* - Synopsis [Prints one rwr node.] + Synopsis [Adds one node.] Description [] @@ -507,85 +280,19 @@ void Rwr_ListAddToTail( Rwr_Node_t ** ppList, Rwr_Node_t * pNode ) SeeAlso [] ***********************************************************************/ -void Rwr_NodePrint_rec( FILE * pFile, Rwr_Node_t * pNode ) +void Rwr_MarkUsed_rec( Rwr_Man_t * p, Rwr_Node_t * pNode ) { - assert( !Rwr_IsComplement(pNode) ); - - if ( pNode->Id == 0 ) - { - fprintf( pFile, "Const1" ); - return; - } - - if ( pNode->Id < 5 ) - { - fprintf( pFile, "%c", 'a' + pNode->Id - 1 ); + if ( pNode->fUsed || pNode->TravId == p->nTravIds ) return; - } - - if ( Rwr_IsComplement(pNode->p0) ) - { - if ( Rwr_Regular(pNode->p0)->Id < 5 ) - { - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); - fprintf( pFile, "\'" ); - } - else - { - fprintf( pFile, "(" ); - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); - fprintf( pFile, ")\'" ); - } - } - else - { - if ( Rwr_Regular(pNode->p0)->Id < 5 ) - { - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); - } - else - { - fprintf( pFile, "(" ); - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); - fprintf( pFile, ")" ); - } - } - - if ( pNode->fExor ) - fprintf( pFile, "+" ); - - if ( Rwr_IsComplement(pNode->p1) ) - { - if ( Rwr_Regular(pNode->p1)->Id < 5 ) - { - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); - fprintf( pFile, "\'" ); - } - else - { - fprintf( pFile, "(" ); - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); - fprintf( pFile, ")\'" ); - } - } - else - { - if ( Rwr_Regular(pNode->p1)->Id < 5 ) - { - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); - } - else - { - fprintf( pFile, "(" ); - Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); - fprintf( pFile, ")" ); - } - } + pNode->TravId = p->nTravIds; + pNode->fUsed = 1; + Rwr_MarkUsed_rec( p, Rwr_Regular(pNode->p0) ); + Rwr_MarkUsed_rec( p, Rwr_Regular(pNode->p1) ); } /**Function************************************************************* - Synopsis [Prints one rwr node.] + Synopsis [Adds one node.] Description [] @@ -594,27 +301,21 @@ void Rwr_NodePrint_rec( FILE * pFile, Rwr_Node_t * pNode ) SeeAlso [] ***********************************************************************/ -void Rwr_NodePrint( FILE * pFile, Rwr_Man_t * p, Rwr_Node_t * pNode ) +void Rwr_Trav_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, int * pVolume ) { - unsigned uTruth; - fprintf( pFile, "%5d : ", pNode->Id ); - Extra_PrintHex( pFile, pNode->uTruth, 4 ); - fprintf( pFile, " tt=" ); - uTruth = pNode->uTruth; - Extra_PrintBinary( pFile, &uTruth, 16 ); -// fprintf( pFile, " cn=", pNode->Id ); -// uTruth = p->puCanons[pNode->uTruth]; -// Extra_PrintBinary( pFile, &uTruth, 16 ); - fprintf( pFile, " lev=%d", pNode->Level ); - fprintf( pFile, " vol=%d", pNode->Volume ); - fprintf( pFile, " " ); - Rwr_NodePrint_rec( pFile, pNode ); - fprintf( pFile, "\n" ); + if ( pNode->fUsed || pNode->TravId == p->nTravIds ) + return; + pNode->TravId = p->nTravIds; + (*pVolume)++; + if ( pNode->fExor ) + (*pVolume)++; + Rwr_Trav_rec( p, Rwr_Regular(pNode->p0), pVolume ); + Rwr_Trav_rec( p, Rwr_Regular(pNode->p1), pVolume ); } /**Function************************************************************* - Synopsis [Prints one rwr node.] + Synopsis [Adds one node.] Description [] @@ -623,58 +324,18 @@ void Rwr_NodePrint( FILE * pFile, Rwr_Man_t * p, Rwr_Node_t * pNode ) SeeAlso [] ***********************************************************************/ -void Rwr_ManPrintFirst( Rwr_Man_t * p ) +int Rwr_ManNodeVolume( Rwr_Man_t * p, Rwr_Node_t * p0, Rwr_Node_t * p1 ) { - FILE * pFile; - Rwr_Node_t * pNode; - unsigned uTruth; - int nFuncs; - int Counter; - int i; - - pFile = fopen( "graph_lib.txt", "w" ); - - Counter = 0; - nFuncs = (1 << 16); - for ( i = 0; i < nFuncs; i++ ) - { - if ( p->pTable[i] == NULL ) - continue; - if ( i != p->puCanons[i] ) - continue; - - fprintf( pFile, "\nClass %3d ", Counter++ ); - - // count the volume of the bush - { - int Volume = 0; - int nFuncs = 0; - Rwr_ManIncTravId( p ); - for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) - { - if ( pNode->uTruth != p->puCanons[pNode->uTruth] ) - continue; - nFuncs++; - Rwr_Trav2_rec( p, pNode, &Volume ); - } - fprintf( pFile, "Functions = %2d. Volume = %2d. ", nFuncs, Volume ); - } - - uTruth = i; - Extra_PrintBinary( pFile, &uTruth, 16 ); - fprintf( pFile, "\n" ); - - for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) - if ( pNode->uTruth == p->puCanons[pNode->uTruth] ) - Rwr_NodePrint( pFile, p, pNode ); - } - - fclose( pFile ); + int Volume = 0; + Rwr_ManIncTravId( p ); + Rwr_Trav_rec( p, p0, &Volume ); + Rwr_Trav_rec( p, p1, &Volume ); + return Volume; } /**Function************************************************************* - Synopsis [Prints one rwr node.] + Synopsis [Adds one node.] Description [] @@ -683,54 +344,17 @@ void Rwr_ManPrintFirst( Rwr_Man_t * p ) SeeAlso [] ***********************************************************************/ -void Rwr_ManPrintNext( Rwr_Man_t * p ) +void Rwr_ManIncTravId( Rwr_Man_t * p ) { - FILE * pFile; Rwr_Node_t * pNode; - unsigned uTruth; - int nFuncs; - int Counter; int i; - - pFile = fopen( "graph_lib2.txt", "w" ); - - Counter = 0; - nFuncs = (1 << 16); - for ( i = 0; i < 222; i++ ) - { - if ( p->pTable[i] == NULL ) - continue; - - fprintf( pFile, "\nClass %3d ", Counter++ ); - - // count the volume of the bush - { - int Volume = 0; - int nFuncs = 0; - Rwr_ManIncTravId( p ); - for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) - { - if ( pNode->uTruth != p->puCanons[pNode->uTruth] ) - continue; - nFuncs++; - Rwr_Trav2_rec( p, pNode, &Volume ); - } - fprintf( pFile, "Functions = %2d. Volume = %2d. ", nFuncs, Volume ); - } - - uTruth = p->pTable[i]->uTruth; - Extra_PrintBinary( pFile, &uTruth, 16 ); - fprintf( pFile, "\n" ); - - for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) - if ( pNode->uTruth == p->puCanons[pNode->uTruth] ) - Rwr_NodePrint( pFile, p, pNode ); - } - - fclose( pFile ); + if ( p->nTravIds++ < 0x8FFFFFFF ) + return; + Vec_PtrForEachEntry( p->vForest, pNode, i ) + pNode->TravId = 0; + p->nTravIds = 1; } - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/rwr/rwrMan.c b/src/opt/rwr/rwrMan.c index 3d40f79e..ead86b4e 100644 --- a/src/opt/rwr/rwrMan.c +++ b/src/opt/rwr/rwrMan.c @@ -24,34 +24,13 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -// the following practical NPN classes of 4-variable functions were computed -// by considering all 4-input cuts appearing in IWLS, MCNC, and ISCAS benchmarks -#define RWR_NUM_CLASSES 135 -static int s_PracticalClasses[RWR_NUM_CLASSES] = { - 0x0000, 0x0001, 0x0003, 0x0006, 0x0007, 0x000f, 0x0016, 0x0017, 0x0018, 0x0019, 0x001b, - 0x001e, 0x001f, 0x003c, 0x003d, 0x003f, 0x0069, 0x006b, 0x006f, 0x007e, 0x007f, 0x00ff, - 0x0116, 0x0118, 0x0119, 0x011a, 0x011b, 0x011e, 0x011f, 0x012c, 0x012d, 0x012f, 0x013c, - 0x013d, 0x013e, 0x013f, 0x0168, 0x0169, 0x016f, 0x017f, 0x0180, 0x0181, 0x0182, 0x0183, - 0x0186, 0x0189, 0x018b, 0x018f, 0x0198, 0x0199, 0x019b, 0x01a8, 0x01a9, 0x01aa, 0x01ab, - 0x01ac, 0x01ad, 0x01ae, 0x01af, 0x01bf, 0x01e9, 0x01ea, 0x01eb, 0x01ee, 0x01ef, 0x01fe, - 0x033c, 0x033d, 0x033f, 0x0356, 0x0357, 0x0358, 0x0359, 0x035a, 0x035b, 0x035f, 0x0368, - 0x0369, 0x036c, 0x036e, 0x037d, 0x03c0, 0x03c1, 0x03c3, 0x03c7, 0x03cf, 0x03d4, 0x03d5, - 0x03d7, 0x03d8, 0x03d9, 0x03dc, 0x03dd, 0x03de, 0x03fc, 0x0660, 0x0661, 0x0666, 0x0669, - 0x066f, 0x0676, 0x067e, 0x0690, 0x0696, 0x0697, 0x069f, 0x06b1, 0x06b6, 0x06f0, 0x06f2, - 0x06f6, 0x06f9, 0x0776, 0x0778, 0x07b0, 0x07b1, 0x07b4, 0x07bc, 0x07f0, 0x07f2, 0x07f8, - 0x0ff0, 0x1683, 0x1696, 0x1698, 0x169e, 0x16e9, 0x178e, 0x17e8, 0x18e7, 0x19e6, 0x1be4, - 0x1ee1, 0x3cc3, 0x6996 -}; - -static unsigned short Rwr_FunctionPerm( unsigned uTruth, int Phase ); - //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Starts the resynthesis manager.] + Synopsis [Starts rewriting manager.] Description [] @@ -60,85 +39,56 @@ static unsigned short Rwr_FunctionPerm( unsigned uTruth, int Phase ); SeeAlso [] ***********************************************************************/ -Rwr_Man_t * Rwr_ManStart( char * pFileName ) +Rwr_Man_t * Rwr_ManStart( bool fPrecompute ) { Rwr_Man_t * p; - int i, k, nClasses; int clk = clock(); - int TableSize; - p = ALLOC( Rwr_Man_t, 1 ); memset( p, 0, sizeof(Rwr_Man_t) ); - p->nFuncs = (1<<16); - // create the table - TableSize = pFileName? 222: (1<<16); - p->pTable = ALLOC( Rwr_Node_t *, TableSize ); - memset( p->pTable, 0, sizeof(Rwr_Node_t *) * TableSize ); + p->nFuncs = (1<<16); // canonical forms, phases, perms - Extra_Truth4VarNPN( &p->puCanons, &p->pPhases, &p->pPerms ); - // initialize practical classes - p->pPractical = ALLOC( char, p->nFuncs ); - memset( p->pPractical, 0, sizeof(char) * p->nFuncs ); - for ( i = 0; i < RWR_NUM_CLASSES; i++ ) - p->pPractical[ s_PracticalClasses[i] ] = 1; - // set the mapping of classes - nClasses = 0; - p->pMap = ALLOC( unsigned char, p->nFuncs ); - for ( i = 0; i < p->nFuncs; i++ ) - { - if ( i != p->puCanons[i] ) - { - assert( i > p->puCanons[i] ); - p->pMap[i] = p->pMap[p->puCanons[i]]; - continue; - } - p->pMap[i] = nClasses++; - } - printf( "The number of NPN-canonical forms = %d.\n", nClasses ); - - // initialize permutations - for ( i = 0; i < 256; i++ ) - for ( k = 0; k < 16; k++ ) - p->puPerms[i][k] = Rwr_FunctionPerm( i, k ); - - // other stuff - p->nTravIds = 1; - p->vForest = Vec_PtrAlloc( 100 ); - p->vForm = Vec_IntAlloc( 50 ); - p->vFanins = Vec_PtrAlloc( 50 ); - p->vTfo = Vec_PtrAlloc( 50 ); - p->vTfoFor = Vec_PtrAlloc( 50 ); - p->vLevels = Vec_VecAlloc( 50 ); - p->pMmNode = Extra_MmFixedStart( sizeof(Rwr_Node_t) ); +clk = clock(); + Extra_Truth4VarNPN( &p->puCanons, &p->pPhases, &p->pPerms, &p->pMap ); +PRT( "NPN classes precomputation time", clock() - clk ); + // initialize practical NPN classes + p->pPractical = Rwr_ManGetPractical( p ); + // create the table + p->pTable = ALLOC( Rwr_Node_t *, p->nFuncs ); + memset( p->pTable, 0, sizeof(Rwr_Node_t *) * p->nFuncs ); + // create the elementary nodes assert( sizeof(Rwr_Node_t) == sizeof(Rwr_Cut_t) ); - - // initialize forest - Rwr_ManAddVar( p, 0x0000, pFileName ); // constant 0 - Rwr_ManAddVar( p, 0xAAAA, pFileName ); // var A - Rwr_ManAddVar( p, 0xCCCC, pFileName ); // var B - Rwr_ManAddVar( p, 0xF0F0, pFileName ); // var C - Rwr_ManAddVar( p, 0xFF00, pFileName ); // var D + p->pMmNode = Extra_MmFixedStart( sizeof(Rwr_Node_t) ); + p->vForest = Vec_PtrAlloc( 100 ); + Rwr_ManAddVar( p, 0x0000, fPrecompute ); // constant 0 + Rwr_ManAddVar( p, 0xAAAA, fPrecompute ); // var A + Rwr_ManAddVar( p, 0xCCCC, fPrecompute ); // var B + Rwr_ManAddVar( p, 0xF0F0, fPrecompute ); // var C + Rwr_ManAddVar( p, 0xFF00, fPrecompute ); // var D p->nClasses = 5; -PRT( "Manager startup time", clock() - clk ); - - // create the nodes - if ( pFileName == NULL ) - { // precompute + // other stuff + p->nTravIds = 1; + p->puPerms43 = Extra_TruthPerm43(); + p->vLevNums = Vec_IntAlloc( 50 ); + p->vFanins = Vec_PtrAlloc( 50 ); + if ( fPrecompute ) + { // precompute subgraphs Rwr_ManPrecompute( p ); - Rwr_ManWriteToFile( p, "data.aaa" ); - Rwr_ManPrintFirst( p ); + Rwr_ManWriteToArray( p ); + Rwr_ManPrint( p ); } else - { // load previously saved nodes - Rwr_ManLoadFromFile( p, pFileName ); - Rwr_ManPrintNext( p ); + { // load saved subgraphs + Rwr_ManLoadFromArray( p ); +// Rwr_ManPrint( p ); + Rwr_ManPreprocess( p ); + return NULL; } return p; } /**Function************************************************************* - Synopsis [Stops the resynthesis manager.] + Synopsis [Stops rewriting manager.] Description [] @@ -149,21 +99,27 @@ PRT( "Manager startup time", clock() - clk ); ***********************************************************************/ void Rwr_ManStop( Rwr_Man_t * p ) { + if ( p->vClasses ) + { + Rwr_Node_t * pNode; + int i, k; + Vec_VecForEachEntry( p->vClasses, pNode, i, k ) + Vec_IntFree( (Vec_Int_t *)pNode->pNext ); + } if ( p->vFanNums ) Vec_IntFree( p->vFanNums ); if ( p->vReqTimes ) Vec_IntFree( p->vReqTimes ); - Vec_IntFree( p->vForm ); - Vec_PtrFree( p->vFanins ); - Vec_PtrFree( p->vTfoFor ); - Vec_PtrFree( p->vTfo ); - Vec_VecFree( p->vLevels ); + if ( p->vClasses ) Vec_VecFree( p->vClasses ); Vec_PtrFree( p->vForest ); - Extra_MmFixedStop( p->pMmNode, 0 ); + Vec_IntFree( p->vLevNums ); + Vec_PtrFree( p->vFanins ); + Extra_MmFixedStop( p->pMmNode, 0 ); + free( p->pTable ); free( p->pPractical ); + free( p->puPerms43 ); free( p->puCanons ); free( p->pPhases ); free( p->pPerms ); free( p->pMap ); - free( p->pTable ); free( p ); } @@ -220,9 +176,10 @@ Vec_Int_t * Rwr_ManReadDecs( Rwr_Man_t * p ) return p->vForm; } + /**Function************************************************************* - Synopsis [Computes a phase of the 3-var function.] + Synopsis [Precomputes AIG subgraphs.] Description [] @@ -231,42 +188,13 @@ Vec_Int_t * Rwr_ManReadDecs( Rwr_Man_t * p ) SeeAlso [] ***********************************************************************/ -unsigned short Rwr_FunctionPerm( unsigned uTruth, int Phase ) +void Rwr_Precompute() { - static int Perm[16][4] = { - { 0, 1, 2, 3 }, // 0000 - skip - { 0, 1, 2, 3 }, // 0001 - skip - { 1, 0, 2, 3 }, // 0010 - { 0, 1, 2, 3 }, // 0011 - skip - { 2, 1, 0, 3 }, // 0100 - { 0, 2, 1, 3 }, // 0101 - { 2, 0, 1, 3 }, // 0110 - { 0, 1, 2, 3 }, // 0111 - skip - { 3, 1, 2, 0 }, // 1000 - { 0, 3, 2, 1 }, // 1001 - { 3, 0, 2, 1 }, // 1010 - { 0, 1, 3, 2 }, // 1011 - { 2, 3, 0, 1 }, // 1100 - { 0, 3, 1, 2 }, // 1101 - { 3, 0, 1, 2 }, // 1110 - { 0, 1, 2, 3 } // 1111 - skip - }; - int i, k, iRes; - unsigned uTruthRes; - assert( Phase < 16 ); - uTruthRes = 0; - for ( i = 0; i < 16; i++ ) - if ( uTruth & (1 << i) ) - { - for ( iRes = 0, k = 0; k < 4; k++ ) - if ( i & (1 << k) ) - iRes |= (1 << Perm[Phase][k]); - uTruthRes |= (1 << iRes); - } - return uTruthRes; + Rwr_Man_t * p; + p = Rwr_ManStart( 1 ); + Rwr_ManStop( p ); } - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/rwr/rwrPrint.c b/src/opt/rwr/rwrPrint.c new file mode 100644 index 00000000..7c0bc212 --- /dev/null +++ b/src/opt/rwr/rwrPrint.c @@ -0,0 +1,239 @@ +/**CFile**************************************************************** + + FileName [rwrCut.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [DAG-aware AIG rewriting package.] + + Synopsis [Cut computation.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: rwrCut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "rwr.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Adds one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_Trav2_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, int * pVolume ) +{ + if ( pNode->fUsed || pNode->TravId == p->nTravIds ) + return; + pNode->TravId = p->nTravIds; + (*pVolume)++; + Rwr_Trav2_rec( p, Rwr_Regular(pNode->p0), pVolume ); + Rwr_Trav2_rec( p, Rwr_Regular(pNode->p1), pVolume ); +} + +/**Function************************************************************* + + Synopsis [Adds the node to the end of the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_GetBushVolume( Rwr_Man_t * p, int Entry, int * pVolume, int * pnFuncs ) +{ + Rwr_Node_t * pNode; + int Volume = 0; + int nFuncs = 0; + Rwr_ManIncTravId( p ); + for ( pNode = p->pTable[Entry]; pNode; pNode = pNode->pNext ) + { + if ( pNode->uTruth != p->puCanons[pNode->uTruth] ) + continue; + nFuncs++; + Rwr_Trav2_rec( p, pNode, &Volume ); + } + *pVolume = Volume; + *pnFuncs = nFuncs; +} + +/**Function************************************************************* + + Synopsis [Prints one rwr node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_NodePrint_rec( FILE * pFile, Rwr_Node_t * pNode ) +{ + assert( !Rwr_IsComplement(pNode) ); + + if ( pNode->Id == 0 ) + { + fprintf( pFile, "Const1" ); + return; + } + + if ( pNode->Id < 5 ) + { + fprintf( pFile, "%c", 'a' + pNode->Id - 1 ); + return; + } + + if ( Rwr_IsComplement(pNode->p0) ) + { + if ( Rwr_Regular(pNode->p0)->Id < 5 ) + { + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); + fprintf( pFile, "\'" ); + } + else + { + fprintf( pFile, "(" ); + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); + fprintf( pFile, ")\'" ); + } + } + else + { + if ( Rwr_Regular(pNode->p0)->Id < 5 ) + { + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); + } + else + { + fprintf( pFile, "(" ); + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p0) ); + fprintf( pFile, ")" ); + } + } + + if ( pNode->fExor ) + fprintf( pFile, "+" ); + + if ( Rwr_IsComplement(pNode->p1) ) + { + if ( Rwr_Regular(pNode->p1)->Id < 5 ) + { + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); + fprintf( pFile, "\'" ); + } + else + { + fprintf( pFile, "(" ); + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); + fprintf( pFile, ")\'" ); + } + } + else + { + if ( Rwr_Regular(pNode->p1)->Id < 5 ) + { + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); + } + else + { + fprintf( pFile, "(" ); + Rwr_NodePrint_rec( pFile, Rwr_Regular(pNode->p1) ); + fprintf( pFile, ")" ); + } + } +} + +/**Function************************************************************* + + Synopsis [Prints one rwr node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_NodePrint( FILE * pFile, Rwr_Man_t * p, Rwr_Node_t * pNode ) +{ + unsigned uTruth; + fprintf( pFile, "%5d : ", pNode->Id ); + Extra_PrintHex( pFile, pNode->uTruth, 4 ); + fprintf( pFile, " tt=" ); + uTruth = pNode->uTruth; + Extra_PrintBinary( pFile, &uTruth, 16 ); +// fprintf( pFile, " cn=", pNode->Id ); +// uTruth = p->puCanons[pNode->uTruth]; +// Extra_PrintBinary( pFile, &uTruth, 16 ); + fprintf( pFile, " lev=%d", pNode->Level ); + fprintf( pFile, " vol=%d", pNode->Volume ); + fprintf( pFile, " " ); + Rwr_NodePrint_rec( pFile, pNode ); + fprintf( pFile, "\n" ); +} + +/**Function************************************************************* + + Synopsis [Prints one rwr node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManPrint( Rwr_Man_t * p ) +{ + FILE * pFile; + Rwr_Node_t * pNode; + unsigned uTruth; + int Counter, Volume, nFuncs, i; + pFile = fopen( "graph_lib.txt", "w" ); + Counter = 0; + nFuncs = (1 << 16); + for ( i = 0; i < nFuncs; i++ ) + { + if ( p->pTable[i] == NULL ) + continue; + if ( i != p->puCanons[i] ) + continue; + fprintf( pFile, "\nClass %3d ", Counter++ ); + Rwr_GetBushVolume( p, i, &Volume, &nFuncs ); + fprintf( pFile, "Functions = %2d. Volume = %2d. ", nFuncs, Volume ); + uTruth = i; + Extra_PrintBinary( pFile, &uTruth, 16 ); + fprintf( pFile, "\n" ); + for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext ) + if ( pNode->uTruth == p->puCanons[pNode->uTruth] ) + Rwr_NodePrint( pFile, p, pNode ); + } + fclose( pFile ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/rwr/rwrUtil.c b/src/opt/rwr/rwrUtil.c index 96d89db5..30b0cf69 100644 --- a/src/opt/rwr/rwrUtil.c +++ b/src/opt/rwr/rwrUtil.c @@ -24,12 +24,200 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +// precomputed data +unsigned short s_RwrPracticalClasses[]; +unsigned short s_RwtAigSubgraphs[]; + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* + Synopsis [Writes data.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManWriteToArray( Rwr_Man_t * p ) +{ + FILE * pFile; + Rwr_Node_t * pNode; + unsigned Entry0, Entry1; + int i, nEntries, clk = clock(); + // prepare the buffer + nEntries = p->vForest->nSize - 5; + pFile = fopen( "npn4_aig_array.txt", "w" ); + fprintf( pFile, "static unsigned short s_RwtAigSubgraphs[] = \n{" ); + for ( i = 0; i < nEntries; i++ ) + { + if ( i % 5 == 0 ) + fprintf( pFile, "\n " ); + pNode = p->vForest->pArray[i+5]; + Entry0 = (Rwr_Regular(pNode->p0)->Id << 1) | Rwr_IsComplement(pNode->p0); + Entry1 = (Rwr_Regular(pNode->p1)->Id << 1) | Rwr_IsComplement(pNode->p1); + Entry0 = (Entry0 << 1) | pNode->fExor; + Extra_PrintHex( pFile, Entry0, 4 ); + fprintf( pFile, "," ); + Extra_PrintHex( pFile, Entry1, 4 ); + fprintf( pFile, ", " ); + } + if ( i % 5 == 0 ) + fprintf( pFile, "\n " ); + Extra_PrintHex( pFile, 0, 4 ); + fprintf( pFile, "," ); + Extra_PrintHex( pFile, 0, 4 ); + fprintf( pFile, " \n};\n" ); + fclose( pFile ); + printf( "The number of nodes saved = %d. ", nEntries ); PRT( "Saving", clock() - clk ); +} + +/**Function************************************************************* + + Synopsis [Loads data.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManLoadFromArray( Rwr_Man_t * p ) +{ + unsigned short * pArray = s_RwtAigSubgraphs; + Rwr_Node_t * p0, * p1; + unsigned Entry0, Entry1; + int Level, Volume, nEntries, fExor; + int i, clk = clock(); + + // reconstruct the forest + for ( i = 0; ; i++ ) + { + Entry0 = pArray[2*i + 0]; + Entry1 = pArray[2*i + 1]; + if ( Entry0 == 0 && Entry1 == 0 ) + break; + // get EXOR flag + fExor = (Entry0 & 1); + Entry0 >>= 1; + // get the nodes + p0 = p->vForest->pArray[Entry0 >> 1]; + p1 = p->vForest->pArray[Entry1 >> 1]; + // compute the level and volume of the new nodes + Level = 1 + ABC_MAX( p0->Level, p1->Level ); + Volume = 1 + Rwr_ManNodeVolume( p, p0, p1 ); + // set the complemented attributes + p0 = Rwr_NotCond( p0, (Entry0 & 1) ); + p1 = Rwr_NotCond( p1, (Entry1 & 1) ); + // add the node +// Rwr_ManTryNode( p, p0, p1, Level, Volume ); + Rwr_ManAddNode( p, p0, p1, fExor, Level, Volume + fExor ); + } + nEntries = i - 1; + printf( "The number of classes = %d. Canonical nodes = %d.\n", p->nClasses, p->nAdded ); + printf( "The number of nodes loaded = %d. ", nEntries ); PRT( "Loading", clock() - clk ); +} + + +/**Function************************************************************* + + Synopsis [Writes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManWriteToFile( Rwr_Man_t * p, char * pFileName ) +{ + FILE * pFile; + Rwr_Node_t * pNode; + unsigned * pBuffer; + int i, nEntries, clk = clock(); + // prepare the buffer + nEntries = p->vForest->nSize - 5; + pBuffer = ALLOC( unsigned, nEntries * 2 ); + for ( i = 0; i < nEntries; i++ ) + { + pNode = p->vForest->pArray[i+5]; + pBuffer[2*i + 0] = (Rwr_Regular(pNode->p0)->Id << 1) | Rwr_IsComplement(pNode->p0); + pBuffer[2*i + 1] = (Rwr_Regular(pNode->p1)->Id << 1) | Rwr_IsComplement(pNode->p1); + // save EXOR flag + pBuffer[2*i + 0] = (pBuffer[2*i + 0] << 1) | pNode->fExor; + + } + pFile = fopen( pFileName, "wb" ); + fwrite( &nEntries, sizeof(int), 1, pFile ); + fwrite( pBuffer, sizeof(unsigned), nEntries * 2, pFile ); + free( pBuffer ); + fclose( pFile ); + printf( "The number of nodes saved = %d. ", nEntries ); PRT( "Saving", clock() - clk ); +} + +/**Function************************************************************* + + Synopsis [Loads data.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ManLoadFromFile( Rwr_Man_t * p, char * pFileName ) +{ + FILE * pFile; + Rwr_Node_t * p0, * p1; + unsigned * pBuffer; + int Level, Volume, nEntries, fExor; + int i, clk = clock(); + + // load the data + pFile = fopen( pFileName, "rb" ); + if ( pFile == NULL ) + { + printf( "Rwr_ManLoadFromFile: Cannot open file \"%s\".\n", pFileName ); + return; + } + fread( &nEntries, sizeof(int), 1, pFile ); + pBuffer = ALLOC( unsigned, nEntries * 2 ); + fread( pBuffer, sizeof(unsigned), nEntries * 2, pFile ); + fclose( pFile ); + // reconstruct the forest + for ( i = 0; i < nEntries; i++ ) + { + // get EXOR flag + fExor = (pBuffer[2*i + 0] & 1); + pBuffer[2*i + 0] = (pBuffer[2*i + 0] >> 1); + // get the nodes + p0 = p->vForest->pArray[pBuffer[2*i + 0] >> 1]; + p1 = p->vForest->pArray[pBuffer[2*i + 1] >> 1]; + // compute the level and volume of the new nodes + Level = 1 + ABC_MAX( p0->Level, p1->Level ); + Volume = 1 + Rwr_ManNodeVolume( p, p0, p1 ); + // set the complemented attributes + p0 = Rwr_NotCond( p0, (pBuffer[2*i + 0] & 1) ); + p1 = Rwr_NotCond( p1, (pBuffer[2*i + 1] & 1) ); + // add the node +// Rwr_ManTryNode( p, p0, p1, Level, Volume ); + Rwr_ManAddNode( p, p0, p1, fExor, Level, Volume + fExor ); + } + free( pBuffer ); + printf( "The number of classes = %d. Canonical nodes = %d.\n", p->nClasses, p->nAdded ); + printf( "The number of nodes loaded = %d. ", nEntries ); PRT( "Loading", clock() - clk ); +} + + +/**Function************************************************************* + Synopsis [Creates the array of fanout counters.] Description [] @@ -52,8 +240,436 @@ Vec_Int_t * Rwt_NtkFanoutCounters( Abc_Ntk_t * pNtk ) return vFanNums; } +/**Function************************************************************* + + Synopsis [Adds the node to the end of the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Rwr_ListAddToTail( Rwr_Node_t ** ppList, Rwr_Node_t * pNode ) +{ + Rwr_Node_t * pTemp; + // find the last one + for ( pTemp = *ppList; pTemp; pTemp = pTemp->pNext ) + ppList = &pTemp->pNext; + // attach at the end + *ppList = pNode; +} + +/**Function************************************************************* + + Synopsis [Create practical classes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Rwr_ManGetPractical( Rwr_Man_t * p ) +{ + char * pPractical; + int i; + pPractical = ALLOC( char, p->nFuncs ); + memset( pPractical, 0, sizeof(char) * p->nFuncs ); + pPractical[0] = 1; + for ( i = 1; ; i++ ) + { + if ( s_RwrPracticalClasses[i] == 0 ) + break; + pPractical[ s_RwrPracticalClasses[i] ] = 1; + } + return pPractical; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +// the following 135 practical NPN classes of 4-variable functions were computed +// by considering all 4-input cuts appearing in IWLS, MCNC, and ISCAS benchmarks +static unsigned short s_RwrPracticalClasses[] = +{ + 0x0000, 0x0001, 0x0003, 0x0006, 0x0007, 0x000f, 0x0016, 0x0017, 0x0018, 0x0019, 0x001b, + 0x001e, 0x001f, 0x003c, 0x003d, 0x003f, 0x0069, 0x006b, 0x006f, 0x007e, 0x007f, 0x00ff, + 0x0116, 0x0118, 0x0119, 0x011a, 0x011b, 0x011e, 0x011f, 0x012c, 0x012d, 0x012f, 0x013c, + 0x013d, 0x013e, 0x013f, 0x0168, 0x0169, 0x016f, 0x017f, 0x0180, 0x0181, 0x0182, 0x0183, + 0x0186, 0x0189, 0x018b, 0x018f, 0x0198, 0x0199, 0x019b, 0x01a8, 0x01a9, 0x01aa, 0x01ab, + 0x01ac, 0x01ad, 0x01ae, 0x01af, 0x01bf, 0x01e9, 0x01ea, 0x01eb, 0x01ee, 0x01ef, 0x01fe, + 0x033c, 0x033d, 0x033f, 0x0356, 0x0357, 0x0358, 0x0359, 0x035a, 0x035b, 0x035f, 0x0368, + 0x0369, 0x036c, 0x036e, 0x037d, 0x03c0, 0x03c1, 0x03c3, 0x03c7, 0x03cf, 0x03d4, 0x03d5, + 0x03d7, 0x03d8, 0x03d9, 0x03dc, 0x03dd, 0x03de, 0x03fc, 0x0660, 0x0661, 0x0666, 0x0669, + 0x066f, 0x0676, 0x067e, 0x0690, 0x0696, 0x0697, 0x069f, 0x06b1, 0x06b6, 0x06f0, 0x06f2, + 0x06f6, 0x06f9, 0x0776, 0x0778, 0x07b0, 0x07b1, 0x07b4, 0x07bc, 0x07f0, 0x07f2, 0x07f8, + 0x0ff0, 0x1683, 0x1696, 0x1698, 0x169e, 0x16e9, 0x178e, 0x17e8, 0x18e7, 0x19e6, 0x1be4, + 0x1ee1, 0x3cc3, 0x6996, 0x0000 +}; + +static unsigned short s_RwtAigSubgraphs[] = +{ + 0x0008,0x0002, 0x000a,0x0002, 0x0008,0x0003, 0x000a,0x0003, 0x0009,0x0002, + 0x000c,0x0002, 0x000e,0x0002, 0x000c,0x0003, 0x000e,0x0003, 0x000d,0x0002, + 0x000c,0x0004, 0x000e,0x0004, 0x000c,0x0005, 0x000e,0x0005, 0x000d,0x0004, + 0x0010,0x0002, 0x0012,0x0002, 0x0010,0x0003, 0x0012,0x0003, 0x0011,0x0002, + 0x0010,0x0004, 0x0012,0x0004, 0x0010,0x0005, 0x0012,0x0005, 0x0011,0x0004, + 0x0010,0x0006, 0x0012,0x0006, 0x0010,0x0007, 0x0012,0x0007, 0x0011,0x0006, + 0x0016,0x0005, 0x0014,0x0006, 0x0016,0x0006, 0x0014,0x0007, 0x0016,0x0007, + 0x0015,0x0006, 0x0014,0x0008, 0x0016,0x0008, 0x0014,0x0009, 0x0016,0x0009, + 0x0015,0x0008, 0x0018,0x0006, 0x001a,0x0006, 0x0018,0x0007, 0x001a,0x0007, + 0x0019,0x0006, 0x0018,0x0009, 0x001a,0x0009, 0x0019,0x0008, 0x001e,0x0005, + 0x001c,0x0006, 0x001e,0x0006, 0x001c,0x0007, 0x001e,0x0007, 0x001d,0x0006, + 0x001c,0x0008, 0x001e,0x0008, 0x001c,0x0009, 0x001e,0x0009, 0x001d,0x0008, + 0x0020,0x0006, 0x0022,0x0006, 0x0020,0x0007, 0x0022,0x0007, 0x0021,0x0006, + 0x0020,0x0008, 0x0022,0x0008, 0x0020,0x0009, 0x0022,0x0009, 0x0021,0x0008, + 0x0024,0x0006, 0x0026,0x0006, 0x0024,0x0007, 0x0026,0x0007, 0x0025,0x0006, + 0x0026,0x0008, 0x0024,0x0009, 0x0026,0x0009, 0x0025,0x0008, 0x0028,0x0004, + 0x002a,0x0004, 0x0028,0x0005, 0x002a,0x0007, 0x0028,0x0008, 0x002a,0x0009, + 0x0029,0x0008, 0x002a,0x000b, 0x0029,0x000a, 0x002a,0x000f, 0x0029,0x000e, + 0x002a,0x0011, 0x002a,0x0013, 0x002c,0x0004, 0x002e,0x0004, 0x002c,0x0005, + 0x002c,0x0009, 0x002e,0x0009, 0x002d,0x0008, 0x002d,0x000c, 0x002e,0x000f, + 0x002e,0x0011, 0x002e,0x0012, 0x0030,0x0004, 0x0032,0x0007, 0x0032,0x0009, + 0x0031,0x0008, 0x0032,0x000b, 0x0032,0x000d, 0x0032,0x000f, 0x0031,0x000e, + 0x0032,0x0013, 0x0034,0x0004, 0x0036,0x0004, 0x0034,0x0005, 0x0036,0x0005, + 0x0035,0x0004, 0x0036,0x0008, 0x0034,0x0009, 0x0036,0x0009, 0x0035,0x0008, + 0x0036,0x000b, 0x0036,0x000d, 0x0036,0x0011, 0x0035,0x0010, 0x0036,0x0013, + 0x0038,0x0004, 0x0039,0x0004, 0x0038,0x0009, 0x003a,0x0009, 0x0039,0x0008, + 0x0038,0x000b, 0x003a,0x000b, 0x003a,0x000d, 0x003a,0x0011, 0x003a,0x0012, + 0x0038,0x0013, 0x003a,0x0013, 0x003c,0x0002, 0x003e,0x0002, 0x003c,0x0003, + 0x003e,0x0005, 0x003e,0x0007, 0x003c,0x0008, 0x003e,0x0008, 0x003c,0x0009, + 0x003e,0x0009, 0x003d,0x0008, 0x003e,0x000d, 0x003e,0x0011, 0x003e,0x0013, + 0x003e,0x0017, 0x003e,0x001b, 0x003e,0x001d, 0x0040,0x0002, 0x0042,0x0002, + 0x0042,0x0005, 0x0041,0x0006, 0x0042,0x0008, 0x0041,0x0008, 0x0042,0x000d, + 0x0042,0x0011, 0x0042,0x0015, 0x0042,0x0019, 0x0042,0x001b, 0x0042,0x001c, + 0x0041,0x001c, 0x0044,0x0002, 0x0046,0x0003, 0x0045,0x0004, 0x0046,0x0007, + 0x0045,0x0008, 0x0046,0x000b, 0x0046,0x000f, 0x0046,0x0013, 0x0045,0x0012, + 0x0046,0x0017, 0x0046,0x001b, 0x0046,0x0021, 0x0048,0x0002, 0x004a,0x0002, + 0x0048,0x0003, 0x004a,0x0003, 0x0049,0x0002, 0x0048,0x0008, 0x004a,0x0008, + 0x0048,0x0009, 0x004a,0x0009, 0x0049,0x0008, 0x004a,0x000b, 0x004a,0x000f, + 0x004a,0x0011, 0x004a,0x0012, 0x004a,0x0013, 0x004a,0x0015, 0x004a,0x0019, + 0x004a,0x001b, 0x004a,0x001d, 0x004c,0x0002, 0x004c,0x0003, 0x004d,0x0002, + 0x004c,0x0008, 0x004e,0x0008, 0x004c,0x0009, 0x004e,0x0009, 0x004d,0x0008, + 0x004c,0x000b, 0x004e,0x000b, 0x004c,0x000f, 0x004e,0x000f, 0x004e,0x0011, + 0x004c,0x0012, 0x004c,0x0013, 0x004e,0x0013, 0x004e,0x0015, 0x004c,0x0017, + 0x004e,0x0019, 0x004c,0x001b, 0x004e,0x001b, 0x004c,0x001c, 0x004c,0x001d, + 0x004e,0x001d, 0x0050,0x0004, 0x0052,0x0004, 0x0050,0x0006, 0x0052,0x0009, + 0x0052,0x000d, 0x0052,0x000f, 0x0052,0x0013, 0x0052,0x0017, 0x0052,0x0019, + 0x0052,0x001d, 0x0052,0x001f, 0x0052,0x0021, 0x0052,0x0023, 0x0052,0x0024, + 0x0052,0x0025, 0x0051,0x0024, 0x0052,0x0027, 0x0054,0x0004, 0x0056,0x0004, + 0x0054,0x0005, 0x0056,0x0006, 0x0054,0x0007, 0x0056,0x0011, 0x0056,0x001b, + 0x0056,0x001e, 0x0054,0x001f, 0x0056,0x001f, 0x0056,0x0020, 0x0054,0x0021, + 0x0055,0x0020, 0x0056,0x0024, 0x0054,0x0025, 0x0056,0x0025, 0x0055,0x0024, + 0x0054,0x0027, 0x0056,0x0027, 0x0055,0x0026, 0x005a,0x0007, 0x005a,0x0009, + 0x005a,0x000b, 0x005a,0x0015, 0x005a,0x001f, 0x0059,0x0020, 0x0058,0x0024, + 0x005a,0x0024, 0x005a,0x0027, 0x0059,0x0026, 0x005c,0x0004, 0x005e,0x0004, + 0x005c,0x0005, 0x005e,0x0006, 0x005c,0x0007, 0x005d,0x0006, 0x005e,0x000d, + 0x005e,0x0013, 0x005e,0x0017, 0x005c,0x001f, 0x005d,0x001e, 0x005e,0x0020, + 0x005e,0x0021, 0x005e,0x0022, 0x005e,0x0023, 0x005c,0x0024, 0x005e,0x0024, + 0x005c,0x0025, 0x005e,0x0025, 0x005d,0x0024, 0x005e,0x0026, 0x005e,0x0027, + 0x0062,0x0004, 0x0061,0x0004, 0x0062,0x0006, 0x0061,0x0006, 0x0060,0x000f, + 0x0060,0x0013, 0x0062,0x0013, 0x0060,0x0019, 0x0062,0x001c, 0x0060,0x001d, + 0x0062,0x001d, 0x0062,0x001f, 0x0060,0x0021, 0x0060,0x0023, 0x0062,0x0024, + 0x0060,0x0027, 0x0061,0x0026, 0x0064,0x0002, 0x0066,0x0002, 0x0064,0x0006, + 0x0066,0x0007, 0x0066,0x0009, 0x0066,0x000d, 0x0066,0x0013, 0x0066,0x0015, + 0x0066,0x0017, 0x0066,0x0019, 0x0066,0x001a, 0x0065,0x001a, 0x0066,0x001f, + 0x0066,0x0023, 0x0066,0x0027, 0x0066,0x002f, 0x0066,0x0030, 0x006a,0x0002, + 0x0068,0x0003, 0x0068,0x0006, 0x006a,0x0006, 0x006a,0x0011, 0x0068,0x0016, + 0x0068,0x0017, 0x006a,0x0017, 0x006a,0x001a, 0x006a,0x001b, 0x006a,0x0025, + 0x006a,0x002d, 0x006e,0x0003, 0x006e,0x0007, 0x006e,0x0009, 0x006e,0x000b, + 0x006e,0x0015, 0x006e,0x0016, 0x006e,0x0017, 0x006c,0x001a, 0x006e,0x001a, + 0x006e,0x001f, 0x006e,0x002b, 0x006e,0x0035, 0x0070,0x0002, 0x0070,0x0003, + 0x0072,0x0006, 0x0070,0x0007, 0x0071,0x0006, 0x0072,0x000b, 0x0072,0x000f, + 0x0072,0x0013, 0x0070,0x0015, 0x0071,0x0014, 0x0072,0x0017, 0x0072,0x0018, + 0x0070,0x0019, 0x0072,0x0019, 0x0070,0x001a, 0x0070,0x001b, 0x0072,0x001b, + 0x0071,0x001a, 0x0072,0x0021, 0x0072,0x0029, 0x0076,0x0002, 0x0076,0x0003, + 0x0075,0x0002, 0x0076,0x0006, 0x0074,0x0007, 0x0076,0x0007, 0x0075,0x0006, + 0x0076,0x000d, 0x0076,0x0011, 0x0076,0x0013, 0x0075,0x0014, 0x0076,0x0019, + 0x0076,0x001a, 0x0076,0x001b, 0x0075,0x001c, 0x0074,0x0023, 0x0075,0x0022, + 0x0074,0x0026, 0x0076,0x0026, 0x0074,0x0027, 0x0076,0x002b, 0x0076,0x002f, + 0x0078,0x0002, 0x0078,0x0004, 0x007a,0x0004, 0x007a,0x0005, 0x0079,0x0004, + 0x007a,0x0009, 0x007a,0x000a, 0x007a,0x000b, 0x007a,0x000d, 0x007a,0x000f, + 0x007a,0x0010, 0x007a,0x0011, 0x007a,0x0012, 0x007a,0x0013, 0x007a,0x0017, + 0x007a,0x001b, 0x007a,0x0021, 0x007a,0x0027, 0x007a,0x002b, 0x007a,0x002f, + 0x007a,0x0030, 0x0079,0x0034, 0x007a,0x0039, 0x007a,0x003a, 0x007e,0x0002, + 0x007c,0x0004, 0x007e,0x0004, 0x007e,0x000c, 0x007c,0x000d, 0x007e,0x0011, + 0x007e,0x0013, 0x007e,0x001b, 0x007e,0x0025, 0x007e,0x002d, 0x007e,0x0037, + 0x0082,0x0003, 0x0082,0x0005, 0x0082,0x0009, 0x0082,0x000b, 0x0080,0x0010, + 0x0082,0x0010, 0x0082,0x0012, 0x0082,0x0015, 0x0082,0x001f, 0x0082,0x002b, + 0x0082,0x0035, 0x0082,0x0039, 0x0082,0x003f, 0x0084,0x0002, 0x0086,0x0002, + 0x0084,0x0003, 0x0086,0x0003, 0x0085,0x0002, 0x0086,0x0004, 0x0084,0x0005, + 0x0085,0x0004, 0x0086,0x000a, 0x0084,0x000b, 0x0085,0x000a, 0x0086,0x000d, + 0x0086,0x000e, 0x0086,0x000f, 0x0084,0x0010, 0x0084,0x0011, 0x0086,0x0011, + 0x0085,0x0010, 0x0084,0x0012, 0x0084,0x0013, 0x0086,0x0013, 0x0085,0x0012, + 0x0086,0x0019, 0x0086,0x0023, 0x0086,0x0029, 0x0086,0x0033, 0x0086,0x0039, + 0x008a,0x0003, 0x0089,0x0002, 0x0088,0x0004, 0x008a,0x0004, 0x0088,0x0005, + 0x0089,0x0004, 0x008a,0x000b, 0x008a,0x0010, 0x0088,0x0011, 0x008a,0x0011, + 0x0089,0x0010, 0x0088,0x0012, 0x008a,0x0012, 0x0089,0x0012, 0x008a,0x0017, + 0x008a,0x001b, 0x0089,0x0020, 0x008a,0x0025, 0x0088,0x0027, 0x008a,0x002b, + 0x008a,0x002f, 0x008a,0x0039, 0x0088,0x003a, 0x008d,0x0044, 0x0092,0x0009, + 0x0092,0x0025, 0x0092,0x0029, 0x0092,0x002d, 0x0092,0x0033, 0x0092,0x0037, + 0x0092,0x003d, 0x0092,0x0041, 0x0095,0x0002, 0x0095,0x0004, 0x0095,0x0010, + 0x0095,0x0012, 0x0096,0x0021, 0x0096,0x0029, 0x0095,0x002e, 0x0096,0x0030, + 0x0096,0x0033, 0x0096,0x003a, 0x0096,0x0043, 0x009a,0x0008, 0x009a,0x0009, + 0x0099,0x0008, 0x009a,0x0011, 0x009a,0x0023, 0x009a,0x0033, 0x009a,0x003d, + 0x009a,0x0044, 0x009a,0x0045, 0x0099,0x0044, 0x009d,0x0002, 0x009e,0x0008, + 0x009c,0x0009, 0x009e,0x0009, 0x009d,0x0008, 0x009e,0x0011, 0x009d,0x0010, + 0x009e,0x001f, 0x009e,0x003f, 0x00a0,0x0009, 0x00a0,0x0011, 0x00a2,0x0030, + 0x00a2,0x0033, 0x00a6,0x0006, 0x00a6,0x0007, 0x00a6,0x0011, 0x00a6,0x0044, + 0x00a6,0x004b, 0x00aa,0x0007, 0x00aa,0x0015, 0x00ae,0x0006, 0x00ae,0x0011, + 0x00ae,0x001b, 0x00ae,0x0025, 0x00ae,0x003d, 0x00ae,0x0041, 0x00ae,0x0043, + 0x00ae,0x0045, 0x00b2,0x0006, 0x00b0,0x0007, 0x00b1,0x0006, 0x00b2,0x0017, + 0x00b1,0x0016, 0x00b0,0x0019, 0x00b2,0x0021, 0x00b2,0x003d, 0x00b5,0x004a, + 0x00ba,0x0009, 0x00ba,0x000f, 0x00bc,0x0009, 0x00be,0x0009, 0x00be,0x000f, + 0x00bd,0x000e, 0x00be,0x0017, 0x00c2,0x0009, 0x00c2,0x0019, 0x00c2,0x001f, + 0x00c2,0x0033, 0x00c6,0x0009, 0x00c5,0x000e, 0x00c6,0x0015, 0x00c6,0x0023, + 0x00c4,0x002d, 0x00c6,0x002f, 0x00c5,0x002e, 0x00c6,0x0045, 0x00ce,0x0007, + 0x00ce,0x0021, 0x00ce,0x0023, 0x00ce,0x0025, 0x00ce,0x0027, 0x00ce,0x0033, + 0x00ce,0x003d, 0x00d2,0x0006, 0x00d0,0x0015, 0x00d0,0x001b, 0x00d2,0x001b, + 0x00d1,0x001a, 0x00d0,0x001f, 0x00d2,0x0025, 0x00d1,0x0024, 0x00d2,0x0037, + 0x00d2,0x0041, 0x00d2,0x0045, 0x00d9,0x0044, 0x00e1,0x0004, 0x00e2,0x000d, + 0x00e2,0x0021, 0x00e0,0x003a, 0x00e6,0x003d, 0x00e6,0x0061, 0x00e6,0x0067, + 0x00e9,0x0004, 0x00ea,0x0008, 0x00ea,0x0009, 0x00ea,0x0039, 0x00e9,0x0038, + 0x00ea,0x003f, 0x00ec,0x000d, 0x00ee,0x000d, 0x00ee,0x0037, 0x00f2,0x003d, + 0x00f2,0x0062, 0x00f5,0x0002, 0x00fa,0x0017, 0x00fa,0x003d, 0x00fe,0x0006, + 0x00fd,0x0006, 0x00fc,0x0015, 0x00fe,0x001b, 0x00fc,0x0025, 0x00fe,0x0025, + 0x00fd,0x0024, 0x00fe,0x0041, 0x00fe,0x004d, 0x00fd,0x004e, 0x0101,0x0014, + 0x0106,0x004d, 0x010a,0x0009, 0x010a,0x000b, 0x0109,0x000a, 0x010a,0x004f, + 0x010a,0x0058, 0x010e,0x0008, 0x010c,0x0009, 0x010e,0x0009, 0x010d,0x0008, + 0x010e,0x000b, 0x010e,0x002b, 0x010d,0x002a, 0x010e,0x0035, 0x010e,0x003d, + 0x010e,0x003f, 0x010e,0x0049, 0x010e,0x0057, 0x010d,0x0056, 0x010d,0x0058, + 0x0111,0x0004, 0x0111,0x0006, 0x0110,0x0009, 0x0112,0x0009, 0x0111,0x0008, + 0x0112,0x002f, 0x0110,0x0035, 0x0110,0x0037, 0x0112,0x0039, 0x0112,0x003d, + 0x0112,0x003f, 0x0112,0x0045, 0x0111,0x0044, 0x0112,0x004b, 0x0112,0x0059, + 0x0112,0x0069, 0x0112,0x007f, 0x0116,0x0009, 0x0115,0x0008, 0x0114,0x000b, + 0x0116,0x000b, 0x0116,0x0058, 0x011a,0x0015, 0x011a,0x001f, 0x011a,0x002b, + 0x011a,0x003f, 0x011a,0x0049, 0x011a,0x0085, 0x011e,0x0007, 0x011e,0x0019, + 0x011e,0x001b, 0x011e,0x0023, 0x011e,0x0027, 0x011e,0x002f, 0x011e,0x0043, + 0x011e,0x004b, 0x011e,0x004e, 0x011e,0x004f, 0x011e,0x005f, 0x011e,0x0061, + 0x011e,0x0065, 0x011e,0x0083, 0x0122,0x0006, 0x0120,0x0007, 0x0122,0x0007, + 0x0121,0x0006, 0x0122,0x0049, 0x0121,0x004e, 0x0122,0x008f, 0x0125,0x0004, + 0x0124,0x0007, 0x0125,0x0006, 0x0124,0x001b, 0x0126,0x001b, 0x0126,0x0045, + 0x0126,0x0087, 0x0128,0x0007, 0x0129,0x0006, 0x012a,0x0019, 0x012a,0x003d, + 0x012a,0x0051, 0x012a,0x0065, 0x012a,0x0083, 0x012d,0x005a, 0x0132,0x0009, + 0x0132,0x008f, 0x0134,0x0009, 0x0135,0x003e, 0x013a,0x003d, 0x013a,0x0044, + 0x0139,0x0044, 0x013e,0x0009, 0x013d,0x0008, 0x013c,0x003d, 0x013c,0x0044, + 0x013c,0x0053, 0x013e,0x008f, 0x013e,0x0095, 0x0142,0x0044, 0x0142,0x0097, + 0x0142,0x009e, 0x0144,0x0007, 0x0148,0x0015, 0x0148,0x001c, 0x0148,0x001f, + 0x0148,0x0026, 0x0149,0x0086, 0x014d,0x0006, 0x014e,0x0044, 0x014d,0x0048, + 0x014e,0x009e, 0x0152,0x0009, 0x0151,0x00a6, 0x0155,0x0030, 0x015d,0x003a, + 0x0162,0x009e, 0x0164,0x000f, 0x0164,0x0013, 0x0169,0x000e, 0x0174,0x0009, + 0x0179,0x0008, 0x0180,0x0009, 0x0181,0x0044, 0x0186,0x0044, 0x0185,0x0044, + 0x018a,0x0068, 0x0195,0x004e, 0x01a6,0x0009, 0x01a5,0x0008, 0x01b1,0x003a, + 0x01c4,0x0029, 0x01c4,0x0030, 0x01ca,0x008f, 0x01ca,0x0095, 0x01cc,0x0029, + 0x01cc,0x0033, 0x01ce,0x003d, 0x01d6,0x00b2, 0x01d8,0x0009, 0x01d9,0x002a, + 0x01d9,0x0056, 0x01d9,0x00a4, 0x01dd,0x003a, 0x01e2,0x00b2, 0x01e6,0x0013, + 0x01e6,0x009f, 0x01e6,0x00ba, 0x01e6,0x00c0, 0x01e6,0x00d3, 0x01e6,0x00d5, + 0x01e6,0x00e5, 0x01e8,0x0005, 0x01f2,0x0013, 0x01f2,0x0095, 0x01f2,0x009f, + 0x01f2,0x00ba, 0x01f2,0x00c0, 0x01f2,0x00d3, 0x0202,0x008f, 0x0202,0x0095, + 0x0202,0x00f3, 0x0202,0x00f9, 0x020a,0x0044, 0x0209,0x00b4, 0x020e,0x0009, + 0x020d,0x0008, 0x020c,0x003d, 0x020c,0x0044, 0x020c,0x0053, 0x020e,0x008f, + 0x020e,0x0095, 0x020c,0x00b1, 0x020e,0x00f3, 0x020e,0x00f9, 0x0210,0x0013, + 0x0211,0x0024, 0x0210,0x0026, 0x0219,0x0004, 0x021e,0x008f, 0x021e,0x0095, + 0x0221,0x003a, 0x0230,0x0009, 0x0236,0x0009, 0x0234,0x0029, 0x0234,0x0030, + 0x0234,0x0033, 0x0234,0x003a, 0x0234,0x003d, 0x0234,0x0044, 0x0235,0x00a6, + 0x023a,0x0009, 0x023d,0x003a, 0x0245,0x0044, 0x0249,0x003a, 0x024e,0x009e, + 0x024e,0x0106, 0x0251,0x0026, 0x0258,0x0013, 0x0259,0x0024, 0x0258,0x0061, + 0x0259,0x0086, 0x0258,0x00c7, 0x0258,0x00df, 0x0259,0x00ec, 0x0258,0x00fc, + 0x025d,0x0024, 0x025d,0x00de, 0x0260,0x00f6, 0x0268,0x0009, 0x0269,0x0044, + 0x0268,0x00f3, 0x0268,0x00f9, 0x026d,0x003a, 0x0270,0x0068, 0x0275,0x003a, + 0x027a,0x0044, 0x0279,0x0044, 0x027e,0x007e, 0x0281,0x0044, 0x0285,0x0008, + 0x028d,0x0006, 0x028d,0x00d2, 0x0295,0x00cc, 0x0296,0x00f6, 0x0295,0x00f8, + 0x0299,0x0030, 0x029e,0x007e, 0x029d,0x0080, 0x02a6,0x008f, 0x02a6,0x0095, + 0x02aa,0x0029, 0x02aa,0x0030, 0x02b5,0x0008, 0x02b9,0x003a, 0x02bd,0x0004, + 0x02bd,0x00fc, 0x02c2,0x00b2, 0x02c1,0x00b4, 0x02c4,0x0029, 0x02c8,0x0029, + 0x02c8,0x0033, 0x02ca,0x003d, 0x02ce,0x0029, 0x02ce,0x0030, 0x02d2,0x0068, + 0x02d1,0x006a, 0x02d5,0x006a, 0x02d9,0x0008, 0x02de,0x012c, 0x02e2,0x012c, + 0x02e4,0x0009, 0x02e5,0x002a, 0x02e5,0x0056, 0x02e5,0x012c, 0x02ea,0x0029, + 0x02ea,0x0030, 0x02e9,0x0030, 0x02ec,0x0029, 0x02ec,0x0030, 0x02ee,0x012c, + 0x02f1,0x0068, 0x02f1,0x00b2, 0x02f1,0x0108, 0x02f1,0x012c, 0x02f6,0x0013, + 0x02f6,0x0015, 0x02f6,0x001f, 0x02f6,0x0030, 0x02f6,0x0065, 0x02f6,0x0067, + 0x02f6,0x009f, 0x02f6,0x00b6, 0x02f6,0x00b9, 0x02f6,0x00c0, 0x02f6,0x00cf, + 0x02f6,0x0107, 0x02f6,0x010b, 0x02f6,0x010f, 0x02f6,0x0115, 0x02f6,0x012d, + 0x02f6,0x0134, 0x02f6,0x0153, 0x02f6,0x0171, 0x02f6,0x0176, 0x02f8,0x0003, + 0x02fa,0x017b, 0x02fc,0x00ba, 0x02fc,0x00d3, 0x0302,0x0013, 0x0302,0x001f, + 0x0302,0x0030, 0x0302,0x005d, 0x0302,0x0065, 0x0302,0x0067, 0x0302,0x0099, + 0x0302,0x009f, 0x0302,0x00ad, 0x0302,0x00b9, 0x0302,0x00c0, 0x0302,0x00cf, + 0x0301,0x00d2, 0x0301,0x00fe, 0x0302,0x0107, 0x0302,0x010b, 0x0302,0x010f, + 0x0302,0x0117, 0x0302,0x0134, 0x0302,0x0153, 0x0302,0x0157, 0x0302,0x0176, + 0x0306,0x0029, 0x0308,0x00b2, 0x0309,0x00dc, 0x030d,0x00f8, 0x0312,0x00f3, + 0x0318,0x007e, 0x031d,0x0080, 0x0321,0x0008, 0x0321,0x0094, 0x0326,0x017b, + 0x0326,0x0181, 0x0329,0x012e, 0x032a,0x017b, 0x032a,0x0181, 0x032e,0x008f, + 0x032e,0x0095, 0x032e,0x00f3, 0x032e,0x00f9, 0x0332,0x0009, 0x0331,0x0008, + 0x0330,0x003d, 0x0330,0x0044, 0x0330,0x0053, 0x0332,0x008f, 0x0332,0x0095, + 0x0330,0x00b1, 0x0332,0x00f3, 0x0332,0x00f9, 0x0330,0x0127, 0x0332,0x017b, + 0x0332,0x0181, 0x033c,0x0013, 0x033c,0x001c, 0x033d,0x0086, 0x033d,0x00ec, + 0x033d,0x0172, 0x033e,0x019d, 0x0345,0x0002, 0x0344,0x008f, 0x0344,0x00f3, + 0x034d,0x0030, 0x0352,0x0033, 0x0354,0x0029, 0x0354,0x0030, 0x035a,0x0009, + 0x035a,0x017b, 0x035a,0x019b, 0x035a,0x01a2, 0x035e,0x0181, 0x0360,0x0009, + 0x0366,0x0009, 0x0364,0x0029, 0x0364,0x0030, 0x0364,0x0033, 0x0364,0x003a, + 0x0364,0x003d, 0x0364,0x0044, 0x0369,0x0030, 0x0370,0x0029, 0x0370,0x0030, + 0x0376,0x0033, 0x037a,0x0009, 0x037a,0x019b, 0x037a,0x01a2, 0x037c,0x0009, + 0x0382,0x0181, 0x0386,0x0009, 0x0384,0x0029, 0x0384,0x0030, 0x0384,0x0033, + 0x0384,0x003a, 0x0384,0x003d, 0x0384,0x0044, 0x038a,0x0044, 0x038a,0x009e, + 0x038a,0x0106, 0x038a,0x0198, 0x038d,0x010e, 0x038d,0x0152, 0x038d,0x0158, + 0x0392,0x009e, 0x0392,0x0106, 0x0392,0x0198, 0x0395,0x0086, 0x0395,0x009a, + 0x0395,0x00ec, 0x0395,0x0172, 0x0398,0x014e, 0x0398,0x0175, 0x0398,0x018d, + 0x039c,0x0023, 0x039c,0x0027, 0x039c,0x00ef, 0x039c,0x0139, 0x039c,0x0168, + 0x03a0,0x0019, 0x03a0,0x001d, 0x03a0,0x0023, 0x03a0,0x0027, 0x03a1,0x004e, + 0x03a4,0x0162, 0x03a4,0x0183, 0x03a8,0x0013, 0x03a8,0x0027, 0x03a8,0x0133, + 0x03a8,0x0148, 0x03a8,0x0181, 0x03ac,0x0013, 0x03ac,0x0027, 0x03b0,0x017b, + 0x03b0,0x0181, 0x03b4,0x004b, 0x03b4,0x00e0, 0x03b4,0x00fb, 0x03b8,0x000f, + 0x03b8,0x0013, 0x03b8,0x00ab, 0x03b8,0x00bf, 0x03b8,0x00d0, 0x03bd,0x00da, + 0x03bd,0x012c, 0x03c8,0x000f, 0x03c8,0x0013, 0x03c8,0x0019, 0x03c8,0x001d, + 0x03cd,0x0086, 0x03cd,0x00ec, 0x03cd,0x0172, 0x03d2,0x00e0, 0x03d2,0x00ef, + 0x03d2,0x0112, 0x03d2,0x0139, 0x03d2,0x0168, 0x03d6,0x017b, 0x03d6,0x0181, + 0x03da,0x0133, 0x03da,0x0148, 0x03e2,0x0023, 0x03e2,0x0027, 0x03e6,0x0027, + 0x03e6,0x0181, 0x03ee,0x017b, 0x03ee,0x0181, 0x03fe,0x003d, 0x0401,0x012a, + 0x0401,0x019e, 0x0405,0x01a0, 0x040a,0x000d, 0x040a,0x011f, 0x040a,0x016f, + 0x040d,0x012a, 0x0412,0x017b, 0x041a,0x0033, 0x041a,0x003d, 0x041a,0x0181, + 0x0421,0x0086, 0x0421,0x009a, 0x0421,0x00ec, 0x0421,0x0172, 0x042e,0x0205, + 0x043a,0x0205, 0x043e,0x017b, 0x0442,0x01f5, 0x044c,0x0007, 0x0452,0x0033, + 0x0452,0x01ce, 0x0452,0x01d0, 0x0452,0x01f1, 0x0452,0x01fb, 0x0452,0x0225, + 0x0454,0x0005, 0x045a,0x0033, 0x045a,0x0181, 0x045a,0x01ce, 0x045a,0x01d0, + 0x045a,0x01f1, 0x0469,0x01de, 0x046e,0x0181, 0x047a,0x01ce, 0x047a,0x01f1, + 0x0485,0x012c, 0x0489,0x012c, 0x0490,0x01d8, 0x0496,0x0033, 0x0496,0x003d, + 0x0498,0x008f, 0x0498,0x00f3, 0x049e,0x0044, 0x049e,0x0221, 0x04a1,0x0006, + 0x04a2,0x0044, 0x04a6,0x0221, 0x04a9,0x0004, 0x04ac,0x0027, 0x04b1,0x009a, + 0x04b6,0x0097, 0x04b8,0x0027, 0x04c6,0x0219, 0x04ca,0x017b, 0x04cc,0x004b, + 0x04d0,0x00ab, 0x04d6,0x017b, 0x04d8,0x000f, 0x04d8,0x0019, 0x04d8,0x0033, + 0x04d8,0x003d, 0x04de,0x003d, 0x04de,0x0103, 0x04de,0x018b, 0x04de,0x0231, + 0x04e2,0x0044, 0x04e2,0x009e, 0x04e2,0x0106, 0x04e2,0x0198, 0x04e5,0x01a4, + 0x04e5,0x01b6, 0x04ea,0x009e, 0x04ea,0x0106, 0x04ea,0x0198, 0x04ed,0x002e, + 0x04ed,0x0038, 0x04ed,0x00a2, 0x04f1,0x0086, 0x04f1,0x009a, 0x04f1,0x00ec, + 0x04f1,0x0172, 0x04f9,0x004e, 0x04f8,0x0229, 0x04f8,0x022d, 0x0500,0x023e, + 0x0504,0x0217, 0x0510,0x00f3, 0x0514,0x0043, 0x0514,0x004d, 0x0514,0x00c3, + 0x0514,0x013d, 0x0514,0x0215, 0x0514,0x0232, 0x0515,0x0260, 0x0519,0x002a, + 0x0518,0x0030, 0x0518,0x0067, 0x0518,0x00c9, 0x0518,0x01eb, 0x0518,0x01ef, + 0x051c,0x0139, 0x051c,0x0168, 0x0520,0x0027, 0x0526,0x014e, 0x0526,0x0175, + 0x0526,0x018d, 0x052d,0x0200, 0x0532,0x0021, 0x0532,0x00bf, 0x0532,0x00d0, + 0x0532,0x0239, 0x0532,0x0266, 0x053d,0x0024, 0x053d,0x00da, 0x054a,0x000f, + 0x054a,0x00ab, 0x054a,0x023a, 0x054e,0x0043, 0x054e,0x004d, 0x054e,0x00c3, + 0x054e,0x013d, 0x054e,0x0215, 0x054e,0x0232, 0x054e,0x029d, 0x0552,0x014e, + 0x0552,0x018d, 0x0556,0x00f3, 0x0556,0x01e4, 0x055a,0x0299, 0x055d,0x0086, + 0x055d,0x009a, 0x055d,0x00ec, 0x055d,0x0172, 0x0566,0x01dc, 0x0566,0x02a5, + 0x056d,0x020a, 0x057a,0x003d, 0x057a,0x01d4, 0x057a,0x01f3, 0x0579,0x025e, + 0x057e,0x0139, 0x057e,0x0168, 0x0581,0x0006, 0x0586,0x017b, 0x0586,0x0181, + 0x0586,0x028c, 0x0588,0x0007, 0x058e,0x0033, 0x058e,0x008f, 0x058e,0x01d0, + 0x058e,0x027c, 0x0590,0x0003, 0x0596,0x0033, 0x0596,0x008f, 0x0596,0x0095, + 0x0596,0x01d0, 0x0596,0x027c, 0x05a2,0x026f, 0x05a5,0x0284, 0x05aa,0x017b, + 0x05ac,0x0205, 0x05b2,0x008f, 0x05b6,0x017b, 0x05b8,0x01da, 0x05c1,0x0276, + 0x05c6,0x0248, 0x05c8,0x0247, 0x05c8,0x027e, 0x05cc,0x003d, 0x05cc,0x01d4, + 0x05cc,0x01f3, 0x05d0,0x014e, 0x05d0,0x018d, 0x05da,0x00f9, 0x05dd,0x0006, + 0x05de,0x0044, 0x05e5,0x002e, 0x05e6,0x02f1, 0x05ea,0x01d4, 0x05ea,0x01f3, + 0x05ea,0x022d, 0x05ed,0x0002, 0x05f6,0x0027, 0x05fa,0x0097, 0x05fc,0x003d, + 0x0602,0x003d, 0x0606,0x00f3, 0x060a,0x0027, 0x060e,0x003d, 0x060e,0x0103, + 0x060e,0x018b, 0x060e,0x0231, 0x060e,0x02d1, 0x0611,0x01fc, 0x0611,0x0234, + 0x061a,0x0287, 0x061d,0x0214, 0x0621,0x01d4, 0x062a,0x0027, 0x062a,0x022d, + 0x062e,0x009e, 0x062e,0x0106, 0x062e,0x0198, 0x0632,0x009e, 0x0632,0x0106, + 0x0632,0x0198, 0x0639,0x0042, 0x0639,0x00b2, 0x0639,0x0108, 0x063d,0x01f8, + 0x0641,0x0086, 0x0641,0x009a, 0x0641,0x00ec, 0x0641,0x0172, 0x0645,0x0044, + 0x0649,0x0042, 0x0648,0x0087, 0x0648,0x00ed, 0x0648,0x0173, 0x0649,0x01a0, + 0x0648,0x0241, 0x0648,0x026f, 0x0648,0x02df, 0x0648,0x0307, 0x064c,0x023a, + 0x064c,0x02b3, 0x0651,0x0062, 0x0650,0x0217, 0x0651,0x02ac, 0x0650,0x02d6, + 0x0655,0x0042, 0x065d,0x0042, 0x0664,0x02b1, 0x0664,0x02ce, 0x0669,0x0238, + 0x066d,0x002a, 0x066c,0x0039, 0x066d,0x01f6, 0x066c,0x0213, 0x066c,0x022e, + 0x066d,0x02a2, 0x066c,0x02e1, 0x0671,0x002a, 0x0670,0x0030, 0x0670,0x0067, + 0x0670,0x00c9, 0x0670,0x01eb, 0x0670,0x01ef, 0x0670,0x02c3, 0x0675,0x0020, + 0x0678,0x0133, 0x0678,0x0148, 0x067c,0x0027, 0x0681,0x023a, 0x0684,0x0021, + 0x0684,0x00bf, 0x0684,0x00d0, 0x0689,0x01fc, 0x068e,0x0162, 0x068e,0x0183, + 0x0691,0x0200, 0x0696,0x0023, 0x0696,0x00e0, 0x0696,0x00fb, 0x0696,0x0268, + 0x069a,0x0282, 0x069d,0x007e, 0x06a2,0x004b, 0x06a2,0x023e, 0x06a2,0x02dc, + 0x06a6,0x0097, 0x06aa,0x02b1, 0x06aa,0x02ce, 0x06ae,0x0039, 0x06ae,0x0213, + 0x06ae,0x022e, 0x06ae,0x02e1, 0x06b2,0x0162, 0x06b2,0x0183, 0x06b6,0x0023, + 0x06b6,0x00e0, 0x06b6,0x00fb, 0x06ba,0x008f, 0x06ba,0x01e4, 0x06be,0x034b, + 0x06c1,0x0086, 0x06c1,0x009a, 0x06c1,0x00ec, 0x06c1,0x0172, 0x06c6,0x01da, + 0x06c6,0x0280, 0x06c6,0x0351, 0x06ce,0x008f, 0x06d2,0x01e3, 0x06d2,0x0287, + 0x06d2,0x0353, 0x06d6,0x027a, 0x06d6,0x029b, 0x06da,0x0033, 0x06da,0x01ce, + 0x06da,0x01f1, 0x06de,0x0133, 0x06de,0x0148, 0x06e2,0x0021, 0x06e2,0x00bf, + 0x06e2,0x00d0, 0x06e5,0x023a, 0x06e9,0x0004, 0x06ee,0x028c, 0x06ee,0x0338, + 0x06f2,0x0328, 0x06f2,0x0330, 0x06f4,0x0005, 0x06f9,0x01e0, 0x06fe,0x0328, + 0x06fe,0x0330, 0x0702,0x003d, 0x0702,0x00f3, 0x0702,0x0330, 0x0704,0x0003, + 0x070a,0x003d, 0x070a,0x00f3, 0x070a,0x01d4, 0x070a,0x01f3, 0x070a,0x0330, + 0x0711,0x032a, 0x0711,0x032e, 0x0716,0x003d, 0x0718,0x0205, 0x0718,0x0282, + 0x071e,0x00f3, 0x0720,0x01dc, 0x0720,0x02a5, 0x0726,0x0324, 0x072a,0x028a, + 0x072a,0x02a7, 0x0729,0x031c, 0x0729,0x032a, 0x072e,0x003d, 0x072e,0x00f9, + 0x072e,0x022d, 0x072e,0x0248, 0x072e,0x02e4, 0x0730,0x003d, 0x0730,0x0247, + 0x0730,0x02e3, 0x0730,0x0324, 0x0732,0x0324, 0x0739,0x032e, 0x073e,0x003d, + 0x0740,0x003d, 0x0744,0x027a, 0x0744,0x029b, 0x0748,0x0033, 0x0748,0x01ce, + 0x0748,0x01f1, 0x074c,0x0162, 0x074c,0x0183, 0x0750,0x0023, 0x0750,0x00e0, + 0x0750,0x00fb, 0x0755,0x0246, 0x075a,0x0095, 0x075a,0x0397, 0x075d,0x0004, + 0x076a,0x03b3, 0x076d,0x0002, 0x0772,0x02fb, 0x0772,0x0301, 0x0772,0x0315, + 0x0772,0x0397, 0x0776,0x008f, 0x077e,0x0027, 0x078a,0x00a1, 0x0792,0x009d, + 0x0792,0x00c3, 0x0792,0x02fb, 0x0792,0x0301, 0x0792,0x0315, 0x0792,0x03bd, + 0x0796,0x0027, 0x0796,0x024f, 0x079e,0x009d, 0x07a6,0x009d, 0x07a6,0x02fb, + 0x07a6,0x0301, 0x07a6,0x0315, 0x07a6,0x03bd, 0x07aa,0x0027, 0x07aa,0x024f, + 0x07ae,0x009d, 0x07b9,0x004e, 0x07b8,0x0087, 0x07b8,0x00ed, 0x07b8,0x0173, + 0x07b8,0x0197, 0x07b9,0x021a, 0x07b9,0x02b8, 0x07b9,0x0364, 0x07be,0x0029, + 0x07be,0x0030, 0x07c0,0x017b, 0x07c6,0x017b, 0x07c8,0x00f3, 0x07ce,0x00f3, + 0x07d0,0x008f, 0x07d6,0x008f, 0x07d9,0x01e8, 0x07dd,0x0292, 0x07e2,0x0053, + 0x07e6,0x008f, 0x07e6,0x00f3, 0x07e6,0x017b, 0x07e8,0x0029, 0x07e8,0x0030, + 0x07ec,0x0021, 0x07ec,0x02ad, 0x07f2,0x0181, 0x07f2,0x0315, 0x07f4,0x0021, + 0x07f8,0x020f, 0x07fd,0x002e, 0x0800,0x008f, 0x0805,0x0006, 0x0809,0x03c2, + 0x080d,0x0084, 0x0812,0x0009, 0x0811,0x0008, 0x0812,0x00f3, 0x0812,0x00f9, + 0x0812,0x017b, 0x0812,0x0181, 0x0814,0x0033, 0x0818,0x0023, 0x081c,0x0285, + 0x0826,0x03bd, 0x082c,0x008f, 0x082c,0x017b, 0x0832,0x0043, 0x0832,0x011b, + 0x0832,0x01b3, 0x0832,0x01c3, 0x0835,0x032a, 0x0838,0x0085, 0x0839,0x032a, + 0x083e,0x0049, 0x083d,0x0084, 0x083e,0x02fb, 0x083e,0x0301, 0x083e,0x0315, + 0x083e,0x0397, 0x0842,0x0009, 0x0841,0x0008, 0x0844,0x0009, 0x0846,0x008f, + 0x084a,0x0033, 0x084e,0x0285, 0x0851,0x009a, 0x0856,0x00a1, 0x0859,0x031c, + 0x085d,0x00b2, 0x0861,0x0012, 0x0861,0x02cc, 0x0865,0x0058, 0x0865,0x007e, + 0x0869,0x004a, 0x0871,0x0010, 0x0876,0x003d, 0x0879,0x032c, 0x087e,0x0089, + 0x0882,0x0229, 0x0882,0x022d, 0x0882,0x02c7, 0x0882,0x02cb, 0x0886,0x0021, + 0x0886,0x02ad, 0x0885,0x0356, 0x088a,0x0017, 0x088a,0x020f, 0x0889,0x0354, + 0x088d,0x009c, 0x0892,0x0089, 0x0895,0x0246, 0x089a,0x03bd, 0x089e,0x008f, + 0x089e,0x02f9, 0x089e,0x0313, 0x08a1,0x032a, 0x08a6,0x0053, 0x08a6,0x0095, + 0x08a6,0x0397, 0x08a8,0x017b, 0x08ad,0x031a, 0x08b2,0x017b, 0x08b4,0x00f3, + 0x08b5,0x02a0, 0x08b8,0x0089, 0x08c1,0x0024, 0x08c4,0x00f3, 0x08c9,0x007e, + 0x08cd,0x007c, 0x08cd,0x0222, 0x08cd,0x0294, 0x08d1,0x003a, 0x08d6,0x0009, + 0x08d9,0x003a, 0x08dc,0x001f, 0x08e0,0x008f, 0x08e0,0x017b, 0x08e4,0x0009, + 0x08e8,0x01ed, 0x08ed,0x031c, 0x08f2,0x003d, 0x08f6,0x008f, 0x08f6,0x017b, + 0x08fa,0x0009, 0x08fe,0x003d, 0x0902,0x01e9, 0x0904,0x01e9, 0x0904,0x0381, + 0x090a,0x03b1, 0x090d,0x031a, 0x0910,0x0299, 0x0914,0x034b, 0x0919,0x0008, + 0x091c,0x0033, 0x091c,0x003d, 0x0920,0x0027, 0x0924,0x0027, 0x0924,0x01fb, + 0x092a,0x01ce, 0x092a,0x01f1, 0x092d,0x031c, 0x0930,0x001f, 0x0936,0x00c5, + 0x0938,0x00c5, 0x0938,0x0381, 0x093c,0x001b, 0x0942,0x017d, 0x094a,0x0027, + 0x094e,0x0027, 0x094e,0x01fb, 0x0952,0x03b1, 0x095a,0x0029, 0x095a,0x0030, + 0x095d,0x0030, 0x0961,0x0030, 0x0966,0x02f9, 0x0966,0x0313, 0x0968,0x02eb, + 0x096d,0x0008, 0x0970,0x017b, 0x0974,0x0033, 0x0979,0x0150, 0x097d,0x009a, + 0x0982,0x0293, 0x0984,0x0293, 0x0984,0x0379, 0x098a,0x02eb, 0x098e,0x0009, + 0x0992,0x003d, 0x0996,0x003d, 0x0999,0x0062, 0x099e,0x003d, 0x09a0,0x0027, + 0x09a5,0x0144, 0x09a8,0x02b5, 0x09ae,0x008f, 0x09ae,0x009d, 0x09b2,0x004d, + 0x09b2,0x0053, 0x09b2,0x00c3, 0x09b2,0x013d, 0x09b2,0x01c5, 0x09b2,0x0271, + 0x09b4,0x0025, 0x09ba,0x0033, 0x09ba,0x0079, 0x09bc,0x0015, 0x09c2,0x013f, + 0x09c4,0x013f, 0x09c4,0x0379, 0x09ca,0x02b5, 0x09cd,0x0006, 0x09da,0x0009, + 0x09d9,0x0008, 0x09dc,0x000b, 0x09dc,0x004f, 0x09dd,0x0086, 0x09e0,0x0009, + 0x09e6,0x00a1, 0x09e8,0x0009, 0x09ed,0x0086, 0x09f2,0x001f, 0x09f2,0x002f, + 0x09f2,0x0049, 0x09f2,0x006f, 0x09f2,0x0085, 0x09f2,0x0091, 0x09f2,0x00a9, + 0x09f2,0x00d3, 0x09f2,0x00d7, 0x09f2,0x011d, 0x09f2,0x0121, 0x09f2,0x0235, + 0x09f2,0x0393, 0x09f6,0x0324, 0x09f8,0x0049, 0x09f8,0x00a9, 0x09f8,0x011d, + 0x09fe,0x001f, 0x09fe,0x0029, 0x09fe,0x0033, 0x09fe,0x003d, 0x09fe,0x0085, + 0x09fe,0x008f, 0x09fe,0x00d3, 0x0a00,0x003d, 0x0a06,0x012d, 0x0a0e,0x00b3, + 0x0a10,0x000b, 0x0a10,0x0387, 0x0a16,0x0059, 0x0a18,0x0009, 0x0a1e,0x0043, + 0x0a24,0x0085, 0x0a2a,0x0009, 0x0a2d,0x0008, 0x0a32,0x028a, 0x0a32,0x02a7, + 0x0a31,0x031c, 0x0a35,0x032e, 0x0a39,0x0006, 0x0a3a,0x0105, 0x0a3a,0x024f, + 0x0a3c,0x0299, 0x0a42,0x01ed, 0x0a46,0x0299, 0x0a48,0x01ed, 0x0a4c,0x0059, + 0x0a52,0x000b, 0x0a52,0x0387, 0x0a56,0x000b, 0x0a5e,0x0009, 0x0a60,0x003d, + 0x0a66,0x0105, 0x0a6a,0x0195, 0x0a6c,0x000b, 0x0a76,0x0053, 0x0a78,0x0009, + 0x0a7a,0x008f, 0x0a82,0x0299, 0x0a86,0x01ed, 0x0a8a,0x0027, 0x0a8e,0x004b, + 0x0a92,0x003d, 0x0a95,0x0322, 0x0a99,0x0038, 0x0a99,0x0090, 0x0a9c,0x0061, + 0x0a9c,0x00c7, 0x0a9c,0x012d, 0x0a9c,0x016f, 0x0a9c,0x017d, 0x0a9c,0x02c9, + 0x0a9c,0x0383, 0x0aa1,0x0010, 0x0aa4,0x00b3, 0x0aa8,0x002f, 0x0aac,0x0027, + 0x0ab0,0x004b, 0x0ab4,0x0043, 0x0ab9,0x0090, 0x0abd,0x0010, 0x0ac4,0x0019, + 0x0acc,0x00f5, 0x0acc,0x022b, 0x0acc,0x037b, 0x0ad2,0x008f, 0x0ad2,0x01f1, + 0x0ad6,0x0324, 0x0ad9,0x0330, 0x0ade,0x008f, 0x0ade,0x01f1, 0x0ae0,0x017b, + 0x0ae4,0x008f, 0x0ae9,0x004e, 0x0aee,0x0027, 0x0af2,0x028a, 0x0af2,0x02a7, + 0x0af1,0x031c, 0x0af6,0x0027, 0x0af9,0x031c, 0x0afe,0x00e9, 0x0afe,0x02bb, + 0x0b02,0x000b, 0x0b06,0x00f5, 0x0b06,0x022b, 0x0b06,0x037b, 0x0b0a,0x003d, + 0x0000,0x0000 +}; + diff --git a/src/sop/ft/ft.h b/src/sop/ft/ft.h index c4eab09f..cea7d935 100644 --- a/src/sop/ft/ft.h +++ b/src/sop/ft/ft.h @@ -94,6 +94,7 @@ extern void Ft_FactorStopMan(); extern Vec_Int_t * Ft_Factor( char * pSop ); extern int Ft_FactorGetNumNodes( Vec_Int_t * vForm ); extern int Ft_FactorGetNumVars( Vec_Int_t * vForm ); +extern void Ft_FactorComplement( Vec_Int_t * vForm ); /*=== ftPrint.c =====================================================*/ extern void Ft_FactorPrint( FILE * pFile, Vec_Int_t * vForm, char * pNamesIn[], char * pNameOut ); diff --git a/src/sop/ft/ftFactor.c b/src/sop/ft/ftFactor.c index 04779fe0..43f9e3ce 100644 --- a/src/sop/ft/ftFactor.c +++ b/src/sop/ft/ftFactor.c @@ -39,7 +39,6 @@ static Ft_Node_t * Ft_FactorTrivialCubeCascade( Vec_Int_t * vForm, Mvc_Cov static Ft_Node_t * Ft_FactorNodeCreate( Vec_Int_t * vForm, int Type, Ft_Node_t * pNode1, Ft_Node_t * pNode2 ); static Ft_Node_t * Ft_FactorLeafCreate( Vec_Int_t * vForm, int iLit ); static void Ft_FactorFinalize( Vec_Int_t * vForm, Ft_Node_t * pNode, int nVars ); -static void Ft_FactorComplement( Vec_Int_t * vForm ); static Vec_Int_t * Ft_FactorConst( int fConst1 ); // temporary procedures that work with the covers @@ -585,8 +584,6 @@ int Ft_FactorGetNumNodes( Vec_Int_t * vForm ) void Ft_FactorComplement( Vec_Int_t * vForm ) { Ft_Node_t * pNode; - int nVars = Ft_FactorGetNumVars( vForm ); - assert( nVars >= 0 ); pNode = Ft_NodeReadLast(vForm); pNode->fCompl ^= 1; } |