path: root/node.c

/*--------------------------------------------------------------*/
/* node.c -- Generation	of detailed network and obstruction	*/
/* information on the routing grid based on the geometry of the	*/
/* layout of the standard cell macros.				*/
/*								*/
/*--------------------------------------------------------------*/
/* Written by Tim Edwards, June, 2011, based on work by Steve	*/
/* Beccue.							*/
/*--------------------------------------------------------------*/

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#include "qrouter.h"
#include "node.h"
#include "qconfig.h"
#include "lef.h"
#include "def.h"
#include "output.h"

/*--------------------------------------------------------------*/
/* SetNodeinfo --						*/
/*	Allocate a NODEINFO record and put it in the Nodeinfo	*/
/*	array at position (gridx, gridy, d->layer).  Return the	*/
/* 	pointer to the location.				*/
/*--------------------------------------------------------------*/

NODEINFO
SetNodeinfo(int gridx, int gridy, int layer, NODE node)
{
    DPOINT dp;
    NODEINFO *lnodeptr;

    lnodeptr = &NODEIPTR(gridx, gridy, layer);
    if (*lnodeptr == NULL) {
	*lnodeptr = (NODEINFO)calloc(1, sizeof(struct nodeinfo_));

	/* Make sure this position is in the list of node's taps.  Add	*/
	/* it if it is not there.					*/

	for (dp = (DPOINT)node->taps; dp; dp = dp->next)
	    if (dp->gridx == gridx && dp->gridy == gridy && dp->layer == layer)
		break;
	if (dp == NULL)
	    for (dp = (DPOINT)node->extend; dp; dp = dp->next)
		if (dp->gridx == gridx && dp->gridy == gridy && dp->layer == layer)
		    break;
	if (dp == NULL) {
	    dp = (DPOINT)malloc(sizeof(struct dpoint_));
	    dp->gridx = gridx;
	    dp->gridy = gridy;
	    dp->layer = layer;
	    dp->x = (gridx * PitchX) + Xlowerbound;
	    dp->y = (gridy * PitchY) + Ylowerbound;
	    dp->next = node->extend;
	    node->extend = dp;
	}
    }
    return *lnodeptr;
}

/*--------------------------------------------------------------*/
/* FreeNodeinfo --						*/
/*	Free a NODEINFO record at array Nodeinfo position	*/
/*	(gridx, gridy, d->layer).  Set the position pointer to	*/
/*	NULL.  							*/
/*--------------------------------------------------------------*/

void
FreeNodeinfo(int gridx, int gridy, int layer)
{
    NODEINFO *lnodeptr;
    lnodeptr = &NODEIPTR(gridx, gridy, layer);

    if (*lnodeptr != NULL) {
        free(*lnodeptr);
	*lnodeptr = NULL;
    }
}

/*--------------------------------------------------------------*/
/* count_reachable_taps()					*/
/*								*/
/*  For each grid point in the layout, find if it corresponds	*/
/*  to a node and is unobstructed.  If so, increment the node's	*/
/*  count of reachable taps.  Then work through the list of	*/
/*  nodes and determine if any are completely unreachable.  If	*/
/*  so, then unobstruct any position that is inside tap		*/
/*  geometry that can contain a via.				*/
/*								*/
/*  NOTE:  This routine should check for tap rectangles that	*/
/*  may combine to form an area large enough to place a via;	*/
/*  also, it should check for tap points that are routable	*/
/*  by a wire and not a tap.  However, those conditions are	*/
/*  rare and are left unhandled for now.			*/
/*								*/
/*  If "unblock_all" is 1, then unblock all grid points that	*/
/*  are cleanly routable by being completely inside a pin with	*/
/*  available margins for placing a via, regardless of whether	*/
/*  or not the pin has other available tap points.  This should	*/
/*  only be used if obstructions are drawn in the style where	*/
/*  they can abut pins (e.g., part of the pin has been marked	*/
/*  as an obstruction).						*/
/*--------------------------------------------------------------*/

void
count_reachable_taps(u_char unblock_all)
{
    NODE node;
    NODEINFO lnode;
    GATE g;
    DSEG ds;
    int l, i, j, orient;
    int gridx, gridy;
    double deltax, deltay;
    double dx, dy;

    for (l = 0; l < Num_layers; l++) {
	for (j = 0; j < NumChannelsX * NumChannelsY; j++) {
	    if (Nodeinfo[l][j]) {
		node = Nodeinfo[l][j]->nodeloc;
		if (node != NULL) {

		    // Redundant check;  if Obs has NO_NET set, then
		    // Nodeinfo->nodeloc for that position should already
		    // be NULL

		    if (!(Obs[l][j] & NO_NET))
			node->numtaps++;
		}
	    }
	}
    }

    for (g = Nlgates; g; g = g->next) {
	for (i = 0; i < g->nodes; i++) {
	    node = g->noderec[i];
	    if (node == NULL) continue;
	    if (node->numnodes == 0) continue;	 // e.g., vdd or gnd bus
	    if ((node->numtaps == 0) || (unblock_all == TRUE)) {

		/* Will try more than one via if available */
		for (orient = 0; orient < 4; orient += 2) {
		    for (ds = g->taps[i]; ds; ds = ds->next) {
			deltax = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 0, orient);
			deltay = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 1, orient);

			gridx = (int)((ds->x1 - Xlowerbound) / PitchX) - 1;
			if (gridx < 0) gridx = 0;
			while (1) {
			    dx = (gridx * PitchX) + Xlowerbound;
			    if (dx > ds->x2 || gridx >= NumChannelsX) break;

			    if (((dx - ds->x1 + EPS) > deltax) &&
					((ds->x2 - dx + EPS) > deltax)) {
				gridy = (int)((ds->y1 - Ylowerbound)
					/ PitchY) - 1;
				if (gridy < 0) gridy = 0;
				while (1) {
				    dy = (gridy * PitchY) + Ylowerbound;
				    if (dy > ds->y2 || gridy >= NumChannelsY)
					break;

				    if (((dy - ds->y1 + EPS) > deltay) &&
						((ds->y2 - dy + EPS) > deltay)) {

					if ((ds->layer == Num_layers - 1) ||
						!(OBSVAL(gridx, gridy, ds->layer + 1)
						& NO_NET)) {

					    // Grid position is clear for placing a via

					    if ((orient == 0) && (Verbose > 1))
						Fprintf(stdout, "Tap position (%g, %g)"
						    " appears to be technically routable"
						    " so it is being forced routable.\n",
						    dx, dy);
					    else if (Verbose > 1)
						Fprintf(stdout, "Tap position (%g, %g)"
						    " appears to be technically routable"
						    " with alternate via, so it is being"
						    " forced routable.\n", dx, dy);

					    OBSVAL(gridx, gridy, ds->layer) =
						(OBSVAL(gridx, gridy, ds->layer)
						& BLOCKED_MASK)
						| (u_int)node->netnum;
					    lnode = SetNodeinfo(gridx, gridy, ds->layer,
							node);
					    lnode->nodeloc = node;
					    lnode->nodesav = node;

					    /* If we got to orient = 2, mark NI_NO_VIAX */
					    if (orient == 2) lnode->flags |= NI_NO_VIAX;
					    /* This is a bit harsh, but should work */
					    else lnode->flags |= NI_NO_VIAY;
					    node->numtaps++;
					}
				    }
				    gridy++;
				}
			    }
			    gridx++;
			}
		    }
		    /* If there's a solution, don't go looking at other vias */
		    if (node->numtaps > 0) break;
		}
	    }
	    if (node->numtaps == 0) {
		/* Node wasn't cleanly within tap geometry when centered */
		/* on a grid point.  But if the via can be offset and is */
		/* cleanly within the tap geometry, then allow it.	 */

		double dist, mindist;
		int dir, mask, tapx, tapy, tapl;

		/* Will try more than one via if available */
		for (orient = 0; orient < 4; orient += 2) {

		    /* Initialize mindist to a large value */
		    mask = 0;
		    mindist = PitchX + PitchY;
		    dir = 0;	/* Indicates no solution found */

		    for (ds = g->taps[i]; ds; ds = ds->next) {
			deltax = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 0, orient);
			deltay = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 1, orient);

			gridx = (int)((ds->x1 - Xlowerbound) / PitchX) - 1;
			if (gridx < 0) gridx = 0;
			while (1) {
			    dx = (gridx * PitchX) + Xlowerbound;
			    if (dx > ds->x2 || gridx >= NumChannelsX) break;

			    if (((dx - ds->x1 + EPS) > -deltax) &&
					((ds->x2 - dx + EPS) > -deltax)) {
				gridy = (int)((ds->y1 - Ylowerbound) / PitchY) - 1;
				if (gridy < 0) gridy = 0;

				while (1) {
				    dy = (gridy * PitchY) + Ylowerbound;
				    if (dy > ds->y2 || gridy >= NumChannelsY)
					break;

				    // Check that the grid position is inside the
				    // tap rectangle.

				    // NOTE: If the point above the grid is blocked,
				    // then a via cannot be placed here, so skip it.
				    // This currently looks only for completely
				    // obstructed positions.  To do:  For directionally
				    // obstructed positions, see if the obstruction
				    // is in the opposite direction of the via's
				    // offset and at least the same distance.
				    // Otherwise, it won't clear.

				    if (((ds->layer == Num_layers - 1) ||
						!(OBSVAL(gridx, gridy, ds->layer + 1)
						& (NO_NET || OBSTRUCT_MASK))) &&
						((dy - ds->y1 + EPS) > -deltay) &&
						((ds->y2 - dy + EPS) > -deltay)) {

					// Grid point is inside tap geometry.
					// Since it did not pass the simple insideness
					// test previously, it can be assumed that
					// one of the edges is closer to the grid point
					// than 1/2 via width.  Find that edge and use
					// it to determine the offset.

					// Check right edge
					if ((ds->x2 - dx + EPS) < deltax) {
					    dist = deltax - ds->x2 + dx;
					    // Confirm other edges
					    if ((dx - dist - deltax + EPS > ds->x1) &&
							(dy - deltay + EPS > ds->y1) &&
							(dy + deltay - EPS < ds->y2)) {
						if (dist < fabs(mindist)) {
						    mindist = dist;
						    mask = STUBROUTE;
						    dir = NI_STUB_EW;
						    tapx = gridx;
						    tapy = gridy;
						    tapl = ds->layer;
						}
					    }
					}
					// Check left edge
					if ((dx - ds->x1 + EPS) < deltax) {
					    dist = deltax - dx + ds->x1;
					    // Confirm other edges
					    if ((dx + dist + deltax - EPS < ds->x2) &&
							(dy - deltay + EPS > ds->y1) &&
							(dy + deltay - EPS < ds->y2)) {
						if (dist < fabs(mindist)) {
						    mindist = -dist;
						    mask = STUBROUTE;
						    dir = NI_STUB_EW;
						    tapx = gridx;
						    tapy = gridy;
						    tapl = ds->layer;
						}
					    }
					}
					// Check top edge
					if ((ds->y2 - dy + EPS) < deltay) {
					    dist = deltay - ds->y2 + dy;
					    // Confirm other edges
					    if ((dx - deltax + EPS > ds->x1) &&
						    (dx + deltax - EPS < ds->x2) &&
						    (dy - dist - deltay + EPS > ds->y1)) {
						if (dist < fabs(mindist)) {
						    mindist = -dist;
						    mask = STUBROUTE;
						    dir = NI_STUB_NS;
						    tapx = gridx;
						    tapy = gridy;
						    tapl = ds->layer;
						}
					    }
					}
					// Check bottom edge
					if ((dy - ds->y1 + EPS) < deltay) {
					    dist = deltay - dy + ds->y1;
					    // Confirm other edges
					    if ((dx - deltax + EPS > ds->x1) &&
						    (dx + deltax - EPS < ds->x2) &&
						    (dy + dist + deltay - EPS < ds->y2)) {
						if (dist < fabs(mindist)) {
					 	    mindist = dist;
						    mask = STUBROUTE;
						    dir = NI_STUB_NS;
						    tapx = gridx;
						    tapy = gridy;
						    tapl = ds->layer;
						}
					    }
					}
				    }
				    gridy++;
				}
			    }
			    gridx++;
			}
		    }

		    /* Was a solution found? */
		    if (mask != 0) {
			// Grid position is clear for placing a via

			if (Verbose > 1)
			    Fprintf(stdout, "Tap position (%d, %d) appears to be"
					" technically routable with an offset, so"
					" it is being forced routable.\n",
					tapx, tapy);

			OBSVAL(tapx, tapy, tapl) =
				(OBSVAL(tapx, tapy, tapl) & BLOCKED_MASK)
				| mask | (u_int)node->netnum;
			lnode = SetNodeinfo(tapx, tapy, tapl, node);
			lnode->nodeloc = node;
			lnode->nodesav = node;
			lnode->stub = dist;
			lnode->flags |= dir;

			/* If we got to orient = 2 then mark NI_NO_VIAX */
			if (orient == 2) lnode->flags |= NI_NO_VIAX;

			node->numtaps++;
		    }

		    /* If there's a solution, don't go looking at other vias */
		    if (node->numtaps > 0) break;
		}
	    }
	}
    }

    /* Last pass to output error messages for any taps that were not	*/
    /* handled by the code above.					*/

    for (g = Nlgates; g; g = g->next) {
	for (i = 0; i < g->nodes; i++) {
	    node = g->noderec[i];
	    if (node == NULL) continue;
	    if (node->numnodes == 0) continue;	 // e.g., vdd or gnd bus
	    if (node->numtaps == 0) {
		Fprintf(stderr, "Error: Node %s of net \"%s\" has no taps!\n",
			print_node_name(node), node->netname);
		Fprintf(stderr, "Qrouter will not be able to completely"
			" route this net.\n");
		if (Verbose > 1) {
		    int found_inside, found_inrange;
		    Fprintf(stderr, "Tap position blockage analysis:\n");

		    /* Unreachable taps are the most common problem with    */
		    /* new processes or buggy code, so make a detailed	    */
		    /* report of blockages affecting routing for debugging. */

		    found_inside = found_inrange = 0;
		    for (ds = g->taps[i]; ds; ds = ds->next) {
			unsigned char is_inside, is_inrange;

			deltax = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 0, 0);
			deltay = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 1, 0);

			Fprintf(stderr, "Tap geometry (%g %g) to (%g %g):\n",
				ds->x1, ds->y1, ds->x2, ds->y2);

			gridx = (int)(((ds->x1 - 1) - Xlowerbound) / PitchX) - 1;
			if (gridx < 0) gridx = 0;
			while (1) {
			    dx = (gridx * PitchX) + Xlowerbound;
			    if (dx > (ds->x2 + 1) || gridx >= NumChannelsX) break;
			    gridy = (int)(((ds->y1 - 1) - Ylowerbound) / PitchY) - 1;
			    if (gridy < 0) gridy = 0;
			    while (1) {
				dy = (gridy * PitchY) + Ylowerbound;
				if (dy > (ds->y2 + 1) || gridy >= NumChannelsY)
				    break;

				is_inside = (dx >= ds->x1 && dx <= ds->x2 &&
					     dy >= ds->y1 && dy <= ds->y2) ? 1 : 0;

				is_inrange = (dx > ds->x1 - deltax &&
					     dx < ds->x2 + deltax &&
					     dy > ds->y1 - deltay &&
					     dy < ds->y2 + deltay) ? 1 : 0;

			        if (is_inrange) {
				    Fprintf(stderr, "Grid position (%d %d) at (%g %g) "
					    "layer %d is %s tap geometry.\n",
					    gridx, gridy, dx, dy, ds->layer,
					    (is_inside == 1) ? "inside" : "outside");
				    print_grid_information(gridx, gridy, ds->layer);
				    found_inrange++;
				    if (is_inside) found_inside++;
				}
				gridy++;
			    }
			    gridx++;
			}
		    }
		    if (found_inrange == 0) Fprintf(stderr, "No positions analyzed.\n");
		    Fprintf(stderr, "%d grid position%s found "
			    "inside tap geometry\n", found_inside,
			    ((found_inside == 1) ? " was" : "s were"));
		    Fprintf(stderr, "%d grid position%s found "
			    "nearby tap geometry\n", found_inrange,
			    ((found_inrange == 1) ? " was" : "s were"));
		}
	    }
	}
    }
}

/*--------------------------------------------------------------*/
/* check_variable_pitch()					*/
/*								*/
/*  This routine is used by the routine below it to generate	*/
/*  obstructions that force routes to be placed in 1-of-N	*/
/*  tracks.  However, it is also used to determine the same	*/
/*  information for the .info file, so that the effective	*/
/*  pitch is output, not the pitch copied from the LEF file.	*/
/*  Output is the vertical and horizontal pitch multipliers,	*/
/*  passed back through pointers.				*/
/*--------------------------------------------------------------*/

void check_variable_pitch(int l, int *hptr, int *vptr)
{
   int o, hnum, vnum;
   double vpitch, hpitch, wvia, wviax, wviay;

   o = LefGetRouteOrientation(l);

   // Note that when "horizontal" (o = 1) is passed to LefGetXYViaWidth,
   // it returns the via width top-to-bottom (orient meaning is
   // reversed for LefGetXYViaWidth), which is what we want. . .

   // Try both via orientations and choose the best, assuming that it is
   // a lot easier to rotate and shift vias around than it is to lose
   // half the routing grid.

   if (l == 0) {
	 wviax = LefGetXYViaWidth(l, l, o, 0);
	 wviay = LefGetXYViaWidth(l, l, o, 3);
   }
   else {
	 wviax = LefGetXYViaWidth(l - 1, l, o, 0);
	 wviay = LefGetXYViaWidth(l - 1, l, o, 3);
   }
   wvia = (wviax < wviay) ? wviax : wviay;

   if (o == 1) {	// Horizontal route
      vpitch = LefGetRoutePitch(l);
      // Changed:  routes must be able to accomodate the placement
      // of a via in the track next to it.

      // hpitch = LefGetRouteWidth(l) + LefGetRouteSpacing(l);
      hpitch = 0.5 * (LefGetRouteWidth(l) + wvia) + LefGetRouteSpacing(l);
   }
   else {		// Vertical route
      hpitch = LefGetRoutePitch(l);
      // vpitch = LefGetRouteWidth(l) + LefGetRouteSpacing(l);
      vpitch = 0.5 * (LefGetRouteWidth(l) + wvia) + LefGetRouteSpacing(l);
   }

   vnum = (int)((vpitch / PitchY) - EPS) + 1;
   hnum = (int)((hpitch / PitchX) - EPS) + 1;

   // To mark blockages, either none of (hnum & vnum) should be
   // larger than 1, or both of them should be.  Further info in
   // create_obstructions_from_variable_pitch(), below.

   if (vnum > 1 && hnum == 1) hnum++;
   if (hnum > 1 && vnum == 1) vnum++;

   *vptr = vnum;
   *hptr = hnum;
}

/*--------------------------------------------------------------*/
/* create_obstructions_from_variable_pitch()			*/
/*								*/
/*  Although it would be nice to have an algorithm that would	*/
/*  work with any arbitrary pitch, qrouter will work around	*/
/*  having larger pitches on upper metal layers by selecting	*/
/*  1 out of every N tracks for routing, and placing 		*/
/*  obstructions in the interstices.  This makes the possibly	*/
/*  unwarranted assumption that the contact down to the layer	*/
/*  below does not cause spacing violations to neighboring	*/
/*  tracks.  If that assumption fails, this routine will have	*/
/*  to be revisited.						*/
/*--------------------------------------------------------------*/

void create_obstructions_from_variable_pitch(void)
{
   int l, vnum, hnum, hoff, voff, x, y;
   NODEINFO lnode;
   TRACKS tracksinfo, tracksinfoother;

   for (l = 0; l < Num_layers; l++) {

      // check_variable_pitch() guarantees that either hnum
      // and vnum are both one, or both are larger than 1.

      check_variable_pitch(l, &hnum, &vnum);

      if (hnum == 1 && vnum == 1) continue;	// No obstructions needed

      // Compute the offset of the tracks to mark obstructions
      tracksinfo = DefGetTracks(l);
      if (tracksinfo == NULL) {
	 // Should look at standard cell placement and LEF offset
	 // to determine offset here.  For now, just use 0.
	 hoff = voff = 0;
      }
      else {
	 // Use the start position relative to lowerbound to determine
	 // the offset.  use the offset of the higher or lower layer
	 // for determining the offset in the opposite direction of
	 // the current layer orientation.
	 if (l < Num_layers - 1) {
	    // If not the top layer, then use the upper layer as the other layer
	    tracksinfoother = DefGetTracks(l + 1);
	 }
	 else if (l > 0) {
	    // Otherwise, use the lower layer
	    tracksinfoother = DefGetTracks(l - 1);
         }
	 else {
	    // Should not happen, as it means routing is done with one layer. . .
	    tracksinfoother = (TRACKS)NULL;
	 }

	 if (Vert[l]) {
	    hoff = (int)((tracksinfo->start - Xlowerbound) / PitchX + 0.5);
	    voff = (tracksinfoother == (TRACKS)NULL) ?
		    0 : (int)((tracksinfoother->start - Ylowerbound) / PitchY + 0.5);
	 }
	 else {
	    voff = (int)((tracksinfo->start - Ylowerbound) / PitchY + 0.5);
	    hoff = (tracksinfoother == (TRACKS)NULL) ?
		    0 : (int)((tracksinfoother->start - Xlowerbound) / PitchX + 0.5);
	 }
      }

      // This could be better handled by restricting
      // access from specific directions rather than
      // marking a position as NO_NET.  Since the
      // routine below will mark no positions restricted
      // if either hnum is 1 or vnum is 1, regardless of
      // the other value, then we force both values to
      // be at least 2.

      if (vnum > 1 || hnum > 1) {
	 for (x = 0; x < NumChannelsX; x++) {
	    if ((x - hoff) % hnum == 0) continue;
	    for (y = 0; y < NumChannelsY; y++) {
	       if ((y - voff) % vnum == 0) continue;

	       // If the grid position itself is a node, don't restrict
	       // routing based on variable pitch.
	       if (((lnode = NODEIPTR(x, y, l)) != NULL) && (lnode->nodeloc != NULL))
		  continue;

	       // If there is a node in an adjacent grid then allow
	       // routing from that direction.

	       if ((x > 0) && ((lnode = NODEIPTR(x - 1, y, l)) != NULL) &&
			(lnode->nodeloc != NULL))
		  OBSVAL(x, y, l) = BLOCKED_MASK & ~BLOCKED_W;
	       else if ((y > 0) && ((lnode = NODEIPTR(x , y - 1, l)) != NULL) &&
			(lnode->nodeloc != NULL))
		  OBSVAL(x, y, l) = BLOCKED_MASK & ~BLOCKED_S;
	       else if ((x < NumChannelsX - 1)
			&& ((lnode = NODEIPTR(x + 1, y, l)) != NULL) &&
			(lnode->nodeloc != NULL))
		  OBSVAL(x, y, l) = BLOCKED_MASK & ~BLOCKED_E;
	       else if ((y < NumChannelsY - 1)
			&& ((lnode = NODEIPTR(x, y + 1, l)) != NULL) &&
			(lnode->nodeloc != NULL))
		  OBSVAL(x, y, l) = BLOCKED_MASK & ~BLOCKED_N;
	       else
		  OBSVAL(x, y, l) = NO_NET;
	    }
	 }
      }
   }
}

/*--------------------------------------------------------------*/
/* disable_gridpos() ---					*/
/*	Render the position at (x, y, lay) unroutable by	*/
/*	setting its Obs[] entry to NO_NET and removing it from	*/
/*	the Nodeinfo->nodeloc and Nodeinfo->nodesav records.	*/
/*--------------------------------------------------------------*/

static void
disable_gridpos(int x, int y, int lay)
{
    int apos = OGRID(x, y);

    Obs[lay][apos] = (u_int)(NO_NET | OBSTRUCT_MASK);
    if (Nodeinfo[lay][apos]) {
	free(Nodeinfo[lay][apos]);
	Nodeinfo[lay][apos] = NULL;
    }
}

/*--------------------------------------------------------------*/
/* count_pinlayers()---						*/
/*	Check which layers have non-NULL Nodeinfo entries.  	*/
/*	Then set "Pinlayers" and free all the unused layers.	*/
/* 	This saves a lot of memory, especially when the number	*/
/*	of routing layers becomes large.			*/ 
/*--------------------------------------------------------------*/

void
count_pinlayers(void)
{
   int j, l;

   Pinlayers = 0;
   for (l = 0; l < Num_layers; l++) {
      for (j = 0; j < NumChannelsX * NumChannelsY; j++) {
	 if (Nodeinfo[l][j]) {
	    Pinlayers = l + 1;
	    break;
	 }
      }
   }

   for (l = Pinlayers; l < Num_layers; l++) {
      free(Nodeinfo[l]);
      Nodeinfo[l] = NULL;
   }
}

/*--------------------------------------------------------------*/
/* check_obstruct()---						*/
/*	Called from create_obstructions_from_gates(), this	*/
/* 	routine takes a grid point at (gridx, gridy) (physical	*/
/* 	position (dx, dy)) and an obstruction defined by the	*/
/*	rectangle "ds", and sets flags and fills the Obsinfo	*/
/*	array to reflect how the obstruction affects routing to	*/
/*	the grid position.					*/
/*--------------------------------------------------------------*/

static void
check_obstruct(int gridx, int gridy, DSEG ds, double dx, double dy, double delta)
{
    u_int *obsptr;
    float dist;

    obsptr = &(OBSVAL(gridx, gridy, ds->layer));
    dist = OBSINFO(gridx, gridy, ds->layer);

    // Grid point is inside obstruction + halo.
    *obsptr |= NO_NET;

    // Completely inside obstruction?
    if (dy > ds->y1 && dy < ds->y2 && dx > ds->x1 && dx < ds->x2)
       *obsptr |= OBSTRUCT_MASK;

    else {
       // Make more detailed checks in each direction

       if (dy <= ds->y1) {
	  if ((*obsptr & (OBSTRUCT_MASK & ~OBSTRUCT_N)) == 0) {
	     if ((dist == 0) || ((ds->y1 - dy) < dist))
		OBSINFO(gridx, gridy, ds->layer) = ds->y1 - dy;
	     *obsptr |= OBSTRUCT_N;
	  }
	  else *obsptr |= OBSTRUCT_MASK;
       }
       else if (dy >= ds->y2) {
	  if ((*obsptr & (OBSTRUCT_MASK & ~OBSTRUCT_S)) == 0) {
	     if ((dist == 0) || ((dy - ds->y2) < dist))
		OBSINFO(gridx, gridy, ds->layer) = dy - ds->y2;
	     *obsptr |= OBSTRUCT_S;
	  }
	  else *obsptr |= OBSTRUCT_MASK;
       }

       if (dx <= ds->x1) {
	  if ((*obsptr & (OBSTRUCT_MASK & ~OBSTRUCT_E)) == 0) {
	     if ((dist == 0) || ((ds->x1 - dx) < dist))
		OBSINFO(gridx, gridy, ds->layer) = ds->x1 - dx;
             *obsptr |= OBSTRUCT_E;
	  }
	  else *obsptr |= OBSTRUCT_MASK;
       }
       else if (dx >= ds->x2) {
	  if ((*obsptr & (OBSTRUCT_MASK & ~OBSTRUCT_W)) == 0) {
	     if ((dist == 0) || ((dx - ds->x2) < dist))
		OBSINFO(gridx, gridy, ds->layer) = dx - ds->x2;
	     *obsptr |= OBSTRUCT_W;
	  }
	  else *obsptr |= OBSTRUCT_MASK;
       }
    }
}

/*--------------------------------------------------------------*/
/* Find the amount of clearance needed between an obstruction	*/
/* and a route track position.  This takes into consideration	*/
/* whether the obstruction is wide or narrow metal, if the	*/
/* spacing rules are graded according to metal width, and if a	*/
/* via placed at the position is or is not symmetric in X and Y	*/
/* "orient" is the via orientation, of which there are four;	*/
/* however, as this only concerns the via bottom layer, the	*/
/* two orientations are represented by orient = 0 and 2.	*/
/*--------------------------------------------------------------*/

static double get_via_clear(int lay, int horiz, int orient, DSEG rect) {
   double vdelta, v2delta, mdelta, mwidth;

   vdelta = LefGetXYViaWidth(lay, lay, 1 - horiz, orient);
   if (lay > 0) {
	v2delta = LefGetXYViaWidth(lay - 1, lay, 1 - horiz, orient);
	if (v2delta > vdelta) vdelta = v2delta;
   }
   vdelta = vdelta / 2.0;

   // Spacing rule is determined by the minimum metal width,
   // either in X or Y, regardless of the position of the
   // metal being checked.

   mwidth = MIN(rect->x2 - rect->x1, rect->y2 - rect->y1);
   mdelta = LefGetRouteWideSpacing(lay, mwidth);

   return vdelta + mdelta;
}

/*--------------------------------------------------------------*/
/* Find the distance from an obstruction to a grid point, 	*/
/* considering only routes which are placed at the position,	*/
/* not vias.							*/
/*--------------------------------------------------------------*/

static double get_route_clear(int lay, DSEG rect) {
   double rdelta, mdelta, mwidth;

   rdelta = LefGetRouteWidth(lay);
   rdelta = rdelta / 2.0;

   // Spacing rule is determined by the minimum metal width,
   // either in X or Y, regardless of the position of the
   // metal being checked.

   mwidth = MIN(rect->x2 - rect->x1, rect->y2 - rect->y1);
   mdelta = LefGetRouteWideSpacing(lay, mwidth);

   return rdelta + mdelta;
}

/*--------------------------------------------------------------*/
/* Truncate gates to the set of tracks.  Warn about any gates	*/
/* with nodes that are clipped entirely outside the routing	*/
/* area.							*/
/*--------------------------------------------------------------*/

void clip_gate_taps(void)
{
    NET net; 
    NODE node;
    DPOINT dp, dpl;
    int i, lay;

    for (i = 0; i < Numnets; i++) {
	net = Nlnets[i];
	for (node = net->netnodes; node; node = node->next) {
	    dpl = NULL;
	    for (dp = (DPOINT)node->taps; dp; ) {

		lay = dp->layer;

		if (dp->gridx < 0 || dp->gridy < 0 ||
			dp->gridx >= NumChannelsX ||
			dp->gridy >= NumChannelsY) {
		    Fprintf(stderr, "Tap of port of node %d of net %s"
			" is outside of route area\n",
			node->nodenum, node->netname);

		    if (dpl == NULL)
			node->taps = dp->next;
		    else
			dpl->next = dp->next;

		    free(dp);
		    dp = (dpl == NULL) ? node->taps : dpl->next;
		}
		else {
		    dpl = dp;
		    dp = dp->next;
		}
	    }
	}
    }
}

/*--------------------------------------------------------------*/
/* create_obstructions_from_gates()				*/
/*								*/
/*  Fills in the Obs[][] grid from obstructions that were	*/
/*  defined for each macro in the technology LEF file and	*/
/*  translated into a list of grid coordinates in each		*/
/*  instance.							*/
/*								*/
/*  Also, fills in the Obs[][] grid with obstructions that	*/
/*  are defined by nodes of the gate that are unconnected in	*/
/*  this netlist.						*/
/*--------------------------------------------------------------*/

void create_obstructions_from_gates(void)
{
    GATE g;
    DSEG ds;
    int i, gridx, gridy, orient;
    double deltax, deltay, delta[MAX_LAYERS];
    double dx, dy, deltaxy;

    // Give a single net number to all obstructions, over the range of the
    // number of known nets, so these positions cannot be routed through.
    // If a grid position is not wholly inside an obstruction, then we
    // maintain the direction of the nearest obstruction in Obs and the
    // distance to it in Obsinfo.  This indicates that a route can avoid
    // the obstruction by moving away from it by the amount in Obsinfo
    // plus spacing clearance.  If another obstruction is found that
    // prevents such a move, then all direction flags will be set, indicating
    // that the position is not routable under any condition. 

    for (g = Nlgates; g; g = g->next) {
       orient = 0;
       for (ds = g->obs;; ds = ds->next) {
	  // Run through ds list twice, checking against horizontally and
	  // vertically oriented vias.

	  if (ds == NULL) {
	     if (orient == 2)
		break;
	     else {
		orient = 2;
	 	ds = g->obs;
		if (ds == NULL) break;
	     }
	  }

	  deltax = get_via_clear(ds->layer, 1, orient, ds);
	  gridx = (int)((ds->x1 - Xlowerbound - deltax) / PitchX) - 1;
	  while (1) {
	     dx = (gridx * PitchX) + Xlowerbound;
	     if ((dx + EPS) > (ds->x2 + deltax)
			|| gridx >= NumChannelsX) break;
	     else if ((dx - EPS) > (ds->x1 - deltax) && gridx >= 0) {
		deltay = get_via_clear(ds->layer, 0, orient, ds);
	        gridy = (int)((ds->y1 - Ylowerbound - deltay) / PitchY) - 1;
	        while (1) {
		   dy = (gridy * PitchY) + Ylowerbound;
	           if ((dy + EPS) > (ds->y2 + deltay)
				|| gridy >= NumChannelsY) break;
		   if ((dy - EPS) > (ds->y1 - deltay) && gridy >= 0) {
		      double s, edist, xp, yp;

		      // Check Euclidean distance measure
		      s = LefGetRouteSpacing(ds->layer);

		      if (dx < (ds->x1 + s - deltax)) {
		         xp = dx + deltax - s;
			 edist = (ds->x1 - xp) * (ds->x1 - xp);
		      }
		      else if (dx > (ds->x2 - s + deltax)) {
		         xp = dx - deltax + s;
			 edist = (xp - ds->x2) * (xp - ds->x2);
		      }
		      else edist = 0;
		      if ((edist > 0) && (dy < (ds->y1 + s - deltay))) {
		         yp = dy + deltay - s;
			 edist += (ds->y1 - yp) * (ds->y1 - yp);
		      }
		      else if ((edist > 0) && (dy > (ds->y2 - s + deltay))) {
		         yp = dy - deltay + s;
			 edist += (yp - ds->y2) * (yp - ds->y2);
		      }
		      else edist = 0;

		      if ((edist + EPS) < (s * s)) {
			 check_obstruct(gridx, gridy, ds, dx, dy, s);
			 if (is_testpoint(gridx, gridy, g, -1, ds) != NULL)
			    Fprintf(stderr, " Position blocked by gate obstruction.\n");
		      }
		      else
			 edist = 0;	// diagnostic break
		   }
		   gridy++;
		}
	     }
	     gridx++;
	  }
       }

       for (i = 0; i < g->nodes; i++) {
	  if (g->netnum[i] == 0) {	/* Unconnected node */
	     // Diagnostic, and power bus handling
	     if (g->node[i]) {
		// Should we flag a warning if we see something that looks
		// like a power or ground net here?
		if (Verbose > 1)
		   Fprintf(stdout, "Gate instance %s unconnected node %s\n",
			g->gatename, g->node[i]);
	     }
	     else {
		if (Verbose > 1)
	           Fprintf(stdout, "Gate instance %s unconnected node (%d)\n",
			g->gatename, i);
	     }
             for (ds = g->taps[i]; ds; ds = ds->next) {

		deltax = get_via_clear(ds->layer, 1, orient, ds);
		gridx = (int)((ds->x1 - Xlowerbound - deltax) / PitchX) - 1;
		while (1) {
		   dx = (gridx * PitchX) + Xlowerbound;
		   if (dx > (ds->x2 + deltax)
				|| gridx >= NumChannelsX) break;
		   else if (dx >= (ds->x1 - deltax) && gridx >= 0) {
		      deltay = get_via_clear(ds->layer, 0, orient, ds);
		      gridy = (int)((ds->y1 - Ylowerbound - deltay) / PitchY) - 1;
		      while (1) {
		         dy = (gridy * PitchY) + Ylowerbound;
		         if ((dy + EPS) > (ds->y2 + deltay)
					|| gridy >= NumChannelsY) break;
		         if ((dy - EPS) >= (ds->y1 - deltay) && gridy >= 0) {

		            double s, edist = 0.0, xp, yp;

		            // Check Euclidean distance measure
		            s = LefGetRouteSpacing(ds->layer);

		            if (dx < (ds->x1 + s - deltax)) {
		               xp = dx + deltax - s;
			       edist += (ds->x1 - xp) * (ds->x1 - xp);
		            }
		            else if (dx > (ds->x2 - s + deltax)) {
		               xp = dx - deltax + s;
			       edist += (xp - ds->x2) * (xp - ds->x2);
		            }
			    else edist = 0;
		            if ((edist > 0) && (dy < (ds->y1 + s - deltay))) {
		               yp = dy + deltay - s;
			       edist += (ds->y1 - yp) * (ds->y1 - yp);
		            }
		            else if ((edist > 0) && (dy > (ds->y2 - s + deltay))) {
		               yp = dy - deltay + s;
			       edist += (yp - ds->y2) * (yp - ds->y2);
		            }
			    else edist = 0;

		            if ((edist + EPS) < (s * s)) {
			       check_obstruct(gridx, gridy, ds, dx, dy, s);
			       if (is_testpoint(gridx, gridy, g, i, ds) != NULL)
				  Fprintf(stderr, " Position blocked by unused"
					    " gate pin.\n");
			    }
			 }
		         gridy++;
		      }
		   }
		   gridx++;
		}
	     }
	  }
       }
    }

    // Create additional obstructions from the UserObs list
    // These obstructions are not considered to be metal layers,
    // so we don't compute a distance measure.  However, we need
    // to compute a boundary of 1/2 route width to avoid having
    // the route overlapping the obstruction area.

    for (i = 0; i < Num_layers; i++) {
	delta[i] = LefGetRouteWidth(i) / 2.0;
    }

    for (ds = UserObs; ds; ds = ds->next) {
	if (ds->layer >= Num_layers) continue;
	gridx = (int)((ds->x1 - Xlowerbound - delta[ds->layer]) / PitchX) - 1;
	while (1) {
	    dx = (gridx * PitchX) + Xlowerbound;
	    if (dx > (ds->x2 + delta[ds->layer])
			|| gridx >= NumChannelsX) break;
	    else if (dx >= (ds->x1 - delta[ds->layer]) && gridx >= 0) {
		gridy = (int)((ds->y1 - Ylowerbound - delta[ds->layer]) / PitchY) - 1;
		while (1) {
		    dy = (gridy * PitchY) + Ylowerbound;
		    if (dy > (ds->y2 + delta[ds->layer])
				|| gridy >= NumChannelsY) break;
		    if (dy >= (ds->y1 - delta[ds->layer]) && gridy >= 0) {
		       check_obstruct(gridx, gridy, ds, dx, dy, delta[i]);
		       if (is_testpoint(gridx, gridy, NULL, -1, ds) != NULL)
			  Fprintf(stderr, " Position blocked by defined obstruction.\n");
		    }

		    gridy++;
		}
	    }
	    gridx++;
	}
    }
}

/*--------------------------------------------------------------*/
/* expand_tap_geometry()					*/
/*								*/
/*  For each rectangle defining part of a gate terminal,	*/
/*  search the surrounding terminal geometry.  If the rectangle	*/
/*  can expand in any direction, then allow it to grow to the	*/
/*  maximum size.  This generates overlapping geometry for each	*/
/*  terminal, but avoids bad results for determining how to	*/
/*  route to a terminal point if the terminal is broken up into	*/
/*  numerous nonoverlapping rectangles.				*/
/*								*/
/*  Note that this is not foolproof.  It also needs a number of	*/
/*  enhancements.  For example, to expand east, other geometry	*/
/*  should be looked at in order of increasing left edge X	*/
/*  value, and so forth.					*/
/*--------------------------------------------------------------*/

void expand_tap_geometry(void)
{
    DSEG ds, ds2;
    GATE g;
    int i;
    u_char expanded;

    for (g = Nlgates; g; g = g->next) {
	for (i = 0; i < g->nodes; i++) {
	    if (g->netnum[i] == 0) continue;
	    if (g->taps == NULL) continue;

	    for (ds = g->taps[i]; ds; ds = ds->next) {
		expanded = TRUE;
		while (expanded == TRUE) {
		    expanded = FALSE;

		    for (ds2 = g->taps[i]; ds2; ds2 = ds2->next) {
		        if (ds == ds2) continue;
			if (ds->layer != ds2->layer) continue;
		    
		        if ((ds2->y1 <= ds->y1) && (ds2->y2 >= ds->y2)) {
			    // Expand east
			    if ((ds2->x1 > ds->x1) && (ds2->x1 <= ds->x2))
			        if (ds->x2 < ds2->x2) {
				    ds->x2 = ds2->x2;
				    expanded = TRUE;
			        }
		    
			    // Expand west
			    if ((ds2->x2 < ds->x2) && (ds2->x2 >= ds->x1))
			        if (ds->x1 > ds2->x1) {
				    ds->x1 = ds2->x1;
				    expanded = TRUE;
			        }
		        }
		    
		        if ((ds2->x1 <= ds->x1) && (ds2->x2 >= ds->x2)) {
			    // Expand north
			    if ((ds2->y1 > ds->y1) && (ds2->y1 <= ds->y2))
			        if (ds->y2 < ds2->y2) {
				    ds->y2 = ds2->y2;
				    expanded = TRUE;
			        }
		    
			    // Expand south
			    if ((ds2->y2 < ds->y2) && (ds2->y2 >= ds->y1))
			        if (ds->y1 > ds2->y1) {
				    ds->y1 = ds2->y1;
				    expanded = TRUE;
			        }
		        }
		    }
		}
	    }
	}
    }
}

/*--------------------------------------------------------------*/
/* is_testpoint()						*/
/*								*/
/*  Check if a grid position is on the testpoint list.  If so,	*/
/*  return the pointer to the testpoint structure.		*/
/*--------------------------------------------------------------*/

DPOINT
is_testpoint(int gridx, int gridy, GATE g, int nidx, DSEG ds)
{
    int layer;
    DPOINT trypoint;
    NODE node = NULL, onode;
    NODEINFO lnode;

    layer = ds->layer;
    for (trypoint = testpoint; trypoint; trypoint = trypoint->next) {
	if (trypoint->gridx == gridx && trypoint->gridy == gridy &&
		trypoint->layer == layer) {
	    Fprintf(stderr, "Watchpoint (%g, %g) layer %d"
		    " grid (%d, %d):\n",
		    trypoint->x, trypoint->y, trypoint->layer,
		    trypoint->gridx, trypoint->gridy); 
	    if (g != NULL) {
		Fprintf(stderr, "  Gate instance = \"%s\"\n", g->gatename);
		if (g->gatetype)
		    Fprintf(stderr, "  Gate cell = \"%s\"\n", g->gatetype->gatename);

		if (nidx >= 0) {
		    Fprintf(stderr, "  Gate pin = \"%s\"\n", g->node[nidx]);
		    Fprintf(stderr, "  Pin geometry = (%g, %g) to (%g, %g)\n",
			    ds->x1, ds->y1, ds->x2, ds->y2);
		    node = g->noderec[nidx];
		    Fprintf(stderr, "  Connects to net \"%s\"\n", node->netname);
		}
	    }
	    if (nidx < 0) {
		Fprintf(stderr, "  Obstruction geometry = (%g, %g) to (%g, %g)\n",
			ds->x1, ds->y1, ds->x2, ds->y2);
	    }
	    lnode = NODEIPTR(gridx, gridy, layer);
	    if (lnode != NULL) {
		onode = lnode->nodesav;
		if (onode != NULL) {
		    if (node && (onode->netnum != node->netnum)) {
			if (onode->netname)
			    Fprintf(stderr, "  Position was previously assigned"
				    " to node %s on net %s\n", print_node_name(onode),
				    onode->netname);
			else
			    Fprintf(stderr, "  Position was previously assigned"
				    " to node %s on different net\n",
				    print_node_name(onode));
		    }
		    else {
			Fprintf(stderr, "  Position was previously assigned"
			    " to node %s on the same net\n",
			    print_node_name(onode));
		    }
		}
		else Fprintf(stderr, "  Position was previously assigned"
			    " to a node that has been disabled.\n");
	    }
	    else Fprintf(stderr, "  Position was not previously assigned"
			    " to a node\n");

	    Fprintf(stderr, "Disabled position because:\n");
	    return trypoint;
	}
    }
    return NULL;
}

/*--------------------------------------------------------------*/
/* create_obstructions_inside_nodes()				*/
/*								*/
/*  Fills in the Obs[][] grid from the position of each node	*/
/*  (net terminal), which may have multiple unconnected		*/
/*  positions.							*/
/*								*/
/*  Also fills in the Nodeinfo.nodeloc[] grid with the node	*/
/*  number, which causes the router to put a premium on		*/
/*  routing other nets over or under this position, to		*/
/*  discourage boxing in a pin position and making it 		*/
/*  unroutable.							*/
/*								*/
/*  This routine is split into two passes.  This pass adds	*/
/*  information for points inside node regions.			*/
/*								*/
/*  ARGS: none.							*/
/*  RETURNS: nothing						*/
/*  SIDE EFFECTS: none						*/
/*  AUTHOR:  Tim Edwards, June 2011, based on code by Steve	*/
/*	Beccue.							*/
/*--------------------------------------------------------------*/

void create_obstructions_inside_nodes(void)
{
    NODE node;
    NODEINFO lnode;
    GATE g;
    DSEG ds;
    DPOINT tpoint;
    u_int dir, mask, k;
    int i, gridx, gridy;
    double dx, dy, xdist, vwx, vwy;
    u_char o0okay, o2okay, duplicate;
    float dist;

    // For each node terminal (gate pin), mark each grid position with the
    // net number.  This overrides any obstruction that may be placed at that
    // point.

    // For each pin position, we also find the "keepout" area around the
    // pin where we may not place an unrelated route.  For this, we use a
    // flag bit, so that the position can be ignored when routing the net
    // associated with the pin.  Normal obstructions take precedence.

    for (g = Nlgates; g; g = g->next) {
       for (i = 0; i < g->nodes; i++) {
	  if (g->netnum[i] != 0) {

	     // Get the node record associated with this pin.
	     node = g->noderec[i];
	     if (node == NULL) continue;

	     // First mark all areas inside node geometry boundary.

             for (ds = g->taps[i]; ds; ds = ds->next) {
		gridx = (int)((ds->x1 - Xlowerbound) / PitchX) - 1;
		if (gridx < 0) gridx = 0;
		while (1) {
		   dx = (gridx * PitchX) + Xlowerbound;
		   if (dx > ds->x2 || gridx >= NumChannelsX) break;
		   else if (dx >= ds->x1 && gridx >= 0) {
		      gridy = (int)((ds->y1 - Ylowerbound) / PitchY) - 1;
		      if (gridy < 0) gridy = 0;
		      while (1) {
		         dy = (gridy * PitchY) + Ylowerbound;
		         if (dy > ds->y2 || gridy >= NumChannelsY) break;

			 // Area inside defined pin geometry

			 if (dy > ds->y1 && gridy >= 0) {
			     int orignet = OBSVAL(gridx, gridy, ds->layer);

			     duplicate = FALSE;
			     lnode = NULL;
			     if ((orignet & ROUTED_NET_MASK & ~ROUTED_NET)
					== (u_int)node->netnum) {

				// Duplicate tap point, or pre-existing route.
				// Re-process carefully.  Check for alternate
				// restrictions.  This geometry may be better
				// than the last one(s) processed.

				if (((lnode = NODEIPTR(gridx, gridy, ds->layer)) != NULL)
					&& (lnode->nodeloc != NULL))
				    duplicate = TRUE;
			     }

			     else if (!(orignet & NO_NET) &&
					((orignet & ROUTED_NET_MASK) != (u_int)0)) {

				// Net was assigned to other net, but is inside
				// this pin's geometry.  Declare point to be
				// unroutable, as it is too close to both pins.
				// NOTE:  This is a conservative rule and could
				// potentially make a pin unroutable.
				// Another note:  By setting Obs[] to
				// OBSTRUCT_MASK as well as NO_NET, we ensure
				// that it falls through on all subsequent
				// processing.

				if (is_testpoint(gridx, gridy, g, i, ds) != NULL)
				    Fprintf(stderr, " Position is inside pin but cannot "
					    "be routed without causing violation.\n");
				disable_gridpos(gridx, gridy, ds->layer);
				gridy++;
				continue;
			     }

			     if (!(orignet & NO_NET)) {

				// A grid point that is within 1/2 route width
				// of a tap rectangle corner can violate metal
				// width rules, and so should declare a stub.
				
				mask = 0;
				dir = 0;
				dist = 0.0;
			        xdist = 0.5 * LefGetRouteWidth(ds->layer);

				if (dx >= ds->x2 - xdist) {
				   if (dy > ds->y2 - xdist + EPS) {
				      // Check northeast corner

				      if ((ds->x2 - dx) > (ds->y2 - dy)) {
					 // West-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x2 - dx - 2.0 * xdist;
				      }
				      else {
					 // South-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y2 - dy - 2.0 * xdist;
				      }

				   }
				   else if (dy < ds->y1 + xdist - EPS) {
				      // Check southeast corner

				      if ((ds->x2 - dx) > (dy - ds->y1)) {
					 // West-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x2 - dx - 2.0 * xdist;
				      }
				      else {
					 // North-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y1 - dy + 2.0 * xdist;
				      }
				   }
				}
				else if (dx <= ds->x1 + xdist) {
				   if (dy > ds->y2 - xdist + EPS) {
				      // Check northwest corner

				      if ((dx - ds->x1) > (ds->y2 - dy)) {
					 // East-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x1 - dx + 2.0 * xdist;
				      }
				      else {
					 // South-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y2 - dy - 2.0 * xdist;
				      }

				   }
				   else if (dy < ds->y1 + xdist - EPS) {
				      // Check southwest corner

				      if ((dx - ds->x2) > (dy - ds->y1)) {
					 // East-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x1 - dx + 2.0 * xdist;
				      }
				      else {
					 // North-pointing stub
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y1 - dy + 2.0 * xdist;
				      }
				   }
				}

				if (!duplicate) {
			           OBSVAL(gridx, gridy, ds->layer)
			        	= (OBSVAL(gridx, gridy, ds->layer)
					   & BLOCKED_MASK) | (u_int)node->netnum | mask;
				   if (!lnode)
				      lnode = SetNodeinfo(gridx, gridy, ds->layer,
						node);
				   lnode->nodeloc = node;
				   lnode->nodesav = node;
				   lnode->stub = dist;
				   lnode->flags |= dir;
				}

				/* If a horizontal or vertical via fits completely */
				/* inside the pin but the other orientation	   */
				/* doesn't, then mark as prohibiting the other	   */
				/* orientation.					   */

				vwx = LefGetXYViaWidth(ds->layer, ds->layer, 0, 0) / 2.0;
				vwy = LefGetXYViaWidth(ds->layer, ds->layer, 1, 0) / 2.0;
				if ((dx - vwx > ds->x1 - EPS) &&
					(dx + vwx < ds->x2 + EPS) &&
				    	(dy - vwy > ds->y1 - EPS) &&
					(dy + vwy < ds->y2 + EPS)) {
				    o0okay = TRUE;
				} else {
				    o0okay = FALSE;
				}
				vwx = LefGetXYViaWidth(ds->layer, ds->layer, 0, 2) / 2.0;
				vwy = LefGetXYViaWidth(ds->layer, ds->layer, 1, 2) / 2.0;
				if ((dx - vwx > ds->x1 - EPS) &&
					(dx + vwx < ds->x2 + EPS) &&
				    	(dy - vwy > ds->y1 - EPS) &&
					(dy + vwy < ds->y2 + EPS)) {
				    o2okay = TRUE;
				} else {
				    o2okay = FALSE;
				}
				if ((o0okay == TRUE) && (o2okay == FALSE))
				    lnode->flags |= NI_NO_VIAY;
				else if ((o0okay == FALSE) && (o2okay == TRUE))
				    lnode->flags |= NI_NO_VIAX;
			     }
			     else if ((orignet & NO_NET) && ((orignet & OBSTRUCT_MASK)
					!= OBSTRUCT_MASK)) {
				/* Handled on next pass */
			     }

			     // Check that we have not created a PINOBSTRUCT
			     // route directly over this point.
			     if ((!duplicate) && (ds->layer < Num_layers - 1)) {
			        k = OBSVAL(gridx, gridy, ds->layer + 1);
			        if (k & PINOBSTRUCTMASK) {
			           if ((k & ROUTED_NET_MASK) != (u_int)node->netnum) {
				       OBSVAL(gridx, gridy, ds->layer + 1) = NO_NET;
				       FreeNodeinfo(gridx, gridy, ds->layer + 1);
				   }
				}
			     }
			 }
		         gridy++;
		      }
		   }
		   gridx++;
		}
	     }
	  }
       }
    }

} /* void create_obstructions_inside_nodes( void ) */

/*--------------------------------------------------------------*/
/* create_obstructions_outside_nodes()				*/
/*								*/
/*  Fills in the Obs[][] grid from the position of each node	*/
/*  (net terminal), which may have multiple unconnected		*/
/*  positions.							*/
/*								*/
/*  Also fills in the Nodeinfo.nodeloc[] grid with the node	*/
/*  number, which causes the router to put a premium on		*/
/*  routing other nets over or under this position, to		*/
/*  discourage boxing in a pin position and making it 		*/
/*  unroutable.							*/
/*								*/
/*  This routine is split into two passes.  This pass adds	*/
/*  information for points outside node regions but close	*/
/*  enough to interact with the node.				*/
/*								*/
/*  ARGS: none.							*/
/*  RETURNS: nothing						*/
/*  SIDE EFFECTS: none						*/
/*  AUTHOR:  Tim Edwards, June 2011, based on code by Steve	*/
/*	Beccue.							*/
/*--------------------------------------------------------------*/


void create_obstructions_outside_nodes(void)
{
    NODE node, n2;
    NODEINFO lnode;
    GATE g;
    DSEG ds;
    DPOINT tpoint;
    u_int dir, mask, k;
    int i, gridx, gridy, orient;
    double dx, dy, xdist, deltax, deltay;
    float dist;

    // For each node terminal (gate pin), mark each grid position with the
    // net number.  This overrides any obstruction that may be placed at that
    // point.

    // For each pin position, we also find the "keepout" area around the
    // pin where we may not place an unrelated route.  For this, we use a
    // flag bit, so that the position can be ignored when routing the net
    // associated with the pin.  Normal obstructions take precedence.

    for (g = Nlgates; g; g = g->next) {
       for (i = 0; i < g->nodes; i++) {
	  if (g->netnum[i] != 0) {

	     // Get the node record associated with this pin.
	     node = g->noderec[i];
	     if (node == NULL) continue;

	     // Repeat this whole exercise for areas in the halo outside
	     // the node geometry.  We have to do this after enumerating
	     // all inside areas because the tap rectangles often overlap,
	     // and one rectangle's halo may be inside another tap.

	     orient = 0;
             for (ds = g->taps[i];; ds = ds->next) {
		if (ds == NULL) {
		    if (orient == 2)
			break;
		    else {
			orient = 2;
			ds = g->taps[i];
			if (ds == NULL) break;
		    }
		}

		// Note:  Should be handling get_route_clear as a less
		// restrictive case, as was done above.
 
		deltax = get_via_clear(ds->layer, 1, orient, ds);
		gridx = (int)((ds->x1 - Xlowerbound - deltax) / PitchX) - 1;
		if (gridx < 0) gridx = 0;

		while (1) {
		   dx = (gridx * PitchX) + Xlowerbound;

		   // Check if obstruction position is too close for
		   // a via in either orientation.  The position can
		   // be marked as prohibiting one orientation or the
		   // other.

		   if (((dx + EPS) > (ds->x2 + deltax)) ||
				(gridx >= NumChannelsX))
		      break;

		   else if ((dx - EPS) > (ds->x1 - deltax) && gridx >= 0) {
		      deltay = get_via_clear(ds->layer, 0, orient, ds);
		      gridy = (int)((ds->y1 - Ylowerbound - deltay) / PitchY) - 1;
		      if (gridy < 0) gridy = 0;

		      while (1) {
		         dy = (gridy * PitchY) + Ylowerbound;

		         if (((dy + EPS) > (ds->y2 + deltay)) ||
				(gridy >= NumChannelsY))
			    break;

			 // 2nd pass on area inside defined pin geometry,
			 // allowing terminal connections to be made using
			 // an offset tap, where possible.

			 if ((dy >= ds->y1 && gridy >= 0) && (dx >= ds->x1)
					&& (dy <= ds->y2) && (dx <= ds->x2)) {
			     int orignet = OBSVAL(gridx, gridy, ds->layer);

			     if ((orignet & ROUTED_NET_MASK) == (u_int)node->netnum) {

				// Duplicate tap point.   Don't re-process it.
				gridy++;
				continue;
			     }

			     if (!(orignet & NO_NET) &&
					((orignet & ROUTED_NET_MASK) != (u_int)0)) {
				/* Do nothing;  previously handled */
			     }

			     else if ((orignet & NO_NET) && ((orignet & OBSTRUCT_MASK)
					!= OBSTRUCT_MASK)) {
				double sdistxx, sdistxy, sdistyx, sdistyy, offd;

				sdistxx = LefGetXYViaWidth(ds->layer, ds->layer,
					0, 0) / 2.0 +
					LefGetRouteSpacing(ds->layer);
				sdistxy = LefGetXYViaWidth(ds->layer, ds->layer,
					0, 2) / 2.0 +
					LefGetRouteSpacing(ds->layer);
				sdistyx = LefGetXYViaWidth(ds->layer, ds->layer,
					1, 0) / 2.0 +
					LefGetRouteSpacing(ds->layer);
				sdistyy = LefGetXYViaWidth(ds->layer, ds->layer,
					1, 2) / 2.0 +
					LefGetRouteSpacing(ds->layer);

				// Define a maximum offset we can have in X or
				// Y above which the placement of a via will
				// cause a DRC violation with a wire in the
				// adjacent route track in the direction of the
				// offset.

				int maxerr = 0;

				// If a cell is positioned off-grid, then a grid
				// point may be inside a pin and still be unroutable.
				// The Obsinfo[] array tells where an obstruction is,
				// if there was only one obstruction in one direction
				// blocking the grid point.  If so, then we set the
				// Nodeinfo.stub[] distance to move the tap away from
				// the obstruction to resolve the DRC error.

				// Make sure we have marked this as a node.
				lnode = SetNodeinfo(gridx, gridy, ds->layer, node);
				lnode->nodeloc = node;
				lnode->nodesav = node;
			        OBSVAL(gridx, gridy, ds->layer)
			        	= (OBSVAL(gridx, gridy, ds->layer)
					   & BLOCKED_MASK) | (u_int)node->netnum;

			        offd = OBSINFO(gridx, gridy, ds->layer);
				if (orignet & OBSTRUCT_N) {
				   if (sdistyy - offd > EPS) {
				      lnode->flags |= NI_NO_VIAY;
				      if (sdistyx - offd > EPS) {
					 /* Cannot route cleanly, so use offset */
				         if (offd - sdistyx > PitchX / 2.0) 
					    /* Offset distance is too large */
					    maxerr = 1;
					 else {

			                    OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				            lnode->offset = offd - sdistyx;
				            lnode->flags |= NI_OFFSET_NS;

				            /* If position above has obstruction, then */
				            /* add up/down block to prevent vias.      */

				            if ((ds->layer < Num_layers - 1) &&
							(gridy > 0) &&
							(OBSVAL(gridx, gridy - 1,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
				   }
				}
				else if (orignet & OBSTRUCT_S) {
				   if (sdistyy - offd > EPS) {
				      lnode->flags |= NI_NO_VIAY;
				      if (sdistyx - offd > EPS) {
				         if (offd - sdistyx > PitchX / 2.0)
					    /* Offset distance is too large */
					    maxerr = 1;
					 else {
			                    OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				            lnode->offset = sdistyx - offd;
				            lnode->flags |= NI_OFFSET_NS;

				            /* If position above has obstruction, then */
				            /* add up/down block to prevent vias.      */

				             if ((ds->layer < Num_layers - 1) &&
							(gridy < NumChannelsY - 1) &&
						   	(OBSVAL(gridx, gridy + 1,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					        block_route(gridx, gridy, ds->layer, UP);
					     }
					 }
				      }
				   }
				}
				else if (orignet & OBSTRUCT_E) {
				   if (sdistxx - offd > EPS) {
				      lnode->flags |= NI_NO_VIAX;
				      if (sdistxy - offd > EPS) {
				         if (offd - sdistxy > PitchY / 2.0)
					    /* Offset distance is too large */
					    maxerr = 1;
					 else {
			                    OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				            lnode->offset = offd - sdistxy;
				            lnode->flags |= NI_OFFSET_EW;

				            /* If position above has obstruction, then */
				            /* add up/down block to prevent vias.      */

				             if ((ds->layer < Num_layers - 1) &&
							(gridx > 0) &&
							(OBSVAL(gridx - 1, gridy,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					        block_route(gridx, gridy, ds->layer, UP);
					     }
					 }
				      }
				   }
				}
				else if (orignet & OBSTRUCT_W) {
				   if (sdistxx - offd > EPS) {
				      lnode->flags |= NI_NO_VIAX;
				      if (sdistxy - offd > EPS) {
				         if (offd - sdistxy > PitchY / 2.0)
					    /* Offset distance is too large */
					    maxerr = 1;
					 else {
			                    OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				            lnode->offset = sdistxy - offd;
				            lnode->flags |= NI_OFFSET_EW;

				            /* If position above has obstruction, then */
				            /* add up/down block to prevent vias.      */

				            if ((ds->layer < Num_layers - 1) &&
							(gridx < NumChannelsX - 1) &&
							(OBSVAL(gridx + 1, gridy,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
				   }
				}

			        if (maxerr == 1) {
				    if (is_testpoint(gridx, gridy, g, i, ds) != NULL)
					Fprintf(stderr,
					    "Attempted to clear obstruction with"
					    " offset, but offset is more than 1/2"
					    " route pitch.\n");
				    disable_gridpos(gridx, gridy, ds->layer);
				}

				// Diagnostic
				else if (Verbose > 3)
				   Fprintf(stderr, "Port overlaps obstruction"
					" at grid %d %d, position %g %g\n",
					gridx, gridy, dx, dy);
			     }
			 }

		         if ((dy - EPS) > (ds->y1 - deltay) && gridy >= 0) {

			    double s, edist, xp, yp;
			    unsigned char epass = 0;

			    // Area inside halo around defined pin geometry.
			    // Exclude areas already processed (areas inside
			    // some pin geometry have been marked with netnum)

			    // Also check that we are not about to define a
			    // route position for a pin on a layer above 0 that
			    // blocks a pin underneath it.

			    // Flag positions that pass a Euclidean distance check.
			    // epass = 1 indicates that position clears a
			    // Euclidean distance measurement.

			    s = LefGetRouteSpacing(ds->layer);

			    if (dx < (ds->x1 + s - deltax)) {
				xp = dx + deltax - s;
				edist = (ds->x1 - xp) * (ds->x1 - xp);
			    }
			    else if (dx > (ds->x2 - s + deltax)) {
				xp = dx - deltax + s;
				edist = (xp - ds->x2) * (xp - ds->x2);
			    }
			    else edist = 0;
			    if ((edist > 0) && (dy < (ds->y1 + s - deltay))) {
				yp = dy + deltay - s;
				edist += (ds->y1 - yp) * (ds->y1 - yp);
			    }
			    else if ((edist > 0) && (dy > (ds->y2 - s + deltay))) {
				yp = dy - deltay + s;
				edist += (yp - ds->y2) * (yp - ds->y2);
			    }
			    else edist = 0;
			    if ((edist + EPS) > (s * s)) epass = 1;

			    xdist = 0.5 * LefGetRouteWidth(ds->layer);

			    n2 = NULL;
			    if (ds->layer > 0) {
			       lnode = NODEIPTR(gridx, gridy, ds->layer - 1);
			       n2 = (lnode) ? lnode->nodeloc : NULL;
			    }
			    if (n2 == NULL) {
			       lnode = NODEIPTR(gridx, gridy, ds->layer);
			       n2 = (lnode) ? lnode->nodeloc : NULL;
			    }
			    else {
			       // Watch out for the case where a tap crosses
			       // over a different tap.  Don't treat the tap
			       // on top as if it is not there!

			       NODE n3;
			       lnode = NODEIPTR(gridx, gridy, ds->layer);
			       n3 = (lnode) ? lnode->nodeloc : NULL;
			       if (n3 != NULL && n3 != node) n2 = n3;
			    }

			    // Ignore my own node.
			    if (n2 == node) n2 = NULL;

			    k = OBSVAL(gridx, gridy, ds->layer);

			    // In case of a port that is inaccessible from a grid
			    // point, or not completely overlapping it, the
			    // stub information will show how to adjust the
			    // route position to cleanly attach to the port.

			    mask = STUBROUTE;
			    dir = NI_STUB_NS | NI_STUB_EW;
			    dist = 0.0;

			    if (((k & ROUTED_NET_MASK) != (u_int)node->netnum)
					&& (n2 == NULL)) {

				if ((k & OBSTRUCT_MASK) != 0) {
				   float sdist = OBSINFO(gridx, gridy, ds->layer);

				   // If the point is marked as close to an
				   // obstruction, we can declare this an
				   // offset tap if we are not on a corner.
				   // Because we cannot define both an offset
				   // and a stub simultaneously, if the distance
				   // to clear the obstruction does not make the
				   // route reach the tap, then we mark the grid
				   // position as unroutable.

				   if (dy >= (ds->y1 - xdist) &&
						dy <= (ds->y2 + xdist)) {
				      if ((dx >= ds->x2) &&
						((k & OBSTRUCT_MASK) == OBSTRUCT_E)) {
				         dist = sdist - LefGetRouteKeepout(ds->layer);
					 if ((dx - ds->x2 + dist) < xdist) {
				 	    mask = OFFSET_TAP;
				 	    dir = NI_OFFSET_EW;

				            if ((ds->layer < Num_layers - 1) &&
							(gridx > 0) &&
							(OBSVAL(gridx - 1, gridy,
							ds->layer + 1)
							& OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
				      else if ((dx <= ds->x1) &&
						((k & OBSTRUCT_MASK) == OBSTRUCT_W)) {
				         dist = LefGetRouteKeepout(ds->layer) - sdist;
					 if ((ds->x1 - dx - dist) < xdist) {
				 	    mask = OFFSET_TAP;
				            dir = NI_OFFSET_EW;

				            if ((ds->layer < Num_layers - 1) &&
							gridx <
							(NumChannelsX - 1)
							&& (OBSVAL(gridx + 1, gridy,
							ds->layer + 1)
							& OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
			 	   }	
				   if (dx >= (ds->x1 - xdist) &&
						dx <= (ds->x2 + xdist)) {
				      if ((dy >= ds->y2) &&
						((k & OBSTRUCT_MASK) == OBSTRUCT_N)) {
				         dist = sdist - LefGetRouteKeepout(ds->layer);
					 if ((dy - ds->y2 + dist) < xdist) {
				 	    mask = OFFSET_TAP;
				            dir = NI_OFFSET_NS;

				            if ((ds->layer < Num_layers - 1) &&
							gridy < 
							(NumChannelsY - 1)
							&& (OBSVAL(gridx, gridy - 1,
							ds->layer + 1)
							& OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
				      else if ((dy <= ds->y1) &&
						((k & OBSTRUCT_MASK) == OBSTRUCT_S)) {
				         dist = LefGetRouteKeepout(ds->layer) - sdist;
					 if ((ds->y1 - dy - dist) < xdist) {
				 	    mask = OFFSET_TAP;
				            dir = NI_OFFSET_NS;

				            if ((ds->layer < Num_layers - 1) &&
							(gridy > 0) &&
							(OBSVAL(gridx, gridy + 1,
							ds->layer + 1)
							& OBSTRUCT_MASK)) {
					       block_route(gridx, gridy, ds->layer, UP);
					    }
					 }
				      }
				   }
				   // Otherwise, dir is left as NI_STUB_MASK
				}
				else {

				   // Cleanly unobstructed area.  Define stub
				   // route from point to tap, with a route width
				   // overlap if necessary to avoid a DRC width
				   // violation.

				   if ((dx >= ds->x2) &&
					((dx - ds->x2) > (dy - ds->y2)) &&
					((dx - ds->x2) > (ds->y1 - dy))) {
				      // West-pointing stub
				      if ((dy - ds->y2) <= xdist &&
					  (ds->y1 - dy) <= xdist) {
					 // Within reach of tap rectangle
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x2 - dx;
					 if (dy < (ds->y2 - xdist) &&
						dy > (ds->y1 + xdist)) {
					    if (dx < ds->x2 + xdist) dist = 0.0;
					 }
					 else {
					    dist -= 2.0 * xdist;
					 }
				      }
				   }
				   else if ((dx <= ds->x1) &&
					((ds->x1 - dx) > (dy - ds->y2)) &&
					((ds->x1 - dx) > (ds->y1 - dy))) {
				      // East-pointing stub
				      if ((dy - ds->y2) <= xdist &&
					  (ds->y1 - dy) <= xdist) {
					 // Within reach of tap rectangle
					 mask = STUBROUTE;
					 dir = NI_STUB_EW;
					 dist = ds->x1 - dx;
					 if (dy < (ds->y2 - xdist) &&
						dy > (ds->y1 + xdist)) {
					    if (dx > ds->x1 - xdist) dist = 0.0;
					 }
					 else {
					    dist += 2.0 * xdist;
					 }
				      }
				   }
				   else if ((dy >= ds->y2) &&
					((dy - ds->y2) > (dx - ds->x2)) &&
					((dy - ds->y2) > (ds->x1 - dx))) {
				      // South-pointing stub
				      if ((dx - ds->x2) <= xdist &&
					  (ds->x1 - dx) <= xdist) {
					 // Within reach of tap rectangle
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y2 - dy;
					 if (dx < (ds->x2 - xdist) &&
						dx > (ds->x1 + xdist)) {
					    if (dy < ds->y2 + xdist) dist = 0.0;
					 }
					 else {
					    dist -= 2.0 * xdist;
					 }
				      }
				   }
				   else if ((dy <= ds->y1) &&
					((ds->y1 - dy) > (dx - ds->x2)) &&
					((ds->y1 - dy) > (ds->x1 - dx))) {
				      // North-pointing stub
				      if ((dx - ds->x2) <= xdist &&
					  (ds->x1 - dx) <= xdist) {
					 // Within reach of tap rectangle
					 mask = STUBROUTE;
					 dir = NI_STUB_NS;
					 dist = ds->y1 - dy;
					 if (dx < (ds->x2 - xdist) &&
						dx > (ds->x1 + xdist)) {
					    if (dy > ds->y1 - xdist) dist = 0.0;
					 }
					 else {
					    dist += 2.0 * xdist;
					 }
				      }
				   }

				   if ((mask == STUBROUTE) && (dir == NI_STUB_MASK)) {

				      // Outside of pin at a corner.  First, if one
				      // direction is too far away to connect to a
				      // pin, then we must route the other direction.

				      if (dx < ds->x1 - xdist || dx > ds->x2 + xdist) {
				         if (dy >= ds->y1 - xdist &&
							dy <= ds->y2 + xdist) {
					    mask = STUBROUTE;
				            dir = NI_STUB_EW;
				            dist = (float)(((ds->x1 + ds->x2) / 2.0)
							- dx);
					 }
				      }
				      else if (dy < ds->y1 - xdist ||
							dy > ds->y2 + xdist) {
					 mask = STUBROUTE;
				         dir = NI_STUB_NS;
				         dist = (float)(((ds->y1 + ds->y2) / 2.0) - dy);
				      }

				      // Otherwise we are too far away at a diagonal
				      // to reach the pin by moving in any single
				      // direction.  To be pedantic, we could define
				      // some jogged stub, but for now, we just call
				      // the point unroutable (leave dir = NI_STUB_MASK)

				      // To do:  Apply offset + stub
				   }
				}

				// Additional checks on stub routes

				// Stub distances of <= 1/2 route width are
				// unnecessary, so don't create them.

				if (mask == STUBROUTE && (dir == NI_STUB_NS
					|| dir == NI_STUB_EW) &&
					(fabs(dist) < (xdist + EPS))) {
				    mask = 0;
				    dir = 0;
				    dist = 0.0;
				}
				else if (mask == STUBROUTE && (dir == NI_STUB_NS
					|| dir == NI_STUB_EW)) {
				   struct dseg_ de;
				   DSEG ds2;
				   u_char errbox = TRUE;

				   // Additional check:  Sometimes the above
				   // checks put stub routes where they are
				   // not needed because the stub is completely
				   // covered by other tap geometry.  Take the
				   // stub area and remove parts covered by
				   // other tap rectangles.  If the entire
				   // stub is gone, then don't put a stub here.

				   if (dir == NI_STUB_NS) {
				       de.x1 = dx - xdist;
				       de.x2 = dx + xdist;
				       if (dist > 0) {
					  de.y1 = dy + xdist;
					  de.y2 = dy + dist;
				       }
				       else {
					  de.y1 = dy + dist;
					  de.y2 = dy - xdist;
				       }
				   }
				   if (dir == NI_STUB_EW) {
				       de.y1 = dy - xdist;
				       de.y2 = dy + xdist;
				       if (dist > 0) {
					  de.x1 = dx + xdist;
					  de.x2 = dx + dist;
				       }
				       else {
					  de.x1 = dx + dist;
					  de.x2 = dx - xdist;
				       }
				   }

				   // For any tap that overlaps the
				   // stub extension box, remove that
				   // part of the box.

			           for (ds2 = g->taps[i]; ds2; ds2 = ds2->next) {
				      if (ds2 == ds) continue;
				      if (ds2->layer != ds->layer) continue;

				      if (ds2->x1 <= de.x1 && ds2->x2 >= de.x2 &&
						ds2->y1 <= de.y1 && ds2->y2 >= de.y2) {
				         errbox = FALSE;	// Completely covered
				         break;
				      }

				      // Look for partial coverage.  Note that any
				      // change can cause a change in the original
				      // two conditionals, so we have to keep
				      // evaluating those conditionals.

				      // ds2 covers left side of de
				      if (ds2->x1 < de.x2 && ds2->x2 > de.x1 + EPS)
				         if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					    if (ds2->x1 < de.x1 + EPS &&
							ds2->x2 < de.x2 - EPS) {
					       de.x1 = ds2->x2;
					       if (de.x1 > de.x2 - EPS) errbox = FALSE;
					    }

				      // ds2 covers right side of de
				      if (ds2->x1 < de.x2 - EPS && ds2->x2 > de.x1)
				         if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					    if (ds2->x2 > de.x2 - EPS &&
							ds2->x1 > de.x1 + EPS) {
					       de.x2 = ds2->x1;
					       if (de.x2 < de.x1 + EPS) errbox = FALSE;
					    }

				      // ds2 covers bottom side of de
				      if (ds2->y1 < de.y2 && ds2->y2 > de.y1 + EPS)
				         if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
					    if (ds2->y1 < de.y1 + EPS &&
							ds2->y2 < de.y2 - EPS) {
					       de.y1 = ds2->y2;
					       if (de.y1 > de.y2 - EPS) errbox = FALSE;
					    }

				      // ds2 covers top side of de
				      if (ds2->y1 < de.y2 - EPS && ds2->y2 > de.y1)
				         if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
					    if (ds2->y2 > de.y2 - EPS &&
							ds2->y1 > de.y1 + EPS) {
					       de.y2 = ds2->y1;
					       if (de.y2 < de.y1 + EPS) errbox = FALSE;
					    }
			           }

				   // If nothing is left of the stub box,
				   // then remove the stub.

				   if (errbox == FALSE) {
				      mask = 0;
				      dir = 0;
				      dist = 0;
				   }
                                }

				lnode = SetNodeinfo(gridx, gridy, ds->layer, node);
				lnode->nodeloc = node;
				lnode->nodesav = node;

				if ((k < Numnets) && (dir != NI_STUB_MASK)) {
				   OBSVAL(gridx, gridy, ds->layer)
				   	= (OBSVAL(gridx, gridy, ds->layer)
					  & BLOCKED_MASK) | (u_int)g->netnum[i] | mask; 
				   lnode->flags |= dir;
				}
				else if ((OBSVAL(gridx, gridy, ds->layer)
					& NO_NET) != 0) {
				   // Keep showing an obstruction, but add the
				   // direction info and log the stub distance.
				   OBSVAL(gridx, gridy, ds->layer) |= mask;
				   lnode->flags |= dir;
				}
				else {
				   OBSVAL(gridx, gridy, ds->layer)
					|= (mask | (g->netnum[i] & ROUTED_NET_MASK));
				   lnode->flags |= dir;
				}
				if ((mask & STUBROUTE) != 0) {
				   lnode->stub = dist;
				}
				else if (((mask & OFFSET_TAP) != 0) || (dist != 0.0)) {
				   lnode->offset = dist;
				}
				
				// Remove entries with NI_STUB_MASK---these
				// are blocked-in taps that are not routable
				// without causing DRC violations (formerly
				// called STUBROUTE_X).

				if (dir == NI_STUB_MASK) {
				    if (is_testpoint(gridx, gridy, g, i, ds) != NULL)
					Fprintf(stderr, "Tap point is blocked in "
					    "and cannot be routed without causing "
					    "DRC violations.\n");
				    disable_gridpos(gridx, gridy, ds->layer);
				}
			    }
			    else if (epass == 0) {

			       // Position fails euclidean distance check

			       int othernet = (k & ROUTED_NET_MASK);

			       if (othernet != 0 && othernet != (u_int)node->netnum) {

			          // This location is too close to two different
				  // node terminals and should not be used

				  // If there is a stub, then we can't specify
				  // an offset tap, so just disable it.  If
				  // there is already an offset, then just
				  // disable it.  Otherwise, check if othernet
				  // could be routed using a tap offset.

				  // To avoid having to check all nearby
				  // geometry, place a restriction that the
				  // next grid point in the direction of the
				  // offset must be free (not a tap point of
				  // any net, including this one).  That is
				  // still "more restrictive than necessary",
				  // but since the alternative is an efficient
				  // area search for interacting geometry, this
				  // restriction will stand until an example
				  // comes along that requires the detailed
				  // search.

				  // Such an example has come along, leading to
				  // an additional relaxation allowing an offset
				  // if the neighboring channel does not have a
				  // node record.  This will probably need
				  // revisiting.
				
				  if ((k & PINOBSTRUCTMASK) != 0) {
				     if (is_testpoint(gridx, gridy, g, i, ds) != NULL) {
					if (k & STUBROUTE)
					    Fprintf(stderr, "Position marked as a "
						"stub route for the net.\n");
					else
					    Fprintf(stderr, "Position marked as a "
						"tap offset for the net.\n");
				     }
				     disable_gridpos(gridx, gridy, ds->layer);
				  }
				  else if ((lnode = NODEIPTR(gridx, gridy, ds->layer))
					!= NULL && (lnode->nodesav != NULL)) {

				     u_char no_offsets = TRUE;
				     int offset_net;

				     // By how much would a tap need to be moved
				     // to clear the obstructing geometry?

				     // Check tap to right

				     if ((dx > ds->x2) && (gridx <
						NumChannelsX - 1)) {
					offset_net = OBSVAL(gridx + 1, gridy, ds->layer);
					if (offset_net == 0 || offset_net == othernet) {
					   xdist = 0.5 * LefGetXYViaWidth(ds->layer,
							ds->layer, 0, orient);
					   dist = ds->x2 - dx + xdist +
							LefGetRouteSpacing(ds->layer);
					   // Only accept an alternative solution if
					   // it has a smaller offset than previously
					   // found.
					   if ((no_offsets == FALSE) ||
						    (fabs(lnode->offset) > fabs(dist))) {
					      mask = OFFSET_TAP;
					      dir = NI_OFFSET_EW;
					      OBSVAL(gridx, gridy, ds->layer) |= mask;
					      lnode->offset = dist;
					      lnode->flags &= ~(NI_OFFSET_NS);
					      lnode->flags |= dir;
					      no_offsets = FALSE;

				              if ((ds->layer < Num_layers - 1) &&
							(gridx > 0) &&
							(OBSVAL(gridx + 1, gridy,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
				              else if ((ds->layer < Num_layers - 1) &&
							(gridx > 0) &&
							(dist > PitchX / 2)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
					   }
					}
				     }

				     // Check tap to left

				     if ((dx < ds->x1) && (gridx > 0)) {
					offset_net = OBSVAL(gridx - 1, gridy, ds->layer);
					if (offset_net == 0 || offset_net == othernet) {
					   xdist = 0.5 * LefGetXYViaWidth(ds->layer,
							ds->layer, 0, orient);
					   dist = ds->x1 - dx - xdist -
							LefGetRouteSpacing(ds->layer);
					   if ((no_offsets == FALSE) ||
						    (fabs(lnode->offset) > fabs(dist))) {
					      mask = OFFSET_TAP;
					      dir = NI_OFFSET_EW;
					      OBSVAL(gridx, gridy, ds->layer) |= mask;
					      lnode->offset = dist;
					      lnode->flags &= ~(NI_OFFSET_NS);
					      lnode->flags |= dir;
					      no_offsets = FALSE;

				              if ((ds->layer < Num_layers - 1) && gridx <
							(NumChannelsX - 1) &&
							(OBSVAL(gridx - 1, gridy,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
				              else if ((ds->layer < Num_layers - 1) &&
							gridx <
							(NumChannelsX - 1) &&
							(dist < -PitchX / 2)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
					   }
					}
				     }

				     // Check tap up

				     if ((dy > ds->y2) && (gridy <
						NumChannelsY - 1)) {
					offset_net = OBSVAL(gridx, gridy + 1, ds->layer);
					if (offset_net == 0 || offset_net == othernet) {
					   xdist = 0.5 * LefGetXYViaWidth(ds->layer,
							ds->layer, 1, orient);
					   dist = ds->y2 - dy + xdist +
							LefGetRouteSpacing(ds->layer);
					   if ((no_offsets == FALSE) ||
						    (fabs(lnode->offset) > fabs(dist))) {
					      mask = OFFSET_TAP;
					      dir = NI_OFFSET_NS;
					      OBSVAL(gridx, gridy, ds->layer) |= mask;
					      lnode->offset = dist;
					      lnode->flags &= ~(NI_OFFSET_EW);
					      lnode->flags |= dir;
					      no_offsets = FALSE;

				              if ((ds->layer < Num_layers - 1) &&
							(gridy > 0) && (OBSVAL(gridx,
							gridy + 1, ds->layer + 1)
							& OBSTRUCT_MASK)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
				              else if ((ds->layer < Num_layers - 1) &&
							(gridy > 0) &&
							(dist > PitchY / 2)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
					   }
					}
				     }

				     // Check tap down

				     if ((dy < ds->y1) && (gridy > 0)) {
					offset_net = OBSVAL(gridx, gridy - 1, ds->layer);
					if (offset_net == 0 || offset_net == othernet) {
					   xdist = 0.5 * LefGetXYViaWidth(ds->layer,
							ds->layer, 1, orient);
					   dist = ds->y1 - dy - xdist -
							LefGetRouteSpacing(ds->layer);
					   if ((no_offsets == FALSE) ||
						    (fabs(lnode->offset) > fabs(dist))) {
					      mask = OFFSET_TAP;
					      dir = NI_OFFSET_NS;
					      OBSVAL(gridx, gridy, ds->layer) |= mask;
					      lnode->offset = dist;
					      lnode->flags &= ~(NI_OFFSET_EW);
					      lnode->flags |= dir;
					      no_offsets = FALSE;

				              if ((ds->layer < Num_layers - 1) &&
							gridx <
							(NumChannelsX - 1) &&
							(OBSVAL(gridx, gridy - 1,
							ds->layer + 1) & OBSTRUCT_MASK)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
				              else if ((ds->layer < Num_layers - 1) &&
							gridx <
							(NumChannelsX - 1) &&
							(dist < -PitchY / 2)) {
					         block_route(gridx, gridy, ds->layer, UP);
					      }
					   }
					}
				     }

				     // No offsets were possible.  If orient is 0
				     // then mark as NI_NO_VIAX and try again with
				     // orient 2.  If orient is 2 and no offsets
				     // are possible, then disable the position.

				     if (no_offsets == TRUE) {
				 	if (orient == 2) {
					    // Maybe no need to revert the flag?
					    lnode->flags &= ~NI_NO_VIAX;
					    if (is_testpoint(gridx, gridy,
						    g, i, ds) != NULL)
						Fprintf(stderr, "Unable to find "
							"a viable offset for a tap.\n");
				            disable_gridpos(gridx, gridy, ds->layer);
					}
					else
					    lnode->flags |= NI_NO_VIAX;
				     }
				  }
				  else {
				     if (is_testpoint(gridx, gridy,
						    g, i, ds) != NULL)
					Fprintf(stderr, "Tap point is too "
						"close to two different nodes "
						"and no offsets are possible.\n");
				     disable_gridpos(gridx, gridy, ds->layer);
				  }
			       }

			       /* If we are on a layer > 0, then this geometry	*/
			       /* may block or partially block a pin on layer	*/
			       /* zero.  Mark this point as belonging to the	*/
			       /* net with a stub route to it.			*/
			       /* NOTE:  This is possibly too restrictive.	*/
			       /* May want to force a tap offset for vias on	*/
			       /* layer zero. . .				*/

			       if ((ds->layer > 0) && (n2 != NULL) && (n2->netnum
					!= node->netnum) && ((othernet == 0) ||
					(othernet == (u_int)node->netnum))) {

				  lnode = NODEIPTR(gridx, gridy, ds->layer);
				  xdist = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer,
						0, orient);
				  if ((dy + xdist + LefGetRouteSpacing(ds->layer) >
					ds->y1) && (dy + xdist < ds->y1)) {
				     if ((dx - xdist < ds->x2) &&
						(dx + xdist > ds->x1) &&
						(lnode == NULL || lnode->stub
						== 0.0)) {
					OBSVAL(gridx, gridy, ds->layer)
				   		= (OBSVAL(gridx, gridy, ds->layer)
						& BLOCKED_MASK) |
						node->netnum | STUBROUTE;
				        lnode = SetNodeinfo(gridx, gridy, ds->layer,
						node);
					lnode->nodeloc = node;
					lnode->nodesav = node;
					lnode->stub = ds->y1 - dy;
					lnode->flags |= NI_STUB_NS;
				     }
				  }
				  if ((dy - xdist - LefGetRouteSpacing(ds->layer) <
					ds->y2) && (dy - xdist > ds->y2)) {
				     if ((dx - xdist < ds->x2) &&
						(dx + xdist > ds->x1) &&
						(lnode == NULL || lnode->stub
						== 0.0)) {
					OBSVAL(gridx, gridy, ds->layer)
				   		= (OBSVAL(gridx, gridy, ds->layer)
						& BLOCKED_MASK) |
						node->netnum | STUBROUTE;
				        lnode = SetNodeinfo(gridx, gridy, ds->layer,
						node);
					lnode->nodeloc = node;
					lnode->nodesav = node;
					lnode->stub = ds->y2 - dy;
					lnode->flags |= NI_STUB_NS;
				     }
				  }

				  xdist = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer,
						1, orient);
				  if ((dx + xdist + LefGetRouteSpacing(ds->layer) >
					ds->x1) && (dx + xdist < ds->x1)) {
				     if ((dy - xdist < ds->y2) &&
						(dy + xdist > ds->y1) &&
						(lnode == NULL || lnode->stub
						 == 0.0)) {
					OBSVAL(gridx, gridy, ds->layer)
				   		= (OBSVAL(gridx, gridy, ds->layer)
						& BLOCKED_MASK) |
						node->netnum | STUBROUTE;
				        lnode = SetNodeinfo(gridx, gridy, ds->layer,
						node);
					lnode->nodeloc = node;
					lnode->nodesav = node;
					lnode->stub = ds->x1 - dx;
					lnode->flags |= NI_STUB_EW;
				     }
				  }
				  if ((dx - xdist - LefGetRouteSpacing(ds->layer) <
					ds->x2) && (dx - xdist > ds->x2)) {
				     if ((dy - xdist < ds->y2) &&
						(dy + xdist > ds->y1) &&
						(lnode == NULL || lnode->stub
						== 0.0)) {
					OBSVAL(gridx, gridy, ds->layer)
				   		= (OBSVAL(gridx, gridy, ds->layer)
						& BLOCKED_MASK) |
						node->netnum | STUBROUTE;
				        lnode = SetNodeinfo(gridx, gridy, ds->layer,
						node);
					lnode->nodeloc = node;
					lnode->nodesav = node;
					lnode->stub = ds->x2 - dx;
					lnode->flags |= NI_STUB_EW;
				     }
				  }
			       }
			    }
		         }
		         gridy++;
		      }
		   }
		   gridx++;
		}
	     }
	  }
       }
    }

} /* void create_obstructions_outside_nodes( void ) */

/*--------------------------------------------------------------*/
/* tap_to_tap_interactions()					*/
/*								*/
/*  Similar to create_obstructions_from_nodes(), but looks at	*/
/*  each node's tap geometry, looks at every grid point in a	*/
/*  wider area surrounding the tap.  If any other node has an	*/
/*  offset that would place it too close to this node's	tap	*/
/*  geometry, then we mark the other node as unroutable at that	*/
/*  grid point.							*/
/*--------------------------------------------------------------*/

void tap_to_tap_interactions(void)
{
    NODEINFO lnode;
    GATE g;
    DSEG ds;
    DPOINT tpoint;
    struct dseg_ de;
    int mingridx, mingridy, maxgridx, maxgridy;
    int i, gridx, gridy, net, orignet;
    double dx, dy;
    float dist;

    double deltaxx[MAX_LAYERS];
    double deltaxy[MAX_LAYERS];
    double deltayx[MAX_LAYERS];
    double deltayy[MAX_LAYERS];

    for (i = 0; i < Num_layers; i++) {
	deltaxx[i] = 0.5 * LefGetXYViaWidth(i, i, 0, 0) + LefGetRouteSpacing(i);
	deltayx[i] = 0.5 * LefGetXYViaWidth(i, i, 1, 0) + LefGetRouteSpacing(i);
	deltaxy[i] = 0.5 * LefGetXYViaWidth(i, i, 0, 2) + LefGetRouteSpacing(i);
	deltayy[i] = 0.5 * LefGetXYViaWidth(i, i, 1, 2) + LefGetRouteSpacing(i);
    }

    for (g = Nlgates; g; g = g->next) {
       for (i = 0; i < g->nodes; i++) {
	  net = g->netnum[i];
	  if (net > 0) {
             for (ds = g->taps[i]; ds; ds = ds->next) {

		mingridx = (int)((ds->x1 - Xlowerbound) / PitchX) - 1;
		if (mingridx < 0) mingridx = 0;
		maxgridx = (int)((ds->x2 - Xlowerbound) / PitchX) + 2;
		if (maxgridx >= NumChannelsX)
		   maxgridx = NumChannelsX - 1;
		mingridy = (int)((ds->y1 - Ylowerbound) / PitchY) - 1;
		if (mingridy < 0) mingridy = 0;
		maxgridy = (int)((ds->y2 - Ylowerbound) / PitchY) + 2;
		if (maxgridy >= NumChannelsY)
		   maxgridy = NumChannelsY - 1;

		for (gridx = mingridx; gridx <= maxgridx; gridx++) {
		   for (gridy = mingridy; gridy <= maxgridy; gridy++) {

		      /* Is there an offset tap at this position, and	*/
		      /* does it belong to a net that is != net?	*/

		      orignet = OBSVAL(gridx, gridy, ds->layer);
		      if (orignet & OFFSET_TAP) {
			 orignet &= ROUTED_NET_MASK;
			 if (orignet != net) {

		            dx = (gridx * PitchX) + Xlowerbound;
		            dy = (gridy * PitchY) + Ylowerbound;

			    lnode = NODEIPTR(gridx, gridy, ds->layer);
			    dist = (lnode) ? lnode->offset : 0.0;

			    /* "de" is the bounding box of a via placed	  */
			    /* at (gridx, gridy) and offset as specified. */
			    /* Expanded by metal spacing requirement.	  */

			    de.x1 = dx - deltaxx[ds->layer];
			    de.x2 = dx + deltaxx[ds->layer];
			    de.y1 = dy - deltayx[ds->layer];
			    de.y2 = dy + deltayx[ds->layer];

			    if (lnode->flags & NI_OFFSET_NS) {
			       de.y1 += dist;
			       de.y2 += dist;
			    }
			    else if (lnode->flags & NI_OFFSET_EW) {
			       de.x1 += dist;
			       de.x2 += dist;
			    }

			    // Shrink by EPS to avoid roundoff errors
			    de.x1 += EPS;
			    de.x2 -= EPS;
			    de.y1 += EPS;
			    de.y2 -= EPS;

			    /* Does the via bounding box interact with	*/
			    /* the tap geometry?			*/

			    if ((de.x1 < ds->x2) && (ds->x1 < de.x2) &&
					(de.y1 < ds->y2) && (ds->y1 < de.y2)) {
			       if (is_testpoint(gridx, gridy,
						    g, i, ds) != NULL)
				    Fprintf(stderr, "Offset tap interferes "
					    "with position.\n");
			       disable_gridpos(gridx, gridy, ds->layer);
			    }
			 }
		      }

		      /* Does the distance to the tap prohibit a specific */
		      /* via orientation?				  */
		      if ((orignet & (~(BLOCKED_N | BLOCKED_S | BLOCKED_E | BLOCKED_W)))
				== 0) {
			 lnode = NODEIPTR(gridx, gridy, ds->layer);
			 /* Positions belonging to nodes should have	*/
			 /* already been handled.			*/
			 if (lnode == NULL) {
		            dx = (gridx * PitchX) + Xlowerbound;
		            dy = (gridy * PitchY) + Ylowerbound;

			    /* For a horizontally-oriented via on ds->layer */
			    de.x1 = dx - deltaxx[ds->layer];
			    de.x2 = dx + deltaxx[ds->layer];
			    de.y1 = dy - deltayx[ds->layer];
			    de.y2 = dy + deltayx[ds->layer];

			    if (ds->x2 > de.x1 && ds->x1 < de.x2) {
			        /* Check north and south */
			        if ((ds->y1 < de.y2 && ds->y2 > de.y2) ||
			 		(ds->y2 > de.y1 && ds->y1 < de.y1)) {
				    /* prohibit horizontal via */
				    lnode = SetNodeinfo(gridx, gridy, ds->layer,
						g->noderec[i]);
				    lnode->flags |= NI_NO_VIAX;
				}
			    }

			    if (ds->y2 > de.y1 && ds->y1 < de.y2) {
			        /* Check east and west*/
			        if ((ds->x1 < de.x2 && ds->x2 > de.x2) ||
					(ds->x2 > de.x1 && ds->x1 < de.x1)) {
				    /* prohibit horizontal via */
				    lnode = SetNodeinfo(gridx, gridy, ds->layer,
						g->noderec[i]);
				    lnode->flags |= NI_NO_VIAX;
				}
			    }

			    /* For a vertically-oriented via on ds->layer */
			    de.x1 = dx - deltaxy[ds->layer];
			    de.x2 = dx + deltaxy[ds->layer];
			    de.y1 = dy - deltayy[ds->layer];
			    de.y2 = dy + deltayy[ds->layer];

			    if (ds->x2 > de.x1 && ds->x1 < de.x2) {
			        /* Check north and south */
			        if ((ds->y1 < de.y2 && ds->y2 > de.y2) ||
			 		(ds->y2 > de.y1 && ds->y1 < de.y1)) {
				    /* prohibit horizontal via */
				    lnode = SetNodeinfo(gridx, gridy, ds->layer,
						g->noderec[i]);
				    lnode->flags |= NI_NO_VIAY;
				}
			    }

			    if (ds->y2 > de.y1 && ds->y1 < de.y2) {
			        /* Check east and west*/
			        if ((ds->x1 < de.x2 && ds->x2 > de.x2) ||
					(ds->x2 > de.x1 && ds->x1 < de.x1)) {
				    /* prohibit horizontal via */
				    lnode = SetNodeinfo(gridx, gridy, ds->layer,
						g->noderec[i]);
				    lnode->flags |= NI_NO_VIAY;
				}
			    }
			 }
		      }
		   }
		}
	     }
	  }
       }
    }
}

/*--------------------------------------------------------------*/
/* make_routable()						*/
/*								*/
/*  In the case that a node can't be routed because it has no	*/
/*  available tap points, but there is tap geometry recorded	*/
/*  for the node, then take the first available grid location	*/
/*  near the tap.  This, of course, bypasses all of qrouter's	*/
/*  DRC checks.  But it is only meant to be a stop-gap measure	*/
/*  to get qrouter to complete all routes, and may work in	*/
/*  cases where, say, the tap passes euclidean rules but not	*/
/*  manhattan rules.						*/
/*--------------------------------------------------------------*/

void
make_routable(NODE node)
{
    NODEINFO lnode;
    GATE g;
    DSEG ds;
    int i, gridx, gridy;
    double dx, dy;

    /* The database is not organized to find tap points	*/
    /* from nodes, so we have to search for the node.	*/
    /* Fortunately this routine isn't normally called.	*/

    for (g = Nlgates; g; g = g->next) {
       for (i = 0; i < g->nodes; i++) {
	  if (g->noderec[i] == node) {
             for (ds = g->taps[i]; ds; ds = ds->next) {
		gridx = (int)((ds->x1 - Xlowerbound) / PitchX) - 1;
		if (gridx < 0) gridx = 0;
		while (1) {
		   dx = (gridx * PitchX) + Xlowerbound;
		   if (dx > ds->x2 || gridx >= NumChannelsX) break;
		   else if (dx >= ds->x1 && gridx >= 0) {
		      gridy = (int)((ds->y1 - Ylowerbound) / PitchY) - 1;
		      if (gridy < 0) gridy = 0;
		      while (1) {
		         dy = (gridy * PitchY) + Ylowerbound;
		         if (dy > ds->y2 || gridy >= NumChannelsY) break;

			 // Area inside defined pin geometry

			 if (dy > ds->y1 && gridy >= 0) {
			    int orignet = OBSVAL(gridx, gridy, ds->layer);

			    if (orignet & NO_NET) {
				OBSVAL(gridx, gridy, ds->layer) = g->netnum[i];
				lnode = SetNodeinfo(gridx, gridy, ds->layer,
						g->noderec[i]);
				lnode->nodeloc = node;
				lnode->nodesav = node;
				return;
			    }
			 }
			 gridy++;
		      }
		   }
		   gridx++;
	        }
	     }
	  }
       }
    }
}

/*--------------------------------------------------------------*/
/* adjust_stub_lengths()					*/
/*								*/
/*  Makes an additional pass through the tap and obstruction	*/
/*  databases, checking geometry against the potential stub	*/
/*  routes for DRC spacing violations.  Adjust stub routes as	*/
/*  necessary to resolve the DRC error(s).			*/
/*								*/
/*  ARGS: none.							*/
/*  RETURNS: nothing						*/
/*  SIDE EFFECTS: none						*/
/*  AUTHOR:  Tim Edwards, April 2013				*/
/*--------------------------------------------------------------*/

void adjust_stub_lengths(void)
{
    NODE node;
    NODEINFO lnode;
    GATE g;
    DSEG ds, ds2;
    struct dseg_ dt, de;
    int i, gridx, gridy, orignet, o;
    double dx, dy, wx, wy, s;
    float dist;
    u_char errbox;
    int orient = 0;

    // For each node terminal (gate pin), look at the surrounding grid points.
    // If any define a stub route or an offset, check if the stub geometry
    // or offset geometry would create a DRC spacing violation.  If so, adjust
    // the stub route to resolve the error.  If the error cannot be resolved,
    // mark the position as unroutable.  If it is the ONLY grid point accessible
    // to the pin, keep it as-is and flag a warning.

    // Unlike blockage-finding routines, which look in an area of a size equal
    // to the DRC interaction distance around a tap rectangle, this routine looks
    // out one grid pitch in each direction, to catch information about stubs that
    // may terminate within a DRC interaction distance of the tap rectangle.

    for (g = Nlgates; g; g = g->next) {
       for (i = 0; i < g->nodes; i++) {
	  if (g->netnum[i] != 0) {

	     // Get the node record associated with this pin.
	     node = g->noderec[i];
	     if (node == NULL) continue;

	     // Work through each rectangle in the tap geometry twice.  The
	     // second sweep checks for errors created by geometry that
	     // interacts with stub routes created by the first sweep, and
	     // also for geometry that interacts with vias in 90 degree
	     // orientation.

	     orient = 0;
             for (ds = g->taps[i];; ds = ds->next) {
		if (ds == NULL) {
		    if (orient == 0) {
			orient = 2;
			ds = g->taps[i];
			if (ds == NULL) break;
		    }
		    else
			break;
		}
		wx = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 0, orient);
		wy = 0.5 * LefGetXYViaWidth(ds->layer, ds->layer, 1, orient);
		s = LefGetRouteSpacing(ds->layer);
		gridx = (int)((ds->x1 - Xlowerbound - PitchX) / PitchX) - 1;
		while (1) {
		   dx = (gridx * PitchX) + Xlowerbound;
		   if (dx > (ds->x2 + PitchX) ||
				gridx >= NumChannelsX) break;
		   else if (dx >= (ds->x1 - PitchX) && gridx >= 0) {
		      gridy = (int)((ds->y1 - Ylowerbound - PitchY) / PitchY) - 1;
		      while (1) {
		         dy = (gridy * PitchY) + Ylowerbound;
		         if (dy > (ds->y2 + PitchY) ||
				gridy >= NumChannelsY) break;
		         if (dy >= (ds->y1 - PitchY) && gridy >= 0) {

			     orignet = OBSVAL(gridx, gridy, ds->layer);

			     // Ignore this location if it is assigned to another
			     // net, or is assigned to NO_NET.

			     if ((orignet & ROUTED_NET_MASK) != node->netnum) {
				gridy++;
				continue;
			     }
			     lnode = NODEIPTR(gridx, gridy, ds->layer);

			     // Even if it's on the same net, we need to check
			     // if the stub is to this node, otherwise it is not
			     // an issue.
			     if ((!lnode) || (lnode->nodesav != node)) {
				gridy++;
				continue;
			     }

			     // NI_STUB_MASK are unroutable;  leave them alone
			     if (orignet & STUBROUTE) {
				if ((lnode->flags & NI_OFFSET_MASK) == NI_OFFSET_MASK) {
				   gridy++;
				   continue;
				}
			     }

			     // define a route box around the grid point

			     errbox = FALSE;
			     dt.x1 = dx - wx;
			     dt.x2 = dx + wx;
			     dt.y1 = dy - wy;
			     dt.y2 = dy + wy;

			     // adjust the route box according to the stub
			     // or offset geometry, provided that the stub
			     // is longer than the route box.

			     if (orignet & OFFSET_TAP) {
			        dist = lnode->offset;
				if (lnode->flags & NI_OFFSET_EW) {
				   dt.x1 += dist;
				   dt.x2 += dist;
				}
				else if (lnode->flags & NI_OFFSET_NS) {
				   dt.y1 += dist;
				   dt.y2 += dist;
				}
			     }
			     else if (orignet & STUBROUTE) {
			        dist = (double)lnode->stub;
				if (lnode->flags & NI_STUB_EW) {
				   if (dist > EPS) {
				      if (dx + dist > dt.x2)
				 	 dt.x2 = dx + dist;
				   }
				   else {
				      if (dx + dist < dt.x1)
					 dt.x1 = dx + dist;
				   }
				}
				else if (lnode->flags & NI_STUB_NS) {
				   if (dist > EPS) {
				      if (dy + dist > dt.y2)
					 dt.y2 = dy + dist;
				   }
				   else {
				      if (dy + dist < dt.y1)
					 dt.y1 = dy + dist;
				   }
				}
			     }

			     de = dt;

			     // check for DRC spacing interactions between
			     // the tap box and the route box

			     if ((dt.y1 - ds->y2) > EPS && (dt.y1 - ds->y2) + EPS < s) {
				if (ds->x2 > (dt.x1 - s) && ds->x1 < (dt.x2 + s)) {
				   de.y2 = dt.y1;
				   de.y1 = ds->y2;
				   if (ds->x2 + s < dt.x2) de.x2 = ds->x2 + s;
				   if (ds->x1 - s > dt.x1) de.x1 = ds->x1 - s;
				   errbox = TRUE;
				}
			     }
			     else if ((ds->y1 - dt.y2) > EPS && (ds->y1 - dt.y2) + EPS < s) {
				if (ds->x2 > (dt.x1 - s) && ds->x1 < (dt.x2 + s)) {
				   de.y1 = dt.y2;
				   de.y2 = ds->y1;
				   if (ds->x2 + s < dt.x2) de.x2 = ds->x2 + s;
				   if (ds->x1 - s > dt.x1) de.x1 = ds->x1 - s;
				   errbox = TRUE;
				}
			     }

			     if ((dt.x1 - ds->x2) > EPS && (dt.x1 - ds->x2) + EPS < s) {
				if (ds->y2 > (dt.y1 - s) && ds->y1 < (dt.y2 + s)) {
				   de.x2 = dt.x1;
				   de.x1 = ds->x2;
				   if (ds->y2 + s < dt.y2) de.y2 = ds->y2 + s;
				   if (ds->y1 - s > dt.y1) de.y1 = ds->y1 - s;
				   errbox = TRUE;
				}
			     }
			     else if ((ds->x1 - dt.x2) > EPS && (ds->x1 - dt.x2) + EPS < s) {
				if (ds->y2 > (dt.y1 - s) && ds->y1 < (dt.y2 + s)) {
				   de.x1 = dt.x2;
				   de.x2 = ds->x1;
				   if (ds->y2 + s < dt.y2) de.y2 = ds->y2 + s;
				   if (ds->y1 - s > dt.y1) de.y1 = ds->y1 - s;
				   errbox = TRUE;
				}
			     }

			     if (errbox == TRUE) {
	
			        // Chop areas off the error box that are covered by
			        // other taps of the same port.

			        for (ds2 = g->taps[i]; ds2; ds2 = ds2->next) {
				   if (ds2 == ds) continue;
				   if (ds2->layer != ds->layer) continue;

				   if (ds2->x1 <= de.x1 && ds2->x2 >= de.x2 &&
					ds2->y1 <= de.y1 && ds2->y2 >= de.y2) {
				      errbox = FALSE;	// Completely covered
				      break;
				   }

				   // Look for partial coverage.  Note that any
				   // change can cause a change in the original
				   // two conditionals, so we have to keep
				   // evaluating those conditionals.

				   if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
				      if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					 // if (ds2->x1 < de.x1 - EPS &&
					 if (ds2->x1 < de.x1 + EPS &&
							ds2->x2 < de.x2 - EPS) {
					    de.x1 = ds2->x2;
					    if (ds2->x2 >= ds->x2) errbox = FALSE;
					 }

				   if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
				      if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					 // if (ds2->x2 > de.x2 + EPS &&
					 if (ds2->x2 > de.x2 - EPS &&
							ds2->x1 > de.x1 + EPS) {
					    de.x2 = ds2->x1;
					    if (ds2->x1 <= ds->x1) errbox = FALSE;
					 }

				   if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
				      if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					 // if (ds2->y1 < de.y1 - EPS &&
					 if (ds2->y1 < de.y1 + EPS &&
							ds2->y2 < de.y2 - EPS) {
					    de.y1 = ds2->y2;
					    if (ds2->y2 >= ds->y2) errbox = FALSE;
					 }

				   if (ds2->x1 < de.x2 && ds2->x2 > de.x1)
				      if (ds2->y1 < de.y2 && ds2->y2 > de.y1)
					 // if (ds2->y2 > de.y2 + EPS &&
					 if (ds2->y2 > de.y2 - EPS &&
							ds2->y1 > de.y1 + EPS) {
					    de.y2 = ds2->y1;
					    if (ds2->y1 <= ds->y1) errbox = FALSE;
					 }
				}
			     }

			     // Any area left over is a potential DRC error.

			     if ((de.x2 <= de.x1) || (de.y2 <= de.y1))
				errbox = FALSE;
		
			     if (errbox == TRUE) {

				// Create stub route to cover error box, or
				// if possible, stretch existing stub route
				// to cover error box.

				// Allow EW stubs to be changed to NS stubs and
				// vice versa if the original stub length was less
				// than a route width.  This means the grid position
				// makes contact without the stub.  Moving the stub
				// to another side should not create an error.

				// NOTE:  error box must touch ds geometry, and by
				// more than just a point.

				// 8/31/2016:
				// If DRC violations are created on two adjacent
				// sides, then create both a stub route and a tap
				// offset.  Put the stub route in the preferred
				// metal direction of the layer, and set the tap
				// offset to prevent the DRC error in the other
				// direction.
				// 10/3/2016:  The tap offset can be set either
				// by moving toward the obstructing edge to
				// remove the gap, or moving away from it to
				// avoid the DRC spacing error.  Choose the one
				// that offsets by the smaller distance.

				if ((de.x2 > dt.x2) && (de.y1 < ds->y2) &&
						(de.y2 > ds->y1)) {
				   if ((orignet & STUBROUTE) == 0) {
			              OBSVAL(gridx, gridy, ds->layer) |= STUBROUTE;
				      lnode->stub = de.x2 - dx;
				      lnode->flags |= NI_STUB_EW;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_EW)) {
				      // Beware, if dist > 0 then this reverses
				      // the stub.  For U-shaped ports may need
				      // to have separate E and W stubs.
				      lnode->stub = de.x2 - dx;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_NS)) {

				      // If preferred route direction is
				      // horizontal, then change the stub

			              OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				      if (LefGetRouteOrientation(ds->layer) == 1) {
					 lnode->flags = NI_OFFSET_NS | NI_STUB_EW;
					 if (lnode->stub > 0) {
					    lnode->offset = lnode->stub - wy;
					    if (lnode->offset < 0) lnode->offset = 0;
					 }
					 else {
					    lnode->offset = lnode->stub + wy;
					    if (lnode->offset > 0) lnode->offset = 0;
					 }
				         lnode->stub = de.x2 - dx;
				         errbox = FALSE;
				      }
				      else {
					 // Add the offset
				         lnode->offset = de.x2 - dx - wx;
					 if (lnode->offset > s - lnode->offset)
					     lnode->offset -= s;
					 lnode->flags |= NI_OFFSET_EW;
				         errbox = FALSE;
				      }
				   }
				}
				else if ((de.x1 < dt.x1) && (de.y1 < ds->y2) &&
						(de.y2 > ds->y1)) {
				   if ((orignet & STUBROUTE) == 0) {
			              OBSVAL(gridx, gridy, ds->layer) |= STUBROUTE;
				      lnode->stub = de.x1 - dx;
				      lnode->flags |= NI_STUB_EW;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_EW)) {
				      // Beware, if dist > 0 then this reverses
				      // the stub.  For U-shaped ports may need
				      // to have separate E and W stubs.
				      lnode->stub = de.x1 - dx;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_NS)) {

				      // If preferred route direction is
				      // horizontal, then change the stub

			              OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				      if (LefGetRouteOrientation(ds->layer) == 1) {
					 lnode->flags = NI_OFFSET_NS | NI_STUB_EW;
					 if (lnode->stub > 0) {
					    lnode->offset = lnode->stub - wy;
					    if (lnode->offset < 0) lnode->offset = 0;
					 }
					 else {
					    lnode->offset = lnode->stub + wy;
					    if (lnode->offset > 0) lnode->offset = 0;
					 }
				         lnode->stub = de.x1 - dx;
				         errbox = FALSE;
				      }
				      else {
					 // Add the offset
				         lnode->offset = de.x1 - dx + wx;
					 if (-lnode->offset > s + lnode->offset)
					     lnode->offset += s;
					 lnode->flags |= NI_OFFSET_EW;
				         errbox = FALSE;
				      }
				   }
				}
				else if ((de.y2 > dt.y2) && (de.x1 < ds->x2) &&
					(de.x2 > ds->x1)) {
				   if ((orignet & STUBROUTE) == 0) {
			              OBSVAL(gridx, gridy, ds->layer) |= STUBROUTE;
				      lnode->stub = de.y2 - dy;
				      lnode->flags |= NI_STUB_NS;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_NS)) {
				      // Beware, if dist > 0 then this reverses
				      // the stub.  For C-shaped ports may need
				      // to have separate N and S stubs.
				      lnode->stub = de.y2 - dy;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_EW)) {

				      // If preferred route direction is
				      // vertical, then change the stub

			              OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				      if (LefGetRouteOrientation(ds->layer) == 0) {
					 lnode->flags = NI_OFFSET_EW | NI_STUB_NS;
					 if (lnode->stub > 0) {
					    lnode->offset = lnode->stub - wx;
					    if (lnode->offset < 0) lnode->offset = 0;
					 }
					 else {
					    lnode->offset = lnode->stub + wx;
					    if (lnode->offset > 0) lnode->offset = 0;
					 }
				         lnode->stub = de.y2 - dy;
				         errbox = FALSE;
				      }
				      else {
					 // Add the offset
				         lnode->offset = de.y2 - dy - wy;
					 if (lnode->offset > s - lnode->offset)
					     lnode->offset -= s;
					 lnode->flags |= NI_OFFSET_NS;
				         errbox = FALSE;
				      }
				   }
				}
				else if ((de.y1 < dt.y1) && (de.x1 < ds->x2) &&
					(de.x2 > ds->x1)) {
				   if ((orignet & STUBROUTE) == 0) {
			              OBSVAL(gridx, gridy, ds->layer) |= STUBROUTE;
				      lnode->stub = de.y1 - dy;
				      lnode->flags |= NI_STUB_NS;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_NS)) {
				      // Beware, if dist > 0 then this reverses
				      // the stub.  For C-shaped ports may need
				      // to have separate N and S stubs.
				      lnode->stub = de.y1 - dy;
				      errbox = FALSE;
				   }
				   else if ((orignet & STUBROUTE)
						&& (lnode->flags & NI_STUB_EW)) {

				      // If preferred route direction is
				      // vertical, then change the stub

			              OBSVAL(gridx, gridy, ds->layer) |= OFFSET_TAP;
				      if (LefGetRouteOrientation(ds->layer) == 0) {
					 lnode->flags = NI_OFFSET_EW | NI_STUB_NS;
					 if (lnode->stub > 0) {
					    lnode->offset = lnode->stub - wx;
					    if (lnode->offset < 0) lnode->offset = 0;
					 }
					 else {
					    lnode->offset = lnode->stub + wx;
					    if (lnode->offset > 0) lnode->offset = 0;
					 }
				         lnode->stub = de.y1 - dy + wy;
				         errbox = FALSE;
				      }
				      else {
					 // Add the offset
				         lnode->offset = de.y1 - dy + wy;
					 if (-lnode->offset > s + lnode->offset)
					     lnode->offset += s;
					 lnode->flags |= NI_OFFSET_NS;
				         errbox = FALSE;
				      }
				   }
				}

				// Where the error box did not touch the stub
				// route, there is assumed to be no error.

				if (errbox == TRUE)
				   if ((de.x2 > dt.x2) || (de.x1 < dt.x1) ||
					(de.y2 > dt.y2) || (de.y1 < dt.y1))
				      errbox = FALSE;

				if (errbox == TRUE) {
				   // Unroutable position, so mark it unroutable
			           OBSVAL(gridx, gridy, ds->layer) |= STUBROUTE;
				   lnode->flags |= NI_STUB_MASK;
				}
			     }
		         }
		         gridy++;
		      }
		   }
		   gridx++;
		}
	     }
	  }
       }
    }

} /* void adjust_stub_lengths() */

/*--------------------------------------------------------------*/
/* block_route()						*/
/*								*/
/*  Mark a specific length along the route tracks as unroutable	*/
/*  by finding the grid point in the direction indicated, and	*/
/*  setting the appropriate block bit in the Obs[] array for	*/
/*  that position.  The original grid point is marked as	*/
/*  unroutable in the opposite direction, for symmetry.		*/
/*--------------------------------------------------------------*/

void
block_route(int x, int y, int lay, u_char dir)
{
   int bx, by, bl, ob;

   bx = x;
   by = y;
   bl = lay;

   switch (dir) {
      case NORTH:
	 if (y == NumChannelsY - 1) return;
	 by = y + 1;
	 break;
      case SOUTH:
	 if (y == 0) return;
	 by = y - 1;
	 break;
      case EAST:
	 if (x == NumChannelsX - 1) return;
	 bx = x + 1;
	 break;
      case WEST:
	 if (x == 0) return;
	 bx = x - 1;
	 break;
      case UP:
	 if (lay == Num_layers - 1) return;
	 bl = lay + 1;
	 break;
      case DOWN:
	 if (lay == 0) return;
	 bl = lay - 1;
	 break;
   }
   
   ob = OBSVAL(bx, by, bl);

   if ((ob & NO_NET) != 0) return;

   switch (dir) {
      case NORTH:
	 OBSVAL(bx, by, bl) |= BLOCKED_S;
	 OBSVAL(x, y, lay) |= BLOCKED_N;
	 break;
      case SOUTH:
	 OBSVAL(bx, by, bl) |= BLOCKED_N;
	 OBSVAL(x, y, lay) |= BLOCKED_S;
	 break;
      case EAST:
	 OBSVAL(bx, by, bl) |= BLOCKED_W;
	 OBSVAL(x, y, lay) |= BLOCKED_E;
	 break;
      case WEST:
	 OBSVAL(bx, by, bl) |= BLOCKED_E;
	 OBSVAL(x, y, lay) |= BLOCKED_W;
	 break;
      case UP:
	 OBSVAL(bx, by, bl) |= BLOCKED_D;
	 OBSVAL(x, y, lay) |= BLOCKED_U;
	 break;
      case DOWN:
	 OBSVAL(bx, by, bl) |= BLOCKED_U;
	 OBSVAL(x, y, lay) |= BLOCKED_D;
	 break;
   }
}

/*--------------------------------------------------------------*/
/* find_route_blocks() ---					*/
/*								*/
/*	Search tap geometry for edges that cause DRC spacing	*/
/*	errors with route edges.  This specifically checks	*/
/*	edges of the route tracks, not the intersection points.	*/
/*	If a tap would cause an error with a route segment,	*/
/*	the grid points on either end of the segment are	*/
/*	flagged to prevent generating a route along that	*/
/*	specific segment.					*/
/*--------------------------------------------------------------*/

void
find_route_blocks()
{
   GATE g;
   NODEINFO lnode;
   DSEG ds;
   struct dseg_ dt, lds;
   int i, gridx, gridy;
   double dx, dy, w, v, s, u;
   double dist;
   int orient = 0;	/* Need to check orient = 2! */

   for (g = Nlgates; g; g = g->next) {
      for (i = 0; i < g->nodes; i++) {
	 if (g->netnum[i] != 0) {

	    // Work through each rectangle in the tap geometry

            for (ds = g->taps[i]; ds; ds = ds->next) {
	       lds = *ds;	/* Make local copy of tap rect */

	       /* Trim to array bounds and reject if out-of-bounds */
	       gridx = (int)((lds.x1 - Xlowerbound) / PitchX);
	       if (gridx >= NumChannelsX) continue;
	       if (gridx < 0) lds.x1 = Xlowerbound;

	       gridx = (int)((lds.x2 - Xlowerbound) / PitchX);
	       if (gridx < 0) continue;
	       if (gridx >= NumChannelsX)
		   lds.x2 = Xlowerbound + (NumChannelsX * PitchX);
	       
	       gridy = (int)((lds.y1 - Ylowerbound) / PitchY);
	       if (gridy >= NumChannelsY) continue;
	       if (gridy < 0) lds.y1 = Ylowerbound;

	       gridy = (int)((lds.y2 - Ylowerbound) / PitchY);
	       if (gridy < 0) continue;
	       if (gridy >= NumChannelsY)
		   lds.y2 = Ylowerbound + (NumChannelsY * PitchY);
	       
	       w = 0.5 * LefGetRouteWidth(lds.layer);
	       v = 0.5 * LefGetXYViaWidth(lds.layer, lds.layer, 0, orient);
	       s = LefGetRouteSpacing(lds.layer);

	       // Look west

	       gridx = (int)((lds.x1 - Xlowerbound) / PitchX);
	       dx = (gridx * PitchX) + Xlowerbound;
	       dist = lds.x1 - dx - w;
	       if (dist > 0 && dist < s && gridx >= 0) {
		  dt.x1 = dt.x2 = dx;
		  dt.y1 = lds.y1;
		  dt.y2 = lds.y2;

		  // Check for other taps covering this edge
		  // (to do)

		  // Find all grid points affected
	          gridy = (int)((lds.y1 - Ylowerbound - PitchY) / PitchY);
	          dy = (gridy * PitchY) + Ylowerbound;
		  while (dy < lds.y1 - s) {
		     dy += PitchY;
		     gridy++;
		  }
		  while (dy < lds.y2 + s) {
		     lnode = NODEIPTR(gridx, gridy, lds.layer);
		     u = ((OBSVAL(gridx, gridy, lds.layer) & STUBROUTE)
				&& (lnode->flags & NI_STUB_EW)) ? v : w;
		     if (dy + EPS < lds.y2 - u) {
			block_route(gridx, gridy, lds.layer, NORTH);
		     }
		     if (dy - EPS > lds.y1 + u) {
			block_route(gridx, gridy, lds.layer, SOUTH);
		     }
		     dy += PitchY;
		     gridy++;
		  }
	       }

	       // Look east

	       gridx = (int)(1.0 + (lds.x2 - Xlowerbound) / PitchX);
	       dx = (gridx * PitchX) + Xlowerbound;
	       dist = dx - lds.x2 - w;
	       if (dist > 0 && dist < s && gridx < NumChannelsX) {
		  dt.x1 = dt.x2 = dx;
		  dt.y1 = lds.y1;
		  dt.y2 = lds.y2;

		  // Check for other taps covering this edge
		  // (to do)

		  // Find all grid points affected
	          gridy = (int)((lds.y1 - Ylowerbound - PitchY) / PitchY);
	          dy = (gridy * PitchY) + Ylowerbound;
		  while (dy < lds.y1 - s) {
		     dy += PitchY;
		     gridy++;
		  }
		  while (dy < lds.y2 + s) {
		     lnode = NODEIPTR(gridx, gridy, lds.layer);
		     u = ((OBSVAL(gridx, gridy, lds.layer) & STUBROUTE)
				&& (lnode->flags & NI_STUB_EW)) ? v : w;
		     if (dy + EPS < lds.y2 - u) {
			block_route(gridx, gridy, lds.layer, NORTH);
		     }
		     if (dy - EPS > lds.y1 + u) {
			block_route(gridx, gridy, lds.layer, SOUTH);
		     }
		     dy += PitchY;
		     gridy++;
		  }
	       }

	       // Look south

	       gridy = (int)((lds.y1 - Ylowerbound) / PitchY);
	       dy = (gridy * PitchY) + Ylowerbound;
	       dist = lds.y1 - dy - w;
	       if (dist > 0 && dist < s && gridy >= 0) {
		  dt.x1 = lds.x1;
		  dt.x2 = lds.x2;
		  dt.y1 = dt.y2 = dy;

		  // Check for other taps covering this edge
		  // (to do)

		  // Find all grid points affected
	          gridx = (int)((lds.x1 - Xlowerbound - PitchX) / PitchX);
	          dx = (gridx * PitchX) + Xlowerbound;
		  while (dx < lds.x1 - s) {
		     dx += PitchX;
		     gridx++;
		  }
		  while (dx < lds.x2 + s) {
		     lnode = NODEIPTR(gridx, gridy, lds.layer);
		     u = ((OBSVAL(gridx, gridy, lds.layer) & STUBROUTE)
				&& (lnode->flags & NI_STUB_NS)) ? v : w;
		     if (dx + EPS < lds.x2 - u) {
			block_route(gridx, gridy, lds.layer, EAST);
		     }
		     if (dx - EPS > lds.x1 + u) {
			block_route(gridx, gridy, lds.layer, WEST);
		     }
		     dx += PitchX;
		     gridx++;
		  }
	       }

	       // Look north

	       gridy = (int)(1.0 + (lds.y2 - Ylowerbound) / PitchY);
	       dy = (gridy * PitchY) + Ylowerbound;
	       dist = dy - lds.y2 - w;
	       if (dist > 0 && dist < s && gridy < NumChannelsY) {
		  dt.x1 = lds.x1;
		  dt.x2 = lds.x2;
		  dt.y1 = dt.y2 = dy;

		  // Check for other taps covering this edge
		  // (to do)

		  // Find all grid points affected
	          gridx = (int)((lds.x1 - Xlowerbound - PitchX) / PitchX);
	          dx = (gridx * PitchX) + Xlowerbound;
		  while (dx < lds.x1 - s) {
		     dx += PitchX;
		     gridx++;
		  }
		  while (dx < lds.x2 + s) {
		     lnode = NODEIPTR(gridx, gridy, lds.layer);
		     u = ((OBSVAL(gridx, gridy, lds.layer) & STUBROUTE)
				&& (lnode->flags & NI_STUB_NS)) ? v : w;
		     if (dx + EPS < lds.x2 - u) {
			block_route(gridx, gridy, lds.layer, EAST);
		     }
		     if (dx - EPS > lds.x1 + u) {
			block_route(gridx, gridy, lds.layer, WEST);
		     }
		     dx += PitchX;
		     gridx++;
		  }
	       }
	    }
	 }
      }
   }
}

/* node.c */