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