#include	<stdio.h>
#include	"tierra.h"
#define	MutationRate	0.002
#define	MaxAlloc	128

static	unsigned char	InitOrganism[] = {
(LabelStart|	InstLabel),
(	InstFindB|	LabelStart),
(	InstStore|	RegBx),		/* Bx <- start address */
(	InstFindF|	LabelEnd),
(	InstSub|	RegBx),
(	InstStore|	RegDx),		/* Dx <- Length of body */
(0x40|	InstLabel),
(	InstAlloc),
(	InstStore|	RegCx),		/* Cx <- daughtor's address */
(	InstCallF|	0x30),
(	InstCellDiv),
(	InstLoad|	RegDx),
(	InstJumpB|	0x40),
(0x30|	InstLabel),
(	InstSave),
(0x50|	InstLabel),
(	InstLoad|	MemBx),
(	InstStore|	MemCx),
(	InstInc|	RegBx),
(	InstInc|	RegCx),
(	InstDec|	RegDx),
(	InstLoad|	RegDx),
(	InstSkipZ),
(	InstJumpB|	0x50),
(	InstRestore),
(	InstReturn),
(LabelEnd|	InstLabel)
};
#define	InitLength	27

unsigned long	NewID = 0, Step = 0, Quite = 0;
Organism	*QueueHead = NULL, *QueueTail = NULL,
		*NextOrg = NULL, *TracedOrg = NULL, *FreeOrg = NULL;
unsigned char	World[WorldSize];

#define	AllocUnit	512

static void fill_mem(start, length, value)
unsigned short	start, length;
unsigned char	value;
{
	if (start + length < WorldSize) {
		memset(World + start, value, length);
		draw_area(start, length, value);
	} else {
		int	w = WorldSize - start;
		memset(World + start, value, w);
		draw_area(start, w, value);
		w = length - w;
		if (w > WorldSize) {
			fprintf(stderr,"BUG fill_mem..length=%d\n",length);
			exit(1);
		}
		memset(World, value, w);
		draw_area(0, w, value);
	}
}
static void kill_org(p)
Organism	*p;
{
	if (p->prev) p->prev->next = p->next;
	else if (p == QueueHead) QueueHead = p->next;
	if (p == NextOrg) NextOrg = p->next;
	if (p->next) p->next->prev = p->prev;
	else if (p == QueueTail) QueueTail = p->prev;
	p->next = FreeOrg;
	FreeOrg = p;
	fill_mem(p->start, p->length, InstEmpty);
	if (p->a_length > 0)
		fill_mem(p->a_start, p->a_length, InstEmpty);
	dec_monitor(p->length);
}
static Organism *new_org()
{
	int	i;
	Organism	*new;
	if (!FreeOrg) {
		FreeOrg = (Organism *)malloc(sizeof(Organism)*AllocUnit);
		if (!FreeOrg) { perror("malloc"); exit(1); }
		for (i = 1; i < AllocUnit; i ++)
			FreeOrg[i-1].next = FreeOrg + i;
		FreeOrg[AllocUnit-1].next = NULL;
	}
	new = FreeOrg;
	FreeOrg = new->next;
	memset(new,0,sizeof(Organism));
	new->id = ( ++ NewID );
	return new;
}
static void alloc_memory(p)
Organism	*p;
{
	int	i, j, start, end, length = p->ax + 1;
	Organism	*old;
	if (p->a_length > 0) {
		fill_mem(p->a_start, p->a_length, InstEmpty);
		p->a_start = p->a_length = 0;
	}
	if (length > MaxAlloc) { p->ax = 0xffff; return; }
	for (j = 0, i = p->start + p->length; i != p->start;
		i = (i + 1) % WorldSize) {
		if (World[i] == InstEmpty) {
			if (j == 0) start = i;
			if (++j >= length) break;
		} else j = 0;
	}
	if (j < length) {
		old = QueueHead;
		if (old == p) old = old->next;
		if (!old) { p->ax = 0xffff; return; }
		kill_org(old);
		p->pc --;
		p->ax = 0xffff;
	} else {
		fill_mem(start, length, InstReserved);
		p->ax = p->a_start = start;
		p->a_length = length;
	}
	return;
}
world_reset()
{
	unsigned short	i;
	Organism	*p;
	if (QueueTail) QueueTail->next = FreeOrg;
	FreeOrg = QueueHead;
	Step = 1;
	NewID = Quite = 0;
	QueueHead = QueueTail = NextOrg = new_org();
	memcpy(World, InitOrganism, InitLength);
	for (i = 0; i < InitLength; i ++) draw_one(i);
	fill_mem(InitLength, WorldSize - InitLength, InstEmpty);
	reset_monitor(1);
	QueueHead->pc = QueueHead->start = 0;
	QueueHead->length = InitLength;
}
static int between(start,length,k)
unsigned short	start, length;
int	k;
{
	unsigned short	end = start + length;
	if (end <= WorldSize) return (start <= k && k < end);
	else return ((start <= k && k < WorldSize)
		|| (0 <= k && k < end - WorldSize));
}
static unsigned short *targetR(p,arg)
Organism	*p;
unsigned char	arg;
{
	static	unsigned short	dummy;
	switch (arg & 0x70) {
		case RegAx: return &p->ax;
		case RegBx: return &p->bx;
		case RegCx: return &p->cx;
		case RegDx: return &p->dx;
	}
	return &dummy;
}
static unsigned char *targetM(p,arg,adr,flag)
Organism	*p;
unsigned char	arg;
unsigned short	*adr;
int	flag;
{
	static	unsigned char	dummy;
	unsigned char	*r;
	unsigned short	v;
	switch (arg & 0x70) {
		case MemAx: v = p->ax; break;
		case MemBx: v = p->bx; break;
		case MemCx: v = p->cx; break;
		case MemDx: v = p->dx; break;
		default: v = 0xffff;
	}
	if ((flag && between(p->a_start,p->a_length,v))
	 || (!flag && v < WorldSize)) {
		r = World + v;
		*adr = v;
	} else {
		r = &dummy;
		*adr = 0xffff;
	}
	return r;
}
static unsigned short find_adr(p,mark,dir)
Organism	*p;
unsigned short	mark;
int	dir;
{
	int	i;
	unsigned short	adr, label = (InstLabel | (mark & 0xf0));
	for (i = 0, adr = p->pc; i < WorldSize; i ++) {
		if (World[adr] == label) return adr;
		adr = (adr + dir + WorldSize) % WorldSize;
	}
	return 0xffff;
}
static void cell_division(p)
Organism	*p;
{
	Organism	*d;
	int	i, k;
	if (p->ax > WorldSize || p->a_length <= 0) return;
	d = new_org();
	QueueTail->next = d;
	d->prev = QueueTail;
	QueueTail = d;
	d->start = d->pc = p->a_start;
	d->length = p->a_length;
	p->a_start = p->a_length = 0;
	d->specie = (p->length == d->length)? p->specie : d->id;
	inc_monitor(d->length);
	for (i = 0, k = d->start; i < d->length; i ++) {
		if (World[k] & 0x80)
			{ World[k] = InstHalt; draw_one(k); }
		k = (k + 1) % WorldSize;
	}
	World[d->start] = (InstLabel|LabelStart);
	World[(d->start + d->length - 1) % WorldSize] = (InstLabel|LabelEnd);
	Quite = 0;
}
static void one_instruct(p)
Organism	*p;
{
	unsigned char	code, inst, arg;
	unsigned short	k;
	if (p->pc == 0xffff) { kill_org(p); return; }
	else if (p->pc > WorldSize) p->pc %= WorldSize;
	code = World[p->pc];
	inst = code & 0x0f;
	arg = code & 0x70;
	if ((code & 0x80) || code == (InstLabel|LabelEnd)) {
		kill_org(p);
	} else if (InstNoArg(code)) switch (code & 0x7f) {
		case InstReturn: p->pc = p->pcy; break;
		case InstCellDiv: cell_division(p); p->pc ++; break;
		case InstSave:
		p->ay = p->ax; p->by = p->by;
		p->cy = p->cx; p->dy = p->dx;
		p->pc ++; break;
		case InstRestore:
		p->ax = p->ay; p->bx = p->by;
		p->cx = p->cy; p->dx = p->dy;
		p->pc ++; break;
		case InstSkipZ: if (p->ax == 0) p->pc ++; p->pc ++; break;
		case InstSkipC: if (p->ax & 0x8000) p->pc ++; p->pc ++; break;
		case InstAlloc: alloc_memory(p); p->pc ++; break;
		case InstHalt: kill_org(p); break;
		default: p->pc ++;
	} else if (InstLabelArg(inst)) switch (inst) {
		case InstJumpF: p->pc = find_adr(p,code,1); break;
		case InstJumpB: p->pc = find_adr(p,code,-1); break;
		case InstFindF: p->ax = find_adr(p,code,1); p->pc ++; break;
		case InstFindB: p->ax = find_adr(p,code,-1); p->pc ++; break;
		case InstCallF: p->pcy = p->pc + 1;
		p->pc = find_adr(p,code,1); break;
		case InstCallB: p->pcy = p->pc + 1;
		p->pc = find_adr(p,code,-1); break;
		default: p->pc ++;
	} else if (ArgRegister(arg)) switch (inst) {
		case InstInc: (*targetR(p,arg)) ++; p->pc ++; break;
		case InstDec: (*targetR(p,arg)) --; p->pc ++; break;
		case InstStore: *targetR(p,arg) = p->ax; p->pc ++; break;
		case InstLoad: p->ax = *targetR(p,arg); p->pc ++; break;
		case InstAdd: p->ax += *targetR(p,arg); p->pc ++; break;
		case InstSub: p->ax -= *targetR(p,arg); p->pc ++; break;
		default: p->pc ++;
	} else switch (inst) {
		case InstInc: (*targetM(p,arg,&k,1)) ++;
		World[k] &= 0x7f; draw_one(k); p->pc ++; break;
		case InstDec: (*targetM(p,arg,&k,1)) --;
		World[k] &= 0x7f; draw_one(k); p->pc ++; break;
		case InstStore: *targetM(p,arg,&k,1) = p->ax & 0x7f;
		draw_one(k); p->pc ++; break;
		case InstLoad: p->ax = *targetM(p,arg,&k,0); p->pc ++; break;
		case InstAdd: p->ax += *targetM(p,arg,&k,0); p->pc ++; break;
		case InstSub: p->ax -= *targetM(p,arg,&k,0); p->pc ++; break;
		default: p->pc ++;
	}
	return;
}

static void mutate_one()
{
	static unsigned char mask[] =
		{ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40 };
	long	n = lrand48();
	int	k = (n / 7) % WorldSize;
	if (World[k] == InstEmpty || World[k] == InstReserved) return;
	World[k] ^= mask[n % 7];
	draw_one(k);
}
void disasm(code,str)
unsigned char	code;
char	*str;
{
	unsigned char	inst, arg;
	char	*nm = "nop", *anm;
	inst = code & 0x0f;
	arg = code & 0xf0;
	strcpy(str,nm);
	if (code == InstEmpty) strcpy(str,"empty");
	else if (code == InstReserved) strcpy(str,"reserved");
	else if (InstNoArg(code)) {
		switch (code & 0x7f) {
			case InstReturn: nm = "ret"; break;
			case InstCellDiv: nm = "cldv"; break;
			case InstSave: nm = "save"; break;
			case InstRestore: nm = "restr"; break;
			case InstSkipZ: nm = "skipz"; break;
			case InstSkipC: nm = "skipc"; break;
			case InstAlloc: nm = "alloc"; break;
			case InstHalt: nm = "halt"; break;
		}
		strcpy(str,nm);
	} else if (InstLabelArg(inst) || inst == InstLabel) {
		switch (inst) {
			case InstLabel: nm = "label"; break;
			case InstJumpF: nm = "jmpf"; break;
			case InstJumpB: nm = "jmpb"; break;
			case InstFindF: nm = "findf"; break;
			case InstFindB: nm = "findb"; break;
			case InstCallF: nm = "callf"; break;
			case InstCallB: nm = "callb"; break;
		}
		sprintf(str,"%-5s %02x",nm,(arg>>4));
	} else {
		switch (inst) {
			case InstInc: nm = "inc"; break;
			case InstDec: nm = "dec"; break;
			case InstStore: nm = "store"; break;
			case InstLoad: nm = "load"; break;
			case InstAdd: nm = "add"; break;
			case InstSub: nm = "sub"; break;
		}
		switch (code & 0x70) {
			case RegAx: anm = "ax"; break;
			case RegBx: anm = "bx"; break;
			case RegCx: anm = "cx"; break;
			case RegDx: anm = "dx"; break;
			case MemAx: anm = "[ax]"; break;
			case MemBx: anm = "[bx]"; break;
			case MemCx: anm = "[cx]"; break;
			case MemDx: anm = "[dx]"; break;
			default: anm = "??";
		}
		sprintf(str,"%-5s %s",nm,anm);
	}
}
show_prog(p,flag)
Organism	*p;
int	flag;
{
	int	j, k;
	char	nm[32];
	unsigned char	code;
	printf("id=%d, specie=%d, %04x-%d\n",
		p->id,p->specie,p->start,p->length);
	printf("pc=%04x,ax=%04x,bx=%04x,cx=%04x,dx=%04x\n",
		p->pc,p->ax,p->bx,p->cx,p->dx);
	for (j = 0, k = p->start; j < p->length; j ++) {
		disasm((code = World[k]), nm);
		printf("%04x:%02x %s%s\n",k,code,
		(((code & 0x0f) == InstLabel)? "": "        "),nm);
		k = (k + 1) % WorldSize;
	}
	TracedOrg = flag? p : NULL;
	if (flag) printf("****** Trace ... %d\n",p->id);
}
show_prog_m(i,flag)
int	i, flag;
{
	Organism	*p;
	if (i < 0 || i > WorldSize)
		{ printf("%d: outof memory.\n",i); return 0; }
	if (World[i] == InstEmpty)
		{ printf("%d: empty.\n",i); return 0; }
	for (p = QueueHead; p; p = p->next) {
		if (between(p->a_start, p->a_length, i)) {
			printf("%d-%d: allocated memory for %d, %d-%d.\n",
			p->a_start,p->a_length,p->id,p->start,p->length);
			return 0;
		} else if (between(p->start, p->length, i)) break;
	}
	if (!p) { printf("%d: ??? %02x.\n",i,World[i]); return 0; }
	show_prog(p,flag);
}
int one_step()
{
	double	drand48();
	Organism	*p;
	if (!NextOrg) {
		NextOrg = QueueHead;
		if (!NextOrg)
			{puts("empty queue"); return 0;}
	}
	p = NextOrg;
	NextOrg = p->next;
	Step ++;
	if (Step % 16 == 0) draw_step(Step);
	if (p == TracedOrg) {
		char	nm[32];
		disasm(World[p->pc],nm);
		printf("%04x:%02x  %-12s %04x,%04x,%04x,%04x\n",p->pc,
			World[p->pc],nm,p->ax,p->bx,p->cx,p->dx);
	}
	one_instruct(p);
	if (drand48() < MutationRate) mutate_one();
	if ((Quite ++) > 1000000L) return 0;
	return NextOrg? 2 : 1;
}

#define	NParams	5
open_file(path)
char	*path;
{
	FILE	*in;
	unsigned long	n, corg, i, prm[NParams];
	Organism	org, *p;
	if (!(in = fopen(path,"r"))) { perror(path); return 0; }
	world_reset();
	fread(prm,sizeof(long),NParams,in);
	NewID = prm[0]; Step = prm[1]; Quite = prm[2];
	n = prm[3]; corg = prm[4];
	fread(World,1,WorldSize,in);
	i = 0;
	do {
		if (!fread(&org,sizeof(Organism),1,in)) {
			perror(path); fclose(in);
			world_reset();
			return;
		}
		org.prev = QueueTail->prev;
		*QueueTail = org;
		if (i == corg) NextOrg = QueueTail;
		i ++;
		if (i < n) {
			p = new_org();
			QueueTail->next = p;
			p->prev = QueueTail;
			QueueTail = p;
		}
	} while (i < n);
	load_histgram(in);
	for (i = 0; i < WorldSize; i ++) draw_one(i);
	QueueTail->next = NULL;
	fclose(in);
}

save_file(path)
char	*path;
{
	FILE	*out;
	unsigned long	n, corg, i, prm[NParams];
	Organism	*p;
	if (!(out = fopen(path,"w"))) { perror(path); return 0; }
	for (n = 0, p = QueueHead; p; n ++, p = p->next)
		if (p == NextOrg) corg = n;
	prm[0] = NewID; prm[1] = Step; prm[2] = Quite;
	prm[3] = n; prm[4] = corg;
	fwrite(prm,sizeof(long),NParams,out);
	fwrite(World,1,WorldSize,out);
	for (p = QueueHead; p; p = p->next)
		if (!fwrite(p,sizeof(Organism),1,out))
			{ perror(path); break; }
	save_histgram(out);
	fclose(out);
}