From bb1f791ce80683443b326e62ae32c255bcff1010 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Rapha=C3=ABl=20Couturier?= <raphael.couturier@univ-fcomte.fr>
Date: Mon, 24 Feb 2020 21:56:52 +0100
Subject: [PATCH] new
---
IDA_new/Makefile | 6 +-
IDA_new/ida_gf65_paper3.cpp | 665 ++++++++++++++++++++++++++++++++++++
IDA_new/run_long_paper3.py | 20 ++
3 files changed, 690 insertions(+), 1 deletion(-)
create mode 100644 IDA_new/ida_gf65_paper3.cpp
create mode 100644 IDA_new/run_long_paper3.py
diff --git a/IDA_new/Makefile b/IDA_new/Makefile
index 6f4f0b4..3171783 100644
--- a/IDA_new/Makefile
+++ b/IDA_new/Makefile
@@ -46,5 +46,9 @@ ida_gf65_paper1: ida_gf65_paper1.cpp
ida_gf65_paper2: ida_gf65_paper2.cpp
g++ -o $@ $< -std=c++11 -O3 -lm -g -O3 -Wall -Ijerasure/include jerasure/src/.libs/jerasure.o jerasure/src/.libs/galois.o -lgf_complete -fpermissive -lpthread -I $(C_INCLUDE)
+ida_gf65_paper3: ida_gf65_paper3.cpp
+ g++ -o $@ $< -std=c++11 -O3 -lm -g -O3 -Wall -Ijerasure/include jerasure/src/.libs/jerasure.o jerasure/src/.libs/galois.o -lgf_complete -fpermissive -lpthread -I $(C_INCLUDE)
+
+
clean:
- rm test_mat2 ida ida_gf64 ida_gf65_paper1 ida_gf65_paper2
+ rm test_mat2 ida ida_gf64 ida_gf65_paper1 ida_gf65_paper2 ida_gf65_paper3
diff --git a/IDA_new/ida_gf65_paper3.cpp b/IDA_new/ida_gf65_paper3.cpp
new file mode 100644
index 0000000..0197e43
--- /dev/null
+++ b/IDA_new/ida_gf65_paper3.cpp
@@ -0,0 +1,665 @@
+
+
+#include <iostream>
+#include <fstream>
+#include <chrono>
+#include <sstream>
+#include <ctime>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <algorithm> // std::random_shuffle
+#include <vector> // std::vector
+#include <unistd.h>
+#include <thread>
+
+
+extern "C" {
+ #include "jerasure.h"
+}
+
+typedef unsigned long mylong;
+#define LLUI (long long unsigned int)
+
+
+using namespace std;
+
+string cloud[5]={"dropboxida1","googleida1","onedriveida2","onedriveida1","pcloudida1"};
+
+void rc4keyperm(uint8_t *key,int len, int rp,int *sc, int size_DK) {
+
+ //sc=1:len;
+
+
+
+ for (int i=0;i<len;i++) {
+ sc[i]=i;
+ }
+ for (int it = 0; it < rp; it++) {
+ int j0 = 1;
+ for(int i0 = 0; i0<len; i0++) {
+ j0 = (j0 + sc[i0] + sc[j0] + key[i0%size_DK] )% len;
+ int tmp = sc[i0];
+ sc[i0] = sc[j0];
+ sc[j0] = tmp;
+ }
+
+ }
+}
+
+
+void display(mylong *mat, int r, int c) {
+ for(int i=0;i<r;i++) {
+ for(int j=0;j<c;j++) {
+ printf("%016llu ",LLUI mat[i*c+j]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+}
+
+mylong *matrix_multiply(gf_t *gf, mylong *m1, mylong *m2, int r1, int c1, int r2, int c2, int w)
+{
+ mylong *product;
+ int i, j, k;
+
+ product = (mylong *) malloc(sizeof(mylong)*r1*c2);
+ for (i = 0; i < r1*c2; i++) product[i] = 0;
+
+ for (i = 0; i < r1; i++) {
+ for (j = 0; j < c2; j++) {
+ for (k = 0; k < r2; k++) {
+ product[i*c2+j] ^= gf->multiply.w64(gf,m1[i*c1+k], m2[k*c2+j]);
+ }
+ }
+ }
+ return product;
+}
+
+
+
+int invert_matrix(gf_t *gf, mylong *mat, mylong *inv, int rows)
+{
+ int cols, i, j, k, x, rs2;
+ int row_start;
+ mylong tmp, inverse;
+
+ cols = rows;
+
+ k = 0;
+ for (i = 0; i < rows; i++) {
+ for (j = 0; j < cols; j++) {
+ inv[k] = (i == j) ? 1 : 0;
+ k++;
+ }
+ }
+// display(inv, rows, rows);
+// printf("\n");
+
+ /* First -- convert into upper triangular */
+ for (i = 0; i < cols; i++) {
+ row_start = cols*i;
+
+ /* Swap rows if we ave a zero i,i element. If we can't swap, then the
+ matrix was not invertible */
+
+ if (mat[row_start+i] == 0) {
+ for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
+ if (j == rows) return -1;
+ rs2 = j*cols;
+ for (k = 0; k < cols; k++) {
+ tmp = mat[row_start+k];
+ mat[row_start+k] = mat[rs2+k];
+ mat[rs2+k] = tmp;
+ tmp = inv[row_start+k];
+ inv[row_start+k] = inv[rs2+k];
+ inv[rs2+k] = tmp;
+ }
+ }
+
+ /* Multiply the row by 1/element i,i */
+ tmp = mat[row_start+i];
+ if (tmp != 1) {
+ inverse = gf->divide.w64(gf,1, tmp);
+ for (j = 0; j < cols; j++) {
+ mat[row_start+j] = gf->multiply.w64(gf,mat[row_start+j], inverse);
+ inv[row_start+j] = gf->multiply.w64(gf,inv[row_start+j], inverse);
+ }
+ }
+
+ /* Now for each j>i, add A_ji*Ai to Aj */
+ k = row_start+i;
+ for (j = i+1; j != cols; j++) {
+ k += cols;
+ if (mat[k] != 0) {
+ if (mat[k] == 1) {
+ rs2 = cols*j;
+ for (x = 0; x < cols; x++) {
+ mat[rs2+x] ^= mat[row_start+x];
+ inv[rs2+x] ^= inv[row_start+x];
+ }
+ } else {
+ tmp = mat[k];
+ rs2 = cols*j;
+ for (x = 0; x < cols; x++) {
+ mat[rs2+x] ^= gf->multiply.w64(gf,tmp, mat[row_start+x]);
+ inv[rs2+x] ^= gf->multiply.w64(gf,tmp, inv[row_start+x]);
+ }
+ }
+ }
+ }
+ }
+
+ /* Now the matrix is upper triangular. Start at the top and multiply down */
+
+ for (i = rows-1; i >= 0; i--) {
+ row_start = i*cols;
+ for (j = 0; j < i; j++) {
+ rs2 = j*cols;
+ if (mat[rs2+i] != 0) {
+ tmp = mat[rs2+i];
+ mat[rs2+i] = 0;
+ for (k = 0; k < cols; k++) {
+ inv[rs2+k] ^= gf->multiply.w64(gf,tmp, inv[row_start+k]);
+ }
+ }
+ }
+ }
+
+/* printf("mat\n");
+ display(mat, rows, rows);
+ printf("\n");
+ printf("inv\n");
+ display(inv, rows, rows);
+ printf("\n");
+*/
+ return 0;
+}
+
+
+
+
+int invertible_matrix(gf_t *gf, int *mat, int rows, int w)
+{
+ int cols, i, j, k, x, rs2;
+ int row_start;
+ mylong tmp, inverse;
+
+ cols = rows;
+
+ /* First -- convert into upper triangular */
+ for (i = 0; i < cols; i++) {
+ row_start = cols*i;
+
+ /* Swap rows if we ave a zero i,i element. If we can't swap, then the
+ matrix was not invertible */
+
+ if (mat[row_start+i] == 0) {
+ for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
+ if (j == rows) return 0;
+ rs2 = j*cols;
+ for (k = 0; k < cols; k++) {
+ tmp = mat[row_start+k];
+ mat[row_start+k] = mat[rs2+k];
+ mat[rs2+k] = tmp;
+ }
+ }
+
+ /* Multiply the row by 1/element i,i */
+ tmp = mat[row_start+i];
+ if (tmp != 1) {
+ inverse = gf->divide.w64(gf,1, tmp);
+ for (j = 0; j < cols; j++) {
+ mat[row_start+j] = gf->multiply.w64(gf,mat[row_start+j], inverse);
+ }
+ }
+
+ /* Now for each j>i, add A_ji*Ai to Aj */
+ k = row_start+i;
+ for (j = i+1; j != cols; j++) {
+ k += cols;
+ if (mat[k] != 0) {
+ if (mat[k] == 1) {
+ rs2 = cols*j;
+ for (x = 0; x < cols; x++) {
+ mat[rs2+x] ^= mat[row_start+x];
+ }
+ } else {
+ tmp = mat[k];
+ rs2 = cols*j;
+ for (x = 0; x < cols; x++) {
+ mat[rs2+x] ^= gf->multiply.w64(gf,tmp,mat[row_start+x]);
+ }
+ }
+ }
+ }
+ }
+ return 1;
+}
+
+
+
+
+
+mylong* readFullFile(char* filename,int n, int t, mylong& sizeFile, mylong & padded_size) {
+
+ ifstream stream(filename, ios::in | ios::binary | ios::ate);
+// ifstream stream("lena_small.png", ios::in | ios::binary | ios::ate);
+// ifstream stream("/home/couturie/Downloads/CARCARIASS.zip", ios::in | ios::binary | ios::ate);
+
+ sizeFile=stream.tellg();
+//cout << sizeFile << std::endl;
+ stream.seekg(0, ios::beg);
+
+
+
+
+
+
+ vector<uint8_t> contents((istreambuf_iterator<char>(stream)), istreambuf_iterator<char>());
+
+
+
+
+
+
+
+ //make padding, we need to pad to be divisible by 8*t, we
+ if((sizeFile+8)%(8*t)!=0) {
+// cout<<(int)(sizeFile/(8*t))<<endl;
+
+ int remainder=(8*t)*(1+(int)((sizeFile+8)/(8*t)))-sizeFile-8;
+ //cout << "remainder " << remainder << endl;
+ uint8_t vec[remainder];
+ for(int i=0;i<remainder;i++)
+ vec[i]=0;
+ //add remainder elements at the end
+ contents.insert(contents.end(),vec,vec+remainder);
+ //add 8 elements at the beginning for the size
+ contents.insert(contents.begin(),vec,vec+8);
+ }
+
+
+
+// cout << "res contents " << contents.size() << endl;
+
+// for(int i=0;i<contents.size();i++)
+// cout << (int)contents[i] << " ";
+// cout << endl;
+
+ uint8_t *p_contents=&contents[0];
+ uint8_t *p_temp=new uint8_t[sizeFile];
+
+ memcpy(p_temp,p_contents,sizeof(uint8_t)*sizeFile);
+
+
+ int sizeDK = 64;
+ uint8_t DK[sizeDK];
+ srand48(32);
+
+ for(int i=0;i<sizeDK;i++) {
+ DK[i]=lrand48();
+ }
+
+ int *Pbox=new int[sizeFile];
+ rc4keyperm(DK, sizeFile, 1, Pbox, 64);
+
+ for(int i=0;i<sizeFile;i++) {
+ p_contents[i]=p_temp[Pbox[i]];
+ }
+
+ free(p_temp);
+
+
+// mylong *p_contents2=reinterpret_cast<mylong*>(p_contents);
+
+ padded_size=contents.size()/8;
+
+ mylong *p_contents2=new mylong[padded_size];
+ memcpy(p_contents2,p_contents,sizeof(mylong)*padded_size);
+ //mylong *p_contents2=(mylong*)p_contents;
+
+ p_contents2[0]=sizeFile;
+
+
+
+
+/* for(int i=0;i<padded_size;i++)
+ cout << p_contents2[i] << " ";
+ cout << endl;
+*/
+ /* long res=0;
+ for(int i=8-1;i>=0;i--) {
+ res<<=8;
+ res+=p_contents[i];
+ }
+
+ cout << "convert val " << (long)res << endl;
+
+ res=0;
+ for(int i=16-1;i>=8;i--) {
+ res<<=8;
+ res+=p_contents[i];
+ }
+
+ cout << "convert val " << (long)res << endl;
+ */
+
+ return p_contents2;
+}
+
+void sendChunk(string name,int cloud_id) {
+ stringstream ss;
+ ss <<"rclone copy "<<name<<" "<<cloud[cloud_id]<<":";
+ string str = ss.str();
+ cout<<str<<endl;
+ system(str.c_str());
+ ss.str("");
+ ss<<"rm -f "<<name;
+ str = ss.str();
+ cout<<str<<endl;
+ system(str.c_str());
+}
+
+
+void retrieveChunk(string name,int cloud_id) {
+ stringstream ss;
+ ss <<"rclone copy "<<cloud[cloud_id]<<":"<<name<<" .";
+ string str = ss.str();
+ cout<<str<<endl;
+ system(str.c_str());
+}
+
+
+void saveFile(uint8_t *data, const char *fileName,long size_file) {
+// cout<<"size file "<<size_file<<endl;
+ FILE* pFile = fopen (fileName, "wb");
+ fwrite (data , sizeof(uint8_t), size_file, pFile);
+
+ fclose (pFile);
+}
+
+
+void readFile(uint8_t *data, const char *fileName,long size_file) {
+// cout<<"size file "<<size_file<<endl;
+ FILE* pFile = fopen (fileName, "rb");
+
+ fseek(pFile, 0L, SEEK_END);
+ int sz = ftell(pFile);
+ rewind(pFile);
+ if(sz!=size_file) {
+ cout << "error : size of this chunk is not correct !! " << endl;
+ exit(0);
+ }
+ fread (data , sizeof(uint8_t), size_file, pFile);
+
+ fclose (pFile);
+}
+
+
+void saveFile8(mylong *data, const char *fileName,long size_file) {
+
+ cout<<"size file 8 "<<size_file<<endl;
+ display(data,1,1);
+ FILE* pFile = fopen (fileName, "wb");
+
+
+
+ fwrite (data , sizeof(mylong), size_file, pFile);
+ fclose (pFile);
+
+
+
+}
+
+
+int main(int argc, char **argv)
+{
+ unsigned int w;
+ int invert;
+ mylong *matS;
+ mylong *matG;
+ mylong *matC;
+ mylong *inverse;
+ mylong *identity;
+
+
+ char *filename=new char[1000];
+
+// int size=5000000;
+ int t=3;
+ int n=5;
+
+ for(int i=0;i<argc;i++) {
+ if(strncmp(argv[i],"t",1)==0)
+ t=atoi(&(argv[i][1]));
+ if(strncmp(argv[i],"n",1)==0)
+ n=atoi(&(argv[i][1]));
+ if(strncmp(argv[i],"f",1)==0)
+ strcpy(filename,&argv[i][1]);
+ }
+
+
+ if(t>n) {
+ cout<<"pb t>n"<<endl;
+ exit(0);
+ }
+
+
+
+
+ double total_time=0;
+
+ w=64;
+ gf_t gf;
+ gf_init_easy(&gf, w);
+
+ mylong padded_size;
+ mylong sizeFile;
+ matS=readFullFile(filename,n,t,sizeFile,padded_size);
+
+// cout<<padded_size*8<<endl;
+
+/* for(int i=0;i<padded_size;i++)
+ cout << matS[i] << " ";
+ cout << endl;
+*/
+
+ int len=padded_size/t;
+// int len=size/t;
+// cout<<" len "<<len<<" "<<padded_size<<endl;
+
+ // matS = malloc(sizeof(mylong)*t*len);
+ matG = malloc(sizeof(mylong)*t*n);
+
+
+
+
+ srand48(time(0));
+ std::srand ( unsigned ( std::time(0) ) );
+
+/*
+ for(int i=0;i<t;i++) {
+ for(int j=0;j<len;j++) {
+ matS[i*len+j]=lrand48()<<32|lrand48();
+ }
+ }
+ */
+
+ for(int i=0;i<n;i++) {
+ for(int j=0;j<t;j++) {
+ matG[i*t+j]=lrand48()<<32|lrand48();
+ }
+ }
+
+
+/*
+ printf("Matrix S:\n");
+// display(matS, len, t);
+ display(matS, t, t);
+
+ printf("Matrix G:\n");
+ display(matG, n, t);
+*/
+
+// sleep(2);
+ auto start = std::chrono::system_clock::now();
+ matC=matrix_multiply(&gf, matG, matS, n, t, t, len, w);
+ auto end = std::chrono::system_clock::now();
+ std::chrono::duration<double> elapsed_seconds = end-start;
+ total_time+=elapsed_seconds.count();
+// cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
+
+// display(matC,t,t);
+
+// thread th[n];
+ //Save trunks
+ for(int i=0;i<n;i++) {
+ stringstream ss;
+ ss <<"file_"<<i<<".dat";
+ string str = ss.str();
+ saveFile((uint8_t*)&matC[i*len], str.c_str(),len*sizeof(mylong));
+// sendChunk( str,i);
+// th[i] = thread(sendChunk,str, i);
+ }
+
+/* for(int i=0;i<n;i++) {
+ th[i].join();
+ }
+*/
+/* cout<<"sleep begin"<<endl;
+ sleep(2);
+ cout<<"sleep end"<<endl;
+*/
+
+
+ mylong *matCs = malloc(sizeof(mylong)*t*len);
+ mylong *matGs = malloc(sizeof(mylong)*t*t);
+
+
+ std::vector<int> myvector;
+
+ // set some values:
+ for (int i=0; i<n; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
+
+ // using built-in random generator:
+ random_shuffle ( myvector.begin(), myvector.end() );
+
+
+
+// std::cout << "random chunk" << std::endl;
+ int ind=0;
+
+
+
+ for(int ii=0;ii<t;ii++) {
+
+ auto i=myvector[ii];
+// std::cout << myvector[i] << " ";
+
+
+ stringstream ss;
+ ss <<"file_"<<i<<".dat";
+ string str = ss.str();
+
+// retrieveChunk(str,i);
+// th[ii] = thread(retrieveChunk,str, i);
+ }
+
+
+ ind=0;
+
+ for(int ii=0;ii<t;ii++) {
+
+ auto i=myvector[ii];
+ // std::cout << myvector[i] << " ";
+
+
+ stringstream ss;
+ ss <<"file_"<<i<<".dat";
+ string str = ss.str();
+ // th[ii].join();
+ readFile((uint8_t*)&matCs[ind*len], str.c_str(),len*sizeof(mylong));
+
+// display(&matCs[ind*len],1,1);
+// display(&matC[i*len],1,1);
+
+ /*for(int j=0;j<len;j++) {
+ matCs[ind*len+j]=matC[i*len+j];
+ }*/
+
+
+
+ for(int j=0;j<t;j++) {
+ matGs[ind*t+j]=matG[i*t+j];
+ }
+ ind++;
+ }
+// std::cout << std::endl;
+
+
+// printf("Matrix Gs:\n");
+// display(matGs, t, t);
+
+// printf("Matrix Cs:\n");
+// display(matCs, t, len);
+
+ mylong* matGs_copy = malloc(sizeof(mylong)* t*t);
+
+ //WARNING invert changes the matrix
+// invert = invertible_matrix(&gf,matGs, t, w);
+// printf("\nInvertible Gs: %s\n", (invert == 1) ? "Yes" : "No");
+
+ memcpy(matGs_copy, matGs, sizeof(mylong)*t*t);
+ mylong *matInvGs = malloc(sizeof(mylong)*t*t);
+ invert_matrix(&gf, matGs_copy, matInvGs, t);
+
+ /*
+ WARNING this changes matGs
+ identity=matrix_multiply(&gf, matInvGs, matGs, t, t, t, t, w);
+ printf("Identity:\n");
+ display(identity, t, t);
+ */
+
+
+ //printf("Matrix Gs:\n");
+ //display(matGs, t, t);
+
+ mylong *matS2 = malloc(sizeof(mylong)*t*len);
+
+// sleep(2);
+ start = std::chrono::system_clock::now();
+ for(int i=0;i<1000;i++) {
+ matS2=matrix_multiply(&gf, matInvGs, matCs, t, t, t, len, w);
+ }
+ end = std::chrono::system_clock::now();
+ elapsed_seconds = end-start;
+// cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
+ total_time+=elapsed_seconds.count();
+ cout/*<<"TOTAL TIME : "*/<<total_time;
+
+/* printf("Matrix S2:\n");
+// display(matS2, len, t);
+ display(matS2, t, t);
+*/
+ int equal=1;
+ for(int i=0;i<padded_size && equal;i++) {
+ equal=matS[i]==matS2[i];
+// if(!equal)
+// printf("ARGH\n");
+ }
+// if(equal)
+// printf("EQUAL !!!\n");
+
+
+ mylong new_size=matS2[0];
+// cout << "size of data " << new_size << endl;
+
+
+ //first elements that contains the size is removed
+ uint8_t *reconstucted_data=reinterpret_cast<uint8_t*>(&matS2[1]);
+// saveFile(reconstucted_data, "file.dat",new_size);
+ return 0;
+}
+
+
diff --git a/IDA_new/run_long_paper3.py b/IDA_new/run_long_paper3.py
new file mode 100644
index 0000000..a395f66
--- /dev/null
+++ b/IDA_new/run_long_paper3.py
@@ -0,0 +1,20 @@
+#python3 run_long_paper3.py > exe_long_paper3.txt
+
+
+import subprocess
+import re
+
+
+print("#size \t t \t n \t time")
+
+i=8
+len=(2**i)
+
+subprocess.check_output("head -c "+str(len)+" </dev/urandom >file"+str(len),shell=True)
+for k in range(2,8,2):
+ result=subprocess.check_output("./ida_gf65_paper2 t"+str(k)+" n8 ffile"+str(len),shell=True)
+ res=result.decode()
+ print(str(len)+"\t"+str(k)+"\t 8 \t"+res)
+
+
+
--
2.39.5