12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205 |
- #include "deflate.h"
- #ifdef ZLIB_DEBUG
- # include <ctype.h>
- #endif
- #define MAX_BL_BITS 7
- #define END_BLOCK 256
- #define REP_3_6 16
- #define REPZ_3_10 17
- #define REPZ_11_138 18
- 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};
- #define DIST_CODE_LEN 512
- #if defined(GEN_TREES_H) || !defined(STDC)
- 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];
- #else
- # include "trees.h"
- #endif
- struct static_tree_desc_s {
- const ct_data *static_tree;
- const intf *extra_bits;
- int extra_base;
- int elems;
- int max_length;
- };
- local const static_tree_desc static_l_desc =
- {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
- local const static_tree_desc static_d_desc =
- {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
- local const static_tree_desc static_bl_desc =
- {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
- 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 build_tree OF((deflate_state *s, tree_desc *desc));
- local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
- local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
- local int build_bl_tree OF((deflate_state *s));
- local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
- int blcodes));
- local void compress_block OF((deflate_state *s, const ct_data *ltree,
- const ct_data *dtree));
- local int detect_data_type OF((deflate_state *s));
- local unsigned bi_reverse OF((unsigned value, int length));
- local void bi_windup OF((deflate_state *s));
- local void bi_flush OF((deflate_state *s));
- #ifdef GEN_TREES_H
- local void gen_trees_header OF((void));
- #endif
- #ifndef ZLIB_DEBUG
- # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
-
- #else
- # define send_code(s, c, tree) \
- { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
- send_bits(s, tree[c].Code, tree[c].Len); }
- #endif
- #define put_short(s, w) { \
- put_byte(s, (uch)((w) & 0xff)); \
- put_byte(s, (uch)((ush)(w) >> 8)); \
- }
- #ifdef ZLIB_DEBUG
- local void send_bits OF((deflate_state *s, int value, int length));
- local void send_bits(
- deflate_state *s,
- int value,
- int length)
- {
- Tracevv((stderr," l %2d v %4x ", length, value));
- Assert(length > 0 && length <= 15, "invalid length");
- s->bits_sent += (ulg)length;
-
- if (s->bi_valid > (int)Buf_size - length) {
- s->bi_buf |= (ush)value << s->bi_valid;
- put_short(s, s->bi_buf);
- s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
- s->bi_valid += length - Buf_size;
- } else {
- s->bi_buf |= (ush)value << s->bi_valid;
- s->bi_valid += length;
- }
- }
- #else
- #define send_bits(s, value, length) \
- { int len = length;\
- if (s->bi_valid > (int)Buf_size - len) {\
- int val = (int)value;\
- s->bi_buf |= (ush)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 |= (ush)(value) << s->bi_valid;\
- s->bi_valid += len;\
- }\
- }
- #endif
- local void tr_static_init()
- {
- #if defined(GEN_TREES_H) || !defined(STDC)
- static int static_init_done = 0;
- int n;
- int bits;
- int length;
- int code;
- int dist;
- ush bl_count[MAX_BITS+1];
-
- if (static_init_done) return;
-
- #ifdef NO_INIT_GLOBAL_POINTERS
- static_l_desc.static_tree = static_ltree;
- static_l_desc.extra_bits = extra_lbits;
- static_d_desc.static_tree = static_dtree;
- static_d_desc.extra_bits = extra_dbits;
- static_bl_desc.extra_bits = extra_blbits;
- #endif
-
- length = 0;
- for (code = 0; code < LENGTH_CODES-1; code++) {
- base_length[code] = length;
- for (n = 0; n < (1<<extra_lbits[code]); n++) {
- _length_code[length++] = (uch)code;
- }
- }
- Assert (length == 256, "tr_static_init: length != 256");
-
- _length_code[length-1] = (uch)code;
-
- dist = 0;
- for (code = 0 ; code < 16; code++) {
- base_dist[code] = dist;
- for (n = 0; n < (1<<extra_dbits[code]); n++) {
- _dist_code[dist++] = (uch)code;
- }
- }
- Assert (dist == 256, "tr_static_init: dist != 256");
- dist >>= 7;
- for ( ; code < D_CODES; code++) {
- base_dist[code] = dist << 7;
- for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
- _dist_code[256 + dist++] = (uch)code;
- }
- }
- Assert (dist == 256, "tr_static_init: 256+dist != 512");
-
- for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
- n = 0;
- while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
- while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
- while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
- while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
-
- gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
-
- for (n = 0; n < D_CODES; n++) {
- static_dtree[n].Len = 5;
- static_dtree[n].Code = bi_reverse((unsigned)n, 5);
- }
- static_init_done = 1;
- # ifdef GEN_TREES_H
- gen_trees_header();
- # endif
- #endif
- }
- #ifdef GEN_TREES_H
- # ifndef ZLIB_DEBUG
- # include <stdio.h>
- # endif
- # define SEPARATOR(i, last, width) \
- ((i) == (last)? "\n};\n\n" : \
- ((i) % (width) == (width)-1 ? ",\n" : ", "))
- void gen_trees_header()
- {
- FILE *header = fopen("trees.h", "w");
- int i;
- Assert (header != NULL, "Can't open trees.h");
- fprintf(header,
- "/* header created automatically with -DGEN_TREES_H */\n\n");
- fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
- for (i = 0; i < L_CODES+2; i++) {
- fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
- static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
- }
- fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
- for (i = 0; i < D_CODES; i++) {
- fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
- static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
- }
- fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
- for (i = 0; i < DIST_CODE_LEN; i++) {
- fprintf(header, "%2u%s", _dist_code[i],
- SEPARATOR(i, DIST_CODE_LEN-1, 20));
- }
- fprintf(header,
- "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
- for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
- fprintf(header, "%2u%s", _length_code[i],
- SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
- }
- fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
- for (i = 0; i < LENGTH_CODES; i++) {
- fprintf(header, "%1u%s", base_length[i],
- SEPARATOR(i, LENGTH_CODES-1, 20));
- }
- fprintf(header, "local const int base_dist[D_CODES] = {\n");
- for (i = 0; i < D_CODES; i++) {
- fprintf(header, "%5u%s", base_dist[i],
- SEPARATOR(i, D_CODES-1, 10));
- }
- fclose(header);
- }
- #endif
- void ZLIB_INTERNAL _tr_init(
- deflate_state *s)
- {
- tr_static_init();
- s->l_desc.dyn_tree = s->dyn_ltree;
- s->l_desc.stat_desc = &static_l_desc;
- s->d_desc.dyn_tree = s->dyn_dtree;
- s->d_desc.stat_desc = &static_d_desc;
- s->bl_desc.dyn_tree = s->bl_tree;
- s->bl_desc.stat_desc = &static_bl_desc;
- s->bi_buf = 0;
- s->bi_valid = 0;
- #ifdef ZLIB_DEBUG
- s->compressed_len = 0L;
- s->bits_sent = 0L;
- #endif
-
- init_block(s);
- }
- local void init_block(
- deflate_state *s)
- {
- int n;
-
- for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
- for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
- for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
- s->dyn_ltree[END_BLOCK].Freq = 1;
- s->opt_len = s->static_len = 0L;
- s->last_lit = s->matches = 0;
- }
- #define SMALLEST 1
- #define pqremove(s, tree, top) \
- {\
- top = s->heap[SMALLEST]; \
- s->heap[SMALLEST] = s->heap[s->heap_len--]; \
- pqdownheap(s, tree, SMALLEST); \
- }
- #define smaller(tree, n, m, depth) \
- (tree[n].Freq < tree[m].Freq || \
- (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
- local void pqdownheap(
- deflate_state *s,
- ct_data *tree,
- int k)
- {
- int v = s->heap[k];
- int j = k << 1;
- while (j <= s->heap_len) {
-
- if (j < s->heap_len &&
- smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
- j++;
- }
-
- if (smaller(tree, v, s->heap[j], s->depth)) break;
-
- s->heap[k] = s->heap[j]; k = j;
-
- j <<= 1;
- }
- s->heap[k] = v;
- }
- local void gen_bitlen(
- deflate_state *s,
- tree_desc *desc)
- {
- ct_data *tree = desc->dyn_tree;
- int max_code = desc->max_code;
- const ct_data *stree = desc->stat_desc->static_tree;
- const intf *extra = desc->stat_desc->extra_bits;
- int base = desc->stat_desc->extra_base;
- int max_length = desc->stat_desc->max_length;
- int h;
- int n, m;
- int bits;
- int xbits;
- ush f;
- int overflow = 0;
- for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
-
- tree[s->heap[s->heap_max]].Len = 0;
- for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
- n = s->heap[h];
- bits = tree[tree[n].Dad].Len + 1;
- if (bits > max_length) bits = max_length, overflow++;
- tree[n].Len = (ush)bits;
-
- if (n > max_code) continue;
- s->bl_count[bits]++;
- xbits = 0;
- if (n >= base) xbits = extra[n-base];
- f = tree[n].Freq;
- s->opt_len += (ulg)f * (unsigned)(bits + xbits);
- if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits);
- }
- if (overflow == 0) return;
- Tracev((stderr,"\nbit length overflow\n"));
-
-
- do {
- bits = max_length-1;
- while (s->bl_count[bits] == 0) bits--;
- s->bl_count[bits]--;
- s->bl_count[bits+1] += 2;
- s->bl_count[max_length]--;
-
- overflow -= 2;
- } while (overflow > 0);
-
- for (bits = max_length; bits != 0; bits--) {
- n = s->bl_count[bits];
- while (n != 0) {
- m = s->heap[--h];
- if (m > max_code) continue;
- if ((unsigned) tree[m].Len != (unsigned) bits) {
- Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
- s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq;
- tree[m].Len = (ush)bits;
- }
- n--;
- }
- }
- }
- local void gen_codes (
- ct_data *tree,
- int max_code,
- ushf *bl_count)
- {
- ush next_code[MAX_BITS+1];
- unsigned code = 0;
- int bits;
- int n;
-
- for (bits = 1; bits <= MAX_BITS; bits++) {
- code = (code + bl_count[bits-1]) << 1;
- next_code[bits] = (ush)code;
- }
-
- Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
- "inconsistent bit counts");
- Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
- for (n = 0; n <= max_code; n++) {
- int len = tree[n].Len;
- if (len == 0) continue;
-
- tree[n].Code = (ush)bi_reverse(next_code[len]++, len);
- Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
- n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
- }
- }
- local void build_tree(
- deflate_state *s,
- tree_desc *desc)
- {
- ct_data *tree = desc->dyn_tree;
- const ct_data *stree = desc->stat_desc->static_tree;
- int elems = desc->stat_desc->elems;
- int n, m;
- int max_code = -1;
- int node;
-
- s->heap_len = 0, s->heap_max = HEAP_SIZE;
- for (n = 0; n < elems; n++) {
- if (tree[n].Freq != 0) {
- s->heap[++(s->heap_len)] = max_code = n;
- s->depth[n] = 0;
- } else {
- tree[n].Len = 0;
- }
- }
-
- while (s->heap_len < 2) {
- node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
- tree[node].Freq = 1;
- s->depth[node] = 0;
- s->opt_len--; if (stree) s->static_len -= stree[node].Len;
-
- }
- desc->max_code = max_code;
-
- for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
-
- node = elems;
- do {
- pqremove(s, tree, n);
- m = s->heap[SMALLEST];
- s->heap[--(s->heap_max)] = n;
- s->heap[--(s->heap_max)] = m;
-
- tree[node].Freq = tree[n].Freq + tree[m].Freq;
- s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
- s->depth[n] : s->depth[m]) + 1);
- tree[n].Dad = tree[m].Dad = (ush)node;
- #ifdef DUMP_BL_TREE
- if (tree == s->bl_tree) {
- fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
- node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
- }
- #endif
-
- s->heap[SMALLEST] = node++;
- pqdownheap(s, tree, SMALLEST);
- } while (s->heap_len >= 2);
- s->heap[--(s->heap_max)] = s->heap[SMALLEST];
-
- gen_bitlen(s, (tree_desc *)desc);
-
- gen_codes ((ct_data *)tree, max_code, s->bl_count);
- }
- local void scan_tree (
- deflate_state *s,
- ct_data *tree,
- int max_code)
- {
- int n;
- int prevlen = -1;
- int curlen;
- int nextlen = tree[0].Len;
- int count = 0;
- int max_count = 7;
- int min_count = 4;
- if (nextlen == 0) max_count = 138, min_count = 3;
- tree[max_code+1].Len = (ush)0xffff;
- for (n = 0; n <= max_code; n++) {
- curlen = nextlen; nextlen = tree[n+1].Len;
- if (++count < max_count && curlen == nextlen) {
- continue;
- } else if (count < min_count) {
- s->bl_tree[curlen].Freq += count;
- } else if (curlen != 0) {
- if (curlen != prevlen) s->bl_tree[curlen].Freq++;
- s->bl_tree[REP_3_6].Freq++;
- } else if (count <= 10) {
- s->bl_tree[REPZ_3_10].Freq++;
- } else {
- s->bl_tree[REPZ_11_138].Freq++;
- }
- count = 0; prevlen = curlen;
- if (nextlen == 0) {
- max_count = 138, min_count = 3;
- } else if (curlen == nextlen) {
- max_count = 6, min_count = 3;
- } else {
- max_count = 7, min_count = 4;
- }
- }
- }
- local void send_tree (
- deflate_state *s,
- ct_data *tree,
- int max_code)
- {
- int n;
- int prevlen = -1;
- int curlen;
- int nextlen = tree[0].Len;
- int count = 0;
- int max_count = 7;
- int min_count = 4;
-
- if (nextlen == 0) max_count = 138, min_count = 3;
- for (n = 0; n <= max_code; n++) {
- curlen = nextlen; nextlen = tree[n+1].Len;
- if (++count < max_count && curlen == nextlen) {
- continue;
- } else if (count < min_count) {
- do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
- } else if (curlen != 0) {
- if (curlen != prevlen) {
- send_code(s, curlen, s->bl_tree); count--;
- }
- Assert(count >= 3 && count <= 6, " 3_6?");
- send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
- } else if (count <= 10) {
- send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
- } else {
- send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
- }
- count = 0; prevlen = curlen;
- if (nextlen == 0) {
- max_count = 138, min_count = 3;
- } else if (curlen == nextlen) {
- max_count = 6, min_count = 3;
- } else {
- max_count = 7, min_count = 4;
- }
- }
- }
- local int build_bl_tree(
- deflate_state *s)
- {
- int max_blindex;
-
- scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
- scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
-
- build_tree(s, (tree_desc *)(&(s->bl_desc)));
-
-
- for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
- if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
- }
-
- s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4;
- Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
- s->opt_len, s->static_len));
- return max_blindex;
- }
- local void send_all_trees(
- deflate_state *s,
- int lcodes,
- int dcodes,
- int blcodes)
- {
- int rank;
- Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
- Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
- "too many codes");
- Tracev((stderr, "\nbl counts: "));
- send_bits(s, lcodes-257, 5);
- send_bits(s, dcodes-1, 5);
- send_bits(s, blcodes-4, 4);
- for (rank = 0; rank < blcodes; rank++) {
- Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
- send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
- }
- Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
- send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
- Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
- send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
- Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
- }
- void ZLIB_INTERNAL _tr_stored_block(
- deflate_state *s,
- charf *buf,
- ulg stored_len,
- int last)
- {
- send_bits(s, (STORED_BLOCK<<1)+last, 3);
- bi_windup(s);
- put_short(s, (ush)stored_len);
- put_short(s, (ush)~stored_len);
- zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
- s->pending += stored_len;
- #ifdef ZLIB_DEBUG
- s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
- s->compressed_len += (stored_len + 4) << 3;
- s->bits_sent += 2*16;
- s->bits_sent += stored_len<<3;
- #endif
- }
- void ZLIB_INTERNAL _tr_flush_bits(
- deflate_state *s)
- {
- bi_flush(s);
- }
- void ZLIB_INTERNAL _tr_align(
- deflate_state *s)
- {
- send_bits(s, STATIC_TREES<<1, 3);
- send_code(s, END_BLOCK, static_ltree);
- #ifdef ZLIB_DEBUG
- s->compressed_len += 10L;
- #endif
- bi_flush(s);
- }
- void ZLIB_INTERNAL _tr_flush_block(
- deflate_state *s,
- charf *buf,
- ulg stored_len,
- int last)
- {
- ulg opt_lenb, static_lenb;
- int max_blindex = 0;
-
- if (s->level > 0) {
-
- if (s->strm->data_type == Z_UNKNOWN)
- s->strm->data_type = detect_data_type(s);
-
- build_tree(s, (tree_desc *)(&(s->l_desc)));
- Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
- s->static_len));
- build_tree(s, (tree_desc *)(&(s->d_desc)));
- Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
- s->static_len));
-
-
- max_blindex = build_bl_tree(s);
-
- opt_lenb = (s->opt_len+3+7)>>3;
- static_lenb = (s->static_len+3+7)>>3;
- Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
- opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
- s->last_lit));
- if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
- } else {
- Assert(buf != (char*)0, "lost buf");
- opt_lenb = static_lenb = stored_len + 5;
- }
- #ifdef FORCE_STORED
- if (buf != (char*)0) {
- #else
- if (stored_len+4 <= opt_lenb && buf != (char*)0) {
-
- #endif
-
- _tr_stored_block(s, buf, stored_len, last);
- #ifdef FORCE_STATIC
- } else if (static_lenb >= 0) {
- #else
- } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
- #endif
- send_bits(s, (STATIC_TREES<<1)+last, 3);
- compress_block(s, (const ct_data *)static_ltree,
- (const ct_data *)static_dtree);
- #ifdef ZLIB_DEBUG
- s->compressed_len += 3 + s->static_len;
- #endif
- } else {
- send_bits(s, (DYN_TREES<<1)+last, 3);
- send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
- max_blindex+1);
- compress_block(s, (const ct_data *)s->dyn_ltree,
- (const ct_data *)s->dyn_dtree);
- #ifdef ZLIB_DEBUG
- s->compressed_len += 3 + s->opt_len;
- #endif
- }
- Assert (s->compressed_len == s->bits_sent, "bad compressed size");
-
- init_block(s);
- if (last) {
- bi_windup(s);
- #ifdef ZLIB_DEBUG
- s->compressed_len += 7;
- #endif
- }
- Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
- s->compressed_len-7*last));
- }
- int ZLIB_INTERNAL _tr_tally (
- deflate_state *s,
- unsigned dist,
- unsigned lc)
- {
- s->d_buf[s->last_lit] = (ush)dist;
- s->l_buf[s->last_lit++] = (uch)lc;
- if (dist == 0) {
-
- s->dyn_ltree[lc].Freq++;
- } else {
- s->matches++;
-
- dist--;
- Assert((ush)dist < (ush)MAX_DIST(s) &&
- (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
- (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
- s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
- s->dyn_dtree[d_code(dist)].Freq++;
- }
- #ifdef TRUNCATE_BLOCK
-
- if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
-
- ulg out_length = (ulg)s->last_lit*8L;
- ulg in_length = (ulg)((long)s->strstart - s->block_start);
- int dcode;
- for (dcode = 0; dcode < D_CODES; dcode++) {
- out_length += (ulg)s->dyn_dtree[dcode].Freq *
- (5L+extra_dbits[dcode]);
- }
- out_length >>= 3;
- Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
- s->last_lit, in_length, out_length,
- 100L - out_length*100L/in_length));
- if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
- }
- #endif
- return (s->last_lit == s->lit_bufsize-1);
-
- }
- local void compress_block(
- deflate_state *s,
- const ct_data *ltree,
- const ct_data *dtree)
- {
- unsigned dist;
- int lc;
- unsigned lx = 0;
- unsigned code;
- int extra;
- if (s->last_lit != 0) do {
- dist = s->d_buf[lx];
- lc = s->l_buf[lx++];
- if (dist == 0) {
- send_code(s, lc, ltree);
- Tracecv(isgraph(lc), (stderr," '%c' ", lc));
- } else {
-
- code = _length_code[lc];
- send_code(s, code+LITERALS+1, ltree);
- extra = extra_lbits[code];
- if (extra != 0) {
- lc -= base_length[code];
- send_bits(s, lc, extra);
- }
- dist--;
- code = d_code(dist);
- Assert (code < D_CODES, "bad d_code");
- send_code(s, code, dtree);
- extra = extra_dbits[code];
- if (extra != 0) {
- dist -= (unsigned)base_dist[code];
- send_bits(s, dist, extra);
- }
- }
-
- Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
- "pendingBuf overflow");
- } while (lx < s->last_lit);
- send_code(s, END_BLOCK, ltree);
- }
- local int detect_data_type(
- deflate_state *s)
- {
-
- unsigned long black_mask = 0xf3ffc07fUL;
- int n;
-
- for (n = 0; n <= 31; n++, black_mask >>= 1)
- if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
- return Z_BINARY;
-
- if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
- || s->dyn_ltree[13].Freq != 0)
- return Z_TEXT;
- for (n = 32; n < LITERALS; n++)
- if (s->dyn_ltree[n].Freq != 0)
- return Z_TEXT;
-
- return Z_BINARY;
- }
- local unsigned bi_reverse(
- unsigned code,
- int len)
- {
- register unsigned res = 0;
- do {
- res |= code & 1;
- code >>= 1, res <<= 1;
- } while (--len > 0);
- return res >> 1;
- }
- local void bi_flush(
- deflate_state *s)
- {
- if (s->bi_valid == 16) {
- put_short(s, s->bi_buf);
- s->bi_buf = 0;
- s->bi_valid = 0;
- } else if (s->bi_valid >= 8) {
- put_byte(s, (Byte)s->bi_buf);
- s->bi_buf >>= 8;
- s->bi_valid -= 8;
- }
- }
- local void bi_windup(
- deflate_state *s)
- {
- if (s->bi_valid > 8) {
- put_short(s, s->bi_buf);
- } else if (s->bi_valid > 0) {
- put_byte(s, (Byte)s->bi_buf);
- }
- s->bi_buf = 0;
- s->bi_valid = 0;
- #ifdef ZLIB_DEBUG
- s->bits_sent = (s->bits_sent+7) & ~7;
- #endif
- }
|