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