1 /* maketrees.c -- output static huffman trees
2  * Copyright (C) 1995-2017 Jean-loup Gailly
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 #include <stdio.h>
7 #include "zbuild.h"
8 #include "deflate.h"
9 #include "trees.h"
10 
11 static ct_data static_ltree[L_CODES+2];
12 /* The static literal tree. Since the bit lengths are imposed, there is no
13  * need for the L_CODES extra codes used during heap construction. However
14  * The codes 286 and 287 are needed to build a canonical tree (see zng_tr_init).
15  */
16 
17 static ct_data static_dtree[D_CODES];
18 /* The static distance tree. (Actually a trivial tree since all codes use 5 bits.)
19  */
20 
21 static unsigned char dist_code[DIST_CODE_LEN];
22 /* Distance codes. The first 256 values correspond to the distances 3 .. 258,
23  * the last 256 values correspond to the top 8 bits of the 15 bit distances.
24  */
25 
26 static unsigned char length_code[MAX_MATCH-MIN_MATCH+1];
27 /* length code for each normalized match length (0 == MIN_MATCH) */
28 
29 static int base_length[LENGTH_CODES];
30 /* First normalized length for each code (0 = MIN_MATCH) */
31 
32 static int base_dist[D_CODES];
33 /* First normalized distance for each code (0 = distance of 1) */
34 
35 
tr_static_init(void)36 static void tr_static_init(void) {
37     int n;        /* iterates over tree elements */
38     int bits;     /* bit counter */
39     int length;   /* length value */
40     int code;     /* code value */
41     int dist;     /* distance index */
42     uint16_t bl_count[MAX_BITS+1];
43     /* number of codes at each bit length for an optimal tree */
44 
45     /* Initialize the mapping length (0..255) -> length code (0..28) */
46     length = 0;
47     for (code = 0; code < LENGTH_CODES-1; code++) {
48         base_length[code] = length;
49         for (n = 0; n < (1 << extra_lbits[code]); n++) {
50             length_code[length++] = (unsigned char)code;
51         }
52     }
53     Assert(length == 256, "tr_static_init: length != 256");
54     /* Note that the length 255 (match length 258) can be represented in two different
55      * ways: code 284 + 5 bits or code 285, so we overwrite length_code[255] to use the best encoding:
56      */
57     length_code[length-1] = (unsigned char)code;
58 
59     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
60     dist = 0;
61     for (code = 0; code < 16; code++) {
62         base_dist[code] = dist;
63         for (n = 0; n < (1 << extra_dbits[code]); n++) {
64             dist_code[dist++] = (unsigned char)code;
65         }
66     }
67     Assert(dist == 256, "tr_static_init: dist != 256");
68     dist >>= 7; /* from now on, all distances are divided by 128 */
69     for ( ; code < D_CODES; code++) {
70         base_dist[code] = dist << 7;
71         for (n = 0; n < (1 << (extra_dbits[code]-7)); n++) {
72             dist_code[256 + dist++] = (unsigned char)code;
73         }
74     }
75     Assert(dist == 256, "tr_static_init: 256+dist != 512");
76 
77     /* Construct the codes of the static literal tree */
78     for (bits = 0; bits <= MAX_BITS; bits++)
79         bl_count[bits] = 0;
80     n = 0;
81     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
82     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
83     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
84     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
85     /* Codes 286 and 287 do not exist, but we must include them in the tree construction
86      * to get a canonical Huffman tree (longest code all ones)
87      */
88     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
89 
90     /* The static distance tree is trivial: */
91     for (n = 0; n < D_CODES; n++) {
92         static_dtree[n].Len = 5;
93         static_dtree[n].Code = (uint16_t)bi_reverse((unsigned)n, 5);
94     }
95 }
96 
97 #  define SEPARATOR(i, last, width) \
98       ((i) == (last)? "\n};\n\n" :    \
99        ((i) % (width) == (width)-1 ? ",\n" : ", "))
100 
gen_trees_header()101 static void gen_trees_header() {
102     int i;
103 
104     printf("#ifndef TREES_TBL_H_\n");
105     printf("#define TREES_TBL_H_\n\n");
106 
107     printf("/* header created automatically with maketrees.c */\n\n");
108 
109     printf("Z_INTERNAL const ct_data static_ltree[L_CODES+2] = {\n");
110     for (i = 0; i < L_CODES+2; i++) {
111         printf("{{%3u},{%u}}%s", static_ltree[i].Code, static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
112     }
113 
114     printf("Z_INTERNAL const ct_data static_dtree[D_CODES] = {\n");
115     for (i = 0; i < D_CODES; i++) {
116         printf("{{%2u},{%u}}%s", static_dtree[i].Code, static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
117     }
118 
119     printf("const unsigned char Z_INTERNAL zng_dist_code[DIST_CODE_LEN] = {\n");
120     for (i = 0; i < DIST_CODE_LEN; i++) {
121         printf("%2u%s", dist_code[i], SEPARATOR(i, DIST_CODE_LEN-1, 20));
122     }
123 
124     printf("const unsigned char Z_INTERNAL zng_length_code[MAX_MATCH-MIN_MATCH+1] = {\n");
125     for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
126         printf("%2u%s", length_code[i], SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
127     }
128 
129     printf("Z_INTERNAL const int base_length[LENGTH_CODES] = {\n");
130     for (i = 0; i < LENGTH_CODES; i++) {
131         printf("%d%s", base_length[i], SEPARATOR(i, LENGTH_CODES-1, 20));
132     }
133 
134     printf("Z_INTERNAL const int base_dist[D_CODES] = {\n");
135     for (i = 0; i < D_CODES; i++) {
136         printf("%5d%s", base_dist[i], SEPARATOR(i, D_CODES-1, 10));
137     }
138 
139     printf("#endif /* TREES_TBL_H_ */\n");
140 }
141 
142 // The output of this application can be piped out to recreate trees.h
main(void)143 int main(void) {
144     tr_static_init();
145     gen_trees_header();
146     return 0;
147 }
148