test/worm.c

   1 /****************************************************************************
   2  * Copyright 2018-2020,2022 Thomas E. Dickey                                *
   3  * Copyright 1998-2016,2017 Free Software Foundation, Inc.                  *
   4  *                                                                          *
   5  * Permission is hereby granted, free of charge, to any person obtaining a  *
   6  * copy of this software and associated documentation files (the            *
   7  * "Software"), to deal in the Software without restriction, including      *
   8  * without limitation the rights to use, copy, modify, merge, publish,      *
   9  * distribute, distribute with modifications, sublicense, and/or sell       *
  10  * copies of the Software, and to permit persons to whom the Software is    *
  11  * furnished to do so, subject to the following conditions:                 *
  12  *                                                                          *
  13  * The above copyright notice and this permission notice shall be included  *
  14  * in all copies or substantial portions of the Software.                   *
  15  *                                                                          *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
  17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
  19  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
  20  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
  21  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
  22  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
  23  *                                                                          *
  24  * Except as contained in this notice, the name(s) of the above copyright   *
  25  * holders shall not be used in advertising or otherwise to promote the     *
  26  * sale, use or other dealings in this Software without prior written       *
  27  * authorization.                                                           *
  28  ****************************************************************************/
  29 /*
  30
  31          @@@        @@@    @@@@@@@@@@     @@@@@@@@@@@    @@@@@@@@@@@@
  32          @@@        @@@   @@@@@@@@@@@@    @@@@@@@@@@@@   @@@@@@@@@@@@@
  33          @@@        @@@  @@@@      @@@@   @@@@           @@@@ @@@  @@@@
  34          @@@   @@   @@@  @@@        @@@   @@@            @@@  @@@   @@@
  35          @@@  @@@@  @@@  @@@        @@@   @@@            @@@  @@@   @@@
  36          @@@@ @@@@ @@@@  @@@        @@@   @@@            @@@  @@@   @@@
  37           @@@@@@@@@@@@   @@@@      @@@@   @@@            @@@  @@@   @@@
  38            @@@@  @@@@     @@@@@@@@@@@@    @@@            @@@  @@@   @@@
  39             @@    @@       @@@@@@@@@@     @@@            @@@  @@@   @@@
  40
  41                                  Eric P. Scott
  42                           Caltech High Energy Physics
  43                                  October, 1980
  44
  45                 Hacks to turn this into a test frame for cursor movement:
  46                         Eric S. Raymond <esr@snark.thyrsus.com>
  47                                 January, 1995
  48
  49                 July 1995 (esr): worms is now in living color! :-)
  50
  51   This program makes a good torture-test for the ncurses cursor-optimization
  52   code.  You can use -T to set the worm move interval over which movement
  53   traces will be dumped.  The program stops and waits for one character of
  54   input at the beginning and end of the interval.
  55
  56   $Id: worm.c,v 1.85 2022/08/13 13:28:01 tom Exp $
  57 */
  58
  59 #include <test.priv.h>
  60
  61 #ifndef NCURSES_VERSION
  62 #undef TRACE
  63 #endif
  64
  65 #ifdef USE_PTHREADS
  66 #include <pthread.h>
  67 #endif
  68
  69 WANT_USE_WINDOW();
  70
  71 #define MAX_WORMS       40
  72 #define MAX_LENGTH      1024
  73
  74 static chtype flavor[] =
  75 {
  76     'O', '*', '#', '$', '%', '0', '@',
  77 };
  78 static const int xinc[] =
  79 {
  80     1, 1, 1, 0, -1, -1, -1, 0
  81 }, yinc[] =
  82 {
  83     -1, 0, 1, 1, 1, 0, -1, -1
  84 };
  85
  86 typedef struct worm {
  87     int orientation;
  88     int head;
  89     int *xpos;
  90     int *ypos;
  91     chtype attrs;
  92 #ifdef USE_PTHREADS
  93     pthread_t thread;
  94 #endif
  95 } WORM;
  96
  97 static unsigned long sequence = 0;
  98 static bool quitting = FALSE;
  99
 100 static WORM worm[MAX_WORMS];
 101 static int max_refs;
 102 static int **refs;
 103 static int last_x, last_y;
 104
 105 static const char *field;
 106 static int length = 16, number = 3;
 107 static chtype trail = ' ';
 108
 109 static unsigned pending;
 110
 111 #ifdef USE_PTHREADS
 112 #define Locked(statement) { \
 113         pthread_mutex_lock(&pending_mutex); \
 114         statement; \
 115         pthread_mutex_unlock(&pending_mutex); \
 116     }
 117 pthread_mutex_t pending_mutex;
 118 #else
 119 #define Locked(statement) statement
 120 #endif
 121
 122 #ifdef TRACE
 123 static int generation, trace_start, trace_end;
 124 #endif /* TRACE */
 125 /* *INDENT-OFF* */
 126 static const struct options {
 127     int nopts;
 128     int opts[3];
 129 } normal[8]={
 130     { 3, { 7, 0, 1 } },
 131     { 3, { 0, 1, 2 } },
 132     { 3, { 1, 2, 3 } },
 133     { 3, { 2, 3, 4 } },
 134     { 3, { 3, 4, 5 } },
 135     { 3, { 4, 5, 6 } },
 136     { 3, { 5, 6, 7 } },
 137     { 3, { 6, 7, 0 } }
 138 }, upper[8]={
 139     { 1, { 1, 0, 0 } },
 140     { 2, { 1, 2, 0 } },
 141     { 0, { 0, 0, 0 } },
 142     { 0, { 0, 0, 0 } },
 143     { 0, { 0, 0, 0 } },
 144     { 2, { 4, 5, 0 } },
 145     { 1, { 5, 0, 0 } },
 146     { 2, { 1, 5, 0 } }
 147 }, left[8]={
 148     { 0, { 0, 0, 0 } },
 149     { 0, { 0, 0, 0 } },
 150     { 0, { 0, 0, 0 } },
 151     { 2, { 2, 3, 0 } },
 152     { 1, { 3, 0, 0 } },
 153     { 2, { 3, 7, 0 } },
 154     { 1, { 7, 0, 0 } },
 155     { 2, { 7, 0, 0 } }
 156 }, right[8]={
 157     { 1, { 7, 0, 0 } },
 158     { 2, { 3, 7, 0 } },
 159     { 1, { 3, 0, 0 } },
 160     { 2, { 3, 4, 0 } },
 161     { 0, { 0, 0, 0 } },
 162     { 0, { 0, 0, 0 } },
 163     { 0, { 0, 0, 0 } },
 164     { 2, { 6, 7, 0 } }
 165 }, lower[8]={
 166     { 0, { 0, 0, 0 } },
 167     { 2, { 0, 1, 0 } },
 168     { 1, { 1, 0, 0 } },
 169     { 2, { 1, 5, 0 } },
 170     { 1, { 5, 0, 0 } },
 171     { 2, { 5, 6, 0 } },
 172     { 0, { 0, 0, 0 } },
 173     { 0, { 0, 0, 0 } }
 174 }, upleft[8]={
 175     { 0, { 0, 0, 0 } },
 176     { 0, { 0, 0, 0 } },
 177     { 0, { 0, 0, 0 } },
 178     { 0, { 0, 0, 0 } },
 179     { 0, { 0, 0, 0 } },
 180     { 1, { 3, 0, 0 } },
 181     { 2, { 1, 3, 0 } },
 182     { 1, { 1, 0, 0 } }
 183 }, upright[8]={
 184     { 2, { 3, 5, 0 } },
 185     { 1, { 3, 0, 0 } },
 186     { 0, { 0, 0, 0 } },
 187     { 0, { 0, 0, 0 } },
 188     { 0, { 0, 0, 0 } },
 189     { 0, { 0, 0, 0 } },
 190     { 0, { 0, 0, 0 } },
 191     { 1, { 5, 0, 0 } }
 192 }, lowleft[8]={
 193     { 3, { 7, 0, 1 } },
 194     { 0, { 0, 0, 0 } },
 195     { 0, { 0, 0, 0 } },
 196     { 1, { 1, 0, 0 } },
 197     { 2, { 1, 7, 0 } },
 198     { 1, { 7, 0, 0 } },
 199     { 0, { 0, 0, 0 } },
 200     { 0, { 0, 0, 0 } }
 201 }, lowright[8]={
 202     { 0, { 0, 0, 0 } },
 203     { 1, { 7, 0, 0 } },
 204     { 2, { 5, 7, 0 } },
 205     { 1, { 5, 0, 0 } },
 206     { 0, { 0, 0, 0 } },
 207     { 0, { 0, 0, 0 } },
 208     { 0, { 0, 0, 0 } },
 209     { 0, { 0, 0, 0 } }
 210 };
 211 /* *INDENT-ON* */
 212
 213 #if HAVE_USE_WINDOW
 214 static int
 215 safe_wgetch(WINDOW *w, void *data GCC_UNUSED)
 216 {
 217     return wgetch(w);
 218 }
 219 static int
 220 safe_wrefresh(WINDOW *w, void *data GCC_UNUSED)
 221 {
 222     return wrefresh(w);
 223 }
 224 #endif
 225
 226 #ifdef KEY_RESIZE
 227 static void
 228 failed(const char *s)
 229 {
 230     perror(s);
 231     stop_curses();
 232     ExitProgram(EXIT_FAILURE);
 233 }
 234 #endif
 235
 236 static void
 237 cleanup(void)
 238 {
 239     USING_WINDOW1(stdscr, wrefresh, safe_wrefresh);
 240     stop_curses();
 241 }
 242
 243 static void
 244 onsig(int sig GCC_UNUSED)
 245 {
 246     cleanup();
 247     ExitProgram(EXIT_FAILURE);
 248 }
 249
 250 static double
 251 ranf(void)
 252 {
 253     long r = (rand() & 077777);
 254     return ((double) r / 32768.);
 255 }
 256
 257 static int
 258 draw_worm(WINDOW *win, void *data)
 259 {
 260     WORM *w = (WORM *) data;
 261     const struct options *op;
 262     unsigned mask = (unsigned) (~(1 << (w - worm)));
 263     chtype attrs;
 264
 265     int x;
 266     int y;
 267     int h;
 268
 269     bool done = FALSE;
 270     bool is_pending;
 271
 272     Locked(is_pending = ((mask & pending) != 0));
 273
 274     attrs = w->attrs | (is_pending ? A_REVERSE : 0);
 275
 276     if ((x = w->xpos[h = w->head]) < 0) {
 277         wmove(win, y = w->ypos[h] = last_y, x = w->xpos[h] = 0);
 278         waddch(win, attrs);
 279         refs[y][x]++;
 280     } else {
 281         y = w->ypos[h];
 282     }
 283
 284     if (x > last_x)
 285         x = last_x;
 286     if (y > last_y)
 287         y = last_y;
 288
 289     if (++h == length)
 290         h = 0;
 291
 292     if (w->xpos[w->head = h] >= 0) {
 293         int x1, y1;
 294         x1 = w->xpos[h];
 295         y1 = w->ypos[h];
 296         if (y1 < LINES
 297             && x1 < COLS
 298             && --refs[y1][x1] == 0) {
 299             wmove(win, y1, x1);
 300             waddch(win, trail);
 301         }
 302     }
 303
 304     op = &(x == 0
 305            ? (y == 0
 306               ? upleft
 307               : (y == last_y
 308                  ? lowleft
 309                  : left))
 310            : (x == last_x
 311               ? (y == 0
 312                  ? upright
 313                  : (y == last_y
 314                     ? lowright
 315                     : right))
 316               : (y == 0
 317                  ? upper
 318                  : (y == last_y
 319                     ? lower
 320                     : normal))))[w->orientation];
 321
 322     switch (op->nopts) {
 323     case 0:
 324         done = TRUE;
 325         Trace(("done - draw_worm"));
 326         break;
 327     case 1:
 328         w->orientation = op->opts[0];
 329         break;
 330     default:
 331         w->orientation = op->opts[(int) (ranf() * (double) op->nopts)];
 332         break;
 333     }
 334
 335     if (!done) {
 336         x += xinc[w->orientation];
 337         y += yinc[w->orientation];
 338         wmove(win, y, x);
 339
 340         if (y < 0)
 341             y = 0;
 342         waddch(win, attrs);
 343
 344         w->ypos[h] = y;
 345         w->xpos[h] = x;
 346         refs[y][x]++;
 347     }
 348
 349     return done;
 350 }
 351
 352 #ifdef USE_PTHREADS
 353 static bool
 354 quit_worm(int bitnum)
 355 {
 356     Locked(pending = (pending | (unsigned) (1 << bitnum)));
 357
 358     napms(10);                  /* let the other thread(s) have a chance */
 359
 360     Locked(pending = (pending & (unsigned) ~(1 << bitnum)));
 361
 362     return quitting;
 363 }
 364
 365 static void *
 366 start_worm(void *arg)
 367 {
 368     unsigned long compare = 0;
 369     Trace(("start_worm"));
 370     while (!quit_worm((int) (((struct worm *) arg) - worm))) {
 371         while (compare < sequence) {
 372             ++compare;
 373             USING_WINDOW2(stdscr, draw_worm, arg);
 374         }
 375     }
 376     Trace(("...start_worm (done)"));
 377     return NULL;
 378 }
 379 #endif
 380
 381 static bool
 382 draw_all_worms(void)
 383 {
 384     bool done = FALSE;
 385     int n;
 386     struct worm *w;
 387
 388 #ifdef USE_PTHREADS
 389     static bool first = TRUE;
 390     if (first) {
 391         first = FALSE;
 392         for (n = 0, w = &worm[0]; n < number; n++, w++) {
 393             (void) pthread_create(&(w->thread), NULL, start_worm, w);
 394         }
 395     }
 396 #else
 397     for (n = 0, w = &worm[0]; n < number; n++, w++) {
 398         if (USING_WINDOW2(stdscr, draw_worm, w))
 399             done = TRUE;
 400     }
 401 #endif
 402     return done;
 403 }
 404
 405 static int
 406 get_input(void)
 407 {
 408     int ch;
 409     ch = USING_WINDOW1(stdscr, wgetch, safe_wgetch);
 410     return ch;
 411 }
 412
 413 #ifdef KEY_RESIZE
 414 static int
 415 update_refs(WINDOW *win, void *data)
 416 {
 417     int x, y;
 418
 419     (void) win;
 420     (void) data;
 421     if (last_x != COLS - 1) {
 422         for (y = 0; y <= last_y; y++) {
 423             refs[y] = typeRealloc(int, (size_t) COLS, refs[y]);
 424             if (!refs[y])
 425                 failed("update_refs");
 426             for (x = last_x + 1; x < COLS; x++)
 427                 refs[y][x] = 0;
 428         }
 429         last_x = COLS - 1;
 430     }
 431     if (last_y != LINES - 1) {
 432         for (y = LINES; y <= last_y; y++)
 433             free(refs[y]);
 434         max_refs = LINES;
 435         refs = typeRealloc(int *, (size_t) LINES, refs);
 436         for (y = last_y + 1; y < LINES; y++) {
 437             refs[y] = typeMalloc(int, (size_t) COLS);
 438             if (!refs[y])
 439                 failed("update_refs");
 440             for (x = 0; x < COLS; x++)
 441                 refs[y][x] = 0;
 442         }
 443         last_y = LINES - 1;
 444     }
 445     return OK;
 446 }
 447 #endif
 448
 449 static void
 450 usage(void)
 451 {
 452     static const char *msg[] =
 453     {
 454         "Usage: worm [options]"
 455         ,""
 456         ,"Options:"
 457 #if HAVE_USE_DEFAULT_COLORS
 458         ," -d       invoke use_default_colors"
 459 #endif
 460         ," -f       fill screen with copies of \"WORM\" at start"
 461         ," -l <n>   set length of worms"
 462         ," -n <n>   set number of worms"
 463         ," -t       leave trail of \".\""
 464 #ifdef TRACE
 465         ," -T <start>,<end> set trace interval"
 466         ," -N       suppress cursor-movement optimization"
 467 #endif
 468     };
 469     size_t n;
 470
 471     for (n = 0; n < SIZEOF(msg); n++)
 472         fprintf(stderr, "%s\n", msg[n]);
 473
 474     ExitProgram(EXIT_FAILURE);
 475 }
 476
 477 int
 478 main(int argc, char *argv[])
 479 {
 480     int ch;
 481     int x, y;
 482     int n;
 483     struct worm *w;
 484     int *ip;
 485     bool done = FALSE;
 486 #if HAVE_USE_DEFAULT_COLORS
 487     bool opt_d = FALSE;
 488 #endif
 489
 490     setlocale(LC_ALL, "");
 491
 492     while ((ch = getopt(argc, argv, "dfl:n:tT:N")) != -1) {
 493         switch (ch) {
 494 #if HAVE_USE_DEFAULT_COLORS
 495         case 'd':
 496             opt_d = TRUE;
 497             break;
 498 #endif
 499         case 'f':
 500             field = "WORM";
 501             break;
 502         case 'l':
 503             if ((length = atoi(optarg)) < 2 || length > MAX_LENGTH) {
 504                 fprintf(stderr, "%s: Invalid length\n", *argv);
 505                 usage();
 506             }
 507             break;
 508         case 'n':
 509             if ((number = atoi(optarg)) < 1 || number > MAX_WORMS) {
 510                 fprintf(stderr, "%s: Invalid number of worms\n", *argv);
 511                 usage();
 512             }
 513             break;
 514         case 't':
 515             trail = '.';
 516             break;
 517 #ifdef TRACE
 518         case 'T':
 519             if (sscanf(optarg, "%d,%d", &trace_start, &trace_end) != 2)
 520                 usage();
 521             break;
 522         case 'N':
 523             _nc_optimize_enable ^= OPTIMIZE_ALL;        /* declared by ncurses */
 524             break;
 525 #endif /* TRACE */
 526         default:
 527             usage();
 528             /* NOTREACHED */
 529         }
 530     }
 531     if (optind < argc)
 532         usage();
 533
 534     signal(SIGINT, onsig);
 535     initscr();
 536     noecho();
 537     cbreak();
 538     nonl();
 539
 540     curs_set(0);
 541
 542     last_y = LINES - 1;
 543     last_x = COLS - 1;
 544
 545 #ifdef A_COLOR
 546     if (has_colors()) {
 547         int bg = COLOR_BLACK;
 548         start_color();
 549 #if HAVE_USE_DEFAULT_COLORS
 550         if (opt_d && (use_default_colors() == OK))
 551             bg = -1;
 552 #endif
 553
 554 #define SET_COLOR(num, fg) \
 555             init_pair(num+1, (short) fg, (short) bg); \
 556             flavor[num] |= (chtype) COLOR_PAIR(num+1) | A_BOLD
 557
 558         SET_COLOR(0, COLOR_GREEN);
 559         SET_COLOR(1, COLOR_RED);
 560         SET_COLOR(2, COLOR_CYAN);
 561         SET_COLOR(3, COLOR_WHITE);
 562         SET_COLOR(4, COLOR_MAGENTA);
 563         SET_COLOR(5, COLOR_BLUE);
 564         SET_COLOR(6, COLOR_YELLOW);
 565     }
 566 #endif /* A_COLOR */
 567
 568     max_refs = LINES;
 569     refs = typeMalloc(int *, (size_t) max_refs);
 570     for (y = 0; y < max_refs; y++) {
 571         refs[y] = typeMalloc(int, (size_t) COLS);
 572         for (x = 0; x < COLS; x++) {
 573             refs[y][x] = 0;
 574         }
 575     }
 576
 577 #ifdef BADCORNER
 578     /* if addressing the lower right corner doesn't work in your curses */
 579     refs[last_y][last_x] = 1;
 580 #endif /* BADCORNER */
 581
 582     for (n = number, w = &worm[0]; --n >= 0; w++) {
 583         w->attrs = flavor[(unsigned) n % SIZEOF(flavor)];
 584         w->orientation = 0;
 585         w->head = 0;
 586
 587         if (!(ip = typeMalloc(int, (size_t) (length + 1)))) {
 588             fprintf(stderr, "%s: out of memory\n", *argv);
 589             ExitProgram(EXIT_FAILURE);
 590         }
 591         w->xpos = ip;
 592         for (x = length; --x >= 0;)
 593             *ip++ = -1;
 594         if (!(ip = typeMalloc(int, (size_t) (length + 1)))) {
 595             fprintf(stderr, "%s: out of memory\n", *argv);
 596             ExitProgram(EXIT_FAILURE);
 597         }
 598         w->ypos = ip;
 599         for (y = length; --y >= 0;)
 600             *ip++ = -1;
 601     }
 602     if (field) {
 603         const char *p;
 604         p = field;
 605         for (y = last_y; --y >= 0;) {
 606             for (x = COLS; --x >= 0;) {
 607                 addch((chtype) (*p++));
 608                 if (!*p)
 609                     p = field;
 610             }
 611         }
 612     }
 613     USING_WINDOW1(stdscr, wrefresh, safe_wrefresh);
 614     nodelay(stdscr, TRUE);
 615
 616 #ifdef USE_PTHREADS
 617     pthread_mutex_init(&pending_mutex, NULL);
 618 #endif
 619
 620     while (!done) {
 621         Locked(++sequence);
 622         if ((ch = get_input()) > 0) {
 623 #ifdef TRACE
 624             if (trace_start || trace_end) {
 625                 if (generation == trace_start) {
 626                     curses_trace(TRACE_CALLS);
 627                     get_input();
 628                 } else if (generation == trace_end) {
 629                     curses_trace(0);
 630                     get_input();
 631                 }
 632
 633                 generation++;
 634             }
 635 #endif
 636
 637 #ifdef KEY_RESIZE
 638             if (ch == KEY_RESIZE) {
 639                 USING_WINDOW(stdscr, update_refs);
 640             }
 641 #endif
 642
 643             /*
 644              * Make it simple to put this into single-step mode, or resume
 645              * normal operation -T.Dickey
 646              */
 647             if (ch == 'q') {
 648                 quitting = TRUE;
 649                 done = TRUE;
 650                 Trace(("done - quitting"));
 651                 continue;
 652             } else if (ch == 's') {
 653                 nodelay(stdscr, FALSE);
 654             } else if (ch == ' ') {
 655                 nodelay(stdscr, TRUE);
 656             }
 657         }
 658
 659         done = draw_all_worms();
 660         napms(10);
 661         USING_WINDOW1(stdscr, wrefresh, safe_wrefresh);
 662     }
 663
 664     Trace(("Cleanup"));
 665     cleanup();
 666 #ifdef USE_PTHREADS
 667     /*
 668      * Do this just in case one of the threads did not really exit.
 669      */
 670     Trace(("join all threads"));
 671     for (n = 0; n < number; n++) {
 672         pthread_join(worm[n].thread, NULL);
 673     }
 674 #endif
 675 #if NO_LEAKS
 676     for (y = 0; y < max_refs; y++) {
 677         free(refs[y]);
 678     }
 679     free(refs);
 680     for (n = number, w = &worm[0]; --n >= 0; w++) {
 681         free(w->xpos);
 682         free(w->ypos);
 683     }
 684 #endif
 685     ExitProgram(EXIT_SUCCESS);
 686 }