code.c

一遗传算法的例子源程序

#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "lithos.h"

Instruction *code0;
Instruction *code1;

int *memory0;
int *memory1;

int *gmemory;
int *gsp;

int *blocks0;
int *blocks1;

static char *mnemonics[] =
{
	"CONST0",
	"CONST1",
	"RANDOM",

	"INC",
	"DEC",

	"ADD",
	"SUB",
	"MUL",
	"DIV",

	"EQ",
	"NE",
	"LT",
	"GT",
	"LE",
	"GE",

	"AND",
	"OR",
	"NOT",

	"LABEL0",
	"LABEL1",

	"JMP",
	"JT",
	"JF",

	"CALL",
	"RET",

	"DUP",
	"SWAP",
	"POP",

	"LOAD",
	"STORE",
};

void initCode()
{
	code0 = alloc((maxSize + 1) * sizeof(Instruction));
	code1 = alloc((maxSize + 1) * sizeof(Instruction));

	memory0 = alloc(maxMemory * sizeof(int));
	memory1 = alloc(maxMemory * sizeof(int));

	blocks0 = alloc((maxSize + 1) * sizeof(int));
	blocks1 = alloc((maxSize + 1) * sizeof(int));
}

int readInstruction(FILE *f)
{
	char *s = readString(f);
	int i;
	for (i = 0; i < INSTRUCTIONS; i++)
		if (!strcmp(s, mnemonics[i]))
			return i;
	printf("Invalid instruction '%s'\n", s);
	exit(EXIT_FAILURE);
	return 0;
}

static int isLabel(int i)
{
	return i == LABEL0 || i == LABEL1;
}

static int match(char *a, char *b)
{
	while (isLabel(*a) && isLabel(*b))
	{
		if (*a != *b)
			return 0;
		a++;
		b++;
	}
	if (isLabel(*a) ||
		isLabel(*b))
		return 0;
	return 1;
}

void unpack(Program *p, Instruction *code)
{
	char *pc = p->code;
	int size = p->size;
	int i, j;
	int i0, i1;
	int d0, d1;
	pc[size] = INSTRUCTIONS;

	for (i = 0; i < size + 1; i++)
	{
		int op = pc[i];
		code[i].op = op;
		code[i].jmp = &code[i + 1];

		if (op != JMP &&
			op != JT &&
			op != JF &&
			op != CALL)
			continue;
		if (!isLabel(pc[i + 1]))
			continue;

		d0 = size;
		d1 = size;

		for (j = i;;)
		{
			for (; j > 0 && !isLabel(pc[j - 1]); j--)
				;
			if (!j)
				break;
			for (; j > 0 && isLabel(pc[j - 1]); j--)
				;
			if (!j)
				break;
			if (!match(pc + i + 1, pc + j))
				continue;
			i0 = j;
			d0 = i - j;
			break;
		}
		for (j = i + 2;;)
		{
			for (; isLabel(pc[j]); j++)
				;
			for (; j < size && !isLabel(pc[j]); j++)
				;
			if (j == size)
				break;
			if (!match(pc + i + 1, pc + j))
				continue;
			i1 = j;
			d1 = j - i;
			break;
		}

		if (d0 <= d1)
		{
			if (d0 != size)
			{
				while (isLabel(pc[i0]))
					i0++;
				code[i].jmp = &code[i0];
			}
		}
		else
			if (d1 != size)
			{
				while (isLabel(pc[i1]))
					i1++;
				code[i].jmp = &code[i1];
			}
	}
}

void exec(Instruction *code, int size, int *memory)
{
	Instruction *ip = code;
	int *top = memory + maxMemory;
	int *sp = memory;
	int n = maxTime;
	int x, y;

	gmemory = memory;
	do
	{
#ifdef DEBUG
		if (ip->op < INSTRUCTIONS)
			printf("%s\n", mnemonics[ip->op]);
#endif

		switch (ip->op)
		{
		case CONST0:
			if (sp == memory)
				sp = top;
			*--sp = 0;
			ip++;
			break;
		case CONST1:
			if (sp == memory)
				sp = top;
			*--sp = 1;
			ip++;
			break;
		case RANDOM:
			if (sp == memory)
				sp = top;
			*--sp = random() % 2;
			ip++;
			break;

		case INC:
			(*sp)++;
			ip++;
			break;
		case DEC:
			(*sp)--;
			ip++;
			break;

		case ADD:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = x + y;
			ip++;
			break;
		case SUB:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = x - y;
			ip++;
			break;
		case MUL:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = x * y;
			ip++;
			break;
		case DIV:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			if (y == 0 || (x == INT_MIN && y == -1))
				y = 1;
			*sp = x / y;
			ip++;
			break;

		case EQ:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x == y)
				*sp = -1;
			ip++;
			break;
		case NE:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x != y)
				*sp = -1;
			ip++;
			break;
		case LT:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x < y)
				*sp = -1;
			ip++;
			break;
		case GT:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x > y)
				*sp = -1;
			ip++;
			break;
		case LE:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x <= y)
				*sp = -1;
			ip++;
			break;
		case GE:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = 0;
			if (x >= y)
				*sp = -1;
			ip++;
			break;

		case AND:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = x & y;
			ip++;
			break;
		case OR:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			*sp = x | y;
			ip++;
			break;
		case NOT:
			*sp = ~*sp;
			ip++;
			break;

		case LABEL0:
		case LABEL1:
			ip++;
			break;

		case DUP:
			x = *sp;
			if (sp == memory)
				sp = top;
			*--sp = x;
			ip++;
			break;
		case SWAP:
			if (sp + 1 == top)
			{
				x = *memory;
				*memory = *sp;
				*sp = x;
				ip++;
				break;
			}
			x = *(sp + 1);
			*(sp + 1) = *sp;
			*sp = x;
			ip++;
			break;
		case POP:
			sp++;
			if (sp == top)
				sp = memory;
			ip++;
			break;

		case JMP:
			ip = ip->jmp;
			break;
		case JT:
			x = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			if (x)
			{
				ip = ip->jmp;
				break;
			}
			ip++;
			break;
		case JF:
			x = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			if (!x)
			{
				ip = ip->jmp;
				break;
			}
			ip++;
			break;

		case CALL:
			if (sp == memory)
				sp = top;
			*--sp = ip + 1 - code;
			ip = ip->jmp;
			break;
		case RET:
			x = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			if (x < 0 || x > size)
			{
				ip++;
				break;
			}
			ip = code + x;
			break;

		case LOAD:
			x = *sp;
			if (x >= 0 && x < maxMemory)
				*sp = memory[x];
			ip++;
			break;
		case STORE:
			y = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			x = *sp;
			sp++;
			if (sp == top)
				sp = memory;
			if (x >= 0 && x < maxMemory)
				memory[x] = y;
			ip++;
			break;

		case INSTRUCTIONS:
			gsp = sp;
			return;
		}

#ifdef DEBUG
		if (top - sp <= maxMemory / 100)
			for (gsp = sp; gsp != top; gsp++)
				printf("%d\n", *gsp);
#endif
	}
	while (--n);
	gsp = sp;
}

int pop()
{
	int x = *gsp;
	gsp++;
	if (gsp == gmemory + maxMemory)
		gsp = gmemory;
	return x;
}

void writeInstruction(FILE *f, int op)
{
	writeString(f, mnemonics[op]);
}