TNTImpl.mesa
Copyright Ó 1985, 1987 by Xerox Corporation. All rights reserved.
Giordano Bruno Beretta, October 17, 1985 4:37:14 pm PDT
gbb June 4, 1987 12:58:38 pm PDT
Implements The Neighbourhood Ref for Genista.
Gli uomini vollero piuttosto le tenebre che la luce (Giovanni, III, 19.)
DIRECTORY
Basics USING [CompareCard, Comparison],
BasicTime USING [GMT, Now, Period],
CD USING [Object, Orientation, Transformation],
CDBasics USING [DecomposeOrient],
CDOps USING [ToRope],
Checksum USING [ComputeChecksum],
Core USING [Wire],
DrcDebug USING [debug, dLog, PrintWire],
IO, -- debugging only
PrincOpsUtils USING [],
RefTab USING [Create, Delete, EachPairAction, Erase, Fetch, GetSize, Insert, Key, Pairs, Store, Ref, Val],
Rope USING [ROPE],
TNT USING [];
TNTImpl: CEDAR PROGRAM
IMPORTS Basics, BasicTime, CDBasics, CDOps, Checksum, DrcDebug, RefTab, IO
EXPORTS TNT
~ BEGIN
The neighbourhood table
TNT: PUBLIC TYPE ~ REF TNTRep; -- The Neighbourhood Ref
TNTRep: PUBLIC TYPE ~ RECORD [table: RefTab.Ref, lastSweep: BasicTime.GMT];
TNTkey: TYPE ~ REF TNTkeyRep;
TNTkeyRep: TYPE ~ RECORD [cell1, cell2: CD.Object, relPos: CD.Transformation];
Different wires may point to the same sequence of elements. [Se dovesse essere che la medesima configurazione si ripetesse spesso con differenti segnali, occorrerebbe mettere due campi contenenti i fili xorati.]
TNTdata: TYPE ~ REF TNTdataRep;
TNTdataRep: TYPE ~ RECORD [neverAccessed: BOOL ← TRUE, actual1, actual2: Core.Wire];
TNTrecord: TYPE ~ RECORD [k: TNTkey, d: TNTdata];
TNTsize: NAT ~ 31991; -- 10007, 21383, 22307
TNThighWaterMark: NAT = (TNTsize / 3) * 2; -- optimization
sweepInterval: INT ~ 25200; -- in seconds
Hash: PROC [k: RefTab.Key] RETURNS [CARDINAL] ~ BEGIN
PROC [Key] RETURNS [CARDINAL]
TRUSTED {RETURN [Checksum.ComputeChecksum [0, SIZE [TNTkeyRep], LOOPHOLE [k]]]}
END; -- Hash
Match: PROC [key1, key2: RefTab.Key] RETURNS [BOOL] ~ BEGIN
RefTab.EqualProc
k1: TNTkey ~ NARROW [key1, TNTkey]; k2: TNTkey = NARROW [key2, TNTkey];
RETURN [(k1^ = k2^)]
END; -- Match
InitTNT: PUBLIC PROC RETURNS [t: TNT] ~ BEGIN
To be called for each design rule check.
t ← NEW [TNTRep ← [table: RefTab.Create [TNTsize, Match, Hash],
lastSweep: BasicTime.Now []]];
END; -- InitTNT
BlowTNT: PUBLIC PROC [t: TNT] ~ BEGIN
To be called after each design rule check.
t.table.Erase; t ← NIL
END; -- BlowTNT
BuildTNTrecord: PROC [o1, o2: CD.Object, t1, t2: CD.Transformation, a1, a2: Core.Wire] RETURNS [rec: TNTrecord] ~ BEGIN
Save a look-up.
order: Basics.Comparison;
rec.k ← NEW [TNTkeyRep]; rec.d ← NEW [TNTdataRep];
TRUSTED {order ← Basics.CompareCard [LOOPHOLE[o1], LOOPHOLE[o2]]};
IF order = greater THEN BEGIN
oZ: CD.Object = o1; tZ: CD.Transformation = t1; aZ: Core.Wire = a1;
o1 ← o2; o2 ← oZ; t1 ← t2; t2 ← tZ;  a1 ← a2; a2 ← aZ
END;
rec.k.cell1 ← o1; rec.k.cell2 ← o2;
rec.k.relPos ← [[t2.off.x - t1.off.x, t2.off.y - t1.off.y], CDBasics.DecomposeOrient [t1.orient, t2.orient]];
rec.d.actual1 ← a1; rec.d.actual2 ← a2
END; -- BuildTNTrecord
RememberTNT: PUBLIC PROC [t: TNT, o1, o2: CD.Object, t1, t2: CD.Transformation, a1, a2: Core.Wire] ~ BEGIN
Puts the two objects in the neighbourhood table.
rec: TNTrecord ~ BuildTNTrecord [o1, o2, t1, t2, a1, a2];
[] ← t.table.Insert [rec.k, rec.d]
END; -- Remember
InTNT: PUBLIC PROC [t: TNT, o1, o2: CD.Object, t1, t2: CD.Transformation, a1, a2: Core.Wire] RETURNS [BOOL] ~ BEGIN
Asserts that a combination of two cells was already checked.
rec: TNTrecord ~ BuildTNTrecord [o1, o2, t1, t2, a1, a2];
isThere: BOOL; rawData: RefTab.Val; data: TNTdata;
SameSignals: PROC RETURNS [BOOL] ~ INLINE BEGIN
IF (data.actual1.size # rec.d.actual1.size) OR (data.actual2.size # rec.d.actual2.size) THEN RETURN [FALSE];
FOR i: NAT IN [0 .. rec.d.actual1.size) DO
IF (rec.d.actual1[i] # data.actual1[i]) THEN RETURN [FALSE]
ENDLOOP;
FOR i: NAT IN [0 .. rec.d.actual2.size) DO
IF (rec.d.actual2[i] # data.actual2[i]) THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
END; -- SameSignals
[found: isThere, val: rawData] ← t.table.Fetch [rec.k];
data ← NARROW [rawData, TNTdata];
IF DrcDebug.debug AND isThere AND NOT SameSignals [] THEN BEGIN
DrcDebug.dLog.Put1 [IO.rope ["Same key, but different signals:\n"]];
[] ← PrintEltLong [rec.k, rec.d]; [] ← PrintEltLong [rec.k, data]
END;
isThere ← isThere AND SameSignals [];
IF isThere THEN data.neverAccessed ← FALSE;
RETURN [isThere]
END; -- InTNT
UpdateTNT: PUBLIC PROC [t: TNT, o1, o2: CD.Object, t1, t2: CD.Transformation, a1, a2: Core.Wire] RETURNS [wasThere: BOOL] ~ BEGIN
Asserts that a combination of two cells was already checked. The new combination is remembered.
rec: TNTrecord ~ BuildTNTrecord [o1, o2, t1, t2, a1, a2];
rawData: RefTab.Val; data: TNTdata;
SameSignals: PROC RETURNS [BOOL] ~ INLINE BEGIN
IF (data.actual1.size # rec.d.actual1.size) OR (data.actual2.size # rec.d.actual2.size) THEN RETURN [FALSE];
FOR i: NAT IN [0 .. rec.d.actual1.size) DO
IF (rec.d.actual1[i] # data.actual1[i]) THEN RETURN [FALSE]
ENDLOOP;
FOR i: NAT IN [0 .. rec.d.actual2.size) DO
IF (rec.d.actual2[i] # data.actual2[i]) THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
END; -- SameSignals
[found: wasThere, val: rawData] ← t.table.Fetch [rec.k];
data ← NARROW [rawData, TNTdata];
wasThere ← wasThere AND SameSignals [];
IF wasThere THEN data.neverAccessed ← FALSE
ELSE [] ← t.table.Store [rec.k, rec.d]
END; -- UpdateTNT
SweepTNT: PUBLIC PROC [t: TNT] ~ BEGIN
If the neighbourhood table is almost full and sufficient time has elapsed, the entries never accessed are removed from the table. To be called periodically by the main Core traversal mechanism. This procedure must be fast as a bullet, so do not put in additional stuff.
RemoveCadavers: RefTab.EachPairAction ~ BEGIN
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE]
IF NARROW [val, TNTdata].neverAccessed THEN [] ← t.table.Delete [key]
END; -- RemoveCadavers
IF (BasicTime.Period[t.lastSweep,BasicTime.Now[]] > sweepInterval)
AND (t.table.GetSize > TNThighWaterMark) THEN
{[] ← t.table.Pairs [RemoveCadavers]; t.lastSweep ← BasicTime.Now []}
END; -- SweepTNT
Debugging
rot: ARRAY CD.Orientation OF Rope.ROPE ~ [original: "0", mirrorX: "x", rotate90: "90", rotate90X: "90x", rotate180: "180", rotate180X: "180x", rotate270: "-90", rotate270X: "-90x"];
PrintEltShort: RefTab.EachPairAction ~ BEGIN
[key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE]
k: TNTkey ~ NARROW [key, TNTkey];
data: TNTdata ~ NARROW [val, TNTdata];
DrcDebug.dLog.PutF ["Key: %g, %g; %g, (%g, %g).\n", IO.card[LOOPHOLE[k.cell1]], IO.card[LOOPHOLE[k.cell2]], IO.rope[rot[k.relPos.orient]], IO.int[k.relPos.off.x], IO.int[k.relPos.off.y]];
FOR i: NAT IN [0 .. data.actual1.size) DO
DrcDebug.dLog.Put [IO.card[LOOPHOLE[data.actual1[i]]], IO.char[' ]]
ENDLOOP;
DrcDebug.dLog.Put1 [IO.char['\n]];
FOR i: NAT IN [0 .. data.actual2.size) DO
DrcDebug.dLog.Put [IO.card[LOOPHOLE[data.actual2[i]]], IO.char[' ]]
ENDLOOP;
DrcDebug.dLog.Put1 [IO.char['\n]]
END; -- PrintEltShort
PrintEltLong: RefTab.EachPairAction ~ BEGIN
[key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE]
k: TNTkey = NARROW [key, TNTkey];
data: TNTdata = NARROW [val, TNTdata];
DrcDebug.dLog.PutF ["Key: %g, %g; %g, (%g, %g) ", IO.card[LOOPHOLE[k.cell1]], IO.card[LOOPHOLE[k.cell2]], IO.rope[rot[k.relPos.orient]], IO.int[k.relPos.off.x], IO.int[k.relPos.off.y]];
DrcDebug.dLog.PutF ["[CD objects: <%g>, <%g>].\n", IO.rope[CDOps.ToRope[k.cell1]], IO.rope[CDOps.ToRope[k.cell2]]];
DrcDebug.PrintWire [data.actual1]; DrcDebug.PrintWire [data.actual2];
DrcDebug.dLog.Put1 [IO.char['\n]]
END; -- PrintEltLong
PrintTNTLong: PROC [t: TNT] ~ BEGIN
For debugging.
DrcDebug.dLog.PutRope ["\nNeighbourhood Ref:\n"];
[] ← RefTab.Pairs [t.table, PrintEltLong]
END; -- PrintTNT
END.