git.oblomov.eu Git - wine/blob - dlls/cabinet/cabextract.c

   1 /*
   2  * cabextract.c
   3  *
   4  * Copyright 2000-2002 Stuart Caie
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  * Principal author: Stuart Caie <kyzer@4u.net>
  21  *
  22  * Based on specification documents from Microsoft Corporation
  23  * Quantum decompression researched and implemented by Matthew Russoto
  24  * Huffman code adapted from unlzx by Dave Tritscher.
  25  * InfoZip team's INFLATE implementation adapted to MSZIP by Dirk Stoecker.
  26  * Major LZX fixes by Jae Jung.
  27  */
  28
  29 #include "config.h"
  30
  31 #include <stdarg.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <ctype.h>
  35
  36 #include "windef.h"
  37 #include "winbase.h"
  38 #include "winerror.h"
  39
  40 #include "cabinet.h"
  41
  42 #include "wine/debug.h"
  43
  44 WINE_DEFAULT_DEBUG_CHANNEL(cabinet);
  45
  46 THOSE_ZIP_CONSTS;
  47
  48 /* all the file IO is abstracted into these routines:
  49  * cabinet_(open|close|read|seek|skip|getoffset)
  50  * file_(open|close|write)
  51  */
  52
  53 /* try to open a cabinet file, returns success */
  54 static BOOL cabinet_open(struct cabinet *cab)
  55 {
  56   const char *name = cab->filename;
  57   HANDLE fh;
  58
  59   TRACE("(cab == ^%p)\n", cab);
  60
  61   if ((fh = CreateFileA( name, GENERIC_READ, FILE_SHARE_READ,
  62               NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL )) == INVALID_HANDLE_VALUE) {
  63     ERR("Couldn't open %s\n", debugstr_a(name));
  64     return FALSE;
  65   }
  66
  67   /* seek to end of file and get the length */
  68   if ((cab->filelen = SetFilePointer(fh, 0, NULL, FILE_END)) == INVALID_SET_FILE_POINTER) {
  69     if (GetLastError() != NO_ERROR) {
  70       ERR("Seek END failed: %s\n", debugstr_a(name));
  71       CloseHandle(fh);
  72       return FALSE;
  73     }
  74   }
  75
  76   /* return to the start of the file */
  77   if (SetFilePointer(fh, 0, NULL, FILE_BEGIN) == INVALID_SET_FILE_POINTER) {
  78     ERR("Seek BEGIN failed: %s\n", debugstr_a(name));
  79     CloseHandle(fh);
  80     return FALSE;
  81   }
  82
  83   cab->fh = fh;
  84   return TRUE;
  85 }
  86
  87 /*******************************************************************
  88  * cabinet_close (internal)
  89  *
  90  * close the file handle in a struct cabinet.
  91  */
  92 static void cabinet_close(struct cabinet *cab) {
  93   TRACE("(cab == ^%p)\n", cab);
  94   if (cab->fh) CloseHandle(cab->fh);
  95   cab->fh = 0;
  96 }
  97
  98 /*******************************************************
  99  * ensure_filepath2 (internal)
 100  */
 101 static BOOL ensure_filepath2(char *path) {
 102   BOOL ret = TRUE;
 103   int len;
 104   char *new_path;
 105
 106   new_path = HeapAlloc(GetProcessHeap(), 0, (strlen(path) + 1));
 107   strcpy(new_path, path);
 108
 109   while((len = strlen(new_path)) && new_path[len - 1] == '\\')
 110     new_path[len - 1] = 0;
 111
 112   TRACE("About to try to create directory %s\n", debugstr_a(new_path));
 113   while(!CreateDirectoryA(new_path, NULL)) {
 114     char *slash;
 115     DWORD last_error = GetLastError();
 116
 117     if(last_error == ERROR_ALREADY_EXISTS)
 118       break;
 119
 120     if(last_error != ERROR_PATH_NOT_FOUND) {
 121       ret = FALSE;
 122       break;
 123     }
 124
 125     if(!(slash = strrchr(new_path, '\\'))) {
 126       ret = FALSE;
 127       break;
 128     }
 129
 130     len = slash - new_path;
 131     new_path[len] = 0;
 132     if(! ensure_filepath2(new_path)) {
 133       ret = FALSE;
 134       break;
 135     }
 136     new_path[len] = '\\';
 137     TRACE("New path in next iteration: %s\n", debugstr_a(new_path));
 138   }
 139
 140   HeapFree(GetProcessHeap(), 0, new_path);
 141   return ret;
 142 }
 143
 144
 145 /**********************************************************************
 146  * ensure_filepath (internal)
 147  *
 148  * ensure_filepath("a\b\c\d.txt") ensures a, a\b and a\b\c exist as dirs
 149  */
 150 static BOOL ensure_filepath(char *path) {
 151   char new_path[MAX_PATH];
 152   int len, i, lastslashpos = -1;
 153
 154   TRACE("(path == %s)\n", debugstr_a(path));
 155
 156   strcpy(new_path, path);
 157   /* remove trailing slashes (shouldn't need to but wth...) */
 158   while ((len = strlen(new_path)) && new_path[len - 1] == '\\')
 159     new_path[len - 1] = 0;
 160   /* find the position of the last '\\' */
 161   for (i=0; i<MAX_PATH; i++) {
 162     if (new_path[i] == 0) break;
 163     if (new_path[i] == '\\')
 164       lastslashpos = i;
 165   }
 166   if (lastslashpos > 0) {
 167     new_path[lastslashpos] = 0;
 168     /* may be trailing slashes but ensure_filepath2 will chop them */
 169     return ensure_filepath2(new_path);
 170   } else
 171     return TRUE; /* ? */
 172 }
 173
 174 /*******************************************************************
 175  * file_open (internal)
 176  *
 177  * opens a file for output, returns success
 178  */
 179 static BOOL file_open(struct cab_file *fi, BOOL lower, LPCSTR dir)
 180 {
 181   char c, *d, *name;
 182   BOOL ok = FALSE;
 183   const char *s;
 184
 185   TRACE("(fi == ^%p, lower == %s, dir == %s)\n", fi, lower ? "TRUE" : "FALSE", debugstr_a(dir));
 186
 187   if (!(name = malloc(strlen(fi->filename) + (dir ? strlen(dir) : 0) + 2))) {
 188     ERR("out of memory!\n");
 189     return FALSE;
 190   }
 191
 192   /* start with blank name */
 193   *name = 0;
 194
 195   /* add output directory if needed */
 196   if (dir) {
 197     strcpy(name, dir);
 198     strcat(name, "\\");
 199   }
 200
 201   /* remove leading slashes */
 202   s = (char *) fi->filename;
 203   while (*s == '\\') s++;
 204
 205   /* copy from fi->filename to new name.
 206    * lowercases characters if needed.
 207    */
 208   d = &name[strlen(name)];
 209   do {
 210     c = *s++;
 211     *d++ = (lower ? tolower((unsigned char) c) : c);
 212   } while (c);
 213
 214   /* create directories if needed, attempt to write file */
 215   if (ensure_filepath(name)) {
 216     fi->fh = CreateFileA(name, GENERIC_WRITE, 0, NULL,
 217                          CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
 218     if (fi->fh != INVALID_HANDLE_VALUE)
 219       ok = TRUE;
 220     else {
 221       ERR("CreateFileA returned INVALID_HANDLE_VALUE\n");
 222       fi->fh = 0;
 223     }
 224   } else
 225     ERR("Couldn't ensure filepath for %s\n", debugstr_a(name));
 226
 227   if (!ok) {
 228     ERR("Couldn't open file %s for writing\n", debugstr_a(name));
 229   }
 230
 231   /* as full filename is no longer needed, free it */
 232   free(name);
 233
 234   return ok;
 235 }
 236
 237 /********************************************************
 238  * close_file (internal)
 239  *
 240  * closes a completed file
 241  */
 242 static void file_close(struct cab_file *fi)
 243 {
 244   TRACE("(fi == ^%p)\n", fi);
 245
 246   if (fi->fh) {
 247     CloseHandle(fi->fh);
 248   }
 249   fi->fh = 0;
 250 }
 251
 252 /******************************************************************
 253  * file_write (internal)
 254  *
 255  * writes from buf to a file specified as a cab_file struct.
 256  * returns success/failure
 257  */
 258 static BOOL file_write(struct cab_file *fi, cab_UBYTE *buf, cab_off_t length)
 259 {
 260   DWORD bytes_written;
 261
 262   TRACE("(fi == ^%p, buf == ^%p, length == %u)\n", fi, buf, length);
 263
 264   if ((!WriteFile( fi->fh, (LPCVOID) buf, length, &bytes_written, FALSE) ||
 265       (bytes_written != length))) {
 266     ERR("Error writing file: %s\n", debugstr_a(fi->filename));
 267     return FALSE;
 268   }
 269   return TRUE;
 270 }
 271
 272
 273 /*******************************************************************
 274  * cabinet_skip (internal)
 275  *
 276  * advance the file pointer associated with the cab structure
 277  * by distance bytes
 278  */
 279 static void cabinet_skip(struct cabinet *cab, cab_off_t distance)
 280 {
 281   TRACE("(cab == ^%p, distance == %u)\n", cab, distance);
 282   if (SetFilePointer(cab->fh, distance, NULL, FILE_CURRENT) == INVALID_SET_FILE_POINTER) {
 283     if (distance != INVALID_SET_FILE_POINTER)
 284       ERR("%s\n", debugstr_a(cab->filename));
 285   }
 286 }
 287
 288 /*******************************************************************
 289  * cabinet_seek (internal)
 290  *
 291  * seek to the specified absolute offset in a cab
 292  */
 293 static void cabinet_seek(struct cabinet *cab, cab_off_t offset) {
 294   TRACE("(cab == ^%p, offset == %u)\n", cab, offset);
 295   if (SetFilePointer(cab->fh, offset, NULL, FILE_BEGIN) != offset)
 296     ERR("%s seek failure\n", debugstr_a(cab->filename));
 297 }
 298
 299 /*******************************************************************
 300  * cabinet_getoffset (internal)
 301  *
 302  * returns the file pointer position of a cab
 303  */
 304 static cab_off_t cabinet_getoffset(struct cabinet *cab)
 305 {
 306   return SetFilePointer(cab->fh, 0, NULL, FILE_CURRENT);
 307 }
 308
 309 /*******************************************************************
 310  * cabinet_read (internal)
 311  *
 312  * read data from a cabinet, returns success
 313  */
 314 static BOOL cabinet_read(struct cabinet *cab, cab_UBYTE *buf, cab_off_t length)
 315 {
 316   DWORD bytes_read;
 317   cab_off_t avail = cab->filelen - cabinet_getoffset(cab);
 318
 319   TRACE("(cab == ^%p, buf == ^%p, length == %u)\n", cab, buf, length);
 320
 321   if (length > avail) {
 322     WARN("%s: WARNING; cabinet is truncated\n", debugstr_a(cab->filename));
 323     length = avail;
 324   }
 325
 326   if (! ReadFile( cab->fh, (LPVOID) buf, length, &bytes_read, NULL )) {
 327     ERR("%s read error\n", debugstr_a(cab->filename));
 328     return FALSE;
 329   } else if (bytes_read != length) {
 330     ERR("%s read size mismatch\n", debugstr_a(cab->filename));
 331     return FALSE;
 332   }
 333
 334   return TRUE;
 335 }
 336
 337 /**********************************************************************
 338  * cabinet_read_string (internal)
 339  *
 340  * allocate and read an aribitrarily long string from the cabinet
 341  */
 342 static char *cabinet_read_string(struct cabinet *cab)
 343 {
 344   cab_off_t len=256, base = cabinet_getoffset(cab), maxlen = cab->filelen - base;
 345   BOOL ok = FALSE;
 346   unsigned int i;
 347   cab_UBYTE *buf = NULL;
 348
 349   TRACE("(cab == ^%p)\n", cab);
 350
 351   do {
 352     if (len > maxlen) len = maxlen;
 353     if (!(buf = realloc(buf, (size_t) len))) break;
 354     if (!cabinet_read(cab, buf, (size_t) len)) break;
 355
 356     /* search for a null terminator in what we've just read */
 357     for (i=0; i < len; i++) {
 358       if (!buf[i]) {ok=TRUE; break;}
 359     }
 360
 361     if (!ok) {
 362       if (len == maxlen) {
 363         ERR("%s: WARNING; cabinet is truncated\n", debugstr_a(cab->filename));
 364         break;
 365       }
 366       len += 256;
 367       cabinet_seek(cab, base);
 368     }
 369   } while (!ok);
 370
 371   if (!ok) {
 372     if (buf)
 373       free(buf);
 374     else
 375       ERR("out of memory!\n");
 376     return NULL;
 377   }
 378
 379   /* otherwise, set the stream to just after the string and return */
 380   cabinet_seek(cab, base + ((cab_off_t) strlen((char *) buf)) + 1);
 381
 382   return (char *) buf;
 383 }
 384
 385 /******************************************************************
 386  * cabinet_read_entries (internal)
 387  *
 388  * reads the header and all folder and file entries in this cabinet
 389  */
 390 static BOOL cabinet_read_entries(struct cabinet *cab)
 391 {
 392   int num_folders, num_files, header_resv, folder_resv = 0, i;
 393   struct cab_folder *fol, *linkfol = NULL;
 394   struct cab_file *file, *linkfile = NULL;
 395   cab_off_t base_offset;
 396   cab_UBYTE buf[64];
 397
 398   TRACE("(cab == ^%p)\n", cab);
 399
 400   /* read in the CFHEADER */
 401   base_offset = cabinet_getoffset(cab);
 402   if (!cabinet_read(cab, buf, cfhead_SIZEOF)) {
 403     return FALSE;
 404   }
 405
 406   /* check basic MSCF signature */
 407   if (EndGetI32(buf+cfhead_Signature) != 0x4643534d) {
 408     ERR("%s: not a Microsoft cabinet file\n", debugstr_a(cab->filename));
 409     return FALSE;
 410   }
 411
 412   /* get the number of folders */
 413   num_folders = EndGetI16(buf+cfhead_NumFolders);
 414   if (num_folders == 0) {
 415     ERR("%s: no folders in cabinet\n", debugstr_a(cab->filename));
 416     return FALSE;
 417   }
 418
 419   /* get the number of files */
 420   num_files = EndGetI16(buf+cfhead_NumFiles);
 421   if (num_files == 0) {
 422     ERR("%s: no files in cabinet\n", debugstr_a(cab->filename));
 423     return FALSE;
 424   }
 425
 426   /* just check the header revision */
 427   if ((buf[cfhead_MajorVersion] > 1) ||
 428       (buf[cfhead_MajorVersion] == 1 && buf[cfhead_MinorVersion] > 3))
 429   {
 430     WARN("%s: WARNING; cabinet format version > 1.3\n", debugstr_a(cab->filename));
 431   }
 432
 433   /* read the reserved-sizes part of header, if present */
 434   cab->flags = EndGetI16(buf+cfhead_Flags);
 435   if (cab->flags & cfheadRESERVE_PRESENT) {
 436     if (!cabinet_read(cab, buf, cfheadext_SIZEOF)) return FALSE;
 437     header_resv     = EndGetI16(buf+cfheadext_HeaderReserved);
 438     folder_resv     = buf[cfheadext_FolderReserved];
 439     cab->block_resv = buf[cfheadext_DataReserved];
 440
 441     if (header_resv > 60000) {
 442       WARN("%s: WARNING; header reserved space > 60000\n", debugstr_a(cab->filename));
 443     }
 444
 445     /* skip the reserved header */
 446     if (header_resv)
 447       if (SetFilePointer(cab->fh, (cab_off_t) header_resv, NULL, FILE_CURRENT) == INVALID_SET_FILE_POINTER)
 448         ERR("seek failure: %s\n", debugstr_a(cab->filename));
 449   }
 450
 451   if (cab->flags & cfheadPREV_CABINET) {
 452     cab->prevname = cabinet_read_string(cab);
 453     if (!cab->prevname) return FALSE;
 454     cab->previnfo = cabinet_read_string(cab);
 455   }
 456
 457   if (cab->flags & cfheadNEXT_CABINET) {
 458     cab->nextname = cabinet_read_string(cab);
 459     if (!cab->nextname) return FALSE;
 460     cab->nextinfo = cabinet_read_string(cab);
 461   }
 462
 463   /* read folders */
 464   for (i = 0; i < num_folders; i++) {
 465     if (!cabinet_read(cab, buf, cffold_SIZEOF)) return FALSE;
 466     if (folder_resv) cabinet_skip(cab, folder_resv);
 467
 468     fol = (struct cab_folder *) calloc(1, sizeof(struct cab_folder));
 469     if (!fol) {
 470       ERR("out of memory!\n");
 471       return FALSE;
 472     }
 473
 474     fol->cab[0]     = cab;
 475     fol->offset[0]  = base_offset + (cab_off_t) EndGetI32(buf+cffold_DataOffset);
 476     fol->num_blocks = EndGetI16(buf+cffold_NumBlocks);
 477     fol->comp_type  = EndGetI16(buf+cffold_CompType);
 478
 479     if (!linkfol)
 480       cab->folders = fol;
 481     else
 482       linkfol->next = fol;
 483
 484     linkfol = fol;
 485   }
 486
 487   /* read files */
 488   for (i = 0; i < num_files; i++) {
 489     if (!cabinet_read(cab, buf, cffile_SIZEOF))
 490       return FALSE;
 491
 492     file = (struct cab_file *) calloc(1, sizeof(struct cab_file));
 493     if (!file) {
 494       ERR("out of memory!\n");
 495       return FALSE;
 496     }
 497
 498     file->length   = EndGetI32(buf+cffile_UncompressedSize);
 499     file->offset   = EndGetI32(buf+cffile_FolderOffset);
 500     file->index    = EndGetI16(buf+cffile_FolderIndex);
 501     file->time     = EndGetI16(buf+cffile_Time);
 502     file->date     = EndGetI16(buf+cffile_Date);
 503     file->attribs  = EndGetI16(buf+cffile_Attribs);
 504     file->filename = cabinet_read_string(cab);
 505
 506     if (!file->filename) {
 507       free(file);
 508       return FALSE;
 509     }
 510
 511     if (!linkfile)
 512       cab->files = file;
 513     else
 514       linkfile->next = file;
 515
 516     linkfile = file;
 517   }
 518   return TRUE;
 519 }
 520
 521 /***********************************************************
 522  * load_cab_offset (internal)
 523  *
 524  * validates and reads file entries from a cabinet at offset [offset] in
 525  * file [name]. Returns a cabinet structure if successful, or NULL
 526  * otherwise.
 527  */
 528 static struct cabinet *load_cab_offset(LPCSTR name, cab_off_t offset)
 529 {
 530   struct cabinet *cab = (struct cabinet *) calloc(1, sizeof(struct cabinet));
 531   int ok;
 532
 533   TRACE("(name == %s, offset == %u)\n", debugstr_a(name), offset);
 534
 535   if (!cab) return NULL;
 536
 537   cab->filename = name;
 538   if ((ok = cabinet_open(cab))) {
 539     cabinet_seek(cab, offset);
 540     ok = cabinet_read_entries(cab);
 541     cabinet_close(cab);
 542   }
 543
 544   if (ok) return cab;
 545   free(cab);
 546   return NULL;
 547 }
 548
 549 /* MSZIP decruncher */
 550
 551 /* Dirk Stoecker wrote the ZIP decoder, based on the InfoZip deflate code */
 552
 553 /********************************************************
 554  * Ziphuft_free (internal)
 555  */
 556 static void Ziphuft_free(struct Ziphuft *t)
 557 {
 558   register struct Ziphuft *p, *q;
 559
 560   /* Go through linked list, freeing from the allocated (t[-1]) address. */
 561   p = t;
 562   while (p != (struct Ziphuft *)NULL)
 563   {
 564     q = (--p)->v.t;
 565     free(p);
 566     p = q;
 567   }
 568 }
 569
 570 /*********************************************************
 571  * Ziphuft_build (internal)
 572  */
 573 static cab_LONG Ziphuft_build(cab_ULONG *b, cab_ULONG n, cab_ULONG s, cab_UWORD *d, cab_UWORD *e,
 574 struct Ziphuft **t, cab_LONG *m, cab_decomp_state *decomp_state)
 575 {
 576   cab_ULONG a;                          /* counter for codes of length k */
 577   cab_ULONG el;                         /* length of EOB code (value 256) */
 578   cab_ULONG f;                          /* i repeats in table every f entries */
 579   cab_LONG g;                           /* maximum code length */
 580   cab_LONG h;                           /* table level */
 581   register cab_ULONG i;                 /* counter, current code */
 582   register cab_ULONG j;                 /* counter */
 583   register cab_LONG k;                  /* number of bits in current code */
 584   cab_LONG *l;                          /* stack of bits per table */
 585   register cab_ULONG *p;                /* pointer into ZIP(c)[],ZIP(b)[],ZIP(v)[] */
 586   register struct Ziphuft *q;           /* points to current table */
 587   struct Ziphuft r;                     /* table entry for structure assignment */
 588   register cab_LONG w;                  /* bits before this table == (l * h) */
 589   cab_ULONG *xp;                        /* pointer into x */
 590   cab_LONG y;                           /* number of dummy codes added */
 591   cab_ULONG z;                          /* number of entries in current table */
 592
 593   l = ZIP(lx)+1;
 594
 595   /* Generate counts for each bit length */
 596   el = n > 256 ? b[256] : ZIPBMAX; /* set length of EOB code, if any */
 597
 598   for(i = 0; i < ZIPBMAX+1; ++i)
 599     ZIP(c)[i] = 0;
 600   p = b;  i = n;
 601   do
 602   {
 603     ZIP(c)[*p]++; p++;               /* assume all entries <= ZIPBMAX */
 604   } while (--i);
 605   if (ZIP(c)[0] == n)                /* null input--all zero length codes */
 606   {
 607     *t = (struct Ziphuft *)NULL;
 608     *m = 0;
 609     return 0;
 610   }
 611
 612   /* Find minimum and maximum length, bound *m by those */
 613   for (j = 1; j <= ZIPBMAX; j++)
 614     if (ZIP(c)[j])
 615       break;
 616   k = j;                        /* minimum code length */
 617   if ((cab_ULONG)*m < j)
 618     *m = j;
 619   for (i = ZIPBMAX; i; i--)
 620     if (ZIP(c)[i])
 621       break;
 622   g = i;                        /* maximum code length */
 623   if ((cab_ULONG)*m > i)
 624     *m = i;
 625
 626   /* Adjust last length count to fill out codes, if needed */
 627   for (y = 1 << j; j < i; j++, y <<= 1)
 628     if ((y -= ZIP(c)[j]) < 0)
 629       return 2;                 /* bad input: more codes than bits */
 630   if ((y -= ZIP(c)[i]) < 0)
 631     return 2;
 632   ZIP(c)[i] += y;
 633
 634   /* Generate starting offsets LONGo the value table for each length */
 635   ZIP(x)[1] = j = 0;
 636   p = ZIP(c) + 1;  xp = ZIP(x) + 2;
 637   while (--i)
 638   {                 /* note that i == g from above */
 639     *xp++ = (j += *p++);
 640   }
 641
 642   /* Make a table of values in order of bit lengths */
 643   p = b;  i = 0;
 644   do{
 645     if ((j = *p++) != 0)
 646       ZIP(v)[ZIP(x)[j]++] = i;
 647   } while (++i < n);
 648
 649
 650   /* Generate the Huffman codes and for each, make the table entries */
 651   ZIP(x)[0] = i = 0;                 /* first Huffman code is zero */
 652   p = ZIP(v);                        /* grab values in bit order */
 653   h = -1;                       /* no tables yet--level -1 */
 654   w = l[-1] = 0;                /* no bits decoded yet */
 655   ZIP(u)[0] = (struct Ziphuft *)NULL;   /* just to keep compilers happy */
 656   q = (struct Ziphuft *)NULL;      /* ditto */
 657   z = 0;                        /* ditto */
 658
 659   /* go through the bit lengths (k already is bits in shortest code) */
 660   for (; k <= g; k++)
 661   {
 662     a = ZIP(c)[k];
 663     while (a--)
 664     {
 665       /* here i is the Huffman code of length k bits for value *p */
 666       /* make tables up to required level */
 667       while (k > w + l[h])
 668       {
 669         w += l[h++];            /* add bits already decoded */
 670
 671         /* compute minimum size table less than or equal to *m bits */
 672         z = (z = g - w) > (cab_ULONG)*m ? *m : z;        /* upper limit */
 673         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
 674         {                       /* too few codes for k-w bit table */
 675           f -= a + 1;           /* deduct codes from patterns left */
 676           xp = ZIP(c) + k;
 677           while (++j < z)       /* try smaller tables up to z bits */
 678           {
 679             if ((f <<= 1) <= *++xp)
 680               break;            /* enough codes to use up j bits */
 681             f -= *xp;           /* else deduct codes from patterns */
 682           }
 683         }
 684         if ((cab_ULONG)w + j > el && (cab_ULONG)w < el)
 685           j = el - w;           /* make EOB code end at table */
 686         z = 1 << j;             /* table entries for j-bit table */
 687         l[h] = j;               /* set table size in stack */
 688
 689         /* allocate and link in new table */
 690         if (!(q = (struct Ziphuft *) malloc((z + 1)*sizeof(struct Ziphuft))))
 691         {
 692           if(h)
 693             Ziphuft_free(ZIP(u)[0]);
 694           return 3;             /* not enough memory */
 695         }
 696         *t = q + 1;             /* link to list for Ziphuft_free() */
 697         *(t = &(q->v.t)) = (struct Ziphuft *)NULL;
 698         ZIP(u)[h] = ++q;             /* table starts after link */
 699
 700         /* connect to last table, if there is one */
 701         if (h)
 702         {
 703           ZIP(x)[h] = i;              /* save pattern for backing up */
 704           r.b = (cab_UBYTE)l[h-1];    /* bits to dump before this table */
 705           r.e = (cab_UBYTE)(16 + j);  /* bits in this table */
 706           r.v.t = q;                  /* pointer to this table */
 707           j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
 708           ZIP(u)[h-1][j] = r;        /* connect to last table */
 709         }
 710       }
 711
 712       /* set up table entry in r */
 713       r.b = (cab_UBYTE)(k - w);
 714       if (p >= ZIP(v) + n)
 715         r.e = 99;               /* out of values--invalid code */
 716       else if (*p < s)
 717       {
 718         r.e = (cab_UBYTE)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
 719         r.v.n = *p++;           /* simple code is just the value */
 720       }
 721       else
 722       {
 723         r.e = (cab_UBYTE)e[*p - s];   /* non-simple--look up in lists */
 724         r.v.n = d[*p++ - s];
 725       }
 726
 727       /* fill code-like entries with r */
 728       f = 1 << (k - w);
 729       for (j = i >> w; j < z; j += f)
 730         q[j] = r;
 731
 732       /* backwards increment the k-bit code i */
 733       for (j = 1 << (k - 1); i & j; j >>= 1)
 734         i ^= j;
 735       i ^= j;
 736
 737       /* backup over finished tables */
 738       while ((i & ((1 << w) - 1)) != ZIP(x)[h])
 739         w -= l[--h];            /* don't need to update q */
 740     }
 741   }
 742
 743   /* return actual size of base table */
 744   *m = l[0];
 745
 746   /* Return true (1) if we were given an incomplete table */
 747   return y != 0 && g != 1;
 748 }
 749
 750 /*********************************************************
 751  * Zipinflate_codes (internal)
 752  */
 753 static cab_LONG Zipinflate_codes(struct Ziphuft *tl, struct Ziphuft *td,
 754   cab_LONG bl, cab_LONG bd, cab_decomp_state *decomp_state)
 755 {
 756   register cab_ULONG e;  /* table entry flag/number of extra bits */
 757   cab_ULONG n, d;        /* length and index for copy */
 758   cab_ULONG w;           /* current window position */
 759   struct Ziphuft *t;     /* pointer to table entry */
 760   cab_ULONG ml, md;      /* masks for bl and bd bits */
 761   register cab_ULONG b;  /* bit buffer */
 762   register cab_ULONG k;  /* number of bits in bit buffer */
 763
 764   /* make local copies of globals */
 765   b = ZIP(bb);                       /* initialize bit buffer */
 766   k = ZIP(bk);
 767   w = ZIP(window_posn);                       /* initialize window position */
 768
 769   /* inflate the coded data */
 770   ml = Zipmask[bl];             /* precompute masks for speed */
 771   md = Zipmask[bd];
 772
 773   for(;;)
 774   {
 775     ZIPNEEDBITS((cab_ULONG)bl)
 776     if((e = (t = tl + ((cab_ULONG)b & ml))->e) > 16)
 777       do
 778       {
 779         if (e == 99)
 780           return 1;
 781         ZIPDUMPBITS(t->b)
 782         e -= 16;
 783         ZIPNEEDBITS(e)
 784       } while ((e = (t = t->v.t + ((cab_ULONG)b & Zipmask[e]))->e) > 16);
 785     ZIPDUMPBITS(t->b)
 786     if (e == 16)                /* then it's a literal */
 787       CAB(outbuf)[w++] = (cab_UBYTE)t->v.n;
 788     else                        /* it's an EOB or a length */
 789     {
 790       /* exit if end of block */
 791       if(e == 15)
 792         break;
 793
 794       /* get length of block to copy */
 795       ZIPNEEDBITS(e)
 796       n = t->v.n + ((cab_ULONG)b & Zipmask[e]);
 797       ZIPDUMPBITS(e);
 798
 799       /* decode distance of block to copy */
 800       ZIPNEEDBITS((cab_ULONG)bd)
 801       if ((e = (t = td + ((cab_ULONG)b & md))->e) > 16)
 802         do {
 803           if (e == 99)
 804             return 1;
 805           ZIPDUMPBITS(t->b)
 806           e -= 16;
 807           ZIPNEEDBITS(e)
 808         } while ((e = (t = t->v.t + ((cab_ULONG)b & Zipmask[e]))->e) > 16);
 809       ZIPDUMPBITS(t->b)
 810       ZIPNEEDBITS(e)
 811       d = w - t->v.n - ((cab_ULONG)b & Zipmask[e]);
 812       ZIPDUMPBITS(e)
 813       do
 814       {
 815         n -= (e = (e = ZIPWSIZE - ((d &= ZIPWSIZE-1) > w ? d : w)) > n ?n:e);
 816         do
 817         {
 818           CAB(outbuf)[w++] = CAB(outbuf)[d++];
 819         } while (--e);
 820       } while (n);
 821     }
 822   }
 823
 824   /* restore the globals from the locals */
 825   ZIP(window_posn) = w;              /* restore global window pointer */
 826   ZIP(bb) = b;                       /* restore global bit buffer */
 827   ZIP(bk) = k;
 828
 829   /* done */
 830   return 0;
 831 }
 832
 833 /***********************************************************
 834  * Zipinflate_stored (internal)
 835  */
 836 static cab_LONG Zipinflate_stored(cab_decomp_state *decomp_state)
 837 /* "decompress" an inflated type 0 (stored) block. */
 838 {
 839   cab_ULONG n;           /* number of bytes in block */
 840   cab_ULONG w;           /* current window position */
 841   register cab_ULONG b;  /* bit buffer */
 842   register cab_ULONG k;  /* number of bits in bit buffer */
 843
 844   /* make local copies of globals */
 845   b = ZIP(bb);                       /* initialize bit buffer */
 846   k = ZIP(bk);
 847   w = ZIP(window_posn);              /* initialize window position */
 848
 849   /* go to byte boundary */
 850   n = k & 7;
 851   ZIPDUMPBITS(n);
 852
 853   /* get the length and its complement */
 854   ZIPNEEDBITS(16)
 855   n = ((cab_ULONG)b & 0xffff);
 856   ZIPDUMPBITS(16)
 857   ZIPNEEDBITS(16)
 858   if (n != (cab_ULONG)((~b) & 0xffff))
 859     return 1;                   /* error in compressed data */
 860   ZIPDUMPBITS(16)
 861
 862   /* read and output the compressed data */
 863   while(n--)
 864   {
 865     ZIPNEEDBITS(8)
 866     CAB(outbuf)[w++] = (cab_UBYTE)b;
 867     ZIPDUMPBITS(8)
 868   }
 869
 870   /* restore the globals from the locals */
 871   ZIP(window_posn) = w;              /* restore global window pointer */
 872   ZIP(bb) = b;                       /* restore global bit buffer */
 873   ZIP(bk) = k;
 874   return 0;
 875 }
 876
 877 /******************************************************
 878  * Zipinflate_fixed (internal)
 879  */
 880 static cab_LONG Zipinflate_fixed(cab_decomp_state *decomp_state)
 881 {
 882   struct Ziphuft *fixed_tl;
 883   struct Ziphuft *fixed_td;
 884   cab_LONG fixed_bl, fixed_bd;
 885   cab_LONG i;                /* temporary variable */
 886   cab_ULONG *l;
 887
 888   l = ZIP(ll);
 889
 890   /* literal table */
 891   for(i = 0; i < 144; i++)
 892     l[i] = 8;
 893   for(; i < 256; i++)
 894     l[i] = 9;
 895   for(; i < 280; i++)
 896     l[i] = 7;
 897   for(; i < 288; i++)          /* make a complete, but wrong code set */
 898     l[i] = 8;
 899   fixed_bl = 7;
 900   if((i = Ziphuft_build(l, 288, 257, (cab_UWORD *) Zipcplens,
 901   (cab_UWORD *) Zipcplext, &fixed_tl, &fixed_bl, decomp_state)))
 902     return i;
 903
 904   /* distance table */
 905   for(i = 0; i < 30; i++)      /* make an incomplete code set */
 906     l[i] = 5;
 907   fixed_bd = 5;
 908   if((i = Ziphuft_build(l, 30, 0, (cab_UWORD *) Zipcpdist, (cab_UWORD *) Zipcpdext,
 909   &fixed_td, &fixed_bd, decomp_state)) > 1)
 910   {
 911     Ziphuft_free(fixed_tl);
 912     return i;
 913   }
 914
 915   /* decompress until an end-of-block code */
 916   i = Zipinflate_codes(fixed_tl, fixed_td, fixed_bl, fixed_bd, decomp_state);
 917
 918   Ziphuft_free(fixed_td);
 919   Ziphuft_free(fixed_tl);
 920   return i;
 921 }
 922
 923 /**************************************************************
 924  * Zipinflate_dynamic (internal)
 925  */
 926 static cab_LONG Zipinflate_dynamic(cab_decomp_state *decomp_state)
 927  /* decompress an inflated type 2 (dynamic Huffman codes) block. */
 928 {
 929   cab_LONG i;           /* temporary variables */
 930   cab_ULONG j;
 931   cab_ULONG *ll;
 932   cab_ULONG l;                  /* last length */
 933   cab_ULONG m;                  /* mask for bit lengths table */
 934   cab_ULONG n;                  /* number of lengths to get */
 935   struct Ziphuft *tl;           /* literal/length code table */
 936   struct Ziphuft *td;           /* distance code table */
 937   cab_LONG bl;                  /* lookup bits for tl */
 938   cab_LONG bd;                  /* lookup bits for td */
 939   cab_ULONG nb;                 /* number of bit length codes */
 940   cab_ULONG nl;                 /* number of literal/length codes */
 941   cab_ULONG nd;                 /* number of distance codes */
 942   register cab_ULONG b;         /* bit buffer */
 943   register cab_ULONG k;         /* number of bits in bit buffer */
 944
 945   /* make local bit buffer */
 946   b = ZIP(bb);
 947   k = ZIP(bk);
 948   ll = ZIP(ll);
 949
 950   /* read in table lengths */
 951   ZIPNEEDBITS(5)
 952   nl = 257 + ((cab_ULONG)b & 0x1f);      /* number of literal/length codes */
 953   ZIPDUMPBITS(5)
 954   ZIPNEEDBITS(5)
 955   nd = 1 + ((cab_ULONG)b & 0x1f);        /* number of distance codes */
 956   ZIPDUMPBITS(5)
 957   ZIPNEEDBITS(4)
 958   nb = 4 + ((cab_ULONG)b & 0xf);         /* number of bit length codes */
 959   ZIPDUMPBITS(4)
 960   if(nl > 288 || nd > 32)
 961     return 1;                   /* bad lengths */
 962
 963   /* read in bit-length-code lengths */
 964   for(j = 0; j < nb; j++)
 965   {
 966     ZIPNEEDBITS(3)
 967     ll[Zipborder[j]] = (cab_ULONG)b & 7;
 968     ZIPDUMPBITS(3)
 969   }
 970   for(; j < 19; j++)
 971     ll[Zipborder[j]] = 0;
 972
 973   /* build decoding table for trees--single level, 7 bit lookup */
 974   bl = 7;
 975   if((i = Ziphuft_build(ll, 19, 19, NULL, NULL, &tl, &bl, decomp_state)) != 0)
 976   {
 977     if(i == 1)
 978       Ziphuft_free(tl);
 979     return i;                   /* incomplete code set */
 980   }
 981
 982   /* read in literal and distance code lengths */
 983   n = nl + nd;
 984   m = Zipmask[bl];
 985   i = l = 0;
 986   while((cab_ULONG)i < n)
 987   {
 988     ZIPNEEDBITS((cab_ULONG)bl)
 989     j = (td = tl + ((cab_ULONG)b & m))->b;
 990     ZIPDUMPBITS(j)
 991     j = td->v.n;
 992     if (j < 16)                 /* length of code in bits (0..15) */
 993       ll[i++] = l = j;          /* save last length in l */
 994     else if (j == 16)           /* repeat last length 3 to 6 times */
 995     {
 996       ZIPNEEDBITS(2)
 997       j = 3 + ((cab_ULONG)b & 3);
 998       ZIPDUMPBITS(2)
 999       if((cab_ULONG)i + j > n)
1000         return 1;
1001       while (j--)
1002         ll[i++] = l;
1003     }
1004     else if (j == 17)           /* 3 to 10 zero length codes */
1005     {
1006       ZIPNEEDBITS(3)
1007       j = 3 + ((cab_ULONG)b & 7);
1008       ZIPDUMPBITS(3)
1009       if ((cab_ULONG)i + j > n)
1010         return 1;
1011       while (j--)
1012         ll[i++] = 0;
1013       l = 0;
1014     }
1015     else                        /* j == 18: 11 to 138 zero length codes */
1016     {
1017       ZIPNEEDBITS(7)
1018       j = 11 + ((cab_ULONG)b & 0x7f);
1019       ZIPDUMPBITS(7)
1020       if ((cab_ULONG)i + j > n)
1021         return 1;
1022       while (j--)
1023         ll[i++] = 0;
1024       l = 0;
1025     }
1026   }
1027
1028   /* free decoding table for trees */
1029   Ziphuft_free(tl);
1030
1031   /* restore the global bit buffer */
1032   ZIP(bb) = b;
1033   ZIP(bk) = k;
1034
1035   /* build the decoding tables for literal/length and distance codes */
1036   bl = ZIPLBITS;
1037   if((i = Ziphuft_build(ll, nl, 257, (cab_UWORD *) Zipcplens, (cab_UWORD *) Zipcplext,
1038                         &tl, &bl, decomp_state)) != 0)
1039   {
1040     if(i == 1)
1041       Ziphuft_free(tl);
1042     return i;                   /* incomplete code set */
1043   }
1044   bd = ZIPDBITS;
1045   Ziphuft_build(ll + nl, nd, 0, (cab_UWORD *) Zipcpdist, (cab_UWORD *) Zipcpdext,
1046                 &td, &bd, decomp_state);
1047
1048   /* decompress until an end-of-block code */
1049   if(Zipinflate_codes(tl, td, bl, bd, decomp_state))
1050     return 1;
1051
1052   /* free the decoding tables, return */
1053   Ziphuft_free(tl);
1054   Ziphuft_free(td);
1055   return 0;
1056 }
1057
1058 /*****************************************************
1059  * Zipinflate_block (internal)
1060  */
1061 static cab_LONG Zipinflate_block(cab_LONG *e, cab_decomp_state *decomp_state) /* e == last block flag */
1062 { /* decompress an inflated block */
1063   cab_ULONG t;                  /* block type */
1064   register cab_ULONG b;     /* bit buffer */
1065   register cab_ULONG k;     /* number of bits in bit buffer */
1066
1067   /* make local bit buffer */
1068   b = ZIP(bb);
1069   k = ZIP(bk);
1070
1071   /* read in last block bit */
1072   ZIPNEEDBITS(1)
1073   *e = (cab_LONG)b & 1;
1074   ZIPDUMPBITS(1)
1075
1076   /* read in block type */
1077   ZIPNEEDBITS(2)
1078   t = (cab_ULONG)b & 3;
1079   ZIPDUMPBITS(2)
1080
1081   /* restore the global bit buffer */
1082   ZIP(bb) = b;
1083   ZIP(bk) = k;
1084
1085   /* inflate that block type */
1086   if(t == 2)
1087     return Zipinflate_dynamic(decomp_state);
1088   if(t == 0)
1089     return Zipinflate_stored(decomp_state);
1090   if(t == 1)
1091     return Zipinflate_fixed(decomp_state);
1092   /* bad block type */
1093   return 2;
1094 }
1095
1096 /****************************************************
1097  * ZIPdecompress (internal)
1098  */
1099 static int ZIPdecompress(int inlen, int outlen, cab_decomp_state *decomp_state)
1100 {
1101   cab_LONG e;               /* last block flag */
1102
1103   TRACE("(inlen == %d, outlen == %d)\n", inlen, outlen);
1104
1105   ZIP(inpos) = CAB(inbuf);
1106   ZIP(bb) = ZIP(bk) = ZIP(window_posn) = 0;
1107   if(outlen > ZIPWSIZE)
1108     return DECR_DATAFORMAT;
1109
1110   /* CK = Chris Kirmse, official Microsoft purloiner */
1111   if(ZIP(inpos)[0] != 0x43 || ZIP(inpos)[1] != 0x4B)
1112     return DECR_ILLEGALDATA;
1113   ZIP(inpos) += 2;
1114
1115   do
1116   {
1117     if(Zipinflate_block(&e, decomp_state))
1118       return DECR_ILLEGALDATA;
1119   } while(!e);
1120
1121   /* return success */
1122   return DECR_OK;
1123 }
1124
1125 /* Quantum decruncher */
1126
1127 /* This decruncher was researched and implemented by Matthew Russoto. */
1128 /* It has since been tidied up by Stuart Caie */
1129
1130 /******************************************************************
1131  * QTMinitmodel (internal)
1132  *
1133  * Initialise a model which decodes symbols from [s] to [s]+[n]-1
1134  */
1135 static void QTMinitmodel(struct QTMmodel *m, struct QTMmodelsym *sym, int n, int s) {
1136   int i;
1137   m->shiftsleft = 4;
1138   m->entries    = n;
1139   m->syms       = sym;
1140   memset(m->tabloc, 0xFF, sizeof(m->tabloc)); /* clear out look-up table */
1141   for (i = 0; i < n; i++) {
1142     m->tabloc[i+s]     = i;   /* set up a look-up entry for symbol */
1143     m->syms[i].sym     = i+s; /* actual symbol */
1144     m->syms[i].cumfreq = n-i; /* current frequency of that symbol */
1145   }
1146   m->syms[n].cumfreq = 0;
1147 }
1148
1149 /******************************************************************
1150  * QTMinit (internal)
1151  */
1152 static int QTMinit(int window, int level, cab_decomp_state *decomp_state) {
1153   unsigned int wndsize = 1 << window;
1154   int msz = window * 2, i;
1155   cab_ULONG j;
1156
1157   /* QTM supports window sizes of 2^10 (1Kb) through 2^21 (2Mb) */
1158   /* if a previously allocated window is big enough, keep it    */
1159   if (window < 10 || window > 21) return DECR_DATAFORMAT;
1160   if (QTM(actual_size) < wndsize) {
1161     if (QTM(window)) free(QTM(window));
1162     QTM(window) = NULL;
1163   }
1164   if (!QTM(window)) {
1165     if (!(QTM(window) = malloc(wndsize))) return DECR_NOMEMORY;
1166     QTM(actual_size) = wndsize;
1167   }
1168   QTM(window_size) = wndsize;
1169   QTM(window_posn) = 0;
1170
1171   /* initialise static slot/extrabits tables */
1172   for (i = 0, j = 0; i < 27; i++) {
1173     CAB(q_length_extra)[i] = (i == 26) ? 0 : (i < 2 ? 0 : i - 2) >> 2;
1174     CAB(q_length_base)[i] = j; j += 1 << ((i == 26) ? 5 : CAB(q_length_extra)[i]);
1175   }
1176   for (i = 0, j = 0; i < 42; i++) {
1177     CAB(q_extra_bits)[i] = (i < 2 ? 0 : i-2) >> 1;
1178     CAB(q_position_base)[i] = j; j += 1 << CAB(q_extra_bits)[i];
1179   }
1180
1181   /* initialise arithmetic coding models */
1182
1183   QTMinitmodel(&QTM(model7), &QTM(m7sym)[0], 7, 0);
1184
1185   QTMinitmodel(&QTM(model00), &QTM(m00sym)[0], 0x40, 0x00);
1186   QTMinitmodel(&QTM(model40), &QTM(m40sym)[0], 0x40, 0x40);
1187   QTMinitmodel(&QTM(model80), &QTM(m80sym)[0], 0x40, 0x80);
1188   QTMinitmodel(&QTM(modelC0), &QTM(mC0sym)[0], 0x40, 0xC0);
1189
1190   /* model 4 depends on table size, ranges from 20 to 24  */
1191   QTMinitmodel(&QTM(model4), &QTM(m4sym)[0], (msz < 24) ? msz : 24, 0);
1192   /* model 5 depends on table size, ranges from 20 to 36  */
1193   QTMinitmodel(&QTM(model5), &QTM(m5sym)[0], (msz < 36) ? msz : 36, 0);
1194   /* model 6pos depends on table size, ranges from 20 to 42 */
1195   QTMinitmodel(&QTM(model6pos), &QTM(m6psym)[0], msz, 0);
1196   QTMinitmodel(&QTM(model6len), &QTM(m6lsym)[0], 27, 0);
1197
1198   return DECR_OK;
1199 }
1200
1201 /****************************************************************
1202  * QTMupdatemodel (internal)
1203  */
1204 void QTMupdatemodel(struct QTMmodel *model, int sym) {
1205   struct QTMmodelsym temp;
1206   int i, j;
1207
1208   for (i = 0; i < sym; i++) model->syms[i].cumfreq += 8;
1209
1210   if (model->syms[0].cumfreq > 3800) {
1211     if (--model->shiftsleft) {
1212       for (i = model->entries - 1; i >= 0; i--) {
1213         /* -1, not -2; the 0 entry saves this */
1214         model->syms[i].cumfreq >>= 1;
1215         if (model->syms[i].cumfreq <= model->syms[i+1].cumfreq) {
1216           model->syms[i].cumfreq = model->syms[i+1].cumfreq + 1;
1217         }
1218       }
1219     }
1220     else {
1221       model->shiftsleft = 50;
1222       for (i = 0; i < model->entries ; i++) {
1223         /* no -1, want to include the 0 entry */
1224         /* this converts cumfreqs into frequencies, then shifts right */
1225         model->syms[i].cumfreq -= model->syms[i+1].cumfreq;
1226         model->syms[i].cumfreq++; /* avoid losing things entirely */
1227         model->syms[i].cumfreq >>= 1;
1228       }
1229
1230       /* now sort by frequencies, decreasing order -- this must be an
1231        * inplace selection sort, or a sort with the same (in)stability
1232        * characteristics
1233        */
1234       for (i = 0; i < model->entries - 1; i++) {
1235         for (j = i + 1; j < model->entries; j++) {
1236           if (model->syms[i].cumfreq < model->syms[j].cumfreq) {
1237             temp = model->syms[i];
1238             model->syms[i] = model->syms[j];
1239             model->syms[j] = temp;
1240           }
1241         }
1242       }
1243
1244       /* then convert frequencies back to cumfreq */
1245       for (i = model->entries - 1; i >= 0; i--) {
1246         model->syms[i].cumfreq += model->syms[i+1].cumfreq;
1247       }
1248       /* then update the other part of the table */
1249       for (i = 0; i < model->entries; i++) {
1250         model->tabloc[model->syms[i].sym] = i;
1251       }
1252     }
1253   }
1254 }
1255
1256 /*******************************************************************
1257  * QTMdecompress (internal)
1258  */
1259 static int QTMdecompress(int inlen, int outlen, cab_decomp_state *decomp_state)
1260 {
1261   cab_UBYTE *inpos  = CAB(inbuf);
1262   cab_UBYTE *window = QTM(window);
1263   cab_UBYTE *runsrc, *rundest;
1264
1265   cab_ULONG window_posn = QTM(window_posn);
1266   cab_ULONG window_size = QTM(window_size);
1267
1268   /* used by bitstream macros */
1269   register int bitsleft, bitrun, bitsneed;
1270   register cab_ULONG bitbuf;
1271
1272   /* used by GET_SYMBOL */
1273   cab_ULONG range;
1274   cab_UWORD symf;
1275   int i;
1276
1277   int extra, togo = outlen, match_length = 0, copy_length;
1278   cab_UBYTE selector, sym;
1279   cab_ULONG match_offset = 0;
1280
1281   cab_UWORD H = 0xFFFF, L = 0, C;
1282
1283   TRACE("(inlen == %d, outlen == %d)\n", inlen, outlen);
1284
1285   /* read initial value of C */
1286   Q_INIT_BITSTREAM;
1287   Q_READ_BITS(C, 16);
1288
1289   /* apply 2^x-1 mask */
1290   window_posn &= window_size - 1;
1291   /* runs can't straddle the window wraparound */
1292   if ((window_posn + togo) > window_size) {
1293     TRACE("straddled run\n");
1294     return DECR_DATAFORMAT;
1295   }
1296
1297   while (togo > 0) {
1298     GET_SYMBOL(model7, selector);
1299     switch (selector) {
1300     case 0:
1301       GET_SYMBOL(model00, sym); window[window_posn++] = sym; togo--;
1302       break;
1303     case 1:
1304       GET_SYMBOL(model40, sym); window[window_posn++] = sym; togo--;
1305       break;
1306     case 2:
1307       GET_SYMBOL(model80, sym); window[window_posn++] = sym; togo--;
1308       break;
1309     case 3:
1310       GET_SYMBOL(modelC0, sym); window[window_posn++] = sym; togo--;
1311       break;
1312
1313     case 4:
1314       /* selector 4 = fixed length of 3 */
1315       GET_SYMBOL(model4, sym);
1316       Q_READ_BITS(extra, CAB(q_extra_bits)[sym]);
1317       match_offset = CAB(q_position_base)[sym] + extra + 1;
1318       match_length = 3;
1319       break;
1320
1321     case 5:
1322       /* selector 5 = fixed length of 4 */
1323       GET_SYMBOL(model5, sym);
1324       Q_READ_BITS(extra, CAB(q_extra_bits)[sym]);
1325       match_offset = CAB(q_position_base)[sym] + extra + 1;
1326       match_length = 4;
1327       break;
1328
1329     case 6:
1330       /* selector 6 = variable length */
1331       GET_SYMBOL(model6len, sym);
1332       Q_READ_BITS(extra, CAB(q_length_extra)[sym]);
1333       match_length = CAB(q_length_base)[sym] + extra + 5;
1334       GET_SYMBOL(model6pos, sym);
1335       Q_READ_BITS(extra, CAB(q_extra_bits)[sym]);
1336       match_offset = CAB(q_position_base)[sym] + extra + 1;
1337       break;
1338
1339     default:
1340       TRACE("Selector is bogus\n");
1341       return DECR_ILLEGALDATA;
1342     }
1343
1344     /* if this is a match */
1345     if (selector >= 4) {
1346       rundest = window + window_posn;
1347       togo -= match_length;
1348
1349       /* copy any wrapped around source data */
1350       if (window_posn >= match_offset) {
1351         /* no wrap */
1352         runsrc = rundest - match_offset;
1353       } else {
1354         runsrc = rundest + (window_size - match_offset);
1355         copy_length = match_offset - window_posn;
1356         if (copy_length < match_length) {
1357           match_length -= copy_length;
1358           window_posn += copy_length;
1359           while (copy_length-- > 0) *rundest++ = *runsrc++;
1360           runsrc = window;
1361         }
1362       }
1363       window_posn += match_length;
1364
1365       /* copy match data - no worries about destination wraps */
1366       while (match_length-- > 0) *rundest++ = *runsrc++;
1367     }
1368   } /* while (togo > 0) */
1369
1370   if (togo != 0) {
1371     TRACE("Frame overflow, this_run = %d\n", togo);
1372     return DECR_ILLEGALDATA;
1373   }
1374
1375   memcpy(CAB(outbuf), window + ((!window_posn) ? window_size : window_posn) -
1376     outlen, outlen);
1377
1378   QTM(window_posn) = window_posn;
1379   return DECR_OK;
1380 }
1381
1382 /* LZX decruncher */
1383
1384 /* Microsoft's LZX document and their implementation of the
1385  * com.ms.util.cab Java package do not concur.
1386  *
1387  * In the LZX document, there is a table showing the correlation between
1388  * window size and the number of position slots. It states that the 1MB
1389  * window = 40 slots and the 2MB window = 42 slots. In the implementation,
1390  * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
1391  * first slot whose position base is equal to or more than the required
1392  * window size'. This would explain why other tables in the document refer
1393  * to 50 slots rather than 42.
1394  *
1395  * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
1396  * is not defined in the specification.
1397  *
1398  * The LZX document does not state the uncompressed block has an
1399  * uncompressed length field. Where does this length field come from, so
1400  * we can know how large the block is? The implementation has it as the 24
1401  * bits following after the 3 blocktype bits, before the alignment
1402  * padding.
1403  *
1404  * The LZX document states that aligned offset blocks have their aligned
1405  * offset huffman tree AFTER the main and length trees. The implementation
1406  * suggests that the aligned offset tree is BEFORE the main and length
1407  * trees.
1408  *
1409  * The LZX document decoding algorithm states that, in an aligned offset
1410  * block, if an extra_bits value is 1, 2 or 3, then that number of bits
1411  * should be read and the result added to the match offset. This is
1412  * correct for 1 and 2, but not 3, where just a huffman symbol (using the
1413  * aligned tree) should be read.
1414  *
1415  * Regarding the E8 preprocessing, the LZX document states 'No translation
1416  * may be performed on the last 6 bytes of the input block'. This is
1417  * correct.  However, the pseudocode provided checks for the *E8 leader*
1418  * up to the last 6 bytes. If the leader appears between -10 and -7 bytes
1419  * from the end, this would cause the next four bytes to be modified, at
1420  * least one of which would be in the last 6 bytes, which is not allowed
1421  * according to the spec.
1422  *
1423  * The specification states that the huffman trees must always contain at
1424  * least one element. However, many CAB files contain blocks where the
1425  * length tree is completely empty (because there are no matches), and
1426  * this is expected to succeed.
1427  */
1428
1429
1430 /* LZX uses what it calls 'position slots' to represent match offsets.
1431  * What this means is that a small 'position slot' number and a small
1432  * offset from that slot are encoded instead of one large offset for
1433  * every match.
1434  * - lzx_position_base is an index to the position slot bases
1435  * - lzx_extra_bits states how many bits of offset-from-base data is needed.
1436  */
1437
1438 /************************************************************
1439  * LZXinit (internal)
1440  */
1441 static int LZXinit(int window, cab_decomp_state *decomp_state) {
1442   cab_ULONG wndsize = 1 << window;
1443   int i, j, posn_slots;
1444
1445   /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
1446   /* if a previously allocated window is big enough, keep it     */
1447   if (window < 15 || window > 21) return DECR_DATAFORMAT;
1448   if (LZX(actual_size) < wndsize) {
1449     if (LZX(window)) free(LZX(window));
1450     LZX(window) = NULL;
1451   }
1452   if (!LZX(window)) {
1453     if (!(LZX(window) = malloc(wndsize))) return DECR_NOMEMORY;
1454     LZX(actual_size) = wndsize;
1455   }
1456   LZX(window_size) = wndsize;
1457
1458   /* initialise static tables */
1459   for (i=0, j=0; i <= 50; i += 2) {
1460     CAB(extra_bits)[i] = CAB(extra_bits)[i+1] = j; /* 0,0,0,0,1,1,2,2,3,3... */
1461     if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */
1462   }
1463   for (i=0, j=0; i <= 50; i++) {
1464     CAB(lzx_position_base)[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */
1465     j += 1 << CAB(extra_bits)[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */
1466   }
1467
1468   /* calculate required position slots */
1469        if (window == 20) posn_slots = 42;
1470   else if (window == 21) posn_slots = 50;
1471   else posn_slots = window << 1;
1472
1473   /*posn_slots=i=0; while (i < wndsize) i += 1 << CAB(extra_bits)[posn_slots++]; */
1474
1475   LZX(R0)  =  LZX(R1)  = LZX(R2) = 1;
1476   LZX(main_elements)   = LZX_NUM_CHARS + (posn_slots << 3);
1477   LZX(header_read)     = 0;
1478   LZX(frames_read)     = 0;
1479   LZX(block_remaining) = 0;
1480   LZX(block_type)      = LZX_BLOCKTYPE_INVALID;
1481   LZX(intel_curpos)    = 0;
1482   LZX(intel_started)   = 0;
1483   LZX(window_posn)     = 0;
1484
1485   /* initialise tables to 0 (because deltas will be applied to them) */
1486   for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) LZX(MAINTREE_len)[i] = 0;
1487   for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++)   LZX(LENGTH_len)[i]   = 0;
1488
1489   return DECR_OK;
1490 }
1491
1492 /*************************************************************************
1493  * make_decode_table (internal)
1494  *
1495  * This function was coded by David Tritscher. It builds a fast huffman
1496  * decoding table out of just a canonical huffman code lengths table.
1497  *
1498  * PARAMS
1499  *   nsyms:  total number of symbols in this huffman tree.
1500  *   nbits:  any symbols with a code length of nbits or less can be decoded
1501  *           in one lookup of the table.
1502  *   length: A table to get code lengths from [0 to syms-1]
1503  *   table:  The table to fill up with decoded symbols and pointers.
1504  *
1505  * RETURNS
1506  *   OK:    0
1507  *   error: 1
1508  */
1509 int make_decode_table(cab_ULONG nsyms, cab_ULONG nbits, cab_UBYTE *length, cab_UWORD *table) {
1510   register cab_UWORD sym;
1511   register cab_ULONG leaf;
1512   register cab_UBYTE bit_num = 1;
1513   cab_ULONG fill;
1514   cab_ULONG pos         = 0; /* the current position in the decode table */
1515   cab_ULONG table_mask  = 1 << nbits;
1516   cab_ULONG bit_mask    = table_mask >> 1; /* don't do 0 length codes */
1517   cab_ULONG next_symbol = bit_mask; /* base of allocation for long codes */
1518
1519   /* fill entries for codes short enough for a direct mapping */
1520   while (bit_num <= nbits) {
1521     for (sym = 0; sym < nsyms; sym++) {
1522       if (length[sym] == bit_num) {
1523         leaf = pos;
1524
1525         if((pos += bit_mask) > table_mask) return 1; /* table overrun */
1526
1527         /* fill all possible lookups of this symbol with the symbol itself */
1528         fill = bit_mask;
1529         while (fill-- > 0) table[leaf++] = sym;
1530       }
1531     }
1532     bit_mask >>= 1;
1533     bit_num++;
1534   }
1535
1536   /* if there are any codes longer than nbits */
1537   if (pos != table_mask) {
1538     /* clear the remainder of the table */
1539     for (sym = pos; sym < table_mask; sym++) table[sym] = 0;
1540
1541     /* give ourselves room for codes to grow by up to 16 more bits */
1542     pos <<= 16;
1543     table_mask <<= 16;
1544     bit_mask = 1 << 15;
1545
1546     while (bit_num <= 16) {
1547       for (sym = 0; sym < nsyms; sym++) {
1548         if (length[sym] == bit_num) {
1549           leaf = pos >> 16;
1550           for (fill = 0; fill < bit_num - nbits; fill++) {
1551             /* if this path hasn't been taken yet, 'allocate' two entries */
1552             if (table[leaf] == 0) {
1553               table[(next_symbol << 1)] = 0;
1554               table[(next_symbol << 1) + 1] = 0;
1555               table[leaf] = next_symbol++;
1556             }
1557             /* follow the path and select either left or right for next bit */
1558             leaf = table[leaf] << 1;
1559             if ((pos >> (15-fill)) & 1) leaf++;
1560           }
1561           table[leaf] = sym;
1562
1563           if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
1564         }
1565       }
1566       bit_mask >>= 1;
1567       bit_num++;
1568     }
1569   }
1570
1571   /* full table? */
1572   if (pos == table_mask) return 0;
1573
1574   /* either erroneous table, or all elements are 0 - let's find out. */
1575   for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
1576   return 0;
1577 }
1578
1579 /************************************************************
1580  * lzx_read_lens (internal)
1581  */
1582 static int lzx_read_lens(cab_UBYTE *lens, cab_ULONG first, cab_ULONG last, struct lzx_bits *lb,
1583                   cab_decomp_state *decomp_state) {
1584   cab_ULONG i,j, x,y;
1585   int z;
1586
1587   register cab_ULONG bitbuf = lb->bb;
1588   register int bitsleft = lb->bl;
1589   cab_UBYTE *inpos = lb->ip;
1590   cab_UWORD *hufftbl;
1591
1592   for (x = 0; x < 20; x++) {
1593     READ_BITS(y, 4);
1594     LENTABLE(PRETREE)[x] = y;
1595   }
1596   BUILD_TABLE(PRETREE);
1597
1598   for (x = first; x < last; ) {
1599     READ_HUFFSYM(PRETREE, z);
1600     if (z == 17) {
1601       READ_BITS(y, 4); y += 4;
1602       while (y--) lens[x++] = 0;
1603     }
1604     else if (z == 18) {
1605       READ_BITS(y, 5); y += 20;
1606       while (y--) lens[x++] = 0;
1607     }
1608     else if (z == 19) {
1609       READ_BITS(y, 1); y += 4;
1610       READ_HUFFSYM(PRETREE, z);
1611       z = lens[x] - z; if (z < 0) z += 17;
1612       while (y--) lens[x++] = z;
1613     }
1614     else {
1615       z = lens[x] - z; if (z < 0) z += 17;
1616       lens[x++] = z;
1617     }
1618   }
1619
1620   lb->bb = bitbuf;
1621   lb->bl = bitsleft;
1622   lb->ip = inpos;
1623   return 0;
1624 }
1625
1626 /*******************************************************
1627  * LZXdecompress (internal)
1628  */
1629 static int LZXdecompress(int inlen, int outlen, cab_decomp_state *decomp_state) {
1630   cab_UBYTE *inpos  = CAB(inbuf);
1631   cab_UBYTE *endinp = inpos + inlen;
1632   cab_UBYTE *window = LZX(window);
1633   cab_UBYTE *runsrc, *rundest;
1634   cab_UWORD *hufftbl; /* used in READ_HUFFSYM macro as chosen decoding table */
1635
1636   cab_ULONG window_posn = LZX(window_posn);
1637   cab_ULONG window_size = LZX(window_size);
1638   cab_ULONG R0 = LZX(R0);
1639   cab_ULONG R1 = LZX(R1);
1640   cab_ULONG R2 = LZX(R2);
1641
1642   register cab_ULONG bitbuf;
1643   register int bitsleft;
1644   cab_ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */
1645   struct lzx_bits lb; /* used in READ_LENGTHS macro */
1646
1647   int togo = outlen, this_run, main_element, aligned_bits;
1648   int match_length, copy_length, length_footer, extra, verbatim_bits;
1649
1650   TRACE("(inlen == %d, outlen == %d)\n", inlen, outlen);
1651
1652   INIT_BITSTREAM;
1653
1654   /* read header if necessary */
1655   if (!LZX(header_read)) {
1656     i = j = 0;
1657     READ_BITS(k, 1); if (k) { READ_BITS(i,16); READ_BITS(j,16); }
1658     LZX(intel_filesize) = (i << 16) | j; /* or 0 if not encoded */
1659     LZX(header_read) = 1;
1660   }
1661
1662   /* main decoding loop */
1663   while (togo > 0) {
1664     /* last block finished, new block expected */
1665     if (LZX(block_remaining) == 0) {
1666       if (LZX(block_type) == LZX_BLOCKTYPE_UNCOMPRESSED) {
1667         if (LZX(block_length) & 1) inpos++; /* realign bitstream to word */
1668         INIT_BITSTREAM;
1669       }
1670
1671       READ_BITS(LZX(block_type), 3);
1672       READ_BITS(i, 16);
1673       READ_BITS(j, 8);
1674       LZX(block_remaining) = LZX(block_length) = (i << 8) | j;
1675
1676       switch (LZX(block_type)) {
1677       case LZX_BLOCKTYPE_ALIGNED:
1678         for (i = 0; i < 8; i++) { READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j; }
1679         BUILD_TABLE(ALIGNED);
1680         /* rest of aligned header is same as verbatim */
1681
1682       case LZX_BLOCKTYPE_VERBATIM:
1683         READ_LENGTHS(MAINTREE, 0, 256, lzx_read_lens);
1684         READ_LENGTHS(MAINTREE, 256, LZX(main_elements), lzx_read_lens);
1685         BUILD_TABLE(MAINTREE);
1686         if (LENTABLE(MAINTREE)[0xE8] != 0) LZX(intel_started) = 1;
1687
1688         READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS, lzx_read_lens);
1689         BUILD_TABLE(LENGTH);
1690         break;
1691
1692       case LZX_BLOCKTYPE_UNCOMPRESSED:
1693         LZX(intel_started) = 1; /* because we can't assume otherwise */
1694         ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
1695         if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */
1696         R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
1697         R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
1698         R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
1699         break;
1700
1701       default:
1702         return DECR_ILLEGALDATA;
1703       }
1704     }
1705
1706     /* buffer exhaustion check */
1707     if (inpos > endinp) {
1708       /* it's possible to have a file where the next run is less than
1709        * 16 bits in size. In this case, the READ_HUFFSYM() macro used
1710        * in building the tables will exhaust the buffer, so we should
1711        * allow for this, but not allow those accidentally read bits to
1712        * be used (so we check that there are at least 16 bits
1713        * remaining - in this boundary case they aren't really part of
1714        * the compressed data)
1715        */
1716       if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
1717     }
1718
1719     while ((this_run = LZX(block_remaining)) > 0 && togo > 0) {
1720       if (this_run > togo) this_run = togo;
1721       togo -= this_run;
1722       LZX(block_remaining) -= this_run;
1723
1724       /* apply 2^x-1 mask */
1725       window_posn &= window_size - 1;
1726       /* runs can't straddle the window wraparound */
1727       if ((window_posn + this_run) > window_size)
1728         return DECR_DATAFORMAT;
1729
1730       switch (LZX(block_type)) {
1731
1732       case LZX_BLOCKTYPE_VERBATIM:
1733         while (this_run > 0) {
1734           READ_HUFFSYM(MAINTREE, main_element);
1735
1736           if (main_element < LZX_NUM_CHARS) {
1737             /* literal: 0 to LZX_NUM_CHARS-1 */
1738             window[window_posn++] = main_element;
1739             this_run--;
1740           }
1741           else {
1742             /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
1743             main_element -= LZX_NUM_CHARS;
1744
1745             match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
1746             if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
1747               READ_HUFFSYM(LENGTH, length_footer);
1748               match_length += length_footer;
1749             }
1750             match_length += LZX_MIN_MATCH;
1751
1752             match_offset = main_element >> 3;
1753
1754             if (match_offset > 2) {
1755               /* not repeated offset */
1756               if (match_offset != 3) {
1757                 extra = CAB(extra_bits)[match_offset];
1758                 READ_BITS(verbatim_bits, extra);
1759                 match_offset = CAB(lzx_position_base)[match_offset]
1760                                - 2 + verbatim_bits;
1761               }
1762               else {
1763                 match_offset = 1;
1764               }
1765
1766               /* update repeated offset LRU queue */
1767               R2 = R1; R1 = R0; R0 = match_offset;
1768             }
1769             else if (match_offset == 0) {
1770               match_offset = R0;
1771             }
1772             else if (match_offset == 1) {
1773               match_offset = R1;
1774               R1 = R0; R0 = match_offset;
1775             }
1776             else /* match_offset == 2 */ {
1777               match_offset = R2;
1778               R2 = R0; R0 = match_offset;
1779             }
1780
1781             rundest = window + window_posn;
1782             this_run -= match_length;
1783
1784             /* copy any wrapped around source data */
1785             if (window_posn >= match_offset) {
1786               /* no wrap */
1787               runsrc = rundest - match_offset;
1788             } else {
1789               runsrc = rundest + (window_size - match_offset);
1790               copy_length = match_offset - window_posn;
1791               if (copy_length < match_length) {
1792                 match_length -= copy_length;
1793                 window_posn += copy_length;
1794                 while (copy_length-- > 0) *rundest++ = *runsrc++;
1795                 runsrc = window;
1796               }
1797             }
1798             window_posn += match_length;
1799
1800             /* copy match data - no worries about destination wraps */
1801             while (match_length-- > 0) *rundest++ = *runsrc++;
1802           }
1803         }
1804         break;
1805
1806       case LZX_BLOCKTYPE_ALIGNED:
1807         while (this_run > 0) {
1808           READ_HUFFSYM(MAINTREE, main_element);
1809
1810           if (main_element < LZX_NUM_CHARS) {
1811             /* literal: 0 to LZX_NUM_CHARS-1 */
1812             window[window_posn++] = main_element;
1813             this_run--;
1814           }
1815           else {
1816             /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
1817             main_element -= LZX_NUM_CHARS;
1818
1819             match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
1820             if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
1821               READ_HUFFSYM(LENGTH, length_footer);
1822               match_length += length_footer;
1823             }
1824             match_length += LZX_MIN_MATCH;
1825
1826             match_offset = main_element >> 3;
1827
1828             if (match_offset > 2) {
1829               /* not repeated offset */
1830               extra = CAB(extra_bits)[match_offset];
1831               match_offset = CAB(lzx_position_base)[match_offset] - 2;
1832               if (extra > 3) {
1833                 /* verbatim and aligned bits */
1834                 extra -= 3;
1835                 READ_BITS(verbatim_bits, extra);
1836                 match_offset += (verbatim_bits << 3);
1837                 READ_HUFFSYM(ALIGNED, aligned_bits);
1838                 match_offset += aligned_bits;
1839               }
1840               else if (extra == 3) {
1841                 /* aligned bits only */
1842                 READ_HUFFSYM(ALIGNED, aligned_bits);
1843                 match_offset += aligned_bits;
1844               }
1845               else if (extra > 0) { /* extra==1, extra==2 */
1846                 /* verbatim bits only */
1847                 READ_BITS(verbatim_bits, extra);
1848                 match_offset += verbatim_bits;
1849               }
1850               else /* extra == 0 */ {
1851                 /* ??? */
1852                 match_offset = 1;
1853               }
1854
1855               /* update repeated offset LRU queue */
1856               R2 = R1; R1 = R0; R0 = match_offset;
1857             }
1858             else if (match_offset == 0) {
1859               match_offset = R0;
1860             }
1861             else if (match_offset == 1) {
1862               match_offset = R1;
1863               R1 = R0; R0 = match_offset;
1864             }
1865             else /* match_offset == 2 */ {
1866               match_offset = R2;
1867               R2 = R0; R0 = match_offset;
1868             }
1869
1870             rundest = window + window_posn;
1871             this_run -= match_length;
1872
1873             /* copy any wrapped around source data */
1874             if (window_posn >= match_offset) {
1875               /* no wrap */
1876               runsrc = rundest - match_offset;
1877             } else {
1878               runsrc = rundest + (window_size - match_offset);
1879               copy_length = match_offset - window_posn;
1880               if (copy_length < match_length) {
1881                 match_length -= copy_length;
1882                 window_posn += copy_length;
1883                 while (copy_length-- > 0) *rundest++ = *runsrc++;
1884                 runsrc = window;
1885               }
1886             }
1887             window_posn += match_length;
1888
1889             /* copy match data - no worries about destination wraps */
1890             while (match_length-- > 0) *rundest++ = *runsrc++;
1891           }
1892         }
1893         break;
1894
1895       case LZX_BLOCKTYPE_UNCOMPRESSED:
1896         if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
1897         memcpy(window + window_posn, inpos, (size_t) this_run);
1898         inpos += this_run; window_posn += this_run;
1899         break;
1900
1901       default:
1902         return DECR_ILLEGALDATA; /* might as well */
1903       }
1904
1905     }
1906   }
1907
1908   if (togo != 0) return DECR_ILLEGALDATA;
1909   memcpy(CAB(outbuf), window + ((!window_posn) ? window_size : window_posn) -
1910     outlen, (size_t) outlen);
1911
1912   LZX(window_posn) = window_posn;
1913   LZX(R0) = R0;
1914   LZX(R1) = R1;
1915   LZX(R2) = R2;
1916
1917   /* intel E8 decoding */
1918   if ((LZX(frames_read)++ < 32768) && LZX(intel_filesize) != 0) {
1919     if (outlen <= 6 || !LZX(intel_started)) {
1920       LZX(intel_curpos) += outlen;
1921     }
1922     else {
1923       cab_UBYTE *data    = CAB(outbuf);
1924       cab_UBYTE *dataend = data + outlen - 10;
1925       cab_LONG curpos    = LZX(intel_curpos);
1926       cab_LONG filesize  = LZX(intel_filesize);
1927       cab_LONG abs_off, rel_off;
1928
1929       LZX(intel_curpos) = curpos + outlen;
1930
1931       while (data < dataend) {
1932         if (*data++ != 0xE8) { curpos++; continue; }
1933         abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
1934         if ((abs_off >= -curpos) && (abs_off < filesize)) {
1935           rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
1936           data[0] = (cab_UBYTE) rel_off;
1937           data[1] = (cab_UBYTE) (rel_off >> 8);
1938           data[2] = (cab_UBYTE) (rel_off >> 16);
1939           data[3] = (cab_UBYTE) (rel_off >> 24);
1940         }
1941         data += 4;
1942         curpos += 5;
1943       }
1944     }
1945   }
1946   return DECR_OK;
1947 }
1948
1949 /*********************************************************
1950  * find_cabs_in_file (internal)
1951  */
1952 static struct cabinet *find_cabs_in_file(LPCSTR name, cab_UBYTE search_buf[])
1953 {
1954   struct cabinet *cab, *cab2, *firstcab = NULL, *linkcab = NULL;
1955   cab_UBYTE *pstart = &search_buf[0], *pend, *p;
1956   cab_off_t offset, caboff, cablen = 0, foffset = 0, filelen, length;
1957   int state = 0, found = 0, ok = 0;
1958
1959   TRACE("(name == %s)\n", debugstr_a(name));
1960
1961   /* open the file and search for cabinet headers */
1962   if ((cab = (struct cabinet *) calloc(1, sizeof(struct cabinet)))) {
1963     cab->filename = name;
1964     if (cabinet_open(cab)) {
1965       filelen = cab->filelen;
1966       for (offset = 0; (offset < filelen); offset += length) {
1967         /* search length is either the full length of the search buffer,
1968          * or the amount of data remaining to the end of the file,
1969          * whichever is less.
1970          */
1971         length = filelen - offset;
1972         if (length > CAB_SEARCH_SIZE) length = CAB_SEARCH_SIZE;
1973
1974         /* fill the search buffer with data from disk */
1975         if (!cabinet_read(cab, search_buf, length)) break;
1976
1977         /* read through the entire buffer. */
1978         p = pstart;
1979         pend = &search_buf[length];
1980         while (p < pend) {
1981           switch (state) {
1982           /* starting state */
1983           case 0:
1984             /* we spend most of our time in this while loop, looking for
1985              * a leading 'M' of the 'MSCF' signature
1986              */
1987             while (*p++ != 0x4D && p < pend);
1988             if (p < pend) state = 1; /* if we found tht 'M', advance state */
1989             break;
1990
1991           /* verify that the next 3 bytes are 'S', 'C' and 'F' */
1992           case 1: state = (*p++ == 0x53) ? 2 : 0; break;
1993           case 2: state = (*p++ == 0x43) ? 3 : 0; break;
1994           case 3: state = (*p++ == 0x46) ? 4 : 0; break;
1995
1996           /* we don't care about bytes 4-7 */
1997           /* bytes 8-11 are the overall length of the cabinet */
1998           case 8:  cablen  = *p++;       state++; break;
1999           case 9:  cablen |= *p++ << 8;  state++; break;
2000           case 10: cablen |= *p++ << 16; state++; break;
2001           case 11: cablen |= *p++ << 24; state++; break;
2002
2003           /* we don't care about bytes 12-15 */
2004           /* bytes 16-19 are the offset within the cabinet of the filedata */
2005           case 16: foffset  = *p++;       state++; break;
2006           case 17: foffset |= *p++ << 8;  state++; break;
2007           case 18: foffset |= *p++ << 16; state++; break;
2008           case 19: foffset |= *p++ << 24;
2009             /* now we have received 20 bytes of potential cab header. */
2010             /* work out the offset in the file of this potential cabinet */
2011             caboff = offset + (p-pstart) - 20;
2012
2013             /* check that the files offset is less than the alleged length
2014              * of the cabinet, and that the offset + the alleged length are
2015              * 'roughly' within the end of overall file length
2016              */
2017             if ((foffset < cablen) &&
2018                 ((caboff + foffset) < (filelen + 32)) &&
2019                 ((caboff + cablen) < (filelen + 32)) )
2020             {
2021               /* found a potential result - try loading it */
2022               found++;
2023               cab2 =  load_cab_offset(name, caboff);
2024               if (cab2) {
2025                 /* success */
2026                 ok++;
2027
2028                 /* cause the search to restart after this cab's data. */
2029                 offset = caboff + cablen;
2030                 if (offset < cab->filelen) cabinet_seek(cab, offset);
2031                 length = 0;
2032                 p = pend;
2033
2034                 /* link the cab into the list */
2035                 if (linkcab == NULL) firstcab = cab2;
2036                 else linkcab->next = cab2;
2037                 linkcab = cab2;
2038               }
2039             }
2040             state = 0;
2041             break;
2042           default:
2043             p++, state++; break;
2044           }
2045         }
2046       }
2047       cabinet_close(cab);
2048     }
2049     free(cab);
2050   }
2051
2052   /* if there were cabinets that were found but are not ok, point this out */
2053   if (found > ok) {
2054     WARN("%s: found %d bad cabinets\n", debugstr_a(name), found-ok);
2055   }
2056
2057   /* if no cabinets were found, let the user know */
2058   if (!firstcab) {
2059     WARN("%s: not a Microsoft cabinet file.\n", debugstr_a(name));
2060   }
2061   return firstcab;
2062 }
2063
2064 /***********************************************************************
2065  * find_cabinet_file (internal)
2066  *
2067  * tries to find *cabname, from the directory path of origcab, correcting the
2068  * case of *cabname if necessary, If found, writes back to *cabname.
2069  */
2070 static void find_cabinet_file(char **cabname, LPCSTR origcab) {
2071
2072   char *tail, *cab, *name, *nextpart, nametmp[MAX_PATH];
2073   int found = 0;
2074
2075   TRACE("(*cabname == ^%p, origcab == %s)\n", cabname ? *cabname : NULL, debugstr_a(origcab));
2076
2077   /* ensure we have a cabinet name at all */
2078   if (!(name = *cabname)) {
2079     WARN("no cabinet name at all\n");
2080   }
2081
2082   /* find if there's a directory path in the origcab */
2083   tail = origcab ? max(strrchr(origcab, '/'), strrchr(origcab, '\\')) : NULL;
2084
2085   if ((cab = (char *) malloc(MAX_PATH))) {
2086     /* add the directory path from the original cabinet name */
2087     if (tail) {
2088       memcpy(cab, origcab, tail - origcab);
2089       cab[tail - origcab] = '\0';
2090     } else {
2091       /* default directory path of '.' */
2092       cab[0] = '.';
2093       cab[1] = '\0';
2094     }
2095
2096     do {
2097       TRACE("trying cab == %s\n", debugstr_a(cab));
2098
2099       /* we don't want null cabinet filenames */
2100       if (name[0] == '\0') {
2101         WARN("null cab name\n");
2102         break;
2103       }
2104
2105       /* if there is a directory component in the cabinet name,
2106        * look for that alone first
2107        */
2108       nextpart = strchr(name, '\\');
2109       if (nextpart) *nextpart = '\0';
2110
2111       found = SearchPathA(cab, name, NULL, MAX_PATH, nametmp, NULL);
2112
2113       /* if the component was not found, look for it in the current dir */
2114       if (!found) {
2115         found = SearchPathA(".", name, NULL, MAX_PATH, nametmp, NULL);
2116       }
2117
2118       if (found)
2119         TRACE("found: %s\n", debugstr_a(nametmp));
2120       else
2121         TRACE("not found.\n");
2122
2123       /* restore the real name and skip to the next directory component
2124        * or actual cabinet name
2125        */
2126       if (nextpart) *nextpart = '\\', name = &nextpart[1];
2127
2128       /* while there is another directory component, and while we
2129        * successfully found the current component
2130        */
2131     } while (nextpart && found);
2132
2133     /* if we found the cabinet, change the next cabinet's name.
2134      * otherwise, pretend nothing happened
2135      */
2136     if (found) {
2137       free((void *) *cabname);
2138       *cabname = cab;
2139       memcpy(cab, nametmp, found+1);
2140       TRACE("result: %s\n", debugstr_a(cab));
2141     } else {
2142       free((void *) cab);
2143       TRACE("result: nothing\n");
2144     }
2145   }
2146 }
2147
2148 /************************************************************************
2149  * process_files (internal)
2150  *
2151  * this does the tricky job of running through every file in the cabinet,
2152  * including spanning cabinets, and working out which file is in which
2153  * folder in which cabinet. It also throws out the duplicate file entries
2154  * that appear in spanning cabinets. There is memory leakage here because
2155  * those entries are not freed. See the XAD CAB client (function CAB_GetInfo
2156  * in CAB.c) for an implementation of this that correctly frees the discarded
2157  * file entries.
2158  */
2159 static struct cab_file *process_files(struct cabinet *basecab) {
2160   struct cabinet *cab;
2161   struct cab_file *outfi = NULL, *linkfi = NULL, *nextfi, *fi, *cfi;
2162   struct cab_folder *fol, *firstfol, *lastfol = NULL, *predfol;
2163   int i, mergeok;
2164
2165   FIXME("(basecab == ^%p): Memory leak.\n", basecab);
2166
2167   for (cab = basecab; cab; cab = cab->nextcab) {
2168     /* firstfol = first folder in this cabinet */
2169     /* lastfol  = last folder in this cabinet */
2170     /* predfol  = last folder in previous cabinet (or NULL if first cabinet) */
2171     predfol = lastfol;
2172     firstfol = cab->folders;
2173     for (lastfol = firstfol; lastfol->next;) lastfol = lastfol->next;
2174     mergeok = 1;
2175
2176     for (fi = cab->files; fi; fi = nextfi) {
2177       i = fi->index;
2178       nextfi = fi->next;
2179
2180       if (i < cffileCONTINUED_FROM_PREV) {
2181         for (fol = firstfol; fol && i--; ) fol = fol->next;
2182         fi->folder = fol; /* NULL if an invalid folder index */
2183       }
2184       else {
2185         /* folder merging */
2186         if (i == cffileCONTINUED_TO_NEXT
2187         ||  i == cffileCONTINUED_PREV_AND_NEXT) {
2188           if (cab->nextcab && !lastfol->contfile) lastfol->contfile = fi;
2189         }
2190
2191         if (i == cffileCONTINUED_FROM_PREV
2192         ||  i == cffileCONTINUED_PREV_AND_NEXT) {
2193           /* these files are to be continued in yet another
2194            * cabinet, don't merge them in just yet */
2195           if (i == cffileCONTINUED_PREV_AND_NEXT) mergeok = 0;
2196
2197           /* only merge once per cabinet */
2198           if (predfol) {
2199             if ((cfi = predfol->contfile)
2200             && (cfi->offset == fi->offset)
2201             && (cfi->length == fi->length)
2202             && (strcmp(cfi->filename, fi->filename) == 0)
2203             && (predfol->comp_type == firstfol->comp_type)) {
2204               /* increase the number of splits */
2205               if ((i = ++(predfol->num_splits)) > CAB_SPLITMAX) {
2206                 mergeok = 0;
2207                 ERR("%s: internal error: CAB_SPLITMAX exceeded. please report this to wine-devel@winehq.org)\n",
2208                     debugstr_a(basecab->filename));
2209               }
2210               else {
2211                 /* copy information across from the merged folder */
2212                 predfol->offset[i] = firstfol->offset[0];
2213                 predfol->cab[i]    = firstfol->cab[0];
2214                 predfol->next      = firstfol->next;
2215                 predfol->contfile  = firstfol->contfile;
2216
2217                 if (firstfol == lastfol) lastfol = predfol;
2218                 firstfol = predfol;
2219                 predfol = NULL; /* don't merge again within this cabinet */
2220               }
2221             }
2222             else {
2223               /* if the folders won't merge, don't add their files */
2224               mergeok = 0;
2225             }
2226           }
2227
2228           if (mergeok) fi->folder = firstfol;
2229         }
2230       }
2231
2232       if (fi->folder) {
2233         if (linkfi) linkfi->next = fi; else outfi = fi;
2234         linkfi = fi;
2235       }
2236     } /* for (fi= .. */
2237   } /* for (cab= ...*/
2238
2239   return outfi;
2240 }
2241
2242 /****************************************************************
2243  * convertUTF (internal)
2244  *
2245  * translate UTF -> ASCII
2246  *
2247  * UTF translates two-byte unicode characters into 1, 2 or 3 bytes.
2248  * %000000000xxxxxxx -> %0xxxxxxx
2249  * %00000xxxxxyyyyyy -> %110xxxxx %10yyyyyy
2250  * %xxxxyyyyyyzzzzzz -> %1110xxxx %10yyyyyy %10zzzzzz
2251  *
2252  * Therefore, the inverse is as follows:
2253  * First char:
2254  *  0x00 - 0x7F = one byte char
2255  *  0x80 - 0xBF = invalid
2256  *  0xC0 - 0xDF = 2 byte char (next char only 0x80-0xBF is valid)
2257  *  0xE0 - 0xEF = 3 byte char (next 2 chars only 0x80-0xBF is valid)
2258  *  0xF0 - 0xFF = invalid
2259  *
2260  * FIXME: use a winapi to do this
2261  */
2262 static int convertUTF(cab_UBYTE *in) {
2263   cab_UBYTE c, *out = in, *end = in + strlen((char *) in) + 1;
2264   cab_ULONG x;
2265
2266   do {
2267     /* read unicode character */
2268     if ((c = *in++) < 0x80) x = c;
2269     else {
2270       if (c < 0xC0) return 0;
2271       else if (c < 0xE0) {
2272         x = (c & 0x1F) << 6;
2273         if ((c = *in++) < 0x80 || c > 0xBF) return 0; else x |= (c & 0x3F);
2274       }
2275       else if (c < 0xF0) {
2276         x = (c & 0xF) << 12;
2277         if ((c = *in++) < 0x80 || c > 0xBF) return 0; else x |= (c & 0x3F)<<6;
2278         if ((c = *in++) < 0x80 || c > 0xBF) return 0; else x |= (c & 0x3F);
2279       }
2280       else return 0;
2281     }
2282
2283     /* terrible unicode -> ASCII conversion */
2284     if (x > 127) x = '_';
2285
2286     if (in > end) return 0; /* just in case */
2287   } while ((*out++ = (cab_UBYTE) x));
2288   return 1;
2289 }
2290
2291 /****************************************************
2292  * NONEdecompress (internal)
2293  */
2294 static int NONEdecompress(int inlen, int outlen, cab_decomp_state *decomp_state)
2295 {
2296   if (inlen != outlen) return DECR_ILLEGALDATA;
2297   memcpy(CAB(outbuf), CAB(inbuf), (size_t) inlen);
2298   return DECR_OK;
2299 }
2300
2301 /**************************************************
2302  * checksum (internal)
2303  */
2304 cab_ULONG checksum(cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum) {
2305   int len;
2306   cab_ULONG ul = 0;
2307
2308   for (len = bytes >> 2; len--; data += 4) {
2309     csum ^= ((data[0]) | (data[1]<<8) | (data[2]<<16) | (data[3]<<24));
2310   }
2311
2312   switch (bytes & 3) {
2313   case 3: ul |= *data++ << 16;
2314   case 2: ul |= *data++ <<  8;
2315   case 1: ul |= *data;
2316   }
2317   csum ^= ul;
2318
2319   return csum;
2320 }
2321
2322 /**********************************************************
2323  * decompress (internal)
2324  */
2325 static int decompress(struct cab_file *fi, int savemode, int fix, cab_decomp_state *decomp_state)
2326 {
2327   cab_ULONG bytes = savemode ? fi->length : fi->offset - CAB(offset);
2328   struct cabinet *cab = CAB(current)->cab[CAB(split)];
2329   cab_UBYTE buf[cfdata_SIZEOF], *data;
2330   cab_UWORD inlen, len, outlen, cando;
2331   cab_ULONG cksum;
2332   cab_LONG err;
2333
2334   TRACE("(fi == ^%p, savemode == %d, fix == %d)\n", fi, savemode, fix);
2335
2336   while (bytes > 0) {
2337     /* cando = the max number of bytes we can do */
2338     cando = CAB(outlen);
2339     if (cando > bytes) cando = bytes;
2340
2341     /* if cando != 0 */
2342     if (cando && savemode)
2343       file_write(fi, CAB(outpos), cando);
2344
2345     CAB(outpos) += cando;
2346     CAB(outlen) -= cando;
2347     bytes -= cando; if (!bytes) break;
2348
2349     /* we only get here if we emptied the output buffer */
2350
2351     /* read data header + data */
2352     inlen = outlen = 0;
2353     while (outlen == 0) {
2354       /* read the block header, skip the reserved part */
2355       if (!cabinet_read(cab, buf, cfdata_SIZEOF)) return DECR_INPUT;
2356       cabinet_skip(cab, cab->block_resv);
2357
2358       /* we shouldn't get blocks over CAB_INPUTMAX in size */
2359       data = CAB(inbuf) + inlen;
2360       len = EndGetI16(buf+cfdata_CompressedSize);
2361       inlen += len;
2362       if (inlen > CAB_INPUTMAX) return DECR_INPUT;
2363       if (!cabinet_read(cab, data, len)) return DECR_INPUT;
2364
2365       /* clear two bytes after read-in data */
2366       data[len+1] = data[len+2] = 0;
2367
2368       /* perform checksum test on the block (if one is stored) */
2369       cksum = EndGetI32(buf+cfdata_CheckSum);
2370       if (cksum && cksum != checksum(buf+4, 4, checksum(data, len, 0))) {
2371         /* checksum is wrong */
2372         if (fix && ((fi->folder->comp_type & cffoldCOMPTYPE_MASK)
2373                     == cffoldCOMPTYPE_MSZIP))
2374         {
2375           WARN("%s: checksum failed\n", debugstr_a(fi->filename));
2376         }
2377         else {
2378           return DECR_CHECKSUM;
2379         }
2380       }
2381
2382       /* outlen=0 means this block was part of a split block */
2383       outlen = EndGetI16(buf+cfdata_UncompressedSize);
2384       if (outlen == 0) {
2385         cabinet_close(cab);
2386         cab = CAB(current)->cab[++CAB(split)];
2387         if (!cabinet_open(cab)) return DECR_INPUT;
2388         cabinet_seek(cab, CAB(current)->offset[CAB(split)]);
2389       }
2390     }
2391
2392     /* decompress block */
2393     if ((err = CAB(decompress)(inlen, outlen, decomp_state))) {
2394       if (fix && ((fi->folder->comp_type & cffoldCOMPTYPE_MASK)
2395                   == cffoldCOMPTYPE_MSZIP))
2396       {
2397         ERR("%s: failed decrunching block\n", debugstr_a(fi->filename));
2398       }
2399       else {
2400         return err;
2401       }
2402     }
2403     CAB(outlen) = outlen;
2404     CAB(outpos) = CAB(outbuf);
2405   }
2406
2407   return DECR_OK;
2408 }
2409
2410 /****************************************************************
2411  * extract_file (internal)
2412  *
2413  * workhorse to extract a particular file from a cab
2414  */
2415 static void extract_file(struct cab_file *fi, int lower, int fix, LPCSTR dir, cab_decomp_state *decomp_state)
2416 {
2417   struct cab_folder *fol = fi->folder, *oldfol = CAB(current);
2418   cab_LONG err = DECR_OK;
2419
2420   TRACE("(fi == ^%p, lower == %d, fix == %d, dir == %s)\n", fi, lower, fix, debugstr_a(dir));
2421
2422   /* is a change of folder needed? do we need to reset the current folder? */
2423   if (fol != oldfol || fi->offset < CAB(offset)) {
2424     cab_UWORD comptype = fol->comp_type;
2425     int ct1 = comptype & cffoldCOMPTYPE_MASK;
2426     int ct2 = oldfol ? (oldfol->comp_type & cffoldCOMPTYPE_MASK) : 0;
2427
2428     /* if the archiver has changed, call the old archiver's free() function */
2429     if (ct1 != ct2) {
2430       switch (ct2) {
2431       case cffoldCOMPTYPE_LZX:
2432         if (LZX(window)) {
2433           free(LZX(window));
2434           LZX(window) = NULL;
2435         }
2436         break;
2437       case cffoldCOMPTYPE_QUANTUM:
2438         if (QTM(window)) {
2439           free(QTM(window));
2440           QTM(window) = NULL;
2441         }
2442         break;
2443       }
2444     }
2445
2446     switch (ct1) {
2447     case cffoldCOMPTYPE_NONE:
2448       CAB(decompress) = NONEdecompress;
2449       break;
2450
2451     case cffoldCOMPTYPE_MSZIP:
2452       CAB(decompress) = ZIPdecompress;
2453       break;
2454
2455     case cffoldCOMPTYPE_QUANTUM:
2456       CAB(decompress) = QTMdecompress;
2457       err = QTMinit((comptype >> 8) & 0x1f, (comptype >> 4) & 0xF, decomp_state);
2458       break;
2459
2460     case cffoldCOMPTYPE_LZX:
2461       CAB(decompress) = LZXdecompress;
2462       err = LZXinit((comptype >> 8) & 0x1f, decomp_state);
2463       break;
2464
2465     default:
2466       err = DECR_DATAFORMAT;
2467     }
2468     if (err) goto exit_handler;
2469
2470     /* initialisation OK, set current folder and reset offset */
2471     if (oldfol) cabinet_close(oldfol->cab[CAB(split)]);
2472     if (!cabinet_open(fol->cab[0])) goto exit_handler;
2473     cabinet_seek(fol->cab[0], fol->offset[0]);
2474     CAB(current) = fol;
2475     CAB(offset) = 0;
2476     CAB(outlen) = 0; /* discard existing block */
2477     CAB(split)  = 0;
2478   }
2479
2480   if (fi->offset > CAB(offset)) {
2481     /* decode bytes and send them to /dev/null */
2482     if ((err = decompress(fi, 0, fix, decomp_state))) goto exit_handler;
2483     CAB(offset) = fi->offset;
2484   }
2485
2486   if (!file_open(fi, lower, dir)) return;
2487   err = decompress(fi, 1, fix, decomp_state);
2488   if (err) CAB(current) = NULL; else CAB(offset) += fi->length;
2489   file_close(fi);
2490
2491 exit_handler:
2492   if (err) {
2493     const char *errmsg;
2494     const char *cabname;
2495     switch (err) {
2496     case DECR_NOMEMORY:
2497       errmsg = "out of memory!\n"; break;
2498     case DECR_ILLEGALDATA:
2499       errmsg = "%s: illegal or corrupt data\n"; break;
2500     case DECR_DATAFORMAT:
2501       errmsg = "%s: unsupported data format\n"; break;
2502     case DECR_CHECKSUM:
2503       errmsg = "%s: checksum error\n"; break;
2504     case DECR_INPUT:
2505       errmsg = "%s: input error\n"; break;
2506     case DECR_OUTPUT:
2507       errmsg = "%s: output error\n"; break;
2508     default:
2509       errmsg = "%s: unknown error (BUG)\n";
2510     }
2511
2512     if (CAB(current)) {
2513       cabname = (CAB(current)->cab[CAB(split)]->filename);
2514     }
2515     else {
2516       cabname = (fi->folder->cab[0]->filename);
2517     }
2518
2519     ERR(errmsg, cabname);
2520   }
2521 }
2522
2523 /*********************************************************
2524  * print_fileinfo (internal)
2525  */
2526 static void print_fileinfo(struct cab_file *fi) {
2527   char *fname = NULL;
2528
2529   if (fi->attribs & cffile_A_NAME_IS_UTF) {
2530     fname = malloc(strlen(fi->filename) + 1);
2531     if (fname) {
2532       strcpy(fname, fi->filename);
2533       convertUTF((cab_UBYTE *) fname);
2534     }
2535   }
2536
2537   TRACE("%9u | %02d.%02d.%04d %02d:%02d:%02d | %s\n",
2538     fi->length,
2539     fi->date & 0x1f, (fi->date>>5) & 0xf, (fi->date>>9) + 1980,
2540     fi->time >> 11, (fi->time>>5) & 0x3f, (fi->time << 1) & 0x3e,
2541     fname ? fname : fi->filename
2542   );
2543
2544   if (fname) free(fname);
2545 }
2546
2547 /****************************************************************************
2548  * process_cabinet (internal)
2549  *
2550  * called to simply "extract" a cabinet file.  Will find every cabinet file
2551  * in that file, search for every chained cabinet attached to those cabinets,
2552  * and will either extract the cabinets, or ? (call a callback?)
2553  *
2554  * PARAMS
2555  *   cabname [I] name of the cabinet file to extract
2556  *   dir     [I] directory to extract to
2557  *   fix     [I] attempt to process broken cabinets
2558  *   lower   [I] ? (lower case something or other?)
2559  *   dest    [O]
2560  *
2561  * RETURNS
2562  *   Success: TRUE
2563  *   Failure: FALSE
2564  */
2565 BOOL process_cabinet(LPCSTR cabname, LPCSTR dir, BOOL fix, BOOL lower, EXTRACTdest *dest)
2566 {
2567   struct cabinet *basecab, *cab, *cab1, *cab2;
2568   struct cab_file *filelist, *fi;
2569   struct ExtractFileList **destlistptr = &(dest->filelist);
2570
2571   /* The first result of a search will be returned, and
2572    * the remaining results will be chained to it via the cab->next structure
2573    * member.
2574    */
2575   cab_UBYTE search_buf[CAB_SEARCH_SIZE];
2576
2577   cab_decomp_state decomp_state_local;
2578   cab_decomp_state *decomp_state = &decomp_state_local;
2579
2580   /* has the list-mode header been seen before? */
2581   int viewhdr = 0;
2582
2583   ZeroMemory(decomp_state, sizeof(cab_decomp_state));
2584
2585   TRACE("Extract %s\n", debugstr_a(cabname));
2586
2587   /* load the file requested */
2588   basecab = find_cabs_in_file(cabname, search_buf);
2589   if (!basecab) return FALSE;
2590
2591   /* iterate over all cabinets found in that file */
2592   for (cab = basecab; cab; cab=cab->next) {
2593
2594     /* bi-directionally load any spanning cabinets -- backwards */
2595     for (cab1 = cab; cab1->flags & cfheadPREV_CABINET; cab1 = cab1->prevcab) {
2596       TRACE("%s: extends backwards to %s (%s)\n", debugstr_a(cabname),
2597             debugstr_a(cab1->prevname), debugstr_a(cab1->previnfo));
2598       find_cabinet_file(&(cab1->prevname), cabname);
2599       if (!(cab1->prevcab = load_cab_offset(cab1->prevname, 0))) {
2600         ERR("%s: can't read previous cabinet %s\n", debugstr_a(cabname), debugstr_a(cab1->prevname));
2601         break;
2602       }
2603       cab1->prevcab->nextcab = cab1;
2604     }
2605
2606     /* bi-directionally load any spanning cabinets -- forwards */
2607     for (cab2 = cab; cab2->flags & cfheadNEXT_CABINET; cab2 = cab2->nextcab) {
2608       TRACE("%s: extends to %s (%s)\n", debugstr_a(cabname),
2609             debugstr_a(cab2->nextname), debugstr_a(cab2->nextinfo));
2610       find_cabinet_file(&(cab2->nextname), cabname);
2611       if (!(cab2->nextcab = load_cab_offset(cab2->nextname, 0))) {
2612         ERR("%s: can't read next cabinet %s\n", debugstr_a(cabname), debugstr_a(cab2->nextname));
2613         break;
2614       }
2615       cab2->nextcab->prevcab = cab2;
2616     }
2617
2618     filelist = process_files(cab1);
2619     CAB(current) = NULL;
2620
2621     if (!viewhdr) {
2622       TRACE("File size | Date       Time     | Name\n");
2623       TRACE("----------+---------------------+-------------\n");
2624       viewhdr = 1;
2625     }
2626     for (fi = filelist; fi; fi = fi->next) {
2627         print_fileinfo(fi);
2628         dest->filecount++;
2629     }
2630     TRACE("Beginning Extraction...\n");
2631     for (fi = filelist; fi; fi = fi->next) {
2632         TRACE("  extracting: %s\n", debugstr_a(fi->filename));
2633         extract_file(fi, lower, fix, dir, decomp_state);
2634         sprintf(dest->lastfile, "%s%s%s",
2635                 strlen(dest->directory) ? dest->directory : "",
2636                 strlen(dest->directory) ? "\\": "",
2637                 fi->filename);
2638         *destlistptr = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY,
2639                                 sizeof(struct ExtractFileList));
2640         if(*destlistptr) {
2641            (*destlistptr)->unknown = TRUE; /* FIXME: were do we get the value? */
2642            (*destlistptr)->filename = HeapAlloc(GetProcessHeap(), 0, (
2643                                                 strlen(fi->filename)+1));
2644            if((*destlistptr)->filename)
2645                 lstrcpyA((*destlistptr)->filename, fi->filename);
2646            destlistptr = &((*destlistptr)->next);
2647         }
2648     }
2649   }
2650
2651   TRACE("Finished processing cabinet.\n");
2652
2653   return TRUE;
2654 }