1. 홈
  2. 질의 응답
  3. 배열의 K 번째 고유 요소 찾기 MIPS

배열의 K 번째 고유 요소 찾기 MIPS

2016-10-30 9 views
0

아래의 C 코드와 동일한 MIPS 코드를 작성하려고합니다.배열의 K 번째 고유 요소 찾기 MIPS

int arrayData[5] = { 1,2,1,3,4 }; 
int K = 3; 
int KCtr = 0; 
int result; 
bool isUnique; 
for (int o = 1; o < 5; o++) 
{ 
    isUnique = true; 
    for (int i = 0; i < o; i++) 
    { 
     if (arrayData[o] == arrayData[i]) 
     { 
      isUnique = false; 
      break; // goto outer loop 
     } 
    } 
    if (isUnique) 
    { 
     KCtr++; 
    } 
    if (KCtr==K) 
    { 
     result = arrayData[o]; 
    } 
}

아래 코드로 결과를 $s1에 저장하고 싶습니다. 내가 $s1 레지스터에 8을 볼 것으로 예상하고 있지만

.data 
Array: .word 1, 2, 4, 8, 16, 32, 64, 128 
sze : .word 8 
K : .word 3 
.text 
.globl main 

main: lw $s0,K($0) # K 
     addi $t0,$zero,0 # index for outer loop 
     addi $t1,$zero,0 # index for inner loop 
     lw $t2,sze($0) 
     lw $s1,Array($0) 
     addi $t6,$zero,0 
     #addi $t7,$zero,1 
     #t3 for array[o] 
     #t4 for array[i] 
     #t5 for unique flag 
     #t6 for counter to reach K 
     #t7 for storing 1 
outerloop: 
    beq $t0,$t2,finish 
    lw $t3,Array($t0) 
    addi $t5,$zero,0 
innerloop: 
    lw $t4,Array($t1)  
    bne $t3,$t4,else 
    addi $t5,$zero,1 
else: 

checkifunique: 
    beq $t5,$t7,isnotuniquebypass 
    addi $t6,$zero,1 
isnotuniquebypass: 
    addi $t1,$t1,4 
    blt $t1,$t0,innerloop 

    bne $t6,$s0,notreachedKbypass 
    lw $s1,Array($t0) 

notreachedKbypass: 

    addi $t0,$t0,4 
    b outerloop 


finish: 
     li $v0,10 
     syscall

, 나는 1을 얻고있다. 내 어셈블리 코드가 잘못 되었나요?

출처

2016-10-30 Muhammet Ali Asan

답변

2

몇 가지 문제가있었습니다.

C 코드가 불완전합니다. asm 코드를 검사하여 C 코드에 누락 된 항목을 추가 할 수있었습니다.

일부 레지스터를 올바르게 설정하지 않았습니다.

배열 인덱스/카운트와 비교하여 배열 오프셋 (반복 증가 변수 4)을 비교 했으므로 비교가 작동하지 않습니다.

당신은 1 KCtr의 레지스터를 설정하는 대신에 나는 세 가지 예 생성 KCtr++

의 ASM 상응하는 일을했다 : 고정 된 C 코드의 일부를 보여주는 ASM의 주석 버전/버그의 대부분. 그리고 정리 된 리팩토링 된 버전입니다.

#include <stdio.h> 

#if 0 
int Array[] = { 1, 2, 1, 3, 4 }; 
#else 
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 
#endif 

int 
main(void) 
{ 
    int result; 
    int K = 3; 
    int KCtr = 0; 
    int count = sizeof(Array)/sizeof(Array[0]); 
    int uniqflg; 

    result = -1; 

    for (int o = 1; o < count; o++) { 
     uniqflg = 1; 
     for (int i = 0; i < o; i++) { 
      if (Array[o] == Array[i]) { 
       uniqflg = 0; 
       break; 
      } 
     } 
     if (! uniqflg) 
      continue; 

     KCtr++; 
     if (KCtr == K) { 
      result = Array[o]; 
     } 
    } 

    printf("result=%d\n",result); 

    return result; 
}

가 여기에 주석 버전입니다 :

.data 
Array:  .word  1,2,4,8,16,32,64,128 
    sze  : 
    K  : 

    .text 
    .globl main 

# s1 for result 
# t0 for o 
# t1 for i 
# t2 for array count 
# t3 for array[o] 
# t4 for array[i] 
# t5 for unique flag 
# t6 for counter to reach K (i.e. KCtr?) 
# t7 for storing 1 
main: 
    lw  $s0,K($0)    # K 
    addi $t0,$zero,0    # index for outer loop 

# NOTE/BUG: this is misplaced it needs to be moved to just above innerloop 
    addi $t1,$zero,0    # index for inner loop 

    lw  $t2,sze($0)    # get array count 
    lw  $s1,Array($0)   # result = Array[0] 
    addi $t6,$zero,0    # KCtr = 0 
# NOTE/BUG: this was commented out: 
    addi $t7,$zero,1 

outerloop: 
    # NOTE/BUG: based on the increment by 4 to $t0 below, this is comparing an 
    # offset against a count 
    beq  $t0,$t2,finish   # o < count? if no, fly 
    lw  $t3,Array($t0)   # get Array[o] 
    addi $t5,$zero,0    # uniqflg = 0 

innerloop: 
    lw  $t4,Array($t1)   # get Array[i] 
    bne  $t3,$t4,inner_neq  # Array[o] == Array[i]? if no, fly 

# NOTE/BUG: this is just setting one (i.e. KCtr = 1 instead of KCtr++) 
    addi $t5,$zero,1    # uniqflg = 1 

inner_neq: 

checkifunique: 
    beq  $t5,$t7,notuniq   # ??? 
    addi $t6,$zero,1 

notuniq: 
    addi $t1,$t1,4    # advance array offset 

    # NOTE/BUG: this compares an array offset against an index 
    blt  $t1,$t0,innerloop  # at end? if no, loop 

    bne  $t6,$s0,inner_next  # KCtr == K? if no, interate 
    lw  $s1,Array($t0)   # get better result 

inner_next: 
    addi $t0,$t0,4    # advance o [as offset] 
    b  outerloop 

finish: 
    li  $v0,10 
    syscall

가 여기에 리팩토링 버전의

다음은 C 코드입니다. 작동 시키려면 다소 단순화했기 때문에 다소 차이가 있습니다. 또한 배열 액세스를 위해 인덱스 또는 오프셋 대신 포인터를 사용합니다. 또한 한 번 KCtr == K, 그 루프를 계속할 필요가 없다는 것을 유의하십시오.

는 
.data 
Array:  .word  1,2,4,8,16,32,64,128 
ArrEnd: 
K:   .word  3 

    .text 
    .globl main 

# s0 for K 
# s1 for result 
# t0 for o (as pointer) 
# t1 for i (as pointer) 
# t2 for array count 
# t3 for array[o] 
# t4 for array[i] 
# t6 for counter to reach K (i.e. KCtr?) 
main: 
    lw  $s0,K     # K 
    li  $t6,0     # KCtr = 0 

    la  $t2,ArrEnd    # point to end of array 
    la  $t0,Array    # o = &Array[0] 
    lw  $s1,0($t0)    # result = Array[0] 

outerloop: 
    addiu $t0,$t0,4    # advance o [as pointer] 
    bgeu $t0,$t2,finish   # o < ArrEnd? if no, fly 
    lw  $t3,0($t0)    # get Array[o] 

    la  $t1,Array    # i = &Array[0] 

innerloop: 
    lw  $t4,0($t1)    # get Array[i] 
    beq  $t3,$t4,outerloop  # Array[o] == Array[i]? if yes, not unique 

    addiu $t1,$t1,4    # advance array pointer for i 
    bltu $t1,$t0,innerloop  # at end? if no, loop 

    # current array value is unique 
    addi $t6,$t6,1    # KCtr++ 
    bne  $t6,$s0,outerloop  # KCtr == K? if no, wait for next unique 
    lw  $s1,0($t0)    # get better result -- no need to loop more 

finish: 
    li  $v0,1 
    move $a0,$s1 
    syscall 

    li  $v0,10 
    syscall

UPDATE :

코드는 스핌에서 작동하는 것 같군. 하지만 "ArrayEnd"를 이해하지 못했습니다. 그것에 대한 가치는 없지만 효과적입니다. 어떻게?

ArrEnd은 "트릭"종류입니다. 마지막 요소의 주소는 Array + 1입니다. 즉, C에서 int Array[5]이면 ArrEnd은 &Array[5]입니다.

C와 마찬가지로 배열을 반복하는 방법을 선택할 수 있습니다. 우리는 색인을 사용하여 다음을 수행 할 수 있습니다 : Array[i]. 또는 int * 포인터를 사용할 수 있습니다. asm에서는 배열의 시작 부분에서 오프셋 (예 : index << 2)을 사용할 수 있습니다.

C 프로그램을 으로 다시 코딩 해 봅시다. 포인터 만 사용하여 배열을 반복 할 수 있습니다. 이것은 C 코드에서 자주 사용되지 않지만, asm에서는 유용합니다. 여기 

#include <stdio.h> 

#if 0 
int Array[] = { 1, 2, 1, 3, 4 }; 
#else 
int Array[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 
#endif 

int 
main(void) 
{ 
    int result; 
    int K = 3; 
    int KCtr = 0; 
    int *ArrEnd = &Array[sizeof(Array)/sizeof(Array[0])]; 
    int uniqflg; 

    result = -1; 

    for (int *o = &Array[1]; o < ArrEnd; o++) { 
     uniqflg = 1; 
     for (int *i = &Array[0]; i < o; i++) { 
      if (*o == *i) { 
       uniqflg = 0; 
       break; 
      } 
     } 
     if (! uniqflg) 
      continue; 

     KCtr++; 
     if (KCtr == K) { 
      result = *o; 
      break; 
     } 
    } 

    printf("result=%d\n",result); 

    return result; 
}

이 ArrEnd에 대한 몇 가지 관용적 사용은 다음과 같습니다 : 이제 

la  $s0,Array    # get array address 
    la  $s1,ArrEnd    # address of array end [one past last] 
    subu $s2,$s1,$s0    # get byte length of array 
    srl  $s3,$s2,2    # get array count

우리는이 값을 가지고, 우리는 반복 할 수 다음은 실제로 내 두 번째 ASM 예제가 무슨 짓을했는지에 대한보다 정확한 C 코드 표현입니다 위의 세 가지 방법 중 하나를 통해 배열을 통해. 오프셋 버전이나 포인터 버전을 사용하면 대개보다 효율적입니다.

ArrEnd이 얼마나 쉬운 지 확인하려면 더 큰 배열을 주석으로 처리하고 C 코드에서 더 짧은 배열을 추가하십시오. 에,이

나는 이것에 대해 잘못 될 수도 있지만 더 반사에 따라 다음 ArrEnd 트릭은 Array

UPDATE # 2에서 수동으로 요소의 수를 계산 할 필요없이 자동으로 일을 조정합니다 질문 제목의 요구 사항을 충족하면 C 코드 [따라서 asm]를 변경해야 할 수도 있습니다.

내부 루프가 전체 배열을 스캔해야한다고 생각합니다. [i == o] 배열을 건너 뛰면 중복을 찾을 수 있습니다. 그렇지 않으면 오탐 (false positive)이 발생할 수 있습니다.

또한 원본에서는 인덱스 0 요소가 고유 한 것으로 생각하지 않는다고합니다. 이는 o 루프가 인덱스 1로 시작했기 때문입니다.

두 알고리즘을 만들었습니다. 위의 원본. 그리고 전체 스캔을하는 사람. 또한 내가 생각하고있는 문제를 설명하기 위해 몇 가지 테스트 케이스를 추가했습니다.

Array0: 1 2 1 3 4 
    orig: MATCH value=2 index=1 
    orig: MATCH value=3 index=3 
    orig: MATCH value=4 index=4 
    orig: FINAL result=4 residx=4 

    full: MATCH value=2 index=1 
    full: MATCH value=3 index=3 
    full: MATCH value=4 index=4 
    full: FINAL result=4 residx=4 

    test: PASS orig=4 full=4 

Array1: 1 2 4 8 16 32 64 128 
    orig: MATCH value=2 index=1 
    orig: MATCH value=4 index=2 
    orig: MATCH value=8 index=3 
    orig: FINAL result=8 residx=3 

    full: MATCH value=1 index=0 
    full: MATCH value=2 index=1 
    full: MATCH value=4 index=2 
    full: FINAL result=4 residx=2 

    test: FAIL orig=8 full=4 

Array2: 1 2 4 4 8 16 32 64 128 
    orig: MATCH value=2 index=1 
    orig: MATCH value=4 index=2 
    orig: MATCH value=8 index=4 
    orig: FINAL result=8 residx=4 

    full: MATCH value=1 index=0 
    full: MATCH value=2 index=1 
    full: MATCH value=8 index=4 
    full: FINAL result=8 residx=4 

    test: PASS orig=8 full=8 

Array3: 1 2 4 8 16 32 64 128 2 
    orig: MATCH value=2 index=1 
    orig: MATCH value=4 index=2 
    orig: MATCH value=8 index=3 
    orig: FINAL result=8 residx=3 

    full: MATCH value=1 index=0 
    full: MATCH value=4 index=2 
    full: MATCH value=8 index=3 
    full: FINAL result=8 residx=3 

    test: PASS orig=8 full=8 

Array4: 1 2 4 8 16 32 64 128 2 4 
    orig: MATCH value=2 index=1 
    orig: MATCH value=4 index=2 
    orig: MATCH value=8 index=3 
    orig: FINAL result=8 residx=3 

    full: MATCH value=1 index=0 
    full: MATCH value=8 index=3 
    full: MATCH value=16 index=4 
    full: FINAL result=16 residx=4 

    test: FAIL orig=8 full=16 

Array5: 1 2 3 4 5 6 
    orig: MATCH value=2 index=1 
    orig: MATCH value=3 index=2 
    orig: MATCH value=4 index=3 
    orig: FINAL result=4 residx=3 

    full: MATCH value=1 index=0 
    full: MATCH value=2 index=1 
    full: MATCH value=3 index=2 
    full: FINAL result=3 residx=2 

    test: FAIL orig=4 full=3 

Array6: 1 2 3 4 5 6 1 3 
    orig: MATCH value=2 index=1 
    orig: MATCH value=3 index=2 
    orig: MATCH value=4 index=3 
    orig: FINAL result=4 residx=3 

    full: MATCH value=2 index=1 
    full: MATCH value=4 index=3 
    full: MATCH value=5 index=4 
    full: FINAL result=5 residx=4 

    test: FAIL orig=4 full=5

모두 문제 Array5있는 예시 간단한 테스트 및 Array6

여기

대응 ASM 코드이다 : 여기 

#include <stdio.h> 

int Array0[] = { 1, 2, 1, 3, 4 }; 
int Array1[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 
int Array2[] = { 1, 2, 4, 4, 8, 16, 32, 64, 128 }; 
int Array3[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2 }; 
int Array4[] = { 1, 2, 4, 8, 16, 32, 64, 128, 2, 4 }; 
int Array5[] = { 1, 2, 3, 4, 5, 6 }; 
int Array6[] = { 1, 2, 3, 4, 5, 6, 1, 3 }; 

int K = 3; 
int sepflg; 
int tstno; 

int 
orig(int *Array,int *ArrEnd) 
{ 
    int result; 
    long residx; 
    int KCtr = 0; 
    int uniqflg; 

    result = -1; 
    residx = -1; 

    for (int *o = &Array[1]; o < ArrEnd; o++) { 
     uniqflg = 1; 
     for (int *i = &Array[0]; i < o; i++) { 
      if (*o == *i) { 
       uniqflg = 0; 
       break; 
      } 
     } 
     if (! uniqflg) 
      continue; 

     printf(" orig: MATCH value=%d index=%ld\n",*o,o - Array); 

     KCtr++; 
     if (KCtr == K) { 
      result = *o; 
      residx = o - Array; 
      break; 
     } 
    } 

    printf(" orig: FINAL result=%d residx=%ld\n",result,residx); 

    return result; 
} 

int 
full(int *Array,int *ArrEnd) 
{ 
    int result; 
    long residx; 
    int KCtr = 0; 
    int uniqflg; 

    result = -1; 
    residx = -1; 

    for (int *o = &Array[0]; o < ArrEnd; o++) { 
     uniqflg = 1; 
     for (int *i = &Array[0]; i < ArrEnd; i++) { 
      if (o == i) 
       continue; 
      if (*o == *i) { 
       uniqflg = 0; 
       break; 
      } 
     } 
     if (! uniqflg) 
      continue; 

     printf(" full: MATCH value=%d index=%ld\n",*o,o - Array); 

     KCtr++; 
     if (KCtr == K) { 
      result = *o; 
      residx = o - Array; 
      break; 
     } 
    } 

    printf(" full: FINAL result=%d residx=%ld\n",result,residx); 

    return result; 
} 

void 
test(int *Array,long siz) 
{ 
    int *ArrEnd = &Array[siz/sizeof(int)]; 
    int oval; 
    int fval; 

    if (sepflg) 
     printf("\n"); 
    sepflg = 1; 

    printf("Array%d:",tstno); 
    for (int *ptr = Array; ptr < ArrEnd; ++ptr) 
     printf(" %4d",*ptr); 
    printf("\n"); 

    oval = orig(Array,ArrEnd); 
    printf("\n"); 
    fval = full(Array,ArrEnd); 

    printf("\n"); 
    printf(" test: %s orig=%d full=%d\n", 
     (oval == fval) ? "PASS" : "FAIL",oval,fval); 

    ++tstno; 
} 

int 
main(void) 
{ 

    test(Array0,sizeof(Array0)); 
    test(Array1,sizeof(Array1)); 
    test(Array2,sizeof(Array2)); 
    test(Array3,sizeof(Array3)); 
    test(Array4,sizeof(Array4)); 
    test(Array5,sizeof(Array5)); 
    test(Array6,sizeof(Array6)); 

    return 0; 
}

프로그램 출력이다 : 여기

테스트 프로그램 :

.data 
Array:  .word  1, 2, 3, 4, 5, 6, 1, 3 
ArrEnd: 
K:   .word  3 

    .text 
    .globl main 

# s0 for K 
# s1 for result 
# t0 for o (as pointer) 
# t1 for i (as pointer) 
# t2 for array count 
# t3 for array[o] 
# t4 for array[i] 
# t6 for counter to reach K (i.e. KCtr?) 
main: 
    lw  $s0,K     # K 
    li  $t6,0     # KCtr = 0 

    la  $t2,ArrEnd    # point to end of array 
    la  $t0,Array    # o = &Array[0] 
    li  $s1,-1     # get fail value 
    b  outstart 

outerloop: 
    addiu $t0,$t0,4    # advance o [as pointer] 
outstart: 
    bgeu $t0,$t2,finish   # o < ArrEnd? if no, fly 
    lw  $t3,0($t0)    # get Array[o] 

    la  $t1,Array    # i = &Array[0] 

innerloop: 
    lw  $t4,0($t1)    # get Array[i] 
    beq  $t1,$t0,innernext  # o == i? if yes, skip test 
    beq  $t3,$t4,outerloop  # Array[o] == Array[i]? if yes, not unique 
innernext: 
    addiu $t1,$t1,4    # advance array pointer for i 
    bltu $t1,$t2,innerloop  # at end? if no, loop 

    # current array value is unique 
    addi $t6,$t6,1    # KCtr++ 
    bne  $t6,$s0,outerloop  # KCtr == K? if no, wait for next unique 
    lw  $s1,0($t0)    # get better result -- no need to loop more 

finish: 
    li  $v0,1 
    move $a0,$s1 
    syscall 

    li  $v0,10 
    syscall

출처

2016-10-30 22:14:24

+0

고맙습니다. C와 어셈블리 코드에서 내 어리석은 실수를 봅니다. 코드가 스핌에서 작동하는 것 같습니다. 하지만 "ArrayEnd"를 이해하지 못했습니다. 그것에 대한 가치는 없지만 효과적입니다. 어떻게? –

 관련 문제

  • 관련 문제 없음^_^