// implement basic life rules, with a fast implementation
#include <vector>
#include "FastLife.h"

namespace { // anon
/* for speed we create a table that 
   given the 16 bits of a 4x4 cell 
		0123
		4567
		89AB
		CDEF
	returns the 4 next generation 
	cells for cells 56 and 9A
	*/

// todo - make a table for each used ruleset?

bool tableInitialized_ = false;
unsigned char bitTable[65536];
char popTable[65536]; // population delta for this transformation (+- 4)

void InitTable(void)
	{
	for (unsigned int val = 0; val < 65536; ++val)
		{
		// fill array with bits
		int arr[4][4];
		int temp = val;
		for (int i = 0; i < 16; ++i)
			{
			arr[i%4][i/4] = temp&1;
			temp >>= 1;
			}
		
		// now compute table entry
		unsigned char entry = 0;
		char popDelta = 0;
		for (int y = 1; y < 3; ++y)
			for (int x = 1; x < 3; ++x)
				{
				int neighbors = 0;
				for (int j = -1; j <= 1; ++j)
					for (int i = -1; i <= 1; ++i)
						{
						if ((0 == i) && (0 == j))
							continue;
						neighbors += arr[x+i][y+j];
						}

				bool alive = arr[x][y] != 0;
				if ((neighbors < 2) || (3 < neighbors))
					{
					if (true == alive)
						--popDelta;
					alive = false;
					}
				else if (3 == neighbors)
					{
					if (false == alive)
						++popDelta;
					alive = true;
					}

				entry >>= 1;
				if (true == alive)
					entry |= 8;
				}
		
		// store entrys
		bitTable[val] = entry;
		popTable[val] = popDelta;
		}
	tableInitialized_ = true;
	} // InitTable




	} // anon

void FastLife::NextGeneration(void)
	{
	++generation_;
	int w = width_;
	int h = height_;
	std::vector<uint32> temp(span_*(height_+2));
	unsigned long *p1, *p2, *p3, *p4; // working values

	// copy border wraps first
	// todo - or 0 them if no wrap
	for (int x = 0; x < w ; ++x)
		{
		SetValue(x,-1,GetValue(x,h - 1));
		SetValue(x, h,GetValue(x,0));
		}
	for (int y = 0; y < h; ++y)
		{
		SetValue(-1,y,GetValue(w - 1, y));
		SetValue(w, y,GetValue(0,y));
		}
	// copy corners
	SetValue(-1,-1,GetValue(w-1,h-1));
	SetValue(w,h,GetValue(0,0));
	SetValue(-1,h,GetValue(w-1,0));
	SetValue(w,-1,GetValue(0,h-1));

	// now do interior cells
	for (int y = 1; y < height_+1; y += 2)
		{
		p1 = &data_[(y-1)*span_];
		p2 = &data_[y*span_];
		p3 = &data_[(y+1)*span_];
		p4 = &data_[(y+2)*span_];

		unsigned long row1 = 0, row2 = 0, index;
		unsigned char val;

		// 4 bytes per pass per each of two rows
		for (int x = 0; x < span_; ++x)
			{
			// get these values, increment pointers
			unsigned long v1 = *p1++, v2 = *p2++, v3 = *p3++, v4 = *p4++;

			// do 30 bits  
			// - this assumes highest bit in row1/2 is set properly
			for (int step = 0; step < 15; ++step)
				{
				// look up value
				index  = (v1 & 15);
				index |= (v2 & 15) << 4;
				index |= (v3 & 15) << 8;
				index |= (v4 & 15) << 12;
				val = bitTable[index];
				population_ += popTable[index];
				row1 >>= 2; // make space
				row2 >>= 2;
				row1 |= (val&3)<<30;
				row2 |= (val>>2)<<30;

				// next value
				v1 >>= 2;
				v2 >>= 2;
				v3 >>= 2;
				v4 >>= 2;
				}
			// do end bits
			v1 |= ((*p1)&3)<<2;
			v2 |= ((*p2)&3)<<2;
			v3 |= ((*p3)&3)<<2;
			v4 |= ((*p4)&3)<<2;

			index  = (v1 & 15);
			index |= (v2 & 15) << 4;
			index |= (v3 & 15) << 8;
			index |= (v4 & 15) << 12;
			val = bitTable[index];
			population_ += popTable[index];
			row1 >>= 1;
			row2 >>= 1;
			row1 |= (val&3)<<31;
			row2 |= (val>>2)<<31;

			temp[x+y*span_]     = row1;
			temp[x+(y+1)*span_] = row2;

			// prepare initial bits for next pass
			row1 = (val>>1)<<31;
			row2 = (val>>3)<<31;
			} // for width (span)
		} // for height
	swap(data_,temp);
	} // NextGeneration


// takes RGB buffer, stride, image width, height, and color to draw r,g,b
// and viewport
void FastLife::DrawBuffer(Viewport & vp, unsigned char * buffer, int stride, int width, int height,
				unsigned char r, unsigned char g, unsigned char b)
	{
	int numerator, denominator;
	vp.GetZoom(numerator, denominator);
	int cellWidth = 1<<denominator; // width of a cell in pixels
	int cellSkip  = 1<<numerator;   // cells wide per pixel

	// x,y goes over cell coords, x1,y1 to x2,y2
	int x1, y1, x2, y2;
	vp.GetViewportWorldCoords(width,height,x1,y1,x2,y2);

	ConvertToExternal();

	// scan over dest pixels
	for (int j = 0; j+cellWidth < height; j += cellWidth)
		{
		unsigned char * ptr = buffer + j*stride;
		for (int i = 0; i+cellWidth < width; i += cellWidth)
			{
			bool alive = false;

			// walk relevant cells to see if any alive
			for (int y = 0; y < cellSkip; ++y)
				for (int x = 0; x < cellSkip; ++x)
					{
					int xpos = x1 + x + i * cellSkip / cellWidth;
					int ypos = y1 + y + j * cellSkip / cellWidth;
					if ((0 <= xpos) && (xpos < width_) && (0 <= ypos) && (ypos < height_))
						alive |= (GetValue(xpos,ypos) != 0);
					}

				// draw cell if alive
				if (false == alive)
					ptr += cellWidth*3;
				else
					{
					for (int y = 0; y < cellWidth; ++y)
						{
						for (int x = 0; x < cellWidth; ++x)
							{
							*ptr++ = r;
							*ptr++ = g;
							*ptr++ = b;
							}
						ptr = ptr + stride - cellWidth*3;
						}
					ptr = ptr - cellWidth*stride + cellWidth*3;
					}
			}
		}
	} // DrawBuffer


FastLife::FastLife(void) : 		
		wraps_(true), population_(0),
		generation_(0)
	{
	if (false == tableInitialized_)
		InitTable();
	SetSize(256,256);
	}

// end - FastLife.cpp