git.ozlabs.org Git - ccan/blob - ccan/antithread/examples/arabella.c

   1 /* Antithread example to approximate picture with triangles using
   2  * genetic algorithm.   Example for a 2 cpu system:
   3  *      ./arabella arabella.jpg out out.save 2
   4  */
   5 #include <stdio.h>
   6 #include <jpeglib.h>
   7 #include <ccan/talloc/talloc.h>
   8 #include <err.h>
   9 #include <assert.h>
  10 #include <limits.h>
  11 #include <string.h>
  12 #include <stdint.h>
  13 #include <math.h>
  14 #include <sys/select.h>
  15 #include <ccan/str/str.h>
  16 #include <ccan/antithread/antithread.h>
  17 #include <sys/types.h>
  18 #include <unistd.h>
  19
  20 // Define this to run 100 times without dumping state
  21 //#define BENCHMARK
  22
  23 /* How many drawings in entire population. */
  24 #define POPULATION_SIZE 1000
  25
  26 /* How many generations without 1% improvement before we terminate. */
  27 #define PLATEAU_GENS 200
  28
  29 /* An image buffer to render into. */
  30 struct image {
  31         unsigned height, width;
  32         unsigned int stride;
  33         /* RGB data */
  34         unsigned char *buffer;
  35 };
  36
  37 /* A drawing is a (fixed) number of triangles. */
  38 struct drawing {
  39         struct triangle *tri;
  40         unsigned int num_tris;
  41         unsigned long score;
  42 };
  43
  44 /* Here's a triangle. */
  45 struct triangle {
  46         struct {
  47                 unsigned int x, y;
  48         } coord[3];
  49
  50         /* RGBA */
  51         unsigned char color[4];
  52         unsigned char mult;
  53         uint16_t add[3];
  54 };
  55
  56 /* Get pointer into image at a specific location. */
  57 static unsigned char *image_at(struct image *image,
  58                                unsigned int x, unsigned int y)
  59 {
  60         return image->buffer + y * image->stride + x * 3;
  61 }
  62
  63 /* Blend a dot into this location. */
  64 static void add_dot(unsigned char *buf,
  65                     unsigned char mult, const uint16_t add[])
  66 {
  67         unsigned int c;
  68         /* /256 isn't quite right, but it's much faster than /255 */
  69         for (c = 0; c < 3; c++)
  70                 buf[c] = (buf[c] * mult + add[c]) / 256;
  71 }
  72
  73 /* Code based on example taken from:
  74  * http://www.devmaster.net/forums/showthread.php?t=1094 */
  75 static void add_flat_triangle(struct image *image,
  76                               int x0, int y0, int x1, int y1, int x2, int y2,
  77                               unsigned char mult, const uint16_t add[])
  78 {
  79         unsigned char *buf;
  80         unsigned int i, j;
  81
  82         // compute slopes for the two triangle legs
  83         float dx0 = (float)(x2 - x0) / (y2 - y0);
  84         float dx1 = (float)(x2 - x1) / (y2 - y1);
  85
  86         int yRange = 0;
  87
  88         float lx = (float) x0, rx = (float) x1;
  89
  90         if (y0 < y2) {
  91                 yRange = y2 - y0;
  92                 buf = image_at(image, 0, y0);
  93         } else {
  94                 yRange = y0 - y2;
  95                 buf = image_at(image, 0, y2);
  96                 lx = rx = (float)x2;
  97         }
  98
  99         for (i=0; i < yRange; ++i) {
 100                 for (j=(int)(lx); j<(int)((rx) + 1.0f); ++j)
 101                         add_dot(buf + 3 * j, mult, add);
 102
 103                 lx  += dx0;
 104                 rx  += dx1;
 105                 buf += image->stride;
 106         }
 107 }
 108
 109 static void swap(int *a, int *b)
 110 {
 111         int tmp = *a;
 112         *a = *b;
 113         *b = tmp;
 114 }
 115
 116 static void paint_triangle(struct image *image, const struct triangle *tri)
 117 {
 118         int i0 = 0, i1 = 1, i2 = 2;
 119         int x0, y0, x1, y1, x2, y2;
 120
 121         /* Could do this on triangle creation. */
 122         // sort verts by height
 123         if (tri->coord[i0].y > tri->coord[i1].y) swap(&i0, &i1);
 124         if (tri->coord[i0].y > tri->coord[i2].y) swap(&i0, &i2);
 125         if (tri->coord[i1].y > tri->coord[i2].y) swap(&i1, &i2);
 126
 127         x0 = tri->coord[i0].x, y0 = tri->coord[i0].y;
 128         x1 = tri->coord[i1].x, y1 = tri->coord[i1].y;
 129         x2 = tri->coord[i2].x, y2 = tri->coord[i2].y;
 130
 131         // test for easy cases, else split trinagle in two and render both halfs
 132         if (y1 == y2) {
 133                 if (x1 > x2) swap(&x1, &x2);
 134                 add_flat_triangle(image, x1, y1, x2, y2, x0, y0,
 135                                   tri->mult, tri->add);
 136         } else if (y0 == y1) {
 137                 if (x0 > x1) swap(&x0, &x1);
 138                 add_flat_triangle(image, x0, y0, x1, y1, x2, y2,
 139                                   tri->mult, tri->add);
 140         } else {
 141                 // compute x pos of the vert that builds the splitting line with x1
 142                 int tmp_x = x0 + (int)(0.5f + (float)(y1-y0) * (float)(x2-x0) / (float)(y2-y0));
 143
 144                 if (x1 > tmp_x) swap(&x1, &tmp_x);
 145                 add_flat_triangle(image, x1, y1, tmp_x, y1, x0, y0,
 146                                   tri->mult, tri->add);
 147                 add_flat_triangle(image, x1, y1, tmp_x, y1, x2, y2,
 148                                   tri->mult, tri->add);
 149         }
 150 }
 151
 152 /* Create a new image, allocated off context. */
 153 static struct image *new_image(const void *ctx,
 154                                unsigned width, unsigned height, unsigned stride)
 155 {
 156         struct image *image = talloc(ctx, struct image);
 157
 158         image->width = width;
 159         image->height = height;
 160         image->stride = stride;
 161         image->buffer = talloc_zero_array(image, unsigned char,
 162                                           stride * height);
 163         return image;
 164 }
 165
 166 /* Taken from JPEG example code.  Quality is 1 to 100. */
 167 static void write_jpeg_file(const struct image *image,
 168                             const char *filename, int quality)
 169 {
 170         struct jpeg_compress_struct cinfo;
 171         struct jpeg_error_mgr jerr;
 172         FILE *outfile;
 173         JSAMPROW row_pointer[1];
 174         int row_stride;
 175
 176         cinfo.err = jpeg_std_error(&jerr);
 177         jpeg_create_compress(&cinfo);
 178
 179         if ((outfile = fopen(filename, "wb")) == NULL)
 180                 err(1, "can't open %s", filename);
 181
 182         jpeg_stdio_dest(&cinfo, outfile);
 183
 184         cinfo.image_width = image->width;
 185         cinfo.image_height = image->height;
 186         cinfo.input_components = 3;
 187         cinfo.in_color_space = JCS_RGB;
 188         jpeg_set_defaults(&cinfo);
 189         jpeg_set_quality(&cinfo, quality, TRUE);
 190
 191         jpeg_start_compress(&cinfo, TRUE);
 192         row_stride = image->width * 3;
 193
 194         while (cinfo.next_scanline < cinfo.image_height) {
 195                 row_pointer[0] = image->buffer + cinfo.next_scanline*row_stride;
 196                 (void) jpeg_write_scanlines(&cinfo, row_pointer, 1);
 197         }
 198
 199         jpeg_finish_compress(&cinfo);
 200         fclose(outfile);
 201
 202         jpeg_destroy_compress(&cinfo);
 203 }
 204
 205 static struct image *read_jpeg_file(const void *ctx, const char *filename)
 206 {
 207         struct jpeg_decompress_struct cinfo;
 208         struct image *image;
 209         struct jpeg_error_mgr jerr;
 210         FILE *infile;
 211         int row_stride;
 212
 213         if ((infile = fopen(filename, "rb")) == NULL)
 214                 err(1, "can't open %s", filename);
 215
 216         cinfo.err = jpeg_std_error(&jerr);
 217
 218         jpeg_create_decompress(&cinfo);
 219
 220         jpeg_stdio_src(&cinfo, infile);
 221
 222         jpeg_read_header(&cinfo, TRUE);
 223
 224         jpeg_start_decompress(&cinfo);
 225         row_stride = cinfo.output_width * cinfo.output_components;
 226
 227         image = new_image(ctx,
 228                           cinfo.output_width, cinfo.output_height, row_stride);
 229         while (cinfo.output_scanline < cinfo.output_height) {
 230                 JSAMPROW row = &image->buffer[cinfo.output_scanline*row_stride];
 231                 jpeg_read_scanlines(&cinfo, &row, 1);
 232         }
 233
 234         (void) jpeg_finish_decompress(&cinfo);
 235         jpeg_destroy_decompress(&cinfo);
 236         fclose(infile);
 237         return image;
 238 }
 239
 240 /* Higher means closer to perfect match.  We assume images same size. */
 241 static unsigned long compare_images(const struct image *a,
 242                                     const struct image *b)
 243 {
 244         unsigned long result = 0;
 245         unsigned i;
 246
 247         /* Huge images won't work here.  We'd need to get cleverer. */
 248         assert(a->height * a->stride < ULONG_MAX / 8);
 249
 250         for (i = 0; i < a->height * a->stride; i++) {
 251                 if (a->buffer[i] > b->buffer[i])
 252                         result += a->buffer[i] - b->buffer[i];
 253                 else
 254                         result += b->buffer[i] - a->buffer[i];
 255         }
 256         return result;
 257 }
 258
 259 /* Precalculate the alpha adds and multiplies for this color/alpha combo. */
 260 static void calc_multipliers(struct triangle *tri)
 261 {
 262         /* Multiply by 255 - alpha. */
 263         tri->mult = (255 - tri->color[3]);
 264         /* Add alpha * color */
 265         tri->add[0] = (tri->color[0] * tri->color[3]);
 266         tri->add[1] = (tri->color[1] * tri->color[3]);
 267         tri->add[2] = (tri->color[2] * tri->color[3]);
 268 }
 269
 270 /* Render the image of this drawing, and return it. */
 271 static struct image *image_of_drawing(const void *ctx,
 272                                       const struct drawing *drawing,
 273                                       const struct image *master)
 274 {
 275         struct image *image;
 276         unsigned int i;
 277
 278         image = new_image(ctx, master->width, master->height, master->stride);
 279
 280         for (i = 0; i < drawing->num_tris; i++)
 281                 paint_triangle(image, &drawing->tri[i]);
 282         return image;
 283 }
 284
 285 /* Render the image and compare with the master. */
 286 static void score_drawing(struct drawing *drawing,
 287                           const struct image *master)
 288 {
 289         struct image *image;
 290
 291         /* We don't allocate it off the drawing, since we don't need
 292          * it inside the shared area. */
 293         image = image_of_drawing(NULL, drawing, master);
 294         drawing->score = compare_images(image, master);
 295         talloc_free(image);
 296 }
 297
 298 /* Create a new drawing allocated off context (which is the antithread
 299  * pool context, so this is all allocated inside the pool so the
 300  * antithreads can access it).
 301  */
 302 static struct drawing *new_drawing(const void *ctx, unsigned int num_tris)
 303 {
 304         struct drawing *drawing = talloc_zero(ctx, struct drawing);
 305         drawing->num_tris = num_tris;
 306         drawing->tri = talloc_array(drawing, struct triangle, num_tris);
 307         return drawing;
 308 }
 309
 310 /* Make a random change to the drawing: frob one triangle. */
 311 static void mutate_drawing(struct drawing *drawing,
 312                            const struct image *master)
 313 {
 314         unsigned int i, r = random();
 315         struct triangle *tri = &drawing->tri[r % drawing->num_tris];
 316
 317         r /= drawing->num_tris;
 318         r %= 12;
 319         if (r < 6) {
 320                 /* Move one corner in x or y dir. */
 321                 if (r % 2)
 322                         tri->coord[r/2].x = random() % master->width;
 323                 else
 324                         tri->coord[r/2].y = random() % master->height;
 325         } else if (r < 10) {
 326                 /* Change one aspect of color. */
 327                 tri->color[r - 6] = random() % 256;
 328         } else if (r == 10) {
 329                 /* Completely move a triangle. */
 330                 for (i = 0; i < 3; i++) {
 331                         tri->coord[i].x = random() % master->width;
 332                         tri->coord[i].y = random() % master->height;
 333                 }
 334         } else {
 335                 /* Completely change a triangle's colour. */
 336                 for (i = 0; i < 4; i++)
 337                         tri->color[i] = random() % 256;
 338         }
 339         calc_multipliers(tri);
 340 }
 341
 342 /* Breed two drawings together, and throw in a mutation. */
 343 static struct drawing *breed_drawing(const void *ctx,
 344                                      const struct drawing *a,
 345                                      const struct drawing *b,
 346                                      const struct image *master)
 347 {
 348         unsigned int i;
 349         struct drawing *drawing;
 350         unsigned int r = random(), randmax = RAND_MAX;
 351
 352         assert(a->num_tris == b->num_tris);
 353         drawing = new_drawing(ctx, a->num_tris);
 354
 355         for (i = 0; i < a->num_tris; i++) {
 356                 switch (r & 1) {
 357                 case 0:
 358                         /* Take from A. */
 359                         drawing->tri[i] = a->tri[i];
 360                         break;
 361                 case 1:
 362                         /* Take from B. */
 363                         drawing->tri[i] = b->tri[i];
 364                         break;
 365                 }
 366                 r >>= 1;
 367                 randmax >>= 1;
 368                 if (randmax == 0) {
 369                         r = random();
 370                         randmax = RAND_MAX;
 371                 }
 372         }
 373         mutate_drawing(drawing, master);
 374         score_drawing(drawing, master);
 375         return drawing;
 376 }
 377
 378 /* This is our anti-thread.  It does the time-consuming operation of
 379  * breeding two drawings together and scoring the result. */
 380 static void *breeder(struct at_pool *atp, struct image *master)
 381 {
 382         const struct drawing *a, *b;
 383
 384         /* For simplicity, controller just hands us two pointers in
 385          * separate writes.  It could put them in the pool for us to
 386          * read. */
 387         while ((a = at_read_parent(atp)) != NULL) {
 388                 struct drawing *child;
 389                 b = at_read_parent(atp);
 390
 391                 child = breed_drawing(at_pool_ctx(atp), a, b, master);
 392                 at_tell_parent(atp, child);
 393         }
 394         /* Unused: we never exit. */
 395         return NULL;
 396 }
 397
 398 /* We keep a very rough count of how much work each athread has.  This
 399  * works fine since fairly all rendering takes about the same time.
 400  *
 401  * Better alternative would be to put all the pending work somewhere
 402  * in the shared area and notify any idle thread.  The threads would
 403  * keep looking in that shared area until they can't see any more
 404  * work, then they'd at_tell_parent() back. */
 405 struct athread_work {
 406         struct athread *at;
 407         unsigned int pending;
 408 };
 409
 410 /* It's assumed that there isn't more than num results pending. */
 411 static unsigned gather_results(struct athread_work *athreads,
 412                                unsigned int num_threads,
 413                                struct drawing **drawing,
 414                                unsigned int num,
 415                                bool block)
 416 {
 417         unsigned int i, maxfd = 0, done = 0;
 418         struct timeval zero = { .tv_sec = 0, .tv_usec = 0 };
 419
 420         /* If it mattered, we could cache this fd mask and maxfd. */
 421         for (i = 0; i < num_threads; i++) {
 422                 if (at_fd(athreads[i].at) > maxfd)
 423                         maxfd = at_fd(athreads[i].at);
 424         }
 425
 426         do {
 427                 fd_set set;
 428                 FD_ZERO(&set);
 429                 for (i = 0; i < num_threads; i++)
 430                         FD_SET(at_fd(athreads[i].at), &set);
 431
 432                 if (select(maxfd+1, &set, NULL, NULL, block ? NULL : &zero) < 0)
 433                         err(1, "Selecting on antithread results");
 434
 435                 for (i = 0; i < num_threads; i++) {
 436                         if (!FD_ISSET(at_fd(athreads[i].at), &set))
 437                                 continue;
 438                         *drawing = at_read(athreads[i].at);
 439                         if (!*drawing)
 440                                 err(1, "Error with thread %u", i);
 441                         drawing++;
 442                         num--;
 443                         athreads[i].pending--;
 444                         done++;
 445                 }
 446         } while (block && num);
 447
 448         return done;
 449 }
 450
 451 /* Hand work to an antithread to breed these two together. */
 452 static void tell_some_breeder(struct athread_work *athreads,
 453                               unsigned int num_threads,
 454                               const struct drawing *a, const struct drawing *b)
 455 {
 456         unsigned int i, best = 0;
 457
 458         /* Find least loaded thread. */
 459         for (i = 1; i < num_threads; i++) {
 460                 if (athreads[i].pending < athreads[best].pending)
 461                         best = i;
 462         }
 463
 464         at_tell(athreads[best].at, a);
 465         at_tell(athreads[best].at, b);
 466         athreads[best].pending++;
 467 }
 468
 469 /* We seed initial triangles colours from the master image. */
 470 static const unsigned char *initial_random_color(const struct image *master)
 471 {
 472         return master->buffer + (random() % (master->height * master->width))*3;
 473 }
 474
 475 /* Create an initial random drawing. */
 476 static struct drawing *random_drawing(const void *ctx,
 477                                       const struct image *master,
 478                                       unsigned int num_tris)
 479 {
 480         struct drawing *drawing = new_drawing(ctx, num_tris);
 481         unsigned int i;
 482
 483         for (i = 0; i < drawing->num_tris; i++) {
 484                 unsigned int c;
 485                 struct triangle *tri = &drawing->tri[i];
 486                 for (c = 0; c < 3; c++) {
 487                         tri->coord[c].x = random() % master->width;
 488                         tri->coord[c].y = random() % master->height;
 489                 }
 490                 memcpy(tri->color, initial_random_color(master), 3);
 491                 tri->color[3] = (random() % 255) + 1;
 492                 calc_multipliers(tri);
 493         }
 494         score_drawing(drawing, master);
 495         return drawing;
 496 }
 497
 498 /* Read in a drawing from the saved state file. */
 499 static struct drawing *read_drawing(const void *ctx, FILE *in,
 500                                     const struct image *master)
 501 {
 502         struct drawing *drawing;
 503         unsigned int i;
 504
 505         if (fscanf(in, "%u triangles:\n", &i) != 1)
 506                 errx(1, "Reading saved state");
 507         drawing = new_drawing(ctx, i);
 508         for (i = 0; i < drawing->num_tris; i++) {
 509                 unsigned int color[4];
 510                 if (fscanf(in, "%u,%u,%u,%u,%u,%u,%u,%u,%u,%u\n",
 511                            &drawing->tri[i].coord[0].x,
 512                            &drawing->tri[i].coord[0].y,
 513                            &drawing->tri[i].coord[1].x,
 514                            &drawing->tri[i].coord[1].y,
 515                            &drawing->tri[i].coord[2].x,
 516                            &drawing->tri[i].coord[2].y,
 517                            &color[0], &color[1], &color[2], &color[3]) != 10)
 518                         errx(1, "Reading saved state");
 519                 drawing->tri[i].color[0] = color[0];
 520                 drawing->tri[i].color[1] = color[1];
 521                 drawing->tri[i].color[2] = color[2];
 522                 drawing->tri[i].color[3] = color[3];
 523                 calc_multipliers(&drawing->tri[i]);
 524         }
 525         score_drawing(drawing, master);
 526         return drawing;
 527 }
 528
 529 /* Comparison function for sorting drawings best to worst. */
 530 static int compare_drawing_scores(const void *_a, const void *_b)
 531 {
 532         struct drawing **a = (void *)_a, **b = (void *)_b;
 533
 534         return (*a)->score - (*b)->score;
 535 }
 536
 537 /* Save one drawing to state file */
 538 static void dump_drawings(struct drawing **drawing, const char *outname)
 539 {
 540         FILE *out;
 541         unsigned int i, j;
 542         char *tmpout = talloc_asprintf(NULL, "%s.tmp", outname);
 543
 544         out = fopen(tmpout, "w");
 545         if (!out)
 546                 err(1, "Opening %s", tmpout);
 547         fprintf(out, "POPULATION_SIZE=%u\n", POPULATION_SIZE);
 548         for (i = 0; i < POPULATION_SIZE; i++) {
 549                 fprintf(out, "%u triangles:\n", drawing[i]->num_tris);
 550                 for (j = 0; j < drawing[i]->num_tris; j++) {
 551                         fprintf(out, "%u,%u,%u,%u,%u,%u,%u,%u,%u,%u\n",
 552                                 drawing[i]->tri[j].coord[0].x,
 553                                 drawing[i]->tri[j].coord[0].y,
 554                                 drawing[i]->tri[j].coord[1].x,
 555                                 drawing[i]->tri[j].coord[1].y,
 556                                 drawing[i]->tri[j].coord[2].x,
 557                                 drawing[i]->tri[j].coord[2].y,
 558                                 drawing[i]->tri[j].color[0],
 559                                 drawing[i]->tri[j].color[1],
 560                                 drawing[i]->tri[j].color[2],
 561                                 drawing[i]->tri[j].color[3]);
 562                 }
 563         }
 564         if (fclose(out) != 0)
 565                 err(1, "Failure closing %s", tmpout);
 566
 567         if (rename(tmpout, outname) != 0)
 568                 err(1, "Renaming %s over %s", tmpout, outname);
 569         talloc_free(tmpout);
 570 }
 571
 572 /* Save state file. */
 573 static void dump_state(struct drawing *drawing[POPULATION_SIZE],
 574                        const struct image *master,
 575                        const char *outpic,
 576                        const char *outstate,
 577                        unsigned int gen)
 578 {
 579         char *out = talloc_asprintf(NULL, "%s.%08u.jpg", outpic, gen);
 580         struct image *image;
 581         printf("Dumping gen %u to %s & %s\n", gen, out, outstate);
 582         dump_drawings(drawing, outstate);
 583         image = image_of_drawing(out, drawing[0], master);
 584         write_jpeg_file(image, out, 80);
 585         talloc_free(out);
 586 }
 587
 588 /* Biassed coinflip moves us towards top performers.  I didn't spend
 589  * too much time on it, but 1/32 seems to give decent results (see
 590  * breeding-algos.gnumeric). */
 591 static struct drawing *select_good_drawing(struct drawing *drawing[],
 592                                            unsigned int population)
 593 {
 594         if (population == 1)
 595                 return drawing[0];
 596         if (random() % 32)
 597                 return select_good_drawing(drawing, population/2);
 598         return select_good_drawing(drawing + population/2, population/2);
 599 }
 600
 601 static void usage(void)
 602 {
 603         errx(1, "usage: <infile> <outfile> <statefile> <numtriangles> <numcpus> [<instatefile>]");
 604 }
 605
 606 int main(int argc, char *argv[])
 607 {
 608         struct image *master;
 609         unsigned int gen, since_prev_best, num_threads, i;
 610         struct drawing *drawing[POPULATION_SIZE];
 611         unsigned long prev_best, poolsize;
 612         struct at_pool *atp;
 613         struct athread_work *athreads;
 614
 615         if (argc != 6 && argc != 7)
 616                 usage();
 617
 618         /* Room for triangles and master image, with some spare.
 619          * We should really read master image header first, so we can be
 620          * more precise than "about 3MB".  ccan/alloc also needs some
 621          * more work to be more efficient. */
 622         poolsize = (POPULATION_SIZE + POPULATION_SIZE/4) * (sizeof(struct drawing) + atoi(argv[4]) * sizeof(struct triangle)) * 2 + 1000 * 1000 * 3;
 623         atp = at_pool(poolsize);
 624         if (!atp)
 625                 err(1, "Creating pool of %lu bytes", poolsize);
 626
 627         /* Auto-free the pool and anything hanging off it (eg. threads). */
 628         talloc_steal(talloc_autofree_context(), atp);
 629
 630         /* Read in file */
 631         master = read_jpeg_file(at_pool_ctx(atp), argv[1]);
 632
 633         if (argc == 6) {
 634                 printf("Creating initial population");
 635                 fflush(stdout);
 636                 for (i = 0; i < POPULATION_SIZE; i++) {
 637                         drawing[i] = random_drawing(at_pool_ctx(atp),
 638                                                     master, atoi(argv[4]));
 639                         printf(".");
 640                         fflush(stdout);
 641                 }
 642                 printf("\n");
 643         } else {
 644                 FILE *state;
 645                 char header[100];
 646                 state = fopen(argv[6], "r");
 647                 if (!state)
 648                         err(1, "Opening %s", argv[6]);
 649                 fflush(stdout);
 650                 fgets(header, 100, state);
 651                 printf("Loading initial population from %s: %s", argv[6],
 652                         header);
 653                 for (i = 0; i < POPULATION_SIZE; i++) {
 654                         drawing[i] = read_drawing(at_pool_ctx(atp),
 655                                                   state, master);
 656                         printf(".");
 657                         fflush(stdout);
 658                 }
 659         }
 660
 661         num_threads = atoi(argv[5]);
 662         if (!num_threads)
 663                 usage();
 664
 665         /* Hang the threads off the pool (not *in* the pool). */
 666         athreads = talloc_array(atp, struct athread_work, num_threads);
 667         for (i = 0; i < num_threads; i++) {
 668                 athreads[i].pending = 0;
 669                 athreads[i].at = at_run(atp, breeder, master);
 670                 if (!athreads[i].at)
 671                         err(1, "Creating antithread %u", i);
 672         }
 673
 674         since_prev_best = 0;
 675         /* Worse than theoretically worst case. */
 676         prev_best = master->height * master->stride * 256;
 677
 678         for (gen = 0; since_prev_best < PLATEAU_GENS; gen++) {
 679                 unsigned int j, done = 0;
 680                 struct drawing *new[POPULATION_SIZE/4];
 681
 682                 qsort(drawing, POPULATION_SIZE, sizeof(drawing[0]),
 683                       compare_drawing_scores);
 684
 685                 printf("Best %lu, worst %lu\n",
 686                        drawing[0]->score, drawing[POPULATION_SIZE-1]->score);
 687
 688                 /* Probability of being chosen to breed depends on
 689                  * rank.  We breed over lowest 1/4 population. */
 690                 for (j = 0; j < POPULATION_SIZE / 4; j++) {
 691                         struct drawing *best1, *best2;
 692
 693                         best1 = select_good_drawing(drawing, POPULATION_SIZE);
 694                         best2 = select_good_drawing(drawing, POPULATION_SIZE);
 695
 696                         tell_some_breeder(athreads, num_threads, best1, best2);
 697
 698                         /* We reap during loop, so return pipes don't fill.
 699                          * See "Better alternative" above. */
 700                         done += gather_results(athreads, num_threads,
 701                                                new + done, j - done, false);
 702                 }
 703
 704                 /* Collate final results. */
 705                 gather_results(athreads, num_threads, new+done, j-done, true);
 706
 707                 /* Overwrite bottom 1/4 */
 708                 for (j = POPULATION_SIZE * 3 / 4; j < POPULATION_SIZE; j++) {
 709                         talloc_free(drawing[j]);
 710                         drawing[j] = new[j - POPULATION_SIZE * 3 / 4];
 711                 }
 712
 713                 /* We dump on every 1% improvement in score. */
 714                 if (drawing[0]->score < prev_best * 0.99) {
 715 #ifndef BENCHMARK
 716                         dump_state(drawing, master, argv[2], argv[3], gen);
 717 #endif
 718                         prev_best = drawing[0]->score;
 719                         since_prev_best = 0;
 720                 } else
 721                         since_prev_best++;
 722
 723 #ifdef BENCHMARK
 724                 if (gen == 100)
 725                         exit(0);
 726 #endif
 727         }
 728
 729         /* Dump final state */
 730         printf("No improvement over %lu for %u gens\n",
 731                prev_best, since_prev_best);
 732         dump_state(drawing, master, argv[2], argv[3], gen);
 733         return 0;
 734 }