nx_align_chain_test.nx source

1// nx_align_chain_test.nx -- KAT for the co-linear seed-chain DP. 2// 3// All vectors hand-verifiable from the DP recurrence in 4// nx_align_chain.nx. Tie-break = leftmost (first index reaching 5// the max chain length wins). 6// 7// expect_exit: 0 8// 9// license_tier: ORIGINAL 10 11import "nx_syscalls.nx" 12import "nx_align_chain.nx" 13 14func main() -> i64 { 15 16 let out: *i64 = sys_mmap(256) as *i64 17 18 // ============================================================ 19 // Section A -- degenerate n=0 returns chain length 0. 20 // ============================================================ 21 22 let q0: *i64 = sys_mmap(64) as *i64 23 let r0: *i64 = sys_mmap(64) as *i64 24 if seed_chain(q0, r0, 0, out, 16) != 0 { return 1 } 25 26 // ============================================================ 27 // Section B -- single seed -> chain length 1, index [0]. 28 // ============================================================ 29 30 let q1: *i64 = sys_mmap(64) as *i64 31 let r1: *i64 = sys_mmap(64) as *i64 32 q1[0] = 5; r1[0] = 10 33 let l1: i64 = seed_chain(q1, r1, 1, out, 16) 34 if l1 != 1 { return 5 } 35 if out[0] != 0 { return 6 } 36 37 // ============================================================ 38 // Section C -- two co-linear seeds -> length 2, indices [0, 1]. 39 // seeds: (q=2,r=10), (q=8,r=20) 40 // ============================================================ 41 42 let q2: *i64 = sys_mmap(64) as *i64 43 let r2: *i64 = sys_mmap(64) as *i64 44 q2[0] = 2; r2[0] = 10 45 q2[1] = 8; r2[1] = 20 46 let l2: i64 = seed_chain(q2, r2, 2, out, 16) 47 if l2 != 2 { return 10 } 48 if out[0] != 0 { return 11 } 49 if out[1] != 1 { return 12 } 50 51 // ============================================================ 52 // Section D -- two anti-co-linear seeds -> length 1, leftmost. 53 // seeds (sorted by r): (q=8,r=10), (q=2,r=20) 54 // q decreases between them -> can't chain together. 55 // Both have chain_len=1; leftmost-tie -> output index 0. 56 // ============================================================ 57 58 let q3: *i64 = sys_mmap(64) as *i64 59 let r3: *i64 = sys_mmap(64) as *i64 60 q3[0] = 8; r3[0] = 10 61 q3[1] = 2; r3[1] = 20 62 let l3: i64 = seed_chain(q3, r3, 2, out, 16) 63 if l3 != 1 { return 15 } 64 if out[0] != 0 { return 16 } 65 66 // ============================================================ 67 // Section E -- five consecutive co-linear seeds. 68 // seeds: (q=0,r=0)..(q=4,r=4) -> chain length 5, indices 0..4. 69 // ============================================================ 70 71 let q4: *i64 = sys_mmap(64) as *i64 72 let r4: *i64 = sys_mmap(64) as *i64 73 var i: i64 = 0 74 while i < 5 { 75 q4[i] = i 76 r4[i] = i 77 i = i + 1 78 } 79 let l4: i64 = seed_chain(q4, r4, 5, out, 16) 80 if l4 != 5 { return 20 } 81 var k: i64 = 0 82 while k < 5 { 83 if out[k] != k { return 21 + k } 84 k = k + 1 85 } 86 87 // ============================================================ 88 // Section F -- best chain "in the middle". 89 // seeds (sorted by r): 90 // 0: (q=0,r=0) 1: (q=5,r=1) 91 // 2: (q=1,r=2) 3: (q=2,r=3) 4: (q=3,r=4) 92 // Best chain: indices [0,2,3,4] (q goes 0->1->2->3, length 4). 93 // Index 1 (q=5) is an outlier that breaks the chain. 94 // ============================================================ 95 96 let q5: *i64 = sys_mmap(64) as *i64 97 let r5: *i64 = sys_mmap(64) as *i64 98 q5[0]=0; r5[0]=0 99 q5[1]=5; r5[1]=1 100 q5[2]=1; r5[2]=2 101 q5[3]=2; r5[3]=3 102 q5[4]=3; r5[4]=4 103 let l5: i64 = seed_chain(q5, r5, 5, out, 16) 104 if l5 != 4 { return 30 } 105 if out[0] != 0 { return 31 } 106 if out[1] != 2 { return 32 } 107 if out[2] != 3 { return 33 } 108 if out[3] != 4 { return 34 } 109 110 // ============================================================ 111 // Section G -- LIS-class multi-option case. 112 // seeds (sorted by r): 113 // 0: (q=3,r=1) 1: (q=1,r=2) 114 // 2: (q=4,r=3) 3: (q=2,r=4) 4: (q=5,r=5) 115 // Multiple length-3 chains possible. Leftmost-tie DP picks: 116 // chain_len: [1, 1, 2, 2, 3] parents: [-1, -1, 0, 1, 2] 117 // Backtrace from 4: 4 -> 2 -> 0. Output q-increasing: [0,2,4]. 118 // ============================================================ 119 120 let q6: *i64 = sys_mmap(64) as *i64 121 let r6: *i64 = sys_mmap(64) as *i64 122 q6[0]=3; r6[0]=1 123 q6[1]=1; r6[1]=2 124 q6[2]=4; r6[2]=3 125 q6[3]=2; r6[3]=4 126 q6[4]=5; r6[4]=5 127 let l6: i64 = seed_chain(q6, r6, 5, out, 16) 128 if l6 != 3 { return 40 } 129 if out[0] != 0 { return 41 } 130 if out[1] != 2 { return 42 } 131 if out[2] != 4 { return 43 } 132 133 // ============================================================ 134 // Section H -- all-equal q-values cannot chain. 135 // Each chain_len = 1; leftmost-tie -> output [0]. 136 // ============================================================ 137 138 let q7: *i64 = sys_mmap(64) as *i64 139 let r7: *i64 = sys_mmap(64) as *i64 140 q7[0]=5; r7[0]=0 141 q7[1]=5; r7[1]=1 142 q7[2]=5; r7[2]=2 143 let l7: i64 = seed_chain(q7, r7, 3, out, 16) 144 if l7 != 1 { return 50 } 145 if out[0] != 0 { return 51 } 146 147 // ============================================================ 148 // Section I -- capacity overflow returns -1. 149 // ============================================================ 150 151 let l8: i64 = seed_chain(q4, r4, 5, out, 3) // chain length 5, capacity 3 152 if l8 != -1 { return 60 } 153 154 // ============================================================ 155 // Section J -- negative n returns -1. 156 // ============================================================ 157 158 if seed_chain(q4, r4, -1, out, 16) != -1 { return 70 } 159 160 return 0 161}