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  1024      // size of the static arrays 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 new 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 int g_tab1[];
 443 extern int g_tab2[];
 444
 445 // NextTic:
 446 //  Advance one step in evolution :-)
 447 //
 448 bool Life::NextTic()
 449 {
 450     CellBox  *c, *up, *dn, *lf, *rt;
 451     wxUint32 t1, t2, t3, t4;
 452     bool     changed = FALSE;
 453
 454     m_numcells = 0;
 455
 456     // Stage 1:
 457     // Compute neighbours of each cell
 458     //
 459     // WARNING: unrolled loops and lengthy code follows!
 460     //
 461     c = m_head;
 462
 463     while (c)
 464     {
 465         if (! (c->m_live1 || c->m_live2))
 466         {
 467             c = c->m_next;
 468             continue;
 469         }
 470         up = c->m_up;
 471         dn = c->m_dn;
 472         lf = c->m_lf;
 473         rt = c->m_rt;
 474
 475         // up
 476         t1 = c->m_live1 & 0x000000ff;
 477         if (t1)
 478         {
 479             if (!up)
 480             {
 481                 up = LinkBox(c->m_x, c->m_y - 8);
 482                 up->m_dn = c;
 483             }
 484             t2 = g_tab1[t1];
 485             up->m_on[7] += t2;
 486             c->m_on[1] += t2;
 487             c->m_on[0] += g_tab2[t1];
 488         }
 489
 490         // down
 491         t1 = (c->m_live2 & 0xff000000) >> 24;
 492         if (t1)
 493         {
 494             if (!dn)
 495             {
 496                 dn = LinkBox(c->m_x, c->m_y + 8);
 497                 dn->m_up = c;
 498             }
 499             t2 = g_tab1[t1];
 500             dn->m_on[0] += t2;
 501             c->m_on[6] += t2;
 502             c->m_on[7] += g_tab2[t1];
 503         }
 504
 505         t1 = c->m_live1;
 506         t2 = c->m_live2;
 507
 508         // left
 509         if (t1 & 0x01010101)
 510         {
 511             if (!lf)
 512             {
 513                 lf = LinkBox(c->m_x - 8, c->m_y);
 514                 lf->m_rt = c;
 515             }
 516             if (t1 & 0x00000001)
 517             {
 518                if (!lf->m_up)
 519                {
 520                    lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8);
 521                    lf->m_up->m_dn = lf;
 522                }
 523                lf->m_up->m_on[7] += 0x10000000;
 524                lf->m_on[0] += 0x10000000;
 525                lf->m_on[1] += 0x10000000;
 526             }
 527             if (t1 & 0x00000100)
 528             {
 529                lf->m_on[0] += 0x10000000;
 530                lf->m_on[1] += 0x10000000;
 531                lf->m_on[2] += 0x10000000;
 532             }
 533             if (t1 & 0x00010000)
 534             {
 535                lf->m_on[1] += 0x10000000;
 536                lf->m_on[2] += 0x10000000;
 537                lf->m_on[3] += 0x10000000;
 538             }
 539             if (t1 & 0x01000000)
 540             {
 541                lf->m_on[2] += 0x10000000;
 542                lf->m_on[3] += 0x10000000;
 543                lf->m_on[4] += 0x10000000;
 544             }
 545         }
 546         if (t2 & 0x01010101)
 547         {
 548             if (!lf)
 549             {
 550                 lf = LinkBox(c->m_x - 8, c->m_y);
 551                 lf->m_rt = c;
 552             }
 553             if (t2 & 0x00000001)
 554             {
 555                lf->m_on[3] += 0x10000000;
 556                lf->m_on[4] += 0x10000000;
 557                lf->m_on[5] += 0x10000000;
 558             }
 559             if (t2 & 0x00000100)
 560             {
 561                lf->m_on[4] += 0x10000000;
 562                lf->m_on[5] += 0x10000000;
 563                lf->m_on[6] += 0x10000000;
 564             }
 565             if (t2 & 0x00010000)
 566             {
 567                lf->m_on[5] += 0x10000000;
 568                lf->m_on[6] += 0x10000000;
 569                lf->m_on[7] += 0x10000000;
 570             }
 571             if (t2 & 0x01000000)
 572             {
 573                if (!lf->m_dn)
 574                {
 575                    lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8);
 576                    lf->m_dn->m_up = lf;
 577                }
 578                lf->m_on[6] += 0x10000000;
 579                lf->m_on[7] += 0x10000000;
 580                lf->m_dn->m_on[0] += 0x10000000;
 581             }
 582         }
 583
 584         // right
 585         if (t1 & 0x80808080)
 586         {
 587             if (!rt)
 588             {
 589                 rt = LinkBox(c->m_x + 8, c->m_y);
 590                 rt->m_lf = c;
 591             }
 592             if (t1 & 0x00000080)
 593             {
 594                if (!rt->m_up)
 595                {
 596                    rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8);
 597                    rt->m_up->m_dn = rt;
 598                }
 599                rt->m_up->m_on[7] += 0x00000001;
 600                rt->m_on[0] += 0x00000001;
 601                rt->m_on[1] += 0x00000001;
 602             }
 603             if (t1 & 0x00008000)
 604             {
 605                rt->m_on[0] += 0x00000001;
 606                rt->m_on[1] += 0x00000001;
 607                rt->m_on[2] += 0x00000001;
 608             }
 609             if (t1 & 0x00800000)
 610             {
 611                rt->m_on[1] += 0x00000001;
 612                rt->m_on[2] += 0x00000001;
 613                rt->m_on[3] += 0x00000001;
 614             }
 615             if (t1 & 0x80000000)
 616             {
 617                rt->m_on[2] += 0x00000001;
 618                rt->m_on[3] += 0x00000001;
 619                rt->m_on[4] += 0x00000001;
 620             }
 621         }
 622         if (t2 & 0x80808080)
 623         {
 624             if (!rt)
 625             {
 626                 rt = LinkBox(c->m_x + 8, c->m_y);
 627                 rt->m_lf = c;
 628             }
 629             if (t2 & 0x00000080)
 630             {
 631                rt->m_on[3] += 0x00000001;
 632                rt->m_on[4] += 0x00000001;
 633                rt->m_on[5] += 0x00000001;
 634             }
 635             if (t2 & 0x00008000)
 636             {
 637                rt->m_on[4] += 0x00000001;
 638                rt->m_on[5] += 0x00000001;
 639                rt->m_on[6] += 0x00000001;
 640             }
 641             if (t2 & 0x00800000)
 642             {
 643                rt->m_on[5] += 0x00000001;
 644                rt->m_on[6] += 0x00000001;
 645                rt->m_on[7] += 0x00000001;
 646             }
 647             if (t2 & 0x80000000)
 648             {
 649                if (!rt->m_dn)
 650                {
 651                    rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8);
 652                    rt->m_dn->m_up = rt;
 653                }
 654                rt->m_on[6] += 0x00000001;
 655                rt->m_on[7] += 0x00000001;
 656                rt->m_dn->m_on[0] += 0x00000001;
 657             }
 658         }
 659
 660         // inner cells
 661         int i;
 662         for (i = 1; i <= 3; i++)
 663         {
 664             t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff;
 665             if (t1)
 666             {
 667                 c->m_on[i - 1] += g_tab1[t1];
 668                 c->m_on[i    ] += g_tab2[t1];
 669                 c->m_on[i + 1] += g_tab1[t1];
 670             }
 671         }
 672         for (i = 0; i <= 2; i++)
 673         {
 674             t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff;
 675             if (t1)
 676             {
 677                 c->m_on[i + 3] += g_tab1[t1];
 678                 c->m_on[i + 4] += g_tab2[t1];
 679                 c->m_on[i + 5] += g_tab1[t1];
 680             }
 681         }
 682
 683         c->m_up = up;
 684         c->m_dn = dn;
 685         c->m_lf = lf;
 686         c->m_rt = rt;
 687         c = c->m_next;
 688     }
 689
 690     // Stage 2:
 691     // Stabilize
 692     //
 693     // WARNING: to be optimized and unrolled soon.
 694     //
 695     c = m_head;
 696
 697     while (c)
 698     {
 699         t1 = c->m_live1;
 700         c->m_old1 = t1;
 701         t2 = 0;
 702         int i;
 703         for (i = 0; i <= 3; i++)
 704         {
 705             t3 = c->m_on[i];
 706             if (!t3)
 707             {
 708                 t1 >>= 8;
 709                 t2 >>= 8;
 710                 continue;
 711             }
 712
 713             for (int j = 0; j < 8; j++)
 714             {
 715                 t2 >>= 1;
 716                 t4 = t3 & 0x0000000f;
 717
 718                 if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001)))
 719                 {
 720                     t2 |= 0x80000000;
 721                     m_numcells++;
 722                 }
 723
 724                 t3 >>= 4;
 725                 t1 >>= 1;
 726             }
 727             c->m_on[i] = 0;
 728         }
 729         c->m_live1 = t2;
 730
 731         t1 = c->m_live2;
 732         c->m_old2 = t1;
 733         t2 = 0;
 734         for (i = 4; i <= 7; i++)
 735         {
 736             t3 = c->m_on[i];
 737             if (!t3)
 738             {
 739                 t1 >>= 8;
 740                 t2 >>= 8;
 741                 continue;
 742             }
 743
 744             for (int j = 0; j < 8; j++)
 745             {
 746                 t2 >>= 1;
 747                 t4 = t3 & 0x0000000f;
 748
 749                 if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001)))
 750                 {
 751                     t2 |= 0x80000000;
 752                     m_numcells++;
 753                 }
 754
 755                 t3 >>= 4;
 756                 t1 >>= 1;
 757             }
 758             c->m_on[i] = 0;
 759         }
 760         c->m_live2 = t2;
 761
 762         // keep track of changes
 763         changed |= ((c->m_live1 ^ c->m_old1) || (c->m_live2 ^ c->m_old2));
 764
 765         // mark, and discard if necessary, dead boxes
 766         if (c->m_live1 || c->m_live2)
 767         {
 768             c->m_dead = 0;
 769             c = c->m_next;
 770         }
 771         else
 772         {
 773             CellBox *aux = c->m_next;
 774             if (c->m_dead++ > MAXDEAD)
 775                KillBox(c);
 776
 777             c = aux;
 778         }
 779     }
 780
 781     return changed;
 782 }
 783
 784 // --------------------------------------------------------------------------
 785 // Lookup tables - these will be generated on-the-fly soon.
 786 // --------------------------------------------------------------------------
 787
 788 // This table converts from bits (like in live1, live2) to number
 789 // of neighbors for each cell in the upper or lower row.
 790 //
 791 int g_tab1[]=
 792 {
 793     0x00000000,
 794     0x00000011,
 795     0x00000111,
 796     0x00000122,
 797     0x00001110,
 798     0x00001121,
 799     0x00001221,
 800     0x00001232,
 801     0x00011100,
 802     0x00011111,
 803     0x00011211,
 804     0x00011222,
 805     0x00012210,
 806     0x00012221,
 807     0x00012321,
 808     0x00012332,
 809     0x00111000,
 810     0x00111011,
 811     0x00111111,
 812     0x00111122,
 813     0x00112110,
 814     0x00112121,
 815     0x00112221,
 816     0x00112232,
 817     0x00122100,
 818     0x00122111,
 819     0x00122211,
 820     0x00122222,
 821     0x00123210,
 822     0x00123221,
 823     0x00123321,
 824     0x00123332,
 825     0x01110000,
 826     0x01110011,
 827     0x01110111,
 828     0x01110122,
 829     0x01111110,
 830     0x01111121,
 831     0x01111221,
 832     0x01111232,
 833     0x01121100,
 834     0x01121111,
 835     0x01121211,
 836     0x01121222,
 837     0x01122210,
 838     0x01122221,
 839     0x01122321,
 840     0x01122332,
 841     0x01221000,
 842     0x01221011,
 843     0x01221111,
 844     0x01221122,
 845     0x01222110,
 846     0x01222121,
 847     0x01222221,
 848     0x01222232,
 849     0x01232100,
 850     0x01232111,
 851     0x01232211,
 852     0x01232222,
 853     0x01233210,
 854     0x01233221,
 855     0x01233321,
 856     0x01233332,
 857     0x11100000,
 858     0x11100011,
 859     0x11100111,
 860     0x11100122,
 861     0x11101110,
 862     0x11101121,
 863     0x11101221,
 864     0x11101232,
 865     0x11111100,
 866     0x11111111,
 867     0x11111211,
 868     0x11111222,
 869     0x11112210,
 870     0x11112221,
 871     0x11112321,
 872     0x11112332,
 873     0x11211000,
 874     0x11211011,
 875     0x11211111,
 876     0x11211122,
 877     0x11212110,
 878     0x11212121,
 879     0x11212221,
 880     0x11212232,
 881     0x11222100,
 882     0x11222111,
 883     0x11222211,
 884     0x11222222,
 885     0x11223210,
 886     0x11223221,
 887     0x11223321,
 888     0x11223332,
 889     0x12210000,
 890     0x12210011,
 891     0x12210111,
 892     0x12210122,
 893     0x12211110,
 894     0x12211121,
 895     0x12211221,
 896     0x12211232,
 897     0x12221100,
 898     0x12221111,
 899     0x12221211,
 900     0x12221222,
 901     0x12222210,
 902     0x12222221,
 903     0x12222321,
 904     0x12222332,
 905     0x12321000,
 906     0x12321011,
 907     0x12321111,
 908     0x12321122,
 909     0x12322110,
 910     0x12322121,
 911     0x12322221,
 912     0x12322232,
 913     0x12332100,
 914     0x12332111,
 915     0x12332211,
 916     0x12332222,
 917     0x12333210,
 918     0x12333221,
 919     0x12333321,
 920     0x12333332,
 921     0x11000000,
 922     0x11000011,
 923     0x11000111,
 924     0x11000122,
 925     0x11001110,
 926     0x11001121,
 927     0x11001221,
 928     0x11001232,
 929     0x11011100,
 930     0x11011111,
 931     0x11011211,
 932     0x11011222,
 933     0x11012210,
 934     0x11012221,
 935     0x11012321,
 936     0x11012332,
 937     0x11111000,
 938     0x11111011,
 939     0x11111111,
 940     0x11111122,
 941     0x11112110,
 942     0x11112121,
 943     0x11112221,
 944     0x11112232,
 945     0x11122100,
 946     0x11122111,
 947     0x11122211,
 948     0x11122222,
 949     0x11123210,
 950     0x11123221,
 951     0x11123321,
 952     0x11123332,
 953     0x12110000,
 954     0x12110011,
 955     0x12110111,
 956     0x12110122,
 957     0x12111110,
 958     0x12111121,
 959     0x12111221,
 960     0x12111232,
 961     0x12121100,
 962     0x12121111,
 963     0x12121211,
 964     0x12121222,
 965     0x12122210,
 966     0x12122221,
 967     0x12122321,
 968     0x12122332,
 969     0x12221000,
 970     0x12221011,
 971     0x12221111,
 972     0x12221122,
 973     0x12222110,
 974     0x12222121,
 975     0x12222221,
 976     0x12222232,
 977     0x12232100,
 978     0x12232111,
 979     0x12232211,
 980     0x12232222,
 981     0x12233210,
 982     0x12233221,
 983     0x12233321,
 984     0x12233332,
 985     0x22100000,
 986     0x22100011,
 987     0x22100111,
 988     0x22100122,
 989     0x22101110,
 990     0x22101121,
 991     0x22101221,
 992     0x22101232,
 993     0x22111100,
 994     0x22111111,
 995     0x22111211,
 996     0x22111222,
 997     0x22112210,
 998     0x22112221,
 999     0x22112321,
1000     0x22112332,
1001     0x22211000,
1002     0x22211011,
1003     0x22211111,
1004     0x22211122,
1005     0x22212110,
1006     0x22212121,
1007     0x22212221,
1008     0x22212232,
1009     0x22222100,
1010     0x22222111,
1011     0x22222211,
1012     0x22222222,
1013     0x22223210,
1014     0x22223221,
1015     0x22223321,
1016     0x22223332,
1017     0x23210000,
1018     0x23210011,
1019     0x23210111,
1020     0x23210122,
1021     0x23211110,
1022     0x23211121,
1023     0x23211221,
1024     0x23211232,
1025     0x23221100,
1026     0x23221111,
1027     0x23221211,
1028     0x23221222,
1029     0x23222210,
1030     0x23222221,
1031     0x23222321,
1032     0x23222332,
1033     0x23321000,
1034     0x23321011,
1035     0x23321111,
1036     0x23321122,
1037     0x23322110,
1038     0x23322121,
1039     0x23322221,
1040     0x23322232,
1041     0x23332100,
1042     0x23332111,
1043     0x23332211,
1044     0x23332222,
1045     0x23333210,
1046     0x23333221,
1047     0x23333321,
1048     0x23333332
1049 };
1050
1051 // This table converts from bits (like in live1, live2) to number
1052 // of neighbors for each cell in the same row (excluding ourselves)
1053 //
1054 int g_tab2[]=
1055 {
1056     0x00000000,
1057     0x00000010,
1058     0x00000101,
1059     0x00000111,
1060     0x00001010,
1061     0x00001020,
1062     0x00001111,
1063     0x00001121,
1064     0x00010100,
1065     0x00010110,
1066     0x00010201,
1067     0x00010211,
1068     0x00011110,
1069     0x00011120,
1070     0x00011211,
1071     0x00011221,
1072     0x00101000,
1073     0x00101010,
1074     0x00101101,
1075     0x00101111,
1076     0x00102010,
1077     0x00102020,
1078     0x00102111,
1079     0x00102121,
1080     0x00111100,
1081     0x00111110,
1082     0x00111201,
1083     0x00111211,
1084     0x00112110,
1085     0x00112120,
1086     0x00112211,
1087     0x00112221,
1088     0x01010000,
1089     0x01010010,
1090     0x01010101,
1091     0x01010111,
1092     0x01011010,
1093     0x01011020,
1094     0x01011111,
1095     0x01011121,
1096     0x01020100,
1097     0x01020110,
1098     0x01020201,
1099     0x01020211,
1100     0x01021110,
1101     0x01021120,
1102     0x01021211,
1103     0x01021221,
1104     0x01111000,
1105     0x01111010,
1106     0x01111101,
1107     0x01111111,
1108     0x01112010,
1109     0x01112020,
1110     0x01112111,
1111     0x01112121,
1112     0x01121100,
1113     0x01121110,
1114     0x01121201,
1115     0x01121211,
1116     0x01122110,
1117     0x01122120,
1118     0x01122211,
1119     0x01122221,
1120     0x10100000,
1121     0x10100010,
1122     0x10100101,
1123     0x10100111,
1124     0x10101010,
1125     0x10101020,
1126     0x10101111,
1127     0x10101121,
1128     0x10110100,
1129     0x10110110,
1130     0x10110201,
1131     0x10110211,
1132     0x10111110,
1133     0x10111120,
1134     0x10111211,
1135     0x10111221,
1136     0x10201000,
1137     0x10201010,
1138     0x10201101,
1139     0x10201111,
1140     0x10202010,
1141     0x10202020,
1142     0x10202111,
1143     0x10202121,
1144     0x10211100,
1145     0x10211110,
1146     0x10211201,
1147     0x10211211,
1148     0x10212110,
1149     0x10212120,
1150     0x10212211,
1151     0x10212221,
1152     0x11110000,
1153     0x11110010,
1154     0x11110101,
1155     0x11110111,
1156     0x11111010,
1157     0x11111020,
1158     0x11111111,
1159     0x11111121,
1160     0x11120100,
1161     0x11120110,
1162     0x11120201,
1163     0x11120211,
1164     0x11121110,
1165     0x11121120,
1166     0x11121211,
1167     0x11121221,
1168     0x11211000,
1169     0x11211010,
1170     0x11211101,
1171     0x11211111,
1172     0x11212010,
1173     0x11212020,
1174     0x11212111,
1175     0x11212121,
1176     0x11221100,
1177     0x11221110,
1178     0x11221201,
1179     0x11221211,
1180     0x11222110,
1181     0x11222120,
1182     0x11222211,
1183     0x11222221,
1184     0x01000000,
1185     0x01000010,
1186     0x01000101,
1187     0x01000111,
1188     0x01001010,
1189     0x01001020,
1190     0x01001111,
1191     0x01001121,
1192     0x01010100,
1193     0x01010110,
1194     0x01010201,
1195     0x01010211,
1196     0x01011110,
1197     0x01011120,
1198     0x01011211,
1199     0x01011221,
1200     0x01101000,
1201     0x01101010,
1202     0x01101101,
1203     0x01101111,
1204     0x01102010,
1205     0x01102020,
1206     0x01102111,
1207     0x01102121,
1208     0x01111100,
1209     0x01111110,
1210     0x01111201,
1211     0x01111211,
1212     0x01112110,
1213     0x01112120,
1214     0x01112211,
1215     0x01112221,
1216     0x02010000,
1217     0x02010010,
1218     0x02010101,
1219     0x02010111,
1220     0x02011010,
1221     0x02011020,
1222     0x02011111,
1223     0x02011121,
1224     0x02020100,
1225     0x02020110,
1226     0x02020201,
1227     0x02020211,
1228     0x02021110,
1229     0x02021120,
1230     0x02021211,
1231     0x02021221,
1232     0x02111000,
1233     0x02111010,
1234     0x02111101,
1235     0x02111111,
1236     0x02112010,
1237     0x02112020,
1238     0x02112111,
1239     0x02112121,
1240     0x02121100,
1241     0x02121110,
1242     0x02121201,
1243     0x02121211,
1244     0x02122110,
1245     0x02122120,
1246     0x02122211,
1247     0x02122221,
1248     0x11100000,
1249     0x11100010,
1250     0x11100101,
1251     0x11100111,
1252     0x11101010,
1253     0x11101020,
1254     0x11101111,
1255     0x11101121,
1256     0x11110100,
1257     0x11110110,
1258     0x11110201,
1259     0x11110211,
1260     0x11111110,
1261     0x11111120,
1262     0x11111211,
1263     0x11111221,
1264     0x11201000,
1265     0x11201010,
1266     0x11201101,
1267     0x11201111,
1268     0x11202010,
1269     0x11202020,
1270     0x11202111,
1271     0x11202121,
1272     0x11211100,
1273     0x11211110,
1274     0x11211201,
1275     0x11211211,
1276     0x11212110,
1277     0x11212120,
1278     0x11212211,
1279     0x11212221,
1280     0x12110000,
1281     0x12110010,
1282     0x12110101,
1283     0x12110111,
1284     0x12111010,
1285     0x12111020,
1286     0x12111111,
1287     0x12111121,
1288     0x12120100,
1289     0x12120110,
1290     0x12120201,
1291     0x12120211,
1292     0x12121110,
1293     0x12121120,
1294     0x12121211,
1295     0x12121221,
1296     0x12211000,
1297     0x12211010,
1298     0x12211101,
1299     0x12211111,
1300     0x12212010,
1301     0x12212020,
1302     0x12212111,
1303     0x12212121,
1304     0x12221100,
1305     0x12221110,
1306     0x12221201,
1307     0x12221211,
1308     0x12222110,
1309     0x12222120,
1310     0x12222211,
1311     0x12222221
1312 };