initial commit

5 files changed, 424 insertions, 0 deletions

diff --git a/qstd/Makefile b/qstd/Makefile
new file mode 100644
index 0000000..fa952dc
--- /dev/null
+++ b/qstd/Makefile
@@ -0,0 +1,25 @@
+.POSIX:
+target = libqstd.a
+includes = -I../qstd
+defines = -Dplat_x86 -Dplat_posix -Dallocation_default_alignment=8
+cflags = -std=c90 -pedantic -Wall -Wextra $(DEBUG_COMPILE_FLAG) $(includes) $(defines)
+lflags = $(DEBUG_LINK_FLAG)
+
+objects = plat.o memory.o
+
+.PHONY: all clean
+
+all: $(target)
+
+memory.o: memory.c memory.h plat.h
+	$(CC) -c $(cflags) memory.c -o memory.o
+
+plat.o: plat.c plat.h
+	$(CC) -c $(cflags) plat.c -o plat.o
+
+$(target): $(objects)
+	$(AR) -rcs $(target) $(objects)
+
+clean:
+	rm -f $(target)
+	rm -f $(objects)
diff --git a/qstd/memory.c b/qstd/memory.c
new file mode 100644
index 0000000..91e4a5b
--- /dev/null
+++ b/qstd/memory.c
@@ -0,0 +1,225 @@
+#include "memory.h"
+#include "plat.h"
+#include <stdint.h>
+#include <stddef.h>
+
+int aligned(const void* p, int a) {
+	return (uintptr_t)p % a == 0;
+}
+
+int align_size(int s, int a) {
+	return (s + (a - 1)) & -a;
+}
+
+static uintptr_t align_address(
+	uintptr_t ad,
+	size_t al
+) {
+	size_t m;
+	m = al - 1;
+	return (ad + m) & ~m;
+}
+
+void init_arena(
+	Arena* a,
+	void* mem,
+	int size
+) {
+	a->buf = mem;
+	a->size = size;
+	a->ptr = 0;
+}
+
+void clear_arena(Arena* a) {
+	a->ptr = 0;
+}
+
+void* imp_arena_alloc(
+	Arena* a,
+	int size
+) {
+	char* r;
+	assert(a->ptr + size < a->size);
+	r = &a->buf[a->ptr];
+	a->ptr += size;
+	return r;
+}
+
+void* arena_alloc(
+	Arena* a,
+	int size
+) {
+	return arena_alloc_aligned(
+		a,
+		size,
+		allocation_default_alignment
+	);
+}
+
+void* arena_alloc_aligned(
+	Arena* a,
+	int size,
+	int align
+) {
+	void* p;
+	p = imp_arena_alloc(
+		a,
+		size + align + 1
+	);
+	return (void*)align_address((uintptr_t)p, align);
+}
+
+void init_heap(
+	Heap* h,
+	void* mem,
+	int size
+) {
+	int* fb;
+	assert(aligned(mem, 4));
+	assert(size > 8);
+	h->buf = mem;
+	h->size = size;
+	h->blocks = 1;
+	fb = (int*)h->buf;
+	fb[0] = size;
+}
+
+void* imp2_heap_alloc(
+	Heap* h,
+	int size
+) {
+	int o, i;
+	int hs = sizeof(int);
+	int as = align_size(size + hs, hs);
+	int f = ~((unsigned)-1 >> 1);
+	for (i = o = 0; i < h->blocks; i++) {
+		int* phdr = (int*)&h->buf[o];
+		int hdr = *phdr, bs;
+		assert(aligned(phdr, sizeof hdr));
+		bs = hdr & ~f;
+		if (~hdr & f) {
+			if (as == bs) {
+				phdr[0] |= 1;
+				return phdr + 1;
+			} else {
+				int ns = bs - as;
+				if (ns > hs) {
+					int* nhdr = &phdr[ns / 4];
+					phdr[0] = ns;
+					nhdr[0] = as | f;
+					h->blocks++;
+					return &nhdr[1];
+				}
+			}
+		} else
+			o += bs;
+	}
+	return 0;
+}
+
+void* imp_heap_alloc(Heap* h, int s) {
+	void* p = imp2_heap_alloc(h, s);
+	if (!p) {
+		heap_defrag(h);
+		p = imp2_heap_alloc(h, s);
+	}
+	return p;
+}
+
+void imp_heap_free(Heap* h, void* p) {
+	assert((char*)p > h->buf);
+	assert((char*)p < h->buf + h->size);
+	(void)h;
+	((int*)p)[-1] &= (unsigned)-1 >> 1;
+}
+
+void* heap_alloc_aligned(
+	Heap* h,
+	int size,
+	int align
+) {
+	unsigned char* p, * a;
+	ptrdiff_t shift;
+	size += (int)align;
+	p = imp_heap_alloc(h, size);
+	if (!p) { return 0; }
+	a = (unsigned char*)align_address((uintptr_t)p, align);
+	a += align * (unsigned)(p == a);
+	shift = a - p;
+	a[-1] = shift & 0xff;
+	return a;
+}
+
+void heap_free_aligned(Heap* h, void* p) {
+	unsigned char* a;
+	ptrdiff_t shift;
+	a = p;
+	shift = a[-1];
+	shift += 256 * shift == 0;
+	a -= shift;
+	imp_heap_free(h, a);
+}
+
+void heap_defrag(Heap* h) {
+	int i, o, mtc;
+	int f = ~((unsigned)-1 >> 1);
+	for (i = o = mtc = 0; i < h->blocks; i++) {
+		int* phdr = (int*)&h->buf[o];
+		int hdr = *phdr, bs, m, mc;
+		assert(aligned(phdr, sizeof hdr));
+		bs = hdr & ~f;
+		if (~hdr & f) {
+			for (
+				m = bs, mc = 0, i++;
+				i < h->blocks;
+				i++, mc++
+			) {
+				int mhdr = *(int*)&h->buf[o + m];
+				if (~mhdr & f)
+					m += mhdr & ~f;
+				else
+					break;
+			}
+			i--;
+			bs = m;
+			phdr[0] = bs;
+			mtc += mc;
+		}
+		o += bs;
+	}
+	h->blocks -= mtc;
+}
+
+void* heap_alloc(
+	Heap* h,
+	int size
+) {
+	return heap_alloc_aligned(
+		h,
+		size,
+		allocation_default_alignment
+	);
+}
+
+void heap_free(
+	Heap* h,
+	void* p
+) {
+	heap_free_aligned(h, p);
+}
+
+/*
+void print_blocks(Heap* h) {
+	int i, o;
+	int fb = ~((unsigned)-1 >> 1);
+	for (i = o = 0; i < h->blocks; i++) {
+		int b = *(int*)&h->buf[o];
+		int bs = b & ~fb;
+		int f = ~b & fb;
+		printf("%s  %d\n", f? "free": "    ", bs);
+		o += bs;
+	}
+	assert(o == h->size);
+}
+*/
+
diff --git a/qstd/memory.h b/qstd/memory.h
new file mode 100644
index 0000000..26c0382
--- /dev/null
+++ b/qstd/memory.h
@@ -0,0 +1,56 @@
+#ifndef memory_h
+#define memory_h
+
+int aligned(const void* p, int a);
+int align_size(int s, int a);
+
+typedef struct Arena {
+	char* buf;
+	int size, ptr;
+} Arena;
+
+void init_arena(
+	Arena* a,
+	void* mem,
+	int size
+);
+void clear_arena(Arena* a);
+void* arena_alloc(
+	Arena* a,
+	int size
+);
+void* arena_alloc_aligned(
+	Arena* a,
+	int size,
+	int align
+);
+
+typedef struct Heap {
+	char* buf;
+	int size, blocks;
+} Heap;
+
+void init_heap(
+	Heap* h,
+	void* mem,
+	int size
+);
+void* heap_alloc(
+	Heap* h,
+	int size
+);
+void* heap_alloc_aligned(
+	Heap* h,
+	int size,
+	int align
+);
+void heap_free_aligned(
+	Heap* h,
+	void* p
+);
+void heap_free(
+	Heap* h,
+	void* p
+);
+void heap_defrag(Heap* h);
+#endif
diff --git a/qstd/plat.c b/qstd/plat.c
new file mode 100644
index 0000000..61385ff
--- /dev/null
+++ b/qstd/plat.c
@@ -0,0 +1,86 @@
+#include "plat.h"
+
+#ifdef plat_posix
+#define _POSIX_SOURCE
+#define _GNU_SOURCE
+
+#include <fcntl.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <time.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+extern int isatty(int);
+extern int fileno(FILE*);
+
+int imp_assert(
+	int val,
+	const char* expr,
+	const char* file,
+	int line
+) {
+	if (!val) {
+		print_err(
+			"%d:%s: Assertion failed: %s.\n",
+			line,
+			file,
+			expr
+		);
+		pbreak(420);
+		return 0;
+	}
+	return 1;
+}
+
+void print(const char* fmt, ...) {
+	va_list args;
+	va_start(args, fmt);
+	vfprintf(stdout, fmt, args);
+	va_end(args);
+}
+
+void print_err(const char* fmt, ...) {
+	va_list args;
+	va_start(args, fmt);
+
+	if (isatty(fileno(stderr))) {
+		fprintf(stderr, "\033[31;31m");
+	}
+
+	vfprintf(stderr, fmt, args);
+
+	if (isatty(fileno(stderr))) {
+		fprintf(stderr, "\033[0m");
+	}
+
+	va_end(args);
+}
+
+void print_war(const char* fmt, ...) {
+	va_list args;
+	va_start(args, fmt);
+
+	if (isatty(fileno(stderr))) {
+		fprintf(stderr, "\033[31;35m");
+	}
+
+	vfprintf(stderr, fmt, args);
+
+	if (isatty(fileno(stderr))) {
+		fprintf(stderr, "\033[0m");
+	}
+
+	va_end(args);
+}
+
+void pbreak(int code) {
+#if defined(DEBUG) && defined(plat_x86)
+	__asm__("int3;");
+	(void)code;
+#else
+	exit(code);
+#endif
+}
+
+#endif
diff --git a/qstd/plat.h b/qstd/plat.h
new file mode 100644
index 0000000..27521fa
--- /dev/null
+++ b/qstd/plat.h
@@ -0,0 +1,32 @@
+#ifndef plat_h
+#define plat_h
+
+#ifdef assert
+#undef assert
+#endif
+
+#ifdef DEBUG
+#define assert(expr) \
+	imp_assert( \
+		expr, \
+		#expr, \
+		__FILE__, \
+		__LINE__ \
+	)
+#else
+#define assert(expr)
+#endif
+
+int imp_assert(
+	int val,
+	const char* expr,
+	const char* file,
+	int line
+);
+
+void print(const char* fmt, ...);
+void print_err(const char* fmt, ...);
+void print_war(const char* fmt, ...);
+void pbreak(int code);
+
+#endif