/*----------Morton ordering---------------------------------
*Transposition
*aim:
*	矩陣向左旋轉90度.
*function:
*	Block_Roate32: 小塊矩陣旋轉
*	trc:	劃分函數
*
*parameter:
*	WIDTH: 圖像寬度
*	HEIGHT:圖像高度
*	BLOCK_W:塊的寬度
*	BLOCK_H:塊的高度
*	BLOCK_NUM:塊的劃分,分四塊時 BLOCK_NUM = 4, 
*						分16塊時 BLOCK_NUM = 8，分32塊時 BLOCK_NUM = 8，
*
*arithmetic advantage:
* 能過充利用cache的臨近訪問優勢，提高cache的命中率
*
*note:
*	1:圖像寬度和高度必須為4的倍數
*	2:函數只處理16色的圖像，垂直分辨71*71
*	3:源圖像內存和目標內存不應當是同一個內存塊]
*	4:劃分的塊的大小也必須是4的倍數
*
*time: 2005-12-23 整理
*author: fred-liu@qq.com
*-------------------------------------------------------*/
//PIC 352*288
#define BLOCK_NUM 8 //劃分成八部分，共 4*4塊 

#define WIDTH		352
#define HEIGHT 	288

#define BLOCK_W 72	// 352/8
#define BLOCK_H 88	// 288/8

/*
*塊轉換函數1
*pack16lsb:兩個低16位轉換成一個整數
*pack16msb:兩個高16位轉換成一個整數
*4字節轉換
*/
void Block_Roate32(unsigned int * restrict image_in, 
 								 unsigned int * restrict  image_out,
 								 int width,
 								 int height,
 								 int block_w,
 								 int block_h)
{
		int	m,n;
			for( m =0; m<(block_h>>1); m ++){	 	 
				for( n =0; n<(block_w>>1); n ++){		
							
					image_out[(block_h>>1)-1 - m + n*height] = 
						pack16lsb(image_in[n + m*width],image_in[n + m*width +(width>>1)]);
					
					image_out[(block_h>>1)-1 - m + (height>>1) + n*height] = 
						pack16msb(image_in[n + m*width],image_in[n + m*width +(width>>1)]);	
			}
		}
}

/*
*塊轉換函數2
*對每個像素進行轉換
*雙字節轉換
*/
void block_trans16(unsigned short int* restrict matrix_in, 
				 unsigned short int* restrict matrix_out, 
				 int width, 
				 int heigh,
				 int block_w, 
				 int block_h)

{	
	int m ;
	int n ;
	for(m =0; m < block_h; m ++){
		for(n =0; n < block_w; n ++){				
			matrix_out[block_h - m + n*heigh -1] = matrix_in[n + m*width];				
		}
	}	
}

/*
*塊轉換函數3
*對每個像素進行轉換
*單字節轉換
*/
void block_trans(unsigned char * restrict matrix_in, 
				 unsigned char * restrict matrix_out, 
				 int width, 
				 int heigh,
				 int block_w, 
				 int block_h)

{	
	int m =0;
	int n =0;
	
	for(m =0; m < block_h<<1; m +=2){				
		for(n =0; n < block_w<<1; n +=2){						

		matrix_out[(block_h<<1) - m + n*heigh-2 ] = matrix_in[n + m*width];	
		matrix_out[(block_h<<1) - m + n*heigh- 1] = matrix_in[n + m*width +1];			
	
		}
	}		
}
/*
*入口函數1
*src:源圖像
*dst:目標圖像
*n:塊劃分參數
*說明:
*			塊的劃分必須是4的倍數
*/
void trc(char unsigned *src, char unsigned *dst,int n)
{

	int nn1 = n/2;
	if(nn1 == 1)
		{//塊轉換
			Block_Roate32((unsigned int *)src,(unsigned int *)dst, WIDTH,HEIGHT,BLOCK_W,BLOCK_H);
		}	
	else
		{
		trc(&src[0], 			&dst[HEIGHT],  nn1);//3
		trc(&src[WIDTH],			&dst[HEIGHT*WIDTH + HEIGHT],  nn1);//4
		trc(&src[WIDTH*HEIGHT],		&dst[0] ,  nn1);//1
		trc(&src[WIDTH*HEIGHT+WIDTH], &dst[HEIGHT*WIDTH ]	,  nn1);		//2		
		}
}

/*
*入口函數2
*說明:
*			塊的劃分必須是4的倍數
*/
void BlockRoate32(unsigned int * restrict image_in, 
 								 unsigned int * restrict image_out,
 								 int width,
 								 int height,
 								 int block_w,
 								 int block_h)
{
	int i,j ;
	for(i =0; i<height/block_h ; i ++){
		for(j =0; j<width/block_w ; j ++){				

		Block_Roate32(&image_in[i*(width>>1)*block_h + j*(block_w>>1)],
		 	&image_out[(height>>1)-i*(block_h>>1)+ j*block_w*(height>>1) -(block_h>>1)],
		 	width,height,block_w,block_h);					
						
		}
	}
}

/*
*入口函數3
*說明:
*			塊的劃分必須是4的倍數
*/
 void BlockRoate(unsigned char * restrict image_in, 
 								 unsigned char * restrict image_out,
 								 int width,
 								 int height,
 								 int block_w,
 								 int block_h)
{
	int i;
	int j;
	for(i =0; i<height/block_h ; i ++){
		for(j =0; j<width/block_w ; j ++){
			//單字節轉換
			block_trans(&image_in[i*(width<<1)*block_h + j*(block_w<<1)], 
				&image_out[(height<<1)- i*(block_h<<1)+ j*(height<<1)*block_w - (block_h<<1)],
				width,height,block_w, block_h);									
						
		}
	}	
}

//
void main()
{
	//
	//trc(src, dst, 4) //分4塊
	//trc(src, dst, 8) //分16塊	
}