1 /*
2 BStone: A Source port of
3 Blake Stone: Aliens of Gold and Blake Stone: Planet Strike
4
5 Copyright (c) 1992-2013 Apogee Entertainment, LLC
6 Copyright (c) 2013-2015 Boris I. Bendovsky (bibendovsky@hotmail.com)
7
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License
10 as published by the Free Software Foundation; either version 2
11 of the License, or (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the
20 Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22 */
23
24
25 // ===========================================================================
26 //
27 // LZHUFF COMPRESSION ROUTINES
28 // VERSION 1.0
29 //
30 // Compression algrythim by Haruhiko OKUMURA
31 // Implementation by Jim T. Row
32 //
33 //
34 // Copyright (c) 1992 -
35 //
36 // ===========================================================================
37 //
38 // Compiler #ifdef switches
39 //
40 // LZHUFF_COMPRESSION & LZHUFF_DECOMPRESSION - not yet functional!
41 //
42 // Usage Explanition :
43 //
44 // if LZHUFF_COMPRESSION is defined then the compression code & data is
45 // compiled and so-forth for the decompression code.
46 //
47 // ---------------------------------------------------------------------------
48
49
50 #include <cstdlib>
51 #include <cstring>
52 #include "jm_cio.h"
53 #include "jm_lzh.h"
54
55
56 // ===========================================================================
57 //
58 // SWITCHES
59 //
60 // NOTE : Make sure the appropriate switches are set in SOFT.c for Softlib
61 // archive support.
62 //
63 // ===========================================================================
64
65
66 #define INCLUDE_LZH_COMP 1
67 #define INCLUDE_LZH_DECOMP 1
68
69
70 #define LZH_DYNAMIC_ALLOCATION
71
72 #define LZH_ID_MEMORY_ALLOCATION
73
74
75 // ===========================================================================
76 //
77 // DEFINES
78 //
79 // ===========================================================================
80
81
82 #define EXIT_OK (0)
83 #define EXIT_FAILED (-1)
84
85 /* LZSS Parameters */
86
87 #define N (4096) /* Size of string buffer */
88 #define F (30) /* Size of look-ahead buffer */
89 #define THRESHOLD (2)
90 #define NIL (N) /* End of tree's node */
91
92 /* Huffman coding parameters */
93
94 #define N_CHAR (256 - THRESHOLD + F) /* character code (= 0..N_CHAR-1) */
95 #define T ((N_CHAR * 2) - 1) /* Size of table */
96 #define R (T - 1) /* root position */
97 #define MAX_FREQ (0x8000) /* update when cumulative frequency */
98 /* reaches to this value */
99
100
101 // ==========================================================================
102 //
103 // LOCAL PROTOTYPES
104 //
105 // ==========================================================================
106
107
108 static void StartHuff();
109 static void reconst();
110
111 static void update(
112 int16_t c);
113
114
115 static void DeleteNode(
116 int16_t p); /* Deleting node from the tree */
117
118 static void InsertNode(
119 int16_t r); /* Inserting node to the tree */
120
121 static void InitTree(); /* Initializing tree */
122
123 static void Putcode(
124 void*& outfile_ptr,
125 int16_t l,
126 uint16_t c);
127
128 static void EncodeChar(
129 void*& outfile_ptr,
130 uint16_t c);
131
132 static void EncodePosition(
133 void*& outfile_ptr,
134 uint16_t c);
135
136 static void EncodeEnd(
137 void*& outfile_ptr);
138
139 static int16_t GetByte(
140 const void*& infile_ptr,
141 uint32_t* CompressLength);
142
143 static int16_t GetBit(
144 const void*& infile_ptr,
145 uint32_t* CompressLength);
146
147 static int16_t DecodeChar(
148 const void*& infile_ptr,
149 uint32_t* CompressLength);
150
151 static int16_t DecodePosition(
152 const void*& infile_ptr,
153 uint32_t* CompressLength);
154
155
156 // ==========================================================================
157 //
158 // USER AVAILABLE VECTORS
159 //
160 // ==========================================================================
161
162 // ---------------------------------------------------------------------------
163 //
164 // LZHUFF DISPLAY VECTORS
165 //
166 // These vectors allow you to hook up any form of display you desire for
167 // displaying the compression/decompression status.
168 //
169 // These routines are called inside of the compression/decompression routines
170 // and pass the orginal size of data and current position within that
171 // data. This allows for any kind of "% Done" messages.
172 //
173 // Your functions MUST have the following parameters in this order...
174 //
175 // void VectorRoutine(unsigned long OriginalSize,unsigned long CurPosition)
176 //
177 //
178
179 #if INCLUDE_LZH_COMP
180 void (* LZH_CompressDisplayVector)(uint32_t, uint32_t) = nullptr;
181 #endif
182
183 #if INCLUDE_LZH_DECOMP
184 void (* LZH_DecompressDisplayVector)(uint32_t, uint32_t) = nullptr;
185 #endif
186
187
188 // ===========================================================================
189 //
190 // GLOBAL VARIABLES
191 //
192 // ===========================================================================
193 /* pointing children nodes (son[], son[] + 1)*/
194
195 uint16_t code, len;
196 uint32_t textsize = 0, codesize = 0, printcount = 0, datasize;
197
198 #ifdef LZH_DYNAMIC_ALLOCATION
199
200 int16_t* son = nullptr;
201
202 //
203 // pointing parent nodes.
204 // area [T..(T + N_CHAR - 1)] are pointers for leaves
205 //
206
207 int16_t* prnt;
208 uint16_t* freq; /* cumulative freq table */
209 uint8_t* text_buf;
210
211 #ifdef LZH_ID_MEMORY_ALLOCATION
212 int16_t* id_son;
213 int16_t* id_prnt;
214 uint16_t* id_freq;
215 uint8_t* id_text_buf;
216 #endif
217
218 #else
219
220 int16_t son[T];
221
222 //
223 // pointing parent nodes.
224 // area [T..(T + N_CHAR - 1)] are pointers for leaves
225 //
226
227 int16_t prnt[T + N_CHAR];
228
229 uint16_t freq[T + 1]; /* cumulative freq table */
230
231 uint8_t text_buf[N + F - 1];
232
233 #endif
234
235
236
237 //
238 // COMPRESSION VARIABLES
239 //
240
241 #if INCLUDE_LZH_COMP
242
243 #ifdef LZH_DYNAMIC_ALLOCATION
244
245 static int16_t* lson, * rson, * dad;
246
247 #ifdef LZH_ID_MEMORY_ALLOCATION
248 int16_t* id_lson;
249 int16_t* id_rson;
250 int16_t* id_dad;
251 #endif
252 #else
253
254 static int16_t lson[N + 1], rson[N + 257], dad[N + 1];
255
256 #endif
257
258 static int16_t match_position, match_length;
259 uint16_t putbuf = 0;
260 uint16_t putlen = 0;
261
262 //
263 // Tables for encoding/decoding upper 6 bits of
264 // sliding dictionary pointer
265 //
266
267 //
268 // encoder table
269 //
270
271 uint8_t p_len[64] = {
272 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
273 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
274 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
275 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
276 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
277 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
278 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
279 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
280 };
281
282 uint8_t p_code[64] = {
283 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
284 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
285 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
286 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
287 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
288 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
289 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
290 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
291 };
292 #endif
293
294
295 //
296 // DECOMPRESSION VARIABLES
297 //
298
299
300 //
301 // decoder table
302 //
303
304 #if INCLUDE_LZH_DECOMP
305
306 uint8_t d_code[256] = {
307 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
308 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
309 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
310 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
311 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
312 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
313 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
314 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
315 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
316 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
317 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
318 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
319 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
320 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
321 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
322 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
323 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
324 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
325 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
326 0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
327 0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
328 0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
329 0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
330 0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
331 0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
332 0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
333 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
334 0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
335 0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
336 0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
337 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
338 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
339 };
340
341 uint8_t d_len[256] = {
342 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
343 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
344 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
345 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
346 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
347 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
348 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
349 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
350 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
351 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
352 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
353 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
354 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
355 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
356 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
357 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
358 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
359 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
360 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
361 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
362 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
363 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
364 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
365 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
366 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
367 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
368 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
369 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
370 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
371 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
372 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
373 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
374 };
375
376 uint16_t getbuf = 0;
377 uint16_t getlen = 0;
378
379 #endif
380
381
382 // ===========================================================================
383 //
384 // COMPRESSION & DECOMPRESSION ROUTINES
385 //
386 // ===========================================================================
387
LZH_Startup()388 bool LZH_Startup()
389 {
390 if (son) {
391 return true;
392 }
393
394 #ifdef LZH_DYNAMIC_ALLOCATION
395 #ifdef LZH_ID_MEMORY_ALLOCATION
396 id_son = new int16_t[T];
397 id_prnt = new int16_t[T + N_CHAR];
398 id_freq = new uint16_t[T + 1];
399 id_text_buf = new uint8_t[N + F - 1];
400 #else
401 if (!(son = farmalloc(T * sizeof(*son)))) {
402 return false;
403 }
404
405 if (!(prnt = farmalloc((T + N_CHAR) * sizeof(*prnt)))) {
406 return false;
407 }
408
409 if (!(freq = farmalloc((T + 1) * sizeof(*freq)))) {
410 return false;
411 }
412
413 if (!(text_buf = farmalloc((N + F - 1) * sizeof(*text_buf)))) {
414 return false;
415 }
416 #endif
417
418 #if INCLUDE_LZH_COMP
419 #ifdef LZH_ID_MEMORY_ALLOCATION
420 id_lson = new int16_t[N + 1];
421 id_rson = new int16_t[N + 257];
422 id_dad = new int16_t[N + 1];
423 #else
424 if (!(lson = farmalloc((N + 1) * sizeof(*lson)))) {
425 return false;
426 }
427
428 if (!(rson = farmalloc((N + 257) * sizeof(*rson)))) {
429 return false;
430 }
431
432 if (!(dad = farmalloc((N + 1) * sizeof(*dad)))) {
433 return false;
434 }
435 #endif
436 #endif
437 #endif
438
439 return true;
440 }
441
LZH_Shutdown()442 void LZH_Shutdown()
443 {
444 #ifdef LZH_DYNAMIC_ALLOCATION
445 #ifdef LZH_ID_MEMORY_ALLOCATION
446 delete [] id_son;
447 id_son = nullptr;
448
449 delete [] id_prnt;
450 id_prnt = nullptr;
451
452 delete [] id_freq;
453 id_freq = nullptr;
454
455 delete [] id_text_buf;
456 id_text_buf = nullptr;
457 #else
458 if (son) {
459 farfree(son);
460 }
461
462 if (prnt) {
463 farfree(prnt);
464 }
465
466 if (freq) {
467 farfree(freq);
468 }
469
470 if (text_buf) {
471 farfree(text_buf);
472 }
473 #endif
474
475 #if INCLUDE_LZH_COMP
476 #ifdef LZH_ID_MEMORY_ALLOCATION
477 delete [] id_lson;
478 id_lson = nullptr;
479
480 delete [] id_rson;
481 id_rson = nullptr;
482
483 delete [] id_dad;
484 id_dad = nullptr;
485 #else
486 if (lson) {
487 farfree(lson);
488 }
489
490 if (rson) {
491 farfree(rson);
492 }
493
494 if (dad) {
495 farfree(dad);
496 }
497 #endif
498 #endif
499
500 son = nullptr; // Must be zeroed on shutdown!
501 #endif
502 }
503
504 /* initialize freq tree */
StartHuff()505 static void StartHuff()
506 {
507 int16_t i, j;
508
509 #ifdef LZH_DYNAMIC_ALLOCATION
510 #ifdef LZH_ID_MEMORY_ALLOCATION
511
512 // Assign _seg pointers to far pointers, always initialized here in case
513 // the memory manager shifted things around after LZH_Startup() was called.
514 //
515 son = id_son;
516 prnt = id_prnt;
517 freq = id_freq;
518 text_buf = id_text_buf;
519 lson = id_lson;
520 rson = id_rson;
521 dad = id_dad;
522
523 #endif
524 #endif
525
526 for (i = 0; i < N_CHAR; i++) {
527 freq[i] = 1;
528 son[i] = i + T;
529 prnt[i + T] = i;
530 }
531 i = 0;
532 j = N_CHAR;
533 while (j <= R) {
534 freq[j] = freq[i] + freq[i + 1];
535 son[j] = i;
536 prnt[i] = prnt[i + 1] = j;
537 i += 2;
538 j++;
539 }
540 freq[T] = 0xffff;
541 prnt[R] = 0;
542
543 printcount = 0;
544
545 putbuf = putlen = match_position = match_length = 0;
546 }
547
548 /* reconstruct freq tree */
reconst()549 static void reconst()
550 {
551 int16_t i, j, k;
552 uint16_t f, l;
553
554 /* halven cumulative freq for leaf nodes */
555
556 j = 0;
557
558 for (i = 0; i < T; i++) {
559 if (son[i] >= T) {
560 freq[j] = (freq[i] + 1) / 2;
561 son[j] = son[i];
562 j++;
563 }
564 }
565
566 /* make a tree : first, connect children nodes */
567
568 for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
569 k = i + 1;
570 f = freq[j] = freq[i] + freq[k];
571
572 for (k = j - 1; f < freq[k]; k--) {
573 }
574
575 k++;
576 l = (j - k) * 2;
577
578 memcpy(&freq[k + 1], &freq[k], l);
579 freq[k] = f;
580
581 memcpy(&son[k + 1], &son[k], l);
582 son[k] = i;
583 }
584
585 /* connect parent nodes */
586
587 for (i = 0; i < T; i++) {
588 if ((k = son[i]) >= T) {
589 prnt[k] = i;
590 } else {
591 prnt[k] = prnt[k + 1] = i;
592 }
593 }
594 }
595
596 // update freq tree
update(int16_t c)597 static void update(
598 int16_t c)
599 {
600 int16_t i, j, k, l;
601
602 if (freq[R] == MAX_FREQ) {
603 reconst();
604 }
605
606 c = prnt[c + T];
607
608 do {
609 k = ++freq[c];
610
611 //
612 // swap nodes to keep the tree freq-ordered
613 //
614
615 if (k > freq[l = c + 1]) {
616 while (k > freq[++l]) {
617 }
618
619 l--;
620 freq[c] = freq[l];
621 freq[l] = k;
622
623 i = son[c];
624 prnt[i] = l;
625 if (i < T) {
626 prnt[i + 1] = l;
627 }
628
629 j = son[l];
630 son[l] = i;
631
632 prnt[j] = c;
633 if (j < T) {
634 prnt[j + 1] = c;
635 }
636
637 son[c] = j;
638
639 c = l;
640 }
641 } while ((c = prnt[c]) != 0); /* do it until reaching the root */
642 }
643
644
645 // ===========================================================================
646 //
647 // COMPRESSION ROUTINES
648 //
649 // ===========================================================================
650
651
652 #if INCLUDE_LZH_COMP
DeleteNode(int16_t p)653 static void DeleteNode(
654 int16_t p) /* Deleting node from the tree */
655 {
656 int16_t q;
657
658 if (dad[p] == NIL) {
659 return; /* unregistered */
660
661 }
662 if (rson[p] == NIL) {
663 q = lson[p];
664 } else if (lson[p] == NIL) {
665 q = rson[p];
666 } else {
667 q = lson[p];
668 if (rson[q] != NIL) {
669 do {
670 q = rson[q];
671 } while (rson[q] != NIL);
672
673 rson[dad[q]] = lson[q];
674 dad[lson[q]] = dad[q];
675 lson[q] = lson[p];
676 dad[lson[p]] = q;
677 }
678
679 rson[q] = rson[p];
680 dad[rson[p]] = q;
681 }
682
683 dad[q] = dad[p];
684
685 if (rson[dad[p]] == p) {
686 rson[dad[p]] = q;
687 } else {
688 lson[dad[p]] = q;
689 }
690
691 dad[p] = NIL;
692 }
693
694 /* Inserting node to the tree */
InsertNode(int16_t r)695 static void InsertNode(
696 int16_t r)
697 {
698 int16_t i, p, cmp;
699 uint8_t* key;
700 uint16_t c;
701
702 cmp = 1;
703 key = &text_buf[r];
704 p = N + 1 + key[0];
705 rson[r] = lson[r] = NIL;
706 match_length = 0;
707 for (;; ) {
708 if (cmp >= 0) {
709 if (rson[p] != NIL) {
710 p = rson[p];
711 } else {
712 rson[p] = r;
713 dad[r] = p;
714 return;
715 }
716 } else {
717 if (lson[p] != NIL) {
718 p = lson[p];
719 } else {
720 lson[p] = r;
721 dad[r] = p;
722 return;
723 }
724 }
725
726
727 for (i = 1; i < F; i++) {
728 if ((cmp = key[i] - text_buf[p + i]) != 0) {
729 break;
730 }
731 }
732
733 if (i > THRESHOLD) {
734 if (i > match_length) {
735 match_position = ((r - p) & (N - 1)) - 1;
736 if ((match_length = i) >= F) {
737 break;
738 }
739 }
740
741 if (i == match_length) {
742 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
743 match_position = c;
744 }
745 }
746 }
747 }
748
749 dad[r] = dad[p];
750 lson[r] = lson[p];
751 rson[r] = rson[p];
752 dad[lson[p]] = r;
753 dad[rson[p]] = r;
754
755 if (rson[dad[p]] == p) {
756 rson[dad[p]] = r;
757 } else {
758 lson[dad[p]] = r;
759 }
760
761 dad[p] = NIL; /* remove p */
762 }
763
764 /* Initializing tree */
InitTree()765 static void InitTree()
766 {
767 int16_t i;
768
769 for (i = N + 1; i <= N + 256; i++) {
770 rson[i] = NIL; /* root */
771
772 }
773 for (i = 0; i < N; i++) {
774 dad[i] = NIL; /* node */
775 }
776 }
777
778 // output c bits
Putcode(void * & outfile_ptr,int16_t l,uint16_t c)779 static void Putcode(
780 void*& outfile_ptr,
781 int16_t l,
782 uint16_t c)
783 {
784 putbuf |= c >> putlen;
785
786 putlen += l;
787
788 if (putlen >= 8) {
789 ::CIO_WritePtr(outfile_ptr, putbuf >> 8);
790 ++codesize;
791
792 putlen -= 8;
793 if (putlen >= 8) {
794 ::CIO_WritePtr(outfile_ptr, static_cast<uint8_t>(putbuf));
795 ++codesize;
796
797 putlen -= 8;
798 putbuf = c << (l - putlen);
799 } else {
800 putbuf <<= 8;
801 }
802 }
803 }
804
EncodeChar(void * & outfile_ptr,uint16_t c)805 static void EncodeChar(
806 void*& outfile_ptr,
807 uint16_t c)
808 {
809 uint16_t i;
810 int16_t j, k;
811
812 i = 0;
813 j = 0;
814 k = prnt[c + T];
815
816 /// search connections from leaf node to the root
817
818 do {
819 i >>= 1;
820
821 //
822 // if node's address is odd, output 1 else output 0
823 //
824
825 if ((k & 1) != 0) {
826 i += 0x8000;
827 }
828
829 ++j;
830 k = prnt[k];
831 } while (k != R);
832
833 ::Putcode(outfile_ptr, j, i);
834
835 code = i;
836 len = j;
837 ::update(c);
838 }
839
EncodePosition(void * & outfile_ptr,uint16_t c)840 static void EncodePosition(
841 void*& outfile_ptr,
842 uint16_t c)
843 {
844 uint16_t i;
845
846 //
847 // output upper 6 bits with encoding
848 //
849
850 i = c >> 6;
851 ::Putcode(outfile_ptr, p_len[i], static_cast<uint16_t>(p_code[i]) << 8);
852
853 //
854 // output lower 6 bits directly
855 //
856
857 ::Putcode(outfile_ptr, 6, (c & 0x3F) << 10);
858 }
859
EncodeEnd(void * & outfile_ptr)860 static void EncodeEnd(
861 void*& outfile_ptr)
862 {
863 if (putlen != 0) {
864 ::CIO_WritePtr(outfile_ptr, putbuf >> 8);
865 ++codesize;
866 }
867 }
868 #endif
869
870
871 // ===========================================================================
872 //
873 // DECOMPRESSION ROUTINES
874 //
875 // ===========================================================================
876
877
878 #if INCLUDE_LZH_DECOMP
879 // ---------------------------------------------------------------------------
880 // GetByte
881 // ---------------------------------------------------------------------------
GetByte(const void * & infile_ptr,uint32_t * CompressLength)882 static int16_t GetByte(
883 const void*& infile_ptr,
884 uint32_t* CompressLength)
885 {
886 uint16_t i;
887
888 while (getlen <= 8) {
889 if (*CompressLength) {
890 i = ::CIO_ReadPtr(infile_ptr);
891 (*CompressLength)--;
892 } else {
893 i = 0;
894 }
895
896 getbuf |= i << (8 - getlen);
897 getlen += 8;
898 }
899
900 i = getbuf;
901 getbuf <<= 8;
902 getlen -= 8;
903 return i >> 8;
904 }
905
GetBit(const void * & infile_ptr,uint32_t * CompressLength)906 static int16_t GetBit(
907 const void*& infile_ptr,
908 uint32_t* CompressLength)
909 {
910 int16_t i;
911
912 while (getlen <= 8) {
913 if (*CompressLength) {
914 i = ::CIO_ReadPtr(infile_ptr);
915 (*CompressLength)--;
916 } else {
917 i = 0;
918 }
919
920 getbuf |= i << (8 - getlen);
921 getlen += 8;
922 }
923
924 i = getbuf;
925 getbuf <<= 1;
926 --getlen;
927 return i < 0;
928 }
929
DecodeChar(const void * & infile_ptr,uint32_t * CompressLength)930 static int16_t DecodeChar(
931 const void*& infile_ptr,
932 uint32_t* CompressLength)
933 {
934 uint16_t c;
935
936 c = son[R];
937
938 /*
939 * start searching tree from the root to leaves.
940 * choose node #(son[]) if input bit == 0
941 * else choose #(son[]+1) (input bit == 1)
942 */
943
944 while (c < T) {
945 c += ::GetBit(infile_ptr, CompressLength);
946 c = son[c];
947 }
948
949 c -= T;
950 ::update(c);
951 return c;
952 }
953
DecodePosition(const void * & infile_ptr,uint32_t * CompressLength)954 static int16_t DecodePosition(
955 const void*& infile_ptr,
956 uint32_t* CompressLength)
957 {
958 uint16_t i;
959 uint16_t j;
960 uint16_t c;
961
962 //
963 // decode upper 6 bits from given table
964 //
965
966 i = ::GetByte(infile_ptr, CompressLength);
967 c = static_cast<uint16_t>(d_code[i]) << 6;
968 j = d_len[i];
969
970 //
971 // input lower 6 bits directly
972 //
973
974 j -= 2;
975 while (j--) {
976 i = (i << 1) + ::GetBit(infile_ptr, CompressLength);
977 }
978
979 return c | (i & 0x3F);
980 }
981 #endif
982
983
984 // ===========================================================================
985 //
986 // EXTERNAL REFERENCED
987 // COMPRESSION & DECOMPRESSION
988 // ROUTINES
989 //
990 // ===========================================================================
991
992 #if INCLUDE_LZH_DECOMP
LZH_Decompress(const void * infile,void * outfile,uint32_t OriginalLength,uint32_t CompressLength)993 int32_t LZH_Decompress(
994 const void* infile,
995 void* outfile,
996 uint32_t OriginalLength,
997 uint32_t CompressLength)
998 {
999 int16_t i, j, k, r, c;
1000 int32_t count;
1001
1002 datasize = textsize = OriginalLength;
1003 getbuf = 0;
1004 getlen = 0;
1005
1006 if (textsize == 0) {
1007 return 0;
1008 }
1009
1010 StartHuff();
1011 for (i = 0; i < N - F; i++) {
1012 text_buf[i] = ' ';
1013 }
1014
1015 r = N - F;
1016
1017 for (count = 0; count < static_cast<int32_t>(textsize); ) {
1018 c = ::DecodeChar(infile, &CompressLength);
1019
1020 if (c < 256) {
1021 ::CIO_WritePtr(outfile, static_cast<uint8_t>(c));
1022
1023 datasize--; // Dec # of bytes to write
1024
1025 text_buf[r++] = static_cast<uint8_t>(c);
1026 r &= (N - 1);
1027 count++; // inc count of bytes written
1028 } else {
1029 i = (r - ::DecodePosition(infile, &CompressLength) - 1) & (N - 1);
1030
1031 j = c - 255 + THRESHOLD;
1032
1033 for (k = 0; k < j; k++) {
1034 c = text_buf[(i + k) & (N - 1)];
1035
1036 ::CIO_WritePtr(outfile, static_cast<uint8_t>(c));
1037
1038 datasize--; // dec count of bytes to write
1039
1040 text_buf[r++] = static_cast<uint8_t>(c);
1041 r &= (N - 1);
1042 count++; // inc count of bytes written
1043 }
1044 }
1045
1046 if (LZH_DecompressDisplayVector && (count > static_cast<int32_t>(printcount))) {
1047 LZH_DecompressDisplayVector(OriginalLength, OriginalLength - datasize);
1048 printcount += 1024;
1049 }
1050 }
1051
1052 if (LZH_DecompressDisplayVector) {
1053 LZH_DecompressDisplayVector(OriginalLength, OriginalLength);
1054 }
1055
1056 return count;
1057 }
1058 #endif
1059
1060 #if INCLUDE_LZH_COMP
LZH_Compress(const void * infile,void * outfile,uint32_t DataLength)1061 int LZH_Compress(
1062 const void* infile,
1063 void* outfile,
1064 uint32_t DataLength)
1065 {
1066 int16_t i;
1067 int16_t c;
1068 int16_t length;
1069 int16_t r;
1070 int16_t s;
1071 int16_t last_match_length;
1072
1073 textsize = DataLength;
1074
1075 if (textsize == 0) {
1076 return 0;
1077 }
1078
1079 getbuf = 0;
1080 getlen = 0;
1081 textsize = 0; /* rewind and rescan */
1082 codesize = 0;
1083 datasize = 0; // Init our counter of ReadData...
1084 StartHuff();
1085 InitTree();
1086
1087 s = 0;
1088 r = N - F;
1089
1090 for (i = s; i < r; i++) {
1091 text_buf[i] = ' ';
1092 }
1093
1094 for (length = 0; length < F && (DataLength > datasize); length++) {
1095 c = ::CIO_ReadPtr(infile);
1096
1097 datasize++; // Dec num of bytes to compress
1098 text_buf[r + length] = static_cast<uint8_t>(c);
1099 }
1100
1101 textsize = length;
1102
1103 for (i = 1; i <= F; i++) {
1104 InsertNode(r - i);
1105 }
1106
1107 InsertNode(r);
1108
1109 do {
1110 if (match_length > length) {
1111 match_length = length;
1112 }
1113
1114 if (match_length <= THRESHOLD) {
1115 match_length = 1;
1116 ::EncodeChar(outfile, text_buf[r]);
1117 } else {
1118 ::EncodeChar(outfile, 255 - THRESHOLD + match_length);
1119 ::EncodePosition(outfile, match_position);
1120 }
1121
1122 last_match_length = match_length;
1123
1124 for (i = 0; i < last_match_length && (DataLength > datasize); i++) {
1125 c = ::CIO_ReadPtr(infile);
1126
1127 datasize++;
1128
1129 DeleteNode(s);
1130 text_buf[s] = static_cast<uint8_t>(c);
1131
1132 if (s < F - 1) {
1133 text_buf[s + N] = static_cast<uint8_t>(c);
1134 }
1135
1136 s = (s + 1) & (N - 1);
1137 r = (r + 1) & (N - 1);
1138 InsertNode(r);
1139 }
1140
1141 if (LZH_CompressDisplayVector && ((textsize += i) > printcount)) {
1142 LZH_CompressDisplayVector(DataLength, datasize);
1143 printcount += 1024;
1144 }
1145
1146
1147 while (i++ < last_match_length) {
1148 DeleteNode(s);
1149 s = (s + 1) & (N - 1);
1150 r = (r + 1) & (N - 1);
1151 if (--length) {
1152 InsertNode(r);
1153 }
1154 }
1155
1156 } while (length > 0);
1157
1158 ::EncodeEnd(outfile);
1159
1160 if (LZH_CompressDisplayVector) {
1161 LZH_CompressDisplayVector(DataLength, DataLength);
1162 }
1163
1164 return codesize;
1165 }
1166 #endif
1167