SXLayersImpl.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Creates a representation of the layout suitable for hierarchical analysis. Spinifex produces a hierarchical circuit representation, and list of regions containing design rule violations.
Written by Shand, September 12, 1983 11:40 pm
Last Edited by Mark Shand, March 13, 1985 2:50:54 am PST
Last Edited by: Jacobi, March 27, 1985 8:25:11 pm PST
Last Edited by: Jacobi, April 8, 1985 4:39:46 pm PST
Bowers, September 6, 1985 11:50:22 am PDT
Last edited by: gbb July 15, 1985 11:52:49 am PDT
DIRECTORY
Atom USING [PropList],
CD,
CDBasics USING [BaseOfRect, Extend, Intersect, Intersection, ToRect],
CDOrient,
CornerStitching,
SX,
SXAccess,
SXAccessInternal,
SXConflicts USING [ComputeConflicts, ResolveConstraints],
SXLayers,
SXQuadTree USING [Create, Dimension, Enumerate, PerRectProc, QuadTree, QuadTreeRoot, Rectangle, Rectangles],
TerminalIO USING [WriteChar, WriteRope];
SXLayersImpl:
CEDAR
PROGRAM
IMPORTS CD, CDBasics, CDOrient, CornerStitching, SX, SXAccess, SXAccessInternal, SXConflicts, SXQuadTree, TerminalIO
EXPORTS SXLayers =
BEGIN
-- TYPES
ConflictWorlds:
TYPE =
ARRAY SX.SpinifexLayerIndex
OF
REF CornerStitching.Tesselation;
--The conflict worlds are used to find the regions where interactions occour.
GeometryWorlds:
TYPE =
ARRAY SX.SpinifexLayerIndex
OF
REF CornerStitching.Tesselation;
--The geometry worlds contain the flattened regions where conflicts occour.
ConstraintQueue: TYPE = ARRAY SX.SpinifexLayerIndex OF LIST OF REF CornerStitching.Region ← ALL[NIL];
--The following two data structures are global for maintenance purposes.
conflictWorlds: ConflictWorlds;
--The conflict worlds are used to find the regions where interactions occour.
geometryWorlds: GeometryWorlds;
--The geometry worlds contain the flattened regions where conflicts occour.
--Maintenance aids
debug:
BOOL =
FALSE;
debugQT: BOOL = FALSE;
debugFullQT: BOOL ← FALSE;
delinquent: CD.Rect = [x1: 10, y1: 48, x2: 18, y2: 56];
saveTesselations: BOOL ← FALSE;
freeTesselations: BOOL ← FALSE;
PROCEDURES FOR FIRST PER LAYER LOOP
BloatConflictsIntoAOIs:
PROC [
cir:
REF
SX.Circuit,
layer: SX.SpinifexLayerIndex,
conflictWorld:
REF CornerStitching.Tesselation]
--All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
RETURNS [cleanedConflictWorld: REF CornerStitching.Tesselation] =
BEGIN
--Local of AnalyzeGeometry, First Per Layer LOOP (AOI = Area Of Interest)
CopyBloated: CornerStitching.PerTileProc =
BEGIN
--[tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY]
IF tile.Value=$Conflict
THEN {
cleanedConflicts.ChangeRect[
rect: CDBasics.Extend[tile.Area, bloatValue],
newValue: $AOI
];
}
END; -- CopyBloated
--BloatConflictsIntoAOIs (AOI = Area Of Interest)
bloatValue: INT ← SXAccess.sxTech.layerInterestBloat[layer];
cleanedConflicts: REF CornerStitching.Tesselation ← CornerStitching.NewTesselation[];
[] ← conflictWorld.EnumerateArea[cir.spinifexLayers[layer].size, CopyBloated];
conflictWorld.FreeTesselation[FALSE];
cleanedConflictWorld ← cleanedConflicts;
END; -- BloatConflictsIntoAOIs
InstantiateAOIs:
PROC [
cir:
REF SX.Circuit,
qt:
REF SXQuadTree.QuadTree,
cellBBox:
CD.Rect,
flatLoc:
CD.Position ← [0, 0],
flatOrient:
CD.Orientation ← CDOrient.original,
appl:
CD.Instance ←
NIL,
nameQualifier:
LIST
OF
CD.Instance ←
NIL,
layer: SX.SpinifexLayerIndex,
conflictWorld:
REF CornerStitching.Tesselation,
geometryWorld:
REF CornerStitching.Tesselation,
constraintQueue: ConstraintQueue]
RETURNS [newConstraintQueue: ConstraintQueue] =
BEGIN
--Local of AnalyzeGeometry, First Per Layer LOOP (AOI = Area Of Interest)
--Depth first instantiation of those regions of the hierarchy that were found to be interesting.
InstantiateTree:
PROC [qt:
REF SXQuadTree.QuadTree, qtBranchBox:
CD.Rect] =
BEGIN
EnqueueConstraintRegion:
PROC [cc:
REF
SX.Constraint, r: CornerStitching.Rect] =
BEGIN
constraintQueue[layer] ←
CONS[
NEW[CornerStitching.Region ← [rect: r, value: cc]],
constraintQueue[layer]
]
END;
InstantiateTree
IF conflictWorld.AreaEmpty[CDOrient.MapRect[
itemInCell: qtBranchBox,
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc
]] THEN RETURN;
IF debug THEN TerminalIO.WriteChar['i];
FOR boxes: SXQuadTree.Rectangles ← qt.boxes, boxes.rest
WHILE boxes#
NIL
DO
mappedDim:
CD.Rect = CDOrient.MapRect[
itemInCell: SXQuadTree.Dimension[boxes.first],
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc
];
IF
NOT conflictWorld.AreaEmpty[mappedDim]
THEN {
WITH boxes.first.nodeInformation
SELECT
FROM
subAppl:
CD.Instance => {
cellQt: REF SXQuadTree.QuadTree;
subcellBBox: CD.Rect;
[size: subcellBBox, geometry: cellQt] ← SXAccessInternal.GetSXData[subAppl.ob].circuit.spinifexLayers[layer];
IF cellQt=NIL THEN LOOP;
constraintQueue ← InstantiateAOIs[
qt: cellQt,
cellBBox: subcellBBox,
flatLoc: CDBasics.BaseOfRect[CDOrient.MapRect[
itemInCell: CDOrient.RectAt[pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation],
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc
]],
flatOrient: CDOrient.ComposeOrient[itemOrientInCell: subAppl.orientation, cellOrientInWorld: flatOrient],
appl: subAppl,
nameQualifier: CONS[subAppl, nameQualifier],
--following are the parameters added in the restructuration:
cir: cir,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue
];
}; -- end rectangle is a subcell
cNode:
REF
SX.CircuitNode => {
name:
REF
SX.CircuitNode =
--nameQualifier is not NIL when this node comes from a subcell of the cell currently being processed.
IF nameQualifier=NIL THEN cNode
ELSE cir.FindRootNode[subcircuitNode: cNode, qualifier: nameQualifier, insertIfNotInCircuit: TRUE].node;
occupants: LIST OF REF CornerStitching.Region ← NARROW[geometryWorld.EnumerateArea[mappedDim] ];
newList: LIST OF REF SX.CircuitNode ← LIST[name];
geometryWorld.ChangeRect [rect: mappedDim, newValue: newList];
WHILE occupants#
NIL
DO
IF ~conflictWorld.AreaEmpty[occupants.first.rect]
THEN
WITH occupants.first.value
SELECT
FROM
oldList:
LIST
OF
REF
SX.CircuitNode =>
-- oldList forms shared tail in all multiply occupied areas. Subsequent processing allows this. We must ensure that each node appears only once and that the list head is unique.
IF ~(oldList.first = name
AND oldList.rest=
NIL)
THEN {
old: LIST OF REF SX.CircuitNode ← oldList;
replaceList: LIST OF REF SX.CircuitNode;
WHILE old#
NIL
DO
-- check not already on list.
IF old.first = name THEN EXIT;
old ← old.rest;
ENDLOOP;
replaceList ←
IF old#
NIL
THEN
CONS[oldList.first, oldList.rest]
ELSE CONS[name, oldList];
geometryWorld.ChangeRect[rect: occupants.first.rect, newValue: replaceList]
};
ENDCASE => ERROR;
occupants ← occupants.rest;
ENDLOOP;
}; -- end rectangle is a node
cc: REF SX.Constraint => EnqueueConstraintRegion[cc, mappedDim];
ENDCASE => ERROR -- This type not expected in quad tree
}
ENDLOOP; -- instantiate all rectangles in this Quad Tree node
{
IF qt.subTrees[north] #
NIL
THEN
InstantiateTree[qt.subTrees[north],
[x1: qtBranchBox.x1, y1: qt.midY, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[south] #
NIL
THEN
InstantiateTree[qt.subTrees[south],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qt.midY]];
IF qt.subTrees[east] #
NIL
THEN
InstantiateTree[qt.subTrees[east],
[x1: qt.midX, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[west] #
NIL
THEN
InstantiateTree[qt.subTrees[west],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qt.midX, y2: qtBranchBox.y2]];
}
END; -- InstantiateTree
Main of InstantiateAOIs
IF debug THEN TerminalIO.WriteChar['a];
InstantiateTree[qt, cellBBox];
newConstraintQueue ← constraintQueue
END; -- InstantiateAOIs
Called in the first per layer loop.
AnalyzeNodesInAOIs:
PROC [
cir:
REF SX.Circuit,
layer: SX.SpinifexLayerIndex,
geometryWorld:
REF CornerStitching.Tesselation] =
--The nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
BEGIN
MergeNodeTiles: CornerStitching.PerTileProc =
--[tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] --
BEGIN
--(local of AnalyzeNodesInAOIs, local of AnalyzeGeometry)
-- This is quite an embarassment to me, but ...
-- This code deals with area and perimeter calculation, perhaps it could be done better. I could think of two ways to do this, neither of them particularly great. I chose to implement the one I understood best although it is perhaps the less efficient of the two. Each cornersitched tile is a list of CircuitNodes which had tiles in the area, think of them as the set of sources for any tile. I'm sure with a bit more time someone could come up with a better way to represent these sets than lists, however it should not be too bad as I expect the list will only ever contain a couple of members. Just be warned that pathological behaviour may arise. Note the length of source lists is precisely the degree of overlap of boxes with the proviso that subcells only contribute one box. Actually it hasn't turned out too badly.
CountEdge:
PROC [nl1, nl2:
LIST
OF
REF SX.CircuitNode]
RETURNS [
INT] =
BEGIN
-- There is an edge for every SX.CircuitNode not shared by the two lists.
InAButNotB:
PROC [a,b:
LIST
OF
REF SX.CircuitNode]
RETURNS [c:
INT ← 0] =
BEGIN
FOR s1:
LIST
OF
REF SX.CircuitNode ← a, s1.rest
WHILE s1#
NIL
DO
s2: LIST OF REF SX.CircuitNode ← b;
WHILE s2#
NIL
DO
IF s1.first=s2.first THEN EXIT; -- Shared sources.
s2 ← s2.rest;
ENDLOOP;
IF s2=NIL THEN c ← c+1; -- node in s1 not in s2
ENDLOOP;
END;
RETURN [InAButNotB[a: nl1, b: nl2] + InAButNotB[a: nl2, b: nl1]]
END; -- CountEdge
--MergeNodeTiles
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
WITH tile.Value
SELECT
FROM
cnList:
LIST
OF
REF SX.CircuitNode => {
-- Process merging and area changes in the interior of the tile.
list: LIST OF REF SX.CircuitNode ← cnList.rest;
eastBound: INT = tile.EastEdge;
northBound: INT = tile.NorthEdge;
westBound: INT = tile.WestEdge;
southBound: INT = tile.SouthEdge;
r: CD.Rect = tile.Area;
extraNodes: INT ← 0;
n1: REF SX.CircuitNode = SX.LookupNode[cnList.first];
WHILE list#
NIL
DO
n2: REF SX.CircuitNode = SX.LookupNode[list.first];
IF n1#n2 THEN cir.MergeNode[to: n1, from: n2];
-- Area adjustment.
SX.AdjustNode[node: n1, layer: layer, area: -((r.x2 - r.x1)*(r.y2 - r.y1)), perim: 0];
extraNodes ← extraNodes+1;
list ← list.rest;
ENDLOOP;
-- Process merging and perim changes at the tile southern and western boundary.
-- To do this we must count the number of edges at each tile-pair boundary.
FOR tileSouth: CornerStitching.TilePtr ← tile.WSouthNeighbour, tileSouth.NEastNeighbour
WHILE tileSouth.WestEdge < eastBound
DO
IF tileSouth.Value#
NIL
THEN
WITH tileSouth.Value
SELECT
FROM
cnSouthList:
LIST
OF
REF SX.CircuitNode => {
n2: REF SX.CircuitNode = SX.LookupNode[cnSouthList.first];
IF n1#n2 THEN cir.MergeNode[to: n1, from: n2];
SX.AdjustNode[
node: n1,
layer: layer,
area: 0,
perim: -(CountEdge[cnList, cnSouthList] * (MIN[eastBound, tileSouth.EastEdge] - MAX[westBound, tileSouth.WestEdge]) )
]
};
constraint: REF SX.Constraint => NULL; -- Ignore
ENDCASE => ERROR
ELSE --
tileSouth.Value=NIL
IF extraNodes > 0
THEN
SX.AdjustNode[node: n1, layer: layer, area: 0,
perim: -(extraNodes * (MIN[eastBound, tileSouth.EastEdge] - MAX[westBound, tileSouth.WestEdge]) )
]
ENDLOOP; -- end FOR tileSouth
FOR tileWest: CornerStitching.TilePtr ← tile.SWestNeighbour, tileWest.ENorthNeighbour
WHILE tileWest.SouthEdge < northBound
DO
IF tileWest.Value#
NIL
THEN
WITH tileWest.Value
SELECT
FROM
cnWestList:
LIST
OF
REF SX.CircuitNode => {
n2: REF SX.CircuitNode;
IF n1#(n2←SX.LookupNode[cnWestList.first])
THEN
cir.MergeNode[to: n1, from: n2];
SX.AdjustNode[node: n1, layer: layer, area: 0,
perim: -(CountEdge[cnList, cnWestList] * (MIN[northBound, tileWest.NorthEdge] - MAX[southBound, tileWest.SouthEdge]) )
]
};
constraint: REF SX.Constraint => NULL; -- Ignore
ENDCASE => ERROR
ELSE
IF extraNodes > 0
THEN
SX.AdjustNode[node: n1, layer: layer, area: 0,
perim: -(extraNodes * (MIN[northBound,tileWest.NorthEdge] - MAX[southBound,tileWest.SouthEdge]) )
]
ENDLOOP; -- tileWest
FOR tileNorth: CornerStitching.TilePtr ← tile.ENorthNeighbour, tileNorth.SWestNeighbour
WHILE tileNorth.EastEdge > westBound
DO
IF tileNorth.Value=NIL
AND extraNodes > 0
THEN
SX.AdjustNode[node: n1, layer: layer, area: 0,
perim: -(extraNodes * (MIN[eastBound, tileNorth.EastEdge] - MAX[westBound, tileNorth.WestEdge]) )
]
ENDLOOP; -- tileNorth
FOR tileEast: CornerStitching.TilePtr ← tile.NEastNeighbour, tileEast.WSouthNeighbour
WHILE tileEast.NorthEdge > southBound
DO
IF tileEast.Value=NIL
AND extraNodes > 0
THEN
SX.AdjustNode[node: n1, layer: layer, area: 0,
perim: -(extraNodes * (MIN[northBound, tileEast.NorthEdge] - MAX[southBound, tileEast.SouthEdge]) )
]
ENDLOOP; -- tileEast
};
ENDCASE => ERROR
END; -- MergeNodeTiles
--AnalyzeNodesInAOIs.
[] ← geometryWorld.EnumerateArea[rect: cir.spinifexLayers[layer].size, perTile: MergeNodeTiles];
END; -- AnalyzeNodesInAOIs
PROCEDURES FOR THIRD PER LAYER LOOP
DesignRuleCheckAOIs:
PROC [
cir:
REF SX.Circuit,
cell:
REF SX.LogicalCell,
constraintQueue: ConstraintQueue,
layer: SX.SpinifexLayerIndex,
geometryWorld:
REF CornerStitching.Tesselation,
conflictWorld:
REF CornerStitching.Tesselation] =
BEGIN
--Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
Tile types: Space (0), Current (1), SX.Constraint (2-7).
--Each rule has two boolean vectors:
--trigger1 identifies whether it is really a corner and gives the orientation.
--trigger2 gives the checking rectangle.
--CornerStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
-- First add the constraint regions to the geometry.
mixRef: REF MixRec = NEW[MixRec]; --used to transfer parameters to MixConstraints
checkRef: REF CheckRec = NEW[CheckRec]; --used to transfer parameters to CheckTile
FOR newCc:
LIST
OF
REF CornerStitching.Region ← constraintQueue[layer], newCc.rest
WHILE newCc#NIL DO
mixRef^ ← [
--parameters of MixConstraints
newConstraint: NARROW[newCc.first.value],
rect: newCc.first.rect,
resolution: SXAccess.sxTech.constraintResolutions[layer],
tilesToPaint: NIL
];
[] ← geometryWorld.EnumerateArea[rect: mixRef.rect, perTile: MixConstraints, backgroundValue: $Nothing, data: mixRef];
FOR tilesToPaint:
LIST
OF
REF CornerStitching.Region
← mixRef.tilesToPaint, tilesToPaint.rest WHILE tilesToPaint#NIL DO
geometryWorld.ChangeRect[rect: tilesToPaint.first.rect, newValue: tilesToPaint.first.value];
ENDLOOP; --tilesToPaint
ENDLOOP; --newCc
-- examine every tile
checkRef^ ← [
--parameters of CheckTile
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
cell: cell,
cir: cir,
rules: SXAccess.sxTech.rules[layer]
];
[] ← geometryWorld.EnumerateArea[
rect: cir.spinifexLayers[layer].size,
perTile: CheckTile,
backgroundValue: $Nothing,
data: checkRef
];
END; -- DesignRuleCheckAOIs
--type MixRec used exclusively to pass parameters to MixConstraints
MixRec:
TYPE =
RECORD [
newConstraint: REF SX.Constraint,
rect: CD.Rect,
resolution: REF SX.ConstraintResolution,
tilesToPaint: LIST OF REF CornerStitching.Region
];
MixConstraints: CornerStitching.PerTileProc =
--called from DesignRuleCheckAOIs only
--[tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY]
BEGIN
mixRef: REF MixRec = NARROW[data];
newval: REF ANY ← mixRef.newConstraint;
IF tile.Value =
NIL
OR
tile.Value # (newval ← SXConflicts.ResolveConstraints[
mixRef.newConstraint, tile.Value, mixRef.resolution
])
THEN
mixRef.tilesToPaint ←
CONS[
NEW[CornerStitching.Region ← [
rect: CDBasics.Intersection[mixRef.rect, tile.Area],
value: newval
]],
mixRef.tilesToPaint
]
END; -- MixConstraints
--type CheckRec used exclusively to pass parameters to CheckTile
CheckRec:
TYPE =
RECORD [
conflictWorld: REF CornerStitching.Tesselation,
geometryWorld: REF CornerStitching.Tesselation,
rules: LIST OF REF SX.GeometricRule,
cell: REF SX.LogicalCell,
cir: REF SX.Circuit
];
FindNode:
PROC [handle:
REF CheckRec, nodeLayer: SX.SpinifexLayerIndex, r:
CD.Rect]
RETURNS [
REF
ANY] =
--logically local to CheckTile
BEGIN
node: REF SX.CircuitNode;
FoundIt: SIGNAL [n: REF SX.CircuitNode];
{
ENABLE FoundIt => {
node ← n;
GOTO Done
};
FindNodeInner:
PROC [circuit:
REF SX.Circuit, rect:
CD.Rect, aChain:
LIST
OF
CD.Instance] =
--(local of FindNode, local of DesignRuleCheckAOIs, local of AnalyzeGeometry)
BEGIN
SearchForNode: SXQuadTree.PerRectProc =
--[r: REF SXQuadTree.Rectangle, data: REF ANY] --
--(local of FindNodeInner, local of FindNode, local of DesignRuleCheckAOIs, local of AnalyzeGeometry)
BEGIN
WITH r.nodeInformation
SELECT
FROM
n:
REF SX.CircuitNode =>
IF CDBasics.Intersect[r.Dimension, rect]
THEN {
parentNode: REF SX.CircuitNode;
newChain: LIST OF CD.Instance;
[parentNode, newChain] ← handle.cir.FindRootNode[n, aChain];
IF newChain=NIL THEN SIGNAL FoundIt[parentNode]
};
a:
CD.Instance => {
--Compose Clip and recurse
subcir: REF SX.Circuit = SXAccessInternal.GetSXData[a.ob].circuit;
subR:
CD.Rect = CDOrient.DeMapRect[
itemInWorld: rect,
cellSize: a.ob.size,
cellInstOrient: a.orientation,
cellInstPos: a.location
];
FindNodeInner[subcir, subR, CONS[a, aChain]];
};
ENDCASE;
END; -- SearchForNode
--FindNodeInner
SXQuadTree.Enumerate [circuit.spinifexLayers[nodeLayer], rect, SearchForNode, NIL]
END; -- FindNodeInner
FindNodeInner[handle.cir, r, NIL];
RETURN [NEW[INT]];
EXITS Done => RETURN [node];
}
END; -- FindNode
CheckTile: CornerStitching.PerTileProc =
--[tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] --
--called from DesignRuleCheckAOIs only
BEGIN
Quadrants: TYPE = {ne, nw, sw, se};
DesignRuleCheckCorner:
PROC [quadVals:
ARRAY Quadrants
OF
REF
ANY, pos:
CD.Position] =
BEGIN
CheckArea:
PROC [rule:
REF
SX.GeometricRule, orient:
CD.Orientation, flavour: { convex, concave}] =
BEGIN
FindNodeAtCorner:
PROC [n:
REF
ANY]
RETURNS [
REF
ANY] =
BEGIN
WITH n
SELECT
FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc:
REF SX.Constraint => {
IF cc.specificCorrespondingNode # NIL THEN RETURN[SX.LookupNode[cc.specificCorrespondingNode]]; --Bowers, September 4, 1985 2:10:58 pm PDT
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeAtCorner: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, CDBasics.Extend[CDBasics.ToRect[pos, pos], 1]] ]
};
ENDCASE => RETURN [NEW[INT]];
END;
FindNodeInTile:
PROC [n:
REF
ANY, area:
CD.Rect]
RETURNS [
REF
ANY] =
BEGIN
WITH n
SELECT
FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc:
REF SX.Constraint => {
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeInTile: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, area]]
};
ENDCASE => RETURN [NEW[INT]];
END;
CheckTileValue: CornerStitching.PerTileProc =
--PROC [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY]
BEGIN
CheckValue[tile.Value, tile.Area]
END;
CheckValue:
PROC [value:
REF
ANY, area:
CD.Rect] =
BEGIN
--Each rule has two boolean vectors:
--trigger1 identifies whether it is really a corner and gives the orientation.
--trigger2 gives the checking rectangle.
--CornerStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
--(local of CheckArea, local of DesignRuleCheckCorner, local of DesignRuleCheckAOIs, local of AnalyzeGeometry)
WriteRectangle: PROCEDURE [r: CD.Rect] =
Writes the coordinates of a rectangle on the screen.
BEGIN
TerminalIO.WriteRope ["x1, y1, x2, y2: "];
TerminalIO.WriteInt [r.x1]; TerminalIO.WriteInt [r.y1];
TerminalIO.WriteInt [r.x2]; TerminalIO.WriteInt [r.y2]
END; -- WriteRectangle
WriteNodeLoc: PROCEDURE [l: SX.NodeLocation] =
BEGIN
TerminalIO.WriteRope ["x, y, layer: "];
TerminalIO.WriteInt [l.xy.x]; TerminalIO.WriteInt [l.xy.y];
TerminalIO.WriteInt [l.layer]
END; -- WriteNodeLoc
WriteAny: PROCEDURE [any: REF ANY] =
BEGIN
WITH any SELECT FROM
cn: REF SX.CircuitNode => {
TerminalIO.WriteRope [" Node at "]; WriteNodeLoc [cn.loc]
};
cc: REF SX.Constraint => TerminalIO.WriteRope [" Constraint."];
ENDCASE => IF any = NIL THEN TerminalIO.WriteRope [" NIL"]
ELSE TerminalIO.WriteRope [" Not node nor constraint."];
END; -- WriteAny
WriteNode: SXQuadTree.PerRectProc =
Writes the node contents
BEGIN
WriteRectangle [r.interestBound];
WriteAny [r.nodeInformation];
TerminalIO.WriteLn
END; -- WriteNode
DumpTree: PUBLIC PROCEDURE [quadTree: SXQuadTree.QuadTreeRoot] =
Writes all nodes of a tree.
BEGIN
SXQuadTree.Enumerate [quadTree, area, WriteNode, NIL]
END; -- DumpTree
DebugQT: PROCEDURE =
Interim
BEGIN
trueArea: CD.Rect = area;
IF debugFullQT THEN area ← CDBasics.universe;
TerminalIO.WriteRope ["Area: "]; WriteRectangle [area];
TerminalIO.WriteRope [". Node at corner: "]; WriteAny [nodeAtCorner];
TerminalIO.WriteRope [". Value: "]; WriteAny [value];
TerminalIO.WriteLn;
WITH value SELECT FROM
cn: REF SX.CircuitNode => {
TerminalIO.WriteRope ["Was searching node at corner"];
TerminalIO.WriteLn;
WITH nodeAtCorner SELECT FROM
n: REF SX.CircuitNode => NULL;
c: REF SX.Constraint => DumpTree [handle.cir.spinifexLayers[c.correspondingNodeLayer]];
ENDCASE => NULL;
};
cc: REF SX.Constraint => {
TerminalIO.WriteRope ["Was searching node in tile"];
TerminalIO.WriteLn;
DumpTree [handle.cir.spinifexLayers[cc.correspondingNodeLayer]]
};
ENDCASE => NULL;
area ← trueArea
END; -- DebugQT
IF SXAccess.stopFlag^
THEN
ERROR
ABORTED;
IF debugQT AND IsDelinquent[area] THEN {
TerminalIO.WriteRope ["\n Tracing delinquent.\n"]; DebugQT};
WITH value
SELECT
FROM
cn:
REF SX.CircuitNode => {
IF ~rule.trigger2[SX.nodeIndex] THEN RETURN;
IF (rule.okIfConnected
AND nodeAtCorner#
NIL
AND FindNodeAtCorner[nodeAtCorner] =
SX.LookupNode[cn])
THEN
RETURN;
};
cc:
REF SX.Constraint => {
IF ~rule.trigger2[cc.index] THEN RETURN;
IF (rule.okIfConnected
AND nodeAtCorner#
NIL
AND cc.hasCorrespondingNode
AND FindNodeAtCorner[nodeAtCorner] = FindNodeInTile[cc, area]
OR
(cc.specificCorrespondingNode # NIL AND FindNodeAtCorner[nodeAtCorner] = SX.LookupNode[cc.specificCorrespondingNode])) THEN
RETURN;
};
cnList:
LIST
OF
REF SX.CircuitNode => {
--this case introduced by Ch. Jacobi, January 3, 1985 11:28:01 am PST
--without understanding the consequences and why a list type is used here
IF cnList.rest#NIL THEN CD.Error[ec: other, explanation: "CheckValue: found a list of circuit nodes where a single one was expected"];
IF ~rule.trigger2[SX.nodeIndex] THEN RETURN;
IF (rule.okIfConnected
AND nodeAtCorner#
NIL
AND FindNodeAtCorner[nodeAtCorner] =
SX.LookupNode[cnList.first])
THEN
RETURN;
};
ENDCASE => {
IF value=
NIL
THEN {
IF ~rule.trigger2[SX.spaceIndex] THEN RETURN;
}
ELSE CD.Error[ec: other, explanation: "CheckValue: value # NIL"]
};
-- Check it is really an error. (Kind of funny sort of empty!
What we mean is empty of non-$AOI tiles)
IF notReportedYet
AND conflictWorld.AreaEmpty[
rect: CDOrient.MapRect[
itemInCell: [x1: -delta, y1: -delta, x2: len, y2: len],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos
],
backgroundValue: $AOI] THEN {
-- FOUND AN ERROR
IF debugQT THEN {
TerminalIO.WriteRope ["\n Found an error for rule "];
TerminalIO.WriteRope [rule.message]; TerminalIO.WriteLn;
DebugQT
};
SXAccessInternal.PutError[ob: handle.cell.cellObj,
r: CDOrient.MapRect[
itemInCell: [x1: 0, y1: 0, x2: rule.extent, y2: rule.extent],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos
],
message: rule.message
];
notReportedYet ← FALSE
}
END; -- CheckValue
notReportedYet: BOOLEAN ← TRUE;
len: INT = rule.extent;
delta: INT = 1;
IF len = 0
THEN {
-- Optimize purely local checks.
IF notReportedYet THEN
CheckValue[quadVals[ne], [pos.x, pos.y, pos.x+delta, pos.y+delta]];
IF notReportedYet
THEN
CheckValue[quadVals[nw], [pos.x, pos.y-delta, pos.x+delta, pos.y]];
IF notReportedYet
THEN
CheckValue[quadVals[sw], [pos.x-delta, pos.y-delta, pos.x, pos.y]];
IF notReportedYet
THEN
CheckValue[quadVals[se], [pos.x-delta, pos.y, pos.x, pos.y+delta]];
}
ELSE {
SELECT flavour
FROM
convex => {
[] ← handle.geometryWorld.EnumerateArea[
rect: CDOrient.MapRect[itemInCell: [x1: -delta, y1: 0, x2: len, y2: len],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos
],
perTile: CheckTileValue,
backgroundValue: $Nix
];
[] ← handle.geometryWorld.EnumerateArea[
rect: CDOrient.MapRect[itemInCell: [x1: 0, y1: -delta, x2: len, y2: 0],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos
],
perTile: CheckTileValue,
backgroundValue: $Nix
];
};
concave => {
[] ← handle.geometryWorld.EnumerateArea[
rect: CDOrient.MapRect[itemInCell: [x1: 0, y1: 0, x2: len, y2: len],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos
],
perTile: CheckTileValue,
backgroundValue: $Nix
];
};
ENDCASE
}
END; -- CheckArea
-- DesignRuleCheckCorner
or0: CD.Orientation = CDOrient.original;
or90: CD.Orientation = CDOrient.rotate90;
or180: CD.Orientation = CDOrient.rotate180;
or270: CD.Orientation = CDOrient.rotate270;
nodeAtCorner: REF ANY ← NIL;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR ruleList:
LIST
OF
REF SX.GeometricRule ← handle.rules, ruleList.rest
WHILE ruleList#
NIL
DO
rule: REF SX.GeometricRule = ruleList.first;
bitIndex: ARRAY Quadrants OF INTEGER = [8, 4, 2, 1];
quadBits: INTEGER ← 0;
nodeAtCorner ← NIL;
-- Translate the quadrant contents into bit vector values.
FOR q: Quadrants
IN Quadrants
DO
WITH quadVals[q]
SELECT
FROM
cn:
REF SX.CircuitNode => {
IF rule.trigger1[SX.nodeIndex]
THEN {
quadBits ← quadBits + bitIndex[q];
nodeAtCorner ← cn
}
};
cc:
REF SX.Constraint => {
IF rule.trigger1[cc.index]
THEN {
quadBits ← quadBits + bitIndex[q];
IF cc.hasCorrespondingNode AND nodeAtCorner=NIL THEN nodeAtCorner ← cc
}
};
cnList:
LIST
OF
REF SX.CircuitNode => {
CD.Error[ec: other, explanation: "DesignRuleCheckCorner: 'LIST OF REF SX.CircuitNode' should have been squashed to 'REF SX.CircuitNode' in `AnalyzeNodesInAOIs'.\nPLEASE save a copy of this design and make it available to Giordano. Thanks"]
--this case introduced by Ch. Jacobi, January 3, 1985 11:28:01 am PST
--without understanding the consequences and why a list type is used here
-- ... and deleted again by Mark Shand February 15, 1985 12:08:02 pm PST
IF rule.trigger1[SX.nodeIndex] THEN {
quadBits ← quadBits + bitIndex[q];
nodeAtCorner ← cnList.first;
IF cnList.rest#NIL THEN CD.Error[ec: other, explanation: "DesignRuleCheckCorner: cnList.rest#NIL"];
};
};
ENDCASE => {
IF quadVals[q]=
NIL
THEN {
IF rule.trigger1[SX.spaceIndex] THEN quadBits ← quadBits + bitIndex[q]
}
ELSE CD.Error[ec: other, explanation: "DesignRuleCheckCorner: quadVals[q]#NIL"]
};
ENDLOOP; -- end Translate the quadrant contents into bit vector values
-- Is this really a corner in the terms of this rule?
-- Bits are ne=8, nw=4, sw=2, se=1. The check is applied to the quad opposite the generating corner. (IE rot. 180)
-- Here are are some diagrams to make it explicit, X=TRUE, O=FALSE
0 - OO 1 - OO 2 - OO 3 - OO
OO OX XO XX
4 - XO 5 - XO 6 - XO 7 - XO
OO OX XO XX
8 - OX 9 - OX 10- OX 11- OX
OO OX XO XX
12- XX 13- XX 14- XX 15- XX
OO OX XO XX
SELECT quadBits
FROM
0 => NULL;
1 => CheckArea[rule, or90, convex];
2 => CheckArea[rule, or0, convex];
3 => NULL;
4 => CheckArea[rule, or270, convex];
5 => { CheckArea[rule, or90, convex]; CheckArea[rule, or270, convex] };
6 => NULL;
7 => CheckArea[rule, or0, concave];
8 => CheckArea[rule, or180, convex];
9 => NULL;
10 => { CheckArea[rule, or0, convex]; CheckArea[rule, or180, convex] };
11 => CheckArea[rule, or90, concave];
12 => NULL;
13 => CheckArea[rule, or180, concave];
14 => CheckArea[rule, or270, concave];
15 => NULL;
ENDCASE => ERROR;
ENDLOOP;
END; -- DesignRuleCheckCorner
--CheckTile
-- Since tile are stitched at their North-East and South-West corners these are favoured points from which to DRC. We exploit the fact that every corner has either 3 or (rarely) 4 edges meeting at it, and thus contains a NE or SW or (rarely) both tile corner at it.
handle: REF CheckRec = NARROW[data];
conflictWorld: REF CornerStitching.Tesselation = handle.conflictWorld;
tileBound: CD.Rect = tile.Area;
-- SW corner
IF conflictWorld.TileAt[[x: tileBound.x1, y: tileBound.y1]].Value = $AOI
THEN {
IF tile.SWestNeighbour.SouthEdge = tileBound.y1
THEN {
IF tile.WSouthNeighbour.WestEdge = tileBound.x1 THEN NULL -- This is a (rare I suspect) 4 way corner it is handled at the NE corner.
ELSE {
IF tile.Value = tile.SWestNeighbour.Value
THEN
CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule"];
-- Get the quadrants at the SW corner and call DesignRuleCheckCorner
DesignRuleCheckCorner[
[ne: tile.Value, nw: tile.SWestNeighbour.Value, sw: tile.WSouthNeighbour.Value, se: tile.WSouthNeighbour.Value],
[tileBound.x1, tileBound.y1]
];
}
}
ELSE {
-- tile.WSouthNeighbour.WestEdge = tileBound.x1 IMPLICITLY
IF tile.Value = tile.WSouthNeighbour.Value THEN NULL -- No corner really
ELSE {
-- Get the quadrants at the SW corner and call DesignRuleCheckCorner
DesignRuleCheckCorner[
[ne: tile.Value, nw: tile.SWestNeighbour.Value, sw: tile.SWestNeighbour.Value, se: tile.WSouthNeighbour.Value],
[tileBound.x1, tileBound.y1]
];
}
}
};
-- NE corner
IF conflictWorld.TileAt[[x: tileBound.x2, y: tileBound.y2]].Value = $AOI
THEN {
IF tile.NEastNeighbour.NorthEdge = tileBound.y2
THEN {
IF tile.ENorthNeighbour.EastEdge = tileBound.x2
THEN {
-- 4 way corner, damn it
neQTile: CornerStitching.TilePtr ← tile.ENorthNeighbour.NEastNeighbour;
WHILE neQTile.SouthEdge > tileBound.y2
DO
neQTile ← neQTile.WSouthNeighbour;
ENDLOOP;
DesignRuleCheckCorner[
[ne: neQTile.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value],
[tileBound.x2, tileBound.y2]
];
}
ELSE {
IF tile.Value = tile.NEastNeighbour.Value
THEN
CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule NEast"];
-- Get the quadrants at the NE corner and call DesignRuleCheckCorner
DesignRuleCheckCorner[
[ne: tile.ENorthNeighbour.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value],
[tileBound.x2, tileBound.y2]
];
}
}
ELSE {
-- tile.ENorthNeighbour.EastEdge = tileBound.x2 IMPLICITLY
IF tile.Value = tile.ENorthNeighbour.Value THEN NULL -- No corner really
ELSE {
-- Get the quadrants at the NE corner and call DesignRuleCheckCorner
DesignRuleCheckCorner[
[ne: tile.NEastNeighbour.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value],
[tileBound.x2, tileBound.y2]
];
}
}
}
END; -- CheckTile
AnalyzeGeometry:
PUBLIC
PROC [cell:
REF
SX.LogicalCell] =
BEGIN
cir: REF SX.Circuit = cell.circuit;
--Process each of the analysis layers.
constraintQueue: ConstraintQueue;
IF freeTesselations THEN FreeTesselations[circuit: cir];
--First per layer LOOP. The quad-trees are enumerated and the conflict world is constructed. Then the areas of interest are bloated. Finally the quad-tree is instantiated into the geometry world and the nodes are analysed.
IF debug THEN TerminalIO.WriteChar['1];
FOR layer: SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
conflictWorld: REF CornerStitching.Tesselation ← conflictWorlds[layer] ← CornerStitching.NewTesselation[];
geometryWorld: REF CornerStitching.Tesselation ← geometryWorlds[layer] ← CornerStitching.NewTesselation[];
--Main Body of first Per Layer LOOP (FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO)
cir.spinifexLayers[layer] ← SXQuadTree.Create [cir.spinifexLayers[layer]];
IF cir.spinifexLayers[layer].geometry = NIL THEN LOOP;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
SXConflicts.ComputeConflicts[cir.spinifexLayers[layer].geometry, conflictWorld, layer, cir];
--The quad-trees are enumerated and the conflict world is constructed. Each rectangle has an area of interest depending on the material. Constraints do not overlap: they are ordered into the technology dependent part; the larger prevails. Every constraint is represented by a number which is an index in a boolean array to infere whether it is there.
--Set break point here to look at the conflict world !
--CSMonitor.Monitor [plane: conflictWorld, name: "conflictWorld", paintDark: NIL];
TerminalIO.WriteChar['.];
conflictWorld ← conflictWorlds[layer] ← BloatConflictsIntoAOIs[cir, layer, conflictWorld];
--All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
TerminalIO.WriteChar['.];
--The quad-tree is instantiated into the geometry world. This is done in two steps, because a tile can have only one value. First the electrical carrying stuff is handled, then the constraints.
constraintQueue ← InstantiateAOIs[
cir: cir,
qt: cir.spinifexLayers[layer].geometry,
cellBBox: cir.spinifexLayers[layer].size,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue
];
TerminalIO.WriteChar['.];
IF debug THEN TerminalIO.WriteChar['n];
--Now the nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
AnalyzeNodesInAOIs [cir, layer, geometryWorld];
TerminalIO.WriteRope [". "];
ENDLOOP; -- end of FOR "layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO"
--Second Per Layer LOOP. For each conductive region in the geometry worlds, change the "LIST OF REF SX.CircuitNode"s (which have already been compressed into a single node per region) to a REF SX.CircuitNode. Normalises the geometrical representation of nodes (All electrically connected regions are made to point to the same node [which was determined in `AnalyzeNodesInAOIs']).
(rewrite using FuncChangeRect)
IF debug THEN TerminalIO.WriteChar['2];
--The loop in plain text:
--for every Spinifex layer
--for every rectangle of material in the design
--get the list of the electrically connected rectangles in the circuit
--collapse the attributes (value) of all rectangle to a single instance of the attributes
--transform the list consisting of a single element in a single element (attributes).
FOR layer:
SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
geometryWorld: REF CornerStitching.Tesselation ← geometryWorlds[layer];
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR tiles:
LIST
OF
REF CornerStitching.Region ←
NARROW[geometryWorld.EnumerateArea[rect: cir.spinifexLayers[layer].size]], tiles.rest
WHILE tiles#
NIL
DO
geometryWorld.ChangeRect [rect: tiles.first.rect, newValue: SX.LookupNode[NARROW[tiles.first.value, LIST OF REF SX.CircuitNode].first ]]
ENDLOOP;
TerminalIO.WriteChar['.];
ENDLOOP; -- second Per Layer LOOP
SX.NormalizeCircuit[cir];
TerminalIO.WriteChar[' ];
--Third per layer LOOP. Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
IF debug THEN TerminalIO.WriteChar['3];
FOR layer: SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
conflictWorld: REF CornerStitching.Tesselation ← conflictWorlds [layer];
geometryWorld: REF CornerStitching.Tesselation ← geometryWorlds [layer];
DesignRuleCheckAOIs [cir, cell, constraintQueue, layer, geometryWorld, conflictWorld];
TerminalIO.WriteChar['.];
ENDLOOP; --third Per Layer LOOP
TerminalIO.WriteChar[' ];
IF debug THEN TerminalIO.WriteChar['4];
IF saveTesselations THEN freeTesselations ← TRUE
ELSE FreeTesselations[circuit: cir];
END; -- AnalyzeGeometry
--Maintenance aids
SaveTesselations:
PUBLIC
PROC [save:
BOOL ←
FALSE] =
BEGIN
saveTesselations ← save
END;
GetTesselation:
PUBLIC
PROC [conflicts:
BOOL ←
TRUE, layer:
SX.SpinifexLayerIndex]
RETURNS [
REF CornerStitching.Tesselation] =
BEGIN
RETURN [IF conflicts THEN conflictWorlds[layer] ELSE geometryWorlds[layer]]
END;
FreeTesselations:
PROC [circuit:
REF
SX.Circuit] =
BEGIN
FOR layer: SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
conflictWorlds[layer].FreeTesselation[FALSE];
geometryWorlds[layer].FreeTesselation[FALSE];
TerminalIO.WriteChar['.];
ENDLOOP;
freeTesselations ← FALSE
END;
IsDelinquent: PROCEDURE [r: CD.Rect] RETURNS [b: BOOL] =
Used to debug quad tree stuff
BEGIN
RETURN [r = delinquent]
END;
END.
Edited on January 3, 1985 11:45:56 am PST, by Jacobi
Fehler umgangen, nicht wirklich korrigiert da nicht verstanden.
Edited on January 3, 1985 4:58:12 pm PST, by Beretta
Tried to improve readability & debuggability.
Took out ComputeConflicts and ResolveConstraints to create a new module SXConflicts. Reason: storage overflow in the compiler.
Edited on January 23, 1985 3:45:47 pm PST, by Beretta
Improved structure
Edited on February 26, 1985 11:46:36 am PST, by Jacobi
stopFlag test feature
Edited on March 8, 1985 6:04:21 pm PST, by Shand
Added parameter to SXConflicts.ResolveConstraints from TechHandle.
changes to: MixConstraints
Edited on March 13, 1985 0:39:24 am PST, by Shand
Optimizations and enhancements to allow zero extent rules.
changes to: DesignRuleCheckAOIs
Edited on March 19, 1985 6:20:07 pm PST, by Beretta
Added maintenance aids section.
changes to: saveTesselations: new, freeTesselations: new, AnalyzeGeometry: check whether old tessellations hang around and fourth loop is done only if necessary in a separate procedure, SaveTesselations: new, GetTesselation: new, FreeTesselations: new
Edited on March 27, 1985 8:02:00 pm PST, by Beretta
procedures MixConstraints, CheckTile made global
Edited on April 8, 1985 3:36:29 pm PST, by Jacobi
reformatted
Edited on June 29, 1985 8:25:03 pm PDT, by Beretta
Tried to fix Quad Tree stuff