3 {$T-}
4 {$define ORG_DEBUG}
5 {
6 trees.c -- output deflated data using Huffman coding
7 Copyright (C) 1995-1998 Jean-loup Gailly
9 Pascal tranlastion
10 Copyright (C) 1998 by Jacques Nomssi Nzali
11 For conditions of distribution and use, see copyright notice in readme.txt
12 }
14 {
15 * ALGORITHM
16 *
17 * The "deflation" process uses several Huffman trees. The more
18 * common source values are represented by shorter bit sequences.
19 *
20 * Each code tree is stored in a compressed form which is itself
21 * a Huffman encoding of the lengths of all the code strings (in
22 * ascending order by source values). The actual code strings are
23 * reconstructed from the lengths in the inflate process, as described
24 * in the deflate specification.
25 *
26 * REFERENCES
27 *
28 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
29 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
30 *
31 * Storer, James A.
32 * Data Compression: Methods and Theory, pp. 49-50.
33 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
34 *
35 * Sedgewick, R.
36 * Algorithms, p290.
37 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
38 }
40 interface
42 {$I imzconf.inc}
44 uses
45 {$ifdef DEBUG}
47 {$ENDIF}
50 { ===========================================================================
51 Internal compression state. }
53 const
55 { number of length codes, not counting the special END_BLOCK code }
58 { number of literal bytes 0..255 }
61 { number of Literal or Length codes, including the END_BLOCK code }
64 { number of distance codes }
67 { number of codes used to transfer the bit lengths }
70 { maximum heap size }
73 { All codes must not exceed MAX_BITS bits }
75 const
79 { Stream status }
82 { Data structure describing a single value and its code string. }
83 type
98 { Freq = fc.freq
99 Code = fc.code
100 Dad = dl.dad
101 Len = dl.len }
103 type
107 { generic tree type }
116 type
118 static_tree_desc =
119 record
134 type
144 { A Pos is an index in the character window. We use short instead of int to
145 save space in the various tables. IPos is used only for parameter passing.}
147 type
161 { used by deflate.pas: }
168 { Sliding window. Input bytes are read into the second half of the window,
169 and move to the first half later to keep a dictionary of at least wSize
170 bytes. With this organization, matches are limited to a distance of
171 wSize-MAX_MATCH bytes, but this ensures that IO is always
172 performed with a length multiple of the block size. Also, it limits
173 the window size to 64K, which is quite useful on MSDOS.
174 To do: use the user input buffer as sliding window. }
177 { Actual size of window: 2*wSize, except when the user input buffer
178 is directly used as sliding window. }
181 { Link to older string with same hash index. To limit the size of this
182 array to 64K, this link is maintained only for the last 32K strings.
183 An index in this array is thus a window index modulo 32K. }
193 { Number of bits by which ins_h must be shifted at each input
194 step. It must be such that after MIN_MATCH steps, the oldest
195 byte no longer takes part in the hash key, that is:
196 hash_shift * MIN_MATCH >= hash_bits }
199 { Window position at the beginning of the current output block. Gets
200 negative when the window is moved backwards. }
210 { Length of the best match at previous step. Matches not greater than this
211 are discarded. This is used in the lazy match evaluation. }
214 { To speed up deflation, hash chains are never searched beyond this
215 length. A higher limit improves compression ratio but degrades the
216 speed. }
218 { moved to the end because Borland Pascal won't accept the following:
219 max_lazy_match : uInt;
220 max_insert_length : uInt absolute max_lazy_match;
221 }
227 { Use a faster search when the previous match is longer than this }
231 { used by trees.pas: }
232 { Didn't use ct_data typedef below to supress compiler warning }
242 { number of codes at each bit length for an optimal tree }
247 { The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
248 The same heap array is used to build all trees. }
251 { Depth of each subtree used as tie breaker for trees of equal frequency }
257 { Size of match buffer for literals/lengths. There are 4 reasons for
258 limiting lit_bufsize to 64K:
259 - frequencies can be kept in 16 bit counters
260 - if compression is not successful for the first block, all input
261 data is still in the window so we can still emit a stored block even
262 when input comes from standard input. (This can also be done for
263 all blocks if lit_bufsize is not greater than 32K.)
264 - if compression is not successful for a file smaller than 64K, we can
265 even emit a stored file instead of a stored block (saving 5 bytes).
266 This is applicable only for zip (not gzip or zlib).
267 - creating new Huffman trees less frequently may not provide fast
268 adaptation to changes in the input data statistics. (Take for
269 example a binary file with poorly compressible code followed by
270 a highly compressible string table.) Smaller buffer sizes give
271 fast adaptation but have of course the overhead of transmitting
272 trees more frequently.
273 - I can't count above 4 }
279 { Buffer for distances. To simplify the code, d_buf and l_buf have
280 the same number of elements. To use different lengths, an extra flag
281 array would be necessary. }
289 {$ifdef DEBUG}
291 {$endif}
294 { Output buffer. bits are inserted starting at the bottom (least
295 significant bits). }
298 { Number of valid bits in bi_buf. All bits above the last valid bit
299 are always zero. }
303 { Attempt to find a better match only when the current match is strictly
304 smaller than this value. This mechanism is used only for compression
305 levels >= 4. }
308 { Insert new strings in the hash table only if the match length is not
309 greater than this length. This saves time but degrades compression.
310 max_insert_length is used only for compression levels <= 3. }
331 implementation
333 { #define GEN_TREES_H }
335 {$ifndef GEN_TREES_H}
336 { header created automatically with -DGEN_TREES_H }
338 const
341 { The static literal tree. Since the bit lengths are imposed, there is no
342 need for the L_CODES extra codes used during heap construction. However
343 The codes 286 and 287 are needed to build a canonical tree (see _tr_init
344 below). }
345 var
347 { fc:(freq, code) dl:(dad,len) }
444 );
447 { The static distance tree. (Actually a trivial tree since all lens use
448 5 bits.) }
460 );
462 { Distance codes. The first 256 values correspond to the distances
463 3 .. 258, the last 256 values correspond to the top 8 bits of
464 the 15 bit distances. }
492 );
494 { length code for each normalized match length (0 == MIN_MATCH) }
509 );
512 { First normalized length for each code (0 = MIN_MATCH) }
516 );
519 { First normalized distance for each code (0 = distance of 1) }
524 );
525 {$endif}
527 { Output a byte on the stream.
528 IN assertion: there is enough room in pending_buf.
529 macro put_byte(s, c)
530 begin
531 s^.pending_buf^[s^.pending] := (c);
532 Inc(s^.pending);
533 end
534 }
536 const
538 { Minimum amount of lookahead, except at the end of the input file.
539 See deflate.c for comments about the MIN_MATCH+1. }
541 {macro d_code(dist)
542 if (dist) < 256 then
543 := _dist_code[dist]
544 else
545 := _dist_code[256+((dist) shr 7)]);
546 Mapping from a distance to a distance code. dist is the distance - 1 and
547 must not have side effects. _dist_code[256] and _dist_code[257] are never
548 used. }
550 {$ifndef ORG_DEBUG}
551 { Inline versions of _tr_tally for speed: }
554 extern uch _length_code[];
555 extern uch _dist_code[];
556 #else
559 #endif
562 var
564 begin
574 var
577 begin
589 {$endif}
591 { ===========================================================================
592 Constants }
594 const
596 { Bit length codes must not exceed MAX_BL_BITS bits }
598 const
600 { end of block literal code }
602 const
604 { repeat previous bit length 3-6 times (2 bits of repeat count) }
606 const
608 { repeat a zero length 3-10 times (3 bits of repeat count) }
610 const
612 { repeat a zero length 11-138 times (7 bits of repeat count) }
614 {local}
615 const
617 { extra bits for each length code }
620 {local}
621 const
623 { extra bits for each distance code }
626 {local}
627 const
631 {local}
632 const
635 { The lengths of the bit length codes are sent in order of decreasing
636 probability, to avoid transmitting the lengths for unused bit length codes.
637 }
639 const
641 { Number of bits used within bi_buf. (bi_buf might be implemented on
642 more than 16 bits on some systems.) }
644 { ===========================================================================
645 Local data. These are initialized only once. }
648 {$ifdef GEN_TREES_H)}
649 { non ANSI compilers may not accept trees.h }
651 const
654 {local}
655 var
657 { The static literal tree. Since the bit lengths are imposed, there is no
658 need for the L_CODES extra codes used during heap construction. However
659 The codes 286 and 287 are needed to build a canonical tree (see _tr_init
660 below). }
662 {local}
664 { The static distance tree. (Actually a trivial tree since all codes use
665 5 bits.) }
668 { Distance codes. The first 256 values correspond to the distances
669 3 .. 258, the last 256 values correspond to the top 8 bits of
670 the 15 bit distances. }
673 { length code for each normalized match length (0 == MIN_MATCH) }
675 {local}
677 { First normalized length for each code (0 = MIN_MATCH) }
679 {local}
681 { First normalized distance for each code (0 = distance of 1) }
685 {local}
686 const
694 {local}
695 const
703 {local}
704 const
712 (* ===========================================================================
713 Local (static) routines in this file. }
715 procedure tr_static_init;
716 procedure init_block(var deflate_state);
717 procedure pqdownheap(var s : deflate_state;
718 var tree : ct_data;
719 k : int);
720 procedure gen_bitlen(var s : deflate_state;
721 var desc : tree_desc);
722 procedure gen_codes(var tree : ct_data;
723 max_code : int;
724 bl_count : pushf);
725 procedure build_tree(var s : deflate_state;
726 var desc : tree_desc);
727 procedure scan_tree(var s : deflate_state;
728 var tree : ct_data;
729 max_code : int);
730 procedure send_tree(var s : deflate_state;
731 var tree : ct_data;
732 max_code : int);
733 function build_bl_tree(var deflate_state) : int;
734 procedure send_all_trees(var deflate_state;
735 lcodes : int;
736 dcodes : int;
737 blcodes : int);
738 procedure compress_block(var s : deflate_state;
739 var ltree : ct_data;
740 var dtree : ct_data);
741 procedure set_data_type(var s : deflate_state);
742 function bi_reverse(value : unsigned;
743 length : int) : unsigned;
744 procedure bi_windup(var deflate_state);
745 procedure bi_flush(var deflate_state);
746 procedure copy_block(var deflate_state;
747 buf : pcharf;
748 len : unsigned;
749 header : int);
750 *)
752 {$ifdef GEN_TREES_H}
753 {local}
755 {$endif}
757 (*
758 { ===========================================================================
759 Output a short LSB first on the stream.
760 IN assertion: there is enough room in pendingBuf. }
762 macro put_short(s, w)
763 begin
764 {put_byte(s, (uch)((w) & 0xff));}
765 s.pending_buf^[s.pending] := uch((w) and $ff);
766 Inc(s.pending);
768 {put_byte(s, (uch)((ush)(w) >> 8));}
769 s.pending_buf^[s.pending] := uch(ush(w) shr 8);;
770 Inc(s.pending);
771 end
772 *)
774 { ===========================================================================
775 Send a value on a given number of bits.
776 IN assertion: length <= 16 and value fits in length bits. }
778 {$ifdef ORG_DEBUG}
780 {local}
784 begin
785 {$ifdef DEBUG}
789 {$ENDIF}
791 { If not enough room in bi_buf, use (valid) bits from bi_buf and
792 (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
793 unused bits in value. }
797 begin
799 {put_short(s, s.bi_buf);}
807 end
808 else
809 begin
821 begin
823 { Send a code of the given tree. c and tree must not have side effects }
824 end
831 {put_short(s, s.bi_buf);}
839 end else begin\
842 end\
846 { ===========================================================================
847 Reverse the first len bits of a code, using straightforward code (a faster
848 method would use a table)
849 IN assertion: 1 <= len <= 15 }
851 {local}
855 var
857 begin
859 repeat
868 { ===========================================================================
869 Generate the codes for a given tree and bit counts (which need not be
870 optimal).
871 IN assertion: the array bl_count contains the bit length statistics for
872 the given tree and the field len is set for all tree elements.
873 OUT assertion: the field code is set for all tree elements of non
874 zero code length. }
876 {local}
881 var
886 var
888 begin
891 { The distribution counts are first used to generate the code values
892 without bit reversal. }
895 begin
899 { Check that the bit counts in bl_count are consistent. The last code
900 must be all ones. }
902 {$IFDEF DEBUG}
906 {$ENDIF}
909 begin
912 continue;
913 { Now reverse the bits }
916 {$ifdef DEBUG}
921 else
925 {$ENDIF}
929 { ===========================================================================
930 Genererate the file trees.h describing the static trees. }
931 {$ifdef GEN_TREES_H}
936 else \
939 else
940 ', '
943 var
946 begin
948 {$I-}
950 {$I+}
957 begin
964 begin
971 begin
978 begin
985 begin
992 begin
1002 { ===========================================================================
1003 Initialize the various 'constant' tables. }
1005 {local}
1008 {$ifdef GEN_TREES_H}
1009 const
1011 var
1018 { number of codes at each bit length for an optimal tree }
1019 begin
1021 exit;
1023 { Initialize the mapping length (0..255) -> length code (0..28) }
1026 begin
1029 begin
1035 { Note that the length 255 (match length 258) can be represented
1036 in two different ways: code 284 + 5 bits or code 285, so we
1037 overwrite length_code[255] to use the best encoding: }
1041 { Initialize the mapping dist (0..32K) -> dist code (0..29) }
1044 begin
1047 begin
1055 begin
1058 begin
1065 { Construct the codes of the static literal tree }
1070 begin
1076 begin
1082 begin
1088 begin
1094 { Codes 286 and 287 do not exist, but we must include them in the
1095 tree construction to get a canonical Huffman tree (longest code
1096 all ones) }
1100 { The static distance tree is trivial: }
1102 begin
1109 {$else}
1110 begin
1114 { ===========================================================================
1115 Initialize a new block. }
1116 {local}
1119 var
1121 begin
1122 { Initialize the trees. }
1137 const
1139 { Index within the heap array of least frequent node in the Huffman tree }
1141 { ===========================================================================
1142 Initialize the tree data structures for a new zlib stream. }
1144 begin
1145 tr_static_init;
1161 {$ifdef DEBUG}
1163 {$endif}
1165 { Initialize the first block of the first file: }
1169 { ===========================================================================
1170 Remove the smallest element from the heap and recreate the heap with
1171 one less element. Updates heap and heap_len.
1173 macro pqremove(s, tree, top)
1174 begin
1175 top := s.heap[SMALLEST];
1176 s.heap[SMALLEST] := s.heap[s.heap_len];
1177 Dec(s.heap_len);
1178 pqdownheap(s, tree, SMALLEST);
1179 end
1180 }
1182 { ===========================================================================
1183 Compares to subtrees, using the tree depth as tie breaker when
1184 the subtrees have equal frequency. This minimizes the worst case length.
1186 macro smaller(tree, n, m, depth)
1187 ( (tree[n].Freq < tree[m].Freq) or
1188 ((tree[n].Freq = tree[m].Freq) and (depth[n] <= depth[m])) )
1189 }
1191 { ===========================================================================
1192 Restore the heap property by moving down the tree starting at node k,
1193 exchanging a node with the smallest of its two sons if necessary, stopping
1194 when the heap property is re-established (each father smaller than its
1195 two sons). }
1196 {local}
1201 var
1204 begin
1208 begin
1209 { Set j to the smallest of the two sons: }
1211 {smaller(tree, s.heap[j+1], s.heap[j], s.depth)}
1215 begin
1218 { Exit if v is smaller than both sons }
1223 break;
1224 { Exchange v with the smallest son }
1228 { And continue down the tree, setting j to the left son of k }
1234 { ===========================================================================
1235 Compute the optimal bit lengths for a tree and update the total bit length
1236 for the current block.
1237 IN assertion: the fields freq and dad are set, heap[heap_max] and
1238 above are the tree nodes sorted by increasing frequency.
1239 OUT assertions: the field len is set to the optimal bit length, the
1240 array bl_count contains the frequencies for each bit length.
1241 The length opt_len is updated; static_len is also updated if stree is
1242 not null. }
1244 {local}
1247 var
1260 begin
1272 { In a first pass, compute the optimal bit lengths (which may
1273 overflow in the case of the bit length tree). }
1278 begin
1282 begin
1287 { We overwrite tree[n].dl.Dad which is no longer needed }
1302 exit;
1303 {$ifdef DEBUG}
1305 {$endif}
1306 { This happens for example on obj2 and pic of the Calgary corpus }
1308 { Find the first bit length which could increase: }
1309 repeat
1316 { The brother of the overflow item also moves one step up,
1317 but this does not affect bl_count[max_length] }
1322 { Now recompute all bit lengths, scanning in increasing frequency.
1323 h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
1324 lengths instead of fixing only the wrong ones. This idea is taken
1325 from 'ar' written by Haruhiko Okumura.) }
1328 begin
1331 begin
1335 continue;
1337 begin
1338 {$ifdef DEBUG}
1341 {$ENDIF}
1351 { ===========================================================================
1352 Construct one Huffman tree and assigns the code bit strings and lengths.
1353 Update the total bit length for the current block.
1354 IN assertion: the field freq is set for all tree elements.
1355 OUT assertions: the fields len and code are set to the optimal bit length
1356 and corresponding code. The length opt_len is updated; static_len is
1357 also updated if stree is not null. The field max_code is set. }
1359 {local}
1363 var
1370 begin
1376 { Construct the initial heap, with least frequent element in
1377 heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
1378 heap[0] is not used. }
1383 begin
1385 begin
1390 end
1391 else
1392 begin
1397 { The pkzip format requires that at least one distance code exists,
1398 and that at least one bit should be sent even if there is only one
1399 possible code. So to avoid special checks later on we force at least
1400 two codes of non zero frequency. }
1403 begin
1406 begin
1410 end
1411 else
1412 begin
1421 { node is 0 or 1 so it does not have extra bits }
1425 { The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
1426 establish sub-heaps of increasing lengths: }
1431 { Construct the Huffman tree by repeatedly combining the least two
1432 frequent nodes. }
1435 repeat
1449 { Create a new node father of n and m }
1451 { maximum }
1454 else
1459 {$ifdef DUMP_BL_TREE}
1461 begin
1465 {$endif}
1466 { and insert the new node in the heap }
1476 { At this point, the fields freq and dad are set. We can now
1477 generate the bit lengths. }
1481 { The field len is now set, we can generate the bit codes }
1485 { ===========================================================================
1486 Scan a literal or distance tree to determine the frequencies of the codes
1487 in the bit length tree. }
1489 {local}
1493 var
1501 begin
1509 begin
1516 begin
1521 continue
1522 else
1525 else
1527 begin
1531 end
1532 else
1535 else
1541 begin
1544 end
1545 else
1547 begin
1550 end
1551 else
1552 begin
1559 { ===========================================================================
1560 Send a literal or distance tree in compressed form, using the codes in
1561 bl_tree. }
1563 {local}
1568 var
1576 begin
1585 begin
1591 begin
1596 continue
1597 else
1599 begin
1600 repeat
1601 {$ifdef DEBUG}
1603 {$ENDIF}
1607 end
1608 else
1610 begin
1612 begin
1613 {$ifdef DEBUG}
1615 {$ENDIF}
1619 {$IFDEF DEBUG}
1621 {$ENDIF}
1622 {$ifdef DEBUG}
1624 {$ENDIF}
1627 end
1628 else
1630 begin
1631 {$ifdef DEBUG}
1633 {$ENDIF}
1636 end
1637 else
1638 begin
1639 {$ifdef DEBUG}
1641 {$ENDIF}
1648 begin
1651 end
1652 else
1654 begin
1657 end
1658 else
1659 begin
1666 { ===========================================================================
1667 Construct the Huffman tree for the bit lengths and return the index in
1668 bl_order of the last bit length code to send. }
1670 {local}
1672 var
1674 begin
1675 { Determine the bit length frequencies for literal and distance trees }
1679 { Build the bit length tree: }
1681 { opt_len now includes the length of the tree representations, except
1682 the lengths of the bit lengths codes and the 5+5+4 bits for the counts. }
1684 { Determine the number of bit length codes to send. The pkzip format
1685 requires that at least 4 bit length codes be sent. (appnote.txt says
1686 3 but the actual value used is 4.) }
1689 begin
1691 break;
1693 { Update opt_len to include the bit length tree and counts }
1695 {$ifdef DEBUG}
1697 {$ENDIF}
1702 { ===========================================================================
1703 Send the header for a block using dynamic Huffman trees: the counts, the
1704 lengths of the bit length codes, the literal tree and the distance tree.
1705 IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. }
1707 {local}
1712 var
1714 begin
1715 {$IFDEF DEBUG}
1721 {$ENDIF}
1726 begin
1727 {$ifdef DEBUG}
1729 {$ENDIF}
1732 {$ifdef DEBUG}
1734 {$ENDIF}
1737 {$ifdef DEBUG}
1739 {$ENDIF}
1742 {$ifdef DEBUG}
1744 {$ENDIF}
1747 { ===========================================================================
1748 Flush the bit buffer and align the output on a byte boundary }
1750 {local}
1752 begin
1754 begin
1755 {put_short(s, s.bi_buf);}
1760 end
1761 else
1763 begin
1764 {put_byte(s, (Byte)s^.bi_buf);}
1770 {$ifdef DEBUG}
1772 {$endif}
1775 { ===========================================================================
1776 Copy a stored block, storing first the length and its
1777 one's complement if requested. }
1779 {local}
1784 begin
1789 begin
1790 {put_short(s, (ush)len);}
1795 {put_short(s, (ush)~len);}
1801 {$ifdef DEBUG}
1803 {$endif}
1805 {$ifdef DEBUG}
1807 {$endif}
1809 begin
1811 {put_byte(s, *buf++);}
1819 { ===========================================================================
1820 Send a stored block }
1827 begin
1835 { ===========================================================================
1836 Flush the bit buffer, keeping at most 7 bits in it. }
1838 {local}
1840 begin
1842 begin
1843 {put_short(s, s.bi_buf);}
1851 end
1852 else
1854 begin
1855 {put_byte(s, (Byte)s^.bi_buf);}
1865 { ===========================================================================
1866 Send one empty static block to give enough lookahead for inflate.
1867 This takes 10 bits, of which 7 may remain in the bit buffer.
1868 The current inflate code requires 9 bits of lookahead. If the
1869 last two codes for the previous block (real code plus EOB) were coded
1870 on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
1871 the last real code. In this case we send two empty static blocks instead
1872 of one. (There are no problems if the previous block is stored or fixed.)
1873 To simplify the code, we assume the worst case of last real code encoded
1874 on one bit only. }
1877 begin
1879 {$ifdef DEBUG}
1881 {$ENDIF}
1885 { Of the 10 bits for the empty block, we have already sent
1886 (10 - bi_valid) bits. The lookahead for the last real code (before
1887 the EOB of the previous block) was thus at least one plus the length
1888 of the EOB plus what we have just sent of the empty static block. }
1890 begin
1892 {$ifdef DEBUG}
1894 {$ENDIF}
1902 { ===========================================================================
1903 Set the data type to ASCII or BINARY, using a crude approximation:
1904 binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
1905 IN assertion: the fields freq of dyn_ltree are set and the total of all
1906 frequencies does not exceed 64K (to fit in an int on 16 bit machines). }
1908 {local}
1910 var
1914 begin
1920 begin
1925 begin
1930 begin
1936 else
1940 { ===========================================================================
1941 Send the block data compressed using the given Huffman trees }
1943 {local}
1947 var
1953 begin
1956 repeat
1961 begin
1962 { send a literal byte }
1963 {$ifdef DEBUG}
1966 {$ENDIF}
1968 end
1969 else
1970 begin
1971 { Here, lc is the match length - MIN_MATCH }
1973 { send the length code }
1974 {$ifdef DEBUG}
1976 {$ENDIF}
1980 begin
1985 {code := d_code(dist);}
1988 else
1991 {$IFDEF DEBUG}
1993 {$ENDIF}
1995 { send the distance code }
1996 {$ifdef DEBUG}
1998 {$ENDIF}
2002 begin
2008 { Check that the overlay between pending_buf and d_buf+l_buf is ok: }
2009 {$IFDEF DEBUG}
2011 {$ENDIF}
2014 {$ifdef DEBUG}
2016 {$ENDIF}
2022 { ===========================================================================
2023 Determine the best encoding for the current block: dynamic trees, static
2024 trees or store, and output the encoded block to the zip file. This function
2025 returns the total compressed length for the file so far. }
2031 var
2034 begin
2037 { Build the Huffman trees unless a stored block is forced }
2039 begin
2040 { Check if the file is ascii or binary }
2044 { Construct the literal and distance trees }
2046 {$ifdef DEBUG}
2048 {$ENDIF}
2051 {$ifdef DEBUG}
2053 {$ENDIF}
2054 { At this point, opt_len and static_len are the total bit lengths of
2055 the compressed block data, excluding the tree representations. }
2057 { Build the bit length tree for the above two trees, and get the index
2058 in bl_order of the last bit length code to send. }
2061 { Determine the best encoding. Compute first the block length in bytes}
2065 {$ifdef DEBUG}
2069 {$ENDIF}
2074 end
2075 else
2076 begin
2077 {$IFDEF DEBUG}
2079 {$ENDIF}
2084 { If compression failed and this is the first and last block,
2085 and if the .zip file can be seeked (to rewrite the local header),
2086 the whole file is transformed into a stored file: }
2088 {$ifdef STORED_FILE_OK}
2089 {$ifdef FORCE_STORED_FILE}
2092 {$else}
2095 begin
2096 {$endif}
2097 { Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: }
2104 end
2105 else
2108 {$ifdef FORCE_STORED}
2111 {$else}
2113 begin
2114 { 4: two words for the lengths }
2115 {$endif}
2116 { The test buf <> NULL is only necessary if LIT_BUFSIZE > WSIZE.
2117 Otherwise we can't have processed more than WSIZE input bytes since
2118 the last block flush, because compression would have been
2119 successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
2120 transform a block into a stored block. }
2124 {$ifdef FORCE_STATIC}
2125 end
2126 else
2129 {$else}
2130 end
2131 else
2133 begin
2134 {$endif}
2138 end
2139 else
2140 begin
2147 {$ifdef DEBUG}
2149 {$ENDIF}
2153 begin
2157 {$ifdef DEBUG}
2160 {$ENDIF}
2166 { ===========================================================================
2167 Save the match info and tally the frequency counts. Return true if
2168 the current block must be flushed. }
2173 var
2174 {$IFDEF DEBUG}
2176 {$ENDIF}
2178 {$ifdef TRUNCATE_BLOCK}
2179 var
2183 {$endif}
2184 begin
2189 begin
2190 { lc is the unmatched char }
2192 end
2193 else
2194 begin
2196 { Here, lc is the match length - MIN_MATCH }
2199 {macro d_code(dist)}
2202 else
2204 {$IFDEF DEBUG}
2205 {macro MAX_DIST(s) <=> ((s)^.w_size-MIN_LOOKAHEAD)
2206 In order to simplify the code, particularly on 16 bit machines, match
2207 distances are limited to MAX_DIST instead of WSIZE. }
2212 {$ENDIF}
2214 {s.dyn_dtree[d_code(dist)].Freq++;}
2218 {$ifdef TRUNCATE_BLOCK}
2219 { Try to guess if it is profitable to stop the current block here }
2221 begin
2222 { Compute an upper bound for the compressed length }
2226 begin
2231 {$ifdef DEBUG}
2233 { s.last_lit, in_length, out_length,
2234 Long(100) - out_length*Long(100) div in_length)); }
2235 {$ENDIF}
2237 begin
2239 exit;
2242 {$endif}
2244 { We avoid equality with lit_bufsize because of wraparound at 64K
2245 on 16 bit machines and because stored blocks are restricted to
2246 64K-1 bytes. }