Prusa MINI Firmware overview
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
trees.c File Reference
#include "deflate.h"

Classes

struct  static_tree_desc_s
 

Macros

#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 DIST_CODE_LEN   512 /* see definition of array dist_code below */
 
#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

void tr_static_init OF ((void))
 
void init_block OF ((deflate_state *s))
 
void pqdownheap OF ((deflate_state *s, ct_data *tree, int k))
 
void gen_bitlen OF ((deflate_state *s, tree_desc *desc))
 
void gen_codes OF ((ct_data *tree, int max_code, ushf *bl_count))
 
void scan_tree OF ((deflate_state *s, ct_data *tree, int max_code))
 
void send_all_trees OF ((deflate_state *s, int lcodes, int dcodes, int blcodes))
 
void compress_block OF ((deflate_state *s, const ct_data *ltree, const ct_data *dtree))
 
unsigned bi_reverse OF ((unsigned value, int length))
 
void tr_static_init ()
 
void ZLIB_INTERNAL _tr_init (deflate_state *s)
 
void init_block (deflate_state *s)
 
void pqdownheap (deflate_state *s, ct_data *tree, int k)
 
void gen_bitlen (deflate_state *s, tree_desc *desc)
 
void gen_codes (ct_data *tree, int max_code, ushf *bl_count)
 
void build_tree (deflate_state *s, tree_desc *desc)
 
void scan_tree (deflate_state *s, ct_data *tree, int max_code)
 
void send_tree (deflate_state *s, ct_data *tree, int max_code)
 
int build_bl_tree (deflate_state *s)
 
void send_all_trees (deflate_state *s, int lcodes, int dcodes, int blcodes)
 
void ZLIB_INTERNAL _tr_stored_block (deflate_state *s, charf *buf, ulg stored_len, int last)
 
void ZLIB_INTERNAL _tr_flush_bits (deflate_state *s)
 
void ZLIB_INTERNAL _tr_align (deflate_state *s)
 
void ZLIB_INTERNAL _tr_flush_block (deflate_state *s, charf *buf, ulg stored_len, int last)
 
int ZLIB_INTERNAL _tr_tally (deflate_state *s, unsigned dist, unsigned lc)
 
void compress_block (deflate_state *s, const ct_data *ltree, const ct_data *dtree)
 
int detect_data_type (deflate_state *s)
 
unsigned bi_reverse (unsigned code, int len)
 
void bi_flush (deflate_state *s)
 
void bi_windup (deflate_state *s)
 

Variables

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}
 
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}
 
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}
 
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}
 
ct_data static_ltree [L_CODES+2]
 
ct_data static_dtree [D_CODES]
 
uch _dist_code [DIST_CODE_LEN]
 
uch _length_code [MAX_MATCH-MIN_MATCH+1]
 
int base_length [LENGTH_CODES]
 
int base_dist [D_CODES]
 
const static_tree_desc static_l_desc
 
const static_tree_desc static_d_desc
 
const static_tree_desc static_bl_desc
 

Macro Definition Documentation

◆ MAX_BL_BITS

#define MAX_BL_BITS   7

◆ END_BLOCK

#define END_BLOCK   256

◆ REP_3_6

#define REP_3_6   16

◆ REPZ_3_10

#define REPZ_3_10   17

◆ REPZ_11_138

#define REPZ_11_138   18

◆ DIST_CODE_LEN

#define DIST_CODE_LEN   512 /* see definition of array dist_code below */

◆ send_code

#define send_code (   s,
  c,
  tree 
)    send_bits(s, tree[c].Code, tree[c].Len)

◆ put_short

#define put_short (   s,
 
)
Value:
{ \
put_byte(s, (uch)((w) & 0xff)); \
put_byte(s, (uch)((ush)(w) >> 8)); \
}

◆ send_bits

#define send_bits (   s,
  value,
  length 
)
Value:
{ 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;\
}\
}

◆ SMALLEST

#define SMALLEST   1

◆ pqremove

#define pqremove (   s,
  tree,
  top 
)
Value:
{\
top = s->heap[SMALLEST]; \
s->heap[SMALLEST] = s->heap[s->heap_len--]; \
pqdownheap(s, tree, SMALLEST); \
}

◆ smaller

#define smaller (   tree,
  n,
  m,
  depth 
)
Value:
(tree[n].Freq < tree[m].Freq || \
(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

Function Documentation

◆ OF() [1/9]

void tr_static_init OF ( (void )

◆ OF() [2/9]

void init_block OF ( (deflate_state *s)  )

◆ OF() [3/9]

void pqdownheap OF ( (deflate_state *s, ct_data *tree, int k)  )

◆ OF() [4/9]

void gen_bitlen OF ( (deflate_state *s, tree_desc *desc)  )

◆ OF() [5/9]

void gen_codes OF ( (ct_data *tree, int max_code, ushf *bl_count)  )

◆ OF() [6/9]

void scan_tree OF ( (deflate_state *s, ct_data *tree, int max_code)  )

◆ OF() [7/9]

void send_all_trees OF ( (deflate_state *s, int lcodes, int dcodes, int blcodes)  )

◆ OF() [8/9]

void compress_block OF ( (deflate_state *s, const ct_data *ltree, const ct_data *dtree)  )

◆ OF() [9/9]

unsigned bi_reverse OF ( (unsigned value, int length )

◆ tr_static_init()

void tr_static_init ( )
233 {
234 #if defined(GEN_TREES_H) || !defined(STDC)
235  static int static_init_done = 0;
236  int n; /* iterates over tree elements */
237  int bits; /* bit counter */
238  int length; /* length value */
239  int code; /* code value */
240  int dist; /* distance index */
241  ush bl_count[MAX_BITS+1];
242  /* number of codes at each bit length for an optimal tree */
243 
244  if (static_init_done) return;
245 
246  /* For some embedded targets, global variables are not initialized: */
247 #ifdef NO_INIT_GLOBAL_POINTERS
253 #endif
254 
255  /* Initialize the mapping length (0..255) -> length code (0..28) */
256  length = 0;
257  for (code = 0; code < LENGTH_CODES-1; code++) {
259  for (n = 0; n < (1<<extra_lbits[code]); n++) {
260  _length_code[length++] = (uch)code;
261  }
262  }
263  Assert (length == 256, "tr_static_init: length != 256");
264  /* Note that the length 255 (match length 258) can be represented
265  * in two different ways: code 284 + 5 bits or code 285, so we
266  * overwrite length_code[255] to use the best encoding:
267  */
268  _length_code[length-1] = (uch)code;
269 
270  /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
271  dist = 0;
272  for (code = 0 ; code < 16; code++) {
273  base_dist[code] = dist;
274  for (n = 0; n < (1<<extra_dbits[code]); n++) {
275  _dist_code[dist++] = (uch)code;
276  }
277  }
278  Assert (dist == 256, "tr_static_init: dist != 256");
279  dist >>= 7; /* from now on, all distances are divided by 128 */
280  for ( ; code < D_CODES; code++) {
281  base_dist[code] = dist << 7;
282  for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
283  _dist_code[256 + dist++] = (uch)code;
284  }
285  }
286  Assert (dist == 256, "tr_static_init: 256+dist != 512");
287 
288  /* Construct the codes of the static literal tree */
289  for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
290  n = 0;
291  while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
292  while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
293  while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
294  while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
295  /* Codes 286 and 287 do not exist, but we must include them in the
296  * tree construction to get a canonical Huffman tree (longest code
297  * all ones)
298  */
299  gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
300 
301  /* The static distance tree is trivial: */
302  for (n = 0; n < D_CODES; n++) {
303  static_dtree[n].Len = 5;
304  static_dtree[n].Code = bi_reverse((unsigned)n, 5);
305  }
306  static_init_done = 1;
307 
308 # ifdef GEN_TREES_H
309  gen_trees_header();
310 # endif
311 #endif /* defined(GEN_TREES_H) || !defined(STDC) */
312 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ _tr_init()

void ZLIB_INTERNAL _tr_init ( deflate_state s)
381 {
382  tr_static_init();
383 
384  s->l_desc.dyn_tree = s->dyn_ltree;
386 
387  s->d_desc.dyn_tree = s->dyn_dtree;
389 
390  s->bl_desc.dyn_tree = s->bl_tree;
392 
393  s->bi_buf = 0;
394  s->bi_valid = 0;
395 #ifdef ZLIB_DEBUG
396  s->compressed_len = 0L;
397  s->bits_sent = 0L;
398 #endif
399 
400  /* Initialize the first block of the first file: */
401  init_block(s);
402 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ init_block()

void init_block ( deflate_state s)
409 {
410  int n; /* iterates over tree elements */
411 
412  /* Initialize the trees. */
413  for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
414  for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
415  for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
416 
417  s->dyn_ltree[END_BLOCK].Freq = 1;
418  s->opt_len = s->static_len = 0L;
419  s->last_lit = s->matches = 0;
420 }
Here is the caller graph for this function:

◆ pqdownheap()

void pqdownheap ( deflate_state s,
ct_data tree,
int  k 
)
455 {
456  int v = s->heap[k];
457  int j = k << 1; /* left son of k */
458  while (j <= s->heap_len) {
459  /* Set j to the smallest of the two sons: */
460  if (j < s->heap_len &&
461  smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
462  j++;
463  }
464  /* Exit if v is smaller than both sons */
465  if (smaller(tree, v, s->heap[j], s->depth)) break;
466 
467  /* Exchange v with the smallest son */
468  s->heap[k] = s->heap[j]; k = j;
469 
470  /* And continue down the tree, setting j to the left son of k */
471  j <<= 1;
472  }
473  s->heap[k] = v;
474 }
Here is the caller graph for this function:

◆ gen_bitlen()

void gen_bitlen ( deflate_state s,
tree_desc desc 
)
489 {
490  ct_data *tree = desc->dyn_tree;
491  int max_code = desc->max_code;
492  const ct_data *stree = desc->stat_desc->static_tree;
493  const intf *extra = desc->stat_desc->extra_bits;
494  int base = desc->stat_desc->extra_base;
495  int max_length = desc->stat_desc->max_length;
496  int h; /* heap index */
497  int n, m; /* iterate over the tree elements */
498  int bits; /* bit length */
499  int xbits; /* extra bits */
500  ush f; /* frequency */
501  int overflow = 0; /* number of elements with bit length too large */
502 
503  for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
504 
505  /* In a first pass, compute the optimal bit lengths (which may
506  * overflow in the case of the bit length tree).
507  */
508  tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
509 
510  for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
511  n = s->heap[h];
512  bits = tree[tree[n].Dad].Len + 1;
513  if (bits > max_length) bits = max_length, overflow++;
514  tree[n].Len = (ush)bits;
515  /* We overwrite tree[n].Dad which is no longer needed */
516 
517  if (n > max_code) continue; /* not a leaf node */
518 
519  s->bl_count[bits]++;
520  xbits = 0;
521  if (n >= base) xbits = extra[n-base];
522  f = tree[n].Freq;
523  s->opt_len += (ulg)f * (unsigned)(bits + xbits);
524  if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits);
525  }
526  if (overflow == 0) return;
527 
528  Tracev((stderr,"\nbit length overflow\n"));
529  /* This happens for example on obj2 and pic of the Calgary corpus */
530 
531  /* Find the first bit length which could increase: */
532  do {
533  bits = max_length-1;
534  while (s->bl_count[bits] == 0) bits--;
535  s->bl_count[bits]--; /* move one leaf down the tree */
536  s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
537  s->bl_count[max_length]--;
538  /* The brother of the overflow item also moves one step up,
539  * but this does not affect bl_count[max_length]
540  */
541  overflow -= 2;
542  } while (overflow > 0);
543 
544  /* Now recompute all bit lengths, scanning in increasing frequency.
545  * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
546  * lengths instead of fixing only the wrong ones. This idea is taken
547  * from 'ar' written by Haruhiko Okumura.)
548  */
549  for (bits = max_length; bits != 0; bits--) {
550  n = s->bl_count[bits];
551  while (n != 0) {
552  m = s->heap[--h];
553  if (m > max_code) continue;
554  if ((unsigned) tree[m].Len != (unsigned) bits) {
555  Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
556  s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq;
557  tree[m].Len = (ush)bits;
558  }
559  n--;
560  }
561  }
562 }
Here is the caller graph for this function:

◆ gen_codes()

void gen_codes ( ct_data tree,
int  max_code,
ushf bl_count 
)
576 {
577  ush next_code[MAX_BITS+1]; /* next code value for each bit length */
578  unsigned code = 0; /* running code value */
579  int bits; /* bit index */
580  int n; /* code index */
581 
582  /* The distribution counts are first used to generate the code values
583  * without bit reversal.
584  */
585  for (bits = 1; bits <= MAX_BITS; bits++) {
586  code = (code + bl_count[bits-1]) << 1;
587  next_code[bits] = (ush)code;
588  }
589  /* Check that the bit counts in bl_count are consistent. The last code
590  * must be all ones.
591  */
592  Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
593  "inconsistent bit counts");
594  Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
595 
596  for (n = 0; n <= max_code; n++) {
597  int len = tree[n].Len;
598  if (len == 0) continue;
599  /* Now reverse the bits */
600  tree[n].Code = (ush)bi_reverse(next_code[len]++, len);
601 
602  Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
603  n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
604  }
605 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ build_tree()

void build_tree ( deflate_state s,
tree_desc desc 
)
618 {
619  ct_data *tree = desc->dyn_tree;
620  const ct_data *stree = desc->stat_desc->static_tree;
621  int elems = desc->stat_desc->elems;
622  int n, m; /* iterate over heap elements */
623  int max_code = -1; /* largest code with non zero frequency */
624  int node; /* new node being created */
625 
626  /* Construct the initial heap, with least frequent element in
627  * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
628  * heap[0] is not used.
629  */
630  s->heap_len = 0, s->heap_max = HEAP_SIZE;
631 
632  for (n = 0; n < elems; n++) {
633  if (tree[n].Freq != 0) {
634  s->heap[++(s->heap_len)] = max_code = n;
635  s->depth[n] = 0;
636  } else {
637  tree[n].Len = 0;
638  }
639  }
640 
641  /* The pkzip format requires that at least one distance code exists,
642  * and that at least one bit should be sent even if there is only one
643  * possible code. So to avoid special checks later on we force at least
644  * two codes of non zero frequency.
645  */
646  while (s->heap_len < 2) {
647  node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
648  tree[node].Freq = 1;
649  s->depth[node] = 0;
650  s->opt_len--; if (stree) s->static_len -= stree[node].Len;
651  /* node is 0 or 1 so it does not have extra bits */
652  }
653  desc->max_code = max_code;
654 
655  /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
656  * establish sub-heaps of increasing lengths:
657  */
658  for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
659 
660  /* Construct the Huffman tree by repeatedly combining the least two
661  * frequent nodes.
662  */
663  node = elems; /* next internal node of the tree */
664  do {
665  pqremove(s, tree, n); /* n = node of least frequency */
666  m = s->heap[SMALLEST]; /* m = node of next least frequency */
667 
668  s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
669  s->heap[--(s->heap_max)] = m;
670 
671  /* Create a new node father of n and m */
672  tree[node].Freq = tree[n].Freq + tree[m].Freq;
673  s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
674  s->depth[n] : s->depth[m]) + 1);
675  tree[n].Dad = tree[m].Dad = (ush)node;
676 #ifdef DUMP_BL_TREE
677  if (tree == s->bl_tree) {
678  fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
679  node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
680  }
681 #endif
682  /* and insert the new node in the heap */
683  s->heap[SMALLEST] = node++;
684  pqdownheap(s, tree, SMALLEST);
685 
686  } while (s->heap_len >= 2);
687 
688  s->heap[--(s->heap_max)] = s->heap[SMALLEST];
689 
690  /* At this point, the fields freq and dad are set. We can now
691  * generate the bit lengths.
692  */
693  gen_bitlen(s, (tree_desc *)desc);
694 
695  /* The field len is now set, we can generate the bit codes */
696  gen_codes ((ct_data *)tree, max_code, s->bl_count);
697 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ scan_tree()

void scan_tree ( deflate_state s,
ct_data tree,
int  max_code 
)
707 {
708  int n; /* iterates over all tree elements */
709  int prevlen = -1; /* last emitted length */
710  int curlen; /* length of current code */
711  int nextlen = tree[0].Len; /* length of next code */
712  int count = 0; /* repeat count of the current code */
713  int max_count = 7; /* max repeat count */
714  int min_count = 4; /* min repeat count */
715 
716  if (nextlen == 0) max_count = 138, min_count = 3;
717  tree[max_code+1].Len = (ush)0xffff; /* guard */
718 
719  for (n = 0; n <= max_code; n++) {
720  curlen = nextlen; nextlen = tree[n+1].Len;
721  if (++count < max_count && curlen == nextlen) {
722  continue;
723  } else if (count < min_count) {
724  s->bl_tree[curlen].Freq += count;
725  } else if (curlen != 0) {
726  if (curlen != prevlen) s->bl_tree[curlen].Freq++;
727  s->bl_tree[REP_3_6].Freq++;
728  } else if (count <= 10) {
729  s->bl_tree[REPZ_3_10].Freq++;
730  } else {
731  s->bl_tree[REPZ_11_138].Freq++;
732  }
733  count = 0; prevlen = curlen;
734  if (nextlen == 0) {
735  max_count = 138, min_count = 3;
736  } else if (curlen == nextlen) {
737  max_count = 6, min_count = 3;
738  } else {
739  max_count = 7, min_count = 4;
740  }
741  }
742 }
Here is the caller graph for this function:

◆ send_tree()

void send_tree ( deflate_state s,
ct_data tree,
int  max_code 
)
752 {
753  int n; /* iterates over all tree elements */
754  int prevlen = -1; /* last emitted length */
755  int curlen; /* length of current code */
756  int nextlen = tree[0].Len; /* length of next code */
757  int count = 0; /* repeat count of the current code */
758  int max_count = 7; /* max repeat count */
759  int min_count = 4; /* min repeat count */
760 
761  /* tree[max_code+1].Len = -1; */ /* guard already set */
762  if (nextlen == 0) max_count = 138, min_count = 3;
763 
764  for (n = 0; n <= max_code; n++) {
765  curlen = nextlen; nextlen = tree[n+1].Len;
766  if (++count < max_count && curlen == nextlen) {
767  continue;
768  } else if (count < min_count) {
769  do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
770 
771  } else if (curlen != 0) {
772  if (curlen != prevlen) {
773  send_code(s, curlen, s->bl_tree); count--;
774  }
775  Assert(count >= 3 && count <= 6, " 3_6?");
776  send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
777 
778  } else if (count <= 10) {
779  send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
780 
781  } else {
782  send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
783  }
784  count = 0; prevlen = curlen;
785  if (nextlen == 0) {
786  max_count = 138, min_count = 3;
787  } else if (curlen == nextlen) {
788  max_count = 6, min_count = 3;
789  } else {
790  max_count = 7, min_count = 4;
791  }
792  }
793 }
Here is the caller graph for this function:

◆ build_bl_tree()

int build_bl_tree ( deflate_state s)
801 {
802  int max_blindex; /* index of last bit length code of non zero freq */
803 
804  /* Determine the bit length frequencies for literal and distance trees */
805  scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
806  scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
807 
808  /* Build the bit length tree: */
809  build_tree(s, (tree_desc *)(&(s->bl_desc)));
810  /* opt_len now includes the length of the tree representations, except
811  * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
812  */
813 
814  /* Determine the number of bit length codes to send. The pkzip format
815  * requires that at least 4 bit length codes be sent. (appnote.txt says
816  * 3 but the actual value used is 4.)
817  */
818  for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
819  if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
820  }
821  /* Update opt_len to include the bit length tree and counts */
822  s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4;
823  Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
824  s->opt_len, s->static_len));
825 
826  return max_blindex;
827 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ send_all_trees()

void send_all_trees ( deflate_state s,
int  lcodes,
int  dcodes,
int  blcodes 
)
837 {
838  int rank; /* index in bl_order */
839 
840  Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
841  Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
842  "too many codes");
843  Tracev((stderr, "\nbl counts: "));
844  send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
845  send_bits(s, dcodes-1, 5);
846  send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
847  for (rank = 0; rank < blcodes; rank++) {
848  Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
849  send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
850  }
851  Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
852 
853  send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
854  Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
855 
856  send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
857  Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
858 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ _tr_stored_block()

void ZLIB_INTERNAL _tr_stored_block ( deflate_state s,
charf buf,
ulg  stored_len,
int  last 
)
868 {
869  send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */
870  bi_windup(s); /* align on byte boundary */
871  put_short(s, (ush)stored_len);
872  put_short(s, (ush)~stored_len);
873  zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
874  s->pending += stored_len;
875 #ifdef ZLIB_DEBUG
876  s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
877  s->compressed_len += (stored_len + 4) << 3;
878  s->bits_sent += 2*16;
879  s->bits_sent += stored_len<<3;
880 #endif
881 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ _tr_flush_bits()

void ZLIB_INTERNAL _tr_flush_bits ( deflate_state s)
888 {
889  bi_flush(s);
890 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ _tr_align()

void ZLIB_INTERNAL _tr_align ( deflate_state s)
898 {
899  send_bits(s, STATIC_TREES<<1, 3);
901 #ifdef ZLIB_DEBUG
902  s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
903 #endif
904  bi_flush(s);
905 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ _tr_flush_block()

void ZLIB_INTERNAL _tr_flush_block ( deflate_state s,
charf buf,
ulg  stored_len,
int  last 
)
916 {
917  ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
918  int max_blindex = 0; /* index of last bit length code of non zero freq */
919 
920  /* Build the Huffman trees unless a stored block is forced */
921  if (s->level > 0) {
922 
923  /* Check if the file is binary or text */
924  if (s->strm->data_type == Z_UNKNOWN)
925  s->strm->data_type = detect_data_type(s);
926 
927  /* Construct the literal and distance trees */
928  build_tree(s, (tree_desc *)(&(s->l_desc)));
929  Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
930  s->static_len));
931 
932  build_tree(s, (tree_desc *)(&(s->d_desc)));
933  Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
934  s->static_len));
935  /* At this point, opt_len and static_len are the total bit lengths of
936  * the compressed block data, excluding the tree representations.
937  */
938 
939  /* Build the bit length tree for the above two trees, and get the index
940  * in bl_order of the last bit length code to send.
941  */
942  max_blindex = build_bl_tree(s);
943 
944  /* Determine the best encoding. Compute the block lengths in bytes. */
945  opt_lenb = (s->opt_len+3+7)>>3;
946  static_lenb = (s->static_len+3+7)>>3;
947 
948  Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
949  opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
950  s->last_lit));
951 
952  if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
953 
954  } else {
955  Assert(buf != (char*)0, "lost buf");
956  opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
957  }
958 
959 #ifdef FORCE_STORED
960  if (buf != (char*)0) { /* force stored block */
961 #else
962  if (stored_len+4 <= opt_lenb && buf != (char*)0) {
963  /* 4: two words for the lengths */
964 #endif
965  /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
966  * Otherwise we can't have processed more than WSIZE input bytes since
967  * the last block flush, because compression would have been
968  * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
969  * transform a block into a stored block.
970  */
971  _tr_stored_block(s, buf, stored_len, last);
972 
973 #ifdef FORCE_STATIC
974  } else if (static_lenb >= 0) { /* force static trees */
975 #else
976  } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
977 #endif
978  send_bits(s, (STATIC_TREES<<1)+last, 3);
979  compress_block(s, (const ct_data *)static_ltree,
980  (const ct_data *)static_dtree);
981 #ifdef ZLIB_DEBUG
982  s->compressed_len += 3 + s->static_len;
983 #endif
984  } else {
985  send_bits(s, (DYN_TREES<<1)+last, 3);
987  max_blindex+1);
988  compress_block(s, (const ct_data *)s->dyn_ltree,
989  (const ct_data *)s->dyn_dtree);
990 #ifdef ZLIB_DEBUG
991  s->compressed_len += 3 + s->opt_len;
992 #endif
993  }
994  Assert (s->compressed_len == s->bits_sent, "bad compressed size");
995  /* The above check is made mod 2^32, for files larger than 512 MB
996  * and uLong implemented on 32 bits.
997  */
998  init_block(s);
999 
1000  if (last) {
1001  bi_windup(s);
1002 #ifdef ZLIB_DEBUG
1003  s->compressed_len += 7; /* align on byte boundary */
1004 #endif
1005  }
1006  Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1007  s->compressed_len-7*last));
1008 }
Here is the call graph for this function:

◆ _tr_tally()

int ZLIB_INTERNAL _tr_tally ( deflate_state s,
unsigned  dist,
unsigned  lc 
)
1018 {
1019  s->d_buf[s->last_lit] = (ush)dist;
1020  s->l_buf[s->last_lit++] = (uch)lc;
1021  if (dist == 0) {
1022  /* lc is the unmatched char */
1023  s->dyn_ltree[lc].Freq++;
1024  } else {
1025  s->matches++;
1026  /* Here, lc is the match length - MIN_MATCH */
1027  dist--; /* dist = match distance - 1 */
1028  Assert((ush)dist < (ush)MAX_DIST(s) &&
1029  (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1030  (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1031 
1032  s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
1033  s->dyn_dtree[d_code(dist)].Freq++;
1034  }
1035 
1036 #ifdef TRUNCATE_BLOCK
1037  /* Try to guess if it is profitable to stop the current block here */
1038  if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1039  /* Compute an upper bound for the compressed length */
1040  ulg out_length = (ulg)s->last_lit*8L;
1041  ulg in_length = (ulg)((long)s->strstart - s->block_start);
1042  int dcode;
1043  for (dcode = 0; dcode < D_CODES; dcode++) {
1044  out_length += (ulg)s->dyn_dtree[dcode].Freq *
1045  (5L+extra_dbits[dcode]);
1046  }
1047  out_length >>= 3;
1048  Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1049  s->last_lit, in_length, out_length,
1050  100L - out_length*100L/in_length));
1051  if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1052  }
1053 #endif
1054  return (s->last_lit == s->lit_bufsize-1);
1055  /* We avoid equality with lit_bufsize because of wraparound at 64K
1056  * on 16 bit machines and because stored blocks are restricted to
1057  * 64K-1 bytes.
1058  */
1059 }

◆ compress_block()

void compress_block ( deflate_state s,
const ct_data ltree,
const ct_data dtree 
)
1068 {
1069  unsigned dist; /* distance of matched string */
1070  int lc; /* match length or unmatched char (if dist == 0) */
1071  unsigned lx = 0; /* running index in l_buf */
1072  unsigned code; /* the code to send */
1073  int extra; /* number of extra bits to send */
1074 
1075  if (s->last_lit != 0) do {
1076  dist = s->d_buf[lx];
1077  lc = s->l_buf[lx++];
1078  if (dist == 0) {
1079  send_code(s, lc, ltree); /* send a literal byte */
1080  Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1081  } else {
1082  /* Here, lc is the match length - MIN_MATCH */
1083  code = _length_code[lc];
1084  send_code(s, code+LITERALS+1, ltree); /* send the length code */
1085  extra = extra_lbits[code];
1086  if (extra != 0) {
1087  lc -= base_length[code];
1088  send_bits(s, lc, extra); /* send the extra length bits */
1089  }
1090  dist--; /* dist is now the match distance - 1 */
1091  code = d_code(dist);
1092  Assert (code < D_CODES, "bad d_code");
1093 
1094  send_code(s, code, dtree); /* send the distance code */
1095  extra = extra_dbits[code];
1096  if (extra != 0) {
1097  dist -= (unsigned)base_dist[code];
1098  send_bits(s, dist, extra); /* send the extra distance bits */
1099  }
1100  } /* literal or match pair ? */
1101 
1102  /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
1103  Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1104  "pendingBuf overflow");
1105 
1106  } while (lx < s->last_lit);
1107 
1108  send_code(s, END_BLOCK, ltree);
1109 }
Here is the caller graph for this function:

◆ detect_data_type()

int detect_data_type ( deflate_state s)
1126 {
1127  /* black_mask is the bit mask of black-listed bytes
1128  * set bits 0..6, 14..25, and 28..31
1129  * 0xf3ffc07f = binary 11110011111111111100000001111111
1130  */
1131  unsigned long black_mask = 0xf3ffc07fUL;
1132  int n;
1133 
1134  /* Check for non-textual ("black-listed") bytes. */
1135  for (n = 0; n <= 31; n++, black_mask >>= 1)
1136  if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1137  return Z_BINARY;
1138 
1139  /* Check for textual ("white-listed") bytes. */
1140  if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
1141  || s->dyn_ltree[13].Freq != 0)
1142  return Z_TEXT;
1143  for (n = 32; n < LITERALS; n++)
1144  if (s->dyn_ltree[n].Freq != 0)
1145  return Z_TEXT;
1146 
1147  /* There are no "black-listed" or "white-listed" bytes:
1148  * this stream either is empty or has tolerated ("gray-listed") bytes only.
1149  */
1150  return Z_BINARY;
1151 }
Here is the caller graph for this function:

◆ bi_reverse()

unsigned bi_reverse ( unsigned  code,
int  len 
)
1161 {
1162  register unsigned res = 0;
1163  do {
1164  res |= code & 1;
1165  code >>= 1, res <<= 1;
1166  } while (--len > 0);
1167  return res >> 1;
1168 }
Here is the caller graph for this function:

◆ bi_flush()

void bi_flush ( deflate_state s)
1175 {
1176  if (s->bi_valid == 16) {
1177  put_short(s, s->bi_buf);
1178  s->bi_buf = 0;
1179  s->bi_valid = 0;
1180  } else if (s->bi_valid >= 8) {
1181  put_byte(s, (Byte)s->bi_buf);
1182  s->bi_buf >>= 8;
1183  s->bi_valid -= 8;
1184  }
1185 }
Here is the caller graph for this function:

◆ bi_windup()

void bi_windup ( deflate_state s)
1192 {
1193  if (s->bi_valid > 8) {
1194  put_short(s, s->bi_buf);
1195  } else if (s->bi_valid > 0) {
1196  put_byte(s, (Byte)s->bi_buf);
1197  }
1198  s->bi_buf = 0;
1199  s->bi_valid = 0;
1200 #ifdef ZLIB_DEBUG
1201  s->bits_sent = (s->bits_sent+7) & ~7;
1202 #endif
1203 }
Here is the caller graph for this function:

Variable Documentation

◆ extra_lbits

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}

◆ extra_dbits

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}

◆ extra_blbits

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}

◆ bl_order

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}

◆ static_ltree

ct_data static_ltree[L_CODES+2]

◆ static_dtree

ct_data static_dtree[D_CODES]

◆ _dist_code

uch _dist_code[DIST_CODE_LEN]

◆ _length_code

uch _length_code[MAX_MATCH-MIN_MATCH+1]

◆ base_length

int base_length[LENGTH_CODES]

◆ base_dist

int base_dist[D_CODES]

◆ static_l_desc

const static_tree_desc static_l_desc

◆ static_d_desc

const static_tree_desc static_d_desc
Initial value:

◆ static_bl_desc

const static_tree_desc static_bl_desc
Initial value:
Bytef
Byte FAR Bytef
Definition: zconf.h:400
MAX_BITS
#define MAX_BITS
Definition: deflate.h:48
tree_desc_s::stat_desc
const static_tree_desc * stat_desc
Definition: deflate.h:89
build_tree
void build_tree(deflate_state *s, tree_desc *desc)
Definition: trees.c:615
SMALLEST
#define SMALLEST
Definition: trees.c:422
internal_state::heap_max
int heap_max
Definition: deflate.h:211
Assert
#define Assert(cond, msg)
Definition: zutil.h:248
send_bits
#define send_bits(s, value, length)
Definition: trees.c:211
internal_state::bl_tree
struct ct_data_s bl_tree[2 *BL_CODES+1]
Definition: deflate.h:200
compress_block
void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree)
Definition: trees.c:1064
uch
unsigned char uch
Definition: zutil.h:43
internal_state::opt_len
ulg opt_len
Definition: deflate.h:250
Tracecv
#define Tracecv(c, x)
Definition: zutil.h:253
internal_state::static_len
ulg static_len
Definition: deflate.h:251
bi_reverse
unsigned bi_reverse(unsigned code, int len)
Definition: trees.c:1158
pqdownheap
void pqdownheap(deflate_state *s, ct_data *tree, int k)
Definition: trees.c:451
smaller
#define smaller(tree, n, m, depth)
Definition: trees.c:441
Z_UNKNOWN
#define Z_UNKNOWN
Definition: zlib.h:206
bl_order
const uch bl_order[BL_CODES]
Definition: trees.c:72
pqremove
#define pqremove(s, tree, top)
Definition: trees.c:430
internal_state::heap
int heap[2 *L_CODES+1]
Definition: deflate.h:209
build_bl_tree
int build_bl_tree(deflate_state *s)
Definition: trees.c:799
STORED_BLOCK
#define STORED_BLOCK
Definition: zutil.h:72
static_bl_desc
const static_tree_desc static_bl_desc
Definition: trees.c:131
Z_BINARY
#define Z_BINARY
Definition: zlib.h:203
BL_CODES
#define BL_CODES
Definition: deflate.h:42
internal_state::pending_buf
Bytef * pending_buf
Definition: deflate.h:103
scan_tree
void scan_tree(deflate_state *s, ct_data *tree, int max_code)
Definition: trees.c:703
Tracev
#define Tracev(x)
Definition: zutil.h:250
internal_state::l_buf
uchf * l_buf
Definition: deflate.h:220
static_d_desc
const static_tree_desc static_d_desc
Definition: trees.c:128
gen_codes
void gen_codes(ct_data *tree, int max_code, ushf *bl_count)
Definition: trees.c:572
internal_state::strm
z_streamp strm
Definition: deflate.h:101
STATIC_TREES
#define STATIC_TREES
Definition: zutil.h:73
_length_code
uch _length_code[MAX_MATCH-MIN_MATCH+1]
Definition: trees.c:104
detect_data_type
int detect_data_type(deflate_state *s)
Definition: trees.c:1124
tree_desc_s
Definition: deflate.h:86
REP_3_6
#define REP_3_6
Definition: trees.c:53
REPZ_3_10
#define REPZ_3_10
Definition: trees.c:56
static_ltree
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
internal_state::lit_bufsize
uInt lit_bufsize
Definition: deflate.h:222
base_length
int base_length[LENGTH_CODES]
Definition: trees.c:107
_tr_stored_block
void ZLIB_INTERNAL _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int last)
Definition: trees.c:863
MAX_MATCH
#define MAX_MATCH
Definition: zutil.h:78
LENGTH_CODES
#define LENGTH_CODES
Definition: deflate.h:30
tr_static_init
void tr_static_init()
Definition: trees.c:232
static_tree_desc_s::elems
int elems
Definition: trees.c:121
_dist_code
uch _dist_code[DIST_CODE_LEN]
Definition: trees.c:98
MAX_DIST
#define MAX_DIST(s)
Definition: deflate.h:289
internal_state::last_lit
uInt last_lit
Definition: deflate.h:242
MAX_BL_BITS
#define MAX_BL_BITS
Definition: trees.c:47
Byte
unsigned char Byte
Definition: zconf.h:391
LITERALS
#define LITERALS
Definition: deflate.h:33
static_tree_desc_s::extra_bits
const intf * extra_bits
Definition: trees.c:119
ush
unsigned short ush
Definition: zutil.h:45
DYN_TREES
#define DYN_TREES
Definition: zutil.h:74
inflate_state::bits
unsigned bits
Definition: inflate.h:102
internal_state::level
int level
Definition: deflate.h:188
static_l_desc
const static_tree_desc static_l_desc
Definition: trees.c:125
internal_state::dyn_ltree
struct ct_data_s dyn_ltree[HEAP_SIZE]
Definition: deflate.h:198
internal_state::d_desc
struct tree_desc_s d_desc
Definition: deflate.h:203
static_tree_desc_s::static_tree
const ct_data * static_tree
Definition: trees.c:118
HEAP_SIZE
#define HEAP_SIZE
Definition: deflate.h:45
extra_blbits
const int extra_blbits[BL_CODES]
Definition: trees.c:69
put_byte
#define put_byte(s, c)
Definition: deflate.h:281
internal_state::strstart
uInt strstart
Definition: deflate.h:162
Code
#define Code
Definition: deflate.h:80
internal_state::d_buf
ushf * d_buf
Definition: deflate.h:244
inflate_state::extra
unsigned extra
Definition: inflate.h:107
bi_windup
void bi_windup(deflate_state *s)
Definition: trees.c:1190
bi_flush
void bi_flush(deflate_state *s)
Definition: trees.c:1173
tree_desc_s::max_code
int max_code
Definition: deflate.h:88
Buf_size
#define Buf_size
Definition: deflate.h:51
d_code
#define d_code(dist)
Definition: deflate.h:308
internal_state::bi_buf
ush bi_buf
Definition: deflate.h:260
REPZ_11_138
#define REPZ_11_138
Definition: trees.c:59
L
#define L(CODE)
Definition: macros.h:76
Z_FIXED
#define Z_FIXED
Definition: zlib.h:199
inflate_state::last
int last
Definition: inflate.h:85
gen_bitlen
void gen_bitlen(deflate_state *s, tree_desc *desc)
Definition: trees.c:486
internal_state::bl_count
ush bl_count[MAX_BITS+1]
Definition: deflate.h:206
Freq
#define Freq
Definition: deflate.h:79
internal_state::bi_valid
int bi_valid
Definition: deflate.h:264
send_code
#define send_code(s, c, tree)
Definition: trees.c:161
init_block
void init_block(deflate_state *s)
Definition: trees.c:407
zmemcpy
void ZLIB_INTERNAL zmemcpy(Bytef *dest, const Bytef *source, uInt len)
Definition: zutil.c:149
base_dist
int base_dist[D_CODES]
Definition: trees.c:110
internal_state::dyn_dtree
struct ct_data_s dyn_dtree[2 *D_CODES+1]
Definition: deflate.h:199
internal_state::bl_desc
struct tree_desc_s bl_desc
Definition: deflate.h:204
Len
#define Len
Definition: deflate.h:82
static_tree_desc_s::extra_base
int extra_base
Definition: trees.c:120
MIN_MATCH
#define MIN_MATCH
Definition: zutil.h:77
ct_data_s
Definition: deflate.h:68
internal_state::heap_len
int heap_len
Definition: deflate.h:210
extra_dbits
const int extra_dbits[D_CODES]
Definition: trees.c:66
createSpeedLookupTable.int
int
Definition: createSpeedLookupTable.py:15
internal_state::l_desc
struct tree_desc_s l_desc
Definition: deflate.h:202
L_CODES
#define L_CODES
Definition: deflate.h:36
internal_state::pending
ulg pending
Definition: deflate.h:106
static_tree_desc_s::max_length
int max_length
Definition: trees.c:122
uInt
unsigned int uInt
Definition: zconf.h:393
D_CODES
#define D_CODES
Definition: deflate.h:39
length
png_uint_32 length
Definition: png.c:2247
tree_desc_s::dyn_tree
ct_data * dyn_tree
Definition: deflate.h:87
code
Definition: inftrees.h:24
internal_state::matches
uInt matches
Definition: deflate.h:252
static_dtree
ct_data static_dtree[D_CODES]
Definition: trees.c:93
send_all_trees
void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
Definition: trees.c:834
put_short
#define put_short(s, w)
Definition: trees.c:174
END_BLOCK
#define END_BLOCK
Definition: trees.c:50
ulg
unsigned long ulg
Definition: zutil.h:47
internal_state::block_start
long block_start
Definition: deflate.h:154
internal_state::strategy
int strategy
Definition: deflate.h:189
send_tree
void send_tree(deflate_state *s, ct_data *tree, int max_code)
Definition: trees.c:748
Z_TEXT
#define Z_TEXT
Definition: zlib.h:204
extra_lbits
const int extra_lbits[LENGTH_CODES]
Definition: trees.c:63
intf
int FAR intf
Definition: zconf.h:403
internal_state::depth
uch depth[2 *L_CODES+1]
Definition: deflate.h:216