4 * Copyright 2000-2002 Stuart Caie
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.
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.
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
20 * Principal author: Stuart Caie <kyzer@4u.net>
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.
39 #include "wine/debug.h"
41 WINE_DEFAULT_DEBUG_CHANNEL(cabinet
);
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
47 cab_UBYTE search_buf
[CAB_SEARCH_SIZE
];
49 cab_decomp_state decomp_state
;
51 /* all the file IO is abstracted into these routines:
52 * cabinet_(open|close|read|seek|skip|getoffset)
53 * file_(open|close|write)
56 /* try to open a cabinet file, returns success */
57 BOOL
cabinet_open(struct cabinet
*cab
)
59 char *name
= (char *)cab
->filename
;
62 TRACE("(cab == ^%p)\n", cab
);
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
));
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
));
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
));
90 /*******************************************************************
91 * cabinet_close (internal)
93 * close the file handle in a struct cabinet.
95 void cabinet_close(struct cabinet
*cab
) {
96 TRACE("(cab == ^%p)\n", cab
);
97 if (cab
->fh
) CloseHandle(cab
->fh
);
101 /*******************************************************
102 * ensure_filepath2 (internal)
104 BOOL
ensure_filepath2(char *path
) {
109 new_path
= HeapAlloc(GetProcessHeap(), 0, (strlen(path
) + 1));
110 strcpy(new_path
, path
);
112 while((len
= strlen(new_path
)) && new_path
[len
- 1] == '\\')
113 new_path
[len
- 1] = 0;
115 TRACE("About to try to create directory %s\n", debugstr_a(new_path
));
116 while(!CreateDirectoryA(new_path
, NULL
)) {
118 DWORD last_error
= GetLastError();
120 if(last_error
== ERROR_ALREADY_EXISTS
)
123 if(last_error
!= ERROR_PATH_NOT_FOUND
) {
128 if(!(slash
= strrchr(new_path
, '\\'))) {
133 len
= slash
- new_path
;
135 if(! ensure_filepath2(new_path
)) {
139 new_path
[len
] = '\\';
140 TRACE("New path in next iteration: %s\n", debugstr_a(new_path
));
143 HeapFree(GetProcessHeap(), 0, new_path
);
148 /**********************************************************************
149 * ensure_filepath (internal)
151 * ensure_filepath("a\b\c\d.txt") ensures a, a\b and a\b\c exist as dirs
153 BOOL
ensure_filepath(char *path
) {
154 char new_path
[MAX_PATH
];
155 int len
, i
, lastslashpos
= -1;
157 TRACE("(path == %s)\n", debugstr_a(path
));
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
] == '\\')
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
);
177 /*******************************************************************
178 * file_open (internal)
180 * opens a file for output, returns success
182 BOOL
file_open(struct cab_file
*fi
, BOOL lower
, LPCSTR dir
)
184 char c
, *s
, *d
, *name
;
187 TRACE("(fi == ^%p, lower == %s, dir == %s)\n", fi
, lower
? "TRUE" : "FALSE", debugstr_a(dir
));
189 if (!(name
= malloc(strlen(fi
->filename
) + (dir
? strlen(dir
) : 0) + 2))) {
190 ERR("out of memory!\n");
194 /* start with blank name */
197 /* add output directory if needed */
203 /* remove leading slashes */
204 s
= (char *) fi
->filename
;
205 while (*s
== '\\') s
++;
207 /* copy from fi->filename to new name.
208 * lowercases characters if needed.
210 d
= &name
[strlen(name
)];
213 *d
++ = (lower
? tolower((unsigned char) c
) : c
);
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
)
223 ERR("CreateFileA returned INVALID_HANDLE_VALUE\n");
227 ERR("Couldn't ensure filepath for %s", debugstr_a(name
));
230 ERR("Couldn't open file %s for writing\n", debugstr_a(name
));
233 /* as full filename is no longer needed, free it */
239 /********************************************************
240 * close_file (internal)
242 * closes a completed file
244 void file_close(struct cab_file
*fi
)
246 TRACE("(fi == ^%p)\n", fi
);
254 /******************************************************************
255 * file_write (internal)
257 * writes from buf to a file specified as a cab_file struct.
258 * returns success/failure
260 BOOL
file_write(struct cab_file
*fi
, cab_UBYTE
*buf
, cab_off_t length
)
264 TRACE("(fi == ^%p, buf == ^%p, length == %u)\n", fi
, buf
, length
);
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
));
275 /*******************************************************************
276 * cabinet_skip (internal)
278 * advance the file pointer associated with the cab structure
281 void cabinet_skip(struct cabinet
*cab
, cab_off_t distance
)
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
));
290 /*******************************************************************
291 * cabinet_seek (internal)
293 * seek to the specified absolute offset in a cab
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
));
301 /*******************************************************************
302 * cabinet_getoffset (internal)
304 * returns the file pointer position of a cab
306 cab_off_t
cabinet_getoffset(struct cabinet
*cab
)
308 return SetFilePointer(cab
->fh
, 0, NULL
, FILE_CURRENT
);
311 /*******************************************************************
312 * cabinet_read (internal)
314 * read data from a cabinet, returns success
316 BOOL
cabinet_read(struct cabinet
*cab
, cab_UBYTE
*buf
, cab_off_t length
)
319 cab_off_t avail
= cab
->filelen
- cabinet_getoffset(cab
);
321 TRACE("(cab == ^%p, buf == ^%p, length == %u)\n", cab
, buf
, length
);
323 if (length
> avail
) {
324 WARN("%s: WARNING; cabinet is truncated\n", debugstr_a((char *)cab
->filename
));
328 if (! ReadFile( cab
->fh
, (LPVOID
) buf
, length
, &bytes_read
, NULL
)) {
329 ERR("%s read error\n", debugstr_a((char *) cab
->filename
));
331 } else if (bytes_read
!= length
) {
332 ERR("%s read size mismatch\n", debugstr_a((char *) cab
->filename
));
339 /**********************************************************************
340 * cabinet_read_string (internal)
342 * allocate and read an aribitrarily long string from the cabinet
344 char *cabinet_read_string(struct cabinet
*cab
)
346 cab_off_t len
=256, base
= cabinet_getoffset(cab
), maxlen
= cab
->filelen
- base
;
349 cab_UBYTE
*buf
= NULL
;
351 TRACE("(cab == ^%p)\n", cab
);
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;
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;}
365 ERR("%s: WARNING; cabinet is truncated\n", debugstr_a((char *) cab
->filename
));
369 cabinet_seek(cab
, base
);
377 ERR("out of memory!\n");
381 /* otherwise, set the stream to just after the string and return */
382 cabinet_seek(cab
, base
+ ((cab_off_t
) strlen((char *) buf
)) + 1);
387 /******************************************************************
388 * cabinet_read_entries (internal)
390 * reads the header and all folder and file entries in this cabinet
392 BOOL
cabinet_read_entries(struct cabinet
*cab
)
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
;
400 TRACE("(cab == ^%p)\n", cab
);
402 /* read in the CFHEADER */
403 base_offset
= cabinet_getoffset(cab
);
404 if (!cabinet_read(cab
, buf
, cfhead_SIZEOF
)) {
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
));
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
));
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
));
428 /* just check the header revision */
429 if ((buf
[cfhead_MajorVersion
] > 1) ||
430 (buf
[cfhead_MajorVersion
] == 1 && buf
[cfhead_MinorVersion
] > 3))
432 WARN("%s: WARNING; cabinet format version > 1.3\n", debugstr_a((char *) cab
->filename
));
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
];
443 if (header_resv
> 60000) {
444 WARN("%s: WARNING; header reserved space > 60000\n", debugstr_a((char *) cab
->filename
));
447 /* skip the reserved header */
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
));
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
);
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
);
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
);
470 fol
= (struct cab_folder
*) calloc(1, sizeof(struct cab_folder
));
472 ERR("out of memory!\n");
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
);
490 for (i
= 0; i
< num_files
; i
++) {
491 if (!cabinet_read(cab
, buf
, cffile_SIZEOF
))
494 file
= (struct cab_file
*) calloc(1, sizeof(struct cab_file
));
496 ERR("out of memory!\n");
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
);
514 linkfile
->next
= file
;
521 /***********************************************************
522 * load_cab_offset (internal)
524 * validates and reads file entries from a cabinet at offset [offset] in
525 * file [name]. Returns a cabinet structure if successful, or NULL
528 struct cabinet
*load_cab_offset(LPCSTR name
, cab_off_t offset
)
530 struct cabinet
*cab
= (struct cabinet
*) calloc(1, sizeof(struct cabinet
));
533 TRACE("(name == %s, offset == %u)\n", debugstr_a((char *) name
), offset
);
535 if (!cab
) return NULL
;
537 cab
->filename
= name
;
538 if ((ok
= cabinet_open(cab
))) {
539 cabinet_seek(cab
, offset
);
540 ok
= cabinet_read_entries(cab
);
549 /* MSZIP decruncher */
551 /* Dirk Stoecker wrote the ZIP decoder, based on the InfoZip deflate code */
553 /* Tables for deflate from PKZIP's appnote.txt. */
554 static const cab_UBYTE Zipborder
[] = /* Order of the bit length code lengths */
555 { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
556 static const cab_UWORD Zipcplens
[] = /* Copy lengths for literal codes 257..285 */
557 { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51,
558 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
559 static const cab_UWORD Zipcplext
[] = /* Extra bits for literal codes 257..285 */
560 { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
561 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
562 static const cab_UWORD Zipcpdist
[] = /* Copy offsets for distance codes 0..29 */
563 { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
564 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
565 static const cab_UWORD Zipcpdext
[] = /* Extra bits for distance codes */
566 { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
567 10, 11, 11, 12, 12, 13, 13};
569 /* And'ing with Zipmask[n] masks the lower n bits */
570 static const cab_UWORD Zipmask
[17] = {
571 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
572 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
575 #define ZIPNEEDBITS(n) {while(k<(n)){cab_LONG c=*(ZIP(inpos)++);\
576 b|=((cab_ULONG)c)<<k;k+=8;}}
577 #define ZIPDUMPBITS(n) {b>>=(n);k-=(n);}
580 /********************************************************
581 * Ziphuft_free (internal)
583 void Ziphuft_free(struct Ziphuft
*t
)
585 register struct Ziphuft
*p
, *q
;
587 /* Go through linked list, freeing from the allocated (t[-1]) address. */
589 while (p
!= (struct Ziphuft
*)NULL
)
597 /*********************************************************
598 * Ziphuft_build (internal)
600 cab_LONG
Ziphuft_build(cab_ULONG
*b
, cab_ULONG n
, cab_ULONG s
, cab_UWORD
*d
, cab_UWORD
*e
,
601 struct Ziphuft
**t
, cab_LONG
*m
)
603 cab_ULONG a
; /* counter for codes of length k */
604 cab_ULONG el
; /* length of EOB code (value 256) */
605 cab_ULONG f
; /* i repeats in table every f entries */
606 cab_LONG g
; /* maximum code length */
607 cab_LONG h
; /* table level */
608 register cab_ULONG i
; /* counter, current code */
609 register cab_ULONG j
; /* counter */
610 register cab_LONG k
; /* number of bits in current code */
611 cab_LONG
*l
; /* stack of bits per table */
612 register cab_ULONG
*p
; /* pointer into ZIP(c)[],ZIP(b)[],ZIP(v)[] */
613 register struct Ziphuft
*q
; /* points to current table */
614 struct Ziphuft r
; /* table entry for structure assignment */
615 register cab_LONG w
; /* bits before this table == (l * h) */
616 cab_ULONG
*xp
; /* pointer into x */
617 cab_LONG y
; /* number of dummy codes added */
618 cab_ULONG z
; /* number of entries in current table */
622 /* Generate counts for each bit length */
623 el
= n
> 256 ? b
[256] : ZIPBMAX
; /* set length of EOB code, if any */
625 for(i
= 0; i
< ZIPBMAX
+1; ++i
)
630 ZIP(c
)[*p
]++; p
++; /* assume all entries <= ZIPBMAX */
632 if (ZIP(c
)[0] == n
) /* null input--all zero length codes */
634 *t
= (struct Ziphuft
*)NULL
;
639 /* Find minimum and maximum length, bound *m by those */
640 for (j
= 1; j
<= ZIPBMAX
; j
++)
643 k
= j
; /* minimum code length */
644 if ((cab_ULONG
)*m
< j
)
646 for (i
= ZIPBMAX
; i
; i
--)
649 g
= i
; /* maximum code length */
650 if ((cab_ULONG
)*m
> i
)
653 /* Adjust last length count to fill out codes, if needed */
654 for (y
= 1 << j
; j
< i
; j
++, y
<<= 1)
655 if ((y
-= ZIP(c
)[j
]) < 0)
656 return 2; /* bad input: more codes than bits */
657 if ((y
-= ZIP(c
)[i
]) < 0)
661 /* Generate starting offsets LONGo the value table for each length */
663 p
= ZIP(c
) + 1; xp
= ZIP(x
) + 2;
665 { /* note that i == g from above */
669 /* Make a table of values in order of bit lengths */
673 ZIP(v
)[ZIP(x
)[j
]++] = i
;
677 /* Generate the Huffman codes and for each, make the table entries */
678 ZIP(x
)[0] = i
= 0; /* first Huffman code is zero */
679 p
= ZIP(v
); /* grab values in bit order */
680 h
= -1; /* no tables yet--level -1 */
681 w
= l
[-1] = 0; /* no bits decoded yet */
682 ZIP(u
)[0] = (struct Ziphuft
*)NULL
; /* just to keep compilers happy */
683 q
= (struct Ziphuft
*)NULL
; /* ditto */
686 /* go through the bit lengths (k already is bits in shortest code) */
692 /* here i is the Huffman code of length k bits for value *p */
693 /* make tables up to required level */
696 w
+= l
[h
++]; /* add bits already decoded */
698 /* compute minimum size table less than or equal to *m bits */
699 z
= (z
= g
- w
) > (cab_ULONG
)*m
? *m
: z
; /* upper limit */
700 if ((f
= 1 << (j
= k
- w
)) > a
+ 1) /* try a k-w bit table */
701 { /* too few codes for k-w bit table */
702 f
-= a
+ 1; /* deduct codes from patterns left */
704 while (++j
< z
) /* try smaller tables up to z bits */
706 if ((f
<<= 1) <= *++xp
)
707 break; /* enough codes to use up j bits */
708 f
-= *xp
; /* else deduct codes from patterns */
711 if ((cab_ULONG
)w
+ j
> el
&& (cab_ULONG
)w
< el
)
712 j
= el
- w
; /* make EOB code end at table */
713 z
= 1 << j
; /* table entries for j-bit table */
714 l
[h
] = j
; /* set table size in stack */
716 /* allocate and link in new table */
717 if (!(q
= (struct Ziphuft
*) malloc((z
+ 1)*sizeof(struct Ziphuft
))))
720 Ziphuft_free(ZIP(u
)[0]);
721 return 3; /* not enough memory */
723 *t
= q
+ 1; /* link to list for Ziphuft_free() */
724 *(t
= &(q
->v
.t
)) = (struct Ziphuft
*)NULL
;
725 ZIP(u
)[h
] = ++q
; /* table starts after link */
727 /* connect to last table, if there is one */
730 ZIP(x
)[h
] = i
; /* save pattern for backing up */
731 r
.b
= (cab_UBYTE
)l
[h
-1]; /* bits to dump before this table */
732 r
.e
= (cab_UBYTE
)(16 + j
); /* bits in this table */
733 r
.v
.t
= q
; /* pointer to this table */
734 j
= (i
& ((1 << w
) - 1)) >> (w
- l
[h
-1]);
735 ZIP(u
)[h
-1][j
] = r
; /* connect to last table */
739 /* set up table entry in r */
740 r
.b
= (cab_UBYTE
)(k
- w
);
742 r
.e
= 99; /* out of values--invalid code */
745 r
.e
= (cab_UBYTE
)(*p
< 256 ? 16 : 15); /* 256 is end-of-block code */
746 r
.v
.n
= *p
++; /* simple code is just the value */
750 r
.e
= (cab_UBYTE
)e
[*p
- s
]; /* non-simple--look up in lists */
754 /* fill code-like entries with r */
756 for (j
= i
>> w
; j
< z
; j
+= f
)
759 /* backwards increment the k-bit code i */
760 for (j
= 1 << (k
- 1); i
& j
; j
>>= 1)
764 /* backup over finished tables */
765 while ((i
& ((1 << w
) - 1)) != ZIP(x
)[h
])
766 w
-= l
[--h
]; /* don't need to update q */
770 /* return actual size of base table */
773 /* Return true (1) if we were given an incomplete table */
774 return y
!= 0 && g
!= 1;
777 /*********************************************************
778 * Zipinflate_codes (internal)
780 cab_LONG
Zipinflate_codes(struct Ziphuft
*tl
, struct Ziphuft
*td
,
781 cab_LONG bl
, cab_LONG bd
)
783 register cab_ULONG e
; /* table entry flag/number of extra bits */
784 cab_ULONG n
, d
; /* length and index for copy */
785 cab_ULONG w
; /* current window position */
786 struct Ziphuft
*t
; /* pointer to table entry */
787 cab_ULONG ml
, md
; /* masks for bl and bd bits */
788 register cab_ULONG b
; /* bit buffer */
789 register cab_ULONG k
; /* number of bits in bit buffer */
791 /* make local copies of globals */
792 b
= ZIP(bb
); /* initialize bit buffer */
794 w
= ZIP(window_posn
); /* initialize window position */
796 /* inflate the coded data */
797 ml
= Zipmask
[bl
]; /* precompute masks for speed */
802 ZIPNEEDBITS((cab_ULONG
)bl
)
803 if((e
= (t
= tl
+ ((cab_ULONG
)b
& ml
))->e
) > 16)
811 } while ((e
= (t
= t
->v
.t
+ ((cab_ULONG
)b
& Zipmask
[e
]))->e
) > 16);
813 if (e
== 16) /* then it's a literal */
814 CAB(outbuf
)[w
++] = (cab_UBYTE
)t
->v
.n
;
815 else /* it's an EOB or a length */
817 /* exit if end of block */
821 /* get length of block to copy */
823 n
= t
->v
.n
+ ((cab_ULONG
)b
& Zipmask
[e
]);
826 /* decode distance of block to copy */
827 ZIPNEEDBITS((cab_ULONG
)bd
)
828 if ((e
= (t
= td
+ ((cab_ULONG
)b
& md
))->e
) > 16)
835 } while ((e
= (t
= t
->v
.t
+ ((cab_ULONG
)b
& Zipmask
[e
]))->e
) > 16);
838 d
= w
- t
->v
.n
- ((cab_ULONG
)b
& Zipmask
[e
]);
842 n
-= (e
= (e
= ZIPWSIZE
- ((d
&= ZIPWSIZE
-1) > w
? d
: w
)) > n
?n
:e
);
845 CAB(outbuf
)[w
++] = CAB(outbuf
)[d
++];
851 /* restore the globals from the locals */
852 ZIP(window_posn
) = w
; /* restore global window pointer */
853 ZIP(bb
) = b
; /* restore global bit buffer */
860 /***********************************************************
861 * Zipinflate_stored (internal)
863 cab_LONG
Zipinflate_stored(void)
864 /* "decompress" an inflated type 0 (stored) block. */
866 cab_ULONG n
; /* number of bytes in block */
867 cab_ULONG w
; /* current window position */
868 register cab_ULONG b
; /* bit buffer */
869 register cab_ULONG k
; /* number of bits in bit buffer */
871 /* make local copies of globals */
872 b
= ZIP(bb
); /* initialize bit buffer */
874 w
= ZIP(window_posn
); /* initialize window position */
876 /* go to byte boundary */
880 /* get the length and its complement */
882 n
= ((cab_ULONG
)b
& 0xffff);
885 if (n
!= (cab_ULONG
)((~b
) & 0xffff))
886 return 1; /* error in compressed data */
889 /* read and output the compressed data */
893 CAB(outbuf
)[w
++] = (cab_UBYTE
)b
;
897 /* restore the globals from the locals */
898 ZIP(window_posn
) = w
; /* restore global window pointer */
899 ZIP(bb
) = b
; /* restore global bit buffer */
904 /******************************************************
905 * Zipinflate_fixed (internal)
907 cab_LONG
Zipinflate_fixed(void)
909 struct Ziphuft
*fixed_tl
;
910 struct Ziphuft
*fixed_td
;
911 cab_LONG fixed_bl
, fixed_bd
;
912 cab_LONG i
; /* temporary variable */
918 for(i
= 0; i
< 144; i
++)
924 for(; i
< 288; i
++) /* make a complete, but wrong code set */
927 if((i
= Ziphuft_build(l
, 288, 257, (cab_UWORD
*) Zipcplens
,
928 (cab_UWORD
*) Zipcplext
, &fixed_tl
, &fixed_bl
)))
932 for(i
= 0; i
< 30; i
++) /* make an incomplete code set */
935 if((i
= Ziphuft_build(l
, 30, 0, (cab_UWORD
*) Zipcpdist
, (cab_UWORD
*) Zipcpdext
,
936 &fixed_td
, &fixed_bd
)) > 1)
938 Ziphuft_free(fixed_tl
);
942 /* decompress until an end-of-block code */
943 i
= Zipinflate_codes(fixed_tl
, fixed_td
, fixed_bl
, fixed_bd
);
945 Ziphuft_free(fixed_td
);
946 Ziphuft_free(fixed_tl
);
950 /**************************************************************
951 * Zipinflate_dynamic (internal)
953 cab_LONG
Zipinflate_dynamic(void)
954 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
956 cab_LONG i
; /* temporary variables */
959 cab_ULONG l
; /* last length */
960 cab_ULONG m
; /* mask for bit lengths table */
961 cab_ULONG n
; /* number of lengths to get */
962 struct Ziphuft
*tl
; /* literal/length code table */
963 struct Ziphuft
*td
; /* distance code table */
964 cab_LONG bl
; /* lookup bits for tl */
965 cab_LONG bd
; /* lookup bits for td */
966 cab_ULONG nb
; /* number of bit length codes */
967 cab_ULONG nl
; /* number of literal/length codes */
968 cab_ULONG nd
; /* number of distance codes */
969 register cab_ULONG b
; /* bit buffer */
970 register cab_ULONG k
; /* number of bits in bit buffer */
972 /* make local bit buffer */
977 /* read in table lengths */
979 nl
= 257 + ((cab_ULONG
)b
& 0x1f); /* number of literal/length codes */
982 nd
= 1 + ((cab_ULONG
)b
& 0x1f); /* number of distance codes */
985 nb
= 4 + ((cab_ULONG
)b
& 0xf); /* number of bit length codes */
987 if(nl
> 288 || nd
> 32)
988 return 1; /* bad lengths */
990 /* read in bit-length-code lengths */
991 for(j
= 0; j
< nb
; j
++)
994 ll
[Zipborder
[j
]] = (cab_ULONG
)b
& 7;
998 ll
[Zipborder
[j
]] = 0;
1000 /* build decoding table for trees--single level, 7 bit lookup */
1002 if((i
= Ziphuft_build(ll
, 19, 19, NULL
, NULL
, &tl
, &bl
)) != 0)
1006 return i
; /* incomplete code set */
1009 /* read in literal and distance code lengths */
1013 while((cab_ULONG
)i
< n
)
1015 ZIPNEEDBITS((cab_ULONG
)bl
)
1016 j
= (td
= tl
+ ((cab_ULONG
)b
& m
))->b
;
1019 if (j
< 16) /* length of code in bits (0..15) */
1020 ll
[i
++] = l
= j
; /* save last length in l */
1021 else if (j
== 16) /* repeat last length 3 to 6 times */
1024 j
= 3 + ((cab_ULONG
)b
& 3);
1026 if((cab_ULONG
)i
+ j
> n
)
1031 else if (j
== 17) /* 3 to 10 zero length codes */
1034 j
= 3 + ((cab_ULONG
)b
& 7);
1036 if ((cab_ULONG
)i
+ j
> n
)
1042 else /* j == 18: 11 to 138 zero length codes */
1045 j
= 11 + ((cab_ULONG
)b
& 0x7f);
1047 if ((cab_ULONG
)i
+ j
> n
)
1055 /* free decoding table for trees */
1058 /* restore the global bit buffer */
1062 /* build the decoding tables for literal/length and distance codes */
1064 if((i
= Ziphuft_build(ll
, nl
, 257, (cab_UWORD
*) Zipcplens
, (cab_UWORD
*) Zipcplext
, &tl
, &bl
)) != 0)
1068 return i
; /* incomplete code set */
1071 Ziphuft_build(ll
+ nl
, nd
, 0, (cab_UWORD
*) Zipcpdist
, (cab_UWORD
*) Zipcpdext
, &td
, &bd
);
1073 /* decompress until an end-of-block code */
1074 if(Zipinflate_codes(tl
, td
, bl
, bd
))
1077 /* free the decoding tables, return */
1083 /*****************************************************
1084 * Zipinflate_block (internal)
1086 cab_LONG
Zipinflate_block(cab_LONG
*e
) /* e == last block flag */
1087 { /* decompress an inflated block */
1088 cab_ULONG t
; /* block type */
1089 register cab_ULONG b
; /* bit buffer */
1090 register cab_ULONG k
; /* number of bits in bit buffer */
1092 /* make local bit buffer */
1096 /* read in last block bit */
1098 *e
= (cab_LONG
)b
& 1;
1101 /* read in block type */
1103 t
= (cab_ULONG
)b
& 3;
1106 /* restore the global bit buffer */
1110 /* inflate that block type */
1112 return Zipinflate_dynamic();
1114 return Zipinflate_stored();
1116 return Zipinflate_fixed();
1117 /* bad block type */
1121 /****************************************************
1122 * Zipdecompress (internal)
1124 int ZIPdecompress(int inlen
, int outlen
)
1126 cab_LONG e
; /* last block flag */
1128 TRACE("(inlen == %d, outlen == %d)\n", inlen
, outlen
);
1130 ZIP(inpos
) = CAB(inbuf
);
1131 ZIP(bb
) = ZIP(bk
) = ZIP(window_posn
) = 0;
1132 if(outlen
> ZIPWSIZE
)
1133 return DECR_DATAFORMAT
;
1135 /* CK = Chris Kirmse, official Microsoft purloiner */
1136 if(ZIP(inpos
)[0] != 0x43 || ZIP(inpos
)[1] != 0x4B)
1137 return DECR_ILLEGALDATA
;
1142 if(Zipinflate_block(&e
))
1143 return DECR_ILLEGALDATA
;
1146 /* return success */
1150 /* Quantum decruncher */
1152 /* This decruncher was researched and implemented by Matthew Russoto. */
1153 /* It has since been tidied up by Stuart Caie */
1155 static cab_UBYTE q_length_base
[27], q_length_extra
[27], q_extra_bits
[42];
1156 static cab_ULONG q_position_base
[42];
1158 /******************************************************************
1159 * QTMinitmodel (internal)
1161 * Initialise a model which decodes symbols from [s] to [s]+[n]-1
1163 void QTMinitmodel(struct QTMmodel
*m
, struct QTMmodelsym
*sym
, int n
, int s
) {
1168 memset(m
->tabloc
, 0xFF, sizeof(m
->tabloc
)); /* clear out look-up table */
1169 for (i
= 0; i
< n
; i
++) {
1170 m
->tabloc
[i
+s
] = i
; /* set up a look-up entry for symbol */
1171 m
->syms
[i
].sym
= i
+s
; /* actual symbol */
1172 m
->syms
[i
].cumfreq
= n
-i
; /* current frequency of that symbol */
1174 m
->syms
[n
].cumfreq
= 0;
1177 /******************************************************************
1178 * QTMinit (internal)
1180 int QTMinit(int window
, int level
) {
1181 int wndsize
= 1 << window
, msz
= window
* 2, i
;
1184 /* QTM supports window sizes of 2^10 (1Kb) through 2^21 (2Mb) */
1185 /* if a previously allocated window is big enough, keep it */
1186 if (window
< 10 || window
> 21) return DECR_DATAFORMAT
;
1187 if (QTM(actual_size
) < wndsize
) {
1188 if (QTM(window
)) free(QTM(window
));
1192 if (!(QTM(window
) = malloc(wndsize
))) return DECR_NOMEMORY
;
1193 QTM(actual_size
) = wndsize
;
1195 QTM(window_size
) = wndsize
;
1196 QTM(window_posn
) = 0;
1198 /* initialise static slot/extrabits tables */
1199 for (i
= 0, j
= 0; i
< 27; i
++) {
1200 q_length_extra
[i
] = (i
== 26) ? 0 : (i
< 2 ? 0 : i
- 2) >> 2;
1201 q_length_base
[i
] = j
; j
+= 1 << ((i
== 26) ? 5 : q_length_extra
[i
]);
1203 for (i
= 0, j
= 0; i
< 42; i
++) {
1204 q_extra_bits
[i
] = (i
< 2 ? 0 : i
-2) >> 1;
1205 q_position_base
[i
] = j
; j
+= 1 << q_extra_bits
[i
];
1208 /* initialise arithmetic coding models */
1210 QTMinitmodel(&QTM(model7
), &QTM(m7sym
)[0], 7, 0);
1212 QTMinitmodel(&QTM(model00
), &QTM(m00sym
)[0], 0x40, 0x00);
1213 QTMinitmodel(&QTM(model40
), &QTM(m40sym
)[0], 0x40, 0x40);
1214 QTMinitmodel(&QTM(model80
), &QTM(m80sym
)[0], 0x40, 0x80);
1215 QTMinitmodel(&QTM(modelC0
), &QTM(mC0sym
)[0], 0x40, 0xC0);
1217 /* model 4 depends on table size, ranges from 20 to 24 */
1218 QTMinitmodel(&QTM(model4
), &QTM(m4sym
)[0], (msz
< 24) ? msz
: 24, 0);
1219 /* model 5 depends on table size, ranges from 20 to 36 */
1220 QTMinitmodel(&QTM(model5
), &QTM(m5sym
)[0], (msz
< 36) ? msz
: 36, 0);
1221 /* model 6pos depends on table size, ranges from 20 to 42 */
1222 QTMinitmodel(&QTM(model6pos
), &QTM(m6psym
)[0], msz
, 0);
1223 QTMinitmodel(&QTM(model6len
), &QTM(m6lsym
)[0], 27, 0);
1228 /****************************************************************
1229 * QTMupdatemodel (internal)
1231 void QTMupdatemodel(struct QTMmodel
*model
, int sym
) {
1232 struct QTMmodelsym temp
;
1235 for (i
= 0; i
< sym
; i
++) model
->syms
[i
].cumfreq
+= 8;
1237 if (model
->syms
[0].cumfreq
> 3800) {
1238 if (--model
->shiftsleft
) {
1239 for (i
= model
->entries
- 1; i
>= 0; i
--) {
1240 /* -1, not -2; the 0 entry saves this */
1241 model
->syms
[i
].cumfreq
>>= 1;
1242 if (model
->syms
[i
].cumfreq
<= model
->syms
[i
+1].cumfreq
) {
1243 model
->syms
[i
].cumfreq
= model
->syms
[i
+1].cumfreq
+ 1;
1248 model
->shiftsleft
= 50;
1249 for (i
= 0; i
< model
->entries
; i
++) {
1250 /* no -1, want to include the 0 entry */
1251 /* this converts cumfreqs into frequencies, then shifts right */
1252 model
->syms
[i
].cumfreq
-= model
->syms
[i
+1].cumfreq
;
1253 model
->syms
[i
].cumfreq
++; /* avoid losing things entirely */
1254 model
->syms
[i
].cumfreq
>>= 1;
1257 /* now sort by frequencies, decreasing order -- this must be an
1258 * inplace selection sort, or a sort with the same (in)stability
1261 for (i
= 0; i
< model
->entries
- 1; i
++) {
1262 for (j
= i
+ 1; j
< model
->entries
; j
++) {
1263 if (model
->syms
[i
].cumfreq
< model
->syms
[j
].cumfreq
) {
1264 temp
= model
->syms
[i
];
1265 model
->syms
[i
] = model
->syms
[j
];
1266 model
->syms
[j
] = temp
;
1271 /* then convert frequencies back to cumfreq */
1272 for (i
= model
->entries
- 1; i
>= 0; i
--) {
1273 model
->syms
[i
].cumfreq
+= model
->syms
[i
+1].cumfreq
;
1275 /* then update the other part of the table */
1276 for (i
= 0; i
< model
->entries
; i
++) {
1277 model
->tabloc
[model
->syms
[i
].sym
] = i
;
1283 /* Bitstream reading macros (Quantum / normal byte order)
1285 * Q_INIT_BITSTREAM should be used first to set up the system
1286 * Q_READ_BITS(var,n) takes N bits from the buffer and puts them in var.
1287 * unlike LZX, this can loop several times to get the
1288 * requisite number of bits.
1289 * Q_FILL_BUFFER adds more data to the bit buffer, if there is room
1290 * for another 16 bits.
1291 * Q_PEEK_BITS(n) extracts (without removing) N bits from the bit
1293 * Q_REMOVE_BITS(n) removes N bits from the bit buffer
1295 * These bit access routines work by using the area beyond the MSB and the
1296 * LSB as a free source of zeroes. This avoids having to mask any bits.
1297 * So we have to know the bit width of the bitbuffer variable. This is
1298 * defined as ULONG_BITS.
1300 * ULONG_BITS should be at least 16 bits. Unlike LZX's Huffman decoding,
1301 * Quantum's arithmetic decoding only needs 1 bit at a time, it doesn't
1302 * need an assured number. Retrieving larger bitstrings can be done with
1303 * multiple reads and fills of the bitbuffer. The code should work fine
1304 * for machines where ULONG >= 32 bits.
1306 * Also note that Quantum reads bytes in normal order; LZX is in
1307 * little-endian order.
1310 #define Q_INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)
1312 #define Q_FILL_BUFFER do { \
1313 if (bitsleft <= (CAB_ULONG_BITS - 16)) { \
1314 bitbuf |= ((inpos[0]<<8)|inpos[1]) << (CAB_ULONG_BITS-16 - bitsleft); \
1315 bitsleft += 16; inpos += 2; \
1319 #define Q_PEEK_BITS(n) (bitbuf >> (CAB_ULONG_BITS - (n)))
1320 #define Q_REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))
1322 #define Q_READ_BITS(v,n) do { \
1324 for (bitsneed = (n); bitsneed; bitsneed -= bitrun) { \
1326 bitrun = (bitsneed > bitsleft) ? bitsleft : bitsneed; \
1327 (v) = ((v) << bitrun) | Q_PEEK_BITS(bitrun); \
1328 Q_REMOVE_BITS(bitrun); \
1332 #define Q_MENTRIES(model) (QTM(model).entries)
1333 #define Q_MSYM(model,symidx) (QTM(model).syms[(symidx)].sym)
1334 #define Q_MSYMFREQ(model,symidx) (QTM(model).syms[(symidx)].cumfreq)
1336 /* GET_SYMBOL(model, var) fetches the next symbol from the stated model
1337 * and puts it in var. it may need to read the bitstream to do this.
1339 #define GET_SYMBOL(m, var) do { \
1340 range = ((H - L) & 0xFFFF) + 1; \
1341 symf = ((((C - L + 1) * Q_MSYMFREQ(m,0)) - 1) / range) & 0xFFFF; \
1343 for (i=1; i < Q_MENTRIES(m); i++) { \
1344 if (Q_MSYMFREQ(m,i) <= symf) break; \
1346 (var) = Q_MSYM(m,i-1); \
1348 range = (H - L) + 1; \
1349 H = L + ((Q_MSYMFREQ(m,i-1) * range) / Q_MSYMFREQ(m,0)) - 1; \
1350 L = L + ((Q_MSYMFREQ(m,i) * range) / Q_MSYMFREQ(m,0)); \
1352 if ((L & 0x8000) != (H & 0x8000)) { \
1353 if ((L & 0x4000) && !(H & 0x4000)) { \
1354 /* underflow case */ \
1355 C ^= 0x4000; L &= 0x3FFF; H |= 0x4000; \
1359 L <<= 1; H = (H << 1) | 1; \
1361 C = (C << 1) | Q_PEEK_BITS(1); \
1365 QTMupdatemodel(&(QTM(m)), i); \
1368 /*******************************************************************
1369 * QTMdecompress (internal)
1371 int QTMdecompress(int inlen
, int outlen
)
1373 cab_UBYTE
*inpos
= CAB(inbuf
);
1374 cab_UBYTE
*window
= QTM(window
);
1375 cab_UBYTE
*runsrc
, *rundest
;
1377 cab_ULONG window_posn
= QTM(window_posn
);
1378 cab_ULONG window_size
= QTM(window_size
);
1380 /* used by bitstream macros */
1381 register int bitsleft
, bitrun
, bitsneed
;
1382 register cab_ULONG bitbuf
;
1384 /* used by GET_SYMBOL */
1389 int extra
, togo
= outlen
, match_length
= 0, copy_length
;
1390 cab_UBYTE selector
, sym
;
1391 cab_ULONG match_offset
= 0;
1393 cab_UWORD H
= 0xFFFF, L
= 0, C
;
1395 TRACE("(inlen == %d, outlen == %d)\n", inlen
, outlen
);
1397 /* read initial value of C */
1401 /* apply 2^x-1 mask */
1402 window_posn
&= window_size
- 1;
1403 /* runs can't straddle the window wraparound */
1404 if ((window_posn
+ togo
) > window_size
) {
1405 TRACE("straddled run\n");
1406 return DECR_DATAFORMAT
;
1410 GET_SYMBOL(model7
, selector
);
1413 GET_SYMBOL(model00
, sym
); window
[window_posn
++] = sym
; togo
--;
1416 GET_SYMBOL(model40
, sym
); window
[window_posn
++] = sym
; togo
--;
1419 GET_SYMBOL(model80
, sym
); window
[window_posn
++] = sym
; togo
--;
1422 GET_SYMBOL(modelC0
, sym
); window
[window_posn
++] = sym
; togo
--;
1426 /* selector 4 = fixed length of 3 */
1427 GET_SYMBOL(model4
, sym
);
1428 Q_READ_BITS(extra
, q_extra_bits
[sym
]);
1429 match_offset
= q_position_base
[sym
] + extra
+ 1;
1434 /* selector 5 = fixed length of 4 */
1435 GET_SYMBOL(model5
, sym
);
1436 Q_READ_BITS(extra
, q_extra_bits
[sym
]);
1437 match_offset
= q_position_base
[sym
] + extra
+ 1;
1442 /* selector 6 = variable length */
1443 GET_SYMBOL(model6len
, sym
);
1444 Q_READ_BITS(extra
, q_length_extra
[sym
]);
1445 match_length
= q_length_base
[sym
] + extra
+ 5;
1446 GET_SYMBOL(model6pos
, sym
);
1447 Q_READ_BITS(extra
, q_extra_bits
[sym
]);
1448 match_offset
= q_position_base
[sym
] + extra
+ 1;
1452 TRACE("Selector is bogus\n");
1453 return DECR_ILLEGALDATA
;
1456 /* if this is a match */
1457 if (selector
>= 4) {
1458 rundest
= window
+ window_posn
;
1459 togo
-= match_length
;
1461 /* copy any wrapped around source data */
1462 if (window_posn
>= match_offset
) {
1464 runsrc
= rundest
- match_offset
;
1466 runsrc
= rundest
+ (window_size
- match_offset
);
1467 copy_length
= match_offset
- window_posn
;
1468 if (copy_length
< match_length
) {
1469 match_length
-= copy_length
;
1470 window_posn
+= copy_length
;
1471 while (copy_length
-- > 0) *rundest
++ = *runsrc
++;
1475 window_posn
+= match_length
;
1477 /* copy match data - no worries about destination wraps */
1478 while (match_length
-- > 0) *rundest
++ = *runsrc
++;
1480 } /* while (togo > 0) */
1483 TRACE("Frame overflow, this_run = %d\n", togo
);
1484 return DECR_ILLEGALDATA
;
1487 memcpy(CAB(outbuf
), window
+ ((!window_posn
) ? window_size
: window_posn
) -
1490 QTM(window_posn
) = window_posn
;
1494 /* LZX decruncher */
1496 /* Microsoft's LZX document and their implementation of the
1497 * com.ms.util.cab Java package do not concur.
1499 * In the LZX document, there is a table showing the correlation between
1500 * window size and the number of position slots. It states that the 1MB
1501 * window = 40 slots and the 2MB window = 42 slots. In the implementation,
1502 * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
1503 * first slot whose position base is equal to or more than the required
1504 * window size'. This would explain why other tables in the document refer
1505 * to 50 slots rather than 42.
1507 * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
1508 * is not defined in the specification.
1510 * The LZX document does not state the uncompressed block has an
1511 * uncompressed length field. Where does this length field come from, so
1512 * we can know how large the block is? The implementation has it as the 24
1513 * bits following after the 3 blocktype bits, before the alignment
1516 * The LZX document states that aligned offset blocks have their aligned
1517 * offset huffman tree AFTER the main and length trees. The implementation
1518 * suggests that the aligned offset tree is BEFORE the main and length
1521 * The LZX document decoding algorithm states that, in an aligned offset
1522 * block, if an extra_bits value is 1, 2 or 3, then that number of bits
1523 * should be read and the result added to the match offset. This is
1524 * correct for 1 and 2, but not 3, where just a huffman symbol (using the
1525 * aligned tree) should be read.
1527 * Regarding the E8 preprocessing, the LZX document states 'No translation
1528 * may be performed on the last 6 bytes of the input block'. This is
1529 * correct. However, the pseudocode provided checks for the *E8 leader*
1530 * up to the last 6 bytes. If the leader appears between -10 and -7 bytes
1531 * from the end, this would cause the next four bytes to be modified, at
1532 * least one of which would be in the last 6 bytes, which is not allowed
1533 * according to the spec.
1535 * The specification states that the huffman trees must always contain at
1536 * least one element. However, many CAB files contain blocks where the
1537 * length tree is completely empty (because there are no matches), and
1538 * this is expected to succeed.
1542 /* LZX uses what it calls 'position slots' to represent match offsets.
1543 * What this means is that a small 'position slot' number and a small
1544 * offset from that slot are encoded instead of one large offset for
1546 * - lzx_position_base is an index to the position slot bases
1547 * - lzx_extra_bits states how many bits of offset-from-base data is needed.
1549 static cab_ULONG lzx_position_base
[51];
1550 static cab_UBYTE extra_bits
[51];
1552 /************************************************************
1553 * LZXinit (internal)
1555 int LZXinit(int window
) {
1556 cab_ULONG wndsize
= 1 << window
;
1557 int i
, j
, posn_slots
;
1559 /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
1560 /* if a previously allocated window is big enough, keep it */
1561 if (window
< 15 || window
> 21) return DECR_DATAFORMAT
;
1562 if (LZX(actual_size
) < wndsize
) {
1563 if (LZX(window
)) free(LZX(window
));
1567 if (!(LZX(window
) = malloc(wndsize
))) return DECR_NOMEMORY
;
1568 LZX(actual_size
) = wndsize
;
1570 LZX(window_size
) = wndsize
;
1572 /* initialise static tables */
1573 for (i
=0, j
=0; i
<= 50; i
+= 2) {
1574 extra_bits
[i
] = extra_bits
[i
+1] = j
; /* 0,0,0,0,1,1,2,2,3,3... */
1575 if ((i
!= 0) && (j
< 17)) j
++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */
1577 for (i
=0, j
=0; i
<= 50; i
++) {
1578 lzx_position_base
[i
] = j
; /* 0,1,2,3,4,6,8,12,16,24,32,... */
1579 j
+= 1 << extra_bits
[i
]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */
1582 /* calculate required position slots */
1583 if (window
== 20) posn_slots
= 42;
1584 else if (window
== 21) posn_slots
= 50;
1585 else posn_slots
= window
<< 1;
1587 /*posn_slots=i=0; while (i < wndsize) i += 1 << extra_bits[posn_slots++]; */
1589 LZX(R0
) = LZX(R1
) = LZX(R2
) = 1;
1590 LZX(main_elements
) = LZX_NUM_CHARS
+ (posn_slots
<< 3);
1591 LZX(header_read
) = 0;
1592 LZX(frames_read
) = 0;
1593 LZX(block_remaining
) = 0;
1594 LZX(block_type
) = LZX_BLOCKTYPE_INVALID
;
1595 LZX(intel_curpos
) = 0;
1596 LZX(intel_started
) = 0;
1597 LZX(window_posn
) = 0;
1599 /* initialise tables to 0 (because deltas will be applied to them) */
1600 for (i
= 0; i
< LZX_MAINTREE_MAXSYMBOLS
; i
++) LZX(MAINTREE_len
)[i
] = 0;
1601 for (i
= 0; i
< LZX_LENGTH_MAXSYMBOLS
; i
++) LZX(LENGTH_len
)[i
] = 0;
1606 /* Bitstream reading macros (LZX / intel little-endian byte order)
1608 * INIT_BITSTREAM should be used first to set up the system
1609 * READ_BITS(var,n) takes N bits from the buffer and puts them in var
1611 * ENSURE_BITS(n) ensures there are at least N bits in the bit buffer.
1612 * it can guarantee up to 17 bits (i.e. it can read in
1613 * 16 new bits when there is down to 1 bit in the buffer,
1614 * and it can read 32 bits when there are 0 bits in the
1616 * PEEK_BITS(n) extracts (without removing) N bits from the bit buffer
1617 * REMOVE_BITS(n) removes N bits from the bit buffer
1619 * These bit access routines work by using the area beyond the MSB and the
1620 * LSB as a free source of zeroes. This avoids having to mask any bits.
1621 * So we have to know the bit width of the bitbuffer variable.
1624 #define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)
1626 /* Quantum reads bytes in normal order; LZX is little-endian order */
1627 #define ENSURE_BITS(n) \
1628 while (bitsleft < (n)) { \
1629 bitbuf |= ((inpos[1]<<8)|inpos[0]) << (CAB_ULONG_BITS-16 - bitsleft); \
1630 bitsleft += 16; inpos+=2; \
1633 #define PEEK_BITS(n) (bitbuf >> (CAB_ULONG_BITS - (n)))
1634 #define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))
1636 #define READ_BITS(v,n) do { \
1639 (v) = PEEK_BITS(n); \
1647 /* Huffman macros */
1649 #define TABLEBITS(tbl) (LZX_##tbl##_TABLEBITS)
1650 #define MAXSYMBOLS(tbl) (LZX_##tbl##_MAXSYMBOLS)
1651 #define SYMTABLE(tbl) (LZX(tbl##_table))
1652 #define LENTABLE(tbl) (LZX(tbl##_len))
1654 /* BUILD_TABLE(tablename) builds a huffman lookup table from code lengths.
1655 * In reality, it just calls make_decode_table() with the appropriate
1656 * values - they're all fixed by some #defines anyway, so there's no point
1657 * writing each call out in full by hand.
1659 #define BUILD_TABLE(tbl) \
1660 if (make_decode_table( \
1661 MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl) \
1662 )) { return DECR_ILLEGALDATA; }
1664 /* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the
1665 * bitstream using the stated table and puts it in var.
1667 #define READ_HUFFSYM(tbl,var) do { \
1669 hufftbl = SYMTABLE(tbl); \
1670 if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) { \
1671 j = 1 << (CAB_ULONG_BITS - TABLEBITS(tbl)); \
1673 j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0; \
1674 if (!j) { return DECR_ILLEGALDATA; } \
1675 } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl)); \
1677 j = LENTABLE(tbl)[(var) = i]; \
1681 /* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
1682 * first to last in the given table. The code lengths are stored in their
1683 * own special LZX way.
1685 #define READ_LENGTHS(tbl,first,last) do { \
1686 lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \
1687 if (lzx_read_lens(LENTABLE(tbl),(first),(last),&lb)) { \
1688 return DECR_ILLEGALDATA; \
1690 bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \
1693 /*************************************************************************
1694 * make_decode_table (internal)
1696 * This function was coded by David Tritscher. It builds a fast huffman
1697 * decoding table out of just a canonical huffman code lengths table.
1700 * nsyms: total number of symbols in this huffman tree.
1701 * nbits: any symbols with a code length of nbits or less can be decoded
1702 * in one lookup of the table.
1703 * length: A table to get code lengths from [0 to syms-1]
1704 * table: The table to fill up with decoded symbols and pointers.
1710 int make_decode_table(cab_ULONG nsyms
, cab_ULONG nbits
, cab_UBYTE
*length
, cab_UWORD
*table
) {
1711 register cab_UWORD sym
;
1712 register cab_ULONG leaf
;
1713 register cab_UBYTE bit_num
= 1;
1715 cab_ULONG pos
= 0; /* the current position in the decode table */
1716 cab_ULONG table_mask
= 1 << nbits
;
1717 cab_ULONG bit_mask
= table_mask
>> 1; /* don't do 0 length codes */
1718 cab_ULONG next_symbol
= bit_mask
; /* base of allocation for long codes */
1720 /* fill entries for codes short enough for a direct mapping */
1721 while (bit_num
<= nbits
) {
1722 for (sym
= 0; sym
< nsyms
; sym
++) {
1723 if (length
[sym
] == bit_num
) {
1726 if((pos
+= bit_mask
) > table_mask
) return 1; /* table overrun */
1728 /* fill all possible lookups of this symbol with the symbol itself */
1730 while (fill
-- > 0) table
[leaf
++] = sym
;
1737 /* if there are any codes longer than nbits */
1738 if (pos
!= table_mask
) {
1739 /* clear the remainder of the table */
1740 for (sym
= pos
; sym
< table_mask
; sym
++) table
[sym
] = 0;
1742 /* give ourselves room for codes to grow by up to 16 more bits */
1747 while (bit_num
<= 16) {
1748 for (sym
= 0; sym
< nsyms
; sym
++) {
1749 if (length
[sym
] == bit_num
) {
1751 for (fill
= 0; fill
< bit_num
- nbits
; fill
++) {
1752 /* if this path hasn't been taken yet, 'allocate' two entries */
1753 if (table
[leaf
] == 0) {
1754 table
[(next_symbol
<< 1)] = 0;
1755 table
[(next_symbol
<< 1) + 1] = 0;
1756 table
[leaf
] = next_symbol
++;
1758 /* follow the path and select either left or right for next bit */
1759 leaf
= table
[leaf
] << 1;
1760 if ((pos
>> (15-fill
)) & 1) leaf
++;
1764 if ((pos
+= bit_mask
) > table_mask
) return 1; /* table overflow */
1773 if (pos
== table_mask
) return 0;
1775 /* either erroneous table, or all elements are 0 - let's find out. */
1776 for (sym
= 0; sym
< nsyms
; sym
++) if (length
[sym
]) return 1;
1786 /************************************************************
1787 * lzx_read_lens (internal)
1789 int lzx_read_lens(cab_UBYTE
*lens
, cab_ULONG first
, cab_ULONG last
, struct lzx_bits
*lb
) {
1793 register cab_ULONG bitbuf
= lb
->bb
;
1794 register int bitsleft
= lb
->bl
;
1795 cab_UBYTE
*inpos
= lb
->ip
;
1798 for (x
= 0; x
< 20; x
++) {
1800 LENTABLE(PRETREE
)[x
] = y
;
1802 BUILD_TABLE(PRETREE
);
1804 for (x
= first
; x
< last
; ) {
1805 READ_HUFFSYM(PRETREE
, z
);
1807 READ_BITS(y
, 4); y
+= 4;
1808 while (y
--) lens
[x
++] = 0;
1811 READ_BITS(y
, 5); y
+= 20;
1812 while (y
--) lens
[x
++] = 0;
1815 READ_BITS(y
, 1); y
+= 4;
1816 READ_HUFFSYM(PRETREE
, z
);
1817 z
= lens
[x
] - z
; if (z
< 0) z
+= 17;
1818 while (y
--) lens
[x
++] = z
;
1821 z
= lens
[x
] - z
; if (z
< 0) z
+= 17;
1832 /*******************************************************
1833 * LZXdecompress (internal)
1835 int LZXdecompress(int inlen
, int outlen
) {
1836 cab_UBYTE
*inpos
= CAB(inbuf
);
1837 cab_UBYTE
*endinp
= inpos
+ inlen
;
1838 cab_UBYTE
*window
= LZX(window
);
1839 cab_UBYTE
*runsrc
, *rundest
;
1840 cab_UWORD
*hufftbl
; /* used in READ_HUFFSYM macro as chosen decoding table */
1842 cab_ULONG window_posn
= LZX(window_posn
);
1843 cab_ULONG window_size
= LZX(window_size
);
1844 cab_ULONG R0
= LZX(R0
);
1845 cab_ULONG R1
= LZX(R1
);
1846 cab_ULONG R2
= LZX(R2
);
1848 register cab_ULONG bitbuf
;
1849 register int bitsleft
;
1850 cab_ULONG match_offset
, i
,j
,k
; /* ijk used in READ_HUFFSYM macro */
1851 struct lzx_bits lb
; /* used in READ_LENGTHS macro */
1853 int togo
= outlen
, this_run
, main_element
, aligned_bits
;
1854 int match_length
, copy_length
, length_footer
, extra
, verbatim_bits
;
1856 TRACE("(inlen == %d, outlen == %d)\n", inlen
, outlen
);
1860 /* read header if necessary */
1861 if (!LZX(header_read
)) {
1863 READ_BITS(k
, 1); if (k
) { READ_BITS(i
,16); READ_BITS(j
,16); }
1864 LZX(intel_filesize
) = (i
<< 16) | j
; /* or 0 if not encoded */
1865 LZX(header_read
) = 1;
1868 /* main decoding loop */
1870 /* last block finished, new block expected */
1871 if (LZX(block_remaining
) == 0) {
1872 if (LZX(block_type
) == LZX_BLOCKTYPE_UNCOMPRESSED
) {
1873 if (LZX(block_length
) & 1) inpos
++; /* realign bitstream to word */
1877 READ_BITS(LZX(block_type
), 3);
1880 LZX(block_remaining
) = LZX(block_length
) = (i
<< 8) | j
;
1882 switch (LZX(block_type
)) {
1883 case LZX_BLOCKTYPE_ALIGNED
:
1884 for (i
= 0; i
< 8; i
++) { READ_BITS(j
, 3); LENTABLE(ALIGNED
)[i
] = j
; }
1885 BUILD_TABLE(ALIGNED
);
1886 /* rest of aligned header is same as verbatim */
1888 case LZX_BLOCKTYPE_VERBATIM
:
1889 READ_LENGTHS(MAINTREE
, 0, 256);
1890 READ_LENGTHS(MAINTREE
, 256, LZX(main_elements
));
1891 BUILD_TABLE(MAINTREE
);
1892 if (LENTABLE(MAINTREE
)[0xE8] != 0) LZX(intel_started
) = 1;
1894 READ_LENGTHS(LENGTH
, 0, LZX_NUM_SECONDARY_LENGTHS
);
1895 BUILD_TABLE(LENGTH
);
1898 case LZX_BLOCKTYPE_UNCOMPRESSED
:
1899 LZX(intel_started
) = 1; /* because we can't assume otherwise */
1900 ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
1901 if (bitsleft
> 16) inpos
-= 2; /* and align the bitstream! */
1902 R0
= inpos
[0]|(inpos
[1]<<8)|(inpos
[2]<<16)|(inpos
[3]<<24);inpos
+=4;
1903 R1
= inpos
[0]|(inpos
[1]<<8)|(inpos
[2]<<16)|(inpos
[3]<<24);inpos
+=4;
1904 R2
= inpos
[0]|(inpos
[1]<<8)|(inpos
[2]<<16)|(inpos
[3]<<24);inpos
+=4;
1908 return DECR_ILLEGALDATA
;
1912 /* buffer exhaustion check */
1913 if (inpos
> endinp
) {
1914 /* it's possible to have a file where the next run is less than
1915 * 16 bits in size. In this case, the READ_HUFFSYM() macro used
1916 * in building the tables will exhaust the buffer, so we should
1917 * allow for this, but not allow those accidentally read bits to
1918 * be used (so we check that there are at least 16 bits
1919 * remaining - in this boundary case they aren't really part of
1920 * the compressed data)
1922 if (inpos
> (endinp
+2) || bitsleft
< 16) return DECR_ILLEGALDATA
;
1925 while ((this_run
= LZX(block_remaining
)) > 0 && togo
> 0) {
1926 if (this_run
> togo
) this_run
= togo
;
1928 LZX(block_remaining
) -= this_run
;
1930 /* apply 2^x-1 mask */
1931 window_posn
&= window_size
- 1;
1932 /* runs can't straddle the window wraparound */
1933 if ((window_posn
+ this_run
) > window_size
)
1934 return DECR_DATAFORMAT
;
1936 switch (LZX(block_type
)) {
1938 case LZX_BLOCKTYPE_VERBATIM
:
1939 while (this_run
> 0) {
1940 READ_HUFFSYM(MAINTREE
, main_element
);
1942 if (main_element
< LZX_NUM_CHARS
) {
1943 /* literal: 0 to LZX_NUM_CHARS-1 */
1944 window
[window_posn
++] = main_element
;
1948 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
1949 main_element
-= LZX_NUM_CHARS
;
1951 match_length
= main_element
& LZX_NUM_PRIMARY_LENGTHS
;
1952 if (match_length
== LZX_NUM_PRIMARY_LENGTHS
) {
1953 READ_HUFFSYM(LENGTH
, length_footer
);
1954 match_length
+= length_footer
;
1956 match_length
+= LZX_MIN_MATCH
;
1958 match_offset
= main_element
>> 3;
1960 if (match_offset
> 2) {
1961 /* not repeated offset */
1962 if (match_offset
!= 3) {
1963 extra
= extra_bits
[match_offset
];
1964 READ_BITS(verbatim_bits
, extra
);
1965 match_offset
= lzx_position_base
[match_offset
]
1966 - 2 + verbatim_bits
;
1972 /* update repeated offset LRU queue */
1973 R2
= R1
; R1
= R0
; R0
= match_offset
;
1975 else if (match_offset
== 0) {
1978 else if (match_offset
== 1) {
1980 R1
= R0
; R0
= match_offset
;
1982 else /* match_offset == 2 */ {
1984 R2
= R0
; R0
= match_offset
;
1987 rundest
= window
+ window_posn
;
1988 this_run
-= match_length
;
1990 /* copy any wrapped around source data */
1991 if (window_posn
>= match_offset
) {
1993 runsrc
= rundest
- match_offset
;
1995 runsrc
= rundest
+ (window_size
- match_offset
);
1996 copy_length
= match_offset
- window_posn
;
1997 if (copy_length
< match_length
) {
1998 match_length
-= copy_length
;
1999 window_posn
+= copy_length
;
2000 while (copy_length
-- > 0) *rundest
++ = *runsrc
++;
2004 window_posn
+= match_length
;
2006 /* copy match data - no worries about destination wraps */
2007 while (match_length
-- > 0) *rundest
++ = *runsrc
++;
2012 case LZX_BLOCKTYPE_ALIGNED
:
2013 while (this_run
> 0) {
2014 READ_HUFFSYM(MAINTREE
, main_element
);
2016 if (main_element
< LZX_NUM_CHARS
) {
2017 /* literal: 0 to LZX_NUM_CHARS-1 */
2018 window
[window_posn
++] = main_element
;
2022 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
2023 main_element
-= LZX_NUM_CHARS
;
2025 match_length
= main_element
& LZX_NUM_PRIMARY_LENGTHS
;
2026 if (match_length
== LZX_NUM_PRIMARY_LENGTHS
) {
2027 READ_HUFFSYM(LENGTH
, length_footer
);
2028 match_length
+= length_footer
;
2030 match_length
+= LZX_MIN_MATCH
;
2032 match_offset
= main_element
>> 3;
2034 if (match_offset
> 2) {
2035 /* not repeated offset */
2036 extra
= extra_bits
[match_offset
];
2037 match_offset
= lzx_position_base
[match_offset
] - 2;
2039 /* verbatim and aligned bits */
2041 READ_BITS(verbatim_bits
, extra
);
2042 match_offset
+= (verbatim_bits
<< 3);
2043 READ_HUFFSYM(ALIGNED
, aligned_bits
);
2044 match_offset
+= aligned_bits
;
2046 else if (extra
== 3) {
2047 /* aligned bits only */
2048 READ_HUFFSYM(ALIGNED
, aligned_bits
);
2049 match_offset
+= aligned_bits
;
2051 else if (extra
> 0) { /* extra==1, extra==2 */
2052 /* verbatim bits only */
2053 READ_BITS(verbatim_bits
, extra
);
2054 match_offset
+= verbatim_bits
;
2056 else /* extra == 0 */ {
2061 /* update repeated offset LRU queue */
2062 R2
= R1
; R1
= R0
; R0
= match_offset
;
2064 else if (match_offset
== 0) {
2067 else if (match_offset
== 1) {
2069 R1
= R0
; R0
= match_offset
;
2071 else /* match_offset == 2 */ {
2073 R2
= R0
; R0
= match_offset
;
2076 rundest
= window
+ window_posn
;
2077 this_run
-= match_length
;
2079 /* copy any wrapped around source data */
2080 if (window_posn
>= match_offset
) {
2082 runsrc
= rundest
- match_offset
;
2084 runsrc
= rundest
+ (window_size
- match_offset
);
2085 copy_length
= match_offset
- window_posn
;
2086 if (copy_length
< match_length
) {
2087 match_length
-= copy_length
;
2088 window_posn
+= copy_length
;
2089 while (copy_length
-- > 0) *rundest
++ = *runsrc
++;
2093 window_posn
+= match_length
;
2095 /* copy match data - no worries about destination wraps */
2096 while (match_length
-- > 0) *rundest
++ = *runsrc
++;
2101 case LZX_BLOCKTYPE_UNCOMPRESSED
:
2102 if ((inpos
+ this_run
) > endinp
) return DECR_ILLEGALDATA
;
2103 memcpy(window
+ window_posn
, inpos
, (size_t) this_run
);
2104 inpos
+= this_run
; window_posn
+= this_run
;
2108 return DECR_ILLEGALDATA
; /* might as well */
2114 if (togo
!= 0) return DECR_ILLEGALDATA
;
2115 memcpy(CAB(outbuf
), window
+ ((!window_posn
) ? window_size
: window_posn
) -
2116 outlen
, (size_t) outlen
);
2118 LZX(window_posn
) = window_posn
;
2123 /* intel E8 decoding */
2124 if ((LZX(frames_read
)++ < 32768) && LZX(intel_filesize
) != 0) {
2125 if (outlen
<= 6 || !LZX(intel_started
)) {
2126 LZX(intel_curpos
) += outlen
;
2129 cab_UBYTE
*data
= CAB(outbuf
);
2130 cab_UBYTE
*dataend
= data
+ outlen
- 10;
2131 cab_LONG curpos
= LZX(intel_curpos
);
2132 cab_LONG filesize
= LZX(intel_filesize
);
2133 cab_LONG abs_off
, rel_off
;
2135 LZX(intel_curpos
) = curpos
+ outlen
;
2137 while (data
< dataend
) {
2138 if (*data
++ != 0xE8) { curpos
++; continue; }
2139 abs_off
= data
[0] | (data
[1]<<8) | (data
[2]<<16) | (data
[3]<<24);
2140 if ((abs_off
>= -curpos
) && (abs_off
< filesize
)) {
2141 rel_off
= (abs_off
>= 0) ? abs_off
- curpos
: abs_off
+ filesize
;
2142 data
[0] = (cab_UBYTE
) rel_off
;
2143 data
[1] = (cab_UBYTE
) (rel_off
>> 8);
2144 data
[2] = (cab_UBYTE
) (rel_off
>> 16);
2145 data
[3] = (cab_UBYTE
) (rel_off
>> 24);
2155 /*********************************************************
2156 * find_cabs_in_file (internal)
2158 struct cabinet
*find_cabs_in_file(LPCSTR name
)
2160 struct cabinet
*cab
, *cab2
, *firstcab
= NULL
, *linkcab
= NULL
;
2161 cab_UBYTE
*pstart
= &search_buf
[0], *pend
, *p
;
2162 cab_off_t offset
, caboff
, cablen
= 0, foffset
= 0, filelen
, length
;
2163 int state
= 0, found
= 0, ok
= 0;
2165 TRACE("(name == %s)\n", debugstr_a((char *) name
));
2167 /* open the file and search for cabinet headers */
2168 if ((cab
= (struct cabinet
*) calloc(1, sizeof(struct cabinet
)))) {
2169 cab
->filename
= name
;
2170 if (cabinet_open(cab
)) {
2171 filelen
= cab
->filelen
;
2172 for (offset
= 0; (offset
< filelen
); offset
+= length
) {
2173 /* search length is either the full length of the search buffer,
2174 * or the amount of data remaining to the end of the file,
2175 * whichever is less.
2177 length
= filelen
- offset
;
2178 if (length
> CAB_SEARCH_SIZE
) length
= CAB_SEARCH_SIZE
;
2180 /* fill the search buffer with data from disk */
2181 if (!cabinet_read(cab
, search_buf
, length
)) break;
2183 /* read through the entire buffer. */
2185 pend
= &search_buf
[length
];
2188 /* starting state */
2190 /* we spend most of our time in this while loop, looking for
2191 * a leading 'M' of the 'MSCF' signature
2193 while (*p
++ != 0x4D && p
< pend
);
2194 if (p
< pend
) state
= 1; /* if we found tht 'M', advance state */
2197 /* verify that the next 3 bytes are 'S', 'C' and 'F' */
2198 case 1: state
= (*p
++ == 0x53) ? 2 : 0; break;
2199 case 2: state
= (*p
++ == 0x43) ? 3 : 0; break;
2200 case 3: state
= (*p
++ == 0x46) ? 4 : 0; break;
2202 /* we don't care about bytes 4-7 */
2203 /* bytes 8-11 are the overall length of the cabinet */
2204 case 8: cablen
= *p
++; state
++; break;
2205 case 9: cablen
|= *p
++ << 8; state
++; break;
2206 case 10: cablen
|= *p
++ << 16; state
++; break;
2207 case 11: cablen
|= *p
++ << 24; state
++; break;
2209 /* we don't care about bytes 12-15 */
2210 /* bytes 16-19 are the offset within the cabinet of the filedata */
2211 case 16: foffset
= *p
++; state
++; break;
2212 case 17: foffset
|= *p
++ << 8; state
++; break;
2213 case 18: foffset
|= *p
++ << 16; state
++; break;
2214 case 19: foffset
|= *p
++ << 24;
2215 /* now we have recieved 20 bytes of potential cab header. */
2216 /* work out the offset in the file of this potential cabinet */
2217 caboff
= offset
+ (p
-pstart
) - 20;
2219 /* check that the files offset is less than the alleged length
2220 * of the cabinet, and that the offset + the alleged length are
2221 * 'roughly' within the end of overall file length
2223 if ((foffset
< cablen
) &&
2224 ((caboff
+ foffset
) < (filelen
+ 32)) &&
2225 ((caboff
+ cablen
) < (filelen
+ 32)) )
2227 /* found a potential result - try loading it */
2229 cab2
= load_cab_offset(name
, caboff
);
2234 /* cause the search to restart after this cab's data. */
2235 offset
= caboff
+ cablen
;
2236 if (offset
< cab
->filelen
) cabinet_seek(cab
, offset
);
2240 /* link the cab into the list */
2241 if (linkcab
== NULL
) firstcab
= cab2
;
2242 else linkcab
->next
= cab2
;
2249 p
++, state
++; break;
2258 /* if there were cabinets that were found but are not ok, point this out */
2260 WARN("%s: found %d bad cabinets\n", debugstr_a(name
), found
-ok
);
2263 /* if no cabinets were found, let the user know */
2265 WARN("%s: not a Microsoft cabinet file.\n", debugstr_a(name
));
2270 /***********************************************************************
2271 * find_cabinet_file (internal)
2273 * tries to find *cabname, from the directory path of origcab, correcting the
2274 * case of *cabname if necessary, If found, writes back to *cabname.
2276 void find_cabinet_file(char **cabname
, LPCSTR origcab
) {
2278 char *tail
, *cab
, *name
, *nextpart
, nametmp
[MAX_PATH
], *filepart
;
2281 TRACE("(*cabname == ^%p, origcab == %s)\n", cabname
? *cabname
: NULL
, debugstr_a(origcab
));
2283 /* ensure we have a cabinet name at all */
2284 if (!(name
= *cabname
)) {
2285 WARN("no cabinet name at all\n");
2288 /* find if there's a directory path in the origcab */
2289 tail
= origcab
? max(strrchr(origcab
, '/'), strrchr(origcab
, '\\')) : NULL
;
2291 if ((cab
= (char *) malloc(MAX_PATH
))) {
2292 /* add the directory path from the original cabinet name */
2294 memcpy(cab
, origcab
, tail
- origcab
);
2295 cab
[tail
- origcab
] = '\0';
2297 /* default directory path of '.' */
2303 TRACE("trying cab == %s", debugstr_a(cab
));
2305 /* we don't want null cabinet filenames */
2306 if (name
[0] == '\0') {
2307 WARN("null cab name\n");
2311 /* if there is a directory component in the cabinet name,
2312 * look for that alone first
2314 nextpart
= strchr(name
, '\\');
2315 if (nextpart
) *nextpart
= '\0';
2317 found
= SearchPathA(cab
, name
, NULL
, MAX_PATH
, nametmp
, &filepart
);
2319 /* if the component was not found, look for it in the current dir */
2321 found
= SearchPathA(".", name
, NULL
, MAX_PATH
, nametmp
, &filepart
);
2325 TRACE("found: %s\n", debugstr_a(nametmp
));
2327 TRACE("not found.\n");
2329 /* restore the real name and skip to the next directory component
2330 * or actual cabinet name
2332 if (nextpart
) *nextpart
= '\\', name
= &nextpart
[1];
2334 /* while there is another directory component, and while we
2335 * successfully found the current component
2337 } while (nextpart
&& found
);
2339 /* if we found the cabinet, change the next cabinet's name.
2340 * otherwise, pretend nothing happened
2343 free((void *) *cabname
);
2345 strncpy(cab
, nametmp
, found
+1);
2346 TRACE("result: %s\n", debugstr_a(cab
));
2349 TRACE("result: nothing\n");
2354 /************************************************************************
2355 * process_files (internal)
2357 * this does the tricky job of running through every file in the cabinet,
2358 * including spanning cabinets, and working out which file is in which
2359 * folder in which cabinet. It also throws out the duplicate file entries
2360 * that appear in spanning cabinets. There is memory leakage here because
2361 * those entries are not freed. See the XAD CAB client for an
2362 * implementation of this that correctly frees the discarded file entries.
2364 struct cab_file
*process_files(struct cabinet
*basecab
) {
2365 struct cabinet
*cab
;
2366 struct cab_file
*outfi
= NULL
, *linkfi
= NULL
, *nextfi
, *fi
, *cfi
;
2367 struct cab_folder
*fol
, *firstfol
, *lastfol
= NULL
, *predfol
;
2370 FIXME("(basecab == ^%p): Memory leak.\n", basecab
);
2372 for (cab
= basecab
; cab
; cab
= cab
->nextcab
) {
2373 /* firstfol = first folder in this cabinet */
2374 /* lastfol = last folder in this cabinet */
2375 /* predfol = last folder in previous cabinet (or NULL if first cabinet) */
2377 firstfol
= cab
->folders
;
2378 for (lastfol
= firstfol
; lastfol
->next
;) lastfol
= lastfol
->next
;
2381 for (fi
= cab
->files
; fi
; fi
= nextfi
) {
2385 if (i
< cffileCONTINUED_FROM_PREV
) {
2386 for (fol
= firstfol
; fol
&& i
--; ) fol
= fol
->next
;
2387 fi
->folder
= fol
; /* NULL if an invalid folder index */
2390 /* folder merging */
2391 if (i
== cffileCONTINUED_TO_NEXT
2392 || i
== cffileCONTINUED_PREV_AND_NEXT
) {
2393 if (cab
->nextcab
&& !lastfol
->contfile
) lastfol
->contfile
= fi
;
2396 if (i
== cffileCONTINUED_FROM_PREV
2397 || i
== cffileCONTINUED_PREV_AND_NEXT
) {
2398 /* these files are to be continued in yet another
2399 * cabinet, don't merge them in just yet */
2400 if (i
== cffileCONTINUED_PREV_AND_NEXT
) mergeok
= 0;
2402 /* only merge once per cabinet */
2404 if ((cfi
= predfol
->contfile
)
2405 && (cfi
->offset
== fi
->offset
)
2406 && (cfi
->length
== fi
->length
)
2407 && (strcmp(cfi
->filename
, fi
->filename
) == 0)
2408 && (predfol
->comp_type
== firstfol
->comp_type
)) {
2409 /* increase the number of splits */
2410 if ((i
= ++(predfol
->num_splits
)) > CAB_SPLITMAX
) {
2412 ERR("%s: internal error, increase CAB_SPLITMAX\n", debugstr_a(basecab
->filename
));
2415 /* copy information across from the merged folder */
2416 predfol
->offset
[i
] = firstfol
->offset
[0];
2417 predfol
->cab
[i
] = firstfol
->cab
[0];
2418 predfol
->next
= firstfol
->next
;
2419 predfol
->contfile
= firstfol
->contfile
;
2421 if (firstfol
== lastfol
) lastfol
= predfol
;
2423 predfol
= NULL
; /* don't merge again within this cabinet */
2427 /* if the folders won't merge, don't add their files */
2432 if (mergeok
) fi
->folder
= firstfol
;
2437 if (linkfi
) linkfi
->next
= fi
; else outfi
= fi
;
2441 } /* for (cab= ...*/
2446 /****************************************************************
2447 * convertUTF (internal)
2449 * translate UTF -> ASCII
2451 * UTF translates two-byte unicode characters into 1, 2 or 3 bytes.
2452 * %000000000xxxxxxx -> %0xxxxxxx
2453 * %00000xxxxxyyyyyy -> %110xxxxx %10yyyyyy
2454 * %xxxxyyyyyyzzzzzz -> %1110xxxx %10yyyyyy %10zzzzzz
2456 * Therefore, the inverse is as follows:
2458 * 0x00 - 0x7F = one byte char
2459 * 0x80 - 0xBF = invalid
2460 * 0xC0 - 0xDF = 2 byte char (next char only 0x80-0xBF is valid)
2461 * 0xE0 - 0xEF = 3 byte char (next 2 chars only 0x80-0xBF is valid)
2462 * 0xF0 - 0xFF = invalid
2464 * FIXME: use a winapi to do this
2466 int convertUTF(cab_UBYTE
*in
) {
2467 cab_UBYTE c
, *out
= in
, *end
= in
+ strlen((char *) in
) + 1;
2471 /* read unicode character */
2472 if ((c
= *in
++) < 0x80) x
= c
;
2474 if (c
< 0xC0) return 0;
2475 else if (c
< 0xE0) {
2476 x
= (c
& 0x1F) << 6;
2477 if ((c
= *in
++) < 0x80 || c
> 0xBF) return 0; else x
|= (c
& 0x3F);
2479 else if (c
< 0xF0) {
2480 x
= (c
& 0xF) << 12;
2481 if ((c
= *in
++) < 0x80 || c
> 0xBF) return 0; else x
|= (c
& 0x3F)<<6;
2482 if ((c
= *in
++) < 0x80 || c
> 0xBF) return 0; else x
|= (c
& 0x3F);
2487 /* terrible unicode -> ASCII conversion */
2488 if (x
> 127) x
= '_';
2490 if (in
> end
) return 0; /* just in case */
2491 } while ((*out
++ = (cab_UBYTE
) x
));
2495 /****************************************************
2496 * NONEdecompress (internal)
2498 int NONEdecompress(int inlen
, int outlen
)
2500 if (inlen
!= outlen
) return DECR_ILLEGALDATA
;
2501 memcpy(CAB(outbuf
), CAB(inbuf
), (size_t) inlen
);
2505 /**************************************************
2506 * checksum (internal)
2508 cab_ULONG
checksum(cab_UBYTE
*data
, cab_UWORD bytes
, cab_ULONG csum
) {
2512 for (len
= bytes
>> 2; len
--; data
+= 4) {
2513 csum
^= ((data
[0]) | (data
[1]<<8) | (data
[2]<<16) | (data
[3]<<24));
2516 switch (bytes
& 3) {
2517 case 3: ul
|= *data
++ << 16;
2518 case 2: ul
|= *data
++ << 8;
2519 case 1: ul
|= *data
;
2526 /**********************************************************
2527 * decompress (internal)
2529 int decompress(struct cab_file
*fi
, int savemode
, int fix
)
2531 cab_ULONG bytes
= savemode
? fi
->length
: fi
->offset
- CAB(offset
);
2532 struct cabinet
*cab
= CAB(current
)->cab
[CAB(split
)];
2533 cab_UBYTE buf
[cfdata_SIZEOF
], *data
;
2534 cab_UWORD inlen
, len
, outlen
, cando
;
2538 TRACE("(fi == ^%p, savemode == %d, fix == %d)\n", fi
, savemode
, fix
);
2541 /* cando = the max number of bytes we can do */
2542 cando
= CAB(outlen
);
2543 if (cando
> bytes
) cando
= bytes
;
2546 if (cando
&& savemode
)
2547 file_write(fi
, CAB(outpos
), cando
);
2549 CAB(outpos
) += cando
;
2550 CAB(outlen
) -= cando
;
2551 bytes
-= cando
; if (!bytes
) break;
2553 /* we only get here if we emptied the output buffer */
2555 /* read data header + data */
2557 while (outlen
== 0) {
2558 /* read the block header, skip the reserved part */
2559 if (!cabinet_read(cab
, buf
, cfdata_SIZEOF
)) return DECR_INPUT
;
2560 cabinet_skip(cab
, cab
->block_resv
);
2562 /* we shouldn't get blocks over CAB_INPUTMAX in size */
2563 data
= CAB(inbuf
) + inlen
;
2564 len
= EndGetI16(buf
+cfdata_CompressedSize
);
2566 if (inlen
> CAB_INPUTMAX
) return DECR_INPUT
;
2567 if (!cabinet_read(cab
, data
, len
)) return DECR_INPUT
;
2569 /* clear two bytes after read-in data */
2570 data
[len
+1] = data
[len
+2] = 0;
2572 /* perform checksum test on the block (if one is stored) */
2573 cksum
= EndGetI32(buf
+cfdata_CheckSum
);
2574 if (cksum
&& cksum
!= checksum(buf
+4, 4, checksum(data
, len
, 0))) {
2575 /* checksum is wrong */
2576 if (fix
&& ((fi
->folder
->comp_type
& cffoldCOMPTYPE_MASK
)
2577 == cffoldCOMPTYPE_MSZIP
))
2579 WARN("%s: checksum failed\n", debugstr_a(fi
->filename
));
2582 return DECR_CHECKSUM
;
2586 /* outlen=0 means this block was part of a split block */
2587 outlen
= EndGetI16(buf
+cfdata_UncompressedSize
);
2590 cab
= CAB(current
)->cab
[++CAB(split
)];
2591 if (!cabinet_open(cab
)) return DECR_INPUT
;
2592 cabinet_seek(cab
, CAB(current
)->offset
[CAB(split
)]);
2596 /* decompress block */
2597 if ((err
= CAB(decompress
)(inlen
, outlen
))) {
2598 if (fix
&& ((fi
->folder
->comp_type
& cffoldCOMPTYPE_MASK
)
2599 == cffoldCOMPTYPE_MSZIP
))
2601 ERR("%s: failed decrunching block\n", debugstr_a(fi
->filename
));
2607 CAB(outlen
) = outlen
;
2608 CAB(outpos
) = CAB(outbuf
);
2614 /****************************************************************
2615 * extract_file (internal)
2617 * workhorse to extract a particular file from a cab
2619 void extract_file(struct cab_file
*fi
, int lower
, int fix
, LPCSTR dir
)
2621 struct cab_folder
*fol
= fi
->folder
, *oldfol
= CAB(current
);
2622 cab_LONG err
= DECR_OK
;
2624 TRACE("(fi == ^%p, lower == %d, fix == %d, dir == %s)\n", fi
, lower
, fix
, debugstr_a(dir
));
2626 /* is a change of folder needed? do we need to reset the current folder? */
2627 if (fol
!= oldfol
|| fi
->offset
< CAB(offset
)) {
2628 cab_UWORD comptype
= fol
->comp_type
;
2629 int ct1
= comptype
& cffoldCOMPTYPE_MASK
;
2630 int ct2
= oldfol
? (oldfol
->comp_type
& cffoldCOMPTYPE_MASK
) : 0;
2632 /* if the archiver has changed, call the old archiver's free() function */
2635 case cffoldCOMPTYPE_LZX
:
2641 case cffoldCOMPTYPE_QUANTUM
:
2651 case cffoldCOMPTYPE_NONE
:
2652 CAB(decompress
) = NONEdecompress
;
2655 case cffoldCOMPTYPE_MSZIP
:
2656 CAB(decompress
) = ZIPdecompress
;
2659 case cffoldCOMPTYPE_QUANTUM
:
2660 CAB(decompress
) = QTMdecompress
;
2661 err
= QTMinit((comptype
>> 8) & 0x1f, (comptype
>> 4) & 0xF);
2664 case cffoldCOMPTYPE_LZX
:
2665 CAB(decompress
) = LZXdecompress
;
2666 err
= LZXinit((comptype
>> 8) & 0x1f);
2670 err
= DECR_DATAFORMAT
;
2672 if (err
) goto exit_handler
;
2674 /* initialisation OK, set current folder and reset offset */
2675 if (oldfol
) cabinet_close(oldfol
->cab
[CAB(split
)]);
2676 if (!cabinet_open(fol
->cab
[0])) goto exit_handler
;
2677 cabinet_seek(fol
->cab
[0], fol
->offset
[0]);
2680 CAB(outlen
) = 0; /* discard existing block */
2684 if (fi
->offset
> CAB(offset
)) {
2685 /* decode bytes and send them to /dev/null */
2686 if ((err
= decompress(fi
, 0, fix
))) goto exit_handler
;
2687 CAB(offset
) = fi
->offset
;
2690 if (!file_open(fi
, lower
, dir
)) return;
2691 err
= decompress(fi
, 1, fix
);
2692 if (err
) CAB(current
) = NULL
; else CAB(offset
) += fi
->length
;
2697 char *errmsg
, *cabname
;
2700 errmsg
= "out of memory!\n"; break;
2701 case DECR_ILLEGALDATA
:
2702 errmsg
= "%s: illegal or corrupt data\n"; break;
2703 case DECR_DATAFORMAT
:
2704 errmsg
= "%s: unsupported data format\n"; break;
2706 errmsg
= "%s: checksum error\n"; break;
2708 errmsg
= "%s: input error\n"; break;
2710 errmsg
= "%s: output error\n"; break;
2712 errmsg
= "%s: unknown error (BUG)\n";
2716 cabname
= (char *) (CAB(current
)->cab
[CAB(split
)]->filename
);
2719 cabname
= (char *) (fi
->folder
->cab
[0]->filename
);
2722 ERR(errmsg
, cabname
);
2726 /*********************************************************
2727 * print_fileinfo (internal)
2729 void print_fileinfo(struct cab_file
*fi
) {
2730 int d
= fi
->date
, t
= fi
->time
;
2733 if (fi
->attribs
& cffile_A_NAME_IS_UTF
) {
2734 fname
= malloc(strlen(fi
->filename
) + 1);
2736 strcpy(fname
, fi
->filename
);
2737 convertUTF((cab_UBYTE
*) fname
);
2741 TRACE("%9u | %02d.%02d.%04d %02d:%02d:%02d | %s\n",
2743 d
& 0x1f, (d
>>5) & 0xf, (d
>>9) + 1980,
2744 t
>> 11, (t
>>5) & 0x3f, (t
<< 1) & 0x3e,
2745 fname
? fname
: fi
->filename
2748 if (fname
) free(fname
);
2751 /****************************************************************************
2752 * process_cabinet (internal)
2754 * called to simply "extract" a cabinet file. Will find every cabinet file
2755 * in that file, search for every chained cabinet attached to those cabinets,
2756 * and will either extract the cabinets, or ? (call a callback?)
2759 * cabname [I] name of the cabinet file to extract
2760 * dir [I] directory to extract to
2761 * fix [I] attempt to process broken cabinets
2762 * lower [I] ? (lower case something or other?)
2768 BOOL
process_cabinet(LPCSTR cabname
, LPCSTR dir
, BOOL fix
, BOOL lower
)
2770 struct cabinet
*basecab
, *cab
, *cab1
, *cab2
;
2771 struct cab_file
*filelist
, *fi
;
2773 /* has the list-mode header been seen before? */
2776 ZeroMemory(&decomp_state
, sizeof(cab_decomp_state
));
2778 TRACE("Extract %s\n", debugstr_a(cabname
));
2780 /* load the file requested */
2781 basecab
= find_cabs_in_file(cabname
);
2782 if (!basecab
) return FALSE
;
2784 /* iterate over all cabinets found in that file */
2785 for (cab
= basecab
; cab
; cab
=cab
->next
) {
2787 /* bi-directionally load any spanning cabinets -- backwards */
2788 for (cab1
= cab
; cab1
->flags
& cfheadPREV_CABINET
; cab1
= cab1
->prevcab
) {
2789 TRACE("%s: extends backwards to %s (%s)\n", debugstr_a(cabname
),
2790 debugstr_a(cab1
->prevname
), debugstr_a(cab1
->previnfo
));
2791 find_cabinet_file(&(cab1
->prevname
), cabname
);
2792 if (!(cab1
->prevcab
= load_cab_offset(cab1
->prevname
, 0))) {
2793 ERR("%s: can't read previous cabinet %s\n", debugstr_a(cabname
), debugstr_a(cab1
->prevname
));
2796 cab1
->prevcab
->nextcab
= cab1
;
2799 /* bi-directionally load any spanning cabinets -- forwards */
2800 for (cab2
= cab
; cab2
->flags
& cfheadNEXT_CABINET
; cab2
= cab2
->nextcab
) {
2801 TRACE("%s: extends to %s (%s)\n", debugstr_a(cabname
),
2802 debugstr_a(cab2
->nextname
), debugstr_a(cab2
->nextinfo
));
2803 find_cabinet_file(&(cab2
->nextname
), cabname
);
2804 if (!(cab2
->nextcab
= load_cab_offset(cab2
->nextname
, 0))) {
2805 ERR("%s: can't read next cabinet %s\n", debugstr_a(cabname
), debugstr_a(cab2
->nextname
));
2808 cab2
->nextcab
->prevcab
= cab2
;
2811 filelist
= process_files(cab1
);
2812 CAB(current
) = NULL
;
2815 TRACE("File size | Date Time | Name\n");
2816 TRACE("----------+---------------------+-------------\n");
2819 for (fi
= filelist
; fi
; fi
= fi
->next
)
2821 TRACE("Beginning Extraction...\n");
2822 for (fi
= filelist
; fi
; fi
= fi
->next
) {
2823 TRACE(" extracting: %s\n", debugstr_a(fi
->filename
));
2824 extract_file(fi
, lower
, fix
, dir
);
2828 TRACE("Finished processing cabinet.\n");