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 <string.h>
00024 #include <math.h>
00025 #include "buff.h"
00026 #include "arith.h"
00027 #include "precomp.h"
00028
00029 double round(double);
00030 int l2(unsigned long x);
00031
00032 typedef struct elt {
00033 int * element;
00034 int taille, nombre;
00035 int pos;
00036 unsigned long valeur, maximum;
00037 struct elt * suivant;
00038 } * liste_t;
00039
00040 liste_t liste_todo;
00041 liste_t liste_inv;
00042 int * aux;
00043
00044 liste_t liste_alloc(liste_t s) {
00045 liste_t l = (liste_t) malloc(sizeof (struct elt));
00046 l->suivant = s;
00047 return l;
00048 }
00049
00050 void liste_free(liste_t l) {
00051 if (l != NULL)
00052 liste_free(l->suivant);
00053 free(l);
00054 }
00055
00056 int is_leaf(int m, int t) {
00057 static int feuille[6] = {7, 5, 4, 4, 3, 3};
00058 if (m < 6)
00059 return (t <= 32);
00060 else if (m > 16)
00061 return (t <= 1);
00062 else if (m > 11)
00063 return (t <= 2);
00064 else
00065 return (feuille[m - 6] >= t);
00066 }
00067
00068 int max_bino[] = {0, 0, 0, 0, 0, 128, 64, 64, 32, 32, 32, 32, 32, 32, 32, 32, 32};
00069 unsigned long * table_bino[] = {
00070 NULL,
00071 NULL,
00072 NULL,
00073 NULL,
00074 NULL,
00075 (unsigned long [129]) {
00076 0U, 0U, 0U, 0U, 0U, 1U, 6U, 21U, 56U, 126U, 252U, 462U, 792U,
00077 1287U, 2002U, 3003U, 4368U, 6188U, 8568U, 11628U, 15504U, 20349U,
00078 26334U, 33649U, 42504U, 53130U, 65780U, 80730U, 98280U, 118755U,
00079 142506U, 169911U, 201376U, 237336U, 278256U, 324632U, 376992U,
00080 435897U, 501942U, 575757U, 658008U, 749398U, 850668U, 962598U,
00081 1086008U, 1221759U, 1370754U, 1533939U, 1712304U, 1906884U,
00082 2118760U, 2349060U, 2598960U, 2869685U, 3162510U, 3478761U,
00083 3819816U, 4187106U, 4582116U, 5006386U, 5461512U, 5949147U,
00084 6471002U, 7028847U, 7624512U, 8259888U, 8936928U, 9657648U,
00085 10424128U, 11238513U, 12103014U, 13019909U, 13991544U, 15020334U,
00086 16108764U, 17259390U, 18474840U, 19757815U,21111090U, 22537515U,
00087 24040016U, 25621596U, 27285336U, 29034396U, 30872016U, 32801517U,
00088 34826302U, 36949857U,39175752U, 41507642U, 43949268U, 46504458U,
00089 49177128U, 51971283U, 54891018U, 57940519U, 61124064U,
00090 64446024U,67910864U, 71523144U, 75287520U, 79208745U, 83291670U,
00091 87541245U, 91962520U, 96560646U, 101340876U, 106308566U,
00092 111469176U, 116828271U, 122391522U, 128164707U, 134153712U,
00093 140364532U, 146803272U, 153476148U, 160389488U,167549733U,
00094 174963438U, 182637273U, 190578024U, 198792594U, 207288004U,
00095 216071394U, 225150024U, 234531275U, 244222650U, 254231775U,
00096 264566400U},
00097 (unsigned long [65]) {
00098 0U, 0U, 0U, 0U, 0U, 0U, 1U, 7U, 28U, 84U, 210U, 462U, 924U, 1716U,
00099 3003U, 5005U, 8008U, 12376U, 18564U, 27132U, 38760U, 54264U,
00100 74613U, 100947U, 134596U, 177100U, 230230U, 296010U, 376740U,
00101 475020U, 593775U, 736281U, 906192U, 1107568U, 1344904U, 1623160U,
00102 1947792U, 2324784U, 2760681U, 3262623U, 3838380U, 4496388U,
00103 5245786U, 6096454U, 7059052U, 8145060U, 9366819U, 10737573U,
00104 12271512U, 13983816U, 15890700U, 18009460U, 20358520U, 22957480U,
00105 25827165U, 28989675U, 32468436U, 36288252U, 40475358U, 45057474U,
00106 50063860U, 55525372U, 61474519U, 67945521U,74974368U},
00107 (unsigned long [65]) {
00108 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 8U, 36U, 120U, 330U, 792U, 1716U,
00109 3432U, 6435U, 11440U, 19448U, 31824U, 50388U, 77520U, 116280U,
00110 170544U, 245157U, 346104U, 480700U, 657800U, 888030U, 1184040U,
00111 1560780U, 2035800U, 2629575U, 3365856U,4272048U, 5379616U,
00112 6724520U, 8347680U, 10295472U, 12620256U, 15380937U, 18643560U,
00113 22481940U, 26978328U, 32224114U, 38320568U, 45379620U, 53524680U,
00114 62891499U, 73629072U, 85900584U, 99884400U, 115775100U,
00115 133784560U, 154143080U, 177100560U, 202927725U, 231917400U,
00116 264385836U, 300674088U, 341149446U, 386206920U,
00117 436270780U,491796152U, 553270671U, 621216192U},
00118 (unsigned long [33]) {
00119 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 9U, 45U, 165U, 495U, 1287U,
00120 3003U, 6435U, 12870U, 24310U, 43758U, 75582U, 125970U, 203490U,
00121 319770U, 490314U, 735471U, 1081575U, 1562275U, 2220075U, 3108105U,
00122 4292145U, 5852925U, 7888725U, 10518300U},
00123 (unsigned long [33]) {
00124 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 10U, 55U, 220U, 715U,
00125 2002U, 5005U, 11440U, 24310U, 48620U, 92378U, 167960U, 293930U,
00126 497420U, 817190U, 1307504U, 2042975U, 3124550U, 4686825U,
00127 6906900U, 10015005U, 14307150U, 20160075U, 28048800U},
00128 (unsigned long [33]) {
00129 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 11U, 66U, 286U, 1001U,
00130 3003U, 8008U, 19448U, 43758U, 92378U, 184756U, 352716U,646646U,
00131 1144066U, 1961256U, 3268760U, 5311735U, 8436285U, 13123110U,
00132 20030010U, 30045015U, 44352165U, 64512240U},
00133 (unsigned long [33]) {
00134 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 12U, 78U, 364U,
00135 1365U, 4368U, 12376U, 31824U, 75582U, 167960U, 352716U, 705432U,
00136 1352078U, 2496144U, 4457400U, 7726160U, 13037895U, 21474180U,
00137 34597290U, 54627300U, 84672315U, 129024480U},
00138 (unsigned long [33]) {
00139 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 13U, 91U,
00140 455U, 1820U, 6188U, 18564U, 50388U, 125970U, 293930U, 646646U,
00141 1352078U, 2704156U, 5200300U, 9657700U, 17383860U, 30421755U,
00142 51895935U, 86493225U, 141120525U, 225792840U},
00143 (unsigned long [33]) {
00144 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 14U, 105U,
00145 560U, 2380U, 8568U, 27132U, 77520U, 203490U, 497420U, 1144066U,
00146 2496144U, 5200300U, 10400600U, 20058300U, 37442160U, 67863915U,
00147 119759850U, 206253075U, 347373600U},
00148 (unsigned long [33]) {
00149 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 15U,
00150 120U, 680U, 3060U, 11628U, 38760U, 116280U, 319770U, 817190U,
00151 1961256U, 4457400U, 9657700U, 20058300U, 40116600U, 77558760U,
00152 145422675U, 265182525U, 471435600U},
00153 (unsigned long [33]) {
00154 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U,
00155 16U, 136U, 816U, 3876U, 15504U, 54264U, 170544U, 490314U,
00156 1307504U, 3268760U, 7726160U, 17383860U, 37442160U, 77558760U,
00157 155117520U, 300540195U, 565722720U},
00158 (unsigned long [33]) {
00159 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U,
00160 1U, 17U, 153U, 969U, 4845U, 20349U, 74613U, 245157U,
00161 735471U,2042975U, 5311735U, 13037895U, 30421755U, 67863915U,
00162 145422675U, 300540195U, 601080390U}};
00163
00164 unsigned long bino(int a, int b) {
00165 return table_bino[b][a];
00166 }
00167
00168 unsigned long cw_coder(int * res, int t) {
00169 unsigned long x = 0;
00170
00171 switch (t) {
00172 case 4:
00173 x = (res[3] * (res[3] - 1) * (res[3] - 2)) / 6;
00174
00175
00176 switch (x & 3) {
00177 case 0:
00178 x >>= 2;
00179 x *= res[3] - 3;
00180 break;
00181 case 1:
00182 case 3:
00183 x *= (res[3] - 3) >> 2;
00184 break;
00185 case 2:
00186 x >>= 1;
00187 x *= (res[3] - 3) >> 1;
00188 break;
00189 }
00190 case 3:
00191 x += ((unsigned long) (((res[2] * (res[2] - 1)) / 2) * (res[2] - 2))) / 3;
00192 case 2:
00193 x += ((unsigned long) (res[1] * (res[1] - 1))) / 2;
00194 case 1:
00195 x += res[0];
00196 break;
00197 default:
00198 x = table_bino[t][res[t - 1]] + cw_coder(res, t - 1);
00199 break;
00200 }
00201
00202 return x;
00203 }
00204
00205
00206
00207 int inv_bino(unsigned long x, int t) {
00208 int debut, fin, milieu;
00209
00210 debut = t - 1;
00211 fin = max_bino[t];
00212 milieu = (fin + debut) / 2;
00213
00214
00215
00216
00217 while (milieu > debut) {
00218 if (x < table_bino[t][milieu])
00219 fin = milieu;
00220 else
00221 debut = milieu;
00222 milieu = (fin + debut) / 2;
00223 }
00224
00225
00226 return debut;
00227 }
00228
00229 void cw_decoder(unsigned long x, int t, int * res) {
00230 if (x == 0) {
00231 while (t > 0) {
00232 t--;
00233 res[t] = t;
00234 }
00235 }
00236 else if (t == 1) {
00237 res[0] = x;
00238 }
00239 else if (t == 2) {
00240 res[1] = round(sqrt(2 * x + 0.25));
00241 res[0] = x - (res[1] * (res[1] - 1)) / 2;
00242 }
00243 else if (t == 3) {
00244 unsigned long b;
00245 res[2] = 1 + cbrtf(6 * ((float) x));
00246 b = (res[2] * (res[2] - 1)) / 2;
00247
00248
00249 x -= (b * (res[2] - 2)) / 3;
00250 if (x >= b) {
00251 res[2]++;
00252 x -= b;
00253 }
00254 cw_decoder(x, 2, res);
00255 }
00256 else if (t == 4) {
00257 unsigned long b;
00258 res[3] = 1 + powf(24 * ((float) x), 0.25);
00259 b = (res[3] * (res[3] - 1) * (res[3] - 2)) / 6;
00260
00261
00262 switch (b & 3) {
00263 case 0:
00264 x -= (b >> 2) * (res[3] - 3);
00265 break;
00266 case 1:
00267 case 3:
00268 x -= b * ((res[3] - 3) >> 2);
00269 break;
00270 case 2:
00271 x -= (b >> 1) * ((res[3] - 3) >> 1);
00272 break;
00273 }
00274 if (x >= b) {
00275 res[3]++;
00276 x -= b;
00277 }
00278 cw_decoder(x, 3, res);
00279 }
00280 else {
00281 res[t - 1] = inv_bino(x, t);
00282 cw_decoder(x - table_bino[t][res[t - 1]], t - 1, res);
00283 }
00284 }
00285
00286 int dicho_rec(int * cw, int i, int s, arith_t state, precomp_t p) {
00287 unsigned long u;
00288 int j, l, r;
00289
00290 if (i == 0)
00291 return 0;
00292
00293 if (i > (1 << s) - i) {
00294 int * cw2 = malloc(((1 << s) - i) * sizeof (int));
00295 r = cw[0] & (((unsigned long) -1) << s);
00296 for (j = 0, l = 0; (l < (1 << s) - i) && (j < i); ++r)
00297 if (cw[j] == r)
00298 ++j;
00299 else {
00300 cw2[l] = r;
00301 ++l;
00302 }
00303 for (; l < (1 << s) - i; ++l, ++r)
00304 cw2[l] = r;
00305 r = dicho_rec(cw2, l, s, state, p);
00306 free(cw2);
00307 return r;
00308 }
00309
00310 if (i == 1) {
00311 liste_todo = liste_alloc(liste_todo);
00312 liste_todo->taille = s;
00313 liste_todo->nombre = 1;
00314 liste_todo->valeur = cw[0] & ((1 << s) - 1);
00315 liste_todo->maximum = 1 << s;
00316 return 0;
00317 }
00318
00319 if (is_leaf(s, i)) {
00320 u = ~((-1) << s);
00321 for (j = 0; j < i; ++j)
00322 aux[j] = cw[j] & u;
00323 liste_todo = liste_alloc(liste_todo);
00324 liste_todo->nombre = i;
00325 liste_todo->valeur = cw_coder(aux, i);
00326 liste_todo->maximum = p.leaf_info[s][i].maximum;
00327 liste_todo->taille = p.leaf_info[s][i].deadbits;
00328 return 0;
00329 }
00330
00331 for (l = 0; l < i; ++l)
00332 if (cw[l] & (1 << (s - 1)))
00333 break;
00334 r = coder(l, precomp_get_distrib(p, s, i), state);
00335
00336 #ifdef DEBUG
00337 printf("%d = %d + %d\n", i, l, i - l);
00338 #endif
00339
00340 r += dicho_rec(cw, l, s - 1, state, p);
00341 r += dicho_rec(cw + l, i - l, s - 1, state, p);
00342
00343 return r;
00344 }
00345
00346
00347 int dicho(int * cw, arith_t state, precomp_t p) {
00348 int m, t, r, i, accel;
00349 liste_t l;
00350
00351 m = p.m;
00352 t = p.t;
00353
00354 aux = (int *) malloc((t + 1) * sizeof (int));
00355 liste_todo = NULL;
00356
00357 r = dicho_rec(cw, t, m, state, p);
00358
00359 #ifdef DEBUG
00360 printf("%d\n", r);
00361 for (l = liste_todo; l != NULL; l = l->suivant)
00362 printf("%d\t%d\t%u\t%u\n", l->nombre, l->taille, l->maximum, l->valeur);
00363 #endif
00364
00365
00366 for (i = 0, l = liste_todo; l != NULL; l = l->suivant)
00367 i += l->taille;
00368
00369
00370
00371
00372
00373
00374
00375
00376 accel = (bwrite_unlocked(state->buffer) >= i);
00377
00378 #ifdef DEBUG
00379 printf(accel ? "accel : oui\n" : "accel : non\n");
00380 printf("%d\t%d\n", bwrite_unlocked(state->buffer), i);
00381 #endif
00382
00383 if (accel)
00384
00385 bwrite_decaler_fin(state->buffer, -i);
00386
00387 for (l = liste_todo; l != NULL; l = l->suivant) {
00388 if (l->nombre > 1) {
00389 r += coder_uniforme(l->valeur >> l->taille, l->maximum, state);
00390 l->valeur &= ((1 << l->taille) - 1);
00391 }
00392 }
00393
00394 #ifdef DEBUG
00395 printf("%d\n", r);
00396 #endif
00397
00398 if (!accel) {
00399 for (l = liste_todo; l != NULL; l = l->suivant) {
00400 while (l->taille > PREC_PROBA) {
00401 l->taille -= PREC_PROBA;
00402 r += coder_uniforme(l->valeur >> l->taille, 1 << PREC_PROBA, state);
00403 l->valeur &= ((1 << l->taille) - 1);
00404 }
00405 r += coder_uniforme(l->valeur, 1 << l->taille, state);
00406 }
00407 }
00408
00409 if (state->min == 0)
00410 bwrite_bit(0, state->buffer);
00411 else {
00412 bwrite_bit(1, state->buffer);
00413 bwrite_bits(0, state->compteur, state->buffer);
00414 }
00415 ++r;
00416
00417 if (accel) {
00418
00419 bwrite_decaler_fin(state->buffer, i);
00420
00421
00422 bwrite_changer_position(state->buffer, state->buffer->fin - i);
00423
00424 for (l = liste_todo; l != NULL; l = l->suivant)
00425 bwrite(l->valeur, l->taille, state->buffer);
00426
00427 r += i;
00428 }
00429
00430 #ifdef DEBUG
00431 printf("%d\n", r);
00432 for (l = liste_todo; l != NULL; l = l->suivant)
00433 printf("%d\t%d\t%u\t%u\n", l->nombre, l->taille, l->maximum, l->valeur);
00434 #endif
00435
00436 free(aux);
00437 liste_free(liste_todo);
00438
00439 return r;
00440 }
00441
00442 int dichoinv_rec(int * cw, int i, int s, int x, arith_t state, precomp_t p) {
00443 int l, r;
00444
00445 if (i == 0)
00446 return 0;
00447
00448 if (i > (1 << s) - i) {
00449 liste_inv = liste_alloc(liste_inv);
00450 liste_inv->nombre = i;
00451 liste_inv->element = cw;
00452 liste_inv->taille = s;
00453 liste_inv->pos = x;
00454 return dichoinv_rec(cw, (1 << s) - i, s, x, state, p);
00455 }
00456
00457 if (i == 1) {
00458 liste_todo = liste_alloc(liste_todo);
00459 liste_todo->element = cw;
00460 liste_todo->nombre = 1;
00461 liste_todo->taille = s;
00462 liste_todo->valeur = 0;
00463 liste_todo->pos = x;
00464 liste_todo->maximum = 1 << s;
00465 return 0;
00466 }
00467
00468 if (is_leaf(s, i)) {
00469 liste_todo = liste_alloc(liste_todo);
00470 liste_todo->element = cw;
00471 liste_todo->nombre = i;
00472 liste_todo->pos = x;
00473 liste_todo->maximum = p.leaf_info[s][i].maximum;
00474 liste_todo->taille = p.leaf_info[s][i].deadbits;
00475 return 0;
00476 }
00477
00478 r = decoder(precomp_get_distrib(p, s, i), &l, state);
00479
00480 #ifdef DEBUG
00481 printf("%d = %d + %d\n", i, l, i - l);
00482 #endif
00483 r += dichoinv_rec(cw, l, s - 1, x, state, p);
00484 r += dichoinv_rec(cw + l, i - l, s - 1, x ^ (1 << (s - 1)), state, p);
00485
00486 return r;
00487 }
00488
00489 int dichoinv(int *cw, arith_t state, precomp_t p) {
00490 int m, t, r, i, accel;
00491 unsigned long x;
00492 liste_t l;
00493 unsigned char c;
00494
00495 m = p.m;
00496 t = p.t;
00497
00498 liste_todo = NULL;
00499 liste_inv = NULL;
00500
00501 r = dichoinv_rec(cw, t, m, 0, state, p);
00502
00503 #ifdef DEBUG
00504 printf("%d\n", r);
00505 for (l = liste_todo; l != NULL; l = l->suivant)
00506 printf("%d\t%d\t%u\t%d\n", l->nombre, l->taille, l->maximum, l->pos);
00507 #endif
00508
00509
00510 for (i = 0, l = liste_todo; l != NULL; l = l->suivant)
00511 i += l->taille;
00512
00513
00514 accel = (bread_unlocked(state->buffer) >= i);
00515
00516 #ifdef DEBUG
00517 printf(accel ? "accel : oui\n" : "accel : non\n");
00518 printf("%d\t%d\n", bread_unlocked(state->buffer), i);
00519 #endif
00520
00521 if (accel)
00522
00523 bread_decaler_fin(state->buffer, -i);
00524
00525 for (l = liste_todo; l != NULL; l = l->suivant)
00526 if (l->nombre > 1) {
00527 r += decoder_uniforme(l->maximum, &x, state);
00528 l->valeur = x << l->taille;
00529 }
00530
00531 #ifdef DEBUG
00532 printf("%d\n", r);
00533 #endif
00534
00535 if (accel) {
00536
00537 bread_decaler_fin(state->buffer, i);
00538
00539
00540 bread_changer_position(state->buffer, state->buffer->fin - i);
00541
00542 for (l = liste_todo; l != NULL; l = l->suivant)
00543 l->valeur ^= bread(l->taille, state->buffer);
00544
00545 r += i;
00546 }
00547 else {
00548 for (l = liste_todo; l != NULL; l = l->suivant) {
00549 while (l->taille > PREC_PROBA) {
00550 r += decoder_uniforme(1 << PREC_PROBA, &x, state);
00551 l->taille -= PREC_PROBA;
00552 l->valeur ^= x << l->taille;
00553 }
00554 r += decoder_uniforme(1 << l->taille, &x, state);
00555 l->valeur ^= x;
00556 }
00557 }
00558
00559
00560
00561
00562
00563
00564
00565
00566 ++r;
00567
00568
00569
00570
00571
00572
00573
00574 for (l = liste_todo; l != NULL; l = l->suivant) {
00575 cw_decoder(l->valeur, l->nombre, l->element);
00576 for (i = 0; i < l->nombre; ++i)
00577 l->element[i] ^= l->pos;
00578 }
00579
00580 #ifdef DEBUG
00581 printf("%d\n", r);
00582 for (l = liste_todo; l != NULL; l = l->suivant)
00583 printf("%d\t%d\t%u\t%u\t%d\n", l->nombre, l->taille, l->maximum, l->valeur, l->pos);
00584 #endif
00585
00586 for (l = liste_inv; l != NULL; l = l->suivant) {
00587 int j, k;
00588 int * cw2;
00589 cw2 = malloc(((1 << l->taille) - l->nombre) * sizeof (int));
00590 memcpy(cw2, l->element, ((1 << l->taille) - l->nombre) * sizeof (int));
00591 i = l->pos;
00592 for (j = 0, k = 0; (k < (1 << l->taille) - l->nombre) && (j < l->nombre); ++i)
00593 if (cw2[k] == i)
00594 ++k;
00595 else {
00596 l->element[j] = i;
00597 ++j;
00598 }
00599 for (; j < l->nombre; ++j, ++i)
00600 l->element[j] = i;
00601 free(cw2);
00602 }
00603
00604 #ifdef DEBUG
00605 for (i = 0; i < t; ++i) printf("%d\t%d\n", i, cw[i]);
00606 #endif
00607
00608 liste_free(liste_todo);
00609 liste_free(liste_inv);
00610
00611 return r;
00612 }
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628 int dicho_b2cw(unsigned char * input_message, int * cw, int start, int len, int m, int t, precomp_t p) {
00629 int i, j, k, l, end, reduc;
00630 arith_t state;
00631 unsigned char c, d;
00632 int * cw2;
00633
00634 if ((t != p.real_t) || (m != p.real_m)) {
00635 printf("inconsistent data for cw, rerun genparams\n");
00636 exit(0);
00637 }
00638
00639 if (start % 8) {
00640 c = input_message[start / 8];
00641 input_message[start / 8] >>= (start % 8);
00642 }
00643 end = start + len;
00644 if (end % 8) {
00645 d = input_message[end / 8];
00646 input_message[end / 8] <<= (8 - (end % 8));
00647 }
00648
00649 state = arith_init(breadinit(input_message, end));
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662 reduc = m - p.m;
00663 bread_changer_position(state->buffer, start + reduc * t);
00664
00665 cw2 = malloc(p.t * sizeof (int));
00666
00667 l = dichoinv(cw2, state, p);
00668
00669 if (p.t == t)
00670 memcpy(cw, cw2, t * sizeof (int));
00671 else {
00672 k = 0;
00673 for (j = 0; j < cw2[0]; ++k, ++j)
00674 cw[k] = j;
00675 for (i = 1; i < p.t; ++i) {
00676 for (j = cw2[i - 1] + 1; j < cw2[i]; ++k, ++j)
00677 cw[k] = j;
00678 }
00679 for (j = cw2[p.t - 1] + 1; j < (1 << p.m); ++k, ++j)
00680 cw[k] = j;
00681 }
00682 free(cw2);
00683
00684 if (reduc > 0) {
00685
00686 bread_changer_position(state->buffer, start);
00687 for (j = 0; j < t; ++j)
00688 cw[j] = (cw[j] << reduc) ^ bread(reduc, state->buffer);
00689 l += reduc * t;
00690 }
00691
00692 breadclose(state->buffer);
00693 free(state);
00694
00695 if (start % 8) {
00696 input_message[start / 8] = c;
00697 }
00698 if (end % 8) {
00699 input_message[end / 8] = d;
00700 }
00701
00702 if (l < len)
00703 return -1;
00704 else
00705 return l;
00706 }
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722 int dicho_cw2b(int * cw, unsigned char * output_message, int start, int len, int m, int t, precomp_t p) {
00723 int i, j, k, l, end, reduc, mask;
00724 arith_t state;
00725 bwrite_t b;
00726 int * cw2;
00727 unsigned char c, d;
00728
00729 if ((t != p.real_t) || (m != p.real_m)) {
00730 printf("inconsistent data for cw, rerun genparams\n");
00731 exit(0);
00732 }
00733
00734 if (start % 8) {
00735 c = output_message[start / 8] & ((1 << (start % 8)) - 1);
00736 output_message[start / 8] = 0;
00737 }
00738 end = start + len;
00739
00740 state = arith_init(bwriteinit(output_message, end));
00741
00742 bwrite_changer_position(state->buffer, start);
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753 reduc = m - p.m;
00754 if (reduc > 0) {
00755
00756 mask = (1 << reduc) - 1;
00757 for (j = 0; j < t; ++j)
00758 bwrite(cw[j] & mask, reduc, state->buffer);
00759 }
00760
00761 cw2 = malloc(p.t * sizeof (int));
00762
00763 if (t == p.t) {
00764 for (j = 0; j < t; ++j)
00765 cw2[j] = cw[j] >> reduc;
00766 }
00767 else {
00768 k = 0;
00769 for (j = 0; j < (cw[0] >> reduc); ++k, ++j)
00770 cw2[k] = j;
00771 for (i = 1; i < t; ++i) {
00772 for (j = (cw[i - 1] >> reduc) + 1; j < (cw[i] >> reduc); ++k, ++j)
00773 cw2[k] = j;
00774 }
00775 for (j = (cw[t - 1] >> reduc) + 1; j < (1 << p.m); ++k, ++j)
00776 cw2[k] = j;
00777 }
00778
00779 l = reduc * t + dicho(cw2, state, p);
00780
00781 free(cw2);
00782
00783 bwriteclose(state->buffer);
00784 free(state);
00785
00786 if (start % 8) {
00787 output_message[start / 8] <<= (start % 8);
00788 output_message[start / 8] ^= c;
00789 }
00790 if (end % 8) {
00791 output_message[end / 8] >>= (8 - (end % 8));
00792 }
00793
00794 if (l < len)
00795 return -1;
00796 else
00797 return l;
00798 }