00001 #include <ecf/ECF.h>
00002 #include "FunctionMinEvalOp.h"
00003
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 #include <math.h>
00007 #include <string.h>
00008
00009 void anf (int *, int);
00010 int anf_ai (int *, int);
00011 int anf_ai_deg (int *, int);
00012 void wt (int *, int);
00013 int wt_nl (int *, int);
00014 int wt_nl_ci (int *, int);
00015 int wt_spektar (int *, int);
00016 int wt_nl_ci_spektar (int *, int);
00017 void autokorelacija (int *, int);
00018 int autokorelacija_rf (int *, int);
00019 int autokorelacija_max (int *, int);
00020 int autokorelacija_rf_pc_max (int *, int );
00021
00022 int karakteristikaPropagacije (int *, int);
00023 int sumaKvadrataIndikator (int *, int);
00024 int AC (int *, int);
00025 int walshSpectrum2 (int *, int);
00026 int algebarskiStupanj (int *, int);
00027 int balans (int *, int);
00028 int nelinearnost (int, int);
00029 int predrasudaNelinearnost (int, int);
00030 int korelacijskiImunitet (int *, int);
00031 int hammingWeight (int);
00032 int choose(int, int);
00033 int preceq(int, int);
00034 int* sort_increasing_deg(int*, int);
00035 typedef struct
00036 {
00037 int _n, _m, **_v;
00038 } MAT;
00039 MAT* initialize_mat(MAT*, int, int);
00040 MAT* deallocate_mat(MAT*);
00041 MAT* swap_columns(MAT*, int, int);
00042 MAT* add_line(MAT*, int, int);
00043 int* get_monomials(int, int, int*, int*);
00044 int* get_support(const int *, int, int*, int*, int);
00045 MAT* get_matrix(const int *, int, MAT*, int*, int, int, int);
00046 int solve_matrix(MAT*, int*, int);
00047 int algebarskiImunitet(int *, int);
00048
00049 void formatiraniPrikaz (int *, int);
00050 void polarniPrikaz (int *, int);
00051
00052 int evaluate_box(int *, int, int, int);
00053 int inner_product(int, int);
00054 float transparency (int *, int);
00055
00056 int walshSpectrum (int *, int);
00057 int autocorrelationSpectrum (int *, int);
00058 int anf_deg (int *, int);
00059
00060
00061 float eval(int tt[], int nVariables, int varijanta, int *stop)
00062 {
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093 float fitness = 0;
00094
00095 int fitness1 = 0, fitness2 = 0, fitness3 = 0;
00096
00097
00098 switch(varijanta) {
00099
00100 case 1:
00101
00102 fitness = balans(tt,nVariables) + wt_nl (tt, nVariables);
00103 break;
00104
00105 case 4:
00106
00107 fitness = balans(tt,nVariables) + (1 - transparency(tt, nVariables));
00108 break;
00109
00110 case 2:
00111
00112 fitness = balans(tt,nVariables) + anf_ai_deg (tt, nVariables) + wt_nl_ci (tt, nVariables);
00113 break;
00114
00115 case 3:
00116
00117 fitness = balans(tt,nVariables) + anf_ai_deg (tt, nVariables) + wt_nl_ci_spektar (tt, nVariables) + autokorelacija_rf_pc_max(tt, nVariables);
00118
00119 break;
00120
00121 case 5:
00122
00123 fitness = wt_nl (tt, nVariables);
00124 break;
00125
00126 case 6:
00127
00128 fitness1 = wt_nl (tt, nVariables);
00129 fitness2 = anf_deg (tt, nVariables);
00130 fitness3 = balans(tt,nVariables);
00131 if (fitness3 == 0 && fitness1 == 55 && fitness2 == 7)
00132 *stop = 1;
00133 fitness = (fitness1 - 55) + (fitness2 - 7) + abs(fitness3);
00134 break;
00135
00136
00137 case 7:
00138
00139 fitness = balans(tt,nVariables) + wt_nl (tt, nVariables);
00140 break;
00141 }
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169 return fitness;
00170 }
00171
00172
00173 int balans (int *tt, int n)
00174 {
00175 int i, rez=0;
00176
00177 for(i=0; i < (1<<n); i++)
00178 {
00179 if (tt[i]==0)
00180 rez=rez+1;
00181 }
00182 if (rez == ((1<<n)/2))
00183 return 1;
00184 else if (rez < ((1<<n)/2))
00185 { if(rez == 0)
00186 rez = 1;
00187
00188
00189 return (((1<<n)-rez)/(1.*rez))*(-50);
00190 }
00191 else if (rez > ((1<<n)/2))
00192 { if(rez == (1 << n))
00193 rez = (1 << n) - 1;
00194
00195
00196 return ((1.*rez)/((1<<n)-rez))*(-50);
00197 }
00198 }
00199
00200 void anf (int *tt, int n)
00201 {
00202 int i, j, k, rezultat = 0;
00203
00204 static int *t=0, *u=0, *rez=0;
00205
00206 if(t == 0) {
00207 rez=(int *) malloc((1<<n)*sizeof(int));
00208 u=(int *) malloc(((1<<n)>>1)*sizeof(int));
00209 t=(int *) malloc(((1<<n)>>1)*sizeof(int));
00210 }
00211
00212 for(i=0; i < (1<<n); ++i)
00213 rez[i] = tt[i];
00214 for( i=0; i < ((1<<n)>> 1); ++i )
00215 u[i]=t[i]=0;
00216
00217 for( i=0; i < n; ++i )
00218 {
00219 for( j=0; j < ( (1<<n)>>1 ); ++j )
00220 {
00221 t[j] = rez[2*j];
00222 u[j] = (rez[2*j]==rez[2*j+1])? 0 : 1;
00223 }
00224 for( k=0; k<((1<<n) >> 1 ); ++k )
00225 {
00226 rez[k] = t[k];
00227 rez[((1<<n) >> 1 ) + k] = u[k];
00228 }
00229 }
00230 printf("ANF je\n");
00231 for (i=0; i < (1<<n); i++)
00232 printf("%d", rez[i]);
00233 printf("\n");
00234
00235 formatiraniPrikaz (rez, n);
00236
00237
00238
00239
00240
00241 }
00242
00243 int anf_ai (int *tt, int n)
00244 {
00245 int i, j, k;
00246
00247 static int *t=0, *u=0, *rez=0;
00248
00249 if(t == 0) {
00250 rez=(int *) malloc((1<<n)*sizeof(int));
00251 u=(int *) malloc(((1<<n)>>1)*sizeof(int));
00252 t=(int *) malloc(((1<<n)>>1)*sizeof(int));
00253 }
00254
00255 for(i=0; i < (1<<n); ++i)
00256 rez[i] = tt[i];
00257 for( i=0; i < ((1<<n)>> 1); ++i )
00258 u[i]=t[i]=0;
00259
00260 for( i=0; i < n; ++i )
00261 {
00262 for( j=0; j < ( (1<<n)>>1 ); ++j )
00263 {
00264 t[j] = rez[2*j];
00265 u[j] = (rez[2*j]==rez[2*j+1])? 0 : 1;
00266 }
00267 for( k=0; k<((1<<n) >> 1 ); ++k )
00268 {
00269 rez[k] = t[k];
00270 rez[((1<<n) >> 1 ) + k] = u[k];
00271 }
00272 }
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282 return algebarskiImunitet(tt, n);
00283
00284 }
00285
00286 int anf_ai_deg (int *tt, int n)
00287 {
00288 int i, j, k, rezultat = 0;
00289
00290 static int *t=0, *u=0, *rez=0;
00291
00292 if(t == 0) {
00293 rez=(int *) malloc((1<<n)*sizeof(int));
00294 u=(int *) malloc(((1<<n)>>1)*sizeof(int));
00295 t=(int *) malloc(((1<<n)>>1)*sizeof(int));
00296 }
00297
00298 for(i=0; i < (1<<n); ++i)
00299 rez[i] = tt[i];
00300 for( i=0; i < ((1<<n)>> 1); ++i )
00301 u[i]=t[i]=0;
00302
00303 for( i=0; i < n; ++i )
00304 {
00305 for( j=0; j < ( (1<<n)>>1 ); ++j )
00306 {
00307 t[j] = rez[2*j];
00308 u[j] = (rez[2*j]==rez[2*j+1])? 0 : 1;
00309 }
00310 for( k=0; k<((1<<n) >> 1 ); ++k )
00311 {
00312 rez[k] = t[k];
00313 rez[((1<<n) >> 1 ) + k] = u[k];
00314 }
00315 }
00316
00317
00318
00319
00320 rezultat = algebarskiStupanj(rez, n) + algebarskiImunitet(tt, n);
00321
00322
00323
00324
00325
00326
00327 return rezultat;
00328
00329 }
00330
00331 int anf_deg (int *tt, int n)
00332 {
00333 int i, j, k, rezultat = 0;
00334
00335 static int *t=0, *u=0, *rez=0;
00336
00337 if(t == 0) {
00338 rez=(int *) malloc((1<<n)*sizeof(int));
00339 u=(int *) malloc(((1<<n)>>1)*sizeof(int));
00340 t=(int *) malloc(((1<<n)>>1)*sizeof(int));
00341 }
00342
00343 for(i=0; i < (1<<n); ++i)
00344 rez[i] = tt[i];
00345 for( i=0; i < ((1<<n)>> 1); ++i )
00346 u[i]=t[i]=0;
00347
00348 for( i=0; i < n; ++i )
00349 {
00350 for( j=0; j < ( (1<<n)>>1 ); ++j )
00351 {
00352 t[j] = rez[2*j];
00353 u[j] = (rez[2*j]==rez[2*j+1])? 0 : 1;
00354 }
00355 for( k=0; k<((1<<n) >> 1 ); ++k )
00356 {
00357 rez[k] = t[k];
00358 rez[((1<<n) >> 1 ) + k] = u[k];
00359 }
00360 }
00361
00362
00363
00364
00365 rezultat = algebarskiStupanj(rez, n);
00366
00367
00368
00369
00370
00371
00372 return rezultat;
00373
00374 }
00375
00376 void wt (int *tt, int n)
00377 {
00378 int i, j, m, halfm, t1, t2, r, a, b, max = 0;
00379
00380 int *rez=0;
00381
00382 rez=(int *) malloc((1<<n)*sizeof(int));
00383
00384
00385
00386 for( i=0; i < (1<<n); ++i )
00387 rez[i] = (tt[i]==0)? 1 : -1;
00388
00389 for( i = 1; i <= n; ++i ) {
00390 m = (1 << i);
00391 halfm = m/2;
00392 for( r=0; r < (1<<n); r += m ) {
00393 t1 = r;
00394 t2 = r + halfm;
00395 for( j=0; j < halfm; ++j, ++t1, ++t2 ) {
00396 a = rez[t1];
00397 b = rez[t2];
00398 rez[t1] = a + b;
00399 rez[t2] = a - b;
00400
00401 if (abs(rez[t1]) > max)
00402 max = abs(rez[t1]);
00403 if (abs(rez[t2]) > max)
00404 max = abs(rez[t2]);
00405 }
00406 }
00407 }
00408 printf("Walsh transformacija je\n");
00409 for (i=0; i < (1<<n); i++)
00410 printf("%d", rez[i]);
00411 printf("\n");
00412
00413
00414
00415
00416
00417
00418 free(rez);
00419
00420 }
00421
00422 int wt_nl (int *tt, int n)
00423 {
00424 int i, j, m, halfm, t1, t2, r, a, b, max = 0, rezultat = 0;
00425
00426 int *rez=0;
00427 int *ac=0;
00428
00429 rez=(int *) malloc((1<<n)*sizeof(int));
00430
00431 for( i=0; i < (1<<n); ++i )
00432 rez[i] = (tt[i]==0)? 1 : -1;
00433
00434 for( i = 1; i <= n; ++i ) {
00435 m = (1 << i);
00436 halfm = m/2;
00437 for( r=0; r < (1<<n); r += m ) {
00438 t1 = r;
00439 t2 = r + halfm;
00440 for( j=0; j < halfm; ++j, ++t1, ++t2 ) {
00441 a = rez[t1];
00442 b = rez[t2];
00443 rez[t1] = a + b;
00444 rez[t2] = a - b;
00445
00446 if (abs(rez[t1]) > max)
00447 max = abs(rez[t1]);
00448 if (abs(rez[t2]) > max)
00449 max = abs(rez[t2]);
00450 }
00451 }
00452 }
00453
00454
00455
00456
00457 free(rez);
00458
00459 return nelinearnost (max, n);
00460 }
00461
00462 int wt_nl_ci (int *tt, int n)
00463 {
00464 int i, j, m, halfm, t1, t2, r, a, b, max = 0, rezultat = 0;
00465
00466 int *rez=0;
00467
00468 rez=(int *) malloc((1<<n)*sizeof(int));
00469
00470 for( i=0; i < (1<<n); ++i )
00471 rez[i] = (tt[i]==0)? 1 : -1;
00472
00473 for( i = 1; i <= n; ++i ) {
00474 m = (1 << i);
00475 halfm = m/2;
00476 for( r=0; r < (1<<n); r += m ) {
00477 t1 = r;
00478 t2 = r + halfm;
00479 for( j=0; j < halfm; ++j, ++t1, ++t2 ) {
00480 a = rez[t1];
00481 b = rez[t2];
00482 rez[t1] = a + b;
00483 rez[t2] = a - b;
00484
00485 if (abs(rez[t1]) > max)
00486 max = abs(rez[t1]);
00487 if (abs(rez[t2]) > max)
00488 max = abs(rez[t2]);
00489 }
00490 }
00491 }
00492
00493
00494
00495
00496 rezultat = nelinearnost (max, n) + korelacijskiImunitet (rez, n);
00497
00498 free(rez);
00499
00500 return rezultat;
00501 }
00502
00503 int wt_spektar (int *tt, int n)
00504 {
00505 int i, j, m, halfm, t1, t2, r, a, b, max = 0, rezultat = 0;
00506
00507 int *rez=0;
00508
00509 int walshSpektar = 0;
00510
00511 rez=(int *) malloc((1<<n)*sizeof(int));
00512
00513 for( i=0; i < (1<<n); ++i )
00514 rez[i] = (tt[i]==0)? 1 : -1;
00515
00516 for( i = 1; i <= n; ++i ) {
00517 m = (1 << i);
00518 halfm = m/2;
00519 for( r=0; r < (1<<n); r += m ) {
00520 t1 = r;
00521 t2 = r + halfm;
00522 for( j=0; j < halfm; ++j, ++t1, ++t2 ) {
00523 a = rez[t1];
00524 b = rez[t2];
00525 rez[t1] = a + b;
00526 rez[t2] = a - b;
00527
00528 if (abs(rez[t1]) > max)
00529 max = abs(rez[t1]);
00530 if (abs(rez[t2]) > max)
00531 max = abs(rez[t2]);
00532 }
00533 }
00534 }
00535
00536 walshSpektar = walshSpectrum2 (rez, n);
00537
00538 free(rez);
00539
00540 return walshSpektar;
00541 }
00542
00543 int wt_nl_ci_spektar (int *tt, int n)
00544 {
00545 int i, j, m, halfm, t1, t2, r, a, b, max = 0, rezultat = 0;
00546
00547 int *rez=0;
00548 int *ac=0;
00549
00550 float walshSpektar = 0;
00551
00552 rez=(int *) malloc((1<<n)*sizeof(int));
00553
00554 ac=(int *) malloc((1<<n)*sizeof(int));
00555
00556 for( i=0; i < (1<<n); ++i )
00557 rez[i] = (tt[i]==0)? 1 : -1;
00558
00559 for( i = 1; i <= n; ++i ) {
00560 m = (1 << i);
00561 halfm = m/2;
00562 for( r=0; r < (1<<n); r += m ) {
00563 t1 = r;
00564 t2 = r + halfm;
00565 for( j=0; j < halfm; ++j, ++t1, ++t2 ) {
00566 a = rez[t1];
00567 b = rez[t2];
00568 rez[t1] = a + b;
00569 rez[t2] = a - b;
00570
00571 if (abs(rez[t1]) > max)
00572 max = abs(rez[t1]);
00573 if (abs(rez[t2]) > max)
00574 max = abs(rez[t2]);
00575 }
00576 }
00577 }
00578
00579
00580
00581
00582 rezultat = nelinearnost (max, n) + korelacijskiImunitet (rez, n) + walshSpectrum2 (rez, n);
00583
00584 free(rez);
00585 free(ac);
00586
00587 return rezultat;
00588 }
00589
00590 int algebarskiStupanj (int * anf, int n)
00591 {
00592
00593 int i, tmp, weight, deg;
00594
00595 if(anf[ (1<<n)-1 ] != 0)
00596 deg = n;
00597 else
00598 for(deg=0, i=1; i < ((1<<n)-1); ++i)
00599 if( anf[i]!=0 ) {
00600 for(weight=0, tmp = i; tmp>0; tmp>>=1)
00601 weight = weight + tmp%2;
00602 if(weight > deg)
00603 deg = weight;
00604 }
00605
00606 return deg;
00607 }
00608
00609 int nelinearnost (int max, int n)
00610 {
00611 return (((1<<n) - max)/2);
00612 }
00613
00614 int predrasudaNelinearnost (int max, int n)
00615 {
00616 return max/(1<<(n+1));
00617 }
00618
00619 int korelacijskiImunitet (int *wh, int n)
00620 {
00621 int i, red = 1;
00622 do
00623 {
00624 for (i = 1; i < (1<<n); i++)
00625 {
00626 if (red == hammingWeight(i))
00627 {
00628 if (wh[i] != 0)
00629 return red-1;
00630 }
00631 }
00632 red++;
00633 } while (red <= n);
00634 return red-2;
00635 }
00636
00637 int hammingWeight(int x)
00638 {
00639 int res;
00640 for( res=0; x>0; x = x>>1 )
00641 res = res + x%2;
00642 return res;
00643 }
00644
00645 void autokorelacija (int *tt, int n)
00646 {
00647 int i, j, tmp = 0, res = 0;
00648
00649 int *ac = 0;
00650
00651 float autokorelacijskiSpektar = 0;
00652
00653 ac =(int *) malloc((1<<n)*sizeof(int));
00654
00655 for (i=0; i < (1<<n); i++)
00656 {
00657 for(j=0; j < (1<<n); j++)
00658 {
00659 tmp = tt[j]^tt[i^j];
00660 if (tmp == 1)
00661 tmp= -1;
00662 else if ( tmp == 0)
00663 tmp = 1;
00664 res= res + tmp;
00665 }
00666 ac[i] = res;
00667 res = 0;
00668 }
00669 printf("Autokorelacija je\n");
00670 for (i=0; i < (1<<n); i++)
00671 printf("%d", ac[i]);
00672 printf("\n");
00673
00674
00675 free(ac);
00676
00677 }
00678
00679 int autokorelacija_rf (int *tt, int n)
00680 {
00681 int i, j, tmp = 0, res = 0, sumaKvadrata = 0;
00682
00683 int *ac = 0;
00684
00685
00686 ac =(int *) malloc((1<<n)*sizeof(int));
00687
00688 for (i=0; i < (1<<n); i++)
00689 {
00690 for(j=0; j < (1<<n); j++)
00691 {
00692 tmp = tt[j]^tt[i^j];
00693 if (tmp == 1)
00694 tmp= -1;
00695 else if ( tmp == 0)
00696 tmp = 1;
00697 res= res + tmp;
00698 }
00699 ac[i] = res;
00700 res = 0;
00701 }
00702
00703 sumaKvadrata = sumaKvadrataIndikator(ac, n);
00704
00705
00706 free(ac);
00707
00708 return sumaKvadrata;
00709 }
00710
00711 int autokorelacija_max (int *tt, int n)
00712 {
00713 int i, j, tmp = 0, res = 0, autokor = 0;
00714
00715 int *ac = 0;
00716
00717 ac =(int *) malloc((1<<n)*sizeof(int));
00718
00719 for (i=0; i < (1<<n); i++)
00720 {
00721 for(j=0; j < (1<<n); j++)
00722 {
00723 tmp = tt[j]^tt[i^j];
00724 if (tmp == 1)
00725 tmp= -1;
00726 else if ( tmp == 0)
00727 tmp = 1;
00728 res= res + tmp;
00729 }
00730 ac[i] = res;
00731 res = 0;
00732 }
00733
00734
00735 autokor = AC (ac, n);
00736
00737 free(ac);
00738
00739 return autokor;
00740 }
00741
00742 int autokorelacija_rf_pc_max (int *tt, int n)
00743 {
00744 int i, j, tmp = 0, res = 0, PC = 0, autokor = 0, sumaKvadrata = 0;
00745
00746 int *ac = 0;
00747
00748 ac =(int *) malloc((1<<n)*sizeof(int));
00749
00750 for (i=0; i < (1<<n); i++)
00751 {
00752 for(j=0; j < (1<<n); j++)
00753 {
00754 tmp = tt[j]^tt[i^j];
00755 if (tmp == 1)
00756 tmp= -1;
00757 else if ( tmp == 0)
00758 tmp = 1;
00759 res= res + tmp;
00760 }
00761 ac[i] = res;
00762 res = 0;
00763 }
00764
00765 PC = karakteristikaPropagacije(ac, n);
00766
00767
00768
00769
00770
00771
00772 autokor = AC (ac, n);
00773
00774
00775
00776 sumaKvadrata = sumaKvadrataIndikator(ac, n);
00777
00778
00779
00780
00781 free(ac);
00782
00783 return PC+autokor+sumaKvadrata;
00784 }
00785
00786 int karakteristikaPropagacije (int *ac, int n)
00787 {
00788 int i, red = 1;
00789 do
00790 {
00791 for (i = 1; i < (1<<n); i++)
00792 {
00793 if (red == hammingWeight(i))
00794 {
00795 if (ac[i] != 0)
00796 return red-1;
00797 }
00798 }
00799 red++;
00800 } while (red <= n);
00801 return red-2;
00802 }
00803
00804 int AC (int *ac, int n)
00805 {
00806 int i, max = 0;
00807 int tmp = 0;
00808 tmp =n/2;
00809 for (i=1; i < (1<<n); i++)
00810 {
00811 if (abs(ac[i]) > max)
00812 max = abs(ac[i]);
00813 }
00814 return max/(-tmp);
00815 }
00816
00817 int sumaKvadrataIndikator (int *ac, int n)
00818 {
00819 int i, suma = 0;
00820 for (i=0; i < (1<<n); i++)
00821 {
00822 suma = suma + (ac[i]*ac[i]);
00823 }
00824 suma = (sqrt((long double)suma/n))/2;
00825 return suma*(-1);
00826 }
00827
00828 int walshSpectrum2(int *walsh, int n)
00829 {
00830 int i;
00831 double rez = 0;
00832 float pot = 0.0, x = 0;
00833 pot = (float)n/2;
00834 x = pow((float)2.0,pot);
00835 for (i=0; i < (1<<n);i++)
00836 {
00837 pot = fabs((float)walsh[i])-x;
00838 rez = rez + pow(pot,2);
00839 }
00840 rez = sqrt((long double)rez);
00841 return rez/(-2);
00842 }
00843
00844 void polarniPrikaz (int *tt, int n)
00845 {
00846 int i, *rez=0;
00847 rez=(int *) malloc((1<<n)*sizeof(int));
00848
00849 for (i=0; i < (1<<n); i++)
00850 {
00851 rez[i] = (tt[i]==0)? 1 : -1;
00852 }
00853 printf("Polarni prikaz je\n");
00854 for (i=0; i < (1<<n); i++)
00855 printf("%d", rez[i]);
00856 printf("\n");
00857 }
00858
00859 void formatiraniPrikaz (int *anf, int n)
00860 {
00861 int i, tmp = 0, j, a = 0;
00862 char prikaz[1000]="";
00863 char *xor = " ^ ";
00864 char *jedan = "1 ^ ";
00865 char *x = "X";
00866 char broj[5];
00867
00868 if (anf [0] == 1)
00869 {
00870 strcat(prikaz, jedan);
00871 }
00872
00873 for (i=1; i < (1<<n);i++)
00874 {
00875 if (anf[i]==1)
00876 {
00877 tmp=i;
00878 for (j=1; tmp > 0; tmp=tmp>>1,j++)
00879 {
00880 if (tmp%2==1)
00881 {
00882 strcat (prikaz, x);
00883 sprintf(broj, "%d", j);
00884 strcat(prikaz,broj);
00885 }
00886 }
00887 strcat(prikaz, xor);
00888 }
00889
00890 }
00891 puts (prikaz);
00892 }
00893
00894
00895
00896
00897
00898
00899 int choose(int n, int k)
00900 {
00901 int i, num = 1, den = 1;
00902 if( k<0 || k>n ) return 0;
00903 for( i=0; i<k; ++i ) {
00904 num *= n--;
00905 den *= (k-i); }
00906 return (num/den);
00907 }
00908
00909 int preceq( int a, int b )
00910 {
00911 int res = 1;
00912 while( (a>0 || b>0) && (res==1) ) {
00913 if( a%2 > b%2 ) res = 0;
00914 a >>= 1; b >>= 1; }
00915 return res;
00916 }
00917
00918 int* sort_increasing_deg( int* v, int len )
00919 {
00920 int i,j,tmp;
00921 for( i=0; i < len-1; ++i )
00922 for( j=i+1; j<len; ++j )
00923 if(hammingWeight(v[j]) < hammingWeight(v[i]) ) {
00924 tmp = v[j];
00925 v[j] = v[i];
00926 v[i] = tmp;
00927 }
00928 return v;
00929 }
00930
00931 MAT* initialize_mat( MAT* mat, int nrow, int ncol)
00932 {
00933 int i,j;
00934 mat = (MAT*) malloc (sizeof(MAT));
00935 mat->_n = nrow;
00936 mat->_m = ncol;
00937 mat->_v = (int**) malloc (nrow * sizeof(int*));
00938 for(i=0; i < nrow; ++i) {
00939 mat->_v[i] = (int*) malloc (ncol * sizeof(int));
00940 for(j=0; j < ncol; ++j)
00941 mat->_v[i][j] = 0;
00942 }
00943 return mat;
00944 }
00945
00946 MAT* deallocate_mat( MAT* mat)
00947 {
00948 int i;
00949 if( mat != NULL ) {
00950 if(mat->_v != NULL) {
00951 for( i=0; i < mat->_n; ++i )
00952 free(mat->_v[i]);
00953 free(mat->_v);
00954 }
00955 free(mat);
00956 }
00957 return NULL;
00958 }
00959
00960 MAT* swap_columns( MAT* mat, int a, int b )
00961 {
00962 int* tmp,i;
00963 tmp = (int*) malloc ( mat->_n * sizeof(int) );
00964 for( i=0; i<mat->_n; ++i ) tmp[i] = mat->_v[i][a];
00965 for( i=0; i<mat->_n; ++i ) mat->_v[i][a] = mat->_v[i][b];
00966 for( i=0; i<mat->_n; ++i ) mat->_v[i][b] = tmp[i];
00967 free(tmp);
00968 return mat;
00969 }
00970
00971 MAT* add_line( MAT* mat, int dst, int src )
00972 {
00973 int j;
00974 for( j=0; j < mat->_m; ++j )
00975 mat->_v[dst][j] = (mat->_v[dst][j] + mat->_v[src][j] )%2;
00976 return mat;
00977 }
00978
00979 int* get_monomials( int n, int d, int* res, int* N )
00980 {
00981 int i,k;
00982 for( (*N)=0, k=0; k<=d; ++k )
00983 (*N) = (*N) + choose(n,k);
00984 res = (int*) malloc ((*N) * sizeof(int));
00985 for( k=0, i=0; i<(1<<n); ++i )
00986 if( hammingWeight(i) <= d )
00987 res[k++] = i;
00988 return res;
00989 }
00990
00991 int* get_support( const int * tt, int n, int* res, int* N, int b )
00992 {
00993 int i,k,len;
00994 len = 1<<n;
00995 for( (*N)=0, i=0; i<len; ++i )
00996 (*N) = (*N) + (tt[i] != b);
00997 res = (int*) malloc ((*N) * sizeof(int));
00998 for( k=0, i=0; i<len; ++i )
00999 if( tt[i] != b )
01000 res[k++] = i;
01001 return res;
01002 }
01003
01004 MAT* get_matrix( const int * tt, int n, MAT* m, int* monomials, int Nm, int ai, int b )
01005 {
01006 int Ns, i, j, len, *support;
01007 len = 1<<n;
01008 support = NULL;
01009 support = get_support( tt, n, support, &Ns, b );
01010 if (Ns == 0 || Ns == len)
01011 m = NULL;
01012 else {
01013 m = (Nm>Ns)? initialize_mat(m,Nm,Nm): initialize_mat(m,Nm,Ns);
01014 for( i=0; i<Nm; ++i )
01015 for( j=0; j<Ns; ++j )
01016 m->_v[i][j] = preceq( monomials[i], support[j] );
01017 }
01018 free(support);
01019 return m;
01020 }
01021
01022 int solve_matrix( MAT* m, int* monomials, int b )
01023 {
01024 int i, j, l, res, *deg, processed_lines, zero_lines;
01025 deg = (int*) malloc (m->_n * sizeof(int));
01026 for( res = 0, i = 0; i < m->_n; ++i ) {
01027 deg[i] = hammingWeight(monomials[i]);
01028 if( deg[i] > res ) res = deg[i];
01029 }
01030 processed_lines = zero_lines = 0;
01031 for( i = 0; i < m->_n; ++i ) {
01032 for( j = 0; j < m->_m && m->_v[i][j] == 0; ++j );
01033 if( j == m->_m ) {
01034 ++ zero_lines;
01035 if( deg[i] < res && deg[i]!=0 )
01036 res = deg[i];
01037 } else {
01038 ++ processed_lines;
01039 if( i!=j && i<m->_m && j<m->_m )
01040 m = swap_columns( m, i, j );
01041 for( l=i+1; l < m->_n && i < m->_m; ++l ) {
01042 if( i < m->_m && m->_v[l][i] != 0 ) {
01043 m = add_line( m, l, i );
01044 deg[l] = (deg[i] > deg[l])? deg[i] : deg[l];
01045 }
01046 }
01047 }
01048 }
01049 free (deg);
01050 return res;
01051 }
01052
01053 int algebarskiImunitet(int *tt, int n)
01054 {
01055 MAT *m0 = NULL, *m1 = NULL;
01056 int deg, *monomials = NULL, Nm;
01057 int a, b, rez=0;
01058
01059 deg = (n >> 1) + (n % 2);
01060 monomials = get_monomials(n, deg, monomials, &Nm);
01061 monomials = sort_increasing_deg(monomials, Nm);
01062 m0 = get_matrix(tt, n, m0, monomials, Nm, deg, 0);
01063 if(m0 == NULL)
01064 rez = 0;
01065 else {
01066 m1 = get_matrix(tt, n, m1, monomials, Nm, deg, 1);
01067 a = solve_matrix(m0, monomials, 0);
01068 b = solve_matrix(m1, monomials, 1);
01069 rez = (a<b)? a : b;
01070 }
01071
01072 free(monomials);
01073 deallocate_mat(m0);
01074 deallocate_mat(m1);
01075
01076 return rez;
01077 }
01078
01079
01080 int autocorrelationSpectrum (int *ac, int n)
01081 {
01082 int i, rez = 0, x, r;
01083 x = -2;
01084 r = 4;
01085 for (i=1; i < (1<<n);i++)
01086 {
01087 rez = rez + pow((long double)abs((abs(ac[i])-x)),r);
01088 }
01089
01090 return rez;
01091 }
01092
01093 int walshSpectrum(int *walsh, int n)
01094 {
01095 int i, rez = 0, x, r;
01096 x = 8;
01097 r = 4;
01098 for (i=0; i < (1<<n);i++)
01099 {
01100 rez = rez + pow((long double)abs((abs(walsh[i])-x)),r);
01101 }
01102
01103 return rez;
01104 }
01105
01106 float transparency (int *tt, int nVariables)
01107 {
01108 int N = nVariables;
01109 int M = 1;
01110 float res = 0.0;
01111 float C = (float) ((1 << (2*N)) - (1 << N));
01112 int b, a, v, x, tmp1, tmp2;
01113 float sigma1, sigma2, sigma3 = 0;
01114 int tmp = 0;
01115
01116 tmp1 = (1 << M);
01117 tmp2 = (1 << N);
01118
01119 for (b = 0; b < tmp1; b++)
01120 {
01121 sigma1 = 0;
01122 for (a = 1; a < tmp2; a++)
01123 {
01124 sigma2 = 0;
01125 for (v = 1; v < tmp1; v = v << 1)
01126 {
01127 sigma3 = 0;
01128 for (x = 0; x < tmp2; x++)
01129 {
01130 sigma3 = sigma3 + (float) (1 - 2*inner_product(v, (evaluate_box(tt, x, a, nVariables))));
01131 }
01132 sigma2 = sigma2 + (float) (1 - 2*inner_product(v, b)) * sigma3;
01133 }
01134
01135 if (sigma2 < 0)
01136 sigma2 = sigma2 *(-1);
01137
01138 sigma1 = sigma2 + sigma1;
01139 }
01140 tmp = 2 * hammingWeight(b);
01141 if (res < abs(M - tmp)-sigma1/C)
01142 res = abs(M - tmp)-sigma1/C;
01143 }
01144 return res;
01145 }
01146
01147 int inner_product(int a, int b)
01148 {
01149 int M = 1;
01150 int i, res = 0;
01151 for (i = 0; i < M; i++)
01152 {
01153 res = res ^ (((a >> i) & 0x01) & ((b >> i ) & 0x01));
01154 }
01155 return res;
01156 }
01157
01158 int evaluate_box(int *tt, int x, int a, int nVariables)
01159 {
01160 int N = nVariables;
01161 int M = 1;
01162 int i, res1 = 0, res2 = 0, tmp, help;
01163
01164 tmp = 1 << M;
01165
01166 for (i = 0; i < M; i++)
01167 {
01168 help = *(tt + tmp*i + x);
01169 res1 |= ((*(tt + tmp*i + x)) << i);
01170 }
01171
01172 x = x^a;
01173 for (i = 0; i < M; i++)
01174 res2 |= ((*(tt + tmp*i + x)) << i);
01175
01176 return res1 ^ res2;
01177 }
01178
01179
01180 uint getResult(uint firstOperator, uint secendOperator, std::string functionName)
01181 {
01182
01183 int functionIndex;
01184 if( strcmp(functionName.c_str(), "NOT") == 0) functionIndex = 0;
01185 else if( strcmp(functionName.c_str(), "AND") == 0) functionIndex = 1;
01186 else if( strcmp(functionName.c_str(), "OR") == 0) functionIndex = 2;
01187 else if( strcmp(functionName.c_str(), "XOR") == 0) functionIndex = 3;
01188 else if( strcmp(functionName.c_str(), "XNOR") == 0) functionIndex = 4;
01189 else functionIndex = 0;
01190
01191
01192 uint output;
01193 switch (functionIndex)
01194 {
01195 case 0:
01196 output = !firstOperator;
01197 break;
01198 case 1:
01199 output = firstOperator & secendOperator;
01200 break;
01201 case 2:
01202 output = firstOperator | secendOperator;
01203 break;
01204 case 3:
01205 output = firstOperator ^ secendOperator;
01206 break;
01207 case 4:
01208 output = !(firstOperator ^ secendOperator);
01209 break;
01210 default:
01211 output = 0;
01212 break;
01213 }
01214 return output;
01215 }
01216
01217 void FunctionMinEvalOp::registerParameters(StateP state)
01218 {
01219 state->getRegistry()->registerEntry("function", (voidP) (new uint(1)), ECF::UINT);
01220 }
01221 bool FunctionMinEvalOp::initialize(StateP state)
01222 {
01223 voidP sptr = state->getRegistry()->getEntry("function");
01224 iFunction_ = *((uint*) sptr.get());
01225
01226 return true;
01227 }
01228
01229
01230 FitnessP FunctionMinEvalOp::evaluate(IndividualP individual)
01231 {
01232
01233 FitnessP fitness (new FitnessMax);
01234
01235 cart::Cartesian* gen = (cart::Cartesian*) individual->getGenotype().get();
01236
01237 double value = 0;
01238
01239 int Nrows = gen->getNumOfRows();
01240 int Ncolumns = gen->getNumOfCols();
01241 int Ninputs = gen->getNumOfInputs();
01242 int Noutputs = gen->getNumOfOutputs();
01243
01244
01245
01246
01247
01248
01249 int* rez = (int*)malloc(sizeof(int)*(Noutputs * pow(2,Ninputs)));
01250 uint* inputs = (uint*)malloc(sizeof(uint)*(Ninputs + (Nrows*Ncolumns)));
01251
01252
01253
01254 for(int i7 = 0; i7 < 2; i7++)
01255 {
01256 for(int i6 = 0; i6 < 2; i6++)
01257 {
01258 for(int i5 = 0; i5 < 2; i5++)
01259 {
01260 for(int i4 = 0; i4 < 2; i4++)
01261 {
01262 for(int i3 = 0; i3 < 2; i3++)
01263 {
01264 for(int i2 = 0; i2 < 2; i2++)
01265 {
01266 for(int i1 = 0; i1 < 2; i1++)
01267 {
01268 for(int i0 = 0; i0 < 2; i0++)
01269 {
01270
01271
01272 inputs[0] = i0;
01273 inputs[1] = i1;
01274 inputs[2] = i2;
01275 inputs[3] = i3;
01276 inputs[4] = i4;
01277 inputs[5] = i5;
01278 inputs[6] = i6;
01279 inputs[7] = i7;
01280
01281
01282
01283 for(int curentNode = 0; curentNode < (Nrows * Ncolumns); curentNode++)
01284 {
01285 inputs[curentNode + Ninputs] = getResult( inputs[gen->at(3 * curentNode)], inputs[gen->at((3 * curentNode) + 1)], gen->funcSet->at(gen->at((3 * curentNode) + 2))->getName());
01286 }
01287
01288
01289
01290
01291 int inputOffset = 8 * (128*i7 + 64*i6 + 32*i5 + 16*i4 + 8*i3 + 4*i2 + 2*i1 + i0);
01292 for(int j = 0; j < Noutputs; j++)
01293 {
01294 rez[inputOffset + j] = inputs[gen->at(3*Nrows*Ncolumns +j)];
01295 }
01296 }
01297 }
01298 }
01299 }
01300 }
01301 }
01302 }
01303 }
01304
01305 value = eval(rez,Noutputs,iFunction_,NULL);
01306
01307 free(rez);
01308 free(inputs);
01309
01310 fitness->setValue(value);
01311 return fitness;
01312 }
01313