DIRECTORY Basics, CardHashTableThreaded, IO, LichenComparisonOps, LichenDataOps, LichenDataStructure, Random, Rope, RopeHash, SymTab; LichenCompareStructure: CEDAR PROGRAM IMPORTS Basics, CardHashTableThreaded, IO, LichenComparisonOps, LichenDataOps, LichenDataStructure, Random, SymTab EXPORTS LichenComparisonOps = BEGIN OPEN LichenDataOps, LichenDataStructure, LichenComparisonOps; TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL; initialNetColor: Color = 1; mirrorColor: Color = 2; initialIMColor: Color = 3; colorClass: CardHashTableThreaded.Class = [GetColorDataKey, SetColorDataLink, GetColorDataLink]; debug: BOOL _ TRUE; Break: SIGNAL = CODE; MidSquare: PROC [x: CARD] RETURNS [y: CARD] ~ {y _ MidSquareI[x]}; MidSquareI: PROC [x: CARD] RETURNS [CARD] ~ INLINE { lowProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.LowHalf[x]]]]; midProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.HighHalf[x]]]]; highProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.HighHalf[x], Basics.HighHalf[x]]]]; m: Basics.LongNumber = [lc[AddC[lowProd.hi, midProd.lo, midProd.lo]]]; lo: Basics.LongNumber = [pair[lo: lowProd.lo, hi: m.lo]]; hi: CARD = highProd.lc + AddC[m.hi, midProd.hi, midProd.hi]; RETURN [hi + lo.lc]}; CompareGraphs: PUBLIC PROC [descriptions: RealGraphDescriptions, a, b: CellType, GenerateHints: PROC [Consume: PROC [vA, vB: Vertex]], pick, mirrors, mayQuitEarly: BOOL, abort: REF BOOL] RETURNS [equiv, didQuitEarly: BOOL, partition: ColorTable] = BEGIN rs: Random.RandomStream = Random.Create[seed: 0]; passColor: Color _ noColor; breakVs: SymTab.Ref _ NIL; ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = { AddEdge: PROC [edgeColor: Color, nv: Vertex] = { IF NOT nv.suspect THEN color _ color + (edgeColor+1) * (nv.oldColor+1); }; color _ v.oldColor + passColor; EnumerateEdges[v, AddEdge, mirrors]; color _ FilterColor[MidSquareI[color]]; IF debug AND breakVs#NIL AND breakVs.Fetch[Describe[v, v.containingCT]].found THEN Break; v _ v; }; EnQNeighbor: PROC [edgeColor: Color, neighbor: Vertex] = {EnQ[neighbor]}; EnQ: PROC [v: Vertex] = { v _ v; IF NOT mirrors THEN WITH v SELECT FROM ci: CellInstance => IF IsMirror[ci] THEN ERROR; w: Wire => NULL; im: Intermediary => NULL; ENDCASE => ERROR; IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext _ QFirst; QFirst _ v; QCount _ QCount + 1}}; AddFrontier: PROC [v: Vertex] = {EnumerateEdges[v, EnQNeighbor, mirrors]}; Initialize: PROC = { ClearVertex: PROC [v: Vertex] = { v.QNext _ notInQ; v.equiv _ NIL; v.oldColor _ noColor; v.curColor _ noColor; v.unique _ FALSE; v.suspect _ FALSE; }; NoteAssoc: PROC [vA, vB: Vertex] = { color: Color = FilterColor[rs.NextInt[]]; vA.oldColor _ color; vA.curColor _ color; vB.oldColor _ color; vB.curColor _ color; }; InitVertex: PROC [v: Vertex] = { v.graph _ curGraph; IF v.curColor = noColor THEN { color: Color ~ WITH v SELECT FROM w: Wire => initialNetColor, ci: CellInstance => IF IsMirror[ci] THEN mirrorColor ELSE ci.type.color, im: Intermediary => initialIMColor, ENDCASE => ERROR; v.oldColor _ color; v.curColor _ color; }; AddToColor[GetColorData[curColorData, v.curColor], v]; nonUniqueCount[curGraph] _ nonUniqueCount[curGraph] + 1; }; curGraph: RealGraphID; partition _ CardHashTableThreaded.Create[class: colorClass]; curColorData _ CardHashTableThreaded.Create[class: colorClass]; EnumerateParts[a, ClearVertex, mirrors]; IF abort^ THEN RETURN; EnumerateParts[b, ClearVertex, mirrors]; IF abort^ THEN RETURN; GenerateHints[NoteAssoc]; IF abort^ THEN RETURN; nonUniqueCount _ ALL[IF mirrors THEN 1 ELSE 0]; curGraph _ A; EnumerateParts[a, InitVertex, mirrors]; IF abort^ THEN RETURN; curGraph _ B; EnumerateParts[b, InitVertex, mirrors]; IF abort^ THEN RETURN; someSuspect _ FALSE; [] _ curColorData.Pairs[ComputeUnique]; SetQToAllNonUniques[]; IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR; }; Finalize: PROC = { FinalVertex: PROC [v: Vertex] = { AddToColor[GetColorData[partition, v.curColor], v]; }; EnumerateParts[a, FinalVertex, mirrors]; EnumerateParts[b, FinalVertex, mirrors]; }; SetQToAllNonUniques: PROC = { AddVertex: PROC [v: Vertex] = {IF v.QNext # notInQ THEN ERROR; EnQ[v]}; EnumerateParts[a, AddVertex, mirrors]; EnumerateParts[b, AddVertex, mirrors]; IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR; }; ChoosePairs: PROC [useSuspects, onlyOne: BOOL] RETURNS [pairCount: CARDINAL] = { ConsiderColor: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = { ccd: ColorData = NARROW[value]; first: ARRAY RealGraphID OF Vertex _ [NIL, NIL]; IF ccd.suspect # useSuspects THEN RETURN; FOR v: Vertex _ ccd.firstVertex, v.colorNext WHILE v # NIL DO IF v.QNext # notInQ THEN ERROR; IF first[v.graph] = NIL THEN { first[v.graph] _ v; IF first[OtherGraph[v.graph]] # NIL THEN EXIT}; 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 { pairCount _ pairCount + 1; EnQ[first[A]]; EnQ[first[B]]; quit _ onlyOne}; }; }; pairCount _ 0; [] _ curColorData.Pairs[ConsiderColor]; }; ComputeUnique: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = { ccd: ColorData = NARROW[value]; uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1]; unique: BOOL _ uniques[A] AND uniques[B]; IF unique THEN { a: Vertex _ ccd.firstVertex; 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 _ TRUE; b.unique _ TRUE; a.equiv _ b; b.equiv _ a; nonUniqueCount[A] _ nonUniqueCount[A] - 1; nonUniqueCount[B] _ nonUniqueCount[B] - 1; }; someSuspect _ (ccd.suspect _ ccd.count[A] # ccd.count[B]) OR someSuspect; FOR v: Vertex _ ccd.firstVertex, v.colorNext WHILE v # NIL DO v.oldColor _ v.curColor; v.suspect _ ccd.suspect; ENDLOOP; }; QueueFrontier: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = { ccd: ColorData = NARROW[value]; uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1]; unique: BOOL _ uniques[A] AND uniques[B]; IF unique THEN { v1: Vertex _ ccd.firstVertex; v2: Vertex _ v1.colorNext; IF v2.colorNext # NIL THEN ERROR; IF v1.graph = v2.graph THEN ERROR; IF NOT (v1.unique AND v2.unique) THEN ERROR; AddFrontier[v1]; AddFrontier[v2]; }; }; nonUniqueCount: TwoCount _ ALL[LAST[CARDINAL]]; curColorData, oldColorData: ColorTable _ NIL; pass: CARDINAL _ 0; QFirst: Vertex _ endOfQ; QCount: CARDINAL _ 0; isAll: BOOL _ TRUE; someMC, someSuspect: BOOL _ FALSE; IF abort^ THEN RETURN [FALSE, FALSE, NIL]; Initialize[]; IF abort^ THEN RETURN [FALSE, FALSE, NIL]; IF debug THEN WriteAll["CompareCDs Initialized", descriptions, a, b, oldColorData, curColorData]; didQuitEarly _ mayQuitEarly AND someSuspect; WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 AND NOT didQuitEarly DO mcCount: CARDINAL _ 0; keepOld: BOOL _ isAll; IF abort^ THEN RETURN [FALSE, FALSE, NIL]; pass _ pass + 1; passColor _ LOOPHOLE[rs.NextInt[], Color]; IF QCount > 0 THEN NULL ELSE IF NOT (isAll AND NOT someMC) THEN SetQToAllNonUniques[] ELSE {pairCount: CARDINAL _ 0; IF pick THEN pairCount _ ChoosePairs[FALSE, TRUE]; IF pairCount = 0 THEN { IF QFirst # endOfQ OR QCount # 0 THEN ERROR; pairCount _ ChoosePairs[TRUE, FALSE]; IF pairCount = 0 THEN EXIT}}; isAll _ (nonUniqueCount[A] + nonUniqueCount[B]) = QCount; oldColorData _ IF keepOld THEN curColorData ELSE CardHashTableThreaded.Create[curColorData.GetSize[], colorClass]; curColorData _ CardHashTableThreaded.Create[curColorData.GetSize[], colorClass]; someMC _ FALSE; WHILE QFirst # endOfQ DO v: Vertex = QFirst; oldColor: Color = v.oldColor; newColor: Color = ComputeColor[v]; ncd: ColorData = GetColorData[curColorData, newColor]; IF abort^ THEN RETURN [FALSE, FALSE, NIL]; IF QFirst = notInQ THEN ERROR; v.curColor _ newColor; QFirst _ v.QNext; v.QNext _ notInQ; IF isAll AND NOT someMC THEN { ocd: ColorData = GetColorData[oldColorData, oldColor, keepOld]; IF ocd.newColor = noColor THEN ocd.newColor _ newColor ELSE IF ocd.multicolored THEN ERROR ELSE IF ocd.newColor = newColor THEN NULL ELSE ocd.multicolored _ someMC _ TRUE; }; AddToColor[ncd, v]; ENDLOOP; QCount _ 0; someSuspect _ FALSE; [] _ curColorData.Pairs[ComputeUnique]; [] _ curColorData.Pairs[QueueFrontier]; IF debug THEN { Log["\nAt end of pass %g:\n", [cardinal[pass]]]; WriteColorTable[curColorData, descriptions]; Log["QCount=%g, nonUniqueCount=[%g, %g]", IO.card[QCount], IO.card[nonUniqueCount[A]], IO.card[nonUniqueCount[B]]]; Log[", someMC=%g, isAll=%g, someSuspect=%g\n", IO.bool[someMC], IO.bool[isAll], IO.bool[someSuspect]]; WriteQ[QFirst, descriptions]; }; ENDLOOP; equiv _ nonUniqueCount[A]=0 AND nonUniqueCount[B]=0; Finalize[]; END; GetColorData: PROC [colorTable: ColorTable, color: Color, mayNotCreate: BOOL _ FALSE] RETURNS [cd: ColorData] = { cd _ NARROW[colorTable.Fetch[color].value]; IF cd # NIL OR mayNotCreate THEN RETURN; cd _ NEW [ColorDataPrivate _ [color: color]]; IF NOT colorTable.Insert[color, cd] THEN ERROR; }; AddToColor: PROC [cd: ColorData, v: Vertex] = INLINE { v.colorNext _ cd.firstVertex; cd.firstVertex _ v; cd.count[v.graph] _ cd.count[v.graph] + 1; }; EnumerateEdges: PROC [v: Vertex, Consume: PROC [Color, Vertex], includeMirror: BOOL] ~ { Pass: PROC [port: Port, w: Vertex] ~ {Consume[port.color, w]}; EnumerateImmediateConnections[v, Pass]; }; WriteQ: PROC [QFirst: Vertex, descriptions: RealGraphDescriptions] = 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", [rope[descriptions[QFirst.graph]]], IO.rope[VerboseVName[QFirst]]]; ENDLOOP; Log["}\n"]; END; GetColorDataKey: PROC [value: REF ANY] RETURNS [key: CARD] = { cd: ColorData = NARROW[value]; key _ cd.color; }; SetColorDataLink: PROC [from, to: REF ANY] = { fromCD: ColorData = NARROW[from]; toCD: ColorData = NARROW[to]; fromCD.nextColor _ toCD; }; GetColorDataLink: PROC [from: REF ANY] RETURNS [to: REF ANY] = { fromCD: ColorData = NARROW[from]; to _ fromCD.nextColor; }; AddC: PROC [c1, c2, c3: CARDINAL] RETURNS [CARD] = INLINE { RETURN [c1.LONG + c2.LONG + c3.LONG]; }; END. РLichenCompareStructure.Mesa Bertrand Serlet June 4, 1986 4:16:39 pm PDT Last tweaked by Mike Spreitzer on December 9, 1987 9:59:50 am PST Э╩ |Ц "cedar" styleШcodeЪЬЩKЩ+KЩAЧKШKЪ╧k Ь ЭЬZШЕKШЪ╨bxЬЭЬЭШ%KЪЭЬ ЭЬIШrKЪЭЬШЧKШKЪЭЬЭЬ9ШCKШKЪ Ь ЭЬЭЬ ЭЬЭЬШ/KШKШKШKЪЬШKШKЪЬ`Ш`KШKЪЬЭЬЭЬШKЪ╧nЬЭЬЭЬШKШKЪ Я ЬЭЬЭЬЭЬЭЬШBKШЪЯ ЬЭЬЭЬЭЬЭЬЭЬШ4KЪЬYШYKЪЬZШZKЪЬ\Ш\KЪЬFШFKЪЬ9Ш9KЪЬЭЬ4ШKЪЬ'Ш'KШЧKШЪЯЬЭЬ8ШDKЪЭШKЪЬЭЬЭЬШKШ ЪЭЬЭЬЭШ:KЪЭЬЭЬЭЬШKЪЭЬЭЬ ЭЬЭЬШ+KЪЬ2ЭЬШQKЪЭЬШЧKШKЪЭЬШЧKШЪЯЬЭЬ ЭЬЭЬЭЬЭЬШ>KЪЬЭЬШKШKШЧKШЪЯЬЭЬЭЬЭЬШ.KЪЬЭЬШ!KЪЬЭЬШKШKШЧKШЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬШ@KЪЬЭЬШ!KШKШЧKШЪЯЬЭЬЭЬЭЬЭЬЭЬШ;KЪЭЬЭЬЭЬЭЬШ%KШKШЧKЪЭЬШЧЕЧ(86D