ReactOS  0.4.15-dev-5500-g82cf6c2
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 code, int len))
 
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 char uch
Definition: zlib.h:47
GLdouble s
Definition: gl.h:2039
unsigned short ush
Definition: zlib.h:49

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;\
}\
}
Definition: pdh_main.c:93
#define put_short(s, w)
Definition: trees.c:174
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
#define Buf_size
Definition: deflate.h:51
GLuint GLfloat * val
Definition: glext.h:7180
GLenum GLsizei len
Definition: glext.h:6722
GLdouble s
Definition: gl.h:2039
unsigned short ush
Definition: zlib.h:49
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 897 of file trees.c.

899 {
900  send_bits(s, STATIC_TREES<<1, 3);
902 #ifdef ZLIB_DEBUG
903  s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
904 #endif
905  bi_flush(s);
906 }
void bi_flush(deflate_state *s)
Definition: trees.c:1152
ct_data static_ltree[L_CODES+2]
Definition: trees.c:86
#define END_BLOCK
Definition: trees.c:50
#define L(x)
Definition: ntvdm.h:50
#define send_bits(s, value, length)
Definition: trees.c:211
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 887 of file trees.c.

889 {
890  bi_flush(s);
891 }
void bi_flush(deflate_state *s)
Definition: trees.c:1152
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 912 of file trees.c.

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

◆ _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
#define L(x)
Definition: ntvdm.h:50
void tr_static_init()
Definition: trees.c:232
const static_tree_desc static_d_desc
Definition: trees.c:128
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  if (stored_len)
874  zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
875  s->pending += stored_len;
876 #ifdef ZLIB_DEBUG
877  s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
878  s->compressed_len += (stored_len + 4) << 3;
879  s->bits_sent += 2*16;
880  s->bits_sent += stored_len<<3;
881 #endif
882 }
POINT last
Definition: font.c:46
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
#define L(x)
Definition: ntvdm.h:50
#define put_short(s, w)
Definition: trees.c:174
#define send_bits(s, value, length)
Definition: trees.c:211
#define zmemcpy
Definition: inflate.c:38
void bi_windup(deflate_state *s)
Definition: trees.c:1169
GLdouble s
Definition: gl.h:2039
unsigned short ush
Definition: zlib.h:49
unsigned long ulg
Definition: zlib.h:51
Byte FAR Bytef
Definition: zlib.h:41
#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 1015 of file trees.c.

1019 {
1020  s->sym_buf[s->sym_next++] = dist;
1021  s->sym_buf[s->sym_next++] = dist >> 8;
1022  s->sym_buf[s->sym_next++] = lc;
1023  if (dist == 0) {
1024  /* lc is the unmatched char */
1025  s->dyn_ltree[lc].Freq++;
1026  } else {
1027  s->matches++;
1028  /* Here, lc is the match length - MIN_MATCH */
1029  dist--; /* dist = match distance - 1 */
1030  Assert((ush)dist < (ush)MAX_DIST(s) &&
1031  (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1032  (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1033 
1034  s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
1035  s->dyn_dtree[d_code(dist)].Freq++;
1036  }
1037  return (s->sym_next == s->sym_end);
1038 }
#define MIN_MATCH
Definition: zutil.h:64
#define MAX_MATCH
Definition: zutil.h:65
#define MAX_DIST(s)
Definition: deflate.h:284
#define LITERALS
Definition: deflate.h:33
GLdouble s
Definition: gl.h:2039
unsigned short ush
Definition: zlib.h:49
#define d_code(dist)
Definition: deflate.h:303
uch _length_code[MAX_MATCH-MIN_MATCH+1]
Definition: trees.c:104
#define D_CODES
Definition: deflate.h:39
#define Assert(cond, msg)
Definition: inflate.c:41

◆ bi_flush()

void bi_flush ( deflate_state s)

Definition at line 1152 of file trees.c.

1154 {
1155  if (s->bi_valid == 16) {
1156  put_short(s, s->bi_buf);
1157  s->bi_buf = 0;
1158  s->bi_valid = 0;
1159  } else if (s->bi_valid >= 8) {
1160  put_byte(s, (Byte)s->bi_buf);
1161  s->bi_buf >>= 8;
1162  s->bi_valid -= 8;
1163  }
1164 }
#define put_short(s, w)
Definition: trees.c:174
#define put_byte(s, c)
Definition: deflate.h:276
GLdouble s
Definition: gl.h:2039
unsigned char Byte
Definition: zlib.h:37

Referenced by _tr_align(), and _tr_flush_bits().

◆ bi_reverse()

unsigned bi_reverse ( unsigned  code,
int  len 
)

Definition at line 1137 of file trees.c.

1140 {
1141  register unsigned res = 0;
1142  do {
1143  res |= code & 1;
1144  code >>= 1, res <<= 1;
1145  } while (--len > 0);
1146  return res >> 1;
1147 }
GLenum GLsizei len
Definition: glext.h:6722
Definition: inflate.c:139
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 1169 of file trees.c.

1171 {
1172  if (s->bi_valid > 8) {
1173  put_short(s, s->bi_buf);
1174  } else if (s->bi_valid > 0) {
1175  put_byte(s, (Byte)s->bi_buf);
1176  }
1177  s->bi_buf = 0;
1178  s->bi_valid = 0;
1179 #ifdef ZLIB_DEBUG
1180  s->bits_sent = (s->bits_sent+7) & ~7;
1181 #endif
1182 }
#define put_short(s, w)
Definition: trees.c:174
#define put_byte(s, c)
Definition: deflate.h:276
GLdouble s
Definition: gl.h:2039
unsigned char Byte
Definition: zlib.h:37

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
const uch bl_order[BL_CODES]
Definition: trees.c:72
#define Tracev(x)
Definition: inflate.c:43
GLdouble s
Definition: gl.h:2039
unsigned long ulg
Definition: zlib.h:51
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
#define HEAP_SIZE
Definition: deflate.h:45
unsigned char uch
Definition: zlib.h:47
GLdouble s
Definition: gl.h:2039
#define pqremove(s, tree, top)
Definition: trees.c:430
unsigned short ush
Definition: zlib.h:49
#define Freq
Definition: deflate.h:79
FILE * stderr
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 1043 of file trees.c.

1047 {
1048  unsigned dist; /* distance of matched string */
1049  int lc; /* match length or unmatched char (if dist == 0) */
1050  unsigned sx = 0; /* running index in sym_buf */
1051  unsigned code; /* the code to send */
1052  int extra; /* number of extra bits to send */
1053 
1054  if (s->sym_next != 0) do {
1055  dist = s->sym_buf[sx++] & 0xff;
1056  dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8;
1057  lc = s->sym_buf[sx++];
1058  if (dist == 0) {
1059  send_code(s, lc, ltree); /* send a literal byte */
1060  Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1061  } else {
1062  /* Here, lc is the match length - MIN_MATCH */
1063  code = _length_code[lc];
1064  send_code(s, code+LITERALS+1, ltree); /* send the length code */
1065  extra = extra_lbits[code];
1066  if (extra != 0) {
1067  lc -= base_length[code];
1068  send_bits(s, lc, extra); /* send the extra length bits */
1069  }
1070  dist--; /* dist is now the match distance - 1 */
1071  code = d_code(dist);
1072  Assert (code < D_CODES, "bad d_code");
1073 
1074  send_code(s, code, dtree); /* send the distance code */
1075  extra = extra_dbits[code];
1076  if (extra != 0) {
1077  dist -= (unsigned)base_dist[code];
1078  send_bits(s, dist, extra); /* send the extra distance bits */
1079  }
1080  } /* literal or match pair ? */
1081 
1082  /* Check that the overlay between pending_buf and sym_buf is ok: */
1083  Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow");
1084 
1085  } while (sx < s->sym_next);
1086 
1087  send_code(s, END_BLOCK, ltree);
1088 }
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 Tracecv(c, x)
Definition: inflate.c:45
#define LITERALS
Definition: deflate.h:33
#define send_bits(s, value, length)
Definition: trees.c:211
Definition: id3.c:95
_Check_return_ _CRTIMP int __cdecl isgraph(_In_ int _C)
GLdouble s
Definition: gl.h:2039
Definition: inflate.c:139
int code
Definition: main.c:75
const int extra_lbits[LENGTH_CODES]
Definition: trees.c:63
#define d_code(dist)
Definition: deflate.h:303
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 Assert(cond, msg)
Definition: inflate.c:41
#define send_code(s, c, tree)
Definition: trees.c:161
static unsigned(__cdecl *hash_bstr)(bstr_t s)

Referenced by _tr_flush_block().

◆ detect_data_type()

int detect_data_type ( deflate_state s)

Definition at line 1103 of file trees.c.

1105 {
1106  /* block_mask is the bit mask of block-listed bytes
1107  * set bits 0..6, 14..25, and 28..31
1108  * 0xf3ffc07f = binary 11110011111111111100000001111111
1109  */
1110  unsigned long block_mask = 0xf3ffc07fUL;
1111  int n;
1112 
1113  /* Check for non-textual ("block-listed") bytes. */
1114  for (n = 0; n <= 31; n++, block_mask >>= 1)
1115  if ((block_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1116  return Z_BINARY;
1117 
1118  /* Check for textual ("allow-listed") bytes. */
1119  if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
1120  || s->dyn_ltree[13].Freq != 0)
1121  return Z_TEXT;
1122  for (n = 32; n < LITERALS; n++)
1123  if (s->dyn_ltree[n].Freq != 0)
1124  return Z_TEXT;
1125 
1126  /* There are no "block-listed" or "allow-listed" bytes:
1127  * this stream either is empty or has tolerated ("gray-listed") bytes only.
1128  */
1129  return Z_BINARY;
1130 }
#define Z_BINARY
Definition: zlib.h:140
#define Z_TEXT
Definition: zlib.h:141
GLdouble n
Definition: glext.h:7729
#define LITERALS
Definition: deflate.h:33
GLdouble s
Definition: gl.h:2039
#define UL
Definition: tui.h:148

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
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLuint base
Definition: 3dtext.c:35
static const WCHAR desc[]
Definition: protectdata.c:36
#define Tracev(x)
Definition: inflate.c:43
GLfloat f
Definition: glext.h:7540
Definition: id3.c:95
#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: zlib.h:45
unsigned short ush
Definition: zlib.h:49
#define f
Definition: ke_i.h:83
unsigned long ulg
Definition: zlib.h:51
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:1137
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: inflate.c:45
#define Tracev(x)
Definition: inflate.c:43
_Check_return_ _CRTIMP int __cdecl isgraph(_In_ int _C)
_In_ UCHAR _In_ UCHAR _In_ ULONG Code
Definition: wdfdevice.h:1697
GLenum GLsizei len
Definition: glext.h:6722
Definition: inflate.c:139
unsigned short ush
Definition: zlib.h:49
FILE * stderr
#define Assert(cond, msg)
Definition: inflate.c:41

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->sym_next = 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 L(x)
Definition: ntvdm.h:50
#define for
Definition: utility.h:88
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]

◆ 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
GLdouble s
Definition: gl.h:2039
unsigned short ush
Definition: zlib.h:49
#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 Tracev(x)
Definition: inflate.c:43
#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
FILE * stderr
#define D_CODES
Definition: deflate.h:39
#define Assert(cond, msg)
Definition: inflate.c:41
#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 send_bits(s, value, length)
Definition: trees.c:211
GLdouble s
Definition: gl.h:2039
#define REPZ_3_10
Definition: trees.c:56
#define Assert(cond, msg)
Definition: inflate.c:41
#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:1137
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
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
ct_data static_dtree[D_CODES]
Definition: trees.c:93
unsigned char uch
Definition: zlib.h:47
const static_tree_desc static_d_desc
Definition: trees.c:128
const int extra_blbits[BL_CODES]
Definition: trees.c:69
Definition: inflate.c:139
unsigned short ush
Definition: zlib.h:49
uch _dist_code[DIST_CODE_LEN]
Definition: trees.c:98
int code
Definition: main.c:75
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
#define Assert(cond, msg)
Definition: inflate.c:41
#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 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().