// A program feladata, hogy az összes n (pl. 11) 
// bites szám (N darab) halmazából megadja azt a legnagyobb halmazt, 
// melynek elemei közti Hamming távolság legalább k (pl. 3)
// Ez a kód 32 bites Intel Duo Core procira készült, típ: T2050, 2x1,6 GHz

#include <stdlib.h>    // randomnak
#include <locale>
#include <wchar.h>
#include "Vectorh.h"
#include <fstream>
//#include <xmmintrin.h> //SSE
//#include <emmintrin.h> //SSE2
#include <tmmintrin.h>   //SSE3
//#include <smmintrin.h> //SSE4  - not supported

using namespace std;

#define utvonal "C:\\R128_B.txt" // a végeredményt tároló fájl helye
#define N   128 // vektor mérete
#define xmmlgh		    128
#define wl               32  // word length - a proc. szószélessége
#define max_li   0xFFFFFFFF  // long int maximum
#define wi (int)       N/wl  // word index max
#define wis (int)  N/xmmlgh  
#define w                11  // bitszélesség - kódszavak
#define k                 3

int hamming_distance(int a,int b) {      // a és b Hamming távolságával tér vissza
	int r,d,hi;                          // r a visszatérési érték, d: hány bitben térnek el, i mint index változó
	r = 0;
	d = a^b;                             // ahol különbség van, ott 1 az érték
		for (hi=0;hi<w;hi++){            // 1-esek számolgatása d-ben
			if((d)&((int)1<<hi)) r++;
		} 
	return r;
}

void main(){
    locale hun("hungarian",locale::all);
	locale::global(hun);
	
	time_t t,t0,t1,t2;
    unsigned int u[wi]; // segédvektor
    __m128i ms[N][wis]; // a szomszédossági mátrix
    __m128i us[wis];    // segédvektor

	int v[N];     // összes 11 bites szám
    int i,j,p;    // index változók
    int z = 0;    // további index változók. 
	int q = 0;
	int z_max = 0; // az élek száma (a klikkek számának maximuma) 
	int z_p   = 0; // az adott részlet mérete
	int z1,z2;     // a részlet kezdete és vége
	int size_max = 0; // a maximáis klikk mérete (NP teljes!)
	int bits; 
	int fc;
    __m128i max_mm_const = _mm_setr_epi32(-1,-1,-1,-1);
	__m128i min_mm_const = _mm_setr_epi32(0x00000000,0x00000000,0x00000000,0x00000000);
	__m128i mask0 = _mm_setr_epi32(0x00000001,0x00000000,0x00000000,0x00000000);   // 128 bit mask
	__m128i mask1 = _mm_setr_epi32(0x00000000,0x00000001,0x00000000,0x00000000);   // 128 bit mask
	__m128i mask2 = _mm_setr_epi32(0x00000000,0x00000000,0x00000001,0x00000000);   // 128 bit mask
	__m128i mask3 = _mm_setr_epi32(0x00000000,0x00000000,0x00000000,0x00000001);   // 128 bit mask
	__m128i masks[xmmlgh];
	__m128i masks_r[xmmlgh];
	char cx[16] = {0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0};
	unsigned char c[16]= {0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0};
	int pNo = 1;  // hány részlet
    int pCr = 1; // aktuális részlet


// Paraméterek beolvasása

	cout<<"Hány részre akarja osztani a program futását?";cout<<endl;
	cin>>pNo;
	cout<<endl;
	cout<<"Hanyadik részletet számolja a program?";cout<<endl;
	cin>>pCr;
	cout<<endl;

    cout<<"A program fut. N=";
	cout<<N; 

	time(&t0);
	
	  for(i=0;i<N;i++){ // vektor feltöltése
		  v[i] = i;     // a vektor elemei alkotják gráfunk pontjait
	  }

	  for(i=0;i<wl;i++){  // maszkok számítása
	    masks[i]      = _mm_slli_epi32(mask0,i);
		masks[i+32]   = _mm_slli_epi32(mask1,i);
		masks[i+64]   = _mm_slli_epi32(mask2,i);
		masks[i+96]   = _mm_slli_epi32(mask3,i);

		masks_r[i]       = _mm_andnot_si128(masks[i],max_mm_const);
		masks_r[i+32]    = _mm_andnot_si128(masks[i+32],max_mm_const);
		masks_r[i+64]    = _mm_andnot_si128(masks[i+64],max_mm_const);
		masks_r[i+96]    = _mm_andnot_si128(masks[i+96],max_mm_const);
	  }
 /*
	  for(i=0;i<N;i++){ // Hamming távolság számítása    
		  for(j=0;j<wi;j++){
			  for(p=0;p<wl;p++){
			    (hamming_distance(v[i],v[j*wl+p])>=k)? (m[i][j]|=(1<<p)): (m[i][j]&= ~(1<<p));  // ha nagyobb mint k, akkor az egy élt jelent a gráfunkban
			  }
	      }
	  }	
*/
	  for(i=0;i<N;i++){ // Hamming távolság számítása    
		  for(j=0;j<wis;j++){
			  for(p=0;p<xmmlgh;p++){
				  if (hamming_distance(v[i],v[j*xmmlgh+p])>=k){ms[i][j]=_mm_or_si128(ms[i][j],masks[p]);} 
				  else ms[i][j]=_mm_and_si128(ms[i][j],masks_r[p]);  // ha nagyobb mint k, akkor az egy élt jelent a gráfunkban	
			  }
	      }
	  }	

      cout<<endl;
	  cout<<"Szomszédossági mátrix feltöltve.";

	  cout<<endl;
	  time(&t);
	  cout<<"T+";cout<<t-t0;cout<<'s';
	  cout<<endl;

	vector<vector<int>> v1;     // a klikkeket tartalmazó változó
	vector<int> v2;             // segédváltozó, int vektor, egy klikk pontjait tartalmazza	
	int n;
   
     v2.insert(0,0);
	 v2.insert(1,0); 
     
	 int j_last;
	 int bNo;
	 // Klikkek keresése: élek alapján
	  for(i=0;i<N;i++){   // zmax meghatározása  
	     for(n=i+1;n<N;n++){
			 j = (int) (n/xmmlgh);
			 p = n%xmmlgh;

			 bNo = (int) p/8;
		     p=p%8;

             // ide jöhet még valami feltételszerűség
             _mm_maskmoveu_si128(ms[i][j], max_mm_const, cx);
			 for(fc = 0;fc<16;fc++) c[fc] = (unsigned char)(cx[fc]);

			 if (c[bNo]&(1<<p)) z++;  // találtunk egy élt
	      }
	  }	  

	  z_max = z;   // z_max a klikkek maximális száma - élek száma a szomszédossági mátrixban
	  z_p   = (int) z_max/pNo;
	  z1 = (int) (pCr-1)*z_p; z2 = (int) (pCr)*z_p;  // a részlet eleje és vége
	  v1.insert_vect_fst(z_max,2,0);
      z=0;

      for(i=0;i<N;i++){     
	     for(n=i+1;n<N;n++){
			 j = (int) (n/xmmlgh);
			 p = n%xmmlgh;
			 bNo = (int) p/8;
		     p=p%8;
             // ide jöhet még valami feltételszerűség
             _mm_maskmoveu_si128(ms[i][j], max_mm_const, cx);        // cx-be kiolvassuk a mátrix i,j indexekkel leírt 128 bites elemét
			 for(fc = 0;fc<16;fc++) c[fc] = (unsigned char)(cx[fc]); // átmásoljuk cx-et c-be

			 if (c[bNo]&(1<<p))  { // találtunk egy élt
				 v2[0]=n;          // az élt két pontja adja meg
				 v2[1]=i;
				 v1[z] = v2;       // minden él egy új klikket jelent (Klikkek száma felülről becsülhető az élek számával.) 
				 z++;              // következő klikk
				 //if (z>=z_p) break;
			 }	  
	      }
		 //if (z>=z_p) break;
	  }	  


	// EZ ITT A FŐCIKLUS

      time(&t);   // T1 időpillanat, a kezdeti klikkek készen vannak
	  t1 = t-t0;

	  // z az aktuális klikket - minden klikken végigmegyünk, és bővítjük, ha lehet. 
      // i futó index, összesen N-szer  
	  for(z = z1;z<z2;z++){  // az egyes klikkeken végigmegyünk
		  for(i=0;i<N;i++){  
			  for (j=0;j<wis;j++) us[j] = max_mm_const;  // u vektor alapállapota
			  for(q = 0;q<v1[z].size();q++){			 // z. klikk elemeinek közös szomszédjai, q - az elemek indexe
				  for(j=0;j<wis;j++) {us[j]= _mm_and_si128((us[j]),(ms[(v1[z][q])][j]));} // közös szomszéd keresése
			  }

             // ez most igen ronda
			  for(j=0;j<wis;j++) {
                _mm_maskmoveu_si128(us[j], max_mm_const, cx);				// csak ezt a 
			    for(fc = 0;fc<16;fc++) c[fc] = (unsigned char)(cx[fc]);
			    u[j*4]   = (c[3]<<24) +(c[2]<<16) +(c[1]<<8) +c[0];
				u[j*4+1] = (c[7]<<24) +(c[6]<<16) +(c[5]<<8) +c[4];
				u[j*4+2] = (c[11]<<24)+(c[10]<<16)+(c[9]<<8) +c[8];
				u[j*4+3] = (c[15]<<24)+(c[14]<<16)+(c[13]<<8)+c[12];
			  } 

			  j = 0;
			  while ((j<wi-1)&&(!(u[j])) ){j++;};            // amíg nem talál egy egyest a tömbben
			  for (p=0;p<wl;p++) if ((u[j])&(1<<p)) break;
			  if (u[j]&(1<<p)) v1[z].insert(v1[z].size(),j*wl+p);       // közös szomszéd beillesztése
		   };
		  
		  if (((z>>8)<<8) == z){  // minden 256.-ik klikknél százalék kiírás 
		    cout<<((z*100/z_max));cout<<"% ";cout<<"klikkek: ";cout<<z;cout<<"/";cout<<z_p;cout<<" (";cout<<z_max;cout<<")";
		    cout<<endl;
		  }
	  }       

	  time(&t);     // T2 időpillanat, a teljes számolás kész
	  t2 = t-t0;

	  // megjelenítés - fájlba írás
      
	  fstream fp; //fp legyen a fájl változónk
	  fp.open (utvonal, fstream::in | fstream::out |fstream::trunc);

	  for(z=z1;z<z2;z++){if (size_max<v1[z].size()) size_max = v1[z].size();} // maxmimum keresése
      
	  cout<<endl;cout<<endl;
	  cout<<"A maximális klikkek:";
	  cout<<endl;cout<<endl;
	  fp<<endl;fp<<endl;
	  fp<<"A maximális klikkek:";
	  fp<<endl;fp<<endl;

	  for(z=z1;z<z2;z++){
		  if (v1[z].size()== size_max){
			  v1[z]=v1[z].mergesort();
		    for(q=0;q<v1[z].size();q++){cout<<v1[z][q];cout<<" ";}
			for(q=0;q<v1[z].size();q++){fp<<v1[z][q];fp<<" ";}
		    cout<<endl;
			fp<<endl;
		  }
	  }
	  cout<<endl;cout<<endl;
	  cout<<"A maximális klikkméret: ";
	  cout<<size_max;
      cout<<endl;cout<<endl;

	  fp<<endl;fp<<endl;
	  fp<<"A maximális klikkméret: ";
	  fp<<size_max;
      fp<<endl;fp<<endl;

	  fp<<endl;fp<<endl;
	  fp<<"A részletek száma:";
	  fp<<pNo;
      fp<<endl;fp<<endl;

	  fp<<endl;fp<<endl;
	  fp<<"Az aktuális részlet:";
	  fp<<pCr;
      fp<<endl;fp<<endl;

	  fp.close(); 

      cout<<endl;
	  time(&t);
	  cout<<"T1: T+";cout<<t1;cout<<'s';     // T1 időpillanat, a kezdeti klikkek készen vannak
	  cout<<endl;
	  cout<<"T2: T+";cout<<t2;cout<<'s';     // T2 időpillanat, a teljes számolás kész
	  cout<<endl;
	  cout<<"T3: T+";cout<<t-t0;cout<<'s';   // T3 időpillanat, kiíratás is kész
	  cout<<endl;cout<<endl;
      cin>>pNo;
}