8x8 배열 90도 회전 최적 알고리즘은??

elecguy의 이미지

안녕하세요..
소프트웨어로 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);

그런데 무식하게 루프를 돌려서 하는 것과 별 속도차이가 없습니다. -.-;;
좀 더 나은 알고리듬이 있을까요?
임베디드 시스템에 쓸 것이기 때문에 테이블을 쓴다면 그 크기가
수십킬로바이트이내에 들어오면 좋겠습니다.
그럼..

너바나의 이미지

보아하니 비트를 세로로 한줄씩 잘라서 가로로 재배치하는 것만하면 되는것 갈은데 테이블이 필요 없을것 같습니다.

그냥

rot[0]=((org[0]&0x80)>>7)|((org[1]&0x80)>>6)|
       ((org[2]&0x80)>>5)|((org[3]&0x80)>>4)|
       ((org[4]&0x80)>>3)|((org[5]&0x80)>>2)|
       ((org[6]&0x80)>>1)|(org[7]&0x80)
.
rot[7]=(org[0]&0x01)|((org[1]&0x01)<<1)|
       ((org[2]&0x01)<<2)|((org[3]&0x01)<<3)|
       ((org[4]&0x01)<<4)|((org[5]&0x01)<<5)|
       ((org[6]&0x01)<<6)|((org[7]&0x01)<<7)

이렇게 하면 재배치가 될것 같은데요.. ^^

익명 사용자의 이미지

  unsigned char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
  int i,j;
  for (i=0;i<8;i++) {
    rot[i]=0;
  }
  for (j=0;j<8;j++) {
    for (i=0;i<8;i++) {
      rot[j]|=((org[i]&mask[j])<<j)>>(7-i);
    }
  }

최적화는 잘 모르겠고, 루프로는..
philossh의 이미지

Anonymous wrote:
  unsigned char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
  int i,j;
  for (i=0;i<8;i++) {
    rot[i]=0;
  }
  for (j=0;j<8;j++) {
    for (i=0;i<8;i++) {
      rot[j]|=((org[i]&mask[j])<<j)>>(7-i);
    }
  }

최적화는 잘 모르겠고, 루프로는..

같은 내용이지만....

for ( i=0; i<7; i++)
{
    rot[i] = 0;
    for ( j=0; j<7; j++)
    {
        rot[i] |= ( (org[j]>>(7-i))&0x01 )<<j;
    }
}

마스크가 차지하는 용량을 줄일 수 있지 않을런지.... :oops:

To be or not to be.
That is the question.

lifthrasiir의 이미지

조금 생각해 보고 코드 짜 봤습니다. :) 아래는 40개의 and 연산, 24개의 or 연산, 24개의 shift 연산을 사용하는 알고리즘입니다.

unsigned char tmp1[8], tmp2[8];

/* pass 1 */
tmp1[0] = (org[0] >> 4) | (org[4] & 0xf0);
tmp1[1] = (org[1] >> 4) | (org[5] & 0xf0);
tmp1[2] = (org[2] >> 4) | (org[6] & 0xf0);
tmp1[3] = (org[3] >> 4) | (org[7] & 0xf0);
tmp1[4] = (org[0] & 0x0f) | (org[4] << 4);
tmp1[5] = (org[1] & 0x0f) | (org[5] << 4);
tmp1[6] = (org[2] & 0x0f) | (org[6] << 4);
tmp1[7] = (org[3] & 0x0f) | (org[7] << 4);

/* pass 2 */
tmp2[0] = (tmp1[2] & 0xcc) | ((tmp1[0] & 0xcc) >> 2);
tmp2[1] = (tmp1[3] & 0xcc) | ((tmp1[1] & 0xcc) >> 2);
tmp2[2] = ((tmp1[2] & 0x33) << 2) | (tmp1[0] & 0x33);
tmp2[3] = ((tmp1[3] & 0x33) << 2) | (tmp1[1] & 0x33);
tmp2[4] = (tmp1[6] & 0xcc) | ((tmp1[4] & 0xcc) >> 2);
tmp2[5] = (tmp1[7] & 0xcc) | ((tmp1[5] & 0xcc) >> 2);
tmp2[6] = ((tmp1[6] & 0x33) << 2) | (tmp1[4] & 0x33);
tmp2[7] = ((tmp1[7] & 0x33) << 2) | (tmp1[5] & 0x33);

/* pass 3 */
rot[0] = (tmp2[1] & 0xaa) | ((tmp2[0] & 0xaa) >> 1);
rot[1] = ((tmp2[1] & 0x55) << 1) | (tmp2[0] & 0x55);
rot[2] = (tmp2[3] & 0xaa) | ((tmp2[2] & 0xaa) >> 1);
rot[3] = ((tmp2[3] & 0x55) << 1) | (tmp2[2] & 0x55);
rot[4] = (tmp2[5] & 0xaa) | ((tmp2[4] & 0xaa) >> 1);
rot[5] = ((tmp2[5] & 0x55) << 1) | (tmp2[4] & 0x55);
rot[6] = (tmp2[7] & 0xaa) | ((tmp2[6] & 0xaa) >> 1);
rot[7] = ((tmp2[7] & 0x55) << 1) | (tmp2[6] & 0x55);

pass 1에서는 8x8을 4x4 조각으로 나눠서 돌리고,
pass 2에서는 각각의 4x4 조각을 다시 2x2 조각으로 나눠서 각각 돌리고,
pass 3에서는 그 2x2 조각을 다시 1x1 조각으로 나눠서 각각 돌립니다.

간단한 분할 정복 알고리즘으로, 크기가 정해져 있기 때문에 여러 개의 연산을 하나로 합쳐서 최적화할 수 있습니다. ((tmp2[3] & 0x55) << 1) 같은 식들을 테이블로 만들면 좀 더 연산 수를 줄일 수 있겠죠. (적당한 테스트를 해서 어떤 식들을 바꿔야 할 지 결정해야 할 겁니다)

- 토끼군

lifthrasiir의 이미지

뽀나쓰 코드-_-입니다. char를 short/int로 확장하는 방법을 사용하면 좀 더 연산의 숫자를 줄일 수 있겠죠. 여기서는 short를 2바이트, int를 4바이트로 가정합니다.

아래 코드는 byte order에 상관 없이 동작하는 코드로, and 28개, or과 shift는 각각 14개가 필요합니다.

unsigned char tmp1[8], tmp2[8];

/* pass 1 */
((int*)tmp1)[0] = ((((int*)org)[0] & 0xf0f0f0f0) >> 4) | (((int*)org)[1] & 0xf0f0f0f0);
((int*)tmp1)[1] = (((int*)org)[0] & 0x0f0f0f0f) | ((((int*)org)[1] & 0x0f0f0f0f) << 4);

/* pass 2 */
((short*)tmp2)[0] = (((short*)tmp1)[1] & 0xcccc) | ((((short*)tmp1)[0] & 0xcccc) >> 2);
((short*)tmp2)[1] = ((((short*)tmp1)[1] & 0x3333) << 2) | (((short*)tmp1)[0] & 0x3333);
((short*)tmp2)[2] = (((short*)tmp1)[3] & 0xcccc) | ((((short*)tmp1)[2] & 0xcccc) >> 2);
((short*)tmp2)[3] = ((((short*)tmp1)[3] & 0x3333) << 2) | (((short*)tmp1)[2] & 0x3333);

/* pass 3 */
rot[0] = (tmp2[1] & 0xaa) | ((tmp2[0] & 0xaa) >> 1);
rot[1] = ((tmp2[1] & 0x55) << 1) | (tmp2[0] & 0x55);
rot[2] = (tmp2[3] & 0xaa) | ((tmp2[2] & 0xaa) >> 1);
rot[3] = ((tmp2[3] & 0x55) << 1) | (tmp2[2] & 0x55);
rot[4] = (tmp2[5] & 0xaa) | ((tmp2[4] & 0xaa) >> 1);
rot[5] = ((tmp2[5] & 0x55) << 1) | (tmp2[4] & 0x55);
rot[6] = (tmp2[7] & 0xaa) | ((tmp2[6] & 0xaa) >> 1);
rot[7] = ((tmp2[7] & 0x55) << 1) | (tmp2[6] & 0x55);

- 토끼군

익명 사용자의 이미지

philossh wrote:
Anonymous wrote:
  unsigned char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
  int i,j;
  for (i=0;i<8;i++) {
    rot[i]=0;
  }
  for (j=0;j<8;j++) {
    for (i=0;i<8;i++) {
      rot[j]|=((org[i]&mask[j])<<j)>>(7-i);
    }
  }

최적화는 잘 모르겠고, 루프로는..

같은 내용이지만....

for ( i=0; i<7; i++)
{
    rot[i] = 0;
    for ( j=0; j<7; j++)
    {
        rot[i] |= ( (org[j]>>(7-i))&0x01 )<<j;
    }
}

마스크가 차지하는 용량을 줄일 수 있지 않을런지.... :oops:

shift연산만 하게 고칠 수도 있겠네요

  for (j=0;j<8;j++) {
    rot[i]=0;
    for (i=0;i<8;i++) {
      rot[j]|=(org[i]>>(7-j))<<i;
    }
  }
lifthrasiir의 이미지

Anonymous wrote:
shift연산만 하게 고칠 수도 있겠네요

  for (j=0;j<8;j++) {
    rot[i]=0;
    for (i=0;i<8;i++) {
      rot[j]|=(org[i]>>(7-j))<<i;
    }
  }

올바르지 않습니다. 예를 들어서 i=3, j=2라고 하면 org[3]>>5<<3이 되는데 이렇게 하면 상위 2비트가 그대로 남아 있지요.

- 토끼군

익명 사용자의 이미지

tokigun wrote:

올바르지 않습니다. 예를 들어서 i=3, j=2라고 하면 org[3]>>5<<3이 되는데 이렇게 하면 상위 2비트가 그대로 남아 있지요.

- 토끼군

  for (j=0;j<8;j++) {
    rot[i]=0;
    for (i=0;i<8;i++) {
      rot[j]|=((org[i]>>(7-j))&0x01)<<i;
    }
  }

shift연산으로 다 하려면 오른쪽 맨 끝으로 쉬프트한 후에 왼쪽으로 다시 <<7을 해야 하는군요.
그냥 위에서 philossh님이 했던것처럼 &0x01을 한번 해주는게 나을듯

아 그러고보니 인덱싱이 잘못되었었군요. philossh님 수정버전인 셈

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.