demos/life/game.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        game.cpp
   3 // Purpose:     Life! game logic
   4 // Author:      Guillermo Rodriguez Garcia, <guille@iies.es>
   5 // Modified by:
   6 // Created:     Jan/2000
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 2000, Guillermo Rodriguez Garcia
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 #ifdef __WIN16__
  13 #error "Sorry, Life! will not work in 16-bit Windows"
  14 #endif
  15
  16 // ==========================================================================
  17 // headers, declarations, constants
  18 // ==========================================================================
  19
  20 #ifdef __GNUG__
  21     #pragma implementation "game.h"
  22 #endif
  23
  24 // For compilers that support precompilation, includes "wx/wx.h".
  25 #include "wx/wxprec.h"
  26
  27 #ifdef __BORLANDC__
  28 #pragma hdrstop
  29 #endif
  30
  31 #ifndef WX_PRECOMP
  32 #include "wx/wx.h"
  33 #endif
  34
  35 #include "wx/log.h"
  36 #include "wx/module.h"
  37 #include "game.h"
  38
  39 #include <string.h>           // for memset
  40
  41
  42 #define ARRAYSIZE  1024       // static array for BeginFind & co.
  43 #define ALLOCBOXES 16         // number of cellboxes to alloc at once
  44 #define MAXDEAD    8          // tics before removing cellbox from list
  45
  46
  47 // ==========================================================================
  48 // CellBox
  49 // ==========================================================================
  50
  51 #define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f)
  52
  53 #define HASHSIZE   16384      // hash table size (do not change!)
  54 #define CELLBOX    8          // cells in a cellbox (do not change!)
  55
  56
  57 class LifeCellBox
  58 {
  59 public:
  60     // members
  61     inline bool IsAlive(int dx, int dy) const;
  62     inline bool SetCell(int dx, int dy, bool alive);
  63
  64     // attributes
  65     wxInt32       m_x, m_y;                     // position in universe
  66     wxUint32      m_live1, m_live2;             // alive cells (1 bit per cell)
  67     wxUint32      m_old1, m_old2;               // old values for m_live1, 2
  68     wxUint32      m_on[8];                      // neighbouring info
  69     wxUint32      m_dead;                       // been dead for n generations
  70     LifeCellBox  *m_up, *m_dn, *m_lf, *m_rt;    // neighbour CellBoxes
  71     LifeCellBox  *m_prev, *m_next;              // in linked list
  72     LifeCellBox  *m_hprev, *m_hnext;            // in hash table
  73 };
  74
  75
  76 // IsAlive:
  77 //  Returns whether cell dx, dy in this box is alive
  78 //
  79 bool LifeCellBox::IsAlive(int dx, int dy) const
  80 {
  81     if (dy > 3)
  82         return (m_live2 & 1 << ((dy - 4) * 8 + dx));
  83     else
  84         return (m_live1 & 1 << ((dy) * 8 + dx));
  85 }
  86
  87 // SetCell:
  88 //  Sets cell dx, dy in this box to 'alive', returns TRUE if
  89 //  the previous value was different, FALSE if it was the same.
  90 //
  91 bool LifeCellBox::SetCell(int dx, int dy, bool alive)
  92 {
  93     if (IsAlive(dx, dy) != alive)
  94     {
  95        if (dy > 3)
  96            m_live2 ^= 1 << ((dy - 4) * 8 + dx);
  97        else
  98            m_live1 ^= 1 << ((dy) * 8 + dx);
  99
 100        // reset this here to avoid updating problems
 101        m_dead = 0;
 102
 103        return TRUE;
 104     }
 105     else
 106        return FALSE;
 107 }
 108
 109
 110 // ==========================================================================
 111 // Life
 112 // ==========================================================================
 113
 114 // --------------------------------------------------------------------------
 115 // Ctor and dtor
 116 // --------------------------------------------------------------------------
 117
 118 Life::Life()
 119 {
 120     // pattern description
 121     m_name        = _("");
 122     m_rules       = _("");
 123     m_description = _("");
 124
 125     // pattern data
 126     m_numcells    = 0;
 127     m_boxes       = new LifeCellBox *[HASHSIZE];
 128     m_head        = NULL;
 129     m_available   = NULL;
 130     for (int i = 0; i < HASHSIZE; i++)
 131         m_boxes[i] = NULL;
 132
 133     // state vars for BeginFind & FindMore
 134     m_cells       = new LifeCell[ARRAYSIZE];
 135     m_ncells      = 0;
 136     m_findmore    = FALSE;
 137     m_changed     = FALSE;
 138 }
 139
 140 Life::~Life()
 141 {
 142     Clear();
 143
 144     delete[] m_boxes;
 145     delete[] m_cells;
 146 }
 147
 148 // Clear:
 149 //  Clears the board, freeing all storage.
 150 //
 151 void Life::Clear()
 152 {
 153     LifeCellBox *c, *nc;
 154
 155     // clear the hash table pointers
 156     for (int i = 0; i < HASHSIZE; i++)
 157         m_boxes[i] = NULL;
 158
 159     // free used boxes
 160     c = m_head;
 161     while (c)
 162     {
 163         nc = c->m_next;
 164         delete c;
 165         c = nc;
 166     }
 167     m_head = NULL;
 168
 169     // free available boxes
 170     c = m_available;
 171     while (c)
 172     {
 173         nc = c->m_next;
 174         delete c;
 175         c = nc;
 176     }
 177     m_available = NULL;
 178
 179     // reset state
 180     m_name        = _("");
 181     m_rules       = _("");
 182     m_description = _("");
 183     m_numcells    = 0;
 184 }
 185
 186 // --------------------------------------------------------------------------
 187 // Test and set individual cells
 188 // --------------------------------------------------------------------------
 189
 190 // IsAlive:
 191 //  Returns whether cell (x, y) is alive.
 192 //
 193 bool Life::IsAlive(wxInt32 x, wxInt32 y)
 194 {
 195     LifeCellBox *c = LinkBox(x, y, FALSE);
 196
 197     return (c && c->IsAlive( x - c->m_x, y - c->m_y ));
 198 }
 199
 200 // SetCell:
 201 //  Sets or clears cell (x, y), according to the 'alive' param.
 202 //
 203 void Life::SetCell(wxInt32 x, wxInt32 y, bool alive)
 204 {
 205     LifeCellBox *c  = LinkBox(x, y);
 206     wxUint32 dx = x - c->m_x;
 207     wxUint32 dy = y - c->m_y;
 208
 209     if (c->SetCell(dx, dy, alive))
 210     {
 211         if (alive)
 212             m_numcells++;
 213         else
 214             m_numcells--;
 215     }
 216 }
 217
 218 void Life::SetPattern(const LifePattern& pattern)
 219 {
 220     wxArrayString data = pattern.m_shape;
 221     wxString line;
 222     long x = 0,
 223          y = 0;
 224
 225     Clear();
 226     for (size_t n = 0; n < data.GetCount(); n++)
 227     {
 228         line = data[n];
 229
 230         if ( (line.GetChar(0) != wxT('*')) &&
 231              (line.GetChar(0) != wxT('.')) )
 232         {
 233             // assume that it is a digit or a minus sign
 234             line.BeforeFirst(wxT(' ')).ToLong(&x);
 235             line.AfterFirst(wxT(' ')).ToLong(&y);
 236         }
 237         else
 238         {
 239             // pattern data
 240             for (size_t k = 0; k < line.Len(); k++)
 241                 SetCell(x + k, y, line.GetChar(k) == wxT('*'));
 242
 243             y++;
 244         }
 245     }
 246
 247     m_name = pattern.m_name;
 248     m_rules = pattern.m_rules;
 249     m_description = pattern.m_description;
 250 }
 251
 252 // --------------------------------------------------------------------------
 253 // Cellbox management functions
 254 // --------------------------------------------------------------------------
 255
 256 // CreateBox:
 257 //  Creates a box in x, y, either taking it from the list
 258 //  of available boxes, or allocating a new one.
 259 //
 260 LifeCellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv)
 261 {
 262     LifeCellBox *c;
 263
 264     // if there are no available boxes, alloc a few more
 265     if (!m_available)
 266         for (int i = 1; i <= ALLOCBOXES; i++)
 267         {
 268             c = new LifeCellBox();
 269
 270             if (!c)
 271             {
 272                 // TODO: handle memory errors. Note that right now, if we
 273                 // couldn't allocate at least one cellbox, we will crash
 274                 // before leaving CreateBox(). Probably we should try to
 275                 // allocate some boxes *before* the m_available list goes
 276                 // empty, so that we have a margin to handle errors
 277                 // gracefully.
 278                 wxLogFatalError(_("Out of memory! Aborting..."));
 279
 280                 // NOTREACHED
 281             }
 282
 283             c->m_next = m_available;
 284             m_available = c;
 285         }
 286
 287     // take a cellbox from the list of available boxes
 288     c = m_available;
 289     m_available = c->m_next;
 290
 291     // reset everything
 292     memset((void *) c, 0, sizeof(LifeCellBox));
 293     c->m_x = x;
 294     c->m_y = y;
 295
 296     // insert c in the list
 297     c->m_next = m_head;
 298     m_head = c;
 299     if (c->m_next) c->m_next->m_prev = c;
 300
 301     // insert c in the hash table
 302     c->m_hnext = m_boxes[hv];
 303     m_boxes[hv] = c;
 304     if (c->m_hnext) c->m_hnext->m_hprev = c;
 305
 306     return c;
 307 }
 308
 309 // LinkBox:
 310 //  Returns a pointer to the box (x, y); if it didn't exist yet,
 311 //  it returns NULL or creates a new one, depending on the value
 312 //  of the 'create' parameter.
 313 //
 314 LifeCellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create)
 315 {
 316     wxUint32 hv;
 317     LifeCellBox *c;
 318
 319     x &= 0xfffffff8;
 320     y &= 0xfffffff8;
 321     hv = HASH(x, y);
 322
 323     // search in the hash table
 324     for (c = m_boxes[hv]; c; c = c->m_hnext)
 325         if ((c->m_x == x) && (c->m_y == y)) return c;
 326
 327     // if not found, and (create == TRUE), create a new one
 328     return create? CreateBox(x, y, hv) : (LifeCellBox*) NULL;
 329 }
 330
 331 // KillBox:
 332 //  Removes this box from the list and the hash table and
 333 //  puts it in the list of available boxes.
 334 //
 335 void Life::KillBox(LifeCellBox *c)
 336 {
 337     wxUint32 hv = HASH(c->m_x, c->m_y);
 338
 339     // remove from the list
 340     if (c != m_head)
 341         c->m_prev->m_next = c->m_next;
 342     else
 343         m_head = c->m_next;
 344
 345     // remove from the hash table
 346     if (c != m_boxes[hv])
 347         c->m_hprev->m_hnext = c->m_hnext;
 348     else
 349         m_boxes[hv] = c->m_hnext;
 350
 351     // update neighbours
 352     if (c->m_next) c->m_next->m_prev = c->m_prev;
 353     if (c->m_hnext) c->m_hnext->m_hprev = c->m_hprev;
 354     if (c->m_up) c->m_up->m_dn = NULL;
 355     if (c->m_dn) c->m_dn->m_up = NULL;
 356     if (c->m_lf) c->m_lf->m_rt = NULL;
 357     if (c->m_rt) c->m_rt->m_lf = NULL;
 358
 359     // append to the list of available boxes
 360     c->m_next = m_available;
 361     m_available = c;
 362 }
 363
 364 // --------------------------------------------------------------------------
 365 // Navigation
 366 // --------------------------------------------------------------------------
 367
 368 LifeCell Life::FindCenter()
 369 {
 370     double sx, sy;
 371     int n;
 372     sx = 0.0;
 373     sy = 0.0;
 374     n = 0;
 375
 376     LifeCellBox *c;
 377     for (c = m_head; c; c = c->m_next)
 378         if (!c->m_dead)
 379         {
 380             sx += c->m_x;
 381             sy += c->m_y;
 382             n++;
 383         }
 384
 385     if (n > 0)
 386     {
 387         sx = (sx / n) + CELLBOX / 2;
 388         sy = (sy / n) + CELLBOX / 2;
 389     }
 390
 391     LifeCell cell;
 392     cell.i = (wxInt32) sx;
 393     cell.j = (wxInt32) sy;
 394     return cell;
 395 }
 396
 397 LifeCell Life::FindNorth()
 398 {
 399     wxInt32 x = 0, y = 0;
 400     bool first = TRUE;
 401
 402     LifeCellBox *c;
 403     for (c = m_head; c; c = c->m_next)
 404         if (!c->m_dead && ((first) || (c->m_y < y)))
 405         {
 406             x = c->m_x;
 407             y = c->m_y;
 408             first = FALSE;
 409         }
 410
 411     LifeCell cell;
 412     cell.i = first? 0 : x + CELLBOX / 2;
 413     cell.j = first? 0 : y + CELLBOX / 2;
 414     return cell;
 415 }
 416
 417 LifeCell Life::FindSouth()
 418 {
 419     wxInt32 x = 0, y = 0;
 420     bool first = TRUE;
 421
 422     LifeCellBox *c;
 423     for (c = m_head; c; c = c->m_next)
 424         if (!c->m_dead && ((first) || (c->m_y > y)))
 425         {
 426             x = c->m_x;
 427             y = c->m_y;
 428             first = FALSE;
 429         }
 430
 431     LifeCell cell;
 432     cell.i = first? 0 : x + CELLBOX / 2;
 433     cell.j = first? 0 : y + CELLBOX / 2;
 434     return cell;
 435 }
 436
 437 LifeCell Life::FindWest()
 438 {
 439     wxInt32 x = 0, y = 0;
 440     bool first = TRUE;
 441
 442     LifeCellBox *c;
 443     for (c = m_head; c; c = c->m_next)
 444         if (!c->m_dead && ((first) || (c->m_x < x)))
 445         {
 446             x = c->m_x;
 447             y = c->m_y;
 448             first = FALSE;
 449         }
 450
 451     LifeCell cell;
 452     cell.i = first? 0 : x + CELLBOX / 2;
 453     cell.j = first? 0 : y + CELLBOX / 2;
 454     return cell;
 455 }
 456
 457 LifeCell Life::FindEast()
 458 {
 459     wxInt32 x = 0, y = 0;
 460     bool first = TRUE;
 461
 462     LifeCellBox *c;
 463     for (c = m_head; c; c = c->m_next)
 464         if (!c->m_dead && ((first) || (c->m_x > x)))
 465         {
 466             x = c->m_x;
 467             y = c->m_y;
 468             first = FALSE;
 469         }
 470
 471     LifeCell cell;
 472     cell.i = first? 0 : x + CELLBOX / 2;
 473     cell.j = first? 0 : y + CELLBOX / 2;
 474     return cell;
 475 }
 476
 477 // --------------------------------------------------------------------------
 478 // FindMore & co.
 479 // --------------------------------------------------------------------------
 480
 481 // DoLine:
 482 //  Post eight cells to the cell arrays - leave out the fourth
 483 //  argument (or pass 0, the default value) to post alive cells
 484 //  only, else it will post cells which have changed.
 485 //
 486 void Life::DoLine(wxInt32 x, wxInt32 y, wxUint32 live, wxUint32 old)
 487 {
 488     wxUint32 diff = (live ^ old) & 0xff;
 489
 490     if (!diff) return;
 491
 492     for (wxInt32 k = 8; k; k--, x++)
 493     {
 494         if (diff & 0x01)
 495         {
 496             m_cells[m_ncells].i = x;
 497             m_cells[m_ncells].j = y;
 498             m_ncells++;
 499         }
 500         diff >>= 1;
 501     }
 502 }
 503
 504 void Life::BeginFind(wxInt32 x0, wxInt32 y0, wxInt32 x1, wxInt32 y1, bool changed)
 505 {
 506     // TODO: optimize for the case where the maximum number of
 507     // cellboxes that fit in the specified viewport is smaller
 508     // than the current total of boxes; iterating over the list
 509     // should then be faster than searching in the hash table.
 510
 511     m_x0 = m_x = x0 & 0xfffffff8;
 512     m_y0 = m_y = y0 & 0xfffffff8;
 513     m_x1 = (x1 + 7) & 0xfffffff8;
 514     m_y1 = (y1 + 7) & 0xfffffff8;
 515
 516     m_findmore = TRUE;
 517     m_changed = changed;
 518 }
 519
 520 bool Life::FindMore(LifeCell *cells[], size_t *ncells)
 521 {
 522     LifeCellBox *c;
 523     *cells = m_cells;
 524     m_ncells = 0;
 525
 526     if (m_changed)
 527     {
 528         for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0)
 529             for ( ; m_x <= m_x1; m_x += 8)
 530             {
 531                 if ((c = LinkBox(m_x, m_y, FALSE)) == NULL)
 532                     continue;
 533
 534                 // check whether there is enough space left in the array
 535                 if (m_ncells > (ARRAYSIZE - 64))
 536                 {
 537                     *ncells = m_ncells;
 538                     return FALSE;
 539                 }
 540
 541                 DoLine(m_x, m_y    , c->m_live1,       c->m_old1      );
 542                 DoLine(m_x, m_y + 1, c->m_live1 >> 8,  c->m_old1 >> 8 );
 543                 DoLine(m_x, m_y + 2, c->m_live1 >> 16, c->m_old1 >> 16);
 544                 DoLine(m_x, m_y + 3, c->m_live1 >> 24, c->m_old1 >> 24);
 545                 DoLine(m_x, m_y + 4, c->m_live2,       c->m_old2      );
 546                 DoLine(m_x, m_y + 5, c->m_live2 >> 8,  c->m_old2 >> 8 );
 547                 DoLine(m_x, m_y + 6, c->m_live2 >> 16, c->m_old2 >> 16);
 548                 DoLine(m_x, m_y + 7, c->m_live2 >> 24, c->m_old2 >> 24);
 549             }
 550     }
 551     else
 552     {
 553         for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0)
 554             for ( ; m_x <= m_x1; m_x += 8)
 555             {
 556                 if ((c = LinkBox(m_x, m_y, FALSE)) == NULL)
 557                     continue;
 558
 559                 // check whether there is enough space left in the array
 560                 if (m_ncells > (ARRAYSIZE - 64))
 561                 {
 562                     *ncells = m_ncells;
 563                     return FALSE;
 564                 }
 565
 566                 DoLine(m_x, m_y    , c->m_live1      );
 567                 DoLine(m_x, m_y + 1, c->m_live1 >> 8 );
 568                 DoLine(m_x, m_y + 2, c->m_live1 >> 16);
 569                 DoLine(m_x, m_y + 3, c->m_live1 >> 24);
 570                 DoLine(m_x, m_y + 4, c->m_live2      );
 571                 DoLine(m_x, m_y + 5, c->m_live2 >> 8 );
 572                 DoLine(m_x, m_y + 6, c->m_live2 >> 16);
 573                 DoLine(m_x, m_y + 7, c->m_live2 >> 24);
 574             }
 575     }
 576
 577     *ncells = m_ncells;
 578     m_findmore = FALSE;
 579     return TRUE;
 580 }
 581
 582 // --------------------------------------------------------------------------
 583 // Evolution engine
 584 // --------------------------------------------------------------------------
 585
 586 extern unsigned char *g_tab;
 587 extern int g_tab1[];
 588 extern int g_tab2[];
 589
 590 // NextTic:
 591 //  Advance one step in evolution :-)
 592 //
 593 bool Life::NextTic()
 594 {
 595     LifeCellBox  *c, *up, *dn, *lf, *rt;
 596     wxUint32 t1, t2, t3, t4;
 597     bool     changed = FALSE;
 598
 599     m_numcells = 0;
 600
 601     // Stage 1:
 602     // Compute neighbours of each cell
 603     //
 604     // WARNING: unrolled loops and lengthy code follows!
 605     //
 606     c = m_head;
 607
 608     while (c)
 609     {
 610         if (! (c->m_live1 || c->m_live2))
 611         {
 612             c = c->m_next;
 613             continue;
 614         }
 615         up = c->m_up;
 616         dn = c->m_dn;
 617         lf = c->m_lf;
 618         rt = c->m_rt;
 619
 620         // up
 621         t1 = c->m_live1 & 0x000000ff;
 622         if (t1)
 623         {
 624             if (!up)
 625             {
 626                 up = LinkBox(c->m_x, c->m_y - 8);
 627                 up->m_dn = c;
 628             }
 629             t2 = g_tab1[t1];
 630             up->m_on[7] += t2;
 631             c->m_on[1] += t2;
 632             c->m_on[0] += g_tab2[t1];
 633         }
 634
 635         // down
 636         t1 = (c->m_live2 & 0xff000000) >> 24;
 637         if (t1)
 638         {
 639             if (!dn)
 640             {
 641                 dn = LinkBox(c->m_x, c->m_y + 8);
 642                 dn->m_up = c;
 643             }
 644             t2 = g_tab1[t1];
 645             dn->m_on[0] += t2;
 646             c->m_on[6] += t2;
 647             c->m_on[7] += g_tab2[t1];
 648         }
 649
 650         t1 = c->m_live1;
 651         t2 = c->m_live2;
 652
 653         // left
 654         if (t1 & 0x01010101)
 655         {
 656             if (!lf)
 657             {
 658                 lf = LinkBox(c->m_x - 8, c->m_y);
 659                 lf->m_rt = c;
 660             }
 661             if (t1 & 0x00000001)
 662             {
 663                if (!lf->m_up)
 664                {
 665                    lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8);
 666                    lf->m_up->m_dn = lf;
 667                }
 668                lf->m_up->m_on[7] += 0x10000000;
 669                lf->m_on[0] += 0x10000000;
 670                lf->m_on[1] += 0x10000000;
 671             }
 672             if (t1 & 0x00000100)
 673             {
 674                lf->m_on[0] += 0x10000000;
 675                lf->m_on[1] += 0x10000000;
 676                lf->m_on[2] += 0x10000000;
 677             }
 678             if (t1 & 0x00010000)
 679             {
 680                lf->m_on[1] += 0x10000000;
 681                lf->m_on[2] += 0x10000000;
 682                lf->m_on[3] += 0x10000000;
 683             }
 684             if (t1 & 0x01000000)
 685             {
 686                lf->m_on[2] += 0x10000000;
 687                lf->m_on[3] += 0x10000000;
 688                lf->m_on[4] += 0x10000000;
 689             }
 690         }
 691         if (t2 & 0x01010101)
 692         {
 693             if (!lf)
 694             {
 695                 lf = LinkBox(c->m_x - 8, c->m_y);
 696                 lf->m_rt = c;
 697             }
 698             if (t2 & 0x00000001)
 699             {
 700                lf->m_on[3] += 0x10000000;
 701                lf->m_on[4] += 0x10000000;
 702                lf->m_on[5] += 0x10000000;
 703             }
 704             if (t2 & 0x00000100)
 705             {
 706                lf->m_on[4] += 0x10000000;
 707                lf->m_on[5] += 0x10000000;
 708                lf->m_on[6] += 0x10000000;
 709             }
 710             if (t2 & 0x00010000)
 711             {
 712                lf->m_on[5] += 0x10000000;
 713                lf->m_on[6] += 0x10000000;
 714                lf->m_on[7] += 0x10000000;
 715             }
 716             if (t2 & 0x01000000)
 717             {
 718                if (!lf->m_dn)
 719                {
 720                    lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8);
 721                    lf->m_dn->m_up = lf;
 722                }
 723                lf->m_on[6] += 0x10000000;
 724                lf->m_on[7] += 0x10000000;
 725                lf->m_dn->m_on[0] += 0x10000000;
 726             }
 727         }
 728
 729         // right
 730         if (t1 & 0x80808080)
 731         {
 732             if (!rt)
 733             {
 734                 rt = LinkBox(c->m_x + 8, c->m_y);
 735                 rt->m_lf = c;
 736             }
 737             if (t1 & 0x00000080)
 738             {
 739                if (!rt->m_up)
 740                {
 741                    rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8);
 742                    rt->m_up->m_dn = rt;
 743                }
 744                rt->m_up->m_on[7] += 0x00000001;
 745                rt->m_on[0] += 0x00000001;
 746                rt->m_on[1] += 0x00000001;
 747             }
 748             if (t1 & 0x00008000)
 749             {
 750                rt->m_on[0] += 0x00000001;
 751                rt->m_on[1] += 0x00000001;
 752                rt->m_on[2] += 0x00000001;
 753             }
 754             if (t1 & 0x00800000)
 755             {
 756                rt->m_on[1] += 0x00000001;
 757                rt->m_on[2] += 0x00000001;
 758                rt->m_on[3] += 0x00000001;
 759             }
 760             if (t1 & 0x80000000)
 761             {
 762                rt->m_on[2] += 0x00000001;
 763                rt->m_on[3] += 0x00000001;
 764                rt->m_on[4] += 0x00000001;
 765             }
 766         }
 767         if (t2 & 0x80808080)
 768         {
 769             if (!rt)
 770             {
 771                 rt = LinkBox(c->m_x + 8, c->m_y);
 772                 rt->m_lf = c;
 773             }
 774             if (t2 & 0x00000080)
 775             {
 776                rt->m_on[3] += 0x00000001;
 777                rt->m_on[4] += 0x00000001;
 778                rt->m_on[5] += 0x00000001;
 779             }
 780             if (t2 & 0x00008000)
 781             {
 782                rt->m_on[4] += 0x00000001;
 783                rt->m_on[5] += 0x00000001;
 784                rt->m_on[6] += 0x00000001;
 785             }
 786             if (t2 & 0x00800000)
 787             {
 788                rt->m_on[5] += 0x00000001;
 789                rt->m_on[6] += 0x00000001;
 790                rt->m_on[7] += 0x00000001;
 791             }
 792             if (t2 & 0x80000000)
 793             {
 794                if (!rt->m_dn)
 795                {
 796                    rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8);
 797                    rt->m_dn->m_up = rt;
 798                }
 799                rt->m_on[6] += 0x00000001;
 800                rt->m_on[7] += 0x00000001;
 801                rt->m_dn->m_on[0] += 0x00000001;
 802             }
 803         }
 804
 805         // inner cells
 806         int i;
 807         for (i = 1; i <= 3; i++)
 808         {
 809             t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff;
 810             if (t1)
 811             {
 812                 c->m_on[i - 1] += g_tab1[t1];
 813                 c->m_on[i    ] += g_tab2[t1];
 814                 c->m_on[i + 1] += g_tab1[t1];
 815             }
 816         }
 817         for (i = 0; i <= 2; i++)
 818         {
 819             t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff;
 820             if (t1)
 821             {
 822                 c->m_on[i + 3] += g_tab1[t1];
 823                 c->m_on[i + 4] += g_tab2[t1];
 824                 c->m_on[i + 5] += g_tab1[t1];
 825             }
 826         }
 827
 828         c->m_up = up;
 829         c->m_dn = dn;
 830         c->m_lf = lf;
 831         c->m_rt = rt;
 832         c = c->m_next;
 833     }
 834
 835     // Stage 2:
 836     // Stabilize
 837     //
 838     c = m_head;
 839
 840     while (c)
 841     {
 842         t1 = 0;
 843         t2 = 0;
 844
 845         t3 = c->m_live1;
 846         c->m_old1 = t3;
 847
 848         t4 = c->m_on[0];
 849         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3      ) & 0xf) ];
 850         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
 851         t4 = c->m_on[1];
 852         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
 853         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
 854         t4 = c->m_on[2];
 855         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
 856         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
 857         t4 = c->m_on[3];
 858         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
 859         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
 860
 861         t3 = c->m_live2;
 862         c->m_old2 = t3;
 863
 864         t4 = c->m_on[4];
 865         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3      ) & 0xf) ];
 866         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
 867         t4 = c->m_on[5];
 868         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
 869         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
 870         t4 = c->m_on[6];
 871         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
 872         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
 873         t4 = c->m_on[7];
 874         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
 875         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
 876
 877         c->m_on[0] = c->m_on[1] = c->m_on[2] = c->m_on[3] =
 878         c->m_on[4] = c->m_on[5] = c->m_on[6] = c->m_on[7] = 0;
 879         c->m_live1 = t1;
 880         c->m_live2 = t2;
 881
 882         // count alive cells
 883 #if 1
 884         wxUint32 t1_, t2_;
 885
 886         t1_ = (t1  & 0x55555555) + (t1  >> 1 & 0x55555555);
 887         t1_ = (t1_ & 0x33333333) + (t1_ >> 2 & 0x33333333);
 888
 889         t2_ = (t2  & 0x55555555) + (t2  >> 1 & 0x55555555);
 890         t2_ = (t2_ & 0x33333333) + (t2_ >> 2 & 0x33333333) + t1_;
 891         t2_ = (t2_ & 0x0F0F0F0F) + (t2_ >> 4 & 0x0F0F0F0F);
 892         t2_ = (t2_ & 0x00FF00FF) + (t2_ >> 8 & 0x00FF00FF);
 893
 894         m_numcells += (t2_ & 0xFF) + (t2_ >> 16 & 0xFF);
 895 #else
 896         // Original, slower code
 897         for (int i = 0; i < 32; i++)
 898         {
 899             if (t1 & (1 << i)) m_numcells++;
 900             if (t2 & (1 << i)) m_numcells++;
 901         }
 902 #endif
 903
 904         changed |= ((t1 ^ c->m_old1) || (t2 ^ c->m_old2));
 905
 906         // mark, and discard if necessary, dead boxes
 907         if (t1 || t2)
 908         {
 909             c->m_dead = 0;
 910             c = c->m_next;
 911         }
 912         else
 913         {
 914             LifeCellBox *aux = c->m_next;
 915             if (c->m_dead++ > MAXDEAD)
 916                KillBox(c);
 917
 918             c = aux;
 919         }
 920     }
 921
 922     return changed;
 923 }
 924
 925 // ==========================================================================
 926 // LifeModule
 927 // ==========================================================================
 928
 929 // A module to pregenerate lookup tables without having to do it
 930 // from the application.
 931
 932 class LifeModule: public wxModule
 933 {
 934 DECLARE_DYNAMIC_CLASS(LifeModule)
 935
 936 public:
 937     LifeModule() {};
 938     bool OnInit();
 939     void OnExit();
 940 };
 941
 942 IMPLEMENT_DYNAMIC_CLASS(LifeModule, wxModule)
 943
 944 bool LifeModule::OnInit()
 945 {
 946     // see below
 947     g_tab = new unsigned char [0xfffff];
 948
 949     if (!g_tab) return FALSE;
 950
 951     for (wxUint32 i = 0; i < 0xfffff; i++)
 952     {
 953         wxUint32 val  = i >> 4;
 954         wxUint32 old  = i & 0x0000f;
 955         wxUint32 live = 0;
 956
 957         for (int j = 0; j < 4; j++)
 958         {
 959             live >>= 1;
 960
 961             if (((val & 0xf) == 3) || (((val & 0xf) == 2) && (old & 0x1)))
 962                 live |= 0x8;
 963
 964             old >>= 1;
 965             val >>= 4;
 966         }
 967
 968         g_tab[i] = (unsigned char) live;
 969     }
 970
 971     return TRUE;
 972 }
 973
 974 void LifeModule::OnExit()
 975 {
 976     delete [] g_tab;
 977 }
 978
 979
 980 // This table converts from number of neighbors (like in on[]) to
 981 // bits, for a set of four cells. It takes as index a five-digit
 982 // hexadecimal value (0xNNNNB) where Ns hold number of neighbors
 983 // for each cell and B holds their previous state.
 984 //
 985 unsigned char *g_tab;
 986
 987 // This table converts from bits (like in live1, live2) to number
 988 // of neighbors for each cell in the upper or lower row.
 989 //
 990 int g_tab1[]=
 991 {
 992     0x00000000,
 993     0x00000011,
 994     0x00000111,
 995     0x00000122,
 996     0x00001110,
 997     0x00001121,
 998     0x00001221,
 999     0x00001232,
1000     0x00011100,
1001     0x00011111,
1002     0x00011211,
1003     0x00011222,
1004     0x00012210,
1005     0x00012221,
1006     0x00012321,
1007     0x00012332,
1008     0x00111000,
1009     0x00111011,
1010     0x00111111,
1011     0x00111122,
1012     0x00112110,
1013     0x00112121,
1014     0x00112221,
1015     0x00112232,
1016     0x00122100,
1017     0x00122111,
1018     0x00122211,
1019     0x00122222,
1020     0x00123210,
1021     0x00123221,
1022     0x00123321,
1023     0x00123332,
1024     0x01110000,
1025     0x01110011,
1026     0x01110111,
1027     0x01110122,
1028     0x01111110,
1029     0x01111121,
1030     0x01111221,
1031     0x01111232,
1032     0x01121100,
1033     0x01121111,
1034     0x01121211,
1035     0x01121222,
1036     0x01122210,
1037     0x01122221,
1038     0x01122321,
1039     0x01122332,
1040     0x01221000,
1041     0x01221011,
1042     0x01221111,
1043     0x01221122,
1044     0x01222110,
1045     0x01222121,
1046     0x01222221,
1047     0x01222232,
1048     0x01232100,
1049     0x01232111,
1050     0x01232211,
1051     0x01232222,
1052     0x01233210,
1053     0x01233221,
1054     0x01233321,
1055     0x01233332,
1056     0x11100000,
1057     0x11100011,
1058     0x11100111,
1059     0x11100122,
1060     0x11101110,
1061     0x11101121,
1062     0x11101221,
1063     0x11101232,
1064     0x11111100,
1065     0x11111111,
1066     0x11111211,
1067     0x11111222,
1068     0x11112210,
1069     0x11112221,
1070     0x11112321,
1071     0x11112332,
1072     0x11211000,
1073     0x11211011,
1074     0x11211111,
1075     0x11211122,
1076     0x11212110,
1077     0x11212121,
1078     0x11212221,
1079     0x11212232,
1080     0x11222100,
1081     0x11222111,
1082     0x11222211,
1083     0x11222222,
1084     0x11223210,
1085     0x11223221,
1086     0x11223321,
1087     0x11223332,
1088     0x12210000,
1089     0x12210011,
1090     0x12210111,
1091     0x12210122,
1092     0x12211110,
1093     0x12211121,
1094     0x12211221,
1095     0x12211232,
1096     0x12221100,
1097     0x12221111,
1098     0x12221211,
1099     0x12221222,
1100     0x12222210,
1101     0x12222221,
1102     0x12222321,
1103     0x12222332,
1104     0x12321000,
1105     0x12321011,
1106     0x12321111,
1107     0x12321122,
1108     0x12322110,
1109     0x12322121,
1110     0x12322221,
1111     0x12322232,
1112     0x12332100,
1113     0x12332111,
1114     0x12332211,
1115     0x12332222,
1116     0x12333210,
1117     0x12333221,
1118     0x12333321,
1119     0x12333332,
1120     0x11000000,
1121     0x11000011,
1122     0x11000111,
1123     0x11000122,
1124     0x11001110,
1125     0x11001121,
1126     0x11001221,
1127     0x11001232,
1128     0x11011100,
1129     0x11011111,
1130     0x11011211,
1131     0x11011222,
1132     0x11012210,
1133     0x11012221,
1134     0x11012321,
1135     0x11012332,
1136     0x11111000,
1137     0x11111011,
1138     0x11111111,
1139     0x11111122,
1140     0x11112110,
1141     0x11112121,
1142     0x11112221,
1143     0x11112232,
1144     0x11122100,
1145     0x11122111,
1146     0x11122211,
1147     0x11122222,
1148     0x11123210,
1149     0x11123221,
1150     0x11123321,
1151     0x11123332,
1152     0x12110000,
1153     0x12110011,
1154     0x12110111,
1155     0x12110122,
1156     0x12111110,
1157     0x12111121,
1158     0x12111221,
1159     0x12111232,
1160     0x12121100,
1161     0x12121111,
1162     0x12121211,
1163     0x12121222,
1164     0x12122210,
1165     0x12122221,
1166     0x12122321,
1167     0x12122332,
1168     0x12221000,
1169     0x12221011,
1170     0x12221111,
1171     0x12221122,
1172     0x12222110,
1173     0x12222121,
1174     0x12222221,
1175     0x12222232,
1176     0x12232100,
1177     0x12232111,
1178     0x12232211,
1179     0x12232222,
1180     0x12233210,
1181     0x12233221,
1182     0x12233321,
1183     0x12233332,
1184     0x22100000,
1185     0x22100011,
1186     0x22100111,
1187     0x22100122,
1188     0x22101110,
1189     0x22101121,
1190     0x22101221,
1191     0x22101232,
1192     0x22111100,
1193     0x22111111,
1194     0x22111211,
1195     0x22111222,
1196     0x22112210,
1197     0x22112221,
1198     0x22112321,
1199     0x22112332,
1200     0x22211000,
1201     0x22211011,
1202     0x22211111,
1203     0x22211122,
1204     0x22212110,
1205     0x22212121,
1206     0x22212221,
1207     0x22212232,
1208     0x22222100,
1209     0x22222111,
1210     0x22222211,
1211     0x22222222,
1212     0x22223210,
1213     0x22223221,
1214     0x22223321,
1215     0x22223332,
1216     0x23210000,
1217     0x23210011,
1218     0x23210111,
1219     0x23210122,
1220     0x23211110,
1221     0x23211121,
1222     0x23211221,
1223     0x23211232,
1224     0x23221100,
1225     0x23221111,
1226     0x23221211,
1227     0x23221222,
1228     0x23222210,
1229     0x23222221,
1230     0x23222321,
1231     0x23222332,
1232     0x23321000,
1233     0x23321011,
1234     0x23321111,
1235     0x23321122,
1236     0x23322110,
1237     0x23322121,
1238     0x23322221,
1239     0x23322232,
1240     0x23332100,
1241     0x23332111,
1242     0x23332211,
1243     0x23332222,
1244     0x23333210,
1245     0x23333221,
1246     0x23333321,
1247     0x23333332
1248 };
1249
1250 // This table converts from bits (like in live1, live2) to number
1251 // of neighbors for each cell in the same row (excluding ourselves)
1252 //
1253 int g_tab2[]=
1254 {
1255     0x00000000,
1256     0x00000010,
1257     0x00000101,
1258     0x00000111,
1259     0x00001010,
1260     0x00001020,
1261     0x00001111,
1262     0x00001121,
1263     0x00010100,
1264     0x00010110,
1265     0x00010201,
1266     0x00010211,
1267     0x00011110,
1268     0x00011120,
1269     0x00011211,
1270     0x00011221,
1271     0x00101000,
1272     0x00101010,
1273     0x00101101,
1274     0x00101111,
1275     0x00102010,
1276     0x00102020,
1277     0x00102111,
1278     0x00102121,
1279     0x00111100,
1280     0x00111110,
1281     0x00111201,
1282     0x00111211,
1283     0x00112110,
1284     0x00112120,
1285     0x00112211,
1286     0x00112221,
1287     0x01010000,
1288     0x01010010,
1289     0x01010101,
1290     0x01010111,
1291     0x01011010,
1292     0x01011020,
1293     0x01011111,
1294     0x01011121,
1295     0x01020100,
1296     0x01020110,
1297     0x01020201,
1298     0x01020211,
1299     0x01021110,
1300     0x01021120,
1301     0x01021211,
1302     0x01021221,
1303     0x01111000,
1304     0x01111010,
1305     0x01111101,
1306     0x01111111,
1307     0x01112010,
1308     0x01112020,
1309     0x01112111,
1310     0x01112121,
1311     0x01121100,
1312     0x01121110,
1313     0x01121201,
1314     0x01121211,
1315     0x01122110,
1316     0x01122120,
1317     0x01122211,
1318     0x01122221,
1319     0x10100000,
1320     0x10100010,
1321     0x10100101,
1322     0x10100111,
1323     0x10101010,
1324     0x10101020,
1325     0x10101111,
1326     0x10101121,
1327     0x10110100,
1328     0x10110110,
1329     0x10110201,
1330     0x10110211,
1331     0x10111110,
1332     0x10111120,
1333     0x10111211,
1334     0x10111221,
1335     0x10201000,
1336     0x10201010,
1337     0x10201101,
1338     0x10201111,
1339     0x10202010,
1340     0x10202020,
1341     0x10202111,
1342     0x10202121,
1343     0x10211100,
1344     0x10211110,
1345     0x10211201,
1346     0x10211211,
1347     0x10212110,
1348     0x10212120,
1349     0x10212211,
1350     0x10212221,
1351     0x11110000,
1352     0x11110010,
1353     0x11110101,
1354     0x11110111,
1355     0x11111010,
1356     0x11111020,
1357     0x11111111,
1358     0x11111121,
1359     0x11120100,
1360     0x11120110,
1361     0x11120201,
1362     0x11120211,
1363     0x11121110,
1364     0x11121120,
1365     0x11121211,
1366     0x11121221,
1367     0x11211000,
1368     0x11211010,
1369     0x11211101,
1370     0x11211111,
1371     0x11212010,
1372     0x11212020,
1373     0x11212111,
1374     0x11212121,
1375     0x11221100,
1376     0x11221110,
1377     0x11221201,
1378     0x11221211,
1379     0x11222110,
1380     0x11222120,
1381     0x11222211,
1382     0x11222221,
1383     0x01000000,
1384     0x01000010,
1385     0x01000101,
1386     0x01000111,
1387     0x01001010,
1388     0x01001020,
1389     0x01001111,
1390     0x01001121,
1391     0x01010100,
1392     0x01010110,
1393     0x01010201,
1394     0x01010211,
1395     0x01011110,
1396     0x01011120,
1397     0x01011211,
1398     0x01011221,
1399     0x01101000,
1400     0x01101010,
1401     0x01101101,
1402     0x01101111,
1403     0x01102010,
1404     0x01102020,
1405     0x01102111,
1406     0x01102121,
1407     0x01111100,
1408     0x01111110,
1409     0x01111201,
1410     0x01111211,
1411     0x01112110,
1412     0x01112120,
1413     0x01112211,
1414     0x01112221,
1415     0x02010000,
1416     0x02010010,
1417     0x02010101,
1418     0x02010111,
1419     0x02011010,
1420     0x02011020,
1421     0x02011111,
1422     0x02011121,
1423     0x02020100,
1424     0x02020110,
1425     0x02020201,
1426     0x02020211,
1427     0x02021110,
1428     0x02021120,
1429     0x02021211,
1430     0x02021221,
1431     0x02111000,
1432     0x02111010,
1433     0x02111101,
1434     0x02111111,
1435     0x02112010,
1436     0x02112020,
1437     0x02112111,
1438     0x02112121,
1439     0x02121100,
1440     0x02121110,
1441     0x02121201,
1442     0x02121211,
1443     0x02122110,
1444     0x02122120,
1445     0x02122211,
1446     0x02122221,
1447     0x11100000,
1448     0x11100010,
1449     0x11100101,
1450     0x11100111,
1451     0x11101010,
1452     0x11101020,
1453     0x11101111,
1454     0x11101121,
1455     0x11110100,
1456     0x11110110,
1457     0x11110201,
1458     0x11110211,
1459     0x11111110,
1460     0x11111120,
1461     0x11111211,
1462     0x11111221,
1463     0x11201000,
1464     0x11201010,
1465     0x11201101,
1466     0x11201111,
1467     0x11202010,
1468     0x11202020,
1469     0x11202111,
1470     0x11202121,
1471     0x11211100,
1472     0x11211110,
1473     0x11211201,
1474     0x11211211,
1475     0x11212110,
1476     0x11212120,
1477     0x11212211,
1478     0x11212221,
1479     0x12110000,
1480     0x12110010,
1481     0x12110101,
1482     0x12110111,
1483     0x12111010,
1484     0x12111020,
1485     0x12111111,
1486     0x12111121,
1487     0x12120100,
1488     0x12120110,
1489     0x12120201,
1490     0x12120211,
1491     0x12121110,
1492     0x12121120,
1493     0x12121211,
1494     0x12121221,
1495     0x12211000,
1496     0x12211010,
1497     0x12211101,
1498     0x12211111,
1499     0x12212010,
1500     0x12212020,
1501     0x12212111,
1502     0x12212121,
1503     0x12221100,
1504     0x12221110,
1505     0x12221201,
1506     0x12221211,
1507     0x12222110,
1508     0x12222120,
1509     0x12222211,
1510     0x12222221
1511 };