All kinds of stuff

Signed-off-by: Mattias Andrée <maandree@kth.se>

1 files changed, 142 insertions, 27 deletions

diff --git a/libsyscalls_get_syscall_display_info.c b/libsyscalls_get_syscall_display_info.c
index f9bbf1a..60bbe8a 100644
--- a/libsyscalls_get_syscall_display_info.c
+++ b/libsyscalls_get_syscall_display_info.c
@@ -1,30 +1,53 @@
 /* See LICENSE file for copyright and license details. */
 #include "common.h"
-#include <stdalign.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
 
-#if defined(__GNUC__)
-# pragma GCC diagnostic ignored "-Winline"
+
+static inline signed char
+trailing_zeroes(unsigned long long int x)
+{
+#ifndef HAVE_BUILTIN_FFSLL
+# if defined(__HAVE_BUILTIN_FFSLL)
+#  define HAVE_BUILTIN_FFSLL
+# elif defined(__clang__)
+#  if __clang_major__ >= 5
+#   define HAVE_BUILTIN_FFSLL
+#  endif
+# elif defined(__GNUC__)
+#   if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+#    define HAVE_BUILTIN_FFSLL
+#   endif
+# endif
 #endif
 
+#ifdef HAVE_BUILTIN_FFSLL
+# if defined(__GNUC__)
+#  pragma GCC diagnostic push
+#  pragma GCC diagnostic ignored "-Wsign-conversion"
+# endif
 
-#define LOWEST_BIT(X) ((X) & ~((X) - 1))
-#define POST_HIGHEST_OF_CONSECUTIVELY_BITS(X) ((X) + LOWEST_BIT(X))
+	return (signed char)(__builtin_ffsll(x) - 1); /* the type for x has changed over time */
 
+# if defined(__GNUC__)
+#  pragma GCC diagnostic pop
+# endif
+#else
 
-static inline signed char
-trailing_zeroes(unsigned long long int x) { /* TODO use builtin function if available */
 	int r = 0;
 	if (x == 0)
 		return -1;
 	for (; (x & 1) == 0; x >>= 1)
 		r += 1;
 	return (signed char)r;
+
+#endif
 }
 
 
+#define USE_INTERPOLATION_SEARCH /* TODO validate; should be configurable and (if good) default on systems with intrinsic divsion */
+#ifndef USE_INTERPOLATION_SEARCH
+
+
+PURE_FUNCTION
 static int
 signed_named_number_cmp(const void *a_, const void *b_)
 {
@@ -33,6 +56,7 @@ signed_named_number_cmp(const void *a_, const void *b_)
 }
 
 
+PURE_FUNCTION
 static int
 unsigned_named_number_cmp(const void *a_, const void *b_)
 {
@@ -41,6 +65,106 @@ unsigned_named_number_cmp(const void *a_, const void *b_)
 }
 
 
+#else
+
+
+/* convertion to unsigned is a modulo (unsigned maximum + 1) operation */
+#define DIFF(TYPE, A, B) ((unsigned TYPE)(A) - (unsigned TYPE)(B))
+
+#define INTERPOL_SEARCH(KEY, BASE, N, READ)\
+	do {\
+		double guess_d;\
+		unsigned long long int guess;\
+		size_t h = (N);\
+		\
+		if (!h--)\
+			return NULL;\
+		\
+		if ((KEY) <= READ((BASE), 0))\
+			return (KEY) == READ((BASE), 0) ? (BASE) : NULL;\
+		if ((KEY) >= READ((BASE), h))\
+			return (KEY) == READ((BASE), h) ? (BASE) : NULL;\
+		if (READ((BASE), 0) == READ((BASE), h))\
+			return NULL;\
+		\
+		guess = DIFF(long long int, (KEY), READ((BASE), 0));\
+		if (h > ULLONG_MAX / guess)\
+			goto use_double;\
+		\
+		for (;;) {\
+			guess = DIFF(long long int, (KEY), READ((BASE), 0));\
+			guess *= (unsigned long long int)h;\
+			guess /= DIFF(long long int, READ((BASE), h), READ((BASE), 0));\
+			\
+			if (READ((BASE), guess) < (KEY)) {\
+				h -= guess += 1;\
+				(BASE) = &(BASE)[guess];\
+			} else if (READ((BASE), guess) > (KEY)) {\
+				h -= guess -= 1;\
+			} else {\
+				return &(BASE)[guess];\
+			}\
+			\
+			if (READ((BASE), 0) == READ((BASE), h))\
+				return (KEY) == READ((BASE), 0) ? (BASE) : NULL;\
+			if ((KEY) < READ((BASE), 0))\
+				return NULL;\
+			if ((KEY) > READ((BASE), h))\
+				return NULL;\
+		}\
+		\
+	use_double:\
+		for (;;) {\
+			guess = DIFF(long long int, (KEY), READ((BASE), 0));\
+			guess_d = (double)guess * (double)h;\
+			guess = DIFF(long long int, READ((BASE), h), READ((BASE), 0));\
+			guess_d /= (double)guess;\
+			guess = (unsigned long long int)guess_d;\
+			\
+			if (READ((BASE), guess) < (KEY)) {\
+				h -= guess += 1;\
+				(BASE) = &(BASE)[guess];\
+			} else if (READ((BASE), guess) > (KEY)) {\
+				h -= guess -= 1;\
+			} else {\
+				return &(BASE)[guess];\
+			}\
+			\
+			if (READ((BASE), 0) == READ((BASE), h))\
+				return (KEY) == READ((BASE), 0) ? (BASE) : NULL;\
+			if ((KEY) < READ((BASE), 0))\
+				return NULL;\
+			if ((KEY) > READ((BASE), h))\
+				return NULL;\
+		}\
+	} while (0)
+
+
+PURE_FUNCTION
+static const struct libsyscalls_named_number *
+interpol_search_signed_named_number(signed long long int key, const struct libsyscalls_named_number *base, size_t n)
+{
+#define X(ARR, I) ((ARR)[I].number.s)
+	INTERPOL_SEARCH(key, base, n, X);
+#undef X
+}
+
+
+PURE_FUNCTION
+static const struct libsyscalls_named_number *
+interpol_search_unsigned_named_number(unsigned long long int key, const struct libsyscalls_named_number *base, size_t n)
+{
+#define X(ARR, I) ((ARR)[I].number.u)
+	INTERPOL_SEARCH(key, base, n, X);
+#undef X
+}
+
+#undef DIFF
+
+
+#endif
+
+
 static const char *
 extract_signal(enum libsyscalls_os os, enum libsyscalls_arch arch,
                unsigned long long int *valuep, char *fallback_out, int is_signed)
@@ -52,23 +176,23 @@ extract_signal(enum libsyscalls_os os, enum libsyscalls_arch arch,
 	if (libsyscalls_get_signals(os, arch, &signals, &nsignals))
 		return NULL;
 
-	found = bsearch(&key, signals, nsignals, sizeof(key), /* TODO interpolation search may be better */
+#ifndef USE_INTERPOLATION_SEARCH
+	found = bsearch(&key, signals, nsignals, sizeof(key),
 	                is_signed ? &signed_named_number_cmp : &unsigned_named_number_cmp);
+#else
+	found = is_signed ? interpol_search_signed_named_number(key.number.s, signals, nsignals)
+	                  : interpol_search_unsigned_named_number(key.number.u, signals, nsignals);
+#endif
 	if (!found)
 		return NULL;
 
-	(void)fallback_out;
+	(void) fallback_out;
 
 	*valuep = 0;
 	return found->name;
 }
 
 
-#if defined(__clang__)
-# pragma clang diagnostic push
-# pragma clang diagnostic ignored "-Wunsafe-buffer-usage"
-#endif
-
 static struct libsyscalls_syscall_display_info *
 build_syscall_display_info(void *data, size_t data_size, size_t data_align,
                            libsyscalls_symbol_printer_function **funcs,
@@ -123,24 +247,15 @@ build_syscall_display_info(void *data, size_t data_size, size_t data_align,
 	return ret;
 }
 
-#if defined(__clang__)
-# pragma clang diagnostic pop
-#endif
-
 
 #include "generated/symbols.c"
 
 
-
-#if defined(__GNUC__) && !defined(__clang__)
-# pragma GCC diagnostic ignored "-Wnonnull-compare" /* Why should I trust that the user is using the same compiler? */
-#endif
-
 enum libsyscalls_error
 libsyscalls_get_syscall_display_info(enum libsyscalls_os os, enum libsyscalls_arch arch,
                                      const struct libsyscalls_syscall_abi *syscall,
                                      long long int syscall_number,
-                                     unsigned long long int *syscall_arguments,
+                                     const unsigned long long int *syscall_arguments,
                                      struct libsyscalls_syscall_display_info **info_out)
 {
 	struct libsyscalls_syscall_display_info *info;