54 " deflate 1.2.11 Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
90 # pragma message("Assembler code may have bugs -- use at your own risk")
91 void match_init
OF((
void));
110 # define TOO_FAR 4096
154 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
162 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
176 #define INSERT_STRING(s, str, match_head) \
177 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
178 match_head = s->head[s->ins_h], \
179 s->head[s->ins_h] = (Pos)(str))
181 #define INSERT_STRING(s, str, match_head) \
182 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
183 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
184 s->head[s->ins_h] = (Pos)(str))
191 #define CLEAR_HASH(s) \
192 s->head[s->hash_size-1] = NIL; \
193 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
205 uInt wsize = s->w_size;
211 *p = (
Pos)(m >= wsize ? m - wsize :
NIL);
218 *p = (
Pos)(m >= wsize ? m - wsize :
NIL);
239 int ZEXPORT
deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
259 if (version ==
Z_NULL || version[0] != my_version[0] ||
266 if (strm->zalloc == (alloc_func)0) {
271 strm->opaque = (voidpf)0;
274 if (strm->zfree == (free_func)0)
282 if (level != 0) level = 1;
287 if (windowBits < 0) {
289 windowBits = -windowBits;
292 else if (windowBits > 15) {
297 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method !=
Z_DEFLATED ||
298 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
299 strategy < 0 || strategy >
Z_FIXED || (windowBits == 8 && wrap != 1)) {
302 if (windowBits == 8) windowBits = 9;
311 s->
w_bits = (uInt)windowBits;
357 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)
377 const Bytef *dictionary;
384 z_const
unsigned char *next;
395 strm->adler =
adler32(strm->adler, dictionary, dictLength);
399 if (dictLength >= s->
w_size) {
406 dictionary += dictLength - s->
w_size;
411 avail = strm->avail_in;
412 next = strm->next_in;
413 strm->avail_in = dictLength;
414 strm->next_in = (z_const Bytef *)dictionary;
437 strm->next_in = next;
438 strm->avail_in = avail;
458 if (dictionary !=
Z_NULL && len)
475 strm->total_in = strm->total_out = 0;
522 strm->state->gzhead =
head;
534 *pending = strm->state->pending;
536 *bits = strm->state->bi_valid;
579 if (level != 0) level = 1;
583 if (level < 0 || level > 9 || strategy < 0 || strategy >
Z_FIXED) {
586 func = configuration_table[s->
level].func;
588 if ((strategy != s->
strategy || func != configuration_table[level].func) &&
594 if (strm->avail_out == 0)
597 if (s->
level != level) {
616 int ZEXPORT
deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
656 uLong complen, wraplen;
659 complen = sourceLen +
660 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
673 wraplen = 6 + (s->
strstart ? 4 : 0);
681 wraplen += 2 + s->
gzhead->extra_len;
703 return complen + wraplen;
706 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
707 (sourceLen >> 25) + 13 - 6 + wraplen;
737 if (len > strm->avail_out) len = strm->avail_out;
738 if (len == 0)
return;
741 strm->next_out +=
len;
743 strm->total_out +=
len;
744 strm->avail_out -=
len;
754 #define HCRC_UPDATE(beg) \
756 if (s->gzhead->hcrc && s->pending > (beg)) \
757 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
758 s->pending - (beg)); \
774 if (strm->next_out ==
Z_NULL ||
775 (strm->avail_in != 0 && strm->next_in ==
Z_NULL) ||
787 if (strm->avail_out == 0) {
802 }
else if (strm->avail_in == 0 &&
RANK(flush) <=
RANK(old_flush) &&
820 else if (s->
level < 6)
822 else if (s->
level == 6)
826 header |= (level_flags << 6);
828 header += 31 - (header % 31);
875 (s->
gzhead->hcrc ? 2 : 0) +
978 put_byte(s, (Byte)(strm->adler & 0xff));
979 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
995 if (strm->avail_in != 0 || s->
lookahead != 0 ||
1002 (*(configuration_table[s->
level].func))(
s, flush);
1008 if (strm->avail_out == 0) {
1023 }
else if (flush !=
Z_BLOCK) {
1038 if (strm->avail_out == 0) {
1051 put_byte(s, (Byte)(strm->adler & 0xff));
1052 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1053 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
1054 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
1055 put_byte(s, (Byte)(strm->total_in & 0xff));
1056 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
1057 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
1058 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
1082 status = strm->state->status;
1085 TRY_FREE(strm, strm->state->pending_buf);
1088 TRY_FREE(strm, strm->state->window);
1090 ZFREE(strm, strm->state);
1127 ds->window = (Bytef *)
ZALLOC(dest, ds->w_size, 2*
sizeof(Byte));
1129 ds->head = (
Posf *)
ZALLOC(dest, ds->hash_size,
sizeof(
Pos));
1130 overlay = (
ushf *)
ZALLOC(dest, ds->lit_bufsize,
sizeof(
ush)+2);
1131 ds->pending_buf = (
uchf *) overlay;
1134 ds->pending_buf ==
Z_NULL) {
1139 zmemcpy(ds->window, ss->window, ds->w_size * 2 *
sizeof(Byte));
1140 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size *
sizeof(
Pos));
1141 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size *
sizeof(
Pos));
1142 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1144 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1145 ds->d_buf = overlay + ds->lit_bufsize/
sizeof(
ush);
1146 ds->l_buf = ds->pending_buf + (1+
sizeof(
ush))*ds->lit_bufsize;
1148 ds->l_desc.dyn_tree = ds->dyn_ltree;
1149 ds->d_desc.dyn_tree = ds->dyn_dtree;
1150 ds->bl_desc.dyn_tree = ds->bl_tree;
1168 unsigned len = strm->avail_in;
1170 if (len > size) len = size;
1171 if (len == 0)
return 0;
1173 strm->avail_in -=
len;
1175 zmemcpy(buf, strm->next_in, len);
1176 if (strm->state->wrap == 1) {
1177 strm->adler =
adler32(strm->adler, buf, len);
1180 else if (strm->state->wrap == 2) {
1181 strm->adler =
crc32(strm->adler, buf, len);
1184 strm->next_in +=
len;
1185 strm->total_in +=
len;
1202 s->max_lazy_match = configuration_table[s->level].max_lazy;
1203 s->good_match = configuration_table[s->level].good_length;
1204 s->nice_match = configuration_table[s->level].nice_length;
1205 s->max_chain_length = configuration_table[s->level].max_chain;
1208 s->block_start = 0
L;
1211 s->match_length = s->prev_length =
MIN_MATCH-1;
1212 s->match_available = 0;
1240 register Bytef *scan = s->window + s->strstart;
1241 register Bytef *match;
1243 int best_len = (
int)s->prev_length;
1251 uInt wmask = s->w_mask;
1257 register Bytef *strend = s->window + s->strstart +
MAX_MATCH - 1;
1258 register ush scan_start = *(
ushf*)scan;
1259 register ush scan_end = *(
ushf*)(scan+best_len-1);
1261 register Bytef *strend = s->window + s->strstart +
MAX_MATCH;
1262 register Byte scan_end1 = scan[best_len-1];
1263 register Byte scan_end = scan[best_len];
1272 if (s->prev_length >= s->good_match) {
1284 match = s->window + cur_match;
1294 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1298 if (*(
ushf*)(match+best_len-1) != scan_end ||
1299 *(
ushf*)match != scan_start)
continue;
1310 Assert(scan[2] == match[2],
"scan[2]?");
1313 }
while (*(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1314 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1315 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1316 *(
ushf*)(scan+=2) == *(
ushf*)(match+=2) &&
1321 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1322 if (*scan == *match) scan++;
1324 len = (
MAX_MATCH - 1) - (
int)(strend-scan);
1329 if (match[best_len] != scan_end ||
1330 match[best_len-1] != scan_end1 ||
1332 *++match != scan[1])
continue;
1341 Assert(*scan == *match,
"match[2]?");
1347 }
while (*++scan == *++match && *++scan == *++match &&
1348 *++scan == *++match && *++scan == *++match &&
1349 *++scan == *++match && *++scan == *++match &&
1350 *++scan == *++match && *++scan == *++match &&
1353 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1360 if (len > best_len) {
1361 s->match_start = cur_match;
1365 scan_end = *(
ushf*)(scan+best_len-1);
1367 scan_end1 = scan[best_len-1];
1368 scan_end = scan[best_len];
1371 }
while ((cur_match = prev[cur_match & wmask]) > limit
1372 && --chain_length != 0);
1374 if ((uInt)best_len <= s->lookahead)
return (uInt)best_len;
1375 return s->lookahead;
1388 register Bytef *scan = s->
window + s->strstart;
1389 register Bytef *match;
1391 register Bytef *strend = s->window + s->strstart +
MAX_MATCH;
1402 match = s->window + cur_match;
1406 if (match[0] != scan[0] || match[1] != scan[1])
return MIN_MATCH-1;
1414 scan += 2, match += 2;
1415 Assert(*scan == *match,
"match[2]?");
1421 }
while (*++scan == *++match && *++scan == *++match &&
1422 *++scan == *++match && *++scan == *++match &&
1423 *++scan == *++match && *++scan == *++match &&
1424 *++scan == *++match && *++scan == *++match &&
1427 Assert(scan <= s->
window+(
unsigned)(s->window_size-1),
"wild scan");
1433 s->match_start = cur_match;
1434 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1453 if (
zmemcmp(s->window + match,
1454 s->window + start, length) != EQUAL) {
1455 fprintf(stderr,
" start %u, match %u, length %d\n",
1456 start, match, length);
1458 fprintf(stderr,
"%c%c", s->window[match++], s->window[start++]);
1459 }
while (--length != 0);
1460 z_error(
"invalid match");
1462 if (z_verbose > 1) {
1463 fprintf(stderr,
"\\[%d,%d]", start-match, length);
1464 do { putc(s->window[start++], stderr); }
while (--length != 0);
1468 # define check_match(s, start, match, length)
1486 uInt wsize = s->w_size;
1491 more = (unsigned)(s->window_size -(
ulg)s->lookahead -(
ulg)s->strstart);
1494 if (
sizeof(
int) <= 2) {
1495 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1498 }
else if (more == (
unsigned)(-1)) {
1509 if (s->strstart >= wsize+
MAX_DIST(s)) {
1511 zmemcpy(s->window, s->window+wsize, (
unsigned)wsize - more);
1512 s->match_start -= wsize;
1513 s->strstart -= wsize;
1514 s->block_start -= (long) wsize;
1518 if (s->strm->avail_in == 0)
break;
1531 Assert(more >= 2,
"more < 2");
1533 n =
read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1537 if (s->lookahead + s->insert >=
MIN_MATCH) {
1538 uInt str = s->strstart - s->insert;
1539 s->ins_h = s->window[str];
1547 s->prev[str & s->w_mask] = s->head[s->ins_h];
1549 s->head[s->ins_h] = (
Pos)str;
1552 if (s->lookahead + s->insert <
MIN_MATCH)
1560 }
while (s->lookahead <
MIN_LOOKAHEAD && s->strm->avail_in != 0);
1569 if (s->high_water < s->window_size) {
1570 ulg curr = s->strstart + (
ulg)(s->lookahead);
1573 if (s->high_water < curr) {
1577 init = s->window_size - curr;
1580 zmemzero(s->window + curr, (
unsigned)init);
1581 s->high_water = curr +
init;
1589 if (init > s->window_size - s->high_water)
1590 init = s->window_size - s->high_water;
1591 zmemzero(s->window + s->high_water, (
unsigned)init);
1592 s->high_water +=
init;
1597 "not enough room for search");
1604 #define FLUSH_BLOCK_ONLY(s, last) { \
1605 _tr_flush_block(s, (s->block_start >= 0L ? \
1606 (charf *)&s->window[(unsigned)s->block_start] : \
1608 (ulg)((long)s->strstart - s->block_start), \
1610 s->block_start = s->strstart; \
1611 flush_pending(s->strm); \
1612 Tracev((stderr,"[FLUSH]")); \
1616 #define FLUSH_BLOCK(s, last) { \
1617 FLUSH_BLOCK_ONLY(s, last); \
1618 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1622 #define MAX_STORED 65535
1625 #define MIN(a, b) ((a) > (b) ? (b) : (a))
1650 unsigned min_block =
MIN(s->pending_buf_size - 5, s->w_size);
1656 unsigned len,
left, have, last = 0;
1657 unsigned used = s->strm->avail_in;
1664 have = (s->bi_valid + 42) >> 3;
1665 if (s->strm->avail_out < have)
1668 have = s->strm->avail_out - have;
1669 left = s->strstart - s->block_start;
1670 if (len > (
ulg)left + s->strm->avail_in)
1671 len = left + s->strm->avail_in;
1680 if (len < min_block && ((len == 0 && flush !=
Z_FINISH) ||
1682 len != left + s->strm->avail_in))
1688 last = flush ==
Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
1692 s->pending_buf[s->pending - 4] =
len;
1693 s->pending_buf[s->pending - 3] = len >> 8;
1694 s->pending_buf[s->pending - 2] = ~len;
1695 s->pending_buf[s->pending - 1] = ~len >> 8;
1702 s->compressed_len += len << 3;
1703 s->bits_sent += len << 3;
1710 zmemcpy(s->strm->next_out, s->window + s->block_start, left);
1711 s->strm->next_out +=
left;
1712 s->strm->avail_out -=
left;
1713 s->strm->total_out +=
left;
1714 s->block_start +=
left;
1722 read_buf(s->strm, s->strm->next_out, len);
1723 s->strm->next_out +=
len;
1724 s->strm->avail_out -=
len;
1725 s->strm->total_out +=
len;
1727 }
while (last == 0);
1735 used -= s->strm->avail_in;
1740 if (used >= s->w_size) {
1742 zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
1743 s->strstart = s->w_size;
1746 if (s->window_size - s->strstart <= used) {
1748 s->strstart -= s->w_size;
1749 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1753 zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
1754 s->strstart += used;
1756 s->block_start = s->strstart;
1757 s->insert +=
MIN(used, s->w_size - s->insert);
1759 if (s->high_water < s->strstart)
1760 s->high_water = s->strstart;
1768 s->strm->avail_in == 0 && (
long)s->strstart == s->block_start)
1772 have = s->window_size - s->strstart - 1;
1773 if (s->strm->avail_in > have && s->block_start >= (
long)s->w_size) {
1775 s->block_start -= s->w_size;
1776 s->strstart -= s->w_size;
1777 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1782 if (have > s->strm->avail_in)
1783 have = s->strm->avail_in;
1785 read_buf(s->strm, s->window + s->strstart, have);
1786 s->strstart += have;
1788 if (s->high_water < s->strstart)
1789 s->high_water = s->strstart;
1796 have = (s->bi_valid + 42) >> 3;
1799 min_block =
MIN(have, s->w_size);
1800 left = s->strstart - s->block_start;
1801 if (left >= min_block ||
1803 s->strm->avail_in == 0 && left <= have)) {
1804 len =
MIN(left, have);
1805 last = flush ==
Z_FINISH && s->strm->avail_in == 0 &&
1806 len == left ? 1 : 0;
1808 s->block_start +=
len;
1841 if (s->lookahead == 0)
break;
1855 if (hash_head !=
NIL && s->strstart - hash_head <=
MAX_DIST(s)) {
1864 check_match(s, s->strstart, s->match_start, s->match_length);
1869 s->lookahead -= s->match_length;
1875 if (s->match_length <= s->max_insert_length &&
1884 }
while (--s->match_length != 0);
1889 s->strstart += s->match_length;
1890 s->match_length = 0;
1891 s->ins_h = s->window[s->strstart];
1892 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1902 Tracevv((stderr,
"%c", s->window[s->strstart]));
1944 if (s->lookahead == 0)
break;
1957 s->prev_length = s->match_length, s->prev_match = s->match_start;
1960 if (hash_head !=
NIL && s->prev_length < s->max_lazy_match &&
1961 s->strstart - hash_head <=
MAX_DIST(s)) {
1969 if (s->match_length <= 5 && (s->strategy ==
Z_FILTERED
1972 s->strstart - s->match_start >
TOO_FAR)
1985 if (s->prev_length >=
MIN_MATCH && s->match_length <= s->prev_length) {
1986 uInt max_insert = s->strstart + s->lookahead -
MIN_MATCH;
1989 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1999 s->lookahead -= s->prev_length-1;
2000 s->prev_length -= 2;
2002 if (++s->strstart <= max_insert) {
2005 }
while (--s->prev_length != 0);
2006 s->match_available = 0;
2012 }
else if (s->match_available) {
2017 Tracevv((stderr,
"%c", s->window[s->strstart-1]));
2024 if (s->strm->avail_out == 0)
return need_more;
2029 s->match_available = 1;
2035 if (s->match_available) {
2036 Tracevv((stderr,
"%c", s->window[s->strstart-1]));
2038 s->match_available = 0;
2062 Bytef *scan, *strend;
2074 if (s->lookahead == 0)
break;
2078 s->match_length = 0;
2079 if (s->lookahead >=
MIN_MATCH && s->strstart > 0) {
2080 scan = s->window + s->strstart - 1;
2082 if (prev == *++scan && prev == *++scan && prev == *++scan) {
2083 strend = s->window + s->strstart +
MAX_MATCH;
2085 }
while (prev == *++scan && prev == *++scan &&
2086 prev == *++scan && prev == *++scan &&
2087 prev == *++scan && prev == *++scan &&
2088 prev == *++scan && prev == *++scan &&
2090 s->match_length =
MAX_MATCH - (uInt)(strend - scan);
2091 if (s->match_length > s->lookahead)
2092 s->match_length = s->lookahead;
2094 Assert(scan <= s->
window+(uInt)(s->window_size-1),
"wild scan");
2099 check_match(s, s->strstart, s->strstart - 1, s->match_length);
2103 s->lookahead -= s->match_length;
2104 s->strstart += s->match_length;
2105 s->match_length = 0;
2108 Tracevv((stderr,
"%c", s->window[s->strstart]));
2137 if (s->lookahead == 0) {
2139 if (s->lookahead == 0) {
2147 s->match_length = 0;
2148 Tracevv((stderr,
"%c", s->window[s->strstart]));