Bug Summary

File:Frameworks/FriBidi Framework/fribidi-0.10.7/packtab.c
Location:line 179, column 10
Description:dead store

Annotated Source Code

1/* PackTab - Pack a static table
2 * Copyright (C) 2001 Behdad Esfahbod.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library, in a file named COPYING; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
17 * Boston, MA 02111-1307, USA
18 *
19 * For licensing issues, contact <fwpg@sharif.edu>.
20 */
21
22/*
23 8 <= N <= 2^21
24 int key
25 1 <= max_depth <= 21
26*/
27#include <stdio.h>
28#include <stdlib.h>
29#include <string.h>
30
31#include "packtab.h"
32
33typedef int uni_table[1024 * 1024 * 2];
34static int n, a, max_depth, N, digits, tab_width, per_row;
35static uni_table temp, x, perm, *tab;
36static int pow[22], cluster, cmpcluster;
37static const char * const *name, *key_type_name, *table_name, *macro_name;
38static FILE *f;
39
40static void
41init (int *base)
42{
43 int i;
44 pow[0] = 1;
45 for (i = 1; i <= 21; i++)
46 pow[i] = pow[i - 1] * 2;
47 for (n = 21; pow[n] > N || N % pow[n]; n--)
48 ;
49 digits = (n + 3) / 4;
50 for (i = 6; i; i--)
51 if (pow[i] * (tab_width + 1) < 80)
52 break;
53 per_row = pow[i];
54}
55
56static int
57compare (const void *r,
58 const void *s)
59{
60 int i;
61 for (i = 0; i < cmpcluster; i++)
62 if (((int *) r)[i] != ((int *) s)[i])
63 return ((int *) r)[i] - ((int *) s)[i];
64 return 0;
65}
66
67static int lev, p[22], t[22], c[22], clusters[22], s, nn;
68static int best_lev, best_p[22], best_t[22], best_c[22], best_cluster[22],
69 best_s;
70
71static void
72found (void)
73{
74 int i;
75
76 if (s < best_s)
77 {
78 best_s = s;
79 best_lev = lev;
80 for (i = 0; i <= lev; i++)
81 {
82 best_p[i] = p[i];
83 best_c[i] = c[i];
84 best_t[i] = t[i];
85 best_cluster[i] = clusters[i];
86 }
87 }
88}
89
90static void
91bt (int node_size)
92{
93 int i, j, k, y, sbak, key_bytes;
94
95 if (t[lev] == 1)
96 {
97 found ();
98 return;
99 }
100 if (lev == max_depth)
101 return;
102
103 for (i = 1 - t[lev] % 2; i <= nn + (t[lev] >> nn) % 2; i++)
104 {
105 nn -= (p[lev] = i);
106 clusters[lev] = cluster = (i && nn >= 0) ? pow[i] : t[lev];
107 cmpcluster = cluster + 1;
108
109 t[lev + 1] = (t[lev] - 1) / cluster + 1;
110 for (j = 0; j < t[lev + 1]; j++)
111 {
112 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
113 cluster * sizeof (tab[lev][0]));
114 temp[j * cmpcluster + cluster] = j;
115 }
116 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
117 for (j = 0; j < t[lev + 1]; j++)
118 {
119 perm[j] = temp[j * cmpcluster + cluster];
120 temp[j * cmpcluster + cluster] = 0;
121 }
122 k = 1;
123 y = 0;
124 tab[lev + 1][perm[0]] = perm[0];
125 for (j = 1; j < t[lev + 1]; j++)
126 {
127 if (compare (temp + y, temp + y + cmpcluster))
128 {
129 k++;
130 tab[lev + 1][perm[j]] = perm[j];
131 }
132 else
133 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
134 y += cmpcluster;
135 }
136 sbak = s;
137 s += k * node_size * cluster;
138 c[lev] = k;
139
140 if (s >= best_s)
141 {
142 s = sbak;
143 nn += i;
144 return;
145 }
146
147 key_bytes = k * cluster;
148 key_bytes = key_bytes <= 0xff ? 1 : key_bytes <= 0xffff ? 2 : 4;
149 lev++;
150 bt (key_bytes);
151 lev--;
152
153 s = sbak;
154 nn += i;
155 }
156}
157
158static void
159solve (void)
160{
161 best_lev = max_depth + 2;
162 best_s = N * a * 2;
163 lev = 0;
164 s = 0;
165 nn = n;
166 t[0] = N;
167 bt (a);
168}
169
170static void
171write_array (int max_key)
172{
173 int i, j, k, y, ii, ofs;
174 const char *key_type;
175
176 if (best_t[lev] == 1)
177 return;
178
Although the value stored to 'i' is used in the enclosing expression, the value is never actually read from 'i'
179 nn -= (i = best_p[lev]);
180 cluster = best_cluster[lev];
181 cmpcluster = cluster + 1;
182
183 t[lev + 1] = best_t[lev + 1];
184 for (j = 0; j < t[lev + 1]; j++)
185 {
186 memmove (temp + j * cmpcluster, tab[lev] + j * cluster,
187 cluster * sizeof (tab[lev][0]));
188 temp[j * cmpcluster + cluster] = j;
189 }
190 qsort (temp, t[lev + 1], cmpcluster * sizeof (temp[0]), compare);
191 for (j = 0; j < t[lev + 1]; j++)
192 {
193 perm[j] = temp[j * cmpcluster + cluster];
194 temp[j * cmpcluster + cluster] = 0;
195 }
196 k = 1;
197 y = 0;
198 tab[lev + 1][perm[0]] = x[0] = perm[0];
199 for (j = 1; j < t[lev + 1]; j++)
200 {
201 if (compare (temp + y, temp + y + cmpcluster))
202 {
203 x[k] = perm[j];
204 tab[lev + 1][perm[j]] = x[k];
205 k++;
206 }
207 else
208 tab[lev + 1][perm[j]] = tab[lev + 1][perm[j - 1]];
209 y += cmpcluster;
210 }
211
212 i = 0;
213 for (ii = 1; ii < k; ii++)
214 if (x[ii] < x[i])
215 i = ii;
216
217 key_type = (!lev ? key_type_name :
218 (max_key <= 0xff ? "PACKTAB_UINT8" :
219 (max_key <= 0xffff ? "PACKTAB_UINT16" : "PACKTAB_UINT32")));
220 fprintf (f, "static const %s %sLevel%d[%d*%d] = {", key_type, table_name,
221 best_lev - lev - 1, cluster, k);
222 ofs = 0;
223 for (ii = 0; ii < k; ii++)
224 {
225 int kk, jj;
226 fprintf (f, "\n\n#define %sLevel%d_%0*X 0x%0X\n", table_name,
227 best_lev - lev - 1, digits, x[i] * pow[n - nn], ofs);
228 kk = x[i] * cluster;
229 if (!lev)
230 if (name)
231 for (j = 0; j < cluster; j++)
232 {
233 if (!(j % per_row) && j != cluster - 1)
234 fprintf (f, "\n ");
235 fprintf (f, "%*s,", tab_width, name[tab[lev][kk++]]);
236 }
237 else
238 for (j = 0; j < cluster; j++)
239 {
240 if (!(j % per_row) && j != cluster - 1)
241 fprintf (f, "\n ");
242 fprintf (f, "%*d,", tab_width, tab[lev][kk++]);
243 }
244 else
245 for (j = 0; j < cluster; j++, kk++)
246 fprintf (f, "\n %sLevel%d_%0*X, /* %0*X..%0*X */", table_name,
247 best_lev - lev, digits,
248 tab[lev][kk] * pow[n - nn - best_p[lev]], digits,
249 x[i] * pow[n - nn] + j * pow[n - nn - best_p[lev]], digits,
250 x[i] * pow[n - nn] + (j + 1) * pow[n - nn - best_p[lev]] -
251 1);
252 ofs += cluster;
253 jj = i;
254 for (j = 0; j < k; j++)
255 if (x[j] > x[i] && (x[j] < x[jj] || jj == i))
256 jj = j;
257 i = jj;
258 }
259 fprintf (f, "\n};\n\n");
260 lev++;
261 write_array (cluster * k);
262 lev--;
263}
264
265static void
266write_source (void)
267{
268 int i, j;
269
270 lev = 0;
271 s = 0;
272 nn = n;
273 t[0] = N;
274 fprintf (f, "\n" "/* *INDENT-OFF* */\n\n");
275 write_array (0);
276 fprintf (f, "/* *INDENT-ON* */\n\n");
277
278 fprintf (f, "#define %s(x)", macro_name);
279 j = 1;
280 for (i = best_lev - 1; i >= 0; i--)
281 {
282 fprintf (f, "\t\\\n\t%sLevel%d[(x)", table_name, i);
283 if (j != 1)
284 fprintf (f, "/%d", j);
285 if (i)
286 fprintf (f, "%%%d +", pow[best_p[best_lev - 1 - i]]);
287 j *= best_cluster[best_lev - 1 - i];
288 }
289 for (i = 0; i < best_lev; i++)
290 fprintf (f, "]");
291 fprintf (f, "\n\n");
292}
293
294static void
295write_out (void)
296{
297 int i;
298 fprintf (f, "/*\n"
299 " Automatically generated by packtab.c version %d\n\n"
300 " just use %s(key)\n\n"
301 " assumed sizeof(%s) == %d\n"
302 " required memory: %d\n"
303 " lookups: %d\n"
304 " partition shape: %s",
305 packtab_version2, macro_name, key_type_name, a, best_s, best_lev,
306 table_name);
307 for (i = best_lev - 1; i >= 0; i--)
308 fprintf (f, "[%d]", best_cluster[i]);
309 fprintf (f, "\n" " different table entries:");
310 for (i = best_lev - 1; i >= 0; i--)
311 fprintf (f, " %d", best_c[i]);
312 fprintf (f, "\n*/\n");
313 write_source ();
314}
315
316int
317pack_table (int *base,
318 int key_num,
319 int key_size,
320 int p_max_depth,
321 int p_tab_width,
322 const char * const *p_name,
323 const char *p_key_type_name,
324 const char *p_table_name,
325 const char *p_macro_name,
326 FILE * out)
327{
328 N = key_num;
329 a = key_size;
330 max_depth = p_max_depth;
331 tab_width = p_tab_width;
332 name = p_name;
333 key_type_name = p_key_type_name;
334 table_name = p_table_name;
335 macro_name = p_macro_name;
336 f = out;
337 init (base);
338 if (!(tab = malloc ((n + 1) * sizeof (tab[0]))))
339 return 0;
340 memmove (tab[0], base, key_num * sizeof (int));
341 solve ();
342 write_out ();
343 free (tab);
344 return 1;
345}
346
347/* End of packtab.c */