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