utils/Install/sfxace/uac_dcpr.c

   1 /* ------------------------------------------------------------------------ */
   2 /*                                                                          */
   3 /*      These are the decompression algorithms.                             */
   4 /*      Don't change here anything (apart from memory allocation perhaps).  */
   5 /*      Any changes will very likely cause bugs!                            */
   6 /*                                                                          */
   7 /* ------------------------------------------------------------------------ */
   8
   9 #include "os.h"
  10
  11 #if defined(AMIGA)
  12  #include <string.h> // mem*()
  13 #endif
  14 #if defined(DOS) || defined(WIN16) || defined(WINNT) || defined(OS2) || defined(UNIX)
  15 #if !defined(__CYGWIN__)
  16  #include <mem.h>    // mem*()
  17 #endif
  18 #endif
  19
  20 #include <stdio.h>   // printf()
  21 #include <stdlib.h>  // malloc()
  22 #include <string.h>
  23
  24
  25 #include "globals.h"
  26 #include "portable.h"
  27 #include "uac_comm.h"
  28 #include "uac_crc.h"
  29 #include "uac_dcpr.h"
  30 #include "uac_sys.h"
  31 #ifdef CRYPT
  32  #include "unace_ps.h"
  33 #endif /* CRYPT */
  34
  35
  36 //------------------------------ QUICKSORT ---------------------------------//
  37 #define xchg_def(v1,v2) {INT dummy;\
  38                          dummy=v1; \
  39                          v1=v2;    \
  40                          v2=dummy;}
  41
  42 void sortrange(INT left, INT right)
  43 {
  44         INT  zl = left,
  45         zr = right,
  46         hyphen;
  47
  48         hyphen = sort_freq[right];
  49
  50         //divides by hyphen the given range into 2 parts
  51         do
  52         {
  53                 while (sort_freq[zl] > hyphen)
  54                         zl++;
  55                 while (sort_freq[zr] < hyphen)
  56                         zr--;
  57                 //found a too small (left side) and
  58                 //a too big (right side) element-->exchange them
  59                 if (zl <= zr)
  60                 {
  61                         xchg_def(sort_freq[zl], sort_freq[zr]);
  62                         xchg_def(sort_org[zl], sort_org[zr]);
  63                         zl++;
  64                         zr--;
  65                 }
  66         }
  67         while (zl < zr);
  68
  69         //sort partial ranges - when very small, sort directly
  70         if (left < zr)
  71         {
  72                 if (left < zr - 1)
  73                         sortrange(left, zr);
  74                 else if (sort_freq[left] < sort_freq[zr])
  75                 {
  76                         xchg_def(sort_freq[left], sort_freq[zr]);
  77                         xchg_def(sort_org[left], sort_org[zr]);
  78                 }
  79         }
  80
  81         if (right > zl)
  82         {
  83                 if (zl < right - 1)
  84                         sortrange(zl, right);
  85                 else if (sort_freq[zl] < sort_freq[right])
  86                 {
  87                         xchg_def(sort_freq[zl], sort_freq[right]);
  88                         xchg_def(sort_org[zl], sort_org[right]);
  89                 }
  90         }
  91 }
  92
  93 void quicksort(INT n)
  94 {
  95         INT  i;
  96
  97         for (i = n + 1; i--;)
  98                 sort_org[i] = i;
  99         sortrange(0, n);
 100 }
 101
 102 //------------------------------ read bits ---------------------------------//
 103 void readdat(void)
 104 {
 105         UINT i;
 106
 107         i = (size_rdb - 2) << 2;
 108         rpos -= size_rdb - 2;
 109         buf_rd[0] = buf_rd[size_rdb - 2];
 110         buf_rd[1] = buf_rd[size_rdb - 1];
 111         read_adds_blk((CHAR *) & buf_rd[2], i);
 112 #ifdef HI_LO_BYTE_ORDER
 113         {
 114                 ULONG *p;
 115                 i>>=2;    // count LONGs not BYTEs
 116                 p=&buf_rd[2];
 117                 while (i--)
 118                 {
 119                         LONGswap(p);
 120                         p++;
 121                 }
 122         }
 123 #endif
 124 }
 125
 126 #define addbits(bits)                                   \
 127 {                                                       \
 128         rpos+=(bits_rd+=bits)>>5;                             \
 129         bits_rd&=31;                                          \
 130         if (rpos==(size_rdb-2)) readdat();                    \
 131         code_rd=(buf_rd[rpos] << bits_rd)                     \
 132         +((buf_rd[rpos+1] >> (32-bits_rd))&(!bits_rd-1));   \
 133         }
 134
 135
 136 //---------------------- COMMENT DECOMPRESSION -----------------------------//
 137
 138 #define comm_cpr_hf(a,b) (a+b)
 139
 140 void dcpr_comm_init(void)
 141 {
 142         INT  i;
 143
 144         i = comm_cpr_size > size_rdb * sizeof(LONG) ? size_rdb * sizeof(LONG) : comm_cpr_size;
 145         if (!f_err)
 146                 memcpy(buf_rd, comm, i);
 147 #ifdef HI_LO_BYTE_ORDER
 148         {
 149                 ULONG *p;
 150                 i>>=2;    // count LONGs not BYTEs
 151                 p=buf_rd;
 152                 while (i--)
 153                 {
 154                         LONGswap(p);
 155                         p++;
 156                 }
 157         }
 158 #endif
 159         code_rd = buf_rd[0];
 160         rpos = bits_rd = 0;
 161 }
 162
 163 void dcpr_comm(INT comm_size)
 164 {
 165         SHORT hash[comm_cpr_hf(255, 255) + 1];
 166         INT  dpos = 0,
 167                 c,
 168         pos = 0,
 169         len,
 170         hs;
 171
 172         memset(&hash, 0, sizeof(hash));
 173         if (comm_cpr_size)
 174         {
 175                 dcpr_comm_init();
 176                 len = code_rd >> (32 - 15);
 177                 addbits(15);
 178                 if (len >= comm_size)
 179                         len = comm_size - 1;
 180                 if (read_wd(maxwd_mn, dcpr_code_mn, dcpr_wd_mn, max_cd_mn))
 181                         do
 182                 {
 183                         if (dpos > 1)
 184                         {
 185                                 pos = hash[hs = comm_cpr_hf(comm[dpos - 1], comm[dpos - 2])];
 186                                 hash[hs] = dpos;
 187                         }
 188                         addbits(dcpr_wd_mn[(c = dcpr_code_mn[code_rd >> (32 - maxwd_mn)])]);
 189                         if (rpos == size_rdb - 3)
 190                                 rpos = 0;
 191                         if (c > 255)
 192                         {
 193                                 c -= 256;
 194                                 c += 2;
 195                                 while (c--)
 196                                         comm[dpos++] = comm[pos++];
 197                         }
 198                         else
 199                         {
 200                                 comm[dpos++] = c;
 201                         }
 202                 }
 203                 while (dpos < len);
 204                 comm[len] = 0;
 205         }
 206 }
 207
 208 //------------------------- LZW1 DECOMPRESSION -----------------------------//
 209 void wrchar(CHAR ch)
 210 {
 211         dcpr_do++;
 212
 213         dcpr_text[dcpr_dpos] = ch;
 214         dcpr_dpos++;
 215         dcpr_dpos &= dcpr_dican;
 216 }
 217
 218 void copystr(LONG d, INT l)
 219 {
 220         INT  mpos;
 221
 222         dcpr_do += l;
 223
 224         mpos = dcpr_dpos - d;
 225         mpos &= dcpr_dican;
 226
 227         if ((mpos >= dcpr_dicsiz - maxlength) || (dcpr_dpos >= dcpr_dicsiz - maxlength))
 228         {
 229                 while (l--)
 230                 {
 231                         dcpr_text[dcpr_dpos] = dcpr_text[mpos];
 232                         dcpr_dpos++;
 233                         dcpr_dpos &= dcpr_dican;
 234                         mpos++;
 235                         mpos &= dcpr_dican;
 236                 }
 237         }
 238         else
 239         {
 240                 while (l--)
 241                         dcpr_text[dcpr_dpos++] = dcpr_text[mpos++];
 242                 dcpr_dpos &= dcpr_dican;
 243         }
 244 }
 245
 246 void decompress(void)
 247 {
 248         INT  c,
 249         lg,
 250         i,
 251         k;
 252         ULONG dist;
 253
 254         while (dcpr_do < dcpr_do_max)
 255         {
 256                 if (!blocksize)
 257                         if (!calc_dectabs())
 258                                 return;
 259
 260                 addbits(dcpr_wd_mn[(c = dcpr_code_mn[code_rd >> (32 - maxwd_mn)])]);
 261                 blocksize--;
 262                 if (c > 255)
 263                 {
 264                         if (c > 259)
 265                         {
 266                                 if ((c -= 260) > 1)
 267                                 {
 268                                         dist = (code_rd >> (33 - c)) + (1L << (c - 1));
 269                                         addbits(c - 1);
 270                                 }
 271                                 else
 272                                         dist = c;
 273                                 dcpr_olddist[(dcpr_oldnum = (dcpr_oldnum + 1) & 3)] = dist;
 274                                 i = 2;
 275                                 if (dist > maxdis2)
 276                                 {
 277                                         i++;
 278                                         if (dist > maxdis3)
 279                                                 i++;
 280                                 }
 281                         }
 282                         else
 283                         {
 284                                 dist = dcpr_olddist[(dcpr_oldnum - (c &= 255)) & 3];
 285                                 for (k = c + 1; k--;)
 286                                         dcpr_olddist[(dcpr_oldnum - k) & 3] = dcpr_olddist[(dcpr_oldnum - k + 1) & 3];
 287                                 dcpr_olddist[dcpr_oldnum] = dist;
 288                                 i = 2;
 289                                 if (c > 1)
 290                                         i++;
 291                         }
 292                         addbits(dcpr_wd_lg[(lg = dcpr_code_lg[code_rd >> (32 - maxwd_lg)])]);
 293                         dist++;
 294                         lg += i;
 295                         copystr(dist, lg);
 296                 }
 297                 else
 298                         wrchar(c);
 299         }
 300 }
 301
 302 //-------------------------- HUFFMAN ROUTINES ------------------------------//
 303 INT  makecode(UINT maxwd, UINT size1_t, UCHAR * wd, USHORT * code)
 304 {
 305         UINT maxc,
 306         size2_t,
 307         l,
 308         c,
 309         i,
 310         max_make_code;
 311
 312         memcpy(&sort_freq, wd, (size1_t + 1) * sizeof(CHAR));
 313         if (size1_t)
 314                 quicksort(size1_t);
 315         else
 316                 sort_org[0] = 0;
 317         sort_freq[size1_t + 1] = size2_t = c = 0;
 318         while (sort_freq[size2_t])
 319                 size2_t++;
 320         if (size2_t < 2)
 321         {
 322                 i = sort_org[0];
 323                 wd[i] = 1;
 324                 size2_t += (size2_t == 0);
 325         }
 326         size2_t--;
 327
 328         max_make_code = 1 << maxwd;
 329         for (i = size2_t + 1; i-- && c < max_make_code;)
 330         {
 331                 maxc = 1 << (maxwd - sort_freq[i]);
 332                 l = sort_org[i];
 333                 if (c + maxc > max_make_code)
 334                 {
 335                         dcpr_do = dcpr_do_max;
 336                         return (0);
 337                 }
 338                 memset16(&code[c], l, maxc);
 339                 c += maxc;
 340         }
 341         return (1);
 342 }
 343
 344 INT  read_wd(UINT maxwd, USHORT * code, UCHAR * wd, INT max_el)
 345 {
 346         UINT c,
 347         i,
 348         j,
 349         num_el,
 350         l,
 351         uplim,
 352         lolim;
 353
 354         memset(wd, 0, max_el * sizeof(CHAR));
 355         memset(code, 0, (1 << maxwd) * sizeof(SHORT));
 356
 357         num_el = code_rd >> (32 - 9);
 358         addbits(9);
 359         if (num_el > max_el)
 360                 num_el = max_el;
 361
 362         lolim = code_rd >> (32 - 4);
 363         addbits(4);
 364         uplim = code_rd >> (32 - 4);
 365         addbits(4);
 366
 367         for (i = -1; ++i <= uplim;)
 368         {
 369                 wd_svwd[i] = code_rd >> (32 - 3);
 370                 addbits(3);
 371         }
 372         if (!makecode(maxwd_svwd, uplim, wd_svwd, code))
 373                 return (0);
 374         j = 0;
 375         while (j <= num_el)
 376         {
 377                 c = code[code_rd >> (32 - maxwd_svwd)];
 378                 addbits(wd_svwd[c]);
 379                 if (c < uplim)
 380                         wd[j++] = c;
 381                 else
 382                 {
 383                         l = (code_rd >> 28) + 4;
 384                         addbits(4);
 385                         while (l-- && j <= num_el)
 386                                 wd[j++] = 0;
 387                 }
 388         }
 389         if (uplim)
 390                 for (i = 0; ++i <= num_el;)
 391                         wd[i] = (wd[i] + wd[i - 1]) % uplim;
 392         for (i = -1; ++i <= num_el;)
 393                 if (wd[i])
 394                         wd[i] += lolim;
 395
 396         return (makecode(maxwd, num_el, wd, code));
 397
 398 }
 399
 400 INT  calc_dectabs(void)
 401 {
 402         if (!read_wd(maxwd_mn, dcpr_code_mn, dcpr_wd_mn, max_cd_mn)
 403                 || !read_wd(maxwd_lg, dcpr_code_lg, dcpr_wd_lg, max_cd_lg))
 404                 return (0);
 405
 406         blocksize = code_rd >> (32 - 15);
 407         addbits(15);
 408
 409         return (1);
 410 }
 411
 412 //---------------------------- BLOCK ROUTINES ------------------------------//
 413 INT  decompress_blk(CHAR * buf, UINT len)
 414 {
 415         LONG old_pos = dcpr_dpos;
 416         INT  i;
 417
 418         dcpr_do = 0;
 419         if ((dcpr_do_max = len - maxlength) > dcpr_size)
 420                 dcpr_do_max = dcpr_size;
 421         if ((LONG) dcpr_size > 0 && dcpr_do_max)
 422         {
 423                 decompress();
 424                 if (old_pos + dcpr_do > dcpr_dicsiz)
 425                 {
 426                         i = dcpr_dicsiz - old_pos;
 427                         memcpy(buf, &dcpr_text[old_pos], i);
 428                         memcpy(&buf[i], dcpr_text, dcpr_do - i);
 429                 }
 430                 else
 431                         memcpy(buf, &dcpr_text[old_pos], dcpr_do);
 432         }
 433         dcpr_size -= dcpr_do;
 434         return (dcpr_do);
 435 }
 436
 437 INT unstore(CHAR * buf, UINT len)
 438 {
 439         UINT rd = 0,
 440         i,
 441         pos = 0;
 442
 443 #ifdef CRYPT
 444         len = crypt_len(len - 8);    /* because of decryption */
 445 #endif /* CRYPT */
 446
 447         while ((i = read_adds_blk((CHAR *) buf_rd, (INT) ((i = ((len > dcpr_size) ? dcpr_size : len)) > size_rdb ? size_rdb : i))) != 0)
 448         {
 449                 rd += i;
 450                 len -= i;
 451                 memcpy(&buf[pos], buf_rd, i);
 452                 pos += i;
 453         }
 454         dcpr_size -= rd;
 455         for (i = 0; i < rd; i++)
 456         {
 457                 dcpr_text[dcpr_dpos] = buf[i];
 458                 dcpr_dpos++;
 459                 dcpr_dpos &= dcpr_dican;
 460         }
 461         return (INT)rd;
 462 }
 463
 464 INT  dcpr_adds_blk(CHAR * buf, UINT len)
 465 {
 466         INT  r;
 467
 468         switch (fhead.TECH.TYPE)
 469         {
 470         case TYPE_STORE:
 471                 r = unstore(buf, len);
 472                 break;
 473         case TYPE_LZW1:
 474                 r = decompress_blk(buf, len);
 475                 break;
 476         default:
 477                 error("\nFile compressed with unknown method. Decompression not possible.\n");
 478                 f_err = ERR_OTHER;
 479                 r = 0;
 480         }
 481         rd_crc = getcrc(rd_crc, (UCHAR*)buf, r);
 482         return r;
 483 }
 484
 485
 486 //----------------------------- INIT ROUTINES ------------------------------//
 487 void dcpr_init(void)
 488 {
 489         dcpr_frst_file = 1;
 490
 491         dcpr_dic = 20;
 492         while ((dcpr_text = malloc(dcpr_dicsiz = (LONG) 1 << dcpr_dic))==NULL)
 493                 dcpr_dic--;
 494         dcpr_dican = dcpr_dicsiz - 1;
 495 }
 496
 497 void dcpr_init_file(void)
 498 {
 499         UINT i;
 500
 501 #ifdef CRYPT
 502
 503         reset_cryptkey();
 504
 505 #else /* CRYPT */
 506
 507         if (head.HEAD_FLAGS & ACE_PASSW)
 508         {
 509                 error("\nFound passworded file. Decryption not supported.\n");
 510                 f_err = ERR_OTHER;
 511                 return;
 512         }
 513
 514 #endif /* CRYPT */
 515
 516         rd_crc = CRC_MASK;
 517         dcpr_size = fhead.SIZE;
 518         if (fhead.TECH.TYPE == TYPE_LZW1)
 519         {
 520                 if ((fhead.TECH.PARM & 15) + 10 > dcpr_dic)
 521                 {
 522                         error("\nNot enough memory or dictionary of archive too large.\n");
 523                         f_err = ERR_MEM;
 524                         return;
 525                 }
 526
 527                 i = size_rdb * sizeof(LONG);
 528                 read_adds_blk((CHAR *) buf_rd, i);
 529 #ifdef HI_LO_BYTE_ORDER
 530                 {
 531                         ULONG *p;
 532                         i>>=2;    // count LONGs not BYTEs
 533                         p=buf_rd;
 534                         while (i--)
 535                         {
 536                                 LONGswap(p);
 537                                 p++;
 538                         }
 539                 }
 540 #endif
 541                 code_rd = buf_rd[0];
 542                 bits_rd = rpos = 0;
 543
 544                 blocksize = 0;
 545         }
 546         if (!adat.sol || dcpr_frst_file)
 547                 dcpr_dpos = 0;
 548
 549         dcpr_oldnum = 0;
 550         memset(&dcpr_olddist, 0, sizeof(dcpr_olddist));
 551
 552         dcpr_frst_file = 0;
 553 }
 554