code wiki / _hdl_build / nx_palmdoc.nx
nx_palmdoc.nx source
↩ module page · 84 lines · 3958 B
1// nx_palmdoc.nx -- Compresses and decompresses text using the PalmDOC LZ77 format for MOBI and AZW files.
2const K_MAGIC_2047: i64 = 2047
3// nx_palmdoc.nx -- SOVEREIGN PalmDOC (LZ77) codec, the text compression used by MOBI / AZW (Kindle) files.
4// Pure byte ops, no syscalls -> a reusable library (no main). Decompress is what the MOBI reader needs; compress
5// exists so the fixture builder can produce REAL PalmDOC-compressed records (round-trippable -> the gate proves
6// the decompressor against the actual on-disk encoding, not a hand-waved blob). Format (per the documented spec):
7// 0x00 -> literal 0x00
8// 0x01..0x08 -> copy the next N bytes verbatim (escape for bytes the bare encoding can't carry)
9// 0x09..0x7F -> literal (that ASCII byte)
10// 0x80..0xBF -> 2-byte back-reference: n=((b0&0x3F)<<8)|b1; distance=n>>3 (<=2047); length=(n&7)+3 (3..10)
11// 0xC0..0xFF -> a space followed by (byte & 0x7F)
12// license_tier: ORIGINAL
13
14// decompress src[0..n) into out (cap) -> decompressed length. Overlapping back-copies handled byte-by-byte.
15func palmdoc_decompress(src: *u8, n: i64, out: *u8, cap: i64) -> i64 {
16 var i: i64 = 0
17 var o: i64 = 0
18 while i < n {
19 let c: i64 = src[i] as i64
20 i = i + 1
21 if c == 0 {
22 if o < cap { out[o] = 0 as u8; o = o + 1 }
23 } else { if c <= 8 {
24 var k: i64 = 0
25 while k < c { if i < n { if o < cap { out[o] = src[i]; o = o + 1 } i = i + 1 } k = k + 1 }
26 } else { if c <= 0x7f {
27 if o < cap { out[o] = c as u8; o = o + 1 }
28 } else { if c <= 0xbf {
29 if i < n {
30 let c2: i64 = src[i] as i64; i = i + 1
31 let pair: i64 = ((c & 0x3f) << 8) | c2
32 let dist: i64 = pair >> 3
33 let len: i64 = (c2 & 0x07) + 3
34 var k: i64 = 0
35 while k < len { if o - dist >= 0 { if o < cap { out[o] = out[o-dist]; o = o + 1 } } k = k + 1 }
36 }
37 } else {
38 if o < cap { out[o] = 0x20 as u8; o = o + 1 }
39 if o < cap { out[o] = (c & 0x7f) as u8; o = o + 1 }
40 } } } }
41 }
42 return o
43}
44
45// greedy LZ77 compress src[0..n) into out (cap) -> compressed length. Window 2047, match 3..10. Bytes the bare
46// encoding can't carry (0x01..0x08, 0x80..0xFF) are escaped via the 0x01 (copy-1-literal) code. Conservative
47// (never emits the 0xC0 space-pair optimization) -> always valid PalmDOC the decompressor reads back identically.
48func palmdoc_compress(src: *u8, n: i64, out: *u8, cap: i64) -> i64 {
49 var i: i64 = 0
50 var o: i64 = 0
51 while i < n {
52 var best_len: i64 = 0
53 var best_dist: i64 = 0
54 var ws: i64 = i - K_MAGIC_2047
55 if ws < 0 { ws = 0 }
56 var j: i64 = ws
57 while j < i {
58 var l: i64 = 0
59 var go: i64 = 1
60 while go == 1 {
61 if l >= 10 { go = 0 } else { if i + l >= n { go = 0 } else { if src[j+l] != src[i+l] { go = 0 } else { l = l + 1 } } }
62 }
63 if l > best_len { best_len = l; best_dist = i - j }
64 j = j + 1
65 }
66 if best_len >= 3 {
67 let pair: i64 = (best_dist << 3) | (best_len - 3)
68 if o < cap { out[o] = (0x80 | ((pair >> 8) & 0x3f)) as u8; o = o + 1 }
69 if o < cap { out[o] = (pair & 0xff) as u8; o = o + 1 }
70 i = i + best_len
71 } else {
72 let c: i64 = src[i] as i64
73 if c == 0 { if o < cap { out[o] = 0 as u8; o = o + 1 } i = i + 1 }
74 else { if c >= 0x09 { if c <= 0x7f {
75 if o < cap { out[o] = c as u8; o = o + 1 } i = i + 1
76 } else {
77 if o < cap { out[o] = 1 as u8; o = o + 1 } if o < cap { out[o] = c as u8; o = o + 1 } i = i + 1
78 } } else {
79 if o < cap { out[o] = 1 as u8; o = o + 1 } if o < cap { out[o] = c as u8; o = o + 1 } i = i + 1
80 } }
81 }
82 }
83 return o
84}