Lines Matching refs:s
269 #define TRY_FREE(s, p) {if (p) ZFREE(s, p); } argument
566 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c); } argument
575 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) argument
582 void _tr_init OF((deflate_state *s));
583 int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));
584 void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
586 void _tr_align OF((deflate_state *s));
587 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
605 #define _tr_tally_lit(s, c, flush) \ argument
607 s->d_buf[s->last_lit] = 0; \
608 s->l_buf[s->last_lit++] = cc; \
609 s->dyn_ltree[cc].Freq++; \
610 flush = (s->last_lit == s->lit_bufsize-1); \
612 #define _tr_tally_dist(s, distance, length, flush) \ argument
615 s->d_buf[s->last_lit] = dist; \
616 s->l_buf[s->last_lit++] = len; \
618 s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
619 s->dyn_dtree[d_code(dist)].Freq++; \
620 flush = (s->last_lit == s->lit_bufsize-1); \
623 #define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) argument
624 #define _tr_tally_dist(s, distance, length, flush) \ argument
625 flush = _tr_tally(s, distance, length)
708 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
711 local void fill_window OF((deflate_state *s));
712 local block_state deflate_stored OF((deflate_state *s, int flush));
713 local block_state deflate_fast OF((deflate_state *s, int flush));
714 local block_state deflate_slow OF((deflate_state *s, int flush));
715 local void lm_init OF((deflate_state *s));
716 local void putShortMSB OF((deflate_state *s, uInt b));
721 uInt longest_match OF((deflate_state *s, IPos cur_match));
723 local uInt longest_match OF((deflate_state *s, IPos cur_match));
727 local void check_match OF((deflate_state *s, IPos start, IPos match,
798 #define UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) argument
813 #define INSERT_STRING(s, str, match_head) \ argument
814 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
815 match_head = s->head[s->ins_h], \
816 s->head[s->ins_h] = (Pos)(str))
818 #define INSERT_STRING(s, str, match_head) \ argument
819 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
820 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
821 s->head[s->ins_h] = (Pos)(str))
829 #define CLEAR_HASH(s) \ argument
830 s->head[s->hash_size-1] = NIL; \
831 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head));
859 deflate_state *s; local
900 s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state));
901 if (s == Z_NULL)
903 strm->state = (struct internal_state FAR *)s;
904 s->strm = strm;
906 s->noheader = noheader;
907 s->w_bits = windowBits;
908 s->w_size = 1 << s->w_bits;
909 s->w_mask = s->w_size - 1;
911 s->hash_bits = memLevel + 7;
912 s->hash_size = 1 << s->hash_bits;
913 s->hash_mask = s->hash_size - 1;
914 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
916 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte));
917 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof (Pos));
918 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof (Pos));
920 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
922 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2);
923 s->pending_buf = (uchf *) overlay;
924 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L);
926 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
927 s->pending_buf == Z_NULL) {
929 s->status = INIT_STATE;
933 s->d_buf = overlay + s->lit_bufsize/sizeof (ush);
934 s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize;
936 s->level = level;
937 s->strategy = strategy;
938 s->method = (Byte)method;
950 deflate_state *s; local
958 s = (deflate_state *) strm->state;
959 if (s->status != INIT_STATE)
966 if (length > MAX_DIST(s)) {
967 length = MAX_DIST(s);
973 Assert(length <= s->window_size, "dict copy");
974 zmemcpy(s->window, dictionary, length);
975 s->strstart = length;
976 s->block_start = (long)length;
983 s->ins_h = s->window[0];
984 UPDATE_HASH(s, s->ins_h, s->window[1]);
986 INSERT_STRING(s, n, hash_head);
997 deflate_state *s; local
1008 s = (deflate_state *)strm->state;
1009 s->pending = 0;
1010 s->pending_out = s->pending_buf;
1012 if (s->noheader < 0) {
1014 s->noheader = 0;
1016 s->status = s->noheader ? BUSY_STATE : INIT_STATE;
1018 s->last_flush = Z_NO_FLUSH;
1020 _tr_init(s);
1021 lm_init(s);
1033 deflate_state *s; local
1039 s = (deflate_state *) strm->state;
1048 func = configuration_table[s->level].func;
1054 if (s->level != level) {
1055 s->level = level;
1056 s->max_lazy_match = configuration_table[level].max_lazy;
1057 s->good_match = configuration_table[level].good_length;
1058 s->nice_match = configuration_table[level].nice_length;
1059 s->max_chain_length = configuration_table[level].max_chain;
1061 s->strategy = strategy;
1072 putShortMSB(s, b) in putShortMSB() argument
1073 deflate_state *s; in putShortMSB()
1076 put_byte(s, (Byte)(b >> 8));
1077 put_byte(s, (Byte)(b & 0xff));
1091 deflate_state *s = (deflate_state *) strm->state; local
1092 unsigned len = s->pending;
1099 zmemcpy(strm->next_out, s->pending_out, len);
1102 s->pending_out += len;
1105 s->pending -= len;
1106 if (s->pending == 0) {
1107 s->pending_out = s->pending_buf;
1118 deflate_state *s; local
1124 s = (deflate_state *) strm->state;
1128 (s->status == FINISH_STATE && flush != Z_FINISH)) {
1133 s->strm = strm; /* just in case */
1134 old_flush = s->last_flush;
1135 s->last_flush = flush;
1138 if (s->status == INIT_STATE) {
1140 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
1141 uInt level_flags = (s->level-1) >> 1;
1145 if (s->strstart != 0) header |= PRESET_DICT;
1148 s->status = BUSY_STATE;
1149 putShortMSB(s, header);
1152 if (s->strstart != 0) {
1153 putShortMSB(s, (uInt)(strm->adler >> 16));
1154 putShortMSB(s, (uInt)(strm->adler & 0xffff));
1160 if (s->pending != 0) {
1172 s->last_flush = -1;
1188 if (s->status == FINISH_STATE && strm->avail_in != 0) {
1193 if (strm->avail_in != 0 || s->lookahead != 0 ||
1194 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
1197 bstate = (*(configuration_table[s->level].func))(s, flush);
1200 s->status = FINISH_STATE;
1205 s->last_flush = -1;
1221 _tr_align(s);
1228 _tr_stored_type_only(s); /* PPP */
1230 _tr_stored_block(s, (char *)0, 0L, 0);
1237 CLEAR_HASH(s); /* forget history */
1243 s->last_flush = -1;
1252 if (s->noheader)
1256 putShortMSB(s, (uInt)(strm->adler >> 16));
1257 putShortMSB(s, (uInt)(strm->adler & 0xffff));
1263 s->noheader = -1; /* write the trailer only once! */
1264 return (s->pending != 0 ? Z_OK : Z_STREAM_END);
1273 deflate_state *s; local
1277 s = (deflate_state *) strm->state;
1279 status = s->status;
1286 TRY_FREE(strm, s->pending_buf);
1287 TRY_FREE(strm, s->head);
1288 TRY_FREE(strm, s->prev);
1289 TRY_FREE(strm, s->window);
1291 ZFREE(strm, s);
1410 lm_init(s) in lm_init() argument
1411 deflate_state *s; in lm_init()
1413 s->window_size = (ulg)2L*s->w_size;
1415 CLEAR_HASH(s);
1418 s->max_lazy_match = configuration_table[s->level].max_lazy;
1419 s->good_match = configuration_table[s->level].good_length;
1420 s->nice_match = configuration_table[s->level].nice_length;
1421 s->max_chain_length = configuration_table[s->level].max_chain;
1423 s->strstart = 0;
1424 s->block_start = 0L;
1425 s->lookahead = 0;
1426 s->match_length = s->prev_length = MIN_MATCH-1;
1427 s->match_available = 0;
1428 s->ins_h = 0;
1451 longest_match(s, cur_match) in longest_match() argument
1452 deflate_state *s; in longest_match()
1456 unsigned chain_length = s->max_chain_length;
1457 register Bytef *scan = s->window + s->strstart; /* current string */
1460 int best_len = s->prev_length; /* best match length so far */
1461 int nice_match = s->nice_match; /* stop if match long enough */
1462 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1463 s->strstart - (IPos)MAX_DIST(s) : NIL;
1468 Posf *prev = s->prev;
1469 uInt wmask = s->w_mask;
1476 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1480 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1490 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1493 if (s->prev_length >= s->good_match) {
1500 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
1502 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
1506 Assert(cur_match <= s->strstart, "no future");
1507 match = s->window + cur_match;
1546 Assert(scan <= s->window+(unsigned)(s->window_size-1),
1584 Assert(scan <= s->window+(unsigned)(s->window_size-1),
1593 s->match_start = cur_match;
1606 if ((uInt)best_len <= s->lookahead)
1608 return (s->lookahead);
1616 longest_match(s, cur_match) in longest_match() argument
1617 deflate_state *s; in longest_match()
1620 register Bytef *scan = s->window + s->strstart; /* current string */
1623 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1630 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1632 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
1635 Assert(cur_match <= s->strstart, "no future");
1637 match = s->window + cur_match;
1664 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1671 s->match_start = cur_match;
1672 return (len <= s->lookahead ? len : s->lookahead);
1683 check_match(s, start, match, length) in check_match() argument
1684 deflate_state *s; in check_match()
1689 if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) {
1693 fprintf(stderr, "%c%c", s->window[match++],
1694 s->window[start++]);
1700 do { putc(s->window[start++], stderr); } while (--length != 0);
1704 #define check_match(s, start, match, length) argument
1719 fill_window(s) in fill_window() argument
1720 deflate_state *s; in fill_window()
1725 uInt wsize = s->w_size;
1728 more = (unsigned)(s->window_size -(ulg)s->lookahead -
1729 (ulg)s->strstart);
1732 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1749 } else if (s->strstart >= wsize+MAX_DIST(s)) {
1751 Assert(wsize+wsize <= s->window_size, "wsize*2");
1752 zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
1753 s->match_start -= wsize;
1755 s->strstart -= wsize;
1756 s->block_start -= (long)wsize;
1768 n = s->hash_size;
1769 p = &s->head[n];
1777 p = &s->prev[n];
1790 if (s->strm->avail_in == 0)
1810 Assert(s->strstart + s->lookahead + more <= s->window_size,
1813 n = read_buf(s->strm, s->window + s->strstart + s->lookahead,
1815 s->lookahead += n;
1818 if (s->lookahead >= MIN_MATCH) {
1819 s->ins_h = s->window[s->strstart];
1820 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1831 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1839 #define FLUSH_BLOCK_ONLY(s, eof) { \ argument
1840 _tr_flush_block(s, (s->block_start >= 0L ? \
1841 (charf *)&s->window[(unsigned)s->block_start] : \
1843 (ulg)((long)s->strstart - s->block_start), \
1845 s->block_start = s->strstart; \
1846 flush_pending(s->strm); \
1851 #define FLUSH_BLOCK(s, eof) { \ argument
1852 FLUSH_BLOCK_ONLY(s, eof); \
1853 if (s->strm->avail_out == 0) \
1868 deflate_stored(s, flush) in deflate_stored() argument
1869 deflate_state *s; in deflate_stored()
1880 if (max_block_size > s->pending_buf_size - 5) {
1881 max_block_size = s->pending_buf_size - 5;
1887 if (s->lookahead <= 1) {
1889 Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1890 s->block_start >= (long)s->w_size,
1893 fill_window(s);
1894 if (s->lookahead == 0 && flush == Z_NO_FLUSH)
1897 if (s->lookahead == 0)
1900 Assert(s->block_start >= 0L, "block gone");
1902 s->strstart += s->lookahead;
1903 s->lookahead = 0;
1906 max_start = s->block_start + max_block_size;
1907 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1912 s->lookahead = (uInt)(s->strstart - max_start);
1913 s->strstart = (uInt)max_start;
1914 FLUSH_BLOCK(s, 0);
1921 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1922 FLUSH_BLOCK(s, 0);
1925 FLUSH_BLOCK(s, flush == Z_FINISH);
1938 deflate_fast(s, flush) in deflate_fast() argument
1939 deflate_state *s; in deflate_fast()
1953 if (s->lookahead < MIN_LOOKAHEAD) {
1954 fill_window(s);
1955 if (s->lookahead < MIN_LOOKAHEAD &&
1959 if (s->lookahead == 0)
1968 if (s->lookahead >= MIN_MATCH) {
1969 INSERT_STRING(s, s->strstart, hash_head);
1977 if (hash_head != NIL && s->strstart - hash_head <=
1978 MAX_DIST(s)) {
1986 if (s->strategy != Z_HUFFMAN_ONLY) {
1987 s->match_length = longest_match(s, hash_head);
1991 if (s->match_length >= MIN_MATCH) {
1992 check_match(s, s->strstart, s->match_start,
1993 s->match_length);
1995 _tr_tally_dist(s, s->strstart - s->match_start,
1996 s->match_length - MIN_MATCH, bflush);
1998 s->lookahead -= s->match_length;
2006 if (s->match_length <= s->max_insert_length &&
2007 s->lookahead >= MIN_MATCH) {
2009 s->match_length--;
2011 s->strstart++;
2012 INSERT_STRING(s, s->strstart,
2020 } while (--s->match_length != 0);
2021 s->strstart++;
2025 s->strstart += s->match_length;
2026 s->match_length = 0;
2027 s->ins_h = s->window[s->strstart];
2028 UPDATE_HASH(s, s->ins_h,
2029 s->window[s->strstart+1]);
2042 Tracevv((stderr, "%c", s->window[s->strstart]));
2043 _tr_tally_lit(s, s->window[s->strstart], bflush);
2044 s->lookahead--;
2045 s->strstart++;
2047 if (bflush) FLUSH_BLOCK(s, 0);
2049 FLUSH_BLOCK(s, flush == Z_FINISH);
2060 deflate_slow(s, flush) in deflate_slow() argument
2061 deflate_state *s; in deflate_slow()
2076 if (s->lookahead < MIN_LOOKAHEAD) {
2077 fill_window(s);
2078 if (s->lookahead < MIN_LOOKAHEAD &&
2083 if (s->lookahead == 0)
2092 if (s->lookahead >= MIN_MATCH) {
2093 INSERT_STRING(s, s->strstart, hash_head);
2100 s->prev_length = s->match_length;
2101 s->prev_match = s->match_start;
2102 s->match_length = MIN_MATCH-1;
2104 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
2105 s->strstart - hash_head <= MAX_DIST(s)) {
2113 if (s->strategy != Z_HUFFMAN_ONLY) {
2114 s->match_length = longest_match(s, hash_head);
2118 if (s->match_length <= 5 &&
2119 (s->strategy == Z_FILTERED ||
2120 (s->match_length == MIN_MATCH &&
2121 s->strstart - s->match_start > TOO_FAR))) {
2128 s->match_length = MIN_MATCH-1;
2136 if (s->prev_length >= MIN_MATCH &&
2137 s->match_length <= s->prev_length) {
2138 uInt max_insert = s->strstart + s->lookahead -
2142 check_match(s, s->strstart-1, s->prev_match,
2143 s->prev_length);
2145 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
2146 s->prev_length - MIN_MATCH, bflush);
2155 s->lookahead -= s->prev_length-1;
2156 s->prev_length -= 2;
2158 if (++s->strstart <= max_insert) {
2159 INSERT_STRING(s, s->strstart,
2162 } while (--s->prev_length != 0);
2163 s->match_available = 0;
2164 s->match_length = MIN_MATCH-1;
2165 s->strstart++;
2167 if (bflush) FLUSH_BLOCK(s, 0);
2169 } else if (s->match_available) {
2177 Tracevv((stderr, "%c", s->window[s->strstart-1]));
2178 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
2180 FLUSH_BLOCK_ONLY(s, 0);
2182 s->strstart++;
2183 s->lookahead--;
2184 if (s->strm->avail_out == 0)
2191 s->match_available = 1;
2192 s->strstart++;
2193 s->lookahead--;
2197 if (s->match_available) {
2198 Tracevv((stderr, "%c", s->window[s->strstart-1]));
2199 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
2200 s->match_available = 0;
2202 FLUSH_BLOCK(s, flush == Z_FINISH);
2356 local void init_block OF((deflate_state *s));
2357 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
2358 local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
2360 local void build_tree OF((deflate_state *s, tree_desc *desc));
2361 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
2362 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
2363 local int build_bl_tree OF((deflate_state *s));
2364 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
2366 local void compress_block OF((deflate_state *s, ct_data *ltree,
2368 local void set_data_type OF((deflate_state *s));
2370 local void bi_windup OF((deflate_state *s));
2371 local void bi_flush OF((deflate_state *s));
2372 local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
2376 #define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) argument
2380 #define send_code(s, c, tree) \ argument
2382 send_bits(s, tree[c].Code, tree[c].Len); }
2390 #define put_short(s, w) { \ argument
2391 put_byte(s, (uch)((w) & 0xff)); \
2392 put_byte(s, (uch)((ush)(w) >> 8)); \
2401 local void send_bits OF((deflate_state *s, int value, int length));
2404 send_bits(s, value, length) in send_bits() argument
2405 deflate_state *s; in send_bits()
2411 s->bits_sent += (ulg)length;
2418 if (s->bi_valid > (int)Buf_size - length) {
2419 s->bi_buf |= (value << s->bi_valid);
2420 put_short(s, s->bi_buf);
2421 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
2422 s->bi_valid += length - Buf_size;
2424 s->bi_buf |= value << s->bi_valid;
2425 s->bi_valid += length;
2430 #define send_bits(s, value, length) \ argument
2432 if (s->bi_valid > (int)Buf_size - len) {\
2434 s->bi_buf |= (val << s->bi_valid); \
2435 put_short(s, s->bi_buf); \
2436 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); \
2437 s->bi_valid += len - Buf_size; \
2439 s->bi_buf |= (value) << s->bi_valid; \
2440 s->bi_valid += len; \
2539 _tr_init(s) in _tr_init() argument
2540 deflate_state *s; in _tr_init()
2544 s->l_desc.dyn_tree = s->dyn_ltree;
2545 s->l_desc.stat_desc = &static_l_desc;
2547 s->d_desc.dyn_tree = s->dyn_dtree;
2548 s->d_desc.stat_desc = &static_d_desc;
2550 s->bl_desc.dyn_tree = s->bl_tree;
2551 s->bl_desc.stat_desc = &static_bl_desc;
2553 s->bi_buf = 0;
2554 s->bi_valid = 0;
2555 s->last_eob_len = 8; /* enough lookahead for inflate */
2556 s->compressed_len = 0L; /* PPP */
2558 s->bits_sent = 0L;
2562 init_block(s);
2570 init_block(s) in init_block() argument
2571 deflate_state *s; in init_block()
2576 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
2577 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
2578 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
2580 s->dyn_ltree[END_BLOCK].Freq = 1;
2581 s->opt_len = s->static_len = 0L;
2582 s->last_lit = s->matches = 0;
2594 #define pqremove(s, tree, top) \ argument
2596 top = s->heap[SMALLEST]; \
2597 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
2598 pqdownheap(s, tree, SMALLEST); \
2617 pqdownheap(s, tree, k) in pqdownheap() argument
2618 deflate_state *s; in pqdownheap()
2622 int v = s->heap[k];
2624 while (j <= s->heap_len) {
2626 if (j < s->heap_len &&
2627 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
2631 if (smaller(tree, v, s->heap[j], s->depth)) break;
2634 s->heap[k] = s->heap[j]; k = j;
2639 s->heap[k] = v;
2654 gen_bitlen(s, desc) in gen_bitlen() argument
2655 deflate_state *s; in gen_bitlen()
2672 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
2678 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
2680 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
2681 n = s->heap[h];
2689 s->bl_count[bits]++;
2693 s->opt_len += (ulg)f * (bits + xbits);
2694 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
2705 while (s->bl_count[bits] == 0) bits--;
2706 s->bl_count[bits]--; /* move one leaf down the tree */
2708 s->bl_count[bits+1] += 2;
2709 s->bl_count[max_length]--;
2726 n = s->bl_count[bits];
2728 m = s->heap[--h];
2733 s->opt_len += ((long)bits - (long)tree[m].Len)
2801 build_tree(s, desc) in build_tree() argument
2802 deflate_state *s; in build_tree()
2817 s->heap_len = 0, s->heap_max = HEAP_SIZE;
2821 s->heap[++(s->heap_len)] = max_code = n;
2822 s->depth[n] = 0;
2834 while (s->heap_len < 2) {
2835 node = s->heap[++(s->heap_len)] = (max_code < 2 ?
2838 s->depth[node] = 0;
2839 s->opt_len--; if (stree) s->static_len -= stree[node].Len;
2848 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2856 pqremove(s, tree, n); /* n = node of least frequency */
2857 m = s->heap[SMALLEST]; /* m = node of next least frequency */
2860 s->heap[--(s->heap_max)] = n;
2861 s->heap[--(s->heap_max)] = m;
2865 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
2868 if (tree == s->bl_tree) {
2875 s->heap[SMALLEST] = node++;
2876 pqdownheap(s, tree, SMALLEST);
2878 } while (s->heap_len >= 2);
2880 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
2886 gen_bitlen(s, (tree_desc *)desc);
2889 gen_codes((ct_data *)tree, max_code, s->bl_count);
2898 scan_tree(s, tree, max_code) in scan_tree() argument
2899 deflate_state *s; in scan_tree()
2919 s->bl_tree[curlen].Freq += count;
2921 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
2922 s->bl_tree[REP_3_6].Freq++;
2924 s->bl_tree[REPZ_3_10].Freq++;
2926 s->bl_tree[REPZ_11_138].Freq++;
2945 send_tree(s, tree, max_code) in send_tree() argument
2946 deflate_state *s; in send_tree()
2966 do { send_code(s, curlen, s->bl_tree); }
2971 send_code(s, curlen, s->bl_tree); count--;
2974 send_code(s, REP_3_6, s->bl_tree);
2975 send_bits(s, count-3, 2);
2978 send_code(s, REPZ_3_10, s->bl_tree);
2979 send_bits(s, count-3, 3);
2982 send_code(s, REPZ_11_138, s->bl_tree);
2983 send_bits(s, count-11, 7);
3002 build_bl_tree(s) in build_bl_tree() argument
3003 deflate_state *s; in build_bl_tree()
3012 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
3013 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
3016 build_tree(s, (tree_desc *)(&(s->bl_desc)));
3029 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
3032 s->opt_len += 3*(max_blindex+1) + 5+5+4;
3034 s->opt_len, s->static_len));
3046 send_all_trees(s, lcodes, dcodes, blcodes) in send_all_trees() argument
3047 deflate_state *s; in send_all_trees()
3057 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
3058 send_bits(s, dcodes-1, 5);
3059 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
3062 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
3065 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
3069 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
3071 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
3075 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
3077 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
3086 _tr_stored_block(s, buf, stored_len, eof) in _tr_stored_block() argument
3087 deflate_state *s; in _tr_stored_block()
3092 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
3093 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; /* PPP */
3094 s->compressed_len += (stored_len + 4) << 3; /* PPP */
3096 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
3104 _tr_stored_type_only(s) in _tr_stored_type_only() argument
3105 deflate_state *s; in _tr_stored_type_only()
3107 send_bits(s, (STORED_BLOCK << 1), 3);
3108 bi_windup(s);
3109 s->compressed_len = (s->compressed_len + 3) & ~7L; /* PPP */
3126 _tr_align(s) in _tr_align() argument
3127 deflate_state *s; in _tr_align()
3129 send_bits(s, STATIC_TREES<<1, 3);
3130 send_code(s, END_BLOCK, static_ltree);
3131 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
3132 bi_flush(s);
3140 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
3141 send_bits(s, STATIC_TREES<<1, 3);
3142 send_code(s, END_BLOCK, static_ltree);
3143 s->compressed_len += 10L;
3144 bi_flush(s);
3146 s->last_eob_len = 7;
3155 _tr_flush_block(s, buf, stored_len, eof) in _tr_flush_block() argument
3156 deflate_state *s; in _tr_flush_block()
3166 if (s->level > 0) {
3169 if (s->data_type == Z_UNKNOWN) set_data_type(s);
3172 build_tree(s, (tree_desc *)(&(s->l_desc)));
3173 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
3174 s->static_len));
3176 build_tree(s, (tree_desc *)(&(s->d_desc)));
3177 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
3178 s->static_len));
3190 max_blindex = build_bl_tree(s);
3196 opt_lenb = (s->opt_len+3+7)>>3;
3197 static_lenb = (s->static_len+3+7)>>3;
3201 opt_lenb, s->opt_len, static_lenb, s->static_len,
3202 stored_len, s->last_lit));
3219 #define FRC_STR_COND eof && s->compressed_len == 0L /* force stored file */
3222 s->compressed_len == 0L && seekable()
3233 copy_block(s, buf, (unsigned)stored_len, 0);
3234 s->compressed_len = stored_len << 3;
3235 s->method = STORED;
3256 _tr_stored_block(s, buf, stored_len, eof);
3264 send_bits(s, (STATIC_TREES<<1)+eof, 3);
3265 compress_block(s, (ct_data *)static_ltree,
3267 s->compressed_len += 3 + s->static_len; /* PPP */
3269 send_bits(s, (DYN_TREES<<1)+eof, 3);
3270 send_all_trees(s, s->l_desc.max_code+1,
3271 s->d_desc.max_code+1,
3273 compress_block(s, (ct_data *)s->dyn_ltree,
3274 (ct_data *)s->dyn_dtree);
3275 s->compressed_len += 3 + s->opt_len; /* PPP */
3278 Assert(s->compressed_len == s->bits_sent, "bad compressed size");
3284 init_block(s);
3287 bi_windup(s);
3288 s->compressed_len += 7; /* align on byte boundary PPP */
3290 Tracev((stderr, "\ncomprlen %lu(%lu) ", s->compressed_len>>3,
3291 s->compressed_len-7*eof));
3302 _tr_tally(s, dist, lc) in _tr_tally() argument
3303 deflate_state *s; in _tr_tally()
3308 s->d_buf[s->last_lit] = (ush)dist;
3309 s->l_buf[s->last_lit++] = (uch)lc;
3312 s->dyn_ltree[lc].Freq++;
3314 s->matches++;
3317 Assert((ush)dist < (ush)MAX_DIST(s) &&
3321 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
3322 s->dyn_dtree[d_code(dist)].Freq++;
3327 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
3329 ulg out_length = (ulg)s->last_lit*8L;
3330 ulg in_length = (ulg)((long)s->strstart - s->block_start);
3333 out_length += (ulg)s->dyn_dtree[dcode].Freq *
3338 s->last_lit, in_length, out_length,
3340 if (s->matches < s->last_lit/2 && out_length < in_length/2)
3344 return (s->last_lit == s->lit_bufsize-1);
3357 compress_block(s, ltree, dtree) in compress_block() argument
3358 deflate_state *s; in compress_block()
3368 if (s->last_lit != 0) do {
3369 dist = s->d_buf[lx];
3370 lc = s->l_buf[lx++];
3373 send_code(s, lc, ltree);
3379 send_code(s, code+LITERALS+1, ltree);
3384 send_bits(s, lc, extra);
3392 send_code(s, code, dtree);
3397 send_bits(s, dist, extra);
3405 Assert(s->pending < s->lit_bufsize + 2*lx,
3408 } while (lx < s->last_lit);
3410 send_code(s, END_BLOCK, ltree);
3411 s->last_eob_len = ltree[END_BLOCK].Len;
3422 set_data_type(s) in set_data_type() argument
3423 deflate_state *s; in set_data_type()
3428 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
3429 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
3430 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
3431 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ?
3459 bi_flush(s) in bi_flush() argument
3460 deflate_state *s; in bi_flush()
3462 if (s->bi_valid == 16) {
3463 put_short(s, s->bi_buf);
3464 s->bi_buf = 0;
3465 s->bi_valid = 0;
3466 } else if (s->bi_valid >= 8) {
3467 put_byte(s, (Byte)s->bi_buf);
3468 s->bi_buf >>= 8;
3469 s->bi_valid -= 8;
3478 bi_windup(s) in bi_windup() argument
3479 deflate_state *s; in bi_windup()
3481 if (s->bi_valid > 8) {
3482 put_short(s, s->bi_buf);
3483 } else if (s->bi_valid > 0) {
3484 put_byte(s, (Byte)s->bi_buf);
3486 s->bi_buf = 0;
3487 s->bi_valid = 0;
3489 s->bits_sent = (s->bits_sent+7) & ~7;
3499 copy_block(s, buf, len, header) in copy_block() argument
3500 deflate_state *s; in copy_block()
3505 bi_windup(s); /* align on byte boundary */
3506 s->last_eob_len = 8; /* enough lookahead for inflate */
3509 put_short(s, (ush)len);
3510 put_short(s, (ush)~len);
3512 s->bits_sent += 2*16;
3516 s->bits_sent += (ulg)len<<3;
3519 Assert(s->pending + len < s->pending_buf_size, "pending_buf overrun");
3520 zmemcpy(&s->pending_buf[s->pending], buf, len); /* PPP */
3521 s->pending += len; /* PPP */
3570 inflate_blocks_statef *s,
3575 inflate_blocks_statef *s));
4198 #define UPDBITS {s->bitb = b; s->bitk = k; }
4200 #define UPDOUT {s->write = q; }
4202 #define LEAVE {UPDATE return (inflate_flush(s, z, r)); }
4204 #define LOADIN {p = z->next_in; n = z->avail_in; b = s->bitb; k = s->bitk; }
4211 #define WAVAIL (uInt)(q < s->read ? s->read-q-1 : s->end-q)
4212 #define LOADOUT {q = s->write; m = (uInt)WAVAIL; }
4213 #define WWRAP {if (q == s->end && s->read != s->window) {q = s->window; \
4215 #define FLUSH {UPDOUT r = inflate_flush(s, z, r); LOADOUT}
4293 inflate_blocks_reset(s, z, c) in inflate_blocks_reset() argument
4294 inflate_blocks_statef *s; in inflate_blocks_reset()
4299 *c = s->check;
4300 if ((s->mode == BTREE || s->mode == DTREE) &&
4301 s->sub.trees.blens != Z_NULL) {
4302 ZFREE(z, s->sub.trees.blens);
4303 s->sub.trees.blens = Z_NULL;
4305 if (s->mode == CODES && s->sub.decode.codes != Z_NULL) {
4306 (void) inflate_codes_free(s->sub.decode.codes, z);
4307 s->sub.decode.codes = Z_NULL;
4309 s->mode = TYPE;
4310 s->bitk = 0;
4311 s->bitb = 0;
4312 s->read = s->write = s->window;
4313 if (s->checkfn != Z_NULL)
4314 z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
4324 inflate_blocks_statef *s; local
4326 if ((s = (inflate_blocks_statef *)ZALLOC
4328 return (s);
4329 s->hufts = (inflate_huft *)ZALLOC(z, MANY, sizeof (inflate_huft));
4330 if (s->hufts == Z_NULL) {
4331 ZFREE(z, s);
4334 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
4336 ZFREE(z, s->hufts);
4337 ZFREE(z, s);
4340 s->end = s->window + w;
4341 s->checkfn = c;
4342 s->mode = TYPE;
4344 inflate_blocks_reset(s, z, Z_NULL);
4345 return (s);
4350 inflate_blocks(s, z, r) in inflate_blocks() argument
4351 inflate_blocks_statef *s; in inflate_blocks()
4369 switch (s->mode)
4374 s->last = t & 1;
4379 s->last ? " (last)" : ""));
4383 s->mode = LENS; /* get length of stored block */
4387 s->last ? " (last)" : ""));
4394 s->sub.decode.codes = inflate_codes_new(bl,
4396 if (s->sub.decode.codes == Z_NULL)
4403 s->mode = CODES;
4407 s->last ? " (last)" : ""));
4409 s->mode = TABLE;
4413 s->mode = BADB;
4423 s->mode = BADB;
4428 s->sub.left = (uInt)b & 0xffff;
4431 s->sub.left));
4432 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
4438 t = s->sub.left;
4444 if ((s->sub.left -= t) != 0)
4448 z->total_out + (q >= s->read ? q - s->read :
4449 (s->end - s->read) + (q - s->window))));
4450 s->mode = s->last ? DRY : TYPE;
4454 s->sub.trees.table = t = (uInt)b & 0x3fff;
4458 s->mode = BADB;
4467 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t,
4474 s->sub.trees.index = 0;
4476 s->mode = BTREE;
4479 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
4482 s->sub.trees.blens[border[s->sub.trees.index++]] =
4486 while (s->sub.trees.index < 19)
4487 s->sub.trees.blens[border[s->sub.trees.index++]] =
4489 s->sub.trees.bb = 7;
4490 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
4491 &s->sub.trees.tb, s->hufts, z);
4494 ZFREE(z, s->sub.trees.blens);
4495 s->sub.trees.blens = Z_NULL;
4498 s->mode = BADB;
4501 s->sub.trees.index = 0;
4503 s->mode = DTREE;
4506 while (t = s->sub.trees.table,
4507 s->sub.trees.index < 258 + (t & 0x1f) +
4513 t = s->sub.trees.bb;
4515 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
4521 s->sub.trees.blens[s->sub.trees.index++] =
4530 i = s->sub.trees.index;
4531 t = s->sub.trees.table;
4536 ZFREE(z, s->sub.trees.blens);
4537 s->sub.trees.blens = Z_NULL;
4538 s->mode = BADB;
4543 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
4545 s->sub.trees.blens[i++] = c;
4547 s->sub.trees.index = i;
4550 s->sub.trees.tb = Z_NULL;
4560 t = s->sub.trees.table;
4563 s->sub.trees.blens, &bl, &bd, &tl, &td,
4564 s->hufts, z);
4565 ZFREE(z, s->sub.trees.blens);
4566 s->sub.trees.blens = Z_NULL;
4570 s->mode = BADB;
4581 s->sub.decode.codes = c;
4583 s->mode = CODES;
4587 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
4588 return (inflate_flush(s, z, r));
4590 (void) inflate_codes_free(s->sub.decode.codes, z);
4593 z->total_out + (q >= s->read ? q - s->read :
4594 (s->end - s->read) + (q - s->window))));
4595 if (!s->last)
4597 s->mode = TYPE;
4600 s->mode = DRY;
4604 if (s->read != s->write)
4606 s->mode = DONEB;
4624 inflate_blocks_free(s, z) in inflate_blocks_free() argument
4625 inflate_blocks_statef *s; in inflate_blocks_free()
4628 inflate_blocks_reset(s, z, Z_NULL);
4629 ZFREE(z, s->window);
4630 s->window = Z_NULL;
4631 ZFREE(z, s->hufts);
4632 s->hufts = Z_NULL;
4633 ZFREE(z, s);
4640 inflate_set_dictionary(s, d, n) in inflate_set_dictionary() argument
4641 inflate_blocks_statef *s; in inflate_set_dictionary()
4645 Assert(s->window + n <= s->end, "set dict");
4646 zmemcpy((charf *)s->window, d, n);
4647 s->read = s->write = s->window + n;
4656 inflate_blocks_sync_point(s) in inflate_blocks_sync_point() argument
4657 inflate_blocks_statef *s; in inflate_blocks_sync_point()
4659 return (s->mode == LENS);
4671 inflate_addhistory(s, z) in inflate_addhistory() argument
4672 inflate_blocks_statef *s; in inflate_addhistory()
4683 if (s->read != s->write)
4685 if (s->mode != TYPE)
4699 if (s->checkfn != Z_NULL)
4700 s->check = (*s->checkfn)(s->check, q, t);
4706 s->read = q; /* drag read pointer forward */
4708 if (q == s->end) {
4709 s->read = q = s->window;
4723 inflate_packet_flush(s) in inflate_packet_flush() argument
4724 inflate_blocks_statef *s; in inflate_packet_flush()
4726 if (s->mode != LENS)
4728 s->mode = TYPE;
4830 huft_build(b, n, s, d, e, t, m, hp, hn, v) in huft_build() argument
4833 uInt s; /* number of simple-valued codes (0..s-1) */
5024 else if (*p < s)
5034 r.exop = (Byte)(e[*p - s] + 16 + 64);
5035 r.base = d[*p++ - s];
5325 inflate_codes(s, z, r) in inflate_codes() argument
5326 inflate_blocks_statef *s; in inflate_codes()
5340 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
5356 c->ltree, c->dtree, s, z);
5452 f = (uInt)(q - s->window) < c->sub.copy.dist ?
5453 s->end - (c->sub.copy.dist - (q - s->window)) :
5457 if ((uInt)(q - s->window) < c->sub.copy.dist)
5458 f = s->end - (c->sub.copy.dist -
5459 (uInt)(q - s->window));
5465 if (f == s->end)
5466 f = s->window;
5485 if (s->read != s->write)
5541 inflate_flush(s, z, r) in inflate_flush() argument
5542 inflate_blocks_statef *s; in inflate_flush()
5552 q = s->read;
5555 n = (uInt)((q <= s->write ? s->write : s->end) - q);
5564 if (s->checkfn != Z_NULL)
5565 z->adler = s->check = (*s->checkfn)(s->check, q, n);
5575 if (q == s->end)
5578 q = s->window;
5579 if (s->write == s->end)
5580 s->write = s->window;
5583 n = (uInt)(s->write - q);
5592 if (s->checkfn != Z_NULL)
5593 z->adler = s->check = (*s->checkfn)(s->check, q, n);
5605 s->read = q;
5647 inflate_fast(bl, bd, tl, td, s, z) in inflate_fast() argument
5651 inflate_blocks_statef *s;
5723 if ((uInt)(q - s->window) >= d)
5741 s->window);
5743 r = s->end - e;
5754 r = s->window;