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 <string.h>           // for memset
  24
  25 #define ARRAYSIZE  1024       // size of the static array for BeginFind & co.
  26 #define ALLOCBOXES 16         // number of cellboxes to alloc at once
  27
  28
  29 // ==========================================================================
  30 // CellBox
  31 // ==========================================================================
  32
  33 #define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f)
  34 #define HASHSIZE   32768
  35 #define MAXDEAD    8
  36
  37
  38 class CellBox
  39 {
  40 public:
  41     // members
  42     inline bool IsAlive(int dx, int dy) const;
  43     inline bool SetCell(int dx, int dy, bool alive);
  44
  45     // attributes
  46     wxInt32   m_x, m_y;                     // position in universe
  47     wxUint32  m_live1, m_live2;             // alive cells (1 bit per cell)
  48     wxUint32  m_old1, m_old2;               // old values for m_live1, 2
  49     wxUint32  m_on[8];                      // neighbouring info
  50     wxUint32  m_dead;                       // been dead for n generations
  51     CellBox  *m_up, *m_dn, *m_lf, *m_rt;    // neighbour CellBoxes
  52     CellBox  *m_prev, *m_next;              // in linked list
  53     CellBox  *m_hprev, *m_hnext;            // in hash table
  54 };
  55
  56
  57 // IsAlive:
  58 //  Returns whether cell dx, dy in this box is alive
  59 //
  60 bool CellBox::IsAlive(int dx, int dy) const
  61 {
  62     if (dy > 3)
  63         return (m_live2 & 1 << ((dy - 4) * 8 + dx));
  64     else
  65         return (m_live1 & 1 << ((dy) * 8 + dx));
  66 }
  67
  68 // SetCell:
  69 //  Sets cell dx, dy in this box to 'alive', returns TRUE if
  70 //  the previous value was different, FALSE if it was the same.
  71 //
  72 bool CellBox::SetCell(int dx, int dy, bool alive)
  73 {
  74     if (IsAlive(dx, dy) != alive)
  75     {
  76        if (dy > 3)
  77            m_live2 ^= 1 << ((dy - 4) * 8 + dx);
  78        else
  79            m_live1 ^= 1 << ((dy) * 8 + dx);
  80
  81        // reset this here to avoid updating problems
  82        m_dead = 0;
  83
  84        return TRUE;
  85     }
  86     else
  87        return FALSE;
  88 }
  89
  90
  91 // ==========================================================================
  92 // Life
  93 // ==========================================================================
  94
  95 // --------------------------------------------------------------------------
  96 // Ctor and dtor
  97 // --------------------------------------------------------------------------
  98
  99 Life::Life()
 100 {
 101     m_numcells  = 0;
 102     m_boxes     = new CellBox *[HASHSIZE];
 103     m_head      = NULL;
 104     m_available = NULL;
 105     for (int i = 0; i < HASHSIZE; i++)
 106         m_boxes[i] = NULL;
 107
 108     m_cells     = new Cell[ARRAYSIZE];
 109     m_ncells    = 0;
 110     m_findmore  = FALSE;
 111     m_changed   = FALSE;
 112 }
 113
 114 Life::~Life()
 115 {
 116     Clear();
 117
 118     delete[] m_boxes;
 119     delete[] m_cells;
 120 }
 121
 122 // Clear:
 123 //  Clears the board, freeing all storage.
 124 //
 125 void Life::Clear()
 126 {
 127     CellBox *c, *nc;
 128
 129     m_numcells = 0;
 130
 131     // clear the hash table pointers
 132     for (int i = 0; i < HASHSIZE; i++)
 133         m_boxes[i] = NULL;
 134
 135     // free used boxes
 136     c = m_head;
 137     while (c)
 138     {
 139         nc = c->m_next;
 140         delete c;
 141         c = nc;
 142     }
 143     m_head = NULL;
 144
 145     // free available boxes
 146     c = m_available;
 147     while (c)
 148     {
 149         nc = c->m_next;
 150         delete c;
 151         c = nc;
 152     }
 153     m_available = NULL;
 154 }
 155
 156 // --------------------------------------------------------------------------
 157 // Test and set individual cells
 158 // --------------------------------------------------------------------------
 159
 160 // IsAlive:
 161 //  Returns whether cell (x, y) is alive.
 162 //
 163 bool Life::IsAlive(wxInt32 x, wxInt32 y)
 164 {
 165     CellBox *c = LinkBox(x, y, FALSE);
 166
 167     return (c && c->IsAlive( x - c->m_x, y - c->m_y ));
 168 }
 169
 170 // SetCell:
 171 //  Sets or clears cell (x, y), according to the 'alive' param.
 172 //
 173 void Life::SetCell(wxInt32 x, wxInt32 y, bool alive)
 174 {
 175     CellBox *c  = LinkBox(x, y);
 176     wxUint32 dx = x - c->m_x;
 177     wxUint32 dy = y - c->m_y;
 178
 179     if (c->SetCell(dx, dy, alive))
 180     {
 181         if (alive)
 182             m_numcells++;
 183         else
 184             m_numcells--;
 185     }
 186 }
 187
 188 void Life::SetShape(const LifeShape& shape)
 189 {
 190     char *p = shape.m_data;
 191
 192     int i0 = -(shape.m_width / 2);
 193     int j0 = -(shape.m_height / 2);
 194     int i1 = i0 + shape.m_width - 1;
 195     int j1 = j0 + shape.m_height - 1;
 196
 197     Clear();
 198     for (int j = j0; j <= j1; j++)
 199         for (int i = i0; i <= i1; i++)
 200             SetCell(i, j, *(p++) == '*');
 201 }
 202
 203 // --------------------------------------------------------------------------
 204 // Cellbox management functions
 205 // --------------------------------------------------------------------------
 206
 207 // CreateBox:
 208 //  Creates a box in x, y, either taking it from the list
 209 //  of available boxes, or allocating a new one.
 210 //
 211 CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv)
 212 {
 213     CellBox *c;
 214
 215     // if there are no available boxes, alloc a few more
 216     if (!m_available)
 217         for (int i = 1; i <= ALLOCBOXES; i++)
 218         {
 219             c = new CellBox();
 220
 221             if (!c)
 222             {
 223                 // TODO: handle memory errors. Note that right now, if we
 224                 // couldn't allocate at least one cellbox, we will crash
 225                 // before leaving CreateBox(). Probably we should try to
 226                 // allocate some boxes *before* the m_available list goes
 227                 // empty, so that we have a margin to handle errors
 228                 // gracefully.
 229                 wxLogFatalError(_("Out of memory! Aborting..."));
 230
 231                 // NOTREACHED
 232             }
 233
 234             c->m_next = m_available;
 235             m_available = c;
 236         }
 237
 238     // take a cellbox from the list of available boxes
 239     c = m_available;
 240     m_available = c->m_next;
 241
 242     // reset everything
 243     memset((void *) c, 0, sizeof(CellBox));
 244     c->m_x = x;
 245     c->m_y = y;
 246
 247     // insert c in the list
 248     c->m_next = m_head;
 249     m_head = c;
 250     if (c->m_next) c->m_next->m_prev = c;
 251
 252     // insert c in the hash table
 253     c->m_hnext = m_boxes[hv];
 254     m_boxes[hv] = c;
 255     if (c->m_hnext) c->m_hnext->m_hprev = c;
 256
 257     return c;
 258 }
 259
 260 // LinkBox:
 261 //  Returns a pointer to the box (x, y); if it didn't exist yet,
 262 //  it returns NULL or creates a new one, depending on the value
 263 //  of the 'create' parameter.
 264 //
 265 CellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create)
 266 {
 267     wxUint32 hv;
 268     CellBox *c;
 269
 270     x &= 0xfffffff8;
 271     y &= 0xfffffff8;
 272     hv = HASH(x, y);
 273
 274     // search in the hash table
 275     for (c = m_boxes[hv]; c; c = c->m_hnext)
 276         if ((c->m_x == x) && (c->m_y == y)) return c;
 277
 278     // if not found, and (create == TRUE), create a new one
 279     return create? CreateBox(x, y, hv) : NULL;
 280 }
 281
 282 // KillBox:
 283 //  Removes this box from the list and the hash table and
 284 //  puts it in the list of available boxes.
 285 //
 286 void Life::KillBox(CellBox *c)
 287 {
 288     wxUint32 hv = HASH(c->m_x, c->m_y);
 289
 290     // remove from the list
 291     if (c != m_head)
 292         c->m_prev->m_next = c->m_next;
 293     else
 294         m_head = c->m_next;
 295
 296     // remove from the hash table
 297     if (c != m_boxes[hv])
 298         c->m_hprev->m_hnext = c->m_hnext;
 299     else
 300         m_boxes[hv] = c->m_hnext;
 301
 302     // update neighbours
 303     if (c->m_next) c->m_next->m_prev = c->m_prev;
 304     if (c->m_hnext) c->m_hnext->m_hprev = c->m_hprev;
 305     if (c->m_up) c->m_up->m_dn = NULL;
 306     if (c->m_dn) c->m_dn->m_up = NULL;
 307     if (c->m_lf) c->m_lf->m_rt = NULL;
 308     if (c->m_rt) c->m_rt->m_lf = NULL;
 309
 310     // append to the list of available boxes
 311     c->m_next = m_available;
 312     m_available = c;
 313 }
 314
 315 // --------------------------------------------------------------------------
 316 // FindMore & co.
 317 // --------------------------------------------------------------------------
 318
 319 // Post eight cells to the cell arrays (changed cells only)
 320 void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live, wxUint32 old)
 321 {
 322     wxUint32 diff = (live ^ old) & 0x000000ff;
 323
 324     if (!diff) return;
 325
 326     for (wxInt32 k = 8; k; k--, i++)
 327     {
 328         if (diff & 0x01)
 329         {
 330             m_cells[m_ncells].i = i;
 331             m_cells[m_ncells].j = j;
 332             m_ncells++;
 333         }
 334         diff >>= 1;
 335         live >>= 1;
 336     }
 337 }
 338
 339 // Post eight cells to the cell arrays (alive cells only)
 340 void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live)
 341 {
 342     if (! (live & 0x000000ff)) return;
 343
 344     for (wxInt32 k = 8; k; k--, i++)
 345     {
 346         if (live & 0x01)
 347         {
 348             m_cells[m_ncells].i = i;
 349             m_cells[m_ncells].j = j;
 350             m_ncells++;
 351         }
 352         live >>= 1;
 353     }
 354 }
 355
 356 void Life::BeginFind(wxInt32 i0, wxInt32 j0, wxInt32 i1, wxInt32 j1, bool changed)
 357 {
 358     // TODO: optimize for the case where the maximum number of
 359     // cellboxes that fit in the specified viewport is smaller
 360     // than the current total of boxes; iterating over the list
 361     // should then be faster than searching in the hash table.
 362
 363     m_i0 = m_i = i0 & 0xfffffff8;
 364     m_j0 = m_j = j0 & 0xfffffff8;
 365     m_i1 = (i1 + 7) & 0xfffffff8;
 366     m_j1 = (j1 + 7) & 0xfffffff8;
 367
 368     m_findmore = TRUE;
 369     m_changed = changed;
 370 }
 371
 372 bool Life::FindMore(Cell *cells[], size_t *ncells)
 373 {
 374     CellBox *c;
 375     *cells = m_cells;
 376     m_ncells = 0;
 377
 378     if (m_changed)
 379     {
 380         for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0)
 381             for ( ; m_i <= m_i1; m_i += 8)
 382             {
 383                 if ((c = LinkBox(m_i, m_j, FALSE)) == NULL)
 384                     continue;
 385
 386                 // check whether there is enough space left in the array
 387                 if (m_ncells > (ARRAYSIZE - 64))
 388                 {
 389                     *ncells = m_ncells;
 390                     return FALSE;
 391                 }
 392
 393                 DoLine(m_i, m_j    , c->m_live1,       c->m_old1      );
 394                 DoLine(m_i, m_j + 1, c->m_live1 >> 8,  c->m_old1 >> 8 );
 395                 DoLine(m_i, m_j + 2, c->m_live1 >> 16, c->m_old1 >> 16);
 396                 DoLine(m_i, m_j + 3, c->m_live1 >> 24, c->m_old1 >> 24);
 397                 DoLine(m_i, m_j + 4, c->m_live2,       c->m_old2      );
 398                 DoLine(m_i, m_j + 5, c->m_live2 >> 8,  c->m_old2 >> 8 );
 399                 DoLine(m_i, m_j + 6, c->m_live2 >> 16, c->m_old2 >> 16);
 400                 DoLine(m_i, m_j + 7, c->m_live2 >> 24, c->m_old2 >> 24);
 401             }
 402     }
 403     else
 404     {
 405         for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0)
 406             for ( ; m_i <= m_i1; m_i += 8)
 407             {
 408                 if ((c = LinkBox(m_i, m_j, FALSE)) == NULL)
 409                     continue;
 410
 411                 // check whether there is enough space left in the array
 412                 if (m_ncells > (ARRAYSIZE - 64))
 413                 {
 414                     *ncells = m_ncells;
 415                     return FALSE;
 416                 }
 417
 418                 DoLine(m_i, m_j    , c->m_live1      );
 419                 DoLine(m_i, m_j + 1, c->m_live1 >> 8 );
 420                 DoLine(m_i, m_j + 2, c->m_live1 >> 16);
 421                 DoLine(m_i, m_j + 3, c->m_live1 >> 24);
 422                 DoLine(m_i, m_j + 4, c->m_live2      );
 423                 DoLine(m_i, m_j + 5, c->m_live2 >> 8 );
 424                 DoLine(m_i, m_j + 6, c->m_live2 >> 16);
 425                 DoLine(m_i, m_j + 7, c->m_live2 >> 24);
 426             }
 427     }
 428
 429     *ncells = m_ncells;
 430     m_findmore = FALSE;
 431     return TRUE;
 432 }
 433
 434 // --------------------------------------------------------------------------
 435 // Evolution engine
 436 // --------------------------------------------------------------------------
 437
 438 extern unsigned char *g_tab;
 439 extern int g_tab1[];
 440 extern int g_tab2[];
 441
 442 // NextTic:
 443 //  Advance one step in evolution :-)
 444 //
 445 bool Life::NextTic()
 446 {
 447     CellBox  *c, *up, *dn, *lf, *rt;
 448     wxUint32 t1, t2, t3, t4;
 449     bool     changed = FALSE;
 450
 451     m_numcells = 0;
 452
 453     // Stage 1:
 454     // Compute neighbours of each cell
 455     //
 456     // WARNING: unrolled loops and lengthy code follows!
 457     //
 458     c = m_head;
 459
 460     while (c)
 461     {
 462         if (! (c->m_live1 || c->m_live2))
 463         {
 464             c = c->m_next;
 465             continue;
 466         }
 467         up = c->m_up;
 468         dn = c->m_dn;
 469         lf = c->m_lf;
 470         rt = c->m_rt;
 471
 472         // up
 473         t1 = c->m_live1 & 0x000000ff;
 474         if (t1)
 475         {
 476             if (!up)
 477             {
 478                 up = LinkBox(c->m_x, c->m_y - 8);
 479                 up->m_dn = c;
 480             }
 481             t2 = g_tab1[t1];
 482             up->m_on[7] += t2;
 483             c->m_on[1] += t2;
 484             c->m_on[0] += g_tab2[t1];
 485         }
 486
 487         // down
 488         t1 = (c->m_live2 & 0xff000000) >> 24;
 489         if (t1)
 490         {
 491             if (!dn)
 492             {
 493                 dn = LinkBox(c->m_x, c->m_y + 8);
 494                 dn->m_up = c;
 495             }
 496             t2 = g_tab1[t1];
 497             dn->m_on[0] += t2;
 498             c->m_on[6] += t2;
 499             c->m_on[7] += g_tab2[t1];
 500         }
 501
 502         t1 = c->m_live1;
 503         t2 = c->m_live2;
 504
 505         // left
 506         if (t1 & 0x01010101)
 507         {
 508             if (!lf)
 509             {
 510                 lf = LinkBox(c->m_x - 8, c->m_y);
 511                 lf->m_rt = c;
 512             }
 513             if (t1 & 0x00000001)
 514             {
 515                if (!lf->m_up)
 516                {
 517                    lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8);
 518                    lf->m_up->m_dn = lf;
 519                }
 520                lf->m_up->m_on[7] += 0x10000000;
 521                lf->m_on[0] += 0x10000000;
 522                lf->m_on[1] += 0x10000000;
 523             }
 524             if (t1 & 0x00000100)
 525             {
 526                lf->m_on[0] += 0x10000000;
 527                lf->m_on[1] += 0x10000000;
 528                lf->m_on[2] += 0x10000000;
 529             }
 530             if (t1 & 0x00010000)
 531             {
 532                lf->m_on[1] += 0x10000000;
 533                lf->m_on[2] += 0x10000000;
 534                lf->m_on[3] += 0x10000000;
 535             }
 536             if (t1 & 0x01000000)
 537             {
 538                lf->m_on[2] += 0x10000000;
 539                lf->m_on[3] += 0x10000000;
 540                lf->m_on[4] += 0x10000000;
 541             }
 542         }
 543         if (t2 & 0x01010101)
 544         {
 545             if (!lf)
 546             {
 547                 lf = LinkBox(c->m_x - 8, c->m_y);
 548                 lf->m_rt = c;
 549             }
 550             if (t2 & 0x00000001)
 551             {
 552                lf->m_on[3] += 0x10000000;
 553                lf->m_on[4] += 0x10000000;
 554                lf->m_on[5] += 0x10000000;
 555             }
 556             if (t2 & 0x00000100)
 557             {
 558                lf->m_on[4] += 0x10000000;
 559                lf->m_on[5] += 0x10000000;
 560                lf->m_on[6] += 0x10000000;
 561             }
 562             if (t2 & 0x00010000)
 563             {
 564                lf->m_on[5] += 0x10000000;
 565                lf->m_on[6] += 0x10000000;
 566                lf->m_on[7] += 0x10000000;
 567             }
 568             if (t2 & 0x01000000)
 569             {
 570                if (!lf->m_dn)
 571                {
 572                    lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8);
 573                    lf->m_dn->m_up = lf;
 574                }
 575                lf->m_on[6] += 0x10000000;
 576                lf->m_on[7] += 0x10000000;
 577                lf->m_dn->m_on[0] += 0x10000000;
 578             }
 579         }
 580
 581         // right
 582         if (t1 & 0x80808080)
 583         {
 584             if (!rt)
 585             {
 586                 rt = LinkBox(c->m_x + 8, c->m_y);
 587                 rt->m_lf = c;
 588             }
 589             if (t1 & 0x00000080)
 590             {
 591                if (!rt->m_up)
 592                {
 593                    rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8);
 594                    rt->m_up->m_dn = rt;
 595                }
 596                rt->m_up->m_on[7] += 0x00000001;
 597                rt->m_on[0] += 0x00000001;
 598                rt->m_on[1] += 0x00000001;
 599             }
 600             if (t1 & 0x00008000)
 601             {
 602                rt->m_on[0] += 0x00000001;
 603                rt->m_on[1] += 0x00000001;
 604                rt->m_on[2] += 0x00000001;
 605             }
 606             if (t1 & 0x00800000)
 607             {
 608                rt->m_on[1] += 0x00000001;
 609                rt->m_on[2] += 0x00000001;
 610                rt->m_on[3] += 0x00000001;
 611             }
 612             if (t1 & 0x80000000)
 613             {
 614                rt->m_on[2] += 0x00000001;
 615                rt->m_on[3] += 0x00000001;
 616                rt->m_on[4] += 0x00000001;
 617             }
 618         }
 619         if (t2 & 0x80808080)
 620         {
 621             if (!rt)
 622             {
 623                 rt = LinkBox(c->m_x + 8, c->m_y);
 624                 rt->m_lf = c;
 625             }
 626             if (t2 & 0x00000080)
 627             {
 628                rt->m_on[3] += 0x00000001;
 629                rt->m_on[4] += 0x00000001;
 630                rt->m_on[5] += 0x00000001;
 631             }
 632             if (t2 & 0x00008000)
 633             {
 634                rt->m_on[4] += 0x00000001;
 635                rt->m_on[5] += 0x00000001;
 636                rt->m_on[6] += 0x00000001;
 637             }
 638             if (t2 & 0x00800000)
 639             {
 640                rt->m_on[5] += 0x00000001;
 641                rt->m_on[6] += 0x00000001;
 642                rt->m_on[7] += 0x00000001;
 643             }
 644             if (t2 & 0x80000000)
 645             {
 646                if (!rt->m_dn)
 647                {
 648                    rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8);
 649                    rt->m_dn->m_up = rt;
 650                }
 651                rt->m_on[6] += 0x00000001;
 652                rt->m_on[7] += 0x00000001;
 653                rt->m_dn->m_on[0] += 0x00000001;
 654             }
 655         }
 656
 657         // inner cells
 658         int i;
 659         for (i = 1; i <= 3; i++)
 660         {
 661             t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff;
 662             if (t1)
 663             {
 664                 c->m_on[i - 1] += g_tab1[t1];
 665                 c->m_on[i    ] += g_tab2[t1];
 666                 c->m_on[i + 1] += g_tab1[t1];
 667             }
 668         }
 669         for (i = 0; i <= 2; i++)
 670         {
 671             t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff;
 672             if (t1)
 673             {
 674                 c->m_on[i + 3] += g_tab1[t1];
 675                 c->m_on[i + 4] += g_tab2[t1];
 676                 c->m_on[i + 5] += g_tab1[t1];
 677             }
 678         }
 679
 680         c->m_up = up;
 681         c->m_dn = dn;
 682         c->m_lf = lf;
 683         c->m_rt = rt;
 684         c = c->m_next;
 685     }
 686
 687     // Stage 2:
 688     // Stabilize
 689     //
 690     c = m_head;
 691
 692     while (c)
 693     {
 694         t1 = 0;
 695         t2 = 0;
 696
 697         t3 = c->m_live1;
 698         c->m_old1 = t3;
 699
 700         t4 = c->m_on[0];
 701         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3      ) & 0xf) ];
 702         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
 703         t4 = c->m_on[1];
 704         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
 705         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
 706         t4 = c->m_on[2];
 707         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
 708         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
 709         t4 = c->m_on[3];
 710         t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
 711         t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
 712
 713         t3 = c->m_live2;
 714         c->m_old2 = t3;
 715
 716         t4 = c->m_on[4];
 717         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3      ) & 0xf) ];
 718         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
 719         t4 = c->m_on[5];
 720         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
 721         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
 722         t4 = c->m_on[6];
 723         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
 724         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
 725         t4 = c->m_on[7];
 726         t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
 727         t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
 728
 729         c->m_on[0] = c->m_on[1] = c->m_on[2] = c->m_on[3] =
 730         c->m_on[4] = c->m_on[5] = c->m_on[6] = c->m_on[7] = 0;
 731         c->m_live1 = t1;
 732         c->m_live2 = t2;
 733
 734         // count alive cells (TODO: find a better way to do this)
 735         for (int i = 0; i < 32; i++)
 736         {
 737             if (t1 & (1 << i)) m_numcells++;
 738             if (t2 & (1 << i)) m_numcells++;
 739         }
 740
 741         changed |= ((t1 ^ c->m_old1) || (t2 ^ c->m_old2));
 742
 743         // mark, and discard if necessary, dead boxes
 744         if (t1 || t2)
 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 };