#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <unordered_set>

/* Chip8 assembler - Created by Joel Yliluoma
 * For video presentation at https://www.youtube.com/watch?v=rpLoS7B6T94
 */

#include "fparser.hh" /* Warp's Function Parser. Google it. */
                      /* Though I made a few small changes. */

/*
    Syntax:

    .define thisreg  v4    // defines an alias

    label:                 // defines a label

    var = expression       // defines a variable that depends on expression
    jp    expression       // expressions can be used in assembler commands

    Expressions:

    50                     // numeric values
    0x40                   // numeric values
    50+(4+2)               // arithmetic expressions
    50+var                 // mathematical formula

*/
#define LIST_INSTRUCTIONS(o) \
    o("sys N",     "0NNN") \
    o("cls",       "00E0") \
    o("ret",       "00EE") \
    o("jp N",      "1NNN") \
    o("jp V0, N",  "BNNN") \
    o("jp V0 + N", "BNNN") \
    o("jp N + V0", "BNNN") \
    o("call N",    "2NNN") \
    o("se vX, N",  "3XNN") \
    o("sne vX, N", "4XNN") \
    o("se vX, vY", "5XY0") \
    o("sne vX, vY","9XY0") \
    o("ld vX, N",  "6XNN") \
    o("ld vX, vY", "8XY0") \
    o("add vX, N", "7XNN") \
    o("or vX, vY", "8XY1") \
    o("and vX, vY", "8XY2") \
    o("xor vX, vY", "8XY3") \
    o("add vX, vY", "8XY4") \
    o("sub vX, vY", "8XY5") \
    o("subn vX, vY", "8XY7") \
    o("shr vX, vY",  "8XY6") \
    o("shl vX, vY",  "8XYE") \
    o("rnd vX, N",   "CXNN") \
    o("drw vX, vY, N", "DXYN") \
    o("skp vX",       "EX9E") \
    o("sknp vX",      "EXA1") \
    o("ld vX, dt",    "FX07") \
    o("ld vX, k",     "FX0A") \
    o("ld dt, vX",    "FX15") \
    o("ld st, vX",    "FX18") \
    o("ld i, N",      "ANNN") \
    o("add i, vX",    "FX1E") \
    o("ld f, vX",     "FX29") \
    o("ld i, digit vX", "FX29") \
    o("ld b, vX",       "FX33") \
    o("ld [i], bcd vX", "FX33") \
    o("ld [i], vX",     "FX55") \
    o("ld vX, [i]",     "FX65") \
    /* schip48 extensions */ \
    o("scd N",           "00CN") \
    o("scr",             "00FB") \
    o("scl",             "00FC") \
    o("exit",            "00FD") \
    o("low",             "00FE") \
    o("high",            "00FF") \
    o("ld hf, vX",       "FX30") \
    o("ld r, vX",        "FX75") \
    o("ld vX, r",        "FX85") \
    /* macros */ \
    o("mld [i], vX",     "FX55") \
    o("mld vX, [i]",     "FX65") \
    o("ld vX, [N]",      "ANNNFX65") \
    o("ld [N], vX",      "ANNNFX55") \
    o("ld [N], bcd vX",  "ANNNFX33") \
    o("if vX = vY",      "9XY0") \
    o("if vX != vY",     "5XY0") \
    o("if vX <> vY",     "5XY0") \
    o("if vX = N",       "4XNN") \
    o("if vX != N",      "3XNN") \
    o("if vX <> N",      "3XNN") \
    o("if key vX",       "EXA1") \
    o("if !key vX",      "EX9E") \

static const std::string alpha = "@ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_0123456789";

typedef FunctionParserBase<long int> fparser_t;
typedef std::pair<std::string/*expr*/, std::unordered_set<std::string/*param*/>>
            ExpressionType;

struct TestResult
{
    ExpressionType n{};
    const char* pattern    =nullptr;
    const char* hex_pattern=nullptr;
    unsigned char x=0, y=0;
    unsigned long long compiled=0;
    unsigned bytes=0;

    std::string Decompile() const
    {
        std::stringstream result;
        result << std::hex << std::uppercase;
        for(const char* p = pattern; *p; ++p)
        {
            if(*p == 'X') result << (unsigned)x;
            else if(*p == 'Y') result << (unsigned)y;
            else if(*p == 'N') result << n.first;
            else result << *p;
        }
        return result.str();
    }
};

static fparser_t fparser;
static std::unordered_map<std::string/*name*/,ExpressionType>  saved_expressions;
static std::vector<TestResult> program;
static std::unordered_set<std::string> defined_identifiers;

static bool IsReservedWord(const std::string& paramname)
{
    std::string param_uc;
    for(char c: paramname) param_uc += std::toupper(c);

    if((param_uc.size() == 2 && param_uc[0] == 'V' && std::isxdigit(param_uc[1]))
    || param_uc == "I"
    || param_uc == "DIGIT"
    || param_uc == "BCD"
    || param_uc == "DT"
    || param_uc == "ST"
    || param_uc == "K"
    || param_uc == "HF"
    || param_uc == "R"
      )
    {
        return true;
    }
    return false;
}

static int ParseAndDeduceVariables(const std::string& expr, std::unordered_set<std::string>& params)
{
redo:;
    std::string paramstr;
    for(const auto& s: params) { if(!paramstr.empty()) paramstr += ','; paramstr += s; }
    int len_parsed = fparser.Parse(expr, paramstr);
    int res = fparser.GetParseErrorType();
    if(res == fparser_t::UNKNOWN_IDENTIFIER)
    {
        int pos = len_parsed;
        std::string paramname;
        while(std::isalnum(expr[pos]) || expr[pos] == '_' || expr[pos] == '@')
            paramname += expr[pos++];

        if(IsReservedWord(paramname)) return len_parsed;

        if(!paramname.empty())
        {
            params.insert(paramname);
            goto redo;
        }
    }
    return len_parsed;
}

static void CheckProgramLine(TestResult& line)
{
    unsigned len = 0;
    if(line.hex_pattern)
    {
        while(line.hex_pattern[len]) ++len;
        line.bytes = len/2;
    }

    if(line.hex_pattern && line.n.second.empty())
    {
        unsigned n = 0, x = line.x, y = line.y;
        if(!line.n.first.empty())
        {
            int len_parsed = fparser.Parse(line.n.first, {});
            if(fparser.GetParseErrorType() == fparser_t::FP_NO_ERROR)
                n = fparser.Eval(nullptr);
            else
            {
                std::string msg = fparser.ErrorMsg();
                std::fprintf(stderr, "%s in expression: %s\n%*s\n",
                    msg.c_str(), line.n.first.c_str(),
                    int(msg.size() + 16 + len_parsed + 1), "^");
            }
        }

        line.compiled = 0;
        unsigned bitpos = 0;
        for(unsigned pos = len; pos-- > 0; bitpos += 4)
        {
            char c = line.hex_pattern[pos];
            /**/ if(c == 'N') { line.compiled += (n & 0xF) << bitpos; n >>= 4; }
            else if(c == 'X') { line.compiled += (x & 0xF) << bitpos; x >>= 4; }
            else if(c == 'Y') { line.compiled += (y & 0xF) << bitpos; y >>= 4; }
            else if(c >= '0' && c <= '9') { line.compiled += ((c-'0'+0) << bitpos); }
            else if(c >= 'A' && c <= 'F') { line.compiled += ((c-'A'+10) << bitpos); }
            else if(c >= 'a' && c <= 'f') { line.compiled += ((c-'a'+10) << bitpos); }
        }
        line.hex_pattern = nullptr;
    }
}

static void DefineExpression(std::string name, ExpressionType&& expr)
{
    std::unordered_set<std::string> cascade;
    std::unordered_set<std::size_t> lines;
    if(IsReservedWord(name))
    {
        std::fprintf(stderr, "Illegal attempt to redefine reserved word '%s' as '%s'\n",
            name.c_str(), expr.first.c_str());
        return;
    }
    for(;;)
    {
        if(expr.second.empty())
        {
            if(defined_identifiers.find(name) != defined_identifiers.end())
            {
                std::fprintf(stderr, "Duplicate definition of variable: %s\n", name.c_str());
            }
            fparser.Parse(expr.first, {});
            if(fparser.GetParseErrorType() == fparser_t::FP_NO_ERROR)
            {
                auto result = fparser.Eval(nullptr);
                if(!fparser.AddConstant(name, result))
                    std::fprintf(stderr, "Illegal variable name or variable already defined: %s\n", name.c_str());
                else
                {
                    defined_identifiers.insert(name);

                    // Check existing expressions, whether they can actually now be defined
                    for(auto i = saved_expressions.begin(); i != saved_expressions.end(); ++i)
                    {
                        auto j = i->second.second.find(name);
                        if(j != i->second.second.end())
                        {
                            // It depends on this variable
                            i->second.second.erase(j);
                            if(i->second.second.empty())
                            {
                                cascade.insert(i->first);
                            }
                        }
                    }
                    // Check program lines, whether they can actually now be compiled
                    for(std::size_t p=0; p<program.size(); ++p)
                        if(program[p].hex_pattern)
                        {
                            auto& v = program[p].n.second;
                            auto j = v.find(name);
                            if(j != v.end())
                            {
                                v.erase(j);
                                lines.insert(p);
                            }
                        }
                }
            }
        }
        else
            saved_expressions.insert({name, std::move(expr)});

more_cascade:
        if(cascade.empty()) break;
        auto i = cascade.begin();
        name = *i;
        auto j = saved_expressions.find(name);
        if(j == saved_expressions.end()) { cascade.erase(i); goto more_cascade; }
        expr = std::move(j->second);
        saved_expressions.erase(j);
        cascade.erase(i);
    }
    for(auto p: lines) CheckProgramLine(program[p]);
}

static void DefineExpression(const std::string& name, const std::string& expression)
{
    std::unordered_set<std::string> params;
    int len_parsed = ParseAndDeduceVariables(expression, params);

    int res = fparser.GetParseErrorType();
    if(res == fparser_t::FP_NO_ERROR)
    {
        DefineExpression(name, {std::move(expression), std::move(params)});
    }
    else
    {
        std::string msg = fparser.ErrorMsg();
        std::fprintf(stderr, "%s in expression: %s\n%*s\n",
            msg.c_str(), expression.c_str(),
            int(msg.size() + 16 + len_parsed + 1), "^");
    }
}

static TestResult MatchInstruction(const std::string &pattern)
{
    auto Test = [&](const char* const expect_, const char* const hex_pattern, TestResult& res)
    {
        const char* src = pattern.c_str();
        const char* expect = expect_;
        for(;;)
        {
            while(std::isspace(*src)) ++src;
            while(std::isspace(*expect)) ++expect;
            switch(*expect)
            {
                case 'X':if(*src>='0' && *src<='9') res.x = *src-'0'+0;
                    else if(*src>='A' && *src<='F') res.x = *src-'A'+10;
                    else if(*src>='a' && *src<='f') res.x = *src-'a'+10;
                    else {
                        //fprintf(stderr, "Not %s: '%c' != hexdigit for '%c'\n", expect_, *src, *expect);
                        return false;
                    }
                    ++src; ++expect;
                    break;
                case 'Y':if(*src>='0' && *src<='9') res.y = *src-'0'+0;
                    else if(*src>='A' && *src<='F') res.y = *src-'A'+10;
                    else if(*src>='a' && *src<='f') res.y = *src-'a'+10;
                    else {
                        //fprintf(stderr, "Not %s: '%c' != hexdigit for '%c'\n", expect_, *src, *expect);
                        return false;
                    }
                    ++src; ++expect;
                    break;
                case 'N':
                {
                    // Parse expression
                    std::unordered_set<std::string> params;
                    std::string subexpr = src;
                    int len = ParseAndDeduceVariables(subexpr, params);
                    if(fparser.GetParseErrorType() != fparser_t::FP_NO_ERROR && len > 0)
                    {
                        subexpr.erase(len, subexpr.size());
                        params.clear();
                        len = ParseAndDeduceVariables(subexpr, params);
                        if(fparser.GetParseErrorType() != fparser_t::FP_NO_ERROR)
                        {
                            //fprintf(stderr, "Not %s: Failed to parse '%s' (%s)\n", expect_, subexpr.c_str(), fparser.ErrorMsg());
                            return false;
                        }
                    }
                    if(len == -1) len = subexpr.size();
                    res.n = { subexpr.substr(0,len), std::move(params) };
                    src += len;
                    ++expect;
                    break;
                }
                case '\0': goto end;
                default:
                    if(*src != *expect)
                    {
                        //fprintf(stderr, "Not %s: '%c' != '%c'\n", expect_, *src, *expect);
                        return false;
                    }
                    ++src;
                    ++expect;
            }
        }
    end:
        while(std::isspace(*src)) ++src;
        if(*src)
        {
            //fprintf(stderr, "Not %s: Trailing '%c'\n", expect_, *src);
            return false;
        }
        res.pattern     = expect_;
        res.hex_pattern = hex_pattern;
        return true;
    };
    TestResult result;
    #define o(asm_pattern, hex_pattern) \
        if(Test(asm_pattern, hex_pattern, result)) \
            { CheckProgramLine(result); return result; }
    LIST_INSTRUCTIONS(o)
    #undef o
    CheckProgramLine(result);
    return result;
}

int main()
{
    std::vector<std::string> lines;
    std::unordered_map<std::string, std::string> defines;

    fparser.AddFunction("AND", [](const long*v) { return v[0] & v[1]; }, 2);
    fparser.AddFunction("OR",  [](const long*v) { return v[0] | v[1]; }, 2);
    fparser.AddFunction("XOR", [](const long*v) { return v[0] ^ v[1]; }, 2);
    fparser.AddFunction("SHR", [](const long*v) { return long((unsigned long)v[0] >> v[1]); }, 2);
    fparser.AddFunction("SHL", [](const long*v) { return long((unsigned long)v[0] << v[1]); }, 2);
    fparser.AddFunction("NOT", [](const long*v) { return ~v[0]; }, 1);

    unsigned PC = 0x200;
    while(std::cin.good())
    {
        #define _(s,n) (((n)==(s).npos)?(s).size():(n))
        std::string s;
        std::getline(std::cin,s);
        std::string line = s;
        // Strip comments
        s.erase(_(s,s.find(';')), s.npos);
        // Strip leading and trailing whitespace
        s.erase(_(s,s.find_last_not_of(" \n\r\t")+1), s.size());
        s.erase(0, _(s,s.find_first_not_of(" \n\r\t")));
        // Replace possible defines with their definitions
        for(const auto& d: defines)
            for(unsigned start=0;;)
            {
                auto p = s.find(d.first, start), end = p + d.first.size();
                if(p == s.npos) break;
                if((p == 0 || !std::isalnum(s[p-1]))
                && (s.size() == end || !std::isalnum(s[end])))
                {
                    s.replace(p, d.first.size(), d.second);
                    start += d.second.size();
                }
                else
                    start += d.first.size();
            }
        bool labels_accepted = true;
re_begin_line:;
        // Capture the first word
        std::string firstword(s, 0, s.find_first_not_of(alpha+"."));
        // Identify the symbol that comes after the first word
        auto nextword_start = s.find_first_not_of(" \n\r\t", firstword.size());
        if(nextword_start != s.npos)
        {
            // If it's a ".define", record the define
            if(firstword == ".define")
            {
                // Delete .define and the whitespace that follows it
                s.erase(0, nextword_start);
                // Take the .define name and delete it from source
                std::string name(s, 0, s.find_first_not_of(alpha));
                s.erase(0, _(s,s.find_first_not_of(" \n\r\t", name.size())));
                if(!name.empty()) defines.insert({name,s});
                continue;
            }
            // Was it a label?
            if(s[nextword_start] == ':' && labels_accepted)
            {
                // Add label
                char Buf[64];
                std::sprintf(Buf, "%u", PC);
                DefineExpression(firstword, Buf);
                // Delete label and restart parsing of line
                s.erase(0, _(s,s.find_first_not_of(" \n+r\t", nextword_start+1)));
                // Did the label begin with '@'? If not, undefine all known @-labels
                if(firstword[0] != '@')
                    for(auto i=defined_identifiers.begin(); i != defined_identifiers.end(); )
                        if((*i)[0] == '@')
                            { fparser.RemoveIdentifier(*i); i = defined_identifiers.erase(i); }
                        else
                            ++i;
                goto re_begin_line;
            }
            // Was it a variable definition?
            if(s[nextword_start] == '=')
            {
                // Capture the expression
                s.erase(0, _(s,s.find_first_not_of(" \n+r\t", nextword_start+1)));
                DefineExpression(firstword, s);
                continue;
            }
            int literal_size=0;
            if(firstword == ".byte" || firstword == ".string" || firstword == ".db") { literal_size=1; goto literal; }
            if(firstword == ".word" || firstword == ".dw") { literal_size=2; goto literal; }
            if(firstword == ".long" || firstword == ".dd") { literal_size=4; goto literal; }
            if(literal_size)
            {
            literal:
                // Delete .byte
                s.erase(0, _(s,s.find_first_not_of(" \n+r\t", nextword_start)));
                const char* src = s.c_str();
                while(*src)
                {
                    if(*src==' ' || *src=='\t') { ++src; continue; }
                    if(*src=='"' && literal_size == 1)
                    {
                        ++src;
                        while(*src && *src != '"')
                        {
                            if(*src == '\\' && src[1]) ++src;
                            TestResult res;
                            res.compiled = (unsigned char)*src++;
                            res.bytes    = 1;
                            CheckProgramLine(res);
                            program.push_back(res); ++PC;
                        }
                        if(*src == '"') ++src;
                        continue;
                    }
                    if(*src==',') { ++src; continue; }
                    // Parse expression
                    std::unordered_set<std::string> params;
                    std::string subexpr = src;
                    int len = ParseAndDeduceVariables(subexpr, params);
                    if(fparser.GetParseErrorType() != fparser_t::FP_NO_ERROR && len > 0)
                    {
                        subexpr.erase(len, subexpr.size());
                        params.clear();
                        len = ParseAndDeduceVariables(subexpr, params);
                        if(fparser.GetParseErrorType() != fparser_t::FP_NO_ERROR)
                        {
                            std::string msg = fparser.ErrorMsg();
                            std::fprintf(stderr, "%s in expression: %s\n%*s\n",
                                msg.c_str(), subexpr.c_str(),
                                int(msg.size() + 16 + len + 1), "^");
                            break;
                        }
                    }
                    else if(len == 0)
                    {
                        std::string msg = fparser.ErrorMsg();
                        std::fprintf(stderr, "%s in expression: %s\n%*s\n",
                            msg.c_str(), subexpr.c_str(),
                            int(msg.size() + 16 + len + 1), "^");
                        break;
                    }
                    if(len == -1) len = subexpr.size();
                    TestResult res;
                    res.n = { subexpr.substr(0,len), std::move(params) };
                    res.pattern     = literal_size == 4 ? ".long"    : (literal_size == 2 ? ".word" : ".byte");
                    res.hex_pattern = literal_size == 4 ? "NNNNNNNN" : (literal_size == 2 ? "NNNN"  : "NN");
                    CheckProgramLine(res);
                    program.push_back(res); ++PC;
                    src += len;
                }
                continue;
            }
        }

        if(s.empty()) continue;
        // Compile the line.
        auto colon = s.find(':');
        std::string rest;
        if(colon != s.npos) { rest = s.substr(colon+1); s.erase(colon,s.npos); }

        auto res = MatchInstruction(s);
        if(!res.hex_pattern && !res.bytes)
            std::fprintf(stderr, "Unrecognized instruction: %s - line: %s\n", s.c_str(), line.c_str());
        else
        {
            program.push_back(res);
            PC += res.bytes;
        }
        if(!rest.empty())
        {
            labels_accepted = false;
            s = std::move(rest);
            // Strip leading and trailing whitespace
            s.erase(_(s,s.find_last_not_of(" \n\r\t")+1), s.size());
            s.erase(0, _(s,s.find_first_not_of(" \n\r\t")));
            goto re_begin_line;
        }
    }
    if(!saved_expressions.empty())
    {
        std::fprintf(stderr, "Unresolved expressions:\n");
        for(const auto& e: saved_expressions)
            std::fprintf(stderr, "  %s = %s\n", e.first.c_str(), e.second.first.c_str());
    }
    bool has_uncompiled = false;
    for(const auto& line: program)
        if(line.hex_pattern)
            { has_uncompiled = true; break; }
    if(has_uncompiled)
    {
        std::fprintf(stderr, "Uncompilable lines due to unresolved expressions:\n");
        for(const auto& line: program)
            if(line.hex_pattern)
                std::fprintf(stderr, "%s\n", line.Decompile().c_str());
    }
    for(const auto& line: program)
        for(unsigned n=line.bytes; n-- > 0; )
        {
            unsigned char byte = line.compiled >> (n*8);
            std::cout.put(byte);
        }
}