DIRECTORY
Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, Core, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover, Drot;

DrotImpl: CEDAR MONITOR
IMPORTS Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover
EXPORTS Drot
~ BEGIN OPEN DrotBool, DrotCover, Drot;

CellTypeFromExpressions: PUBLIC PROC [outputs: LIST OF ROPE, fanout: INT _ 4] RETURNS [Core.CellType] ~ {
tree: Dag _ BoolTreeFromExpressionList[outputs, TRUE];
RETURN[CreateCellTypeFromDag[tree, fanout]]
};

CreateCellTypeFromDag: PUBLIC PROC [tree: Dag, fanout: INT _ 4] RETURNS [Core.CellType] ~ {
ctcoll: Treeset _ MakeNewCTreeSet[];
AssembleCTree[ctcoll];
FOR ctiter: Dag _ ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO
RemoveOrs[ctiter];
ENDLOOP;
TwoifyAllTrees[ctcoll];
SimplifyDag[tree];
EstablishLevels[tree];
TwoifyTree[tree];
ReduceFanout[tree, fanout];
RemoveOrs[tree];
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP;
BufferNecessaryNodes[tree];
ReduceFanout[tree, fanout];
KillHangingNodes[tree, FALSE];
ProduceTotalCovering[tree, ctcoll];
RETURN[FromDagToCellType[tree]]
};

Parse: PUBLIC PROC [tree: Dag, be: ROPE, inpos, len: INT] RETURNS [outv: Node, outpos: INT] ~ {
onode, anode, temp: Node _ NIL;  --the current or and and node
andcount, orcount: INT _ 0;  --the number of terms encountered so far in the current or and and.
notactivep: BOOL _ FALSE;  --should we negate the current expression
WHILE inpos # len DO
SELECT Rope.Fetch[be, inpos] FROM
'( => {  --Parse a subexpression
[outv: temp, outpos: inpos] _ Parse[tree, be, inpos+1, len];
IF notactivep THEN temp _ Negate[tree, temp];
notactivep _ FALSE;
IF andcount > 0 THEN MakeLink[anode, temp];
andcount _ andcount + 1};
'  =>  --Ignore spaces
NULL;
'~ =>  --We should negate the next expression
notactivep _ NOT notactivep;
'* =>  --The past item was a term in a multiply
IF andcount = 1 THEN {
[] _ MakeNewNodeA[tree, NIL, and];
anode _ tree^.csucs;
MakeLink[anode, temp]};
'+ => {  --The past item was a term in an add
IF orcount = 0
THEN {
[] _ MakeNewNodeA[tree, NIL, or];
onode _ tree^.csucs};
orcount _ orcount + 1;
IF andcount = 1
THEN MakeLink[onode, temp]
ELSE MakeLink[onode, anode];
andcount _ 0};
') => {  --we've just finished an expression
IF orcount # 0
THEN {
outv _ onode;
IF andcount = 1
THEN MakeLink[onode, temp]
ELSE MakeLink[onode, anode]}
ELSE IF andcount = 1
THEN outv _ temp
ELSE outv _ anode;
outpos _ inpos;
RETURN}
ENDCASE => {  --there is an input variable to be processed
nomen: ROPE;
[name: nomen, outpos: inpos] _ GetName[be, inpos];
temp _ FindNodeByName[tree, nomen];
IF temp = NIL THEN {
[] _ MakeNewNodeA[tree, NIL ,prim];
temp _ tree^.csucs;
temp^.inname _ nomen};
IF notactivep THEN temp _ Negate[tree, temp];
notactivep _ FALSE;
IF andcount > 0 THEN MakeLink[anode, temp];
andcount _ andcount + 1};
inpos _ inpos + 1;
outpos _ inpos;
ENDLOOP;
};

GetName: PROC [be: ROPE, inpos: INT] RETURNS [name: ROPE, outpos: INT] ~ {
endpos: INT _ Rope.SkipTo[be, inpos, "()+*"] - 1;
inpos _ Rope.SkipOver[be, inpos, " "];
outpos _ endpos;
WHILE Rope.Fetch[be,endpos] = '  DO
endpos _ endpos - 1
ENDLOOP;
name _ Rope.Substr[be, inpos, endpos - inpos + 1]
};

AugmentBoolTreeBySingleExpression: PUBLIC PROC [tree: Dag, output: ROPE] ~ {
len: INT _ Rope.Length[output];
be: ROPE;
v1: Node;
asspos: INT _ Rope.Find[output, "=", 0];
internal: BOOL _ asspos > -1;
asspos _ MAX[asspos, Rope.Find[output, "_", 0]];
be _ Rope.Substr[output, asspos + 1, len - asspos - 1];
IF InputOKp[be]
THEN {
[outv: v1] _ Parse[tree, Rope.Cat["(", be, ")"], 1, Rope.Length[be]+2];
IF asspos > -1 THEN IF internal
THEN v1^.varname _ Rope.Substr[output,0,asspos -1]
ELSE v1^.outname _ CONS[Rope.Substr[output,0,asspos -1], v1^.outname];
IF NOT internal THEN v1^.output _ TRUE}
ELSE ERROR
};

AddInputToCover: PUBLIC PROC [be1: ROPE, ctcoll: Treeset] ~ {
iter: Node;
len: INT _ Rope.Length[be1];
asspos: INT _ Rope.Find[be1, "_", 0];
be : ROPE _ Rope.Substr[be1, asspos + 1, len - asspos - 1];
MakeNewCTree[ctcoll, NIL];
IF InputOKp[be]
THEN {
[outv: iter] _ Parse[ctcoll^.top, Rope.Cat["(",be,")"], 1, Rope.Length[be] + 2];
IF asspos > -1 THEN iter^.outname _ CONS[Rope.Substr[be1,0,asspos - 1], iter^.outname];
iter^.output _ TRUE}
ELSE ERROR
};

AssembleCTree: PROC [ctcoll: Treeset] ~ {
AddInputToCover["X _ ~I", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "inv"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A * I-B)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand2"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ I-A * I-B", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and2"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A + I-B)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor2"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ I-A + I-B", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or2"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A * I-B * I-C)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand3"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ (I-A * I-B * I-C)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and3"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A + I-B + I-C)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor3"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ (I-A + I-B + I-C)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or3"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A * I-B * I-C * I-D)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand4"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ ~(I-A + I-B + I-C + I-D)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor4"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;

AddInputToCover["X _ (I-A * I-B + ~I-A * ~I-B)", ctcoll];
ctcoll^.top^.cell _ NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "xor2"].val];
ctcoll^.top^.val _ NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
};

InputOKp: PROC [be1: ROPE, out: IO.STREAM] RETURNS [test: BOOL] ~ {
len: INT _ Rope.Length[be1];
asspos: INT _ Rope.Find[be1, "_", 0];
be : ROPE _ Rope.Substr[be1, asspos + 1, len - asspos - 1];
IF NOT ParensMatch[be]
THEN {IO.PutF[out, "Parens not OK\n"]; RETURN[FALSE]}
ELSE {IO.PutF[out, "Parens OK\n"]; IF AndOrOK[be]
THEN {IO.PutF[out, "Chars OK"]; RETURN[TRUE]}
ELSE {IO.PutF[out, "Chars not OK"]; RETURN[FALSE]}}
};

ParensMatch: PROC [be: ROPE] RETURNS [test: BOOL] ~ {
count: INT _ 0;
len: INT _ Rope.Length[be];
FOR pos: INT _ Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be,pos+1,"()"] DO
IF pos = len
THEN RETURN[count = 0]
ELSE IF Rope.Fetch[be,pos] = '(
THEN count _ count + 1
ELSE {
count _ count - 1;
IF count = -1 THEN RETURN[FALSE]};
ENDLOOP;
};

AndOrOK: PROC [be: ROPE] RETURNS [test: BOOL] ~ {
len: INT _ Rope.Length[be];
FOR pos: INT _ Rope.SkipTo[be, 0, "*+~"], Rope.SkipTo[be, pos+1, "*+~"] DO
IF pos = len
THEN EXIT
ELSE
IF Rope.Fetch[be,pos] # '~
THEN {
jobbg : INT _ Rope.SkipOver[be, pos+1, "*+ )"];
IF jobbg = len
THEN RETURN[FALSE]
ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE];
FOR iter: INT _ pos - 1, iter - 1 DO
IF iter = -1
THEN RETURN[FALSE]
ELSE  SELECT Rope.Fetch[be,iter] FROM
'*,'+,'(,'~ => RETURN[FALSE];
'  => NULL;
ENDCASE => EXIT;
ENDLOOP}
ELSE {
jobbg : INT _ Rope.SkipOver[be, pos+1, "*+ )"];
IF jobbg = len
THEN RETURN[FALSE]
ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE]}
ENDLOOP;
FOR pos: INT _ Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be, pos+1, "()"] DO
IF pos = len
THEN RETURN[TRUE]
ELSE IF Rope.Fetch[be,pos] = '(
THEN {
jobbg: INT _ Rope.SkipTo[be, pos+1, ")"];
IF Rope.SkipOver[be,pos+1,") "] > jobbg THEN RETURN[FALSE];
FOR iter: INT _ pos - 1, iter - 1 DO
IF iter = -1
THEN EXIT
ELSE SELECT Rope.Fetch[be,iter] FROM
'*,'+,'~,'( => EXIT;
'  => NULL;
ENDCASE => RETURN[FALSE];
ENDLOOP}
ELSE {
jobbb: INT _ Rope.SkipOver[be, pos+1, "+* )"];
jobbg : INT _ Rope.SkipTo[be, pos+1, "*+)"];
IF jobbb < jobbg THEN RETURN[FALSE]};
ENDLOOP;
};

Commander.Register[key: "Gen", proc: MakeGenerator, doc: "Standard cells from logic equations"];
MakeGenerator: Commander.CommandProc = TRUSTED {Process.Detach[FORK Gen]};

Gen: PUBLIC PROC ~ {
tree: Dag _ MakeNewBoolTree[];
ctcoll: Treeset _ MakeNewCTreeSet[];
gettinginput : BOOL _ TRUE;
in, out: IO.STREAM;
be: ROPE;
dummy : INT _ 0;
[] _ MakeNewNodeB[tree, NIL, prim, "Gnd"];
[] _ MakeNewNodeB[tree, NIL, prim,"Vdd"];
[in: in, out: out] _ ViewerIO.CreateViewerStreams["Logic Generator"];
AssembleCTree[ctcoll];
IO.PutF[out, "Enter Boolean expressions, <CR> to terminate sequence\n"];
WHILE gettinginput DO
IO.PutF[out, ">  "];
ViewerTools.SetSelection[ViewerIO.GetViewerFromStream[in]];
be _ IO.GetLineRope[in];
IF Rope.IsEmpty[be]
THEN EXIT
ELSE IF Rope.Fetch[be,0] = ':
THEN {
be _ Rope.Substr[be,1,Rope.Length[be] - 1];
IF InputOKp[be, out]
THEN AddInputToCover[be,ctcoll]
ELSE IO.PutF[out, "   Problem with cover expression.  Please enter anew.\n"]}
ELSE IF InputOKp[be,out]
THEN AugmentBoolTreeBySingleExpression[tree, be]
ELSE IO.PutF[out, "     Problem with input expression.  Please enter anew.\n"];
dummy _ dummy + 1;
ENDLOOP;
FromLogicToCell[tree, ctcoll, out];
dummy _ dummy + 1;
};

FromLogicToCell: PROC [tree: Dag, ctcoll: Treeset, out: IO.STREAM] ~ {
foo: Core.CellType;
FOR ctiter: Dag _ ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO
RemoveOrs[ctiter];
ENDLOOP;
IO.PutF[out, "Done with first pass\n"];
TwoifyAllTrees[ctcoll];
IO.PutF[out, "Done with second pass\n"];
SimplifyDag[tree];
IO.PutF[out, "Done with third pass\n"];
EstablishLevels[tree];
IO.PutF[out, "Done with fourth pass\n"];
TwoifyTree[tree];
IO.PutF[out, "Done with fifth pass\n"];
ReduceFanout[tree, 4];
IO.PutF[out, "Done with sixth pass\n"];
RemoveOrs[tree];
IO.PutF[out, "Done with seventh pass\n"];
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP;
IO.PutF[out, "Done with pass seven and a half\n"];
BufferNecessaryNodes[tree];
ReduceFanout[tree, 4];
KillHangingNodes[tree, FALSE];
IO.PutF[out, "Done with pass seven and three quarters\n"];
ProduceTotalCovering[tree, ctcoll];
IO.PutF[out, "Done with eighth pass\n"];
foo _ FromDagToCellType[tree];
IO.PutF[out, "Done\n"];
};

Disp: PUBLIC PROC [tree: Dag, out: IO.STREAM] ~ {
iter: Node _ tree^.csucs;
WHILE iter # NIL DO
kiter: Kidptr _ iter^.kidlist;
piter: Kidptr _ iter^.parlist;
IO.PutF[out, "\n%3g: ", IO.int[iter^.number]];
SELECT iter^.type FROM
and => IO.PutF[out," and"];
nand => IO.PutF[out,"nand"];
or => IO.PutF[out,"  or"];
nor => IO.PutF[out," nor"];
not => IO.PutF[out," not"];
buf => IO.PutF[out," buf"];
ENDCASE => IO.PutF[out,"prim"];
IO.PutF[out, Rope.Concat["   ",Rope.Concat[iter^.inname, Rope.Concat[" ", iter^.varname]]]];
IF iter^.output THEN IO.PutF[out, Rope.Concat["*^*",iter^.outname.first]];
IF iter^.sim THEN IO.PutF[out,"   Sim  "];
IO.PutF[out, "  %3g\n", IO.int[iter^.level]];
IO.PutF[out, "      Kids: "];
WHILE kiter # NIL DO
IO.PutF[out, "%3g", IO.int[kiter^.child^.number]];
IF kiter^.next # NIL
THEN IO.PutF[out, ","]
ELSE IO.PutF[out, "\n"];
kiter _ kiter^.next;
ENDLOOP;
IO.PutF[out, "      Pars: "];
WHILE piter # NIL DO
IO.PutF[out, "%3g", IO.int[piter^.child^.number]];
IF piter^.next # NIL
THEN IO.PutF[out, ","];
piter _ piter^.next;
ENDLOOP;
iter _ iter^.next;
ENDLOOP;
IO.PutF[out,"\n"]
};
SimplifyDag: PROC [tree: Dag] ~ {
iter : Node;
firstPass : BOOL _ TRUE;
WHILE firstPass OR AbsorbIdenticalNodes[tree] DO
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] OR ProcessGndAndVdd[tree] OR ReduceExpressions[tree] DO ENDLOOP;
firstPass _ FALSE;
ENDLOOP;
OrderNodesByPrims[tree];
iter _ tree^.csucs^.prev;
WHILE iter # tree^.csucs DO
temp : Node _ iter^.next;
RAdjustVertex[tree, iter];
IF temp = NIL
THEN IF iter = tree^.csucs^.prev
THEN iter _ iter^.prev
ELSE iter _ tree^.csucs^.prev
ELSE IF temp^.prev = iter
THEN iter _ iter^.prev
ELSE iter _ temp^.prev;
ENDLOOP;
RAdjustVertex[tree, iter];
};

AbsorbIdenticalNodes: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ {
OrderNodesByOrphans[tree];
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
subtype : Vtype;
IF iter^.type = and OR iter^.type = nand THEN subtype _ and
ELSE IF iter^.type = or OR iter^.type = nor THEN subtype _ or
ELSE subtype _ iter^.type;
FOR kiditer: Kidptr _ iter^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
IF (kiditer^.child^.type = subtype OR iter^.type = not OR iter^.type = buf) AND kiditer^.child^.parnum = 1 AND NOT kiditer^.child^.output THEN {
FOR grandchilditer: Kidptr _ kiditer^.child^.kidlist, grandchilditer^.next UNTIL grandchilditer = NIL DO
MakeLinkE[iter, grandchilditer^.child];
ENDLOOP;
IF iter^.type = not
THEN iter^.type _ NegNodeType[kiditer^.child^.type]
ELSE IF iter^.type = buf THEN iter^.type _ kiditer^.child^.type;
RemoveNode[tree, kiditer^.child];
modified _ TRUE};
ENDLOOP;
ENDLOOP;
};

RemoveDuplicateNodes: PUBLIC PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ {
PrimitivesToEnd[tree];
IF tree^.csucs^.type # prim THEN {
front: Node _ tree^.csucs^.prev;
rear : Node _ front;
ClearScratch[tree];
WHILE front^.type = prim DO
front _ front^.prev;
ENDLOOP;
WHILE front # NIL DO
szuloiter : Kidptr _ rear^.parlist;
middle: Node _ front^.next;
WHILE szuloiter # NIL DO
KidptrToEnd[szuloiter^.parlink, szuloiter^.child];
IF szuloiter^.child^.scratch = szuloiter^.child^.kidnum - 1
THEN {
nodeiter: Node _ middle^.prev;
WHILE nodeiter # front DO
IF nodeiter^.type = szuloiter^.child^.type AND ForwardSimilar[nodeiter, szuloiter^.child]
THEN {
MergeNodes[nodeiter, szuloiter^.child, tree];
modified _ TRUE;
EXIT}
ELSE nodeiter _ nodeiter^.prev;
ENDLOOP;
front _ PlaceAfter[tree, front, szuloiter^.child]}
ELSE szuloiter^.child^.scratch _ szuloiter^.child^.scratch + 1;
szuloiter _ szuloiter^.next;
ENDLOOP;
rear _ rear^.prev;
ENDLOOP}
};

MergeNodes: PROC [bol, be: Node, tree: Dag] ~ {
be^.output _ be^.output OR bol^.output;
be^.outname _ MergeListOfRopes[bol^.outname, be^.outname];
be^.inname _ Rope.Concat[be^.inname, bol^.inname];
be^.varname _ Rope.Concat[be^.varname, bol^.varname];
FOR iter: Kidptr _ bol^.parlist, iter^.next UNTIL iter = NIL DO
MakeLink[iter^.child, be];
ENDLOOP;
RemoveNode[tree, bol]
};

RemoveAllIdenticalLinks: PROC [tree: Dag] RETURNS [modified: BOOL _ FALSE] ~ {
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
modified _ modified OR RemoveIdenticalLinks[iter]
ENDLOOP;
};

RemoveIdenticalLinks: PROC [vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ {
FOR kiditer: Kidptr _ vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
kiditer^.child^.scratch _ 0;
ENDLOOP;
FOR kiditer: Kidptr _ vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
IF kiditer^.child^.scratch = 1
THEN {
[] _ KillCLink[kiditer];
modified _ TRUE}
ELSE kiditer^.child^.scratch _ 1;
ENDLOOP;
FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
pariter^.child^.scratch _ 0;
ENDLOOP;
FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
IF pariter^.child^.scratch = 1
THEN {
[] _ KillPLink[pariter];
modified _ TRUE}
ELSE pariter^.child^.scratch _ 1;
ENDLOOP;
};

ProcessGndAndVdd: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ {
gnd: Node _ FindInputByName[tree, "Gnd"];
vdd: Node _ FindInputByName[tree, "Vdd"];
IF gnd # NIL OR vdd # NIL THEN {
IF gnd = NIL THEN [] _ MakeNewNodeB[tree, NIL, prim, "Gnd"]
ELSE IF vdd = NIL THEN [] _ MakeNewNodeB[tree, NIL, prim, "Vdd"];
IF gnd^.parlist # NIL OR vdd^.parlist # NIL THEN mdoified _ TRUE;
WHILE gnd^.parlist # NIL OR vdd^.parlist # NIL DO
IF gnd^.parlist # NIL THEN ProcessGnd[gnd, vdd, tree];
IF vdd^.parlist # NIL THEN ProcessVdd[gnd, vdd, tree];
ENDLOOP}
};

ProcessGnd: PROC [gnd, vdd: Node, tree: Dag] ~ {
par : Node _ gnd^.parlist^.child;
SELECT par^.type FROM
or, nor => {
[] _ KillPLink[gnd^.parlist];
RAdjustVertex[tree, par]};
and, buf => {
FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, gnd];
ENDLOOP;
gnd^.output _ gnd^.output OR par^.output;
gnd^.outname _ MergeListOfRopes[gnd^.outname, par^.outname];
RemoveNode[tree, par]};
nand, not => {
FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, vdd];
ENDLOOP;
vdd^.output _ vdd^.output OR par^.output;
vdd^.outname _ MergeListOfRopes[vdd^.outname, par^.outname];
RemoveNode[tree, par]};
ENDCASE => tree^.csucs^.prev^.next^.prev _ NIL; --This will cause an error.  Shouldn't be reached.
};

ProcessVdd: PROC [gnd, vdd: Node, tree: Dag] ~ {
par: Node _ vdd^.parlist^.child;
SELECT par^.type FROM
and, nand => {
[] _ KillPLink[gnd^.parlist];
RAdjustVertex[tree, par]};
nor, not => {
FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, gnd];
ENDLOOP;
gnd^.output _ gnd^.output OR par^.output;
gnd^.outname _ MergeListOfRopes[gnd^.outname, par^.outname];
RemoveNode[tree, par]};
or, buf => {
FOR pariter: Kidptr _ par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, vdd];
ENDLOOP;
vdd^.output _ vdd^.output OR par^.output;
vdd^.outname _ MergeListOfRopes[vdd^.outname, par^.outname];
RemoveNode[tree, par]};
ENDCASE => tree^.csucs^.prev^.next^.prev _ NIL; --This will cause an error.  Shouldn't be reached.
};

ReduceExpressions: PROC [tree: Dag] RETURNS[modified: BOOL _ FALSE] ~ {
OrderNodesByPrims[tree];
FOR iter: Node _ tree^.csucs^.prev, iter^.prev UNTIL iter = tree^.csucs DO
modified _ modified OR ReduceExpression1[tree, iter];
modified _ modified OR ReduceExpression2[tree, iter];
ENDLOOP;
modified _ modified OR ReduceExpression1[tree, tree^.csucs];
modified _ modified OR ReduceExpression2[tree, tree^.csucs];
};

ReduceExpression1: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ {
subtype: Vtype _ and;
IF vertex^.kidnum > 1 THEN {
iter1: Kidptr _ vertex^.kidlist;
IF vertex^.type = and OR vertex^.type = nand THEN subtype _ or;
WHILE iter1 # NIL DO
pair : Node _ NegativeOf[iter1^.child];
IF pair = NIL
THEN iter1 _ iter1^.next
ELSE {
iter2: Kidptr _ vertex^.kidlist;
IF ConnectionBetween[vertex, pair] # NIL
THEN {  This is the a*~a clause
IF subtype = or
THEN [] _ MakeLink[vertex, FindInputByName[tree, "Gnd"]]
ELSE [] _ MakeLink[vertex, FindInputByName[tree, "Vdd"]];
[] _ ProcessGndAndVdd[tree];
RETURN[TRUE]};
WHILE iter2 # NIL DO
IF iter2^.child^.type # subtype OR iter2 = iter1 OR ConnectionBetween[iter2^.child, pair] = NIL
THEN iter2 _ iter2^.next
ELSE IF iter2^.child^.kidnum = 2
THEN {
IF iter2^.child^.kidlist^.child = pair
THEN [] _ MakeLinkE[vertex, iter2^.child^.kidlist^.next^.child]
ELSE [] _ MakeLinkE[vertex, iter2^.child^.kidlist^.child];
iter2 _ iter2^.next;
modified _ TRUE;
IF iter2^.prev^.child^.parnum = 1
THEN RemoveNode[tree, iter2^.prev^.child]
ELSE [] _ KillCLink[iter2^.prev]}
ELSE IF iter2^.child^.parnum = 1
THEN {
temp: Kidptr _ iter2^.next;
[] _ KillCLink[ConnectionBetween[iter2^.child, pair]];
[] _ PlaceKidptrAfter[iter1, iter2, vertex];
modified _ TRUE;
iter2 _ temp}
ELSE iter2 _ iter2^.next;
ENDLOOP;
iter1 _ iter1^.next};
ENDLOOP}
};

ReduceExpression2: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL _ FALSE] ~ {
subtype : Vtype _ and;
IF vertex^.kidnum > 1 THEN {
front: Kidptr;
OrderKidptrsBySize[vertex];
front _ vertex^.kidlist;
IF vertex^.type = and OR vertex^.type = nand THEN subtype _ or;
WHILE front # NIL DO
nextfront: Kidptr _ front^.next;
IF front^.child^.type = subtype THEN {
rear: Kidptr _ front^.next;
WHILE rear # NIL DO
IF rear^.child^.type # subtype
THEN rear _ rear^.next
ELSE {
conFromFrontToRear: Kidptr _ ConnectionBetween[front^.child, rear^.child];
conFromRearToFront: Kidptr _ ConnectionBetween[rear^.child, front^.child];
IF conFromRearToFront # NIL
THEN IF rear^.child^.parnum = 1
THEN
{rear _ rear^.next;
modified _ TRUE;
IF rear = NIL
THEN RemoveNode[tree, vertex^.kidlist^.prev^.child]
ELSE RemoveNode[tree, rear^.prev^.child]}
ELSE rear _ KillCLink[rear]
ELSE IF conFromFrontToRear # NIL
THEN {
nextfront _ front^.next;
IF front^.child^.parnum = 1
THEN RemoveNode[tree, front^.child]
ELSE [] _ KillCLink[front];
modified _ TRUE;
rear _ NIL}
ELSE IF rear^.child^.kidnum # front^.child^.kidnum
THEN IF IntersectionSize[front^.child, rear^.child] = rear^.child^.kidnum
THEN {  --second case
nextfront _ front^.next;
IF front^.child^.parnum = 1
THEN RemoveNode[tree, front^.child]
ELSE [] _ KillCLink[front];
modified _ TRUE;
rear _ NIL}
ELSE rear _ rear^.next
ELSE {  --third case
temp: Kidptr;
exp, negexp: Kidptr;
[son1 : exp, son2: negexp] _ CheckTheseTwo[front^.child, rear^.child];
IF exp = NIL
THEN rear _ rear^.next
ELSE {
IF rear^.child^.parnum = 1
THEN {
temp _ rear;
[] _ KillCLink[negexp];
Percolate[temp, vertex];
nextfront _ KillCLink[front];
modified _ TRUE;
IF exp^.parlink^.child^.parnum = 0 AND NOT exp^.parlink^.child^.output THEN RemoveNode[tree, exp^.parlink^.child]}
ELSE IF front^.child^.parnum = 1
THEN {
temp _ front;
[] _ KillCLink[exp];
[] _ KillCLink[rear];
modified _ TRUE;
nextfront _ front^.next;
Percolate[temp, vertex]}
ELSE {
MakeLink[vertex, MakeNewNodeA[tree, vertex, subtype]];
temp _ vertex^.next^.parlist^.parlink;
FOR iter: Kidptr _ front^.child^.kidlist, iter^.next UNTIL iter = NIL DO
IF iter # exp THEN MakeLink[temp^.child, iter^.child];
ENDLOOP;
Percolate[temp, vertex];
[] _ KillCLink[rear];
nextfront _ KillCLink[front]};
rear _ NIL}}}
ENDLOOP};
front _ nextfront;
ENDLOOP};
};

CheckTheseTwo: PROC [sib1, sib2: Node] RETURNS [son1: Kidptr _ NIL, son2: Kidptr _ NIL] ~ {
FOR iter: Kidptr _ sib1^.kidlist, iter^.next UNTIL iter = NIL DO
pair: Node _ NegativeOf[iter^.child];
IF pair # NIL THEN {
dummy: BOOL _ TRUE;
sonlink: Kidptr _ ConnectionBetween[sib2, pair];
IF sonlink # NIL THEN {
FOR iter1: Kidptr _ sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO
iter1^.child^.scratch _ 0;
ENDLOOP;
FOR iter2: Kidptr _ sib2^.kidlist, iter2^.next UNTIL iter2 = NIL DO
iter2^.child^.scratch _ 1;
ENDLOOP;
FOR iter1: Kidptr _ sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO
IF iter1^.child^.scratch # 1 AND iter1^.child # iter^.child THEN dummy _ FALSE;
ENDLOOP;
IF dummy THEN {
son1 _ iter;
son2 _ sonlink;
RETURN}}}
ENDLOOP;
};

OrderKidptrsBySize: PROC [vertex: Node] ~ {
iter: Kidptr _ vertex^.kidlist;
temp: Kidptr;
IF iter # NIL
THEN iter _ iter^.prev
ELSE RETURN;
WHILE iter # vertex^.kidlist DO
temp _ iter^.prev;
Percolate[iter, vertex];
iter _ temp;
ENDLOOP;
Percolate[iter, vertex]
};

Percolate: PROC [kid: Kidptr, vertex: Node] ~ {
IF kid^.next # NIL AND kid^.next^.child^.kidnum > kid^.child^.kidnum THEN {
FOR iter: Kidptr _ kid^.next, iter^.next UNTIL iter = NIL DO
IF kid^.child^.kidnum > iter^.child^.kidnum THEN {
[] _ PlaceKidptrAfter[iter^.prev, kid, vertex];
RETURN}
ENDLOOP;
[] _ PlaceKidptrAfter[vertex^.kidlist^.prev, kid, vertex]}
};

PlaceKidptrAfter: PROC [before, after: Kidptr, tree: Node] RETURNS[Kidptr] ~ {
IF before = NIL
THEN PlaceKidptrAtBeg[after, tree]
ELSE IF before # after AND (before^.next # after) THEN
IF before^.next = NIL
THEN {
before^.next _ after;
IF after = tree^.kidlist
THEN {
tree^.kidlist _ after^.next;
after^.next _ NIL}
ELSE {
after^.prev^.next _ after^.next;
after^.next^.prev _ after^.prev;
tree^.kidlist^.prev _ after;
after^.next _ NIL;
after^.prev _ before}}
ELSE {
IF after^.next = NIL
THEN tree^.kidlist^.prev _ after^.prev
ELSE after^.next^.prev _ after^.prev;
IF after = tree^.kidlist
THEN tree^.kidlist _ after^.next
ELSE after^.prev^.next _ after^.next;
after^.prev _ before;
after^.next _ before^.next;
before^.next^.prev _ after;
before^.next _ after};
IF after = tree^.kidlist
THEN RETURN[NIL]
ELSE RETURN[after^.prev];
};

PlaceKidptrAtBeg: PROC [vertex: Kidptr, tree: Node] ~ {
IF vertex # tree^.kidlist THEN {
IF vertex^.next = NIL 
THEN {
vertex^.prev^.next _ NIL
}
ELSE {
vertex^.prev^.next _ vertex^.next;
vertex^.next^.prev _ vertex^.prev;
vertex^.prev _ tree^.kidlist^.prev;
tree^.kidlist^.prev _ vertex
};
vertex^.next _ tree^.kidlist;
tree^.kidlist _ vertex}
};

RAdjustVertex: PROC [tree: Dag, vertex: Node] ~ {
IF vertex^.type # prim THEN
IF vertex^.kidnum = 0
THEN {
IF vertex^.output THEN vertex^.kidlist^.next _ NIL;--Error.  There is a floating output
FOR iter: Kidptr _ vertex^.parlist, iter^.next UNTIL iter = NIL DO
par : Node _ iter^.child;
[] _ KillPLink[iter];
RAdjustVertex[tree, par];
ENDLOOP}
ELSE IF vertex^.kidnum = 1 THEN SELECT vertex^.type FROM
nand, nor => vertex^.type _ not;
and, or => {
son: Node _ vertex^.kidlist^.child;
son^.output _ son^.output OR vertex^.output;
son^.outname _ MergeListOfRopes[son^.outname, vertex^.outname];
FOR pariter: Kidptr _ vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLink[pariter^.child, son];
ENDLOOP;
RemoveNode[tree, vertex]};
ENDCASE => NULL;
};

ReduceFanout: PUBLIC PROC [tree: Dag, fout: INT] ~ {
OrderNodesByOrphans[tree];
ClearScratch[tree];
FOR front: Node _  tree^.csucs, front^.next UNTIL front = NIL DO
IF front^.type # prim THEN
WHILE front^.parnum > fout DO
[] _ MakeNewNodeB[tree, front, front^.type];
FOR kiditer: Kidptr _ front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
MakeLink[front^.prev, kiditer^.child];
ENDLOOP;
IF fout < 2*front^.parnum
THEN FOR i: INT IN [1..front^.parnum/2] DO
MakeLink[front^.parlist^.child,front^.prev];
[] _ KillPLink[front^.parlist];
ENDLOOP
ELSE FOR i: INT IN [1..fout] DO
MakeLink[front^.parlist^.child,front^.prev];
[] _ KillPLink[front^.parlist];
ENDLOOP;
ENDLOOP;
ENDLOOP
};

BufferNecessaryNodes: PROC [tree: Dag] ~ {
OrderNodesByOrphans[tree];
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.type = prim
THEN IF iter^.output
THEN {
IF Member[iter^.inname, iter^.outname]
THEN iter^.outname _ RemoveNameFromList[iter^.inname, iter^.outname]
ELSE iter^.output _ FALSE;
SELECT iter^.inname FROM
"Gnd" => IF iter^.outname # NIL THEN {
vdd: Node _ FindInputByName[tree, "Vdd"];
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], vdd];
iter^.outname _ iter^.outname.rest;
ENDLOOP;
"Vdd" => IF iter^.outname # NIL THEN {
gnd: Node _ FindInputByName[tree, "Gnd"];
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], gnd];
iter^.outname _ iter^.outname.rest;
ENDLOOP;
ENDCASE =>
IF iter^.outname # NIL THEN {
notAbove: Node _ NotAbove[iter^.parlist];
IF notAbove = NIL THEN {
notAbove _ MakeNewNodeB[tree, iter, not];
MakeLink[notAbove, iter]};
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove];
notAbove^.prev^.output _ TRUE;
notAbove^.prev^.outname _ LIST[iter^.outname.first];
iter^.outname _ iter^.outname.rest;
ENDLOOP};
IF iter^.output THEN iter^.outname _ LIST[iter^.inname];}
ELSE NULL
ELSE IF iter^.output THEN
IF iter^.outname # NIL AND iter^.outname.rest # NIL THEN {
notAbove: Node _ NotAbove[iter^.parlist];
IF notAbove = NIL THEN {
notAbove _ MakeNewNodeB[tree, iter, not];
MakeLink[notAbove, iter]};
WHILE iter^.outname.rest # NIL DO
MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove];
notAbove^.prev^.output _ TRUE;
notAbove^.prev^.outname _ LIST[iter^.outname.first];
iter^.outname _ iter^.outname.rest;
ENDLOOP};
ENDLOOP;
};

RemoveNameFromList: PROC [name: ROPE, list: LIST OF ROPE] RETURNS [LIST OF ROPE] ~ {
IF list = NIL THEN RETURN[NIL]
ELSE IF Rope.Equal[list.first,name] THEN RETURN[RemoveNameFromList[name, list.rest]]
ELSE RETURN[CONS[list.first, RemoveNameFromList[name, list.rest]]]
};

Member: PROC [element: ROPE, list: LIST OF ROPE] RETURNS [BOOL] ~ {
IF list = NIL THEN RETURN[FALSE]
ELSE IF Rope.Equal[element,list.first] THEN RETURN[TRUE]
ELSE RETURN[Member[element, list.rest]]
};

RemoveOrs: PROC [tree: Dag] ~ {
OrderNodesByOrphans[tree];
FOR front: Node _ tree^.csucs, front^.next UNTIL front = NIL DO
notAbove : Node;
IF front^.type = or OR front^.type = nor THEN {
FOR kiditer: Kidptr _ front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
NegateConnection[tree, kiditer];
ENDLOOP;
IF front^.type = or
THEN front^.type _ nand
ELSE front^.type _ and};
IF front^.type = and THEN {
notAbove _ NotAbove[front^.parlist];
IF notAbove = NIL
THEN {
Splitnode[tree, front];
front^.type _ nand;
front^.prev^.type _ not}
ELSE IF front^.parnum =1 AND NOT front^.output
THEN {
FOR iter: Kidptr _ notAbove^.parlist, iter^.next UNTIL iter = NIL DO
MakeLink[iter^.child, front];
ENDLOOP;
front^.output _ notAbove^.output;
front^.varname _ notAbove^.varname;
front^.inname _ notAbove^.inname;
front^.outname _ notAbove^.outname;
RemoveNode[tree, notAbove];
front^.type _ nand}
ELSE SwitchWithNot[notAbove]};
IF front^.type = not THEN {
notAbove _ NotAbove[front^.parlist];
IF notAbove # NIL THEN {
FOR pariter: Kidptr _ notAbove^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLink[pariter^.child, front^.kidlist^.child];
ENDLOOP;
front^.kidlist^.child^.output _ front^.kidlist^.child^.output OR notAbove^.output;
front^.kidlist^.child^.inname _ Rope.Concat[front^.kidlist^.child^.inname, notAbove^.inname];
front^.kidlist^.child^.outname _ MergeListOfRopes[notAbove^.outname, front^.kidlist^.child^.outname];
RemoveNode[tree, notAbove]}};
ENDLOOP;
};

Splitnode: PROC [tree: Dag, vertex: Node, type: Vtype _ not] ~ {
temp: Node _ NEW[Noderec _ [next: vertex, prev: vertex^.prev, kidlist: NEW[Kidrec _ [child: vertex]], kidnum: 1, parnum: vertex^.parnum, parlist: vertex^.parlist, type: type, output: vertex^.output, inname: vertex^.inname, outname: vertex^.outname, number: tree^.size + 1]];
pariter: Kidptr;
vertex^.parlist _ NEW[Kidrec _ [child: temp, parlink: temp^.kidlist]];
vertex^.parnum _ 1;
vertex^.output _ FALSE;
vertex^.outname _ NIL;
vertex^.inname _ NIL;
vertex^.varname _ NIL;
vertex^.parlist^.prev _ vertex^.parlist;
temp^.kidlist^.prev _ temp^.kidlist;
temp^.kidlist^.parlink _ vertex^.parlist;
IF vertex = tree^.csucs
THEN tree^.csucs _ temp
ELSE vertex^.prev^.next _ temp;
vertex^.prev _ temp;
pariter _ temp^.parlist;
WHILE pariter # NIL DO
pariter^.parlink^.parlink _ pariter;
pariter^.parlink^.child _ temp;
pariter _ pariter^.next
ENDLOOP;
tree^.size _ tree^.size + 1
};

SwitchWithNot: PROC [vertex: Node]  ~ {
fmarker : Kidptr _ vertex^.parlist;
rmarker : Kidptr _ NIL;
tempname: ROPE;
tempoutname: LIST OF ROPE;
IF fmarker # NIL THEN rmarker _ fmarker^.prev;
FOR piter: Kidptr _ vertex^.kidlist^.child^.parlist, piter^.next UNTIL piter = NIL DO
IF piter^.child # vertex THEN {
MakeLink[piter^.child, vertex];
[] _ KillPLink[piter]};
ENDLOOP;
IF fmarker # NIL THEN {
FOR piter: Kidptr _ fmarker, piter^.next UNTIL piter = rmarker DO
MakeLink[piter^.child, vertex^.kidlist^.child];
[] _ KillPLink[piter];
ENDLOOP;
MakeLink[rmarker^.child, vertex^.kidlist^.child];
[] _ KillPLink[rmarker]};
IF ((NOT vertex^.kidlist^.child^.output) AND vertex^.output) OR (vertex^.kidlist^.child^.output AND NOT vertex^.output) THEN {
vertex^.kidlist^.child^.output _ vertex^.output;
vertex^.output _ NOT vertex^.output};
tempname _ vertex^.inname;
vertex^.inname _ vertex^.kidlist^.child^.inname;
vertex^.kidlist^.child^.inname _ tempname;
tempname _ vertex^.varname;
vertex^.varname _ vertex^.kidlist^.child^.varname;
vertex^.kidlist^.child^.varname _ tempname;
tempoutname _ vertex^.outname;
vertex^.outname _ vertex^.kidlist^.child^.outname;
vertex^.kidlist^.child^.outname _ tempoutname;
vertex^.kidlist^.child^.type _ NegNodeType[vertex^.kidlist^.child^.type];
};

TwoifyTree: PUBLIC PROC [tree: Dag] ~ {
OrderNodesByOrphans[tree];
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
TwoifyGate[iter, tree];
ENDLOOP;
};

TwoifyGate: PROC [vertex: Node, tree: Dag] ~ {
IF vertex^.kidnum > 2 THEN {
level: INT _ 1;
inleft: INT;
singlep: BOOL _ FALSE;
remaining: INT _ vertex^.kidnum;
nexttype: Vtype _ and;
iter: Kidptr;
right, left: Node;
links: Links _ CreateLinkSet[vertex^.kidlist];
llinks: Links _ CreateLinkSet[NIL];
rlinks: Links _ CreateLinkSet[NIL];
OrderLinksByReq[links];
iter _ links^.top;
WHILE iter # NIL DO
IF iter^.req > 0 THEN {
temp: Kidptr _ iter^.next;
TransferLink[links, iter, llinks];
iter _ temp;
remaining _ remaining - 1;
IF Fullp[llinks] THEN
IF Fullp[rlinks]
THEN ERROR  --Cannot satisfy requirements in TwoifyGate at vertex^.number
ELSE {
templs: Links _ llinks;
llinks _ rlinks;
rlinks _ templs}};
iter _ iter^.next;
ENDLOOP;
WHILE SpaceA[llinks, level] + SpaceA[rlinks, level] < remaining DO
level _ level + 1;
ENDLOOP;
inleft _ (remaining * SpaceA[llinks, level])/(SpaceA[llinks, level] + SpaceA[rlinks, level]);
FOR counter: INT IN [1..inleft] DO
TransferLink[links, links^.top, llinks];
ENDLOOP;
WHILE links^.top # NIL DO
TransferLink[links, links^.top, rlinks];
ENDLOOP;
IF inleft # 1 AND rlinks^.top^.next = NIL THEN {
templs: Links _ llinks;
llinks _ rlinks;
rlinks _ templs;
inleft _ 1};
singlep _ (inleft = 1);
IF vertex^.type = nor OR vertex^.type = or THEN nexttype _ or;
right _ MakeNewNodeA[tree, vertex, nexttype, NIL];
vertex^.kidlist _ rlinks^.top;
WHILE vertex^.kidlist # NIL DO
MakeLink[right, vertex^.kidlist^.child];
[] _ KillCLink[vertex^.kidlist];
ENDLOOP;
vertex^.kidlist _ llinks^.top;
IF NOT singlep THEN {
left _ MakeNewNodeA[tree, vertex, nexttype, NIL];
WHILE vertex^.kidlist # NIL DO
MakeLink[left, vertex^.kidlist^.child];
[] _ KillCLink[vertex^.kidlist];
ENDLOOP;
MakeLink[vertex, left]};
MakeLink[vertex, right];
IF NOT singlep THEN TwoifyGate[left, tree];
TwoifyGate[right, tree]}
};

CreateLinkSet: PROC [link: Kidptr] RETURNS [newLinks: Links] ~ {
newLinks _ NEW[Linksrec _ [top: link]];
IF link # NIL THEN newLinks^.size _ link^.parlink^.child^.kidnum
};

OrderLinksByReq: PROC [links: Links] ~ {
front : Kidptr _ links^.top;
WHILE front # NIL DO
iter: Kidptr _ front^.next;
WHILE iter # NIL DO
IF iter^.req > iter^.prev^.req THEN {
SwitchLinksB[iter, links];
IF front^.prev = iter THEN front _ iter;
iter _ iter^.next};
iter _ iter^.next
ENDLOOP;
front _ front^.next;
ENDLOOP
};

SwitchLinksB: PROC [link: Kidptr, links: Links] ~ {
IF link # links^.top THEN {
prev: Kidptr _ link^.prev;
IF link^.next = NIL
THEN links^.top^.prev _ prev
ELSE link^.next^.prev _ prev;
link^.next _ prev;
IF prev # links^.top
THEN prev^.prev^.next _ link
ELSE links^.top _ link;
prev^.prev _ link}
};

TransferLink: PROC [ebbol: Links, link: Kidptr, ebbe: Links] ~ {
IF link^.next = NIL
THEN ebbol^.top^.prev _ link^.prev
ELSE link^.next^.prev _ link^.prev;
IF link = ebbol^.top
THEN ebbol^.top _ link^.next
ELSE link^.prev^.next _ link^.next;
link^.next _ NIL;
IF ebbe^.top = NIL
THEN ebbe^.top _ link
ELSE {
link^.prev _ ebbe^.top^.prev;
ebbe^.top^.prev^.next _ link};
ebbe^.top^.prev _ link;
ebbol^.size _ ebbol^.size  - 1;
ebbe^.size _ ebbe^.size + 1;
IF link^.req > 0 THEN link^.req _ link^.req - 1
};

Fullp: PROC [links: Links] RETURNS [valasz: BOOL _ FALSE] ~ {
IF links^.top # NIL THEN RETURN[0 # SpaceA[links, links^.top^.prev^.req]]
};

SpaceA: PROC [links: Links, level: INT] RETURNS [free: INT _ 1] ~ {
iter: Kidptr _ links^.top;
atlevel: INT _ 0;  -- Sort of kludgey, but TransferLink has subtracted one from the req field --
WHILE iter # NIL DO
IF iter^.req > atlevel
THEN IF atlevel = level
THEN RETURN
ELSE {
atlevel _ atlevel + 1;
free _ 2 * free}
ELSE {
free _ free - 1;
IF free = 0 THEN RETURN;
iter _ iter^.next}
ENDLOOP;
WHILE atlevel + 1 # level DO
free _ 2 * free;
atlevel _ atlevel + 1;
ENDLOOP;
RETURN
};
CollectWires: PROC [iter: Node] RETURNS [pas: LIST OF CoreCreate.PA _ NIL] ~ {
IF iter # NIL THEN {
IF iter^.type = prim
THEN pas _ CONS[[iter^.inname, iter^.mate^.wire], CollectWires[iter^.next]]
ELSE IF iter^.output
THEN pas _ CONS[[iter^.outname.first, iter^.mate^.wire], CollectWires[iter^.next]]
ELSE pas _ CollectWires[iter^.next]}
};

WireNameFromNode: PROC [vertex: Node] RETURNS [name: ROPE] ~ {
IF vertex^.output OR vertex^.type = prim
THEN IF vertex^.type = prim
THEN name _ vertex^.inname
ELSE name _ vertex^.outname.first
ELSE IF NOT Rope.IsEmpty[vertex^.inname]
THEN name _ Rope.Concat["intrnal", vertex^.inname]
ELSE IF NOT Rope.IsEmpty[vertex^.varname]
THEN name _ Rope.Concat["intrnal", vertex^.varname]
ELSE name _ Rope.Concat["intrnal",Convert.RopeFromInt[vertex^.number,10,FALSE]];
};

MarkCoveredSubtree: PROC [vertex: Node, cover: Node] ~ {
IF cover^.type = prim
THEN IF vertex^.scratch # 1
THEN {
vertex^.scratch _ 1;
IF vertex^.type # prim THEN MarkCoveredSubtree[vertex, vertex^.cover^.csucs]}
ELSE NULL
ELSE IF cover^.type = not
THEN MarkCoveredSubtree[vertex^.kidlist^.child, cover^.kidlist^.child]
ELSE {
MarkCoveredSubtree[cover^.kidlist^.child^.mate, cover^.kidlist^.child];
MarkCoveredSubtree[cover^.kidlist^.next^.child^.mate, cover^.kidlist^.next^.child]}
};

FromDagToCellType: PROC [tree: Dag] RETURNS [cellType: Core.CellType] ~ {
publics: LIST OF CoreCreate.WR _ NIL;
intOnlys: LIST OF CoreCreate.WR _ NIL;
instances: CoreCreate.CellInstances _ NIL;
ClearScratch[tree];
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.output AND iter^.scratch = 0 THEN {
iter^.scratch _ 1;
IF iter^.type # prim THEN MarkCoveredSubtree[iter, iter^.cover^.csucs]};
IF iter^.type = prim THEN iter^.scratch _ 1;
ENDLOOP;
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.scratch = 1 THEN {
iter^.wire _ CoreOps.CreateWires[0, WireNameFromNode[iter]];
IF iter^.output OR iter^.type = prim
THEN publics _ CONS[iter^.wire, publics]
ELSE intOnlys _ CONS[iter^.wire, intOnlys]}
ENDLOOP;
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.scratch = 1 AND iter^.type # prim
THEN instances _ CONS[CoreCreate.InstanceList[iter^.cover^.cell, CollectWires[iter^.cover^.csucs]], instances];
ENDLOOP;
RETURN [CoreCreate.Cell[
public: CoreCreate.WireList[publics],
onlyInternal: CoreCreate.WireList[intOnlys],
instances: instances
]]
};
BoolTreeFromExpressionList: PUBLIC PROC [outputs: LIST OF ROPE, includeGlobalVariablesp: BOOL _ FALSE] RETURNS [tree: Dag] ~ {
tree _ MakeNewBoolTree[];
IF includeGlobalVariablesp THEN {
[] _ MakeNewNodeB[tree, NIL, prim, "Gnd"];
[] _ MakeNewNodeB[tree, NIL, prim, "Vdd"]};
RBoolTreeFromExpressionList[tree, outputs]
};

RBoolTreeFromExpressionList: PROC [tree: Dag, outputs: LIST OF ROPE] ~ {
IF outputs # NIL THEN {
AugmentBoolTreeBySingleExpression[tree, outputs.first];
RBoolTreeFromExpressionList[tree, outputs.rest]}
};

MakeNewBoolTree: PUBLIC PROC [] RETURNS [tree: Dag] ~ {
tree _ NEW[Degree]
};

MakeNewVariableNode: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [newNode: Node] ~ {
newNode _ MakeNewNodeB[tree, NIL, prim, name]
};

MakeNewNotNode: PUBLIC PROC [tree: Dag, node: Node] RETURNS [newNode: Node] ~ {
newNode _ MakeNewNodeA[tree, node, not, NIL];
MakeLink[newNode, node]
};
RMakeNewLinks: PROC [vertex: Node, nodes: LIST OF Node] ~ {
IF nodes # NIL THEN {
MakeLink[vertex, nodes.first];
RMakeNewLinks[vertex, nodes.rest]}
};
MakeNewOrNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ {
newNode _ MakeNewNodeA[tree, NIL, or, NIL];
RMakeNewLinks[newNode, nodes]
};

MakeNewAndNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ {
newNode _ MakeNewNodeA[tree, NIL, and, NIL];
RMakeNewLinks[newNode, nodes]
};

NameNode: PUBLIC PROC [node: Node, name: ROPE] ~ {
node^.varname _ name
};

MakeNamedOutputNode: PUBLIC PROC [tree: Dag, node: Node, name: ROPE] ~ {
node^.output _ TRUE;
node^.outname _ LIST[name]
};

END.

@DrotImpl.mesa
Copyright Ó 1987 by Xerox Corporation.  All rights reserved.
Csaba Gabor August 21, 1987 2:17:27 pm PDT
Bertrand Serlet August 21, 1987 2:24:21 pm PDT
Top Level Calls
Given a list of Boolean Expressions this will return a CellType which they generate
Given a tree, this will construct a CellType which implements the equations described by the tree
Given a Boolean expression, be, this will make incorporate it in tree representation into tree.  Len is the length of be and is passed to avoid recomputing it--
Finds the next name substring in the input ROPE, be--
This calls Parse after a minor amount of preprocessing, it will add the parsed contents of output to tree--
This calls Parse after a minor amount of preprocessing but it adds the representation to the growing set of trees, ctcoll, which are used for covering the main tree--
This is where the trees to be used in the cover are created.

1 input
2 inputs
3 inputs (some missing)
4 inputs (many missing)
xors
Verifies that be1 is a legitimate boolean expression--
Verifies that the parenthesis in be match
Verifies that the operators within be are OK.
I think this section verifies that ands and ors are OK
I think this section verifies that the parenthesis aren't doing anything funny.
Debugging Procedures
Given a tree, this will display it on stream out --
Massaging Procedures
This section here should just be a single routine.  Chalk another one up to laziness and lack of time.
This absorbs certain nodes into others in an attempt to make the Dag smaller.
What do we do for not and buf?
This will get rid of any nodes with the same subset of children from the tree --
this should be rewritten with IntersectionSize instead of the way it is currently being done.  Remember, though, IntersectionSize modifies the scratch field.
If bol and be both have the same children (and type) then this causes bol to be merged into be--
This will disconnect Gnd and Vdd from all other signals, simplifying as it goes along.
This will disconnect gnd from all other nodes, simplifying as it goes along, and sometimes hooking things up to vdd.
This is supposed to eliminate several different types of expressions such as a+~a*b, a*b+~a*b, a*~a, a+b*a and simplify them.  Also for the case of switching the + with the *.  One test which indicates an error somewhere is foo _ a*b+~(a*b)+c.  The interesting thing is that bar = a*b, foo _ bar+~bar+c works.
This one is supposed to take care of the cases a+~a*b and a*~a and the same with + and * switched.
I would slightly redo this section to just remove the two conflicting nodes, make the hookup to gnd or vdd and let the other routine take care of fixing it up on its own.   It's a few more lines code, but conceptually nicer and easier to understand.
This was the a+~a*b check
Maybe you will want to add something here, but it could make the tree bigger than before
This takes care of the a*b+~a*b case a*b+a*b*c case and the following: bar = a*b, foo _ bar + bar*c which is really the previous case arranged in a different way.  Note the use of IntersectionSize.
for the third case
This is legitimate because the kidptrs have been ordered.
Uses the fact that MakeLink places the new link at the beginning
Also, this makes the tree bigger so I don't set modified
This is a genuinely dumb way to do this.  Should be redone with IntersectionSize.  What it does is check to see if sib1 and sib2 are of the form z*(x1*x2*...) and ~z*(x1*x2*...) where * is the the respective types of the two nodes.
Here we assume the two siblings are of equal size
before stays fixed here.  This procedure takes before and after in tree and causes after to be placed after before in linear order.  If before = NIL then PlaceKidptrAtBeg[after,tree] is invoked.  Will fail if after = NIL.  Returns after^.prev (or NIL if after = tree^.kidlist). --
This takes vertex in tree and causes it to be the first in linear order in the tree --
This cleans up dangling nodes from the bottom up.
This splits nodes in tree where the fanout is greater than fout
Any node which is both a prim and and output (other than Vdd and Gnd this should only happen in unaccessed signals) will be buffered, and so are multiple outputs with different names.
Why is this last thing being done?  I think it's because of something I do in outputting the generated cell type, but this may be obsolete by now.
Eliminates name from list, if it is there
Determines whether element is part of list
This eliminates all ors, nors, and ands from the tree, converting everything into nands and nots, leaving the prims alone --
This takes a vertex and makes two in its place, the original's children being the bottom's children and the original's parents being the top's parents.  The top node gets type type (defaulted to not).
This assumes vertex is of type not and switches it with its child
This will yield a tree where each node has fan-in at most 2 --
Given vertex with > 2 children, this will remake that node so that there are at most two inputs per gate at that node.--
This makes a ptr to the given link
This does a bubble sort on the list of Kidptrs on the field req --
This exchanges link and the Kidptr just before it.  Thus, the operation will produce no result if link = links^.top --
This takes and moves link from ebbol into ebbe--
This yields whether or not a subtree is saturated by links with requirements.  It assumes that all links have requirements, and that these are sorted. --
Assuming that all links in links have a req field > 0 this yields the number of free nodes still left assuming a tree of maximum depth level--
Constructing CellType from processed Dag
This makes a list of all the input and one output wires of a true tree headed by iter
This takes a node and generates a wire name from it.  vertex^.number is used if no other name is found
This will put a 1 in the scratch field of the mate of every input vertex in the tree headed by cover.
Takes a covered Dag and returns the cell type which implements that dag, the one implied by the cover.
This marks all nodes which contribute input, output, or internal signals
This is to catch floating inputs (and currently Vdd and Gnd).
Here we create the publics and internal signals from the marked nodes.
Here we create the instances from the covers
Tree Constructors
This returns a BoolTree (Dag) constructed from a list of expressions
This adds an expression to the given tree.
This creates a new Dag with no children
This creates a new node in tree which is treated as an input node with name the given name.
This creates a new node in tree which is the not of node.


This creates a new node in tree which is the OR of all the nodes in the list of nodes.
This creates a new node in tree which is the AND of all the nodes in the list of nodes.
This assigns the specified (var)name to the specified node.  This is useful for later referencing that node by name.
This causes the specified node to be viewed as one of the outputs.
�Ê0ÿ–

"cedar" style˜
codeš
œ
™
K™<Kš
œ*™*K™.—K˜š
Ïk	˜	Kšœ�œ�
˜š
—K˜KšÐlnœ�œ
�˜Kš�œ�œ€
˜•
Kš�œ˜Kšœ�œ
�œ˜'K˜
headš
œ™šÏnœ�œ
�œ�œ
�œ
�œ
�œ�œ˜iKš
œS™SKšœ0�œ˜6Kš�œ%˜+K˜—K˜š
Ÿœ�œ
�œ�œ�œ˜[Kš
œa™aK˜$K˜š�œ)�œ
�œ
�˜AK˜Kš�œ
˜—K˜K˜K˜K˜K˜K˜Kš�œ�œ�œ
�œ
˜MK˜K˜Kšœ�œ˜Kš
œ#˜#Kš�œ˜K˜—K˜šŸœ�œ
�œ�œ�œ�œ�œ˜_Kšœž
Ïc™ 
Kšœ�œ ˜>Kšœ�œ C˜`Kšœ�œ�œ )˜Dš�œ
�˜š�œ�˜!šœ	 ˜ K˜<Kš�œ�œ˜-Kšœ
�œ
˜Kš�œ�œ˜+K˜—šœ ˜Kš�œ
˜—šœ &˜-Kšœ
�œ˜—šœ (˜/š�œ�œ˜Kšœ�œ˜"K˜K˜——šœ	 $˜-š�œ˜š�œ˜Kšœ�œ˜!K˜——K˜š�œ
˜Kš�œ˜Kš�œ˜—K˜—šœ	 #˜,š�œ˜š�œ˜Kš
œ
˜
š�œ
˜Kš�œ˜Kš�œ˜——š�œ
�œ
˜Kš�œ˜Kš�œ˜——K˜Kš�œ
˜—š�œ ,˜:Kšœ�œ
˜Kš
œ2˜2K˜#š�œ�œ
�œ˜Kšœ�œ˜#Kš
œ˜Kš
œ˜—Kš�œ�œ˜-Kšœ
�œ
˜Kš�œ�œ˜+K˜——K˜K˜Kš�œ
˜—Kš
œ˜K˜šŸœ�œ�œ	�œ�œ�œ
�œ˜JKšœ+�œ ™5Kšœ�œ&˜1K˜&Kš
œ˜š�œ�˜#K˜Kš�œ
˜—K˜1Kš
œ˜——K˜šŸ!œ�œ
�œ�œ˜LKšœi ™kKšœ�œ˜Kšœ�œ
˜	K˜	Kšœ�œ˜(Kšœ
�œ˜Kšœ	�œ$˜0Kš
œ7˜7š�œ
˜š�œ˜Kš
œG˜Gš�œ
�œ
�œ	˜Kš�œ.˜2Kš�œ�œ/˜F—Kš�œ
�œ
�œ�œ
˜'—Kš�œ
�˜
—Kš
œ˜—K˜šŸœ�œ
�œ�œ˜=Kšœ¤
 ™¦
K˜Kšœ�œ˜Kšœ�œ˜%Kšœ�œ2˜;Kšœ�œ˜š�œ
˜š�œ˜K˜PKš�œ
�œ�œ/˜WKšœ�œ
˜—Kš�œ
�˜
—K˜—K˜šŸ
œ�œ˜)Kš
œ<™<K™Kš
œ™K˜"Kšœ�œ?˜YKšœ�œ?�œ
�œ˜bK˜K™K˜,Kšœ�œA˜[Kšœ�œ?�œ
�œ˜bK˜K˜)Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bK˜K˜,Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bK˜K˜)Kšœ�œ?˜YKšœ�œ?�œ
�œ˜bK˜K™K˜2Kšœ�œA˜[Kšœ�œ?�œ
�œ˜bK˜K˜1Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bK˜K˜2Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bK˜K˜1Kšœ�œ?˜YKšœ�œ?�œ
�œ˜bK˜K™K˜8Kšœ�œA˜[Kšœ�œ?�œ
�œ˜bK˜K˜8Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bK˜Kš
œ™K˜9Kšœ�œ@˜ZKšœ�œ?�œ
�œ˜bKš
œ˜—K˜šŸœ�œ�œ�œ
�œ�œ�œ˜CKšœ4 ™6Kšœ�œ˜Kšœ�œ˜%Kšœ�œ2˜;š�œ
�œ˜Kš�œ�œ�œ
�œ˜5š�œ�œ�œ˜1Kš�œ�œ�œ
�œ˜-Kš�œ�œ�œ
�œ˜3——K˜K˜š
Ÿœ�œ�œ�œ�œ˜5Kš
œ)™)Kšœ�œ˜Kšœ�œ˜š�œ�œ8�˜Fš�œ
˜Kš�œ
�œ˜š�œ
�œ˜Kš�œ˜š�œ˜K˜Kš�œ�œ
�œ
�œ˜"———Kš�œ
˜—K˜—K˜š
Ÿœ�œ�œ�œ�œ˜1Kšœ*�œ
™-Kšœ�œ˜š�œ�œ<�˜JKšœ4�™6š�œ
˜Kš�œ
�˜	š
�˜š�œ˜š�œ˜Kšœ�œ$˜/š�œ˜Kš�œ
�œ
�œ
˜Kš
�œ
�œ'�œ
�œ
�œ˜A—š�œ�œ�˜$š�œ
˜Kš�œ
�œ
�œ
˜š�œ�œ�˜%Kšœ�œ
�œ˜Kšœ�œ
˜Kš�œ�œ
˜——Kš�œ
˜——š�œ˜Kšœ�œ$˜/š�œ˜Kš�œ
�œ
�œ
˜Kš
�œ
�œ'�œ
�œ
�œ˜A—————Kš�œ
˜—š�œ�œ:�˜HKš
œO™Oš�œ
˜Kš�œ
�œ
�œ
˜š�œ
�œ˜š�œ˜Kšœ�œ˜)Kš�œ&�œ
�œ
�œ˜;š�œ�œ�˜$š�œ
˜Kš�œ
�˜	š�œ
�œ�˜$Kšœ�œ
˜Kšœ�œ
˜Kš�œ�œ
�œ˜——Kš�œ
˜——š�œ˜Kšœ�œ$˜.Kšœ�œ!˜,Kš�œ�œ
�œ
�œ˜%———Kš�œ
˜—K˜——K˜K˜`—š
œ™KšŸ
œ�œ�œ˜JK˜šŸœ�œ
�œ˜K˜K˜$Kšœ�œ�œ
˜Kšœ	�œ
�œ
˜Kšœ�œ
˜	Kšœ�œ˜Kšœ�œ˜*Kšœ�œ˜)K˜EK˜Kš�œF˜Hš�œ�˜Kš�œ˜K˜;Kšœ�œ˜š�œ˜Kš�œ
�˜	š�œ
�œ˜š�œ˜Kš
œ+˜+š�œ˜Kš�œ˜Kš�œ
�œF˜M——š�œ
�œ˜Kš�œ,˜0Kš�œ
�œH˜O———K˜Kš�œ
˜—K˜#K˜K˜—K˜šŸœ�œ#�œ
�œ˜FK˜š�œ)�œ
�œ
�˜AK˜Kš�œ
˜—Kš�œ%˜'K˜Kš�œ&˜(K˜Kš�œ%˜'K˜Kš�œ&˜(K˜Kš�œ%˜'K˜Kš�œ%˜'K˜Kš�œ'˜)Kš�œ�œ�œ
�œ
˜MKš�œ0˜2K˜K˜Kšœ�œ˜Kš�œ8˜:Kš
œ#˜#Kš�œ&˜(K˜Kš�œ˜K˜—K˜š
Ÿœ�œ
�œ�œ
�œ˜1Kšœ1 ™3K˜š�œ�œ
�˜K˜K˜Kš�œ�œ˜.š�œ�˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ˜Kš�œ�œ˜—Kš�œZ˜\Kš�œ�œ
�œ3˜JKš�œ�œ
�œ˜*Kš�œ�œ˜-Kš�œ˜š�œ	�œ
�˜Kš�œ�œ˜2š�œ�˜Kš�œ
�œ˜Kš�œ
�œ˜—K˜Kš�œ
˜—Kš�œ˜š�œ	�œ
�˜Kš�œ�œ˜2š�œ�˜Kš�œ
�œ˜—K˜Kš�œ
˜—K˜Kš�œ
˜—Kš�œ˜K˜——™šŸœ�œ˜!K˜Kšœ�œ�œ
˜š�œ�œ�˜0Kš�œ�œ�œ�œ�œ
�œ
˜‚
Kšœ�œ
˜Kš�œ
˜—Kš
œf™fK˜K˜š�œ�˜Kš
œ˜K˜š�œ�˜
š�œ
�œ˜ Kš�œ˜Kš�œ˜—š�œ
�œ˜Kš�œ˜Kš�œ˜——Kš�œ
˜—K˜K˜K˜Kš
Ÿœ�œ
�œ�œ�œ˜Jš
œM™MK˜š�œ&�œ�œ
�˜<K˜š�œ�œ�œ˜;š�œ
�œ�œ�œ
˜=Kš�œ˜Kš
œ™——š�œ0�œ�œ
�˜Iš�œ!�œ�œ�œ�œ
�œ�œ˜�
Kš�œH�œ�œ
�˜hKš
œ'˜'Kš�œ
˜š�œ˜Kš�œ/˜3Kš�œ
�œ�œ#˜@—K˜!Kšœ�œ˜—Kš�œ
˜—Kš�œ
˜—K˜—K˜šŸœ�œ
�œ
�œ�œ�œ˜QšœN ™PK™�
—K˜š�œ�œ˜"K˜ K˜K˜š�œ�˜K˜Kš�œ
˜—š�œ	�œ
�˜K˜#K˜š�œ
�œ
�˜K˜2š�œ9˜;š�œ˜K˜š�œ�˜š�œ)�œ+˜Yš�œ˜K˜-Kšœ�œ
˜Kš�œ
˜—Kš�œ˜—Kš�œ
˜—K˜2—Kš�œ;˜?—K˜Kš�œ
˜—K˜Kš�œ
˜——K˜K˜šŸ
œ�œ˜/Kšœ^ ™`Kšœ�œ
˜'K˜:K˜2K˜5š�œ)�œ�œ
�˜?K˜Kš�œ
˜—K˜K˜——K˜š
Ÿœ�œ
�œ�œ�œ˜Nš�œ&�œ�œ
�˜<Kšœ�œ˜1Kš�œ
˜—K˜K˜š
Ÿœ�œ�œ�œ�œ˜Mš�œ2�œ�œ
�˜KK˜Kš�œ
˜—š�œ2�œ�œ
�˜Kš�œ˜š�œ˜Kš
œ˜Kšœ�œ
˜—Kš�œ˜!—Kš�œ
˜—š�œ2�œ�œ
�˜KK˜Kš�œ
˜—š�œ2�œ�œ
�˜Kš�œ˜š�œ˜Kš
œ˜Kšœ�œ
˜—Kš�œ˜!—Kš�œ
˜—K˜——K˜š
Ÿœ�œ
�œ�œ�œ˜FKš
œV™VK˜)K˜)š
�œ�œ
�œ�œ
�œ˜ š�œ�œ
�œ�œ˜;Kš
�œ
�œ�œ
�œ�œ˜A—Kš�œ�œ
�œ�œ
�œ�œ
˜Aš	�œ�œ
�œ�œ
�˜1Kš�œ�œ
�œ˜6Kš�œ�œ
�œ˜6Kš�œ
˜——K˜K˜šŸ
œ�œ ˜0Kš
œt™tK˜!š�œ�˜˜K˜K˜—˜
š�œ/�œ�œ
�˜HK˜Kš�œ
˜—Kšœ�œ
˜)K˜<K˜—˜š�œ/�œ�œ
�˜HK˜Kš�œ
˜—Kšœ�œ
˜)K˜<K˜—Kš�œ$�œ 2˜b—K˜—K˜šŸ
œ�œ ˜0K˜ š�œ�˜˜K˜K˜—˜
š�œ/�œ�œ
�˜HK˜Kš�œ
˜—Kšœ�œ
˜)K˜<K˜—˜š�œ/�œ�œ
�˜HK˜Kš�œ
˜—Kšœ�œ
˜)K˜<K˜—Kš�œ$�œ 2˜b—K˜——K˜š
Ÿœ�œ
�œ�œ�œ˜GKš
œµ™µK˜š�œ,�œ�˜JKšœ�œ˜5Kšœ�œ˜5Kš�œ
˜—Kšœ�œ&˜<Kšœ�œ&˜<K˜K˜š
Ÿœ�œ�œ�œ�œ˜UKš
œb™bK˜š�œ�œ˜K˜ Kš�œ�œ�œ˜?š�œ	�œ
�˜K˜'š�œ�˜
Kš�œ˜š�œ˜K˜ š�œ#�˜(š�œ˜š�œ
˜Kš�œ4˜8š�œ5˜9Kš
ϝ
™ù
——K˜Kš�œ
�œ˜——š�œ	�œ
�˜š�œ�œ�œ)�˜_Kš
œ™Kš�œ˜š�œ
�œ˜ š�œ˜š�œ$˜&Kš�œ;˜?Kš�œ6˜:—K˜Kšœ�œ
˜š�œ˜!Kš�œ%˜)Kš�œ˜!——š�œ
�œ˜ š�œ˜K˜K˜6K˜,Kšœ�œ
˜K˜
—Kš�œ˜Kš
œX™X———Kš�œ
˜—Kš
œ˜——Kš�œ
˜——K˜—K˜š
Ÿœ�œ�œ�œ�œ˜UKš
ρ
™Å
K˜š�œ�œ˜K˜K˜K˜Kš�œ�œ�œ˜?š�œ	�œ
�˜K˜ š�œ�œ˜&K˜š�œ�œ
�˜š�œ˜Kš�œ˜š�œ˜Kš
œJ˜JKš
œJ˜JKš
œ™š�œ�˜š�œ
�œ˜š
�˜Kš
œ˜Kšœ�œ
˜š�œ�˜
Kš�œ/˜3Kš�œ%˜)——Kš�œ˜—š�œ
�œ�˜ š�œ˜K˜š�œ˜Kš�œ˜#Kš�œ˜—Kšœ�œ
˜Kšœ�œ
˜—š�œ
�œ+˜2š�œ
�œB˜IKš
œ9™9š�œ 
˜K˜š�œ˜Kš�œ˜#Kš�œ˜—Kšœ�œ
˜Kšœ�œ
˜—Kš�œ˜—š�œ ˜K˜
K˜K˜Fš�œ�˜Kš�œ˜š�œ˜š�œ˜š�œ˜K˜K˜K˜K˜Kšœ�œ
˜Kš�œ!�œ
�œ�œ'˜r—š�œ
�œ˜ š�œ˜K˜
K˜K˜Kšœ�œ
˜K˜K˜—š�œ˜K˜6Kš
œ@™@K™8K˜&š�œ2�œ�œ
�˜HKš�œ�œ$˜6Kš�œ
˜—K˜K˜K˜———Kšœ�œ˜
————————Kš�œ˜	——K˜Kš�œ˜	——K˜K˜š
Ÿ
œ�œ�œ�œ�œ˜[Kš
ύ
™ç
š�œ*�œ�œ
�˜@K˜%š�œ�œ
�œ˜Kšœ�œ�œ
˜K˜0š�œ�œ
�œ˜Kš
œ1™1š�œ,�œ	�œ
�˜CK˜Kš�œ
˜—š�œ,�œ	�œ
�˜CK˜Kš�œ
˜—š�œ,�œ	�œ
�˜CKš�œ�œ�œ	�œ
˜OKš�œ
˜—š�œ�œ˜K˜K˜Kš�œ˜	———Kš�œ
˜—K˜—K˜šŸœ�œ˜+K˜K˜
š�œ�˜
Kš�œ˜Kš�œ
�œ
˜—š�œ�˜K˜K˜K˜Kš�œ
˜—K˜K˜—K˜šŸ	œ�œ ˜/š�œ
�œ
�œ/�œ˜Kš�œ&�œ�œ
�˜<š�œ*�œ˜2K˜/Kš�œ
˜—Kš�œ
˜—K˜:—K˜K˜šŸœ�œ%�œ˜NKšœ‘
�œE�œ�œ ™˜š�œ
�˜Kš�œ˜"š�œ
�œ�œ�˜6š�œ�˜š�œ˜K˜š�œ˜š�œ˜K˜Kšœ�œ
˜—š�œ˜K˜ K˜ K˜Kšœ�œ
˜K˜———š�œ˜š�œ�˜Kš�œ"˜&Kš�œ!˜%—š�œ˜Kš�œ˜ Kš�œ!˜%—K˜K˜K˜K˜————š�œ˜Kš�œ
�œ
�œ
˜Kš�œ
�œ˜—K˜K˜šŸœ�œ!˜7KšœT ™Vš�œ�œ˜ š�œ�œ
˜š�œ˜Kšœ�˜K˜
—š�œ˜K˜"K˜"K˜#K˜Kš
œ˜——K˜K˜—K˜—————K˜šŸ
œ�œ˜1Kš
œ1™1š�œ�˜š�œ˜š�œ˜Kš�œ�œ�œ
 $˜Wš�œ,�œ�œ
�˜BK˜K˜K˜Kš�œ
˜——š	�œ
�œ�œ
�œ�˜8K˜ ˜K˜#Kšœ�œ˜,K˜?š�œ2�œ�œ
�˜KK˜Kš�œ
˜—K˜—Kš�œ�œ
˜———K˜——K˜šŸœ�œ
�œ�œ˜4Kš
œ?™?K˜K˜š�œ)�œ	�œ
�˜@š�œ�˜š�œ�˜K˜,š�œ1�œ�œ
�˜JK˜&Kš�œ
˜—š�œ˜š	�œ
�œ�œ
�œ�˜*K˜,K˜Kš
�˜—š	�œ
�œ�œ
�œ�˜K˜,K˜Kš�œ
˜——Kš�œ
˜——Kš
�˜—K˜—K˜šŸœ�œ˜*Kš
œ·
™·
K˜š�œ&�œ�œ
�˜<š�œ˜š�œ
�œ
˜š�œ˜š�œ$˜&Kš�œ@˜DKš�œ�œ
˜—š�œ�˜šœ	�œ�œ
�œ˜&K˜)š�œ�œ
�˜Kš	œ'�œ�œ�œ�œ˜XK˜#Kš�œ
˜——šœ	�œ�œ
�œ˜&K˜)š�œ�œ
�˜Kš	œ'�œ�œ�œ�œ˜XK˜#Kš�œ
˜——š�œ˜
š�œ�œ
�œ˜K˜)š�œ�œ
�œ˜K˜)K˜—š�œ�œ
�˜K˜6Kšœ�œ
˜Kšœ�œ˜4K˜#Kš�œ˜	————Kš�œ�œ�œ˜9Kš
œ’
™’
—Kš�œ
�˜	—š�œ
�œ�˜š
�œ�œ
�œ�œ
�œ˜:K˜)š�œ�œ
�œ˜K˜)K˜—š�œ�œ
�˜!K˜6Kšœ�œ
˜Kšœ�œ˜4K˜#Kš�œ˜	————Kš�œ
˜—K˜K˜šŸœ�œ�œ�œ
�œ
�œ�œ�œ
�œ
�œ˜TKš
œ)™)š
�œ�œ
�œ
�œ
�œ
˜š�œ
�œ�œ
�œ%˜TKš�œ
�œ
�œ2˜B——K˜—K˜šŸœ�œ�œ�œ
�œ
�œ�œ�œ˜CKš
œ*™*š
�œ�œ
�œ
�œ
�œ
˜ š
�œ
�œ �œ
�œ
�œ
˜8Kš�œ
�œ˜'——K˜——K˜šŸ	œ�œ˜Kšœz ™|Kš
œ˜š�œ(�œ	�œ
�˜?K˜š�œ�œ�œ˜/š�œ1�œ�œ
�˜JK˜ Kš�œ
˜—š�œ˜Kš�œ˜Kš�œ˜——š�œ�œ˜K˜$š�œ�˜š�œ˜K˜K˜K˜—š�œ
�œ�œ
�œ˜.š�œ˜š�œ.�œ�œ
�˜DK˜Kš�œ
˜—K˜!K˜#K˜!K˜#Kš
œ˜Kš
œ˜—Kš�œ˜———š�œ�œ˜K˜$š�œ�œ
�œ˜š�œ4�œ�œ
�˜MK˜0Kš�œ
˜—Kšœ>�œ˜RK˜]K˜eK˜——Kš�œ
˜—K˜K˜šŸ	œ�œ1˜@Kš
œÈ
™È
Kšœ
�œ7�œÈ
˜’K˜Kšœ�œ1˜FK˜Kšœ�œ
˜Kšœ�œ
˜Kšœ�œ
˜Kšœ�œ
˜K˜(K˜$K˜)š�œ˜Kš�œ˜Kš�œ˜—K˜K˜š�œ�œ
�˜K˜$K˜K˜Kš�œ
˜—K˜K˜—K˜šŸ
œ�œ˜'Kš
œA™AK˜#Kšœ�œ
˜Kšœ
�œ
˜Kšœ
�œ
�œ
�œ
˜Kš�œ�œ
�œ˜.š�œ>�œ	�œ
�˜Uš�œ�œ˜K˜K˜—Kš�œ
˜—š�œ�œ
�œ˜š�œ&�œ�˜AK˜/K˜Kš�œ
˜—K˜1K˜—š�œ�œ!�œ�œ!�œ
�œ�œ˜~K˜0Kšœ�œ˜%—K˜K˜0K˜*K˜K˜2K˜+K˜K˜2K˜.K˜IKš
œ˜——K˜šŸ
œ�œ
�œ˜'Kšœ< ™>K˜š�œ&�œ�œ
�˜<K˜Kš�œ
˜—K˜K˜šŸ
œ�œ˜.Kšœv ™xš�œ�œ˜Kšœ�œ˜Kšœ�œ
˜Kšœ	�œ�œ
˜Kšœ�œ˜ K˜K˜
K˜K˜.Kšœ�œ˜#Kšœ�œ˜#K˜K˜š�œ�œ
�˜š�œ�œ˜K˜K˜"K˜K˜š�œ�˜š�œ˜Kš�œ
�œ =˜Iš�œ˜K˜K˜K˜————K˜Kš�œ
˜—š�œ;�˜BKš
œ˜Kš�œ
˜—Kš
œ]˜]š�œ
�œ
�œ
�˜"K˜(Kš�œ
˜—š�œ�œ
�˜K˜(Kš�œ
˜—š�œ�œ�œ
�œ˜0K˜K˜K˜K˜—K˜Kš�œ�œ�œ˜>Kšœ-�œ˜2K˜š�œ�œ
�˜K˜(K˜ Kš�œ
˜—K˜š�œ
�œ	�œ˜Kšœ,�œ˜1š�œ�œ
�˜K˜'K˜ Kš�œ
˜—K˜—K˜Kš�œ
�œ	�œ˜+K˜—Kš
œ˜K˜šŸ
œ�œ�œ˜@Kš
œ"™"Kšœ�œ˜'Kš�œ�œ
�œ.˜@K˜—K˜šŸœ�œ˜(Kšœ@ ™BK˜š�œ	�œ
�˜K˜š�œ�œ
�˜š�œ�œ˜%K˜Kš�œ�œ˜(K˜—K˜Kš�œ
˜—K˜Kš
�˜—Kš
œ˜K˜šŸœ�œ!˜3Kšœt ™vš�œ�œ˜K˜š�œ�˜Kš�œ˜Kš�œ˜—K˜š�œ˜Kš�œ˜Kš�œ˜—K˜—K˜——K˜šŸœ�œ.˜@Kšœ. ™0š�œ�˜Kš�œ˜"Kš�œ˜#—š�œ˜Kš�œ˜Kš�œ˜#—Kšœ
�œ
˜š�œ
�˜Kš�œ˜š�œ˜Kš
œ˜K˜——K˜K˜K˜Kš�œ�œ˜/K˜—K˜š
Ÿœ�œ�œ
�œ�œ˜=Kšœ—
 ™™
Kš�œ�œ
�œ
�œ*˜IK˜—K˜š
Ÿœ�œ�œ�œ�œ	˜CKšœŒ
 ™Ž
K˜Kšœ	�œ M˜`š�œ�œ
�˜š�œ˜š�œ
�œ˜Kš�œ
�˜š�œ˜K˜K˜——š�œ˜K˜Kš�œ
�œ
�œ
˜K˜——Kš�œ
˜—š�œ�˜K˜K˜Kš�œ
˜—Kš
�˜K˜————š
œ(™(šŸœ�œ�œ�œ
�œ�œ�œ˜NKš
œU™Uš�œ�œ
�œ˜š�œ˜Kš�œ�œ<˜Kš�œ
�œ
˜Kš�œ�œC˜RKš�œ ˜$———K˜—K˜šŸœ�œ�œ�œ˜>Kš
œf™fš�œ�œ˜(š�œ
�œ˜Kš�œ˜Kš�œ˜!—š�œ
�œ
�œ˜(Kš�œ.˜2š�œ
�œ
�œ˜)Kš�œ/˜3Kš�œD�œ˜P———K˜—K˜šŸœ�œ ˜8Kš
œe™eš�œ˜š�œ
�œ˜š�œ˜K˜Kš�œ�œ2˜M—Kš�œ
�˜	—š�œ
�œ˜Kš�œB˜Fš�œ˜K˜GK˜S———K˜—K˜šŸœ�œ
�œ˜IKš
œf™fKš	œ	�œ
�œ�œ�œ
˜%Kš	œ
�œ
�œ�œ�œ
˜&Kšœ&�œ
˜*K˜š�œ&�œ�œ
�˜<Kš
œH™Hš�œ�œ�œ˜,K˜Kš�œ�œ/˜H—Kš�œ�œ˜,Kš
œ=™=Kš�œ
˜—š�œ&�œ�œ
�˜<Kš
œF™Fš�œ�œ˜K˜<š�œ�œ˜$Kš�œ�œ˜(Kš�œ�œ˜+——Kš�œ
˜—š�œ&�œ�œ
�˜<Kš
œ,™,š�œ�œ˜*Kš�œ
�œZ˜o—Kš�œ
˜—š�œ˜Kš
œ%˜%Kš
œ,˜,Kš
œ˜K˜—Kš
œ˜——š
œ™šŸœ�œ
�œ�œ
�œ
�œ�œ�œ�œ˜~Kš
œD™DKš
œ˜š�œ�œ˜!Kšœ�œ˜*Kšœ�œ˜+—K˜*K˜—˜š
Ÿœ�œ�œ
�œ
�œ˜HKš
œ*™*š�œ�œ
�œ˜K˜7K˜0—K˜——K˜šŸœ�œ
�œ�œ˜7Kš
œ'™'Kšœ�œ˜Kš
œ˜—K˜š
Ÿœ�œ
�œ�œ�œ˜TKš
œ[™[Kšœ�œ
˜-K˜—K˜šŸœ�œ
�œ�œ˜OK™9Kšœ(�œ˜-K˜K˜—K™šŸ
œ�œ�œ
�œ
˜;š�œ	�œ
�œ˜K˜K˜"—K˜—K™šŸ
œ�œ
�œ�œ
�œ�œ˜WKšœ-�œ'™VKšœ�œ�œ˜+K˜K˜—K˜šŸœ�œ
�œ�œ
�œ�œ˜XKšœ-�œ'™WKšœ�œ�œ˜,K˜K˜—K˜šŸœ�œ
�œ�œ˜2K™tK˜K˜—K˜šŸœ�œ
�œ�œ˜HKš
œB™BKšœ�œ
˜Kšœ�œ˜K˜——K˜Kš�œ
˜K˜—…—�úê9