1 /* deflate.cpp -- compress data using the deflation algorithm

     2  * Copyright (C) 1995-2005 Jean-loup Gailly.

     3  * For conditions of distribution and use, see copyright notice in zlib.h

     4  */

     5 

     6 /*

     7  *  ALGORITHM

     8  *

     9  *      The "deflation" process depends on being able to identify portions

    10  *      of the input text which are identical to earlier input (within a

    11  *      sliding window trailing behind the input currently being processed).

    12  *

    13  *      The most straightforward technique turns out to be the fastest for

    14  *      most input files: try all possible matches and select the longest.

    15  *      The key feature of this algorithm is that insertions into the string

    16  *      dictionary are very simple and thus fast, and deletions are avoided

    17  *      completely. Insertions are performed at each input character, whereas

    18  *      string matches are performed only when the previous match ends. So it

    19  *      is preferable to spend more time in matches to allow very fast string

    20  *      insertions and avoid deletions. The matching algorithm for small

    21  *      strings is inspired from that of Rabin & Karp. A brute force approach

    22  *      is used to find longer strings when a small match has been found.

    23  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze

    24  *      (by Leonid Broukhis).

    25  *         A previous version of this file used a more sophisticated algorithm

    26  *      (by Fiala and Greene) which is guaranteed to run in linear amortized

    27  *      time, but has a larger average cost, uses more memory and is patented.

    28  *      However the F&G algorithm may be faster for some highly redundant

    29  *      files if the parameter max_chain_length (described below) is too large.

    30  *

    31  *  ACKNOWLEDGEMENTS

    32  *

    33  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and

    34  *      I found it in 'freeze' written by Leonid Broukhis.

    35  *      Thanks to many people for bug reports and testing.

    36  *

    37  *  REFERENCES

    38  *

    39  *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".

    40  *      Available in http://www.ietf.org/rfc/rfc1951.txt

    41  *

    42  *      A description of the Rabin and Karp algorithm is given in the book

    43  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.

    44  *

    45  *      Fiala,E.R., and Greene,D.H.

    46  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595

    47  *

    48  */

    49 

    50 /* @(#) $Id: deflate.cpp,v 1.1.2.1 2008/08/14 15:26:57 e0222316 Exp $ */

    51 

    52 #include "deflate.h"

    53 

    54 const char deflate_copyright[] =

    55    " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";

    56 

    57 /*

    58   If you use the zlib library in a product, an acknowledgment is welcome

    59   in the documentation of your product. If for some reason you cannot

    60   include such an acknowledgment, I would appreciate that you keep this

    61   copyright string in the executable of your product.

    62  */

    63 

    64 /* ===========================================================================

    65  *  Function prototypes.

    66  */

    67 typedef enum {

    68     need_more,      /* block not completed, need more input or more output */

    69     block_done,     /* block flush performed */

    70     finish_started, /* finish started, need only more output at next deflate */

    71     finish_done     /* finish done, accept no more input or output */

    72 } block_state;

    73 

    74 typedef block_state (*compress_func) OF((deflate_state *s, int flush));

    75 /* Compression function. Returns the block state after the call. */

    76 

    77 local void fill_window    OF((deflate_state *s));

    78 local block_state deflate_stored OF((deflate_state *s, int flush));

    79 local block_state deflate_fast   OF((deflate_state *s, int flush));

    80 #ifndef FASTEST

    81 local block_state deflate_slow   OF((deflate_state *s, int flush));

    82 #endif

    83 local void lm_init        OF((deflate_state *s));

    84 local void putShortMSB    OF((deflate_state *s, uInt b));

    85 local void flush_pending  OF((z_streamp strm));

    86 local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));

    87 #ifndef FASTEST

    88 #ifdef ASMV

    89       void match_init OF((void)); /* asm code initialization */

    90       uInt longest_match  OF((deflate_state *s, IPos cur_match));

    91 #else

    92 local uInt longest_match  OF((deflate_state *s, IPos cur_match));

    93 #endif

    94 #endif

    95 local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));

    96 

    97 #ifdef DEBUG

    98 local  void check_match OF((deflate_state *s, IPos start, IPos match,

    99                             int length));

   100 #endif

   101 

   102 /* ===========================================================================

   103  * Local data

   104  */

   105 

   106 #define NIL 0

   107 /* Tail of hash chains */

   108 

   109 #ifndef TOO_FAR

   110 #  define TOO_FAR 4096

   111 #endif

   112 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */

   113 

   114 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)

   115 /* Minimum amount of lookahead, except at the end of the input file.

   116  * See deflate.c for comments about the MIN_MATCH+1.

   117  */

   118 

   119 /* Values for max_lazy_match, good_match and max_chain_length, depending on

   120  * the desired pack level (0..9). The values given below have been tuned to

   121  * exclude worst case performance for pathological files. Better values may be

   122  * found for specific files.

   123  */

   124 typedef struct config_s {

   125    ush good_length; /* reduce lazy search above this match length */

   126    ush max_lazy;    /* do not perform lazy search above this match length */

   127    ush nice_length; /* quit search above this match length */

   128    ush max_chain;

   129    compress_func func;

   130 } config;

   131 

   132 #ifdef FASTEST

   133 local const config configuration_table[2] = {

   134 /*      good lazy nice chain */

   135 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */

   136 /* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */

   137 #else

   138 local const config configuration_table[10] = {

   139 /*      good lazy nice chain */

   140 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */

   141 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */

   142 /* 2 */ {4,    5, 16,    8, deflate_fast},

   143 /* 3 */ {4,    6, 32,   32, deflate_fast},

   144 

   145 /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */

   146 /* 5 */ {8,   16, 32,   32, deflate_slow},

   147 /* 6 */ {8,   16, 128, 128, deflate_slow},

   148 /* 7 */ {8,   32, 128, 256, deflate_slow},

   149 /* 8 */ {32, 128, 258, 1024, deflate_slow},

   150 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */

   151 #endif

   152 

   153 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4

   154  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different

   155  * meaning.

   156  */

   157 

   158 #define EQUAL 0

   159 /* result of memcmp for equal strings */

   160 

   161 #ifndef NO_DUMMY_DECL

   162 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */

   163 #endif

   164 

   165 /* ===========================================================================

   166  * Update a hash value with the given input byte

   167  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive

   168  *    input characters, so that a running hash key can be computed from the

   169  *    previous key instead of complete recalculation each time.

   170  */

   171 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)

   172 

   173 

   174 /* ===========================================================================

   175  * Insert string str in the dictionary and set match_head to the previous head

   176  * of the hash chain (the most recent string with same hash key). Return

   177  * the previous length of the hash chain.

   178  * If this file is compiled with -DFASTEST, the compression level is forced

   179  * to 1, and no hash chains are maintained.

   180  * IN  assertion: all calls to to INSERT_STRING are made with consecutive

   181  *    input characters and the first MIN_MATCH bytes of str are valid

   182  *    (except for the last MIN_MATCH-1 bytes of the input file).

   183  */

   184 #ifdef FASTEST

   185 #define INSERT_STRING(s, str, match_head) \

   186    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \

   187     match_head = s->head[s->ins_h], \

   188     s->head[s->ins_h] = (Pos)(str))

   189 #else

   190 #define INSERT_STRING(s, str, match_head) \

   191    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \

   192     match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \

   193     s->head[s->ins_h] = (Pos)(str))

   194 #endif

   195 

   196 /* ===========================================================================

   197  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).

   198  * prev[] will be initialized on the fly.

   199  */

   200 #define CLEAR_HASH(s) \

   201     s->head[s->hash_size-1] = NIL; \

   202     zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));

   203 

   204 /* ========================================================================= */

   205 #ifdef __SYMBIAN32__

   206 EXPORT_C int  deflateInit__r( z_streamp strm,int  level,const char * version,int  stream_size)

   207 #else

   208 int ZEXPORT deflateInit_(strm, level, version, stream_size)

   209     z_streamp strm;

   210     int level;

   211     const char *version;

   212     int stream_size;

   213 #endif //__SYMBIAN32__

   214 {

   215     return deflateInit2__r(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,

   216                          Z_DEFAULT_STRATEGY, version, stream_size);

   217     /* To do: ignore strm->next_in if we use it as window */

   218 }

   219 

   220 /* ========================================================================= */

   221 #ifdef __SYMBIAN32__

   222 EXPORT_C int  deflateInit2__r(z_streamp strm, int level,int method,int windowBits,int memLevel,int strategy,

   223                const char * version,int stream_size)

   224 #else

   225 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,

   226                   version, stream_size)

   227     z_streamp strm;

   228     int  level;

   229     int  method;

   230     int  windowBits;

   231     int  memLevel;

   232     int  strategy;

   233     const char *version;

   234     int stream_size;

   235 #endif //__SYMBIAN32__

   236 {

   237     deflate_state *s;

   238     int wrap = 1;

   239     static const char my_version[] = ZLIB_VERSION;

   240 

   241     ushf *overlay;

   242     /* We overlay pending_buf and d_buf+l_buf. This works since the average

   243      * output size for (length,distance) codes is <= 24 bits.

   244      */

   245 

   246     if (version == Z_NULL || version[0] != my_version[0] ||

   247         stream_size != sizeof(z_stream)) {

   248         return Z_VERSION_ERROR;

   249     }

   250     if (strm == Z_NULL) return Z_STREAM_ERROR;

   251 

   252     strm->msg = Z_NULL;

   253     if (strm->zalloc == (alloc_func)0) {

   254         strm->zalloc = zcalloc;

   255         strm->opaque = (voidpf)0;

   256     }

   257     if (strm->zfree == (free_func)0) strm->zfree = zcfree;

   258 

   259 #ifdef FASTEST

   260     if (level != 0) level = 1;

   261 #else

   262     if (level == Z_DEFAULT_COMPRESSION) level = 6;

   263 #endif

   264 

   265     if (windowBits < 0) { /* suppress zlib wrapper */

   266         wrap = 0;

   267         windowBits = -windowBits;

   268     }

   269 #ifdef GZIP

   270     else if (windowBits > 15) {

   271         wrap = 2;       /* write gzip wrapper instead */

   272         windowBits -= 16;

   273     }

   274 #endif

   275     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||

   276         windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||

   277         strategy < 0 || strategy > Z_FIXED) {

   278         return Z_STREAM_ERROR;

   279     }

   280     if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */

   281     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));

   282     if (s == Z_NULL) return Z_MEM_ERROR;

   283     strm->state = (struct internal_state FAR *)s;

   284     s->strm = strm;

   285 

   286     s->wrap = wrap;

   287     s->gzhead = Z_NULL;

   288     s->w_bits = windowBits;

   289     s->w_size = 1 << s->w_bits;

   290     s->w_mask = s->w_size - 1;

   291 

   292     s->hash_bits = memLevel + 7;

   293     s->hash_size = 1 << s->hash_bits;

   294     s->hash_mask = s->hash_size - 1;

   295     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);

   296 

   297     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));

   298     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));

   299     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));

   300 

   301     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */

   302 

   303     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);

   304     s->pending_buf = (uchf *) overlay;

   305     s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);

   306 

   307     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||

   308         s->pending_buf == Z_NULL) {

   309         s->status = FINISH_STATE;

   310         strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);

   311 

   312         deflateEnd_r (strm);

   313         return Z_MEM_ERROR;

   314     }

   315     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);

   316     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;

   317 

   318     s->level = level;

   319     s->strategy = strategy;

   320     s->method = (Byte)method;

   321 

   322     return deflateReset_r (strm);

   323 }

   324 

   325 /* ========================================================================= */

   326 #ifdef __SYMBIAN32__

   327 EXPORT_C int  deflateSetDictionary_r (z_streamp strm, const Bytef *  dictionary,uInt   dictLength)

   328 #else

   329 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)

   330     z_streamp strm;

   331     const Bytef *dictionary;

   332     uInt  dictLength;

   333 #endif //__SYMBIAN32__

   334 {

   335     deflate_state *s;

   336     uInt length = dictLength;

   337     uInt n;

   338     IPos hash_head = 0;

   339     

   340 	// Line to stop compiler warning about unused mandatory global variable 'deflate_copyright'

   341 	char dontCare = deflate_copyright[0]; dontCare = dontCare;

   342 	

   343     if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||

   344         strm->state->wrap == 2 ||

   345         (strm->state->wrap == 1 && strm->state->status != INIT_STATE))

   346         return Z_STREAM_ERROR;

   347 

   348     s = strm->state;

   349     if (s->wrap)

   350         strm->adler = adler32_r(strm->adler, dictionary, dictLength);

   351 

   352     if (length < MIN_MATCH) return Z_OK;

   353     if (length > MAX_DIST(s)) {

   354         length = MAX_DIST(s);

   355         dictionary += dictLength - length; /* use the tail of the dictionary */

   356     }

   357     zmemcpy(s->window, dictionary, length);

   358     s->strstart = length;

   359     s->block_start = (long)length;

   360 

   361     /* Insert all strings in the hash table (except for the last two bytes).

   362      * s->lookahead stays null, so s->ins_h will be recomputed at the next

   363      * call of fill_window.

   364      */

   365     s->ins_h = s->window[0];

   366     UPDATE_HASH(s, s->ins_h, s->window[1]);

   367     for (n = 0; n <= length - MIN_MATCH; n++) {

   368         INSERT_STRING(s, n, hash_head);

   369     }

   370     if (hash_head) hash_head = 0;  /* to make compiler happy */

   371     return Z_OK;

   372 }

   373 

   374 /* ========================================================================= */

   375 #ifdef __SYMBIAN32__

   376 EXPORT_C int  deflateReset_r (z_streamp strm)

   377 #else

   378 int ZEXPORT deflateReset (strm)

   379     z_streamp strm;

   380 #endif //__SYMBIAN32__

   381 {

   382     deflate_state *s;

   383 

   384     if (strm == Z_NULL || strm->state == Z_NULL ||

   385         strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {

   386         return Z_STREAM_ERROR;

   387     }

   388 

   389     strm->total_in = strm->total_out = 0;

   390     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */

   391     strm->data_type = Z_UNKNOWN;

   392 

   393     s = (deflate_state *)strm->state;

   394     s->pending = 0;

   395     s->pending_out = s->pending_buf;

   396 

   397     if (s->wrap < 0) {

   398         s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */

   399     }

   400     s->status = s->wrap ? INIT_STATE : BUSY_STATE;

   401     strm->adler =

   402 #ifdef GZIP

   403         s->wrap == 2 ? crc32_r(0L, Z_NULL, 0) :

   404 #endif

   405         adler32_r(0L, Z_NULL, 0);

   406     s->last_flush = Z_NO_FLUSH;

   407 

   408     _tr_init(s);

   409     lm_init(s);

   410 

   411     return Z_OK;

   412 }

   413 

   414 /* ========================================================================= */

   415 

   416 #ifdef __SYMBIAN32__

   417 EXPORT_C int deflateSetHeader_r (z_streamp strm, gz_headerp  head)

   418 #else

   419 int ZEXPORT deflateSetHeader (strm, head)

   420     z_streamp strm;

   421     gz_headerp head;

   422 #endif //__SYMBIAN32__

   423 {

   424     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   425     if (strm->state->wrap != 2) return Z_STREAM_ERROR;

   426     strm->state->gzhead = head;

   427     return Z_OK;

   428 }

   429 

   430 /* ========================================================================= */

   431 #ifdef __SYMBIAN32__

   432 EXPORT_C int  deflatePrime_r (z_streamp strm,int  bits,int  value)

   433 #else

   434 int ZEXPORT deflatePrime (strm, bits, value)

   435     z_streamp strm;

   436     int bits;

   437     int value;

   438 #endif //__SYMBIAN32__

   439 {

   440     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   441     strm->state->bi_valid = bits;

   442     strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));

   443     return Z_OK;

   444 }

   445 

   446 /* ========================================================================= */

   447 

   448 #ifdef __SYMBIAN32__

   449 EXPORT_C int deflateParams_r (z_streamp strm,int  level,int  strategy)

   450 #else

   451 int ZEXPORT deflateParams(strm, level, strategy)

   452     z_streamp strm;

   453     int level;

   454     int strategy;

   455 #endif //__SYMBIAN32__

   456 {

   457     deflate_state *s;

   458     compress_func func;

   459     int err = Z_OK;

   460 

   461     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   462     s = strm->state;

   463 

   464 #ifdef FASTEST

   465     if (level != 0) level = 1;

   466 #else

   467     if (level == Z_DEFAULT_COMPRESSION) level = 6;

   468 #endif

   469     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {

   470         return Z_STREAM_ERROR;

   471     }

   472     func = configuration_table[s->level].func;

   473 

   474     if (func != configuration_table[level].func && strm->total_in != 0) {

   475         /* Flush the last buffer: */

   476         err = deflate_r(strm, Z_PARTIAL_FLUSH);

   477     }

   478     if (s->level != level) {

   479         s->level = level;

   480         s->max_lazy_match   = configuration_table[level].max_lazy;

   481         s->good_match       = configuration_table[level].good_length;

   482         s->nice_match       = configuration_table[level].nice_length;

   483         s->max_chain_length = configuration_table[level].max_chain;

   484     }

   485     s->strategy = strategy;

   486     return err;

   487 }

   488 

   489 /* ========================================================================= */

   490 

   491 #ifdef __SYMBIAN32__

   492 EXPORT_C int  deflateTune_r(z_streamp strm, int good_length, int max_lazy, int nice_length, int max_chain)

   493 #else

   494 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)

   495     z_streamp strm;

   496     int good_length;

   497     int max_lazy;

   498     int nice_length;

   499     int max_chain;

   500 #endif //__SYMBIAN32__

   501 {

   502     deflate_state *s;

   503 

   504     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   505     s = strm->state;

   506     s->good_match = good_length;

   507     s->max_lazy_match = max_lazy;

   508     s->nice_match = nice_length;

   509     s->max_chain_length = max_chain;

   510     return Z_OK;

   511 }

   512 

   513 /* =========================================================================

   514  * For the default windowBits of 15 and memLevel of 8, this function returns

   515  * a close to exact, as well as small, upper bound on the compressed size.

   516  * They are coded as constants here for a reason--if the #define's are

   517  * changed, then this function needs to be changed as well.  The return

   518  * value for 15 and 8 only works for those exact settings.

   519  *

   520  * For any setting other than those defaults for windowBits and memLevel,

   521  * the value returned is a conservative worst case for the maximum expansion

   522  * resulting from using fixed blocks instead of stored blocks, which deflate

   523  * can emit on compressed data for some combinations of the parameters.

   524  *

   525  * This function could be more sophisticated to provide closer upper bounds

   526  * for every combination of windowBits and memLevel, as well as wrap.

   527  * But even the conservative upper bound of about 14% expansion does not

   528  * seem onerous for output buffer allocation.

   529  */

   530 

   531 #ifdef __SYMBIAN32__

   532 EXPORT_C  uLong deflateBound_r(z_streamp strm,uLong  sourceLen)

   533 #else

   534 uLong ZEXPORT deflateBound(strm, sourceLen)

   535     z_streamp strm;

   536     uLong sourceLen;

   537 #endif //__SYMBIAN32__

   538 {

   539     deflate_state *s;

   540     uLong destLen;

   541 

   542     /* conservative upper bound */

   543     destLen = sourceLen +

   544               ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11;

   545 

   546     /* if can't get parameters, return conservative bound */

   547     if (strm == Z_NULL || strm->state == Z_NULL)

   548         return destLen;

   549 

   550     /* if not default parameters, return conservative bound */

   551     s = strm->state;

   552     if (s->w_bits != 15 || s->hash_bits != 8 + 7)

   553         return destLen;

   554 

   555     /* default settings: return tight bound for that case */

   556     return compressBound_r(sourceLen);

   557 }

   558 

   559 /* =========================================================================

   560  * Put a short in the pending buffer. The 16-bit value is put in MSB order.

   561  * IN assertion: the stream state is correct and there is enough room in

   562  * pending_buf.

   563  */

   564 

   565 #ifdef __SYMBIAN32__

   566 local void putShortMSB (deflate_state * s, uInt  b)

   567 #else  

   568 local void putShortMSB (s, b)

   569     deflate_state *s;

   570     uInt b;

   571 #endif //__SYMBIAN32__

   572 {

   573     put_byte(s, (Byte)(b >> 8));

   574     put_byte(s, (Byte)(b & 0xff));

   575 }

   576 

   577 /* =========================================================================

   578  * Flush as much pending output as possible. All deflate() output goes

   579  * through this function so some applications may wish to modify it

   580  * to avoid allocating a large strm->next_out buffer and copying into it.

   581  * (See also read_buf()).

   582  */

   583 #ifdef __SYMBIAN32__

   584 local void flush_pending(z_streamp strm)

   585 #else  

   586 local void flush_pending(strm)

   587     z_streamp strm;

   588 #endif //__SYMBIAN32__

   589 {

   590     unsigned len = strm->state->pending;

   591 

   592     if (len > strm->avail_out) len = strm->avail_out;

   593     if (len == 0) return;

   594 

   595     zmemcpy(strm->next_out, strm->state->pending_out, len);

   596     strm->next_out  += len;

   597     strm->state->pending_out  += len;

   598     strm->total_out += len;

   599     strm->avail_out  -= len;

   600     strm->state->pending -= len;

   601     if (strm->state->pending == 0) {

   602         strm->state->pending_out = strm->state->pending_buf;

   603     }

   604 }

   605 

   606 /* ========================================================================= */

   607 

   608 #ifdef __SYMBIAN32__

   609 EXPORT_C int  deflate_r (z_streamp strm,int  flush)

   610 #else

   611 int ZEXPORT deflate (strm, flush)

   612     z_streamp strm;

   613     int flush;

   614 #endif //__SYMBIAN32__

   615 {

   616     int old_flush; /* value of flush param for previous deflate call */

   617     deflate_state *s;

   618 

   619     if (strm == Z_NULL || strm->state == Z_NULL ||

   620         flush > Z_FINISH || flush < 0) {

   621         return Z_STREAM_ERROR;

   622     }

   623     s = strm->state;

   624 

   625     if (strm->next_out == Z_NULL ||

   626         (strm->next_in == Z_NULL && strm->avail_in != 0) ||

   627         (s->status == FINISH_STATE && flush != Z_FINISH)) {

   628         ERR_RETURN(strm, Z_STREAM_ERROR);

   629     }

   630     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

   631 

   632     s->strm = strm; /* just in case */

   633     old_flush = s->last_flush;

   634     s->last_flush = flush;

   635 

   636     /* Write the header */

   637     if (s->status == INIT_STATE) {

   638 #ifdef GZIP

   639         if (s->wrap == 2) {

   640             strm->adler = crc32_r(0L, Z_NULL, 0);

   641             put_byte(s, 31);

   642             put_byte(s, 139);

   643             put_byte(s, 8);

   644             if (s->gzhead == NULL) {

   645                 put_byte(s, 0);

   646                 put_byte(s, 0);

   647                 put_byte(s, 0);

   648                 put_byte(s, 0);

   649                 put_byte(s, 0);

   650                 put_byte(s, s->level == 9 ? 2 :

   651                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?

   652                              4 : 0));

   653                 put_byte(s, OS_CODE);

   654                 s->status = BUSY_STATE;

   655             }

   656             else {

   657                 put_byte(s, (s->gzhead->text ? 1 : 0) +

   658                             (s->gzhead->hcrc ? 2 : 0) +

   659                             (s->gzhead->extra == Z_NULL ? 0 : 4) +

   660                             (s->gzhead->name == Z_NULL ? 0 : 8) +

   661                             (s->gzhead->comment == Z_NULL ? 0 : 16)

   662                         );

   663                 put_byte(s, (Byte)(s->gzhead->time & 0xff));

   664                 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));

   665                 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));

   666                 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));

   667                 put_byte(s, s->level == 9 ? 2 :

   668                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?

   669                              4 : 0));

   670                 put_byte(s, s->gzhead->os & 0xff);

   671                 if (s->gzhead->extra != NULL) {

   672                     put_byte(s, s->gzhead->extra_len & 0xff);

   673                     put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);

   674                 }

   675                 if (s->gzhead->hcrc)

   676                     strm->adler = crc32_r(strm->adler, s->pending_buf,

   677                                         s->pending);

   678                 s->gzindex = 0;

   679                 s->status = EXTRA_STATE;

   680             }

   681         }

   682         else

   683 #endif

   684         {

   685             uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;

   686             uInt level_flags;

   687 

   688             if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)

   689                 level_flags = 0;

   690             else if (s->level < 6)

   691                 level_flags = 1;

   692             else if (s->level == 6)

   693                 level_flags = 2;

   694             else

   695                 level_flags = 3;

   696             header |= (level_flags << 6);

   697             if (s->strstart != 0) header |= PRESET_DICT;

   698             header += 31 - (header % 31);

   699 

   700             s->status = BUSY_STATE;

   701             putShortMSB(s, header);

   702 

   703             /* Save the adler32 of the preset dictionary: */

   704             if (s->strstart != 0) {

   705                 putShortMSB(s, (uInt)(strm->adler >> 16));

   706                 putShortMSB(s, (uInt)(strm->adler & 0xffff));

   707             }

   708             strm->adler = adler32_r(0L, Z_NULL, 0);

   709         }

   710     }

   711 #ifdef GZIP

   712     if (s->status == EXTRA_STATE) {

   713         if (s->gzhead->extra != NULL) {

   714             uInt beg = s->pending;  /* start of bytes to update crc */

   715 

   716             while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {

   717                 if (s->pending == s->pending_buf_size) {

   718                     if (s->gzhead->hcrc && s->pending > beg)

   719                         strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   720                                             s->pending - beg);

   721                     flush_pending(strm);

   722                     beg = s->pending;

   723                     if (s->pending == s->pending_buf_size)

   724                         break;

   725                 }

   726                 put_byte(s, s->gzhead->extra[s->gzindex]);

   727                 s->gzindex++;

   728             }

   729             if (s->gzhead->hcrc && s->pending > beg)

   730                 strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   731                                     s->pending - beg);

   732             if (s->gzindex == s->gzhead->extra_len) {

   733                 s->gzindex = 0;

   734                 s->status = NAME_STATE;

   735             }

   736         }

   737         else

   738             s->status = NAME_STATE;

   739     }

   740     if (s->status == NAME_STATE) {

   741         if (s->gzhead->name != NULL) {

   742             uInt beg = s->pending;  /* start of bytes to update crc */

   743             int val;

   744 

   745             do {

   746                 if (s->pending == s->pending_buf_size) {

   747                     if (s->gzhead->hcrc && s->pending > beg)

   748                         strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   749                                             s->pending - beg);

   750                     flush_pending(strm);

   751                     beg = s->pending;

   752                     if (s->pending == s->pending_buf_size) {

   753                         val = 1;

   754                         break;

   755                     }

   756                 }

   757                 val = s->gzhead->name[s->gzindex++];

   758                 put_byte(s, val);

   759             } while (val != 0);

   760             if (s->gzhead->hcrc && s->pending > beg)

   761                 strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   762                                     s->pending - beg);

   763             if (val == 0) {

   764                 s->gzindex = 0;

   765                 s->status = COMMENT_STATE;

   766             }

   767         }

   768         else

   769             s->status = COMMENT_STATE;

   770     }

   771     if (s->status == COMMENT_STATE) {

   772         if (s->gzhead->comment != NULL) {

   773             uInt beg = s->pending;  /* start of bytes to update crc */

   774             int val;

   775 

   776             do {

   777                 if (s->pending == s->pending_buf_size) {

   778                     if (s->gzhead->hcrc && s->pending > beg)

   779                         strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   780                                             s->pending - beg);

   781                     flush_pending(strm);

   782                     beg = s->pending;

   783                     if (s->pending == s->pending_buf_size) {

   784                         val = 1;

   785                         break;

   786                     }

   787                 }

   788                 val = s->gzhead->comment[s->gzindex++];

   789                 put_byte(s, val);

   790             } while (val != 0);

   791             if (s->gzhead->hcrc && s->pending > beg)

   792                 strm->adler = crc32_r(strm->adler, s->pending_buf + beg,

   793                                     s->pending - beg);

   794             if (val == 0)

   795                 s->status = HCRC_STATE;

   796         }

   797         else

   798             s->status = HCRC_STATE;

   799     }

   800     if (s->status == HCRC_STATE) {

   801         if (s->gzhead->hcrc) {

   802             if (s->pending + 2 > s->pending_buf_size)

   803                 flush_pending(strm);

   804             if (s->pending + 2 <= s->pending_buf_size) {

   805                 put_byte(s, (Byte)(strm->adler & 0xff));

   806                 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));

   807                 strm->adler = crc32_r(0L, Z_NULL, 0);

   808                 s->status = BUSY_STATE;

   809             }

   810         }

   811         else

   812             s->status = BUSY_STATE;

   813     }

   814 #endif

   815 

   816     /* Flush as much pending output as possible */

   817     if (s->pending != 0) {

   818         flush_pending(strm);

   819         if (strm->avail_out == 0) {

   820             /* Since avail_out is 0, deflate will be called again with

   821              * more output space, but possibly with both pending and

   822              * avail_in equal to zero. There won't be anything to do,

   823              * but this is not an error situation so make sure we

   824              * return OK instead of BUF_ERROR at next call of deflate:

   825              */

   826             s->last_flush = -1;

   827             return Z_OK;

   828         }

   829 

   830     /* Make sure there is something to do and avoid duplicate consecutive

   831      * flushes. For repeated and useless calls with Z_FINISH, we keep

   832      * returning Z_STREAM_END instead of Z_BUF_ERROR.

   833      */

   834     } else if (strm->avail_in == 0 && flush <= old_flush &&

   835                flush != Z_FINISH) {

   836         ERR_RETURN(strm, Z_BUF_ERROR);

   837     }

   838 

   839     /* User must not provide more input after the first FINISH: */

   840     if (s->status == FINISH_STATE && strm->avail_in != 0) {

   841         ERR_RETURN(strm, Z_BUF_ERROR);

   842     }

   843 

   844     /* Start a new block or continue the current one.

   845      */

   846     if (strm->avail_in != 0 || s->lookahead != 0 ||

   847         (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {

   848         block_state bstate;

   849 

   850         bstate = (*(configuration_table[s->level].func))(s, flush);

   851 

   852         if (bstate == finish_started || bstate == finish_done) {

   853             s->status = FINISH_STATE;

   854         }

   855         if (bstate == need_more || bstate == finish_started) {

   856             if (strm->avail_out == 0) {

   857                 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */

   858             }

   859             return Z_OK;

   860             /* If flush != Z_NO_FLUSH && avail_out == 0, the next call

   861              * of deflate should use the same flush parameter to make sure

   862              * that the flush is complete. So we don't have to output an

   863              * empty block here, this will be done at next call. This also

   864              * ensures that for a very small output buffer, we emit at most

   865              * one empty block.

   866              */

   867         }

   868         if (bstate == block_done) {

   869             if (flush == Z_PARTIAL_FLUSH) {

   870                 _tr_align(s);

   871             } else { /* FULL_FLUSH or SYNC_FLUSH */

   872                 _tr_stored_block(s, (char*)0, 0L, 0);

   873                 /* For a full flush, this empty block will be recognized

   874                  * as a special marker by inflate_sync().

   875                  */

   876                 if (flush == Z_FULL_FLUSH) {

   877                     CLEAR_HASH(s);             /* forget history */

   878                 }

   879             }

   880             flush_pending(strm);

   881             if (strm->avail_out == 0) {

   882               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */

   883               return Z_OK;

   884             }

   885         }

   886     }

   887     Assert(strm->avail_out > 0, "bug2");

   888 

   889     if (flush != Z_FINISH) return Z_OK;

   890     if (s->wrap <= 0) return Z_STREAM_END;

   891 

   892     /* Write the trailer */

   893 #ifdef GZIP

   894     if (s->wrap == 2) {

   895         put_byte(s, (Byte)(strm->adler & 0xff));

   896         put_byte(s, (Byte)((strm->adler >> 8) & 0xff));

   897         put_byte(s, (Byte)((strm->adler >> 16) & 0xff));

   898         put_byte(s, (Byte)((strm->adler >> 24) & 0xff));

   899         put_byte(s, (Byte)(strm->total_in & 0xff));

   900         put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));

   901         put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));

   902         put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));

   903     }

   904     else

   905 #endif

   906     {

   907         putShortMSB(s, (uInt)(strm->adler >> 16));

   908         putShortMSB(s, (uInt)(strm->adler & 0xffff));

   909     }

   910     flush_pending(strm);

   911     /* If avail_out is zero, the application will call deflate again

   912      * to flush the rest.

   913      */

   914     if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */

   915     return s->pending != 0 ? Z_OK : Z_STREAM_END;

   916 }

   917 

   918 /* ========================================================================= */

   919 #ifdef __SYMBIAN32__

   920 EXPORT_C int   deflateEnd_r (z_streamp strm)

   921 #else

   922 int ZEXPORT deflateEnd (strm)

   923     z_streamp strm;

   924 #endif //__SYMBIAN32__

   925   

   926 {

   927     int status;

   928 

   929     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   930 

   931     status = strm->state->status;

   932     if (status != INIT_STATE &&

   933         status != EXTRA_STATE &&

   934         status != NAME_STATE &&

   935         status != COMMENT_STATE &&

   936         status != HCRC_STATE &&

   937         status != BUSY_STATE &&

   938         status != FINISH_STATE) {

   939       return Z_STREAM_ERROR;

   940     }

   941 

   942     /* Deallocate in reverse order of allocations: */

   943     TRY_FREE(strm, strm->state->pending_buf);

   944     TRY_FREE(strm, strm->state->head);

   945     TRY_FREE(strm, strm->state->prev);

   946     TRY_FREE(strm, strm->state->window);

   947 

   948     ZFREE(strm, strm->state);

   949     strm->state = Z_NULL;

   950 

   951     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;

   952 }

   953 

   954 /* =========================================================================

   955  * Copy the source state to the destination state.

   956  * To simplify the source, this is not supported for 16-bit MSDOS (which

   957  * doesn't have enough memory anyway to duplicate compression states).

   958  */

   959 #ifdef __SYMBIAN32__

   960 EXPORT_C int deflateCopy_r (z_streamp dest, z_streamp source)

   961 #else

   962 int ZEXPORT deflateCopy (dest, source)

   963     z_streamp dest;

   964     z_streamp source;

   965 #endif //__SYMBIAN32__	

   966 {

   967 #ifdef MAXSEG_64K

   968     return Z_STREAM_ERROR;

   969 #else

   970     deflate_state *ds;

   971     deflate_state *ss;

   972     ushf *overlay;

   973 

   974 

   975     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {

   976         return Z_STREAM_ERROR;

   977     }

   978 

   979     ss = source->state;

   980 

   981     zmemcpy(dest, source, sizeof(z_stream));

   982 

   983     ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));

   984     if (ds == Z_NULL) return Z_MEM_ERROR;

   985     dest->state = (struct internal_state FAR *) ds;

   986     zmemcpy(ds, ss, sizeof(deflate_state));

   987     ds->strm = dest;

   988 

   989     ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));

   990     ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));

   991     ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));

   992     overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);

   993     ds->pending_buf = (uchf *) overlay;

   994 

   995     if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||

   996         ds->pending_buf == Z_NULL) {

   997         deflateEnd_r (dest);

   998         return Z_MEM_ERROR;

   999     }

  1000     /* following zmemcpy do not work for 16-bit MSDOS */

  1001     zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));

  1002     zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));

  1003     zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));

  1004     zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);

  1005 

  1006     ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);

  1007     ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);

  1008     ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;

  1009 

  1010     ds->l_desc.dyn_tree = ds->dyn_ltree;

  1011     ds->d_desc.dyn_tree = ds->dyn_dtree;

  1012     ds->bl_desc.dyn_tree = ds->bl_tree;

  1013 

  1014     return Z_OK;

  1015 #endif /* MAXSEG_64K */

  1016 }

  1017 

  1018 /* ===========================================================================

  1019  * Read a new buffer from the current input stream, update the adler32

  1020  * and total number of bytes read.  All deflate() input goes through

  1021  * this function so some applications may wish to modify it to avoid

  1022  * allocating a large strm->next_in buffer and copying from it.

  1023  * (See also flush_pending()).

  1024  */

  1025 #ifdef __SYMBIAN32__

  1026 local int read_buf(z_streamp strm,Bytef *  buf,unsigned  size)

  1027 #else

  1028 local int read_buf(strm, buf, size)

  1029     z_streamp strm;

  1030     Bytef *buf;

  1031     unsigned size;

  1032 #endif //__SYMBIAN32__

  1033 {

  1034     unsigned len = strm->avail_in;

  1035 

  1036     if (len > size) len = size;

  1037     if (len == 0) return 0;

  1038 

  1039     strm->avail_in  -= len;

  1040 

  1041     if (strm->state->wrap == 1) {

  1042         strm->adler = adler32_r(strm->adler, strm->next_in, len);

  1043     }

  1044 #ifdef GZIP

  1045     else if (strm->state->wrap == 2) {

  1046         strm->adler = crc32_r(strm->adler, strm->next_in, len);

  1047     }

  1048 #endif

  1049     zmemcpy(buf, strm->next_in, len);

  1050     strm->next_in  += len;

  1051     strm->total_in += len;

  1052 

  1053     return (int)len;

  1054 }

  1055 

  1056 /* ===========================================================================

  1057  * Initialize the "longest match" routines for a new zlib stream

  1058  */

  1059 

  1060 #ifdef __SYMBIAN32__

  1061 local void lm_init (deflate_state * s)

  1062 #else

  1063 local void lm_init (s)

  1064     deflate_state *s;

  1065 #endif //__SYMBIAN32__

  1066 {

  1067     s->window_size = (ulg)2L*s->w_size;

  1068 

  1069     CLEAR_HASH(s);

  1070 

  1071     /* Set the default configuration parameters:

  1072      */

  1073     s->max_lazy_match   = configuration_table[s->level].max_lazy;

  1074     s->good_match       = configuration_table[s->level].good_length;

  1075     s->nice_match       = configuration_table[s->level].nice_length;

  1076     s->max_chain_length = configuration_table[s->level].max_chain;

  1077 

  1078     s->strstart = 0;

  1079     s->block_start = 0L;

  1080     s->lookahead = 0;

  1081     s->match_length = s->prev_length = MIN_MATCH-1;

  1082     s->match_available = 0;

  1083     s->ins_h = 0;

  1084 #ifndef FASTEST

  1085 #ifdef ASMV

  1086     match_init(); /* initialize the asm code */

  1087 #endif

  1088 #endif

  1089 }

  1090 

  1091 #ifndef FASTEST

  1092 /* ===========================================================================

  1093  * Set match_start to the longest match starting at the given string and

  1094  * return its length. Matches shorter or equal to prev_length are discarded,

  1095  * in which case the result is equal to prev_length and match_start is

  1096  * garbage.

  1097  * IN assertions: cur_match is the head of the hash chain for the current

  1098  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1

  1099  * OUT assertion: the match length is not greater than s->lookahead.

  1100  */

  1101 #ifndef ASMV

  1102 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or

  1103  * match.S. The code will be functionally equivalent.

  1104  */

  1105 #ifdef __SYMBIAN32__

  1106 local uInt longest_match(deflate_state * s,IPos  cur_match)

  1107 #else

  1108 local uInt longest_match(s, cur_match)

  1109     deflate_state *s;

  1110     IPos cur_match;                             /* current match */

  1111 #endif //__SYMBIAN32__

  1112 {

  1113     unsigned chain_length = s->max_chain_length;/* max hash chain length */

  1114     register Bytef *scan = s->window + s->strstart; /* current string */

  1115     register Bytef *match;                       /* matched string */

  1116     register int len;                           /* length of current match */

  1117     int best_len = s->prev_length;              /* best match length so far */

  1118     int nice_match = s->nice_match;             /* stop if match long enough */

  1119     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?

  1120         s->strstart - (IPos)MAX_DIST(s) : NIL;

  1121     /* Stop when cur_match becomes <= limit. To simplify the code,

  1122      * we prevent matches with the string of window index 0.

  1123      */

  1124     Posf *prev = s->prev;

  1125     uInt wmask = s->w_mask;

  1126 

  1127 #ifdef UNALIGNED_OK

  1128     /* Compare two bytes at a time. Note: this is not always beneficial.

  1129      * Try with and without -DUNALIGNED_OK to check.

  1130      */

  1131     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;

  1132     register ush scan_start = *(ushf*)scan;

  1133     register ush scan_end   = *(ushf*)(scan+best_len-1);

  1134 #else