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