mirror of
https://github.com/RTimothyEdwards/magic.git
synced 2026-09-05 08:51:53 +02:00
R. Timothy Edwards
14afb4bd52
time-consuming (note the commit message "There are still likely much better ways to do this"). Worked out a method of hashing the location of terminals on other planes so that they can be looked up from the address of the tile. This requires only one pass through the devices to locate and record the terminals, and no loops through devices when processing tiles. Also corrected the positioning of the substrate terminal to be the center position of the device tile, not the substrate tile. This not only better represents the substrate connections, but it also eliminates the condition in which many thousands of resistors converge on the same point, which causes stack overflow. With the current scheme, stack overflow is unlikely to occur.
1233 lines
31 KiB
C
1233 lines
31 KiB
C
|
|
#ifndef lint
|
|
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/resis/ResMakeRes.c,v 1.3 2010/06/24 12:37:56 tim Exp $";
|
|
#endif /* not lint */
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <ctype.h>
|
|
#include <math.h>
|
|
|
|
#include "utils/magic.h"
|
|
#include "utils/geometry.h"
|
|
#include "utils/geofast.h"
|
|
#include "tiles/tile.h"
|
|
#include "utils/hash.h"
|
|
#include "database/database.h"
|
|
#include "utils/malloc.h"
|
|
#include "textio/textio.h"
|
|
#include "extract/extract.h"
|
|
#include "extract/extractInt.h"
|
|
#include "windows/windows.h"
|
|
#include "dbwind/dbwind.h"
|
|
#include "utils/tech.h"
|
|
#include "textio/txcommands.h"
|
|
#include "resis/resis.h"
|
|
#include "cif/CIFint.h"
|
|
|
|
/* C99 compat */
|
|
#include "cif/cif.h"
|
|
|
|
/* Forward declarations */
|
|
bool ResCalcNearDevice();
|
|
bool ResCalcNorthSouth();
|
|
bool ResCalcEastWest();
|
|
|
|
|
|
/*
|
|
*--------------------------------------------------------------------------
|
|
*
|
|
* ResCalcTileResistance-- Given a set of partitions for a tile, the tile can
|
|
* be converted into resistors. To do this, nodes are sorted in the
|
|
* direction of current flow. Resistors are created by counting squares
|
|
* between successive breakpoints. Breakpoints with the same coordinate
|
|
* are combined.
|
|
*
|
|
* Results: returns TRUE if the startnode was involved in a merge.
|
|
*
|
|
* Side Effects: Resistor structures are produced. Some nodes may be
|
|
* eliminated.
|
|
*--------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
ResCalcTileResistance(tile, info, pendingList, doneList)
|
|
Tile *tile;
|
|
resInfo *info;
|
|
resNode **pendingList, **doneList;
|
|
|
|
{
|
|
int MaxX = MINFINITY, MinX = INFINITY;
|
|
int MaxY = MINFINITY, MinY = INFINITY;
|
|
int device;
|
|
bool merged;
|
|
Breakpoint *p1;
|
|
|
|
merged = FALSE;
|
|
device = FALSE;
|
|
|
|
if ((p1 = info->breakList) == NULL) return FALSE;
|
|
for (; p1; p1 = p1->br_next)
|
|
{
|
|
int x = p1->br_loc.p_x;
|
|
int y = p1->br_loc.p_y;
|
|
if (x > MaxX) MaxX = x;
|
|
if (x < MinX) MinX = x;
|
|
if (y > MaxY) MaxY = y;
|
|
if (y < MinY) MinY = y;
|
|
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE)
|
|
device = TRUE;
|
|
}
|
|
|
|
/* Finally, produce resistors for partition. Keep track of */
|
|
/* whether or not the node was involved in a merge. */
|
|
|
|
if (device)
|
|
{
|
|
merged |= ResCalcNearDevice(tile, pendingList, doneList, &ResResList);
|
|
}
|
|
else if (MaxY-MinY > MaxX-MinX)
|
|
{
|
|
merged |= ResCalcNorthSouth(tile, pendingList, doneList, &ResResList);
|
|
}
|
|
else
|
|
{
|
|
merged |= ResCalcEastWest(tile, pendingList, doneList, &ResResList);
|
|
}
|
|
|
|
/*
|
|
* For all the new resistors, propagate the resistance from the origin
|
|
* to the new nodes.
|
|
*/
|
|
|
|
return(merged);
|
|
}
|
|
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResCalcEastWest-- Makes resistors from an EastWest partition.
|
|
*
|
|
* Results: Returns TRUE if the sacredNode was involved in a merge.
|
|
*
|
|
* Side Effects: Makes resistors. Frees breakpoints.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
ResCalcEastWest(tile, pendingList, doneList, resList)
|
|
Tile *tile;
|
|
resNode **pendingList, **doneList;
|
|
resResistor **resList;
|
|
{
|
|
int count, height;
|
|
bool merged;
|
|
TileType ttype;
|
|
Breakpoint *p1, *p2, *p3;
|
|
resResistor *resistor;
|
|
resElement *element;
|
|
resNode *currNode;
|
|
float rArea;
|
|
resInfo *info = (resInfo *)TiGetClientPTR(tile);
|
|
HashTable BreakTable;
|
|
HashEntry *he;
|
|
|
|
merged = FALSE;
|
|
height = TOP(tile) - BOTTOM(tile);
|
|
|
|
/*
|
|
* One Breakpoint? No resistors need to be made. Free up the first
|
|
* breakpoint, then return.
|
|
*/
|
|
|
|
p1 = info->breakList;
|
|
if (p1->br_next == NULL)
|
|
{
|
|
p1->br_this->rn_float.rn_area += height * (LEFT(tile) - RIGHT(tile));
|
|
freeMagic((char *)p1);
|
|
info->breakList = NULL;
|
|
return(merged);
|
|
}
|
|
|
|
/* Simplified split tile handling */
|
|
if (IsSplit(tile))
|
|
{
|
|
ttype = TiGetLeftType(tile);
|
|
if (TiGetLeftType(tile) == TT_SPACE)
|
|
ttype = TiGetRightType(tile);
|
|
}
|
|
else
|
|
ttype = TiGetTypeExact(tile);
|
|
|
|
/* Re-sort nodes left to right. */
|
|
count = ResSortBreaks(&info->breakList, TRUE);
|
|
|
|
/* For long lists (defined as >= 16 entries), make a hash table of
|
|
* the node pointer conversions so that each node can be updated
|
|
* as we walk the list, instead of walking the rest of the list in
|
|
* a nested loop for each entry.
|
|
*/
|
|
if (count >= 16)
|
|
HashInit(&BreakTable, HT_DEFAULTSIZE, HT_CLIENTKEYS);
|
|
|
|
/*
|
|
* Eliminate breakpoints with the same X coordinate and merge
|
|
* their nodes.
|
|
*/
|
|
|
|
p2 = info->breakList;
|
|
|
|
/* Add extra left area to leftmost node */
|
|
|
|
p2->br_this->rn_float.rn_area += height * (p2->br_loc.p_x - LEFT(tile));
|
|
while (p2->br_next != NULL)
|
|
{
|
|
p1 = p2;
|
|
p2 = p2->br_next;
|
|
|
|
/* Has the node been recorded as needing to be replaced? */
|
|
if (count >= 16)
|
|
{
|
|
while (TRUE)
|
|
{
|
|
he = HashLookOnly(&BreakTable, (char *)p2->br_this);
|
|
if (!he) break;
|
|
p2->br_this = (resNode *)HashGetValue(he);
|
|
}
|
|
}
|
|
|
|
if (p2->br_loc.p_x == p1->br_loc.p_x)
|
|
{
|
|
if (p2->br_this == p1->br_this)
|
|
{
|
|
currNode = NULL;
|
|
p1->br_next = p2->br_next;
|
|
freeMagic((char *)p2);
|
|
p2 = p1;
|
|
}
|
|
else if (p2->br_this == resCurrentNode)
|
|
{
|
|
currNode = p1->br_this;
|
|
ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
|
|
merged = TRUE;
|
|
freeMagic((char *)p1);
|
|
}
|
|
else if (p1->br_this == resCurrentNode)
|
|
{
|
|
currNode = p2->br_this;
|
|
p1->br_next = p2->br_next;
|
|
ResMergeNodes(p1->br_this, p2->br_this, pendingList, doneList);
|
|
merged = TRUE;
|
|
freeMagic((char *)p2);
|
|
p2 = p1;
|
|
}
|
|
else
|
|
{
|
|
currNode = p1->br_this;
|
|
ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
|
|
freeMagic((char *)p1);
|
|
}
|
|
|
|
/*
|
|
* Was the node used in another info or breakpoint?
|
|
* If so, replace the old node with the new one.
|
|
*
|
|
* Short lists: Walk the list to the end and change
|
|
* nodes on the fly.
|
|
* Long lists: Record the change to be made in the
|
|
* hash table so that it can be executed as each list
|
|
* entry is encountered.
|
|
*/
|
|
if (count >= 16)
|
|
{
|
|
he = HashFind(&BreakTable, (char *)currNode);
|
|
HashSetValue(he, (char *)p2->br_this);
|
|
}
|
|
else
|
|
{
|
|
p3 = p2->br_next;
|
|
while (p3 != NULL)
|
|
{
|
|
if (p3->br_this == currNode)
|
|
p3->br_this = p2->br_this;
|
|
|
|
p3 = p3->br_next;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* If the X coordinates don't match, make a resistor between
|
|
* the breakpoints.
|
|
*/
|
|
|
|
else
|
|
{
|
|
resistor = (resResistor *)mallocMagic((unsigned)sizeof(resResistor));
|
|
resistor->rr_nextResistor = (*resList);
|
|
resistor->rr_lastResistor = NULL;
|
|
if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
|
|
(*resList) = resistor;
|
|
resistor->rr_connection1 = p1->br_this;
|
|
resistor->rr_connection2 = p2->br_this;
|
|
element = (resElement *)mallocMagic((unsigned)sizeof(resElement));
|
|
element->re_nextEl = p1->br_this->rn_re;
|
|
element->re_thisEl = resistor;
|
|
p1->br_this->rn_re = element;
|
|
element = (resElement *)mallocMagic((unsigned)sizeof(resElement));
|
|
element->re_nextEl = p2->br_this->rn_re;
|
|
element->re_thisEl = resistor;
|
|
p2->br_this->rn_re = element;
|
|
resistor->rr_cl = (TOP(tile) + BOTTOM(tile)) >> 1;
|
|
resistor->rr_width = height;
|
|
resistor->rr_tt = ttype;
|
|
|
|
if (IsSplit(tile))
|
|
{
|
|
resistor->rr_status = RES_DIAGONAL;
|
|
resistor->rr_status |= (SplitDirection(tile)) ? RES_NS
|
|
: RES_EW;
|
|
}
|
|
else
|
|
{
|
|
resistor->rr_status = RES_EW;
|
|
}
|
|
resistor->rr_value =
|
|
(float)ExtCurStyle->exts_sheetResist[resistor->rr_tt]
|
|
* (float)(p2->br_loc.p_x - p1->br_loc.p_x)
|
|
/ (float)height;
|
|
rArea = ((p2->br_loc.p_x - p1->br_loc.p_x) * height) / 2;
|
|
resistor->rr_connection1->rn_float.rn_area += rArea;
|
|
resistor->rr_connection2->rn_float.rn_area += rArea;
|
|
resistor->rr_float.rr_area = 0;
|
|
|
|
freeMagic((char *)p1);
|
|
}
|
|
}
|
|
|
|
if (count >= 16) HashKill(&BreakTable);
|
|
|
|
p2->br_this->rn_float.rn_area += height * (RIGHT(tile) - p2->br_loc.p_x);
|
|
freeMagic((char *)p2);
|
|
info->breakList = NULL;
|
|
return merged;
|
|
}
|
|
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResCalcNorthSouth-- Makes resistors from a NorthSouth partition
|
|
*
|
|
* Results: Returns TRUE if the resCurrentNode was involved in a merge.
|
|
*
|
|
* Side Effects: Makes resistors. Frees breakpoints
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
ResCalcNorthSouth(tile, pendingList, doneList, resList)
|
|
Tile *tile;
|
|
resNode **pendingList, **doneList;
|
|
resResistor **resList;
|
|
{
|
|
int count, width;
|
|
bool merged;
|
|
TileType ttype;
|
|
Breakpoint *p1, *p2, *p3;
|
|
resResistor *resistor;
|
|
resElement *element;
|
|
resNode *currNode;
|
|
float rArea;
|
|
resInfo *info = (resInfo *)TiGetClientPTR(tile);
|
|
HashTable BreakTable;
|
|
HashEntry *he;
|
|
|
|
merged = FALSE;
|
|
width = RIGHT(tile) - LEFT(tile);
|
|
|
|
/*
|
|
* One Breakpoint? No resistors need to be made. Free up the first
|
|
* breakpoint, then return.
|
|
*/
|
|
|
|
p1 = info->breakList;
|
|
if (p1->br_next == NULL)
|
|
{
|
|
p1->br_this->rn_float.rn_area += width * (TOP(tile) - BOTTOM(tile));
|
|
freeMagic((char *)p1);
|
|
info->breakList = NULL;
|
|
return(merged);
|
|
}
|
|
|
|
/* Re-sort nodes south to north. */
|
|
count = ResSortBreaks(&info->breakList, FALSE);
|
|
|
|
/* For long lists (defined as >= 16 entries), make a hash table of
|
|
* the node pointer conversions so that each node can be updated
|
|
* as we walk the list, instead of walking the rest of the list in
|
|
* a nested loop for each entry.
|
|
*/
|
|
if (count >= 16)
|
|
HashInit(&BreakTable, HT_DEFAULTSIZE, HT_CLIENTKEYS);
|
|
|
|
/* Simplified split tile handling */
|
|
if (IsSplit(tile))
|
|
{
|
|
ttype = TiGetLeftType(tile);
|
|
if (TiGetLeftType(tile) == TT_SPACE)
|
|
ttype = TiGetRightType(tile);
|
|
}
|
|
else
|
|
ttype = TiGetTypeExact(tile);
|
|
|
|
/*
|
|
* Eliminate breakpoints with the same Y coordinate and merge
|
|
* their nodes.
|
|
*/
|
|
|
|
p2 = info->breakList;
|
|
|
|
/* Add extra left area to leftmost node */
|
|
|
|
p2->br_this->rn_float.rn_area += width * (p2->br_loc.p_y - BOTTOM(tile));
|
|
while (p2->br_next != NULL)
|
|
{
|
|
p1 = p2;
|
|
p2 = p2->br_next;
|
|
|
|
/* Has the node been recorded as needing to be replaced? */
|
|
if (count >= 16)
|
|
{
|
|
while (TRUE)
|
|
{
|
|
he = HashLookOnly(&BreakTable, (char *)p2->br_this);
|
|
if (!he) break;
|
|
p2->br_this = (resNode *)HashGetValue(he);
|
|
}
|
|
}
|
|
|
|
if (p1->br_loc.p_y == p2->br_loc.p_y)
|
|
{
|
|
if (p2->br_this == p1->br_this)
|
|
{
|
|
currNode = NULL;
|
|
p1->br_next = p2->br_next;
|
|
freeMagic((char *)p2);
|
|
p2 = p1;
|
|
}
|
|
else if (p2->br_this == resCurrentNode)
|
|
{
|
|
currNode = p1->br_this;
|
|
ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
|
|
freeMagic((char *)p1);
|
|
merged = TRUE;
|
|
}
|
|
else if (p1->br_this == resCurrentNode)
|
|
{
|
|
currNode = p2->br_this;
|
|
p1->br_next = p2->br_next;
|
|
ResMergeNodes(p1->br_this, p2->br_this, pendingList, doneList);
|
|
merged = TRUE;
|
|
freeMagic((char *)p2);
|
|
p2 = p1;
|
|
}
|
|
else
|
|
{
|
|
currNode = p1->br_this;
|
|
ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
|
|
freeMagic((char *)p1);
|
|
}
|
|
|
|
/*
|
|
* Was the node used in another info or breakpoint?
|
|
* If so, replace the old node with the new one.
|
|
*
|
|
* Short lists: Walk the list to the end and change
|
|
* nodes on the fly.
|
|
* Long lists: Record the change to be made in the
|
|
* hash table so that it can be executed as each list
|
|
* entry is encountered.
|
|
*/
|
|
if (count >= 16)
|
|
{
|
|
he = HashFind(&BreakTable, (char *)currNode);
|
|
HashSetValue(he, (char *)p2->br_this);
|
|
}
|
|
else
|
|
{
|
|
p3 = p2->br_next;
|
|
while (p3 != NULL)
|
|
{
|
|
if (p3->br_this == currNode)
|
|
p3->br_this = p2->br_this;
|
|
|
|
p3 = p3->br_next;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* If the Y coordinates don't match, make a resistor between
|
|
* the breakpoints.
|
|
*/
|
|
|
|
else
|
|
{
|
|
resistor = (resResistor *) mallocMagic((unsigned) (sizeof(resResistor)));
|
|
resistor->rr_nextResistor = (*resList);
|
|
resistor->rr_lastResistor = NULL;
|
|
if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
|
|
(*resList) = resistor;
|
|
resistor->rr_connection1 = p1->br_this;
|
|
resistor->rr_connection2 = p2->br_this;
|
|
element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
|
|
element->re_nextEl = p1->br_this->rn_re;
|
|
element->re_thisEl = resistor;
|
|
p1->br_this->rn_re = element;
|
|
element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
|
|
element->re_nextEl = p2->br_this->rn_re;
|
|
element->re_thisEl = resistor;
|
|
p2->br_this->rn_re = element;
|
|
resistor->rr_cl = (LEFT(tile) + RIGHT(tile)) >> 1;
|
|
resistor->rr_width = width;
|
|
resistor->rr_tt = ttype;
|
|
if (IsSplit(tile))
|
|
{
|
|
resistor->rr_status = RES_DIAGONAL;
|
|
resistor->rr_status |= (SplitDirection(tile)) ? RES_NS
|
|
: RES_EW;
|
|
}
|
|
else
|
|
{
|
|
resistor->rr_status = RES_NS;
|
|
}
|
|
resistor->rr_value =
|
|
(float)ExtCurStyle->exts_sheetResist[resistor->rr_tt]
|
|
* (float)(p2->br_loc.p_y - p1->br_loc.p_y)
|
|
/ (float)width;
|
|
rArea = ((p2->br_loc.p_y - p1->br_loc.p_y) * width) / 2;
|
|
resistor->rr_connection1->rn_float.rn_area += rArea;
|
|
resistor->rr_connection2->rn_float.rn_area += rArea;
|
|
resistor->rr_float.rr_area = 0;
|
|
freeMagic((char *)p1);
|
|
}
|
|
}
|
|
p2->br_this->rn_float.rn_area += width * (TOP(tile) - p2->br_loc.p_y);
|
|
freeMagic((char *)p2);
|
|
info->breakList = NULL;
|
|
return(merged);
|
|
}
|
|
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResCalcNearDevice-- Calculating the direction of current flow near
|
|
* devices is tricky because there are two adjoining regions with
|
|
* vastly different sheet resistances. ResCalcNearDevice is called
|
|
* whenever a diffusion tile adjoining a real tile is found. It makes
|
|
* a guess at the correct direction of current flow, removes extra
|
|
* breakpoints, and call either ResCalcEastWest or ResCalcNorthSouth
|
|
*
|
|
* Results:
|
|
* TRUE if merging occurred, FALSE if not.
|
|
*
|
|
* Side Effects: Makes resistors. Frees breakpoints
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
ResCalcNearDevice(tile, pendingList, doneList, resList)
|
|
Tile *tile;
|
|
resNode **pendingList, **doneList;
|
|
resResistor **resList;
|
|
|
|
{
|
|
bool merged;
|
|
int devcount, devedge, deltax, deltay;
|
|
Breakpoint *p1, *p2, *p3;
|
|
resInfo *info = (resInfo *)TiGetClientPTR(tile);
|
|
|
|
merged = FALSE;
|
|
|
|
/*
|
|
* One Breakpoint? No resistors need to be made. Free up the first
|
|
* breakpoint, then return.
|
|
*/
|
|
|
|
if (info->breakList->br_next == NULL)
|
|
{
|
|
freeMagic((char *)info->breakList);
|
|
info->breakList = NULL;
|
|
return(merged);
|
|
}
|
|
|
|
/* Count the number of device breakpoints */
|
|
/* Mark which edge they connect to */
|
|
|
|
devcount = 0;
|
|
devedge = 0;
|
|
for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
|
|
{
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE)
|
|
{
|
|
devcount++;
|
|
if (p1->br_loc.p_x == LEFT(tile)) devedge |= LEFTEDGE;
|
|
else if (p1->br_loc.p_x == RIGHT(tile)) devedge |= RIGHTEDGE;
|
|
else if (p1->br_loc.p_y == TOP(tile)) devedge |= TOPEDGE;
|
|
else if (p1->br_loc.p_y == BOTTOM(tile)) devedge |= BOTTOMEDGE;
|
|
}
|
|
}
|
|
|
|
/* Use distance from device to next breakpoint as determinant */
|
|
/* If there is only one device or if all the devices are along */
|
|
/* the same edge. */
|
|
|
|
if (devcount == 1 ||
|
|
(devedge & LEFTEDGE) == devedge ||
|
|
(devedge & RIGHTEDGE) == devedge ||
|
|
(devedge & TOPEDGE) == devedge ||
|
|
(devedge & BOTTOMEDGE) == devedge)
|
|
{
|
|
ResSortBreaks(&info->breakList, TRUE);
|
|
p2 = NULL;
|
|
for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
|
|
{
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE)
|
|
break;
|
|
|
|
if (p1->br_next != NULL &&
|
|
(p1->br_loc.p_x != p1->br_next->br_loc.p_x ||
|
|
p1->br_loc.p_y != p1->br_next->br_loc.p_y))
|
|
p2 = p1;
|
|
}
|
|
deltax = INFINITY;
|
|
for (p3 = p1->br_next; p3 != NULL &&
|
|
p3->br_loc.p_x == p1->br_loc.p_x &&
|
|
p3->br_loc.p_y == p1->br_loc.p_y; p3 = p3->br_next);
|
|
if (p3 != NULL)
|
|
{
|
|
if (p3->br_crect)
|
|
{
|
|
if (p3->br_crect->r_ll.p_x > p1->br_loc.p_x)
|
|
{
|
|
deltax = p3->br_crect->r_ll.p_x - p1->br_loc.p_x;
|
|
}
|
|
else if (p3->br_crect->r_ur.p_x < p1->br_loc.p_x)
|
|
{
|
|
deltax = p1->br_loc.p_x - p3->br_crect->r_ur.p_x;
|
|
}
|
|
else
|
|
{
|
|
deltax = 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
deltax = abs(p1->br_loc.p_x - p3->br_loc.p_x);
|
|
}
|
|
}
|
|
if (p2 != NULL)
|
|
{
|
|
if (p2->br_crect)
|
|
{
|
|
if (p2->br_crect->r_ll.p_x > p1->br_loc.p_x)
|
|
{
|
|
deltax = MIN(deltax, p2->br_crect->r_ll.p_x - p1->br_loc.p_x);
|
|
}
|
|
else if (p2->br_crect->r_ur.p_x < p1->br_loc.p_x)
|
|
{
|
|
deltax = MIN(deltax, p1->br_loc.p_x - p2->br_crect->r_ur.p_x);
|
|
}
|
|
else
|
|
{
|
|
deltax = 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
deltax = MIN(deltax, abs(p1->br_loc.p_x - p2->br_loc.p_x));
|
|
}
|
|
}
|
|
|
|
/* Re-sort nodes south to north. */
|
|
ResSortBreaks(&info->breakList, FALSE);
|
|
p2 = NULL;
|
|
for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
|
|
{
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE)
|
|
{
|
|
break;
|
|
}
|
|
if (p1->br_next != NULL &&
|
|
(p1->br_loc.p_x != p1->br_next->br_loc.p_x ||
|
|
p1->br_loc.p_y != p1->br_next->br_loc.p_y))
|
|
{
|
|
p2 = p1;
|
|
}
|
|
}
|
|
deltay = INFINITY;
|
|
for (p3 = p1->br_next; p3 != NULL &&
|
|
p3->br_loc.p_x == p1->br_loc.p_x &&
|
|
p3->br_loc.p_y == p1->br_loc.p_y; p3 = p3->br_next);
|
|
if (p3 != NULL)
|
|
{
|
|
if (p3->br_crect)
|
|
{
|
|
if (p3->br_crect->r_ll.p_y > p1->br_loc.p_y)
|
|
{
|
|
deltay = p3->br_crect->r_ll.p_y - p1->br_loc.p_y;
|
|
}
|
|
else if (p3->br_crect->r_ur.p_y < p1->br_loc.p_y)
|
|
{
|
|
deltay = p1->br_loc.p_y - p3->br_crect->r_ur.p_y;
|
|
}
|
|
else
|
|
{
|
|
deltay = 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
deltay = abs(p1->br_loc.p_y - p3->br_loc.p_y);
|
|
}
|
|
}
|
|
if (p2 != NULL)
|
|
{
|
|
if (p2->br_crect)
|
|
{
|
|
if (p2->br_crect->r_ll.p_y > p1->br_loc.p_y)
|
|
{
|
|
deltay = MIN(deltay, p2->br_crect->r_ll.p_y - p1->br_loc.p_y);
|
|
}
|
|
else if (p2->br_crect->r_ur.p_y < p1->br_loc.p_y)
|
|
{
|
|
deltay = MIN(deltay, p1->br_loc.p_y - p2->br_crect->r_ur.p_y);
|
|
}
|
|
else
|
|
{
|
|
deltay = 0;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
deltay = MIN(deltay, abs(p1->br_loc.p_y - p2->br_loc.p_y));
|
|
}
|
|
}
|
|
if (deltay > deltax)
|
|
{
|
|
return ResCalcNorthSouth(tile, pendingList, doneList, resList);
|
|
}
|
|
else
|
|
{
|
|
return ResCalcEastWest(tile, pendingList, doneList, resList);
|
|
}
|
|
}
|
|
|
|
/* Multiple devices connected to the partition */
|
|
|
|
else
|
|
{
|
|
if (devedge == 0)
|
|
{
|
|
TxError("Error in device current direction routine\n");
|
|
return(merged);
|
|
}
|
|
|
|
/* Check to see if the current flow is north-south */
|
|
/* Possible north-south conditions: */
|
|
/* 1. There are devices along the top and bottom edges */
|
|
/* but not along the left or right */
|
|
/* 2. There are devices along two sides at right angles, */
|
|
/* and the tile is wider than it is tall. */
|
|
|
|
if (((devedge & TOPEDGE) && (devedge & BOTTOMEDGE) &&
|
|
!(devedge & LEFTEDGE) && !(devedge & RIGHTEDGE)) ||
|
|
((devedge & TOPEDGE || devedge & BOTTOMEDGE) &&
|
|
(devedge & LEFTEDGE || devedge & RIGHTEDGE) &&
|
|
(RIGHT(tile) - LEFT(tile)) > (TOP(tile) - BOTTOM(tile))))
|
|
{
|
|
/* re-sort nodes south to north. */
|
|
ResSortBreaks(&info->breakList, FALSE);
|
|
|
|
/* eliminate duplicate S/D pointers */
|
|
for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
|
|
{
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE &&
|
|
(p1->br_loc.p_y == BOTTOM(tile) ||
|
|
p1->br_loc.p_y == TOP(tile)))
|
|
{
|
|
p3 = NULL;
|
|
p2 = info->breakList;
|
|
while (p2 != NULL)
|
|
{
|
|
if (p2->br_this == p1->br_this && p2 != p1 &&
|
|
p2->br_loc.p_y != BOTTOM(tile) &&
|
|
p2->br_loc.p_y != TOP(tile))
|
|
{
|
|
if (p3 == NULL)
|
|
{
|
|
info->breakList = p2->br_next;
|
|
freeMagic((char *) p2);
|
|
p2 = info->breakList;
|
|
}
|
|
else
|
|
{
|
|
p3->br_next = p2->br_next;
|
|
freeMagic((char *) p2);
|
|
p2 = p3->br_next;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
p3 = p2;
|
|
p2 = p2->br_next;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return ResCalcNorthSouth(tile, pendingList, doneList, resList);
|
|
}
|
|
else
|
|
{
|
|
/* Eliminate duplicate S/D pointers */
|
|
for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
|
|
{
|
|
if (p1->br_this->rn_why == RES_NODE_DEVICE &&
|
|
(p1->br_loc.p_x == LEFT(tile) ||
|
|
p1->br_loc.p_x == RIGHT(tile)))
|
|
{
|
|
p3 = NULL;
|
|
p2 = info->breakList;
|
|
while (p2 != NULL)
|
|
{
|
|
if (p2->br_this == p1->br_this && p2 != p1 &&
|
|
p2->br_loc.p_x != LEFT(tile) &&
|
|
p2->br_loc.p_x != RIGHT(tile))
|
|
{
|
|
if (p3 == NULL)
|
|
{
|
|
info->breakList = p2->br_next;
|
|
freeMagic((char *) p2);
|
|
p2 = info->breakList;
|
|
}
|
|
else
|
|
{
|
|
p3->br_next = p2->br_next;
|
|
freeMagic((char *) p2);
|
|
p2 = p3->br_next;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
p3 = p2;
|
|
p2 = p2->br_next;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return ResCalcEastWest(tile, pendingList, doneList, resList);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResDoContacts-- Add node (or nodes) for a contact. If there are contact
|
|
* resistances, also add a resistor.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side Effects: Creates nodes and resistors
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResDoContacts(contact, nodes, resList)
|
|
ResContactPoint *contact;
|
|
resNode **nodes;
|
|
resResistor **resList;
|
|
{
|
|
resNode *resptr;
|
|
cElement *ccell;
|
|
int tilenum, squaresx, squaresy, viawidth;
|
|
int minside, spacing, border, cscale;
|
|
float squaresf;
|
|
resResistor *resistor;
|
|
resElement *element;
|
|
static int too_small = 1;
|
|
|
|
minside = CIFGetContactSize(contact->cp_type, &viawidth, &spacing, &border);
|
|
cscale = CIFCurStyle->cs_scaleFactor;
|
|
|
|
if ((ExtCurStyle->exts_viaResist[contact->cp_type] == 0) || (viawidth == 0))
|
|
{
|
|
int x = contact->cp_center.p_x;
|
|
int y = contact->cp_center.p_y;
|
|
|
|
resptr = (resNode *) mallocMagic((unsigned) (sizeof(resNode)));
|
|
InitializeResNode(resptr, x, y, RES_NODE_CONTACT);
|
|
ResAddToQueue(resptr, nodes);
|
|
|
|
ccell = (cElement *) mallocMagic((unsigned) (sizeof(cElement)));
|
|
ccell->ce_nextc = resptr->rn_ce;
|
|
resptr->rn_ce = ccell;
|
|
ccell->ce_thisc = contact;
|
|
|
|
/* Add 1 celement for each layer of contact */
|
|
|
|
for (tilenum = 0; tilenum < contact->cp_currentcontact; tilenum++)
|
|
{
|
|
Tile *tile = contact->cp_tile[tilenum];
|
|
|
|
contact->cp_cnode[tilenum] = resptr;
|
|
ResNewBreak(resptr, tile, contact->cp_center.p_x,
|
|
contact->cp_center.p_y, &contact->cp_rect);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (((contact->cp_width * cscale) < minside) ||
|
|
((contact->cp_height * cscale) < minside))
|
|
{
|
|
if (too_small)
|
|
{
|
|
TxError("Warning: %s at %d %d smaller than extract section allows\n",
|
|
DBTypeLongNameTbl[contact->cp_type],
|
|
contact->cp_center.p_x, contact->cp_center.p_y);
|
|
too_small = 0;
|
|
}
|
|
squaresx = squaresy = 1;
|
|
}
|
|
else
|
|
{
|
|
viawidth += spacing;
|
|
squaresf = (float)((contact->cp_width * cscale) - minside);
|
|
squaresf /= (float)viawidth;
|
|
squaresx = (int)squaresf;
|
|
squaresx++;
|
|
|
|
squaresf = (float)((contact->cp_height * cscale) - minside);
|
|
squaresf /= (float)viawidth;
|
|
squaresy = (int)squaresf;
|
|
squaresy++;
|
|
}
|
|
for (tilenum = 0; tilenum < contact->cp_currentcontact; tilenum++)
|
|
{
|
|
int x = contact->cp_center.p_x;
|
|
int y = contact->cp_center.p_y;
|
|
Tile *tile = contact->cp_tile[tilenum];
|
|
|
|
resptr = (resNode *) mallocMagic((unsigned) (sizeof(resNode)));
|
|
InitializeResNode(resptr, x, y, RES_NODE_CONTACT);
|
|
ResAddToQueue(resptr, nodes);
|
|
|
|
/* Add contact pointer to node */
|
|
|
|
ccell = (cElement *) mallocMagic((unsigned) (sizeof(cElement)));
|
|
ccell->ce_nextc = resptr->rn_ce;
|
|
resptr->rn_ce = ccell;
|
|
ccell->ce_thisc = contact;
|
|
|
|
contact->cp_cnode[tilenum] = resptr;
|
|
ResNewBreak(resptr, tile, contact->cp_center.p_x,
|
|
contact->cp_center.p_y, &contact->cp_rect);
|
|
|
|
/* Add resistors here */
|
|
|
|
if (tilenum > 0)
|
|
{
|
|
resistor = (resResistor *) mallocMagic((unsigned) (sizeof(resResistor)));
|
|
resistor->rr_nextResistor = (*resList);
|
|
resistor->rr_lastResistor = NULL;
|
|
if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
|
|
(*resList) = resistor;
|
|
resistor->rr_connection1 = contact->cp_cnode[tilenum - 1];
|
|
resistor->rr_connection2 = contact->cp_cnode[tilenum];
|
|
|
|
element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
|
|
element->re_nextEl = contact->cp_cnode[tilenum - 1]->rn_re;
|
|
element->re_thisEl = resistor;
|
|
contact->cp_cnode[tilenum - 1]->rn_re = element;
|
|
element = (resElement *) mallocMagic((unsigned)(sizeof(resElement)));
|
|
element->re_nextEl = contact->cp_cnode[tilenum]->rn_re;
|
|
element->re_thisEl = resistor;
|
|
contact->cp_cnode[tilenum]->rn_re = element;
|
|
|
|
/* Need to figure out how to handle the multiple nodes */
|
|
/* and multiple resistors necessary to determine the */
|
|
/* correct geometry for the geometry extractor. For */
|
|
/* now, extract as one big glob. */
|
|
|
|
/* rr_cl doesn't need to represent centerline; use for */
|
|
/* # squares in y direction instead; use rr_width for */
|
|
/* # squares in x direction. */
|
|
|
|
resistor->rr_cl = squaresy;
|
|
resistor->rr_width = squaresx;
|
|
|
|
resistor->rr_value =
|
|
(float)ExtCurStyle->exts_viaResist[contact->cp_type] /
|
|
(float)(squaresx * squaresy);
|
|
resistor->rr_tt = contact->cp_type;
|
|
resistor->rr_float.rr_area = 0;
|
|
resistor->rr_status = 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* BreakCompare --
|
|
*
|
|
* Helper routine for MergeSortBreaks() (below). Simple
|
|
* comparison of the breakpoint position. Comparison is
|
|
* done for the X position if "xsort" is TRUE, and the Y
|
|
* position if "xsort" is FALSE.
|
|
*
|
|
* Return value:
|
|
* Return -1 if the (x or y) position of a is less than the
|
|
* (x or y) position of b; return +1 if the position of a is
|
|
* greater than the position of b; and return 0 if they have
|
|
* equal positions.
|
|
*
|
|
* Side effect:
|
|
* None.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
BreakCompare(
|
|
Breakpoint *a,
|
|
Breakpoint *b,
|
|
int xsort)
|
|
{
|
|
if (xsort == TRUE)
|
|
{
|
|
if (a->br_loc.p_x < b->br_loc.p_x) return -1;
|
|
if (a->br_loc.p_x > b->br_loc.p_x) return 1;
|
|
}
|
|
else
|
|
{
|
|
if (a->br_loc.p_y < b->br_loc.p_y) return -1;
|
|
if (a->br_loc.p_y > b->br_loc.p_y) return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* MergeSorted --
|
|
*
|
|
* Helper routine for MergeSortBreaks() (below). Merge sort
|
|
* merging routine.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
Breakpoint *
|
|
MergeSorted(
|
|
Breakpoint *a,
|
|
Breakpoint *b,
|
|
int xsort)
|
|
{
|
|
Breakpoint head;
|
|
Breakpoint *tail = &head;
|
|
|
|
head.br_next = NULL;
|
|
|
|
while (a != NULL && b != NULL)
|
|
{
|
|
if (BreakCompare(a, b, xsort) <= 0)
|
|
{
|
|
tail->br_next = a;
|
|
a = a->br_next;
|
|
}
|
|
else
|
|
{
|
|
tail->br_next = b;
|
|
b = b->br_next;
|
|
}
|
|
tail = tail->br_next;
|
|
}
|
|
tail->br_next = (a != NULL) ? a : b;
|
|
|
|
return head.br_next;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* SplitList --
|
|
*
|
|
* Helper routine for MergeSortBreaks() (below). Merge sort
|
|
* splitting routine.
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
SplitList(
|
|
Breakpoint *source,
|
|
Breakpoint **front,
|
|
Breakpoint **back)
|
|
{
|
|
Breakpoint *slow;
|
|
Breakpoint *fast;
|
|
|
|
if (source == NULL || source->br_next == NULL)
|
|
{
|
|
*front = source;
|
|
*back = NULL;
|
|
return;
|
|
}
|
|
|
|
slow = source;
|
|
fast = source->br_next;
|
|
|
|
while (fast != NULL)
|
|
{
|
|
fast = fast->br_next;
|
|
|
|
if (fast != NULL)
|
|
{
|
|
slow = slow->br_next;
|
|
fast = fast->br_next;
|
|
}
|
|
}
|
|
|
|
*front = source;
|
|
*back = slow->br_next;
|
|
slow->br_next = NULL;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* MergeSortBreaks --
|
|
*
|
|
* See "ResSortBreaks" below. Alternative to bubble sort for long
|
|
* linked lists.
|
|
*
|
|
* Results:
|
|
* Pointer to a sorted breakpoint list.
|
|
*
|
|
* Side effects:
|
|
* The breakpoints are sorted.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
Breakpoint *
|
|
MergeSortBreaks(Breakpoint *list, int xsort)
|
|
{
|
|
Breakpoint *a, *b;
|
|
|
|
if (list == NULL || list->br_next == NULL)
|
|
return list;
|
|
|
|
SplitList(list, &a, &b);
|
|
|
|
a = MergeSortBreaks(a, xsort);
|
|
b = MergeSortBreaks(b, xsort);
|
|
|
|
return MergeSorted(a, b, xsort);
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResSortBreaks --
|
|
*
|
|
* Sort breakpoints, either in the X direction (if "xsort" is TRUE)
|
|
* or in the Y direction (if "xsort" is FALSE). For short lists
|
|
* (< 16 elements), a simple bubble sort is used. For larger lists,
|
|
* a merge sort is used. Most resistor networks are short, but
|
|
* power/ground networks can be huge and cause a performance
|
|
* bottleneck.
|
|
*
|
|
* Results:
|
|
* Return the length of the list (maximum truncated at 16) so that
|
|
* the calling routine can determine if this is a long or a short
|
|
* linked list and treat it accordingly.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
ResSortBreaks(masterlist, xsort)
|
|
Breakpoint **masterlist;
|
|
int xsort;
|
|
{
|
|
Breakpoint *p1, *p2, *p3, *p4;
|
|
bool changed;
|
|
int count = 0;
|
|
|
|
for (p1 = *masterlist; p1; p1 = p1->br_next)
|
|
{
|
|
count++;
|
|
if (count > 16)
|
|
{
|
|
*masterlist = MergeSortBreaks(*masterlist, xsort);
|
|
return count;
|
|
}
|
|
}
|
|
|
|
/* Simple bubble sort */
|
|
|
|
changed = TRUE;
|
|
while (changed == TRUE)
|
|
{
|
|
changed = FALSE;
|
|
p1 = NULL;
|
|
p2 = *masterlist;
|
|
p3 = p2->br_next;
|
|
while (p3 != NULL)
|
|
{
|
|
if ((xsort == TRUE && p2->br_loc.p_x > p3->br_loc.p_x) ||
|
|
(xsort == FALSE && p2->br_loc.p_y > p3->br_loc.p_y))
|
|
{
|
|
changed = TRUE;
|
|
if (p1 == NULL)
|
|
{
|
|
*masterlist = p3;
|
|
}
|
|
else
|
|
{
|
|
p1->br_next = p3;
|
|
}
|
|
p2->br_next = p3->br_next;
|
|
p3->br_next = p2;
|
|
p4 = p2;
|
|
p2 = p3;
|
|
p3 = p4;
|
|
}
|
|
else
|
|
{
|
|
p1 = p2;
|
|
p2 = p3;
|
|
p3 = p3->br_next;
|
|
}
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|