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