1 /* 2 * mzInternal.h -- 3 * 4 * This file defines data structures, variables, and constants internal to 5 * the maze router module. 6 * 7 * 8 * 9 * ********************************************************************* 10 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the * 11 * * University of California. * 12 * * Permission to use, copy, modify, and distribute this * 13 * * software and its documentation for any purpose and without * 14 * * fee is hereby granted, provided that the above copyright * 15 * * notice appear in all copies. The University of California * 16 * * makes no representations about the suitability of this * 17 * * software for any purpose. It is provided "as is" without * 18 * * express or implied warranty. Export of this software outside * 19 * * of the United States of America may require an export license. * 20 * ********************************************************************* 21 * 22 * 23 * rcsid $Header: /usr/cvsroot/magic-8.0/mzrouter/mzInternal.h,v 1.2 2008/06/01 18:37:44 tim Exp $ 24 */ 25 26 #ifndef _MZINTERNAL_H 27 #define _MZINTERNAL_H 28 29 /* 30 * Structures etc. that are exported by the mzrouter are defined in 31 * mzrouter.h. 32 * 33 * Structures (etc.) defined here are shared between files in this module. 34 * 35 * Structures local to a given source 36 * file are defined at the top of that source file. 37 * 38 * Structures specific to a given function are defined at 39 * the head of that function. 40 */ 41 42 #ifndef _MZROUTER_H 43 #include "mzrouter/mzrouter.h" 44 #endif 45 46 #ifndef _HEAP_H 47 #include "utils/heap.h" 48 #endif 49 50 /* ------------------------ Version String --------------------------- */ 51 #define MZROUTER_VERSION "0.6" 52 53 /* ------------------------ Debugging flags ----------------------------- */ 54 extern ClientData mzDebugID; 55 #include "mzDebug.h" 56 57 /* ---------- Default Parameter Values ----------------------------------- */ 58 59 /* Penalty factor applied to cost estimate in excess of max window bound 60 * represented as mantissa / 2**nExponent 61 */ 62 /* (2048/2**1 = 1028) */ 63 #define DEF_PENALTY_MANTISSA 2048 64 #define DEF_PENALTY_NEXPONENT 1 65 66 /* Window rate in cost/bloom */ 67 #define DEF_WINDOW_RATE 500 68 69 /* Window width in cost */ 70 #define DEF_WINDOW_WIDTH 10000 71 72 /* Maximum cost increase allowed during blooming */ 73 #define DEF_BLOOM_DELTA_COST 1 74 75 /* minimum radius of blockage plane info required around point being expanded. 76 * value of -1 causes mzrouter to compute its own best guess. 77 * (Areas twice this size are gened. whenever the minimum is not met.) 78 */ 79 #define DEF_BOUNDS_INCREMENT -1 80 81 /* If reset, degenerate estimation plane used (just 4 tiles - one for each 82 * quadrant with respect to destination point). 83 */ 84 #define DEF_ESTIMATE 1 85 /* If set, routes may start or terminate at any geometry that is 86 * electrically connected to specified start or dest regions. 87 */ 88 #define DEF_EXPAND_ENDPOINTS 1 89 #define MZ_EXPAND_START 1 /* ClientData type for start tiles */ 90 #define MZ_EXPAND_DEST 0 /* ClientData type for dest tiles */ 91 #define MZ_EXPAND_NONE CLIENTDEFAULT /* Normal ClientData type */ 92 93 /* If set only hints in toplevel cell are recognized - speeds up processing 94 * of hint planes when there are lots of expanded subcells. 95 */ 96 #define DEF_TOP_HINTS_ONLY 0 97 /* Maximum distance route can penetrate blocked areas to reach destination. 98 * Note only "same node" blockage will be penetrated, i.e. blocks steming from 99 * spacing to unrelated nodes are always honored. 100 * 101 * A value of -1 causes the max penetration to be recomputed prior to each 102 * route based on the design rules for the active routetypes. 103 */ 104 #define DEF_MAX_WALK_LENGTH -1 105 /* controls message printing: 0 = errors and warnings only, 1 = brief, 2 = 106 * lots of statistics. 107 */ 108 #define DEF_VERBOSITY 1 109 /* if positive, puts upper limit on number of blooms during search. 110 * After limit is reached routing is terminated and best complete route 111 * to date is returned. 112 */ 113 #define DEF_BLOOM_LIMIT 0 114 115 /* This struc used to make list of named parameter sets for maze routing. 116 * Only the MazeParameters themselves are passed to the routines 117 * in this module. 118 */ 119 typedef struct mazestyle 120 { 121 char *ms_name; /* name of style */ 122 List *ms_spacingL; /* used to store spacing during tech readin. */ 123 MazeParameters ms_parms; /* parameter settings for this style */ 124 struct mazestyle *ms_next; 125 } MazeStyle; 126 127 128 /* ----- TileTypes, Paint Tables, and Paint Planes, and Internal Cells ---- */ 129 /* RESULT CELL */ 130 extern CellDef *mzResultDef; 131 extern CellUse *mzResultUse; 132 133 /* Types are offset to coincide with hint types. 134 * This facilitates display for debugging. 135 */ 136 #define TT_OFF (TT_MAGNET - 1) 137 138 /* BLOCKAGE PLANES - AND CELL FOR DISPLAY */ 139 /* Higher numbered blockage types ALWAYS take priority during painting */ 140 141 /* Start or destination terminal */ 142 #define TT_SAMENODE (1 + TT_OFF) 143 /* Block due to start or destination terminal */ 144 #define TT_SAMENODE_BLOCK (2 + TT_OFF) 145 /* Can reach dest via contact */ 146 #define TT_ABOVE_UD_WALK (3 + TT_OFF) 147 #define TT_BELOW_UD_WALK (4 + TT_OFF) 148 #define TT_ABOVE_LR_WALK (5 + TT_OFF) 149 #define TT_BELOW_LR_WALK (6 + TT_OFF) 150 /* Approach to dest area */ 151 #define TT_LEFT_WALK (7 + TT_OFF) 152 #define TT_RIGHT_WALK (8 + TT_OFF) 153 #define TT_TOP_WALK (9 + TT_OFF) 154 #define TT_BOTTOM_WALK (10 + TT_OFF) 155 /* route destination area */ 156 #define TT_DEST_AREA (11 + TT_OFF) 157 /* Can't route in this space */ 158 #define TT_BLOCKED (12 + TT_OFF) 159 160 #define TT_MAXROUTETYPES (1 + TT_BLOCKED) 161 162 extern PaintResultType mzBlockPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES]; 163 extern CellDef *mzBlockDef ; 164 165 /* BOUNDS PLANE */ 166 /* Blockage planes generated here */ 167 #define TT_INBOUNDS (1 + TT_OFF) 168 #define TT_GENBLOCK (2 + TT_OFF) 169 extern PaintResultType mzBoundsPaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES]; 170 extern Plane *mzHBoundsPlane; 171 extern Plane *mzVBoundsPlane; 172 173 /* ESTIMATION PLANE */ 174 #define TT_EST_SUBCELL (1 + TT_OFF) 175 #define TT_EST_FENCE (2 + TT_OFF) 176 #define TT_EST_DEST (3 + TT_OFF) 177 extern PaintResultType mzEstimatePaintTbl[TT_MAXROUTETYPES][TT_MAXROUTETYPES]; 178 extern Plane *mzEstimatePlane; 179 180 /* HINT TYPES */ 181 extern TileTypeBitMask mzHintTypesMask; /* map of hint, fence 182 and rotate types */ 183 extern TileTypeBitMask mzStartTypesMask; /* mask of valid types for a route start */ 184 185 /* HINT (magnet) PLANES */ 186 extern Plane *mzHHintPlane; 187 extern Plane *mzVHintPlane; 188 189 /* FENCE PLANE */ 190 extern Plane *mzHFencePlane; 191 192 /* ROTATE PLANES */ 193 extern Plane *mzHRotatePlane; 194 extern Plane *mzVRotatePlane; 195 196 /* Number Lines - used to mark points aligned with dest tile corners */ 197 typedef struct numberLine 198 { 199 int nl_sizeAlloced; /* Number of entries allocated */ 200 int nl_sizeUsed; 201 int *nl_entries; 202 } NumberLine; 203 204 /* 205 * Macros for allocating segments of a RoutePath. 206 * During maze-routing, we allocate RoutePaths from our own private area. 207 * When the time comes to return a RoutePath, it is copied to permanent 208 * storage (i.e., mallocMagic/freeMagic-managed) and the rest of the 209 * temporary storage is reclaimed. This approach avoids the need for 210 * additional pointers in each RoutePath that would otherwise be required 211 * for storage reclamation. 212 */ 213 #define PATHSPERSEG 200 /* Number of RoutePaths per segment */ 214 215 typedef struct routePage 216 { 217 struct routePage *rpp_next; 218 int rpp_free; 219 RoutePath rpp_array[PATHSPERSEG]; 220 } RoutePage; 221 222 /* First, last, and current RoutePages on list for allocating RoutePaths */ 223 extern RoutePage *mzFirstPage; 224 extern RoutePage *mzLastPage; 225 extern RoutePage *mzCurPage; 226 227 /* Allocate a new RoutePath */ 228 #define NEWPATH() \ 229 ((mzCurPage == NULL \ 230 || mzCurPage->rpp_free >= PATHSPERSEG) \ 231 ? mzAllocRPath() \ 232 : (RoutePath *) (&mzCurPage->rpp_array[mzCurPage->rpp_free++])) 233 234 /*------------------- Start and Dest Terminals ---------------------------- */ 235 /* A start or destination terminal is a rectangle and a type to connect 236 * on. This struct is used to create lists of legal start and destination 237 * areas. (This structure also used in other situations requiring rects 238 * with an associated tiletype.) 239 */ 240 typedef struct 241 { 242 Rect cr_rect; 243 TileType cr_type; 244 } ColoredRect; 245 246 /*----------------------Path Hash Table and Queues ----------------------- */ 247 248 /* 249 * The following hash table is used to index points 250 * so that redundant extension from points reached more than once 251 * is avoided. 252 * It is indexed by (x,y,routeLayer, orientation). Orientation is either 253 * Horizontal, vertical, or original (point on layer). Horizontal and 254 * vertical entries to the point are both extended from since they 255 * may vary in number of jogs and hence cost. 256 */ 257 typedef struct 258 { 259 Point pk_point; /* (x, y) */ 260 RouteLayer *pk_rLayer; /* "z" - Layer we are on */ 261 int pk_orient; /* Because of jogCost, we must distinguish 262 * between endpts of horizontal and vertical 263 * segments. 264 */ 265 #if SIZEOF_VOID_P == 8 266 unsigned pk_buffer; /* Structure size will be to word boundary! 267 * make sure we don't pass an uninitialized 268 * byte block to the hash function! 269 */ 270 #endif 271 } PointKey; 272 273 extern HashTable mzPointHash; 274 #define INITHASHSIZE 64 275 276 /* Queues for partial paths */ 277 extern Heap mzMaxToGoHeap; /* paths nearer destination than WINDOW */ 278 extern Heap mzMinCostHeap; /* paths in WINDOW */ 279 extern Heap mzMinAdjCostHeap; /* paths farther from dest than WINDOW*/ 280 extern List *mzBloomStack; /* paths in current local focus */ 281 extern List *mzStraightStack; /* focus paths being extended in straightline*/ 282 extern List *mzDownHillStack; /* focus paths followed only until cost 283 increases */ 284 extern List *mzWalkStack; /* paths inside walk (i.e. inside blocked 285 * area adjacent to destination. 286 */ 287 extern Heap mzMinCostCompleteHeap; /* completed paths */ 288 #define INITHEAPSIZE 64 289 290 /* ------------------------ Routines Global to MazeRouter --------------- */ 291 extern RoutePath *mzAllocRPath(); 292 extern char *mzCost2String(); 293 extern char *mzDICost2String(); 294 extern RouteType *mzFindRouteType(); 295 extern void mzNLClear(); 296 extern int *mzNLGetContainingInterval(); 297 extern void mzNLInit(); 298 extern void mzNLInsert(); 299 extern void mzTechFinal(); 300 extern int mzPaintContact(); 301 extern TileTypeBitMask mzTouchingTypes(); 302 303 extern void mzAddPoint(RoutePath *, Point *, RouteLayer *, int, int, dlong *); 304 extern void mzWalkRight(RoutePath *); 305 extern void mzWalkLeft(RoutePath *); 306 extern void mzWalkUp(RoutePath *); 307 extern void mzWalkDown(RoutePath *); 308 extern void mzWalkContact(RoutePath *); 309 extern dlong mzEstimatedCost(Point *); 310 extern RoutePath *mzSearch(); 311 312 313 /* --------------------- Variables Global to MazeRouter ----------------- */ 314 315 /* Use a maximum cost which we can add to without overflowing */ 316 #define COST_MAX (DLONG_MAX >> 2) 317 318 /* Parameter sets for mzrouting - from tech file. */ 319 extern MazeStyle *mzStyles; 320 321 /* Source of path currently being extended */ 322 extern int mzPathSource; 323 #define SOURCE_INIT 0 324 #define SOURCE_BLOOM 1 325 #define SOURCE_STRAIGHT 2 326 #define SOURCE_DOWNHILL 3 327 #define SOURCE_WALK 4 328 329 /* Paint generated by router */ 330 extern CellDef *mzResultDef; 331 extern CellUse *mzResultUse; 332 333 /* Cell to do routing in */ 334 extern CellUse *mzRouteUse; 335 336 /* Mask giving expanded subcells */ 337 extern int mzCellExpansionMask; 338 339 /* Don't route outside of this area */ 340 extern Rect mzBoundingRect; 341 342 /* List of Route starting terminals */ 343 extern List *mzStartTerms; 344 345 /* Cell containing dest areas */ 346 extern CellDef *mzDestAreasDef; 347 extern CellUse *mzDestAreasUse; 348 349 /* dest terminal alignment coordinates */ 350 extern NumberLine mzXAlignNL; 351 extern NumberLine mzYAlignNL; 352 /* initial size of above number lines */ 353 #define INITIAL_ALIGN_SIZE 100 354 355 /* Fence parity */ 356 extern bool mzInsideFence; 357 358 /* largest design rule distance - used during incremental blockage gen. */ 359 extern int mzContextRadius; 360 361 /* Route types */ 362 extern RouteLayer *mzRouteLayers; 363 extern RouteLayer *mzActiveRLs; 364 extern RouteContact *mzRouteContacts; 365 extern RouteType *mzRouteTypes; 366 extern RouteType *mzActiveRTs; 367 368 /* minimum radius of blockage plane info required around point being expanded. 369 * (Areas twice this size are gened. whenever the minimum is not met.) 370 */ 371 extern int mzBoundsIncrement; 372 373 /* If reset, degenerate estimation plane used (just 4 tiles - one for each 374 * quadrant with respect to destination point). 375 */ 376 extern int mzEstimate; 377 /* If set, routes may terminate at any geometry that is 378 * electrically connected to specified dest areas (default TRUE) 379 */ 380 extern int mzExpandDests; 381 /* If set, routes may start at any geometry that is 382 * electrically connected to specified start areas (default TRUE) 383 */ 384 extern int mzExpandStarts; 385 /* If set, only hints in toplevel cell are recognized */ 386 extern int mzTopHintsOnly; 387 /* Maximum distance route will extend into blocked area to connect to dest. */ 388 extern int mzMaxWalkLength; 389 /* limits area of route for performance, 390 * NOTE: IF NONNULL, USER MUST MAKE SURE ROUTE IS ACTUALLY LIMITED TO THIS 391 * AREA WITH FENCES, OTHERWISE THE RESULT IS UNPREDICTABLE. 392 */ 393 extern Rect *mzBoundsHint; 394 395 /* how generous to be with messages */ 396 extern int mzVerbosity; 397 /* if positive, limit on number of blooms */ 398 extern int mzBloomLimit; 399 400 /* minimum estimated total cost for initial paths */ 401 extern dlong mzMinInitialCost; 402 403 /* Parameters controlling search */ 404 extern RouteFloat mzPenalty; 405 extern dlong mzWRate; 406 extern dlong mzBloomDeltaCost; 407 extern dlong mzWWidth; 408 409 /* Statistics */ 410 extern dlong mzInitialEstimate; /* Initial estimated cost of route */ 411 extern int mzNumBlooms; 412 extern int mzNumOutsideBlooms; /* num blooms from outside window */ 413 extern int mzNumComplete; /* number of complete paths so far */ 414 extern int mzBlockGenCalls; /* # of calls to blockage gen. code */ 415 extern double mzBlockGenArea; /* area over which blockage planes 416 * have been gened. */ 417 extern int mzNumPathsGened; /* number of partial paths added to heap */ 418 extern int mzNumPaths; /* number of paths processed */ 419 extern int mzReportInterval; /* frequency that # of paths etc. 420 * is reported. */ 421 extern int mzPathsTilReport; /* counts down to next path report */ 422 423 /* Variables controlling search */ 424 extern dlong mzWInitialMinToGo; 425 extern dlong mzWInitialMaxToGo; 426 extern dlong mzBloomMaxCost; 427 428 /* Search status */ 429 extern dlong mzWindowMinToGo; /* Window location */ 430 extern dlong mzWindowMaxToGo; 431 432 /* Marked cell list */ 433 extern List *mzMarkedCellsList; 434 435 /* ------------ Interesting Point Macros -------------------------------- */ 436 /* The following macros are used in the low-level routines for finding 437 * the NEXT interesting point to the Right, Left, Up and Down. 438 * 439 * The macros are used to choose the first among 2 interesting points. 440 */ 441 #define PRUNE_TO_MIN(a,new,reasonSet,reason) \ 442 if (1) \ 443 { \ 444 if((new)<(a)) \ 445 { \ 446 (a) = (new); \ 447 (reasonSet) = (reason); \ 448 } \ 449 else if ((new)==(a)) \ 450 { \ 451 (reasonSet) |= (reason); \ 452 } \ 453 } else 454 455 #define PRUNE_TO_MAX(a,new,reasonSet,reason) \ 456 if (1) \ 457 { \ 458 if((new)>(a)) \ 459 { \ 460 (a) = (new); \ 461 (reasonSet) = (reason); \ 462 } \ 463 else if ((new)==(a)) \ 464 { \ 465 (reasonSet) |= (reason); \ 466 } \ 467 } else 468 469 #define RC_JOG 1 470 #define RC_ALIGNOTHER 2 471 #define RC_CONTACT 4 472 #define RC_ALIGNGOAL 8 473 #define RC_HINT 16 474 #define RC_ROTBEFORE 32 475 #define RC_ROTINSIDE 64 476 #define RC_BOUNDS 128 477 #define RC_WALK 256 478 #define RC_WALKUDC 512 479 #define RC_WALKLRC 1024 480 #define RC_DONE 2048 481 482 #endif /* _MZINTERNAL_H */ 483