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