~alex-sergeyev/htmldoc/trunk : revision 593

1

/* deflate.c -- compress data using the deflation algorithm

2

3

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

4

*/

5

52

#include "deflate.h"

53

54

const char deflate_copyright[] =

55

56

/*

57

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

58

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

79

#ifndef FASTEST

80

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

81

#endif

82

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

83

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

82

84

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

83

85

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

84

86

local void flush_pending OF((z_streamp strm));

85

87

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

86

#ifndef FASTEST

87

88

#ifdef ASMV

88

89

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

89

90

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

90

91

#else

91

92

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

92

93

#endif

93

#endif

94

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

95

94

96

95

#ifdef DEBUG

97

96

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

110

109

#endif

111

110

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

112

111

113

#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)

114

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

115

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

116

*/

117

118

112

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

119

113

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

120

114

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

288

282

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

289

283

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

290

284

285

s->high_water = 0; /* nothing written to s->window yet */

286

291

287

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

292

288

293

289

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

332

328

strm->adler = adler32(strm->adler, dictionary, dictLength);

333

329

334

330

if (length < MIN_MATCH) return Z_OK;

335

if (length > MAX_DIST(s)) {

336

length = MAX_DIST(s);

331

if (length > s->w_size) {

332

length = s->w_size;

337

333

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

338

334

}

339

335

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

435

431

}

436

432

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

437

433

438

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

434

if ((strategy != s->strategy || func != configuration_table[level].func) &&

435

strm->total_in != 0) {

439

436

/* Flush the last buffer: */

440

err = deflate(strm, Z_PARTIAL_FLUSH);

437

err = deflate(strm, Z_BLOCK);

441

438

}

442

439

if (s->level != level) {

443

440

s->level = level;

481

478

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

482

479

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

483

480

*

484

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

485

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

486

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

487

* seem onerous for output buffer allocation.

481

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

482

* every combination of windowBits and memLevel. But even the conservative

483

* upper bound of about 14% expansion does not seem onerous for output buffer

484

* allocation.

488

485

*/

489

486

uLong ZEXPORT deflateBound(strm, sourceLen)

490

487

z_streamp strm;

491

488

uLong sourceLen;

492

489

{

493

490

deflate_state *s;

494

uLong destLen;

495

496

/* conservative upper bound */

497

destLen = sourceLen +

498

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

499

500

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

491

uLong complen, wraplen;

492

Bytef *str;

493

494

/* conservative upper bound for compressed data */

495

complen = sourceLen +

496

((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;

497

498

/* if can't get parameters, return conservative bound plus zlib wrapper */

501

499

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

502

return destLen;

500

return complen + 6;

501

502

/* compute wrapper length */

503

s = strm->state;

504

switch (s->wrap) {

505

case 0: /* raw deflate */

506

wraplen = 0;

507

break;

508

case 1: /* zlib wrapper */

509

wraplen = 6 + (s->strstart ? 4 : 0);

510

break;

511

case 2: /* gzip wrapper */

512

wraplen = 18;

513

if (s->gzhead != Z_NULL) { /* user-supplied gzip header */

514

if (s->gzhead->extra != Z_NULL)

515

wraplen += 2 + s->gzhead->extra_len;

516

str = s->gzhead->name;

517

if (str != Z_NULL)

518

do {

519

wraplen++;

520

} while (*str++);

521

str = s->gzhead->comment;

522

if (str != Z_NULL)

523

do {

524

wraplen++;

525

} while (*str++);

526

if (s->gzhead->hcrc)

527

wraplen += 2;

528

}

529

break;

530

default: /* for compiler happiness */

531

wraplen = 6;

532

}

503

533

504

534

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

505

s = strm->state;

506

535

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

507

return destLen;

536

return complen + wraplen;

508

537

509

538

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

510

return compressBound(sourceLen);

539

return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +

540

(sourceLen >> 25) + 13 - 6 + wraplen;

511

541

}

512

542

513

543

/* =========================================================================

557

587

deflate_state *s;

558

588

559

589

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

560

flush > Z_FINISH || flush < 0) {

590

flush > Z_BLOCK || flush < 0) {

561

591

return Z_STREAM_ERROR;

562

592

}

563

593

s = strm->state;

581

611

put_byte(s, 31);

582

612

put_byte(s, 139);

583

613

put_byte(s, 8);

584

if (s->gzhead == NULL) {

614

if (s->gzhead == Z_NULL) {

585

615

put_byte(s, 0);

586

616

put_byte(s, 0);

587

617

put_byte(s, 0);

608

638

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

609

639

4 : 0));

610

640

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

611

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

641

if (s->gzhead->extra != Z_NULL) {

612

642

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

613

643

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

614

644

}

650

680

}

651

681

#ifdef GZIP

652

682

if (s->status == EXTRA_STATE) {

653

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

683

if (s->gzhead->extra != Z_NULL) {

654

684

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

655

685

656

686

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

678

708

s->status = NAME_STATE;

679

709

}

680

710

if (s->status == NAME_STATE) {

681

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

711

if (s->gzhead->name != Z_NULL) {

682

712

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

683

713

int val;

684

714

709

739

s->status = COMMENT_STATE;

710

740

}

711

741

if (s->status == COMMENT_STATE) {

712

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

742

if (s->gzhead->comment != Z_NULL) {

713

743

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

714

744

int val;

715

745

787

817

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

788

818

block_state bstate;

789

819

790

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

820

bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :

821

(s->strategy == Z_RLE ? deflate_rle(s, flush) :

822

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

791

823

792

824

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

793

825

s->status = FINISH_STATE;

808

840

if (bstate == block_done) {

809

841

if (flush == Z_PARTIAL_FLUSH) {

810

842

_tr_align(s);

811

} else { /* FULL_FLUSH or SYNC_FLUSH */

843

} else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */

812

844

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

813

845

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

814

846

* as a special marker by inflate_sync().

815

847

*/

816

848

if (flush == Z_FULL_FLUSH) {

817

849

CLEAR_HASH(s); /* forget history */

850

if (s->lookahead == 0) {

851

s->strstart = 0;

852

s->block_start = 0L;

853

}

818

854

}

819

855

}

820

856

flush_pending(strm);

1167

1203

return s->lookahead;

1168

1204

}

1169

1205

#endif /* ASMV */

1170

#endif /* FASTEST */

1206

1207

#else /* FASTEST */

1171

1208

1172

1209

/* ---------------------------------------------------------------------------

1173

* Optimized version for level == 1 or strategy == Z_RLE only

1210

* Optimized version for FASTEST only

1174

1211

*/

1175

local uInt longest_match_fast(s, cur_match)

1212

local uInt longest_match(s, cur_match)

1176

1213

deflate_state *s;

1177

1214

IPos cur_match; /* current match */

1178

1215

{

1225

1262

return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;

1226

1263

}

1227

1264

1265

#endif /* FASTEST */

1266

1228

1267

#ifdef DEBUG

1229

1268

/* ===========================================================================

1230

1269

* Check that the match at match_start is indeed a match.

1303

1342

later. (Using level 0 permanently is not an optimal usage of

1304

1343

zlib, so we don't care about this pathological case.)

1305

1344

*/

1306

/* %%% avoid this when Z_RLE */

1307

1345

n = s->hash_size;

1308

1346

p = &s->head[n];

1309

1347

do {

1355

1393

*/

1356

1394

1357

1395

} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);

1396

1397

/* If the WIN_INIT bytes after the end of the current data have never been

1398

* written, then zero those bytes in order to avoid memory check reports of

1399

* the use of uninitialized (or uninitialised as Julian writes) bytes by

1400

* the longest match routines. Update the high water mark for the next

1401

* time through here. WIN_INIT is set to MAX_MATCH since the longest match

1402

* routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.

1403

*/

1404

if (s->high_water < s->window_size) {

1405

ulg curr = s->strstart + (ulg)(s->lookahead);

1406

ulg init;

1407

1408

if (s->high_water < curr) {

1409

/* Previous high water mark below current data -- zero WIN_INIT

1410

* bytes or up to end of window, whichever is less.

1411

*/

1412

init = s->window_size - curr;

1413

if (init > WIN_INIT)

1414

init = WIN_INIT;

1415

zmemzero(s->window + curr, (unsigned)init);

1416

s->high_water = curr + init;

1417

}

1418

else if (s->high_water < (ulg)curr + WIN_INIT) {

1419

/* High water mark at or above current data, but below current data

1420

* plus WIN_INIT -- zero out to current data plus WIN_INIT, or up

1421

* to end of window, whichever is less.

1422

*/

1423

init = (ulg)curr + WIN_INIT - s->high_water;

1424

if (init > s->window_size - s->high_water)

1425

init = s->window_size - s->high_water;

1426

zmemzero(s->window + s->high_water, (unsigned)init);

1427

s->high_water += init;

1428

}

1429

}

1358

1430

}

1359

1431

1360

1432

/* ===========================================================================

1361

1433

* Flush the current block, with given end-of-file flag.

1362

1434

* IN assertion: strstart is set to the end of the current match.

1363

1435

*/

1364

#define FLUSH_BLOCK_ONLY(s, eof) { \

1436

#define FLUSH_BLOCK_ONLY(s, last) { \

1365

1437

_tr_flush_block(s, (s->block_start >= 0L ? \

1366

1438

(charf *)&s->window[(unsigned)s->block_start] : \

1367

1439

(charf *)Z_NULL), \

1368

1440

(ulg)((long)s->strstart - s->block_start), \

1369

(eof)); \

1441

(last)); \

1370

1442

s->block_start = s->strstart; \

1371

1443

flush_pending(s->strm); \

1372

1444

Tracev((stderr,"[FLUSH]")); \

1373

1445

}

1374

1446

1375

1447

/* Same but force premature exit if necessary. */

1376

#define FLUSH_BLOCK(s, eof) { \

1377

FLUSH_BLOCK_ONLY(s, eof); \

1378

if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \

1448

#define FLUSH_BLOCK(s, last) { \

1449

FLUSH_BLOCK_ONLY(s, last); \

1450

if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \

1379

1451

}

1380

1452

1381

1453

/* ===========================================================================

1449

1521

deflate_state *s;

1450

1522

int flush;

1451

1523

{

1452

IPos hash_head = NIL; /* head of the hash chain */

1524

IPos hash_head; /* head of the hash chain */

1453

1525

int bflush; /* set if current block must be flushed */

1454

1526

1455

1527

for (;;) {

1469

1541

/* Insert the string window[strstart .. strstart+2] in the

1470

1542

* dictionary, and set hash_head to the head of the hash chain:

1471

1543

*/

1544

hash_head = NIL;

1472

1545

if (s->lookahead >= MIN_MATCH) {

1473

1546

INSERT_STRING(s, s->strstart, hash_head);

1474

1547

}

1481

1554

* of window index 0 (in particular we have to avoid a match

1482

1555

* of the string with itself at the start of the input file).

1483

1556

*/

1484

#ifdef FASTEST

1485

if ((s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) ||

1486

(s->strategy == Z_RLE && s->strstart - hash_head == 1)) {

1487

s->match_length = longest_match_fast (s, hash_head);

1488

}

1489

#else

1490

if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) {

1491

s->match_length = longest_match (s, hash_head);

1492

} else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {

1493

s->match_length = longest_match_fast (s, hash_head);

1494

}

1495

#endif

1496

/* longest_match() or longest_match_fast() sets match_start */

1557

s->match_length = longest_match (s, hash_head);

1558

/* longest_match() sets match_start */

1497

1559

}

1498

1560

if (s->match_length >= MIN_MATCH) {

1499

1561

check_match(s, s->strstart, s->match_start, s->match_length);

1555

1617

deflate_state *s;

1556

1618

int flush;

1557

1619

{

1558

IPos hash_head = NIL; /* head of hash chain */

1620

IPos hash_head; /* head of hash chain */

1559

1621

int bflush; /* set if current block must be flushed */

1560

1622

1561

1623

/* Process the input block. */

1576

1638

/* Insert the string window[strstart .. strstart+2] in the

1577

1639

* dictionary, and set hash_head to the head of the hash chain:

1578

1640

*/

1641

hash_head = NIL;

1579

1642

if (s->lookahead >= MIN_MATCH) {

1580

1643

INSERT_STRING(s, s->strstart, hash_head);

1581

1644

}

1591

1654

* of window index 0 (in particular we have to avoid a match

1592

1655

* of the string with itself at the start of the input file).

1593

1656

*/

1594

if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) {

1595

s->match_length = longest_match (s, hash_head);

1596

} else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {

1597

s->match_length = longest_match_fast (s, hash_head);

1598

}

1599

/* longest_match() or longest_match_fast() sets match_start */

1657

s->match_length = longest_match (s, hash_head);

1658

/* longest_match() sets match_start */

1600

1659

1601

1660

if (s->match_length <= 5 && (s->strategy == Z_FILTERED

1602

1661

#if TOO_FAR <= 32767

1674

1733

}

1675

1734

#endif /* FASTEST */

1676

1735

1677

#if 0

1678

1736

/* ===========================================================================

1679

1737

* For Z_RLE, simply look for runs of bytes, generate matches only of distance

1680

1738

* one. Do not maintain a hash table. (It will be regenerated if this run of

1684

1742

deflate_state *s;

1685

1743

int flush;

1686

1744

{

1687

int bflush; /* set if current block must be flushed */

1688

uInt run; /* length of run */

1689

uInt max; /* maximum length of run */

1690

uInt prev; /* byte at distance one to match */

1691

Bytef *scan; /* scan for end of run */

1745

int bflush; /* set if current block must be flushed */

1746

uInt prev; /* byte at distance one to match */

1747

Bytef *scan, *strend; /* scan goes up to strend for length of run */

1692

1748

1693

1749

for (;;) {

1694

1750

/* Make sure that we always have enough lookahead, except

1704

1760

}

1705

1761

1706

1762

/* See how many times the previous byte repeats */

1707

run = 0;

1708

if (s->strstart > 0) { /* if there is a previous byte, that is */

1709

max = s->lookahead < MAX_MATCH ? s->lookahead : MAX_MATCH;

1763

s->match_length = 0;

1764

if (s->lookahead >= MIN_MATCH && s->strstart > 0) {

1710

1765

scan = s->window + s->strstart - 1;

1711

prev = *scan++;

1712

do {

1713

if (*scan++ != prev)

1714

break;

1715

} while (++run < max);

1766

prev = *scan;

1767

if (prev == *++scan && prev == *++scan && prev == *++scan) {

1768

strend = s->window + s->strstart + MAX_MATCH;

1769

do {

1770

} while (prev == *++scan && prev == *++scan &&

1771

prev == *++scan && prev == *++scan &&

1772

prev == *++scan && prev == *++scan &&

1773

prev == *++scan && prev == *++scan &&

1774

scan < strend);

1775

s->match_length = MAX_MATCH - (int)(strend - scan);

1776

if (s->match_length > s->lookahead)

1777

s->match_length = s->lookahead;

1778

}

1716

1779

}

1717

1780

1718

1781

/* Emit match if have run of MIN_MATCH or longer, else emit literal */

1719

if (run >= MIN_MATCH) {

1720

check_match(s, s->strstart, s->strstart - 1, run);

1721

_tr_tally_dist(s, 1, run - MIN_MATCH, bflush);

1722

s->lookahead -= run;

1723

s->strstart += run;

1782

if (s->match_length >= MIN_MATCH) {

1783

check_match(s, s->strstart, s->strstart - 1, s->match_length);

1784

1785

_tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);

1786

1787

s->lookahead -= s->match_length;

1788

s->strstart += s->match_length;

1789

s->match_length = 0;

1724

1790

} else {

1725

1791

/* No match, output a literal byte */

1726

1792

Tracevv((stderr,"%c", s->window[s->strstart]));

1733

1799

FLUSH_BLOCK(s, flush == Z_FINISH);

1734

1800

return flush == Z_FINISH ? finish_done : block_done;

1735

1801

}

1736

#endif

1802

1803

/* ===========================================================================

1804

* For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.

1805

* (It will be regenerated if this run of deflate switches away from Huffman.)

1806

*/

1807

local block_state deflate_huff(s, flush)

1808

deflate_state *s;

1809

int flush;

1810

{

1811

int bflush; /* set if current block must be flushed */

1812

1813

for (;;) {

1814

/* Make sure that we have a literal to write. */

1815

if (s->lookahead == 0) {

1816

fill_window(s);

1817

if (s->lookahead == 0) {

1818

if (flush == Z_NO_FLUSH)

1819

return need_more;

1820

break; /* flush the current block */

1821

}

1822

}

1823

1824

/* Output a literal byte */

1825

s->match_length = 0;

1826

Tracevv((stderr,"%c", s->window[s->strstart]));

1827

_tr_tally_lit (s, s->window[s->strstart], bflush);

1828

s->lookahead--;

1829

s->strstart++;

1830

if (bflush) FLUSH_BLOCK(s, 0);

1831

}

1832

FLUSH_BLOCK(s, flush == Z_FINISH);

1833

return flush == Z_FINISH ? finish_done : block_done;

1834

}