55 " deflate 1.2.11 Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
91 # pragma message("Assembler code may have bugs -- use at your own risk")
92 void match_init
OF((
void));
111 # define TOO_FAR 4096
155 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
163 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
177 #define INSERT_STRING(s, str, match_head) \
178 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
179 match_head = s->head[s->ins_h], \
180 s->head[s->ins_h] = (Pos)(str))
182 #define INSERT_STRING(s, str, match_head) \
183 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
184 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
185 s->head[s->ins_h] = (Pos)(str))
192 #define CLEAR_HASH(s) \
193 s->head[s->hash_size-1] = NIL; \
194 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
212 *p = (
Pos)(m >= wsize ? m - wsize :
NIL);
219 *p = (
Pos)(m >= wsize ? m - wsize :
NIL);
241 version, stream_size)
260 if (version ==
Z_NULL || version[0] != my_version[0] ||
267 if (strm->zalloc == (alloc_func)0) {
275 if (strm->zfree == (free_func)0)
283 if (level != 0) level = 1;
288 if (windowBits < 0) {
290 windowBits = -windowBits;
293 else if (windowBits > 15) {
299 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
300 strategy < 0 || strategy >
Z_FIXED || (windowBits == 8 && wrap != 1)) {
303 if (windowBits == 8) windowBits = 9;
358 strm->zalloc == (alloc_func)0 ||
strm->zfree == (free_func)0)
378 const Bytef *dictionary;
400 if (dictLength >= s->
w_size) {
407 dictionary += dictLength - s->
w_size;
412 avail =
strm->avail_in;
413 next =
strm->next_in;
414 strm->avail_in = dictLength;
438 strm->next_in = next;
439 strm->avail_in = avail;
459 if (dictionary !=
Z_NULL && len)
476 strm->total_in =
strm->total_out = 0;
537 *bits =
strm->state->bi_valid;
584 if (level < 0 || level > 9 || strategy < 0 || strategy >
Z_FIXED) {
595 if (
strm->avail_out == 0)
657 uLong complen, wraplen;
660 complen = sourceLen +
661 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
674 wraplen = 6 + (s->
strstart ? 4 : 0);
682 wraplen += 2 + s->
gzhead->extra_len;
704 return complen + wraplen;
707 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
708 (sourceLen >> 25) + 13 - 6 + wraplen;
738 if (len >
strm->avail_out) len =
strm->avail_out;
739 if (len == 0)
return;
742 strm->next_out += len;
744 strm->total_out += len;
745 strm->avail_out -= len;
755 #define HCRC_UPDATE(beg) \
757 if (s->gzhead->hcrc && s->pending > (beg)) \
758 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
759 s->pending - (beg)); \
788 if (
strm->avail_out == 0) {
803 }
else if (
strm->avail_in == 0 &&
RANK(flush) <=
RANK(old_flush) &&
821 else if (s->
level < 6)
823 else if (s->
level == 6)
827 header |= (level_flags << 6);
829 header += 31 - (header % 31);
876 (s->
gzhead->hcrc ? 2 : 0) +
1009 if (
strm->avail_out == 0) {
1024 }
else if (flush !=
Z_BLOCK) {
1039 if (
strm->avail_out == 0) {
1130 ds->head = (
Posf *)
ZALLOC(dest, ds->hash_size,
sizeof(
Pos));
1131 overlay = (
ushf *)
ZALLOC(dest, ds->lit_bufsize,
sizeof(
ush)+2);
1132 ds->pending_buf = (
uchf *) overlay;
1135 ds->pending_buf ==
Z_NULL) {
1140 zmemcpy(ds->window, ss->window, ds->w_size * 2 *
sizeof(
Byte));
1143 zmemcpy(ds->pending_buf, ss->pending_buf, (
uInt)ds->pending_buf_size);
1145 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1146 ds->d_buf = overlay + ds->lit_bufsize/
sizeof(
ush);
1147 ds->l_buf = ds->pending_buf + (1+
sizeof(
ush))*ds->lit_bufsize;
1149 ds->l_desc.dyn_tree = ds->dyn_ltree;
1150 ds->d_desc.dyn_tree = ds->dyn_dtree;
1151 ds->bl_desc.dyn_tree = ds->bl_tree;
1169 unsigned len =
strm->avail_in;
1171 if (len > size) len = size;
1172 if (len == 0)
return 0;
1174 strm->avail_in -= len;
1177 if (
strm->state->wrap == 1) {
1181 else if (
strm->state->wrap == 2) {
1185 strm->next_in += len;
1186 strm->total_in += len;
1209 s->block_start = 0L;
1212 s->match_length = s->prev_length =
MIN_MATCH-1;
1213 s->match_available = 0;
1241 register Bytef *scan = s->window + s->strstart;
1242 register Bytef *match;
1244 int best_len = (int)s->prev_length;
1252 uInt wmask = s->w_mask;
1258 register Bytef *strend = s->window + s->strstart +
MAX_MATCH - 1;
1259 register ush scan_start = *(
ushf*)scan;
1260 register ush scan_end = *(
ushf*)(scan+best_len-1);
1263 register Byte scan_end1 = scan[best_len-1];
1264 register Byte scan_end = scan[best_len];
1273 if (s->prev_length >= s->good_match) {
1285 match = s->window + cur_match;
1295 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1299 if (*(
ushf*)(match+best_len-1) != scan_end ||
1300 *(
ushf*)match != scan_start)
continue;
1311 Assert(scan[2] == match[2],
"scan[2]?");
1314 }
while (*(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1315 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1316 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1317 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1322 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1323 if (*scan == *match) scan++;
1325 len = (
MAX_MATCH - 1) - (
int)(strend-scan);
1330 if (match[best_len] != scan_end ||
1331 match[best_len-1] != scan_end1 ||
1333 *++match != scan[1])
continue;
1342 Assert(*scan == *match,
"match[2]?");
1348 }
while (*++scan == *++match && *++scan == *++match &&
1349 *++scan == *++match && *++scan == *++match &&
1350 *++scan == *++match && *++scan == *++match &&
1351 *++scan == *++match && *++scan == *++match &&
1354 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1361 if (len > best_len) {
1362 s->match_start = cur_match;
1366 scan_end = *(
ushf*)(scan+best_len-1);
1368 scan_end1 = scan[best_len-1];
1369 scan_end = scan[best_len];
1372 }
while ((cur_match =
prev[cur_match & wmask]) > limit
1373 && --chain_length != 0);
1375 if ((
uInt)best_len <= s->lookahead)
return (
uInt)best_len;
1376 return s->lookahead;
1390 register Bytef *match;
1403 match = s->window + cur_match;
1407 if (match[0] != scan[0] || match[1] != scan[1])
return MIN_MATCH-1;
1415 scan += 2, match += 2;
1416 Assert(*scan == *match,
"match[2]?");
1422 }
while (*++scan == *++match && *++scan == *++match &&
1423 *++scan == *++match && *++scan == *++match &&
1424 *++scan == *++match && *++scan == *++match &&
1425 *++scan == *++match && *++scan == *++match &&
1428 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1434 s->match_start = cur_match;
1435 return (
uInt)len <= s->lookahead ? (
uInt)len : s->lookahead;
1454 if (
zmemcmp(s->window + match,
1455 s->window + start, length) != EQUAL) {
1456 fprintf(stderr,
" start %u, match %u, length %d\n",
1457 start, match, length);
1459 fprintf(stderr,
"%c%c", s->window[match++], s->window[start++]);
1460 }
while (--length != 0);
1461 z_error(
"invalid match");
1463 if (z_verbose > 1) {
1464 fprintf(stderr,
"\\[%d,%d]", start-match, length);
1465 do { putc(s->window[start++], stderr); }
while (--length != 0);
1469 # define check_match(s, start, match, length)
1492 more = (unsigned)(s->window_size -(
ulg)s->lookahead -(
ulg)s->strstart);
1495 if (
sizeof(
int) <= 2) {
1496 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1499 }
else if (more == (
unsigned)(-1)) {
1510 if (s->strstart >= wsize+
MAX_DIST(s)) {
1512 zmemcpy(s->window, s->window+wsize, (
unsigned)wsize - more);
1513 s->match_start -= wsize;
1514 s->strstart -= wsize;
1515 s->block_start -= (long) wsize;
1519 if (s->strm->avail_in == 0)
break;
1532 Assert(more >= 2,
"more < 2");
1534 n =
read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1538 if (s->lookahead + s->insert >=
MIN_MATCH) {
1539 uInt str = s->strstart - s->insert;
1540 s->ins_h = s->window[str];
1548 s->prev[str & s->w_mask] = s->head[s->ins_h];
1550 s->head[s->ins_h] = (
Pos)str;
1553 if (s->lookahead + s->insert <
MIN_MATCH)
1561 }
while (s->lookahead <
MIN_LOOKAHEAD && s->strm->avail_in != 0);
1570 if (s->high_water < s->window_size) {
1571 ulg curr = s->strstart + (
ulg)(s->lookahead);
1574 if (s->high_water < curr) {
1578 init = s->window_size - curr;
1581 zmemzero(s->window + curr, (
unsigned)init);
1582 s->high_water = curr + init;
1590 if (init > s->window_size - s->high_water)
1591 init = s->window_size - s->high_water;
1592 zmemzero(s->window + s->high_water, (
unsigned)init);
1593 s->high_water += init;
1598 "not enough room for search");
1605 #define FLUSH_BLOCK_ONLY(s, last) { \
1606 _tr_flush_block(s, (s->block_start >= 0L ? \
1607 (charf *)&s->window[(unsigned)s->block_start] : \
1609 (ulg)((long)s->strstart - s->block_start), \
1611 s->block_start = s->strstart; \
1612 flush_pending(s->strm); \
1613 Tracev((stderr,"[FLUSH]")); \
1617 #define FLUSH_BLOCK(s, last) { \
1618 FLUSH_BLOCK_ONLY(s, last); \
1619 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1623 #define MAX_STORED 65535
1626 #define MIN(a, b) ((a) > (b) ? (b) : (a))
1651 unsigned min_block =
MIN(s->pending_buf_size - 5, s->w_size);
1657 unsigned len, left, have, last = 0;
1658 unsigned used = s->strm->avail_in;
1665 have = (s->bi_valid + 42) >> 3;
1666 if (s->strm->avail_out < have)
1669 have = s->strm->avail_out - have;
1670 left = s->strstart - s->block_start;
1671 if (len > (
ulg)left + s->strm->avail_in)
1672 len = left + s->strm->avail_in;
1681 if (len < min_block && ((len == 0 && flush !=
Z_FINISH) ||
1683 len != left + s->strm->avail_in))
1689 last = flush ==
Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
1693 s->pending_buf[s->pending - 4] = len;
1694 s->pending_buf[s->pending - 3] = len >> 8;
1695 s->pending_buf[s->pending - 2] = ~len;
1696 s->pending_buf[s->pending - 1] = ~len >> 8;
1703 s->compressed_len += len << 3;
1704 s->bits_sent += len << 3;
1711 zmemcpy(s->strm->next_out, s->window + s->block_start, left);
1712 s->strm->next_out += left;
1713 s->strm->avail_out -= left;
1714 s->strm->total_out += left;
1715 s->block_start += left;
1723 read_buf(s->strm, s->strm->next_out, len);
1724 s->strm->next_out += len;
1725 s->strm->avail_out -= len;
1726 s->strm->total_out += len;
1728 }
while (last == 0);
1736 used -= s->strm->avail_in;
1741 if (used >= s->w_size) {
1743 zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
1744 s->strstart = s->w_size;
1747 if (s->window_size - s->strstart <= used) {
1749 s->strstart -= s->w_size;
1750 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1754 zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
1755 s->strstart += used;
1757 s->block_start = s->strstart;
1758 s->insert +=
MIN(used, s->w_size - s->insert);
1760 if (s->high_water < s->strstart)
1761 s->high_water = s->strstart;
1769 s->strm->avail_in == 0 && (
long)s->strstart == s->block_start)
1773 have = s->window_size - s->strstart - 1;
1774 if (s->strm->avail_in > have && s->block_start >= (
long)s->w_size) {
1776 s->block_start -= s->w_size;
1777 s->strstart -= s->w_size;
1778 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1783 if (have > s->strm->avail_in)
1784 have = s->strm->avail_in;
1786 read_buf(s->strm, s->window + s->strstart, have);
1787 s->strstart += have;
1789 if (s->high_water < s->strstart)
1790 s->high_water = s->strstart;
1797 have = (s->bi_valid + 42) >> 3;
1800 min_block =
MIN(have, s->w_size);
1801 left = s->strstart - s->block_start;
1802 if (left >= min_block ||
1804 s->strm->avail_in == 0 && left <= have)) {
1805 len =
MIN(left, have);
1806 last = flush ==
Z_FINISH && s->strm->avail_in == 0 &&
1807 len == left ? 1 : 0;
1809 s->block_start += len;
1842 if (s->lookahead == 0)
break;
1856 if (hash_head !=
NIL && s->strstart - hash_head <=
MAX_DIST(s)) {
1865 check_match(s, s->strstart, s->match_start, s->match_length);
1870 s->lookahead -= s->match_length;
1876 if (s->match_length <= s->max_insert_length &&
1885 }
while (--s->match_length != 0);
1890 s->strstart += s->match_length;
1891 s->match_length = 0;
1892 s->ins_h = s->window[s->strstart];
1893 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1903 Tracevv((stderr,
"%c", s->window[s->strstart]));
1945 if (s->lookahead == 0)
break;
1958 s->prev_length = s->match_length, s->prev_match = s->match_start;
1961 if (hash_head !=
NIL && s->prev_length < s->max_lazy_match &&
1962 s->strstart - hash_head <=
MAX_DIST(s)) {
1970 if (s->match_length <= 5 && (s->strategy ==
Z_FILTERED
1973 s->strstart - s->match_start >
TOO_FAR)
1986 if (s->prev_length >=
MIN_MATCH && s->match_length <= s->prev_length) {
1990 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
2000 s->lookahead -= s->prev_length-1;
2001 s->prev_length -= 2;
2003 if (++s->strstart <= max_insert) {
2006 }
while (--s->prev_length != 0);
2007 s->match_available = 0;
2013 }
else if (s->match_available) {
2018 Tracevv((stderr,
"%c", s->window[s->strstart-1]));
2025 if (s->strm->avail_out == 0)
return need_more;
2030 s->match_available = 1;
2036 if (s->match_available) {
2037 Tracevv((stderr,
"%c", s->window[s->strstart-1]));
2039 s->match_available = 0;
2063 Bytef *scan, *strend;
2075 if (s->lookahead == 0)
break;
2079 s->match_length = 0;
2080 if (s->lookahead >=
MIN_MATCH && s->strstart > 0) {
2081 scan = s->window + s->strstart - 1;
2083 if (
prev == *++scan &&
prev == *++scan &&
prev == *++scan) {
2084 strend = s->window + s->strstart +
MAX_MATCH;
2086 }
while (
prev == *++scan &&
prev == *++scan &&
2087 prev == *++scan &&
prev == *++scan &&
2088 prev == *++scan &&
prev == *++scan &&
2089 prev == *++scan &&
prev == *++scan &&
2092 if (s->match_length > s->lookahead)
2093 s->match_length = s->lookahead;
2100 check_match(s, s->strstart, s->strstart - 1, s->match_length);
2104 s->lookahead -= s->match_length;
2105 s->strstart += s->match_length;
2106 s->match_length = 0;
2109 Tracevv((stderr,
"%c", s->window[s->strstart]));
2138 if (s->lookahead == 0) {
2140 if (s->lookahead == 0) {
2148 s->match_length = 0;
2149 Tracevv((stderr,
"%c", s->window[s->strstart]));