16/cawat/LZW.C

   1 /* Catacomb Armageddon Source Code\r
   2  * Copyright (C) 1993-2014 Flat Rock Software\r
   3  *\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
   8  *\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
  13  *\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
  17  */\r
  18 \r
  19 //===========================================================================\r
  20 //\r
  21 //                                                                LZW COMPRESSION ROUTINES\r
  22 //                                                                                VERSION 1.1\r
  23 //\r
  24 //                              Compression algrythim by Haruhiko OKUMURA\r
  25 //                                              Implementation by Jim T. Row\r
  26 //\r
  27 //\r
  28 //   Copyright (c) 1992 - Softdisk Publishing inc. - All rights reserved\r
  29 //\r
  30 //===========================================================================\r
  31 //\r
  32 //\r
  33 //---------------------------------------------------------------------------\r
  34 \r
  35 \r
  36 #include <stdio.h>\r
  37 #include <stdlib.h>\r
  38 #include <string.h>\r
  39 #include <ctype.h>\r
  40 #include <alloc.h>\r
  41 #include <fcntl.h>\r
  42 #include <dos.h>\r
  43 #include <io.h>\r
  44 \r
  45 #include "lzw.h"\r
  46 #include "jam_io.h"\r
  47 \r
  48 \r
  49 //===========================================================================\r
  50 //\r
  51 //                                                                                      SWITCHES\r
  52 //\r
  53 // NOTE : Make sure the appropriate switches are set in SOFT.c for Softlib\r
  54 //                       archive support.\r
  55 //\r
  56 //===========================================================================\r
  57 \r
  58 #define INCLUDE_LZW_COMP                        0\r
  59 #define INCLUDE_LZW_DECOMP                      1\r
  60 \r
  61 \r
  62 //===========================================================================\r
  63 //\r
  64 //                                                                                      DEFINES\r
  65 //\r
  66 //===========================================================================\r
  67 \r
  68 \r
  69 #define LZW_N                                                   4096\r
  70 #define LZW_F                                                   18\r
  71 \r
  72 #define LZW_THRESHOLD                           2               // encode string into position and\r
  73                                                                                                         // length if match_length is greater\r
  74                                                                                                         // than this\r
  75 \r
  76 #define LZW_NIL                         LZW_N    // index for root of bin search trees\r
  77 \r
  78 \r
  79 //============================================================================\r
  80 //\r
  81 //                                                              GLOBAL VARIABLES NECESSARY FOR\r
  82 //\r
  83 //                                                       COMP/DECOMP ROUTINES.\r
  84 //\r
  85 //============================================================================\r
  86 \r
  87 \r
  88 \r
  89 unsigned char far LZW_ring_buffer[LZW_N + LZW_F - 1];   // ring buffer of size\r
  90                                                                                                                                                   // LZW_N, with extra\r
  91                                                                                                                                                   // LZW_F-1 bytes to\r
  92                                                                                                                                                   // facilitate\r
  93                                                                                                                                                   // string comparison\r
  94 \r
  95 #if INCLUDE_LZW_COMP\r
  96 \r
  97 int LZW_match_pos,      // MAtchLength of longest match.  These are set by the\r
  98                                                         // InsertNode() procedure.\r
  99          LZW_match_len,\r
 100 \r
 101         // left & right children & parents -- These constitute binary search trees. */\r
 102 \r
 103         LZW_left_child[LZW_N + 1],\r
 104         LZW_right_child[LZW_N + 257],\r
 105         LZW_parent[LZW_N + 1];\r
 106 \r
 107 #endif\r
 108 \r
 109 \r
 110 //============================================================================\r
 111 //\r
 112 //                                                                      LZW DISPLAY VECTORS\r
 113 //\r
 114 // These vectors allow you to hook up any form of display you desire for\r
 115 // displaying the compression/decompression status.\r
 116 //\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
 120 //\r
 121 // Your functions MUST have the following parameters in this order...\r
 122 //\r
 123 //   void VectorRoutine(unsigned long OrginalSize,unsigned long CurPosition)\r
 124 //\r
 125 //\r
 126 \r
 127 void (*LZW_CompressDisplayVector)() = NULL;\r
 128 void (*LZW_DecompressDisplayVector)() = NULL;\r
 129 \r
 130 \r
 131 \r
 132 \r
 133 //============================================================================\r
 134 //\r
 135 //                                                      SUPPORT ROUTINES FOR LZW COMPRESSION\r
 136 //\r
 137 //============================================================================\r
 138 \r
 139 \r
 140 #if INCLUDE_LZW_COMP\r
 141 \r
 142 static void InitLZWTree(void)  /* initialize trees */\r
 143 {\r
 144          int i;\r
 145 \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
 153 \r
 154          for (i = LZW_N + 1; i <= LZW_N + 256; i++)\r
 155                 LZW_right_child[i] = LZW_NIL;\r
 156 \r
 157          for (i = 0; i < LZW_N; i++)\r
 158                 LZW_parent[i] = LZW_NIL;\r
 159 }\r
 160 \r
 161 \r
 162 ////////////////////////////////////////////////////////////////////////////\r
 163 \r
 164 static void InsertLZWNode(unsigned long r)\r
 165 \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
 172 {\r
 173          int  i, p, cmp;\r
 174          unsigned char *key;\r
 175 \r
 176          cmp = 1;\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
 180          LZW_match_len = 0;\r
 181 \r
 182         for ( ; ; )\r
 183         {\r
 184                 if (cmp >= 0)\r
 185                 {\r
 186                         if (LZW_right_child[p] != LZW_NIL)\r
 187                                 p = LZW_right_child[p];\r
 188                         else\r
 189                         {\r
 190                                 LZW_right_child[p] = r;\r
 191                                 LZW_parent[r] = p;\r
 192                                 return;\r
 193                         }\r
 194                 }\r
 195                 else\r
 196                 {\r
 197                         if (LZW_left_child[p] != LZW_NIL)\r
 198                                 p = LZW_left_child[p];\r
 199                         else\r
 200                         {\r
 201                                 LZW_left_child[p] = r;\r
 202                                 LZW_parent[r] = p;\r
 203                                 return;\r
 204                         }\r
 205                 }\r
 206 \r
 207                 for (i = 1; i < LZW_F; i++)\r
 208                         if ((cmp = key[i] - LZW_ring_buffer[p + i]) != 0)\r
 209                                 break;\r
 210 \r
 211                 if (i > LZW_match_len)\r
 212                 {\r
 213                         LZW_match_pos = p;\r
 214                         if ((LZW_match_len = i) >= LZW_F)\r
 215                                 break;\r
 216                 }\r
 217         }\r
 218 \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
 224 \r
 225         if (LZW_right_child[LZW_parent[p]] == p)\r
 226                 LZW_right_child[LZW_parent[p]] = r;\r
 227         else\r
 228                 LZW_left_child[LZW_parent[p]] = r;\r
 229 \r
 230         LZW_parent[p] = LZW_NIL;  /* remove p */\r
 231 }\r
 232 \r
 233 ////////////////////////////////////////////////////////////////////////////\r
 234 \r
 235 static void DeleteLZWNode(unsigned long p)  /* deletes node p from tree */\r
 236 {\r
 237         int q;\r
 238 \r
 239         if (LZW_parent[p] == LZW_NIL)\r
 240                 return;                                          /* not in tree */\r
 241 \r
 242         if (LZW_right_child[p] == LZW_NIL)\r
 243                 q = LZW_left_child[p];\r
 244         else\r
 245         if (LZW_left_child[p] == LZW_NIL)\r
 246                 q = LZW_right_child[p];\r
 247         else\r
 248         {\r
 249                 q = LZW_left_child[p];\r
 250                 if (LZW_right_child[q] != LZW_NIL)\r
 251                 {\r
 252                         do {\r
 253 \r
 254                                 q = LZW_right_child[q];\r
 255 \r
 256                         } while (LZW_right_child[q] != LZW_NIL);\r
 257 \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
 262                 }\r
 263 \r
 264                 LZW_right_child[q] = LZW_right_child[p];\r
 265                 LZW_parent[LZW_right_child[p]] = q;\r
 266          }\r
 267 \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
 271          else\r
 272                 LZW_left_child[LZW_parent[p]] = q;\r
 273 \r
 274          LZW_parent[p] = LZW_NIL;\r
 275 }\r
 276 \r
 277 \r
 278 \r
 279 //--------------------------------------------------------------------------\r
 280 //\r
 281 // lzwCompress() - Compresses data from an input ptr to a dest ptr\r
 282 //\r
 283 // PARAMS:\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
 288 //\r
 289 // RETURNS:\r
 290 //          Length of compressed data.\r
 291 //\r
 292 //      COMPTYPE : ct_LZW\r
 293 //\r
 294 // NOTES    : Does not write ANY header information!\r
 295 //\r
 296 unsigned long lzwCompress(void far *infile, void far *outfile,unsigned long DataLength,unsigned PtrTypes)\r
 297 {\r
 298         short i;\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
 302 \r
 303         unsigned CodeCount = 0;\r
 304         unsigned long OrgDataLen = DataLength;\r
 305 \r
 306         // initialize trees\r
 307 \r
 308         InitLZWTree();\r
 309 \r
 310         code_buf[0] = 0;\r
 311 \r
 312         //\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
 317         //\r
 318 \r
 319          code_buf_ptr = mask = 1;\r
 320          s = 0;\r
 321          r = LZW_N - LZW_F;\r
 322 \r
 323         // Clear the buffer with any character that will appear often.\r
 324         //\r
 325 \r
 326          for (i = s; i < r; i++)\r
 327                         LZW_ring_buffer[i] = ' ';\r
 328 \r
 329         // Read LZW_F bytes into the last LZW_F bytes of the buffer\r
 330         //\r
 331 \r
 332          for (len = 0; (len < LZW_F) && DataLength; len++)\r
 333          {\r
 334                 c = ReadPtr((long)&infile,PtrTypes);\r
 335                 DataLength--;\r
 336 \r
 337                 // text of size zero\r
 338 \r
 339                 LZW_ring_buffer[r + len] = c;\r
 340          }\r
 341 \r
 342          if (!(len && DataLength))\r
 343                 return(0);\r
 344 \r
 345         //\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
 349         // to occur.\r
 350         //\r
 351 \r
 352          for (i = 1; i <= LZW_F; i++)\r
 353                         InsertLZWNode(r - i);\r
 354 \r
 355         //\r
 356         // Finally, insert the whole string just read.  The global\r
 357         // variables LZW_match_len and LZW_match_pos are set. */\r
 358         //\r
 359 \r
 360          InsertLZWNode(r);\r
 361 \r
 362          do {\r
 363                         // LZW_match_len may be spuriously long near the end of text.\r
 364                         //\r
 365 \r
 366                         if (LZW_match_len > len)\r
 367                                 LZW_match_len = len;\r
 368 \r
 369                         if (LZW_match_len <= LZW_THRESHOLD)\r
 370                         {\r
 371                                   // Not long enough match.  Send one byte.\r
 372                                   //\r
 373 \r
 374                                   LZW_match_len = 1;\r
 375 \r
 376                                   // 'send one byte' flag\r
 377                                   //\r
 378 \r
 379                                   code_buf[0] |= mask;\r
 380 \r
 381                                   // Send uncoded.\r
 382                                   //\r
 383 \r
 384                                   code_buf[code_buf_ptr++] = LZW_ring_buffer[r];\r
 385                         }\r
 386                         else\r
 387                         {\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
 390 \r
 391                                 // Send position and length pair.\r
 392                                 // Note LZW_match_len > LZW_THRESHOLD.\r
 393                         }\r
 394 \r
 395                         if ((mask <<= 1) == 0)\r
 396                         {\r
 397                                 // Shift mask left one bit.\r
 398                                 // Send at most 8 units of data\r
 399 \r
 400                                 for (i = 0; i < code_buf_ptr; i++)\r
 401                                         WritePtr((long)&outfile,code_buf[i],PtrTypes);\r
 402 \r
 403                                 complen += code_buf_ptr;\r
 404                                 code_buf[0] = 0;\r
 405                                 code_buf_ptr = mask = 1;\r
 406                         }\r
 407 \r
 408                         last_LZW_match_len = LZW_match_len;\r
 409 \r
 410                         for (i = 0; i < last_LZW_match_len && DataLength; i++)\r
 411                         {\r
 412                                 c = ReadPtr((long)&infile,PtrTypes);\r
 413                                 DataLength--;\r
 414 \r
 415                                 DeleteLZWNode(s);                           // Delete old strings and\r
 416                                 LZW_ring_buffer[s] = c;                                          // read new bytes\r
 417 \r
 418                                 // If the position is near the end of buffer, extend the\r
 419                                 //      buffer to make string comparison easier.\r
 420 \r
 421                                 if (s < LZW_F - 1)\r
 422                                         LZW_ring_buffer[s + LZW_N] = c;\r
 423 \r
 424                                 // Since this is a ring buffer, inc the position modulo LZW_N.\r
 425                                 //\r
 426 \r
 427                                 s = (s + 1) & (LZW_N - 1);\r
 428                                 r = (r + 1) & (LZW_N - 1);\r
 429 \r
 430                                 // Register the string in LZW_ring_buffer[r..r+LZW_F-1]\r
 431                                 //\r
 432 \r
 433                                 InsertLZWNode(r);\r
 434                         }\r
 435 \r
 436 \r
 437                         //\r
 438                         // MANAGE DISPLAY VECTOR\r
 439                         //\r
 440 \r
 441                         if (LZW_CompressDisplayVector)\r
 442                         {\r
 443                                 // Update display every 1k!\r
 444                                 //\r
 445 \r
 446                                 if ((CodeCount += i) > 1024)\r
 447                                 {\r
 448                                         LZW_CompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);\r
 449                                         CodeCount = 0;\r
 450                                 }\r
 451                         }\r
 452 \r
 453 \r
 454                         //\r
 455                         // Manage Compression tree..\r
 456                         //\r
 457 \r
 458                         while (i++ < last_LZW_match_len)\r
 459                         {\r
 460                                                                                                                   // After the end of text,\r
 461                                 DeleteLZWNode(s);               // no need to read, but\r
 462 \r
 463                                 s = (s + 1) & (LZW_N - 1);\r
 464                                 r = (r + 1) & (LZW_N - 1);\r
 465 \r
 466                                 if (--len)\r
 467                                         InsertLZWNode(r);          // buffer may not be empty.\r
 468                         }\r
 469 \r
 470          } while (len > 0);  // until length of string to be processed is zero\r
 471 \r
 472 \r
 473          if (code_buf_ptr > 1)\r
 474          {\r
 475                 // Send remaining code.\r
 476                 //\r
 477 \r
 478                 for (i = 0; i < code_buf_ptr; i++)\r
 479                         WritePtr((long)&outfile,code_buf[i],PtrTypes);\r
 480 \r
 481                 complen += code_buf_ptr;\r
 482          }\r
 483 \r
 484         if (LZW_CompressDisplayVector)\r
 485         {\r
 486                 if ((CodeCount += i) > 1024)\r
 487                 {\r
 488                         LZW_CompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);\r
 489                 }\r
 490         }\r
 491 \r
 492          return(complen);\r
 493 }\r
 494 \r
 495 #endif\r
 496 \r
 497 \r
 498 \r
 499 \r
 500 //============================================================================\r
 501 //\r
 502 //                                                      SUPPORT ROUTINES FOR LZW DECOMPRESSION\r
 503 //\r
 504 //============================================================================\r
 505 \r
 506 #if INCLUDE_LZW_DECOMP\r
 507 \r
 508 //--------------------------------------------------------------------------\r
 509 //\r
 510 // lzwDecompress() - Compresses data from an input ptr to a dest ptr\r
 511 //\r
 512 // PARAMS:\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
 517 //\r
 518 // RETURNS:\r
 519 //          Length of compressed data.\r
 520 //\r
 521 //      COMPTYPE : ct_LZW\r
 522 //\r
 523 // NOTES    : Does not write ANY header information!\r
 524 //\r
 525 void lzwDecompress(void far *infile, void far *outfile,unsigned long DataLength,unsigned PtrTypes)\r
 526 {\r
 527         int  i, j, k, r, c;\r
 528         unsigned int flags;\r
 529         unsigned char Buffer[8];\r
 530 //      unsigned char LZW_ring_buffer[LZW_N + LZW_F - 1];\r
 531 \r
 532         unsigned CodeCount = 0;\r
 533         unsigned long OrgDataLen = DataLength;\r
 534 \r
 535         for (i = 0; i < LZW_N - LZW_F; i++)\r
 536                 LZW_ring_buffer[i] = ' ';\r
 537 \r
 538          r = LZW_N - LZW_F;\r
 539          flags = 0;\r
 540 \r
 541          for ( ; ; )\r
 542          {\r
 543                         if (((flags >>= 1) & 256) == 0)\r
 544                         {\r
 545                                 c = ReadPtr((long)&infile,PtrTypes);\r
 546 \r
 547                                 flags = c | 0xff00;      // uses higher byte cleverly to count 8\r
 548                         }\r
 549 \r
 550                         if (flags & 1)\r
 551                         {\r
 552                                 c = ReadPtr((long)&infile,PtrTypes);            // Could test for EOF iff FFILE type\r
 553 \r
 554                                 WritePtr((long)&outfile,c,PtrTypes);\r
 555 \r
 556                                 if (!--DataLength)\r
 557                                         return;\r
 558 \r
 559                                 LZW_ring_buffer[r++] = c;\r
 560                                 r &= (LZW_N - 1);\r
 561                         }\r
 562                         else\r
 563                         {\r
 564                                 i = ReadPtr((long)&infile,PtrTypes);\r
 565 \r
 566                                 j = ReadPtr((long)&infile,PtrTypes);\r
 567 \r
 568                                 i |= ((j & 0xf0) << 4);\r
 569                                 j = (j & 0x0f) + LZW_THRESHOLD;\r
 570 \r
 571                                 for (k = 0; k <= j; k++)\r
 572                                 {\r
 573                                          c = LZW_ring_buffer[(i + k) & (LZW_N - 1)];\r
 574 \r
 575                                          WritePtr((long)&outfile,c,PtrTypes);\r
 576 \r
 577                                          if (!--DataLength)\r
 578                                                 return;\r
 579 \r
 580                                          LZW_ring_buffer[r++] = c;\r
 581                                          r &= (LZW_N - 1);\r
 582                                 }\r
 583                         }\r
 584 \r
 585 \r
 586 \r
 587                         //\r
 588                         //      MANAGE DISPLAY VECTOR\r
 589                         //\r
 590 \r
 591                         if (LZW_DecompressDisplayVector)\r
 592                         {\r
 593                                 //\r
 594                                 // Update DisplayVector every 1K\r
 595                                 //\r
 596 \r
 597                                 if ((CodeCount+=k) > 1024)\r
 598                                 {\r
 599                                         LZW_DecompressDisplayVector(OrgDataLen,OrgDataLen-DataLength);\r
 600                                         CodeCount = 0;\r
 601                                 }\r
 602                         }\r
 603 \r
 604          }\r
 605 }\r
 606 \r
 607 #endif\r
 608 \r