Move library source into src sub-directory

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

18 files changed, 2562 insertions, 0 deletions

diff --git a/lib/util/src/alloc.c b/lib/util/src/alloc.c
new file mode 100644
index 0000000..359fef5
--- /dev/null
+++ b/lib/util/src/alloc.c
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * alloc.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+
+#include <stdlib.h>
+#include <errno.h>
+
+void *alloc_flex(size_t base_size, size_t item_size, size_t nmemb)
+{
+	size_t size;
+
+	if (SZ_MUL_OV(nmemb, item_size, &size) ||
+	    SZ_ADD_OV(base_size, size, &size)) {
+		errno = EOVERFLOW;
+		return NULL;
+	}
+
+	return calloc(1, size);
+}
+
+void *alloc_array(size_t item_size, size_t nmemb)
+{
+	size_t size;
+
+	if (SZ_MUL_OV(nmemb, item_size, &size)) {
+		errno = EOVERFLOW;
+		return NULL;
+	}
+
+	return calloc(1, size);
+}
diff --git a/lib/util/src/array.c b/lib/util/src/array.c
new file mode 100644
index 0000000..40bac50
--- /dev/null
+++ b/lib/util/src/array.c
@@ -0,0 +1,115 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * array.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "compat.h"
+#include "util/array.h"
+
+#include "sqfs/error.h"
+
+#include <stdlib.h>
+
+int array_init(array_t *array, size_t size, size_t capacity)
+{
+	size_t total;
+
+	memset(array, 0, sizeof(*array));
+
+	if (capacity > 0) {
+		if (SZ_MUL_OV(size, capacity, &total))
+			return SQFS_ERROR_OVERFLOW;
+
+		array->data = malloc(total);
+		if (array->data == NULL)
+			return SQFS_ERROR_ALLOC;
+	}
+
+	array->size = size;
+	array->count = capacity;
+	return 0;
+}
+
+int array_init_copy(array_t *array, const array_t *src)
+{
+	int ret;
+
+	ret = array_init(array, src->size, src->used);
+	if (ret != 0)
+		return ret;
+
+	memcpy(array->data, src->data, src->used * src->size);
+	array->used = src->used;
+	return 0;
+}
+
+void array_cleanup(array_t *array)
+{
+	free(array->data);
+	memset(array, 0, sizeof(*array));
+}
+
+int array_append(array_t *array, const void *data)
+{
+	size_t new_sz, new_count;
+	void *new;
+
+	if (array->used == array->count) {
+		if (array->count == 0) {
+			new_count = 128;
+		} else {
+			if (SZ_MUL_OV(array->count, 2, &new_count))
+				return SQFS_ERROR_ALLOC;
+		}
+
+		if (SZ_MUL_OV(new_count, array->size, &new_sz))
+			return SQFS_ERROR_ALLOC;
+
+		new = realloc(array->data, new_sz);
+		if (new == NULL)
+			return SQFS_ERROR_ALLOC;
+
+		array->data = new;
+		array->count = new_count;
+	}
+
+	memcpy((char *)array->data + array->size * array->used,
+	       data, array->size);
+
+	array->used += 1;
+	return 0;
+}
+
+int array_set_capacity(array_t *array, size_t capacity)
+{
+	size_t new_sz, new_count;
+	void *new;
+
+	if (capacity <= array->count)
+		return 0;
+
+	if (array->count == 0) {
+		new_count = 128;
+	} else {
+		if (SZ_MUL_OV(array->count, 2, &new_count))
+			return SQFS_ERROR_ALLOC;
+	}
+
+	while (new_count < capacity) {
+		if (SZ_MUL_OV(new_count, 2, &new_count))
+			return SQFS_ERROR_ALLOC;
+	}
+
+	if (SZ_MUL_OV(new_count, array->size, &new_sz))
+		return SQFS_ERROR_ALLOC;
+
+	new = realloc(array->data, new_sz);
+	if (new == NULL)
+		return SQFS_ERROR_ALLOC;
+
+	array->data = new;
+	array->count = new_count;
+	return 0;
+}
diff --git a/lib/util/src/base64_decode.c b/lib/util/src/base64_decode.c
new file mode 100644
index 0000000..b1cf5b6
--- /dev/null
+++ b/lib/util/src/base64_decode.c
@@ -0,0 +1,103 @@
+/* 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"
+
+#include <ctype.h>
+
+static int base64_digit(int c)
+{
+	if (isupper(c))
+		return c - 'A';
+	if (islower(c))
+		return c - 'a' + 26;
+	if (isdigit(c))
+		return c - '0' + 52;
+	if (c == '+')
+		return 62;
+	if (c == '/' || c == '-')
+		return 63;
+	return -1;
+}
+
+int base64_decode(const char *in, size_t in_len, sqfs_u8 *out, size_t *out_len)
+{
+	int i1, i2, i3, i4;
+	size_t count = 0;
+
+	while (in_len >= 4) {
+		i1 = base64_digit(*(in++));
+		i2 = base64_digit(*(in++));
+		i3 = *(in++);
+		i4 = *(in++);
+		in_len -= 4;
+
+		if (i1 < 0 || i2 < 0 || count >= *out_len)
+			goto fail;
+
+		out[count++] = (i1 << 2) | (i2 >> 4);
+
+		if (i3 == '=' || i3 == '_') {
+			if ((i4 != '=' && i4 != '_') || in_len > 0)
+				goto fail;
+			break;
+		}
+
+		i3 = base64_digit(i3);
+		if (i3 < 0 || count >= *out_len)
+			goto fail;
+
+		out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2);
+
+		if (i4 == '=' || i4 == '_') {
+			if (in_len > 0)
+				goto fail;
+			break;
+		}
+
+		i4 = base64_digit(i4);
+		if (i4 < 0 || count >= *out_len)
+			goto fail;
+
+		out[count++] = ((i3 & 0x3) << 6) | i4;
+	}
+
+	/* libarchive has this bizarre bastardization of truncated base64 */
+	if (in_len > 0) {
+		if (in_len == 1)
+			goto fail;
+
+		i1 = base64_digit(*(in++));
+		i2 = base64_digit(*(in++));
+		in_len -= 2;
+
+		if (i1 < 0 || i2 < 0 || count >= *out_len)
+			goto fail;
+
+		out[count++] = (i1 << 2) | (i2 >> 4);
+
+		if (in_len > 0) {
+			i3 = *(in++);
+			--in_len;
+
+			if (i3 != '=' && i3 != '_') {
+				i3 = base64_digit(i3);
+				if (i3 < 0 || count >= *out_len)
+					goto fail;
+
+				out[count++] = ((i2 & 0x0F) << 4) | (i3 >> 2);
+			}
+		}
+	}
+
+	*out_len = count;
+	return 0;
+fail:
+	*out_len = 0;
+	return -1;
+}
diff --git a/lib/util/src/canonicalize_name.c b/lib/util/src/canonicalize_name.c
new file mode 100644
index 0000000..534e89e
--- /dev/null
+++ b/lib/util/src/canonicalize_name.c
@@ -0,0 +1,60 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * canonicalize_name.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+
+static void normalize_slashes(char *filename)
+{
+	char *dst = filename, *src = filename;
+
+	while (*src == '/')
+		++src;
+
+	while (*src != '\0') {
+		if (*src == '/') {
+			while (*src == '/')
+				++src;
+			if (*src == '\0')
+				break;
+			*(dst++) = '/';
+		} else {
+			*(dst++) = *(src++);
+		}
+	}
+
+	*dst = '\0';
+}
+
+int canonicalize_name(char *filename)
+{
+	char *dst = filename, *src = filename;
+
+	normalize_slashes(filename);
+
+	while (*src != '\0') {
+		if (src[0] == '.') {
+			if (src[1] == '\0')
+				break;
+			if (src[1] == '/') {
+				src += 2;
+				continue;
+			}
+			if (src[1] == '.' && (src[2] == '/' || src[2] == '\0'))
+				return -1;
+		}
+
+		while (*src != '\0' && *src != '/')
+			*(dst++) = *(src++);
+
+		if (*src == '/')
+			*(dst++) = *(src++);
+	}
+
+	*dst = '\0';
+	normalize_slashes(filename);
+	return 0;
+}
diff --git a/lib/util/src/fast_urem_by_const.h b/lib/util/src/fast_urem_by_const.h
new file mode 100644
index 0000000..4fb78d3
--- /dev/null
+++ b/lib/util/src/fast_urem_by_const.h
@@ -0,0 +1,77 @@
+/*
+ * Copyright © 2010 Valve Software
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include "sqfs/predef.h"
+
+#include <assert.h>
+#include <stdint.h>
+
+/*
+ * Code for fast 32-bit unsigned remainder, based off of "Faster Remainder by
+ * Direct Computation: Applications to Compilers and Software Libraries,"
+ * available at https://arxiv.org/pdf/1902.01961.pdf.
+ *
+ * util_fast_urem32(n, d, REMAINDER_MAGIC(d)) returns the same thing as
+ * n % d for any unsigned n and d, however it compiles down to only a few
+ * multiplications, so it should be faster than plain sqfs_u32 modulo if the
+ * same divisor is used many times.
+ */
+
+#define REMAINDER_MAGIC(divisor) \
+   ((sqfs_u64) ~0ull / (divisor) + 1)
+
+/*
+ * Get bits 64-96 of a 32x64-bit multiply. If __int128_t is available, we use
+ * it, which usually compiles down to one instruction on 64-bit architectures.
+ * Otherwise on 32-bit architectures we usually get four instructions (one
+ * 32x32->64 multiply, one 32x32->32 multiply, and one 64-bit add).
+ */
+
+static inline sqfs_u32
+_mul32by64_hi(sqfs_u32 a, sqfs_u64 b)
+{
+#if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16
+   return ((__uint128_t) b * a) >> 64;
+#else
+   /*
+    * Let b = b0 + 2^32 * b1. Then a * b = a * b0 + 2^32 * a * b1. We would
+    * have to do a 96-bit addition to get the full result, except that only
+    * one term has non-zero lower 32 bits, which means that to get the high 32
+    * bits, we only have to add the high 64 bits of each term. Unfortunately,
+    * we have to do the 64-bit addition in case the low 32 bits overflow.
+    */
+   sqfs_u32 b0 = (sqfs_u32) b;
+   sqfs_u32 b1 = b >> 32;
+   return ((((sqfs_u64) a * b0) >> 32) + (sqfs_u64) a * b1) >> 32;
+#endif
+}
+
+static inline sqfs_u32
+util_fast_urem32(sqfs_u32 n, sqfs_u32 d, sqfs_u64 magic)
+{
+   sqfs_u64 lowbits = magic * n;
+   sqfs_u32 result = _mul32by64_hi(d, lowbits);
+   assert(result == n % d);
+   return result;
+}
+
diff --git a/lib/util/src/file_cmp.c b/lib/util/src/file_cmp.c
new file mode 100644
index 0000000..2aa0cc2
--- /dev/null
+++ b/lib/util/src/file_cmp.c
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * file_cmp.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "util/util.h"
+#include "sqfs/io.h"
+
+#include <string.h>
+
+int check_file_range_equal(sqfs_file_t *file, void *scratch, size_t scratch_sz,
+			   sqfs_u64 loc_a, sqfs_u64 loc_b, sqfs_u64 size)
+{
+	sqfs_u8 *ptr_a = scratch, *ptr_b = ptr_a + scratch_sz / 2;
+	int ret;
+
+	while (size > 0) {
+		size_t diff = scratch_sz / 2;
+		diff = (sqfs_u64)diff > size ? size : diff;
+
+		ret = file->read_at(file, loc_a, ptr_a, diff);
+		if (ret != 0)
+			return ret;
+
+		ret = file->read_at(file, loc_b, ptr_b, diff);
+		if (ret != 0)
+			return ret;
+
+		if (memcmp(ptr_a, ptr_b, diff) != 0)
+			return 1;
+
+		size -= diff;
+		loc_a += diff;
+		loc_b += diff;
+	}
+
+	return 0;
+}
diff --git a/lib/util/src/filename_sane.c b/lib/util/src/filename_sane.c
new file mode 100644
index 0000000..b52ce4d
--- /dev/null
+++ b/lib/util/src/filename_sane.c
@@ -0,0 +1,78 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * filename_sane.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+
+#include <string.h>
+
+#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32)
+#ifdef _MSC_VER
+#define strncasecmp _strnicmp
+#define strcasecmp _stricmp
+#endif
+
+static const char *bad_names[] = {
+	"CON", "PRN", "AUX", "NUL",
+	"COM1", "COM2", "COM3", "COM4", "COM5", "COM6", "COM7", "COM8", "COM9",
+	"LPT1", "LPT2", "LPT3", "LPT4", "LPT5", "LPT6", "LPT7", "LPT8", "LPT9",
+};
+
+static bool is_allowed_by_os(const char *name)
+{
+	size_t len, i;
+
+	for (i = 0; i < sizeof(bad_names) / sizeof(bad_names[0]); ++i) {
+		len = strlen(bad_names[i]);
+
+		if (strncasecmp(name, bad_names[i], len) != 0)
+			continue;
+
+		if (name[len] == '\0')
+			return false;
+
+		if (name[len] == '.' && strchr(name + len + 1, '.') == NULL)
+			return false;
+	}
+
+	return true;
+}
+#else
+static bool is_allowed_by_os(const char *name)
+{
+	(void)name;
+	return true;
+}
+#endif
+
+bool is_filename_sane(const char *name, bool check_os_specific)
+{
+	if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
+		return false;
+
+	if (check_os_specific && !is_allowed_by_os(name))
+		return false;
+
+	while (*name != '\0') {
+		if (*name == '/')
+			return false;
+
+#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32)
+		if (check_os_specific) {
+			if (*name == '<' || *name == '>' || *name == ':')
+				return false;
+			if (*name == '"' || *name == '|' || *name == '?')
+				return false;
+			if (*name == '*' || *name == '\\' || *name <= 31)
+				return false;
+		}
+#endif
+
+		++name;
+	}
+
+	return true;
+}
diff --git a/lib/util/src/hash_table.c b/lib/util/src/hash_table.c
new file mode 100644
index 0000000..0010e9f
--- /dev/null
+++ b/lib/util/src/hash_table.c
@@ -0,0 +1,417 @@
+/*
+ * Copyright © 2009,2012 Intel Corporation
+ * Copyright © 1988-2004 Keith Packard and Bart Massey.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Except as contained in this notice, the names of the authors
+ * or their institutions shall not be used in advertising or
+ * otherwise to promote the sale, use or other dealings in this
+ * Software without prior written authorization from the
+ * authors.
+ *
+ * Authors:
+ *    Eric Anholt <eric@anholt.net>
+ *    Keith Packard <keithp@keithp.com>
+ */
+
+/**
+ * Implements an open-addressing, linear-reprobing hash table.
+ *
+ * For more information, see:
+ *
+ * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "fast_urem_by_const.h"
+#include "util/hash_table.h"
+
+#  define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
+static const sqfs_u32 deleted_key_value;
+
+/**
+ * From Knuth -- a good choice for hash/rehash values is p, p-2 where
+ * p and p-2 are both prime.  These tables are sized to have an extra 10%
+ * free to avoid exponential performance degradation as the hash table fills
+ */
+static const struct {
+   sqfs_u32 max_entries, size, rehash;
+   sqfs_u64 size_magic, rehash_magic;
+} hash_sizes[] = {
+#define ENTRY(max_entries, size, rehash) \
+   { max_entries, size, rehash, \
+      REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
+
+   ENTRY(2,            5,            3            ),
+   ENTRY(4,            7,            5            ),
+   ENTRY(8,            13,           11           ),
+   ENTRY(16,           19,           17           ),
+   ENTRY(32,           43,           41           ),
+   ENTRY(64,           73,           71           ),
+   ENTRY(128,          151,          149          ),
+   ENTRY(256,          283,          281          ),
+   ENTRY(512,          571,          569          ),
+   ENTRY(1024,         1153,         1151         ),
+   ENTRY(2048,         2269,         2267         ),
+   ENTRY(4096,         4519,         4517         ),
+   ENTRY(8192,         9013,         9011         ),
+   ENTRY(16384,        18043,        18041        ),
+   ENTRY(32768,        36109,        36107        ),
+   ENTRY(65536,        72091,        72089        ),
+   ENTRY(131072,       144409,       144407       ),
+   ENTRY(262144,       288361,       288359       ),
+   ENTRY(524288,       576883,       576881       ),
+   ENTRY(1048576,      1153459,      1153457      ),
+   ENTRY(2097152,      2307163,      2307161      ),
+   ENTRY(4194304,      4613893,      4613891      ),
+   ENTRY(8388608,      9227641,      9227639      ),
+   ENTRY(16777216,     18455029,     18455027     ),
+   ENTRY(33554432,     36911011,     36911009     ),
+   ENTRY(67108864,     73819861,     73819859     ),
+   ENTRY(134217728,    147639589,    147639587    ),
+   ENTRY(268435456,    295279081,    295279079    ),
+   ENTRY(536870912,    590559793,    590559791    ),
+   ENTRY(1073741824,   1181116273,   1181116271   ),
+   ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
+};
+
+static inline bool
+key_pointer_is_reserved(const struct hash_table *ht, const void *key)
+{
+   return key == NULL || key == ht->deleted_key;
+}
+
+static int
+entry_is_free(const struct hash_entry *entry)
+{
+   return entry->key == NULL;
+}
+
+static int
+entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry)
+{
+   return entry->key == ht->deleted_key;
+}
+
+static int
+entry_is_present(const struct hash_table *ht, struct hash_entry *entry)
+{
+   return entry->key != NULL && entry->key != ht->deleted_key;
+}
+
+static bool
+hash_table_init(struct hash_table *ht,
+                sqfs_u32 (*key_hash_function)(void *user, const void *key),
+                bool (*key_equals_function)(void *user, const void *a,
+                                            const void *b))
+{
+   ht->size_index = 0;
+   ht->size = hash_sizes[ht->size_index].size;
+   ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->size_magic = hash_sizes[ht->size_index].size_magic;
+   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
+   ht->max_entries = hash_sizes[ht->size_index].max_entries;
+   ht->key_hash_function = key_hash_function;
+   ht->key_equals_function = key_equals_function;
+   ht->table = calloc(sizeof(struct hash_entry), ht->size);
+   ht->entries = 0;
+   ht->deleted_entries = 0;
+   ht->deleted_key = &deleted_key_value;
+
+   return ht->table != NULL;
+}
+
+struct hash_table *
+hash_table_create(sqfs_u32 (*key_hash_function)(void *user, const void *key),
+                  bool (*key_equals_function)(void *user, const void *a,
+                                              const void *b))
+{
+   struct hash_table *ht;
+
+   ht = malloc(sizeof(struct hash_table));
+   if (ht == NULL)
+      return NULL;
+
+   if (!hash_table_init(ht, key_hash_function, key_equals_function)) {
+      free(ht);
+      return NULL;
+   }
+
+   return ht;
+}
+
+struct hash_table *
+hash_table_clone(struct hash_table *src)
+{
+   struct hash_table *ht;
+
+   ht = malloc(sizeof(struct hash_table));
+   if (ht == NULL)
+      return NULL;
+
+   memcpy(ht, src, sizeof(struct hash_table));
+
+   ht->table = calloc(sizeof(struct hash_entry), ht->size);
+   if (ht->table == NULL) {
+      free(ht);
+      return NULL;
+   }
+
+   memcpy(ht->table, src->table, ht->size * sizeof(struct hash_entry));
+
+   return ht;
+}
+
+/**
+ * Frees the given hash table.
+ */
+void
+hash_table_destroy(struct hash_table *ht,
+		   void (*delete_function)(struct hash_entry *entry))
+{
+   if (!ht)
+      return;
+
+   if (delete_function) {
+      hash_table_foreach(ht, entry) {
+         delete_function(entry);
+      }
+   }
+   free(ht->table);
+   free(ht);
+}
+
+static struct hash_entry *
+hash_table_search(struct hash_table *ht, sqfs_u32 hash, const void *key)
+{
+   assert(!key_pointer_is_reserved(ht, key));
+
+   sqfs_u32 size = ht->size;
+   sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
+   sqfs_u32 hash_address = start_hash_address;
+
+   do {
+      struct hash_entry *entry = ht->table + hash_address;
+
+      if (entry_is_free(entry)) {
+         return NULL;
+      } else if (entry_is_present(ht, entry) && entry->hash == hash) {
+         if (ht->key_equals_function(ht->user, key, entry->key)) {
+            return entry;
+         }
+      }
+
+      hash_address += double_hash;
+      if (hash_address >= size)
+         hash_address -= size;
+   } while (hash_address != start_hash_address);
+
+   return NULL;
+}
+
+/**
+ * Finds a hash table entry with the given key and hash of that key.
+ *
+ * Returns NULL if no entry is found.  Note that the data pointer may be
+ * modified by the user.
+ */
+struct hash_entry *
+hash_table_search_pre_hashed(struct hash_table *ht, sqfs_u32 hash,
+                             const void *key)
+{
+   assert(ht->key_hash_function == NULL ||
+          hash == ht->key_hash_function(ht->user, key));
+   return hash_table_search(ht, hash, key);
+}
+
+static void
+hash_table_insert_rehash(struct hash_table *ht, sqfs_u32 hash,
+                         const void *key, void *data)
+{
+   sqfs_u32 size = ht->size;
+   sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
+   sqfs_u32 hash_address = start_hash_address;
+   do {
+      struct hash_entry *entry = ht->table + hash_address;
+
+      if (entry->key == NULL) {
+         entry->hash = hash;
+         entry->key = key;
+         entry->data = data;
+         return;
+      }
+
+      hash_address += double_hash;
+      if (hash_address >= size)
+         hash_address -= size;
+   } while (true);
+}
+
+static void
+hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
+{
+   struct hash_table old_ht;
+   struct hash_entry *table;
+
+   if (new_size_index >= ARRAY_SIZE(hash_sizes))
+      return;
+
+   table = calloc(sizeof(struct hash_entry), hash_sizes[new_size_index].size);
+   if (table == NULL)
+      return;
+
+   old_ht = *ht;
+
+   ht->table = table;
+   ht->size_index = new_size_index;
+   ht->size = hash_sizes[ht->size_index].size;
+   ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->size_magic = hash_sizes[ht->size_index].size_magic;
+   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
+   ht->max_entries = hash_sizes[ht->size_index].max_entries;
+   ht->entries = 0;
+   ht->deleted_entries = 0;
+
+   hash_table_foreach(&old_ht, entry) {
+      hash_table_insert_rehash(ht, entry->hash, entry->key, entry->data);
+   }
+
+   ht->entries = old_ht.entries;
+
+   free(old_ht.table);
+}
+
+static struct hash_entry *
+hash_table_insert(struct hash_table *ht, sqfs_u32 hash,
+                  const void *key, void *data)
+{
+   struct hash_entry *available_entry = NULL;
+
+   assert(!key_pointer_is_reserved(ht, key));
+
+   if (ht->entries >= ht->max_entries) {
+      hash_table_rehash(ht, ht->size_index + 1);
+   } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
+      hash_table_rehash(ht, ht->size_index);
+   }
+
+   sqfs_u32 size = ht->size;
+   sqfs_u32 start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   sqfs_u32 double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
+   sqfs_u32 hash_address = start_hash_address;
+   do {
+      struct hash_entry *entry = ht->table + hash_address;
+
+      if (!entry_is_present(ht, entry)) {
+         /* Stash the first available entry we find */
+         if (available_entry == NULL)
+            available_entry = entry;
+         if (entry_is_free(entry))
+            break;
+      }
+
+      /* Implement replacement when another insert happens
+       * with a matching key.  This is a relatively common
+       * feature of hash tables, with the alternative
+       * generally being "insert the new value as well, and
+       * return it first when the key is searched for".
+       *
+       * Note that the hash table doesn't have a delete
+       * callback.  If freeing of old data pointers is
+       * required to avoid memory leaks, perform a search
+       * before inserting.
+       */
+      if (!entry_is_deleted(ht, entry) &&
+          entry->hash == hash &&
+          ht->key_equals_function(ht->user, key, entry->key)) {
+         entry->key = key;
+         entry->data = data;
+         return entry;
+      }
+
+      hash_address += double_hash;
+      if (hash_address >= size)
+         hash_address -= size;
+   } while (hash_address != start_hash_address);
+
+   if (available_entry) {
+      if (entry_is_deleted(ht, available_entry))
+         ht->deleted_entries--;
+      available_entry->hash = hash;
+      available_entry->key = key;
+      available_entry->data = data;
+      ht->entries++;
+      return available_entry;
+   }
+
+   /* We could hit here if a required resize failed. An unchecked-malloc
+    * application could ignore this result.
+    */
+   return NULL;
+}
+
+/**
+ * Inserts the key with the given hash into the table.
+ *
+ * Note that insertion may rearrange the table on a resize or rehash,
+ * so previously found hash_entries are no longer valid after this function.
+ */
+struct hash_entry *
+hash_table_insert_pre_hashed(struct hash_table *ht, sqfs_u32 hash,
+                             const void *key, void *data)
+{
+   assert(ht->key_hash_function == NULL ||
+          hash == ht->key_hash_function(ht->user, key));
+   return hash_table_insert(ht, hash, key, data);
+}
+
+/**
+ * This function is an iterator over the hash table.
+ *
+ * Pass in NULL for the first entry, as in the start of a for loop.  Note that
+ * an iteration over the table is O(table_size) not O(entries).
+ */
+struct hash_entry *
+hash_table_next_entry(struct hash_table *ht,
+                      struct hash_entry *entry)
+{
+   if (entry == NULL)
+      entry = ht->table;
+   else
+      entry = entry + 1;
+
+   for (; entry != ht->table + ht->size; entry++) {
+      if (entry_is_present(ht, entry)) {
+         return entry;
+      }
+   }
+
+   return NULL;
+}
diff --git a/lib/util/src/hex_decode.c b/lib/util/src/hex_decode.c
new file mode 100644
index 0000000..ee4b21c
--- /dev/null
+++ b/lib/util/src/hex_decode.c
@@ -0,0 +1,34 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * hex_decode.h
+ *
+ * Copyright (C) 2022 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/util.h"
+
+#include <ctype.h>
+
+static sqfs_u8 xdigit(int in)
+{
+	if (isupper(in))
+		return in - 'A' + 10;
+	if (islower(in))
+		return in - 'a' + 10;
+	return in - '0';
+}
+
+int hex_decode(const char *in, size_t in_sz, sqfs_u8 *out, size_t out_sz)
+{
+	while (out_sz > 0 && in_sz >= 2 &&
+	       isxdigit(in[0]) && isxdigit(in[1])) {
+		sqfs_u8 hi = xdigit(*(in++));
+		sqfs_u8 lo = xdigit(*(in++));
+
+		*(out++) = (hi << 4) | lo;
+
+		in_sz -= 2;
+		--out_sz;
+	}
+
+	return (in_sz > 0) ? -1 : 0;
+}
diff --git a/lib/util/src/is_memory_zero.c b/lib/util/src/is_memory_zero.c
new file mode 100644
index 0000000..aabd45d
--- /dev/null
+++ b/lib/util/src/is_memory_zero.c
@@ -0,0 +1,54 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * is_memory_zero.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "util/util.h"
+
+#include <stdint.h>
+
+#define U64THRESHOLD (128)
+
+static bool test_u8(const unsigned char *blob, size_t size)
+{
+	while (size--) {
+		if (*(blob++) != 0)
+			return false;
+	}
+
+	return true;
+}
+
+bool is_memory_zero(const void *blob, size_t size)
+{
+	const sqfs_u64 *u64ptr;
+	size_t diff;
+
+	if (size < U64THRESHOLD)
+		return test_u8(blob, size);
+
+	diff = (uintptr_t)blob % sizeof(sqfs_u64);
+
+	if (diff != 0) {
+		diff = sizeof(sqfs_u64) - diff;
+
+		if (!test_u8(blob, diff))
+			return false;
+
+		blob = (const char *)blob + diff;
+		size -= diff;
+	}
+
+	u64ptr = blob;
+
+	while (size >= sizeof(sqfs_u64)) {
+		if (*(u64ptr++) != 0)
+			return false;
+
+		size -= sizeof(sqfs_u64);
+	}
+
+	return test_u8((const unsigned char *)u64ptr, size);
+}
diff --git a/lib/util/src/mempool.c b/lib/util/src/mempool.c
new file mode 100644
index 0000000..e2ddaf0
--- /dev/null
+++ b/lib/util/src/mempool.c
@@ -0,0 +1,216 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * mempool.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/mempool.h"
+
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+#include <assert.h>
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+#define WIN32_LEAN_AND_MEAN
+#include <windows.h>
+#else
+#include <sys/mman.h>
+#endif
+
+#define DEF_POOL_SIZE (65536)
+#define MEM_ALIGN (8)
+
+typedef struct pool_t {
+	struct pool_t *next;
+
+	unsigned char *data;
+	unsigned char *limit;
+
+	unsigned int *bitmap;
+
+	size_t obj_free;
+
+	unsigned int blob[];
+} pool_t;
+
+struct mem_pool_t {
+	size_t obj_size;
+	size_t pool_size;
+	size_t bitmap_count;
+	pool_t *pool_list;
+};
+
+static size_t pool_size_from_bitmap_count(size_t count, size_t obj_size)
+{
+	size_t size, byte_count, bit_count;
+
+	size = sizeof(pool_t);
+	if (size % sizeof(unsigned int))
+		size += sizeof(unsigned int) - size % sizeof(unsigned int);
+
+	byte_count = count * sizeof(unsigned int);
+	bit_count = byte_count * CHAR_BIT;
+
+	size += byte_count;
+	if (size % obj_size)
+		size += obj_size - size % obj_size;
+
+	size += bit_count * obj_size;
+	return size;
+}
+
+static pool_t *create_pool(const mem_pool_t *mem)
+{
+	unsigned char *ptr;
+	pool_t *pool;
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+	pool = VirtualAlloc(NULL, mem->pool_size, MEM_RESERVE | MEM_COMMIT,
+			    PAGE_READWRITE);
+
+	if (pool == NULL)
+		return NULL;
+#else
+	pool = mmap(NULL, mem->pool_size, PROT_READ | PROT_WRITE,
+		    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	if (pool == MAP_FAILED)
+		return NULL;
+#endif
+	pool->bitmap = pool->blob;
+	pool->obj_free = mem->bitmap_count * sizeof(unsigned int) * CHAR_BIT;
+
+	ptr = (unsigned char *)(pool->bitmap + mem->bitmap_count);
+
+	if (((uintptr_t)ptr) % mem->obj_size) {
+		ptr += mem->obj_size;
+		ptr -= ((uintptr_t)ptr) % mem->obj_size;
+	}
+
+	pool->data = ptr;
+	pool->limit = pool->data + pool->obj_free * mem->obj_size - 1;
+
+	memset(pool->bitmap, 0, mem->bitmap_count * sizeof(unsigned int));
+	return pool;
+}
+
+mem_pool_t *mem_pool_create(size_t obj_size)
+{
+	mem_pool_t *mem = calloc(1, sizeof(*mem));
+	size_t count = 1, total;
+
+	if (mem == NULL)
+		return NULL;
+
+	if (obj_size % MEM_ALIGN)
+		obj_size += MEM_ALIGN - obj_size % MEM_ALIGN;
+
+	for (;;) {
+		total = pool_size_from_bitmap_count(count, obj_size);
+		if (total > DEF_POOL_SIZE)
+			break;
+		++count;
+	}
+
+	--count;
+
+	mem->obj_size = obj_size;
+	mem->pool_size = DEF_POOL_SIZE;
+	mem->bitmap_count = count;
+	return mem;
+}
+
+void mem_pool_destroy(mem_pool_t *mem)
+{
+	while (mem->pool_list != NULL) {
+		pool_t *pool = mem->pool_list;
+		mem->pool_list = pool->next;
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+		VirtualFree(pool, mem->pool_size, MEM_RELEASE);
+#else
+		munmap(pool, mem->pool_size);
+#endif
+	}
+
+	free(mem);
+}
+
+void *mem_pool_allocate(mem_pool_t *mem)
+{
+	size_t idx, i, j;
+	void *ptr = NULL;
+	pool_t *it;
+retry_pool:
+	for (it = mem->pool_list; it != NULL; it = it->next) {
+		if (it->obj_free > 0)
+			break;
+	}
+
+	if (it == NULL) {
+		it = create_pool(mem);
+		if (it == NULL)
+			return NULL;
+
+		it->next = mem->pool_list;
+		mem->pool_list = it;
+	}
+
+	for (i = 0; i < mem->bitmap_count; ++i) {
+		if (it->bitmap[i] < UINT_MAX)
+			break;
+	}
+
+	if (i == mem->bitmap_count) {
+		it->obj_free = 0;
+		goto retry_pool;
+	}
+
+	for (j = 0; j < (sizeof(it->bitmap[i]) * CHAR_BIT); ++j) {
+		if (!(it->bitmap[i] & (1UL << j)))
+			break;
+	}
+
+	if (j == (sizeof(it->bitmap[i]) * CHAR_BIT)) {
+		it->obj_free = 0;
+		goto retry_pool;
+	}
+
+	idx = i * sizeof(unsigned int) * CHAR_BIT + j;
+	ptr = it->data + idx * mem->obj_size;
+
+	it->bitmap[i] |= (1UL << j);
+	it->obj_free -= 1;
+
+	memset(ptr, 0, mem->obj_size);
+	return ptr;
+}
+
+void mem_pool_free(mem_pool_t *mem, void *ptr)
+{
+	size_t idx, i, j;
+	pool_t *it;
+
+	for (it = mem->pool_list; it != NULL; it = it->next) {
+		if ((unsigned char *)ptr >= it->data &&
+		    (unsigned char *)ptr < it->limit) {
+			break;
+		}
+	}
+
+	assert(it != NULL);
+
+	idx = (size_t)((unsigned char *)ptr - it->data);
+
+	assert((idx % mem->obj_size) == 0);
+	idx /= mem->obj_size;
+
+	i = idx / (sizeof(unsigned int) * CHAR_BIT);
+	j = idx % (sizeof(unsigned int) * CHAR_BIT);
+
+	assert((it->bitmap[i] & (1 << j)) != 0);
+
+	it->bitmap[i] &= ~(1 << j);
+	it->obj_free += 1;
+}
diff --git a/lib/util/src/mkdir_p.c b/lib/util/src/mkdir_p.c
new file mode 100644
index 0000000..993d8ec
--- /dev/null
+++ b/lib/util/src/mkdir_p.c
@@ -0,0 +1,170 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * mkdir_p.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/util.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+
+#ifdef _WIN32
+/*
+  Supported paths:
+   - <letter>:\ <absolute path>
+   - \\<server>\<share>\ <absolute path>
+   - \\?\<letter>:\ <absolute path>
+   - \\?\UNC\<server>\<share>\ <absolute path>
+   - Relative path not starting with '\'
+ */
+
+static WCHAR *skip_unc_path(WCHAR *ptr)
+{
+	/* server */
+	if (*ptr == '\0' || *ptr == '\\')
+		return NULL;
+
+	while (*ptr != '\0' && *ptr != '\\')
+		++ptr;
+
+	if (*(ptr++) != '\\')
+		return NULL;
+
+	/* share */
+	if (*ptr == '\0' || *ptr == '\\')
+		return NULL;
+
+	while (*ptr != '\0' && *ptr != '\\')
+		++ptr;
+
+	return (*ptr == '\\') ? (ptr + 1) : ptr;
+}
+
+static WCHAR *skip_prefix(WCHAR *ptr)
+{
+	if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\')
+		return ptr + 3;
+
+	if (ptr[0] == '\\' && ptr[1] == '\\') {
+		if (ptr[2] == '?') {
+			if (ptr[3] != '\\')
+				return NULL;
+
+			ptr += 4;
+
+			if ((ptr[0] == 'u' || ptr[0] == 'U') &&
+			    (ptr[1] == 'n' || ptr[1] == 'N') &&
+			    (ptr[2] == 'c' || ptr[2] == 'C') &&
+			    ptr[3] == '\\') {
+				ptr += 4;
+
+				return skip_unc_path(ptr);
+			}
+
+			if (isalpha(ptr[0]) && ptr[1] == ':' && ptr[2] == '\\')
+				return ptr + 3;
+
+			return NULL;
+		}
+
+		return skip_unc_path(ptr);
+	}
+
+	if (ptr[0] == '\\')
+		return NULL;
+
+	return ptr;
+}
+
+int mkdir_p(const char *path)
+{
+	WCHAR *wpath, *ptr, *end;
+	DWORD error;
+	bool done;
+
+
+	wpath = path_to_windows(path);
+	if (wpath == NULL)
+		return -1;
+
+	ptr = skip_prefix(wpath);
+	if (ptr == NULL) {
+		fprintf(stderr, "Illegal or unsupported path: %s\n", path);
+		goto fail;
+	}
+
+	while (*ptr != '\0') {
+		if (*ptr == '\\') {
+			++ptr;
+			continue;
+		}
+
+		for (end = ptr; *end != '\0' && *end != '\\'; ++end)
+			++end;
+
+		if (*end == '\\') {
+			done = false;
+			*end = '\0';
+		} else {
+			done = true;
+		}
+
+		if (!CreateDirectoryW(wpath, NULL)) {
+			error = GetLastError();
+
+			if (error != ERROR_ALREADY_EXISTS) {
+				fprintf(stderr, "Creating %s: %ld\n",
+					path, error);
+				goto fail;
+			}
+		}
+
+		if (!done)
+			*end = '\\';
+
+		ptr = done ? end : (end + 1);
+	}
+
+	free(wpath);
+	return 0;
+fail:
+	free(wpath);
+	return -1;
+}
+#else
+int mkdir_p(const char *path)
+{
+	size_t i, len;
+	char *buffer;
+
+	while (path[0] == '/' && path[1] == '/')
+		++path;
+
+	if (*path == '\0' || (path[0] == '/' && path[1] == '\0'))
+		return 0;
+
+	len = strlen(path) + 1;
+	buffer = alloca(len);
+
+	for (i = 0; i < len; ++i) {
+		if (i > 0 && (path[i] == '/' || path[i] == '\0')) {
+			buffer[i] = '\0';
+
+			if (mkdir(buffer, 0755) != 0) {
+				if (errno != EEXIST) {
+					fprintf(stderr, "mkdir %s: %s\n",
+						buffer, strerror(errno));
+					return -1;
+				}
+			}
+		}
+
+		buffer[i] = path[i];
+	}
+
+	return 0;
+}
+#endif
diff --git a/lib/util/src/rbtree.c b/lib/util/src/rbtree.c
new file mode 100644
index 0000000..8b43e43
--- /dev/null
+++ b/lib/util/src/rbtree.c
@@ -0,0 +1,267 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * rbtree.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include "sqfs/error.h"
+#include "util/rbtree.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#define IS_RED(n) ((n) && (n)->is_red)
+
+#ifdef NO_CUSTOM_ALLOC
+static void destroy_nodes_dfs(rbtree_node_t *n)
+{
+	rbtree_node_t *l, *r;
+
+	if (n != NULL) {
+		l = n->left;
+		r = n->right;
+		free(n);
+		destroy_nodes_dfs(l);
+		destroy_nodes_dfs(r);
+	}
+}
+#else
+static void destroy_nodes_dfs(rbtree_node_t *n)
+{
+	(void)n;
+}
+#endif
+
+static void flip_colors(rbtree_node_t *n)
+{
+	n->is_red = !n->is_red;
+	n->left->is_red = !n->left->is_red;
+	n->right->is_red = !n->right->is_red;
+}
+
+static rbtree_node_t *rotate_right(rbtree_node_t *n)
+{
+	rbtree_node_t *x;
+
+	x = n->left;
+	n->left = x->right;
+	x->right = n;
+
+	x->is_red = x->right->is_red;
+	x->right->is_red = 1;
+	return x;
+}
+
+static rbtree_node_t *rotate_left(rbtree_node_t *n)
+{
+	rbtree_node_t *x;
+
+	x = n->right;
+	n->right = x->left;
+	x->left = n;
+
+	x->is_red = x->left->is_red;
+	x->left->is_red = 1;
+	return x;
+}
+
+static rbtree_node_t *subtree_balance(rbtree_node_t *n)
+{
+	if (IS_RED(n->right) && !IS_RED(n->left))
+		n = rotate_left(n);
+
+	if (IS_RED(n->left) && IS_RED(n->left->left))
+		n = rotate_right(n);
+
+	if (IS_RED(n->left) && IS_RED(n->right))
+		flip_colors(n);
+
+	return n;
+}
+
+static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root,
+				     rbtree_node_t *new)
+{
+	if (root == NULL)
+		return new;
+
+	if (tree->key_compare(tree->key_context, new->data, root->data) < 0) {
+		root->left = subtree_insert(tree, root->left, new);
+	} else {
+		root->right = subtree_insert(tree, root->right, new);
+	}
+
+	return subtree_balance(root);
+}
+
+static rbtree_node_t *mknode(rbtree_t *t, const void *key, const void *value)
+{
+	rbtree_node_t *node;
+
+#ifdef NO_CUSTOM_ALLOC
+	node = calloc(1, sizeof(*node) + t->key_size_padded + t->value_size);
+#else
+	node = mem_pool_allocate(t->pool);
+#endif
+
+	if (node == NULL)
+		return NULL;
+
+	node->value_offset = t->key_size_padded;
+	node->is_red = 1;
+
+	memcpy(node->data, key, t->key_size);
+	memcpy(node->data + t->key_size_padded, value, t->value_size);
+	return node;
+}
+
+static rbtree_node_t *copy_node(rbtree_t *nt, const rbtree_t *t,
+				const rbtree_node_t *n)
+{
+	rbtree_node_t *out;
+
+#ifdef NO_CUSTOM_ALLOC
+	out = calloc(1, sizeof(*out) + t->key_size_padded + t->value_size);
+#else
+	out = mem_pool_allocate(nt->pool);
+#endif
+
+	if (out == NULL)
+		return NULL;
+
+	memcpy(out, n, sizeof(*n) + t->key_size_padded + t->value_size);
+	out->left = NULL;
+	out->right = NULL;
+
+	if (n->left != NULL) {
+		out->left = copy_node(nt, t, n->left);
+
+		if (out->left == NULL) {
+			destroy_nodes_dfs(out);
+			return NULL;
+		}
+	}
+
+	if (n->right != NULL) {
+		out->right = copy_node(nt, t, n->right);
+
+		if (out->right == NULL) {
+			destroy_nodes_dfs(out);
+			return NULL;
+		}
+	}
+
+	return out;
+}
+
+int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize,
+		int(*key_compare)(const void *, const void *, const void *))
+{
+	size_t diff, size;
+
+	memset(tree, 0, sizeof(*tree));
+	tree->key_compare = key_compare;
+	tree->key_size = keysize;
+	tree->key_size_padded = keysize;
+	tree->value_size = valuesize;
+
+	/* make sure the value always has pointer alignment */
+	diff = keysize % sizeof(void *);
+
+	if (diff != 0) {
+		diff = sizeof(void *) - diff;
+
+		if (SZ_ADD_OV(tree->key_size_padded, diff,
+			      &tree->key_size_padded)) {
+			return SQFS_ERROR_OVERFLOW;
+		}
+	}
+
+	/* make sure the node can store the offset */
+	if (sizeof(size_t) > sizeof(sqfs_u32)) {
+		if (tree->key_size_padded > 0x0FFFFFFFFUL)
+			return SQFS_ERROR_OVERFLOW;
+	}
+
+	/* make sure the nodes fit in memory */
+	size = sizeof(rbtree_node_t);
+
+	if (SZ_ADD_OV(size, tree->key_size_padded, &size))
+		return SQFS_ERROR_OVERFLOW;
+
+	if (SZ_ADD_OV(size, tree->value_size, &size))
+		return SQFS_ERROR_OVERFLOW;
+
+#ifndef NO_CUSTOM_ALLOC
+	/* initialize the underlying pool allocator */
+	tree->pool = mem_pool_create(size);
+	if (tree->pool == NULL)
+		return SQFS_ERROR_ALLOC;
+#endif
+	return 0;
+}
+
+int rbtree_copy(const rbtree_t *tree, rbtree_t *out)
+{
+	memcpy(out, tree, sizeof(*out));
+	out->root = NULL;
+
+#ifndef NO_CUSTOM_ALLOC
+	out->pool = mem_pool_create(sizeof(rbtree_node_t) +
+				    tree->key_size_padded +
+				    tree->value_size);
+	if (out->pool == NULL)
+		return SQFS_ERROR_ALLOC;
+#endif
+
+	if (tree->root != NULL) {
+		out->root = copy_node(out, tree, tree->root);
+
+		if (out->root == NULL) {
+			memset(out, 0, sizeof(*out));
+			return SQFS_ERROR_ALLOC;
+		}
+	}
+
+	return 0;
+}
+
+void rbtree_cleanup(rbtree_t *tree)
+{
+#ifdef NO_CUSTOM_ALLOC
+	destroy_nodes_dfs(tree->root);
+#else
+	mem_pool_destroy(tree->pool);
+#endif
+	memset(tree, 0, sizeof(*tree));
+}
+
+int rbtree_insert(rbtree_t *tree, const void *key, const void *value)
+{
+	rbtree_node_t *node = mknode(tree, key, value);
+
+	if (node == NULL)
+		return SQFS_ERROR_ALLOC;
+
+	tree->root = subtree_insert(tree, tree->root, node);
+	tree->root->is_red = 0;
+	return 0;
+}
+
+rbtree_node_t *rbtree_lookup(const rbtree_t *tree, const void *key)
+{
+	rbtree_node_t *node = tree->root;
+	int ret;
+
+	while (node != NULL) {
+		ret = tree->key_compare(tree->key_context, key, node->data);
+		if (ret == 0)
+			break;
+
+		node = ret < 0 ? node->left : node->right;
+	}
+
+	return node;
+}
diff --git a/lib/util/src/source_date_epoch.c b/lib/util/src/source_date_epoch.c
new file mode 100644
index 0000000..26e5530
--- /dev/null
+++ b/lib/util/src/source_date_epoch.c
@@ -0,0 +1,44 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * source_date_epoch.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/util.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <ctype.h>
+
+sqfs_u32 get_source_date_epoch(void)
+{
+	const char *str, *ptr;
+	sqfs_u32 x, tval = 0;
+
+	str = getenv("SOURCE_DATE_EPOCH");
+
+	if (str == NULL || *str == '\0')
+		return 0;
+
+	for (ptr = str; *ptr != '\0'; ++ptr) {
+		if (!isdigit(*ptr))
+			goto fail_nan;
+
+		x = (*ptr) - '0';
+
+		if (tval > (UINT32_MAX - x) / 10)
+			goto fail_ov;
+
+		tval = tval * 10 + x;
+	}
+
+	return tval;
+fail_ov:
+	fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s does not fit into "
+		"32 bit integer\n", str);
+	return 0;
+fail_nan:
+	fprintf(stderr, "WARNING: SOURCE_DATE_EPOCH=%s is not a positive "
+		"number\n", str);
+	return 0;
+}
diff --git a/lib/util/src/str_table.c b/lib/util/src/str_table.c
new file mode 100644
index 0000000..2d3e354
--- /dev/null
+++ b/lib/util/src/str_table.c
@@ -0,0 +1,183 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * str_table.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "sqfs/error.h"
+#include "util/str_table.h"
+#include "util/util.h"
+
+/* R5 hash function (borrowed from reiserfs) */
+static sqfs_u32 strhash(const char *s)
+{
+	const signed char *str = (const signed char *)s;
+	sqfs_u32 a = 0;
+
+	while (*str != '\0') {
+		a += *str << 4;
+		a += *str >> 4;
+		a *= 11;
+		str++;
+	}
+
+	return a;
+}
+
+static bool key_equals_function(void *user, const void *a, const void *b)
+{
+	(void)user;
+	return strcmp(a, b) == 0;
+}
+
+int str_table_init(str_table_t *table)
+{
+	memset(table, 0, sizeof(*table));
+
+	if (array_init(&table->bucket_ptrs, sizeof(str_bucket_t *), 0))
+		goto fail_arr;
+
+	table->ht = hash_table_create(NULL, key_equals_function);
+	if (table->ht == NULL)
+		goto fail_ht;
+
+	return 0;
+fail_ht:
+	array_cleanup(&table->bucket_ptrs);
+fail_arr:
+	memset(table, 0, sizeof(*table));
+	return SQFS_ERROR_ALLOC;
+}
+
+int str_table_copy(str_table_t *dst, const str_table_t *src)
+{
+	str_bucket_t *bucket, **array;
+	int ret;
+
+	ret = array_init_copy(&dst->bucket_ptrs, &src->bucket_ptrs);
+	if (ret != 0)
+		return ret;
+
+	dst->ht = hash_table_clone(src->ht);
+	if (dst->ht == NULL) {
+		array_cleanup(&dst->bucket_ptrs);
+		return SQFS_ERROR_ALLOC;
+	}
+
+	array = (str_bucket_t **)dst->bucket_ptrs.data;
+
+	hash_table_foreach(dst->ht, ent) {
+		bucket = alloc_flex(sizeof(*bucket), 1, strlen(ent->key) + 1);
+		if (bucket == NULL) {
+			str_table_cleanup(dst);
+			return SQFS_ERROR_ALLOC;
+		}
+
+		memcpy(bucket, ent->data,
+		       sizeof(*bucket) + strlen(ent->key) + 1);
+
+		ent->data = bucket;
+		ent->key = bucket->string;
+
+		array[bucket->index] = bucket;
+	}
+
+	return 0;
+}
+
+void str_table_cleanup(str_table_t *table)
+{
+	hash_table_foreach(table->ht, ent) {
+		free(ent->data);
+		ent->data = NULL;
+		ent->key = NULL;
+	}
+
+	hash_table_destroy(table->ht, NULL);
+	array_cleanup(&table->bucket_ptrs);
+	memset(table, 0, sizeof(*table));
+}
+
+int str_table_get_index(str_table_t *table, const char *str, size_t *idx)
+{
+	struct hash_entry *ent;
+	str_bucket_t *new;
+	sqfs_u32 hash;
+
+	hash = strhash(str);
+	ent = hash_table_search_pre_hashed(table->ht, hash, str);
+
+	if (ent != NULL) {
+		*idx = ((str_bucket_t *)ent->data)->index;
+		return 0;
+	}
+
+	new = alloc_flex(sizeof(*new), 1, strlen(str) + 1);
+	if (new == NULL)
+		return SQFS_ERROR_ALLOC;
+
+	new->index = table->next_index;
+	strcpy(new->string, str);
+
+	ent = hash_table_insert_pre_hashed(table->ht, hash, str, new);
+	if (ent == NULL) {
+		free(new);
+		return SQFS_ERROR_ALLOC;
+	}
+
+	ent->key = new->string;
+
+	if (array_append(&table->bucket_ptrs, &new) != 0) {
+		free(new);
+		ent->key = NULL;
+		ent->data = NULL;
+		return SQFS_ERROR_ALLOC;
+	}
+
+	*idx = table->next_index++;
+	return 0;
+}
+
+static str_bucket_t *bucket_by_index(const str_table_t *table, size_t index)
+{
+	if (index >= table->bucket_ptrs.used)
+		return NULL;
+
+	return ((str_bucket_t **)table->bucket_ptrs.data)[index];
+}
+
+const char *str_table_get_string(const str_table_t *table, size_t index)
+{
+	str_bucket_t *bucket = bucket_by_index(table, index);
+
+	return bucket == NULL ? NULL : bucket->string;
+}
+
+void str_table_add_ref(str_table_t *table, size_t index)
+{
+	str_bucket_t *bucket = bucket_by_index(table, index);
+
+	if (bucket != NULL && bucket->refcount < ~((size_t)0))
+		bucket->refcount += 1;
+}
+
+void str_table_del_ref(str_table_t *table, size_t index)
+{
+	str_bucket_t *bucket = bucket_by_index(table, index);
+
+	if (bucket != NULL && bucket->refcount > 0)
+		bucket->refcount -= 1;
+}
+
+size_t str_table_get_ref_count(const str_table_t *table, size_t index)
+{
+	str_bucket_t *bucket = bucket_by_index(table, index);
+
+	return bucket != NULL ? bucket->refcount : 0;
+}
diff --git a/lib/util/src/threadpool.c b/lib/util/src/threadpool.c
new file mode 100644
index 0000000..c7357cd
--- /dev/null
+++ b/lib/util/src/threadpool.c
@@ -0,0 +1,392 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * threadpool.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/threadpool.h"
+#include "util/util.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+#include "util/w32threadwrap.h"
+
+#define THREAD_FUN(funname, argname) DWORD WINAPI funname(LPVOID argname)
+#define THREAD_EXIT_SUCCESS (0)
+#else
+#include <pthread.h>
+#include <signal.h>
+
+#define THREAD_FUN(funname, argname) void *funname(void *argname)
+#define THREAD_EXIT_SUCCESS NULL
+#endif
+
+typedef struct thread_pool_impl_t thread_pool_impl_t;
+
+typedef struct work_item_t {
+	struct work_item_t *next;
+	size_t ticket_number;
+
+	void *data;
+} work_item_t;
+
+typedef struct {
+	pthread_t thread;
+	thread_pool_impl_t *pool;
+
+	thread_pool_worker_t fun;
+	void *user;
+} worker_t;
+
+struct thread_pool_impl_t {
+	thread_pool_t base;
+
+	pthread_mutex_t mtx;
+	pthread_cond_t queue_cond;
+	pthread_cond_t done_cond;
+
+	size_t next_ticket;
+	size_t next_dequeue_ticket;
+
+	size_t item_count;
+
+	work_item_t *queue;
+	work_item_t *queue_last;
+
+	work_item_t *done;
+
+	work_item_t *safe_done;
+	work_item_t *safe_done_last;
+
+	work_item_t *recycle;
+
+	int status;
+
+	size_t num_workers;
+	worker_t workers[];
+};
+
+/*****************************************************************************/
+
+static void store_completed(thread_pool_impl_t *pool, work_item_t *done,
+			    int status)
+{
+	work_item_t *it = pool->done, *prev = NULL;
+
+	while (it != NULL) {
+		if (it->ticket_number >= done->ticket_number)
+			break;
+
+		prev = it;
+		it = it->next;
+	}
+
+	if (prev == NULL) {
+		done->next = pool->done;
+		pool->done = done;
+	} else {
+		done->next = prev->next;
+		prev->next = done;
+	}
+
+	if (status != 0 && pool->status == 0)
+		pool->status = status;
+
+	pthread_cond_broadcast(&pool->done_cond);
+}
+
+static work_item_t *get_next_work_item(thread_pool_impl_t *pool)
+{
+	work_item_t *item = NULL;
+
+	while (pool->queue == NULL && pool->status == 0)
+		pthread_cond_wait(&pool->queue_cond, &pool->mtx);
+
+	if (pool->status == 0) {
+		item = pool->queue;
+		pool->queue = item->next;
+		item->next = NULL;
+
+		if (pool->queue == NULL)
+			pool->queue_last = NULL;
+	}
+
+	return item;
+}
+
+static THREAD_FUN(worker_proc, arg)
+{
+	work_item_t *item = NULL;
+	worker_t *worker = arg;
+	int status = 0;
+
+	for (;;) {
+		pthread_mutex_lock(&worker->pool->mtx);
+		if (item != NULL)
+			store_completed(worker->pool, item, status);
+
+		item = get_next_work_item(worker->pool);
+		pthread_mutex_unlock(&worker->pool->mtx);
+
+		if (item == NULL)
+			break;
+
+		status = worker->fun(worker->user, item->data);
+	}
+
+	return THREAD_EXIT_SUCCESS;
+}
+
+/*****************************************************************************/
+
+static work_item_t *try_dequeue_done(thread_pool_impl_t *pool)
+{
+	work_item_t *out;
+
+	if (pool->done == NULL)
+		return NULL;
+
+	if (pool->done->ticket_number != pool->next_dequeue_ticket)
+		return NULL;
+
+	out = pool->done;
+	pool->done = out->next;
+	out->next = NULL;
+	pool->next_dequeue_ticket += 1;
+	return out;
+}
+
+static void free_item_list(work_item_t *list)
+{
+	while (list != NULL) {
+		work_item_t *item = list;
+		list = list->next;
+		free(item);
+	}
+}
+
+static void destroy(thread_pool_t *interface)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+	size_t i;
+
+	pthread_mutex_lock(&pool->mtx);
+	pool->status = -1;
+	pthread_cond_broadcast(&pool->queue_cond);
+	pthread_mutex_unlock(&pool->mtx);
+
+	for (i = 0; i < pool->num_workers; ++i)
+		pthread_join(pool->workers[i].thread, NULL);
+
+	pthread_cond_destroy(&pool->done_cond);
+	pthread_cond_destroy(&pool->queue_cond);
+	pthread_mutex_destroy(&pool->mtx);
+
+	free_item_list(pool->queue);
+	free_item_list(pool->done);
+	free_item_list(pool->recycle);
+	free_item_list(pool->safe_done);
+	free(pool);
+}
+
+static size_t get_worker_count(thread_pool_t *interface)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+
+	return pool->num_workers;
+}
+
+static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+
+	if (idx >= pool->num_workers)
+		return;
+
+	pthread_mutex_lock(&pool->mtx);
+	pool->workers[idx].user = ptr;
+	pthread_mutex_unlock(&pool->mtx);
+}
+
+static int submit(thread_pool_t *interface, void *ptr)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+	work_item_t *item = NULL;
+	int status;
+
+	if (pool->recycle != NULL) {
+		item = pool->recycle;
+		pool->recycle = item->next;
+		item->next = NULL;
+	}
+
+	if (item == NULL) {
+		item = calloc(1, sizeof(*item));
+		if (item == NULL)
+			return -1;
+	}
+
+	pthread_mutex_lock(&pool->mtx);
+	status = pool->status;
+
+	if (status == 0) {
+		item->data = ptr;
+		item->ticket_number = pool->next_ticket++;
+
+		if (pool->queue_last == NULL) {
+			pool->queue = item;
+		} else {
+			pool->queue_last->next = item;
+		}
+
+		pool->queue_last = item;
+		pool->item_count += 1;
+	}
+
+	for (;;) {
+		work_item_t *done = try_dequeue_done(pool);
+		if (done == NULL)
+			break;
+
+		if (pool->safe_done_last == NULL) {
+			pool->safe_done = done;
+		} else {
+			pool->safe_done_last->next = done;
+		}
+
+		pool->safe_done_last = done;
+	}
+
+	pthread_cond_broadcast(&pool->queue_cond);
+	pthread_mutex_unlock(&pool->mtx);
+
+	if (status != 0) {
+		memset(item, 0, sizeof(*item));
+		item->next = pool->recycle;
+		pool->recycle = item;
+	}
+
+	return status;
+}
+
+static void *dequeue(thread_pool_t *interface)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+	work_item_t *out = NULL;
+	void *ptr = NULL;
+
+	if (pool->item_count == 0)
+		return NULL;
+
+	if (pool->safe_done != NULL) {
+		out = pool->safe_done;
+
+		pool->safe_done = pool->safe_done->next;
+		if (pool->safe_done == NULL)
+			pool->safe_done_last = NULL;
+	} else {
+		pthread_mutex_lock(&pool->mtx);
+		for (;;) {
+			out = try_dequeue_done(pool);
+			if (out != NULL)
+				break;
+
+			pthread_cond_wait(&pool->done_cond, &pool->mtx);
+		}
+		pthread_mutex_unlock(&pool->mtx);
+	}
+
+	ptr = out->data;
+
+	out->ticket_number = 0;
+	out->data = NULL;
+	out->next = pool->recycle;
+	pool->recycle = out;
+
+	pool->item_count -= 1;
+	return ptr;
+}
+
+static int get_status(thread_pool_t *interface)
+{
+	thread_pool_impl_t *pool = (thread_pool_impl_t *)interface;
+	int status;
+
+	pthread_mutex_lock(&pool->mtx);
+	status = pool->status;
+	pthread_mutex_unlock(&pool->mtx);
+
+	return status;
+}
+
+thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker)
+{
+	thread_pool_impl_t *pool;
+	thread_pool_t *interface;
+	sigset_t set, oldset;
+	size_t i, j;
+	int ret;
+
+	if (num_jobs < 1)
+		num_jobs = 1;
+
+	pool = alloc_flex(sizeof(*pool), sizeof(pool->workers[0]), num_jobs);
+	if (pool == NULL)
+		return NULL;
+
+	if (pthread_mutex_init(&pool->mtx, NULL) != 0)
+		goto fail_free;
+
+	if (pthread_cond_init(&pool->queue_cond, NULL) != 0)
+		goto fail_mtx;
+
+	if (pthread_cond_init(&pool->done_cond, NULL) != 0)
+		goto fail_qcond;
+
+	sigfillset(&set);
+	pthread_sigmask(SIG_SETMASK, &set, &oldset);
+
+	pool->num_workers = num_jobs;
+
+	for (i = 0; i < num_jobs; ++i) {
+		pool->workers[i].fun = worker;
+		pool->workers[i].pool = pool;
+
+		ret = pthread_create(&pool->workers[i].thread, NULL,
+				     worker_proc, pool->workers + i);
+
+		if (ret != 0)
+			goto fail;
+	}
+
+	pthread_sigmask(SIG_SETMASK, &oldset, NULL);
+
+	interface = (thread_pool_t *)pool;
+	interface->destroy = destroy;
+	interface->get_worker_count = get_worker_count;
+	interface->set_worker_ptr = set_worker_ptr;
+	interface->submit = submit;
+	interface->dequeue = dequeue;
+	interface->get_status = get_status;
+	return interface;
+fail:
+	pthread_mutex_lock(&pool->mtx);
+	pool->status = -1;
+	pthread_cond_broadcast(&pool->queue_cond);
+	pthread_mutex_unlock(&pool->mtx);
+
+	for (j = 0; j < i; ++j)
+		pthread_join(pool->workers[j].thread, NULL);
+
+	pthread_sigmask(SIG_SETMASK, &oldset, NULL);
+	pthread_cond_destroy(&pool->done_cond);
+fail_qcond:
+	pthread_cond_destroy(&pool->queue_cond);
+fail_mtx:
+	pthread_mutex_destroy(&pool->mtx);
+fail_free:
+	free(pool);
+	return NULL;
+}
diff --git a/lib/util/src/threadpool_serial.c b/lib/util/src/threadpool_serial.c
new file mode 100644
index 0000000..fb24ee8
--- /dev/null
+++ b/lib/util/src/threadpool_serial.c
@@ -0,0 +1,162 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * threadpool_serial.c
+ *
+ * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "util/threadpool.h"
+#include "util/util.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct work_item_t {
+	struct work_item_t *next;
+	void *data;
+} work_item_t;
+
+typedef struct {
+	thread_pool_t base;
+
+	work_item_t *queue;
+	work_item_t *queue_last;
+
+	work_item_t *recycle;
+
+	thread_pool_worker_t fun;
+	void *user;
+	int status;
+} serial_impl_t;
+
+static void destroy(thread_pool_t *interface)
+{
+	serial_impl_t *pool = (serial_impl_t *)interface;
+
+	while (pool->queue != NULL) {
+		work_item_t *item = pool->queue;
+		pool->queue = item->next;
+		free(item);
+	}
+
+	while (pool->recycle != NULL) {
+		work_item_t *item = pool->recycle;
+		pool->recycle = item->next;
+		free(item);
+	}
+
+	free(pool);
+}
+
+static size_t get_worker_count(thread_pool_t *pool)
+{
+	(void)pool;
+	return 1;
+}
+
+static void set_worker_ptr(thread_pool_t *interface, size_t idx, void *ptr)
+{
+	serial_impl_t *pool = (serial_impl_t *)interface;
+
+	if (idx >= 1)
+		return;
+
+	pool->user = ptr;
+}
+
+static int submit(thread_pool_t *interface, void *ptr)
+{
+	serial_impl_t *pool = (serial_impl_t *)interface;
+	work_item_t *item = NULL;
+
+	if (pool->status != 0)
+		return pool->status;
+
+	if (pool->recycle != NULL) {
+		item = pool->recycle;
+		pool->recycle = item->next;
+		item->next = NULL;
+	}
+
+	if (item == NULL) {
+		item = calloc(1, sizeof(*item));
+		if (item == NULL)
+			return -1;
+	}
+
+	item->data = ptr;
+
+	if (pool->queue_last == NULL) {
+		pool->queue = item;
+	} else {
+		pool->queue_last->next = item;
+	}
+
+	pool->queue_last = item;
+	return 0;
+}
+
+static void *dequeue(thread_pool_t *interface)
+{
+	serial_impl_t *pool = (serial_impl_t *)interface;
+	work_item_t *item;
+	void *ptr;
+	int ret;
+
+	if (pool->queue == NULL)
+		return NULL;
+
+	item = pool->queue;
+	pool->queue = item->next;
+
+	if (pool->queue == NULL)
+		pool->queue_last = NULL;
+
+	ptr = item->data;
+
+	memset(item, 0, sizeof(*item));
+	item->next = pool->recycle;
+	pool->recycle = item;
+
+	ret = pool->fun(pool->user, ptr);
+
+	if (ret != 0 && pool->status == 0)
+		pool->status = ret;
+
+	return ptr;
+}
+
+static int get_status(thread_pool_t *interface)
+{
+	serial_impl_t *pool = (serial_impl_t *)interface;
+
+	return pool->status;
+}
+
+thread_pool_t *thread_pool_create_serial(thread_pool_worker_t worker)
+{
+	serial_impl_t *pool = calloc(1, sizeof(*pool));
+	thread_pool_t *interface = (thread_pool_t *)pool;
+
+	if (pool == NULL)
+		return NULL;
+
+	pool->fun = worker;
+
+	interface = (thread_pool_t *)pool;
+	interface->destroy = destroy;
+	interface->get_worker_count = get_worker_count;
+	interface->set_worker_ptr = set_worker_ptr;
+	interface->submit = submit;
+	interface->dequeue = dequeue;
+	interface->get_status = get_status;
+	return interface;
+
+}
+
+#ifdef NO_THREAD_IMPL
+thread_pool_t *thread_pool_create(size_t num_jobs, thread_pool_worker_t worker)
+{
+	(void)num_jobs;
+	return thread_pool_create_serial(worker);
+}
+#endif
diff --git a/lib/util/src/xxhash.c b/lib/util/src/xxhash.c
new file mode 100644
index 0000000..60467fb
--- /dev/null
+++ b/lib/util/src/xxhash.c
@@ -0,0 +1,112 @@
+/*
+ * xxHash - Extremely Fast Hash algorithm
+ * Copyright (C) 2012-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ *     copyright notice, this list of conditions and the following disclaimer
+ *     in the documentation and/or other materials provided with the
+ *     distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * ----------------------------------------------------------------------------
+ * This code has been lifted from Linux (the OS kernel) and adapted for use in
+ * libsquashfs. For the original, unmodified and complete source, see below.
+ *
+ * You can contact the author at:
+ * - xxHash homepage: http://cyan4973.github.io/xxHash/
+ * - xxHash source repository: https://github.com/Cyan4973/xxHash
+ */
+#include "config.h"
+#include "util/util.h"
+
+#include <string.h>
+
+#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
+
+static const sqfs_u32 PRIME32_1 = 2654435761U;
+static const sqfs_u32 PRIME32_2 = 2246822519U;
+static const sqfs_u32 PRIME32_3 = 3266489917U;
+static const sqfs_u32 PRIME32_4 =  668265263U;
+static const sqfs_u32 PRIME32_5 =  374761393U;
+
+static sqfs_u32 xxh32_round(sqfs_u32 seed, sqfs_u32 input)
+{
+	seed += input * PRIME32_2;
+	seed = xxh_rotl32(seed, 13);
+	seed *= PRIME32_1;
+	return seed;
+}
+
+static sqfs_u32 XXH_readLE32(const sqfs_u8 *ptr)
+{
+	sqfs_u32 value;
+	memcpy(&value, ptr, sizeof(value));
+	return le32toh(value);
+}
+
+sqfs_u32 xxh32(const void *input, const size_t len)
+{
+	const sqfs_u8 *p = (const sqfs_u8 *)input;
+	const sqfs_u8 *b_end = p + len;
+	sqfs_u32 h32;
+
+	if (len >= 16) {
+		const sqfs_u8 *const limit = b_end - 16;
+		sqfs_u32 v1 = PRIME32_1 + PRIME32_2;
+		sqfs_u32 v2 = PRIME32_2;
+		sqfs_u32 v3 = 0;
+		sqfs_u32 v4 = PRIME32_1;
+
+		do {
+			v1 = xxh32_round(v1, XXH_readLE32(p     ));
+			v2 = xxh32_round(v2, XXH_readLE32(p +  4));
+			v3 = xxh32_round(v3, XXH_readLE32(p +  8));
+			v4 = xxh32_round(v4, XXH_readLE32(p + 12));
+			p += 16;
+		} while (p <= limit);
+
+		h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
+			xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
+	} else {
+		h32 = PRIME32_5;
+	}
+
+	h32 += (sqfs_u32)len;
+
+	while (p + 4 <= b_end) {
+		h32 += XXH_readLE32(p) * PRIME32_3;
+		h32 = xxh_rotl32(h32, 17) * PRIME32_4;
+		p += 4;
+	}
+
+	while (p < b_end) {
+		h32 += (*p) * PRIME32_5;
+		h32 = xxh_rotl32(h32, 11) * PRIME32_1;
+		p++;
+	}
+
+	h32 ^= h32 >> 15;
+	h32 *= PRIME32_2;
+	h32 ^= h32 >> 13;
+	h32 *= PRIME32_3;
+	h32 ^= h32 >> 16;
+	return h32;
+}