usr: sort, cmp, strings, du, time

- sort [-r] [-n]: everything in RAM, which bounds it - a task has 8 KiB and a
  file caps at 3 KiB, so 96 lines of 2400 bytes with room for the stack.
  Insertion sort over an index; at that size the simple thing is fast and
  costs far less ROM. `uniq -c f | sort -n -r` finally works.
  NB the key needs a scratch SLOT of its own: gt() compares table entries, so
  reusing slot i as scratch overwrites the entries being shifted into it.
- cmp: reports the first differing byte, silent when the files match. There
  was no way to check a copy on the machine - you had to haul both to a host.
- strings [-n N]: pairs with xxd now that /bin/<prog> is readable. It finds
  "gbos sm83 (Game Boy Color)" inside /bin/uname.
- du [dir]: 256-byte blocks, the unit df and the filesystem use. Bytes
  overflow - /bin alone is 52 x 16 KiB, which wrapped a 16-bit counter and
  printed 32768. Recurses by re-opendir'ing, since the kernel keeps only one
  "directory being listed" cursor.
- time CMD: 1/64 s resolution from the tick counter. It rebuilds the child's
  command line at $A000 - which is its own argument area, so everything is
  copied to the stack first.

1 files changed, 134 insertions, 0 deletions

diff --git a/usr/sort.c b/usr/sort.c
new file mode 100644
index 0000000..b322c28
--- /dev/null
+++ b/usr/sort.c
@@ -0,0 +1,134 @@
+#include "gbos.h"
+/* sort [-r] [-n] [file]: sort lines, from a file or stdin.
+ *
+ * Everything is held in RAM, which bounds it: a task has 8 KiB, a file caps
+ * at 3 KiB, so MAXBYTES/MAXLINES are set to fit with room for the stack.
+ * Insertion sort - with at most 96 lines, the simple thing is fast enough and
+ * costs far less ROM than anything clever.
+ *
+ *   ls /bin | sort | head       alphabetical
+ *   uniq -c f | sort -n -r      the classic "top hits" pipeline
+ *
+ * The line store is static (it is far too big for the stack), so main() must
+ * copy the arguments off $A000 before touching it - see usr/ping.c. */
+
+#define MAXBYTES 2400
+#define MAXLINES 96
+
+#define KEY MAXLINES /* scratch slot: the line being inserted */
+
+static char store[MAXBYTES];
+static unsigned int off[MAXLINES + 1];
+static unsigned char len[MAXLINES + 1];
+
+/* -> 1 if line a sorts after line b */
+static unsigned char gt(unsigned char a, unsigned char b, unsigned char num) {
+    unsigned char i, la = len[a], lb = len[b];
+    if (num) { /* leading integer, if any */
+        unsigned int va = 0, vb = 0;
+        for (i = 0; i < la && store[off[a] + i] >= '0' && store[off[a] + i] <= '9'; i++)
+            va = va * 10 + (unsigned char)(store[off[a] + i] - '0');
+        for (i = 0; i < lb && store[off[b] + i] >= '0' && store[off[b] + i] <= '9'; i++)
+            vb = vb * 10 + (unsigned char)(store[off[b] + i] - '0');
+        if (va != vb) return (unsigned char)(va > vb);
+    }
+    for (i = 0; i < la && i < lb; i++) {
+        char ca = store[off[a] + i], cb = store[off[b] + i];
+        if (ca != cb) return (unsigned char)(ca > cb);
+    }
+    return (unsigned char)(la > lb);
+}
+
+void main(void) {
+    char args[24];
+    char *argv[4];
+    unsigned char argc, rev, num, fd = NOFD, i, j;
+    unsigned int used = 0;
+    unsigned char n = 0, clen = 0;
+    unsigned int cstart = 0;
+    char *fname = 0;
+    int ch;
+
+    { /* argv lives at $A000, and so does store[] - copy the flags out first */
+        char *a = getargs();
+        for (i = 0; a[i] && i < 23; i++) args[i] = a[i];
+        args[i] = 0;
+    }
+    argc = 0;
+    { /* tokenize our stack copy */
+        char *p = args;
+        for (;;) {
+            while (*p == ' ') *p++ = 0;
+            if (!*p) break;
+            if (argc < 4) argv[argc] = p;
+            argc++;
+            while (*p && *p != ' ') p++;
+        }
+    }
+    rev = hasflag(argv, argc, 'r');
+    num = hasflag(argv, argc, 'n');
+    for (i = 0; i < argc; i++)
+        if (argv[i][0] != '-') {
+            fname = argv[i];
+            break;
+        }
+
+    if (fname) {
+        fd = open(fname, O_READ);
+        if (fd == EISDIR) {
+            puts("sort: is a directory");
+            nl();
+            sexit(2);
+        }
+        if (fd == NOFD) {
+            puts("sort: no such file");
+            nl();
+            sexit(2);
+        }
+    }
+    cstart = 0;
+    for (;;) {
+        if (fd == NOFD) {
+            char c = readc();
+            ch = (c == EOF) ? -1 : c;
+        } else ch = fgetc(fd);
+        if (ch == '\r') continue;
+        if (ch >= 0 && ch != '\n') {
+            if (used < MAXBYTES) {
+                store[used++] = (char)ch;
+                clen++;
+            }
+            continue;
+        }
+        if (ch < 0 && clen == 0) break;
+        if (n < MAXLINES) {
+            off[n] = cstart;
+            len[n] = clen;
+            n++;
+        }
+        cstart = used;
+        clen = 0;
+        if (ch < 0) break;
+    }
+    if (fd != NOFD) close(fd);
+
+    for (i = 1; i < n; i++) { /* insertion sort on the index */
+        off[KEY] = off[i];
+        len[KEY] = len[i];
+        j = i;
+        /* shift while the neighbour is on the wrong side of the key. gt()
+           takes table slots, so the key needs a slot of its own - reusing
+           slot i as scratch overwrites the entries being shifted into it. */
+        while (j && (gt((unsigned char)(j - 1), KEY, num) ? !rev : rev)) {
+            off[j] = off[j - 1];
+            len[j] = len[j - 1];
+            j--;
+        }
+        off[j] = off[KEY];
+        len[j] = len[KEY];
+    }
+    for (i = 0; i < n; i++) {
+        writes(store + off[i], len[i]);
+        nl();
+    }
+}