1 /*
2 * mzMain.c --
3 *
4 * Global Data Definitions and interface procedures for the Maze Router.
5 *
6 * OTHER ENTRY POINTS (not in this file):
7 * Technology readin - mzTech.c
8 * Initialization (after tech readin) - mzInit.c
9 * Test command interface - TestCmd.c
10 *
11 * *********************************************************************
12 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the *
13 * * University of California. *
14 * * Permission to use, copy, modify, and distribute this *
15 * * software and its documentation for any purpose and without *
16 * * fee is hereby granted, provided that the above copyright *
17 * * notice appear in all copies. The University of California *
18 * * makes no representations about the suitability of this *
19 * * software for any purpose. It is provided "as is" without *
20 * * express or implied warranty. Export of this software outside *
21 * * of the United States of America may require an export license. *
22 * *********************************************************************
23 */
24
25 #ifndef lint
26 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/mzrouter/mzMain.c,v 1.3 2010/06/24 12:37:19 tim Exp $";
27 #endif /* not lint */
28
29 /*--- includes --- */
30 #include <stdio.h>
31 #include <string.h>
32
33 #include "utils/magic.h"
34 #include "utils/geometry.h"
35 #include "tiles/tile.h"
36 #include "utils/hash.h"
37 #include "database/database.h"
38 #include "drc/drc.h"
39 #include "select/select.h"
40 #include "utils/signals.h"
41 #include "textio/textio.h"
42 #include "windows/windows.h"
43 #include "dbwind/dbwind.h"
44 #include "utils/styles.h"
45 #include "debug/debug.h"
46 #include "utils/undo.h"
47 #include "textio/txcommands.h"
48 #include "utils/malloc.h"
49 #include "utils/main.h"
50 #include "utils/geofast.h"
51 #include "../utils/list.h"
52 #include "utils/heap.h"
53 #include "utils/touchingtypes.h"
54 #include "mzrouter/mzrouter.h"
55 #include "mzrouter/mzInternal.h"
56
57 /*---- Global Data Definitions ----*/
58 /* (Actual storage for static global structures for maze router defined here)*/
59
60 /* Debug flags */
61 ClientData mzDebugID;
62 int mzDebMaze; /* identify flags to debug module */
63 int mzDebStep;
64
65 /* parameter sets - from tech file */
66 MazeStyle *mzStyles = NULL;
67
68 /* Toplevel cell visible to the router */
69 CellUse *mzRouteUse;
70
71 /* Route types */
72 /* (Specifies what types are permitted during routing, and related design
73 * rules.)
74 */
75 RouteType *mzRouteTypes;
76 RouteType *mzActiveRTs; /* Only route types that are turned on */
77 RouteLayer *mzRouteLayers;
78 RouteLayer *mzActiveRLs; /* Only route layers that are turned on */
79 RouteContact *mzRouteContacts;
80
81 /* Routing is confined to this rectangle */
82 Rect mzBoundingRect;
83
84 /* Expansion mask - defines which subcells to treat as expanded */
85 int mzCellExpansionMask;
86
87 /* If reset, degenerate estimation plane used (just 4 tiles - one for each
88 * quadrant with respect to destination point).
89 */
90 int mzEstimate;
91
92 /* If set dest areas are expanded to include all electrically
93 * connected geometry.
94 */
95 int mzExpandEndpoints;
96 /* If set only hints in toplevel cell are recognized */
97 int mzTopHintsOnly;
98
99 /* Maximum distance route will extend into blocked area to connect to dest.
100 * terminal. If set to -1, a max value is computed as a function of the
101 * design rules for the active route types prior to each route.
102 */
103 int mzMaxWalkLength;
104
105 /* if nonnull, limits area of search for performance.
106 * (NOTE: USER MUST LIMIT ROUTE TO THIS AREA WITH FENCES - OTHERWISE
107 * RESULT IS UNPREDICTABLE).
108 */
109 Rect *mzBoundsHint;
110
111 /* how many messages to print */
112 int mzVerbosity;
113 /* if positive, upper bound on number of blooms */
114 int mzBloomLimit;
115
116 /* maskdata unexpanded subcells, marked because they are part of
117 * dest. nodes. */
118 List *mzMarkedCellsList;
119
120 /* start terminals */
121 List *mzStartTerms;
122
123 /* internal cell for dest areas */
124 CellDef *mzDestAreasDef = (CellDef *) NULL;
125 CellUse *mzDestAreasUse = (CellUse *) NULL;
126
127 /* Fence parity */
128 bool mzInsideFence;
129
130 /* largest design rule distance - used during incremental blockage gen. */
131 int mzContextRadius;
132
133 /* Internal cell for completed route */
134 CellDef *mzResultDef = (CellDef *) NULL;
135 CellUse *mzResultUse = (CellUse *) NULL;
136
137 /* HINT PLANES */
138 TileTypeBitMask mzHintTypesMask;
139 Plane *mzHHintPlane;
140 Plane *mzVHintPlane;
141
142 /* FENCE PLANE */
143 TileTypeBitMask mzFenceTypesMask;
144 Plane *mzHFencePlane;
145
146 /* ROTATE PLANES */
147 TileTypeBitMask mzRotateTypesMask;
148 Plane *mzHRotatePlane;
149 Plane *mzVRotatePlane;
150
151 /* BOUNDS PLANES */
152 PaintResultType mzBoundsPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
153 Plane *mzHBoundsPlane;
154 Plane *mzVBoundsPlane;
155
156 /* BLOCKAGE PLANES */
157 TileTypeBitMask mzStartTypesMask;
158 PaintResultType mzBlockPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
159
160 /* ESTIMATE PLANE */
161 PaintResultType mzEstimatePaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES];
162 Plane *mzEstimatePlane;
163
164 /* dest terminal alignment coordinates */
165 NumberLine mzXAlignNL;
166 NumberLine mzYAlignNL;
167
168 /* minimum radius of blockage plane info required around point being expanded.
169 * (Areas twice this size are gened. whenever the minimum is not met.)
170 */
171 int mzBoundsIncrement;
172
173 /* minimum estimated total cost for initial path */
174 dlong mzMinInitialCost;
175
176 /* where current path came from */
177 int mzPathSource;
178
179 /* Parameters controlling search */
180 RouteFloat mzPenalty;
181 dlong mzWRate;
182 dlong mzBloomDeltaCost;
183 dlong mzWWidth;
184
185 /* Statistics */
186 dlong mzInitialEstimate; /* Initial estimated cost of route */
187 int mzNumBlooms;
188 int mzNumOutsideBlooms; /* num blooms from outside window */
189 int mzNumComplete; /* number of complete paths so far */
190 int mzBlockGenCalls; /* # of calls to blockage gen. code */
191 double mzBlockGenArea; /* area over which blockage planes
192 have been gened. */
193 int mzNumPathsGened; /* number of partial paths added to heap */
194 int mzNumPaths; /* number of paths processed */
195 int mzReportInterval; /* frequency that # of paths etc.
196 * is reported. */
197 int mzPathsTilReport; /* counts down to next path report */
198
199 /* Variables controlling search */
200 dlong mzWInitialMinToGo;
201 dlong mzWInitialMaxToGo;
202 dlong mzBloomMaxCost;
203
204 /* Search status */
205 dlong mzWindowMinToGo; /* Window location */
206 dlong mzWindowMaxToGo;
207
208 /* Hash table to avoid repeated expansion from same point during search */
209 HashTable mzPointHash;
210
211 /* Queues for partial paths */
212 Heap mzMaxToGoHeap; /* paths nearer destination than WINDOW */
213 Heap mzMinCostHeap; /* paths in WINDOW */
214 Heap mzMinAdjCostHeap; /* paths farther from dest than WINDOW*/
215 List *mzBloomStack; /* paths in current local focus */
216 List *mzStraightStack; /* focus paths expanded in a straight line */
217 List *mzDownHillStack; /* focus paths expanded as long as
218 * estimated total cost doesn't increase.
219 */
220 List *mzWalkStack; /* paths in walks, i.e. blocks adjacent
221 * to dest areas.
222 */
223 Heap mzMinCostCompleteHeap; /* completed paths */
224
225 /*----------- static data - referenced only in this file ------------------- */
226
227 /* set when storage that needs to be reclaimed has been allocated by router */
228 bool mzDirty = FALSE;
229
230 /* set when path queues and hast table have been allocated */
231 bool mzPathsDirty = FALSE;
232
233 /* macro for adding address pairs to translation table */
234 #define ADDR_TBL_EQUIV(a1,a2) \
235 if(TRUE) \
236 { \
237 HashSetValue(HashFind(&aT, (char *) (a1)), (char *) (a2)); \
238 HashSetValue(HashFind(&aT, (char *) (a2)), (char *) (a1)); \
239 } else
240
241 /* macro for translating address to address paired with it in address table */
242 #define ADDR_TBL(type,a) \
243 if (TRUE) \
244 { \
245 HashEntry *he = HashLookOnly(&aT, (char *) (a)); \
246 if(he) \
247 { \
248 a = (type) HashGetValue(he); \
249 } \
250 } else
251
252
253 /*
254 * ----------------------------------------------------------------------------
255 *
256 * MZCopyParms --
257 *
258 * Allocate and setup duplicate maze parameters with same values.
259 * (Duplicates substructures as well)
260 *
261 * Results:
262 * Pointer to new parameters.
263 *
264 * Side effects:
265 * See above.
266 *
267 * ----------------------------------------------------------------------------
268 */
269
270 MazeParameters *
MZCopyParms(oldParms)271 MZCopyParms(oldParms)
272 MazeParameters *oldParms; /* Maze routing parameters */
273 {
274 MazeParameters *newParms;
275 HashTable aT; /* Address translation hash table */
276
277 /* If passed NULL parms, just return NULL */
278 if(oldParms==NULL)
279 {
280 return NULL;
281 }
282
283 /* Initialize address translation table */
284 HashInit(&aT, 1000, HT_WORDKEYS);
285
286 /* allocate new structure and copy MazeParameters */
287 {
288 newParms = (MazeParameters *) mallocMagic((unsigned)(sizeof(MazeParameters)));
289 *newParms = *oldParms;
290 }
291
292 /* Copy RouteLayers (and sub-structures) */
293 {
294 RouteLayer *rLOld;
295
296 for(rLOld = oldParms->mp_rLayers;
297 rLOld != NULL;
298 rLOld = rLOld->rl_next)
299 {
300 RouteLayer *rLNew;
301
302 /* allocate and equivalence new rL and its rT */
303 {
304 rLNew = (RouteLayer *) mallocMagic((unsigned)(sizeof(RouteLayer)));
305 ADDR_TBL_EQUIV(rLOld, rLNew);
306 ADDR_TBL_EQUIV(&(rLOld->rl_routeType),&(rLNew->rl_routeType));
307 }
308
309 /* copy the rL */
310 *rLNew = *rLOld;
311
312 /* make a copy of the routeLayer contact list */
313 LIST_COPY(rLOld->rl_contactL, rLNew->rl_contactL);
314
315 /* allocate new blockage planes */
316 rLNew->rl_routeType.rt_hBlock = DBNewPlane((ClientData) TT_SPACE);
317 rLNew->rl_routeType.rt_vBlock = DBNewPlane((ClientData) TT_SPACE);
318 }
319 }
320
321 /* Copy RouteContacts (and sub-structures) */
322 {
323 RouteContact *rCOld;
324
325 for(rCOld = oldParms->mp_rContacts;
326 rCOld != NULL;
327 rCOld = rCOld->rc_next)
328 {
329 RouteContact *rCNew;
330
331 /* allocate and equivalence new rC and its rT */
332 {
333 rCNew = (RouteContact *) mallocMagic((unsigned)(sizeof(RouteContact)));
334 ADDR_TBL_EQUIV(rCOld, rCNew);
335 ADDR_TBL_EQUIV(&(rCOld->rc_routeType),&(rCNew->rc_routeType));
336 }
337
338 /* copy the rC */
339 *rCNew = *rCOld;
340
341 rCNew->rc_routeType.rt_hBlock = DBNewPlane((ClientData) TT_SPACE);
342 rCNew->rc_routeType.rt_vBlock = DBNewPlane((ClientData) TT_SPACE);
343 }
344 }
345
346 /* Translate addresses in MazeParameters */
347 ADDR_TBL(RouteLayer *, newParms->mp_rLayers);
348 ADDR_TBL(RouteContact *, newParms->mp_rContacts);
349 ADDR_TBL(RouteType *, newParms->mp_rTypes);
350
351 /* Translate addresses in RouteLayers (and sub-structures) */
352 {
353 RouteLayer *rLOld;
354
355 for(rLOld = oldParms->mp_rLayers;
356 rLOld != NULL;
357 rLOld = rLOld->rl_next)
358 {
359 RouteLayer *rLNew = rLOld;
360 ADDR_TBL(RouteLayer *, rLNew);
361
362 ADDR_TBL(RouteLayer *, rLNew->rl_next);
363 ADDR_TBL(RouteType *, rLNew->rl_routeType.rt_next);
364
365 /* translate RouteContact addresses in contact list */
366 {
367 List *l;
368 for(l = rLNew->rl_contactL; l!=NULL; l=LIST_TAIL(l))
369 {
370 ADDR_TBL(ClientData, LIST_FIRST(l));
371 }
372 }
373
374 }
375 }
376
377 /* Translate addresses in RouteContacts (and sub-structures) */
378 {
379 RouteContact *rCOld;
380
381 for(rCOld = oldParms->mp_rContacts;
382 rCOld != NULL;
383 rCOld = rCOld->rc_next)
384 {
385 RouteContact *rCNew =rCOld;
386 ADDR_TBL(RouteContact *, rCNew);
387
388 ADDR_TBL(RouteLayer *, rCNew->rc_rLayer1);
389 ADDR_TBL(RouteLayer *, rCNew->rc_rLayer2);
390 ADDR_TBL(RouteContact *, rCNew->rc_next);
391 ADDR_TBL(RouteType *, rCNew->rc_routeType.rt_next);
392 }
393 }
394
395 HashKill(&aT);
396 return newParms;
397 }
398
399
400 /*
401 * ----------------------------------------------------------------------------
402 *
403 * MZFindStyle --
404 *
405 * Find style of given name.
406 *
407 * Results:
408 * Pointer to maze parameters for given style, or NULL if not found.
409 *
410 * Side effects:
411 * None.
412 *
413 * ----------------------------------------------------------------------------
414 */
415
416 MazeParameters *
MZFindStyle(name)417 MZFindStyle(name)
418 char *name; /* name of style we are looking for */
419 {
420 MazeStyle *style = mzStyles;
421
422 while(style!=NULL && strcmp(name,style->ms_name)!=0)
423 {
424 style = style->ms_next;
425 }
426
427 if(style==NULL)
428 {
429 return NULL;
430 }
431 else
432 {
433 return &(style->ms_parms);
434 }
435 }
436
437
438 /*
439 * ----------------------------------------------------------------------------
440 *
441 * MZInitRoute --
442 *
443 *
444 * Set up datastructures for maze route, and initialize per/route statistics
445 *
446 * Results:
447 * None.
448 *
449 * Side effects:
450 * See above.
451 *
452 * NOTE: RouteUse supplied as parm to MZInitRoute is toplevel cell visible
453 * to router. However resulting route is painted to current edit cell.
454 *
455 * ----------------------------------------------------------------------------
456 */
457
458 void
MZInitRoute(parms,routeUse,expansionMask)459 MZInitRoute(parms, routeUse, expansionMask)
460 MazeParameters *parms; /* Maze routing parameters */
461 CellUse *routeUse; /* toplevel cell router sees */
462 int expansionMask; /* which subcells are expanded - NOTE: the
463 * maze router interpets a 0 mask to mean
464 * all cells are expanded
465 */
466 {
467 /* Disable undo to avoid overhead on paint operations to internal planes */
468 UndoDisable();
469
470 /* Clean up after last route - if necessary */
471 if(mzDirty)
472 {
473 MZClean();
474 }
475
476 /* Set dirty flag - since we are about to alloc storage for this route */
477 mzDirty = TRUE;
478
479 /* initial source of paths is initialization routine */
480 mzPathSource = SOURCE_INIT;
481
482 /* initial estimated cost is infinity */
483 mzMinInitialCost = COST_MAX;
484
485 /* initialize per-route statistics */
486 mzBlockGenCalls = 0;
487 mzBlockGenArea = 0.0;
488 mzNumComplete = 0;
489 mzNumPathsGened = 0;
490 mzNumPaths = 0;
491 mzNumBlooms = 0;
492 mzNumOutsideBlooms = 0;
493 mzPathsTilReport = mzReportInterval;
494
495 /* Make supplied parms current */
496
497 mzRouteLayers = parms->mp_rLayers;
498 mzRouteContacts = parms->mp_rContacts;
499 mzRouteTypes = parms->mp_rTypes;
500
501 mzPenalty = parms->mp_penalty;
502 mzWWidth = parms->mp_wWidth;
503 mzWRate = parms->mp_wRate;
504 mzBloomDeltaCost = parms->mp_bloomDeltaCost;
505
506 mzBoundsIncrement = parms->mp_boundsIncrement;
507 mzEstimate = parms->mp_estimate;
508 mzExpandEndpoints = parms->mp_expandEndpoints;
509 mzTopHintsOnly = parms->mp_topHintsOnly;
510
511 mzMaxWalkLength = parms->mp_maxWalkLength;
512 mzBoundsHint = parms->mp_boundsHint;
513 mzVerbosity = parms->mp_verbosity;
514 mzBloomLimit = parms->mp_bloomLimit;
515
516 /* Some parms are computed from the supplied ones */
517 mzComputeDerivedParms();
518
519 /* set route cell (toplevel cell visible during routing */
520 mzRouteUse = routeUse;
521
522 /* set expansion mask */
523 mzCellExpansionMask = expansionMask;
524
525 /* Build hint fence and rotate planes */
526 mzBuildHFR(mzRouteUse, &mzBoundingRect);
527
528 /* Initialize Blockage Planes */
529 {
530 RouteType *rT;
531
532 /* Clear bounds planes = regions for which blockage
533 has been generated */
534 DBClearPaintPlane(mzHBoundsPlane);
535 DBClearPaintPlane(mzVBoundsPlane);
536
537 /* Clear blockage planes */
538 for (rT=mzRouteTypes; rT!=NULL; rT=rT->rt_next)
539 {
540 DBClearPaintPlane(rT->rt_hBlock);
541 DBClearPaintPlane(rT->rt_vBlock);
542 }
543 }
544
545 /* Initialize Dest Area Cell */
546 DBCellClearDef(mzDestAreasUse->cu_def);
547 /* take our hold off undo */
548 UndoEnable();
549
550 return;
551 }
552
553 /*
554 * ----------------------------------------------------------------------------
555 *
556 * MZAddStart --
557 *
558 * Add a starting terminal for the maze router.
559 *
560 * Results:
561 * None.
562 *
563 * Side effects:
564 * Builds mzStartTerms list.
565 *
566 * ----------------------------------------------------------------------------
567 */
568
569 void
MZAddStart(point,type)570 MZAddStart(point, type)
571 Point *point;
572 TileType type;
573 {
574 /* Disable undo to avoid overhead on paint operations to internal planes */
575 UndoDisable();
576
577 /* check fence parity */
578 if(mzStartTerms == NULL)
579 {
580 /* This is first start terminal, set fence parity by it, i.e.
581 * whether route is inside or outside of fence
582 */
583 Tile *tFencePlane = TiSrPointNoHint(mzHFencePlane, point);
584 mzInsideFence = (TiGetType(tFencePlane) != TT_SPACE);
585
586 /* If inside fence, clip mzBounds to fence bounding box
587 * to save processing.
588 */
589 if(mzInsideFence)
590 {
591 Rect r;
592
593 DBBoundPlane(mzHFencePlane, &r);
594 r.r_xbot -= 2*mzContextRadius;
595 r.r_ybot -= 2*mzContextRadius;
596 r.r_xtop += 2*mzContextRadius;
597 r.r_ytop += 2*mzContextRadius;
598 GEOCLIP(&mzBoundingRect, &r);
599 }
600 }
601 else
602 {
603 /* not first start terminal, check for consistency with respect
604 * to fence parity.
605 */
606 Tile *tFencePlane = TiSrPointNoHint(mzHFencePlane, point);
607 int newInside = (TiGetType(tFencePlane) != TT_SPACE);
608
609 if(newInside != mzInsideFence)
610 {
611 TxPrintf("Start points on both sides of fence. ");
612 TxPrintf("Arbitrarily choosing those %s fence.\n",
613 (mzInsideFence ? "inside" : "outside"));
614
615 return;
616 }
617 }
618
619 /* Mark tiles connected to start point */
620
621 /* Comment added by Tim 8/5/06 */
622 /* TO DO: If mzExpandEndpoints is FALSE, mzMarkConnectedTiles */
623 /* should still add all tiles immediately under the point to the */
624 /* start list. */
625
626 {
627 Rect rect;
628
629 /* build degenerate rect containing point to initiate the
630 * marking process;
631 */
632 rect.r_ll = *point;
633 rect.r_ur = *point;
634
635 mzMarkConnectedTiles(&rect, type, (mzExpandEndpoints) ?
636 MZ_EXPAND_START : MZ_EXPAND_NONE);
637 }
638
639 /* Take our hold off undo */
640 UndoEnable();
641
642 /* and return */
643 return;
644 }
645
646 /*
647 * ----------------------------------------------------------------------------
648 *
649 * MZAddDest --
650 *
651 * Add a destination terminal.
652 *
653 * Results:
654 * none.
655 *
656 * Side effects:
657 * Paints dest area into mzDestAreasDef.
658 *
659 * Marks mask data tiles connected to supplied dest area (rect and type
660 * passed to this func), also keeps list of marked tiles for cleanup.
661 *
662 * Tiles are marked with TRUE on the clientdata field. The default
663 * clientdata value of CLIENTDEFAULT should be restored by the router
664 * before it returns.
665 *
666 * ----------------------------------------------------------------------------
667 */
668
669 void
MZAddDest(rect,type)670 MZAddDest(rect, type)
671 Rect *rect;
672 TileType type;
673 {
674 ColoredRect *dTerm;
675
676 UndoDisable();
677
678 /* If we're not marking all connected tiles, we need to paint */
679 /* this specific rectangle into the mzDestAreasUse cell. */
680
681 if (!mzExpandEndpoints)
682 {
683 RouteLayer *rL;
684
685 for(rL = mzRouteLayers; rL != NULL; rL = rL->rl_next)
686 {
687 if (rL->rl_routeType.rt_active &&
688 TTMaskHasType(&(DBConnectTbl[type]),
689 rL->rl_routeType.rt_tileType))
690 DBPaint(mzDestAreasUse->cu_def, rect,
691 rL->rl_routeType.rt_tileType);
692 }
693 }
694
695 /* Mark all tiles connected to dest terminal and paint them into */
696 /* the mzDestAreasUse cell. */
697
698 mzMarkConnectedTiles(rect, type,
699 (mzExpandEndpoints) ? MZ_EXPAND_DEST : MZ_EXPAND_NONE);
700
701 UndoEnable();
702 return;
703 }
704
705 /*
706 * ----------------------------------------------------------------------------
707 *
708 * MZRoute --
709 *
710 * Do the route.
711 *
712 * Results:
713 * Zero-width route path. NOTE: route path is allocated from temporary
714 * storage that will be reused for next route.
715 *
716 * Side effects:
717 *
718 *
719 * ----------------------------------------------------------------------------
720 */
721
722 RoutePath *
MZRoute(mzResult)723 MZRoute(mzResult)
724 int *mzResult; /* Place to put result code */
725 {
726 RoutePath *path; /* handle for result of search */
727 ColoredRect *term;
728 List *terms;
729
730 /* Disable undo to avoid overhead on paint operations to internal planes */
731 UndoDisable();
732
733 /* Clear result cell */
734 DBCellClearDef(mzResultDef);
735
736 /* 1st pass over start terminals: */
737 /* paint TT_SAMENODE on each start terminal */
738
739 for(terms = mzStartTerms; terms != NULL; terms = LIST_TAIL(terms))
740 {
741 term = (ColoredRect *) LIST_FIRST(terms);
742 mzPaintBlockType(&term->cr_rect, term->cr_type, &mzBoundingRect,
743 TT_SAMENODE);
744 }
745
746 /* Generate dest areas and walks in blockage planes.
747 * (also adds alignment coords for dest areas to alignment structs.)
748 */
749 mzBuildDestAreaBlocks();
750
751 /* Check that there is an unblocked destination */
752 if (mzXAlignNL.nl_sizeUsed == 2)
753 {
754 /* No alignment marks, so no destination areas */
755 TxPrintf("No reachable destination area!\n");
756 if (mzResult) *mzResult = MZ_UNROUTABLE;
757 goto abort;
758 }
759
760 /* Build Estimate Plane.
761 * (allowing for end points in unexpanded subcells)
762 */
763 mzBuildEstimate();
764 if (SigInterruptPending)
765 {
766 if (mzResult) *mzResult = MZ_INTERRUPTED;
767 goto abort;
768 }
769
770 /* allocating queues and hashtable so set dirty flag */
771 mzPathsDirty = TRUE;
772
773 /*
774 * Initialize queues (actually heaps and lists) for partial paths
775 * Double Precision Integer keys used in cost keyed heaps
776 * to avoid overflow.
777 */
778 HeapInitType(&mzMaxToGoHeap, INITHEAPSIZE, TRUE, FALSE, HE_DLONG);
779 HeapInitType(&mzMinCostHeap, INITHEAPSIZE, FALSE, FALSE, HE_DLONG);
780 HeapInitType(&mzMinAdjCostHeap, INITHEAPSIZE, FALSE, FALSE, HE_DLONG);
781 HeapInitType(&mzMinCostCompleteHeap, INITHEAPSIZE, FALSE, FALSE, HE_DLONG);
782 mzBloomStack = NULL;
783 mzStraightStack = NULL;
784 mzDownHillStack = NULL;
785 mzWalkStack = NULL;
786
787 /*
788 * A hash table is used to hold all points reached,
789 * so we can avoid redundant expansion.
790 */
791 HashInit(&mzPointHash, INITHASHSIZE, HashSize(sizeof (PointKey)));
792
793 /* Build blockage planes at start points and create initial
794 * partial paths
795 */
796
797 /* set bloom threshold to zero, so that initial points are placed
798 * on Max ToGo heap.
799 */
800 mzBloomMaxCost = 0;
801
802 /* 2nd pass over start terminals: generate initial paths */
803 /* for each start point */
804
805 for(terms = mzStartTerms; terms != NULL; terms = LIST_TAIL(terms))
806 {
807 term = (ColoredRect *) LIST_FIRST(terms);
808 mzExtendBlockBounds(&(term->cr_rect.r_ll));
809
810 if (mzStart(term) == FALSE)
811 {
812 if (mzResult) *mzResult = MZ_ALREADY_ROUTED;
813 goto abort;
814 }
815 }
816
817 /* initialize search window */
818 /* estimated total cost is min estimated cost for initial paths */
819
820 mzInitialEstimate = mzMinInitialCost;
821
822 mzWInitialMinToGo = mzInitialEstimate;
823 mzWInitialMaxToGo = mzWInitialMinToGo + mzWWidth;
824
825 /* Make sure we got here without interruption */
826 if (SigInterruptPending) goto abort;
827
828 /* Do the route */
829 path = mzSearch(mzResult);
830 /* On interruption mzSearch returns best complete path
831 * found prior to interruption
832 */
833
834 UndoEnable();
835 return path;
836
837 abort:
838 UndoEnable();
839 return NULL;
840 }
841
842 /*
843 * ----------------------------------------------------------------------------
844 *
845 * MZCleanupPath --
846 *
847 * Given a RoutePath constructed by mzRoute, check for conditions that
848 * result in DRC errors, and correct them. Conditions checked and
849 * the method to fix are as follows:
850 *
851 * 1) contact1->(any)->contact2 where contacts are the same type and
852 * would overlap to produce a non-rectangular area.
853 * FIX: replace second contact with its residues.
854 *
855 * 2) contact1->(any)->contact2 where contacts are the same type and
856 * would be spaced closer than the allowed contact->contact minimum
857 * DRC space.
858 * FIX: fill the area between the two contacts with the contact
859 * residue types.
860 *
861 * 3a) route1-(bend)->route2->contact where length(route2) is less than
862 * the spacing rule type(route2)->type(contact).
863 * FIX: pull route2 segment toward the inside corner of the bend
864 * until the route segment edge aligns with the contact edge.
865 *
866 * 3b) contact->route2-(bend)->route1, the reverse of the above.
867 *
868 *
869 * Results:
870 * None.
871 *
872 * Side effects:
873 * Messes with the path list.
874 *
875 * ----------------------------------------------------------------------------
876 */
877
878 void
MZCleanupPath(pathList)879 MZCleanupPath(pathList)
880 RoutePath *pathList;
881 {
882 RoutePath *path, *n1path, *n2path, *n3path;
883 RoutePath *spath, *cpath, *mpath;
884 RouteType *rT;
885 RouteContact *rC, *rC1, *rC2;
886 TileType ctype, ctype1, ctype2;
887 int pathlength, hdist, vdist, cdist1, cdist2;
888
889
890 /* 1st pass: Consolidate multiple V or H routes */
891 for (path = pathList; path != NULL; path = path->rp_back)
892 {
893 n1path = path->rp_back;
894 while (n1path && (((n1path->rp_orient == 'V') && (path->rp_orient == 'V')) ||
895 ((n1path->rp_orient == 'H') && (path->rp_orient == 'H'))))
896 {
897 /* NOTE: Route paths are allocated by a special procedure; */
898 /* DON'T use freeMagic() on them! */
899 path->rp_back = n1path->rp_back;
900 n1path = path->rp_back;
901 }
902 }
903
904 /* 2nd pass: Look for route paths causing DRC errors */
905 for (path = pathList; path != NULL; path = path->rp_back)
906 {
907 /* Pick up the next two path segments, if they exist */
908 n1path = path->rp_back;
909 n2path = (n1path) ? n1path->rp_back : NULL;
910
911 if (n2path && (n1path->rp_rLayer != n2path->rp_rLayer))
912 {
913 /* Search backward until we reach the next contact */
914 for (spath = n2path->rp_back; spath && spath->rp_back;
915 spath = spath->rp_back)
916 {
917 cpath = spath->rp_back;
918 if (spath->rp_rLayer != cpath->rp_rLayer)
919 {
920 rC1 = MZGetContact(n1path, n2path);
921 rC2 = MZGetContact(spath, cpath);
922 hdist = abs(n1path->rp_entry.p_x - spath->rp_entry.p_x);
923 vdist = abs(n1path->rp_entry.p_y - spath->rp_entry.p_y);
924 ctype1 = rC1->rc_routeType.rt_tileType;
925 ctype2 = rC2->rc_routeType.rt_tileType;
926 cdist1 = rC1->rc_routeType.rt_width;
927 cdist2 = rC2->rc_routeType.rt_width;
928
929 /* To-do: split into cases based on ctype1 vs. ctype2 */
930 if ((cpath->rp_rLayer == n1path->rp_rLayer) &&
931 (hdist < cdist1 && vdist < cdist1) &&
932 (hdist > 0) && (vdist > 0))
933 {
934 /* Case 1 */
935 TxPrintf("Diagnostic: Overlapping contacts (%d:%d) at %d %d\n",
936 hdist, vdist,
937 path->rp_entry.p_x, path->rp_entry.p_y);
938
939 /* Replace orient code of one contact with 'C', */
940 /* to be handled by mzPaintContact */
941
942 if (n1path->rp_extendCode > EC_ALL
943 && n1path->rp_orient != 'C')
944 spath->rp_orient = 'C';
945 else
946 n1path->rp_orient = 'C';
947
948 break;
949 }
950 hdist += rC1->rc_routeType.rt_width;
951 vdist += rC1->rc_routeType.rt_width;
952 cdist1 = rC1->rc_routeType.rt_spacing[ctype1];
953 if (hdist < cdist1 && vdist < cdist1 && hdist > 0 && vdist > 0)
954 {
955 /* Case 2 */
956 TxPrintf("Diagnostic: Contacts too close (%d:%d) at %d %d\n",
957 hdist, vdist,
958 n1path->rp_entry.p_x, n1path->rp_entry.p_y);
959
960 /* Replace orient code of route with 'M' if contacts */
961 /* are the same type, 'N' if they're different. */
962 /* To be handled by MZPaintPath */
963
964 for (mpath = n1path; mpath != spath; mpath = mpath->rp_back)
965 if (mpath->rp_orient != 'O')
966 {
967 if (cpath->rp_rLayer == n1path->rp_rLayer)
968 mpath->rp_orient = 'M';
969 else
970 mpath->rp_orient = 'N';
971 }
972 break;
973 }
974
975 break; /* Stop searching after 1st contact found */
976 }
977 }
978 }
979
980 /* Pick up the following path segment, if it exists */
981 n3path = (n2path) ? n2path->rp_back : NULL;
982
983 /* Cases 3a and 3b */
984 if (n3path != NULL)
985 {
986 /* Cases 3a: route1->route2->contact */
987
988 if (n2path->rp_orient == 'O' &&
989 n1path->rp_orient != 'O' &&
990 path->rp_orient != 'O' &&
991 n1path->rp_orient != path->rp_orient)
992 {
993 rT = &(n1path->rp_rLayer->rl_routeType);
994 rC = MZGetContact(n2path, n3path);
995 ctype = rC->rc_routeType.rt_tileType;
996
997 if (n1path->rp_orient == 'V')
998 {
999 if (n1path->rp_entry.p_y > n2path->rp_entry.p_y)
1000 {
1001 /* Case 3a.1: route down to contact */
1002 pathlength = n1path->rp_entry.p_y - n2path->rp_entry.p_y
1003 - rC->rc_routeType.rt_width;
1004 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1005 {
1006 TxPrintf("Diagnostic: Path needs fix for type "
1007 "3a.1 DRC error at (%d, %d) dist %d\n",
1008 path->rp_entry.p_x, path->rp_entry.p_y,
1009 pathlength);
1010 }
1011 }
1012 else
1013 {
1014 /* Case 3a.2: route up to contact */
1015 pathlength = n2path->rp_entry.p_y - n1path->rp_entry.p_y
1016 - rT->rt_width;
1017 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1018 {
1019 TxPrintf("Diagnostic: Path needs fix for type "
1020 "3a.2 DRC error at (%d, %d) dist %d\n",
1021 path->rp_entry.p_x, path->rp_entry.p_y,
1022 pathlength);
1023 }
1024 }
1025 }
1026 else
1027 {
1028 if (n1path->rp_entry.p_x > n2path->rp_entry.p_x)
1029 {
1030 /* Case 3a.3: route left to contact */
1031 pathlength = n1path->rp_entry.p_x - n2path->rp_entry.p_x
1032 - rC->rc_routeType.rt_width;
1033 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1034 {
1035 TxPrintf("Diagnostic: Path needs fix for type "
1036 "3a.3 DRC error at (%d, %d) dist %d\n",
1037 path->rp_entry.p_x, path->rp_entry.p_y,
1038 pathlength);
1039 }
1040 }
1041 else
1042 {
1043 /* Case 3a.4: route right to contact */
1044 pathlength = n2path->rp_entry.p_x - n1path->rp_entry.p_x
1045 - rT->rt_width;
1046 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1047 {
1048 TxPrintf("Diagnostic: Path needs fix for type "
1049 "3a.4 DRC error at (%d, %d) dist %d\n",
1050 path->rp_entry.p_x, path->rp_entry.p_y,
1051 pathlength);
1052 }
1053 }
1054 }
1055 }
1056
1057 /* Cases 3b: contact->route1->route2 */
1058
1059 if (n1path->rp_orient == 'O' &&
1060 n2path->rp_orient != 'O' &&
1061 n3path->rp_orient != 'O' &&
1062 n2path->rp_orient != n3path->rp_orient)
1063 {
1064 rT = &(n2path->rp_rLayer->rl_routeType);
1065 rC = MZGetContact(n1path, path);
1066 ctype = rC->rc_routeType.rt_tileType;
1067
1068 if (n2path->rp_orient == 'V')
1069 {
1070 if (n2path->rp_entry.p_y > n1path->rp_entry.p_y)
1071 {
1072 /* Case 3b.1: route down from contact */
1073 pathlength = n2path->rp_entry.p_y - n1path->rp_entry.p_y
1074 - rC->rc_routeType.rt_width;
1075 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1076 {
1077 TxPrintf("Diagnostic: Path needs fix for type "
1078 "3b.1 DRC error at (%d, %d) dist %d\n",
1079 path->rp_entry.p_x, path->rp_entry.p_y,
1080 pathlength);
1081 }
1082 }
1083 else
1084 {
1085 /* Case 3b.2: route up from contact */
1086 pathlength = n1path->rp_entry.p_y - n2path->rp_entry.p_y
1087 - rT->rt_width;
1088 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1089 {
1090 TxPrintf("Diagnostic: Path needs fix for type "
1091 "3b.2 DRC error at (%d, %d) dist %d\n",
1092 path->rp_entry.p_x, path->rp_entry.p_y,
1093 pathlength);
1094 }
1095 }
1096 }
1097 else
1098 {
1099 if (n2path->rp_entry.p_x > n1path->rp_entry.p_x)
1100 {
1101 /* Case 3b.3: route left from contact */
1102 pathlength = n2path->rp_entry.p_x - n1path->rp_entry.p_x
1103 - rC->rc_routeType.rt_width;
1104 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1105 {
1106 TxPrintf("Diagnostic: Path needs fix for type "
1107 "3b.3 DRC error at (%d, %d) dist %d\n",
1108 path->rp_entry.p_x, path->rp_entry.p_y,
1109 pathlength);
1110 }
1111 }
1112 else
1113 {
1114 /* Case 3b.4: route right from contact */
1115 pathlength = n1path->rp_entry.p_x - n2path->rp_entry.p_x
1116 - rT->rt_width;
1117 if (pathlength > 0 && pathlength < rT->rt_bloatTop[ctype])
1118 {
1119 TxPrintf("Diagnostic: Path needs fix for type "
1120 "3b.4 DRC error at (%d, %d) dist %d\n",
1121 path->rp_entry.p_x, path->rp_entry.p_y,
1122 pathlength);
1123 }
1124 }
1125 }
1126 }
1127 }
1128 }
1129 }
1130
1131
1132 /*
1133 * ----------------------------------------------------------------------------
1134 *
1135 * MZPaintPath --
1136 *
1137 * Given a RoutePath constructed by mzRoute, convert it to paint.
1138 * The input RoutePath specifies a sequence of points completely, so
1139 * each leg can be painted as we go.
1140 *
1141 * Results:
1142 * Pointer to result cell containing painted path.
1143 *
1144 * Side effects:
1145 * Paints into result cell.
1146 *
1147 * ----------------------------------------------------------------------------
1148 */
1149
1150 CellUse *
MZPaintPath(pathList)1151 MZPaintPath(pathList)
1152 RoutePath *pathList;
1153 {
1154 RoutePath *path, *prev;
1155 RouteLayer *last_rL = NULL;
1156 int cwidth = 0;
1157
1158 /*
1159 * First, check the path for common problems causing DRC errors
1160 */
1161 MZCleanupPath(pathList);
1162
1163 /*
1164 * Each segment of the path contains no bends, so is
1165 * either horizontal, vertical, or a contact.
1166 */
1167 for (path = pathList;
1168 (prev = path->rp_back)!= NULL && !SigInterruptPending;
1169 path = prev)
1170 {
1171 RouteLayer *rL;
1172 Rect r;
1173 int t;
1174
1175 /*
1176 * Special handling for a contact if different planes.
1177 * In this case, no x- or y- motion is allowed.
1178 */
1179 if (path->rp_rLayer != prev->rp_rLayer)
1180 {
1181 ASSERT(path->rp_entry.p_x == prev->rp_entry.p_x, "MZPaintPath");
1182 ASSERT(path->rp_entry.p_y == prev->rp_entry.p_y, "MZPaintPath");
1183 cwidth = mzPaintContact(path, prev);
1184 last_rL = path->rp_rLayer;
1185 continue;
1186 }
1187
1188 /*
1189 * Leg on the same plane.
1190 * Generate a box between the start and end points
1191 * with the width specified for this layer.
1192 * Flip the rectangle as necessary to ensure that
1193 * LL <= UR.
1194 */
1195 r.r_ll = path->rp_entry;
1196 r.r_ur = prev->rp_entry;
1197 if (r.r_xbot > r.r_xtop)
1198 t = r.r_xbot, r.r_xbot = r.r_xtop, r.r_xtop = t;
1199 if (r.r_ybot > r.r_ytop)
1200 t = r.r_ybot, r.r_ybot = r.r_ytop, r.r_ytop = t;
1201 if (path->rp_orient == 'M' || path->rp_orient == 'N')
1202 {
1203 r.r_xtop += cwidth;
1204 r.r_ytop += cwidth;
1205 }
1206 else
1207 {
1208 r.r_xtop += path->rp_rLayer->rl_routeType.rt_width;
1209 r.r_ytop += path->rp_rLayer->rl_routeType.rt_width;
1210 }
1211
1212 rL = path->rp_rLayer;
1213 DBPaintPlane(mzResultDef->cd_planes[rL->rl_planeNum], &r,
1214 DBStdPaintTbl(rL->rl_routeType.rt_tileType,
1215 rL->rl_planeNum), (PaintUndoInfo *) NULL);
1216
1217 /* Routes between close contacts of the same type should paint */
1218 /* both residue types. */
1219
1220 if ((path->rp_orient == 'M') && (last_rL != NULL))
1221 {
1222 DBPaintPlane(mzResultDef->cd_planes[last_rL->rl_planeNum], &r,
1223 DBStdPaintTbl(last_rL->rl_routeType.rt_tileType,
1224 last_rL->rl_planeNum), (PaintUndoInfo *) NULL);
1225 }
1226 }
1227
1228 /* Update bounding box of result cell */
1229 DBReComputeBbox(mzResultDef);
1230
1231 /* return pointer to result cell use */
1232 return mzResultUse;
1233
1234 }
1235
1236
1237 /*
1238 * ----------------------------------------------------------------------------
1239 *
1240 * MZClean --
1241 *
1242 * Reclaim storage space gobbled up during route, and reset tile client
1243 * fields. After a MZInitRoute() has been issued, MZClean() should always
1244 * be called prior to returning from Magic command.
1245 *
1246 * Results:
1247 * None
1248 *
1249 * Side effects:
1250 * See above.
1251 *
1252 * ----------------------------------------------------------------------------
1253 */
1254
1255 void
MZClean()1256 MZClean()
1257 {
1258 if(mzDirty)
1259 {
1260 /* clear estimate plane */
1261 mzCleanEstimate();
1262
1263 /* Reclaim storage and reset mzStartList */
1264 {
1265 ListDeallocC(mzStartTerms);
1266 mzStartTerms = NULL;
1267 }
1268
1269 /* Reset dest alignment structures */
1270 mzNLClear(&mzXAlignNL);
1271 mzNLClear(&mzYAlignNL);
1272
1273 /* Unmark marked tiles, and cells and dealloc marked lists */
1274 {
1275 List *l;
1276
1277 /* Reset Marked subcell client fields to CLIENTDEFAULT */
1278 for(l=mzMarkedCellsList; l!=NULL; l=LIST_TAIL(l))
1279 {
1280 CellUse *cu = (CellUse *) LIST_FIRST(l);
1281
1282 /* Restore celluse client field to its "unmarked" value */
1283 cu->cu_client = (ClientData) CLIENTDEFAULT;
1284 }
1285
1286 /* Dealloc list of marked cells */
1287 ListDealloc(mzMarkedCellsList);
1288 mzMarkedCellsList = NULL;
1289 }
1290
1291 /* Free up route-path queues */
1292 if(mzPathsDirty)
1293 {
1294 HeapKill(&mzMaxToGoHeap, (void (*)()) NULL);
1295 HeapKill(&mzMinCostHeap, (void (*)()) NULL);
1296 HeapKill(&mzMinAdjCostHeap, (void (*)()) NULL);
1297 HeapKill(&mzMinCostCompleteHeap, (void (*)()) NULL);
1298 ListDealloc(mzBloomStack);
1299 ListDealloc(mzStraightStack);
1300 ListDealloc(mzDownHillStack);
1301 ListDealloc(mzWalkStack);
1302
1303 /* Free up hash table */
1304 HashKill(&mzPointHash);
1305
1306 /* Reclaims route path entries */
1307 mzFreeAllRPaths();
1308
1309 /* reset flag */
1310 mzPathsDirty = FALSE;
1311 }
1312
1313 /* reset flag */
1314 mzDirty = FALSE;
1315 }
1316
1317 return;
1318 }
1319