Rev 1896 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1896 | Rev 3926 | ||
---|---|---|---|
Line 1... | Line 1... | ||
1 | /* trees.c -- output deflated data using Huffman coding |
1 | /* trees.c -- output deflated data using Huffman coding |
2 | * Copyright (C) 1995-2010 Jean-loup Gailly |
2 | * Copyright (C) 1995-2012 Jean-loup Gailly |
3 | * detect_data_type() function provided freely by Cosmin Truta, 2006 |
3 | * detect_data_type() function provided freely by Cosmin Truta, 2006 |
4 | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | * For conditions of distribution and use, see copyright notice in zlib.h |
5 | */ |
5 | */ |
Line 6... | Line 6... | ||
6 | 6 | ||
Line 72... | Line 72... | ||
72 | = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; |
72 | = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; |
73 | /* The lengths of the bit length codes are sent in order of decreasing |
73 | /* The lengths of the bit length codes are sent in order of decreasing |
74 | * probability, to avoid transmitting the lengths for unused bit length codes. |
74 | * probability, to avoid transmitting the lengths for unused bit length codes. |
75 | */ |
75 | */ |
Line 76... | Line -... | ||
76 | - | ||
77 | #define Buf_size (8 * 2*sizeof(char)) |
- | |
78 | /* Number of bits used within bi_buf. (bi_buf might be implemented on |
- | |
79 | * more than 16 bits on some systems.) |
- | |
80 | */ |
- | |
81 | 76 | ||
82 | /* =========================================================================== |
77 | /* =========================================================================== |
83 | * Local data. These are initialized only once. |
78 | * Local data. These are initialized only once. |
Line 84... | Line 79... | ||
84 | */ |
79 | */ |
Line 149... | Line 144... | ||
149 | local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
144 | local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
150 | local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
145 | local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
151 | local int build_bl_tree OF((deflate_state *s)); |
146 | local int build_bl_tree OF((deflate_state *s)); |
152 | local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, |
147 | local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, |
153 | int blcodes)); |
148 | int blcodes)); |
154 | local void compress_block OF((deflate_state *s, ct_data *ltree, |
149 | local void compress_block OF((deflate_state *s, const ct_data *ltree, |
155 | ct_data *dtree)); |
150 | const ct_data *dtree)); |
156 | local int detect_data_type OF((deflate_state *s)); |
151 | local int detect_data_type OF((deflate_state *s)); |
157 | local unsigned bi_reverse OF((unsigned value, int length)); |
152 | local unsigned bi_reverse OF((unsigned value, int length)); |
158 | local void bi_windup OF((deflate_state *s)); |
153 | local void bi_windup OF((deflate_state *s)); |
159 | local void bi_flush OF((deflate_state *s)); |
154 | local void bi_flush OF((deflate_state *s)); |
160 | local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
155 | local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
Line 397... | Line 392... | ||
397 | s->bl_desc.dyn_tree = s->bl_tree; |
392 | s->bl_desc.dyn_tree = s->bl_tree; |
398 | s->bl_desc.stat_desc = &static_bl_desc; |
393 | s->bl_desc.stat_desc = &static_bl_desc; |
Line 399... | Line 394... | ||
399 | 394 | ||
400 | s->bi_buf = 0; |
395 | s->bi_buf = 0; |
401 | s->bi_valid = 0; |
- | |
402 | s->last_eob_len = 8; /* enough lookahead for inflate */ |
396 | s->bi_valid = 0; |
403 | #ifdef DEBUG |
397 | #ifdef DEBUG |
404 | s->compressed_len = 0L; |
398 | s->compressed_len = 0L; |
405 | s->bits_sent = 0L; |
399 | s->bits_sent = 0L; |
Line 881... | Line 875... | ||
881 | #endif |
875 | #endif |
882 | copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ |
876 | copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ |
883 | } |
877 | } |
Line 884... | Line 878... | ||
884 | 878 | ||
- | 879 | /* =========================================================================== |
|
- | 880 | * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) |
|
- | 881 | */ |
|
- | 882 | void ZLIB_INTERNAL _tr_flush_bits(s) |
|
- | 883 | deflate_state *s; |
|
- | 884 | { |
|
- | 885 | bi_flush(s); |
|
- | 886 | } |
|
- | 887 | ||
885 | /* =========================================================================== |
888 | /* =========================================================================== |
886 | * Send one empty static block to give enough lookahead for inflate. |
889 | * Send one empty static block to give enough lookahead for inflate. |
887 | * This takes 10 bits, of which 7 may remain in the bit buffer. |
- | |
888 | * The current inflate code requires 9 bits of lookahead. If the |
- | |
889 | * last two codes for the previous block (real code plus EOB) were coded |
- | |
890 | * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode |
- | |
891 | * the last real code. In this case we send two empty static blocks instead |
- | |
892 | * of one. (There are no problems if the previous block is stored or fixed.) |
- | |
893 | * To simplify the code, we assume the worst case of last real code encoded |
- | |
894 | * on one bit only. |
890 | * This takes 10 bits, of which 7 may remain in the bit buffer. |
895 | */ |
891 | */ |
896 | void ZLIB_INTERNAL _tr_align(s) |
892 | void ZLIB_INTERNAL _tr_align(s) |
897 | deflate_state *s; |
893 | deflate_state *s; |
898 | { |
894 | { |
899 | send_bits(s, STATIC_TREES<<1, 3); |
895 | send_bits(s, STATIC_TREES<<1, 3); |
900 | send_code(s, END_BLOCK, static_ltree); |
896 | send_code(s, END_BLOCK, static_ltree); |
901 | #ifdef DEBUG |
897 | #ifdef DEBUG |
902 | s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ |
898 | s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ |
903 | #endif |
899 | #endif |
904 | bi_flush(s); |
- | |
905 | /* Of the 10 bits for the empty block, we have already sent |
- | |
906 | * (10 - bi_valid) bits. The lookahead for the last real code (before |
- | |
907 | * the EOB of the previous block) was thus at least one plus the length |
- | |
908 | * of the EOB plus what we have just sent of the empty static block. |
- | |
909 | */ |
- | |
910 | if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { |
- | |
911 | send_bits(s, STATIC_TREES<<1, 3); |
- | |
912 | send_code(s, END_BLOCK, static_ltree); |
- | |
913 | #ifdef DEBUG |
- | |
914 | s->compressed_len += 10L; |
- | |
915 | #endif |
- | |
916 | bi_flush(s); |
- | |
917 | } |
- | |
918 | s->last_eob_len = 7; |
900 | bi_flush(s); |
Line 919... | Line 901... | ||
919 | } |
901 | } |
920 | 902 | ||
921 | /* =========================================================================== |
903 | /* =========================================================================== |
Line 988... | Line 970... | ||
988 | } else if (static_lenb >= 0) { /* force static trees */ |
970 | } else if (static_lenb >= 0) { /* force static trees */ |
989 | #else |
971 | #else |
990 | } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { |
972 | } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { |
991 | #endif |
973 | #endif |
992 | send_bits(s, (STATIC_TREES<<1)+last, 3); |
974 | send_bits(s, (STATIC_TREES<<1)+last, 3); |
993 | compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); |
975 | compress_block(s, (const ct_data *)static_ltree, |
- | 976 | (const ct_data *)static_dtree); |
|
994 | #ifdef DEBUG |
977 | #ifdef DEBUG |
995 | s->compressed_len += 3 + s->static_len; |
978 | s->compressed_len += 3 + s->static_len; |
996 | #endif |
979 | #endif |
997 | } else { |
980 | } else { |
998 | send_bits(s, (DYN_TREES<<1)+last, 3); |
981 | send_bits(s, (DYN_TREES<<1)+last, 3); |
999 | send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
982 | send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
1000 | max_blindex+1); |
983 | max_blindex+1); |
1001 | compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); |
984 | compress_block(s, (const ct_data *)s->dyn_ltree, |
- | 985 | (const ct_data *)s->dyn_dtree); |
|
1002 | #ifdef DEBUG |
986 | #ifdef DEBUG |
1003 | s->compressed_len += 3 + s->opt_len; |
987 | s->compressed_len += 3 + s->opt_len; |
1004 | #endif |
988 | #endif |
1005 | } |
989 | } |
1006 | Assert (s->compressed_len == s->bits_sent, "bad compressed size"); |
990 | Assert (s->compressed_len == s->bits_sent, "bad compressed size"); |
Line 1073... | Line 1057... | ||
1073 | /* =========================================================================== |
1057 | /* =========================================================================== |
1074 | * Send the block data compressed using the given Huffman trees |
1058 | * Send the block data compressed using the given Huffman trees |
1075 | */ |
1059 | */ |
1076 | local void compress_block(s, ltree, dtree) |
1060 | local void compress_block(s, ltree, dtree) |
1077 | deflate_state *s; |
1061 | deflate_state *s; |
1078 | ct_data *ltree; /* literal tree */ |
1062 | const ct_data *ltree; /* literal tree */ |
1079 | ct_data *dtree; /* distance tree */ |
1063 | const ct_data *dtree; /* distance tree */ |
1080 | { |
1064 | { |
1081 | unsigned dist; /* distance of matched string */ |
1065 | unsigned dist; /* distance of matched string */ |
1082 | int lc; /* match length or unmatched char (if dist == 0) */ |
1066 | int lc; /* match length or unmatched char (if dist == 0) */ |
1083 | unsigned lx = 0; /* running index in l_buf */ |
1067 | unsigned lx = 0; /* running index in l_buf */ |
1084 | unsigned code; /* the code to send */ |
1068 | unsigned code; /* the code to send */ |
Line 1116... | Line 1100... | ||
1116 | "pendingBuf overflow"); |
1100 | "pendingBuf overflow"); |
Line 1117... | Line 1101... | ||
1117 | 1101 | ||
Line 1118... | Line 1102... | ||
1118 | } while (lx < s->last_lit); |
1102 | } while (lx < s->last_lit); |
1119 | - | ||
1120 | send_code(s, END_BLOCK, ltree); |
1103 | |
Line 1121... | Line 1104... | ||
1121 | s->last_eob_len = ltree[END_BLOCK].Len; |
1104 | send_code(s, END_BLOCK, ltree); |
1122 | } |
1105 | } |
1123 | 1106 | ||
Line 1224... | Line 1207... | ||
1224 | charf *buf; /* the input data */ |
1207 | charf *buf; /* the input data */ |
1225 | unsigned len; /* its length */ |
1208 | unsigned len; /* its length */ |
1226 | int header; /* true if block header must be written */ |
1209 | int header; /* true if block header must be written */ |
1227 | { |
1210 | { |
1228 | bi_windup(s); /* align on byte boundary */ |
1211 | bi_windup(s); /* align on byte boundary */ |
1229 | s->last_eob_len = 8; /* enough lookahead for inflate */ |
- | |
Line 1230... | Line 1212... | ||
1230 | 1212 | ||
1231 | if (header) { |
1213 | if (header) { |
1232 | put_short(s, (ush)len); |
1214 | put_short(s, (ush)len); |
1233 | put_short(s, (ush)~len); |
1215 | put_short(s, (ush)~len); |