code wiki / _hdl_build / nx_boolsynth.nx
nx_boolsynth.nx source
↩ module page · 87 lines · 3639 B
1// nx_boolsynth.nx -- a NEW search space: minimal straight-line BOOLEAN circuits for a
2// 3-input function, where verification is EXACT and free. The trick: drive the inputs with
3// the truth-table columns a=0xAA, b=0xCC, c=0xF0 (the 8 bit positions enumerate all 8 input
4// combinations in parallel), so a program's output BYTE *is* its truth table. A candidate
5// matches the target iff (output & 0xFF) == target -- one word op covers ALL inputs, no
6// execution, no loop. Iterative deepening over op count gives the PROVABLY-MINIMAL circuit
7// over {AND, OR, XOR, NOT}. This is the class where exhaustive search can beat a heuristic
8// compiler (the compiler emits the literal expression; the superoptimizer finds the floor).
9// license_tier: ORIGINAL Refs: Knuth TAOCP 4A 7.1.2 (boolean evaluation); STOKE; souper.
10
11import "nx_syscalls.nx"
12
13const BL_AND: i64 = 0
14const BL_OR: i64 = 1
15const BL_XOR: i64 = 2
16const BL_NOT: i64 = 3 // unary: ~a
17
18// the three input columns (low byte enumerates all 8 combinations of a,b,c)
19const BL_A: i64 = 170 // 0xAA
20const BL_B: i64 = 204 // 0xCC
21const BL_C: i64 = 240 // 0xF0
22
23func bl_is_unary(op: i64) -> i64 { if op == BL_NOT { return 1 } return 0 }
24func bl_eval(op: i64, va: i64, vb: i64) -> i64 {
25 if op == BL_AND { return va & vb }
26 if op == BL_OR { return va | vb }
27 if op == BL_XOR { return va ^ vb }
28 return (0 - 1) ^ va // NOT (bitwise complement)
29}
30
31// recursive iterative-deepening enumeration. sv[] holds the magic-eval value per slot:
32// slot 0=a, 1=b, 2=c, op t writes slot t+3; operands range over all earlier slots 0..t+2.
33func bl_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, sv: *i64, target: i64) -> i64 {
34 if t == L { if (sv[L + 2] & 255) == target { return 1 } return 0 }
35 let nav: i64 = t + 3 // available operand slots: 0 .. t+2
36 let rslot: i64 = t + 3
37 var o: i64 = 0
38 while o < 4 {
39 if bl_is_unary(o) == 1 {
40 var i: i64 = 0
41 while i < nav {
42 sv[rslot] = bl_eval(o, sv[i], 0)
43 op[t] = o; a[t] = i; b[t] = i
44 if bl_enum(op, a, b, t + 1, L, sv, target) == 1 { return 1 }
45 i = i + 1
46 }
47 } else {
48 var i: i64 = 0
49 while i < nav {
50 var j: i64 = i // commutative ops: j >= i (dedup)
51 while j < nav {
52 sv[rslot] = bl_eval(o, sv[i], sv[j])
53 op[t] = o; a[t] = i; b[t] = j
54 if bl_enum(op, a, b, t + 1, L, sv, target) == 1 { return 1 }
55 j = j + 1
56 }
57 i = i + 1
58 }
59 }
60 o = o + 1
61 }
62 return 0
63}
64
65// find the SHORTEST boolean circuit for the 3-input truth table `target` (0..255). writes
66// op/a/b, returns op count L (1..maxL), or 0 if not found. Inputs occupy slots 0,1,2.
67func bl_find(target: i64, op: *i64, a: *i64, b: *i64, maxL: i64) -> i64 {
68 let sv: *i64 = sys_mmap(8 * (maxL + 6)) as *i64
69 sv[0] = BL_A; sv[1] = BL_B; sv[2] = BL_C
70 // L=0: is the target already one of the inputs (or constant)?
71 if (BL_A & 255) == target { return 0 }
72 if (BL_B & 255) == target { return 0 }
73 if (BL_C & 255) == target { return 0 }
74 var L: i64 = 1
75 while L <= maxL {
76 if bl_enum(op, a, b, 0, L, sv, target) == 1 { return L }
77 L = L + 1
78 }
79 return 0 - 1
80}
81
82func bl_opname(o: i64) -> *u8 {
83 if o == BL_AND { return "and" as *u8 }
84 if o == BL_OR { return "or" as *u8 }
85 if o == BL_XOR { return "xor" as *u8 }
86 return "not" as *u8
87}