Zhu-Takaoka Two-dimensional Pattern Matching

#define REHASH(a, b, h)    (((h - a * d) << 1) + b)

void getNext(char *pattern, int n, int next[]){
	int i = 0, j = -1;
	next[i] = j;
	
	while(i < n){
		while(j >= 0 && next[i] != next[j])
			j = next[j];
		
		++i; ++j;
		next[i] = j;
	}
}

void bitsCompare(BIG_IMAGE bigImg, SMALL_IMAGE smallImg, int bigRow, int bigCol, int smallRow, int smallCol, int lastRow, int lastCol){
	// The beginning coordinate in big image.
	int i0 = lastRow - smallRow + 1;
	int j0 = lastCol - smallCol + 1;
	
	for(int i = 0; i < smallRow; ++i)
		for(int j = 0; j < smallCol; ++j)
			if(bigImg[i0 + i][j0 + j] != smallImg[i][j])
				return;
	
	// Record the position of successful match.
	OUTPUT(i0, j0);
}

void KMP_Inline(BIG_IMAGE bigImg, SMALL_IMAGE smallImg, int bigRow, int bigCol, int smallRow, int smallCol, int bigImgHashArr[], int smallImgHashArr[], int next[], int lastRow){
	int i = 0, j = 0;
	
	while(i < bigCol){
		while(j >= 0 && bigImgHashArr[i] != smallImgHashArr[j])
			j = next[j];
		
		++i; ++j
		
		// If matched with pattern, then j should be not less than smallCol
		if(j >= smallCol){
			bitsCompare(bigImg, smallImg, bigRow, bigCol, smallRow, smallCol, lastRow, i-1);
			j = next[smallCol];
		}
		
	}
}

void ZT_TwoDimMatch(BIG_IMAGE bigImg, SMALL_IMAGE smallImg, int bigRow, int bigCol, int smallRow, int smallCol){
	int bigImgHashArr[BIG_COL], smallImgHashArr[SMALL_COL], next[SMALL_COL];
	
	// Preprocessing
	// Compute first bigImg hash array
	for(int j = 0; j < bigCol; ++j){
		bigImgHashArr[j] = 0;
		for(int i = 0; i < smallRow; ++ i)
			bigImgHashArr[j] = (bigImgHashArr[j] << 1) + bigImg[i][j];	// The mod we use implicitly here is MAX_INT
	}
	
	// Compute the smallImg hash array
	for(int j = 0; j < smallCol; ++j){
		smallImgHashArr[j] = 0;
		for(int i = 0; i < smallRow; ++i)
			smallImgHashArr[j] = (smallImgHashArr[j] << 1) + smallImg[i][j];	// The mod we use implicitly here is MAX_INT
	}
	
	// Last row of one checking window
	lastRow = smallRow - 1;
	// digit of re-hash
	d = 1;
	for(int j = 1; j < smallRow; ++j)
		d <<= 1;
	
	getNext(smallImgHashArr, smallCol, next);
	
	// Searching
	while(lastRow < bigRow){
		KMP_Inline(bigImg, smallImg, bigRow, bigCol, smallRow, smallCol, bigImgHashArr, smallImgHashArr, next, lastRow);
		
		// Rehash the big hash array
		if(lastRow < bigRow - 1)
			for(int j = 0; j < bigCol; ++j)
				bigImgHashArr[j] = REHASH(bigImg[lastRow - smallRow + 1][j], bigImg[lastRow + 1][j], bigImgHashArr[j]);	// The mod we use implicitly here is MAX_INT
		
		++lastRow;
	}
	
}