#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <pthread.h>
#include <time.h>
#include <sys/time.h>
#include <malloc.h>
//#include <bitset>
//#include <xmmintrin.h>

struct sort_structure{
	unsigned int highest;
	unsigned int sub_highest[256][256];
};

//struct custom64{
//       unsigned long num_64 : 64;
//};


struct translation_structure{
	unsigned int times;
        char *series;
	//unsigned int filler;
};

struct empty{
	char times;
};

struct pat_length{
	unsigned int highest_times;
	unsigned int len;
	unsigned int search_num;
	//int frequency;
	//unsigned int sizes[256][256]; //262KB
	struct translation_structure ***member;
	//unsigned long filler;
}*table;


struct buffer_structure {
	//unsigned long unique_id;
	//int open;
	//unsigned int times;
	char *string;
	char *series;
	unsigned int times;
	//char filler[8];
	//24 bytes + size of string
};

struct common_structure {
	//unsigned long unique_id;
	//int open;
	unsigned int times;
	unsigned int sub;
	char *string;
	//unsigned int sub;
	//char filler[8];
	//20 bytes + size of string
};

/*
struct indices{
	//char index[2][256][256]; //64KB
	//char index2[256][256];
	struct buffer_structure *buffer[256]; //786KB
	struct common_structure *common[256]; //655KB
	unsigned int buf_members[256]; //1KB
	unsigned int buf_count[256]; //1KB
	unsigned int com_count[256]; //1KB
	unsigned long *unique_id[256];
};
*/

int file_bytes;
int frequency;
char *mem_file;

static void progress_func(int max_searchs, int pat_len);
void *match_search(void *set);

static void progress_func(int max_searchs, int pat_len){
	static float a = 0;
	static float b = 0;
	
	if(max_searchs == 0){
		b++;
		printf("progress: %.02lf%% %d length patterns done.\n",(double)((b/a)*100),pat_len );
	}else{
		a = max_searchs;
		printf("progress: %.02lf%%\n",(double)((b/a)*100));
	}
}

void *match_search(void *set){
        //returns 0 for match found and written
        //returns 1 for no matches found

	int num7;
        int num4;
        register int num2=0;
        register int num3;
	int num5=0;
	int num6=0;

	const int num1 = table[*(unsigned int *)set].search_num;
	//const unsigned int stop_byte = file_bytes-table[num1].len;
	const unsigned int stop_byte = file_bytes-table[num1].len-128;
	const unsigned short member_length = table[num1].len-1;
	unsigned short search_offset = 0;	

	int prefetch_a[128];
	int prefetch_b[8];
	//int prefetch_id=0;
	//unsigned int prefetch_id_a[]= {0, 0, 0, 0};
	//char prefetch_id_b[4];
	//unsigned char prefetch_c[16];
	unsigned int pre_int=0;
	unsigned int pre_count=0;
	int pre_ret=0;
/*
	register unsigned char prefetch_a;
	register unsigned char prefetch_b;

	register unsigned char prefetch_c;
	register unsigned char prefetch_d;
	register unsigned char prefetch_e;
	register unsigned char prefetch_f;
	register unsigned char prefetch_g;
	register unsigned char prefetch_h;
*/


	register unsigned char first_char=0;
	unsigned char last_char=0;	
	unsigned char sec_char=0;
	unsigned char a_char=0;
	unsigned char b_char=0;
	unsigned char c_char=0;

	register unsigned int id = 0;
	unsigned int table_miss = 0;
	unsigned int table_found = 0;
	unsigned int cache_found = 0;
	unsigned int buffer_found = 0;
	unsigned int patterns_total = 0;
	unsigned int patterns_freed = 0;
	unsigned int empties = 0;

//num3 = sysconf(_SC_PAGESIZE);
//printf("pagesize: %d\n", num3);

	//char *index[256][256];

	char *index;

	if(member_length>5){
		index = malloc(sizeof(char)*65536*2);
		//for(num3=0; num3<256; num3++){
		//	for(num4=0; num4<256; num4++){
		//		index[num3][num4]=malloc(sizeof(char)*2);
		//	}
		//}
	}else{
		index = malloc(sizeof(char)*65536);
		//for(num3=0; num3<256; num3++){		
		//	for(num4=0; num4<256; num4++){
		//		index[num3][num4]=malloc(sizeof(char));
		//	}
		//}
	}

        struct buffer_structure *buffer[256]; 
        struct common_structure *common[256]; 
        unsigned int buf_members[256]; 
        unsigned int buf_count[256]; 
        unsigned int com_count[256]; 

//        unsigned long *unique_id[256];
//	unsigned long *common_id[256];
//	unsigned long *buffer_id[256];

	unsigned int *unique_id[256];

	unsigned int *common_id[256];
	unsigned int *buffer_id[256];
	int *buffer_open[256];
	int *common_open[256];

	unsigned int sizes[256][256];

	//unsigned int exclusion[32768];

	struct translation_structure *temp_struct_array;

	double cache_sizes[2];

	//struct indices index;
	
	//unsigned int i_members = 128;
	//calculate cache/buffer members
	//24
/*
	num2 = member_length+1;
	if(num2 < 5){
		num4 = 4;
	}else if(num2 < 21){
		num4 = 20;
	}else if(num2 < 53){
		num4 = 52;
	}else{
		num4 = 116;
	}
*/
	num3 = 256*(sizeof(struct buffer_structure)+member_length+1);	
//	num7 = num4 - num2;

	//num4=floor(917504/num3);
	//num4=floor(524288/num3);
	//num4=floor(393216/num3);
	//num4=floor(1572864/num3);
	num4=floor(262144/num3);
	//num4=floor(131072/num3);
	//num4=floor(65536/num3);
/*
	num2 = member_length+1;
	if(num2 < 9){
		num5 = 8;
	}else if(num2 < 25){
		num5 = 24;
	}else if(num2 < 57){
		num5 = 56;
	}else{
		num5 = 120;
	}

	num6 = num5 - num2;
	num3 = 256*(8+num5);
*/
	//num5=floor(917504/num3);
	//num5=floor(1572864/num3);
	num3 = 256*(sizeof(struct common_structure)+member_length+1);
	num5=floor(786432/num3);
	//num5=floor(524288/num3);
	//num5=floor(393216/num3);
	//num5=floor(262144/num3);
	//num5=floor(131072/num3);
	//num5=floor(65536/num3);


	if(num4 < 8){
		num4=8;
	}
	while(num4 % 8 != 0){
		num4++;
	}
	//if(num5 < 8){
	//	num5=8;
	//}
	while(num5 % 4 != 0){
		num5++;
	}

	const unsigned short b_members = num4;
	const unsigned short c_members = num5;

//printf("buff: %lu comm: %lu\n", sizeof(struct buffer_structure), sizeof(struct common_structure));
//printf("charptr: %lu int: %lu\n", sizeof(char *), sizeof(int) );

	for(num3=0; num3<256; num3++){

//buffer[num3] = memalign (16, b_members*sizeof(struct buffer_structure));
//common[num3] = memalign (16, c_members*sizeof(struct common_structure));
//posix_memalign(&var, 64, 8)
		buffer[num3] = malloc(b_members*sizeof(struct buffer_structure));
		common[num3] = malloc(c_members*sizeof(struct common_structure));
		//buffer_id[num3] = malloc(b_members*sizeof(unsigned long));
		//common_id[num3] = malloc(c_members*sizeof(unsigned long));
//buffer_id[num3] = memalign (64, b_members*sizeof(unsigned int));
//common_id[num3] = memalign (64, c_members*sizeof(unsigned int));
//buffer_open[num3] = memalign (64, b_members*sizeof(int));
//common_open[num3] = memalign (64, c_members*sizeof(int));



		buffer_id[num3] = malloc(b_members*sizeof(unsigned int));
		common_id[num3] = malloc(c_members*sizeof(unsigned int));
		buffer_open[num3] = malloc(b_members*sizeof(int));
		common_open[num3] = malloc(c_members*sizeof(int));

		for(num4=0; num4<b_members; num4++){			
//buffer[num3][num4].string = memalign (32, table[num1].len*sizeof(char));
			buffer[num3][num4].string = malloc(table[num1].len*sizeof(char));
			//buffer_id[num3][num4] = malloc(sizeof(unsigned long));
		}
		for(num4=0; num4<c_members; num4++){
//common[num3][num4].string = memalign (32, table[num1].len*sizeof(char));
			common[num3][num4].string = malloc(table[num1].len*sizeof(char));
			//common_id[num3][num4] = malloc(sizeof(unsigned long));
		}

	}
	cache_sizes[0] = 256*b_members*( sizeof(struct buffer_structure)+sizeof(unsigned int)+sizeof(int)+(table[num1].len*sizeof(char)) );
	cache_sizes[1] = 256*c_members*( sizeof(struct common_structure)+sizeof(unsigned int)+sizeof(int)+(table[num1].len*sizeof(char)) );
	
	//
	//index.unique_id = malloc(sizeof(int *)*256);
	for(num3=0; num3<256; num3++){
		//unique_id[num3] = memalign (16, sizeof(unsigned int)*16);
		unique_id[num3]=malloc(sizeof(unsigned int)*4);
		//unique_id[num3]=malloc(sizeof(unsigned long)*16);
		unique_id[num3][0]=3;
		for(num4=0; num4<256; num4++){
			sizes[num3][num4] = 1;
		}
	}

	//index.unique_id[0]=0;

	for(num7=0; num7<256; num7++){
		num2=0;
		for(num3=0; num3<256; num3++){
			buf_members[num3] = 0;
			buf_count[num3] = 0;
			com_count[num3]=0;
			//index.com_members[num3]=0;
			if(member_length>5){
				for(num4=0; num4<256; num4++){
					index[num3*256+num4]=0;
					index[65536+num3*256+num4]=0;
				}
			}else{
				for(num4=0; num4<256; num4++){
					index[num3*256+num4]=0;
				}
			}
			for(num4=0; num4<b_members; num4++){
				buffer_open[num3][num4]=1;
				buffer[num3][num4].times=0;
			}
			for(num4=0; num4<c_members; num4++){
				common[num3][num4].times=0;
				common[num3][num4].sub=0;
				common_open[num3][num4]=1;
			}
		}
		
		for(num3=0; num3<256; num3++){
			//if(index.unique_id[num3][0] > 24){
				//free(index.unique_id[num3]);
				//index.unique_id[num3]=malloc(sizeof(unsigned int)*25);

			//for(num4=1; num4<index.unique_id[num3][0]+1; num4++){
			//	index.unique_id[num3][num4]=0;
			//}
			unique_id[num3][0]=3;
			//}
		}
		for(num3=0; num3<8; num3++){
			prefetch_b[num3] = num7;
		}
		//for(num3=0; num3<128; num3++){
		//	prefetch_a[num3]=0;
		//}

			//index.unique_id[0]=0;
		while(num2<stop_byte){

			//fill a page 16bytes at a time
			for(num3=0; num3<121; num3+=8){
				prefetch_a[num3] = (unsigned char)mem_file[num2+num3];
				prefetch_a[num3+1] = (unsigned char)mem_file[num2+num3+1];
				prefetch_a[num3+2] = (unsigned char)mem_file[num2+num3+2];
				prefetch_a[num3+3] = (unsigned char)mem_file[num2+num3+3];

				prefetch_a[num3+4] = (unsigned char)mem_file[num2+num3+4];
				prefetch_a[num3+5] = (unsigned char)mem_file[num2+num3+5];
				prefetch_a[num3+6] = (unsigned char)mem_file[num2+num3+6];
				prefetch_a[num3+7] = (unsigned char)mem_file[num2+num3+7];
/*
				prefetch_a[num3+8] = (unsigned char)mem_file[num2+num3+8];
				prefetch_a[num3+9] = (unsigned char)mem_file[num2+num3+9];
				prefetch_a[num3+10] = (unsigned char)mem_file[num2+num3+10];
				prefetch_a[num3+11] = (unsigned char)mem_file[num2+num3+11];
				prefetch_a[num3+12] = (unsigned char)mem_file[num2+num3+12];
				prefetch_a[num3+13] = (unsigned char)mem_file[num2+num3+13];
				prefetch_a[num3+14] = (unsigned char)mem_file[num2+num3+14];
				prefetch_a[num3+15] = (unsigned char)mem_file[num2+num3+15];
*/

			}
//printf("here 1\n");
			//parse page for num7 matches
			for(num3=0; num3<121; num3+=8){

                                if(prefetch_a[num3] == prefetch_b[0]){
					prefetch_a[num3]=-1;
				}
                                if(prefetch_a[num3+1] == prefetch_b[1]){
					prefetch_a[num3+1]=-1;
				}
                                if(prefetch_a[num3+2] == prefetch_b[2]){
					prefetch_a[num3+2]=-1;
				}
                                if(prefetch_a[num3+3] == prefetch_b[3]){
					prefetch_a[num3+3]=-1;
				}

                                if(prefetch_a[num3+4] == prefetch_b[4]){
					prefetch_a[num3+4]=-1;
				}
                                if(prefetch_a[num3+5] == prefetch_b[5]){
					prefetch_a[num3+5]=-1;
				}
                                if(prefetch_a[num3+6] == prefetch_b[6]){
					prefetch_a[num3+6]=-1;
				}
                                if(prefetch_a[num3+7] == prefetch_b[7]){
					prefetch_a[num3+7]=-1;
				}
/*
                                if(prefetch_a[num3+8] == prefetch_b[8]){
					prefetch_a[num3+8]=-1;
				}
                                if(prefetch_a[num3+9] == prefetch_b[9]){
					prefetch_a[num3+9]=-1;
				}
                                if(prefetch_a[num3+10] == prefetch_b[10]){
					prefetch_a[num3+10]=-1;
				}
                                if(prefetch_a[num3+11] == prefetch_b[11]){
					prefetch_a[num3+11]=-1;
				}
                                if(prefetch_a[num3+12] == prefetch_b[12]){
					prefetch_a[num3+12]=-1;
				}
                                if(prefetch_a[num3+13] == prefetch_b[13]){
					prefetch_a[num3+13]=-1;
				}
                                if(prefetch_a[num3+14] == prefetch_b[14]){
					prefetch_a[num3+14]=-1;
				}
                                if(prefetch_a[num3+15] == prefetch_b[15]){
					prefetch_a[num3+15]=-1;
				}

*/
			}
			
//printf("here 2\n");
			pre_int=num2;

			//for(pre_count=0; pre_count<4096; pre_count++){

			pre_count=0;
			first_char = num7;
			while(pre_count<125){

				if(prefetch_a[pre_count] == -1){
					num2=pre_int+pre_count;					
					pre_ret=1;
					goto proceed;
				}
				pre_a:
				pre_count++;
				if(prefetch_a[pre_count] == -1){
					num2=pre_int+pre_count;
					pre_ret=2;
					goto proceed;
				}
				pre_b:
				pre_count++;
				if(prefetch_a[pre_count] == -1){
					num2=pre_int+pre_count;
					pre_ret=3;
					goto proceed;
				}
				pre_c:
				pre_count++;
				if(prefetch_a[pre_count] == -1){
					num2=pre_int+pre_count;
					pre_ret=4;
					goto proceed;
				}
				pre_d:
				pre_count++;
			}
						
			goto found;

			proceed:
			sec_char = (unsigned char)mem_file[num2+1];

			//first_char = (unsigned char)mem_file[num2];
			//sec_char = (unsigned char)mem_file[num2+1];
			last_char = (unsigned char)mem_file[num2+member_length];
//			if(!index[sec_char][last_char]){
//				goto no_search;
//			}

			if(member_length>5){
				a_char = (unsigned char)mem_file[num2+member_length-1];
				b_char = (unsigned char)mem_file[num2+member_length-2];
				search_offset = member_length-3;
				c_char = (unsigned char)mem_file[num2+search_offset];
				//id = c_char*4294967296 + b_char*65536 + a_char*256 + last_char;
				id = c_char*16777216 + b_char*65536 + a_char*256 + last_char;
				if(!index[sec_char*256+last_char] || !index[65536+a_char*256+b_char]){
					goto no_search;
				}
				//for(num3=0; num3<4; num3++){
				//	prefetch_id_a[num3] = id;
				//}
			}else{
				search_offset = member_length-1;
				a_char = (unsigned char)mem_file[num2+search_offset];
				//id = first_char*4294967296 + sec_char*65536 + a_char*256 + last_char;
				id = first_char*16777216 + sec_char*65536 + a_char*256 + last_char;
				if(!index[sec_char*256+last_char]){
					goto no_search;
				}
				//for(num3=0; num3<4; num3++){
				//	prefetch_id_a[num3] = id;
				//}

			}

			//if(!index[0][sec_char][last_char]){
			//	goto no_search;
			//}

			//if(!index.index2[a_char][_char]){


                        num3=0;
                        //search cached xMB worth of most recent found patterns
                        while(num3<b_members){
                                if(!buffer_open[last_char][num3]){
                                        //if(last_char != (unsigned char)index.buffer[sec_char][num3].string[member_length]){
                                        if(id != buffer_id[last_char][num3]){
                                                goto r_next;
                                        }
                                                 
                                        for( num4=1; num4 < search_offset; num4++){
                                                if( mem_file[num2+num4] != buffer[last_char][num3].string[num4] ){
                                                        goto r_next;
                                                }  
                                        }
                                        buffer_found++;
                                        buffer[last_char][num3].times++;
                                        //goto found;
					//goto next_member;
					if(pre_ret == 1){
						goto pre_a;
					}
					if(pre_ret == 2){
						goto pre_b;
					}
					if(pre_ret == 3){
						goto pre_c;
					}
					if(pre_ret == 4){
						goto pre_d;
					}

                                }
                                r_next:
                                num3++;
                        }
/*

			for(num3=table[num1].member[first_char][sec_char][0].times; num3>0; num3--){
				//__asm__(
				//"movups (id), %xmm0\n"
				//"movups (index.unique_id[sec_char][num3]), %xmm1\n"
				//"movups (z0), %xmm0\n"
				//"movups (z0), %xmm0\n"
				if(index.unique_id[sec_char][num3] == id){
				//if(index.unique_id[sec_char][num3] == id || index.unique_id[sec_char][num3-1] == id || index.unique_id[sec_char][num3-2] == id || index.unique_id[sec_char][num3-3] == id){
					goto search;
				}

			}
			//for(num3=table[num1].member[first_char][sec_char][0].times; num3>0; num3--){
			//while(num3>0){
			//	if(index.unique_id[sec_char][num3] == id){
			//		goto search;
			//	}
			//	num3--;
			//}

			goto no_search;
*/
			//num6=num2+member_length-1;
			//b_char = (unsigned char)mem_file[num6];
			//id = first_char*4294967296 + sec_char*65536 + b_char*256 + last_char;

		//	if(!index.index[sec_char][last_char]){
		//		goto no_search;
		//	}

			//search cached xMB worth of most often found patterns
			//search:
			num3=0; 
			
			while(num3<c_members){
				if(!common_open[last_char][num3]){
					//if(last_char != (unsigned char)index.common[sec_char][num3].string[member_length]){
					if(id != common_id[last_char][num3]){
						goto o_next;
					}
					for( num4=1; num4 < search_offset; num4++){
						if( mem_file[num2+num4] != common[last_char][num3].string[num4] ){
							goto o_next;						
						}
					}
					cache_found++;
					common[last_char][num3].times++;
					//goto found;
					//goto next_member;
                                        if(pre_ret == 1){
                                                goto pre_a;
                                        }
                                        if(pre_ret == 2){
                                                goto pre_b;
                                        }
                                        if(pre_ret == 3){
                                                goto pre_c;
                                        }
                                        if(pre_ret == 4){
                                                goto pre_d;
                                        }

				}
				o_next:
				num3++;
			}

/*
			num3=0;
			//search cached xMB worth of most recent found patterns
			while(num3<b_members){
				if(!index.buffer[sec_char][num3].open){
					//if(last_char != (unsigned char)index.buffer[sec_char][num3].string[member_length]){
					if(id != index.buffer[sec_char][num3].unique_id){
						goto r_next;
					}
					
					for( num4=2; num4 < search_offset; num4++){
						if( mem_file[num2+num4] != index.buffer[sec_char][num3].string[num4] ){
							goto r_next;
						}
					}
					buffer_found++;
					index.buffer[sec_char][num3].times++;
					goto found;
				}
				r_next:
				num3++;
			}
*/

			//search:
			num5 = table[num1].member[first_char][last_char][0].times;
			//num6 = num2+member_length-1;
			num3 = num5;

			//prefetch_id = num5 % 4;
			//prefetch_id = floor(num3 / 4);
			//while(num3>0){
			//for(num3=num5; num3>1; num3-=2){
			//while(num3>3){
			//for(num3=1; num3+3<num5; prefetch_id=num3){
			//while(prefetch_id > 0){
			//for(prefetch_id = floor(num5 / 4); prefetch_id > 0; prefetch_id--){
			while(num3>3){
				if(unique_id[last_char][num3] == id){
					//if(prefetch_id_b[0]){
					num6=0;
					//num3=prefetch_id;
					//prefetch_id_b[0]=0;					
					goto id_match;
				}
				next1:
				num3--;				
				if(unique_id[last_char][num3-1] == id){
					//if(prefetch_id_b[1]){
					num6=1;
					//num3=prefetch_id+1;
					goto id_match;
				}
				next2:
				num3--;
				if(unique_id[last_char][num3-2] == id){
					//if(prefetch_id_b[2]){
					num6=2;
					//num3=prefetch_id+2;
					goto id_match;
				}
				next3:
				num3--;
				if(unique_id[last_char][num3-3] == id){
					//if(prefetch_id_b[3]){
					num6=3;
					//num3=prefetch_id+3;
					goto id_match;
				}
				next4:
				num3--;
				//prefetch_id--;
			}

			//prefetch_id = num5 % 4;
			num6=4;
			while(num3>0){
				//while(num3<num5+1){
					if(unique_id[last_char][num3] == id){
						//num6=4;
						goto id_match;
					}
					next5:
					num3--;
				//}
			}

			table_miss++;
			goto no_search;

			id_match:
			num4=1;
				while(num4<search_offset){
					if( mem_file[num2+num4] != table[num1].member[first_char][last_char][num3].series[num4]){
						if(num6 == 0){
							goto next1;
						}
						//goto next2;

						if(num6 == 1){
							goto next2;
						}
						if(num6 == 2){
							goto next3;
						}
						if(num6 == 3){
							goto next4;
						}
						goto next5;

					}
					num4++;
				}

				//match_found:
				table[num1].member[first_char][last_char][num3].times++;
					
				if(table[num1].member[first_char][last_char][num3].times > table[num1].highest_times){
					table[num1].highest_times=table[num1].member[first_char][last_char][num3].times;
				}

				for(num4=com_count[last_char]; num4<c_members; num4++){
					if(table[num1].member[first_char][last_char][num3].times>common[last_char][num4].times){
						//contribute results to table before replacing
						if(common_open[last_char][num4] != 1){
							num6 = common[last_char][num4].sub;
							table[num1].member[first_char][last_char][num6].times=common[last_char][num4].times;
							if(table[num1].member[first_char][last_char][num6].times > table[num1].highest_times){
								table[num1].highest_times=table[num1].member[first_char][last_char][num6].times;
							}
						}
						//write new results to common index
						common_open[last_char][num4]=0;
						common[last_char][num4].times=table[num1].member[first_char][last_char][num3].times;

						common_id[last_char][num4]=unique_id[last_char][num3];
						//ndex.common[sec_char][num4].unique_id=table[num1].member[first_char][sec_char][num3].unique_id;
						common[last_char][num4].sub=num3;
						for(num6=0; num6<member_length+1; num6++){
							common[last_char][num4].string[num6]=table[num1].member[first_char][last_char][num3].series[num6];
						}
						if(com_count[last_char] == c_members-1){
							com_count[last_char] = 0;
						}else{
							com_count[last_char]++;
						}
						table_found++;
						//goto found;
						//goto next_member;
                                        	if(pre_ret == 1){
                                                	goto pre_a;
                                        	}
                                        	if(pre_ret == 2){
                                                	goto pre_b;
                                        	}
                                        	if(pre_ret == 3){
                                                	goto pre_c;
                                        	}
                                        	if(pre_ret == 4){
                                                	goto pre_d;
                                        	}

					}
				}						
				table_found++;
				//goto found;
				//goto next_member;
                                        if(pre_ret == 1){
                                                goto pre_a;
                                        }
                                        if(pre_ret == 2){
                                                goto pre_b;
                                        }
                                        if(pre_ret == 3){
                                                goto pre_c;
                                        }
                                        if(pre_ret == 4){
                                                goto pre_d;
                                        }
		

			no_search:
			;
			if(buf_members[last_char]<b_members){				
				for(num3=0; num3<member_length+1; num3++){
					buffer[last_char][ buf_count[last_char] ].string[num3]=mem_file[num2+num3];
				}
				buffer[last_char][ buf_count[last_char] ].series=&mem_file[num2];
				buffer_id[last_char][ buf_count[last_char] ] = id;
				buffer[last_char][ buf_count[last_char] ].times = 1;
				buffer_open[last_char][buf_count[last_char]]=0;
				//index[0][sec_char][last_char]=1;
				if(member_length>5){
					index[sec_char*256+last_char]=1;
					index[65536+a_char*256+b_char]=1;
				}else{
					index[sec_char*256+last_char]=1;
				}
				
//index.unique_id[sec_char][ num3 ]=id;
				buf_count[last_char]++;
				buf_members[last_char]++;
			}else{
				//take 4 oldest out of buffer and place into table
				//dealing with sets of 4
				if(buf_count[last_char] == b_members){
					buf_count[last_char] = 0;
				}

				for(num3=buf_count[last_char]; num3<buf_count[last_char]+4; num3++){

					num5 = table[num1].member[first_char][last_char][0].times;
					if(sizes[first_char][last_char] == num5){
						table[num1].member[first_char][last_char]=realloc(table[num1].member[first_char][last_char],sizeof(struct translation_structure) * (sizes[first_char][last_char]+1+3) );
		//index.unique_id[sec_char]=realloc(index.unique_id[sec_char], sizeof(unsigned int) * (table[num1]sizes[first_char][sec_char]+1+3) );
						sizes[first_char][last_char]+=3;

					}
					
					table[num1].member[first_char][last_char][num5+1].series = buffer[last_char][num3].series;
					table[num1].member[first_char][last_char][num5+1].times = buffer[last_char][num3].times;
					//table[num1].member[first_char][sec_char][num5+1].unique_id = buffer[sec_char][num3].unique_id;
					if( num5 == unique_id[last_char][0]){
						//unique_id[last_char] = memalign (16, sizeof(unsigned int)*(unique_id[last_char][0]+6));
						unique_id[last_char]=realloc(unique_id[last_char], sizeof(unsigned int)*(unique_id[last_char][0]+4) );
						unique_id[last_char][0]+=3;
					}

					unique_id[last_char][ num5+1 ] = buffer_id[last_char][num3];
					//index.unique_id[sec_char][0] = 1000;
					table[num1].member[first_char][last_char][0].times++;
					buffer_open[last_char][num3]=1;
				}

				//put current pattern into buffer
				for(num3=0; num3<member_length+1; num3++){
					buffer[last_char][buf_count[last_char]].string[num3]=mem_file[num2+num3];
				}
				buffer[last_char][buf_count[last_char]].series=&mem_file[num2];
				buffer_id[last_char][buf_count[last_char]] = id;
				buffer[last_char][buf_count[last_char]].times = 1;
				buffer_open[last_char][buf_count[last_char]]=0;
				//index[0][last_char][last_char]=1;
				if(member_length>5){
					index[sec_char*256+last_char]=1;
					index[65536+a_char*256+b_char]=1;
				}else{
					index[sec_char*256+last_char]=1;
				}
				buf_count[last_char]++;
				buf_members[last_char]-=3;
			}
			found:
			num2=pre_int+pre_count;
			//num2=pre_int+4096;
			//num2+=4;
			//num2+=member_length+1;
		}
		first_char = num7;
		//save all needed index info to tables before reset
		for(num3=0; num3<256; num3++){
			//table[num1].member[num6][sec_char]=realloc(table[num1].member[num6][sec_char], sizeof(struct translation_
			for(num6=0; num6<b_members; num6++){
				
				if(!buffer_open[num3][num6]){
					num5 = table[num1].member[first_char][num3][0].times;
					if(sizes[first_char][num3] == num5){					
						table[num1].member[first_char][num3]=realloc(table[num1].member[first_char][num3], sizeof(struct translation_structure) * (sizes[first_char][num3]+1+3) );
						sizes[first_char][num3]+=3;
					}
					table[num1].member[first_char][num3][0].times++;
					table[num1].member[first_char][num3][num5+1].series=buffer[num3][num6].series;
					table[num1].member[first_char][num3][num5+1].times=buffer[num3][num6].times;
					if(table[num1].member[first_char][num3][num5+1].times > table[num1].highest_times){
						table[num1].highest_times=table[num1].member[first_char][num3][num5+1].times;
					}
				}
			}

			for(num4=0; num4<c_members; num4++){
				if(!common_open[num3][num4]){
					num6 = common[num3][num4].sub;
					table[num1].member[first_char][num3][num6].times=common[num3][num4].times;
					if(table[num1].member[first_char][num3][num6].times > table[num1].highest_times){
						table[num1].highest_times=table[num1].member[first_char][num3][num6].times;
					}
				}
			}
//printf("num1: %d ht: %u\n", num1, table[num1].highest_times);
		}

//printf("here 2\n");
	}
	//free all strings that don't meet min frequency to save memory later
	for(num2=0; num2<256; num2++){
		for(num3=0; num3<256; num3++){
			num5=table[num1].member[num2][num3][0].times+1;
			num6=0;
			for(num4=0; num4<num5; num4++){
				if(table[num1].member[num2][num3][num4].times>frequency-1){
					num6=1;
				}
			}
			if(num6 == 0){
					//free(table[num1].member[num2][num3][num4].series);
				free(table[num1].member[num2][num3]);				
				table[num1].member[num2][num3]=malloc(sizeof(struct empty));
				//patterns_total+=(table[num1].sizes[num2][num3]+1)*(sizeof(struct translation_structure)-sizeof(struct empty));
				table[num1].member[num2][num3][0].times=0;
				empties++;
				patterns_freed+=(sizes[num2][num3]+1);
					//patterns_total++;
				//}
			}else{
				num7=1;
				temp_struct_array = malloc(sizeof(struct translation_structure)*num5 );
				//patterns_total+=sizeof(struct translation_structure)-sizeof(struct empty);
				temp_struct_array[0].times = table[num1].member[num2][num3][0].times;
				for(num4=1; num4<num5; num4++){
					//only way is to shift/reorganize all members, costly
					if(table[num1].member[num2][num3][num4].times>frequency-1){
						memcpy(&temp_struct_array[num7], &table[num1].member[num2][num3][num4], sizeof(struct translation_structure));
						num7++;
						//table[num1].member[num2][num3][num4]=realloc(table[num1].member[num2][num3][num4], sizeof(struct empty));
						//table[num1].member[num2][num3][num4].times=0;
					}else{
						temp_struct_array[0].times--;
						patterns_freed++;
						//patterns_total+=sizeof(struct translation_structure);
					}
				}
				
				//patterns_total+=sizeof(struct translation_structure)*num7;
				free(table[num1].member[num2][num3]);
				table[num1].member[num2][num3]=malloc(sizeof(struct translation_structure)*num7 );
				memcpy(table[num1].member[num2][num3], temp_struct_array, sizeof(struct translation_structure)*num7 );	
				//table[num1].member[num2][num3]=realloc(temp_struct_array, sizeof(struct translation_structure)*num7 );
				//for(num4=0; num4<num7; num4++){
				//memcpy(table[num1].member[num2][num3], temp_struct_array, sizeof(struct translation_structure)*num7);	
			}
		}
	}



	progress_func(0, member_length+1);
	//printf("\tfreed: %.04lfMB low freq patterns\n", (double)patterns_total/1024/1024 );
	//num4=0;
	//for(num3=0; num3<256; num3++){
	//	num4 += index.unique_id[num3][0]+1;
	//}	
	//printf("\tunique_id cache: %u(%.02lfKB)\n", num4, (double)sizeof(unsigned long)*num4/1024);
		//24 20
	printf("\tbuffer/cache sizes\n");
	if(member_length>5){
		num3=2;
	}else{
		num3=1;
	}

	printf("\t\trecent: %u(%.02lfKB) common: %u(%.02lfKB) index: %.02lfKB\n",b_members, cache_sizes[0]/1024, c_members, cache_sizes[1]/1024, (double)sizeof(char)*256*256*num3/1024); 

//(double)256*(sizeof()*b_members/1024, c_members, (double)256*(20+member_length+1)*c_members/1024);

	patterns_total = table_found + buffer_found + cache_found + table_miss;
	printf("\ttotal patterns found: %u\n", patterns_total-table_miss);
	printf("\ttable_miss: %u table_found: %u recent_found: %u common_found: %u\n", table_miss, table_found, buffer_found, cache_found);
	printf("\ttable_miss: %.02lf%% table_found: %.02lf%% recent_found: %.02lf%% common_found: %.02lf%%\n", (double)table_miss/patterns_total*100, (double)table_found/patterns_total*100, (double)buffer_found/patterns_total*100, (double)cache_found/patterns_total*100); 

	printf("\tfreed: %u (%.04lfMB) low freq pattern structures\n", patterns_freed-empties, (double)(patterns_freed*sizeof(struct translation_structure)-empties)/1024/1024);
	pthread_exit(0);
}

void usage(void){
        printf("\tUsage: patterns <output> <input> <min pattern size (bytes)> <max pattern size (bytes)> <threads>\n");
        exit(1);
}


int main(int argc, char **argv){
        FILE *output;
	int input;
        //FILE *input;
        struct stat buffer;
        int status;
        int pat_size;
        int num1, num2, num3, num4, num5;
        int progress=0;
	double progress2=0;
        int max_searchs=0;
        int max_pat;
        int half_file;
        frequency=4;
	int thread_count;
	struct timeval starttime,endtime;
	double time1;

        if(argc != 6){
                usage();
        }

	//frequency = atoi(argv[5]);
	//frequency = 4;
	thread_count = atoi(argv[5]);
        pat_size = atoi(argv[3]);
        max_pat = atoi(argv[4]);
	//input = fopen(argv[2], "r");
        input = open(argv[2], O_RDONLY);
        if(input == -1){
	//if(input == NULL){
                fprintf( stderr, "Error opening %s\n", argv[2] );
                exit( 1 );
        }
	
        status = fstat(input, &buffer);
	//status = stat(argv[2], &buffer);
        file_bytes=buffer.st_size;

/*
	mem_file=malloc(file_bytes);
	for(num1=0; num1<file_bytes; num1++){
		mem_file[num1]=getc(input);
	}
        //character=getc(input);
        //while(character != EOF){  
*/


        mem_file=(char *)mmap(0, file_bytes, PROT_READ, MAP_SHARED, input, 0);
        if (mem_file == MAP_FAILED) {
                close(input);
                perror("Error mmapping the file");
                exit(EXIT_FAILURE);
        }


        if( ( output = fopen( argv[1], "w" ) ) == NULL ) {
                fprintf( stderr, "Error opening %s\n", argv[1] );
                exit( 1 );
        }

        printf("input: %s\n", argv[2]);
        printf("output: %s\n", argv[1]);
        printf("pat_size: %d\n", pat_size);
        printf("bytes: %d\n", file_bytes);
        if(max_pat > file_bytes/2){
                max_pat = floor(file_bytes/2);
                printf("max_pat: %d (reduced to limit!)\n", max_pat);
        }else{
                printf("max_pat: %d\n", max_pat);
        }



        half_file = sizeof(unsigned char)*ceil(file_bytes/2);

        for(num1=pat_size; num1<max_pat; num1++){
                max_searchs++;
        }

	max_searchs++;
        printf("max_searchs: %d\n", max_searchs);
        printf("frequency: %d\n", frequency);
	printf("threads: %d\n", thread_count);

	//pat_index=(struct one_index *)malloc( sizeof(struct one_index) * max_searchs);
	//table=(struct pat_length *)malloc( sizeof(struct pat_length) * max_searchs);
	pthread_t *threads = (pthread_t *)malloc(sizeof(pthread_t) * max_searchs);


	table=(struct pat_length *)malloc( sizeof(struct pat_length) * max_searchs);


	for(num1=0; num1<max_searchs; num1++){
		table[num1].member=malloc( 256*sizeof(void *) );
		for(num2=0; num2<256 ; num2++){
                        table[num1].member[num2]=malloc( 256*sizeof(void *) );
			//for(num5=0; num5<256; num5++){
				//table[num1].member[num2][num5]=malloc( 256*sizeof(void *) );
				for(num3=0; num3<256; num3++){
					//table[num1].index[num2][num3]=0;
					//table[num1].index2[num2][num3]=0;
				//	table[num1].sizes[num2][num3]=1;
					table[num1].member[num2][num3]=malloc( 2*sizeof(struct translation_structure) );
					table[num1].member[num2][num3][0].times=0;
					//table[num1].member[num2][num3][1].unique_id=1;
					//table[num1].member[num2][num3][1].unique_id=-1;
				}
			
                }
        }

/*
	for(num1=0; num1<max_searchs; num1++){
		for(num5=0; num5<256; num5++){
			for(num2=0; num2<256; num2++){
				//table[num1].index2[num5][num2]=1;
				for(num3=0; num3<256; num3++){
					table[num1].index[num5][num2][num3]=0;
				}
			}
		}
	}
*/

//////////////////////////////////


	progress=0;
	progress2=0;

	progress_func(max_searchs, 0);

	gettimeofday(&starttime, NULL);
	num2=1;
	for(num1=0; num1<max_searchs; num1++){
		table[num1].len=pat_size+num1;		
		table[num1].search_num=num1;
		table[num1].highest_times=0;

               	if (pthread_create(&threads[num1], NULL, match_search, &table[num1].search_num) != 0)
                       	perror("pthread_create"), exit(1);
		
		
		if(num2 % thread_count == 0 || num2 == max_searchs){
			for(num3=progress; num3<num2; num3++){
				if (pthread_join(threads[num3], NULL) != 0)
					perror("pthread_join"),exit(1);
			}
			progress=num2;
		}
		num2++;
	}
	gettimeofday(&endtime, NULL);
	time1=((double)(endtime.tv_sec*1000000-starttime.tv_sec*1000000+endtime.tv_usec-starttime.tv_usec))/1000000;
	printf("time: %.02lfs\n", time1);
	printf("generating output file...\n");

	gettimeofday(&starttime, NULL);

        //parse structures and write to output

	int next_highest=0;
	int index1=0;
	int index2=0;
	int max_print=0;
	int num6;
	//int hi_tbl=0;
	//int hi_in1=0;
	//int hi_in2=0;
        struct sort_structure *sort_index;
	sort_index = malloc(max_searchs*sizeof(struct sort_structure));
printf("here 1\n");
	//initialize sort_index to all 0's
	for(num5=0; num5<max_searchs; num5++){
		//sort_index[num5].indice[0]=0;
		//sort_index[num5].indice[1]=0;
		sort_index[num5].highest=0;
		for(num6=0; num6<256; num6++){
			for(index1=0; index1<256; index1++){
				sort_index[num5].sub_highest[num6][index1]=0;
			}
		}
	}
	
printf("here 2\n");
	//search tables for the one containing the highest count
	num2=0;
	for(num1=0; num1<max_searchs; num1++){
		//find highest member count
		sort_index[num1].highest=table[num1].highest_times;
		if(sort_index[num1].highest > num2){
			num2=sort_index[num1].highest;
			//hi_tbl = num1;

		}
	}
printf("here 3\n");

	//search tables for highest in all sets and save to sort_index
	for(num1=max_searchs-1; num1>-1; num1--){
		for(index1=0; index1<256; index1++){
			for(index2=0; index2<256; index2++){
				num5=table[num1].member[index1][index2][0].times+1;
				for(num4=1; num4<num5; num4++){
					if(table[num1].member[index1][index2][num4].times > sort_index[num1].sub_highest[index1][index2]){
						//sort_index[num1].times[index1][index2]=table[num1].member[index1][index2][num4].times;
						sort_index[num1].sub_highest[index1][index2]=table[num1].member[index1][index2][num4].times;
						//if(num1 == hi_tbl){
						//	hi_in1=index1;
						//	hi_in2=index2;
						//}
						//if(sort_index[num1].sub_highest[index1][index2]>sort_index[num1].highest){
						//	sort_index[num1].highest=sort_index[num1].sub_highest[index1][index2];
							//sort_index[num1].indice[0]=index1;
							//sort_index[num1].indice[1]=index2;
						//}

					}
				}
			}
		}
	}

/*
printf("here 4\n");
	//prime search
	next_highest=0;  
	for(num1=max_searchs-1; num1>-1; num1--){
		if(sort_index[num1].highest>next_highest){
			next_highest=sort_index[num1].highest;
			//hi_tbl=num1;
			//hi_in1=sort_index[num1].indice[0];
			//hi_in2=sort_index[num1].indice[1];
		}
	}
        num2=next_highest;


printf("%d\n", num2);
printf("here 5\n");
	//main search
	while(num2>=frequency){
		for(num1=max_searchs-1; num1>-1; num1--){
			if(sort_index[num1].highest_times==num2){
				//sort_index[num1].highest_times=0;
				for(index1=0; index1<256; index1++){
					if(!sort_index[num1].index1[index1]){
						for(index2=0; index2<256; index2++){
							if(!sort_index[num1].index2[index2]){
								//
								
								num5=table[num1].member[index1][index2][0].times+1;
								for(num4=1; num4<num5; num4++){
								if(table[num1].member[index1][index2][num4].times == num2){
									fprintf(output, "%d %d", table[num1].len, table[num1].member[index1][index2][num4].times);
									for(num3=0; num3<table[hi_tbl].len; num3++){
										fprintf(output, " %d", table[num1].member[index1][index2][num4].series[num3]);
									}
									fprintf(output, "\n");
									max_print++;
									if(max_print == 40000){
										goto complete;
									}
								}else if(table[num1].member[index1][index2][num4].times < num2){
									if(table[num1].member[index1][index2][num4].times > next_highest){
										next_highest=table[num1].member[index1][index2][num4].times;
										sort_index[num1].index2[index2]=1;
									}
								}
							}else if(
									
							}
					}else if(

					}
				}
			}else if(
			
			}
		}
	}
				hi_tbl=num1;
				//hi_in1=sort_index[num1].indice[0];
				//hi_in2=sort_index[num1].indice[1];
				hi_in1=index1;
				hi_in2=index2;

				sort_index[hi_tbl].times[hi_in1][hi_in2]=0;
				num5=table[hi_tbl].member[hi_in1][hi_in2][0].times+1;

				sort_index[hi_tbl].next_highest=0;		
				//next_highest=0;

				for(num4=1; num4<num5; num4++){
					
					if(table[hi_tbl].member[hi_in1][hi_in2][num4].times == num2){
						fprintf(output, "%d %d", table[hi_tbl].len, table[hi_tbl].member[hi_in1][hi_in2][num4].times);
						for(num3=0; num3<table[hi_tbl].len; num3++){
							fprintf(output, " %d", table[hi_tbl].member[hi_in1][hi_in2][num4].series[num3]);
						}
						fprintf(output, "\n");
						max_print++;
						if(max_print == 40000){
							goto complete;
						}
					}else if(table[hi_tbl].member[hi_in1][hi_in2][num4].times < num2){
						if(table[hi_tbl].member[hi_in1][hi_in2][num4].times > sort_index[hi_tbl].times[hi_in1][hi_in2]){
							sort_index[hi_tbl].times[hi_in1][hi_in2] = table[hi_tbl].member[hi_in1][hi_in2][num4].times;
							if(sort_index[hi_tbl].times[hi_in1][hi_in2]>sort_index[hi_tbl].next_highest){
								sort_index[hi_tbl].highest=sort_index[hi_tbl].times[hi_in1][hi_in2];
								sort_index[hi_tbl].indice[0]=hi_in1;
								sort_index[hi_tbl].indice[1]=hi_in2;
							}
						}
					}
				}
			}
		}

		next_highest=0;
		for(num1=max_searchs-1; num1>-1; num1--){
			if(sort_index[num1].highest>next_highest){
				next_highest=sort_index[num1].highest;
				//hi_tbl=num1;
				//hi_in1=sort_index[num1].indice[0];
				//hi_in2=sort_index[num1].indice[1];
			}
		}
		num2=next_highest;
		//num2=sort_index[hi_tbl].times[hi_in1][hi_in2];
	}
*/
printf("here 6\n");


	while(num2>=frequency){
		for(num1=max_searchs-1; num1>-1; num1--){
			if(sort_index[num1].highest == num2){
				sort_index[num1].highest = 0;
				//table[num1].highest_times = 0;
				for(index1=0; index1<256; index1++){
					for(index2=0; index2<256; index2++){
						
						
						if(sort_index[num1].sub_highest[index1][index2] == num2){
							sort_index[num1].sub_highest[index1][index2]=0;

							num5=table[num1].member[index1][index2][0].times+1;
							//num2=table[num1].highest_times[index1][index2] == num2){
		
							for(num4=1; num4<num5; num4++){
								if(table[num1].member[index1][index2][num4].times == num2){			
									fprintf(output, "%d %d", table[num1].len, table[num1].member[index1][index2][num4].times);
                        						for(num3=0; num3<table[num1].len; num3++){
                        							fprintf(output, " %d", table[num1].member[index1][index2][num4].series[num3]);
                        						}
									fprintf(output, "\n");
									max_print++;
									if(max_print == 40000){
										goto complete;
									}
                        					}else if(table[num1].member[index1][index2][num4].times < num2){
									if(table[num1].member[index1][index2][num4].times > sort_index[num1].sub_highest[index1][index2]){
										sort_index[num1].sub_highest[index1][index2] = table[num1].member[index1][index2][num4].times;
									}
								}
							}
							//
						}
						if(sort_index[num1].sub_highest[index1][index2] > sort_index[num1].highest){
							sort_index[num1].highest=sort_index[num1].sub_highest[index1][index2];
						}
						//set sort_index[num1].highest to greatest sort_index[num1].sub_highest[index1][index2]

					}
				}
			// 
			}
		}
		
		


		num2=0;
		for(num6=0; num6<max_searchs; num6++){
			//find highest member count
			if(sort_index[num6].highest > num2){
				num2=sort_index[num6].highest;
			}
		}
		//num2 = next_highest;
		//next_highest = 0;
        }


	complete:
	;

	gettimeofday(&endtime, NULL);
	time1=((double)(endtime.tv_sec*1000000-starttime.tv_sec*1000000+endtime.tv_usec-starttime.tv_usec))/1000000;
	printf("time: %.02lfs\n", time1);

        if (munmap(mem_file, file_bytes) == -1) {
                perror("Error un-mmapping the file");
        }

	//free(mem_file);
        close(input);

        fclose(output);
	printf("done.\n");
        return 0;
}