ls command

8 files changed, 261 insertions, 12 deletions

diff --git a/stage3/def.h b/stage3/def.h
index f125a01..807af43 100644
--- a/stage3/def.h
+++ b/stage3/def.h
@@ -35,4 +35,6 @@ typedef struct {
 #define BARRIER_VAR(var) asm volatile(""::"m"(var))
 #define BARRIER() asm volatile("":::"memory")
 
+#define LEN(x) (sizeof (x) / sizeof *(x))
+
 #endif
diff --git a/stage3/fs.c b/stage3/fs.c
index d4a325f..5653e4e 100644
--- a/stage3/fs.c
+++ b/stage3/fs.c
@@ -4,29 +4,162 @@
 #include "memory.h"
 #include "heap.h"
 
-str fs_read(str filename)
+#define FS_WALKER(X) bool (X)(str filename, u64 lba, usize fsize, usize fsect, void *varg)
+
+void fs_walk(FS_WALKER(*fun), void *arg)
 {
-	u64 start = (*(u32 *) (0x1000-10-8))/512;
+	u64 lba = (*(u32 *) (0x1000-10-8))/512;
 
 	for (;;) {
-		u8 *info = ata_read_full(start, 1);
+		u8 *info = ata_read_full(lba, 1);
 
 		if (memcmp(info+257, "ustar", 5) != 0) {
 			free(info);
-			return NILS;
+			break;
 		}
 
-		usize fsize;
+		u64 fsize;
 		str_parse_num((str) { 11, (char *) info+124 }, 8, &fsize);
 
 		usize fsect = (fsize+511)/512;
+		str filename = str_intro((char *) info);
 
-		if (memcmp(info, filename.data, filename.len) == 0 && info[filename.len] == '\0') {
-			free(info);
-			return (str) { .len = fsize, .data = ata_read_full(start+1, fsect) };
+		bool done = fun(filename, lba, fsize, fsect, arg);
+
+		free(info);
+		if (done)
+			break;
+
+		lba += 1 + fsect;
+	}
+}
+
+typedef struct {
+	str path;
+	str result;
+} fs_read_arg;
+
+static FS_WALKER(fs_read_walker)
+{
+	fs_read_arg *arg = varg;
+
+	if (str_cmp(filename, arg->path) != 0)
+		return false;
+
+	arg->result = (str) { .len = fsize, .data = ata_read_full(lba+1, fsect) };
+	return true;
+}
+
+str fs_read(str path)
+{
+	fs_read_arg arg = {
+		.path = path,
+		.result = NILS,
+	};
+
+	fs_walk(&fs_read_walker, &arg);
+	return arg.result;
+}
+
+typedef struct {
+	str path;
+	usize cap;
+	dir result;
+} fs_readdir_arg;
+
+static str strip_trail(str x)
+{
+	while (x.len > 0 && x.data[x.len-1] == '/')
+		x.len--;
+	return x;
+}
+
+static FS_WALKER(fs_readdir_walker)
+{
+	(void) lba, (void) fsect;
+	fs_readdir_arg *arg = varg;
+
+	enum {
+		HER_SELF,
+		HER_CHILD,
+		HER_GRANDCHILD,
+	} heritage;
+
+	str entn;
+	str iter = filename;
+
+	bool match = str_start(iter, arg->path);
+	if (!match)
+		return false;
+	iter = str_advance(iter, arg->path.len);
+
+	if (iter.len == 0) {
+		entn = filename;
+		heritage = HER_SELF;
+	} else {
+		if (arg->path.len != 0) {
+			if (iter.data[0] != '/')
+				return false;
+			iter = str_advance(iter, 1);
+		}
+
+		if (iter.len == 0) {
+			entn = strip_trail(filename);
+			heritage = HER_SELF;
 		} else {
-			free(info);
-			start += 1 + fsect;
+			entn = str_walk(&iter, S("/"));
+			if (iter.len == 0)
+				heritage = HER_CHILD;
+			else
+				heritage = HER_GRANDCHILD;
 		}
 	}
+
+	bool is_dir = filename.len == 0 || filename.data[filename.len-1] == '/';
+
+	switch (heritage) {
+		case HER_SELF:
+			if (is_dir)
+				return false;
+
+			__attribute__((fallthrough));
+
+		case HER_CHILD:
+			if (arg->result.len == arg->cap)
+				arg->result.data = realloc(arg->result.data,
+					sizeof(dirent) * (arg->cap = arg->cap ? arg->cap*2 : 1));
+			arg->result.data[arg->result.len++] = (dirent) {
+				.name = str_clone(entn),
+				.size = fsize,
+				.is_dir = is_dir,
+				.children = 0,
+			};
+
+			return heritage == HER_SELF;
+
+		case HER_GRANDCHILD:
+			for (usize i = 0; i < arg->result.len; i++) {
+				dirent *d = &arg->result.data[i];
+				if (str_cmp(d->name, entn) == 0) {
+					d->size += fsize;
+					d->children++;
+					return false;
+				}
+			}
+
+			// orphan. this shouldn't happen
+			return false;
+	};
+}
+
+dir fs_readdir(str path)
+{
+	fs_readdir_arg arg = {
+		.path = strip_trail(path),
+		.cap = 0,
+		.result = { 0, nil },
+	};
+
+	fs_walk(&fs_readdir_walker, &arg);
+	return arg.result;
 }
diff --git a/stage3/fs.h b/stage3/fs.h
index c1fea24..f75f511 100644
--- a/stage3/fs.h
+++ b/stage3/fs.h
@@ -5,4 +5,18 @@
 
 str fs_read(str filename);
 
+typedef struct {
+	str name;
+	bool is_dir;
+	usize size;
+	usize children;
+} dirent;
+
+typedef struct {
+	usize len;
+	dirent *data;
+} dir;
+
+dir fs_readdir(str path);
+
 #endif
diff --git a/stage3/interrupts.c b/stage3/interrupts.c
index edfe431..0a2dd6f 100644
--- a/stage3/interrupts.c
+++ b/stage3/interrupts.c
@@ -122,7 +122,7 @@ static void dump_frame(interrupt_frame *frame)
 
 	usize f = 0;
 	for (usize i = 0; i < 63; i++) {
-		bool has_name = f < sizeof flags / sizeof *flags && flags[f].bit == i;
+		bool has_name = f < LEN(flags) && flags[f].bit == i;
 
 		if (frame->rflags & ((u64) 1 << i)) {
 			if (has_name)
diff --git a/stage3/main.c b/stage3/main.c
index c2ae4c8..9f738d5 100644
--- a/stage3/main.c
+++ b/stage3/main.c
@@ -115,6 +115,7 @@ void kmain()
 	ata_init();
 	ps2_init();
 
+	print(S("loading debug info\n"));
 	dbg_map = fs_read(S("dbg/kernel.map"));
 	dbg_disas = fs_read(S("dbg/kernel.dis.asm"));
 
diff --git a/stage3/shell.c b/stage3/shell.c
index dfcea43..6aca52d 100644
--- a/stage3/shell.c
+++ b/stage3/shell.c
@@ -168,6 +168,58 @@ static void cmd_uname(str arg)
 	print(S("\n"));
 }
 
+static u64 ipow(u64 b, u64 exp)
+{
+	u64 x = 1;
+	for (u64 i = 0; i < exp; i++)
+		x *= b;
+	return x;
+}
+
+static void print_bytes(usize bytes)
+{
+	static char fmt[] = { ' ', 'K', 'M', 'G', 'T' };
+	usize unit = ipow(1000, LEN(fmt)-1);
+	for (usize i = 0; i < LEN(fmt); i++) {
+		if (bytes >= unit || unit == 1) {
+			print_num_pad(bytes/unit, 10, 3, ' ');
+			print_char('.');
+			print_dec((bytes%unit)/100);
+			print_char(' ');
+			print_char(fmt[LEN(fmt)-1-i]);
+			print_char('B');
+			break;
+		}
+		unit /= 1000;
+	}
+}
+
+static void cmd_ls(str arg)
+{
+	dir d = fs_readdir(arg);
+	usize longest = 0;
+	for (usize i = 0; i < d.len; i++)
+		if (longest < d.data[i].name.len)
+			longest = d.data[i].name.len;
+	for (usize i = 0; i < d.len; i++) {
+		print_char(' ');
+		print_bytes(d.data[i].size);
+		print_char(' ');
+		print(d.data[i].name);
+		for (usize j = 0; j < longest+1-d.data[i].name.len; j++)
+			print_char(' ');
+		if (d.data[i].is_dir) {
+			print_dec(d.data[i].children);
+			print(S(" files"));
+		}
+		print_char('\n');
+		free(d.data[i].name.data);
+	}
+
+	if (d.data != nil)
+		free(d.data);
+}
+
 typedef struct {
 	str name;
 	void (*fn)(str arg);
@@ -185,6 +237,7 @@ static command registry[] = {
 	{ S("clear"),    &cmd_clear    },
 	{ S("love"),     &cmd_love     },
 	{ S("uname"),    &cmd_uname    },
+	{ S("ls"),       &cmd_ls       },
 };
 
 void shell_run_cmd(str cmd)
@@ -194,7 +247,7 @@ void shell_run_cmd(str cmd)
 	if (prog.len == 0)
 		return;
 
-	for (usize i = 0; i < sizeof registry / sizeof *registry; i++) {
+	for (usize i = 0; i < LEN(registry); i++) {
 		if (str_cmp(prog, registry[i].name) == 0) {
 			registry[i].fn(cmd);
 			return;
diff --git a/stage3/string.c b/stage3/string.c
index 836f6a3..5669483 100644
--- a/stage3/string.c
+++ b/stage3/string.c
@@ -91,3 +91,18 @@ bool str_start(str s, str start)
 	s.len = start.len;
 	return str_cmp(s, start) == 0;
 }
+
+str str_intro(char *c)
+{
+	usize i = 0;
+	while (c[i] != '\0')
+		i++;
+	return (str) { i, c };
+}
+
+str str_clone(str s)
+{
+	str c = { s.len, malloc(s.len) };
+	memcpy(c.data, s.data, s.len);
+	return c;
+}
diff --git a/stage3/string.h b/stage3/string.h
index fc91522..1a28494 100644
--- a/stage3/string.h
+++ b/stage3/string.h
@@ -3,12 +3,43 @@
 
 #include "def.h"
 
+// compares two strings by length and ASCII values. return value:
+//   < 0 if s1 < s2
+//   = 0 if s1 = s2
+//   > 0 if s1 > s2
 isize str_cmp(str s1, str s2);
+
+// returns index of first of occurrence in s of any of the chars in tokens
+// returns length of s if not found
 usize str_find(str s, str tokens);
+
+// parses a number in base base and returns number of chars processed
+// resulting number is stored in *x
 usize str_parse_num(str s, u8 base, u64 *x);
+
+// this is a splitting function
+// returns the next non-empty substring of *s that is delimited by the tokens in sep
+// the returned string does not contain any of the separators
+// returns an emtpy string when end is reached
+// advances s to after the substring plus first delimiting token
 str str_walk(str *s, str sep);
+
+// advances the string while its first token matches any of the chars in tokens
+// this can be used to consume whitespace, for example
 str str_eat(str s, str tokens);
+
+// advances the string s by x chars, increasing the data pointer and decreasing the length
+// note: this is not bounds checked
 str str_advance(str s, usize x);
+
+// returns true if s starts with start
 bool str_start(str s, str start);
 
+// construct a str from a \0 terminated string at runtime
+// avoid this for literals: use the S macro from def.h instead without a runtime cost
+str str_intro(char *c);
+
+// copy a string to the heap
+str str_clone(str s);
+
 #endif