1 /*
2 * ExtInteraction.c --
3 *
4 * Circuit extraction.
5 * Finds interaction areas.
6 *
7 * *********************************************************************
8 * * Copyright (C) 1985, 1990 Regents of the University of California. *
9 * * Permission to use, copy, modify, and distribute this *
10 * * software and its documentation for any purpose and without *
11 * * fee is hereby granted, provided that the above copyright *
12 * * notice appear in all copies. The University of California *
13 * * makes no representations about the suitability of this *
14 * * software for any purpose. It is provided "as is" without *
15 * * express or implied warranty. Export of this software outside *
16 * * of the United States of America may require an export license. *
17 * *********************************************************************
18 */
19
20 #ifndef lint
21 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/extract/ExtInter.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
22 #endif /* not lint */
23
24 #include <stdio.h>
25
26 #include "utils/magic.h"
27 #include "utils/geometry.h"
28 #include "utils/geofast.h"
29 #include "utils/undo.h"
30 #include "tiles/tile.h"
31 #include "utils/hash.h"
32 #include "database/database.h"
33 #include "utils/malloc.h"
34 #include "textio/textio.h"
35 #include "debug/debug.h"
36 #include "extract/extract.h"
37 #include "extract/extractInt.h"
38 #include "utils/signals.h"
39 #include "utils/styles.h"
40
41 /* Local data */
42 CellUse *extInterUse = (CellUse *) NULL; /* Subtree being processed */
43 Plane *extInterPlane; /* Paint into this plane */
44 int extInterHalo; /* Elements closer than this
45 * constitute an interaction.
46 */
47 int extInterBloat; /* Bloat by this much when
48 * painting into result plane.
49 */
50
51 /* Forward declarations */
52 int extInterOverlapSubtree();
53 int extInterOverlapTile();
54 int extInterSubtree();
55 int extInterSubtreeClip();
56 int extInterSubtreeElement();
57 int extInterSubtreeTile();
58 int extInterSubtreePaint();
59
60 #define BLOATBY(r, h) ( (r)->r_xbot -= (h), (r)->r_ybot -= (h), \
61 (r)->r_xtop += (h), (r)->r_ytop += (h) )
62
63 /*
64 * ----------------------------------------------------------------------------
65 *
66 * ExtFindInteractions --
67 *
68 * Paint into the supplied tile plane 'resultPlane' TT_ERROR_P tiles
69 * for each area in the CellDef 'def' that must be processed for
70 * interactions.
71 *
72 * Each interaction arises from paint in two different subtrees
73 * being less than (but not equal to) 'halo' units away from
74 * each other. In this definition, a subtree refers to a single
75 * CellUse, which may be either a single cell or an entire array.
76 *
77 * If 'bloat' is non-zero, each interaction area is bloated by
78 * this amount when being painted into the result plane.
79 *
80 * Results:
81 * None.
82 *
83 * Side effects:
84 * Paints into the plane 'resultPlane'.
85 *
86 * ----------------------------------------------------------------------------
87 */
88
89 void
ExtFindInteractions(def,halo,bloatby,resultPlane)90 ExtFindInteractions(def, halo, bloatby, resultPlane)
91 CellDef *def; /* Find interactions among children of def */
92 int halo; /* Interaction is elements closer than halo */
93 int bloatby; /* Bloat each interaction area by this amount when
94 * painting into resultPlane.
95 */
96 Plane *resultPlane; /* Paint interaction areas into this plane */
97 {
98 SearchContext scx;
99
100 UndoDisable();
101 extInterPlane = resultPlane;
102 extInterHalo = halo;
103 extInterBloat = bloatby;
104 extParentUse->cu_def = def;
105 scx.scx_use = extParentUse;
106 scx.scx_trans = GeoIdentityTransform;
107 scx.scx_area = def->cd_bbox;
108
109 /*
110 * Process each child subtree.
111 * This involves comparing all the paint in the subtree
112 * with all the paint in all other subtrees up to, but
113 * not including, the subtree under consideration.
114 */
115 extInterUse = (CellUse *) NULL;
116 (void) DBCellSrArea(&scx, extInterSubtree, (ClientData) NULL);
117
118 /*
119 * Process parent paint if there were any subcells.
120 * We compare each paint rectangle with all the paint in
121 * all the subtrees, to see if there is an overlap.
122 */
123 if (extInterUse)
124 {
125 extInterUse = (CellUse *) NULL;
126 (void) DBCellSrArea(&scx, extInterSubtreePaint, (ClientData) def);
127 }
128 UndoEnable();
129 }
130
131 int
extInterSubtreePaint(scx,def)132 extInterSubtreePaint(scx, def)
133 SearchContext *scx;
134 CellDef *def;
135 {
136 Rect r;
137 int pNum;
138
139 r = scx->scx_use->cu_bbox;
140 BLOATBY(&r, extInterHalo);
141 for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
142 (void) DBSrPaintArea((Tile *) NULL, def->cd_planes[pNum], &r,
143 &DBAllButSpaceAndDRCBits, extInterSubtreeTile, (ClientData) NULL);
144
145 return (2);
146 }
147
148 /*
149 * ----------------------------------------------------------------------------
150 *
151 * extInterSubtree --
152 *
153 * Called for each immediate child use of the cell being processed
154 * for interactions. Our job is to process all the paint in this
155 * use against all other subtrees overlapping this one.
156 *
157 * Results:
158 * Returns 2 to abort after the first array element.
159 *
160 * Side effects:
161 * Sets extInterUse to scx->scx_use.
162 * Children may paint into extInterPlane.
163 *
164 * ----------------------------------------------------------------------------
165 */
166
167 int
extInterSubtree(scx)168 extInterSubtree(scx)
169 SearchContext *scx;
170 {
171 CellUse *oldUse = extInterUse;
172 SearchContext parentScx;
173
174 extInterUse = scx->scx_use;
175 if (oldUse)
176 {
177 /* Find all other subtrees overlapping this cell */
178 parentScx.scx_area = scx->scx_use->cu_bbox;
179 BLOATBY(&parentScx.scx_area, extInterHalo);
180 parentScx.scx_trans = GeoIdentityTransform;
181 parentScx.scx_use = extParentUse;
182 (void) DBCellSrArea(&parentScx, extInterSubtreeClip, (ClientData) scx);
183 }
184 return (2);
185 }
186
187 int
extInterSubtreeClip(overlapScx,scx)188 extInterSubtreeClip(overlapScx, scx)
189 SearchContext *overlapScx, *scx;
190 {
191 Rect r, r2;
192
193 /* Only search as far as extInterUse */
194 if (overlapScx->scx_use == extInterUse)
195 return (2);
196
197 /*
198 * Only process the overlap between overlapScx and scx,
199 * bloating both by extInterHalo.
200 */
201 r = overlapScx->scx_use->cu_bbox;
202 BLOATBY(&r, extInterHalo);
203 r2 = scx->scx_use->cu_bbox;
204 BLOATBY(&r2, extInterHalo);
205 GEOCLIP(&r, &r2);
206
207 (void) DBArraySr(scx->scx_use, &r, extInterSubtreeElement,
208 (ClientData) &r);
209 return (2);
210 }
211
212 /*
213 * ----------------------------------------------------------------------------
214 *
215 * extInterSubtreeElement --
216 *
217 * Called for each element in the array forming the use passed to
218 * extInterSubtree(). See extInterSubtree() for comments.
219 *
220 * Results:
221 * Returns 0 always.
222 *
223 * Side effects:
224 * See ExtFindInteractions.
225 *
226 * ----------------------------------------------------------------------------
227 */
228
229 int
extInterSubtreeElement(use,trans,x,y,r)230 extInterSubtreeElement(use, trans, x, y, r)
231 CellUse *use;
232 Transform *trans;
233 int x, y;
234 Rect *r;
235 {
236 SearchContext scx;
237 Transform tinv;
238
239 scx.scx_use = use;
240 scx.scx_trans = *trans;
241 scx.scx_x = x;
242 scx.scx_y = y;
243 GEOINVERTTRANS(trans, &tinv);
244 GEOTRANSRECT(&tinv, r, &scx.scx_area);
245 (void) DBTreeSrTiles(&scx, &DBAllButSpaceAndDRCBits, 0,
246 extInterSubtreeTile, (ClientData) NULL);
247 return (0);
248 }
249
250 /*
251 * ----------------------------------------------------------------------------
252 *
253 * extInterSubtreeTile --
254 *
255 * Called for each tile in the subtree being processed by
256 * extInterSubtree(). Transform this tile to root coordinates,
257 * bloating by extInterHalo, and then call extInterOverlapSubtree
258 * to process all the other subtrees for paint overlapping
259 * this bloated area. If the argument 'cxp' is non-NULL, we
260 * use cxp->tc_scx->scx_trans to transform the area of tile to
261 * root coordinates; otherwise, we don't transform it at all.
262 *
263 * Results:
264 * Returns 0 always.
265 *
266 * Side effects:
267 * See extInterOverlapTile.
268 *
269 * ----------------------------------------------------------------------------
270 */
271
272 int
extInterSubtreeTile(tile,cxp)273 extInterSubtreeTile(tile, cxp)
274 Tile *tile;
275 TreeContext *cxp;
276 {
277 SearchContext newscx;
278 Rect r;
279
280 TITORECT(tile, &r);
281 BLOATBY(&r, extInterHalo);
282 if (cxp)
283 {
284 GEOTRANSRECT(&cxp->tc_scx->scx_trans, &r, &newscx.scx_area);
285 }
286 else newscx.scx_area = r;
287 newscx.scx_trans = GeoIdentityTransform;
288 newscx.scx_use = extParentUse;
289 (void) DBCellSrArea(&newscx, extInterOverlapSubtree, (ClientData) NULL);
290 return (0);
291 }
292
293 /*
294 * ----------------------------------------------------------------------------
295 *
296 * extInterOverlapSubtree --
297 *
298 * Called for each subcell of the root that overlaps the piece
299 * of paint found by extInterSubtreeTile() above. We stop
300 * as soon as we see extInterUse; otherwise, search all the
301 * cells in the subtree rooted at scx->scx_use for paint
302 * overlapping scx->scx_area.
303 *
304 * Results:
305 * Returns 2 if we see extInterUse; otherwise, returns 0.
306 *
307 * Side effects:
308 * Paints into the plane 'resultPlane'; see extInterOverlapTile.
309 *
310 * ----------------------------------------------------------------------------
311 */
312
313 int
extInterOverlapSubtree(scx)314 extInterOverlapSubtree(scx)
315 SearchContext *scx;
316 {
317 if (extInterUse == scx->scx_use)
318 return (2);
319
320 (void) extTreeSrPaintArea(scx, extInterOverlapTile, (ClientData) NULL);
321 return (0);
322 }
323
324 /*
325 * ----------------------------------------------------------------------------
326 *
327 * extInterOverlapTile --
328 *
329 * Called for each piece of paint overlapping the piece found
330 * by extInterSubtreeTile(). Bloat the found piece by extInterHalo,
331 * then clip to the area of the overlapping piece of paint in root
332 * coordinates. If the result is non-empty, paint it into the
333 * plane extInterPlane.
334 *
335 * Results:
336 * Returns 0 always.
337 *
338 * Side effects:
339 * Paints into the plane 'resultPlane'.
340 *
341 * ----------------------------------------------------------------------------
342 */
343
344 int
extInterOverlapTile(tile,cxp)345 extInterOverlapTile(tile, cxp)
346 Tile *tile;
347 TreeContext *cxp;
348 {
349 SearchContext *scx = cxp->tc_scx;
350 Rect r, rootr;
351
352 TITORECT(tile, &r);
353 BLOATBY(&r, extInterHalo);
354 GEOCLIP(&r, &scx->scx_area);
355 if (GEO_RECTNULL(&r))
356 return (0);
357
358 GEOTRANSRECT(&scx->scx_trans, &r, &rootr);
359 BLOATBY(&rootr, extInterBloat);
360 DBPaintPlane(extInterPlane, &rootr, DBStdWriteTbl(TT_ERROR_P),
361 (PaintUndoInfo *) NULL);
362
363 return (0);
364 }
365
366 /*
367 *-----------------------------------------------------------------------------
368 *
369 * extTreeSrPaintArea --
370 *
371 * Recursively search downward from the supplied CellUse for
372 * all paint tiles.
373 *
374 * The procedure should be of the following form:
375 *
376 * int
377 * func(tile, scx, cdata)
378 * Tile *tile;
379 * SearchContext *scx;
380 * ClientData cdata;
381 * {
382 * }
383 *
384 * The SearchContext is stored in cxp->tc_scx, and the user's arg is stored
385 * in cxp->tc_filter->tf_arg.
386 *
387 * In the above, the scx transform is the net transform from the coordinates
388 * of tile to "world" coordinates (or whatever coordinates the initial
389 * transform supplied to extTreeSrTiles was a transform to). Func returns
390 * 0 under normal conditions. If 1 is returned, it is a request to
391 * abort the search.
392 *
393 * *** WARNING ***
394 *
395 * The client procedure should not modify any of the paint planes in
396 * the cells visited by extTreeSrTiles, because we use DBSrPaintArea
397 * as our paint-tile enumeration function.
398 *
399 * Results:
400 * 0 is returned if the search finished normally. 1 is returned
401 * if the search was aborted.
402 *
403 * Side effects:
404 * Whatever side effects are brought about by applying the
405 * procedure supplied.
406 *
407 *-----------------------------------------------------------------------------
408 */
409
410 int
extTreeSrPaintArea(scx,func,cdarg)411 extTreeSrPaintArea(scx, func, cdarg)
412 SearchContext *scx; /* Pointer to search context specifying
413 * a cell use to search, an area in the
414 * coordinates of the cell's def, and a
415 * transform back to "root" coordinates.
416 */
417 int (*func)(); /* Function to apply at each qualifying tile */
418 ClientData cdarg; /* Client data for above function */
419 {
420 int extTreeSrFunc();
421 CellDef *def = scx->scx_use->cu_def;
422 TreeContext context;
423 TreeFilter filter;
424 int pNum;
425
426 if ((def->cd_flags & CDAVAILABLE) == 0)
427 {
428 bool dereference = (def->cd_flags & CDDEREFERENCE) ? TRUE : FALSE;
429 if (!DBCellRead(def, (char *) NULL, TRUE, dereference, NULL)) return 0;
430 }
431
432 filter.tf_func = func;
433 filter.tf_arg = cdarg;
434 context.tc_scx = scx;
435 context.tc_filter = &filter;
436
437 /*
438 * Apply the function first to any of the tiles in the planes
439 * for this CellUse's CellDef that match the mask.
440 */
441 for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
442 if (DBSrPaintArea((Tile *) NULL, def->cd_planes[pNum],
443 &scx->scx_area, &DBAllButSpaceAndDRCBits, func,
444 (ClientData) &context))
445 return (1);
446
447 /* Visit our children recursively */
448 return (DBCellSrArea(scx, extTreeSrFunc, (ClientData) &filter));
449 }
450
451 /*
452 * extTreeSrFunc --
453 *
454 * Filter procedure applied to subcells by extTreeSrPaintArea().
455 */
456
457 int
extTreeSrFunc(scx,fp)458 extTreeSrFunc(scx, fp)
459 SearchContext *scx;
460 TreeFilter *fp;
461 {
462 CellDef *def = scx->scx_use->cu_def;
463 TreeContext context;
464 int pNum;
465
466 if ((def->cd_flags & CDAVAILABLE) == 0)
467 {
468 bool dereference = (def->cd_flags & CDDEREFERENCE) ? TRUE : FALSE;
469 if (!DBCellRead(def, (char *) NULL, TRUE, dereference, NULL)) return (0);
470 }
471
472 context.tc_scx = scx;
473 context.tc_filter = fp;
474
475 /*
476 * Apply the function first to any of the tiles in the planes
477 * for this CellUse's CellDef that match the mask.
478 */
479 for (pNum = PL_TECHDEPBASE; pNum < DBNumPlanes; pNum++)
480 if (DBSrPaintArea((Tile *) NULL, def->cd_planes[pNum],
481 &scx->scx_area, &DBAllButSpaceAndDRCBits,
482 fp->tf_func, (ClientData) &context))
483 return (1);
484
485 /* Visit our children recursively */
486 return (DBCellSrArea(scx, extTreeSrFunc, (ClientData) fp));
487 }
488
489