[SPARC] 35. Bubble Sort 구현

이번에는 지금까지 정리한 내용에 더불어 C 라이브러리를 활용하여 버블소트를 SPARC로 구현할 것이다.

C 코드

#include <stdio.h>
#incdlue <stdlib.h>
#incdlue <time.h>

struct sort_info {
    unsigned int num_items;
    unsigned int max_value;
};

unsigned int askNumber(char* message) {
    unsigned int val;
    register int result;
    
    do {
        printf("%s", message);
        result = scanf("%u", &val);
    } while (result != 1);
    return val;
}

struct sort_info askInfo() {
    struct sort_info si;
    si.num_items = askNumber("Enter number of items to sort> ");
    si.max_value = askNumber("Enter the maximum value> ");
    return si;
}

void compare_and_swap(int* p_a, int* p_b) {
    register int temp;
    if (*p_a > *p_b) {
        temp = *p_a;
        *p_a = *p_b;
        *p_b = temp;
    }
}

int main() {
    struct sort_info si = askInfo();
    
    register int * p_array = malloc(sizeof(int) * si.num_items);
    register int i, j;
    
    srand(time(NULL)); // Seed 설정
    
    for (i = 0; i < si.num_items; i++) {
        register int v = rand(); // random value 생성
        v = v % si.max_value;
        p_array[i] = v;
        printf("%u ", v);
    }
    printf("\n----\n");
    
    for (j = si.nums_items-1; j >= 0; j--) {
        for (i = 0; i< j; i++) {
            compare_and_swap( &p_array[i], %p_array[i+1] );
        }
    }
    
    for (i = 0; i < si.num_items; i++) {
        printf("%u ", p_array[i]);
    }
    
    printf("\n----\n");
    free(p_array);
    
    return 1;
}

 

위 소스코드를 어셈블리로 구현할 것이다.

벌써부터 보기만해도 한숨이 절로 나오지만... 한번 구현해보자.

(컴파일러의 필요성을 느낄 수 있는 예제..)

 

이 코드는 정렬할 아이템의 개수와 아이템이 가질 수 있는 값의 최댓값을 입력으로 넣으면, 해당 개수와 범위에 맞는 배열을 만들어주고, 그 배열을 bubble sort 방식으로 정렬한 결과를 보여주는 코드이다.

 

하나씩 구현해보자.

main 함수 (1) : 배열 생성하기

구체적인 함수 구현은 나중에 하더라도, 일단 함수 선언만 먼저 해두자.

main 함수의 스택 프레임 사이즈는 아래와 같다.

 

기본 64

함수 호출이 있으므로 (4 + 24)

6개를 넘는 추가 매개변수는 없다.

지역 변수에는 구조체 변수가 하나 있다.

해당 구조체는 unsigned int 형 변수를 2개 가지고 있으므로 구조체 하나당 8byte 사이즈를 가진다.

offset, int 형인 4의 배수에 맞추는 것 모두 고려하지 않아도 문제가 없으므로, 지역 변수 영역은 8byte 이다.

 

따라서 전체 필요한 스택 프레임의 사이즈는 64 + 4 + 24 + 8 = 100 byte

이를 8의 배수로 맞추면 104 byte 의 공간을 선언하면 된다.

askInfo(), malloc() 호출

 

malloc 함수는 heap 영역 메모리를 동적으로 할당하는 명령어로,

인자에는 할당할 메모리의 사이즈를 byte 단위로 입력한다.

askInfo() 함수로 정렬할 배열의 사이즈를 입력받아두었으므로,

그 사이즈와 int형 변수의 크기인 4를 곱한 값을 malloc 함수의 인자로 넘기면 된다.

Srand(), time() 함수 호출

 

이제 malloc 에 이어 srand 함수를 실행하여 시드를 설정하자.

srand 함수는 인자로 seed value 값을 넘겨주어야 한다.

보통 가장 많이 사용하는 seed value 값은 현재 시간이다.

이는 time 함수를 통해 가져올 수 있다.

 

time 함수에 0을 인자로 넘기면서 실행하고, 그 결과를 그대로 srand 함수에 넘겨준다.

랜덤값 생성 후 p_array 에 할당

 

이제 시드값 설정도 끝났으니 반복문을 돌면서 동적할당한 배열에 랜덤으로 생성한 값을 넣어주는 코드를 작성하자.

배열을 순회하는 예제를 작성했던 기억을 떠올리면서 코드를 작성하였다.

배열 원소 하나의 크기가 4byte 이므로 주소값도 인덱스가 하나 증가할 때마다 4byte 씩 증가하도록 계산해주면 된다.

위 코드는 i 에 4를 곱하는 방식으로 작성하였는데, 이렇게 안하고 매번 주소값을 4 씩 증가시켜도 된다.

 

이 상태에서 프로그램을 실행시키면 프로그램이 바로 종료된다.

 

아직 askInfo 함수가 없어 si.num_items 의 값을 넣어주지 못해 0이기 때문이다.

i = 0 일 때, si.num_items = 0 과 비교하므로 바로 반복문을 빠져나가서 프로그램이 종료된다.

 

반복문을 빠져나간 뒤, 수평선을 출력하는 코드를 추가해준다.

여기까지 한 상태에서, 한번 askInfo() 함수를 구현하여 사이즈를 입력받은 뒤 랜덤값이 잘 생성되는지 확인해보자.

askInfo() 함수 구현

struct sort_info askInfo() {
    struct sort_info si;
    si.num_items = askNumber("Enter number of items to sort> ");
    si.max_value = askNumber("Enter the maximum value> ");
    return si;
}

 

askInfo() 함수의 스택 프레임 사이즈를 먼저 계산해보자.

 

기본 64

함수 호출 있음 (4 + 24)

6개 초과 매개변수 없음

지역 변수 -> 구조체가 있으나, 구조체는 struct return pointer 위치를 이용하여 다루므로 따로 공간을 만들지 않음.

 

따라서 필요한 스택 프레임의 크기는 64 + 4 + 24 = 92 byte 이므로 선언시에는 96 byte 를 선언한다.

 

askInfo 함수를 호출할 때 분명 struct return pointer 를 넘겼을테니, 이 값을 %fp 를 통해 받아온뒤, 구조체의 멤버 변수에 접근하여 askNumber 함수의 호출 결과로 얻어온 값을 집어넣자.

 

구조체 return 부분 내용을 참고하면 예제와 동일한 코드라서 어렵지 않게 작성할 수 있다.

askNumber() 함수 구현

이제 askNumber 함수를 구현하자.

먼저 스택 프레임 사이즈를 계산해보자.

 

기본 64

내부에서 pinrtf, scanf 함수를 호출하므로 4 + 24

6개를 초과하는 매개변수는 없다.

지역 변수는 unsigned int val 하나만 있으므로 4byte를 선언하면 된다.

 

따라서 필요한 스택 프레임의 사이즈는 64 + 4 + 24 + 4 = 96 이고 이는 8의 배수이므로 96 byte 를 선언하면 된다.

 

askNumber 함수는 위와 같이 작성하였다.

do while 문은 어셈블리 분기문으로 작성하기가 더 편해서 좋다.

1차 테스트

테스트를 해보니 너무 많은 오류가 있어서 거의 1시간을 눈물의 똥꼬쇼를 하면서 고쳤다.

궁금하면 접은 글을 읽어보자...

이제 한번 테스트를 해보자.

 

askNumber 함수까지는 잘 들어오는데, 숫자를 넣고나면 에러가 난다.

 

core dumped 오류는 보통 메모리 접근 주소가 잘못되었을 때 일어난다.

그래서 한번 위 사진에 보이는 코드를 주석 처리하고 실행시켜 보았다.

 

이번엔 그 다음 함수까지 실행이 된다.

과연 무엇이 문제였을까?

바로 askInfo 함수를 호출 할 때, %sp + 64 위치에 구조체 주소를 선언하지 않은 것이 문제였다.

 

이렇게 수정을 해주었다.

다시 실행을 시켜보자.

 

이번엔 또 뭐가 문제일까..

 

이번엔 이 코드를 주석처리 해보았더니 실행이 됐다.

두번째로 최댓값을 입력받은 뒤, 그 값을 저장하는 코드이다.

 

이 부분이 문제였다.

8번 줄에서 add %sp, si, %o0 을 입력했는데, 여기에서 %sp 를 %fp 로 바꾸어 주어야 했다.

 

하지만 다시 실행시켜보니

 

어림도 없지.. 산순 연산 오류가 났다.

 

한 가지 다행인 점은 그래도 오류가 발생하는 명령줄을 생각보다 잘 찾아냈다..

이 코드를 주석처리하니 실행이 일단은 된다.

si 와 num_items 가 상수라서 저렇게 해도 상관 없을 거라고 생각했는데 안되나보다.

add 함수로 빼서 작성해보았다.

 

이렇게 수정하였다.

이번엔 오류가 출력되진 않으나, 여전히 배열이 생성되지 않고 있다.

이 바보야...

80번째 줄에 확인한다고 해둔 주석을 안풀어서 생긴 문제였다....

 

그런데 여전히 값을 1개만 만들고 있다.

이 바보야...22

 

값을 증가시킨 다음 다시 반복문으로 돌아가는 분기를 작성하지 않아서 생긴 문제였다..

아래 소스코드는 여기까지 디버깅을 한 뒤 실행에 성공한 코드이다.

.global main
si = -8
num_items = 0
max_value = 4
main:
  save %sp, -104, %sp

  add %fp, si, %o0
  st  %o0, [%sp + 64]
  call askInfo
  nop

  ! %l0 => p_array
  ! %l1 => i
  ! %l2 => j

  add %fp, si, %o0
  ld [%o0 + num_items], %l3  ! l3 = si.num_items
  call malloc
  sll %l3, 2, %o0             ! delay slot, malloc( l3 * 4 ), 4 == sizeof(int)
  mov %o0, %l0

  call time
  mov %g0, %o0                ! delay slot, time(0) == time(NULL)
  call srand                  ! time(0)'s result is still in %o0
  nop

  mov %g0, %l1                ! i = 0
loop_for_set_random_value_in_array:
  cmp %l1, %l3                ! i < si.num_items
  bge break_1
  nop

  ! register int v = rand()
  call rand
  nop

  ld [%fp + si + max_value], %o1  ! o1 => si.max_value
  call .rem                   ! v = v % si.max_value
  nop
  
  mov %o0, %l4                ! l4 => v

  ! calculate address for array[i]
  ! l5 => &array[i]
  sll %l1, 2, %l5             ! l5 = i * 4
  add %l5, %l0, %l5           ! l5 += array
  st %l4, [%l5]               ! p_array[i] = v
                              ! 4byte 부터는 어차피 32bit 를 저장하므로, signed, unsigned 명령어 구분 없음.
  ! print element
  set str_unsigned, %o0       ! printf("%u ", v)
  call printf
  mov %l4, %o1

  inc %l1                     ! i++
  ba loop_for_set_random_value_in_array
  nop

break_1:
  ! print line
  set line, %o0
  call printf
  nop

  mov 1, %g1
  ta 0


askInfo:
  save %sp, -96, %sp

  ld [%fp + 64], %l0              ! l0 = si's address

  set str_ask_number, %o0
  call askNumber
  nop
  st %o0, [%l0 + num_items] ! si.num_items = askNumber("~~")

  set str_ask_max, %o0
  call askNumber
  nop
  st %o0, [%l0 + max_value] ! si.max_value = askNumber("~~")

  ret
  restore

askNumber:
  val = -4
  save %sp, -96, %sp

  ! %l0 => result
loop_for_scanf:
  set str_s, %o0
  call printf
  mov %i0, %o1        ! printf("%s", message)

  set str_u, %o0
  call scanf
  add %fp, val, %o1   ! scanf("%u", &val)

  cmp %o0, 1
  bne loop_for_scanf  ! while (result != 1)
  nop

  ld [%fp + val], %i0 ! set val as return

  ret
  restore

.data
str_unsigned:
  .asciz	"%u "
line:
  .asciz	"\n----\n"
str_ask_number:
  .asciz  "Enter number of items to sort> "
str_ask_max:
  .asciz  "Enter the maximum value> "
str_s:
  .asciz	"%s"
str_u:
  .asciz  "%u"

 

 

성공적으로 랜덤값 10개를 생성하는데 성공했다.

main() 함수 (2) : Bubble Sort 코드 작성하기

이제 2중 for 문을 돌면서 정렬을 진행해보자.

 

이렇게 2중 for문 틀을 잡아두었다.

내부 for 문에 이렇게 p_array[i] 와 p_array[i+1] 의 주소값을 계산하여 인자로 넘기는 코드를 작성한다.

그 뒤, compare_and_swap 함수를 호출한다.

compare_and_swap() 함수

얼마 안남았다.

compare_and_swap 서브루틴을 작성해보자.

그런데 이 서브루틴은 내부에 지역변수도 없고, 함수도 호출하지 않으며, 매개변수도 6개를 넘지 않는다.

 

그렇다면 스택 프레임이 필요없는 서브루틴이다.

따라서 이 서브루틴은 리프 서브루틴으로 구현해보자.

 

포인터 매개변수 예제와 완전 동일하다.

main() 함수 (3) : 정렬 결과 출력하기

이제 마지막으로 정렬 결과를 출력하면 된다.

 

이 부분에서 막혀서 장난아니게 애를 먹었다.

디버거로 찍어보면 모든 값이 올바르게 들어있는데 마지막 결과 배열이 출력되지 않는 문제가 발생했다.

일단 찾아낸 해결책은 마지막 배열 원소를 모두 출력하기 전에 개행을 한번 더 해주는 것으로 해결했다.

그런데 대체 왜 이런 문제가 발생하는건지는 이해를 못하겠다..

 

결과는 잘 나온다.

이렇게 마무리 하는건 너무 찝찝해서 아주 킹받지만.. 이게 나의 최선인 것 같다.

마지막에 free 만 해주는 것으로 마무리하자.

 

.global main
si = -8
num_items = 0
max_value = 4
main:
  save %sp, -104, %sp

  add %fp, si, %o0
  st  %o0, [%sp + 64]
  call askInfo
  nop

  ! %l0 => p_array
  ! %l1 => i
  ! %l2 => j

  add %fp, si, %o0
  ld [%o0 + num_items], %l3  ! l3 = si.num_items
  call malloc
  sll %l3, 2, %o0             ! delay slot, malloc( l3 * 4 ), 4 == sizeof(int)
  mov %o0, %l0

  call time
  mov %g0, %o0                ! delay slot, time(0) == time(NULL)
  call srand                  ! time(0)'s result is still in %o0
  nop

  mov %g0, %l1                ! i = 0
loop_for_set_random_value_in_array:
  cmp %l1, %l3                ! i < si.num_items
  bge break_1
  nop

  ! register int v = rand()
  call rand
  nop

  ld [%fp + si + max_value], %o1  ! o1 => si.max_value
  call .rem                   ! v = v % si.max_value
  nop
  
  mov %o0, %l4                ! l4 => v

  ! calculate address for array[i]
  ! l5 => &array[i]
  sll %l1, 2, %l5             ! l5 = i * 4
  add %l5, %l0, %l5           ! l5 += array
  st %l4, [%l5]               ! p_array[i] = v
                              ! 4byte 부터는 어차피 32bit 를 저장하므로, signed, unsigned 명령어 구분 없음.

  ! print element
  set str_unsigned, %o0       ! printf("%u ", v)
  call printf
  mov %l4, %o1

  inc %l1                     ! i++
  ba loop_for_set_random_value_in_array
  nop

break_1:
  ! print line
  set line, %o0
  call printf
  nop

  add %fp, si, %o0
  ld [%o0 + num_items], %l2 ! j = si.num_items
  dec %l2                   ! j -= 1
loop_for_sort_out:
  cmp %l2, 0
  bl break_2
  nop

  mov %g0, %l1              ! i = 0
loop_for_sort_inner:
  cmp %l1, %l2
  bge break_inner
  nop

  ! calculate %p_array[i]
  sll %l1, 2, %o0           ! o0 = i * 4
  add %o0, %l0, %o0         ! o0 = p_array + i * 4
  add %o0, 4, %o1           ! o1 = o0 + 4
  call compare_and_swap
  nop

  inc %l1                   ! i++
  ba loop_for_sort_inner
  nop

break_inner:
  dec %l2                    ! j--
  ba loop_for_sort_out
  nop

break_2:
  add %fp, si, %o0
  ld [%o0 + num_items], %l3 ! l3 = si.num_items
  mov %g0, %l1              ! i = 0
loop_print_result:
  cmp %l1, %l3
  bge break_3
  nop
  set str_unsigned, %o0

  ! calculate &p_array[i]
  sll %l1, 2, %l5
  add %l0, %l5, %l5
  ld [%l5], %o1             ! p_array[i]

  call printf
  nop

  inc %l1                    ! i++
  ba loop_print_result
  nop

break_3:
  set line, %o0
  call printf
  nop

  call free
  mov %l0, %o0

  mov 1, %g1
  ta 0


askInfo:
  save %sp, -96, %sp

  ld [%fp + 64], %l0              ! l0 = si's address

  set str_ask_number, %o0
  call askNumber
  nop
  st %o0, [%l0 + num_items] ! si.num_items = askNumber("~~")

  set str_ask_max, %o0
  call askNumber
  nop
  st %o0, [%l0 + max_value] ! si.max_value = askNumber("~~")

  ret
  restore

askNumber:
  val = -4
  save %sp, -96, %sp

  ! %l0 => result
loop_for_scanf:
  set str_s, %o0
  call printf
  mov %i0, %o1        ! printf("%s", message)

  set str_u, %o0
  call scanf
  add %fp, val, %o1   ! scanf("%u", &val)

  cmp %o0, 1
  bne loop_for_scanf  ! while (result != 1)
  nop

  ld [%fp + val], %i0 ! set val as return

  ret
  restore

compare_and_swap:
  ld [%o0], %o4 ! *p_a
  ld [%o1], %o5 ! *p_b

  cmp %o4, %o5
  ble end
  nop

  st %o4, [%o1]
  st %o5, [%o0]
end:
  retl
  nop


.data
str_unsigned:
  .asciz	"%u "
line:
  .asciz	"\n----\n\n"
str_ask_number:
  .asciz  "Enter number of items to sort> "
str_ask_max:
  .asciz  "Enter the maximum value> "
str_s:
  .asciz	"%s"
str_u:
  .asciz  "%u"

str_test:
  .asciz	"\n"

 

전체 소스코드는 다음과 같다.

 

이것으로 서브루틴의 모든 내용을 정리하였다.

다음 글에서는 새로운 주제인 '실수' 에 대해 정리하고자 한다.