/*
	Copyright (C) 2006 yopyop
	Copyright (C) 2007 shash
	Copyright (C) 2007-2011 DeSmuME team

	This file is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 2 of the License, or
	(at your option) any later version.

	This file is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with the this software.  If not, see <http://www.gnu.org/licenses/>.
*/

// this file is split from MMU.h for the purpose of avoiding ridiculous recompile times
// when changing it, because practically everything includes MMU.h.

#pragma once

#include <algorithm>
#include <cmath>
#include "MMU.h"
#include "cp15.h"
#include "readwrite.h"
#include "NDSSystem.h"

////////////////////////////////////////////////////////////////
// MEMORY TIMING ACCURACY CONFIGURATION
//
// the more of these are enabled,
// the more accurate memory access timing _should_ become.
// they should be listed roughly in order of most to least important.
// it's reasonable to disable some of these as a speed hack.
// obviously, these defines don't cover all the variables or features needed,
// and in particular, DMA or code+data access bus contention is still missing.

// disable this to prevent the advanced timing logic from ever running at all
//#define ENABLE_ADVANCED_TIMING

#ifdef ENABLE_ADVANCED_TIMING
// makes non-sequential accesses slower than sequential ones.
#define ACCOUNT_FOR_NON_SEQUENTIAL_ACCESS
// (SOMETIMES THIS IS A BIG SPEED HIT!)

// enables emulation of code fetch waits.
#define ACCOUNT_FOR_CODE_FETCH_CYCLES

// makes access to DTCM (arm9 only) fast.
#define ACCOUNT_FOR_DATA_TCM_SPEED

// enables simulation of cache hits and cache misses.
#define ENABLE_CACHE_CONTROLLER_EMULATION

#endif //ENABLE_ADVANCED_TIMING

//
////////////////////////////////////////////////////////////////

inline bool USE_TIMING()
{
#ifdef ENABLE_ADVANCED_TIMING
	return CommonSettings.advanced_timing;
#else
	return false;
#endif
}

enum MMU_ACCESS_DIRECTION
{
	MMU_AD_READ, MMU_AD_WRITE
};

// note that we don't actually emulate the cache contents here,
// only enough to guess what would be a cache hit or a cache miss.
// this doesn't really get used unless ENABLE_CACHE_CONTROLLER_EMULATION is defined.
template<int SIZESHIFT, int ASSOCIATIVESHIFT, int BLOCKSIZESHIFT> class CacheController
{
public:
	template<MMU_ACCESS_DIRECTION DIR> bool Cached(uint32_t addr)
	{
		uint32_t blockMasked = addr & BLOCKMASK;
		if (blockMasked == this->m_cacheCache)
			return true;
		else
			return this->CachedInternal<DIR>(addr, blockMasked);
	}

	void Reset()
	{
		for (int blockIndex = 0; blockIndex < NUMBLOCKS; ++blockIndex)
			this->m_blocks[blockIndex].Reset();
		this->m_cacheCache = ~0;
	}
	CacheController()
	{
		this->Reset();
	}

private:
	template<MMU_ACCESS_DIRECTION DIR> bool CachedInternal(uint32_t addr, uint32_t blockMasked)
	{
		uint32_t blockIndex = blockMasked >> BLOCKSIZESHIFT;
		CacheBlock &block = this->m_blocks[blockIndex];
		addr &= TAGMASK;

		for (int way = 0; way < ASSOCIATIVITY; ++way)
			if (addr == block.tag[way])
			{
				// found it, already allocated
				this->m_cacheCache = blockMasked;
				return true;
			}
		if (DIR == MMU_AD_READ)
		{
			// TODO: support other allocation orders?
			block.tag[block.nextWay++] = addr;
			block.nextWay %= ASSOCIATIVITY;
			this->m_cacheCache = blockMasked;
		}
		return false;
	}

	enum { SIZE = 1 << SIZESHIFT };
	enum { ASSOCIATIVITY = 1 << ASSOCIATIVESHIFT };
	enum { BLOCKSIZE = 1 << BLOCKSIZESHIFT };
	enum { TAGSHIFT = SIZESHIFT - ASSOCIATIVESHIFT };
	enum { TAGMASK = ~0 << TAGSHIFT };
	enum { BLOCKMASK = (~0 >> (32 - TAGSHIFT)) & (~0 << BLOCKSIZESHIFT) };
	enum { WORDSIZE = sizeof(uint32_t) };
	enum { WORDSPERBLOCK = (1 << BLOCKSIZESHIFT) / WORDSIZE };
	enum { DATAPERWORD = WORDSIZE * ASSOCIATIVITY };
	enum { DATAPERBLOCK = DATAPERWORD * WORDSPERBLOCK };
	enum { NUMBLOCKS = SIZE / DATAPERBLOCK };

	struct CacheBlock
	{
		uint32_t tag[ASSOCIATIVITY];
		uint32_t nextWay;

		void Reset()
		{
			this->nextWay = 0;
			for (int way = 0; way < ASSOCIATIVITY; ++way)
				this->tag[way] = 0;
		}
	};

	uint32_t m_cacheCache; // optimization

	CacheBlock m_blocks[NUMBLOCKS];
};

template<int PROCNUM, MMU_ACCESS_TYPE AT, int READSIZE, MMU_ACCESS_DIRECTION DIRECTION, bool TIMING> inline uint32_t _MMU_accesstime(uint32_t addr, bool sequential);

template<int PROCNUM, MMU_ACCESS_TYPE AT> class FetchAccessUnit
{
public:
	template<int READSIZE, MMU_ACCESS_DIRECTION DIRECTION, bool TIMING> uint32_t Fetch(uint32_t address)
	{
#ifdef ACCOUNT_FOR_CODE_FETCH_CYCLES
		bool prohibit = TIMING;
#else
		bool prohibit = false;
#endif

		if (AT == MMU_AT_CODE && !prohibit)
			return 1;

		uint32_t time = _MMU_accesstime<PROCNUM, AT, READSIZE, DIRECTION,TIMING>(address,
#ifdef ACCOUNT_FOR_NON_SEQUENTIAL_ACCESS
			TIMING ? (address == m_lastAddress + (READSIZE >> 3)) : true
#else
			true
#endif
		);

#ifdef ACCOUNT_FOR_NON_SEQUENTIAL_ACCESS
		this->m_lastAddress = address;
#endif

		return time;
	}

	void Reset()
	{
		this->m_lastAddress = ~0;
	}
	FetchAccessUnit()
	{
		this->Reset();
	}

private:
	uint32_t m_lastAddress;
};

struct MMU_struct_timing
{
	// technically part of the cp15, but I didn't want the dereferencing penalty.
	// these template values correspond with the value of armcp15->cacheType.
	CacheController<13, 2, 5> arm9codeCache; // 8192 bytes, 4-way associative, 32-byte blocks
	CacheController<12, 2, 5> arm9dataCache; // 4096 bytes, 4-way associative, 32-byte blocks

	// technically part of armcpu_t, but that struct isn't templated on PROCNUM
	FetchAccessUnit<0, MMU_AT_CODE> arm9codeFetch;
	FetchAccessUnit<0, MMU_AT_DATA> arm9dataFetch;
	FetchAccessUnit<1, MMU_AT_CODE> arm7codeFetch;
	FetchAccessUnit<1, MMU_AT_DATA> arm7dataFetch;

	template<int PROCNUM> FetchAccessUnit<PROCNUM, MMU_AT_CODE> &armCodeFetch();
	template<int PROCNUM> FetchAccessUnit<PROCNUM, MMU_AT_DATA> &armDataFetch();
};
template<> inline FetchAccessUnit<0, MMU_AT_CODE> &MMU_struct_timing::armCodeFetch<0>() { return this->arm9codeFetch; }
template<> inline FetchAccessUnit<1, MMU_AT_CODE> &MMU_struct_timing::armCodeFetch<1>() { return this->arm7codeFetch; }
template<> inline FetchAccessUnit<0, MMU_AT_DATA> &MMU_struct_timing::armDataFetch<0>() { return this->arm9dataFetch; }
template<> inline FetchAccessUnit<1, MMU_AT_DATA> &MMU_struct_timing::armDataFetch<1>() { return this->arm7dataFetch; }

extern MMU_struct_timing MMU_timing;

// calculates the time a single memory access takes,
// in units of cycles of the current processor.
// this function replaces what used to be MMU_WAIT16 and MMU_WAIT32.
// this may have side effects, so don't call it more than necessary.
template<int PROCNUM, MMU_ACCESS_TYPE AT, int READSIZE, MMU_ACCESS_DIRECTION DIRECTION, bool TIMING> inline uint32_t _MMU_accesstime(uint32_t addr, bool /*sequential*/)
{
	static const int MC = 1; // cached or tcm memory speed
	static const int M32 = PROCNUM == ARMCPU_ARM9 ? 2 : 1; // access through 32-bit bus
	static const int M16 = M32 * (READSIZE > 16 ? 2 : 1); // access through 16-bit bus
	static const int MSLW = M16 * 8; // this needs tuning

	if (PROCNUM == ARMCPU_ARM9 && AT == MMU_AT_CODE && addr < 0x02000000)
		return MC; // ITCM

#ifdef ACCOUNT_FOR_DATA_TCM_SPEED
	if (TIMING && PROCNUM == ARMCPU_ARM9 && AT == MMU_AT_DATA && (addr & ~0x3FFF) == MMU.DTCMRegion)
		return MC; // DTCM
#endif

	// for now, assume the cache is always enabled for all of main memory
	if (AT != MMU_AT_DMA && TIMING && PROCNUM == ARMCPU_ARM9 && (addr & 0x0F000000) == 0x02000000)
	{
#ifdef ENABLE_CACHE_CONTROLLER_EMULATION
		bool cached = false;
		if (AT == MMU_AT_CODE)
			cached = MMU_timing.arm9codeCache.Cached<DIRECTION>(addr);
		if (AT == MMU_AT_DATA)
			cached = MMU_timing.arm9dataCache.Cached<DIRECTION>(addr);
		if (cached)
			return MC;
		uint32_t c;
		if (sequential && AT == MMU_AT_DATA)
			c = M16; // bonus for sequential data access
		else if (DIRECTION == MMU_AD_READ)
			c = M16 * 5;
		else
			c = M16 * 2; // should be 4, but write buffer isn't emulated yet.
		if (DIRECTION == MMU_AD_READ)
			// cache miss while reading means it has to fill a whole cache line
			// by reading 32 bytes...
			c += 8 * M32 * 2;
		return c;
#elif defined(ACCOUNT_FOR_NON_SEQUENTIAL_ACCESS)
		// this is the closest approximation I could find
		// to the with-cache-controller timing
		// that doesn't do any actual caching logic.
		return sequential ? MC : M16;
#endif
	}

	static const TWaitState MMU_WAIT[] =
	{
		// ITCM, ITCM, MAIN, SWI, REG, VMEM, LCD, OAM,  ROM,  ROM,  RAM,   U,  U,  U,  U, BIOS
#define X    MC,   MC,  M16, M32, M32,  M16, M16, M32, MSLW, MSLW, MSLW, M32,M32,M32,M32,  M32,
		// duplicate it 16 times (this was somehow faster than using a mask of 0xF)
		X X X X  X X X X  X X X X  X X X X
#undef X
	};

	uint32_t c = MMU_WAIT[addr >> 24];

#ifdef ACCOUNT_FOR_NON_SEQUENTIAL_ACCESS
	if (TIMING && !sequential)
	{
		//if(c != MC || PROCNUM==ARMCPU_ARM7) // check not needed anymore because ITCM/DTCM return earlier
		{
			c += PROCNUM == ARMCPU_ARM9 ? 6 : 1;
		}
	}
#endif

	return c;
}

// calculates the cycle time of a single memory access in the MEM stage.
// to be used to calculate the memCycles argument for MMU_aluMemCycles.
// this may have side effects, so don't call it more than necessary.
template<int PROCNUM, int READSIZE, MMU_ACCESS_DIRECTION DIRECTION, bool TIMING> inline uint32_t MMU_memAccessCycles(uint32_t addr)
{
	if (TIMING)
		return MMU_timing.armDataFetch<PROCNUM>().template Fetch<READSIZE, DIRECTION, true>(addr & (~((READSIZE >> 3) - 1)));
	else
		return MMU_timing.armDataFetch<PROCNUM>().template Fetch<READSIZE, DIRECTION, false>(addr & (~((READSIZE >> 3) - 1)));
}

template<int PROCNUM, int READSIZE, MMU_ACCESS_DIRECTION DIRECTION> inline uint32_t MMU_memAccessCycles(uint32_t addr)
{
	if (USE_TIMING())
		return MMU_memAccessCycles<PROCNUM, READSIZE, DIRECTION, true>(addr);
	else
		return MMU_memAccessCycles<PROCNUM, READSIZE, DIRECTION, false>(addr);
}

// calculates the cycle time of a single code fetch in the FETCH stage
// to be used to calculate the fetchCycles argument for MMU_fetchExecuteCycles.
// this may have side effects, so don't call it more than necessary.
template<int PROCNUM, int READSIZE> inline uint32_t MMU_codeFetchCycles(uint32_t addr)
{
	if (USE_TIMING())
		return MMU_timing.armCodeFetch<PROCNUM>().template Fetch<READSIZE, MMU_AD_READ, true>(addr & (~((READSIZE >> 3) - 1)));
	else
		return MMU_timing.armCodeFetch<PROCNUM>().template Fetch<READSIZE, MMU_AD_READ, false>(addr & (~((READSIZE >> 3) - 1)));
}

// calculates the cycle contribution of ALU + MEM stages (= EXECUTE)
// given ALU cycle time and the summation of multiple memory access cycle times.
// this function might belong more in armcpu, but I don't think it matters.
template<int PROCNUM> inline uint32_t MMU_aluMemCycles(uint32_t aluCycles, uint32_t memCycles)
{
	if (PROCNUM == ARMCPU_ARM9)
		// ALU and MEM are different stages of the 5-stage pipeline.
		// we approximate the pipeline throughput using max,
		// since simply adding the cycles of each instruction together
		// fails to take into account the parallelism of the arm pipeline
		// and would make the emulated system unnaturally slow.
		return std::max(aluCycles, memCycles);
	else
		// ALU and MEM are part of the same stage of the 3-stage pipeline,
		// thus they occur in sequence and we can simply add the counts together.
		return aluCycles + memCycles;
}

// calculates the cycle contribution of ALU + MEM stages (= EXECUTE)
// given ALU cycle time and the description of a single memory access.
// this may have side effects, so don't call it more than necessary.
template<int PROCNUM, int READSIZE, MMU_ACCESS_DIRECTION DIRECTION> inline uint32_t MMU_aluMemAccessCycles(uint32_t aluCycles, uint32_t addr)
{
	uint32_t memCycles;
	if (USE_TIMING())
		memCycles = MMU_memAccessCycles<PROCNUM, READSIZE, DIRECTION, true>(addr);
	else
		memCycles = MMU_memAccessCycles<PROCNUM, READSIZE, DIRECTION, false>(addr);
	return MMU_aluMemCycles<PROCNUM>(aluCycles, memCycles);
}

// calculates the cycle contribution of FETCH + EXECUTE stages
// given executeCycles = the combined ALU+MEM cycles
//     and fetchCycles = the cycle time of the FETCH stage
// this function might belong more in armcpu, but I don't think it matters.
template<int PROCNUM> inline uint32_t MMU_fetchExecuteCycles(uint32_t executeCycles, uint32_t fetchCycles)
{
#ifdef ACCOUNT_FOR_CODE_FETCH_CYCLES
	bool allow = true;
#else
	bool allow = false;
#endif

	if (USE_TIMING() && allow)
	{
		// execute and fetch are different stages of the pipeline for both arm7 and arm9.
		// again, we approximate the pipeline throughput using max.
		return std::max(executeCycles, fetchCycles);
		// TODO: add an option to support conflict between MEM and FETCH cycles
		//  if they're both using the same data bus.
		//  in the case of a conflict this should be:
		//  return std::max(aluCycles, memCycles + fetchCycles);
	}
	return executeCycles;
}