Move "optimize unpack order" to from fstree to rdsquashfs

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

3 files changed, 122 insertions, 1 deletions

diff --git a/unpack/Makemodule.am b/unpack/Makemodule.am
index b60292d..964cc05 100644
--- a/unpack/Makemodule.am
+++ b/unpack/Makemodule.am
@@ -1,7 +1,7 @@
 rdsquashfs_SOURCES = unpack/rdsquashfs.c unpack/rdsquashfs.h
 rdsquashfs_SOURCES += unpack/list_files.c unpack/options.c
 rdsquashfs_SOURCES += unpack/restore_fstree.c unpack/describe.c
-rdsquashfs_SOURCES += unpack/fill_files.c
+rdsquashfs_SOURCES += unpack/fill_files.c unpack/optimize_unpack_order.c
 rdsquashfs_LDADD = libsqfshelper.a libsquashfs.la libfstree.a libutil.la
 
 bin_PROGRAMS += rdsquashfs
diff --git a/unpack/optimize_unpack_order.c b/unpack/optimize_unpack_order.c
new file mode 100644
index 0000000..a76dd51
--- /dev/null
+++ b/unpack/optimize_unpack_order.c
@@ -0,0 +1,119 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * optimize_unpack_order.c
+ *
+ * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+#include "rdsquashfs.h"
+
+static bool has_fragment(const fstree_t *fs, const file_info_t *file)
+{
+	if (file->size % fs->block_size == 0)
+		return false;
+
+	return file->fragment_offset < fs->block_size &&
+		(file->fragment != 0xFFFFFFFF);
+}
+
+static int compare_files(const fstree_t *fs, const file_info_t *lhs,
+			 const file_info_t *rhs)
+{
+	/* NOOP < everything else */
+	if (lhs->input_file == NULL)
+		return rhs->input_file == NULL ? 0 : -1;
+
+	if (rhs->input_file == NULL)
+		return 1;
+
+	/* Files with fragments come first, ordered by ID.
+	   In case of tie, files without data blocks come first,
+	   and the others are ordered by start block. */
+	if (has_fragment(fs, lhs)) {
+		if (!(has_fragment(fs, rhs)))
+			return -1;
+
+		if (lhs->fragment < rhs->fragment)
+			return -1;
+		if (lhs->fragment > rhs->fragment)
+			return 1;
+
+		if (lhs->size < fs->block_size)
+			return (rhs->size < fs->block_size) ? 0 : -1;
+		if (rhs->size < fs->block_size)
+			return 1;
+		goto order_by_start;
+	}
+
+	if (has_fragment(fs, rhs))
+		return 1;
+
+	/* order the rest by start block */
+order_by_start:
+	return lhs->startblock < rhs->startblock ? -1 :
+		lhs->startblock > rhs->startblock ? 1 : 0;
+}
+
+/* TODO: unify ad-hoc merge sort with the one in fstree_sort */
+static file_info_t *merge(const fstree_t *fs, file_info_t *lhs,
+			  file_info_t *rhs)
+{
+	file_info_t *it;
+	file_info_t *head = NULL;
+	file_info_t **next_ptr = &head;
+
+	while (lhs != NULL && rhs != NULL) {
+		if (compare_files(fs, lhs, rhs) <= 0) {
+			it = lhs;
+			lhs = lhs->next;
+		} else {
+			it = rhs;
+			rhs = rhs->next;
+		}
+
+		*next_ptr = it;
+		next_ptr = &it->next;
+	}
+
+	it = (lhs != NULL ? lhs : rhs);
+	*next_ptr = it;
+	return head;
+}
+
+static file_info_t *list_sort(const fstree_t *fs, file_info_t *head)
+{
+	file_info_t *it, *half, *prev;
+
+	it = half = prev = head;
+	while (it != NULL) {
+		prev = half;
+		half = half->next;
+		it = it->next;
+		if (it != NULL) {
+			it = it->next;
+		}
+	}
+
+	// half refers to the (count/2)'th element ROUNDED UP.
+	// It will be null therefore only in the empty and the
+	// single element list
+	if (half == NULL) {
+		return head;
+	}
+
+	prev->next = NULL;
+
+	return merge(fs, list_sort(fs, head), list_sort(fs, half));
+}
+
+file_info_t *optimize_unpack_order(fstree_t *fs)
+{
+	file_info_t *file_list;
+
+	file_list = list_sort(fs, fs->files);
+	while (file_list != NULL && file_list->input_file == NULL)
+		file_list = file_list->next;
+
+	fs->files = NULL;
+	return file_list;
+}
diff --git a/unpack/rdsquashfs.h b/unpack/rdsquashfs.h
index b5570dd..065f4aa 100644
--- a/unpack/rdsquashfs.h
+++ b/unpack/rdsquashfs.h
@@ -74,4 +74,6 @@ int describe_tree(tree_node_t *root, const char *unpack_root);
 
 void process_command_line(options_t *opt, int argc, char **argv);
 
+file_info_t *optimize_unpack_order(fstree_t *fs);
+
 #endif /* RDSQUASHFS_H */