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 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 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 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 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 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 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 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 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 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