PLAOpsImplD:
CEDAR
PROGRAM
IMPORTS CommandTool, BoolEx, FileNames, FS, RefTab, SymTab, IO, PLAOps, Rope, RopeList, REFBit EXPORTS PLAOps =
BEGIN
OPEN PLAOps;
OpIndex: TYPE = BoolEx.OpIndex;
CopyPLA:
PUBLIC
PROC[old:
PLA]
RETURNS[new:
PLA] = {
new ← NewPLA[old.data, old.out, old.name];
new.time ← old.time;
new.termList ← CopyTermList[old.termList]};
plas: SymTab.Ref ← SymTab.Create[];
FlushPLACache: PUBLIC PROC = {SymTab.Erase[plas]};
ReadPLAFile:
PUBLIC
PROC
[name: IO.ROPE, log:IO.STREAM ← NIL, useCache: BOOL ← FALSE] RETURNS[pla: PLA] = {
ENABLE
FS.Error =>
IF error.group = user
THEN {
log.PutRope[error.explanation];
CONTINUE };
fullPathName: IO.ROPE;
plaName: IO.ROPE;
rope: IO.ROPE;
inName: IO.ROPE;
outName: IO.ROPE;
iForm: Format;
oForm: Format;
iFormat: Format;
oFormat: Format;
checkedOnce: BOOL ← FALSE;
length: CARDINAL ← 0;
time: BasicTime.GMT;
inStm: IO.STREAM;
IF log = NIL THEN log ← IO.noWhereStream;
IF useCache
AND SymTab.Fetch[plas, name].found
THEN {
pla ← CopyPLA[NARROW[SymTab.Fetch[plas, name].val]];
log.PutF["PLA: %g\n", IO.rope[name]];
RETURN[pla]};
fullPathName ← FileNames.FileWithSearchRules[
root: name,
defaultExtension: ".ttt",
searchRules: LIST[initialWorkingDirectory]].fullPath;
plaName ← FileNames.GetShortName[fullPathName];
plaName ← plaName.Substr[0, plaName.Index[0, "."]];
inStm ← FS.StreamOpen[fileName: fullPathName];
IF inStm=NIL THEN RETURN[NIL];
DO
ENABLE IO.EndOfStream => EXIT;
rope ← IO.GetTokenRope[inStm].token;
SELECT
TRUE
FROM
Rope.Equal[rope, "Name"] => {plaName ← IO.GetTokenRope[inStm].token};
Rope.Equal[rope, "
Date"] =>
{[ ] ← IO.GetChar[inStm]; time ← IO.GetTime[inStm]};
Rope.Equal[rope, "InType"] => {inName ←
IO.GetTokenRope[inStm].token;
IF inName.Equal["LIST"]
THEN
DO
rope ← IO.GetTokenRope[inStm].token;
inName ← inName.Cat[rope];
IF rope.Equal["]"] THEN EXIT;
inName ← inName.Cat[" "] ENDLOOP};
Rope.Equal[rope, "OutType"] => {outName ←
IO.GetTokenRope[inStm].token;
IF outName.Equal["LIST"]
THEN
DO
rope ← IO.GetTokenRope[inStm].token;
outName ← outName.Cat[rope];
IF rope.Equal["]"] THEN EXIT;
outName ← outName.Cat[" "] ENDLOOP};
Rope.Equal[rope, "
Terms"] =>
{[ ] ← IO.GetChar[inStm]; length ← IO.GetCard[inStm]; EXIT};
Rope.Equal[rope, "BitFormat"] => {
WHILE NOT Rope.Equal[IO.GetTokenRope[inStm].token,"BitTotal"] DO ENDLOOP;
[ ] ← IO.GetChar[inStm]; [ ] ← IO.GetTokenRope[inStm]};
Rope.Equal[rope, "TermList"] => {[ ] ← IO.GetChar[inStm]; EXIT};
ENDCASE => {LOOP};
ENDLOOP;
IF outName=NIL THEN {log.PutRope["\nI couldn't find 'OutType'\n"]; RETURN[NIL]};
IF inName=NIL THEN {log.PutRope["\nI couldn't find 'InType'\n"]; RETURN[NIL]};
IF length=0 THEN {log.PutRope["\nI couldn't find 'Terms'\n"]; RETURN[NIL]};
pla ← NewPLA[inName, outName, plaName];
IF pla=NIL THEN {log.PutRope["\nProblem with 'InType' or 'OutType'\n"]; RETURN[NIL]};
pla.time ← time;
DO
ENABLE IO.EndOfStream => EXIT;
OK:
PROC
RETURNS[
BOOL] = {
IF rope=NIL OR rope.Length=0 THEN RETURN[FALSE];
RETURN[SELECT rope.Fetch[0] FROM '0,'1,'-,'+,'x,'X,'. => TRUE, ENDCASE => FALSE] };
rope ← IO.GetLineRope[inStm];
IF ~OK[] THEN LOOP;
IF
NOT checkedOnce
THEN {
checkedOnce ← TRUE;
[iFormat, oFormat] ← RopeToFormat[rope];
iForm ← REFBit.Desc[pla.data].fieldForm;
oForm ← REFBit.Desc[pla.out].fieldForm;
IF iFormat.size # iForm.size THEN {SIGNAL InvalidTermRope[rope]; EXIT};
IF oFormat.size # oForm.size THEN {SIGNAL InvalidTermRope[rope]; EXIT};
FOR i: NAT IN [0..iFormat.size) DO
IF iFormat[i].bitSize#iForm[i].bitSize THEN
{SIGNAL InvalidTermRope[rope]; EXIT};
REPEAT Exit => EXIT ENDLOOP;
FOR i: NAT IN [0..oFormat.size) DO
IF oFormat[i].bitSize#oForm[i].bitSize THEN
{SIGNAL InvalidTermRope[rope]; EXIT};
};
AppendTerm[RopeToTerm[rope, pla.termList, iForm, oForm], pla.termList];
IF (pla.termList.length
MOD 100)=0
THEN log.PutRope["!"]
ELSE
IF (pla.termList.length MOD 10)=0 THEN log.PutRope["."];
ENDLOOP;
IF pla.termList.length # length
THEN
log.PutF["Number of terms changed to: %g\n", IO.int[pla.termList.length]];
log.PutF["Reading pla on file: %g\n", IO.rope[name]];
log.PutRope[PLAHeader[pla]];
[] ← SymTab.Store[plas, name, CopyPLA[pla]]};
WritePLAFile:
PUBLIC
PROC
[pla: PLA, fileName: IO.ROPE←NIL, log: IO.STREAM ← NIL] = {
out: IO.STREAM;
IF fileName=NIL THEN fileName←pla.name;
IF
NOT fileName.Substr[fileName.Length[]-4, 4].Equal[".ttt"]
THEN
fileName ← fileName.Cat[".ttt"];
out ← FS.StreamOpen[fileName, $create];
IF log=NIL THEN log ← IO.noWhereStream;
log.PutF["Writing pla on file: %g\n", IO.rope[fileName]];
log.PutRope[PLAHeader[pla]];
WritePLA[pla, out];
out.Close[]};
WritePLA:
PUBLIC
PROC[pla:
PLA,
out:
IO.
STREAM] = {
out.PutRope[PLAHeader[pla]];
out.PutRope[REFBit.FormatListing[pla.data]];
out.PutRope[REFBit.FormatListing[pla.out]];
out.PutRope["\nTermList:\n"];
ListTermList[
pla.termList,
FALSE,
FALSE,
out,
REFBit.Desc[pla.data].fieldForm,
REFBit.Desc[pla.out].fieldForm]};
PLAToExpression:
PUBLIC
PROC[pla:
PLA]
RETURNS[expression: Exp] = {
outForm: Format ← REFBit.Desc[pla.out].bitForm;
inForm: Format ← REFBit.Desc[pla.data].bitForm;
mach: LIST OF REF;
name: IO.ROPE ← IF pla.name=NIL THEN "MachineName" ELSE pla.name;
termIndex: INT ← 0;
termTab: RefTab.Ref ← RefTab.Create[];
TermID: TYPE = RECORD[name: IO.ROPE, expr: Exp];
FOR term: Term ← pla.termList.end, term.last
WHILE term#
NIL
DO
termDef: LIST OF REF;
and: LIST OF REF ← NIL;
andEx: REF ← NIL;
termID: IO.ROPE ← MakeIndexedId["Term", termIndex, pla.termList.length];
termIndex ← termIndex+1;
FOR in:
INT
DECREASING
IN [0..inForm.size)
DO
q: Qrt;
IF (q ← GetInQrt[term, inForm[in].firstBit]) = dontcare THEN LOOP;
IF inForm[in].name#
NIL
THEN
IF q = one
THEN and ← CONS[inForm[in].name, and]
ELSE and ← CONS[LIST[BoolEx.OpNm[not], inForm[in].name], and]
ELSE
IF q = zero
THEN and ← CONS[inForm[in].nameInv, and]
ELSE and ← CONS[LIST[BoolEx.OpNm[not], inForm[in].nameInv], and]
ENDLOOP;
andEx ← IF and.rest=NIL THEN and.first ELSE CONS[BoolEx.OpNm[and], and];
[]←RefTab.Store[termTab, term, NEW[TermID ← [termID, andEx]]];
termDef ← LIST[ BoolEx.OpNm[var], termID, andEx];
mach ← CONS[termDef, mach];
ENDLOOP;
FOR outIndex:
INT
DECREASING
IN [0..outForm.size)
DO
out: LIST OF REF;
or: LIST OF REF ← NIL;
orEx: REF ← NIL;
FOR term: Term ← pla.termList.end, term.last
WHILE term#
NIL
DO
IF GetOutQrt[term, outForm[outIndex].firstBit]=one
THEN {
termID: REF TermID ← NARROW[RefTab.Fetch[termTab, term].val];
or ← CONS[termID.name, or]};
ENDLOOP;
orEx ← IF or.rest=NIL THEN or.first ELSE CONS[BoolEx.OpNm[or], or];
out ← LIST[ BoolEx.OpNm[out], outForm[outIndex].name, orEx];
mach ← CONS[out, mach];
ENDLOOP;
mach ← CONS[BoolEx.OpNm[mach], CONS[name, mach]];
AddSharedInverters[mach];
expression ← mach};
MakeIndexedId:
PROC[id:
IO.
ROPE, index, size:
CARDINAL]
RETURNS[
IO.
ROPE] = {
RETURN[
SELECT size
FROM
<10 => IO.PutFR["%g%01g", IO.rope[id], IO.card[index]],
<100 => IO.PutFR["%g%02g", IO.rope[id], IO.card[index]],
<1000 => IO.PutFR["%g%03g", IO.rope[id], IO.card[index]],
<10000 => IO.PutFR["%g%04g", IO.rope[id], IO.card[index]],
ENDCASE => ERROR]};
MakeDummyRef:
PROC[id:
IO.
ROPE, size:
INT]
RETURNS[ref:
REF] = {
name: IO.ROPE ← "LIST[";
FOR i: INT IN [0..size) DO name ← name.Cat[" ", MakeIndexedId[id,i,size] ] ENDLOOP;
name ← name.Cat[" ]"];
ref ← REFBit.NEWFromName[name]};
This doesn't seem to be a very useful function.
Or plane: Making each term correspond to independent outputs can't help minimize the or plane.
And plane: Making the terms correspond to inputs just seems to increase the connections in the ouput plane.
SplitPLA:
PUBLIC
PROC[pla:
PLA]
RETURNS[andPla, orPla:
PLA] = {
termRef: REF ← MakeDummyRef["Term", pla.termList.length];
inForm: Format ← REFBit.Desc[pla.data].bitForm;
termForm: Format ← REFBit.Desc[termRef].bitForm;
outForm: Format ← REFBit.Desc[pla.out].bitForm;
defs: LIST OF REF ← NIL;
defaultName: IO.ROPE ← "MachineName";
index: INT ← 0;
tempAnd: Term;
tempOr: Term;
andPla ← NewPLA[pla.data, termRef, pla.name.Cat["AndPlane"]];
orPla ← NewPLA[termRef, pla.out, pla.name.Cat["OrPlane"]];
tempAnd ← NewTerm[andPla.termList.inBits, andPla.termList.outBits];
tempOr ← NewTerm[orPla.termList.inBits, orPla.termList.outBits];
FOR term: Term ← pla.termList.begin, term.next
WHILE term#
NIL
DO
SetOutQrt[one, tempAnd, termForm[index].firstBit]; tempAnd.in ← term.in;
ACopy[tempAnd, andPla.termList];
SetOutQrt[zero, tempAnd, termForm[index].firstBit];
index ← index+1 ENDLOOP;
FOR out:
INT
IN [0..outForm.size)
DO
index ← 0;
SetOutQrt[one, tempOr, outForm[out].firstBit];
FOR term: Term ← pla.termList.begin, term.next
WHILE term#
NIL
DO
IF GetOutQrt[term, outForm[out].firstBit]=one
THEN
SetInQrt[one, tempOr, termForm[index].firstBit];
index ← index+1 ENDLOOP;
ACopy[tempOr, orPla.termList];
FOR inWd: INT IN [0..tempOr.in.wdSize) DO tempOr.in[inWd] ← initInQrtWdc ENDLOOP;
SetOutQrt[zero, tempOr, outForm[out].firstBit];
ENDLOOP;
[ ] ← ConvertTermListToCompleteSum[andPla.termList, FALSE, FALSE];
[ ] ← FindAMinimalCover[andPla.termList, 120];
[ ] ← ConvertTermListToCompleteSum[orPla.termList, FALSE, FALSE];
[ ] ← FindAMinimalCover[orPla.termList, 120]};
Array: TYPE = REF ArrayRec;
ArrayRec:
TYPE =
RECORD[
maxGates: INT,
colNm: SeqNm,
seq: SEQUENCE size: CARDINAL OF Row];
Row: TYPE = REF RowRec;
RowRec:
TYPE =
RECORD
[expr: LIST OF IO.ROPE, marked: INT, smallest: INT, seq: SEQUENCE size: CARDINAL OF BOOL];
SeqNm: TYPE = REF SeqNmRec;
SeqNmRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF IO.ROPE];
Factor:
PUBLIC
PROC[pla:
PLA]
RETURNS[mach: Exp] = {
inForm: Format ← REFBit.Desc[pla.data].bitForm;
outForm: Format ← REFBit.Desc[pla.out].bitForm;
andXDim: INT ← 2*inForm.size;
andYDim: INT ← pla.termList.length;
orXDim: INT ← pla.termList.length;
orYDim: INT ← outForm.size;
badRow: INT ← -1;
levelSum: INT ← 0;
defs: LIST OF REF;
andNm: IO.ROPE ← "Factor";
termNm: IO.ROPE ← "Term";
orNm: IO.ROPE ← "Sum";
machName: IO.ROPE ← IF pla.name=NIL THEN "MachineName" ELSE pla.name;
index: INT ← 0;
gateOp: OpIndex ← nand; -- The last AND plane gateOp is the first OR plane gateOp.
andAry: Array ← NEW[ArrayRec[andYDim]];
orAry: Array ← NEW[ArrayRec[orYDim]];
andAry.colNm ← NEW[SeqNmRec[andXDim]];
orAry.colNm ← NEW[SeqNmRec[orXDim]];
FOR col:
INT
IN [0..andXDim)
DO
input: INT ← IF col < inForm.size THEN col ELSE col-inForm.size;
name: IO.ROPE ← inForm[input].name;
nameInv: IO.ROPE ← Rope.Cat["~", name];
andAry.colNm[col] ← IF col < inForm.size THEN name ELSE nameInv ENDLOOP;
FOR col:
INT
IN [0..orXDim)
DO
name: IO.ROPE ← MakeIndexedId[termNm, col, orXDim];
orAry.colNm[col] ← name ENDLOOP;
FOR row:
INT
IN [0..andYDim)
DO
andAry[row] ← NEW[RowRec[andXDim]];
andAry[row].expr ← NIL;
andAry[row].marked ← 0 ENDLOOP;
FOR row:
INT
IN [0..orYDim)
DO
orAry[row] ← NEW[RowRec[orXDim]];
orAry[row].expr ← NIL;
orAry[row].marked ← 0 ENDLOOP;
FOR term: Term ← pla.termList.begin, term.next
WHILE term#
NIL
DO
FOR in:
INT
IN [0..inForm.size)
DO
q: Qrt ← GetInQrt[term, inForm[in].firstBit];
andAry[index][in] ← q=one;
andAry[index][in+inForm.size] ← q=zero;
ENDLOOP;
FOR out:
INT
IN [0..outForm.size)
DO
q: Qrt ← GetOutQrt[term, outForm[out].firstBit];
orAry[out][index] ← q=one;
ENDLOOP;
index ← index + 1 ENDLOOP;
FOR initOp: OpIndex
IN [and..or]
DO
ary: Array ← IF initOp=and THEN andAry ELSE orAry;
baseNm: IO.ROPE ← IF initOp=and THEN andNm ELSE orNm;
maxExposed: INT ← 0;
IF initOp#and AND initOp#or THEN LOOP;
maxExposed ← 0;
FOR row:
INT
IN [0..ary.size)
DO
cnt: INT ← 0;
FOR col: INT IN [0..ary[row].size) DO IF ary[row][col] THEN cnt ← cnt+1 ENDLOOP;
maxExposed ← MAX[cnt, maxExposed] ENDLOOP;
ary.maxGates ← 1;
WHILE maxExposed > 4
DO maxExposed ← (maxExposed-1)/4+1; ary.maxGates ← ary.maxGates*4 ENDLOOP;
FOR level:
INT ← 0, level+1
DO
new: Array;
nextColHeads: LIST OF IO.ROPE;
newCols: INT ← 0;
gateCnt: INT ← 0;
levelSum ← levelSum + 1;
Init row params
FOR row:
INT
IN [0..ary.size)
DO
[]←GetRowParmsAndSetSmallest[ary, row] ENDLOOP;
DO
nameIf2OrMore:
IO.
ROPE ←
IO.PutFR["%g%gx%03g",
IO.rope[baseNm], IO.int[level], IO.int[gateCnt]];
def: LIST OF IO.ROPE ← AddBestGate4[ary, nameIf2OrMore];
IF def = NIL THEN EXIT;
IF def.rest=
NIL
THEN {
name: IO.ROPE ← InvertName[def.first];
IF RopeList.Memb[nextColHeads, name] THEN ERROR; -- check assumption
nextColHeads ← CONS[name, nextColHeads]}
ELSE {
list, term: LIST OF REF;
FOR def ← def, def.rest WHILE def#NIL DO list ← CONS[def.first, list] ENDLOOP;
list ← CONS[BoolEx.OpNm[gateOp], list];
term ← LIST[BoolEx.OpNm[var], nameIf2OrMore, list];
defs ← CONS[term, defs];
nextColHeads ← CONS[nameIf2OrMore, nextColHeads];
gateCnt ← gateCnt+1};
ENDLOOP;
IF GetMaxGates[ary] NOT IN (ary.maxGates/4..ary.maxGates] THEN ERROR;
IF (ary.maxGates = 1)
THEN {
FOR row:
INT
IN [0..ary.size)
DO
name:
IO.
ROPE ←
IF initOp=and
THEN orAry.colNm[row]
ELSE outForm[row].name;
def: REF ← ary[row].expr.first;
IF ary[row].expr.rest#NIL THEN ERROR;
IF (initOp=or)
AND ((levelSum
MOD 2)=1)
THEN
{inv: LIST OF REF ← LIST[BoolEx.OpNm[not], def]; def ← inv};
def ← LIST[BoolEx.OpNm[(IF initOp=and THEN var ELSE out)], name, def];
defs ← CONS[def, defs];
ENDLOOP;
EXIT};
gateOp ← IF gateOp=nand THEN nor ELSE nand; -- must be after test for loop exit
new ← NEW[ArrayRec[ary.size]];
newCols ← RopeList.Length[nextColHeads];
new.colNm ← NEW[SeqNmRec[newCols]];
new.maxGates ← ary.maxGates/4;
FOR col:
INT
IN [0..newCols)
DO
new.colNm[col] ← nextColHeads.first;
nextColHeads ← nextColHeads.rest ENDLOOP;
FOR row:
INT
IN [0..ary.size)
DO
new[row] ← NEW[RowRec[newCols]];
new[row].expr ← NIL;
new[row].marked ← 0;
FOR col:
INT
IN [0..newCols)
DO
new[row][col] ← RopeList.Memb[ary[row].expr, new.colNm[col]] ENDLOOP;
ENDLOOP;
ary ← new;
ENDLOOP;
ENDLOOP;
defs ← CONS[BoolEx.OpNm[mach], CONS[machName, defs]];
AddSharedInverters[defs];
BoolEx.Sort[defs];
mach ← defs};
AddBestGate4:
PROC[ary: Array, nameIf2OrMore:
IO.
ROPE]
RETURNS[gate: LIST OF IO.ROPE] = {
gateExpr: IO.ROPE ← NIL;
bestFanIn: INT ← 1;
fanCnts: ARRAY [1..4] OF INT ← ALL[0];
fanCols: ARRAY [1..4] OF INT ← ALL[-1];
Find fanCols and fanCnts;
FOR fanIn:
INT
IN [1..4]
DO
maxCol: INT ← -1;
maxCnt: INT ← 0;
FOR col:
INT
IN [0..ary.colNm.size)
DO
cnt: INT ← 0;
FOR fc:
INT
IN [1..fanIn)
DO
IF fanCols[fc]=col THEN GOTO Loop REPEAT Loop => LOOP ENDLOOP;
FOR row:
INT
IN [0..ary.size)
DO
IF NOT ary[row].marked=(fanIn-1) THEN LOOP;
IF ary[row][col] THEN cnt ← cnt + 1 ENDLOOP;
IF cnt > maxCnt THEN {maxCnt ← cnt; maxCol ← col} ENDLOOP;
IF maxCnt = 0 THEN IF fanIn=1 THEN RETURN[NIL] ELSE EXIT;
fanCnts[fanIn] ← maxCnt;
fanCols[fanIn] ← maxCol;
FOR row:
INT
IN [0..ary.size)
DO
IF ary[row].marked=(fanIn-1)
AND ary[row][maxCol]
THEN ary[row].marked ← ary[row].marked+1 ENDLOOP;
ENDLOOP;
Reduce fanCnts for smaller fanIns;
FOR row:
INT
IN [0..ary.size)
DO
FOR fanIn:
INT
IN [1..4)
DO
IF ary[row].marked < fanIn THEN LOOP;
IF fanCols[fanIn]#-1
AND ary[row].smallest > fanIn
THEN fanCnts[fanIn] ← fanCnts[fanIn]-1 ENDLOOP ENDLOOP;
Find best fanIn;
FOR fanIn:
INT
IN (1..4]
DO
IF fanIn*fanCnts[fanIn] >= bestFanIn*fanCnts[bestFanIn] THEN bestFanIn ← fanIn;
ENDLOOP; -- use larger gates if equal
Build Gate
FOR fanIn:
INT
IN [1..bestFanIn]
DO
gate ← CONS[ary.colNm[fanCols[fanIn]], gate] ENDLOOP;
gateExpr ←
IF bestFanIn>1
THEN nameIf2OrMore
ELSE InvertName[gate.first];
Add Gate
FOR row:
INT
IN [0..ary.size)
DO
IF bestFanIn
IN [ary[row].smallest .. ary[row].marked]
THEN {
ary[row].expr ← CONS[gateExpr, ary[row].expr];
FOR fanIn: INT IN [1..bestFanIn] DO ary[row][fanCols[fanIn]] ← FALSE ENDLOOP};
[]←GetRowParmsAndSetSmallest[ary, row];
ary[row].marked ← 0;
ENDLOOP};
AddSharedInverters:
PROC[mach:
LIST
OF
REF] = {
ConvertInvToList:
PROC[ref:
REF]
RETURNS[
REF] = {
WITH ref
SELECT
FROM
rope:
IO.
ROPE =>
IF rope.Fetch[]='~
THEN RETURN[LIST[BoolEx.OpNm[not], ConvertInvToList[rope.Substr[1]]]]
ELSE RETURN[rope];
elist:
LIST
OF
REF => {
FOR elist ← elist.rest, elist.rest
WHILE elist#
NIL
DO
elist.first ← ConvertInvToList[elist.first] ENDLOOP;
RETURN[ref]};
ENDCASE => ERROR};
RemoveDoubleInvs:
PROC[ref:
REF]
RETURNS[
REF] = {
WITH ref
SELECT
FROM
rope: IO.ROPE => RETURN[rope];
elist:
LIST
OF
REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
SELECT op
FROM
not => {
elist.rest.first ← RemoveDoubleInvs[elist.rest.first];
WITH elist.rest.first
SELECT
FROM
rp: IO.ROPE => RETURN[ref];
el:
LIST
OF
REF => {
op ← BoolEx.NmOp[NARROW[el.first]];
SELECT op
FROM
not => RETURN[el.rest.first]
ENDCASE => RETURN[ref]};
ENDCASE => ERROR};
ENDCASE => {
FOR elist ← elist.rest, elist.rest
WHILE elist#
NIL
DO
elist.first ← RemoveDoubleInvs[elist.first] ENDLOOP;
RETURN[ref]} };
ENDCASE => ERROR};
UseInvDefs:
PROC[ref:
REF]
RETURNS[
REF] = {
WITH ref
SELECT
FROM
rope: IO.ROPE => RETURN[ref];
elist:
LIST
OF
REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
SELECT op
FROM
not => {
elist.rest.first ← UseInvDefs[elist.rest.first];
WITH elist.rest.first
SELECT
FROM
rp:
IO.
ROPE => {
invNm: IO.ROPE ← IO.PutFR["NOT%g", IO.rope[rp]];
IF SymTab.Insert[invTab, rp, invNm]
THEN {
invDef: LIST OF REF ← LIST[BoolEx.OpNm[var], invNm, ref];
defs ← CONS[invDef, defs]};
RETURN[invNm]};
el: LIST OF REF => RETURN[ref]
ENDCASE => ERROR};
ENDCASE => {
FOR elist ← elist.rest, elist.rest
WHILE elist#
NIL
DO
elist.first ← UseInvDefs[elist.first] ENDLOOP;
RETURN[ref]} };
ENDCASE => ERROR};
invTab: SymTab.Ref ← SymTab.Create[];
defs: LIST OF REF ← mach.rest.rest;
FOR dfs:
LIST
OF
REF ← defs, dfs.rest
WHILE dfs#
NIL
DO
def: LIST OF REF ← NARROW[dfs.first];
def.rest.rest.first ← ConvertInvToList[def.rest.rest.first]; ENDLOOP;
FOR dfs:
LIST
OF
REF ← defs, dfs.rest
WHILE dfs#
NIL
DO
def: LIST OF REF ← NARROW[dfs.first];
def.rest.rest.first ← RemoveDoubleInvs[def.rest.rest.first]; ENDLOOP;
FOR dfs:
LIST
OF
REF ← defs, dfs.rest
WHILE dfs#
NIL
DO
def: LIST OF REF ← NARROW[dfs.first];
def.rest.rest.first ← UseInvDefs[def.rest.rest.first]; ENDLOOP;
mach.rest.rest ← defs};
InvertName:
PROC[name:
IO.
ROPE ]
RETURNS[
IO.
ROPE] =
{RETURN[IF name.Fetch[]='~ THEN name.Substr[1] ELSE Rope.Cat["~", name]]};
RopesToRefs:
PROC[ropes:
LIST
OF
IO.
ROPE]
RETURNS[refs:
LIST
OF
REF] = {
IF ropes=NIL THEN RETURN[NIL];
RETURN[CONS[ropes.first, RopesToRefs[ropes.rest]]]};
GetMaxGates:
PROC[arry: Array]
RETURNS[max:
INT ← 0] = {
FOR row:
INT
IN [0..arry.size)
DO
max ← MAX[max, RopeList.Length[arry[row].expr]] ENDLOOP};
GetRowParmsAndSetSmallest:
PROC[arry: Array, row:
INT]
RETURNS[nofGates, exposed: INT ← 0] = {
FOR col: INT IN [0..arry[row].size) DO IF arry[row][col] THEN exposed ← exposed+1 ENDLOOP;
FOR list:
LIST
OF
IO.ROPE ← arry[row].expr, list.rest
WHILE list#
NIL
DO nofGates←nofGates+1 ENDLOOP;
arry[row].smallest ← MAX[1, (exposed - (arry.maxGates-nofGates-1)*4)];
IF arry[row].smallest>4 THEN ERROR};
ShowArray:
PROC[ary: Array, log:
IO.
STREAM] = {
-- for debugging
FOR row:
INT
DECREASING
IN [0..ary.size)
DO
nofGates, exposed: INT;
[nofGates, exposed] ← GetRowParmsAndSetSmallest[ary, row];
log.PutF["%2g g:%g e:%2g s:%g m:%2g ",
IO.int[row],
IO.int[nofGates],
IO.int[exposed],
IO.int[ary[row].smallest],
IO.int[ary[row].marked]];
FOR col:
INT
IN [0..ary[row].size)
DO
log.PutChar[IF ary[row][col] THEN '1 ELSE '.] ENDLOOP;
log.PutChar[IO.CR] ENDLOOP};
CTCompressPLA:
PUBLIC
PROC[pla:
PLA, complete:
BOOL ←
FALSE]
RETURNS[new:
PLA] = {
name: IO.ROPE ← (IF pla.name.Length[]=0 THEN "Temp" ELSE pla.name);
cmdLine: IO.ROPE;
cmdLine ←
IF complete
THEN IO.PutFR["PLAOpsCompress -c %g", IO.rope[name]]
ELSE IO.PutFR["PLAOpsCompress %g", IO.rope[name]];
PLAOps.WritePLAFile[pla];
[]𡤌ommandTool.DoCommand[cmdLine, NIL];
new ← PLAOps.ReadPLAFile[name.Cat[".com.ttt"], IO.noWhereStream]};
FactorExpression:
PUBLIC
PROC[mach: Exp]
RETURNS[newMach: Exp] = {
pla: PLA ← ExpressionToPLA[mach];
newMach ← Factor[pla]};
CompressExpression:
PUBLIC
PROC[mach: Exp, complete:
BOOL ←
FALSE]
RETURNS[newMach: Exp] = {
machName: IO.ROPE ← NARROW[NARROW[mach, LIST OF REF].rest.first];
pla: PLA ← ExpressionToPLA[mach];
IF complete
THEN pla ← CTCompressPLA[pla, TRUE]
ELSE {
[] ← ConvertTermListToCompleteSum[pla.termList, FALSE, FALSE];
PLAOps.WritePLAFile[pla]};
newMach ← PLAToExpression[pla]};
ExpressionToPLA:
PUBLIC
PROC[expression: Exp]
RETURNS[pla:
PLA] = {
TwoTermIns: TYPE = RECORD[in0, in1: PLAOps.QWSeq];
inName: IO.ROPE ← "LIST[ ";
outName: IO.ROPE ← "LIST[ ";
inNames: LIST OF IO.ROPE ← NIL;
outNames: LIST OF IO.ROPE ← NIL;
outForm: Format;
inForm: Format;
temp: Term;
terms: PLAOps.TermList ← NIL;
machName: IO.ROPE;
inTab: SymTab.Ref;
outTab: SymTab.Ref;
tranStateTab: SymTab.Ref ← SymTab.Create[];
uniqueIdx: INT ← 0;
MkInNm: SymTab.EachPairAction = {IF val=key THEN inNames ← CONS[key, inNames]};
MkOutNmAndCollectTranStates: SymTab.EachPairAction = {
outNames ← CONS[key, outNames];
val ← CollectTranStates[key, val];
IF val#
NIL
THEN {
-- pretend the remaining expression had a Term Def
uniqueNm: IO.ROPE ← IO.PutFR["uniqueName%g", IO.int[uniqueIdx]];
uniqueIdx←uniqueIdx+1;
IF ~SymTab.Insert[inTab, uniqueNm, val] THEN ERROR;
AppendSymTabRpItem[tranStateTab, uniqueNm, key]}};
CollectTranStates:
PROC[out:
IO.
ROPE, e: Exp]
RETURNS[Exp] = {
WITH e
SELECT
FROM
rope:
IO.
ROPE =>
{AppendSymTabRpItem[tranStateTab, rope, out]; RETURN[NIL]};
elist:
LIST
OF
REF =>
IF BoolEx.NmOp[NARROW[elist.first]]#or
THEN RETURN[e]
ELSE {
ls: LIST OF REF ← elist;
WHILE ls.rest#
NIL
DO
ls.rest.first ← CollectTranStates[out, ls.rest.first];
IF ls.rest.first=
NIL
THEN ls.rest ← ls.rest.rest
ELSE ls ← ls.rest ENDLOOP;
RETURN[IF elist.rest=NIL THEN NIL ELSE elist]};
ENDCASE => ERROR};
AppendSymTabRpItem:
PROC[tab: SymTab.Ref, key, item:
IO.
ROPE] = {
list: LIST OF IO.ROPE ← NARROW[SymTab.Fetch[tab, key].val];
list ← CONS[item, list];
[]←SymTab.Store[tab, key, list]};
AddTranStateOutsToPla: SymTab.EachPairAction = {
Build:
PROC[e:
REF]
RETURNS[be: TermList] = {
WITH e
SELECT
FROM
in:
REF
INT => {
be ←
NEW[TermListRec ←
[inBits: pla.termList.inBits, outBits: pla.termList.outBits]];
SetInQrt[one, temp, inForm[in^].firstBit];
ACopy[temp, be];
SetInQrt[dontcare, temp, inForm[in^].firstBit]};
rope: IO.ROPE => RETURN[Build[SymTab.Fetch[inTab, rope].val]];
elist:
LIST
OF
REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
be ←
SELECT op
FROM
or, nor => OrFalse,
and, nand => AndTrue,
not => NIL,
ENDCASE => ERROR;
FOR elist ← elist.rest, elist.rest
WHILE elist#
NIL
DO
arg: TermList ← Build[elist.first];
SELECT op
FROM
or, nor => be ← Or [arg, be];
and, nand => be ← And [arg, be];
not => be ← Not [arg];
ENDCASE => ERROR ENDLOOP;
SELECT op
FROM
nor, nand => be ← Not[be] ENDCASE};
ENDCASE => ERROR};
outs: LIST OF IO.ROPE ← NARROW[val];
outIdxs: LIST OF INT ← NIL;
FOR outIdx:
INT
IN [0..outForm.size)
DO
IF RopeList.Memb[outs, outForm[outIdx].name]
THEN outIdxs ← CONS[outIdx, outIdxs] ENDLOOP;
FOR ls:
LIST
OF
INT ← outIdxs, ls.rest
WHILE ls#
NIL
DO
SetOutQrt[one, temp, outForm[ls.first].firstBit] ENDLOOP;
terms ← Build[SymTab.Fetch[inTab, key].val];
FOR term: Term ← terms.begin, term.next
WHILE term#
NIL
DO
[temp.in, term.in] ← TwoTermIns[term.in, temp.in];
ACopy[temp, pla.termList];
[temp.in, term.in] ← TwoTermIns[term.in, temp.in] ENDLOOP;
FOR ls:
LIST
OF
INT ← outIdxs, ls.rest
WHILE ls#
NIL
DO
SetOutQrt[zero, temp, outForm[ls.first].firstBit] ENDLOOP};
IF expression=NIL THEN RETURN[NIL];
expression ← BoolEx.Copy[expression];
[machName, inTab, outTab] ← BoolEx.GetExpressionTables[expression];
[]←SymTab.Pairs[inTab, MkInNm];
[]←SymTab.Pairs[outTab, MkOutNmAndCollectTranStates];
inNames ← RopeList.Sort[inNames, RopeList.IgnoreCase];
outNames ← RopeList.Sort[outNames, RopeList.IgnoreCase];
FOR inNames ← inNames, inNames.rest
WHILE inNames#
NIL
DO
inName ← inName.Cat[inNames.first, " "]
REPEAT FINISHED => inName ← inName.Cat["]"] ENDLOOP;
FOR outNames ← outNames, outNames.rest
WHILE outNames#
NIL
DO
outName ← outName.Cat[outNames.first, " "]
REPEAT FINISHED => outName ← outName.Cat["]"] ENDLOOP;
pla ← NewPLA[inName, outName, machName];
outForm ← REFBit.Desc[pla.out].bitForm;
inForm ← REFBit.Desc[pla.data].bitForm;
temp ← NewTerm[pla.termList.inBits, pla.termList.outBits];
FOR index: INT IN [0..temp.in.wdSize) DO temp.in[index] ← initInQrtWdc ENDLOOP;
FOR in:
INT
IN [0..inForm.size)
DO
IF SymTab.Store[inTab, inForm[in].name, NEW[INT ← in]] THEN ERROR ENDLOOP;
[]←SymTab.Pairs[tranStateTab, AddTranStateOutsToPla]};
PLAHeader:
PUBLIC
PROC [pla:
PLA]
RETURNS[header:
IO.
ROPE] = {
out: IO.STREAM ← IO.ROS[];
out.PutRope["\n"];
IF pla.name#NIL THEN -- notice this is just for next line
out.PutF["Name: %g\n", IO.rope[pla.name]];
out.PutF["Date: %g\n", IO.time[pla.time]];
out.PutF["InType: %g\n", IO.rope[REFBit.Desc[pla.data].typeName]];
out.PutF["OutType: %g\n", IO.rope[REFBit.Desc[pla.out].typeName]];
out.PutF["Terms: %g\n", IO.card[pla.termList.length]];
header ← IO.RopeFromROS[out]};
StripDirFromName:
PROC[ file:
IO.
ROPE]
RETURNS[
IO.
ROPE] = {
index: INT𡤀
WHILE index>=0
DO
index ← file.Find[s2: ">"];
file ← file.Substr[start: index+1] ENDLOOP;
RETURN[file]};
DefaultCMDLine:
PUBLIC
PROC[ cmdLine, default:
IO.
ROPE]
RETURNS[
IO.
ROPE] = {
DO
ENABLE IO.EndOfStream => EXIT;
default ← IO.GetTokenRope[IO.RIS[cmdLine]].token; EXIT; ENDLOOP;
RETURN[default]};
initialWorkingDirectory: IO.ROPE ← FileNames.CurrentWorkingDirectory[];
EqualExpr:
PUBLIC
PROC[e0, e1: Exp]
RETURNS[equal:
BOOL] = {
pla0: PLA ← ExpressionToPLA[e0];
pla1: PLA ← ExpressionToPLA[e1];
nm0: IO.ROPE ← IF e0=NIL THEN NIL ELSE NARROW[NARROW[e0, LIST OF REF].rest.first];
nm1: IO.ROPE ← IF e1=NIL THEN NIL ELSE NARROW[NARROW[e1, LIST OF REF].rest.first];
IF e0=e1 THEN RETURN[TRUE];
IF e0=NIL OR e1=NIL THEN RETURN[FALSE];
IF NOT Rope.Equal[nm0, nm1] THEN RETURN[FALSE];
RETURN[EqualPLA[pla0, pla1]]};
EqualPLA:
PUBLIC
PROC[pla0, pla1:
PLA]
RETURNS[equal:
BOOL] = {
inForm: Format;
outForm: Format;
IF pla0=pla1 THEN RETURN[TRUE];
IF pla0=NIL OR pla1=NIL THEN RETURN[FALSE];
inForm ← REFBit.Desc[pla0.data].bitForm;
outForm ← REFBit.Desc[pla0.out].bitForm;
pla1 ← ReconfigurePLA[pla1, pla0.data, pla0.out];
IF pla1=NIL THEN RETURN[FALSE];
FOR out:
INT
IN [0..outForm.size)
DO
t0, t1: Term;
be0: BoolExpr ← GetOutputBE[pla0, outForm[out].firstBit];
be1: BoolExpr ← GetOutputBE[pla1, outForm[out].firstBit];
[] ← ConvertTermListToCompleteSum[be0, TRUE, TRUE];
[] ← ConvertTermListToCompleteSum[be1, TRUE, TRUE];
IF be0.length # be1.length THEN RETURN[TRUE];
t0 ← be0.begin;
t1 ← be1.begin;
FOR term:
INT
IN [0..be0.length)
DO IF NOT EqualTerm[t0, t1] THEN RETURN[FALSE]; t0 ← t0.next; t1 ← t1.next
ENDLOOP ENDLOOP;
RETURN[TRUE]};
EqualTerm:
PUBLIC
PROC[term0, term1: Term]
RETURNS[equal:
BOOL] = {
IF term0=term1 THEN RETURN[TRUE];
IF term0=NIL OR term1=NIL THEN RETURN[FALSE];
IF term0.in.wdSize # term1.in.wdSize THEN RETURN[FALSE];
IF term0.out.wdSize # term1.out.wdSize THEN RETURN[FALSE];
FOR in:
INT
IN [0..term0.in.wdSize)
DO
IF term0.in[in]#term1.in[in] THEN RETURN[FALSE] ENDLOOP;
FOR out:
INT
IN [0..term0.out.wdSize)
DO
IF term0.out[out]#term1.out[out] THEN RETURN[FALSE] ENDLOOP;
RETURN[TRUE]};
END.