#include "deflate.h"
Go to the source code of this file.
Data Structures | |
struct | static_tree_desc_s |
Defines | |
#define | MAX_BL_BITS 7 |
#define | END_BLOCK 256 |
#define | REP_3_6 16 |
#define | REPZ_3_10 17 |
#define | REPZ_11_138 18 |
#define | Buf_size (8 * 2*sizeof(char)) |
#define | DIST_CODE_LEN 512 |
#define | send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) |
#define | put_short(s, w) |
#define | send_bits(s, value, length) |
#define | SMALLEST 1 |
#define | pqremove(s, tree, top) |
#define | smaller(tree, n, m, depth) |
Functions | |
local void tr_static_init | OF ((void)) |
local void init_block | OF ((deflate_state *s)) |
local void pqdownheap | OF ((deflate_state *s, ct_data *tree, int k)) |
local void gen_bitlen | OF ((deflate_state *s, tree_desc *desc)) |
local void gen_codes | OF ((ct_data *tree, int max_code, ushf *bl_count)) |
local void scan_tree | OF ((deflate_state *s, ct_data *tree, int max_code)) |
local void send_all_trees | OF ((deflate_state *s, int lcodes, int dcodes, int blcodes)) |
local void compress_block | OF ((deflate_state *s, ct_data *ltree, ct_data *dtree)) |
local unsigned bi_reverse | OF ((unsigned value, int length)) |
local void copy_block | OF ((deflate_state *s, charf *buf, unsigned len, int header)) |
local void | tr_static_init () |
void | _tr_init (deflate_state *s) |
local void | init_block (deflate_state *s) |
local void | pqdownheap (deflate_state *s, ct_data *tree, int k) |
local void | gen_bitlen (deflate_state *s, tree_desc *desc) |
local void | gen_codes (ct_data *tree, int max_code, ushf *bl_count) |
local void | build_tree (deflate_state *s, tree_desc *desc) |
local void | scan_tree (deflate_state *s, ct_data *tree, int max_code) |
local void | send_tree (deflate_state *s, ct_data *tree, int max_code) |
local int | build_bl_tree (deflate_state *s) |
local void | send_all_trees (deflate_state *s, int lcodes, int dcodes, int blcodes) |
void | _tr_stored_block (deflate_state *s, charf *buf, ulg stored_len, int eof) |
void | _tr_align (deflate_state *s) |
void | _tr_flush_block (deflate_state *s, charf *buf, ulg stored_len, int eof) |
int | _tr_tally (deflate_state *s, unsigned dist, unsigned lc) |
local void | compress_block (deflate_state *s, ct_data *ltree, ct_data *dtree) |
local void | set_data_type (deflate_state *s) |
local unsigned | bi_reverse (unsigned code, int len) |
local void | bi_flush (deflate_state *s) |
local void | bi_windup (deflate_state *s) |
local void | copy_block (deflate_state *s, charf *buf, unsigned len, int header) |
Variables | |
local const int | extra_lbits [LENGTH_CODES] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0} |
local const int | extra_dbits [D_CODES] = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13} |
local const int | extra_blbits [BL_CODES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7} |
local const uch | bl_order [BL_CODES] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15} |
local ct_data | static_ltree [L_CODES+2] |
local ct_data | static_dtree [D_CODES] |
uch | _dist_code [DIST_CODE_LEN] |
uch | _length_code [MAX_MATCH-MIN_MATCH+1] |
local int | base_length [LENGTH_CODES] |
local int | base_dist [D_CODES] |
local static_tree_desc | static_l_desc |
local static_tree_desc | static_d_desc |
local static_tree_desc | static_bl_desc |
#define END_BLOCK 256 |
Definition at line 49 of file trees.cc.
Referenced by _tr_align(), compress_block(), and init_block().
#define pqremove | ( | s, | |||
tree, | |||||
top | ) |
#define put_short | ( | s, | |||
w | ) |
Value:
{ \ put_byte(s, (uch)((w) & 0xff)); \ put_byte(s, (uch)((ush)(w) >> 8)); \ }
Definition at line 180 of file trees.cc.
Referenced by bi_flush(), bi_windup(), and copy_block().
#define REP_3_6 16 |
#define REPZ_11_138 18 |
#define REPZ_3_10 17 |
#define send_bits | ( | s, | |||
value, | |||||
length | ) |
Value:
{ int len = length;\ if (s->bi_valid > (int)Buf_size - len) {\ int val = value;\ s->bi_buf |= (val << s->bi_valid);\ put_short(s, s->bi_buf);\ s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ s->bi_valid += len - Buf_size;\ } else {\ s->bi_buf |= (value) << s->bi_valid;\ s->bi_valid += len;\ }\ }
Definition at line 214 of file trees.cc.
Referenced by _tr_align(), _tr_flush_block(), _tr_stored_block(), compress_block(), send_all_trees(), and send_tree().
#define send_code | ( | s, | |||
c, | |||||
tree | ) | send_bits(s, tree[c].Code, tree[c].Len) |
Definition at line 167 of file trees.cc.
Referenced by _tr_align(), compress_block(), and send_tree().
#define smaller | ( | tree, | |||
n, | |||||
m, | |||||
depth | ) |
void _tr_align | ( | deflate_state * | s | ) |
Definition at line 864 of file trees.cc.
References bi_flush(), END_BLOCK, send_bits, send_code, and static_ltree.
Referenced by deflate().
00865 { 00866 send_bits(s, STATIC_TREES<<1, 3); 00867 send_code(s, END_BLOCK, static_ltree); 00868 #ifdef DEBUG 00869 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 00870 #endif 00871 bi_flush(s); 00872 /* Of the 10 bits for the empty block, we have already sent 00873 * (10 - bi_valid) bits. The lookahead for the last real code (before 00874 * the EOB of the previous block) was thus at least one plus the length 00875 * of the EOB plus what we have just sent of the empty static block. 00876 */ 00877 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 00878 send_bits(s, STATIC_TREES<<1, 3); 00879 send_code(s, END_BLOCK, static_ltree); 00880 #ifdef DEBUG 00881 s->compressed_len += 10L; 00882 #endif 00883 bi_flush(s); 00884 } 00885 s->last_eob_len = 7; 00886 }
void _tr_flush_block | ( | deflate_state * | s, | |
charf * | buf, | |||
ulg | stored_len, | |||
int | eof | |||
) |
Definition at line 892 of file trees.cc.
References _tr_stored_block(), bi_windup(), build_bl_tree(), build_tree(), compress_block(), init_block(), send_all_trees(), send_bits, set_data_type(), static_dtree, and static_ltree.
00893 { 00894 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 00895 int max_blindex = 0; /* index of last bit length code of non zero freq */ 00896 00897 /* Build the Huffman trees unless a stored block is forced */ 00898 if (s->level > 0) { 00899 00900 /* Check if the file is ascii or binary */ 00901 if (s->strm->data_type == Z_UNKNOWN) set_data_type(s); 00902 00903 /* Construct the literal and distance trees */ 00904 build_tree(s, (tree_desc *)(&(s->l_desc))); 00905 Tracev((stderr, (char*)"\nlit data: dyn %ld, stat %ld", s->opt_len, 00906 s->static_len)); 00907 00908 build_tree(s, (tree_desc *)(&(s->d_desc))); 00909 Tracev((stderr, (char*)"\ndist data: dyn %ld, stat %ld", s->opt_len, 00910 s->static_len)); 00911 /* At this point, opt_len and static_len are the total bit lengths of 00912 * the compressed block data, excluding the tree representations. 00913 */ 00914 00915 /* Build the bit length tree for the above two trees, and get the index 00916 * in bl_order of the last bit length code to send. 00917 */ 00918 max_blindex = build_bl_tree(s); 00919 00920 /* Determine the best encoding. Compute the block lengths in bytes. */ 00921 opt_lenb = (s->opt_len+3+7)>>3; 00922 static_lenb = (s->static_len+3+7)>>3; 00923 00924 Tracev((stderr, (char*)"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 00925 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 00926 s->last_lit)); 00927 00928 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 00929 00930 } else { 00931 Assert(buf != (char*)0, (char*)"lost buf"); 00932 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 00933 } 00934 00935 #ifdef FORCE_STORED 00936 if (buf != (char*)0) { /* force stored block */ 00937 #else 00938 if (stored_len+4 <= opt_lenb && buf != (char*)0) { 00939 /* 4: two words for the lengths */ 00940 #endif 00941 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 00942 * Otherwise we can't have processed more than WSIZE input bytes since 00943 * the last block flush, because compression would have been 00944 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 00945 * transform a block into a stored block. 00946 */ 00947 _tr_stored_block(s, buf, stored_len, eof); 00948 00949 #ifdef FORCE_STATIC 00950 } else if (static_lenb >= 0) { /* force static trees */ 00951 #else 00952 } else if (static_lenb == opt_lenb) { 00953 #endif 00954 send_bits(s, (STATIC_TREES<<1)+eof, 3); 00955 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 00956 #ifdef DEBUG 00957 s->compressed_len += 3 + s->static_len; 00958 #endif 00959 } else { 00960 send_bits(s, (DYN_TREES<<1)+eof, 3); 00961 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 00962 max_blindex+1); 00963 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 00964 #ifdef DEBUG 00965 s->compressed_len += 3 + s->opt_len; 00966 #endif 00967 } 00968 Assert (s->compressed_len == s->bits_sent, (char*)"bad compressed size"); 00969 /* The above check is made mod 2^32, for files larger than 512 MB 00970 * and uLong implemented on 32 bits. 00971 */ 00972 init_block(s); 00973 00974 if (eof) { 00975 bi_windup(s); 00976 #ifdef DEBUG 00977 s->compressed_len += 7; /* align on byte boundary */ 00978 #endif 00979 } 00980 Tracev((stderr,(char*)"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 00981 s->compressed_len-7*eof)); 00982 }
void _tr_init | ( | deflate_state * | s | ) |
Definition at line 379 of file trees.cc.
References init_block(), static_bl_desc, static_d_desc, static_l_desc, and tr_static_init().
Referenced by deflateReset().
00380 { 00381 tr_static_init(); 00382 00383 s->l_desc.dyn_tree = s->dyn_ltree; 00384 s->l_desc.stat_desc = &static_l_desc; 00385 00386 s->d_desc.dyn_tree = s->dyn_dtree; 00387 s->d_desc.stat_desc = &static_d_desc; 00388 00389 s->bl_desc.dyn_tree = s->bl_tree; 00390 s->bl_desc.stat_desc = &static_bl_desc; 00391 00392 s->bi_buf = 0; 00393 s->bi_valid = 0; 00394 s->last_eob_len = 8; /* enough lookahead for inflate */ 00395 #ifdef DEBUG 00396 s->compressed_len = 0L; 00397 s->bits_sent = 0L; 00398 #endif 00399 00400 /* Initialize the first block of the first file: */ 00401 init_block(s); 00402 }
void _tr_stored_block | ( | deflate_state * | s, | |
charf * | buf, | |||
ulg | stored_len, | |||
int | eof | |||
) |
Definition at line 843 of file trees.cc.
References copy_block(), and send_bits.
Referenced by _tr_flush_block(), and deflate().
00844 { 00845 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 00846 #ifdef DEBUG 00847 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 00848 s->compressed_len += (stored_len + 4) << 3; 00849 #endif 00850 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 00851 }
int _tr_tally | ( | deflate_state * | s, | |
unsigned | dist, | |||
unsigned | lc | |||
) |
Definition at line 988 of file trees.cc.
References _length_code, and extra_dbits.
00989 { 00990 s->d_buf[s->last_lit] = (ush)dist; 00991 s->l_buf[s->last_lit++] = (uch)lc; 00992 if (dist == 0) { 00993 /* lc is the unmatched char */ 00994 s->dyn_ltree[lc].Freq++; 00995 } else { 00996 s->matches++; 00997 /* Here, lc is the match length - MIN_MATCH */ 00998 dist--; /* dist = match distance - 1 */ 00999 Assert((ush)dist < (ush)MAX_DIST(s) && 01000 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 01001 (ush)d_code(dist) < (ush)D_CODES, (char*)"_tr_tally: bad match"); 01002 01003 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 01004 s->dyn_dtree[d_code(dist)].Freq++; 01005 } 01006 01007 #ifdef TRUNCATE_BLOCK 01008 /* Try to guess if it is profitable to stop the current block here */ 01009 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { 01010 /* Compute an upper bound for the compressed length */ 01011 ulg out_length = (ulg)s->last_lit*8L; 01012 ulg in_length = (ulg)((long)s->strstart - s->block_start); 01013 int dcode; 01014 for (dcode = 0; dcode < D_CODES; dcode++) { 01015 out_length += (ulg)s->dyn_dtree[dcode].Freq * 01016 (5L+extra_dbits[dcode]); 01017 } 01018 out_length >>= 3; 01019 Tracev((stderr,(char*)"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 01020 s->last_lit, in_length, out_length, 01021 100L - out_length*100L/in_length)); 01022 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 01023 } 01024 #endif 01025 return (s->last_lit == s->lit_bufsize-1); 01026 /* We avoid equality with lit_bufsize because of wraparound at 64K 01027 * on 16 bit machines and because stored blocks are restricted to 01028 * 64K-1 bytes. 01029 */ 01030 }
local void bi_flush | ( | deflate_state * | s | ) |
Definition at line 1115 of file trees.cc.
References put_short.
Referenced by _tr_align().
01116 { 01117 if (s->bi_valid == 16) { 01118 put_short(s, s->bi_buf); 01119 s->bi_buf = 0; 01120 s->bi_valid = 0; 01121 } else if (s->bi_valid >= 8) { 01122 put_byte(s, (Byte)s->bi_buf); 01123 s->bi_buf >>= 8; 01124 s->bi_valid -= 8; 01125 } 01126 }
local unsigned bi_reverse | ( | unsigned | code, | |
int | len | |||
) |
Definition at line 1102 of file trees.cc.
Referenced by gen_codes(), and tr_static_init().
01103 { 01104 register unsigned res = 0; 01105 do { 01106 res |= code & 1; 01107 code >>= 1, res <<= 1; 01108 } while (--len > 0); 01109 return res >> 1; 01110 }
local void bi_windup | ( | deflate_state * | s | ) |
Definition at line 1131 of file trees.cc.
References put_short.
Referenced by _tr_flush_block(), and copy_block().
01132 { 01133 if (s->bi_valid > 8) { 01134 put_short(s, s->bi_buf); 01135 } else if (s->bi_valid > 0) { 01136 put_byte(s, (Byte)s->bi_buf); 01137 } 01138 s->bi_buf = 0; 01139 s->bi_valid = 0; 01140 #ifdef DEBUG 01141 s->bits_sent = (s->bits_sent+7) & ~7; 01142 #endif 01143 }
local int build_bl_tree | ( | deflate_state * | s | ) |
Definition at line 782 of file trees.cc.
References bl_order, build_tree(), and scan_tree().
Referenced by _tr_flush_block().
00783 { 00784 int max_blindex; /* index of last bit length code of non zero freq */ 00785 00786 /* Determine the bit length frequencies for literal and distance trees */ 00787 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 00788 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 00789 00790 /* Build the bit length tree: */ 00791 build_tree(s, (tree_desc *)(&(s->bl_desc))); 00792 /* opt_len now includes the length of the tree representations, except 00793 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 00794 */ 00795 00796 /* Determine the number of bit length codes to send. The pkzip format 00797 * requires that at least 4 bit length codes be sent. (appnote.txt says 00798 * 3 but the actual value used is 4.) 00799 */ 00800 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 00801 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 00802 } 00803 /* Update opt_len to include the bit length tree and counts */ 00804 s->opt_len += 3*(max_blindex+1) + 5+5+4; 00805 Tracev((stderr, (char*)"\ndyn trees: dyn %ld, stat %ld", 00806 s->opt_len, s->static_len)); 00807 00808 return max_blindex; 00809 }
local void build_tree | ( | deflate_state * | s, | |
tree_desc * | desc | |||
) |
Definition at line 606 of file trees.cc.
References CLHEP::detail::n.
Referenced by _tr_flush_block(), and build_bl_tree().
00607 { 00608 ct_data *tree = desc->dyn_tree; 00609 const ct_data *stree = desc->stat_desc->static_tree; 00610 int elems = desc->stat_desc->elems; 00611 int n, m; /* iterate over heap elements */ 00612 int max_code = -1; /* largest code with non zero frequency */ 00613 int node; /* new node being created */ 00614 00615 /* Construct the initial heap, with least frequent element in 00616 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 00617 * heap[0] is not used. 00618 */ 00619 s->heap_len = 0, s->heap_max = HEAP_SIZE; 00620 00621 for (n = 0; n < elems; n++) { 00622 if (tree[n].Freq != 0) { 00623 s->heap[++(s->heap_len)] = max_code = n; 00624 s->depth[n] = 0; 00625 } else { 00626 tree[n].Len = 0; 00627 } 00628 } 00629 00630 /* The pkzip format requires that at least one distance code exists, 00631 * and that at least one bit should be sent even if there is only one 00632 * possible code. So to avoid special checks later on we force at least 00633 * two codes of non zero frequency. 00634 */ 00635 while (s->heap_len < 2) { 00636 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 00637 tree[node].Freq = 1; 00638 s->depth[node] = 0; 00639 s->opt_len--; if (stree) s->static_len -= stree[node].Len; 00640 /* node is 0 or 1 so it does not have extra bits */ 00641 } 00642 desc->max_code = max_code; 00643 00644 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 00645 * establish sub-heaps of increasing lengths: 00646 */ 00647 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 00648 00649 /* Construct the Huffman tree by repeatedly combining the least two 00650 * frequent nodes. 00651 */ 00652 node = elems; /* next internal node of the tree */ 00653 do { 00654 pqremove(s, tree, n); /* n = node of least frequency */ 00655 m = s->heap[SMALLEST]; /* m = node of next least frequency */ 00656 00657 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 00658 s->heap[--(s->heap_max)] = m; 00659 00660 /* Create a new node father of n and m */ 00661 tree[node].Freq = tree[n].Freq + tree[m].Freq; 00662 s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ? 00663 s->depth[n] : s->depth[m]) + 1); 00664 tree[n].Dad = tree[m].Dad = (ush)node; 00665 #ifdef DUMP_BL_TREE 00666 if (tree == s->bl_tree) { 00667 fprintf(stderr,(char*)"\nnode %d(%d), sons %d(%d) %d(%d)", 00668 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 00669 } 00670 #endif 00671 /* and insert the new node in the heap */ 00672 s->heap[SMALLEST] = node++; 00673 pqdownheap(s, tree, SMALLEST); 00674 00675 } while (s->heap_len >= 2); 00676 00677 s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 00678 00679 /* At this point, the fields freq and dad are set. We can now 00680 * generate the bit lengths. 00681 */ 00682 gen_bitlen(s, (tree_desc *)desc); 00683 00684 /* The field len is now set, we can generate the bit codes */ 00685 gen_codes ((ct_data *)tree, max_code, s->bl_count); 00686 }
local void compress_block | ( | deflate_state * | s, | |
ct_data * | ltree, | |||
ct_data * | dtree | |||
) |
Definition at line 1035 of file trees.cc.
References _length_code, base_dist, base_length, END_BLOCK, extra_dbits, extra_lbits, send_bits, and send_code.
Referenced by _tr_flush_block().
01036 { 01037 unsigned dist; /* distance of matched string */ 01038 int lc; /* match length or unmatched char (if dist == 0) */ 01039 unsigned lx = 0; /* running index in l_buf */ 01040 unsigned code; /* the code to send */ 01041 int extra; /* number of extra bits to send */ 01042 01043 if (s->last_lit != 0) do { 01044 dist = s->d_buf[lx]; 01045 lc = s->l_buf[lx++]; 01046 if (dist == 0) { 01047 send_code(s, lc, ltree); /* send a literal byte */ 01048 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 01049 } else { 01050 /* Here, lc is the match length - MIN_MATCH */ 01051 code = _length_code[lc]; 01052 send_code(s, code+LITERALS+1, ltree); /* send the length code */ 01053 extra = extra_lbits[code]; 01054 if (extra != 0) { 01055 lc -= base_length[code]; 01056 send_bits(s, lc, extra); /* send the extra length bits */ 01057 } 01058 dist--; /* dist is now the match distance - 1 */ 01059 code = d_code(dist); 01060 Assert (code < D_CODES, (char*)"bad d_code"); 01061 01062 send_code(s, code, dtree); /* send the distance code */ 01063 extra = extra_dbits[code]; 01064 if (extra != 0) { 01065 dist -= base_dist[code]; 01066 send_bits(s, dist, extra); /* send the extra distance bits */ 01067 } 01068 } /* literal or match pair ? */ 01069 01070 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 01071 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 01072 (char*)"pendingBuf overflow"); 01073 01074 } while (lx < s->last_lit); 01075 01076 send_code(s, END_BLOCK, ltree); 01077 s->last_eob_len = ltree[END_BLOCK].Len; 01078 }
local void copy_block | ( | deflate_state * | s, | |
charf * | buf, | |||
unsigned | len, | |||
int | header | |||
) |
Definition at line 1149 of file trees.cc.
References bi_windup(), and put_short.
Referenced by _tr_stored_block().
01150 { 01151 bi_windup(s); /* align on byte boundary */ 01152 s->last_eob_len = 8; /* enough lookahead for inflate */ 01153 01154 if (header) { 01155 put_short(s, (ush)len); 01156 put_short(s, (ush)~len); 01157 #ifdef DEBUG 01158 s->bits_sent += 2*16; 01159 #endif 01160 } 01161 #ifdef DEBUG 01162 s->bits_sent += (ulg)len<<3; 01163 #endif 01164 while (len--) { 01165 put_byte(s, *buf++); 01166 } 01167 }
local void gen_bitlen | ( | deflate_state * | s, | |
tree_desc * | desc | |||
) |
Definition at line 482 of file trees.cc.
References CLHEP::detail::n.
00483 { 00484 ct_data *tree = desc->dyn_tree; 00485 int max_code = desc->max_code; 00486 const ct_data *stree = desc->stat_desc->static_tree; 00487 const intf *extra = desc->stat_desc->extra_bits; 00488 int base = desc->stat_desc->extra_base; 00489 int max_length = desc->stat_desc->max_length; 00490 int h; /* heap index */ 00491 int n, m; /* iterate over the tree elements */ 00492 int bits; /* bit length */ 00493 int xbits; /* extra bits */ 00494 ush f; /* frequency */ 00495 int overflow = 0; /* number of elements with bit length too large */ 00496 00497 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 00498 00499 /* In a first pass, compute the optimal bit lengths (which may 00500 * overflow in the case of the bit length tree). 00501 */ 00502 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 00503 00504 for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 00505 n = s->heap[h]; 00506 bits = tree[tree[n].Dad].Len + 1; 00507 if (bits > max_length) bits = max_length, overflow++; 00508 tree[n].Len = (ush)bits; 00509 /* We overwrite tree[n].Dad which is no longer needed */ 00510 00511 if (n > max_code) continue; /* not a leaf node */ 00512 00513 s->bl_count[bits]++; 00514 xbits = 0; 00515 if (n >= base) xbits = extra[n-base]; 00516 f = tree[n].Freq; 00517 s->opt_len += (ulg)f * (bits + xbits); 00518 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 00519 } 00520 if (overflow == 0) return; 00521 00522 Trace((stderr,(char*)"\nbit length overflow\n")); 00523 /* This happens for example on obj2 and pic of the Calgary corpus */ 00524 00525 /* Find the first bit length which could increase: */ 00526 do { 00527 bits = max_length-1; 00528 while (s->bl_count[bits] == 0) bits--; 00529 s->bl_count[bits]--; /* move one leaf down the tree */ 00530 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 00531 s->bl_count[max_length]--; 00532 /* The brother of the overflow item also moves one step up, 00533 * but this does not affect bl_count[max_length] 00534 */ 00535 overflow -= 2; 00536 } while (overflow > 0); 00537 00538 /* Now recompute all bit lengths, scanning in increasing frequency. 00539 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 00540 * lengths instead of fixing only the wrong ones. This idea is taken 00541 * from 'ar' written by Haruhiko Okumura.) 00542 */ 00543 for (bits = max_length; bits != 0; bits--) { 00544 n = s->bl_count[bits]; 00545 while (n != 0) { 00546 m = s->heap[--h]; 00547 if (m > max_code) continue; 00548 if (tree[m].Len != (unsigned) bits) { 00549 Trace((stderr,(char*)"code %d bits %d->%d\n", m, tree[m].Len, bits)); 00550 s->opt_len += ((long)bits - (long)tree[m].Len) 00551 *(long)tree[m].Freq; 00552 tree[m].Len = (ush)bits; 00553 } 00554 n--; 00555 } 00556 } 00557 }
local void gen_codes | ( | ct_data * | tree, | |
int | max_code, | |||
ushf * | bl_count | |||
) |
Definition at line 567 of file trees.cc.
References bi_reverse(), CLHEP::detail::n, and static_ltree.
Referenced by tr_static_init().
00568 { 00569 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 00570 ush code = 0; /* running code value */ 00571 int bits; /* bit index */ 00572 int n; /* code index */ 00573 00574 /* The distribution counts are first used to generate the code values 00575 * without bit reversal. 00576 */ 00577 for (bits = 1; bits <= MAX_BITS; bits++) { 00578 next_code[bits] = code = (code + bl_count[bits-1]) << 1; 00579 } 00580 /* Check that the bit counts in bl_count are consistent. The last code 00581 * must be all ones. 00582 */ 00583 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 00584 (char*)"inconsistent bit counts"); 00585 Tracev((stderr,(char*)"\ngen_codes: max_code %d ", max_code)); 00586 00587 for (n = 0; n <= max_code; n++) { 00588 int len = tree[n].Len; 00589 if (len == 0) continue; 00590 /* Now reverse the bits */ 00591 tree[n].Code = bi_reverse(next_code[len]++, len); 00592 00593 Tracecv(tree != static_ltree, (stderr,(char*)"\nn %3d %c l %2d c %4x (%x) ", 00594 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 00595 } 00596 }
local void init_block | ( | deflate_state * | s | ) |
Definition at line 407 of file trees.cc.
References END_BLOCK, and CLHEP::detail::n.
Referenced by _tr_flush_block(), and _tr_init().
00408 { 00409 int n; /* iterates over tree elements */ 00410 00411 /* Initialize the trees. */ 00412 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 00413 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 00414 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 00415 00416 s->dyn_ltree[END_BLOCK].Freq = 1; 00417 s->opt_len = s->static_len = 0L; 00418 s->last_lit = s->matches = 0; 00419 }
local void copy_block OF | ( | (deflate_state *s, charf *buf, unsigned len, int header) | ) |
local unsigned bi_reverse OF | ( | (unsigned value, int length) | ) |
local void compress_block OF | ( | (deflate_state *s, ct_data *ltree, ct_data *dtree) | ) |
local void send_all_trees OF | ( | (deflate_state *s, int lcodes, int dcodes, int blcodes) | ) |
local void scan_tree OF | ( | (deflate_state *s, ct_data *tree, int max_code) | ) |
local void gen_codes OF | ( | (ct_data *tree, int max_code, ushf *bl_count) | ) |
local void gen_bitlen OF | ( | (deflate_state *s, tree_desc *desc) | ) |
local void pqdownheap OF | ( | (deflate_state *s, ct_data *tree, int k) | ) |
local void init_block OF | ( | (deflate_state *s) | ) |
local void tr_static_init OF | ( | (void) | ) |
local void pqdownheap | ( | deflate_state * | s, | |
ct_data * | tree, | |||
int | k | |||
) |
Definition at line 450 of file trees.cc.
References smaller.
00451 { 00452 int v = s->heap[k]; 00453 int j = k << 1; /* left son of k */ 00454 while (j <= s->heap_len) { 00455 /* Set j to the smallest of the two sons: */ 00456 if (j < s->heap_len && 00457 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 00458 j++; 00459 } 00460 /* Exit if v is smaller than both sons */ 00461 if (smaller(tree, v, s->heap[j], s->depth)) break; 00462 00463 /* Exchange v with the smallest son */ 00464 s->heap[k] = s->heap[j]; k = j; 00465 00466 /* And continue down the tree, setting j to the left son of k */ 00467 j <<= 1; 00468 } 00469 s->heap[k] = v; 00470 }
local void scan_tree | ( | deflate_state * | s, | |
ct_data * | tree, | |||
int | max_code | |||
) |
Definition at line 692 of file trees.cc.
References CLHEP::detail::n, REP_3_6, REPZ_11_138, and REPZ_3_10.
Referenced by build_bl_tree().
00693 { 00694 int n; /* iterates over all tree elements */ 00695 int prevlen = -1; /* last emitted length */ 00696 int curlen; /* length of current code */ 00697 int nextlen = tree[0].Len; /* length of next code */ 00698 int count = 0; /* repeat count of the current code */ 00699 int max_count = 7; /* max repeat count */ 00700 int min_count = 4; /* min repeat count */ 00701 00702 if (nextlen == 0) max_count = 138, min_count = 3; 00703 tree[max_code+1].Len = (ush)0xffff; /* guard */ 00704 00705 for (n = 0; n <= max_code; n++) { 00706 curlen = nextlen; nextlen = tree[n+1].Len; 00707 if (++count < max_count && curlen == nextlen) { 00708 continue; 00709 } else if (count < min_count) { 00710 s->bl_tree[curlen].Freq += count; 00711 } else if (curlen != 0) { 00712 if (curlen != prevlen) s->bl_tree[curlen].Freq++; 00713 s->bl_tree[REP_3_6].Freq++; 00714 } else if (count <= 10) { 00715 s->bl_tree[REPZ_3_10].Freq++; 00716 } else { 00717 s->bl_tree[REPZ_11_138].Freq++; 00718 } 00719 count = 0; prevlen = curlen; 00720 if (nextlen == 0) { 00721 max_count = 138, min_count = 3; 00722 } else if (curlen == nextlen) { 00723 max_count = 6, min_count = 3; 00724 } else { 00725 max_count = 7, min_count = 4; 00726 } 00727 } 00728 }
local void send_all_trees | ( | deflate_state * | s, | |
int | lcodes, | |||
int | dcodes, | |||
int | blcodes | |||
) |
Definition at line 816 of file trees.cc.
References bl_order, send_bits, and send_tree().
Referenced by _tr_flush_block().
00817 { 00818 int rank; /* index in bl_order */ 00819 00820 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, (char*)"not enough codes"); 00821 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 00822 (char*)"too many codes"); 00823 Tracev((stderr, (char*)"\nbl counts: ")); 00824 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 00825 send_bits(s, dcodes-1, 5); 00826 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 00827 for (rank = 0; rank < blcodes; rank++) { 00828 Tracev((stderr, (char*)"\nbl code %2d ", bl_order[rank])); 00829 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 00830 } 00831 Tracev((stderr, (char*)"\nbl tree: sent %ld", s->bits_sent)); 00832 00833 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 00834 Tracev((stderr, (char*)"\nlit tree: sent %ld", s->bits_sent)); 00835 00836 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 00837 Tracev((stderr, (char*)"\ndist tree: sent %ld", s->bits_sent)); 00838 }
local void send_tree | ( | deflate_state * | s, | |
ct_data * | tree, | |||
int | max_code | |||
) |
Definition at line 734 of file trees.cc.
References CLHEP::detail::n, REP_3_6, REPZ_11_138, REPZ_3_10, send_bits, and send_code.
Referenced by send_all_trees().
00735 { 00736 int n; /* iterates over all tree elements */ 00737 int prevlen = -1; /* last emitted length */ 00738 int curlen; /* length of current code */ 00739 int nextlen = tree[0].Len; /* length of next code */ 00740 int count = 0; /* repeat count of the current code */ 00741 int max_count = 7; /* max repeat count */ 00742 int min_count = 4; /* min repeat count */ 00743 00744 /* tree[max_code+1].Len = -1; */ /* guard already set */ 00745 if (nextlen == 0) max_count = 138, min_count = 3; 00746 00747 for (n = 0; n <= max_code; n++) { 00748 curlen = nextlen; nextlen = tree[n+1].Len; 00749 if (++count < max_count && curlen == nextlen) { 00750 continue; 00751 } else if (count < min_count) { 00752 do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 00753 00754 } else if (curlen != 0) { 00755 if (curlen != prevlen) { 00756 send_code(s, curlen, s->bl_tree); count--; 00757 } 00758 Assert(count >= 3 && count <= 6, (char*)" 3_6?"); 00759 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 00760 00761 } else if (count <= 10) { 00762 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 00763 00764 } else { 00765 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 00766 } 00767 count = 0; prevlen = curlen; 00768 if (nextlen == 0) { 00769 max_count = 138, min_count = 3; 00770 } else if (curlen == nextlen) { 00771 max_count = 6, min_count = 3; 00772 } else { 00773 max_count = 7, min_count = 4; 00774 } 00775 } 00776 }
local void set_data_type | ( | deflate_state * | s | ) |
Definition at line 1086 of file trees.cc.
References CLHEP::detail::n.
Referenced by _tr_flush_block().
01087 { 01088 int n = 0; 01089 unsigned ascii_freq = 0; 01090 unsigned bin_freq = 0; 01091 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 01092 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 01093 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 01094 s->strm->data_type = bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII; 01095 }
local void tr_static_init | ( | ) |
Definition at line 235 of file trees.cc.
References _dist_code, _length_code, base_dist, base_length, bi_reverse(), extra_blbits, extra_dbits, extra_lbits, gen_codes(), CLHEP::detail::n, static_bl_desc, static_d_desc, static_dtree, static_l_desc, and static_ltree.
Referenced by _tr_init().
00236 { 00237 #if defined(GEN_TREES_H) || !defined(STDC) 00238 static int static_init_done = 0; 00239 int n; /* iterates over tree elements */ 00240 int bits; /* bit counter */ 00241 int length; /* length value */ 00242 int code; /* code value */ 00243 int dist; /* distance index */ 00244 ush bl_count[MAX_BITS+1]; 00245 /* number of codes at each bit length for an optimal tree */ 00246 00247 if (static_init_done) return; 00248 00249 /* For some embedded targets, global variables are not initialized: */ 00250 static_l_desc.static_tree = static_ltree; 00251 static_l_desc.extra_bits = extra_lbits; 00252 static_d_desc.static_tree = static_dtree; 00253 static_d_desc.extra_bits = extra_dbits; 00254 static_bl_desc.extra_bits = extra_blbits; 00255 00256 /* Initialize the mapping length (0..255) -> length code (0..28) */ 00257 length = 0; 00258 for (code = 0; code < LENGTH_CODES-1; code++) { 00259 base_length[code] = length; 00260 for (n = 0; n < (1<<extra_lbits[code]); n++) { 00261 _length_code[length++] = (uch)code; 00262 } 00263 } 00264 Assert (length == 256, (char*)"tr_static_init: length != 256"); 00265 /* Note that the length 255 (match length 258) can be represented 00266 * in two different ways: code 284 + 5 bits or code 285, so we 00267 * overwrite length_code[255] to use the best encoding: 00268 */ 00269 _length_code[length-1] = (uch)code; 00270 00271 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 00272 dist = 0; 00273 for (code = 0 ; code < 16; code++) { 00274 base_dist[code] = dist; 00275 for (n = 0; n < (1<<extra_dbits[code]); n++) { 00276 _dist_code[dist++] = (uch)code; 00277 } 00278 } 00279 Assert (dist == 256, (char*)"tr_static_init: dist != 256"); 00280 dist >>= 7; /* from now on, all distances are divided by 128 */ 00281 for ( ; code < D_CODES; code++) { 00282 base_dist[code] = dist << 7; 00283 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 00284 _dist_code[256 + dist++] = (uch)code; 00285 } 00286 } 00287 Assert (dist == 256, (char*)"tr_static_init: 256+dist != 512"); 00288 00289 /* Construct the codes of the static literal tree */ 00290 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 00291 n = 0; 00292 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 00293 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 00294 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 00295 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 00296 /* Codes 286 and 287 do not exist, but we must include them in the 00297 * tree construction to get a canonical Huffman tree (longest code 00298 * all ones) 00299 */ 00300 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 00301 00302 /* The static distance tree is trivial: */ 00303 for (n = 0; n < D_CODES; n++) { 00304 static_dtree[n].Len = 5; 00305 static_dtree[n].Code = bi_reverse((unsigned)n, 5); 00306 } 00307 static_init_done = 1; 00308 00309 # ifdef GEN_TREES_H 00310 gen_trees_header(); 00311 # endif 00312 #endif /* defined(GEN_TREES_H) || !defined(STDC) */ 00313 }
uch _dist_code[DIST_CODE_LEN] |
uch _length_code[MAX_MATCH-MIN_MATCH+1] |
Definition at line 108 of file trees.cc.
Referenced by _tr_tally(), compress_block(), and tr_static_init().
local int base_dist[D_CODES] |
local int base_length[LENGTH_CODES] |
local const uch bl_order[BL_CODES] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15} |
local const int extra_blbits[BL_CODES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7} |
local const int extra_dbits[D_CODES] = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13} |
Definition at line 65 of file trees.cc.
Referenced by _tr_tally(), compress_block(), and tr_static_init().
local const int extra_lbits[LENGTH_CODES] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0} |
local static_tree_desc static_bl_desc |
Initial value:
{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}
Definition at line 135 of file trees.cc.
Referenced by _tr_init(), and tr_static_init().
local static_tree_desc static_d_desc |
Initial value:
{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}
Definition at line 132 of file trees.cc.
Referenced by _tr_init(), and tr_static_init().
local ct_data static_dtree[D_CODES] |
local static_tree_desc static_l_desc |
Initial value:
{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}
Definition at line 129 of file trees.cc.
Referenced by _tr_init(), and tr_static_init().
local ct_data static_ltree[L_CODES+2] |
Definition at line 90 of file trees.cc.
Referenced by _tr_align(), _tr_flush_block(), gen_codes(), and tr_static_init().