// MEMORY EMULATION

// ----------------

//

// Memory access emulation is a very important part of the CPU emulation.

// Because they happen so frequently they really need to be executed as fast as

// possible otherwise they will completely bring down the speed of the CPU

// emulation.

//

// A very fast way to emulate memory accesses is by simply reading/writing to a

// 64kb array (for a 16-bit address space). Unfortunately this doesn't allow

// for memory mapped IO (MMIO). These are memory regions where read/writes

// trigger side effects, so where we need to execute device-specific code on

// read or writes. An alternative that does work with MMIO is for every access

// execute a virtual method call, (this is the approach taken by most current

// MSX emulators). Unfortunately this is also a lot slower.

//

// It is possible to combine the speed of array accesses with the flexibility

// of virtual methods. In openMSX it's implemented as follows: the 64kb address

// space is divided in 256 regions of 256 bytes (called cacheLines in the code

// below). For each such region we store a pointer, if this pointer is nullptr

// then we have to use the slow way (=virtual method call). If it is not nullptr,

// the pointer points to a block of memory that can be directly accessed. In

// some contexts accesses via the pointer are known as backdoor accesses while

// the accesses directly to the device are known as front-door accesses.

//

// We keep different pointers for read and write accesses. This allows to also

// implement ROMs efficiently: read is handled as regular RAM, but writes end

// up in some dummy memory region. This region is called 'unmappedWrite' in the

// code. There is also a special region 'unmappedRead', this region is filled

// with 0xFF and can be used to model (parts of) a device that don't react to

// reads (so reads return 0xFF).

//

// Because of bank switching (the MSX slot select mechanism, but also e.g.

// MegaROM back switching) the memory map as seen by the Z80 is not static. This

// means that the cacheLine pointers also need to change during runtime. To

// solve this we made the bank switch code also responsible for invalidating the

// cacheLines of the switched region. These pointers are filled-in again in a

// lazy way: the first read or write to a cache line will first get this

// pointer (see getReadCacheLine() and getWriteCacheLine() in the code below),

// from then on this pointer is used for all further accesses to this region,

// until the cache is invalidated again.

//

//

// INSTRUCTION EMULATION

// ---------------------

//

// UPDATE: the 'threaded interpreter model' is not enabled by default

//         main reason is the huge memory requirement while compiling

//         and that it doesn't work on non-gcc compilers

//

// The current implementation is based on a 'threaded interpreter model'. In

// the text below I'll call the older implementation the 'traditional

// interpreter model'. From a very high level these two models look like this:

//

//     Traditional model:

//         while (!needExit()) {

//             uint8_t opcode = fetch(PC++);

//             switch (opcode) {

//                 case 0x00: nop(); break;

//                 case 0x01: ld_bc_nn(); break;

//                 ...

//             }

//         }

//

//     Threaded model:

//         uint8_t opcode = fetch(PC++);   //

//         goto *(table[opcode]);       // fetch-and-dispatch

//         // note: the goto * syntax is a gcc extension called computed-gotos

//

//         op00: nop();      if (!needExit()) [fetch-and-dispatch];

//         op01: ld_bc_nn(); if (!needExit()) [fetch-and-dispatch];

//         ...

//

// In the first model there is a central place in the code that fetches (the

// first byte of) the instruction and based on this byte jumps to the

// appropriate routine. In the second model, this fetch-and-dispatch logic is

// duplicated at the end of each instruction.

//

// Typically the 'dispatch' part in above paragraph is implemented (either by

// the compiler or manually using computed goto's) via a jump table. Thus on

// assembler level via an indirect jump. For the host CPU it's hard to predict

// the destination address of such an indirect jump, certainly if there's only

// one such jump for all dispatching (the traditional model). If each

// instruction has its own indirect jump instruction (the threaded model), it

// becomes a bit easier, because often one particular z80 instructions is

// followed by a specific other z80 instruction (or one from a small subset).

// For example a z80 'cp' instruction is most likely followed by a 'conditional

// jump' z80 instruction. Modern CPUs are quite sensitive to

// branch-(mis)predictions, so the above optimization helps quite a lot. I

// measured a speedup of more than 10%!

//

// There is another advantage to the threaded model. Because also the

// needExit() test is duplicated for each instruction, it becomes possible to

// tweak it for individual instructions. But first let me explain this

// exit-test in more detail.

//

// These are the main reasons why the emulator should stop emulating CPU

// instructions:

//  1) When other devices than the CPU must be emulated (e.g. video frame

//     rendering). In openMSX this is handled by the Scheduler class and

//     actually we don't exit the CPU loop (anymore) for this. Instead we

//     simply execute the device code as a subroutine. Each time right before

//     we access an IO port or do a front-door memory access, there is a check

//     whether we should emulate device code (search for schedule() in the code

//     below).

//  2) To keep the inner CPU loop as fast as possible we don't check for IRQ,

//     NMI or HALT status in this loop. Instead this condition is checked only

//     once at the beginning outside of the loop (if there wasn't a pending IRQ

//     on the first instruction there also won't be one on the second

//     instruction, if all we did was emulating cpu instructions). Now when one

//     of these conditions changes, we must exit the inner loop and re-evaluate

//     them. For example after an EI instruction we must check the IRQ status

//     again.

//  3) Various reasons like:

//      * Z80/R800 switch

//      * executing a Tcl command (could be a cpu-register debug read)

//      * exit the emulator

//  4) 'once-in-a-while': To avoid threading problems and race conditions,

//     several threads in openMSX only 'schedule' work that will later be

//     executed by the main emulation thread. The main thread checks for such

//     task outside of the cpu emulation loop. So once-in-a-while we need to

//     exit the loop. The exact timing doesn't matter here because anyway the

//     relative timing between threads is undefined.

// So for 1) we don't need to do anything (we don't actually exit). For 2) and

// 3) we need to exit the loop as soon as possible (right after the current

// instruction is finished). For 4) it's OK to exit 'eventually' (a few hundred

// z80 instructions late is still OK).

//

// Condition 2) is implemented with the 'slowInstructions' mechanism. Condition

// 3) via exitCPULoopSync() (may only get called by the main emulation thread)

// and condition 4) is implemented via exitCPULoopAsync() (can be called from

// any thread).

//

// Now back to the exit-test optimization: in the threaded model each

// instruction ends with:

//

//     if (needExit()) return

//     uint8_t opcode = fetch(PC++);

//     goto *(table[opcode]);

//

// And if we look in more detail at fetch():

//

//     if (canDoBackdoor(addr)) {

//         doBackdoorAccess(addr);

//     } else {

//         doFrontdoorAccess(addr);

//     }

//

// So there are in fact two checks per instruction. This can be reduced to only

// one check with the following trick:

//

// !!!WRONG!!!

// In the past we optimized this to only check canDoBackdoor() (and make sure

// canDoBackdoor() returned false when needExit() would return true). This

// worked rather well, except for one case: when we exit the CPU loop we also

// check for pending Syncronization points. It is possible such a SyncPoint

// raises the IRQ line. So it is important to check for exit after every

// instruction, otherwise we would enter the IRQ routine a couple of

// instructions too late.

#include "CPUCore.hh"

#include "Dasm.hh"

#include "MSXCPUInterface.hh"

#include "R800.hh"

#include "Z80.hh"

#include "MSXCliComm.hh"

#include "MSXMotherBoard.hh"

#include "Scheduler.hh"

#include "TclCallback.hh"

#include "Thread.hh"

#include "endian.hh"

#include "inline.hh"

#include "narrow.hh"

#include "unreachable.hh"

#include "xrange.hh"

#include <array>

#include <bit>

#include <cassert>

#include <iostream>

#include <type_traits>

//

// #define USE_COMPUTED_GOTO

//

// Computed goto's are not enabled by default:

// - Computed goto's are a gcc extension, it's not part of the official c++

//   standard. So this will only work if you use gcc as your compiler (it

//   won't work with visual c++ for example)

// - This is only beneficial on CPUs with branch prediction for indirect jumps

//   and a reasonable amount of cache. For example it is very beneficial for a

//   intel core2 cpu (10% faster), but not for a ARM920 (a few percent slower)

// - Compiling src/cpu/CPUCore.cc with computed goto's enabled is very demanding

//   on the compiler. On older gcc versions it requires up to 1.5GB of memory.

//   But even on more recent gcc versions it still requires around 700MB.

//

// Probably the easiest way to enable this, is to pass the -DUSE_COMPUTED_GOTO

// flag to the compiler. This is for example done in the super-opt flavour.

// See build/flavour-super-opt.mk

#ifndef _MSC_VER

  // [[maybe_unused]] on a label is not (yet?) officially part of c++

  // Gcc/clang do support it (as an extension), but visual studio complains

  // about it. Hence the different implementation for both.

  #define MAYBE_UNUSED_LABEL [[maybe_unused]]

#else

  #pragma warning(disable : 4102) // unreferenced label

  #define MAYBE_UNUSED_LABEL

#endif

namespace openmsx {

enum Reg8  : uint8_t { A, F, B, C, D, E, H, L, IXH, IXL, IYH, IYL, REG_I, REG_R, DUMMY };

enum Reg16 : uint8_t { AF, BC, DE, HL, IX, IY, SP };

// flag positions

static constexpr uint8_t S_FLAG = 0x80;

static constexpr uint8_t Z_FLAG = 0x40;

static constexpr uint8_t Y_FLAG = 0x20;

static constexpr uint8_t H_FLAG = 0x10;

static constexpr uint8_t X_FLAG = 0x08;

static constexpr uint8_t V_FLAG = 0x04;

static constexpr uint8_t P_FLAG = V_FLAG;

static constexpr uint8_t N_FLAG = 0x02;

static constexpr uint8_t C_FLAG = 0x01;

// flag-register lookup tables

struct Table {

	std::array<uint8_t, 256> ZS;

	std::array<uint8_t, 256> ZSXY;

	std::array<uint8_t, 256> ZSP;

	std::array<uint8_t, 256> ZSPXY;

	std::array<uint8_t, 256> ZSPH;

};

static constexpr uint8_t ZS0     = Z_FLAG;

static constexpr uint8_t ZSXY0   = Z_FLAG;

static constexpr uint8_t ZSP0    = Z_FLAG | V_FLAG;

static constexpr uint8_t ZSPXY0  = Z_FLAG | V_FLAG;

static constexpr uint8_t ZS255   = S_FLAG;

static constexpr uint8_t ZSXY255 = S_FLAG | X_FLAG | Y_FLAG;

static constexpr Table initTables()

{

	Table table = {};

	for (auto i_ : xrange(256)) {

		auto i = narrow_cast<uint8_t>(i_);

		uint8_t zFlag = (i == 0) ? Z_FLAG : 0;

		uint8_t sFlag = i & S_FLAG;

		uint8_t xFlag = i & X_FLAG;

		uint8_t yFlag = i & Y_FLAG;

		uint8_t vFlag = std::popcount(i) % 2 ? 0 : V_FLAG;

		table.ZS   [i] = zFlag | sFlag;

		table.ZSXY [i] = zFlag | sFlag | xFlag | yFlag;

		table.ZSP  [i] = zFlag | sFlag |                 vFlag;

		table.ZSPXY[i] = zFlag | sFlag | xFlag | yFlag | vFlag;

		table.ZSPH [i] = zFlag | sFlag |                 vFlag | H_FLAG;

	}

	assert(table.ZS   [  0] == ZS0);

	assert(table.ZSXY [  0] == ZSXY0);

	assert(table.ZSP  [  0] == ZSP0);

	assert(table.ZSPXY[  0] == ZSPXY0);

	assert(table.ZS   [255] == ZS255);

	assert(table.ZSXY [255] == ZSXY255);

	return table;

}

static constexpr Table table = initTables();

// conditions

struct CondC  { bool operator()(uint8_t f) const { return  (f & C_FLAG) != 0; } };

struct CondNC { bool operator()(uint8_t f) const { return !(f & C_FLAG); } };

struct CondZ  { bool operator()(uint8_t f) const { return  (f & Z_FLAG) != 0; } };

struct CondNZ { bool operator()(uint8_t f) const { return !(f & Z_FLAG); } };

struct CondM  { bool operator()(uint8_t f) const { return  (f & S_FLAG) != 0; } };

struct CondP  { bool operator()(uint8_t f) const { return !(f & S_FLAG); } };

struct CondPE { bool operator()(uint8_t f) const { return  (f & V_FLAG) != 0; } };

struct CondPO { bool operator()(uint8_t f) const { return !(f & V_FLAG); } };

struct CondTrue { bool operator()(uint8_t /*f*/) const { return true; } };

template<typename T> CPUCore<T>::CPUCore(

		MSXMotherBoard& motherboard_, const std::string& name,

		TclCallback& diHaltCallback_, EmuTime time)

	: CPURegs(T::IS_R800)

	, T(time, motherboard_.getScheduler())

	, motherboard(motherboard_)

	, scheduler(motherboard.getScheduler())

	, diHaltCallback(diHaltCallback_)

	, IRQStatus(motherboard.getDebugger(), name + ".pendingIRQ",

	            "Non-zero if there are pending IRQs (thus CPU would enter "

	            "interrupt routine in EI mode).",

	            0)

	, IRQAccept(motherboard.getDebugger(), name + ".acceptIRQ",

	            "This is a valueless (void) probe, it generates an event when the CPU accepts an IRQ.")

	, freqLocked(

		motherboard.getCommandController(), tmpStrCat(name, "_freq_locked"),

	        "real (locked) or custom (unlocked) CPU frequency",

	        true, Setting::Save::NO)

	, freqValue(

		motherboard.getCommandController(), tmpStrCat(name, "_freq"),

		"custom CPU frequency (only valid when unlocked)",

		T::CLOCK_FREQ, 1000000, 1000000000)

	, freq(T::CLOCK_FREQ)

	, isCMOS(motherboard.hasToshibaEngine())  // Toshiba MSX-ENGINEs embed a CMOS Z80

{

	static_assert(!std::is_polymorphic_v<CPUCore<T>>,

		"keep CPUCore non-virtual to keep PC at offset 0");

	doSetFreq();

	doReset(time);

}

template<typename T> void CPUCore<T>::warp(EmuTime time)

{

	assert(T::getTimeFast() <= time);

	T::setTime(time);

}

template<typename T> EmuTime CPUCore<T>::getCurrentTime() const

{

	return T::getTime();

}

template<typename T> void CPUCore<T>::doReset(EmuTime time)

{

	// AF and SP are 0xFFFF

	// PC, R, IFF1, IFF2, HALT and IM are 0x0

	// all others are random

	setAF(0xFFFF);

	setBC(0xFFFF);

	setDE(0xFFFF);

	setHL(0xFFFF);

	setIX(0xFFFF);

	setIY(0xFFFF);

	setPC(0x0000);

	setSP(0xFFFF);

	setAF2(0xFFFF);

	setBC2(0xFFFF);

	setDE2(0xFFFF);

	setHL2(0xFFFF);

	setIFF1(false);

	setIFF2(false);

	setHALT(false);

	setExtHALT(false);

	setIM(0);

	setI(0x00);

	setR(0x00);

	T::setMemPtr(0xFFFF);

	clearPrevious();

	// We expect this assert to be valid

	//   assert(T::getTimeFast() <= time); // time shouldn't go backwards

	// But it's disabled for the following reason:

	//   'motion' (IRC nickname) managed to create a replay file that

	//   contains a reset command that falls in the middle of a Z80

	//   instruction. Replayed commands go via the Scheduler, and are

	//   (typically) executed right after a complete CPU instruction. So

	//   the CPU is (slightly) ahead in time of the about to be executed

	//   reset command.

	//   Normally this situation should never occur: console commands,

	//   hotkeys, commands over cliComm, ... are all handled via the global

	//   event mechanism. Such global events are scheduled between CPU

	//   instructions, so also in a replay they should fall between CPU

	//   instructions.

	//   However if for some reason the timing of the emulation changed

	//   (improved emulation accuracy or a bug so that emulation isn't

	//   deterministic or the replay file was edited, ...), then the above

	//   reasoning no longer holds and the assert can trigger.

	// We need to be robust against loading older replays (when emulation

	// timing has changed). So in that respect disabling the assert is

	// good. Though in the example above (motion's replay) it's not clear

	// whether the assert is really triggered by mixing an old replay

	// with a newer openMSX version. In any case so far we haven't been

	// able to reproduce this assert by recording and replaying using a

	// single openMSX version.

	T::setTime(time);

	assert(NMIStatus == 0); // other devices must reset their NMI source

	assert(IRQStatus == 0); // other devices must reset their IRQ source

}

// I believe the following two methods are thread safe even without any

// locking. The worst that can happen is that we occasionally needlessly

// exit the CPU loop, but that's harmless

//  TODO thread issues are always tricky, can someone confirm this really

//       is thread safe

template<typename T> void CPUCore<T>::exitCPULoopAsync()

{

	// can get called from non-main threads

	exitLoop = true;

}

template<typename T> void CPUCore<T>::exitCPULoopSync()

{

	assert(Thread::isMainThread());

	exitLoop = true;

	T::disableLimit();

}

template<typename T> inline bool CPUCore<T>::needExitCPULoop()

{

	// always executed in main thread

	if (exitLoop) [[unlikely]] {

		// Note: The test-and-set is _not_ atomic! But that's fine.

		//   An atomic implementation is trivial (see below), but

		//   this version (at least on x86) avoids the more expensive

		//   instructions on the likely path.

		exitLoop = false;

		return true;

	}

	return false;

	// Alternative implementation:

	//  atomically set to false and return the old value

	//return exitLoop.exchange(false);

}

template<typename T> void CPUCore<T>::setSlowInstructions()

{

	slowInstructions = 2;

	T::disableLimit();

}

template<typename T> void CPUCore<T>::raiseIRQ()

{

	assert(IRQStatus >= 0);

	if (IRQStatus == 0) {

		setSlowInstructions();

	}

	IRQStatus = IRQStatus + 1;

}

template<typename T> void CPUCore<T>::lowerIRQ()

{

	IRQStatus = IRQStatus - 1;

	assert(IRQStatus >= 0);

}

template<typename T> void CPUCore<T>::raiseNMI()

{

	assert(NMIStatus >= 0);

	if (NMIStatus == 0) {

		nmiEdge = true;

		setSlowInstructions();

	}

	NMIStatus++;

}

template<typename T> void CPUCore<T>::lowerNMI()

{

	NMIStatus--;

	assert(NMIStatus >= 0);

}

template<typename T> bool CPUCore<T>::isM1Cycle(unsigned address) const

{

	// This method should only be called from within a MSXDevice::readMem()

	// method. It can be used to check whether the current read action has

	// the M1 pin active. The 'address' parameter that is give to readMem()

	// should be passed (unchanged) to this method.

	//

	// This simple implementation works because the rest of the CPUCore

	// code is careful to only update the PC register on M1 cycles. In

	// practice that means that the PC is (only) updated at the very end of

	// every instruction, even if is a multi-byte instruction. Or for

	// prefix-instructions the PC is also updated after the prefix is

	// fetched (because such instructions activate M1 twice).

	return address == getPC();

}

template<typename T> void CPUCore<T>::wait(EmuTime time)

{

	assert(time >= getCurrentTime());

	scheduler.schedule(time);

	T::advanceTime(time);

}

template<typename T> EmuTime CPUCore<T>::waitCycles(EmuTime time, unsigned cycles)

{

	T::add(cycles);

	EmuTime time2 = T::calcTime(time, cycles);

	// note: time2 is not necessarily equal to T::getTime() because of the

	// way how WRITE_PORT() is implemented.

	scheduler.schedule(time2);

	return time2;

}

template<typename T> void CPUCore<T>::setNextSyncPoint(EmuTime time)

{

	T::setLimit(time);

}

template<typename T> void CPUCore<T>::update(const Setting& setting) noexcept

{

	if (&setting == &freqLocked) {

		doSetFreq();

	} else if (&setting == &freqValue) {

		doSetFreq();

	}

}

template<typename T> void CPUCore<T>::setFreq(unsigned freq_)

{

	freq = freq_;

	doSetFreq();

}

template<typename T> void CPUCore<T>::doSetFreq()

{

	if (freqLocked.getBoolean()) {

		// locked, use value set via setFreq()

		T::setFreq(freq);

	} else {

		// unlocked, use value set by user

		T::setFreq(freqValue.getInt());

	}

}

template<typename T> inline uint8_t CPUCore<T>::READ_PORT(uint16_t port, unsigned cc)

{

	EmuTime time = T::getTimeFast(cc);

	scheduler.schedule(time);

	uint8_t result = interface->readIO(port, time);

	// note: no forced page-break after IO

	return result;

}

template<typename T> inline void CPUCore<T>::WRITE_PORT(uint16_t port, uint8_t value, unsigned cc)

{

	EmuTime time = T::getTimeFast(cc);

	scheduler.schedule(time);

	interface->writeIO(port, value, time);

	// note: no forced page-break after IO

}

template<typename T> template<bool PRE_PB, bool POST_PB>

NEVER_INLINE uint8_t CPUCore<T>::RDMEMslow(unsigned address, unsigned cc)

{

	interface->tick(CacheLineCounters::NonCachedRead);

	// not cached

	unsigned high = address >> CacheLine::BITS;

        if (readCacheLine[high] == nullptr) {

		// try to cache now (not a valid entry, and not yet tried)

		auto addrBase = narrow_cast<uint16_t>(address & CacheLine::HIGH);

		if (const uint8_t* line = interface->getReadCacheLine(addrBase)) {

			// cached ok

			T::template PRE_MEM<PRE_PB, POST_PB>(address);

			T::template POST_MEM<       POST_PB>(address);

			readCacheLine[high] = line - addrBase;

			return readCacheLine[high][address];

		}

	}

	// uncacheable

	readCacheLine[high] = std::bit_cast<const uint8_t*>(uintptr_t(1));

	T::template PRE_MEM<PRE_PB, POST_PB>(address);

	EmuTime time = T::getTimeFast(cc);

	scheduler.schedule(time);

	uint8_t result = interface->readMem(narrow_cast<uint16_t>(address), time);

	T::template POST_MEM<POST_PB>(address);

	return result;

}

template<typename T> template<bool PRE_PB, bool POST_PB>

ALWAYS_INLINE uint8_t CPUCore<T>::RDMEM_impl2(unsigned address, unsigned cc)

{

	const uint8_t* line = readCacheLine[address >> CacheLine::BITS];

	if (uintptr_t(line) > 1) [[likely]] {

		// cached, fast path

		T::template PRE_MEM<PRE_PB, POST_PB>(address);

		T::template POST_MEM<       POST_PB>(address);

		return line[address];

	} else {

		return RDMEMslow<PRE_PB, POST_PB>(address, cc); // not inlined

	}

}

template<typename T> template<bool PRE_PB, bool POST_PB>

ALWAYS_INLINE uint8_t CPUCore<T>::RDMEM_impl(unsigned address, unsigned cc)

{

	constexpr bool PRE  = T::template Normalize<PRE_PB >::value;

	constexpr bool POST = T::template Normalize<POST_PB>::value;