colorClass: CardHashTableThreaded.Class = [GetColorDataKey, SetColorDataLink, GetColorDataLink];
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;
QFirst ← endOfQ; QCount ← 0;
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;
QCount: CARDINAL;
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;