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.89 2022/12/24 20:46:49 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         for (;;) {
 372             bool done = FALSE;
 373             Locked(done = (compare >= sequence));
 374             if (done)
 375                 break;
 376             ++compare;
 377             USING_WINDOW2(stdscr, draw_worm, arg);
 378         }
 379     }
 380     Trace(("...start_worm (done)"));
 381     return NULL;
 382 }
 383 #endif
 384
 385 static bool
 386 draw_all_worms(void)
 387 {
 388     bool done = FALSE;
 389     int n;
 390     struct worm *w;
 391
 392 #ifdef USE_PTHREADS
 393     static bool first = TRUE;
 394     if (first) {
 395         first = FALSE;
 396         for (n = 0, w = &worm[0]; n < number; n++, w++) {
 397             (void) pthread_create(&(w->thread), NULL, start_worm, w);
 398         }
 399     }
 400 #else
 401     for (n = 0, w = &worm[0]; n < number; n++, w++) {
 402         if (USING_WINDOW2(stdscr, draw_worm, w))
 403             done = TRUE;
 404     }
 405 #endif
 406     return done;
 407 }
 408
 409 static int
 410 get_input(void)
 411 {
 412     int ch;
 413     ch = USING_WINDOW1(stdscr, wgetch, safe_wgetch);
 414     return ch;
 415 }
 416
 417 #ifdef KEY_RESIZE
 418 static int
 419 update_refs(WINDOW *win, void *data)
 420 {
 421     int x, y;
 422
 423     (void) win;
 424     (void) data;
 425     if (last_x != COLS - 1) {
 426         for (y = 0; y <= last_y; y++) {
 427             refs[y] = typeRealloc(int, (size_t) COLS, refs[y]);
 428             if (!refs[y])
 429                 failed("update_refs");
 430             for (x = last_x + 1; x < COLS; x++)
 431                 refs[y][x] = 0;
 432         }
 433         last_x = COLS - 1;
 434     }
 435     if (last_y != LINES - 1) {
 436         for (y = LINES; y <= last_y; y++)
 437             free(refs[y]);
 438         max_refs = LINES;
 439         refs = typeRealloc(int *, (size_t) LINES, refs);
 440         for (y = last_y + 1; y < LINES; y++) {
 441             refs[y] = typeMalloc(int, (size_t) COLS);
 442             if (!refs[y])
 443                 failed("update_refs");
 444             for (x = 0; x < COLS; x++)
 445                 refs[y][x] = 0;
 446         }
 447         last_y = LINES - 1;
 448     }
 449     return OK;
 450 }
 451 #endif
 452
 453 static void
 454 usage(int ok)
 455 {
 456     static const char *msg[] =
 457     {
 458         "Usage: worm [options]"
 459         ,""
 460         ,USAGE_COMMON
 461         ,"Options:"
 462 #if HAVE_USE_DEFAULT_COLORS
 463         ," -d       invoke use_default_colors"
 464 #endif
 465         ," -f       fill screen with copies of \"WORM\" at start"
 466         ," -l <n>   set length of worms"
 467         ," -n <n>   set number of worms"
 468         ," -t       leave trail of \".\""
 469 #ifdef TRACE
 470         ," -T <start>,<end> set trace interval"
 471         ," -N       suppress cursor-movement optimization"
 472 #endif
 473     };
 474     size_t n;
 475
 476     for (n = 0; n < SIZEOF(msg); n++)
 477         fprintf(stderr, "%s\n", msg[n]);
 478
 479     ExitProgram(ok ? EXIT_SUCCESS : EXIT_FAILURE);
 480 }
 481 /* *INDENT-OFF* */
 482 VERSION_COMMON()
 483 /* *INDENT-ON* */
 484
 485 int
 486 main(int argc, char *argv[])
 487 {
 488     int ch;
 489     int x, y;
 490     int n;
 491     struct worm *w;
 492     int *ip;
 493     bool done = FALSE;
 494 #if HAVE_USE_DEFAULT_COLORS
 495     bool opt_d = FALSE;
 496 #endif
 497
 498     setlocale(LC_ALL, "");
 499
 500     while ((ch = getopt(argc, argv, OPTS_COMMON "dfl:n:tT:N")) != -1) {
 501         switch (ch) {
 502 #if HAVE_USE_DEFAULT_COLORS
 503         case 'd':
 504             opt_d = TRUE;
 505             break;
 506 #endif
 507         case 'f':
 508             field = "WORM";
 509             break;
 510         case 'l':
 511             if ((length = atoi(optarg)) < 2 || length > MAX_LENGTH) {
 512                 fprintf(stderr, "%s: Invalid length\n", *argv);
 513                 usage(FALSE);
 514             }
 515             break;
 516         case 'n':
 517             if ((number = atoi(optarg)) < 1 || number > MAX_WORMS) {
 518                 fprintf(stderr, "%s: Invalid number of worms\n", *argv);
 519                 usage(FALSE);
 520             }
 521             break;
 522         case 't':
 523             trail = '.';
 524             break;
 525 #ifdef TRACE
 526         case 'T':
 527             if (sscanf(optarg, "%d,%d", &trace_start, &trace_end) != 2)
 528                 usage(FALSE);
 529             break;
 530         case 'N':
 531             _nc_optimize_enable ^= OPTIMIZE_ALL;        /* declared by ncurses */
 532             break;
 533 #endif /* TRACE */
 534         case OPTS_VERSION:
 535             show_version(argv);
 536             ExitProgram(EXIT_SUCCESS);
 537         default:
 538             usage(ch == OPTS_USAGE);
 539             /* NOTREACHED */
 540         }
 541     }
 542     if (optind < argc)
 543         usage(FALSE);
 544
 545     signal(SIGINT, onsig);
 546     initscr();
 547     noecho();
 548     cbreak();
 549     nonl();
 550
 551     curs_set(0);
 552
 553     last_y = LINES - 1;
 554     last_x = COLS - 1;
 555
 556 #ifdef A_COLOR
 557     if (has_colors()) {
 558         int bg = COLOR_BLACK;
 559         start_color();
 560 #if HAVE_USE_DEFAULT_COLORS
 561         if (opt_d && (use_default_colors() == OK))
 562             bg = -1;
 563 #endif
 564
 565 #define SET_COLOR(num, fg) \
 566             init_pair(num+1, (short) fg, (short) bg); \
 567             flavor[num] |= (chtype) COLOR_PAIR(num+1) | A_BOLD
 568
 569         SET_COLOR(0, COLOR_GREEN);
 570         SET_COLOR(1, COLOR_RED);
 571         SET_COLOR(2, COLOR_CYAN);
 572         SET_COLOR(3, COLOR_WHITE);
 573         SET_COLOR(4, COLOR_MAGENTA);
 574         SET_COLOR(5, COLOR_BLUE);
 575         SET_COLOR(6, COLOR_YELLOW);
 576     }
 577 #endif /* A_COLOR */
 578
 579     max_refs = LINES;
 580     refs = typeMalloc(int *, (size_t) max_refs);
 581     for (y = 0; y < max_refs; y++) {
 582         refs[y] = typeMalloc(int, (size_t) COLS);
 583         for (x = 0; x < COLS; x++) {
 584             refs[y][x] = 0;
 585         }
 586     }
 587
 588 #ifdef BADCORNER
 589     /* if addressing the lower right corner doesn't work in your curses */
 590     refs[last_y][last_x] = 1;
 591 #endif /* BADCORNER */
 592
 593     for (n = number, w = &worm[0]; --n >= 0; w++) {
 594         w->attrs = flavor[(unsigned) n % SIZEOF(flavor)];
 595         w->orientation = 0;
 596         w->head = 0;
 597
 598         if (!(ip = typeMalloc(int, (size_t) (length + 1)))) {
 599             fprintf(stderr, "%s: out of memory\n", *argv);
 600             ExitProgram(EXIT_FAILURE);
 601         }
 602         w->xpos = ip;
 603         for (x = length; --x >= 0;)
 604             *ip++ = -1;
 605         if (!(ip = typeMalloc(int, (size_t) (length + 1)))) {
 606             fprintf(stderr, "%s: out of memory\n", *argv);
 607             ExitProgram(EXIT_FAILURE);
 608         }
 609         w->ypos = ip;
 610         for (y = length; --y >= 0;)
 611             *ip++ = -1;
 612     }
 613     if (field) {
 614         const char *p;
 615         p = field;
 616         for (y = last_y; --y >= 0;) {
 617             for (x = COLS; --x >= 0;) {
 618                 addch((chtype) (*p++));
 619                 if (!*p)
 620                     p = field;
 621             }
 622         }
 623     }
 624     USING_WINDOW1(stdscr, wrefresh, safe_wrefresh);
 625     nodelay(stdscr, TRUE);
 626
 627 #ifdef USE_PTHREADS
 628     pthread_mutex_init(&pending_mutex, NULL);
 629 #endif
 630
 631     while (!done) {
 632         Locked(++sequence);
 633         if ((ch = get_input()) > 0) {
 634 #ifdef TRACE
 635             if (trace_start || trace_end) {
 636                 if (generation == trace_start) {
 637                     curses_trace(TRACE_CALLS);
 638                     get_input();
 639                 } else if (generation == trace_end) {
 640                     curses_trace(0);
 641                     get_input();
 642                 }
 643
 644                 generation++;
 645             }
 646 #endif
 647
 648 #ifdef KEY_RESIZE
 649             if (ch == KEY_RESIZE) {
 650                 USING_WINDOW(stdscr, update_refs);
 651             }
 652 #endif
 653
 654             /*
 655              * Make it simple to put this into single-step mode, or resume
 656              * normal operation -T.Dickey
 657              */
 658             if (ch == 'q') {
 659                 quitting = TRUE;
 660                 done = TRUE;
 661                 Trace(("done - quitting"));
 662                 continue;
 663             } else if (ch == 's') {
 664                 nodelay(stdscr, FALSE);
 665             } else if (ch == ' ') {
 666                 nodelay(stdscr, TRUE);
 667             }
 668         }
 669
 670         done = draw_all_worms();
 671         napms(10);
 672         USING_WINDOW1(stdscr, wrefresh, safe_wrefresh);
 673     }
 674
 675     Trace(("Cleanup"));
 676     cleanup();
 677 #ifdef USE_PTHREADS
 678     /*
 679      * Do this just in case one of the threads did not really exit.
 680      */
 681     Trace(("join all threads"));
 682     for (n = 0; n < number; n++) {
 683         pthread_join(worm[n].thread, NULL);
 684     }
 685 #endif
 686 #if NO_LEAKS
 687     for (y = 0; y < max_refs; y++) {
 688         free(refs[y]);
 689     }
 690     free(refs);
 691     for (n = number, w = &worm[0]; --n >= 0; w++) {
 692         free(w->xpos);
 693         free(w->ypos);
 694     }
 695 #endif
 696     ExitProgram(EXIT_SUCCESS);
 697 }