IDA_new/ida_gf65_paper3.cpp

   1
   2
   3 #include <iostream>
   4 #include <fstream>
   5 #include <chrono>
   6 #include <sstream>
   7 #include <ctime>
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include <algorithm>    // std::random_shuffle
  12 #include <vector>       // std::vector
  13 #include <unistd.h>
  14 #include <thread>
  15
  16
  17 extern "C" {
  18   #include "jerasure.h"
  19 }
  20
  21 typedef unsigned long mylong;
  22 #define LLUI (long long unsigned int)
  23
  24
  25 using namespace std;
  26
  27 string cloud[5]={"dropboxida1","googleida1","onedriveida2","onedriveida1","pcloudida1"};
  28
  29 void rc4keyperm(uint8_t *key,int len, int rp,int *sc, int size_DK) {
  30
  31   //sc=1:len;
  32
  33
  34
  35   for (int i=0;i<len;i++) {
  36     sc[i]=i;
  37   }
  38   for (int it = 0; it < rp; it++) {
  39     int j0 = 1;
  40     for(int i0 = 0; i0<len; i0++) {
  41       j0 = (j0 + sc[i0] + sc[j0] + key[i0%size_DK] )% len;
  42       int tmp = sc[i0];
  43       sc[i0] = sc[j0];
  44       sc[j0] = tmp;
  45     }
  46
  47   }
  48 }
  49
  50
  51 void display(mylong *mat, int r, int c) {
  52  for(int i=0;i<r;i++) {
  53     for(int j=0;j<c;j++) {
  54       printf("%016llu ",LLUI mat[i*c+j]);
  55     }
  56     printf("\n");
  57   }
  58  printf("\n");
  59 }
  60
  61 mylong *matrix_multiply(gf_t *gf, mylong *m1, mylong *m2, int r1, int c1, int r2, int c2, int w, float *toto)
  62 {
  63   mylong *product;
  64   int i, j, k;
  65
  66   product = (mylong *) malloc(sizeof(mylong)*r1*c2);
  67   for (i = 0; i < r1*c2; i++) product[i] = 0;
  68
  69   for (i = 0; i < r1; i++) {
  70     for (j = 0; j < c2; j++) {
  71       for (k = 0; k < r2; k++) {
  72         product[i*c2+j] ^= gf->multiply.w64(gf,m1[i*c1+k], m2[k*c2+j]);
  73       }
  74     }
  75   }
  76   *toto=*toto+0.021;
  77   return product;
  78 }
  79
  80
  81
  82 int invert_matrix(gf_t *gf, mylong *mat, mylong *inv, int rows)
  83 {
  84   int cols, i, j, k, x, rs2;
  85   int row_start;
  86   mylong tmp, inverse;
  87
  88   cols = rows;
  89
  90   k = 0;
  91   for (i = 0; i < rows; i++) {
  92     for (j = 0; j < cols; j++) {
  93       inv[k] = (i == j) ? 1 : 0;
  94       k++;
  95     }
  96   }
  97 //  display(inv, rows, rows);
  98 //  printf("\n");
  99
 100   /* First -- convert into upper triangular  */
 101   for (i = 0; i < cols; i++) {
 102     row_start = cols*i;
 103
 104     /* Swap rows if we ave a zero i,i element.  If we can't swap, then the
 105        matrix was not invertible  */
 106
 107     if (mat[row_start+i] == 0) {
 108       for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
 109       if (j == rows) return -1;
 110       rs2 = j*cols;
 111       for (k = 0; k < cols; k++) {
 112         tmp = mat[row_start+k];
 113         mat[row_start+k] = mat[rs2+k];
 114         mat[rs2+k] = tmp;
 115         tmp = inv[row_start+k];
 116         inv[row_start+k] = inv[rs2+k];
 117         inv[rs2+k] = tmp;
 118       }
 119     }
 120
 121     /* Multiply the row by 1/element i,i  */
 122     tmp = mat[row_start+i];
 123     if (tmp != 1) {
 124       inverse = gf->divide.w64(gf,1, tmp);
 125       for (j = 0; j < cols; j++) {
 126         mat[row_start+j] = gf->multiply.w64(gf,mat[row_start+j], inverse);
 127         inv[row_start+j] = gf->multiply.w64(gf,inv[row_start+j], inverse);
 128       }
 129     }
 130
 131     /* Now for each j>i, add A_ji*Ai to Aj  */
 132     k = row_start+i;
 133     for (j = i+1; j != cols; j++) {
 134       k += cols;
 135       if (mat[k] != 0) {
 136         if (mat[k] == 1) {
 137           rs2 = cols*j;
 138           for (x = 0; x < cols; x++) {
 139             mat[rs2+x] ^= mat[row_start+x];
 140             inv[rs2+x] ^= inv[row_start+x];
 141           }
 142         } else {
 143           tmp = mat[k];
 144           rs2 = cols*j;
 145           for (x = 0; x < cols; x++) {
 146             mat[rs2+x] ^= gf->multiply.w64(gf,tmp, mat[row_start+x]);
 147             inv[rs2+x] ^= gf->multiply.w64(gf,tmp, inv[row_start+x]);
 148           }
 149         }
 150       }
 151     }
 152   }
 153
 154   /* Now the matrix is upper triangular.  Start at the top and multiply down  */
 155
 156   for (i = rows-1; i >= 0; i--) {
 157     row_start = i*cols;
 158     for (j = 0; j < i; j++) {
 159       rs2 = j*cols;
 160       if (mat[rs2+i] != 0) {
 161         tmp = mat[rs2+i];
 162         mat[rs2+i] = 0;
 163         for (k = 0; k < cols; k++) {
 164           inv[rs2+k] ^= gf->multiply.w64(gf,tmp, inv[row_start+k]);
 165         }
 166       }
 167     }
 168   }
 169
 170 /*  printf("mat\n");
 171   display(mat, rows, rows);
 172   printf("\n");
 173    printf("inv\n");
 174   display(inv, rows, rows);
 175   printf("\n");
 176 */
 177   return 0;
 178 }
 179
 180
 181
 182
 183 int invertible_matrix(gf_t *gf, int *mat, int rows, int w)
 184 {
 185   int cols, i, j, k, x, rs2;
 186   int row_start;
 187   mylong tmp, inverse;
 188
 189   cols = rows;
 190
 191   /* First -- convert into upper triangular  */
 192   for (i = 0; i < cols; i++) {
 193     row_start = cols*i;
 194
 195     /* Swap rows if we ave a zero i,i element.  If we can't swap, then the
 196        matrix was not invertible  */
 197
 198     if (mat[row_start+i] == 0) {
 199       for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
 200       if (j == rows) return 0;
 201       rs2 = j*cols;
 202       for (k = 0; k < cols; k++) {
 203         tmp = mat[row_start+k];
 204         mat[row_start+k] = mat[rs2+k];
 205         mat[rs2+k] = tmp;
 206       }
 207     }
 208
 209     /* Multiply the row by 1/element i,i  */
 210     tmp = mat[row_start+i];
 211     if (tmp != 1) {
 212       inverse =  gf->divide.w64(gf,1, tmp);
 213       for (j = 0; j < cols; j++) {
 214         mat[row_start+j] =  gf->multiply.w64(gf,mat[row_start+j], inverse);
 215       }
 216     }
 217
 218     /* Now for each j>i, add A_ji*Ai to Aj  */
 219     k = row_start+i;
 220     for (j = i+1; j != cols; j++) {
 221       k += cols;
 222       if (mat[k] != 0) {
 223         if (mat[k] == 1) {
 224           rs2 = cols*j;
 225           for (x = 0; x < cols; x++) {
 226             mat[rs2+x] ^= mat[row_start+x];
 227           }
 228         } else {
 229           tmp = mat[k];
 230           rs2 = cols*j;
 231           for (x = 0; x < cols; x++) {
 232             mat[rs2+x] ^=  gf->multiply.w64(gf,tmp,mat[row_start+x]);
 233           }
 234         }
 235       }
 236     }
 237   }
 238   return 1;
 239 }
 240
 241
 242
 243
 244
 245 mylong*  readFullFile(char* filename,int n, int t, mylong& sizeFile, mylong & padded_size) {
 246
 247   ifstream stream(filename, ios::in | ios::binary | ios::ate);
 248 //  ifstream stream("lena_small.png", ios::in | ios::binary | ios::ate);
 249 //  ifstream stream("/home/couturie/Downloads/CARCARIASS.zip", ios::in | ios::binary | ios::ate);
 250
 251   sizeFile=stream.tellg();
 252 //cout << sizeFile << std::endl;
 253   stream.seekg(0, ios::beg);
 254
 255
 256
 257
 258
 259
 260   vector<uint8_t> contents((istreambuf_iterator<char>(stream)), istreambuf_iterator<char>());
 261
 262
 263
 264
 265
 266
 267
 268   //make padding, we need to pad to be divisible by 8*t, we
 269   if((sizeFile+8)%(8*t)!=0) {
 270 //    cout<<(int)(sizeFile/(8*t))<<endl;
 271
 272     int remainder=(8*t)*(1+(int)((sizeFile+8)/(8*t)))-sizeFile-8;
 273     //cout << "remainder " << remainder << endl;
 274     uint8_t vec[remainder];
 275     for(int i=0;i<remainder;i++)
 276       vec[i]=0;
 277     //add remainder elements at the end
 278     contents.insert(contents.end(),vec,vec+remainder);
 279     //add 8 elements at the beginning for the size
 280     contents.insert(contents.begin(),vec,vec+8);
 281   }
 282
 283
 284
 285 //  cout << "res contents " << contents.size() << endl;
 286
 287 //  for(int i=0;i<contents.size();i++)
 288 //    cout << (int)contents[i] << " ";
 289 //  cout << endl;
 290
 291   uint8_t *p_contents=&contents[0];
 292   uint8_t *p_temp=new uint8_t[sizeFile];
 293
 294   memcpy(p_temp,p_contents,sizeof(uint8_t)*sizeFile);
 295
 296
 297   int sizeDK = 64;
 298   uint8_t DK[sizeDK];
 299   srand48(32);
 300
 301   for(int i=0;i<sizeDK;i++) {
 302     DK[i]=lrand48();
 303   }
 304
 305   int *Pbox=new int[sizeFile];
 306   rc4keyperm(DK, sizeFile, 1, Pbox, 64);
 307
 308   for(int i=0;i<sizeFile;i++) {
 309     p_contents[i]=p_temp[Pbox[i]];
 310   }
 311
 312   free(p_temp);
 313
 314
 315 //  mylong *p_contents2=reinterpret_cast<mylong*>(p_contents);
 316
 317   padded_size=contents.size()/8;
 318
 319   mylong *p_contents2=new mylong[padded_size];
 320   memcpy(p_contents2,p_contents,sizeof(mylong)*padded_size);
 321          //mylong *p_contents2=(mylong*)p_contents;
 322
 323   p_contents2[0]=sizeFile;
 324
 325
 326
 327
 328 /*  for(int i=0;i<padded_size;i++)
 329     cout << p_contents2[i] << " ";
 330   cout << endl;
 331 */
 332   /* long res=0;
 333   for(int i=8-1;i>=0;i--) {
 334     res<<=8;
 335     res+=p_contents[i];
 336   }
 337
 338   cout << "convert val " << (long)res << endl;
 339
 340   res=0;
 341   for(int i=16-1;i>=8;i--) {
 342     res<<=8;
 343     res+=p_contents[i];
 344   }
 345
 346   cout << "convert val " << (long)res << endl;
 347   */
 348
 349   return p_contents2;
 350 }
 351
 352 void sendChunk(string name,int cloud_id) {
 353   stringstream ss;
 354   ss <<"rclone copy "<<name<<" "<<cloud[cloud_id]<<":";
 355   string str = ss.str();
 356   cout<<str<<endl;
 357   system(str.c_str());
 358   ss.str("");
 359   ss<<"rm -f "<<name;
 360   str = ss.str();
 361   cout<<str<<endl;
 362   system(str.c_str());
 363 }
 364
 365
 366 void retrieveChunk(string name,int cloud_id) {
 367   stringstream ss;
 368   ss <<"rclone copy "<<cloud[cloud_id]<<":"<<name<<" .";
 369   string str = ss.str();
 370   cout<<str<<endl;
 371   system(str.c_str());
 372 }
 373
 374
 375 void saveFile(uint8_t *data, const char *fileName,long size_file) {
 376 //  cout<<"size file "<<size_file<<endl;
 377   FILE* pFile = fopen (fileName, "wb");
 378   fwrite (data , sizeof(uint8_t), size_file, pFile);
 379
 380   fclose (pFile);
 381 }
 382
 383
 384 void readFile(uint8_t *data, const char *fileName,long size_file) {
 385 //  cout<<"size file "<<size_file<<endl;
 386   FILE* pFile = fopen (fileName, "rb");
 387
 388   fseek(pFile, 0L, SEEK_END);
 389   int sz = ftell(pFile);
 390   rewind(pFile);
 391   if(sz!=size_file) {
 392     cout << "error : size of this chunk is not correct !! " << endl;
 393     exit(0);
 394   }
 395   fread (data , sizeof(uint8_t), size_file, pFile);
 396
 397   fclose (pFile);
 398 }
 399
 400
 401 void saveFile8(mylong *data, const char *fileName,long size_file) {
 402
 403   cout<<"size file 8 "<<size_file<<endl;
 404       display(data,1,1);
 405     FILE* pFile = fopen (fileName, "wb");
 406
 407
 408
 409     fwrite (data , sizeof(mylong), size_file, pFile);
 410     fclose (pFile);
 411
 412
 413
 414 }
 415
 416
 417
 418 int main(int argc, char **argv)
 419 {
 420   unsigned int  w;
 421   int invert;
 422   mylong *matS;
 423   mylong *matG;
 424   mylong *matC;
 425   mylong *inverse;
 426   mylong *identity;
 427
 428
 429   char *filename=new char[1000];
 430
 431 //  int size=5000000;
 432   int t=3;
 433   int n=5;
 434
 435   for(int i=0;i<argc;i++) {
 436     if(strncmp(argv[i],"t",1)==0)
 437       t=atoi(&(argv[i][1]));
 438     if(strncmp(argv[i],"n",1)==0)
 439       n=atoi(&(argv[i][1]));
 440     if(strncmp(argv[i],"f",1)==0)
 441       strcpy(filename,&argv[i][1]);
 442   }
 443
 444
 445   if(t>n) {
 446     cout<<"pb t>n"<<endl;
 447     exit(0);
 448   }
 449
 450
 451
 452
 453   double total_time=0;
 454
 455   w=64;
 456   gf_t gf;
 457   gf_init_easy(&gf, w);
 458
 459   mylong padded_size;
 460   mylong sizeFile;
 461   matS=readFullFile(filename,n,t,sizeFile,padded_size);
 462
 463 //  cout<<padded_size*8<<endl;
 464
 465 /* for(int i=0;i<padded_size;i++)
 466     cout << matS[i] << " ";
 467   cout << endl;
 468 */
 469
 470   int len=padded_size/t;
 471 //  int len=size/t;
 472 //  cout<<" len "<<len<<" "<<padded_size<<endl;
 473
 474   // matS = malloc(sizeof(mylong)*t*len);
 475   matG = malloc(sizeof(mylong)*t*n);
 476
 477
 478
 479
 480   srand48(time(0));
 481   std::srand ( unsigned ( std::time(0) ) );
 482
 483 /*
 484   for(int i=0;i<t;i++) {
 485     for(int j=0;j<len;j++) {
 486       matS[i*len+j]=lrand48()<<32|lrand48();
 487     }
 488   }
 489   */
 490
 491   for(int i=0;i<n;i++) {
 492     for(int j=0;j<t;j++) {
 493       matG[i*t+j]=lrand48()<<32|lrand48();
 494     }
 495   }
 496
 497
 498 /*
 499   printf("Matrix S:\n");
 500 //  display(matS, len, t);
 501   display(matS, t, t);
 502
 503   printf("Matrix G:\n");
 504   display(matG, n, t);
 505 */
 506
 507   int nb_iter=1000;
 508
 509 //  sleep(2);
 510   float toto=0.001;
 511   auto start = std::chrono::system_clock::now();
 512   for(int i=0;i<nb_iter;i++) {
 513     matC=matrix_multiply(&gf, matG, matS, n, t, t, len, w,&toto);
 514   }
 515   auto end = std::chrono::system_clock::now();
 516   std::chrono::duration<double> elapsed_seconds = end-start;
 517   total_time+=elapsed_seconds.count();
 518   cout << "elapsed time: " << elapsed_seconds.count() << " "<<toto<<"       ";
 519
 520 //  display(matC,t,t);
 521
 522 //  thread th[n];
 523   //Save trunks
 524   for(int i=0;i<n;i++) {
 525     stringstream ss;
 526     ss <<"file_"<<i<<".dat";
 527     string str = ss.str();
 528     saveFile((uint8_t*)&matC[i*len], str.c_str(),len*sizeof(mylong));
 529 //    sendChunk( str,i);
 530 //    th[i] = thread(sendChunk,str, i);
 531   }
 532
 533 /*  for(int i=0;i<n;i++) {
 534     th[i].join();
 535   }
 536 */
 537 /*  cout<<"sleep begin"<<endl;
 538   sleep(2);
 539   cout<<"sleep end"<<endl;
 540 */
 541
 542
 543   mylong *matCs = malloc(sizeof(mylong)*t*len);
 544   mylong *matGs = malloc(sizeof(mylong)*t*t);
 545
 546
 547   std::vector<int> myvector;
 548
 549   // set some values:
 550   for (int i=0; i<n; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
 551
 552   // using built-in random generator:
 553   random_shuffle ( myvector.begin(), myvector.end() );
 554
 555
 556
 557 //  std::cout << "random chunk" << std::endl;
 558   int ind=0;
 559
 560
 561
 562   for(int ii=0;ii<t;ii++) {
 563
 564     auto i=myvector[ii];
 565 //    std::cout << myvector[i] << " ";
 566
 567
 568     stringstream ss;
 569     ss <<"file_"<<i<<".dat";
 570     string str = ss.str();
 571
 572 //    retrieveChunk(str,i);
 573 //    th[ii] = thread(retrieveChunk,str, i);
 574   }
 575
 576
 577   ind=0;
 578
 579   for(int ii=0;ii<t;ii++) {
 580
 581     auto i=myvector[ii];
 582     //  std::cout << myvector[i] << " ";
 583
 584
 585     stringstream ss;
 586     ss <<"file_"<<i<<".dat";
 587     string str = ss.str();
 588     //   th[ii].join();
 589     readFile((uint8_t*)&matCs[ind*len], str.c_str(),len*sizeof(mylong));
 590
 591 //    display(&matCs[ind*len],1,1);
 592 //    display(&matC[i*len],1,1);
 593
 594     /*for(int j=0;j<len;j++) {
 595       matCs[ind*len+j]=matC[i*len+j];
 596       }*/
 597
 598
 599
 600     for(int j=0;j<t;j++) {
 601       matGs[ind*t+j]=matG[i*t+j];
 602     }
 603     ind++;
 604   }
 605 //  std::cout << std::endl;
 606
 607
 608 //  printf("Matrix Gs:\n");
 609 //  display(matGs, t, t);
 610
 611 //  printf("Matrix Cs:\n");
 612 //  display(matCs, t, len);
 613
 614   mylong* matGs_copy = malloc(sizeof(mylong)* t*t);
 615
 616   //WARNING invert changes the matrix
 617 //  invert = invertible_matrix(&gf,matGs, t, w);
 618 //  printf("\nInvertible Gs: %s\n", (invert == 1) ? "Yes" : "No");
 619
 620   memcpy(matGs_copy, matGs, sizeof(mylong)*t*t);
 621   mylong *matInvGs = malloc(sizeof(mylong)*t*t);
 622   invert_matrix(&gf, matGs_copy, matInvGs, t);
 623
 624   /*
 625   WARNING   this changes matGs
 626   identity=matrix_multiply(&gf, matInvGs, matGs, t, t, t, t, w);
 627   printf("Identity:\n");
 628   display(identity, t, t);
 629   */
 630
 631
 632   //printf("Matrix Gs:\n");
 633   //display(matGs, t, t);
 634
 635   mylong *matS2 = malloc(sizeof(mylong)*t*len);
 636
 637 //  sleep(2);
 638   start = std::chrono::system_clock::now();
 639    toto=0.001;
 640   for(int i=0;i<nb_iter;i++) {
 641
 642     matS2=matrix_multiply(&gf, matInvGs, matCs, t, t, t, len, w, &toto);
 643
 644   }
 645   end = std::chrono::system_clock::now();
 646   elapsed_seconds = end-start;
 647 //  cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
 648   total_time+=elapsed_seconds.count();
 649   cout/*<<"TOTAL TIME : "*/<<total_time<<" "<<toto;
 650
 651 /*  printf("Matrix S2:\n");
 652 //  display(matS2, len, t);
 653   display(matS2, t, t);
 654 */
 655   int equal=1;
 656   for(int i=0;i<padded_size && equal;i++) {
 657       equal=matS[i]==matS2[i];
 658 //      if(!equal)
 659 //      printf("ARGH\n");
 660   }
 661 //  if(equal)
 662 //    printf("EQUAL !!!\n");
 663
 664
 665   mylong new_size=matS2[0];
 666 //  cout << "size of data " << new_size << endl;
 667
 668
 669   //first elements that contains the size is removed
 670   uint8_t *reconstucted_data=reinterpret_cast<uint8_t*>(&matS2[1]);
 671 //  saveFile(reconstucted_data, "file.dat",new_size);
 672   return 0;
 673 }
 674
 675