From 39ab246ce68e50df4757bbe395d6722ada582927 Mon Sep 17 00:00:00 2001
From: Shamus Hammons <jlhamm@acm.org>
Date: Sun, 20 Jul 2014 16:30:39 -0500
Subject: [PATCH] Fixed RISC division algorithm; thanks to SPCPD for the info.

---
 src/dsp.cpp | 54 +++++++++++++++++++++++++----------------------------
 src/gpu.cpp | 41 ++++++++++++++++++++++++++--------------
 2 files changed, 52 insertions(+), 43 deletions(-)

diff --git a/src/dsp.cpp b/src/dsp.cpp
index 0218a7d..b3ca25e 100644
--- a/src/dsp.cpp
+++ b/src/dsp.cpp
@@ -2455,29 +2455,6 @@ static void dsp_opcode_abs(void)
 static void dsp_opcode_div(void)
 {
 #if 0
-	uint32_t _Rm=RM;
-	uint32_t _Rn=RN;
-
-	if (_Rm)
-	{
-		if (dsp_div_control & 1)
-		{
-			dsp_remain = (((uint64_t)_Rn) << 16) % _Rm;
-			if (dsp_remain&0x80000000)
-				dsp_remain-=_Rm;
-			RN = (((uint64_t)_Rn) << 16) / _Rm;
-		}
-		else
-		{
-			dsp_remain = _Rn % _Rm;
-			if (dsp_remain&0x80000000)
-				dsp_remain-=_Rm;
-			RN/=_Rm;
-		}
-	}
-	else
-		RN=0xffffffff;
-#else
 	if (RM)
 	{
 		if (dsp_div_control & 0x01)		// 16.16 division
@@ -2493,15 +2470,34 @@ static void dsp_opcode_div(void)
 			RN = RN / RM;
 		}
 
-// What we really should do here is figure out why this condition
-// happens in the real divide unit and emulate *that* behavior.
-#if 0
-		if ((gpu_remain - RM) & 0x80000000)	// If the result would have been negative...
-			gpu_remain -= RM;			// Then make it negative!
-#endif
 	}
 	else
+	{
+		// This is what happens according to SCPCD. NYAN!
 		RN = 0xFFFFFFFF;
+		dsp_remain = 0;
+	}
+#else
+	// Real algorithm, courtesy of SCPCD: NYAN!
+	uint32_t q = RN;
+	uint32_t r = 0;
+
+	// If 16.16 division, stuff top 16 bits of RN into remainder and put the
+	// bottom 16 of RN in top 16 of quotient
+	if (dsp_div_control & 0x01)
+		q <<= 16, r = RN >> 16;
+
+	for(int i=0; i<32; i++)
+	{
+//		uint32_t sign = (r >> 31) & 0x01;
+		uint32_t sign = r & 0x80000000;
+		r = (r << 1) | ((q >> 31) & 0x01);
+		r += (sign ? RM : -RM);
+		q = (q << 1) | (((~r) >> 31) & 0x01);
+	}
+
+	RN = q;
+	dsp_remain = r;
 #endif
 }
 
diff --git a/src/gpu.cpp b/src/gpu.cpp
index d5e9054..fbf26a0 100644
--- a/src/gpu.cpp
+++ b/src/gpu.cpp
@@ -2390,13 +2390,7 @@ static void gpu_opcode_div(void)	// RN / RM
 	if (doGPUDis)
 		WriteLog("%06X: DIV    R%02u, R%02u (%s) [NCZ:%u%u%u, R%02u=%08X, R%02u=%08X] -> ", gpu_pc-2, IMM_1, IMM_2, (gpu_div_control & 0x01 ? "16.16" : "32"), gpu_flag_n, gpu_flag_c, gpu_flag_z, IMM_1, RM, IMM_2, RN);
 #endif
-// NOTE: remainder is NOT calculated correctly here!
-//       The original tried to get it right by checking to see if the
-//       remainder was negative, but that's too late...
-// The code there should do it now, but I'm not 100% sure...
-// [Now it should be correct, but not displaying correct behavior of the actual
-//  hardware. A step in the right direction.]
-
+#if 0
 	if (RM)
 	{
 		if (gpu_div_control & 0x01)		// 16.16 division
@@ -2411,16 +2405,35 @@ static void gpu_opcode_div(void)	// RN / RM
 			gpu_remain = RN % RM;
 			RN = RN / RM;
 		}
-
-// What we really should do here is figure out why this condition
-// happens in the real divide unit and emulate *that* behavior.
-#if 0
-		if ((gpu_remain - RM) & 0x80000000)	// If the result would have been negative...
-			gpu_remain -= RM;			// Then make it negative!
-#endif
 	}
 	else
+	{
+		// This is what happens according to SCPCD. NYAN!
 		RN = 0xFFFFFFFF;
+		gpu_remain = 0;
+	}
+#else
+	// Real algorithm, courtesy of SCPCD: NYAN!
+	uint32_t q = RN;
+	uint32_t r = 0;
+
+	// If 16.16 division, stuff top 16 bits of RN into remainder and put the
+	// bottom 16 of RN in top 16 of quotient
+	if (gpu_div_control & 0x01)
+		q <<= 16, r = RN >> 16;
+
+	for(int i=0; i<32; i++)
+	{
+//		uint32_t sign = (r >> 31) & 0x01;
+		uint32_t sign = r & 0x80000000;
+		r = (r << 1) | ((q >> 31) & 0x01);
+		r += (sign ? RM : -RM);
+		q = (q << 1) | (((~r) >> 31) & 0x01);
+	}
+
+	RN = q;
+	gpu_remain = r;
+#endif
 
 #ifdef GPU_DIS_DIV
 	if (doGPUDis)
-- 
2.37.2