Index: trunk/scconfig/hooks.c =================================================================== --- trunk/scconfig/hooks.c (revision 1046) +++ trunk/scconfig/hooks.c (revision 1047) @@ -45,6 +45,10 @@ {"buildin-autorouter", "/local/pcb/autorouter/buildin", arg_true, "$static link the autorouter plugin into the executable"}, {"plugin-autorouter", "/local/pcb/autorouter/buildin", arg_false, "$the autorouter plugin is dynamic loadable"}, + {"disable-autoplace", "/local/pcb/autoplace/enable", arg_false, "$do not compile the autoplace"}, + {"buildin-autoplace", "/local/pcb/autoplace/buildin", arg_true, "$static link the autoplace plugin into the executable"}, + {"plugin-autoplace", "/local/pcb/autoplace/buildin", arg_false, "$the autoplace plugin is dynamic loadable"}, + {NULL, NULL, NULL, NULL} }; @@ -111,6 +115,10 @@ put("/local/pcb/autorouter/enable", strue); put("/local/pcb/autorouter/buildin", strue); + db_mkdir("/local/pcb/autoplace"); + put("/local/pcb/autoplace/enable", strue); + put("/local/pcb/autoplace/buildin", strue); + return 0; } @@ -248,6 +256,27 @@ return generr; } +static void plugin_stat(const char *header, const char *path_prefix) +{ + char path_en[256], path_bi[256]; + + sprintf(path_en, "%s/enable", path_prefix); + sprintf(path_bi, "%s/buildin", path_prefix); + + printf("%-32s", header); + if (node_istrue(path_en)) { + printf("yes "); + if (node_istrue(path_bi)) + printf("(buildin)\n"); + else + printf("(plugin)\n"); + } + else + printf("no\n"); + + +} + /* Runs after detection hooks, should generate the output (Makefiles, etc.) */ int hook_generate() { @@ -298,7 +327,7 @@ printf("disabled\n"); /* special case because the "presents" node */ - printf("Scripting via GPMI: "); + printf("%-32s", "Scripting via GPMI: "); if (node_istrue("libs/script/gpmi/presents")) { printf("yes "); if (node_istrue("/local/pcb/gpmi/buildin")) @@ -309,18 +338,9 @@ else printf("no\n"); - printf("Autorouter: "); - if (node_istrue("/local/pcb/autorouter/enable")) { - printf("yes "); - if (node_istrue("/local/pcb/autorouter/buildin")) - printf("(buildin)\n"); - else - printf("(plugin)\n"); - } - else - printf("no\n"); + plugin_stat("Autorouter: ", "/local/pcb/autorouter"); + plugin_stat("Autoplace: ", "/local/pcb/autoplace"); - if (manual_config) printf("\n\n * NOTE: you may want to edit config.manual.h (user preferences) *\n"); } Index: trunk/src/autoplace.c =================================================================== --- trunk/src/autoplace.c (revision 1046) +++ trunk/src/autoplace.c (nonexistent) @@ -1,766 +0,0 @@ -/* $Id$ */ - -/* - * COPYRIGHT - * - * PCB, interactive printed circuit board design - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - * - * Contact addresses for paper mail and Email: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - -/* - * This moduel, autoplace.c, was written by and is - * Copyright (c) 2001 C. Scott Ananian - */ - -/* functions used to autoplace elements. - */ - -#include "config.h" - -#include -#include -#include -#include - -#include "global.h" - -#include "autoplace.h" -#include "box.h" -#include "compat.h" -#include "data.h" -#include "draw.h" -#include "error.h" -#include "intersect.h" -#include "rtree.h" -#include "macro.h" -#include "mirror.h" -#include "misc.h" -#include "move.h" -#include "mymem.h" -#include "rats.h" -#include "remove.h" -#include "rotate.h" - - -RCSID("$Id$"); - -#define EXPANDRECTXY(r1, x1, y1, x2, y2) { \ - r1->X1=MIN(r1->X1, x1); r1->Y1=MIN(r1->Y1, y1); \ - r1->X2=MAX(r1->X2, x2); r1->Y2=MAX(r1->Y2, y2); \ -} -#define EXPANDRECT(r1, r2) EXPANDRECTXY(r1, r2->X1, r2->Y1, r2->X2, r2->Y2) - -/* --------------------------------------------------------------------------- - * some local prototypes - */ -static double ComputeCost(NetListTypePtr Nets, double T0, double T); - -/* --------------------------------------------------------------------------- - * some local types - */ -const struct { - double via_cost; - double congestion_penalty; /* penalty length / unit area */ - double overlap_penalty_min; /* penalty length / unit area at start */ - double overlap_penalty_max; /* penalty length / unit area at end */ - double out_of_bounds_penalty; /* assessed for each component oob */ - double overall_area_penalty; /* penalty length / unit area */ - double matching_neighbor_bonus; /* length bonus per same-type neigh. */ - double aligned_neighbor_bonus; /* length bonus per aligned neigh. */ - double oriented_neighbor_bonus; /* length bonus per same-rot neigh. */ -#if 0 - double pin_alignment_bonus; /* length bonus per exact alignment */ - double bound_alignment_bonus; /* length bonus per exact alignment */ -#endif - double m; /* annealing stage cutoff constant */ - double gamma; /* annealing schedule constant */ - int good_ratio; /* ratio of moves to good moves for halting */ - bool fast; /* ignore SMD/pin conflicts */ - Coord large_grid_size; /* snap perturbations to this grid when T is high */ - Coord small_grid_size; /* snap to this grid when T is small. */ -} -/* wire cost is manhattan distance (in mils), thus 1 inch = 1000 */ CostParameter = -{ - 3e3, /* via cost */ - 2e-2, /* congestion penalty */ - 1e-2, /* initial overlap penalty */ - 1e2, /* final overlap penalty */ - 1e3, /* out of bounds penalty */ - 1e0, /* penalty for total area used */ - 1e0, /* subtract 1000 from cost for every same-type neighbor */ - 1e0, /* subtract 1000 from cost for every aligned neighbor */ - 1e0, /* subtract 1000 from cost for every same-rotation neighbor */ - 20, /* move on when each module has been profitably moved 20 times */ - 0.75, /* annealing schedule constant: 0.85 */ - 40, /* halt when there are 60 times as many moves as good moves */ - false, /* don't ignore SMD/pin conflicts */ - MIL_TO_COORD(100), /* coarse grid is 100 mils */ - MIL_TO_COORD(10), /* fine grid is 10 mils */ -}; - -typedef struct { - ElementTypePtr *element; - Cardinal elementN; -} ElementPtrListType; - -enum ewhich { SHIFT, ROTATE, EXCHANGE }; - -typedef struct { - ElementTypePtr element; - enum ewhich which; - Coord DX, DY; /* for shift */ - unsigned rotate; /* for rotate/flip */ - ElementTypePtr other; /* for exchange */ -} PerturbationType; - -/* --------------------------------------------------------------------------- - * some local identifiers - */ - -/* --------------------------------------------------------------------------- - * Update the X, Y and group position information stored in the NetList after - * elements have possibly been moved, rotated, flipped, etc. - */ -static void UpdateXY(NetListTypePtr Nets) -{ - Cardinal SLayer, CLayer; - Cardinal i, j; - /* find layer groups of the component side and solder side */ - SLayer = GetLayerGroupNumberByNumber(solder_silk_layer); - CLayer = GetLayerGroupNumberByNumber(component_silk_layer); - /* update all nets */ - for (i = 0; i < Nets->NetN; i++) { - for (j = 0; j < Nets->Net[i].ConnectionN; j++) { - ConnectionTypePtr c = &(Nets->Net[i].Connection[j]); - switch (c->type) { - case PAD_TYPE: - c->group = TEST_FLAG(ONSOLDERFLAG, (ElementTypePtr) c->ptr1) - ? SLayer : CLayer; - c->X = ((PadTypePtr) c->ptr2)->Point1.X; - c->Y = ((PadTypePtr) c->ptr2)->Point1.Y; - break; - case PIN_TYPE: - c->group = SLayer; /* any layer will do */ - c->X = ((PinTypePtr) c->ptr2)->X; - c->Y = ((PinTypePtr) c->ptr2)->Y; - break; - default: - Message("Odd connection type encountered in " "UpdateXY"); - break; - } - } - } -} - -/* --------------------------------------------------------------------------- - * Create a list of selected elements. - */ -static PointerListType collectSelectedElements() -{ - PointerListType list = { 0, 0, NULL }; - ELEMENT_LOOP(PCB->Data); - { - if (TEST_FLAG(SELECTEDFLAG, element)) { - ElementTypePtr *epp = (ElementTypePtr *) GetPointerMemory(&list); - *epp = element; - } - } - END_LOOP; - return list; -} - -#if 0 /* only for debugging box lists */ -#include "create.h" -/* makes a line on the solder layer surrounding all boxes in blist */ -static void showboxes(BoxListTypePtr blist) -{ - Cardinal i; - LayerTypePtr SLayer = &(PCB->Data->Layer[solder_silk_layer]); - for (i = 0; i < blist->BoxN; i++) { - CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y1, blist->Box[i].X2, blist->Box[i].Y1, 1, 1, 0); - CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y2, blist->Box[i].X2, blist->Box[i].Y2, 1, 1, 0); - CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y1, blist->Box[i].X1, blist->Box[i].Y2, 1, 1, 0); - CreateNewLineOnLayer(SLayer, blist->Box[i].X2, blist->Box[i].Y1, blist->Box[i].X2, blist->Box[i].Y2, 1, 1, 0); - } -} -#endif - -/* --------------------------------------------------------------------------- - * Helper function to compute "closest neighbor" for a box in a rtree. - * The closest neighbor on a certain side is the closest one in a trapezoid - * emanating from that side. - */ -/*------ r_find_neighbor ------*/ -struct r_neighbor_info { - const BoxType *neighbor; - BoxType trap; - direction_t search_dir; -}; -#define ROTATEBOX(box) { Coord t;\ - t = (box).X1; (box).X1 = - (box).Y1; (box).Y1 = t;\ - t = (box).X2; (box).X2 = - (box).Y2; (box).Y2 = t;\ - t = (box).X1; (box).X1 = (box).X2; (box).X2 = t;\ -} -/* helper methods for __r_find_neighbor */ -static int __r_find_neighbor_reg_in_sea(const BoxType * region, void *cl) -{ - struct r_neighbor_info *ni = (struct r_neighbor_info *) cl; - BoxType query = *region; - ROTATEBOX_TO_NORTH(query, ni->search_dir); - /* ______________ __ trap.y1 __ - * \ / |__| query rect. - * \__________/ __ trap.y2 - * | | - * trap.x1 trap.x2 sides at 45-degree angle - */ - return (query.Y2 > ni->trap.Y1) && (query.Y1 < ni->trap.Y2) && - (query.X2 + ni->trap.Y2 > ni->trap.X1 + query.Y1) && (query.X1 + query.Y1 < ni->trap.X2 + ni->trap.Y2); -} - -static int __r_find_neighbor_rect_in_reg(const BoxType * box, void *cl) -{ - struct r_neighbor_info *ni = (struct r_neighbor_info *) cl; - BoxType query = *box; - int r; - ROTATEBOX_TO_NORTH(query, ni->search_dir); - /* ______________ __ trap.y1 __ - * \ / |__| query rect. - * \__________/ __ trap.y2 - * | | - * trap.x1 trap.x2 sides at 45-degree angle - */ - r = (query.Y2 > ni->trap.Y1) && (query.Y1 < ni->trap.Y2) && - (query.X2 + ni->trap.Y2 > ni->trap.X1 + query.Y1) && (query.X1 + query.Y1 < ni->trap.X2 + ni->trap.Y2); - r = r && (query.Y2 <= ni->trap.Y2); - if (r) { - ni->trap.Y1 = query.Y2; - ni->neighbor = box; - } - return r; -} - -/* main r_find_neighbor routine. Returns NULL if no neighbor in the - * requested direction. */ -static const BoxType *r_find_neighbor(rtree_t * rtree, const BoxType * box, direction_t search_direction) -{ - struct r_neighbor_info ni; - BoxType bbox; - - ni.neighbor = NULL; - ni.trap = *box; - ni.search_dir = search_direction; - - bbox.X1 = bbox.Y1 = 0; - bbox.X2 = PCB->MaxWidth; - bbox.Y2 = PCB->MaxHeight; - /* rotate so that we can use the 'north' case for everything */ - ROTATEBOX_TO_NORTH(bbox, search_direction); - ROTATEBOX_TO_NORTH(ni.trap, search_direction); - /* shift Y's such that trap contains full bounds of trapezoid */ - ni.trap.Y2 = ni.trap.Y1; - ni.trap.Y1 = bbox.Y1; - /* do the search! */ - r_search(rtree, NULL, __r_find_neighbor_reg_in_sea, __r_find_neighbor_rect_in_reg, &ni); - return ni.neighbor; -} - -/* --------------------------------------------------------------------------- - * Compute cost function. - * note that area overlap cost is correct for SMD devices: SMD devices on - * opposite sides of the board don't overlap. - * - * Algorithms follow those described in sections 4.1 of - * "Placement and Routing of Electronic Modules" edited by Michael Pecht - * Marcel Dekker, Inc. 1993. ISBN: 0-8247-8916-4 TK7868.P7.P57 1993 - */ -static double ComputeCost(NetListTypePtr Nets, double T0, double T) -{ - double W = 0; /* wire cost */ - double delta1 = 0; /* wire congestion penalty function */ - double delta2 = 0; /* module overlap penalty function */ - double delta3 = 0; /* out of bounds penalty */ - double delta4 = 0; /* alignment bonus */ - double delta5 = 0; /* total area penalty */ - Cardinal i, j; - Coord minx, maxx, miny, maxy; - bool allpads, allsameside; - Cardinal thegroup; - BoxListType bounds = { 0, 0, NULL }; /* save bounding rectangles here */ - BoxListType solderside = { 0, 0, NULL }; /* solder side component bounds */ - BoxListType componentside = { 0, 0, NULL }; /* component side bounds */ - /* make sure the NetList have the proper updated X and Y coords */ - UpdateXY(Nets); - /* wire length term. approximated by half-perimeter of minimum - * rectangle enclosing the net. Note that we penalize vias in - * all-SMD nets by making the rectangle a cube and weighting - * the "layer height" of the net. */ - for (i = 0; i < Nets->NetN; i++) { - NetTypePtr n = &Nets->Net[i]; - if (n->ConnectionN < 2) - continue; /* no cost to go nowhere */ - minx = maxx = n->Connection[0].X; - miny = maxy = n->Connection[0].Y; - thegroup = n->Connection[0].group; - allpads = (n->Connection[0].type == PAD_TYPE); - allsameside = true; - for (j = 1; j < n->ConnectionN; j++) { - ConnectionTypePtr c = &(n->Connection[j]); - MAKEMIN(minx, c->X); - MAKEMAX(maxx, c->X); - MAKEMIN(miny, c->Y); - MAKEMAX(maxy, c->Y); - if (c->type != PAD_TYPE) - allpads = false; - if (c->group != thegroup) - allsameside = false; - } - /* save bounding rectangle */ - { - BoxTypePtr box = GetBoxMemory(&bounds); - box->X1 = minx; - box->Y1 = miny; - box->X2 = maxx; - box->Y2 = maxy; - } - /* okay, add half-perimeter to cost! */ - W += COORD_TO_MIL(maxx - minx) + COORD_TO_MIL(maxy - miny) + ((allpads && !allsameside) ? CostParameter.via_cost : 0); - } - /* now compute penalty function Wc which is proportional to - * amount of overlap and congestion. */ - /* delta1 is congestion penalty function */ - delta1 = CostParameter.congestion_penalty * sqrt(fabs(ComputeIntersectionArea(&bounds))); -#if 0 - printf("Wire Congestion Area: %f\n", ComputeIntersectionArea(&bounds)); -#endif - /* free bounding rectangles */ - FreeBoxListMemory(&bounds); - /* now collect module areas (bounding rect of pins/pads) */ - /* two lists for solder side / component side. */ - - ELEMENT_LOOP(PCB->Data); - { - BoxListTypePtr thisside; - BoxListTypePtr otherside; - BoxTypePtr box; - BoxTypePtr lastbox = NULL; - Coord thickness; - Coord clearance; - if (TEST_FLAG(ONSOLDERFLAG, element)) { - thisside = &solderside; - otherside = &componentside; - } - else { - thisside = &componentside; - otherside = &solderside; - } - box = GetBoxMemory(thisside); - /* protect against elements with no pins/pads */ - if (element->PinN == 0 && element->PadN == 0) - continue; - /* initialize box so that it will take the dimensions of - * the first pin/pad */ - box->X1 = MAX_COORD; - box->Y1 = MAX_COORD; - box->X2 = -MAX_COORD; - box->Y2 = -MAX_COORD; - PIN_LOOP(element); - { - thickness = pin->Thickness / 2; - clearance = pin->Clearance * 2; - EXPANDRECTXY(box, - pin->X - (thickness + clearance), - pin->Y - (thickness + clearance), pin->X + (thickness + clearance), pin->Y + (thickness + clearance))} - END_LOOP; - PAD_LOOP(element); - { - thickness = pad->Thickness / 2; - clearance = pad->Clearance * 2; - EXPANDRECTXY(box, - MIN(pad->Point1.X, - pad->Point2.X) - (thickness + - clearance), - MIN(pad->Point1.Y, - pad->Point2.Y) - (thickness + - clearance), - MAX(pad->Point1.X, - pad->Point2.X) + (thickness + clearance), MAX(pad->Point1.Y, pad->Point2.Y) + (thickness + clearance))} - END_LOOP; - /* add a box for each pin to the "opposite side": - * surface mount components can't sit on top of pins */ - if (!CostParameter.fast) - PIN_LOOP(element); - { - box = GetBoxMemory(otherside); - thickness = pin->Thickness / 2; - clearance = pin->Clearance * 2; - /* we ignore clearance here */ - /* (otherwise pins don't fit next to each other) */ - box->X1 = pin->X - thickness; - box->Y1 = pin->Y - thickness; - box->X2 = pin->X + thickness; - box->Y2 = pin->Y + thickness; - /* speed hack! coalesce with last box if we can */ - if (lastbox != NULL && - ((lastbox->X1 == box->X1 && - lastbox->X2 == box->X2 && - MIN(abs(lastbox->Y1 - box->Y2), - abs(box->Y1 - lastbox->Y2)) < - clearance) || (lastbox->Y1 == box->Y1 - && lastbox->Y2 == box->Y2 - && MIN(abs(lastbox->X1 - box->X2), abs(box->X1 - lastbox->X2)) < clearance))) { - EXPANDRECT(lastbox, box); - otherside->BoxN--; - } - else - lastbox = box; - } - END_LOOP; - /* assess out of bounds penalty */ - if (element->VBox.X1 < 0 || element->VBox.Y1 < 0 || element->VBox.X2 > PCB->MaxWidth || element->VBox.Y2 > PCB->MaxHeight) - delta3 += CostParameter.out_of_bounds_penalty; - } - END_LOOP; - /* compute intersection area of module areas box list */ - delta2 = sqrt(fabs(ComputeIntersectionArea(&solderside) + - ComputeIntersectionArea(&componentside))) * - (CostParameter.overlap_penalty_min + (1 - (T / T0)) * CostParameter.overlap_penalty_max); -#if 0 - printf("Module Overlap Area (solder): %f\n", ComputeIntersectionArea(&solderside)); - printf("Module Overlap Area (component): %f\n", ComputeIntersectionArea(&componentside)); -#endif - FreeBoxListMemory(&solderside); - FreeBoxListMemory(&componentside); - /* reward pin/pad x/y alignment */ - /* score higher if pins/pads belong to same *type* of component */ - /* XXX: subkey should be *distance* from thing aligned with, so that - * aligning to something far away isn't profitable */ - { - /* create r tree */ - PointerListType seboxes = { 0, 0, NULL } - , ceboxes = { - 0, 0, NULL}; - struct ebox { - BoxType box; - ElementTypePtr element; - }; - direction_t dir[4] = { NORTH, EAST, SOUTH, WEST }; - struct ebox **boxpp, *boxp; - rtree_t *rt_s, *rt_c; - int factor; - ELEMENT_LOOP(PCB->Data); - { - boxpp = (struct ebox **) - GetPointerMemory(TEST_FLAG(ONSOLDERFLAG, element) ? &seboxes : &ceboxes); - *boxpp = (struct ebox *) malloc(sizeof(**boxpp)); - if (*boxpp == NULL) { - fprintf(stderr, "malloc() failed in %s\n", __FUNCTION__); - exit(1); - } - - (*boxpp)->box = element->VBox; - (*boxpp)->element = element; - } - END_LOOP; - rt_s = r_create_tree((const BoxType **) seboxes.Ptr, seboxes.PtrN, 1); - rt_c = r_create_tree((const BoxType **) ceboxes.Ptr, ceboxes.PtrN, 1); - FreePointerListMemory(&seboxes); - FreePointerListMemory(&ceboxes); - /* now, for each element, find its neighbor on all four sides */ - delta4 = 0; - for (i = 0; i < 4; i++) - ELEMENT_LOOP(PCB->Data); - { - boxp = (struct ebox *) - r_find_neighbor(TEST_FLAG(ONSOLDERFLAG, element) ? rt_s : rt_c, &element->VBox, dir[i]); - /* score bounding box alignments */ - if (!boxp) - continue; - factor = 1; - if (element->Name[0].TextString && - boxp->element->Name[0].TextString && 0 == NSTRCMP(element->Name[0].TextString, boxp->element->Name[0].TextString)) { - delta4 += CostParameter.matching_neighbor_bonus; - factor++; - } - if (element->Name[0].Direction == boxp->element->Name[0].Direction) - delta4 += factor * CostParameter.oriented_neighbor_bonus; - if (element->VBox.X1 == boxp->element->VBox.X1 || - element->VBox.X1 == boxp->element->VBox.X2 || - element->VBox.X2 == boxp->element->VBox.X1 || - element->VBox.X2 == boxp->element->VBox.X2 || - element->VBox.Y1 == boxp->element->VBox.Y1 || - element->VBox.Y1 == boxp->element->VBox.Y2 || - element->VBox.Y2 == boxp->element->VBox.Y1 || element->VBox.Y2 == boxp->element->VBox.Y2) - delta4 += factor * CostParameter.aligned_neighbor_bonus; - } - END_LOOP; - /* free k-d tree memory */ - r_destroy_tree(&rt_s); - r_destroy_tree(&rt_c); - } - /* penalize total area used by this layout */ - { - Coord minX = MAX_COORD, minY = MAX_COORD; - Coord maxX = -MAX_COORD, maxY = -MAX_COORD; - ELEMENT_LOOP(PCB->Data); - { - MAKEMIN(minX, element->VBox.X1); - MAKEMIN(minY, element->VBox.Y1); - MAKEMAX(maxX, element->VBox.X2); - MAKEMAX(maxY, element->VBox.Y2); - } - END_LOOP; - if (minX < maxX && minY < maxY) - delta5 = CostParameter.overall_area_penalty * sqrt(COORD_TO_MIL(maxX - minX) * COORD_TO_MIL(maxY - minY)); - } - if (T == 5) { - T = W + delta1 + delta2 + delta3 - delta4 + delta5; - printf("cost components are %.3f %.3f %.3f %.3f %.3f %.3f\n", - W / T, delta1 / T, delta2 / T, delta3 / T, -delta4 / T, delta5 / T); - } - /* done! */ - return W + (delta1 + delta2 + delta3 - delta4 + delta5); -} - -/* --------------------------------------------------------------------------- - * Perturb: - * 1) flip SMD from solder side to component side or vice-versa. - * 2) rotate component 90, 180, or 270 degrees. - * 3) shift component random + or - amount in random direction. - * (magnitude of shift decreases over time) - * -- Only perturb selected elements (need count/list of selected?) -- - */ -PerturbationType createPerturbation(PointerListTypePtr selected, double T) -{ - PerturbationType pt = { 0 }; - /* pick element to perturb */ - pt.element = (ElementTypePtr) selected->Ptr[random() % selected->PtrN]; - /* exchange, flip/rotate or shift? */ - switch (random() % ((selected->PtrN > 1) ? 3 : 2)) { - case 0: - { /* shift! */ - Coord grid; - double scaleX = CLAMP(sqrt(T), MIL_TO_COORD(2.5), PCB->MaxWidth / 3); - double scaleY = CLAMP(sqrt(T), MIL_TO_COORD(2.5), PCB->MaxHeight / 3); - pt.which = SHIFT; - pt.DX = scaleX * 2 * ((((double) random()) / RAND_MAX) - 0.5); - pt.DY = scaleY * 2 * ((((double) random()) / RAND_MAX) - 0.5); - /* snap to grid. different grids for "high" and "low" T */ - grid = (T > MIL_TO_COORD(10)) ? CostParameter.large_grid_size : CostParameter.small_grid_size; - /* (round away from zero) */ - pt.DX = ((pt.DX / grid) + SGN(pt.DX)) * grid; - pt.DY = ((pt.DY / grid) + SGN(pt.DY)) * grid; - /* limit DX/DY so we don't fall off board */ - pt.DX = MAX(pt.DX, -pt.element->VBox.X1); - pt.DX = MIN(pt.DX, PCB->MaxWidth - pt.element->VBox.X2); - pt.DY = MAX(pt.DY, -pt.element->VBox.Y1); - pt.DY = MIN(pt.DY, PCB->MaxHeight - pt.element->VBox.Y2); - /* all done but the movin' */ - break; - } - case 1: - { /* flip/rotate! */ - /* only flip if it's an SMD component */ - bool isSMD = pt.element->PadN != 0; - pt.which = ROTATE; - pt.rotate = isSMD ? (random() & 3) : (1 + (random() % 3)); - /* 0 - flip; 1-3, rotate. */ - break; - } - case 2: - { /* exchange! */ - pt.which = EXCHANGE; - pt.other = (ElementTypePtr) - selected->Ptr[random() % (selected->PtrN - 1)]; - if (pt.other == pt.element) - pt.other = (ElementTypePtr) selected->Ptr[selected->PtrN - 1]; - /* don't allow exchanging a solderside-side SMD component - * with a non-SMD component. */ - if ((pt.element->PinN != 0 /* non-SMD */ && - TEST_FLAG(ONSOLDERFLAG, pt.other)) || (pt.other->PinN != 0 /* non-SMD */ && - TEST_FLAG(ONSOLDERFLAG, pt.element))) - return createPerturbation(selected, T); - break; - } - default: - assert(0); - } - return pt; -} - -void doPerturb(PerturbationType * pt, bool undo) -{ - Coord bbcx, bbcy; - /* compute center of element bounding box */ - bbcx = (pt->element->VBox.X1 + pt->element->VBox.X2) / 2; - bbcy = (pt->element->VBox.Y1 + pt->element->VBox.Y2) / 2; - /* do exchange, shift or flip/rotate */ - switch (pt->which) { - case SHIFT: - { - Coord DX = pt->DX, DY = pt->DY; - if (undo) { - DX = -DX; - DY = -DY; - } - MoveElementLowLevel(PCB->Data, pt->element, DX, DY); - return; - } - case ROTATE: - { - unsigned b = pt->rotate; - if (undo) - b = (4 - b) & 3; - /* 0 - flip; 1-3, rotate. */ - if (b) - RotateElementLowLevel(PCB->Data, pt->element, bbcx, bbcy, b); - else { - Coord y = pt->element->VBox.Y1; - MirrorElementCoordinates(PCB->Data, pt->element, 0); - /* mirroring moves the element. move it back. */ - MoveElementLowLevel(PCB->Data, pt->element, 0, y - pt->element->VBox.Y1); - } - return; - } - case EXCHANGE: - { - /* first exchange positions */ - Coord x1 = pt->element->VBox.X1; - Coord y1 = pt->element->VBox.Y1; - Coord x2 = pt->other->BoundingBox.X1; - Coord y2 = pt->other->BoundingBox.Y1; - MoveElementLowLevel(PCB->Data, pt->element, x2 - x1, y2 - y1); - MoveElementLowLevel(PCB->Data, pt->other, x1 - x2, y1 - y2); - /* then flip both elements if they are on opposite sides */ - if (TEST_FLAG(ONSOLDERFLAG, pt->element) != TEST_FLAG(ONSOLDERFLAG, pt->other)) { - PerturbationType mypt; - mypt.element = pt->element; - mypt.which = ROTATE; - mypt.rotate = 0; /* flip */ - doPerturb(&mypt, undo); - mypt.element = pt->other; - doPerturb(&mypt, undo); - } - /* done */ - return; - } - default: - assert(0); - } -} - -/* --------------------------------------------------------------------------- - * Auto-place selected components. - */ -bool AutoPlaceSelected(void) -{ - NetListTypePtr Nets; - PointerListType Selected = { 0, 0, NULL }; - PerturbationType pt; - double C0, T0; - bool changed = false; - - /* (initial netlist processing copied from AddAllRats) */ - /* the netlist library has the text form - * ProcNetlist fills in the Netlist - * structure the way the final routing - * is supposed to look - */ - Nets = ProcNetlist(&(PCB->NetlistLib[NETLIST_EDITED])); - if (!Nets) { - Message(_("Can't add rat lines because no netlist is loaded.\n")); - goto done; - } - - Selected = collectSelectedElements(); - if (Selected.PtrN == 0) { - Message(_("No elements selected to autoplace.\n")); - goto done; - } - - /* simulated annealing */ - { /* compute T0 by doing a random series of moves. */ - const int TRIALS = 10; - const double Tx = MIL_TO_COORD(300), P = 0.95; - double Cs = 0.0; - int i; - C0 = ComputeCost(Nets, Tx, Tx); - for (i = 0; i < TRIALS; i++) { - pt = createPerturbation(&Selected, INCH_TO_COORD(1)); - doPerturb(&pt, false); - Cs += fabs(ComputeCost(Nets, Tx, Tx) - C0); - doPerturb(&pt, true); - } - T0 = -(Cs / TRIALS) / log(P); - printf("Initial T: %f\n", T0); - } - /* now anneal in earnest */ - { - double T = T0; - long steps = 0; - int good_moves = 0, moves = 0; - const int good_move_cutoff = CostParameter.m * Selected.PtrN; - const int move_cutoff = 2 * good_move_cutoff; - printf("Starting cost is %.0f\n", ComputeCost(Nets, T0, 5)); - C0 = ComputeCost(Nets, T0, T); - while (1) { - double Cprime; - pt = createPerturbation(&Selected, T); - doPerturb(&pt, false); - Cprime = ComputeCost(Nets, T0, T); - if (Cprime < C0) { /* good move! */ - C0 = Cprime; - good_moves++; - steps++; - } - else if ((random() / (double) RAND_MAX) < exp(MIN(MAX(-20, (C0 - Cprime) / T), 20))) { - /* not good but keep it anyway */ - C0 = Cprime; - steps++; - } - else - doPerturb(&pt, true); /* undo last change */ - moves++; - /* are we at the end of a stage? */ - if (good_moves >= good_move_cutoff || moves >= move_cutoff) { - printf("END OF STAGE: COST %.0f\t" "GOOD_MOVES %d\tMOVES %d\t" "T: %.1f\n", C0, good_moves, moves, T); - /* is this the end? */ - if (T < 5 || good_moves < moves / CostParameter.good_ratio) - break; - /* nope, adjust T and continue */ - moves = good_moves = 0; - T *= CostParameter.gamma; - /* cost is T dependent, so recompute */ - C0 = ComputeCost(Nets, T0, T); - } - } - changed = (steps > 0); - } -done: - if (changed) { - DeleteRats(false); - AddAllRats(false, NULL); - Redraw(); - } - FreePointerListMemory(&Selected); - return (changed); -} Index: trunk/src/autoplace.h =================================================================== --- trunk/src/autoplace.h (revision 1046) +++ trunk/src/autoplace.h (nonexistent) @@ -1,45 +0,0 @@ -/* $Id$ */ - -/* - * COPYRIGHT - * - * PCB, interactive printed circuit board design - * Copyright (C) 1994,1995,1996 Thomas Nau - * Copyright (C) 1998,1999,2000,2001 harry eaton - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - * - * Contact addresses for paper mail and Email: - * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA - * haceaton@aplcomm.jhuapl.edu - * - */ - -/* this file, autoplace.h, was written and is - * Copyright (c) 2001 C. Scott Ananian. - * - */ - -/* prototypes for autoplace routines - */ - -#ifndef PCB_AUTOPLACE_H -#define PCB_AUTOPLACE_H - -#include "global.h" - -bool AutoPlaceSelected(void); - -#endif Index: trunk/src/Makefile.dep =================================================================== --- trunk/src/Makefile.dep (revision 1046) +++ trunk/src/Makefile.dep (revision 1047) @@ -2,7 +2,7 @@ action.o: action.c ../config.h ../config.manual.h ../config.auto.h \ global.h const.h ../globalconst.h ../config.h macro.h hid.h polyarea.h \ - libpcb_fp.h action.h autoplace.h buffer.h change.h command.h \ + libpcb_fp.h action.h buffer.h change.h command.h \ copy.h create.h crosshair.h data.h draw.h error.h file.h find.h insert.h \ line.h mymem.h misc.h ds.h mirror.h move.h polygon.h rats.h remove.h \ report.h rotate.h rubberband.h search.h select.h set.h thermal.h undo.h \ @@ -9,7 +9,7 @@ rtree.h pcb-printf.h plugins.h rats_patch.h autoplace.o: autoplace.c ../config.h ../config.manual.h ../config.auto.h \ global.h const.h ../globalconst.h ../config.h macro.h hid.h polyarea.h \ - libpcb_fp.h autoplace.h box.h misc.h ds.h mymem.h compat.h data.h draw.h \ + libpcb_fp.h box.h misc.h ds.h mymem.h compat.h data.h draw.h \ error.h intersect.h rtree.h mirror.h move.h rats.h remove.h rotate.h buffer.o: buffer.c ../config.h ../config.manual.h ../config.auto.h \ global.h const.h ../globalconst.h ../config.h macro.h hid.h polyarea.h \ @@ -415,7 +415,7 @@ ../config.h macro.h hid.h polyarea.h libpcb_fp.h hid/gtk/gtkhid.h \ hid/gtk/gui.h hid.h hid/common/hid_resource.h resource.h data.h global.h \ misc.h ds.h mymem.h hid/gtk/ghid-coord-entry.h hid/gtk/ghid-main-menu.h \ - hid/gtk/gui-pinout-preview.h hid/gtk/../hidint.h action.h autoplace.h \ + hid/gtk/gui-pinout-preview.h hid/gtk/../hidint.h action.h \ autoroute.h buffer.h change.h command.h copy.h create.h crosshair.h \ draw.h error.h file.h find.h gpcb-menu.h insert.h line.h mymem.h move.h \ pcb-printf.h polygon.h rats.h remove.h report.h rotate.h rubberband.h \ Index: trunk/src/Makefile.in =================================================================== --- trunk/src/Makefile.in (revision 1046) +++ trunk/src/Makefile.in (revision 1047) @@ -12,7 +12,6 @@ # main: objects put /local/pcb/OBJS [@ action.o - autoplace.o buffer.o change.o clip.o @@ -127,6 +126,7 @@ include {Makefile.in.mod/lpr} include {../src_plugins/autoroute/Makefile.mod} +include {../src_plugins/autoplace/Makefile.mod} if /target/libs/script/gpmi/presents then Index: trunk/src/action.c =================================================================== --- trunk/src/action.c (revision 1046) +++ trunk/src/action.c (revision 1047) @@ -35,7 +35,6 @@ #include "global.h" #include "action.h" -#include "autoplace.h" #include "buffer.h" #include "change.h" #include "command.h" @@ -3634,29 +3633,6 @@ /* --------------------------------------------------------------------------- */ -static const char autoplace_syntax[] = "AutoPlaceSelected()"; - -static const char autoplace_help[] = "Auto-place selected components."; - -/* %start-doc actions AutoPlaceSelected - -Attempts to re-arrange the selected components such that the nets -connecting them are minimized. Note that you cannot undo this. - -%end-doc */ - -static int ActionAutoPlaceSelected(int argc, char **argv, Coord x, Coord y) -{ - hid_action("Busy"); - if (gui->confirm_dialog(_("Auto-placement can NOT be undone.\n" "Do you want to continue anyway?\n"), 0)) { - if (AutoPlaceSelected()) - SetChangedFlag(true); - } - return 0; -} - -/* --------------------------------------------------------------------------- */ - static const char markcrosshair_syntax[] = "MarkCrosshair()\n" "MarkCrosshair(Center)"; static const char markcrosshair_help[] = "Set/Reset the Crosshair mark."; @@ -7592,9 +7568,6 @@ {"Atomic", 0, ActionAtomic, atomic_help, atomic_syntax} , - {"AutoPlaceSelected", 0, ActionAutoPlaceSelected, - autoplace_help, autoplace_syntax} - , {"ChangeClearSize", 0, ActionChangeClearSize, changeclearsize_help, changeclearsize_syntax} , Index: trunk/src_plugins/autoplace/Makefile =================================================================== --- trunk/src_plugins/autoplace/Makefile (nonexistent) +++ trunk/src_plugins/autoplace/Makefile (revision 1047) @@ -0,0 +1,4 @@ +all: + cd ../../src && make mod_autoplace + + Index: trunk/src_plugins/autoplace/Makefile.mod =================================================================== --- trunk/src_plugins/autoplace/Makefile.mod (nonexistent) +++ trunk/src_plugins/autoplace/Makefile.mod (revision 1047) @@ -0,0 +1,26 @@ +append /local/pcb/autoplace/enable {} +append /local/pcb/autoplace/buildin {} + +append /local/pcb/autoplace/OBJS [@ ${PLUGDIR}/autoplace/autoplace.o ${PLUGDIR}/autoplace/action.o @] + +if /local/pcb/autoplace/enable then + if /local/pcb/autoplace/buildin then + append /local/pcb/OBJS /local/pcb/autoplace/OBJS + append /local/pcb/RULES [@ + +mod_autoplace: all + +@] + + else + append /local/pcb/all [@ ${PLUGDIR}/autoplace/autoplace.so @] + append /local/pcb/RULES [@ + +${PLUGDIR}/autoplace/autoplace.so: @/local/pcb/autoplace/OBJS@ + $(CC) $(LDFLAGS) -shared @cc/rdynamic@ -o ${PLUGDIR}/autoplace/autoplace.so @/local/pcb/autoplace/OBJS@ + +mod_autoplace: ${PLUGDIR}/autoplace/autoplace.so + +@] + end +end Index: trunk/src_plugins/autoplace/action.c =================================================================== --- trunk/src_plugins/autoplace/action.c (nonexistent) +++ trunk/src_plugins/autoplace/action.c (revision 1047) @@ -0,0 +1,67 @@ +/* + * COPYRIGHT + * + * PCB, interactive printed circuit board design + * Copyright (C) 1994,1995,1996 Thomas Nau + * Copyright (C) 1997, 1998, 1999, 2000, 2001 Harry Eaton + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Contact addresses for paper mail and Email: + * Harry Eaton, 6697 Buttonhole Ct, Columbia, MD 21044, USA + * haceaton@aplcomm.jhuapl.edu + * + */ + +#include "config.h" +#include "global.h" +#include "autoplace.h" + + +static const char autoplace_syntax[] = "AutoPlaceSelected()"; + +static const char autoplace_help[] = "Auto-place selected components."; + +/* %start-doc actions AutoPlaceSelected + +Attempts to re-arrange the selected components such that the nets +connecting them are minimized. Note that you cannot undo this. + +%end-doc */ + +static int ActionAutoPlaceSelected(int argc, char **argv, Coord x, Coord y) +{ + hid_action("Busy"); + if (gui->confirm_dialog(_("Auto-placement can NOT be undone.\n" "Do you want to continue anyway?\n"), 0)) { + if (AutoPlaceSelected()) + SetChangedFlag(true); + } + return 0; +} + + +HID_Action autoplace_action_list[] = { + {"AutoPlaceSelected", 0, ActionAutoPlaceSelected, + autoplace_help, autoplace_syntax} + , +}; + +REGISTER_ACTIONS(autoplace_action_list) + +#include "dolists.h" +void hid_autoplace_init(void) +{ + REGISTER_ACTIONS(autoplace_action_list) +} Index: trunk/src_plugins/autoplace/autoplace.c =================================================================== --- trunk/src_plugins/autoplace/autoplace.c (nonexistent) +++ trunk/src_plugins/autoplace/autoplace.c (revision 1047) @@ -0,0 +1,766 @@ +/* $Id$ */ + +/* + * COPYRIGHT + * + * PCB, interactive printed circuit board design + * Copyright (C) 1994,1995,1996 Thomas Nau + * Copyright (C) 1998,1999,2000,2001 harry eaton + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * Contact addresses for paper mail and Email: + * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA + * haceaton@aplcomm.jhuapl.edu + * + */ + +/* + * This moduel, autoplace.c, was written by and is + * Copyright (c) 2001 C. Scott Ananian + */ + +/* functions used to autoplace elements. + */ + +#include "config.h" + +#include +#include +#include +#include + +#include "global.h" + +#include "autoplace.h" +#include "box.h" +#include "compat.h" +#include "data.h" +#include "draw.h" +#include "error.h" +#include "intersect.h" +#include "rtree.h" +#include "macro.h" +#include "mirror.h" +#include "misc.h" +#include "move.h" +#include "mymem.h" +#include "rats.h" +#include "remove.h" +#include "rotate.h" + + +RCSID("$Id$"); + +#define EXPANDRECTXY(r1, x1, y1, x2, y2) { \ + r1->X1=MIN(r1->X1, x1); r1->Y1=MIN(r1->Y1, y1); \ + r1->X2=MAX(r1->X2, x2); r1->Y2=MAX(r1->Y2, y2); \ +} +#define EXPANDRECT(r1, r2) EXPANDRECTXY(r1, r2->X1, r2->Y1, r2->X2, r2->Y2) + +/* --------------------------------------------------------------------------- + * some local prototypes + */ +static double ComputeCost(NetListTypePtr Nets, double T0, double T); + +/* --------------------------------------------------------------------------- + * some local types + */ +const struct { + double via_cost; + double congestion_penalty; /* penalty length / unit area */ + double overlap_penalty_min; /* penalty length / unit area at start */ + double overlap_penalty_max; /* penalty length / unit area at end */ + double out_of_bounds_penalty; /* assessed for each component oob */ + double overall_area_penalty; /* penalty length / unit area */ + double matching_neighbor_bonus; /* length bonus per same-type neigh. */ + double aligned_neighbor_bonus; /* length bonus per aligned neigh. */ + double oriented_neighbor_bonus; /* length bonus per same-rot neigh. */ +#if 0 + double pin_alignment_bonus; /* length bonus per exact alignment */ + double bound_alignment_bonus; /* length bonus per exact alignment */ +#endif + double m; /* annealing stage cutoff constant */ + double gamma; /* annealing schedule constant */ + int good_ratio; /* ratio of moves to good moves for halting */ + bool fast; /* ignore SMD/pin conflicts */ + Coord large_grid_size; /* snap perturbations to this grid when T is high */ + Coord small_grid_size; /* snap to this grid when T is small. */ +} +/* wire cost is manhattan distance (in mils), thus 1 inch = 1000 */ CostParameter = +{ + 3e3, /* via cost */ + 2e-2, /* congestion penalty */ + 1e-2, /* initial overlap penalty */ + 1e2, /* final overlap penalty */ + 1e3, /* out of bounds penalty */ + 1e0, /* penalty for total area used */ + 1e0, /* subtract 1000 from cost for every same-type neighbor */ + 1e0, /* subtract 1000 from cost for every aligned neighbor */ + 1e0, /* subtract 1000 from cost for every same-rotation neighbor */ + 20, /* move on when each module has been profitably moved 20 times */ + 0.75, /* annealing schedule constant: 0.85 */ + 40, /* halt when there are 60 times as many moves as good moves */ + false, /* don't ignore SMD/pin conflicts */ + MIL_TO_COORD(100), /* coarse grid is 100 mils */ + MIL_TO_COORD(10), /* fine grid is 10 mils */ +}; + +typedef struct { + ElementTypePtr *element; + Cardinal elementN; +} ElementPtrListType; + +enum ewhich { SHIFT, ROTATE, EXCHANGE }; + +typedef struct { + ElementTypePtr element; + enum ewhich which; + Coord DX, DY; /* for shift */ + unsigned rotate; /* for rotate/flip */ + ElementTypePtr other; /* for exchange */ +} PerturbationType; + +/* --------------------------------------------------------------------------- + * some local identifiers + */ + +/* --------------------------------------------------------------------------- + * Update the X, Y and group position information stored in the NetList after + * elements have possibly been moved, rotated, flipped, etc. + */ +static void UpdateXY(NetListTypePtr Nets) +{ + Cardinal SLayer, CLayer; + Cardinal i, j; + /* find layer groups of the component side and solder side */ + SLayer = GetLayerGroupNumberByNumber(solder_silk_layer); + CLayer = GetLayerGroupNumberByNumber(component_silk_layer); + /* update all nets */ + for (i = 0; i < Nets->NetN; i++) { + for (j = 0; j < Nets->Net[i].ConnectionN; j++) { + ConnectionTypePtr c = &(Nets->Net[i].Connection[j]); + switch (c->type) { + case PAD_TYPE: + c->group = TEST_FLAG(ONSOLDERFLAG, (ElementTypePtr) c->ptr1) + ? SLayer : CLayer; + c->X = ((PadTypePtr) c->ptr2)->Point1.X; + c->Y = ((PadTypePtr) c->ptr2)->Point1.Y; + break; + case PIN_TYPE: + c->group = SLayer; /* any layer will do */ + c->X = ((PinTypePtr) c->ptr2)->X; + c->Y = ((PinTypePtr) c->ptr2)->Y; + break; + default: + Message("Odd connection type encountered in " "UpdateXY"); + break; + } + } + } +} + +/* --------------------------------------------------------------------------- + * Create a list of selected elements. + */ +static PointerListType collectSelectedElements() +{ + PointerListType list = { 0, 0, NULL }; + ELEMENT_LOOP(PCB->Data); + { + if (TEST_FLAG(SELECTEDFLAG, element)) { + ElementTypePtr *epp = (ElementTypePtr *) GetPointerMemory(&list); + *epp = element; + } + } + END_LOOP; + return list; +} + +#if 0 /* only for debugging box lists */ +#include "create.h" +/* makes a line on the solder layer surrounding all boxes in blist */ +static void showboxes(BoxListTypePtr blist) +{ + Cardinal i; + LayerTypePtr SLayer = &(PCB->Data->Layer[solder_silk_layer]); + for (i = 0; i < blist->BoxN; i++) { + CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y1, blist->Box[i].X2, blist->Box[i].Y1, 1, 1, 0); + CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y2, blist->Box[i].X2, blist->Box[i].Y2, 1, 1, 0); + CreateNewLineOnLayer(SLayer, blist->Box[i].X1, blist->Box[i].Y1, blist->Box[i].X1, blist->Box[i].Y2, 1, 1, 0); + CreateNewLineOnLayer(SLayer, blist->Box[i].X2, blist->Box[i].Y1, blist->Box[i].X2, blist->Box[i].Y2, 1, 1, 0); + } +} +#endif + +/* --------------------------------------------------------------------------- + * Helper function to compute "closest neighbor" for a box in a rtree. + * The closest neighbor on a certain side is the closest one in a trapezoid + * emanating from that side. + */ +/*------ r_find_neighbor ------*/ +struct r_neighbor_info { + const BoxType *neighbor; + BoxType trap; + direction_t search_dir; +}; +#define ROTATEBOX(box) { Coord t;\ + t = (box).X1; (box).X1 = - (box).Y1; (box).Y1 = t;\ + t = (box).X2; (box).X2 = - (box).Y2; (box).Y2 = t;\ + t = (box).X1; (box).X1 = (box).X2; (box).X2 = t;\ +} +/* helper methods for __r_find_neighbor */ +static int __r_find_neighbor_reg_in_sea(const BoxType * region, void *cl) +{ + struct r_neighbor_info *ni = (struct r_neighbor_info *) cl; + BoxType query = *region; + ROTATEBOX_TO_NORTH(query, ni->search_dir); + /* ______________ __ trap.y1 __ + * \ / |__| query rect. + * \__________/ __ trap.y2 + * | | + * trap.x1 trap.x2 sides at 45-degree angle + */ + return (query.Y2 > ni->trap.Y1) && (query.Y1 < ni->trap.Y2) && + (query.X2 + ni->trap.Y2 > ni->trap.X1 + query.Y1) && (query.X1 + query.Y1 < ni->trap.X2 + ni->trap.Y2); +} + +static int __r_find_neighbor_rect_in_reg(const BoxType * box, void *cl) +{ + struct r_neighbor_info *ni = (struct r_neighbor_info *) cl; + BoxType query = *box; + int r; + ROTATEBOX_TO_NORTH(query, ni->search_dir); + /* ______________ __ trap.y1 __ + * \ / |__| query rect. + * \__________/ __ trap.y2 + * | | + * trap.x1 trap.x2 sides at 45-degree angle + */ + r = (query.Y2 > ni->trap.Y1) && (query.Y1 < ni->trap.Y2) && + (query.X2 + ni->trap.Y2 > ni->trap.X1 + query.Y1) && (query.X1 + query.Y1 < ni->trap.X2 + ni->trap.Y2); + r = r && (query.Y2 <= ni->trap.Y2); + if (r) { + ni->trap.Y1 = query.Y2; + ni->neighbor = box; + } + return r; +} + +/* main r_find_neighbor routine. Returns NULL if no neighbor in the + * requested direction. */ +static const BoxType *r_find_neighbor(rtree_t * rtree, const BoxType * box, direction_t search_direction) +{ + struct r_neighbor_info ni; + BoxType bbox; + + ni.neighbor = NULL; + ni.trap = *box; + ni.search_dir = search_direction; + + bbox.X1 = bbox.Y1 = 0; + bbox.X2 = PCB->MaxWidth; + bbox.Y2 = PCB->MaxHeight; + /* rotate so that we can use the 'north' case for everything */ + ROTATEBOX_TO_NORTH(bbox, search_direction); + ROTATEBOX_TO_NORTH(ni.trap, search_direction); + /* shift Y's such that trap contains full bounds of trapezoid */ + ni.trap.Y2 = ni.trap.Y1; + ni.trap.Y1 = bbox.Y1; + /* do the search! */ + r_search(rtree, NULL, __r_find_neighbor_reg_in_sea, __r_find_neighbor_rect_in_reg, &ni); + return ni.neighbor; +} + +/* --------------------------------------------------------------------------- + * Compute cost function. + * note that area overlap cost is correct for SMD devices: SMD devices on + * opposite sides of the board don't overlap. + * + * Algorithms follow those described in sections 4.1 of + * "Placement and Routing of Electronic Modules" edited by Michael Pecht + * Marcel Dekker, Inc. 1993. ISBN: 0-8247-8916-4 TK7868.P7.P57 1993 + */ +static double ComputeCost(NetListTypePtr Nets, double T0, double T) +{ + double W = 0; /* wire cost */ + double delta1 = 0; /* wire congestion penalty function */ + double delta2 = 0; /* module overlap penalty function */ + double delta3 = 0; /* out of bounds penalty */ + double delta4 = 0; /* alignment bonus */ + double delta5 = 0; /* total area penalty */ + Cardinal i, j; + Coord minx, maxx, miny, maxy; + bool allpads, allsameside; + Cardinal thegroup; + BoxListType bounds = { 0, 0, NULL }; /* save bounding rectangles here */ + BoxListType solderside = { 0, 0, NULL }; /* solder side component bounds */ + BoxListType componentside = { 0, 0, NULL }; /* component side bounds */ + /* make sure the NetList have the proper updated X and Y coords */ + UpdateXY(Nets); + /* wire length term. approximated by half-perimeter of minimum + * rectangle enclosing the net. Note that we penalize vias in + * all-SMD nets by making the rectangle a cube and weighting + * the "layer height" of the net. */ + for (i = 0; i < Nets->NetN; i++) { + NetTypePtr n = &Nets->Net[i]; + if (n->ConnectionN < 2) + continue; /* no cost to go nowhere */ + minx = maxx = n->Connection[0].X; + miny = maxy = n->Connection[0].Y; + thegroup = n->Connection[0].group; + allpads = (n->Connection[0].type == PAD_TYPE); + allsameside = true; + for (j = 1; j < n->ConnectionN; j++) { + ConnectionTypePtr c = &(n->Connection[j]); + MAKEMIN(minx, c->X); + MAKEMAX(maxx, c->X); + MAKEMIN(miny, c->Y); + MAKEMAX(maxy, c->Y); + if (c->type != PAD_TYPE) + allpads = false; + if (c->group != thegroup) + allsameside = false; + } + /* save bounding rectangle */ + { + BoxTypePtr box = GetBoxMemory(&bounds); + box->X1 = minx; + box->Y1 = miny; + box->X2 = maxx; + box->Y2 = maxy; + } + /* okay, add half-perimeter to cost! */ + W += COORD_TO_MIL(maxx - minx) + COORD_TO_MIL(maxy - miny) + ((allpads && !allsameside) ? CostParameter.via_cost : 0); + } + /* now compute penalty function Wc which is proportional to + * amount of overlap and congestion. */ + /* delta1 is congestion penalty function */ + delta1 = CostParameter.congestion_penalty * sqrt(fabs(ComputeIntersectionArea(&bounds))); +#if 0 + printf("Wire Congestion Area: %f\n", ComputeIntersectionArea(&bounds)); +#endif + /* free bounding rectangles */ + FreeBoxListMemory(&bounds); + /* now collect module areas (bounding rect of pins/pads) */ + /* two lists for solder side / component side. */ + + ELEMENT_LOOP(PCB->Data); + { + BoxListTypePtr thisside; + BoxListTypePtr otherside; + BoxTypePtr box; + BoxTypePtr lastbox = NULL; + Coord thickness; + Coord clearance; + if (TEST_FLAG(ONSOLDERFLAG, element)) { + thisside = &solderside; + otherside = &componentside; + } + else { + thisside = &componentside; + otherside = &solderside; + } + box = GetBoxMemory(thisside); + /* protect against elements with no pins/pads */ + if (element->PinN == 0 && element->PadN == 0) + continue; + /* initialize box so that it will take the dimensions of + * the first pin/pad */ + box->X1 = MAX_COORD; + box->Y1 = MAX_COORD; + box->X2 = -MAX_COORD; + box->Y2 = -MAX_COORD; + PIN_LOOP(element); + { + thickness = pin->Thickness / 2; + clearance = pin->Clearance * 2; + EXPANDRECTXY(box, + pin->X - (thickness + clearance), + pin->Y - (thickness + clearance), pin->X + (thickness + clearance), pin->Y + (thickness + clearance))} + END_LOOP; + PAD_LOOP(element); + { + thickness = pad->Thickness / 2; + clearance = pad->Clearance * 2; + EXPANDRECTXY(box, + MIN(pad->Point1.X, + pad->Point2.X) - (thickness + + clearance), + MIN(pad->Point1.Y, + pad->Point2.Y) - (thickness + + clearance), + MAX(pad->Point1.X, + pad->Point2.X) + (thickness + clearance), MAX(pad->Point1.Y, pad->Point2.Y) + (thickness + clearance))} + END_LOOP; + /* add a box for each pin to the "opposite side": + * surface mount components can't sit on top of pins */ + if (!CostParameter.fast) + PIN_LOOP(element); + { + box = GetBoxMemory(otherside); + thickness = pin->Thickness / 2; + clearance = pin->Clearance * 2; + /* we ignore clearance here */ + /* (otherwise pins don't fit next to each other) */ + box->X1 = pin->X - thickness; + box->Y1 = pin->Y - thickness; + box->X2 = pin->X + thickness; + box->Y2 = pin->Y + thickness; + /* speed hack! coalesce with last box if we can */ + if (lastbox != NULL && + ((lastbox->X1 == box->X1 && + lastbox->X2 == box->X2 && + MIN(abs(lastbox->Y1 - box->Y2), + abs(box->Y1 - lastbox->Y2)) < + clearance) || (lastbox->Y1 == box->Y1 + && lastbox->Y2 == box->Y2 + && MIN(abs(lastbox->X1 - box->X2), abs(box->X1 - lastbox->X2)) < clearance))) { + EXPANDRECT(lastbox, box); + otherside->BoxN--; + } + else + lastbox = box; + } + END_LOOP; + /* assess out of bounds penalty */ + if (element->VBox.X1 < 0 || element->VBox.Y1 < 0 || element->VBox.X2 > PCB->MaxWidth || element->VBox.Y2 > PCB->MaxHeight) + delta3 += CostParameter.out_of_bounds_penalty; + } + END_LOOP; + /* compute intersection area of module areas box list */ + delta2 = sqrt(fabs(ComputeIntersectionArea(&solderside) + + ComputeIntersectionArea(&componentside))) * + (CostParameter.overlap_penalty_min + (1 - (T / T0)) * CostParameter.overlap_penalty_max); +#if 0 + printf("Module Overlap Area (solder): %f\n", ComputeIntersectionArea(&solderside)); + printf("Module Overlap Area (component): %f\n", ComputeIntersectionArea(&componentside)); +#endif + FreeBoxListMemory(&solderside); + FreeBoxListMemory(&componentside); + /* reward pin/pad x/y alignment */ + /* score higher if pins/pads belong to same *type* of component */ + /* XXX: subkey should be *distance* from thing aligned with, so that + * aligning to something far away isn't profitable */ + { + /* create r tree */ + PointerListType seboxes = { 0, 0, NULL } + , ceboxes = { + 0, 0, NULL}; + struct ebox { + BoxType box; + ElementTypePtr element; + }; + direction_t dir[4] = { NORTH, EAST, SOUTH, WEST }; + struct ebox **boxpp, *boxp; + rtree_t *rt_s, *rt_c; + int factor; + ELEMENT_LOOP(PCB->Data); + { + boxpp = (struct ebox **) + GetPointerMemory(TEST_FLAG(ONSOLDERFLAG, element) ? &seboxes : &ceboxes); + *boxpp = (struct ebox *) malloc(sizeof(**boxpp)); + if (*boxpp == NULL) { + fprintf(stderr, "malloc() failed in %s\n", __FUNCTION__); + exit(1); + } + + (*boxpp)->box = element->VBox; + (*boxpp)->element = element; + } + END_LOOP; + rt_s = r_create_tree((const BoxType **) seboxes.Ptr, seboxes.PtrN, 1); + rt_c = r_create_tree((const BoxType **) ceboxes.Ptr, ceboxes.PtrN, 1); + FreePointerListMemory(&seboxes); + FreePointerListMemory(&ceboxes); + /* now, for each element, find its neighbor on all four sides */ + delta4 = 0; + for (i = 0; i < 4; i++) + ELEMENT_LOOP(PCB->Data); + { + boxp = (struct ebox *) + r_find_neighbor(TEST_FLAG(ONSOLDERFLAG, element) ? rt_s : rt_c, &element->VBox, dir[i]); + /* score bounding box alignments */ + if (!boxp) + continue; + factor = 1; + if (element->Name[0].TextString && + boxp->element->Name[0].TextString && 0 == NSTRCMP(element->Name[0].TextString, boxp->element->Name[0].TextString)) { + delta4 += CostParameter.matching_neighbor_bonus; + factor++; + } + if (element->Name[0].Direction == boxp->element->Name[0].Direction) + delta4 += factor * CostParameter.oriented_neighbor_bonus; + if (element->VBox.X1 == boxp->element->VBox.X1 || + element->VBox.X1 == boxp->element->VBox.X2 || + element->VBox.X2 == boxp->element->VBox.X1 || + element->VBox.X2 == boxp->element->VBox.X2 || + element->VBox.Y1 == boxp->element->VBox.Y1 || + element->VBox.Y1 == boxp->element->VBox.Y2 || + element->VBox.Y2 == boxp->element->VBox.Y1 || element->VBox.Y2 == boxp->element->VBox.Y2) + delta4 += factor * CostParameter.aligned_neighbor_bonus; + } + END_LOOP; + /* free k-d tree memory */ + r_destroy_tree(&rt_s); + r_destroy_tree(&rt_c); + } + /* penalize total area used by this layout */ + { + Coord minX = MAX_COORD, minY = MAX_COORD; + Coord maxX = -MAX_COORD, maxY = -MAX_COORD; + ELEMENT_LOOP(PCB->Data); + { + MAKEMIN(minX, element->VBox.X1); + MAKEMIN(minY, element->VBox.Y1); + MAKEMAX(maxX, element->VBox.X2); + MAKEMAX(maxY, element->VBox.Y2); + } + END_LOOP; + if (minX < maxX && minY < maxY) + delta5 = CostParameter.overall_area_penalty * sqrt(COORD_TO_MIL(maxX - minX) * COORD_TO_MIL(maxY - minY)); + } + if (T == 5) { + T = W + delta1 + delta2 + delta3 - delta4 + delta5; + printf("cost components are %.3f %.3f %.3f %.3f %.3f %.3f\n", + W / T, delta1 / T, delta2 / T, delta3 / T, -delta4 / T, delta5 / T); + } + /* done! */ + return W + (delta1 + delta2 + delta3 - delta4 + delta5); +} + +/* --------------------------------------------------------------------------- + * Perturb: + * 1) flip SMD from solder side to component side or vice-versa. + * 2) rotate component 90, 180, or 270 degrees. + * 3) shift component random + or - amount in random direction. + * (magnitude of shift decreases over time) + * -- Only perturb selected elements (need count/list of selected?) -- + */ +PerturbationType createPerturbation(PointerListTypePtr selected, double T) +{ + PerturbationType pt = { 0 }; + /* pick element to perturb */ + pt.element = (ElementTypePtr) selected->Ptr[random() % selected->PtrN]; + /* exchange, flip/rotate or shift? */ + switch (random() % ((selected->PtrN > 1) ? 3 : 2)) { + case 0: + { /* shift! */ + Coord grid; + double scaleX = CLAMP(sqrt(T), MIL_TO_COORD(2.5), PCB->MaxWidth / 3); + double scaleY = CLAMP(sqrt(T), MIL_TO_COORD(2.5), PCB->MaxHeight / 3); + pt.which = SHIFT; + pt.DX = scaleX * 2 * ((((double) random()) / RAND_MAX) - 0.5); + pt.DY = scaleY * 2 * ((((double) random()) / RAND_MAX) - 0.5); + /* snap to grid. different grids for "high" and "low" T */ + grid = (T > MIL_TO_COORD(10)) ? CostParameter.large_grid_size : CostParameter.small_grid_size; + /* (round away from zero) */ + pt.DX = ((pt.DX / grid) + SGN(pt.DX)) * grid; + pt.DY = ((pt.DY / grid) + SGN(pt.DY)) * grid; + /* limit DX/DY so we don't fall off board */ + pt.DX = MAX(pt.DX, -pt.element->VBox.X1); + pt.DX = MIN(pt.DX, PCB->MaxWidth - pt.element->VBox.X2); + pt.DY = MAX(pt.DY, -pt.element->VBox.Y1); + pt.DY = MIN(pt.DY, PCB->MaxHeight - pt.element->VBox.Y2); + /* all done but the movin' */ + break; + } + case 1: + { /* flip/rotate! */ + /* only flip if it's an SMD component */ + bool isSMD = pt.element->PadN != 0; + pt.which = ROTATE; + pt.rotate = isSMD ? (random() & 3) : (1 + (random() % 3)); + /* 0 - flip; 1-3, rotate. */ + break; + } + case 2: + { /* exchange! */ + pt.which = EXCHANGE; + pt.other = (ElementTypePtr) + selected->Ptr[random() % (selected->PtrN - 1)]; + if (pt.other == pt.element) + pt.other = (ElementTypePtr) selected->Ptr[selected->PtrN - 1]; + /* don't allow exchanging a solderside-side SMD component + * with a non-SMD component. */ + if ((pt.element->PinN != 0 /* non-SMD */ && + TEST_FLAG(ONSOLDERFLAG, pt.other)) || (pt.other->PinN != 0 /* non-SMD */ && + TEST_FLAG(ONSOLDERFLAG, pt.element))) + return createPerturbation(selected, T); + break; + } + default: + assert(0); + } + return pt; +} + +void doPerturb(PerturbationType * pt, bool undo) +{ + Coord bbcx, bbcy; + /* compute center of element bounding box */ + bbcx = (pt->element->VBox.X1 + pt->element->VBox.X2) / 2; + bbcy = (pt->element->VBox.Y1 + pt->element->VBox.Y2) / 2; + /* do exchange, shift or flip/rotate */ + switch (pt->which) { + case SHIFT: + { + Coord DX = pt->DX, DY = pt->DY; + if (undo) { + DX = -DX; + DY = -DY; + } + MoveElementLowLevel(PCB->Data, pt->element, DX, DY); + return; + } + case ROTATE: + { + unsigned b = pt->rotate; + if (undo) + b = (4 - b) & 3; + /* 0 - flip; 1-3, rotate. */ + if (b) + RotateElementLowLevel(PCB->Data, pt->element, bbcx, bbcy, b); + else { + Coord y = pt->element->VBox.Y1; + MirrorElementCoordinates(PCB->Data, pt->element, 0); + /* mirroring moves the element. move it back. */ + MoveElementLowLevel(PCB->Data, pt->element, 0, y - pt->element->VBox.Y1); + } + return; + } + case EXCHANGE: + { + /* first exchange positions */ + Coord x1 = pt->element->VBox.X1; + Coord y1 = pt->element->VBox.Y1; + Coord x2 = pt->other->BoundingBox.X1; + Coord y2 = pt->other->BoundingBox.Y1; + MoveElementLowLevel(PCB->Data, pt->element, x2 - x1, y2 - y1); + MoveElementLowLevel(PCB->Data, pt->other, x1 - x2, y1 - y2); + /* then flip both elements if they are on opposite sides */ + if (TEST_FLAG(ONSOLDERFLAG, pt->element) != TEST_FLAG(ONSOLDERFLAG, pt->other)) { + PerturbationType mypt; + mypt.element = pt->element; + mypt.which = ROTATE; + mypt.rotate = 0; /* flip */ + doPerturb(&mypt, undo); + mypt.element = pt->other; + doPerturb(&mypt, undo); + } + /* done */ + return; + } + default: + assert(0); + } +} + +/* --------------------------------------------------------------------------- + * Auto-place selected components. + */ +bool AutoPlaceSelected(void) +{ + NetListTypePtr Nets; + PointerListType Selected = { 0, 0, NULL }; + PerturbationType pt; + double C0, T0; + bool changed = false; + + /* (initial netlist processing copied from AddAllRats) */ + /* the netlist library has the text form + * ProcNetlist fills in the Netlist + * structure the way the final routing + * is supposed to look + */ + Nets = ProcNetlist(&(PCB->NetlistLib[NETLIST_EDITED])); + if (!Nets) { + Message(_("Can't add rat lines because no netlist is loaded.\n")); + goto done; + } + + Selected = collectSelectedElements(); + if (Selected.PtrN == 0) { + Message(_("No elements selected to autoplace.\n")); + goto done; + } + + /* simulated annealing */ + { /* compute T0 by doing a random series of moves. */ + const int TRIALS = 10; + const double Tx = MIL_TO_COORD(300), P = 0.95; + double Cs = 0.0; + int i; + C0 = ComputeCost(Nets, Tx, Tx); + for (i = 0; i < TRIALS; i++) { + pt = createPerturbation(&Selected, INCH_TO_COORD(1)); + doPerturb(&pt, false); + Cs += fabs(ComputeCost(Nets, Tx, Tx) - C0); + doPerturb(&pt, true); + } + T0 = -(Cs / TRIALS) / log(P); + printf("Initial T: %f\n", T0); + } + /* now anneal in earnest */ + { + double T = T0; + long steps = 0; + int good_moves = 0, moves = 0; + const int good_move_cutoff = CostParameter.m * Selected.PtrN; + const int move_cutoff = 2 * good_move_cutoff; + printf("Starting cost is %.0f\n", ComputeCost(Nets, T0, 5)); + C0 = ComputeCost(Nets, T0, T); + while (1) { + double Cprime; + pt = createPerturbation(&Selected, T); + doPerturb(&pt, false); + Cprime = ComputeCost(Nets, T0, T); + if (Cprime < C0) { /* good move! */ + C0 = Cprime; + good_moves++; + steps++; + } + else if ((random() / (double) RAND_MAX) < exp(MIN(MAX(-20, (C0 - Cprime) / T), 20))) { + /* not good but keep it anyway */ + C0 = Cprime; + steps++; + } + else + doPerturb(&pt, true); /* undo last change */ + moves++; + /* are we at the end of a stage? */ + if (good_moves >= good_move_cutoff || moves >= move_cutoff) { + printf("END OF STAGE: COST %.0f\t" "GOOD_MOVES %d\tMOVES %d\t" "T: %.1f\n", C0, good_moves, moves, T); + /* is this the end? */ + if (T < 5 || good_moves < moves / CostParameter.good_ratio) + break; + /* nope, adjust T and continue */ + moves = good_moves = 0; + T *= CostParameter.gamma; + /* cost is T dependent, so recompute */ + C0 = ComputeCost(Nets, T0, T); + } + } + changed = (steps > 0); + } +done: + if (changed) { + DeleteRats(false); + AddAllRats(false, NULL); + Redraw(); + } + FreePointerListMemory(&Selected); + return (changed); +} Index: trunk/src_plugins/autoplace/autoplace.h =================================================================== --- trunk/src_plugins/autoplace/autoplace.h (nonexistent) +++ trunk/src_plugins/autoplace/autoplace.h (revision 1047) @@ -0,0 +1,45 @@ +/* $Id$ */ + +/* + * COPYRIGHT + * + * PCB, interactive printed circuit board design + * Copyright (C) 1994,1995,1996 Thomas Nau + * Copyright (C) 1998,1999,2000,2001 harry eaton + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * Contact addresses for paper mail and Email: + * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA + * haceaton@aplcomm.jhuapl.edu + * + */ + +/* this file, autoplace.h, was written and is + * Copyright (c) 2001 C. Scott Ananian. + * + */ + +/* prototypes for autoplace routines + */ + +#ifndef PCB_AUTOPLACE_H +#define PCB_AUTOPLACE_H + +#include "global.h" + +bool AutoPlaceSelected(void); + +#endif