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