Logo Search packages:      
Sourcecode: magic version File versions  Download package

CIFgen.c

/* CIFgen.c -
 *
 *    This file provides routines that generate CIF from Magic
 *    tile information, using one of the styles read from the
 *    technology file.
 *
 *     ********************************************************************* 
 *     * Copyright (C) 1985, 1990 Regents of the University of California. * 
 *     * Permission to use, copy, modify, and distribute this              * 
 *     * software and its documentation for any purpose and without        * 
 *     * fee is hereby granted, provided that the above copyright          * 
 *     * notice appear in all copies.  The University of California        * 
 *     * makes no representations about the suitability of this            * 
 *     * software for any purpose.  It is provided "as is" without         * 
 *     * express or implied warranty.  Export of this software outside     * 
 *     * of the United States of America may require an export license.    * 
 *     *********************************************************************
 */

#ifndef lint
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-7.5/cif/CIFgen.c,v 1.30 2010/05/13 21:28:12 tim Exp $";
#endif  /* not lint */

#include <stdio.h>
#include <stdlib.h>             /* for abs() */
#include <math.h>       /* for ceil() and sqrt() */

#include "utils/magic.h"
#include "utils/geometry.h"
#include "tiles/tile.h"
#include "utils/hash.h"
#include "database/database.h"
#include "cif/CIFint.h"
#include "calma/calma.h"      /* for CalmaContactArrays */
#include "utils/stack.h"
#include "utils/malloc.h"

/* The following global arrays hold pointers to the CIF planes
 * generated by the procedures in this module.  There are two
 * kinds of planes:  real CIF, which will ostensibly be output,
 * and temporary layers used to build up more complex geometric
 * functions.
 */

global Plane *CIFPlanes[MAXCIFLAYERS];

/* The following are paint tables used by the routines that implement
 * the geometric operations on mask layers, such as AND, OR, GROW,
 * etc.  There are really only two tables.  The first will paint
 * CIF_SOLIDTYPE over anything else, and the second will paint
 * space over anything else.  These tables are used on planes with
 * only two tile types, TT_SPACE and CIF_SOLIDTYPE, so they only
 * have two entries each.
 */

PaintResultType CIFPaintTable[] = {CIF_SOLIDTYPE, CIF_SOLIDTYPE};
PaintResultType CIFEraseTable[] = {TT_SPACE, TT_SPACE};

/* The following local variables are used as a convenience to pass
 * information between CIFGen and the various search functions.
 */

static int growDistance;      /* Distance to grow stuff. */
static Plane *cifPlane;       /* Plane acted on by search functions. */
static int cifScale;          /* Scale factor to use on tiles. */

extern void cifClipPlane();
extern void cifGenClip();

/*
 * ----------------------------------------------------------------------------
 *
 * cifPaintFunc --
 *
 *    This search function is called during CIF_AND and CIF_OR
 *    and CIF_ANDNOT operations for each relevant tile.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    For the area of the tile, either paints or erases in
 *    cifNewPlane, depending on the paint table passed as parameter.
 *    The tile's area is scaled by cifScale first.
 * ----------------------------------------------------------------------------
 */

int
cifPaintFunc(tile, table)
    Tile *tile;
    PaintResultType *table;         /* Used for painting. */
{
    Rect area;

    TiToRect(tile, &area);
    area.r_xbot *= cifScale;
    area.r_xtop *= cifScale;
    area.r_ybot *= cifScale;
    area.r_ytop *= cifScale;

#ifdef NONMANHATTAN
    DBNMPaintPlane(cifPlane, TiGetTypeExact(tile), &area, table,
            (PaintUndoInfo *) NULL);
#else
    DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);
#endif
    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowGridFunc --
 *
 *    Called for each relevant tile during grow-grid operations.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Scales the tile by cifScale, then expands its area by the
 *    remainder of the distance to the nearest grid point, as
 *    defined by the grid distance (growDistance) in the current
 *    CIFOp, then paints this area into cifNewPlane using the table
 *    passed as parameter.
 * ----------------------------------------------------------------------------
 */

int
cifGrowGridFunc(tile, table)
    Tile *tile;
    PaintResultType *table;         /* Table to be used for painting. */
{
    Rect area;
    int remainder;

    /* To be done---handle non-Manhattan geometry */
    TileType oldType = TiGetType(tile);

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot *= cifScale;
    if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot *= cifScale;
    if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop *= cifScale;
    if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop *= cifScale;

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot)
      area.r_xbot -= (abs(area.r_xbot) % growDistance);
    if (area.r_ybot > TiPlaneRect.r_ybot)
      area.r_ybot -= (abs(area.r_ybot) % growDistance);
    if (area.r_xtop < TiPlaneRect.r_xtop)
      area.r_xtop += (abs(area.r_xtop) % growDistance);
    if (area.r_ytop < TiPlaneRect.r_ytop)
      area.r_ytop += (abs(area.r_ytop) % growDistance);

    DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

    CIFTileOps += 1;
    return 0;
}

#ifdef NONMANHATTAN
/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowEuclideanFunc --
 *
 *    Called for each relevant tile during grow or shrink operations.
 *    For growing, these are solid tiles.  For shrinking, these are
 *    space tiles.   This routine differs from cifGrowFunc in that it
 *    grows the minimum distance on non-Manhattan edges necessary to
 *    create a euclidean distance to the edge of growDistance while
 *    keeping corner points on-grid.  This requires a substantially
 *    different algorithm from cifGrowFunc.
 *    
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Scales the tile by cifScale, then expands its area by the
 *    distance in the current CIFOp, then paints this area into
 *    cifNewPlane using the table passed as parameter.
 * ----------------------------------------------------------------------------
 */

#define GROW_NORTH 0x1
#define GROW_SOUTH 0x2
#define GROW_EAST  0x4
#define GROW_WEST  0x8

#define STOP_NW 0x1     /*       WN     EN      */
#define STOP_SW 0x2     /*    NW +-------+ NE   */
#define STOP_NE 0x4     /*       |       |      */
#define STOP_SE 0x8     /*       |       |      */
#define STOP_WN 0x10    /*      SW +-------+ SE */
#define STOP_WS 0x20    /*         WS     ES    */
#define STOP_EN 0x40
#define STOP_ES 0x80

int
cifGrowEuclideanFunc(tile, table)
    Tile *tile;
    PaintResultType *table;         /* Table to be used for painting. */
{
    Tile *tp;
    Rect area, rtmp;
    TileType oldType = TiGetTypeExact(tile);
    unsigned char growDirs = GROW_NORTH | GROW_SOUTH | GROW_EAST | GROW_WEST;
    unsigned char cornerDirs = 0;

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot)
      area.r_xbot *= cifScale;
    else
      growDirs &= ~GROW_WEST;
    if (area.r_ybot > TiPlaneRect.r_ybot)
      area.r_ybot *= cifScale;
    else
      growDirs &= ~GROW_SOUTH;
    if (area.r_xtop < TiPlaneRect.r_xtop)
      area.r_xtop *= cifScale;
    else
      growDirs &= ~GROW_EAST;
    if (area.r_ytop < TiPlaneRect.r_ytop)
      area.r_ytop *= cifScale;
    else
      growDirs &= ~GROW_NORTH;

    /* Grow on diagonal tiles:  grow rectangular tiles around the */
    /* straight edges of the right-triangle, then copy the diagonal     */
    /* tile (at its original size) in the direction of the diagonal.    */
    /* Note:  A diagonal tile, by definition, can't have infinities.    */

    if (oldType & TT_DIAGONAL)
    {
      int growDistanceX, growDistanceY;
      int height, width;
      double hyp;

      if (oldType & TT_SIDE)
          growDirs &= ~GROW_WEST;
      else
          growDirs &= ~GROW_EAST;

      if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION))
          growDirs &= ~GROW_SOUTH;
      else
          growDirs &= ~GROW_NORTH;

      /* Grow non-Manhattan edges to (the closest integer value   */
      /* to) growDistance along the normal to the edge.  This     */
      /* will overestimate the distance only to the minimum       */
      /* amount necessary to ensure on-grid endpoints.            */

      width = area.r_xtop - area.r_xbot;
      height = area.r_ytop - area.r_ybot;
      hyp = sqrt((double)(width * width + height * height));
      growDistanceY = ceil((growDistance * (hyp - height)) / width);
      growDistanceX = ceil((growDistance * (hyp - width)) / height);

      /* Draw vertical tile to distance X */

      rtmp = area;
      if (!(growDirs & GROW_EAST))  rtmp.r_xtop = rtmp.r_xbot + growDistanceX;
      if (!(growDirs & GROW_WEST))  rtmp.r_xbot = rtmp.r_xtop - growDistanceX;
      if (!(growDirs & GROW_SOUTH)) rtmp.r_ybot -=growDistance;
      if (!(growDirs & GROW_NORTH)) rtmp.r_ytop += growDistance;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

      /* Draw horizontal tile to distance Y */

      rtmp = area;
      if (!(growDirs & GROW_EAST))  rtmp.r_xtop += growDistance;
      if (!(growDirs & GROW_WEST))  rtmp.r_xbot -= growDistance;
      if (!(growDirs & GROW_SOUTH)) rtmp.r_ybot = rtmp.r_ytop - growDistanceY;
      if (!(growDirs & GROW_NORTH)) rtmp.r_ytop = rtmp.r_ybot + growDistanceY;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

      /* Finally:  translate, resize, and paint the diagonal tile */

      rtmp = area;

      if (!(growDirs & GROW_NORTH))
          rtmp.r_ytop += growDistance;
      else
          rtmp.r_ytop -= growDistanceY;
      if (!(growDirs & GROW_SOUTH))
          rtmp.r_ybot -= growDistance;
      else
          rtmp.r_ybot += growDistanceY;
      if (!(growDirs & GROW_EAST))
          rtmp.r_xtop += growDistance;
      else
          rtmp.r_xtop -= growDistanceX;
      if (!(growDirs & GROW_WEST))
          rtmp.r_xbot -= growDistance;
      else
          rtmp.r_xbot += growDistanceX;

      DBNMPaintPlane(cifPlane, oldType, &rtmp, table, (PaintUndoInfo *) NULL);
      oldType = (growDirs & GROW_EAST) ? TiGetRightType(tile) : TiGetLeftType(tile);
    }
    else
      DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

    /* Check tile corner areas for paint */

    tp = TR(tile);
    if (TiGetLeftType(tp) == oldType) cornerDirs |= STOP_NE;
    for (; TOP(LB(tp)) > BOTTOM(tile); tp = LB(tp));
    if (TiGetLeftType(tp) == oldType) cornerDirs |= STOP_SE;

    tp = RT(tile);
    if (TiGetBottomType(tp) == oldType) cornerDirs |= STOP_EN;
    for (; RIGHT(BL(tp)) > LEFT(tile); tp = BL(tp));
    if (TiGetBottomType(tp) == oldType) cornerDirs |= STOP_WN;

    tp = BL(tile);
    if (TiGetRightType(tp) == oldType) cornerDirs |= STOP_SW;
    for (; BOTTOM(RT(tp)) < TOP(tile); tp = RT(tp));
    if (TiGetRightType(tp) == oldType) cornerDirs |= STOP_NW;

    tp = LB(tile);
    if (TiGetTopType(tp) == oldType) cornerDirs |= STOP_WS;
    for (; LEFT(TR(tp)) < RIGHT(tile); tp = TR(tp));
    if (TiGetTopType(tp) == oldType) cornerDirs |= STOP_ES;

    if (growDirs & GROW_NORTH)
    {
      rtmp = area;
      rtmp.r_ybot = area.r_ytop;
      rtmp.r_ytop = area.r_ytop + growDistance;
      if ((cornerDirs & (STOP_EN | STOP_NE)) == 0)
          if (growDirs & GROW_EAST) rtmp.r_xtop += growDistance;
      if ((cornerDirs & (STOP_WN | STOP_NW)) == 0)
          if (growDirs & GROW_WEST) rtmp.r_xbot -= growDistance;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_EAST)
    {
      rtmp = area;
      rtmp.r_xbot = area.r_xtop;
      rtmp.r_xtop = area.r_xtop + growDistance;
      if ((cornerDirs & (STOP_EN | STOP_NE)) == 0)
          if (growDirs & GROW_NORTH) rtmp.r_ytop += growDistance;
      if ((cornerDirs & (STOP_SE | STOP_ES)) == 0)
          if (growDirs & GROW_SOUTH) rtmp.r_ybot -= growDistance;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_SOUTH)
    {
      rtmp = area;
      rtmp.r_ytop = area.r_ybot;
      rtmp.r_ybot = area.r_ybot - growDistance;
      if ((cornerDirs & (STOP_SE | STOP_ES)) == 0)
          if (growDirs & GROW_EAST) rtmp.r_xtop += growDistance;
      if ((cornerDirs & (STOP_SW | STOP_WS)) == 0)
          if (growDirs & GROW_WEST) rtmp.r_xbot -= growDistance;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_WEST)
    {
      rtmp = area;
      rtmp.r_xtop = area.r_xbot;
      rtmp.r_xbot = area.r_xbot - growDistance;
      if ((cornerDirs & (STOP_NW | STOP_WN)) == 0)
          if (growDirs & GROW_NORTH) rtmp.r_ytop += growDistance;
      if ((cornerDirs & (STOP_SW | STOP_WS)) == 0)
          if (growDirs & GROW_SOUTH) rtmp.r_ybot -= growDistance;
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    CIFTileOps++;
    return 0;
}
#endif       /* NONMANHATTAN */

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowFunc --
 *
 *    Called for each relevant tile during grow or shrink operations.
 *    For growing, these are solid tiles.  For shrinking, these are
 *    space tiles.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Scales the tile by cifScale, then expands its area by the
 *    distance in the current CIFOp, then paints this area into
 *    cifNewPlane using the table passed as parameter.
 * ----------------------------------------------------------------------------
 */

int
cifGrowFunc(tile, table)
    Tile *tile;
    PaintResultType *table;         /* Table to be used for painting. */
{
    Rect area;
    TileType oldType = TiGetTypeExact(tile);

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot *= cifScale;
    if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot *= cifScale;
    if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop *= cifScale;
    if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop *= cifScale;

#ifdef NONMANHATTAN
    /* Grow on diagonal tiles:  grow rectangular tiles around the */
    /* straight edges of the right-triangle, then copy the diagonal     */
    /* tile (at its original size) in the direction of the diagonal.    */
    /* Note:  A diagonal tile, by definition, can't have infinities.    */

    if (oldType & TT_DIAGONAL)
    {
      Rect rtmp;

      /* Grow top and bottom */

      rtmp.r_ybot = area.r_ybot - growDistance;
      rtmp.r_ytop = area.r_ytop + growDistance;

      /* Grow around left or right edge */

      if (oldType & TT_SIDE)
      {
          rtmp.r_xbot = area.r_xtop - growDistance;
          rtmp.r_xtop = area.r_xtop + growDistance;
      }
      else
      {
          rtmp.r_xbot = area.r_xbot - growDistance;
          rtmp.r_xtop = area.r_xbot + growDistance;
      }
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

      /* Now do the same for the other edge. */

      rtmp.r_xbot = area.r_xbot - growDistance;
      rtmp.r_xtop = area.r_xtop + growDistance;

      if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
      {
          rtmp.r_ybot = area.r_ytop - growDistance;
          rtmp.r_ytop = area.r_ytop + growDistance;
      }
      else /* bottom */
      {
          rtmp.r_ybot = area.r_ybot - growDistance;
          rtmp.r_ytop = area.r_ybot + growDistance;
      }
      DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

      /* Finally, Move and replace the diagonal tile */

      if (oldType & TT_SIDE)
      {
          rtmp.r_xtop = area.r_xtop - growDistance;
          rtmp.r_xbot = area.r_xbot - growDistance;
      }
      else
      {
          rtmp.r_xtop = area.r_xtop + growDistance;
          rtmp.r_xbot = area.r_xbot + growDistance;
      }

      if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
      {
          rtmp.r_ytop = area.r_ytop - growDistance;
          rtmp.r_ybot = area.r_ybot - growDistance;
      }
      else  /* bottom */
      {
          rtmp.r_ytop = area.r_ytop + growDistance;
          rtmp.r_ybot = area.r_ybot + growDistance;
      }
      DBNMPaintPlane(cifPlane, oldType, &rtmp, table, (PaintUndoInfo *) NULL);
    }
    else
    {
#endif

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot -= growDistance;
    if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot -= growDistance;
    if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop += growDistance;
    if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop += growDistance;

    DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

#ifdef NONMANHATTAN
    }
#endif

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatFunc --
 *
 *    Called once for each tile to be selectively bloated.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Uses the bloat table in the current CIFOp to expand the
 *    tile depending on which tiles it abuts, then paints the
 *    expanded area into the new CIF plane.  The bloat table
 *    contains one entry for each tile type.  When that tile
 *    type is seen next to the current tile, the area of the current
 *    tile is bloated by the table value in that location.  The
 *    only exception to this rule is that internal edges (between
 *    two tiles of the same type) cause no bloating.
 *    Note:  the original tile is scaled into CIF coordinates.
 * ----------------------------------------------------------------------------
 */

int
cifBloatFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;
{
    Rect tileArea, cifArea, bloat;
    TileType oldType, type, topLeftType, bottomRightType;
    Tile *t;
    int tilestart, tilestop, cifstart, cifstop;
    BloatData *bloats = (BloatData *)clientData;
    int *bloatTable = (int *)bloats->bl_distance;

    oldType = TiGetTypeExact(tile);
    TiToRect(tile, &tileArea);

    /* Output the original area of the tile. */

    cifArea = tileArea;
    cifArea.r_xbot *= cifScale;
    cifArea.r_xtop *= cifScale;
    cifArea.r_ybot *= cifScale;
    cifArea.r_ytop *= cifScale;

#ifdef NONMANHATTAN

    /* This is a modified version of the nonmanhattan grow function.    */
    /* We grow only in the direction of the diagonal.             */                
    /* This will not work in all situations!  Corner extensions are not */
    /* considered (but should be, for completeness).              */

    if (oldType & TT_DIAGONAL)
    {
      TileType otherType = (oldType & TT_SIDE) ?
            TiGetLeftType(tile) : TiGetRightType(tile);
      int dist = bloatTable[otherType];

      /* The Euclidean grow function is identical to Euclidean bloat-or */
      if (CIFCurStyle->cs_flags & CWF_GROW_EUCLIDEAN)
      {
          growDistance = dist;
          cifGrowEuclideanFunc(tile, CIFPaintTable);
      } 
      else
      {
          /* Grow top and bottom */

          if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
          {
            bloat.r_ybot = cifArea.r_ytop - dist;
            bloat.r_ytop = cifArea.r_ytop;
          }
          else /* bottom */
          {
            bloat.r_ybot = cifArea.r_ybot;
            bloat.r_ytop = cifArea.r_ybot + dist;
          }

          /* Grow around left or right edge */

          if (oldType & TT_SIDE)
          {
            bloat.r_xbot = cifArea.r_xbot - dist;
            bloat.r_xtop = cifArea.r_xtop;
          }
          else
          {
            bloat.r_xbot = cifArea.r_xbot;
            bloat.r_xtop = cifArea.r_xtop + dist;
          }
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable, (PaintUndoInfo *) NULL);

          /* Now do the same for the left or right edge. */

          if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
          {
            bloat.r_ybot = cifArea.r_ybot - dist;
            bloat.r_ytop = cifArea.r_ytop;
          }
          else /* bottom */
          {
            bloat.r_ybot = cifArea.r_ybot;
            bloat.r_ytop = cifArea.r_ytop + dist;
          }

          if (oldType & TT_SIDE)
          {
            bloat.r_xbot = cifArea.r_xtop - dist;
            bloat.r_xtop = cifArea.r_xtop;
          }
          else
          {
            bloat.r_xbot = cifArea.r_xbot;
            bloat.r_xtop = cifArea.r_xbot + dist;
          }
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable, (PaintUndoInfo *) NULL);

          /* Finally, Move and replace the diagonal tile */

          if (oldType & TT_SIDE)
          {
            bloat.r_xtop = cifArea.r_xtop - dist;
            bloat.r_xbot = cifArea.r_xbot - dist;
          }
          else
          {
            bloat.r_xtop = cifArea.r_xtop + dist;
            bloat.r_xbot = cifArea.r_xbot + dist;
          }

          if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
          {
            bloat.r_ytop = cifArea.r_ytop - dist;
            bloat.r_ybot = cifArea.r_ybot - dist;
          }
          else    /* bottom */
          {
            bloat.r_ytop = cifArea.r_ytop + dist;
            bloat.r_ybot = cifArea.r_ybot + dist;
          }
          DBNMPaintPlane(cifPlane, oldType, &bloat, CIFPaintTable,
                  (PaintUndoInfo *) NULL);
      }
    }
    else
      DBNMPaintPlane(cifPlane, oldType, &cifArea,
            CIFPaintTable, (PaintUndoInfo *) NULL);
#else
    DBPaintPlane(cifPlane, &cifArea, CIFPaintTable, (PaintUndoInfo *) NULL);
#endif

    /* Go around the tile, scanning the neighbors along each side.
     * Start with the left side, and output the bloats along that
     * side, if any.
     */
    
    tilestop = tileArea.r_ytop;
    cifstop = cifArea.r_ytop;
    type = oldType;

#ifdef NONMANHATTAN
    /* If the tile type doesn't exist on the left side, skip */
    if (oldType & TT_DIAGONAL)
    {
      type = TiGetLeftType(tile);
      if (oldType & TT_SIDE)
      {
          if (oldType & TT_DIRECTION)
          {
            topLeftType = type;
            goto dotop;
          }
          else
          {
            tilestop = tileArea.r_ybot;
            cifstop = cifArea.r_ybot;
            type = TiGetBottomType(tile);
          }
      }
    }
#endif

    bloat.r_ybot = cifArea.r_ybot - bloatTable[TiGetRightType(LB(tile))];
    bloat.r_xtop = cifArea.r_xbot;
    for (t = BL(tile); BOTTOM(t) < TOP(tile); t = RT(t))
    {
      if (BOTTOM(t) >= tilestop) continue;
      topLeftType = TiGetRightType(t);
      bloat.r_xbot = bloat.r_xtop - bloatTable[topLeftType];
      if (TOP(t) > tilestop)
          bloat.r_ytop = cifstop;
      else bloat.r_ytop = cifScale * TOP(t);
      if ((bloatTable[topLeftType] != 0) && (topLeftType != type))
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
            (PaintUndoInfo *) NULL);
      bloat.r_ybot = bloat.r_ytop;
    }

    /* Now do the top side.  Use the type of the top-left tile to
     * side-extend the left end of the top bloat in order to match
     * things up at the corner.
     */

dotop:
    cifstart = cifArea.r_xtop;
    tilestart = tileArea.r_xtop;
#ifdef NONMANHATTAN
    /* If the tile type doesn't exist on the top side, skip */
    if (oldType & TT_DIAGONAL)
    {
      type = TiGetTopType(tile);
      if (((oldType & TT_SIDE) >> 1) != (oldType & TT_DIRECTION))
      {
          if (oldType & TT_SIDE)
            goto doright;
          else
          {
            cifstart = cifArea.r_xbot;
            tilestart = tileArea.r_xbot;
            type = TiGetLeftType(tile);
          }
      }
    }
#endif

    bloat.r_ybot = cifArea.r_ytop;
    bloat.r_xtop = cifstart;
    for (t = RT(tile); RIGHT(t) > LEFT(tile); t = BL(t))
    {
      TileType otherType;
      if (LEFT(t) >= tilestart) continue;
      otherType = TiGetBottomType(t);
      bloat.r_ytop = bloat.r_ybot + bloatTable[otherType];
      if (LEFT(t) <= tileArea.r_xbot)
          bloat.r_xbot = cifArea.r_xbot - bloatTable[topLeftType];
      else bloat.r_xbot = cifScale * LEFT(t);
      if ((bloatTable[otherType] != 0) && (otherType != type))
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
            (PaintUndoInfo *) NULL);
      bloat.r_xtop = bloat.r_xbot;
    }

    /* Now do the right side. */

doright:
    tilestop = tileArea.r_ybot;
    cifstop = cifArea.r_ybot;
#ifdef NONMANHATTAN
    /* If the tile type doesn't exist on the right side, skip */
    if (oldType & TT_DIAGONAL)
    {
      type = TiGetRightType(tile);
      if (!(oldType & TT_SIDE))
      {
          if (oldType & TT_DIRECTION)
          {
            bottomRightType = type;
            goto dobottom;
          }
          else
          {
            tilestop = tileArea.r_ytop;
            cifstop = cifArea.r_ytop;
            type = TiGetTopType(tile);
          }
      }
    }
#endif

    bloat.r_ytop = cifArea.r_ytop + bloatTable[TiGetLeftType(RT(tile))];
    bloat.r_xbot = cifArea.r_xtop;
    for (t = TR(tile); TOP(t) > BOTTOM(tile); t = LB(t))
    {
      if (TOP(t) <= tilestop) continue;
      bottomRightType = TiGetLeftType(t);
      bloat.r_xtop = bloat.r_xbot + bloatTable[bottomRightType];
      if (BOTTOM(t) < tilestop)
          bloat.r_ybot = cifstop;
      else bloat.r_ybot = cifScale * BOTTOM(t);
      if ((bloatTable[bottomRightType] != 0) && (bottomRightType != type))
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
            (PaintUndoInfo *) NULL);
      bloat.r_ytop = bloat.r_ybot;
    }

    /* Now do the bottom side.  Use the type of the bottom-right tile
     * to side-extend the right end of the bottom bloat in order to match
     * things up at the corner.
     */

dobottom:
    cifstart = cifArea.r_xbot;
    tilestart = tileArea.r_xbot;
#ifdef NONMANHATTAN
    /* If the tile type doesn't exist on the bottom side, skip */
    if (oldType & TT_DIAGONAL)
    {
      type = TiGetBottomType(tile);
      if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION))
      {
          if (!(oldType & TT_DIRECTION))
            goto endbloat;
          else
          {
            cifstart = cifArea.r_xtop;
            tilestart = tileArea.r_xtop;
            type = TiGetRightType(tile);
          }
      }
    }
#endif

    bloat.r_ytop = cifArea.r_ybot;
    bloat.r_xbot = cifstart;
    for (t = LB(tile); LEFT(t) < RIGHT(tile); t = TR(t))
    {
      TileType otherType;
      if (RIGHT(t) <= tilestart) continue;
      otherType = TiGetTopType(t);
      bloat.r_ybot = bloat.r_ytop - bloatTable[otherType];
      if (RIGHT(t) >= tileArea.r_xtop)
          bloat.r_xtop = cifArea.r_xtop + bloatTable[bottomRightType];
      else bloat.r_xtop = cifScale * RIGHT(t);
      if ((bloatTable[otherType] != 0) && (otherType != type))
          DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
            (PaintUndoInfo *) NULL);
      bloat.r_xbot = bloat.r_xtop;
    }

endbloat:
    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatAllFunc --
 *
 *    Called once for each tile to be selectively bloated
 *    using the CIFOP_BLOATALL operation.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Uses the bloat table in the current CIFOp to expand the tile,
 *    depending on which tiles it abuts.  All bordering material that
 *    has bl_distance = 1 is painted into the result plane.
 *
 * ----------------------------------------------------------------------------
 */

#define CIF_PENDING     0
#define CIF_UNPROCESSED CLIENTDEFAULT
#define CIF_PROCESSED   1
#define CIF_IGNORE      2

#define PUSHTILE(tp, stack) \
    if ((tp)->ti_client == (ClientData) CIF_UNPROCESSED) { \
      (tp)->ti_client = (ClientData) CIF_PENDING; \
      STACKPUSH((ClientData) (tp), stack); \
    }

int
cifBloatAllFunc(tile, op)
    Tile *tile;               /* The tile to be processed. */
    CIFOp *op;                /* Describes the operation to be performed */
{
    Rect area;
    TileTypeBitMask connect;
    Tile *t, *tp;
    TileType type;
    BloatData *bloats = (BloatData *)op->co_client;
    int i;
    static Stack *BloatStack = (Stack *)NULL;

    /* Create a mask of all connecting types (these must be in a single
     * plane), then call a search function to find all connecting material
     * of these types.
     */

    TTMaskZero(&connect);
    for (i = 0; i < TT_MAXTYPES; i++)
      if (bloats->bl_distance[i] != 0)
          TTMaskSetType(&connect, i);

    /* This search function is based on drcCheckArea */

    if (BloatStack == (Stack *)NULL)
      BloatStack = StackNew(64);

    PUSHTILE(tile, BloatStack);
    while (!StackEmpty(BloatStack))
    {
      t = (Tile *) STACKPOP(BloatStack);
      if (t->ti_client != (ClientData)CIF_PENDING) continue;
        t->ti_client = (ClientData)CIF_PROCESSED;
      
      /* Get the tile into CIF coordinates. */

      TiToRect(t, &area);
      area.r_xbot *= cifScale;
      area.r_ybot *= cifScale;
      area.r_xtop *= cifScale;
      area.r_ytop *= cifScale;

#ifdef NONMANHATTAN
      DBNMPaintPlane(cifPlane, TiGetTypeExact(t), &area,
            CIFPaintTable, (PaintUndoInfo *) NULL);
#else
      DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
#endif

      /* Top */
      for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
          if (TTMaskHasType(&connect, TiGetBottomType(tp)))
            PUSHTILE(tp, BloatStack);

      /* Left */
      for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
          if (TTMaskHasType(&connect, TiGetRightType(tp)))
            PUSHTILE(tp, BloatStack);

      /* Bottom */
      for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
          if (TTMaskHasType(&connect, TiGetTopType(tp)))
            PUSHTILE(tp, BloatStack);

      /* Right */
      for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
          if (TTMaskHasType(&connect, TiGetLeftType(tp)))
            PUSHTILE(tp, BloatStack);
    }

    /* Clear the tiles that were processed */

    tile->ti_client = (ClientData)CIF_UNPROCESSED;
    STACKPUSH(tile, BloatStack);
    while (!StackEmpty(BloatStack))
    {
      t = (Tile *) STACKPOP(BloatStack);

      /* Top */
      for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
          if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
          {
            tp->ti_client = (ClientData)CIF_UNPROCESSED;
            STACKPUSH(tp, BloatStack);
          }

      /* Left */
      for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
          if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
          {
            tp->ti_client = (ClientData)CIF_UNPROCESSED;
            STACKPUSH(tp, BloatStack);
          }

      /* Bottom */
      for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
          if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
          {
            tp->ti_client = (ClientData)CIF_UNPROCESSED;
            STACKPUSH(tp, BloatStack);
          }

      /* Right */
      for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
          if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
          {
            tp->ti_client = (ClientData)CIF_UNPROCESSED;
            STACKPUSH(tp, BloatStack);
          }
    }
    return 0;     /* Keep the search alive. . . */
}

/*--------------------------------------------------------------*/
/* Support routines and definitions for cifSquareFillArea   */
/*--------------------------------------------------------------*/

/*--------------------------------------------------------------*/
/* Data structure used for identifying contact strips       */
/*--------------------------------------------------------------*/

01010 typedef struct _linkedStrip {
    Rect    area;
    bool    vertical;   /* Tile is vertical */
    bool    shrink_ld;  /* Shrink left or down before creating cuts */
    bool    shrink_ur;  /* Shrink right or up before creating cuts */
    struct _linkedStrip *strip_next;
} linkedStrip;

01018 typedef struct
{
    int           size;
    int           pitch;
    linkedStrip *strips;
} StripsData;

/*
 *--------------------------------------------------------------
 *
 * cifSquaresInitFunc --
 *
 *    Find the first unprocessed tile in the plane.
 *
 * Results:
 *    Return 1 to stop the search and process.
 *    Otherwise, return 0 to keep the search going.
 *
 *--------------------------------------------------------------
 */

int
cifSquaresInitFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;    /* unused */
{
    return (tile->ti_client == (ClientData) CIF_UNPROCESSED) ? 1 : 0;
}

/*
 *--------------------------------------------------------------
 *
 * cifSquaresResetFunc --
 *
 *    Unmark all tiles
 *
 * Results:
 *    Return 0 to keep the search going.
 *
 *--------------------------------------------------------------
 */

int
cifSquaresResetFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;    /* unused */
{
    tile->ti_client = (ClientData) CIF_UNPROCESSED;
    return 0;
}

/*
 *--------------------------------------------------------------
 *
 * cifUnconnectFunc --
 *
 *    Find space tiles inside a possible contact area
 *
 * Results:
 *    Return 1 to stop the ongoing search.
 *
 *--------------------------------------------------------------
 */

int
cifUnconnectFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;    /* unused */
{
    return 1;
}

/*
 *--------------------------------------------------------------
 *
 * cifSquaresStripFunc --
 *
 *    Find vertical or horizontal strips of contact material
 * that is between 1 and 2 contact cuts wide.  Generate and
 * return a list of all such strips.
 *
 * Results:  Return 0 to keep the search going.
 *
 *--------------------------------------------------------------
 */

int
cifSquaresStripFunc(tile, stripsData)
    Tile *tile;
    StripsData *stripsData;
{
    bool vertical;
    int width, height;
    linkedStrip *newStrip;
    Tile *tp, *tp2;
    Rect bbox;

#ifdef NONMANHATTAN
    if (IsSplit(tile))
      return 0;
#endif
    TiToRect(tile, &bbox);

    /* Check if the tile is wide enough for exactly one cut */

    width = bbox.r_xtop - bbox.r_xbot;
    height = bbox.r_ytop - bbox.r_ybot;

    if (height > width)
    {
      vertical = TRUE;
      height = width;
    }
    else
      vertical = FALSE;

    if ((height < stripsData->size) || (height >=
            (stripsData->size + stripsData->pitch)))
      return 0;
      
#ifdef NONMANHATTAN
    /* Ignore strips that are part of a larger  */
    /* collection of non-manhattan geometry.    */

    for (tp = BL(tile); BOTTOM(tp) < TOP(tile); tp = RT(tp))
      if (IsSplit(tp))
          break;
    if (BOTTOM(tp) < TOP(tile))
      return 0;
#endif

    /* Note that the max horizontal stripes rule guarantees */
    /* that a tile is always bounded on left and right by   */
    /* TT_SPACE.  Thus, we only need to search the top and  */
    /* bottom boundaries of horizontal tiles.               */

    if (vertical)
    {
      newStrip = (linkedStrip *)mallocMagic(sizeof(linkedStrip));
      newStrip->area = bbox;
      newStrip->vertical = TRUE;
      newStrip->shrink_ur = (TTMaskHasType(&CIFSolidBits,
                  TiGetBottomType(RT(tile)))) ? TRUE : FALSE;
      newStrip->shrink_ld = (TTMaskHasType(&CIFSolidBits,
                  TiGetTopType(LB(tile)))) ? TRUE : FALSE;
      newStrip->strip_next = stripsData->strips;
      stripsData->strips = newStrip;
    }
    else
    {
      int segstart, segend;
      int matchstart, matchend;

      tp = RT(tile);
      segend = RIGHT(tile);
      while (RIGHT(tp) > LEFT(tile))
      {
          /* Isolate segments of space along the top of the tile */

          while ((RIGHT(tp) > LEFT(tile)) &&
                  TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
            tp = BL(tp);
          segend = MIN(segend, RIGHT(tp));
          while ((RIGHT(tp) > LEFT(tile)) &&
                  TTMaskHasType(&DBSpaceBits, TiGetBottomType(tp)))
            tp = BL(tp);
          segstart = MAX(LEFT(tile), RIGHT(tp));
          if (segend <= segstart) break; 

          /* Find matching segments along the bottom of the  tile */

          for (tp2 = LB(tile); RIGHT(tp2) < segstart; tp2 = TR(tp2));

          while (LEFT(tp2) < segend)
          {
            while (RIGHT(tp2) < segstart) tp2 = TR(tp2);
            while ((LEFT(tp2) < segend) &&
                        TTMaskHasType(&CIFSolidBits, TiGetTopType(tp2)))
                tp2 = TR(tp2);
            matchstart = MAX(LEFT(tp2), segstart);
            while ((LEFT(tp2) < segend) &&
                        TTMaskHasType(&DBSpaceBits, TiGetTopType(tp2)))
                tp2 = TR(tp2);
            matchend = MIN(LEFT(tp2), segend);
            if (matchend <= matchstart) break; 

            /* Process the strip */

            newStrip = (linkedStrip *)mallocMagic(sizeof(linkedStrip));
            newStrip->area = bbox;
            newStrip->area.r_xbot = matchstart;
            newStrip->area.r_xtop = matchend;
            newStrip->vertical = FALSE;
            newStrip->strip_next = stripsData->strips;
            newStrip->shrink_ur = (matchend != RIGHT(tile)) ? TRUE : FALSE;
            newStrip->shrink_ld = (matchstart != LEFT(tile)) ? TRUE : FALSE;

            stripsData->strips = newStrip;
          }
      }
    }
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquaresFillArea --
 *
 *    Fill areas in the current CIF output plane with contact cuts based on
 *    the SQUARES operation passed in "op".  This differs from the original
 *    tile-based contact cut generation by collecting all connected tiles
 *    in an area, and placing cuts relative to that area's bounding box.
 *    A tile search is used to select the parts of any non-rectangular area
 *    inside the bounding box that allow contact cuts, which lets cuts 
 *    be placed across tile boundaries and inside non-manhattan tiles.
 *    It also allows contacts to be placed inside complex structures such
 *    as (possibly intersecting) guardrings.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *
 * ----------------------------------------------------------------------------
 */

void
cifSquaresFillArea(op, cellDef, plane)
    CIFOp *op;
    CellDef *cellDef;
    Plane *plane;
{
    Tile *tile, *t, *tp;
    Rect bbox, area, square, cut, llcut;
    int nAcross, nUp, left, pitch, size, diff, right;
    int i, j, k, savecount;
    TileType type;
    SquaresData *squares = (SquaresData *)op->co_client;
    StripsData stripsData;
    linkedStrip *stripList;
    bool simple;
    static Stack *CutStack = (Stack *)NULL;

    pitch = squares->sq_size + squares->sq_sep;
    size = squares->sq_size + 2 * squares->sq_border;
    diff = squares->sq_sep - 2 * squares->sq_border;

    if (CutStack == (Stack *)NULL)
      CutStack = StackNew(64);

    /* Two-pass algorithm */

    /* Search the plane for "strips", sections of contact that are only */
    /* wide enough for 1 cut.  Process them separately, then erase the  */
    /* processed areas.   The purpose of this is to avoid applying the  */
    /* contact matrix algorithm on non-convex spaces, such as guard     */
    /* rings, where centering the matrix on the bounding box of the     */
    /* contact area may produce a matrix misaligned with the contact    */
    /* strips, preventing any contacts from being drawn!  Due to the    */
    /* maximum horizontal stripes rule for corner stitched tiles, we    */
    /* need only identify vertical contact strips.  After processing    */
    /* and erasing them, all remaining areas will be convex.  This      */
    /* algorithm allows contacts to be drawn in any arbitrary geometry. */

    stripsData.size = size;
    stripsData.pitch = pitch;
    stripsData.strips = NULL;
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
            cifSquaresStripFunc, (ClientData)&stripsData);

    /* Generate cuts in each strip found, then erase the strip */

    stripList = stripsData.strips;
    while (stripList != NULL)
    {
      Rect stripLess = stripList->area;
      
      if (diff > 0)
      {
          if (stripList->vertical)
          {
            if (stripList->shrink_ur) stripLess.r_ytop -= diff;
            if (stripList->shrink_ld) stripLess.r_ybot += diff;
          }
          else
          {
            if (stripList->shrink_ur) stripLess.r_xtop -= diff;
            if (stripList->shrink_ld) stripLess.r_xbot += diff;
          }
      }

      /* Create the cuts */

      if (op->co_opcode == CIFOP_SQUARES)
          cifSquareFunc(&stripLess, op, &nUp, &nAcross, &llcut);
      else if (op->co_opcode == CIFOP_SQUARES_G)
          cifSquareGridFunc(&stripLess, op, &nUp, &nAcross, &llcut);

      cut.r_ybot = llcut.r_ybot;
      cut.r_ytop = llcut.r_ytop;

      for (i = 0; i < nUp; i++)
      {
          cut.r_xbot = llcut.r_xbot;
          cut.r_xtop = llcut.r_xtop;
          for (j = 0; j < nAcross; j++)
          {
            DBPaintPlane(cifPlane, &cut, CIFPaintTable, (PaintUndoInfo *)NULL);
            cut.r_xbot += pitch;
            cut.r_xtop += pitch;
          }
          cut.r_ybot += pitch;
          cut.r_ytop += pitch;
      }
      if (nUp == 0)
      {
          if (stripList->shrink_ur == 0 && stripList->shrink_ld == 0)
            CIFError(&stripList->area, "no room for contact cuts in area!");

          /* This is rather ad hoc, but works reasonably well:  Assume that   */
          /* a strip that has enough total area for two or more cuts but      */
          /* which fits none is a mistake.  This code catches problems due    */
          /* to contact areas of the proper size not fitting cuts because the */
          /* squares_grid offset prohibits it.                    */
          else if (((stripList->area.r_ur.p_x - stripList->area.r_ll.p_x) *
                  (stripList->area.r_ur.p_y - stripList->area.r_ll.p_y)) >
                  2 * (pitch * pitch))
            CIFError(&stripList->area, "contact strip with no room for cuts!");
      }

      DBPaintPlane(plane, &stripList->area, CIFEraseTable,
                  (PaintUndoInfo *) NULL);

      freeMagic(stripList);
      stripList = stripList->strip_next;
    }

    /* 2nd pass:  Search the plane for unmarked tiles */

    while (DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
            cifSquaresInitFunc, (ClientData)NULL) != 0)
    {
      /* Now, search for (nontrivially) connected tiles in all    */
      /* directions.  Mark the tiles, and record the bounding box.      */
      /* (Largely copied from cifBloatAllFunc)              */

      simple = TRUE;
      tile = plane->pl_hint;
      TiToRect(tile, &bbox);
      
      PUSHTILE(tile, CutStack);
      while (!StackEmpty(CutStack))
      {
          t = (Tile *) STACKPOP(CutStack);
          if (t->ti_client != (ClientData)CIF_PENDING) continue;
            t->ti_client = (ClientData)CIF_PROCESSED;
      
          /* Adjust bounding box */
          TiToRect(t, &area);
          GeoInclude(&area, &bbox);

#ifdef NONMANHATTAN
          if (IsSplit(t)) simple = FALSE;
#endif

          /* Top */
          for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
            if (TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
            {
                simple = FALSE;
                PUSHTILE(tp, CutStack);
            }

          /* Left */
          for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
            if (TTMaskHasType(&CIFSolidBits, TiGetRightType(tp)))
            {
                simple = FALSE;
                PUSHTILE(tp, CutStack);
            }

          /* Bottom */
          for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
            if (TTMaskHasType(&CIFSolidBits, TiGetTopType(tp)))
            {
                simple = FALSE;
                PUSHTILE(tp, CutStack);
            }

          /* Right */
          for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
            if (TTMaskHasType(&CIFSolidBits, TiGetLeftType(tp)))
            {
                simple = FALSE;
                PUSHTILE(tp, CutStack);
            }
      }

      savecount = CIFTileOps;

      for (k = 0; k < 3; k++) /* prepare for up to 3 passes */
      {

          /* Determine the contact cut offsets from the bounding box */

          if (op->co_opcode == CIFOP_SQUARES)
            cifSquareFunc(&bbox, op, &nUp, &nAcross, &llcut);
          else if (op->co_opcode == CIFOP_SQUARES_G)
            cifSquareGridFunc(&bbox, op, &nUp, &nAcross, &llcut);

          cut.r_ybot = llcut.r_ybot;
          cut.r_ytop = llcut.r_ytop;

          /* For each contact cut area, check that there is */
          /* no whitespace                            */

          for (i = 0; i < nUp; i++)
          {
            cut.r_xbot = llcut.r_xbot;
            cut.r_xtop = llcut.r_xtop;

            square.r_ybot = cut.r_ybot - squares->sq_border;
            square.r_ytop = cut.r_ytop + squares->sq_border;

            for (j = 0; j < nAcross; j++)
            {
                square.r_xbot = cut.r_xbot - squares->sq_border;
                square.r_xtop = cut.r_xtop + squares->sq_border;

                /* If there is only one simple rectangle in the   */
                /* area, the area is convex, so we don't have to  */
                /* check for unconnected regions                  */

                if (simple || DBSrPaintArea((Tile *)tile, plane,
                        &square, &DBSpaceBits, cifUnconnectFunc,
                        (ClientData)NULL) == 0)
                {
                  DBPaintPlane(cifPlane, &cut, CIFPaintTable,
                        (PaintUndoInfo *)NULL);
                  CIFTileOps++;
                }
                cut.r_xbot += pitch;
                cut.r_xtop += pitch;
            }
            cut.r_ybot += pitch;
            cut.r_ytop += pitch;
          }
          if (savecount != CIFTileOps) break;

          /* In non_Manhattan regions with beveled corners, where */
          /* the bounding box has space for 2 contacts, there may not   */
          /* be space in the shape itself for more than one.  We will   */
          /* attempt to shrink X, Y, and/or both to fit (up to 3  */
          /* passes may be necessary).                      */

          if (nUp == 2)
          {
            int bdiff = 1 + (bbox.r_ytop - bbox.r_ybot) -
                  (2 * (squares->sq_size + squares->sq_border) +
                  squares->sq_sep);
            if (bdiff & 0x1) bdiff++;     /* bdiff must be even   */
            bdiff >>= 1;                  /* take half            */
            bbox.r_ytop -= bdiff;
            bbox.r_ybot += bdiff;
          }
          else if (nAcross == 2)
          {
            int bdiff = 1 + (bbox.r_xtop - bbox.r_xbot) -
                  (2 * (squares->sq_size + squares->sq_border) +
                  squares->sq_sep);
            if (bdiff & 0x1) bdiff++;     /* bdiff must be even   */
            bdiff >>= 1;                  /* take half            */
            bbox.r_xtop -= bdiff;
            bbox.r_xbot += bdiff;
          }
          else
            break;
      }
      if (savecount == CIFTileOps)
          CIFError(&bbox, "no room for contacts in area!");

      /* Clear the tiles that were processed */

      tile->ti_client = (ClientData)CIF_IGNORE;
      STACKPUSH(tile, CutStack);
      while (!StackEmpty(CutStack))
      {
          t = (Tile *) STACKPOP(CutStack);

          /* Top */
          for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
            if (tp->ti_client == (ClientData)CIF_PROCESSED)
            {
                tp->ti_client = (ClientData)CIF_IGNORE;
                STACKPUSH(tp, CutStack);
            }

          /* Left */
          for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
            if (tp->ti_client == (ClientData)CIF_PROCESSED)
            {
                tp->ti_client = (ClientData)CIF_IGNORE;
                STACKPUSH(tp, CutStack);
            }

          /* Bottom */
          for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
            if (tp->ti_client == (ClientData)CIF_PROCESSED)
            {
                tp->ti_client = (ClientData)CIF_IGNORE;
                STACKPUSH(tp, CutStack);
            }

          /* Right */
          for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
            if (tp->ti_client == (ClientData)CIF_PROCESSED)
            {
                tp->ti_client = (ClientData)CIF_IGNORE;
                STACKPUSH(tp, CutStack);
            }
      }
    }

    /* Clear all the tiles that were processed (is this step necessary?) */
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
            cifSquaresResetFunc, (ClientData)NULL);
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatMaxFunc --
 *
 *    Called once for each tile to be selectively bloated or
 *    shrunk using the CIFOP_BLOATMAX or CIFOP_BLOATMIN operation.
 *
 * Results:
 *    Always returns 0 to keep the search alive.
 *
 * Side effects:
 *    Uses the bloat table in the current CIFOp to expand or shrink
 *    the tile, depending on which tiles it abuts.  The rectangular
 *    area of the tile is modified by moving each side in or out
 *    by the maximum bloat distance for any of its neighbors on
 *    that side.  The result is a new rectangle, which is OR'ed
 *    into the result plane.  Note:  any edge between two tiles of
 *    same type is given a zero bloat factor.
 *
 * ----------------------------------------------------------------------------
 */

int
cifBloatMaxFunc(tile, op)
    Tile *tile;               /* The tile to be processed. */
    CIFOp *op;                /* Describes the operation to be performed
                         * (all we care about is the opcode and
                         * bloat table).
                         */
{
    Rect area;
    int bloat, tmp;
    Tile *t;
    TileType type, otherType;
    BloatData *bloats = (BloatData *)op->co_client;

    /* Get the tile into CIF coordinates. */

    type = TiGetType(tile);
    TiToRect(tile, &area);
    area.r_xbot *= cifScale;
    area.r_ybot *= cifScale;
    area.r_xtop *= cifScale;
    area.r_ytop *= cifScale;

    /* See how much to adjust the left side of the tile. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = BL(tile); BOTTOM(t) < TOP(tile); t = RT(t))
    {    
      otherType = TiGetType(t);
      if (otherType == type) continue;
      tmp = bloats->bl_distance[otherType];
      if (op->co_opcode == CIFOP_BLOATMAX)
      {
          if (tmp > bloat) bloat = tmp;
      }
      else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
      area.r_xbot -= bloat;

    /* Now figure out how much to adjust the top side of the tile. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = RT(tile); RIGHT(t) > LEFT(tile); t = BL(t))
    {    
      otherType = TiGetType(t);
      if (otherType == type) continue;
      tmp = bloats->bl_distance[otherType];
      if (op->co_opcode == CIFOP_BLOATMAX)
      {
          if (tmp > bloat) bloat = tmp;
      }
      else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
      area.r_ytop += bloat;

    /* Now the right side. */
 
    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = TR(tile); TOP(t) > BOTTOM(tile); t = LB(t))
    {    
      otherType = TiGetType(t);
      if (otherType == type) continue;
      tmp = bloats->bl_distance[otherType];
      if (op->co_opcode == CIFOP_BLOATMAX)
      {
          if (tmp > bloat) bloat = tmp;
      }
      else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
      area.r_xtop += bloat;

    /* Lastly, do the bottom side. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = LB(tile); LEFT(t) < RIGHT(tile); t = TR(t))
    {    
      otherType = TiGetType(t);
      if (otherType == type) continue;
      tmp = bloats->bl_distance[otherType];
      if (op->co_opcode == CIFOP_BLOATMAX)
      {
          if (tmp > bloat) bloat = tmp;
      }
      else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
      area.r_ybot -= bloat;

    /* Make sure the tile didn't shrink into negativity.  If it's
     * ok, paint it into the new plane being built.
     */

    if ((area.r_xbot > area.r_xtop) || (area.r_ybot > area.r_ytop))
    {
      TiToRect(tile, &area);
      area.r_xbot *= cifScale;
      area.r_xtop *= cifScale;
      area.r_ybot *= cifScale;
      area.r_ytop *= cifScale;
      CIFError(&area, "tile inverted by shrink");
    }
    else
#ifdef NONMANHATTAN
      DBNMPaintPlane(cifPlane, TiGetTypeExact(tile), &area,
            CIFPaintTable, (PaintUndoInfo *) NULL);
#else
      DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
#endif

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * inside_triangle --
 *
 *    Test if the specified rectangle is completely inside the tile.
 *    Tile is presumed to be a split tile.
 *
 * Results:
 *    TRUE if inside, FALSE if outside or overlapping.
 *
 * Side Effects:
 *    None.
 *
 * Notes:
 *    This is an optimized version of the code in DBtiles.c.  It
 *    assumes that the square is never infinite.
 *
 * ----------------------------------------------------------------------------
 */

bool
inside_triangle(rect, tile)
    Rect *rect;
    Tile *tile;
{
    int theight, twidth;
    dlong f1, f2, f3, f4;

    theight = TOP(tile) - BOTTOM(tile);
    twidth = RIGHT(tile) - LEFT(tile);

    f1 = (dlong)(TOP(tile) - rect->r_ybot) * twidth;
    f2 = (dlong)(rect->r_ytop - BOTTOM(tile)) * twidth;

    if (SplitLeftType(tile) != TT_SPACE)
    {
        /* Inside-of-triangle check */
        f4 = (dlong)(rect->r_xbot - LEFT(tile)) * theight;
        if (SplitDirection(tile) ? (f1 > f4) : (f2 > f4))
          return TRUE;
    }
    else
    {
        /* Inside-of-triangle check */
        f3 = (dlong)(RIGHT(tile) - rect->r_xtop) * theight;
        if (SplitDirection(tile) ? (f2 > f3) : (f1 > f3))
          return TRUE;
    }
    return FALSE;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifContactFunc --
 *
 *    Called for each relevant tile when chopping up contacts into
 *    square cuts using the procedure of using a pre-defined cell
 *    definition of a single contact and arraying the cell.
 *    Technically, this is not a CIF function because CIF does not
 *    have an array method for cells, so there is no advantage to
 *    drawing lots of subcells in place of drawing lots of boxes.
 *    In GDS, however, the array method is much more compact than
 *    drawing individual cuts when the array size is larger than 1.
 *
 * Results:
 *    Normally returns 0 to keep the search going.  Return 1 if
 *    the contact type cannot be found, which halts the search.
 *
 * Side effects:
 *    Stuff is painted into cifPlane.
 *
 * ----------------------------------------------------------------------------
 */

int
cifContactFunc(tile, csi)
    Tile *tile;               /* Tile to be diced up. */
    CIFSquaresInfo *csi;      /* Describes how to generate squares. */
{
    Rect area;
    int i, nAcross, j, nUp, left, bottom, pitch, halfsize;
    bool result;
    SquaresData *squares = csi->csi_squares;

#ifdef NONMANHATTAN
    /* For now, don't allow squares on non-manhattan tiles */
    if (IsSplit(tile))
      return 0;
#endif

    TiToRect(tile, &area);
    pitch = squares->sq_size + squares->sq_sep;

    nAcross = (area.r_xtop - area.r_xbot + squares->sq_sep
          - (2 * squares->sq_border)) / pitch;
    if (nAcross == 0)
    {
      left = (area.r_xbot + area.r_xtop - squares->sq_size) / 2;
      if (left >= area.r_xbot) nAcross = 1;
    }
    else
      left = (area.r_xbot + area.r_xtop + squares->sq_sep
            - (nAcross * pitch)) / 2;

    nUp = (area.r_ytop - area.r_ybot + squares->sq_sep
          - (2 * squares->sq_border)) / pitch;
    if (nUp == 0)
    {
      bottom = (area.r_ybot + area.r_ytop - squares->sq_size) / 2;
      if (bottom >= area.r_ybot) nUp = 1;
    }
    else
      bottom = (area.r_ybot + area.r_ytop + squares->sq_sep
            - (nUp * pitch)) / 2;

    /* Lower-left coordinate should be centered on the contact cut, as
     * contact definitions are centered on the origin.
     */
    halfsize = (squares->sq_size / 2);
    left += halfsize;
    bottom += halfsize;

    result = CalmaGenerateArray((FILE *)csi->csi_client, csi->csi_type,
            left, bottom, pitch, nAcross, nUp);

    return (result == TRUE) ? 0 : 1;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSlotFunc --
 *
 *    Called for each relevant tile when chopping areas up into
 *    slots (rectangles).  Chops each tile up into slots and paints
 *    into cifPlane.
 *
 * Results:
 *    Always return 0
 *
 * Side effects:
 *    Stuff is painted into cifPlane.
 *
 * ----------------------------------------------------------------------------
 */

int
cifSlotFunc(tile, op)
    Tile *tile;               /* Tile to be diced up. */
    CIFOp *op;                /* Describes how to generate squares. */
{
    Rect area, slot;
    int i, nAcross, j, nUp, width, height, xpitch, ypitch, left;
    int *axtop, *axbot, *aytop, *aybot;
    int *sxtop, *sxbot, *sytop, *sybot;
    TileType type;
    SlotsData *slots = (SlotsData *)op->co_client;

#ifdef NONMANHATTAN
    /* For now, don't allow squares on non-manhattan tiles */
    if (IsSplit(tile))
      return 0;
#endif

    TiToRect(tile, &area);
    width = area.r_xtop - area.r_xbot;
    height = area.r_ytop - area.r_ybot;

    /* Orient to the short/long orientation of the tile */

    /* Assume a vertical tile;  if not, reorient area and remember */
    if (width > height)
    {
      axbot = &area.r_ybot;
      aybot = &area.r_xbot;
      axtop = &area.r_ytop;
      aytop = &area.r_xtop;
      sxbot = &slot.r_ybot;
      sybot = &slot.r_xbot;
      sxtop = &slot.r_ytop;
      sytop = &slot.r_xtop;
      width = *axtop - *axbot;
      height = *aytop - *aybot;
    }
    else
    {
      axbot = &area.r_xbot;
      aybot = &area.r_ybot;
      axtop = &area.r_xtop;
      aytop = &area.r_ytop;
      sxbot = &slot.r_xbot;
      sybot = &slot.r_ybot;
      sxtop = &slot.r_xtop;
      sytop = &slot.r_ytop;
    }

    xpitch = slots->sl_ssize + slots->sl_ssep;

calcX:
    nAcross = (width + slots->sl_ssep - (2 * slots->sl_sborder)) / xpitch;
    if (nAcross == 0)
    {
      left = (*axbot + *axtop - slots->sl_ssize) / 2;
      if (left >= *axbot) nAcross = 1;
    }
    else
      left = (*axbot + *axtop + slots->sl_ssep - (nAcross * xpitch)) / 2;

    /* Check that we are not violating any gridlimit */

    if (CIFCurStyle && (CIFCurStyle->cs_gridLimit > 0))
    {
      int delta = abs(left) % CIFCurStyle->cs_gridLimit;
      if (delta > 0)
      {
          *axtop -= 2 * delta;
          goto calcX;
      }
    }


    if (slots->sl_lsize > 0)
    {
      ypitch = slots->sl_lsize + slots->sl_lsep;
calcY:
      nUp = (*aytop - *aybot + slots->sl_lsep - (2 * slots->sl_lborder)) / ypitch;
      if (nUp == 0)
      {
          *sybot = (*aybot + *aytop - slots->sl_lsize) / 2;
          if (*sybot >= *aybot) nUp = 1;
      }
      else
          *sybot = (*aybot + *aytop + slots->sl_lsep - (nUp * ypitch)) / 2;
      *sytop = *sybot + slots->sl_lsize;

      /* Check that we are not violating any gridlimit */

      if (CIFCurStyle && (CIFCurStyle->cs_gridLimit > 0))
      {
          int delta = abs(*sybot) % CIFCurStyle->cs_gridLimit;
          if (delta > 0)
          {
            *aytop -= 2 * delta;
            goto calcY;
          }
      }
    }
    else
    {
      nUp = 1;
      *sybot = *aybot + slots->sl_lborder;
      *sytop = *aytop - slots->sl_lborder;
      /* There's no space to fit a slot */
      if (*sytop - *sybot <= 0)
          return 0;
    }

    /* To be done---slot offsets */

    for (i = 0; i < nUp; i++)
    {
      *sxbot = left;
      for (j = 0; j < nAcross; j++)
      {
          *sxtop = *sxbot + slots->sl_ssize;

          DBPaintPlane(cifPlane, &slot, CIFPaintTable,
                  (PaintUndoInfo *) NULL);
          CIFTileOps += 1;
          *sxbot += xpitch;
      }
      *sybot += ypitch;
      *sytop += ypitch;
    }
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquareFunc --
 *
 *    Called for each relevant rectangle when chopping areas up into
 *    squares.   Determines the number of rows and columns in the area
 *    and returns these and the area of the lower-left cut.
 *
 * Results:
 *    Always return 0
 *
 * Side effects:
 *    Results filled in the pointer positions passed to the function
 *
 * ----------------------------------------------------------------------------
 */

int
cifSquareFunc(area, op, rows, columns, cut)
    Rect *area;               /* Area to be diced up */
    CIFOp *op;                /* Describes how to generate squares.     */
    int *rows, *columns;      /* Return values: # rows and # columns,   */
    Rect *cut;                /* initial (lower left) cut area.   */
{
    int pitch;
    SquaresData *squares = (SquaresData *)op->co_client;

    pitch = squares->sq_size + squares->sq_sep;

    /* Compute the real border to leave around the sides.  If only
     * one square will fit in a particular direction, center it
     * regardless of the requested border size.  If more than one
     * square will fit, then fit it in extras only if at least the
     * requested border size can be left.  Also center things in the
     * rectangle, so that the box's exact size doesn't matter. This
     * trickiness is done so that coincident contacts from overlapping
     * cells always have their squares line up, regardless of the
     * orientation of the cells.
     *
     * Update 1/13/09:  Don't generate contacts with a border less than
     * the required amount.  Use the slots function for contacts having
     * different border allowances on different sides.
     */

    *columns = (area->r_xtop - area->r_xbot + squares->sq_sep
          - (2 * squares->sq_border)) / pitch;
    if (*columns == 0)
    {
      *rows = 0;
      return 0;
      // cut->r_xbot = (area->r_xbot + area->r_xtop - squares->sq_size) / 2;
      // if (cut->r_xbot >= area->r_xbot) *columns = 1;
    }
    else
    {
      cut->r_xbot = (area->r_xbot + area->r_xtop + squares->sq_sep
            - (*columns * pitch)) / 2;
    }

    *rows = (area->r_ytop - area->r_ybot + squares->sq_sep
          - (2 * squares->sq_border)) / pitch;
    if (*rows == 0)
    {
      return 0;
      // cut->r_ybot = (area->r_ybot + area->r_ytop - squares->sq_size) / 2;
      // if (cut->r_ybot >= area->r_ybot) *rows = 1;
    }
    else
    {
      cut->r_ybot = (area->r_ybot + area->r_ytop + squares->sq_sep
            - (*rows * pitch)) / 2;
    }

    cut->r_xtop = cut->r_xbot + squares->sq_size;
    cut->r_ytop = cut->r_ybot + squares->sq_size;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquareGridFunc --
 *
 *    Called for each relevant rectangle when chopping areas up into
 *    squares.   Determines the number of rows and columns in the area
 *    and returns these and the area of the lower-left cut.
 *
 * Results:
 *    Always return 0
 *
 * Side effects:
 *    Results filled in the pointer positions passed to the function
 *
 * ----------------------------------------------------------------------------
 */

int
cifSquareGridFunc(area, op, rows, columns, cut)
    Rect *area;               /* Area to be diced up */
    CIFOp *op;                /* Describes how to generate squares.     */
    int *rows, *columns;      /* Return values: # rows and # columns,   */
    Rect *cut;                /* initial (lower left) cut area.   */
{
    Rect locarea;
    int left, bottom, right, top, pitch;
    int gridx, gridy, margin;
    SquaresData *squares = (SquaresData *)op->co_client;

    /*
     * It may be necessary to generate contacts on a specific grid; e.g.,
     * to avoid placing contacts at half-lambda.  If this is the case,
     * then the DRC section of the techfile should specify "no overlap"
     * for these types.
     *
     * This routine has been simplified.  It flags a warning when there
     * is not enough space for a contact cut, rather than attempting to
     * draw a cut without enough border area.  The routine has also been
     * extended to allow different x and y grids to be specified.  This
     * allows certain tricks, such as generating offset contact grids on
     * a pad, as required by some processes.
     */

    pitch = squares->sq_size + squares->sq_sep;
    gridx = squares->sq_gridx;
    gridy = squares->sq_gridy;

    locarea.r_xtop = area->r_xtop - squares->sq_border;
    locarea.r_ytop = area->r_ytop - squares->sq_border;
    locarea.r_xbot = area->r_xbot + squares->sq_border;
    locarea.r_ybot = area->r_ybot + squares->sq_border;

    left = locarea.r_xbot / gridx;
    left *= gridx;
    if (left < locarea.r_xbot) left += gridx;

    bottom = locarea.r_ybot / gridy;
    bottom *= gridy;
    if (bottom < locarea.r_ybot) bottom += gridy;

    *columns = (locarea.r_xtop - left + squares->sq_sep) / pitch;
    if (*columns == 0)
    {
      *rows = 0;
      return 0;
    }
    
    *rows = (locarea.r_ytop - bottom + squares->sq_sep) / pitch;
    if (*rows == 0) return 0;

    /* Center the contacts while remaining on-grid */
    right = left + *columns * squares->sq_size + (*columns - 1) * squares->sq_sep;
    top = bottom + *rows * squares->sq_size + (*rows - 1) * squares->sq_sep;
    margin = ((locarea.r_xtop - right) - (left - locarea.r_xbot)) / (gridx * 2);
    locarea.r_xbot = left + margin * gridx;
    margin = ((locarea.r_ytop - top) - (bottom - locarea.r_ybot)) / (gridy * 2);
    locarea.r_ybot = bottom + margin * gridy;

    cut->r_ybot = locarea.r_ybot;
    cut->r_ytop = cut->r_ybot + squares->sq_size;
    cut->r_xbot = locarea.r_xbot;
    cut->r_xtop = cut->r_xbot + squares->sq_size;
    return 0;
}


/*
 * ----------------------------------------------------------------------------
 *
 * cifSrTiles --
 *
 *    This is a utility procedure that just calls DBSrPaintArea
 *    one or more times for the planes being used in processing
 *    one CIFOp.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *    This procedure itself has no side effects.  For each of the
 *    paint or temporary planes indicated in cifOp, we call
 *    DBSrPaintArea to find the desired tiles in the desired
 *    area for the operation.  DBSrPaintArea is given func as a
 *    search function, and cdArg as ClientData.
 *
 * ----------------------------------------------------------------------------
 */

void
cifSrTiles(cifOp, area, cellDef, temps, func, cdArg)
    CIFOp *cifOp;       /* Geometric operation being processed. */
    Rect *area;               /* Area of Magic paint to consider. */
    CellDef *cellDef;         /* CellDef to search for paint. */
    Plane *temps[];           /* Planes to use for temporaries. */
    int (*func)();            /* Search function to pass to DBSrPaintArea. */
    ClientData cdArg;         /* Client data for func. */
{
    TileTypeBitMask maskBits;
    TileType t;
    int i;
    BloatData *bloats;

    /* When reading data from a cell, it must first be scaled to
     * CIF units.  Check for CIFCurStyle, as we don't want to
     * crash while reading CIF/GDS just becuase the techfile
     * "cifoutput" section was blank.
     */

    cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;

    /* Bloat operations have to be in a single plane */

    switch (cifOp->co_opcode) {
      case CIFOP_BLOAT:
      case CIFOP_BLOATMIN:
      case CIFOP_BLOATMAX:
          bloats = (BloatData *)cifOp->co_client;
          i = bloats->bl_plane;
          maskBits = DBPlaneTypes[i];
          TTMaskAndMask(&maskBits, &cifOp->co_paintMask);
          if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
            DBSrPaintArea((Tile *) NULL, cellDef->cd_planes[i],
                        area, &cifOp->co_paintMask, func, cdArg);
          break;

      default:
          for (i = PL_DRC_CHECK; i < DBNumPlanes; i++)
          {
            maskBits = DBPlaneTypes[i];
            TTMaskAndMask(&maskBits, &cifOp->co_paintMask);
            if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
                (void) DBSrPaintArea((Tile *) NULL, cellDef->cd_planes[i],
                  area, &cifOp->co_paintMask, func, cdArg);
          }
          break;
    }

    /* When processing CIF data, use everything in the plane. */

    cifScale = 1;
    for (t = 0; t < TT_MAXTYPES; t++, temps++)
      if (TTMaskHasType(&cifOp->co_cifMask, t))
          (void) DBSrPaintArea((Tile *) NULL, *temps, &TiPlaneRect,
            &CIFSolidBits, func, (ClientData) cdArg);
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFGenLayer --
 *
 *    This routine will generate one CIF layer.
 *    It provides the core of the CIF generator.
 *
 * Results:
 *    Returns a malloc'ed plane with tiles of type CIF_SOLIDTYPE
 *    marking the area of this CIF layer as built up by op.
 *
 * Side effects:
 *    None, except to create a new plane holding the CIF for the layer.
 *    The CIF that's generated may fall outside of area... it's what
 *    results from considering everything in area.  In most cases the
 *    caller will clip the results down to the desired area.
 *
 * ----------------------------------------------------------------------------
 */

Plane *
CIFGenLayer(op, area, cellDef, temps, clientdata)
    CIFOp *op;                /* List of CIFOps telling how to make layer. */
    Rect *area;               /* Area to consider when generating CIF.  Only
                         * material in this area will be considered, so
                         * the caller should usually expand his desired
                         * area by one CIF radius.
                         */
    CellDef *cellDef;         /* CellDef to search when paint layers are
                         * needed for operation.
                         */
    Plane *temps[];           /* Temporary layers to be used when needed
                         * for operation.
                         */
    ClientData clientdata;    /*
                         * Data that may be passed to the CIF operation
                         * function.
                         */
{
    Plane *temp;
    static Plane *nextPlane, *curPlane;
    Rect bbox;
    CIFOp *tempOp;
    CIFSquaresInfo csi;
    int (*cifGrowFuncPtr)() = (CIFCurStyle->cs_flags & CWF_GROW_EUCLIDEAN) ?
            cifGrowEuclideanFunc : cifGrowFunc;

    /* Set up temporary planes used during computation.  One of these
     * will be returned as the result (whichever is curPlane at the
     * end of the computation).  The other is saved for later use.
     */

    if (nextPlane == NULL)
      nextPlane = DBNewPlane((ClientData) TT_SPACE);
    curPlane = DBNewPlane((ClientData) TT_SPACE);

    /* Go through the geometric operations and process them one
     * at a time.
     */

    for ( ; op != NULL; op = op->co_next)
    {
      switch (op->co_opcode)
      {
          /* For AND, first collect all the stuff to be anded with
           * plane in a temporary plane.  Then find all the places
           * where there isn't any stuff, and erase from the
           * current plane.
           */

          case CIFOP_AND:
            DBClearPaintPlane(nextPlane);
            cifPlane = nextPlane;
            cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
                (ClientData) CIFPaintTable);
            cifPlane = curPlane;
            cifScale = 1;
            (void) DBSrPaintArea((Tile *) NULL, nextPlane, &TiPlaneRect,
                &DBSpaceBits, cifPaintFunc,
                (ClientData) CIFEraseTable);
            break;
          
          /* For OR, just use cifPaintFunc to OR the areas of all
           * relevant tiles into plane.  HOWEVER, if the co_client
           * record is non-NULL and CalmaContactArrays is TRUE,
           * then for each contact type, we do the paint function
           * separately, then call the contact array generation
           * procedure.
           */

          case CIFOP_OR:
            cifPlane = curPlane;
            cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;

            if ((op->co_client != (ClientData)NULL)
                        && (CalmaContactArrays == TRUE))
            {
                TileTypeBitMask paintMask, errMask, *rMask;
                TileType i, j;

                TTMaskZero(&errMask);
                TTMaskZero(&paintMask);
                TTMaskSetMask(&paintMask, &op->co_paintMask);
                for (i = TT_TECHDEPBASE; i < DBNumUserLayers; i++)
                {
                  if (TTMaskHasType(&paintMask, i))
                  {
                      TTMaskSetOnlyType(&op->co_paintMask, i);
                      for (j = DBNumUserLayers; j < DBNumTypes; j++)
                      {
                        rMask = DBResidueMask(j);
                        if (TTMaskHasType(rMask, i))
                            TTMaskSetType(&op->co_paintMask, j);
                      }

                      cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
                              (ClientData) CIFPaintTable);

                      csi.csi_squares = (SquaresData *)op->co_client;
                      csi.csi_type = i;
                      csi.csi_client = clientdata;

                      if (DBSrPaintArea((Tile *) NULL, curPlane,
                              &TiPlaneRect, &CIFSolidBits,
                              cifContactFunc,   (ClientData) &csi))
                      {
                        /* Failure of DBSrPaintArea() (returns 1)
                         * indicates that a contact cell type
                         * could not be found for magic layer i.
                         * Record the error for subsequent handling.
                         */
                        TTMaskSetType(&errMask, i);
                      }
                      DBClearPaintPlane(curPlane);
                  }
                }
                if (!TTMaskIsZero(&errMask))
                {
                  /*
                   * Handle layers for which a contact cell could
                   * not be found in the default manner.
                   */
                  TTMaskZero(&op->co_paintMask);
                  TTMaskSetMask(&op->co_paintMask, &errMask);
                  cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
                        (ClientData) CIFPaintTable);
                }

                /* Recover the original magic layer mask for the cifop */

                TTMaskZero(&op->co_paintMask);
                TTMaskSetMask(&op->co_paintMask, &paintMask);
            }
            else
            {
                cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
                  (ClientData) CIFPaintTable);
            }
            break;
          
          /* For ANDNOT, do exactly the same thing as OR, except erase
           * instead of paint.
           */

          case CIFOP_ANDNOT:
            cifPlane = curPlane;
            cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
                (ClientData) CIFEraseTable);
            break;
          
          /* For GROW, just find all solid tiles in the current plane,
           * and paint a larger version into a new plane.  The switch
           * the current and new planes.
           */
      
          case CIFOP_GROW:
            growDistance = op->co_distance;
            DBClearPaintPlane(nextPlane);
            cifPlane = nextPlane;
            cifScale = 1;
            (void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
                &CIFSolidBits, *cifGrowFuncPtr, (ClientData) CIFPaintTable);
            temp = curPlane;
            curPlane = nextPlane;
            nextPlane = temp;
            break;

          /* GROW_G grows non-uniformly to the indicated grid. */

          case CIFOP_GROW_G:
            growDistance = op->co_distance;
            DBClearPaintPlane(nextPlane);
            cifPlane = nextPlane;
            cifScale = 1;
            (void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
                &CIFSolidBits, cifGrowGridFunc, (ClientData) CIFPaintTable);
            temp = curPlane;
            curPlane = nextPlane;
            nextPlane = temp;
            break;
          
          /* SHRINK is just like grow except work from the space tiles. */

          case CIFOP_SHRINK:
            growDistance = op->co_distance;
            DBClearPaintPlane(nextPlane);
            DBPaintPlane(nextPlane, &TiPlaneRect, CIFPaintTable,
                (PaintUndoInfo *) NULL);
            cifPlane = nextPlane;
            cifScale = 1;
            (void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
                &DBSpaceBits, *cifGrowFuncPtr, (ClientData) CIFEraseTable);
            temp = curPlane;
            curPlane = nextPlane;
            nextPlane = temp;
            break;
          
          case CIFOP_BLOAT:
            cifPlane = curPlane;
            cifSrTiles(op, area, cellDef, temps,
                cifBloatFunc, op->co_client);
            break;
          
          case CIFOP_BLOATMAX:
          case CIFOP_BLOATMIN:
            cifPlane = curPlane;
            cifSrTiles(op, area, cellDef, temps,
                cifBloatMaxFunc, (ClientData) op);
            break;

          case CIFOP_BLOATALL:
            cifPlane = curPlane;
            cifSrTiles(op, area, cellDef, temps,
                cifBloatAllFunc, (ClientData) op);
            break;
          
          case CIFOP_SQUARES:
            if (CalmaContactArrays == FALSE)
            {
                DBClearPaintPlane(nextPlane);
                cifPlane = nextPlane;
                cifSquaresFillArea(op, cellDef, curPlane);
                temp = curPlane;
                curPlane = nextPlane;
                nextPlane = temp;
            }
            break;

          case CIFOP_SQUARES_G:
            DBClearPaintPlane(nextPlane);
            cifPlane = nextPlane;
            cifSquaresFillArea(op, cellDef, curPlane);
            temp = curPlane;
            curPlane = nextPlane;
            nextPlane = temp;
            break;

          case CIFOP_SLOTS:
            DBClearPaintPlane(nextPlane);
            cifPlane = nextPlane;
            (void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
                &CIFSolidBits, cifSlotFunc, (ClientData) op);
            temp = curPlane;
            curPlane = nextPlane;
            nextPlane = temp;
            break;

          case CIFOP_BBOX:
            if (CIFErrorDef == NULL) break;

            /* co_client contains the flag (1) for top-level only */
            if ((int)op->co_client == 1)
            {
                /* Only generate output for the top-level cell */
                int found = 0;
                CellUse *celluse;
                for (celluse = CIFErrorDef->cd_parents;
                        celluse != (CellUse *) NULL;
                        celluse = celluse->cu_nextuse)
                {
                  if (celluse->cu_parent != (CellDef *) NULL)
                      if ((celluse->cu_parent->cd_flags & CDINTERNAL)
                              != CDINTERNAL)
                      {
                        found = 1;
                        break;
                      }
                }
                if (found != 0) break;
            }
            cifPlane = curPlane;
            bbox = CIFErrorDef->cd_bbox;
            cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;
            bbox.r_xbot *= cifScale;
            bbox.r_xtop *= cifScale;
            bbox.r_ybot *= cifScale;
            bbox.r_ytop *= cifScale;
#ifdef NONMANHATTAN
            DBNMPaintPlane(curPlane, CIF_SOLIDTYPE, &bbox,
                  CIFPaintTable, (PaintUndoInfo *)NULL); 
#else
            DBPaintPlane(curPlane, &bbox, CIFPaintTable,
                  (PaintUndoInfo *)NULL); 
#endif
            break;

          default:
            continue;
      }
    }

    return curPlane;
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFGen --
 *
 *    This procedure generates a complete set of CIF layers for
 *    a particular area of a particular cell.  NOTE: if the argument
 *    genAllPlanes is FALSE, only planes for those layers having
 *    a bit set in 'layers' are generated; the others are set
 *    to NULL.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *    The parameters realPlanes and tempPlanes are modified
 *    to hold the CIF and temporary layers for area of cellDef,
 *    as determined by the current CIF generation rules.
 *
 * ----------------------------------------------------------------------------
 */

void
CIFGen(cellDef, area, planes, layers, replace, genAllPlanes, clientdata)
    CellDef *cellDef;         /* Cell for which CIF is to be generated. */
    Rect *area;               /* Any CIF overlapping this area (in coords
                         * of cellDef) will be generated.  The CIF
                         * will be clipped to this area.
                         */
    Plane **planes;           /* Pointer to array of pointers to planes
                         * to hold "real" CIF layers that are
                         * generated.  Pointers may initially be
                         * NULL.
                         */
    TileTypeBitMask *layers;  /* CIF layers to generate. */
    bool replace;       /* TRUE means that the new CIF is to replace
                         * anything that was previously in planes.
                         * FALSE means that the new CIF is to be
                         * OR'ed in with the current contents of
                         * planes.
                         */
    bool genAllPlanes;        /* If TRUE, generate a tile plane even for
                         * those layers not specified as being
                         * generated in the 'layers' mask above.
                         */
    ClientData clientdata;    /* Data that may be passed along to the
                         * CIF operation functions.
                         */
{
    int i;
    Plane *new[MAXCIFLAYERS];
    Rect expanded, clip;

    /*
     * Generate the area in magic coordinates to search, and the area in
     * cif coordinates to use in clipping the results of CIFGenLayer().
     */
    cifGenClip(area, &expanded, &clip);

    /*
     * Generate all of the new layers in a temporary place.
     * If a layer isn't being generated, leave new[i] set to
     * NULL to indicate this fact.
     */
    for (i = 0; i < CIFCurStyle->cs_nLayers; i++)
    {
      if (TTMaskHasType(layers,i))
      {
          CIFErrorLayer = i;
          new[i] = CIFGenLayer(CIFCurStyle->cs_layers[i]->cl_ops,
                &expanded, cellDef, new, clientdata);
      }
      else if (genAllPlanes) new[i] = DBNewPlane((ClientData) TT_SPACE);
      else new[i] = (Plane *) NULL;
    }

    /*
     * Now mask off all the unwanted material in the new layers, and
     * either OR them into the existing layers or replace the existing
     * material with them.
     */
    for (i = 0; i < CIFCurStyle->cs_nLayers; i += 1)
    {
      if (new[i])
          cifClipPlane(new[i], &clip);

      if (replace)
      {
          if (planes[i])
          {
            DBFreePaintPlane(planes[i]);
            TiFreePlane(planes[i]);
          }
          planes[i] = new[i];
          continue;
      }

      if (planes[i])
      {
          if (new[i])
          {
            cifPlane = planes[i];
            cifScale = 1;
            (void) DBSrPaintArea((Tile *) NULL, new[i], &TiPlaneRect,
                  &CIFSolidBits, cifPaintFunc,
                  (ClientData) CIFPaintTable);
            DBFreePaintPlane(new[i]);
            TiFreePlane(new[i]);
          }
      }
      else planes[i] = new[i];
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifClipPlane --
 *
 * Erase the portions of the plane 'plane' that lie outside of 'clip'.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *    See above.
 *
 * ----------------------------------------------------------------------------
 */

void
cifClipPlane(plane, clip)
    Plane *plane;
    Rect *clip;
{
    Rect r;

    if (clip->r_xtop < TiPlaneRect.r_xtop)
    {
      r = TiPlaneRect;
      r.r_xbot = clip->r_xtop;
      DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_ytop < TiPlaneRect.r_ytop)
    {
      r = TiPlaneRect;
      r.r_ybot = clip->r_ytop;
      DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_xbot > TiPlaneRect.r_xbot)
    {
      r = TiPlaneRect;
      r.r_xtop = clip->r_xbot;
      DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_ybot > TiPlaneRect.r_ybot)
    {
      r = TiPlaneRect;
      r.r_ytop = clip->r_ybot;
      DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGenClip --
 *
 * Compute two new areas from the original area:  one ('expanded')
 * is expanded by a CIF halo and is used to determine how much of
 * the database to search to find what's relevant for CIF generation;
 * the other ('clip') is the CIF equivalent of area and is used to
 * clip the resulting CIF.  This code is tricky because area may run
 * off to infinity, and we have to be careful not to expand past infinity.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *    Sets *expanded and *clip.
 *
 * ----------------------------------------------------------------------------
 */

void
cifGenClip(area, expanded, clip)
    Rect *area;               /* Any CIF overlapping this area (in coords
                         * of cellDef) will be generated.  The CIF
                         * will be clipped to this area.
                         */
    Rect *expanded, *clip;
{
    if (area->r_xbot > TiPlaneRect.r_xbot)
    {
      clip->r_xbot = area->r_xbot * CIFCurStyle->cs_scaleFactor;
      expanded->r_xbot = area->r_xbot - CIFCurStyle->cs_radius;
    }
    else clip->r_xbot = expanded->r_xbot = area->r_xbot;
    if (area->r_ybot > TiPlaneRect.r_ybot)
    {
      clip->r_ybot = area->r_ybot * CIFCurStyle->cs_scaleFactor;
      expanded->r_ybot = area->r_ybot - CIFCurStyle->cs_radius;
    }
    else clip->r_ybot = expanded->r_ybot = area->r_ybot;
    if (area->r_xtop < TiPlaneRect.r_xtop)
    {
      clip->r_xtop = area->r_xtop * CIFCurStyle->cs_scaleFactor;
      expanded->r_xtop = area->r_xtop + CIFCurStyle->cs_radius;
    }
    else clip->r_xtop = expanded->r_xtop = area->r_xtop;
    if (area->r_ytop < TiPlaneRect.r_ytop)
    {
      clip->r_ytop = area->r_ytop * CIFCurStyle->cs_scaleFactor;
      expanded->r_ytop = area->r_ytop + CIFCurStyle->cs_radius;
    }
    else clip->r_ytop = expanded->r_ytop = area->r_ytop;
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFClearPlanes --
 *
 *    This procedure clears out a collection of CIF planes.
 *
 * Results:
 *    None.
 *
 * Side effects:
 *    Each of the planes in "planes" is re-initialized to point to
 *    an empty paint plane.
 *
 * ----------------------------------------------------------------------------
 */

void
CIFClearPlanes(planes)
    Plane **planes;           /* Pointer to an array of MAXCIFLAYERS
                         * planes.
                         */
{
    int i;

    for (i = 0; i < MAXCIFLAYERS; i++)
    {
      if (planes[i] == NULL)
      {
          planes[i] = DBNewPlane((ClientData) TT_SPACE);
      }
      else
      {
          DBClearPaintPlane(planes[i]);
      }
    }
}

Generated by  Doxygen 1.6.0   Back to index