1 /* Copyright (C) 2001-2006 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, modified
8    or distributed except as expressly authorized under the terms of that
9    license.  Refer to licensing information at http://www.artifex.com/
10    or contact Artifex Software, Inc.,  7 Mt. Lassen Drive - Suite A-134,
11    San Rafael, CA  94903, U.S.A., +1(415)492-9861, for further information.
12 */
13 
14 /* $Id: scfdgen.c 8250 2007-09-25 13:31:24Z giles $ */
15 /* Generate the CCITTFaxDecode tables */
16 #include "stdio_.h"		/* includes std.h */
17 #include "scf.h"
18 #include "malloc_.h"
19 #include "memory_.h"
20 
21 typedef void (*cfd_node_proc) (cfd_node *, cfd_node *, uint, int, int, int);
22 typedef void (*cfd_enum_proc) (cfd_node_proc, cfd_node *, cfd_node *, int);
23 static void cfd_build_tree(cfd_node *, cfd_enum_proc, int, FILE *);
24 static void cfd_enumerate_white(cfd_node_proc, cfd_node *, cfd_node *, int);
25 static void cfd_enumerate_black(cfd_node_proc, cfd_node *, cfd_node *, int);
26 static void cfd_enumerate_2d(cfd_node_proc, cfd_node *, cfd_node *, int);
27 static void cfd_enumerate_uncompressed(cfd_node_proc, cfd_node *, cfd_node *, int);
28 
main()29 main()
30 {
31     FILE *out = fopen("scfdtab.c", "w");
32     cfd_node area[1 << max(cfd_white_initial_bits, cfd_black_initial_bits)];
33 
34     fputs("/* Copyright (C) 1992, 1993, 1998, 1999 Aladdin Enterprises.  All rights reserved. */\n\n", out);
35     fputs("/* $Id: scfdgen.c 8250 2007-09-25 13:31:24Z giles $ */\n", out);
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