1 //Copyright Paul Reiche, Fred Ford. 1992-2002
2
3 /*
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18
19 /*
20 * LZHUF.C English version 1.0
21 * Based on Japanese version 29-NOV-1988
22 * LZSS coded by Haruhiko OKUMURA
23 * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI
24 * Edited and translated to English by Kenji RIKITAKE
25 */
26
27 #include <stdio.h>
28 #include "lzh.h"
29 #include "libs/reslib.h"
30
31 static UWORD match_position, match_length;
32 static SWORD *lson;
33 static SWORD *rson;
34 static SWORD *dad;
35 static SWORD *encode_arrays;
36
37 #define AllocEncodeArrays() \
38 HCalloc ( \
39 (((N + 1) + (N + 257) + (N + 1)) \
40 * sizeof (lson[0])))
41 #define FreeCodeArrays HFree
42
43 static BOOLEAN
InitTree(void)44 InitTree (void)
45 {
46 if ((encode_arrays = AllocEncodeArrays ()) == NULL)
47 {
48 FreeCodeArrays (encode_arrays);
49 encode_arrays = NULL;
50 return (FALSE);
51 }
52 else
53 {
54 SWORD i;
55
56 lson = encode_arrays;
57 rson = lson + (N + 1);
58 dad = rson + (N + 257);
59
60 for (i = N + 1; i <= N + 256; i++)
61 rson[i] = NIL; /* root */
62 for (i = 0; i < N; i++)
63 dad[i] = NIL; /* node */
64
65 return (TRUE);
66 }
67 }
68
69 static void
InsertNode(SWORD r)70 InsertNode (SWORD r)
71 {
72 SWORD p, cmp;
73 BYTE *lpBuf;
74
75 cmp = 1;
76 lpBuf = _lpCurCodeDesc->text_buf;
77 p = N + 1 + lpBuf[r];
78 rson[r] = lson[r] = NIL;
79 match_length = 0;
80 for (;;)
81 {
82 UWORD i;
83
84 if (cmp >= 0)
85 {
86 if (rson[p] != NIL)
87 p = rson[p];
88 else
89 {
90 rson[p] = r;
91 dad[r] = p;
92 return;
93 }
94 }
95 else
96 {
97 if (lson[p] != NIL)
98 p = lson[p];
99 else
100 {
101 lson[p] = r;
102 dad[r] = p;
103 return;
104 }
105 }
106
107 i = F;
108 {
109 SWORD _r, _p;
110
111 _r = r;
112 _p = p;
113 while (--i && (cmp = lpBuf[++_r] - lpBuf[++_p]) == 0)
114 ;
115 }
116 if ((i = F - i) > THRESHOLD)
117 {
118 if (i > match_length)
119 {
120 match_position = ((r - p) & (N - 1)) - 1;
121 if ((match_length = i) >= F)
122 break;
123 }
124 else if (i == match_length)
125 {
126 if ((i = ((r - p) & (N - 1)) - 1) < match_position)
127 {
128 match_position = i;
129 }
130 }
131 }
132 }
133 dad[r] = dad[p];
134 lson[r] = lson[p];
135 rson[r] = rson[p];
136 dad[lson[p]] = r;
137 dad[rson[p]] = r;
138 if (rson[dad[p]] == p)
139 rson[dad[p]] = r;
140 else
141 lson[dad[p]] = r;
142 dad[p] = NIL; /* remove p */
143 }
144
145 static void
DeleteNode(SWORD p)146 DeleteNode (SWORD p)
147 {
148 SWORD q;
149
150 if (dad[p] == NIL)
151 return; /* unregistered */
152 if (rson[p] == NIL)
153 q = lson[p];
154 else if (lson[p] == NIL)
155 q = rson[p];
156 else
157 {
158 q = lson[p];
159 if (rson[q] != NIL)
160 {
161 do
162 {
163 q = rson[q];
164 } while (rson[q] != NIL);
165 rson[dad[q]] = lson[q];
166 dad[lson[q]] = dad[q];
167 lson[q] = lson[p];
168 dad[lson[p]] = q;
169 }
170 rson[q] = rson[p];
171 dad[rson[p]] = q;
172 }
173 dad[q] = dad[p];
174 if (rson[dad[p]] == p)
175 rson[dad[p]] = q;
176 else
177 lson[dad[p]] = q;
178 dad[p] = NIL;
179 }
180
181 static void
Putcode(SWORD l,UWORD c)182 Putcode (SWORD l, UWORD c)
183 {
184 _workbuf |= c >> _workbuflen;
185 if ((_workbuflen += l) >= 8)
186 {
187 OutChar ((BYTE)(_workbuf >> 8));
188 ++_lpCurCodeDesc->StreamIndex;
189 if ((_workbuflen -= 8) >= 8)
190 {
191 OutChar ((BYTE)(_workbuf));
192 ++_lpCurCodeDesc->StreamIndex;
193 _workbuflen -= 8;
194 _workbuf = c << (l - _workbuflen);
195 }
196 else
197 {
198 _workbuf <<= 8;
199 }
200 _workbuf &= 0xFFFF;
201 }
202 }
203
204 static void
EncodeChar(UWORD c)205 EncodeChar (UWORD c)
206 {
207 UWORD i;
208 SWORD j, k;
209
210 i = 0;
211 j = 0;
212 k = _lpCurCodeDesc->prnt[c + T];
213
214 /* search connections from leaf node to the root */
215 do
216 {
217 i >>= 1;
218
219 /*
220 if node's address is odd, output 1
221 else output 0
222 */
223 if (k & 1)
224 i += 0x8000;
225
226 j++;
227 } while ((k = _lpCurCodeDesc->prnt[k]) != R);
228 Putcode (j, i);
229 _update (c + T);
230 }
231
232 static void
EncodePosition(UWORD c)233 EncodePosition (UWORD c)
234 {
235 UWORD i;
236 /*
237 * Tables for encoding/decoding upper 6 bits of
238 * sliding dictionary pointer
239 */
240 /* encoder table */
241 static const BYTE p_len[64] =
242 {
243 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
244 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
245 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
246 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
247 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
248 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
249 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
250 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
251 };
252
253 static const BYTE p_code[64] =
254 {
255 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
256 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
257 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
258 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
259 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
260 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
261 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
262 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
263 };
264
265 /* output upper 6 bits with encoding */
266 i = c >> 6;
267 Putcode (p_len[i], (UWORD)p_code[i] << 8);
268
269 /* output lower 6 bits directly */
270 Putcode (6, (c & 0x3f) << 10);
271 }
272
273 static void
UninitTree(void)274 UninitTree (void)
275 {
276 if (_workbuflen)
277 {
278 OutChar ((BYTE)(_workbuf >> 8));
279 ++_lpCurCodeDesc->StreamIndex;
280 }
281
282 FreeCodeArrays (encode_arrays);
283 encode_arrays = NULL;
284 lson = NULL;
285 rson = NULL;
286 dad = NULL;
287 }
288
289 static void
_encode_cleanup(void)290 _encode_cleanup (void)
291 {
292 UWORD r, s, last_match_length, len;
293
294 _StreamType = _lpCurCodeDesc->StreamType;
295 _Stream = _lpCurCodeDesc->Stream;
296 _workbuf = _lpCurCodeDesc->workbuf;
297 _workbuflen = _lpCurCodeDesc->workbuflen;
298
299 r = _lpCurCodeDesc->buf_index;
300 s = _lpCurCodeDesc->restart_index;
301 last_match_length = _lpCurCodeDesc->bytes_left;
302 if (_lpCurCodeDesc->StreamLength >= F)
303 len = F;
304 else
305 {
306 UWORD i;
307
308 for (i = 1; i <= F; i++)
309 InsertNode (r - i);
310 InsertNode (r);
311
312 len = (UWORD)_lpCurCodeDesc->StreamLength;
313 }
314
315 while (1)
316 {
317 while (last_match_length--)
318 {
319 DeleteNode (s);
320 if (--len == 0)
321 {
322 BYTE lobyte, hibyte;
323 UWORD loword, hiword;
324
325 UninitTree ();
326
327 _lpCurCodeDesc->StreamIndex += 4;
328 /* rewind */
329 if (_lpCurCodeDesc->StreamType == FILE_STREAM)
330 SeekResFile ((uio_Stream *)_Stream,
331 -(int)_lpCurCodeDesc->StreamIndex, SEEK_CUR);
332 else /* _lpCurCodeDesc->StreamType == MEMORY_STREAM */
333 _Stream = (BYTE*)_Stream - _lpCurCodeDesc->StreamIndex;
334
335 loword = LOWORD (_lpCurCodeDesc->StreamLength);
336 lobyte = LOBYTE (loword);
337 hibyte = HIBYTE (loword);
338 OutChar (lobyte);
339 OutChar (hibyte);
340 hiword = HIWORD (_lpCurCodeDesc->StreamLength);
341 lobyte = LOBYTE (hiword);
342 hibyte = HIBYTE (hiword);
343 OutChar (lobyte);
344 OutChar (hibyte);
345
346 return;
347 }
348 s = (s + 1) & (N - 1);
349 r = (r + 1) & (N - 1);
350 InsertNode (r);
351 }
352 if (match_length > len)
353 match_length = len;
354 if (match_length <= THRESHOLD)
355 {
356 match_length = 1;
357 EncodeChar (_lpCurCodeDesc->text_buf[r]);
358 }
359 else
360 {
361 EncodeChar (255 - THRESHOLD + match_length);
362 EncodePosition (match_position);
363 }
364 last_match_length = match_length;
365 }
366 }
367
368 COUNT
cwrite(const void * buf,COUNT size,COUNT count,PLZHCODE_DESC lpCodeDesc)369 cwrite (const void *buf, COUNT size, COUNT count, PLZHCODE_DESC lpCodeDesc)
370 {
371 UWORD r, s, last_match_length;
372 BYTE *lpBuf;
373 const BYTE *lpStr;
374
375 if ((_lpCurCodeDesc = lpCodeDesc) == 0
376 || (size *= count) == 0)
377 return (0);
378
379 _StreamType = lpCodeDesc->StreamType;
380 _Stream = lpCodeDesc->Stream;
381 _workbuf = lpCodeDesc->workbuf;
382 _workbuflen = lpCodeDesc->workbuflen;
383 lpStr = (const BYTE *) buf;
384 lpBuf = lpCodeDesc->text_buf;
385
386 r = lpCodeDesc->buf_index;
387 s = lpCodeDesc->restart_index;
388 last_match_length = lpCodeDesc->bytes_left;
389 if (last_match_length)
390 {
391 lpCodeDesc->StreamLength += size;
392 goto EncodeRestart;
393 }
394 else if (lpCodeDesc->StreamLength < F)
395 {
396 UWORD i;
397
398 if ((i = (UWORD)lpCodeDesc->StreamLength) == 0)
399 {
400 if (!InitTree ())
401 return (0);
402
403 _lpCurCodeDesc->StreamIndex = 0;
404 lpCodeDesc->CleanupFunc = _encode_cleanup;
405 }
406
407 lpCodeDesc->StreamLength += size;
408
409 for (; i < F && size; ++i, --size)
410 lpBuf[r + i] = *lpStr++;
411 if (i < F)
412 goto EncodeExit;
413
414 for (i = 1; i <= F; i++)
415 InsertNode (r - i);
416 InsertNode (r);
417 if (size == 0)
418 goto EncodeExit;
419 }
420 else
421 lpCodeDesc->StreamLength += size;
422
423 do
424 {
425 if (match_length > F)
426 match_length = F;
427 if (match_length <= THRESHOLD)
428 {
429 match_length = 1;
430 EncodeChar (lpBuf[r]);
431 }
432 else
433 {
434 EncodeChar (255 - THRESHOLD + match_length);
435 EncodePosition (match_position);
436 }
437 last_match_length = match_length;
438 EncodeRestart:
439 while (last_match_length && size)
440 {
441 BYTE c;
442
443 --size;
444 --last_match_length;
445
446 DeleteNode (s);
447 c = *lpStr++;
448 lpBuf[s] = c;
449 if (s < F - 1)
450 lpBuf[s + N] = c;
451 s = (s + 1) & (N - 1);
452 r = (r + 1) & (N - 1);
453 InsertNode (r);
454 }
455 } while (last_match_length == 0);
456
457 EncodeExit:
458 lpCodeDesc->buf_index = r;
459 lpCodeDesc->restart_index = s;
460 lpCodeDesc->bytes_left = last_match_length;
461
462 lpCodeDesc->Stream = _Stream;
463 lpCodeDesc->workbuf = _workbuf;
464 lpCodeDesc->workbuflen = _workbuflen;
465
466 return (count);
467 }
468
469