`nx_author.nx` source

1// nx_author.nx -- the team AUTHORS a new technique from its own diagnosis, by EXPERIMENT.
2// Last loops the team diagnosed "the competitor used a mnemonic I lack: imul" and I had to
3// tell it (or pre-stock) what imul does. This removes me: the team LEARNS the instruction's
4// semantics itself. It emits the instruction (in the form it observed in the competitor's
5// objdump: `imulq $K, %rdi, %rax`), RUNS it on several (K,x) probes, observes the outputs,
6// and INFERS which operation it computes by testing hypotheses {mul,add,sub,xor,and,or,shl}
7// against the observed input->output pairs. The hypothesis that matches ALL probes is the
8// learned semantics. Discovery by experiment -- the team teaches ITSELF a new primitive.
9// license_tier: ORIGINAL
10
11import "nx_engineer_crash.nx"   // eng_link + eng_run (emit -> assemble -> run -> observe)
12import "nx_superopt_emit.nx"    // se_str + se_num (emit the probe asm)
13const AU_MAGIC_1024: i64 = 1024
14
15const AU_MUL: i64 = 0
16const AU_ADD: i64 = 1
17const AU_SUB: i64 = 2
18const AU_XOR: i64 = 3
19const AU_AND: i64 = 4
20const AU_OR:  i64 = 5
21const AU_SHL: i64 = 6
22const AU_NONE: i64 = 0 - 1
23
24func au_name(op: i64) -> *u8 {
25    if op == AU_MUL { return "MULTIPLY (x*K)" as *u8 }
26    if op == AU_ADD { return "ADD (x+K)" as *u8 }
27    if op == AU_SUB { return "SUB (x-K)" as *u8 }
28    if op == AU_XOR { return "XOR (x^K)" as *u8 }
29    if op == AU_AND { return "AND (x&K)" as *u8 }
30    if op == AU_OR  { return "OR (x|K)" as *u8 }
31    if op == AU_SHL { return "SHIFT (x<<K)" as *u8 }
32    return "UNKNOWN" as *u8
33}
34
35// emit a probe: synth applies the observed instruction form to x; _start exits with the
36// low byte of synth(x). (Here the form learned from the diagnosis is `imulq $K,%rdi,%rax`.)
37func au_emit_probe(mnem: *u8, K: i64, x: i64, buf: *u8) -> i64 {
38    var oi: i64 = 0
39    oi = se_str(buf, oi, "	.att_syntax prefix\n	.text\n	.globl _start\n_start:\n	movabsq $" as *u8)
40    oi = se_num(buf, oi, x)
41    oi = se_str(buf, oi, ", %rdi\n	call synth\n	andq $255, %rax\n	movq %rax, %rdi\n	movabsq $60, %rax\n	syscall\nsynth:\n	" as *u8)
42    oi = se_str(buf, oi, mnem); oi = se_str(buf, oi, " $" as *u8); oi = se_num(buf, oi, K)
43    oi = se_str(buf, oi, ", %rdi, %rax\n	ret\n" as *u8)
44    return oi
45}
46
47// run one probe: emit the instruction with (K,x), assemble, run, return the observed low byte.
48func au_observe(mnem: *u8, K: i64, x: i64) -> i64 {
49    let buf: *u8 = sys_mmap(AU_MAGIC_1024)
50    let blen: i64 = au_emit_probe(mnem, K, x, buf)
51    let fd: i64 = sys_openat_wr("/tmp/au.s" as *u8, 0x1a4)
52    if fd < 0 { return 0 - 2 }
53    sys_write(fd, buf, blen); sys_close(fd)
54    if eng_link("/tmp/au.s" as *u8, "/tmp/au.elf" as *u8) != 0 { return 0 - 2 }
55    return eng_run("/tmp/au.elf" as *u8, 0 as *u8)
56}
57
58// what each hypothesis predicts for (x,K), masked to the observed low byte.
59func au_predict(op: i64, x: i64, K: i64) -> i64 {
60    if op == AU_MUL { return (x * K) & 255 }
61    if op == AU_ADD { return (x + K) & 255 }
62    if op == AU_SUB { return (x - K) & 255 }
63    if op == AU_XOR { return (x ^ K) & 255 }
64    if op == AU_AND { return (x & K) & 255 }
65    if op == AU_OR  { return (x | K) & 255 }
66    if op == AU_SHL { return (x << K) & 255 }
67    return 0 - 1
68}
69
70// LEARN the instruction's semantics by experiment: probe N (K,x) pairs, then return the one
71// hypothesis whose prediction matches EVERY observation. AU_NONE if nothing matches.
72func au_learn(mnem: *u8, Ks: *i64, Xs: *i64, n: i64, obs: *i64) -> i64 {
73    var i: i64 = 0
74    while i < n { obs[i] = au_observe(mnem, Ks[i], Xs[i]); i = i + 1 }
75    var op: i64 = 0
76    while op < 7 {
77        var ok: i64 = 1
78        var j: i64 = 0
79        while j < n { if au_predict(op, Xs[j], Ks[j]) != obs[j] { ok = 0 } j = j + 1 }
80        if ok == 1 { return op }
81        op = op + 1
82    }
83    return AU_NONE
84}
nx_author.nx source

`nx_author.nx` source
