GCHQ_challenge.cpp

#include <array>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <functional>
#include <cassert>
#include "memory_content.hpp"

// opcode | instruction | operands (mod 0) | operands (mod 1)
// -------+-------------+------------------+-----------------
// 0x00   | jmp         | r1               | r2:r1
// 0x01   | movr        | r1, r2           | rx,   imm 
// 0x02   | movm        | r1, [ds:r2]      | [ds:r1], r2
// 0x03   | add         | r1, r2           | r1,   imm
// 0x04   | xor         | r1, r2           | r1,   imm 
// 0x05   | cmp         | r1, r2           | r1,   imm 
// 0x06   | jmpe        | r1               | r2:r1
// 0x07   | hlt         | N/A              | N/A

enum class OpCodes_e
{
    op_jmp = 0x00,
    op_movr = 0x01,
    op_movm = 0x02,
    op_add = 0x03,
    op_xor = 0x04,
    op_cmp = 0x05,
    op_jmpe = 0x06,
    op_hlt = 0x07
};

const auto IsJump = [](const OpCodes_e opcode)
{
    switch(opcode)
    {
    case OpCodes_e::op_jmp:
    case OpCodes_e::op_jmpe:
        return true;
    default:
        return false;
    }
};

/// Segmented memory model with 16-byte segment size (notation seg:offset)
const int seg_size = 16;
/// Total memory size    
const int memory_size = 16 * 256;

/// Type of the memory unit.
using TMemory = unsigned char;

enum class Registers_e
{
    R0 = 0,/// 4 general-purpose registers (r0-r3)
    R1 = 1,/// 4 general-purpose registers (r0-r3)
    R2 = 2,/// 4 general-purpose registers (r0-r3)
    R3 = 3,/// 4 general-purpose registers (r0-r3)
    R4 = 4, CS = 4, /// Code Segment register index (r4)
    R5 = 5, DS = 5 /// Data Segment register index (r5)
};

enum class Modifier_e
{
    ZERO, 
    ONE
};

class Registers final : public std::array<TMemory, 6>
{
public:
    Registers() :std::array<TMemory, 6>() { }
    Registers withValue(const Registers_e reg, const TMemory value) const
    {
        Registers new_registers = *this;
        new_registers.at(static_cast<char>(reg)) = value;
        return new_registers;
    }
};

class Memory final : public std::array<TMemory, memory_size>
{
public:
    Memory() :std::array<TMemory, memory_size>() { }
    Memory(std::array<TMemory, memory_size> && init) :std::array<TMemory, memory_size>(init) { }
    Memory withValue(const size_t location, const TMemory value) const
    {
        Memory new_mem = *this;
        new_mem.at(location) = value;
        return new_mem;
    }
};

class Cpu final
{
private:
    /*const*/ Registers registers;
    Cpu(const TMemory _ip, const Registers &_registers, const TMemory _fl) :
        ip(_ip),
        registers(_registers),
        fl(_fl)
    {
    }
public:
    bool isFlagZero() const { return fl == 0; }
    /*const*/ TMemory ip; //< Instruction pointer
    /*const*/ TMemory fl; //< 1 flags register (fl)

    TMemory getRegister(const Registers_e reg) const
    {
        return registers.at(static_cast<char>(reg));
    }

    Cpu withRegister(const Registers_e reg, const TMemory value) const
    {
        return Cpu{ ip, registers.withValue(reg, value), fl };
    }

    Cpu withIp(const TMemory new_ip) const
    {
        return Cpu{ new_ip, registers, fl };
    }

    Cpu withFl(const TMemory new_fl) const
    {
        return Cpu{ ip, registers, new_fl };
    }

    std::string toString() const
    {
        std::ostringstream oss;
        oss << "r0-r5: " << std::hex << getRegister(Registers_e::R0) << ", "
            << getRegister(Registers_e::R1) << ", "
            << getRegister(Registers_e::R2) << ", "
            << getRegister(Registers_e::R3) << ", "
            << getRegister(Registers_e::R4) << ", "
            << getRegister(Registers_e::R5) << ", fl=" << std::dec
            << this->fl << ", ip=" << std::hex << this->ip;
        return oss.str();
    }

    static Cpu New()
    {
        return Cpu{ 0, Registers{}, 0 };
    }
};

#pragma warning(disable:4510) // warning C4510: 'Vm' : default constructor could not be generated
#pragma warning(disable:4610) //  warning C4610: class 'Vm' can never be instantiated - user defined constructor required
class Vm final
{
public:
    Cpu cpu;
    Memory mem;
    OpCodes_e getCurrentOpCode() const
    {
        return static_cast<OpCodes_e>((this->getCurrentInstruction() >> 5) & 0x7);
    }
    Modifier_e getCurrentModifier() const
    {
        return static_cast<Modifier_e>((this->getCurrentInstruction() >> 4) & 0x1);
    }
    TMemory getCurrentInstruction() const
    {
        const size_t location = cpu.getRegister(Registers_e::CS) * 16 + cpu.ip;
        return mem.at(location);
    }
    TMemory getNextInstruction() const
    {
        const size_t location = cpu.getRegister(Registers_e::CS) * 16 + (cpu.ip + 1);
        return mem.at(location);
    }
    size_t getIpIncrease() const
    {
        if(IsJump(this->getCurrentOpCode()) && this->getCurrentModifier() == Modifier_e::ZERO)
            return 1;
        return 2;
    };
};

#if _DEBUG
#define log() std::cout << __FUNCTION__ << "\t" << vm.cpu.toString() << std::endl;
#else
#define log()
#endif

namespace opcode
{
    // operand1 is always a register index
    // operand2 is optional, depending upon the instruction set specified below
    // the value of mod alters the meaning of any operand2
    //   0: operand2 = reg ix
    //   1: operand2 = fixed immediate value or target segment (depending on instruction)
    Vm Nop(const Vm& vm)
    {
        log();
        return vm;
    }

    Vm JmpR1(const Vm& vm, const Registers_e r1)
    {
        log();
        const TMemory new_ip = vm.cpu.getRegister(r1);
        return Vm{ vm.cpu.withIp(new_ip), vm.mem };
    }

    Vm JmpR1R2(const Vm& vm, const Registers_e r1, const TMemory r2)
    {
        log();
        const TMemory new_ip = vm.cpu.getRegister(r1);
        const Cpu cpu = vm.cpu
            .withIp(new_ip)
            .withRegister(Registers_e::CS, r2);
        return Vm{ cpu, vm.mem };
    }

    Vm JmpeR1(const Vm& vm, const Registers_e r1)
    {
        log();
        if(vm.cpu.isFlagZero())
            return JmpR1(vm, r1);
        return vm;
    }

    Vm JmpeR1R2(const Vm& vm, const Registers_e r1, const TMemory r2)
    {
        log();
        if(vm.cpu.isFlagZero())
            return JmpR1R2(vm, r1, r2);
        return vm;
    }

    Vm Cmp(const Vm& vm, const Registers_e r1, const TMemory r2)
    {
        log();
        const TMemory new_fl = [&]() -> TMemory {
            if(vm.cpu.getRegister(r1) == r2)
                return 0;
            if(vm.cpu.getRegister(r1) < r2)
                return 0xFF;
            return 1;
        }();
        return Vm{ vm.cpu.withFl(new_fl), vm.mem };
    }

    Vm Movr(const Vm& vm, const Registers_e r1, const TMemory imm)
    {
        log();
        return Vm{ vm.cpu.withRegister(r1, imm), vm.mem };
    }

    Vm Movm0(const Vm& vm, const Registers_e r1, const Registers_e r2)
    {
        log();
        const size_t location = vm.cpu.getRegister(Registers_e::DS) * seg_size + vm.cpu.getRegister(r2);
        const TMemory val = vm.mem.at(location);
        const Cpu cpu = vm.cpu.withRegister(r1, val);
        return Vm{ cpu, vm.mem };
    }

    Vm Movm1(const Vm& vm, const Registers_e r1, const Registers_e r2)
    {
        log();
        const size_t location = vm.cpu.getRegister(Registers_e::DS) * seg_size + vm.cpu.getRegister(r1);
        const TMemory val = vm.cpu.getRegister(r2);
        const Memory mem = vm.mem.withValue(location, val);
        return Vm{ vm.cpu, mem };
    }

    Vm Add(const Vm& vm, const Registers_e r1, const TMemory imm)
    {
        log();
        const TMemory r1_val = vm.cpu.getRegister(r1);
        const Cpu cpu = vm.cpu.withRegister(r1, (r1_val + imm) & 0xFF);
        return Vm{ cpu, vm.mem };
    }

    Vm Xor(const Vm& vm, const Registers_e r1, const TMemory imm)
    {
        log();
        const TMemory r1_val = vm.cpu.getRegister(r1);
        const Cpu cpu = vm.cpu.withRegister(r1, r1_val ^ imm);
        return Vm{ cpu, vm.mem };
    }
}

#pragma warning(disable:4512) // warning C4512: 'Executor' : assignment operator could not be generated
class Executor final
{
    Vm executeOpcode(Vm vm) const
    {
        const TMemory byte1 = vm.getCurrentInstruction();
        const OpCodes_e opcode = vm.getCurrentOpCode();
        const Modifier_e current_modifier = vm.getCurrentModifier();
        const TMemory next_instruction = vm.getNextInstruction();
        const Registers_e operand1 = static_cast<Registers_e>(byte1 & 0xF);
        const TMemory operand2 = [&](){
            if(!IsJump(opcode) && current_modifier == Modifier_e::ZERO)
                return vm.cpu.getRegister(static_cast<Registers_e>(next_instruction));
            return next_instruction;
        }();
        const TMemory new_ip = vm.cpu.ip + vm.getIpIncrease() & 0xFF;
        vm = Vm{ vm.cpu.withIp(new_ip), vm.mem };

        using std::placeholders::_1;
        switch(opcode)
        {
        case OpCodes_e::op_movr:
            return opcode::Movr(vm, operand1, operand2);
        case OpCodes_e::op_add:
            return opcode::Add(vm, operand1, operand2);
        case OpCodes_e::op_xor:
            return opcode::Xor(vm, operand1, operand2);
        case OpCodes_e::op_cmp:
            return opcode::Cmp(vm, operand1, operand2);
        case OpCodes_e::op_hlt:
            return opcode::Nop(vm);
        case OpCodes_e::op_jmp: switch(current_modifier) {
            case Modifier_e::ZERO:
                return opcode::JmpR1(vm, operand1);
            case Modifier_e::ONE:
                return opcode::JmpR1R2(vm, operand1, operand2);
        }
        case OpCodes_e::op_jmpe: switch(current_modifier) {
            case Modifier_e::ZERO:
                return opcode::JmpeR1(vm, operand1);
            case Modifier_e::ONE:
                return opcode::JmpeR1R2(vm, operand1, operand2);
            }
        case OpCodes_e::op_movm: switch(current_modifier) {
            case Modifier_e::ZERO:
                return opcode::Movm0(vm, operand1, static_cast<Registers_e>(next_instruction));
            case Modifier_e::ONE:
                return opcode::Movm1(vm, operand1, static_cast<Registers_e>(next_instruction));
        }
        default:
            throw std::logic_error("Unexpected opcode");
        }
    }
public:
    const Vm _vm;
    Vm run() const
    {
        Vm vm = _vm;
        while(vm.getCurrentOpCode() != OpCodes_e::op_hlt)
        {
            vm = executeOpcode(vm);
        }
        return vm;
    }
};

static Memory executeProgram(const Memory &mem)
{
    const Cpu cpu = Cpu::New().withRegister(Registers_e::DS, 0x10);
    const Executor executor{ Vm{ cpu, mem } };
    const Vm vm = executor.run();
    return vm.mem;
}

template<class TType, int Size>
static Memory initializeMemory(const TType(&initial_content)[Size])
{
    Memory memory;
    std::copy(initial_content, initial_content + Size, memory.begin());
    return memory;
}

static const char *expected_result{ "GET /da75370fe15c4148bd4ceec861fbdaa5.exe HTTP/1.0" };

int main()
{
    const Memory mem = executeProgram(initializeMemory(memory_content));
    
    // Unit tests ;-)
    assert(std::equal(expected_result, expected_result + sizeof(expected_result),
                      mem.begin() + 448,
                      [](const TMemory a, const char b)
    {
        return a == b;
    }));
    std::ostream_iterator<TMemory> out_it(std::cout, "");
    std::copy(mem.begin() + 448, mem.begin() + 498, out_it);
    std::cout << std::endl;

    return 0;
}

memory_content.hpp

#pragma once

const unsigned char memory_content[] = {
    0x31, 0x04, 0x33, 0xaa, 0x40, 0x02, 0x80, 0x03, 0x52, 0x00, 0x72, 0x01, 0x73, 0x01, 0xb2, 0x50,
    0x30, 0x14, 0xc0, 0x01, 0x80, 0x00, 0x10, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x98, 0xab, 0xd9, 0xa1, 0x9f, 0xa7, 0x83, 0x83, 0xf2, 0xb1, 0x34, 0xb6, 0xe4, 0xb7, 0xca, 0xb8,
    0xc9, 0xb8, 0x0e, 0xbd, 0x7d, 0x0f, 0xc0, 0xf1, 0xd9, 0x03, 0xc5, 0x3a, 0xc6, 0xc7, 0xc8, 0xc9,
    0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9,
    0xda, 0xdb, 0xa9, 0xcd, 0xdf, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9,
    0x26, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9,
    0x7d, 0x1f, 0x15, 0x60, 0x4d, 0x4d, 0x52, 0x7d, 0x0e, 0x27, 0x6d, 0x10, 0x6d, 0x5a, 0x06, 0x56,
    0x47, 0x14, 0x42, 0x0e, 0xb6, 0xb2, 0xb2, 0xe6, 0xeb, 0xb4, 0x83, 0x8e, 0xd7, 0xe5, 0xd4, 0xd9,
    0xc3, 0xf0, 0x80, 0x95, 0xf1, 0x82, 0x82, 0x9a, 0xbd, 0x95, 0xa4, 0x8d, 0x9a, 0x2b, 0x30, 0x69,
    0x4a, 0x69, 0x65, 0x55, 0x1c, 0x7b, 0x69, 0x1c, 0x6e, 0x04, 0x74, 0x35, 0x21, 0x26, 0x2f, 0x60,
    0x03, 0x4e, 0x37, 0x1e, 0x33, 0x54, 0x39, 0xe6, 0xba, 0xb4, 0xa2, 0xad, 0xa4, 0xc5, 0x95, 0xc8,
    0xc1, 0xe4, 0x8a, 0xec, 0xe7, 0x92, 0x8b, 0xe8, 0x81, 0xf0, 0xad, 0x98, 0xa4, 0xd0, 0xc0, 0x8d,
    0xac, 0x22, 0x52, 0x65, 0x7e, 0x27, 0x2b, 0x5a, 0x12, 0x61, 0x0a, 0x01, 0x7a, 0x6b, 0x1d, 0x67,
    0x75, 0x70, 0x6c, 0x1b, 0x11, 0x25, 0x25, 0x70, 0x7f, 0x7e, 0x67, 0x63, 0x30, 0x3c, 0x6d, 0x6a,
    0x01, 0x51, 0x59, 0x5f, 0x56, 0x13, 0x10, 0x43, 0x19, 0x18, 0xe5, 0xe0, 0xbe, 0xbf, 0xbd, 0xe9,
    0xf0, 0xf1, 0xf9, 0xfa, 0xab, 0x8f, 0xc1, 0xdf, 0xcf, 0x8d, 0xf8, 0xe7, 0xe2, 0xe9, 0x93, 0x8e,
    0xec, 0xf5, 0xc8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x37, 0x7a, 0x07, 0x11, 0x1f, 0x1d, 0x68, 0x25, 0x32, 0x77, 0x1e, 0x62, 0x23, 0x5b, 0x47, 0x55,
    0x53, 0x30, 0x11, 0x42, 0xf6, 0xf1, 0xb1, 0xe6, 0xc3, 0xcc, 0xf8, 0xc5, 0xe4, 0xcc, 0xc0, 0xd3,
    0x85, 0xfd, 0x9a, 0xe3, 0xe6, 0x81, 0xb5, 0xbb, 0xd7, 0xcd, 0x87, 0xa3, 0xd3, 0x6b, 0x36, 0x6f,
    0x6f, 0x66, 0x55, 0x30, 0x16, 0x45, 0x5e, 0x09, 0x74, 0x5c, 0x3f, 0x29, 0x2b, 0x66, 0x3d, 0x0d,
    0x02, 0x30, 0x28, 0x35, 0x15, 0x09, 0x15, 0xdd, 0xec, 0xb8, 0xe2, 0xfb, 0xd8, 0xcb, 0xd8, 0xd1,
    0x8b, 0xd5, 0x82, 0xd9, 0x9a, 0xf1, 0x92, 0xab, 0xe8, 0xa6, 0xd6, 0xd0, 0x8c, 0xaa, 0xd2, 0x94,
    0xcf, 0x45, 0x46, 0x67, 0x20, 0x7d, 0x44, 0x14, 0x6b, 0x45, 0x6d, 0x54, 0x03, 0x17, 0x60, 0x62,
    0x55, 0x5a, 0x4a, 0x66, 0x61, 0x11, 0x57, 0x68, 0x75, 0x05, 0x62, 0x36, 0x7d, 0x02, 0x10, 0x4b,
    0x08, 0x22, 0x42, 0x32, 0xba, 0xe2, 0xb9, 0xe2, 0xd6, 0xb9, 0xff, 0xc3, 0xe9, 0x8a, 0x8f, 0xc1,
    0x8f, 0xe1, 0xb8, 0xa4, 0x96, 0xf1, 0x8f, 0x81, 0xb1, 0x8d, 0x89, 0xcc, 0xd4, 0x78, 0x76, 0x61,
    0x72, 0x3e, 0x37, 0x23, 0x56, 0x73, 0x71, 0x79, 0x63, 0x7c, 0x08, 0x11, 0x20, 0x69, 0x7a, 0x14,
    0x68, 0x05, 0x21, 0x1e, 0x32, 0x27, 0x59, 0xb7, 0xcf, 0xab, 0xdd, 0xd5, 0xcc, 0x97, 0x93, 0xf2,
    0xe7, 0xc0, 0xeb, 0xff, 0xe9, 0xa3, 0xbf, 0xa1, 0xab, 0x8b, 0xbb, 0x9e, 0x9e, 0x8c, 0xa0, 0xc1,
    0x9b, 0x5a, 0x2f, 0x2f, 0x4e, 0x4e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

C++ implementation of https://gist.github.com/markusl/1490780