code wiki / _hdl_build / nx_boolsynth4.nx
nx_boolsynth4.nx source
↩ module page · 79 lines · 3374 B
1// nx_boolsynth4.nx -- L8 gate-level synthesis, 4-input (extends the team's proven 3-input superopt up
2// the hardware rung). The team AUTHORS a minimal straight-line circuit for any 4-input boolean function
3// by SEARCH, and the result is verified EXACTLY and FREE by the truth-table-as-bitmask trick: drive the
4// four inputs with the columns 0xAAAA / 0xCCCC / 0xF0F0 / 0xFF00, and the 16-bit output word IS the
5// function's truth table -- so circuit==target is one integer compare, all 16 rows at once, no execution.
6// Gate count is a DETERMINISTIC counted invariant (nx_cost_oracle), so the win vs a naive sum-of-products
7// baseline is judged objectively, not by wall-clock or self-assessment.
8// Honest scope: the search is the chain class (each gate combines the running value with a PRIMARY input)
9// -- a real straight-line subclass that captures reduce/parity/threshold forms; the full DAG search +
10// real gcc/clang race (the existing 71-win 3-input standing) is the triangulation rung above this.
11// license_tier: ORIGINAL
12
13import "nx_cost_oracle.nx" // co_fair_verdict -- deterministic gate-count judging
14import "nx_syscalls.nx"
15
16// the k-th input column of the 4-input truth table (the bitmask-trick basis).
17func bs4_in(k: i64) -> i64 {
18 if k == 0 { return 0xAAAA }
19 if k == 1 { return 0xCCCC }
20 if k == 2 { return 0xF0F0 }
21 return 0xFF00
22}
23
24// a 2-input gate on 16-bit truth-table words (0=AND, 1=OR, 2=XOR), masked to 16 bits.
25func bs4_op(op: i64, a: i64, b: i64) -> i64 {
26 var r: i64 = 0
27 if op == 0 { r = a & b }
28 if op == 1 { r = a | b }
29 if op == 2 { r = a ^ b }
30 return r & 0xFFFF
31}
32
33// recursive minimal-chain search: from `cur`, applying one more gate (op x primary-input) toward target.
34// returns the fewest additional gates to reach target within the budget, or -1.
35func bs4_search(cur: i64, used: i64, target: i64, maxg: i64) -> i64 {
36 if cur == target { return used }
37 if used >= maxg { return 0 - 1 }
38 var best: i64 = 0 - 1
39 var op: i64 = 0
40 while op < 3 {
41 var inp: i64 = 0
42 while inp < 4 {
43 let nxt: i64 = bs4_op(op, cur, bs4_in(inp))
44 let res: i64 = bs4_search(nxt, used + 1, target, maxg)
45 if res >= 0 { if best < 0 { best = res } else { if res < best { best = res } } }
46 inp = inp + 1
47 }
48 op = op + 1
49 }
50 return best
51}
52
53// synthesize the MINIMAL chain gate count for a 4-input target truth table (-1 if not in the chain class).
54func bs4_synth(target: i64, maxg: i64) -> i64 {
55 var best: i64 = 0 - 1; var s: i64 = 0
56 while s < 4 {
57 let res: i64 = bs4_search(bs4_in(s), 0, target, maxg)
58 if res >= 0 { if best < 0 { best = res } else { if res < best { best = res } } }
59 s = s + 1
60 }
61 return best
62}
63
64// popcount of a 16-bit word (number of TRUE rows = minterms).
65func bs4_popcount(x: i64) -> i64 {
66 var c: i64 = 0; var i: i64 = 0
67 while i < 16 { if ((x >> i) & 1) == 1 { c = c + 1 } i = i + 1 }
68 return c
69}
70
71// the NAIVE sum-of-products gate count (the objective baseline a non-optimizing emitter produces):
72// M minterms, each a 4-literal product (3 AND gates), OR-ed together (M-1 OR gates).
73func bs4_naive_sop_gates(target: i64) -> i64 {
74 let m: i64 = bs4_popcount(target)
75 if m <= 0 { return 0 }
76 var g: i64 = m * 3
77 if m > 1 { g = g + (m - 1) }
78 return g
79}