1 /* Catacomb Armageddon Source Code
\r
2 * Copyright (C) 1993-2014 Flat Rock Software
\r
4 * This program is free software; you can redistribute it and/or modify
\r
5 * it under the terms of the GNU General Public License as published by
\r
6 * the Free Software Foundation; either version 2 of the License, or
\r
7 * (at your option) any later version.
\r
9 * This program is distributed in the hope that it will be useful,
\r
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
12 * GNU General Public License for more details.
\r
14 * You should have received a copy of the GNU General Public License along
\r
15 * with this program; if not, write to the Free Software Foundation, Inc.,
\r
16 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
\r
19 //===========================================================================
\r
21 // LZW COMPRESSION ROUTINES
\r
24 // Compression algrythim by Haruhiko OKUMURA
\r
25 // Implementation by Jim T. Row
\r
28 // Copyright (c) 1992 - Softdisk Publishing inc. - All rights reserved
\r
30 //===========================================================================
\r
33 //---------------------------------------------------------------------------
\r
49 //===========================================================================
\r
53 // NOTE : Make sure the appropriate switches are set in SOFT.c for Softlib
\r
56 //===========================================================================
\r
58 #define INCLUDE_LZW_COMP 0
\r
59 #define INCLUDE_LZW_DECOMP 1
\r
62 //===========================================================================
\r
66 //===========================================================================
\r
72 #define LZW_THRESHOLD 2 // encode string into position and
\r
73 // length if match_length is greater
\r
76 #define LZW_NIL LZW_N // index for root of bin search trees
\r
79 //============================================================================
\r
81 // GLOBAL VARIABLES NECESSARY FOR
\r
83 // COMP/DECOMP ROUTINES.
\r
85 //============================================================================
\r
89 unsigned char far LZW_ring_buffer[LZW_N + LZW_F - 1]; // ring buffer of size
\r
90 // LZW_N, with extra
\r
93 // string comparison
\r
95 #if INCLUDE_LZW_COMP
\r
97 int LZW_match_pos, // MAtchLength of longest match. These are set by the
\r
98 // InsertNode() procedure.
\r
101 // left & right children & parents -- These constitute binary search trees. */
\r
103 LZW_left_child[LZW_N + 1],
\r
104 LZW_right_child[LZW_N + 257],
\r
105 LZW_parent[LZW_N + 1];
\r
110 //============================================================================
\r
112 // LZW DISPLAY VECTORS
\r
114 // These vectors allow you to hook up any form of display you desire for
\r
115 // displaying the compression/decompression status.
\r
117 // These routines are called inside of the compression/decompression routines
\r
118 // and pass the orginal size of data and current position within that
\r
119 // data. This allows for any kind of "% Done" messages.
\r
121 // Your functions MUST have the following parameters in this order...
\r
123 // void VectorRoutine(unsigned long OrginalSize,unsigned long CurPosition)
\r
127 void (*LZW_CompressDisplayVector)() = NULL;
\r
128 void (*LZW_DecompressDisplayVector)() = NULL;
\r
133 //============================================================================
\r
135 // SUPPORT ROUTINES FOR LZW COMPRESSION
\r
137 //============================================================================
\r
140 #if INCLUDE_LZW_COMP
\r
142 static void InitLZWTree(void) /* initialize trees */
\r
146 /* For i = 0 to LZW_N - 1, LZW_right_child[i] and LZW_left_child[i] will be the right and
\r
147 left children of node i. These nodes need not be initialized.
\r
148 Also, LZW_parent[i] is the parent of node i. These are initialized to
\r
149 LZW_NIL (= LZW_N), which stands for 'not used.'
\r
150 For i = 0 to 255, LZW_right_child[LZW_N + i + 1] is the root of the tree
\r
151 for strings that begin with character i. These are initialized
\r
152 to LZW_NIL. Note there are 256 trees. */
\r
154 for (i = LZW_N + 1; i <= LZW_N + 256; i++)
\r
155 LZW_right_child[i] = LZW_NIL;
\r
157 for (i = 0; i < LZW_N; i++)
\r
158 LZW_parent[i] = LZW_NIL;
\r
162 ////////////////////////////////////////////////////////////////////////////
\r
164 static void InsertLZWNode(unsigned long r)
\r
166 /* Inserts string of length LZW_F, LZW_ring_buffer[r..r+LZW_F-1], into one of the
\r
167 trees (LZW_ring_buffer[r]'th tree) and returns the longest-match position
\r
168 and length via the global variables LZW_match_pos and LZW_match_len.
\r
169 If LZW_match_len = LZW_F, then removes the old node in favor of the new
\r
170 one, because the old one will be deleted sooner.
\r
171 Note r plays double role, as tree node and position in buffer. */
\r
174 unsigned char *key;
\r
177 key = &LZW_ring_buffer[r];
\r
178 p = LZW_N + 1 + key[0];
\r
179 LZW_right_child[r] = LZW_left_child[r] = LZW_NIL;
\r
186 if (LZW_right_child[p] != LZW_NIL)
\r
187 p = LZW_right_child[p];
\r
190 LZW_right_child[p] = r;
\r
197 if (LZW_left_child[p] != LZW_NIL)
\r
198 p = LZW_left_child[p];
\r
201 LZW_left_child[p] = r;
\r
207 for (i = 1; i < LZW_F; i++)
\r
208 if ((cmp = key[i] - LZW_ring_buffer[p + i]) != 0)
\r
211 if (i > LZW_match_len)
\r
214 if ((LZW_match_len = i) >= LZW_F)
\r
219 LZW_parent[r] = LZW_parent[p];
\r
220 LZW_left_child[r] = LZW_left_child[p];
\r
221 LZW_right_child[r] = LZW_right_child[p];
\r
222 LZW_parent[LZW_left_child[p]] = r;
\r
223 LZW_parent[LZW_right_child[p]] = r;
\r
225 if (LZW_right_child[LZW_parent[p]] == p)
\r
226 LZW_right_child[LZW_parent[p]] = r;
\r
228 LZW_left_child[LZW_parent[p]] = r;
\r
230 LZW_parent[p] = LZW_NIL; /* remove p */
\r
233 ////////////////////////////////////////////////////////////////////////////
\r
235 static void DeleteLZWNode(unsigned long p) /* deletes node p from tree */
\r
239 if (LZW_parent[p] == LZW_NIL)
\r
240 return; /* not in tree */
\r
242 if (LZW_right_child[p] == LZW_NIL)
\r
243 q = LZW_left_child[p];
\r
245 if (LZW_left_child[p] == LZW_NIL)
\r
246 q = LZW_right_child[p];
\r
249 q = LZW_left_child[p];
\r
250 if (LZW_right_child[q] != LZW_NIL)
\r
254 q = LZW_right_child[q];
\r
256 } while (LZW_right_child[q] != LZW_NIL);
\r
258 LZW_right_child[LZW_parent[q]] = LZW_left_child[q];
\r
259 LZW_parent[LZW_left_child[q]] = LZW_parent[q];
\r
260 LZW_left_child[q] = LZW_left_child[p];
\r
261 LZW_parent[LZW_left_child[p]] = q;
\r
264 LZW_right_child[q] = LZW_right_child[p];
\r
265 LZW_parent[LZW_right_child[p]] = q;
\r
268 LZW_parent[q] = LZW_parent[p];
\r
269 if (LZW_right_child[LZW_parent[p]] == p)
\r
270 LZW_right_child[LZW_parent[p]] = q;
\r
272 LZW_left_child[LZW_parent[p]] = q;
\r
274 LZW_parent[p] = LZW_NIL;
\r
279 //--------------------------------------------------------------------------
\r
281 // lzwCompress() - Compresses data from an input ptr to a dest ptr
\r
284 // infile - Pointer at the BEGINNING of the data to compress
\r
285 // outfile - Pointer to the destination (no header).
\r
286 // DataLength - Number of bytes to compress.
\r
287 // PtrTypes - Type of pointers being used (SRC_FILE,DEST_FILE,SRC_MEM etc).
\r
290 // Length of compressed data.
\r
292 // COMPTYPE : ct_LZW
\r
294 // NOTES : Does not write ANY header information!
\r
296 unsigned long lzwCompress(void far *infile, void far *outfile,unsigned long DataLength,unsigned PtrTypes)
\r
299 short c, len, r, s, last_LZW_match_len, code_buf_ptr;
\r
300 unsigned char code_buf[17], mask;
\r
301 unsigned long complen = 0;
\r
303 unsigned CodeCount = 0;
\r
304 unsigned long OrgDataLen = DataLength;
\r
306 // initialize trees
\r
313 // code_buf[1..16] saves eight units of code, and code_buf[0] works
\r
314 // as eight flags, "1" representing that the unit is an unencoded
\r
315 // letter (1 byte), "0" a position-and-length pair (2 bytes). Thus,
\r
316 // eight units require at most 16 bytes of code.
\r
319 code_buf_ptr = mask = 1;
\r
323 // Clear the buffer with any character that will appear often.
\r
326 for (i = s; i < r; i++)
\r
327 LZW_ring_buffer[i] = ' ';
\r
329 // Read LZW_F bytes into the last LZW_F bytes of the buffer
\r
332 for (len = 0; (len < LZW_F) && DataLength; len++)
\r
334 c = ReadPtr((long)&infile,PtrTypes);
\r
337 // text of size zero
\r
339 LZW_ring_buffer[r + len] = c;
\r
342 if (!(len && DataLength))
\r
346 // Insert the LZW_F strings, each of which begins with one or more
\r
347 // 'space' characters. Note the order in which these strings
\r
348 // are inserted. This way, degenerate trees will be less likely
\r
352 for (i = 1; i <= LZW_F; i++)
\r
353 InsertLZWNode(r - i);
\r
356 // Finally, insert the whole string just read. The global
\r
357 // variables LZW_match_len and LZW_match_pos are set. */
\r
363 // LZW_match_len may be spuriously long near the end of text.
\r
366 if (LZW_match_len > len)
\r
367 LZW_match_len = len;
\r
369 if (LZW_match_len <= LZW_THRESHOLD)
\r
371 // Not long enough match. Send one byte.
\r
376 // 'send one byte' flag
\r
379 code_buf[0] |= mask;
\r
384 code_buf[code_buf_ptr++] = LZW_ring_buffer[r];
\r
388 code_buf[code_buf_ptr++] = (unsigned char) LZW_match_pos;
\r
389 code_buf[code_buf_ptr++] = (unsigned char) (((LZW_match_pos >> 4) & 0xf0) | (LZW_match_len - (LZW_THRESHOLD + 1)));
\r
391 // Send position and length pair.
\r
392 // Note LZW_match_len > LZW_THRESHOLD.
\r
395 if ((mask <<= 1) == 0)
\r
397 // Shift mask left one bit.
\r
398 // Send at most 8 units of data
\r
400 for (i = 0; i < code_buf_ptr; i++)
\r
401 WritePtr((long)&outfile,code_buf[i],PtrTypes);
\r
403 complen += code_buf_ptr;
\r
405 code_buf_ptr = mask = 1;
\r
408 last_LZW_match_len = LZW_match_len;
\r
410 for (i = 0; i < last_LZW_match_len && DataLength; i++)
\r
412 c = ReadPtr((long)&infile,PtrTypes);
\r
415 DeleteLZWNode(s); // Delete old strings and
\r
416 LZW_ring_buffer[s] = c; // read new bytes
\r
418 // If the position is near the end of buffer, extend the
\r
419 // buffer to make string comparison easier.
\r
422 LZW_ring_buffer[s + LZW_N] = c;
\r
424 // Since this is a ring buffer, inc the position modulo LZW_N.
\r
427 s = (s + 1) & (LZW_N - 1);
\r
428 r = (r + 1) & (LZW_N - 1);
\r
430 // Register the string in LZW_ring_buffer[r..r+LZW_F-1]
\r
438 // MANAGE DISPLAY VECTOR
\r
441 if (LZW_CompressDisplayVector)
\r
443 // Update display every 1k!
\r
446 if ((CodeCount += i) > 1024)
\r
448 LZW_CompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);
\r
455 // Manage Compression tree..
\r
458 while (i++ < last_LZW_match_len)
\r
460 // After the end of text,
\r
461 DeleteLZWNode(s); // no need to read, but
\r
463 s = (s + 1) & (LZW_N - 1);
\r
464 r = (r + 1) & (LZW_N - 1);
\r
467 InsertLZWNode(r); // buffer may not be empty.
\r
470 } while (len > 0); // until length of string to be processed is zero
\r
473 if (code_buf_ptr > 1)
\r
475 // Send remaining code.
\r
478 for (i = 0; i < code_buf_ptr; i++)
\r
479 WritePtr((long)&outfile,code_buf[i],PtrTypes);
\r
481 complen += code_buf_ptr;
\r
484 if (LZW_CompressDisplayVector)
\r
486 if ((CodeCount += i) > 1024)
\r
488 LZW_CompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);
\r
500 //============================================================================
\r
502 // SUPPORT ROUTINES FOR LZW DECOMPRESSION
\r
504 //============================================================================
\r
506 #if INCLUDE_LZW_DECOMP
\r
508 //--------------------------------------------------------------------------
\r
510 // lzwDecompress() - Compresses data from an input ptr to a dest ptr
\r
513 // infile - Pointer at the BEGINNING of the compressed data (no header!)
\r
514 // outfile - Pointer to the destination.
\r
515 // DataLength - Number of bytes to decompress.
\r
516 // PtrTypes - Type of pointers being used (SRC_FILE,DEST_FILE,SRC_MEM etc).
\r
519 // Length of compressed data.
\r
521 // COMPTYPE : ct_LZW
\r
523 // NOTES : Does not write ANY header information!
\r
525 void lzwDecompress(void far *infile, void far *outfile,unsigned long DataLength,unsigned PtrTypes)
\r
528 unsigned int flags;
\r
529 unsigned char Buffer[8];
\r
530 // unsigned char LZW_ring_buffer[LZW_N + LZW_F - 1];
\r
532 unsigned CodeCount = 0;
\r
533 unsigned long OrgDataLen = DataLength;
\r
535 for (i = 0; i < LZW_N - LZW_F; i++)
\r
536 LZW_ring_buffer[i] = ' ';
\r
543 if (((flags >>= 1) & 256) == 0)
\r
545 c = ReadPtr((long)&infile,PtrTypes);
\r
547 flags = c | 0xff00; // uses higher byte cleverly to count 8
\r
552 c = ReadPtr((long)&infile,PtrTypes); // Could test for EOF iff FFILE type
\r
554 WritePtr((long)&outfile,c,PtrTypes);
\r
559 LZW_ring_buffer[r++] = c;
\r
564 i = ReadPtr((long)&infile,PtrTypes);
\r
566 j = ReadPtr((long)&infile,PtrTypes);
\r
568 i |= ((j & 0xf0) << 4);
\r
569 j = (j & 0x0f) + LZW_THRESHOLD;
\r
571 for (k = 0; k <= j; k++)
\r
573 c = LZW_ring_buffer[(i + k) & (LZW_N - 1)];
\r
575 WritePtr((long)&outfile,c,PtrTypes);
\r
580 LZW_ring_buffer[r++] = c;
\r
588 // MANAGE DISPLAY VECTOR
\r
591 if (LZW_DecompressDisplayVector)
\r
594 // Update DisplayVector every 1K
\r
597 if ((CodeCount+=k) > 1024)
\r
599 LZW_DecompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);
\r