00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdlib.h>
00022 #include <stdio.h>
00023 #include <math.h>
00024 #include "precomp.h"
00025
00026 #ifndef INFINITY
00027 #define INFINITY (1.0 / 0.0)
00028 #endif
00029
00030 typedef struct tnode {
00031 int m, t;
00032 struct tnode ** sons;
00033 } * tree_t;
00034
00035 typedef struct lnode {
00036 tree_t tree;
00037 struct lnode * next;
00038 } * list_t;
00039
00040 list_t list_alloc(tree_t a, list_t s) {
00041 list_t l = (list_t) malloc(sizeof (struct lnode));
00042 l->tree = a;
00043 l->next = s;
00044 return l;
00045 }
00046
00047 tree_t leaf_alloc(int m, int t) {
00048 tree_t a = (tree_t) malloc(sizeof (struct tnode));
00049 a->m = m;
00050 a->t = t;
00051 a->sons = NULL;
00052 return a;
00053 }
00054
00055 tree_t tree_alloc(int m, int t, tree_t * s) {
00056 tree_t a = (tree_t) malloc(sizeof (struct tnode));
00057 a->m = m;
00058 a->t = t;
00059 a->sons = s;
00060 return a;
00061 }
00062
00063 int l2(unsigned long x) {
00064 static char table[256] = {
00065 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
00066 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00067 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00068 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00069 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00070 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00071 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00072 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00073 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00074 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00075 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00076 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00077 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00078 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00079 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00080 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
00081 };
00082
00083 #if __WORDSIZE == 64
00084 if (x >> 32)
00085 if (x >> 48)
00086 if (x >> 56)
00087 return table[x >> 56] + 56;
00088 else
00089 return table[x >> 48] + 48;
00090 else if (x >> 40)
00091 return table[x >> 40] + 40;
00092 else
00093 return table[x >> 32] + 32;
00094 else
00095 #endif
00096 if (x >> 16)
00097 if (x >> 24)
00098 return table[x >> 24] + 24;
00099 else
00100 return table[x >> 16] + 16;
00101 else if (x >> 8)
00102 return table[x >> 8] + 8;
00103 else
00104 return table[x];
00105 }
00106
00107 int is_leaf(int m, int t) {
00108 static int leaf[6] = {7, 5, 4, 4, 3, 3};
00109 if (m < 6)
00110 return (t <= 32);
00111 else if (m > 16)
00112 return (t <= 1);
00113 else if (m > 11)
00114 return (t <= 2);
00115 else
00116 return (leaf[m - 6] >= t);
00117 }
00118
00119 double bino_d(int a, int b) {
00120 if (b == 0)
00121 return 1;
00122 return (bino_d(a, b - 1) * (a - b + 1)) / b;
00123 }
00124
00125 double binomial_d(int a, int b) {
00126 if (b > a / 2)
00127 return bino_d(a, a - b);
00128 if (b < 0)
00129 return 0;
00130 return bino_d(a, b);
00131 }
00132
00133 double log_bino_d(int a, int b) {
00134 if (b == 0)
00135 return 0;
00136 return log_bino_d(a, b - 1) + log2(a - b + 1) - log2(b);
00137 }
00138
00139 double log_binomial_d(int a, int b) {
00140 if (b > a / 2)
00141 return log_bino_d(a, a - b);
00142 if (b < 0)
00143 return -INFINITY;
00144 return log_bino_d(a, b);
00145 }
00146
00147
00148
00149
00150
00151
00152
00153
00154 double dicho_si_lb_node(int i, distrib_t d) {
00155 double y;
00156
00157 if (i == d.max)
00158 y = (1UL << PREC_PROBA) - distrib_get_proba(d, i);
00159 else
00160 y = distrib_get_proba(d, i + 1) - distrib_get_proba(d, i);
00161 y = ldexp(y, -PREC_PROBA);
00162 y += ldexp(1, 2 - PREC_INTER);
00163
00164 return -log2(y);
00165 }
00166
00167 double dicho_si_lb_leaf(int m, int t, int l) {
00168 double y;
00169 unsigned long u;
00170
00171 u = binomial_d(1 << m, t);
00172 u &= (((unsigned) -1) << l);
00173 y = 1.0 / u;
00174 y += ldexp(1, 2 - PREC_INTER - l);
00175
00176 return -log2(y);
00177 }
00178
00179 void dicho_si_lb_rec(int m, int t, precomp_t p, double ** pe) {
00180 int i;
00181 double x;
00182 distrib_t d;
00183
00184 if (t > (1 << m) - t) {
00185 dicho_si_lb_rec(m, (1 << m) - t, p, pe);
00186 pe[m][t] = pe[m][(1 << m) - t];
00187 }
00188 else if ((pe[m][t] == 0) && (t > 0)) {
00189 if (t == 1)
00190 pe[m][t] = m;
00191 else if (is_leaf(m, t)) {
00192 pe[m][t] = dicho_si_lb_leaf(m, t, p.leaf_info[m][t].deadbits);
00193 }
00194 else {
00195 d = precomp_get_distrib(p, m, t);
00196 for (i = d.min; i <= d.max; ++i) {
00197 dicho_si_lb_rec(m - 1, i, p, pe);
00198 dicho_si_lb_rec(m - 1, t - i, p, pe);
00199 x = dicho_si_lb_node(i, d);
00200 x += pe[m - 1][i] + pe[m - 1][t - i];
00201 if ((pe[m][t] == 0) || (x < pe[m][t]))
00202 pe[m][t] = x;
00203 }
00204 }
00205 }
00206 }
00207
00208 double ** dicho_si_lb(precomp_t p) {
00209 int i;
00210 double ** pe, x;
00211
00212 pe = (double **) calloc(p.m + 1, sizeof (double *));
00213 for (i = 0; i <= p.m; ++i)
00214 pe[i] = (double *) calloc(p.t + 1, sizeof (double));
00215
00216 dicho_si_lb_rec(p.m, p.t, p, pe);
00217
00218 return pe;
00219 }
00220
00221
00222
00223
00224
00225
00226 double dicho_si_node(int i, distrib_t d) {
00227 double y;
00228
00229 if (i == d.max)
00230 y = (1UL << PREC_PROBA) - distrib_get_proba(d, i);
00231 else
00232 y = distrib_get_proba(d, i + 1) - distrib_get_proba(d, i);
00233
00234 return PREC_PROBA - log2(y);
00235 }
00236
00237
00238
00239 double dicho_si_leaf(int m, int t, int l) {
00240 unsigned long u;
00241
00242 u = binomial_d(1 << m, t);
00243 u &= (((unsigned) -1) << l);
00244 return log2(u);
00245 }
00246
00247 void dicho_si_rec(int m, int t, precomp_t p, double ** pe) {
00248 int i;
00249 double x;
00250 distrib_t d;
00251
00252 if (t > (1 << m) - t) {
00253 dicho_si_lb_rec(m, (1 << m) - t, p, pe);
00254 pe[m][t] = pe[m][(1 << m) - t];
00255 }
00256 else if ((pe[m][t] == 0) && (t > 0)) {
00257 if (t == 1)
00258 pe[m][t] = m;
00259 else if (is_leaf(m, t))
00260 pe[m][t] = dicho_si_leaf(m, t, p.leaf_info[m][t].deadbits);
00261 else {
00262 d = precomp_get_distrib(p, m, t);
00263 for (i = d.min; i <= d.max; ++i) {
00264 dicho_si_rec(m - 1, i, p, pe);
00265 dicho_si_rec(m - 1, t - i, p, pe);
00266 x = dicho_si_node(i, d) + pe[m - 1][i] + pe[m - 1][t - i];
00267 if ((pe[m][t] == 0) || (x < pe[m][t]))
00268 pe[m][t] = x;
00269 }
00270 }
00271 }
00272 }
00273
00274 double ** dicho_si(precomp_t p) {
00275 int i;
00276 double ** pe, x;
00277
00278 pe = (double **) calloc(p.m + 1, sizeof (double *));
00279 for (i = 0; i <= p.m; ++i)
00280 pe[i] = (double *) calloc(p.t + 1, sizeof (double));
00281
00282
00283 dicho_si_rec(p.m, p.t, p, pe);
00284
00285 return pe;
00286 }
00287
00288 double ** si_lb;
00289 double min = 0;
00290
00291
00292
00293
00294 #define EPSILON (1.0 / (1UL << PREC_INTER))
00295
00296 double * dicho_self_info_bounds(precomp_t p) {
00297 double * res;
00298 double ** si;
00299
00300 res = malloc(2 * sizeof (double));
00301
00302
00303
00304
00305 si = dicho_si(p);
00306
00307
00308
00309
00310 si_lb = dicho_si_lb(p);
00311
00312 res[0] = si_lb[p.m][p.t] + (p.real_m - p.m) * p.real_t + EPSILON;
00313 res[1] = si[p.m][p.t] + (p.real_m - p.m) * p.real_t + EPSILON;
00314 free(si);
00315 free(si_lb);
00316
00317 return res;
00318 }
00319
00320 unsigned long update_delta(int i, distrib_t d, unsigned long delta) {
00321 unsigned long u;
00322
00323 u = (i == d.max) ? delta : ((distrib_get_proba(d, i + 1) * delta) >> PREC_PROBA);
00324 u -= ((distrib_get_proba(d, i) * delta) >> PREC_PROBA);
00325
00326 return u;
00327 }
00328
00329 unsigned long adjust_delta(unsigned long delta, int * l) {
00330 *l = PREC_INTER - l2(delta - 1) - 1;
00331 return (delta << (*l));
00332 }
00333
00334 #define ABOVE_MIN(len, delta, z) ((len) + PREC_INTER - log2(delta) + (z) + EPSILON >= min)
00335
00336 double dicho_si_from_list(list_t l, unsigned long delta, int len, double z, precomp_t p) {
00337 int m, t, j_up, j_down;
00338 unsigned long u, delta_down, delta_up;
00339 double x;
00340
00341 if (ABOVE_MIN(len, delta, z))
00342 return INFINITY;
00343
00344 if (l == NULL)
00345 return min = len + PREC_INTER - log2(delta);
00346
00347 t = l->tree->t;
00348 m = l->tree->m;
00349
00350 if (t == 0)
00351 return dicho_si_from_list(l->next, delta, len, z, p);
00352
00353 if (t == 1)
00354 return dicho_si_from_list(l->next, delta, len + m, z - m, p);
00355
00356 x = INFINITY;
00357
00358 z -= si_lb[m][t];
00359 len += p.leaf_info[m][t].deadbits;
00360
00361
00362
00363
00364
00365 u = binomial_d(1 << m, t);
00366 u >>= p.leaf_info[m][t].deadbits;
00367
00368 delta_up = adjust_delta((delta - 1) / u + 1, &j_up);
00369
00370 delta_down = adjust_delta(delta / u, &j_down);
00371
00372 x = dicho_si_from_list(l->next, delta_up, len + j_up, z, p);
00373
00374 if ((x == INFINITY) && (delta_up != delta_down))
00375 x = dicho_si_from_list(l->next, delta_down, len + j_down, z, p);
00376
00377 return x;
00378 }
00379
00380 double tree_search(tree_t a, list_t path, list_t todo, unsigned long delta, int len, double z, precomp_t p) {
00381 int i, j, m, t;
00382 unsigned long u;
00383 distrib_t d;
00384 list_t l;
00385 double x;
00386
00387 m = a->m;
00388 t = a->t;
00389
00390 if (ABOVE_MIN(len, delta, z + si_lb[m][t]))
00391 return INFINITY;
00392
00393 x = INFINITY;
00394
00395 if (a->sons == NULL) {
00396 z += si_lb[m][t];
00397 l = list_alloc(a, path);
00398 if (todo == NULL)
00399 x = dicho_si_from_list(l, delta, len, z, p);
00400 else {
00401 z -= si_lb[todo->tree->m][todo->tree->t];
00402 x = tree_search(todo->tree, l, todo->next, delta, len, z, p);
00403 }
00404 free(l);
00405 }
00406 else {
00407 d = precomp_get_distrib(p, m, t);
00408 for (i = d.min; (i <= d.max) && (x == INFINITY); ++i) {
00409 u = update_delta(i, d, delta);
00410 u = adjust_delta(u, &j);
00411 l = list_alloc(a->sons[t - i], todo);
00412 x = tree_search(a->sons[i], path, l, u, len + j, z + si_lb[m - 1][t - i], p);
00413 free(l);
00414 }
00415 }
00416
00417 return x;
00418 }
00419
00420 tree_t dicho_build_tree(int m, int t, precomp_t p) {
00421 unsigned long u;
00422 int i;
00423 distrib_t d;
00424 tree_t * a;
00425
00426 if (t == 0)
00427 return leaf_alloc(m, t);
00428
00429 if (t == 1)
00430 return leaf_alloc(m, t);
00431
00432 if (t > (1 << m) - t)
00433 return dicho_build_tree(m, (1 << m) - t, p);
00434
00435 if (is_leaf(m, t))
00436 return leaf_alloc(m, t);
00437
00438 d = precomp_get_distrib(p, m, t);
00439 a = malloc((d.max + 1) * sizeof (tree_t *));
00440 for (i = d.min; i <= d.max; ++i)
00441 a[i] = dicho_build_tree(m - 1, i, p);
00442
00443 return tree_alloc(m, t, a);
00444 }
00445
00446 void clear_tree(tree_t a, precomp_t p) {
00447 int i;
00448 distrib_t d;
00449
00450 if (a->sons != NULL) {
00451 d = precomp_get_distrib(p, a->m, a->t);
00452 for (i = d.min; i <= d.max; ++i)
00453 clear_tree(a->sons[i], p);
00454 free(a->sons);
00455 }
00456 free(a);
00457 }
00458
00459 double dicho_searchmin(precomp_t p, double min_value) {
00460 double res;
00461 tree_t a;
00462
00463
00464 si_lb = dicho_si_lb(p);
00465 min = min_value - (p.real_m - p.m) * p.real_t;
00466
00467 a = dicho_build_tree(p.m, p.t, p);
00468 res = tree_search(a, NULL, NULL, 1UL << PREC_INTER, 0, 0, p);
00469 clear_tree(a, p);
00470 free(si_lb);
00471
00472 return min + (p.real_m - p.m) * p.real_t;
00473 }
00474
00475 distrib_t init_proba(int m, int t, int i) {
00476 int n, j;
00477 distrib_t dist;
00478 double x, * y;
00479
00480 dist.min = i;
00481 dist.max = t - i;
00482 dist.prob = (unsigned long *) malloc((dist.max - dist.min + 1) * sizeof (unsigned long));
00483 y = (double *) malloc((dist.max + 1) * sizeof (double));
00484 n = 1 << (m - 1);
00485
00486 for (x = 0, j = dist.min; j <= dist.max; ++j) {
00487 y[j] = x;
00488 x += binomial_d(n, j) * binomial_d(n, t - j);
00489 }
00490
00491 for (j = dist.min; j <= dist.max; ++j)
00492 distrib_get_proba(dist, j) = (unsigned long) round(ldexp(y[j] / x, PREC_PROBA));
00493
00494 free(y);
00495
00496 return dist;
00497 }
00498
00499 leaf_info_t leaf_info(int m, int t) {
00500 int i, l;
00501 double x, y;
00502 unsigned long u, v;
00503 leaf_info_t li;
00504
00505 u = binomial_d(1 << m, t);
00506
00507 i = l2(u);
00508 l = i - PREC_PROBA;
00509 if (l < 0)
00510 l = 0;
00511 x = 0;
00512 for (; l < i - 2; ++l) {
00513 v = u & (((unsigned) -1) << l);
00514 y = 1.0 / v;
00515 y += ldexp(1, 2 - PREC_INTER - l);
00516 if ((x == 0) || (y < x)) {
00517 li.deadbits = l;
00518 li.maximum = u >> l;
00519 x = y;
00520 }
00521 }
00522
00523 return li;
00524 }
00525
00526
00527
00528 double max_si_loss(int m, int t, distrib_t d) {
00529 int i;
00530 double x, y;
00531
00532 for (y = 0, i = d.min; i <= d.max; ++i) {
00533 x = binomial_d(1 << (m - 1), i) * binomial_d(1 << (m - 1), t - i);
00534 x = binomial_d(1 << m, t) / x;
00535 x = log2(x);
00536
00537 x -= dicho_si_lb_node(i, d);
00538 if (x > y)
00539 y = x;
00540 }
00541 return y;
00542 }
00543
00544 void distrib_clear(distrib_t dist) {
00545 free(dist.prob);
00546 }
00547
00548 precomp_t precomp_build(int m, int t, int reduc) {
00549 int i, j, k;
00550 double x, y, z;
00551 int * start, * end;
00552 distrib_t tmp;
00553 precomp_t p;
00554
00555 p.real_m = m;
00556 p.real_t = t;
00557 m -= reduc;
00558 p.m = m;
00559 t = (t < (1 << m) - t) ? t : ((1 << m) - t);
00560 p.t = t;
00561
00562 p.leaf_info = (leaf_info_t **) malloc((m + 1) * sizeof (leaf_info_t *));
00563 for (i = (m < 5) ? m : 5; i <= m; ++i) {
00564 for (j = (1 << (i - 1)); j >= 2; --j)
00565 if (is_leaf(i, j))
00566 break;
00567 p.leaf_info[i] = (leaf_info_t *) malloc((j + 1) * sizeof (leaf_info_t));
00568 for (k = 2; k <= j; ++k)
00569 p.leaf_info[i][k] = leaf_info(i, k);
00570 }
00571
00572 if (is_leaf(m, t)) {
00573 p.distrib = NULL;
00574 p.offset = NULL;
00575 return p;
00576 }
00577 p.distrib = (distrib_t **) calloc(m + 1, sizeof (distrib_t *));
00578 p.offset = start = calloc(m + 1, sizeof (int));
00579 end = calloc(m + 1, sizeof (int));
00580 start[m] = end[m] = t;
00581 while (start[m] <= end[m]) {
00582 p.distrib[m] = (distrib_t *) calloc(end[m] - start[m] + 1, sizeof (distrib_t));
00583 for (x = 0, i = 0; i <= end[m] - start[m]; ++i) {
00584 if (i + start[m] > (1 << (m - 1))) {
00585 fprintf(stderr, "erreur init : m=%d t=%d\n", m, i + start[m]);
00586 exit(0);
00587 }
00588 k = (i + start[m]) / 2;
00589 p.distrib[m][i] = init_proba(m, i + start[m], k);
00590 z = max_si_loss(m, i + start[m], p.distrib[m][i]);
00591 for (--k; k >= 0; --k) {
00592 tmp = init_proba(m, i + start[m], k);
00593 y = max_si_loss(m, i + start[m], tmp);
00594 if (y < z) {
00595 distrib_clear(p.distrib[m][i]);
00596 p.distrib[m][i] = tmp;
00597 z = y;
00598 j = k;
00599 }
00600 else
00601 distrib_clear(tmp);
00602 }
00603 }
00604
00605 for (j = 0, k = end[m], i = 0; i <= end[m] - start[m]; ++i) {
00606 if (p.distrib[m][i].max > j)
00607 j = p.distrib[m][i].max;
00608 if (p.distrib[m][i].min < k)
00609 k = p.distrib[m][i].min;
00610 }
00611 m--;
00612 end[m] = j;
00613 start[m] = k;
00614 #define MIN(x,y) ((x < y) ? x : y)
00615
00616
00617 k = MIN(start[m], (1 << m) - end[m]);
00618 j = MIN(end[m], (1 << m) - start[m]);
00619 start[m] = k;
00620 end[m] = MIN(j, 1 << (m - 1));
00621
00622 while (is_leaf(m, start[m]) && (start[m] <= end[m])) {
00623 ++start[m];
00624 }
00625 }
00626 free(end);
00627
00628 return p;
00629 }
00630
00631 void write_precomp(precomp_t p, FILE * output_stream) {
00632 int i, j, k, l;
00633 int * start, * end;
00634 distrib_t ** d;
00635
00636 start = (int *) calloc(p.m + 1, sizeof (int));
00637 end = (int *) calloc(p.m + 1, sizeof (int));
00638
00639 d = p.distrib;
00640 l = p.m;
00641 start[l] = end[l] = p.t;
00642 while (l > 5) {
00643 for (j = 0, k = end[l], i = 0; i <= end[l] - start[l]; ++i) {
00644 if (d[l][i].max > j)
00645 j = d[l][i].max;
00646 if (d[l][i].min < k)
00647 k = d[l][i].min;
00648 }
00649 end[l - 1] = j;
00650 start[l - 1] = k;
00651
00652 k = MIN(start[l - 1], (1 << (l - 1)) - end[l - 1]);
00653 j = MIN(end[l - 1], (1 << (l - 1)) - start[l - 1]);
00654 start[l - 1] = k;
00655 end[l - 1] = MIN(j, 1 << (l - 2));
00656
00657 while (is_leaf(l - 1, start[l - 1]))
00658 start[l - 1]++;
00659 if (start[l - 1] > end[l - 1])
00660 break;
00661 l--;
00662 }
00663 fprintf(output_stream,"#include <stdlib.h>\n");
00664 fprintf(output_stream,"#include \"precomp.h\"\n\n");
00665 fprintf(output_stream,"precomp_t cwdata = {\n %d, %d, %d, %d, (int []) {", p.m, p.t, p.real_m, p.real_t);
00666 for (k = 0; k < l; ++k)
00667 fprintf(output_stream,"0, ");
00668 fprintf(output_stream,"%d", start[l]);
00669 for (k = l + 1; k <= p.m; ++k)
00670 fprintf(output_stream,", %d", start[k]);
00671 fprintf(output_stream,"},\n");
00672 if (p.m > 5) {
00673 fprintf(output_stream," (distrib_t *[]) {\n ");
00674 for (k = 0; k < l; ++k)
00675 fprintf(output_stream,"NULL, ");
00676 fprintf(output_stream,"\n");
00677 for (; l <= p.m; ++l) {
00678 fprintf(output_stream, " (distrib_t []) {\n");
00679 for (i = 0; i <= end[l] - start[l]; ++i) {
00680 fprintf(output_stream, " {%d, %d, (unsigned long []) {0", d[l][i].min, d[l][i].max);
00681 for (j = d[l][i].min + 1; j <= d[l][i].max; ++j)
00682 fprintf(output_stream, ", %u", distrib_get_proba(d[l][i], j));
00683 fprintf(output_stream, "}}");
00684 if (i < end[l] - start[l])
00685 fprintf(output_stream, ",\n");
00686 else
00687 fprintf(output_stream, "\n");
00688 }
00689 fprintf(output_stream, " }");
00690 if (l < p.m)
00691 fprintf(output_stream, ",\n");
00692 else
00693 fprintf(output_stream, "\n");
00694 }
00695 fprintf(output_stream, " },\n");
00696 }
00697 else
00698 fprintf(output_stream," NULL,\n");
00699 fprintf(output_stream," (leaf_info_t *[]) {\n NULL, NULL, NULL, NULL, NULL,\n");
00700 l = p.m;
00701 for (i = 5; i <= p.m; ++i) {
00702 fprintf(output_stream, " (leaf_info_t []) {{0, 0}, {0, 0}, ");
00703 for (j = (1 << (i - 1)); j >= 2; --j)
00704 if (is_leaf(i, j))
00705 break;
00706 for (k = 2; k <= j; ++k) {
00707 fprintf(output_stream, "{%d, %d}", p.leaf_info[i][k].maximum, p.leaf_info[i][k].deadbits);
00708 if (k < j)
00709 fprintf(output_stream, ", ");
00710 else
00711 fprintf(output_stream, "}");
00712 }
00713 if (i == p.m)
00714 fprintf(output_stream, "\n");
00715 else if (!is_leaf(i + 1, 2)) {
00716 fprintf(output_stream, "\n");
00717 break;
00718 }
00719 else
00720 fprintf(output_stream, ",\n");
00721 }
00722 fprintf(output_stream, " }\n};\n");
00723 free(start);
00724 free(end);
00725 }
00726
00727 void clear_precomp(precomp_t p) {
00728 int m, i, j, end;
00729
00730 if ((p.t > (1 << p.m)) || is_leaf(p.m, p.t))
00731 return;
00732
00733 end = p.t;
00734 for (m = p.m; m >= 6; --m) {
00735 end = MIN(MIN(end, (1 << m) - p.offset[m]), 1 << (m - 1));
00736 j = end - p.offset[m];
00737 if (j < 0)
00738 break;
00739 end = 0;
00740 for (i = 0; i <= j; ++i) {
00741 if (end < p.distrib[m][i].max)
00742 end = p.distrib[m][i].max;
00743 distrib_clear(p.distrib[m][i]);
00744 }
00745
00746 end = MIN(end, (1 << (m - 1)) - p.offset[m - 1]);
00747 free(p.distrib[m]);
00748 }
00749 free(p.offset);
00750 free(p.distrib);
00751 }