1 /************************************************************ 2 ** 3 ** COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH 4 ** COPYRIGHT (C) 1996, 2004 GANNON UNIVERSITY 5 ** ALL RIGHTS RESERVED 6 ** 7 ** This software is distributed on an as-is basis 8 ** with no warranty implied or intended. No author 9 ** or distributor takes responsibility to anyone 10 ** regarding its use of or suitability. 11 ** 12 ** The software may be distributed and modified 13 ** freely for academic and other non-commercial 14 ** use but may NOT be utilized or included in whole 15 ** or part within any commercial product. 16 ** 17 ** This copyright notice must remain on all copies 18 ** and modified versions of this software. 19 ** 20 ************************************************************/ 21 22 23 /* file network.h */ 24 /* ------------------------------------------------------------------------ 25 * Common definitions for place and route spl 6/89 26 * 27 * ------------------------------------------------------------------------ 28 */ 29 30 #ifndef _ASG_NETWORK_H_ 31 #define _ASG_NETWORK_H_ 32 33 #include <stdio.h> 34 #include <stdlib.h> 35 #include <string.h> 36 #if defined(DARWIN) 37 #include <sys/malloc.h> 38 #else 39 #include <malloc.h> 40 #endif 41 #include <time.h> 42 #include <pwd.h> 43 #include <ctype.h> 44 #include <signal.h> 45 #include <sys/types.h> 46 #include <sys/stat.h> 47 #include <errno.h> 48 #include <limits.h> 49 #include <locale.h> 50 #include <unistd.h> /* for unlink() */ 51 52 #include <X11/Intrinsic.h> 53 #include <X11/StringDefs.h> 54 #include <X11/Shell.h> 55 #include <X11/Xutil.h> 56 #include <X11/cursorfont.h> 57 #include <X11/Xproto.h> 58 #include <X11/Xatom.h> 59 60 #ifdef TCL_WRAPPER 61 #include <tk.h> 62 #else 63 #include "Xw/Xw.h" 64 #include "Xw/Form.h" 65 #include "Xw/WorkSpace.h" 66 #include "Xw/PButton.h" 67 #include "Xw/SText.h" 68 #include "Xw/Cascade.h" 69 #include "Xw/PopupMgr.h" 70 #include "Xw/MenuBtn.h" 71 #include "Xw/BBoard.h" 72 #include "Xw/TextEdit.h" 73 #include "Xw/Toggle.h" 74 #endif 75 76 #ifndef P_tmpdir 77 #define P_tmpdir TMPDIR 78 #endif 79 80 #ifdef TCL_WRAPPER 81 #define malloc Tcl_Alloc 82 #define calloc(a,b) my_calloc(a, b) /* see utility.c */ 83 #define free(a) Tcl_Free((char *)(a)) 84 #define realloc(a,b) Tcl_Realloc((char *)(a), b) 85 86 #define fprintf tcl_printf /* defined by xcircuit */ 87 #define fflush tcl_stdflush 88 #endif 89 90 /*----------------------------------------------------------------------*/ 91 /* Local includes */ 92 /*----------------------------------------------------------------------*/ 93 94 #include "xcircuit.h" 95 /* #include "cursors.h" */ 96 /* #include "colordefs.h" */ 97 /* #include "menudep.h" */ 98 99 /*----------------------------------------------------------------------*/ 100 /* Function prototype declarations */ 101 /*----------------------------------------------------------------------*/ 102 #include "prototypes.h" 103 #include "list.h" 104 #include "var.h" 105 #include "cstitch.h" 106 107 /* 108 * Definition of the Design 109 * M is the set of all modules 110 * N is the set of all nets 111 * ST the set of system terminals 112 * T the set of sub-system terminals 113 * terms(module) : returns the subset of T for that module 114 * type(terminal(tUst)): returns its type (in, out, inout) 115 * postion-terminal(terminal(t)) : returns its (x,y) position 116 * net(terminal(tUst)) : returns the Net for this terminal 117 * size(module) : returns its x,y size 118 * side(terminal(t)) : returns (left, right, up, down) 119 */ 120 121 122 #define STF(x) \ 123 (((x) == FALSE) ? "FALSE" : "TRUE") 124 125 /* only extract_tree in place.c uses these two: */ 126 #define CHILDOK 2 127 #define CHILDNOTOK 3 128 #define LEAF 2 129 #define CLIPPED 4 130 131 /* used in most files, but also defined in net.h */ 132 #ifndef MAX 133 #define MAX(a,b) (((a)>(b))?(a):(b)) 134 #define MIN(a,b) (((a)<(b))?(a):(b)) 135 #endif 136 137 /* I think the only hack that counts on these values is in 138 * utility.c rot_side(). Everyone else cases them out. 139 */ 140 141 /* mod->flag values, used in placement */ 142 #define SEEN 1 143 #define UNSEEN 0 144 #define UNPLACED -1 145 #define PLACED 1 146 147 /* the type of connection matrix built may be */ 148 #define FORWARD 1 149 #define REVERSE -1 150 #define UNSIGNED 0 151 152 153 /* sides of module, clockwise order */ 154 #define LEFT 0 155 #define UP 1 156 #define TOP 1 157 #define RIGHT 2 158 #define BOTTOM 3 159 #define DOWN 3 160 161 #define SSIDE(x) \ 162 (((x) == LEFT) ? "LEFT":\ 163 ((x) == RIGHT) ? "RIGHT":\ 164 ((x) == UP) ? "UP" : "DOWN") 165 166 /* clockwise rotation amounts */ 167 #define ZERO 0 168 #define NINETY 1 169 #define ONE_EIGHTY 2 170 #define TWO_SEVENTY 3 171 172 #define SROT(x) \ 173 (((x) == ZERO) ? "ZERO":\ 174 ((x) == NINETY) ? "NINETY":\ 175 ((x) == ONE_EIGHTY) ? "ONE_EIGHTY" : "TWO_SEVENTY") 176 177 178 #define NONE 0 /* used with those below for system net types */ 179 180 /* directions of terminals */ 181 #define IN 1 /* Left side of icon */ 182 #define OUT 2 /* Right side of icon */ 183 #define INOUT 3 /* Bottom of icon */ 184 #define OUTIN 7 /* Top of icon */ 185 #define GND 4 186 #define VDD 5 187 #define DUMMY 6 188 189 #define SNTYPE(x) \ 190 (((x) == IN) ? "IN":\ 191 ((x) == OUT) ? "OUT":\ 192 ((x) == INOUT) ? "INOUT" :\ 193 ((x) == OUTIN) ? "OUTIN" :"NONE") 194 195 #define ICON_SIZE 8 /* default object icon sizes are 8 x 8 for sced */ 196 #define TERM_NAME_SIZE 32 /* size of strings for terminal names */ 197 #define GATE_NAME_SIZE 10 /* Aesthetic limit on icon name sizes */ 198 #define NET_NAME_SIZE 14 /* limit on net name sizes (fits _DUMMY_SIGNAL_) */ 199 200 #define XCANVAS_SCALE_FACTOR 6 /* Used to scale XCanvas bitmaps (see -b flag) */ 201 202 #define MAX_MOD 256 /* maximum number of modules */ 203 204 #define CHANNEL_HEIGHT 48 205 #define CHANNEL_LENGTH 48 206 #define MAX_DEPTH 12 /* maximum length of module box string */ 207 #define WHITE_SPACE 36 /* multiplier * # terms on a side for routing space */ 208 #define CC_SPACE 48 /* min routing space between cross-coupled modules*/ 209 210 /* 211 * Rents rule: SIZE = A |Connections| ** B with .5 < A < 5 and .4 < B < .8 212 * I have no idea for good values. 213 * Try A = 1 B = .5 and Size =5 Conn = 25 (note values below are -1) 214 */ 215 216 /* these are now just the default maxes, see the command line */ 217 #define MAX_PARTITION_SIZE 4 /* 4 should we follow rent's rule? */ 218 #define MAX_PARTITION_CONN 24 /* 24 connections from inside to outside */ 219 #define DEF_PARTITION_RULE 3 /* enable the -c and -s flags for partitioning */ 220 #define DEF_PARTITION_RATIO 3.0 /* sets the ratio used by rule number 2 */ 221 #define CC_SEARCH_LEVEL 2 /* only look for modules that are cross 222 coupled to two levels of removal */ 223 #define DEF_TURN_MODE 0 /* .5 Turns */ 224 #define TIGHT 1 225 226 227 /* offsets around things for routing */ 228 #define TERM_SIZE 2 229 #define OUTSIDE_BORDER 100 230 231 /* default sizes for the virtual space tiles used for each partition: */ 232 #define TILE_SPACE_X_LEN 15000 233 #define TILE_SPACE_Y_LEN 15000 234 #define TILE_SPACE_X_POS -5000 235 #define TILE_SPACE_Y_POS -5000 236 237 238 /* for routing and tile space support */ 239 #define HORZ 0 240 #define VERT 1 241 242 /*- begin psfigs support ------------------------------------------------------*/ 243 #define XNOR_GATE "XNOR" /* Used to identify the Type of the module */ 244 #define BUFFER_GATE "BUFFER" 245 #define INPUT_TERM "IN" 246 #define OUTPUT_TERM "OUT" 247 #define INOUT_TERM "INOUT" 248 #define OUTIN_TERM "OUTIN" 249 #define GENERIC_BLOCK "BLOCK" 250 251 252 /* Used within the placement algorithm; clip_null_gates() also uses this 253 when maintaining the integrity of the global "module_info[]" structure. 254 The integers typically note which partition numbers are referenced by 255 a particular module, there being one such structure for each module. 256 */ 257 typedef struct info_struct 258 { 259 int in, out, used, order; 260 } info_type; 261 262 263 /*--------------------------------------------------------------- 264 * Templates for major linked list data structures. 265 * We use a general paradigm of a linked list of "things" 266 * the list has a "this" field and a "next" field 267 * the "this" field is coerced into a pointer to a type "thing" 268 * the "next" field is coerced into a pointer to a list of "things" 269 * We then use generic list routines (in utility.c) to manipulate 270 * these. 271 *--------------------------------------------------------------- 272 */ 273 274 typedef struct term_struct term; /* the terminals */ 275 typedef struct mod_struct module; /* the modules */ 276 typedef struct net_struct net; /* the nets */ 277 typedef struct rng_struct rng; /* the ranges of segments */ 278 typedef struct clu_struct cluster; /* the clusters of modules */ 279 280 /* typedef struct list_struct list; Moved to 'list.h' */ 281 typedef struct tnode_struct tnode; /* for binary trees */ 282 typedef struct term_list tlist; 283 typedef struct mod_list mlist; 284 typedef struct net_list nlist; 285 typedef struct rng_list rlist; 286 typedef struct cl_list clist; 287 typedef struct cluster_tree ctree; 288 289 typedef struct link_list llist; /* for 2d linked lists */ 290 /* typedef struct indexed_list ilist; Moved to 'list.h' */ 291 292 293 struct term_struct 294 /* terminals are where nets attach to modules */ 295 { 296 char *name; 297 int x_pos; /* we will eventually have to look this up */ 298 int y_pos; 299 module *mod; 300 int side; /* side of the module on which it apears */ 301 int type; /* direction in, out, inout, outin for this module */ 302 net *nt; /* the net that this terminal belongs to */ 303 }; 304 305 struct mod_struct 306 /* modules are the "gates" both simple and complex, rectangles are assumed */ 307 { 308 int index; /* unique number */ 309 char *name; /* unique instance name */ 310 char *type; /* gate types will be our key for icons */ 311 /* int dly_type; /* inertial or transport -- for simulation */ 312 /* int delay; /* the delay time -- for simulation */ 313 int x_pos; /* we will determine this in "place" */ 314 int y_pos; /* we will determine this in "place" */ 315 int x_size; /* we will have to look this up */ 316 int y_size; /* we will have to look this up */ 317 int flag; /* flag for recursive marking */ 318 int placed; /* marks that the critter has been placed within a partition */ 319 int rot; /* rotation */ 320 tile *htile; /* Tile in the horizontal routing space to which this module is assigned */ 321 tile *vtile; /* Tile in the vertical routing space to which this module is assigned */ 322 term *primary_in; /* the primary input terminal */ 323 term *primary_out; /* the primary output terminal */ 324 tlist *terms; /* the terminals on this module */ 325 var *fx, *fy; /* Fuzzy X and Fuzzy Y positions for this module */ 326 327 }; 328 329 struct clu_struct 330 /* clusters are collections of gates */ 331 { 332 int index; /* unique number */ 333 int size; /* number of elements in branch */ 334 int connects; /* number of connections external to the cluster */ 335 module *contents; /* the module within this cluster (leaf nodes) */ 336 }; 337 338 struct net_struct 339 /* a net is a list of terminals, one electrical node */ 340 { 341 char *name; 342 tlist *terms; 343 int type; /* identify system terminal nets */ 344 int rflag; /* Routing status flag */ 345 list *expns; /* Used in both local & global routing; */ 346 list *done; /* Records expansions that are completed */ 347 list *route; /* used in local routing */ 348 }; 349 350 struct rng_struct 351 /* a range of a segment is a 3-tuple */ 352 { 353 int x; /* "" : lower index in the other direction */ 354 int y; /* "" : upper index */ 355 int c; /* number of crossed wires */ 356 }; 357 358 /*-----------------------------------------------------*/ 359 struct tnode_struct 360 /* these are coerced to be binary trees of the sort below */ 361 { 362 int *this; 363 tnode *left, *right; 364 }; 365 366 struct cluster_tree 367 { 368 cluster *this; 369 ctree *left, *right; 370 }; 371 372 373 /*-----------------------------------------------------*/ 374 struct term_list 375 /* */ 376 { 377 term *this; 378 tlist *next; 379 }; 380 struct mod_list 381 /* */ 382 { 383 module *this; 384 mlist *next; 385 }; 386 387 struct cl_list 388 /* Used to maintain clusters as they are built into and taken from a tree. */ 389 { 390 int index; 391 ctree *this; 392 clist *next; 393 }; 394 395 struct net_list 396 /* */ 397 { 398 net *this; 399 nlist *next; 400 }; 401 402 403 struct rng_list 404 /* */ 405 { 406 rng *this; 407 rlist *next; 408 }; 409 410 struct link_list 411 /* this is different for 2 - d lists */ 412 { 413 int index; /* index */ 414 list *values; /* list */ 415 llist *next; /* next link */ 416 }; 417 418 419 #endif 420 /*--------------------------------------------------------------- 421 * END OF FILE 422 *--------------------------------------------------------------- 423 */ 424