8x8 배열 90도 회전 최적 알고리즘은??
글쓴이: elecguy / 작성시간: 화, 2005/08/02 - 12:04오후
안녕하세요..
소프트웨어로 8x8(bit) 배열을 90도 회전을 시킬려고하는데
가장 빠른 알고리즘은 무엇일까요???
예를 들면 다음과 같은 배열이 있습니다.
unsigned char org[8]={ 0x80, /* 0x10000000 */ 0xC0, /* 0x11000000 */ 0xE0, /* 0x11100000 */ 0xF0, /* 0x11110000 */ 0xF8, /* 0x11111000 */ 0xFC, /* 0x11111100 */ 0xFE, /* 0x11111110 */ 0xFF /* 0x11111111 */ };
아래와 같은 배열을 얻고 싶습니다.
unsigned char rot[8]; #if 0 /* wanted */ 0x80, /* 0x11111111 */ 0xC0, /* 0x11111110 */ 0xE0, /* 0x11111100 */ 0xF0, /* 0x11111000 */ 0xF8, /* 0x11110000 */ 0xFC, /* 0x11100000 */ 0xFE, /* 0x11000000 */ 0xFF /* 0x10000000 */ #endif
나름대로 해본 방법은 테이블을 사용한 것입니다.
unsigned char rtbl[256][8]= { /*row 0 1 2 3 4 5 6 7*/ {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}, /*0x00*/ {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xFF}, /*0x01*/ {0x00,0x00,0x00,0x00,0x00,0x00,0xFF,0x00}, /*0x02*/ {0x00,0x00,0x00,0x00,0x00,0x00,0xFF,0xFF}, /*0x03*/ ................., {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00}, /*0xFE*/ {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF}, /*0xFF*/ } rot[0]=(rtbl[org[0]][0]&0x01)|(rtbl[org[1]][0]&0x02)| (rtbl[org[2]][0]&0x04)|(rtbl[org[3]][0]&0x08)| (rtbl[org[4]][0]&0x10)|(rtbl[org[5]][0]&0x20)| (rtbl[org[6]][0]&0x40)|(rtbl[org[7]][0]&0x80); rot[1]=(rtbl[org[0]][1]&0x01)|(rtbl[org[1]][1]&0x02)| (rtbl[org[2]][1]&0x04)|(rtbl[org[3]][1]&0x08)| (rtbl[org[4]][1]&0x10)|(rtbl[org[5]][1]&0x20)| (rtbl[org[6]][1]&0x40)|(rtbl[org[7]][1]&0x80); ...................... rot[7]=(rtbl[org[0]][7]&0x01)|(rtbl[org[1]][7]&0x02)| (rtbl[org[2]][7]&0x04)|(rtbl[org[3]][7]&0x08)| (rtbl[org[4]][7]&0x10)|(rtbl[org[5]][7]&0x20)| (rtbl[org[6]][7]&0x40)|(rtbl[org[7]][7]&0x80);
그런데 무식하게 루프를 돌려서 하는 것과 별 속도차이가 없습니다. -.-;;
좀 더 나은 알고리듬이 있을까요?
임베디드 시스템에 쓸 것이기 때문에 테이블을 쓴다면 그 크기가
수십킬로바이트이내에 들어오면 좋겠습니다.
그럼..
Forums:
테이블이 왜 필요하죠 ?
보아하니 비트를 세로로 한줄씩 잘라서 가로로 재배치하는 것만하면 되는것 갈은데 테이블이 필요 없을것 같습니다.
그냥
이렇게 하면 재배치가 될것 같은데요.. ^^
[code:1] unsigned char mask[]
최적화는 잘 모르겠고, 루프로는..
[quote="Anonymous"][code:1] unsigned
같은 내용이지만....
마스크가 차지하는 용량을 줄일 수 있지 않을런지.... :oops:
To be or not to be.
That is the question.
조금 생각해 보고 코드 짜 봤습니다. :) 아래는 40개의 and 연산,
조금 생각해 보고 코드 짜 봤습니다. :) 아래는 40개의 and 연산, 24개의 or 연산, 24개의 shift 연산을 사용하는 알고리즘입니다.
pass 1에서는 8x8을 4x4 조각으로 나눠서 돌리고,
pass 2에서는 각각의 4x4 조각을 다시 2x2 조각으로 나눠서 각각 돌리고,
pass 3에서는 그 2x2 조각을 다시 1x1 조각으로 나눠서 각각 돌립니다.
간단한 분할 정복 알고리즘으로, 크기가 정해져 있기 때문에 여러 개의 연산을 하나로 합쳐서 최적화할 수 있습니다. ((tmp2[3] & 0x55) << 1) 같은 식들을 테이블로 만들면 좀 더 연산 수를 줄일 수 있겠죠. (적당한 테스트를 해서 어떤 식들을 바꿔야 할 지 결정해야 할 겁니다)
- 토끼군
뽀나쓰 코드-_-입니다. char를 short/int로 확장하는 방법을
뽀나쓰 코드-_-입니다. char를 short/int로 확장하는 방법을 사용하면 좀 더 연산의 숫자를 줄일 수 있겠죠. 여기서는 short를 2바이트, int를 4바이트로 가정합니다.
아래 코드는 byte order에 상관 없이 동작하는 코드로, and 28개, or과 shift는 각각 14개가 필요합니다.
- 토끼군
[quote="philossh"][quote="Anonymous"][co
shift연산만 하게 고칠 수도 있겠네요
[quote="Anonymous"]shift연산만 하게 고칠 수도 있겠네
올바르지 않습니다. 예를 들어서 i=3, j=2라고 하면 org[3]>>5<<3이 되는데 이렇게 하면 상위 2비트가 그대로 남아 있지요.
- 토끼군
[quote="tokigun"]올바르지 않습니다. 예를 들어서 i
shift연산으로 다 하려면 오른쪽 맨 끝으로 쉬프트한 후에 왼쪽으로 다시 <<7을 해야 하는군요.
그냥 위에서 philossh님이 했던것처럼 &0x01을 한번 해주는게 나을듯
아 그러고보니 인덱싱이 잘못되었었군요. philossh님 수정버전인 셈
댓글 달기