nlz알고리즘들은 정말 눈이 아프더군요. 그래서 다음으로 미룹니다.


--------------------------------

워드 검색은 워드에 포함된 바이트를 다루는 알고리즘이라 할 수 있습니다.


오늘은 그중에서 특정 바이트의 위치를 찾는 함수를 알아봅시다.


특정 바이트의 위치는 오른쪽에서부터 세냐, 왼쪽부터 세냐에 따라 right left형으로 나눠질 수 있어요.

가령, left는

0, x = 00xxxxxx

1, x = nn00xxxx

2, x = nnnn00xx

3, x = nnnnnn00

라 찾으며

right는

0, x = xxxxxx00

1, x = xxxx00nn

2, x = xx00nnnn

3, x = 00nnnnnn

와 같은 위치들을 찾죠


left는 함수로

if ( ( x >> 24) == 0 ) return 0

if ( ( x & 0x00ff0000) == 0 ) return 1

if ( ( x & 0x0000ff00) == 0 ) return 2

if ( ( x & 0x000000ff) == 0 ) return 3

return 4

이렇게 구현할 수 있습니다.

뭐 rigth 는 4-left로 찾을 수 있겠죠


무분기 코드로는

y = (x & 0x7f7f7f7f) + 0x7f7f7f7f

y = ~(y | x | 0x7f7f7f7f)

return nlz(y) >> 3

로 쓸 수 있습니다.  (nlz는 선행 0의 개수를 셉니다)

이는 포함된 0x00을 0x80으로 변환하고 나머지를 0x00으로 변환하고 선행 0의 개수를 세는 알고리즘이죠

아이디어는 간단합니다. x & 0x7F에서 7bits를 가져오고 여기에 7f를 더해 8bit를 켜게 만듭니다.

00이 아니라면 무조건 켜지게 된다는 거죠. 그다음 not~~구문에서 8bit가 꺼진 부분만 켜면됩니다.

(책에 설명이 안되있어서 해석을 해봤는데 이게 맞는 이해인지는 모르겠네요)

right는 return (32 - nlz(~y & (y - 1))) >> 3 로 반환값을 대체해 쓸 수 있습니다.


제일 오른쪽 0바이트를 찾는 하므로

어떤 문서에선 다음과 같은 알고리즘을 제안하기도 합니다.

y = (x - 0x01010101) & ~x & 0x80808080

n = ntz(y) >> 3 (ntz는 후행0의 개수를 셉니다.)

원리는 다음과 같습니다. 

x - 0x01구문은 0000 0001 -> 0000 0000이 되고, 0000 0000 -> 1111 1111이 될 수 있습니다.

즉, x의 byte가 0인 부분이 0xf. 로 덮힌다는 원리를 이용한 것이죠.

하지만, 0xfe같은 값이 들어오면 같은 결과를 낳으므로 ~x & 0x80808080을 통해 유효한 MSB를 추출하게 됩니다..

즉, 0xfe는 ~x ... 에 의해 0000 0000이 된다는 의미가 됩니다.

마지막으로 & 연산에 의해 zero byte를 찾을 수 있게됩니다.

이렇게 찾아진 zero byte는 후행 0의 개수세기 알고리즘으로 찾아 질 수 있습니다.


----------------------------------------------------------------------------

zero byte알고리즘이 나온 김에 다른 코드도 알아봅시다.

MS사의 strlen.asm에선 다음과 같은 코드가 존재합니다.

        mov     edx,7efefeffh

        add     edx,eax

        xor     eax,-1

        xor     eax,edx

        test    eax,81010100h

이 코드를 C언어로 옮기면,

if ( ((( x + 0x7efefeff ) ^ ~x) & 0x81010100) ) ... else goto main_loop;

로 쓸 수 있 수 있습니다..  ( cpu내부에선 cmp는 감산을, test는 and연산을 수행한다. )

간단히 분석해봅시다.

x + 0x7efefeff 에서 x + 0111 1110 1111 1110 1111 1110 1111 1111 로 표현되며,

0x81010100 는 1000 0001 0000 0001 0000 0001 0000 0000 입니다.

두 숫자의 패턴을 찾을 수 있을까요?

그 패턴은 ~0x7efefeff == 0x81010100이라는 것입니다.

어째서 이 규칙이 적용되어야 하는 것일까요?

x + 0x7efefeff를 보면, x의 값이 최대 2라도 변하면 각 nibble의 상태가 변하게됩니다.

예를 들어

1110 + 1 -> 0 1111

1110 + 2 -> 1 0000

1111 + 1 -> 1 0000 이죠. 

즉, 상위 nibble의 영향을 주어 값의 변화를 유도함으로써 0x81010100에 의해 if 본문이 실행되지 않을 거란 예상을 할 수 있습니다.

not연산을 통해 각 nibble의 변화를 본다고 할 수 있습니다.

가령, 0x11223344를 x라고 가정해봅시다. x + 0x7efefeff는 0x90213243이고, ~x는 0xEEDDCCBB 이므로 xor은

0x7EFCFEF8 입니다. 최종적으로 if ( 0 )가 되어 zero byte를 찾지 못한 것이죠.

이번엔 zero byte가 포함되어있는 0x11002233를 x라고 가정해봅시다.

x + 0x7efefeff는 0x8FFF2132

~x는 0xEEFFDDCC

이 둘의 xor은 6100FCFE입니다. if ( 0x01,00,00,00 )가 되어 구문이 실행될 수 있어요.

----------------------------------------------------------------------------


원점으로 돌아가서, 이런 위치 검색 코드들을 nlz나 ntz가 프로세서 지원이 안된다면 성능차이가 심할 수 있는 부분들 입니다

따라서 nlz를 이용하지 않은 코드가 필요해 보입니다.

이 코드는 nlz를 사용하지 않은 무분기 left를 보여줍니다.

y = (x & 0x7f7f7f7f) + 0x7f7f7f7f

y = ~(y | x | 0x7f7f7f7f)

if ( y == 0 ) return 4 // 4

if ( y > 0x0000FFFF )

   return (y >> 31) ^ 1 // 0, 1

else return (y >> 15) ^ 3 // 2, 3


법과 배열을 사용한다면

static table[16] = { 4, 3, 2, 2, 1, 1, 1, 1, 0, };

y = (x & 0x7f7f7f7f) + 0x7f7f7f7f

y = ~(y | x | 0x7f7f7f7f)

return table [ y % 127 ] 로도 줄일 수 있습니다.

부호 없는 32비트 곱셈을 지원한다면

return table[hopu(y, 0x02040810) & 15]

return table[y*0x00204081 >> 28] 로도 쓸 수 있습니다.

여기서  hopu(a,b)는 HLL(곱셈의 값이, 계산된 곱의 하위 32비트라는)기반의 부호 없는 곱의 상위 32bit를 뜻합니다.

곱하기가 빠르거나 시프트나 더하기로 수행할다면 위 방법이 쉬울 수 있습니다. 이런 곱셈을 네 개의 그런 명령으로 수행할 수 있습니다.

y (1+2**7+2**14+2**21)은 y(1+2**7)(1+2**14)니깐요

그 예로 64비트에선

table[y % 511]

table[(y*0x00020408 10204081) >> 56]과 같이 확장될 수 있음을 보여줍니다.

(마지막건 저도 잘 모르겠습니다.)



----------------------------------------------------------------------------

이전 게시물들


기초편

http://gall.dcinside.com/board/view/?id=programming&no=537462&page=1

경계점검

http://gall.dcinside.com/board/view/?id=programming&no=538546&page=1

비트 수 세기

http://gall.dcinside.com/board/view/?id=programming&no=538740&page=1