// Autoplay guess the number using binary search in hex #include #include #include #include #include using namespace std::string_literals; const static std::string program = // Each line is 32 bytes. 'English' version at the bottom of the page "\x00\x43\x6F\x6D\x70\x75\x74\x65\x72\x27\x73\x20\x67\x75\x65\x73\x73\x3A\x20\x00\x48\x69\x67\x68\x65\x72\x0A\x00\x4C\x6F\x77\x65"s "\x72\x0A\x00\x59\x6F\x75\x20\x67\x75\x65\x73\x73\x65\x64\x20\x63\x6F\x72\x72\x65\x63\x74\x6C\x79\x21\x0A\x00\x54\x68\x69\x73\x20"s "\x70\x72\x6F\x67\x72\x61\x6D\x20\x69\x73\x20\x77\x72\x69\x74\x74\x65\x6E\x20\x69\x6E\x20\x68\x65\x78\x20\x62\x79\x20\x44\x65\x6E"s "\x6E\x69\x73\x20\x77\x69\x74\x68\x20\x63\x75\x73\x74\x6F\x6D\x20\x43\x50\x55\x20\x6F\x70\x63\x6F\x64\x65\x73\x20\x61\x6E\x64\x20"s "\x74\x61\x6B\x65\x73\x20\x75\x70\x20\x6F\x6E\x6C\x79\x20\x32\x35\x36\x20\x62\x79\x74\x65\x73\x2E\x0A\x0A\x00\x75\x00\x00\x00\x00"s "\x00\x00\x00\x49\x4A\x4B\x13\x00\x14\xFF\x02\x13\x3E\x4B\x18\x23\x0A\x1C\x3A\x01\x00\x03\xE6\x00\x02\x02\x02\x11\x0A\x2A\x47\x9B"s "\x0D\x8C\x3A\x1C\x00\x03\xE6\x00\x02\x11\x0A\x40\x35\x45\x5D\x3A\x14\x00\x03\xE6\x00\x02\x11\x0A\x3F\x32\x45\x50\x3A\x23\x00\x03"s "\xE6\x00\x07\x06\x05\x29\x17\x49\x12\x00\x3C\x2A\x47\x84\x02\x01\x3B\x45\x76\x05\x18\x29\x3A\x3B\x00\x03\xE6\x00\x03\xA3\x00\x01"s; /* Line 1 - 5 are all string literals, they take up most of the memory Line 6 contains the entry point of the guess-the-number function at a local offset of 0x03 ( 0xA3 globally ( 6 - 1 ) * 32 + 3 ) Line 7 is still part of the function Line 8 the function ends at a local offset of 0x05 ( 0xE5 globally ) Another function's entry point is located at a local offset 0x06 ( 0xE6 globally ) that prints strings and ends at a local offset of 0x15 ( 0xF5 globally ) CPU entry point is located at a local offset of 0x16 ( 0xF6 globally ) which displays a message, calls the guess-the-number function and then terminates the program. The program takes up 32 bytes * 8 lines = 256 bytes. ( Still have 8 bytes that are unused, so actually 248 bytes ) */ /* Opcodes: 0x00: NOP 0x01: Shutdown CPU 0x02: Interrupt 0x03: Call 0x04: Pop to B 0x05: Pop to C 0x06: Pop to D 0x07: Pop to E 0x08: Pop to H 0x09: Pop to L 0x0A: Shift A Right 0x0B: Shift A Left 0x0C: Jump by signed offset if Carry flag is reset 0x0D: Jump by signed offset if Carry flag is set 0x10: Load Immediate to A 0x11: Load Immediate to B 0x12: Load Immediate to C 0x13: Load Immediate to D 0x14: Load Immediate to E 0x15: Load Immediate to H 0x16: Load Immediate to L 0x17: Push A to the stack 0x18: Pop to A 0x1A: Add B to A 0x1B: Add C to A 0x1C: Add D to A 0x1D: Add E to A 0x1E: Add H to A 0x1F: Add L to A 0x20: Add A to A 0x21: Sub B from A 0x22: Sub C from A 0x23: Sub D from A 0x24: Sub E from A 0x25: Sub H from A 0x26: Sub L from A 0x27: Sub A from A 0x28: Jump to 16 bit address 0x29: Return 0x2A: Compare A with C, Zero flag set if result of subtraction is 0, otherwise the Zero flag is reset. If a carry occurs the Carry flag is set, otherwise reset 0x2B: Jump if Zero flag is reset, (th jump if set see 0x43 ) 0x2C: Increment A 0x2D: Decrement A 0x2E: Increment B 0x2F: Decrement B 0x30: Increment C 0x31: Decrement C 0x32: Increment D 0x33: Decrement D 0x34: Increment E 0x35: Decrement E 0x36: Increment H 0x37: Decrement H 0x38: Increment L 0x39: Decrement L 0x3A: Load immediate to HL 0x3B: Increment pointer in HL 0x3C: Store value pointed to by HL into A 0x3D: Copy A to B 0x3E: Copy A to C 0x3F: Copy A to D 0x40: Copy A to E 0x41: Copy A to H 0x42: Copy A to L 0x43: Jump if Zero flag is set 0x44: Decrement pointer in HL 0x45: Jump by signed offset 0x46: Jump by signed offset if Zero flag is reset 0x47: Jump by signed offset if Zero flag is set 0x48: Push B to stack 0x49: Push C to stack 0x4A: Push D to stack 0x4B: Push E to stack 0x4C: Push H to stack 0x4D: Push L to stack 0x4E: Push HL to stack 0x4F: Pop to HL */ using u16 = unsigned short; using u8 = unsigned char; using s8 = signed char; namespace Dennis { // Returns number of clock cycles of the cpu, used to seed random number generator uint64_t rdtsc() { uint32_t l, h; __asm__ __volatile__( "rdtsc" : "=a"(l), "=d"(h) ); return (uint64_t)h << 32 | l; } // Utility class class Random { public: template static T getRandom( T min, T max ); private: static std::mt19937 m_mt; }; std::mt19937 Random::m_mt( rdtsc() ); template T Random::getRandom( T min, T max ) { static_assert( std::is_integral() || std::is_floating_point(), "T must either be an integral or a floating point!"); return typename std::conditional< std::is_integral::value, std::uniform_int_distribution, std::uniform_real_distribution >::type( min, max )( m_mt ); } class CPUEmulator { private: enum class Flag : u8 { Zero = 1 << 0, // Used by the compare opcode ( 0x2A ), will be set if A == C Negative = 1 << 1, // Not used, yet Carry = 1 << 2, // Used by the compare opcode ( 0x2A ), will be set if A < C Shutdown = 1 << 7, // Shutdown flag for the cpu, ( just to prevent a time limit error ) }; // 1kb of memory to work with, mostly space for the stack pointer constexpr static u16 MemorySize = 0x400; public: explicit CPUEmulator(); void LoadProgram( const std::string& program ); int Execute(); private: void ExecuteInstruction( u8 opcode ); void SetFlag( Flag flag ); void ResetFlag( Flag flag ); bool GetFlag( Flag flag ) const; void InitializeCPU(); u8 ReadMemory( u16 index ); void WriteMemory( u16 index, u8 value ); void PushToStack( u16 value ); u16 PopFromStack(); u16 ReadImmediate16(); void HandleInterrupt(); private: union Register { u16 reg16; struct { u8 lo; u8 hi; }; } m_AF, m_BC, m_DE, m_HL, m_SP; u16 m_PC; std::unique_ptr m_Memory; }; CPUEmulator::CPUEmulator() : m_Memory( new u8[MemorySize] ) { } void CPUEmulator::LoadProgram( const std::string& program ) { std::copy( program.begin(), program.end(), m_Memory.get() ); } int CPUEmulator::Execute() { InitializeCPU(); while( !GetFlag( Flag::Shutdown ) ) { HandleInterrupt(); u8 opcode = ReadMemory( m_PC++ ); ExecuteInstruction( opcode ); } if( m_SP.reg16 != MemorySize - 2 ) { throw std::logic_error( "CPU ended with unbalanced Stack Pointer, expected "s + std::to_string( MemorySize - 2 ) + " but got "s + std::to_string( m_SP.reg16 ) + "."s ); } return m_AF.hi; } void CPUEmulator::ExecuteInstruction( u8 opcode ) { u8 temp; u16 temp16; // Micro opcode encodings ( these are read top to bottom, not left to right ) if("01000000000000000000000000000000000000000000000000000000000000000000000000000000"[opcode]=='1') SetFlag( Flag::Shutdown ); // Shutdown CPU if("00000000001100000000000100111111111111110010110000000000000001111110000000000000"[opcode]=='1') temp = m_AF.hi; // Read a if("00000000000000000000000000000000000000000000001100000000000000000000000010000000"[opcode]=='1') temp = m_BC.hi; // Read b if("00000000000000000000000000000000000000000000000011000000000000000000000001000000"[opcode]=='1') temp = m_BC.lo; // Read c if("00000000000000000000000000000000000000000000000000110000000000000000000000100000"[opcode]=='1') temp = m_DE.hi; // Read d if("00000000000000000000000000000000000000000000000000001100000000000000000000010000"[opcode]=='1') temp = m_DE.lo; // Read e if("00000000000000000000000000000000000000000000000000000011000000000000000000001000"[opcode]=='1') temp = m_HL.hi; // Read h if("00000000000000000000000000000000000000000000000000000000110000000000000000000100"[opcode]=='1') temp = m_HL.lo; // Read l if("00000000000000000000000000000000000000000000000000000000000100000000100000000010"[opcode]=='1') temp16 = m_HL.reg16; // Read HL if("00000000000000000000000000000000000000000000000000000000000010000000000000000000"[opcode]=='1') temp = ReadMemory( m_HL.reg16 ); // Read value pointed to by HL if("00100000000011001111111000000000000000000000000000000000000000000000011100000000"[opcode]=='1') temp = ReadMemory( m_PC++ ); // Read immediate if("00010000000000000000000000000000000000001001000000000000001000000001000000000000"[opcode]=='1') temp16 = ReadImmediate16(); // Read immediate word if("00000000000000000000000000000000100000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_AF.hi; // Add a if("00000000000000000000000000100000000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_BC.hi; // Add b if("00000000000000000000000000010000000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_BC.lo; // Add c if("00000000000000000000000000001000000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_DE.hi; // Add d if("00000000000000000000000000000100000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_DE.lo; // Add e if("00000000000000000000000000000010000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_HL.hi; // Add h if("00000000000000000000000000000001000000000000000000000000000000000000000000000000"[opcode]=='1') temp += m_HL.lo; // Add l if("00000000000000000000000000000000000000010000000000000000000000000000000000000000"[opcode]=='1') temp -= m_AF.hi; // Sub a if("00000000000000000000000000000000010000000000000000000000000000000000000000000000"[opcode]=='1') temp -= m_BC.hi; // Sub b if("00000000000000000000000000000000001000000010000000000000000000000000000000000000"[opcode]=='1') temp -= m_BC.lo; // Sub c if("00000000000000000000000000000000000100000000000000000000000000000000000000000000"[opcode]=='1') temp -= m_DE.hi; // Sub d if("00000000000000000000000000000000000010000000000000000000000000000000000000000000"[opcode]=='1') temp -= m_DE.lo; // Sub e if("00000000000000000000000000000000000001000000000000000000000000000000000000000000"[opcode]=='1') temp -= m_HL.hi; // Sub h if("00000000000000000000000000000000000000100000000000000000000000000000000000000000"[opcode]=='1') temp -= m_HL.lo; // Sub l if("00000000000000000000000000000000000000000000101010101010100000000000000000000000"[opcode]=='1') ++temp; // Incr if("00000000000000000000000000000000000000000000010101010101010000000000000000000000"[opcode]=='1') --temp; // Decr if("00000000000000000000000000000000000000000000000000000000000100000000000000000000"[opcode]=='1') ++temp16; // Incr word( ptr ) if("00000000000000000000000000000000000000000000000000000000000000000000100000000000"[opcode]=='1') --temp16; // Decr word( ptr ) if("00100000000000000000000100000000000000000000000000000000000000000000000011111100"[opcode]=='1') WriteMemory( --m_SP.reg16, temp ); // Push value to stack if("00001111110000000000000010000000000000000000000000000000000000000000000000000000"[opcode]=='1') temp = ReadMemory( m_SP.reg16++ ); // Pop value from stack if("00010000000000000000000000000000000000000000000000000000000000000000000000000000"[opcode]=='1') PushToStack( m_PC ); // Push PC to stack if("00000000000000000000000000000000000000000100000000000000000000000000000000000000"[opcode]=='1') temp16 = PopFromStack(); // Pop PC from stack if("00000000000000000000000000000000000000000000000000000000000000000000000000000010"[opcode]=='1') PushToStack( temp16 ); // Push word to stack if("00000000000000000000000000000000000000000000000000000000000000000000000000000001"[opcode]=='1') temp16 = PopFromStack(); // Pop word from stack if("00010000000000000000000000000000000000001100000000000000000000000000000000000000"[opcode]=='1') m_PC = temp16; // Jump if("00000000000000000000000000000000000000000001000000000000000000000000000000000000"[opcode]=='1') m_PC = (GetFlag( Flag::Zero ) ? m_PC : temp16); // Jump if zero flag is not set if("00000000000000000000000000000000000000000000000000000000000000000001000000000000"[opcode]=='1') m_PC = (!GetFlag( Flag::Zero ) ? m_PC : temp16); // Jump if zero flag is set if("00000000000000000000000000000000000000000000000000000000000000000000010000000000"[opcode]=='1') m_PC += s8( temp - 127 ); // Offset jump if("00000000000000000000000000000000000000000000000000000000000000000000001000000000"[opcode]=='1') m_PC += ( GetFlag( Flag::Zero ) ? 0 : s8( temp - 127 )); // Offset jump if zero flag is not set if("00000000000000000000000000000000000000000000000000000000000000000000000100000000"[opcode]=='1') m_PC += (!GetFlag( Flag::Zero ) ? 0 : s8( temp - 127 )); // Offset jump if zero flag is set if("00000000000010000000000000000000000000000000000000000000000000000000000000000000"[opcode]=='1') m_PC += ( GetFlag( Flag::Carry ) ? 0 : s8( temp - 127 )); // Offset jump if carry flag is not set if("00000000000001000000000000000000000000000000000000000000000000000000000000000000"[opcode]=='1') m_PC += (!GetFlag( Flag::Carry ) ? 0 : s8( temp - 127 )); // Offset jump if carry flag is set if("00000000001000000000000000000000000000000000000000000000000000000000000100000000"[opcode]=='1') temp >>= 1; // Shift right by 1 if("00000000000100000000000000000000000000000000000000000000000000000000000100000000"[opcode]=='1') temp <<= 1; // Shift left by 1 if("00000000001100001000000011011111111111110000110000000000000010000000000000000000"[opcode]=='1') m_AF.hi = temp; // Store to a if("00001000000000000100000000000000000000000000001100000000000001000000000000000000"[opcode]=='1') m_BC.hi = temp; // Store to b if("00000100000000000010000000000000000000000000000011000000000000100000000000000000"[opcode]=='1') m_BC.lo = temp; // Store to c if("00000010000000000001000000000000000000000000000000110000000000010000000000000000"[opcode]=='1') m_DE.hi = temp; // Store to d if("00000001000000000000100000000000000000000000000000001100000000001000000000000000"[opcode]=='1') m_DE.lo = temp; // Store to e if("00000000100000000000010000000000000000000000000000000011000000000100000000000000"[opcode]=='1') m_HL.hi = temp; // Store to h if("00000000010000000000001000000000000000000000000000000000110000000010000000000000"[opcode]=='1') m_HL.lo = temp; // Store to l if("00000000000000000000000000000000000000000000000000000000001100000000100000000001"[opcode]=='1') m_HL.reg16 = temp16; // Store to HL if("00000000000000000000000000000000000000000010000000000000000000000000000000000000"[opcode]=='1') temp == 0 ? SetFlag( Flag::Zero ) : ResetFlag( Flag::Zero ); // Update Zero flag if("00000000000000000000000000000000000000000010000000000000000000000000000000000000"[opcode]=='1') temp > m_AF.hi ? SetFlag( Flag::Carry ) : ResetFlag( Flag::Carry ); // Update Carry flag if("00100000000000000000000000000000000000000000000000000000000000000000000000000000"[opcode]=='1') m_Memory[MemorySize - 1] = 1; // Call interrupt // Just some debugging checks if( m_SP.reg16 > MemorySize - 2 || m_SP.reg16 < 256 ) { throw std::logic_error( "Stack pointer entered an invalid area of memory, perhaps you are pushing too much to the stack? Memory: "s + std::to_string( m_SP.reg16 ) + "."s ); } if( m_PC > 256 ) { throw std::logic_error( "The program counter entered an invalid area of memory "s + std::to_string( m_PC ) + "."s ); } } void CPUEmulator::SetFlag( Flag flag ) { m_AF.lo |= static_cast( flag ); } void CPUEmulator::ResetFlag( Flag flag ) { m_AF.lo &= ~static_cast( flag ); } bool CPUEmulator::GetFlag( Flag flag ) const { return m_AF.lo & static_cast( flag ); } void CPUEmulator::InitializeCPU() { // Entrance point m_PC = 0xF6; // Setup stack pointer m_SP.reg16 = MemorySize - 2; // Last byte in memory is used to indicate if there is an interrupt m_Memory[ MemorySize - 1 ] = 0; m_AF.reg16 = 0x0100; m_BC.reg16 = 0x0013; m_DE.reg16 = 0x00D8; m_HL.reg16 = 0x00FF; } u8 CPUEmulator::ReadMemory( u16 index ) { return m_Memory[index]; } void CPUEmulator::WriteMemory( u16 index, u8 value ) { m_Memory[index] = value; } void CPUEmulator::PushToStack( u16 value ) { WriteMemory( --m_SP.reg16, value >> 8 ); WriteMemory( --m_SP.reg16, value & 0xFF ); } u16 CPUEmulator::PopFromStack() { u16 value = ReadMemory( m_SP.reg16 ) | ReadMemory( m_SP.reg16 + 1 ) << 8; m_SP.reg16 += 2; return value; } u16 CPUEmulator::ReadImmediate16() { u16 value = ReadMemory( m_PC + 1 ) << 8 | ReadMemory( m_PC ); m_PC += 2; return value; } void CPUEmulator::HandleInterrupt() { // Check if there is an interrupt to process if( m_Memory[MemorySize - 1] ) { // Get the specific interrupt from the stack and pop it u8 interrupt = ReadMemory( m_SP.reg16++ ); // Disable interrupt again m_Memory[MemorySize - 1] = 0; // Interrupts are usually located in the first part of memory in the interrupt vector table but this works too switch( interrupt ) { // Interrupt that print stuff case 0x01: std::cout << m_AF.hi; break; case 0x02: std::cout << (u16)m_AF.hi; break; case 0x03: std::cout << m_BC.hi; break; case 0x04: std::cout << (u16)m_BC.hi; break; case 0x05: std::cout << m_BC.lo; break; case 0x06: std::cout << (u16)m_BC.hi; break; case 0x07: std::cout << m_DE.hi; break; case 0x08: std::cout << (u16)m_DE.hi; break; case 0x09: std::cout << m_DE.lo; break; case 0x0A: std::cout << (u16)m_DE.lo; break; case 0x0B: std::cout << m_HL.hi; break; case 0x0C: std::cout << (u16)m_HL.hi; break; case 0x0D: std::cout << m_HL.lo; break; case 0x0E: std::cout << (u16)m_HL.lo; break; case 0x0F: { u8 tmp = ReadMemory( m_HL.reg16 ); std::cout << tmp; break; } case 0x10: { u8 tmp = ReadMemory( m_HL.reg16 ); std::cout << (u16)tmp; break; } case 0x11: { u8 immediate = ReadMemory( m_PC++ ); std::cout << immediate; break; } case 0x12: { u8 immediate = ReadMemory( m_PC++ ); std::cout << (u16)immediate; break; } // === // Returns rand between 0 and 255 case 0x13:{ m_AF.hi = Random::getRandom( 0, 255 ); break; } // Returns rand between x and y ( pops these values off the stack ) parameters should be pushed in reverse order case 0x14: { u16 word = PopFromStack(); u8 min = word & 0xFF, max = (word & 0xFF00) >> 8; m_AF.hi = Random::getRandom( min, max ); break; } // Take input case 0x15: { u16 tmp = 0; // [Removed input to prevent popup since I'm not using it anyway for this program] m_AF.hi = tmp & 0xFF; break; } } } } } int main() { if( program.size() != 256 ) { throw std::logic_error( "The program size is incorrect, expected a size of 256 but got "s + std::to_string( program.size() ) ); } Dennis::CPUEmulator cpu; cpu.LoadProgram( program ); return cpu.Execute(); // Returns the value in Register A, in this case the guessed number } /* Above program, a bit more readable: Guess_The_Number: Register A is storage for our guess Register C is target number Register D is lowest guess Register E is highest guess Push C: 0x49 Push D: 0x4A Push E: 0x4B Move 0 to D: 0x13 0x00 Move 255 to E: 0x14 0xFF Generate a random number and store it in C: Get random: 0x02 0x13 Copy A to C: 0x3E Loop: Make a guess: A = (E - D) / 2 + D: Copy E to A: 0x4B 0x18 Subtract D from A: 0x23 Shift A right: 0x0A Add D to A: 0x1C Print guess message: 0x3A 0x01 0x00 0x03 AddressOfPrint_string Print A as number: 0x02 0x02 Print newline: 0x02 0x11 0x0A Compare A with C: 0x2A Jump to Win if zero flag is set: 0x47 OffsetToWin Jump to Lower if carry flag is set: 0x0D OffsetToLower Higher: Display lower message: 0x3A 0x1C 0x00 0x03 AddressOfPrint_string Print newline: 0x02 0x11 0x0A Copy A to E: 0x40 Decrement E: 0x35 Jump to Loop: 0x45 OffsetToLoop Lower: Display higher message: 0x3A 0x14 0x00 0x03 AddressOfPrint_string Print newline: 0x02 0x11 0x0A Copy A to D: 0x3F Increment D: 0x32 Jump to Loop: 0x45 OffsetToLoop Win: Display win message 0x3A 0x23 0x00 0x03 AddressOfPrint_string End: Pop E: 0x07 Pop D: 0x06 Pop C: 0x05 Return: 0x29 Print_string: Register A Stores the character Register C Stores null character to compare to ( current CPU can only compare register A with C ) Register HL Stores the pointer to the beginning of a string array Push A: 0x17 Push C: 0x49 Move 0 to C: 0x12 Loop: Store value pointed to by HL in A: 0x3C Compare A with C: 0x2A Jump to End if A == 0: 0x47 OffsetToEnd Print character in A 0x02 0x01 Increment HL pointer 0x3B Jump to Loop: 0x45 OffsetToLoop End: Pop C: 0x05 Pop A: 0x18 Return: 0x29 CPU_Entry_Point: Load message address to HL 0x3A Address Call Print_string 0x03 AddressOfPrint_string Call Guess_The_Number 0x03 AddressOfGuess_The_Number Shutdown CPU 0x01 */

CPU Emulator