1 /*!
2 * \file src/autoroute.c
3 *
4 * \brief Functions used to autoroute nets.
5 *
6 * this file, autoroute.c, was written and is
7 *
8 * Copyright (c) 2001 C. Scott Ananian
9 *
10 * Copyright (c) 2006 harry eaton
11 *
12 * Copyright (c) 2009 harry eaton
13 *
14 * This file implements a rectangle-expansion router, based on
15 * "A Method for Gridless Routing of Printed Circuit Boards" by
16 * A. C. Finch, K. J. Mackenzie, G. J. Balsdon, and G. Symonds in the
17 * 1985 Proceedings of the 22nd ACM/IEEE Design Automation Conference.
18 *
19 * This reference is available from the ACM Digital Library at
20 * http://www.acm.org/dl for those with institutional or personal
21 * access to it. It's also available from your local engineering
22 * library.
23 *
24 * The code is much closer to what is described in the paper now,
25 * in that expansion areas can grow from corners and in all directions
26 * at once. Previously, these were emulated with discrete boxes moving
27 * in the cardinal directions. With the new method, there are fewer but
28 * larger expansion boxes that one might do a better job of routing in.
29 *
30 * <hr>
31 *
32 * <h1><b>Copyright.</b></h1>\n
33 *
34 * PCB, interactive printed circuit board design
35 *
36 * Copyright (C) 1994,1995,1996 Thomas Nau
37 *
38 * Copyright (C) 1998,1999,2000,2001 harry eaton
39 *
40 * This program is free software; you can redistribute it and/or modify
41 * it under the terms of the GNU General Public License as published by
42 * the Free Software Foundation; either version 2 of the License, or
43 * (at your option) any later version.
44 *
45 * This program is distributed in the hope that it will be useful,
46 * but WITHOUT ANY WARRANTY; without even the implied warranty of
47 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
48 * GNU General Public License for more details.
49 *
50 * You should have received a copy of the GNU General Public License along
51 * with this program; if not, write to the Free Software Foundation, Inc.,
52 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
53 *
54 * Contact addresses for paper mail and Email:
55 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
56 * haceaton@aplcomm.jhuapl.edu
57 *
58 */
59
60 #define NET_HEAP 1
61 #ifdef HAVE_CONFIG_H
62 #include "config.h"
63 #endif
64
65 #include "global.h"
66
67 #include <assert.h>
68 #include <setjmp.h>
69
70 #include "data.h"
71 #include "macro.h"
72 #include "autoroute.h"
73 #include "box.h"
74 #include "create.h"
75 #include "draw.h"
76 #include "error.h"
77 #include "find.h"
78 #include "flags.h"
79 #include "heap.h"
80 #include "rtree.h"
81 #include "misc.h"
82 #include "mtspace.h"
83 #include "mymem.h"
84 #include "polygon.h"
85 #include "rats.h"
86 #include "remove.h"
87 #include "thermal.h"
88 #include "undo.h"
89 #include "vector.h"
90 #include "pcb-printf.h"
91 #include "hid_draw.h"
92
93 #ifdef HAVE_LIBDMALLOC
94 #include <dmalloc.h>
95 #endif
96
97 /* #defines to enable some debugging output */
98 /*
99 #define ROUTE_VERBOSE
100 */
101
102 /*
103 #define ROUTE_DEBUG
104 //#define DEBUG_SHOW_ROUTE_BOXES
105 #define DEBUG_SHOW_EXPANSION_BOXES
106 //#define DEBUG_SHOW_EDGES
107 //#define DEBUG_SHOW_VIA_BOXES
108 #define DEBUG_SHOW_TARGETS
109 #define DEBUG_SHOW_SOURCES
110 //#define DEBUG_SHOW_ZIGZAG
111 */
112
113 static direction_t
directionIncrement(direction_t dir)114 directionIncrement(direction_t dir)
115 {
116 switch(dir)
117 {
118 case NORTH:
119 dir = EAST;
120 break;
121 case EAST:
122 dir = SOUTH;
123 break;
124 case SOUTH:
125 dir = WEST;
126 break;
127 case WEST:
128 dir = NE;
129 break;
130 case NE:
131 dir = SE;
132 break;
133 case SE:
134 dir = SW;
135 break;
136 case SW:
137 dir = NW;
138 break;
139 case NW:
140 dir = ALL;
141 break;
142 case ALL:
143 dir = NORTH;
144 break;
145 }
146 return dir;
147 }
148
149 #ifdef ROUTE_DEBUG
150 HID_DRAW *ddraw = NULL;
151 static hidGC ar_gc = 0;
152 #endif
153
154 #define EXPENSIVE 3e28
155 /* round up "half" thicknesses */
156 #define HALF_THICK(x) (((x)+1)/2)
157 /* a styles maximum bloat is its keepaway plus the larger of its via radius
158 * or line half-thickness. */
159 #define BLOAT(style)\
160 ((style)->Keepaway + HALF_THICK((style)->Thick))
161 /* conflict penalty is less for traces laid down during previous pass than
162 * it is for traces already laid down in this pass. */
163 #define CONFLICT_LEVEL(rb)\
164 (((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\
165 HI_CONFLICT : LO_CONFLICT )
166 #define CONFLICT_PENALTY(rb)\
167 ((CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
168 AutoRouteParameters.ConflictPenalty : \
169 CONFLICT_LEVEL(rb)==LO_CONFLICT ? \
170 AutoRouteParameters.LastConflictPenalty : 1) * (rb)->pass)
171
172 #define _NORTH 1
173 #define _EAST 2
174 #define _SOUTH 4
175 #define _WEST 8
176
177 #define LIST_LOOP(init, which, x) do {\
178 routebox_t *__next_one__ = (init);\
179 x = NULL;\
180 if (!__next_one__)\
181 assert(__next_one__);\
182 else\
183 while (!x || __next_one__ != (init)) {\
184 x = __next_one__;\
185 /* save next one first in case the command modifies or frees it */\
186 __next_one__ = x->which.next
187 #define FOREACH_SUBNET(net, p) do {\
188 routebox_t *_pp_;\
189 /* fail-fast: check subnet_processed flags */\
190 LIST_LOOP(net, same_net, p); \
191 assert(!p->flags.subnet_processed);\
192 END_LOOP;\
193 /* iterate through *distinct* subnets */\
194 LIST_LOOP(net, same_net, p); \
195 if (!p->flags.subnet_processed) {\
196 LIST_LOOP(p, same_subnet, _pp_);\
197 _pp_->flags.subnet_processed=1;\
198 END_LOOP
199 #define END_FOREACH(net, p) \
200 }; \
201 END_LOOP;\
202 /* reset subnet_processed flags */\
203 LIST_LOOP(net, same_net, p); \
204 p->flags.subnet_processed=0;\
205 END_LOOP;\
206 } while (0)
207 #define SWAP(t, f, s) do { t a=s; s=f; f=a; } while (0)
208 /* notes:
209 * all rectangles are assumed to be closed on the top and left and
210 * open on the bottom and right. That is, they include their top-left
211 * corner but don't include their bottom and right edges.
212 *
213 * expansion regions are always half-closed. This means that when
214 * tracing paths, you must steer clear of the bottom and right edges.,
215 * because these are not actually in the allowed box.
216 *
217 * All routeboxes *except* EXPANSION_AREAS now have their "box" bloated by
218 * their particular required keepaway. This simplifies the tree searching.
219 * the "sbox" contains the unbloated box.
220 */
221 /* ---------------------------------------------------------------------------
222 * some local types
223 */
224
225 /* enumerated type for conflict levels */
226 typedef enum
227 { NO_CONFLICT = 0, LO_CONFLICT = 1, HI_CONFLICT = 2 }
228 conflict_t;
229
230 typedef struct routebox_list
231 {
232 struct routebox *next, *prev;
233 }routebox_list;
234
235 typedef enum etype
236 { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE, THERMAL }
237 etype;
238
239 typedef struct routebox
240 {
241 BoxType box, sbox;
242 union
243 {
244 PadType *pad;
245 PinType *pin;
246 PinType *via;
247 struct routebox *via_shadow; /* points to the via in r-tree which
248 * points to the PinType in the PCB. */
249 LineType *line;
250 void *generic; /* 'other' is polygon, arc, text */
251 struct routebox *expansion_area; /* previous expansion area in search */
252 }
253 parent;
254 unsigned short group;
255 unsigned short layer;
256 etype type;
257 struct
258 {
259 unsigned nonstraight:1;
260 unsigned fixed:1;
261 /* for searches */
262 unsigned source:1;
263 unsigned target:1;
264 /* rects on same net as source and target don't need clearance areas */
265 unsigned nobloat:1;
266 /* mark circular pins, so that we be sure to connect them up properly */
267 unsigned circular:1;
268 /* we sometimes create routeboxen that don't actually belong to a
269 * r-tree yet -- make sure refcount of homelesss is set properly */
270 unsigned homeless:1;
271 /* was this nonfixed obstacle generated on an odd or even pass? */
272 unsigned is_odd:1;
273 /* fixed route boxes that have already been "routed through" in this
274 * search have their "touched" flag set. */
275 unsigned touched:1;
276 /* this is a status bit for iterating through *different* subnets */
277 unsigned subnet_processed:1;
278 /* some expansion_areas represent via candidates */
279 unsigned is_via:1;
280 /* mark non-straight lines which go from bottom-left to upper-right,
281 * instead of from upper-left to bottom-right. */
282 unsigned bl_to_ur:1;
283 /* mark polygons which are "transparent" for via-placement; that is,
284 * vias through the polygon will automatically be given a keepaway
285 * and will not electrically connect to the polygon. */
286 unsigned clear_poly:1;
287 /* this marks "conflicting" routes that must be torn up to obtain
288 * a correct routing. This flag allows us to return a correct routing
289 * even if the user cancels auto-route after a non-final pass. */
290 unsigned is_bad:1;
291 /* for assertion that 'box' is never changed after creation */
292 unsigned inited:1;
293 /* indicate this expansion ares is a thermal between the pin and plane */
294 unsigned is_thermal;
295 }
296 flags;
297 /* indicate the direction an expansion box came from */
298 cost_t cost;
299 CheapPointType cost_point;
300 /* reference count for homeless routeboxes; free when refcount==0 */
301 int refcount;
302 /* when routing with conflicts, we keep a record of what we're
303 * conflicting with.
304 */
305 vector_t *conflicts_with;
306 /* route style of the net associated with this routebox */
307 RouteStyleType *style;
308 /* congestion values for the edges of an expansion box */
309 unsigned char n, e, s, w;
310 /* what pass this this track was laid down on */
311 unsigned char pass;
312 /* the direction this came from, if any */
313 direction_t came_from;
314 /* circular lists with connectivity information. */
315 routebox_list same_net, same_subnet, original_subnet, different_net;
316 union {
317 PinType *via;
318 LineType *line;
319 } livedraw_obj;
320 }
321 routebox_t;
322
323 typedef struct routedata
324 {
325 /* one rtree per layer *group */
326 rtree_t *layergrouptree[MAX_GROUP]; /* no silkscreen layers here =) */
327 /* root pointer into connectivity information */
328 routebox_t *first_net;
329 /* default routing style */
330 RouteStyleType defaultstyle;
331 /* style structures */
332 RouteStyleType *styles[NUM_STYLES + 1];
333 /* what is the maximum bloat (keepaway+line half-width or
334 * keepaway+via_radius) for any style we've seen? */
335 Coord max_bloat;
336 Coord max_keep;
337 mtspace_t *mtspace;
338 }
339 routedata_t;
340
341 typedef struct edge_struct
342 {
343 routebox_t *rb; /* path expansion edges are real routeboxen. */
344 CheapPointType cost_point;
345 cost_t cost_to_point; /* from source */
346 cost_t cost; /* cached edge cost */
347 routebox_t *mincost_target; /* minimum cost from cost_point to any target */
348 vetting_t *work; /* for via search edges */
349 direction_t expand_dir;
350 struct
351 {
352 /* this indicates that this 'edge' is a via candidate. */
353 unsigned is_via:1;
354 /* record "conflict level" of via candidates, in case we need to split
355 * them later. */
356 conflict_t via_conflict_level:2;
357 /* when "routing with conflicts", sometimes edge is interior. */
358 unsigned is_interior:1;
359 /* this is a fake edge used to defer searching for via spaces */
360 unsigned via_search:1;
361 /* this is a via edge in a plane where the cost point moves for free */
362 unsigned in_plane:1;
363 }
364 flags;
365 }
366 edge_t;
367
368 static struct
369 {
370 /* net style parameters */
371 RouteStyleType *style;
372 /* the present bloat */
373 Coord bloat;
374 /* cost parameters */
375 cost_t ViaCost, /* additional "length" cost for using a via */
376 LastConflictPenalty, /* length mult. for routing over last pass' trace */
377 ConflictPenalty, /* length multiplier for routing over another trace */
378 JogPenalty, /* additional "length" cost for changing direction */
379 CongestionPenalty, /* (rational) length multiplier for routing in */
380 NewLayerPenalty, /* penalty for routing on a previously unused layer */
381 MinPenalty; /* smallest Direction Penalty */
382 /* maximum conflict incidence before calling it "no path found" */
383 int hi_conflict;
384 /* are vias allowed? */
385 bool use_vias;
386 /* is this an odd or even pass? */
387 bool is_odd;
388 /* permit conflicts? */
389 bool with_conflicts;
390 /* is this a final "smoothing" pass? */
391 bool is_smoothing;
392 /* rip up nets regardless of conflicts? */
393 bool rip_always;
394 bool last_smooth;
395 unsigned char pass;
396 }
397 AutoRouteParameters;
398
399 struct routeone_state
400 {
401 /* heap of all candidate expansion edges */
402 heap_t *workheap;
403 /* information about the best path found so far. */
404 routebox_t *best_path, *best_target;
405 cost_t best_cost;
406 };
407
408
409 /* ---------------------------------------------------------------------------
410 * some local prototypes
411 */
412 static routebox_t *CreateExpansionArea (const BoxType * area, Cardinal group,
413 routebox_t * parent,
414 bool relax_edge_requirements,
415 edge_t * edge);
416
417 static cost_t edge_cost (const edge_t * e, const cost_t too_big);
418 static void best_path_candidate (struct routeone_state *s,
419 edge_t * e, routebox_t * best_target);
420
421 static BoxType edge_to_box (const routebox_t * rb, direction_t expand_dir);
422
423 static void add_or_destroy_edge (struct routeone_state *s, edge_t * e);
424
425 static void
426 RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
427 Cardinal group, Cardinal layer, routebox_t * subnet,
428 bool is_bad);
429 static void ResetSubnet (routebox_t * net);
430 #ifdef ROUTE_DEBUG
431 static int showboxen = -2;
432 static int aabort = 0;
433 static void showroutebox (routebox_t * rb);
434 #endif
435
436 /* ---------------------------------------------------------------------------
437 * some local identifiers
438 */
439 /* group number of groups that hold surface mount pads */
440 static Cardinal front, back;
441 static bool usedGroup[MAX_GROUP];
442 static int x_cost[MAX_GROUP], y_cost[MAX_GROUP];
443 static bool is_layer_group_active[MAX_GROUP];
444 static int ro = 0;
445 static int smoothes = 1;
446 static int passes = 12;
447 static int routing_layers = 0;
448 static float total_wire_length = 0;
449 static int total_via_count = 0;
450
451 /* assertion helper for routeboxen */
452 #ifndef NDEBUG
453 static int
__routebox_is_good(routebox_t * rb)454 __routebox_is_good (routebox_t * rb)
455 {
456 assert (rb && (rb->group < max_group) &&
457 (rb->box.X1 <= rb->box.X2) && (rb->box.Y1 <= rb->box.Y2) &&
458 (rb->flags.homeless ?
459 (rb->box.X1 != rb->box.X2) || (rb->box.Y1 != rb->box.Y2) :
460 (rb->box.X1 != rb->box.X2) && (rb->box.Y1 != rb->box.Y2)));
461 assert ((rb->flags.source ? rb->flags.nobloat : 1) &&
462 (rb->flags.target ? rb->flags.nobloat : 1) &&
463 (rb->flags.homeless ? !rb->flags.touched : rb->refcount == 0) &&
464 (rb->flags.touched ? rb->type != EXPANSION_AREA : 1));
465 assert ((rb->flags.is_odd ? (!rb->flags.fixed) &&
466 (rb->type == VIA || rb->type == VIA_SHADOW || rb->type == LINE
467 || rb->type == PLANE) : 1));
468 assert (rb->flags.clear_poly ?
469 ((rb->type == OTHER || rb->type == PLANE) && rb->flags.fixed
470 && !rb->flags.homeless) : 1);
471 assert (rb->flags.inited);
472 /* run through conflict list showing none are homeless, targets or sources */
473 if (rb->conflicts_with)
474 {
475 int i;
476 for (i = 0; i < vector_size (rb->conflicts_with); i++)
477 {
478 routebox_t *c = vector_element (rb->conflicts_with, i);
479 assert (!c->flags.homeless && !c->flags.source && !c->flags.target
480 && !c->flags.fixed);
481 }
482 }
483 assert (rb->style != NULL && rb->style != NULL);
484 assert (rb->type == EXPANSION_AREA
485 || (rb->same_net.next && rb->same_net.prev && rb->same_subnet.next
486 && rb->same_subnet.prev && rb->original_subnet.next
487 && rb->original_subnet.prev && rb->different_net.next
488 && rb->different_net.prev));
489 return 1;
490 }
491 static int
__edge_is_good(edge_t * e)492 __edge_is_good (edge_t * e)
493 {
494 assert (e && e->rb && __routebox_is_good (e->rb));
495 assert ((e->rb->flags.homeless ? e->rb->refcount > 0 : 1));
496 assert ((0 <= e->expand_dir) && (e->expand_dir < 9)
497 && (e->flags.
498 is_interior ? (e->expand_dir == ALL
499 && e->rb->conflicts_with) : 1));
500 assert ((e->flags.is_via ? e->rb->flags.is_via : 1)
501 && (e->flags.via_conflict_level >= 0
502 && e->flags.via_conflict_level <= 2)
503 && (e->flags.via_conflict_level != 0 ? e->flags.is_via : 1));
504 assert ((e->cost_to_point >= 0) && e->cost >= 0);
505 return 1;
506 }
507
508 int
no_planes(const BoxType * b,void * cl)509 no_planes (const BoxType * b, void *cl)
510 {
511 routebox_t *rb = (routebox_t *) b;
512 if (rb->type == PLANE)
513 return 0;
514 return 1;
515 }
516 #endif /* !NDEBUG */
517
518 /*---------------------------------------------------------------------
519 * route utility functions.
520 */
521
522 enum boxlist
523 { NET, SUBNET, ORIGINAL, DIFFERENT_NET };
524 static struct routebox_list *
__select_list(routebox_t * r,enum boxlist which)525 __select_list (routebox_t * r, enum boxlist which)
526 {
527 assert (r);
528 switch (which)
529 {
530 default:
531 assert (0);
532 case NET:
533 return &(r->same_net);
534 case SUBNET:
535 return &(r->same_subnet);
536 case ORIGINAL:
537 return &(r->original_subnet);
538 case DIFFERENT_NET:
539 return &(r->different_net);
540 }
541 }
542 static void
InitLists(routebox_t * r)543 InitLists (routebox_t * r)
544 {
545 static enum boxlist all[] =
546 { NET, SUBNET, ORIGINAL, DIFFERENT_NET }
547 , *p;
548 for (p = all; p < all + (sizeof (all) / sizeof (*p)); p++)
549 {
550 struct routebox_list *rl = __select_list (r, *p);
551 rl->prev = rl->next = r;
552 }
553 }
554
555 static void
MergeNets(routebox_t * a,routebox_t * b,enum boxlist which)556 MergeNets (routebox_t * a, routebox_t * b, enum boxlist which)
557 {
558 struct routebox_list *al, *bl, *anl, *bnl;
559 routebox_t *an, *bn;
560 assert (a && b);
561 assert (a != b);
562 assert (a->type != EXPANSION_AREA);
563 assert (b->type != EXPANSION_AREA);
564 al = __select_list (a, which);
565 bl = __select_list (b, which);
566 assert (al && bl);
567 an = al->next;
568 bn = bl->next;
569 assert (an && bn);
570 anl = __select_list (an, which);
571 bnl = __select_list (bn, which);
572 assert (anl && bnl);
573 bl->next = an;
574 anl->prev = b;
575 al->next = bn;
576 bnl->prev = a;
577 }
578
579 static void
RemoveFromNet(routebox_t * a,enum boxlist which)580 RemoveFromNet (routebox_t * a, enum boxlist which)
581 {
582 struct routebox_list *al, *anl, *apl;
583 routebox_t *an, *ap;
584 assert (a);
585 al = __select_list (a, which);
586 assert (al);
587 an = al->next;
588 ap = al->prev;
589 if (an == a || ap == a)
590 return; /* not on any list */
591 assert (an && ap);
592 anl = __select_list (an, which);
593 apl = __select_list (ap, which);
594 assert (anl && apl);
595 anl->prev = ap;
596 apl->next = an;
597 al->next = al->prev = a;
598 return;
599 }
600
601 static void
init_const_box(routebox_t * rb,Coord X1,Coord Y1,Coord X2,Coord Y2,Coord keepaway)602 init_const_box (routebox_t * rb,
603 Coord X1, Coord Y1, Coord X2,
604 Coord Y2, Coord keepaway)
605 {
606 BoxType *bp = (BoxType *) & rb->box; /* note discarding const! */
607 assert (!rb->flags.inited);
608 assert (X1 <= X2 && Y1 <= Y2);
609 bp->X1 = X1 - keepaway;
610 bp->Y1 = Y1 - keepaway;
611 bp->X2 = X2 + keepaway;
612 bp->Y2 = Y2 + keepaway;
613 bp = (BoxType *) & rb->sbox;
614 bp->X1 = X1;
615 bp->Y1 = Y1;
616 bp->X2 = X2;
617 bp->Y2 = Y2;
618 rb->flags.inited = 1;
619 }
620
621 static inline BoxType
shrink_routebox(const routebox_t * rb)622 shrink_routebox (const routebox_t * rb)
623 {
624 return rb->sbox;
625 }
626
627 static inline cost_t
box_area(const BoxType b)628 box_area (const BoxType b)
629 {
630 cost_t ans = b.X2 - b.X1;
631 return ans * (b.Y2 - b.Y1);
632 }
633
634 static inline CheapPointType
closest_point_in_routebox(const CheapPointType * from,const routebox_t * rb)635 closest_point_in_routebox (const CheapPointType * from, const routebox_t * rb)
636 {
637 return closest_point_in_box (from, &rb->sbox);
638 }
639
640 static inline bool
point_in_shrunk_box(const routebox_t * box,Coord X,Coord Y)641 point_in_shrunk_box (const routebox_t * box, Coord X, Coord Y)
642 {
643 BoxType b = shrink_routebox (box);
644 return point_in_box (&b, X, Y);
645 }
646
647 /*---------------------------------------------------------------------
648 * routedata initialization functions.
649 */
650
651 static routebox_t *
AddPin(PointerListType layergroupboxes[],PinType * pin,bool is_via,RouteStyleType * style)652 AddPin (PointerListType layergroupboxes[], PinType *pin, bool is_via,
653 RouteStyleType * style)
654 {
655 routebox_t **rbpp, *lastrb = NULL;
656 int i, ht;
657 /* a pin cuts through every layer group */
658 for (i = 0; i < max_group; i++)
659 {
660 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[i]);
661 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
662 memset ((void *) *rbpp, 0, sizeof (**rbpp));
663 (*rbpp)->group = i;
664 ht = HALF_THICK (MAX (pin->Thickness, pin->DrillingHole));
665 init_const_box (*rbpp,
666 /*X1 */ pin->X - ht,
667 /*Y1 */ pin->Y - ht,
668 /*X2 */ pin->X + ht,
669 /*Y2 */ pin->Y + ht, style->Keepaway);
670 /* set aux. properties */
671 if (is_via)
672 {
673 (*rbpp)->type = VIA;
674 (*rbpp)->parent.via = pin;
675 }
676 else
677 {
678 (*rbpp)->type = PIN;
679 (*rbpp)->parent.pin = pin;
680 }
681 (*rbpp)->flags.fixed = 1;
682 (*rbpp)->came_from = ALL;
683 (*rbpp)->style = style;
684 (*rbpp)->flags.circular = !TEST_FLAG (SQUAREFLAG, pin);
685 /* circular lists */
686 InitLists (*rbpp);
687 /* link together */
688 if (lastrb)
689 {
690 MergeNets (*rbpp, lastrb, NET);
691 MergeNets (*rbpp, lastrb, SUBNET);
692 MergeNets (*rbpp, lastrb, ORIGINAL);
693 }
694 lastrb = *rbpp;
695 }
696 return lastrb;
697 }
698 static routebox_t *
AddPad(PointerListType layergroupboxes[],ElementType * element,PadType * pad,RouteStyleType * style)699 AddPad (PointerListType layergroupboxes[],
700 ElementType *element, PadType *pad, RouteStyleType * style)
701 {
702 Coord halfthick;
703 routebox_t **rbpp;
704 int layergroup = (TEST_FLAG (ONSOLDERFLAG, pad) ? back : front);
705 assert (0 <= layergroup && layergroup < max_group);
706 assert (PCB->LayerGroups.Number[layergroup] > 0);
707 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
708 assert (rbpp);
709 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
710 assert (*rbpp);
711 memset (*rbpp, 0, sizeof (**rbpp));
712 (*rbpp)->group = layergroup;
713 halfthick = HALF_THICK (pad->Thickness);
714 init_const_box (*rbpp,
715 /*X1 */ MIN (pad->Point1.X, pad->Point2.X) - halfthick,
716 /*Y1 */ MIN (pad->Point1.Y, pad->Point2.Y) - halfthick,
717 /*X2 */ MAX (pad->Point1.X, pad->Point2.X) + halfthick,
718 /*Y2 */ MAX (pad->Point1.Y, pad->Point2.Y) + halfthick,
719 style->Keepaway);
720 /* kludge for non-manhattan pads (which are not allowed at present) */
721 if (pad->Point1.X != pad->Point2.X && pad->Point1.Y != pad->Point2.Y)
722 (*rbpp)->flags.nonstraight = 1;
723 /* set aux. properties */
724 (*rbpp)->type = PAD;
725 (*rbpp)->parent.pad = pad;
726 (*rbpp)->flags.fixed = 1;
727 (*rbpp)->came_from = ALL;
728 (*rbpp)->style = style;
729 /* circular lists */
730 InitLists (*rbpp);
731 return *rbpp;
732 }
733 static routebox_t *
AddLine(PointerListType layergroupboxes[],int layergroup,LineType * line,LineType * ptr,RouteStyleType * style)734 AddLine (PointerListType layergroupboxes[], int layergroup, LineType *line,
735 LineType *ptr, RouteStyleType * style)
736 {
737 routebox_t **rbpp;
738 assert (layergroupboxes && line);
739 assert (0 <= layergroup && layergroup < max_group);
740 assert (PCB->LayerGroups.Number[layergroup] > 0);
741
742 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
743 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
744 memset (*rbpp, 0, sizeof (**rbpp));
745 (*rbpp)->group = layergroup;
746 init_const_box (*rbpp,
747 /*X1 */ MIN (line->Point1.X,
748 line->Point2.X) - HALF_THICK (line->Thickness),
749 /*Y1 */ MIN (line->Point1.Y,
750 line->Point2.Y) - HALF_THICK (line->Thickness),
751 /*X2 */ MAX (line->Point1.X,
752 line->Point2.X) + HALF_THICK (line->Thickness),
753 /*Y2 */ MAX (line->Point1.Y,
754 line->Point2.Y) +
755 HALF_THICK (line->Thickness), style->Keepaway);
756 /* kludge for non-manhattan lines */
757 if (line->Point1.X != line->Point2.X && line->Point1.Y != line->Point2.Y)
758 {
759 (*rbpp)->flags.nonstraight = 1;
760 (*rbpp)->flags.bl_to_ur =
761 (MIN (line->Point1.X, line->Point2.X) == line->Point1.X) !=
762 (MIN (line->Point1.Y, line->Point2.Y) == line->Point1.Y);
763 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ZIGZAG)
764 showroutebox (*rbpp);
765 #endif
766 }
767 /* set aux. properties */
768 (*rbpp)->type = LINE;
769 (*rbpp)->parent.line = ptr;
770 (*rbpp)->flags.fixed = 1;
771 (*rbpp)->came_from = ALL;
772 (*rbpp)->style = style;
773 /* circular lists */
774 InitLists (*rbpp);
775 return *rbpp;
776 }
777 static routebox_t *
AddIrregularObstacle(PointerListType layergroupboxes[],Coord X1,Coord Y1,Coord X2,Coord Y2,Cardinal layergroup,void * parent,RouteStyleType * style)778 AddIrregularObstacle (PointerListType layergroupboxes[],
779 Coord X1, Coord Y1,
780 Coord X2, Coord Y2, Cardinal layergroup,
781 void *parent, RouteStyleType * style)
782 {
783 routebox_t **rbpp;
784 Coord keep = style->Keepaway;
785 assert (layergroupboxes && parent);
786 assert (X1 <= X2 && Y1 <= Y2);
787 assert (0 <= layergroup && layergroup < max_group);
788 assert (PCB->LayerGroups.Number[layergroup] > 0);
789
790 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
791 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
792 memset (*rbpp, 0, sizeof (**rbpp));
793 (*rbpp)->group = layergroup;
794 init_const_box (*rbpp, X1, Y1, X2, Y2, keep);
795 (*rbpp)->flags.nonstraight = 1;
796 (*rbpp)->type = OTHER;
797 (*rbpp)->parent.generic = parent;
798 (*rbpp)->flags.fixed = 1;
799 (*rbpp)->style = style;
800 /* circular lists */
801 InitLists (*rbpp);
802 return *rbpp;
803 }
804
805 static routebox_t *
AddPolygon(PointerListType layergroupboxes[],Cardinal layer,PolygonType * polygon,RouteStyleType * style)806 AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
807 PolygonType *polygon, RouteStyleType * style)
808 {
809 int is_not_rectangle = 1;
810 int layergroup = GetLayerGroupNumberByNumber (layer);
811 routebox_t *rb;
812 assert (0 <= layergroup && layergroup < max_group);
813 rb = AddIrregularObstacle (layergroupboxes,
814 polygon->BoundingBox.X1,
815 polygon->BoundingBox.Y1,
816 polygon->BoundingBox.X2,
817 polygon->BoundingBox.Y2,
818 layergroup, polygon, style);
819 if (polygon->PointN == 4 &&
820 polygon->HoleIndexN == 0 &&
821 (polygon->Points[0].X == polygon->Points[1].X ||
822 polygon->Points[0].Y == polygon->Points[1].Y) &&
823 (polygon->Points[1].X == polygon->Points[2].X ||
824 polygon->Points[1].Y == polygon->Points[2].Y) &&
825 (polygon->Points[2].X == polygon->Points[3].X ||
826 polygon->Points[2].Y == polygon->Points[3].Y) &&
827 (polygon->Points[3].X == polygon->Points[0].X ||
828 polygon->Points[3].Y == polygon->Points[0].Y))
829 is_not_rectangle = 0;
830 rb->flags.nonstraight = is_not_rectangle;
831 rb->layer = layer;
832 rb->came_from = ALL;
833 if (TEST_FLAG (CLEARPOLYFLAG, polygon))
834 {
835 rb->flags.clear_poly = 1;
836 if (!is_not_rectangle)
837 rb->type = PLANE;
838 }
839 return rb;
840 }
841 static void
AddText(PointerListType layergroupboxes[],Cardinal layergroup,TextType * text,RouteStyleType * style)842 AddText (PointerListType layergroupboxes[], Cardinal layergroup,
843 TextType *text, RouteStyleType * style)
844 {
845 AddIrregularObstacle (layergroupboxes,
846 text->BoundingBox.X1, text->BoundingBox.Y1,
847 text->BoundingBox.X2, text->BoundingBox.Y2,
848 layergroup, text, style);
849 }
850 static routebox_t *
AddArc(PointerListType layergroupboxes[],Cardinal layergroup,ArcType * arc,RouteStyleType * style)851 AddArc (PointerListType layergroupboxes[], Cardinal layergroup,
852 ArcType *arc, RouteStyleType * style)
853 {
854 return AddIrregularObstacle (layergroupboxes,
855 arc->BoundingBox.X1, arc->BoundingBox.Y1,
856 arc->BoundingBox.X2, arc->BoundingBox.Y2,
857 layergroup, arc, style);
858 }
859
860 struct rb_info
861 {
862 BoxType query;
863 routebox_t *winner;
864 jmp_buf env;
865 };
866
867 static int
__found_one_on_lg(const BoxType * box,void * cl)868 __found_one_on_lg (const BoxType * box, void *cl)
869 {
870 struct rb_info *inf = (struct rb_info *) cl;
871 routebox_t *rb = (routebox_t *) box;
872 BoxType sb;
873
874 if (rb->flags.nonstraight)
875 return 0;
876 sb = shrink_box (&rb->box, rb->style->Keepaway);
877 if (inf->query.X1 >= sb.X2 || inf->query.X2 <= sb.X1 ||
878 inf->query.Y1 >= sb.Y2 || inf->query.Y2 <= sb.Y1)
879 return 0;
880 inf->winner = rb;
881 if (rb->type == PLANE)
882 return 1; /* keep looking for something smaller if a plane was found */
883 longjmp (inf->env, 1);
884 return 0;
885 }
886 static routebox_t *
FindRouteBoxOnLayerGroup(routedata_t * rd,Coord X,Coord Y,Cardinal layergroup)887 FindRouteBoxOnLayerGroup (routedata_t * rd,
888 Coord X, Coord Y, Cardinal layergroup)
889 {
890 struct rb_info info;
891 info.winner = NULL;
892 info.query = point_box (X, Y);
893 if (setjmp (info.env) == 0)
894 r_search (rd->layergrouptree[layergroup], &info.query, NULL,
895 __found_one_on_lg, &info);
896 return info.winner;
897 }
898
899 #ifdef ROUTE_DEBUG_VERBOSE
900 static void
DumpRouteBox(routebox_t * rb)901 DumpRouteBox (routebox_t * rb)
902 {
903 pcb_printf ("RB: %#mD-%#mD l%d; ",
904 rb->box.X1, rb->box.Y1, rb->box.X2, rb->box.Y2, (int) rb->group);
905 switch (rb->type)
906 {
907 case PAD:
908 printf ("PAD[%s %s] ", rb->parent.pad->Name, rb->parent.pad->Number);
909 break;
910 case PIN:
911 printf ("PIN[%s %s] ", rb->parent.pin->Name, rb->parent.pin->Number);
912 break;
913 case VIA:
914 if (!rb->parent.via)
915 break;
916 printf ("VIA[%s %s] ", rb->parent.via->Name, rb->parent.via->Number);
917 break;
918 case LINE:
919 printf ("LINE ");
920 break;
921 case OTHER:
922 printf ("OTHER ");
923 break;
924 case EXPANSION_AREA:
925 printf ("EXPAREA ");
926 break;
927 default:
928 printf ("UNKNOWN ");
929 break;
930 }
931 if (rb->flags.nonstraight)
932 printf ("(nonstraight) ");
933 if (rb->flags.fixed)
934 printf ("(fixed) ");
935 if (rb->flags.source)
936 printf ("(source) ");
937 if (rb->flags.target)
938 printf ("(target) ");
939 if (rb->flags.homeless)
940 printf ("(homeless) ");
941 printf ("\n");
942 }
943 #endif
944
945 static routedata_t *
CreateRouteData()946 CreateRouteData ()
947 {
948 NetListListType Nets;
949 PointerListType layergroupboxes[MAX_GROUP];
950 BoxType bbox;
951 routedata_t *rd;
952 int group, i;
953
954 /* check which layers are active first */
955 routing_layers = 0;
956 for (group = 0; group < max_group; group++)
957 {
958 for (i = 0; i < PCB->LayerGroups.Number[group]; i++)
959 /* layer must be 1) not silk (ie, < max_copper_layer) and 2) on */
960 if ((PCB->LayerGroups.Entries[group][i] < max_copper_layer) &&
961 PCB->Data->Layer[PCB->LayerGroups.Entries[group][i]].On)
962 {
963 routing_layers++;
964 is_layer_group_active[group] = true;
965 break;
966 }
967 else
968 is_layer_group_active[group] = false;
969 }
970 /* if via visibility is turned off, don't use them */
971 AutoRouteParameters.use_vias = routing_layers > 1 && PCB->ViaOn;
972 front = GetLayerGroupNumberBySide (TOP_SIDE);
973 back = GetLayerGroupNumberBySide (BOTTOM_SIDE);
974 /* determine preferred routing direction on each group */
975 for (i = 0; i < max_group; i++)
976 {
977 if (i != back && i != front)
978 {
979 x_cost[i] = (i & 1) ? 2 : 1;
980 y_cost[i] = (i & 1) ? 1 : 2;
981 }
982 else if (i == back)
983 {
984 x_cost[i] = 4;
985 y_cost[i] = 2;
986 }
987 else
988 {
989 x_cost[i] = 2;
990 y_cost[i] = 2;
991 }
992 }
993 /* create routedata */
994 rd = (routedata_t *)malloc (sizeof (*rd));
995 memset ((void *) rd, 0, sizeof (*rd));
996 /* create default style */
997 rd->defaultstyle.Thick = Settings.LineThickness;
998 rd->defaultstyle.Diameter = Settings.ViaThickness;
999 rd->defaultstyle.Hole = Settings.ViaDrillingHole;
1000 rd->defaultstyle.Keepaway = Settings.Keepaway;
1001 rd->max_bloat = BLOAT (&rd->defaultstyle);
1002 rd->max_keep = Settings.Keepaway;
1003 /* create styles structures */
1004 bbox.X1 = bbox.Y1 = 0;
1005 bbox.X2 = PCB->MaxWidth;
1006 bbox.Y2 = PCB->MaxHeight;
1007 for (i = 0; i < NUM_STYLES + 1; i++)
1008 {
1009 RouteStyleType *style =
1010 (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultstyle;
1011 rd->styles[i] = style;
1012 }
1013
1014 /* initialize pointerlisttype */
1015 for (i = 0; i < max_group; i++)
1016 {
1017 layergroupboxes[i].Ptr = NULL;
1018 layergroupboxes[i].PtrN = 0;
1019 layergroupboxes[i].PtrMax = 0;
1020 GROUP_LOOP (PCB->Data, i);
1021 {
1022 if (layer->LineN || layer->ArcN)
1023 usedGroup[i] = true;
1024 else
1025 usedGroup[i] = false;
1026 }
1027 END_LOOP;
1028 }
1029 usedGroup[front] = true;
1030 usedGroup[back] = true;
1031 /* add the objects in the netlist first.
1032 * then go and add all other objects that weren't already added
1033 *
1034 * this saves on searching the trees to find the nets
1035 */
1036 /* use the DRCFLAG to mark objects as they are entered */
1037 Nets = CollectSubnets (false);
1038 {
1039 routebox_t *last_net = NULL;
1040 NETLIST_LOOP (&Nets);
1041 {
1042 routebox_t *last_in_net = NULL;
1043 NET_LOOP (netlist);
1044 {
1045 routebox_t *last_in_subnet = NULL;
1046 int j;
1047
1048 for (j = 0; j < NUM_STYLES; j++)
1049 if (net->Style == rd->styles[j])
1050 break;
1051 CONNECTION_LOOP (net);
1052 {
1053 routebox_t *rb = NULL;
1054 SET_FLAG (DRCFLAG, (PinType *) connection->ptr2);
1055 if (connection->type == LINE_TYPE)
1056 {
1057 LineType *line = (LineType *) connection->ptr2;
1058
1059 /* lines are listed at each end, so skip one */
1060 /* this should probably by a macro named "BUMP_LOOP" */
1061 n--;
1062
1063 /* dice up non-straight lines into many tiny obstacles */
1064 if (line->Point1.X != line->Point2.X
1065 && line->Point1.Y != line->Point2.Y)
1066 {
1067 LineType fake_line = *line;
1068 Coord dx = (line->Point2.X - line->Point1.X);
1069 Coord dy = (line->Point2.Y - line->Point1.Y);
1070 int segs = MAX (ABS (dx),
1071 ABS (dy)) / (4 * BLOAT (rd->styles[j]) + 1);
1072 int qq;
1073 segs = CLAMP (segs, 1, 32); /* don't go too crazy */
1074 dx /= segs;
1075 dy /= segs;
1076 for (qq = 0; qq < segs - 1; qq++)
1077 {
1078 fake_line.Point2.X = fake_line.Point1.X + dx;
1079 fake_line.Point2.Y = fake_line.Point1.Y + dy;
1080 if (fake_line.Point2.X == line->Point2.X
1081 && fake_line.Point2.Y == line->Point2.Y)
1082 break;
1083 rb =
1084 AddLine (layergroupboxes, connection->group,
1085 &fake_line, line, rd->styles[j]);
1086 if (last_in_subnet && rb != last_in_subnet)
1087 MergeNets (last_in_subnet, rb, ORIGINAL);
1088 if (last_in_net && rb != last_in_net)
1089 MergeNets (last_in_net, rb, NET);
1090 last_in_subnet = last_in_net = rb;
1091 fake_line.Point1 = fake_line.Point2;
1092 }
1093 fake_line.Point2 = line->Point2;
1094 rb =
1095 AddLine (layergroupboxes, connection->group, &fake_line,
1096 line, rd->styles[j]);
1097 }
1098 else
1099 {
1100 rb =
1101 AddLine (layergroupboxes, connection->group, line, line,
1102 rd->styles[j]);
1103 }
1104 }
1105 else
1106 switch (connection->type)
1107 {
1108 case PAD_TYPE:
1109 rb =
1110 AddPad (layergroupboxes, (ElementType *)connection->ptr1,
1111 (PadType *)connection->ptr2, rd->styles[j]);
1112 break;
1113 case PIN_TYPE:
1114 rb =
1115 AddPin (layergroupboxes, (PinType *)connection->ptr2, false,
1116 rd->styles[j]);
1117 break;
1118 case VIA_TYPE:
1119 rb =
1120 AddPin (layergroupboxes, (PinType *)connection->ptr2, true,
1121 rd->styles[j]);
1122 break;
1123 case POLYGON_TYPE:
1124 rb =
1125 AddPolygon (layergroupboxes,
1126 GetLayerNumber (PCB->Data, (LayerType *)connection->ptr1),
1127 (struct polygon_st *)connection->ptr2, rd->styles[j]);
1128 break;
1129 }
1130 assert (rb);
1131 /* update circular connectivity lists */
1132 if (last_in_subnet && rb != last_in_subnet)
1133 MergeNets (last_in_subnet, rb, ORIGINAL);
1134 if (last_in_net && rb != last_in_net)
1135 MergeNets (last_in_net, rb, NET);
1136 last_in_subnet = last_in_net = rb;
1137 rd->max_bloat = MAX (rd->max_bloat, BLOAT (rb->style));
1138 rd->max_keep = MAX (rd->max_keep, rb->style->Keepaway);
1139 }
1140 END_LOOP;
1141 }
1142 END_LOOP;
1143 if (last_net && last_in_net)
1144 MergeNets (last_net, last_in_net, DIFFERENT_NET);
1145 last_net = last_in_net;
1146 }
1147 END_LOOP;
1148 rd->first_net = last_net;
1149 }
1150 FreeNetListListMemory (&Nets);
1151
1152 /* reset all nets to "original" connectivity (which we just set) */
1153 {
1154 routebox_t *net;
1155 LIST_LOOP (rd->first_net, different_net, net);
1156 ResetSubnet (net);
1157 END_LOOP;
1158 }
1159
1160 /* add pins and pads of elements */
1161 ALLPIN_LOOP (PCB->Data);
1162 {
1163 if (TEST_FLAG (DRCFLAG, pin))
1164 CLEAR_FLAG (DRCFLAG, pin);
1165 else
1166 AddPin (layergroupboxes, pin, false, rd->styles[NUM_STYLES]);
1167 }
1168 ENDALL_LOOP;
1169 ALLPAD_LOOP (PCB->Data);
1170 {
1171 if (TEST_FLAG (DRCFLAG, pad))
1172 CLEAR_FLAG (DRCFLAG, pad);
1173 else
1174 AddPad (layergroupboxes, element, pad, rd->styles[NUM_STYLES]);
1175 }
1176 ENDALL_LOOP;
1177 /* add all vias */
1178 VIA_LOOP (PCB->Data);
1179 {
1180 if (TEST_FLAG (DRCFLAG, via))
1181 CLEAR_FLAG (DRCFLAG, via);
1182 else
1183 AddPin (layergroupboxes, via, true, rd->styles[NUM_STYLES]);
1184 }
1185 END_LOOP;
1186
1187 for (i = 0; i < max_copper_layer; i++)
1188 {
1189 int layergroup = GetLayerGroupNumberByNumber (i);
1190 /* add all (non-rat) lines */
1191 LINE_LOOP (LAYER_PTR (i));
1192 {
1193 if (TEST_FLAG (DRCFLAG, line))
1194 {
1195 CLEAR_FLAG (DRCFLAG, line);
1196 continue;
1197 }
1198 /* dice up non-straight lines into many tiny obstacles */
1199 if (line->Point1.X != line->Point2.X
1200 && line->Point1.Y != line->Point2.Y)
1201 {
1202 LineType fake_line = *line;
1203 Coord dx = (line->Point2.X - line->Point1.X);
1204 Coord dy = (line->Point2.Y - line->Point1.Y);
1205 int segs = MAX (ABS (dx), ABS (dy)) / (4 * rd->max_bloat + 1);
1206 int qq;
1207 segs = CLAMP (segs, 1, 32); /* don't go too crazy */
1208 dx /= segs;
1209 dy /= segs;
1210 for (qq = 0; qq < segs - 1; qq++)
1211 {
1212 fake_line.Point2.X = fake_line.Point1.X + dx;
1213 fake_line.Point2.Y = fake_line.Point1.Y + dy;
1214 if (fake_line.Point2.X == line->Point2.X
1215 && fake_line.Point2.Y == line->Point2.Y)
1216 break;
1217 AddLine (layergroupboxes, layergroup, &fake_line, line,
1218 rd->styles[NUM_STYLES]);
1219 fake_line.Point1 = fake_line.Point2;
1220 }
1221 fake_line.Point2 = line->Point2;
1222 AddLine (layergroupboxes, layergroup, &fake_line, line,
1223 rd->styles[NUM_STYLES]);
1224 }
1225 else
1226 {
1227 AddLine (layergroupboxes, layergroup, line, line,
1228 rd->styles[NUM_STYLES]);
1229 }
1230 }
1231 END_LOOP;
1232 /* add all polygons */
1233 POLYGON_LOOP (LAYER_PTR (i));
1234 {
1235 if (TEST_FLAG (DRCFLAG, polygon))
1236 CLEAR_FLAG (DRCFLAG, polygon);
1237 else
1238 AddPolygon (layergroupboxes, i, polygon, rd->styles[NUM_STYLES]);
1239 }
1240 END_LOOP;
1241 /* add all copper text */
1242 TEXT_LOOP (LAYER_PTR (i));
1243 {
1244 AddText (layergroupboxes, layergroup, text, rd->styles[NUM_STYLES]);
1245 }
1246 END_LOOP;
1247 /* add all arcs */
1248 ARC_LOOP (LAYER_PTR (i));
1249 {
1250 AddArc (layergroupboxes, layergroup, arc, rd->styles[NUM_STYLES]);
1251 }
1252 END_LOOP;
1253 }
1254
1255 /* create r-trees from pointer lists */
1256 for (i = 0; i < max_group; i++)
1257 {
1258 /* create the r-tree */
1259 rd->layergrouptree[i] =
1260 r_create_tree ((const BoxType **) layergroupboxes[i].Ptr,
1261 layergroupboxes[i].PtrN, 1);
1262 }
1263
1264 if (AutoRouteParameters.use_vias)
1265 {
1266 rd->mtspace = mtspace_create ();
1267
1268 /* create "empty-space" structures for via placement (now that we know
1269 * appropriate keepaways for all the fixed elements) */
1270 for (i = 0; i < max_group; i++)
1271 {
1272 POINTER_LOOP (&layergroupboxes[i]);
1273 {
1274 routebox_t *rb = (routebox_t *) * ptr;
1275 if (!rb->flags.clear_poly)
1276 mtspace_add (rd->mtspace, &rb->box, FIXED, rb->style->Keepaway);
1277 }
1278 END_LOOP;
1279 }
1280 }
1281 /* free pointer lists */
1282 for (i = 0; i < max_group; i++)
1283 FreePointerListMemory (&layergroupboxes[i]);
1284 /* done! */
1285 return rd;
1286 }
1287
1288 void
DestroyRouteData(routedata_t ** rd)1289 DestroyRouteData (routedata_t ** rd)
1290 {
1291 int i;
1292 for (i = 0; i < max_group; i++)
1293 r_destroy_tree (&(*rd)->layergrouptree[i]);
1294 if (AutoRouteParameters.use_vias)
1295 mtspace_destroy (&(*rd)->mtspace);
1296 free (*rd);
1297 *rd = NULL;
1298 }
1299
1300 /*-----------------------------------------------------------------
1301 * routebox reference counting.
1302 */
1303
1304 /*!
1305 * \brief Increment the reference count on a routebox.
1306 */
1307 static void
RB_up_count(routebox_t * rb)1308 RB_up_count (routebox_t * rb)
1309 {
1310 assert (rb->flags.homeless);
1311 rb->refcount++;
1312 }
1313
1314 /*!
1315 * \brief Decrement the reference count on a routebox, freeing if this
1316 * box becomes unused.
1317 */
1318 static void
RB_down_count(routebox_t * rb)1319 RB_down_count (routebox_t * rb)
1320 {
1321 assert (rb->type == EXPANSION_AREA);
1322 assert (rb->flags.homeless);
1323 assert (rb->refcount > 0);
1324 if (--rb->refcount == 0)
1325 {
1326 if (rb->parent.expansion_area->flags.homeless)
1327 RB_down_count (rb->parent.expansion_area);
1328 free (rb);
1329 }
1330 }
1331
1332 /*-----------------------------------------------------------------
1333 * Rectangle-expansion routing code.
1334 */
1335
1336 static void
ResetSubnet(routebox_t * net)1337 ResetSubnet (routebox_t * net)
1338 {
1339 routebox_t *rb;
1340 /* reset connectivity of everything on this net */
1341 LIST_LOOP (net, same_net, rb);
1342 rb->same_subnet = rb->original_subnet;
1343 END_LOOP;
1344 }
1345
1346 static inline cost_t
cost_to_point_on_layer(const CheapPointType * p1,const CheapPointType * p2,Cardinal point_layer)1347 cost_to_point_on_layer (const CheapPointType * p1,
1348 const CheapPointType * p2, Cardinal point_layer)
1349 {
1350 cost_t x_dist = p1->X - p2->X, y_dist = p1->Y - p2->Y, r;
1351 x_dist *= x_cost[point_layer];
1352 y_dist *= y_cost[point_layer];
1353 /* cost is proportional to orthogonal distance. */
1354 r = ABS (x_dist) + ABS (y_dist);
1355 if (p1->X != p2->X && p1->Y != p2->Y)
1356 r += AutoRouteParameters.JogPenalty;
1357 return r;
1358 }
1359
1360 static cost_t
cost_to_point(const CheapPointType * p1,Cardinal point_layer1,const CheapPointType * p2,Cardinal point_layer2)1361 cost_to_point (const CheapPointType * p1, Cardinal point_layer1,
1362 const CheapPointType * p2, Cardinal point_layer2)
1363 {
1364 cost_t r = cost_to_point_on_layer (p1, p2, point_layer1);
1365 /* apply via cost penalty if layers differ */
1366 if (point_layer1 != point_layer2)
1367 r += AutoRouteParameters.ViaCost;
1368 return r;
1369 }
1370
1371 /*!
1372 * \brief Return the minimum *cost* from a point to a box on any layer.
1373 *
1374 * It's safe to return a smaller than minimum cost.
1375 */
1376 static cost_t
cost_to_layerless_box(const CheapPointType * p,Cardinal point_layer,const BoxType * b)1377 cost_to_layerless_box (const CheapPointType * p, Cardinal point_layer,
1378 const BoxType * b)
1379 {
1380 CheapPointType p2 = closest_point_in_box (p, b);
1381 register cost_t c1, c2;
1382
1383 c1 = p2.X - p->X;
1384 c2 = p2.Y - p->Y;
1385
1386 c1 = ABS (c1);
1387 c2 = ABS (c2);
1388 if (c1 < c2)
1389 return c1 * AutoRouteParameters.MinPenalty + c2;
1390 else
1391 return c2 * AutoRouteParameters.MinPenalty + c1;
1392 }
1393
1394 /*!
1395 * \brief Get to actual pins/pad target coordinates.
1396 */
1397 bool
TargetPoint(CheapPointType * nextpoint,const routebox_t * target)1398 TargetPoint (CheapPointType * nextpoint, const routebox_t * target)
1399 {
1400 if (target->type == PIN)
1401 {
1402 nextpoint->X = target->parent.pin->X;
1403 nextpoint->Y = target->parent.pin->Y;
1404 return true;
1405 }
1406 else if (target->type == PAD)
1407 {
1408 if (abs (target->parent.pad->Point1.X - nextpoint->X) <
1409 abs (target->parent.pad->Point2.X - nextpoint->X))
1410 nextpoint->X = target->parent.pad->Point1.X;
1411 else
1412 nextpoint->X = target->parent.pad->Point2.X;
1413 if (abs (target->parent.pad->Point1.Y - nextpoint->Y) <
1414 abs (target->parent.pad->Point2.Y - nextpoint->Y))
1415 nextpoint->Y = target->parent.pad->Point1.Y;
1416 else
1417 nextpoint->Y = target->parent.pad->Point2.Y;
1418 return true;
1419 }
1420 else
1421 {
1422 nextpoint->X = CENTER_X (target->sbox);
1423 nextpoint->Y = CENTER_Y (target->sbox);
1424 }
1425 return false;
1426 }
1427
1428 /*!
1429 * \brief Return the *minimum cost* from a point to a route box,
1430 * including possible via costs if the route box is on a different
1431 * layer.
1432 *
1433 * Assume routbox is bloated unless it is an expansion area.
1434 */
1435 static cost_t
cost_to_routebox(const CheapPointType * p,Cardinal point_layer,const routebox_t * rb)1436 cost_to_routebox (const CheapPointType * p, Cardinal point_layer,
1437 const routebox_t * rb)
1438 {
1439 register cost_t trial = 0;
1440 CheapPointType p2 = closest_point_in_routebox (p, rb);
1441 if (!usedGroup[point_layer] || !usedGroup[rb->group])
1442 trial = AutoRouteParameters.NewLayerPenalty;
1443 if ((p2.X - p->X) * (p2.Y - p->Y) != 0)
1444 trial += AutoRouteParameters.JogPenalty;
1445 /* special case for defered via searching */
1446 if (point_layer > max_group || point_layer == rb->group)
1447 return trial + ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
1448 /* if this target is only a via away, then the via is cheaper than the congestion */
1449 if (p->X == p2.X && p->Y == p2.Y)
1450 return trial + 1;
1451 trial += AutoRouteParameters.ViaCost;
1452 trial += ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
1453 return trial;
1454 }
1455
1456
1457 static BoxType
bloat_routebox(routebox_t * rb)1458 bloat_routebox (routebox_t * rb)
1459 {
1460 BoxType r;
1461 Coord keepaway;
1462 assert (__routebox_is_good (rb));
1463
1464 if (rb->flags.nobloat)
1465 return rb->sbox;
1466
1467 /* Obstacle exclusion zones get bloated by the larger of
1468 * the two required clearances plus half the track width.
1469 */
1470 keepaway = MAX (AutoRouteParameters.style->Keepaway, rb->style->Keepaway);
1471 r = bloat_box (&rb->sbox, keepaway +
1472 HALF_THICK (AutoRouteParameters.style->Thick));
1473 return r;
1474 }
1475
1476
1477 #ifdef ROUTE_DEBUG /* only for debugging expansion areas */
1478
1479 /*!
1480 * \brief Makes a line on the solder layer silk surrounding the box.
1481 */
1482 void
showbox(BoxType b,Dimension thickness,int group)1483 showbox (BoxType b, Dimension thickness, int group)
1484 {
1485 LineType *line;
1486 LayerType *SLayer = LAYER_PTR (group);
1487 if (showboxen < -1)
1488 return;
1489 if (showboxen != -1 && showboxen != group)
1490 return;
1491
1492 if (ddraw != NULL)
1493 {
1494 ddraw->set_line_width (ar_gc, thickness);
1495 ddraw->set_line_cap (ar_gc, Trace_Cap);
1496 ddraw->set_color (ar_gc, SLayer->Color);
1497
1498 ddraw->draw_line (ar_gc, b.X1, b.Y1, b.X2, b.Y1);
1499 ddraw->draw_line (ar_gc, b.X1, b.Y2, b.X2, b.Y2);
1500 ddraw->draw_line (ar_gc, b.X1, b.Y1, b.X1, b.Y2);
1501 ddraw->draw_line (ar_gc, b.X2, b.Y1, b.X2, b.Y2);
1502 }
1503
1504 #if 1
1505 if (b.Y1 == b.Y2 || b.X1 == b.X2)
1506 thickness = 5;
1507 line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
1508 b.X1, b.Y1, b.X2, b.Y1, thickness, 0,
1509 MakeFlags (0));
1510 AddObjectToCreateUndoList (LINE_TYPE,
1511 LAYER_PTR (top_silk_layer), line,
1512 line);
1513 if (b.Y1 != b.Y2)
1514 {
1515 line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
1516 b.X1, b.Y2, b.X2, b.Y2, thickness, 0,
1517 MakeFlags (0));
1518 AddObjectToCreateUndoList (LINE_TYPE,
1519 LAYER_PTR (bottom_silk_layer),
1520 line, line);
1521 }
1522 line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
1523 b.X1, b.Y1, b.X1, b.Y2, thickness, 0,
1524 MakeFlags (0));
1525 AddObjectToCreateUndoList (LINE_TYPE,
1526 LAYER_PTR (top_silk_layer), line,
1527 line);
1528 if (b.X1 != b.X2)
1529 {
1530 line = CreateNewLineOnLayer (LAYER_PTR (top_silk_layer),
1531 b.X2, b.Y1, b.X2, b.Y2, thickness, 0,
1532 MakeFlags (0));
1533 AddObjectToCreateUndoList (LINE_TYPE,
1534 LAYER_PTR (top_silk_layer),
1535 line, line);
1536 }
1537 #endif
1538 }
1539 #endif
1540
1541 #if defined(ROUTE_DEBUG)
1542 static void
showedge(edge_t * e)1543 showedge (edge_t * e)
1544 {
1545 BoxType *b = (BoxType *) e->rb;
1546
1547 if (ddraw == NULL)
1548 return;
1549
1550 ddraw->set_line_cap (ar_gc, Trace_Cap);
1551 ddraw->set_line_width (ar_gc, 1);
1552 ddraw->set_color (ar_gc, Settings.MaskColor);
1553
1554 switch (e->expand_dir)
1555 {
1556 case NORTH:
1557 ddraw->draw_line (ar_gc, b->X1, b->Y1, b->X2, b->Y1);
1558 break;
1559 case SOUTH:
1560 ddraw->draw_line (ar_gc, b->X1, b->Y2, b->X2, b->Y2);
1561 break;
1562 case WEST:
1563 ddraw->draw_line (ar_gc, b->X1, b->Y1, b->X1, b->Y2);
1564 break;
1565 case EAST:
1566 ddraw->draw_line (ar_gc, b->X2, b->Y1, b->X2, b->Y2);
1567 break;
1568 default:
1569 break;
1570 }
1571 }
1572 #endif
1573
1574 #if defined(ROUTE_DEBUG)
1575 static void
showroutebox(routebox_t * rb)1576 showroutebox (routebox_t * rb)
1577 {
1578 showbox (rb->sbox, rb->flags.source ? 20 : (rb->flags.target ? 10 : 1),
1579 rb->flags.is_via ? top_silk_layer : rb->group);
1580 }
1581 #endif
1582
1583 /*!
1584 * \brief Return a "parent" of this edge which immediately precedes it
1585 * in the route.
1586 */
1587 static routebox_t *
route_parent(routebox_t * rb)1588 route_parent (routebox_t * rb)
1589 {
1590 while (rb->flags.homeless && !rb->flags.is_via && !rb->flags.is_thermal)
1591 {
1592 assert (rb->type == EXPANSION_AREA);
1593 rb = rb->parent.expansion_area;
1594 assert (rb);
1595 }
1596 return rb;
1597 }
1598
1599 static vector_t *
path_conflicts(routebox_t * rb,routebox_t * conflictor,bool branch)1600 path_conflicts (routebox_t * rb, routebox_t * conflictor, bool branch)
1601 {
1602 if (branch)
1603 rb->conflicts_with = vector_duplicate (rb->conflicts_with);
1604 else if (!rb->conflicts_with)
1605 rb->conflicts_with = vector_create ();
1606 vector_append (rb->conflicts_with, conflictor);
1607 return rb->conflicts_with;
1608 }
1609
1610 /*!
1611 * \brief Touch everything (except fixed) on each net found
1612 * in the conflicts vector. If the vector is different
1613 * from the last one touched, untouch the last batch
1614 * and touch the new one. Always call with touch=1
1615 * (except for recursive call). Call with NULL, 1 to
1616 * clear the last batch touched.
1617 *
1618 * Touched items become invisible to current path
1619 * so we don't encounter the same conflictor more
1620 * than once.
1621 */
1622 static void
touch_conflicts(vector_t * conflicts,int touch)1623 touch_conflicts (vector_t * conflicts, int touch)
1624 {
1625 static vector_t *last = NULL;
1626 static int last_size = 0;
1627 int i, n;
1628 i = 0;
1629 if (touch)
1630 {
1631 if (last && conflicts != last)
1632 touch_conflicts (last, 0);
1633 if (!conflicts)
1634 return;
1635 last = conflicts;
1636 i = last_size;
1637 }
1638 n = vector_size (conflicts);
1639 for (; i < n; i++)
1640 {
1641 routebox_t *rb = (routebox_t *) vector_element (conflicts, i);
1642 routebox_t *p;
1643 LIST_LOOP (rb, same_net, p);
1644 if (!p->flags.fixed)
1645 p->flags.touched = touch;
1646 END_LOOP;
1647 }
1648 if (!touch)
1649 {
1650 last = NULL;
1651 last_size = 0;
1652 }
1653 else
1654 last_size = n;
1655 }
1656
1657 /*!
1658 * \brief Return a "parent" of this edge which resides in a r-tree
1659 * somewhere.
1660 *
1661 * Actually, this "parent" *may* be a via box, which doesn't live in
1662 * a r-tree.
1663 */
1664 static routebox_t *
nonhomeless_parent(routebox_t * rb)1665 nonhomeless_parent (routebox_t * rb)
1666 {
1667 return route_parent (rb);
1668 }
1669
1670 /*!
1671 * \brief Some routines to find the minimum *cost* from a cost point to
1672 * a target (any target).
1673 */
1674 struct mincost_target_closure
1675 {
1676 const CheapPointType *CostPoint;
1677 Cardinal CostPointLayer;
1678 routebox_t *nearest;
1679 cost_t nearest_cost;
1680 };
1681 static int
__region_within_guess(const BoxType * region,void * cl)1682 __region_within_guess (const BoxType * region, void *cl)
1683 {
1684 struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
1685 cost_t cost_to_region;
1686 if (mtc->nearest == NULL)
1687 return 1;
1688 cost_to_region =
1689 cost_to_layerless_box (mtc->CostPoint, mtc->CostPointLayer, region);
1690 assert (cost_to_region >= 0);
1691 /* if no guess yet, all regions are "close enough" */
1692 /* note that cost is *strictly more* than minimum distance, so we'll
1693 * always search a region large enough. */
1694 return (cost_to_region < mtc->nearest_cost);
1695 }
1696 static int
__found_new_guess(const BoxType * box,void * cl)1697 __found_new_guess (const BoxType * box, void *cl)
1698 {
1699 struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
1700 routebox_t *guess = (routebox_t *) box;
1701 cost_t cost_to_guess =
1702 cost_to_routebox (mtc->CostPoint, mtc->CostPointLayer, guess);
1703 assert (cost_to_guess >= 0);
1704 /* if this is cheaper than previous guess... */
1705 if (cost_to_guess < mtc->nearest_cost)
1706 {
1707 mtc->nearest = guess;
1708 mtc->nearest_cost = cost_to_guess; /* this is our new guess! */
1709 return 1;
1710 }
1711 else
1712 return 0; /* not less expensive than our last guess */
1713 }
1714
1715 /*!
1716 * \brief .
1717 *
1718 * \c target_guess is our guess at what the nearest target is, or
1719 * \c NULL if we just plum don't have a clue.
1720 */
1721 static routebox_t *
mincost_target_to_point(const CheapPointType * CostPoint,Cardinal CostPointLayer,rtree_t * targets,routebox_t * target_guess)1722 mincost_target_to_point (const CheapPointType * CostPoint,
1723 Cardinal CostPointLayer,
1724 rtree_t * targets, routebox_t * target_guess)
1725 {
1726 struct mincost_target_closure mtc;
1727 assert (target_guess == NULL || target_guess->flags.target); /* this is a target, right? */
1728 mtc.CostPoint = CostPoint;
1729 mtc.CostPointLayer = CostPointLayer;
1730 mtc.nearest = target_guess;
1731 if (mtc.nearest)
1732 mtc.nearest_cost =
1733 cost_to_routebox (mtc.CostPoint, mtc.CostPointLayer, mtc.nearest);
1734 else
1735 mtc.nearest_cost = EXPENSIVE;
1736 r_search (targets, NULL, __region_within_guess, __found_new_guess, &mtc);
1737 assert (mtc.nearest != NULL && mtc.nearest_cost >= 0);
1738 assert (mtc.nearest->flags.target); /* this is a target, right? */
1739 return mtc.nearest;
1740 }
1741
1742 /*!
1743 * \brief Create edge from field values.
1744 *
1745 * mincost_target_guess can be \c NULL .
1746 */
1747 static edge_t *
CreateEdge(routebox_t * rb,Coord CostPointX,Coord CostPointY,cost_t cost_to_point,routebox_t * mincost_target_guess,direction_t expand_dir,rtree_t * targets)1748 CreateEdge (routebox_t * rb,
1749 Coord CostPointX, Coord CostPointY,
1750 cost_t cost_to_point,
1751 routebox_t * mincost_target_guess,
1752 direction_t expand_dir, rtree_t * targets)
1753 {
1754 edge_t *e;
1755 assert (__routebox_is_good (rb));
1756 e = (edge_t *)malloc (sizeof (*e));
1757 memset ((void *) e, 0, sizeof (*e));
1758 assert (e);
1759 e->rb = rb;
1760 if (rb->flags.homeless)
1761 RB_up_count (rb);
1762 e->cost_point.X = CostPointX;
1763 e->cost_point.Y = CostPointY;
1764 e->cost_to_point = cost_to_point;
1765 e->flags.via_search = 0;
1766 /* if this edge is created in response to a target, use it */
1767 if (targets)
1768 e->mincost_target =
1769 mincost_target_to_point (&e->cost_point, rb->group,
1770 targets, mincost_target_guess);
1771 else
1772 e->mincost_target = mincost_target_guess;
1773 e->expand_dir = expand_dir;
1774 assert (e->rb && e->mincost_target); /* valid edge? */
1775 assert (!e->flags.is_via || e->expand_dir == ALL);
1776 /* cost point should be on edge (unless this is a plane/via/conflict edge) */
1777 #if 0
1778 assert (rb->type == PLANE || rb->conflicts_with != NULL || rb->flags.is_via
1779 || rb->flags.is_thermal
1780 || ((expand_dir == NORTH || expand_dir == SOUTH) ? rb->sbox.X1 <=
1781 CostPointX && CostPointX < rb->sbox.X2
1782 && CostPointY == (expand_dir ==
1783 NORTH ? rb->sbox.Y1 : rb->sbox.Y2 - 1) :
1784 /* expand_dir==EAST || expand_dir==WEST */
1785 rb->sbox.Y1 <= CostPointY && CostPointY < rb->sbox.Y2 &&
1786 CostPointX == (expand_dir ==
1787 EAST ? rb->sbox.X2 - 1 : rb->sbox.X1)));
1788 #endif
1789 assert (__edge_is_good (e));
1790 /* done */
1791 return e;
1792 }
1793
1794 /*!
1795 * \brief Create edge, using previous edge to fill in defaults.
1796 *
1797 * Most of the work here is in determining a new cost point.
1798 */
1799 static edge_t *
CreateEdge2(routebox_t * rb,direction_t expand_dir,edge_t * previous_edge,rtree_t * targets,routebox_t * guess)1800 CreateEdge2 (routebox_t * rb, direction_t expand_dir,
1801 edge_t * previous_edge, rtree_t * targets, routebox_t * guess)
1802 {
1803 BoxType thisbox;
1804 CheapPointType thiscost, prevcost;
1805 cost_t d;
1806
1807 assert (rb && previous_edge);
1808 /* okay, find cheapest costpoint to costpoint of previous edge */
1809 thisbox = edge_to_box (rb, expand_dir);
1810 prevcost = previous_edge->cost_point;
1811 /* find point closest to target */
1812 thiscost = closest_point_in_box (&prevcost, &thisbox);
1813 /* compute cost-to-point */
1814 d = cost_to_point_on_layer (&prevcost, &thiscost, rb->group);
1815 /* add in jog penalty */
1816 if (previous_edge->expand_dir != expand_dir)
1817 d += AutoRouteParameters.JogPenalty;
1818 /* okay, new edge! */
1819 return CreateEdge (rb, thiscost.X, thiscost.Y,
1820 previous_edge->cost_to_point + d,
1821 guess ? guess : previous_edge->mincost_target,
1822 expand_dir, targets);
1823 }
1824
1825 /*!
1826 * \brief Create via edge, using previous edge to fill in defaults.
1827 */
1828 static edge_t *
CreateViaEdge(const BoxType * area,Cardinal group,routebox_t * parent,edge_t * previous_edge,conflict_t to_site_conflict,conflict_t through_site_conflict,rtree_t * targets)1829 CreateViaEdge (const BoxType * area, Cardinal group,
1830 routebox_t * parent, edge_t * previous_edge,
1831 conflict_t to_site_conflict,
1832 conflict_t through_site_conflict, rtree_t * targets)
1833 {
1834 routebox_t *rb;
1835 CheapPointType costpoint;
1836 cost_t d;
1837 edge_t *ne;
1838 cost_t scale[3];
1839
1840 scale[0] = 1;
1841 scale[1] = AutoRouteParameters.LastConflictPenalty;
1842 scale[2] = AutoRouteParameters.ConflictPenalty;
1843
1844 assert (box_is_good (area));
1845 assert (AutoRouteParameters.with_conflicts ||
1846 (to_site_conflict == NO_CONFLICT &&
1847 through_site_conflict == NO_CONFLICT));
1848 rb = CreateExpansionArea (area, group, parent, true, previous_edge);
1849 rb->flags.is_via = 1;
1850 rb->came_from = ALL;
1851 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES)
1852 showroutebox (rb);
1853 #endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */
1854 /* for planes, choose a point near the target */
1855 if (previous_edge->flags.in_plane)
1856 {
1857 routebox_t *target;
1858 CheapPointType pnt;
1859 /* find a target near this via box */
1860 pnt.X = CENTER_X (*area);
1861 pnt.Y = CENTER_Y (*area);
1862 target = mincost_target_to_point (&pnt, rb->group,
1863 targets,
1864 previous_edge->mincost_target);
1865 /* now find point near the target */
1866 pnt.X = CENTER_X (target->box);
1867 pnt.Y = CENTER_Y (target->box);
1868 costpoint = closest_point_in_routebox (&pnt, rb);
1869 /* we moved from the previous cost point through the plane which is free travel */
1870 d =
1871 (scale[through_site_conflict] *
1872 cost_to_point (&costpoint, group, &costpoint,
1873 previous_edge->rb->group));
1874 ne =
1875 CreateEdge (rb, costpoint.X, costpoint.Y,
1876 previous_edge->cost_to_point + d, target, ALL, NULL);
1877 ne->mincost_target = target;
1878 }
1879 else
1880 {
1881 routebox_t *target;
1882 target = previous_edge->mincost_target;
1883 costpoint = closest_point_in_routebox (&previous_edge->cost_point, rb);
1884 d =
1885 (scale[to_site_conflict] *
1886 cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
1887 previous_edge->rb->group)) +
1888 (scale[through_site_conflict] *
1889 cost_to_point (&costpoint, group, &costpoint,
1890 previous_edge->rb->group));
1891 /* if the target is just this via away, then this via is cheaper */
1892 if (target->group == group &&
1893 point_in_shrunk_box (target, costpoint.X, costpoint.Y))
1894 d -= AutoRouteParameters.ViaCost / 2;
1895 ne =
1896 CreateEdge (rb, costpoint.X, costpoint.Y,
1897 previous_edge->cost_to_point + d,
1898 previous_edge->mincost_target, ALL, targets);
1899 }
1900 ne->flags.is_via = 1;
1901 ne->flags.via_conflict_level = to_site_conflict;
1902 assert (__edge_is_good (ne));
1903 return ne;
1904 }
1905
1906 /*!
1907 * \brief Create "interior" edge for routing with conflicts.
1908 *
1909 * Presently once we "jump inside" the conflicting object
1910 * we consider it a routing highway to travel inside since
1911 * it will become available if the conflict is elliminated.
1912 * That is why we ignore the interior_edge argument.
1913 */
1914 static edge_t *
CreateEdgeWithConflicts(const BoxType * interior_edge,routebox_t * container,edge_t * previous_edge,cost_t cost_penalty_to_box,rtree_t * targets)1915 CreateEdgeWithConflicts (const BoxType * interior_edge,
1916 routebox_t * container, edge_t * previous_edge,
1917 cost_t cost_penalty_to_box, rtree_t * targets)
1918 {
1919 routebox_t *rb;
1920 CheapPointType costpoint;
1921 cost_t d;
1922 edge_t *ne;
1923 assert (interior_edge && container && previous_edge && targets);
1924 assert (!container->flags.homeless);
1925 assert (AutoRouteParameters.with_conflicts);
1926 assert (container->flags.touched == 0);
1927 assert (previous_edge->rb->group == container->group);
1928 /* use the caller's idea of what this box should be */
1929 rb =
1930 CreateExpansionArea (interior_edge, previous_edge->rb->group,
1931 previous_edge->rb, true, previous_edge);
1932 path_conflicts (rb, container, true); /* crucial! */
1933 costpoint =
1934 closest_point_in_box (&previous_edge->cost_point, interior_edge);
1935 d =
1936 cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
1937 previous_edge->rb->group);
1938 d *= cost_penalty_to_box;
1939 d += previous_edge->cost_to_point;
1940 ne = CreateEdge (rb, costpoint.X, costpoint.Y, d, NULL, ALL, targets);
1941 ne->flags.is_interior = 1;
1942 assert (__edge_is_good (ne));
1943 return ne;
1944 }
1945
1946 static void
KillEdge(void * edge)1947 KillEdge (void *edge)
1948 {
1949 edge_t *e = (edge_t *) edge;
1950 assert (e);
1951 if (e->rb->flags.homeless)
1952 RB_down_count (e->rb);
1953 if (e->flags.via_search)
1954 mtsFreeWork (&e->work);
1955 free (e);
1956 }
1957
1958 static void
DestroyEdge(edge_t ** e)1959 DestroyEdge (edge_t ** e)
1960 {
1961 assert (e && *e);
1962 KillEdge (*e);
1963 *e = NULL;
1964 }
1965
1966 /*!
1967 * \brief Cost function for an edge.
1968 */
1969 static cost_t
edge_cost(const edge_t * e,const cost_t too_big)1970 edge_cost (const edge_t * e, const cost_t too_big)
1971 {
1972 cost_t penalty = e->cost_to_point;
1973 if (e->rb->flags.is_thermal || e->rb->type == PLANE)
1974 return penalty; /* thermals are cheap */
1975 if (penalty > too_big)
1976 return penalty;
1977
1978 /* cost_to_routebox adds in our via correction, too. */
1979 return penalty +
1980 cost_to_routebox (&e->cost_point, e->rb->group, e->mincost_target);
1981 }
1982
1983 /*!
1984 * \brief Given an edge of a box, return a box containing exactly the
1985 * points on that edge.
1986 *
1987 * Note that the return box is treated as closed; that is, the bottom
1988 * and right "edges" consist of points (just barely) not in the
1989 * (half-open) box.
1990 */
1991 static BoxType
edge_to_box(const routebox_t * rb,direction_t expand_dir)1992 edge_to_box (const routebox_t * rb, direction_t expand_dir)
1993 {
1994 BoxType b = shrink_routebox (rb);
1995 /* narrow box down to just the appropriate edge */
1996 switch (expand_dir)
1997 {
1998 case NORTH:
1999 b.Y2 = b.Y1 + 1;
2000 break;
2001 case EAST:
2002 b.X1 = b.X2 - 1;
2003 break;
2004 case SOUTH:
2005 b.Y1 = b.Y2 - 1;
2006 break;
2007 case WEST:
2008 b.X2 = b.X1 + 1;
2009 break;
2010 default:
2011 assert (0);
2012 }
2013 /* done! */
2014 return b;
2015 }
2016
2017 struct broken_boxes
2018 {
2019 BoxType left, center, right;
2020 bool is_valid_left, is_valid_center, is_valid_right;
2021 };
2022
2023 static struct broken_boxes
break_box_edge(const BoxType * original,direction_t which_edge,routebox_t * breaker)2024 break_box_edge (const BoxType * original, direction_t which_edge,
2025 routebox_t * breaker)
2026 {
2027 BoxType origbox, breakbox;
2028 struct broken_boxes result;
2029
2030 assert (original && breaker);
2031
2032 origbox = *original;
2033 breakbox = bloat_routebox (breaker);
2034 ROTATEBOX_TO_NORTH (origbox, which_edge);
2035 ROTATEBOX_TO_NORTH (breakbox, which_edge);
2036 result.right.Y1 = result.center.Y1 = result.left.Y1 = origbox.Y1;
2037 result.right.Y2 = result.center.Y2 = result.left.Y2 = origbox.Y1 + 1;
2038 /* validity of breaker is not important because the boxes are marked invalid */
2039 //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
2040 /* left edge piece */
2041 result.left.X1 = origbox.X1;
2042 result.left.X2 = breakbox.X1;
2043 /* center (ie blocked) edge piece */
2044 result.center.X1 = MAX (breakbox.X1, origbox.X1);
2045 result.center.X2 = MIN (breakbox.X2, origbox.X2);
2046 /* right edge piece */
2047 result.right.X1 = breakbox.X2;
2048 result.right.X2 = origbox.X2;
2049 /* validity: */
2050 result.is_valid_left = (result.left.X1 < result.left.X2);
2051 result.is_valid_center = (result.center.X1 < result.center.X2);
2052 result.is_valid_right = (result.right.X1 < result.right.X2);
2053 /* rotate back */
2054 ROTATEBOX_FROM_NORTH (result.left, which_edge);
2055 ROTATEBOX_FROM_NORTH (result.center, which_edge);
2056 ROTATEBOX_FROM_NORTH (result.right, which_edge);
2057 /* done */
2058 return result;
2059 }
2060
2061 #ifndef NDEBUG
2062 static int
share_edge(const BoxType * child,const BoxType * parent)2063 share_edge (const BoxType * child, const BoxType * parent)
2064 {
2065 return
2066 (child->X1 == parent->X2 || child->X2 == parent->X1 ||
2067 child->Y1 == parent->Y2 || child->Y2 == parent->Y1) &&
2068 ((parent->X1 <= child->X1 && child->X2 <= parent->X2) ||
2069 (parent->Y1 <= child->Y1 && child->Y2 <= parent->Y2));
2070 }
2071 static int
edge_intersect(const BoxType * child,const BoxType * parent)2072 edge_intersect (const BoxType * child, const BoxType * parent)
2073 {
2074 return
2075 (child->X1 <= parent->X2) && (child->X2 >= parent->X1) &&
2076 (child->Y1 <= parent->Y2) && (child->Y2 >= parent->Y1);
2077 }
2078 #endif
2079
2080 /*!
2081 * \brief Area is the expansion area, on layer group 'group'.
2082 *
2083 * 'parent' is the immediately preceding expansion area, for backtracing.
2084 * 'lastarea' is the last expansion area created, we string these
2085 * together in a loop so we can remove them all easily at the end.
2086 */
2087 static routebox_t *
CreateExpansionArea(const BoxType * area,Cardinal group,routebox_t * parent,bool relax_edge_requirements,edge_t * src_edge)2088 CreateExpansionArea (const BoxType * area, Cardinal group,
2089 routebox_t * parent,
2090 bool relax_edge_requirements, edge_t * src_edge)
2091 {
2092 routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
2093 memset ((void *) rb, 0, sizeof (*rb));
2094 assert (area && parent);
2095 init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
2096 rb->group = group;
2097 rb->type = EXPANSION_AREA;
2098 /* should always share edge or overlap with parent */
2099 assert (relax_edge_requirements ? box_intersect (&rb->sbox, &parent->sbox)
2100 : share_edge (&rb->sbox, &parent->sbox));
2101 rb->parent.expansion_area = route_parent (parent);
2102 rb->cost_point =
2103 closest_point_in_box (&rb->parent.expansion_area->cost_point, area);
2104 rb->cost =
2105 rb->parent.expansion_area->cost +
2106 cost_to_point_on_layer (&rb->parent.expansion_area->cost_point,
2107 &rb->cost_point, rb->group);
2108 assert (relax_edge_requirements ? edge_intersect (&rb->sbox, &parent->sbox)
2109 : share_edge (&rb->sbox, &parent->sbox));
2110 if (rb->parent.expansion_area->flags.homeless)
2111 RB_up_count (rb->parent.expansion_area);
2112 rb->flags.homeless = 1;
2113 rb->flags.nobloat = 1;
2114 rb->style = AutoRouteParameters.style;
2115 rb->conflicts_with = parent->conflicts_with;
2116 /* we will never link an EXPANSION_AREA into the nets because they
2117 * are *ONLY* used for path searching. No need to call InitLists ()
2118 */
2119 rb->came_from = src_edge->expand_dir;
2120 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
2121 showroutebox (rb);
2122 #endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
2123 return rb;
2124 }
2125
2126 /*------ Expand ------*/
2127 struct E_result
2128 {
2129 routebox_t *parent;
2130 routebox_t *n, *e, *s, *w;
2131 Coord keep, bloat;
2132 BoxType inflated, orig;
2133 int done;
2134 };
2135
2136 /*!
2137 * \brief Test method for Expand().
2138 *
2139 * This routebox potentially is a blocker limiting expansion
2140 * if this is so, we limit the inflate box so another exactly
2141 * like it wouldn't be seen. We do this while keep the inflated
2142 * box as large as possible.
2143 */
2144 static int
__Expand_this_rect(const BoxType * box,void * cl)2145 __Expand_this_rect (const BoxType * box, void *cl)
2146 {
2147 struct E_result *res = (struct E_result *) cl;
2148 routebox_t *rb = (routebox_t *) box;
2149 BoxType rbox;
2150 Coord dn, de, ds, dw, bloat;
2151
2152 /* we don't see conflicts already encountered */
2153 if (rb->flags.touched)
2154 return 0;
2155
2156 /* The inflated box outer edges include its own
2157 * track width plus its own keepaway.
2158 *
2159 * To check for intersection, we need to expand
2160 * anything with greater keepaway by its excess
2161 * keepaway.
2162 *
2163 * If something has nobloat then we need to shrink
2164 * the inflated box back and see if it still touches.
2165 */
2166
2167 if (rb->flags.nobloat)
2168 {
2169 rbox = rb->sbox;
2170 bloat = res->bloat;
2171 if (rbox.X2 <= res->inflated.X1 + bloat ||
2172 rbox.X1 >= res->inflated.X2 - bloat ||
2173 rbox.Y1 >= res->inflated.Y2 - bloat ||
2174 rbox.Y2 <= res->inflated.Y1 + bloat)
2175 return 0; /* doesn't touch */
2176 }
2177 else
2178 {
2179 if (rb->style->Keepaway > res->keep)
2180 rbox = bloat_box (&rb->sbox, rb->style->Keepaway - res->keep);
2181 else
2182 rbox = rb->sbox;
2183
2184 if (rbox.X2 <= res->inflated.X1 || rbox.X1 >= res->inflated.X2
2185 || rbox.Y1 >= res->inflated.Y2 || rbox.Y2 <= res->inflated.Y1)
2186 return 0; /* doesn't touch */
2187 bloat = 0;
2188 }
2189
2190 /* this is an intersecting box; it has to jump through a few more hoops */
2191 if (rb == res->parent || rb->parent.expansion_area == res->parent)
2192 return 0; /* don't see what we came from */
2193
2194 /* if we are expanding a source edge, don't let other sources
2195 * or their expansions stop us.
2196 */
2197 #if 1
2198 if (res->parent->flags.source)
2199 if (rb->flags.source
2200 || (rb->type == EXPANSION_AREA
2201 && rb->parent.expansion_area->flags.source))
2202 return 0;
2203 #endif
2204
2205 /* we ignore via expansion boxes because maybe its
2206 * cheaper to get there without the via through
2207 * the path we're exploring now.
2208 */
2209 if (rb->flags.is_via && rb->type == EXPANSION_AREA)
2210 return 0;
2211
2212 if (rb->type == PLANE) /* expanding inside a plane is not good */
2213 {
2214 if (rbox.X1 < res->orig.X1 && rbox.X2 > res->orig.X2 &&
2215 rbox.Y1 < res->orig.Y1 && rbox.Y2 > res->orig.Y2)
2216 {
2217 res->inflated = bloat_box (&res->orig, res->bloat);
2218 return 1;
2219 }
2220 }
2221 /* calculate the distances from original box to this blocker */
2222 dn = de = ds = dw = 0;
2223 if (!(res->done & _NORTH) && rbox.Y1 <= res->orig.Y1
2224 && rbox.Y2 > res->inflated.Y1)
2225 dn = res->orig.Y1 - rbox.Y2;
2226 if (!(res->done & _EAST) && rbox.X2 >= res->orig.X2
2227 && rbox.X1 < res->inflated.X2)
2228 de = rbox.X1 - res->orig.X2;
2229 if (!(res->done & _SOUTH) && rbox.Y2 >= res->orig.Y2
2230 && rbox.Y1 < res->inflated.Y2)
2231 ds = rbox.Y1 - res->orig.Y2;
2232 if (!(res->done & _WEST) && rbox.X1 <= res->orig.X1
2233 && rbox.X2 > res->inflated.X1)
2234 dw = res->orig.X1 - rbox.X2;
2235 if (dn <= 0 && de <= 0 && ds <= 0 && dw <= 0)
2236 return 1;
2237 /* now shrink the inflated box to the largest blocking direction */
2238 if (dn >= de && dn >= ds && dn >= dw)
2239 {
2240 res->inflated.Y1 = rbox.Y2 - bloat;
2241 res->n = rb;
2242 }
2243 else if (de >= ds && de >= dw)
2244 {
2245 res->inflated.X2 = rbox.X1 + bloat;
2246 res->e = rb;
2247 }
2248 else if (ds >= dw)
2249 {
2250 res->inflated.Y2 = rbox.Y1 + bloat;
2251 res->s = rb;
2252 }
2253 else
2254 {
2255 res->inflated.X1 = rbox.X2 - bloat;
2256 res->w = rb;
2257 }
2258 return 1;
2259 }
2260
2261 static bool
boink_box(routebox_t * rb,struct E_result * res,direction_t dir)2262 boink_box (routebox_t * rb, struct E_result *res, direction_t dir)
2263 {
2264 Coord bloat;
2265 if (rb->style->Keepaway > res->keep)
2266 bloat = res->keep - rb->style->Keepaway;
2267 else
2268 bloat = 0;
2269 if (rb->flags.nobloat)
2270 bloat = res->bloat;
2271 switch (dir)
2272 {
2273 case NORTH:
2274 case SOUTH:
2275 if (rb->sbox.X2 <= res->inflated.X1 + bloat
2276 || rb->sbox.X1 >= res->inflated.X2 - bloat)
2277 return false;
2278 return true;
2279 case EAST:
2280 case WEST:
2281 if (rb->sbox.Y1 >= res->inflated.Y2 - bloat
2282 || rb->sbox.Y2 <= res->inflated.Y1 + bloat)
2283 return false;
2284 return true;
2285 break;
2286 default:
2287 assert (0);
2288 }
2289 return false;
2290 }
2291
2292 /*!
2293 * \brief Main Expand routine.
2294 *
2295 * The expansion probe edge includes the keepaway and half thickness
2296 * as the search is performed in order to see everything relevant.
2297 * The result is backed off by this amount before being returned.
2298 * Targets (and other no-bloat routeboxes) go all the way to touching.
2299 * This is accomplished by backing off the probe edge when checking
2300 * for touch against such an object. Usually the expanding edge
2301 * bumps into neighboring pins on the same device that require a
2302 * keepaway, preventing seeing a target immediately. Rather than await
2303 * another expansion to actually touch the target, the edge breaker code
2304 * looks past the keepaway to see these targets even though they
2305 * weren't actually touched in the expansion.
2306 */
2307 struct E_result *
Expand(rtree_t * rtree,edge_t * e,const BoxType * box)2308 Expand (rtree_t * rtree, edge_t * e, const BoxType * box)
2309 {
2310 static struct E_result ans;
2311 int noshrink; /* bit field of which edges to not shrink */
2312
2313 ans.bloat = AutoRouteParameters.bloat;
2314 ans.orig = *box;
2315 ans.n = ans.e = ans.s = ans.w = NULL;
2316
2317 /* the inflated box must be bloated in all directions that it might
2318 * hit something in order to guarantee that we see object in the
2319 * tree it might hit. The tree holds objects bloated by their own
2320 * keepaway so we are guaranteed to honor that.
2321 */
2322 switch (e->expand_dir)
2323 {
2324 case ALL:
2325 ans.inflated.X1 = (e->rb->came_from == EAST ? ans.orig.X1 : 0);
2326 ans.inflated.Y1 = (e->rb->came_from == SOUTH ? ans.orig.Y1 : 0);
2327 ans.inflated.X2 =
2328 (e->rb->came_from == WEST ? ans.orig.X2 : PCB->MaxWidth);
2329 ans.inflated.Y2 =
2330 (e->rb->came_from == NORTH ? ans.orig.Y2 : PCB->MaxHeight);
2331 if (e->rb->came_from == NORTH)
2332 ans.done = noshrink = _SOUTH;
2333 else if (e->rb->came_from == EAST)
2334 ans.done = noshrink = _WEST;
2335 else if (e->rb->came_from == SOUTH)
2336 ans.done = noshrink = _NORTH;
2337 else if (e->rb->came_from == WEST)
2338 ans.done = noshrink = _EAST;
2339 else
2340 ans.done = noshrink = 0;
2341 break;
2342 case NORTH:
2343 ans.done = _SOUTH + _EAST + _WEST;
2344 noshrink = _SOUTH;
2345 ans.inflated.X1 = box->X1 - ans.bloat;
2346 ans.inflated.X2 = box->X2 + ans.bloat;
2347 ans.inflated.Y2 = box->Y2;
2348 ans.inflated.Y1 = 0; /* far north */
2349 break;
2350 case NE:
2351 ans.done = _SOUTH + _WEST;
2352 noshrink = 0;
2353 ans.inflated.X1 = box->X1 - ans.bloat;
2354 ans.inflated.X2 = PCB->MaxWidth;
2355 ans.inflated.Y2 = box->Y2 + ans.bloat;
2356 ans.inflated.Y1 = 0;
2357 break;
2358 case EAST:
2359 ans.done = _NORTH + _SOUTH + _WEST;
2360 noshrink = _WEST;
2361 ans.inflated.Y1 = box->Y1 - ans.bloat;
2362 ans.inflated.Y2 = box->Y2 + ans.bloat;
2363 ans.inflated.X1 = box->X1;
2364 ans.inflated.X2 = PCB->MaxWidth;
2365 break;
2366 case SE:
2367 ans.done = _NORTH + _WEST;
2368 noshrink = 0;
2369 ans.inflated.X1 = box->X1 - ans.bloat;
2370 ans.inflated.X2 = PCB->MaxWidth;
2371 ans.inflated.Y2 = PCB->MaxHeight;
2372 ans.inflated.Y1 = box->Y1 - ans.bloat;
2373 break;
2374 case SOUTH:
2375 ans.done = _NORTH + _EAST + _WEST;
2376 noshrink = _NORTH;
2377 ans.inflated.X1 = box->X1 - ans.bloat;
2378 ans.inflated.X2 = box->X2 + ans.bloat;
2379 ans.inflated.Y1 = box->Y1;
2380 ans.inflated.Y2 = PCB->MaxHeight;
2381 break;
2382 case SW:
2383 ans.done = _NORTH + _EAST;
2384 noshrink = 0;
2385 ans.inflated.X1 = 0;
2386 ans.inflated.X2 = box->X2 + ans.bloat;
2387 ans.inflated.Y2 = PCB->MaxHeight;
2388 ans.inflated.Y1 = box->Y1 - ans.bloat;
2389 break;
2390 case WEST:
2391 ans.done = _NORTH + _SOUTH + _EAST;
2392 noshrink = _EAST;
2393 ans.inflated.Y1 = box->Y1 - ans.bloat;
2394 ans.inflated.Y2 = box->Y2 + ans.bloat;
2395 ans.inflated.X1 = 0;
2396 ans.inflated.X2 = box->X2;
2397 break;
2398 case NW:
2399 ans.done = _SOUTH + _EAST;
2400 noshrink = 0;
2401 ans.inflated.X1 = 0;
2402 ans.inflated.X2 = box->X2 + ans.bloat;
2403 ans.inflated.Y2 = box->Y2 + ans.bloat;
2404 ans.inflated.Y1 = 0;
2405 break;
2406 default:
2407 noshrink = ans.done = 0;
2408 assert (0);
2409 }
2410 ans.keep = e->rb->style->Keepaway;
2411 ans.parent = nonhomeless_parent (e->rb);
2412 r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
2413 /* because the overlaping boxes are found in random order, some blockers
2414 * may have limited edges prematurely, so we check if the blockers realy
2415 * are blocking, and make another try if not
2416 */
2417 if (ans.n && !boink_box (ans.n, &ans, NORTH))
2418 ans.inflated.Y1 = 0;
2419 else
2420 ans.done |= _NORTH;
2421 if (ans.e && !boink_box (ans.e, &ans, EAST))
2422 ans.inflated.X2 = PCB->MaxWidth;
2423 else
2424 ans.done |= _EAST;
2425 if (ans.s && !boink_box (ans.s, &ans, SOUTH))
2426 ans.inflated.Y2 = PCB->MaxHeight;
2427 else
2428 ans.done |= _SOUTH;
2429 if (ans.w && !boink_box (ans.w, &ans, WEST))
2430 ans.inflated.X1 = 0;
2431 else
2432 ans.done |= _WEST;
2433 if (ans.done != _NORTH + _EAST + _SOUTH + _WEST)
2434 {
2435 r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
2436 }
2437 if ((noshrink & _NORTH) == 0)
2438 ans.inflated.Y1 += ans.bloat;
2439 if ((noshrink & _EAST) == 0)
2440 ans.inflated.X2 -= ans.bloat;
2441 if ((noshrink & _SOUTH) == 0)
2442 ans.inflated.Y2 -= ans.bloat;
2443 if ((noshrink & _WEST) == 0)
2444 ans.inflated.X1 += ans.bloat;
2445 return &ans;
2446 }
2447
2448 /*!
2449 * \brief \c blocker_to_heap puts the blockers into a heap so they
2450 * can be retrieved in clockwise order. If a blocker
2451 * is also a target, it gets put into the vector too.
2452 * It returns 1 for any fixed blocker that is not part
2453 * of this net and zero otherwise.
2454 */
2455 static int
blocker_to_heap(heap_t * heap,routebox_t * rb,BoxType * box,direction_t dir)2456 blocker_to_heap (heap_t * heap, routebox_t * rb,
2457 BoxType * box, direction_t dir)
2458 {
2459 BoxType b = rb->sbox;
2460 if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
2461 b =
2462 bloat_box (&b,
2463 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
2464 b = clip_box (&b, box);
2465 assert (box_is_good (&b));
2466 /* we want to look at the blockers clockwise around the box */
2467 switch (dir)
2468 {
2469 /* we need to use the other coordinate fraction to resolve
2470 * ties since we want the shorter of the furthest
2471 * first.
2472 */
2473 case NORTH:
2474 heap_insert (heap, b.X1 - b.X1 / (b.X2 + 1.0), rb);
2475 break;
2476 case EAST:
2477 heap_insert (heap, b.Y1 - b.Y1 / (b.Y2 + 1.0), rb);
2478 break;
2479 case SOUTH:
2480 heap_insert (heap, -(b.X2 + b.X1 / (b.X2 + 1.0)), rb);
2481 break;
2482 case WEST:
2483 heap_insert (heap, -(b.Y2 + b.Y1 / (b.Y2 + 1.0)), rb);
2484 break;
2485 default:
2486 assert (0);
2487 }
2488 if (rb->flags.fixed && !rb->flags.target && !rb->flags.source)
2489 return 1;
2490 return 0;
2491 }
2492
2493 /*!
2494 * \brief This creates an EXPANSION_AREA to bridge small gaps or,
2495 * (more commonly) create a supper-thin box to provide a
2496 * home for an expansion edge.
2497 */
2498 static routebox_t *
CreateBridge(const BoxType * area,routebox_t * parent,direction_t dir)2499 CreateBridge (const BoxType * area, routebox_t * parent, direction_t dir)
2500 {
2501 routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
2502 memset ((void *) rb, 0, sizeof (*rb));
2503 assert (area && parent);
2504 init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
2505 rb->group = parent->group;
2506 rb->type = EXPANSION_AREA;
2507 rb->came_from = dir;
2508 rb->cost_point = closest_point_in_box (&parent->cost_point, area);
2509 rb->cost = parent->cost + cost_to_point_on_layer (&parent->cost_point,
2510 &rb->cost_point,
2511 rb->group);
2512 rb->parent.expansion_area = route_parent (parent);
2513 if (rb->parent.expansion_area->flags.homeless)
2514 RB_up_count (rb->parent.expansion_area);
2515 rb->flags.homeless = 1;
2516 rb->flags.nobloat = 1;
2517 rb->style = parent->style;
2518 rb->conflicts_with = parent->conflicts_with;
2519 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
2520 showroutebox (rb);
2521 #endif
2522 return rb;
2523 }
2524
2525 /*!
2526 * \brief \c moveable_edge prepares the new search edges based on the
2527 * starting box, direction and blocker if any.
2528 */
2529 void
moveable_edge(vector_t * result,const BoxType * box,direction_t dir,routebox_t * rb,routebox_t * blocker,edge_t * e,rtree_t * targets,struct routeone_state * s,rtree_t * tree,vector_t * area_vec)2530 moveable_edge (vector_t * result, const BoxType * box, direction_t dir,
2531 routebox_t * rb,
2532 routebox_t * blocker, edge_t * e, rtree_t * targets,
2533 struct routeone_state *s, rtree_t * tree, vector_t * area_vec)
2534 {
2535 BoxType b;
2536 assert (box_is_good (box));
2537 b = *box;
2538 /* for the cardinal directions, move the box to overlap the
2539 * the parent by 1 unit. Corner expansions overlap more
2540 * and their starting boxes are pre-prepared.
2541 * Check if anything is headed off the board edges
2542 */
2543 switch (dir)
2544 {
2545 default:
2546 break;
2547 case NORTH:
2548 b.Y2 = b.Y1;
2549 b.Y1--;
2550 if (b.Y1 <= AutoRouteParameters.bloat)
2551 return; /* off board edge */
2552 break;
2553 case EAST:
2554 b.X1 = b.X2;
2555 b.X2++;
2556 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat)
2557 return; /* off board edge */
2558 break;
2559 case SOUTH:
2560 b.Y1 = b.Y2;
2561 b.Y2++;
2562 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat)
2563 return; /* off board edge */
2564 break;
2565 case WEST:
2566 b.X2 = b.X1;
2567 b.X1--;
2568 if (b.X1 <= AutoRouteParameters.bloat)
2569 return; /* off board edge */
2570 break;
2571 case NE:
2572 if (b.Y1 <= AutoRouteParameters.bloat + 1
2573 && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2574 return; /* off board edge */
2575 if (b.Y1 <= AutoRouteParameters.bloat + 1)
2576 dir = EAST; /* north off board edge */
2577 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2578 dir = NORTH; /* east off board edge */
2579 break;
2580 case SE:
2581 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
2582 && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2583 return; /* off board edge */
2584 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
2585 dir = EAST; /* south off board edge */
2586 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2587 dir = SOUTH; /* east off board edge */
2588 break;
2589 case SW:
2590 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
2591 && b.X1 <= AutoRouteParameters.bloat + 1)
2592 return; /* off board edge */
2593 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
2594 dir = WEST; /* south off board edge */
2595 if (b.X1 <= AutoRouteParameters.bloat + 1)
2596 dir = SOUTH; /* west off board edge */
2597 break;
2598 case NW:
2599 if (b.Y1 <= AutoRouteParameters.bloat + 1
2600 && b.X1 <= AutoRouteParameters.bloat + 1)
2601 return; /* off board edge */
2602 if (b.Y1 <= AutoRouteParameters.bloat + 1)
2603 dir = WEST; /* north off board edge */
2604 if (b.X1 <= AutoRouteParameters.bloat + 1)
2605 dir = NORTH; /* west off board edge */
2606 break;
2607 }
2608
2609 if (!blocker)
2610 {
2611 edge_t *ne;
2612 routebox_t *nrb = CreateBridge (&b, rb, dir);
2613 /* move the cost point in corner expansions
2614 * these boxes are bigger, so move close to the target
2615 */
2616 if (dir == NE || dir == SE || dir == SW || dir == NW)
2617 {
2618 CheapPointType p;
2619 p =
2620 closest_point_in_box (&nrb->cost_point, &e->mincost_target->sbox);
2621 p = closest_point_in_box (&p, &b);
2622 nrb->cost += cost_to_point_on_layer (&p, &nrb->cost_point,
2623 nrb->group);
2624 nrb->cost_point = p;
2625 }
2626 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
2627 nrb->cost, NULL, dir, targets);
2628 vector_append (result, ne);
2629 }
2630 else if (AutoRouteParameters.with_conflicts && !blocker->flags.target
2631 && !blocker->flags.fixed && !blocker->flags.touched &&
2632 !blocker->flags.source && blocker->type != EXPANSION_AREA)
2633 {
2634 edge_t *ne;
2635 routebox_t *nrb;
2636 /* make a bridge to the edge of the blocker
2637 * in all directions from there
2638 */
2639 switch (dir)
2640 {
2641 case NORTH:
2642 b.Y1 = blocker->sbox.Y2 - 1;
2643 break;
2644 case EAST:
2645 b.X2 = blocker->sbox.X1 + 1;
2646 break;
2647 case SOUTH:
2648 b.Y2 = blocker->sbox.Y1 + 1;
2649 break;
2650 case WEST:
2651 b.X1 = blocker->sbox.X2 - 1;
2652 break;
2653 default:
2654 assert (0);
2655 }
2656 if (!box_is_good (&b))
2657 return; /* how did this happen ? */
2658 nrb = CreateBridge (&b, rb, dir);
2659 r_insert_entry (tree, &nrb->box, 1);
2660 vector_append (area_vec, nrb);
2661 nrb->flags.homeless = 0; /* not homeless any more */
2662 /* mark this one as conflicted */
2663 path_conflicts (nrb, blocker, true);
2664 /* and make an expansion edge */
2665 nrb->cost_point =
2666 closest_point_in_box (&nrb->cost_point, &blocker->sbox);
2667 nrb->cost +=
2668 cost_to_point_on_layer (&nrb->parent.expansion_area->cost_point,
2669 &nrb->cost_point,
2670 nrb->group) * CONFLICT_PENALTY (blocker);
2671
2672 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y, nrb->cost,
2673 NULL, ALL, targets);
2674 ne->flags.is_interior = 1;
2675 vector_append (result, ne);
2676 }
2677 #if 1
2678 else if (blocker->type == EXPANSION_AREA)
2679 {
2680 if (blocker->cost < rb->cost || blocker->cost <= rb->cost +
2681 cost_to_point_on_layer (&blocker->cost_point, &rb->cost_point,
2682 rb->group))
2683 return;
2684 if (blocker->conflicts_with || rb->conflicts_with)
2685 return;
2686 /* does the blocker overlap this routebox ?? */
2687 /* does this re-parenting operation leave a memory leak? */
2688 if (blocker->parent.expansion_area->flags.homeless)
2689 RB_down_count (blocker->parent.expansion_area);
2690 blocker->parent.expansion_area = rb;
2691 return;
2692 }
2693 #endif
2694 else if (blocker->flags.target)
2695 {
2696 routebox_t *nrb;
2697 edge_t *ne;
2698 b = bloat_box (&b, 1);
2699 if (!box_intersect (&b, &blocker->sbox))
2700 {
2701 /* if the expansion edge stopped before touching, expand the bridge */
2702 switch (dir)
2703 {
2704 case NORTH:
2705 b.Y1 -= AutoRouteParameters.bloat + 1;
2706 break;
2707 case EAST:
2708 b.X2 += AutoRouteParameters.bloat + 1;
2709 break;
2710 case SOUTH:
2711 b.Y2 += AutoRouteParameters.bloat + 1;
2712 break;
2713 case WEST:
2714 b.X1 -= AutoRouteParameters.bloat + 1;
2715 break;
2716 default:
2717 assert (0);
2718 }
2719 }
2720 assert (box_intersect (&b, &blocker->sbox));
2721 b = shrink_box (&b, 1);
2722 nrb = CreateBridge (&b, rb, dir);
2723 r_insert_entry (tree, &nrb->box, 1);
2724 vector_append (area_vec, nrb);
2725 nrb->flags.homeless = 0; /* not homeless any more */
2726 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
2727 nrb->cost, blocker, dir, NULL);
2728 best_path_candidate (s, ne, blocker);
2729 DestroyEdge (&ne);
2730 }
2731 }
2732
2733 struct break_info
2734 {
2735 heap_t *heap;
2736 routebox_t *parent;
2737 BoxType box;
2738 direction_t dir;
2739 bool ignore_source;
2740 };
2741
2742 static int
__GatherBlockers(const BoxType * box,void * cl)2743 __GatherBlockers (const BoxType * box, void *cl)
2744 {
2745 routebox_t *rb = (routebox_t *) box;
2746 struct break_info *bi = (struct break_info *) cl;
2747 BoxType b;
2748
2749 if (bi->parent == rb || rb->flags.touched ||
2750 bi->parent->parent.expansion_area == rb)
2751 return 0;
2752 if (rb->flags.source && bi->ignore_source)
2753 return 0;
2754 b = rb->sbox;
2755 if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
2756 b =
2757 bloat_box (&b,
2758 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
2759 if (b.X2 <= bi->box.X1 || b.X1 >= bi->box.X2
2760 || b.Y1 >= bi->box.Y2 || b.Y2 <= bi->box.Y1)
2761 return 0;
2762 return blocker_to_heap (bi->heap, rb, &bi->box, bi->dir);
2763 }
2764
2765 /*!
2766 * \brief Shrink the box to the last limit for the previous direction,
2767 * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
2768 * edge, which would be the southern most edge for that example.
2769 */
2770 static inline BoxType
previous_edge(Coord last,direction_t i,const BoxType * b)2771 previous_edge (Coord last, direction_t i, const BoxType * b)
2772 {
2773 BoxType db = *b;
2774 switch (i)
2775 {
2776 case EAST:
2777 db.X1 = last;
2778 break;
2779 case SOUTH:
2780 db.Y1 = last;
2781 break;
2782 case WEST:
2783 db.X2 = last;
2784 break;
2785 default:
2786 Message ("previous edge bogus direction!");
2787 assert (0);
2788 }
2789 return db;
2790 }
2791
2792 /*!
2793 * \brief Break all the edges of the box that need breaking, handling
2794 * targets as they are found, and putting any moveable edges
2795 * in the return vector.
2796 */
2797 vector_t *
BreakManyEdges(struct routeone_state * s,rtree_t * targets,rtree_t * tree,vector_t * area_vec,struct E_result * ans,routebox_t * rb,edge_t * e)2798 BreakManyEdges (struct routeone_state * s, rtree_t * targets, rtree_t * tree,
2799 vector_t * area_vec, struct E_result * ans, routebox_t * rb,
2800 edge_t * e)
2801 {
2802 struct break_info bi;
2803 vector_t *edges;
2804 heap_t *heap[4];
2805 Coord first, last;
2806 Coord bloat;
2807 direction_t dir;
2808 routebox_t fake;
2809
2810 edges = vector_create ();
2811 bi.ignore_source = rb->parent.expansion_area->flags.source;
2812 bi.parent = rb;
2813 /* we add 2 to the bloat.
2814 * 1 will get us to the actual blocker that Expand() hit
2815 * but 1 more is needed because the new expansion edges
2816 * move out by 1 so they don't overlap their parents
2817 * this extra expansion could "trap" the edge if
2818 * there is a blocker 2 units from the original rb,
2819 * it is 1 unit from the new expansion edge which
2820 * would prevent expansion. So we want to break the
2821 * edge on it now to avoid the trap.
2822 */
2823
2824 bloat = AutoRouteParameters.bloat + 2;
2825 /* for corner expansion, we need to have a fake blocker
2826 * to prevent expansion back where we came from since
2827 * we still need to break portions of all 4 edges
2828 */
2829 if (e->expand_dir == NE || e->expand_dir == SE ||
2830 e->expand_dir == SW || e->expand_dir == NW)
2831 {
2832 BoxType *fb = (BoxType *) &fake.sbox;
2833 memset (&fake, 0, sizeof (fake));
2834 *fb = e->rb->sbox;
2835 fake.flags.fixed = 1; /* this stops expansion there */
2836 fake.type = LINE;
2837 fake.style = AutoRouteParameters.style;
2838 #ifndef NDEBUG
2839 /* the routbox_is_good checker wants a lot more! */
2840 fake.flags.inited = 1;
2841 fb = (BoxType *) &fake.box;
2842 *fb = e->rb->sbox;
2843 fake.same_net.next = fake.same_net.prev = &fake;
2844 fake.same_subnet.next = fake.same_subnet.prev = &fake;
2845 fake.original_subnet.next = fake.original_subnet.prev = &fake;
2846 fake.different_net.next = fake.different_net.prev = &fake;
2847 #endif
2848 }
2849 /* gather all of the blockers in heaps so they can be accessed
2850 * in clockwise order, which allows finding corners that can
2851 * be expanded.
2852 */
2853 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
2854 {
2855 /* don't break the edge we came from */
2856 if (e->expand_dir != ((dir + 2) % 4))
2857 {
2858 heap[dir] = heap_create ();
2859 bi.box = bloat_box (&rb->sbox, bloat);
2860 bi.heap = heap[dir];
2861 bi.dir = dir;
2862 /* convert to edge */
2863 switch (dir)
2864 {
2865 case NORTH:
2866 bi.box.Y2 = bi.box.Y1 + bloat + 1;
2867 /* for corner expansion, block the start edges and
2868 * limit the blocker search to only the new edge segment
2869 */
2870 if (e->expand_dir == SE || e->expand_dir == SW)
2871 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2872 if (e->expand_dir == SE)
2873 bi.box.X1 = e->rb->sbox.X2;
2874 if (e->expand_dir == SW)
2875 bi.box.X2 = e->rb->sbox.X1;
2876 rb->n = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2877 break;
2878 case EAST:
2879 bi.box.X1 = bi.box.X2 - bloat - 1;
2880 /* corner, same as above */
2881 if (e->expand_dir == SW || e->expand_dir == NW)
2882 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2883 if (e->expand_dir == SW)
2884 bi.box.Y1 = e->rb->sbox.Y2;
2885 if (e->expand_dir == NW)
2886 bi.box.Y2 = e->rb->sbox.Y1;
2887 rb->e = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2888 break;
2889 case SOUTH:
2890 bi.box.Y1 = bi.box.Y2 - bloat - 1;
2891 /* corner, same as above */
2892 if (e->expand_dir == NE || e->expand_dir == NW)
2893 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2894 if (e->expand_dir == NE)
2895 bi.box.X1 = e->rb->sbox.X2;
2896 if (e->expand_dir == NW)
2897 bi.box.X2 = e->rb->sbox.X1;
2898 rb->s = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2899 break;
2900 case WEST:
2901 bi.box.X2 = bi.box.X1 + bloat + 1;
2902 /* corner, same as above */
2903 if (e->expand_dir == NE || e->expand_dir == SE)
2904 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2905 if (e->expand_dir == SE)
2906 bi.box.Y1 = e->rb->sbox.Y2;
2907 if (e->expand_dir == NE)
2908 bi.box.Y2 = e->rb->sbox.Y1;
2909 rb->w = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2910 break;
2911 default:
2912 assert (0);
2913 }
2914 }
2915 else
2916 heap[dir] = NULL;
2917 }
2918 #if 1
2919 rb->cost +=
2920 (rb->n + rb->e + rb->s +
2921 rb->w) * AutoRouteParameters.CongestionPenalty / box_area (rb->sbox);
2922 #endif
2923 /* now handle the blockers:
2924 * Go around the expansion area clockwise (North->East->South->West)
2925 * pulling blockers from the heap (which makes them come out in the right
2926 * order). Break the edges on the blocker and make the segments and corners
2927 * moveable as possible.
2928 */
2929 first = last = -1;
2930 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
2931 {
2932 if (heap[dir] && !heap_is_empty (heap[dir]))
2933 {
2934 /* pull the very first one out of the heap outside of the
2935 * heap loop because it is special; it can be part of a corner
2936 */
2937 routebox_t *blk = (routebox_t *) heap_remove_smallest (heap[dir]);
2938 BoxType b = rb->sbox;
2939 struct broken_boxes broke = break_box_edge (&b, dir, blk);
2940 if (broke.is_valid_left)
2941 {
2942 /* if last > 0, then the previous edge had a segment
2943 * joining this one, so it forms a valid corner expansion
2944 */
2945 if (last > 0)
2946 {
2947 /* make a corner expansion */
2948 BoxType db = b;
2949 switch (dir)
2950 {
2951 case EAST:
2952 /* possible NE expansion */
2953 db.X1 = last;
2954 db.Y2 = MIN (db.Y2, broke.left.Y2);
2955 break;
2956 case SOUTH:
2957 /* possible SE expansion */
2958 db.Y1 = last;
2959 db.X1 = MAX (db.X1, broke.left.X1);
2960 break;
2961 case WEST:
2962 /* possible SW expansion */
2963 db.X2 = last;
2964 db.Y1 = MAX (db.Y1, broke.left.Y1);
2965 break;
2966 default:
2967 assert (0);
2968 break;
2969 }
2970 moveable_edge (edges, &db, (direction_t)(dir + 3), rb, NULL, e, targets,
2971 s, NULL, NULL);
2972 }
2973 else if (dir == NORTH) /* north is start, so nothing "before" it */
2974 {
2975 /* save for a possible corner once we've
2976 * finished circling the box
2977 */
2978 first = MAX (b.X1, broke.left.X2);
2979 }
2980 else
2981 {
2982 /* this is just a boring straight expansion
2983 * since the orthogonal segment was blocked
2984 */
2985 moveable_edge (edges, &broke.left, dir, rb, NULL, e,
2986 targets, s, NULL, NULL);
2987 }
2988 } /* broke.is_valid_left */
2989 else if (last > 0)
2990 {
2991 /* if the last one didn't become a corner,
2992 * we still want to expand it straight out
2993 * in the direction of the previous edge,
2994 * which it belongs to.
2995 */
2996 BoxType db = previous_edge (last, dir, &rb->sbox);
2997 moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
2998 NULL, NULL);
2999 }
3000 if (broke.is_valid_center && !blk->flags.source)
3001 moveable_edge (edges, &broke.center, dir, rb, blk, e, targets, s,
3002 tree, area_vec);
3003 /* this is the heap extraction loop. We break out
3004 * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
3005 * just leave stuff in the heap when it is destroyed
3006 */
3007 while (broke.is_valid_right)
3008 {
3009 /* move the box edge to the next potential free point */
3010 switch (dir)
3011 {
3012 case NORTH:
3013 last = b.X1 = MAX (broke.right.X1, b.X1);
3014 break;
3015 case EAST:
3016 last = b.Y1 = MAX (broke.right.Y1, b.Y1);
3017 break;
3018 case SOUTH:
3019 last = b.X2 = MIN (broke.right.X2, b.X2);
3020 break;
3021 case WEST:
3022 last = b.Y2 = MIN (broke.right.Y2, b.Y2);
3023 break;
3024 default:
3025 assert (0);
3026 }
3027 if (heap_is_empty (heap[dir]))
3028 break;
3029 blk = (routebox_t *)heap_remove_smallest (heap[dir]);
3030 broke = break_box_edge (&b, dir, blk);
3031 if (broke.is_valid_left)
3032 moveable_edge (edges, &broke.left, dir, rb, NULL, e, targets,
3033 s, NULL, NULL);
3034 if (broke.is_valid_center && !blk->flags.source)
3035 moveable_edge (edges, &broke.center, dir, rb, blk, e, targets,
3036 s, tree, area_vec);
3037 }
3038 if (!broke.is_valid_right)
3039 last = -1;
3040 }
3041 else /* if (heap[dir]) */
3042 {
3043 /* nothing touched this edge! Expand the whole edge unless
3044 * (1) it hit the board edge or (2) was the source of our expansion
3045 *
3046 * for this case (of hitting nothing) we give up trying for corner
3047 * expansions because it is likely that they're not possible anyway
3048 */
3049 if ((e->expand_dir == ALL ? e->rb->came_from : e->expand_dir) !=
3050 ((dir + 2) % 4))
3051 {
3052 /* ok, we are not going back on ourselves, and the whole edge seems free */
3053 moveable_edge (edges, &rb->sbox, dir, rb, NULL, e, targets, s,
3054 NULL, NULL);
3055 }
3056
3057 if (last > 0)
3058 {
3059 /* expand the leftover from the prior direction */
3060 BoxType db = previous_edge (last, dir, &rb->sbox);
3061 moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
3062 NULL, NULL);
3063 }
3064 last = -1;
3065 }
3066 } /* for loop */
3067 /* finally, check for the NW corner now that we've come full circle */
3068 if (first > 0 && last > 0)
3069 {
3070 BoxType db = rb->sbox;
3071 db.X2 = first;
3072 db.Y2 = last;
3073 moveable_edge (edges, &db, NW, rb, NULL, e, targets, s, NULL, NULL);
3074 }
3075 else
3076 {
3077 if (first > 0)
3078 {
3079 BoxType db = rb->sbox;
3080 db.X2 = first;
3081 moveable_edge (edges, &db, NORTH, rb, NULL, e, targets, s, NULL,
3082 NULL);
3083 }
3084 else if (last > 0)
3085 {
3086 BoxType db = rb->sbox;
3087 db.Y2 = last;
3088 moveable_edge (edges, &db, WEST, rb, NULL, e, targets, s, NULL,
3089 NULL);
3090 }
3091 }
3092 /* done with all expansion edges of this box */
3093 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
3094 {
3095 if (heap[dir])
3096 heap_destroy (&heap[dir]);
3097 }
3098 return edges;
3099 }
3100
3101 static routebox_t *
rb_source(routebox_t * rb)3102 rb_source (routebox_t * rb)
3103 {
3104 while (rb && !rb->flags.source)
3105 {
3106 assert (rb->type == EXPANSION_AREA);
3107 rb = rb->parent.expansion_area;
3108 }
3109 assert (rb);
3110 return rb;
3111 }
3112
3113 /* ------------ */
3114
3115 struct foib_info
3116 {
3117 const BoxType *box;
3118 routebox_t *intersect;
3119 jmp_buf env;
3120 };
3121
3122 static int
foib_rect_in_reg(const BoxType * box,void * cl)3123 foib_rect_in_reg (const BoxType * box, void *cl)
3124 {
3125 struct foib_info *foib = (struct foib_info *) cl;
3126 BoxType rbox;
3127 routebox_t *rb = (routebox_t *) box;
3128 if (rb->flags.touched)
3129 return 0;
3130 // if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
3131 // return 0;
3132 rbox = bloat_routebox (rb);
3133 if (!box_intersect (&rbox, foib->box))
3134 return 0;
3135 /* this is an intersector! */
3136 foib->intersect = (routebox_t *) box;
3137 longjmp (foib->env, 1); /* skip to the end! */
3138 return 1;
3139 }
3140 static routebox_t *
FindOneInBox(rtree_t * rtree,routebox_t * rb)3141 FindOneInBox (rtree_t * rtree, routebox_t * rb)
3142 {
3143 struct foib_info foib;
3144 BoxType r;
3145
3146 r = rb->sbox;
3147 foib.box = &r;
3148 foib.intersect = NULL;
3149
3150 if (setjmp (foib.env) == 0)
3151 r_search (rtree, &r, NULL, foib_rect_in_reg, &foib);
3152 return foib.intersect;
3153 }
3154
3155 struct therm_info
3156 {
3157 routebox_t *plane;
3158 BoxType query;
3159 jmp_buf env;
3160 };
3161 static int
ftherm_rect_in_reg(const BoxType * box,void * cl)3162 ftherm_rect_in_reg (const BoxType * box, void *cl)
3163 {
3164 routebox_t *rbox = (routebox_t *) box;
3165 struct therm_info *ti = (struct therm_info *) cl;
3166 BoxType sq, sb;
3167
3168 if (rbox->type != PIN && rbox->type != VIA && rbox->type != VIA_SHADOW)
3169 return 0;
3170 if (rbox->group != ti->plane->group)
3171 return 0;
3172
3173 sb = shrink_routebox (rbox);
3174 switch (rbox->type)
3175 {
3176 case PIN:
3177 sq = shrink_box (&ti->query, rbox->parent.pin->Thickness);
3178 if (!box_intersect (&sb, &sq))
3179 return 0;
3180 sb.X1 = rbox->parent.pin->X;
3181 sb.Y1 = rbox->parent.pin->Y;
3182 break;
3183 case VIA:
3184 if (rbox->flags.fixed)
3185 {
3186 sq = shrink_box (&ti->query, rbox->parent.via->Thickness);
3187 sb.X1 = rbox->parent.pin->X;
3188 sb.Y1 = rbox->parent.pin->Y;
3189 }
3190 else
3191 {
3192 sq = shrink_box (&ti->query, rbox->style->Diameter);
3193 sb.X1 = CENTER_X (sb);
3194 sb.Y1 = CENTER_Y (sb);
3195 }
3196 if (!box_intersect (&sb, &sq))
3197 return 0;
3198 break;
3199 case VIA_SHADOW:
3200 sq = shrink_box (&ti->query, rbox->style->Diameter);
3201 if (!box_intersect (&sb, &sq))
3202 return 0;
3203 sb.X1 = CENTER_X (sb);
3204 sb.Y1 = CENTER_Y (sb);
3205 break;
3206 default:
3207 assert (0);
3208 }
3209 ti->plane = rbox;
3210 longjmp (ti->env, 1);
3211 return 1;
3212 }
3213
3214 /*!
3215 * \brief Check for a pin or via target that a polygon can just use a
3216 * thermal to connect to.
3217 */
3218 routebox_t *
FindThermable(rtree_t * rtree,routebox_t * rb)3219 FindThermable (rtree_t * rtree, routebox_t * rb)
3220 {
3221 struct therm_info info;
3222
3223 info.plane = rb;
3224 info.query = shrink_routebox (rb);
3225
3226 if (setjmp (info.env) == 0)
3227 {
3228 r_search (rtree, &info.query, NULL, ftherm_rect_in_reg, &info);
3229 return NULL;
3230 }
3231 return info.plane;
3232 }
3233
3234 /*!
3235 * \brief Route-tracing code: once we've got a path of expansion boxes,
3236 * trace a line through them to actually create the connection.
3237 */
3238 static void
RD_DrawThermal(routedata_t * rd,Coord X,Coord Y,Cardinal group,Cardinal layer,routebox_t * subnet,bool is_bad)3239 RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
3240 Cardinal group, Cardinal layer, routebox_t * subnet,
3241 bool is_bad)
3242 {
3243 routebox_t *rb;
3244 rb = (routebox_t *) malloc (sizeof (*rb));
3245 memset ((void *) rb, 0, sizeof (*rb));
3246 init_const_box (rb, X, Y, X + 1, Y + 1, 0);
3247 rb->group = group;
3248 rb->layer = layer;
3249 rb->flags.fixed = 0;
3250 rb->flags.is_bad = is_bad;
3251 rb->flags.is_odd = AutoRouteParameters.is_odd;
3252 rb->flags.circular = 0;
3253 rb->style = AutoRouteParameters.style;
3254 rb->type = THERMAL;
3255 InitLists (rb);
3256 MergeNets (rb, subnet, NET);
3257 MergeNets (rb, subnet, SUBNET);
3258 /* add it to the r-tree, this may be the whole route! */
3259 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3260 rb->flags.homeless = 0;
3261 }
3262
3263 static void
RD_DrawVia(routedata_t * rd,Coord X,Coord Y,Coord radius,routebox_t * subnet,bool is_bad)3264 RD_DrawVia (routedata_t * rd, Coord X, Coord Y,
3265 Coord radius, routebox_t * subnet, bool is_bad)
3266 {
3267 routebox_t *rb, *first_via = NULL;
3268 int i;
3269 int ka = AutoRouteParameters.style->Keepaway;
3270 PinType *live_via = NULL;
3271
3272 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3273 {
3274 live_via = CreateNewVia (PCB->Data, X, Y, radius * 2,
3275 2 * AutoRouteParameters.style->Keepaway, 0,
3276 AutoRouteParameters.style->Hole, NULL,
3277 MakeFlags (0));
3278 if (live_via != NULL)
3279 DrawVia (live_via);
3280 }
3281
3282 /* a via cuts through every layer group */
3283 for (i = 0; i < max_group; i++)
3284 {
3285 if (!is_layer_group_active[i])
3286 continue;
3287 rb = (routebox_t *) malloc (sizeof (*rb));
3288 memset ((void *) rb, 0, sizeof (*rb));
3289 init_const_box (rb,
3290 /*X1 */ X - radius, /*Y1 */ Y - radius,
3291 /*X2 */ X + radius + 1, /*Y2 */ Y + radius + 1, ka);
3292 rb->group = i;
3293 rb->flags.fixed = 0; /* indicates that not on PCB yet */
3294 rb->flags.is_odd = AutoRouteParameters.is_odd;
3295 rb->flags.is_bad = is_bad;
3296 rb->came_from = ALL;
3297 rb->flags.circular = true;
3298 rb->style = AutoRouteParameters.style;
3299 rb->pass = AutoRouteParameters.pass;
3300 if (first_via == NULL)
3301 {
3302 rb->type = VIA;
3303 rb->parent.via = NULL; /* indicates that not on PCB yet */
3304 first_via = rb;
3305 /* only add the first via to mtspace, not the shadows too */
3306 mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
3307 rb->style->Keepaway);
3308 }
3309 else
3310 {
3311 rb->type = VIA_SHADOW;
3312 rb->parent.via_shadow = first_via;
3313 }
3314 InitLists (rb);
3315 /* add these to proper subnet. */
3316 MergeNets (rb, subnet, NET);
3317 MergeNets (rb, subnet, SUBNET);
3318 assert (__routebox_is_good (rb));
3319 /* and add it to the r-tree! */
3320 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3321 rb->flags.homeless = 0; /* not homeless anymore */
3322 rb->livedraw_obj.via = live_via;
3323 }
3324 }
3325 static void
RD_DrawLine(routedata_t * rd,Coord X1,Coord Y1,Coord X2,Coord Y2,Coord halfthick,Cardinal group,routebox_t * subnet,bool is_bad,bool is_45)3326 RD_DrawLine (routedata_t * rd,
3327 Coord X1, Coord Y1, Coord X2,
3328 Coord Y2, Coord halfthick, Cardinal group,
3329 routebox_t * subnet, bool is_bad, bool is_45)
3330 {
3331 /* we hold the line in a queue to concatenate segments that
3332 * ajoin one another. That reduces the number of things in
3333 * the trees and allows conflict boxes to be larger, both of
3334 * which are really useful.
3335 */
3336 static Coord qX1 = -1, qY1, qX2, qY2;
3337 static Coord qhthick;
3338 static Cardinal qgroup;
3339 static bool qis_45, qis_bad;
3340 static routebox_t *qsn;
3341
3342 routebox_t *rb;
3343 Coord ka = AutoRouteParameters.style->Keepaway;
3344
3345 /* don't draw zero-length segments. */
3346 if (X1 == X2 && Y1 == Y2)
3347 return;
3348 if (qX1 == -1) /* first ever */
3349 {
3350 qX1 = X1;
3351 qY1 = Y1;
3352 qX2 = X2;
3353 qY2 = Y2;
3354 qhthick = halfthick;
3355 qgroup = group;
3356 qis_45 = is_45;
3357 qis_bad = is_bad;
3358 qsn = subnet;
3359 return;
3360 }
3361 /* Check if the lines concatenat. We only check the
3362 * normal expected nextpoint=lastpoint condition
3363 */
3364 if (X1 == qX2 && Y1 == qY2 && qhthick == halfthick && qgroup == group)
3365 {
3366 if (qX1 == qX2 && X1 == X2) /* everybody on the same X here */
3367 {
3368 qY2 = Y2;
3369 return;
3370 }
3371 if (qY1 == qY2 && Y1 == Y2) /* same Y all around */
3372 {
3373 qX2 = X2;
3374 return;
3375 }
3376 }
3377 /* dump the queue, no match here */
3378 if (qX1 == -1)
3379 return; /* but not this! */
3380 rb = (routebox_t *) malloc (sizeof (*rb));
3381 memset ((void *) rb, 0, sizeof (*rb));
3382 assert (is_45 ? (ABS (qX2 - qX1) == ABS (qY2 - qY1)) /* line must be 45-degrees */
3383 : (qX1 == qX2 || qY1 == qY2) /* line must be ortho */ );
3384 init_const_box (rb,
3385 /*X1 */ MIN (qX1, qX2) - qhthick,
3386 /*Y1 */ MIN (qY1, qY2) - qhthick,
3387 /*X2 */ MAX (qX1, qX2) + qhthick + 1,
3388 /*Y2 */ MAX (qY1, qY2) + qhthick + 1, ka);
3389 rb->group = qgroup;
3390 rb->type = LINE;
3391 rb->parent.line = NULL; /* indicates that not on PCB yet */
3392 rb->flags.fixed = 0; /* indicates that not on PCB yet */
3393 rb->flags.is_odd = AutoRouteParameters.is_odd;
3394 rb->flags.is_bad = qis_bad;
3395 rb->came_from = ALL;
3396 rb->flags.homeless = 0; /* we're putting this in the tree */
3397 rb->flags.nonstraight = qis_45;
3398 rb->flags.bl_to_ur = ((qX2 >= qX1 && qY2 <= qY1)
3399 || (qX2 <= qX1 && qY2 >= qY1));
3400 rb->style = AutoRouteParameters.style;
3401 rb->pass = AutoRouteParameters.pass;
3402 InitLists (rb);
3403 /* add these to proper subnet. */
3404 MergeNets (rb, qsn, NET);
3405 MergeNets (rb, qsn, SUBNET);
3406 assert (__routebox_is_good (rb));
3407 /* and add it to the r-tree! */
3408 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3409
3410 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3411 {
3412 LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
3413 LineType *line = CreateNewLineOnLayer (layer, qX1, qY1, qX2, qY2,
3414 2 * qhthick, 0, MakeFlags (0));
3415 rb->livedraw_obj.line = line;
3416 if (line != NULL)
3417 DrawLine (layer, line);
3418 }
3419
3420 /* and to the via space structures */
3421 if (AutoRouteParameters.use_vias)
3422 mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
3423 rb->style->Keepaway);
3424 usedGroup[rb->group] = true;
3425 /* and queue this one */
3426 qX1 = X1;
3427 qY1 = Y1;
3428 qX2 = X2;
3429 qY2 = Y2;
3430 qhthick = halfthick;
3431 qgroup = group;
3432 qis_45 = is_45;
3433 qis_bad = is_bad;
3434 qsn = subnet;
3435 }
3436
3437 static bool
RD_DrawManhattanLine(routedata_t * rd,const BoxType * box1,const BoxType * box2,CheapPointType start,CheapPointType end,Coord halfthick,Cardinal group,routebox_t * subnet,bool is_bad,bool last_was_x)3438 RD_DrawManhattanLine (routedata_t * rd,
3439 const BoxType * box1, const BoxType * box2,
3440 CheapPointType start, CheapPointType end,
3441 Coord halfthick, Cardinal group,
3442 routebox_t * subnet, bool is_bad, bool last_was_x)
3443 {
3444 CheapPointType knee = start;
3445 if (end.X == start.X)
3446 {
3447 RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
3448 subnet, is_bad, false);
3449 return false;
3450 }
3451 else if (end.Y == start.Y)
3452 {
3453 RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
3454 subnet, is_bad, false);
3455 return true;
3456 }
3457 /* find where knee belongs */
3458 if (point_in_box (box1, end.X, start.Y)
3459 || point_in_box (box2, end.X, start.Y))
3460 {
3461 knee.X = end.X;
3462 knee.Y = start.Y;
3463 }
3464 else
3465 {
3466 knee.X = start.X;
3467 knee.Y = end.Y;
3468 }
3469 if ((knee.X == end.X && !last_was_x) &&
3470 (point_in_box (box1, start.X, end.Y)
3471 || point_in_box (box2, start.X, end.Y)))
3472 {
3473 knee.X = start.X;
3474 knee.Y = end.Y;
3475 }
3476 assert (AutoRouteParameters.is_smoothing
3477 || point_in_closed_box (box1, knee.X, knee.Y)
3478 || point_in_closed_box (box2, knee.X, knee.Y));
3479
3480 if (1 || !AutoRouteParameters.is_smoothing)
3481 {
3482 /* draw standard manhattan paths */
3483 RD_DrawLine (rd, start.X, start.Y, knee.X, knee.Y, halfthick, group,
3484 subnet, is_bad, false);
3485 RD_DrawLine (rd, knee.X, knee.Y, end.X, end.Y, halfthick, group,
3486 subnet, is_bad, false);
3487 }
3488 else
3489 {
3490 /* draw 45-degree path across knee */
3491 Coord len45 = MIN (ABS (start.X - end.X), ABS (start.Y - end.Y));
3492 CheapPointType kneestart = knee, kneeend = knee;
3493 if (kneestart.X == start.X)
3494 kneestart.Y += (kneestart.Y > start.Y) ? -len45 : len45;
3495 else
3496 kneestart.X += (kneestart.X > start.X) ? -len45 : len45;
3497 if (kneeend.X == end.X)
3498 kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45;
3499 else
3500 kneeend.X += (kneeend.X > end.X) ? -len45 : len45;
3501 RD_DrawLine (rd, start.X, start.Y, kneestart.X, kneestart.Y, halfthick,
3502 group, subnet, is_bad, false);
3503 RD_DrawLine (rd, kneestart.X, kneestart.Y, kneeend.X, kneeend.Y,
3504 halfthick, group, subnet, is_bad, true);
3505 RD_DrawLine (rd, kneeend.X, kneeend.Y, end.X, end.Y, halfthick, group,
3506 subnet, is_bad, false);
3507 }
3508 return (knee.X != end.X);
3509 }
3510
3511 /* for smoothing, don't pack traces to min clearance gratuitously */
3512 #if 0
3513 static void
3514 add_clearance (CheapPointType * nextpoint, const BoxType * b)
3515 {
3516 if (nextpoint->X == b->X1)
3517 {
3518 if (nextpoint->X +
3519 AutoRouteParameters.style->Keepaway < (b->X1 + b->X2) / 2)
3520 nextpoint->X += AutoRouteParameters.style->Keepaway;
3521 else
3522 nextpoint->X = (b->X1 + b->X2) / 2;
3523 }
3524 else if (nextpoint->X == b->X2)
3525 {
3526 if (nextpoint->X -
3527 AutoRouteParameters.style->Keepaway > (b->X1 + b->X2) / 2)
3528 nextpoint->X -= AutoRouteParameters.style->Keepaway;
3529 else
3530 nextpoint->X = (b->X1 + b->X2) / 2;
3531 }
3532 else if (nextpoint->Y == b->Y1)
3533 {
3534 if (nextpoint->Y +
3535 AutoRouteParameters.style->Keepaway < (b->Y1 + b->Y2) / 2)
3536 nextpoint->Y += AutoRouteParameters.style->Keepaway;
3537 else
3538 nextpoint->Y = (b->Y1 + b->Y2) / 2;
3539 }
3540 else if (nextpoint->Y == b->Y2)
3541 {
3542 if (nextpoint->Y -
3543 AutoRouteParameters.style->Keepaway > (b->Y1 + b->Y2) / 2)
3544 nextpoint->Y -= AutoRouteParameters.style->Keepaway;
3545 else
3546 nextpoint->Y = (b->Y1 + b->Y2) / 2;
3547 }
3548 }
3549 #endif
3550
3551 /*!
3552 * \brief This back-traces the expansion boxes along the best path
3553 * it draws the lines that will make the actual path.
3554 *
3555 * During refinement passes, it should try to maximize the area
3556 * for other tracks so routing completion is easier.
3557 *
3558 * During smoothing passes, it should try to make a better path,
3559 * possibly using diagonals, etc. The path boxes are larger on
3560 * average now so there is more possiblity to decide on a nice
3561 * path. Any combination of lines and arcs is possible, so long
3562 * as they don't poke more than half thick outside the path box.
3563 */
3564
3565 static void
TracePath(routedata_t * rd,routebox_t * path,const routebox_t * target,routebox_t * subnet,bool is_bad)3566 TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
3567 routebox_t * subnet, bool is_bad)
3568 {
3569 bool last_x = false;
3570 Coord halfwidth = HALF_THICK (AutoRouteParameters.style->Thick);
3571 Coord radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3572 CheapPointType lastpoint, nextpoint;
3573 routebox_t *lastpath;
3574 BoxType b;
3575
3576 assert (subnet->style == AutoRouteParameters.style);
3577 /*XXX: because we round up odd thicknesses, there's the possibility that
3578 * a connecting line end-point might be 0.005 mil off the "real" edge.
3579 * don't worry about this because line *thicknesses* are always >= 0.01 mil. */
3580
3581 /* if we start with a thermal the target was a plane
3582 * or the target was a pin and the source a plane
3583 * in which case this thermal is the whole path
3584 */
3585 if (path->flags.is_thermal)
3586 {
3587 /* the target was a plane, so we need to find a good spot for the via
3588 * now. It's logical to place it close to the source box which
3589 * is where we're utlimately headed on this path. However, it
3590 * must reside in the plane as well as the via area too.
3591 */
3592 nextpoint.X = CENTER_X (path->sbox);
3593 nextpoint.Y = CENTER_Y (path->sbox);
3594 if (path->parent.expansion_area->flags.is_via)
3595 {
3596 TargetPoint (&nextpoint, rb_source (path));
3597 /* nextpoint is the middle of the source terminal now */
3598 b = clip_box (&path->sbox, &path->parent.expansion_area->sbox);
3599 nextpoint = closest_point_in_box (&nextpoint, &b);
3600 /* now it's in the via and plane near the source */
3601 }
3602 else /* no via coming, target must have been a pin */
3603 {
3604 assert (target->type == PIN);
3605 TargetPoint (&nextpoint, target);
3606 }
3607 assert (point_in_box (&path->sbox, nextpoint.X, nextpoint.Y));
3608 RD_DrawThermal (rd, nextpoint.X, nextpoint.Y, path->group,
3609 path->layer, subnet, is_bad);
3610 }
3611 else
3612 {
3613 /* start from best place of target box */
3614 lastpoint.X = CENTER_X (target->sbox);
3615 lastpoint.Y = CENTER_Y (target->sbox);
3616 TargetPoint (&lastpoint, target);
3617 if (AutoRouteParameters.last_smooth
3618 && box_in_box (&path->sbox, &target->sbox))
3619 path = path->parent.expansion_area;
3620 b = path->sbox;
3621 if (path->flags.circular)
3622 b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
3623 nextpoint = closest_point_in_box (&lastpoint, &b);
3624 if (AutoRouteParameters.last_smooth)
3625 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3626 halfwidth, path->group, subnet, is_bad, TRUE);
3627 else
3628 last_x = RD_DrawManhattanLine (rd, &target->sbox, &path->sbox,
3629 lastpoint, nextpoint, halfwidth,
3630 path->group, subnet, is_bad, last_x);
3631 }
3632 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3633 showroutebox (path);
3634 #if defined(ROUTE_VERBOSE)
3635 pcb_printf ("TRACEPOINT start %#mD\n", nextpoint.X, nextpoint.Y);
3636 #endif
3637 #endif
3638
3639 do
3640 {
3641 lastpoint = nextpoint;
3642 lastpath = path;
3643 assert (path->type == EXPANSION_AREA);
3644 path = path->parent.expansion_area;
3645 b = path->sbox;
3646 if (path->flags.circular)
3647 b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
3648 assert (b.X1 != b.X2 && b.Y1 != b.Y2); /* need someplace to put line! */
3649 /* find point on path perimeter closest to last point */
3650 /* if source terminal, try to hit a good place */
3651 nextpoint = closest_point_in_box (&lastpoint, &b);
3652 #if 0
3653 /* leave more clearance if this is a smoothing pass */
3654 if (AutoRouteParameters.is_smoothing &&
3655 (nextpoint.X != lastpoint.X || nextpoint.Y != lastpoint.Y))
3656 add_clearance (&nextpoint, &b);
3657 #endif
3658 if (path->flags.source && path->type != PLANE)
3659 TargetPoint (&nextpoint, path);
3660 assert (point_in_box (&lastpath->box, lastpoint.X, lastpoint.Y));
3661 assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
3662 #if defined(ROUTE_DEBUG_VERBOSE)
3663 printf ("TRACEPATH: ");
3664 DumpRouteBox (path);
3665 pcb_printf ("TRACEPATH: point %#mD to point %#mD layer %d\n",
3666 lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3667 path->group);
3668 #endif
3669
3670 /* draw orthogonal lines from lastpoint to nextpoint */
3671 /* knee is placed in lastpath box */
3672 /* should never cause line to leave union of lastpath/path boxes */
3673 if (AutoRouteParameters.last_smooth)
3674 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3675 halfwidth, path->group, subnet, is_bad, TRUE);
3676 else
3677 last_x = RD_DrawManhattanLine (rd, &lastpath->sbox, &path->sbox,
3678 lastpoint, nextpoint, halfwidth,
3679 path->group, subnet, is_bad, last_x);
3680 if (path->flags.is_via)
3681 { /* if via, then add via */
3682 #ifdef ROUTE_VERBOSE
3683 printf (" (vias)");
3684 #endif
3685 assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
3686 RD_DrawVia (rd, nextpoint.X, nextpoint.Y, radius, subnet, is_bad);
3687 }
3688
3689 assert (lastpath->flags.is_via || path->group == lastpath->group);
3690
3691 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3692 showroutebox (path);
3693 #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
3694 /* if this is connected to a plane, draw the thermal */
3695 if (path->flags.is_thermal || path->type == PLANE)
3696 RD_DrawThermal (rd, lastpoint.X, lastpoint.Y, path->group,
3697 path->layer, subnet, is_bad);
3698 /* when one hop from the source, make an extra path in *this* box */
3699 if (path->type == EXPANSION_AREA
3700 && path->parent.expansion_area->flags.source
3701 && path->parent.expansion_area->type != PLANE)
3702 {
3703 /* find special point on source (if it exists) */
3704 if (TargetPoint (&lastpoint, path->parent.expansion_area))
3705 {
3706 lastpoint = closest_point_in_routebox (&lastpoint, path);
3707 b = shrink_routebox (path);
3708 #if 0
3709 if (AutoRouteParameters.is_smoothing)
3710 add_clearance (&lastpoint, &b);
3711 #else
3712 if (AutoRouteParameters.last_smooth)
3713 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X,
3714 nextpoint.Y, halfwidth, path->group, subnet,
3715 is_bad, TRUE);
3716 else
3717 #endif
3718 last_x = RD_DrawManhattanLine (rd, &b, &b,
3719 nextpoint, lastpoint,
3720 halfwidth, path->group, subnet,
3721 is_bad, last_x);
3722 #if defined(ROUTE_DEBUG_VERBOSE)
3723 printf ("TRACEPATH: ");
3724 DumpRouteBox (path);
3725 pcb_printf
3726 ("TRACEPATH: (to source) point %#mD to point %#mD layer %d\n",
3727 nextpoint.X, nextpoint.Y, lastpoint.X, lastpoint.Y,
3728 path->group);
3729 #endif
3730
3731 nextpoint = lastpoint;
3732 }
3733 }
3734 }
3735 while (!path->flags.source);
3736 /* flush the line queue */
3737 RD_DrawLine (rd, -1, 0, 0, 0, 0, 0, NULL, false, false);
3738
3739 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3740 Draw ();
3741
3742 #ifdef ROUTE_DEBUG
3743 if (ddraw != NULL)
3744 gui->flush_debug_draw ();
3745 #endif
3746 }
3747
3748 /*!
3749 * \brief Create a fake "edge" used to defer via site searching.
3750 */
3751 static void
CreateSearchEdge(struct routeone_state * s,vetting_t * work,edge_t * parent,routebox_t * rb,conflict_t conflict,rtree_t * targets,bool in_plane)3752 CreateSearchEdge (struct routeone_state *s, vetting_t * work, edge_t * parent,
3753 routebox_t * rb, conflict_t conflict, rtree_t * targets,
3754 bool in_plane)
3755 {
3756 routebox_t *target;
3757 BoxType b;
3758 cost_t cost;
3759 assert (__routebox_is_good (rb));
3760 /* find the cheapest target */
3761 #if 0
3762 target =
3763 mincost_target_to_point (&parent->cost_point, max_group + 1, targets,
3764 parent->mincost_target);
3765 #else
3766 target = parent->mincost_target;
3767 #endif
3768 b = shrink_routebox (target);
3769 cost =
3770 parent->cost_to_point + AutoRouteParameters.ViaCost +
3771 cost_to_layerless_box (&rb->cost_point, 0, &b);
3772 if (cost < s->best_cost)
3773 {
3774 edge_t *ne;
3775 ne = (edge_t *)malloc (sizeof (*ne));
3776 memset ((void *) ne, 0, sizeof (*ne));
3777 assert (ne);
3778 ne->flags.via_search = 1;
3779 ne->flags.in_plane = in_plane;
3780 ne->rb = rb;
3781 if (rb->flags.homeless)
3782 RB_up_count (rb);
3783 ne->work = work;
3784 ne->mincost_target = target;
3785 ne->flags.via_conflict_level = conflict;
3786 ne->cost_to_point = parent->cost_to_point;
3787 ne->cost_point = parent->cost_point;
3788 ne->cost = cost;
3789 heap_insert (s->workheap, ne->cost, ne);
3790 }
3791 else
3792 {
3793 mtsFreeWork (&work);
3794 }
3795 }
3796
3797 static void
add_or_destroy_edge(struct routeone_state * s,edge_t * e)3798 add_or_destroy_edge (struct routeone_state *s, edge_t * e)
3799 {
3800 e->cost = edge_cost (e, s->best_cost);
3801 assert (__edge_is_good (e));
3802 assert (is_layer_group_active[e->rb->group]);
3803 if (e->cost < s->best_cost)
3804 heap_insert (s->workheap, e->cost, e);
3805 else
3806 DestroyEdge (&e);
3807 }
3808
3809 static void
best_path_candidate(struct routeone_state * s,edge_t * e,routebox_t * best_target)3810 best_path_candidate (struct routeone_state *s,
3811 edge_t * e, routebox_t * best_target)
3812 {
3813 e->cost = edge_cost (e, EXPENSIVE);
3814 if (s->best_path == NULL || e->cost < s->best_cost)
3815 {
3816 #if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
3817 printf ("New best path seen! cost = %f\n", e->cost);
3818 #endif
3819 /* new best path! */
3820 if (s->best_path && s->best_path->flags.homeless)
3821 RB_down_count (s->best_path);
3822 s->best_path = e->rb;
3823 s->best_target = best_target;
3824 s->best_cost = e->cost;
3825 assert (s->best_cost >= 0);
3826 /* don't free this when we destroy edge! */
3827 if (s->best_path->flags.homeless)
3828 RB_up_count (s->best_path);
3829 }
3830 }
3831
3832
3833 /*!
3834 * \brief Vectors for via site candidates (see mtspace.h).
3835 */
3836 struct routeone_via_site_state
3837 {
3838 vector_t *free_space_vec;
3839 vector_t *lo_conflict_space_vec;
3840 vector_t *hi_conflict_space_vec;
3841 };
3842
3843 void
add_via_sites(struct routeone_state * s,struct routeone_via_site_state * vss,mtspace_t * mtspace,routebox_t * within,conflict_t within_conflict_level,edge_t * parent_edge,rtree_t * targets,Coord shrink,bool in_plane)3844 add_via_sites (struct routeone_state *s,
3845 struct routeone_via_site_state *vss,
3846 mtspace_t * mtspace, routebox_t * within,
3847 conflict_t within_conflict_level, edge_t * parent_edge,
3848 rtree_t * targets, Coord shrink, bool in_plane)
3849 {
3850 Coord radius, keepaway;
3851 vetting_t *work;
3852 BoxType region = shrink_routebox (within);
3853 shrink_box (®ion, shrink);
3854
3855 radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3856 keepaway = AutoRouteParameters.style->Keepaway;
3857 assert (AutoRouteParameters.use_vias);
3858 /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when
3859 XXX: routing with conflicts may poke over edge. */
3860
3861 /* ask for a via box near our cost_point first */
3862 work = mtspace_query_rect (mtspace, ®ion, radius, keepaway,
3863 NULL, vss->free_space_vec,
3864 vss->lo_conflict_space_vec,
3865 vss->hi_conflict_space_vec,
3866 AutoRouteParameters.is_odd,
3867 AutoRouteParameters.with_conflicts,
3868 &parent_edge->cost_point);
3869 if (!work)
3870 return;
3871 CreateSearchEdge (s, work, parent_edge, within, within_conflict_level,
3872 targets, in_plane);
3873 }
3874
3875 void
do_via_search(edge_t * search,struct routeone_state * s,struct routeone_via_site_state * vss,mtspace_t * mtspace,rtree_t * targets)3876 do_via_search (edge_t * search, struct routeone_state *s,
3877 struct routeone_via_site_state *vss, mtspace_t * mtspace,
3878 rtree_t * targets)
3879 {
3880 int i, j, count = 0;
3881 Coord radius, keepaway;
3882 vetting_t *work;
3883 routebox_t *within;
3884 conflict_t within_conflict_level;
3885
3886 radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3887 keepaway = AutoRouteParameters.style->Keepaway;
3888 work = mtspace_query_rect (mtspace, NULL, 0, 0,
3889 search->work, vss->free_space_vec,
3890 vss->lo_conflict_space_vec,
3891 vss->hi_conflict_space_vec,
3892 AutoRouteParameters.is_odd,
3893 AutoRouteParameters.with_conflicts, NULL);
3894 within = search->rb;
3895 within_conflict_level = search->flags.via_conflict_level;
3896 for (i = 0; i < 3; i++)
3897 {
3898 vector_t *v =
3899 (i == NO_CONFLICT ? vss->free_space_vec :
3900 i == LO_CONFLICT ? vss->lo_conflict_space_vec :
3901 i == HI_CONFLICT ? vss->hi_conflict_space_vec : NULL);
3902 assert (v);
3903 while (!vector_is_empty (v))
3904 {
3905 BoxType cliparea;
3906 BoxType *area = (BoxType *)vector_remove_last (v);
3907 if (!(i == NO_CONFLICT || AutoRouteParameters.with_conflicts))
3908 {
3909 free (area);
3910 continue;
3911 }
3912 /* answers are bloated by radius + keepaway */
3913 cliparea = shrink_box (area, radius + keepaway);
3914 close_box (&cliparea);
3915 free (area);
3916 assert (box_is_good (&cliparea));
3917 count++;
3918 for (j = 0; j < max_group; j++)
3919 {
3920 edge_t *ne;
3921 if (j == within->group || !is_layer_group_active[j])
3922 continue;
3923 ne = CreateViaEdge (&cliparea, j, within, search,
3924 within_conflict_level, (conflict_t)i, targets);
3925 add_or_destroy_edge (s, ne);
3926 }
3927 }
3928 }
3929 /* prevent freeing of work when this edge is destroyed */
3930 search->flags.via_search = 0;
3931 if (!work)
3932 return;
3933 CreateSearchEdge (s, work, search, within, within_conflict_level, targets,
3934 search->flags.in_plane);
3935 assert (vector_is_empty (vss->free_space_vec));
3936 assert (vector_is_empty (vss->lo_conflict_space_vec));
3937 assert (vector_is_empty (vss->hi_conflict_space_vec));
3938 }
3939
3940 /* vector of expansion areas to be eventually removed from r-tree
3941 * this is a global for troubleshooting
3942 */
3943 vector_t *area_vec;
3944
3945 /* some routines for use in gdb while debugging */
3946 #if defined(ROUTE_DEBUG)
3947 static void
list_conflicts(routebox_t * rb)3948 list_conflicts (routebox_t * rb)
3949 {
3950 int i, n;
3951 if (!rb->conflicts_with)
3952 return;
3953 n = vector_size (rb->conflicts_with);
3954 for (i = 0; i < n; i++)
3955 printf ("%p, ", vector_element (rb->conflicts_with, i));
3956 }
3957
3958 static void
show_area_vec(int lay)3959 show_area_vec (int lay)
3960 {
3961 int n, save;
3962
3963 if (!area_vec)
3964 return;
3965 save = showboxen;
3966 showboxen = lay;
3967 for (n = 0; n < vector_size (area_vec); n++)
3968 {
3969 routebox_t *rb = (routebox_t *) vector_element (area_vec, n);
3970 showroutebox (rb);
3971 }
3972 showboxen = save;
3973 }
3974
3975 static bool
net_id(routebox_t * rb,long int id)3976 net_id (routebox_t * rb, long int id)
3977 {
3978 routebox_t *p;
3979 LIST_LOOP (rb, same_net, p);
3980 if (p->flags.source && p->parent.pad->ID == id)
3981 return true;
3982 END_LOOP;
3983 return false;
3984 }
3985
3986 static void
trace_parents(routebox_t * rb)3987 trace_parents (routebox_t * rb)
3988 {
3989 while (rb && rb->type == EXPANSION_AREA)
3990 {
3991 printf (" %p ->", rb);
3992 rb = rb->parent.expansion_area;
3993 }
3994 if (rb)
3995 printf (" %p is source\n", rb);
3996 else
3997 printf ("NULL!\n");
3998 }
3999
4000 static void
show_one(routebox_t * rb)4001 show_one (routebox_t * rb)
4002 {
4003 int save = showboxen;
4004 showboxen = -1;
4005 showroutebox (rb);
4006 showboxen = save;
4007 }
4008
4009 static void
show_path(routebox_t * rb)4010 show_path (routebox_t * rb)
4011 {
4012 while (rb && rb->type == EXPANSION_AREA)
4013 {
4014 show_one (rb);
4015 rb = rb->parent.expansion_area;
4016 }
4017 show_one (rb);
4018 }
4019
4020 static void
show_sources(routebox_t * rb)4021 show_sources (routebox_t * rb)
4022 {
4023 routebox_t *p;
4024 if (!rb->flags.source && !rb->flags.target)
4025 {
4026 printf ("start with a source or target please\n");
4027 return;
4028 }
4029 LIST_LOOP (rb, same_net, p);
4030 if (p->flags.source)
4031 show_one (p);
4032 END_LOOP;
4033 }
4034
4035 #endif
4036
4037 static int
__conflict_source(const BoxType * box,void * cl)4038 __conflict_source (const BoxType * box, void *cl)
4039 {
4040 routebox_t *rb = (routebox_t *) box;
4041 if (rb->flags.touched || rb->flags.fixed)
4042 return 0;
4043 else
4044 {
4045 routebox_t *dis = (routebox_t *) cl;
4046 path_conflicts (dis, rb, false);
4047 touch_conflicts (dis->conflicts_with, 1);
4048 }
4049 return 1;
4050 }
4051
4052 static void
source_conflicts(rtree_t * tree,routebox_t * rb)4053 source_conflicts (rtree_t * tree, routebox_t * rb)
4054 {
4055 if (!AutoRouteParameters.with_conflicts)
4056 return;
4057 r_search (tree, &rb->sbox, NULL, __conflict_source, rb);
4058 touch_conflicts (NULL, 1);
4059 }
4060
4061 struct routeone_status
4062 {
4063 bool found_route;
4064 int route_had_conflicts;
4065 cost_t best_route_cost;
4066 bool net_completely_routed;
4067 };
4068
4069
4070 static struct routeone_status
RouteOne(routedata_t * rd,routebox_t * from,routebox_t * to,int max_edges)4071 RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
4072 {
4073 struct routeone_status result;
4074 routebox_t *p;
4075 int seen, i;
4076 const BoxType **target_list;
4077 int num_targets;
4078 rtree_t *targets;
4079 /* vector of source edges for filtering */
4080 vector_t *source_vec;
4081 /* working vector */
4082 vector_t *edge_vec;
4083
4084 struct routeone_state s;
4085 struct routeone_via_site_state vss;
4086
4087 assert (rd && from);
4088 result.route_had_conflicts = 0;
4089 /* no targets on to/from net need keepaway areas */
4090 LIST_LOOP (from, same_net, p);
4091 p->flags.nobloat = 1;
4092 END_LOOP;
4093 /* set 'source' flags */
4094 LIST_LOOP (from, same_subnet, p);
4095 if (!p->flags.nonstraight)
4096 p->flags.source = 1;
4097 END_LOOP;
4098
4099 /* count up the targets */
4100 num_targets = 0;
4101 seen = 0;
4102 /* remove source/target flags from non-straight obstacles, because they
4103 * don't fill their bounding boxes and so connecting to them
4104 * after we've routed is problematic. Better solution? */
4105 if (to)
4106 { /* if we're routing to a specific target */
4107 if (!to->flags.source)
4108 { /* not already connected */
4109 /* check that 'to' and 'from' are on the same net */
4110 seen = 0;
4111 #ifndef NDEBUG
4112 LIST_LOOP (from, same_net, p);
4113 if (p == to)
4114 seen = 1;
4115 END_LOOP;
4116 #endif
4117 assert (seen); /* otherwise from and to are on different nets! */
4118 /* set target flags only on 'to's subnet */
4119 LIST_LOOP (to, same_subnet, p);
4120 if (!p->flags.nonstraight && is_layer_group_active[p->group])
4121 {
4122 p->flags.target = 1;
4123 num_targets++;
4124 }
4125 END_LOOP;
4126 }
4127 }
4128 else
4129 {
4130 /* all nodes on the net but not connected to from are targets */
4131 LIST_LOOP (from, same_net, p);
4132 if (!p->flags.source && is_layer_group_active[p->group]
4133 && !p->flags.nonstraight)
4134 {
4135 p->flags.target = 1;
4136 num_targets++;
4137 }
4138 END_LOOP;
4139 }
4140
4141 /* if no targets, then net is done! reset flags and return. */
4142 if (num_targets == 0)
4143 {
4144 LIST_LOOP (from, same_net, p);
4145 p->flags.source = p->flags.target = p->flags.nobloat = 0;
4146 END_LOOP;
4147 result.found_route = false;
4148 result.net_completely_routed = true;
4149 result.best_route_cost = 0;
4150 result.route_had_conflicts = 0;
4151
4152 return result;
4153 }
4154 result.net_completely_routed = false;
4155
4156 /* okay, there's stuff to route */
4157 assert (!from->flags.target);
4158 assert (num_targets > 0);
4159 /* create list of target pointers and from that a r-tree of targets */
4160 target_list = (const BoxType **)malloc (num_targets * sizeof (*target_list));
4161 i = 0;
4162 LIST_LOOP (from, same_net, p);
4163 if (p->flags.target)
4164 {
4165 target_list[i++] = &p->box;
4166 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_TARGETS)
4167 showroutebox (p);
4168 #endif
4169 }
4170 END_LOOP;
4171 targets = r_create_tree ((const BoxType **)target_list, i, 0);
4172 assert (i <= num_targets);
4173 free (target_list);
4174
4175 source_vec = vector_create ();
4176 /* touch the source subnet to prepare check for conflictors */
4177 LIST_LOOP (from, same_subnet, p);
4178 p->flags.touched = 1;
4179 END_LOOP;
4180 LIST_LOOP (from, same_subnet, p);
4181 {
4182 /* we need the test for 'source' because this box may be nonstraight */
4183 if (p->flags.source && is_layer_group_active[p->group])
4184 {
4185 CheapPointType cp;
4186 edge_t *e;
4187 BoxType b = shrink_routebox (p);
4188
4189 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
4190 showroutebox (p);
4191 #endif
4192 /* may expand in all directions from source; center edge cost point. */
4193 /* note that planes shouldn't really expand, but we need an edge */
4194
4195 cp.X = CENTER_X (b);
4196 cp.Y = CENTER_Y (b);
4197 e = CreateEdge (p, cp.X, cp.Y, 0, NULL, ALL, targets);
4198 cp = closest_point_in_box (&cp, &e->mincost_target->sbox);
4199 cp = closest_point_in_box (&cp, &b);
4200 e->cost_point = cp;
4201 p->cost_point = cp;
4202 source_conflicts (rd->layergrouptree[p->group], p);
4203 vector_append (source_vec, e);
4204 }
4205 }
4206 END_LOOP;
4207 LIST_LOOP (from, same_subnet, p);
4208 p->flags.touched = 0;
4209 END_LOOP;
4210 /* break source edges; some edges may be too near obstacles to be able
4211 * to exit from. */
4212
4213 /* okay, main expansion-search routing loop. */
4214 /* set up the initial activity heap */
4215 s.workheap = heap_create ();
4216 assert (s.workheap);
4217 while (!vector_is_empty (source_vec))
4218 {
4219 edge_t *e = (edge_t *)vector_remove_last (source_vec);
4220 assert (is_layer_group_active[e->rb->group]);
4221 e->cost = edge_cost (e, EXPENSIVE);
4222 heap_insert (s.workheap, e->cost, e);
4223 }
4224 vector_destroy (&source_vec);
4225 /* okay, process items from heap until it is empty! */
4226 s.best_path = NULL;
4227 s.best_cost = EXPENSIVE;
4228 area_vec = vector_create ();
4229 edge_vec = vector_create ();
4230 vss.free_space_vec = vector_create ();
4231 vss.lo_conflict_space_vec = vector_create ();
4232 vss.hi_conflict_space_vec = vector_create ();
4233 while (!heap_is_empty (s.workheap))
4234 {
4235 edge_t *e = (edge_t *)heap_remove_smallest (s.workheap);
4236 #ifdef ROUTE_DEBUG
4237 if (aabort)
4238 goto dontexpand;
4239 #endif
4240 /* don't bother expanding this edge if the minimum possible edge cost
4241 * is already larger than the best edge cost we've found. */
4242 if (s.best_path && e->cost >= s.best_cost)
4243 {
4244 heap_free (s.workheap, KillEdge);
4245 goto dontexpand; /* skip this edge */
4246 }
4247 /* surprisingly it helps to give up and not try too hard to find
4248 * a route! This is not only faster, but results in better routing.
4249 * who would have guessed?
4250 */
4251 if (seen++ > max_edges)
4252 goto dontexpand;
4253 assert (__edge_is_good (e));
4254 /* mark or unmark conflictors as needed */
4255 touch_conflicts (e->rb->conflicts_with, 1);
4256 if (e->flags.via_search)
4257 {
4258 do_via_search (e, &s, &vss, rd->mtspace, targets);
4259 goto dontexpand;
4260 }
4261 /* we should never add edges on inactive layer groups to the heap. */
4262 assert (is_layer_group_active[e->rb->group]);
4263 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
4264 //showedge (e);
4265 #endif
4266 if (e->rb->flags.is_thermal)
4267 {
4268 best_path_candidate (&s, e, e->mincost_target);
4269 goto dontexpand;
4270 }
4271 /* for a plane, look for quick connections with thermals or vias */
4272 if (e->rb->type == PLANE)
4273 {
4274 routebox_t *pin = FindThermable (targets, e->rb);
4275 if (pin)
4276 {
4277 BoxType b = shrink_routebox (pin);
4278 edge_t *ne;
4279 routebox_t *nrb;
4280 assert (pin->flags.target);
4281 nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
4282 nrb->flags.is_thermal = 1;
4283 /* moving through the plane is free */
4284 e->cost_point.X = b.X1;
4285 e->cost_point.Y = b.Y1;
4286 ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, pin);
4287 best_path_candidate (&s, ne, pin);
4288 DestroyEdge (&ne);
4289 }
4290 else
4291 {
4292 /* add in possible via sites in plane */
4293 if (AutoRouteParameters.use_vias &&
4294 e->cost + AutoRouteParameters.ViaCost < s.best_cost)
4295 {
4296 /* we need a giant thermal */
4297 routebox_t *nrb =
4298 CreateExpansionArea (&e->rb->sbox, e->rb->group, e->rb,
4299 true, e);
4300 edge_t *ne = CreateEdge2 (nrb, e->expand_dir, e, NULL,
4301 e->mincost_target);
4302 nrb->flags.is_thermal = 1;
4303 add_via_sites (&s, &vss, rd->mtspace, nrb, NO_CONFLICT, ne,
4304 targets, e->rb->style->Diameter, true);
4305 }
4306 }
4307 goto dontexpand; /* planes only connect via thermals */
4308 }
4309 if (e->flags.is_via)
4310 { /* special case via */
4311 routebox_t *intersecting;
4312 assert (AutoRouteParameters.use_vias);
4313 assert (e->expand_dir == ALL);
4314 assert (vector_is_empty (edge_vec));
4315 /* if there is already something here on this layer (like an
4316 * EXPANSION_AREA), then we don't want to expand from here
4317 * at least not inside the expansion area. A PLANE on the
4318 * other hand may be a target, or not.
4319 */
4320 intersecting =
4321 FindOneInBox (rd->layergrouptree[e->rb->group], e->rb);
4322
4323 if (intersecting && intersecting->flags.target
4324 && intersecting->type == PLANE)
4325 {
4326 /* we have hit a plane */
4327 edge_t *ne;
4328 routebox_t *nrb;
4329 BoxType b = shrink_routebox (e->rb);
4330 /* limit via region to that inside the plane */
4331 clip_box (&b, &intersecting->sbox);
4332 nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
4333 nrb->flags.is_thermal = 1;
4334 ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, intersecting);
4335 best_path_candidate (&s, ne, intersecting);
4336 DestroyEdge (&ne);
4337 goto dontexpand;
4338 }
4339 else if (intersecting == NULL)
4340 {
4341 /* this via candidate is in an open area; add it to r-tree as
4342 * an expansion area */
4343 assert (e->rb->type == EXPANSION_AREA && e->rb->flags.is_via);
4344 /*assert (!r_search (rd->layergrouptree[e->rb->group],
4345 &e->rb->box, NULL, no_planes,0));
4346 */
4347 r_insert_entry (rd->layergrouptree[e->rb->group], &e->rb->box,
4348 1);
4349 e->rb->flags.homeless = 0; /* not homeless any more */
4350 /* add to vector of all expansion areas in r-tree */
4351 vector_append (area_vec, e->rb);
4352 /* mark reset refcount to 0, since this is not homeless any more. */
4353 e->rb->refcount = 0;
4354 /* go ahead and expand this edge! */
4355 }
4356 else if (1)
4357 goto dontexpand;
4358 else if (0)
4359 { /* XXX: disabling this causes no via
4360 collisions. */
4361 BoxType a = bloat_routebox (intersecting), b;
4362 edge_t *ne;
4363 int i, j;
4364 /* something intersects this via candidate. split via candidate
4365 * into pieces and add these pieces to the workheap. */
4366 for (i = 0; i < 3; i++)
4367 {
4368 for (j = 0; j < 3; j++)
4369 {
4370 b = shrink_routebox (e->rb);
4371 switch (i)
4372 {
4373 case 0:
4374 b.X2 = MIN (b.X2, a.X1);
4375 break; /* left */
4376 case 1:
4377 b.X1 = MAX (b.X1, a.X1);
4378 b.X2 = MIN (b.X2, a.X2);
4379 break; /*c */
4380 case 2:
4381 b.X1 = MAX (b.X1, a.X2);
4382 break; /* right */
4383 default:
4384 assert (0);
4385 }
4386 switch (j)
4387 {
4388 case 0:
4389 b.Y2 = MIN (b.Y2, a.Y1);
4390 break; /* top */
4391 case 1:
4392 b.Y1 = MAX (b.Y1, a.Y1);
4393 b.Y2 = MIN (b.Y2, a.Y2);
4394 break; /*c */
4395 case 2:
4396 b.Y1 = MAX (b.Y1, a.Y2);
4397 break; /* bottom */
4398 default:
4399 assert (0);
4400 }
4401 /* skip if this box is not valid */
4402 if (!(b.X1 < b.X2 && b.Y1 < b.Y2))
4403 continue;
4404 if (i == 1 && j == 1)
4405 {
4406 /* this bit of the via space is obstructed. */
4407 if (intersecting->type == EXPANSION_AREA
4408 || intersecting->flags.fixed)
4409 continue; /* skip this bit, it's already been done. */
4410 /* create an edge with conflicts, if enabled */
4411 if (!AutoRouteParameters.with_conflicts)
4412 continue;
4413 ne = CreateEdgeWithConflicts (&b, intersecting, e, 1
4414 /*cost penalty to box */
4415 , targets);
4416 add_or_destroy_edge (&s, ne);
4417 }
4418 else
4419 {
4420 /* if this is not the intersecting piece, create a new
4421 * (hopefully unobstructed) via edge and add it back to the
4422 * workheap. */
4423 ne =
4424 CreateViaEdge (&b, e->rb->group,
4425 e->rb->parent.expansion_area, e,
4426 e->flags.via_conflict_level,
4427 NO_CONFLICT
4428 /* value here doesn't matter */
4429 , targets);
4430 add_or_destroy_edge (&s, ne);
4431 }
4432 }
4433 }
4434 goto dontexpand;
4435 }
4436 /* between the time these edges are inserted and the
4437 * time they are processed, new expansion boxes (which
4438 * conflict with these edges) may be added to the graph!
4439 * w.o vias this isn't a problem because the broken box
4440 * is not homeless. */
4441 }
4442 if (1)
4443 {
4444 routebox_t *nrb;
4445 struct E_result *ans;
4446 BoxType b;
4447 vector_t *broken;
4448 if (e->flags.is_interior)
4449 {
4450 assert (AutoRouteParameters.with_conflicts); /* no interior edges unless
4451 routing with conflicts! */
4452 assert (e->rb->conflicts_with);
4453 b = e->rb->sbox;
4454 switch (e->rb->came_from)
4455 {
4456 case NORTH:
4457 b.Y2 = b.Y1 + 1;
4458 b.X1 = CENTER_X (b);
4459 b.X2 = b.X1 + 1;
4460 break;
4461 case EAST:
4462 b.X1 = b.X2 - 1;
4463 b.Y1 = CENTER_Y (b);
4464 b.Y2 = b.Y1 + 1;
4465 break;
4466 case SOUTH:
4467 b.Y1 = b.Y2 - 1;
4468 b.X1 = CENTER_X (b);
4469 b.X2 = b.X1 + 1;
4470 break;
4471 case WEST:
4472 b.X2 = b.X1 + 1;
4473 b.Y1 = CENTER_Y (b);
4474 b.Y2 = b.Y1 + 1;
4475 break;
4476 default:
4477 assert (0);
4478 }
4479 }
4480 /* sources may not expand to their own edges because of
4481 * adjacent blockers.
4482 */
4483 else if (e->rb->flags.source)
4484 b = box_center (&e->rb->sbox);
4485 else
4486 b = e->rb->sbox;
4487 ans = Expand (rd->layergrouptree[e->rb->group], e, &b);
4488 if (!box_intersect (&ans->inflated, &ans->orig))
4489 goto dontexpand;
4490 #if 0
4491 /* skip if it didn't actually expand */
4492 if (ans->inflated.X1 >= e->rb->sbox.X1 &&
4493 ans->inflated.X2 <= e->rb->sbox.X2 &&
4494 ans->inflated.Y1 >= e->rb->sbox.Y1 &&
4495 ans->inflated.Y2 <= e->rb->sbox.Y2)
4496 goto dontexpand;
4497 #endif
4498
4499 if (!box_is_good (&ans->inflated))
4500 goto dontexpand;
4501 nrb = CreateExpansionArea (&ans->inflated, e->rb->group, e->rb,
4502 true, e);
4503 r_insert_entry (rd->layergrouptree[nrb->group], &nrb->box, 1);
4504 vector_append (area_vec, nrb);
4505 nrb->flags.homeless = 0; /* not homeless any more */
4506 broken =
4507 BreakManyEdges (&s, targets, rd->layergrouptree[nrb->group],
4508 area_vec, ans, nrb, e);
4509 while (!vector_is_empty (broken))
4510 {
4511 edge_t *ne = (edge_t *)vector_remove_last (broken);
4512 add_or_destroy_edge (&s, ne);
4513 }
4514 vector_destroy (&broken);
4515
4516 /* add in possible via sites in nrb */
4517 if (AutoRouteParameters.use_vias && !e->rb->flags.is_via &&
4518 e->cost + AutoRouteParameters.ViaCost < s.best_cost)
4519 add_via_sites (&s, &vss,
4520 rd->mtspace, nrb, NO_CONFLICT, e, targets, 0,
4521 false);
4522 goto dontexpand;
4523 }
4524 dontexpand:
4525 DestroyEdge (&e);
4526 }
4527 touch_conflicts (NULL, 1);
4528 heap_destroy (&s.workheap);
4529 r_destroy_tree (&targets);
4530 assert (vector_is_empty (edge_vec));
4531 vector_destroy (&edge_vec);
4532
4533 /* we should have a path in best_path now */
4534 if (s.best_path)
4535 {
4536 routebox_t *rb;
4537 #ifdef ROUTE_VERBOSE
4538 printf ("%d:%d RC %.0f", ro++, seen, s.best_cost);
4539 #endif
4540 result.found_route = true;
4541 result.best_route_cost = s.best_cost;
4542 /* determine if the best path had conflicts */
4543 result.route_had_conflicts = 0;
4544 if (AutoRouteParameters.with_conflicts && s.best_path->conflicts_with)
4545 {
4546 while (!vector_is_empty (s.best_path->conflicts_with))
4547 {
4548 rb = (routebox_t *)vector_remove_last (s.best_path->conflicts_with);
4549 rb->flags.is_bad = 1;
4550 result.route_had_conflicts++;
4551 }
4552 }
4553 #ifdef ROUTE_VERBOSE
4554 if (result.route_had_conflicts)
4555 printf (" (%d conflicts)", result.route_had_conflicts);
4556 #endif
4557 if (result.route_had_conflicts < AutoRouteParameters.hi_conflict)
4558 {
4559 /* back-trace the path and add lines/vias to r-tree */
4560 TracePath (rd, s.best_path, s.best_target, from,
4561 result.route_had_conflicts);
4562 MergeNets (from, s.best_target, SUBNET);
4563 }
4564 else
4565 {
4566 #ifdef ROUTE_VERBOSE
4567 printf (" (too many in fact)");
4568 #endif
4569 result.found_route = false;
4570 }
4571 #ifdef ROUTE_VERBOSE
4572 printf ("\n");
4573 #endif
4574 }
4575 else
4576 {
4577 #ifdef ROUTE_VERBOSE
4578 printf ("%d:%d NO PATH FOUND.\n", ro++, seen);
4579 #endif
4580 result.best_route_cost = s.best_cost;
4581 result.found_route = false;
4582 }
4583 /* now remove all expansion areas from the r-tree. */
4584 while (!vector_is_empty (area_vec))
4585 {
4586 routebox_t *rb = (routebox_t *)vector_remove_last (area_vec);
4587 assert (!rb->flags.homeless);
4588 if (rb->conflicts_with
4589 && rb->parent.expansion_area->conflicts_with != rb->conflicts_with)
4590 vector_destroy (&rb->conflicts_with);
4591 r_delete_entry (rd->layergrouptree[rb->group], &rb->box);
4592 }
4593 vector_destroy (&area_vec);
4594 /* clean up; remove all 'source', 'target', and 'nobloat' flags */
4595 LIST_LOOP (from, same_net, p);
4596 if (p->flags.source && p->conflicts_with)
4597 vector_destroy (&p->conflicts_with);
4598 p->flags.touched = p->flags.source = p->flags.target = p->flags.nobloat = 0;
4599 END_LOOP;
4600
4601 vector_destroy (&vss.free_space_vec);
4602 vector_destroy (&vss.lo_conflict_space_vec);
4603 vector_destroy (&vss.hi_conflict_space_vec);
4604
4605 return result;
4606 }
4607
4608 static void
InitAutoRouteParameters(int pass,RouteStyleType * style,bool with_conflicts,bool is_smoothing,bool lastpass)4609 InitAutoRouteParameters (int pass,
4610 RouteStyleType * style,
4611 bool with_conflicts, bool is_smoothing,
4612 bool lastpass)
4613 {
4614 int i;
4615 /* routing style */
4616 AutoRouteParameters.style = style;
4617 AutoRouteParameters.bloat = style->Keepaway + HALF_THICK (style->Thick);
4618 /* costs */
4619 AutoRouteParameters.ViaCost =
4620 INCH_TO_COORD (3.5) + style->Diameter * (is_smoothing ? 80 : 30);
4621 AutoRouteParameters.LastConflictPenalty =
4622 (400 * pass / passes + 2) / (pass + 1);
4623 AutoRouteParameters.ConflictPenalty =
4624 4 * AutoRouteParameters.LastConflictPenalty;
4625 AutoRouteParameters.JogPenalty = 1000 * (is_smoothing ? 20 : 4);
4626 AutoRouteParameters.CongestionPenalty = 1e6;
4627 AutoRouteParameters.MinPenalty = EXPENSIVE;
4628 for (i = 0; i < max_group; i++)
4629 {
4630 if (is_layer_group_active[i])
4631 {
4632 AutoRouteParameters.MinPenalty = MIN (x_cost[i],
4633 AutoRouteParameters.
4634 MinPenalty);
4635 AutoRouteParameters.MinPenalty =
4636 MIN (y_cost[i], AutoRouteParameters.MinPenalty);
4637 }
4638 }
4639 AutoRouteParameters.NewLayerPenalty = is_smoothing ?
4640 0.5 * EXPENSIVE : 10 * AutoRouteParameters.ViaCost;
4641 /* other */
4642 AutoRouteParameters.hi_conflict = MAX (8 * (passes - pass + 1), 6);
4643 AutoRouteParameters.is_odd = (pass & 1);
4644 AutoRouteParameters.with_conflicts = with_conflicts;
4645 AutoRouteParameters.is_smoothing = is_smoothing;
4646 AutoRouteParameters.rip_always = is_smoothing;
4647 AutoRouteParameters.last_smooth = 0; //lastpass;
4648 AutoRouteParameters.pass = pass + 1;
4649 }
4650
4651 #ifndef NDEBUG
4652 int
bad_boy(const BoxType * b,void * cl)4653 bad_boy (const BoxType * b, void *cl)
4654 {
4655 routebox_t *box = (routebox_t *) b;
4656 if (box->type == EXPANSION_AREA)
4657 return 1;
4658 return 0;
4659 }
4660
4661 bool
no_expansion_boxes(routedata_t * rd)4662 no_expansion_boxes (routedata_t * rd)
4663 {
4664 int i;
4665 BoxType big;
4666 big.X1 = 0;
4667 big.X2 = MAX_COORD;
4668 big.Y1 = 0;
4669 big.Y2 = MAX_COORD;
4670 for (i = 0; i < max_group; i++)
4671 {
4672 if (r_search (rd->layergrouptree[i], &big, NULL, bad_boy, NULL))
4673 return false;
4674 }
4675 return true;
4676 }
4677 #endif
4678
4679 static void
ripout_livedraw_obj(routebox_t * rb)4680 ripout_livedraw_obj (routebox_t *rb)
4681 {
4682 if (rb->type == LINE && rb->livedraw_obj.line)
4683 {
4684 LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
4685 EraseLine (rb->livedraw_obj.line);
4686 DestroyObject (PCB->Data, LINE_TYPE, layer, rb->livedraw_obj.line, NULL);
4687 rb->livedraw_obj.line = NULL;
4688 }
4689 if (rb->type == VIA && rb->livedraw_obj.via)
4690 {
4691 EraseVia (rb->livedraw_obj.via);
4692 DestroyObject (PCB->Data, VIA_TYPE, rb->livedraw_obj.via, NULL, NULL);
4693 rb->livedraw_obj.via = NULL;
4694 }
4695 }
4696
4697 static int
ripout_livedraw_obj_cb(const BoxType * b,void * cl)4698 ripout_livedraw_obj_cb (const BoxType * b, void *cl)
4699 {
4700 routebox_t *box = (routebox_t *) b;
4701 ripout_livedraw_obj (box);
4702 return 0;
4703 }
4704
4705 struct routeall_status
4706 {
4707 /* --- for completion rate statistics ---- */
4708 int total_subnets;
4709 /* total subnets routed without conflicts */
4710 int routed_subnets;
4711 /* total subnets routed with conflicts */
4712 int conflict_subnets;
4713 /* net failted entirely */
4714 int failed;
4715 /* net was ripped */
4716 int ripped;
4717 int total_nets_routed;
4718 };
4719
4720 static double
calculate_progress(double this_heap_item,double this_heap_size,struct routeall_status * ras)4721 calculate_progress (double this_heap_item, double this_heap_size,
4722 struct routeall_status *ras)
4723 {
4724 double total_passes = passes + smoothes + 1; /* + 1 is the refinement pass */
4725 double this_pass = AutoRouteParameters.pass - 1; /* Number passes from zero */
4726 double heap_fraction = (double)(ras->routed_subnets + ras->conflict_subnets + ras->failed) /
4727 (double)ras->total_subnets;
4728 double pass_fraction = (this_heap_item + heap_fraction ) / this_heap_size;
4729 double process_fraction = (this_pass + pass_fraction) / total_passes;
4730
4731 return process_fraction;
4732 }
4733
4734 struct routeall_status
RouteAll(routedata_t * rd)4735 RouteAll (routedata_t * rd)
4736 {
4737 struct routeall_status ras;
4738 struct routeone_status ros;
4739 bool rip;
4740 int request_cancel;
4741 #ifdef NET_HEAP
4742 heap_t *net_heap;
4743 #endif
4744 heap_t *this_pass, *next_pass, *tmp;
4745 routebox_t *net, *p, *pp;
4746 cost_t total_net_cost, last_cost = 0, this_cost = 0;
4747 int i;
4748 int this_heap_size;
4749 int this_heap_item;
4750
4751 /* initialize heap for first pass;
4752 * do smallest area first; that makes
4753 * the subsequent costs more representative */
4754 this_pass = heap_create ();
4755 next_pass = heap_create ();
4756 #ifdef NET_HEAP
4757 net_heap = heap_create ();
4758 #endif
4759 LIST_LOOP (rd->first_net, different_net, net);
4760 {
4761 double area;
4762 BoxType bb = shrink_routebox (net);
4763 LIST_LOOP (net, same_net, p);
4764 {
4765 MAKEMIN (bb.X1, p->sbox.X1);
4766 MAKEMIN (bb.Y1, p->sbox.Y1);
4767 MAKEMAX (bb.X2, p->sbox.X2);
4768 MAKEMAX (bb.Y2, p->sbox.Y2);
4769 }
4770 END_LOOP;
4771 area = (double) (bb.X2 - bb.X1) * (bb.Y2 - bb.Y1);
4772 heap_insert (this_pass, area, net);
4773 }
4774 END_LOOP;
4775
4776 ras.total_nets_routed = 0;
4777 /* refinement/finishing passes */
4778 for (i = 0; i <= passes + smoothes; i++)
4779 {
4780 #ifdef ROUTE_VERBOSE
4781 if (i > 0 && i <= passes)
4782 printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i);
4783 else if (i > passes)
4784 printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
4785 i - passes);
4786 #endif
4787 ras.total_subnets = ras.routed_subnets = ras.conflict_subnets =
4788 ras.failed = ras.ripped = 0;
4789 assert (heap_is_empty (next_pass));
4790
4791 this_heap_size = heap_size (this_pass);
4792 for (this_heap_item = 0; !heap_is_empty (this_pass); this_heap_item++)
4793 {
4794 #ifdef ROUTE_DEBUG
4795 if (aabort)
4796 break;
4797 #endif
4798 net = (routebox_t *) heap_remove_smallest (this_pass);
4799 InitAutoRouteParameters (i, net->style, i < passes, i > passes,
4800 i == passes + smoothes);
4801 if (i > 0)
4802 {
4803 /* rip up all unfixed traces in this net ? */
4804 if (AutoRouteParameters.rip_always)
4805 rip = true;
4806 else
4807 {
4808 rip = false;
4809 LIST_LOOP (net, same_net, p);
4810 if (p->flags.is_bad)
4811 {
4812 rip = true;
4813 break;
4814 }
4815 END_LOOP;
4816 }
4817
4818 LIST_LOOP (net, same_net, p);
4819 p->flags.is_bad = 0;
4820 if (!p->flags.fixed)
4821 {
4822 #ifndef NDEBUG
4823 bool del;
4824 #endif
4825 assert (!p->flags.homeless);
4826 if (rip)
4827 {
4828 RemoveFromNet (p, NET);
4829 RemoveFromNet (p, SUBNET);
4830 }
4831 if (AutoRouteParameters.use_vias && p->type != VIA_SHADOW
4832 && p->type != PLANE)
4833 {
4834 mtspace_remove (rd->mtspace, &p->box,
4835 p->flags.is_odd ? ODD : EVEN,
4836 p->style->Keepaway);
4837 if (!rip)
4838 mtspace_add (rd->mtspace, &p->box,
4839 p->flags.is_odd ? EVEN : ODD,
4840 p->style->Keepaway);
4841 }
4842 if (rip)
4843 {
4844 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
4845 ripout_livedraw_obj (p);
4846 #ifndef NDEBUG
4847 del =
4848 #endif
4849 r_delete_entry (rd->layergrouptree[p->group],
4850 &p->box);
4851 #ifndef NDEBUG
4852 assert (del);
4853 #endif
4854 }
4855 else
4856 {
4857 p->flags.is_odd = AutoRouteParameters.is_odd;
4858 }
4859 }
4860 END_LOOP;
4861 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
4862 Draw ();
4863 /* reset to original connectivity */
4864 if (rip)
4865 {
4866 ras.ripped++;
4867 ResetSubnet (net);
4868 }
4869 else
4870 {
4871 heap_insert (next_pass, 0, net);
4872 continue;
4873 }
4874 }
4875 /* count number of subnets */
4876 FOREACH_SUBNET (net, p);
4877 ras.total_subnets++;
4878 END_FOREACH (net, p);
4879 /* the first subnet doesn't require routing. */
4880 ras.total_subnets--;
4881 /* and re-route! */
4882 total_net_cost = 0;
4883 /* only route that which isn't fully routed */
4884 #ifdef ROUTE_DEBUG
4885 if (ras.total_subnets == 0 || aabort)
4886 #else
4887 if (ras.total_subnets == 0)
4888 #endif
4889 {
4890 heap_insert (next_pass, 0, net);
4891 continue;
4892 }
4893
4894 /* the loop here ensures that we get to all subnets even if
4895 * some of them are unreachable from the first subnet. */
4896 LIST_LOOP (net, same_net, p);
4897 {
4898 #ifdef NET_HEAP
4899 BoxType b = shrink_routebox (p);
4900 /* using a heap allows us to start from smaller objects and
4901 * end at bigger ones. also prefer to start at planes, then pads */
4902 heap_insert (net_heap, (float) (b.X2 - b.X1) *
4903 #if defined(ROUTE_RANDOMIZED)
4904 (0.3 + rand () / (RAND_MAX + 1.0)) *
4905 #endif
4906 (b.Y2 - b.Y1) * (p->type == PLANE ?
4907 -1 : (p->type ==
4908 PAD ? 1 : 10)), p);
4909 }
4910 END_LOOP;
4911 ros.net_completely_routed = 0;
4912 while (!heap_is_empty (net_heap))
4913 {
4914 p = (routebox_t *) heap_remove_smallest (net_heap);
4915 #endif
4916 if (!p->flags.fixed || p->flags.subnet_processed ||
4917 p->type == OTHER)
4918 continue;
4919
4920 while (!ros.net_completely_routed)
4921 {
4922 double percent;
4923
4924 assert (no_expansion_boxes (rd));
4925 /* FIX ME: the number of edges to examine should be in autoroute parameters
4926 * i.e. the 2000 and 800 hard-coded below should be controllable by the user
4927 */
4928 ros =
4929 RouteOne (rd, p, NULL,
4930 ((AutoRouteParameters.
4931 is_smoothing ? 2000 : 800) * (i +
4932 1)) *
4933 routing_layers);
4934 total_net_cost += ros.best_route_cost;
4935 if (ros.found_route)
4936 {
4937 if (ros.route_had_conflicts)
4938 ras.conflict_subnets++;
4939 else
4940 {
4941 ras.routed_subnets++;
4942 ras.total_nets_routed++;
4943 }
4944 }
4945 else
4946 {
4947 if (!ros.net_completely_routed)
4948 ras.failed++;
4949 /* don't bother trying any other source in this subnet */
4950 LIST_LOOP (p, same_subnet, pp);
4951 pp->flags.subnet_processed = 1;
4952 END_LOOP;
4953 break;
4954 }
4955 /* note that we can infer nothing about ras.total_subnets based
4956 * on the number of calls to RouteOne, because we may be unable
4957 * to route a net from a particular starting point, but perfectly
4958 * able to route it from some other. */
4959 percent = calculate_progress (this_heap_item, this_heap_size, &ras);
4960 request_cancel = gui->progress (percent * 100., 100,
4961 _("Autorouting tracks"));
4962 if (request_cancel)
4963 {
4964 ras.total_nets_routed = 0;
4965 ras.conflict_subnets = 0;
4966 Message ("Autorouting cancelled\n");
4967 goto out;
4968 }
4969 }
4970 }
4971 #ifndef NET_HEAP
4972 END_LOOP;
4973 #endif
4974 if (!ros.net_completely_routed)
4975 net->flags.is_bad = 1; /* don't skip this the next round */
4976
4977 /* Route easiest nets from this pass first on next pass.
4978 * This works best because it's likely that the hardest
4979 * is the last one routed (since it has the most obstacles)
4980 * but it will do no good to rip it up and try it again
4981 * without first changing any of the other routes
4982 */
4983 heap_insert (next_pass, total_net_cost, net);
4984 if (total_net_cost < EXPENSIVE)
4985 this_cost += total_net_cost;
4986 /* reset subnet_processed flags */
4987 LIST_LOOP (net, same_net, p);
4988 {
4989 p->flags.subnet_processed = 0;
4990 }
4991 END_LOOP;
4992 }
4993 /* swap this_pass and next_pass and do it all over again! */
4994 ro = 0;
4995 assert (heap_is_empty (this_pass));
4996 tmp = this_pass;
4997 this_pass = next_pass;
4998 next_pass = tmp;
4999 #if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
5000 printf
5001 ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
5002 i, ras.routed_subnets, ras.total_subnets, this_cost,
5003 ras.conflict_subnets, ras.failed, ras.ripped);
5004 #endif
5005 #ifdef ROUTE_DEBUG
5006 if (aabort)
5007 break;
5008 #endif
5009 /* if no conflicts found, skip directly to smoothing pass! */
5010 if (ras.conflict_subnets == 0 && ras.routed_subnets == ras.total_subnets
5011 && i <= passes)
5012 i = passes - (smoothes ? 0 : 1);
5013 /* if no changes in a smoothing round, then we're done */
5014 if (this_cost == last_cost && i > passes && i < passes + smoothes)
5015 i = passes + smoothes - 1;
5016 last_cost = this_cost;
5017 this_cost = 0;
5018 }
5019
5020 Message ("%d of %d nets successfully routed.\n",
5021 ras.routed_subnets, ras.total_subnets);
5022
5023 out:
5024 heap_destroy (&this_pass);
5025 heap_destroy (&next_pass);
5026 #ifdef NET_HEAP
5027 heap_destroy (&net_heap);
5028 #endif
5029
5030 /* no conflicts should be left at the end of the process. */
5031 assert (ras.conflict_subnets == 0);
5032
5033 return ras;
5034 }
5035
5036 struct fpin_info
5037 {
5038 PinType *pin;
5039 Coord X, Y;
5040 jmp_buf env;
5041 };
5042
5043 static int
fpin_rect(const BoxType * b,void * cl)5044 fpin_rect (const BoxType * b, void *cl)
5045 {
5046 PinType *pin = (PinType *) b;
5047 struct fpin_info *info = (struct fpin_info *) cl;
5048 if (pin->X == info->X && pin->Y == info->Y)
5049 {
5050 info->pin = (PinType *) b;
5051 longjmp (info->env, 1);
5052 }
5053 return 0;
5054 }
5055
5056 static int
FindPin(const BoxType * box,PinType ** pin)5057 FindPin (const BoxType * box, PinType ** pin)
5058 {
5059 struct fpin_info info;
5060
5061 info.pin = NULL;
5062 info.X = box->X1;
5063 info.Y = box->Y1;
5064 if (setjmp (info.env) == 0)
5065 r_search (PCB->Data->pin_tree, box, NULL, fpin_rect, &info);
5066 else
5067 {
5068 *pin = info.pin;
5069 return PIN_TYPE;
5070 }
5071 if (setjmp (info.env) == 0)
5072 r_search (PCB->Data->via_tree, box, NULL, fpin_rect, &info);
5073 else
5074 {
5075 *pin = info.pin;
5076 return VIA_TYPE;
5077 }
5078 *pin = NULL;
5079 return NO_TYPE;
5080 }
5081
5082
5083 /*!
5084 * \brief Paths go on first 'on' layer in group.
5085 *
5086 * Returns 'true' if any paths were added.
5087 */
5088 bool
IronDownAllUnfixedPaths(routedata_t * rd)5089 IronDownAllUnfixedPaths (routedata_t * rd)
5090 {
5091 bool changed = false;
5092 LayerType *layer;
5093 routebox_t *net, *p;
5094 int i;
5095 LIST_LOOP (rd->first_net, different_net, net);
5096 {
5097 LIST_LOOP (net, same_net, p);
5098 {
5099 if (!p->flags.fixed)
5100 {
5101 /* find first on layer in this group */
5102 assert (PCB->LayerGroups.Number[p->group] > 0);
5103 assert (is_layer_group_active[p->group]);
5104 for (i = 0, layer = NULL; i < PCB->LayerGroups.Number[p->group];
5105 i++)
5106 {
5107 layer = LAYER_PTR (PCB->LayerGroups.Entries[p->group][i]);
5108 if (layer->On)
5109 break;
5110 }
5111 assert (layer && layer->On); /*at least one layer must be on in this group! */
5112 assert (p->type != EXPANSION_AREA);
5113 if (p->type == LINE)
5114 {
5115 Coord halfwidth = HALF_THICK (p->style->Thick);
5116 double th = halfwidth * 2 + 1;
5117 BoxType b;
5118 assert (p->parent.line == NULL);
5119 /* orthogonal; thickness is 2*halfwidth */
5120 /* flip coordinates, if bl_to_ur */
5121 b = p->sbox;
5122 total_wire_length += hypot (b.X2 - b.X1 - th, b.Y2 - b.Y1 - th);
5123 b = shrink_box (&b, halfwidth);
5124 if (b.X2 == b.X1 + 1)
5125 b.X2 = b.X1;
5126 if (b.Y2 == b.Y1 + 1)
5127 b.Y2 = b.Y1;
5128 if (p->flags.bl_to_ur)
5129 {
5130 Coord t;
5131 t = b.X1;
5132 b.X1 = b.X2;
5133 b.X2 = t;
5134 }
5135 /* using CreateDrawn instead of CreateNew concatenates sequential lines */
5136 p->parent.line = CreateDrawnLineOnLayer
5137 (layer, b.X1, b.Y1, b.X2, b.Y2,
5138 p->style->Thick,
5139 p->style->Keepaway * 2,
5140 MakeFlags (AUTOFLAG |
5141 (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG :
5142 0)));
5143
5144 if (p->parent.line)
5145 {
5146 AddObjectToCreateUndoList (LINE_TYPE, layer,
5147 p->parent.line, p->parent.line);
5148 changed = true;
5149 }
5150 }
5151 else if (p->type == VIA || p->type == VIA_SHADOW)
5152 {
5153 routebox_t *pp =
5154 (p->type == VIA_SHADOW) ? p->parent.via_shadow : p;
5155 Coord radius = HALF_THICK (pp->style->Diameter);
5156 BoxType b = shrink_routebox (p);
5157 total_via_count++;
5158 assert (pp->type == VIA);
5159 if (pp->parent.via == NULL)
5160 {
5161 assert (b.X1 + radius == b.X2 - radius);
5162 assert (b.Y1 + radius == b.Y2 - radius);
5163 pp->parent.via =
5164 CreateNewVia (PCB->Data, b.X1 + radius,
5165 b.Y1 + radius,
5166 pp->style->Diameter,
5167 2 * pp->style->Keepaway,
5168 0, pp->style->Hole, NULL,
5169 MakeFlags (AUTOFLAG));
5170 assert (pp->parent.via);
5171 if (pp->parent.via)
5172 {
5173 AddObjectToCreateUndoList (VIA_TYPE,
5174 pp->parent.via,
5175 pp->parent.via,
5176 pp->parent.via);
5177 changed = true;
5178 }
5179 }
5180 assert (pp->parent.via);
5181 if (p->type == VIA_SHADOW)
5182 {
5183 p->type = VIA;
5184 p->parent.via = pp->parent.via;
5185 }
5186 }
5187 else if (p->type == THERMAL)
5188 /* nothing to do because, the via might not be there yet */ ;
5189 else
5190 assert (0);
5191 }
5192 }
5193 END_LOOP;
5194 /* loop again to place all the thermals now that the vias are down */
5195 LIST_LOOP (net, same_net, p);
5196 {
5197 if (p->type == THERMAL)
5198 {
5199 PinType *pin = NULL;
5200 /* thermals are alread a single point search, no need to shrink */
5201 int type = FindPin (&p->box, &pin);
5202 if (pin)
5203 {
5204 AddObjectToClearPolyUndoList (type,
5205 pin->Element ? pin->Element : pin,
5206 pin, pin, false);
5207 RestoreToPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
5208 pin);
5209 AddObjectToFlagUndoList (type,
5210 pin->Element ? pin->Element : pin, pin,
5211 pin);
5212 ASSIGN_THERM (p->layer, PCB->ThermStyle, pin);
5213 AddObjectToClearPolyUndoList (type,
5214 pin->Element ? pin->Element : pin,
5215 pin, pin, true);
5216 ClearFromPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
5217 pin);
5218 changed = true;
5219 }
5220 }
5221 }
5222 END_LOOP;
5223 }
5224 END_LOOP;
5225 return changed;
5226 }
5227
5228 bool
AutoRoute(bool selected)5229 AutoRoute (bool selected)
5230 {
5231 bool changed = false;
5232 routedata_t *rd;
5233 int i;
5234
5235 total_wire_length = 0;
5236 total_via_count = 0;
5237
5238 #ifdef ROUTE_DEBUG
5239 ddraw = gui->request_debug_draw ();
5240 if (ddraw != NULL)
5241 {
5242 ar_gc = ddraw->make_gc ();
5243 ddraw->set_line_cap (ar_gc, Round_Cap);
5244 }
5245 #endif
5246
5247 for (i = 0; i < NUM_STYLES; i++)
5248 {
5249 if (PCB->RouteStyle[i].Thick == 0 ||
5250 PCB->RouteStyle[i].Diameter == 0 ||
5251 PCB->RouteStyle[i].Hole == 0 || PCB->RouteStyle[i].Keepaway == 0)
5252 {
5253 Message ("You must define proper routing styles\n"
5254 "before auto-routing.\n");
5255 return (false);
5256 }
5257 }
5258 if (PCB->Data->RatN == 0)
5259 return (false);
5260 rd = CreateRouteData ();
5261
5262 if (1)
5263 {
5264 routebox_t *net, *rb, *last;
5265 int i = 0;
5266 /* count number of rats selected */
5267 RAT_LOOP (PCB->Data);
5268 {
5269 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5270 i++;
5271 }
5272 END_LOOP;
5273 #ifdef ROUTE_VERBOSE
5274 printf ("%d nets!\n", i);
5275 #endif
5276 if (i == 0)
5277 goto donerouting; /* nothing to do here */
5278 /* if only one rat selected, do things the quick way. =) */
5279 if (i == 1)
5280 {
5281 RAT_LOOP (PCB->Data);
5282 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5283 {
5284 /* look up the end points of this rat line */
5285 routebox_t *a =
5286 FindRouteBoxOnLayerGroup (rd, line->Point1.X,
5287 line->Point1.Y, line->group1);
5288 routebox_t *b =
5289 FindRouteBoxOnLayerGroup (rd, line->Point2.X,
5290 line->Point2.Y, line->group2);
5291
5292 /* If the rat starts or ends at a non-straight pad (i.e., at a
5293 * rotated SMD), a or b will be NULL since the autorouter can't
5294 * handle these.
5295 */
5296 if (a != NULL && b != NULL)
5297 {
5298 assert (a->style == b->style);
5299 /* route exactly one net, without allowing conflicts */
5300 InitAutoRouteParameters (0, a->style, false, true, true);
5301 /* hace planes work better as sources than targets */
5302 changed = RouteOne (rd, a, b, 150000).found_route || changed;
5303 goto donerouting;
5304 }
5305 }
5306 END_LOOP;
5307 }
5308 /* otherwise, munge the netlists so that only the selected rats
5309 * get connected. */
5310 /* first, separate all sub nets into separate nets */
5311 /* note that this code works because LIST_LOOP is clever enough not to
5312 * be fooled when the list is changing out from under it. */
5313 last = NULL;
5314 LIST_LOOP (rd->first_net, different_net, net);
5315 {
5316 FOREACH_SUBNET (net, rb);
5317 {
5318 if (last)
5319 {
5320 last->different_net.next = rb;
5321 rb->different_net.prev = last;
5322 }
5323 last = rb;
5324 }
5325 END_FOREACH (net, rb);
5326 LIST_LOOP (net, same_net, rb);
5327 {
5328 rb->same_net = rb->same_subnet;
5329 }
5330 END_LOOP;
5331 /* at this point all nets are equal to their subnets */
5332 }
5333 END_LOOP;
5334 if (last)
5335 {
5336 last->different_net.next = rd->first_net;
5337 rd->first_net->different_net.prev = last;
5338 }
5339
5340 /* now merge only those subnets connected by a rat line */
5341 RAT_LOOP (PCB->Data);
5342 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5343 {
5344 /* look up the end points of this rat line */
5345 routebox_t *a;
5346 routebox_t *b;
5347 a =
5348 FindRouteBoxOnLayerGroup (rd, line->Point1.X,
5349 line->Point1.Y, line->group1);
5350 b =
5351 FindRouteBoxOnLayerGroup (rd, line->Point2.X,
5352 line->Point2.Y, line->group2);
5353 if (!a || !b)
5354 {
5355 #ifdef DEBUG_STALE_RATS
5356 AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
5357 ASSIGN_FLAG (SELECTEDFLAG, true, line);
5358 DrawRat (line, 0);
5359 #endif /* DEBUG_STALE_RATS */
5360 Message ("The rats nest is stale! Aborting autoroute...\n");
5361 goto donerouting;
5362 }
5363 /* merge subnets into a net! */
5364 MergeNets (a, b, NET);
5365 }
5366 END_LOOP;
5367 /* now 'different_net' may point to too many different nets. Reset. */
5368 LIST_LOOP (rd->first_net, different_net, net);
5369 {
5370 if (!net->flags.touched)
5371 {
5372 LIST_LOOP (net, same_net, rb);
5373 rb->flags.touched = 1;
5374 END_LOOP;
5375 }
5376 else /* this is not a "different net"! */
5377 RemoveFromNet (net, DIFFERENT_NET);
5378 }
5379 END_LOOP;
5380 /* reset "touched" flag */
5381 LIST_LOOP (rd->first_net, different_net, net);
5382 {
5383 LIST_LOOP (net, same_net, rb);
5384 {
5385 assert (rb->flags.touched);
5386 rb->flags.touched = 0;
5387 }
5388 END_LOOP;
5389 }
5390 END_LOOP;
5391 }
5392 /* okay, rd's idea of netlist now corresponds to what we want routed */
5393 /* auto-route all nets */
5394 changed = (RouteAll (rd).total_nets_routed > 0) || changed;
5395 donerouting:
5396 gui->progress (0, 0, NULL);
5397 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
5398 {
5399 int i;
5400 BoxType big = {0, 0, MAX_COORD, MAX_COORD};
5401 for (i = 0; i < max_group; i++)
5402 {
5403 r_search (rd->layergrouptree[i], &big, NULL, ripout_livedraw_obj_cb, NULL);
5404 }
5405 }
5406 #ifdef ROUTE_DEBUG
5407 if (ddraw != NULL)
5408 {
5409 ddraw->destroy_gc (ar_gc);
5410 gui->finish_debug_draw ();
5411 }
5412 #endif
5413
5414 if (changed)
5415 changed = IronDownAllUnfixedPaths (rd);
5416 Message ("Total added wire length = %$mS, %d vias added\n",
5417 (Coord) total_wire_length, total_via_count);
5418 DestroyRouteData (&rd);
5419 if (changed)
5420 {
5421 SaveUndoSerialNumber ();
5422
5423 /* optimize rats, we've changed connectivity a lot. */
5424 DeleteRats (false /*all rats */ );
5425 RestoreUndoSerialNumber ();
5426 AddAllRats (false /*all rats */ , NULL);
5427 RestoreUndoSerialNumber ();
5428
5429 IncrementUndoSerialNumber ();
5430
5431 Redraw ();
5432 }
5433 #if defined (ROUTE_DEBUG)
5434 aabort = 0;
5435 #endif
5436 return (changed);
5437 }
5438