asg/network.h

   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  */