11장 - 디지털 훌라후프 - 쉬프트와 로테이트사람이 인공적으로 만들어낸 사물은 대부분 네모나거나 직선형이다. 하지만 자연이 만들어낸 사물은 대부분 동그랗거나 원형에 가깝다. 우리가 여기서
다룰 쉬프트 (shift)와 로테이트 (rotate) 명령은 원형적 사고방식을 적용하면 이해하기가 쉽다. 이 둘은 사전상 "회전하다"는 뜻을 가진다. 둘간의
차이가 있지만 비트를 회전하는 점에서는 같다. 여기 8인치 줄자가 있다.
<그림> 
각 비트 번호는 오른쪽에서 왼쪽으로 0번부터 메겼다. 우리는 이를 바이트라고 부르며, 8비트 속에 비트8은 없다. 이중 제일 왼쪽 끝 비트를 MSb,
제일 오른쪽 끝 비트를 LSb라고 부른다. 이 네모난 비트 박스에 0 이 들어갈지 1 이 들어갈지는 정의하기 나름이다. 또한 이 바이트가 무엇을
담을지는 상황에 따라 다르며, 만약 산술 연산에 사용될 숫자를 의미한다면, MSb = sign bit가 된다. 익히 알고 있는 내용일 것이다.
이제 이 비트 덩어리에서 왼쪽 끝 / 오른쪽 끝 비트에 접착제로 붙여서 띠를 만들어 허리에 두를 수 있다고 하자. 물론 8인치가 너무 작으면
16인치나 32/64인치 허리띠도 있으니 상황에 따라 필요한 것을 취하면 되니 길이는 무시하기로 하자. 이제 우리는 원형으로 만들었으니 이 비트
덩어리를 회전시킬 수 있다.
왼쪽으로 회전시키는 명령이 shl/sal/rol/rcl 이고, 반대로 오른쪽으로 회전시키는 명령이 shr/sar/ror/rcr이다. 좌우 어느 방향으로 회전하든간에
비트 위치는 고정되며, 데이터가 들어있는 네모난 비트 박스만 이동된다고 생각하자. 플랙표는 이렇다:
<그림> 
똑똑한 사람들은 이를 다 외우지만, 혹사시킬 뇌세포가 부족한 사람은 이를 이해한다. 최소 8비트 이상의 비트를 회전할 것이므로 AF의 의미는 없다.
또한 회전을 할 때마다 비트 레벨 자리 올림이 일어날 수 있으므로 CF를 항상 리셋한다. 로테이트 명령은 비트를 유지하면서 회전하는 것이므로
SF/ZF/PF에 영향을 줘서는 안된다. 반면 쉬프트 명령은 회전할 때마다 비트를 리셋하므로 SF/ZF/PF는 결과에 따라 리셋된다. 1비트만 회전할 경우
OF 마저 리셋하며 그 이상을 회전할 경우 OF는 어찌될지 알 수 없다.
shl/sal 명령은 "shl/sal d, c" (d: dest, c: count) 일반 포맷으로, c에 정해준 수만큼 왼쪽으로 비트를 회전한다. 두 명령은 같은 명령이며, 두
명령의 기계어까지 같다. debug.exe는 sal을 허용치 않으며, 만약 signed 데이터일 경우 형식적으로 sal (shift arithmetic left)을 사용한다.
떨어져나가는 제일 왼쪽 끝 비트는 CF에 복사되고, 채워져 들어오는 제일 오른쪽 끝 비트는 0 으로 채워진다.
<그림> 
위의 플랙표를 참조하면, ZF 플랙도 갱신한다고 되어있다. 어떤 수를 왼쪽 쉬프트하여 0으로 만드는 경우는 오버플로를 일으키는 경우이다. 이는 80h
이상의 수를 쉬프트할 때 발생한다. 예로, 80h/8000h/8000000h에 해당하는 수를 1비트 쉬프트하면 바이트/워드/더블워드 레벨에서 담을 수 없으므로
OF가 토글되고, 쉬프트 됨과 동시에 0 이 되므로 ZF가 토글되며, 또한 최상위 비트인 1이 떨어져 나가니 CF까지 함께 토글하며, MSB에서 패러티가
짝수 (0)로 변하므로 PE 플랙까지 함께 토글하며, 또한 최상위 비트인 사인 비트가 떨어져 나가므로 SF 까지 토글한다. 즉, 80h를 쉬프트하는 것은
CPU 입장에서 일종의 혁명 (?)이 일어난 셈이다.
mov al, 80h ; al = 1000 0000
shl al, 1
80h는 음수도 아닌 것이 양수도 아닌 것이 음수도 되고 양수도 되는 중성적인 존재이다. 결국 어떠한 수이건간에 여러번 shl하다보면, 언젠가는 0이
될 것이다.
mov al, 01h ; al = 01
mov cl, 80h ; 80h (128)번 루프도세요 (cl = 루프 카운터)
L1:
shl al, 1
loop L1
이 경우 결국 어느 시점에서 0이 될 것이며, 그 이상은 공회전하는 역할이다. 보통 mov 명령으로 cl에 쉬프트 카운터를 정해주는데 cl이 8비트
레지스터라고해서 8비트 값을 모두 정해봤자 의미가 없다. 왜냐하면 FFh (255)로 정해준다면, 쉬프트 중간에 이미 0이 되므로 더 이상 쉬프트할
필요가 없기 때문이다. 즉, 데이터가 8/16/32비트이면, 그 데이터에 따라 7/15/31이 최대 유효 쉬프트 카운트이다.
이 시점에서 CPU 매뉴얼을 인용하자.
IA-32 Architecture Compatibility
The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask
the shift count to 5 bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the
virtual-8086 mode) to reduce the maximum execution time of the instructions.
32비트 이하 모드 (이를 호환 모드라고 한다)에서 8086 CPU는 쉬프트 카운트를 마스킹하지 않는다. 하지만, 286 이후부터의 모든 IA-32 프로세서는
쉬프트 카운트를 5 bits로 마스킹하여 최대 쉬프트 카운트를 31까지만 허용한다. 결과적으로 모든 운영 모드 (V86 모드도 포함)에서 shl/sal 명령의
실행에 걸리는 시간을 단축시켰다.
이 시점에서 코드로 이를 확인하자.
mov al, 1
mov cl, 32 ; 쉬프트 카운터
shl al, cl ; al = 01
mov bl, 1
mov cl, 31
shl al, cl ; al = 00
mov bh, 0FFh
mov cl, 32
shl al, cl ; al = 0FFh
보다시피 쉬프트 카운터를 32 이상으로 정해주면 쉬프트가 일어나지 않으며 값이 그대로 유지된다. 그렇다면 64비트 모드에서는 마스킹하지 않는다는
소린가 ? 애석하게도 내 컴이 아직 32비트라서 테스트해볼 수가 없었다. 솔직히 말해서 32비트 이상을 쉬프트할 일도 별로 없다. 하지만, 만약 32비트
이상을 쉬프트 한다면, 중간에 끊어서 다시 쉬프트해주거나 위처럼 루프로 돌리면 된다. 참고로 "shl al, 2"처럼 쉬프트나 로테이트 명령에 2이상의
imm 값을 정해주려면 masm에서 .286 이상의 프로세서 지시어를 써야한다. 그 이전의 프로세서에서 2이상의 쉬프트를 하려면, cl에 정해주던가
아니면 다음처럼 "shl X, 1" 명령의 반복 코드를 써왔었다.
mov al, 1
shl al, 1
shl al, 1
shl al, 1
shl al, 1
비록 코딩량은 좀 늘어나지만, "shl X, 1" 명령은 상대적으로 빠른 명령 (386 3클럭, 펜티엄 이상 1클럭)이라서 문제될 것이 없다.
"shl X, 1" 명령은 왼쪽으로 비트를 격상 (promotion)시키므로, 오버플로가 발생하지 않는 범위 내에서 결국 2의 배수를 곱한 값이 된다. 그런
이유로 2의 배수를 곱한다 싶으면 상대적으로 느린 mul/imul을 대신하여 "shl X, 1"을 써왔다. 반면 "shl X, 0"을 하면 어떨까 ?
mov al, 12
shl al, 0 ; 인밸리드래...ㅡ,.ㅡ
이렇게 해주면, masm은 친절히 invalid instruction operands 라고 알려주며, debug.exe는 친절히 거부해버린다. shl "X, Y"의 8비트 레벨 매직
넘버를 나열하면 이렇다.
Y:01 - X * 2
Y:02 - X * 4
Y:03 - X * 8
Y:04 - X * 16
Y:05 - X * 32
Y:06 - X * 64
Y:07 - X * 128
Y:08 - X * 256
위에서 8비트 레벨의 맥시멈 쉬트프 카운터는 7이라고 했으므로, 이 카운터를 8로 정해주는 것은 결국 1 0000 0000 으로 만드는 것과 같다. 즉,
"mov al, 0" 다만 플랙을 OF/CF/PF/ZF을 세팅하는 점이 다를 뿐이다. 이는 쉬프트하다가 중간에 플랙을 테스트하여 브레이크를 걸 수 있다는 뜻이다.
mov al, 01h ; al = 01
mov cl, 50h ; 대충 넉넉히 잡아주고
L1:
shl al, 1
jo L2 ; 오버플로가 일어나면 (al = 80h) 브레이크
loop L1
L2:
shl al, 1
jo L3 ; 오버플로가 일어나면 (al = 00) 다시 브레이크
loop L2
L3:
이 경우 오버플로 플랙을 테스트하여 브레이크를 걸었다. 즉, 바이트 레벨 최상위 비트가 세팅되어서 브레이크가 걸린 셈이다.shl로 상수 곱셈을 대신하는 경우는 이전에도 설명했다. 예로, al = al * 9를 한다고 하자.
mov al, 8
mov bl, al ; 복사해서
shl al, 1 ; al = al * 2
shl al, 1 ; al = al * 4
shl al, 1 ; al = al * 8
add al, bl ; 붙여넣기
shl을 쓰는 이유가 "mul al, 9" 보다 빠르기 때문에 이렇게 해왔다. 산술 쉬프트인 sal은 쉬프트를 하는 점은 유사하지만, 사인 비트를 유지한다.
여기서 사인 비트라 하면 음수일 경우 -를 의미하려 채워지는 모든 사인 비트를 의미한다. 코드로 확인하자.
mov al, 0FFh
mov cl, 80h
L1:
sal al, 1
loop L1
초기에 al = 0FFh (-1)을 정해주고 루프에서 "sal al, 1"로 한번씩 쉬프트했다. 그 결과,
al = 0FFh ; 1111 1111 (-1)
al = 0FEh ; 1111 1110 (-2)
al = 0FCh ; 1111 1100 (-4)
al = 0F8h ; 1111 1000 (-8)
al = 0F0h ; 1111 0000 (-16)
al = 0E0h ; 1110 0000 (-32)
al = 0C0h ; 1100 0000 (-64)
al = 080h ; 1000 0000 (-128)
al = 000h ; 0000 0000 (-256 = 0)
보다시피 sal은 shl과 똑같이 작동한다. 실제로 디버그로 sal을 트레이싱하면 shl로 변환해서 보여준다.
and/or 등의 비트 연산 명령으로 특정 비트를 복사해서 붙여넣기 방식을 배웠다. 이들 명령이 쉬프트와 혼합하면 더욱 놀라운 일을 하기도 한다.
xor ax, ax ; ah = al = 0
mov al, 16 ; al = 0001 0000
shl al, 1 ; al = 0010 0000
and al, 0F0h ; al = 0010 0000
or ah, al ; ax = 0010 0000 0010 0000
이 경우 al의 값을 shl로 1비트 쉬프트하여 ah에 그대로 복사했다. 또한 다른 레지스터와 결합하여 더욱 놀라운 일을 하기도 한다.
mov ax, 1234h ; ax = 1234h
xor bx, bx ; bx = 0000h
mov bl, 0AAh ; bl = 1010 1010
shl bl, 1 ; bl = 0101 0100
and bl, 0F0h ; bl = 0101 0000
mov bh, bl ; bx = 0101 0000 0101 0000
or ax, bx ; ax = 5274h
이 경우 bl로 비트 교차 패턴 (AAh, 55h)으로 마스킹해주고 하위 니블을 지우고 bh에 마스킹 패턴을 복사하여 ax를 or로 비트합산해줬다.
사회적으로 높은 지위로 오르기 위해 왼쪽만 보고 달렸다면, 이제 과거를 돌이켜보려 오른쪽도 살펴봐야 공평할 것이다. shr/sar은 비트를 오른쪽으로
쉬프트하며, shl/sal과 반대 방향이다. 쉬프트하여 떨어져나가는 오른쪽 비트 (LSb)는 캐리 플랙 (CF)에 저장되고, 최상위 왼쪽 비트 (MSb)는 0으로
채워진다. shr/sar로 비트를 쉬프트하다보면 특정 비트가 다른 비트 위치로 이동하거나 숫자로 의미를 가지는 데이터는 2의 배수로 나눠지는 역할을
한다. 즉, X = X / power of 2 이며, 이를 그림으로 그려보면 이렇다:
<그림>
보다시피 떨어져나간 마지막 비트는 CF에 저장된다. shr/sar의 차이는 사인 비트 (MSb)를 어떻게 세팅하냐로 판가름난다. shr은 가장 왼쪽 끝 비트를
0 으로 지운다. sar은 양수일 경우는 0으로 지우지만, 음수일 경우는 1로 채운다. sar가 1로 채우는 경우는 최상위 비트가 1로 세팅되어 음수로
인정하기 때문이다.
mov al, 0FFh ; al = 1111 1111
sar al, 1 ; al = 1111 1111, CF = 1, SF = 1, PF = 1
shr al, 1 ; al = 0111 1111, CF = 1, OF = 1, PF = 1, OF = 1
이 경우 모든 비트가 1로 세트된 상태이므로 sar로 1비트 오른 쉬프트를 하더라도 사인 비트가 1로 채워지므로 결과적으로 값이 변하지 않지만,
shr는 부호와는 상관없이 무조건 0으로 채우므로 결국 7Fh로 반감된다. 7Fh는 양수이며, 127이다. 결국 -1 / 2 가 shr 일땐 + 127 이, sar 일땐
-1이 되었다는 얘기다. 255 / 2 = 127.5인데 나머지를 무시한 (chopped, truncated) 나눗셈이 되었다. 만약 div/idiv으로 FFh를 다음처럼 나누면,
mov al, 0FFh
mov bl, 2
div/idiv bl ; ax = 017F (ah = 나머지, al = 몫)
같은 결과가 될 것이다. shr는 어느 정도 수긍이 가지만, sar는 -1을 2로 나눠 -1이 되었다는게 조금 이상할 것이다. 0이 되어야 하지 않나 ?
이 시점에서 CPU 매뉴얼을 꺼내보자. 조금 장문이니 긴장하고 읽어보자.
Using the SAR instruction to perform a division operation does not produce the same result as the IDIV instruction.
The quotient from the IDIV instruction is rounded toward zero, whereas the “quotient” of the SAR instruction is
rounded toward negative infinity. This difference is apparent only for negative numbers. For example, when the IDIV
instruction is used to divide -9 by 4, the result is -2 with a remainder of -1. If the SAR instruction is used to
shift -9 right by two bits, the result is -3 and the “remainder” is +3; however, the SAR instruction stores only
the most significant bit of the remainder (in the CF flag).
- sar로 2씩 나눌 때는 idiv으로 나눌 때와 결과가 다를 수 있다. idiv의 몫은 0으로 라운드되지만, sar의 "몫"은 음의
무한대로 라운드된다. 이 둘의 미묘한 차이는 음수 나눗셈을 할 때 확연히 드러나는데, 예로 들면, -9를 4로 idiv으로
나누면 결과는 몫이 -2, 나머지가 -1이 되는 반면에, sar로 -9를 2비트 오른 쉬프트하면, 결과는 -3이 되고, 나머지는 +3이
된다. 하지만, sar 명령은 나머지의 가장 중요한 비트만 CF에 저장한다.
쉽게 해석하려고 노력했는데 무슨 소린지 이해가 가는가 ? 해석한 나 또한 모르겠으니 코드로 직접 나눠보자.
xor ax, ax
mov bx, ax
mov dx, ax
mov al, -9 ; F7
cbw ; FFF7
mov bl, 4 ; FFF7 / 4
idiv bl ; ah = 나머지 (FF = -1), al = 몫 (FE = 1111 1110 -> 2의 보수로 0000 0001 + 1 = 0000 0010 = [2])
mov dl, -9 ; dl = F7 = 1111 0111 -> 2의 보수로 0000 1000 + 1 = 0000 1001 = [9]
sar dl, 1 ; dl = FB = 1111 1011 -> 2의 보수로 0000 0100 + 1 = 0000 0101 = [5]
sar dl, 1 ; dl = FD = 1111 1101 -> 2의 보수로 0000 0010 + 1 = 0000 0011 = [3]
idiv 의 경우 -9 / 4 = -2 (몫), -1 (나머지) 이고, sar의 경우 -9 / 4 = -3 (몫), +3 (?) 몫은 이해가 가는데 나머지는 어떻게 측정했는지
도무지 감이 안온다. sar 회전시 두번 다 SF/ZF/PF/CF를 토글했음은 알 수 있었다. 여튼 한가지 분명한 것은 음수중 절대치가 홀수인 수를
여러번 sar 하는 것은 라운드 문제로 인해 오해의 소지가 있음을 알 수 있다. 반면, 다음처럼
mov al, -16h ; F0
sar al, 1 ; F8 = -8
sar al, 1 ; FC = -4
절대치가 짝수인 음수는 아무 문제가 없음을 알 수 있다. 그런데 -9/4의 sar 했을 때 나머지가 무슨 근거로 +3이라고 했는지는 여전히 미지수다.
피젯수 (dividend)가 양수일 경우에 사람들은 익숙하므로, -1 을 2로 정수 레벨 나눗셈을 한다면 0이 될 것이라고 생각한다.
mov ax, 1
mov bx, -1
sar ax, 1 ; 0000h, 1 / 2 = 0
sar bx, 1 ; FFFFh, -1 / 2 = -1
그렇다면, 피젯수 (dividend)가 음수이며 절대치가 홀수일 땐 특별한 처리를 해줘야 한다는 얘기다. Michael Abrash는 다음처럼 음수일 경우 홀/짝에
관계없이 1을 더해서 해결하는 방법을 알려준다.
mov ax, -1 ; 음수라면
and ax, ax ; 사인 플랙을 체크하고
jns L1 ; 양수일 땐 정상적인 나눗셈
add ax, 2 - 1 ; 절대치를 컴파일 타임시 - 연산자로 빼준 값을 더해준다. (즉, 1을 더해준다)
L1:
sar ax, 1 ; 이제 음수든 양수든 2로 나눈다.
이 아이디어와 앞장에서 배운 "cmp X, 1" 방법을 응용하여 우리는 다음처럼 해결할 수도 있다.
mov ax, -1 ; 음수라고 하자
cmp ax, 1 ; 마지막 비트를 테스트하여
jz L1 ; 짝수면 L1으로
add ax, 1 ; 홀수면 1을 더하고
L1:
sar ax, 1 ; 음수든 양수든 2로 나눈다.
sar 명령은 부호를 유지하면서 쉬프트하므로 사인 확장에 요긴하게 쓰인다. 1비트씩 sar 할 때마다 사인 비트가 차곡 차곡 쌓여가니 8번 sar하면
결국 모든 비트가 부호 비트로만 채워진다. "sar ax, 8"이라고 하면 al의 사인 비트가 16비트 ax로 확장되며, ah는 지워진다.
mov al, 81h ; -127
mov cl, 8 ; 쉬프트 카운터
sar ax, cl ; ax = 0, OF = 0, SF = 0, ZF = 0, CF = 1
하지만 부호 확장을 하려면 상위 데이터의 MSb만 남겨둬야하므로 바이트/워드/더블워드로 확장하는 명령인 CBW/CWD/CDQ는 다음처럼 -1을 빼고 쉬프트
해줘야 한다.
mov ah, al ; 복사 mov dx, ax ; 복사 mov edx, eax ; 복사
sar ah, 7 ; = CBW sar dx, 15 ; CWD sar edx, 31 ; CDQ
물론 .286 이상의 프로세서 지시어를 쓰지 않으면 cl에 쉬프트 카운터를 정해줘야 하고, 다음처럼 다른 레지스터에 부호를 확장할 수 있다.
mov cx, bx ; 복사
sar cx, 15 ; CWD (CX:BX)
이외에도 특정 비트를 복사하여 붙여넣기 방법과 .286 이상부터 .movsx/movzx 등으로 확장하는 방법은 나중에 더 다루겠다.
sar를 이해했다면 shr는 더 쉽다 오른 쉬프트를 하되, 제일 왼쪽 비트를 0으로 채운다. 그 결과 2로 나눈 효과가 된다.
mov al, 0FFh ; al = 1111 1111 (FFh, 255)
shr al, 1 ; al = 0111 1111 (7Fh, 127)
shr al, 1 ; al = 0011 1111 (3Fh, 63)
보다시피 한번씩 쉬프트할 때마다 왼쪽에 추가되는 비트는 0이다. shift 연산시 매번 캐리 플랙 (CF)을 리셋하므로 만약 CF를 캐리로 더해주거나
빼주면 어떨까 ?
mov ax, 0FFFFh ; FFFFh, 양수 65535라고 하자
mov cl, 4
shr ax, cl ; 0FFFh, = 4095, 65535/16 = 4095.9375
adc ax, 0 ; 마지막 캐리를 더하자. (ax = 4096)
보다시피 간단히 반올림 (round up) 처리를 했다. 간혹 and와 or은 쉬프트/로테이트 연산에 날개를 달아준다.
mov al, 0AAh ; al = 1010 1010
mov cl, 4 ; 쉬프트 카운터
shr al, cl ; al = 0000 1010
or al, 30h ; al = 0011 1010 = 3A
이번엔 니블 단위로 뒤집어보자. 물론 rol 명령으로 할 수 있지만, 여기서는 shr/shl을 혼합해서 해보자.
mov al, 3Fh ; 테스트 값
mov bl, al ; 복사하여
mov cl, 4
shr al, cl ; al은 상위 니블 소거
shl bl, cl ; bl은 하위 니블 소거
or al, bl ; 둘을 합친다
간단히 니블 병합을 해줬다. rol 명령도 좋긴 한데 간혹 다른 비트는 손대지 않고 싶을 때가 있고, 노는 레지스터가 있으면 해볼만 할 것이다.
또한 shr/shl 대상을 서로 바꿔도 잘 통하며, 16비트나 32비트로도 확장할 수 있다. shr/shl/or을 한번씩 더 적어주면 뒤집기가 된다. 만약
32비트에서 작업한다면 워드만 and 등으로 마스킹해서 합쳐도 좋을 것이다.rol 명령은 shl 명령처럼 비트를 왼쪽으로 회전시킨다.
<그림>
shl과 마찬가지로 매번 떨어져 나가는 비트는 캐리 플랙 (CF)에 복사되지만, shl과는 다르게 떨어져나간 비트 (MSb)로 채워질 비트 (LSb)를 채운다.
마치 열쇠 고리에서 열쇠를 들고 자물쇠에 맞춰 보는 것으로 비유하면, CF가 자물쇠, 회전되는 비트가 열쇠 정도에 해당한다. CF에 채워지는 비트는
LSb에도 채워진다.
mov al, 55h ; al = 0101 0101
rol al, 1 ; al = 1010 1010
rol al, 1 ; al = 0101 0101, CF = 1
rol al, 1 ; al = 1010 1010
rol al, 1 ; al = 0101 0101, CF = 1
이 경우 55h (0101 0101)는 비트가 서로 교차되는 패턴이므로 한번씩 회전시킬 때마다 CF가 번갈아 토글된다. 8비트 레지스터에서 8 비트를 회전하면
결국 제자리로 돌아온다. "rol al, 4"처럼 8비트 레지스터를 4비트 회전하면 니블이 서로 바뀐다. 물론 복수 비트를 회전시킬 경우 .286이하에서는
cl에 로테이트 카운터를 정해준다. 로테이트 명령은 쉬프트 명령과 명령 포맷이 같다.
ror 명령은 shr 명령처럼 비트를 오른쪽으로 회전시킨다.
<그림>
매번 떨어져 나가는 비트는 캐리 플랙 (CF)에 복사되고, 그 비트는 또한 LSb에도 채워진다. 만약 8비트 레지스터를 8비트 로테이트하면 원래로
돌아오고 4비트 로테이트하면 두 니블이 바꿔진다.
mov ax, 1234h
mov cl, 4
ror ax, cl ; ax = 4123
ror ax, cl ; ax = 3412
ror ax, cl ; ax = 2341
ror ax, cl ; ax = 1234
만약 ax = 1234h 일 경우 ax의 모든 니블을 4321h로 스와핑하라면 ? 바이트/워드/더블워드/쿼드워드의 공통점은 니블의 갯수 (또는 비트의 갯수)가
짝수라는 점이므로, 상/하위 반토막씩 쪼개서 쓸 수 있다. 만약 AX에 니블 4개 값이 있다면 다음처럼 4개를 역순으로 스와핑할 수 있다.
mov ax, 1234h ; 1234
mov cl, 4
ror ax, cl ; 2341
ror ax, cl ; 3412
ror ah, cl ; 4312
ror al, cl ; 4321
모든 쉬프트/로테이트 연산은 캐리 플랙을 갱신한다. 그러므로 쉬프트나 로테이트할 때마다 떨어져나가는 CF를 조사하여 비트가 몇개인지 셀수 있다.
여기서는 캐리를 이용하여 입력 키 값을 2진수로 출력해보자.
;=========== bin dump ==========
;
mStdout macro prompt
mov ah, 40h
mov bx, 1
mov cx, sizeof prompt
lea dx, prompt
int 21h
endm
.model small
.stack 100h
.data
temp db 8 dup (?)
.code
main proc
mov ax, @data
mov ds, ax
mov ah, 00h ; Get Keystroke (al = ASCII)
int 16h
cmp al, 1Bh ; if ESC
jz Exit
lea si, temp
mov cl, 8 ; 8 bits
L1:
mov bl, 30h ; mask
rol al, 1 ; rotate
adc bl, 0 ; mask + carry
mov [si], bl
inc si
loop L1
mStdout temp
Exit:
mov ax, 4C00h
int 21h
main endp
end main
보다시피 출력 변수 포인터를 옵셋 0으로 잡아줬으니 rol로 각 비트를 로테이트하여 미리 매직 넘버로 30h를 세팅한 값에 adc로 캐리를 더해줬다.
rol/ror 명령은 쉬프트 명령과 마찬가지로 캐리 플랙 (CF)을 매번 갱신하지만, 오버플로 플랙 (OF)은 다소 이상하게 갱신한다. 쉬프트에서 OF는
"초과"의 의미가 있지만, 로테이트에서 OF는 쉬프트 되는 비트가 0 인가 1 인가를 측정하는 용도로 사용된다. 쉬프트 연산과는 다르게 로테이트
연산은 비트 자체를 유지하므로 소스 데이터의 내용에 의존하므로 로테이트 이후 SF/PF/ZF/AF를 세팅해서는 안된다. 논리적으로 따져보면 당연한
결과이다. 반면 CF는 매번 리셋하고, OF는 작동 방식이 다소 애매하므로 CPU 매뉴얼을 인용해보자:
The OF flag is defined only for the 1-bit rotates; it is undefined in all other cases (except that a zero-bit rotate does nothing,
that is affects no flags). For left rotates, the OF flag is set to the exclusive OR of the CF bit (after the rotate) and the
most-significant bit of the result. For right rotates, the OF flag is set to the exclusive OR of the two most-significant bits
of the result.
- OF 플랙은 1비트 로테이트에서만 정의되며 멀티 비트일 경우 의미가 없다. (0 비트 로테이트는 아무것도 하지 않으며, 아무 플랙에 영향주지
않는다). 왼쪽 쉬프트일때, OF는 소스 데이터의 MSb와 CF를 xor하여 갱신하고, 오른쪽 쉬프트일때, OF는 연산 결과의 소스 데이터의 두 MSb를
xor하여 세팅된다.
다소 설명이 애매하므로 유사코드로 살펴보자.
이 코드를 조금 살펴보자. 먼저 연산자의 크기를 mod 연산으로 구해두고, 루프로 들어가 dest 연산자의 MSb를 CF에 복사해두고, dest 연산자는
2를 곱하거나 (rol), 2로 나누고 (ror), 카운트를 감소시켜 루프를 돈다. rol/ror 모두 로테이트 카운터가 1일 경우만 OF를 세팅하는데, rol의
경우 OF <- MSb (dest) xor CF, ror의 경우 OF <- MSb (dest) xor MSb-1 (dest) 라고 위의 설명한 내용이 나온다. 코드로 보자.
mov al, 0 ; al = 00xx xxx0
ror al, 1 ; al = 00xx xxx0, CF = 0, OF = 0 xor 0 = 0
mov al, 80h ; al = 10xx xxx0
ror al, 1 ; al = 010x xxx0, CF = 0, OF = 0 xor 1 = 1
mov al, 0FFh ; al = 11xx xxx1
ror al, 1 ; al = 111x xxx1, CF = 1, OF = 1 xor 1 = 0
00 이나 FF는 아무리 로테이트해도 값이 변경안되므로 OF는 항상 0이며, 비트 1이 교차된 데이터를 로테이트하면 반드시 OF = 1이다. 위의 유사
코드에서 FF가 "rol X, 1" 했을 때 왜 FF가 되는지는 다소 흥미롭지 않은가 ? 또한 쉬프트/로테이트 카운터가 0이 아닐때를 보면, 멀티 비트
쉬프트/로테이트를 루프로 해결하는 것을 알 수 있다. 즉, 쉬프트 카운터가 루프 카운터로 작동하니, 반대로 쉬프트 카운터를 적은 값으로
정해줄수록 루프를 적게 돈다는 얘기다.
rcl/rcr 명령도 각각 좌/우로 로테이트하는 명령이다. 이들 명령에 사용되는 CF은 1비트 레지스터 역할을 한다. 즉, 대상 (피)연산자가 8비트라면,
rcl/rcr 명령은 9비트를 로테이트 하는 셈이다. 이들 명령 또한 쉬프트 명령과 포맷은 같다. rcl 명령은 왼쪽으로 로테이트하고 떨어져 나가는 MSb는
CF에 임시로 저장되고, rcr 명령은 오른쪽으로 로테이트하고 떨어져나가는 LSb를 CF에 임시로 저장한다. 위의 rol/ror 그림을 그대로 참조하여
CF를 로테이트에 끼워넣는다고 이해하면 된다.
모든 쉬프트/로테이트 연산은 CF를 수정하므로 rcl/rcr 명령은 다른 쉬프트/로테이트 명령과 자주 결합하여 사용된다. 특히 복정밀 쉬프트/로테이트
연산이나 압축된 데이터 연산에서는 없어서는 안되는 존재이다. 마치 덧셈에서 adc, 뺄셈에서 sbb와 비슷한 역할을 한다.
mov al, 12h ; al = 0001 0010
shr al, 1 ; al = 0000 1001, CF = 0
shr al, 1 ; al = 0000 0100, CF = 1
rcr al, 1 ; al = 1000 0010, OF = 1, CF = 0
rcr al, 1 ; al = 0100 0001, OF = 1, CF = 0
첫번째 shr는 보다시피 0000 1001로 만들고 캐리를 일으키지 않지만, 두번째 shr는 캐리를 일으키므로 이 캐리는 CF에 들어간다. 이어서 rcr을 써주면
마지막 캐리된 비트를 로테이트에 재사용한다. 그 결과 캐리가 MSb에 들어가 1000 0010이 되고, 떨어져나가는 비트가 없으므로 CF는 0이 되었다.
두번재 rcr은 첫번째 rcr의 떨어져나간 0을 그대로 MSb에 넣고, 마지막 떨어져나가는 비트는 0이므로 CF에 영향주지 않는다.
rcl/rcr 명령에서 OF는 OF <- MSb (dest) xor CF로 같다. 이는 CF가 0이면 OF = 1, CF가 1이면 OF는 0으로 반대로 작동한다는 뜻이다. 하지만, rcl은
선 로테이트 후 OF 갱신, RCR은 선 OF 갱신 후 로테이트를 하는 점이 다르다. rcl은 연산 후 대상 연산자에 2를 곱해서 CF를 더한 것이며, rcr은
대상 연산자를 2로 나눠 (CF * 2의 연산자크기 만큼 거듭제곱)을 더한 것이다.
0이 아닌 (non-zero) 어떤 수를 쉬프트/로테이트 명령만으로 0으로 만들어라고한다면, 단순히 좌/우 어느 한 방향으로 0이 될때까지 쉬프트시키면
된다. 만약, 8비트라면 8번 쉬프트하면 결국 원래 값이 된다. 캐리된 비트를 다른 레지스터로 옮겨주면 비트 레벨 복사가 된다. 물론 mov 명령으로
해결할 수 있지만, 여기서는 로테이트로 해보자.
xor ax, ax
mov bx, ax
mov cx, bx
mov ax, 1234h
mov cl, 16
L1:
ror ax, 1 ; ax = 1234h
rcr bx, 1 ; bx = 1234h
loop L1
ror을 한번씩 실행할 때마다 ax에서 CF로 떨어져나간 비트를 rcr을 사용하여 bx로 보내주었다. 이는 rol/rcl 조합으로도 가능하다. 이처럼 rcl/rcr
명령은 다른 쉬프트/로테이트 연산 뒤에서 쓰여지면 캐리를 복사한 셈이된다. 그러면 몇개의 1을 가지고 있는지도 쉽게 셀 수 있다.
L1:
ror ax, 1 ; ax = 0001 0010 0011 0100
adc bx, 0 ; bx = 1의 갯수
loop L1
그렇다면 0인 비트를 모두 지우고 1인 비트만 복사할 수도 있을 것이다.
xor ax, ax
mov bx, ax
mov cx, bx
mov ax, 1234h
mov cl, 16
L1:
ror ax, 1 ; ax = 0001 0010 0011 0100
jc L3
L2:
dec cl
jcxz Last
jmp L1
L3:
rcl bx, 1 ; bx = 1Fh = 11111b
jmp L2
Last:
rol/ror을 거치고 이어서 rcl/rcl을 쓰면 rcl/rcr 명령 또한 CF를 토글하므로 우리는 이전 rol/ror의 떨어져나간 비트를 얻어낼 방법이 없으므로
분기처리로 해줬다. 마치 워드 프로세서에서 공백을 제거하는 것과 비슷한 연산을 해줬다.
어떤 바이트에 있는 모든 비트를 역순으로 재배치할 수는 없을까 ? 사실 현실 세계에서 바이트가 최소 의미 레벨이므로 이를 뒤집는 것은 현실과는
거리가 멀지만 몇몇 프로그램에서 암호화 루틴이나 압축 루틴에서 이는 자주 사용된다. 이는 bsf/bsr 등의 비트 연산 명령으로 할 수 있지만, 이는
.386 이상의 프로세서 지시어를 써야한다. 그렇다면 이전 사람들은 어떻게 해결했을까 ? 이를 쉬프트와 로테이트 명령으로 에뮬레이트해보자.
예로, 76543210 8개의 비트가 있다고 하자. 이를 절반으로 나눠서 7654 3210으로 일단 살펴보면, 7 <-> 0, 6 <-> 1, 5 <-> 2, 4 <-> 3으로 바꿔야
0123 4567 이 됨을 알 수 있다. 비록 1바이트 레지스터에 모두 담을 수는 있지만, 그 레지스터를 쉬프트/로테이트해봤자 07654321 식으로 밖에
안된다. 이는 다소 정렬 알고리즘에 가까우므로 여기서 다루기엔 조금 무리가 있지만, 배운 것을 실제 적용하는 차원에서 직접 코딩해보자.
먼저 알고리즘을 조금 살펴봐야겠다. 알고리즘 책 먼지 쌓이게 덮어둔지 오래되서 이런 정렬 방식을 뭐라하는지는 모르겠으나, 우리는 8개의
비트를 거꾸로 정렬하되, 이 데이터를 16비트로 확장하여 (즉, 노는 레지스터에 복사하여) 이를 반복적으로 캐리를 포함한 로테이트하기로 하자.
8비트 데이터를 1비트씩 rcl/rcr 하다보면, 언젠가는 중복되는 패턴이 나올 수 있다. 76543210이라는 데이터는 여기서는 비트 위치를 의미한다.
그리고 그 데이터를 al에 정해주고 이를 ah에 복사하면 다음처럼 패턴이 그려질 것이다. ah = 7654 3210, al = 7654 3210.
이제 캐리를 포함하여 반복으로 ah는 왼쪽으로 로테이트하고, al은 오른쪽으로 로테이트하면, 다음처럼 패턴이 그려질 것이다.
CF ah al CF 루프 횟수
7654 3210 7654 3210
7 - 6543 2107 7765 4321 - 0 1
6 - 5432 1070 6776 5432 - 1 2
5 - 4321 0701 5677 6543 - 2 3
4 - 3210 7012 4567 7654 - 3 4
3 - 2107 0123 3456 7765 - 4 5
...
우리는 0123 과 4567 이라는 패턴을 찾았으므로 더는 루프를 돌 필요가 없다. 왜냐하면 76543210은 데이터가 아니고 비트 위치를 의미하기 때문이다.
그런데 문제는 서로 한칸씩 밀려서 일치하는 패턴이 형성되므로 루프를 네번만 돌고 ah만 따로 한번 더 로테이트해주면 된다. 이 과정을 마치면,
ax = 2107 0123 4567 7654 의 패턴이 나오며, 이를 오른쪽으로 4번 쉬프트하고 ah만 따로 4번 더 쉬프트하면 결국 ah는 0이 되고, 바뀌어진 비트
위치는 al에 0123 4567로 리턴된다. 이를 코딩하면 이렇다:
xor ax, ax
mov al, 0AEh ; al = 7654 3210 (bit #, 테스트 값 무시)
mov ah, al ; ax = 7654 3210 7654 3210
mov cl, 4 ; loop counter
rol ah, 1 ; ax = 6543 2107 7654 3210, CF = 7
L1:
rcr al, 1 ; ax = 6543 2107 7765 4321, CF = 0
rcl ah, 1 ; ax = 5432 1070 7765 4321, CF = 6
loop L1 ; ax = 5432 1070 6776 5432, CF = 1,...
; ax = 2107 0123 4567 7654
mov cl, 4
shr ax, cl ; ax = 2107 0000 0123 4567
shr ah, cl ; ax = 0000 0000 0123 4567
L2:
숫자가 도배되다보니 제법 복잡해보이지만, 코딩 자체는 단순하기 그지 없다. 이 원리를 나중에 알고리즘 구현할 때 써먹는 것은 어떤가 ? 그냥
bsf/bsr 명령에 의존하더라도 한번쯤 연구해볼만 하지 않은가 ? 알고리즘은 원리만 알아두면 두고 두고 써먹을 수 있다. 이제 우리에게 남은 것은
복정밀 쉬프트/로테이트 연산이다.
rcl/rcr로 캐리를 이용한 쉬프트/로테이트 연산의 작동 방식을 이해하면 복정밀 쉬프트/로테이트 또한 쉽다. 복정밀 연산에 대해서는 귀찮은 관계로
AoA 코드를 부분 인용하기로 한다. rcl/rcr 명령은 adc 명령 처럼 없어서는 안되는 존재이다. 왜냐하면 쉬프트/로테이트 연산이 그 자체가 자리
옮김을 의미하기 때문이다. 우선 더블워드 데이터를 워드 레지스터로 쉬프트/로테이트 연산해보자. ax가 상위 값을 담는 레지스터이고 dx가 하위
값을 담는 레지스터라면 다음처럼 shl/rcl 조합으로 간단히 32비트 데이터를 1비트 왼쪽 쉬프트할 수 있으며 x2를 한 값이 된다.
xor ax, ax
xor dx, dx
mov ax, 1234h
mov dx, 5678h
shl ax, 1
rcl dx, 1
만약 48비트 데이터라면 여분 레지스터를 하나 더 이용하여 다음처럼 1비트 오른 쉬프트를 할 수 있다:
xor ax, ax
mov bx, ax
mov dx, ax
mov ax, 1234h
mov bx, 5678h
mov dx, 9ABCh
shr ax, 1
rcr bx, 1
rcr dx, 1
결과는 2로 나눈 값이 ax:bx:dx 3 레지스터에 저장된다. 만약 64비트 데이터라면 여분 레지스터를 하나 더 이용하여 다음처럼 1비트 쉬프트할
수 있다:
xor ax, ax
mov bx, ax
mov cx, bx
mov dx, cx
mov ax, 1234h
mov bx, 5678h
mov cx, 9ABCh
mov dx, 0DEF0h
shr ax, 1
rcr bx, 1
rcr cx, 1
rcr dx, 1
이처럼 방향이 어느쪽인지 결정하여 shr이면 rcr을 shl이면 rcl을 추가로 하위 레지스터에 값을 로테이트해주면 된다. 여기서 주의할 점은 쉬프트
/로테이트 명령은 카운터를 복수 비트로 정해줄 경우 캐리를 무시하고 연산하므로 우리는 1비트 단위로 쉬프트해야 한다. 이 문제를 더블 쉬프트
명령 (shld/shrd)으로 어느 정도 해결할 수 있으나 애석하게도 더블 로테이트 명령은 아직 없다. shl/shr처럼 rol/ror도 해주면 된다. 하지만
로테이트는 자리 이동이 중요하지 그 결과값이 얼마냐가 중요한 것이 아니다.
메모리에 저장된 복정밀 데이터는 리틀 엔디언이다. 그러므로 만약 48비트 메모리 쉬프트를 한다면 다음처럼 해준다.
shl word ptr [myVar], 1 ; 상위 워드 시작 옵셋
rcl word ptr [myVar+2], 1 ; 다음 워드
rcl word ptr [myVar+4], 1 ; 최하위 워드
만약 복수 비트 쉬프트할 경우 이 블럭을 루프로 잡아주고 cl에 카운터를 정해주면 된다. 만약 데이터가 메모리 연산자라면 위의 레지스터 연산을
상위 워드부터 해야하므로 다음처럼 거꾸로 정해줘야 한다:
L1:
sar word ptr [myVar+4], 1
rcr word ptr [myVar+2], 1
rcr word ptr [myVar], 1
L2:
shr word ptr [foo+4], 1
rcr word ptr [foo+2], 1
rcr word ptr [foo], 1
L1은 sar 버전이고 L2는 shr 버전이다. 만약 .386 지시어로 확장 쉬프트 명령으로 한다면 다음처럼 코딩한다:
myVar dw 1234h, 5678h, 9012h
...
mov eax, myVar+4
shld myVar+8, eax, 6
mov eax, myVar
shld myVar+4, eax, 6
shl myVar, 6
"shld s1, s2, imm" 명령은 s2에서 비트를 취해 s1으로 imm 만큼 쉬프트해서 넣는다. 첫번째 shld는 myVar+4에서 myVar+8로 쉬프트해서 넣고,
두번째 shld는 myVar에서 myVar+4로 쉬프트해서 넣으며 마지막 shl은 최하위 더블워드를 적절히 쉬프트한다. 기억할 것으로 최상위 dword를 최하위
dword로 쉬프트하는 점이고, 복수 비트 연산이므로 캐리 플랙이 영향을 못 발휘하는 점이다. 확장 로테이트에 대해서는 직접 AoA를 참조하라.
댓글 없음:
댓글 쓰기