SPARC Assembler Array Sorting Programming

음, 이제 레지스터와 메모리 개념도 확실히 잡히고, (SPARC 구조상...)
여러 메모리 테스트를 해보았더니, 이제 메모리 부분을 fp와 sp를 이용하여 자유롭게 접근이 가능하였다.
그래서 아주 간단한 Sorting 프로그램을 만들어보기로 했다.

물론 구현 알고리즘은 C로 하면 매우 간단하나 어셈블리어로 직접 확인해 보는데, 의의를 두고 시작하였다.
먼저 알고리즘의 기본적인 C++ source는 다음과 같다.

#include<iostream> using namespace std; void main() { int ary[10]={9,8,7,6,5,4,3,2,1,0}; int i,j; for(i=0;i<10;i++){ for(j=i+1;j<10;j++){ if(ary[j]<=ary[i]){ int temp; temp=ary[i]; ary[i]=ary[j]; ary[j]=temp; } } } for(i=0;i<10;i++){ cout<<ary[i]<<" "; } cout<<endl; }
위 코드는 무식하게 배열을 모두 순환해 나가며, 작은 값을 배열의 맨 왼쪽에 집어넣고, 그 행동을 총 크기 n번만큼 하는 코드이다. 즉, n+(n-1)+(n-2)+....1 번을 수행하게 된다. 거의 N의 2승의 느려터진 속도를 자랑하지만.....
역시나 직관적이고 코드로 즉각 표현하기 용이 하므로 이를 이용한다. (위 방식이 삽입정렬은 아니다!!)

위 코드의 결과는 결국 오름차순으로 배열의 값이 정렬된다.

그럼 이제 어셈블리어 코드를 살펴보자.

우리가 만들 정렬코드의 목적은 다음과 같다.
1. 임의의 숫자를 10개를 입력받아 배열 구조를 이용하여 저장한다.
2. 입력받는 도중에 Ctrl+D를 입력받으면 입력루틴에서 빠져나오고, 정렬연산을 수행한다.
3. Sorting시 오름차순으로 정렬한다.
4. 배열구조에 접근할때는 무조건 반복을을 이용한다.
5. 마지막에 정렬된 결과를 출력한다.

[작성환경 : solaris sparc machine  작성툴 : Vi editor   컴파일러 : gcc]

!Assembler Sorting Array .section ".data" str: .asciz "%d " str0: .asciz "Input 10 Num\n" str1: .asciz "Sorted Array : " newline: .asciz "\n" input: .asciz "%d" !must except \n plz .section ".text" .global printf .global main main: save %sp, -136, %sp add %fp, -40, %l3 ! Array Size 4 byte x 10 set str0, %o0 call printf mov 0, %l1 ! Count Loop and Array Value ba initfor mov 0, %l7 ! %l7 is Input Num Count initForLoop: set input, %o0 ! %l1 is Array Index 0,1,2,3,....9 call scanf add %l3, %l4, %o1 cmp %o0, -1 be endInIt inc %l1 inc %l7 initfor: cmp %l1, 10 bl,a initForLoop sll %l1, 2, %l4 ! %l4 is Array Address Length 0,4,8,12...36 endInIt: clr %l0 ! %l0 is Array Index ba sortAry clr %l1 ! %l1 is Count Loop sortLoop: add %l1, 1, %l5 !%l5 is Inner Ary Index ba sortAryInner nop sortLoopInner: ld [%l3+%l6], %i0 !%i0 is ary[j] value [ex: ary[1], ary[2]....] ld [%l3+%l4], %i1 !%i1 is ary[i] value [ex: ary[0]] cmp %i1, %i0 ble sortAryInner inc %l5 changeValue: st %i0, [%l3+%l4] st %i1, [%l3+%l6] ! exchange %i0, %i1 sortAryInner: cmp %l5, %l7 ! %l7 is input Num count bl,a sortLoopInner sll %l5, 2, %l6 !%l6 is Inner Ary Address Length inc %l1 sortAry: cmp %l1, %l7 ! %l7 is input Num count bl,a sortLoop sll %l1, 2, %l4 set str1, %o0 call printf clr %l0 ! %l0 is Array Index ba printAry clr %l1 ! %l1 is Count Loop printAryLoop: set str, %o0 call printf ld [%l3+%l4], %o1 inc %l1 printAry: cmp %l1, %l7 bl printAryLoop sll %l1, 2, %l4 ! %l4 is Array Index 0,4,8,12...36 set newline, %o0 call printf nop ret restore

C언어 22줄짜리가 Assembler 75줄로 늘어났다.
그것도 nop을 줄이기 위해 짱구를 엄청 굴려놓은 것이다..
워낙 길어지기 때문에 Quick_Sort나 Merge_Sort는 생각도 않했다 -.,-;

Lable들이 지저분하게 많다만 모두 반복문에 쓰인 것이다.

<소스분석>
2~7 Line : data영역을 초기화한 부분이다. printf 나 scanf를 위한 문자열 및 format으로 사용된다.
               필자는 이부분에서 scanf를 사용하는 input 부분에서 골머리를 썩혔는데, 그이유는 scanf를 호출시 format을 처음 "%d\n"으로 설정했다가 필자가 예상한 값과 너무 다른 현상이 발생하였다. 알고보니 C언어에서도 \n은 사용하지 않았던 기억이 나서 \n을 지워버렸더니 예상대로 잘 돌아갔다~

16~30 Line : 입력을 받으면서 메모리 영역에 배열의 Value를 초기화하는 부분이다.
                  참고할만한 부분은 Ctrl+D를 입력받았을 경우 %o0에 -1값이 반환된다는 사실이다. 이를 이용하여 scanf호출 후 %o0를 cmp로 검출하여 Ctrl+D의 입력 여부를 판정이 가능하다.

32~56 Line : 전체적인 Sorting하는 부분이다. 이부분은 두개의 중첩 for문으로 이루어져 있다.
                  for문을 어셈상에서 구현하는 방법은 여러가지가 있지만, 필자가 사용한 것처럼 첫번째에는 수행할 것들을, 마지막 부분에는 Loop여부를 판단하는 코드를 넣어주는 방식이 보편적이다.
                 예를들면,

     ba inTest
     nop

                 inLoop: ........(연산수행, C언어에서는 for문 내부 루틴)
                 .
                 .                 (for문의 증감연산자는 이 마지막 부분이다.)
                 inTest: ......(조건 테스트, C언어에서는 for문 가로 내 조건)

                 bl inLoop
                 nop
위와 같은 식으로 위에서 Test로 바로 넘어오고(ba이용), 첫번째 test를 거쳐 위로 올라가서 계속 반복하는 구조가 좋다. 무조건적은 아니고 필자가 이것저것 해본 결과, 가장 직관적이고, 중첩되었을때 프로그래밍하기 훨씬 수월하다~^^

※ 위와 같은 구조로 연산 수행부분에 다시 같은 양식의 InnerLoop가 들어있는 모습을 볼 수 있을 것이다. 이 때 Register 값이 어디에 쓰이는지 명확히 주석을 써놓으면서 코딩을 해야 헷갈리지 않는다 ㅠ.ㅜ;      
값을 교환하는 부분은 46, 47 Line인데 Register와 Memory를 사용하므로 Swap하는 형식을 사용할 필요 없이
 st %i0, [%l3+%l4]
 st %i1, [%l3+%l6]
코드만을 이용해 구현이 가능했다.

57~75 Line : 배열을 출력하는 부분이다. 반복에 의해 각 메모리에 위치한 배열의 Value를 출력한다.

※ 어셈블러가 nop을 제거하다보면 정말 어느정도 숙련이 되지 않으면 소스가 보기 불편하다. 허나 자꾸 보다보면 왜 이게 여기 있는지 알게 될 것이다.

<10개의 모든 값을 임의 대로 입력한다. 입력하자마자 정렬해서 놓는 구조가 아니라,
일단 배열에 입력된 순서대로 넣고, 그 배열을 순차적으로 정렬하는 구조이다.>

<8번째 입력에서 숫자를 입력하지 않고 Ctrl+D를 입력한 상황이다.
바로 입력이 끝나고 Sorting된 결과를 확인 할 수 있다.
이를 위해서는 입력 받을 때마다 입력받은 개수를 Count해주는 변수를 하나 설정해서
Sorting과 print할때 반복문에 이용하여야 한다.>