[SPARC] 비트처리 연산

문제 정의

 

 

비트 처리 연산

0부터 63까지의 수를 저장하는 집합에 대한 연산을 구현하려 한다. 집합은 정적 영역에 set1, set2, set3 이란 이름으로 정의한다. set1, set2, set3의 각 비트는 63, 62, ...,2, 1, 0를 나타내고, 해당 하는 수가 집합에 속해 있으면 그 비트가 1 아니면 0으로 지정된다. 초기에는 테스트 하려고 하 는 집합을 정의하면 된다.

•   member(j, set): j 가 set의 원소이면 1을 반환

•   union: 합집합. set3 = set1 ∪ set2

•   intersection: 교집합. set3 = set1 ∩ set2

•   subtract: 차집합. set3 = set1 - set2

•   add(j, set): 집합 set에 원소 j를 추가

•   mapinc(set,d): set의 각 원소에 d를 더한 집합. 예를 들어 set({1, 13, 17}, 1) = {2, 14, 18}

  이다.

  제출물

•   위 3개의 함수만 정의되어 있는 파일을 제출한다. main과 집합 set1, set2가 정의되는 파 일은 제출하지 않는다. 각자 테스팅을 위해 별도로 만들어 연결하여 실행하는데 사용한 다.

설계

1. 집합은 정적영역에 set1, set2, set3 이란 이름으로 정의.

2. set1, set2,set 3 의 각 비트는 63,62,61....,2,1,0 을 나타냄.

3. 해당 하는 수가 집합에 속해 있으면 그 비트가 1 아니면 0 으로 지정됨.

4. 초기 테스트 하려는 집합 정의.

< 별볼일 없는 소스 코드.. >

1. member(j,set) 함수 > 결과값 0 or 1

*해당 소스코드를 돌리시려면 굵은 글씨 주석을 풀어주세요.

!.section ".data"

!set1:.word 1,4,5,16

!set2:.word 1,4,7,23

!

!.section ".text"

!!local variables

!n = -4

! index i in $l0

! max in $l1

! .global main

!main : save %sp,-96,%sp

! set set1, %l2

!    st %l2,[%sp + 16]

! set set2, %l3

!    st %l3,[%sp + 32]

!    mov 16,%o0

!    call member

!    mov %l2,%o1

!test : ret

! restore

!N=4 ! ( if N = 4 , it's only works in {a,b,c,d} just 4 objects)

 

 

    .global member

member : save %sp,-96,%sp

         mov 1,%l0 ! move 1 to l0

         sll %l0,N,%l5 ! 2^N to l5 (this time 2^4 = 16 )

         add %fp,%l5,%o3 ! address %fp+16

         ld [%o3],%o0 ! right value of [%fp+16]

         cmp %i0,%o0 ! x == [%fp+16] ?

         be,a isexist ! if yes goto isexist return

         ba loop ! or not goto loop

indexup : inc %l0 ! increase index ++

loop:   sll %l0,2,%l2 ! address l2 = i*4

        add %o0,%l2,%o1 ! [%fp+16+i*4]

        ld [%o1],%l1    ! load [%fp+16+i*4]

        cmp %i0,%l1     ! x== [%fp+16+i*4]

        be isexist      ! if equal then goto isexist

        cmp %l0,N       ! %l0 < N

        bl,a indexup    ! if true goto indexup

        nop

nonexist: mov 0,%i0 ! return value 0 - not exist

          ret

          restore

isexist: mov 1,%i0 ! return value 1 - it's exist

         ret

         restore

2. add(j,set) 함수 >  { 1,3,4, j }

*해당 소스코드를 돌리시려면 굵은 글씨 주석을 풀어주세요.

!.section ".data"

!set1:.word 1,4,5,16

!

!.section ".text"

!local variables

!n = -4

!

! index i in $l0

! max in $l1

!

! .global main

!main : save %sp,-96,%sp

! set set1, %l2

!    mov 44,%o1

!    call add

!    mov %l2,%o0

!test : ret

! restore

 

!N=4 ! ( if N = 4 , it's only works in {a,b,c,d} just 4 objects)

            .global add

add :    save %sp,-96,%sp

            mov 1,%l0

            mov %i0,%o0;

            sll %l0,N,%l5 ! 2^N to l5 (this time 2^4 = 16 )

            add %i0,%l5,%i0

            st %i1,[%i0]

 

addend:     ret

            restore

3. mapinc(set,d) 함수 >  {1,3,4} , d= 1 > {2,4,5}

*해당 소스코드를 돌리시려면 굵은 글씨 주석을 풀어주세요.

!.section ".data"

!set1:.word 1,4,5,16

!set2:.word 1,4,7,23

!

!.section ".text"

!local variables

!n = -4

!

! index i in $l0

! max in $l1

!

! .global main

!main : save %sp,-96,%sp

! set set1, %l2

!    st %l2,[%sp + 16]

!    mov 1,%o1

!    call mapinc

!   mov %l2,%o0

!test : ret

! restore

!

!N=4 ! ( if N = 4 , it's only works in {a,b,c,d} just 4 objects)

 

            .global mapinc

mapinc :    save %sp,-96,%sp

            mov 1,%l0

            sll %l0,N,%l5 ! 2^N to l5 (this time 2^4 = 16 )

            add %fp,%l5,%o3 ! address %fp+16

            ld [%o3],%o0 ! right value of [%fp+16]

            ba loop ! or not goto loop

            clr %l0

indexup :   inc %l0 ! increase index ++

loop:       sll %l0,2,%l2 ! address l2 = i*4

            add %o0,%l2,%o1 ! [%fp+16+i*4]

            ld [%o1],%l1    ! load [%fp+16+i*4]

            add %l1,%i1,%l1 ! add  %l1 = %l1 + %i1

            st %l1,[%o1]    ! store %l1 to [%fp+16+i*4]

            cmp %l0,N       ! compare %l0 < N

            bl,a indexup    ! if true goto indexup

            nop

            ret

            restore

별거 없는 소스코드들이 모두 끝났습니다...

이번 과제를 하면서 느낀건 배열의 주소를 접근할때 bit 처리를 하면 따로 mul 을 사용하여 주소 계산을 하지 않아도 된다는 것입니다. 매우 편리합니다.

물론, 소스가 최적화 되어 있지 않습니다. 저는 왕초보이니까요..

대략 소스 짜는데 6시간의 삽질이 걸렸습니다. 디버깅을 해서 메모리에 뭐가있는지 하나하나 확인해보았습니다.

아, 디버깅시 사용하는 명령어로는..

- gcc -g main.c -o main     ::  main.c 파일을 global 레이블 참조가능하게 컴파일하고, main 이라는 이름의 실행파일을 뱉어낸다.

- gdb main   :: main 을 디버깅한다.

- p $i0    ::  %i0  ,  i0 레지스트의 값을 출력한다.

- p set1@n   ::  정적변수 set1 의 n 번째 값까지 확인한다 

ex) -p set1@3    >> {1 , 4 , 5 }

제가 이해한 내용들이 많이 틀렸을 수 있습니다. 바로 잡아주시면 수정하도록 하겠습니다.

감사합니다.