nx_huffman_kat.nx source

1// nx_huffman_kat.nx -- KAT for nx_huffman (canonical Huffman build + decode; the DEFLATE symbol layer). 2// HONESTY [W] weak point (reach=122; the in-file main self-tests via return-codes but no external node). 3// Formalizes the canonical-build KAT (RFC-1951 canonical code assignment for lengths [2,1,3,3]) and adds a 4// DECODE ROUNDTRIP the demo lacked: pack canonical codes MSB-first, decode them back to the symbols. 5// license_tier: ORIGINAL expect_exit:0 6import "nx_syscalls.nx" 7import "nx_bitio.nx" 8import "nx_bitstream.nx" 9import "nx_huffman.nx" 10 11func hw(s: *u8) -> i64 { var n:i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } 12func hn(v: i64) -> i64 { let b:*u8=sys_mmap(24); var m:i64=v; if m<0{sys_write(1,"-" as *u8,1);m=0-m} let t:*u8=sys_mmap(24); var k:i64=0; if m==0{t[0]=48 as u8;k=1} while m>0{t[k]=(48+(m%10)) as u8;m=m/10;k=k+1} var j:i64=0; while j<k{b[j]=t[k-1-j];j=j+1} sys_write(1,b,k); return 0 } 13 14func main() -> i64 { 15 var pass: i64 = 0 16 17 // canonical table for lengths [2,1,3,3] -> codes sym1=0, sym0=10, sym2=110, sym3=111 18 let lens: *nx_int = sys_mmap(64) as *nx_int 19 lens[0] = 2; lens[1] = 1; lens[2] = 3; lens[3] = 3 20 let t: *NxHuffmanTable = nx_huffman_build(lens, 4) 21 if (t as i64) == 0 { hw("build failed\nNX-HUFFMAN-KAT 0/6 RED\n" as *u8); return 1 } 22 23 // T1: shape 24 if t.n_symbols == 4 { if t.max_length == 3 { pass = pass + 1; hw("T1 shape PASS\n" as *u8) } else { hw("T1 FAIL max_len\n" as *u8) } } else { hw("T1 FAIL n_sym\n" as *u8) } 25 26 // T2: per-length counts 27 if t.count[1] == 1 { if t.count[2] == 1 { if t.count[3] == 2 { pass = pass + 1; hw("T2 counts PASS\n" as *u8) } else { hw("T2 FAIL c3\n" as *u8) } } else { hw("T2 FAIL c2\n" as *u8) } } else { hw("T2 FAIL c1\n" as *u8) } 28 29 // T3: canonical first_code (0, (0+1)*2=2, (2+1)*2=6) 30 if t.first_code[1] == 0 { if t.first_code[2] == 2 { if t.first_code[3] == 6 { pass = pass + 1; hw("T3 first_code canonical PASS\n" as *u8) } else { hw("T3 FAIL fc3\n" as *u8) } } else { hw("T3 FAIL fc2\n" as *u8) } } else { hw("T3 FAIL fc1\n" as *u8) } 31 32 // T4: symbol_table sorted by (length,symbol): [1,0,2,3] 33 if t.symbol_table[0] == 1 { if t.symbol_table[1] == 0 { if t.symbol_table[2] == 2 { if t.symbol_table[3] == 3 { pass = pass + 1; hw("T4 symtab sorted PASS\n" as *u8) } else { hw("T4 FAIL s3\n" as *u8) } } else { hw("T4 FAIL s2\n" as *u8) } } else { hw("T4 FAIL s1\n" as *u8) } } else { hw("T4 FAIL s0\n" as *u8) } 34 35 // T5: DECODE ROUNDTRIP -- pack codes MSB-first (sym1=0, sym0=10, sym2=110, sym3=111) then decode 36 let buf: *u8 = sys_mmap(16) 37 var i: i64 = 0; while i < 16 { buf[i] = 0 as u8; i = i + 1 } 38 var bp: i64 = 0 39 bp = nx_bw_put(buf, bp, 0, 1) // sym1 code 0 40 bp = nx_bw_put(buf, bp, 2, 2) // sym0 code 10 41 bp = nx_bw_put(buf, bp, 6, 3) // sym2 code 110 42 bp = nx_bw_put(buf, bp, 7, 3) // sym3 code 111 43 let bs: *NxBitStream = nx_bitstream_alloc(buf, 4) 44 let d0: i64 = nx_huffman_decode_msb(t, bs) 45 let d1: i64 = nx_huffman_decode_msb(t, bs) 46 let d2: i64 = nx_huffman_decode_msb(t, bs) 47 let d3: i64 = nx_huffman_decode_msb(t, bs) 48 if d0 == 1 { if d1 == 0 { if d2 == 2 { if d3 == 3 { pass = pass + 1; hw("T5 decode roundtrip [1,0,2,3] PASS\n" as *u8) } else { hw("T5 FAIL d3=" as *u8); hn(d3); hw("\n" as *u8) } } else { hw("T5 FAIL d2=" as *u8); hn(d2); hw("\n" as *u8) } } else { hw("T5 FAIL d1=" as *u8); hn(d1); hw("\n" as *u8) } } else { hw("T5 FAIL d0=" as *u8); hn(d0); hw("\n" as *u8) } 49 50 // T6: 2-symbol table [1,1] -> codes 0,1 ; decode '0'->0, '1'->1 51 let l2: *nx_int = sys_mmap(32) as *nx_int 52 l2[0] = 1; l2[1] = 1 53 let t2: *NxHuffmanTable = nx_huffman_build(l2, 2) 54 let b2: *u8 = sys_mmap(8); b2[0] = 0 as u8 55 nx_bw_put(b2, 0, 0, 1) // code 0 -> sym0 56 nx_bw_put(b2, 1, 1, 1) // code 1 -> sym1 57 let bs2: *NxBitStream = nx_bitstream_alloc(b2, 1) 58 let e0: i64 = nx_huffman_decode_msb(t2, bs2) 59 let e1: i64 = nx_huffman_decode_msb(t2, bs2) 60 if e0 == 0 { if e1 == 1 { pass = pass + 1; hw("T6 2-sym decode PASS\n" as *u8) } else { hw("T6 FAIL e1=" as *u8); hn(e1); hw("\n" as *u8) } } else { hw("T6 FAIL e0=" as *u8); hn(e0); hw("\n" as *u8) } 61 62 hw("NX-HUFFMAN-KAT " as *u8); hn(pass); hw("/6" as *u8) 63 if pass == 6 { hw(" GREEN\n" as *u8); return 0 } 64 hw(" RED\n" as *u8) 65 return 1 66}