어셈블리어 나눗셈 구현(Assembler Divide Implementation)

요구사항
1. 어셈블리어로 나눗셈을 구현하시오. 단 함수 호출이 아닌 알고리즘을 이용하시요.
2. 음수와 양수 모든 경우에 따라 나눗셈이 가능하도록 구현하시오.
3. 나눗셈은 C, C++의 방식을 이용하시오.
4. 한번에 두개의 입력을 받고, (피젯수, 제수, 몫, 나머지) 순으로 출력하시오.

구현내용
어셈블리어에서 우리가 흔히 사용하는
call .mul
call .div
내장함수는 사실 이미 add와 subcc, branch 등등으로 구현되어 있다.
곱하기의 경우는 결국 "+" 의 반복이고, 나눗셈의 경우 "-"의 반복이다.
이에 대한 최적의 알고리즘이 존재하는데, 39~77 Line의 내용이다.
워낙 최적이라 설명하기도 까리하다.
주된 내용은 최소의 Register 2개를 내용을 이용하여 쉬프트와 덧셈을 이용한다.
레지스터 2개중 상위는 High Register, 하위는 Low Register로 나뉜다.
처음 나눗셈을 시작하면 Low Register에는 dividend(피제수)가 설정이되고 High Register에는 모두 0으로 셋팅한 상태에서 시작하게된다.
그리고 알고리즘에 따라 연산을 하면
Low Register에는 몫 이,
High Register에는 나머지 가 최종적으로 들어오게 된다.
Divisor(제수)는 중간 연산에서 subcc와 addcc에 사용된다.

최적화 알고리즘은 위와 같은 순서로 진행된다.
단 위 알고리즘은 양수의 연산 에서만 적용된다.
그렇기 때문에 요구조건에 맞추어 입력과 출력시 양과 음을 따로 판정해주어야 한다.
즉 위 알고리즘을 중심으로 상단부에 음양판정코드, 하단부에 음양판정코드가 있다.
피제수 / 제수 = 몫  , 나머지
   +     /    +   =  +   ,    +
   +     /    -   =  -   ,    +
   -     /    +   =  -   ,    -
   -     /    -   =  +   ,    -  
의 순서로 입력된 피제수와 제수에 따라 몫과 나머지 사이에는 일정한 규칙이 있다.
이를 응용하여 들어오는 피제수와 제수에 따라 몫과 나머지의 부호가 결정된다.

이 규칙에서 요구사항중 [C와 C++의 나숫셈방식] 을 이용하라는 것을 충족한다.
나눗셈에 문제가 되는 것은 피제수(dividend)가 음수가 될때이다.
어셈블리언어에서도 사실상 피제수가 음수가 되느냐, 제수가 음수가 되느냐에 따라 알고리즘이 다르게 구현된다고 한다.
(곱셈도 마찬가지)
피제수가 음수가되면 다음과 같은 고민에 빠지게 된다.
-13/4 =?
1. 몫 : -3, 나머지 : -1
2. 몫 : -4, 나머지 : 3

1번을 방식을 선택할 경우 가장 작은 수가 나머지로 나오며,
2번을 선택할 경우 나머지는 항상 양수가 나오게된다.

이 둘은 몫에서 확연히 다른수를 출력한다.
1번의 경우 C, C++, Java에서 선택하고 있고,
2번의 경우 Python, Ruby에서 택하고 있다고 한다.

2번의 경우 항상 나머지가 양수가 나와 통일성이 있지만, 나머지는 절대값은 커지게 된다.
이문제에 대하서는 프로그램마다 다른 것이고, 프로그램 언어상 우선순위에서 오는 해석문제라고 한다.
(수학자들은 나머지가 양수인 것을 선호한다고 함.)

이에 대한 고찰 및 좀더 자세한 설명은 아래 블로그에서 확인 할 수 있을 것이다.
http://soyoja.com/88
http://agile.egloos.com/1666312

[작성환경 : solaris sparc machine  작성툴 : Vi editor   컴파일러 : gcc]
.section ".data" input: .asciz "%d %d" output: .asciz "%d, %d, %d, %d\n" .align 4 .section ".text" .global printf .global scanf .global main main: save %sp, -112, %sp set input, %o0 add %fp,-4,%o1 add %fp,-8,%o2 call scanf nop ld [%fp-4], %l1 ! l1 dividend setting mov %g0, %l0 ! l1 is low, l0 is high ld [%fp-8], %l3 !l3 is divisor mov 32, %l2 ! l2 is Count (32 bit) ! g3 is check neg on dividend ! g4 is chekc neg on divisor checkneg1: ! sign Check tst %l1 mov 1,%g3 bge checkneg2 nop not %l1 add %l1,1,%l1 mov 0,%g3 checkneg2: ! sign Check tst %l3 mov 1, %g4 bge start nop not %l3 add %l3,1,%l3 mov 0, %g4 start: ba pos nop test: tst %l0 bge pos nop neg: addcc %l1,%l1,%l1 add %l0,%l0,%l0 bcc 1f nop bset 1,%l0 1: addcc %l0,%l3,%l0 ba fin nop pos: addcc %l1, %l1, %l1 add %l0,%l0,%l0 bcc 1f nop bset 1,%l0 1: subcc %l0,%l3,%l0 fin: bl szero nop or %l1,1,%l1 szero: subcc %l2,1,%l2 bg test nop tst %l0 done: bge ok nop add %l0,%l3,%l0 ok: ckoutputneg: ! Check Result Sign add %g3,%g4,%g5 ! It has 4 Case. cmp %g5,2 be chcase1 nop cmp %g5,0 be chcase2 nop cmp %g5,1 be chcase3 nop chcase1: ba end nop chcase2: not %l0 add %l0,1,%l0 ba end nop chcase3: subcc %g3, %g4, %g0 bl chcase4 nop not %l1 add %l1,1,%l1 nop ba end nop chcase4: not %l0 not %l1 add %l0,1,%l0 add %l1,1,%l1 end: ! %l1 Register is quotient (Low Register) ! %l0 Register is remainder (High Register) set output, %o0 mov %l1, %o3 ld [%fp-4], %o1 ld [%fp-8], %o2 call printf mov %l0, %o4 mov 1, %g1 ta 0

Output은 다음과 같다. 인자로 두개의 수를 받은 후
[피제수(Dividend), 제수(Divisor), 몫(quotient), 나머지(Remainder)]를 순서대로 출력한다. 물론 양,음 모두 가능하다.

코드분석
위의 코드들을 보면 (알고리즘상에서) 생각하지 못했던 재미있던 코드들이 있다.

위 코드는 로우레지스터와 하이레지스터간에 1칸 쉬프트를 하는 코드이다.
shift를 할때 lowRegister의 마지막에 1이 있을 경우 HighRegister에 1을 옮겨준다.
sll을 사용하지 않은 것은 넘겨줄 값이 1이 있을 경우와 없을 경우를 판단하기 위해 addcc를 사용하였다.
bcc는 Branch condition Carry로 Carry 비트에 따라서 분기를 하거나 하지 않는다.
정확히 Carry가 0일때 분기문으로 넘어가고 1일때, 즉 캐리값이 있을 경우 분기를 하지 않고 다음 문장을 실행하게 된다.
bcc의 경우 Condition Code의 C값이 0일때 bgeu를 실행하게 된다.

bset은 비트를 셋팅하는 수로 위의 bset 1, %hi_r는 최하위 비트가 1로 셋팅되게된다.
원리는 [or %register, 1, %register]이다. 즉 or연산을 통해 비트를 셋팅한다. 만약 1이 아니라 7이라면 첫번째와 두번째, 세번째 비트가 1로 셋팅된다.

위코드중에서는
not %l1
add %l1, 1, %l1
으로 나타낸 부분이 있다.
이부분은 2의보수를 이용하여 음수로 바꿔준 것이다.
이것을 좀더 줄인다면
not %l1
inc %l1
으로 줄일 수 있고,
한번 더 줄인다면
neg %l1
로 할 수 있다.
neg는 2의 보수를 만들어주는 명령어로 그 내부적으로는 sub %g0, %REG, %REG 로되어 있다.

코드에서 음/양을 판정하기 위해 tst라는 명령어는 사용하였다.
tst는 말그대로 test하는 명령어이다. 내부적으로는 orcc %REG, %g0, %g0로 되어 있다.
orcc를 사용하여 Condition Code를 수정하게 되는데 이는 바로 다음에 분기문에 이용할 수 있다는 사실이다.
%g0는 항상 0이고 3번째가 %g0로 되어 있는 것은 cc연산이기 때문이다.
결국 0이랑 선택한 레지스터와 or을 하여 cc연산을 해주게 된다.
tst사용후 bge를 쓰면 [레지스터의 수가 0과 같거나 같을 때 분기(양수일때],
bl을 쓰면 [레지스터의 수가 0보다 작을 경우 분기(음수일때)]. 식으로 해석이 된다.


※ .div와 비슷한 기능의 .rem이라는 나머지를 구하는 함수가 존재한다.