1 /*--------------------------------------------------------------*/
2 /* mask.c -- qrouter general purpose autorouter */
3 /* Route mask generation */
4 /*--------------------------------------------------------------*/
5 /* Written by Tim Edwards, June 2011, based on code by Steve */
6 /* Beccue, 2003 */
7 /*--------------------------------------------------------------*/
8
9 #include <ctype.h>
10 #include <stdio.h>
11 #include <math.h>
12 #include <stdarg.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <unistd.h>
16
17 #ifdef TCL_QROUTER
18 #include <tk.h>
19 #endif
20
21 #include "qrouter.h"
22 #include "qconfig.h"
23 #include "point.h"
24 #include "node.h"
25 #include "maze.h"
26 #include "mask.h"
27 #include "output.h"
28 #include "lef.h"
29 #include "def.h"
30 #include "graphics.h"
31
32 u_char *RMask; // mask out best area to route
33
34 /*--------------------------------------------------------------*/
35 /* Comparison routine used for qsort. Sort nets by number of */
36 /* nodes. */
37 /*--------------------------------------------------------------*/
38
compNets(NET * a,NET * b)39 int compNets(NET *a, NET *b)
40 {
41 NET p = *a;
42 NET q = *b;
43
44 // NULL nets get shoved up front
45 if (p == NULL) return ((q == NULL) ? 0 : -1);
46 if (q == NULL) return 1;
47
48 // Sort critical nets at the front by assigned order
49
50 if ((p->flags & NET_CRITICAL) || (q->flags & NET_CRITICAL)) {
51 if (!(p->flags & NET_CRITICAL)) return 1;
52 else if (!(q->flags & NET_CRITICAL)) return -1;
53 else return (p->netorder < q->netorder) ? -1 : 1;
54 }
55
56 // Otherwise sort by number of nodes
57
58 if (p->numnodes < q->numnodes)
59 return 1;
60 if (p->numnodes > q->numnodes)
61 return -1;
62 return 0;
63 }
64
65 /*--------------------------------------------------------------*/
66 /* Alternative net comparison used for qsort. Sort nets by */
67 /* minimum dimension of the bounding box, and if equal, by the */
68 /* number of nodes in the net. Bounding box dimensions are */
69 /* ordered smallest to largest, and number of nodes are ordered */
70 /* largest to smallest. */
71 /*--------------------------------------------------------------*/
72
altCompNets(NET * a,NET * b)73 int altCompNets(NET *a, NET *b)
74 {
75 NET p = *a;
76 NET q = *b;
77
78 int pwidth, qwidth, pheight, qheight, pdim, qdim;
79
80 // Any NULL nets get shoved up front
81 if (p == NULL) return ((q == NULL) ? 0 : -1);
82 if (q == NULL) return 1;
83
84 // Sort critical nets at the front by assigned order
85
86 if ((p->flags & NET_CRITICAL) || (q->flags & NET_CRITICAL)) {
87 if (!(p->flags & NET_CRITICAL)) return 1;
88 else if (!(q->flags & NET_CRITICAL)) return -1;
89 else return (p->netorder < q->netorder) ? -1 : 1;
90 }
91
92
93 // Otherwise sort as described above.
94
95 pwidth = p->xmax - p->xmin;
96 pheight = p->ymax - p->ymin;
97 pdim = (pwidth > pheight) ? pheight : pwidth;
98
99 qwidth = q->xmax - q->xmin;
100 qheight = q->ymax - q->ymin;
101 qdim = (qwidth > qheight) ? qheight : qwidth;
102
103 if (pdim < qdim)
104 return (-1);
105 else if (pdim > qdim)
106 return (1);
107 else {
108 if (p->numnodes < q->numnodes)
109 return (1);
110 if (p->numnodes > q->numnodes)
111 return (-1);
112 return (0);
113 }
114 }
115
116 /*--------------------------------------------------------------*/
117 /* create_netorder --- assign indexes to net->netorder */
118 /* Re-sort Nlnets according to net order. Since Nlnets is a */
119 /* global variable, nothing is returned from this routine. */
120 /* */
121 /* method = 0 */
122 /* Nets are ordered simply from those with the most nodes */
123 /* to those with the fewest. However, any nets marked */
124 /* critical in the configuration or critical net files */
125 /* will be given precedence. */
126 /* */
127 /* method = 1 */
128 /* Nets are ordered by minimum bounding box dimension. */
129 /* This is based on the principle that small or narrow */
130 /* nets have little room to be moved around without */
131 /* greatly increasing the net length. If these are put */
132 /* down first, then remaining nets can route around them. */
133 /*--------------------------------------------------------------*/
134
create_netorder(u_char method)135 void create_netorder(u_char method)
136 {
137 int i, j;
138 NET net;
139 STRING cn;
140
141 i = 1;
142 for (cn = CriticalNet; cn; cn = cn->next) {
143 if (Verbose > 1)
144 Fprintf(stdout, "critical net %s\n", cn->name);
145 net = DefFindNet(cn->name);
146 if (net) {
147 net->netorder = i++;
148 net->flags |= NET_CRITICAL;
149 }
150 }
151
152 switch (method) {
153 case 0:
154 qsort((char *)Nlnets, Numnets, (int)sizeof(NET),
155 (__compar_fn_t)compNets);
156 break;
157 case 1:
158 qsort((char *)Nlnets, Numnets, (int)sizeof(NET),
159 (__compar_fn_t)altCompNets);
160 break;
161 }
162
163 for (i = 0; i < Numnets; i++) {
164 net = Nlnets[i];
165 net->netorder = i++;
166 }
167
168 } /* create_netorder() */
169
170 /*--------------------------------------------------------------*/
171 /* Measure and record the bounding box of a net. */
172 /* This is preparatory to generating a mask for the net. */
173 /* Find the bounding box of each node, and record that */
174 /* information, at the same time computing the whole net's */
175 /* bounding box as the area bounding all of the nodes. */
176 /* Determine if the bounding box is more horizontal or */
177 /* vertical, and specify a direction for the net's trunk line. */
178 /* Initialize the trunk line as the midpoint between all of the */
179 /* nodes, extending the width (or height) of the bounding box. */
180 /* Initialize the node branch position as the line extending */
181 /* from the middle of the node's bounding box to the trunk */
182 /* line. These positions (trunk and branches) will be sorted */
183 /* and readjusted by "create_nodeorder()". */
184 /*--------------------------------------------------------------*/
185
find_bounding_box(NET net)186 void find_bounding_box(NET net)
187 {
188 NODE n1, n2;
189 DPOINT d1tap, d2tap, dtap, mintap;
190 int mindist, dist, dx, dy;
191
192 if (net->numnodes == 2) {
193
194 n1 = (NODE)net->netnodes;
195 n2 = (NODE)net->netnodes->next;
196
197 // Simple 2-pass---pick up first tap on n1, find closest tap on n2,
198 // then find closest tap on n1.
199
200 d1tap = (n1->taps == NULL) ? n1->extend : n1->taps;
201 if (d1tap == NULL) return;
202 d2tap = (n2->taps == NULL) ? n2->extend : n2->taps;
203 if (d2tap == NULL) return;
204 dx = d2tap->gridx - d1tap->gridx;
205 dy = d2tap->gridy - d1tap->gridy;
206 mindist = dx * dx + dy * dy;
207 mintap = d2tap;
208 for (d2tap = d2tap->next; d2tap != NULL; d2tap = d2tap->next) {
209 dx = d2tap->gridx - d1tap->gridx;
210 dy = d2tap->gridy - d1tap->gridy;
211 dist = dx * dx + dy * dy;
212 if (dist < mindist) {
213 mindist = dist;
214 mintap = d2tap;
215 }
216 }
217 d2tap = mintap;
218 d1tap = (n1->taps == NULL) ? n1->extend : n1->taps;
219 dx = d2tap->gridx - d1tap->gridx;
220 dy = d2tap->gridy - d1tap->gridy;
221 mindist = dx * dx + dy * dy;
222 mintap = d1tap;
223 for (d1tap = d1tap->next; d1tap != NULL; d1tap = d1tap->next) {
224 dx = d2tap->gridx - d1tap->gridx;
225 dy = d2tap->gridy - d1tap->gridy;
226 dist = dx * dx + dy * dy;
227 if (dist < mindist) {
228 mindist = dist;
229 mintap = d1tap;
230 }
231 }
232 d1tap = mintap;
233
234 net->xmin = (d1tap->gridx < d2tap->gridx) ? d1tap->gridx : d2tap->gridx;
235 net->xmax = (d1tap->gridx < d2tap->gridx) ? d2tap->gridx : d1tap->gridx;
236 net->ymin = (d1tap->gridy < d2tap->gridy) ? d1tap->gridy : d2tap->gridy;
237 net->ymax = (d1tap->gridy < d2tap->gridy) ? d2tap->gridy : d1tap->gridy;
238 }
239 else { // Net with more than 2 nodes
240
241 // Use the first tap point for each node to get a rough bounding box and
242 // centroid of all taps
243 net->xmax = net->ymax = -(MAXRT);
244 net->xmin = net->ymin = MAXRT;
245 for (n1 = net->netnodes; n1 != NULL; n1 = n1->next) {
246 dtap = (n1->taps == NULL) ? n1->extend : n1->taps;
247 if (dtap) {
248 if (dtap->gridx > net->xmax) net->xmax = dtap->gridx;
249 if (dtap->gridx < net->xmin) net->xmin = dtap->gridx;
250 if (dtap->gridy > net->ymax) net->ymax = dtap->gridy;
251 if (dtap->gridy < net->ymin) net->ymin = dtap->gridy;
252 }
253 }
254 }
255 }
256
257 /*--------------------------------------------------------------*/
258 /* defineRouteTree() --- */
259 /* */
260 /* Define a trunk-and-branches potential best route for a net. */
261 /* */
262 /* The net is analyzed for aspect ratio, and is determined if */
263 /* it will have a horizontal or vertical trunk. Then, each */
264 /* node will define a branch line extending from the node */
265 /* position to the trunk. Trunk position is recorded in the */
266 /* net record, and branch positions are recorded in the node */
267 /* records. */
268 /* */
269 /* To do: */
270 /* Trunk and branch lines will be analyzed for immediate */
271 /* collisions and sorted to help ensure a free track exists for */
272 /* each net's trunk line. */
273 /*--------------------------------------------------------------*/
274
defineRouteTree(NET net)275 void defineRouteTree(NET net)
276 {
277 NODE n1;
278 DPOINT dtap;
279 int xcent, ycent, xmin, ymin, xmax, ymax;
280
281 // This is called after create_bounding_box(), so bounds have
282 // been calculated.
283
284 xmin = net->xmin;
285 xmax = net->xmax;
286 ymin = net->ymin;
287 ymax = net->ymax;
288
289 if (net->numnodes == 2) {
290
291 // For 2-node nets, record the initial position as
292 // one horizontal trunk + one branch for one "L" of
293 // the bounding box, and one vertical trunk + one
294 // branch for the other "L" of the bounding box.
295
296 net->trunkx = xmin;
297 net->trunky = ymin;
298 }
299 else if (net->numnodes > 0) {
300
301 // Use the first tap point for each node to get a rough
302 // centroid of all taps
303
304 xcent = ycent = 0;
305 for (n1 = net->netnodes; n1 != NULL; n1 = n1->next) {
306 dtap = (n1->taps == NULL) ? n1->extend : n1->taps;
307 if (dtap == NULL) continue;
308 xcent += dtap->gridx;
309 ycent += dtap->gridy;
310 }
311 xcent /= net->numnodes;
312 ycent /= net->numnodes;
313
314 // Record the trunk line in the net record
315
316 net->trunkx = xcent;
317 net->trunky = ycent;
318 }
319
320 if (xmax - xmin > ymax - ymin) {
321 // Horizontal trunk preferred
322 net->flags &= ~NET_VERTICAL_TRUNK;
323 }
324 else {
325 // Vertical trunk preferred
326 net->flags |= NET_VERTICAL_TRUNK;
327 }
328
329 // Set the branch line positions to the node tap points
330
331 for (n1 = net->netnodes; n1; n1 = n1->next) {
332 dtap = (n1->taps == NULL) ? n1->extend : n1->taps;
333 if (!dtap) continue;
334 n1->branchx = dtap->gridx;
335 n1->branchy = dtap->gridy;
336 }
337 }
338
339 /*--------------------------------------------------------------*/
340 /* initMask() --- */
341 /*--------------------------------------------------------------*/
342
initMask(void)343 void initMask(void)
344 {
345 RMask = (u_char *)calloc(NumChannelsX * NumChannelsY,
346 sizeof(u_char));
347 if (!RMask) {
348 fprintf(stderr, "Out of memory 3.\n");
349 exit(3);
350 }
351 }
352
353 /*--------------------------------------------------------------*/
354 /* Fill mask around the area of a vertical line */
355 /*--------------------------------------------------------------*/
356
357 void
create_vbranch_mask(int x,int y1,int y2,u_char slack,u_char halo)358 create_vbranch_mask(int x, int y1, int y2, u_char slack, u_char halo)
359 {
360 int gx1, gx2, gy1, gy2;
361 int i, j, v;
362 u_char m;
363
364 gx1 = x - slack;
365 gx2 = x + slack;
366 if (y1 > y2) {
367 gy1 = y2 - slack;
368 gy2 = y1 + slack;
369 }
370 else {
371 gy1 = y1 - slack;
372 gy2 = y2 + slack;
373 }
374 if (gx1 < 0) gx1 = 0;
375 if (gx2 >= NumChannelsX) gx2 = NumChannelsX - 1;
376 if (gy1 < 0) gy1 = 0;
377 if (gy2 >= NumChannelsY) gy2 = NumChannelsY - 1;
378
379 for (i = gx1; i <= gx2; i++)
380 for (j = gy1; j <= gy2; j++)
381 RMASK(i, j) = (u_char)0;
382
383 for (v = 1; v < halo; v++) {
384 if (gx1 > 0) gx1--;
385 if (gx2 < NumChannelsX - 1) gx2++;
386 if (y1 > y2) {
387 if (gy1 < NumChannelsY - 1) gy1++;
388 if (gy2 < NumChannelsY - 1) gy2++;
389 }
390 else {
391 if (gy1 > 0) gy1--;
392 if (gy2 > 0) gy2--;
393 }
394 for (i = gx1; i <= gx2; i++)
395 for (j = gy1; j <= gy2; j++) {
396 m = RMASK(i, j);
397 if (m > v) RMASK(i, j) = (u_char)v;
398 }
399 }
400 }
401
402 /*--------------------------------------------------------------*/
403 /* Fill mask around the area of a horizontal line */
404 /*--------------------------------------------------------------*/
405
406 void
create_hbranch_mask(int y,int x1,int x2,u_char slack,u_char halo)407 create_hbranch_mask(int y, int x1, int x2, u_char slack, u_char halo)
408 {
409 int gx1, gx2, gy1, gy2;
410 int i, j, v;
411 u_char m;
412
413 gy1 = y - slack;
414 gy2 = y + slack;
415 if (x1 > x2) {
416 gx1 = x2 - slack;
417 gx2 = x1 + slack;
418 }
419 else {
420 gx1 = x1 - slack;
421 gx2 = x2 + slack;
422 }
423 if (gx1 < 0) gx1 = 0;
424 if (gx2 >= NumChannelsX) gx2 = NumChannelsX - 1;
425 if (gy1 < 0) gy1 = 0;
426 if (gy2 >= NumChannelsY) gy2 = NumChannelsY - 1;
427
428 for (i = gx1; i <= gx2; i++)
429 for (j = gy1; j <= gy2; j++)
430 RMASK(i, j) = (u_char)0;
431
432 for (v = 1; v < halo; v++) {
433 if (gy1 > 0) gy1--;
434 if (gy2 < NumChannelsY - 1) gy2++;
435 if (x1 > x2) {
436 if (gx1 < NumChannelsX - 1) gx1++;
437 if (gx2 < NumChannelsX - 1) gx2++;
438 }
439 else {
440 if (gx1 > 0) gx1--;
441 if (gx2 > 0) gx2--;
442 }
443 for (i = gx1; i <= gx2; i++)
444 for (j = gy1; j <= gy2; j++) {
445 m = RMASK(i, j);
446 if (m > v) RMASK(i, j) = (u_char)v;
447 }
448 }
449 }
450
451 /*--------------------------------------------------------------*/
452 /* setBboxCurrent() --- */
453 /* */
454 /* Alter the net's bounding box information to include the */
455 /* existing bounding box around all net route segments. This */
456 /* allows stage 3 routing to minimize the search area. */
457 /* */
458 /*--------------------------------------------------------------*/
459
setBboxCurrent(NET net)460 void setBboxCurrent(NET net)
461 {
462 ROUTE rt;
463 SEG seg;
464
465 // If net is routed, increase the bounding box to
466 // include the current route solution.
467
468 for (rt = net->routes; rt; rt = rt->next)
469 for (seg = rt->segments; seg; seg = seg->next)
470 {
471 if (seg->x1 < net->xmin) net->xmin = seg->x1;
472 else if (seg->x1 > net->xmax) net->xmax = seg->x1;
473
474 if (seg->x2 < net->xmin) net->xmin = seg->x2;
475 else if (seg->x2 > net->xmax) net->xmax = seg->x2;
476
477 if (seg->y1 < net->ymin) net->ymin = seg->y1;
478 else if (seg->y1 > net->ymax) net->ymax = seg->y1;
479
480 if (seg->y2 < net->ymin) net->ymin = seg->y2;
481 else if (seg->y2 > net->ymax) net->ymax = seg->y2;
482 }
483 }
484
485 /*--------------------------------------------------------------*/
486 /* createBboxMask() --- */
487 /* */
488 /* Create mask limiting the area to search for routing */
489 /* */
490 /* The bounding box mask generates an area including the */
491 /* bounding box as defined in the net record, includes all pin */
492 /* positions in the mask, and increases the mask area by one */
493 /* route track for each pass, up to "halo". */
494 /*--------------------------------------------------------------*/
495
createBboxMask(NET net,u_char halo)496 void createBboxMask(NET net, u_char halo)
497 {
498 int xmin, ymin, xmax, ymax;
499 int i, j, gx1, gy1, gx2, gy2;
500
501 fillMask((u_char)halo);
502
503 xmin = net->xmin;
504 xmax = net->xmax;
505 ymin = net->ymin;
506 ymax = net->ymax;
507
508 for (gx1 = xmin; gx1 <= xmax; gx1++)
509 for (gy1 = ymin; gy1 <= ymax; gy1++)
510 RMASK(gx1, gy1) = (u_char)0;
511
512 for (i = 1; i <= halo; i++) {
513 gx1 = xmin - i;
514 if (gx1 >= 0 && gx1 < NumChannelsX)
515 for (j = ymin - i; j <= ymax + i; j++)
516 if (j >= 0 && j < NumChannelsY)
517 RMASK(gx1, j) = (u_char)i;
518
519 gx2 = xmax + i;
520 if (gx2 >= 0 && gx2 < NumChannelsX)
521 for (j = ymin - i; j <= ymax + i; j++)
522 if (j >= 0 && j < NumChannelsY)
523 RMASK(gx2, j) = (u_char)i;
524
525 gy1 = ymin - i;
526 if (gy1 >= 0 && gy1 < NumChannelsY)
527 for (j = xmin - i; j <= xmax + i; j++)
528 if (j >= 0 && j < NumChannelsX)
529 RMASK(j, gy1) = (u_char)i;
530
531 gy2 = ymax + i;
532 if (gy2 >= 0 && gy2 < NumChannelsY)
533 for (j = xmin - i; j <= xmax + i; j++)
534 if (j >= 0 && j < NumChannelsX)
535 RMASK(j, gy2) = (u_char)i;
536 }
537 }
538
539 /*--------------------------------------------------------------*/
540 /* analyzeCongestion() --- */
541 /* */
542 /* Given a trunk route at ycent, between ymin and ymax, score */
543 /* the neighboring positions as a function of congestion and */
544 /* offset from the ideal location. Return the position of the */
545 /* best location for the trunk route. */
546 /*--------------------------------------------------------------*/
547
analyzeCongestion(int ycent,int ymin,int ymax,int xmin,int xmax)548 int analyzeCongestion(int ycent, int ymin, int ymax, int xmin, int xmax)
549 {
550 int x, y, i, minidx = -1, sidx, n;
551 int *score, minscore;
552
553 score = (int *)malloc((ymax - ymin + 1) * sizeof(int));
554
555 for (y = ymin; y <= ymax; y++) {
556 sidx = y - ymin;
557 score[sidx] = ABSDIFF(ycent, y) * Num_layers;
558 for (x = xmin; x <= xmax; x++) {
559 for (i = 0; i < Num_layers; i++) {
560 n = OBSVAL(x, y, i);
561 if (n & ROUTED_NET) score[sidx]++;
562 if (n & NO_NET) score[sidx]++;
563 if (n & PINOBSTRUCTMASK) score[sidx]++;
564 }
565 }
566 }
567 minscore = MAXRT;
568 for (i = 0; i < (ymax - ymin + 1); i++) {
569 if (score[i] < minscore) {
570 minscore = score[i];
571 minidx = i + ymin;
572 }
573 }
574
575 free(score);
576 return minidx;
577 }
578
579 /*--------------------------------------------------------------*/
580 /* createMask() --- */
581 /* */
582 /* Create mask limiting the area to search for routing */
583 /* */
584 /* For 2-node routes, find the two L-shaped routes between the */
585 /* two closest points of the nodes. */
586 /* For multi-node (>2) routes, find the best trunk line that */
587 /* passes close to all nodes, and generate stems to the closest */
588 /* point on each node. */
589 /* */
590 /* Optimizations: (1) multi-node routes that are in a small */
591 /* enough area, just mask the bounding box. (2) Where nodes */
592 /* at the end of two branches are closer to each other than to */
593 /* the trunk, mask an additional cross-connection between the */
594 /* two branches. */
595 /* */
596 /* Values are "halo" where there is no mask, 0 on the */
597 /* closest "slack" routes to the ideal (typically 1), and */
598 /* values increasing out to a distance of "halo" tracks away */
599 /* from the ideal. This allows a greater search area as the */
600 /* number of passes of the search algorithm increases. */
601 /* */
602 /* To do: Choose the position of trunk line based on */
603 /* congestion analysis. */
604 /*--------------------------------------------------------------*/
605
createMask(NET net,u_char slack,u_char halo)606 void createMask(NET net, u_char slack, u_char halo)
607 {
608 NODE n1, n2;
609 DPOINT dtap;
610 int i, j, orient;
611 int dx, dy, gx1, gx2, gy1, gy2;
612 int xcent, ycent, xmin, ymin, xmax, ymax;
613 int oxmin, oymin, oxmax, oymax;
614
615 fillMask((u_char)halo);
616
617 oxmin = net->xmin;
618 oxmax = net->xmax;
619 oymin = net->ymin;
620 oymax = net->ymax;
621
622 xcent = net->trunkx;
623 ycent = net->trunky;
624
625 orient = 0;
626
627 // Construct the trunk line mask
628
629 if (!(net->flags & NET_VERTICAL_TRUNK) || (net->numnodes == 2)) {
630 // Horizontal trunk
631 orient |= 1;
632
633 ycent = analyzeCongestion(net->trunky, oymin, oymax, oxmin, oxmax);
634 ymin = ymax = ycent;
635 xmin = oxmin;
636 xmax = oxmax;
637
638 // Avoid faulting if the min/max values were never set
639 if (xmin > xmax) {
640 xmin = 0;
641 xmax = NumChannelsX - 1;
642 }
643
644 for (i = xmin - slack; i <= xmax + slack; i++) {
645 if (i < 0 || i >= NumChannelsX) continue;
646 for (j = ycent - slack; j <= ycent + slack; j++) {
647 if (j < 0 || j >= NumChannelsY) continue;
648 RMASK(i, j) = (u_char)0;
649 }
650 }
651
652 for (i = 1; i < halo; i++) {
653 gy1 = ycent - slack - i;
654 gy2 = ycent + slack + i;
655 for (j = xmin - slack - i; j <= xmax + slack + i; j++) {
656 if (j < 0 || j >= NumChannelsX) continue;
657 if (gy1 >= 0)
658 RMASK(j, gy1) = (u_char)i;
659 if (gy2 < NumChannelsY)
660 RMASK(j, gy2) = (u_char)i;
661 }
662 gx1 = xmin - slack - i;
663 gx2 = xmax + slack + i;
664 for (j = ycent - slack - i; j <= ycent + slack + i; j++) {
665 if (j < 0 || j >= NumChannelsY) continue;
666 if (gx1 >= 0)
667 RMASK(gx1, j) = (u_char)i;
668 if (gx2 < NumChannelsX)
669 RMASK(gx2, j) = (u_char)i;
670 }
671 }
672 }
673 if ((net->flags & NET_VERTICAL_TRUNK) || (net->numnodes == 2)) {
674 // Vertical trunk
675 orient |= 2;
676 xmin = xmax = xcent;
677 ymin = oymin;
678 ymax = oymax;
679
680 // Avoid faulting if the min/max values were never set
681 if (ymin > ymax) {
682 ymin = 0;
683 ymax = NumChannelsY - 1;
684 }
685
686 for (i = xcent - slack; i <= xcent + slack; i++) {
687 if (i < 0 || i >= NumChannelsX) continue;
688 for (j = ymin - slack; j <= ymax + slack; j++) {
689 if (j < 0 || j >= NumChannelsY) continue;
690 RMASK(i, j) = (u_char)0;
691 }
692 }
693
694 for (i = 1; i < halo; i++) {
695 gx1 = xcent - slack - i;
696 gx2 = xcent + slack + i;
697 for (j = ymin - slack - i; j <= ymax + slack + i; j++) {
698 if (j < 0 || j >= NumChannelsY) continue;
699 if (gx1 >= 0)
700 RMASK(gx1, j) = (u_char)i;
701 if (gx2 < NumChannelsX)
702 RMASK(gx2, j) = (u_char)i;
703 }
704 gy1 = ymin - slack - i;
705 gy2 = ymax + slack + i;
706 for (j = xcent - slack - i; j <= xcent + slack + i; j++) {
707 if (j < 0 || j >= NumChannelsX) continue;
708 if (gy1 >= 0)
709 RMASK(j, gy1) = (u_char)i;
710 if (gy2 < NumChannelsY)
711 RMASK(j, gy2) = (u_char)i;
712 }
713 }
714 }
715
716 // Construct the branch line masks
717
718 for (n1 = net->netnodes; n1; n1 = n1->next) {
719 dtap = (n1->taps == NULL) ? n1->extend : n1->taps;
720 if (!dtap) continue;
721
722 if (orient & 1) // Horizontal trunk, vertical branches
723 create_vbranch_mask(n1->branchx, n1->branchy, ycent, slack, halo);
724 if (orient & 2) // Vertical trunk, horizontal branches
725 create_hbranch_mask(n1->branchy, n1->branchx, xcent, slack, halo);
726 }
727
728 // Look for branches that are closer to each other than to the
729 // trunk line. If any are found, make a cross-connection between
730 // the branch end that is closer to the trunk and the branch that
731 // is its nearest neighbor.
732
733 if (orient & 1) { // Horizontal trunk, vertical branches
734 for (n1 = net->netnodes; n1; n1 = n1->next) {
735 for (n2 = net->netnodes->next; n2; n2 = n2->next) {
736
737 // Check if both ends are on the same side of the trunk
738 if ((n2->branchy > ycent && n1->branchy > ycent) ||
739 (n2->branchy < ycent && n1->branchy < ycent)) {
740
741 // Check if branches are closer to each other than
742 // the shortest branch is away from the trunk
743 dx = ABSDIFF(n2->branchx, n1->branchx);
744 gy1 = ABSDIFF(n1->branchy, ycent);
745 gy2 = ABSDIFF(n2->branchy, ycent);
746 if ((dx < gy1) && (dx < gy2)) {
747 if (gy1 < gy2)
748 create_hbranch_mask(n1->branchy, n2->branchx,
749 n1->branchx, slack, halo);
750 else
751 create_hbranch_mask(n2->branchy, n2->branchx,
752 n1->branchx, slack, halo);
753 }
754 }
755 }
756 }
757 }
758 if (orient & 2) { // Vertical trunk, horizontal branches
759 for (n1 = net->netnodes; n1; n1 = n1->next) {
760 for (n2 = net->netnodes->next; n2; n2 = n2->next) {
761
762 // Check if both ends are on the same side of the trunk
763 if ((n2->branchx > xcent && n1->branchx > xcent) ||
764 (n2->branchx < xcent && n1->branchx < xcent)) {
765
766 // Check if branches are closer to each other than
767 // the shortest branch is away from the trunk
768 dy = ABSDIFF(n2->branchy, n1->branchy);
769 gx1 = ABSDIFF(n1->branchx, xcent);
770 gx2 = ABSDIFF(n2->branchx, xcent);
771 if ((dy < gx1) && (dy < gx2)) {
772 if (gx1 < gx2)
773 create_vbranch_mask(n1->branchx, n2->branchy,
774 n1->branchy, slack, halo);
775 else
776 create_vbranch_mask(n2->branchx, n2->branchy,
777 n1->branchy, slack, halo);
778 }
779 }
780 }
781 }
782 }
783
784 // Allow routes at all tap and extension points
785 for (n1 = net->netnodes; n1 != NULL; n1 = n1->next) {
786 for (dtap = n1->taps; dtap != NULL; dtap = dtap->next)
787 RMASK(dtap->gridx, dtap->gridy) = (u_char)0;
788 for (dtap = n1->extend; dtap != NULL; dtap = dtap->next)
789 RMASK(dtap->gridx, dtap->gridy) = (u_char)0;
790 }
791
792 if (Verbose > 2) {
793 if (net->numnodes == 2)
794 Fprintf(stdout, "Two-port mask has bounding box (%d %d) to (%d %d)\n",
795 oxmin, oymin, oxmax, oymax);
796 else
797 Fprintf(stdout, "multi-port mask has trunk line (%d %d) to (%d %d)\n",
798 xmin, ymin, xmax, ymax);
799 }
800 }
801
802 /*--------------------------------------------------------------*/
803 /* fillMask() fills the Mask[] array with all 1s as a last */
804 /* resort, ensuring that no valid routes are missed due to a */
805 /* bad guess about the optimal route positions. */
806 /*--------------------------------------------------------------*/
807
fillMask(u_char value)808 void fillMask(u_char value) {
809 memset((void *)RMask, (int)value,
810 (size_t)(NumChannelsX * NumChannelsY
811 * sizeof(u_char)));
812 }
813
814 /* end of mask.c */
815