src/slotifier.c

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