DIRECTORY CompareDataStructure, CompareOps, IO, OrderedSymbolTableRef, Real, Rope;CompareCellDefs: CEDAR PROGRAMIMPORTS CompareOps, IO, OrderedSymbolTableRef, Real, RopeEXPORTS CompareDataStructure, CompareOps =BEGIN OPEN CompareDataStructure, CompareOps;TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;graphIDToRope: PUBLIC ARRAY GraphID OF ROPE _ [A: "A", B: "B", Unspecified: "Unspecified"];endOfQ: PUBLIC Vertex _ NEW [VertexRep];PortHashSize: CARDINAL = LAST[HashTableIndex];MinHashSize: CARDINAL _ 511;sizeFactor: REAL _ 0.25;initialNetColor: Color _ 1;CompareGraphs: PUBLIC PROC [a, b: CellType, seeAllInstanceNames: BOOL] RETURNS [equiv: BOOL] =BEGINComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {color _ v.oldColor;FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DOnv: Vertex _ e.sides[OtherClass[v.class]].v;IF e.sides[v.class].v # v THEN ERROR;IF NOT nv.suspect THEN color _ (color + (e.color+1) * (nv.oldColor+1)) MOD hashTable.length;ENDLOOP};EnQ: PROC [v: Vertex] = {IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext _ QFirst; QFirst _ v; QCount _ QCount + 1}};AddFrontier: PROC [v: Vertex] = {FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DOIF e.sides[v.class].v # v THEN ERROR;EnQ[e.sides[OtherClass[v.class]].v];ENDLOOP};Initialize: PROC = {InitVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {v: Vertex;stop _ FALSE;WITH ra SELECT FROMvtx: Vertex => v _ vtx;a: Alias => {v _ NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};ENDCASE => ERROR;v.graph _ curGraph;IF v.unique OR v.QNext # notInQ THEN ERROR;v.equiv _ NIL;v.suspect _ FALSE;SELECT v.class FROMnet => v.curColor _ initialNetColor;cell => {portIndex: PortIndex _ 0;IF v.type.inittedFor # hts THEN InitCellType[v.type];v.curColor _ v.type.color;FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DOIF e.portIndex # portIndex THEN ERROR;IF e.sides[cell].v # v THEN ERROR;e.color _ v.type.ports[portIndex].color;portIndex _ portIndex + 1;ENDLOOP;IF portIndex # v.type.ports.length THEN ERROR;};ENDCASE => ERROR;v.oldColor _ v.curColor;EnQ[v]};InitCellType: PROC [ct: CellType] = {ct.inittedFor _ hts;ct.color _ HashRope[CTEquivClass[ct], hts];FOR pi: PortIndex IN [0 .. ct.ports.length) DOct.ports[pi].color _ HashRope[PortEquivClass[ct, pi], PortHashSize];ENDLOOP;};hts: CARDINAL _ MAX[MinHashSize, Real.RoundC[sizeFactor * (a.parts.Size[] + b.parts.Size[] + 2)]];curGraph: RealGraphID;QFirst _ endOfQ; QCount _ 0;hashTable _ NEW [HashTableRep[hts]];hashTable.firstNonEmpty _ NullIndex;FOR hti: HashTableIndex IN [0 .. hashTable.length) DOhashTable[hti] _ [];ENDLOOP;curGraph _ A;a.parts.EnumerateIncreasing[InitVertex]; [] _ InitVertex[a.mirror]; --AM1curGraph _ B;b.parts.EnumerateIncreasing[InitVertex]; [] _ InitVertex[b.mirror];nonUniqueCount[A] _ a.parts.Size[] + 1;nonUniqueCount[B] _ b.parts.Size[] + 1;IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;};SetQToAllNonUniques: PROC = {AddVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {v: Vertex;stop _ FALSE;WITH ra SELECT FROMvtx: Vertex => v _ vtx;a: Alias => {v _ NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};ENDCASE => ERROR;IF v.QNext # notInQ THEN ERROR;EnQ[v]};wasAll _ TRUE;a.parts.EnumerateIncreasing[AddVertex]; [] _ AddVertex[a.mirror]; --AM1b.parts.EnumerateIncreasing[AddVertex]; [] _ AddVertex[b.mirror];IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;hashTable.firstNonEmpty _ NullIndex};ChoosePairs: PROC [useSuspects: BOOL] RETURNS [pairCount: CARDINAL] = {wasAll _ TRUE; pairCount _ 0;FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DOfirst: ARRAY RealGraphID OF Vertex _ [NIL, NIL];IF hashTable[hti].suspect # useSuspects THEN LOOP;FOR v: Vertex _ hashTable[hti].v, v.colorNext WHILE v # NIL DOIF v.QNext # notInQ THEN ERROR;IF first[v.graph] = NIL THEN first[v.graph] _ v;ENDLOOP;IF first[A]#NIL AND first[B]#NIL THEN {IF first[A].unique # first[B].unique THEN ERROR;IF NOT first[A].unique THEN {IF first[A].QNext # notInQ THEN ERROR;IF first[B].QNext # notInQ THEN ERROR;pairCount _ pairCount + 1;EnQ[first[A]]; EnQ[first[B]]}};ENDLOOP;hashTable.firstNonEmpty _ NullIndex};nonUniqueCount: TwoCount _ ALL[LAST[CARDINAL]];hashTable: HashTable _ NIL;pass: CARDINAL _ 0;QFirst: Vertex;QCount: CARDINAL;wasAll: BOOL _ TRUE;Initialize[];WriteAll["CompareCDs Initialized", a, b, hashTable];WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 DOmcCount: CARDINAL _ 0;someMC: BOOL _ FALSE;pass _ pass + 1;WHILE QFirst # endOfQ DOv: Vertex _ QFirst;oldColor: Color _ v.oldColor;newColor: Color _ v.curColor _ ComputeColor[v];IF QFirst = notInQ THEN ERROR;QFirst _ v.QNext;v.QNext _ notInQ;IF wasAll AND NOT someMC THEN {IF hashTable[oldColor].newColor = noColor THEN hashTable[oldColor].newColor _ newColorELSE IF hashTable[oldColor].multicolored THEN ERRORELSE IF hashTable[oldColor].newColor = newColor THEN NULLELSE hashTable[oldColor].multicolored _ someMC _ TRUE;};IF hashTable[newColor].count[A] = 0 AND hashTable[newColor].count[B] = 0 THEN {hashTable[newColor].v _ NIL;hashTable[newColor].nextNonEmpty _ hashTable.firstNonEmpty;hashTable.firstNonEmpty _ newColor};v.colorNext _ hashTable[newColor].v;hashTable[newColor].v _ v;hashTable[newColor].count[v.graph] _ hashTable[newColor].count[v.graph] + 1;ENDLOOP;QCount _ 0;FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DOuniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];unique: BOOL _ uniques[A] AND uniques[B];IF unique THEN {a: Vertex _ hashTable[hti].v;b: Vertex _ a.colorNext;IF b.colorNext # NIL THEN ERROR;IF a.graph = b.graph THEN ERROR;IF a.unique OR b.unique THEN ERROR;a.unique _ b.unique _ TRUE;a.equiv _ b; b.equiv _ a;nonUniqueCount[A] _ nonUniqueCount[A] - 1;nonUniqueCount[B] _ nonUniqueCount[B] - 1;};ENDLOOP;FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DOuniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];unique: BOOL _ uniques[A] AND uniques[B];IF unique THEN {a: Vertex _ hashTable[hti].v;b: Vertex _ a.colorNext;IF b.colorNext # NIL THEN ERROR;IF a.graph = b.graph THEN ERROR;IF NOT (a.unique AND b.unique) THEN ERROR;AddFrontier[a]; AddFrontier[b];};hashTable[hti].suspect_ hashTable[hti].count[A] # hashTable[hti].count[B];FOR v: Vertex _ hashTable[hti].v, v.colorNext WHILE v # NIL DOv.oldColor _ v.curColor;v.suspect _ hashTable[hti].suspect;ENDLOOP;hashTable[hti].count[A] _ 0;hashTable[hti].count[B] _ 0;hashTable[hti].newColor _ noColor;hashTable[hti].multicolored _ FALSE;ENDLOOP;WriteAll[IO.PutFR["Almost end of pass %g", IO.card[pass]], a, b, hashTable];Log["QCount=%g, nonUniqueCount=[%g, %g], someMC=%g, wasAll=%g\n",IO.card[QCount], IO.card[nonUniqueCount[A]],IO.card[nonUniqueCount[B]], IO.bool[someMC], IO.bool[wasAll]];WriteQ[QFirst];IF QCount > 0 THEN {wasAll _ (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;hashTable.firstNonEmpty _ NullIndex}ELSE IF someMC OR (NOT wasAll) THEN SetQToAllNonUniques[]ELSE {pairCount: CARDINAL _ ChoosePairs[useSuspects: FALSE];IF pairCount = 0 THEN {QFirst _ endOfQ; QCount _ 0;pairCount _ ChoosePairs[useSuspects: TRUE];IF pairCount = 0 THEN EXIT}};ENDLOOP;equiv _ nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;END;HashRope: PROC [r: ROPE, hashTableSize: CARDINAL] RETURNS [c: Color] =BEGINlen: INT = r.Length[];c _ 1;FOR i: INT DECREASING IN [0 .. len) DOchar: CHAR _ r.Fetch[i];long: LONG CARDINAL _ rot*c + (char-0C);c _ long MOD hashTableSize;ENDLOOP;END;rot: LONG CARDINAL _ 128 + 32 + 2;CTEquivClass: PROC [ct: CellType] RETURNS [equivClass: EquivClass] = {equivClass _ IF ct.equivClass = implicitClass THEN PickAName[ct.names] ELSE ct.equivClass};PortEquivClass: PROC [ct: CellType, pi: PortIndex] RETURNS [equivClass: EquivClass] = {equivClass _ IF ct.ports[pi].equivClass = implicitClass THEN PickAName[ct.ports[pi].names] ELSE ct.ports[pi].equivClass};WriteQ: PROC [QFirst: Vertex] =BEGINfirst: BOOL _ TRUE;Log["Q = {"];FOR QFirst _ QFirst, QFirst.QNext WHILE QFirst # endOfQ DOIF QFirst = notInQ THEN ERROR;IF first THEN first _ FALSE ELSE Log[", "];Log["%g.%g", IO.rope[graphIDToRope[QFirst.graph]], IO.rope[PickAName[QFirst.names]]];ENDLOOP;Log["}\n"];END;Test: PROC [da, db: Design, aName, bName: ROPE] =BEGINaType: CellType _ NARROW[Lookup[da.cellTypesByName, aName]];bType: CellType _ NARROW[Lookup[db.cellTypesByName, bName]];equiv: BOOL;EnsureParts[aType];EnsureParts[bType];Log["\nTesting %g %g\n", IO.rope[aName], IO.rope[bName]];equiv _ CompareGraphs[aType, bType, FALSE];Log["\nEquiv = %g.\n", IO.bool[equiv]];FlushLog[];END;END.    R  CompareCellDefs.MesaLast Edited by: Spreitzer, June 1, 1985 3:57:15 pm PDTЭ╩ї  Ц"cedar" styleШ IcodeЩJЩ6KШ KЪ╧k	Ь#ЭЬ$ШRKШ Ъ╨bxЬЭЬЭШKЪЭЬЭЬ#Ш9KЪЭЬ#Ш*KШ KЪЭЬЭЬ"Ш,KШ KЪ	Ь
ЭЬЭЬЭЬЭЬШ/KШ KЪЬЭЬЭЬ	ЭЬЭЬЭЬЭЬ#Ш[KШ KЪЬЭЬ
ЭЬШ(KШ KЪЬЭЬЭЬШ.KЪЬЭЬШKЪЬЭЬШKШKШ Ъ╧nЬЭЬЭЬ'ЭЬЭЬ	ЭЬШ^KЪЭШЪЯЬЭЬЭЬШ9KЪЬШЪЭЬ.ЭЬЭЬЭШAKШ,KЪЭЬЭЬЭЬШ%KЪЭЬЭЬЭЬ1ЭЬШ\KЪЭЬШ	ЧЧKЪЯЬЭЬЭЬЭЬЭЬЭЬ6Ш|ЪЯЬЭЬШ!ЪЭЬ.ЭЬЭЬЭШAKЪЭЬЭЬЭЬШ%KШ$KЪЭЬШ	ЧЧЪЯ
ЬЭЬШЪЯ
ЬЭЬЭЬЭЬЭЬЭЬШ7KЪЬ
Ш
KЪЬЭЬШЪЭЬЭЬЭШKЪЬШKЪ	ЬЭЬЭЬЭЬЭЬШSKЪЭЬЭЬШЧKШKЪЭЬ
ЭЬЭЬЭЬШ+KЪЬ
ЭЬШKЪЬЭЬШЪЭЬ	ЭШKШ$Ш	KШKЪЭЬЭЬШ5KШЪЭЬ+ЭЬЭЬЭШ>KЪЭЬЭЬЭЬШ&KЪЭЬЭЬЭЬШ"KШ(KШKЪЭЬШЧKЪЭЬ!ЭЬЭЬШ.KШЧKЪЭЬЭЬШЧKШKШЧЪЯЬЭЬШ%KШKШ+ЪЭЬЭЬЭШ.KЪЬDШDKЪЭЬШЧKШЧKЪЬЭЬЭЬOШbKШKШKЪЬЭЬШ$KЪЬ$Ш$ЪЭЬЭЬЭШ5KШKЪЭЬШЧKЪЬЭЬШKЪЬD╧cШIKЪЬЭЬШKЪЬCШCKЪЬЭЬШ'KЪЬЭЬШ'KЪ
ЭЬЭЬЭЬЭЬЭЬШ?KЪЬШЧЪЯЬЭЬШЪЯ	ЬЭЬЭЬЭЬЭЬЭЬШ6KЪЬ
Ш
KЪЬЭЬШЪЭЬЭЬЭШKШKЪ	ЬЭЬЭЬЭЬЭЬШSKЪЭЬЭЬШЧKЪЭЬЭЬЭЬШKЪЬШЧKЪЬ	ЭЬШKЪЬBаШGKЪЬAШAKЪ
ЭЬЭЬЭЬЭЬЭЬШ?KЪЬ%Ш%ЧЪ
ЯЬЭЬЭЬЭЬЭЬШGKЪЬ	ЭЬШЪЭЬLЭЬЭШgKЪ	ЬЭЬЭЬЭЬЭЬШ0KЪЭЬ&ЭЬЭЬШ2ЪЭЬ+ЭЬЭЬЭШ>KЪЭЬЭЬЭЬШKЪЭЬЭЬЭЬШ0KЪЭЬШЧЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ'KЪ
ЭЬЭЬЭЬ	ЭЬЭЬШ0ЪЭЬЭЬЭЬ	ЭЬШKЪЭЬЭЬЭЬЭЬШ&KЪЭЬЭЬЭЬЭЬШ&KЪЬШKЪЬ
ЭЬЭЬШЧЧKЪЭЬШЧKЪЬ%Ш%ЧKЪЬЭЬЭЬЭЬШ/KЪЬЭЬШKЪЬЭЬШKШKЪЬЭЬШKЪЬЭЬЭЬШKШKШ4Ъ	ЭЬЭЬЭЬЭЬЭШ4KЪЬ	ЭЬШKЪЬЭЬЭЬШKЪЬШЪЭЬЭШKШKШKЪЬ/Ш/KЪЭЬЭЬЭЬШKШKЪЬШЪЭЬЭЬЭЬЭЬШKЪЭЬ(ЭЬ(ШVKЪЭЬЭЬ"ЭЬЭШ3KЪЭЬЭЬ)ЭЬЭШ9KЪЭЬ-ЭЬШ6KШЧЪ
ЭЬЭЬЭЬЭЬЭЬШOKЪЬЭЬШKЪЬ;Ш;KЪЬ$Ш$ЧKЪЬ$Ш$KЪЬШKЪЬLШLKЪЭЬШЧKШЪЭЬLЭЬЭШgKЪЬ	ЭЬЭЬЭЬЭЬЭЬШ\KЪ	ЬЭЬЭЬЭЬ	ЭЬШ)ЪЭЬЭЬШKЪЬШKШKЪЭЬЭЬЭЬЭЬШ KЪЭЬЭЬЭЬШ KЪЭЬ
ЭЬ
ЭЬЭЬШ#KЪЬЭЬШKШKЪЬЭЬЭЬШ*KЪЬЭЬЭЬШ*KШЧKЪЭЬШЧЪЭЬLЭЬЭШgKЪЬ	ЭЬЭЬЭЬЭЬЭЬШ\KЪ	ЬЭЬЭЬЭЬ	ЭЬШ)ЪЭЬЭЬШKЪЬШKШKЪЭЬЭЬЭЬЭЬШ KЪЭЬЭЬЭЬШ KЪ
ЭЬЭЬЭЬЭЬЭЬШ*KЪЬШKШЧKЪЬ-ЭЬЭЬШJЪЭЬ+ЭЬЭЬЭШ>KШKЪЬ#Ш#KЪЭЬШЧKЪЬЭЬШKЪЬЭЬШKЪЬ"Ш"KЪЬЭЬШ$KЪЭЬШЧKЪЬ	ЭЬ ЭЬШLЪЬAШAKЪЭЬЭЬЭЬШ,KЪЭЬЭЬЭЬЭЬШ>ЧKШЪЭЬЭЬШKЪЬЭЬЭЬШ:KШ$ЧKЪ
ЭЬЭЬЭЬЭЬ	ЭЬШ9ЪЭЬЭЬЭЬШ<ЪЭЬЭЬШ3KЪЬ%ЭЬШ+KЪЭЬЭЬЭЬШЧЧKЪЭЬШЧKЪЬЭЬЭЬЭЬШ4KЪЭЬШЧKШ Ъ
ЯЬЭЬЭЬЭЬЭЬШFKЪЭШKЪЬЭЬШKШЪ	ЭЬЭЬЭ
ЬЭЬЭШ&KЪЬЭЬШKЪЬЭЬЭЬШ(KЪЬ	ЭЬШKЪЭЬШЧKЪЭЬШKЪЬЭЬЭЬШ"ЧKШ ЪЯЬЭЬЭЬШFKЪЬЭЬЭЬЭЬШ[ЧKШ ЪЯЬЭЬЭЬШWKЪЬЭЬ)ЭЬЭЬШyЧKШ ЪЯЬЭЬШKЪЭШKЪЬЭЬЭЬШKШЪЭЬЭЬЭШ:KЪЭЬЭЬЭЬШKЪЭЬЭЬ	ЭЬЭЬШ+KЪЬЭЬ$ЭЬ ШUKЪЭЬШЧKШKЪЭЬШЧKШ ЪЯЬЭЬ ЭЬШ1KЪЭШKЪЬЭЬ$Ш<KЪЬЭЬ$Ш<KЪЬЭЬШKЪЬШKЪЬШKЪЬЭЬЭЬШ9KЪЬ$ЭЬШ+KЪЬЭЬШ'KШKЪЭЬШЧKШ KЪЭЬШЧЧ ЕЧ    "Ў  /=  