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