/**
 * Malbolge interpreter.
 * 2012, 2017 Matthias Lutter.
 * Please visit <http://www.matthias-ernst.eu/malbolge.html>
 *
 * To the extent possible under law, the author has dedicated all copyright
 * and related and neighboring rights to this software to the public domain 
 * worldwide. This software is distributed without any warranty.
 *
 * See <http://creativecommons.org/publicdomain/zero/1.0/>.
 */
#include <stdio.h>

const char* xlat2 = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1C" \
		"B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";

unsigned int opr(unsigned int a, unsigned int d){
	const unsigned int OPR[] = {
			1,0,0,
			1,0,2,
			2,2,1};
	unsigned int output = 0;
	unsigned int multiple = 1;
	while (multiple < 59049){
		output += multiple * OPR[(a%3) + 3*(d%3)];
		a /= 3;
		d /= 3;
		multiple *= 3;
	}
	return output;
}

unsigned int rotate_r(unsigned int d){
	return 19683*(d%3) + d/3;
}

int main(int argc, char* argv[]) {
	unsigned int memory[59050];
	unsigned int a = 0, c = 0, d = 0, result;
	FILE* file;
	if (argc < 2) {
		// read program code from STDIN
		file = stdin;
	}else{
		file = fopen(argv[1],"rb");
	}
	if (file == NULL) {
		fprintf(stderr, "error: cannot open file\n");
		return 1;
	}
	while (d < 59050){
		unsigned int instruction;
		memory[d] = 0;
		result = fread(memory+d,1,1,file);
		if (result == 0) {
			if (feof(file))
				break;
			else {
				fprintf(stderr, "error: input error\n");
				return 1;
			}
		}
		instruction = (memory[d]+d)%94;
		if (memory[d]==' ' || memory[d] == '\t'
				|| memory[d] == '\r' || memory[d] == '\n');
		else if (memory[d] >= 33 && memory[d] < 127 && (
					   instruction ==  4 || instruction ==  5
					|| instruction == 23 || instruction == 39
					|| instruction == 40 || instruction == 62
					|| instruction == 68 || instruction == 81
				))
			d++;
		else{
			fprintf(stderr, "error: not a valid Malbolge program\n");
			return 1;
		}
	}
	if (file != stdin) {
		fclose(file);
	}
	if (d < 2 || d > 59049) {
		fprintf(stderr, "error: not a valid Malbolge program\n");
		return 1;
	}
	for (; d < 59049; d++)
		memory[d] = opr(memory[d-1], memory[d-2]);

	// execute program
	d = 0;
	while (1) {
		// fetch instruction
		unsigned int instruction = memory[c];
		if (instruction < 33 || instruction > 126) {
			fprintf(stderr, "error: invalid instruction at 0x%05x\n",c);
			return 1;
		}
		switch ((instruction+c)%94){
			case 4: // jmp
				c = memory[d];
				break;
			case 5: // out
				printf("%c",(char)(a));
				break;
			case 23: // in
				a = getchar();
				if (a == EOF)
					a = 59048;
				break;
			case 39: // rot
				a = (memory[d] = rotate_r(memory[d]));
				break;
			case 40: // movd
				d = memory[d];
				break;
			case 62: // opr
				a = (memory[d] = opr(a, memory[d]));
				break;
			case 81: // hlt
				return 0;
			case 68: // nop
			default:
				break;
		}
		// apply xlat2
		if (memory[c] < 33 || memory[c] > 126) {
			fprintf(stderr,"error: undefined xlat2 cycle\n");
			return 1;
		}
		memory[c] = xlat2[(memory[c]-33)%94];
		// increment registers
		c = (c+1)%59049;
		d = (d+1)%59049;
	}
	return 0;
}