ReactOS  0.4.14-dev-368-gfa26425
trees.c File Reference
#include "deflate.h"
Include dependency graph for trees.c:

Go to the source code of this file.

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

◆ DIST_CODE_LEN

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

Definition at line 81 of file trees.c.

◆ END_BLOCK

#define END_BLOCK   256

Definition at line 50 of file trees.c.

◆ MAX_BL_BITS

#define MAX_BL_BITS   7

Definition at line 47 of file trees.c.

◆ pqremove

#define pqremove (   s,
  tree,
  top 
)
Value:
{\
top = s->heap[SMALLEST]; \
s->heap[SMALLEST] = s->heap[s->heap_len--]; \
pqdownheap(s, tree, SMALLEST); \
}
#define SMALLEST
Definition: trees.c:422
GLdouble s
Definition: gl.h:2039

Definition at line 430 of file trees.c.

◆ put_short

#define put_short (   s,
  w 
)
Value:
{ \
put_byte(s, (uch)((w) & 0xff)); \
put_byte(s, (uch)((ush)(w) >> 8)); \
}
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
unsigned short ush
Definition: zutil.h:36
GLdouble s
Definition: gl.h:2039
unsigned char uch
Definition: zutil.h:34

Definition at line 174 of file trees.c.

◆ REP_3_6

#define REP_3_6   16

Definition at line 53 of file trees.c.

◆ REPZ_11_138

#define REPZ_11_138   18

Definition at line 59 of file trees.c.

◆ REPZ_3_10

#define REPZ_3_10   17

Definition at line 56 of file trees.c.

◆ 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;\
}\
}
#define put_short(s, w)
Definition: trees.c:174
#define Buf_size
Definition: deflate.h:51
GLuint GLfloat * val
Definition: glext.h:7180
unsigned short ush
Definition: zutil.h:36
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
GLenum GLsizei len
Definition: glext.h:6722
GLdouble s
Definition: gl.h:2039
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Definition at line 211 of file trees.c.

◆ send_code

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

Definition at line 161 of file trees.c.

◆ smaller

#define smaller (   tree,
  n,
  m,
  depth 
)
Value:
(tree[n].Freq < tree[m].Freq || \
(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
GLdouble n
Definition: glext.h:7729
const GLfloat * m
Definition: glext.h:10848
GLint GLint GLsizei GLsizei GLsizei depth
Definition: gl.h:1546

Definition at line 441 of file trees.c.

◆ SMALLEST

#define SMALLEST   1

Definition at line 422 of file trees.c.

Function Documentation

◆ _tr_align()

void ZLIB_INTERNAL _tr_align ( deflate_state s)

Definition at line 896 of file trees.c.

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 }
void bi_flush(deflate_state *s)
Definition: trees.c:1173
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
#define END_BLOCK
Definition: trees.c:50
#define send_bits(s, value, length)
Definition: trees.c:211
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
#define STATIC_TREES
Definition: zutil.h:60
#define send_code(s, c, tree)
Definition: trees.c:161

Referenced by deflate().

◆ _tr_flush_bits()

void ZLIB_INTERNAL _tr_flush_bits ( deflate_state s)

Definition at line 886 of file trees.c.

888 {
889  bi_flush(s);
890 }
void bi_flush(deflate_state *s)
Definition: trees.c:1173
GLdouble s
Definition: gl.h:2039

Referenced by deflatePrime(), and flush_pending().

◆ _tr_flush_block()

void ZLIB_INTERNAL _tr_flush_block ( deflate_state s,
charf buf,
ulg  stored_len,
int  last 
)

Definition at line 911 of file trees.c.

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);
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);
986  send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
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 }
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
POINT last
Definition: font.c:46
void init_block(deflate_state *s)
Definition: trees.c:407
unsigned long ulg
Definition: zutil.h:38
#define Z_UNKNOWN
Definition: zlib.h:206
ct_data static_dtree[D_CODES]
Definition: trees.c:93
#define Assert(cond, msg)
Definition: zutil.h:196
#define DYN_TREES
Definition: zutil.h:61
#define send_bits(s, value, length)
Definition: trees.c:211
void bi_windup(deflate_state *s)
Definition: trees.c:1190
void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
Definition: trees.c:834
int detect_data_type(deflate_state *s)
Definition: trees.c:1124
GLdouble s
Definition: gl.h:2039
void ZLIB_INTERNAL _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int last)
Definition: trees.c:863
int build_bl_tree(deflate_state *s)
Definition: trees.c:799
#define STATIC_TREES
Definition: zutil.h:60
#define Tracev(x)
Definition: zutil.h:198
FILE * stderr
#define Z_FIXED
Definition: zlib.h:199
void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree)
Definition: trees.c:1064
void build_tree(deflate_state *s, tree_desc *desc)
Definition: trees.c:615

◆ _tr_init()

void ZLIB_INTERNAL _tr_init ( deflate_state s)

Definition at line 379 of file trees.c.

381 {
382  tr_static_init();
383 
384  s->l_desc.dyn_tree = s->dyn_ltree;
385  s->l_desc.stat_desc = &static_l_desc;
386 
387  s->d_desc.dyn_tree = s->dyn_dtree;
388  s->d_desc.stat_desc = &static_d_desc;
389 
390  s->bl_desc.dyn_tree = s->bl_tree;
391  s->bl_desc.stat_desc = &static_bl_desc;
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 }
const static_tree_desc static_bl_desc
Definition: trees.c:131
void init_block(deflate_state *s)
Definition: trees.c:407
void tr_static_init()
Definition: trees.c:232
const static_tree_desc static_d_desc
Definition: trees.c:128
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
const static_tree_desc static_l_desc
Definition: trees.c:125

Referenced by deflateResetKeep().

◆ _tr_stored_block()

void ZLIB_INTERNAL _tr_stored_block ( deflate_state s,
charf buf,
ulg  stored_len,
int  last 
)

Definition at line 863 of file trees.c.

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 }
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
POINT last
Definition: font.c:46
unsigned long ulg
Definition: zutil.h:38
Byte FAR Bytef
Definition: zconf.h:400
#define put_short(s, w)
Definition: trees.c:174
unsigned short ush
Definition: zutil.h:36
#define send_bits(s, value, length)
Definition: trees.c:211
void bi_windup(deflate_state *s)
Definition: trees.c:1190
void zmemcpy(Bytef *dest, const Bytef *source, uInt len)
Definition: zutil.c:17
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
#define STORED_BLOCK
Definition: zutil.h:59

Referenced by _tr_flush_block(), deflate(), and deflate_stored().

◆ _tr_tally()

int ZLIB_INTERNAL _tr_tally ( deflate_state s,
unsigned  dist,
unsigned  lc 
)

Definition at line 1014 of file trees.c.

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 }
#define MIN_MATCH
Definition: zutil.h:64
const int extra_dbits[D_CODES]
Definition: trees.c:66
#define MAX_MATCH
Definition: zutil.h:65
unsigned long ulg
Definition: zutil.h:38
#define MAX_DIST(s)
Definition: deflate.h:289
#define LITERALS
Definition: deflate.h:33
unsigned short ush
Definition: zutil.h:36
#define Assert(cond, msg)
Definition: zutil.h:196
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
#define d_code(dist)
Definition: deflate.h:308
#define Tracev(x)
Definition: zutil.h:198
#define long
Definition: qsort.c:33
uch _length_code[MAX_MATCH-MIN_MATCH+1]
Definition: trees.c:104
FILE * stderr
#define D_CODES
Definition: deflate.h:39
unsigned char uch
Definition: zutil.h:34

◆ bi_flush()

void bi_flush ( deflate_state s)

Definition at line 1173 of file trees.c.

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 }
unsigned char Byte
Definition: zconf.h:391
#define put_short(s, w)
Definition: trees.c:174
#define put_byte(s, c)
Definition: deflate.h:281
GLdouble s
Definition: gl.h:2039

Referenced by _tr_align(), and _tr_flush_bits().

◆ bi_reverse()

unsigned bi_reverse ( unsigned  code,
int  len 
)

Definition at line 1158 of file trees.c.

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 }
GLenum GLsizei len
Definition: glext.h:6722
GLuint res
Definition: glext.h:9613

Referenced by gen_codes(), and tr_static_init().

◆ bi_windup()

void bi_windup ( deflate_state s)

Definition at line 1190 of file trees.c.

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 }
unsigned char Byte
Definition: zconf.h:391
#define put_short(s, w)
Definition: trees.c:174
#define put_byte(s, c)
Definition: deflate.h:281
GLdouble s
Definition: gl.h:2039

Referenced by _tr_flush_block(), and _tr_stored_block().

◆ build_bl_tree()

int build_bl_tree ( deflate_state s)

Definition at line 799 of file trees.c.

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 }
void scan_tree(deflate_state *s, ct_data *tree, int max_code)
Definition: trees.c:703
#define BL_CODES
Definition: deflate.h:42
unsigned long ulg
Definition: zutil.h:38
const uch bl_order[BL_CODES]
Definition: trees.c:72
GLdouble s
Definition: gl.h:2039
#define Tracev(x)
Definition: zutil.h:198
FILE * stderr
void build_tree(deflate_state *s, tree_desc *desc)
Definition: trees.c:615

Referenced by _tr_flush_block().

◆ build_tree()

void build_tree ( deflate_state s,
tree_desc desc 
)

Definition at line 615 of file trees.c.

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++;
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 }
void gen_bitlen(deflate_state *s, tree_desc *desc)
Definition: trees.c:486
GLdouble n
Definition: glext.h:7729
#define SMALLEST
Definition: trees.c:422
void pqdownheap(deflate_state *s, ct_data *tree, int k)
Definition: trees.c:451
const GLfloat * m
Definition: glext.h:10848
struct node node
void gen_codes(ct_data *tree, int max_code, ushf *bl_count)
Definition: trees.c:572
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
static const WCHAR desc[]
Definition: protectdata.c:36
unsigned short ush
Definition: zutil.h:36
#define HEAP_SIZE
Definition: deflate.h:45
GLdouble s
Definition: gl.h:2039
#define pqremove(s, tree, top)
Definition: trees.c:430
#define Freq
Definition: deflate.h:79
FILE * stderr
unsigned char uch
Definition: zutil.h:34
Definition: dlist.c:348

Referenced by _tr_flush_block(), build_bl_tree(), and get_mono_path().

◆ compress_block()

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

Definition at line 1064 of file trees.c.

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 }
const int extra_dbits[D_CODES]
Definition: trees.c:66
int base_length[LENGTH_CODES]
Definition: trees.c:107
#define END_BLOCK
Definition: trees.c:50
#define LITERALS
Definition: deflate.h:33
#define Tracecv(c, x)
Definition: zutil.h:201
#define Assert(cond, msg)
Definition: zutil.h:196
#define send_bits(s, value, length)
Definition: trees.c:211
Definition: id3.c:18
_Check_return_ _CRTIMP int __cdecl isgraph(_In_ int _C)
GLdouble s
Definition: gl.h:2039
int code
Definition: i386-dis.c:3591
const int extra_lbits[LENGTH_CODES]
Definition: trees.c:63
#define d_code(dist)
Definition: deflate.h:308
uch _length_code[MAX_MATCH-MIN_MATCH+1]
Definition: trees.c:104
int base_dist[D_CODES]
Definition: trees.c:110
FILE * stderr
#define D_CODES
Definition: deflate.h:39
#define send_code(s, c, tree)
Definition: trees.c:161
unsigned int uInt
Definition: zconf.h:393

Referenced by _tr_flush_block().

◆ detect_data_type()

int detect_data_type ( deflate_state s)

Definition at line 1124 of file trees.c.

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 }
GLdouble n
Definition: glext.h:7729
#define LITERALS
Definition: deflate.h:33
#define Z_BINARY
Definition: zlib.h:203
GLdouble s
Definition: gl.h:2039
#define Z_TEXT
Definition: zlib.h:204
#define UL
Definition: tui.h:83

Referenced by _tr_flush_block().

◆ gen_bitlen()

void gen_bitlen ( deflate_state s,
tree_desc desc 
)

Definition at line 486 of file trees.c.

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 }
#define MAX_BITS
Definition: deflate.h:48
GLdouble n
Definition: glext.h:7729
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
const GLfloat * m
Definition: glext.h:10848
unsigned long ulg
Definition: zutil.h:38
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLuint base
Definition: 3dtext.c:35
static const WCHAR desc[]
Definition: protectdata.c:36
unsigned short ush
Definition: zutil.h:36
GLfloat f
Definition: glext.h:7540
Definition: id3.c:18
#define HEAP_SIZE
Definition: deflate.h:45
#define for
Definition: utility.h:88
#define Len
Definition: deflate.h:82
GLdouble s
Definition: gl.h:2039
int FAR intf
Definition: zconf.h:403
#define Tracev(x)
Definition: zutil.h:198
#define f
Definition: ke_i.h:83
FILE * stderr

Referenced by build_tree().

◆ gen_codes()

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

Definition at line 572 of file trees.c.

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 }
unsigned bi_reverse(unsigned code, int len)
Definition: trees.c:1158
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
#define MAX_BITS
Definition: deflate.h:48
GLdouble n
Definition: glext.h:7729
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
#define Tracecv(c, x)
Definition: zutil.h:201
unsigned short ush
Definition: zutil.h:36
#define Assert(cond, msg)
Definition: zutil.h:196
#define Code
Definition: deflate.h:80
_Check_return_ _CRTIMP int __cdecl isgraph(_In_ int _C)
GLenum GLsizei len
Definition: glext.h:6722
#define Tracev(x)
Definition: zutil.h:198
FILE * stderr

Referenced by build_tree(), and tr_static_init().

◆ init_block()

void init_block ( deflate_state s)

Definition at line 407 of file trees.c.

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 }
#define BL_CODES
Definition: deflate.h:42
GLdouble n
Definition: glext.h:7729
#define END_BLOCK
Definition: trees.c:50
#define for
Definition: utility.h:88
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
#define D_CODES
Definition: deflate.h:39
#define L_CODES
Definition: deflate.h:36

Referenced by _tr_flush_block(), and _tr_init().

◆ OF() [1/9]

void tr_static_init OF ( (void )

◆ OF() [2/9]

◆ OF() [3/9]

◆ OF() [4/9]

◆ 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]

◆ OF() [9/9]

unsigned bi_reverse OF ( (unsigned value, int length )

◆ pqdownheap()

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

Definition at line 451 of file trees.c.

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 }
#define smaller(tree, n, m, depth)
Definition: trees.c:441
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
GLdouble s
Definition: gl.h:2039
const GLdouble * v
Definition: gl.h:2040
int k
Definition: mpi.c:3369

Referenced by build_tree().

◆ scan_tree()

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

Definition at line 703 of file trees.c.

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 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble n
Definition: glext.h:7729
#define REP_3_6
Definition: trees.c:53
#define REPZ_11_138
Definition: trees.c:59
unsigned short ush
Definition: zutil.h:36
GLdouble s
Definition: gl.h:2039
#define REPZ_3_10
Definition: trees.c:56

Referenced by build_bl_tree().

◆ send_all_trees()

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

Definition at line 834 of file trees.c.

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 }
#define BL_CODES
Definition: deflate.h:42
const uch bl_order[BL_CODES]
Definition: trees.c:72
#define Assert(cond, msg)
Definition: zutil.h:196
#define send_bits(s, value, length)
Definition: trees.c:211
GLdouble s
Definition: gl.h:2039
void send_tree(deflate_state *s, ct_data *tree, int max_code)
Definition: trees.c:748
#define Tracev(x)
Definition: zutil.h:198
FILE * stderr
#define D_CODES
Definition: deflate.h:39
#define L_CODES
Definition: deflate.h:36

Referenced by _tr_flush_block().

◆ send_tree()

void send_tree ( deflate_state s,
ct_data tree,
int  max_code 
)

Definition at line 748 of file trees.c.

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 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble n
Definition: glext.h:7729
#define REP_3_6
Definition: trees.c:53
#define REPZ_11_138
Definition: trees.c:59
#define Assert(cond, msg)
Definition: zutil.h:196
#define send_bits(s, value, length)
Definition: trees.c:211
GLdouble s
Definition: gl.h:2039
#define REPZ_3_10
Definition: trees.c:56
#define send_code(s, c, tree)
Definition: trees.c:161

Referenced by send_all_trees().

◆ tr_static_init()

void tr_static_init ( )

Definition at line 232 of file trees.c.

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 }
unsigned bi_reverse(unsigned code, int len)
Definition: trees.c:1158
const int extra_dbits[D_CODES]
Definition: trees.c:66
const intf * extra_bits
Definition: trees.c:119
const static_tree_desc static_bl_desc
Definition: trees.c:131
int base_length[LENGTH_CODES]
Definition: trees.c:107
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
#define MAX_BITS
Definition: deflate.h:48
GLdouble n
Definition: glext.h:7729
#define LENGTH_CODES
Definition: deflate.h:30
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
void gen_codes(ct_data *tree, int max_code, ushf *bl_count)
Definition: trees.c:572
ct_data static_dtree[D_CODES]
Definition: trees.c:93
unsigned short ush
Definition: zutil.h:36
#define Assert(cond, msg)
Definition: zutil.h:196
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
const static_tree_desc static_d_desc
Definition: trees.c:128
const int extra_blbits[BL_CODES]
Definition: trees.c:69
int code
Definition: i386-dis.c:3591
uch _dist_code[DIST_CODE_LEN]
Definition: trees.c:98
const int extra_lbits[LENGTH_CODES]
Definition: trees.c:63
const static_tree_desc static_l_desc
Definition: trees.c:125
uch _length_code[MAX_MATCH-MIN_MATCH+1]
Definition: trees.c:104
int base_dist[D_CODES]
Definition: trees.c:110
const ct_data * static_tree
Definition: trees.c:118
#define D_CODES
Definition: deflate.h:39
unsigned char uch
Definition: zutil.h:34
#define L_CODES
Definition: deflate.h:36

Referenced by _tr_init().

Variable Documentation

◆ _dist_code

uch _dist_code[DIST_CODE_LEN]

Definition at line 98 of file trees.c.

Referenced by tr_static_init().

◆ _length_code

uch _length_code[MAX_MATCH-MIN_MATCH+1]

Definition at line 104 of file trees.c.

Referenced by _tr_tally(), compress_block(), and tr_static_init().

◆ base_dist

int base_dist[D_CODES]

Definition at line 110 of file trees.c.

Referenced by compress_block(), and tr_static_init().

◆ base_length

◆ 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}

Definition at line 72 of file trees.c.

Referenced by build_bl_tree(), and send_all_trees().

◆ 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}

Definition at line 69 of file trees.c.

Referenced by tr_static_init().

◆ 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}

Definition at line 66 of file trees.c.

Referenced by _tr_tally(), compress_block(), and tr_static_init().

◆ 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}

Definition at line 63 of file trees.c.

Referenced by compress_block(), and tr_static_init().

◆ static_bl_desc

const static_tree_desc static_bl_desc
Initial value:
=
#define BL_CODES
Definition: deflate.h:42
#define MAX_BL_BITS
Definition: trees.c:47
const int extra_blbits[BL_CODES]
Definition: trees.c:69

Definition at line 131 of file trees.c.

Referenced by _tr_init(), and tr_static_init().

◆ static_d_desc

const static_tree_desc static_d_desc
Initial value:
=
const int extra_dbits[D_CODES]
Definition: trees.c:66
#define MAX_BITS
Definition: deflate.h:48
ct_data static_dtree[D_CODES]
Definition: trees.c:93
#define D_CODES
Definition: deflate.h:39

Definition at line 128 of file trees.c.

Referenced by _tr_init(), and tr_static_init().

◆ static_dtree

ct_data static_dtree[D_CODES]

Definition at line 93 of file trees.c.

Referenced by _tr_flush_block(), and tr_static_init().

◆ static_l_desc

const static_tree_desc static_l_desc
Initial value:
=
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
#define MAX_BITS
Definition: deflate.h:48
#define LITERALS
Definition: deflate.h:33
const int extra_lbits[LENGTH_CODES]
Definition: trees.c:63
#define L_CODES
Definition: deflate.h:36

Definition at line 125 of file trees.c.

Referenced by _tr_init(), and tr_static_init().

◆ static_ltree

ct_data static_ltree[L_CODES+2]

Definition at line 86 of file trees.c.

Referenced by _tr_align(), _tr_flush_block(), gen_codes(), and tr_static_init().