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