//This is main 
//Initial Major chunk of Code written By Researcher Martin Albrecht and his team 
//https://bitbucket.org/malb/research-snippets/src
//mpicc -w -std=c99 try_for_mpi.c -o try -msse4.2 -lm
//time mpirun -np 8 try
//threads variable will have to be changed according to number of cores and must be a multiple of 2 
#include <stdbool.h> 
#include <unistd.h>
#include <time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <emmintrin.h>
#include <nmmintrin.h>
#include "mpi.h" 

#define RADIX 64 
#define Bs 64
#define Ks 80 

typedef unsigned long long uint64_t;

typedef uint64_t word;

void compare(unsigned long long b,unsigned long long c,unsigned long long *v64val)
{
     __m128i x, y;
    x=_mm_set_epi64x(Ks,Ks);
    y=_mm_set_epi64x(c,b);
    __m128i res = _mm_cmpeq_epi64(x, y);
    unsigned long long *val = (int64_t*) &res;
    v64val[0]=val[0];v64val[1]=val[1];
}


void XOR_word(word *a,word *b,const word *c,const word *d)
{
  __m128i var;
  var=_mm_xor_si128 (_mm_set_epi64x(*a,*b),_mm_set_epi64x(*c,*d));
  unsigned long long *v64val = (int64_t*) &var;
  *a=v64val[1],*b=v64val[0];
}
static inline void present_sbox(word *Y0, word *Y1, word *Y2, word *Y3, const word X0, const word X1, const word X2, const word X3) {
  register word T1,T2,T3,T4;
  T1 = X2 ^ X1;
  T2 = X1 & T1;
  T3 = X0 ^ T2;
  *Y3 = X3 ^ T3;
  T2 = T1 & T3;
  T1 ^= (*Y3);
  T2 ^= X1;
  T4 = X3 | T2;
  *Y2 = T1 ^ T4;
  T2 ^= (~X3);
  *Y0 = (*Y2) ^ T2;
  T2 |= T1;
  *Y1 = T3 ^ T2;
}

void transpose(word *out, word *inp, const size_t out_size, const size_t inp_size) {
  for(size_t j=0; j<out_size; j++) {
    out[j] = 0;
    for(size_t i=0; i<inp_size; i++) {
      out[j] |= ( ((inp[i]>>(j&63))&1) )<<(i&63);
    }
  }
}


void sBoxLayer(word *Y, word *X) {
  present_sbox(Y+ 0,Y+ 1,Y+ 2,Y+ 3, X[ 0],X[ 1],X[ 2],X[ 3]);
  present_sbox(Y+ 4,Y+ 5,Y+ 6,Y+ 7, X[ 4],X[ 5],X[ 6],X[ 7]);
  present_sbox(Y+ 8,Y+ 9,Y+10,Y+11, X[ 8],X[ 9],X[10],X[11]);
  present_sbox(Y+12,Y+13,Y+14,Y+15, X[12],X[13],X[14],X[15]);
  present_sbox(Y+16,Y+17,Y+18,Y+19, X[16],X[17],X[18],X[19]);
  
  present_sbox(Y+20,Y+21,Y+22,Y+23, X[20],X[21],X[22],X[23]);
  present_sbox(Y+24,Y+25,Y+26,Y+27, X[24],X[25],X[26],X[27]);
  present_sbox(Y+28,Y+29,Y+30,Y+31, X[28],X[29],X[30],X[31]);
  present_sbox(Y+32,Y+33,Y+34,Y+35, X[32],X[33],X[34],X[35]);
  present_sbox(Y+36,Y+37,Y+38,Y+39, X[36],X[37],X[38],X[39]);
  
  present_sbox(Y+40,Y+41,Y+42,Y+43, X[40],X[41],X[42],X[43]);
  present_sbox(Y+44,Y+45,Y+46,Y+47, X[44],X[45],X[46],X[47]);
  present_sbox(Y+48,Y+49,Y+50,Y+51, X[48],X[49],X[50],X[51]);
  present_sbox(Y+52,Y+53,Y+54,Y+55, X[52],X[53],X[54],X[55]);
  present_sbox(Y+56,Y+57,Y+58,Y+59, X[56],X[57],X[58],X[59]);
  
  present_sbox(Y+60,Y+61,Y+62,Y+63, X[60],X[61],X[62],X[63]);
}
void addRoundKey(word *X, const word *K) {
  XOR_word(X+0,X+1,K+0,K+1);    XOR_word(X+2,X+3,K+2,K+3);    XOR_word(X+4,X+5,K+4,K+5);    XOR_word(X+6,X+7,K+6,K+7);
  XOR_word(X+8,X+9,K+8,K+9);    XOR_word(X+10,X+11,K+10,K+11);XOR_word(X+12,X+13,K+12,K+13);XOR_word(X+14,X+15,K+14,K+15);
  XOR_word(X+16,X+17,K+16,K+17);XOR_word(X+18,X+19,K+18,K+19);XOR_word(X+20,X+21,K+20,K+21);XOR_word(X+22,X+23,K+22,K+23);  
  XOR_word(X+24,X+25,K+24,K+25);XOR_word(X+26,X+27,K+26,K+27);XOR_word(X+28,X+29,K+28,K+29);XOR_word(X+30,X+31,K+30,K+31);  
  XOR_word(X+32,X+33,K+32,K+33);XOR_word(X+34,X+35,K+34,K+35);XOR_word(X+36,X+37,K+36,K+37);XOR_word(X+38,X+39,K+38,K+39);  
  XOR_word(X+40,X+41,K+40,K+41);XOR_word(X+42,X+43,K+42,K+43);XOR_word(X+44,X+45,K+44,K+45);XOR_word(X+46,X+47,K+46,K+47);  
  XOR_word(X+48,X+49,K+48,K+49);XOR_word(X+50,X+51,K+50,K+51);XOR_word(X+52,X+53,K+52,K+53);XOR_word(X+54,X+55,K+54,K+55);  
  XOR_word(X+56,X+57,K+56,K+57);XOR_word(X+58,X+59,K+58,K+59);XOR_word(X+60,X+61,K+60,K+61);XOR_word(X+62,X+63,K+62,K+63);
}

void pLayer(word *X, word *Y) {
  X[ 0] = Y[ 0],  X[ 1] = Y[ 4],  X[ 2] = Y[ 8],  X[ 3] = Y[12];
  X[ 4] = Y[16],  X[ 5] = Y[20],  X[ 6] = Y[24],  X[ 7] = Y[28];
  X[ 8] = Y[32],  X[ 9] = Y[36],  X[10] = Y[40],  X[11] = Y[44];
  X[12] = Y[48],  X[13] = Y[52],  X[14] = Y[56],  X[15] = Y[60];
  X[16] = Y[ 1],  X[17] = Y[ 5],  X[18] = Y[ 9],  X[19] = Y[13];
  X[20] = Y[17],  X[21] = Y[21],  X[22] = Y[25],  X[23] = Y[29];
  X[24] = Y[33],  X[25] = Y[37],  X[26] = Y[41],  X[27] = Y[45];
  X[28] = Y[49],  X[29] = Y[53],  X[30] = Y[57],  X[31] = Y[61];
  X[32] = Y[ 2],  X[33] = Y[ 6],  X[34] = Y[10],  X[35] = Y[14];
  X[36] = Y[18],  X[37] = Y[22],  X[38] = Y[26],  X[39] = Y[30];
  X[40] = Y[34],  X[41] = Y[38],  X[42] = Y[42],  X[43] = Y[46];
  X[44] = Y[50],  X[45] = Y[54],  X[46] = Y[58],  X[47] = Y[62];
  X[48] = Y[ 3],  X[49] = Y[ 7],  X[50] = Y[11],  X[51] = Y[15];
  X[52] = Y[19],  X[53] = Y[23],  X[54] = Y[27],  X[55] = Y[31];
  X[56] = Y[35],  X[57] = Y[39],  X[58] = Y[43],  X[59] = Y[47];
  X[60] = Y[51],  X[61] = Y[55],  X[62] = Y[59],  X[63] = Y[63];
}

void encrypt(word *X, const word *subkeys, const size_t nr) {
  static word Y[Bs];
  for(size_t i=0; i<nr;i++) {
    addRoundKey(X, subkeys + (i*Bs));
    sBoxLayer(Y, X);
    pLayer(X, Y);
  }
  addRoundKey(X, subkeys + (nr*Bs));
}


/** Key Schedule **/

void rotate(word *k) {
  word temp[Ks];
  memcpy(temp,k,Ks*sizeof(word));
  for(size_t i =0; i<Ks; i++) {
    k[i] = temp[(i+61)%Ks];
  }
}

static inline void round_constant(word *rc, size_t i) {
  static word lookup[2] =
    {(uint64_t)0x0000000000000000,((uint64_t)0xFFFFFFFFFFFFFFFF)};
  rc[4] = lookup[(i&(1<<0))>>0];
  rc[3] = lookup[(i&(1<<1))>>1];
  rc[2] = lookup[(i&(1<<2))>>2];
  rc[1] = lookup[(i&(1<<3))>>3];
  rc[0] = lookup[(i&(1<<4))>>4];
}

void key_schedule(word *subkeys, word *key, const size_t nr) {
  word *ki = subkeys;
  word S[8];
  word rc[5];
  for(size_t i=0; i<=nr; i++) {
    for(size_t j=0; j<Bs; j++)
      ki[j] = key[j];
    ki+=Bs;
    rotate(key);
    present_sbox(&S[0],&S[1],&S[2],&S[3], key[0], key[1], key[2], key[3]);
    key[0] = S[0], key[1] = S[1], key[2] = S[2], key[3] = S[3];
    unsigned long long v64val[2];
    compare(80,128,v64val);
    if(((int)v64val[1])==-1) { 
      present_sbox(&S[4+0],&S[4+1],&S[4+2],&S[4+3], key[4+0], key[4+1], key[4+2], key[4+3]);
      key[4+0] = S[4+0], key[4+1] = S[4+1], key[4+2] = S[4+2], key[4+3] = S[4+3];
    };
    round_constant(rc, i+1);
    if(((int)v64val[0])==-1) {
      key[Ks-1-19] ^= rc[0], key[Ks-1-18] ^= rc[1], key[Ks-1-17] ^= rc[2];
      key[Ks-1-16] ^= rc[3], key[Ks-1-15] ^= rc[4];
    };
    if(((int)v64val[1])==-1) {
      key[Ks-1-66] ^= rc[0], key[Ks-1-65] ^= rc[1], key[Ks-1-64] ^= rc[2];
      key[Ks-1-63] ^= rc[3], key[Ks-1-62] ^= rc[4];
    };
  }
}


uint64_t Mirror64(uint64_t ins) {
  uint64_t inv_ins=0;
  for (int i = 0; i < 64; i++)
    if((ins>>i)&1)
      inv_ins|=(((uint64_t)0x0000000000000001)<<(64-1-i));
  return inv_ins;
};

void print_hex(int a)
{
  
  if(a<9){
    printf("%d",a);
  }
  else{
    switch(a)
    {
      case 10:
        printf("A");
        break;
      case 11:
        printf("B");
        break;
      case 12:
        printf("C");
        break;     
      case 13:
        printf("D");
        break;  
      case 14:
        printf("E");
        break;
      case 15:
        printf("F");
        break;    
    }
  }
}
void print_key(word key[Ks])
{
  int i,number=0;
  for(i=0;i<Ks;i=i+4)
  {
    number=key[i]*pow(2,3)+key[i+1]*pow(2,2)+key[i+2]*pow(2,1)+key[i+3]*pow(2,0);
    print_hex(number);
  }
  printf("\n");
}


int Desert(unsigned long long nn,unsigned long long crypt,int keyarr[Ks]){
{
  const size_t ntrials = 1;

  uint64_t plaintexts[RADIX];
  uint64_t ciphertexts[RADIX];
  word tmp[Bs];
  word key[Ks];
  
  size_t nr = 31;
  
  size_t i=0;
  if(Ks==80) {
    //printf("\nkey is:\n ");
    for(i=0;i<Ks;i++)
    {
      key[i] = keyarr[i]; 
    }
    //print_key(key);
    //printf("\n plaintext is %lld",nn);
    plaintexts[0]=nn;
  };
  if(Ks==128) {
    uint64_t ABC=Mirror64((uint64_t)0x0123456789abcdef);
    for(i=0;i<Ks;i++)
      key[i] = ((uint64_t)0xFFFFFFFFFFFFFFFF)*((ABC>>(i&63))&1);
    for(i=0; i<RADIX; i++)
      plaintexts[i] = ABC;
  };
  word *subkeys = (word *)calloc(Bs * (nr+1), sizeof(word));
  key_schedule(subkeys, key, nr);
  
  transpose(tmp, plaintexts, Bs, RADIX);
  
  for(i=0;i<ntrials;i++)
    encrypt(tmp, subkeys, nr);
        
  transpose(ciphertexts, tmp,  RADIX, Bs);
    for(i=0; i<1; i++)
    {
#ifdef _MSC_VER
      printf("%016I64X%016I64X\n",Mirror64(plaintexts[i]),Mirror64(ciphertexts[i]));
#else
      //printf("cipher %lld \n",Mirror64(ciphertexts[i]),crypt);//%16llx
#endif
 //     if(prin_flag==1)printf("cipher %lld \n",Mirror64(ciphertexts[i]),crypt);//%16llx 
    }
  free(subkeys);
  //printf("\n ciphertext is %lld",Mirror64(ciphertexts[0]));
  //printf("\n desired ciphertext is %lld",crypt);
  if(Mirror64(ciphertexts[0])==crypt)return 1;
  else return 0; 
}
}
unsigned long long  init_value(unsigned long long nn,int keyarr[Ks]){
{
  const size_t ntrials = 1;

  uint64_t plaintexts[RADIX];
  uint64_t ciphertexts[RADIX];
  word tmp[Bs];
  word key[Ks];
  
  size_t nr = 31;
  
  size_t i=0;
  if(Ks==80) {
    //printf("\ninitial key is:\n ");
    for(i=0;i<Ks;i++)
    {
      key[i] = keyarr[i];
    }
    //print_key(key);
    //printf("\n plaintext is %lld",nn);
      plaintexts[0]=nn;
  };
  if(Ks==128) {
    uint64_t ABC=Mirror64((uint64_t)0x0123456789abcdef);
    for(i=0;i<Ks;i++)
      key[i] = ((uint64_t)0xFFFFFFFFFFFFFFFF)*((ABC>>(i&63))&1);
    for(i=0; i<RADIX; i++)
      plaintexts[i] = ABC;
  };
  word *subkeys = (word *)calloc(Bs * (nr+1), sizeof(word));
  key_schedule(subkeys, key, nr);
  
  transpose(tmp, plaintexts, Bs, RADIX);
  
  for(i=0;i<ntrials;i++)
    encrypt(tmp, subkeys, nr);
        
  transpose(ciphertexts, tmp,  RADIX, Bs);
    for(i=0; i<1; i++)
    {
#ifdef _MSC_VER
      printf("%016I64X%016I64X\n",Mirror64(plaintexts[i]),Mirror64(ciphertexts[i]));
#else
#endif
    }
  free(subkeys);
  //printf("\ninitial ciphertext is %lld",Mirror64(ciphertexts[0]));
  return Mirror64(ciphertexts[0]);
}
}
int main(int argc, char **argv) 
{
  int a,i,count=0,length=20,Total_tasks=pow(2,length),threads=8,per_thread=Total_tasks/threads,my_id,numtasks,j;
   //char str[]="10111100110101100000101100011110001110101111010010101001000111010101110101010010";
  char str[]="11111010100110100111010010011001000011010011110111100000011011111000010101111101";
  //char str[]="00111011101110100001100011000010011101001100010001110100101010011101001110000100"
  unsigned long long ciphertext,plaintext;
  int y[Ks];
  for(i=0;i<Ks;i++){
    y[i]=str[i]-48;
  }
  plaintext=396;
  ciphertext=init_value(plaintext,y);
  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
  MPI_Comm_rank(MPI_COMM_WORLD, &my_id);
  //printf("Thread id %d has first =%d last =%d\n",my_id,my_id*per_thread,my_id*per_thread+per_thread-1);
  //printf("first 20 bits of the matching key will be printed");
  printf("Thread id %d is searching\n",my_id);

  for(i=my_id*per_thread;i<=my_id*per_thread+5;i++)
  {
      count=i; 
      for(j=0;j<length;j++)
      {
        y[length-1-j]=count%2;
        count=count/2;
      }
      //printf("Thread id %d using key as binary of %d  for plain text %llu found ",my_id,i,plaintext);
      printf("Thread with id %d is searching\n",my_id,i); 
      a=Desert(plaintext,ciphertext,y);
      if(a==1){
        count=i;
        printf("Thread with id %d found key is binary of %d",my_id,i);
        printf("\n");
        break;
      }
  }
  for(i=my_id*per_thread;i<=my_id*per_thread+per_thread-1;i++)
  {
      count=i; 
      for(j=0;j<length;j++)
      {
        y[length-1-j]=count%2;
        count=count/2;
      }
      a=Desert(plaintext,ciphertext,y);
      if(a==1){
        count=i;
        printf("Thread with id %d found key which is binary of %d",my_id,i);
        printf("\n");
        //for(j=0;j<20;j++)printf("%c",str[i]);
        for(j=0;j<length;j++)
        {
        y[length-1-j]=count%2;
        printf("%d",y[j]);
        count=count/2;
        }
        printf("\n");
        break;
      }
  }
  MPI_Finalize();
  return 0;
}