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