[PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[Jan Dubiec]

See the comment below. I don't know why qsort behaves so strangely. It
could be a bug, or simply a consequence of its being an unstable sort.
Unfortunately, I don't have time to investigate the root cause.

Signed-off-by: Jan Dubiec <jdx@o2.pl>
---
 sim/h8300/compile.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/sim/h8300/compile.c b/sim/h8300/compile.c
index 06988095228..c08f7704ef3 100644
--- a/sim/h8300/compile.c
+++ b/sim/h8300/compile.c
@@ -1568,6 +1568,41 @@ store2 (SIM_DESC sd, ea_type *arg, int n)
   return store_1 (sd, arg, n, 1);
 }
 
+#ifdef __MINGW32__
+/* On Windows/MinGW, qsort for some reason produces a "shuffled" opcode
+table instead of a sorted one, causing the entire simulator to hang.
+
+This is a simple insertion sort implementation, but it has virtually
+no impact on simulator performance.  */
+
+#define qsort opcode_insertion_sort
+
+static void
+opcode_insertion_sort(void *base, size_t nmemb, size_t size,
+                      int (*compar)(const void *, const void *))
+{
+  unsigned char *a = base;
+  struct h8_opcode tmp;
+  size_t i, j;
+
+  if (nmemb < 2 || size == 0)
+    return;
+
+  for (i = 1; i < nmemb; ++i) {
+    memcpy(&tmp, a + i * size, size);
+
+    j = i;
+    while (j > 0 && compar(&tmp, a + (j - 1) * size) < 0) {
+      memcpy(a + j * size, a + (j - 1) * size, size);
+      --j;
+    }
+
+    memcpy(a + j * size, &tmp, size);
+  }
+
+}
+#endif /* #ifdef __MINGW32__ */
+
 /* Callback for qsort.  We sort first based on availability
    (available instructions sort lower).  When availability state
    is the same, then we use the first 4 bit nibble as a secondary
-- 
2.55.0

Re: [PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[Jan Dubiec]

[-- Attachment #1: Type: text/plain, Size: 1326 bytes --]

On 22.08.2026 13:02, Jan Dubiec wrote:
> See the comment below. I don't know why qsort behaves so strangely. It
> could be a bug, or simply a consequence of its being an unstable sort.
> Unfortunately, I don't have time to investigate the root cause.
OK, I did some testing that shows that Microsoft's implementation of 
qsort() uses an unstable sorting algorithm, i.e. the order of equal 
elements may change. See the attached program. It compares insertion 
sort, which is a stable algorithm, with qsort(). The test fails on 
Windows and passes on Linux. The compiler is irrelevant — both 
Microsoft's compiler and GCC from MinGW produce the same result.

It's worth noting that although the test passes on Linux, this is not 
guaranteed. According to AI, the qsort() implementation in glibc 
generally uses merge sort (stable), but may fall back to heapsort 
(unstable), depending on the size of the data. The glibc documentation 
seems to confirm this — it clearly states that "If two elements compare 
equal, their order after sorting is unpredictable":
https://sourceware.org/glibc/manual/2.44/html_node/Array-Sort-Function.html

So I think the best solution is to use a sorting algorithm known to be 
stable on every host, e.g. the insertion sort implementation from my 
previous message.

What do you think?

/J.D.

[-- Attachment #2: qsort_test.c --]
[-- Type: text/plain, Size: 2299 bytes --]

/*
 * Compile commad: gcc -O2 -s -o qsort_test.exe qsort_test.c
 * or              cl /O2 /Fe:qsort_test.exe qsort_test.c
 * Usage: qsort_test.exe [-d]
 *   -d - dump tables to stdout
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TABLESIZE 5

typedef struct {
	int f1;
	int f2;
	int f3;
} element_type;

static int
element_comparator (const void *el1, const void *el2)
{
	element_type *p1 = (element_type*) el1;
	element_type *p2 = (element_type*) el2;

	/* Only f1 and f2 are used as sort keys; f3 is irrelevant. */
	if (p1->f1 != p2->f1)
		return (p1->f1 > p2->f1) - (p1->f1 < p2->f1);

	if (p1->f2 != p2->f2)
		return (p1->f2 > p2->f2) - (p1->f2 < p2->f2);

	return 0;
}

static void
insertion_sort(void *base, size_t nmemb, size_t size,
				int (*compar)(const void *, const void *))
{
	unsigned char *a = base;
	unsigned char *tmp;
	size_t i, j;

	if (nmemb < 2 || size == 0)
		return;

	tmp = malloc(size);
	if (tmp == NULL)
		return;

	for (i = 1; i < nmemb; ++i) {
		memcpy(tmp, a + i * size, size);

		j = i;
		while (j > 0 && compar(tmp, a + (j - 1) * size) < 0) {
			memcpy(a + j * size, a + (j - 1) * size, size);
			--j;
		}

		memcpy(a + j * size, tmp, size);
	}

	free(tmp);
}

int main (int argc, char *argv[])
{
	element_type t0[TABLESIZE] = {
		{0, 0, 10}, {7, 7, 10}, {5, 5, 10}, {7, 7, 5}, {0, 0, 11}
	};
	element_type t1[TABLESIZE], t2[TABLESIZE];
	size_t i;

	memcpy(t1, t0, TABLESIZE*sizeof(element_type));
	memcpy(t2, t0, TABLESIZE*sizeof(element_type));

	insertion_sort(t1, TABLESIZE, sizeof(element_type), element_comparator);
	qsort(t2, TABLESIZE, sizeof(element_type), element_comparator);

	/* Dump tables to stdout */
	if (argc > 1 && argv[1][0] == '-' && argv[1][1] == 'd') {
		for (i = 0; i < TABLESIZE; ++i) {
			printf("t0[%zu]:\t%d\t%d\t%d\n", i, t0[i].f1, t0[i].f2, t0[i].f3);
			printf("t1[%zu]:\t%d\t%d\t%d\n", i, t1[i].f1, t1[i].f2, t1[i].f3);
			printf("t2[%zu]:\t%d\t%d\t%d\n\n", i, t2[i].f1, t2[i].f2, t2[i].f3);
		}
	}

	for (i = 0; i < TABLESIZE; ++i) {
		if ( memcmp(&t1[i], &t2[i], sizeof(element_type)) ) {
			printf("First fail at element %zu\n", i);
			printf("FAIL\n");
			return -1;
		}
	}
	printf("PASS\n");
	return 0;
}

Re: [PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[Tom Tromey]

>>>>> "Jan" == Jan Dubiec <jdx@o2.pl> writes:

Jan> So I think the best solution is to use a sorting algorithm known to be
Jan> stable on every host, e.g. the insertion sort implementation from my
Jan> previous message.

Would it be possible to change the comparison function to be stable?
I think it would be somewhat nicer not to have a separate sort
implementation.

If that's too hard, though, I think your approach is fine.

Tom

Re: [PATCH] H8/300: sim: Fix simulator hang caused by qsort on Windows/MinGW.

[Jan Dubiec]

[-- Attachment #1: Type: text/plain, Size: 1470 bytes --]

On 27.08.2026 17:19, Tom Tromey wrote:
>>>>>> "Jan" == Jan Dubiec <jdx@o2.pl> writes:
> 
> Jan> So I think the best solution is to use a sorting algorithm known to be
> Jan> stable on every host, e.g. the insertion sort implementation from my
> Jan> previous message.
> 
> Would it be possible to change the comparison function to be stable?

It is impossible by definition, because stability is a property of the 
sorting algorithm, not the comparator. However, the comparator can be 
modified in such a way that an unstable sorting algorithm produces a 
“good enough” result.

That said, the following simple patch is sufficient:
    /* Secondarily sort based on the first opcode nibble.  */
-  return p1->data.nib[0] - p2->data.nib[0];
+  if (p1->data.nib[0] != p2->data.nib[0])
+    return p1->data.nib[0] - p2->data.nib[0];
+
+  /* The 3rd sort key */
+  return strcmp(p1->name, p2->name);

However, I decided to take the longer route (see the attached patch) in 
order to make the opcode table as close as possible to the one that 
would be produced by a stable sorting algorithm.

> I think it would be somewhat nicer not to have a separate sort
> implementation.
> 
> If that's too hard, though, I think your approach is fine.
It wasn't difficult, but I’m still inclined to favor a stable, 
predictable sorting algorithm. That said, it’s not a big deal to me. Let 
me know what you think about it, and then I’ll post a new version of the 
patch.

/J.D.

[-- Attachment #2: instruction_comparator.patch --]
[-- Type: text/plain, Size: 1868 bytes --]

 sim/h8300/compile.c | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

diff --git a/sim/h8300/compile.c b/sim/h8300/compile.c
index 06988095228..3cca69730b0 100644
--- a/sim/h8300/compile.c
+++ b/sim/h8300/compile.c
@@ -1586,6 +1586,7 @@ instruction_comparator (const void *p1_, const void *p2_)
 {
   struct h8_opcode *p1 = (struct h8_opcode *)p1_;
   struct h8_opcode *p2 = (struct h8_opcode *)p2_;
+  int cmp;
 
   /* The 1st sort key is based on whether or not the
      instruction is even available.  This reduces the
@@ -1605,7 +1606,43 @@ instruction_comparator (const void *p1_, const void *p2_)
     return p2_available - p1_available;
 
   /* Secondarily sort based on the first opcode nibble.  */
-  return p1->data.nib[0] - p2->data.nib[0];
+  if (p1->data.nib[0] != p2->data.nib[0])
+    return p1->data.nib[0] - p2->data.nib[0];
+
+  /* The 3rd sort key  */
+  cmp = strcmp(p1->name, p2->name);
+  if (cmp)
+    {
+      /* Two different opcodes  */
+      size_t l1 = strlen(p1->name);
+      size_t l2 = strlen(p2->name);
+      ptrdiff_t i1 = strchr(p1->name, '.') - p1->name;
+      ptrdiff_t i2 = strchr(p2->name, '.') - p2->name;
+      char c1, c2;
+
+      if ((l1 == l2) && (i1 == i2) && (i1 > 0))
+        {
+          /* Check for different mnemonics, e.g. add.w vs. and.b  */
+          cmp = strncmp(p1->name, p2->name, i1);
+          if (cmp)
+            return cmp;
+
+          /* At this point we expect only b, w or l suffix,
+             where b < w < l  */
+          c1 = p1->name[i1+1];
+          c2 = p2->name[i2+1];
+          if (c1 == 'b')
+            return -1;
+          else if (c1 == 'w')
+            return (c2 == 'b') ? 1 : -1;
+          else
+            return 1;
+        }
+      return cmp;
+    }
+
+  /* The 4th sort key  */
+  return p1->how - p2->how;
 }