KDevelop API Documentation

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.1.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Tue Feb 22 09:22:39 2005 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2003