KDevelop API Documentation

parts/doctreeview/chm/decompress.cpp

Go to the documentation of this file.
00001 /* Most of this file is taken from: 00002 cabextract 0.5 - a program to extract Microsoft Cabinet files 00003 (C) 2000-2001 Stuart Caie <kyzer@4u.net> 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public License 00016 along with this library; see the file COPYING.LIB. If not, write to 00017 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 00018 Boston, MA 02111-1307, USA. 00019 */ 00020 00021 #include <stdio.h> 00022 #include <stdlib.h> 00023 #include <string.h> 00024 #include "decompress.h" 00025 00026 int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table); 00027 int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb); 00028 00029 00030 /*--------------------------------------------------------------------------*/ 00031 /* our archiver information / state */ 00032 00033 /* LZX stuff */ 00034 00035 /* some constants defined by the LZX specification */ 00036 #define LZX_MIN_MATCH (2) 00037 #define LZX_MAX_MATCH (257) 00038 #define LZX_NUM_CHARS (256) 00039 #define LZX_BLOCKTYPE_INVALID (0) /* also blocktypes 4-7 invalid */ 00040 #define LZX_BLOCKTYPE_VERBATIM (1) 00041 #define LZX_BLOCKTYPE_ALIGNED (2) 00042 #define LZX_BLOCKTYPE_UNCOMPRESSED (3) 00043 #define LZX_PRETREE_NUM_ELEMENTS (20) 00044 #define LZX_ALIGNED_NUM_ELEMENTS (8) /* aligned offset tree #elements */ 00045 #define LZX_NUM_PRIMARY_LENGTHS (7) /* this one missing from spec! */ 00046 #define LZX_NUM_SECONDARY_LENGTHS (249) /* length tree #elements */ 00047 00048 /* LZX huffman defines: tweak tablebits as desired */ 00049 #define LZX_PRETREE_MAXSYMBOLS (LZX_PRETREE_NUM_ELEMENTS) 00050 #define LZX_PRETREE_TABLEBITS (6) 00051 #define LZX_MAINTREE_MAXSYMBOLS (LZX_NUM_CHARS + 50*8) 00052 #define LZX_MAINTREE_TABLEBITS (12) 00053 #define LZX_LENGTH_MAXSYMBOLS (LZX_NUM_SECONDARY_LENGTHS+1) 00054 #define LZX_LENGTH_TABLEBITS (12) 00055 #define LZX_ALIGNED_MAXSYMBOLS (LZX_ALIGNED_NUM_ELEMENTS) 00056 #define LZX_ALIGNED_TABLEBITS (7) 00057 00058 #define LZX_LENTABLE_SAFETY (64) /* we allow length table decoding overruns */ 00059 00060 #define LZX_DECLARE_TABLE(tbl) \ 00061 UWORD tbl##_table[(1<<LZX_##tbl##_TABLEBITS) + (LZX_##tbl##_MAXSYMBOLS<<1)];\ 00062 UBYTE tbl##_len [LZX_##tbl##_MAXSYMBOLS + LZX_LENTABLE_SAFETY] 00063 00064 struct LZXstate 00065 { 00066 UBYTE *window; /* the actual decoding window */ 00067 ULONG window_size; /* window size (32Kb through 2Mb) */ 00068 ULONG actual_size; /* window size when it was first allocated */ 00069 ULONG window_posn; /* current offset within the window */ 00070 ULONG R0, R1, R2; /* for the LRU offset system */ 00071 UWORD main_elements; /* number of main tree elements */ 00072 int header_read; /* have we started decoding at all yet? */ 00073 UWORD block_type; /* type of this block */ 00074 ULONG block_length; /* uncompressed length of this block */ 00075 ULONG block_remaining; /* uncompressed bytes still left to decode */ 00076 ULONG frames_read; /* the number of CFDATA blocks processed */ 00077 LONG intel_filesize; /* magic header value used for transform */ 00078 LONG intel_curpos; /* current offset in transform space */ 00079 int intel_started; /* have we seen any translatable data yet? */ 00080 00081 LZX_DECLARE_TABLE(PRETREE); 00082 LZX_DECLARE_TABLE(MAINTREE); 00083 LZX_DECLARE_TABLE(LENGTH); 00084 LZX_DECLARE_TABLE(ALIGNED); 00085 }; 00086 00087 00088 /* generic stuff */ 00089 #define CAB(x) (decomp_state.x) 00090 #define LZX(x) (decomp_state.lzx.x) 00091 #define DECR_OK (0) 00092 #define DECR_DATAFORMAT (1) 00093 #define DECR_ILLEGALDATA (2) 00094 #define DECR_NOMEMORY (3) 00095 #define DECR_CHECKSUM (4) 00096 #define DECR_INPUT (5) 00097 #define DECR_OUTPUT (6) 00098 00099 struct 00100 { 00101 struct LZXstate lzx; 00102 } decomp_state; 00103 00104 00105 /* LZX decruncher */ 00106 00107 /* Microsoft's LZX document and their implementation of the 00108 * com.ms.util.cab Java package do not concur. 00109 * 00110 * In the LZX document, there is a table showing the correlation between 00111 * window size and the number of position slots. It states that the 1MB 00112 * window = 40 slots and the 2MB window = 42 slots. In the implementation, 00113 * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the 00114 * first slot whose position base is equal to or more than the required 00115 * window size'. This would explain why other tables in the document refer 00116 * to 50 slots rather than 42. 00117 * 00118 * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode 00119 * is not defined in the specification. 00120 * 00121 * The LZX document does not state the uncompressed block has an 00122 * uncompressed length field. Where does this length field come from, so 00123 * we can know how large the block is? The implementation has it as the 24 00124 * bits following after the 3 blocktype bits, before the alignment 00125 * padding. 00126 * 00127 * The LZX document states that aligned offset blocks have their aligned 00128 * offset huffman tree AFTER the main and length trees. The implementation 00129 * suggests that the aligned offset tree is BEFORE the main and length 00130 * trees. 00131 * 00132 * The LZX document decoding algorithm states that, in an aligned offset 00133 * block, if an extra_bits value is 1, 2 or 3, then that number of bits 00134 * should be read and the result added to the match offset. This is 00135 * correct for 1 and 2, but not 3, where just a huffman symbol (using the 00136 * aligned tree) should be read. 00137 * 00138 * Regarding the E8 preprocessing, the LZX document states 'No translation 00139 * may be performed on the last 6 bytes of the input block'. This is 00140 * correct. However, the pseudocode provided checks for the *E8 leader* 00141 * up to the last 6 bytes. If the leader appears between -10 and -7 bytes 00142 * from the end, this would cause the next four bytes to be modified, at 00143 * least one of which would be in the last 6 bytes, which is not allowed 00144 * according to the spec. 00145 * 00146 * The specification states that the huffman trees must always contain at 00147 * least one element. However, many CAB files contain blocks where the 00148 * length tree is completely empty (because there are no matches), and 00149 * this is expected to succeed. 00150 */ 00151 00152 00153 /* LZX uses what it calls 'position slots' to represent match offsets. 00154 * What this means is that a small 'position slot' number and a small 00155 * offset from that slot are encoded instead of one large offset for 00156 * every match. 00157 * - position_base is an index to the position slot bases 00158 * - extra_bits states how many bits of offset-from-base data is needed. 00159 */ 00160 static ULONG position_base[51]; 00161 static UBYTE extra_bits[51]; 00162 00163 00164 int LZXinit(int window) { 00165 ULONG wndsize = 1 << window; 00166 int i, j, posn_slots; 00167 00168 /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */ 00169 /* if a previously allocated window is big enough, keep it */ 00170 if (window < 15 || window > 21) return DECR_DATAFORMAT; 00171 if (LZX(actual_size) < wndsize) 00172 { 00173 if (LZX(window)) free(LZX(window)); 00174 LZX(window) = NULL; 00175 } 00176 if (!LZX(window)) 00177 { 00178 if (!(LZX(window) = (UBYTE*)malloc(wndsize))) return DECR_NOMEMORY; 00179 LZX(actual_size) = wndsize; 00180 } 00181 LZX(window_size) = wndsize; 00182 00183 /* initialise static tables */ 00184 for (i=0, j=0; i <= 50; i += 2) 00185 { 00186 extra_bits[i] = extra_bits[i+1] = j; /* 0,0,0,0,1,1,2,2,3,3... */ 00187 if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */ 00188 } 00189 for (i=0, j=0; i <= 50; i++) 00190 { 00191 position_base[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */ 00192 j += 1 << extra_bits[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */ 00193 } 00194 00195 /* calculate required position slots */ 00196 if (window == 20) posn_slots = 42; 00197 else if (window == 21) posn_slots = 50; 00198 else posn_slots = window << 1; 00199 00200 /*posn_slots=i=0; while (i < wndsize) i += 1 << extra_bits[posn_slots++]; */ 00201 00202 00203 LZX(R0) = LZX(R1) = LZX(R2) = 1; 00204 LZX(main_elements) = LZX_NUM_CHARS + (posn_slots << 3); 00205 LZX(header_read) = 0; 00206 LZX(frames_read) = 0; 00207 LZX(block_remaining) = 0; 00208 LZX(block_type) = LZX_BLOCKTYPE_INVALID; 00209 LZX(intel_curpos) = 0; 00210 LZX(intel_started) = 0; 00211 LZX(window_posn) = 0; 00212 00213 /* initialise tables to 0 (because deltas will be applied to them) */ 00214 for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) LZX(MAINTREE_len)[i] = 0; 00215 for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) LZX(LENGTH_len)[i] = 0; 00216 00217 return DECR_OK; 00218 } 00219 00220 00221 /* Bitstream reading macros: 00222 * 00223 * INIT_BITSTREAM should be used first to set up the system 00224 * READ_BITS(var,n) takes N bits from the buffer and puts them in var 00225 * 00226 * ENSURE_BITS(n) ensures there are at least N bits in the bit buffer 00227 * PEEK_BITS(n) extracts (without removing) N bits from the bit buffer 00228 * REMOVE_BITS(n) removes N bits from the bit buffer 00229 * 00230 * These bit access routines work by using the area beyond the MSB and the 00231 * LSB as a free source of zeroes. This avoids having to mask any bits. 00232 * So we have to know the bit width of the bitbuffer variable. This is 00233 * sizeof(ULONG) * 8, also defined as ULONG_BITS 00234 */ 00235 00236 /* number of bits in ULONG. Note: This must be at multiple of 16, and at 00237 * least 32 for the bitbuffer code to work (ie, it must be able to ensure 00238 * up to 17 bits - that's adding 16 bits when there's one bit left, or 00239 * adding 32 bits when there are no bits left. The code should work fine 00240 * for machines where ULONG >= 32 bits. 00241 */ 00242 #define ULONG_BITS (sizeof(ULONG)<<3) 00243 00244 #define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0) 00245 00246 #define ENSURE_BITS(n) \ 00247 while (bitsleft < (n)) { \ 00248 bitbuf |= ((inpos[1]<<8)|inpos[0]) << (ULONG_BITS-16 - bitsleft); \ 00249 bitsleft += 16; inpos+=2; \ 00250 } 00251 00252 #define PEEK_BITS(n) (bitbuf >> (ULONG_BITS - (n))) 00253 #define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n))) 00254 00255 #define READ_BITS(v,n) do { \ 00256 ENSURE_BITS(n); \ 00257 (v) = PEEK_BITS(n); \ 00258 REMOVE_BITS(n); \ 00259 } while (0) 00260 00261 00262 /* Huffman macros */ 00263 00264 #define TABLEBITS(tbl) (LZX_##tbl##_TABLEBITS) 00265 #define MAXSYMBOLS(tbl) (LZX_##tbl##_MAXSYMBOLS) 00266 #define SYMTABLE(tbl) (LZX(tbl##_table)) 00267 #define LENTABLE(tbl) (LZX(tbl##_len)) 00268 00269 /* BUILD_TABLE(tablename) builds a huffman lookup table from code lengths. 00270 * In reality, it just calls make_decode_table() with the appropriate 00271 * values - they're all fixed by some #defines anyway, so there's no point 00272 * writing each call out in full by hand. 00273 */ 00274 #define BUILD_TABLE(tbl) \ 00275 if (make_decode_table( \ 00276 MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl) \ 00277 )) { return DECR_ILLEGALDATA; } 00278 00279 00280 /* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the 00281 * bitstream using the stated table and puts it in var. 00282 */ 00283 #define READ_HUFFSYM(tbl,var) do { \ 00284 ENSURE_BITS(16); \ 00285 hufftbl = SYMTABLE(tbl); \ 00286 if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) { \ 00287 j = 1 << (ULONG_BITS - TABLEBITS(tbl)); \ 00288 do { \ 00289 j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0; \ 00290 if (!j) { return DECR_ILLEGALDATA; } \ 00291 } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl)); \ 00292 } \ 00293 j = LENTABLE(tbl)[(var) = i]; \ 00294 REMOVE_BITS(j); \ 00295 } while (0) 00296 00297 00298 /* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols 00299 * first to last in the given table. The code lengths are stored in their 00300 * own special LZX way. 00301 */ 00302 #define READ_LENGTHS(tbl,first,last) do { \ 00303 lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \ 00304 if (lzx_read_lens(LENTABLE(tbl),(first),(last),&lb)) { \ 00305 return DECR_ILLEGALDATA; \ 00306 } \ 00307 bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \ 00308 } while (0) 00309 00310 00311 /* make_decode_table(nsyms, nbits, length[], table[]) 00312 * 00313 * This function was coded by David Tritscher. It builds a fast huffman 00314 * decoding table out of just a canonical huffman code lengths table. 00315 * 00316 * nsyms = total number of symbols in this huffman tree. 00317 * nbits = any symbols with a code length of nbits or less can be decoded 00318 * in one lookup of the table. 00319 * length = A table to get code lengths from [0 to syms-1] 00320 * table = The table to fill up with decoded symbols and pointers. 00321 * 00322 * Returns 0 for OK or 1 for error 00323 */ 00324 00325 int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table) { 00326 register UWORD sym; 00327 register ULONG leaf; 00328 register UBYTE bit_num = 1; 00329 ULONG fill; 00330 ULONG pos = 0; /* the current position in the decode table */ 00331 ULONG table_mask = 1 << nbits; 00332 ULONG bit_mask = table_mask >> 1; /* don't do 0 length codes */ 00333 ULONG next_symbol = bit_mask; /* base of allocation for long codes */ 00334 00335 /* fill entries for codes short enough for a direct mapping */ 00336 while (bit_num <= nbits) 00337 { 00338 for (sym = 0; sym < nsyms; sym++) 00339 { 00340 if (length[sym] == bit_num) 00341 { 00342 leaf = pos; 00343 00344 if ((pos += bit_mask) > table_mask) return 1; /* table overrun */ 00345 00346 /* fill all possible lookups of this symbol with the symbol itself */ 00347 fill = bit_mask; 00348 while (fill-- > 0) table[leaf++] = sym; 00349 } 00350 } 00351 bit_mask >>= 1; 00352 bit_num++; 00353 } 00354 00355 /* if there are any codes longer than nbits */ 00356 if (pos != table_mask) 00357 { 00358 /* clear the remainder of the table */ 00359 for (sym = pos; sym < table_mask; sym++) table[sym] = 0; 00360 00361 /* give ourselves room for codes to grow by up to 16 more bits */ 00362 pos <<= 16; 00363 table_mask <<= 16; 00364 bit_mask = 1 << 15; 00365 00366 while (bit_num <= 16) 00367 { 00368 for (sym = 0; sym < nsyms; sym++) 00369 { 00370 if (length[sym] == bit_num) 00371 { 00372 leaf = pos >> 16; 00373 for (fill = 0; fill < bit_num - nbits; fill++) 00374 { 00375 /* if this path hasn't been taken yet, 'allocate' two entries */ 00376 if (table[leaf] == 0) 00377 { 00378 table[(next_symbol << 1)] = 0; 00379 table[(next_symbol << 1) + 1] = 0; 00380 table[leaf] = next_symbol++; 00381 } 00382 /* follow the path and select either left or right for next bit */ 00383 leaf = table[leaf] << 1; 00384 if ((pos >> (15-fill)) & 1) leaf++; 00385 } 00386 table[leaf] = sym; 00387 00388 if ((pos += bit_mask) > table_mask) return 1; /* table overflow */ 00389 } 00390 } 00391 bit_mask >>= 1; 00392 bit_num++; 00393 } 00394 } 00395 00396 /* full table? */ 00397 if (pos == table_mask) return 0; 00398 00399 /* either erroneous table, or all elements are 0 - let's find out. */ 00400 for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1; 00401 return 0; 00402 } 00403 00404 int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb) { 00405 ULONG i,j, x,y; 00406 int z; 00407 00408 register ULONG bitbuf = lb->bb; 00409 register int bitsleft = lb->bl; 00410 UBYTE *inpos = lb->ip; 00411 UWORD *hufftbl; 00412 00413 for (x = 0; x < 20; x++) 00414 { 00415 READ_BITS(y, 4); 00416 LENTABLE(PRETREE)[x] = y; 00417 } 00418 BUILD_TABLE(PRETREE); 00419 00420 for (x = first; x < last;) 00421 { 00422 READ_HUFFSYM(PRETREE, z); 00423 if (z == 17) 00424 { 00425 READ_BITS(y, 4); y += 4; 00426 while (y--) lens[x++] = 0; 00427 } 00428 else if (z == 18) 00429 { 00430 READ_BITS(y, 5); y += 20; 00431 while (y--) lens[x++] = 0; 00432 } 00433 else if (z == 19) 00434 { 00435 READ_BITS(y, 1); y += 4; 00436 READ_HUFFSYM(PRETREE, z); 00437 z = lens[x] - z; if (z < 0) z += 17; 00438 while (y--) lens[x++] = z; 00439 } 00440 else 00441 { 00442 z = lens[x] - z; if (z < 0) z += 17; 00443 lens[x++] = z; 00444 } 00445 } 00446 00447 lb->bb = bitbuf; 00448 lb->bl = bitsleft; 00449 lb->ip = inpos; 00450 return 0; 00451 } 00452 00453 int LZXdecompress(UBYTE* inpos, int inlen, UBYTE* outpos, int outlen) { 00454 UBYTE *endinp = inpos + inlen; 00455 UBYTE *window = LZX(window); 00456 UBYTE *runsrc, *rundest; 00457 UWORD *hufftbl; /* used in READ_HUFFSYM macro as chosen decoding table */ 00458 00459 ULONG window_posn = LZX(window_posn); 00460 ULONG window_size = LZX(window_size); 00461 ULONG R0 = LZX(R0); 00462 ULONG R1 = LZX(R1); 00463 ULONG R2 = LZX(R2); 00464 00465 register ULONG bitbuf; 00466 register int bitsleft; 00467 ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */ 00468 lzx_bits lb; /* used in READ_LENGTHS macro */ 00469 00470 int togo = outlen, this_run, main_element, aligned_bits; 00471 int match_length, length_footer, extra, verbatim_bits; 00472 00473 INIT_BITSTREAM; 00474 00475 /* read header if necessary */ 00476 if (!LZX(header_read)) 00477 { 00478 i = j = 0; 00479 READ_BITS(k, 1); if (k) 00480 { 00481 READ_BITS(i,16); READ_BITS(j,16); 00482 } 00483 LZX(intel_filesize) = (i << 16) | j; /* or 0 if not encoded */ 00484 LZX(header_read) = 1; 00485 } 00486 00487 /* main decoding loop */ 00488 while (togo > 0) 00489 { 00490 /* last block finished, new block expected */ 00491 if (LZX(block_remaining) == 0) 00492 { 00493 if (LZX(block_type) == LZX_BLOCKTYPE_UNCOMPRESSED) 00494 { 00495 if (LZX(block_length) & 1) inpos++; /* realign bitstream to word */ 00496 INIT_BITSTREAM; 00497 } 00498 00499 READ_BITS(LZX(block_type), 3); 00500 READ_BITS(i, 16); 00501 READ_BITS(j, 8); 00502 LZX(block_remaining) = LZX(block_length) = (i << 8) | j; 00503 00504 switch (LZX(block_type)) 00505 { 00506 case LZX_BLOCKTYPE_ALIGNED: 00507 for (i = 0; i < 8; i++) 00508 { 00509 READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j; 00510 } 00511 BUILD_TABLE(ALIGNED); 00512 /* rest of aligned header is same as verbatim */ 00513 00514 case LZX_BLOCKTYPE_VERBATIM: 00515 READ_LENGTHS(MAINTREE, 0, 256); 00516 READ_LENGTHS(MAINTREE, 256, LZX(main_elements)); 00517 BUILD_TABLE(MAINTREE); 00518 if (LENTABLE(MAINTREE)[0xE8] != 0) LZX(intel_started) = 1; 00519 00520 READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS); 00521 BUILD_TABLE(LENGTH); 00522 break; 00523 00524 case LZX_BLOCKTYPE_UNCOMPRESSED: 00525 LZX(intel_started) = 1; /* because we can't assume otherwise */ 00526 ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */ 00527 if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */ 00528 R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4; 00529 R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4; 00530 R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4; 00531 break; 00532 00533 default: 00534 return DECR_ILLEGALDATA; 00535 } 00536 } 00537 00538 /* buffer exhaustion check */ 00539 if (inpos > endinp) 00540 { 00541 /* it's possible to have a file where the next run is less than 00542 * 16 bits in size. In this case, the READ_HUFFSYM() macro used 00543 * in building the tables will exhaust the buffer, so we should 00544 * allow for this, but not allow those accidentally read bits to 00545 * be used (so we check that there are at least 16 bits 00546 * remaining - in this boundary case they aren't really part of 00547 * the compressed data) 00548 */ 00549 if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA; 00550 } 00551 00552 while ((this_run = LZX(block_remaining)) > 0 && togo > 0) 00553 { 00554 if (this_run > togo) this_run = togo; 00555 togo -= this_run; 00556 LZX(block_remaining) -= this_run; 00557 00558 /* apply 2^x-1 mask */ 00559 window_posn &= window_size - 1; 00560 /* runs can't straddle the window wraparound */ 00561 if ((window_posn + this_run) > window_size) 00562 return DECR_DATAFORMAT; 00563 00564 switch (LZX(block_type)) 00565 { 00566 00567 case LZX_BLOCKTYPE_VERBATIM: 00568 while (this_run > 0) 00569 { 00570 READ_HUFFSYM(MAINTREE, main_element); 00571 00572 if (main_element < LZX_NUM_CHARS) 00573 { 00574 /* literal: 0 to LZX_NUM_CHARS-1 */ 00575 window[window_posn++] = main_element; 00576 this_run--; 00577 } 00578 else 00579 { 00580 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */ 00581 main_element -= LZX_NUM_CHARS; 00582 00583 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; 00584 if (match_length == LZX_NUM_PRIMARY_LENGTHS) 00585 { 00586 READ_HUFFSYM(LENGTH, length_footer); 00587 match_length += length_footer; 00588 } 00589 match_length += LZX_MIN_MATCH; 00590 00591 match_offset = main_element >> 3; 00592 00593 if (match_offset > 2) 00594 { 00595 /* not repeated offset */ 00596 if (match_offset != 3) 00597 { 00598 extra = extra_bits[match_offset]; 00599 READ_BITS(verbatim_bits, extra); 00600 match_offset = position_base[match_offset] - 2 + verbatim_bits; 00601 } 00602 else 00603 { 00604 match_offset = 1; 00605 } 00606 00607 /* update repeated offset LRU queue */ 00608 R2 = R1; R1 = R0; R0 = match_offset; 00609 } 00610 else if (match_offset == 0) 00611 { 00612 match_offset = R0; 00613 } 00614 else if (match_offset == 1) 00615 { 00616 match_offset = R1; 00617 R1 = R0; R0 = match_offset; 00618 } 00619 else /* match_offset == 2 */ 00620 { 00621 match_offset = R2; 00622 R2 = R0; R0 = match_offset; 00623 } 00624 00625 rundest = window + window_posn; 00626 runsrc = rundest - match_offset; 00627 window_posn += match_length; 00628 this_run -= match_length; 00629 00630 /* copy any wrapped around source data */ 00631 while ((runsrc < window) && (match_length-- > 0)) 00632 { 00633 *rundest++ = *(runsrc + window_size); runsrc++; 00634 } 00635 /* copy match data - no worries about destination wraps */ 00636 while (match_length-- > 0) *rundest++ = *runsrc++; 00637 00638 } 00639 } 00640 break; 00641 00642 case LZX_BLOCKTYPE_ALIGNED: 00643 while (this_run > 0) 00644 { 00645 READ_HUFFSYM(MAINTREE, main_element); 00646 00647 if (main_element < LZX_NUM_CHARS) 00648 { 00649 /* literal: 0 to LZX_NUM_CHARS-1 */ 00650 window[window_posn++] = main_element; 00651 this_run--; 00652 } 00653 else 00654 { 00655 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */ 00656 main_element -= LZX_NUM_CHARS; 00657 00658 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; 00659 if (match_length == LZX_NUM_PRIMARY_LENGTHS) 00660 { 00661 READ_HUFFSYM(LENGTH, length_footer); 00662 match_length += length_footer; 00663 } 00664 match_length += LZX_MIN_MATCH; 00665 00666 match_offset = main_element >> 3; 00667 00668 if (match_offset > 2) 00669 { 00670 /* not repeated offset */ 00671 extra = extra_bits[match_offset]; 00672 match_offset = position_base[match_offset] - 2; 00673 if (extra > 3) 00674 { 00675 /* verbatim and aligned bits */ 00676 extra -= 3; 00677 READ_BITS(verbatim_bits, extra); 00678 match_offset += (verbatim_bits << 3); 00679 READ_HUFFSYM(ALIGNED, aligned_bits); 00680 match_offset += aligned_bits; 00681 } 00682 else if (extra == 3) 00683 { 00684 /* aligned bits only */ 00685 READ_HUFFSYM(ALIGNED, aligned_bits); 00686 match_offset += aligned_bits; 00687 } 00688 else if (extra > 0) 00689 { /* extra==1, extra==2 */ 00690 /* verbatim bits only */ 00691 READ_BITS(verbatim_bits, extra); 00692 match_offset += verbatim_bits; 00693 } 00694 else /* extra == 0 */ 00695 { 00696 /* ??? */ 00697 match_offset = 1; 00698 } 00699 00700 /* update repeated offset LRU queue */ 00701 R2 = R1; R1 = R0; R0 = match_offset; 00702 } 00703 else if (match_offset == 0) 00704 { 00705 match_offset = R0; 00706 } 00707 else if (match_offset == 1) 00708 { 00709 match_offset = R1; 00710 R1 = R0; R0 = match_offset; 00711 } 00712 else /* match_offset == 2 */ 00713 { 00714 match_offset = R2; 00715 R2 = R0; R0 = match_offset; 00716 } 00717 00718 rundest = window + window_posn; 00719 runsrc = rundest - match_offset; 00720 window_posn += match_length; 00721 this_run -= match_length; 00722 00723 /* copy any wrapped around source data */ 00724 while ((runsrc < window) && (match_length-- > 0)) 00725 { 00726 *rundest++ = *(runsrc + window_size); runsrc++; 00727 } 00728 /* copy match data - no worries about destination wraps */ 00729 while (match_length-- > 0) *rundest++ = *runsrc++; 00730 00731 } 00732 } 00733 break; 00734 00735 case LZX_BLOCKTYPE_UNCOMPRESSED: 00736 if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA; 00737 memcpy(window + window_posn, inpos, (size_t) this_run); 00738 inpos += this_run; window_posn += this_run; 00739 break; 00740 00741 default: 00742 return DECR_ILLEGALDATA; /* might as well */ 00743 } 00744 00745 } 00746 } 00747 00748 if (togo != 0) return DECR_ILLEGALDATA; 00749 memcpy(outpos, window + ((!window_posn) ? window_size : window_posn) - 00750 outlen, (size_t) outlen); 00751 00752 LZX(window_posn) = window_posn; 00753 LZX(R0) = R0; 00754 LZX(R1) = R1; 00755 LZX(R2) = R2; 00756 00757 /* intel E8 decoding */ 00758 if ((LZX(frames_read)++ < 32768) && LZX(intel_filesize) != 0) 00759 { 00760 if (outlen <= 6 || !LZX(intel_started)) 00761 { 00762 LZX(intel_curpos) += outlen; 00763 } 00764 else 00765 { 00766 UBYTE *data = outpos; 00767 UBYTE *dataend = data + outlen - 10; 00768 LONG curpos = LZX(intel_curpos); 00769 LONG filesize = LZX(intel_filesize); 00770 LONG abs_off, rel_off; 00771 00772 LZX(intel_curpos) = curpos + outlen; 00773 00774 while (data < dataend) 00775 { 00776 if (*data++ != 0xE8) 00777 { 00778 curpos++; continue; 00779 } 00780 abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24); 00781 if ((abs_off >= -curpos) && (abs_off < filesize)) 00782 { 00783 rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize; 00784 data[0] = (UBYTE) rel_off; 00785 data[1] = (UBYTE) (rel_off >> 8); 00786 data[2] = (UBYTE) (rel_off >> 16); 00787 data[3] = (UBYTE) (rel_off >> 24); 00788 } 00789 data += 4; 00790 curpos += 5; 00791 } 00792 } 00793 } 00794 return DECR_OK; 00795 } 00796
KDE Logo
This file is part of the documentation for KDevelop Version 3.0.4.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Wed Oct 6 17:39:10 2004 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003