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