/**
 * Generator for text printing Malbolge programs.
 * 2012, 2015 Matthias Ernst.
 * 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>
#include <string.h>
#include <malloc.h>

#define MB_OUT 5
#define MB_ROT 39
#define MB_OPR 62
#define MB_NOP 68
#define MB_HALT 81

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

int memory[59050]; // program
int memory_runtime[59050]; // memory at runtime: with encrypted commands
int last_A_val = 0; // last value of A register

/**
 * Searches and generates Malbolge instructions that generate goal's value in the A register.
 * Malbolge command sequence starts at position C.
 * Returns the length of the instruction set.
 * Returns -1 on failure.
 */
int generate_character(int C, char goal);

void create_malbolge_command(int command, int position) {
	command = (command-(position)%94+94)%94;
	if (command<33) {
		command+=94;
	}
	memory[position] = command;
	if (position >= 98) {
		memory_runtime[position] = translation[memory[position]-33];
	} else {
		memory_runtime[position] = memory[position];
	}
}

int opr(int a, int d){
	int crz[] = {1,0,0,1,0,2,2,2,1};
	int position = 0;
	int output = 0;
	while (position < 10){
		int i = a%3;
		int j = d%3;
		int out = crz[i+3*j];
		int multiple = 1;
		int k;
		for (k=0;k<position;k++)
			multiple *= 3;
		output += multiple*out;
		a /= 3;
		d /= 3;
		position++;
	}
	return output;
}

int rotateR(int d){
	int carry = d%3;
	d /= 3;
	d += 19683 * carry;
	return d;
}


int main(int a, char* b[]){
	char* out_s; // string that should be printed out by the Malbolge program
	int C = 0; // current size of Malbolge program. respectively the value of the C register in Malbolge
	int i;
	
	// read command line arguments
	if (a > 1){
		int total_length = 0; // total length of command line arguments
		int pos = 0;
		for (i=1;i<a;i++){
			total_length += strlen(b[i])+1;
		}
		if (total_length == 0)
			total_length++;
		out_s = (char*)(malloc(total_length*sizeof(char)));
		for (i=1;i<a;i++){
			memcpy(out_s+pos,b[i],strlen(b[i]));
			pos+=strlen(b[i]);
			out_s[pos]=' ';
			pos++;
		}
		if (pos>0)
			pos--;
		out_s[pos]=0;
	}else{
		// If no command line arguments are given, read from STDIN.
		// Read 59.000 characters at most.
		int pos = 0;
		int result = 0;
		out_s = (char*)malloc(59001*sizeof(char));
		if (stdin == 0){
			printf("Cannot access STDIN.\n");
			return -1;
		}
		while (!feof(stdin) && pos < 59000){
			result = fread(out_s+pos,1,1,stdin);
			if (result<0){
				printf("Error while reading from STDIN.\n");
				return -1;
			}
			if (result==0)
				break;
			pos++;
		}
		out_s[pos]=0;
	}

	// first character: b -> cause a jump to address 98 which will be encrypted first
	memory_runtime[0] = memory[0] = 'b';
	// fill skipped memory cells with NOPs
	for (i=1;i<99;i++){
		create_malbolge_command(MB_NOP, i);
	}
	// Malbolge program execution continues with data pointer at 1 and program counter at 99
	C = 99;
	// The data pointer is always D = C-98, so we needn't store its value.

	while (*out_s != 0){
		int command_length = 0;
		// load character to A register
		do {
			command_length = generate_character(C, *out_s);
			out_s++;
		} while(command_length < 0 && *out_s!=0);
		if (command_length == -1)
			break;
		C += command_length;
		if (C > 59047){
			C=59047;
			break;
		}else{
			// print A register
			create_malbolge_command(MB_OUT, C);
			C++;
		}
	}

	if (C > 59047){
		C=59047;
	}
	// halt
	create_malbolge_command(MB_HALT, C);
	C++;
	for (i=0;i<C;i++){
		printf("%c",(char)memory[i]);
		if (i%70 == 69 && i+1 < C)
			printf("\n");
	}
	printf("\n");

	return 0;
}



int generate_character(int C, char goal) {
	// Current size of the search window.
	int window_size = 1;
	int i;

	if (((unsigned char)goal >= 154 && (unsigned char)goal <= 208)) {
		// These characters cannot be generated by our method. Return -1 (no success).
		return -1;
	}
	
	if ((char)last_A_val == goal){
		// goal's value is in the A register already.
		return 0;
	}

	// search for instructions of format
	// NOP* ROT? NOP* OPR? NOP* OPR
	// or
	// NOP* ROT
	// that generate goal's value in the A register
	// within the search window.
	while(window_size <= 700 && window_size + C < 59049){		
		int rotPos = -1;
		do{
			int inner_opr_pos = rotPos+1;
			do{
				int cur_A_val = last_A_val;

				for (i=C;i<C+rotPos;i++){
					create_malbolge_command(MB_NOP, i);
				}

				if (rotPos >= 0){
					create_malbolge_command(MB_ROT, C+rotPos);
					cur_A_val = rotateR(memory_runtime[C+rotPos-98]);
				}

				for (i=C+rotPos+1;i<C+inner_opr_pos;i++){
					create_malbolge_command(MB_NOP, i);
				}
				
				if (inner_opr_pos < window_size-1) {
					create_malbolge_command(MB_OPR, C+inner_opr_pos);
					cur_A_val = opr(cur_A_val,memory_runtime[C+inner_opr_pos-98]);
					for (i=C+inner_opr_pos+1;i<C+window_size;i++){
						create_malbolge_command(MB_NOP, i);
					}
				}

				if (rotPos < window_size-1){
					create_malbolge_command(MB_OPR, C+window_size-1);
					cur_A_val = opr(cur_A_val, memory_runtime[C+window_size-1-98]);
				}


				if ((char)cur_A_val == goal){
					// Success.
					// Update last_A_val and return length of Malbolge code sequence.
					last_A_val = cur_A_val;
					return window_size;
				}
				
				inner_opr_pos++;
			}while (inner_opr_pos < window_size);
			rotPos++;
		}while (rotPos < window_size);
		window_size++; // increase size of search window
	}
	// Malbolge program size or search space exceeded. Return -1 (no success).
	return -1;
}