Reintegrate test code with library code

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

12 files changed, 2016 insertions, 0 deletions

diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am
index 35e8078..0a0e50e 100644
--- a/lib/util/Makemodule.am
+++ b/lib/util/Makemodule.am
@@ -32,3 +32,55 @@ libutil_a_SOURCES += lib/util/src/mempool.c
 endif
 
 noinst_LIBRARIES += libutil.a
+
+test_str_table_SOURCES = lib/util/test/str_table.c
+test_str_table_LDADD = libutil.a libio.a libcompat.a
+test_str_table_CPPFLAGS = $(AM_CPPFLAGS) -DTESTPATH=$(top_srcdir)/lib/util/test
+
+test_rbtree_SOURCES = lib/util/test/rbtree.c
+test_rbtree_LDADD = libutil.a libcompat.a
+
+test_xxhash_SOURCES = lib/util/test/xxhash.c
+test_xxhash_LDADD = libutil.a libcompat.a
+
+test_threadpool_SOURCES = lib/util/test/threadpool.c
+test_threadpool_CFLAGS = $(AM_CFLAGS) $(PTHREAD_CFLAGS)
+test_threadpool_CPPFLAGS = $(AM_CPPFLAGS)
+test_threadpool_LDADD = libutil.a libcompat.a $(PTHREAD_LIBS)
+
+if HAVE_PTHREAD
+test_threadpool_CPPFLAGS += -DHAVE_PTHREAD
+endif
+
+test_ismemzero_SOURCES = lib/util/test/is_memory_zero.c
+test_ismemzero_LDADD = libutil.a libcompat.a
+
+test_canonicalize_name_SOURCES = lib/util/test/canonicalize_name.c
+test_canonicalize_name_LDADD = libutil.a libcompat.a
+
+test_filename_sane_SOURCES = lib/util/test/filename_sane.c
+test_filename_sane_SOURCES += lib/util/src/filename_sane.c
+test_filename_sane_LDADD = libcompat.a libutil.a
+
+test_filename_sane_w32_SOURCES = lib/util/test/filename_sane.c
+test_filename_sane_w32_SOURCES += lib/util/src/filename_sane.c
+test_filename_sane_w32_CPPFLAGS = $(AM_CPPFLAGS) -DTEST_WIN32=1
+test_filename_sane_w32_LDADD = libcompat.a
+
+test_sdate_epoch_SOURCES = lib/util/test/epoch.c
+test_sdate_epoch_LDADD = libutil.a libcompat.a
+
+test_hex_decode_SOURCES = lib/util/test/hex_decode.c
+test_hex_decode_LDADD = libutil.a libcompat.a
+
+test_base64_decode_SOURCES = lib/util/test/base64_decode.c
+test_base64_decode_LDADD = libutil.a libcompat.a
+
+LIBUTIL_TESTS = \
+	test_str_table test_rbtree test_xxhash test_threadpool test_ismemzero \
+	test_canonicalize_name test_filename_sane test_filename_sane_w32 \
+	test_sdate_epoch test_hex_decode test_base64_decode
+
+check_PROGRAMS += $(LIBUTIL_TESTS)
+TESTS += $(LIBUTIL_TESTS)
+EXTRA_DIST += $(top_srcdir)/lib/util/test/words.txt
diff --git a/lib/util/test/base64_decode.c b/lib/util/test/base64_decode.c
new file mode 100644
index 0000000..8f22a86
--- /dev/null
+++ b/lib/util/test/base64_decode.c
@@ -0,0 +1,74 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * base64_decode.c
+ *
+ * Copyright (C) 2022 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+#include "util/test.h"
+
+static const struct {
+	int result;
+	const char *in;
+	const char *out;
+} test_vec[] = {
+	{ 0, "", "" },
+	{ 0, "Zg", "f" },
+	{ 0, "Zg==", "f" },
+	{ 0, "Zm8=", "fo" },
+	{ 0, "Zm9v", "foo" },
+	{ 0, "Zm9vYg==", "foob" },
+	{ 0, "Zm9vYmE=", "fooba" },
+	{ 0, "Zm9vYmFy", "foobar" },
+	{ 0, "TGV0J3MgYWxsIGxvdmUgTGFpbiEK", "Let's all love Lain!\n" },
+	{ -1, "Zg==X",     "XX" },
+};
+
+int main(int argc, char **argv)
+{
+	sqfs_u8 buffer[256];
+	size_t i, j;
+	(void)argc; (void)argv;
+
+	for (i = 0; i < sizeof(test_vec) / sizeof(test_vec[0]); ++i) {
+		const size_t in_len = strlen(test_vec[i].in);
+		const size_t out_len = strlen(test_vec[i].out);
+		size_t real_out;
+		int ret;
+
+		/* initialize the buffer */
+		for (j = 0; j < sizeof(buffer); ++j) {
+			buffer[j] = (j % 2) ? 0xAA : 0x55;
+		}
+
+		/* convert */
+		real_out = sizeof(buffer);
+		ret = base64_decode(test_vec[i].in, in_len, buffer, &real_out);
+
+		/* make sure pattern is un-touched after expected offset */
+		j = (in_len / 4) * 3;
+		if (in_len % 4)
+			j += 3;
+
+		for (; j < sizeof(buffer); ++j) {
+			TEST_ASSERT(buffer[j] == ((j % 2) ? 0xAA : 0x55));
+		}
+
+		/* check result */
+		if (test_vec[i].result == 0) {
+			TEST_ASSERT(ret == 0);
+			TEST_EQUAL_UI(real_out, out_len);
+			ret = memcmp(buffer, test_vec[i].out, out_len);
+			TEST_ASSERT(ret == 0);
+		} else {
+			TEST_ASSERT(ret != 0);
+			TEST_EQUAL_UI(real_out, 0);
+		}
+
+		fprintf(stderr, "CASE %lu OK\n", (unsigned long)i);
+	}
+
+	return EXIT_SUCCESS;
+}
+
diff --git a/lib/util/test/canonicalize_name.c b/lib/util/test/canonicalize_name.c
new file mode 100644
index 0000000..9f81b04
--- /dev/null
+++ b/lib/util/test/canonicalize_name.c
@@ -0,0 +1,78 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * canonicalize_name.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+#include "util/test.h"
+
+static const struct {
+	const char *in;
+	const char *out;
+} must_work[] = {
+	{ "", "" },
+	{ "/", "" },
+	{ "\\", "\\" },
+	{ "///", "" },
+	{ "\\\\\\", "\\\\\\" },
+	{ "/\\//\\\\/", "\\/\\\\" },
+	{ "foo/bar/test", "foo/bar/test" },
+	{ "foo\\bar\\test", "foo\\bar\\test" },
+	{ "/foo/bar/test/", "foo/bar/test" },
+	{ "\\foo\\bar\\test\\", "\\foo\\bar\\test\\" },
+	{ "///foo//bar//test///", "foo/bar/test" },
+	{ "./foo/././bar/test/./.", "foo/bar/test" },
+	{ "./foo/././", "foo" },
+	{ ".", "" },
+	{ "./", "" },
+	{ "./.", "" },
+	{ "foo/.../bar", "foo/.../bar" },
+	{ "foo/.test/bar", "foo/.test/bar" },
+};
+
+static const char *must_not_work[] = {
+	"..",
+	"foo/../bar",
+	"../foo/bar",
+	"foo/bar/..",
+	"foo/bar/../",
+};
+
+int main(int argc, char **argv)
+{
+	char buffer[512];
+	size_t i;
+	(void)argc; (void)argv;
+
+	for (i = 0; i < sizeof(must_work) / sizeof(must_work[0]); ++i) {
+		strcpy(buffer, must_work[i].in);
+
+		if (canonicalize_name(buffer)) {
+			fprintf(stderr, "Test case rejected: '%s'\n",
+				must_work[i].in);
+			return EXIT_FAILURE;
+		}
+
+		if (strcmp(buffer, must_work[i].out) != 0) {
+			fprintf(stderr, "Expected result: %s\n",
+				must_work[i].out);
+			fprintf(stderr, "Actual result: %s\n", buffer);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; i < sizeof(must_not_work) / sizeof(must_not_work[0]); ++i) {
+		strcpy(buffer, must_not_work[i]);
+
+		if (canonicalize_name(buffer) == 0) {
+			fprintf(stderr, "Test case accepted: '%s'\n",
+				must_not_work[i]);
+			fprintf(stderr, "Transformed into: '%s'\n", buffer);
+			return EXIT_FAILURE;
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/epoch.c b/lib/util/test/epoch.c
new file mode 100644
index 0000000..a04942e
--- /dev/null
+++ b/lib/util/test/epoch.c
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * epoch.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+#include "util/test.h"
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+static void setenv(const char *key, const char *value, int overwrite)
+{
+	char buffer[128];
+	(void)overwrite;
+
+	snprintf(buffer, sizeof(buffer) - 1, "%s=%s", key, value);
+	buffer[sizeof(buffer) - 1] = '\0';
+
+	_putenv(buffer);
+}
+
+static void unsetenv(const char *key)
+{
+	setenv(key, "", 0);
+}
+#endif
+
+int main(int argc, char **argv)
+{
+	sqfs_u32 ts;
+	(void)argc; (void)argv;
+
+	unsetenv("SOURCE_DATE_EPOCH");
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0);
+
+	setenv("SOURCE_DATE_EPOCH", "1337", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 1337);
+
+	setenv("SOURCE_DATE_EPOCH", "0xCAFE", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0);
+
+	setenv("SOURCE_DATE_EPOCH", "foobar", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0);
+
+	setenv("SOURCE_DATE_EPOCH", "-12", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0);
+
+	setenv("SOURCE_DATE_EPOCH", "12", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 12);
+
+	setenv("SOURCE_DATE_EPOCH", "4294967295", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0xFFFFFFFF);
+
+	setenv("SOURCE_DATE_EPOCH", "4294967296", 1);
+	ts = get_source_date_epoch();
+	TEST_EQUAL_UI(ts, 0);
+
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/filename_sane.c b/lib/util/test/filename_sane.c
new file mode 100644
index 0000000..9c9930d
--- /dev/null
+++ b/lib/util/test/filename_sane.c
@@ -0,0 +1,94 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * filename_sane.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+#include "util/test.h"
+
+static const char *must_work[] = {
+	"foobar",
+	"test.txt",
+#if !defined(_WIN32) && !defined(__WINDOWS__) && !defined(TEST_WIN32)
+	"\\foo", "foo\\", "foo\\bar",
+#endif
+	NULL,
+};
+
+static const char *must_not_work[] = {
+	".",
+	"..",
+	"/foo",
+	"foo/",
+	"foo/bar",
+	NULL,
+};
+
+static const char *must_not_work_here[] = {
+#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32)
+	"\\foo", "foo\\", "foo\\bar",
+	"fo<o", "fo>o", "fo:o", "fo\"o",
+	"fo|o", "fo?o", "fo*o", "fo\ro",
+	"CON", "PRN", "AUX", "NUL",
+	"COM1", "COM2", "LPT1", "LPT2",
+	"con", "prn", "aux", "nul",
+	"com1", "com2", "lpt1", "lpt2",
+	"AUX.txt", "aux.txt", "NUL.txt", "nul.txt",
+#endif
+	NULL,
+};
+
+int main(int argc, char **argv)
+{
+	size_t i;
+	(void)argc; (void)argv;
+
+	for (i = 0; must_work[i] != NULL; ++i) {
+		if (!is_filename_sane(must_work[i], false)) {
+			fprintf(stderr, "%s was rejected!\n", must_work[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (!is_filename_sane(must_work[i], true)) {
+			fprintf(stderr,
+				"%s was rejected when testing for "
+				"OS specific stuff!\n", must_work[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; must_not_work[i] != NULL; ++i) {
+		if (is_filename_sane(must_not_work[i], false)) {
+			fprintf(stderr, "%s was accepted!\n",
+				must_not_work[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (is_filename_sane(must_not_work[i], true)) {
+			fprintf(stderr,
+				"%s was accepted when testing for "
+				"OS specific stuff!\n", must_not_work[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	for (i = 0; must_not_work_here[i] != NULL; ++i) {
+		if (!is_filename_sane(must_not_work_here[i], false)) {
+			fprintf(stderr,
+				"%s was rejected in the generic test!\n",
+				must_not_work_here[i]);
+			return EXIT_FAILURE;
+		}
+
+		if (is_filename_sane(must_not_work_here[i], true)) {
+			fprintf(stderr,
+				"%s was accepted when testing for "
+				"OS specific stuff!\n", must_not_work_here[i]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/hex_decode.c b/lib/util/test/hex_decode.c
new file mode 100644
index 0000000..21ac4e7
--- /dev/null
+++ b/lib/util/test/hex_decode.c
@@ -0,0 +1,66 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * hex_decode.c
+ *
+ * Copyright (C) 2022 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+#include "util/test.h"
+
+static const struct {
+	int result;
+	const char *in;
+	const char *out;
+} test_vec[] = {
+	{ 0, "", NULL },
+	{ -1, "A", NULL },
+	{ 0, "AA", "\xAA" },
+	{ 0, "0A", "\x0A" },
+	{ 0, "A0", "\xA0" },
+	{ -1, "A0B", NULL },
+	{ 0, "A0BC", "\xA0\xBC" },
+	{ 0, "0123456789ABCDEF", "\x01\x23\x45\x67\x89\xAB\xCD\xEF" },
+	{ 0, "0123456789abcdef", "\x01\x23\x45\x67\x89\xAB\xCD\xEF" },
+	{ -1, "0123456789ABCDEFGH", NULL },
+	{ -1, "0123456789abcdefgh", NULL },
+};
+
+int main(int argc, char **argv)
+{
+	sqfs_u8 buffer[256];
+	size_t i, j;
+	(void)argc; (void)argv;
+
+	for (i = 0; i < sizeof(test_vec) / sizeof(test_vec[0]); ++i) {
+		size_t in_len = strlen(test_vec[i].in);
+		size_t out_len = in_len / 2;
+		int ret;
+
+		/* initialize the buffer */
+		for (j = 0; j < sizeof(buffer); ++j) {
+			buffer[j] = (j % 2) ? 0xAA : 0x55;
+		}
+
+		/* convert */
+		ret = hex_decode(test_vec[i].in, in_len,
+				 buffer, sizeof(buffer));
+
+		/* make sure pattern is un-touched after expected offset */
+		for (j = out_len; j < sizeof(buffer); ++j) {
+			TEST_ASSERT(buffer[j] == ((j % 2) ? 0xAA : 0x55));
+		}
+
+		/* check result */
+		if (test_vec[i].result == 0) {
+			TEST_ASSERT(ret == 0);
+			ret = memcmp(buffer, test_vec[i].out, out_len);
+			TEST_ASSERT(ret == 0);
+		} else {
+			TEST_ASSERT(ret != 0);
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
+
diff --git a/lib/util/test/is_memory_zero.c b/lib/util/test/is_memory_zero.c
new file mode 100644
index 0000000..f62b0bb
--- /dev/null
+++ b/lib/util/test/is_memory_zero.c
@@ -0,0 +1,33 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * is_memory_zero.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/test.h"
+#include "util/util.h"
+
+int main(int argc, char **argv)
+{
+	unsigned char temp[1024];
+	size_t i, j;
+	(void)argc; (void)argv;
+
+	memset(temp, 0, sizeof(temp));
+
+	for (i = 0; i < sizeof(temp); ++i) {
+		TEST_ASSERT(is_memory_zero(temp, i));
+
+		for (j = 0; j < i; ++j) {
+			TEST_ASSERT(is_memory_zero(temp, i));
+			temp[j] = 42;
+			TEST_ASSERT(!is_memory_zero(temp, i));
+			temp[j] = 0;
+			TEST_ASSERT(is_memory_zero(temp, i));
+		}
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/rbtree.c b/lib/util/test/rbtree.c
new file mode 100644
index 0000000..ca01c0d
--- /dev/null
+++ b/lib/util/test/rbtree.c
@@ -0,0 +1,233 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * rbtree.c
+ *
+ * Copyright (C) 2020 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/rbtree.h"
+#include "util/test.h"
+
+static int key_compare(const void *ctx, const void *a, const void *b)
+{
+	(void)ctx;
+	return *((const sqfs_s32 *)a) - *((const sqfs_s32 *)b);
+}
+
+static size_t count_nodes_dfs(rbtree_node_t *n)
+{
+	return 1 + (n->left == NULL ? 0 : count_nodes_dfs(n->left))
+		+ (n->right == NULL ? 0 : count_nodes_dfs(n->right));
+}
+
+static size_t min_depth(rbtree_node_t *n)
+{
+	size_t lhs, rhs;
+
+	if (n == NULL)
+		return 0;
+
+	lhs = min_depth(n->left) + 1;
+	rhs = min_depth(n->right) + 1;
+
+	return lhs < rhs ? lhs : rhs;
+}
+
+static size_t max_depth(rbtree_node_t *n)
+{
+	size_t lhs, rhs;
+
+	if (n == NULL)
+		return 0;
+
+	lhs = min_depth(n->left) + 1;
+	rhs = min_depth(n->right) + 1;
+
+	return lhs > rhs ? lhs : rhs;
+}
+
+static size_t get_ref_black_depth(rbtree_t *rb)
+{
+	rbtree_node_t *n;
+	size_t count = 0;
+
+	for (n = rb->root; n != NULL; n = n->left) {
+		if (!n->is_red)
+			count += 1;
+	}
+
+	return count;
+}
+
+static void check_binary_tree_dfs(rbtree_node_t *n)
+{
+	const void *key = rbtree_node_key(n);
+	const void *cmp;
+
+	if (n->left != NULL) {
+		cmp = rbtree_node_key(n->left);
+		TEST_ASSERT(key_compare(NULL, cmp, key) < 0);
+
+		check_binary_tree_dfs(n->left);
+	}
+
+	if (n->right != NULL) {
+		cmp = rbtree_node_key(n->right);
+		TEST_ASSERT(key_compare(NULL, cmp, key) > 0);
+
+		check_binary_tree_dfs(n->right);
+	}
+}
+
+static void check_colors_dfs(rbtree_node_t *n)
+{
+	if (n->is_red) {
+		TEST_ASSERT(n->left == NULL || !n->left->is_red);
+		TEST_ASSERT(n->right == NULL || !n->right->is_red);
+	}
+
+	if (n->left != NULL)
+		check_colors_dfs(n->left);
+
+	if (n->right != NULL)
+		check_colors_dfs(n->right);
+}
+
+static void check_black_depth_dfs(rbtree_node_t *n, size_t ref,
+				  size_t counter)
+{
+	if (!n->is_red)
+		counter += 1;
+
+	if (n->left == NULL || n->right == NULL)
+		TEST_EQUAL_UI(counter, ref);
+
+	if (n->left != NULL)
+		check_black_depth_dfs(n->left, ref, counter);
+
+	if (n->right != NULL)
+		check_black_depth_dfs(n->right, ref, counter);
+}
+
+static int check_subtrees_equal(const rbtree_node_t *lhs,
+				const rbtree_node_t *rhs,
+				size_t datasize)
+{
+	if (lhs == rhs)
+		return -1;
+
+	if (lhs->value_offset != rhs->value_offset)
+		return -1;
+
+	if ((lhs->is_red && !rhs->is_red) || (!lhs->is_red && rhs->is_red))
+		return -1;
+
+	if (memcmp(lhs->data, rhs->data, datasize) != 0)
+		return -1;
+
+	if (lhs->left == NULL) {
+		if (rhs->left != NULL)
+			return -1;
+	} else {
+		if (rhs->left == NULL)
+			return -1;
+
+		if (check_subtrees_equal(lhs->left, rhs->left, datasize))
+			return -1;
+	}
+
+	if (lhs->right == NULL) {
+		if (rhs->right != NULL)
+			return -1;
+	} else {
+		if (rhs->right == NULL)
+			return -1;
+
+		if (check_subtrees_equal(lhs->right, rhs->right, datasize))
+			return -1;
+	}
+
+	return 0;
+}
+
+int main(int argc, char **argv)
+{
+	size_t count, blkdepth, mind, maxd;
+	sqfs_s32 key, key2;
+	rbtree_t rb, copy;
+	rbtree_node_t *n;
+	sqfs_u64 value;
+	int ret;
+	(void)argc; (void)argv;
+
+	TEST_ASSERT(rbtree_init(&rb, sizeof(sqfs_s32),
+				sizeof(sqfs_u64), key_compare) == 0);
+
+	count = 0;
+
+	for (key = -1000; key < 1000; ++key) {
+		/* lookup of current key must fail prior to insert */
+		TEST_NULL(rbtree_lookup(&rb, &key));
+
+		/* previous key/value pairs must still be there */
+		for (key2 = -1000; key2 < key; ++key2) {
+			n = rbtree_lookup(&rb, &key2);
+			TEST_NOT_NULL(n);
+			value = *((sqfs_u64 *)rbtree_node_value(n));
+			TEST_EQUAL_UI((sqfs_u64)(key2 + 10000), value);
+		}
+
+		/* insert key value pair */
+		value = key + 10000;
+		TEST_ASSERT(rbtree_insert(&rb, &key, &value) == 0);
+		count += 1;
+
+		/* check if the tree has the right number of nodes */
+		TEST_EQUAL_UI(count_nodes_dfs(rb.root), count);
+
+		/* check if it is still a binary tree */
+		check_binary_tree_dfs(rb.root);
+
+		/* root node must be black. Every red node
+		   must have black children. */
+		TEST_ASSERT(!rb.root->is_red);
+		check_colors_dfs(rb.root);
+
+		/* every path from the root to a leave must have
+		   the same number of black nodes. */
+		blkdepth = get_ref_black_depth(&rb);
+		check_black_depth_dfs(rb.root, blkdepth, 0);
+
+		/* longest root to leaf path must be at most
+		   twice as long as the shortest. */
+		mind = min_depth(rb.root);
+		maxd = max_depth(rb.root);
+		TEST_ASSERT(maxd <= mind * 2);
+
+		/* lookup of current key must work after insert */
+		n = rbtree_lookup(&rb, &key);
+		TEST_NOT_NULL(n);
+		value = *((sqfs_u64 *)rbtree_node_value(n));
+		TEST_EQUAL_UI((sqfs_u64)(key + 10000), value);
+	}
+
+	/* test if copy works */
+	ret = rbtree_copy(&rb, &copy);
+	TEST_EQUAL_I(ret, 0);
+
+	TEST_EQUAL_UI(rb.key_size, copy.key_size);
+	TEST_EQUAL_UI(rb.key_size_padded, copy.key_size_padded);
+	TEST_EQUAL_UI(rb.value_size, copy.value_size);
+	TEST_ASSERT(rb.key_compare == copy.key_compare);
+	TEST_ASSERT(rb.root != copy.root);
+
+	ret = check_subtrees_equal(rb.root, copy.root,
+				   rb.key_size_padded + rb.value_size);
+	TEST_EQUAL_I(ret, 0);
+
+	/* cleanup */
+	rbtree_cleanup(&rb);
+	rbtree_cleanup(&copy);
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/str_table.c b/lib/util/test/str_table.c
new file mode 100644
index 0000000..d4160eb
--- /dev/null
+++ b/lib/util/test/str_table.c
@@ -0,0 +1,85 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * str_table.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/str_table.h"
+#include "io/file.h"
+#include "compat.h"
+#include "util/test.h"
+
+static char *strings[1000];
+
+static int read_strings(void)
+{
+	istream_t *fp;
+	ssize_t ret;
+	char *line;
+	int i;
+
+	fp = istream_open_file("words.txt");
+	TEST_NOT_NULL(fp);
+
+	for (i = 0; i < 1000; ++i) {
+		ret = istream_get_line(fp, &line, NULL, 0);
+		TEST_EQUAL_I(ret, 0);
+
+		strings[i] = line;
+	}
+
+	sqfs_drop(fp);
+	return 0;
+}
+
+int main(int argc, char **argv)
+{
+	str_table_t table;
+	size_t i, j, idx;
+	const char *str;
+	(void)argc; (void)argv;
+
+	TEST_ASSERT(chdir(TEST_PATH) == 0);
+
+	if (read_strings())
+		return EXIT_FAILURE;
+
+	TEST_ASSERT(str_table_init(&table) == 0);
+
+	for (i = 0; i < 1000; ++i) {
+		TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0);
+
+		TEST_EQUAL_UI(idx, i);
+
+		for (j = 0; j <= i; ++j) {
+			str = str_table_get_string(&table, j);
+
+			TEST_NOT_NULL(str);
+			TEST_ASSERT(str != strings[i]);
+			TEST_STR_EQUAL(str, strings[j]);
+		}
+
+		for (; j < 1000; ++j)
+			TEST_NULL(str_table_get_string(&table, j));
+	}
+
+	for (i = 0; i < 1000; ++i) {
+		TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0);
+		TEST_EQUAL_UI(idx, i);
+
+		str = str_table_get_string(&table, i);
+
+		TEST_NOT_NULL(str);
+		TEST_ASSERT(str != strings[i]);
+		TEST_STR_EQUAL(str, strings[i]);
+	}
+
+	str_table_cleanup(&table);
+
+	for (i = 0; i < 1000; ++i)
+		free(strings[i]);
+
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/threadpool.c b/lib/util/test/threadpool.c
new file mode 100644
index 0000000..cf54484
--- /dev/null
+++ b/lib/util/test/threadpool.c
@@ -0,0 +1,168 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * threadpool.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/threadpool.h"
+#include "util/test.h"
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+#define WIN32_LEAN_AND_MEAN
+#define VC_EXTRALEAN
+#include <windows.h>
+
+static CRITICAL_SECTION mutex;
+static unsigned int ticket;
+
+static void ticket_init(void)
+{
+	InitializeCriticalSection(&mutex);
+	ticket = 0;
+}
+
+static void ticket_cleanup(void)
+{
+	DeleteCriticalSection(&mutex);
+	ticket = 0;
+}
+
+static void ticket_wait(unsigned int value)
+{
+	for (;;) {
+		EnterCriticalSection(&mutex);
+
+		if (value == ticket) {
+			ticket += 1;
+			LeaveCriticalSection(&mutex);
+			break;
+		}
+
+		LeaveCriticalSection(&mutex);
+		SwitchToThread();
+	}
+}
+#elif defined(HAVE_PTHREAD)
+#include <pthread.h>
+
+static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
+static unsigned int ticket;
+
+static void ticket_init(void)
+{
+	ticket = 0;
+}
+
+static void ticket_cleanup(void)
+{
+}
+
+static void ticket_wait(unsigned int value)
+{
+	for (;;) {
+		pthread_mutex_lock(&mutex);
+
+		if (value == ticket) {
+			ticket += 1;
+			pthread_mutex_unlock(&mutex);
+			break;
+		}
+
+		pthread_mutex_unlock(&mutex);
+		sched_yield();
+	}
+}
+#else
+static void ticket_init(void)
+{
+}
+
+static void ticket_cleanup(void)
+{
+}
+
+static void ticket_wait(unsigned int value)
+{
+	(void)value;
+}
+#endif
+
+static int worker(void *user, void *work_item)
+{
+	unsigned int value = *((unsigned int *)work_item);
+	(void)user;
+
+	ticket_wait(value);
+
+	*((unsigned int *)work_item) = 42;
+	return 0;
+}
+
+static int worker_serial(void *user, void *work_item)
+{
+	(void)user;
+	*((unsigned int *)work_item) = 42;
+	return 0;
+}
+
+static void test_case(thread_pool_t *pool)
+{
+	unsigned int values[10];
+	unsigned int *ptr;
+	size_t i, count;
+	int ret;
+
+	/* must return a sane value */
+	count = pool->get_worker_count(pool);
+	TEST_ASSERT(count >= 1);
+
+	/* dequeue on empty pool MUST NOT lock up */
+	ptr = pool->dequeue(pool);
+	TEST_NULL(ptr);
+
+	/* submit work items in reverse order */
+	ticket_init();
+
+	for (i = 0; i < sizeof(values) / sizeof(values[0]); ++i) {
+		values[i] = (sizeof(values) / sizeof(values[0]) - 1) - i;
+
+		ret = pool->submit(pool, values + i);
+		TEST_EQUAL_I(ret, 0);
+	}
+
+	/* items must dequeue in the same order */
+	for (i = 0; i < sizeof(values) / sizeof(values[0]); ++i) {
+		ptr = pool->dequeue(pool);
+
+		TEST_NOT_NULL(ptr);
+		TEST_ASSERT(ptr == (values + i));
+		TEST_EQUAL_UI(*ptr, 42);
+	}
+
+	ticket_cleanup();
+
+	/* queue now empty */
+	ptr = pool->dequeue(pool);
+	TEST_NULL(ptr);
+}
+
+int main(int argc, char **argv)
+{
+	thread_pool_t *pool;
+	(void)argc; (void)argv;
+
+	/* test the actual parallel implementation */
+	pool = thread_pool_create(10, worker);
+	TEST_NOT_NULL(pool);
+	test_case(pool);
+	pool->destroy(pool);
+
+	/* repeate the test with the serial reference implementation */
+	pool = thread_pool_create_serial(worker_serial);
+	TEST_NOT_NULL(pool);
+	test_case(pool);
+	pool->destroy(pool);
+	return EXIT_SUCCESS;
+}
diff --git a/lib/util/test/words.txt b/lib/util/test/words.txt
new file mode 100644
index 0000000..9496e14
--- /dev/null
+++ b/lib/util/test/words.txt
@@ -0,0 +1,1000 @@
+a
+ability
+able
+about
+above
+accept
+according
+account
+across
+act
+action
+activity
+actually
+add
+address
+administration
+admit
+adult
+affect
+after
+again
+against
+age
+agency
+agent
+ago
+agree
+agreement
+ahead
+air
+all
+allow
+almost
+alone
+along
+already
+also
+although
+always
+American
+among
+amount
+analysis
+and
+animal
+another
+answer
+any
+anyone
+anything
+appear
+apply
+approach
+area
+argue
+arm
+around
+arrive
+art
+article
+artist
+as
+ask
+assume
+at
+attack
+attention
+attorney
+audience
+author
+authority
+available
+avoid
+away
+baby
+back
+bad
+bag
+ball
+bank
+bar
+base
+be
+beat
+beautiful
+because
+become
+bed
+before
+begin
+behavior
+behind
+believe
+benefit
+best
+better
+between
+beyond
+big
+bill
+billion
+bit
+black
+blood
+blue
+board
+body
+book
+born
+both
+box
+boy
+break
+bring
+brother
+budget
+build
+building
+business
+but
+buy
+by
+call
+camera
+campaign
+can
+cancer
+candidate
+capital
+car
+card
+care
+career
+carry
+case
+catch
+cause
+cell
+center
+central
+century
+certain
+certainly
+chair
+challenge
+chance
+change
+character
+charge
+check
+child
+choice
+choose
+church
+citizen
+city
+civil
+claim
+class
+clear
+clearly
+close
+coach
+cold
+collection
+college
+color
+come
+commercial
+common
+community
+company
+compare
+computer
+concern
+condition
+conference
+Congress
+consider
+consumer
+contain
+continue
+control
+cost
+could
+country
+couple
+course
+court
+cover
+create
+crime
+cultural
+culture
+cup
+current
+customer
+cut
+dark
+data
+daughter
+day
+dead
+deal
+death
+debate
+decade
+decide
+decision
+deep
+defense
+degree
+Democrat
+democratic
+describe
+design
+despite
+detail
+determine
+develop
+development
+die
+difference
+different
+difficult
+dinner
+direction
+director
+discover
+discuss
+discussion
+disease
+do
+doctor
+dog
+door
+down
+draw
+dream
+drive
+drop
+drug
+during
+each
+early
+east
+easy
+eat
+economic
+economy
+edge
+education
+effect
+effort
+eight
+either
+election
+else
+employee
+end
+energy
+enjoy
+enough
+enter
+entire
+environment
+environmental
+especially
+establish
+even
+evening
+event
+ever
+every
+everybody
+everyone
+everything
+evidence
+exactly
+example
+executive
+exist
+expect
+experience
+expert
+explain
+eye
+face
+fact
+factor
+fail
+fall
+family
+far
+fast
+father
+fear
+federal
+feel
+feeling
+few
+field
+fight
+figure
+fill
+film
+final
+finally
+financial
+find
+fine
+finger
+finish
+fire
+firm
+first
+fish
+five
+floor
+fly
+focus
+follow
+food
+foot
+for
+force
+foreign
+forget
+form
+former
+forward
+four
+free
+friend
+from
+front
+full
+fund
+future
+game
+garden
+gas
+general
+generation
+get
+girl
+give
+glass
+go
+goal
+good
+government
+great
+green
+ground
+group
+grow
+growth
+guess
+gun
+guy
+hair
+half
+hand
+hang
+happen
+happy
+hard
+have
+he
+head
+health
+hear
+heart
+heat
+heavy
+help
+her
+here
+herself
+high
+him
+himself
+his
+history
+hit
+hold
+home
+hope
+hospital
+hot
+hotel
+hour
+house
+how
+however
+huge
+human
+hundred
+husband
+I
+idea
+identify
+if
+image
+imagine
+impact
+important
+improve
+in
+include
+including
+increase
+indeed
+indicate
+individual
+industry
+information
+inside
+instead
+institution
+interest
+interesting
+international
+interview
+into
+investment
+involve
+issue
+it
+item
+its
+itself
+job
+join
+just
+keep
+key
+kid
+kill
+kind
+kitchen
+know
+knowledge
+land
+language
+large
+last
+late
+later
+laugh
+law
+lawyer
+lay
+lead
+leader
+learn
+least
+leave
+left
+leg
+legal
+less
+let
+letter
+level
+lie
+life
+light
+like
+likely
+line
+list
+listen
+little
+live
+local
+long
+look
+lose
+loss
+lot
+love
+low
+machine
+magazine
+main
+maintain
+major
+majority
+make
+man
+manage
+management
+manager
+many
+market
+marriage
+material
+matter
+may
+maybe
+me
+mean
+measure
+media
+medical
+meet
+meeting
+member
+memory
+mention
+message
+method
+middle
+might
+military
+million
+mind
+minute
+miss
+mission
+model
+modern
+moment
+money
+month
+more
+morning
+most
+mother
+mouth
+move
+movement
+movie
+Mr
+Mrs
+much
+music
+must
+my
+myself
+name
+nation
+national
+natural
+nature
+near
+nearly
+necessary
+need
+network
+never
+new
+news
+newspaper
+next
+nice
+night
+no
+none
+nor
+north
+not
+note
+nothing
+notice
+now
+n't
+number
+occur
+of
+off
+offer
+office
+officer
+official
+often
+oh
+oil
+ok
+old
+on
+once
+one
+only
+onto
+open
+operation
+opportunity
+option
+or
+order
+organization
+other
+others
+our
+out
+outside
+over
+own
+owner
+page
+pain
+painting
+paper
+parent
+part
+participant
+particular
+particularly
+partner
+party
+pass
+past
+patient
+pattern
+pay
+peace
+people
+per
+perform
+performance
+perhaps
+period
+person
+personal
+phone
+physical
+pick
+picture
+piece
+place
+plan
+plant
+play
+player
+PM
+point
+police
+policy
+political
+politics
+poor
+popular
+population
+position
+positive
+possible
+power
+practice
+prepare
+present
+president
+pressure
+pretty
+prevent
+price
+private
+probably
+problem
+process
+produce
+product
+production
+professional
+professor
+program
+project
+property
+protect
+prove
+provide
+public
+pull
+purpose
+push
+put
+quality
+question
+quickly
+quite
+race
+radio
+raise
+range
+rate
+rather
+reach
+read
+ready
+real
+reality
+realize
+really
+reason
+receive
+recent
+recently
+recognize
+record
+red
+reduce
+reflect
+region
+relate
+relationship
+religious
+remain
+remember
+remove
+report
+represent
+Republican
+require
+research
+resource
+respond
+response
+responsibility
+rest
+result
+return
+reveal
+rich
+right
+rise
+risk
+road
+rock
+role
+room
+rule
+run
+safe
+same
+save
+say
+scene
+school
+science
+scientist
+score
+sea
+season
+seat
+second
+section
+security
+see
+seek
+seem
+sell
+send
+senior
+sense
+series
+serious
+serve
+service
+set
+seven
+several
+sex
+sexual
+shake
+share
+she
+shoot
+short
+shot
+should
+shoulder
+show
+side
+sign
+significant
+similar
+simple
+simply
+since
+sing
+single
+sister
+sit
+site
+situation
+six
+size
+skill
+skin
+small
+smile
+so
+social
+society
+soldier
+some
+somebody
+someone
+something
+sometimes
+son
+song
+soon
+sort
+sound
+source
+south
+southern
+space
+speak
+special
+specific
+speech
+spend
+sport
+spring
+staff
+stage
+stand
+standard
+star
+start
+state
+statement
+station
+stay
+step
+still
+stock
+stop
+store
+story
+strategy
+street
+strong
+structure
+student
+study
+stuff
+style
+subject
+success
+successful
+such
+suddenly
+suffer
+suggest
+summer
+support
+sure
+surface
+system
+table
+take
+talk
+task
+tax
+teach
+teacher
+team
+technology
+television
+tell
+ten
+tend
+term
+test
+than
+thank
+that
+the
+their
+them
+themselves
+then
+theory
+there
+these
+they
+thing
+think
+third
+this
+those
+though
+thought
+thousand
+threat
+three
+through
+throughout
+throw
+thus
+time
+to
+today
+together
+tonight
+too
+top
+total
+tough
+toward
+town
+trade
+traditional
+training
+travel
+treat
+treatment
+tree
+trial
+trip
+trouble
+true
+truth
+try
+turn
+TV
+two
+type
+under
+understand
+unit
+until
+up
+upon
+us
+use
+usually
+value
+various
+very
+victim
+view
+violence
+visit
+voice
+vote
+wait
+walk
+wall
+want
+war
+watch
+water
+way
+we
+weapon
+wear
+week
+weight
+well
+west
+western
+what
+whatever
+when
+where
+whether
+which
+while
+white
+who
+whole
+whom
+whose
+why
+wide
+wife
+will
+win
+wind
+window
+wish
+with
+within
+without
+woman
+wonder
+word
+work
+worker
+world
+worry
+would
+write
+writer
+wrong
+yard
+yeah
+year
+yes
+yet
+you
+young
+your
+yourself
diff --git a/lib/util/test/xxhash.c b/lib/util/test/xxhash.c
new file mode 100644
index 0000000..17374fd
--- /dev/null
+++ b/lib/util/test/xxhash.c
@@ -0,0 +1,66 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * xxhash.c
+ *
+ * Copyright (C) 2020 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+#include "util/test.h"
+
+static const struct {
+	const char *plaintext;
+	size_t psize;
+	sqfs_u32 digest;
+} test_vectors[] = {
+	{
+		.plaintext = "\x9e",
+		.psize = 1,
+		.digest = 0xB85CBEE5,
+	},
+	{
+		.plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd"
+		"\xb5\x54\x4d\x2a\x95\x2b",
+		.psize = 14,
+		.digest = 0xE5AA0AB4,
+	},
+	{
+		.plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd"
+		"\xb5\x54\x4d\x2a\x95\x2b\x57\xae"
+		"\x5d\xba\x74\xe9\xd3\xa6\x4c\x98"
+		"\x30\x60\xc0\x80\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00\x00\x00\x00"
+		"\x00\x00\x00\x00\x00",
+		.psize = 101,
+		.digest = 0x018F52BC,
+	},
+};
+
+int main(int argc, char **argv)
+{
+	sqfs_u32 hash;
+	size_t i;
+	(void)argc; (void)argv;
+
+	for (i = 0; i < sizeof(test_vectors) / sizeof(test_vectors[0]); ++i) {
+		hash = xxh32(test_vectors[i].plaintext, test_vectors[i].psize);
+
+		if (hash != test_vectors[i].digest) {
+			fprintf(stderr, "Test case " PRI_SZ " failed!\n", i);
+			fprintf(stderr, "Expected result: 0x%08X\n",
+				test_vectors[i].digest);
+			fprintf(stderr, "Actual result:   0x%08X\n", hash);
+			return EXIT_FAILURE;
+		}
+	}
+
+	return EXIT_SUCCESS;
+}