Merge pull request #55 from spicyjpeg/psxmdec

Full MDEC support, C library refactors, cleanups and bugfixes (v0.20)

5 files changed, 278 insertions, 258 deletions

diff --git a/libpsn00b/libc/_start.s b/libpsn00b/libc/_start.s
new file mode 100644
index 0000000..56075c8
--- /dev/null
+++ b/libpsn00b/libc/_start.s
@@ -0,0 +1,18 @@
+# PSn00bSDK _start() trampoline
+# (C) 2022 spicyjpeg - MPL licensed
+#
+# This file provides a weak function that can be easily overridden to e.g. set
+# $sp or perform additional initialization before the "real" _start()
+# (_start_inner()) is called.
+
+.set noreorder
+.section .text
+
+.global _start
+.type _start, @function
+.weak _start
+_start:
+	la $gp, _gp
+
+	j  _start_inner
+	nop
diff --git a/libpsn00b/libc/c++-support.cxx b/libpsn00b/libc/cpp_support.cpp
index 38354dd..f451044 100644
--- a/libpsn00b/libc/c++-support.cxx
+++ b/libpsn00b/libc/cpp_support.cpp
@@ -1,8 +1,22 @@
+/*
+ * PSn00bSDK C++ support library
+ * (C) 2019-2022 Lameguy64, spicyjpeg - MPL licensed
+ */
 
 #include <stdint.h>
 #include <stdlib.h>
 #include <stdio.h>
 
+/* GCC builtins */
+
+extern "C" void *__builtin_new(size_t size) {
+	return malloc(size);
+}
+
+extern "C" void __builtin_delete(void *ptr) {
+	free(ptr);
+}
+
 /* Default new/delete operators */
 
 void *operator new(size_t size) noexcept {
@@ -21,20 +35,15 @@ void operator delete[](void *ptr) noexcept {
 	free(ptr);
 }
 
-/*
- * https://en.cppreference.com/w/cpp/memory/new/operator_delete
- *
- * Called if a user-defined replacement is provided, except that it's
- * unspecified whether other overloads or this overload is called when deleting
- * objects of incomplete type and arrays of non-class and trivially
- * destructible class types.
- *
- * A memory allocator can use the given size to be more efficient.
- */
+// https://en.cppreference.com/w/cpp/memory/new/operator_delete
 void operator delete(void *ptr, size_t size) noexcept {
 	free(ptr);
 }
 
+void operator delete[](void *ptr, size_t size) noexcept {
+	free(ptr);
+}
+
 /* Placement new operators */
 
 void *operator new(size_t size, void *ptr) noexcept {
diff --git a/libpsn00b/libc/malloc.c b/libpsn00b/libc/malloc.c
new file mode 100644
index 0000000..9d538cd
--- /dev/null
+++ b/libpsn00b/libc/malloc.c
@@ -0,0 +1,235 @@
+/*
+ * PSn00bSDK default memory allocator
+ * (C) 2022 Nicolas Noble, spicyjpeg
+ *
+ * This code is based on psyqo's malloc implementation, available here:
+ * https://github.com/grumpycoders/pcsx-redux/blob/main/src/mips/psyqo/src/alloc.c
+ *
+ * Heap management and memory allocation are completely separate, with the
+ * latter being built on top of the former. This makes it possible to override
+ * only InitHeap() and sbrk() while still using the default allocator, or
+ * override malloc()/realloc()/free() while using the default heap manager.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#define _align(x, n) (((x) + ((n) - 1)) & ~((n) - 1))
+
+/* Private types */
+
+typedef struct _BlockHeader {
+	struct _BlockHeader	*prev, *next;
+	void				*ptr;
+	size_t				size;
+} BlockHeader;
+
+/* Data */
+
+static void			*_heap_start, *_heap_end, *_heap_limit;
+static void			*_alloc_start = 0;
+static BlockHeader	*_alloc_head = 0, *_alloc_tail = 0;
+
+/* Heap management API */
+
+__attribute__((weak)) void InitHeap(void *addr, size_t size) {
+	_heap_start = addr;
+	_heap_end   = addr;
+	_heap_limit = (void *) ((uintptr_t) addr + size);
+}
+
+__attribute__((weak)) void *sbrk(ptrdiff_t incr) {
+	void *old_end = _heap_end;
+	void *new_end = (void *) _align((uintptr_t) old_end + incr, 8);
+
+	if (new_end > _heap_limit)
+		return 0;
+
+	_heap_end = new_end;
+	return old_end;
+}
+
+/* Memory allocator */
+
+static BlockHeader *_find_fit(BlockHeader *head, size_t size) {
+	BlockHeader *prev = head;
+
+	for (; prev; prev = prev->next) {
+		if (prev->next) {
+			uintptr_t next_bot = (uintptr_t) prev->next;
+			next_bot          -= (uintptr_t) prev->ptr + prev->size;
+
+			if (next_bot >= size)
+				return prev;
+		}
+	}
+
+	return prev;
+}
+
+__attribute__((weak)) void *malloc(size_t size) {
+	size_t _size = _align(size + sizeof(BlockHeader), 8);
+
+	// Nothing's initialized yet? Let's just initialize the bottom of our heap,
+	// flag it as allocated.
+	if (!_alloc_head) {
+		if (!_alloc_start)
+			_alloc_start = sbrk(0);
+
+		BlockHeader *new = (BlockHeader *) sbrk(_size);
+		if (!new)
+			return 0;
+
+		void *ptr = (void *) &new[1];
+		new->ptr  = ptr;
+		new->size = _size - sizeof(BlockHeader);
+		new->prev = 0;
+		new->next = 0;
+
+		_alloc_head = new;
+		_alloc_tail = new;
+		return ptr;
+	}
+
+	// We *may* have the bottom of our heap that has shifted, because of a free.
+	// So let's check first if we have free space there, because I'm nervous
+	// about having an incomplete data structure.
+	if (((uintptr_t) _alloc_start + _size) < ((uintptr_t) _alloc_head)) {
+		BlockHeader *new = (BlockHeader *) _alloc_start;
+
+		void *ptr = (void *) &new[1];
+		new->ptr  = ptr;
+		new->size = _size - sizeof(BlockHeader);
+		new->prev = 0;
+		new->next = _alloc_head;
+
+		_alloc_head->prev = new;
+		_alloc_head       = new;
+		return ptr;
+	}
+
+	// No luck at the beginning of the heap, let's walk the heap to find a fit.
+	BlockHeader *prev = _find_fit(_alloc_head, _size);
+	if (prev) {
+		BlockHeader *new = (BlockHeader *) ((uintptr_t) prev->ptr + prev->size);
+
+		void *ptr = (void *)((uintptr_t) new + sizeof(BlockHeader));
+		new->ptr  = ptr;
+		new->size = _size - sizeof(BlockHeader);
+		new->prev = prev;
+		new->next = prev->next;
+
+		(new->next)->prev = new;
+		prev->next        = new;
+		return ptr;
+	}
+
+	// Time to extend the size of the heap.
+	BlockHeader *new = (BlockHeader *) sbrk(_size);
+	if (!new)
+		return 0;
+
+	void *ptr = (void *) &new[1];
+	new->ptr  = ptr;
+	new->size = _size - sizeof(BlockHeader);
+	new->prev = _alloc_tail;
+	new->next = 0;
+
+	_alloc_tail->next = new;
+	_alloc_tail       = new;
+	return ptr;
+}
+
+__attribute__((weak)) void *calloc(size_t num, size_t size) {
+	return malloc(num * size);
+}
+
+__attribute__((weak)) void *realloc(void *ptr, size_t size) {
+	if (!size) {
+		free(ptr);
+		return 0;
+	}
+	if (!ptr)
+		return malloc(size);
+
+	size_t _size = _align(size + sizeof(BlockHeader), 8);
+
+	BlockHeader *prev = (BlockHeader *) ((uintptr_t) ptr - sizeof(BlockHeader));
+
+	// New memory block shorter?
+	if (prev->size >= _size) {
+		prev->size = _size;
+		if (!prev->next)
+			sbrk((ptr - sbrk(0)) + _size);
+
+		return ptr;
+	}
+
+	// New memory block larger; is it the last one?
+	if (!prev->next) {
+		void *new = sbrk(_size - prev->size);
+		if (!new)
+			return 0;
+
+		prev->size = _size;
+		return ptr;
+	}
+
+	// Do we have free memory after it?
+	if (((prev->next)->ptr - ptr) > _size) {
+		prev->size = _size;
+		return ptr;
+	}
+
+	// No luck.
+	void *new = malloc(_size);
+	if (!new)
+		return 0;
+
+	__builtin_memcpy(new, ptr, prev->size);
+	free(ptr);
+	return new;
+}
+
+__attribute__((weak)) void free(void *ptr) {
+	if (!ptr || !_alloc_head)
+		return;
+
+	// First block; bumping head ahead.
+	if (ptr == _alloc_head->ptr) {
+		size_t size = _alloc_head->size;
+		size       += (uintptr_t) _alloc_head->ptr - (uintptr_t) _alloc_head;
+		_alloc_head = _alloc_head->next;
+
+		if (_alloc_head) {
+			_alloc_head->prev = 0;
+		} else {
+			_alloc_tail = 0;
+			sbrk(-size);
+		}
+
+		return;
+	}
+
+	// Finding the proper block
+	BlockHeader *cur = _alloc_head;
+	for (cur = _alloc_head; ptr != cur->ptr; cur = cur->next) {
+		if (!cur->next)
+			return;
+	}
+
+	if (cur->next) {
+		// In the middle, just unlink it
+		cur->next->prev = cur->prev;
+	} else {
+		// At the end, shrink heap
+		_alloc_tail = cur->prev;
+
+		void  *top  = sbrk(0);
+		size_t size = (top - (cur->prev)->ptr) - (cur->prev)->size;
+		sbrk(-size);
+	}
+
+	(cur->prev)->next = cur->next;
+}
diff --git a/libpsn00b/libc/malloc.s b/libpsn00b/libc/malloc.s
deleted file mode 100644
index e441bbe..0000000
--- a/libpsn00b/libc/malloc.s
+++ /dev/null
@@ -1,242 +0,0 @@
-# Custom first-fit malloc routines by Lameguy64
-# Part of the PSn00bSDK Project
-#
-# NOTE: there reportedly is a GCC bug which messes up .weak functions written
-# in assembly if LTO is enabled. I haven't tested but, according to the
-# internet, this bug has never been fixed.
-# https://gcc.gnu.org/legacy-ml/gcc-help/2019-10/msg00092.html
-
-.set noreorder
-
-.set ND_PREV,	0	# Address to previous block (NULL if starting block)
-.set ND_NEXT,	4	# Address to next block (NULL if end block)
-.set ND_SIZE,	8	# Size of block
-.set ND_HSIZ,	12
-
-.section .text
-
-# Stupid small function just to get bss end
-# due to GCC insisting externs to be gp relative
-.global GetBSSend
-.type GetBSSend, @function
-GetBSSend:
-	la		$v0, _end
-	jr		$ra
-	nop
-	
-
-# Initializes the heap for malloc
-#   a0 - Starting address of heap
-#   a1 - Size of memory heap
-#
-.global InitHeap
-.type InitHeap, @function
-.weak InitHeap
-InitHeap:
-	la		$v0, _malloc_addr
-	sw		$a0, 0($v0)
-	la		$v0, _malloc_size
-	sw		$a1, 0($v0)
-	
-	sw		$0 , ND_PREV($a0)		# Set heap header
-	sw		$0 , ND_NEXT($a0)
-	jr		$ra
-	sw		$0 , ND_SIZE($a0)
-	
-	
-# Changes the heap size without clearing or relocating the heap
-#   a0 - Size of memory heap in bytes
-.global SetHeapSize
-.type SetHeapSize, @function
-.weak SetHeapSize
-SetHeapSize:
-	la		$v1, _malloc_size
-	lw		$v0, 0($v1)
-	jr		$ra
-	sw		$a1, 0($v1)
-
-
-# Allocates a block of memory in the heap
-#   a0 - Size of memory block to allocate.
-#
-.global malloc
-.type malloc, @function
-.weak malloc
-malloc:
-	addiu	$a0, 3					# Round size to a multiple of 4
-	srl		$a0, 2
-	
-	la		$a2, _malloc_addr
-	lw		$a2, 0($a2)
-	sll		$a0, 2
-	
-.Lfind_next:
-	
-	move	$a1, $a2
-	
-	lw		$a2, ND_NEXT($a1)		# Get block header
-	lw		$v1, ND_SIZE($a1)
-	
-	subu	$v0, $a2, $a1			# Compute space between current and next
-	
-	beqz	$v1, .Lempty_block		# Occupy empty block (if size = 0)
-	nop
-	
-	beqz	$a2, .Lnew_block		# Allocate a new block (if no next)
-	nop
-	
-	addiu	$v0, -(ND_HSIZ*2)		# Compute remaining space of block
-	subu	$v0, $v1
-	
-	blt		$v0, $a0, .Lfind_next	# Search for the next block if space is not big enough
-	nop
-	
-	# Perform a block split using remaining space of current block
-
-	addiu	$v0, $a1, ND_HSIZ		# Compute address for new header
-	addu	$v0, $v1
-	
-	sw		$a1, ND_PREV($v0)		# Set the new block header
-	sw		$a2, ND_NEXT($v0)
-	sw		$a0, ND_SIZE($v0)
-	
-	sw		$v0, ND_NEXT($a1)		# Update previous and next blocks
-	sw		$v0, ND_PREV($a2)
-	
-	jr		$ra
-	addiu	$v0, ND_HSIZ
-	
-.Lempty_block:						# Occupy an empty block
-
-	beqz	$a2, .Lno_next			# Skip size calculation if there's no next
-	nop
-	
-	addiu	$v0, -ND_HSIZ
-	blt		$v0, $a0, .Lfind_next
-	nop
-	
-	b		.Lskip_space_check
-	nop
-	
-.Lno_next:
-
-	la		$v1, _malloc_addr		# Check if there's enough space for a block
-	lw		$v1, 0($v1)
-	la		$v0, _malloc_size
-	lw		$v0, 0($v0)
-	
-	subu	$v1, $a1, $v1
-	addu	$v1, $a0
-	addiu	$v1, ND_HSIZ
-	
-	bgt		$v1, $v0, .Lno_space
-	nop
-	
-.Lskip_space_check:
-
-	sw		$a0, ND_SIZE($a1)
-	jr		$ra						# Return address
-	addiu	$v0, $a1, ND_HSIZ
-	
-.Lnew_block:						# Create a new block
-
-	addu	$a2, $a1, $v1			# Compute address for new block
-	addiu	$a2, ND_HSIZ
-	
-	la		$v1, _malloc_addr
-	lw		$v1, 0($v1)
-	la		$v0, _malloc_size
-	lw		$v0, 0($v0)
-	
-	subu	$v1, $a2, $v1
-	addu	$v1, $a0
-	addiu	$v1, ND_HSIZ
-	
-	bgt		$v1, $v0, .Lno_space	# Reject if it exceeds specified size
-	nop
-	
-	sw		$a1, ND_PREV($a2)
-	sw		$0 , ND_NEXT($a2)
-	sw		$a0, ND_SIZE($a2)
-	
-	sw		$a2, ND_NEXT($a1)
-	
-	jr		$ra						# Return address
-	addiu	$v0, $a2, ND_HSIZ
-	
-.Lno_space:							# Return a null if no space can be found
-
-	jr		$ra
-	move	$v0, $0
-
-	
-# Allocates a block of memory in block units and zero fills the
-# allocated block.
-#   a0 - Block size.
-#	a1 - Number of blocks to allocate
-#
-.global calloc
-.type calloc, @function
-.weak calloc
-calloc:
-	mult	$a0, $a1
-	addiu	$sp, -4
-	sw		$ra, 0($sp)
-	
-	jal		malloc
-	mflo	$a0
-	
-	move	$a0, $v0
-	mflo	$a1
-
-.Lclear_loop:
-
-	sw		$0 , 0($a0)
-	addi	$a1, 4
-	bgtz	$a1, .Lclear_loop
-	addiu	$a0, 4
-	
-	lw		$ra, 0($sp)
-	addiu	$sp, 4
-	jr		$ra
-	nop
-
-	
-# Deallocates an allocated block
-#	a0 - An address returned by malloc to deallocate
-#
-.global free
-.type free, @function
-.weak free
-free:
-
-	addiu	$a0, -ND_HSIZ
-	lw		$a1, ND_PREV($a0)
-	lw		$a2, ND_NEXT($a0)
-	
-	beqz	$a1, .Lis_start			# Check if block is a starting block
-	nop
-	
-	beqz	$a2, .Lis_end
-	nop
-
-	# Unlink
-	
-	sw		$a2, ND_NEXT($a1)
-	jr		$ra
-	sw		$a1, ND_PREV($a2)
-	
-.Lis_end:							# Unlinks the ending block
-
-	jr		$ra
-	sw		$0 , ND_NEXT($a1)
-	
-.Lis_start:							# Simply set size to 0 if starting block
-
-	jr		$ra
-	sw		$0 , ND_SIZE($a0)
-
-
-# Internal variables
-.comm _malloc_addr, 4, 4
-.comm _malloc_size, 4, 4
diff --git a/libpsn00b/libc/start.c b/libpsn00b/libc/start.c
index fd6fe33..87ac951 100644
--- a/libpsn00b/libc/start.c
+++ b/libpsn00b/libc/start.c
@@ -62,10 +62,10 @@ extern uint8_t _end[];
 // useful though to change the stack size and/or reinitialize the heap on
 // systems that have more than 2 MB of RAM (e.g. emulators, devkits, PS1-based
 // arcade boards).
-void _mem_init(int ram_size, int stack_max_size) {
-	void *exe_end = _end + 4;
-	int  exe_size = (int) exe_end - (int) __text_start;
-	int  ram_used = (0x10000 + exe_size + stack_max_size) & 0xfffffffc;
+void _mem_init(size_t ram_size, size_t stack_max_size) {
+	void   *exe_end = _end + 4;
+	size_t exe_size = (size_t) exe_end - (size_t) __text_start;
+	size_t ram_used = (0x10000 + exe_size + stack_max_size) & 0xfffffffc;
 
 	InitHeap(exe_end, ram_size - ram_used);
 }
@@ -80,8 +80,8 @@ extern int main(int argc, const char* argv[]);
 // Even though _start() usually takes no arguments, this implementation allows
 // parent executables to pass args directly to child executables without having
 // to overwrite the arg strings in kernel RAM.
-void _start(int32_t override_argc, const char **override_argv) {
-	__asm__ volatile("la $gp, _gp;");
+void _start_inner(int32_t override_argc, const char **override_argv) {
+	//__asm__ volatile("la $gp, _gp;");
 
 	// Clear BSS 4 bytes at a time. BSS is always aligned to 4 bytes by the
 	// linker script.