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