Read entire asset file tree

2 files changed, 148 insertions, 66 deletions

diff --git a/tools/rom/build.c b/tools/rom/build.c
index 95b35e6f..8b63b3c6 100644
--- a/tools/rom/build.c
+++ b/tools/rom/build.c
@@ -195,22 +195,18 @@ bool GrowFntSubtable(FntContext *pContext, size_t growSize) {
 	return true;
 }
 
-bool WriteFntSubtable(FILE *fpRom, size_t *pAddress, FntContext *pContext) {
+bool WriteFntSubtable(FILE *fpRom, size_t *pAddress, FntTree *tree, FntContext *pContext) {
 	size_t address = *pAddress;
-	FntSubEntry *entries[MAX_DIR_SIZE];
-	size_t numEntries;
 
 	FntContext ctx;
 	memcpy(&ctx, pContext, sizeof(ctx));
 	size_t subtableStart = ctx.subtableSize;
 
-	if (!GetFiles(entries, MAX_DIR_SIZE, &numEntries)) return false;
-	qsort(entries, numEntries, sizeof(FntSubEntry*), CompareFnt);
-
 	// Create initial subtable entries
 	size_t numFiles = 0;
-	for (size_t i = 0; i < numEntries; ++i) {
-		FntSubEntry *entry = entries[i];
+	for (size_t i = 0; i < tree->numChildren; ++i) {
+		FntTree *child = &tree->children[i];
+		FntSubEntry *entry = child->entry;
 		if (!entry->isSubdir) numFiles += 1;
 
 		size_t entrySize = sizeof(*entry) + entry->length + (entry->isSubdir ? 2 : 0);
@@ -226,8 +222,9 @@ bool WriteFntSubtable(FILE *fpRom, size_t *pAddress, FntContext *pContext) {
 	ctx.subtableSize += 1;
 
 	// Recurse child directories
-	for (size_t i = 0; i < numEntries; ++i) {
-		FntSubEntry *entry = entries[i];
+	for (size_t i = 0; i < tree->numChildren; ++i) {
+		FntTree *child = &tree->children[i];
+		FntSubEntry *entry = child->entry;
 		if (!entry->isSubdir) continue;
 		uint16_t subdirId = 0xf000 | ctx.tableSize;
 		WRITE_SUBDIR_ID(entry, subdirId);
@@ -246,30 +243,27 @@ bool WriteFntSubtable(FILE *fpRom, size_t *pAddress, FntContext *pContext) {
 
 		char name[128];
 		strncpy(name, entry->name, entry->length);
-		if (chdir(name) != 0) FATAL("Failed to enter assets subdirectory '%s'\n", name);
-		if (!WriteFntSubtable(fpRom, &address, &ctx)) return false;
-		if (chdir("..") != 0) FATAL("Failed to leave assets subdirectory '%s'\n", name);
+		if (!WriteFntSubtable(fpRom, &address, child, &ctx)) return false;
 
 		ctx.parentId = oldParentId;
 	}
 
 	// Update subdir IDs
 	size_t subtableOffset = 0;
-	for (size_t i = 0; i < numEntries; ++i) {
-		FntSubEntry *entry = entries[i];
+	for (size_t i = 0; i < tree->numChildren; ++i) {
+		FntTree *child = &tree->children[i];
+		FntSubEntry *entry = child->entry;
 		size_t entrySize = sizeof(*entry) + entry->length + (entry->isSubdir ? 2 : 0);
 		memcpy(ctx.subtable + subtableStart + subtableOffset, entry, entrySize);
 		subtableOffset += entrySize;
 	}
-
-	FreeFiles(entries, numEntries);
 	
 	memcpy(pContext, &ctx, sizeof(ctx));
 	*pAddress = address;
 	return true;
 }
 
-bool WriteFnt(FILE *fpRom, size_t *pAddress, size_t firstFileId) {
+bool WriteFnt(FILE *fpRom, size_t *pAddress, FntTree *pRoot, size_t firstFileId) {
 	size_t address = *pAddress;
 
 	FntContext ctx;
@@ -281,7 +275,7 @@ bool WriteFnt(FILE *fpRom, size_t *pAddress, size_t firstFileId) {
 	ctx.subtableSize = 0;
 	ctx.subtableMax = INITIAL_SUBTABLE_SIZE;
 
-	if (!WriteFntSubtable(fpRom, &address, &ctx)) return false;
+	if (!WriteFntSubtable(fpRom, &address, pRoot, &ctx)) return false;
 	free(ctx.subtable);
 
 	*pAddress = address;
@@ -430,9 +424,13 @@ int main(int argc, const char **argv) {
 	header.arm7.offset = address;
 	if (!AppendFile(fpRom, ARM7_PROGRAM_FILE, &address, &header.arm7.size)) return 1;
 
+	FntTree root;
+	if (!MakeFntTree(&root)) return false;
+	if (!SortFntTree(&root)) return false;
+
 	if (!Align(256, fpRom, &address)) return 1;
 	header.fileNames.offset = address;
-	if (!WriteFnt(fpRom, &address, numOverlays)) return 1;
+	if (!WriteFnt(fpRom, &address, &root, numOverlays)) return 1;
 
 	if (!Align(256, fpRom, &address)) return 1;
 	header.fileAllocs.offset = address;
@@ -440,6 +438,8 @@ int main(int argc, const char **argv) {
 
 	// TODO (aetias): Write files
 
+	if (!FreeFntTree(&root)) return false;
+
 	if (chdir(rootDir) != 0) {
 		fprintf(stderr, "Failed to leave assets directory '%s'\n", assetsDir);
 		return 1;
diff --git a/tools/rom/files.h b/tools/rom/files.h
index a776a8ab..5e0c44dd 100644
--- a/tools/rom/files.h
+++ b/tools/rom/files.h
@@ -4,68 +4,150 @@
 #include "util.h"
 #include "rom.h"
 
-bool GetFiles(FntSubEntry **entries, size_t maxLength, size_t *pLength) {
+bool MakeFntTree(FntTree *pTree);
+
+bool IterFiles(bool (*callback)(const char *name, bool isDir, void*), void *userData) {
 #ifdef _WIN32
-	size_t length = 0;
-	WIN32_FIND_DATA findData;
+	WIN32_FIND_DATAA findData;
 	HANDLE hFind = FindFirstFileA("*", &findData);
-	if (hFind == INVALID_HANDLE_VALUE) FATAL("Failed to open directory to get files\n");
+	if (hFind == INVALID_HANDLE_VALUE) FATAL("Failed to open directory to iterate files\n");
 	do {
-		if (length >= maxLength) FATAL("Max file entries surpassed\n");
-		size_t nameLength = strlen(findData.cFileName);
-		if (nameLength > 127) FATAL("File name '%s' longer than 127 characters\n", findData.cFileName);
-
-		bool isSubdir = (findData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0;
-		size_t extraSize = isSubdir ? 2 : 0;
-		FntSubEntry *entry = (FntSubEntry*) malloc(sizeof(FntSubEntry) + nameLength + extraSize);
-		entry->isSubdir = isSubdir;
-		entry->length = nameLength;
-		memcpy(entry->name, findData.cFileName, nameLength);
-		WRITE_SUBDIR_ID(entry, 0);
-
-		entries[length] = entry;
-		length += 1;
+		const char *name = findData.cFileName;
+		bool isDir = (findData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0;
+		if (!callback(name, isDir, userData)) return false;
 	} while (FindNextFileA(hFind, &findData));
 	FindClose(hFind);
-	*pLength = length;
-	return true;
-#elif __linux__
-	size_t length = 0;
+#else __linux__
 	DIR *dir = opendir(".");
-	if (dir == NULL) FATAL("Failed to open directory to get files\n");
-	struct dirent *dirent;
-	while ((dirent = readdir(dir)) != NULL) {
-		if (length >= maxLength) FATAL("Max file entries surpassed\n");
-		size_t nameLength = strlen(dirent->d_name);
-		if (nameLength > 127) FATAL("File name '%s' longer than 127 characters\n", dirent->d_name);
-
-		bool isSubdir = dirent->d_type == DT_DIR;
-		size_t extraSize = isSubdir ? 2 : 0;
-		FntSubEntry *entry = (FntSubEntry*) malloc(sizeof(FntSubEntry) + nameLength + extraSize);
-		entry->isSubdir = isSubdir;
+	struct dirent entry;
+	while ((entry = readdir(dir)) != NULL) {
+		const char *name = entry->d_name;
+		bool isDir = entry->d_type == DT_DIR;
+		if (!callback(name, isDir, userData)) return false;
+	}
+	closedir(dir);
+#endif
+}
+
+typedef struct FntTree {
+	struct FntTree *children;
+	size_t numChildren;
+	size_t maxChildren;
+	FntSubEntry *entry;
+} FntTree;
+
+bool _GrowFntTreeChildren(FntTree *pTree, size_t minChildren) {
+	FntTree tree;
+	memcpy(&tree, pTree, sizeof(tree));
+	if (tree.numChildren >= minChildren) return true;
+
+	size_t newSize = tree.maxChildren;
+	if (newSize == 0) newSize = minChildren;
+	while (newSize < minChildren) newSize *= 2;
+	if (tree.children == NULL) {
+		FntTree *children = malloc(newSize * sizeof(FntTree));
+		if (children == NULL) FATAL("Failed to allocate FNT tree children\n");
+		tree.children = children;
+	} else {
+		FntTree *children = realloc(tree.children, newSize * sizeof(FntTree));
+		if (children == NULL) FATAL("Failed to reallocate FNT tree children\n");
+		tree.children = children;
+	}
+	tree.maxChildren = newSize;
+
+	memcpy(pTree, &tree, sizeof(tree));
+	return true;
+}
+
+bool _FntTreeFileCallback(const char *name, bool isDir, void *userData) {
+	FntTree *pTree = (FntTree*) userData;
+	size_t nameLength = strlen(name);
+
+	if (isDir) {
+		FntSubEntry *entry = malloc(sizeof(FntSubEntry) + nameLength + 2);
+		if (entry == NULL) FATAL("Failed to allocate FNT sub entry for directory '%s'\n", name);
+		entry->isSubdir = true;
 		entry->length = nameLength;
-		memcpy(entry->name, findData.cFileName, nameLength);
+		memcpy(entry->name, name, nameLength);
+		WRITE_SUBDIR_ID(entry, 0);
 
-		entries[length] = entry;
-		length += 1;
+		if (chdir(name) != 0) FATAL("Failed to enter FNT directory '%s'\n", name);
+
+		FntTree child;
+		if (!MakeFntTree(&child)) return false;
+		child.entry = entry;
+		memcpy(&pTree->children[pTree->numChildren], &child, sizeof(child));
+		pTree->numChildren += 1;
+
+		if (chdir("..") != 0) FATAL("Failed to leave FNT directory '%s'\n", name);
+	} else {
+		FntSubEntry *entry = malloc(sizeof(FntSubEntry) + nameLength);
+		if (entry == NULL) FATAL("Failed to allocate FNT sub entry for file '%s'\n", name);
+		entry->isSubdir = false;
+		entry->length = nameLength;
+		memcpy(entry->name, name, nameLength);
+
+		FntTree child;
+		child.children = NULL;
+		child.numChildren = 0;
+		child.maxChildren = 0;
+		child.entry = entry;
+		if (!_GrowFntTreeChildren(pTree, pTree->numChildren + 1)) return false;
+		memcpy(&pTree->children[pTree->numChildren], &child, sizeof(child));
+		pTree->numChildren += 1;
 	}
-	closedir(dir);
-	*pLength = length;
+}
+
+bool MakeFntTree(FntTree *pTree) {
+	FntTree tree;
+	tree.maxChildren = 0;
+	tree.numChildren = 0;
+	if (!_GrowFntTreeChildren(&tree, 64)) return false;
+	tree.entry = NULL;
+
+	if (!IterFiles(_FntTreeFileCallback, &tree)) return false;
+	memcpy(pTree, &tree, sizeof(tree));
 	return true;
-#endif
 }
 
-bool FreeFiles(FntSubEntry **pEntries, size_t length) {
-	for (size_t i = 0; i < length; ++i) free(pEntries[i]);
+bool FreeFntTree(FntTree *pTree) {
+	for (size_t i = 0; i < pTree->numChildren; ++i) {
+		if (!FreeFntTree(&pTree->children[i])) return false;
+	}
+	if (pTree->children != NULL) {
+		free(pTree->children);
+		pTree->children = NULL;
+	}
+	pTree->numChildren = 0;
+	pTree->maxChildren = 0;
+	if (pTree->entry != NULL) {
+		free(pTree->entry);
+		pTree->entry = NULL;
+	}
 }
 
-int CompareFnt(const FntSubEntry *a, const FntSubEntry *b) {
-	size_t minSize = ((a->length < b->length) ? a : b)->length;
-	int cmp = strncmp(a->name, b->name, minSize);
+int CompareFntTree(const FntTree *a, const FntTree *b) {
+	size_t lenA = a->entry->length;
+	size_t lenB = b->entry->length;
+	size_t minSize = (lenA < lenB) ? lenA : lenB;
+	int cmp = strncmp(a->entry->name, b->entry->name, minSize);
 	if (cmp != 0) return cmp;
-	if (a->length < b->length) return -1;
-	if (a->length > b->length) return 1;
+	if (lenA < lenB) return -1;
+	if (lenA > lenB) return 1;
 	return 0;
 }
 
+bool SortFntTree(FntTree *pTree) {
+	FntTree tree;
+	memcpy(&tree, pTree, sizeof(tree));
+
+	qsort(tree.children, tree.numChildren, sizeof(*tree.children), CompareFntTree);
+	for (size_t i = 0; i < tree.numChildren; ++i) {
+		if (!SortFntTree(&tree.children[i])) return false;
+	}
+
+	memcpy(pTree, &tree, sizeof(tree));
+	return true;
+}
+
 #endif