9장 - 이진 세상으로 - 나누기
나눗셈은 곱셈에서 mul/imul처럼 div/idiv 명령으로 해결한다. 나눗셈의 방식은 나누어질 값 (피젯수, dividend)과 나누려는 값 (젯수, divisor)을
정해주고 "div/idiv divisor" 포맷을 실행하면, 그 몫 (quotinet)과 나머지 (remainder)가 각각 특정 레지스터에 리턴된다. 실수 레벨로 로 5 / 2
= 2.5 이지만, div/idiv 명령은 정수 레벨 나눗셈이라서 5 / 2 = 2 이다. 즉, A = BQ + R의 형태로 리턴되며, 다음처럼 생각해볼 수 있다.
1 R
5 / 2 = 2 --- Q---
2 B
그렇다면 나머지는 어떻게 구하는가 ? 나머지만 저장하는 레지스터에서 얻어서 더해주면 된다. 하지만 나머지만 전문으로 저장하는 레지스터 또한
정수 레벨로 1만 저장하므로 나머지의 의미는 문맥에 의존한다. 결국 정확한 나눗셈을 할 수 없다는 얘기다. 그런 이유로 부동 소수점 레지스터나
고정 소숫점 연산이라는 것이 등장했다. 참고로 부동 (浮動, floating) 소숫점에서 "부동"의 의미는 "떠서 다닌다"는 뜻이지, "움직이지 않다"나
"얼지 않는다" 의 부동이 아니다.
더 깊이 들어가기에 앞서 우리는 십진 나눗셈을 살펴보자.
411 - Q
_______
3 ) 1234
12
---
03
03
---
04
03
----
1 - R
이진 나눗셈은 0과 1만 써서 나누므로 십진 나눗셈보다 더 쉽다. 다만 자릿수가 늘어날 뿐이다.
0110011011 - Q
____________
11 ) 10011010010 - 1234
00
---
100
11
--
11
11
--
01
00
--
10
00
--
101
11
--
100
11
--
10
00
--
101
11
--
100
11
--
1 - R
div/idiv 명령은 누적 레지스터 (accumulator)를 암시적 피젯수 (dividend)로 사용하며, 젯수는 div/idiv 명령에 "div/idiv r/m8/16/32" 형식으로
정해줄 수 있으며, 그 결과 나눗셈이 수행되어 몫이 누적 레지스터 (AL/AH/EAX)에 리턴되고, 나머지가 보조 레지스터 (AH/DX/EDX)에 리턴된다.
나머지는 몫보다 크지 않으므로, mul/imul과는 전혀 반대로 작동한다고 생각할 수 있다. mul/imul은 몫의 상위값이 보조 레지스터에 리턴된다.
나눗셈 수행시 정수가 아닌 수 (소수점 이하, 분수 부분)은 0으로 짤린다 (truncated/chopped). 나머지는 항상 몫보다 양적 (magnitude)으로 적거나
(unsgined, div을 사용할 경우), 절대치로 적다 (signed, idiv을 사용할 경우). 대부분의 경우 연산 에러를 CF로 표시하지만, 나눗셈에서는
오버플로가 발생하면 #DE (divide error) 예외를 발생하여 프로그램을 종료한다. #DE는 INT 0와 같은 말이며, 나눗셈 연산시 나눗셈의 결과를 담을
대상 레지스터의 크기에 맞지 않으면 발생하는 예외 (fault)이다. 만약 피젯수 (dividend)가 0이거나 몫 (quotient)이 결과 누적 레지스터
(accumulaotr)보다 커서 담지 못할 경우 발생한다.
8비트 나눗셈의 작동 코드는 다음과 유사하다.
if SRC = 0 then #DE fi
if OPSize = 8 then
temp <- AX / SRC
if temp > FFh then #DE
else AL <- temp, AH <- AX MOD SRC
fi
보다시피 #DE가 발생하는 경우는 두 종류이다. #DE를 "divide-by-zero"라고도 하는데, 첫째 if의 의미만 놓고보면 그렇지만, 둘째 if까지 감안하면
몫이 누적 레지스터 (AL)보다 클 경우도 발생함을 주의해야 한다. 만약 OPSize의 크기가 16/32비트이면, temp는 FFFFh/FFFFFFFFh를 검사한다.
각 레지스터의 역할은 이렇다:
(피)연산자 크기 피젯수 (dividend) 젯수 (divisor) 몫 (quotient) 나머지 (remainder)
Word 나누기 Byte AX r/m8 AL AH
Dword 나누기 Word DX:AX r/m16 AX DX
Qword 나누기 Dword EDX:EAX r/m32 EAX EDX
보다시피 AX의 역할이 8비트 나눗셈에서는 피젯수를 지정하는 역할이며, 16비트 나눗셈에서는 하위 피젯수/몫을 담는 역할로 용도가 바뀐다.
idiv (integer divide/signed divide) 또한 레지스터의 역할은 같지만, 음수/양수를 모두 허용하는 나눗셈이므로 레지스터의 표현 범위 (range)가
절반으로 줄어든다. 8비트 나눗셈 (보통 나눗셈의 비트, operand size는 divisor의 크기로 표현한다)작동 코드는 이렇다:
if SRC = 0 then #DE fi
if OPSize = 8 then
temp <- AX / SRC
if (temp > 7Fh) OR (temp < 80h) ; 양수 결과가 7Fh 이상이거나 음수 결과가 80h 이하인 경우
then #DE
else
AL <- temp, AH <- AX SignedMOD SRC
fi
오버플로를 7Fh/80h으로 비교하는 점이 div과 다름을 알 수 있다. (피)연산자의 크기가 16/32비트이면, 이는 7FFF/8000, 7FFFFFFF/80000000h으로
오버플로를 체크한다.
div/idiv 명령은 둘다 6대 플랙에 아무 영향을 주지 않는다. 예로,
mov ax, 0012h
mov bx, 0034h
div bx
라고해도 플랙은 변경되지 않는다.
mov ax, -9
mov bx, 3
div/idiv bx
이렇게 한다면 unsigned 나눗셈이므로 AX에 -9에 해당하는 FFF7이 들어가고, 이를 3으로 나누므로 AX에 몫이 5552h로 리턴되고, DX는 나머지 1이
리턴되며 오버플로를 발생하지 않는다. 만약 div를 idiv로 바꾸어도 FFF7을 3으로 나누므로 AX에 몫이 5552h로 리턴되고 오버플로를 발생하지 않는다.
mov ax, -9
mov bx, -3
div/idiv bx
(div: AX = 0000, DX = FFF7h, idiv : AX = AAAE, DX = 0001)
이 경우 둘다 오버플로를 발생하지 않으며, div 버전은 양수라고 가정한 상태에서 -3으로 나눈 셈이므로 AX에 몫으로 0을 리턴하고, dx에 나머지
FFF7 - 0 = FFF7 을 리턴하고, idiv은 어디서 저런 값이 나왔는지는 모르겠으나 오버플로를 일으키지 않았다.
간혹 나눗셈 오류 "divide by zero"를 겪는 프로그램을 본다. 나는 분명 0으로 나누지 않았는데, 왜 이런 에러를 접하게 되는가 ? 흔히 접하는 이런
오류는 다음과 같은 증상일 수 있다.
1. dividend나 divisor가 다른 연산에 되먹여 사용되는 경우
2. dividend나 divisor가 push/pop으로 변경되는 경우
3. dividend나 divisor가 루프에서 수정된 경우
4. 상위 dividend를 정해주지 않고 나눗셈을 실행할 경우
1. 2. 번은 예를 들기 어려울 정도로 많으며, 3번의 경우 루프 카운터 (보통 CX를 사용)로 나머지를 정해줄 경우 루프내에서 1씩 증감하다가 결국
0에 이르러 나눗셈 오버플로 (#DE)가 발생할 수 있다. 4번의 경우는 다음처럼 부호 확장 명령으로 어느 정도 예방할 수 있다.
8비트 나눗셈일 경우
mov al, dividend ; divisor는 이미 로드되었다고 가정
cbw ; ah를 al의 사인 비트로 채운다
div ; 나눗셈을 실행한다.
16비트 나눗셈일 경우
mov ax, dividend ;
cwd ; dx를 ax의 사인비트로 채운다
div
cbw는 8비트 나눗셈의 상위 피젯수 (ah)를 al의 사인 비트 (bit7)로 채워 ax를 16비트로 확장한다. cwd는 ax의 사인 비트 (bit15)로 상위 피젯수
(dx)를 채워 전체 피젯수를 32비트로 확장한다. 확장 될 사인비트는 양수일 경우 0, 음수일 경우 1이다.
부호 확장 (sign extension)은 덧셈/뺄셈에서는 거의 의미없으나 곱셈/나눗셈 기타 비트 단위 (bitwise, bit-by-bit) 연산에서는 필수 요소다.
예로 곱셈의 경우는 작은 수 둘을 곱하므로 곱셈 연산후 거기에 맞는 부호로 확장해주고, 나눗셈은 그 반대로 큰 수에서 작은 수를 나누므로
거기에 맞는 부호로 먼저 확장해주고 이어서 나눗셈을 한다. 즉, 선 곱셈 후 확장, 선 확장 후 나눗셈이다. 원리는 간단하다. 하위 데이터의
최상위 비트를 상위 데이터의 전체에 복사해서 넣는다. 이를 해주는 명령이 cbw/cwd/cwde/cdq 등이다. .386 이상에서 movsx/movzx 명령도
부호를 확장해준다.
mov al, 10110000b ; al = 1011 0000
cbw ; ax = 1111 1111 1011 0000
보다시피 cbw는 al의 최상위 비트 (bit7)를 ah에 복사해넣는다. 사실 ah는 연산에 관여하기보다는 단지 사인 비트 (ax의 bit15)를 채워주는
역할을 하는 것 뿐이다. 그 결과 바이트 데이터를 워드 데이터로 인정하는 것이다. 이는 .386이상에서 다음처럼 바꿔쓸 수 있다.
mov al, 10110000b ; al = 1011 0000
movsx ax, al ; ax = 1111 1111 1011 0000
보다시피 별반 차이가 없다. 이를 양수/음수를 의미하는 특별한 상수 (imm)로 하려면 이렇다.
mov ax, 0 ; ax = 0000 0000 0000 0000 mov ax, 0FFFFh ; ax = 1111 1111 1111 1111
mov al, 10110000b ; ax = 0000 0000 1011 0000 mov al, 10110000b ; ax = 1111 1111 1011 0000
왼쪽은 양수일 경우이고 오른쪽은 음수일 경우이다. 양수일 경우 xor ah, ah로 해줘도 무관하다. 부호를 매직 넘버 0/FFFFh로 확장하는 제일
간단한 방법이랄 수 있다. 부호를 확장하는 방법이 다양해 나중에 다시 다룰테니 주제로 돌아오자.
나눗셈이 워낙에 클럭 소모적인 명령이다보니, 나눗셈을 하기위해 다양한 대체 방법이 등장했다. 나눗셈을 가장 잘 활용한 예를 들라면 나는
진수 변환 (radix conversion)을 들 수 있다. 이 주제에 대해 우리는 이미 다뤘다. 대표적으로 십진 변환을 들 수 있는데, 십진 변환은 반복적으로
10으로 나눠주는 원리이다. 10뿐만 아니라 다른 여러가지 상수 나눗셈 (division by constants)을 위한 방법이 많이 등장했으며, 여기서는 십진
변환을 반복 뺄셈 (division by subtraction) 방법으로 해결해보자. 나눗셈과 뺄셈은 깊은 관련이 있다. 예로, 19, 20, 21 을 10으로 나눈다고 하자.
몫과 나머지는 각각 Q = 1, 2, 2 이고, R = 9, 0, 1이다.
10 은 2 * 5이다 그말은 1비트 shr하고 5/2 비트를 shr하면 해결되는데, 문제는 5/2비트 쉬프트를 정수 레벨로 할 수 없으므로 우리는 이를 10을
이용한 반복 뺄셈으로 해결해보자. div으로 나눈다면 다음 패턴의 코드가 될 것이다:
xor dx, dx
mov ax, 1234 ; ax = dividend
mov bx, 10 ; div factor
div bx ; ax = Q (123), dx = R (4)
이를 반복 뺄셈으로 에뮬레이션하면 이렇다.
xor dx, dx
mov ax, 1234
mov bx, 10
L1:
cmp ax, 10 ; ax < 10 ?
jb L2 ; yes, L2
sub ax, bx ; no, ax - bx
inc dx ; increase subtraction counter
jmp L1
L2: ; swap
xor ax, dx
xor dx, ax
xor ax, dx
보다시피 반복으로 10을 계속 빼서 dx에 뺀 횟수를 누적시켜 연산이 끝나면 ax와 dx를 바꿔줬다. 그 결과 ax는 몫이 dx는 나머지가 저장된다.
간단히 나눗셈을 에뮬레이션했다. 물론 값이 커질수록 루프를 여러번 돌기 때문에 속도면에서 느리겠지만, 이 방법은 특정 레지스터에 묶이지
않는 장점이 있다.
또한 어떤 수를 10으로 나누지 않고 그 역수 (1/10)를 곱해줄 수 있다. 16비트 레벨에서 65536은 오버플로가 있는 0이라고 할 수 있다. 만약
16비트 어떤 수에 65536을 곱한다면 (이는 16비트 레지스터로 정해줄 수 없는 값이므로 가상으로 곱한다고 생각하자) 그 결과는 dx:ax에 담기며,
(dx - 상위, ax - 하위) 오버플로가 토글되어 dx는 1, ax는 0으로 세팅된다고 생각할 수 있다 (즉, 1 0000h). dx에 1/10 에 해당하는 6554
(근사치)를 곱하면, 결국 총 결과에 1/10을 곱한 셈이 된다. 이를 코딩하면 이렇다.
mov ax, 1234
mov dx, 6554
mul dx ; dx = 상위 (몫), ax = 하위
xchg ax, dx ; 둘을 바꿔준다 (옵션)
보다시피 역수 (reciprocal)를 곱해서 그 결과를 xchg로 바꿔줬는데, 사실 나눗셈에서 몫이 의미를 가지므로 dx를 바로 취해서 쓰면 그만이고,
xchg는 옵션에 해당한다. 이 아이디어로 만약 8비트 곱셈을 한다면 ? 256/10 = 26 이를 곱하면 ?
mov al, 13 ; 나누려는 수
mov ah, 26 ; 매직 넘버
mul ah
mov cl, 8
shr ax, cl ; 옵션
충분히 이해될 것이다. 만약 32비트로 확장한다면 ?
mov eax, 12345678 ; test value
mov edx, 429496730 ; magic number
mul edx ; edx = eax / 10
인텔 계열 CPU에서 최소한 상수 곱셈은 상수 나눗셈보다 빠르니 별 것 아니지만서도 써먹으면 나을 것이다. 이 연산의 공통점은 상위 곱의 최소
정수 함수 (floor)를 취하는 점이다. 이 함수는 지금 단층 집에서 4층으로 올리려면 바닥을 몇번 더 깔아야하는가 ? 라는 질문에 답을 해주는
것으로 비유할 수 있다. 우리는 이전에 어떤 수를 2로 나눌 때 "shr x, 1"로 해주는 것을 터득했으니, 이제 다른 소수인 3, 5, 7마저 나눠보자.
매직 넘버만 바꿔주면 된다.
나누기 3 - 바이트 레벨: 256/3 = 85, 워드 레벨: 65536/3 = 21845, 더블워드 레벨: 4,294,967,296/3 = 1431655765
나누기 5 - 바이트 레벨: 256/5 = 51, 워드 레벨: 65536/5 = 13107, 더블워드 레벨: 4,294,967,296/5 = 858993459
나누기 7 - 바이트 레벨: 256/7 = 37, 워드 레벨: 65536/5 = 9362, 더블워드 레벨: 4,294,967,296/7 = 613566757샘플로 32비트에서 7로 나눠 테스트해봤다.
mov eax, 12345678 ; test value
mov edx, 4294967295/7 ; magic number
mul edx ; edx = eax / 7
제대로 작동하였으며, 1을 빼준 이유는 어셈블러가 런타임시 이 값을 계산할 수 없기 때문이다. 계산된 값 (613566757)을 넣어줘도 된다."shr x, 1" 방법은 어떤 수를 2로 나눴을 때 몫 (quotient)을 구하는 방법이다. 간혹 나머지 (remainder, modulus)를 구하고 싶을 때가 있다. 이때
div으로 나눴을 때 나머지가 저장되는 레지스터 (AH/DX/EDX)를 살펴보면 된다. div 명령 말고도 특별한 수 (2의 n승)로 나눳을 때의 나머지는
1을 뺀 and로도 구할 수도 있다. 예로, 어떤 수를 4로 나눴을 때의 나머지를 구한다면
and ax, 3 ; ax = ax mod 4
and ax, 7 ; ax = ax mod 8
and ax, 0Fh ; ax = ax mod 16
and ax, 1Fh ; ax = ax mod 32
and ax, 3Fh ; ax = ax mod 64
and ax, 7Fh ; ax = ax mod 128
and ax, 0FFh ; ax = ax mod 256
=
mov ah, 0 ; ax = ax mod 256
곱셈을 나눗셈으로 해결하던 옛날도 있었다. 옛날이면 컴퓨터가 더 느렸을텐데 하물며 더 느린 나눗셈 명령을 쓴다는 말인가 ? 그렇다. 바로 소수를
곱할 때가 그런 경우에 해당한다. 부동 소수점 프로세서 (FPU)가 없던 시절에 0.135를 어떤 수에 곱하라는 명령이 떨어졌다면 이를 어떻게 해결할
것인가 ? 135를 곱해서 그 결과를 1000으로 나누면 되지 않겠는가 ?
mov ax, 1234 ; 테스트 값
mov dx, 135 ; 곱하려는 값
mul dx ; 곱한 결과 dx:ax (상위:하위)
mov bx, 1000 ; 나누려는 값
div bx ; AX = 몫, DX = 나머지
계산기로 계산한 결과 1234 * 0.135 = 166.59로 리턴되었다. AX = A6 (166), DX = C9 (590). DX는 590/1000이다.
드디어 이장의 마지막인 복정밀 나눗셈에 이르렀다. 우리는 64비트 테스트 값 (dividend)을 16진수 값 (divisor)로 나눠 64비트 몫 (Quotient)과
16진수 나머지 (remainder)를 구해보자. 참고로 AOA에서 베껴서 살짝만 수정하기로 한다. 여기서 몫이 16비트이므로 나머지 또한 그 이상이 될 수
없으며, 복정밀 나눗셈은 캐리를 감안할 필요가 없으므로 다소 쉽지만, #DE만 조심하면 된다.
;=========== multiple precision division example ==========
;
.model small
.stack 100h
.data
dividend dd 0FFFFFFFFh, 12345678h ; FFFF FFFF 7856 3412
divisor dw 16
quotient dd 0, 0 ; 64비트 몫 2개
remainder dw 0
result db 5 dup (30h), 0D, 0Ah
;==============================
.code
main proc
mov ax, @data
mov ds, ax
mov ax, word ptr [dividend+6] ; 1234를 포인트
xor dx, dx ; 나눗셈 준비
div divisor ; 16으로 나눠, ax = Q(123h), dx = R (4)
mov word ptr [quotient+6], ax ; 결과 몫 최하위 워드에
mov ax, word ptr [dividend+4] ; 다음 워드 (5678h)
div divisor ; ax = Q (4567h), dx = R (8)
mov word ptr [quotient+4], ax ; 결과 몫 저장
mov ax, word ptr [dividend+2] ; 다음 워드 (FFFFh)
div divisor ; ax = 8FFFh / dx = 0Fh
mov word ptr [quotient+2], ax
mov ax, word ptr [dividend] ; 마지막 (FFFFh)
div divisor ; ax = FFFFh / dx = 0Fh
mov word ptr [quotient], ax
mov [remainder], dx ; 나머지 (8) 저장, 몫 : 0000 0000 0000 0000 -> 0123 4567 8FFF FFFF
exit:
mov ah, 08h ; 잠시 지연
int 21h
mov ax, 4C00h
int 21h
main endp
베껴 작성한거라서 결과가 맞는지는 모르겠다.
댓글 없음:
댓글 쓰기