#include "VDPAccessSlots.hh"

#include "one_of.hh"

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <utility>

namespace openmsx::VDPAccessSlots {

// These tables must contain at least one value that is bigger or equal
// to 1368+132. So we extend the data with some cyclic duplicates.

// Screen rendering disabled (or vertical border).
// This is correct (measured on real V9938) for bitmap and character mode.
// TODO also correct for text mode? See 'vdp-timing-2.html for more details.
static constexpr std::array<int16_t, 154 + 17> slotsScreenOff = {
	   0,    8,   16,   24,   32,   40,   48,   56,   64,   72,
	  80,   88,   96,  104,  112,  120,  164,  172,  180,  188,
	 196,  204,  212,  220,  228,  236,  244,  252,  260,  268,
	 276,  292,  300,  308,  316,  324,  332,  340,  348,  356,
	 364,  372,  380,  388,  396,  404,  420,  428,  436,  444,
	 452,  460,  468,  476,  484,  492,  500,  508,  516,  524,
	 532,  548,  556,  564,  572,  580,  588,  596,  604,  612,
	 620,  628,  636,  644,  652,  660,  676,  684,  692,  700,
	 708,  716,  724,  732,  740,  748,  756,  764,  772,  780,
	 788,  804,  812,  820,  828,  836,  844,  852,  860,  868,
	 876,  884,  892,  900,  908,  916,  932,  940,  948,  956,
	 964,  972,  980,  988,  996, 1004, 1012, 1020, 1028, 1036,
	1044, 1060, 1068, 1076, 1084, 1092, 1100, 1108, 1116, 1124,
	1132, 1140, 1148, 1156, 1164, 1172, 1188, 1196, 1204, 1212,
	1220, 1228, 1268, 1276, 1284, 1292, 1300, 1308, 1316, 1324,
	1334, 1344, 1352, 1360,
	1368+  0, 1368+  8, 1368+16, 1368+ 24, 1368+ 32,
	1368+ 40, 1368+ 48, 1368+56, 1368+ 64, 1368+ 72,
	1368+ 80, 1368+ 88, 1368+96, 1368+104, 1368+112,
	1368+120, 1368+164
};

// Bitmap mode, sprites disabled.
static constexpr std::array<int16_t, 88 + 16> slotsSpritesOff = {
	   6,   14,   22,   30,   38,   46,   54,   62,   70,   78,
	  86,   94,  102,  110,  118,  162,  170,  182,  188,  214,
	 220,  246,  252,  278,  310,  316,  342,  348,  374,  380,
	 406,  438,  444,  470,  476,  502,  508,  534,  566,  572,
	 598,  604,  630,  636,  662,  694,  700,  726,  732,  758,
	 764,  790,  822,  828,  854,  860,  886,  892,  918,  950,
	 956,  982,  988, 1014, 1020, 1046, 1078, 1084, 1110, 1116,
	1142, 1148, 1174, 1206, 1212, 1266, 1274, 1282, 1290, 1298,
	1306, 1314, 1322, 1332, 1342, 1350, 1358, 1366,
	1368+  6, 1368+14, 1368+ 22, 1368+ 30, 1368+ 38,
	1368+ 46, 1368+54, 1368+ 62, 1368+ 70, 1368+ 78,
	1368+ 86, 1368+94, 1368+102, 1368+110, 1368+118,
	1368+162,
};

// Bitmap mode, sprites enabled.
static constexpr std::array<int16_t, 31 + 3> slotsSpritesOn = {
	  28,   92,  162,  170,  188,  220,  252,  316,  348,  380,
	 444,  476,  508,  572,  604,  636,  700,  732,  764,  828,
	 860,  892,  956,  988, 1020, 1084, 1116, 1148, 1212, 1264,
	1330,
	1368+28, 1368+92, 1368+162,
};

// Character mode, sprites enabled.
static constexpr std::array<int16_t, 31 + 3> slotsChar = {
	  32,   96,  166,  174,  188,  220,  252,  316,  348,  380,
	 444,  476,  508,  572,  604,  636,  700,  732,  764,  828,
	 860,  892,  956,  988, 1020, 1084, 1116, 1148, 1212, 1268,
	1334,
	1368+32, 1368+96, 1368+166,
};

// Text mode.
static constexpr std::array<int16_t, 47 + 10> slotsText = {
	   2,   10,   18,   26,   34,   42,   50,   58,   66,  166,
	 174,  182,  190,  198,  206,  214,  222,  312,  408,  504,
	 600,  696,  792,  888,  984, 1080, 1176, 1206, 1214, 1222,
	1230, 1238, 1246, 1254, 1262, 1270, 1278, 1286, 1294, 1302,
	1310, 1318, 1326, 1336, 1346, 1354, 1362,
	1368+ 2, 1368+10, 1368+18, 1368+26, 1368+ 34,
	1368+42, 1368+50, 1368+58, 1368+66, 1368+166,
};


// TMS9918 (MSX1) cycle numbers translated to V99x8 cycles (multiplied by 4).
// MSX1 screen off.
static constexpr std::array<int16_t, 107 + 18> slotsMsx1ScreenOff = {
	   4,   12,   20,   28,   36,   44,   52,   60,   68,   76,
	  84,   92,  100,  108,  116,  124,  132,  140,  148,  156,
	 164,  172,  180,  188,  196,  204,  220,  236,  252,  268,
	 284,  300,  316,  332,  348,  364,  380,  396,  412,  428,
	 444,  460,  476,  492,  508,  524,  540,  556,  572,  588,
	 604,  620,  636,  652,  668,  684,  700,  716,  732,  748,
	 764,  780,  796,  812,  828,  844,  860,  876,  892,  908,
	 924,  940,  956,  972,  988, 1004, 1020, 1036, 1052, 1068,
	1084, 1100, 1116, 1132, 1148, 1164, 1180, 1196, 1212, 1228,
	1236, 1244, 1252, 1260, 1268, 1276, 1284, 1292, 1300, 1308,
	1316, 1324, 1332, 1340, 1348, 1356, 1364,
	1368+  4, 1368+ 12, 1368+ 20, 1368+ 28, 1368+ 36,
	1368+ 44, 1368+ 52, 1368+ 60, 1368+ 68, 1368+ 76,
	1368+ 84, 1368+ 92, 1368+100, 1368+108, 1368+116,
	1368+124, 1368+132, 1368+140,
};

// MSX1 graphic mode 1 and 2 (aka screen 1 and 2).
static constexpr std::array<int16_t, 19 + 8> slotsMsx1Gfx12 = {
	   4,   12,   20,   28,  116,  124,  132,  140,  220,  348,
	 476,  604,  732,  860,  988, 1116, 1236, 1244, 1364,
	1368+  4, 1368+ 12, 1368+ 20, 1368+ 28, 1368+116,
	1368+124, 1368+132, 1368+140,
};

// MSX1 graphic mode 3 (aka screen 3).
static constexpr std::array<int16_t, 51 + 8> slotsMsx1Gfx3 = {
	   4,   12,   20,   28,  116,  124,  132,  140,  220,  228,
	 260,  292,  324,  348,  356,  388,  420,  452,  476,  484,
	 516,  548,  580,  604,  612,  644,  676,  708,  732,  740,
	 772,  804,  836,  860,  868,  900,  932,  964,  988,  996,
	1028, 1060, 1092, 1116, 1124, 1156, 1188, 1220, 1236, 1244,
	1364,
	1368+  4, 1368+ 12, 1368+ 20, 1368+ 28, 1368+116,
	1368+124, 1368+132, 1368+140,
};


// MSX1 text mode 1 (aka screen 0 width 40).
static constexpr std::array<int16_t, 91 + 18> slotsMsx1Text = {
	   4,   12,   20,   28,   36,   44,   52,   60,   68,   76,
	  84,   92,  100,  108,  116,  124,  132,  140,  148,  156,
	 164,  172,  180,  188,  196,  204,  212,  220,  228,  244,
	 268,  292,  316,  340,  364,  388,  412,  436,  460,  484,
	 508,  532,  556,  580,  604,  628,  652,  676,  700,  724,
	 748,  772,  796,  820,  844,  868,  892,  916,  940,  964,
	 988, 1012, 1036, 1060, 1084, 1108, 1132, 1156, 1180, 1196,
	1204, 1212, 1220, 1228, 1236, 1244, 1252, 1260, 1268, 1276,
	1284, 1292, 1300, 1308, 1316, 1324, 1332, 1340, 1348, 1356,
	1364,
	1368+  4, 1368+ 12, 1368+ 20, 1368+ 28, 1368+ 36,
	1368+ 44, 1368+ 52, 1368+ 60, 1368+ 68, 1368+ 76,
	1368+ 84, 1368+ 92, 1368+100, 1368+108, 1368+116,
	1368+124, 1368+132, 1368+140,
};

// Helper functions to transform the above tables into a format that is easier
// (=faster) to work with.

/** Upper bound on the number of entries in one of the tables above. */
static constexpr size_t MAX_SLOTS = 192;

/** Extra timing properties of a slot table, based on the investigation
  * documented here:
  *     https://github.com/sndpl/openMSX/pull/5
  *
  * 'pad': the VDP pads its line out to 1368 cycles by making a few of its memory
  * cycles in the horizontal blanking region longer than the rest. The command
  * engine's delay counter does not see those extra cycles, so a delay that spans
  * them takes that many more real cycles to be satisfied. Each entry is the
  * cycle at which one padded memory cycle has completed, and how many cycles it
  * adds; an interval (from, to] loses that many cycles per entry it contains.
  * An entry with 'at == 0' is unused.
  *
  * Measured from /RAS. The total is 4 cycles in each of the three bitmap modes,
  * but it is not distributed the same way: with the display off and with sprites
  * off two memory cycles are 10 cycles long where the rest of that part of the
  * line runs at 8 (and the /CAS of those two follows their /RAS by 2 cycles
  * instead of 1); with sprites on the 13/6/10 pattern that part of the line has
  * becomes 15/7/11, so three cycles are padded, by 2, 1 and 1.
  *
  * The underlying reason for this mechanism are the S1/S0 bits in R#9. With these
  * the VDP switches between 1368 and 1365 cycles per line (this is not emulated).
  * And then in 1368-mode, parts of the VDP 'stall' including the command engine
  * part. Measured directly: with S1,S0 != 0,0 the line is 1365 cycles and the
  * same memory cycles carry 3 cycles less padding (they do not lose all of it).
  *
  * 'extra': added to every command engine step. Sprite rendering costs an extra
  * cycle, as if the arbitration decision for a slot were taken a cycle earlier
  * while the sprite fetch logic is active. (In earlier versions we emulated this
  * with 'sprOn' specific values timing values in LMMM and HMMM). The
  * measurements admit 1 or 2 here and cannot separate them.
  *
  * 'lateLead' / 'plainSlots': CPU slots come in two classes. A 'late' slot
  * wants 'lateLead' cycles more lookahead than the 16 of a 'plain' one, and it
  * releases the CPU's single request buffer one cycle before its access instead
  * of one cycle after. The V9938 die shows why: a CPU slot is one tick of a
  * two-tick-wide waveform, and which of the two it is decides when the grant is
  * sampled. In the sprites-enabled and the G1/G2/G3 tables every CPU slot is
  * late except the two in 'plainSlots'; in the other tables 'lateLead' is 0 and
  * there are no late slots at all.
  *
  * These apply to the V99x8 bitmap tables, and the slot classes also to the
  * character table; the text and MSX1 tables have never been measured this way
  * and are left alone. */
struct Timing {
	struct Pad {
		int16_t at = 0;
		int16_t cycles = 0;
	};
	std::array<Pad, 3> pad = {};
	int extra = 0;
	int16_t lateLead = 0;
	std::array<int16_t, 2> plainSlots = {-1, -1};
};

struct AccessTable
{
	std::array<uint8_t, NUM_DELTAS * TICKS> values = {};
	Timing timing;
};

/** Is this one of the CPU slots that wants the longer lookahead? */
[[nodiscard]] static constexpr bool isLate(const Timing& timing, int tick)
{
	return (timing.lateLead != 0) && !contains(timing.plainSlots, tick);
}

struct CycleTable : AccessTable
{
	constexpr CycleTable(bool msx1, std::span<const int16_t> slots,
	                     Timing timing_ = {})
	{
		timing = timing_;
		assert(std::ranges::is_sorted(slots));

		// !!! Keep this in sync with the 'Delta' enum !!!
		constexpr std::array<int, NUM_DELTAS> delta = {
			0, 1, 16, 28, 16, 24, 32, 36, 46, 60, 72, 84, 88, 36+68, 84+36,
			60+68, 72+58, 63, 64, 76, 100, 112
		};

		// Memory-cycle time of every cycle in the line: real time minus the
		// padding that has completed up to and including it. The distance
		// from cycle 'i' to slot 's' as the command engine counts it is then
		// mem[s] - mem[i]. Two lines, because the slot tables run past 1368.
		std::array<int16_t, 2 * TICKS> mem = {};
		for (int t = 1; t < 2 * TICKS; ++t) {
			int m = mem[t - 1] + 1;
			for (const auto& p : timing.pad) {
				if (p.at && ((t == p.at) || (t == p.at + TICKS))) m -= p.cycles;
			}
			mem[t] = narrow_cast<int16_t>(m);
		}

		// Which slots follow another slot after only 6 cycles? Only the
		// sprites-off table has such slots (25 of its 88 slots). And which
		// want the longer CPU lookahead? Both indexed by slot, so that the
		// search below does not have to ask per candidate.
		std::bitset<TICKS> tight;
		static_vector<int16_t, 25> tightSlots;
		std::array<uint8_t, MAX_SLOTS> cpuLead = {};
		for (auto i : xrange(slots.size())) {
			auto s = slots[i];
			if ((i > 0) && (s >= 6) && ((slots[i - 1] + 6) == s) && (s < TICKS)) {
				tight[s] = true; // assume no tight slots wrap around 1368
				tightSlots.push_back(s);
			}
			cpuLead[i] = isLate(timing, s % TICKS)
			           ? narrow_cast<uint8_t>(timing.lateLead) : 0;
		}
		assert(tightSlots.size() == one_of(0u, 25u));

		size_t out = 0;
		for (auto idx : xrange(NUM_DELTAS)) {
			bool cmd = (FIRST_CMD_DELTA <= idx) && (idx < LAST_CMD_DELTA);
			bool cpu = (FIRST_CPU_DELTA <= idx) && (idx < LAST_CPU_DELTA);
			bool skipTight = cpu && (idx != CPU_ANY_DELTA);
			int step = delta[idx] + (cmd ? timing.extra : 0);
			int p = 0;
			for (auto i : xrange(TICKS)) {
				// 'mem' is not monotonic in 'i' at the stretched slots, so
				// the search can occasionally have to step back one slot.
				auto ok = [&](int q) {
					if (cpu) {
						// The CPU never gets one of the tight slots: the
						// VDP spends it on a dummy read and does the CPU's
						// access in the next slot. And a 'late' slot hands
						// out its grant later than a plain one.
						if (skipTight && tight[slots[q] % TICKS]) return false;
						return (mem[slots[q]] - mem[i]) >= (step + cpuLead[q]);
					}
					return cmd ? ((mem[slots[q]] - mem[i]) >= step)
					           : ((slots[q] - i) >= step);
				};
				while (!ok(p)) ++p;
				while ((p > 0) && ok(p - 1)) --p;
				unsigned t = slots[p] - i;
				if (msx1) {
					if (step <= 40) assert(t < 256);
				} else {
					assert(t < 256);
				}
				values[out++] = narrow_cast<uint8_t>(t);
			}
		}
		// A memory cycle that starts only 6 cycles after the previous
		// one finishes one cycle late as far as the command engine is
		// concerned, so a step that starts there needs one extra cycle,
		// which is the same as starting one cycle later. All the tight
		// slots are in the display area, far away from the stretched
		// memory cycles, so the shift is exact.
		for (auto idx : xrange(FIRST_CMD_DELTA, LAST_CMD_DELTA)) {
			for (auto ts : tightSlots) {
				size_t b = (size_t(idx) * TICKS) + ts;
				values[b] = narrow_cast<uint8_t>(values[b + 1] + 1);
			}
		}
	}
};

static constexpr CycleTable tabSpritesOn    {false, slotsSpritesOn,  Timing{.pad = {{{1330, 2}, {1337, 1}, {1348, 1}}}, .extra = 1, .lateLead = 2, .plainSlots = {162, 170}}};
static constexpr CycleTable tabSpritesOff   {false, slotsSpritesOff, Timing{.pad = {{{1332, 2}, {1342, 2}}}, .extra = 0}};
static constexpr CycleTable tabChar         {false, slotsChar,        Timing{.lateLead = 2, .plainSlots = {166, 174}}};
static constexpr CycleTable tabText         {false, slotsText};
static constexpr CycleTable tabScreenOff    {false, slotsScreenOff,  Timing{.pad = {{{1334, 2}, {1344, 2}}}, .extra = 0}};
static constexpr CycleTable tabMsx1Gfx12    {true,  slotsMsx1Gfx12};
static constexpr CycleTable tabMsx1Gfx3     {true,  slotsMsx1Gfx3};
static constexpr CycleTable tabMsx1Text     {true,  slotsMsx1Text};
static constexpr CycleTable tabMsx1ScreenOff{true,  slotsMsx1ScreenOff};
static constexpr AccessTable tabBroken{};


[[nodiscard]] static inline const AccessTable& getTable(const VDP& vdp)
{
	if (vdp.getBrokenCmdTiming()) return tabBroken;
	// Note: the access grid switches over one line before the display area,
	// hence isSlotTableDisplayEnabled() rather than isDisplayEnabled().
	bool enabled = vdp.isSlotTableDisplayEnabled();
	bool sprites = vdp.spritesEnabledRegister();
	auto mode    = vdp.getDisplayMode();
	bool bitmap  = mode.isBitmapMode();
	bool text    = mode.isTextMode();
	bool gfx3    = mode.getBase() == DisplayMode::GRAPHIC3;

	if (vdp.isMSX1VDP()) {
		if (!enabled) return tabMsx1ScreenOff;
		return text ? tabMsx1Text
		            : (gfx3 ? tabMsx1Gfx3
		                    : tabMsx1Gfx12);
		// TODO undocumented modes
	} else {
		if (bitmap) {
			return !enabled ? tabScreenOff
			      : sprites ? tabSpritesOn
			                : tabSpritesOff;
		} else {
			// 'enabled' or 'sprites' doesn't matter in V99x8 non-bitmap mode
			// See: https://github.com/openMSX/openMSX/issues/1754
			return text ? tabText
			            : tabChar;
		}
	}
}

EmuTime getAccessSlot(
	EmuTime frame_, EmuTime time, Delta delta,
	const VDP& vdp)
{
	VDP::VDPClock frame(frame_);
	unsigned ticks = frame.getTicksTill(time) % TICKS;
	const auto& tab = getTable(vdp);
	return time + VDP::VDPClock::duration(tab.values[std::to_underlying(delta) + ticks]);
}

Calculator getCalculator(
	EmuTime frame, EmuTime time, EmuTime limit,
	const VDP& vdp)
{
	return {frame, time, limit, getTable(vdp).values};
}

int paddingCycles(int tick, int n, const VDP& vdp)
{
	assert(0 <= tick); assert(tick < TICKS);
	assert(0 < n); assert(n <= MAX_PADDING_SPAN);

	int result = 0;
	for (const auto& p : getTable(vdp).timing.pad) {
		if (!p.at) continue;
		int d = p.at - tick;            // cycles till the next time this
		if (d <= 0) d += TICKS;         //   padded memory cycle completes
		if (d <= n) result += p.cycles;
	}
	return result;
}

bool isLateCpuSlot(int slotTick, const VDP& vdp)
{
	return isLate(getTable(vdp).timing, slotTick);
}

} // namespace openmsx::VDPAccessSlots