1 /* 2 * mzrouter.h -- 3 * 4 * This file defines the interface provided by the maze router 5 * module to the rest of Magic. 6 * 7 * ********************************************************************* 8 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the * 9 * * University of California. * 10 * * Permission to use, copy, modify, and distribute this * 11 * * software and its documentation for any purpose and without * 12 * * fee is hereby granted, provided that the above copyright * 13 * * notice appear in all copies. The University of California * 14 * * makes no representations about the suitability of this * 15 * * software for any purpose. It is provided "as is" without * 16 * * express or implied warranty. Export of this software outside * 17 * * of the United States of America may require an export license. * 18 * ********************************************************************* 19 * 20 * rcsid $Header: /usr/cvsroot/magic-8.0/mzrouter/mzrouter.h,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $ 21 */ 22 23 #ifndef _MZROUTER_H 24 #define _MZROUTER_H 25 26 #include "database/database.h" 27 #include "utils/geometry.h" 28 #include "utils/list.h" 29 30 /* This module does not support a command level interface: it is accessed 31 * by other modules (such as the irouter and the garouter) via procedure 32 * calls. 33 * 34 * NOTE: a wizard command interface (`*mzroute') IS provided for testing. 35 * (see mzTestCmd.c) 36 */ 37 38 /* PARAMETER STRUCTURES */ 39 /*----------------------------- RouteType ----------------------------------*/ 40 41 /* 42 * Contains information about a tile type used by the router. 43 * 44 * This structure is contained in both RouteLayer and RouteContacts strucs. 45 * It contains information that is relevant to both route layers and layers 46 * used for contacts by the router. 47 * 48 * *DERIVED* = member computed by MZInitRoute() prior to each route. 49 * 50 */ 51 52 typedef struct 53 routetype 54 { 55 /* IDENTIFICATION */ 56 TileType rt_tileType; /* "Home" tile type of this layer */ 57 58 /* STATUS */ 59 bool rt_active; /* Maze router uses type only if this flag 60 set */ 61 62 /* DESIGN RULES */ 63 int rt_width; /* Width of path or contact */ 64 int rt_length; /* Length of contact or minimum */ 65 /* length of a path to satisfy */ 66 /* minimum area requirements */ 67 int rt_spacing[TT_MAXTYPES + 1]; /* spacings to various types 68 last entry is SUBCELL spacing */ 69 70 /* DERIVATIVE DESIGN RULES - computed from DESIGN RULES above. 71 * for contact routeTypes, max design rules for components used, so 72 * that a contact will not be placed unless there is space for wires 73 * on both connected layers. 74 * 75 * bloatTop = spacing 76 * bloatBot = spacing + width - 1 77 */ 78 int rt_effWidth; /* *DERIVED* - for contact, 79 * max of component width */ 80 int rt_bloatBot[TT_MAXTYPES + 1]; /* *DERIVED* - bloat distance 81 * to bottom and left */ 82 int rt_bloatTop[TT_MAXTYPES + 1]; /* *DERIVED* - bloat distance to 83 * top and right */ 84 85 /* BLOCKAGE PLANES */ 86 Plane *rt_hBlock; /* Blockage plane for layer organized into maximal 87 horizontal strips */ 88 Plane *rt_vBlock; /* Blockage plane for layer organized into maximal 89 vertical strips */ 90 91 struct routetype *rt_next; /* For convenience, all route types are 92 * threaded 93 * together. (This threading is in addition 94 * to the routeLayers list and the 95 * routeContacts list. 96 */ 97 struct routetype *rt_nextActive; /* *DERIVED* - This list built in 98 * MZInitRoute() */ 99 } RouteType; 100 101 /*--------------------------- RouteLayer ----------------------------------*/ 102 103 /* 104 * The RouteLayers list contains one of these structures for each 105 * layer on which routing is permitted. The structure is a 106 * handle for all information relevant to a route layer. 107 * 108 * *DERIVED* = member computed by MZInitRoute() prior to each route. 109 * 110 */ 111 112 typedef struct routelayer 113 { 114 /* TYPE */ 115 RouteType rl_routeType; /* Contains info. relevant to both 116 route layers and contact types */ 117 118 /* PLANE NUMBER */ 119 int rl_planeNum; /* Plane number of layer */ 120 121 /* CONTACTS */ 122 List *rl_contactL; /* list of contact types that connect to this layer */ 123 124 /* COST */ 125 int rl_hCost; /* cost per unit length for horizontal segments */ 126 int rl_vCost; /* cost per unit length for vertical segments */ 127 int rl_jogCost; /* cost of a jog */ 128 int rl_hintCost; /* cost per unit area for deviation from hint */ 129 int rl_overCost; /* cost per unit length for crossing another route layer */ 130 131 /* NEXT ROUTE LAYER */ 132 struct routelayer *rl_next; 133 struct routelayer *rl_nextActive; /* *DERIVED* - Only accurate after 134 * MZInitRoute() */ 135 } RouteLayer; 136 137 /*---------------------------- RouteContact ------------------------------*/ 138 /* 139 * This sturcture describes a type of contact to be used during routing. 140 * Contacts connect two route layers. 141 */ 142 143 typedef struct routecontact 144 { 145 /* TYPE */ 146 RouteType rc_routeType; /* Contains info. relevant to both 147 route layers and contact types */ 148 149 /* LAYERS CONNECTED */ 150 RouteLayer *rc_rLayer1; /* Layers connected by this type of contact */ 151 RouteLayer *rc_rLayer2; 152 153 /* COST */ 154 int rc_cost; 155 156 /* NEXT ROUTE CONTACT */ 157 struct routecontact *rc_next; /* next in RouteContacts list */ 158 159 } RouteContact; 160 161 /* ----------------------------- Paths ----------------------------------- */ 162 163 /* 164 * Zero-width path segment structure. Paths and partial-paths built from 165 * these structures during search. 166 * 167 * Can be flushed out to paint via MZPaintPath(). 168 * 169 */ 170 typedef struct rpath 171 { 172 struct rpath *rp_back; /* Pointer to previous leg of path */ 173 RouteLayer *rp_rLayer; /* Route layer of this segment */ 174 int rp_orient; /* orientation of this segment, 175 * 'H' = hor, 'V' = vert, 'O' = contact 176 * or start point. 177 */ 178 Point rp_entry; /* Cost was computed to this point */ 179 int rp_extendCode; /* directions to extend */ 180 dlong rp_cost; /* estimated total cost */ 181 dlong rp_togo; /* estimated cost to completion */ 182 } RoutePath; 183 184 /* extension codes */ 185 #define EC_RIGHT 1 186 #define EC_LEFT 2 187 #define EC_UP 4 188 #define EC_DOWN 8 189 #define EC_UDCONTACTS 16 190 #define EC_LRCONTACTS 32 191 #define EC_ALL 63 192 193 #define EC_WALKRIGHT 64 194 #define EC_WALKLEFT 128 195 #define EC_WALKUP 256 196 #define EC_WALKDOWN 512 197 #define EC_WALKUDCONTACT 1024 198 #define EC_WALKLRCONTACT 2048 199 200 #define EC_COMPLETE 4096 201 202 /*----------------------- Soft Floating Point ----------------------------- */ 203 /* (Floating Point Format for our own software-implemented floating-point. 204 * Used for the penalty factor for costs outside the window.) 205 */ 206 207 /* Note: nExponent must be >=0 208 * To multiply dlong by routeFloat, first multiply by mantissa, then 209 * shift right nExponent number of bits. 210 */ 211 typedef struct routeFloat 212 { 213 int rf_mantissa; 214 int rf_nExponent; 215 } RouteFloat; 216 217 /*---------------------------- MazeParameters ------------------------------*/ 218 219 /* 220 * This sturcture contains all maze router parameters, including design rules. 221 */ 222 typedef struct mazeparameters 223 { 224 RouteLayer *mp_rLayers; /* list of route layers */ 225 RouteContact *mp_rContacts; /* list of route contacts */ 226 RouteType *mp_rTypes; /* list of all route types */ 227 228 RouteFloat mp_penalty; /* Penalty for lagging behind window */ 229 /* BY NP---changed from DoubleInt to dlong */ 230 dlong mp_wWidth; /* Window width */ 231 dlong mp_wRate; /* Rate of motion for window */ 232 dlong mp_bloomDeltaCost; /* Max increment. in cost while blooming */ 233 int mp_boundsIncrement; /* min radius of blockage info required 234 * around point being extended - twice the 235 * increment is generated whenever gen. is 236 * necessary. 237 */ 238 bool mp_estimate; /* If set, nontrivial estimation of cost 239 * to completion is used - factoring in 240 * blocks due to subcells and fences. 241 */ 242 243 bool mp_expandEndpoints; /* If set, routes may start or terminate anywhere 244 * that is electrically connected 245 * to specified start or dest regions. 246 */ 247 248 bool mp_topHintsOnly; /* If set, only hints in the top cell presented 249 * to the router are recognized - used by 250 * garouter to speed up processing. 251 */ 252 253 int mp_maxWalkLength; /* max distance into blocked area route 254 * will extend in order to connect to 255 * a destination terminal. If set to -1, 256 * max distance is computed as a function 257 * of design rules for active layers prior 258 * to each route. 259 */ 260 261 Rect *mp_boundsHint; /* If nonnull, improves perfomrnace by limiting 262 * estimation, bounds generation etc to this 263 * area. 264 * NOTE: IF SET IT IS THE USERS RESPONSIBILITY 265 * TO CONTAIN THE ROUTE WITHIN THIS AREA 266 * VIA FENCES - ELSE BIZARRE BEHAVIOUR 267 * IS POSSIBLE. 268 */ 269 270 int mp_verbosity; /* amount of messages printed: 271 * 0 = errors and warnings only, 272 * 1 = brief 273 * 2 = lots of statistics. 274 */ 275 276 int mp_bloomLimit; /* if positive, puts upper limit on number of 277 * blooms in maze search before router 278 * terminates. 279 * 280 * If negative or 0, no limit is imposed. 281 */ 282 } MazeParameters; 283 #define VERB_WARNONLY 0 284 #define VERB_BRIEF 1 285 #define VERB_STATS 2 286 287 /* Return codes for MZRoute() */ 288 289 #define MZ_NO_ACTION -1 /* Never ran MZRoute() */ 290 #define MZ_SUCCESS 0 /* Successful route */ 291 #define MZ_CURRENT_BEST 1 /* Interrupted, returned best choice so far */ 292 #define MZ_ALREADY_ROUTED 2 /* Start node = Dest node already */ 293 #define MZ_FAILURE 3 /* Route failed for some reason */ 294 #define MZ_UNROUTABLE 4 /* Failed to generate a walk to the dest node */ 295 #define MZ_INTERRUPTED 5 /* Interrupted, no route was found */ 296 297 /* INTERFACE PROCEDURES */ 298 /* Call sequence for routing: 299 * 1. MZInitRoute() 300 * 2. MZAddStart()'s and MZAddDest()'s 301 * 3. MZRoute() 302 * 4. MZPaintPath() 303 * 5. MZClean() 304 * 305 * NOTE: IF THE SEQUENCE IS ABORTED PART WAY THROUGH BE SURE AND CALL MZClean() 306 * PRIOR TO RETURNING TO MAGIC COMMAND PROCESSOR. THIS IS NECESSARY TO 307 * RESTORE TILE CLIENTDATA TO INITIAL STATE. 308 */ 309 extern MazeParameters *MZFindStyle(); /* return parms of given style */ 310 extern MazeParameters *MZCopyParms(); /* Create new MazeParameters */ 311 312 extern void MZInitRoute(); /* Initialize route */ 313 extern void MZAddStart(); /* After MzInitRoute, to add start points */ 314 extern void MZAddDest(); /* After MZInitRoute, to add dest area */ 315 extern RoutePath *MZRoute(); /* After MZAddStart, and MZAddDest 316 * to do search */ 317 extern CellUse *MZPaintPath(); /* Turns path into actual paint */ 318 extern void MZClean(); /* Reclaim storage */ 319 extern void MZTest(); /* Wizard command interface (`*mzroute') */ 320 extern RouteType *MZFindRouteType(); 321 extern RouteLayer *MZFindRouteLayer(); 322 extern RouteContact *MZGetContact(); 323 extern RouteContact *MZRouteContact(); 324 extern void MZPrintRLs(); /* Allows clients to dump maze parms */ 325 extern void MZPrintRCs(); 326 extern void MZPrintRLListNames(); 327 extern void MZPrintRCListNames(); 328 extern void MZFreeParameters(MazeParameters *); 329 330 extern void MZInit(); 331 extern void MZAfterTech(); 332 333 /* TECHNOLOGY FILE PROCESSING PROCEDURES */ 334 /* "mzrouter" section */ 335 extern void MZTechInit(); 336 extern bool MZTechLine(); 337 extern void MZTechFinal(); 338 339 /* plane scaling pointer recovery */ 340 341 extern void MZAttachHintPlanes(); 342 343 /* EXPORTED VARIABLES */ 344 345 /* Major cost unit */ 346 extern int mzMajorCostUnit; 347 348 #endif /* _MZROUTER_H */ 349