1 /* Copyright (C) 2001-2019 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato,
13 CA 94945, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* Generate the CCITTFaxDecode tables */
18 #include "stdio_.h" /* includes std.h */
19 #include "scf.h"
20 #include "malloc_.h"
21 #include "memory_.h"
22
23 typedef void (*cfd_node_proc) (cfd_node *, cfd_node *, uint, int, int, int);
24 typedef void (*cfd_enum_proc) (cfd_node_proc, cfd_node *, cfd_node *, int);
25 static void cfd_build_tree(cfd_node *, cfd_enum_proc, int, FILE *);
26 static void cfd_enumerate_white(cfd_node_proc, cfd_node *, cfd_node *, int);
27 static void cfd_enumerate_black(cfd_node_proc, cfd_node *, cfd_node *, int);
28 static void cfd_enumerate_2d(cfd_node_proc, cfd_node *, cfd_node *, int);
29 static void cfd_enumerate_uncompressed(cfd_node_proc, cfd_node *, cfd_node *, int);
30
main()31 main()
32 {
33 FILE *out = fopen("scfdtab.c", "w");
34 cfd_node area[1 << max(cfd_white_initial_bits, cfd_black_initial_bits)];
35
36 fputs("/* Tables for CCITTFaxDecode filter. */\n\n", out);
37 fputs("/* This file was generated automatically. It is governed by the same terms */\n", out);
38 fputs("/* as the files scfetab.c and scfdgen.c from which it was derived. */\n", out);
39 fputs("/* Consult those files for the licensing terms and conditions. */\n\n", out);
40 fputs("#include \"std.h\"\n", out);
41 fputs("#include \"scommon.h\"\t\t/* for scf.h */\n", out);
42 fputs("#include \"scf.h\"\n\n", out);
43 fputs("/* White decoding table. */\n", out);
44 fputs("const cfd_node cf_white_decode[] = {\n", out);
45 cfd_build_tree(area, cfd_enumerate_white, cfd_white_initial_bits, out);
46 fputs("\n};\n\n", out);
47 fputs("/* Black decoding table. */\n", out);
48 fputs("const cfd_node cf_black_decode[] = {\n", out);
49 cfd_build_tree(area, cfd_enumerate_black, cfd_black_initial_bits, out);
50 fputs("\n};\n\n", out);
51 fputs("/* 2-D decoding table. */\n", out);
52 fputs("const cfd_node cf_2d_decode[] = {\n", out);
53 cfd_build_tree(area, cfd_enumerate_2d, cfd_2d_initial_bits, out);
54 fputs("\n};\n\n", out);
55 fputs("/* Uncompresssed decoding table. */\n", out);
56 fputs("const cfd_node cf_uncompressed_decode[] = {\n", out);
57 cfd_build_tree(area, cfd_enumerate_uncompressed, cfd_uncompressed_initial_bits, out);
58 fputs("\n};\n\n", out);
59 fputs("/* Dummy executable code to pacify compilers. */\n", out);
60 fputs("void scfdtab_dummy(void);\n", out);
61 fputs("void\nscfdtab_dummy(void)\n{\n}\n", out);
62 fclose(out);
63 return 0;
64 }
65
66 /* Initialize first-level leaves, count second-level nodes. */
67 static void
cfd_count_nodes(cfd_node * tree,cfd_node * ignore_extn,uint code,int code_length,int run_length,int initial_bits)68 cfd_count_nodes(cfd_node * tree, cfd_node * ignore_extn,
69 uint code, int code_length, int run_length, int initial_bits)
70 {
71 if (code_length <= initial_bits) {
72 /* Initialize one or more first-level leaves. */
73 int sh = initial_bits - code_length;
74 cfd_node *np = &tree[code << sh];
75 int i;
76
77 for (i = 1 << sh; i > 0; i--, np++)
78 np->run_length = run_length,
79 np->code_length = code_length;
80 } else {
81 /* Note the need for a second level. */
82 cfd_node *np = &tree[code >> (code_length - initial_bits)];
83
84 np->code_length = max(np->code_length, code_length);
85 }
86 }
87
88 /* Initialize second-level nodes. */
89 static void
cfd_init2_nodes(cfd_node * tree,cfd_node * extn,uint code,int code_length,int run_length,int initial_bits)90 cfd_init2_nodes(cfd_node * tree, cfd_node * extn,
91 uint code, int code_length, int run_length, int initial_bits)
92 {
93 int xbits = code_length - initial_bits;
94 int xrep;
95 cfd_node *np1, *np2;
96 int i;
97
98 if (xbits <= 0)
99 return;
100 np1 = &tree[code >> xbits];
101 np2 = &extn[np1->run_length - (1 << initial_bits)];
102 xrep = np1->code_length - code_length;
103 i = 1 << xrep;
104 np2 += (code & ((1 << xbits) - 1)) * i;
105 for (; i > 0; i--, np2++)
106 np2->run_length = run_length,
107 np2->code_length = xbits;
108 }
109
110 /* Enumerate all the relevant white or black codes. */
111 static void
cfd_enumerate_codes(cfd_node_proc proc,cfd_node * tree,cfd_node * extn,int initial_bits,const cfe_run * tt,const cfe_run * mut)112 cfd_enumerate_codes(cfd_node_proc proc, cfd_node * tree, cfd_node * extn,
113 int initial_bits, const cfe_run * tt, const cfe_run * mut)
114 {
115 int i;
116 const cfe_run *ep;
117
118 for (i = 0, ep = tt; i < 64; i++, ep++)
119 (*proc) (tree, extn, ep->code, ep->code_length, i, initial_bits);
120 for (i = 1, ep = mut + 1; i < 41; i++, ep++)
121 (*proc) (tree, extn, ep->code, ep->code_length, i << 6, initial_bits);
122 (*proc) (tree, extn,
123 cf1_run_uncompressed.code, cf1_run_uncompressed.code_length,
124 run_uncompressed, initial_bits);
125 (*proc) (tree, extn,
126 0, run_eol_code_length - 1,
127 run_zeros, initial_bits);
128 }
129 static void
cfd_enumerate_white(cfd_node_proc proc,cfd_node * tree,cfd_node * extn,int initial_bits)130 cfd_enumerate_white(cfd_node_proc proc, cfd_node * tree, cfd_node * extn,
131 int initial_bits)
132 {
133 cfd_enumerate_codes(proc, tree, extn, initial_bits,
134 cf_white_runs.termination, cf_white_runs.make_up);
135 }
136 static void
cfd_enumerate_black(cfd_node_proc proc,cfd_node * tree,cfd_node * extn,int initial_bits)137 cfd_enumerate_black(cfd_node_proc proc, cfd_node * tree, cfd_node * extn,
138 int initial_bits)
139 {
140 cfd_enumerate_codes(proc, tree, extn, initial_bits,
141 cf_black_runs.termination, cf_black_runs.make_up);
142 }
143
144 /* Enumerate the 2-D codes. */
145 static void
cfd_enumerate_2d(cfd_node_proc proc,cfd_node * tree,cfd_node * extn,int initial_bits)146 cfd_enumerate_2d(cfd_node_proc proc, cfd_node * tree, cfd_node * extn,
147 int initial_bits)
148 {
149 int i;
150 const cfe_run *ep;
151
152 (*proc) (tree, extn, cf2_run_pass.code, cf2_run_pass.code_length,
153 run2_pass, initial_bits);
154 (*proc) (tree, extn, cf2_run_horizontal.code, cf2_run_horizontal.code_length,
155 run2_horizontal, initial_bits);
156 for (i = 0; i < countof(cf2_run_vertical); i++) {
157 ep = &cf2_run_vertical[i];
158 (*proc) (tree, extn, ep->code, ep->code_length, i, initial_bits);
159 }
160 (*proc) (tree, extn, cf2_run_uncompressed.code, cf2_run_uncompressed.code_length,
161 run_uncompressed, initial_bits);
162 (*proc) (tree, extn, 0, run_eol_code_length - 1, run_zeros, initial_bits);
163 }
164
165 /* Enumerate the uncompressed codes. */
166 static void
cfd_enumerate_uncompressed(cfd_node_proc proc,cfd_node * tree,cfd_node * extn,int initial_bits)167 cfd_enumerate_uncompressed(cfd_node_proc proc, cfd_node * tree, cfd_node * extn,
168 int initial_bits)
169 {
170 int i;
171 const cfe_run *ep;
172
173 for (i = 0; i < countof(cf_uncompressed); i++) {
174 ep = &cf_uncompressed[i];
175 (*proc) (tree, extn, ep->code, ep->code_length, i, initial_bits);
176 }
177 for (i = 0; i < countof(cf_uncompressed_exit); i++) {
178 ep = &cf_uncompressed_exit[i];
179 (*proc) (tree, extn, ep->code, ep->code_length, i, initial_bits);
180 }
181 }
182
183 /* Build and write out the table. */
184 static void
cfd_build_tree(cfd_node * tree,cfd_enum_proc enum_proc,int initial_bits,FILE * f)185 cfd_build_tree(cfd_node * tree, cfd_enum_proc enum_proc, int initial_bits,
186 FILE * f)
187 {
188 cfd_node *np;
189 const char *prev = "";
190 int i, next;
191 cfd_node *extn;
192
193 memset(tree, 0, sizeof(cfd_node) << initial_bits);
194 /* Construct and write the first level of the tree. */
195 (*enum_proc) (cfd_count_nodes, tree, (cfd_node *) 0, initial_bits);
196 next = 0;
197 for (i = 0, np = tree; i < 1 << initial_bits; i++, np++) {
198 if (np->code_length > initial_bits) { /* second level needed */
199 np->run_length = next + (1 << initial_bits);
200 next += 1 << (np->code_length - initial_bits);
201 }
202 fprintf(f, "%s\t{ %d, %d }", prev, np->run_length, np->code_length);
203 prev = ",\n";
204 }
205 /* Construct and write the second level. */
206 extn = (cfd_node *) malloc(sizeof(cfd_node) * next);
207 for (i = 0, np = extn; i < next; i++, np++)
208 np->run_length = run_error,
209 np->code_length = 0;
210 (*enum_proc) (cfd_init2_nodes, tree, extn, initial_bits);
211 for (i = 0, np = extn; i < next; i++, np++)
212 fprintf(f, ",\n\t{ %d, %d }", np->run_length, np->code_length);
213 free((char *)extn);
214 }
215