code wiki / _hdl_build / nx_huffcdic.nx
nx_huffcdic.nx source
↩ module page · 128 lines · 6297 B
1// nx_huffcdic.nx -- SOVEREIGN HUFF/CDIC decompressor for MOBI/AZW (compression type 17480), the Nishi capability
2// equivalent of Calibre's huffcdic reference. CLEAN-ROOM: written from the documented algorithm (HUFF/CDIC record
3// layout + the 32-bit Huffman-window decode), NOT copied -- pure NishiLang (nx_cc -> nxasm_x86, no python/gcc/sh).
4// Newer Kindle books use HUFF/CDIC instead of PalmDOC; nx_mobi_book currently handles 1/2 (none/PalmDOC) only.
5//
6// HUFF record: "HUFF\x00\x00\x00\x18" | off1(u32) | off2(u32) | dict1[256]u32 (at off1) | dict2[64]u32 (at off2)
7// dict1 entry v: codelen = v&0x1f ; term = v&0x80 ; maxcode = ((v>>8)+1 << (32-codelen)) - 1
8// dict2: 32 (mincode,maxcode) pairs -> mincode[cl] = raw<<(32-cl) ; maxcode[cl] = ((raw+1)<<(32-cl))-1, cl=1..32
9// CDIC record: "CDIC\x00\x00\x00\x10" | phrases(u32) | bits(u32) | u16 offset table -> phrases
10// phrase j: off = be16(16+j*2) ; blen = be16(16+off) ; bytes = [18+off .. 18+off+(blen&0x7fff)) ; flag = blen&0x8000
11// unpack: 32-bit window; codelen/term/maxcode = dict1[code>>24]; if !term walk mincode[] up; r=(maxcode-code)>>(32-codelen)
12// is the dictionary index; a non-terminal phrase is itself a compressed slice -> recurse, then cache as terminal.
13// NXASM-SAFE: be64 builds the u64 via a <<8 loop (immediate shifts >=32 are mis-encoded); every <<(32-cl) is a
14// VARIABLE (register) shift, which x86 SHR/SHL handle correctly. license_tier: ORIGINAL
15import "nx_syscalls.nx"
16const K_MAGIC_65536: i64 = 65536
17
18func hc_be16(b: *u8, o: i64) -> i64 { return ((b[o] as i64)<<8)|(b[o+1] as i64) }
19func hc_be32(b: *u8, o: i64) -> i64 { return ((b[o] as i64)<<24)|((b[o+1] as i64)<<16)|((b[o+2] as i64)<<8)|(b[o+3] as i64) }
20func hc_be64(b: *u8, o: i64) -> i64 { var v: i64=0; var i: i64=0; while i<8 { v=(v<<8)|(b[o+i] as i64); i=i+1 } return v }
21
22// parse a HUFF record -> the dict1 (codelen/term/maxcode) + mincode/maxcode tables. arrays caller-allocated:
23// d1cl/d1tm/d1mx: >=256 ; mincode/maxcode: >=64 (indexed by code length 0..32). ret 0 ok / negative on bad input.
24func huff_load(huff: *u8, hlen: i64, d1cl: *i64, d1tm: *i64, d1mx: *i64, mincode: *i64, maxcode: *i64) -> i64 {
25 if hlen < 16 { return 0-1 }
26 if huff[0]!=(0x48 as u8) { return 0-1 }
27 if huff[1]!=(0x55 as u8) { return 0-1 }
28 if huff[2]!=(0x46 as u8) { return 0-1 }
29 if huff[3]!=(0x46 as u8) { return 0-1 }
30 if huff[7]!=(0x18 as u8) { return 0-1 }
31 let off1: i64 = hc_be32(huff, 8)
32 let off2: i64 = hc_be32(huff, 12)
33 var i: i64 = 0
34 while i < 256 {
35 let v: i64 = hc_be32(huff, off1 + i*4)
36 let cl: i64 = v & 0x1f
37 if cl == 0 { return 0-2 }
38 d1cl[i] = cl
39 d1tm[i] = v & 0x80
40 d1mx[i] = (((v >> 8) + 1) << (32 - cl)) - 1
41 i = i + 1
42 }
43 mincode[0] = 0
44 maxcode[0] = 0xffffffff
45 var cl: i64 = 1
46 while cl <= 32 {
47 let mnr: i64 = hc_be32(huff, off2 + (2*(cl-1))*4)
48 let mxr: i64 = hc_be32(huff, off2 + (2*(cl-1)+1)*4)
49 mincode[cl] = mnr << (32 - cl)
50 maxcode[cl] = ((mxr + 1) << (32 - cl)) - 1
51 cl = cl + 1
52 }
53 return 0
54}
55
56// parse a CDIC record, APPENDING its phrases to the dictionary (dptr/dlen/dflag, caller-allocated; dcount in/out).
57// phrase bytes are referenced IN PLACE (dptr = pointer into the cdic buffer) until they are recursively expanded.
58func cdic_load(cdic: *u8, clen: i64, dptr: *i64, dlen: *i64, dflag: *i64, dcount: *i64) -> i64 {
59 if clen < 16 { return 0-1 }
60 if cdic[0]!=(0x43 as u8) { return 0-1 }
61 if cdic[1]!=(0x44 as u8) { return 0-1 }
62 if cdic[2]!=(0x49 as u8) { return 0-1 }
63 if cdic[3]!=(0x43 as u8) { return 0-1 }
64 if cdic[7]!=(0x10 as u8) { return 0-1 }
65 let phrases: i64 = hc_be32(cdic, 8)
66 let bits: i64 = hc_be32(cdic, 12)
67 var n: i64 = 1 << bits
68 let rem: i64 = phrases - dcount[0]
69 if n > rem { n = rem }
70 if n < 0 { n = 0 }
71 var j: i64 = 0
72 while j < n {
73 let off: i64 = hc_be16(cdic, 16 + j*2)
74 let blen: i64 = hc_be16(cdic, 16 + off)
75 let idx: i64 = dcount[0]
76 dptr[idx] = (cdic as i64) + 18 + off
77 dlen[idx] = blen & 0x7fff
78 if (blen & 0x8000) != 0 { dflag[idx] = 1 } else { dflag[idx] = 0 }
79 dcount[0] = idx + 1
80 j = j + 1
81 }
82 return 0
83}
84
85// decode `data` (datalen bytes) into ob (cap obcap) using the loaded tables. recursive: a non-terminal phrase is a
86// compressed slice that is itself unpacked then cached terminal. returns the number of output bytes written.
87func hc_unpack(data: *u8, datalen: i64, ob: *u8, obcap: i64, d1cl: *i64, d1tm: *i64, d1mx: *i64, mincode: *i64, maxcode: *i64, dptr: *i64, dlen: *i64, dflag: *i64, dcount: i64) -> i64 {
88 let buf: *u8 = sys_mmap(datalen + 16)
89 var i: i64 = 0
90 while i < datalen { buf[i] = data[i]; i = i + 1 }
91 while i < datalen + 8 { buf[i] = 0 as u8; i = i + 1 }
92 var bitsleft: i64 = datalen * 8
93 var pos: i64 = 0
94 var x: i64 = hc_be64(buf, pos)
95 var n: i64 = 32
96 var op: i64 = 0
97 var go: i64 = 1
98 while go == 1 {
99 if n <= 0 { pos = pos + 4; x = hc_be64(buf, pos); n = n + 32 }
100 let code: i64 = (x >> n) & 0xffffffff
101 let top: i64 = (code >> 24) & 0xff
102 var codelen: i64 = d1cl[top]
103 var mx: i64 = d1mx[top]
104 if d1tm[top] == 0 {
105 while codelen <= 32 { if code < mincode[codelen] { codelen = codelen + 1 } else { break } }
106 mx = maxcode[codelen]
107 }
108 n = n - codelen
109 bitsleft = bitsleft - codelen
110 if bitsleft < 0 { go = 0 } else {
111 let r: i64 = (mx - code) >> (32 - codelen)
112 if r < 0 { go = 0 } else { if r >= dcount { go = 0 } else {
113 if dflag[r] == 0 {
114 let tmp: *u8 = sys_mmap(K_MAGIC_65536)
115 let tl: i64 = hc_unpack(dptr[r] as *u8, dlen[r], tmp, K_MAGIC_65536, d1cl, d1tm, d1mx, mincode, maxcode, dptr, dlen, dflag, dcount)
116 dptr[r] = tmp as i64
117 dlen[r] = tl
118 dflag[r] = 1
119 }
120 let sp: *u8 = dptr[r] as *u8
121 let sl: i64 = dlen[r]
122 var k: i64 = 0
123 while k < sl { if op < obcap { ob[op] = sp[k] } op = op + 1; k = k + 1 }
124 } }
125 }
126 }
127 return op
128}