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