#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <unistd.h>
#include <pthread.h>

#define MAX( a, b ) ( a > b ? a : b )
#define MIN( a, b ) ( a < b ? a : b )

#define MAXTHREAD 8
#define NUMTHREAD 2
#define BLOCK 1024

/* 檔案內容的指標 */
char *s1, *s2, *s3;

/* 儲存部份結果的陣列 */
int *left[MAXTHREAD], *top[MAXTHREAD], *right[MAXTHREAD], *buttom[MAXTHREAD];

/* 區塊大小 */
int block1, block2;

/* 讀入檔案，將傳入的指標指向內容，傳回檔案長度 */
int readfile( char *filename, char **s )
{
	int fd;
	ssize_t len;
	off_t size;
	struct stat st;

	/* 這種情況下應該用 non-buffer 的 open, read 會比較快 */
	fd = open( filename, O_RDONLY );
	fstat( fd, &st );
	size = st.st_size;
	*s = (char *)malloc(size);
	len = read( fd, *s, size );

	/*
	fprintf( stderr, "file size: %u\nread: %d\n", size, len );
	*/

	return size;
}

/* 一般化的 LCS, 可由上方及左方傳入計算所需的部份結果 */
/* lcs(...) 會從 top[order], left[order] 取得上方與左方的計算結果 */
int lcs( int order, char *ss1, char *ss2, int len1, int len2 )
{
	int i, j, result;
	int lastindex, currindex;
	int *buf[2];

	/* 初始化暫存用的陣列 */
	buf[0] = (int *)malloc( block2 * sizeof(int) );
	buf[1] = (int *)malloc( block2 * sizeof(int) );

	/* 將傳來的資料抄到該去的地方 */
	for(i = 0; i < len2; i++) {
		buf[1][i] = top[order][i];
	}

	for( i = 0; i < len1; i++) {

		/* 每次只 allocate 兩行紀錄內容 */
		lastindex = (i & 1) ^ 1;
		currindex = (i & 1) ^ 0;

		/* 將第一 column 獨立出來處理，節省判斷次數 */
		if( ss1[i] == ss2[0] ) {
			if( i == 0 ) {
				buf[currindex][0] = 1;
			} else {
				buf[currindex][0] = left[order][i - 1] + 1;
			}
		} else {
			buf[currindex][0] = MAX( left[order][i], buf[lastindex][0]);
		}

		/* 標準的 lcs 計算 */
		for( j = 1; j < len2; j++) {
			if( ss1[i] == ss2[j] ) {
				buf[currindex][j] = buf[lastindex][j - 1] + 1;
			} else {
				buf[currindex][j] = MAX( buf[currindex][j - 1], buf[lastindex][j] );
			}
		}

		/* 要傳給右邊的 */
		right[order][i] = buf[currindex][len2 - 1];
	}

	/* 要傳給下面的 */
	for( j = 0; j < len2; j++ ) {
		buttom[order][j] = buf[currindex][j];
	}

	result = buf[currindex][len2 - 1];

	/* 釋放暫存用的陣列 */
	free(buf[0]);
	free(buf[1]);

	return result;
}

/* thread(...) 只負責計算參數以及啟動 lcs(...) */
void* thread(void *arg)
{
	int order;
	int i, j, blen1, blen2;
	int result;

	order = ((int*)arg)[0];
	i = ((int*)arg)[1];
	j = ((int*)arg)[2];
	blen1 = ((int*)arg)[3];
	blen2 = ((int*)arg)[4];

	/* 計算部份的 LCS */
	result = lcs( order, s1 + i * block1, s2 + j * block2, blen1, blen2 );
	/*
	printf("%d, %d -> %d\n", i, j, result);
	*/

	/* lcs(...) 會修改全域變數 right, buttom 因此不需要傳回值 */
	return NULL;
}

int myceil( int x, int y )
{
	int r = x / y;
	if( y * r == x ) {
		return r;
	}
	return r + 1;
}

int main( int argc, char *argv[])
{
	int tasks;
	int len1, len2, len3, blen1, blen2;
	int i, j, k, ii, jj, m, n, time;

	int run[MAXTHREAD];
	int para[MAXTHREAD][5];
	pthread_t threads[MAXTHREAD];

	/* 預設使用 2 個 thread */
	tasks = NUMTHREAD;

	/* len1 為第一個檔的長度，s1 則為內容 */
	len1 = readfile( argv[1], &s1 );
	len2 = readfile( argv[2], &s2 );

	/* 保證 s1 一定比 s2 短 */
	if( len2 < len1 ) {
		len3 = len1;
		s3 = s1;
		len1 = len2;
		s1 = s2;
		len2 = len3;
		s2 = s3;
	}

	/* row 數等於 thread 數 */
	m = tasks;
	block1 = myceil( len1, m);

	/* 每 BLOCK 切一個 column, 並保證 column 一定比 row 多 */
	n = myceil( len2, BLOCK);
	if( n < m ) {
		n = m;
		block2 = myceil( len2, n);
	} else {
		block2 = BLOCK;
	}

	/* 初始化每個 thread 需要的空間 */
	for( i = 0; i < tasks; i++) {
		left[i] = (int *)malloc( block1 * sizeof(int) );
		right[i] = (int *)malloc(block1 * sizeof(int) );
		top[i] = (int *)malloc( block2 * sizeof(int) );
		buttom[i] = (int *)malloc( block2 * sizeof(int) );
		run[i] = 0;
	}

	/* 斜切的座標，執行右上左下斜切的執行順序 */
	for( j = time = 0; j < m + n - 1; j++, time++) {
		/*
		printf("Begin time %d\n", time);
		*/
		for( i = 0;; i++) {

			/* 算出真正的座標 */
			if( j < n ) {
				ii = i;
				jj = j - i;
			} else {
				ii = j - n + 1 + i;
				jj = n -1 - i;
			}

			/* 到不合法的位置了，跳至下一單位時間 */
			if( jj < 0 || ii >= m ) {
				break;
			}

			/*
			fprintf( stderr, "calculating %d, %d\n", ii, jj );
			*/

			/* 算出待計算區域的 dimension */
			if( ii != m - 1 ) {
				blen1 = block1;
			} else {
				blen1 = len1 - ii * block1;
			}

			if( jj != n - 1 ) {
				blen2 =  block2;
			} else {
				blen2 = len2 - jj * block2;
			}

			/* 第一行與第一列初始化為 0, 其餘複製之前的結果 */
			if( ii == 0 ) {
				bzero( top[ii], blen2 * sizeof(int) );
			} else {
				for( k = 0; k < blen2; k++ ) {
					top[ii][k] = buttom[ii - 1][k];
				}
			}

			if( jj == 0 ) {
				bzero( left[ii], blen1 * sizeof(int) );
			} else {
				for( k = 0; k < blen1; k++) {
					left[ii][k] = right[ii][k];
				}
			}

			/* 設定傳給 thread 的參數 */
			para[ii][0] = ii;
			para[ii][1] = ii;
			para[ii][2] = jj;
			para[ii][3] = blen1;
			para[ii][4] = blen2;

			/* 紀錄 thread 正在執行中 */
			run[ii] = 1;

			/* 啟動 thread */
			pthread_create( &threads[ii], NULL, thread, (void*)para[ii] );
		}

		for( i = 0; i < tasks; i++) {
			/* 等待執行中的 thread 結束 */
			if( run[i] ) {
				pthread_join( threads[i], NULL );
				run[i] = 0;
			}
		}

		/*
		printf("End time %d\n", time);
		*/
	}

	/* 印出答案 */
	printf( "Answer: %d\n", buttom[tasks - 1][blen2 - 1] );

	/* 釋放每個 thread 暫存結果的空間 */
	for( i = 0; i < tasks; i++) {
		free(left[i]);
		free(right[i]);
		free(top[i]);
		free(buttom[i]);
	}

	return 0;
}