aboutsummaryrefslogtreecommitdiff
path: root/lib/util/src
diff options
context:
space:
mode:
Diffstat (limited to 'lib/util/src')
-rw-r--r--lib/util/src/alloc.c37
-rw-r--r--lib/util/src/array.c115
-rw-r--r--lib/util/src/base64_decode.c103
-rw-r--r--lib/util/src/canonicalize_name.c60
-rw-r--r--lib/util/src/fast_urem_by_const.h77
-rw-r--r--lib/util/src/file_cmp.c41
-rw-r--r--lib/util/src/filename_sane.c78
-rw-r--r--lib/util/src/hash_table.c417
-rw-r--r--lib/util/src/hex_decode.c34
-rw-r--r--lib/util/src/is_memory_zero.c54
-rw-r--r--lib/util/src/mempool.c216
-rw-r--r--lib/util/src/mkdir_p.c170
-rw-r--r--lib/util/src/rbtree.c267
-rw-r--r--lib/util/src/source_date_epoch.c44
-rw-r--r--lib/util/src/str_table.c183
-rw-r--r--lib/util/src/threadpool.c392
-rw-r--r--lib/util/src/threadpool_serial.c162
-rw-r--r--lib/util/src/xxhash.c112
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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-27 22:55:32 +0000