src/slotifier.c

   1 /*
   2  * Utility to convert overlapping Excellon drill hits into drill slots.
   3  * Copyright © 2018, 2021 Nick Bowler
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <config.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <stddef.h>
  23 #include <string.h>
  24 #include <locale.h>
  25 #include <stdint.h>
  26 #include <assert.h>
  27 #include <getopt.h>
  28 #include <gettext.h>
  29 #include <CNearTree.h>
  30 #include <gerbv.h>
  31 #include <striconv.h>
  32 #include <localcharset.h>
  33
  34 #if !ENABLE_NLS
  35 #  undef ENABLE_NLS
  36 #  define ENABLE_NLS 0
  37 #endif
  38
  39 #define _(x) (gettext(x))
  40
  41 static unsigned verbose;
  42
  43 static const char *progname = "slotifier";
  44 static const char sopts[] = "o:vVH";
  45 static const struct option lopts[] = {
  46         { "output",  1, NULL, 'o' },
  47         { "verbose", 0, NULL, 'v' },
  48         { "version", 0, NULL, 'V' },
  49         { "help",    0, NULL, 'H' },
  50         { 0 }
  51 };
  52
  53 static void print_version(void)
  54 {
  55         const char *copysign = "(C)";
  56         void *convsign = NULL;
  57
  58         puts(PACKAGE_STRING);
  59
  60         if (ENABLE_NLS) {
  61                 convsign = str_iconv("\xc2\xa9", "UTF-8", locale_charset());
  62                 if (convsign)
  63                         copysign = convsign;
  64         }
  65
  66         printf("Copyright %s 2021 Nick Bowler.\n", copysign);
  67         puts("License GPLv3+: GNU GPL version 3 or any later version.");
  68         puts("This is free software: you are free to change and redistribute it.");
  69         puts("There is NO WARRANTY, to the extent permitted by law.");
  70
  71         free(convsign);
  72 }
  73
  74 static void print_usage(FILE *f)
  75 {
  76         fprintf(f, _("Usage: %s [options] [-o filename] filename\n"), progname);
  77         if (f != stdout)
  78                 fprintf(f, _("Try %s --help for more information.\n"),
  79                            progname);
  80 }
  81
  82 static void print_help(void)
  83 {
  84         const struct option *opt;
  85         print_usage(stdout);
  86
  87         puts(_("This is \"slotifier\": a tool to convert overlapping drill hits in Excellon\n"
  88                "drill files to G85 drill slots."));
  89         putchar('\n');
  90
  91         puts(_("Options:"));
  92         for (opt = lopts; opt->val; opt++) {
  93                 const char *line, *text = "ARG";
  94                 int w = 0;
  95
  96                 if (opt->has_arg) {
  97                         switch (opt->val) {
  98                         case 'o': text = _("FILE");
  99                         }
 100
 101                         w += printf(_("  -%c, --%s=%s"),
 102                                     opt->val, opt->name, text);
 103                 } else {
 104                         w += printf(_("  -%c, --%s"), opt->val, opt->name);
 105                 }
 106
 107                 if (w > 18) {
 108                         putchar('\n');
 109                         w = 0;
 110                 }
 111
 112                 switch (opt->val) {
 113                 case 'o':
 114                         text = _("Output to FILE, instead of standard output.");
 115                         break;
 116                 case 'v':
 117                         text = _("Increase verbosity (can be specified more than once).");
 118                         break;
 119                 case 'V':
 120                         text = _("Print a version message and then exit.");
 121                         break;
 122                 case 'H':
 123                         text = _("Print this message and then exit.");
 124                         break;
 125                 default:
 126                         if (w)
 127                                 putchar('\n');
 128                         continue;
 129                 }
 130
 131                 for (line = text; line[0];) {
 132                         const char *nl = strchr(line, '\n');
 133
 134                         if (!nl) {
 135                                 printf("%*s%s\n", 20-w, "", line);
 136                                 break;
 137                         }
 138
 139                         printf("%*s%.*s\n", 20-w, "", (int)(nl-line), line);
 140                         line = nl+1;
 141                 }
 142         }
 143         putchar('\n');
 144
 145         puts(_("For more information, see the slotifier(1) man page."));
 146         putchar('\n');
 147
 148         printf(_("Report bugs to <%s>."), PACKAGE_BUGREPORT);
 149         putchar('\n');
 150 }
 151
 152 static void init_i18n(void)
 153 {
 154         setlocale(LC_ALL, "");
 155         bindtextdomain(PACKAGE, LOCALEDIR);
 156         textdomain(PACKAGE);
 157 }
 158
 159 static CNearTreeHandle build_search_tree(gerbv_image_t *drill)
 160 {
 161         CNearTreeHandle t;
 162         gerbv_net_t *x;
 163
 164         if (CNearTreeCreate(&t, 2, CNEARTREE_TYPE_DOUBLE|CNEARTREE_NORM_L2))
 165                 return 0;
 166
 167         /* Build a search tree from all the holes. */
 168         for (x = drill->netlist; x; x = x->next) {
 169                 double xy[2] = { x->start_x, x->start_y };
 170
 171                 assert(x->aperture >= 0 && x->aperture < APERTURE_MAX);
 172
 173                 /* Skip things that aren't drill hits */
 174                 if (!drill->aperture[x->aperture])
 175                         continue;
 176
 177                 /* Holes are marked as "flashing"; otherwise it's an existing
 178                  * slot; skip it. */
 179                 if (x->aperture_state != GERBV_APERTURE_STATE_FLASH)
 180                         continue;
 181
 182                 if (CNearTreeInsert(t, xy, x)) {
 183                         CNearTreeFree(&t);
 184                         return 0;
 185                 }
 186         }
 187
 188         if (CNearTreeCompleteDelayedInsert(t)) {
 189                 CNearTreeFree(&t);
 190                 return 0;
 191         }
 192
 193         return t;
 194 }
 195
 196 static gerbv_aperture_type_t tool_type(gerbv_image_t *drill, int aperture)
 197 {
 198         gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
 199
 200         return tool->type;
 201 }
 202
 203 static double tool_radius(gerbv_image_t *drill, int aperture)
 204 {
 205         gerbv_aperture_t *tool = drill->aperture[abs(aperture)];
 206
 207         /* Half a mil slop to decisively include points on boundary. */
 208         return tool->parameter[0] / 2.0 + 0.0005;
 209 }
 210
 211 static int holes_overlap(gerbv_image_t *drill, gerbv_net_t *a, gerbv_net_t *b)
 212 {
 213         double d = hypot(a->start_x - b->start_x, a->start_y - b->start_y);
 214
 215         return tool_radius(drill, a->aperture) >= d
 216             || tool_radius(drill, b->aperture) >= d;
 217 }
 218
 219 static int combine_holes(gerbv_image_t *drill, gerbv_net_t *hole,
 220                          CNearTreeHandle t)
 221 {
 222         CVectorHandle group, tmp;
 223         int biggest_tool, ret = -1;
 224         double biggest_r;
 225         size_t i, j;
 226
 227         /*
 228          * Since we consider holes in order of decreasing size, the initial hole
 229          * considered is by definition the biggest one we will find in a group.
 230          */
 231         biggest_r = tool_radius(drill, (biggest_tool = hole->aperture));
 232
 233         if (CVectorCreate(&group, sizeof (gerbv_net_t *), 10)) {
 234                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 235                 return -1;
 236         }
 237
 238         if (CVectorCreate(&tmp, sizeof (void *), 10)) {
 239                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 240                 CVectorFree(&group);
 241                 return -1;
 242         }
 243
 244         /*
 245          * Breadth-first nearest neighbour search of holes.  We negate the
 246          * aperture to indicate which holes have been previously visited.
 247          */
 248         CVectorAddElement(group, &hole);
 249         hole->aperture = -hole->aperture;
 250
 251         for (i = 0; i < CVectorSize(group); i++) {
 252                 double xy[2];
 253
 254                 CVectorGetElement(group, &hole, i);
 255
 256                 assert(tool_type(drill, hole->aperture) == GERBV_APTYPE_CIRCLE);
 257                 assert(tool_radius(drill, hole->aperture) <= biggest_r);
 258
 259                 xy[0] = hole->start_x; xy[1] = hole->start_y;
 260                 if (CNearTreeFindInSphere(t, biggest_r, 0, tmp, xy, 1) != 0) {
 261                         /* We should always should find at least one hole! */
 262                         fprintf(stderr, _("%s: fatal error searching holes\n"),
 263                                         progname);
 264                         goto err;
 265                 }
 266
 267                 for (j = 0; j < CVectorSize(tmp); j++) {
 268                         /* I don't know why, but CNearTree returns a list
 269                          * of pointers to its internal copies of pointers
 270                          * to the objects in the tree.  So we need this
 271                          * double indirection to get the actual hole. */
 272                         gerbv_net_t *newhole;
 273                         void *p;
 274
 275                         CVectorGetElement(tmp, &p, j);
 276                         newhole = *(void **)p;
 277
 278                         if (newhole->aperture < 0)
 279                                 continue; /* already visited */
 280
 281                         if (holes_overlap(drill, hole, newhole)) {
 282                                 CVectorAddElement(group, &newhole);
 283                                 newhole->aperture = -newhole->aperture;
 284                         }
 285                 }
 286         }
 287
 288         /* Compare each pair of matched points to find the longest slot. */
 289         if (CVectorSize(group) > 1) {
 290                 int biggest_slot = 0;
 291                 double bestlen = 0;
 292
 293                 for (i = 0; i < CVectorSize(group) - 1; i++) {
 294                         CVectorGetElement(group, &hole, i);
 295                         for (j = i+1; j < CVectorSize(group); j++) {
 296                                 gerbv_net_t *h2;
 297                                 double newlen;
 298
 299                                 CVectorGetElement(group, &h2, j);
 300                                 newlen = hypot(hole->start_x - h2->start_x,
 301                                                hole->start_y - h2->start_y);
 302
 303                                 if (newlen > bestlen) {
 304                                         hole->stop_x = h2->start_x;
 305                                         hole->stop_y = h2->stop_y;
 306                                         bestlen = newlen;
 307                                         biggest_slot = i;
 308                                 }
 309                         }
 310                 }
 311
 312                 CVectorGetElement(group, &hole, biggest_slot);
 313                 hole->aperture = biggest_tool;
 314                 hole->aperture_state = GERBV_APERTURE_STATE_ON;
 315
 316                 if (verbose) {
 317                         const char *fmt = ngettext(
 318                                 "%s: merged %zu hole into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
 319                                 "%s: merged %zu holes into slot (%.4f,%.4f)-(%.4f,%.4f)\n",
 320                                 CVectorSize(group));
 321
 322                         fprintf(stderr, fmt, progname, CVectorSize(group),
 323                                              hole->start_x, hole->start_y,
 324                                              hole->stop_x, hole->stop_y);
 325                 }
 326         } else {
 327                 /* The only hole we found was our original one, restore
 328                  * initial state. */
 329                 CVectorGetElement(group, &hole, 0);
 330
 331                 assert(hole->aperture < 0);
 332                 hole->aperture = -hole->aperture;
 333
 334                 if (verbose > 1) {
 335                         fprintf(stderr, _("%s: hole at (%.4f,%.4f) not merged\n"),
 336                                         progname, hole->start_x, hole->start_y);
 337                 }
 338         }
 339
 340         ret = 0;
 341 err:
 342         CVectorFree(&tmp);
 343         CVectorFree(&group);
 344         return ret;
 345 }
 346
 347 /*
 348  * Order two holes by hole diameter.
 349  */
 350 static gerbv_image_t *hsc_drill_data;
 351 static int hole_size_cmp(const void *a_, const void *b_)
 352 {
 353         gerbv_net_t * const *a = a_, * const *b = b_;
 354         gerbv_aperture_t *ta, *tb;
 355
 356         ta = hsc_drill_data->aperture[abs(a[0]->aperture)];
 357         assert(ta->type == GERBV_APTYPE_CIRCLE);
 358
 359         tb = hsc_drill_data->aperture[abs(b[0]->aperture)];
 360         assert(tb->type == GERBV_APTYPE_CIRCLE);
 361
 362         if (ta->parameter[0] > tb->parameter[0])
 363                 return -1;
 364         if (ta->parameter[0] < tb->parameter[0])
 365                 return 1;
 366         return 0;
 367 }
 368
 369 static void sort_holes_by_size(gerbv_image_t *drill, CVectorHandle work)
 370 {
 371         hsc_drill_data = drill;
 372         qsort(work->array, work->size, work->elementsize, hole_size_cmp);
 373 }
 374
 375 static int slotify(gerbv_image_t *drill)
 376 {
 377         CVectorHandle holes, work;
 378         CNearTreeHandle t;
 379         int ret = 0;
 380         size_t i;
 381
 382         t = build_search_tree(drill);
 383         if (!t) {
 384                 fprintf(stderr, _("%s: failed to build search tree\n"),
 385                                 progname);
 386                 return -1;
 387         }
 388
 389         CNearTreeObjects(t, &holes);
 390         if (!holes)
 391                 goto err_free_tree;
 392
 393         if (CVectorCreate(&work, sizeof (gerbv_net_t *), CVectorSize(holes))) {
 394                 fprintf(stderr, _("%s: failed to allocate memory\n"), progname);
 395                 goto err_free_tree;
 396         }
 397
 398         memcpy(work->array, holes->array, holes->size * holes->elementsize);
 399         work->size = holes->size;
 400         sort_holes_by_size(drill, work);
 401
 402         for (i = 0; i < CVectorSize(work); i++) {
 403                 gerbv_net_t *hole;
 404
 405                 CVectorGetElement(work, &hole, i);
 406                 /* Skip holes we've already looked at */
 407                 if (hole->aperture < 0)
 408                         continue;
 409                 if (hole->aperture_state == GERBV_APERTURE_STATE_ON)
 410                         continue;
 411
 412                 if (verbose > 1) {
 413                         fprintf(stderr, _("%s: checking hole at (%.4f,%.4f) for overlaps\n"),
 414                                         progname, hole->start_x, hole->start_y);
 415                 }
 416
 417                 if (combine_holes(drill, hole, t) < 0) {
 418                         ret = -1;
 419                         break;
 420                 }
 421         }
 422
 423         /* Clean out any holes we don't need anymore */
 424         for (i = 0; i < CVectorSize(holes); i++) {
 425                 gerbv_net_t *hole;
 426
 427                 CVectorGetElement(holes, &hole, i);
 428                 if (hole->aperture < 0)
 429                         gerbv_image_delete_net(hole);
 430         }
 431
 432         CVectorFree(&work);
 433 err_free_tree:
 434         CNearTreeFree(&t);
 435         return ret;
 436 }
 437
 438 int main(int argc, char **argv)
 439 {
 440         const char *outfile = "/dev/stdout";
 441         gerbv_project_t *gp;
 442         gerbv_image_t *drill;
 443         int opt, ret = 0;
 444
 445         if (argc > 0)
 446                 progname = argv[0];
 447
 448         init_i18n();
 449
 450         while ((opt = getopt_long(argc, argv, sopts, lopts, NULL)) != -1) {
 451                 switch (opt) {
 452                 case 'o':
 453                         outfile = optarg;
 454                         break;
 455                 case 'v':
 456                         verbose++;
 457                         break;
 458                 case 'V':
 459                         print_version();
 460                         return EXIT_SUCCESS;
 461                 case 'H':
 462                         print_help();
 463                         return EXIT_SUCCESS;
 464                 default:
 465                         print_usage(stderr);
 466                         return EXIT_FAILURE;
 467                 }
 468         }
 469
 470         if (!argv[optind]) {
 471                 fprintf(stderr, _("%s: error: must specify a filename\n"),
 472                                 progname);
 473                 print_usage(stderr);
 474                 return EXIT_FAILURE;
 475         }
 476
 477         if (optind + 1 < argc) {
 478                 fprintf(stderr, _("%s: error: excess command-line arguments\n"),
 479                                 progname);
 480                 print_usage(stderr);
 481                 return EXIT_FAILURE;
 482         }
 483
 484         gp = gerbv_create_project();
 485         if (!gp)
 486                 return EXIT_FAILURE;
 487
 488         gerbv_open_layer_from_filename(gp, argv[optind]);
 489         if (!gp->file[0]) {
 490                 ret = EXIT_FAILURE;
 491                 goto out;
 492         }
 493
 494         drill = gp->file[0]->image;
 495         if (drill->layertype != GERBV_LAYERTYPE_DRILL) {
 496                 fprintf(stderr, _("%s: %s: error: not a drill file\n"),
 497                                 progname, argv[optind]);
 498                 ret = EXIT_FAILURE;
 499                 goto out;
 500         }
 501
 502         if (slotify(drill) != 0) {
 503                 ret = EXIT_FAILURE;
 504                 goto out;
 505         }
 506
 507         if (!gerbv_export_drill_file_from_image(outfile, drill, NULL))
 508                 ret = EXIT_FAILURE;
 509 out:
 510         gerbv_destroy_project(gp);
 511         return ret;
 512 }