在数组 MIPS 中查找第 K 个不同的元素

Finding Kth distinct element in an array MIPS

我正在尝试编写与下面的 C 代码等效的 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 中。

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

main: lw $s0,K([=11=]) # K 
      addi $t0,$zero,0 # index for outer loop
      addi $t1,$zero,0 # index for inner loop
      lw   $t2,sze([=11=])
      lw   $s1,Array([=11=])
      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

虽然我希望在 $s1 寄存器中看到 8,但我得到了 1。我的汇编代码有什么问题?

有些事情是错误的。

您的 C 代码不完整。通过检查您的 asm 代码,我能够将缺失的内容添加到 C 代码中。

您没有正确设置一些寄存器。

您还比较了数组偏移量(递增 4 的迭代变量)与数组 index/count,因此比较不起作用。

您将 KCtr 的寄存器设置为 1,而不是执行 KCtr++

的 asm 等价物

我创建了三个示例:固定的 C 代码,您的 asm 的注释版本显示了 some/most 个错误。并且,一个清理、重构和工作的版本。


这是 C 代码:

#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([=11=])               # 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([=11=])             # get array count
    lw      $s1,Array([=11=])           # 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

这是重构后的版本。它与您的有所不同,因为为了使其正常工作,我对其进行了一些简化。它还使用指针而不是索引或偏移量来访问数组。还要注意,一旦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

更新:

Your code seems to be working in spim. But I didn't understand "ArrayEnd". There is no value set for it,but it works. How ?

ArrEnd 是某种 "trick"。是Array+1的最后一个元素的地址。也就是说,在C中,如果我们有int Array[5],那么ArrEnd就是&Array[5]

就像在 C 中一样,我们可以选择如何遍历数组。我们可以使用索引并执行:Array[i]。或者,我们可以使用 int * 指针。在 asm 中,我们可以使用从数组开始的偏移量(即 index << 2)。

让我们将 C 程序重新编码为 使用指针 [而不是索引] 遍历数组。这在 C 代码中不常使用,但它对 asm 很方便。以下实际上是我的第二个 asm 示例所做的更准确的 C 代码表示:

#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

现在我们有了这些值,我们可以通过上述三种方法中的任何一种来遍历数组。使用偏移版本或指针版本通常可以更有效。

要了解 ArrEnd 使事情变得多么简单,请注释掉较大的数组并从 C 代码中添加较短的数组。 ArrEnd 技巧将自动调整 而无需 需要手动计算 Array

中的元素数量

更新#2:

我可能对此有误,但进一步思考,为了满足问题标题的要求,C代码[以及因此asm]可能需要更改。

我认为内部循环在查找重复项时必须扫描 整个 数组 [跳过 i == o 所在的元素]。否则可能会误报。

还有,看来原文从来不认为index 0元素是唯一的,即使是。这是因为 o 循环从索引 1 开始。

我创建了两种算法。原文如上。还有一个进行全面扫描的。我还添加了更多测试用例来说明我正在考虑的问题。

测试程序如下:

#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;
}

程序输出如下:

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

说明这两个问题的最简单测试是 Array5Array6

对应的asm代码如下:

    .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