3 files changed, 215 insertions, 0 deletions
diff --git a/include/util/compat.h b/include/util/compat.h
new file mode 100644
index 0000000..74d0b6f
--- /dev/null
+++ b/include/util/compat.h
@@ -0,0 +1,95 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * util.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef COMPAT_H
+#define COMPAT_H
+
+#if defined(__APPLE__)
+#include <libkern/OSByteOrder.h>
+
+#define htole16(x) OSSwapHostToLittleInt16(x)
+#define htole32(x) OSSwapHostToLittleInt32(x)
+#define htole64(x) OSSwapHostToLittleInt64(x)
+
+#define le32toh(x) OSSwapLittleToHostInt32(x)
+#define le16toh(x) OSSwapLittleToHostInt16(x)
+#define le64toh(x) OSSwapLittleToHostInt64(x)
+#elif defined(__OpenBSD__)
+#include <sys/endian.h>
+#elif defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__)
+#include <sys/endian.h>
+
+#define le16toh(x) letoh16(x)
+#define le32toh(x) letoh32(x)
+#define le64toh(x) letoh64(x)
+#elif defined(_WIN32) || defined(__WINDOWS__)
+#define htole16(x) (x)
+#define htole32(x) (x)
+#define htole64(x) (x)
+
+#define le16toh(x) (x)
+#define le32toh(x) (x)
+#define le64toh(x) (x)
+#else
+#include <endian.h>
+#endif
+
+#if defined(_WIN32) || defined(__WINDOWS__)
+#define S_IFSOCK SQFS_INODE_MODE_SOCK
+#define S_IFLNK SQFS_INODE_MODE_LNK
+#define S_IFREG SQFS_INODE_MODE_REG
+#define S_IFBLK SQFS_INODE_MODE_BLK
+#define S_IFDIR SQFS_INODE_MODE_DIR
+#define S_IFCHR SQFS_INODE_MODE_CHR
+#define S_IFIFO SQFS_INODE_MODE_FIFO
+#define S_IFMT SQFS_INODE_MODE_MASK
+
+#define S_ISREG(m) (((m) & S_IFMT) == S_IFREG)
+#define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR)
+#define S_ISCHR(m) (((m) & S_IFMT) == S_IFCHR)
+#define S_ISBLK(m) (((m) & S_IFMT) == S_IFBLK)
+#define S_ISFIFO(m) (((m) & S_IFMT) == S_IFIFO)
+#define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK)
+#define S_ISSOCK(m) (((m) & S_IFMT) == S_IFSOCK)
+
+#define S_ISUID SQFS_INODE_SET_UID
+#define S_ISGID SQFS_INODE_SET_GID
+#define S_ISVTX SQFS_INODE_STICKY
+
+#define S_IRWXU SQFS_INODE_OWNER_MASK
+#define S_IRUSR SQFS_INODE_OWNER_R
+#define S_IWUSR SQFS_INODE_OWNER_W
+#define S_IXUSR SQFS_INODE_OWNER_X
+
+#define S_IRWXG SQFS_INODE_GROUP_MASK
+#define S_IRGRP SQFS_INODE_GROUP_R
+#define S_IWGRP SQFS_INODE_GROUP_W
+#define S_IXGRP SQFS_INODE_GROUP_X
+
+#define S_IRWXO SQFS_INODE_OTHERS_MASK
+#define S_IROTH SQFS_INODE_OTHERS_R
+#define S_IWOTH SQFS_INODE_OTHERS_W
+#define S_IXOTH SQFS_INODE_OTHERS_X
+
+/* lifted from musl libc */
+#define major(x) \
+	((unsigned)( (((x)>>31>>1) & 0xfffff000) | (((x)>>8) & 0x00000fff) ))
+
+#define minor(x)							\
+	((unsigned)( (((x)>>12) & 0xffffff00) | ((x) & 0x000000ff) ))
+
+#define makedev(x,y) ( \
+        (((x)&0xfffff000ULL) << 32) | \
+	(((x)&0x00000fffULL) << 8) | \
+        (((y)&0xffffff00ULL) << 12) | \
+	(((y)&0x000000ffULL)) )
+#else
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/sysmacros.h>
+#endif
+
+#endif /* COMPAT_H */
diff --git a/include/util/str_table.h b/include/util/str_table.h
new file mode 100644
index 0000000..60be1d1
--- /dev/null
+++ b/include/util/str_table.h
@@ -0,0 +1,53 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * str_table.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef STR_TABLE_H
+#define STR_TABLE_H
+
+#include "sqfs/predef.h"
+
+typedef struct str_bucket_t {
+	struct str_bucket_t *next;
+	char *str;
+	size_t index;
+	size_t refcount;
+} str_bucket_t;
+
+/* Stores strings in a hash table and assigns an incremental, unique ID to
+   each string. Subsequent additions return the existing ID. The ID can be
+   used for (hopefully) constant time lookup of the original string. */
+typedef struct {
+	str_bucket_t **buckets;
+	size_t num_buckets;
+
+	char **strings;
+	size_t num_strings;
+	size_t max_strings;
+} str_table_t;
+
+/* `size` is the number of hash table buckets to use internally. */
+SQFS_INTERNAL int str_table_init(str_table_t *table, size_t size);
+
+SQFS_INTERNAL void str_table_cleanup(str_table_t *table);
+
+/* Resolve a string to an incremental, unique ID. */
+SQFS_INTERNAL
+int str_table_get_index(str_table_t *table, const char *str, size_t *idx);
+
+/* Resolve a unique ID to the string it represents.
+   Returns NULL if the ID is unknown, i.e. out of bounds. */
+SQFS_INTERNAL
+const char *str_table_get_string(str_table_t *table, size_t index);
+
+SQFS_INTERNAL void str_table_reset_ref_count(str_table_t *table);
+
+SQFS_INTERNAL void str_table_add_ref(str_table_t *table, size_t index);
+
+SQFS_INTERNAL void str_table_del_ref(str_table_t *table, size_t index);
+
+SQFS_INTERNAL size_t str_table_get_ref_count(str_table_t *table, size_t index);
+
+#endif /* STR_TABLE_H */
diff --git a/include/util/util.h b/include/util/util.h
new file mode 100644
index 0000000..881b59c
--- /dev/null
+++ b/include/util/util.h
@@ -0,0 +1,67 @@
+/* SPDX-License-Identifier: LGPL-3.0-or-later */
+/*
+ * util.h
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#ifndef UTIL_H
+#define UTIL_H
+
+#include "config.h"
+#include "sqfs/predef.h"
+
+#include <stdint.h>
+#include <stddef.h>
+
+#include "compat.h"
+
+#if defined(__GNUC__) || defined(__clang__)
+#define UI_ADD_OV __builtin_uadd_overflow
+#define UL_ADD_OV __builtin_uaddl_overflow
+#define ULL_ADD_OV __builtin_uaddll_overflow
+
+#define UI_MUL_OV __builtin_umul_overflow
+#define UL_MUL_OV __builtin_umull_overflow
+#define ULL_MUL_OV __builtin_umulll_overflow
+#else
+#error Sorry, I do not know how to trap integer overflows with this compiler
+#endif
+
+#if SIZEOF_SIZE_T <= SIZEOF_INT
+#define SZ_ADD_OV UI_ADD_OV
+#define SZ_MUL_OV UI_MUL_OV
+#elif SIZEOF_SIZE_T == SIZEOF_LONG
+#define SZ_ADD_OV UL_ADD_OV
+#define SZ_MUL_OV UL_MUL_OV
+#elif SIZEOF_SIZE_T == SIZEOF_LONG_LONG
+#define SZ_ADD_OV ULL_ADD_OV
+#define SZ_MUL_OV ULL_MUL_OV
+#else
+#error Cannot determine maximum value of size_t
+#endif
+
+/*
+  Helper for allocating data structures with flexible array members.
+
+  'base_size' is the size of the struct itself, 'item_size' the size of a
+  single array element and 'nmemb' the number of elements.
+
+  Iternally checks for arithmetic overflows when allocating the combined thing.
+ */
+SQFS_INTERNAL
+void *alloc_flex(size_t base_size, size_t item_size, size_t nmemb);
+
+/* Basically the same as calloc, but *ALWAYS* does overflow checking */
+SQFS_INTERNAL
+void *alloc_array(size_t item_size, size_t nmemb);
+
+/*
+  Convert back to forward slashed, remove all preceeding and trailing slashes,
+  collapse all sequences of slashes, remove all path components that are '.'
+  and returns failure state if one of the path components is '..'.
+
+  Returns 0 on success.
+*/
+SQFS_INTERNAL int canonicalize_name(char *filename);
+
+#endif /* UTIL_H */