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.

7 files changed, 500 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 3f07ec2..123f924 100644
--- a/Makefile
+++ b/Makefile
@@ -30,7 +30,9 @@ PROGS  := chello echo true false uname pid cat wc head args \
           wget chat netd ping nslookup dhcp irc uptime ansi \
           grep more cp nc httpd ircd \
           df mv sleep tee tail help poweroff xxd \
-          touch tr rev cut uniq
+          touch tr rev cut uniq \
+          sort cmp strings du time clear ln \
+          ntpdate date
 CBLOBS := $(patsubst %,$(BUILD)/usr/%.bin,$(PROGS))
 $(BUILD)/programs.o: $(CBLOBS)
 
diff --git a/src/programs.asm b/src/programs.asm
index e9e1be9..96229f4 100644
--- a/src/programs.asm
+++ b/src/programs.asm
@@ -196,6 +196,33 @@ ProgCut:
 SECTION "prog_uniq",   ROMX[$4000], BANK[53]
 ProgUniq:
     INCBIN "build/usr/uniq.bin"
+SECTION "prog_sort",    ROMX[$4000], BANK[54]
+ProgSort:
+    INCBIN "build/usr/sort.bin"
+SECTION "prog_cmp",     ROMX[$4000], BANK[55]
+ProgCmp:
+    INCBIN "build/usr/cmp.bin"
+SECTION "prog_strings", ROMX[$4000], BANK[56]
+ProgStrings:
+    INCBIN "build/usr/strings.bin"
+SECTION "prog_du",      ROMX[$4000], BANK[57]
+ProgDu:
+    INCBIN "build/usr/du.bin"
+SECTION "prog_time",    ROMX[$4000], BANK[58]
+ProgTime:
+    INCBIN "build/usr/time.bin"
+SECTION "prog_clear",   ROMX[$4000], BANK[59]
+ProgClear:
+    INCBIN "build/usr/clear.bin"
+SECTION "prog_ln",      ROMX[$4000], BANK[60]
+ProgLn:
+    INCBIN "build/usr/ln.bin"
+SECTION "prog_ntpdate", ROMX[$4000], BANK[61]
+ProgNtpdate:
+    INCBIN "build/usr/ntpdate.bin"
+SECTION "prog_date",    ROMX[$4000], BANK[62]
+ProgDate:
+    INCBIN "build/usr/date.bin"
 
 ; -----------------------------------------------------------------------------
 ; PROG_SH (bank 3) - the shell, now written in C (usr/sh.c): parses >/</| and
@@ -342,6 +369,24 @@ ProgramTable::
     dw ProgCut
     db LOW(BANK(ProgUniq)), HIGH(BANK(ProgUniq))
     dw ProgUniq
+    db LOW(BANK(ProgSort)), HIGH(BANK(ProgSort))
+    dw ProgSort
+    db LOW(BANK(ProgCmp)), HIGH(BANK(ProgCmp))
+    dw ProgCmp
+    db LOW(BANK(ProgStrings)), HIGH(BANK(ProgStrings))
+    dw ProgStrings
+    db LOW(BANK(ProgDu)), HIGH(BANK(ProgDu))
+    dw ProgDu
+    db LOW(BANK(ProgTime)), HIGH(BANK(ProgTime))
+    dw ProgTime
+    db LOW(BANK(ProgClear)), HIGH(BANK(ProgClear))
+    dw ProgClear
+    db LOW(BANK(ProgLn)), HIGH(BANK(ProgLn))
+    dw ProgLn
+    db LOW(BANK(ProgNtpdate)), HIGH(BANK(ProgNtpdate))
+    dw ProgNtpdate
+    db LOW(BANK(ProgDate)), HIGH(BANK(ProgDate))
+    dw ProgDate
 ProgramTableEnd::
 
 ; -----------------------------------------------------------------------------
@@ -453,4 +498,22 @@ NameTable::
     db PROG_CUT
     db "uniq", 0
     db PROG_UNIQ
+    db "sort", 0
+    db PROG_SORT
+    db "cmp", 0
+    db PROG_CMP
+    db "strings", 0
+    db PROG_STRINGS
+    db "du", 0
+    db PROG_DU
+    db "time", 0
+    db PROG_TIME
+    db "clear", 0
+    db PROG_CLEAR
+    db "ln", 0
+    db PROG_LN
+    db "ntpdate", 0
+    db PROG_NTPDATE
+    db "date", 0
+    db PROG_DATE
     db 0
diff --git a/usr/cmp.c b/usr/cmp.c
new file mode 100644
index 0000000..5a4a718
--- /dev/null
+++ b/usr/cmp.c
@@ -0,0 +1,61 @@
+#include "gbos.h"
+/* cmp FILE1 FILE2: report the first byte where two files differ, or say
+ * nothing when they match (like cmp(1), silence means identical).
+ *
+ * After cp/mv/tee/nc there was still no way to check a copy ON the machine -
+ * you had to haul both files to a host. */
+void main(void) {
+    char *argv[4];
+    unsigned char argc = argv_parse(argv, 4);
+    unsigned char a, b;
+    unsigned int off = 0;
+    int ca, cb;
+
+    if (argc < 2) {
+        puts("usage: cmp FILE1 FILE2");
+        nl();
+        sexit(2);
+    }
+    a = open(argv[0], O_READ);
+    if (a > 3) {
+        puts("cmp: cannot open ");
+        puts(argv[0]);
+        nl();
+        sexit(2);
+    }
+    b = open(argv[1], O_READ);
+    if (b > 3) {
+        puts("cmp: cannot open ");
+        puts(argv[1]);
+        nl();
+        close(a);
+        sexit(2);
+    }
+
+    for (;;) {
+        ca = fgetc(a);
+        cb = fgetc(b);
+        if (ca < 0 && cb < 0) break; /* same length, same bytes */
+        if (ca < 0 || cb < 0) {
+            puts("cmp: EOF on ");
+            puts(ca < 0 ? argv[0] : argv[1]);
+            puts(" after ");
+            putu(off);
+            nl();
+            close(a);
+            close(b);
+            sexit(1);
+        }
+        if (ca != cb) {
+            puts("differ: byte ");
+            putu(off);
+            nl();
+            close(a);
+            close(b);
+            sexit(1);
+        }
+        off++;
+    }
+    close(a);
+    close(b);
+}
diff --git a/usr/du.c b/usr/du.c
new file mode 100644
index 0000000..2667159
--- /dev/null
+++ b/usr/du.c
@@ -0,0 +1,85 @@
+#include "stat.h"
+/* du [dir]: disk usage per entry, and a total, in 256-byte blocks.
+ *
+ * Blocks, not bytes, for two reasons: it is the unit df(1) and the filesystem
+ * itself use, and bytes overflow - /bin alone is 52 programs x 16 KiB, which
+ * wraps a 16-bit counter (it printed 32768).
+ *
+ * Recurses by re-opendir'ing: the kernel keeps ONE "directory being listed"
+ * (wListDir), so walking into a child loses the parent's cursor - the parent
+ * has to be re-opened and re-indexed on the way back up. With 32 inodes and
+ * shallow trees that costs nothing. */
+
+#define MAXDEPTH 3
+
+static unsigned int total; /* 256-byte blocks */
+
+static void pad(unsigned int n, unsigned char w) {
+    unsigned char d = 1;
+    unsigned int v = n;
+    while (v >= 10) {
+        v = v / 10;
+        d++;
+    }
+    while (d++ < w) putc(' ');
+    putu(n);
+}
+
+/* sum one directory, printing each entry; returns its byte total */
+static unsigned int walk(char *path, unsigned char depth) {
+    char name[16];
+    char child[40];
+    struct gstat st;
+    unsigned int sum = 0;
+    unsigned char i, j, k;
+
+    for (i = 0;; i++) {
+        if (opendir(path)) return sum; /* re-open: flist has one cursor */
+        if (!flist(i, name)) break;
+        name[15] = 0;
+        j = 0;
+        for (k = 0; path[k] && j < 30; k++) child[j++] = path[k];
+        if (j && child[j - 1] != '/') child[j++] = '/';
+        for (k = 0; name[k] && j < 38; k++) child[j++] = name[k];
+        child[j] = 0;
+        if (!gstat(child, &st)) continue;
+        if (st.type == ST_DIR && depth < MAXDEPTH) {
+            sum += walk(child, (unsigned char)(depth + 1));
+        } else {
+            {
+                unsigned int blk = (unsigned int)((st.size + 255) / 256);
+                sum += blk;
+                pad(blk, 6);
+            }
+            putc(' ');
+            puts(child);
+            nl();
+        }
+    }
+    pad(sum, 6);
+    putc(' ');
+    puts(path);
+    nl();
+    return sum;
+}
+
+void main(void) {
+    char dir[32];
+    char *argv[4];
+    unsigned char argc = argv_parse(argv, 4);
+    unsigned char i, j, have = 0;
+
+    /* copy the argument before gstat's static request block lands on $A000 */
+    for (i = 0; i < argc; i++)
+        if (argv[i][0] != '-') {
+            for (j = 0; argv[i][j] && j < 31; j++) dir[j] = argv[i][j];
+            dir[j] = 0;
+            have = 1;
+            break;
+        }
+    if (!have) {
+        dir[0] = '/';
+        dir[1] = 0;
+    }
+    total = walk(dir, 0);
+}
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();
+    }
+}
diff --git a/usr/strings.c b/usr/strings.c
new file mode 100644
index 0000000..b3db75d
--- /dev/null
+++ b/usr/strings.c
@@ -0,0 +1,60 @@
+#include "gbos.h"
+/* strings [-n N] [file]: print runs of N or more printable characters
+ * (default 4). Pairs with xxd now that /bin/<prog> is readable - it is how
+ * you find the text baked into a program image. */
+
+#define MAXRUN 64
+
+void main(void) {
+    char *argv[8];
+    char run[MAXRUN];
+    unsigned char argc = argv_parse(argv, 8);
+    char *nv = optval(argv, argc, 'n');
+    unsigned char min = nv ? atou(nv) : 4;
+    unsigned char len = 0, fd = NOFD, i;
+    char *fname = 0;
+    int ch;
+
+    if (min == 0) min = 4;
+    if (min > MAXRUN) min = MAXRUN;
+    for (i = 0; i < argc; i++) {
+        if (argv[i][0] == '-') continue;
+        if (nv == argv[i]) continue;
+        fname = argv[i];
+        break;
+    }
+    if (fname) {
+        fd = open(fname, O_READ);
+        if (fd == EISDIR) {
+            puts("strings: is a directory");
+            nl();
+            sexit(2);
+        }
+        if (fd == NOFD) {
+            puts("strings: no such file");
+            nl();
+            sexit(2);
+        }
+    }
+    for (;;) {
+        if (fd == NOFD) {
+            char c = readc();
+            ch = (c == EOF) ? -1 : c;
+        } else ch = fgetc(fd);
+        if (ch >= 32 && ch < 127) {
+            if (len < MAXRUN) run[len++] = (char)ch;
+            continue;
+        }
+        if (len >= min) {
+            writes(run, len);
+            nl();
+        } /* run ended: keep it? */
+        len = 0;
+        if (ch < 0) break;
+    }
+    if (len >= min) {
+        writes(run, len);
+        nl();
+    }
+    if (fd != NOFD) close(fd);
+}
diff --git a/usr/time.c b/usr/time.c
new file mode 100644
index 0000000..c97fb34
--- /dev/null
+++ b/usr/time.c
@@ -0,0 +1,94 @@
+#include "gbos.h"
+/* time CMD [ARGS]: run a command and report how long it took.
+ *
+ * Reads the kernel's 64 Hz tick before and after, so the resolution is 1/64s.
+ * The child's command line has to be rebuilt at $A000 ("cmd\0args\0", the
+ * shape usr/sh.c leaves) - which is also OUR argument area, so everything is
+ * copied to the stack first. */
+
+#define ARGV0 ((char *)0xA000)
+
+static void two(unsigned int v) {
+    if (v < 10) putc('0');
+    putu(v);
+}
+
+void main(void) {
+    char args[64];
+    char *cmd, *rest;
+    unsigned char t0[4], t1[4], id, i, j;
+    unsigned long ticks;
+    unsigned int sec, hund;
+    union {
+        unsigned long l;
+        unsigned char b[4];
+    } u;
+
+    {
+        char *a = getargs();
+        for (i = 0; a[i] && i < 63; i++) args[i] = a[i];
+        args[i] = 0;
+    }
+    if (!args[0]) {
+        puts("usage: time CMD [ARGS]");
+        nl();
+        sexit(2);
+    }
+
+    cmd = args; /* split "cmd rest..." */
+    i = 0;
+    while (args[i] && args[i] != ' ') i++;
+    rest = args + i;
+    if (args[i]) {
+        args[i] = 0;
+        rest = args + i + 1;
+    }
+
+    id = lookup(cmd);
+    if (id == NOFD) {
+        puts(cmd);
+        puts(": not found");
+        nl();
+        sexit(127);
+    }
+
+    gticks(t0);
+    {
+        char *p = ARGV0; /* rebuild the child's command line */
+        for (j = 0; cmd[j]; j++) *p++ = cmd[j];
+        *p++ = 0;
+        for (j = 0; rest[j]; j++) *p++ = rest[j];
+        *p = 0;
+    }
+    if (fork() == 0) exec(id);
+    wait();
+    gticks(t1);
+
+    /* elapsed ticks, 32-bit, little-endian - no long division (see uptime.c) */
+    u.b[0] = t1[0];
+    u.b[1] = t1[1];
+    u.b[2] = t1[2];
+    u.b[3] = t1[3];
+    ticks = u.l;
+    u.b[0] = t0[0];
+    u.b[1] = t0[1];
+    u.b[2] = t0[2];
+    u.b[3] = t0[3];
+    ticks -= u.l;
+
+    sec = 0;
+    while (ticks >= 64UL) {
+        ticks -= 64UL;
+        sec++;
+    }
+    hund = 0;                                                /* remaining ticks -> hundredths */
+    while (ticks--) hund += 2;                               /* 1/64 s ~ 0.0156 s ~ 1.56/100 */
+    hund = (unsigned int)(hund - (hund >> 2) - (hund >> 4)); /* ~x1.5625/2 */
+
+    puts("real ");
+    putu(sec);
+    putc('.');
+    two(hund > 99 ? 99 : hund);
+    puts("s");
+    nl();
+}