#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DBGLOG(...)             printf(__VA_ARGS__)
//#define DBGLOG(...)
#define error(...)              fprintf(stderr, __VA_ARGS__); \
                                fprintf(stderr, "%lu | %s\n", \
                                        g_asm_line_number, g_asm_line); \
				g_error_encountered = true;

#define valid_symbol_char(c) (('0' <= c && c <= '9') || ('A' <= c && c <= 'Z') \
                           || ('a' <= c && c <= 'z') || c == '_' || c == '.'   \
		                                     || c == '$' || c == ':')

#define MAX_LINE_LEN            256

#define MAX_SYMBOL_STR_LEN      MAX_LINE_LEN - 2
#define RESERVED_LABEL_NUM      23
#define MAX_SYMBOLS             32768

bool g_error_encountered = false;

char *g_asm_line;                 // currently-read line for convenience
size_t g_asm_line_number;         // current line number
size_t g_instruction_number = 0;  // instruction offset

struct symbol_t {
	char *symbolstr;
	uint16_t value;
};

char *g_reserved_symbol_strs[RESERVED_LABEL_NUM] = {"R0", "R1", "R2", "R3",
                                                    "R4", "R5", "R6", "R7",
                                                    "R8", "R9", "R10", "R11",
                                                    "R12", "R13", "R14", "R15",
                                                    "SP", "LCL", "ARG", "THIS",
                                                    "THAT", "SCREEN", "KBD"};
uint16_t g_reserved_symbol_values[RESERVED_LABEL_NUM] = {0, 1, 2, 3,
                                                         4, 5, 6, 7,
                                                         8, 9, 10, 11,
                                                         12, 13, 14, 15,
                                                         0, 1, 2, 3,
                                                         4, 0x4000, 0x6000};

// label and variable symbols will effectively be treated the same; the only
// difference is in their use (in a hack program)
struct symbol_t *g_symbol_list[MAX_SYMBOLS + RESERVED_LABEL_NUM];
size_t g_symbol_list_len = 0;
size_t g_current_variable_address = 16; // address for next variable symbol


void print_binary_word16(uint16_t w)
{
        unsigned char i, msb;
        char binary_string[17];
        binary_string[16] = '\0';

        for (i = 0; i < 16; ++i) {
                msb = (char)(w >> 15);

                if (msb != 0)
                        binary_string[i] = '1';
                else
                        binary_string[i] = '0';
                w <<= 1;
        }
        printf("%s", binary_string);
}

static uint32_t myatoi(const char *str)
{
	size_t i;
	uint32_t ret = 0;

	for (i = 0; i < 5 && '0' <= str[i] && str[i] <= '9'; ++i) {
		ret = (ret * 10) + (str[i] - 0x30);
	}

	return ret;
}

void debug_dump_all_symbols()
{
	size_t i;
	struct symbol_t *symbol;

	DBGLOG("-------- DEBUG SYMBOL DUMP --------\n");
	for (i = 0; i < g_symbol_list_len; ++i) {
		symbol = g_symbol_list[i];
		DBGLOG("symbol (%s, %hu)\n", symbol->symbolstr, symbol->value);
	}
	DBGLOG("-------- END SYMBOL DUMP --------\n");

	g_symbol_list_len = 0;
}

void free_all_symbols()
{
	size_t i;
	struct symbol_t *symbol;

	for (i = 0; i < g_symbol_list_len; ++i) {
		symbol = g_symbol_list[i];
		free(symbol->symbolstr);    // not checking NULL
		free(symbol);
	}

	g_symbol_list_len = 0;
}

struct symbol_t *create_symbol(const char *str, uint16_t value)
{
	size_t len, i;
	struct symbol_t *symbol;
	char *symbolstr;

	//DBGLOG("creating symbol {'%s', %hu} ...\n", str, value);

	len = strlen(str);
	if (len == 0) {
		error("error creating empty label\n");
		return NULL;
	}

	symbol = malloc(sizeof(struct symbol_t));
	symbolstr = malloc(len + 1);
	if (symbol == NULL || symbolstr == NULL) {
		error("error creating label: malloc() returned NULL\n");
		exit(-1);
	}

	for (i = 0; i < len; ++i) {
		symbolstr[i] = str[i];
	}
	symbolstr[len] = '\0';

	symbol->symbolstr = symbolstr;
	symbol->value = value;

	return symbol;
}

struct symbol_t *lookup_symbol(char *str)
{
	size_t i;
	int diff;
	struct symbol_t *symbol;

	for (i = 0; i < g_symbol_list_len; ++i) {
		symbol = g_symbol_list[i];
		diff = strncmp(str, symbol->symbolstr, MAX_SYMBOL_STR_LEN);
		if (!diff) {
			return symbol;
		}
	}

	return NULL;  // symbol not found
}

bool add_symbol(struct symbol_t *symbol)
{
	struct symbol_t *symbol_already_present;

	if (g_symbol_list_len > (MAX_SYMBOLS + RESERVED_LABEL_NUM)) {
		error("internal: symbol list full, over %d symbols\n",
		       (MAX_SYMBOLS + RESERVED_LABEL_NUM));
		return false;
	}

	symbol_already_present = lookup_symbol(symbol->symbolstr);
	if (symbol_already_present != NULL) { // if present
		error("error: failed to add symbol %s: already found in list\n",
		      symbol->symbolstr);
		return false;
	}

	g_symbol_list[g_symbol_list_len] = symbol;
	++g_symbol_list_len;
	return true;
}

// pre-fill list with 'reserved' symbols and values
bool init_symbol_list()
{
	size_t i;
	struct symbol_t *s;

	for (i = 0; i < RESERVED_LABEL_NUM; ++i) {
		if((s = create_symbol(g_reserved_symbol_strs[i],
		                      g_reserved_symbol_values[i])) == NULL) {
			return false;  // failed to create symbol
		}
		if (!add_symbol(s)) {
			return false;  // failed to add symbol
		}
	}

	return true;
}

// assumes line starts at symbol (_not_ at '(' character, if relevant)
bool parse_symbol_str(const char *line, char *symbol_str, size_t *symbol_len)
{
	char c;
	size_t i;

	//DBGLOG("Parsing symbol string: line %lu | %s\n", g_asm_line_number, line);

	*symbol_len = 0;
	for (i = 0; (c = line[i]) != '\0'; ++i) {
		if (i == 0 && ('0' <= c && c <= '9')) {
			error("syntax error: label starts with a number\n");
			return false;
		}
		// parse characters until closing ')'
		if (i > MAX_SYMBOL_STR_LEN) {
			error("syntax error: label is too long (> %d chars)\n",
			       MAX_SYMBOL_STR_LEN);
			return false;
		} else if (valid_symbol_char(c)) {
			symbol_str[i] = c;
		} else {
			if (i == 1) {
				error("syntax error: empty label '()'\n");
				return false;
			}

			break;
		}
	}

	symbol_str[i] = '\0';
	*symbol_len = i;

	return true;
}

// assumes line[0] == '('
bool parse_label(const char *line)
{
	bool ret;
	size_t label_len;
	uint16_t value;
	char label_str[MAX_SYMBOL_STR_LEN + 1];
	struct symbol_t *symbol;

	//DBGLOG("Parsing label: line %lu | %s\n", g_asm_line_number, line);

	if (line[0] != '(') {  // just to be safe
		return false;  // not a label; label's look like (THIS)
	}

	ret = parse_symbol_str(&line[1], label_str, &label_len);
	if (!ret) {
		return false;
	}

	if (line[label_len + 1] != ')') {
		error("syntax error: no matching ')' found for label, found "
		      "value '%c' in label\n", line[label_len + 1]);
		return false;
	}

	// create label, add to symbol list
	value = (uint16_t)g_instruction_number; // safe. won't
						// be > 65535
	symbol = create_symbol(label_str, value);
	if (symbol == NULL)
		return false;
	return add_symbol(symbol);
}

bool parse_line_for_label(const char *line)
{
	char c;
	size_t i;

	for (i = 0; (c = line[i]) != '\0'; ++i) {
		if (c == ' ' || c == '\t') {
			continue;
		} else if (i == 0 && c == '\0') {
			return false;
		} else if (c == '/') { // likely comment
			return false;
		} else if (c == '(') {
			return parse_label(&line[i]);
		} else if (('!' <= c && c <= '\'') || ('*' <= c && c <= '~')) {
			++g_instruction_number;  // likely instruction found
			return false;
		} else {
			error("syntax error: invalid character '%c' found in "
			      "line\n", c);
		}
	}

	return false;
}

static bool parse_a_type(const char *line, uint16_t *instruction)
{
	bool ret;
	char c, a_field_str[6], symbol_str[MAX_SYMBOL_STR_LEN + 1];
	uint32_t a_field = 0;
	size_t i, a = 0, symbol_len;
	struct symbol_t *symbol;

	//DBGLOG("line: %s\n", line);

	if (line[0] != '@') {
		error("syntax error: A-type instruction doesn't start with @\n");
		return false;
	}

	c = line[1];

	if (c == '\0') {
		error("syntax error: A-type instruction empty after @\n");
		return false;
	}

	if (valid_symbol_char(c) && !('0' <= c && c <= '9')) {
		ret = parse_symbol_str(&line[1], symbol_str, &symbol_len);
		if (!ret)
			return ret;

		symbol = lookup_symbol(symbol_str);
		if (symbol == NULL) {  // symbol doesn't exist in table, is new
			a_field = g_current_variable_address;
			symbol = create_symbol(symbol_str, a_field);
			if (symbol == NULL)
				return false; // create failed
			ret = add_symbol(symbol);
			if (!ret)
				return ret;
			++g_current_variable_address;
		} else {               // symbol exists in table, use its value
			a_field = symbol->value;  // symbol value from table
		}
	} else {
		for (i = 1; (c = line[i]) != '\0' && a < 6; ++i) {
			if ('0' <= c && c <= '9') {
				if (a > 4) {
					error("error: @<number> too long\n");
					return false;
				}
				a_field_str[a] = c; // get number
				a++;
			} else if ((c == ' ' || c == '\t' || c == '/') && i > 1) {
				break;
			} else {       // any other character encountered
				error("syntax error: invalid char '%c' found "
				      "after @\n", c);
				return false;
			}
		}

		if (a == 0) {
			error("syntax error: A-type instruction empty "
			      "after '@'\n");
			return false;
		}

		a_field_str[a] = '\0';

		a_field = myatoi(a_field_str);
	}

	if (a_field > 32767) {
		error("error: %u > 32767, too large\n", a_field);
		return false;
	}

	*instruction = 0x0000 | (uint16_t) a_field;
	return true;
}

/* returns dest bits 0b00000ddd
 * Note: order doesn't matter for multi-register dest (but officially it should)
 */
static bool parse_c_type_dest(const char *dest_line, uint8_t *dest)
{
	size_t len;

	//DBGLOG("dest_line: %s\n", dest_line);

	for (len = 0; dest_line[len] != '='; ++len) {  // read until '='
		if (dest_line[len] == 'A') {
			if (*dest & 0x04) { // if A register already set
				error("syntax error: A register set twice\n");
				return false;
			}
			*dest |= 0x04;
		} else if (dest_line[len] == 'D') {
			if (*dest & 0x02) { // if D register already set
				error("syntax error: D register set twice\n");
				return false;
			}
			*dest |= 0x02;
		} else if (dest_line[len] == 'M') {
			if (*dest & 0x01) { // if M register already set
				error("syntax error: M register set twice\n");
				return false;
			}
			*dest |= 0x01;
		} else {
			error("syntax error: invalid destination register %c\n",
			      dest_line[len]);
			return false;
		}

		if (len >= 3) {
			error("syntax error: dest field incorrect length %lu\n",
			      len);
			return false;
		}
	}
	if (len == 0) {
		error("syntax error: dest field empty\n");
		return false;
	}

	return true;
}

/* returns comp bits 0b0acccccc
 */
static bool parse_c_type_comp(const char *comp_line, uint8_t *comp)
{
	size_t len;

	//DBGLOG("comp_line: %s\n", comp_line);

	for (len = 0; comp_line[len] == '0' || comp_line[len] == '1' ||
	              comp_line[len] == '-' || comp_line[len] == 'D' ||
	              comp_line[len] == 'A' || comp_line[len] == 'M' ||
	              comp_line[len] == '!' || comp_line[len] == '+' ||
	              comp_line[len] == '&' || comp_line[len] == '|'; ++len) {}
	if (len == 1) {  // 0 1 D A M
		switch (comp_line[0]) {
		case '0': *comp = 0x2a; break; // 0 101010
		case '1': *comp = 0x3f; break; // 0 111111
		case 'D': *comp = 0x0c; break; // 0 001100
		case 'A': *comp = 0x30; break; // 0 110000
		case 'M': *comp = 0x70; break; // 1 110000
		default:
			error("syntax error: comp field incorrect value\n");
			return false;
		}
	} else if (len == 2) {  // -1 !D !A !M -D -A -M 
		if (comp_line[0] == '-') {
			switch (comp_line[1]) {
			case '1': *comp = 0x3a; break; // 0 111010
			case 'D': *comp = 0x0f; break; // 0 001111
			case 'A': *comp = 0x33; break; // 0 110011
			case 'M': *comp = 0x73; break; // 1 110011
			default:
				error("syntax error: comp field incorrect value\n");
				return false;
			}
		} else if (comp_line[0] == '!') {
			switch (comp_line[1]) {
			case 'D': *comp = 0x0d; break; // 0 001101
			case 'A': *comp = 0x31; break; // 0 110001
			case 'M': *comp = 0x71; break; // 1 110001
			default:
				error("syntax error: comp field incorrect value\n");
				return false;
			}
		} else {
			error("syntax error: comp field incorrect value\n");
			return false;
		}
	} else if (len == 3) {
		if (comp_line[0] == 'D') {
			if (comp_line[2] == '1') {  // D+1 D-1
				if (comp_line[1] == '+') {
					*comp = 0x1f; // 0 011111
				} else if (comp_line[1] == '-') {
					*comp = 0x0e; // 0 001110
				} else {
					error("syntax error: comp field "
					      "incorrect value\n");
					return false;
				}
			} else {             // D+A D+M D-A D-M D&A D&M D|A D|M
				if (comp_line[2] == 'M') {
					*comp = 0x40;              // _1_ 000000
				} else if (comp_line[2] == 'A') {
					*comp = 0x00;              // _0_ 000000
				} else {
					error("syntax error: comp field "
					      "incorrect value\n");
					return false;
				}

				switch (comp_line[1]) {
				case '+': *comp |= 0x02; break; // 000010
				case '-': *comp |= 0x13; break; // 010011
				case '&': *comp |= 0x00; break; // 000000
				case '|': *comp |= 0x15; break; // 010101
				default:
					error("syntax error: comp field "
					      "incorrect value\n");
					return false;
				}
			}
		} else {
			// A+1 M+1 A-1 M-1 A-D M-D
			if (comp_line[0] == 'M') {
				*comp = 0x40;              // _1_ 000000
			} else if (comp_line[0] == 'A') {
				*comp = 0x00;              // _0_ 000000
			} else {
				error("syntax error: comp field incorrect value\n");
				return false;
			}

			if (comp_line[1] == '+' && comp_line[2] == '1') {
				*comp |= 0x37;  // 1 110111
			} else if (comp_line[1] == '-' && comp_line[2] == '1') {
				*comp |= 0x32;  // 1 110010
			} else if (comp_line[1] == '-' && comp_line[2] == 'D') {
				*comp |= 0x07;  // 1 000111
			} else {
				error("syntax error: comp field incorrect value\n");
				return false;
			}
		}
	} else {
		error("syntax error: comp field incorrect length %lu\n", len);
		return false;
	}

	return true;
}

/* returns jump bits 0b00000jjj
 */
static bool parse_c_type_jump(const char *jump_line, uint8_t *jump)
{
	size_t len;
	char *err_3rd_char = "syntax error: 3rd letter in jump field incorrect\n";

	//DBGLOG("jump_line: %s\n", jump_line);

	for (len = 0; jump_line[len] == 'J' || jump_line[len] == 'G' ||
	              jump_line[len] == 'T' || jump_line[len] == 'E' ||
	              jump_line[len] == 'Q' || jump_line[len] == 'L' ||
	              jump_line[len] == 'N' || jump_line[len] == 'M' ||
	              jump_line[len] == 'P'; ++len) {}
	if (len != 3) {
		error("syntax error: jump field incorrect length %lu\n", len);
		return false;
	}

	if (jump_line[0] == 'J') {                         // if "J__"
		switch (jump_line[1]) {
		case 'G':                                  // if "JG_"
			if (jump_line[2] == 'T') {         // if "JGT"
				*jump = 0x1;
			} else if (jump_line[2] == 'E') {  // if "JGE"
				*jump = 0x3;
			} else {
				error(err_3rd_char); return false;
			}
			break;
		case 'E':                                  // if "JE_"
			if (jump_line[2] == 'Q') {         // if "JEQ"
				*jump = 0x2;
			} else {
				error(err_3rd_char); return false;
			}
			break;
		case 'L':                                  // if "JL_"
			if (jump_line[2] == 'T') {         // if "JLT"
				*jump = 0x4;
			} else if (jump_line[2] == 'E') {  // if "JLE"
				*jump = 0x6;
			} else {
				error(err_3rd_char); return false;
			}
			break;
		case 'N':                                  // if "JN_"
			if (jump_line[2] == 'E') {         // if "JNE"
				*jump = 0x5;
			} else {
				error(err_3rd_char); return false;
			}
			break;
		case 'M':                                  // if "JM_"
			if (jump_line[2] == 'P') {         // if "JMP"
				*jump = 0x7;
			} else {
				error(err_3rd_char); return false;
			}
			break;
		default:
			error("syntax error: 2nd letter in jump field incorrect\n");
			return false;
		}
	} else {
		error("syntax error: jump field doesn't start with 'J'\n");
		return false;
	}

	return true;
}

/* Instruction format: 0b111accccccdddjjj
 * Assumes line begins with actual instruction (prepended whitespace stripped)
 * TODO: eventually just replace all wasteful c-instruction parsing w/ strcmp()
 */
static bool parse_c_type(const char *line, uint16_t *instruction)
{
	bool ret = false;
	char c;
	const char *dest_start = NULL;
	const char *comp_start = NULL;
	const char *jump_start = NULL;
	size_t i = 0;
	uint8_t dest = 0;  // default value when not present
	uint8_t comp = 0;
	uint8_t jump = 0;  // default value when not present

	// set pointers to comp, dest, and/or jump field (if applicable)
	c = line[0];
	for (i = 0; c != ' ' && c != '\t' &&
	            c != '\n' && c != '\0'; ++i) {  // read until end of line
		c = line[i];

		if (c == '=') {                     // indicates dest field
			if (1 <= i && i <= 3) {
				dest_start = &line[0];   // start of line
				// this 'i+1' might be dangerous!
				comp_start = &line[i+1]; // after "[dest]="
			} else {
				error("syntax error: dest incorrect length %lu\n", i);
				return false;
			}
		} else if (c == ';') {              // indicates jump field
			if (1 <= i && i <= 7) {
				// this 'i+1' might be dangerous!
				jump_start = &line[i+1]; // after "[comp];"
			} else {
				error("syntax error: jump incorrect length %lu\n", i);
				return false;
			}
		}
	}

	// Only the comp field is mandatory for assembly instructions;
	// dest and jump fields are optional, and may/may not be present
	if (comp_start == NULL) {
		comp_start = &line[0];  // start of line (no dest field)
	}

	ret = parse_c_type_comp(comp_start, &comp);
	if (!ret) {
		return false;
	}

	if (dest_start != NULL) {
		ret = parse_c_type_dest(dest_start, &dest);
		if (!ret) {
			return false;
		}
	}

	if (jump_start != NULL) {
		ret = parse_c_type_jump(jump_start, &jump);
		if (!ret) {
			return false;
		}
	}

	*instruction = 0xe000 | ((uint16_t)comp << 6)
	                      | ((uint16_t)dest << 3)
	                      | ((uint16_t)jump);
	return true;
}

// does not care about line line length; exits at first newline or after
// relevant portion parsed (allows for syntactically-incorrect lines, I know)
static bool parse_next_instruction(const char *line, uint16_t *instruction)
{
	bool ret = false;
	char c;
	size_t i = 0;

	while ((c = line[i]) != '\0') {
		if (c == ' ' || c == '\t')
			;  // skip any whitespace at start of line
		else if (c == '@') {
			ret = parse_a_type(&line[i], instruction);
			++g_instruction_number;
			break;
		} else if (c >= '!' && c < '~') {
			ret = parse_c_type(&line[i], instruction);
			++g_instruction_number;
			break;
		} else {
			error("syntax error: line '%s' incorrectly formatted\n",
			      line);
		}

		++i;
	}

	return ret;
}

// return false for comment or invalid assembly instruction
bool parse_line(const char *line, uint16_t *instruction)
{
	char c;
	bool slash_found = false;
	size_t i;

	// filter out comment lines
	for (i = 0; (c = line[i]) != '\0'; ++i) {
		if (c == ' ' || c == '\t') {
			continue;
		} else if (i == 0 && c == '\0') {
			return false;         // originally bugfix
		} else if (c == '/') {
			if (slash_found) {    // second slash means comment
				return false;
			}
			slash_found = true;
			continue;
		} else if (slash_found) {
			// this char not slash, but previous was: invalid syntax
			error("syntax error: found '/', comments need '//'\n");
			return false;
		} else if (c == '(') {        // found label, ignore and return
			return false;
		} else {                      // non-whitespace/slash discovered
			break;
		}
	}

	// comment not found, so attempting to parse instruction
	return parse_next_instruction(line, instruction);
}


char *usage_msg = "Usage: assembler1 [path/to/file.asm]\n";

int main(int argc, char *argv[])
{
	bool result = false; 
	uint16_t instruction;
	char in_line[MAX_LINE_LEN];
	size_t i, file_line, in_line_len;
	char *in_file_path;
	FILE *fp;

	if (argc != 2) {                            // requires 1 argument
		fprintf(stderr, usage_msg);
		exit(-1);
	}

	in_file_path = argv[1];
	fp = fopen(in_file_path, "r");
	if (fp == NULL) {
		fprintf(stderr, "failed to open file %s for reading\n",
		        in_file_path);
		exit(-1);
	}

	if(!init_symbol_list()) {
		fprintf(stderr, "internal: failed to initialize symbol list\n");
		exit(-1);
	}

	file_line = 1;
	// first pass to read labels and associate with values
	while (fgets(in_line, MAX_LINE_LEN, fp) != NULL) {  // parse loop
		for (i = 0; in_line[i] != '\0'; ++i) {      // remove newlines
			if (in_line[i] == '\n' || in_line[i] == '\r') {
				in_line[i] = '\0';
				break;
			}
			++in_line_len;
		}

		if (in_line_len == 0 || in_line_len == 1)
			continue;

		g_asm_line = in_line;
		g_asm_line_number = file_line;
		result = parse_line_for_label(in_line);
		//if (result)
		//	DBGLOG("DEBUG: label found in line %s\n", in_line);

		++file_line;
	}

	// skip second pass if error found in first pass
	if (g_error_encountered) {
		fprintf(stderr, "error during first pass label parsing, "
		                "aborting...\n");
		exit(-1);
	}

	if (fseek(fp, 0, SEEK_SET)) {
		fprintf(stderr, "failed to re-read file %s from beginning\n",
		        in_file_path);
		exit(-1);
	}

	file_line = 1;
	while (fgets(in_line, MAX_LINE_LEN, fp) != NULL) {  // parse loop
		fprintf(stderr, "line %lu: %s", file_line, in_line);
		for (i = 0; in_line[i] != '\0'; ++i) {      // remove newlines
			if (in_line[i] == '\n' || in_line[i] == '\r') {
				in_line[i] = '\0';
				break;
			}
			++in_line_len;
		}

		if (in_line_len == 0 || in_line_len == 1)
			continue;

		g_asm_line = in_line;
		g_asm_line_number = file_line;
		result = parse_line(in_line, &instruction);

		if (result) {
			print_binary_word16(instruction);
			putchar('\n');
		}

		++file_line;
	}

	//debug_dump_all_symbols();

	free_all_symbols();

	if (fclose(fp)) {
		fprintf(stderr, "Failed to close file %s\n", in_file_path);
		exit(-1);
	}

	return 0;
}