From 56473644aa260aad93f21050a2064854a3448c13 Mon Sep 17 00:00:00 2001
From: Gediminas Jakutis <gediminas@varciai.lt>
Date: Wed, 3 Mar 2021 16:04:14 +0200
Subject: now up to 256 bit!

Signed-off-by: Gediminas Jakutis <gediminas@varciai.lt>
---
 meson_options.txt |  2 +-
 src/defs.h        | 30 +++++++++++++++++++++++++++++-
 src/mergesort.c   |  3 ++-
 src/meson.build   |  2 ++
 src/util.h        | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 80 insertions(+), 3 deletions(-)
 create mode 100644 src/util.h

diff --git a/meson_options.txt b/meson_options.txt
index 52d535b..3833423 100644
--- a/meson_options.txt
+++ b/meson_options.txt
@@ -4,6 +4,6 @@ option('data-signed',
 	description : 'Switch whether to use signed data type')
 option('data-bitness',
 	type : 'combo',
-	choices : ['64', '32', '16', '8'],
+	choices : ['256', '128', '64', '32', '16', '8'],
 	value : '64',
 	description : 'Size of a data entry to use, in bits')
diff --git a/src/defs.h b/src/defs.h
index 0d543d7..2c0d81c 100644
--- a/src/defs.h
+++ b/src/defs.h
@@ -41,12 +41,40 @@
 #	else
 		typedef uint32_t field;
 #	endif
-#else
+#elif entry_field_size == 64
 #	ifdef entry_field_signed
 		typedef int64_t field;
 #	else
 		typedef uint64_t field;
 #	endif
+#elif entry_field_size == 128
+#	ifdef entry_field_signed
+		typedef struct field {
+			uint64_t low;
+			int64_t high;
+		} field;
+#	else
+		typedef struct field {
+			uint64_t low;
+			uint64_t high;
+		} field;
+#	endif
+#elif entry_field_size == 256
+#	ifdef entry_field_signed
+		typedef struct field {
+			uint64_t low;
+			uint64_t midlow;
+			uint64_t midhigh;
+			int64_t high;
+		} field;
+#	else
+		typedef struct field {
+			uint64_t low;
+			uint64_t midlow;
+			uint64_t midhigh;
+			uint64_t high;
+		} field;
+#	endif
 #endif
 
 union nextoff {
diff --git a/src/mergesort.c b/src/mergesort.c
index 1b21db7..053e702 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -7,6 +7,7 @@
 #include "defs.h"
 #include "stream.h"
 #include "mergesort.h"
+#include "util.h"
 
 static int merge(struct stream * const dest, struct stream * const A, struct stream * const B);
 
@@ -53,7 +54,7 @@ static int merge(struct stream * const dest, struct stream * const A, struct str
 	b = B->get(B);
 
 	while (a || b) {
-		if (a && (!b || a->val <= b->val)) {
+		if (a && (!b || is_less_equal(a->val, b->val))) {
 			dest->put(dest, a);
 			a = A->get(A);
 		} else {
diff --git a/src/meson.build b/src/meson.build
index aed222e..7f391ab 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -4,6 +4,7 @@ source_files = [
 	'stream.c',
 	'main.c',
 	'mergesort.c',
+	'util.h',
 ]
 
 header_files = [
@@ -12,6 +13,7 @@ header_files = [
 	'datagen.h',
 	'stream.h',
 	'mergesort.h',
+	'util.h',
 ]
 
 sources = files(source_files)
diff --git a/src/util.h b/src/util.h
new file mode 100644
index 0000000..af819f4
--- /dev/null
+++ b/src/util.h
@@ -0,0 +1,46 @@
+/* SPDX-License-Identifier: LGPL-2.1-only */
+
+/* Copyright (C) 2021 Gediminas Jakutis */
+
+#ifndef ALGOS_UTIL_H_INCLUDED
+#define ALGOS_UTIL_H_INCLUDED
+
+#include "defs.h"
+
+static inline int is_less_equal(const field a, const field b) __attribute__((always_inline));
+
+static inline int is_less_equal(const field a, const field b)
+{
+	int ret;
+
+/* all sizes fitting in a primitive type */
+#if entry_field_size <= 64
+
+	ret = a <= b;
+
+/* composite of two 64bit */
+#elif entry_field_size == 128
+
+	if (unlikely(a.high == b.high)) {
+		ret = a.low <= b.low;
+	} else {
+		ret = a.high < b.high;
+	}
+
+/* composite of four 64bit */
+#elif entry_field_size == 256
+	if (likely(a.high != b.high)) {
+		ret = a.high < b.high;
+	} else if (likely(a.midhigh != b.midhigh)){
+		ret = a.midhigh < b.midhigh;
+	} else if (likely(a.midlow != b.midlow)){
+		ret = a.midlow < b.midlow;
+	} else {
+		ret = a.low <= b.low;
+	}
+#endif
+
+	return ret;
+}
+
+#endif /* ALGOS_UTIL_H_INCLUDED */
-- 
cgit v1.2.3