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